{"id":"8df6984a-ebc3-45cd-a495-5d4a9fe3fb02","arxiv_id":"2502.00176","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For k > C sqrt(n log n), the maximum size of a point set in an n by n grid with no k+1 collinear points is exactly k n.","lead":"The authors prove that in an n by n square grid, if the allowed number of points on a line is k and k is larger than about 15 times the square root of n log n, the maximum number of points you can place without k+1 on a line is exactly k n. This settles the no-(k+1)-in-line problem in a large, previously open range and showcases a random bi-uniform construction that may apply to other lattice extremal questions.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proof's load-bearing black box is Theorem 2.4: the claimed absolute constant K is derived from [16] with δ = 1/m, and the paper gives no evidence that the constants are uniform as δ → 0. If K depends on m, the C√(n log n) threshold in Theorem 1.2 may fail or need a larger C.","rationale":"The central claim f_k(n) = kn for k ≥ C√(n log n) rests on a probabilistic construction whose core probability estimate is Lemma 3.6. The upper bound, the explicit construction for k ≥ 2n/3, the (k, δ)-feasibility of R (Lemma 3.5), and the adjustment lemmas 3.12 and 3.13 are all internally consistent and check out. The only place where the argument depends on an unverifiable external input is Theorem 2.4, which supplies the matching-containment probability bound. The paper's proof of Theorem 2.4 is a compressed invocation of [16, Theorem 5.8] with δ = 1/m; if the constants in that theorem are not uniform in δ, the bound in Lemma 3.6 gains m-dependent factors. Since Lemma 3.6 is used to show that no generic line exceeds k points, a non-absolute K would either inflate the required constant C or, in the worst case, invalidate the threshold C√(n log n) entirely. This is exactly the weakest assumption the reader identified. I found no other load-bearing error: the equality in Lemma 3.6 that should be an inclusion and the compressed constant arithmetic in (3.5) are cosmetic, and the possible degeneracy α = 1 in Lemma 3.7 is patchable. The verdict should remain CONDITIONAL pending verification of Theorem 2.4's uniformity.","tokens_in":13401,"tokens_out":29373,"duration_ms":259564,"concrete_test":"Check the statement and hypotheses of [16, Theorem 5.8] (Isaev–McKay, Random Structures & Algorithms 52(4):617–661, 2018): is δ = 1/m admissible for every m, and is the constant c̃(δ, 1/2, 1, 1) uniformly bounded as δ → 0? If the theorem does not give an absolute K, re-derive Theorem 2.4 for the sparse regime r/m → 0 via the configuration model and verify numerically (for m = n/4 up to 10^6 and r ≍ √(m log m)) that the ratio P(M ⊆ E(G))/(r/m)^t is bounded by an absolute constant, e.g. 2.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The main theorem for k ≤ 5n/6 relies on Lemma 3.6, whose tail bound uses Theorem 2.4: P(M ⊆ E(G)) ≤ K (r/m)^|M| with an absolute constant K. The proof of Theorem 2.4 invokes [16, Theorem 5.8] with δ = 1/m, which is not a fixed constant. The author asserts that the resulting constant c̃ = c̃(δ, ε, c1, c2) is absolute, but if the error constant in [16] grows as δ → 0 (e.g., like 1/δ or exp(1/δ)), then K depends on m = n/4. In Lemma 3.6, K enters D1 through log K; a polynomial dependence K = m^c only shifts the leading constant 5/2√35, but an exponential dependence would make the required k substantially larger than C√(n log n), breaking the stated theorem. The paper provides no quantitative control on K, and the displayed bound on |K̃'| in the proof sketch contains a term n ε^{-1/2} that cannot be bounded by a constant independent of n, so the sketch does not demonstrate absoluteness. This is the weakest link in the argument.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the no-(k+1)-in-line problem for the n x n integer grid: what is the maximum number f_k(n) of points one can select with no k+1 points on any line. The trivial row-count upper bound is kn. The authors prove that for every C > (5/2)sqrt(35) (and by Remark 3.11, any C > 25/2) there is N_C such that f_k(n)=kn whenever n >= N_C and k >= C sqrt(n log n). The proof combines an explicit construction for k >= 2n/3 and a probabilistic construction for k <= 5n/6, using a 4x4 subdivision into subgrids, independent uniform random regular bipartite graphs in each subgrid with sparse/dense densities, and concentration inequalities. Divisibility conditions on n and k are removed via two adjustment lemmas (reducing k and extending the grid). The central probabilistic lemmas (3.5-3.7, Corollary 3.8) control the intersection of the random set with generic lines and yield a set with positive reserve, giving the lower bound. The paper is well-organized and largely self-contained except for a cited enumeration bound (Theorem 2.4).","tokens_in":13651,"tokens_out":24367,"duration_ms":210345,"significance":"If correct, this is a substantial advance on a century-old problem: it determines the exact extremal value f_k(n)=kn for all k slightly above sqrt(n log n), showing that the trivial row bound is asymptotically tight in this regime. The random bipartite graph construction with a feasible density matrix (delta=4/5) is elegant and novel, and the reduction lemmas that pass from divisible n,k to the general case are clean and explicit. The paper also gives an explicit universal constant in the main theorem and notes a possible improvement to C>12.5. The main risk is the black-box reliance on Theorem 2.4 (the Isaev-McKay matching-containment bound); that issue is addressed in the major comments. Overall, the result, if fully substantiated, would be a notable contribution to lattice point geometry and extremal combinatorics.","major_comments":[{"comment":"The absoluteness of the constant K in Theorem 2.4 is not established. The proof sets delta=1/m, which is not a fixed constant, and claims that c-tilde(delta,epsilon,c1,c2) is absolute without demonstrating that the error terms in [16, Theorem 5.8] are uniform as delta tends to 0. Moreover, the displayed bound on |K-tilde'| contains the term n*epsilon^{-1/2}, which is unbounded as n grows; the claimed conclusion |K-tilde'| <= exp(3 c-tilde)-1 therefore does not follow from the displayed expression. This is load-bearing because Lemma 3.6 applies Theorem 2.4 to every subgrid (with m=n/4) and every matching arising from a generic line, and D1 depends on log K. If K actually depends on m (e.g., exponentially in 1/delta), the constant C in Theorem 1.2 would have to grow with n, breaking the stated result. The authors must either provide a self-contained proof of a uniform matching-containment bound for random r-regular bipartite graphs, or state and verify the precise version of [16, Theorem 5.8] they invoke, including uniformity of the error term as delta=1/m -> 0.","section":"Section 2.2, Theorem 2.4 and its proof"},{"comment":"The displayed expression for D3 in (3.5) is inconsistent with the definitions in Lemmas 3.6 and 3.7. From D2 = sqrt(7n)*D1 + 7 and D1 of order sqrt(log n), the leading term of D3 should be 5*sqrt(7(4-3epsilon)/2) * sqrt(n log n), not 5*sqrt(7(4-3epsilon)/2) * n log n, and the second term should be of order O(sqrt(n/log n)*log K), not (7/2) n log(7*2KL). As printed, the right-hand side is O(n log n) + O(n), which for fixed C would exceed k ~ C sqrt(n log n) for all sufficiently large n and would make the inequality C sqrt(n log n) >= D3 impossible. This is presumably a typographical error, but it must be corrected so that the threshold constant (5/2)sqrt(35) can be verified.","section":"Section 3.2, Proposition 3.9, Eq. (3.5)"},{"comment":"The proof contains the displayed equality P(sum s_{i,j} > sum kappa_{i,j}) = P(exists (i,j) : s_{i,j} > kappa_{i,j}), which is not correct as an equality: it is only an inclusion (the left event is contained in the union on the right). The subsequent use of the union bound requires only the inclusion, so the argument survives, but the statement as written is inaccurate and should be changed to a subset relation.","section":"Section 3.2, Lemma 3.6, proof"}],"minor_comments":[{"comment":"The definition of h'' is written as h'' := 2(n - n'), which is nonpositive because n <= n'. It should be h'' := 2(n' - n) (which lies in {0,2,4,6}). The subsequent sentence 'S' has reserve h''' should be 'S' has reserve at least h''', since h' >= h'' is used.","section":"Section 3.3, proof of Theorem 1.2"},{"comment":"The term n*epsilon^{-1/2} in the bound on |K-tilde'| is likely a typo for n^{-1/2}*epsilon^{-1/2} or a similar decaying factor. As written, the displayed bound cannot be bounded by a constant independent of n. This is tied to Major Comment 1 and should be clarified.","section":"Section 2.2, proof of Theorem 2.4"},{"comment":"For a subgrid with g_{i,j}(ell)=1, the interval for beta in (3.2) can force beta > 1, so Theorem 2.2 (which requires 0<beta<1) is not directly applicable. This is easily fixed by treating g=1 separately (the probability of exceeding kappa is then 0 for kappa >= 1), but the current proof does not address it.","section":"Section 3.2, Lemma 3.7"},{"comment":"The remark that delta=4/5 is the smallest value for which a (k,delta)-feasible 4x4 matrix exists (with at most four distinct entries) is stated without proof. If retained, it should be accompanied by a short justification or a reference.","section":"Section 3.1, Lemma 3.5"}],"recommendation":"major_revision","confidential_remarks":"The central probabilistic construction and the reduction lemmas appear sound and the result is likely correct in essence. The main risk is the reliance on Theorem 2.4; the proof of that theorem in the manuscript is only a sketch and contains an apparently incorrect bound (the n*epsilon^{-1/2} term). I did not verify [16] directly, but the uniformity of the constant as a function of delta=1/m is exactly the kind of issue that can invalidate the stated constant in the main theorem. The authors should be asked to provide a complete, checkable proof of the matching-containment bound or an exact citation with the uniformity condition verified. The other issues are mostly typographical and easily corrected. The paper is a good fit for the journal and, once the black-box issue is resolved, would be a strong contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis paper proves what looks like the right answer for a large regime: f_k(n)=kn whenever k ≥ C√(n log n). That is a genuine advance — prior work had asymptotics and bounds, not an exact value in this range. The construction is clever: split the grid into 4x4 subgrids, choose random regular bipartite factors with sparse/dense blocks, and use concentration to show no line gets more than k points. The upper bound is trivial, so the whole game is the lower bound, and the probabilistic machinery is well organized.\n\nThe main soft spot is Theorem 2.4, the black-box bound on the probability that a random regular bipartite graph contains a fixed matching. The proof given in the paper is compressed: it cites [16] with δ = 1/m and claims an absolute constant K, but the displayed exponent contains a term n ε^{-1/2} that is not constant in n. Either the cited theorem has a different normalization, or the authors have misread it. This matters because K enters the threshold constant C. If K depends on m, the stated C > 25/2 may not hold as written; the argument would still go through with a slightly larger C, but that is not what the theorem claims. A referee needs to check the Isaev–McKay statement directly. This is the one place I cannot certify the proof from the preprint.\n\nMinor issues: reference [11] is \"personal communication\" and is cited in the conclusion as if it were a paper; and Lemma 3.6 writes an equality where only an inclusion is true. Neither affects the argument.\n\nWho is this for? Extremal combinatorists and people who care about lattice point problems. It is a solid, clearly written paper with a real result. If the black box checks out, it is a nice theorem. I would send it to a serious referee.\n\nRecommendation: engage with it; accept for review.","headline":"Real exact result for large k, but the claimed absolute constant in Theorem 2.4 needs referee verification — worth a serious look.","tokens_in":14259,"tokens_out":3544,"would_cite":true,"duration_ms":31518,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05D40","05C80","05C35","52C10"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that an n×n grid can hold kn points with no k+1 collinear whenever k is at least a constant times √(n log n), making the trivial row bound tight.","keywords":["no-(k+1)-in-line problem","no-three-in-line problem","lattice points","regular bipartite graphs","probabilistic method","line intersections","extremal combinatorics","concentration inequalities"],"falsifier":"For fixed α in (0,1), sample uniform r = αm regular bipartite graphs on m+m vertices for growing m, and estimate sup_M P(M ⊆ G)/(r/m)^{|M|} over matchings M; if this ratio is unbounded, the absolute matching-probability constant used in Lemma 3.6 fails and the main theorem loses its uniform proof.","tokens_in":13168,"feed_emoji":"🎯","tokens_out":10272,"duration_ms":105140,"temperature":0.7,"pith_summary":"The paper targets a generalization of the no-three-in-line problem: how many points can be chosen from an n×n grid without any k+1 of them lying on one line? It proves that when k grows faster than about √(n log n), the exact answer is kn, the trivial bound obtained by allowing at most k points per row. This settles the exact extremal value in a broad range where no exact determination was previously known. The proof is probabilistic: it builds kn points by randomly filling rows and columns with a deliberate density bias, so that every non-axis-parallel line sees well below k points in expectation, and then uses concentration inequalities to control all lines at once.","feed_headline":"Grid puzzle's exact answer is kn for large k","feed_subtitle":"Theorem: if k exceeds a constant times √(n log n), no k+1 of the kn points share a line.","key_machinery":"The load-bearing object is the bi-uniform random graph: a union of independent uniform r_{i,j}-regular bipartite graphs on the 16 subgrids, with r_{i,j} taking two prescribed values according to a 4×4 sparse/dense pattern. Its feasibility matrix R records these densities, and R is (k, 4/5)-feasible, meaning the row and column sums of R are k and every generic secant's expected number of selected points is at most 4k/5. The proof's main lemma controls the probability that any secant exceeds a threshold: it bounds the union over lines by way of a matching-probability theorem for regular bipartite graphs, converts those bounds into exponential tails, and sums over all long secants using a grid line-count estimate. The final ingredient is reserve: the random set has at least 15 points of slack on every generic line, which the authors exploit through a line-colouring decomposition and an orthogonal projection step to pass from divisible n and k to all n and k.","core_discovery":"The central claim, Theorem 1.2, is that for every constant C > 25/2 (stated as C > (5/2)√35 in the theorem and improved in Remark 3.11) there is a threshold N_C such that f_k(n) = kn for all n ≥ N_C and k ≥ C√(n log n). The upper bound kn is trivial by counting points in rows; the content is the matching lower bound. The construction partitions the grid into 16 equal square blocks, marks the diagonal blocks as sparse and the off-diagonal blocks as dense, and in each block independently selects a uniform random r-factor with r = 2k/10 for sparse blocks and r = 3k/10 for dense blocks. Every row and every column then contains exactly k selected points, while any non-axis-parallel line has expected intersection at most 4k/5. A concentration lemma, built from a matching-enumeration bound for regular bipartite graphs and a Chernoff-type inequality for dependent variables, shows that with high probability no generic line exceeds k − 15, giving the desired set with reserve 15; elementary row-and-column adjustments then remove the divisibility assumptions on n and k.","pith_inferences":["The threshold √(n log n) is likely not the end of the story: the paper explicitly leaves open the possibility that f_k(n) = kn for k as small as n^ε for every ε > 0, and sharper line-count or matching-enumeration bounds would plausibly push the method into that range.","The sparse/dense block-bias idea may transfer to other settings with a known line-count bound, such as non-square grids or higher-dimensional lattices, where the trivial hyperplane bound could again be tight under a comparable scale condition.","A natural finite check not performed in the paper is to estimate the matching-probability ratio for moderate grid sizes; if that ratio stayed bounded, the black-box constant on which the proof relies would be experimentally credible."],"forward_implications":["For every fixed C > 12.5, once n is large and k ≥ C√(n log n), an n×n grid contains kn points with no k+1 collinear, so the row-count upper bound f_k(n) ≤ kn is tight throughout this whole range.","The same construction produces such sets with reserve 15 on every non-axis-parallel line, so small changes in k or n can be absorbed while keeping the extremal value.","The classical no-three-in-line problem with k = 2 remains open, but the generalized problem is now settled on an unbounded range of k, removing a long-standing family of open extremal questions in that regime.","Any improvement in the line-count exponent or in the matching-probability bound immediately shrinks the threshold constant C, since these quantities enter the main probability estimate directly."],"supporting_citations":[{"why":"Supplies the uniform bound on the probability that a fixed matching lies in a random regular bipartite graph; this is the engine that makes the per-line probability estimates in Lemma 3.6 possible.","marker":"[16]"},{"why":"Gives the concentration inequality for dependent indicator variables that converts bounded t-matching probabilities into the exponential tail bound used over every generic line.","marker":"[20]"},{"why":"Provides the asymptotic count of secants with at least κ points in an n×n grid, which lets the proof union-bound over all generic lines rather than being swamped by their number.","marker":"[23]"}],"fun_headline_variants":["Exact grid max: kn points with no k+1 collinear when k large","Century-old in-line puzzle: max is kn for large k","Settling the no-(k+1)-in-line problem: answer is kn for large k","No k+1 collinear: kn points is exact maximum for big k","For large k, grid max with no k+1 in line is exactly kn"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Everything rests on the imported claim that a single absolute constant controls the probability that a random regular bipartite graph contains a fixed matching, uniformly in the graph size.","fun_headline_variants_meta":{"raw":{"variants":["Exact grid max: kn points with no k+1 collinear when k large","Century-old in-line puzzle: max is kn for large k","Settling the no-(k+1)-in-line problem: answer is kn for large k","No k+1 collinear: kn points is exact maximum for big k","For large k, grid max with no k+1 in line is exactly kn"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000783,"raw_usage":{"total_tokens":3424,"prompt_tokens":882,"completion_tokens":2542,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":498,"completion_tokens_details":{"reasoning_tokens":2435}},"tokens_in":498,"tokens_out":2542,"duration_ms":17694,"temperature":1.0,"reasoning_tokens":2435,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T20:01:21.536592+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For fixed α in (0,1), sample uniform r = αm regular bipartite graphs on m+m vertices for growing m, and estimate sup_M P(M ⊆ G)/(r/m)^{|M|} over matchings M; if this ratio is unbounded, the absolute matching-probability constant used in Lemma 3.6 fails and the main theorem loses its uniform proof.","supporting_citations":[{"cited_title":"Isaev and B","cited_arxiv_id":null,"evidence_quote":"Supplies the uniform bound on the probability that a fixed matching lies in a random regular bipartite graph; this is the engine that makes the per-line probability estimates in Lemma 3.6 possible."},{"cited_title":"Pach and G","cited_arxiv_id":null,"evidence_quote":"Provides the asymptotic count of secants with at least κ points in an n×n grid, which lets the proof union-bound over all generic lines rather than being swamped by their number."}],"review_version":1}