CS Paper Radar

Cubic lower bounds for the permanent in odd characteristic, for Pfaffian representations, and for polynomial entries

Karthik Sheshadri

cs.CC math.AC ·submitted 2026-10-29 17:14 UTC · v1
theory

Abstract

The determinantal complexity of a polynomial is the order of the smallest matrix whose entries are polynomials of degree at most one and whose determinant equals the polynomial. A lower bound for the permanent in this measure is the algebraic form of the question whether the permanent is harder to compute than the determinant. Over the complex numbers, the best known lower bound grows cubically in the size of the permanent. It holds even when the permanent only has to be a limit of such determinants. I prove that the cubic lower bound holds over every algebraically closed field of odd characteristic $p$, with a constant that depends on $p$. Hence the cubic bound does not depend on characteristic zero. I also prove the bound for Pfaffians, which are square roots of determinants of skew symmetric matrices. Lower bounds for Pfaffians imply the same bounds for determinants. Further, I prove the bound, divided by $a$, for matrices whose entries are polynomials of degree at most $a$. All three results come from one lower bound for smooth hypersurfaces. I prove it in every characteristic by counting intersection points together with their multiplicities.

Comment
18 pages; stand-alone; submitted to International Mathematical Research Notices

Closest papers

Nearest neighbours by meaning across the whole index.

The determinantal complexity of the 4*4 permanent is 15

cs.CC ·2026-11-04 ·Karthik Sheshadri
theory similarity 0.66
Abstract · 8 pages

The best known lower bound on the determinantal complexity of the 4x4 permanent is 10. In this short note, I prove that this value is exactly 15: the 4x4 permanent is the determinant of a 15x15 matrix of affine linear forms, and cannot be that of any smaller matrix. To do so, I must establish both a lower and upper bound. To establish the upper bound, I use Grenet's construction of size 2^n-1. Hence that construction is optimal at n=4 (and n=3). This now constitutes the first knwon exact value of the determinantal complexity of the permanent at n=4. Only the value at n=3 was exactly known, prior to this note. The general quadratic bound only gives 8 for n=4. To establish the lower bound, I work from a normal form at a zero of the permanent. In the first row (and column) of the normal form, the linear forms vanish on a linear space inside the singular locus of the permanent. A hessian inequality bounds the size of the matrix in terms of that space. Then, a matrix of sie 14 foces the space into any of nine corordinate types. The forcing is either up to symmetry, or else into a family that degenerates to one of them. I then rule out every case. All involved computations are exact. In respect of the claim, I have made all certificates public.

0.25

A Quadratic Lower Bound on Determinantal Complexity

cs.CC math.ACmath.AG ·2026-09-28 ·Mrinal Kumar, Ben Lee Volk
publishedtheoryhighly cited similarity 0.62
Abstract

We prove an $Ω(n^2)$ lower bound on the determinantal complexity of the power sum polynomial $\sum_{i=1}^n x_i^n$ over the field of complex numbers. A similar result was claimed in a recent paper of Sheshadri (arXiv:2606.13628), via an AI-assisted and AI-written proof. Assuming its correctness, this was the first super-linear lower bound for this fundamental algebraic problem for any explicit polynomial. However, the authors of this note were unable to follow the details and verify the argument in arXiv:2606.13628, in spite of considerable effort on their part. The proof we provide here is short, (almost) self-contained and seemingly simpler.

0.60

Improved Bounds for the Bilu-Linial Conjecture via Spectral Recovery from Mixed Determinantal Polynomials

cs.DM math.CO ·2026-09-14 ·Fangfang Lin, Hong Zhou
theory similarity 0.61
Abstract · 25 pages, slightly improved bound for graphs of girth at least 5, include some recent progress

Bilu and Linial conjectured that every finite $d$-regular graph with $d \geq 2$ admits an edge signing $σ$ whose signed adjacency matrix $A_σ$ has spectral radius at most $2\sqrt{d-1}$. We prove that every signing meeting the mixed-root condition $r_{A_σ}\leq\sqrt{2(d-1)}$ satisfies \[ ρ(A_σ) < \frac{3+\sqrt5}{2}\sqrt{d-1}, \] where $r_{A_σ}$ is the largest root of the mixed determinantal polynomial $χ[A_σ,-A_σ]$. The interlacing theorem of Ravichandran and Srivastava guarantees a signing satisfying the mixed-root condition, so our result improves the coefficient $2\sqrt2$ in their two-sided spectral bound. In the proof, we construct a positive matrix-valued probability measure supported on the roots of $χ[A_σ,-A_σ]$. The second moment gives a simple matrix inequality $A_σ^2 + dI \preceq 4r_{A_σ}^2I$, which yields a preliminary coefficient $\sqrt{7}$. Estimates for the fourth moment use information about short walks to obtain the coefficient $(3+\sqrt{5})/2$. For triangle-free graphs, the coefficient improves to $\sqrt6$, and for graphs with girth at least five, it improves to $\sqrt{35/6}$. As a result of independent interest, we extend the construction to $χ[A_1,\ldots,A_k]$ for Hermitian matrices $A_1,\ldots,A_k$ with zero diagonal, and compute the first two moments explicitly. Finally, an explicit signing of $K_8$ shows that the mixed-root condition alone cannot guarantee a coefficient below $(4+\sqrt5)/\sqrt6$.

0.54

A linear-in-$q$ range of dimensions for the MDS conjecture over $\mathbb F_q$ in odd characteristic

cs.IT math.CO ·2026-09-22 ·Xiang Fan
theory similarity 0.61
Abstract · 23 pages. The proof has been reorganized to make its homological structure explicit. Other versions of this preprint are available on Zenodo…

Let $q$ be a power of an odd prime $p$. We prove the MDS conjecture over $\mathbb F_q$ in every dimension $k$ satisfying \[ 2\leqslant k\leqslant B(p,q) \quad\text{or}\quad q+2-B(p,q)\leqslant k\leqslant q, \qquad B(p,q)=\left\lfloor\frac{(p-2)q+6p-10}{2p-3}\right\rfloor. \] For fixed $p$, the first interval is linear in $q$; together with duality, the theorem covers an asymptotic proportion $1-1/(2p-3)$ of all dimensions. The proof rests on a vanishing theorem for determinant relations over an arbitrary field of characteristic $p>0$. It yields full row rank for Chowdhury's matrices over a larger range of arc sizes. In particular, at $|G|=2k-3+n$ it proves Chowdhury's full-row-rank conjecture without the $q$-dependent restriction. Specialization to $\mathbb F_q$, together with the Ball--Lavrauw construction, gives the stated MDS range. We also prove that, for every odd prime power $q$, every normal rational curve in $\mathrm{PG}(N,q)$ is complete for $2\leqslant N\leqslant q-2$, and every projective Reed--Solomon code of length $q+1$ and dimension $2\leqslant k\leqslant q-2$ has covering radius $q-k$.

0.59

Supersingular Elliptic Curves Without Inseparable Small Degree Endomorphisms

cs.CR math.NT ·2026-09-03 ·Nicolas Swanson
theorycode/dataunusual similarity 0.58
Abstract · Computational supplement available at https://github.com/Nicswansonwaterloo/MaxFrobeniusConj

For a fixed characteristic $p$, let $δ(p)$ denote the smallest degree needed to guarantee the existence of an isogeny from any supersingular curve $E$ to its Frobenius conjugate $E^{(p)}$. We translate existence questions concerning $δ(p)$ into questions about positive definite integral ternary quadratic forms and use Voronoi's theory of perfect forms in dimension three to characterize when $δ(p)$ is nearly maximal. For sufficiently large primes, we show that $δ(p)$ attains its upper bound precisely when $p$ is represented by one of nine explicit cubic polynomials, reducing the infinitude of such primes to whether one of these cubics takes prime values infinitely often. We also prove that, for almost all primes, $δ(p)$ lies at least $p^{1/6-o(1)}$ below its upper bound.

0.68

Determinant boundaries and gaps in determinantal complexity

cs.CC ·2026-11-02 ·Karthik Sheshadri
theory similarity 0.58
Abstract · 75 pages, in submission to FoCM

Landsberg, Manivel, and Ressayre constructed determinant-boundary components whose defining forms, for odd n >= 3, are limits of n x n determinants but cannot themselves be represented by determinants of that size. Their border determinantal complexity (DC) is therefore smaller than their exact DC. We prove that the difference can grow linearly with n. For every n >= 10, we construct an explicit homogeneous form of degree n, concise in n^2 variables, whose orbit closure is a boundary component, whose border DC is n, and whose exact DC is at least 2n - 1. Thus n rows suffice when limits are allowed, whereas every exact representation requires at least 2n - 1 rows. The same bound holds for the unpadded odd-skew forms at every odd n >= 3. We also prove that every concise degree-n boundary form in n^2 variables has exact DC at least n + 2. We construct three families of pairwise distinct boundary components. Together with the traceless determinant, they give at least floor((n-1)/2) + floor(n/3) components for every n >= 3, with an additional term counted explicitly in the paper. The main lower bound follows from a general degree lemma. If an affine matrix represents an irreducible homogeneous polynomial f of degree d and has globally free rank-one cokernel over the coordinate ring of f = 0, its size is at least 2d - 1. The adjugate factors into two nonzero kernel vectors, each requiring a coordinate of degree at least d - 1. Comparing their product with the degree of a cofactor proves the bound. The lemma is sharp for individual representations, as witnessed by algebraic branching programs. Whether the exact-versus-border gap can grow superlinearly remains open.

0.32

A Hyperplane Bound and Ward's Divisibility Conjecture

cs.IT ·2026-10-19 ·Guanghui Zhang
theoryhot direction similarity 0.57
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.53

A Counterexample to the Tang Zhang Schatten Norm Conjecture and Sharp Positive Results

cs.LG math.COmath.FA ·2026-08-16 ·Zijian Zeng, Houde Liu, Kurunathan Ratnavelu
theory similarity 0.57
Abstract · 9 pages, 0 figure,

For $m\geq 2$, let $c_p(m)$ be the all-dimensional best constant in $$ \left\|\sum_{k=1}^m A_k\right\|_p \leq c_p(m)\left\|\sum_{k=1}^m |A_k|\right\|_p. $$ Tang and Zhang conjectured an explicit formula for every finite $p>1$. We disprove the conjecture with two explicit real $2\times 2$ rank-one matrices at $p=3/2$. The comparison is certified by seven strict rational inequalities and, in particular, places the attained ratio above $207/200$, while the conjectured constant lies below $207/200$. On the positive side, we prove the conjectured sharp bound for every family of rank-at-most-one summands when $2\leq p<\infty$, and classify all equality cases. We also prove the corresponding endpoint statement for $p=\infty$. Finally, for arbitrary complex matrices, we establish the conjectured sharp constant in the case $m=2$, $p=4$.

0.44