CS Paper Radar

Polynomials with restricted support and maximal zeros on a finite Cartesian set

Dipak K. Bhunia, Eduardo Camps-Moreno, Ignacio GarcÍa-Marco, Hiram H. López, Irene Márquez-Corbella

cs.IT math.ACmath.NT ·submitted 2026-10-05 05:08 UTC · v1
theory

Abstract

Given a finite Cartesian set $S=X \times Y$ and a decreasing set of monomials $\mathcal M$, we call extremal polynomials for $\mathcal M$ over $S$ those that have the maximum number of zeros in $S$ and whose support belongs to $\mathcal M$. Coordinate factorizations give a family of extremal polynomials; we call them canonical. If $\max(\mathcal M)$, taken with respect to divisibility, is a single monomial, all extremal polynomials are canonical. If $|\max(\mathcal M)|=2$, either all extremal polynomials are canonical, or the problem reduces to the case where $\max(\mathcal M)=\{x^{d_x},y^{d_y}\}$. In the latter case, we prove that the existence of noncanonical extremal polynomials depends on finding families of subsets whose elementary symmetric functions agree. This condition is more restrictive than the classical Prouhet--Tarry--Escott problem, which asks for two sets whose elementary symmetric functions agree. We determine the number of triples $(X, Y, h)$, where $h$ is a quadratic noncanonical extremal polynomial. We apply extremal polynomials to coding theory via minimum-weight codewords.

Closest papers

Nearest neighbours by meaning across the whole index.

New bounds for the support of input-output equations in differential-algebraic systems

cs.SC math.AG ·2026-09-03 ·Gabriela Jeronimo, Leonardo Lanciano
theory similarity 0.61
Abstract · 26 pages

Given a polynomial dynamical system $\mathbf{x}'=\mathbf{f}(\mathbf{x},\mathbf{u})$ together with an observation function $y=g(\mathbf{x},\mathbf{u})$, where $\mathbf{x}=(x_1,\ldots,x_n)$, $\mathbf{u}=(u_1,\ldots,u_m)$ and $y$ are differential variables, and $\mathbf{f}=(f_1,\ldots,f_n)$, $g$ are polynomials with coefficients in a differential field, we study the problem of determining a minimal polynomial differential equation satisfied by the inputs $\mathbf{u}$ and the output $y$ which follows as a differential consequence of the system. We provide a characterization of a finite superset of the set of monomials appearing with non-zero coefficients in this input-output equation. Specifically, we establish an upper bound for the degree of the minimal polynomial and a family of inequalities that define a polytope containing its Newton polytope. These results extend recent work by Mukhina and Pogudin for systems with constant parameters, and enable the use of evaluation-interpolation techniques for the efficient computation of such eliminant polynomials.

0.30

When Are Monomial Symmetric Polynomials Hard?

cs.CC cs.SCmath.CO ·2026-10-18 ·Markus Bläser, Radu Curticapean, Sagnik Dutta, Gorav Jindal
top venue similarity 0.60
Abstract · 20 pages, 3 figures. Accepted at SODA 2027

For a partition $\boldsymbolλ = (λ_1,\ldots,λ_r)$ and $n\ge r$, the monomial symmetric polynomial is defined as $$m_{\boldsymbolλ}(x_1,\ldots,x_n) := \sum x_{i_1}^{λ_1} x_{i_2}^{λ_2} \cdots x_{i_r}^{λ_r},$$ where the sum ranges over all distinct monomials obtained by assigning the parts of $\boldsymbolλ$ to pairwise distinct variables. We establish an almost-complete dichotomy for the complexity of the monomial symmetric polynomials $m_{\boldsymbolλ}$: If a family of partitions contains polynomially many distinct parts, then the corresponding monomial symmetric polynomials (on sufficiently many variables) are VNP-complete. If the number of distinct parts is constant, the family admits polynomial-size circuits. Thus the only remaining gap concerns the intermediate regime where the number of distinct parts grows subpolynomially. As part of our proof, we use combinatorial properties of matching polynomials to establish VNP-hardness of the perfect matching polynomial for blow-up graphs; these are graphs with non-generic edge-weights that are obtained by "blowing up" a smaller graph. We reduce these matching polynomials to monomial-symmetric polynomials by combining classical techniques from algebraic complexity theory with structural properties of Sidon sets.

0.72

Degree profiles of uniform polynomial consequences: Linear lower bounds for Nullstellensatz and Polynomial Calculus

cs.CC cs.LOmath.LO ·2026-11-05 ·Søren Riis
similarity 0.55
Abstract · 78 pages. Tutorial, Lean formalisation and verification records: https://doi.org/10.5281/zenodo.23965838

This paper proves asymptotically optimal linear degree lower bounds for Nullstellensatz and Polynomial Calculus, yielding a four-way polynomial-versus-exponential proof-size classification for uniform polynomial consequences over fields of positive characteristic. The size bounds use full, explicit coefficient lists, including zeros. Apart from a fixed finite initial range, exactly one of four cases occurs: $\mathrm T_1$, bounded degree; $\mathrm T_2$, degree at least linear in the universe size $n$; $\mathrm T_3$, constant degree on some residue classes and at least linear degree on the others; or $\mathrm T_4$, infinitely many recurring finite degrees, with bounded-degree subsequences and finite $Ω(n)$ peaks at arbitrarily large sizes. Thus the size patterns are polynomial bounds, exponential lower bounds, a periodic mixture, or polynomial subsequences with finite exponential peaks, respectively. Underivable targets have degree $\infty$, and both proof systems assign the same type. The result strengthens my 2008--2009 refutation classification and extends it to uniform consequences. The proof uses degree-preserving lifting with onset and period bounds linear in the degree. A common $p$-adic hardness spectrum describes the four types topologically. Distinguishing any two types is undecidable already for refutations. The linear degree bounds, four-way classification and pairwise undecidability results have been formalised and verified in Lean. The Lean formalisation, verification records and an accompanying tutorial are available in the supporting materials (https://doi.org/10.5281/zenodo.23965838).

0.41

Common zeros of homogeneous polynomials and the weight hierarchy of projective Reed-Muller codes

cs.IT math.ACmath.AG ·2026-11-05 ·Rodrigo San-José
theory similarity 0.55
Abstract

We determine the maximum number of common zeros in projective space of any set of linearly independent homogeneous polynomials of the same degree, when the degree is smaller than the cardinality of the finite field. This proves the conjecture of Beelen, Datta, and Ghorpade, resolving a longstanding problem on common zeros and determining the complete weight hierarchy of the corresponding projective Reed-Muller codes. The proof uses Green's hyperplane restriction bound, combined with a footprint argument that reduces the problem to the affine case solved by Heijnen and Pellikaan. Wei duality then determines the hierarchy in sufficiently large degrees, recovering the complete hierarchy in every degree for the projective plane. Finally, we prove an upper bound valid in every degree, and conjecture that it is always sharp.

0.13

Explicit Constructions of Maximum-Cardinality Families of Plateaued Functions with Pairwise Disjoint Walsh Supports

cs.IT ·2026-09-18 ·Chen Wang, Xiaoyan Zhang, Chunming Tang, Zhengchun Zhou
hot direction similarity 0.55
Abstract

Families of plateaued Boolean functions with pairwise disjoint Walsh supports are useful in secondary constructions of cryptographic Boolean functions. Of particular interest are maximum-cardinality families whose members admit no nonzero linear structures. To the best of our knowledge, the previously known general construction attaining both properties is spectral (Hodžić et al., IEEE Trans. Inf. Theory 65(9): 5865--5879, 2019). In that work, explicit algebraic normal forms are not generally provided, and no general method is established for prescribing a common algebraic degree for all family members. In this paper, we present two new explicit algebraic constructions within a unified framework, one based on linear functions and the other on partially linear functions with bent components. Let $p\geq 2$ and $q\geq 0$ satisfy $q<2^p-p-1$, and set $m=p+q$. Both constructions yield maximum-cardinality families of $2^{q+1}$ $(q+1)$-plateaued Boolean functions with pairwise disjoint Walsh supports. No member admits a nonzero linear structure, and every member has an explicit generalized Maiorana--McFarland representation. The first construction produces functions in $m+p+1$ variables and realizes any prescribed common algebraic degree $3\leq d\leq p+1$, provided that $q<\sum_{i=2}^{d-1}\binom{p}{i}$; its maximum attainable degree $p+1$ is optimal. The second construction produces functions in $n+p+1$ variables, where $n>m$ and $n-m$ is even, and realizes any prescribed common algebraic degree $3\leq d\leq p+(n-m)/2$, provided that $q<\sum_{i=2}^{\min\{d-1,p\}}\binom{p}{i}$; its maximum attainable degree $p+(n-m)/2$ is next-to-optimal.

0.34

A Hyperplane Bound and Ward's Divisibility Conjecture

cs.IT ·2026-10-19 ·Guanghui Zhang
theoryhot direction similarity 0.53
Abstract · 31 pages

Let $q=p^f$, where $p$ is prime. We prove that every $q$-ary linear code meeting the Griesmer bound, with positive dimension and minimum distance $d\ge1$, is $p^{\max\{0,ν_p(d)-f+1\}}$-divisible, as asserted in Ward's conjecture. Arbitrary projective column multiplicities are allowed. The geometric ingredient is a bound independent of dimension: a nonzero scalar-invariant function $F:\mathbb{F}_q^k\to\mathbb{F}_p$, with $F(0)=0$ and prime-field algebraic degree at most $(f+s)(p-1)$, vanishes identically on at most $p^s(q-1)$ linear hyperplanes when $0\le s<f$. A truncated digit-sum inequality forces selected coefficient polynomials to be homogeneous of ordinary degree less than $q$. Weighted moments on a projective line then bound their linear factors, while a second-moment argument handles the complementary support configuration. An elementary finite-difference calculation supplies the degree bound for divided weight residues. Endpoint shortenings prove the basic divisibility layers; endpoint lifting, a surjective linear functional, and residual-code induction extend the argument to every valuation. We include the proofs of the classical ingredients, identify their sources, and distinguish the present argument from an earlier reported unpublished proof.

0.52

Extremal character spectra of finite projective systems

cs.IT math.CO ·2026-10-30 ·Shitao Li, Yang Li, Gaojun Luo
theory similarity 0.53
Abstract

Let $\mathcal M$ be a finite spanning multiset of points in ${\rm PG}(k-1,q)$, and let ${\rm Char}_{\mathcal M}$ be its character function. For $1\le r\le k$, we study the maximum number of distinct values attained by ${\rm Char}_{\mathcal M}$ on the codimension-$r$ flats under a total-multiplicity budget. The spectrum is subject to two natural upper bounds, whose extremal cases lead respectively to $r$-maximum character spectrum ($r$-MCS) and $r$-full character spectrum ($r$-FCS) systems. We establish the existence of $r$-FCS systems in a broad parameter range, and solve the size-constrained extremal problem completely when $r=k-1$, including the minimum-cost multiplicity profiles. For $1\le r<k$, put $M_r=\qbinom{k}{r}$ and $B_r=\qbinom{k-1}{r}$. The minimum size $ν_r(k,q)$ of an $r$-MCS system satisfies \[\left\lceil\frac{\binom{M_r}{2}}{B_r}\right\rceil\le ν_r(k,q)\le \binom{M_r-1}{2}+\frac{q^k-q^{k-r}}{q-1}.\] The upper bound is at most $\binom{M_r}{2}$, strictly less when $r\le k-2$, and exact when $r=k-1$. Its proof applies positive additive labelings to the complement of one flat, whose trace is empty while all remaining traces are distinct. For $r=1$, we improve the known upper bounds on the minimum length of such systems. We also develop global moment identities and local flat-incidence bounds that impose strong structural constraints on large character spectra. Under the projective-system correspondence, complementary character spectra are the support-weight spectra of $r$-dimensional subcodes.

0.34

Block Sensitivity and Certificate Complexity of Rotation Symmetric Boolean Functions

cs.CC math.COcs.DM ·2026-10-12 ·Yuan Li, Jing Zhang
theory similarity 0.52
Abstract · Version 2, 44 pages

We investigate block sensitivity and certificate complexity of monomial rotation-symmetric Boolean functions, obtaining exact formulas and structural classifications for several families. For odd-degree monomial rotation-symmetric functions, the equality $s(f)=n$ established in our earlier work yields $bs(f)=C(f)=n$. For quadratic monomial rotation-symmetric functions, we determine both measures completely and prove that block sensitivity equals certificate complexity. For consecutive quartic monomials, we determine sensitivity, block sensitivity, and certificate complexity in every residue class of the number of variables. Our principal result is an exact global block-sensitivity formula for consecutive monomials of every even degree $d\ge4$. Writing $n=q(d+2)+ρ$, where $0\leρ<d+2$ and $q\ge\max\{2,d/2-1\}$, we prove \[ bs(F_{d,n})=n-\min\left\{\left\lceil\fracρ{2}\right\rceil,d+2-ρ\right\}. \] We also establish the corresponding sensitivity formula by a self-contained argument, yielding arbitrarily large gaps between sensitivity and block sensitivity as the degree varies. For certificate complexity, we obtain exact pointwise formulas for structured run-and-gap configurations and establish additional global equalities, including $C(F_{6,8q+5})=bs(F_{6,8q+5})=8q+2$ for $q\ge2$. Our methods combine cyclic run decomposition, parity arguments, explicit sensitive-block constructions, and constant-subcube certificates. The exact global certificate complexity for arbitrary even degrees remains open.

0.43