Pith. sign in

REVIEW 1 major objections 8 minor 42 references

No-$(k+1)$-in-line problem for $k \geqslant 3$

T0 review · 1 major / 8 minor · reviewed 2026-07-07 · glm-5.2

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For k≥3 and sufficiently large n, the maximum number of points in an n×n grid with no k+1 collinear is exactly kn.

desk verdict Resolves the no-(k+1)-in-line problem for all k≥3: f_k(n)=kn. New non-algebraic method via pseudorandom matchings + randomized switching completion. Sound, significant, deserves a serious referee. read the letter →

arxiv 2607.05255 v1 pith:RKEBR6FF submitted 2026-07-06 math.CO math.MG

Anubhab Ghosal , Ritesh Goenka , Alexandr Grebennikov , Peter Keevash , Matthew Kwan , Huy Tuan Pham This is my paper
classification math.COmath.MG
keywords pointsproblemgeqslantgridlinesizeconstructionheavy
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The no-three-in-line problem asks: how many points can you place on an n×n grid so that no three are in a straight line? The trivial upper bound is 2n (since each of the n rows can hold at most 2 points), but whether this is achievable remains a famous open problem. This paper studies the generalization to no k+1 points in a line. For k≥3, the authors prove the maximum is exactly kn, matching the trivial upper bound. The key insight is that for k≥3, the problem is dominated by a few 'heavy' line directions (like rows, columns, and diagonals). The sum over light directions converges, allowing a deletion argument to clean up violations. The proof constructs an approximate set of size kn−o(n) using pseudorandom hypergraph matchings, then uses a randomized switching procedure to fill the remaining gap to exactly kn.
Extended reading notes

Core claim

Theorem 1.1: Let n, k be integers such that k≥3 and n≥max(n₀, k) for some absolute constant n₀. Then there exists a set S⊆[n]² of size kn such that every Euclidean line contains at most k points of S. This proves the trivial upper bound f_k(n)≤kn is tight for all k≥3.

Load-bearing premise

Proposition 4.10, the core of the completion procedure, asserts that with high probability the randomized switching algorithm never aborts because there are always at least ρn available absorbers. The proof of this relies on the spreadness of S_init ∪ S_half (Lemma 4.16) and the transfer argument in Lemma 4.17 bounding |T_L(S_init ∪ S_comp)|. If the moment-based argument in Lemma 4.12 or the spreadness coupling in Fact 2.3 has a gap, the completion from kn−o(n) to exactly kn fails.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 8 minor

Summary. This paper resolves the no-$(k+1)$-in-line problem for all $k geq 3$ and sufficiently large $n$, proving that the trivial upper bound $f_k(n) le kn$ is tight. The proof has two stages: an approximate construction of size $kn - o(n)$ via pseudorandom hypergraph matchings (using the Ehard–Glock–Joos theorem), followed by a randomized switching procedure that completes the construction to exactly $kn$ points. The key insight is that for $k ge 3$, the contribution of $varepsilon$-light lines is controlled by a convergent series, making the problem dominated by finitely many heavy directions. The paper also proves a higher-dimensional analogue (Theorem 1.4) and improves the lower bound for the no-four-on-a-circle problem to $2n - o(n)$ (Theorem 1.5).

Significance. The main result (Theorem 1.1) settles a natural generalization of Dudeney's no-three-in-line problem for all $k ge 3$, showing the trivial upper bound is achieved. This is a substantial advance: prior work of Kovács–Nagy–Szabó gave $f_k(n) ge (k-2-o(1))n$, and the result of Grebennikov–Kwan covered only $k ge 10^{37}$. The method is non-algebraic, contrasting with all previous constructions for small $k$. The completion procedure (Section 4), building on ideas of Simkin and Luria for the $n$-queens problem, is technically intricate and appears to be the first application of such switching-based absorption to the no-$(k+1)$-in-line setting. The extension to the no-four-on-a-circle problem (improving from $n - o(n)$ to $2n - o(n)$) and the higher-dimensional result add further value. The proof of Lemma 2.2 in Appendix A, which extends the Ehard–Glock–Joos pseudorandom matching theorem to include an explicit spreadness guarantee, is a useful standalone contribution.

major comments (1)
  1. Lemma 4.17 (the transfer argument from $S_{init} cup S_{half}$ to $S_{init} cup S_{comp}$): The proof states that each point $p_1, p_2, p_3$ of a triple in $T_L(S_{init} cup S_{comp})$ is included in $S_{init} cup S_{half}$ with probability at least $1/2$ independently, conditional on $S_{init}$ and $S_{comp}$ (and the absorber choices). However, the independence claim needs scrutiny: the absorber choices $(x_t, y_t)$ are determined by $S_{init}$ and the algorithm's internal randomness, and $S_{half}$ further randomizes which of the two added points is selected. The statement that each triple point survives in $S_{half}$ with probability $ge 1/2$ independently relies on the triple's three points belonging to three distinct switching steps. If two of the three points come from the same step $t$ (i.e., both $(x_t, r_t)$ and $(c_t, y_t)$ are in the same triple), then their inclusion in $S_{
minor comments (8)
  1. Section 1.3, paragraph on approximate constructions: the heuristic computation in Remark 1.7 uses $sum_{m=lfloor 1/varepsilon rfloor+1}^{n} 1/m^{k-1}$, but the text says 'this sum is about $log n$' for $k=2$. For $k=2$ the sum is $sum 1/m$, which is indeed $Theta(log n)$, but the statement 'independently of $varepsilon$' is slightly imprecise since the lower limit depends on $varepsilon$; the leading term is $log n - log(1/varepsilon) = log(nvarepsilon)$. Consider clarifying.
  2. Definition 4.1, condition A2: the line through $(x,r)$ and $(c,y)$ is required to be 'irrelevant' (i.e., $|d|_infty ge n/3$). The term 'irrelevant' is defined earlier in Section 4 but could benefit from a brief reminder at the point of use in Definition 4.1, since it is load-bearing for the absorber definition.
  3. Lemma 4.2: the constant $0.05$ is used as a lower bound for $|I(c,r)|/n^2$. The proof uses the Minkowski-type result giving $6/pi^2 cdot n^2/12 + o(n^2) approx 0.05066 n^2$. The margin is thin; it would help to state the numerical value $6/(12pi^2) approx 0.0507$ explicitly so the reader can verify $> 0.05$.
  4. Section 5, proof of Theorem 1.4: the codegree bound $Delta_2(H_varepsilon^{(k)}) le n^{s-1}$ is stated but the justification ('since an intersection of two primitive rank-$s$ lattices has rank at most $s-1$') could be elaborated slightly, as the bound on the number of common edges (not just vertices) requires a bit more care.
  5. Reference [7] (Conlon, 'Private communication') and [17] (Green, '100 open problems, Manuscript') lack precise bibliographic details. If possible, provide more complete citations or note the status.
  6. Appendix B: the table of numerical data is a nice addition. The claim that $f_{IT}(n) - f_{circ}(n) = o(n)$ is 'plausible' is reasonable, but the convergence rate of Lemma 6.1 is noted as 'very slow' without quantification. A brief remark on the known rate (the exponent $4+18/29$) would contextualize this.
  7. Typo in Section 4.4, proof of Proposition 4.10, Case 3b: 'Since $k ge 3$ and $S_{t-1} subseteq S_{init} cup S_{comp}$, the line $L$ must contain a triple of points in $T_{L_1}(S_{init} cup S_{comp})$ or $T_{L_2}(S_{init} cup S_{comp})$.' This is correct but the logic could be stated more explicitly: $L$ has $ge k ge 3$ points of $S_{t-1}$, at most one of which is in the row/column of $(c,r)$, leaving $ge k-1 ge 2$ points; but since $k ge 3$ and the triple requires 3 points, one should clarify that $ge 3$ points remain outside $L_1 cup L_2$ (or at least that a triple can be found).
  8. Notation: the parameter hierarchy (2) uses $a gg b$ to mean $b$ is sufficiently small in terms of $a$, which is non-standard (usually $a gg b$ means $a$ is much larger than $b$). The convention is stated but could be confused with the standard usage; consider a different symbol such as $succ$.
Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

No new mathematical entities are postulated. The proof uses standard combinatorial objects (hypergraphs, matchings, test functions, absorbers) and established theorems. The 'absorber' concept is a proof technique, not a new entity.

free parameters (2)
  • n₀ = absolute constant (not explicitly computed)
    The threshold beyond which the result holds. Existence is proved but exact value is not needed.
  • ε, ρ, α = satisfying 1/k ≫ ρ ≫ α ≫ ε ≫ 1/n
    Intermediate parameters controlling the heaviness thresholds and absorber density in the completion procedure (Section 4, equation (2)). Chosen to satisfy inequalities, not fitted to data.
assumptions (5)
  • standard math Ehard-Glock-Joos pseudorandom matching theorem [12, Theorem 1.3]
    External result providing pseudorandom matchings in hypergraphs with small codegrees. Extended slightly in Lemma 2.2 / Appendix A.
  • standard math Molloy-Reed edge-coloring theorem [28, Theorem 2]
    Used in Appendix A to partition edges of random subgraphs into matchings.
  • standard math Schmidt's theorem on lattice counting [34, Theorem 2]
    Used in Section 5 to bound the number of primitive lattices with bounded determinant.
  • standard math Huxley-Konyagin estimate on cyclic quadrilaterals [21]
    Used in Section 6 (Lemma 6.1) to show most cyclic quadrilaterals are isosceles trapezia.
  • standard math Widmer's lattice point counting result [41, Corollary 2.10]
    Used in Lemma 5.1 to bound lattice point intersections in higher dimensions.

how reviews work

0 comments
Cite this review

Pith. "Pith review of No-$(k+1)$-in-line problem for $k \geqslant 3$." pith.science (2026). https://pith.science/paper/RKEBR6FF

@misc{pith2026260705255,
  author       = {Pith},
  title        = {Pith review of: No-$(k+1)$-in-line problem for $k \geqslant 3$},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RKEBR6FF}},
  note         = {Machine review of arXiv:2607.05255}
}
abstract

What is the maximum number of points one can place in an $n \times n$ grid such that every Euclidean line contains at most $k$ points? For $k = 2$, this is the notorious no-three-in-line problem of Dudeney. In this paper, we resolve this problem for all other $k$ (and sufficiently large $n$). Namely, for $k \geqslant 3$ and sufficiently large $n$, we show that this maximum is exactly $kn$. To prove this, our key observation is that in the regime $k \geqslant 3$, the problem is dominated in a certain statistical sense by the influence of a small number of "heavy" lines with many grid points. We apply a result of Ehard-Glock-Joos on pseudorandom hypergraph matchings to construct a set of size $kn - o(n)$ with at most $k$ points on each heavy line, and then a crude deletion argument yields a no-$(k+1)$-in-line set of nearly the same size. Finally, we use a randomised switching procedure to complete the construction (building upon ideas of Simkin and Luria). Using similar ideas, we also address the no-four-on-a-circle problem of Erd\H{o}s and Purdy. Namely, we prove the existence of a set of $2n - o(n)$ points in the $n \times n$ grid such that no four of these points lie on a circle or a line, improving on the previous construction of size $n - o(n)$ due to Dong and Xu.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

42 extracted references · 42 canonical work pages

  1. [1]

    On a hypergraph matching problem.Graphs Combin., 21(4):377–384, 2005

    Noga Alon and Raphael Yuster. On a hypergraph matching problem.Graphs Combin., 21(4):377–384, 2005

    work page 2005

  2. [2]

    Ball and J

    S. Ball and J. W. P. Hirschfeld. Bounds on (n, r)-arcs and their application to linear codes.Finite Fields Appl., 11(3):326–336, 2005

    work page 2005

  3. [3]

    Primitive points in rational polygons.Canad

    Imre B´ ar´ any, Greg Martin, Eric Naslund, and Sinai Robins. Primitive points in rational polygons.Canad. Math. Bull., 63(4):850–870, 2020

    work page 2020

  4. [4]

    The $n$-queens problem

    Candida Bowtell and Peter Keevash. Then-queens problem, 2021. Preprint, arXiv:2109.08083

    work page Pith review arXiv 2021

  5. [5]

    On counting point-hyperplane incidences.Comput

    Peter Brass and Christian Knauer. On counting point-hyperplane incidences.Comput. Geom., 25(1–2):13–20, 2003. European Workshop on Computational Geometry (CG01)

    work page 2003

  6. [6]

    Peter Brass, William O. J. Moser, and J´ anos Pach. Lattice point problems. InResearch Problems in Discrete Geometry, pages 417–433. Springer, New York, 2005

    work page 2005

  7. [7]

    Private communication

    David Conlon. Private communication

    work page

  8. [8]

    Thresholds for (n, q,2)-Steiner systems via refined absorption.Mathematical Proceedings of the Cambridge Philosophical Society, pages 1–20, 2026

    Michelle Delcourt, Tom Kelly, and Luke Postle. Thresholds for (n, q,2)-Steiner systems via refined absorption.Mathematical Proceedings of the Cambridge Philosophical Society, pages 1–20, 2026

    work page 2026

Show all 42 references
  1. [9]

    Large grid subsets without many cospherical points, 2025

    Zichao Dong and Zijian Xu. Large grid subsets without many cospherical points, 2025. Preprint, arXiv:2506.18113

    2025 arXiv

  2. [10]

    H. E. Dudeney.Amusements in Mathematics. Nelson, London, 1917

    1917

  3. [11]

    Subspace evasive sets

    Zeev Dvir and Shachar Lovett. Subspace evasive sets. InProceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 351–358, 2012. 20

    2012

  4. [12]

    Pseudorandom hypergraph matchings.Combin

    Stefan Ehard, Stefan Glock, and Felix Joos. Pseudorandom hypergraph matchings.Combin. Probab. Comput., 29(6):868–885, 2020

    2020

  5. [13]

    Cambridge University Press, 2018

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

    2018

  6. [14]

    On subsets of lattice cubes avoiding affine and spherical degeneracies,

    Anubhab Ghosal, Ritesh Goenka, and Peter Keevash. On subsets of lattice cubes avoiding affine and spherical degeneracies,

  7. [15]

    Geom., arXiv:2509.06935

    To appear in Discrete Comput. Geom., arXiv:2509.06935

    arXiv

  8. [16]

    Conflict-free hypergraph matchings.J

    Stefan Glock, Felix Joos, Jaehoon Kim, Marcus K¨ uhn, and Lyuben Lichev. Conflict-free hypergraph matchings.J. Lond. Math. Soc. (2), 109(5):Paper No. e12899, 78, 2024

    2024

  9. [17]

    No-(k+1)-in-line problem for large constantk, 2025

    Alexandr Grebennikov and Matthew Kwan. No-(k+1)-in-line problem for large constantk, 2025. Preprint, arXiv:2510.17743

    2025

  10. [18]

    100 open problems

    Ben Green. 100 open problems. Manuscript

  11. [19]

    Guy.Unsolved Problems in Number Theory, volume 1 ofUnsolved Problems in Intuitive Mathematics

    Richard K. Guy.Unsolved Problems in Number Theory, volume 1 ofUnsolved Problems in Intuitive Mathematics. Springer- Verlag, New York, 1981

    1981

  12. [20]

    Guy and Patrick A

    Richard K. Guy and Patrick A. Kelly. The no-three-in-line problem.Canadian Mathematical Bulletin, 11(4):527–531, 1968

    1968

  13. [21]

    R. R. Hall, T. H. Jackson, A. Sudbery, and K. Wild. Some advances in the no-three-in-line problem.J. Combinatorial Theory Ser. A, 18:336–341, 1975

    1975

  14. [22]

    M. N. Huxley and S. V. Konyagin. Cyclic polygons of integer points.Acta Arith., 138(2):109–136, 2009

    2009

  15. [23]

    Optimal thresholds for Latin squares, Steiner triple systems, and edge colorings

    Vishesh Jain and Huy Tuan Pham. Optimal thresholds for Latin squares, Steiner triple systems, and edge colorings. InPro- ceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1425–1436. SIAM, Philadelphia, PA, 2024

    2024

  16. [24]

    Thresholds for Latin squares and Steiner triple systems: bounds within a logarithmic factor.Trans

    Dong Yeap Kang, Tom Kelly, Daniela K¨ uhn, Abhishek Methuku, and Deryk Osthus. Thresholds for Latin squares and Steiner triple systems: bounds within a logarithmic factor.Trans. Amer. Math. Soc., 376(9):6623–6662, 2023

    2023

  17. [25]

    The optimal edge-colouring threshold, 2022

    Peter Keevash. The optimal edge-colouring threshold, 2022. Preprint, arXiv:2212.04397

    2022 arXiv

  18. [26]

    Benedek Kov´ acs, Zolt´ an L´ or´ ant Nagy, and D´ avid R. Szab´ o. Randomised algebraic constructions for the no-(k+ 1)-in-line problem, 2025. Preprint, arXiv:2508.07632

    2025 arXiv

  19. [27]

    Benedek Kov´ acs, Zolt´ an L´ or´ ant Nagy, and D´ avid R. Szab´ o. Settling the no-(k+ 1)-in-line problem whenkis not small, 2025. Preprint, arXiv:2502.00176

    2025 arXiv

  20. [28]

    Extensions of the no-three-in-line problem

    Hanno Lefmann. Extensions of the no-three-in-line problem. Preprint, 2012

    2012

  21. [29]

    Near-optimal list colorings.Random Structures & Algorithms, 17(3–4):376–402, 2000

    Michael Molloy and Bruce Reed. Near-optimal list colorings.Random Structures & Algorithms, 17(3–4):376–402, 2000

    2000

  22. [30]

    Alexander Novikov, Ngˆ an V˜ u, Marvin Eisenberger, Emilien Dupont, Po-Sen Huang, Adam Zsolt Wagner, Sergey Shirobokov, Borislav Kozlovskii, Francisco J. R. Ruiz, Abbas Mehrabian, M. Pawan Kumar, Abigail See, Swarat Chaudhuri, George Holland, Alex Davies, Sebastian Nowozin, Pu...

    2025 arXiv

  23. [31]

    Asymptotic behavior of the chromatic index for hypergraphs.J

    Nicholas Pippenger and Joel Spencer. Asymptotic behavior of the chromatic index for hypergraphs.J. Combin. Theory Ser. A, 51(1):24–42, 1989

    1989

  24. [32]

    Constraint satisfaction programming for the no-three-in-line problem, 2026

    Thomas Prellberg. Constraint satisfaction programming for the no-three-in-line problem, 2026. Preprint, arXiv:2602.07751

    2026

  25. [33]

    K. F. Roth. On a problem of Heilbronn.J. London Math. Soc., 26:198–204, 1951

    1951

  26. [34]

    Threshold for Steiner triple systems.Geom

    Ashwin Sah, Mehtaab Sawhney, and Michael Simkin. Threshold for Steiner triple systems.Geom. Funct. Anal., 33(4):1141– 1172, 2023

    2023

  27. [35]

    Wolfgang M. Schmidt. Asymptotic formulae for point lattices of bounded determinant and subspaces of bounded height.Duke Math. J., 35:327–339, 1968

    1968

  28. [36]

    The number ofn-queens configurations.Adv

    Michael Simkin. The number ofn-queens configurations.Adv. Math., 427:Paper No. 109127, 83, 2023

    2023

  29. [37]

    A lower bound for then-queens problem

    Michael Simkin and Zur Luria. A lower bound for then-queens problem. InProceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2185–2197. [Society for Industrial and Applied Mathematics (SIAM)], Philadelphia, PA, 2022

    2022

  30. [38]

    Evasive sets, covering by subspaces, and point-hyperplane incidences.Discrete Comput

    Benny Sudakov and Istv´ an Tomon. Evasive sets, covering by subspaces, and point-hyperplane incidences.Discrete Comput. Geom., 72(3):1333–1347, 2024

    2024

  31. [39]

    On higher dimensional point sets in general position.Combin

    Andrew Suk and Ji Zeng. On higher dimensional point sets in general position.Combin. Probab. Comput., 35(1):134–148, 2026

    2026

  32. [40]

    PhD thesis, Institut f¨ ur Mathematik II, Freie Universit¨ at Berlin, Berlin, 1995

    Torsten Thiele.Geometric Selection Problems and Hypergraphs. PhD thesis, Institut f¨ ur Mathematik II, Freie Universit¨ at Berlin, Berlin, 1995

    1995

  33. [41]

    The no-four-on-circle problem.Journal of Combinatorial Theory, Series A, 71(2):332–334, 1995

    Torsten Thiele. The no-four-on-circle problem.Journal of Combinatorial Theory, Series A, 71(2):332–334, 1995

    1995

  34. [42]

    Lipschitz class, narrow class, and counting lattice points.Proceedings of the American Mathematical Society, 140(2):677–689, 2012

    Martin Widmer. Lipschitz class, narrow class, and counting lattice points.Proceedings of the American Mathematical Society, 140(2):677–689, 2012. AppendixA.Deduction of Lemma 2.2 from[12] First, we deduce the following version of Lemma 2.2 that requires thatw(E(H)) is large co...

    2012

Pith tools

Reviewed July 7, 2026 · model on record in the stance chip above.