Let us systematically generate all constructible points in the plane. We begin with just two points, which specify the unit distance.
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.
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.
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. [Update: The sequence now exists as A333944.]
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.
Best Answer
I have written some Haskell code to compute the next number in the constructibility sequence. It's confirmed everything we have already established and gave me the following extra results:
There are $149714263$ line-line intersections at the 4th step (computed in ~14 hours). Pace Nielsen's approximation was only off by 8! This includes some points that are between a distance of $10^{-12}$ and $10^{-13}$ from each other.
I have found the fourth number in the constructibility sequence: $$1723816861$$ I computed this by splitting the first quadrant into sections along the x-axis, computing values in these sections and combining them. The program was not parallel, but the work was split amongst 6 process on 3 machines. It took approximately 6 days to complete and each process never used more than 5GB of RAM.
My data can be found here. I've produced these two graphs from my data, which give a sense of how the points are distributed:
If we focus at the area from $0$ to $1$ we get:
Implementation Details:
I represent constructible reals as pairs of a 14 decimal digit approximation (using ireal) and a symbolic represenation (using constructible). This is done to speed up comparisons: the approximations give us quick but partial comparisons functions, while the symbolic representation gives us slower but total comparison functions.
Lines are represented by a pair $\langle m, c \rangle$ such that $y = mx + c$. To deal with vertical lines, we create a data-type that's enhanced with an infinite value. Circles are triples $\langle a, b, r \rangle$ such that $(x-a)^2 + (y-b)^2 = r^2$.
I use a sweep-line algorithm to compute the number of intersections in a given rectangle. It extends the Bentley-Ottoman Algorithm to allow the checking of intersections between circles as well as lines. The idea behind the algorithm is that we have a vertical line moving from the left to right face of the rectangle. We think of this line as a strictly ordered set of objects (lines and circles). This requires some care to get right. Circles need to be split into their top and bottom semi-circles, and we don't only want to order objects based on their y-coordinates but if they are equal then also their slope and we need to deal with circles that are tangential to each other at a point. The composition or order of this set can change in 3 ways as we move from left to right:
We keep track of these events in a priority queue, and deal with them in the order they occur as we move from left to right.
The big advantage of this alogrithm over the naive approach is that it doesn't require us to keep track of the collision points. It also has the advantage that if we compute the amount of collisions in two rectangles then it is very easy to combine them, since we just need to add the amount of collisions in each, making sure we aren't double counting the borders. This makes it very easy to distribute computation. It also has very reasonable RAM demands. Its RAM use should be $O(n)$ where $n$ is the amount of lines and circles and the constant is quite small.