Construction algorithm

In our previous post, we have learnt about Similar Triangles and the Right Triangle Altitude Theorem. Today, continuing our journey in the garden of geometry, we want to find answer to the following question

Given a line segment of length $r$, by compass and straightedge, what kind of shapes can we construct? 

There are two simple cases that we can see straightaway.

• We can construct a line segment whose length is a multiple of a given length, and
• We can divide a given line segment into a number of equal parts. 

Here are some examples

• Given a line segment $AB=r$, by compass and straightedge, we can easily construct a line segment $AC = 3r$.

• Given a line segment $AB=r$. Construct an arbitrary ray $Ax$ and on this ray, construct $C_1$, $C_2$, $C_3$, $C_4$, $C_5$ such that $$A C_1 = C_1 C_2 = C_2 C_3 = C_3 C_4 = C_4 C_5.$$ Through $C_1$, $C_2$, $C_3$, $C_4$, construct four lines parallel to $B C_5$ which intersect with $AB$ at $D_1$, $D_2$, $D_3$, $D_4$. Then we have $$A D_1 = D_1 D_2 = D_2 D_3 = D_3 D_4 = D_4 B = \frac{r}{5}$$

• Given a line segment $AB=r$, first construct $AC = 3r$ and then divide $AC$ into 5 equal parts then we have a line segment of length $\frac{3}{5} r$.

From these simple examples we deduce the following conclusion

Given a line segment of length $r$, and $\frac{p}{q}$ is a rational number, then by compass and straightedge, we can construct a line segment of length $\frac{p}{q} r$.

Let us now look at two examples which are a bit more sophisticated: construction of a regular pentagon and construction of a regular polygon with 17 sides.

To construct a regular pentagon, first we construct a circle and pick a point $P_0$ on it. If we can construct the point $H$ then from $H$ we can construct $P_1$, and from $P_1$ we can construct other vertices of the pentagon.

Suppose that $r$ is the radius of the circle, we have the following trigonometric identity
$$\angle P_0 O P_1 = \frac{2 \pi}{5}$$ $$OH = r \cos{\frac{2 \pi}{5}}  = r \frac{\sqrt{5}-1}{4}$$

So, in order to construct the pentagon, we need to construct the line segment $OH$ of length $\frac{\sqrt{5}-1}{4} r$.


Similarly, in order to construct the regular 17-gon in the picture below, we need to construct the line segment $OH = r \cos{\frac{2 \pi}{17}}$.

In 1796, at the age of 19, the mathematician Gauss made a breakthrough in solving the regular polygon construction problem. Using modulo arithmetic, Gauss calculated
$$\cos{\frac{2 \pi}{17}} = \frac{1}{16} \left( -1 + \sqrt{17} + \sqrt{34 - 2 \sqrt{17}} + 2 \sqrt{17 + 3 \sqrt{17} - \sqrt{34 - 2 \sqrt{17}} - 2 \sqrt{34 + 2 \sqrt{17}}} \right)$$
and showed that a regular 17-gon is constructible.

With the above two examples, have you spotted out any pattern yet?



Constructible numbers

Let us now define the concept of  "constructible numbers"

A number $\alpha$ is called a constructible number if $\alpha$ is obtained from integers by addition, subtraction, multiplication, division and taking square root.

For example,
$$\frac{3}{5} \mbox{ is a constructible number,}$$
$$\cos \frac{2 \pi}{5}=\frac{\sqrt{5}-1}{4} \mbox{ is a constructible number,}$$
$$\frac{\sqrt{\sqrt{2} + 5 \sqrt{3} - 2}}{\sqrt{\frac{2}{5}} + 1} \mbox{ is a constructible number.}$$

We have the following theorem

Fundamental theorem of compass-and-straightedge construction. Given a line segment of length $r$, and $\alpha$ is a constructible number, then by compass and straightedge, we can construct a line segment of length $\alpha \, r$.

We will prove this theorem by showing a construction algorithm.



Construction algorithm

Given three line segments of length $r$, $a r$ and $b r$. Using compass and straightedge, we can construct

• a line segment of length $(a+b)r$

• a line segment of length $(a−b)r$

• a line segment of length $(ab) r$ 

$AB$ is parallel to $CD$: $\frac{OD}{OC} = \frac{OA}{OB} = a \to OD = abr$

• a line segment of length $(a/b) r$ 

$AB$ is parallel to $CD$: $\frac{OD}{OC} = \frac{OA}{OB} = \frac{a}{b} \to OD = \frac{a}{b}r$

• a line segment of length $(\sqrt{ab}) r$ 

by the Right Triangle Altitude Theorem, $HC^2 = HA \times HB = ab r^2 \to HC = \sqrt{ab}r$

With the above construction algorithm, if $\alpha$ is a constructible number then from a line segment of length $r$, we can show step by step how to construct a line segment of length $\alpha r$.


Let us stop here for now. Next time, we will learn about Fermat's little theorem, modulo cycle and many other exciting stuff and then we will learn how to derive Gauss trigonometric identity
$$\cos{\frac{2 \pi}{17}} = \frac{1}{16} \left( -1 + \sqrt{17} + \sqrt{34 - 2 \sqrt{17}} + 2 \sqrt{17 + 3 \sqrt{17} - \sqrt{34 - 2 \sqrt{17}} - 2 \sqrt{34 + 2 \sqrt{17}}} \right)$$

Hope to see you again then!


Homework.

1. Prove that $$\cos \frac{2 \pi}{5}=\frac{\sqrt{5}-1}{4}$$

2. Use Moivre formula to find a polynomial of integer coefficients such that $\cos \frac{2 \pi}{17}$ is one of its roots.

3. We will use the notation $(PQ)$ to denote the line $PQ$, and notation $(P, PQ)$ to denote the circle centre at $P$ and of radius $PQ$.

Fundamental theorem of compass-and-straightedge construction.

Given a line segment $AB = r$. A point $M$ on the plane is said to be constructible from $AB$ if there exists a sequence of points $X_1$, $X_2$, ..., $X_n$ such that

• $X_1 = A$, $X_2 = B$ and $X_n = M$
• For any $3 \leq i \leq n$, the point $X_i$ is either the intersection point of two lines $(X_{k_1} X_{k_2})$ and $(X_{k_3} X_{k_4})$, or an intersection point of the line $(X_{k_1} X_{k_2})$ with the circle $(X_{k_3}, X_{k_3} X_{k_4})$, or an intersection point of the circle $(X_{k_1}, X_{k_1} X_{k_2})$ with the circle $(X_{k_3}, X_{k_3} X_{k_4})$, for some $1\leq k_1, k_2, k_3, k_4 < i$.

Draw a Cartesian coordinate system $Axy$ where the point $B$ is on $Ax$. Each point $M$ on the plane will have a coordinate $M(x,y)$.

Prove that a point $M(x,y)$ is constructible from $AB$ if and only if $x = \alpha_1 r$ and $y = \alpha_2 r$ where $\alpha_1$ and $\alpha_2$ are constructible numbers.

4. Write about one of your favourite construction problems. Use google.com to learn more about that problem.