pith. sign in

arxiv: 2605.21221 · v1 · pith:ZO5U3SR7new · submitted 2026-05-20 · 🧮 math.NT

Binomial coefficients with divisors avoiding an interval

Hung M. Bui , Kyle Pratt , Alexandru Zaharescu This is my paper

Pith reviewed 2026-05-21 01:40 UTC · model grok-4.3

classification 🧮 math.NT
keywords binomial coefficientsdivisorsErdős-Graham conjecturecovering systemssieve methodsGeneralized Riemann Hypothesisexponential sumsnumber theory
0
0 comments X

The pith

Under the Generalized Riemann Hypothesis, some binomial coefficients with small k lack any divisors in a positive proportion of the interval up to n.

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

The paper examines a conjecture of Erdős and Graham asking whether every binomial coefficient binom n k with 1 ≤ k ≤ n/2 must have a divisor d ≤ n satisfying d > c n for a fixed positive constant c. It proves that the required divisor always exists once k grows sufficiently rapidly as a function of n. Under the Generalized Riemann Hypothesis the authors produce counterexamples in which k remains small relative to n and the binomial coefficient has no divisors in the interval (c n, n]. This gives a conditional negative answer to the conjecture for the small-k regime.

Core claim

The Erdős-Graham conjecture holds whenever k is sufficiently large as a function of n, yet fails for certain small k under the Generalized Riemann Hypothesis; the failure is established by constructing binomial coefficients whose prime factors below n all lie well below c n, via a restricted covering of residue classes together with sieve methods and exponential-sum estimates.

What carries the argument

A restricted covering problem with residue classes, solved using sieve methods and exponential sum estimates to produce binomial coefficients free of divisors in (c n, n].

If this is right

  • Whenever k exceeds a certain threshold depending on n, binom n k is guaranteed to possess a divisor in (c n, n] for some absolute c > 0.
  • Under GRH there exist infinitely many n and corresponding small k such that binom n k avoids all divisors in a large subinterval of [1, n].
  • The size of k relative to n determines whether the Erdős-Graham property holds unconditionally or only conditionally on GRH.

Where Pith is reading between the lines

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

  • The transition point between the large-k regime where the property is unconditional and the small-k regime where it requires GRH may be pinned down more precisely by refining the covering construction.
  • Analogous covering techniques could be applied to other families of combinatorial integers whose prime factors are constrained by similar arithmetic-progression conditions.
  • If GRH fails, the existence of such divisor-avoiding binomial coefficients for small k would remain open, potentially requiring different methods.

Load-bearing premise

The Generalized Riemann Hypothesis is assumed in order to guarantee the arithmetic-progression distributions needed for the residue-class covering to succeed.

What would settle it

An explicit pair of integers n and k with k small compared to n for which the prime factorization of binom n k can be computed and shown to contain no prime factor in the interval (c n, n] for a fixed c > 0.

read the original abstract

We investigate 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 (under the Generalized Riemann Hypothesis) 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 settles the conjecture of Erd\H{o}s and Graham, under GRH. This latter, more substantial argument involves a restricted covering problem with residue classes, sieve methods, and various exponential sum estimates.

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.

Referee Report

3 major / 2 minor

Summary. The manuscript addresses the Erdős–Graham conjecture on whether every binomial coefficient {n choose k} (1 ≤ k ≤ n/2) possesses a divisor d ≤ n satisfying d ≫ n. It proves unconditionally that such a divisor exists whenever k is sufficiently large as a function of n, using sieve methods. Under the Generalized Riemann Hypothesis, it constructs counterexamples for small k via a restricted covering system of residue classes combined with a sieve that eliminates candidate divisors in an interval (c n, n], relying on GRH-derived bounds for exponential sums over characters.

Significance. If the derivations hold, the unconditional theorem resolves the conjecture in the large-k regime with standard analytic tools, while the GRH-conditional construction provides a disproof for small k and thus settles the full conjecture conditionally. The paper appropriately credits the use of covering systems and GRH-based character-sum estimates; these are load-bearing for the complementary regimes and represent a proportionate advance on a fifty-year-old problem.

major comments (3)
  1. [§5] §5, exponential-sum estimates under GRH: the zero-free region for Dirichlet L-functions is invoked to bound character sums, but the resulting error term in the sieve (after inclusion-exclusion over the covering) must be shown smaller than the main term by an explicit factor; without this comparison the covering may fail to remove every divisor in (c n, n].
  2. [Theorem 1.2] Theorem 1.2 (unconditional large-k statement): the threshold 'k sufficiently large as a function of n' is not made effective; the level of distribution in the sieve must be verified to hold down to the smallest k for which the main term dominates, otherwise the transition between the two regimes remains imprecise.
  3. [§6] §6, restricted covering construction: the completeness of the residue-class covering for the chosen interval length must be checked against the specific modulus; any uncovered class would permit a potential divisor d ≈ n and invalidate the counterexample.
minor comments (2)
  1. [Abstract] The abstract and introduction use 'close to n' without fixing an explicit constant c in the first paragraph; a uniform c > 0 should be stated once for both the positive and negative results.
  2. [§3 and §6] Notation for the sieve weights and the restricted covering could be unified between §3 and §6 to avoid redefining similar objects.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment point by point below, indicating the changes we will make in the revised version.

read point-by-point responses

  1. Referee: [§5] §5, exponential-sum estimates under GRH: the zero-free region for Dirichlet L-functions is invoked to bound character sums, but the resulting error term in the sieve (after inclusion-exclusion over the covering) must be shown smaller than the main term by an explicit factor; without this comparison the covering may fail to remove every divisor in (c n, n].

    Authors: We agree that an explicit comparison of the error term to the main term is necessary to confirm that the sieve removes all candidates in (c n, n]. In the revised manuscript we will add a detailed calculation in §5, using the explicit constants from the zero-free region for Dirichlet L-functions, to show that the total error after inclusion-exclusion is at most half the size of the main term for all sufficiently large n. revision: yes

  2. Referee: [Theorem 1.2] Theorem 1.2 (unconditional large-k statement): the threshold 'k sufficiently large as a function of n' is not made effective; the level of distribution in the sieve must be verified to hold down to the smallest k for which the main term dominates, otherwise the transition between the two regimes remains imprecise.

    Authors: We acknowledge that the current statement of Theorem 1.2 leaves the threshold implicit. To make the transition between regimes more precise, we will revise the manuscript to supply an explicit (though possibly large) lower bound on k in terms of n. This requires tracing the constants through the level-of-distribution estimates in the sieve; we will add a short appendix or remark verifying that the main term dominates for all k exceeding this explicit bound. revision: yes

  3. Referee: [§6] §6, restricted covering construction: the completeness of the residue-class covering for the chosen interval length must be checked against the specific modulus; any uncovered class would permit a potential divisor d ≈ n and invalidate the counterexample.

    Authors: The referee is right that completeness of the covering must be verified explicitly for the chosen modulus and interval length. In the revised §6 we will include a direct check (or a short computational verification for the specific parameters) confirming that every integer in the target interval lies in at least one of the residue classes, so that no divisor d in (c n, n] remains uncovered. revision: yes

Circularity Check

0 steps flagged

No circularity: unconditional large-k result and GRH-conditional small-k construction are independent of self-referential inputs

full rationale

The paper establishes an unconditional theorem that binom(n,k) has a divisor d ≤ n with d ≫ n when k is large relative to n, using standard sieve or divisor arguments that do not reduce to fitted parameters or self-definitions. The complementary construction of counterexamples for small k explicitly invokes the external Generalized Riemann Hypothesis to obtain the necessary exponential-sum bounds for the sieve; this is not a prediction derived from the paper's own data or prior self-citations but a standard conditional existence argument resting on zero-free regions for L-functions. No load-bearing step equates a claimed prediction to its own input by construction, nor does any uniqueness theorem or ansatz originate from the authors' earlier work in a circular manner. The derivation chain remains self-contained against external benchmarks once GRH is granted as an assumption.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the Generalized Riemann Hypothesis for the counterexample construction and on standard but non-trivial estimates from sieve theory and exponential sums whose full justification lies outside the abstract.

axioms (1)
  • domain assumption Generalized Riemann Hypothesis
    Invoked to guarantee the existence of the small-k binomial coefficients without divisors in the forbidden interval.

pith-pipeline@v0.9.0 · 5688 in / 1224 out tokens · 46645 ms · 2026-05-21T01:40:48.717704+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

41 extracted references · 41 canonical work pages · 1 internal anchor

  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

  9. [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

    work page 1980

  10. [10]

    Erd˝ os and G

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

    work page

  11. [11]

    Paul Erd˝ os memorial collection

    work page

  12. [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

    work page 2018

  13. [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

    work page 2010

  14. [14]

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

    work page 1998

  15. [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

    work page 1989

  16. [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

    work page 2008

  17. [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

    work page 1996

  18. [18]

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

    work page 2004

  19. [19]

    Harborth

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

    work page 1979

  20. [20]

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

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  21. [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

    work page 2007

  22. [22]

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

    work page 2001

  23. [23]

    Hildebrand and G

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

    work page 1993

  24. [24]

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

    work page 1972

  25. [25]

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

    work page 1978

  26. [26]

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

    work page 1972

  27. [27]

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

    work page 1937

  28. [28]

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

    work page 2014

  29. [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

    work page 2014

  30. [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

    work page 2004

  31. [31]

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

    work page 1995

  32. [32]

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

    work page

  33. [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

    work page 2022

  34. [34]

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

    work page 2016

  35. [35]

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

    work page 2025

  36. [36]

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

    work page 2067

  37. [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–

    work page 1974

  38. [38]

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

    work page 1976

  39. [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

    work page 1985

  40. [40]

    Schinzel

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

    work page 1958

  41. [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, USA Email address:kyle.pratt@mathematics.byu.edu Department of Mathematics, Un...

    work page 1995