Four-corner permutation tests for no-three-in-line configurations

The basic objects

The no-three-in-line problem asks for marked grid points with no three lying on any single Euclidean line. Rows, columns, ordinary diagonals, and long sloping lines all count.

Here a configuration means a best-possible arrangement on an N × N grid: it has 2N marked points and no three in line. Since no row can contain three marked points, 2N points force exactly two points in every row. The same argument gives exactly two points in every column.

Now suppose N = 2M and cut the square into four M × M quadrants. A quadrant is a permutation matrix if it has exactly one marked point in each of its local rows and exactly one in each of its local columns. Equivalently, it is the pattern of M non-attacking rooks on an M × M chessboard.

The conjectures

The adjacent conjecture is stronger: if all four quadrants are permutation matrices, then certainly two adjacent quadrants are.

The evidence statement is computational. The four-corner conjecture has been checked for N = 2M < 38; the adjacent conjecture has slightly less evidence. If the condition M > 5 is removed, the known small exceptions are exactly the pictures below.

Small-grid exceptions

The thick cross shows the four quadrants. In the first six pictures, every quadrant is a permutation matrix.

Why either conjecture implies Guy–Kelly II

Guy–Kelly Conjecture II, as listed by Flammenkamp, says that every no-three-in-line configuration with both horizontal and vertical mirror symmetry has the full symmetry of the square. Here full symmetry means all eight square symmetries: four rotations and four reflections.

The proof uses only row and column counting. A 2N-point configuration has exactly two points in each row, because no row can contain three and there are N rows. The same argument gives exactly two points in each column.

Odd grids can be dismissed at once. If N were odd, the middle row would contain two points. Vertical symmetry makes them a left-right pair, so both lie off the middle column. In either of those two columns, horizontal symmetry fixes the middle-row point and pairs all other points. That column therefore contains an odd number of points, contradicting the required total of exactly two.

So write N = 2M. The two mirror axes now lie between rows and between columns. In each row, vertical symmetry swaps left and right; since there are exactly two points in the row, there is one on each side. Similarly, every column has one point in the top half and one in the bottom half. Thus each quadrant has one point in every local row and every local column. In other words, the four quadrants are permutation matrices.

Now assume the four-corner conjecture. For M > 5, the preceding paragraph gives exactly the forbidden pattern, so no two-mirror configuration exists. For M ≤ 5, the complete small list above shows that the only two-mirror cases are A, B, and F, and those already have full symmetry. Hence every two-mirror configuration has full symmetry.

The adjacent conjecture gives the same conclusion. Two mirror symmetries force all four quadrants to be permutation matrices, hence force two adjacent permutation quadrants. This is forbidden for M > 5. For M ≤ 5, the complete small list above gives the same conclusion: the only two-mirror cases are the full-symmetry cases A, B, and F.

In short: two perpendicular mirror symmetries force permutation quadrants; the conjectures forbid those quadrants in large grids; the remaining small two-mirror examples are already fully symmetric.

References

1. Achim Flammenkamp, The No-Three-in-Line Problem, webpage: https://wwwhomes.uni-bielefeld.de/achim/no3in/readme.html.
2. Richard K. Guy and Patrick A. Kelly, “The No-Three-In-Line Problem,” Canadian Mathematical Bulletin, vol. 11, issue 4, 1968, pp. 527–531. DOI: 10.4153/CMB-1968-062-3.