Paper 2026/1114

Counterexamples to the Low-Norm Nullstellensatz Hypothesis

Abstract

We give several examples of families of polynomials $p_1, ... , p_t \in \mathbb R[x_1, ... , x_n]/\langle x_i^d - 1\rangle_i$ on which the Low-Norm Nullstellensatz Hypothesis of [Devadas-Hopkins-Kalai-Kothari-Lombardi-Mathialagan, STOC 2026] fails to hold. That is, we prove the existence of polynomials $f \in \langle p_1, ... , p_t\rangle$ with coefficient $L^1$ norm $||f||_1 = 1$ but such that every decomposition $f = \sum_i p_i \cdot q_i$ has cost $\sum_i ||q_i||_1 = 2^{\Omega(n)}$. Our examples include one with $d=2$, the regime originally studied by [Devadas et al.], as well as generalizations that would also have sufficed for their purposes. Our counterexamples highlight an important class of polynomials for (potentially) falsifying the LNNH: for prime $d$, functions $f(x) = f_C(x)=\frac 1 {|C|}\sum_{c\in C} x^c$ that are indicator functions for the input $x \in \mu_d^n\simeq \mathbb Z_d^n$ belonging to a linear subspace $C^\bot \subset \mathbb Z_d^n$, or more generally a coset $C^\bot + \sigma$.