Erd\H{o}s's integer dilation approximation problem and GCD graphs

Dimitris Koukoulopoulos; Jared Duker Lichtman; Youness Lamzouri

REVIEW 1 major objections 4 minor 24 references

Erd\H{o}s's integer dilation approximation problem and GCD graphs

T0 review · 1 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Positive reciprocal density guarantees an integer dilation pair

desk verdict This paper resolves Erdős's 1948 dilation problem under logarithmic density condition (1.3) with a convincing proof, though a few key lemmas are inherited from an unpublished preprint via 'minimal changes' assertions. read the letter →

arxiv 2502.09539 v1 pith:5OCKMXOW submitted 2025-02-13 math.NT math.COmath.DS

Dimitris Koukoulopoulos , Youness Lamzouri , Jared Duker Lichtman This is my paper · ORCID

classification math.NTmath.COmath.DS MSC 11J2511B8311A0505C40

keywords integerdilationapproximationGCDgraphsprimitivesetsDiophantinesecondmomentmethodlogarithmicdensityroughnumbersstructureversusrandomness

topics The Collatz Conjecture

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

A discrete set of positive real numbers with positive reciprocal logarithmic density must contain two distinct elements α and β for which some positive integer n makes |nα−β|<ε, for every ε>0. The paper proves this 1948 Diophantine approximation problem under condition (1.3), and the proof actually yields infinitely many such pairs. The significance is that a purely measure-theoretic divergence condition forces a number-theoretic approximation phenomenon, even when the set is discrete and has no accumulation points. The argument combines a second moment method over intervals with a structural dichotomy: sets that avoid close integer dilations must either be mostly random, where averaging works, or contain a large primitive-like structured part, where a refinement of a classical primitive-set estimate supplies the needed saving.

What carries the argument

The load-bearing mechanism is the GCD-graph machine, imported from work on a related Diophantine approximation problem and adapted to rational vertices. Alongside it, the proof introduces the bracket [α,β]=H(α/β)/max{α,β}, which measures the height of a rational ratio, and replaces the intervals Mα by thinner events Nα whose multipliers n are α-rough, meaning all prime factors exceed α. These choices make disjointness and negative correlation easy: when [α,β]≤1 the events Nα and Nβ do not overlap at all, and when [α,β] is large the correlation is bounded by sieving estimates. The remaining small-bracket pairs are shown, via maximal GCD subgraphs and a quality function q(G), to concentrate in a structured subgraph, to which a refined primitive-set estimate (Theorem 4.1) is applied. That refinement, itself a generalization of a classical primitive-set result, supplies exactly the savings needed to balance the extra summation over possible fixed divisors, a feature the paper singles out as new.

What would settle it

Verify Proposition 2.15 numerically on finite, 1-spaced sets B of rational numbers with controlled heights and bracket sizes: compute λ of the pairs with H(α/β)≤$x^{3}$, y<[α,β]≤2y, and L(α/β;z)>1, and check whether the bound λ({(α,β)∈B×B:...}) ≪ y $e^{{-z}}$ (log x)^2 holds for all admissible x,y,z. A single counterexample would directly refute the key reduction and hence Theorem 1.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is Theorem 1: for any discrete A⊂R>0 with limsup_{x→∞} (1/log x) ∑_{α∈A∩[1,x]} 1/α > 0 and any ε>0, there exist distinct α,β∈A and n∈N with |nα−β|<ε. Iterating the theorem after deleting each found pair gives infinitely many such pairs. The proof proceeds by contradiction, assuming that |nα−β|≥1 for all distinct α,β and all n∈N. From that assumption the paper derives lim_{T→∞} (1/T)∑_{α∈A∩[1,T]}1 = 0, which contradicts the divergence of the reciprocal sums. This density-zero conclusion is exactly what resolves the problem; no quantitative rate such as (1.6) is obtained, and the authors explicitly describe the proof as soft.

Load-bearing premise

The proof rests on a battery of GCD-graph lemmas taken from an unpublished companion preprint, applied to rational vertices with a modified quality function, with the paper asserting that the adaptations require only minimal changes; if any of those adaptations is not actually valid, the central claim is unsupported.

Editorial extensions

If this is right

Every set A satisfying condition (1.3) contains infinitely many distinct pairs (α,β) with |nα−β|<ε for each ε>0, obtained by repeatedly deleting already-found pairs.
The 1948 problem is settled in its contrapositive form under the logarithmic divergence condition: no discrete set with positive reciprocal logarithmic density is free of close integer dilations.
The random-versus-structured dichotomy becomes a usable proof architecture: either the second moment over α-rough events succeeds directly, or a large structured subset supports a Behrend-type saving.
The proof is deliberately non-quantitative; it shows the counting function is o(log x) without a rate, and the paper states that quantitative estimates like (1.6) are not proved.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Because the final saving is exactly balanced by the extra summation over fixed divisors, a quantitative analogue with a rate would likely require a new mechanism to break that balance; the paper only obtains the qualitative o(log x) conclusion.
The same GCD-graph dichotomy may be adaptable to prove stronger distribution statements about the ratios of elements of A, for example that the ratios cannot all stay away from the integers in a weighted second-moment sense.
The square-free-numerator case singled out in the paper is a natural intermediate target: with square-free numerators the added denominator-only iteration could yield the stronger estimate (1.5), and testing that case would isolate how much of the full theorem depends on the delicate final balancing step.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The short version: this is a genuine resolution of a sixty-plus-year-old problem, and the main body of the proof is in good shape. The theorem — positive logarithmic density forces some |nα − β| < ε for distinct α, β in the set — is new; Haight only handled the all-irrational-ratio case. The high-level strategy is clear: restrict to rough multiples, use the second moment method, show irrational ratios are uncorrelated, then use GCD graphs to control rational-ratio correlations. The two genuinely new moves are the adaptation of the GCD-graph machinery to rational vertices (tracking numerator and denominator GCDs together) and the use of a generalized Behrend estimate to balance the extra summation over the possible fixed divisors A and B. That balance is the kind of thing you either see or you don't, and here it is spelled out.

What the paper does well: the reduction to Proposition 2.15 is explicit and the intermediate lemmas (correlation estimates, the construction of the sets A′_j, the generalized Behrend theorem, the deduction of the rational-set Proposition 6.2) are proved carefully in the text. The writing is unusually honest about the structure of the argument, including the limitation that the final sections do not yield the stronger quantitative estimate (1.6).

The soft spot is exactly what the stress test flags: Propositions 7.11–7.14, which carry the weight in Section 8, are proved using Lemmas 9.2, 9.4, 9.5, 9.6 and 11.1, and for all of those the paper says 'the argument of [22] goes through with minimal changes' (or words to that effect). The changes are real — rational vertices, negative p-adic valuations, a modified quality function — and the paper does not include the transfer proofs. Since [22] is a preprint (even if by largely overlapping authors), a referee cannot fully verify those assertions without doing substantial work. I did not find a concrete error in the written portions, and the dependence is flagged rather than hidden, but it is still a load-bearing reliance on an unpublished source. If any of those adaptations is wrong, the E_3 bound fails and with it Theorem 1. That said, the surrounding arguments in Sections 2–6 and 8 are coherent, and the machinery from [21] is established enough that the 'minimal changes' claim is plausible.

Who this is for: people working in Diophantine approximation, primitive sets, and GCD-graph methods. The paper deserves a serious referee — it is important, new, and largely self-contained except for the [22] dependence. My recommendation: send it to a strong number theory journal, and instruct the referee to put real effort into checking Section 9–11 against [22], or ask the authors to supply a fuller appendix. The dependence is unpublishable in its current form only if the referee finds a concrete break; otherwise it should be accepted with a request for additional verification of those transfers.

Referee Report

1 major / 4 minor

Summary. The paper proves Erdős's 1948 integer dilation approximation problem under the logarithmic-density condition (1.3): if A ⊂ R>0 is discrete with limsup_{x→∞} (1/log x) Σ_{α∈A∩[1,x]} 1/α > 0, then for every ε>0 there are infinitely many distinct α,β∈A and a positive integer n with |nα−β|<ε. The proof uses a second-moment method over the rough-number events N_α, analyzes their correlations through a new bracket [α,β], and reduces the hard correlation case to a bound on weighted bipartite GCD graphs whose vertices are rational numbers. The key estimate is Proposition 2.15, which is reduced to Proposition 6.2 and then to a series of GCD graph propositions (7.11–7.14). The paper is well organized and contains a self-contained proof of a refinement of Behrend's theorem (Theorem 4.1) and a substantial portion of the GCD graph arguments, but the proof of the central propositions relies on adaptations from the unpublished preprint [22] that are stated but not carried out.

Significance. If correct, this is a major advance: it resolves a problem Erdős posed in 1948 under condition (1.3) and introduces a novel combination of the GCD graph machinery with rational vertices, negative p-adic valuations, and a Behrend-type sieve. The paper gives a clear structure-versus-randomness heuristic, explicit reductions, and no evident circularity. The constants θ=2.001 and M=e^4 are chosen to make the iterative argument work and appear to be legitimate. However, the proof's load-bearing part—the GCD graph propositions—is not self-contained: Propositions 7.11–7.14 depend on Lemmas 9.2, 9.4, 9.5, 9.6, and 11.1, which are asserted to follow from [22] with 'minimal changes.' This is a genuine verification gap that should be addressed before the paper can be accepted as a complete proof.

major comments (1)

[Sections 9-11] The proof of Proposition 6.2, and hence of Theorem 1, relies on Propositions 7.11–7.14, whose proofs are not given. Instead, Sections 9–11 state that certain lemmas are direct adaptations of results in the unpublished preprint [22], with only 'minimal changes' (e.g., §9.1, §9.2, and the context of Lemma 11.1 in Section 11). These lemmas are load-bearing: Lemma 9.4 is used in Proposition 7.12, Lemma 9.6 in Proposition 7.11, Lemmas 9.2/9.3 in Proposition 7.13, and Lemma 11.1 in Proposition 7.14. Because the changes involve rational vertices, negative p-adic valuations, and a modified quality function without the Euler factors of [22], the correctness of these adaptations is not verifiable from the text. The manuscript should either provide complete proofs of the adapted lemmas, or a precise line-by-line correspondence with [22] displaying all modifications and verifying them. Without this, the central estimate (2.23) is not fully established.

minor comments (4)

[Section 3.2] The notation '3ω' in the definition of η (and in the proof) should be '3^{ω}'; the proof clearly uses the exponential form 3^{ω(...)} in bounding S. If the printed version indeed uses 3ω, it is a typo that makes the estimate dimensionally wrong.
[Section 2.2] The terminology 'negatively correlated' is formally incorrect, as the condition is asymptotic non-positive correlation; the authors acknowledge this in the footnote, but the main text would benefit from a brief remark or a slightly different name.
[References] Reference [22] is cited as 'Duke Math. J., to appear' but the proof depends essentially on it; the reference should be updated to the published version, or its availability should be confirmed, to allow readers to verify the minimal changes.
[Section 2.5] The sentence 'the remaining pairs are very few' is vague; it would be clearer to state explicitly that they are handled by Proposition 2.15, whose statement follows.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the derivation is a self-contained mathematical proof modulo the cited GCD-graph machinery; the [22] dependency is a verification risk, not a circular step.

full rationale

Walking the derivation chain: Theorem 1 is reduced to a second-moment claim (2.14) via the contradiction assumption (2.2) and the density argument in Section 2.1; the correlation estimates for the sets N_alpha are proved in Section 3 (Lemmas 3.1, 2.9, 2.12) using elementary sieving, with no appeal to the target theorem. The key estimate Proposition 2.15 is reduced to Proposition 6.2 in Section 6 through a fully written-out maximal-subgraph argument (Lemmas 5.9-5.12). Proposition 6.2 is then proved in Section 8 from Propositions 7.11-7.14. These propositions concern abstract GCD graphs; their statements involve only the graph data and quality function, not the set A of the theorem or condition (1.3). The paper's proofs of Propositions 7.11-7.14 rely on lemmas quoted from the authors' preprint [22] with phrases such as 'the argument of [22] goes through with minimal changes' (Sections 9.1, 9.2, 10, 11). This is a genuine verification dependency on an unpublished paper by overlapping authors, but it is not circularity: [22] is a parameter-free result about GCD graphs whose assumptions do not include the Erdos dilation problem, so it is independent support in the sense of the review rules. The constants theta=2.001 and M=e^4 are chosen from open ranges and are not fitted to any data or to force the conclusion. I found no step in which an output equals an input by definition or in which a fitted parameter is renamed as a prediction. The self-citation chain therefore lowers confidence in correctness but does not make the derivation circular.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The proof introduces mathematical constructions (brackets [α,β], sets N_α, GCD graphs with rational vertices) but no physical or metaphysical entities. The only non-standard external input is the adaptation of results from the preprint [22]. The hand-picked constants θ and M are arbitrary but fixed, not fitted.

free parameters (2)

θ (theta) = 2.001
Chosen in (2, 2.01), with τ = θ−2 = 0.001, to make the GCD graph power arguments and quality comparisons work. Arbitrary fixed value, not fitted to data.
M = e^4
Chosen arbitrarily ≥ 2 as the quality-loss multiplier in the GCD graph iteration (Section 7.2). It controls the trade-off between quality loss and removal of primes; not fitted.

assumptions (5)

domain assumption Behrend's estimate: for any primitive set A ⊂ N, sum_{a∈A∩[1,x]} 1/a ≪ log x / sqrt(log log x)
Used to prove the generalized Theorem 4.1, which provides the savings needed for Proposition 2.15. This is a published classical result.
ad hoc to paper The results of Koukoulopoulos, Maynard, Yang (arXiv:2404.14628), specifically Lemmas 9.2, 9.4, 9.5 as adapted in Sections 9-11
The paper states these adapt with 'minimal changes' to rational vertices and the modified quality function. This is the load-bearing external input and the weakest assumption.
standard math Fundamental lemma of sieve and Mertens' theorem
Used throughout Sections 3 and 4 to estimate counts of rough numbers and multiplicative sums.
standard math Second moment method (Cauchy-Schwarz) as in Lemma 2.1
Used to show the union of the sets N_α covers a proportion close to 1 of [0,T].
standard math Sperner's theorem on antichains
Used in the proof of Theorem 4.1 to bound the number of divisors from a primitive set.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Erd\H{o}s's integer dilation approximation problem and GCD graphs." pith.science (2026). https://pith.science/paper/5OCKMXOW

@misc{pith2026250209539,
  author       = {Pith},
  title        = {Pith review of: Erd\Hos's integer dilation approximation problem and GCD graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5OCKMXOW}},
  note         = {Machine review of arXiv:2502.09539}
}

abstract

Let $\mathcal{A}\subset\mathbb{R}_{\geqslant1}$ be a countable set such that $\limsup_{x\to\infty}\frac{1}{\log x}\sum_{\alpha\in\mathcal{A}\cap[1,x]}\frac{1}{\alpha}>0$. We prove that, for every $\varepsilon>0$, there exist infinitely many pairs $(\alpha, \beta)\in \mathcal{A}^2$ such that $\alpha\neq \beta$ and $|n\alpha-\beta| <\varepsilon$ for some positive integer $n$. This resolves a problem of Erd\H{o}s from 1948. A critical role in the proof is played by the machinery of GCD graphs, which were introduced by the first author and by James Maynard in their work on the Duffin--Schaeffer conjecture in Diophantine approximation.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

[22]

Koukoulopoulos, J

D. Koukoulopoulos, J. Maynard and D. Y ang, An almost sharp quantitative version of the Dufﬁn-Schaeffe r conjecture. Duke Math. J., to appear. Preprint available (arXiv:2404.1 4628)

work page
[21]

Koukoulopoulos and J

D. Koukoulopoulos and J. Maynard, On the Dufﬁn-Schaeffer conjecture. Ann. of Math. (2) 192 (2020), no. 1, 251–307

work page 2020
[1]

Ahlswede, L

R. Ahlswede, L. Khachatrian, A. S´ ark¨ ozy,On the density of primitive sets . J. Number Theory, (2004), 319–361

work page 2004
[2]

Behrend, On sequences of numbers not divisible by another

F. Behrend, On sequences of numbers not divisible by another . J. Lond. Math. Soc. (1935), 42–45

work page 1935
[3]

A. S. Besicovitch, On the density of certain sequences of integers , Math. Ann. 110 (1934), 336–341

work page 1934
[4]

Erd˝ os,Note on sequences of integers no one of which is divisible by a ny other

P . Erd˝ os,Note on sequences of integers no one of which is divisible by a ny other. J. London Math. Soc. (1935), 126–128

work page 1935
[5]

, On the density of some sequences of integers. Bull. Amer. Math. Soc. 54 (1948), 685–692

work page 1948
[6]

Magyar Tud

, Some unsolved problems. Magyar Tud. Akad. Mat. Kutat´ o Int. K¨ ozl. (1961), 221–254

work page 1961

Show all 24 references

[7]

, Quelques probl`emes de th ´eorie des nombres , Monographies de l’Enseignement Math´ ematique, No. 6 , pp. 81–135, L’Enseignement Math´ ematique, Universit´ e, Geneva, 1963. 7G+ is a denominator-exact subgraph of G because if (a/q, b/r ) ∈ V + × W + with gcd(a, q ) = gcd( b, ...

1963
[8]

A survey of combinatorial theory (Proc

, Problems and results on combinatorial number theory. A survey of combinatorial theory (Proc. Inter- nat. Sympos., Colorado State Univ., Fort Collins, Colo., 19 71), pp. 117–138. North-Holland Publishing Co., Amsterdam-London, 1973

1973
[9]

Lecture Notes in Math., 475 , pp

, Problems and results on Diophantine approximations, II. Lecture Notes in Math., 475 , pp. 89–99, Springer, Berlin, 1975

1975
[10]

, Probl`emes extr ´emaux et combinatoires en th ´eorie des nombres , S´ eminaire Delange-Pisot-Poitou (17e ann´ ee: 1975/76), Th´ eorie des nombres, Fasc. 2, Exp. No. 67, 5 pp., Secr´ etariat Math´ ematique, Paris, 1977

1975
[11]

Discrete Mathematics 6 (1980), 89–115

, A survey of problems in combinatorial number theory, Combin atorial mathematics, optimal designs and their applications Ann. Discrete Mathematics 6 (1980), 89–115

1980
[12]

Hardy-Ramanujan J

, Some of my forgotten problems in number theory. Hardy-Ramanujan J. 15 (1992), 34–50

1992
[13]

The mathematics of Paul Erd˝ os, I, 47–67

, Some of my favorite problems and results. The mathematics of Paul Erd˝ os, I, 47–67. Algorithms Com- bin., 13, Springer-V erlag, Berlin, 1997

1997
[14]

Erd˝ os and A

P . Erd˝ os and A. S´ ark¨ ozy,Some solved and unsolved problems in combinatorial number t heory. Math. Slovaca 28 (1978) no. 4, 407–421

1978
[15]

Erd˝ os, A

P . Erd˝ os, A. S´ ark¨ ozi and E. Szemer´ edi,On divisibility properties of sequences of integers . Colloq. Math. Soc. J´ anos Bolyai, 2 North-Holland Publishing Co., Amsterdam-London, 1968, pp. 35–49

1968
[16]

Green and A

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

2021
[17]

A. J. Haight, On multiples of certain real sequences. Acta Arith. 49 (1988), no. 3, 303–306

1988
[18]

Harman, Metric number theory

G. Harman, Metric number theory. London Math. Soc. Monogr. (N.S.), 18 The Clarendon Press, Ox ford Univer- sity Press, New Y ork, 1998, xviii+297 pp

1998
[19]

Hauke, S

M. Hauke, S. V azquez Saez and A. Walker, Proving the Dufﬁn-Schaeffer conjecture without GCD graphs . Preprint (2024), 27 pages, arXiv:2404.15123

2024 arXiv
[20]

Koukoulopoulos, The distribution of prime numbers

D. Koukoulopoulos, The distribution of prime numbers. Graduate Studies in Mathematics, 203. American Math- ematical Society, Providence, RI, 2019

2019
[23]

A. D. Pollington and R. C. V aughan, R. C., The k-dimensional Dufﬁn and Schaeffer conjecture. Mathematika 37 (1990), no. 2, 190–200

1990
[24]

Sperner, Ein Satz ¨uber Untermengen einer endlichen Menge , Math

E. Sperner, Ein Satz ¨uber Untermengen einer endlichen Menge , Math. Z. 27 (1928) 544–548. D ´EPARTEMENT DE MATH ´EMATIQUES ET DE STATISTIQUE , U NIVERSIT ´E DE MONTR ´EAL , CP 6128 SUCC . CENTRE -V ILLE , M ONTR ´EAL , QC H3C 3J7, C ANADA Email address: dimitris.koukoulopoulo...

1928

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [22]

Koukoulopoulos, J

D. Koukoulopoulos, J. Maynard and D. Y ang, An almost sharp quantitative version of the Dufﬁn-Schaeffe r conjecture. Duke Math. J., to appear. Preprint available (arXiv:2404.1 4628)

work page

[2] [21]

Koukoulopoulos and J

D. Koukoulopoulos and J. Maynard, On the Dufﬁn-Schaeffer conjecture. Ann. of Math. (2) 192 (2020), no. 1, 251–307

work page 2020

[3] [1]

Ahlswede, L

R. Ahlswede, L. Khachatrian, A. S´ ark¨ ozy,On the density of primitive sets . J. Number Theory, (2004), 319–361

work page 2004

[4] [2]

Behrend, On sequences of numbers not divisible by another

F. Behrend, On sequences of numbers not divisible by another . J. Lond. Math. Soc. (1935), 42–45

work page 1935

[5] [3]

A. S. Besicovitch, On the density of certain sequences of integers , Math. Ann. 110 (1934), 336–341

work page 1934

[6] [4]

Erd˝ os,Note on sequences of integers no one of which is divisible by a ny other

P . Erd˝ os,Note on sequences of integers no one of which is divisible by a ny other. J. London Math. Soc. (1935), 126–128

work page 1935

[7] [5]

, On the density of some sequences of integers. Bull. Amer. Math. Soc. 54 (1948), 685–692

work page 1948

[8] [6]

Magyar Tud

, Some unsolved problems. Magyar Tud. Akad. Mat. Kutat´ o Int. K¨ ozl. (1961), 221–254

work page 1961