Feeds:
Posts

## Square roots have no unexpected linear relationships

IMO medalist Iurie Boreico has an article in an issue of the Harvard College Mathematics Review about his favorite problem:

Let $n_1, ... n_k$ be distinct squarefree integers. Show that if $a_1, ... a_k \in \mathbb{Z}$ are not all zero, then the sum $S = a_1 \sqrt{n_1} + ... + a_k \sqrt{n_k}$ is nonzero.

In other words, the problem is to show that there are no “unexpected” linear relationships between the fractions $\sqrt{1}, \sqrt{2}, \sqrt{3}, \sqrt{5}, \sqrt{6}, ...$. This is one of those nice problems that justifies an intuition without being amenable to the obvious attacks. Iurie gives several ingenious Olympiad-style arguments, i.e. arguments that don’t require much machinery, including a clearly motivated argument that serves as a good way to motivate the definition of a Galois group.

Today I want to share a different argument that generalizes a simple argument for special cases, but it has the unfortunate property that in full generality it is severe overkill.

First of all, it may not be clear that the problem statement implies that numbers such as $\sqrt{2} + \sqrt{3}$ are irrational; it only implies that they are non-integer. However, it’s known that the sum of algebraic integers is again an algebraic integer, and it is also known, via the rational root theorem, that the only rational algebraic integers are the integers. (Even if you aren’t familiar with the proofs of these results, I would like to stress that they are straightforward compared to the results we’ll be citing by the end of this post!) So the problem statement does involve showing that a large class of sums that we expect to be irrational are in fact irrational.

The very simplest special case of this problem requires showing that $\sqrt{n}$ is irrational for $n$ a square-free integer. This is a well-known classical problem in number theory dating back to the Greeks; one can argue by contradiction and prime factorization, from the rational root theorem, or from the fact that $\sqrt{n}$ has a periodic continued fraction. The first argument is elementary, the first and second generalize readily to $k^{th}$ powers, but the third is my favorite; it is the basis of a certain proof you may have seen of the irrationality of $\sqrt{2}$ which disguises a proof of the identity

$\displaystyle \sqrt{2} = 1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + ...}}}$.

There is a fourth argument I would like to present, and it may seem silly at first: $\sqrt{2}$ cannot be an integer because $2$ is not a quadratic residue $\bmod 3$.

Why is this sufficient? Suppose $\sqrt{2} = k$ for some integer $k$. Then $2 = k^2$, which implies that $2 \equiv k^2 \bmod 3$, but checking $k = 0, 1, 2$ we readily see that this can’t occur; contradiction.

This is the seed of an important idea, which can be stated roughly as follows.

Important idea: Certain statements have the property that if they are true locally (i.e. modulo a prime), then they are true for the integers.

More precisely, we need the following result.

Proposition: Let $f(x)$ be a monic polynomial with integer coefficients. If $f(x) \bmod p$ is irreducible over $\mathbb{F}_p[x]$, then $f(x)$ is irreducible over $\mathbb{Z}[x]$. (The reverse implication does not hold in general.)

In other words, if an algebraic integer is “locally irrational,” then it must be irrational. This is the first conceptual ingredient of our proof.

Here’s the second. Suppose I want to prove that $\sqrt{2} + \sqrt{3}$ is irrational. I want to reduce this to a statement about the irrationality of a single square root, since I already know how to deal with that by finding a suitable prime (under the assumption that such a prime exists). So here’s the trick: find a prime such that $2$ is a quadratic residue, but $3$ isn’t!

Here’s how this works with $p = 7$. Suppose $\sqrt{2} + \sqrt{3} = k$ for some integer $k$. Since $\sqrt{2} \equiv \sqrt{9} \equiv \pm 3 \bmod 7$, this is equivalent to $3 = (k \pm 3)^2 \bmod 7$, but again checking $0^2, 1^2, ... 6^2$ (or using Euler’s criterion) we can readily verify that $3$ isn’t a quadratic residue $\bmod 7$; contradiction.

Problems of this sort were often given on my abstract algebra problem sets before we covered Galois theory. I think the intended solution was either to square (which, as Iurie mentions, stops working for sums of more than four square roots) or to show that the minimal polynomial is irreducible. But one of the easiest ways to show that a polynomial is irreducible is to show that it’s irreducible modulo a prime – this is the motivation behind Eisenstein’s criterion – and so we are led back to this idea anyway, which we can implement without actually computing the minimal polynomial.

On another problem set we were asked to show that $\sqrt[3]{5}$ was not an element of $\mathbb{Q}[ \sqrt[3]{2} ]$; since $\sqrt[3]{5}$ is an algebraic integer, this is equivalent to showing that $\sqrt[3]{5}$ isn’t of the form $a + b \sqrt[3]{2} + c \sqrt[3]{4}$ for integers $a, b, c$. (Well, up to the small problem that I don’t have a good proof that the ring of integers in $\mathbb{Q}[ \sqrt[3]{2} ]$ is $\mathbb{Z}[ \sqrt[3]{2} ]$, but for now I’ll take this as given.) The trick is to find a prime relative to which $2$ is a cubic residue, but $5$ isn’t. It turns out that $31$ is such a prime, since $\sqrt[3]{2} \equiv \sqrt[3]{64} \equiv 4 \bmod 31$ but

$5^{\frac{31-1}{3}} \equiv 5 \bmod 31$

(this is the cubic generalization of Euler’s criterion). So this “find a prime” method works well for specific cases, but I haven’t described a general way to find the magical primes we need. The intuition we want here is that numbers that are unrelated multiplicatively behave independently modulo various primes. So we need to prove a statement like the following.

Conjecture: Let $s_1, ... s_k$ be distinct primes. Then there exists an arbitrarily large prime $p$ relative to which $s_1, ... s_{k-1}$ are quadratic residues, but $s_k$ isn’t.

First let’s verify that this conjecture implies the desired result. Given a sum $c_1 \sqrt{n_1} + c_2 \sqrt{n_2} + ...$ of integer combinations of distinct squarefree integers that might be equal to zero, we’re going to induct on the number of distinct primes $k$ that appears in $n_1 n_2 ...$. Clearly the original problem statement is satisfied for $k = 1$. Now, any such sum can be written as a polynomial in some set $\sqrt{s_1}, ... \sqrt{s_k}$ of square roots of primes. The monomials of this polynomial are squarefree, i.e. the polynomial is linear in each variable, so we can write

$\displaystyle c_1 \sqrt{n_1} + ... = a + b \sqrt{s_k} = 0$

where $a, b$ are integer linear combinations of products of distinct elements of the set $\sqrt{s_1}, ... \sqrt{s_{k-1}}$ and $b$ is nonzero by the inductive hypothesis. Actually, the inductive hypothesis gives us something stronger, which is that all of the conjugates of $b$ are also nonzero, hence the minimal polynomial of $b$ has nonzero constant term, i.e. the norm of $b$ is nonzero.

This is important. Now we pick a prime $p$ satisfying the hypotheses of the conjecture such that $p$ does not divide this constant term (which is why we need $p$ to be arbitrarily large). Then any “reduction” of $b \bmod p$ is still nonzero and $s_k \equiv \left( - \frac{a}{b} \right)^2 \bmod p$ is a contradiction.

The hard part, of course, is proving the conjecture. I see no way to do it that doesn’t require the following two tools: quadratic reciprocity and Dirichlet’s theorem. Quadratic reciprocity is a gem of number theory; it not only validates the assumption that numbers behave independently modulo primes, but it makes the astonishing claim that whether a prime $q$ is a quadratic residue $\bmod p$ depends only on the residue class of $p \bmod 4q$. Dirichlet’s theorem is another validation of intuition: it lets us find arbitrarily large primes in arbitrary residue classes exactly like the ones we need for quadratic reciprocity.

Now for every $1 \le i \le k-1$ there exists a residue class $a_i \bmod 4s_i$ such that $s_i$ is a quadratic residue relative to primes in this residue class by quadratic reciprocity. There also exists a residue class $a_k \bmod 4s_k$ such that $s_k$ is not a quadratic residue relative to primes in this residue class, again by quadratic reciprocity. If we choose all the $a_i$ to be congruent $\bmod 4$ (and we can always do this), then by CRT there exists a residue class $a \bmod s$ such that $s_1, ... s_{k-1}$ are quadratic residues relative to primes in this residue class but $s_k$ isn’t. By Dirichlet’s theorem, this residue class contains arbitrarily large primes, and we’re done.

If that seemed like more work than was necessary to solve this problem, it probably was. But I think this argument is a good demonstration of the local perspective in number theory. It also suggests that it would be useful to understand higher-order reciprocity laws in order to generalize the proof to higher powers, but this leads into waters so deep they justify themselves as of independent interest.

### 7 Responses

1. on July 6, 2009 at 1:11 am | Reply the7new7ramanujan

hey, the proof of the first problem is pretty easy from elementary vector space arguments, right ?
… anyway it’s nice to see your blog, i’m also a student of math

• I’m not sure what you mean. Could you elaborate? Showing that square roots are linearly independent over $\mathbb{Q}$ can’t really be done without appealing to the specific number-theoretic properties in play in some form or other.

2. The start of a proof that the ring of integers in $Z[\sqrt[3]{2}]$ is as claimed:

Notice that the trace of an algebraic integer is an algebraic integer. A quick computation shows that $tr(a+b \sqrt[3]{2} + c \sqrt[3]{4})=3a$. So, if $z := a+b \sqrt[2]{2} + c \sqrt[3]{4}$ is an algebraic integer, then $tr(z) = 3a$, $tr(\sqrt[3]{2} z)=6b$ and $tr(\sqrt[3]{4} z)=6c$ are all integers.

Now, you just need to do local analyses at the primes 2 and 3. I have reasonably elegant ways of doing these, but nothing super-slick.

3. Very nice proof, I like it very much. If i had known it, i would have definitely put it in my expository article. I can think of another “find a prime” application in the proof of the Minkowski-Hasse Theorem (special cases for forms of order 4). And then you have some ISL problems I think.. but you usually hit the Dirichlet theorem.

4. What a coincidence! I made up this problem:

Given any n tuple of positive integers {a_i} find k such that {(a_i^k)+1} all have a common factor.

and I solved it with that conjecture in your post. I had the exact same proof for that conjecture as well. I really like this post of yours by the way.

5. [...] Comments Non-update « P… on Exceptional structuresAhwing on Square roots have no unexpecte…skipper hartley on Aboutiura on Square roots have no unexpecte…Qiaochu Yuan on [...]

6. [...] Qiaochu Yuan writes about Kraft’s inequality for prefix codes and the probabilistic method, and also on linear relationships between square roots. [...]