← All problems

Erdős Problem #376 — Central binomial coefficients coprime to 105

45 years old · documented by

For a positive integer nn, let (2nn)=(2n)!/(n!)2\binom{2n}{n}=(2n)!/(n!)^2 be the central binomial coefficient, and let gcd⁡(a,b)\gcd(a,b) denote the greatest common divisor of integers aa and bb. Is the set

{n∈Z≥1:gcd⁡ ⁣((2nn),105)=1},105=3⋅5⋅7,\left\{n\in\mathbb Z_{\geq 1}:\gcd\!\left(\binom{2n}{n},105\right)=1\right\},\qquad 105=3\cdot5\cdot7,

infinite? Erdős Problems #376 On a conjecture of Graham on the p-divisibility of central binomial coefficients (2022 preprint)

Background

Known as Graham's problem, the question has a useful digit interpretation. Kummer's theorem identifies the exponent of a prime pp in (2nn)\binom{2n}{n} with the number of carries when adding nn to itself in base pp. Thus p∤(2nn)p\nmid\binom{2n}{n} exactly when every base-pp digit of nn is less than p/2p/2. For the three primes in the question, this requires digits only from {0,1}\{0,1\} in base 33, from {0,1,2}\{0,1,2\} in base 55, and from {0,1,2,3}\{0,1,2,3\} in base 77. Erdős Problems #376 On a conjecture of Graham on the p-divisibility of central binomial coefficients (2022 preprint)

Pomerance's heuristic treats these three digit restrictions as independent for a random integer up to xx. The estimated probabilities are approximately x−0.37x^{-0.37}, x−0.32x^{-0.32}, and x−0.29x^{-0.29}, respectively, suggesting roughly x0.02x^{0.02} simultaneous solutions up to xx. This is a heuristic based on an independence assumption, not a proof of infinitude. On a conjecture of Graham on the p-divisibility of central binomial coefficients (2022 preprint)

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.