13
$\begingroup$

Suppose you start with two points in the plane which are distance 1 apart, which for concreteness can be $(0,0)$ and $(0,1)$. Then you keep marking new points based on ruler and compass constructions. That is, you start with those two points as "marked. " At each stage you draw all possible circles which have a previously marked point as a center and with another previously marked point as a point on the circle, and you draw every line which goes through any two marked points. Then you mark every point which is an intersection of a circle or line and a circle or line. The set of marked points is the set of "constructible" points and has been studied since the ancient Greeks.

Here is a variant of that. Instead what happens if at each stage instead of throwing in every new line and circle, we only throw in those from a single pair of points chosen randomly and uniformly from all currently marked points? That is, suppose that at each stage we pick two marked points chosen uniformly at random, and we throw in the line and two circles determined by those points, and then mark every new point resulting from those circles and lines intersecting with each other or our existing circles and lines.

Question: With probability 1 do we still end up with all constructible points in our resulting set?

This seems hard. I don't even see any obvious way to prove that with probability 1 our resulting set is dense in the plane (which is trivially true for the set of constructible points). Based on the answer to [this question], one can choose specific points to get very far away from the origin very fast but there one is carefully choosing specific points.

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ This is a very nice problem. At first I thought it was obvious that every point would be generated with probability 1; now I'm not even confident that (0,2) is. A closely related interesting question: what's the expected asymptotic number of points generated by stage $n$ of this process? It's easy to show examples with linear growth and not much harder to give an example with quadratic growth; exponential growth feels unlikely but hard to prove. $\endgroup$
    – Steven Stadnicki
    Commented Oct 17, 2021 at 4:57
  • 2
    $\begingroup$ A dyadic variant: Start with the corners of the unit square (or cube or interval); then at every stage, randomly select points $P$ and $Q$, and add one of $2P-Q$, $(P+Q)/2$, $2Q-P$. Will this almost surely produce all points with dyadic rational coordinates? $\endgroup$
    – user44143
    Commented Oct 17, 2021 at 12:10
  • $\begingroup$ @StevenStadnicki, surely the first iteration has to select points $(0,0)$ and $(0,1)$ and construct points $(0,-1)$, $(0,2)$, $(\tfrac12, \pm\sqrt{\tfrac34})$? $\endgroup$
    – Peter Taylor
    Commented Oct 17, 2021 at 13:57
  • $\begingroup$ @PeterTaylor I misunderstood the construction slightly — I thought a pair of points was being chosen and either one of the circles or the line through them was being constructed. I suspect the answer is going to be the same, though, and that heuristically it should be straightforward to argue that the configuration grows 'too quick' for arbitrary points to be added. $\endgroup$
    – Steven Stadnicki
    Commented Oct 17, 2021 at 15:35
  • 1
    $\begingroup$ (Also, it struck me this morning that it's easy to see that exponential growth is impossible; after $n$ steps we have $O(n)$ 'girders' (lines and circles), and the $O(1)$ new girders added at the $(n+1)$st step can only add $O(n)$ new points to the assembly.) $\endgroup$
    – Steven Stadnicki
    Commented Oct 17, 2021 at 15:37

1 Answer 1

Reset to default
1
$\begingroup$

Fleshing out my comment slightly, here's a heuristic argument with a couple of blanks to be filled in that suggests that most points will be 'found' with probability $\lt 1$. For approximation purposes I'm going to ignore logarithmic factors here, so take all $O()$, etc. as being 'up to $n^{o(1)}$ factors'.

The argument is straightforward: pick some $P$ not in the initial assembly (e.g., $P=(0, 100)$.) Suppose that the asymptotic number of points in the construction after $n$ stages is $\Theta(n^\alpha)$ for some $1\leq \alpha \leq 2$. Then we have $\Theta(n^{2\alpha})$ pairs of points to choose; further suppose that $\Theta(n^\beta)$ of those pairs add the point $P$. Then at each iteration, $P$ gets added with probability $\Theta(n^{\beta-2\alpha})$ and therefore never gets added at all with probability $\prod_n\left(1-\Theta(n^{\beta-2\alpha})\right)$; if we have $\beta\lt2\alpha-1$ then this product converges to a non-zero value.

From a different angle, note that if the asymptotic size is $\Theta(n^\alpha)$ then at each stage $\Theta(n^{\alpha-1})$ points are added. If there are $\Theta(n^\gamma)$ 'new' points accessible from the construction at stage $n$ and we assume that each point is added with equal probability, then any given accessible point will be added with probability $\Theta(n^{-(1+(\gamma-\alpha))})$; in particular, if it can be shown that the number of points immediately constructible from a figure of size $n^\alpha$ is $\Omega(n^{\alpha+\epsilon})$ for some $\epsilon\gt 0$ then we get the same convergence result. This seems likely to me if $\alpha\gt 1$, but of course filling in the blanks here is bound to be highly non-trivial.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .