Four-cycles in no-three-in-line configurations

Based on a note by Achim Flammenkamp · 30 June 2026

In a maximum no-three-in-line configuration on an n × n grid, there are 2n chosen points and no three lie on one straight line. This forces exactly two chosen points in every row and every column. If we alternately jump to the other point in the same row, then to the other point in the same column, and so on, the chosen points split uniquely into even cycles. Achim’s conjecture is that only finitely many maximum configurations have all these cycles of length four; more boldly, that there are exactly fifteen, shown below.

The basic setup

The no-three-in-line problem asks for as many marked grid points as possible with no three on a single Euclidean line. Horizontal, vertical, diagonal, and long sloping lines all count.

On an n × n grid, no row can contain three chosen points, so there can be at most two in each row. Thus 2n points is the natural upper bound. When that bound is reached, every row has exactly two chosen points. The same argument applied to columns shows that every column also has exactly two.

The row-column cycles

Start at a chosen point p. There is exactly one other chosen point in the same row; call it q. Now switch direction. In the column of q, there is exactly one other chosen point; call it r. Continue alternating: row, column, row, column.

Because there are only finitely many chosen points, this process eventually returns to the starting point. It cannot branch, because at every step there is exactly one possible next point. Repeating this from points not yet used decomposes the whole configuration into disjoint cycles.

A 4-cycle is just a rectangle: row jump, column jump, row jump, column jump.

Another way to say the same thing is to make a bipartite graph. Put one vertex for each row and one vertex for each column. A chosen grid point is an edge joining its row to its column. Since every row and column has degree two, the graph is a disjoint union of cycles.

The cycle lengths are even. The smallest possible length is four: a 2-cycle would mean using the same grid point twice. A cycle of length 2n − 2 is also impossible, because the two remaining points would have to form such an impossible 2-cycle.

The conjecture

Four-cycle decomposition conjecture.

There are only finitely many maximum no-three-in-line configurations whose row-column cycle decomposition consists entirely of 4-cycles.

Sharper version.

There are exactly fifteen essentially different configurations with this property. The fifteen known examples are the ones drawn below.

When every cycle has length four, the configuration is made from n/2 axis-parallel rectangles, each rectangle contributing its four corners. This rectangle structure is very restrictive, but it does not by itself guarantee the no-three-in-line condition: one still has to check all sloping lines through points in different rectangles.

Why orthogonal reflection symmetry forces 4-cycles

Here “orthogonal reflection” means reflection in a horizontal or vertical middle line of the square, not reflection in a diagonal.

With vertical reflection symmetry, the two points in each row must be mirror partners.

Suppose the configuration is symmetric under a vertical reflection. In any row there are exactly two chosen points, and reflection preserves that row. Therefore those two points must be mirror images of each other.

Now start at a point p. The row step takes us to its mirror image. The column step reaches some second row. In that row, the next row step again takes the mirror image. The final column step returns to p. So the cycle has length four.

The same proof works for horizontal reflection. Hence any configuration with one orthogonal reflection, two orthogonal reflections, or full square symmetry has only 4-cycles.

The fifteen known examples

The dots are the chosen grid points. The light rectangles show the 4-cycles in the row-column decomposition. Rotations and reflections of the same pattern are not listed again.

Orthogonal reflection or full symmetry

These are the seven examples Achim singles out as already known in the orthogonal-reflection/full classes.

n = 2, full square symmetry
1 four-cycles, 4 points

n = 4, full square symmetry
2 four-cycles, 8 points

n = 4, one orthogonal reflection
2 four-cycles, 8 points

n = 8, one orthogonal reflection
4 four-cycles, 16 points

n = 10, full square symmetry
5 four-cycles, 20 points

n = 26, one orthogonal reflection
13 four-cycles, 52 points

n = 28, one orthogonal reflection
14 four-cycles, 56 points

Rotational symmetry

These seven have half-turn or quarter-turn symmetry, but not an orthogonal reflection in the listed representative.

n = 4, half-turn symmetry
2 four-cycles, 8 points

n = 8, half-turn symmetry
4 four-cycles, 16 points

n = 8, quarter-turn symmetry #1
4 four-cycles, 16 points

n = 8, quarter-turn symmetry #2
4 four-cycles, 16 points

n = 10, half-turn symmetry #1
5 four-cycles, 20 points

n = 10, half-turn symmetry #2
5 four-cycles, 20 points

n = 10, quarter-turn symmetry
5 four-cycles, 20 points

Asymmetric

The remaining example has no nontrivial square symmetry in the listed representative.

n = 8, asymmetric
4 four-cycles, 16 points

What the count says

The fifteen examples fall into the three groups described in Achim’s note:

Seven have an orthogonal reflection or full square symmetry.
Seven more have rotational symmetry.
One is asymmetric.

All but two have grid size at most 10. The two larger examples are the orthogonal-reflection configurations on 26 × 26 and 28 × 28 grids.

References

Achim Flammenkamp, The No-Three-in-Line Problem.
Achim Flammenkamp, download directory of known no-three-in-line configurations, including files grouped by grid size and symmetry class.