arxiv: 2605.09215 · v1 · submitted 2026-05-09 · 🧮 math.CO

Recognition: no theorem link

No-three-in-line sets on the checkerboard grid

Thomas Prellberg

Pith reviewed 2026-05-12 02:23 UTC · model grok-4.3

classification 🧮 math.CO

keywords no-three-in-line problemcheckerboard gridlinear programming relaxationcontinuum dual certificatedensity upper boundcollinear pointsgrid parity

0 comments

The pith

Explicit nonnegative functions prove that the odd-fat continuum relaxation of the checkerboard no-three-in-line problem has limiting density at most the middle real root α of the cubic 401α³-1744α²+2240α-768=0.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies the largest set of same-color points on an n by n checkerboard grid with no three collinear, denoted D_mono(n). It introduces a four-direction linear-programming relaxation that incorporates row, column, and ±1-diagonal constraints on one parity class; this relaxation is stronger than the elementary 2n-2 bound from the diagonals alone. Scaling the odd-fat version to the continuum yields a dual problem whose optimum is bounded by constructing explicit nonnegative functions that obey the obstacle inequalities and attain objective value α, the middle real root of the given cubic. Finite LP solutions and small-n exact data align with this value as the asymptotic slope. A reader cares because the construction supplies a concrete, potentially sharp density limit for a classic combinatorial extremal problem under the checkerboard restriction.

Core claim

The main rigorous result is an exact continuum dual certificate for the formal continuum problem associated with the scaled odd-fat case. We construct explicit nonnegative functions satisfying the continuum obstacle inequalities and having objective value α, where 401α³-1744α²+2240α-768=0 and α is the middle real root. This proves the upper bound Λ_fat ≤ α for the odd-fat continuum relaxation. Finite LP computations are consistent with α as a limiting slope, and exact small-n data suggest the same scale for the original checkerboard optimum.

What carries the argument

The four-direction linear-programming relaxation on a fixed parity class using rows, columns, and the two families of ±1 diagonals, together with the explicit nonnegative functions that serve as the continuum dual certificate.

If this is right

The odd-fat continuum relaxation is bounded above by α.
Finite LP computations align with α as the limiting slope.
Exact small-n data indicate the same asymptotic scale for the discrete checkerboard optimum.
The slope-±1 diagonals alone give only the weaker bound D_mono(n) ≤ 2n-2, while the full four-direction LP is tighter.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If the bound is tight, the maximum number of same-parity no-three-in-line points would grow as α n + o(n).
The same continuum-certificate technique could be tested on checkerboard restrictions with other sets of allowed slopes.
The approach might extend to parity-restricted versions of no-four-in-line or higher-order avoidance problems.
Comparing the derived cubic root numerically with large-scale LP solutions would test how closely the continuum bound is approached.

Load-bearing premise

The constructed nonnegative functions satisfy every continuum obstacle inequality, and the continuum relaxation correctly upper-bounds the discrete checkerboard problem.

What would settle it

A concrete falsifier is either a pointwise violation of one obstacle inequality by the given explicit functions or the existence of a one-color n by n configuration with more than α n points and no three collinear, for sufficiently large n.

Figures

Figures reproduced from arXiv: 2605.09215 by Thomas Prellberg.

**Figure 1.** Figure 1: The continuum dual profiles A and B on [0, 1]. The zero intervals and the breakpoints p, c, d, e, f, g show the piecewise-profile pattern suggested by the finite dual profiles. The function A is zero up to p, while B vanishes after g; between the breakpoints the pieces are quadratic or linear as in (6). Proof of the certificate Proof of Theorem 1. First, the displayed breakpoints satisfy 0 < p < c < d < 1,… view at source ↗

**Figure 2.** Figure 2: Subdivision of the continuum triangle after the change of variables [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗

read the original abstract

The classical no-three-in-line problem asks for the largest number (D(n)) of points that can be chosen from an (n \times n) grid with no three collinear. We study the checkerboard-restricted variant in which all chosen points lie in one fixed parity class of (x+y \pmod 2). Let (D_{\mathrm{mono}}(n)) be the corresponding optimum. The slope-(\pm1) diagonals give the elementary bound (D_{\mathrm{mono}}(n) \le 2n-2). The main tool is a four-direction linear-programming relaxation on a fixed parity class, using rows, columns, and the two diagonal families of slopes (\pm1). For the ordinary square-grid problem this relaxation is trivial, but on the checkerboard it gives substantially tighter finite bounds. After symmetry reduction, the dual relaxation has three one-dimensional forms, according to the parity of (n) and the chosen colour class. The main rigorous result is an exact continuum dual certificate for the formal continuum problem associated with the scaled odd-fat case. We construct explicit nonnegative functions satisfying the continuum obstacle inequalities and having objective value (\alpha), where (401\alpha^3-1744\alpha^2+2240\alpha-768=0) and (\alpha) is the middle real root. This proves the upper bound (\Lambda_{\mathrm{fat}}\le\alpha) for the odd-fat continuum relaxation. Finite LP computations are consistent with (\alpha) as a limiting slope, and exact small-(n) data suggest the same scale for the original checkerboard optimum.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives an explicit continuum dual certificate yielding a new upper bound α (middle root of that cubic) for the odd-fat checkerboard no-three-in-line relaxation, with the global validity of the functions as the main thing to check.

read the letter

The main new piece is the construction of explicit nonnegative functions for the four-direction continuum dual on the odd-fat checkerboard case. These achieve objective value α, the middle real root of 401α³-1744α²+2240α-768=0, and thereby prove Λ_fat ≤ α. This is tighter than the elementary 2n-2 bound from the slope-±1 diagonals and applies specifically to the mono parity class after the symmetry reduction to three one-dimensional dual forms. The finite LP runs and small-n exact values line up with α as the limiting slope, which adds useful consistency checks. The setup of the LP relaxation itself is straightforward and shows why the checkerboard parity makes the four-direction version nontrivial, unlike the ordinary grid case. That is the concrete advance. The soft spot is whether the given functions satisfy the obstacle inequalities at every point in the continuum, not just on the optimized loci or at test points. The continuum imposes pointwise conditions everywhere, so any local violation would invalidate the certificate for α. The paper claims the functions work, but this needs explicit verification in the text, perhaps through sign analysis or derivative checks on the difference functions. Minor gaps in the write-up of the verification would be easy to fix. This is for combinatorialists interested in no-three-in-line variants or LP relaxations for grid problems. A reader working on discrete geometry bounds or continuum limits will find the explicit certificate and the parity-specific relaxation worth seeing. The thinking is clear and the evidence is reproducible in principle. It deserves a serious referee because the bound is new and the method is concrete, even if the dual check requires close reading.

Referee Report

1 major / 2 minor

Summary. The manuscript studies the checkerboard-restricted no-three-in-line problem, defining D_mono(n) as the maximum number of points on one fixed parity class of an n×n grid with no three collinear. It introduces a four-direction LP relaxation (rows, columns, and ±1 diagonals) that is nontrivial on the checkerboard, reduces the dual by symmetry into three one-dimensional forms, and focuses on the odd-fat continuum limit. The central rigorous result constructs explicit nonnegative functions satisfying the continuum obstacle inequalities with objective value α (the middle real root of 401α³-1744α²+2240α-768=0), proving the upper bound Λ_fat ≤ α; finite LP computations and small-n data are consistent with this scale.

Significance. If the explicit dual functions are globally valid, the result supplies a concrete, non-trivial upper bound for the scaled odd-fat continuum relaxation, improving on the elementary 2n-2 diagonal bound and providing a candidate limiting density for the discrete checkerboard problem. The explicit, closed-form nature of the certificate is a clear strength, as it permits direct verification and contrasts with purely numerical approaches; consistency with finite LP and exact small-n data further supports potential tightness.

major comments (1)

[Continuum dual certificate] Continuum dual certificate (the main rigorous result): the manuscript asserts that the constructed nonnegative functions satisfy the obstacle inequalities at every point in the continuum domain and achieve objective α. Because the continuum imposes infinitely many pointwise conditions and the construction is optimized only to equality at selected loci, an explicit, exhaustive verification (or a proof that the piecewise definitions never violate the inequalities in open regions) is required; any local violation would invalidate the claimed dual bound Λ_fat ≤ α.

minor comments (2)

The cubic 401α³-1744α²+2240α-768=0 is stated without its numerical approximation or factorization; supplying the approximate decimal value of the middle root (and confirming it is the relevant one) would aid readers.
Notation for the three symmetry-reduced dual forms (by parity of n and colour class) is introduced late; a brief early table or diagram distinguishing them would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for recognizing the potential significance of the explicit continuum dual certificate. We address the major comment below and will strengthen the manuscript accordingly.

read point-by-point responses

Referee: Continuum dual certificate (the main rigorous result): the manuscript asserts that the constructed nonnegative functions satisfy the obstacle inequalities at every point in the continuum domain and achieve objective α. Because the continuum imposes infinitely many pointwise conditions and the construction is optimized only to equality at selected loci, an explicit, exhaustive verification (or a proof that the piecewise definitions never violate the inequalities in open regions) is required; any local violation would invalidate the claimed dual bound Λ_fat ≤ α.

Authors: We agree that the current presentation states the satisfaction of the obstacle inequalities but does not supply a complete analytical verification across the entire domain. The functions are given explicitly in piecewise form, with equality imposed at selected breakpoints, yet the nonnegativity of the relevant combinations in the open intervals between breakpoints is asserted rather than proved in detail. In the revised manuscript we will add a dedicated subsection (or appendix) that partitions the continuum domain into the finitely many intervals determined by those breakpoints and verifies the inequalities directly in each open subinterval by showing that the appropriate linear combinations of the dual functions remain nonnegative (these differences reduce to low-degree polynomials whose signs can be checked analytically or by evaluating derivatives at critical points). This will make the dual certificate fully rigorous and self-contained. revision: yes

Circularity Check

0 steps flagged

No significant circularity; dual certificate is independently constructed

full rationale

The paper derives the upper bound Λ_fat ≤ α by explicitly constructing nonnegative functions that satisfy the continuum obstacle inequalities pointwise and achieve objective value α (the middle root of the cubic 401α³-1744α²+2240α-768=0). This is a standard primal-dual certificate argument: the functions are defined explicitly, the cubic is obtained by enforcing equality in the obstacle conditions at the critical loci, and the resulting α certifies the bound without reference to fitted data or prior results from the same authors. Finite LP computations and small-n enumerations are presented only as consistency checks after the fact, not as inputs to the construction. No self-definitional loops, fitted predictions renamed as results, or load-bearing self-citations appear in the derivation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The proof relies on standard LP theory and the construction of specific functions for the dual problem. No new entities are postulated.

axioms (2)

standard math Linear programming duality holds for the relaxation.
Used to obtain the dual certificate.
domain assumption The continuum limit accurately captures the asymptotic behavior of the discrete problem.
Assumed for the bound to apply to finite n.

pith-pipeline@v0.9.0 · 5581 in / 1161 out tokens · 51425 ms · 2026-05-12T02:23:27.690877+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages

[1]

Adena, D.A

M.A. Adena, D.A. Holton, P.A. Kelly, Some thoughts on the no-three-in-line problem, in: D.A. Holton (ed.), Combinatorial Mathematics: Proceedings of the Second Aus- tralian Conference, Lecture Notes in Mathematics 403, Springer, Berlin, 1974, pp. 6–17. doi:10.1007/BFb0057371

work page doi:10.1007/bfb0057371 1974
[2]

Aichholzer, D

O. Aichholzer, D. Eppstein, E.-M. Hainzl, Geometric dominating sets—a minimum ver- sion of the No-Three-In-Line Problem, Comput. Geom. 108 (2023), Article 101913. doi:10.1016/j.comgeo.2022.101913

work page doi:10.1016/j.comgeo.2022.101913 2023
[3]

Anderson, Update on the no-three-in-line problem, J

D.B. Anderson, Update on the no-three-in-line problem, J. Combin. Theory Ser. A 27 (1979) 365–366. doi:10.1016/0097-3165(79)90025-6

work page doi:10.1016/0097-3165(79)90025-6 1979
[4]

Balogh, F.C

J. Balogh, F.C. Clemen, A. Dumitrescu, D. Liu, Subset selection problems in planar point sets, arXiv:2412.14287 (2024)

work page arXiv 2024
[5]

S. Basu, R. Pollack, M.-F. Roy, Algorithms in Real Algebraic Geometry, 2nd ed., Springer, Berlin, 2006. doi:10.1007/3-540-33099-2

work page doi:10.1007/3-540-33099-2 2006
[6]

Brass, W.O.J

P. Brass, W.O.J. Moser, J. Pach, Research Problems in Discrete Geometry, Springer, New York, 2005. doi:10.1007/0-387-29929-7

work page doi:10.1007/0-387-29929-7 2005
[7]

Cao, Study on Two Optimization Problems: Line Cover and Maximum Genus Embed- ding, Master’s thesis, Texas A&M University, May 2012.https://hdl.handle.net/1969

C. Cao, Study on Two Optimization Problems: Line Cover and Maximum Genus Embed- ding, Master’s thesis, Texas A&M University, May 2012.https://hdl.handle.net/1969. 1/ETD-TAMU-2012-05-11073

work page 2012
[8]

Di Stefano, Haritha S., E.J

Ullas Chandran S.V., G. Di Stefano, Haritha S., E.J. Thomas, J. Tuite, Colouring a graph with position sets, Ars Math. Contemp., early access (2025). doi:10.26493/1855- 3974.3454.a3c. 17

work page doi:10.26493/1855- 2025
[9]

Cooper, O

A.S. Cooper, O. Pikhurko, J.R. Schmitt, G.S. Warrington, Martin Gardner’s minimum no-3-in-a-line problem, Amer. Math. Monthly 121 (2014) 213–221. doi:10.4169/amer.math.monthly.121.03.213

work page doi:10.4169/amer.math.monthly.121.03.213 2014
[10]

Cooper, J

J. Cooper, J. Hyatt, Permutations minimizing the number of collinear triples, Des. Codes Cryptogr. 93 (2025) 3135–3142. doi:10.1007/s10623-025-01632-w

work page doi:10.1007/s10623-025-01632-w 2025
[11]

Cooper, J

J.N. Cooper, J. Solymosi, Collinear points in permutations, Ann. Comb. 9 (2005) 169–175. doi:10.1007/s00026-005-0248-4

work page doi:10.1007/s00026-005-0248-4 2005
[12]

Dudeney, Amusements in Mathematics, Nelson, Edinburgh, 1917

H. Dudeney, Amusements in Mathematics, Nelson, Edinburgh, 1917

work page 1917
[13]

Dumitrescu, General Position Subset Selection in Line Arrangements, Algorithms 18 (2025), 315

A. Dumitrescu, General Position Subset Selection in Line Arrangements, Algorithms 18 (2025), 315. doi:10.3390/a18060315

work page doi:10.3390/a18060315 2025
[14]

Eppstein, Forbidden Configurations in Discrete Geometry, Cambridge University Press, Cambridge, 2018

D. Eppstein, Forbidden Configurations in Discrete Geometry, Cambridge University Press, Cambridge, 2018. doi:10.1017/9781108539180

work page doi:10.1017/9781108539180 2018
[15]

Farouki, The Bernstein polynomial basis, a centennial retrospective, Comput

R.T. Farouki, The Bernstein polynomial basis, a centennial retrospective, Comput. Aided Geom. Design 29 (2012) 379–419. doi:10.1016/j.cagd.2012.03.001

work page doi:10.1016/j.cagd.2012.03.001 2012
[16]

Flammenkamp, Progress in the no-three-in-line problem, J

A. Flammenkamp, Progress in the no-three-in-line problem, J. Combin. Theory Ser. A 60 (1992) 305–311

work page 1992
[17]

Flammenkamp, Progress in the No-Three-in-Line Problem, II, J

A. Flammenkamp, Progress in the No-Three-in-Line Problem, II, J. Combin. Theory Ser. A 81 (1998) 108–113

work page 1998
[18]

Fowler, A

J. Fowler, A. Groot, D. Pandya, B. Snapp, The no-three-in-line problem on a torus, arXiv:1203.6604 (2012)

work page arXiv 2012
[19]

Froese, I

V. Froese, I. Kanj, A. Nichterlein, R. Niedermeier, Finding points in general position, Int. J. Comput. Geom. Appl. 27 (2017) 277–296. doi:10.1142/S021819591750008X

work page doi:10.1142/s021819591750008x 2017
[20]

F¨ uredi, Maximal independent subsets in Steiner systems and in planar sets, SIAM J

Z. F¨ uredi, Maximal independent subsets in Steiner systems and in planar sets, SIAM J. Discrete Math. 4 (1991) 196–199. doi:10.1137/0404019

work page doi:10.1137/0404019 1991
[21]

Guy, P.A

R.K. Guy, P.A. Kelly, The no-three-in-line problem, Canadian Math. Bull. 11 (1968) 527– 531

work page 1968
[22]

Hall, T.H

R.R. Hall, T.H. Jackson, A. Sudbery, K. Wild, Some advances in the no-three-in-line problem, J. Combin. Theory Ser. A 18 (1975) 336–341. doi:10.1016/0097-3165(75)90043-6

work page doi:10.1016/0097-3165(75)90043-6 1975
[23]

Harborth, P

H. Harborth, P. Oertel, T. Prellberg, No-three-in-line for seventeen and nineteen, Discrete Math. 73 (1988/89) 89–90

work page 1988
[24]

Kløve, On the No-Three-in-Line Problem, III, J

T. Kløve, On the No-Three-in-Line Problem, III, J. Combin. Theory Ser. A 26 (1979) 82–83. (See also related notes in the same volume.)

work page 1979
[25]

Kov´ acs, Z.L

B. Kov´ acs, Z.L. Nagy, D.R. Szab´ o, Randomised algebraic constructions for the no-(k+ 1)- in-line problem, arXiv:2508.07632 (2025)

work page arXiv 2025
[26]

C.Y. Ku, K.B. Wong, On No-Three-In-Line Problem onm-Dimensional Torus, Graphs Combin. 34 (2018) 355–364. doi:10.1007/s00373-018-1878-8

work page doi:10.1007/s00373-018-1878-8 2018
[27]

Nagy, Z.L

D.T. Nagy, Z.L. Nagy, R. Woodroofe, The extensible No-Three-In-Line problem, European J. Combin. 114 (2023), Article 103796. doi:10.1016/j.ejc.2023.103796

work page doi:10.1016/j.ejc.2023.103796 2023
[28]

Payne, D.R

M.S. Payne, D.R. Wood, On the general position subset selection problem, SIAM J. Dis- crete Math. 27 (2013) 1727–1733. doi:10.1137/120897493. 18

work page doi:10.1137/120897493 2013
[29]

P´ or, D.R

A. P´ or, D.R. Wood, No-three-in-line-in-3D, Algorithmica 47 (2007) 481–488. doi:10.1007/s00453-006-0158-9

work page doi:10.1007/s00453-006-0158-9 2007
[30]

Prellberg, Constraint satisfaction programming for the no-three-in-line problem, arXiv:2602.07751 (2026)

T. Prellberg, Constraint satisfaction programming for the no-three-in-line problem, arXiv:2602.07751 (2026)

work page arXiv 2026
[31]

Schrijver, Theory of Linear and Integer Programming, Wiley, Chichester, 1998

A. Schrijver, Theory of Linear and Integer Programming, Wiley, Chichester, 1998. ISBN 978-0-471-98232-6

work page 1998
[32]

Skotnica, No-three-in-line problem on a torus: periodicity, Discrete Math

M. Skotnica, No-three-in-line problem on a torus: periodicity, Discrete Math. 342 (2019) 111611. doi:10.1016/j.disc.2019.111611

work page doi:10.1016/j.disc.2019.111611 2019
[33]

Wood, A note on colouring the plane grid, Geombinatorics XIII(4) (2004) 193–196

D.R. Wood, A note on colouring the plane grid, Geombinatorics XIII(4) (2004) 193–196. https://users.monash.edu.au/~davidwo/papers/Wood-GridColouring.pdf. 19

work page 2004