Erdős Problem #728 - Discussion thread

PROVED (LEAN) This has been solved in the affirmative and the proof verified in Lean.

Let $C>0$ and $\epsilon>0$ be sufficiently small. Are there infinitely many integers $a,b,n$ with $a\geq \epsilon n$ and $b\geq \epsilon n$ such that\[a! b! \mid n!(a+b-n)!\]and $a+b>n+C\log n$?

A question of Erdős, Graham, Ruzsa, and Straus [EGRS75].
Erdős [Er68c] proved that if $a!b!\mid n!$ then $a+b\leq n+O(\log n)$.

This problem can be rephrased (taking $k=a+b-n$ and $N=a+b$) as asking for $\binom{N}{k}\mid \binom{N}{a}$.

This problem is ambiguous, and there are a number of trivial solutions to the problem as written. for example, the AlphaProof team has noted that there are solutions with very large $a$ and $b$ - for example, $a=n+w+1$ and $b=\frac{(n+w+1)!}{n!}-1$ for some $w\geq \max(C\log n,\epsilon n)$.

From context presumably the condition $a,b\leq n$ was intended, but here we also have trivial solutions: for example one can take $a=b=n$, or $b=n-1$ and $a$ any large divisor of $n$. No doubt the authors had in mind some condition such as $a,b\leq (1-\epsilon)n$.

Barreto and ChatGPT-5.2 have proved that, for any $0<C_1<C_2$, there are infinitely many $a,b,n$ with $b=n/2$, $a=n/2+O(\log n)$, and\[C_1\log n< a+b-n< C_2\log n\]such that\[a!b!\mid n!(a+b-n)!.\]This appears to answer the question in the spirit it was intended.

See also [729].

View the LaTeX source

This page was last edited 06 January 2026. View history

Additional thanks to: Yael Dillies and Moritz Firsching

When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:

T. F. Bloom, Erdős Problem #728, https://www.erdosproblems.com/728, accessed 2026-03-10

Order by oldest first or newest first. (The most recent comments are highlighted in a red border.)

• Carl Pomerance's writeup "A remark on the middle binomial coefficient" has been formalized by Aristotle. Type-check it online!

  There's not necessarily anything exciting in this formalization, but it *did* help generate feedback for the writeup itself, in particular informing the specific constants in the theorems. It is also one of the longest files I've posted (I didn't do any cleanup), perhaps out of proportion with the difficulty of the arguments? Or at least the de Bruijn factor is higher than usual.

• In the latest version of the writeup on arxiv, I’ve added another appendix discussing the generalization which has [728], [729], [401] as corollaries. Also, in Carl Pomerance’s latest preprint, this also gives slightly weaker results than his Theorem 1 and Theorem 2 (my bounds are ineffective while Pomerance’s bounds are effective). I’ve also emailed Carl Pomerance directly regarding this update!

• Carl Pomerance has just uploaded to his web site a brief note explaining how the methods of his paper can resolve this question (with $a+b-n$ as large as $\exp(\log^{1/2} n)$), with some brief remarks on potential further improvements beyond this.

• After some grueling work (although made much lighter with ChatGPT), I have produced a complete paper containing a writeup of Aristotle's proof. This means it's on an exact same level as a journal submission, sidestepping the difficulty of how to treat "half-finished paper" that I produced earlier.

  This means several things:

  1) I went thorough all mathematics myself. In particular, any inaccuracy or awkward statement written by ChatGPT are all corrected using the usual standard for human mathematicians.

  2) I checked the Lean file correspondence as best as I can. Admittedly this is the weakest point (because I don't know Lean), but I did ask ChatGPT to correct/improve anything that looks off to me.

  3) I looked at all the literature cited and ensure that the description is accurate. (ChatGPT's original and even subsequent versions are often a bit off - this may be its limit in understanding, though it does understand many things and produces many useful statements.)

  4) I wrote our story (recorded in this thread) in the appendix!

  About the workflow:

  I actually find that ChatGPT has several recurring weak points. In particular, for proofs, details are often over-presented (too much details that dilute the content), but surprisingly you can often delete some things to make it perfect! This is much easier than writing it up in the first place. However, for exposition/commentaries, a lot of times crucial things are missing and/or what it writes is somewhat irrelevant. I often have to rewrite the whole thing. But fortunately this seems easier to write than proofs. So overall, it feels like this makes the writing process easier. But! You need very high discipline to make this work: the intermediate work often looks *good* at a glance already, so you must keep responsibility in making sure every part is properly addressed (because the wrong things won't jump out). I still won't recommend this as a standard workflow or anything, but this particular case (Erdos 728) seems special, so it warrants special methods, so to speak.

  I'll leave this here and invite everyone to find errors and corrections. Once this seems ready, I'll probably submit to arxiv, but won't do a journal submission. (Note: I won't fix grammar. I know I have bad grammar; but it's fine if it doesn't impact readability.)

  Edit: I'll add acknowledgements to everyone discussing the math in here, which I forgot to add.

• Some references to related recent work, obtained by more good old-fashioned bibliographic search:

  1. Ford, Kevin; Konyagin, Sergei Divisibility of the central binomial coefficient $\binom{2n}{n}$, Trans. Am. Math. Soc. 374, No. 2, 923-953 (2021). Builds upon the Pomerance paper, for instance by determining the density of $n$ for which $n^\ell | \binom{2n}{n}$, although the emphasis is on the regime where $\ell$ is fixed and $n$ goes to infinity.
  2. Croot, Ernie; Mousavi, Hamed; Schmidt, Maxie, On a conjecture of Graham on the p-divisibility of central binomial coefficients
  Mathematika 70, No. 3, Article ID e12249, 29 p. (2024). This is more to do with #376, studying the situation where the number of small prime factors of $\binom{2n}{n}$ is unexpectedly small (which is the opposite of the situation here where we want the number of such factors to be large). I'll also make a note of this reference at that problem page. EDIT: there is even more recent work by Bloom and Croot here.

  In the event that a research paper is formed from this work, one should definitely do a more complete literature survey (presumably one can get further references by various forwards and backwards citation searches from these two recent works).

All comments are the responsibility of the user. Comments appearing on this page are not verified for correctness. Please keep posts mathematical and on topic.