It’s a great equation for pulling out of the bag when giving talks at IMO training camps on functional equations, partly because it is so simple and pops up reasonably often, but also because it teaches a valuable lesson to school children about functions: they aren’t always nice. However, we always wave our hands and say that there exist horrible solutions, and circumstantial evidence for this is that it seems like we can’t get any more information out of the equation than its value on the rationals (or a translation thereof). However, we are always a little wary of actually doing the construction, partly because it would be useless for the IMO, and partly because it in some sense isn’t really a construction at all – it requires Zorn’s lemma, and in some sense always will. That said, I think IMO trainees have a right to know what these solutions look like if they’re curious, so I thought I’d try putting an elementary explanation up here.

Firstly, recall that Cauchy’s equation is a property of functions from the reals to the reals, telling us that

for all .

An obvious guess is , which clearly works. However, we cannot deduce this **must** be the solution for all reals, but we can deduce, by a fairly routine induction argument, that for all *rational *.

These two properties taken together tell us that for every we have . If we consider the real numbers to be a set of *vectors *over the rationals, then this tells us that is a *linear map*. However, it is also clear that the converse holds, so in fact *any* linear map will satisfy both of these conditions and so satisfy the Cauchy equation.

Just to elaborate on what we mean by considering the real numbers to be vectors over the rationals, the standard vectors from A-level maths are usually vectors over the reals. We could represent a 3-dimensional vector by where are real numbers, and are fixed vectors which should be somehow considered as abstract objects with the properties that:

- The sum of any two vectors is a vector (and we can subtract vectors, there is a zero vector, and so on).
- If we multiply a vector by a
*scalar*(in this case a real number) we get another vector.

These two operations interact with one another in the obvious way. However, there’s no reason vectors have to represent arrows in space. Anything that obeys the above rules, regardless of its interpretation, can be considered as a ‘vector’. To see that the reals can be considered as vectors over the rationals, consider the set of numbers of the form . It is not tricky to prove that this behaves, for our purposes, just like the 3D real vector spaces from A-level maths. Sure, we can multiply real numbers together in a way we can’t multiply geometrical vectors, but this is a property we will ignore for now (except the multiplication in which one number is a rational number).

Bearing in mind the above example, it therefore isn’t a giant leap of intuition to consider the *entire* set of real numbers as a set of vectors over the rational numbers. There is one important potential area of confusion still unresolved though. In all the above examples, we were able to *expand* any vector out and write it uniquely as a (finite) linear combination of other vectors (e.g. ). A collection with this property, like is called a *basis* for the vector space. If you spend a while trying to build a basis for the reals over the rationals, it soon becomes clear that it’s going to have to be pretty big. In fact, you don’t have to think too hard before you find an infinitely large collection of real numbers where none can be written in terms of the others (so the basis is going to have to be infinite). It isn’t at all obvious that a basis even exists.

However, fortunately, one can prove using Zorn’s Lemma that a basis always exists (in fact, even better, we can *extend* any set of vectors that aren’t expressible in terms of each other to form a basis). A statement and sketch proof of Zorn can be found elsewhere on my blog, as can the proof that every vector space has a basis. A basis for the reals over the rationals is often called a *Hamel basis*.

Now we have a basis, it is easy to construct linear maps. In general, a linear map can be thought of as any ‘square matrix’ (which in the case of the reals over the rationals will have infinite size). A more useful definition is that given above, that it satisfies the equation . Given our basis (where is some indexing set and could be larger than ) it is clear that any *permutation* of the basis is a linear map (and will hence satisfy Cauchy’s equation).

To make this concrete, let’s consider a simple example. Suppose, for simplicity, we only care for now about numbers of the form (where are rationals). We define (a linear map obtained by a permutation of the basis).

One the one hand it is simple to check that if then . I.e. this function does satisfy the Cauchy equation. But on the other hand consider (which is a very small number). which is very large (and it is clear that by taking better and better rational approximations to one can get arbitrarily large values of arbitrarily close to zero). So is a decidedely bizarre function, but it does satisfy the Cauchy equation (and it is easy to see that, given a Hamel basis, it can be extended to the entire set of real numbers by just fixing everything else in the basis).

## 2 comments

Comments feed for this article

September 17, 2009 at 10:33 pm

tloveringPerhaps it’s worth remarking for readers with a knowledge of basic undergraduate algebra that it is clear exactly the same proof will run if we consider Cauchy’s equation over an arbitrary field (or any vector space thereof) and tell us that the solution set is precisely the set of linear maps of considered as a vector space over , the prime field of (that generated just by the element 1 and the operations of addition, subtraction, multiplication and division).

January 27, 2010 at 9:49 am

Sune Kristian JakobsenAbout a month ago I wrote some notes about how wild non-linear solutions to Cauchy’ functional equations are (6 pages, but unfortunately in Danish. I might translate them if someone is very interested). One fact that is easy to prove is that the graph, of a non-linear solution must be dense in :

Since f is non-linear there exist such that and are linearly independent. Because f is a solution to Cauchy’s functional equation, any linear combination over the rationals of these two vectors must be in the graph, and because they are linearly independent, any point in the plane is a linear combination over the reals of these two. But any linear combination of reals can be approximated by linear combinations over the rationals, so the graph is dense in the plane.

It is even possible to prove this much stronger fact: If B is a open interval and A a subset of R with positive measure, then is non-empty!

If you chose f carefully, you can get even wilder functions: There exist solutions to Cauchy’s functional equation that intersects any continuous function on every open interval (in fact on any set with positive measure).