REVIEW 2 major objections 3 minor 1 cited by
Randomised algebraic constructions for the no-$(k+1)$-in-line problem
T0 review · 2 major / 3 minor · reviewed 2026-08-05 · deepseek-v4-flash
Pith's one-line read The paper proves that for every even k, (1-2/k)kn lattice points can be selected with no k+1 collinear, and for odd k, (1-3/k)kn, whenever n is large enough.
desk verdict Plausible and potentially substantial lower-bound improvement, but the abstract hides the key probability estimate, so soundness is unverifiable. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The proof uses a randomised algebraic construction: points are chosen from a random algebraic object over a finite field, which is then embedded into the integer lattice so that any line intersects the selected set in a controlled number of points. The randomness is used to show that, with positive probability, no line contains $k+1$ selected points; the constants $2/k$ and $3/k$ arise from the probability estimates governing this construction.
What would settle it
For an even $k$ such as $k=6$, establish an upper bound $f_k(n) < (1-2/k)kn$ for some arbitrarily large $n$, or show that the construction's expected number of bad lines is at least 1 for all sufficiently large $n$; either would directly contradict the claimed lower bound.
Extended reading notes
Core claim
The central claim is that for each fixed $k$, with $n$ sufficiently large, the maximum size $f_k(n)$ of a subset of $[n]\times[n]$ with no $k+1$ collinear points satisfies $\left(1-\tfrac{2}{k}\right)kn \le f_k(n) \le kn$ when $k$ is even, and $\left(1-\tfrac{3}{k}\right)kn \le f_k(n) \le kn$ when $k$ is odd. In particular, $\lim_{k\to\infty} f_k(n)/(kn)=1$ for every such $n$, so the trivial upper bound is asymptotically tight. The paper also states improved lower bounds for constant values of $k$ below $23$.
Load-bearing premise
The proof assumes that for every even or odd $k$, the randomised construction succeeds with positive probability when $n$ is large enough; if that probability estimate fails for some $k$, the lower bound collapses.
Editorial extensions
If this is right
- For every fixed $k$, the lower bound is within a factor of $1 - O(1/k)$ of the trivial upper bound $kn$, so $f_k(n)$ is asymptotically $kn/(1+o(1))$ as $k\to\infty$.
- The result replaces the previous $\Omega(kn)$ estimate with explicit constants, giving the exact asymptotic order of $f_k(n)$ for all $k$.
- For constant $k$ below $23$, the paper provides stronger lower bounds, improving the best known values in those cases.
- The random algebraic method may extend to other extremal problems on lattices with collinearity constraints.
Reading between the lines
- The threshold $n_0(k)$ is left unspecified; a natural next step is to determine how large $n$ must be, and the method might work with $n$ merely polynomial in $k$ rather than extremely large.
- The constants $2/k$ and $3/k$ are likely not optimal; a finer analysis of the probability estimates could push them closer to $1/k$ for both parities.
- The odd/even asymmetry (3/k vs 2/k) may be an artifact of the construction, and a symmetric variant might remove it and approach $kn$ faster.
- If the construction works over any finite field, it might transfer to point sets in other finite abelian groups, connecting to cap-set-type problems.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the no-(k+1)-in-line problem: the maximum size f_k(n) of a subset of the n×n grid containing no k+1 collinear points. The abstract claims that, for all sufficiently large n, every even k satisfies (1−2/k)kn ≤ f_k(n) ≤ kn and every odd k satisfies (1−3/k)kn ≤ f_k(n) ≤ kn, so that the bounds are asymptotically tight as k→∞. It also claims further improvements for constant k with k<23, and states that these bounds come from randomised algebraic constructions. Previously, only f_k(n)=Ω(kn) was known due to Lefmann, so the abstract promises a substantial strengthening. The full text was not available for this review; only the abstract was supplied.
Significance. If the stated bounds are correct, the paper would replace Lefmann's qualitative Ω(kn) lower bound with explicit, asymptotically tight constants that approach the trivial upper bound kn as k grows. This would be a significant advance for a problem that has been open for over a century in the classical k=2 case. The use of randomised algebraic constructions is a plausible and potentially fruitful method. The abstract’s specificity about the constants is a positive signal, and no definitional circularity or fitted parameters are apparent. However, because the proof, lemmas, and probability estimates are not visible in the available text, the correctness of the central claim cannot currently be checked. Credit should be given for the clarity of the main statement and the explicit comparison to prior work, but verification requires the full manuscript.
major comments (2)
- [Abstract (main theorem)] The central claim that (1−2/k)kn ≤ f_k(n) ≤ kn for every even k (and the odd analogue) is stated without any proof in the available text. The load-bearing step must be a probabilistic analysis of the random construction showing that, with positive probability, no lattice line contains k+1 selected points. This requires a union bound over all relevant lattice lines, whose number is polynomial in n; the per-line failure probability must be o(n^{-c}) for the appropriate exponent c. The abstract gives no such probability estimate, nor does it specify the construction’s parameters, the range of k, or the threshold n_0(k). Without these, the theorem is unverified from the supplied material.
- [Abstract ('randomised algebraic constructions')] The construction is not described. If the selected set is built from k polynomial graphs of degree d, then a fixed line intersects each graph in at most d points, so k+1 collinear points can arise only through intersections across the graphs; the success of the construction hinges on controlling the maximum number of selected points on any line. The abstract does not state d, the choice of random coefficients, or how the algebraic structure prevents large collinear sets. The claimed improvements for k<23 are likewise stated without the actual improved lower bounds, making them impossible to assess.
minor comments (3)
- [Abstract (quantifiers)] The phrase 'for every even k … provided that n is large enough' is ambiguous: does it mean for each fixed k there exists n_0(k), or is there a relationship between k and n (e.g., n ≫ k)? Since the bound is asymptotically tight as k→∞, the intended regime should be stated explicitly.
- [Abstract (notation)] The title uses 'no-$(k+1)$-in-line' while the abstract uses 'no-(k+1)-in line'; the hyphenation should be made consistent.
- [Abstract (references)] The reference to Kovács, Nagy and Szabó is mentioned without a citation; if this is the published version, the full citation should be included in the abstract or introduction.
Circularity Check
No circular derivation apparent; only a background self-citation, not load-bearing.
full rationale
Based on the available abstract, the announced lower bounds are attributed to 'randomised algebraic constructions' and are contrasted with Lefmann's earlier Omega(kn) bound. No fitted parameter is relabelled as a prediction, and no quantity is defined in terms of the target. The only self-reference is the authors' prior upper-bound result ('as Kovacs, Nagy and Szabo proved that the upper bound kn can be attained, provided that k>C sqrt(n log n)'), which is presented as context and is not used to derive the new lower bounds. The skeptical union-bound objection concerns whether the random construction succeeds with positive probability for each fixed k and all sufficiently large n; that is a correctness/rigor question, not circularity. Since the full text is not available for equation-level inspection, no additional circular steps can be identified. The minor background self-citation keeps the score just above zero, but the central claim appears independent of its inputs.
Assumptions & free parameters
assumptions (3)
- standard math f_k(n) <= kn, the trivial row-count upper bound
- ad hoc to paper The randomised algebraic construction succeeds with positive probability for all sufficiently large n
- domain assumption The theorem is asymptotic in n, with the threshold n0(k) unspecified
Cite this review
Pith. "Pith review of Randomised algebraic constructions for the no-$(k+1)$-in-line problem." pith.science (2026). https://pith.science/paper/5HEQS23L
@misc{pith2026250807632,
author = {Pith},
title = {Pith review of: Randomised algebraic constructions for the no-$(k+1)$-in-line problem},
year = {2026},
howpublished = {\url{https://pith.science/paper/5HEQS23L}},
note = {Machine review of arXiv:2508.07632}
}
abstract
The no-(k+1)-in line problem seeks the maximum number of points that can be selected from an $n \times n$ square lattice such that no $k+1$ of them are collinear. The problem was first posed more than $100$ years ago for the special case $k=2$ and has remained open ever since. The general problem was recently resolved in the case $k$ is not small compared to $n$, as Kov\'acs, Nagy and Szab\'o proved that the upper bound $kn$ can be attained, provided that $k>C\sqrt{n\log{n}}$ for an absolute constant $C$. In this paper, we show that $\left(1-\tfrac{2}{k}\right)kn \leq f_k(n)\leq kn$ and $\left(1-\tfrac{3}{k}\right)kn \leq f_k(n)\leq kn$ hold for every even $k$ and odd $k$, respectively, provided that $n$ is large enough. This is asymptotically tight as $k\to \infty$. Previously, only $f_k(n)=\Omega(kn)$ was known due to Lefmann. We present further improvements on the lower bounds for constant values of $k$ when $k<23$ holds. All these bounds are based on randomised algebraic constructions.
Forward citations
Cited by 1 Pith paper
-
No-$(k+1)$-in-line problem for $k \geqslant 3$
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.
Reviewed August 5, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.