Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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)$?
share|improve this question
2  
Can you indicate the argument for your lower bound? Offhand I can't see how to do better than $D(n) \ge 2^n$. –  Mark Meckes Jul 22 '10 at 18:39
1  
Repeated squaring gives that lower bound. –  Sam Nead Jul 22 '10 at 19:30
    
Thanks, I misunderstood what you could do with the ruler. I thought you could only get the line segment between the two points. –  Mark Meckes Jul 23 '10 at 3:26

6 Answers 6

up vote 12 down vote accepted

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.

share|improve this answer

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...

share|improve this answer

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.

share|improve this answer

Here is a construction showing that $D(n) \ge 2^{2^{n-O(1)}}$. This shows that any constant $c<1$ in the original question can be achieved for sufficiently large $n$. The construction assumes some fixed (but arbitrary) positive integer $m$.

  1. Using a constant number of moves, draw both the real and imaginary axes, and mark the points $A = -i$ and $B = -1$. Let $z_0 = 1$.

  2. For $k = 1,2,3,\ldots,m$, do

a) If $k$ is odd, then draw a circle centered at $A$ and passing through $z_{k-1}$. Let $z_k$ be the intersection of this circle with the positive imaginary axis.

b) If $k$ is even, then draw a circle centered at $B$ and passing through $z_{k-1}$. Let $z_k$ be the intersection of this circle with the positive real axis.

  1. Using a constant number of moves, construct the reciprocal of $|z_m|$.

Some things to observe:

  1. Step 2 uses exactly $m$ moves, so the total number of moves is $n = m + O(1)$.
  2. $z_k > 0$ for all even $k$, and $-iz_k > 0$ for all odd $k$.
  3. For all $k\in\{1,\ldots,m\}$, we have $|z_k| = \sqrt{1+|z_{k-1}|^2}-1 \le |z_{k-1}|^2/2$.
  4. The previous fact combined with induction on $k$ gives $|z_k| \le 2^{-(2^k-1)}$.
  5. Thus the point constructed in Step 3 has norm at least $2^{2^m-1} \ge 2^{2^{n-O(1)}}$.
share|improve this answer

I just recently posted this link as an answer to this MO question. Is this what you want?

share|improve this answer
    
Although the title of the questions mentions "fast", the body of the questions asks about how much paper you need for a given construction in terms of how many steps it has. –  lhf Jul 22 '10 at 22:05
1  
Thanks, Igor, that reference is a good lead. It doesn't necessarily answer the question because the maximum distance between marked points will not generally be an integer, but it is a start. About the title of the question, by "fast" I am referring to how fast constructed points can move away from one another as a function of the number of moves. My apologies if that caused confusion. –  John Watrous Jul 23 '10 at 1:09

I'm not sure but perhaps the classic Géométrographie by Lemoine discusses this space complexity as well as time complexity. See also http://www.cs.mcgill.ca/~sqrt/cons/constructions.html and http://geometrographie.org/ .

I think I once saw a paper about space complexity but I can't find it right now.

share|improve this answer
    
Your first link is broken. Perhaps this one works: en.wikipedia.org/wiki/Emile_Lemoine –  Sam Nead Jul 23 '10 at 8:46
    
@Sam: fixed, thanks. –  lhf Jul 23 '10 at 11:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.