Oct 2026· Forum of Mathematics, Sigma· Vol 14· 0 citations· 28 references
Abstract
Abstract We obtain upper bounds, independent of the ambient dimension, for the number of realizable zero-nonzero patterns and (over ordered fields) sign conditions of a finite family of polynomials P
$\mathcal P$
script upper P restricted to an algebraic subset V of affine or projective space. The bounds depend only on card(P)
$\mathrm {card}(\mathcal P)$
card left parenthesis script upper P right parenthesis and the degrees of the polynomials in P
$\mathcal P$
script upper P , together with deg(V)
$\deg (V)$
degree left parenthesis upper V right parenthesis and dim(V)
$\dim (V)$
dimension left parenthesis upper V right parenthesis , and not on the dimension of the space in which V is embedded. This feature is particularly useful when V has small intrinsic dimension but is presented in a very high-dimensional ambient space. We describe several applications. First, we extend existing results on bounding the ε
$\varepsilon $
epsilon -entropy of real algebraic varieties. Second, we derive lower bounds (in terms of the number of connected components) for membership testing in semi-algebraic sets in the algebraic computation tree model. Finally, motivated by quantum complexity theory, we introduce additive and multiplicative notions of relative rank in finite-dimensional vector spaces and algebras with respect to a fixed algebraic subset, generalizing the classical notion of tensor rank. We prove a general lower bound on the maximum relative rank of finite subsets with respect to algebraic sets of bounded degree and dimension that is again independent of the ambient dimension. As an illustration, we obtain a quantum analog of Shannon’s classical lower bound. We prove that if Δn
$\Delta _n$
normal upper Delta Subscript n is an algebraic family of allowed gates with dimΔn=poly(n),logdegΔn= poly(n),
$$ \begin{align*}\dim \Delta_n= \mathrm{poly}(n), \qquad \log\deg\Delta_n= \text{ poly}(n),\end{align*} $$
dimension normal upper Delta Subscript n Baseline equals poly left parenthesis n right parenthesis comma log degree normal upper Delta Subscript n Baseline equals poly left parenthesis n right parenthesis comma then some Boolean functions require 2n/poly(n)
$2^n/\text {poly}(n)$
2 Superscript n Baseline divided by poly left parenthesis n right parenthesis gates from Δn
$\Delta _n$
normal upper Delta Subscript n , even when individual gates in Δn
$\Delta _n$
normal upper Delta Subscript n may be highly nonlocal.
We study exact representations of explicit signed modular predicates on $\{-1,1\}^n$ as products of bounded-degree polynomials over prime fields, measured by total variable-occurrence cost. Our main result is an exponential lower bound for products of cubic polynomials. Over $\mathbb F_3$ the proof is self-contained: e...
We study monic irreducible polynomials over $\mathbb{F}_q[T]$ whose non-leading digits, with respect to an arbitrary polynomial base $b(T)$, avoid a prescribed set of forbidden digits. Identifying the digit set with the ring $D=\mathbb{F}_q[T]/(b)$, we obtain an asymptotic formula for the number of such irreducible pol...
We compute top derived products and inverse limits on products of affine lines with doubled origin over $B[s]$, for any nonzero commutative ring $B$. For every $B$-module $M$, the two top obstruction modules fit into an explicit exact sequence and contain $M^{\mathbb N}/M^{(\mathbb N)}$as a natural $B$-module direct su...
If $f$ is a tuple of functions satisfying an algebraic ODE and $P\in{\mathbb C}(x)[f]$, it is common in applications to transcendental number theory to consider upper bounds for the order of zero of $P(x,f)$ at a given point in terms of $\operatorname{deg}_x P,\operatorname{deg}_f P$. Nesterenko introduced a condition...
Let $X$ be a nonsingular projective curve of genus $g\ge2$ over an algebraically closed field of odd characteristic $p$. Giulietti and Korchm\'aros established a quadratic genus bound with constant $900$ forcing zero $p$-rank for curves of even genus. We extend this bound to odd genus: for every $g\ge2$, positive $p$-r...
We give an explicit hitting set of size $\text{poly}(n,d,r)$ for the class of $n$-variate degree-$d$ polynomials whose partial derivative space is bounded by $r$, over any field $\mathbb{F}$ of characteristic zero. In particular, this yields a polynomial sized hitting set for the class of depth-$3$ powering circuits. T...