A Proof of the Dittert Conjecture in Dimension 4 via an Exact Constrained Sum-of-Squares Certificate
Jinhui Li, Beibei Xiong, Zhengfeng Yang
cs.SC
Jul 31, 2026 · v2
TL;DR
The exact rational SOS certificate and both main theorems (Dittert conjecture for n=4 and the stability bound) are machine-checked in Lean 4 with Mathlib.
Abstract
The Dittert conjecture states that the Dittert functional on nonnegative $n\times n$ matrices whose entries sum to $n$ is uniquely maximized by the uniform matrix. We prove the conjecture in dimension $4$. More precisely, let $K_4$ be the simplex of nonnegative $4\times4$ real matrices whose entries sum to $4$, let $U_4$ be the uniform matrix, and let $φ$ denote the Dittert functional. We establish $\frac{61}{32}-φ(A)\ge \frac{1}{52}\|A-U_4\|_F^2$ for every $A\in K_4$. Consequently, $U_4$ is the unique maximizer of $φ$ on $K_4$. The proof reduces the problem to an exact certification of the nonnegativity of a structured quartic polynomial in sixteen variables on a simplex. We develop a symbolic-numeric procedure for constructing an exact rational constrained sum-of-squares certificate. The procedure combines adaptive template selection with sequential rational recovery to handle singular Gram matrices and coupled SOS blocks arising from the constraint structure. The final certificate consists of a main SOS with $152$ positively weighted rational squares and $136$ smaller SOS blocks, each containing $16$ such squares. Exact $LDL^T$ decompositions and coefficient comparison over $\mathbb{Q}$ certify the polynomial identity. The resulting exact certificate is formally verified using the Lean proof assistant.
Problem
The Dittert conjecture states that the uniform matrix uniquely maximizes the Dittert functional on nonnegative n×n matrices whose entries sum to n. Only the cases n=2 and n=3, plus n≥17 in a preprint, were previously settled.
Approach
The dimension-4 case is reduced to certifying nonnegativity of a structured quartic polynomial in 16 variables on a simplex. An agent-guided symbolic-numeric procedure selects a constrained SOS template from a hierarchy and then sequentially recovers rational Gram blocks, handling singular Gram matrices and coupled blocks. The resulting exact certificate is formalized in Lean 4 with mathlib4, using Mathlib's Matrix.permanent and a bridging lemma to the entrywise definition.
Results
The bound 61/32 − φ(A) ≥ (1/52)‖A−U_4‖_F² is proved for all A in K_4, so U_4 is the unique maximizer. The certificate has a main SOS with 152 rational squares and 136 smaller blocks of 16 squares each, and is verified in Lean.