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) < 2^2cn 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 z₀=0 and z₁=1, and any z_n (n≥2) can be obtained from earlier numbers by addition, subtraction, multiplication, division or square root. The claim follows if |z_n| < 2^2O(n).

Lemma 1: The degree of z_n over ℚ is at most 2ⁿ.

Proof: Let F_n=ℚ(z₀, …, z_n) be the minimum field containing ℚ∪{z₀, …, z_n}. Then F₀=ℚ, and F_n is either equal to F_n−1 or an extension of F_n−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 [F_n:F_n−1] is either 1 or 2. By the degree formula, it holds that [F_n:ℚ] = [F_n:F₀] = [F_n:F_n−1][F_n−1:F_n−2]…[F₁:F₀] ≤ 2ⁿ. Therefore, the degree of every element in F_n over ℚ is also at most 2ⁿ. (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|h(α). In particular, h(√α)=h(α)/2.

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

References

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

Up to constant factors (i.e. replacing n by cn), the question is equivalent (up to constant factors) to asking what is the largest number that can be generated by an arithmetic circuit of complexity n using 0, 1, the arithmetic operations +, -, *, /, and the square root operation, since each ruler-and-compass operation can be modeled by a circuit of complexity O(1) (and vice versa), basically because of the quadratic formula.

It then seems to me from induction that the numbers one generates after n steps must be algebraic numbers of degree growing at most exponentially in n, and height growing at most double exponentially in n, which matches the lower bound mentioned in the post.

EDIT: Actually, the naive bounds are worse than I first thought. Taking square roots and reciprocals (or negation) is not a problem, but adding or multiplying two algebraic numbers can square the degree and raise the heights to a power comparable to the degree (using resultants etc.) That only gives us a double exponential bound on the degree and a triple exponential bound on the height, so there is a gap of one exponential between the easy upper and lower bounds...

According to this paper (MR0949111 Davenport, James H. Heintz, Joos Real quantifier elimination is doubly exponential. J. Symbolic Comput. 5 (1988), no. 1-2, 29--35) the problem of deciding the truth of a question in the theory of real closed fields (a slight extension of Euclidean geometry) is doubly exponential: the time needed to decide the truth of a sentence of length n can be as much as 2^2^cn, and I think there is an algorithm to do it in this time. This is about the same as the bound for D(n) given in the question. I have a sort of hunch that the 2 bounds may be related, but I can't offhand see a direct connection between them.