Dittert’s conjecture

← Minc’s list

Minc’s list · Conjecture 28

Dittert’s conjecture

Open

Posed by
Dittert
First posed
1983

Statement

Attributed to Eric Dittert and communicated to Minc by E. T. H. Wang; it first appeared as Conjecture 28 in Minc’s 1983 survey.

Conjecture 28. Let \(K_n\) be the set of nonnegative \(n\times n\) matrices whose entries sum to \(n\). For \(A\in K_n\) with row sums \(r_1,\dots,r_n\) and column sums \(c_1,\dots,c_n\), put

\[ \varphi(A)=\prod_{i=1}^n r_i+\prod_{j=1}^n c_j-\operatorname{per}A. \]

Then \(\max\{\varphi(A):A\in K_n\}=2-\dfrac{n!}{n^n}\), and the maximum is attained only at \(J_n\), the matrix with every entry \(1/n\).

Equivalently, \(\operatorname{per}A+\bigl(2-\prod_i r_i-\prod_j c_j\bigr)\ge n!/n^n\) on \(K_n\). The bracket is nonnegative, and it vanishes exactly on the doubly stochastic matrices, where the statement is the van der Waerden inequality.

Prior progress

  • The case \(n=2\) is due to Sinkhorn (1984) and the case \(n=3\) to Hwang (1987). Hwang (1986) showed that every maximizer with positive entries is \(J_n\).
  • Cheon and Wanless (2012) showed that no partly decomposable matrix is a maximizer when \(n\ge12\), and confined possible counterexamples for \(n\ge10\) to an explicit region.
  • Pang (June 2026) proved the conjecture for all \(n\ge17\), and Kafidov (July 2026) for \(n=16\).
  • Li, Xiong and Yang (31 July 2026) proved the case \(n=4\) with an exact sum-of-squares certificate verified in the Lean proof assistant.

Our progress so far

  • All orders \(8\le n\le15\). We proved the conjecture for every \(n\ge8\), which is new for \(8\le n\le15\), with \(J_n\) as the unique maximizer.
  • The case \(n=4\), independently. We found our own proof of the case \(n=4\), on the same day as the preprint of Li, Xiong and Yang.
  • The remaining orders \(n=5,6,7\). There we have proved \(\operatorname{per}A+\alpha\bigl(2-\prod_i r_i-\prod_j c_j\bigr)\ge n!/n^n\) only for \(\alpha=4619/800\), \(989/400\) and \(13313/10000\) respectively; the conjecture is the case \(\alpha=1\).

References

  1. H. Minc, Theory of permanents 1978–1981, Linear and Multilinear Algebra 12 (1983), 227–263. doi:10.1080/03081088308817488
  2. R. Sinkhorn, A problem related to the van der Waerden permanent theorem, Linear and Multilinear Algebra 16 (1984), 167–173. doi:10.1080/03081088408817620
  3. S.-G. Hwang, A note on a conjecture on permanents, Linear Algebra Appl. 76 (1986), 31–44. doi:10.1016/0024-3795(86)90212-0
  4. S.-G. Hwang, On a conjecture of E. Dittert, Linear Algebra Appl. 95 (1987), 161–169. doi:10.1016/0024-3795(87)90032-2
  5. G.-S. Cheon and I. M. Wanless, Some results towards the Dittert conjecture on permanents, Linear Algebra Appl. 436 (2012), 791–801. doi:10.1016/j.laa.2010.08.041
  6. Z. Pang, Proof of Dittert’s conjecture for dimensions n ≥ 17, preprint (2026). arXiv:2606.01531
  7. B. Kafidov, Dittert’s conjecture in dimension 16 via a joint-deficit scaling lemma, preprint (2026). arXiv:2607.19439
  8. J. Li, B. Xiong and Z. Yang, A proof of the Dittert conjecture in dimension 4 via an exact constrained sum-of-squares certificate, preprint (2026). arXiv:2607.29191