Revisions - MathOverflow

Return to Answer

fixed typos

view source

edited Jul 31 2010 at 18:16

This

Edit on July 31: Now the upper bound is not a complete answer tight (up to replacing n by O(n)). The improvement over the question, but here 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) is at most doubly-exponential with quadratic exponent, i.e., D(n) < 2^{2^cn² for some positive constant c>0 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^{2^O(n²⁾.}

The length of an algebraic number α

There is the sum of 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 coefficients proof of the integer-coefficient minimum polynomial of α.

Lemma 2following properties:

If algebraic numbers α and β have is an algebraic number of degree at most dand length at most L, then α+β, α−β, αβ, α/β |α| ≤ exp(dh(α)).

If p and √q are integers which are relatively prime, then h(p/q) = ln max{|p|,|q|}.

If α have length at most 2^{dand β are algebraic numbers, then h(α+β) ≤ h(α) + h(β) + ln 2}((d+1)L)^{2d.
Proof idea: Construct the minimum polynomials of α+β etc. by using resultants,}

If α and bound the lengths of the constructed polynomials by straightforward calculationβ are algebraic numbers, then h(αβ) ≤ h(α) + h(β).(end of proof idea of Lemma 2

If α is an algebraic number and n is an integer, then h(αⁿ) = |n|h(α). In particular, h(√α)=h(α)/2.

By combining Lemmas 1 and 2 and using the properties 2–5 and the mathematical induction, we obtain can prove that the length of zh(z_n is at most 2) ≤ 2^n²+n+1 = 2^{2^O(n ln 2}).

Since the length is an upper bound on By combining the height property 1 and the absolute value of a root of a polynomial is at most Lemma 1plus the height of the polynomial, we obtain that |z_n| is also at most 2≤ 2^O(n²)²ⁿ.

Remark

References

[Wal00] Michel Waldschmidt: I do not claim that the bound in Lemma 2 is close to optimal. However, even if Diophantine Approximation on Linear Algebraic Groups: Transcendence Properties of the bound Exponential Function in Lemma 2 is improved to, say, L^√(d), the upper bound on D(n) we obtain is still 2^{2^O(n²)}. In particularSeveral Variables, if D(n) < 2^{2^cn} for some constant c>0 for sufficiently large nSpringer, its proof cannot be obtained by improving the bound in Lemma 2 alone2000.

improved formatting and added discussion on improving the upper bound

view source

edited Jul 31 2010 at 0:15

Tsuyoshi Ito
1,349●6●15

This is not a complete answer to the question, but here is a proof that D(n) is at most doubly-exponential with quadratic exponent, i.e., D(n) < 2^{2^cn²} for some positive constant c>0 for sufficiently large 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 the lemmaLemma 1)

The length of an algebraic number α is the sum of the absolute values of the coefficients of the integer-coefficient minimum polynomial of α.

Lemma 2: If algebraic numbers α and β have degree at most d and length at most L, then α+β, α−β, αβ, α/β and √α have length at most 2^d²((d+1)L)^2d.(I obtained this by constructing

Proof idea: Construct the minimum polynomials of α+β etc. by using resultants, and dirty bound the lengths of the constructed polynomials by straightforward calculation. I do not claim that this bound is close to optimal.(end of proof idea of Lemma 2)

By combining this with the earlier bound on the degree Lemmas 1 and 2 and using the mathematical induction, we obtain that the length of z_n is at most 2^{2^n²+n+1} = 2^{2^O(n²)}.

Since the length is an upper bound on the height and the absolute value of a root of a polynomial is at most 1 plus the height of the polynomial, |z_n| is also at most 2^{2^O(n²)}.

Remark: I do not claim that the bound in Lemma 2 is close to optimal. However, even if the bound in Lemma 2 is improved to, say, L^√(d), the upper bound on D(n) we obtain is still 2^{2^O(n²)}. In particular, if D(n) < 2^{2^cn} for some constant c>0 for sufficiently large n, its proof cannot be obtained by improving the bound in Lemma 2 alone.

view source

answered Jul 29 2010 at 21:44

Tsuyoshi Ito
1,349●6●15

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

The length of an algebraic number α is the sum of the absolute values of the coefficients of the integer-coefficient minimum polynomial of α. If algebraic numbers α and β have degree at most d and length at most L, then α+β, α−β, αβ, α/β and √α have length at most 2^d²((d+1)L)^2d. (I obtained this by constructing the minimum polynomials of α+β etc. by using resultants and dirty calculation. I do not claim that this bound is close to optimal.) By combining this with the earlier bound on the degree and using the mathematical induction, we obtain that the length of z_n is at most 2^{2^n²+n+1} = 2^{2^O(n²)}.

Since the length is an upper bound on the height and the absolute value of a root of a polynomial is at most 1 plus the height of the polynomial, |z_n| is also at most 2^{2^O(n²)}.