A Geometric Iteration with a Sylvester-Gallai Guarantee

Let $S$ be a set of points in a plane.

Define $A(S)$ to be the set of points obtained from $S$ in the following way: Let $L$ be the set of all lines that intersect $S$ in exactly two points. Let $P$ be the set of midpoints defined by the pairs of points $l \cap S$ for each $l \in L$.  Let $A(S) = S \cup P$.

That is, we add to $S$ the midpoint of every pair of points in $S$ that are not collinear with another point of $S$. By construction, $S \subset A(S)$.

The map $A$ is not so interesting if the points in $S$ are all collinear. If the points are all collinear and $S$ contains other than 2 points, then $A(S) = S$.  If there are exactly two points in $S$, then $A(S)$ will consist of the two points of $S$ together with their midpoint.

But if the points of $S$ are not all collinear, things get interesting.

Let $S$ be a finite set of points in a plane which are not all collinear. The Sylvester-Gallai theorem tells us that there will always be a line that intersects $S$ in exactly two points. This means we can iterate $A$ to create a sequence of strictly increasing sets. We start with some finite set of points in the plane not all collinear. Call it $S_0$. For $k > 0$, define $S_k = A(S_{k-1})$. The Sylvester-Gallai theorem guarantees that this sequence will never stabilize.

For example, if we start with the vertices of an equilateral triangle, here’s what happens:

The image at the very top of this blog post shows the result after one more iteration.

The total number of points in each stage, starting with the initial triangle vertices is:

3, 6, 9, 18, 69, 336, 1518, . . .

(By the way, this effectively represents the situation where $S_0$ consists of the vertices of any triangle because linear transformations respect the notions of collinearity and midpoint.)

If we don’t restrict ourselves to finite sets, the map $A$ has some interesting properties. For instance, if $S$ is the boundary of a bounded convex set in the plane, can you show that $A(S)$ is $S$ together with all the points inside?

If $S$ is two kissing circles of the same radius, then $A(S)$ will consist of the two circles plus the gray region shown below:

Do you know what kind of curves the red boundaries are?

For the answer, hover over this.

Getting back to the iteration that starts with the vertices of a triangle, let $S_\infty$ be the union of all the $S_k$.  Then $S_\infty$ is an example of a bounded, countable set of points such that no line intersects $S_\infty$ in exactly 2 points. Can you think of other countable, bounded sets that have this property? (There are a lot!) Can you think of a discrete set $S$ in the plane that satisfies $A(S) = S$?

Finally, here’s a question I don’t know the answer to: what is the closure of $S_\infty$?

If you dream up a set $S$ with a neat $A(S)$, please share!

(Speaking of Sylvester-Gallai, Prof. Terrence Tao recently blogged about new results he obtained with Ben Green related to the theorem. They obtained far out results concerning the structure of finite sets of points that have very few lines that intersect in exactly two points (or 3 points) enabling them to obtain sharp lower bounds on the number of such “ordinary” lines for large sets. In his post, he mentions use of one of my favorite mathematical results due to Poonen and Rubenstein: if you draw in all the diagonals of a regular polygon, what is the maximum number of diagonals that can intersect in a single point off center? In a regular polygon with 2n sides, n of the diagonals will intersect at the center point. But what about off the center point? The answer, which first happens in a regular 30-gon, is 7. For an illustration, see page 2 of Poonen and Rubenstein’s paper.)