Difference between revisions of "Constructible number"

(Statement of theorem)
m
 
(2 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 also say that the point <math>(x,y)</math> is constructible). It is easy to show that <math>x+yi</math> is constructible iff 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 our two definitions coincide when <math>z</math> is a real number.)
+
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==
 
==Characterization Theorem==
 
It is possible to completely characterize the set of all constructible numbers:
 
It is possible to completely characterize the set of all constructible numbers:
  
A complex number <math>\alpha</math> 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.
+
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>.
 
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>.
Line 12: Line 12:
 
This condition can be rephrased in terms of [[field theory]] as follows:
 
This condition can be rephrased in terms of [[field theory]] as follows:
  
A complex number <math>\alpha</math> is constructible iff 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>).  
+
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 iff <math>K = F(\sqrt{a})</math> for some <math>a\in F</math> with <math>\sqrt{a}\not\in F</math>, 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?)''
+
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 it's [[minimal polynomial]] has degree <math>2^n</math>.
+
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]].
 
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 07:39, 21 August 2009

We say that a real number $x$ is constructible if a line segment of length $|x|$ can be constructed with a straight edge and compass starting with a segment of length $1$.

We say that a complex number $z = x+yi$ is constructible if $x$ and $y$ are both constructible, and we also say that the point $(x,y)$ is constructible. One can show that $x+yi$ is constructible if and only if the point $(x,y)$ can be constructed with a straight edge and compass in the Cartesian plane starting with the points $(0,0)$ and $(1,0)$. Notice that a real number $x$ 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 $\alpha$ 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: $2,\frac{5}{2},\sqrt{6}$ and $\frac{2\sqrt{7}+\sqrt{\frac{4}{3}+\sqrt{87}}}{9+\sqrt{3}+\sqrt{\sqrt{5}+2\sqrt{19}}}$, but one cannot construct a segment of length $\sqrt[3]{3}$.

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

A complex number $\alpha$ is constructible if and only if there is a chain of field extensions $\mathbb Q = K_0\subseteq K_1\subseteq \cdots\subseteq K_n = \mathbb Q(\alpha)$ such that each extension $K_i\subseteq K_{i+1}$ is quadratic (i.e. $[K_{i+1}:K_i]=2$).

This is equivalent because the field extension $F\subseteq K$ is quadratic if and only if $K = F(\sqrt{a})$ for some $a\in F$ with $\sqrt{a}\not\in F$. 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 $[\mathbb Q(\alpha):\mathbb Q] = 2^n$ for some nonnegative integer $n$, or equivalently that $\alpha$ is algebraic and its minimal polynomial has degree $2^n$.

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 $K$ 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 $K$ is precisely the set of constructible numbers. Note that (by definition) $K$ is a field and for all $a\in K$, $\sqrt{a}\in K$ as well.

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

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

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 $\theta$ (the step in which $\theta$ is actually constructed) must be of type (C), (D) or (E). Hence, as all previously constructed points are in $K$, $\theta$ must have one of the following must be true:

  • (i) $\theta$ is the intersection of the lines $zw$ and $z'w'$, where $z,w,z',w'\in K$.
  • (ii) $\theta$ is the intersection of the circle with center $z$ and radius $r$ and the line $z'w'$, where $z,r,z',w'\in K$.
  • (iii) $\theta$ is the intersection of circles with centers $z$ and $z'$ and radii $r$ and $r'$, where $z,r,z',r'\in K$.

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

Case 1: Note the if $z=a+bi$ and $w=c+di$ then the line $zw$ has equation $y-b = \frac{d-b}{c-a}(x-a)$, which can be rewritten in the form $Ax+By = C$ where $A,B,C\in K$. So now $\theta = x+yi$ satisfies the system of equations: \begin{align*} Ax+By&=C\\ A'x+B'y&=C' \end{align*} Solving this gives $x = \frac{CB'-C'B}{AB'-A'B}$ and $y = \frac{AC'-A'C}{AB'-A'B}$, so in particular, $x,y\in K$, so $\theta = x+yi\in K$, as desired.

Case 2: The equation of a circle with center $z=h+ki$ and radius $r$ is $(x-h)^2+(y-k)^2=r^2$. Expressing the equation of the line $z'w'$ as in case 1, we get the system of equations: \begin{align*} (x-h)^2+(y-k)^2&=r^2\\ A'x+B'y&=C' \end{align*} Solving the second equation for $y$ and substituting the result into the first equation yields (upon expanding and simplifying) $A''x^2+B''x+C''=0$, where $A'',B'',C''\in K$. Now using the quadratic formula (and remembering that $a\in K\Rightarrow \sqrt{a}\in K$) gives $x = \frac{-B''\pm\sqrt{B''^2-4A''C''}}{2A''}\in K$. And now it easily follows that $y = \frac{C'-A'x}{B'}\in K$ and $\theta = x+yi\in K$, as desired.

Case 3: Expressing the equations of the circles as in Case 2 gives the system of equations: \begin{align*} (x-h)^2+(y-k)^2&=r^2\\ (x-h')^2+(y-k')^2&=r'^2 \end{align*} Subtracting the first equation from the second yields the system: \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*} So now upon setting $A' = 2(h'-h)$, $B' = 2(k'-k)$ and $C' = r^2-r'^2-h^2+h'^2-k^2+k'^2$ (note that $A',B',C'\in K$) this reduces to case 2. So we again have $\theta\in K$.

Thus in all cases $\theta\in K$, yielding a contradiction, and finishing the proof.

Invalid username
Login to AoPS