All Random Solved Random Open
0 solved out of 3 shown
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$.
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.\]

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}$.