Difference between revisions of "Constructible number"

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.

@@ 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==
 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>.
@@ Line 12: / Line 12: @@
 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]].
+==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\\
+(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:Field theory]]

Page

Toolbox

Search

Difference between revisions of "Constructible number"

Latest revision as of 07:39, 21 August 2009

Characterization Theorem

Proof