A Geometric Iteration with a Sylvester-Gallai Guarantee

SG Iteration 6 triangle

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:

SG iteration 1 triangle

SG iteration 2 triangle

SG iteration 3 triangle

SG iteration 4 triangle

SG iteration 5 triangle

SG iteration 6 triangle

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:

A(kissing circles)

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


About girlsangle

We're a math club for girls.
This entry was posted in math, Math Education and tagged , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s