Which roots refuse to be fractions

The square that cannot shrink settles one number. Its argument is a descent — assume $\sqrt2$ is a fraction, produce a smaller one with the same property, and observe that the whole numbers do not allow an endless supply of smaller whole numbers.

That argument is beautiful and it is also stubbornly single-purpose. Adapting it to $\sqrt3$ takes work; adapting it to $\sqrt[3]{2}$ takes more. What is wanted is a rule that decides the whole family at once, and there is one, and the surprise is how little it needs.

Turning it into a question about polynomials #

Write the question as an equation rather than as a root. Asking whether $\sqrt{n}$ is a fraction is asking whether

$$x^2 - n = 0$$

has a rational solution. That looks like no progress at all, and it is the whole of the progress, because equations with whole-number coefficients have a property that square roots do not obviously have.

The rational root theorem. If a polynomial with whole-number coefficients has a rational root $p/q$ in lowest terms, then $p$ divides the constant term and $q$ divides the leading coefficient.

The proof is three lines. Substitute $p/q$ into $a_d x^d + \dots + a_0 = 0$ and multiply through by $q^d$:

$$a_d p^d + a_{d-1}p^{d-1}q + \dots + a_0 q^d = 0.$$

Every term after the first has a factor of $q$, so $q$ divides $a_d p^d$; and $q$ shares no factor with $p$, so it shares none with $p^d$, so it divides $a_d$. Every term before the last has a factor of $p$, so $p$ divides $a_0 q^d$, so by the same argument $p$ divides $a_0$.

The step that is doing the work is the one about sharing no factors, and it is not free: it is unique factorisation, in the form that says a prime dividing a product divides one of the factors. Every proof in this essay rests on that theorem, and it is worth knowing which brick is load-bearing.

What that gives for a square root #

For $x^2 - n$ the leading coefficient is $1$. So $q$ divides $1$, which means $q = 1$, which means any rational root is a whole number.

That single sentence is the whole reduction. There was an infinity of fractions to check and now there is a finite list: the whole numbers dividing $n$. Try each, square it, and see.

• $n = 2$: candidates $1, 2$; squares $1, 4$; neither is $2$.
• $n = 3$: candidates $1, 3$; squares $1, 9$; neither is $3$.
• $n = 9$: candidates $1, 3, 9$; squares $1, 9, 81$; the second is $9$, so $\sqrt9 = 3$.

The figure runs that search on eight numbers at once. It also checks the answer a second way: for each $n$ it computes whether $n$ is a perfect square directly, and asserts that the search agrees. The two are the same question, which is exactly what the theorem says and exactly what a figure ought to demonstrate rather than assume.

A square root of a whole number is either a whole number or not a fraction at all. There is nothing in between, and the middle case that intuition wants — a root that is “nearly” rational, a fraction with a big denominator — does not exist.

The same answer read off a factorisation #

There is a second proof, and it is worth having because it says why the perfect squares are the exception rather than only that they are.

Every whole number above one factors into primes in exactly one way. Suppose $\sqrt{n} = p/q$ in lowest terms; then $n q^2 = p^2$. Look at the exponent of any single prime on each side. On the right it is even, being twice the exponent in $p$. On the left it is the exponent in $n$ plus an even number. So every prime’s exponent in $n$ is even, and a number all of whose prime exponents are even is a perfect square.

The two proofs are the same theorem and they answer different questions. The divisor search says no candidate works; the exponent argument says the candidates are the numbers whose prime exponents are all even, and those are the squares. The second is the one that would let a reader decide $\sqrt{1{,}000{,}000}$ without listing a single divisor.

It also makes the cube-root case obvious rather than a repetition: $\sqrt[3]{n}$ is rational exactly when every prime exponent in $n$ is a multiple of three, and $\sqrt[k]{n}$ exactly when every exponent is a multiple of $k$. The figure’s cube-root columns pass at eight and twenty-seven for precisely that reason — $2^3$ and $3^3$ — and at nothing else drawn.

Why the argument has to be this shape #

It is worth noticing what has and has not been proved, because the theorem is often quoted in a stronger form than it has.

The theorem does not say the polynomial has no root. $x^2 - 2$ has two perfectly good roots; it says nothing about them except that they are not fractions. Nor does it produce a root, or approximate one, or say anything about how close a fraction can get — that last question is answered elsewhere and answered differently.

What it does is convert a search over an infinite set into a search over a finite one, and the conversion is the only interesting step. Infinitely many fractions could solve the equation as far as anyone knew before; afterwards, only the divisors of $n$ could, and there are at most a few dozen of those for any $n$ a reader will meet.

That is the shape of a great many impossibility proofs: not an argument that no object exists, but an argument that if one existed it would be findable, followed by a search that fails. The cube that will not double is the same manoeuvre at greater length, and the search over divisors that decides whether a number is perfect is another.

The cube root, free of charge #

Nothing about the argument used the exponent two, so the same search decides cube roots.

The case $n = 2$ is the one with a history attached. $\sqrt[3]{2}$ is the side of a cube with twice the volume of a unit cube, which is the Delian problem — and this argument shows it is not a fraction in about four lines, where showing it is not constructible with compass and straightedge took two thousand years and a different subject.

The gap between those two facts is worth holding on to. Not a fraction is easy and not enough; the constructible numbers include $\sqrt2$, which is not a fraction either, so irrationality decides nothing about ruler-and-compass constructions. What decides them is the degree of the field extension, and that is a much later idea.

The general statement #

The theorem gives more than roots of whole numbers, and the general form is worth having because it is what makes algebraic number a usable notion.

Take any polynomial with whole-number coefficients whose leading coefficient is $1$ — a monic polynomial. Then $q = 1$, and every rational root is a whole number. So

$$x^3 - x - 1 = 0$$

has a rational root only if it is $\pm 1$, and neither works, so its real root is irrational. And

$$x^5 - x - 1 = 0$$

likewise. Any monic polynomial with whole-number coefficients and no whole-number root has only irrational roots, and testing for a whole-number root is a finite search over the divisors of the constant term.

The name for what has just been proved is integrality: a rational number that is a root of a monic whole-number polynomial is a whole number. It is one of those statements that sounds like a triviality and is a theorem, and it is the reason the whole numbers are the right notion of “integer” inside the rationals rather than an arbitrary choice.

Descent and divisors, side by side #

The two arguments prove overlapping things and it is worth being precise about which is stronger where.

Descent is geometric, it is visible on a page, and it says something the divisor argument does not: it exhibits the failure. Given any fraction claiming to be $\sqrt2$, it produces a smaller one, so it is a procedure rather than a decision. That is why it survives into settings where the divisor argument has nothing to say — Fermat’s descent for the equation $x^4 + y^4 = z^4$ is the same move, and there is no polynomial in one variable to apply a root theorem to.

The divisor search decides more cases with less work and it decides them uniformly. It handles every $n$, every exponent, and every monic polynomial, and its cost is the cost of listing divisors. What it gives up is the picture: nothing about the search suggests why the answer comes out the way it does, and the two-line proof that $q$ divides $1$ is the kind of step that convinces without illuminating.

Both rest on unique factorisation. The descent’s step needs “if $a^2$ is even then $a$ is even”, and the divisor search needs “a prime dividing a product divides a factor”. Those are the same theorem, and in a number system where it fails both arguments fail with it.

What a search that finishes is worth #

There is a habit of mind worth naming here, because it recurs across this site and it is the reason the divisor argument is the one to remember.

An impossibility is hard to demonstrate directly. No fraction squares to two quantifies over an infinite set, and no amount of checking settles it. What settles it is a reduction: an argument that any counterexample would have to be of a particular restricted shape, followed by an exhaustion of that shape. The infinity is dealt with by the reduction and the remainder by brute force.

The pattern is everywhere once it is looked for. Six people at a party reduces an infinity of colourings to a case analysis on one vertex. Why only five solids reduces an infinity of candidate polyhedra to a handful of angle sums, and then checks them. Every one of them has the same two halves, and the interesting half is always the reduction.

What makes this instance a good first example is that the reduction is three lines and the exhaustion is a list a reader can read. There is nowhere for the argument to hide, and the figure is the exhaustion printed in full rather than summarised — which is the site’s standing rule for a picture of an impossibility, and is the only honest one.

Where the answer changes #

The interesting test of any criterion is a case where it gives a different answer, and there is one nearby.

In the whole numbers, $\sqrt{n}$ is rational exactly when $n$ is a perfect square. In the ring $\mathbb{Z}[\sqrt{-5}]$, where $6 = 2 \times 3 = (1+\sqrt{-5})(1-\sqrt{-5})$ and factorisation is not unique, the analogous questions have different answers, and the reason is precisely the brick that has been removed.

Closer to home, the criterion changes if the leading coefficient is not one. $2x^2 - 1 = 0$ has roots $\pm 1/\sqrt2$, and the theorem allows a denominator dividing $2$ — so the candidates are $\pm 1, \pm 1/2$, four of them rather than two, and all four fail. The extra candidates are real work and the search still finishes.

And the criterion says nothing at all once the coefficients stop being whole numbers. $x^2 - \pi$ has an irrational root for a completely different reason, which is the next rung but one and needs an argument of a different kind entirely.

How many numbers this catches, and how few #

Every number this essay has ruled a fraction or ruled out is a root of a whole-number polynomial. Those numbers have a name — the algebraic numbers — and they include a great deal: every fraction, every root of every whole number, every number built from those by adding, multiplying and taking roots, and a good many that cannot be built that way at all.

It is tempting to conclude that a criterion covering so much covers nearly everything. It does not, and the direction of the error is worth stating now because the last rung of this ladder is about it: the algebraic numbers can be listed, and the real numbers cannot, so almost every real number is a root of no whole-number polynomial whatever. The rational root theorem has nothing to say about any of them, because there is no polynomial to apply it to.

That gap is the reason this ladder does not stop here. The criterion is complete for its own question and its own question turns out to be a narrow one — and the two numbers everyone wants to ask about, $e$ and $\pi$, are both outside it.

What the picture cannot show #

The figure shows a search that finished, and the reason it finished is not in the picture. That every candidate is a divisor is the theorem; the picture assumes it and lists the divisors, so a reader who does not already believe the reduction sees a suspiciously short list of things tried.

It cannot show the fractions that were ruled out, either, because there are infinitely many of them and that is the point. What the columns show is the residue after an infinite set was reduced to a finite one, and the reduction happened in the prose.

And it says nothing about how close those ruled-out fractions get. $99/70$ is $\sqrt2$ to four decimal places and the figure has no column for it; the search is about exactness and is completely blind to accuracy.

The rung above that asks about accuracy rather than exactness finds a different world, and finds it precisely by asking a question this one refuses to ask.

Where the ladder goes next #

Above: numbers that are not roots of any whole-number polynomial at all, which no divisor search can decide because there is no constant term to divide. The two classical cases, $e$ and $\pi$, each need an argument built for it, and both are squeezes rather than searches.

One debt this essay leaves. Unique factorisation is used twice and proved nowhere here; it has its own essay, and the dependence is worth stating rather than hiding, because the whole of this rung rests on it and the descent argument on the rung below does too.

What the reduction was #

An infinite question about fractions becomes a finite question about divisors, because a denominator has to divide the leading coefficient and the leading coefficient is one.

That is the sentence to carry. Everything else — the eight columns, the cube roots, the monic polynomials — is the same observation applied again, and the reason it feels like a trick the first time is that the infinity disappears in a single line and never comes back.