Extremal Problems for GCDs and LCMs in Higher Dimensions

Haozhe Gou

arxiv: 2604.21122 · v1 · submitted 2026-04-22 · 🧮 math.NT

Extremal Problems for GCDs and LCMs in Higher Dimensions

Haozhe Gou This is my paper

Pith reviewed 2026-05-09 22:52 UTC · model grok-4.3

classification 🧮 math.NT

keywords gcdlcmextremal problemshigher dimensionsmeasure concentrationlarge sievenumber theory

0 comments

The pith

If a positive proportion of k-tuples have gcd at least D then the product of set sizes is bounded by roughly delta to the power minus k over k-1 times prod X_i over D to the k, for k at least 3.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper establishes upper bounds on the sizes of sets A_i inside intervals of length about X_i when a positive proportion delta of their k-tuples satisfy a large-gcd or small-lcm condition. For the gcd problem when k is at least 3 it combines a minimal-counterexample argument with a new high-dimensional measure concentration lemma to reach the stated bound involving delta to the power minus k over k-1 minus epsilon. For the lcm problem it uses a separate argument that already works for k at least 2 and produces a bound with L raised to a positive power over the product of the X_i to the power 1 over k-1. The paper shows both families of bounds are essentially best possible by exhibiting matching constructions up to the epsilon losses. A reader would care because these results limit how dense several sets of integers can be while their tuples still exhibit strong arithmetic correlations.

Core claim

For k greater than or equal to 3, whenever gcd of a1 through ak is at least D for at least proportion delta of the tuples in the product of the A_i, the product of the cardinalities |A_i| is much smaller than delta to the power minus k over k-1 minus epsilon times the product of the X_i divided by D to the k. An analogous inequality holds for the condition that lcm of the k numbers is at most L, valid already for all k at least 2, with the product of sizes bounded by delta to the minus k over k-1 times L to the power k over k-1 plus epsilon over the product of the X_i to the power 1 over k-1. Both statements are shown to be essentially optimal up to the epsilon terms in the exponents.

What carries the argument

A minimal-counterexample argument together with a new high-dimensional measure concentration lemma that controls how the large-gcd condition spreads over the product space of the sets A_i.

If this is right

The lcm bound holds for every k at least 2 and takes the form involving L raised to k over k-1 plus epsilon over the product of the X_i to the power 1 over k-1.
A large sieve type inequality supplies a complementary estimate for the gcd problem that does not rely on the concentration lemma.
Both families of bounds are essentially sharp because there exist constructions that achieve nearly the same exponents.
The results extend the one-dimensional case to arbitrary k while preserving the same main exponent k over k-1.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The concentration techniques might adapt to study other tuple-wise conditions such as the sum being divisible by a fixed integer or the numbers being pairwise coprime.
Numerical experiments for small k and moderate X_i could check whether the epsilon losses can be removed or are forced by the constructions.
These bounds may connect to questions in multi-dimensional sieve theory or discrepancy estimates for divisor functions.
Strengthening the concentration lemma could potentially eliminate the epsilon from the gcd exponent.

Load-bearing premise

The new high-dimensional measure concentration lemma holds with the stated constants and applies without hidden restrictions on the sets A_i.

What would settle it

Exhibit explicit sets A_i inside the given intervals for which the proportion of tuples with gcd at least D equals some delta yet the product of the set sizes exceeds the claimed bound by more than any fixed multiple of delta to a small positive power.

read the original abstract

We study extremal problems for tuples of integers chosen from sets $A_i \subset [X_i,2X_i]$ for $1\le i\le k$, under large GCD and small LCM conditions. For the GCD problem, we extend the work of Green and Walker to higher dimensions. Specifically, for $k\ge 3$, if $\gcd(a_1,\dots,a_k)\ge D$ for at least a proportion $\delta$ of the tuples in $\prod_{i=1}^k A_i$, then $$ \prod_{i=1}^k |A_i| \ll_{k,\varepsilon} \delta^{-k/(k-1)-\varepsilon} \frac{\prod_{i=1}^k X_i}{D^k}. $$ The proof is based on a minimal counterexample argument and a new high-dimensional measure concentration lemma. We also establish a large sieve-type inequality to obtain a complementary estimate for the GCD problem. For the LCM problem, we use a quite different method to show that, for all $k\ge 2$, $$ \prod_{i=1}^k |A_i| \ll_{k,\varepsilon} \delta^{-k/(k-1)} \frac{L^{k/(k-1)+\varepsilon}} {\bigl(\prod_{i=1}^k X_i\bigr)^{1/(k-1)}}, $$ whenever $\operatorname{lcm}(a_1,\dots,a_k)\le L$ for at least a proportion $\delta$ of the $k$-tuples in $\prod_{i=1}^k A_i$. Finally, we show that these bounds are essentially best possible up to $\varepsilon$-losses in the exponent.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Extends Green-Walker GCD results to k>=3 via a new concentration lemma and gives a separate LCM bound for k>=2, both with near-sharp examples.

read the letter

The paper's core advance is the higher-dimensional GCD statement for k at least 3: if a positive proportion delta of tuples from the product of the A_i have gcd at least D, then the product of the sizes is bounded by something like delta to the minus k over k-1 times the product of the X_i over D to the k, up to eps losses. The proof goes through a minimal-counterexample reduction plus a new high-dimensional measure concentration lemma. For the LCM side it switches to an entirely different argument that works already for k at least 2 and produces an analogous upper bound in terms of L. Both directions come with explicit constructions showing the exponents cannot be improved much without the eps room. A large-sieve inequality is added for a complementary GCD estimate. These pieces are not routine extensions; the concentration lemma and the LCM method are the fresh ingredients, and the sharpness examples close the loop on what the bounds can say. The citation pattern is clean, resting on Green-Walker as background rather than on self-referential fitting. The main soft spot is the applicability of the new lemma inside the minimal-counterexample step. The abstract claims the lemma holds with explicit constants and no extra restrictions on the A_i, but the reduction only invokes it after assuming a counterexample exists. If the lemma secretly needs some uniformity or density condition that those particular sets can violate, the contradiction does not go through. The stress-test note flags exactly this point, and without the full derivation it is the one place where the argument could still have a gap. Otherwise the claims look internally consistent and the methods are distinct enough to be worth checking. This is for people already working on arithmetic extremal problems or sieve-type inequalities in number theory. A reader who knows the Green-Walker paper will see the direct generalization and the new technical tool; someone outside the niche will not find immediate applications. It deserves a serious referee because the statements are precise, the optimality is addressed, and the only real uncertainty is the lemma's range of validity, which a referee can settle by reading the proof.

Referee Report

1 major / 2 minor

Summary. The paper extends extremal problems for GCDs and LCMs of k-tuples from sets A_i ⊂ [X_i, 2X_i] to higher dimensions. For k ≥ 3, if gcd(a1,…,ak) ≥ D for a proportion δ of tuples in ∏ A_i, then ∏ |A_i| ≪_{k,ε} δ^{-k/(k-1)-ε} (∏ X_i)/D^k. For k ≥ 2, if lcm(a1,…,ak) ≤ L for proportion δ, then ∏ |A_i| ≪_{k,ε} δ^{-k/(k-1)} L^{k/(k-1)+ε} / (∏ X_i)^{1/(k-1)}. Proofs use a minimal-counterexample argument plus a new high-dimensional measure-concentration lemma for the GCD case, a large-sieve inequality, and a separate method for LCM; both families of bounds are shown to be essentially sharp up to ε-losses.

Significance. If the central claims hold, the work supplies the first quantitative higher-dimensional extensions of Green–Walker-type results on GCD/LCM extremal problems, together with essentially sharp exponents and a new concentration lemma that may be of independent interest. The explicit sharpness constructions and the complementary large-sieve estimate are concrete strengths.

major comments (1)

[Proof of the main GCD bound (minimal-counterexample section)] The minimal-counterexample argument for the GCD theorem (k ≥ 3) invokes a new high-dimensional measure-concentration lemma whose stated hypotheses must be verified against the regularity properties of the putative minimal counterexample sets A_i. If the lemma requires, for example, uniform distribution modulo many primes or a density condition that the counterexample can violate, the reduction does not close. The abstract and proof sketch flag this lemma as the novel ingredient, yet no explicit verification of its applicability to the extremal sets is supplied.

minor comments (2)

[Large-sieve section] The large-sieve inequality is presented as a complementary estimate but its precise statement and range of applicability (e.g., dependence on the X_i) are not compared quantitatively with the main concentration bound.
[Introduction and statements of theorems] Notation for the product measures and the precise definition of “proportion δ” should be fixed uniformly across the GCD and LCM statements to avoid minor ambiguity.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and for identifying the need for explicit verification of the concentration lemma's hypotheses in the minimal-counterexample argument. We address the comment below and will revise the manuscript to strengthen the exposition.

read point-by-point responses

Referee: [Proof of the main GCD bound (minimal-counterexample section)] The minimal-counterexample argument for the GCD theorem (k ≥ 3) invokes a new high-dimensional measure-concentration lemma whose stated hypotheses must be verified against the regularity properties of the putative minimal counterexample sets A_i. If the lemma requires, for example, uniform distribution modulo many primes or a density condition that the counterexample can violate, the reduction does not close. The abstract and proof sketch flag this lemma as the novel ingredient, yet no explicit verification of its applicability to the extremal sets is supplied.

Authors: We agree that the verification should be made fully explicit to ensure the reduction is transparent. In the minimal-counterexample construction, the sets A_i are chosen to be maximal (in the sense of inclusion) among all collections violating the target inequality while maintaining the GCD proportion δ. This maximality directly implies the required regularity: if the elements of any A_i were concentrated in too few residue classes modulo a small prime p, one could delete a single residue class to produce strictly smaller sets that still violate the bound at the same δ, contradicting minimality. Consequently, the sets satisfy the density hypotheses of the concentration lemma (Lemma 3.2), including the uniform-distribution conditions modulo primes up to a suitable range depending on k and ε. We will insert a new paragraph immediately after the statement of the lemma that carries out this verification in full detail, confirming each hypothesis against the properties of the minimal counterexample. This closes the argument without altering the proof strategy. revision: yes

Circularity Check

0 steps flagged

No circularity; new lemma and independent methods support the claims.

full rationale

The derivation for the GCD bound (k>=3) proceeds via a minimal-counterexample argument that invokes a newly stated high-dimensional measure concentration lemma with explicit constants, plus a large sieve inequality. The LCM bound uses an entirely separate method. Both are shown sharp by explicit constructions. Green-Walker is cited only as background for the 2-dimensional case; no load-bearing step reduces to a self-citation, a fitted parameter renamed as prediction, or a self-definitional loop. The paper is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The results rely on standard properties of gcd and lcm together with a newly introduced concentration lemma; no free parameters or invented entities are introduced.

axioms (2)

standard math Standard arithmetic properties of gcd and lcm, including multiplicativity and divisibility relations
Invoked in the definitions of the conditions and in the construction of sharpness examples.
ad hoc to paper Existence and applicability of a high-dimensional measure concentration lemma
New lemma introduced specifically for the gcd proof; its statement and proof are not supplied in the abstract.

pith-pipeline@v0.9.0 · 5613 in / 1416 out tokens · 45276 ms · 2026-05-09T22:52:53.806701+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

2 extracted references · 2 canonical work pages

[1]

Green and A

B. Green and A. Walker, Extremal problems for GCDs.Combin. Probab. Comput.30(2021), no. 6, 922–929

work page 2021
[2]

Koukoulopoulos and J

D. Koukoulopoulos and J. Maynard, On the Duffin-Schaeffer conjecture.Ann. of Math. (2)192(2020), no. 1, 251–307. School of Mathematics, Shandong University, Jinan 250100, China D´epartement de math ´ematiques et de statistique, Universit ´e de Montr ´eal, C.P. 6128, succ. Centre-ville, Montr´eal, QC H3C 3J7, Canada Email address:haozhegou@gmail.com

work page 2020

[1] [1]

Green and A

B. Green and A. Walker, Extremal problems for GCDs.Combin. Probab. Comput.30(2021), no. 6, 922–929

work page 2021

[2] [2]

Koukoulopoulos and J

D. Koukoulopoulos and J. Maynard, On the Duffin-Schaeffer conjecture.Ann. of Math. (2)192(2020), no. 1, 251–307. School of Mathematics, Shandong University, Jinan 250100, China D´epartement de math ´ematiques et de statistique, Universit ´e de Montr ´eal, C.P. 6128, succ. Centre-ville, Montr´eal, QC H3C 3J7, Canada Email address:haozhegou@gmail.com

work page 2020