pith. sign in

arxiv: 2605.07000 · v1 · submitted 2026-05-07 · 🧮 math.CO

A note on the extensible no-three-in-line problem

Anubhab Ghosal This is my paper

Pith reviewed 2026-05-11 01:08 UTC · model grok-4.3

classification 🧮 math.CO
keywords no-three-in-line problemextensible no-three-in-linecollinear triplesprobabilistic methodlower boundinteger latticediscrete geometry
0
0 comments X

The pith

A random subset of the integer lattice produces no-three-in-line sets of size Omega n over square root log n.

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

The paper establishes the existence of large subsets of the integer grid with no three points on a straight line. Using a probabilistic construction, it reaches a density of Omega n over square root log n inside any n by n square. This beats the prior lower bound by a factor of square root log n while the trivial upper bound of order n stays the same distance away. A reader would care because the result tightens the known range for the largest possible such sets and shows that randomness can push the construction limit further without needing an explicit pattern.

Core claim

The paper shows that there exists a set S subset Z^2 with no three collinear points such that the intersection of S with the n by n grid has size Omega n over square root log n for all sufficiently large n. The proof proceeds by exhibiting a random subset whose probability of containing a collinear triple is strictly less than one, which immediately implies the desired existence statement.

What carries the argument

A random subset of Z^2 chosen so that the probability of any three points being collinear falls below one, established by direct counting of lines and point triples.

If this is right

  • The best known lower bound on the size of an extensible no-three-in-line set improves by a square-root-log-n factor over the earlier result of Nagy, Nagy and Woodroofe.
  • The gap between this construction and the trivial upper bound of O n remains unchanged in asymptotic order.
  • Random methods suffice to produce collinear-free subsets larger than what was previously guaranteed by explicit constructions.
  • The same approach leaves open the possibility of removing the remaining log factor entirely by refining the probability estimates.

Where Pith is reading between the lines

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

  • Similar random-selection arguments could be tested on the no-four-in-line problem or on grids in higher dimensions to see whether the same density gain appears.
  • The result indicates that the log factor in earlier bounds was an artifact of the construction technique rather than an intrinsic limit of the problem.
  • If the probabilistic threshold can be pushed lower, it would connect this problem more closely to other extremal questions in discrete geometry where randomness closes small gaps.

Load-bearing premise

The probabilistic calculations must succeed in showing that some random subset avoids all collinear triples with positive probability.

What would settle it

A proof that every subset of the grid of density c n over square root log n must contain three collinear points for some constant c and large n would falsify the claim.

read the original abstract

We show the existence of a set $S\subset\mathbb{Z}^2$ avoiding collinear triples satisfying $|S\cap [n]^2|=\Omega(n/\sqrt{\log n})$ for sufficiently large $n$. This improves on the best-known lower bound on Erde's extensible no-three-in-line problem due to Nagy, Nagy and Woodroofe by $\sqrt{\log n}$, leaving the same gap to the trivial upper bound. Our construction is random.

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

1 major / 2 minor

Summary. The paper claims to prove, via a random construction, the existence of a single set S ⊆ ℤ² containing no three collinear points such that |S ∩ [n]²| = Ω(n / √(log n)) for all sufficiently large n. This improves the previous best lower bound for Erde's extensible no-three-in-line problem by a √(log n) factor while leaving the same gap to the trivial O(n) upper bound.

Significance. If the probabilistic argument is complete, the result is a modest but concrete advance in combinatorial geometry: it supplies a denser infinite no-three-in-line set than was previously known. The random method is the natural tool for such existence statements, and the paper explicitly credits the improvement over Nagy–Nagy–Woodroofe. The work is short and focused, which is appropriate for a note.

major comments (1)
  1. [the probabilistic construction] The random model on the infinite grid ℤ² is described only at a high level. It is not shown explicitly how the inclusion probabilities are chosen (or how the Lovász Local Lemma is applied) so that a single realization S simultaneously avoids three collinear points on every line in ℤ² and satisfies the stated lower bound on |S ∩ [n]²| for all large n. A fixed positive density would produce infinitely many points on every infinite line almost surely; the manuscript must therefore specify the measure and the uniform bounds over countably many lines.
minor comments (2)
  1. The abstract and introduction should state more explicitly that the claimed S is a single infinite set (rather than a family of finite sets, one for each n).
  2. A short sentence recalling the definition of the finite no-three-in-line problem would help readers situate the extensible variant.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive evaluation and for identifying a point where the exposition of the probabilistic construction can be strengthened. We address the major comment below and will revise the manuscript to incorporate the requested clarifications.

read point-by-point responses

  1. Referee: The random model on the infinite grid ℤ² is described only at a high level. It is not shown explicitly how the inclusion probabilities are chosen (or how the Lovász Local Lemma is applied) so that a single realization S simultaneously avoids three collinear points on every line in ℤ² and satisfies the stated lower bound on |S ∩ [n]²| for all large n. A fixed positive density would produce infinitely many points on every infinite line almost surely; the manuscript must therefore specify the measure and the uniform bounds over countably many lines.

    Authors: We agree that the current description of the random model is high-level and that an explicit account of the probabilities and the LLL application would strengthen the paper. In the revised manuscript we will define the probability measure in full detail, state the precise inclusion probability for each point of ℤ², introduce the bad events associated with each line, and supply the uniform estimates on their probabilities and dependency degrees that allow the Lovász Local Lemma to be applied simultaneously to the countable collection of lines. These additions will establish that there exists a single set S with no three collinear points whose intersection with [n]² meets the claimed lower bound for all sufficiently large n. revision: yes

Circularity Check

0 steps flagged

No circularity: direct probabilistic existence argument

full rationale

The paper presents a random construction of an infinite set S subset Z^2 with no three collinear points, achieving the stated density in finite grids for large n. The derivation relies on external probabilistic inequalities (e.g., union bounds or LLL-style estimates on bad events for lines) applied to the random model. No step defines a quantity in terms of the target density or renames a fitted parameter as a prediction. No self-citation is load-bearing for the central existence claim, and the argument does not reduce to its own inputs by construction. The finite-to-infinite transfer, if present, is a standard probabilistic-method step rather than a tautology.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof relies on the standard probabilistic method and basic counting arguments from combinatorics; no new entities or fitted parameters are introduced.

axioms (1)
  • standard math The probabilistic method proves existence when a random object satisfies the desired property with positive probability.
    Invoked implicitly to conclude existence from the random construction.

pith-pipeline@v0.9.0 · 5354 in / 1104 out tokens · 38184 ms · 2026-05-11T01:08:03.606406+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

10 extracted references · 10 canonical work pages

  1. [1]

    Peter Brass, William O. J. Moser, and J´ anos Pach,Research problems in discrete geometry, Problem Books in Mathematics, Springer, New York, 2005. MR 2163782

    work page 2005

  2. [2]

    Dudeney,Amusements in mathematics, Thomas Nelson and Sons, London, 1917

    Henry E. Dudeney,Amusements in mathematics, Thomas Nelson and Sons, London, 1917

    work page 1917

  3. [3]

    David Ellis and Robert Johnson (editors),A collection of open problems in celebration of Imre Leader’s 60th birthday, arXiv preprint arXiv:2310.18163 (2023)

    work page arXiv 2023

  4. [4]

    Anubhab Ghosal and Ritesh Goenka,On the extensible no-four-on-a-circle problem, in preparation

    work page

  5. [5]

    Anubhab Ghosal, Ritesh Goenka, and Peter Keevash,On subsets of lattice cubes avoiding affine and spherical degeneracies, arXiv preprint arXiv:2509.06935 (2025)

    work page arXiv 2025

  6. [6]

    Ben Green,100 open problems, Manuscript

    work page

  7. [7]

    Guy,Unsolved problems in number theory, Springer-Verlag, New York-Berlin, 1981

    Richard K. Guy,Unsolved problems in number theory, Springer-Verlag, New York-Berlin, 1981. MR 0656313

    work page 1981

  8. [8]

    Hall, Terence H

    Richard R. Hall, Terence H. Jackson, Anthony Sudbery, and Ken Wild,Some advances in the no-three-in-line problem, Journal of Combinatorial Theory, Series A18(1975), no. 3, 336–341

    work page 1975

  9. [9]

    D´ aniel T Nagy, Zolt´ an L´ or´ ant Nagy, and Russ Woodroofe,The extensible no-three-in-line problem, European Journal of Combinatorics114(2023), 103796

    work page 2023

  10. [10]

    Roth,On a problem of Heilbronn, Journal of the London Mathematical Society1(1951), no

    Klaus F. Roth,On a problem of Heilbronn, Journal of the London Mathematical Society1(1951), no. 3, 198–204. Mathematical Institute, University of Oxford, Oxford, UK OX2 6GG Email address:ghosal@maths.ox.ac.uk 5

    work page 1951