{"id":"c812b446-b94d-4100-a8a3-5a05e9eec1a9","arxiv_id":"2607.05255","paper_version":1,"verdict":"ACCEPT","confidence":"UNKNOWN","novelty_score":8.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":2,"one_line_summary":"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.","lead":"This paper proves that for k≥3, you can place exactly kn points on an n×n grid with no k+1 collinear, matching the trivial upper bound. It resolves a generalization of the classic no-three-in-line problem for all k≥3.","discovery_kind":"unclear","skeptic_critique":{"model":"glm-5.2","headline":"No significant objection identified. The completion procedure analysis (Section 4) is intricate but each step — spreadness of S_half (Lemma 4.16), the transfer argument (Lemma 4.17), and the case analysis in Proposition 4.10 — holds up under careful scrutiny. The k≥3 requirement is cleanly motivated","rationale":"The reader correctly identified Proposition 4.10 and the completion procedure as the weakest point. After careful examination, I find no gap in the argument. The key steps are: (1) Lemma 4.8 establishes that S_init is spread and has ≥2ρn ε-absorbers for every point, via an inclusion-exclusion argument whose lower bound relies on the convergence of Σ 1/m^{k-1} for k≥3 — this is the fundamental reason the result requires k≥3. (2) Lemma 4.16 establishes spreadness of S_half by a sequential conditioning argument. (3) Fact 2.3 combines the spreadness of S_init and S_half. (4) Lemma 4.12 uses a moment method to bound |T_L(S_init ∪ S_half)|. (5) Lemma 4.17 transfers this bound to S_init ∪ S_comp using the fact that S_half ⊆ S_comp and each triple survives with probability ≥1/8. (6) Proposition 4.10 combines these via a case analysis where the k≥3 assumption is used crucially in Case 3b. Each step checks out. The parameter hierarchy 1/k ≫ ρ ≫ α ≫ ε ≫ 1/n ensures all error terms are dominated. The paper also has independent support from the earlier result [16] covering k ≥ 10^{37}, meaning only bounded k needs the new argument. No formal verification is provided, but the argument is sufficiently detailed for expert verification. The secondary results (Theorems 1.4 and 1.5) use similar but simpler techniques and also appear correct.","tokens_in":30776,"tokens_out":11566,"duration_ms":309515,"concrete_test":"Independently re-derive the bound in Lemma 4.12 by computing E[|T_L(S)|^m] for a concrete small case (e.g., k=3, n=1000, α=0.01, c=2k/n) via Monte Carlo simulation: sample (c/n, 3m)-spread random sets S and verify that |T_L(S)| = O(c³αn) with the predicted failure probability exp(-m). If the empirical tail is substantially heavier than exp(-m), the moment bound in Lemma 4.12 — and hence Lemma 4.17 and Proposition 4.10 — would need re-examination.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No significant objection identified. The reader correctly identifies Proposition 4.10 and the completion procedure as the most intricate part of the proof. Having examined each step carefully, the argument appears sound. Specifically: (1) Lemma 4.16's spreadness bound for S_half is correct — at each step t < τ, the absorber is chosen uniformly from ≥ρn options, and at most 2k share a row/column with any given point, giving probability ≤ 2k/(ρn) per point, and the sequential conditioning is handled properly. (2) The transfer argument in Lemma 4.17 is correct: since S_half ⊆ S_comp, we have |T_L(S_init ∪ S_half)| ≤ |T_L(S_init ∪ S_comp)|, and the expectation bound E[|T_L(S_init ∪ S_half)| | S_init, S_comp] ≥ |T_L(S_init ∪ S_comp)|/8 (each triple survives with probability ≥ 1/8) combined with the upper bound on X gives P[X ≥ N/16] ≥ 1/16 via total expectation. (3) The case analysis in Proposition 4.10 is correct: the crucial Case 3b works because the line L through (x,r) or (c,y) contains at least k points of S_{t-1} (not counting (x,r)/(c,y) itself, which may not be in S_{t-1}), and since L is non-trivial it intersects the row/column of (c,r) at exactly one point, leaving k ≥ 3 points in [n]² ∖ L to form a triple in T_L. This is exactly why k ≥ 3 is required — for k = 2 only 2 points would remain, insufficient for a triple. The parameter hierarchy (2) ensures all error terms are dominated by ρn. The approximate construction (Section 3) and the circle result (Section 6) are straightforward applications of Lemma 2.2.","agreement_with_reader":"agree"},"referee_report":{"model":"glm-5.2","summary":"This paper resolves the no-$(k+1)$-in-line problem for all $k geq 3$ and sufficiently large $n$, proving that the trivial upper bound $f_k(n) le kn$ is tight. The proof has two stages: an approximate construction of size $kn - o(n)$ via pseudorandom hypergraph matchings (using the Ehard–Glock–Joos theorem), followed by a randomized switching procedure that completes the construction to exactly $kn$ points. The key insight is that for $k ge 3$, the contribution of $varepsilon$-light lines is controlled by a convergent series, making the problem dominated by finitely many heavy directions. The paper also proves a higher-dimensional analogue (Theorem 1.4) and improves the lower bound for the no-four-on-a-circle problem to $2n - o(n)$ (Theorem 1.5).","tokens_in":31126,"tokens_out":1859,"duration_ms":442758,"significance":"The main result (Theorem 1.1) settles a natural generalization of Dudeney's no-three-in-line problem for all $k ge 3$, showing the trivial upper bound is achieved. This is a substantial advance: prior work of Kovács–Nagy–Szabó gave $f_k(n) ge (k-2-o(1))n$, and the result of Grebennikov–Kwan covered only $k ge 10^{37}$. The method is non-algebraic, contrasting with all previous constructions for small $k$. The completion procedure (Section 4), building on ideas of Simkin and Luria for the $n$-queens problem, is technically intricate and appears to be the first application of such switching-based absorption to the no-$(k+1)$-in-line setting. The extension to the no-four-on-a-circle problem (improving from $n - o(n)$ to $2n - o(n)$) and the higher-dimensional result add further value. The proof of Lemma 2.2 in Appendix A, which extends the Ehard–Glock–Joos pseudorandom matching theorem to include an explicit spreadness guarantee, is a useful standalone contribution.","major_comments":[{"comment":"Lemma 4.17 (the transfer argument from $S_{init} cup S_{half}$ to $S_{init} cup S_{comp}$): The proof states that each point $p_1, p_2, p_3$ of a triple in $T_L(S_{init} cup S_{comp})$ is included in $S_{init} cup S_{half}$ with probability at least $1/2$ independently, conditional on $S_{init}$ and $S_{comp}$ (and the absorber choices). However, the independence claim needs scrutiny: the absorber choices $(x_t, y_t)$ are determined by $S_{init}$ and the algorithm's internal randomness, and $S_{half}$ further randomizes which of the two added points is selected. The statement that each triple point survives in $S_{half}$ with probability $ge 1/2$ independently relies on the triple's three points belonging to three distinct switching steps. If two of the three points come from the same step $t$ (i.e., both $(x_t, r_t)$ and $(c_t, y_t)$ are in the same triple), then their inclusion in $S_{","section":null}],"minor_comments":[{"comment":"Section 1.3, paragraph on approximate constructions: the heuristic computation in Remark 1.7 uses $sum_{m=lfloor 1/varepsilon rfloor+1}^{n} 1/m^{k-1}$, but the text says 'this sum is about $log n$' for $k=2$. For $k=2$ the sum is $sum 1/m$, which is indeed $Theta(log n)$, but the statement 'independently of $varepsilon$' is slightly imprecise since the lower limit depends on $varepsilon$; the leading term is $log n - log(1/varepsilon) = log(nvarepsilon)$. Consider clarifying.","section":null},{"comment":"Definition 4.1, condition A2: the line through $(x,r)$ and $(c,y)$ is required to be 'irrelevant' (i.e., $|d|_infty ge n/3$). The term 'irrelevant' is defined earlier in Section 4 but could benefit from a brief reminder at the point of use in Definition 4.1, since it is load-bearing for the absorber definition.","section":null},{"comment":"Lemma 4.2: the constant $0.05$ is used as a lower bound for $|I(c,r)|/n^2$. The proof uses the Minkowski-type result giving $6/pi^2 cdot n^2/12 + o(n^2) approx 0.05066 n^2$. The margin is thin; it would help to state the numerical value $6/(12pi^2) approx 0.0507$ explicitly so the reader can verify $> 0.05$.","section":null},{"comment":"Section 5, proof of Theorem 1.4: the codegree bound $Delta_2(H_varepsilon^{(k)}) le n^{s-1}$ is stated but the justification ('since an intersection of two primitive rank-$s$ lattices has rank at most $s-1$') could be elaborated slightly, as the bound on the number of common edges (not just vertices) requires a bit more care.","section":null},{"comment":"Reference [7] (Conlon, 'Private communication') and [17] (Green, '100 open problems, Manuscript') lack precise bibliographic details. If possible, provide more complete citations or note the status.","section":null},{"comment":"Appendix B: the table of numerical data is a nice addition. The claim that $f_{IT}(n) - f_{circ}(n) = o(n)$ is 'plausible' is reasonable, but the convergence rate of Lemma 6.1 is noted as 'very slow' without quantification. A brief remark on the known rate (the exponent $4+18/29$) would contextualize this.","section":null},{"comment":"Typo in Section 4.4, proof of Proposition 4.10, Case 3b: 'Since $k ge 3$ and $S_{t-1} subseteq S_{init} cup S_{comp}$, the line $L$ must contain a triple of points in $T_{L_1}(S_{init} cup S_{comp})$ or $T_{L_2}(S_{init} cup S_{comp})$.' This is correct but the logic could be stated more explicitly: $L$ has $ge k ge 3$ points of $S_{t-1}$, at most one of which is in the row/column of $(c,r)$, leaving $ge k-1 ge 2$ points; but since $k ge 3$ and the triple requires 3 points, one should clarify that $ge 3$ points remain outside $L_1 cup L_2$ (or at least that a triple can be found).","section":null},{"comment":"Notation: the parameter hierarchy (2) uses $a gg b$ to mean $b$ is sufficiently small in terms of $a$, which is non-standard (usually $a gg b$ means $a$ is much larger than $b$). The convention is stated but could be confused with the standard usage; consider a different symbol such as $succ$.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The paper is a strong result by a well-known group of authors. The main technical risk is in Lemma 4.17's transfer argument, as flagged in the major comments. I believe the issue is fixable (the condition A2 in Definition 4.1 is designed precisely to prevent two points from the same switching step from lying on the same non-irrelevant line, so the independence should hold), but the current writeup does not make this explicit enough. The higher-dimensional result (Theorem 1.4) does not achieve the exact bound $kn^{d-s}$ (only $(1-eta)kn^{d-s}$), which is honestly stated; a completion procedure for higher dimensions is noted as an open problem in Remark 1.9. The AlphaEvolve experiments in Appendix B are a nice touch but not load-bearing for any result."},"author_rebuttal":null,"desk_editor":{"model":"glm-5.2","letter":"This paper resolves the no-(k+1)-in-line problem for all k≥3 and sufficiently large n, proving f_k(n)=kn. That is the trivial upper bound, so the answer is tight. The k=2 case (Dudeney's original) remains open, as the authors are careful to note. This is a significant result and the proof introduces a genuinely new method for this problem family. The key insight is clean: for k≥3, the sum over light line directions converges (it's a tail of a convergent p-series with p=k-1≥2), so the problem is dominated by a constant number of heavy directions. This lets the authors reduce to an almost-perfect matching in a bounded-uniformity hypergraph, handle heavy lines via the Ehard-Glock-Joos pseudorandom matching theorem, and clean up light lines by deletion. The approximate construction (Section 3) is short and well-motivated. The completion procedure (Section 4) is the harder part: they use a randomized switching argument (building on Simkin-Luria's n-queens work) to go from kn-o(n) to exactly kn. The absorber counting via inclusion-exclusion (Lemma 4.8) and the spreadness transfer (Lemma 4.17) are intricate but each step checks out. The stress-test note's verification of Case 3b in Proposition 4.10 is correct: the k≥3 requirement enters exactly because a non-trivial line through (x,r) or (c,y) intersects the row/column of (c,r) at one point, leaving k≥3 points off L to form a triple — for k=2 you'd only have 2, which is insufficient. The parameter hierarchy (1/k≫ρ≫α≫ε≫1/n) ensures all error terms are dominated by ρn. The higher-dimensional result (Theorem 1.4) and the no-four-on-a-circle improvement (Theorem 1.5, from n-o(n) to 2n-o(n)) are straightforward applications of the same framework. The circle result uses a nice two-stage matching construction exploiting Huxley-Konyagin's estimate that most cyclic quadrilaterals are isosceles trapezia. No soft spots worth flagging at the level that would affect the main result. The completion procedure is the most fragile part of the argument, but the coupling and moment arguments are sound. The paper is self-contained apart from the external matching theorem. This is for combinatorialists and probabilistic combinatorics readers. It deserves a serious referee who can verify the inclusion-exclusion and spreadness transfer in detail.","headline":"Resolves the no-(k+1)-in-line problem for all k≥3: f_k(n)=kn. New non-algebraic method via pseudorandom matchings + randomized switching completion. Sound, significant, deserves a serious referee.","tokens_in":31926,"tokens_out":636,"would_cite":true,"duration_ms":73216,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":null,"created_at":"2026-07-07T21:07:47.841922+00:00","model_set":{"reader":"glm-5.2"},"falsifier":null,"supporting_citations":[],"review_version":1}