Settling the no-$(k+1)$-in-line problem when $k$ is not small

Benedek Kov\'acs; D\'avid R. Szab\'o; Zolt\'an L\'or\'ant Nagy

REVIEW 3 major objections 4 minor 1 cited by

Settling the no-$(k+1)$-in-line problem when $k$ is not small

T0 review · 3 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash

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

Pith's one-line read This paper proves that an n×n grid can hold kn points with no k+1 collinear whenever k is at least a constant times √(n log n), making the trivial row bound tight.

desk verdict Real exact result for large k, but the claimed absolute constant in Theorem 2.4 needs referee verification — worth a serious look. read the letter →

arxiv 2502.00176 v1 pith:LFXMDLKZ submitted 2025-01-31 math.CO

Benedek Kovács , Zoltán Lóránt Nagy , Dávid R. Szabó This is my paper · ORCID

classification math.CO MSC 05D4005C8005C3552C10

keywords no-(k+1)-in-lineproblemno-three-in-linelatticepointsregularbipartitegraphsprobabilisticmethodlineintersectionsextremalcombinatoricsconcentrationinequalities

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 paper targets a generalization of the no-three-in-line problem: how many points can be chosen from an n×n grid without any k+1 of them lying on one line? It proves that when k grows faster than about √(n log n), the exact answer is kn, the trivial bound obtained by allowing at most k points per row. This settles the exact extremal value in a broad range where no exact determination was previously known. The proof is probabilistic: it builds kn points by randomly filling rows and columns with a deliberate density bias, so that every non-axis-parallel line sees well below k points in expectation, and then uses concentration inequalities to control all lines at once.

What carries the argument

The load-bearing object is the bi-uniform random graph: a union of independent uniform r_{i,j}-regular bipartite graphs on the 16 subgrids, with r_{i,j} taking two prescribed values according to a 4×4 sparse/dense pattern. Its feasibility matrix R records these densities, and R is (k, 4/5)-feasible, meaning the row and column sums of R are k and every generic secant's expected number of selected points is at most 4k/5. The proof's main lemma controls the probability that any secant exceeds a threshold: it bounds the union over lines by way of a matching-probability theorem for regular bipartite graphs, converts those bounds into exponential tails, and sums over all long secants using a grid line-count estimate. The final ingredient is reserve: the random set has at least 15 points of slack on every generic line, which the authors exploit through a line-colouring decomposition and an orthogonal projection step to pass from divisible n and k to all n and k.

What would settle it

For fixed α in (0,1), sample uniform r = αm regular bipartite graphs on m+m vertices for growing m, and estimate sup_M P(M ⊆ G)/(r/m)^{|M|} over matchings M; if this ratio is unbounded, the absolute matching-probability constant used in Lemma 3.6 fails and the main theorem loses its uniform proof.

Watch

Extended reading notes

Core claim

The central claim, Theorem 1.2, is that for every constant C > 25/2 (stated as C > (5/2)√35 in the theorem and improved in Remark 3.11) there is a threshold N_C such that f_k(n) = kn for all n ≥ N_C and k ≥ C√(n log n). The upper bound kn is trivial by counting points in rows; the content is the matching lower bound. The construction partitions the grid into 16 equal square blocks, marks the diagonal blocks as sparse and the off-diagonal blocks as dense, and in each block independently selects a uniform random r-factor with r = 2k/10 for sparse blocks and r = 3k/10 for dense blocks. Every row and every column then contains exactly k selected points, while any non-axis-parallel line has expected intersection at most 4k/5. A concentration lemma, built from a matching-enumeration bound for regular bipartite graphs and a Chernoff-type inequality for dependent variables, shows that with high probability no generic line exceeds k − 15, giving the desired set with reserve 15; elementary row-and-column adjustments then remove the divisibility assumptions on n and k.

Load-bearing premise

Everything rests on the imported claim that a single absolute constant controls the probability that a random regular bipartite graph contains a fixed matching, uniformly in the graph size.

Editorial extensions

If this is right

For every fixed C > 12.5, once n is large and k ≥ C√(n log n), an n×n grid contains kn points with no k+1 collinear, so the row-count upper bound f_k(n) ≤ kn is tight throughout this whole range.
The same construction produces such sets with reserve 15 on every non-axis-parallel line, so small changes in k or n can be absorbed while keeping the extremal value.
The classical no-three-in-line problem with k = 2 remains open, but the generalized problem is now settled on an unbounded range of k, removing a long-standing family of open extremal questions in that regime.
Any improvement in the line-count exponent or in the matching-probability bound immediately shrinks the threshold constant C, since these quantities enter the main probability estimate directly.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The threshold √(n log n) is likely not the end of the story: the paper explicitly leaves open the possibility that f_k(n) = kn for k as small as n^ε for every ε > 0, and sharper line-count or matching-enumeration bounds would plausibly push the method into that range.
The sparse/dense block-bias idea may transfer to other settings with a known line-count bound, such as non-square grids or higher-dimensional lattices, where the trivial hyperplane bound could again be tight under a comparable scale condition.
A natural finite check not performed in the paper is to estimate the matching-probability ratio for moderate grid sizes; if that ratio stayed bounded, the black-box constant on which the proof relies would be experimentally credible.

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.

Desk Editor's Note

read the letter

Colleague,

This paper proves what looks like the right answer for a large regime: f_k(n)=kn whenever k ≥ C√(n log n). That is a genuine advance — prior work had asymptotics and bounds, not an exact value in this range. The construction is clever: split the grid into 4x4 subgrids, choose random regular bipartite factors with sparse/dense blocks, and use concentration to show no line gets more than k points. The upper bound is trivial, so the whole game is the lower bound, and the probabilistic machinery is well organized.

The main soft spot is Theorem 2.4, the black-box bound on the probability that a random regular bipartite graph contains a fixed matching. The proof given in the paper is compressed: it cites [16] with δ = 1/m and claims an absolute constant K, but the displayed exponent contains a term n ε^{-1/2} that is not constant in n. Either the cited theorem has a different normalization, or the authors have misread it. This matters because K enters the threshold constant C. If K depends on m, the stated C > 25/2 may not hold as written; the argument would still go through with a slightly larger C, but that is not what the theorem claims. A referee needs to check the Isaev–McKay statement directly. This is the one place I cannot certify the proof from the preprint.

Minor issues: reference [11] is "personal communication" and is cited in the conclusion as if it were a paper; and Lemma 3.6 writes an equality where only an inclusion is true. Neither affects the argument.

Who is this for? Extremal combinatorists and people who care about lattice point problems. It is a solid, clearly written paper with a real result. If the black box checks out, it is a nice theorem. I would send it to a serious referee.

Recommendation: engage with it; accept for review.

Referee Report

3 major / 4 minor

Summary. The paper studies the no-(k+1)-in-line problem for the n x n integer grid: what is the maximum number f_k(n) of points one can select with no k+1 points on any line. The trivial row-count upper bound is kn. The authors prove that for every C > (5/2)sqrt(35) (and by Remark 3.11, any C > 25/2) there is N_C such that f_k(n)=kn whenever n >= N_C and k >= C sqrt(n log n). The proof combines an explicit construction for k >= 2n/3 and a probabilistic construction for k <= 5n/6, using a 4x4 subdivision into subgrids, independent uniform random regular bipartite graphs in each subgrid with sparse/dense densities, and concentration inequalities. Divisibility conditions on n and k are removed via two adjustment lemmas (reducing k and extending the grid). The central probabilistic lemmas (3.5-3.7, Corollary 3.8) control the intersection of the random set with generic lines and yield a set with positive reserve, giving the lower bound. The paper is well-organized and largely self-contained except for a cited enumeration bound (Theorem 2.4).

Significance. If correct, this is a substantial advance on a century-old problem: it determines the exact extremal value f_k(n)=kn for all k slightly above sqrt(n log n), showing that the trivial row bound is asymptotically tight in this regime. The random bipartite graph construction with a feasible density matrix (delta=4/5) is elegant and novel, and the reduction lemmas that pass from divisible n,k to the general case are clean and explicit. The paper also gives an explicit universal constant in the main theorem and notes a possible improvement to C>12.5. The main risk is the black-box reliance on Theorem 2.4 (the Isaev-McKay matching-containment bound); that issue is addressed in the major comments. Overall, the result, if fully substantiated, would be a notable contribution to lattice point geometry and extremal combinatorics.

major comments (3)

[Section 2.2, Theorem 2.4 and its proof] The absoluteness of the constant K in Theorem 2.4 is not established. The proof sets delta=1/m, which is not a fixed constant, and claims that c-tilde(delta,epsilon,c1,c2) is absolute without demonstrating that the error terms in [16, Theorem 5.8] are uniform as delta tends to 0. Moreover, the displayed bound on |K-tilde'| contains the term n*epsilon^{-1/2}, which is unbounded as n grows; the claimed conclusion |K-tilde'| <= exp(3 c-tilde)-1 therefore does not follow from the displayed expression. This is load-bearing because Lemma 3.6 applies Theorem 2.4 to every subgrid (with m=n/4) and every matching arising from a generic line, and D1 depends on log K. If K actually depends on m (e.g., exponentially in 1/delta), the constant C in Theorem 1.2 would have to grow with n, breaking the stated result. The authors must either provide a self-contained proof of a uniform matching-containment bound for random r-regular bipartite graphs, or state and verify the precise version of [16, Theorem 5.8] they invoke, including uniformity of the error term as delta=1/m -> 0.
[Section 3.2, Proposition 3.9, Eq. (3.5)] The displayed expression for D3 in (3.5) is inconsistent with the definitions in Lemmas 3.6 and 3.7. From D2 = sqrt(7n)*D1 + 7 and D1 of order sqrt(log n), the leading term of D3 should be 5*sqrt(7(4-3epsilon)/2) * sqrt(n log n), not 5*sqrt(7(4-3epsilon)/2) * n log n, and the second term should be of order O(sqrt(n/log n)*log K), not (7/2) n log(7*2KL). As printed, the right-hand side is O(n log n) + O(n), which for fixed C would exceed k ~ C sqrt(n log n) for all sufficiently large n and would make the inequality C sqrt(n log n) >= D3 impossible. This is presumably a typographical error, but it must be corrected so that the threshold constant (5/2)sqrt(35) can be verified.
[Section 3.2, Lemma 3.6, proof] The proof contains the displayed equality P(sum s_{i,j} > sum kappa_{i,j}) = P(exists (i,j) : s_{i,j} > kappa_{i,j}), which is not correct as an equality: it is only an inclusion (the left event is contained in the union on the right). The subsequent use of the union bound requires only the inclusion, so the argument survives, but the statement as written is inaccurate and should be changed to a subset relation.

minor comments (4)

[Section 3.3, proof of Theorem 1.2] The definition of h'' is written as h'' := 2(n - n'), which is nonpositive because n <= n'. It should be h'' := 2(n' - n) (which lies in {0,2,4,6}). The subsequent sentence 'S' has reserve h''' should be 'S' has reserve at least h''', since h' >= h'' is used.
[Section 2.2, proof of Theorem 2.4] The term n*epsilon^{-1/2} in the bound on |K-tilde'| is likely a typo for n^{-1/2}*epsilon^{-1/2} or a similar decaying factor. As written, the displayed bound cannot be bounded by a constant independent of n. This is tied to Major Comment 1 and should be clarified.
[Section 3.2, Lemma 3.7] For a subgrid with g_{i,j}(ell)=1, the interval for beta in (3.2) can force beta > 1, so Theorem 2.2 (which requires 0<beta<1) is not directly applicable. This is easily fixed by treating g=1 separately (the probability of exceeding kappa is then 0 for kappa >= 1), but the current proof does not address it.
[Section 3.1, Lemma 3.5] The remark that delta=4/5 is the smallest value for which a (k,delta)-feasible 4x4 matrix exists (with at most four distinct entries) is stated without proof. If retained, it should be accompanied by a short justification or a reference.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof constructs point sets of size kn and never defines the target quantity in terms of itself.

full rationale

The paper's central claim is that f_k(n)=kn for k above a threshold. The upper bound f_k(n)≤kn is a standard row-count observation, and the proof supplies an independent lower bound by explicitly constructing a no-(k+1)-in-line set of size kn. The construction sets subgrid densities via the matrix R in (3.1), checks that the expected number of selected points on each generic secant is at most δk with δ=4/5, and then uses concentration inequalities (Theorem 2.2) and the external Isaev–McKay bound (Theorem 2.4) to show that all lines have at most k points. None of these ingredients is defined in terms of f_k(n), and no fitted parameter is later renamed as a prediction. The only self-citation, reference [22], appears in a contextual sentence about related problems and is not load-bearing for the proof. The reliance on Theorem 2.4 as an external black box may raise verification concerns, but it is not circularity: the theorem is stated as an independent result about uniform random regular bipartite graphs with explicit hypotheses, and the present proof uses it as a tool rather than assuming the target answer kn. Adjustments for general n and k in Section 3.3 use König's theorem and elementary projection arguments, again without importing the conclusion. The derivation chain is therefore self-contained in the sense relevant to circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The proof relies on standard external theorems listed above rather than on new entities or fitted parameters. The constants delta=4/5, h=15, epsilon=1/2, and p=1/2 are internal choices made to satisfy the inequalities; they are not data-derived and do not encode the target answer.

assumptions (4)

standard math Chernoff-Hoeffding concentration bounds and Linial-Luria inequality for sums of dependent indicators
Used in Section 2.2 and Lemma 3.6 to bound line-intersection tails.
standard math Erdos-Szemeredi-Trotter bound on number of large secants of the n by n grid: L_{>kappa}(G) <= L n^4 / kappa^3
Invoked in Lemma 3.6 to close the union bound; stated as Theorem 2.3.
standard math Isaev-McKay enumeration bound as stated in Theorem 2.4: a uniform random r-regular bipartite graph contains any fixed matching M with probability at most K(r/m)^|M| for an absolute constant K
Central to Lemma 3.6; the paper gives only a sketch via [16, Theorem 5.8].
standard math Konig's line coloring theorem and Hall's marriage theorem for decomposing regular bipartite graphs into perfect matchings
Used in Section 3.3, Lemmas 3.12 and 3.13, and Proposition 3.1.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Settling the no-$(k+1)$-in-line problem when $k$ is not small." pith.science (2026). https://pith.science/paper/LFXMDLKZ

@misc{pith2026250200176,
  author       = {Pith},
  title        = {Pith review of: Settling the no-$(k+1)$-in-line problem when $k$ is not small},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LFXMDLKZ}},
  note         = {Machine review of arXiv:2502.00176}
}

abstract

What is the maximum number of points that can be selected from an $n \times n$ square lattice such that no $k+1$ of them are in a line? This has been asked more than $100$ years ago for $k=2$ and it remained wide open ever since. In this paper, we prove the precise answer is $kn$, provided that $k>C\sqrt{n\log{n}}$ for an absolute constant $C$. The proof relies on carefully constructed bi-uniform random bipartite graphs and concentration inequalities.

Figures

Figures reproduced from arXiv: 2502.00176 by the authors.

**Figure 2.** The arrangement of the sparse and dense subgrids an [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

No-$(k+1)$-in-line problem for $k \geqslant 3$
math.CO 2026-07 accept novelty 8.0 of 10

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.

Reference graph

Works this paper leans on

28 extracted references · 26 canonical work pages · cited by 1 Pith paper

[16]

Isaev and B

M. Isaev and B. D. McKay. Complex martingales and asympt otic enumeration. Random Structures & Algorithms , 52(4):617–661, 2018

work page 2018
[11]

P. Gao. personal communication

work page
[1]

Aichholzer, D

O. Aichholzer, D. Eppstein, and E.-M. Hainzl. Geometric dominating sets - a minimum version of the No-Three- In-Line problem. Computational Geometry , 108:Article 101913, 2023

work page 2023
[2]

D. B. Anderson. Update on the no-three-in-line problem. Journal of Combinatorial Theory, Series A , 27(3):365–366, 1979

work page 1979
[3]

S. Ball, A. Blokhuis, and F. Mazzocca. Maximal arcs in des arguesian planes of odd order do not exist. Combinatorica, 17(1):31–41, 1997. 12

work page 1997
[4]

Ball and J

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

work page 2005
[5]

R. C. Bose. Mathematical theory of the symmetrical facto rial design. Sankhy¯ a: The Indian Journal of Statistics , pages 107–166, 1947

work page 1947
[6]

Brass, W

P. Brass, W. O. J. Moser, and J. Pach. Lattice Point Problems , pages 417–433. Springer New York, New York, NY, 2005

work page 2005

Show all 28 references

[7]

R. H. Denniston. Some maximal arcs in ﬁnite projective pl anes. Journal of Combinatorial Theory , 6(3):317–319, 1969

1969
[8]

H. E. Dudeney. Amusements in mathematics , volume 473. Courier Corporation, 1917

1917
[9]

Eppstein

D. Eppstein. Forbidden conﬁgurations in discrete geometry . Cambridge University Press, 2018

2018
[10]

Flammenkamp

A. Flammenkamp. Progress in the no-three-in-line prob lem, II. Journal of Combinatorial Theory, Series A , 81(1):108–113, 1998

1998
[12]

B. Green. 100 open problems. Manuscript, available on r equest to Professor Green
[13]

Greenhill and B

C. Greenhill and B. D. McKay. Random dense bipartite gra phs and directed graphs with speciﬁed degrees. Random Structures & Algorithms , 35(2):222–249, 2009

2009
[14]

R. K. Guy and P. A. Kelly. The no-three-in-line problem. Canadian Mathematical Bulletin , 11:527–531, 1968

1968
[15]

R. R. Hall, T. H. Jackson, A. Sudbery, and K. Wild. Some ad vances in the no-three-in-line problem. Journal of Combinatorial Theory, Series A , 18(3):336–341, 1975

1975
[17]

Klimoˇ sov´ a, C

T. Klimoˇ sov´ a, C. Reiher, A. Ruci´ nski, and M. ˇSileikis. Sandwiching biregular random graphs. Combinatorics, Probability and Computing , 32(1):1–44, 2023

2023
[18]

H. Lefmann. No l grid-points in spaces of small dimension. In Algorithmic Aspects in Information and Management , pages 259–270, Berlin, Heidelberg, 2008. Springer Berlin H eidelberg

2008
[19]

Liebenau and N

A. Liebenau and N. Wormald. Asymptotic enumeration of d igraphs and bipartite graphs by degree sequence. Random Structures & Algorithms , 62(2):259–286, 2023

2023
[20]

Linial and Z

N. Linial and Z. Luria. Chernoﬀ’s inequality-a very ele mentary proof. arXiv preprint arXiv:1403.7739 , 2014

2014 arXiv
[21]

B. D. McKay. Subgraphs of random graphs with speciﬁed de grees. In Proceedings of the International Congress of Mathematicians 2010 , pages 2489–2501. World Scientiﬁc, 2010

2010
[22]

D. T. Nagy, Z. L. Nagy, and R. Woodroofe. The extensible n o-three-in-line problem. European Journal of Combin- atorics, 114:103796, 2023

2023
[23]

Pach and G

J. Pach and G. T´ oth. Graphs drawn with few crossings per edge. Combinatorica, 17(3):427–439, 1997

1997
[24]

P´ or and D

A. P´ or and D. R. Wood. No-three-in-line-in-3D. Algorithmica, 47(4):481–488, 2007

2007
[25]

K. F. Roth. On a problem of Heilbronn. The Journal of the London Mathematical Society , 26:198–204, 1951

1951
[26]

B. Segre. Curve razionali normali e k-archi negli spazi ﬁniti. Annali di Matematica Pura ed Applicata (4) , 39:357–379, 1955

1955
[27]

B. Segre. Ovals in a ﬁnite projective plane. Canadian Journal of Mathematics , 7:414–416, 1955

1955
[28]

Szemer´ edi and W

E. Szemer´ edi and W. T. Trotter. Extremal problems in di screte geometry. Combinatorica, 3:381–392, 1983. 13

1983

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.

[1] [16]

Isaev and B

M. Isaev and B. D. McKay. Complex martingales and asympt otic enumeration. Random Structures & Algorithms , 52(4):617–661, 2018

work page 2018

[2] [11]

P. Gao. personal communication

work page

[3] [1]

Aichholzer, D

O. Aichholzer, D. Eppstein, and E.-M. Hainzl. Geometric dominating sets - a minimum version of the No-Three- In-Line problem. Computational Geometry , 108:Article 101913, 2023

work page 2023

[4] [2]

D. B. Anderson. Update on the no-three-in-line problem. Journal of Combinatorial Theory, Series A , 27(3):365–366, 1979

work page 1979

[5] [3]

S. Ball, A. Blokhuis, and F. Mazzocca. Maximal arcs in des arguesian planes of odd order do not exist. Combinatorica, 17(1):31–41, 1997. 12

work page 1997

[6] [4]

Ball and J

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

work page 2005

[7] [5]

R. C. Bose. Mathematical theory of the symmetrical facto rial design. Sankhy¯ a: The Indian Journal of Statistics , pages 107–166, 1947

work page 1947

[8] [6]

Brass, W

P. Brass, W. O. J. Moser, and J. Pach. Lattice Point Problems , pages 417–433. Springer New York, New York, NY, 2005

work page 2005