Difference between revisions of "Constructible number"

(Proof (could probably be cleaned up a bit))
m
 
(One intermediate revision by the same user 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]].

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