# Prove a set is a union of subsets

I'm in a class on proofs and problem-solving, and my final paper is on Zagier's "one sentence" proof regarding primes and their relations to the sum of two squares. One portion of the explanation of Zagier's proof requires me to prove that $$S = A\cup B\cup C$$ Definitions can be found here, to sum up the sets: $$S = \{ (x,y,z) \in \mathbb N^3 : x^2 + 4yz = p \}$$ $$(x,y,z) \mapsto \begin{cases} (x+2z, z, y-x-z) & \text{ if } x < y-z \\ (2y-x, y, x-y+z) & \text{ if } y-z < x < 2y \\ (x-2y, x-y+z, y) & \text{ if } x > 2y. \end{cases}$$

Once again, I'd just like to know how to prove $S = A\cup B\cup C$. Thanks in advance.

-

What you’ve written in the question is inadequate to make the question comprehensible, so I’m going to expand it. Let $p\equiv1\pmod4$ be prime, set $$S=\big\{\langle x,y,z\rangle\in\Bbb N^3:x^2+4yz=p\big\}\;,$$ and let

$$\varphi:S\to\Bbb N^3:\langle x,y,z\rangle\mapsto\begin{cases} \langle x+2z,z,y-x-z\rangle,&\text{if }x<y-z\\ \langle 2y-x,y,x-y+z\rangle,&\text{if }y-z<x<2y\\ \langle x-2y,x-y+z,y\rangle,&\text{if }x>2y\;; \end{cases}\tag{1}$$

then $\varphi$ is an involution on $S$ with a unique fixed point.

I’m guessing that your sets $A,B$, and $C$ correspond to the cases of the definition of $\varphi$:

\begin{align*} A&=\big\{\langle x,y,z\rangle\in S:x<y-z\big\}\;,\\ B&=\big\{\langle x,y,z\rangle\in S:y-z<x<2y\big\}\;,\text{ and}\\ C&=\big\{\langle x,y,z\rangle\in S:x>2y\big\}\;. \end{align*}

By definition $A\cup B\cup C\subseteq S$, so in order to show that $A\cup B\cup C$ is all of $S$, we need only prove that if $\langle x,y,z\rangle\in S$, then $x\ne y-z$ and $x\ne 2y$. Suppose, then, that $x,y,z\in\Bbb N$ and $x^2+4yz=p$.

1. If $x=y-z$, then $p=(y-z)^2+4yz=y^2+2yz+z^2=(y+z)^2$, which is impossible, since $p$ is prime.
2. If $x=2y$, then $p=4y^2+4yz=4y(y+z)$, which is again impossible because $p$ is prime.

The three cases of $(1)$ are therefore exhaustive $-$ no element of $S$ falls through the cracks $-$ and $S=A\cup B\cup C$.

Do you also need help showing that $\varphi$ is an involution and that it has a unique fixed point?

-
Thank you! I apologize for not making myself clear, I've been working so long on this problem I mistook the information you assumed to be obvious. I think I've got the portion of the problem regarding $\phi.$ Thank you again for your help. – Nick Taber Dec 5 '12 at 0:59
@Nick: No worries: it happens. – Brian M. Scott Dec 5 '12 at 1:00

Don Zagier took this involution because it's easy to show, that this involution has exactly one fixed point. Hence it appears that involution $(x,y,z) \mapsto (x,z,y)$ also has exactly one fixed point, implying the theorem.

-