6
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Cross-posted at MSE here. $\endgroup$ – RobPratt Feb 22 at 21:23
9
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Very nice! (Not quite directly helpful but I upvoted it anyway). $\endgroup$ – Wlod AA Feb 23 at 4:01
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.