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

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).

• Cross-posted at MSE here. – RobPratt Feb 22 at 21:23

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

• Very nice! (Not quite directly helpful but I upvoted it anyway). – Wlod AA Feb 23 at 4:01

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.