Score: 0

Shifted Partial Derivative Polynomial Rank and Codimension

Published: December 23, 2025 | arXiv ID: 2512.20729v1

By: Darren J. Edwards

Shifted partial derivative (SPD) methods are a central algebraic tool for circuit lower bounds, measuring the dimension of spaces of shifted derivatives of a polynomial. We develop the Shifted Partial Derivative Polynomial (SPDP) framework, packaging SPD into an explicit coefficient-matrix formalism. This turns shifted-derivative spans into concrete linear-algebraic objects and yields two dual measures: SPDP rank and SPDP codimension. We define the SPDP generating family, its span, and the SPDP matrix M_{k,l}(p) inside a fixed ambient coefficient space determined by the (k,l) regime, so rank is canonical and codimension is a deficit from ambient fullness. We prove structural properties needed for reuse: monotonicity in the shift/derivative parameters (with careful scoping for |S|=k versus |S|<=k conventions), invariance under admissible variable symmetries and basis changes, and robustness across standard Boolean/multilinear embeddings. We then give generic width-to-rank upper-bound templates for local circuit models via profile counting, separating the model-agnostic SPDP toolkit from additional compiled refinements used elsewhere. We illustrate the codimension viewpoint on representative examples.

Category
Computer Science:
Computational Complexity