An upper bound for the G.C.D. of $\binom{a}{3}$ and $\binom{b}{3}$

Question

I can't seem to find anything in the literature on how to estimate the g.c.d. of $\binom{a}{k}$ and $\binom{b}{k}$. In particular, I would like to know why $\gcd(\binom{a}{3}, \binom{b}{3})\leq b \binom{a-b}{3}$ for $a-b\geq 4$. I'm confident it's true (computer search).

Answer 1

Here is a similar looking result.

Lemma. For any positive integers $a$ and $b$ satisfying $a-b\geq 2$, $$\gcd\left(\binom{a}{3}, \binom{b}{3}\right)\qquad\text{divides}\qquad (a+b-2)\binom{a-b+1}{3}.$$

Proof. The statement follows readily from the identity $$(2a-b-1)\binom{b}{3}-(2b-a-1)\binom{a}{3}\ =\ (a+b-2)\binom{a-b+1}{3}.$$

Answer 2

I will hopefully prove this statement below modulo a finite check (I believe this will also work to show that $\gcd(\binom{b}{3}, \binom{a}{3}) \le \varepsilon b(a-b)^3$ for any $\varepsilon > 0$ except for a finite set of counterexamples).

Denote for simplicity $a - b = c$ and $\gcd(\binom{b}{3}, \binom{a}{3}) = d$.

First we will show that $d \ll c^5$. Indeed, each divisor of $d$ comes from one of the pairs $(a-k, b - l)$, where $k, l = 0,1, 2$. Each such pair gives us as a contribution a divisor of $a - b + l - k$ and there are five such numbers from $a - b - 2$ to $a - b + 2$. Note also that (up to a finite number of divisors like extra $6$ or so) different pairs with the same $l - k$ will contribute to the different prime divisors of $a - b + l - k $ because it will otherwise divide $\gcd(a - k, a - k_1) | (k - k_1)$. So we get $\ll (a - b - 2)\ldots (a - b + 2) \ll c^5$.

Therefore, if $c \le \delta \sqrt{a}$, then we are done. Indeed, in that case $d \ll c^5 \le c^3\delta^2 a$ while $b\binom{c}{3} \asymp ac^3$. Thus, $c \ge \delta \sqrt{a}$ for some fixed positive $\delta$.

Now assume that $c \ge C a^{2/3}$ for big enough $C$. Then $b\binom{c}{3} \gg C^3ba^2 \gg C^3b^3$ which is bigger than $\binom{b}{3}$ for big enough $C$ and we are done (here we used the obvious fact that $d\le \binom{b}{3}$). So $c \le Ca^{2/3}$ for some fixed positive $C$. In particular, $c = o(a)$ so $b \sim a$.

Now we will use the ingenious observation of GH from MO that

$$(2a - b - 1)\binom{b}{3} - (2b - a - 1)\binom{a}{3} = (a + b - 2)\binom{c + 1}{3}.$$

Note that if $\gcd(2a-b-1, 2b - a - 1) \ge C$ then we are done. Indeed, in that case we can divide by this $\gcd$ and get that $d \ll \frac{(a+b-2)c^3}{C}$. Since now $a\sim b$ we get that this is $\ll \frac{bc^3}{C}$ which is what we need for big enough $C$ (being a bit more careful we can show that it is enough to consider cases with $\gcd(2a-b-1, 2b-a-1) \le 2$).

We have $$\gcd(2a-b-1, 2b - a - 1) = \gcd(2a-b-1, 3(a-b)) \ge \gcd(2a-b-1, a-b)=\\ =\gcd(a-1, a - b) =\gcd(a-1, b-1).$$

Thus, $a-1$ and $b-1$ are almost coprime.

Similar to the above computation we can get that (up to the division by some uniformly bounded number) $d = (a+b-2)\binom{c+1}{3}$. We have here four factors: $(c-1), c, c+1, a+b-2$.

$c-1$ can come from gcd of $a-1,b$ or gcd of $a-2, b-1$.

$c$ can come from gcd of $a, b$; $a-2, b-2$ or $a-1, b-1$, but the last case can be excluded since $\gcd(a-1, b-1) \le C$.

$c + 1$ can come from gcd of $a, b-1$ or gcd of $a-1, b-2$.

Finally, $a+b-2$ can come from gcd of $a, b-2$; $a-2, b$ or $a-1, b-1$, but the last case we can again exclude.

Assume that $c-1$ splits between gcd of $a-1, b$ and gcd of $a-2, b-1$ as $r_1$ and $s_1$. Similarly for the next ones we would have $r_2, s_2$, $r_3, s_3$ and $r_4, s_4$.

Observe that different numbers among $r_1, \ldots , s_4$ corresponding to the same number among $a, a-1, a-2, b, b-1, b-2$ will be almost coprime in a sense that their $gcd$ is at most some constant (for $r_1, \ldots , s_3$ it is obvious because $c-k, c-l$ are almost coprime and with $r_4, s_4$ e.g. when we look at $r_1$ and $s_4$ corresponding to $b$ we have $\gcd(r_1, s_4) \mid \gcd(a-b-1, b, a+b-2) = 1$. Other cases are similar).

Note that $r_1s_1 \sim r_2s_2 \sim r_3s_3 \sim c$ and $r_4s_4 \sim a$.

Let's look at the numbers $b, b-2, a, a-2$:

For $b$ we have by almost coprimeness $r_1r_2s_4 \ll a$,

For $b-2$ we have $s_2s_3r_4 \ll a$,

For $a$ we have $r_2r_3r_4 \ll a$,

For $a-2$ we have $s_1s_2s_4 \ll a$.

Multiplying these inequalities we get $c^4a^2 \ll a^4$, that is $c \ll \sqrt{a}$.

So, after all this reasoning, we got that $\sqrt{a} \ll c \ll \sqrt{a}$ so $c\sim \sqrt{a}$! I guess one can reach the same conclusion from the assumption $d \ll \varepsilon b\binom{c}{3}$.

Now, we have two numbers which are (almost) divisible by our gcd: $\binom{c+2}{5}$ and $(a+b-2)\binom{c+1}{3}$. Note that both of them are proportional to the required $b\binom{c}{3}$. Thus, they are almost the same in a sense that $n\binom{c+2}{5} = m(a+b-2)\binom{c+1}{3}$ for some integers $n, m \le C$. Dividing by $\binom{c+1}{3}$ we get $r(c+2)(c-2) = (a+b-2)$ for some $r\in \mathbb{Q}$, $r > 0$ with bounded denominator and numerator. So $a$ and $b$ are some second degree polynomials of $c$:

$$a = \frac{r(c+2)(c-2) + c + 2}{2}, b = \frac{r(c+2)(c-2)-c+2}{2}.$$

Therefore $\binom{a}{3}$ and $\binom{b}{3}$ are polynomials of degree $6$ in $c$. It remains to show that their $\gcd$ (as polynomials in $\mathbb{Q}[x]$) has degree at most $4$ – in that case $\gcd(\binom{a}{3}, \binom{b}{3}) \ll c^4$ while $b\binom{c}{3} \sim c^5$.

Since $\binom{a}{3}$ is a product of three quadratic polynomials, if $\gcd$ has degree at least $5$ then all factors should be used, in particular $a-1 = \frac{r(c+2)(c-2) + c}{2}$. If it is not coprime to some $b-k$ then their $\gcd$ divides their difference which is $\frac{2c + 2k - 2}{2}$. Thus, $c = 1 - k$ is a root of $a-1$ for $k = 0$, $k = 1$ or $k = 2$. Case $c = 0$ gives us $r = 0$, $c = -1$ gives us $r = -\frac{1}{3}$ and $c = 1$ gives us $r = \frac{1}{3}$. In all three cases the degree of gcd is at most $4$ and the proof is complete.