# Seeking proofs that depend on the notion of even-vs-odd parity to prove their points

The notion of the parity is very important in a variety of branches of mathematics. Specifically, I am looking for proofs that use parity in the even-vs-odd sense to prove their points.

For example, it is instructive to show that $$\sqrt{2}$$ is irrational by contradiction and assuming there exist relatively prime integers $$m,n$$ where $$n \neq 0$$ such that $$\frac{m^2}{n^2} = 2$$. By assuming that $$m^2$$ is even, you can arrive at a contradiction. A similar argument applies when assuming that $$m^2$$ is odd$. Another example is showing that the alternating group of even permutations ($$A_n$$ within $$S_n$$) is a subgroup under composition of permutations. That claim can be extended to show that the odd permutations of $$S_n$$ do not form a subgroup. I'm not looking for explanations of even/odd functions or how to partition $$n$$ into distinct odd/even parts, but rather my question is: What proofs exists that depend on the notion of even-vs-odd parity to prove their points? Ideally an answer will supply a description of the theorem/proof or a reference or a full proof itself. ## 5 Answers The parity of the order of a finite group plays an enormous role in finite group theory! The Feit-Thompson Theorem settled Burnside's conjecture that every non-Abelian simple group has even order. There were numerous stepping-stones along the way, and a big part of the classification of finite simple groups was devoted to studying how involutions (non-identity elements of order two, guaranteed to exist in groups of even order, by Cauchy's theorem) affect the structure of a group; in particular looking at what's possible for the centralizer of an involution (apparently this is a consequence of the Brauer-Fowler Theorem, although I don't see the connection). One such stepping stone was Suzuki's CA paper, which studied groups (now called CA groups) in which the centralizer of any non-identity element is Abelian. In this paper, Suzuki showed that any CA group with odd order is solvable, and hence not simple. In even-dimensional Euclidean spaces, spherical waves have trailing edges; in odd-dimensional spaces they don't. The case of even perfect numbers is settled since long ($$P=M(M+1)/2$$ for $$M$$ a Mersenne prime). That of odd perfect numbers is still open. The diophantine equation $$x^p+y^p=z^p$$ where $$p$$ is a prime only has solutions for even $$p$$. • Saying "the case" "is settled" seems to mean a particular case of some particular question, and you haven't said which question it is. Much is not know about even perfect numbers; for example, nobody knows how many there are.${}\qquad{}\$ Apr 20, 2015 at 19:06
• @MichaelHardy: feel free to clarify my answer.
– user65203
Apr 20, 2015 at 19:13
• @Yves Daoust: Macroscopic REFERENCE to parity is a far cry from microscopic USE of parity, which is evidently what the OP is seeking.
– user584285
Jul 19, 2020 at 18:56
• @EulerSpoiler: haha.
– user65203
Jul 19, 2020 at 19:23

A really good example of a proof that depends on the notion of parity is on Don Zagier's one sentence proof that every prime $$p$$ of the form $$4k+1$$ can be written as the sum of two squares. His proof is below:

"The involution on the finite set $$\left\{S=(x,y,z)\in\Bbb{N}^3:x^2+4yz=p\right\}$$ defined by $$(x,y,z)\rightarrow \left\{ \begin{array}{ll} (x+2z,\space z,\space y-x-z) &\text{if}\space x has exactly one fixed point, so $$|S|$$ is odd and the involution defined by $$(x,y,z)\rightarrow (x,z,y)$$ also has a fixed point."

I have written a thorough and detailed explanation for how this proof works in case anyone is interested.

For every prime $$p$$ the set $$S$$ is non-empty and finite. The solution $$(1,1,k)$$ always works this demonstrates that the set always has at least one solution. The $$k$$ in $$(1,1,k)$$ comes from the $$4k+1$$ near the top of this answer. (The particular solution $$(1,1,k)$$ will be important later.) By definition $$x,y,z$$ are all natural numbers and each must be less than the finite number $$p$$ because of the equation $$x^2+4yz=p$$. This shows that the number of solutions is finite.

The order of the numbers in the triplet is important. For example when $$p=17$$ the solution $$(3,1,2)$$ is a different solution from $$(3,2,1)$$.

An involution is defined as a function that is it's own inverse. For example $$f(x)=\frac{1}{x}$$ is an involution because $$f(f(x))=\frac{1}{f(x)}=\frac{1}{\frac{1}{x}}=x$$. A second example is $$g(x)=-x\quad g(g(x))=-g(x)=-(-x)=x$$.

Fixed points of functions are when the input of the function equals the output of the function. The fixed points of $$f(x)=\frac{1}{x}$$ occur at $$x=1$$ and $$x=-1$$ because it is when $$x=f(x)\rightarrow x=\frac{1}{x}\rightarrow x^2=1 \rightarrow x=\pm1$$.

The cardinality of a set is the number of elements in the set. If $$A$$ is a set, then the cardinality of a set can be denoted as $$|A|$$. If $$A=\left\{1,2,3,6,8\right\}$$ then $$|A|=5$$

I now want to show that the map:

$$(x,y,z)\rightarrow \left\{ \begin{array}{ll} (x+2z,\space z,\space y-x-z) &\text{if}\space x

is well defined. There are two steps to this, the first is to show that the inequalities are valid and the second is to show that the numbers in the second set of triplets are all natural numbers. $$x\neq y-z$$ because if it did then the expression $$x^2+4yz$$ wouldn't be prime. If $$x=y-z$$ then $$x^2+4yz=(y-z)^2+4yz=y^2-2yz+z^2+4yz=y^2+2yz+z^2=(y+z)^2$$ The last expression is clearly a square which can't be prime. If $$x=2y$$ then $$4$$ divides $$x^2+4yz$$. $$x^2+4yz=(2y)^2+4yz=4y^2+4yz=4(y^2+yz)$$ the last term is clearly divisable by $$4$$ and therefore $$x\neq 2y$$. The expression $$2y\le y-z$$ is impossible. $$2y\le y-z \rightarrow y \le -z$$ a natural number can't be less than or equal to a negative number. Therefore $$y-z\lt 2y$$. The only possibilities left are the one shown in the mapping: $$x\lt y-z\lt 2y$$ or $$y-z\lt x\lt 2y$$ or $$y-z\lt 2y\lt x$$. This means that the inequalities are valid.

The mapping shows three triplets (for a total of nine entries). The entries with only positive terms must produce natural numbers. The entries that might be negative are the ones with negative terms. The inequality of the first triplet shows that the third entry is positive $$x\lt y-z \rightarrow 0\lt y-x-z$$. The inequality of the second term show that both the first entry and the third entry are positive. $$x\lt 2y \rightarrow 0\lt 2y-x$$ and $$y-z\lt x \rightarrow 0\lt x-y+z$$. The inequality of the third term shows that the first entry is positive $$2y\lt x \rightarrow 0\lt x-2y$$. If $$2y\lt x$$ then $$y-z\lt x\rightarrow 0. This shows the second entry of the third triplet is positive. All entries of all triplets are natural numbers.

Now I want to show that the new triplets are solutions to $$p$$. For the first triplet every $$x$$ in the expression $$x^2+4yz$$ is substituted with $$x+2z$$, every $$y$$ is substituted with $$z$$ and every $$z$$ is substituted with $$y-x-z$$. The substitutions look like this: $$x^2+4yz \Rightarrow (x+2z)^2+4(z)(y-x-z)=x^2+4xz+4z^2+4yz-4xz-4z^2=x^2+4yz$$

For the second triplet every $$x$$ in the expression $$x^2+4yz$$ is substituted with $$2y-x$$, all $$y$$'s stay the same and every $$z$$ is substituted with $$x-y+z$$. The substitutions look like this: $$x^2+4yz \Rightarrow (2y-x)^2+4(y)(x-y+z)=4y^2-4xy+x^2+4xy-4y^2+4yz=x^2+4yz$$

For the third triplet every $$x$$ in the expression $$x^2+4yz$$ is substituted with $$x-2y$$, every $$y$$ is substituted with $$x-y+z$$ and every $$z$$ is substituted with $$y$$. The substitutions look like this: $$x^2+4yz \Rightarrow (x-2y)^2+4(x-y+z)(y)=x^2-4xy+4y^2+4xy-4y^2+4yz=x^2+4yz$$

Now I want to show that the mapping is an involution by using the second set of triplets as an input.It is easy to get confused on this part of the post. To try and help avoid confusion I will put down a separate mapping with slightly different labels.

$$(a,b,c)\rightarrow \left\{ \begin{array}{ll} (a+2b,\space c,\space b-a-c) &\text{if}\space a

Now if we use the first triplet from the $$(x,y,z)$$ mapping as an input to this one then $$a=x+2z,b=z,c=y-x-z$$ in this case the output is the third triplet of the $$(a,b,c)$$ mapping because $$2b\lt a$$. So the output is $$(a-2b,\space a-b+c,\space b)$$. Now we just apply the substitutions to get the output in terms of $$x,y,$$ and $$z$$. $$((x+2z)-2(z),(x+2z)-(z)+(y-x-z),(z))=(x+2z-2z,x+2z-z+y-x-z,z)=(x,y,z)$$

If the second triplet from the $$(x,y,z)$$ mapping is the input for the $$(a,b,c)$$ mapping then $$a=2y-x,b=y,c=x-y+z$$ in this case the output is the second triplet of the $$(a,b,c)$$ mapping because $$b-c\lt a\lt 2b$$. So the output is $$(2b-a,\space b,\space a-b+c)$$. Now we just apply the substitutions to get the output in terms of $$x,y,$$ and $$z$$. $$(2(y)-(2y-x),(y),(2y-x)-(y)+(x-y+z))=(2y-2y+x,y,2y-x-y+x-y+z)=(x,y,z)$$

If the third triplet from the $$(x,y,z)$$ mapping is the input for the $$(a,b,c)$$ mapping then $$a=x-2y,b=x-y+z,c=y$$ in this case the output is the first triplet of the $$(a,b,c)$$ mapping because $$a\lt b-c$$. So the output is $$(a+2c,\space c,\space b-a-c)$$. Now we just apply the substitutions to get the output in terms of $$x,y,$$ and $$z$$. $$((x-2y)+2(y),(y),(x-y+z)-(x-2y)-(y))=(x-2y+2y,y,x-y+z-x+2y-y)=(x,y,z)$$

This shows that the mapping is an involution. Applying the map twice got the original output back in all three cases.

Now I want to find all of the fixed points of the mapping. If the first triplet is the same as the input then $$x=x+2z$$ and $$y=z$$ and $$z=y-x-z$$

$$x=x+2z\rightarrow 0=2z \rightarrow 0=z$$

$$y=z\rightarrow y=0$$

$$z=y-x-z\rightarrow 0=-x \rightarrow x=0$$

There are no fixed points from the first triplet.

If the second triplet is the same as the input then $$x=2y-x$$ and $$y=y$$ and $$z=x-y+z$$

$$x=2y-x\rightarrow 2x=2y \rightarrow x=y$$

$$z=x-y+z\rightarrow 0=x-y \rightarrow y=x$$

if $$y=x$$ then $$x^2+4yz=x^2+4xz=x(x+4z)=p=4k+1$$

Since $$x(x+4z)$$ is prime and $$x\lt x+4z$$ the only way that this can produce a prime is if $$x=1$$. So $$x(x+4z)=4z+1=4k+1\rightarrow 4z=4k\rightarrow z=k$$.

The second triplet has one fixed point $$(1,1,k)$$.

If the third triplet is the same as the input then $$x=x-2y$$ and $$y=x-y+z$$ and $$z=y$$

$$x=x+2y\rightarrow 0=2y \rightarrow 0=y$$

$$y=x-y+z\rightarrow 0=x+z\rightarrow -x=z$$

$$z=y\rightarrow z=0 \rightarrow -x=0 \rightarrow x=0$$

There are no fixed points from the third triplet.

There is only one fixed point from the mapping. If all solutions come in pairs with the sole exception of the fixed point this means that there are an odd number of solutions or in other words $$|S|$$ is odd. With this new knowledge one can use a second mapping $$(x,y,z) \rightarrow (x,z,y)$$. This second mapping has no inequalities. The second mapping’s output are clearly natural numbers. The output gives the same result for $$p$$, since $$x^2+4yz=x^2+4zy$$. This second mapping is also clearly an involution because switching the $$y$$ and $$z$$ terms twice is the same as not switching them at all. All solutions of the second mapping have two cases the first is that the two solutions $$(x,y,z)$$ and $$(x,z,y)$$ are different and in pairs. The second case is that $$(x,y,z)$$ and $$(x,z,y)$$ are the same solution (A fixed point). Since it known that $$|S|$$ is odd there must be an odd number of fixed points (at least one). If $$(x,y,z)$$ and $$(x,z,y)$$ are the same solution then $$y=z$$ which means $$x^2+4yz=x^2+4y^2=x^2+(2y)^2$$. This means that $$p$$ can be written as the sum of two squares.

Euler, in his proof that all even perfect numbers have the form given by Euclid, used a very slick parity (odd/even) argument.

Also, parity is crucial in the canonical solution to the problem of generating Pythagorean triples.

Also, by a parity argument, it is proved that the number of sides of a golygon is a multiple of 8. Here is the link to the Wikipedia article on golygons: https://en.wikipedia.org/wiki/Golygon

It’s worth noting that in Language Arts, opposite parities can co-exist. That is, certain expressions, like ‘to dust’ possess antonymous meanings. Such expressions are called auto-antonyms. Here is the link to the Wikipedia article on this topic: https://en.wikipedia.org/wiki/Auto-antonym#:~:text=An%20auto%2Dantonym%20or%20autantonym,is%20the%20reverse%20of%20another.&text=This%20phenomenon%20is%20called%20enantiosemy,%22)%2C%20antilogy%20or%20autantonymy.