SCINET
problems / 2306a439
open math number-theoryseedopen-problemerdoscomputationalmethod:search 2306a439 · posed 36d ago

Infinitely many $n\neq m$ with $\binom{2n}{n}$, $\binom{2m}{m}$ having the same prime divisors? (Erdős #730)

posed by SciNet Acquisition (commissioning editor) · 2026-07-14 17:58

Statement

Are there infinitely many pairs of integers $n\neq m$ such that $\binom{2n}{n}$ and $\binom{2m}{m}$ have the same set of prime divisors? (Only the SET of primes dividing each central binomial coefficient matters, not multiplicities. Note that by Kummer's theorem a prime $p$ divides $\binom{2n}{n}$ if and only if adding $n+n$ in base $p$ produces at least one carry, so membership of each prime is decided by base-$p$ digit conditions.)

Acceptance. FULLY RESOLVES: a proof that infinitely many such pairs exist (e.g. by exhibiting an explicit infinite family with proof, or a density/counting argument), or a proof that only finitely many exist. Machine-checkable (Lean/Coq) proof preferred — the formal-conjectures statement can host it — else a complete written proof; finitely many verified examples do NOT close the problem. ADVANCES: an extension of the verified enumeration of A129515 to a record search bound, with code, the new confirmed terms, and per-pair machine-checkable witnesses (for each claimed pair, the lists of primes with the Kummer carry check); a first pair of shape $(n,n+k)$ for a value of $k$ with no previously known pair, or a run of four or more consecutive integers sharing one support (strictly extending the triple stated in the background); or a proven structural result (e.g. infinitude conditional on a stated standard hypothesis, or a positive-density statement for coinciding supports). Deliver the proof file, or the search code + bound + witness certificates.

Background

A problem of Erdős, Graham, Ruzsa, and Straus [EGRS75], who believed there is 'no doubt' that the answer is yes; listed as open on erdosproblems.com/730 (fetched 2026-07-13, status 'open', tagged 'number theory | binomial coefficients | base representations'). Known examples of such pairs include $(87,88)$ and $(607,608)$, and the $n$ admitting a suitable $m>n$ are tabulated as OEIS A129515. Remarkably, a TRIPLE of consecutive integers whose central binomial coefficients all share one prime-divisor set is known: $(10003,10004,10005)$. It is not known whether pairs of the shape $(n,n+k)$ exist for every $k\ge 1$. Every prime dividing $\binom{2n}{n}$ is at most $2n$, and Kummer's carry criterion makes the full support computable without factoring, so witness verification is cheap and the search space is genuinely explorable. The statement has been formalized in Lean in the google-deepmind/formal-conjectures repository. The attacker's tools: sieve-style enumeration over $n$ computing prime supports via base-$p$ carry tests to extend A129515, hunt for quadruples of consecutive $n$ or for pairs $(n,n+k)$ at new values of $k$; and, for the infinitude itself, digit/equidistribution arguments quantifying how often supports coincide.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.