A Strange Inequality.

Today, while trying to prove a result for a preprint I'm working on, I got so frustrated that I played around with something else from that paper. I got an idea to get rid of something non-nice, namely I had an asymptotic bound for $g, n \to \infty$ , and wanted to drop the if possible. Of course, this is only possibe if and if $g \ge C n$ for some constant .

So I began working this out to see how far I could get. It is rather easy to translate the whole problem into a question on some integers. Namely, assume that is an integer, and we are given integers $1 \le n_1, \dots, n_s < n$ with $\gcd(n_1, \dots, n_s, n) = 1$ . Define the quantity $g(n_1, \dots, n_s)$ as

$\frac{\biggl(n - \gcd\biggl(n, \sum\limits_{i=1}^s n_i\biggr)\biggr) + \sum\limits_{i=1}^s (n - \gcd(n, n_i)) - 2 (n - 1)}{2}.$

One can show that this is always a non-negative integer. Now I claim that $g(n_1, \dots, n_s)$ is either 0, or $\ge \frac{1}{6} n$ .

Where does this strange expression comes from? Consider the function field $K = \C(x, y)$ over $\C$ defined by

$y^n = \prod_{i=1}^s (x - i)^{n_i}.$

(In fact, one can do this over any field whose characteristic is coprime to , and which has at least elements. Moreover, over an algebraically closed field , any function field extension which is cyclic of order , where is coprime to the characteristic of , can be written in this form, since this is a Kummer extension.) One can show that this equation is irreducibe if and only if $\gcd(n_1, \dots, n_s, n) = 1$ , and that the genus of this function field is given by $g(n_1, \dots, n_s)$ . This also explains why we must have that $g(n_1, \dots, n_s) \ge 0$ , since the genus is always a nonnegative integer.

Now we have a struggle: is it easier to show the claim using some Elementary Number Theory, or using some (advanced?) Algebraic Geometry (considering the geometric side) or Algebraic Number Theory (considering the function field side)? I don't have any idea how to use the latter two to prove this, but I found an elementary proof.

First, note that if $s \ge 5$ , or in case $n \ge 4$ and $n \nmid n_1 + \dots + n_s$ , at least five of the $n - \gcd(n, \bullet)$ terms must be $\ge \frac{n}{2}$ since $\bullet$ is not divisible by . Therefore, $g(n_1, \dots, n_s) \ge \frac{5 \cdot \tfrac{1}{2} n - 2 (n - 1)}{2} \ge \tfrac{1}{2} n$ .

Moreover, if $n \mid n_1 + \dots + n_s$ , we have $n_s \equiv -(n_1 + \dots + n_{s-1}) \pmod{n}$ , and therefore $1 = \gcd(n_1, \dots, n_s, n) = \gcd(n_1, \dots, n_{s-1}, n)$ and $\gcd(n, n_s) = \gcd(n, n_1 + \dots + n_{s-1})$ . Hence,

$g(n_1, \dots, n_s) = g(n_1, \dots, n_{s-1}).$

Therefore, it suffices to consider the case $n \nmid n_1 + \dots + n_s$ and $s \le 3$ .

For , note that $\gcd(n, n_1) = 1$ implies . Hence, there is nothing to show.

For , let me consider three cases.

$\gcd(n, n_1) = n/p$ for some prime ;
$\gcd(n, n_1) = n/p^2$ for some prime ;
$\gcd(n, n_1) = n/(p q)$ for two distinct prims .

In all three cases, one can show by analyzing several cases that the claim is true. Thus, we are only interested in the cases where no $\gcd(n, n_i)$ is of the form , , . Therefore, $\gcd(n, n_i) \le \frac{1}{12}$ for all . Since not all $\gcd(n, n_i)$ 's cannot be the same – this would contradict

$1 = \gcd(n_1, \dots, n_s, n) = \gcd(\gcd(n_1, n), \dots, \gcd(n_s, n))$

– we must have

$& (n - \gcd(n, n_1 + n_2)) + \sum_{i=1}^2 (n - \gcd(n, n_i)) - 2 (n - 1) \\ {}\ge{} & n - (\tfrac{1}{2} + \tfrac{1}{12} + \tfrac{1}{13}) n + 2 \ge \tfrac{1}{3} n + 2.$

Let me demonstrate how to do $\gcd(n, n_1) = n/p$ . (In fact, this case suffices if one does not wants the constant $\frac{1}{6}$ , but one is happy with the constant $\frac{1}{24}$ , since $1 - \frac{1}{4} - \frac{1}{6} - \frac{1}{2} = \frac{1}{12}$ .) Assume that $\gcd(n, n_1) = n/p$ for some prime . Since

$1 = \gcd(n_1, n_2, n) = \gcd(\gcd(n, n_1), \gcd(n, n_2) = \gcd(n/p, \gcd(n, n_2)),$

we must have $\gcd(n, n_2) \mid p$ , with $p^2 \nmid n$ in case $\gcd(n, n_2) = p$ . In both cases, we have $\gcd(n/p, n_1 + n_2) = 1$ .

In case $\gcd(n, n_2) = 1$ , $\gcd(n/p, n_1 + n_2) = 1$ implies $\gcd(n, n_1 + n_2) \mid p$ . Therefore, $\gcd(n, n_1) + \gcd(n, n_2) + \gcd(n, n_1 + n_2) \le n/p + 1 + p$ . In case $\gcd(n, n_2) = p$ , $\gcd(n/p, n_1 + n_2) = 1$ implies $\gcd(n, n_1 + n_2) = 1$ . Therefore, we also have

$\gcd(n, n_1) + \gcd(n, n_2) + \gcd(n, n_1 + n_2) \le n/p + p + 1.$

This yields

$& (n - \gcd(n, n_1 + n_2)) + \sum_{i=1}^2 (n - \gcd(n, n_i)) - 2 (n - 1) \\ {}\ge{} & n - (n/p + p + 1) + 2 = n \tfrac{p - 1}{p} - p + 1 \overset{!}{\ge} \tfrac{1}{3} n.$

The latter inequality is true if and only if

$n \ge \frac{3 p (p - 1)}{2 p - 3}.$

If we write , this translates to

$p \ge 3 \frac{k - 1}{2 k - 3};$

if $k \ge 2$ , $3 \frac{k - 1}{2 k - 3} \le 3$ , and if $k \ge 3$ , $3 \frac{k - 1}{2 k - 3} \le 2$ . Hence, the only cases were the above argument does not work are () and (, ).

In case , we must have and $n_2 \in \{ 1, 3 \}$ . In that case, $\gcd(n, n_1) + \gcd(n, n_2) + \gcd(n, n_1 + n_2) = 2 + 1 + 1 = 4$ , whence

$& (n - \gcd(n, n_1 + n_2)) + \sum_{i=1}^2 (n - \gcd(n, n_i)) - 2 (n - 1) \ {}={} & (4 - 1) + (4 - 2) + (4 - 1) - 2 (4 - 1) = 2 \ge \tfrac{1}{3} \cdot 4.$

In case , since we do by assumption $p \nmid n_1 + n_2$ , we obtain $\gcd(n, n_1) + \gcd(n, n_2) + \gcd(n, n_1 + n_2) = 1 + 1 + 1 = 3$ , whence

$(n - \gcd(n, n_1 + n_2)) + \sum_{i=1}^2 (n - \gcd(n, n_i)) - 2 (n - 1) = n - 1 \ge \tfrac{1}{3} n$

since $n \ge 3/2$ .

The cases $\gcd(n, n_1) = n / p^2$ and $\gcd(n, n_1) = n / (p q)$ are proven analogously, with a few more case distinctions.

So we are left with the case . Here, one can proceed in a similar, painful way. Or one increases the constant to $\frac{1}{12}$ , since we know that not all $\gcd(n, n_i)$ 's can be , whence one is at least $\le n/3$ . Hence,

$& (n - \gcd(n, n_1 + n_2)) + \sum_{i=1}^3 (n - \gcd(n, n_i)) - 2 (n - 1) \ {}\ge{} & 4 n - 3 \cdot \tfrac{1}{2} n - \tfrac{1}{3} n - 2 n + 2 = \tfrac{1}{6} n + 2,$

which yields the claim.

To sum everything up, we showed the following theorem:

Theorem.

Let be an integer, $s \ge 1$ , and $n_1, \dots, n_s \in \{ 1, \dots, n - 1 \}$ satisfy $\gcd(n_1, \dots, n_s, n) = 1$ . Then $g(n_1, \dots, n_s)$ , defined as

$\frac{\biggl(n - \gcd\biggl(n, \sum\limits_{i=1}^s n_i\biggr)\biggr) + \sum\limits_{i=1}^s (n - \gcd(n, n_i)) - 2 (n - 1)}{2},$

satisfies $g(n_1, \dots, n_s) \ge 0$ , and if it is strictly larger than zero,

$g(n_1, \dots, n_s) \ge \frac{1}{24} n.$

As mentioned, if one invests more work, one can actually show $g(n_1, \dots, n_s) \ge \frac{1}{6} n$ . For my preprint though, this is not worth the trouble.

Felix' Math Place

Focussed on, but not limited to Computational Number Theory

Comments.

About Me.

About This Blog.

Overview Pages.

Recent Posts.

Archives.

Impressum.

Data Protection.