Erdős Problem #396

Erdős Problem 396: carry barriers and explicit certificates

Statement and outcome

Exact valuations and an exponential size barrier

For $p=2$, summing the binary expansion gives $v_2(n!)=n-s_2(n)$, where $s_2$ counts the one-bits. As $s_2(2n)=s_2(n)$, $1$ becomes $v_2\binom{2n}{n}=s_2(n)$. Since \[ D_k(n)=(k+1)!\binom n{k+1}, \] any witness must satisfy $s_2(n)\ge v_2((k+1)!)$. An integer with at least $r$ one-bits is at least $2^r-1$. Hence \[ n\ge2^{\,k+1-s_2(k+1)}-1. \tag{3} \] This is an exponential necessary lower bound up to a polynomial factor; it is not an existence construction.

If $n=p^a$ for an odd prime, $1$ is zero: for $j\le a$ the quotient $n/p^j$ is integral, and for $j>a$ one has $p^j>2n$. Thus even $n\mid\binom{2n}{n}$ fails. For $n=2^a$, its binary valuation is $1$, so only $a=1$ can work. Apart from $n=1$, the only prime-power witness for $k=0$ is therefore $n=2$.

A prime near the endpoint is impossible

An explicit proof for $k=2$ and further witnesses

Remaining gap

1) FORMAL RESTATEMENT

For integers $n\ge 1$ define the central binomial coefficient \[ \binom{2n}{n}=\frac{(2n)!}{(n!)^2}. \]

Fix an integer $k\ge 0$.

Question. Does there exist an integer $n\ge k+1$ such that \[ \prod_{i=0}^{k} (n-i) \mid \binom{2n}{n}? \] (We restrict to $n\ge k+1$ so the product is a nonzero integer.)

Edge cases. For $k=0$, the question is whether there exists $n$ with $n\mid\binom{2n}{n}$.

2) QUICK LITERATURE/CONTEXT CHECK

I do not claim any results beyond what the problem statement itself records.

The statement records: - $n+1\mid\binom{2n}{n}$ for all $n$ (Catalan integrality). - Pomerance proved: for each $k\ge 0$, infinitely many $n$ satisfy $(n-k)\mid\binom{2n}{n}$, but this set has upper density $<1/3$. - Pomerance also proved: for each fixed $k\ge 1$, the set of $n$ with $\prod_{1\le i\le k}(n+i)\mid\binom{2n}{n}$ has density $1$.

3) ATTACK PLAN

Proof-track (existential construction): - Rewrite the divisibility condition prime-by-prime using $p$-adic valuations (Legendre formula). - Try to choose $n$ with unusually large $v_p\!\left(\binom{2n}{n}\right)$ for small primes and controlled $v_p(n-i)$.

Disproof-track: - Try to find a specific small $k$ (e.g. $k=2$) where computation suggests impossibility, then attempt to prove impossibility via a $p$-adic obstruction.

Chosen path: derive exact $p$-adic criterion and compute small cases for $k=0,1,2$.

4) WORK

PHASE 1 — FAST REALITY CHECK (computed)

$1$ Solutions to $n\mid\binom{2n}{n}$ for $n\le 200$. By direct computation, the integers $n\le 200$ such that $n\mid\binom{2n}{n}$ are \[ 1,2,6,15,20,28,42,45,66,77,88,91,104,110,126,140,153,156,170,187,190. \]

$2$ Solutions to $n(n-1)\mid\binom{2n}{n}$ for $n\le 200$. By direct computation, the only $n\le 200$ satisfying $n(n-1)\mid\binom{2n}{n}$ is $n=2$.

$3$ For $k=2$, i.e. $n(n-1)(n-2)\mid\binom{2n}{n}$, there is no solution for $n\le 200$.

Lemma 1 (Catalan divisibility: $(n+1)\mid\binom{2n}{n}$). For every integer $n\ge 0$, \[ (n+1)\mid \binom{2n}{n}. \]

Proof. Consider the adjacent binomial coefficient \[ \binom{2n}{n+1}=\frac{(2n)!}{(n+1)!(n-1)!}. \] A direct ratio computation gives \[ \binom{2n}{n+1}=\binom{2n}{n}\cdot \frac{n}{n+1}. \] Rearranging, \[ \binom{2n}{n}-\binom{2n}{n+1}=\binom{2n}{n}\left(1-\frac{n}{n+1}\right)=\frac{1}{n+1}\binom{2n}{n}. \] The left-hand side is an integer difference of integers, hence is an integer. Therefore $\binom{2n}{n}/(n+1)$ is an integer, i.e. $(n+1)\mid\binom{2n}{n}$. $\square$

Lemma 2 ($p$-adic valuation formula and divisibility criterion). Let $p$ be prime and $n\ge 1$. Then \[ v_p\!\left(\binom{2n}{n}\right)=\sum_{j\ge 1}\left(\lfloor\tfrac{2n}{p^j}\rfloor-2\lfloor\tfrac{n}{p^j}\rfloor\right). \] Moreover, for fixed $k\ge 0$ and $n\ge k+1$, \[ \prod_{i=0}^{k}(n-i)\mid\binom{2n}{n} \] holds if and only if for every prime $p$, \[ \sum_{i=0}^{k} v_p(n-i)\le v_p\!\left(\binom{2n}{n}\right). \]

Proof. Legendre's formula for factorial valuations states \[ v_p(m!)=\sum_{j\ge 1}\lfloor\frac{m}{p^j}\rfloor. \] Applying this to $(2n)!$ and $n!$ gives \[ v_p\!\left(\binom{2n}{n}\right)=v_p((2n)!)-2v_p(n!) =\sum_{j\ge 1}\left(\lfloor\tfrac{2n}{p^j}\rfloor-2\lfloor\tfrac{n}{p^j}\rfloor\right). \]

For the divisibility criterion, note that for any nonzero integer $M$, $M\mid\binom{2n}{n}$ is equivalent to $v_p(M)\le v_p\!\left(\binom{2n}{n}\right)$ for all primes $p$. Here $M=\prod_{i=0}^k (n-i)$, and by additivity of $v_p$ on products, \[ v_p(M)=\sum_{i=0}^{k} v_p(n-i). \] This gives the equivalence. $\square$

Lemma 3 (prime obstruction for $k=0$ at $n=p$). If $p$ is an odd prime, then \[ p\nmid \binom{2p}{p}. \]

Proof. Work modulo $p$. First, for $1\le j\le p-1$, the binomial coefficient $\binom{p}{j}$ is divisible by $p$, because \[ \binom{p}{j}=\frac{p(p-1)\cdots(p-j+1)}{j!} \] has a factor of $p$ in the numerator and $j!$ is not divisible by $p$. Hence in the binomial expansion \[ (1+x)^p=\sum_{j=0}^p \binom{p}{j}x^j, \] all intermediate coefficients vanish mod $p$, so \[ (1+x)^p\equiv 1+x^p\pmod p. \] Squaring both sides yields \[ (1+x)^{2p}=\left((1+x)^p\right)^2\equiv (1+x^p)^2\equiv 1+2x^p+x^{2p}\pmod p. \] On the other hand, \[ (1+x)^{2p}=\sum_{j=0}^{2p}\binom{2p}{j}x^j. \] Comparing the coefficient of $x^p$ on both sides modulo $p$ gives \[ \binom{2p}{p}\equiv 2 \pmod p. \] Since $p$ is odd, $2\not\equiv 0\pmod p$, so $p\nmid \binom{2p}{p}$. $\square$

5) VERIFICATION

- Lemma 1: checked numerically for $n\le 200$ as part of the computation. - Lemma 2: The valuation identity is a direct consequence of Legendre's formula; the second statement is a standard equivalence between divisibility and prime-by-prime valuations. - Lemma 3: For $p=3$, the lemma predicts $3\nmid\binom{6}{3}=20$, which holds.

6) FINAL

UNRESOLVED

(i) Strongest fully proved partial result obtained here. - For all $n$, $(n+1)\mid\binom{2n}{n}$ (Lemma 1). - Exact prime-by-prime criterion (Lemma 2). - For odd primes $p$, $p\nmid\binom{2p}{p}$, so $n=p$ can never solve the $k=0$ case (Lemma 3). - Computation: for $k=2$ there is no solution with $n\le 200$; for $k=1$ only $n=2$ works up to $200$.

(ii) Exact first gap. Even the first genuinely new case $k=2$ (existence of some $n$ with $n(n-1)(n-2)\mid\binom{2n}{n}$) is not resolved by the arguments here.

(iii) Top 3 next moves (concrete targets). 1. Use Lemma 2 to search for $n$ where $v_p\!\left(\binom{2n}{n}\right)$ is unusually large for small primes $p$ while the product $\prod_{i=0}^k(n-i)$ has controlled $p$-adic size. 2. Try to leverage carry-counting interpretations of $v_p\!\left(\binom{2n}{n}\right)$ (equivalently, the sum formula in Lemma 2) to design $n$ with large valuations. 3. Extend computation to larger $n$ for small $k$ using a valuation-based check (avoiding huge integers) to search for a first example or to build evidence for a $k$-counterexample.

(iv) What a minimal counterexample would likely look like. A counterexample would be a smallest $k\ge 2$ such that for every $n\ge k+1$ there exists a prime $p$ with \[ \sum_{i=0}^{k} v_p(n-i) > v_p\!\left(\binom{2n}{n}\right). \] Such a $p$ would likely be a small prime that divides many of the consecutive factors $n,n-1,\dots,n-k$ with a larger total exponent than the central binomial coefficient can supply.