Talk at Cornell College: Thursday, November 6, 2001 1:00 pm "Professor, you have not even looked at my proof. How can you say that it is wrong?" This is the typical question asked by angle trisectors when they wish to show me their construction for trisecting an angle. It seems reasonable. Either their proof is correct, or else it has a mistake. If I cannot find a mistake, then in all fairness, I must accept that their proof is correct. Can I reasonably decide which is the case without looking. The answer is yes. The goal of today's lecture is to show how I can tell somebody his proof is wrong without even looking at the proof. I will work three of these algebraic proofs of impossibility. The first will be easy, the second will be harder, but within the realm of real understanding. The third will be very complicated and only the barest outline will be presented. The three problems are: (1) Triangular puzzle peg, (2) Geometric Constructions, and (3) Solvability by radicals. The steps to a proof of impossibility. ===================================== (a) We give a property that holds at the beginning. (b) We show by induction that the property continues to hold during any sequence of legal moves. (c) We assume that something questionable were really possible. (d) We observe that now we can create a situation where the property does not hold. (e) We conclude that the questionable thing must be impossible. First Example: ============== Pegs are arranged in a triangle with one vacant hole. o o o o o o o o o o o o o o o o o o o o o o o o [ ] o o o The player is asked to use jumps to reduce the array down to one peg. A jump consists of moving one peg over another and into a vacant hole. The peg which was jumped over is removed. Jumps can be horizontally or diagonally. We label the board using letters 1,p,q. Notice that any three consecutive positions horizontally or diagonally will involve all three letters. p q 1 1 p q p q 1 p q 1 p q 1 1 p q 1 p q p q 1 p q 1 p In Z2xZ2 let p = (1,0), q = (0,1), 1 = (1,1), and 0 = (0,0). (i) 0 is the additive identity. (ii) x+x = 0 for all x in {1,p,q,0}. (iii) 1+p+q = 0. The value of the board is the sum of the values of the pegs. The value of the peg is the value of the hole it occupies. We now compute the value of the board. p q 1 1 p q p q 1 p q 1 p q 1 1 p q 1 p q p q 1 [p] q 1 p -------------------------------------------------- p+1 +1+q+p+1+q +q+p = p+q+1 = 0. The value of the board starts at zero. Each legal move involves holes labeled with three distinct values. Since the sum of any two of them equals the third, the value of the board does not change and will remain zero. If one could reduce it to one peg, the value of the board must be 1, or p, or q. There is no hole with value 0. It must be impossible to reduce the board to one peg! Geometric Construction: ====================== The construction of the pentagon is a follows. ....B.... . . . . . . . . . . . . . . .....A.... . C . . . . . ......... The point A is at (1/2,0). The point B is (0,1). The Distance AB is Sqrt[5/4) The point C is (1/2-Sqrt[5/4],0) the Distance BC is the side of the pentagon and is |BC| = Sqrt[(1/2-Sqrt[5/4])^2 + 1)] = Sqrt[10/4 - Sqrt[5/4]] = Sqrt[5/2 - 1/2 Sqrt[5]]. The idea to be noted from this calculation is that our answer can be expressed using addition, subtraction, multiplication, division and square roots. The constructible numbers are those that can be expressed using the arithmetic operations +-*/ and square roots. The equation of a line is y = mx + b and the equation of a circle is x^2 + y^2 + Ax + By + C = 0. The point of intersection is obtained by substituting y = mx+b into the equation of the circle. This gives a quadratic in x. The solution is given by the quadratic formula and involves +-*/ and a square root. Subsequent calculations will involve this square root and introduce more of them. As complicated as this is, there is a constraint on all of the coordinates involved. The constraint is that they can be expressed using only +-*/ and square roots. This description of the roots seems reasonable. But the question now is, how can we show that there are numbers that cannot be expressed this way? The answer is that any number build up out of square roots will satisfy a polynomial over the rationals. Since it satisfies a polynomial, it satisfies a polynomial of minimal degree. That minimal degree will be 2^n for some n. The CubeRoot[2] satisfies the minimal polynomial x^3-2. Cos[20] satisfies the minimal polynomial 8x^3-6 x-1. The degree of either of these minimal polynomials is three. A number like Sqrt[Pi] does not satisfy any polynomial over the rationals at all. The three problems of antiquity were: (1) Duplicating a cube. Essentially, making a cube twice as ------------------ big in volume. (2) Trisecting the angle. Given an angle theta, find an angle -------------------- equal to theta/3. (3) Squaring the circle. Given a circle, find a square which ------------------- is equal in area. Duplicating a cube is impossible since it is impossible to construct a line segment of length CubeRoot[2]. If we could trisect 60 degrees, we could locate the point (Cos[20],Sin[20]). But we know that creating Cos[20] is impossible. Therefore, trisecting 60 degrees must be impossible. Any trisecting must work when applied to 60 degrees. Therefore, there is no such procedure. If we could square the circle, then we could create a square of side length Sqrt[Pi]. Then we could construct Pi. But to construct Pi is impossible. Thus we cannot square the circle of radius 1. Any circle squaring procedure must work on the circle of radius 1. Therefore, there is no such procedure. Solvability by radicals. ======================= In the preceding problem we discussed all the numbers that could be build out of +-*/ and extraction of square roots. We now wish to allow the extraction of any nth root. It is advantageous to limit the roots to p th roots where p is a prime. This is not really a limitation because we can get any nth root by sequentially extracting p th roots for the primary factors of n. We need some way of characterizing the elements which can be expressed by extraction of p th roots. The characterization is done using homomorphisms. A homomorphism preserves addition, and multiplication. f(a+b) = f(a)+f(b) f(ab) = f(a) f(b). The key to the proof is that polynomials have a very limited number of roots. If a1,a2, ..., an are the roots of a polynomial of degree n over the rationals, and h is a homomorphism, then h has to permute the roots among themselves. In this way homomorphisms become permutations. There are instances where there are 5 roots and there are 5! homomorphisms. That is, one can find a homomorphism which moves the roots by any permutation one would like. The polynomials with this property are irreducible. But not all irreducible polynomials have this property. If you take an irreducible polynomial x^p - b it has root r , rw, rw^2, rw^3, ..., rw^(p-1) where r is a p th root of b and w is a primitive p th root of unity. These roots when graphed on the complex plane form the vertices of a regular p-gon. Notice that once the image of r and w is known, then the image of all the other roots are known. f(rw^i) = f(r) f(w)^i. It is clear that for polynomials of the form x^p - b, one is not going to get n! homomorphisms. If you have an expression x created by +-*/ and extraction of p th roots, then you can consider x as being assembled a bit at a time by working from the inside out. One produces a sequence g1, g2, g3, ... each of which is obtained by taking a p th root of something expressible by +-*/ of the preceding elements. --------------------------------------------------------- | | | | |---------------------------- | |--------------------- | | |------------ 1/p1| 1/p2| 1/p3 | | Q | g1 | g2 | g3 .... x | | | | | | |------------ | | | |--------------------- | | |---------------------------- | | | | | | | --------------------------------------------------------- We can represent this as Q = Fo c F1 c F2 c F3 c ... c Fn where Fi+1 = Fi [ gi^(1/pi ] where gi is in Fi and x is in Fn. Given any homomorphism f, we can classify f by which of these fields it leaves fixed. All homomorphisms leave the rationals fixed. Q is the rationals. So we have a decreasing chain Ho > H1 > H2 > ... Hn where Hi leaves Fi fixed. Every f is in Ho. Hn contains only the identity. We can view all of these homomorphisms as permutations. Thus Ho is a group of permutations and all of the others are subgroups of Ho. Each Hi+1 is a normal subgroup of Hi. If we choose a polynomial where Ho is Sn, we would have a Solvable series of Sn. We know these do not exist for h >= 5. Since we can find a polynomial of degree 5 where Ho is S5, then we must not be able to solve that polynomial with radicals. We can solve polynomials of degree four by radicals because the series {I} c K4 c A4 c S4 is a solvable series for S4. We have shown something stronger than the fact that we cannot find a quintic formula. We have shown that one simply cannot express the roots using +-*/ and radicals. If there were a formula, then certainly the roots would be expressible by radicals. But it is at least conceivable, that one could express the roots by radicals without having a general formula. Closing Remarks =============== We cannot trisect the angle and we cannot construct a line segment of length cubeRoot[3]. At least we cannot using the rules of construction. If we take upon ourselves a bit of leeway and allow ourselves to mark the straightedge with marks one unit apart, then we can do both of these problems.