This may be more of a recreational mathematics question than a research question, but I have wondered about it for a while. I hope it is not inappropriate for MO.


Consider the standard assumptions for ruler and compass constructions: We have an infinitely large sheet of paper, which we associate with the complex plane, that is initially blank aside from the points 0 and 1 being marked. In addition we have an infinite ruler and a compass that can be stretched to an arbitrary length.


Let us define a *move* to be one of the two actions normally associated with a ruler and compass:


1. Use the ruler to draw the line defined by any two distinct points already marked on the paper.
2. Stretch the compass from any one marked point to another and draw the resulting circle.


Assume that all intersection points among lines and circles drawn by these operations are automatically marked on the paper. 


Now define $D(n)$ to be the maximum distance between any two marked points that can be constructed in this way with $n$ moves.


Questions:


1. Is anyone aware of results about the function $D(n)$ or something equivalent?
2. It is not difficult to prove $D(n) > 2^{2^{cn}}$ for some positive constant $c$ for sufficiently large $n$. Can one do better? If so, can one prove an upper bound on $D(n)$?



How fast are a ruler and compass?
*Edit on July 31: Now the upper bound is tight (up to replacing n by O(n)). The improvement over the older version is in the argument after Lemma 1. Now we consider the Weil absolute logarithmic height of an algebraic number instead of the length.*


Here is a proof that D(n) < 22cn for some positive constant c>0 for sufficiently large n. In other words, the answer to the “can one do better” part of the question 2 is negative.


As Terry Tao pointed out, this problem can be rephrased in the algebraic form. We have z0=0 and z1=1, and any zn (n≥2) can be obtained from earlier numbers by addition, subtraction, multiplication, division or square root. The claim follows if |zn| < 22O(n).


**Lemma 1**: The degree of zn over ℚ is at most 2n.


Proof: Let Fn=ℚ(z0, …, zn) be the minimum field containing ℚ∪{z0, …, zn}. Then F0=ℚ, and Fn is either equal to Fn−1 or an extension of Fn−1 obtained by adjoining a square root. Since adjoining a square root of a non-square element gives an extension of degree 2, the extension degree [Fn:Fn−1] is either 1 or 2. By the degree formula, it holds that [Fn:ℚ] = [Fn:F0] = [Fn:Fn−1][Fn−1:Fn−2]…[F1:F0] ≤ 2n. Therefore, the degree of every element in Fn over ℚ is also at most 2n. (end of proof of Lemma 1)


There is a function called the *Weil absolute logarithmic height* h(α) defined on algebraic numbers α which takes nonnegative real values. See Section 3.2 of [Wal00] for its definition and the proof of the following properties:


1. If α is an algebraic number of degree d, then |α| ≤ exp(dh(α)).
2. If p and q are integers which are relatively prime, then h(p/q) = ln max{|p|,|q|}.
3. If α and β are algebraic numbers, then h(α+β) ≤ h(α) + h(β) + ln 2.
4. If α and β are algebraic numbers, then h(αβ) ≤ h(α) + h(β).
5. If α is an algebraic number and n is an integer, then h(αn) = |n|h(α). In particular, h(√α)=h(α)/2.


By using the properties 2–5 and the mathematical induction, we can prove that h(zn) ≤ 2n ln 2. By combining the property 1 and Lemma 1, we obtain that |zn| ≤ 222n.


References


[Wal00] Michel Waldschmidt: *Diophantine Approximation on Linear Algebraic Groups: Transcendence Properties of the Exponential Function in Several Variables*, Springer, 2000.


