# Difference between revisions of "Constructible number"

(Statement of theorem) |
(Proof (could probably be cleaned up a bit)) |
||

Line 19: | Line 19: | ||

Using this theorem one can easily answer many classical construction problems, such as the [[three Greek problems of antiquity]] and the question of [[constructible polygon|which regular polygons are constructible]]. | Using this theorem one can easily answer many classical construction problems, such as the [[three Greek problems of antiquity]] and the question of [[constructible polygon|which regular polygons are constructible]]. | ||

+ | |||

+ | ==Proof== | ||

+ | Let <math>K</math> represent the set of complex numbers which can be obtained from the rational numbers in a finite number of steps using only the operations addition, subtraction, multiplication, division, and taking square roots. We wish to show that <math>K</math> is precisely the set of constructible numbers. Note that (by definition) <math>K</math> is a field and for all <math>a\in K</math>, <math>\sqrt{a}\in K</math> as well. | ||

+ | |||

+ | First it is straightforward to show that, given the points on the [[complex plane]] corresponding to <math>0,1,z</math> and <math>w</math>, one can construct the points <math>z+w</math>, <math>z-w</math>, <math>zw</math>, <math>\frac{z}{w}</math> and <math>\sqrt{z}</math> using basic ruler and compass constructions. Hence all numbers in <math>K</math> are indeed constructible. | ||

+ | |||

+ | Now we claim that all constructible numbers lie in <math>K</math>. Assume that this is not the case. Consider the set <math>S</math> of all constructible numbers which are not in <math>K</math>. Take some <math>\theta\in S</math> which can be constructed in the minimal number of steps. Then clearly in the construction of <math>\theta</math> all points constructed before <math>\theta</math> must lie in <math>K</math>. Let <math>\theta=x+yi</math>. | ||

+ | |||

+ | Notice that every step in a geometric construction must consist of one of the following: | ||

+ | *(A) Connecting two previously constructed points with a line. | ||

+ | *(B) Drawing a circle centered at an previously constructed point with an previously constructed radius. | ||

+ | *(C) Finding the intersection point of two previously constructed lines. | ||

+ | *(D) Finding the intersection point(s) of a previously constructed line and a previously constructed circle. | ||

+ | *(E) Finding the intersection point(s) of two previously constructed circles. | ||

+ | |||

+ | Obviously the final step in the construction of <math>\theta</math> (the step in which <math>\theta</math> is actually constructed) must be of type (C), (D) or (E). Hence, as all previously constructed points are in <math>K</math>, <math>\theta</math> must have one of the following must be true: | ||

+ | *(i) <math>\theta</math> is the intersection of the lines <math>zw</math> and <math>z'w'</math>, where <math>z,w,z',w'\in K</math>. | ||

+ | *(ii) <math>\theta</math> is the intersection of the circle with center <math>z</math> and radius <math>r</math> and the line <math>z'w'</math>, where <math>z,r,z',w'\in K</math>. | ||

+ | *(iii) <math>\theta</math> is the intersection of circles with centers <math>z</math> and <math>z'</math> and radii <math>r</math> and <math>r'</math>, where <math>z,r,z',r'\in K</math>. | ||

+ | |||

+ | We now show that in each of these cases we must have <math>\theta\in K</math>, giving a contradiction. | ||

+ | |||

+ | '''Case 1:''' | ||

+ | Note the if <math>z=a+bi</math> and <math>w=c+di</math> then the line <math>zw</math> has equation <math>y-b = \frac{d-b}{c-a}(x-a)</math>, which can be rewritten in the form <math>Ax+By = C</math> where <math>A,B,C\in K</math>. So now <math>\theta = x+yi</math> satisfies the system of equations: | ||

+ | <cmath> | ||

+ | \begin{align*} | ||

+ | Ax+By&=C\\ | ||

+ | A'x+B'y&=C' | ||

+ | \end{align*} | ||

+ | </cmath> | ||

+ | Solving this gives <math>x = \frac{CB'-C'B}{AB'-A'B}</math> and <math>y = \frac{AC'-A'C}{AB'-A'B}</math>, so in particular, <math>x,y\in K</math>, so <math>\theta = x+yi\in K</math>, as desired. | ||

+ | |||

+ | '''Case 2:''' | ||

+ | The equation of a circle with center <math>z=h+ki</math> and radius <math>r</math> is <math>(x-h)^2+(y-k)^2=r^2</math>. Expressing the equation of the line <math>z'w'</math> as in case 1, we get the system of equations: | ||

+ | <cmath> | ||

+ | \begin{align*} | ||

+ | (x-h)^2+(y-k)^2&=r^2\\ | ||

+ | A'x+B'y&=C' | ||

+ | \end{align*} | ||

+ | </cmath> | ||

+ | Solving the second equation for <math>y</math> and substituting the result into the first equation yields (upon expanding and simplifying) <math>A''x^2+B''x+C''=0</math>, where <math>A'',B'',C''\in K</math>. Now using the quadratic formula (and remembering that <math>a\in K\Rightarrow \sqrt{a}\in K</math>) gives <math>x = \frac{-B''\pm\sqrt{B''^2-4A''C''}}{2A''}\in K</math>. And now it easily follows that <math>y = \frac{C'-A'x}{B'}\in K</math> and <math>\theta = x+yi\in K</math>, as desired. | ||

+ | |||

+ | '''Case 3:''' | ||

+ | Expressing the equations of the circles as in Case 2 gives the system of equations: | ||

+ | <cmath> | ||

+ | \begin{align*} | ||

+ | (x-h)^2+(y-k)^2&=r^2\\ | ||

+ | (x-h')^2+(y-k')^2&=r'^2 | ||

+ | \end{align*} | ||

+ | </cmath> | ||

+ | Subtracting the first equation from the second yields the system: | ||

+ | <cmath> | ||

+ | \begin{align*} | ||

+ | (x-h)^2+(y-k)^2&=r^2\\ | ||

+ | 2(h'-h)x+2(k'-k)y &= r^2-r'^2-h^2+h'^2-k^2+k'^2 | ||

+ | \end{align*} | ||

+ | </cmath> | ||

+ | So now upon setting <math>A' = 2(h'-h)</math>, <math>B' = 2(k'-k)</math> and <math>C' = r^2-r'^2-h^2+h'^2-k^2+k'^2</math> (note that <math>A',B',C'\in K</math>) this reduces to case 2. So we again have <math>\theta\in K</math>. | ||

+ | |||

+ | Thus in all cases <math>\theta\in K</math>, yielding a contradiction, and finishing the proof. | ||

[[Category:Geometry]] | [[Category:Geometry]] | ||

[[Category:Field theory]] | [[Category:Field theory]] |

## Revision as of 23:38, 20 August 2009

We say that a real number is **constructible** if a segment of length can be constructed with a straight edge and compass starting with a segment of length .

We say that a complex number is constructible if and are both constructible (we also say that the point is constructible). It is easy to show that is constructible iff the point can be constructed with a straight edge and compass in the cartesian plane starting with the points and . (Notice that our two definitions coincide when is a real number.)

## Characterization Theorem

It is possible to completely characterize the set of all constructible numbers:

A complex number is constructible iff it can be formed from the rational numbers in a finite number of steps using only the operations addition, subtraction, multiplication, division, and taking square roots.

For instance, this means one can construct segments of length: and , but one cannot construct a segment of length .

This condition can be rephrased in terms of field theory as follows:

A complex number is constructible iff there is a chain of field extensions such that each extension is quadratic (i.e. ).

This is equivalent because the field extension is quadratic iff for some with , so taking a square root in the above construction is equivalent to taking at most a quadratic extension of a field, while adding, subtracting, multiplying or dividing does not add anything to the field. *(Does someone else want to phrase that better?)*

Using this second characterization (and the tower law) we get the necessary (but *not* sufficient) condition that for some nonnegative integer , or equivalently that is algebraic and it's minimal polynomial has degree .

Using this theorem one can easily answer many classical construction problems, such as the three Greek problems of antiquity and the question of which regular polygons are constructible.

## Proof

Let represent the set of complex numbers which can be obtained from the rational numbers in a finite number of steps using only the operations addition, subtraction, multiplication, division, and taking square roots. We wish to show that is precisely the set of constructible numbers. Note that (by definition) is a field and for all , as well.

First it is straightforward to show that, given the points on the complex plane corresponding to and , one can construct the points , , , and using basic ruler and compass constructions. Hence all numbers in are indeed constructible.

Now we claim that all constructible numbers lie in . Assume that this is not the case. Consider the set of all constructible numbers which are not in . Take some which can be constructed in the minimal number of steps. Then clearly in the construction of all points constructed before must lie in . Let .

Notice that every step in a geometric construction must consist of one of the following:

- (A) Connecting two previously constructed points with a line.
- (B) Drawing a circle centered at an previously constructed point with an previously constructed radius.
- (C) Finding the intersection point of two previously constructed lines.
- (D) Finding the intersection point(s) of a previously constructed line and a previously constructed circle.
- (E) Finding the intersection point(s) of two previously constructed circles.

Obviously the final step in the construction of (the step in which is actually constructed) must be of type (C), (D) or (E). Hence, as all previously constructed points are in , must have one of the following must be true:

- (i) is the intersection of the lines and , where .
- (ii) is the intersection of the circle with center and radius and the line , where .
- (iii) is the intersection of circles with centers and and radii and , where .

We now show that in each of these cases we must have , giving a contradiction.

**Case 1:**
Note the if and then the line has equation , which can be rewritten in the form where . So now satisfies the system of equations:
Solving this gives and , so in particular, , so , as desired.

**Case 2:**
The equation of a circle with center and radius is . Expressing the equation of the line as in case 1, we get the system of equations:
Solving the second equation for and substituting the result into the first equation yields (upon expanding and simplifying) , where . Now using the quadratic formula (and remembering that ) gives . And now it easily follows that and , as desired.

**Case 3:**
Expressing the equations of the circles as in Case 2 gives the system of equations:
Subtracting the first equation from the second yields the system:
So now upon setting , and (note that ) this reduces to case 2. So we again have .

Thus in all cases , yielding a contradiction, and finishing the proof.