Skip to main content

Dittert’s conjecture

← Minc’s list

Minc’s list · Conjecture 28

Dittert’s conjecture

Proved by others Proved in July 2026

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.

Resolution

The conjecture is now proved in every order, with \(J_n\) as the unique maximizer.

In July 2026, Pedro Paulo Marques do Nascimento posted a proof chain covering every order, described in its repository as under review. It combines Nascimento’s own arguments for \(n=4,5\) and \(8\le n\le16\) with a computer-assisted proof of Hongyuan Lu for \(n=6,7\) and Pang’s theorem for \(n\ge17\).

Xinan Dai, Wenhao Deng, Yingdong Shi, Tailin Wu and Yuchen Yang proved the full conjecture in a paper submitted to arXiv on 30 July 2026.

We generalized the theorem from permanents to homogeneous real stable polynomials with nonnegative coefficients. Let \(P(s,x_1,\dots,x_n)\) be such a polynomial of degree \(n\) with \(P(1,0,\dots,0)=1\), and suppose that the derivatives \(r_i=\partial_{x_i}P(1,0,\dots,0)\) satisfy \(\sum_i r_i=n\). Then

\[ [x_1\cdots x_n]\,P(0,x_1,\dots,x_n)+2-\prod_{i=1}^n r_i-P(0,1,\dots,1)\ \ge\ \frac{n!}{n^n}, \]

where \([x_1\cdots x_n]\) denotes the coefficient of \(x_1\cdots x_n\), with equality only for \(P=\bigl(s+(x_1+\cdots+x_n)/n\bigr)^n\). For \(P(s,x)=\prod_{j=1}^n\bigl(s+\sum_{i=1}^n a_{ij}x_i\bigr)\), the \(r_i\) are the row sums of \(A\), \(P(0,1,\dots,1)=\prod_j c_j\), and the coefficient is \(\operatorname{per}A\), so the inequality becomes Dittert’s. In particular, our paper gives an independent proof of the conjecture in every order, with \(J_n\) as the unique maximizer.

Read the proof ↗ Read our paper →

Earlier progress

  • The case \(n=2\) is due to Sinkhorn (1984), who also showed that every maximizer has a positive permanent. The case \(n=3\) is due to Hwang (1987), and 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, and neither is any matrix whose zeros form a single rectangular block after permuting rows and columns. They also showed that any counterexample would have row and column sums very close to 1 and a permanent extremely close to that of \(J_n\). Their proofs use computer checks for small orders.
  • Pang (June 2026) proved the conjecture for all \(n\ge17\), and Kafidov (July 2026) for \(n=16\).
  • Lu (July 2026) posted a computer-assisted proof for \(6\le n\le15\).

References

  1. P. P. M. do Nascimento, Working proof chain for Dittert’s conjecture in all dimensions (2026). github.com/pedromnasc/dittert-conjecture-proof
  2. X. Dai, W. Deng, Y. Shi, T. Wu and Y. Yang, A proof of the Dittert conjecture via boundary rigidity, preprint (2026). arXiv:2610.10545
  3. H. Lu, Dittert’s conjecture in dimensions six through fifteen: an exact computer-assisted proof, manuscript, revision 2.0 (25 July 2026). github.com/lueluelue2006/dittert-n7-extension
  4. H. Minc, Theory of permanents 1978–1981, Linear and Multilinear Algebra 12 (1983), 227–263. doi:10.1080/03081088308817488
  5. R. Sinkhorn, A problem related to the van der Waerden permanent theorem, Linear and Multilinear Algebra 16 (1984), 167–173. doi:10.1080/03081088408817620
  6. 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
  7. S.-G. Hwang, On a conjecture of E. Dittert, Linear Algebra Appl. 95 (1987), 161–169. doi:10.1016/0024-3795(87)90032-2
  8. 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
  9. Z. Pang, Proof of Dittert’s conjecture for dimensions n ≥ 17, preprint (2026). arXiv:2606.01531
  10. B. Kafidov, Dittert’s conjecture in dimension 16 via a joint-deficit scaling lemma, preprint (2026). arXiv:2607.19439