That One Sentence Proof

see image here

So... I've seen this proof about 4 years ago and at that time I wasn't mathematically strong enough to understand what was going on with this proof. However, the proof is explained in a lecture of Number Theory I today so I'm writing what I understood here.

Lemma. Let $X$ be a finite set, and let $f \colon X \to X$ be a function such that $f \circ f = \mathrm{id}_X$ (we call such function "involution"). Then the parity of the number of fixed points of $f$ matches the parity of the cardinality of $X$. In particular, if $|X|$ is odd then there exists a fixed point of $f$.

Proof. Since $X$ is finite, we can give an algorithm that runs in finite time as the following. Let $S$ be the empty set initially. While $S \ne X$ pick $x \in X \setminus S$ and pair it with $f(x)$, then insert both $x$ and $f(x)$ into $S$. If they are the same, then $x$ is a fixed point, otherwise, a pair of distinct elements is counted (note that if $x \notin S$ then we're sure that $f(x) \notin S$ also because if $f(x)$ were to be in $S$ then either $f(x) = x'$ for some old $x'$, which $f(x') = f(f(x)) = x$ must've already been in $S$, a contradiction, or $f(x) = f(x')$ for some old $x'$ in which case $x'$ and $f(x')$ were already paired and inserted to $S$, a contradiction). We keep repeating this process until $S = X$. Then this gives the following equation.

$$|X| = 2|\text{pairs counted}| + |\text{fixed points}|$$

We modulo this equation by $2$ and see that the parity of $|X|$ must be equal to the parity of the number of fixed points.

In the particular case, if $|X|$ is odd then it is not possible that there is no fixed point. $\square$

One Sentence Proof with multiple sentences. (Zagier, idea from Heath-Brown, inspired by Liouville) The idea of that one sentence proof is to prove the existence of positive integers $a, b$ such that $a^2 + b^2 = p$ when $p \equiv 1 \pmod{4}$ is a prime. We consider the set $X = \{(a, b, c) \in \mathbb{Z}_{>0} \colon a^2 + 4bc = p\}$, and consider the involution $f$ defined as

$$f \colon \begin{cases} X &\to X\\ (a, b, c) &\mapsto (a, c, b). \end{cases}$$

Since $f$ swaps $b$ and $c$, if $f$ has an odd number of fixed point then there must be at least once that $b = c$ so that the swapping gives a fixed point. Once that happens, we see that there is a tuple of the form $(a, b, b)$ in $X$, meaning that $a^2 + 4bb = p$, that is, $a^2 + (2b)^2 = p$, which completes the proof. Now, by the lemma, it is enough to show that $|X|$ is odd, and this will show that $f$ has a fixed point.

To show that $|X|$ is odd, we begin by defining another involution $g$ as the following.

$$g \colon \begin{cases} X &\to X\\ (a, b, c) &\mapsto \begin{cases} (a+2c, c, b-a-c) & \text{if } a < b-c\\ (2b-a, b, a-b+c) & \text{if } b-c < a < 2b\\ (a-2b, a-b+c, b) & \text{if } a > 2b. \end{cases} \end{cases}$$

Now we need to check three things. First, $g$ is well-defined. This is not hard to see--the only undefined case is when $a = b-c$ and when $a = 2b$. If $a = b-c$ then $a^2 + 4bc = (b-c)^2 + 4bc = (b+c)^2$. This cannot be prime since it's a square! If $a = 2b$ then $p = a^2 + 4bc = 4b^2 + 4bc$ is divisible by $4$, a contradiction.

Second, $g$ is an involution. Well this is the boring part... but you get it. We check three cases: $a < b-c$ and see that if $(\alpha, \beta, \gamma) := g(a,b,c)$ then $\alpha > 2\beta$, so $g(\alpha, \beta, \gamma)$ must go to the third case, which gives back $(a, b, c)$. The second case is when $b-c < a < 2b$ and the third case is $2b < a$. They are tedious and similar to check.

Third, the only fixed point of $g$ is $(1, 1, \frac{p-1}{4})$. Well the existence is simple: just plug in $(1, 1, \frac{p-1}{4})$ and check that it belongs to $X$. The uniqueness can now be seen by the following. Suppose $(a, b, c)$ is another fixed point of $g$, then $g(a, b, c) = (a, b, c)$. The only possible case for this is the case that $b-c < a < 2b$ (trying to equate $(a, b, c)$ with $(a+2c, c, b-a-c)$ gives a problem that $c = 0$, and trying to equate $(a, b, c)$ with $(a-2b, a-b+c, b)$ gives a problem that $b = 0$). And therefore, $(a, b, c) = (2b-a, b, a-b+c)$. This means $a = b$. Plugging back, we have $a^2 + 4ac = p$, but $p$ is prime so $a$ must be $1$. Now $c$ is constrained to be $\frac{p-1}{4}$ automatically.

With these three facts, we know that $g$ is an involution with exactly one fixed point, so $|X|$ is odd. Since $|X|$ is odd, $f$ must have a fixed point too, so there is $(a, b, b) \in X$ such that $a^2 + 4bb = p$ and this completes the proof. $\square$