The Eudoxus reals

Let’s call a function $f : {\mathbb Z} \to {\mathbb Z}$ a near-endomorphism of $\mathbb Z$ if there is a constant $C>0$ such that $|f(a+b)-f(a)-f(b)| \leq C$ for all $a,b \in \mathbb Z$ . The set of near-endomorphisms of $\mathbb Z$ will be denoted by $N$ . We put an equivalence relation $\sim$ on $N$ by declaring that $f \sim g$ iff the function $f-g$ is bounded, and let ${\mathbb E}$ denote the set of equivalence classes.

It’s not difficult to show that defining $f+g$ in terms of pointwise addition and $f \cdot g$ in terms of composition of functions turns ${\mathbb E}$ into a commutative ring. And it turns out that this ring has a more familiar name… Before reading further, can you guess what it is?

When I first heard that ${\mathbb E}$ is isomorphic to the field of real numbers, I found it quite surprising. In this post, I’ll attempt to explain why this is true. I think that this description of the reals deserves to be better known!

Intuition

Before attempting a proof, let’s try to demystify the isomorphism ${\mathbb E} \cong {\mathbb R}$ . The idea is the following. First, we can identify a real number $a$ with the corresponding linear function $f_a : {\mathbb R} \to {\mathbb R}$ of slope $a$ defined by $x \mapsto ax$ . But note that we can also recover $a$ from the discretized function $g_a : {\mathbb Z} \to {\mathbb Z}$ defined by $n \mapsto [an]$ , since $a = \lim_{n \to \infty} \frac{[an]}{n}$ . The function $g_a$ is not additive, but it is nearly so: it belongs to the set $N$ of near-endomorphisms of ${\mathbb Z}$ defined above. Moreover, if we add a bounded function $h$ to $g_a$ the resulting function still satisfies $\lim_{n \to \infty} \frac{(g_a + h)(n)}{n} = a$ since $\lim_{n \to \infty} \frac{h(n)}{n} = 0$ . It turns out (and this is really the key point of the argument below) that every near-endomorphism of ${\mathbb Z}$ is equivalent to a function of the form $g_a$ . Moreover, it is not hard to see that $g_a(g_b(n)) - g_{ab}(n)$ is bounded as a function of $n$ . These facts together imply that the map $\lambda: {\mathbb E} \to {\mathbb R}$ defined by $\lambda(\bar{g}) = \lim_{n \to \infty} \frac{g(n)}{n}$ is an isomorphism of rings, where $\bar{g}$ denotes the equivalence class of $g$ .

Exercise: Show that, under the isomorphism $\lambda$ , the real number $\pi$ corresponds to the equivalence class of the function $g$ defined by $g(n) = \# \{ (a,b) \in {\mathbb Z} \; : \; a^2 + b^2 \leq n^2 \}$ .

Why ‘Eudoxus reals’?

In this paper by R.D. Arthan, he calls $\mathbb E$ the Eudoxus reals, and justifies the terminology in the following way. In Book 5 of Euclid’s “Elements”, Euclid writes:

Magnitudes are said to be in the same ratio, the first to the second and the third to the fourth, when, if any equimultiples whatever are taken of the first and third, and any equimultiples whatever of the second and fourth, the former equimultiples alike exceed, are alike equal to, or alike fall short of, the latter equimultiples respectively taken in corresponding order.

In modern language, Euclid is saying that $a/b = c/d$ iff for all natural numbers $m,n$ and all $* \in \{ >, =, < \}$ , the statements $ma * nb$ and $mc * nd$ are either both true or both false.

We now quote from Arthan:

“According to the commentary in Heath’s translation of the Elements, de Morgan gave an interesting rationale for this definition: imagine a fence with equally spaced railings in front of a colonnade of equally spaced columns:

Let the distance between the columns be $C$ and the distance between the railings be $R$ . If the construction is continued indefinitely, an observer can compare $C$ with $R$ to any degree of accuracy without making any measurements just by counting the columns and railings. For example, in the figure, the 6th railing lies between the 8th and 9th columns, so that $8C < 6R < 9C$ , which means that $R/C$ lies between $4/3$ and $3/2$ . If more precision were required, the observer might continue counting to find that the 25th railing lies between the 35th and 36th columns and conclude that $R/C$ lies between $7/5$ and $36/25$ .

This picture suggests a way of representing real numbers: construct the colonnade so that the distance $C$ between the columns is 1 and represent $R$ by the sequence of integers in which the m-th term, $R_m$ say, gives the number of columns to the left of or in line with the m-th railing in the figure. This sequence $R_m$ will represent $R$ . In the example in figure 1, the first few $R_m$ are 1,2,4,5,7,8,…. Since Euclid’s book V is generally believed to describe the work of Eudoxus, let us call the real numbers represented in this way the Eudoxus reals.”

A proof that ${\mathbb E} \cong {\mathbb R}$

Following this paper by Theo Grundhöfer, we prove that ${\mathbb E}$ and ${\mathbb R}$ are isomorphic as rings (and therefore as fields).

$(\star) \; \; \; |\frac{f(n)}{n} - \frac{f(m)}{m}| < (\frac{1}{n} + \frac{1}{m}) C$

for all $n,m \in {\mathbb N}$ .

Therefore $\{ \frac{f(n)}{n} \}_{n \in {\mathbb N}}$ is a Cauchy sequence, so it has a limit $\lambda(f)$ in ${\mathbb R}$ . The resulting map $\lambda : N \to {\mathbb R}$ is easily checked to be additive, and since $\lambda(g_a) = a$ it is also surjective. The kernel of $\lambda$ clearly contains the subgroup $B$ of bounded functions. We claim that the kernel is precisely $B$ .

To see this, note first that by letting $m$ tend to infinity in $(\star)$ and multiplying by $n$ we obtain

$(\star\star) \; \; \; |f(n) - n \lambda(f)| \leq C$

for all $n \in {\mathbb N}$ . If $\lambda(f) = 0$ , then $(\star\star)$ implies that $f$ is bounded on $\mathbb N$ . Since $f(n) + f(-n) \in B$ by the near-endomorphism property of $f$ , it follows that $f$ is bounded on all of ${\mathbb Z}$ as claimed. Thus $\lambda$ induces an isomorphism of additive groups $\lambda : {\mathbb E} = N/B \to {\mathbb R}$ .

It remains to show that $\lambda$ is multiplicative, i.e., that $\lambda(f \circ g) = \lambda(f) \lambda(g)$ for all $f,g \in N$ . This is clear if $\lambda(g) = 0$ , since in that case $g \in B$ and thus $f\circ g \in B$ as well. So we may assume that $\lambda(g) \neq 0$ . In this case, $(\star\star)$ shows that $\lim_{n \to \infty} g(n) = +\infty$ if $\lambda(g) > 0$ and $\lim_{n \to \infty} g(n) = -\infty$ if $\lambda(g) < 0$ . In the former case, we can write

$\lambda(f \circ g) = \lim_{n \to \infty} \frac{f(g(n))}{g(n)} \cdot \frac{g(n)}{n} = \lambda(f) \cdot \lambda(g)$

and we’re done. In the latter case, since $f(n) + f(-n)$ is bounded we have $\lim_{n \to \infty} \frac{f(-n)}{n} = -\lambda(f)$ and the result follows from a similar calculation. Q.E.D.

Constructing the real numbers

The proof we have just given presupposes the existence of the real numbers as a completion of ${\mathbb Q}$ . It is natural to wonder if one could define the real numbers as ${\mathbb E} = N/B$ and deduce from first principles that ${\mathbb E}$ is a complete ordered field, without referencing another construction of ${\mathbb R}$ . This can in fact be done; see the papers by Arthan and A’Campo.

Concluding remarks

(1) The triple $(R,+,\cdot)$ defined above is not quite a ring, since in general $f \circ (g+h) \neq f \circ g + f \circ h$ (it’s what’s called a near-ring). This is why we first defined the isomorphism $R/B \to {\mathbb R}$ at the level of abelian groups and then proved that it’s multiplicative. The distributive law does hold once we take the quotient by $B$ ; this can be proved directly but it also follows from the argument above.

(2) According to Arthan, the definition of the Eudoxus reals is due to Stephen Schanuel and dates back to the early 1980s. As Arthan writes, “He named the resulting development of the real numbers after Eudoxus, since it seemed to reflect the relationship between the discrete and the continuous apparent in the ancient theory of proportion. Schanuel communicated the idea to many people, but did not publish it.” It seems that the idea was independently discovered by Norbert A’Campo in 2003. In this paper, Ross Street mentions another independent discovery of the Eudoxus reals by Richard Lewis.

(3) The definition of ${\mathbb E}$ and the isomorphism $\lambda : {\mathbb E} \to {\mathbb R}$ are reminiscent of John Tate’s definition of the canonical height on an elliptic curve (and more generally the Call-Silverman construction of canonical heights attached to polarized dynamical systems).

(4) Steffen Kionke has shown that equivalence classes of near-endomorphisms, in the spirit of the Eudoxus reals, can be used to construct the completion of any field with respect to an absolute value.

(5) T.J.D. Hermans has explored various generalizations of the Eudoxus reals and proves some interesting results. Given an abelian group $A$ , define ${\rm QEnd}(A)$ to be the set of functions $f : A \to A$ such that $\{ f(a+b)-f(a)-f(b) \}_{a,b \in A}$ is finite modulo functions for which $\{ f(a) \}_{a \in A}$ is finite. When endowed with the operations of pointwise addition and composition. ${\rm QEnd}(A)$ becomes a ring. Hermans proves that ${\rm QEnd}({\mathbb Z}[1/p] / {\mathbb Z})$ is isomorphic to the field ${\mathbb Q}_p$ of $p$ -adic numbers, and ${\rm QEnd}({\mathbb Q})$ is isomorphic to the rational adèle ring ${\mathbb A}_{\mathbb Q}$ .