Pith. sign in

REVIEW 1 major objections 3 minor 16 references

Improved Bounds for Distinct Multiples in Intervals

T0 review · 1 major / 3 minor · reviewed 2026-08-01 · deepseek-v4-flash

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

Pith's one-line read The paper proves that the shortest interval guaranteed to contain distinct multiples of every integer up to n grows faster than n log n, falsifying a conjecture that n log n would suffice.

desk verdict Genuine improvements on a niche problem; the two flagged gaps are real but repairable, so the paper should go to referees. read the letter →

arxiv 2607.26450 v1 pith:VBVCKEZT submitted 2026-07-29 math.NT math.CO

Kaizhe Chen This is my paper · ORCID
classification math.NTmath.CO MSC 11N0511P70
keywords distinctmultiplesintervalsmatchingarithmeticKakeyalowerboundupperprimedistributionadditivecombinatorics
topics The Twin Prime 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

Two interval-length functions are studied: F(n), the smallest length such that every interval of that length contains, for each integer 1 through n, a distinct multiple of that integer, and h_P(n), the analogous quantity when only primes at most n are required. The main advance is a lower bound h_P(n) ≥ n exp((1/50) log n / log log n) for all large n, which transfers to F(n) because F(n) ≥ h_P(n). This growth is faster than n log n, so a conjecture that F(n) is at most n log n is refuted. The paper also obtains improved upper bounds, F(n) ≤ n^{β+o(1)} with β ≈ 1.4031 and h_P(n) ≪ n^{7/5}/(log n)^{2/5}, improving the 1980 bounds.

What carries the argument

The lower bound's engine is the digit-product arithmetic-Kakeya set: a set of integers that contains, for every d up to W^t, a k-term arithmetic progression with common difference d, yet stays sparse (size ≤ W^{t(1−ε)}). This smallness, combined with the classical matching criterion for bipartite graphs and a Chinese-remainder shift, produces an interval whose prime-multiple offsets fit inside fewer offsets than there are primes, blocking any distinct multiple assignment. The upper bounds rely on a projection inequality for finite subsets of Z² and on a lemma counting C6 cycles in a C4-free bipartite graph.

What would settle it

Inspect Lemma 4.1 numerically: compute W, ε, and the ratio |S|/W for the specified construction, and check whether |S|^t ≤ W^{t(1−ε)} for t=2 or t=3. A direct computation showing the digit-product set exceeds W^{t(1−ε)} would falsify the lower-bound proof; confirming the stronger bound k^{-11}W would support it.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is a quantitative lower bound: for sufficiently large n, h_P(n) ≥ n exp((1/50) log n / log log n), and therefore the same inequality holds for F(n). The proof constructs, for a carefully chosen product W of small odd primes, a digit-product set A_t that contains a k-term arithmetic progression of every difference d < W^t (a (k,W^t) arithmetic-Kakeya set) while having size at most W^{t(1−ε)}. Embedding the primes in a CRT-chosen interval then makes the neighborhood of the prime set too small for a matching, so the interval must be long. A separate argument, based on a projection estimate for finite lattice sets, yields F(n) ≤ n^{1.4031+o(1)}; an

Load-bearing premise

The load-bearing premise is the quantitative size bound on the digit-product set in Lemma 4.1. The proof derives it from |S|≤k^{-10}W, but the stated constants do not by themselves force |A_t|≤W^{t(1−ε)}; if that size bound were false the lower bound would collapse, although the surrounding estimates appear to provide the stronger |S|≤k^{-11}W needed.

Editorial extensions

If this is right

  • The lower bound F(n) ≥ n exp((1/50) log n / log log n) disproves the conjecture that F(n) ≪ n log n.
  • Because F(n) ≥ h_P(n), the same superlinear lower bound applies to all-integer distinct multiples, not just primes.
  • The upper bound F(n) ≤ n^{1.4031+o(1)} improves the long-standing n^{3/2} bound.
  • The upper bound h_P(n) ≪ n^{7/5}/(log n)^{2/5} improves the previous n^{3/2}/√(log n) bound for the prime-only problem.
  • The older conjecture that F(n) = n^{1+o(1)} remains open, but the new bounds narrow the possible range to between n exp((1/50)log n/log log n) and n^{1.4031+o(1)}.

Reading between the lines

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

  • The size-bound step in Lemma 4.1 appears to require a slightly stronger estimate than the stated |S|≤k^{-10}W; the surrounding estimates seem to supply |S|≤k^{-11}W, which would close the gap, so the theorem likely survives a careful rewriting.
  • The same CRT-plus-sparse-set template might extend to other sets of moduli — for example, integers with at most two prime factors — wherever the corresponding arithmetic-Kakeya set can be made sparse.
  • The upper-bound method for h_P(n) uses only a codegree-at-most-one structure and a lower bound on C6 cycles, so it may generalize to other 'few-overlap' families of arithmetic progressions.
  • Numerical tests of Lemma 4.1 for moderate k would indicate whether the stated quantitative smallness is present or whether the proof needs the stronger estimate.
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.

Referee Report

1 major / 3 minor

Summary. The paper studies two functions introduced by Erdős and Pomerance: F(n), the minimal interval length guaranteeing a distinct-multiple matching for all integers up to n, and h_P(n), the analogous quantity for primes up to n. Three theorems are proved. Theorem 1.1 gives F(n) ≤ n^{β+o(1)} with β ≈ 1.4031, using the Katz–Tao sum-difference theorem. Theorem 1.2 gives h_P(n) ≥ n exp((1/50) log n / log log n) for large n, based on a square-residue digit construction of Green–Ruzsa; since F(n) ≥ h_P(n), this also gives the same lower bound for F(n) and disproves Kominers's conjecture F(n) ≪ n log n. Theorem 1.4 gives h_P(n) ≪ n^{7/5}/(log n)^{2/5} by a combinatorial argument with a C4-free graph. The proofs are largely self-contained and import only standard external results: Hall's theorem, Katz–Tao, PNT/Mertens, CRT, and spectral graph inequalities.

Significance. If the technical gap discussed below is repaired, the lower bound is a substantial qualitative improvement over Ruzsa's h_P(n)/n → ∞ and over the polynomial-type lower bounds of van Doorn and Kominers; in particular, it settles Kominers's conjecture in the negative. The upper bounds improve the classical 1980 results of Erdős and Pomerance and combine disparate tools in a convincing way. The paper is constructive: constants and heights are tracked in the key arithmetic-Kakeya construction, which makes the argument checkable. There is no circular dependence on the target results, and the infrastructure from [6, 11] is used as an external input rather than as an unproved ad hoc assumption.

major comments (1)
  1. [§4, Lemma 4.1] The proof contains a load-bearing step that is not justified as written. The displayed chain |A_t| ≤ |S|^t ≤ (k^{-10}W)^t ≤ W^{t(1-ε)} requires k^{-10} ≤ W^{-ε}. Together with log W = (20+o(1)) log k log log k and ε = (1/2+o(1))/log log k, this gives W^{-ε} = k^{-(10+o(1))}; the inequality k^{-10} ≤ k^{-(10+o(1))} depends on the sign of the o(1), which is not controlled. If the o(1) is positive, the inequality fails. However, the preceding estimate, namely |S| ≤ k^2 W / 2^r ∏(1+1/q_i) with r = ⌈20 log k⌉, actually yields the stronger bound |S| ≤ k^{-11}W for all sufficiently large k. Replacing k^{-10} by k^{-11} makes the chain valid, since k^{-11} ≤ k^{-(10+o(1))} eventually. This repair is necessary because Theorem 1.2 rests on this size estimate of A_t.
minor comments (3)
  1. [§5, Lemma 5.1] In the 'Combining' display after (14)–(18), the term 3 tr(RC^2) is bounded by 3·2|X|^{3/2}ℓ^2 = 6|X|^{3/2}ℓ^2, so the lower bound for T_B should subtract |X|^{3/2}ℓ^2, not (1/3)|X|^{3/2}ℓ^2. The final conclusion is unaffected because this term is of lower order than |X|^2ℓ when ℓ ≫ |X|^{2/5}, so it can be absorbed by taking C_0 large, but the displayed inequality should be corrected.
  2. [§5, Lemma 5.2] The branching thresholds are inconsistent: the first case covers L ≤ 20C_0|P|^{2/5}, and the second case then should assume L > 20C_0|P|^{2/5}, not merely L ≥ 10C_0|P|^{2/5}. This is only a clarity issue.
  3. [§4, proof of Theorem 1.2] The CRT gives an integer m; since h_P(n) is defined for intervals of positive integers, the proof should explicitly say that m is chosen in the positive residue class modulo ∏_{p∈P} p. This does not affect the argument.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: all load-bearing inputs are external theorems (Katz–Tao, PNT, Hall, CRT, Mertens) or lemmas proved in the paper; no fitted parameter is relabeled as a prediction and no self-citation is load-bearing.

full rationale

The derivation chain is self-contained with respect to the claimed results. Theorem 1.1 derives an upper bound on F(n) from Hall's theorem and the Katz–Tao sum-difference theorem (Theorem 2.2), both cited external results; the proof constructs a matching from the projected-set estimate and does not assume the conclusion. Theorem 1.2 derives the h_P(n) lower bound from Lemma 4.1, whose construction is explicitly imported from Green and Ruzsa's square-residue digit construction but is re-proved in the paper with quantitative tracking, and from Lemma 4.2, which is a prime-number-theorem pigeonhole argument. The parameter k is chosen freely, not fitted to any value of h_P(n), and the lower bound follows by exhibiting an interval whose divisibility graph fails Hall's condition. Theorem 1.4 is proved by new combinatorial lemmas (5.1, 5.2) built from scratch. There are no non-trivial self-citations by the author; the cited prior works are independent external theorems. The one flagged issue (the displayed |S| ≤ k^{-10} W estimate in Lemma 4.1 may require the stronger k^{-11} W bound for the exponent comparison) is a potential correctness gap, not a circularity: it concerns the truth of an auxiliary size bound, not the use of the target result as an input. No definition reduces to the target, no fitted quantity is renamed a prediction, and no uniqueness claim is imported from the author's own prior work. Hence the paper's score is 0.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

No fitted values or new entities; the only input parameters are explicit constants in the theorem statements. The main external dependencies are the Katz–Tao theorem and standard number-theoretic results. One elementary matching fact for small primes is unstated.

assumptions (7)
  • standard math Hall's marriage theorem: a bipartite graph has a perfect matching iff |Γ(S)|≥|S| for every S⊆L.
    Used throughout (Theorem 2.1) to convert matching existence to neighborhood-size inequalities; invoked in proofs of Theorems 1.1, 1.2, 1.4.
  • domain assumption Katz–Tao sum–difference theorem (Theorem 2.2): for α the root of α^3−4α+2=0, any finite G with π_{−1} injective satisfies |G|≤C_η (max_{r∈R_η}|π_r(G)|)^{α+η}.
    Imported deep external result; it is the engine behind Theorem 1.1. The paper does not prove it.
  • standard math Prime number theorem: π(x)∼x/log x and ϑ(x)∼x.
    Used in Lemma 4.1 to compute log W and in Lemma 4.2 for prime counts in dyadic blocks.
  • standard math Mertens' bound: ∏_{p≤x}(1−1/p)^{−1}≪log x.
    Used in Lemma 4.1 to control ∏(1+1/q_i).
  • standard math Chinese remainder theorem for pairwise coprime moduli.
    Used in Lemma 2.5 and in the construction of m in §4 and in Lemma 4.1.
  • domain assumption Any interval of length at least the sum of a finite set of moduli admits a distinct-multiple matching for those moduli (by allocating disjoint subintervals of length p to each modulus).
    Used implicitly in Theorem 1.4 for the small-prime block H_c; the assertion 'by definition of H_c' assumes this elementary fact without proof.
  • standard math Singular value variational principle (standard linear algebra) used in Lemma 2.7.
    Used to lower-bound tr((BB^T)^3) in Lemma 5.1. The paper proves the lemma, but it depends on standard facts.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Improved Bounds for Distinct Multiples in Intervals." pith.science (2026). https://pith.science/paper/VBVCKEZT

@misc{pith2026260726450,
  author       = {Pith},
  title        = {Pith review of: Improved Bounds for Distinct Multiples in Intervals},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VBVCKEZT}},
  note         = {Machine review of arXiv:2607.26450}
}
abstract

In this note, we study two functions introduced by Erd\H{o}s and Pomerance. For any positive integer $n$, let $F(n)$ be the smallest integer $F>0$ such that any $F$ consecutive integers contain a distinct multiple for each positive integer at most $n$, and let $h_{\mathbb{P}}(n)$ be the smallest integer $H>0$ such that any $H$ consecutive integers contain a distinct multiple for each prime at most $n$. Based on the square-residue digit construction of Green and Ruzsa, we prove \[ F(n)\ge h_{\mathbb P}(n)\ge n\exp\!\left(\frac{1}{50}\frac{\log n}{\log\log n}\right), \] for sufficiently large $n$. This improves the previous bounds $h_{\mathbb P}(n)/n\to\infty$ by Ruzsa, $F(n)\gg n\log n/\log \log n$ by van Doorn, and $F(n)\gg n\log n$ by Kominers and, in particular, disproves the conjecture $F(n)\ll n\log n$ by Kominers. Moreover, we prove \[ F(n)\le n^{\beta+o(1)}\ll n^{1.4031} \qquad {\rm and}\qquad h_{\mathbb P}(n) \ll \frac{n^{7/5}}{(\log n)^{2/5}}, \] where $\beta\in (1,2)$ is the root of $2\beta^3-8\beta^2+8\beta-1=0$. This improves the previous best bounds $F(n)\ll n^{3/2}$ and $h_{\mathbb{P}}(n)\ll n^{3/2}/\sqrt{\log n}$ by Erd\H{o}s and Pomerance in 1980. Our upper bound on $F(n)$ is a corollary of the sum--difference theorem of Katz and Tao, while the upper bound on $h_{\mathbb P}(n)$ is achieved via a novel combinatorial method.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 1 linked inside Pith

  1. [1]

    T. F. Bloom, Erdős Problem #711,https://www.erdosproblems.com/711, accessed July 21, 2026. 15

    2026

  2. [2]

    T. F. Bloom, Erdős Problem #860,https://www.erdosproblems.com/860, accessed July 21, 2026

    2026

  3. [3]

    A. E. Brouwer and W. H. Haemers,Spectra of Graphs, Universitext, Springer, New York, 2012

    2012

  4. [4]

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

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

    1992

  5. [5]

    Erdős and C

    P. Erdős and C. Pomerance, Matching the natural numbers up tonwith distinct multiples in another interval,Indagationes Mathematicae42(1980), no. 2, 147–161

    1980

  6. [6]

    Green and I

    B. Green and I. Z. Ruzsa, On the arithmetic Kakeya conjecture of Katz and Tao, Periodica Mathematica Hungarica78(2019), no. 2, 135–151

    2019

  7. [7]

    R. K. Guy,Unsolved problems in number theory, Springer, New York, 2004

    2004

  8. [8]

    Hadamard, Sur la distribution des zéros de la fonctionζ(s)et ses conséquences arithmétiques,Bulletin de la Société Mathématique de France24(1896), 199–220

    J. Hadamard, Sur la distribution des zéros de la fonctionζ(s)et ses conséquences arithmétiques,Bulletin de la Société Mathématique de France24(1896), 199–220

Show all 16 references
  1. [9]

    Hall, On representatives of subsets,Journal of the London Mathematical Society s1-10(1935), no

    P. Hall, On representatives of subsets,Journal of the London Mathematical Society s1-10(1935), no. 1, 26–30

    1935

  2. [10]

    Ireland and M

    K. Ireland and M. Rosen,A Classical Introduction to Modern Number Theory, 2nd ed., Graduate Texts in Mathematics 84, Springer, New York, 1990

    1990

  3. [11]

    N. H. Katz and T. Tao, New bounds for Kakeya problems,Journal d’Analyse Math- ématique87(2002), 231–263

    2002

  4. [12]

    S. D. Kominers, Long intervals without distinct multiples of the firstnpositive integers, arXiv:2607.10431, 2026

    2026 arXiv

  5. [13]

    Mertens, Ein Beitrag zur analytischen Zahlentheorie,Journal für die reine und angewandte Mathematik78(1874), 46–62

    F. Mertens, Ein Beitrag zur analytischen Zahlentheorie,Journal für die reine und angewandte Mathematik78(1874), 46–62

  6. [14]

    I. Z. Ruzsa, Few multiples of many primes,Studia Scientiarum Mathematicarum Hungarica30(1995), no. 1–2, 123–125

    1995

  7. [15]

    de la Vallée Poussin, Recherches analytiques sur la théorie des nombres premiers, Annales de la Société Scientifique de Bruxelles20(1896), 183–256

    C.-J. de la Vallée Poussin, Recherches analytiques sur la théorie des nombres premiers, Annales de la Société Scientifique de Bruxelles20(1896), 183–256

  8. [16]

    van Doorn, On the length of an interval that contains distinct multiples of the firstnpositive integers, arXiv:2601.16972, 2026

    W. van Doorn, On the length of an interval that contains distinct multiples of the firstnpositive integers, arXiv:2601.16972, 2026. 16

    2026

Pith tools

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