A derivation of a proof by D. Zagier

A derivation of a proof by D. Zagier

In The American Mathematical Monthly (Vol. 97, Num. 2, Feb. 1990, p. 144), D. Zagier published a half-page article titled: "A One-Sentence Proof That Every Prime $p \equiv 1$ (mod 4) Is a Sum of Two Squares". The first sentence of the article is the proof in question, the second sentence reads: "This proof is a simplification of one due to Heath-Brown [...] (inspired, in turn, by a proof given by Liouville).".

I can understand that the author could not resist the temptation to cram his proof into a single sentence, but the sentence became long and he was forced to commit the sin of omission. The latter is compensated by explanatory information in the article's second paragraph. But even when this explanation is taken into account, the author still pulls a number of sizeable rabbits out of his hat. The purpose of this note is the removal of those rabbits.

we have to prove that (for suitable $p$ )

$$ (0) \quad (x, y): x ^ {2} + y ^ {2} = p. $$

For the general existence theorem $\langle \exists x::Q.x\rangle$ , there exist two radically different proof forms, viz. the "constructive" and the "nonconstructive" proof.

In a constructive proof, one constructs a value $w$ ,or designs an algorithm that constructs a value $w$ ,such that by virtue of its construction $W$ can be shown to satisfy Q ; in this context,such a $W$ is called a "witness".

In a nonconstructive proof, $\langle \exists x::Q.x\rangle$ is demonstrated without constructing a witness, typically by translating the demonstrandum into $\langle \underline{N} x::Q.x\rangle \neq 0$ , i.e. by proving the existence by means of a counting argument.

Constructive proofs have a number of potential attractions: they give more (viz. the witness), they can be simpler by avoiding the detour of the counting, and, finally, their design gives us the opportunity to draw on our experience in program construction. This time, however, that same experience suggests a nonconstructive proof that (0) can be solved, for a constructive proof

would via the witness effectively boil down to a factorization - in the complex plane - of $p$ since ${x}^{2} + {y}^{2} = \left( {x + {yi}}\right) \left( {x - {yi}}\right)$ ,and all factorization algorithms I know are non- constructive in the sense that they are no more than search algorithms that work equally well if there are no factorizations to be found. So I propose to pursue the demonstrandum in the form

$$ (1) \quad \begin{array}{l l} {\langle N (x, y) : x ^ {2} + y ^ {2} = p \rangle \neq 0} \ {*} \end{array} $$

In view of our demonstrum (1), we now focus our attention on the constant 0. What do we know about zero? Well, obviously $x + 0 = x$ and $x \cdot 0 = 0$ for all natural $x$ . For our current purpose - the question of how we can conclude difference from 0 - the multiplicative property of zero is more interesting. (Possibly, as the following calculation suggests, this is because the statement of the multiplicative property contains the constant 0 twice.) We observe

$$ \begin{array}{l} n = 0 \ \Rightarrow \quad {x \cdot 0 = 0 } \ \langle \forall x: x \cdot 0 = n \rangle \ \Rightarrow \quad {\mathrm {p r e d . c a l c .} } \ \langle \forall x: \langle \exists y: x \cdot y = n \rangle \ \end{array} $$

taking the contra-positive, we get

(2) $\left\langle {\exists x : \left\langle {\forall y : x \cdot y \neq n}\right\rangle }\right\rangle \Rightarrow n \neq 0\;\therefore$

i.e. we can conclude that $n$ differs from zero when we have found an $x$ that does not divide $n$ .

We now focus our attention for a while on one number being a divisor or a multiple of another one. This situation is closely related to periodicity, and a standard way of generating an eventually periodic sequence is by repeated application of an operator defined on a finite domain.

The main purpose of this section is to introduce a metaphor that enables us to discuss these matters in the terminology of directed graphs. The mathematical content of this section is simple and well-known; it was certainly known to Fermat, but I don't know in which terminology he dealt with it.

We consider a domain $S$ and functions $f$ and $g$ from $S$ to $S$ ; $x$ and $y$ range over the elements of $S$ . With function $f$ we associate a directed graph whose vertices are the elements of

S and in which $f \cdot x = y$ is captured by a directed edge from $x$ to $y$ ; if you allow me a pictorial representation in a formula, the metaphor is captured by the equivalence

(3) $f \cdot x = y \equiv \underset{x}{\underbrace{''}} - \underset{y}{\underbrace{''}}$

We have obviously

• in the graph representing a function, each vertex has exactly 1 outgoing edge.

Let $f$ be invertible, i.e. let there exist a function $g$ , such that for all $x, y$

$$ f \cdot x = y \equiv x = g \cdot y $$

i.e. the graph representing $g$ is obtained by inverting the direction of all edges in the graph for $f$ ; hence

• in the graph representing an invertible function, each vertex has exactly 1 in- coming edge.

Combining our last two findings and restricting ourselves to finite domains, we conclude

• the graph representing an invertible function on a finite domain consists of cycles, such that each vertex lies on one cycle: the cycles partition the domain.

• $\langle \exists n : n \geq 1 : \left\langle {\forall x : x = {f}^{n}x}\right\rangle \rangle$ ,in which the ex- ponent $n$ denotes $n$ -fold functional composi-tion; a witness for $n$ is the smallest common multiple of the lengths of the cycles occurring in the graph for $f$ .

Conversely, if we are given that, for some positive $p$ , $\left\langle {\forall x : x = f{P}_{ * }x}\right\rangle$ ,then - $f$ is invertible (since then

$$ f \cdot x = y \equiv x = f ^ {p - 1} \cdot y) $$

for finite domain, each cycle in the graph for $f$ has a length that divides $p$ .

The latter conclusion is of particular interest if the exponent $p$ is prime, since then the domain of $f$ is partitioned into (i) cycles of length $p$ , and (ii) cycles of length 1, i.e. fixpoints of $f$ . Consequently, the number of elements of $S$ and the number of fixpoints of $f$ differ by a multiple of $p$ .

(By constructing a suitable $f$ on a suitable domain, I thus proved for prime

$$ n ^ {p} \equiv n (\mod p) \quad i n E W D 7 4 0 $$

and ${\left( p - 1\right) }^{!} \equiv \left( {p - 1}\right) \left( {\;\operatorname{mod}\;p}\right)$ in ${EWD742}$ .

I am convinced that the device was known to

Piesre de Fermat.)

This theorem will be used below for the simplest case, viz. $p = 2$ . In that special case, viz. if $f^2 x = x$ for all $x$ , $x$ is called an "involution".

Remark. An alternative definition of an involution is: a function that is its own inverse; this definition, however, is less attractive because it does not invite the generalization from 2 to any positive integer. (End of Remark.)

That is, we shall use that for involu-tions on a finite domain, odd/evenness of the size of the domain equivaiaes add/even-ness of the number of fixpoints of the involution. We shall use the equivalence in both directions; calling the two involu-tions involved "inv0" and "inv1" and the common domain on which they are defined "s", we shall use the following structure

the number of fixpoints of inv0 differs from zero

$\Leftarrow$ the number of fixpoints of ${inv0}$ is odd $\Leftarrow$ the number of elements of $S$ is odd. $\Leftarrow$ the number of fixpoints of $\operatorname{inv1}$ is odd $\Leftarrow$ inv1 has exactly 1 fixpoint

After all these preliminaries, the time has come to return to our obligation of showing that equation (0) has a solution in natural num- bers. Our first observation is that, because $p$ is odd, one of the squares is odd while the other one is even; consequently, solvability of (0) is equivaient to solva- bility of

$\left( 4\right) \;\left( {x,y}\right) : {x}^{2} + 4{y}^{2} = p$

Remark The transition from (0) to (4) is primarily cosmetic; it is the simplest way of representing our choice that $x^{2}$ be the odd square. (End of Remark.)

In order to use the preceding, in parti- cular the way of showing the existence of fixpoints, for showing the existence of solutions of (4), we establish a one-to- one correspondence between the solutions of (4) and the fixpoints of an involution. For the construction of that involution we do something with which every compu- ing scientist is very familiar: replacing in a target relation -here (4)- something by a fresh variable. In more detail, there is a trivial one-to-one correspondence between the solutions of (4) and those of

$$ (x, y, z): x ^ {2} + 4 y ^ {2} = p \wedge y = z $$

which equation -thanks to Leibniz's Principle-

can be rewritten as

(5) $\left( {x,y,z}\right) : {x}^{2} + {4yz} = p\;w\;y = z$

Next we create a one-to-one correspondence between the solutions of (5) and fixpoints of an involution, which we call "inv0". The domain $S$ of inv0 consists of the natural solutions of

(6) $\left( {x,y,z}\right) : {x}^{2} + {4yz} = p$

so that the truth of the first conjunct of (5) holds for any fixpoint of inv0. Under ex- ploitation of (6)'s symmetry in y&z, we choose for inv0

(7) $(x, y, z) \mapsto (x, z, y)$ ,

whose fixpoints truthf y the second conjunct of (5) because $(x,y,z) = (x,z,y) \equiv y = z$ . Our obligation to show that (5) - and hence (4) - has a natural solution has thus been translated in our obligation to show that involution inv 0, as defined by (7) on S, has at least 1 fixpoint. Since domain S -the set of natural solutions of (6)- is rather obviously finite, our last obligation can be met by showing that S

contains an odd number of elements, and this we shall demonstrate by defining on $S$ an involution, called "inv1", which has exactly 1 fixpoint. The remainder of this note is devoted to the design of a suitable inv1.

Before starting the design of inv1, we investigate properties of the individual elements of $S$ , i.e. direct consequences for a natural triple $\left( {x,y,z}\right)$ that solves (6) for prime $p$ of the form $4{k} + 1$ . It so happens that here we only use

(i) $p$ is odd (ii) $p$ is not a square (note that $p = 1$ ) is excluded because 1 is not considered

a prime number)

Our first lemma is that for $\left( {x,y,z}\right) \in S$

(8) $x > 0 \land y > 0 \land z > 0$

$$ \begin{array}{l} \mathrm {P r o o f} \quad x > 0 \ \Leftrightarrow \quad {(x, y, z) \in S, \mathrm {h e n c e} x \mathrm {i s n a t u r a l} } \ x \mathrm {i s o d d} \ = {(\mathbf {x}, \mathbf {y}, z) \in S, h e n c e (6) } \ p \mathrm {i s o d d} \ = {(\cdot) } \ t r u e \ \end{array} $$

$$ \begin{array}{r l} & {y > 0 \land z > 0} \ {\Leftrightarrow} & {{(x, y, z) \in S ^ {\prime}, \mathrm {h e n c e} y, z \mathrm {a r e n a t u r a l} }} \end{array} $$

$$ \begin{array}{l} y \neq 0 \land z \neq 0 \ = {\mathrm {a r i t h m e t i c} } \ 4 y ^ {2} \neq 0 \ = {(\mathbf {x}, \mathbf {y}, z) \in S, h e n c e (6) } \ = \begin{array}{l} x ^ {2} \neq p \ {C } \end{array} \ \end{array} $$

$$ t r u e $$

$$ (E n d o f P r o o f) $$

Our next lemma - in the same vein - is

that for $\left( {x,y,z}\right) \in S$

$\left( 9\right) x \neq y - 2\;x \neq z - y$

Proof. $x \neq y - z\;x \neq z - y$

$$ \begin{array}{l} = {\mathrm {a r i t h m e t i c} } \ x ^ {2} \neq (y - z) ^ {2} \ = {\mathrm {a r i t h m e t i c} } \ x ^ {2} + 4 y z \neq (y + z) ^ {2} \ = {\left(x, y, z\right) \in S ^ {\prime}, h e n c e (6) } \ p \neq (y + z) ^ {2} \ = {i i } \ \end{array} $$

$$ t r u e $$

$$ (\mathrm {E n d o f} \mathit {P r o o f}). $$

Now are ready to embark on our design of invi , which should be an involution on S with a single fixpoint. To begin with, we ignore most of these requirements and concentrate our attention on the elab- orate (6): can we think of operators on

$\left( {x,y,z}\right)$ for which ${x}^{2} + {4yz} = p$ is an invariant, i.e. that transforms a solution of (6) in- to a solution of (6)?

In order that we look beyond invo (as given by (7)) we investigate operators

(10) $\left( {x,y,z}\right) \mapsto \left( {x + {\Delta x},y + {\Delta y},z + {\Delta z}}\right)$

in which $\Delta$ is not identically zero . Be- cause any solution to (6) has an odd value of $x$ ,we can confine our atten. tion to even $\Delta$ ; we do justice to this fact by parameterizing

(11) $\Delta x = {2b}$

The requirement that ${x}^{2} + {4yz} = p$ be an invariant of (10) now translates into

$$ \begin{array}{l} \Delta (x ^ {2} + 4 y z) = 0 \ = {\Delta - c a l c u l u s } \ \Delta (x ^ {2}) = - 4 \Delta (y z) \ = {\Delta - c a l c u l s } \ 2 \times (\Delta x) + (\Delta x) ^ {2} = - 4 \Delta (y z) \ = {(\mathbf {1 1}), a r i t h m e t i c } \ b \cdot (x + b) = - \Delta (y z) \ = {\Delta - c a l c u l u s } \ b \cdot (x + b) = - y \cdot \Delta z - z \cdot \Delta y - \Delta y \cdot \Delta z \ \end{array} $$

The simplest way of finding solutions is by eliminating 2 of the 3 products at

the right-hand side by choosing, say,

(12) ${\Delta y} = 0$

thus simplifying the relation between $b$ and ${\Delta z}$ to

(13) $b \cdot \left( {x + b}\right) = - y \cdot {\Delta z}$

Note Choice (12) can be made without loss of generality", that is, firstly, that the choice of $\Delta z = 0$ would not have given something essentially new since (6) is symmetric in $y$ and $z$ , and, secondly, that it is no restriction to change of the pair $(y,z)$ only one at a time: we can always combine two moves into a single one so as to achieve $\Delta y \neq 0$ and $\Delta z \neq 0$ . (End of Note)

I can think of only 4 ways of satisfying rela-tion (13). The derivations of the $i$ operators below have taken (11) and (12) into account:

$\therefore b = - y \land x + b = {\Delta z}$ yields

(14) $\left( {x,y,z}\right) \mapsto \left( {x - {2y},y,z + x - y}\right)$

$\therefore b = y\; \land x + b = - {\Delta z}\;y$ ields

(15) $\left( {x,y,z}\right) \mapsto \left( {x + {2y},y,z - x - y}\right)$ ;

$b = {\Delta z}\;w + b = - y\;y$ yields (after

solving b from the second conjunct)

(16) $\left( {x,y,z}\right) \mapsto \left( {-x - {2y},y,z - x - y}\right)$ ; - $b = - {\Delta z}\; \land x + b = y\;y$ ields (again a.f. $\left( {17}\right) \;\left( {x,y,z}\right) \mapsto \left( {{2y} - x,y,z + x - y}\right)$

Note that formulae (14) through (17), of the form

(18) $\left( {x,y,z}\right) \mapsto \left( {{x}^{\prime },{y}^{\prime },{z}^{\prime }}\right)$ are templates in the sense that, because of (6)'s symmetry in y and z, we are free to interchange y, and z, or to interchange y' and 2'. For instance, applying the first one to (15) would yield (19) $(x, y, z) \mapsto (x + 2z, z, y - x - z)$ , and applying the second one to (14) would yield $\left( {x,y,z}\right) \mapsto \left( {x - {2y},z + x - y,y}\right)$

Up till now, we have confined our attention to the invariance of (6). The next constraint to take into account is that $\mathcal{S}$ consists of the natural solutions of (6), i.e. we have to achieve the invariance of (8). This means that transformation (18)

is guarded by

$$ (2 1) \quad x ^ {\prime} > 0 \wedge y ^ {\prime} > 0 \wedge z ^ {\prime} > 0 $$

of the templates, (16) is identified by this requirement as useless, as it yields ${x}^{\prime } < 0$ (on account of (8)). This observation restricts our interest to templates

The time has come to remember that we are looking for an involution. inv1 on S with exactly 1 fixpoint , i.e. for which $(x,y,z) = (x',y',z')$ holds for exactly 1 triple. The subtarget $x = x'$ rules out (14) and (15) as $x = x'$ then implies $y = 0$ , which falsifies (8). Consequently, the requirement that a fixpoint exist focuses our attention on (17).

In the following we shall use that, for $(x_0,y_0,z_0)$ and $(x_1,y_1,z_1)$ points on domain $S$ ,

$$ x 0 = x 1 \equiv y 0 = y 1 \equiv z 0 = z 1 $$

which is a consequence of (6) and (8); as a result $\left( {{x0},{y0},{z0}}\right) = \left( {{x1},{y1},{z1}}\right)$ can be established by 2 of the 3 equalities.

Therefore, because under (17) we have $y = {y}^{\prime }$ , fixpoints of(17) are characterized by

$x = {x}^{\prime }$ , i.e. $x = {2y} - x$ or,equivalently, $x = y$ . Hence,for(x,y,z) a fixpoint of (17), we have on account of (6):

$$ x \cdot (x + 4 z) = p, $$

which guarantees for (17) the unique fix- point (1,1,k) if $p$ is a prime of the form $1 + {4k}$ . (The conclusion of the uniqueness of this fixpoint is the only use made of $p$ ’s primality.)

The next question is whether (17) is an involution, that is, with

$\left( {x,y,z}\right) \mapsto \left( {{x}^{\prime },{y}^{\prime },{z}^{\prime }}\right) \mapsto \left( {17}\right) \mapsto \left( {{x}^{\prime \prime },{y}^{\prime \prime },{z}^{\prime \prime }}\right)$ , holds $\;\left( {x,y,z}\right) = \left( {{x}^{\prime \prime },{y}^{\prime \prime },{z}^{\prime \prime }}\right)$ ?

We observe

$$ \begin{array}{l} = \left{ \begin{array}{l l} (1 7) & \mathrm {w i t h} x, y := x ^ {\prime}, y ^ {\prime} \ 2 y ^ {\prime} - x ^ {\prime} \end{array} \right} \ = {1 7 } \ 2 y - (2 y - x) \ = \begin{array}{l} {{\mathrm {a l g e b r a} }} \ {x} \end{array} \ \end{array} $$

since $y = {y}^{\prime \prime }$ is a trivial consequence of(17), (17) is indeed an involution.

The last question about (17) is: "Is it an involution on $S$ ?", and here the answer is

negative: constraint (21) tells us that (17) is an involution on the subdomain of $S$ re-stricted by

$$ 2 y - x > 0 \quad \wedge \quad z + x - y > 0 $$

Note that we do not need to check that the target point $(x', y', z')$ lies on the subdomain, as it follows from (17) being an involution:

$$ \begin{array}{l} 2 y ^ {\prime} - x ^ {\prime} > 0 \land z ^ {\prime} + x ^ {\prime} - y ^ {\prime} > 0 \ {(1 7) } \ x ^ {\prime \prime} > 0 \quad \wedge \quad z ^ {\prime \prime} > 0 \ = {1 7) i s a n i n v o l u t i o n } \ x > 0 \land z > 0 \ = {x, y, z) \in S } \ t r u e \ \end{array} $$

We accept (17) restricted to the subdomain (22) of $S$ as part of inv1, more precisely as the part of inv1 that contains 1 fixpoint. Our remaining task is to complete the definition of inv1, i.e. to design a fixpoint-free involution on the complement of (22); because of odd.x and $x \neq y - z$ , that complement is the subdomain of $S$ restricted by

$$ x - 2 y > 0 \quad v \quad y - x - z > 0 $$

which is equivalent to the subdomain

$x - {2y} > 0 \land z + x - y > 0$ $y - x - z > 0$

Note that these conditions are no rabbits:

(23) is the guard - corresponding to (21) - for transformations (14) and (20), and (24) is for instance the guard for (19)

In fact, (19) and (20) are suitable candidates for the completion of the definition of $\operatorname{inv}$ ; they are, when we can show $\left( {x,y,z}\right) = \left( {{x}^{\prime },{y}^{\prime },{z}^{\prime }}\right)$ with

$\left( {x,y,z}\right) \mapsto \left( {{x}^{\prime },{y}^{\prime },{z}^{\prime }}\right) \mapsto \left( {20}\right) \left( {{x}^{\prime \prime },{y}^{\prime \prime },{z}^{\prime \prime }}\right)$ (ii) $\left( {x,y,z}\right) \mapsto \left( {{20}^{ \circ }}\right) \left( {{x}^{\prime },{y}^{\prime },{z}^{\prime }}\right) \mapsto \left( {19}\right) \rightarrow \left( {{x}^{\prime \prime },{y}^{\prime \prime },{z}^{\prime \prime }}\right)$

Proof ad (i) we observe

$$ \begin{array}{l} x = x ^ {\prime \prime} \wedge z = z ^ {\prime \prime} \ = {(2 0) \mathrm {w i t h} x, y, z := x ^ {\prime}, y ^ {\prime}, z ^ {\prime} } \ x = x ^ {\prime} - 2 y ^ {\prime} \wedge z = y ^ {\prime} \ = {(- 1 9) } \ x = x + 2 z - 2 z \wedge z = z \ = {\mathrm {a l g e b r a} } \ t r u e \ \end{array} $$

ad (ii) we observe similarly

$$ \begin{array}{l} x = x ^ {\prime \prime} \wedge y = y ^ {\prime \prime} \ = {(\mathrm {1 9}) \mathrm {w i t h} x, y, z := x ^ {\prime}, y ^ {\prime}, z ^ {\prime} } \ x = x ^ {\prime} + 2 z ^ {\prime} \wedge y = z ^ {\prime} \ = {2 0 } \ x = x - 2 y + 2 y \wedge y = y \ \end{array} $$

$$ \begin{array}{l} = {\mathrm {a l g e b r a} } \ t r u e \ (E n d o f P r o o f.) \ \end{array} $$

Summarizing, inv is defined by

$$ (x, y, z) \mapsto $$

$$ \begin{array}{l} (2 y - x, y, z + x - y) \mathrm {i f} 2 y > x \land z + x > y \ (x - 2 y, z + x - y, y) \quad \mathrm {i f} x > 2 y \land z + x > y \ (x + 2 z, z, y - x - z) \quad \mathrm {i f} \quad y > z + x \ \end{array} $$

The remaining question to be answered is how "miraculous" this proof is, how fortunate Zagier has been in the construction of inv1. Since S has an odd number of elements, the existence of involutions with a single fixpoint is no problem; the problem is the choice of an inv1 with compact definition and manageable properties. The linearity of the expressions in (14) through (17) makes the transformations invertible, which is very nice if you are heading for an involution, that fixpoints can only come from (17) and that (14) and (15) are each other's inverse is fairly obvious. But the guards are not mutually exclusive and their disjunction is not true for each point of S. That the latter can be achieved by replacing (14) and (15) via x,y-exchange by (19) and (20), well, that is, as far as I can see, just a hell of a lot of luck. Eager to see my prejudices

confirmed, I interpret this luck of course as the well-deserved reward for keeping things as simple as possible.

Acknowledgements My debt to D. Zagier is obvious. I am also indebted to the undergraduate students that attended my last spring's course on "Mathematical Methodology" and with whom I discussed and designed the above proof in their oral examinations.

Nuenen, 2 August 1993

Prof. Dr. Edsger W. Dgkstra Department of Computer Sciences The University of Texas at Austin Austin, TX 78712 - 1188 USA