← All problems

Erdős Problem #698 — Growing common divisors of binomial coefficients

1 year old · traced to

For positive integers n,i,jn,i,j with 2≤i<j2\le i<j and j≤n/2j\le n/2, consider the greatest common divisor of the two binomial coefficients (ni)\binom{n}{i} and (nj)\binom{n}{j}. The question is whether there is a function h:N→Nh:\mathbb N\to\mathbb N tending to infinity such that, for every admissible triple (n,i,j)(n,i,j),

h(n)≤gcd⁡ ⁣((ni),(nj)).h(n)\le \gcd\!\left(\binom{n}{i},\binom{n}{j}\right).

Erdős Problems #698

Background

Erdős and Szekeres introduced the underlying common-divisor phenomenon in 1978. For equal-weight proper binomial coefficients, their result says that any two have a common divisor greater than 11. In the range considered here, an elementary identity relating the two coefficients to other binomial coefficients also gives the lower bound gcd⁡((ni),(nj))≥2i\gcd(\binom{n}{i},\binom{n}{j})\ge 2^i. This already grows when ii grows, but does not provide a bound tending to infinity with nn when ii is fixed. Bergman (2011) Erdős and Szekeres (1978)

Bergman addressed this fixed-small-index difficulty in a paper on common divisors of multinomial coefficients. His argument counts the orbits of pairs of subsets under permutations of an nn-element set. The orbit sizes are multinomial coefficients divisible by the least common multiple of (ni)\binom{n}{i} and (nj)\binom{n}{j}. Comparing several of these sizes gives an upper bound on that least common multiple, and hence a stronger lower bound on the greatest common divisor. Bergman (2011)

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.