Proof. The matrices in \(\Omega_n\) with at least one zero entry are the boundary points of the doubly stochastic polytope. For \(n>3\), the corollary following [10] shows that the minimum of the permanent on this boundary is \(\mathop{\mathrm{per}}(T_n)=m_n\). The assertion follows. ◻

Proof. The case \(q=p\) is trivial. Assume first that \(q>p\). For fixed \(p\), let \[D(q)=p\log \frac{p}{q}+(1-p)\log\frac{1-p}{1-q}.\] Then \[D'(q)=-\frac{p}{q}+\frac{1-p}{1-q}=\frac{q-p}{q(1-q)}.\] Since \(D(p)=0\), we have \[D(q)=D(q)-D(p)=\int_{p}^{q}D'(x)\,\mathrm{d}x =\int_{p}^{q}\frac{x-p}{x(1-x)}\,\mathrm{d}x.\] Since \(x(1-x)\le 1/4\) on \((0,1)\), it follows that \[D(q)\ge \int_{p}^{q}4(x-p)\,\mathrm{d}x=2(q-p)^2.\] If \(q<p\), then \[D(q)=D(q)-D(p)=-\int_{q}^{p}D'(x)\,\mathrm{d}x =\int_{q}^{p}\frac{p-x}{x(1-x)}\,\mathrm{d}x.\] The same estimate gives \(D(q)\ge \int_{q}^{p}4(p-x)\,\mathrm{d}x=2(p-q)^2\). This proves the lemma. ◻

Proof. It is enough to prove the row estimate, because the column estimate follows by transposition. Let \(R=\prod_{i=1}^{n}r_i\) and \(C=\prod_{j=1}^{n}c_j\). Since \(\sum_{i=1}^{n}r_i=n\) and \(\sum_{j=1}^{n}c_j=n\), the AM-GM inequality gives \(R\le1\) and \(C\le1\). By assumption, \(\phi(A)\ge\phi(n^{-1}J_n)\). Thus \[R+C-(\gamma_n-\delta)\ge 2-\gamma_n.\] Together with \(C\le1\), this gives \[\label{eq:R-lower} R\ge 1-\delta .\tag{1}\]

The cases \(k=0\) and \(k=n\) are trivial. Assume \(1\le k\le n-1\), and fix a row index set \(\alpha\) with \(|\alpha|=k\). Let \[\varepsilon=\sum_{i\in\alpha}r_i-k.\] We first prove \[\label{eq:aux-eps} \varepsilon^2\le \frac{2n\delta}{3}.\tag{2}\] If \(\varepsilon<0\), apply the following argument to the complement of \(\alpha\), whose deviation is \(-\varepsilon\). Hence we may assume \(\varepsilon\ge0\). Since \(R>0\), all row sums are positive and \(0\le \varepsilon<n-k\). By AM-GM applied to the rows in \(\alpha\), \[\prod_{i\in\alpha}r_i\le \left(\frac{1}{k}\sum_{i\in\alpha}r_i\right)^k =\left(1+\frac{\varepsilon}{k}\right)^k.\] By AM-GM applied to the rows outside \(\alpha\), \[\prod_{i\notin\alpha}r_i\le \left(\frac{1}{n-k}\sum_{i\notin\alpha}r_i\right)^{n-k} =\left(1-\frac{\varepsilon}{n-k}\right)^{n-k}.\] Multiplying the two inequalities gives \[R\le \left(1+\frac{\varepsilon}{k}\right)^k\left(1-\frac{\varepsilon}{n-k}\right)^{n-k}.\] Let \(p=k/n\) and \(q=(k+\varepsilon)/n\). Taking logarithms gives \[\log R\le -n\left(p\log\frac{p}{q}+(1-p)\log\frac{1-p}{1-q}\right).\] By Lemma 2, \(\log R\le -2\varepsilon^2/n\). Combining this with 1 , \[1-\delta\le R\le \exp\left(-\frac{2\varepsilon^2}{n}\right).\] Therefore \[\varepsilon^2\le -\frac{n}{2}\log(1-\delta).\] Also, \[-\log(1-\delta)=\int_{0}^{\delta}\frac{\mathrm{d}t}{1-t} \le \int_{0}^{\delta}\frac{\mathrm{d}t}{1-\delta} =\frac{\delta}{1-\delta}.\] Because \(\delta\le1/4\), we have \((1-\delta)^{-1}\le4/3\). Hence \[\varepsilon^2\le -\frac{n}{2}\log(1-\delta) \le \frac{n\delta}{2(1-\delta)} \le\frac{2n\delta}{3}.\] This proves 2 .

Let \(m=\min\{k,n-k\}\). By [8], applied to \(\alpha\), \[\left|\sum_{i\in\alpha}r_i-k\right|\le \sqrt{2\delta k}.\] Since \(\sum_{i=1}^{n}r_i=n\), we have \[\sum_{i\in\alpha^c}r_i-(n-k) =n-\sum_{i\in\alpha}r_i-(n-k) =k-\sum_{i\in\alpha}r_i =-\varepsilon .\] Applying [8] to the complement \(\alpha^c\) gives \[|\varepsilon| =\left|\sum_{i\in\alpha^c}r_i-(n-k)\right| \le \sqrt{2\delta(n-k)}.\] Together with the bound obtained from \(\alpha\), this gives \[\label{eq:CW-min} \varepsilon^2 =\left|\sum_{i\in\alpha}r_i-k\right|^2 \le 2\delta\min\{k,n-k\} =2\delta m .\tag{3}\] If \(m\le n/3\), then \(2\delta m\le 3\delta m(n-m)/n\). If \(m> n/3\), then \(m(n-m)>2n^2/9\), and 2 gives \(\varepsilon^2\le 2n\delta/3<3\delta m(n-m)/n\). Since \(m(n-m)=k(n-k)\), the desired inequality follows. ◻

Proof. Let \(t=\sqrt{3n\delta}\), and suppose that \(S=(1-t)^{-1}A\) is not doubly superstochastic. By [8], there exist row and column sets \(I,J\subseteq\{1,\ldots,n\}\) such that, with \(u=|I|\), \(v=|J|\), and \(p=u+v-n\), \[s(S[I,J])<p.\] Since \(S=(1-t)^{-1}A\), this is equivalent to \[\label{eq:not-super-new} s(A[I,J])<(1-t)p.\tag{4}\] Because \(s(A[I,J])\ge0\) and \(1-t>0\), this inequality forces \(p>0\). As \(p\) is an integer, \(p\ge1\). Here \(s(X)\) denotes the sum of the entries of \(X\).

Let \(a=n-u=|I^c|\) and \(b=n-v=|J^c|\). Then \(p=n-a-b\). By Lemma 3, applied to \(I^c\), \[\sum_{i\in I^c}r_i-a \le \left|\sum_{i\in I^c}r_i-a\right| \le \sqrt{\frac{3\delta a(n-a)}{n}}.\] Similarly, \[\sum_{j\in J^c}c_j-b \le \left|\sum_{j\in J^c}c_j-b\right| \le \sqrt{\frac{3\delta b(n-b)}{n}}.\] Because all entries are nonnegative, \[\begin{align} s(A[I,J])&=n-\sum_{i\in I^c}r_i-\sum_{j\in J^c}c_j+s(A[I^c,J^c]) \notag\\ &\ge p-\sqrt{\frac{3\delta}{n}}\left(\sqrt{a(n-a)}+\sqrt{b(n-b)}\right).\label{eq:submatrix-lower} \end{align}\tag{5}\] For \(0\le a,b\le n\), we have \(\sqrt{a(n-a)}\le n/2\) and \(\sqrt{b(n-b)}\le n/2\). Hence 5 gives \(s(A[I,J])\ge p-t\). Since \(p\ge1\) and \(0<t<1\), we have \(p-t\ge(1-t)p\). This contradicts 4 . Therefore \(S\) is doubly superstochastic. ◻

Proof. Let \(q_n=m_n/\gamma_n\). From the definitions of \(m_n\) and \(\gamma_n\), \[\label{eq:qn-new} q_n=\frac{n^{n-1}(n-2)^{n-2}}{(n-1)^{2n-3}}=\left(1-\frac{1}{(n-1)^2}\right)^{n-1}\frac{n-1}{n-2}.\tag{6}\] The desired inequality is equivalent to \[\label{eq:q-equiv-new} \frac{q_n-1}{q_n^2}>\frac{3}{4} n^3\gamma_n .\tag{7}\]

We first check \(n=17\). A direct calculation gives \[\frac{q_{17}-1}{q_{17}^2}>\frac{3}{4}\,17^3\gamma_{17}.\] Hence 7 holds for \(n=17\).

Now we prove 7 for \(n\ge18\). Let \(x=1/(n-1)\). Then \(0<x\le1/17\). Taking logarithms in 6 , \[\begin{align} \log q_n &=\frac{1}{x}\log(1-x^2)-\log(1-x) \notag\\ &=-\sum_{r=1}^{\infty}\frac{x^{2r-1}}{r}+\sum_{r=1}^{\infty}\frac{x^r}{r} \notag\\ &=\sum_{j=1}^{\infty}\frac{x^{2j}}{2j}+\sum_{j=1}^{\infty}x^{2j+1}\left(\frac{1}{2j+1}-\frac{1}{j+1}\right) \notag\\ &=\sum_{j=1}^{\infty}x^{2j}\left(\frac{1}{2j}-\frac{jx}{(2j+1)(j+1)}\right).\label{eq:logseries-new} \end{align}\tag{8}\] Since for all \(j\ge1\), \[\frac{jx}{(2j+1)(j+1)} <\frac{j}{(2j+1)(j+1)} <\frac{1}{2j},\] every summand in 8 is positive. Keeping the first summand gives \[\log q_n>x^2\left(\frac{1}{2}-\frac{x}{6}\right)>\frac{x^2}{3}.\] Since \(e^y-1>y\) for \(y>0\), applied with \(y=\log q_n\), \[\label{eq:qminus-new} q_n-1>\log q_n>\frac{x^2}{3}=\frac{1}{3(n-1)^2}.\tag{9}\] Also 6 gives \(q_n<(n-1)/(n-2)\le17/16\). Hence \[\label{eq:qq-new} \frac{q_n-1}{q_n^2}>\frac{1}{3(n-1)^2}\left(\frac{16}{17}\right)^2.\tag{10}\] It is enough to prove \[\label{eq:gamma-new} \gamma_n<\frac{4}{9n^3(n-1)^2}\left(\frac{16}{17}\right)^2.\tag{11}\] Let \[T_n=\frac{9}{4} n^3(n-1)^2\gamma_n\left(\frac{17}{16}\right)^2.\] Then 11 is equivalent to \(T_n<1\). Since \(\gamma_{n+1}/\gamma_n=(n/(n+1))^n\), \[\frac{T_n}{T_{n+1}}=\left(\frac{n-1}{n}\right)^2\left(1+\frac{1}{n}\right)^{n-3}.\] By Bernoulli’s inequality, \((1+1/n)^{n-3}>1+(n-3)/n=(2n-3)/n\). For \(n\ge18\), \((2n-3)(n-1)^2>n^3\). Therefore \(T_n/T_{n+1}>1\), so \(T_n\) is decreasing for \(n\ge18\). A direct calculation gives \(T_{18}<1\). Thus \(T_n<1\) for every \(n\ge18\). This proves 11 . Combining 11 and 10 gives 7 . Hence ?? holds for every \(n\ge17\). ◻

Proof. Because \(K_n\) is compact and \(\phi\) is continuous, there exists \(A\in K_n\) such that \(\phi(A)=\max_{X\in K_n}\phi(X)\). If \(A\) is positive, then Hwang’s positive-support result [7] gives \(A=n^{-1}J_n\). We now assume that \(A\) has a zero entry. Since \(A\) maximizes \(\phi\), we have \(\phi(A)\ge\phi(n^{-1}J_n)=2-\gamma_n\). Let \(\delta=\gamma_n-\mathop{\mathrm{per}}(A)\). By [8], \(0\le\delta\le\gamma_n\).

We first show that \(\delta>0\). If \(\delta=0\), then \(\mathop{\mathrm{per}}(A)=\gamma_n\). By the AM-GM inequality, \(\prod_{i=1}^{n}r_i\le1\) and \(\prod_{j=1}^{n}c_j\le1\). Since \(\phi(A)\ge2-\gamma_n\), equality must hold in both inequalities. Hence all row sums and all column sums of \(A\) are equal to \(1\), so \(A\in\Omega_n\). By [8], \(A=n^{-1}J_n\), contradicting the fact that \(A\) has a zero entry. Thus \(\delta>0\).

For \(n\ge17\), we have \(\delta\le\gamma_n<\min\{1/4,1/(3n)\}\). This follows from \(\gamma_{17}<1/2320000\) and from the facts that \(\gamma_n\) and \(n\gamma_n\) are decreasing in \(n\). Therefore Lemma 4 applies. Let \(t=\sqrt{3n\delta}\) and \(S=(1-t)^{-1}A\). Then \(S\) is doubly superstochastic, so there exists \(B\in\Omega_n\) such that \(0\le B\le S\) entrywise.

The matrix \(S\) is a positive scalar multiple of \(A\), so \(S\) has a zero entry. At the same position, \(0\le B\le S\) forces \(B\) to have a zero entry. By Lemma 1, \(\mathop{\mathrm{per}}(B)\ge m_n\). Because the permanent is monotone on nonnegative matrices, \(\mathop{\mathrm{per}}(S)\ge\mathop{\mathrm{per}}(B)\ge m_n\). Since \(S=(1-t)^{-1}A\), we obtain \[\label{eq:firstineq-new} \gamma_n-\delta=\mathop{\mathrm{per}}(A)=(1-t)^n\mathop{\mathrm{per}}(S)\ge (1-t)^n m_n .\tag{12}\]

Now we prove that 12 is impossible. Bernoulli’s inequality gives \((1-t)^n\ge1-nt\). Hence \[\begin{align} (1-t)^n m_n-(\gamma_n-\delta) &\ge m_n-\gamma_n+\delta-nm_n\sqrt{3n\delta} \\ &=m_n-\gamma_n+\left(\sqrt{\delta}-\frac{1}{2} nm_n\sqrt{3n}\right)^2-\frac{3}{4} n^3m_n^2 \\ &\ge m_n-\gamma_n-\frac{3}{4} n^3m_n^2. \end{align}\] By Lemma 5, the last expression is positive. Hence \((1-t)^n m_n>\gamma_n-\delta\), contradicting 12 . Therefore a maximizing matrix cannot have a zero entry.

Every maximizing matrix is positive. Hence Hwang’s positive-support result [7] implies that every maximizing matrix is \(n^{-1}J_n\). This proves both the inequality and the equality statement. ◻

Proof. The case \(n=2\) is due to Sinkhorn [5], and the case \(n=3\) is due to Hwang [6]. The cases \(n\ge17\) follow from Theorem 1. ◻