{"id":"47c0112d-268e-45fc-a441-422285392f69","arxiv_id":"2508.07632","paper_version":2,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"For sufficiently large n, the no-(k+1)-in-line number satisfies (1-2/k)kn <= f_k(n) <= kn for even k and (1-3/k)kn <= f_k(n) <= kn for odd k, asymptotically tight as k grows.","lead":"This paper proves new lower bounds on how many points can be chosen from a large n by n grid without any k+1 points lying on one line. The authors obtain nearly the maximum possible number for large k and improve earlier guarantees for small k.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Union bound over ~n^3 lines is the load-bearing step; abstract gives no probability estimate, so 'every k with n large enough' is unsubstantiated.","rationale":"The reader's verdict is UNVERDICTED due to lack of full text, and my stress-test does not change that. I identified the same cluster of concerns: the abstract omits the probability estimate and the threshold n0(k). I narrowed the load-bearing issue to the union bound over the Θ(n^3) lines: for the claimed 'every k with n large enough' to hold, the per-line failure probability must decay faster than n^{-3}. The abstract gives no indication of this, and there are natural constructions (unions of polynomial graphs) where the per-line intersection count does not decay with n for fixed k. This is a concrete correctness risk, not just a complaint about exposition. I did not find an internal contradiction in the announced bounds; the statement is plausible and the small-k cases (e.g., k=4) have simple supporting constructions. But without the proof's probability estimates, the central claim cannot be accepted. My recommended verdict remains UNVERDICTED, hence UNCHANGED.","tokens_in":765,"tokens_out":23594,"duration_ms":293259,"concrete_test":"Obtain the full proof and locate the lemma that bounds Pr(|ℓ ∩ S| ≥ k+1) for a fixed line ℓ. Compute the dominant asymptotic in n: if the probability is O(n^{-4}) or smaller, the union bound over Θ(n^3) lines succeeds; if it is only O(1/k), O(1/n), or e^{-Ω(k)} with k fixed, then as n→∞ the probability that some line is bad goes to 1, invalidating the claim for every k. If no such probability lemma exists, the probabilistic construction is incomplete.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that f_k(n) ≥ (1−2/k)kn for every even k (and the odd analogue) requires a random construction whose success probability is positive for each fixed k and all n ≥ n0(k). Any line in the n×n grid can contain at most k points; there are Θ(n^3) lines determined by grid pairs. For the union bound to succeed, the probability that a fixed line contains k+1 selected points must be ≪ n^{-3}. The abstract states no such bound. If the construction is a union of k random polynomial graphs of degree d, then for a fixed line the intersection count is at most kd; forcing kd≤k would require d=1, which produces full lines and immediate violations. Thus the construction must rely on randomness to suppress the maximum intersection count below k for all lines simultaneously. Whether this suppression can be achieved for constant k and n→∞ is exactly the unverified point. Without the probability estimate and a valid union bound, the theorem is not established.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":1023,"tokens_out":7053,"duration_ms":83279,"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":[{"comment":"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.","section":"Abstract (main theorem)"},{"comment":"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.","section":"Abstract ('randomised algebraic constructions')"}],"minor_comments":[{"comment":"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.","section":"Abstract (quantifiers)"},{"comment":"The title uses 'no-$(k+1)$-in-line' while the abstract uses 'no-(k+1)-in line'; the hyphenation should be made consistent.","section":"Abstract (notation)"},{"comment":"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.","section":"Abstract (references)"}],"recommendation":"uncertain","confidential_remarks":"This review is based solely on the abstract; the full manuscript was not available. The claims are plausible and could be a significant contribution, but correctness cannot be judged without the proof. I recommend obtaining the full text before making a decision. If the proof contains the standard union-bound estimate and the construction is properly specified, the paper may well be publishable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick note on arXiv:2508.07632. This is an abstract-only posting, so my verdict is necessarily provisional. If the lower bounds are correct, they replace Lefmann's Omega(kn) with explicit (1-2/k)kn and (1-3/k)kn, which is a real improvement and asymptotically tight as k grows. The small-k improvements for k<23 are a nice extra. The statements are precise and the paper appears to engage honestly with the prior bound.\n\nWhat I cannot do from the abstract is check the construction. The load-bearing step is clearly a probabilistic estimate: there are ~n^3 lines in the grid, so for a union bound to work, the probability that any fixed line contains k+1 selected points has to be negligible compared to n^{-3}. The abstract gives no hint of that estimate, and the phrase 'randomised algebraic constructions' could mean many things. If the construction is a union of k graphs of random polynomials of degree d, then on a fixed line the intersection count is at most kd, so you'd need d=1 to avoid immediate violations, which wouldn't work. So the entire theorem rests on a probability estimate that isn't stated. That doesn't mean it's wrong—just that I can't score soundness at all.\n\nThe self-citation to the authors' earlier upper bound is fine; this lower bound appears independent of Lefmann's result. No fitted parameters are visible. The abstract is honest about the limits: 'n is large enough' but no threshold n0(k) is given, and 'constant values of k when k<23' is left vague. Those are minor omissions for an abstract.\n\nBottom line: this is a paper for people working in extremal combinatorics. If the proof is correct, it's a solid subfield result. The lack of a full text makes this impossible to verify, but the claim is specific and plausible. I'd send it to referees and ask them to focus on the probability estimate behind the union bound. That's the make-or-break point.","headline":"Plausible and potentially substantial lower-bound improvement, but the abstract hides the key probability estimate, so soundness is unverifiable.","tokens_in":1468,"tokens_out":2467,"would_cite":false,"duration_ms":28096,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05D40","05B30"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["no-(k+1)-in-line problem","lattice points","collinear points","randomised algebraic constructions","probabilistic method","extremal combinatorics","finite fields"],"falsifier":"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.","tokens_in":721,"feed_emoji":"📐","tokens_out":11991,"duration_ms":137903,"temperature":0.7,"pith_summary":"The paper studies the no-$(k+1)$-in-line problem: how many points of an $n \\times n$ lattice can be chosen so that no $k+1$ of them lie on a common line? The trivial upper bound is $kn$ points, but no construction came close for general $k$; the best known was only an unspecified constant times $kn$. The paper proves that for every even $k$, at least $(1-2/k)kn$ points can be chosen, and for every odd $k$, at least $(1-3/k)kn$ points, provided $n$ is large enough. Since the gaps $2/k$ and $3/k$ shrink to zero as $k$ grows, this shows the upper bound is asymptotically attainable. The construction is randomised and algebraic, and it also yields stronger constants for each fixed $k<23$.","feed_headline":"For even k, (1-2/k)kn points avoid k+1 collinear","feed_subtitle":"Lattice bound nearly hits the trivial maximum kn for every large n; odd k gives (1-3/k)kn.","key_machinery":"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.","core_discovery":"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$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[],"fun_headline_variants":["Even k: (1-2/k)kn points avoid k+1 collinear","Odd k: (1-3/k)kn points avoid k+1 collinear","Randomised algebraic constructions yield near-max lower bounds","Lattice no-(k+1)-in-line bounds nearly hit the trivial max","For large n, even k hits (1-2/k)kn, odd k gets (1-3/k)kn"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Even k: (1-2/k)kn points avoid k+1 collinear","Odd k: (1-3/k)kn points avoid k+1 collinear","Randomised algebraic constructions yield near-max lower bounds","Lattice no-(k+1)-in-line bounds nearly hit the trivial max","For large n, even k hits (1-2/k)kn, odd k gets (1-3/k)kn"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001247,"raw_usage":{"total_tokens":4982,"prompt_tokens":808,"completion_tokens":4174,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":552,"completion_tokens_details":{"reasoning_tokens":4064}},"tokens_in":552,"tokens_out":4174,"duration_ms":33671,"temperature":1.0,"reasoning_tokens":4064,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T21:57:09.726481+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}