Some results towards the Dittert conjecture on permanents (Q763062): Difference between revisions

The Dittert conjecture says the following. Let \(A=(a_{ij})\) be an \(n\times n\) martix. Consider the function \[ \phi(A)=\prod_{i=1}^n\sum_{j=1}^n a_{ij}+\prod_{j=1}^n\sum_{i=1}^n a_{ij}-per(A), \] and define \(J_n\) to be a matrix all whose entries equal \(\frac{1}{n}\). Dittert conjectured that for a real nonnegative \(n\times n\) matrix \(A\) with entries sum \(n\) one has \[ \phi(A)\leq 2-\frac{n!}{n^n}, \] with equality if and only if \(A=J_n\). The Dittert conjecture is still open for \(n\geq 4\). This conjecture generalizes the van der Waerden conjecture. The problem was to find the minimun of \(per(A)\) on the set of matrices with all row and column sums equal to \(1\) (these matrices are called stochastic matrices). This problem was solved by Egorycev and Falikman [\textit{G. P. Egorychev}, Adv. Math. 42, 299--305 (1981; Zbl 0478.15003); \textit{D. I. Falikman}, Math. Notes 29, 475--479 (1981); translation from Mat. Zametki 29, 931--938 (1981; Zbl 0475.15007)]. In particular they proved that the matrix with the minimal permanent is \(J_n\). In the Dittert conjecture a larger set of matrices than in the van der Waerden conjecture is considered; if one restricts to the set of stochastic matrices then the Dittert conjecture follows from the van der Waerden conjecture. Several partial results on the Dittert conjecture were obtained by \textit{R. Sinkhorn} [Linear Multilinear Algebra 16, 167--173 (1984; Zbl 0568.15004)], \textit{S. G. Hwang} [Linear Algebra Appl. 76, 31--44 (1986; Zbl 0589.15016); ibid. 95, 161--169 (1987; Zbl 0628.15018)], \textit{G.-S. Cheon} and \textit{H.-W. Yoon} [Int. Math. Forum 1, No. 37--40, 1943--1949 (2006; Zbl 1306.15008)]. The main results of the paper under review are the following. If \(A\) is partially decomposable, then \(\phi(A)\leq \phi(J_n)\). If the zeroes in \(A\) form a block then \(A\) is not a \(\phi\)-maximizing matrix. One has \(\phi(A)<\phi(J_n)\) unless \(\delta:=per(J_n)-per(A)\leq O(n^4e^{-2n})\) and \[ |k-\sum_{i\in \alpha} r_i|<\sqrt{2\delta k}, \] \[ |k-\sum_{i\in \beta}c_i|<\sqrt{2\delta k} \text{ and } \sum_{i\in \alpha, j\in \beta} a_{ij}<k+\sqrt{\delta k} \] for all sets \(\alpha,\beta\) of \(k\) integers chosen from \(\{1,2,\dots,n\}\)