REVIEW 3 major objections 4 minor 17 references
Covering half-grids with lines and planes
T0 review · 3 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash
Pith's one-line read For generic half-grids, the minimum k-fold line cover is asymptotically 3nk/2, and the plane cover in 3D is 31nk/18.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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).
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [§3.2, lower-bound proof of Theorem 3.5] 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.
- [Theorem 3.5 / Theorem 1.5 statement] 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.
- [§2, Corollary 3 proof] 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.
minor comments (4)
- [§3.2, upper-bound construction, type 3 planes] 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'.
- [§1, Introduction] The name 'Cayely-Bacharach' should be 'Cayley-Bacharach'.
- [§3.1, LP formulation] 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.
- [Definition 5] 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.
Circularity Check
No significant circularity: the proofs derive new bounds from stated LP duals, explicit constructions, and external theorems; self-citations are methodological only.
full rationale
The paper's central results are not circular. The lower bounds in Theorems 1.1 and 1.2 are obtained from an explicit counting lemma (Lemma 1) applied to conical and half-grids, with no parameter fitted to the claimed answer. The 2D generic bound (Theorem 1.4) is proved by an explicit dual LP weighting stated in the paper, and the validity of that weighting is checked directly against the genericity definition; the citation to [6] is only for the standard LP-duality framework, which the paper also restates. The 3D upper bound is a concrete plane construction, and the 3D lower bound imports a weighting from [4], an external paper by different authors, scaling it by a constant; this is independent support rather than a self-citation. The self-citations to [5] and [6] concern methodology and terminology, not the truth of the main theorems, so they are not load-bearing. The geometric concern that a plane need not intersect the index-simplex front face in a line is a potential correctness gap in the 3D lower-bound argument, not a circularity: the conclusion is not assumed among the inputs, and the genericity condition is a stated hypothesis rather than a renamed version of the result. Accordingly, no step in the derivation reduces by construction to its own input.
Assumptions & free parameters
free parameters (2)
- Threshold fractions in 3D construction (2n/3, n/3) =
2/3, 1/3
- Dual weighting constants (1/2 in 2D; 1/3, 1/6, 3/n^2 in 3D) =
1/2, 1/3, 1/6, 3/n^2
assumptions (5)
- standard math Alon-Furedi theorem: covering an s x t grid while missing one point requires s+t-2 lines
- standard math Ball-Serra multiplicity theorem for grids
- standard math Linear programming duality for covering ILPs
- domain assumption Genericity of half-grids (Definitions 4 and 5)
- standard math Harmonic series estimates (H_n > ln n + gamma, H_n < ln n + gamma + 1/(2n))
Cite this review
Pith. "Pith review of Covering half-grids with lines and planes." pith.science (2026). https://pith.science/paper/JADOHYKC
@misc{pith2026250111156,
author = {Pith},
title = {Pith review of: Covering half-grids with lines and planes},
year = {2026},
howpublished = {\url{https://pith.science/paper/JADOHYKC}},
note = {Machine review of arXiv:2501.11156}
}
abstract
We study hyperplane covering problems for finite grid-like structures in $\mathbb{R}^d$. We call a set $\mathcal{C}$ of points in $\mathbb{R}^2$ a conical grid if the line $y = a_i$ intersects $\mathcal{C}$ in exactly $i$ points, for some $a_1 > \cdots > a_n \in \mathbb{R}$. We prove that the number of lines required to cover every point of such a grid at least $k$ times is at least $nk\left(1-\frac{1}{e}-O(\frac{1}{n}) \right)$. If the grid $\mathcal{C}$ is obtained by cutting an $m \times n$ grid of points in half along one of the diagonals, then we prove the lower bound of $mk\left(1-e^{-\frac{n}{m}}-O(\frac{n}{m^2})\right)$. In general, we call a grid obtained by cutting a grid in $\mathbb{R}^d$ along one of the diagonals a half-grid. Motivated by the Alon-F\"uredi theorem on hyperplane coverings of grids that miss a point and its multiplicity variations, we study the problem of finding the minimum number of hyperplanes required to cover every point of an $n \times \cdots \times n$ half-grid in $\mathbb{R}^d$ at least $k$ times while missing a point $P$. For almost all such half-grids, with $P$ being the corner point, we prove asymptotically sharp upper and lower bounds for the covering number in dimensions $2$ and $3$. For $k = 1$, $d = 2$, and an arbitrary $P$, we determine this number exactly by using the polynomial method bound for grids.
Reference graph
Works this paper leans on
-
[4]
Covering triangular grids with multiplicity
A. Basit, A. Clifton, and P. Horn. Covering triangular gr ids with multiplicity. arXiv preprint arXiv:2307.13257, 2023
work page Pith review arXiv 2023
-
[1]
N. Alon. Combinatorial Nullstellensatz. Combin. Probab. Comput. , 8(1–2):7–29, 1999
work page 1999
-
[2]
N. Alon and Z. F¨ uredi. Covering the cube by affine hyperpla nes. European J. Combin. , 14(2):79–83, 1993
work page 1993
-
[3]
S. Ball and O. Serra. Punctured combinatorial Nullstell ens¨ atze.Combinatorica, 29(5):511– 522, 2009
work page 2009
-
[5]
A. Bishnoi, S. Boyadzhiyska, S. Das, and T. M´ esz´ aros. S ubspace coverings with multiplic- ities. Combin. Probab. Comput. , 32(5):782–795, 2023
work page 2023
-
[6]
A. Bishnoi, S. Boyadzhiyska, Y. den Bakker, and S. Das. Co vering grids with multiplicity. Combinatorial Theory , 3(3), 2023
work page 2023
-
[7]
A. Blokhuis, A. E. Brouwer, and T. Sz˝ onyi. Covering all p oints except one. J. Algebraic Combin., 32(1):59–66, 2010
work page 2010
- [8]
Show all 17 references
-
[9]
A. E. Brouwer and A. Schrijver. The blocking number of an a ffine space. J. Combinatorial Theory Ser. A , 24(2):251–253, 1978
1978
-
[10]
A. A. Bruen. Polynomial multiplicities over finite field s and intersection sets. J. Combin. Theory Ser. A , 60(1):19–33, 1992
1992
-
[11]
Clifton and H
A. Clifton and H. Huang. On almost k-covers of hypercubes. Combinatorica, 40(4):511–526, 2020
2020
-
[12]
Eisenbud, M
D. Eisenbud, M. Green, and J. Harris. Cayley–Bacharach theorems and conjectures. Bull. Amer. Math. Soc. , 33(3):295–324, 1996
1996
-
[13]
R. E. Jamison. Covering finite fields with cosets of subsp aces. J. Combinatorial Theory Ser. A , 22(3):253–266, 1977. 9
1977
-
[14]
R. Karasev. Residues and the combinatorial Nullstelle nsatz. Period. Math. Hungar., 78:157– 165, 2019
2019
-
[15]
Komj´ ath
P. Komj´ ath. Partitions of vector spaces. Period. Math. Hungar. , 28(3):187–193, 1994
1994
-
[16]
Sauermann and Y
L. Sauermann and Y. Wigderson. Polynomials that vanish to high order on most of the hypercube. J. Lond. Math. Soc. (2) , 106(3):2379–2402, 2022
2022
-
[17]
Verlinde
L. Verlinde. Polynomial methods for grid covering prob lems. Mas- ter’s Thesis , Delft University of Technology, 2024. Available at: https://repository.tudelft.nl/record/uuid:6bd5107d- dead-4c26-9393-5b8952fe98a9. 10
2024
Reviewed August 10, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.