Shifted Partial Derivative Polynomial Rank and Codimension
Darren J. Edwards · 2025
Read Shifted Partial Derivative Polynomial Rank and Codimension by Darren J. Edwards (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-20729.txt.
Introduction
Darren J. Edwards writes on computational complexity, the study of how much work a problem needs. His tools are shifted partial derivatives, an algebraic method used to prove circuit lower bounds. Those bounds show that certain problems cannot be solved by small circuits.
Edwards packages the method into a framework built around an explicit coefficient matrix. From it he defines two paired measures, rank and codimension. He proves the framework stays stable under changes of variables and standard embeddings. He also gives templates that bound rank from circuit width for local models. The payoff is a reusable toolkit for lower-bound arguments.
Catalog record
| CREATOR | Darren J. Edwards |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 84 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-20729
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Shifted Partial Derivative Polynomial Rank and Codimension Darren J. Edwards Abstract Shifted partial derivative (SPD) methods are a central algebraic tool for proving circuit lower bounds by measuring the dimension of spaces of shifted derivatives of a polynomial. In this paper we develop the Shifted Partial Derivative Polynomial (SPDP) framework, packaging classical SPD methods into an explicit coefficient-matrix formalism. This turns these spaces into concrete linear-algebraic objects and introduces two dual complexity measures: SPDP rank and SPDP codimension. We first define the SPDP generating family, the associated span, and the SPDP matrix M κ , ℓ ( p ) M_{\kappa,\ell}(p) in a fixed ambient coefficient space determined by the ( κ , ℓ ) (\kappa,\ell) regime, so that rank is well-defined and codimension becomes a canonical “deficit from ambient fullness.” We then prove structural properties that make the framework usable as a standalone toolkit: monotonicity in the shift/derivative parameters (with precise scoping for the | S | = κ |S|=\kappa versus | S | ≤ κ |S|\leq\kappa conventions), invariance under admissible variable symmetries and basis changes, and robustness across standard Boolean/multilinear embedding conventions. Next, we give generic width-to-rank upper-bound templates for local circuit models, showing how combinatorial profile counting yields polynomial bounds in logarithmic ( κ , ℓ ) (\kappa,\ell) regimes under the deterministic compiler/diagonal-basis hypothesis. This explicitly separates the model-agnostic SPDP toolkit from additional compiled refinements used in separate work (e.g. Edwards 2025); nothing in this paper relies on those refinements. Finally, we illustrate the codimension viewpoint on representative examples, emphasizing how codimension captures rigidity as the failure of shifted-derivative spans to fill their ambient space. Overall, SPDP provides a clean, self-contained linear-algebraic packaging of shifted partial derivatives that supports both rank-based and deficit-based (codimension) reasoning, and is intended as a reusable reference for algebraic complexity applications. Keywords: Shifted partial derivatives, complexity measures, algebraic methods, rank, codimension 1 Introduction Shifted partial derivatives have become a standard tool in algebraic and Boolean complexity, particularly for proving lower bounds against restricted circuit models [ Nisan and Wigderson 1997 , Kayal 2012 , Gupta et al. 2016 , Kayal and Saha 2016 , Limaye et al. 2024 , Shpilka and Yehudayoff 2010 ] . Most of the literature uses dimension of a shifted partial derivative space as the primary complexity statistic. The present work isolates and formalizes a closely related invariant package—the Shifted Partial Derivative Polynomial (SPDP) framework—with two dual quantities: SPDP rank (dimension) and SPDP codimension (ambient deficit). For an application of these ideas to complexity separations, see Edwards 2025 . Main contributions. This note isolates a clean, self-contained “SPDP toolkit” that can be cited independently of any separation application. • SPDP matrix formalism + dual invariant. We package the shifted partial derivative (SPD) dimension measure as an explicit coefficient matrix M_{\kappa,\ell}(p) whose rank is \Gamma_{\kappa,\ell}(p) , and we introduce the dual quantity \mathrm{codim}_{\kappa,\ell}(p) as the ambient deficit. This makes invariance and monotonicity statements transparent as linear-algebraic properties of M_{\kappa,\ell}(p) . • Robustness and invariances. We prove basis-invariance and permutation-invariance of \Gamma_{\kappa,\ell}(p) and \mathrm{codim}_{\kappa,\ell}(p) under the intended ambient conventions, clarifying the scope of invariance under Boolean/multilinear embeddings. • A width \Rightarrow rank upper-bound schema with a sharp profile count. We formalize a minimal local-width computation model and prove a polynomial Width \Rightarrow Rank bound in the regime \kappa,\ell=\Theta(\log n) and R=C(\log n)^{c} . The key technical bridge is a profile compression lemma showing that the number of realizable interface-anonymous profiles is R^{O(1)} independent of the window length \kappa , avoiding the crude ordered-step count (\log n)^{O(\kappa)} . • Compatibility with the block-partitioned SPDP framework. We record a dictionary relating the unblocked SPDP matrix M_{\kappa,\ell}(p) to the block-partitioned matrix M^{B}_{\kappa,\ell}(p) used in block-local/compiled settings, including the rank comparison \Gamma^{B}_{\kappa,\ell}(p)\leq\Gamma_{\kappa,\ell}(p) . What this paper does We provide (i) a clean definition of SPDP spaces and a canonical SPDP matrix representation; (ii) rank and codimension invariants that are stable under natural transformations; (iii) general properties (monotonicity, invariance, and basic closure lemmas); and (iv) rank upper bounds for broad computational models in a consistent parameter regime, together with codimension formulations that clarify rigidity. What this paper does not do This paper is not a separation claim and does not address barrier frameworks or any global complexity-class consequences. The aim is to establish SPDP rank and codimension as a standalone measure with a rigorous, self-contained development. Application to other work (compiled/block-partitioned SPDP). This note develops SPDP rank and codimension in the unblocked matrix formalism, i.e. via the coefficient matrix M_{\kappa,\ell}(p) and its rank \Gamma_{\kappa,\ell}(p) (and the dual ambient deficit \mathrm{codim}_{\kappa,\ell}(p) ) under a fixed ambient/basis convention. Other work [ Edwards 2025 ] applies a more restrictive compiled variant in which a fixed radius– 1 block partition B is imposed and one takes the rank of a structured restriction M^{B}_{\kappa,\ell}(p) (with \Gamma^{B}_{\kappa,\ell}(p)\leq\Gamma_{\kappa,\ell}(p) ) tailored to block-local compiler transformations. Nothing in the present paper relies on that compiled setting; we include a short dictionary ( 12.1 ) only to align notation. 2 Preliminaries and Notation Fix a base field \mathbb{F} (e.g. \mathbb{Q} or \mathbb{R} ). We work with polynomials f\in\mathbb{F}[x_{1},\dots,x_{n}] representing Boolean functions on \{0,1\}^{n} (via multilinearization or a chosen embedding, made explicit in 3 ). 2.1 Multi-index notation For \alpha=(\alpha_{1},\dots,\alpha_{n})\in\mathbb{N}^{n} , let |\alpha|=\sum_{i}\alpha_{i} and write \partial^{\alpha}=\partial_{x_{1}}^{\alpha_{1}}\cdots\partial_{x_{n}}^{\alpha_{n}} . 2.2 Parameter regime Throughout, we fix parameters (\kappa,\ell) that may depend on n . All theorems in this paper explicitly state which (\kappa,\ell) regime they assume. When helpful, we highlight standard regimes, e.g. \kappa=O(1) with \ell=\mathrm{poly}(n) , or \kappa=\Theta(\log n) with \ell=\Theta(\log n) . No claim in this paper depends on mixing incompatible parameter choices. 3 Polynomial embedding of Boolean functions We record a minimal embedding convention. The reader may substitute an equivalent standard convention; our invariance results show the measure is robust to such choices. Definition 3.1 (Boolean-to-polynomial representation) . Let f:\{0,1\}^{n}\to\{0,1\} . A polynomial representation of f is a polynomial \tilde{f}\in\mathbb{F}[x_{1},\dots,x_{n}] that agrees with f on \{0,1\}^{n} . Unless otherwise stated, we assume \tilde{f} is multilinear (via standard multilinearization modulo (x_{i}^{2}-x_{i}) ). Remark 3.2 . If a non-multilinear representation is used, all SPDP spaces below may be taken modulo the Boolean ideal (x_{i}^{2}-x_{i}) ; this does not affect the rank/codimension definitions, only the ambient basis choice. 4 The SPDP framework Shifted partial derivative methods study the linear span of low-order partial derivatives of a target polynomial, optionally multiplied by low-degree monomials (shift). In this paper we package that construction as an explicit matrix and work with two dual invariants: SPDP rank and SPDP codimension. 4.1 Parameter regime and scope Fix input length n and a base field \mathbb{F} . Let p\in\mathbb{F}[x_{1},\dots,x_{n}] be a polynomial representing a Boolean function under a chosen embedding (e.g. multilinear representation modulo (x_{i}^{2}-x_{i}) ). We work with parameters (\kappa,\ell) , where \kappa is the derivative order and \ell is the degree bound for the shift monomials. A key methodological requirement is parameter consistency : whenever we compare an upper bound for a computational model to a lower bound for an explicit family, both bounds must hold for the same (\kappa,\ell) regime. Remark 4.1 (Typical regimes) . Two standard choices are: (i) \kappa,\ell=\Theta(\log n) (polylogarithmic derivatives/shifts), often used when one expects polynomial bounds under suitable structural assumptions. (ii) \kappa=\Theta(n) with \ell=O(1) (high-order derivatives, no/low