← All papers
First page of Sum of Squares and Non Sum of Squares Regimes for the Toeplitz Bottcher Wenzel Form

Sum of Squares and Non Sum of Squares Regimes for the Toeplitz Bottcher Wenzel Form

Wenqi Zhu, Ping Nie

math.NA Oct 6, 2026 · v3 math.OC
Lean 4 formally verifies the large-order non-SoS theorem with its explicit threshold, and the SoS certificates for Toeplitz BW forms of orders 2 to 20.
Toeplitz matrices are among the simplest structured models of translation invariance, arising naturally in convolution, stationary covariance models, and discretizations of translation-invariant operators. For a pair of real matrices, the Böttcher–Wenzel form (BW form) is a nonnegative quartic measuring the gap in the corresponding commutator inequality. László conjectured that, when both matrices are Toeplitz, this quartic is a sum of squares for every matrix order. We show that the conjecture is false. More precisely, we identify an explicit family of corner-supported Toeplitz pairs, retaining only the outermost diagonals on the two sides, for which the associated BW form is not a sum of squares at all sufficiently large orders. The proof reduces the complete family of Gram representations to a finite complex test: its Gram-invariant part develops a strictly negative limiting direction, while the remaining Gram-dependent contribution vanishes. We also give an explicit sufficient threshold for the matrix order. The negative result is complemented by two positive regimes. If either Toeplitz factor is symmetric or skew-symmetric, then the corresponding BW form is SoS for every order, with the other factor allowed to be an arbitrary real Toeplitz matrix. For unrestricted Toeplitz pairs, we further prove SoS representability for every $2\le N\le50$, with formal Lean 4 verification through order 20. The large-order non-SoS theorem, including the explicit sufficient threshold, has also been formally verified in Lean 4.

László conjectured in 2012 that the Böttcher–Wenzel quartic form is a sum of squares (SoS) for every matrix order when both matrices are Toeplitz. The question is whether this conjecture holds.

The authors restrict the form to corner-supported Toeplitz pairs and work in wedge coordinates. They reduce the full family of Gram representations to a normal form using symmetries. A finite complex test then shows that the Gram-invariant part has a strictly negative limiting direction while the Gram-dependent part vanishes. For the positive results, they split each factor into symmetric and skew-symmetric parts, and they build exact rational inductive SoS certificates for small orders. The non-SoS theorem and the certificates for orders up to 20 are checked in Lean 4.

The conjecture is false: the Toeplitz BW form is not SoS for all sufficiently large orders, with an explicit sufficient threshold N0 = 2^9961475. The form is SoS at every order if either factor is symmetric or skew-symmetric. Unrestricted Toeplitz pairs are SoS for 2 ≤ N ≤ 50, with Lean verification for orders up to 20.