*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<sup>2<sup>cn</sup></sup> for some positive constant c&gt;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<sub>0</sub>=0 and z<sub>1</sub>=1, and any z<sub>n</sub> (n≥2) can be obtained from earlier numbers by addition, subtraction, multiplication, division or square root.  The claim follows if |z<sub>n</sub>| &lt; 2<sup>2<sup>O(n)</sup></sup>.

<strong>Lemma 1</strong>: The degree of z<sub>n</sub> over ℚ is at most 2<sup>n</sup>.

Proof: Let F<sub>n</sub>=ℚ(z<sub>0</sub>, …, z<sub>n</sub>) be the minimum field containing ℚ∪{z<sub>0</sub>, …, z<sub>n</sub>}.  Then F<sub>0</sub>=ℚ, and F<sub>n</sub> is either equal to F<sub>n−1</sub> or an extension of F<sub>n−1</sub> 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<sub>n</sub>:F<sub>n−1</sub>] is either 1 or 2.  By the degree formula, it holds that [F<sub>n</sub>:ℚ] = [F<sub>n</sub>:F<sub>0</sub>] = [F<sub>n</sub>:F<sub>n−1</sub>][F<sub>n−1</sub>:F<sub>n−2</sub>]…[F<sub>1</sub>:F<sub>0</sub>] ≤ 2<sup>n</sup>.  Therefore, the degree of every element in F<sub>n</sub> over ℚ is also at most 2<sup>n</sup>.  (end of proof of Lemma 1)

There is a function called the <em>Weil absolute logarithmic height</em> 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(α<sup>n</sup>) = |n|h(α).  In particular, h(√α)=h(α)/2.

By using the properties 2–5 and the mathematical induction, we can prove that h(z<sub>n</sub>) ≤ 2<sup>n</sup> ln 2.  By combining the property 1 and Lemma 1, we obtain that |z<sub>n</sub>| ≤ 2<sup>2<sup>2n</sup></sup>.

References

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