Cauchy's Theorem on the Permutations of a Function

It is perhaps a bit surprising that a study of functions with multiple parameters led to the proof by Niels Abel that the quintic equation was not solvable by radicals.

In today's blog, I will focus on a very interesting result from Augustin-Louis Cauchy. He discovered that there are limits to the number of values a function of multiple parameters can take when you change the order of the parameters. The content in today's blog is taken from Peter Pesic's Abel's Proof.

Joseph-Louis Lagrange had shown that the number of values a function of n parameters can take from permuting parameters will necessarily divide n!. I went over this result in a previous entry.

Cauchy found additional limits on the number of values a function can take. For a function with n parameters, if p is the highest prime that divides n, then the function can take 1, 2, or at least p possible values from permuting the order of its parameters.

That a function with n parameteres can take 1 value is easy to show. Consider the following function:

f(x₁, x₂, ..., x_n) = x₁ + x₂ + ... + x_n

Clearly, swapping any two parameters doesn't change the value so it is clear that no permutation will change its value. In this case, the function of n parameters can only take on 1 value.

It is also easy to show a function of n parameters can take on 2 values. Consider the following function:

f(x₁, x₂, ..., x_n) = (x₁ - x₂) *(x₁ - x₃)*... *(x₁ - x_n)*...*(x_n-1 - x_n)

Now, any swap of two parameters will keep the absolute value but change the sign of the function. So, the absolute value stays the same.

So, this is where Cauchy's Theorem comes in. Cauchy proves that if a function of n parameters takes on more than 2 values, then it necessarily takes on at least p values where p is the highest prime dividing n.

Here's an example where this occurs. Consider the following function:

f(x₁, x₂, x₃, x₄, x₅) = (x₁ + x₂ + x₃ + x₄) - x₅

How many values can this function take on if we permute the parameters? Since swapping x₅ changes the value of the function, we can see that there are at least 5 possible values (1 + 4) that the function can take.

Let's start out with some definitions:

Definition 1: f(P)^u

Let P be a permutation and let f(P)^u represent the value of the function after the permutation P is applied to the function f, u times. I will use f(P)⁰ to mean that the permutation has been applied 0 times.

Definition 2: Order of a Permutation

A permutation P is said to be of order k if P^k(f(x₁, ..., x_n)) = f(x₁, ..., x_n). Using the above notation, this means that f(P)^k = f(P)⁰.

In other words, the permutation after being applied k times return the function to its original ordering of the parameters.

Definition 3: f(P)^-u

By -u, I mean the inverse of the permutation. Since each permutation is one-to-one and onto, (see here for review if needed), it follows that it has an inverse which is also a permutation. f(P)^-u means that we apply the inverse of the permutation u times.

This gives us the result that if we apply the permutation P u times to f(P)^-u, we are left with f(P)^-u+u = f(P)⁰

Now, I will use these definitions in the following lemmas from Cauchy:

Lemma 1:

Let f be a function that takes n parameters.

Let p be the largest prime that divides n

Let m be the number of values that f takes on when we permute the order of f's parameters.

If m is less than p, then any permutation of order p will leave the value of f unchanged.

Proof:

(1) Let P be a permutation of order p such as (x₁ → x₂ → x₃ → ... → x_p → x₁)

(2) So, we have f(P)^p = f(P)⁰

(3) Now, let's consider the set of p-1 orderings that f takes as we apply P to f:

f(P)⁰, f(P)¹, f(P)², ..., f(P)^p-1

(4) Since we are assuming that m is at most p-1, it follows that two of these values must be the same.

(5) Let's label them r and r' where 0 ≤ r' ≤ p-2 and 1 ≤ r ≤ p-1 and further r' is less than r so that:

f(P)^r = f(P)^r'

(6) Now since both r, r' are less than p, we know that p-r ≥ 1.

(7) Now, if we apply the permutation P to both values (p-r) times, we get:

f(P)^r+p-r = f(P)^r'+p-r

(8) Since r+p-r = p and f(P)^p = f(P)⁰, we are left with:

f(P)⁰ = f(P)^r'+p-r

(9) Let j = r'+p-r so that we have:

f(P)⁰ = f(P)^j

(10) We can see that f(P)⁰ = f(P)^bj where b is any integer that we choose since:

(a) For b=1, this is clearly the case from step #9.

(b) We assume it is true up to b-1 so that:

f(P)⁰ = f(P)^(b-1)j = f(P)^bj-j

(c) Now, we apply P to each side j times so that we have:

f(P)^0+j = f(P)^bj-j+j

(d) This gives us that:

f(P)^j = f(P)^bj

(e) Applying step #9 gives us:

f(P)⁰ = f(P)^bj

(f) We can make the same argument for the case when b is negative.

(g) Let P^-1 be the inverse permutation of P.

(h) Apply P^-1 j times to each value in step #9 gives us:

f(P)^-j = f(P)⁰

(h) Now, we assume that it is true up to b-1 so that we have:

f(P)^-j(b-1) = f(P)^-bj+jf(P)⁰

(i) Now, we apply P^-1 j times to each side to get:

f(P)^-bj = f(P)^-j

(j) Applying step #10i gives us:

f(P)^-bj = f(P)⁰

(11) Now, we know that j is a number less than p since j = r' + p - r and r is greater than r'.

(12) Since p is prime, it follows that gcd(p,j)=1 and using Bezout's Identity, we know that there exists integers a',b such that:
a'p + bj = 1

(13) Let a = -a', then we have:

-ap + bj = 1

which is the same as:

bj = ap + 1

(14) Appyling this equation to f gives us:
f(P)^bj = f(P)^ap+1

(15) From step #10 this gives us that:

f(P)⁰ = f(P)^ap+1

(16) But from step #2, this gives us that:

f(P)⁰ = f(P)^ap
(17) This means that:

f(P)^ap = f(P)^ap+1

(18) But this is only possible if P doesn't change the value of the function.

QED

Let's explore Lemma 1 in more detail. Consider our function with 2 values where:

f(x₁, x₂, x₃) = (x₁ - x₂)*(x₁ - x₃)*(x₂ - x₃)

Since n=3, the highest prime is 3. Let's see how many permutations there are with the order of 3.

P = (x₁ → x₂ → x₃ → x₁)

So, applying P once gives us:

f(P)¹ = (x₂ - x₃)*(x₂ - x₁)*(x₃ - x₁) = (x₂ - x₃)*(-1)*(x₁ - x₂)*(-1)*(x₁ - x₃) = (x₁ - x₂)*(x₁ - x₃)*(x₂ - x₃)

So, we see that Lemma 1 holds.

Now, it turns out that this lemma has a surprising corollary.

Corollary 1.1:

Let f be a function that takes n parameters.

Let p be the largest prime that divides n

Let m be the number of values that f takes on when we permute the order of f's parameters.

If m is less than p, then any permutation of order 3 will leave the value of f unchanged.

Proof:

(1) Let P₁ be a permutation of order 3 which we can define as x_i1 → x_i2 → x_i3 → x_i1

(2) I will show that it is equivalent to application of two permutations of order p.

(3) Let P₂ be the permutation of order p such that:

x_i1 → x_i2 → ... → x_ip

We can view this as (1234...p)

(4) Let P₃ be another permutation of order p such that:

x_i2 → x_i3, x_i3 → x_i1, x_i4 → x_i2, x_i5 → x_i4, x_i6 → x_i5, ..., x_i1 → x_ip

We can view this as (1p...5423)

(5) Now, if we perform the first permutation (P₂) and then the second (P₃), we get:

x_i1 → x_i2 → x_i3, x_i2 → x_i3 → x_i1, x_i3 → x_i4 → x_i2, x_i4 → x_i5 → x_i4, x_i5 → x_i6 → x_i5, ..., x_ip → x_i1 → x_ip

(6) In other words, we have the three-order permutation:

x_i1 → x_i2 → x_i3 → x_i1

(7) Since both order-p permutations of step #3 and step #4 do not change the value of the function and since P₁ = P₃(P₂), it follows P₁ does not change the value of the function.

QED

Let's see this result in action. Let's revise our example above to now have 5 parameters so that we have n=5, p=5 and the number of different values are 2:

f(x₁, x₂, x₃, x₄, x₅) = (x₁ - x₂)*(x₁ - x₃)*...*(x₂ - x₃)...*(x₄ - x₅)

Now, let's see what happens when we apply the following permutation of order 3:

P = (x₁ → x₂ → x₃ → x₁)

We get:

f(P)¹ = (x₂ - x₃)*(x₂ - x₄)*...*(x₄ - x₅)

Now, we only need to consider the cases where the the first element is greater than the second element. This occurred twice so that we now have:

(x₂ - x₁)*(x₃ - x₁)

But if it occurs only twice, then we have:

(-1)*(x₁ - x₂)*(-1)*(x₁ - x₃) = (x₁-x₂)*(x₁ - x₃)

So, we see that the corrollary holds.

Cauchy was able to take this result one step farther:

Corollary 1.2:

Let f be a function that takes n parameters.

Let p be the largest prime that divides n

Let m be the number of values that f takes on when we permute the order of f's parameters.

If m is less than p, then application of any two permutation of order 2 will leave the value of f unchanged.

Proof:

(1) Let P₁ be an order-2 permutation such that:

x_j1 → x_j2

(2) Let P₂ be an order-2 permutation with overlap with P₁

x_j2 → x_j3

(3) So, we can define an order-3 permutation that is equivalent to the application of these two permutations of order 2:

x_j1 → x_j2 → x_j3

(4) Again, we know that application of the two overlapping order-2 permutations cannot change the value. If they did, this would imply that the above order-3 permutation would also change the value which goes against Corollary 1.1 above.

(5) Let's redefine P₂ so that it does not overlap with P₁ so that:

x_j3 → x_j4

(6) But in this case, it is equivalent to application of two order-3 permutations.

(7) Let us define P₃ as:

x_j1 → x_j2→ x_j3

(8) And define P₄ as:

x_j3 → x_j1 → x_j4

(9) We can see that they are equivalent since we now have:

x_j1 → x_j2 → x_j2

x_j2 → x_j3 → x_j1

x_j3 → x_j1 → x_j4

x_j4 → x_j4 → x_j3

(10) Again, the application of two order-2 permutations cannot change the value since the application of two order-3 permutations cannot change the value.

QED

Now, we are ready for Cauchy's main theorem.

Theorem 2: For a function with n parameters, if p is the highest prime that divides n, then the function can take 1, 2, or at least p possible values from permuting the order of its parameters.

Proof:

(1) To prove this theorem, we only need to prove that if the number of values is less than p, then it is 1 or 2.

(2) Assume that the number of values that the function takes is less than p.

(3) Assume further that the number of values is at least 3.

(4) Let's label them V₁, V₂, V₃

(5) Let's define a permutation P₁ as the reordering of V₁ so that it becomes V₂ so that:

Let V₁ = f(x_i1, x_i2, ..., x_in)

Let V₂ = f(x_j1, x_j2, ..., x_jn)

Then P₁ = (x_i1 → x_j1, ..., x_in → x_jn)

(6) Now, we know that P₁ is an order 2 permutation since:

(a) We can view P₁ as sequence of order 2 permutations (see step 5 above)

(b) Each of the permutations is either changing the value or keeping the value. By Corollary 1.2 above, if one of the permutations changes the value, then any order-2 permutation applied to it must undo the change.

(c) So, clearly if the value changes, only of the sequence of order-2 permutations changes the value.

(7) Using the same logic as step #5, we can define a permutation that changes V₂ to V₃ and we can assume that this permutation consists of a sequence of order-2 permutations.

(8) But by the same logic as step #6, P₂ must also be an order-2 permutation.

(9) But now we have a contradiction since if we can apply P₁ to V₁ to change the value to V₂ and we can apply P₂ to V₂ to change the value to V₃, then we have a situation where application of two 2-order permutations results in a change of value which contradicts Corollary 1.2.

(10) Therefore, we must reject our assumption in step #3 and assume that the number of values is at most 2.

QED

References

• Peter Pesic, Abel's Proof: An Essay on the Sources and Meaning of Mathematical Unsolvability, The MIT Press, 2004.
  

Augustin-Louis Cauchy

Augustin-Louis Cauchy was born on August 21, 1789 in Paris. It was the time of the French Revolution. For a bit, Cauchy's father left Paris but later returned.

Cauchy's father was friends with some of the most famous mathematicians of France. Joseph-Louis Lagrange and Pierre-Simon Laplace were visitors to the Cauchy home. Indeed, it is said that Lagrange took an interest in young Cauchy and recommended that Augustin start with the study of classical languages before taking on mathematics.

In 1802, Augustin entered the Ecole Central du Pantheon where he followed Lagrange's advice and focused on the study of languages for the first two years and then switched to mathematics in 1804.

In 1805, he took the entrance exam for the Ecole Polytechnique. He got the second highest score. At the Ecole Polytechnique, he shined in mathematics and was over all, an excellent student. After he graduated from the Polytechnique, he studied engineering and became an engineer.

In 1811, he published his first paper in mathematics on the angles of a convex polyhedron. He showed the angles depended on the faces of the polyhedron. Encouraged by the response to the first paper, in 1812, he submitted a second mathematical paper whose topic was polygons and polyhedra.

In 1812, he moved to Paris in an effort to make more of an impact in mathematics. His next paper was on symmetric functions. He now tried to get an academic post in Paris. He applied for numerous positions but was unable to get them. For two years, he continued with his mathematical researches. He continued to try for different positions. Despite his failure at achieving academic positions, his mathematical output was phenomenal. In 1814, he wrote his very important work on definite integrals which would have a big impact on the theory of complex functions.

Finally, in 1815, he received an assistant professorship at the Ecole Polytechnique. This seemed to indicate that his time had finally come. The next year, his work on waves won the Grand Prix at the French Academy of Sciences. He became even more well known when we he resolved on of Pierre de Fermat's claims about polygonal numbers. He now was admitted to the French Academy of Sciences.

At this time, Cauchy began his very important analysis on the foundations of calculus. It began as preparation for a textbook. He focused on the convergence conditions of an infinite series. He sought a precise definition of the integral. In 1829, he was the first to study complex functions with complex variables.

Cauchy did not have the best reputation with the other mathematicians of his day. He was famous for being arrogant. Niels Abel wrote (see MacTutor reference below):

Cauchy is mad and there is nothing that can be done about him, although, right now, he is the only one who knows how mathematics should be done.

Jean-Victor Poncelet, when he tried to talk with Cauchy about a paper that Cauchy criticized, reported (see MacTutor reference below):

...without allowing me to say anything else, he abruptly walked off, referring me to the forthcoming publication of his Leçons à 'École Polytechnique where, according to him, 'the question would be very properly explored'.

After the "July Revolution," Cauchy left Paris. At first, it appears he planned to take a break, but when a loyalty oath was required for him to keep his position, he declined. In 1832, he accepted a position in Theoretical Physics at Turin. In 1833, he moved to Prague to tutor the grandson of Charles X. It is said that Cauchy was not a very patient teacher. One person reported (see MacTutor):

As with mathematics, the prince showed very little interest in these subjects. Cauchy became annoyed and screamed and yelled. The queen sometimes said to him, soothingly, smilingly, 'too loud, not so loud'.

Cauchy returned to Paris in 1838. Because he refused to take the loyalty oath, he was limited in the responsibilities he could take. He was not allowed to teach, not allowed to attend scientific meetings, and could not not earn a salary for his work. During this period of time, Cauchy wrote on differential equations, mathematical physics, and mathematical astronomy.

By 1848, Louis Philippe and his government were out. Cauchy was now able to reclaim his position in academia. In 1850, he ran against Joseph Liouville for a top mathematical chair position. The election was close but Liouville won. This led to bad relations between the two top mathematicians.

Cauchy died on May 23, 1857. His daughter wrote the following (see MacTutor reference):

Having remained fully alert, in complete control of his mental powers, until 3.30 a.m.. my father suddenly uttered the blessed names of Jesus, Mary and Joseph. For the first time, he seemed to be aware of the gravity of his condition. At about four o'clock, his soul went to God. He met his death with such calm that made us ashamed of our unhappiness.

Cauchy was one of the most productive mathematicians of all time. The collection of his work spans 27 volumes. In all, he had written 789 mathematical papers. Here is how one historian summarized his life work (see MacTutor reference):

... such an enormous scientific creativity is nothing less than staggering, for it presents research on all the then-known areas of mathematics ... in spite of its vastness and rich multifaceted character, Cauchy's scientific works possess a definite unifying theme, a secret wholeness

References

• "Augustin Louis Cauchy", MacTutor Math Web Site.
  

Abel's Proof: A Gentle Introduction to Mathematics

In addition to this blog, I have started a series of "softer" mathematical essays on hubpages.com.

You can see my first posting in the series here. It is on Abel's proof.

Paolo Ruffini

Paolo Ruffini was born on September 22, 1765 in what is today Italy. In 1783, he entered the University of Modena where he studied geometry, calculus and medicine. In 1787, he was asked to teach the course on calculus even though he was still a student. Later, in 1788, he became a professor at the university.

Even as he taught mathematics, he continued to study medicine and in 1791, he received his license to practice medicine.

1796 was the time of Napoleon Bonaparte who took over Modena. Napoleon set up what became the Cisalpine Republic that included Modena. All faculty of the university were required to swear an oath of allegiance to the new republic.

Ruffini refused to swear this oath and so lost his job and was no longer allowed to teach. This change enabled him to focus on medicine and to actively study his own projects in mathematics.

One of his math projects was an effort to solve the quintic equation in terms of radicals. The quadratic equation was long known to be solvable. The cubic equation had been solved by Giralomo Cardano and the quartic equation had been solved by Lodovico Ferrari. No one had yet solved the quintic.

It was at this point, that Paolo Ruffini approached the problem differently than others had before him. He was the first person to propose that the problem was not solvable in terms of radicals. In 1799, Ruffini published his math treatise which he titled: General theory of equations in which it is shown that the algebraic solution of the general equation of degree greater than four is impossible.

In the introduction, he writes:

The algebraic solution of general equations of degree greater than four is always impossible. Behold a very important theorem which I believe I am able to assert (if I do not err): to present the proof of it is the main reason for publishing this volume. The immortal Lagrange, with his sublime reflections, has provided the basis of my proof.

In writing this work, he made arguments in terms of group theory. Since group theory had not yet been invented, Ruffini had to invent concepts which made his argument even hard to follow. In this work, we find such concepts as order, cycles, and the notion of primitive elements. Joseph-Louis Lagrange had previously written about permutations but Ruffini applied these points to his argument in ways that Lagrange had not. In this work, he successfully proved some very important theorems of group theory.

Unfortunately, he did not succeed in proving his claim about the quintic equation. He came very close. So close, in fact, that it was later accepted by Augustin Louis Cauchy as valid. In retrospect, it is clear that his argument had a significant gap which would later be resolved by Niels Abel. Ruffini assumed but failed to demonstrate that:

"...if an expression by radicals is a root of the general equation of some degree, then every function of it is composed is a rational expression of the roots." (Jean-Pierre Tignol, p211).

In fairness to Ruffini, he received no response from the mathematical community on this point. He sent a copy to Lagrange in 1801. He got no response. He sent out a second copy of his book with the following message:

Because of the uncertainty that you may have received my book, I send you another copy. If I have erred in any proof, or if I have said something which I believed new, and which is in reality not new, finally if I have written a useless book, I pray you point it out to me sincerely.

He still got no response. In 1802, he wrote a follow up letter. Again, no response.

A mathematician named Gian Malfatti did respond with objections that today are viewed as a misunderstanding of Ruffini's ideas. Ruffini responded with additional proofs that are today accepted as answering Malfatti's objections.

Why didn't anyone respond? The answer seems to be that Ruffini was tackling a question in a way that no one wanted to be right. The mathematical community was not yet ready to concede that quintic equations were not solvable by radicals. In addition, Ruffini's proof was over 516 pages and the mathematical argument was difficult to follow.

In 1810, Ruffini asked the Institute of Science in Paris to make a formal statement on the validity of his proof. After over a year, Adrien-Marie Legendre, Lagrange, and Sylvestre Francois de Lacroix concluded that there was nothing of importance here and that it was not "worthy of attention."

Ruffini made the same request of the Royal Society. The response was polite but again reflected disinterest in the topic area.

In 1814, after the fall of Napoleon, Ruffini was reinstated back at the University of Modena. All this time, Ruffini had a reputation for honesty and integrity. As a doctor, he treated patients from the richest to the poorest backgrounds. In 1817, there was a typhus epidemic. Ruffini proceeded to continue to treat patients and caught the disease himself. Although, he made a recovery, he never regained his health and had to resign from his university position in 1819.

The year before his death, he received the following correspondence from Cauchy which would represent the only recognition he received while he was alive from a major mathematician:

... your memoir on the general resolution of equations is a work which has always seemed to me worthy of the attention of mathematicians and which, in my judgement, proves completely the impossibility of solving algebraically equations of higher than the fourth degree.

Even so, Ruffini does not get credit for proof that the quintic equation is not solvable by radicals. That honor goes to Niels Abel. On this point, R. G. Ayoub writes:

... the mathematical community was not ready to accept so revolutionary an idea: that a polynomial could not be solved in radicals. Then, too, the method of permutations was too exotic and, it must be conceeded, Ruffini's early account is not easy to follow. ... between 1800 and 1820 say, the mood of the mathematical community ... changed from one attempting to solve the quintic to one proving its impossibility...

Paolo Ruffini died on May 10, 1822 in Modena.

References

• "Paolo Ruffini: Biography", MacTutor
• Jean-Pierre Tignol, Galois' Theory of Algebraic Equations, World Scientific, 2001

Gauss: Construction of regular polygons

It was not enough for Carl Friedrich Gauss to prove the constructibility a heptadecagon (a seventeen sided polygon). He generalized the idea to come up with the theorem that I will present today.

The content in today's blog is taken from Jean-Pierre Tignol's Galois' Theory of Algebraic Equations.

Lemma 1: The periods of two terms are (2 cos 2kπ/p) for k = 1 ... (p-1)/2

Proof:

(1) η_j = ζ_j + ζ_{[j + (p-1)/2]} [See Definition 3, here where e = (p-1)/2 and f = 2]

(2) ζ_{[j + (p-1)/2]} = (ζ_j)^g(p-1)/2 [See Definition 1, here]

(3) g^(p-1)/2 ≡ -1 (mod p) since:

(a) (g^(p-1)/2)² ≡ g^p-1 (mod p)

(b) g^p-1 ≡ 1 (mod p) [By Fermat's Little Theorem, see here]

(c) Thus, g^(p-1)/2 ≡ ± 1 (mod p)

(d) But since g is a primitive root modulo p (see Definition 2 and Definition 4, here) and since (p-1)/2 is less than p-1, it follows that g^(p-1)/2 ≠ 1.

(e) Thus, we have that g^(p-1)/2 ≡ -1 (mod p).

(4) So, we have η_j = ζ_j + ζ_j^-1 [See Lemma 1, here]

(5) We can express the p-th roots of unity as solutions to Φ_p(x) such that they are the solution to:

x^p-1 + x^p-2 + ... + 1 = 0 [See Lemma 1, here]

(6) The trigonometric solution for the equation above are (see Corollary 1.1, here):

cos 2kπ/p + isin 2kπ/p where 1 ≤ k ≤ p-1.

(7) For ζ_j, there exists an integer m such that:

ζ_j = cos 2mπ/p + i sin 2mπ/p

(8) Using Lemma 4, here, where u= 2mπ/p, we have:

ζ_j + ζ_j^-1 = cos 2mπ/p + i sin 2mπ/p + cos 2mπ/p - isin 2mπ/p = 2 cos 2m π/p.

QED

Theorem 2: If p is a prime number of the form p = 2^m+1 (with m ∈ N) then the regular polygon with p sides can be constructed with ruler and compass.

Proof:

(1) Since p=2^m + 1, p-1 is a power of 2.

(2) We can thus view p-1 as a chain of multiplications such as:

1 → 2 → ... → 2^m-2 → 2^m-1 → 2^m

(3) Using a previous result (see Lemma 5, here), we can see that the chain of multiplication in step #2 shows that the periods of two terms can be determined by solving a sequence of quadratic equations.

(4) The periods of two terms are the values 2 cos 2kπ/p for k = 1 ... (p-1)/2 [See Lemma 1 above]

(5) Since the solution of a quadratic equation only requires rational operations and extraction of square roots (see Theorem, here), it follows that cos 2π/p can be obtained from 0 and 1 by rational operations and extractions of roots.

(6) So, using Wantzel's Constructibility Criterion (see Theorem 5, here), it follows that (cos 2π/p, 0) is constructible.

(7) Let A be a point at (0,a) and O at (0,0) such that we take OA as one unit of measurement and circle OA is a unit circle (see here for details if needed on unit circles)

(8) Point P0 = (cos 2π/p, sin 2π/p) is obtained in the following way:

(a) Let Q be the point at (cos 2π/p, 0) that we showed was constructible in step #6 above.

(b) Let QP0 be a line that is perpendicular to OQ and where P0 intersects with the unit circle OA. [See here for Euclid, Book I, Proposition 11 which shows this construction]

(c) Now, we can see that P0 is at (cos 2π/p, sin 2π/p) since:




By the diagram above:

x = cos 2π/p

r = 1

Since cos θ = (cos 2π/p)/1 = cos 2π/p, we have θ = 2π/p.

Also, we have: sin θ = sin 2π/p = y/1 = y

(9) The point P0 is a vertex of the regular polygon with p sides. The line AP0 forms one side of the polygon, so we can label point A as P1.

(10) We can find the other p-1 sides in the following way. Let P0P1 be a circle at point P1 with radius equal to P0P1 (see Postulate 2, here). Call P2 the point where circle P0P1 intersects with unit circle OA (and is not point P0). We can repeat for circle P2P1 (finding point P3), circle P3P2 (find point P4), etc. until we have constructed our regular p-sided figure.

QED

Corollary 2.1: A regular polygon with n sides can be constructed with a ruler and compass if n is a product of distinct Fermat primes and a power of 2.

Proof:

(1) A regular polygon with n sides is constructible when n is a Fermat prime. [By Theorem 2 above]

(2) Since we can always do a repeated bisection of angles (see here for Euclid's Elements, Book I, Prop 9), a regular polygon with n sides is also constructible when n is a power of 2.

(3) So, to complete this proof, we only need to show that if n₁ and n₂ are relatively prime and a polygon with n₁ sides is constructible and a polygon with n₂ sides is constructible, then it follows that a polygon with n₁n₂ sides is constructible.

(4) Since n₁, n₂ are relatively prime, there exists integers m₁, m₂ such that (see Lemma 1, here):

m₁n₁ + m₂n₂ = 1.

(5) Multiplying both sides by 2π/(n₁n₂) gets us:

m₁(2π/n₂) + m₂(2π/n₁) = 2π/(n₁n₂)

(6) Therefore using Wantzel's Criterion (see Theorem 5, here), it follows that 2π/(n₁n₂) can be constructed by repeating a certain number of times 2π/n₁ and 2π/n₂.

(7) It therefore follows that the regular polygon with n₁n₂ sides can be constructed from regular n₁ polygon and a regular n₂ polygon.

QED

References

• Jean-Pierre Tignol, Galois' Theory of Algebraic Equations, World Scientific, 2001

Fermat Numbers

While of all Pierre de Fermat's proposed theorems really turned out to be theorems, not all of his conjectures turned out to be true.

In all fairness to Fermat, these theorems and conjectures were published after his death and were based on the notes he kept.

Pierre de Fermat conjectured that the F_n = 2²ⁿ + 1 is prime for every integer n. These values F_n are today called Fermat Numbers.

The content in today's blog is taken from Jean-Pierre Tignol's Galois' Theory of Algebraic Equations.

Now, for n=0, 1, 2, 3, 4 the results are F₀=3, F₁=5, F₂=17, F₃=257, and F₄=65537 which are all prime.

In 1732, Leonhard Euler showed that F₅ = 641*6,700,417.

Since then, it has been shown that for 5 ≤ n ≤ 16, F_n is not prime.

Despite all these efforts, no other Fermat number has been found to be prime and no proof has been offered that would resolve this issue.

I will end today's blog with the following proof:

Lemma 1: If a prime number p has the form 2^m + 1, then m is a power of 2.

Proof:

(1) Assume that m is not a power of 2.

(2) Then it is divisible by some odd integer k.

(3) Now, we know that:

x^k + 1 = (x + 1)(x^k-1 - x^k-2 + ... - x + 1) [See Lemma 4, here where a=x, b=1]

(4) Let x= 2^m/k

(5) This then gives us:

(2^m/k)^k + 1= (2^m/k + 1)([2^m/k]^k-1 - [2^m/k]^k-2 + ... - [2^m/k] + 1)

(6) Since (2^m/k)^k + 1 = 2^m + 1, it follows that 2^m + 1 cannot be a prime since it is divisible by (2^m/k + 1).

(7) Therefore, we have a contradiction and we reject our assumption in step #1.

QED

References

• Jean-Pierre Tignol, Galois' Theory of Algebraic Equations, World Scientific, 2001

Wantzel: Constructibility Criterion

The criterion presented in today's blog was known to Carl Friedrich Gauss in 1796 when he presented his criterion for the constructibility of regular polygons. Even so, the proof of the criteroin was first presented in 1837 by Pierre Laurent Wantzel.

The content in today's blog is taken from Jean-Pierre Tignol's Galois' Theory of Algebraic Equations.

To simplify the proof, I offer the following postulates.

Postulate 1:

It is possible to draw a line between any two points that are already determined.

Posulate 2:

It is possible to draw a circle with a center at a point already determined and with the radius equal to the distance between any two points already determined.

Postulate 3:

If two lines are not parallel and not colinear, then they intersect at exactly one point.

Postulate 4:

If a circle's center is at a point on a line then the circle intersects the extended line at two points.

I will now use these postulates to present some lemmas:

Lemma 1: (0,v) is constructible if and only if (v,0) is constructible

Proof:








This follows from Postulate 2 above setting center A at (0,0) and radius = v. If C at (v,0) is constructible, then we can obtain B at (0,v). If B at (0,v) is constructible, then we can obtain C at (v,0).

QED

Lemma 2: (u,0) is constructible and (0,v) is constructible if and only if (u,v) is constructible















Proof:

(1) Assume that B at (u,0) and D at (0,v) are constructible.

(2) If B at (u,0) is constructible and D at (0,v) is constructible, then F at (u,v) is constructible since:

(a) Let BG be a line that intersects B at (u,0) and is parallel to the y-axis. [Euclid: Book I, Prop 12, see here]

(b) Let DE be a line that insersects D at (0,v) and is parallel to the x-axis. [Euclid: Book I, Prop 12, see here]

(c) Then F at (u,v) is constructible since it is the point where BG,DE intersect [See Postulate 3 above]

(4) Assume that F at (u,v) is constructible.

(5) Since F at (u,v) is constructible, we know that B at (u,0) is constructible and D at (0,v) is constructible since:

(a) Let FG be a line parallel to the y-axis that passes through F at (u,v) [Euclid: Book I, Prop 12, see here]

(b) Then B at (u,0) is the point where FG and the x-axis intersect. [See Postulate 3 above]

(c) Let EF be a line parallel to the x-axis that passes through F at (u,v) [Euclid: Book I, Prop 12, see here]

(d) Then D at (0,v) is the point where EF and the y-axis intersect. [See Postulate 3 above]

QED

Lemma 3:

If a line passes through two points (a₁,b₁) and (a₂,b₂), then it has the equation of form:

αX + βY = γ

where

α = b₂ - b₁
β = a₁ - a₂
γ = a₁b₂ - b₁a₂

Proof:

(1) This lemma is proved if it can be shown that both points satisfy the equation given.

That is, both equations, lead to γ = a₁b₂ - b₁a₂

(2) Case I: (a₁,b₁)

α(a₁) + β(b₁) = (b₂ - b₁)(a₁) + (a₁ - a₂)(b₁) = a₁b₂ - b₁a₂

(3) Case II: (a₂,b₂)

α(a₂) + β(b₂) = (b₂ - b₁)(a₂) + (a₁ - a₂)(b₂) = a₁b₂ - b₁a₂

QED

Lemma 4:

If we construct a circle with center (a₁,b₁) and radius equal to the distance between (a₂,b₂) and (a₃,b₃), then it's equation has the form:

X² + Y² = αX + βY + γ

where:

α, β, γ are rational expressions of a₁, a₂, a₃, b₁, b₂, b₃

Proof:

(1) The equation for this circle is (see Theorem 1, here):

(X - a₁)² + (Y - b₁)² = (a₂ - a₃)² + (b₂ - b₃)²

(2) Multiplying out the squares involving X,Y gives us:

X² - 2a₁X + a₁² + Y² - 2b₁Y - b₁²

(3) Moving everything but X²,Y² to the other side gives us:

X² + Y² = 2a₁X + 2b₁Y + [-a₁² -b₁² + (a₂ - a₃)² + (b₂ - b₃)²]

QED

Theorem 5: Criterion of Constructibility

Let O be a circle that with center at (0,0) and radius = 1 unit.

The point (u,v) is constructible from O if and only if (u,v) can be obtained from (1,0) by a sequence of operations of the following types:

(i) rational operations
(ii) extraction of square roots

Proof:

(1) I will prove the first part of the theorem using induction.

(2) For the base case, we assume that u=a or 0 and v=a or 0.

(3) To prove the base case, we have four cases to prove:

(a) (a,0),(0,0) [Constructible from the given]

(b) (0,a) [Constructible from (a,0) and Proposition 2 above if we set center at (0,0) and radius=a].

(c) (a,a) [Constructible from (a,0) and Lemma 1 above]

(4) So we assume that all points (u',v') are constructible.

(5) To complete the first half of the proof, we need to show that if (u',v') is constructible and (u,v) is obtained in a single operation from (u',v'), then (u,v) is constructible.

(6) Using Lemma 2 above, step #5 is achieved if we show that the following points are constructible:

(u'+v',0)
(u' -v',0)
(u'v',0)
(u'v'^-1,0) [assuming v ≠ 0 ]
(√u',0) [assuming u ≥ 0]

(7) (u'+v',0) and (u' -v',0) are constructible [From Postulate 2 above where the center is (u',0) and the radius=v and Postulate 4 above where (u'-v',0) and (u'+v',0) are the intersection of the circle and the x-axis.]

(8) (u'v',0) is constructible since:















(a) We are given that F at (0,v') is constructible.

(b) We are given that C at (u',0) is constructible.

(c) Let E at (0,b) be a point where b is less than v' and b is greater than 0 such that we consider b our unit of measure (i.e. b is length = 1 unit)

(d) Draw a line EC connecting E at (0,b) and C at (u',0) [See Posulate 1 above]

(e) Draw a line called FB parallel to EC and passing through F at (0,v') [Euclid: Book I, Prop 12, see here]

(f) Let B at (z,0) be the point where FB intersects with the x-axis. [See Postulate 3 above]

(g) Triangles EAC and FAB are similar since:

∠ EAC and ∠ FAB are the same.

∠ AEC is congruent to ∠ AFB and ∠ ACE is congruent to ∠ ABF since FB and EC are parallel [Euclid: Book I, Prop 29]

(h) So, we know that:

AC/AE = AB/AF [see Lemma 3, here]

(i) Since in step #8c above we assumed that AE = 1 unit, we have:

AC = AB/AF

or equivalently:

AB = AF*AC

(j) Since the length of AB is z [since A is at (0,0) and B is at (z,0)], the length of AF is v' [since A is at (0,0) and F is at (0,v')] and the length of AC is u' [since A is at (0,0) and C is at (u',0)], it follows that:

z = u'*v'

(9) (u'v'^-1,0) is constructible since:

(a) Using the same diagram as step #8 above, we are given that F at (0,v') is constructible.

(b) Let us assume that we are given B at (u',0) is constructible.

(c) Let E at (0,b) be a point where b is less than v' and b is greater than 0 such that we consider b our unit of measure (i.e. b is length = 1 unit)

(d) Draw a line EC connecting E at (0,b) with a point C at (c,0) on the x-axis. [Euclid: Book I, Prop 12, see here]

(e) We can use the same arguments as #8g above to establish that Triangles EAC and FAB are similar

(f) Using the same argument as #8i, we have:

AC = AB/AF

(g) Since the length of AB is u' [since A is at (0,0) and B is at (u',0)], the length of AF is v' [since A is at (0,0) and F is at (0,v')] and the length of AC is c [since A is at (0,0) and C is at (c,0)], it follows that:

c = u'/v' = u'*v'^-1

(10) Assuming u ≥ 0, then ( √u , 0) is constructible since:













(a) Assume that point B is at (0,0)

(b) Let D be a point on the x-axis at (d,0) such that BD = 1 unit.

(c) Let C be a point on the x-axis at (1+u',0) where 1 = BD. [See step #7 above]

(d) Let us a draw a circle O whose center is at the midpoint M of BC and whose radius is MC. [See Postulate 2 above]

(e) Let A at (1,a) be the intersection of O and a line drawn from D that is perpendicular to BC. [Euclid: Book I, Prop 11, see here]

(f) We can see that triangle BDA and triangle ADC are similar since:

Both ∠ BDA and ∠ ADC are right angles

And, ∠ BAC is a right angle [see Euclid: Book III, Prop 31]

So, ∠ BAD + ∠ DAC = 90 °

Since triangle ADC is a right triangle, we also have ∠ DAC + ∠ DCA = 90 ° [See Lemma 4, here]

So, we have shown that ∠ BAD ≅ ∠ DCA.

(g) Since the two triangles are equiangular, we have [see Lemma 3, here]:

DA/BD = DC/DA

(h) Since the length of DA is c [since A is at (1,c) and D is at (1,0)], the length of BD is 1 [since B is at (0,0) and D is at (1,0)] and the length of DC is u' [since D is at (1,0) and C is at (1+u,0)], it follows that:

c/1 = u'/c

Further, this gives us that:

c² = u'

which means that:

c = √u'

(11) To complete the second half of the proof, I will show that if a point (u,v) can be constructed from (1,0) then it can be obtained from (1,0) through a finite sequence of operations.

(12) To accomplish, I need to show that the following imply points obtained from (1,0):

(a) two lines intersecting
(b) two circles intersecting
(c) line intersecting with a circle

(13) A point at two lines intersecting implies that this new point is obtained from the previous points since:

(a) By Lemma 3 above, the two lines can be represented by:

α₁X + β₁Y = γ₁

α₂X + β₂Y = γ₂

(b) Assuming that α₁ ≠ 0, we multiply the top equation by (-α₂/α₁) and add the two equations together to get:

(-α₂/α₁)β₁Y + β₂Y = γ₁ + γ₂

which gives us that:

Y[(-α₂/α₁)β₁ + β₂] = γ₁ + γ₂

which shows that Y can be obtained from the given points.

Y = [γ₁ + γ₂ ]/[(-α₂/α₁)β₁ + β₂]

(c) Now, all we need to do is show that X can be obtained from the given points which can be shown using the first equation:

α₁X + β₁Y = γ₁

which then shows:

X = (γ₁ - β₁Y)/(α₁)

(14) A point at two circles intersecting implies that this new point is obtained from the previous points since:

(a) By Lemma 4 above, the two circles can be represented by:

X² + Y² = α₁X + β₁Y + γ₁

X² + Y² = α₂X + β₂Y + γ₂

which gives us:

α₁X + β₁Y + γ₁ = α₂X + β₂Y + γ₂

and moving X to one side and Y to the other gives us:

α₁X - α₂X = β₂Y - β₁Y + γ₂ - γ₁

(b) Now, assuming that (α₁ - α₂) ≠ 0, we can state X in terms of Y

X = [(β₂ - β₁)Y + γ₂ - γ₁]/(α₁ - α₂)

(c) Now, we can state Y as a quadratic equation since:

Using:

X² + Y² = α₁X + β₁Y + γ₁

We get:

{[(β₂ - β₁)Y + γ₂ - γ₁]/(α₁ - α₂)}² + Y² = α₁{[(β₂ - β₁)Y + γ₂ - γ₁]/(α₁ - α₂)} + β₁Y + γ₁

(d) Since a quadratic equation is solvable in terms of the coefficients (see Theorem, here if needed), we have shown that in this case, the points are obtained from the previous points.

(15) A point at a circle intersecting with a line is obtained from the previous points since:

(a) By Lemma 3 above, the line can be represented by:

α₁X + β₁Y = γ₁

(b) By Lemma 4 above, the circle can be represented by:

X² + Y² = α₂X + β₂Y + γ₂

(c) Assuming α₁ ≠ 0, we can restate X in terms of Y using step #15a since:

X = (γ₁ - β₁Y)/α₁

(d) Substituting into the equation in #15b gives us the following quadratic equation:

([γ₁ - β₁Y]/α₁)² + Y² = α₂([γ₁ - β₁Y]/α₁) + β₂Y + γ₂

(e) Since a quadratic equation is solvable in terms of the coefficients (see Theorem, here if needed), we have shown that in this case, the points are obtained from the previous points.

QED

References

• Jean-Pierre Tignol, Galois' Theory of Algebraic Equations, World Scientific, 2001