{"id":"a8ff8d21-f038-47d7-bdab-8678c5156636","arxiv_id":"2501.11156","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"New asymptotic covering bounds for k-fold line and plane covers of conical and half grids, plus an exact formula for one-shot covers in the plane.","lead":"This paper proves new bounds on how many lines or planes are needed to cover every dot in a triangular half-grid at least k times while skipping one corner. The results extend the classic Alon-Furedi grid covering theorem to more general point shapes, with sharp answers in 2D and 3D for generic grids.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 3D lower-bound proof assumes planes cut the front face in lines; for support-size-2 planes this is false in coordinate space, so the dual weighting is not certified.","rationale":"The reader's CONDITIONAL verdict was based on typos and the omitted k/6 condition in the 3D dual weighting. The stress-test found a deeper issue in the same lower-bound proof: the dual weighting's feasibility is not established because a plane with support of size 2 does not cut the abstract front face in a line, so the [4] line-sum bound cannot be applied. The upper bound construction in Theorem 1.5 is concrete and appears sound; the central risk is the lower bound. This is not a counterexample to the theorem, but it invalidates the written proof. Since the theorem may be recoverable with a stronger genericity hypothesis or a different dual certificate, the verdict remains conditional rather than reject. The concrete test would determine whether the proposed weighting fails on an allowed grid, thereby settling whether the concern actually lands.","tokens_in":10910,"tokens_out":28627,"duration_ms":278995,"concrete_test":"Fix n large and k=1. Choose strictly increasing sets S2 and S3 so that the equation b_s + c_t = 1 has one solution on each anti-diagonal s+t = 2,...,n, while choosing S1 generically so Definition 5 still holds. Compute the paper's proposed dual weight on the plane y+z=1 restricted to the front face. If the sum exceeds 1, the proposed weighting is infeasible and the lower-bound proof fails; if the sum stays at most 1 for all such constructions, the gap may be repairable.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The lower bound for Theorem 1.5 rests on a dual weighting whose feasibility proof conflates the index simplex {r+s+t=n} with the actual geometric front face. The text says 'the intersection of any plane with this front face is a line', but a plane with support {2,3}, e.g. u2*y + u3*z = 1, meets the index set in the curve u2*b_s + u3*c_t = 1, which need not be a line; it can contain one point from many different x-slices. Definition 5 only bounds each slice (fixed x) by |I|=2 points, so it does not prevent such a curve from containing Theta(n) weighted front-face points. The [4] weighting is certified only on lines of the triangular front face, not on arbitrary monotone curves, so the sum of weights on such a plane can exceed k. Consequently the claimed 31nk/18 - O(k) lower bound is not proved by the given argument. The omitted k/6 condition noted by the reader is fixable, but this geometric gap is structural: either the genericity definition must be strengthened or a different weighting/argument is needed for planes parallel to an axis.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies multiplicity hyperplane covering problems for half-grids, i.e., grids cut along a diagonal. It proves lower bounds for covering conical grids and m x n half-grids with lines (Theorems 1.1 and 1.2), an exact formula for covering an m x n half-rectangular grid while missing an arbitrary point (Theorem 1.3), and asymptotically tight bounds for generic 2D and 3D half-grids with the vertex missing (Theorems 1.4 and 1.5). The proofs combine a row-counting lemma, explicit constructions, and LP-duality weightings.","tokens_in":11162,"tokens_out":25328,"duration_ms":236998,"significance":"If the results are correct, the paper gives the first asymptotically sharp multiplicity covering bound for generic half-grids in R^3, and it shows a separation from the full-grid constant. The 2D bounds, the conical-grid lower bound, and the exact structured-grid result are clean and likely correct; the explicit plane construction in the 3D upper bound is also a useful contribution. However, the lower-bound proof for the 3D theorem relies on an unproved geometric assertion about plane intersections with the front face, and the statement of the theorem has an incorrect error term. These issues need repair before the main claim can be accepted.","major_comments":[{"comment":"The assertion that 'the intersection of any plane with this front face is a line' is not justified. The front face {(a_r,b_s,c_t): r+s+t=n} is not a geometric plane for a general half-grid, and a plane with support {2,3}, e.g. u_2 y + u_3 z = 1, intersects it in the set of index pairs (s,t) satisfying u_2 b_s + u_3 c_t = 1 as r varies. Definition 5 only bounds each fixed-x slice by |I|=2 points, so such a plane can contain Theta(n) front-face points, one per slice. The weighting from [4] is certified for lines in the 2D triangular grid, not for such monotone curves, so the sum of weights on such a plane is not shown to be at most k. Consequently the lower bound 31/18 nk - O(k) is not established by the given argument. The genericity definition must be strengthened or a different weighting/argument is required.","section":"§3.2, lower-bound proof of Theorem 3.5"},{"comment":"The stated equality cov_k(Γ) = 31/18 nk - Θ(n^2 + k) is not supported by the proof. The lower bound proved is 31/18 nk - O(k), and the upper bound is 31/18 nk + O(n^2 + k). The error term therefore lies between -O(k) and +O(n^2+k), so writing '-Θ(n^2+k)' incorrectly asserts a negative error of order n^2. The theorem should state the result as 31/18 nk + O(n^2 + k), or give separate upper and lower bounds with their respective error terms.","section":"Theorem 3.5 / Theorem 1.5 statement"},{"comment":"In the proof of Corollary 3, Lemma 1 is applied to an m-row half-grid, so the first term in the lower bound should be (m-s)k, not (n-s)k. As written, the expression l + (n-s)k - ... leads to a bound of order nk, which would contradict the trivial upper bound of mk lines (take each horizontal line k times) when n > m. The subsequent critical-point calculation and the final bound mk(1 - e^{-n/m} - O(n/m^2)) are consistent with the corrected expression (m-s)k.","section":"§2, Corollary 3 proof"}],"minor_comments":[{"comment":"In item 3 of the plane construction, 'z/c_i + z/a_i = 1' appears to be a typo for 'z/c_i + x/a_i = 1'.","section":"§3.2, upper-bound construction, type 3 planes"},{"comment":"The name 'Cayely-Bacharach' should be 'Cayley-Bacharach'.","section":"§1, Introduction"},{"comment":"The set L of lines is defined as all lines intersecting Γ in at least two points, without excluding lines through the vertex, but the primal problem forbids covering the vertex. The dual constraints later correctly restrict to lines not passing through V; the definition of L should be adjusted to match.","section":"§3.1, LP formulation"},{"comment":"The index sets S_i in Definition 5 are written as {0 = a_{i,0} < ... < a_{i,n}} with n+1 elements, whereas earlier definitions (e.g., Definition 2) use index sets of size n with sums bounded by (n-1). This notational inconsistency should be clarified.","section":"Definition 5"}],"recommendation":"major_revision","confidential_remarks":"The 3D lower-bound gap is the main obstacle. I believe the upper bound and the rest of the paper are sound, but the proof of Theorem 3.5's lower bound needs either a substantially stronger genericity condition or a new dual-weighting argument. The theorem statement's error term also needs correction. I recommend major revision rather than rejection because the claimed results are plausible and the manuscript contains other correct contributions that are worth preserving."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe paper has a real gap in its headline result. Theorem 1.5's lower bound relies on a dual weighting that the authors certify by saying any plane intersects the front face in a line. That is false for planes with support size 2 (e.g., u2 y + u3 z = 1). Such a plane can meet the index simplex {r+s+t=n} in a curve that picks one point from many x-slices, and the genericity condition only bounds each slice by 2 points. So the weight sum on such a plane can exceed k, and the 31nk/18 - O(k) lower bound is not proved by the given argument. This is structural, not a typo; either the genericity definition needs strengthening to rule out such curves, or a new weighting is needed.\n\nThat said, there is genuinely new and correct material here. The conical grid bound (Theorem 1.1) and the m x n half-grid bound (Theorem 1.2) follow from a simple counting lemma that seems sound, modulo fixable typos (Corollary 3 uses n-s where m-s is needed, and the displayed bound in Corollary 2 is mangled). The exact k=1 formula for half-rectangular grids (Theorem 1.3) is clean and correct as far as I can tell. The 2D generic half-grid result (Theorem 1.4) is also correct: the dual weighting is valid because any line meets at most two weighted points.\n\nThe 3D upper bound construction is plausible and the case analysis checks out in broad strokes (with the obvious typo in type 3 planes, z/c_i + x/a_i, not z/a_i). The lower bound is the problem. The paper's comparison to the triangular grid bound of Basit-Clifton-Horn is useful and honest.\n\nI agree with the reader that the circularity burden is zero and the paper engages fairly with prior work. The typos are easy repairs, but the 3D weighting gap is not. Still, this is a paper worth refereeing: the 2D and conical grid contributions are solid, and the 3D problem is likely fixable with either a stronger genericity notion or a different LP weighting. I'd send it to review, but the referee should be asked to check Theorem 1.5's lower bound carefully.\n\nBest,\n[Your name]","headline":"The 3D lower bound in Theorem 1.5 rests on a false geometric claim, but the paper has enough solid new results to warrant a serious referee.","tokens_in":11732,"tokens_out":4570,"would_cite":false,"duration_ms":41930,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05B40","52C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"For generic half-grids, the minimum k-fold line cover is asymptotically 3nk/2, and the plane cover in 3D is 31nk/18.","keywords":["half-grid","conical grid","hyperplane covering","covering with multiplicity","generic grid","linear programming duality","Alon-Furedi theorem","polynomial method"],"falsifier":"Take a generic half-grid with n=6 in the plane and k=4, compute the true minimum number of lines by exhaustive integer programming over all lines determined by pairs of grid points, and check whether any cover uses fewer than 3*6*4/2 - 2*4 = 28 lines; a cover with 27 lines would refute the lower bound. In 3D, check whether the proposed dual weighting is feasible by testing every plane not through the origin: if any plane has total weight exceeding k, the lower-bound argument fails.","tokens_in":10697,"feed_emoji":"🔺","tokens_out":7073,"duration_ms":71807,"temperature":0.7,"pith_summary":"This paper establishes asymptotically sharp bounds on how many lines or planes are needed to cover every point of a half-grid—the triangular point set obtained by cutting a rectangular grid along a diagonal—at least k times while deliberately missing the corner point. For generic n by n half-grids in the plane the answer is 3nk/2 up to O(k), and for generic n by n by n half-grids in space it is 31nk/18 up to O($n^{2}$+k). These are the first multiplicity-covering bounds of this sharpness for three-dimensional half-grids, and the 3D constant genuinely differs from the full-grid constant. The paper also proves a general lower bound of about nk(1-1/e) for arbitrary conical grids and an exact formula, in the single-cover case k=1, when the missing point is arbitrary.","feed_headline":"Generic half-grids need 3/2 nk lines, 31/18 nk planes","feed_subtitle":"Sharp k-fold covering bounds while missing the corner: 3D's 31/18 differs from the full grid's 11/6.","key_machinery":"The argument runs through the dual of the linear programming relaxation of the covering problem: assign nonnegative weights to the points of the half-grid so that every admissible line or plane that misses the vertex has total weight at most k; the total assigned weight is then a lower bound on the covering number. The paper's lower bounds are feasible weightings—constant weights on certain boundary diagonals and on the surface r+s+t=n in 3D—whose validity rests on the genericity assumption, since any line or plane can then meet only a few positively weighted points. Matching upper bounds come from explicit constructions that repeat a fixed family of axis-parallel and diagonal lines or planes, with counts chosen to cover every point at least k times; the 3D construction uses five types of planes and a case analysis on the coordinates of the point being covered.","core_discovery":"Specialize to a half-grid H built from two n-point sets on the axes, with vertex at the corner, and assume genericity: no line that is not axis-parallel contains more than two points of H, and in three dimensions no plane that is not axis-parallel contains more than three points. The paper proves that the minimum number of lines covering every point of H except the vertex at least k times lies between 3nk/2 - 2k and 3nk/2 + k/2, and that in three dimensions the analogous number for planes is exactly 31nk/18 - Θ($n^{2}$ + k). Equally spaced half-grids admit a much cheaper cover of k(n-1) hyperplanes, so the nontrivial constants come from the generic geometry. For conical grids of arbitrary shape the paper proves a universal lower bound of nk(1 - 1/e - O(1/n)), and for half-rectangular grids with one-covering it gives the exact formula n - ceil((n-m)y0/(m-1)) - 1 when the missing point has height y0.","pith_inferences":["The pattern 1 + 1/2 + ... + 1/(d-1) + 2/d^2, which the authors conjecture for general d, would give a 4D constant of 47/24 ≈ 1.958; the same dual-weighting construction should be testable on random 4D half-grids for small n.","The exact formula's independence from x0 suggests the horizontal position of the missing point is irrelevant for one-coverings of half-rectangular grids; if this extends to higher multiplicities, it would simplify the general problem.","The failure of genericity on equally spaced grids lowers the covering number to k(n-1); an intermediate regime of sparse collinearities might interpolate between these extremes, but the paper does not address it.","Equal-spaced half-grids are the pathological case here; because random coordinates give generic half-grids with probability 1, the constants 3/2 and 31/18 describe a typical triangular array rather than a specially constructed one."],"forward_implications":["For generic planar half-grids, the asymptotic covering factor is 3/2 per point per multiplicity layer, independent of n.","In three dimensions the factor is 31/18 ≈ 1.722, smaller than the full-grid factor 11/6 ≈ 1.833, showing that cutting a grid along a diagonal genuinely changes the answer.","The construction yields an explicit k-fold cover for every k by repeating a base cover and adding axis-parallel planes for the remainder, so the O(n^2+k) error term is controlled.","For a single cover of a half-rectangular grid, the exact number of lines depends only on the vertical coordinate of the missing point, not its horizontal coordinate.","The conical-grid bound gives a universal linear lower bound of about 0.632 nk for any triangular arrangement of points."],"supporting_citations":[{"why":"Supplies the base theorem that covering an n1 by ... by nd grid while missing one point needs sum_i(|S_i|-1) hyperplanes, which Theorem 1.3 builds on.","marker":"[2]"},{"why":"Provides the multiplicity version of the Alon-Furedi theorem for grids, the benchmark against which half-grid constants are compared.","marker":"[3]"},{"why":"Gives the triangular-grid lower bound 2nk/3 - O(k) and the front-face weighting scheme that the 3D lower bound adapts.","marker":"[4]"},{"why":"Supplies the LP-duality weighting method and the generic full-grid asymptotics that the half-grid results generalize.","marker":"[6]"},{"why":"Provides the almost-k-cover argument for hypercubes and the full-grid asymptotic comparison used in the introduction.","marker":"[11]"}],"fun_headline_variants":["Generic half-grids: exact line and plane cover numbers","Corners cut: half-grids need 3/2 lines, 31/18 planes","Half-grid covering tight: 3/2 nk lines, 31/18 nk planes","Generic half-grid covers: 3nk/2 lines, 31nk/18 planes","Half-grids: sharp constants 3/2 and 31/18 for covers"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The sharp bounds hold only for generic half-grids: no line in 2D, or plane in 3D, that is not axis-parallel contains more than two or three points, respectively, of the weighted part of the grid; if many points are collinear, the covering number drops to k(n-1).","fun_headline_variants_meta":{"raw":{"variants":["Generic half-grids: exact line and plane cover numbers","Corners cut: half-grids need 3/2 lines, 31/18 planes","Half-grid covering tight: 3/2 nk lines, 31/18 nk planes","Generic half-grid covers: 3nk/2 lines, 31nk/18 planes","Half-grids: sharp constants 3/2 and 31/18 for covers"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000598,"raw_usage":{"total_tokens":2883,"prompt_tokens":1119,"completion_tokens":1764,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":735,"completion_tokens_details":{"reasoning_tokens":1653}},"tokens_in":735,"tokens_out":1764,"duration_ms":15379,"temperature":1.0,"reasoning_tokens":1653,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T18:35:40.979450+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a generic half-grid with n=6 in the plane and k=4, compute the true minimum number of lines by exhaustive integer programming over all lines determined by pairs of grid points, and check whether any cover uses fewer than 3*6*4/2 - 2*4 = 28 lines; a cover with 27 lines would refute the lower bound. In 3D, check whether the proposed dual weighting is feasible by testing every plane not through the origin: if any plane has total weight exceeding k, the lower-bound argument fails.","supporting_citations":[{"cited_title":"Alon and Z","cited_arxiv_id":null,"evidence_quote":"Supplies the base theorem that covering an n1 by ... by nd grid while missing one point needs sum_i(|S_i|-1) hyperplanes, which Theorem 1.3 builds on."},{"cited_title":"Ball and O","cited_arxiv_id":null,"evidence_quote":"Provides the multiplicity version of the Alon-Furedi theorem for grids, the benchmark against which half-grid constants are compared."},{"cited_title":"Covering triangular grids with multiplicity","cited_arxiv_id":"2307.13257","evidence_quote":"Gives the triangular-grid lower bound 2nk/3 - O(k) and the front-face weighting scheme that the 3D lower bound adapts."},{"cited_title":"Bishnoi, S","cited_arxiv_id":null,"evidence_quote":"Supplies the LP-duality weighting method and the generic full-grid asymptotics that the half-grid results generalize."},{"cited_title":"Clifton and H","cited_arxiv_id":null,"evidence_quote":"Provides the almost-k-cover argument for hypercubes and the full-grid asymptotic comparison used in the introduction."}],"review_version":1}