728 Discussion Thread | Erdős Problems

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-08-16

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

• I realize this was already solved back in January, but I've been working on an AI research agent recently and have been using this problem as one of my test cases. In the process, it generated two new methodologically distinct solutions that may be of interest to the community. You can read them at:
  Paper 1 link
  Paper 2 link
  Both of the proofs are deterministic, distinguishing them from the January proof.
  The first paper was checked with Lean. I've been checking some of my research agent's output in Lean, not all of it only because I find it is generally very trustworthy these days, and generating Lean increases the cost and slows it down. However, if there is a mistake, I'd be interested to hear that feedback.
  I know that this community doesn't want to have pure AI commentary only, so I did in fact read over the work and work through it myself as I understand it. I've verified them in various ways including Lean, so I believe it should be correct.

• 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).

• 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.

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.