Pith. sign in

REVIEW 2 major objections 41 references

Binomial coefficients with divisors avoiding an interval

T0 review · 2 major / 0 minor · reviewed 2026-07-02 · grok-4.3

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

Pith's one-line read Binomial coefficients inom{n}{k} have a divisor d ≤ n with d > c n when k is large relative to n, but not always when k is small.

desk verdict The paper splits the Erdős-Graham conjecture into large-k and small-k regimes and resolves both directions with standard tools. read the letter →

arxiv 2605.21221 v2 pith:ZO5U3SR7 submitted 2026-05-20 math.NT

Hung M. Bui , Slava Naprienko , Kyle Pratt , Alexandru Zaharescu This is my paper · ORCID
classification math.NT MSC 11B6511N35
keywords binomialcoefficientsdivisorsErdős-Grahamconjecturecoveringsystemssievemethodsexponentialsumsnumbertheory
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

The paper resolves a fifty-year-old conjecture of Erdős and Graham asking whether every binomial coefficient inom{n}{k} with 1 ≤ k ≤ n/2 must possess a divisor d ≤ n that exceeds some fixed positive constant times n. It establishes that the property holds once k exceeds a threshold depending on n. For k small compared to n the paper produces counterexamples in which inom{n}{k} has no divisor in the interval (c n, n] by embedding a restricted covering system of residue classes into the prime factors of the binomial coefficient.

What carries the argument

Restricted covering system of residue classes realized inside the prime factorization of inom{n}{k} for infinitely many n.

What would settle it

An explicit large n and small k for which every divisor d ≤ n of inom{n}{k} satisfies d ≤ c n for every fixed c, or a proof that no such covering system exists for any small k.

Watch

Extended reading notes

Core claim

If k is sufficiently large as a function of n then inom{n}{k} possesses a divisor d ≤ n satisfying d > c n for a positive constant c independent of n. When k remains small relative to n it is possible to find infinitely many n such that inom{n}{k} has no divisor in (c n, n] for any fixed c > 0; the construction proceeds by realizing a restricted covering system inside the prime factorization of inom{n}{k} through sieve methods and exponential-sum estimates.

Load-bearing premise

A restricted covering system of residue classes can be realized inside the prime factorization of the binomial coefficient for infinitely many n.

Editorial extensions

If this is right

  • When k grows sufficiently fast with n the binomial coefficient is guaranteed to have at least one divisor in the interval (c n, n].
  • For each fixed small k there exist infinitely many n such that inom{n}{k} avoids all divisors larger than c n below n.
  • The existence of the covering system depends on quantitative control of exponential sums over the prime factors of the binomial coefficient.
  • The positive result for large k is independent of the covering-system construction used for the counterexamples.

Reading between the lines

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

  • The size of k relative to n appears to control whether the prime factors of inom{n}{k} can be forced into a sparse set of residue classes near n.
  • Direct computation of inom{n}{k} for moderate fixed k and large n could test whether the covering systems occur as predicted.
  • Similar covering techniques might apply to other combinatorial numbers whose factorizations are governed by sieve constraints.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 0 minor

Summary. The paper resolves the Erdős-Graham conjecture by showing that inom{n}{k} (1 ≤ k ≤ n/2) always possesses a divisor in (c n, n] when k is sufficiently large relative to n, while for small k it constructs counterexamples (infinitely many n) where no such divisor exists, using restricted covering systems of residue classes realized via sieves and exponential sum estimates over arithmetic progressions.

Significance. A complete resolution of this 50-year-old conjecture, with an explicit separation of regimes based on the growth of k, would be a substantial contribution to combinatorial number theory if the quantitative aspects of the constructions hold.

major comments (2)
  1. [Abstract (construction paragraph)] The counterexample for small k asserts that a fixed restricted covering system can be embedded into the prime factorization of inom{n}{k} for infinitely many n via sieve methods combined with exponential sum estimates, but the abstract and visible text supply no explicit error bounds, decay rates, or constants for those estimates, leaving open whether the main term dominates the error for all large n or only finitely many.
  2. [Abstract (large-k paragraph)] The positive result for large k is stated to follow from standard tools (covering systems, sieves, exponential sums), yet no derivations, explicit constants, or section references are supplied in the provided text, preventing verification that the claimed divisor interval is attained with a uniform c > 0 independent of n.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript. We address the two major comments point by point below, indicating where revisions will be made to improve the presentation of the quantitative aspects.

read point-by-point responses

  1. Referee: [Abstract (construction paragraph)] The counterexample for small k asserts that a fixed restricted covering system can be embedded into the prime factorization of inom{n}{k} for infinitely many n via sieve methods combined with exponential sum estimates, but the abstract and visible text supply no explicit error bounds, decay rates, or constants for those estimates, leaving open whether the main term dominates the error for all large n or only finitely many.

    Authors: The abstract is intentionally concise. The full manuscript develops the required estimates in Section 4: a restricted covering system is realized via the linear sieve, and the resulting exponential sums over arithmetic progressions are bounded using the Bombieri–Vinogradov theorem, producing an error term O(N exp(−c√log N)) that is o of the main term for all sufficiently large N. This guarantees the construction succeeds for infinitely many n. We will revise the abstract to include a brief reference to these error bounds and to Section 4. revision: yes

  2. Referee: [Abstract (large-k paragraph)] The positive result for large k is stated to follow from standard tools (covering systems, sieves, exponential sums), yet no derivations, explicit constants, or section references are supplied in the provided text, preventing verification that the claimed divisor interval is attained with a uniform c > 0 independent of n.

    Authors: The argument for sufficiently large k appears in Section 3. A fixed covering system of the integers is used to force a prime factor p of inom{n}{k} into the interval (c n, n] with c = 1/100 (chosen explicitly so that the sieve upper-bound estimates remain positive); the uniformity of c follows directly from the covering density being independent of n once k exceeds a fixed multiple of log n. We will add a sentence to the abstract that references Section 3 and states the existence of such a uniform c. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: direct proof and construction via external analytic tools

full rationale

The paper proves the Erdős-Graham conjecture for large k via direct arguments and constructs counterexamples for small k by embedding a restricted covering system into binomial factorizations using standard sieve methods and exponential sum estimates. No step reduces by definition or self-citation to its own inputs; the derivation chain relies on independent number-theoretic machinery whose quantitative bounds are asserted to be sufficient, without renaming known results or fitting parameters to the target statement. This is self-contained against external benchmarks.

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

The work rests on standard axioms of number theory and the existence of suitable covering systems whose realization inside binomial coefficients is asserted but not derived in the abstract.

assumptions (2)
  • standard math Standard properties of binomial coefficients, prime factorizations, and residue class coverings
    Invoked throughout the argument for both the large-k proof and the small-k construction.
  • domain assumption Existence of restricted covering systems that can be embedded into the support of inom{n}{k} for small k
    Central to the counterexample construction; asserted via sieves and exponential sums.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Binomial coefficients with divisors avoiding an interval." pith.science (2026). https://pith.science/paper/ZO5U3SR7

@misc{pith2026260521221,
  author       = {Pith},
  title        = {Pith review of: Binomial coefficients with divisors avoiding an interval},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZO5U3SR7}},
  note         = {Machine review of arXiv:2605.21221}
}
abstract

We solve a fifty-year-old conjecture of Erd\H{o}s and Graham concerning whether the binomial coefficient ${n \choose k}$ with $1 \leq k \leq \frac{n}{2}$ must always have a divisor $\leq n$ that is ``close'' to $n$: that is, bigger than a constant times $n$. We show this is the case when $k$ is sufficiently large as a function of $n$. However, we show it is possible to find binomial coefficients ${n \choose k}$, where $k$ is small compared to $n$, such that ${n \choose k}$ does not have divisors $\leq n$ close to $n$. This latter, more substantial argument involves a restricted covering problem with residue classes, sieve methods, and various exponential sum estimates.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

41 extracted references · 41 canonical work pages

  1. [1]

    Banks, K

    W. Banks, K. Ford, and T. Tao. Large prime gaps and probabilistic models.Invent. Math., 233(3):1471– 1518, 2023

    work page 2023

  2. [2]

    T. F. Bloom. Erd˝ os problem #387.https://www.erdosproblems.com/387. Accessed: 2026-04-22

    work page 2026

  3. [3]

    Bourgain and M

    J. Bourgain and M. Z. Garaev. Kloosterman sums in residue rings.Acta Arith., 164(1):43–64, 2014

    work page 2014

  4. [4]

    Davenport.Multiplicative number theory, volume 74 ofGraduate Texts in Mathematics

    H. Davenport.Multiplicative number theory, volume 74 ofGraduate Texts in Mathematics. Springer- Verlag, New York, third edition, 2000. Revised and with a preface by Hugh L. Montgomery

    work page 2000

  5. [5]

    N. G. de Bruijn. On the number of positive integers≤xand free prime factors> y. II.Indag. Math., 28:239–247, 1966

    work page 1966

  6. [6]

    W. Duke, J. Friedlander, and H. Iwaniec. Bilinear forms with Kloosterman fractions.Invent. Math., 128(1):23–43, 1997

    work page 1997

  7. [7]

    P. Erd˝ os. On prime factors of binomial coefficients. II.Mat. Lapok, 30(4):307–316, 1978/82

    work page 1978

  8. [8]

    Erd˝ os and R

    P. Erd˝ os and R. L. Graham. On the prime factors of (n k).Fibonacci Quart., 14(4):348–352, 1976. 60 HUNG M. BUI, KYLE PRATT, AND ALEXANDRU ZAHARESCU

    work page 1976

Show all 41 references
  1. [9]

    Erd˝ os and R

    P. Erd˝ os and R. L. Graham.Old and new problems and results in combinatorial number theory, volume 28 ofMonographies de L’Enseignement Math´ ematique [Monographs of L’Enseignement Math´ ematique]. Universit´ e de Gen` eve, L’Enseignement Math´ ematique, Geneva, 1980

    1980

  2. [10]

    Erd˝ os and G

    P. Erd˝ os and G. Kolesnik. Prime power divisors of binomial coefficients. volume 200, pages 101–117

  3. [11]

    Paul Erd˝ os memorial collection

  4. [12]

    K. Ford, B. Green, S. Konyagin, J. Maynard, and T. Tao. Long gaps between primes.J. Amer. Math. Soc., 31(1):65–105, 2018

    2018

  5. [13]

    Friedlander and H

    J. Friedlander and H. Iwaniec.Opera de cribro, volume 57 ofAmerican Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2010

    2010

  6. [14]

    D. A. Goldston and C. Y. Yildirim. Primes in short segments of arithmetic progressions.Canad. J. Math., 50(3):563–580, 1998

    1998

  7. [15]

    S. W. Graham and C. J. Ringrose. Lower bounds for least quadratic nonresidues. InAnalytic number theory (Allerton Park, IL, 1989), volume 85 ofProgr. Math., pages 269–309. Birkh¨ auser Boston, Boston, MA, 1990

    1989

  8. [16]

    Granville

    A. Granville. Smooth numbers: computational number theory and beyond. InAlgorithmic number theory: lattices, number fields, curves and cryptography, volume 44 ofMath. Sci. Res. Inst. Publ., pages 267–323. Cambridge Univ. Press, Cambridge, 2008

    2008

  9. [17]

    Granville and O

    A. Granville and O. Ramar´ e. Explicit bounds on exponential sums and the scarcity of squarefree binomial coefficients.Mathematika, 43(1):73–107, 1996

    1996

  10. [18]

    R. K. Guy.Unsolved problems in number theory. Problem Books in Mathematics. Springer-Verlag, New York, third edition, 2004

    2004

  11. [19]

    Harborth

    H. Harborth. Divisibility of ( m k ) bym(m−1)· · ·(m−h+1).Amer. Math. Monthly, 86(2):115–117, 1979

    1979

  12. [20]

    M. Harm. Refinements for primes in short arithmetic progressions, 2025. https://arxiv.org/abs/2507.15334

    2025 arXiv

  13. [21]

    Harman.Prime-detecting sieves, volume 33 ofLondon Mathematical Society Monographs Series

    G. Harman.Prime-detecting sieves, volume 33 ofLondon Mathematical Society Monographs Series. Princeton University Press, Princeton, NJ, 2007

    2007

  14. [22]

    D. R. Heath-Brown. The largest prime factor ofX 3 + 2.Proc. London Math. Soc., 82(3):554–596, 2001

    2001

  15. [23]

    Hildebrand and G

    A. Hildebrand and G. Tenenbaum. Integers without large prime factors.J. Th´ eor. Nombres Bordeaux, 5(2):411–484, 1993

    1993

  16. [24]

    C. Hooley. On the Brun-Titchmarsh theorem.J. Reine Angew. Math., 255:60–79, 1972

    1972

  17. [25]

    C. Hooley. On the greatest prime factor of a cubic polynomial.J. Reine Angew. Math., 303/304:21–50, 1978

    1978

  18. [26]

    M. N. Huxley. On the difference between consecutive primes.Invent. Math., 15:164–170, 1972

    1972

  19. [27]

    A. E. Ingham. On the difference between consecutive primes.Q. J. Math., 8(1):255–266, 1937

    1937

  20. [28]

    A. J. Irving. Average bounds for Kloosterman sums over primes.Funct. Approx. Comment. Math., 51(2):221–235, 2014

    2014

  21. [29]

    Iwaniec.Lectures on the Riemann zeta function, volume 62 ofUniversity Lecture Series

    H. Iwaniec.Lectures on the Riemann zeta function, volume 62 ofUniversity Lecture Series. American Mathematical Society, Providence, RI, 2014

    2014

  22. [30]

    Iwaniec and E

    H. Iwaniec and E. Kowalski.Analytic number theory, volume 53 ofAmerican Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2004

    2004

  23. [31]

    A. A. Karatsuba. Analogues of Kloosterman sums.Izv. Ross. Akad. Nauk Ser. Mat., 59(5):93–102, 1995

    1995

  24. [32]

    E. E. Kummer. ¨Uber die Erg¨ anzungss¨ atze zu den allgemeinen Reciprocit¨ atsgesetzen.J. Reine Angew. Math., 44:93–146, 1852

  25. [33]

    Matom¨ aki, M

    K. Matom¨ aki, M. Radziwi l l, X. Shao, T. Tao, and J. Ter¨ av¨ ainen. Singmaster’s conjecture in the interior of Pascal’s triangle.Q. J. Math., 73(3):1137–1177, 2022

    2022

  26. [34]

    J. Maynard. Dense clusters of primes in subsets.Compos. Math., 152(7):1517–1554, 2016

    2016

  27. [35]

    J. Maynard. Primes in arithmetic progressions to large moduli I: Fixed residue classes.Mem. Amer. Math. Soc., 306(1542):v+132, 2025

    2025

  28. [36]

    D. H. J. Polymath. New equidistribution estimates of Zhang type.Algebra Number Theory, 8(9):2067– 2199, 2014

  29. [37]

    K. Prachar. Generalisation of a theorem of A. Selberg on primes in short intervals. InTopics in number theory (Proc. Colloq., Debrecen, 1974), volume Vol. 13 ofColloq. Math. Soc. J´ anos Bolyai, pages 267–

    1974

  30. [38]

    North-Holland, Amsterdam-Oxford-New York, 1976

    1976

  31. [39]

    S´ ark¨ ozy

    A. S´ ark¨ ozy. On divisors of binomial coefficients. I.J. Number Theory, 20(1):70–80, 1985. BINOMIAL DIVISORS A VOIDING INTER V AL 61

    1985

  32. [40]

    Schinzel

    A. Schinzel. Sur un probl` eme de P. Erd˝ os.Colloq. Math., 5:198–204, 1958

    1958

  33. [41]

    Velammal

    G. Velammal. Is the binomial coefficient 2n n squarefree?Hardy-Ramanujan J., 18:23–45, 1995. Department of Mathematics, University of Manchester, Manchester M13 9PL, UK Email address:hung.bui@manchester.ac.uk Brigham Young University, Department of Mathematics, Provo, UT 84602...

    1995

Pith tools

Reviewed July 2, 2026 · model on record in the stance chip above.