On representing some real numbers exactly

There are uncountably many real numbers, and only countably many finite strings of symbols, so we know for sure that there is no scheme to represent all real numbers as finite strings of symbols in such a way that different reals get different representations. However, there are useful subsets of the real numbers that *are* equipped with finite encoding schemes. I hope to give some examples of such sets, including one, the set of periods, that isn't currently well known outside the mathematical world.

It's traditional to think of the real numbers as divided up into three types of number: the rational numbers, the algebraic numbers, and the leftovers known collectively as the transcendental numbers. If you're not familiar with those terms I'll be explaining them below. We can represent this as follows:

ℚ⊂A⊂ℝ

I'm using unicode for blackboard bold R and Q there. I hope your browser supports them. ℝ is the set of real numbers, ℚ is the set of rational numbers, and A is the algebraic numbers.

But there are many different kinds of transcendental number in existence, so the subject of this article will be three more levels of classification we could insert between the set of algebraic numbers and the set of real numbers in the sequence above.

But first, let's revisit ℚ and A.

The Rational Numbers, ℚ
The rational numbers are fairly straightforward to deal with. They are nothing more than the ratios of integers. Given two such ratios we can easily compare them to see whether they are equal. For example, we're taught at a young age how to tell if 2/3 is the same as 4/6.

However, it didn't take long for the Ancient Greeks to realise that they had some equations they could solve approximately using rationals, but couldn't solve exactly. The best known example is solving x²=2.

Assume x is rational, so that x=p/q, with p and q integers with highest factors cancelled out. We have p²=2q², and so p must be divisible by 2. But then p² is divisible by 4, and so q is divisible by 2. This means that we can cancel 2 from the top and bottom of p/q. That contradicts our assumption about cancellation. So the equation has no rational solution.

If we expect x²=2 to have a solution we must work with numbers that can't be represented as fractions.

Notice how the rational numbers come equipped with a notation to describe them. We can just write one integer over another, with a horizontal line between them. Given such a description we can immediately tell if it's valid (it's only invalid if the denominator is 0) and whether it equals some other rational number.

One interesting property of the rational numbers is that they are *dense* in the real numbers. This is just another way of saying that any real number can be approximated as well as we like by a rational number. For example, we can approximate √2 to within 1/1000 by the rational number 141421/10000. This is an important property that will come up again later.

We also know that there are only countably many rational numbers because there are only countably many pairs of integers.

The Real Algebraic Numbers, A
The real algebraic numbers are all the real numbers that we can obtain by finding roots of polynomial equations whose coefficients are rational numbers. For example, the real solutions to x⁵-2x²+½=0 are all algebraic numbers. Among other things, this includes the solution to x²=2 that wasn't contained in the rationals. The algebraic real numbers also include the solutions to "insoluble" algebraic equations. (By 'algebraic' equations, I just mean polynomial equations.) Even though Galois proved we can't write expressions for the solutions to all algebraic equations using the four arithmetic operations and nth roots, these solutions still exist in the real numbers, and they are all, by definition, algebraic numbers.

We can describe an algebraic number by writing down the equation it solves, and additionally providing some description to say which root of the equation we're interested in. Unfortunately, given any algebraic number there is always an infinite number of algebraic equations that it satisfies. So like with the rationals there is some redundancy. The good news, however, is that given two such descriptions of algebraic numbers there is an algorithm to tell whether or not they describe equal numbers.

Even though there are vastly more algebraic numbers than rational numbers, they still only form a countable set. As mentioned in the previous paragraph, every algebraic number can be described by a finite string of symbols, and there are only countably many such strings.

The Computable Real Numbers, C
Now I want to insert a set between A and ℝ. These are the computable real numbers. But first think back to what I said about the rational numbers.

Pick a real number x. Given any ε we can always find a rational number that comes within ε of x. We can define a function f on the rationals with the property that f(ε) is rational and within ε of x for any rational ε. So f gives rational approximations to x to any desired accuracy. Such a function uniquely specifies x. In fact x is the limit of f(ε) as ε tends to zero. The computable real numbers are the real numbers specified in this way by *computable* functions. Notice how there are no infinities involved here. A computable real number is represented by nothing more than a finite string of symbols forming a computer program that processes finite integers. We can find out what the real number is to any desired accuracy in a finite time.

Because we can write computer programs to find roots of algebraic equations to any desired accuracy we know that the algebraic numbers are contained in the computables. So now we have:

ℚ⊂A ⊂C ⊂ℝ

Where I'm using C to represent the computables.

Almost any number we ever want to work with is computable. Whether it's √2, or π, or the value of some humongous integral that's appeared in your engineering problem, chances are there's an algorithm somewhere that can approximate it as accurately as you like, given enough CPU time and RAM.

Note that every computable is described by a finite string of symbols, and so the computables form a countable set.

There are some problems with computable numbers. Given two representations of computable numbers we have no way of telling whether or not they are equal. It's not just that this is hard to do. There simply is no algorithm to prove that the numbers are equal. The problem is that the two computer programs may give exactly the same approximations to every degree of accuracy down to a certain ε. But for higher accuracy they may give different results. We have no way of knowing in advance at what value of ε they'll start differing. And anyway, there simply is no algorithm for telling if two computer programs will always generate the same results. So paradoxically, testing the equality of two computable numbers is itself uncomputable.

Actually, the situation is much worse. We can't even tell if we have a valid representation of a computable real. In order to do that, we need to know that our computer program to generate approximations terminates. But solving that would solve the halting problem.

By the way, despite these issues this representation of computable real numbers as functions leads to practical ways to do arbitrary precision arithmetic on a computer in a way that gives us guaranteed bounds on the accuracy of our results.

From here we could go two ways. We could try to rein in our class of number to something more manageable. Or we could try to push further and try to find ways to represent real numbers that aren't even computable. Let's do the former first.

The Periods, P
The periods are an interesting class of real number that doesn't seem to be well known. The definition may be old, but it was only recently that they were being promoted in mathematical circles as an interesting thing to study. So I thought I'd contribute to their promotion.

Consider the number π. It arises straightforwardly in geometric problems. An example is computing the area of a circle. Back in the 18th century Lambert proved that it was irrational and in the 19th century Lindemann proved that it was transcendental. But in a sense the transcendental numbers are simply a rubbish heap into which the leftover numbers have been discarded. Can we get some kind of handle on at least some of these numbers in a way that puts π back on the map?

The real number π is the area of a unit circle. So it is the area of the region of the plane given by the equation x²+y²<1.



Here's a similar construction of another real number:



The area of that region is log(2). (Natural logarithm of course!) We can construct the logarithm of any positive rational number in a similar way. These are all transcendental numbers. But in a way they are nice transcendental numbers. They arise from considering areas of the plane described by straightforward algebraic inequalities. (As in the previous section, I'm using 'algebraic inequalities' to mean 'polynomial inequalities'.)

That suggests a class of real number: those numbers that can be represented as the volume of a region defined by a bunch of algebraic inequalities with rational coefficients. These are known as the periods. I'm talking about generalised volumes in n-dimensions, not just areas in the plane. Clearly π and log(2) are periods.

But does this representation solve the problem we had with computable numbers where we were unable to guarantee we could check the equality of two numbers? Now it gets interesting. The answer is: we don't know. It is conjectured that if we have the same number represented in two different ways as a period that we can transform one representation into another simply by using a small set of elementary operations. It is also conjectured that there is a terminating algorithm for finding such a sequence of operations, or if one doesn't exist, demonstrating this.

One obvious question now is this: are there any computable reals that aren't periods? A recent paper, Periods and elementary real numbers claims to exhibit one by means of a kind of diagonalisation argument. But in general it's hard to prove that a number isn't a period. I don't believe there is a proof yet that e = 2.718... isn't a period, but mathematicians expect that it isn't.

I think the name 'period' comes from the fact that the period of a pendulum of rational length, in a gravitational field of rational strength, is a period. Computing this requires elliptic functions, and these often result in periods when applied to rational numbers.

Although mathematics is about numbers, few mathematical publications talk much about specific real numbers. Curiously, when they do, they often talk about numbers that are periods. For example there have been many recent papers on the values of the Riemann zeta function for interesting arguments. These are often periods.

It has been suggested that the study of periods is actually the study of algebraic geometry in disguise. There is certainly no end to the interesting mathematics we can do using only periods.

We now have:

Q ⊂A ⊂P ⊂C ⊂R

The Definables
In the section on computable numbers I mentioned that we could go the other way and try to find a bigger class of real numbers that could be represented by finite strings of symbols. We could simply go "all the way" and consider those real numbers that can be defined, by any means possible, using the symbols of mathematics. We can try to pin this down a bit better. We'll work with the language of set theory. In this language we can write strings of symbols like S = "x>0 and x²=2". Such a string uniquely defines a real number if when we glue the string "there exists a unique x such that" onto the beginning of it we get a true proposition. We can now represent the number √2 as the string S.

It looks like we now have:

Q ⊂A ⊂P ⊂C ⊂D ⊂R

with D the set of definables.

Except there's a problem. The set D is not definable! The problem is this: we can talk about strings of symbols representing real numbers. To talk about these in set theory we'd encode these strings of symbols as sets so that we can apply the language of set theory. In order to use our attempted definition of definable we need some way to say when a string of symbols represents a true proposition. But to define a set of definables we need to talk about true propositions in the language of set theory. Godel showed us how to talk about the provability of a proposition within set theory. He did this by showing that provability is about mechanical operations we can perform on strings. But there's nothing analogous for talking about the truth of propositions. In fact, Tarski showed us this is impossible. So while we can talk about all kinds of individual numbers as being definable, we can't construct the set of definable numbers.

You may be interested to see an example of a definable number that isn't computable. Probably the most publicised example is Chaitin's constant. It represents the probability that a randomly generated string of symbols is a computer program that terminates in a finite time. We can't actually compute this number because it requires us to solve the halting problem. Nonetheless, it's perfectly well defined.

You can find the original paper on periods by Zagier and Kontsevich here. I first found out about periods from the book Mathematics Unlimited.

Update: Jared asked if I intended the real algebraic numbers. That's what I said in the text, but I confusingly wrote ℚ for this set. But that usually means the *complex* algebraic numbers. So I've changed notation and now use A for the real algebraic numbers.

Similarly, the periods are usually defined to be complex numbers whose real and imaginary parts are given by algebraically specified volumes. I was trying to avoid mention of the complex numbers to keep prerequisites to a minimum and the essential ideas here work without mention of the complex numbers.