CS Paper Radar

Eventual Nonnegativity of a Matrix Is in P

Julian D'Costa

cs.LO ·submitted 2026-09-20 19:44 UTC · v2
theorycode/data

Abstract

Given a rational matrix $A$, is every sufficiently large power $A^n$ entrywise nonnegative? We prove that this problem is decidable in deterministic polynomial time. This is in contrast with deciding eventual nonnegativity of a single prescribed entry sequence $(A^n)_{ij}$, which amounts to the Ultimate Positivity Problem for linear recurrence sequences, whose decidability is open. The previous decidability procedure (D'Costa, Ouaknine and Worrell, STACS 2024) splits the matrix powers into residue classes modulo a torsion exponent $D$ whose value can be exponential in the input size. We show that it is sufficient to check a single progression $A^{Dk+1}$: the exponents $n$ with $A^n \geq 0$ are closed under addition, and two consecutive exponents of the progression are coprime, so they generate every sufficiently large exponent. Along the progression, eigenvalues are grouped by their common $D$th power, and the required coefficients for each group are computed without forming $A^D$, any $λ^D$, or a splitting field: each summand is evaluated in its own root field $\mathbb{Q}(λ)$, and Galois equivariance keeps the degree and height of every class sum polynomially bounded, enabling certified zero and sign tests. The same algorithm with one case rejected decides eventual positivity, and a variant decides whether the matrix has any nonnegative power at all.

Comment
19 pages, including appendix. v2: added a reference and minor edits to the exposition. A Lean 4 formalisation of the structural criterion and key inequalities is available at https://github.com/julianrdcosta/ptime-ENN-lean-formalization

Closest papers

Nearest neighbours by meaning across the whole index.

Beyond the Bethe Approximation of the Permanent

cs.DS math.CO ·2026-08-28 ·Nima Anari
theorycode/data similarity 0.59
Abstract · 34 pages. Accompanying Lean 4 formalization: https://github.com/nimaanari/formalization-beyond-bethe. Palomar Registry entry: https://paloma…

The canonical Bethe approximation gives a deterministic approximation to the permanent of every nonnegative matrix within a factor of $(\sqrt{2})^n$. We improve the base of this exponential factor: for some absolute constant $c<\sqrt{2}$, there is a deterministic polynomial-time $c^n$-approximation for the permanent of every nonnegative matrix. This shows that the canonical Bethe guarantee is not a barrier for deterministic approximation of the permanent. The proof augments the Bethe lower bound with a new certificate tailored to matrices on which that lower bound loses nearly the full factor. The author supplied the high-level plan of attack, and the proof was developed in an interaction with ChatGPT 5.6 Sol Pro. The author subsequently verified the results. Codex assisted with proof checking, manuscript assembly, and typesetting.

0.67

Explicit matrix hitting points for noncommutative algebraic branching programs

cs.CC math.RAmath.CO ·2026-10-11 ·Zhipeng Lu
similarity 0.59
Abstract · 24 pages. There's statement about reproducibility and Lean verification in section 5

We give a deterministic polynomial-resource black-box identity test for noncommutative algebraic branching programs (ABPs), using ordinary matrix evaluations of the output polynomial. Given an alphabet of size $m\ge1$ and an ABP vertex bound $S\ge1$, we construct one fixed tuple of integer matrices of order $R=(m+2)d(d+1)/2$, where $d=(m+2)S$, with entry bit length $O(d\log(d+1))$. Every nonzero polynomial computed by an ABP with at most $S$ vertices has a nonzero evaluation at this tuple. The construction accesses neither the hidden ABP nor its intermediate gates. A rectangular variant improves the order to $O(m^{3/2}S^2)$. Matrix order, description length, and all returned entries are counted; the total resources are polynomial. The result holds in characteristic zero and in characteristic $p>\binom d2$. The main ingredient is a fixed polynomial frame spanning the joint cyclic module of every matrix tuple from every prescribed vector. A compensating block makes a tagged encoding nilpotent of index at most three, while preserving the original cyclic module. A differential exterior-vector argument then gives a single triangular recurrence with polynomially many outputs. Its shared left-linear circuit is converted into actual integer query matrices by coefficient duality. Two-sided pairing further gives deterministic nonadaptive reconstruction of an equivalent ABP from polynomially many output-only matrix queries. The same frame gives polynomial-cardinality explicit trace separators for simultaneous-conjugation orbit closures, and a fixed nilpotent substitution for bounded-dimensional recognizable series. The latter also tests rational formulas whose given syntax is defined at the scalar origin. We provide complete proofs, construction costs, and exact implementation checks.

0.16

Mortality Is Undecidable for $2 \times 2$ Integer Matrices

cs.CC ·2026-11-04 ·Thanin Quartz, Ivan O. Shevchenko, Hans De Sterck, Jun Liu
similarity 0.56
Abstract

The matrix mortality problem asks whether a given finite family of matrices can be multiplied, in any order and with possible repetition, to get the zero matrix. It is one of the most basic decision problems about matrix products, and it arises naturally in the study of switched linear systems and of finite automata. Mortality is trivially decidable in dimension one and has been known to be undecidable for integer matrices in dimensions three and higher since 1970; only the problem in dimension $2$ is left open. We resolve this problem by proving that mortality is undecidable for families of 5,799 distinct $2\times2$ integer matrices. All but one of the matrices are fixed and nonsingular, with determinants $\pm p$ for a single fixed prime $p$. The input affects only the remaining rank-one matrix, which encodes this input into its kernel. Our proof encodes the computation of a fixed universal machine into products of $2\times2$ matrices. We represent each configuration of the computation by a single rational number, which we identify with a line through the origin in $\mathbb{Q}^2$, and each nonsingular matrix carries out a small piece of one computation step. The main difficulty is that the matrices may be multiplied in any order, so we design them to check their own work: a "wrong'' step puts a factor of a prime number $p$ into the denominator of the rational number corresponding to the current computation step, where no later matrix can remove it. As a result, products of these matrices can go from one encoded configuration to another only by following a valid computation. The rank-one matrix then turns the question of whether the machine halts into the question of whether some product equals zero. A companion formalization in the Lean proof assistant verifies the complete reduction.

0.19

Matrix Multiplication from Polynomial Packings: A Constructive and Elementary Proof of $ω\le9/4$

cs.CC ·2026-10-20 ·Rafael Pass
similarity 0.55
Abstract

We give a self-contained constructive proof that the matrix multiplication exponent satisfies $ω\le9/4$. In a recent breakthrough, OpenAI~\cite{original} established this bound in the model of exact scalar arithmetic over the complex numbers, using non-constructive arguments in Strassen's asymptotic spectral framework. We explicitly construct a Strassen-style matrix multiplication identity and obtain the bound by ordinary block recursion. For every $γ>0$, the resulting algorithm multiplies two $n\times n$ integer matrices using $O(n^{9/4+γ})$ integer arithmetic operations. As an independent contribution, we develop a framework of \emph{polynomial packings}---methods for reducing many polynomial multiplications to fewer ones using linear operations. We isolate and generalize a construction of OpenAI~\cite{original} to obtain a simple packing, and show how packings can be composed to amplify their ``compression rate", which finally yields Strassen-like identities.

0.07

Subexponential Approximation of the Permanent in Deterministic Polynomial Time

cs.DS cs.CCmath.CO ·2026-09-09 ·Sergei Kudria, Jason Luo, Mahbod Majid
theory similarity 0.55
Abstract · 44 pages

We give the first deterministic polynomial time algorithm that approximates the permanent of arbitrary nonnegative rational matrices within a subexponential factor. For a matrix of order $n$, the approximation factor is \[ \exp\!\left(O\!\left(\frac{n(\log\log n)^2}{\log n}\right)\right)=\exp(o(n)). \] All previously known deterministic polynomial time guarantees for unrestricted inputs had approximation factors $\exp(Ω(n))$. Our proof uses convex optimization to tighten an upper bound on the permanent. The bound is based on weighted sums over all matchings in a bipartite graph representing the matrix, and correlations between unmatched vertices control its error. We approximate these sums deterministically using correlation decay and a bound on the effect of vertex deletion.

0.45

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

cs.CC math.AC ·2026-10-29 ·Karthik Sheshadri
theory similarity 0.55
Abstract · 18 pages; stand-alone; submitted to International Mathematical Research Notices

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.

0.28

Equal Hamming Weights at Fixed Root Order and Applications to Constacyclic MDS Codes

cs.IT ·2026-10-31 ·Li Zhu, Hongfeng Wu
theory similarity 0.54
Abstract

For a fixed positive integer $n>1$, we study the prime powers $q$ coprime to $n$ for which all monic irreducible factors of $Φ_n$ over $\F_q$ have the same coefficient Hamming weight. Cyclotomic orbit coefficients give a finite, effective classification of these fields. Outside finitely many computable characteristics, every factor has the support of its characteristic-zero orbit polynomial; the uniform condition $p>2^{\varphi(n)}$ suffices. In each remaining characteristic, extension exponents reduce to divisors of $\ord_n(p)$, and an integer variance identity expressed by polynomial gcd degrees decides equal weight. The same coefficient data determine the full weight distribution. As an application, we prove that an MDS constacyclic code with an irreducible generator forces every irreducible polynomial of the same root order to have full support, including factors associated with different constacyclic constants. This yields a uniform gcd and norm obstruction. We develop its short-multiplier extension, give a prime-order cubic family, and establish an explicit quadratic-residue exclusion without a prime-square alphabet or a near-square length hypothesis.

0.20

An $\widetilde{O}(n^3)$-time FPRAS for the Permanent

cs.DS cs.DMmath.COmath.PR ·2026-09-17 ·Xiaoyu Chen, Heng Guo, Eric Vigoda, Xiongxin Yang
theory similarity 0.54
Abstract · 62 pages

We give an FPRAS for the permanent of an $n\times n$ $0/1$ matrix with running time $\widetilde O(n^3)$. Our algorithm extends to a strongly polynomial FPRAS for arbitrary nonnegative matrices with the same running-time bound (but in the unit-cost arithmetic model). Jerrum, Sinclair, and Vigoda (2004) gave the first FPRAS for the permanent of a nonnegative matrix. The running time was subsequently improved to $\widetilde{O}(n^7)$ by Bezáková, Štefankovič, Vazirani, and Vigoda (2008), and recently to $\widetilde{O}(n^6)$ by Chen, Vigoda, and Yang (2026). We introduce a multicommodity-flow bound inspired by electrical flows, replacing the usual path-length factor by routing energy. For the classical JSV chain with perfect-matching weights multiplied by $n^2$, we prove a relaxation-time bound of $O(n^3\log n)$ and obtain comparable bounds for estimating the stationary probabilities of having a specified pair of unmatched vertices. We use a separate chain on assignments to generate a warm start at any given temperature, avoiding the long initialization of the JSV chain. Finally, we replace the JSV chain with a new chain that uses only $n$ hole weights and speeds up hole-weight learning by a factor of $n$.

0.20