{"id":"146e0cc0-e798-485f-9d10-58ca59bdb87b","arxiv_id":"2412.14287","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper proves new asymptotic upper and lower bounds for three subset-selection problems on planar point sets with at most s collinear points.","lead":"The paper derives new bounds on the largest subset of a planar point set that avoids collinear triples, stays monotone, or has pairwise distinct slopes, given that no line contains more than s points. A specialist would read it for progress on three Erdős-style subset-selection problems, including a near-matching logarithmic gap when s is about the square root of n.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Equation (36) fails the Saxton–Thomason container condition: the term 2Δ3/(dτ²) is O(log n / n^f), not O(n^(−f)), so Theorem 1(ii) has a repairable gap; the reader's eq-(33) objection is not valid.","rationale":"I read the paper in good faith and checked the main mathematical structure. The central claim, Theorem 1, is a pair of upper bounds for the largest general-position subset. The proof of part (i) is a standard random-grid construction and appears sound. The proof of part (ii) uses the hypergraph container method; this is where the most load-bearing step lives. The reader's stated weakest assumption was the monotonicity step at equation (33), claiming that f(n,s) ≤ f(n,3) ≤ n^(5/6+o(1)) cannot imply O(n^(5/6+o(1))/√s) for 3 ≤ s ≤ log n. That objection does not land: for this range √s is at most √(log n), which is n^(o(1)), so the denominator can be absorbed into the o(1) exponent. The proof can be read as choosing that o(1) appropriately. However, I found a separate, real gap that the reader did not identify. In equation (36), the bound for the second term of Δ(H′,τ) is off by a logarithmic factor: the displayed inequality 10^8 log n / n^f ≤ ε with ε = n^(−f)/2 is false. This exact point is needed to apply Lemma 10, so the proof of the main container step is incomplete as written. The gap is not fatal: choosing ε to be a small absolute constant instead of n^(−f)/2 makes the container hypothesis true for large n, and the subsequent shrinking and counting arguments only require ε to be bounded away from 1, not tending to zero. I also noted the minor inconsistency in Lemma 11, where a matching of triples is written as if it were all binomial triples; the lower-bound estimate that follows is the one consistent with the matching construction, so this is an expositional error. Given the easy repair, the paper's verdict should remain conditional: the theorem is likely correct, but the manuscript should fix the verification of the container condition and correct the Lemma 11 display before publication.","tokens_in":18281,"tokens_out":27178,"duration_ms":231072,"concrete_test":"Recompute the verification of Lemma 10 in §3.2: substitute d ≥ n^(3−3x)/(10^7 log n), Δ2 = Δ3 = 1, τ = n^(x+γ/2−3/2), and x ≤ γ−f into (36). Confirm that the second term is on the order of log n / n^f, which exceeds ε/600 when ε = n^(−f)/2, so the stated inequality fails. Then rerun the argument with ε replaced by 1/4: verify Δ ≤ 1/2400 for n ≥ n_0(f), the shrink bound (38) becomes |S\\C| ≥ (3/4)f|S|/10^4, and the final container count in (39) is unchanged up to constants. If all steps pass, the theorem is proved after this correction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In §3.2 the container hypothesis is not verified as written. With d ≥ n^(3−3x)/(10^7 log n), Δ2, Δ3 ≤ 1, τ = n^(x+γ/2−3/2), and x ≤ γ−f, the second term in Δ(H′,τ) is bounded by 2·10^7 log n / n^(γ−x) ≤ 2·10^7 log n / n^f, while ε = n^(−f)/2 gives ε/(100·3!) = n^(−f)/1200. The asserted inequality 10^8 log n / n^f ≤ n^(−f)/2 is false for every n, so Lemma 10 cannot be applied with this ε. This gap is load-bearing because the container step is the core of the main upper-bound construction. The repair is simple: choose ε to be a small absolute constant, e.g., 1/4; then Δ ≤ 1/2400 for sufficiently large n, and the later steps (37)–(39) only need ε bounded away from 1, so the shrinking argument and container-size estimate survive unchanged. Alternatively, multiply τ by √(log n). The reader's concern about equation (33) is not genuine: for 3 ≤ s ≤ log n, √s ≤ √(log n) = n^(o(1)), so the known f(n,3) bound yields O(n^(5/6+o(1))/√s) once the o(1) exponent is chosen to absorb √(log n). Lemma 11's displayed binomial formula is a typo: the matching on ℓ∩S has about |ℓ∩S|/3 edges, not C(|ℓ∩S|,3), but the lower bound |S|/3 − |L_v| actually used is valid.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies three subset-selection problems for n-point planar sets with maximum collinearity s: (i) the largest subset in general position, (ii) the largest monotone general-position subset, and (iii) the largest subset with pairwise distinct slopes. The main results are Theorem 1, giving upper bounds f(n,s)=O(n/s) for n^{1/3} ≤ s ≤ n and f(n,s)=O(n^{5/6+o(1)}/√s) for 3 ≤ s ≤ n^{1/3}; Theorem 4, giving g(n,s)=Ω((n log n log s / s^2 / log s)^{1/4}) and O((n/s)^{1/2}); Theorem 5, giving lower and upper bounds for the grid; Theorem 6, giving h(n,s)=Ω((n/log s)^{1/3}) and upper bounds; and Theorem 22, on coloring point sets into general-position classes. The proofs combine incidence geometry, the Cooper–Mubayi coloring lemma, the Saxton–Thomason container method, Szemerédi–Trotter, Sidon sets, and random sampling.","tokens_in":18715,"tokens_out":14363,"duration_ms":103753,"significance":"If the proofs are correct, the paper provides the first upper bounds for f(n,s) in the non-constant range that are tight up to constants when s=Ω(√n log n), as well as new bounds for the monotone and distinct-slope variants for arbitrary planar sets. The container-based approach extends Balogh–Solymosi in a novel way, and the lower-bound constructions are clean and use a well-chosen mix of existing tools. However, the central container step contains a false inequality in §3.2, Eq. (36), which currently invalidates the proof of Theorem 1(ii); the gap appears easily repairable, so the results are likely salvageable with a modest revision.","major_comments":[{"comment":"The application of Lemma 10 fails as written. With d ≥ n^{3−3x}/(10^7 log n), τ = n^{x+γ/2−3/2}, and x ≤ γ − f, the second term in Δ(H′,τ) satisfies 2Δ_3/(dτ^2) ≤ 2·10^7 log n / n^{γ−x} ≤ 2·10^7 log n / n^f, so Δ(H′,τ) = O(log n / n^f), not O(n^{−f}). For the claimed ε = n^{−f}/2, the required inequality Δ(H′,τ) ≤ ε/(100·3!) = n^{−f}/1200 would force log n = O(1), which is false for large n. Consequently, Lemma 10 cannot be applied with this ε, and the container collection, the shrinking bound (38), and the container-size estimate (39) are not justified as written. A simple repair is to take ε to be a small absolute constant, e.g., ε = 1/4; then Δ(H′,τ) ≤ 1/2400 for sufficiently large n, and the later steps (37)–(39) only require that ε is bounded away from 1. The repair should be stated explicitly because the current text claims ε = n^{−f}/2.","section":"§3.2, Eq. (36)"}],"minor_comments":[{"comment":"The monotonicity step in Eq. (33) is actually valid: for 3 ≤ s ≤ log n, we have √s ≤ √(log n) = n^{o(1)}, so the o(1) in the known bound f(n,3) ≤ n^{5/6+o(1)} absorbs the extra √(log n) factor. The claimed bound O(n^{5/6+o(1)}/√s) therefore follows for this range; the concern that monotonicity alone cannot create the √s improvement is unfounded, because the improvement comes from the slack in the exponent, not from a hidden monotonicity inequality.","section":"§3.2, Eq. (33)"},{"comment":"The displayed equality e(H'[ℓ∩S]) = binom(|ℓ∩S|,3) is incorrect: H' is defined by placing a matching on ℓ∩S, so the number of edges on a line ℓ is floor((|ℓ∩S|−2)/3), not a binomial coefficient. The subsequent lower bound T_v ≥ |S|/3 − |L_v| is consistent with the matching interpretation, so this is a presentation typo rather than a substantive error, but it should be corrected.","section":"Lemma 11, Eq. (31)"},{"comment":"The bound on Δ(H′) is written as n^{3−3x} 10^{3f} log n, which is ambiguous: it could be read as n^{3−3x}/(10^{3f} log n) or n^{3−3x}/(10^3 f log n). The proof and the subsequent use of the bound in Eq. (36) depend on the intended denominator; the authors should disambiguate the notation.","section":"Lemma 11"},{"comment":"In the upper-bound construction for Theorem 4, the phrase 'slightly randomly perturb each of its grid points and replace it by a collinear s-tuple' should specify that the perturbed points are chosen so that no unintended collinearities or monotonicity obstructions arise; as written, the construction is rather informal, though the intended argument is clear.","section":"§4.1"},{"comment":"In the proof of Theorem 6 lower bound, the notation L is used both for the number of collinear triples and, in Lemma 18, for a line; this is not a mathematical error but the double use of L may confuse readers.","section":"§5.1"}],"recommendation":"major_revision","confidential_remarks":"The false inequality in Eq. (36) is a genuine gap in the proof of Theorem 1(ii), but it is local and easily repairable by taking ε to be a small absolute constant, as described in Major Comment 1. I do not agree with the reader's concern about Eq. (33); that step is justified because √(log n)=n^{o(1)}. Once the container repair is made explicit, the main results appear sound. The paper is otherwise well within the scope of math.CO and would be a solid contribution after the repair."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth engaging with. The main upper-bound proof as written has a gap in the container step, but it is local and easy to fix. The reader's objection to equation (33) does not survive reading: for s ≤ log n, sqrt(s) = n^{o(1)}, so the known f(n,3) bound yields exactly the claimed O(n^{5/6+o(1)}/sqrt(s)) once the o(1) exponent absorbs sqrt(log n). Monotonicity is fine here.\n\nThe real issue is equation (36). The second term in Δ(H',τ) is 10^8 log n / n^f, which is not O(n^{-f}) as the stated ε = n^{-f}/2 requires. So Lemma 10 cannot be applied with that ε. The fix is simple: take ε to be a small fixed constant, e.g., 1/4; then the condition holds for sufficiently large n, and the container-size estimate only needs ε bounded away from 1. This should be corrected in revision, but it is not fatal.\n\nWhat is actually new: the balanced supersaturation lemma (Lemma 11) and its use inside the container iteration is a genuine technical novelty, and it yields the first sub-polynomial improvement over the f(n,3) upper bound for intermediate s. The lower bounds for g and h on general point sets, and the near-matching logarithmic gaps at s = Θ(√n), are also new. The paper is clearly written, and the tools — incidence geometry, containers, additive combinatorics — are used appropriately.\n\nSoft spots beyond (36): Lemma 11 has a typo in the displayed edge-count formula, writing binom(|ℓ∩S|,3) where the matching gives about |ℓ∩S|/3; the subsequent lower bound uses the correct quantity, so it is cosmetic. The small-s part of Theorem 1(ii) is fine once you accept the monotonicity-plus-o(1) argument. The proof of Theorem 4's lower bound is a quick combination of Proposition 2 and Erdős–Szekeres, which is legitimate.\n\nFor whom: anyone working on subset selection in discrete geometry or on container-method applications to geometric problems. It deserves a serious referee; the gap is local and repairable. I would send it out.","headline":"Genuinely new bounds, but the container-step verification has a repairable log-factor gap.","tokens_in":19267,"tokens_out":2708,"would_cite":true,"duration_ms":22177,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["52C10","05D40","05C65"],"pacs":[],"model":"deepseek-v4-flash","headline":"For planar points with bounded collinearity, the largest no-three-in-line subset is $\\Theta(n/s)$ when $s$ is large, with new bounds in every remaining regime.","keywords":["subset selection","general position","collinearity","monotone subsets","distinct slopes","hypergraph containers","supersaturation","planar point sets"],"falsifier":"Compute the edge count in Lemma 11 directly for a small example such as $S=[n]^3$ with $x=0$: because each line contributes a matching of about $|\\ell\\cap S|/3$ edges rather than $\\binom{|\\ell\\cap S|}{3}$, the displayed lower bound $e(H')\\ge n^6/(10^7\\log n)$ should be checked against the corrected count; if it falls below the bound, the supersaturation lemma loses support. Separately, a search for $n$-point sets with at most 4 collinear points and a general-position subset larger than the claimed $O(n^{5/6+o(1)}/\\sqrt{4})$ bound would refute Theorem 1(ii) in that case.","tokens_in":18094,"feed_emoji":"📐","tokens_out":16572,"duration_ms":125018,"temperature":0.7,"pith_summary":"This paper establishes upper bounds for three subset-selection problems on planar point sets with limited collinearity. For the classical problem of choosing a subset with no three points on a line, the main result is that every $n$-point set with at most $s$ points per line has such a subset of size $O(n/s)$ when $n^{1/3} \\le s \\le n$, and $O(n^{5/6+o(1)}/\\sqrt{s})$ when $3 \\le s \\le n^{1/3}$; together with previously known lower bounds this gives $\\Theta(n/s)$ once $s = \\Omega(\\sqrt{n} \\log n)$. The paper also proves bounds for monotone general-position subsets, showing upper $O((n/s)^{1/2})$ and, when $s=\\Theta(\\sqrt{n})$, upper $O(n^{1/4})$ and lower $\\Omega((n \\log \\log n/\\log n)^{1/4})$, so the gap is only logarithmic. For subsets with pairwise distinct slopes it gives a universal lower bound $\\Omega((n/\\log s)^{1/3})$ and worst-case upper bounds $O(\\sqrt{n})$ and $O((n/s)^{4/5})$ in complementary ranges of $s$. These are quantitative answers to questions rooted in classical no-three-in-line problems that remain open for grids.","feed_headline":"Optimal no-three-in-line subset size found when s is large","feed_subtitle":"Sharp up to a constant factor for s at least √n log n, with new bounds for all smaller s.","key_machinery":"The load-bearing object is the 3-uniform hypergraph whose vertices are grid points and whose edges are collinear triples. The new step is a balanced supersaturation lemma: any $S\\subseteq[n]^3$ of size $n^{3-x}$ contains a spanning subhypergraph $H'$ with $e(H')\\ge n^{6-4x}/(10^7\\log n)$, maximum degree at most $n^{3-3x}/(10^3 f\\log n)$, and pair-codegree at most 1. Feeding this hypergraph into the container lemma yields containers that shrink by a constant fraction, and iterating $(\\log n)^2$ times produces $\\exp(n^{(3+\\gamma)/2+o(1)})$ containers of size $n^{3-\\gamma+f}$. A random subset of $[n]^3$ with no collinear $n^\\alpha$-tuple is then shown, by a first-moment estimate over the containers, to have no large general-position subset; projecting back to the plane gives the upper-bound construction.","core_discovery":"The paper's central claim is Theorem 1: for every $n$-point planar set $P$ with at most $s$ points on any line, the largest general-position subset has size $f(n,s)=O(n/s)$ for $n^{1/3}\\le s\\le n$ and $f(n,s)=O(n^{5/6+o(1)}/\\sqrt{s})$ for $3\\le s\\le n^{1/3}$; in particular $f(n,s)=\\Theta(n/s)$ when $s=\\Omega(\\sqrt{n}\\log n)$. The large-$s$ range is proved by taking a random subset of the square grid $[n]^2$ and applying the pigeonhole principle. The small-$s$ range is proved by lifting to the cube $[n]^3$, applying the hypergraph container method to a sparsified hypergraph of collinear triples with pair-codegree at most one, iterating containers until every collinear-triple-free set lies in a small family of small containers, and then projecting a random subset back to the plane. The paper additionally claims bounds for monotone general-position subsets and for subsets with pairwise distinct slopes, stated as Theorems 4 through 6.","pith_inferences":["The proof of the small-$s$ range in Theorem 1(ii) contains a monotonicity step that is not fully justified for $3\\le s\\le\\log n$; if that step fails, the claimed $1/\\sqrt{s}$ improvement for fixed small $s$ would be unsupported even though the rest of the theorem could stand.","If the small-$s$ bound survives scrutiny, it predicts a genuine constant-factor improvement over $f(n,3)$ for every fixed $s>3$, which could be probed computationally on small grids for $s=4,5$.","The balanced supersaturation lemma is formulated for collinear triples in $[n]^3$, but the same container iteration only needs bounded pair-codegrees; it may transfer to higher-dimensional grids or to collinear $k$-tuples.","The distinct-slopes bounds leave a wide gap in the middle range, suggesting the extremal construction is neither a grid nor a parabolic Sidon set; finding the true extremal set for $s$ near $n^{3/8}$ is a concrete next step."],"forward_implications":["If Theorem 1 is right, the general-position problem is resolved up to constants for $n^{1/3}\\le s\\le n$, and exactly $\\Theta(n/s)$ for $s=\\Omega(\\sqrt{n}\\log n)$.","When $s=\\Theta(\\sqrt{n})$, monotone general-position subsets have size between $\\Omega((n\\log\\log n/\\log n)^{1/4})$ and $O(n^{1/4})$, so only logarithmic factors separate the bounds.","Every $\\sqrt{n}\\times\\sqrt{n}$ grid contains a monotone general-position subset of size $\\Omega((n/\\log n)^{2/5})$, while every such subset has size $o(n^{1/2})$.","For distinct slopes, any $n$-point set with at most $O(\\sqrt{n})$ collinear points contains a subset of size $\\Omega((n/\\log s)^{1/3})$, matching the best grid bound when $s=\\Theta(\\sqrt{n})$, with worst-case upper bounds $O(\\sqrt n)$ for $s\\le n^{3/8}$ and $O((n/s)^{4/5})$ after.","As a corollary, any $n$-point set with at most $\\sqrt n$ collinear points can be colored with $O(\\sqrt n\\log n)$ colors so each color class is in general position."],"supporting_citations":[{"why":"supplies the projection method and the supersaturation starting point that Theorem 1(ii) extends.","marker":"[2]"},{"why":"provides the hypergraph container lemma used to produce the small container family.","marker":"[30]"},{"why":"gives the sparse-hypergraph chromatic-number bound used in the Proposition 2 lower bound.","marker":"[7]"},{"why":"supplies the collinear-triple count (Lemma 8) and the earlier lower bounds for f(n,s) that Theorem 1 complements.","marker":"[24]"},{"why":"supplies the monotone-subsequence theorem used to extract a monotone subset from a general-position subset.","marker":"[13]"},{"why":"grid result that every large subset of [n]^2 contains a trapezoid underlies the distinct-slopes upper bound.","marker":"[11]"},{"why":"supplies the incidence bound used to estimate the number of trapezoids in Lemma 18.","marker":"[32]"},{"why":"Jarnik's convex lattice polygon bound is the baseline for the grid lower bound in Theorem 5.","marker":"[20]"},{"why":"Pomerance's collinear-subsequence theorem produces the o(n^{1/2}) upper bound for monotone general-position subsets of the grid.","marker":"[26]"}],"fun_headline_variants":["Tight no-three-in-line subset size for large s","New bounds for largest collinear-free subset in plane","Sharp bounds for no-3-collinear and distinct-slope subsets","Optimal no-three-in-line subset size for large s"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof of the small-$s$ range in Theorem 1(ii) relies on equation (33), which derives the factor $1/\\sqrt{s}$ for $3\\le s\\le\\log n$ from monotonicity alone; that division is not a consequence of monotonicity, and the container argument only establishes it for $s\\ge\\log n$.","fun_headline_variants_meta":{"raw":{"variants":["Tight no-three-in-line subset size for large s","New bounds for largest collinear-free subset in plane","Sharp bounds for no-3-collinear and distinct-slope subsets","Optimal no-three-in-line subset size for large s"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000691,"raw_usage":{"total_tokens":3297,"prompt_tokens":1279,"completion_tokens":2018,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":895,"completion_tokens_details":{"reasoning_tokens":1962}},"tokens_in":895,"tokens_out":2018,"duration_ms":17842,"temperature":1.0,"reasoning_tokens":1962,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T12:23:31.577553+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the edge count in Lemma 11 directly for a small example such as $S=[n]^3$ with $x=0$: because each line contributes a matching of about $|\\ell\\cap S|/3$ edges rather than $\\binom{|\\ell\\cap S|}{3}$, the displayed lower bound $e(H')\\ge n^6/(10^7\\log n)$ should be checked against the corrected count; if it falls below the bound, the supersaturation lemma loses support. Separately, a search for $n$-point sets with at most 4 collinear points and a general-position subset larger than the claimed $O(n^{5/6+o(1)}/\\sqrt{4})$ bound would refute Theorem 1(ii) in that case.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the projection method and the supersaturation starting point that Theorem 1(ii) extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides the hypergraph container lemma used to produce the small container family."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"gives the sparse-hypergraph chromatic-number bound used in the Proposition 2 lower bound."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the collinear-triple count (Lemma 8) and the earlier lower bounds for f(n,s) that Theorem 1 complements."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the monotone-subsequence theorem used to extract a monotone subset from a general-position subset."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"grid result that every large subset of [n]^2 contains a trapezoid underlies the distinct-slopes upper bound."},{"cited_title":"Trotter, Extremal problems in discrete geometry, Combinatorica 3 (1983), 381–392","cited_arxiv_id":null,"evidence_quote":"supplies the incidence bound used to estimate the number of trapezoids in Lemma 18."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Jarnik's convex lattice polygon bound is the baseline for the grid lower bound in Theorem 5."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Pomerance's collinear-subsequence theorem produces the o(n^{1/2}) upper bound for monotone general-position subsets of the grid."}],"review_version":1}