SOLVED

Show that, for any $n\geq 5$, the binomial coefficient $\binom{2n}{n}$ is not squarefree.

It is easy to see that $4\mid \binom{2n}{n}$ except when $n=2^k$, and hence it suffices to prove this when $n$ is a power of $2$.

Proved by Sárkzözy [Sa85] for all sufficiently large $n$, and by Granville and Ramaré [GrRa96] for all $n\geq 5$.

More generally, if $f(n)$ is the largest integer such that, for some prime $p$, we have $p^{f(n)}$ dividing $\binom{2n}{n}$, then $f(n)$ should tend to infinity with $n$. Can one even disprove that $f(n)\gg \log n$?

OPEN

Are there infinitely many $n$ such that $\binom{2n}{n}$ is coprime to $105$?

OPEN

Is there some absolute constant $C>0$ such that
\[\sum_{p\leq n}1_{p\nmid \binom{2n}{n}}\frac{1}{p}\leq C\]
for all $n$?

A question of Erdős, Graham, Ruzsa, and Straus [EGRS75], who proved that if $f(n)$ is the sum in question then
\[\lim_{x\to \infty}\frac{1}{x}\sum_{n\leq x}f(n) = \sum_{k=2}^\infty \frac{\log k}{2^k}=\gamma_0\]
and
\[\lim_{x\to \infty}\frac{1}{x}\sum_{n\leq x}f(n)^2 = \gamma_0^2,\]
so that for almost all integers $f(m)=\gamma_0+o(1)$. They also prove that, for all large $n$,
\[f(n) \leq c\log\log n\]
for some constant $c<1$. (It is trivial from Mertens estimates that $f(n)\leq (1+o(1))\log\log n$.)

A positive answer would imply that \[\sum_{p\leq n}1_{p\mid \binom{2n}{n}}\frac{1}{p}=(1-o(1))\log\log n,\] and Erdős, Graham, Ruzsa, and Straus say there is 'no doubt' this latter claim is true.

OPEN

Let $r\geq 0$. Does the density of integers $n$ for which $\binom{n}{k}$ is squarefree for at least $r$ values of $1\leq k<n$ exist? Is this density $>0$?

Erdős and Graham state they can prove that, for $k$ fixed and large, the density of $n$ such that $\binom{n}{k}$ is squarefree is $o_k(1)$. They can also prove that there are infinitely many $n$ such that $\binom{n}{k}$ is not squarefree for $1\leq k<n$, and expect that the density of such $n$ is positive.

OPEN

Let $S(n)$ denote the largest integer such that, for all $1\leq k<n$, the binomial coefficient $\binom{n}{k}$ is divisible by $p^{S(n)}$ for some prime $p$ (depending on $k$). Is it true that
\[\limsup S(n)=\infty?\]

If $s(n)$ denotes the largest integer such that $\binom{n}{k}$ is divisible by $p^{s(n)}$ for some prime $p$ for at least one $1\leq k<n$ then it is easy to see that $s(n)\to \infty$ as $n\to \infty$ (and in fact that $s(n) \asymp \log n$).

SOLVED

If $1<k<n-1$ then $\binom{n}{k}$ is divisible by a prime $p<n/2$ (except $\binom{7}{3}=5\cdot 7$).

A conjecture of Erdős and Selfridge. Proved by Ecklund [Ec69], who made the stronger conjecture that whenever $n>k^2$ the binomial coefficient $\binom{n}{k}$ is divisible by a prime $p<n/k$. They have proved the weaker inequality $p\ll n/k^c$ for some constant $c>0$.

OPEN

Can $\binom{n}{k}$ be the product of consecutive primes infinitely often? For example
\[\binom{21}{2}=2\cdot 3\cdot 5\cdot 7.\]

Erdős and Graham write that 'a proof that this cannot happen infinitely often for $\binom{n}{2}$ seems hopeless; probably this can never happen for $\binom{n}{k}$ if $3\leq k\leq n-3$.'

OPEN

Is there an absolute constant $c>0$ such that, for all $1\leq k< n$, the binomial coefficient $\binom{n}{k}$ has a divisor in $(cn,n]$?

Erdős once conjectured that $\binom{n}{k}$ must always have a divisor in $(n-k,n]$, but this was disproved by Schinzel and Erdős [Sc58].

OPEN

Is it true that for every $k$ there exists $n$ such that
\[\prod_{0\leq i\leq k}(n-i) \mid \binom{2n}{n}?\]

Erdős and Graham write that $n+1$ always divides $\binom{2n}{n}$ (indeed $\frac{1}{n+1}\binom{2n}{n}$ is the $n$th Catalan number), but it is quite rare that $n$ divides $\binom{2n}{n}$.

Pomerance [Po14] has shown that for any $k\geq 0$ there are infinitely many $n$ such that $n-k\mid\binom{2n}{n}$, although the set of such $n$ has upper density $<1/3$. Pomerance also shows that the set of $n$ such that \[\prod_{1\leq i\leq k}(n+i)\mid \binom{2n}{n}\] has density $1$.

The smallest $n$ for each $k$ are listed as A375077 on the OEIS.

OPEN

Is it true that for every $0\leq k\leq n$ the largest prime divisor of $\binom{n}{k}$ is
\[> \min(n-k+1, k^{1+c})\]
for some constant $c>0$?

A theorem of Sylvester and Schur states that this is $>k$ if $k\leq n/2$. Erdős writes it 'seems certain' that this holds for every $c>0$, with only a finite number of exceptions (depending on $c$). Standard heuristics on prime gaps suggest that the largest prime divisor of $\binom{n}{k}$ is in fact
\[> \min(n-k+1, e^{c\sqrt{k}})\]
for some constant $c>0$.

OPEN

For $0\leq k\leq n$ write
\[\binom{n}{k} = uv\]
where the only primes dividing $u$ are in $[2,k]$ and the only primes dividing $v$ are in $(k,n]$.

Let $f(n)$ be the smallest $k$ such that $u>n^2$. Give bounds for $f(n)$.

A classical theorem of Mahler states that for any $\epsilon>0$ and integers $k$ and $l$ then, writing
\[(n+1)\cdots (n+k) = ab\]
where the only primes dividing $a$ are $\leq l$ and the only primes dividing $b$ are $>l$, we have $a < n^{1+\epsilon}$ for all sufficiently large (depending on $\epsilon,k,l$) $n$.

Mahler's theorem implies $f(n)\to \infty$ as $n\to \infty$, but is ineffective, and so gives no bounds on the growth of $f(n)$.

One can similarly ask for estimates on the smallest integer $f(n,k)$ such that if $m$ is the factor of $\binom{n}{k}$ containing all primes $\leq f(n,k)$ then $m > n^2$.

OPEN

Let $\epsilon>0$ and $n$ be large depending on $\epsilon$. Is it true that for all $n^\epsilon<k\leq n^{1-\epsilon}$ the number of distinct prime divisors of $\binom{n}{k}$ is
\[(1+o(1))k\sum_{k<p<n}\frac{1}{p}?\]
Or perhaps even when $k \geq (\log n)^c$?

It is trivial that the number of prime factors is
\[>\frac{\log \binom{n}{k}}{\log n},\]
and this inequality becomes (asymptotic) equality if $k>n^{1-o(1)}$.

OPEN

Is there some $h(n)\to \infty$ such that for all $2\leq i<j\leq n/2$
\[\textrm{gcd}\left( \binom{n}{i},\binom{n}{j}\right) \geq h(n)?\]

A problem of Erdős and Szekeres, who observed that
\[\textrm{gcd}\left( \binom{n}{i},\binom{n}{j}\right) \geq \frac{\binom{n}{i}}{\binom{j}{i}}\geq 2^i\]
(in particular the greatest common divisor is always $>1$). This inequality is sharp for $i=1$, $j=p$, and $n=2p$.

OPEN

Is it true that for every $1\leq i<j\leq n/2$ there exists some prime $p\geq i$ such that
\[p\mid \textrm{gcd}\left(\binom{n}{i}, \binom{n}{j}\right)?\]

A problem of Erdős and Szekeres. A theorem of Sylvester and Schur says that for any $1\leq i\leq n/2$ there exists some prime $p>i$ which divides $\binom{n}{i}$.

Erdős and Szekeres further conjectured that $p\geq i$ can be improved to $p>i$ except in a few special cases. In particular this fails when $i=2$ and $n$ being some particular powers of $2$. They also found some counterexamples when $i=3$, but only one counterexample when $i\geq 4$: \[\textrm{gcd}\left(\binom{28}{5},\binom{28}{14}\right)=2^3\cdot 3^3\cdot 5.\]

OPEN

Let
\[f(n)=\min_{1<j\leq n/2}\textrm{gcd}\left(n,\binom{n}{k}\right).\]

- Characterise those composite $n$ such that $f(n)=n/P(n)$, where $P(n)$ is the largest prime dividing $n$.
- Are there infinitely many composite $n$ such that $f(n)>n^{1/2}$?
- Is it true that, for every composite $n$, \[f(n) \ll_A \frac{n}{(\log n)^A}\] for every $A>0$?

A problem of Erdős and Szekeres. It is easy to see that $f(n)\leq n/P(n)$ for composite $n$, since if $j=p^k$ where $p^k\mid n$ and $p^{k+1}\nmid n$ then $\textrm{gcd}\left(n,\binom{n}{k}\right)=n/p^k$. This implies
\[f(n) \leq (1+o(1))\frac{n}{\log n}.\]

It is known that $f(n)=n/P(n)$ when $n$ is the product of two primes. Another example is $n=30$.

For the second problem, it is easy to see that for any $n$ we have $f(n)\geq p(n)$, where $p(n)$ is the smallest prime dividing $n$, and hence there are infinitely many $n$ (those $=p^2)$ such that $f(n)\geq n^{1/2}$.

OPEN

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?

A problem of Erdős, Graham, Ruzsa, and Straus [EGRS75], who believed there is 'no doubt' that the answer is yes.

For example $(87,88)$ and $(607,608)$.

Kummer's theorem implies that, for all odd primes $p$, $p\mid \binom{2n}{n}$ if and only some base $p$ digit of $n$ is $>p/2$, and hence $(n,n+1)$ has the required property if for all primes $p\leq n$ we have $n\not\in \{\frac{p-1}{2},p-1\}\pmod{p}$. Standard heuristics then predict there should be \[\gg \frac{x}{(\log x)^2}\] many such $n\leq x$.

OPEN

Is it true that, for every integer $t\geq 1$, there is some integer $a$ such that
\[\binom{n}{k}=a\]
(with $1\leq k\leq n/2$) has exactly $t$ solutions?

Erdős [Er96b] credits this to himself and Gordon 'many years ago', but it is more commonly known as Singmaster's conjecture. For $t=3$ one could take $a=120$, and for $t=4$ one could take $a=3003$. There are no known examples for $t\geq 5$.

Both Erdős and Singmaster believed the answer to this question is no, and in fact that there exists an absolute upper bound on the number of solutions.

Matomäki, Radziwill, Shao, Tao, and Teräväinen [MRSTT22] have proved that there are always at most two solutions if we restrict $k$ to \[k\geq \exp((\log n)^{2/3+\epsilon}),\] assuming $a$ is sufficiently large depending on $\epsilon>0$.