Difference between revisions of "Constructible number"
m (slightly different statement of definition) |
m |
||
(3 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
− | We say that a [[real number]] <math>x</math> is '''constructible''' if a segment of length <math>|x|</math> can be constructed with a [[straight edge]] and [[compass]] starting with a segment of length <math>1</math>. | + | We say that a [[real number]] <math>x</math> is '''constructible''' if a [[line segment]] of length <math>|x|</math> can be constructed with a [[straight edge]] and [[compass]] starting with a segment of length <math>1</math>. |
− | We say that a complex number <math>z = x+yi</math> is constructible if <math>x</math> and <math>y</math> are both constructible | + | We say that a [[complex number]] <math>z = x+yi</math> is constructible if <math>x</math> and <math>y</math> are both constructible, and we also say that the point <math>(x,y)</math> is constructible. One can show that <math>x+yi</math> is constructible if and only if the point <math>(x,y)</math> can be constructed with a [[straight edge]] and [[compass]] in the [[Cartesian plane]] starting with the points <math>(0,0)</math> and <math>(1,0)</math>. Notice that a real number <math>x</math> is constructible as a real number if and only if it is constructible as a complex number, i.e., our two definitions coincide in this case. |
+ | ==Characterization Theorem== | ||
+ | It is possible to completely characterize the set of all constructible numbers: | ||
+ | |||
+ | A complex number <math>\alpha</math> is constructible if and only if 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 root]]s. | ||
+ | |||
+ | For instance, this means one can construct segments of length: <math>2,\frac{5}{2},\sqrt{6}</math> and <math>\frac{2\sqrt{7}+\sqrt{\frac{4}{3}+\sqrt{87}}}{9+\sqrt{3}+\sqrt{\sqrt{5}+2\sqrt{19}}}</math>, but one cannot construct a segment of length <math>\sqrt[3]{3}</math>. | ||
+ | |||
+ | This condition can be rephrased in terms of [[field theory]] as follows: | ||
+ | |||
+ | A complex number <math>\alpha</math> is constructible if and only if there is a chain of [[field extension]]s <math>\mathbb Q = K_0\subseteq K_1\subseteq \cdots\subseteq K_n = \mathbb Q(\alpha)</math> such that each extension <math>K_i\subseteq K_{i+1}</math> is quadratic (i.e. <math>[K_{i+1}:K_i]=2</math>). | ||
+ | |||
+ | This is equivalent because the field extension <math>F\subseteq K</math> is quadratic if and only if <math>K = F(\sqrt{a})</math> for some <math>a\in F</math> with <math>\sqrt{a}\not\in F</math>. Therefore, 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 do not add anything to the field. | ||
+ | |||
+ | Using this second characterization (and the [[tower law]]) we get the necessary (but ''not'' sufficient) condition that <math>[\mathbb Q(\alpha):\mathbb Q] = 2^n</math> for some nonnegative integer <math>n</math>, or equivalently that <math>\alpha</math> is [[algebraic]] and its [[minimal polynomial]] has degree <math>2^n</math>. | ||
+ | |||
+ | 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]] |
Latest revision as of 08:39, 21 August 2009
We say that a real number is constructible if a line 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, and we also say that the point
is constructible. One can show that
is constructible if and only if the point
can be constructed with a straight edge and compass in the Cartesian plane starting with the points
and
. Notice that a real number
is constructible as a real number if and only if it is constructible as a complex number, i.e., our two definitions coincide in this case.
Characterization Theorem
It is possible to completely characterize the set of all constructible numbers:
A complex number is constructible if and only if 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 if and only if there is a chain of field extensions
such that each extension
is quadratic (i.e.
).
This is equivalent because the field extension is quadratic if and only if
for some
with
. Therefore, 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 do not add anything to the field.
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 its 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.