No-Three-in-Line Problem and Parafermions

EasyChair Preprint 10235, version 2

Abstract

The no-three-in-line problem in discrete geometry asks how many points can be placed in the n × n grid so that no three points lie on the same line. The problem concerns lines of all slopes, not only those aligned with the grid. It was introduced by Henry Dudeney in 1917. Peter Brass, William Moser and Janos Pach call it “one of the oldest and most extensively studied geometric questions concerning lattice points”.

This number is at most 2n, since if 2n + 1 points are placed in the grid, then by the pigeonhole principle some row and some column will contain three points. Although the problem can be solved with 2n points for every n up to 46, it is conjectured that fewer than 2n points are possible for sufficiently large values of n. The best solutions that are known to work for arbitrarily large values of n place slightly fewer than 3n/2 points.

In this paper the reformulation of the no-three-in-line problem using parafermions is given, which allows to get a better lower bound.

Keyphrases: Beck’s theorem, Fibonacci anyons, General Position Subset Selection Problem, No-three-in-line problem, Parafermions, Temperley–Lieb algebra, deformation, square grid, statistical model, vertex algebras

@booklet{EasyChair:10235,
  author    = {Valerii Sopin},
  title     = {No-Three-in-Line Problem and Parafermions},
  howpublished = {EasyChair Preprint 10235},
  year      = {EasyChair, 2023}}