pith. sign in

arxiv: 2606.02843 · v1 · pith:4MUSKOYXnew · submitted 2026-06-01 · 🧮 math.CO

The extensible no-(k(n)+1)-in-line problem

Tam\'as G\'abriel , M\'at\'e J\'anosik , D\'avid Melj\'an , Benedek N\'ador This is my paper

Pith reviewed 2026-06-28 13:31 UTC · model grok-4.3

classification 🧮 math.CO
keywords no-k-in-line problemextensiblecollinear pointspoint densityinteger gridcombinatorial geometrypolynomial growth
0
0 comments X

The pith

Any configuration achieving liminf S_n/(n k(n)) at least 0.897 must have k(n) grow as Omega(n^c) for some c>0.

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

The extensible no-(k(n)+1)-in-line problem asks for the densest subset of the integer grid such that at most k(n) points are collinear inside any n by n square. The authors give constructions that achieve optimal or positive density when k(n) is linear or a power of n. They prove that any set reaching a liminf density ratio of 0.897 or higher forces k(n) to grow at least polynomially. This rules out constant k at that density threshold. They also reduce the general case to the constant-k case by showing that a positive-density solution for fixed k extends to any sufficiently regular varying k(n).

Core claim

The central claim is that any point configuration satisfying liminf S_n / (n k(n)) >= 0.897 in the extensible no-(k(n)+1)-in-line problem must satisfy k(n) = Omega(n^c) for some constant c>0, so the problem admits no such high-density configurations when k is constant. Optimal sets are constructed for linear k(n), positive-density sets for power k(n), and the problem is reduced to the constant-k case by proving that positive density for constant k yields positive density for any sufficiently regular k(n).

What carries the argument

The liminf density ratio S_n/(n k(n)) combined with a combinatorial counting argument that derives a polynomial lower bound on k(n) from any sufficiently high value of the ratio.

If this is right

  • Optimal point sets exist for linear functions k(n).
  • Positive-density point sets exist for power functions k(n).
  • Existence of a positive-density set for constant k implies existence for any sufficiently regular k(n).
  • No configuration with constant k can achieve the 0.897 density threshold.

Where Pith is reading between the lines

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

  • For constant k the maximal achievable density must be o(n), even if superlinear in k.
  • The reduction implies the constant-k instance is the core hard case for the whole family of extensible problems.
  • Small-n computational enumeration could check whether densities approach 0.897 before any polynomial growth in k(n) becomes necessary.
  • Analogous density thresholds might separate feasible and infeasible regimes in other grid-avoidance problems.

Load-bearing premise

The combinatorial counting argument that extracts a polynomial growth lower bound on k(n) from the density assumption applies without additional regularity conditions on the point set.

What would settle it

An explicit point-set construction with constant k that achieves liminf S_n/(n k(n)) >= 0.897, or a counterexample showing the polynomial lower bound does not follow from the density assumption alone.

Figures

Figures reproduced from arXiv: 2606.02843 by Benedek N\'ador, D\'avid Melj\'an, M\'at\'e J\'anosik, Tam\'as G\'abriel.

Figure 1
Figure 1. Figure 1: for c = 1 3 Case 0: l is horizontal or vertical. If l is horizontal, it contains at most ⌈(n − A)/m2 ⌉m + m = ⌈(n − 2m2 )/m2 ⌉m + m = = ⌈n/m2 − 2⌉m + m ≤ [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The gaps in grey and Sk in white two positive integers, whose denominator is 10k . Denote this denominator by mk, that is mk = 10k . To begin the construction, we create a gap G1, consisting of the first g1 = 2m2 1 rows and columns. The points within any gap are permanently excluded from the selection throughout the entire con￾struction of S. Next, within square [g1 + 1, s1] 2 let our configuration, be S ∩… view at source ↗
Figure 3
Figure 3. Figure 3: Comparison of positive and negative gradients [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Point set S if k(n) = n 0.5 , with m ≥ 4 If m is large enough, the following inequality holds: 1 2 1 α  1 α − 1  (Am + ε) 1 α −2 ≤ 1 2α2 (Am) 1 α −2 Rearranging the terms yields 1 − α ≤  Am Am + ε  1 α −2 , Which holds if m is large enough. Thus we get the following upper and lower bounds: c − 1 α 1 α (Am) 1 α −1 ≤ wm ≤ c − 1 α 1 α (Am) 1 α −1 + c − 1 α 1 2α2 (Am) 1 α −2 Approximating sm: sm ≥ hm wm − … view at source ↗
Figure 6
Figure 6. Figure 6: III/b) q ≥ 2 Remark 2.11. We did not attempt to optimize the density of the lim inf with this type of con￾struction, it might be larger, we suspect that in fact, this construction is not optimal. Furthermore, we checked that this ’tower’ construction works for polynomially growing functions k(n) only, and does not provide a positive density set for slower growing functions. 3 Criteria for large lim inf n→∞… view at source ↗
Figure 7
Figure 7. Figure 7: Shifting up and deleting the points lying in the left-bottom square. [PITH_FULL_IMAGE:figures/full_fig_p022_7.png] view at source ↗
read the original abstract

The classical no-$k$-in-line problem asks for the largest number of points that can be placed on an $n \times n$ grid without having $k$ of them collinear. A natural extension, motivated by the analogous question by Erde for $k\in \mathbb{Z}$, is the \emph{extensible no-$(k(n)+1)$-in-line problem}, which seeks a subset of points in $\mathbb{Z}^2$ with maximal possible density such that at most $k(n)$ points are collinear within the subgrid $[1,n]^2$. We construct optimal sets for linear functions and positive-density sets for power functions. We prove that any configuration achieving $\liminf\frac{S_n}{n k(n)} \ge 0.897$ must satisfy $k(n) = \Omega( n^c)$ for some $c>0$ constant; therefore, the extensible no-$k$-in-line problem has no configuration with this property when $k$ is a constant. Finally, we reduce the problem to the extensible no-$k$-in-line problem, showing that if a positive-density point-set exists for a constant limiter function, then one also exists for any sufficiently regular function $k(n)$.

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.

Referee Report

2 major / 1 minor

Summary. The manuscript introduces the extensible no-(k(n)+1)-in-line problem on Z^2, seeking maximal-density point sets where at most k(n) points are collinear inside any [1,n]^2 subgrid. It constructs optimal sets for linear k(n) and positive-density sets for power functions k(n), proves that any configuration with liminf S_n/(n k(n)) >= 0.897 requires k(n) = Omega(n^c) for some c>0 (hence constant k is impossible), and reduces the general case to the constant-limiter problem under regularity assumptions on k(n).

Significance. If the impossibility result and constructions hold, the work supplies both positive-density examples for growing k(n) and a density threshold that forces super-constant growth, sharpening the boundary between achievable and impossible densities in variable-limiter collinearity problems.

major comments (2)
  1. [Abstract] Abstract: the central negative claim that liminf S_n/(n k(n)) >= 0.897 forces k(n) = Omega(n^c) rests on an unspecified combinatorial counting argument that extracts polynomial growth from the density hypothesis; no sketch, double-counting identity, or extremal tool is supplied, so the implication cannot be verified for arbitrary point sets.
  2. [Abstract] Abstract: the numerical threshold 0.897 is stated without derivation, error analysis, or indication of how it arises from the underlying counting argument, leaving the precise cutoff uncheckable.
minor comments (1)
  1. [Abstract] Abstract: the reduction statement mentions 'sufficiently regular' k(n) but supplies no definition of regularity; add the precise conditions (e.g., monotonicity, growth rate) under which the implication holds.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their detailed reading of the manuscript. Below we respond point-by-point to the two major comments, both of which concern the presentation of the negative result in the abstract. We agree that additional clarity is warranted and will revise accordingly.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central negative claim that liminf S_n/(n k(n)) >= 0.897 forces k(n) = Omega(n^c) rests on an unspecified combinatorial counting argument that extracts polynomial growth from the density hypothesis; no sketch, double-counting identity, or extremal tool is supplied, so the implication cannot be verified for arbitrary point sets.

    Authors: The full proof of the negative result is contained in Section 3. It proceeds by a double-counting argument that bounds the total number of point-line incidences under the density hypothesis, then applies a simple extremal estimate (a variant of the Szemerédi–Trotter incidence bound specialized to axis-aligned grids) to extract the required polynomial lower bound on k(n). We will add a concise one-sentence sketch of this counting argument to the abstract in the revised version. revision: yes

  2. Referee: [Abstract] Abstract: the numerical threshold 0.897 is stated without derivation, error analysis, or indication of how it arises from the underlying counting argument, leaving the precise cutoff uncheckable.

    Authors: The constant 0.897 is the explicit numerical value obtained by optimizing the leading coefficient in the incidence bound of Section 3 (specifically, the maximum of a quadratic function arising from the double-counting identity when the growth of k(n) is assumed sub-polynomial). We will append a short parenthetical clause to the abstract indicating that the threshold is the optimum of this coefficient. revision: yes

Circularity Check

0 steps flagged

No circularity: claims rest on combinatorial constructions and counting arguments from definitions

full rationale

The paper states constructions for linear and power functions, a density-based impossibility result via combinatorial counting, and a reduction between constant and regular k(n). No equations or steps are shown to reduce by construction to fitted inputs, self-definitions, or load-bearing self-citations. The liminf implication is presented as following from standard density and collinearity definitions rather than any ansatz or renaming that loops back to the target result. The derivation is therefore self-contained against external combinatorial benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract, the paper rests on standard definitions of collinearity in the integer lattice, asymptotic density, and liminf; no free parameters, invented entities, or non-standard axioms are mentioned.

axioms (1)
  • standard math Collinearity is the standard geometric notion on Z^2; density is the usual liminf of points inside [1,n]^2 divided by n^2.
    Invoked throughout the problem statement and all stated results.

pith-pipeline@v0.9.1-grok · 5769 in / 1440 out tokens · 25470 ms · 2026-06-28T13:31:18.101865+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

66 extracted references · 4 canonical work pages

  1. [1]

    arXiv preprint arXiv:2105.11431 , year=

    A lower bound for the n -queens problem , author=. arXiv preprint arXiv:2105.11431 , year=

    arXiv

  2. [2]

    and Kelly, Patrick A

    Guy, Richard K. and Kelly, Patrick A. , TITLE =. Canadian Mathematical Bulletin , VOLUME =. 1968 , PAGES =. doi:10.4153/CMB-1968-062-3 , URL =

    work page doi:10.4153/cmb-1968-062-3 1968

  3. [3]

    arXiv preprint arXiv:2109.08083 , year=

    The n -queens problem , author=. arXiv preprint arXiv:2109.08083 , year=

    arXiv

  4. [4]

    Advances in Mathematics , volume=

    The number of n-queens configurations , author=. Advances in Mathematics , volume=. 2023 , publisher=

    2023

  5. [5]

    Note on the existence of large minimal blocking sets in

    Sz. Note on the existence of large minimal blocking sets in. Combinatorica , volume=. 1992 , publisher=

    1992

  6. [6]

    Finite Fields and Their Applications , volume=

    Bounds on (n, r)-arcs and their application to linear codes , author=. Finite Fields and Their Applications , volume=. 2005 , publisher=

    2005

  7. [7]

    arXiv preprint arXiv:1403.7739 , year=

    Chernoff's Inequality-A very elementary proof , author=. arXiv preprint arXiv:1403.7739 , year=

    Pith/arXiv arXiv

  8. [8]

    arXiv preprint arXiv:2502.00176 , year=

    Settling the no- (k+ 1) -in-line problem when k is not small , author=. arXiv preprint arXiv:2502.00176 , year=

    arXiv

  9. [9]

    2025 , eprint=

    Randomised algebraic constructions for the no- (k+1) -in-line problem , author=. 2025 , eprint=

    2025

  10. [10]

    Combinatorica , volume=

    Graphs drawn with few crossings per edge , author=. Combinatorica , volume=. 1997 , publisher=

    1997

  11. [11]

    Combinatorica , volume=

    Extremal problems in discrete geometry , author=. Combinatorica , volume=. 1983 , publisher=

    1983

  12. [12]

    An extension of the Ruzsa-Szemer

    S. An extension of the Ruzsa-Szemer. Combinatorica , volume=. 2004 , publisher=

    2004

  13. [13]

    , TITLE =

    Roth, Karl F. , TITLE =. The Journal of the London Mathematical Society , VOLUME =. 1951 , PAGES =. doi:10.1112/jlms/s1-26.3.198 , URL =

    work page doi:10.1112/jlms/s1-26.3.198 1951

  14. [14]

    No-three-in-line-in-3

    P\'. No-three-in-line-in-3. Algorithmica , FJOURNAL =. 2007 , NUMBER =. doi:10.1007/s00453-006-0158-9 , URL =

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

  15. [15]

    Computational Geometry , VOLUME =

    Aichholzer, Oswin and Eppstein, David and Hainzl, Eva-Maria , TITLE =. Computational Geometry , VOLUME =. 2023 , DOI =

    2023

  16. [16]

    2018 , publisher=

    Forbidden configurations in discrete geometry , author=. 2018 , publisher=

    2018

  17. [17]

    1917 , publisher=

    Amusements in mathematics , author=. 1917 , publisher=

    1917

  18. [18]

    Ovals in a finite projective plane , volume =

    Segre, Beniamino , journal =. Ovals in a finite projective plane , volume =

  19. [19]

    Curve razionali normali e

    Segre, Beniamino , journal =. Curve razionali normali e

  20. [20]

    Mathematical theory of the symmetrical factorial design , author=. Sankhy. 1947 , publisher=

    1947

  21. [21]

    Towards mechanized mathematical assistants , pages=

    The on-line encyclopedia of integer sequences , author=. Towards mechanized mathematical assistants , pages=. 2007 , publisher=

    2007

  22. [22]

    Brass, Peter and Moser, William O. J. and Pach, János. Lattice Point Problems. Research Problems in Discrete Geometry. 2005. doi:10.1007/0-387-29929-7_11

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

  23. [23]

    1998 , publisher=

    Flammenkamp, Achim , journal=. 1998 , publisher=

    1998

  24. [24]

    Journal of Combinatorial Theory, Series A , volume=

    Update on the no-three-in-line problem , author=. Journal of Combinatorial Theory, Series A , volume=. 1979 , publisher=

    1979

  25. [25]

    Journal of Combinatorial Theory, Series A , volume=

    Some advances in the no-three-in-line problem , author=. Journal of Combinatorial Theory, Series A , volume=. 1975 , publisher=

    1975

  26. [26]

    No-Three-in-Line-in-3

    P. No-Three-in-Line-in-3. Algorithmica , volume=

  27. [27]

    Finite Fields and Their Applications , volume=

    Bounds on (n, r) -arcs and their application to linear codes , author=. Finite Fields and Their Applications , volume=. 2005 , publisher=

    2005

  28. [28]

    EMS Surveys in Mathematical Sciences , volume=

    Arcs in finite projective spaces , author=. EMS Surveys in Mathematical Sciences , volume=

  29. [29]

    Combinatorica , volume=

    Small Complete Arcs in Projective Planes , author=. Combinatorica , volume=

  30. [30]

    and Wood, David R

    Payne, Michael S. and Wood, David R. , journal =. On the general position subset selection problem , volume =

  31. [31]

    Mathematical games: combinatorial problems, some old, some new and all newly attacked by computer , volume =

    Gardner, Martin , journal =. Mathematical games: combinatorial problems, some old, some new and all newly attacked by computer , volume =

  32. [32]

    , journal =

    Wood, David R. , journal =. Grid drawings of

  33. [33]

    and Holton, Derek A

    Adena, Michael A. and Holton, Derek A. and Kelly, Patrick A. , booktitle =. Some thoughts on the no-three-in-line problem , year =

  34. [34]

    , howpublished =

    OEIS Foundation Inc. , howpublished =. The

  35. [35]

    Advances in Mathematics , volume=

    Sandwiching random graphs: universality between random graph models , author=. Advances in Mathematics , volume=. 2004 , publisher=

    2004

  36. [36]

    Combinatorics, Probability and Computing , volume=

    Sandwiching biregular random graphs , author=. Combinatorics, Probability and Computing , volume=. 2023 , publisher=

    2023

  37. [37]

    Baker, R. C. and Harman, G. and Pintz, J. , journal =. The difference between consecutive primes

  38. [38]

    Gao, Pu and Isaev, Mikhail and McKay, Brendan , journal=. Kim-

  39. [39]

    International Workshop on Randomization and Approximation Techniques in Computer Science , pages=

    Constructive proofs of concentration bounds , author=. International Workshop on Randomization and Approximation Techniques in Computer Science , pages=. 2010 , organization=

    2010

  40. [40]

    2023 , publisher=

    Random graphs and networks: a first course , author=. 2023 , publisher=

    2023

  41. [41]

    SIAM Journal on Computing , volume=

    Randomized distributed edge coloring via an extension of the Chernoff--Hoeffding bounds , author=. SIAM Journal on Computing , volume=. 1997 , publisher=

    1997

  42. [42]

    Journal of Graph Theory , volume=

    Perfect matchings in random subgraphs of regular bipartite graphs , author=. Journal of Graph Theory , volume=. 2021 , publisher=

    2021

  43. [43]

    European Journal of Combinatorics , volume=

    The extensible No-Three-In-Line problem , author=. European Journal of Combinatorics , volume=. 2023 , publisher=

    2023

  44. [44]

    manuscript , url=

    100 open problems , author=. manuscript , url=

  45. [45]

    2005 , publisher=

    Research problems in discrete geometry , author=. 2005 , publisher=

    2005

  46. [46]

    The American Mathematical Monthly , volume=

    Martin Gardner's minimum no-3-in-a-line problem , author=. The American Mathematical Monthly , volume=. 2014 , publisher=

    2014

  47. [47]

    arXiv e-prints , pages=

    Repeatedly applying the Combinatorial Nullstellensatz for Zero-sum Grids to Martin Gardner's minimum no-3-in-a-line problem , author=. arXiv e-prints , pages=

  48. [48]

    preprint , year=

    Extensions of the no-three-in-line problem , author=. preprint , year=

  49. [49]

    Combinatorica , volume=

    Maximal arcs in Desarguesian planes of odd order do not exist , author=. Combinatorica , volume=. 1997 , publisher=

    1997

  50. [50]

    Journal of Combinatorial Theory , volume=

    Some maximal arcs in finite projective planes , author=. Journal of Combinatorial Theory , volume=. 1969 , publisher=

    1969

  51. [51]

    , publisher=

    Pu Gao , journal=. , publisher=

  52. [52]

    No l Grid-Points in Spaces of Small Dimension

    Lefmann, Hanno. No l Grid-Points in Spaces of Small Dimension. Algorithmic Aspects in Information and Management. 2008

    2008

  53. [53]

    Random Structures & Algorithms , volume=

    Asymptotic enumeration of digraphs and bipartite graphs by degree sequence , author=. Random Structures & Algorithms , volume=. 2023 , publisher=

    2023

  54. [54]

    Advances in Mathematics , volume=

    On the number of matrices and a random matrix with prescribed row and column sums and 0--1 entries , author=. Advances in Mathematics , volume=. 2010 , publisher=

    2010

  55. [55]

    Maximal independent subsets in

    F. Maximal independent subsets in. SIAM Journal on Discrete Mathematics , volume=. 1991 , publisher=

    1991

  56. [56]

    Random Structures & Algorithms , volume=

    Random dense bipartite graphs and directed graphs with specified degrees , author=. Random Structures & Algorithms , volume=. 2009 , publisher=

    2009

  57. [57]

    Proceedings of the International Congress of Mathematicians 2010 , pages=

    Subgraphs of random graphs with specified degrees , author=. Proceedings of the International Congress of Mathematicians 2010 , pages=. 2010 , organization=

    2010

  58. [58]

    ACM Transactions on Algorithms (TALG) , volume=

    Perfect matchings via uniform sampling in regular bipartite graphs , author=. ACM Transactions on Algorithms (TALG) , volume=. 2010 , publisher=

    2010

  59. [59]

    Random Structures & Algorithms , volume=

    Complex martingales and asymptotic enumeration , author=. Random Structures & Algorithms , volume=. 2018 , publisher=

    2018

  60. [60]

    A collection of open problems in celebration of

    Rahil Baber and Natalie Behague and Asier Calbet and David Ellis and Joshua Erde and Ron Gray and Maria-Romina Ivan and Barnabás Janzer and Robert Johnson and Luka Milićević and John Talbot and Ta Sheng Tan and Belinda Wickes , year=. A collection of open problems in celebration of. 2310.18163 , archivePrefix=

    arXiv

  61. [61]

    arXiv preprint arXiv:2510.17743 , year=

    No- (k+ 1) -in-line problem for large constant k , author=. arXiv preprint arXiv:2510.17743 , year=

    arXiv

  62. [62]

    1900 , howpublished =

    Dudeney, Henry , title =. 1900 , howpublished =

    1900

  63. [63]

    A272651: The no-3-in-line problem , howpublished =

  64. [64]

    2025 , journal =

    Extensible no- (k(n)+1) -in-line when k(n)=cn^ , author=. 2025 , journal =

    2025

  65. [65]

    Extensible no- (k(n)+1) -in-line when k(n)=cn , author=

  66. [66]

    arXiv preprint arXiv:2605.07000 , year=

    A note on the extensible no-three-in-line problem , author=. arXiv preprint arXiv:2605.07000 , year=

    Pith/arXiv arXiv