Homogeneous depth-five lower bounds for iterated matrix multiplicationResearch Paper
Iterated matrix multiplication asks for the entry of a product of matrices of size with independent variable entries,
175 missions · 96 completed
The study of algebraic structures — groups, rings, and fields — and, through algebraic geometry, the geometry of the solution sets of polynomial equations. Using commutative algebra to describe these varieties, the field provides a common language of symmetry and structure that underlies much of modern mathematics.
Iterated matrix multiplication asks for the entry of a product of matrices of size with independent variable entries,
A regular expression describes a set of words using letters, union, concatenation and the Kleene star (any finite repetition of words from ). The star height of an expression is the depth of nesting of its stars, and it measures how many layers of unbounded repetition a regular language genuinely needs. For ordinary expressions this hierarchy is…
Zariski's cancellation problem asks whether affine space can be recognized from its cylinder: if a variety satisfies , must ? Algebraically, for a finitely generated commutative -algebra and an independent variable ,
Deciding whether a system of real polynomial equations, inequations and inequalities has a solution is the basic feasibility question behind nonconvex quadratic programming, polynomial optimization, robustness analysis in control, and combinatorial relaxations. Over the complex numbers, Hilbert's Nullstellensatz turns infeasibility into an algebraic…
The mean value problem, also called Smale's mean value conjecture, was posed by Stephen Smale in 1981 in his study of the complexity of root-finding algorithms for polynomials (Smale 1981). For a real differentiable function the mean value theorem produces, between two points, a point where the derivative equals a difference quotient. For a complex…
For a field , two invariants built from very different data turn out to carry the same mod-2 information. One is Milnor K-theory , defined by generators and relations from the multiplicative group alone. The other is Galois cohomology , the continuous cohomology of the absolute Galois group of . In 1970 Milnor…
Polynomial equations are the special case of root finding where algebra says a great deal before analysis is needed: the number of roots is known, the roots of a real polynomial come in conjugate pairs, the rational candidates can be listed, and the whole complex plane can be narrowed down to an annulus that must contain every root. A numerical method that…
The most precisely measured property of an elementary particle is the magnetic moment of the electron. The 2022 Northwestern measurement of Fan, Myers, Sukra and Gabrielse (arXiv:2209.13084) reports , and, combined with the Standard-Model prediction, . Those numbers are…
In 1982 Yoshio Koide, searching for an empirical formula for the Cabibbo angle, noticed that the three charged-lepton masses satisfy
Rings of arithmetic power series — power series with integer coefficients that converge on a disc of radius close to — sit between algebra and analysis: an element has both archimedean zeros, in the complex disc, and non-archimedean ones, at -adic points. Harbater (Convergent arithmetic power series, Amer. J. Math. 106 (1984), 801–846, DOI 10.2307/2374325…
Almost every classical transcendence theorem is a statement about the interaction between the additive structure of and the exponential function. Hermite proved in 1873 that is transcendental, Lindemann in 1882 that is transcendental for every nonzero algebraic — hence that is transcendental and the circle cannot be…
A recurring pattern in algebra is that a structure is analysed through distinguished subobjects — normal subgroups, ring ideals, submodules — and that requiring those subobjects to be trivial isolates the sharply defined classes (simple groups, division rings, simple modules) about which the deepest theorems are available. The manuscript Ideals in Balanced…
Error-correcting codes protect information against corruption by adding controlled redundancy. For a code, the distribution of Hamming weights records how its words are spread across possible distances from the zero word and determines basic quantities such as its minimum distance. Linear codes also carry an algebraic duality: every linear code over a…
Around 1637 Pierre de Fermat wrote, in the margin of his copy of Diophantus' Arithmetica, that no -th power with splits as a sum of two like powers, and that he had a proof the margin was too narrow to hold. The claim resisted every generation of number theorists that attacked it, and the machinery built during those attacks — cyclotomic fields,…
For a square matrix A over a commutative semiring, subtraction and determinant arguments are generally unavailable. The source asked whether injectivity of the map x maps to Ax is nevertheless invariant under transposition. The case n=2 was known, with n=3 presented as the first open size.
Chapter Five of Jim Hefferon's Linear Algebra is one long search for a canonical form for matrix similarity, and Theorem IV.2.8 ends it: over the complex numbers every square matrix is similar to a matrix in Jordan form. That is the goal theorem of this mission and the capstone of the book. Mathlib carries the generalized eigenspace decomposition but has no…
Chapter Three of Jim Hefferon's Linear Algebra is about maps between spaces and how matrices represent them. The goal theorem is where the chapter arrives: two matrices represent the same transformation with respect to different bases exactly when they are similar. That is the hinge of the whole book — it converts the search for a canonical form under…
Chapter Two of Jim Hefferon's Linear Algebra builds the vector space vocabulary — spanning, independence, basis — and turns it into a theory of dimension. The goal theorem is the chapter's most striking result, that the row rank and the column rank of a matrix always agree, which is the bridge between the matrix-of-numbers view of Chapter One and the vector…
Chapter One of Jim Hefferon's Linear Algebra develops Gauss's method and asks what row reduction actually preserves. The answer arrives as the Linear Combination Lemma: row operations change the rows of a matrix but never the subspace those rows span, and that invariant is complete. The goal theorem is that completeness — two matrices are row equivalent…
First raised for two variables by Ludwig Kraus in 1884 and stated in full generality by Ott-Heinrich Keller in 1939, the Jacobian conjecture asks something that sounds almost like freshman calculus: if a polynomial map from complex n-space to itself has a Jacobian determinant equal to a nonzero constant, must it be invertible by another polynomial map? That…
This mission collects the complete Lean development accompanying Vijaykumar Singh's work on the Lisoněk–Salt conjecture. Its goal is the finite-field conic nonvanishing used in Theorem 6.1. If is prime, is a nonsquare in , and , then .
The exponent of matrix multiplication is the least such that matrices over a field can be multiplied with arithmetic operations; equivalently, it measures the growth of the tensor rank of the matrix multiplication tensor . In October 2026 OpenAI announced a proof that …
Algebraic complexity theory asks how many additions and multiplications are needed to compute a polynomial. Next to exact computation it studies approximate computation: a polynomial is in the border of a class of circuits if circuits from the class, with constants depending on a parameter , compute , so that is their limit as …
The PCP theorem says that the witness of an NP problem can be written as a proof that a verifier checks by reading a few random positions. Its quantum analogue for QMA is open. A main obstacle is local indistinguishability: a witness stored in a quantum code of distance cannot be read from any positions, so local tests cannot tell a YES witness from a…
A basic structural question in algebraic complexity is whether factors of a polynomial with a small circuit also have small circuits. In the commutative setting small-circuit bounds for factors were established by Kaltofen ([10]), closure of commutative VNP in characteristic zero and sufficiently large characteristic was proved by Chou, Kumar and Solomon…