Let us systematically generate all constructible points in the plane. We begin with just two points, which specify the unit distance.

enter image description here

With the straightedge, we may construct the line joining them. And with the compass, we may construct the two circles centered at each of them, having that unit segment as radius. These circles intersect each other and the line, creating four additional points of intersection. Thus, we have now six points in all.

enter image description here

Using these six points, we proceed to the next stage, constructing all possible lines and circles using those six points, and finding the resulting points of intersection.

enter image description here

I believe that we now have 203 points. Let us proceed in this way to systematically construct all constructible points in the plane, in a hierarchy of finite stages. At each stage, we form all possible lines and circles that may be formed from our current points using straightedge and compass, and then we find all points of intersection from the resulting figures.

This produces what I call the constructibility sequence:

$$2\qquad\qquad 6\qquad\qquad 203\qquad\qquad ?$$

Each entry is the number of points constructed at that stage. I have a number of questions about the constructibility sequence:

Question 1. What is the next constructibility number?

There is no entry in the online encyclopedia of integer sequences beginning 2, 6, 203, and so I would like to create an entry for the constructibility sequence. But they request at least four numbers, and so we seem to need to know the next number. I'm not sure exactly how to proceed with this, since if one proceeds computationally, then one will inevitably have to decide if two very-close points count as identical are not, and I don't see any principled way to ensure that this is done correctly. So it seems that one will need to proceed with some kind of idealized geometric calculus, which gets the right answer about coincidence of intersection points.

Question 2. What kind of asymptotic upper bounds can you prove on the growth of the constructibility sequence?

At each stage, every pair of points determine a line and two circles. And every intersection point is realized as the intersection of two lines, two circles or a line and circle, which have at most two intersection points in each case. So a rough upper bound is that from $k$ points, we produce no more than $3k^2$ many lines and circles, and so at most $(3k^2)^2$ many pairs of line and circles, and so at most $2(3k^2)^2$ many points of intersection. This leads to an upper bound of growth something like $18^n2^{4^n}$ after $n$ stages. Can anyone give a better bound?

Question 3. And what of lower bounds?

I suspect that the sequence grows very quickly, probably doubly exponentially. But to prove this, we would seem to need to identify a realm of construction patterns where there is little interference of intersection coincidence, so that one can be sure of a certain known growth in new points.

  • 2
    $\begingroup$ I used Mathematica to check your numbers and can confirm 203 points at third stage. But couldn't find the fourth stage with the same code, it takes too much time. $\endgroup$ – Aretino Oct 3 at 10:18
  • 2
    $\begingroup$ Even if it is 1000 times smaller, it's still too big for a naive Mathematica program. $\endgroup$ – Andrej Bauer Oct 3 at 16:37
  • 2
    $\begingroup$ I am told there's an OCaml library for constructible numbers. That would be fast enough, I am trying to get my hands on it. $\endgroup$ – Andrej Bauer Oct 3 at 22:41
  • 3
    $\begingroup$ The traditional use of the compass is to place one end on each point and to draw the circle. The compass equivalence theorem asserts that one can also simulate the operation of carrying a radius to another center point, but this takes more steps. So in the universal construction process, those circles come a bit later. $\endgroup$ – JDH Oct 4 at 20:54
  • 2
    $\begingroup$ I've checked that the number of distinct lines on the next step is exactly 17562, using minimal polynomials and exact arithmetic. I double-checked this number using floating point approximations to more than 25 places. I'm currently computing the number of circles. The exact arithmetic will take a bit of time, but the same floating point calculation finishes quickly and gives 32719 circles. $\endgroup$ – Pace Nielsen Oct 8 at 23:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.