pith. sign in

arxiv: 2603.14262 · v2 · submitted 2026-03-15 · 🧮 math.CO

Covering Hypercube mB^n

Zihao Huang , Miao Wang , Suijie Wang This is my paper

Pith reviewed 2026-05-15 11:44 UTC · model grok-4.3

classification 🧮 math.CO
keywords m-ary hypercubehyperplane coveringcombinatorial nullstellensatzvanishing multiplicityAlon-Furedi theoremLagrange inversionpolynomial degree boundcovering number
0
0 comments X

The pith

A tight lower bound on the degree of polynomials vanishing to multiplicity k on mB^n except at the origin determines exact hyperplane covering numbers f_m(n,k) for k=1 and 2.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper extends the Alon-Furedi theorem and its multiplicity version by Sauermann and Wigderson from the Boolean cube to the general m-ary hypercube mB^n = {0,1,...,m}^n. It proves a sharp lower bound on the total degree of any polynomial that vanishes with multiplicity at least k at every nonzero point of mB^n while having multiplicity strictly less than k at the origin. This bound is tight, as shown by an explicit hyperplane construction, and is applied to compute the minimal number of hyperplanes f_m(n,k) needed to achieve the k-fold covering of all nonzero points. The proofs also rely on the Lagrange inversion formula to handle the resulting enumerative identities.

Core claim

Any polynomial that vanishes with multiplicity at least k at all points of mB^n excluding the origin and with multiplicity less than k at the origin must have total degree at least an explicit quantity depending on m, n and k. This lower bound is achieved by polynomials arising from products of linear forms that define suitable collections of hyperplanes, yielding the exact values of the covering number f_m(n,k) for k=1 and k=2 together with matching upper and lower bounds for k greater than or equal to 3 when n is at least k-1.

What carries the argument

The extended Combinatorial Nullstellensatz for mB^n that converts a prescribed multiplicity vanishing condition at all nonzero lattice points (and lower multiplicity at the origin) into a sharp lower bound on total polynomial degree.

If this is right

  • The covering number f_m(n,1) equals an explicit closed-form expression in m and n derived from the degree bound.
  • The covering number f_m(n,2) likewise equals an explicit closed-form expression in m and n.
  • For every k greater than or equal to 3 and n at least k-1, the covering number f_m(n,k) is sandwiched between two explicit functions of m, n and k.
  • The new hyperplane construction supplies matching upper bounds that realize the lower bounds for k=1 and k=2.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same multiplicity-to-degree conversion may apply directly to non-uniform multiplicity patterns across different points of the grid.
  • The appearance of the Lagrange inversion formula indicates that minimal coverings can be counted via generating functions for lattice paths or trees.
  • Analogous degree bounds are likely to hold for other product spaces such as rectangular grids with unequal side lengths.

Load-bearing premise

The lower bound on polynomial degree coming from the extended nullstellensatz is achieved by the explicit hyperplane construction when k equals 1 or 2.

What would settle it

A single explicit polynomial of degree strictly below the claimed bound that still vanishes to multiplicity at least k at every nonzero point of mB^n while having multiplicity less than k at the origin would disprove the lower bound.

Figures

Figures reproduced from arXiv: 2603.14262 by Miao Wang, Suijie Wang, Zihao Huang.

Figure 1
Figure 1. Figure 1: Logical structure of proofs. 2 Proof of Theorem 1.4 This section is devoted to proving Theorem 1.4, whose proof relies on Ball and Serra’s Punctured Combinatorial Nullstellensatz (see [3, Theorem 4.1]). We begin by recalling their result after introducing some necessary notation. Let F be a field and let f be a nonzero polynomial in F[x1, . . . , xn]. We say that a = (a1, . . . , an) ∈ F n is a zero of mul… view at source ↗
read the original abstract

A celebrated result of Alon and F\"{u}redi gives a tight lower bound on the number of hyperplanes required to cover all points of the Boolean cube $B^n$ except the origin $\bm{0}$. Recent breakthroughs by Sauermann and Wigderson generalized this to the case where all points of $B^n \setminus \{\mathbf{0}\}$ are covered with multiplicities at least $k$. In this paper, we further extend their result by replacing the Boolean cube with the general hypercube $mB^n = \{0, 1, \dots, m\}^n$. \vspace{2mm} Let $f_m(n, k)$ denote the minimum number of hyperplanes required to cover every point of $mB^n \setminus \{\mathbf{0}\}$ at least $k$ times while leaving the origin uncovered. Our primary contribution is a sharp extension of the Sauermann--Wigderson Combinatorial Nullstellensatz to the setting of $mB^n$. We determine a tight lower bound for the degree of polynomials that vanish with multiplicity at least $k$ at all points of $mB^n \setminus \{\mathbf{0}\}$ and have multiplicity less than $k$ at the origin. As an application, we establish the exact values $f_m(n, k)$ for $k=1,2$ and provide upper and lower bounds for $f_m(n, k)$ when $k \ge 3$ and $n\ge k-1$. The proofs involve a new construction of hyperplanes and a surprisingly elegant application of the Lagrange inversion formula in enumerative combinatorics.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper extends the Alon-Füredi theorem and the Sauermann-Wigderson generalization of the Combinatorial Nullstellensatz from the Boolean cube B^n to the grid mB^n = {0,1,...,m}^n. It defines f_m(n,k) as the minimum number of hyperplanes that cover every nonzero point of mB^n with multiplicity at least k while leaving the origin uncovered. The central contribution is a sharp lower bound on the degree of polynomials vanishing to multiplicity k on mB^n excluding the origin but to multiplicity less than k at the origin; this bound is applied to obtain exact values of f_m(n,k) for k=1 and k=2, together with upper and lower bounds for k≥3 (when n≥k-1), via an explicit hyperplane construction and an application of the Lagrange inversion formula.

Significance. If the generalized nullstellensatz and the matching construction hold, the work provides a natural and tight extension of a major line of results in combinatorial nullstellensatz and covering problems to arbitrary grid sizes. The exact determinations for k=1,2 and the use of Lagrange inversion to obtain closed forms are concrete strengths that would make the paper a useful reference for further work on multiplicity coverings and polynomial methods over grids.

major comments (2)
  1. The precise statement of the generalized Combinatorial Nullstellensatz for mB^n (including the exact form of the degree lower bound) is load-bearing for the exact values of f_m(n,k). Please state it explicitly, including any dependence on m, and verify that the hyperplane construction saturates the bound for k=1 and k=2 in the applications section.
  2. The verification that the explicit construction meets the lower bound (rather than merely providing an upper bound) must be checked for all m and n in the claimed regimes; the current sketch leaves open whether the Lagrange inversion step produces an integer count that exactly matches the degree bound for every parameter.
minor comments (2)
  1. The abstract contains a stray LaTeX command (vspace); remove it for the final version.
  2. Notation for the grid mB^n and the function f_m(n,k) is introduced clearly in the abstract but should be restated at the beginning of the main text for readers who start there.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address the major comments point by point below and will incorporate clarifications in the revised manuscript.

read point-by-point responses

  1. Referee: The precise statement of the generalized Combinatorial Nullstellensatz for mB^n (including the exact form of the degree lower bound) is load-bearing for the exact values of f_m(n,k). Please state it explicitly, including any dependence on m, and verify that the hyperplane construction saturates the bound for k=1 and k=2 in the applications section.

    Authors: We agree that the precise statement of the generalized Combinatorial Nullstellensatz, including the explicit degree lower bound and its dependence on m, should be stated clearly. In the revised manuscript we will add this statement as a standalone theorem early in the paper. We will also expand the applications section to include a direct verification that the hyperplane construction saturates the bound for k=1 and k=2, confirming that the multiplicities match exactly. revision: yes

  2. Referee: The verification that the explicit construction meets the lower bound (rather than merely providing an upper bound) must be checked for all m and n in the claimed regimes; the current sketch leaves open whether the Lagrange inversion step produces an integer count that exactly matches the degree bound for every parameter.

    Authors: We acknowledge the need for explicit verification of integrality and exact matching. The closed-form expression obtained via Lagrange inversion is an integer for all positive integers m and n (by its combinatorial interpretation as a counting function) and equals the degree lower bound in the regimes where we claim exact values of f_m(n,k). In the revision we will supply the full expansion of the inversion step together with a short argument confirming integrality and equality for k=1 and k=2 across all relevant m and n. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation extends the external Sauermann-Wigderson Combinatorial Nullstellensatz to mB^n via a new proof, derives the lower bound on polynomial degree directly from this extension, and matches it with an independent explicit hyperplane construction for k=1 and k=2. The Lagrange inversion formula is applied as a standard enumerative tool with no parameter fitting or self-referential definitions. No load-bearing self-citations, ansatzes smuggled via prior work, or reductions of predictions to fitted inputs appear in the chain; the central claims remain self-contained against the stated assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on an unproved extension of the Combinatorial Nullstellensatz to the m-ary setting together with the correctness of the hyperplane construction; no free parameters or new entities are introduced.

axioms (1)
  • domain assumption A sharp Combinatorial Nullstellensatz holds for polynomials over mB^n that controls multiplicity at the origin versus all other points.
    Invoked to obtain the tight lower bound on polynomial degree that is then matched by the construction.

pith-pipeline@v0.9.0 · 5596 in / 1366 out tokens · 67313 ms · 2026-05-15T11:44:20.127188+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

  1. [1]

    Alon, Combinatorial Nullstellensatz, Combin

    N. Alon, Combinatorial Nullstellensatz, Combin. Probab. Comput.8(1999), 7–29

    work page 1999

  2. [2]

    Alon and Z

    N. Alon and Z. F¨uredi, Covering the cube by affine hyperplanes, Eur. J. Combin.14 (1993), 79–83

    work page 1993

  3. [3]

    Ball and O

    S. Ball and O. Serra, Punctured combinatorial Nullstellens¨atze, Combinatorica29 (2009), 511–522

    work page 2009

  4. [4]

    Batzaya and G

    G. Batzaya and G. Bayarmagnai, A generalized combinatorial Nullstellensatz for multisets, Eur. J. Combin.83(2020)

    work page 2020

  5. [5]

    Bishnoi, P

    A. Bishnoi, P. L. Clark, A. Potukuchi, and J. Schmitt, On zeros of a polynomial in a finite grid, Combin. Probab. Comput.27(2018), 310–333

    work page 2018

  6. [6]

    Bukh and T

    B. Bukh and T. -W. Chao, Sharp density bounds on the finite field Kakeya problem, Discrete Anal.26(2021), 1–9

    work page 2021

  7. [7]

    Clifton and H

    A. Clifton and H. Huang, On almost k-covers of hypercubes, Combinatorica40 (2020), 511–526

    work page 2020

  8. [8]

    Z. Dvir, S. Kopparty, S. Saraf, and M. Sudan, Extensions to the method of multi- plicities, with applications to Kakeya sets and mergers, SIAM J. Comput.42(2013), 2305–2328

    work page 2013

  9. [9]

    I. M. Gessel, Lagrange inversion, J. Combin. Theory Ser. A144(2016), 212–249

    work page 2016

  10. [10]

    Hanson and G

    B. Hanson and G. Petridis, Refined Estimates Concerning Sumsets Contained in the Roots of Unity, Proc. Lond. Math. Soc.122(2021), 353–358

    work page 2021

  11. [11]

    Komj ´ath, Partitions of vector spaces, Period

    P. Komj ´ath, Partitions of vector spaces, Period. Math. Hungar.28(1994), 187–193

    work page 1994

  12. [12]

    K´os and L

    G. K´os and L. R´onyai, Alon’s Nullstellensatz for multisets, Combinatorica32(2012), 589–605

    work page 2012

  13. [13]

    G. K´os, T. M´esz´aros, and L. R´onyai, Some extensions of Alon’s Nullstellensatz, Publ. Math. Debrecen79(2011), 507–519

    work page 2011

  14. [14]

    Sauermann and Y

    L. Sauermann and Y . Wigderson, Polynomials that vanish to high order on most of the hypercube, J. Lond. Math. Soc.106(3)(2022), 2379–2402. 24 A Supplementary Constructions We present explicit constructions that determine the values of f2(n,3) for n= 2,3,4 . Each construction is specified by a family of hyperplanes along with their respective counts. Reca...

    work page 2022