Permanent Bounds for Diffuse Doubly Stochastic Matrices

Definitions and mathematical statement

Fix a real constant $\gamma\geq1$, independent of $n$. An $n\times n$ doubly stochastic matrix $A=(a_{ij})$ has real entries $a_{ij}\geq0$ with every row sum and column sum equal to one. Its permanent is \[ \operatorname{per}(A)=\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)}. \] Assume the squared Frobenius-norm bound \[ \sum_{i,j=1}^n a_{ij}^2\leq\gamma. \] The main question is whether \[ \operatorname{per}(A)=n^{O(1)}e^{-n} \] uniformly over these matrices as $n\to\infty$, with the polynomial exponent and constants allowed to depend on the fixed $\gamma$. The requested polynomial-factor upper estimate can be stated as \[ \exists C_\gamma>0\ \exists k_\gamma\geq0\ \exists n_\gamma\quad \forall n\geq n_\gamma\ \forall A\text{ satisfying the hypotheses},\qquad \operatorname{per}(A)\leq C_\gamma n^{k_\gamma}e^{-n}. \] If the equality notation is intended to require two-sided polynomial comparability, one must additionally require a lower bound of the form $C_\gamma^{-1}n^{-k_\gamma}e^{-n}$. The extraction does not expand its asymptotic notation. In particular, $\gamma$ is fixed before the matrix dimension; no dimension-independent constants uniform over all $\gamma$ are asserted.

The raw record additionally includes a planar counting question, separately represented by local record OWR-2090-027: is there $c>1$ such that for every sufficiently large allowed planar point set $P$, \[ \operatorname{st}(P)\geq c^{|P|}\operatorname{tr}(P), \] where $\operatorname{st}$ counts crossing-free straight-line spanning trees and $\operatorname{tr}$ counts triangulations of the point set? This is retained as raw-record provenance, not merged with the permanent conjecture. Collinearity and triangulation conventions for that separate question are not supplied.

Short English statement

For fixed $\gamma$, does a doubly stochastic matrix with squared Frobenius norm at most $\gamma$ have permanent at most a polynomial in its dimension times $e^{-n}$? The raw source also contains a separately catalogued planar tree-versus-triangulation question.

Sources

• Local UnsolvedMath registry, permanent ID $30001073$, source code catalogue entry, "Permanent Bounds for Diffuse Doubly Stochastic Matrices." No individual proposer is supplied.
• Adjacent local registry record, permanent ID $30001074$, OWR-2090-027, "Spanning-Tree Counts versus Triangulation Counts," separately represents the raw record's second question.
• Discrete Geometry (2009), Oberwolfach Reports, DOI 10.4171/owr/2008/44, pp. 2477--2556, listed as "OWR Report 44": https://doi.org/10.4171/owr/2008/44. This is the sole supplied external reference.
• Supplied literature triage, checked 2026-08-21: status "open." It says the Frobenius-norm hypothesis is not covered by the known entrywise bound and reports no located proof of the permanent estimate. The entrywise theorem and its hypotheses are not reproduced. This is supplied dated curation, not independently verified; time-sensitive status and cited claims require independent verification.