\documentclass[11pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{microtype}
\usepackage{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{xcolor}
\usepackage{hyperref}

\geometry{margin=1in}
\hypersetup{
  colorlinks=true,
  linkcolor=blue!55!black,
  citecolor=blue!55!black,
  urlcolor=blue!55!black,
  pdfauthor={Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník},
  pdftitle={Linear Trace-Deficit Decay for Permanents of Positive Semidefinite Contractions},
  pdfsubject={A linear-in-epsilon strengthening of the PSD permanent upper bound}
}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{conjecture}[theorem]{Conjectural target}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{example}[theorem]{Example}

\numberwithin{equation}{section}

\DeclareMathOperator{\permanent}{per}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\diag}{diag}
\newcommand{\per}{\permanent}
\newcommand{\C}{\mathbb C}
\newcommand{\R}{\mathbb R}
\newcommand{\E}{\mathbb E}
\newcommand{\ip}[2]{\left\langle #1,#2\right\rangle}
\newcommand{\opnorm}[1]{\left\lVert #1\right\rVert_{\mathrm{op}}}
\newcommand{\fnorm}[1]{\left\lVert #1\right\rVert_{\mathrm F}}

\title{Linear Trace-Deficit Decay for Permanents\\
of Positive Semidefinite Contractions\thanks{This work was produced within the Bolzano project (\url{https://bolzano.app}), using AI systems for mathematical research and manuscript preparation. The listed authors contributed to the project and the preparation of this release. The manuscript received only limited human checking.}}
\author{Mat\v{e}j Kripner \qquad V\'{a}clav Rozho\v{n} \qquad Robert \v{S}\'{a}mal\\[0.4em]
Martin \v{S}indel\'{a}\v{r} \qquad Adri\'{a}n Z\'{a}me\v{c}n\'{i}k}
\date{}


% Collection typography.
\geometry{a4paper,hmargin=23mm,vmargin=25mm}
\definecolor{BolzanoInk}{HTML}{24445C}
\hypersetup{colorlinks=true,linkcolor=BolzanoInk,citecolor=BolzanoInk,
  urlcolor=BolzanoInk,pdfauthor={Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník},pdflang={en-US}}
\urlstyle{same}
\setlength{\emergencystretch}{1em}
\let\BolzanoBibliography\thebibliography
\renewcommand{\thebibliography}[1]{\BolzanoBibliography{#1}\raggedright}
\begin{document}

\maketitle

\begin{abstract}
Every Hermitian positive semidefinite contraction \(A\) satisfies
\(\per(A)\leq\exp(-\tr(I-A)/68)\). This proves the linear
trace-deficit bound conjectured by Ebrahimnejad, Nagda, and Oveis Gharan,
whose estimate had quadratic dependence on the normalized deficit.
The proof combines a size-biased complex Gaussian representation,
a block version of Hanson--Wright decoupling, and a rational Loewner
majorant. The constant is uniform in the dimension and is not optimized.
\end{abstract}

\section{Introduction}

\subsection{Background and the source problem}

For \(A=(A_{ij})\in\C^{n\times n}\), its permanent is
\[
  \per(A)=\sum_{\sigma\in S_n}\prod_{i=1}^n A_{i,\sigma(i)}.
\]
When \(A\) is Hermitian positive semidefinite, the permanent is
nonnegative and admits a useful complex Gaussian representation.  The
permanent of a positive semidefinite matrix is also monotone in the
Loewner order; both facts will be proved below.

There are two related questions: how accurately a permanent can be
approximated, and how small it must be when the matrix falls below the
identity. For the first, Anari, Gurvits, Oveis Gharan, and Saberi
\cite[Theorem~1 and Definition~1]{AGGS17} obtained a deterministic
\(e^{(\gamma+1)n}\)-approximation through a diagonal-majorant relaxation;
here \(\gamma\) is Euler's constant. Yuan and Parrilo
\cite[Corollary~1.2]{YP22} sharpened the guarantee for that relaxation
using its connection with products of linear forms and low-rank
solutions. Ebrahimnejad, Nagda, and Oveis Gharan
\cite[Theorems~1.1--1.2]{ENO24} subsequently improved the approximation
exponent below \(\gamma+1\) and established hardness below \(\gamma\).
Anari and Ebrahimnejad \cite[Theorem~1]{AE26} have now obtained the
optimal \(e^{(\gamma+o(1))n}\) exponent. The present paper concerns
the second question, a structural inequality for each individual matrix.

In their work on approximating positive semidefinite permanents,
Ebrahimnejad, Nagda, and Oveis Gharan established the following
trace-sensitive estimate.

\begin{theorem}[Ebrahimnejad--Nagda--Oveis Gharan
  {\cite[Lemma~1.3]{ENO24}}]\label{thm:source}
Let \(0\leq\varepsilon\leq 1\), and let \(A\in\C^{n\times n}\) be
Hermitian with
\[
  0\preceq A\preceq I_n
  \qquad\text{and}\qquad
  \tr(A)\leq(1-\varepsilon)n.
\]
Then
\[
  \per(A)\leq\left(1-\frac{\varepsilon^2}{20}\right)^n.
\]
\end{theorem}

In Section~1.4 of \cite{ENO24}, the authors identify the
\(O(\varepsilon^2)\) dependence in Theorem~\ref{thm:source} as the
bottleneck to a better approximation ratio and conjecture that it can be
improved to \(O(\varepsilon)\).  Since the estimate in
Theorem~\ref{thm:source} is expressed through its base, the corresponding
quantitative target is the following.

\begin{conjecture}[Linear form of the source-paper target
  {\cite[Section~1.4]{ENO24}}]\label{conj:source}
There is a universal constant \(c>0\) such that, for every
\(0\leq\varepsilon\leq1\) and every Hermitian matrix \(A\) satisfying
\[
  0\preceq A\preceq I_n,
  \qquad
  \tr(A)\leq(1-\varepsilon)n,
\]
one has
\[
  \per(A)\leq(1-c\varepsilon)^n.
\]
\end{conjecture}

\subsection{Contribution}

The main result establishes Conjecture~\ref{conj:source} through an
exponential estimate in the actual trace deficit.

\begin{theorem}[Trace-deficit decay]\label{thm:main}
For every \(n\geq1\) and every Hermitian matrix
\(A\in\C^{n\times n}\) with \(0\preceq A\preceq I_n\),
\begin{equation}\label{eq:main}
  \per(A)\leq
  \exp\!\left(-\frac{1}{68}\tr(I_n-A)\right).
\end{equation}
\end{theorem}

\begin{corollary}[Linear dependence on \(\varepsilon\)]
\label{cor:linear}
Under the hypotheses of Conjecture~\ref{conj:source},
\[
  \per(A)\leq e^{-\varepsilon n/68}
  \leq(1-c\varepsilon)^n,
  \qquad
  c=1-e^{-1/68}>0.
\]
\end{corollary}

The proof has two principal components.

\begin{enumerate}
\item The local estimate in Theorem~\ref{thm:local} shows that, for
  \(K\succeq0\) of sufficiently small operator norm,
  \[
    \log\per((I_n+K)^{-1})
      \leq-\tr(K)+17\tr(K^2).
  \]
  Its linear term comes from an exact Gaussian density calculation, while
  Lemma~\ref{lem:offdiag} keeps the quadratic error proportional to
  \(\tr(K^2)\), rather than to \((\tr K)^2\).

\item Lemma~\ref{lem:majorant} compares a general contraction
  \(A=I_n-D\) to the rational majorant
  \((I_n+\theta D)^{-1}\) in Loewner order.  Taking
  \(\theta=1/34\), applying Theorem~\ref{thm:local}, and using
  \(D^2\preceq D\) yields Theorem~\ref{thm:main}.
\end{enumerate}

\subsection{Intuition and related methods}

For a diagonal contraction, the scalar inequality
\(a\leq e^{-(1-a)}\) immediately gives
\(\per(A)\leq e^{-\tr(I-A)}\). Off-diagonal entries introduce
additional permutation terms, and Example~\ref{ex:projection} shows
that this constant cannot hold for all contractions. Nevertheless,
the total spectral deficit remains the right quantity. The spectral
cutoff in the proof of \cite[Lemma~1.3]{ENO24} first finds sufficiently
many eigenvalues a sufficient distance below one. Both quantities cost
a factor of the normalized deficit. The rational majorant above
instead shrinks every deficit by the same fixed factor and retains
their entire sum.

The local calculation explains why this is possible. Gaussian Wick
identities for PSD permanents are standard; see
\cite[Lemma~2.9]{ENO24}. Barvinok \cite[Theorem~1.1 and Section~2.1]{Bar20}
uses such an integral representation for an approximation scheme when
the eigenvalues lie in \([1,2]\), and \cite[Lemma~3.2]{ENO24} uses it
to bound permanents by determinants. Here a change of density absorbs
the product of squared coordinates into independent size-biased
complex Gaussian variables. Their expected quadratic form is
\(2\tr K\), whereas the determinant factor contributes at most
\(\tr K\). This leaves a negative linear term. The essential estimate
is that its fluctuation costs only \(O(\tr K^2)\).

The random partition and Gaussian linearization used to control that
fluctuation follow the proof strategy of Rudelson and Vershynin
\cite[proof of Theorem~1.1, Steps~2--4]{RV13}. The auxiliary-Gaussian
comparison also appears in Hsu, Kakade, and Zhang
\cite[Theorem~1 and Remark~2]{HKZ12}. These are precedents for the
method, rather than statements of the permanent inequality. Each
complex coordinate here gives an independent two-dimensional real
block; its real and imaginary parts are dependent after size biasing.
Lemma~\ref{lem:offdiag} therefore gives the block argument explicitly,
with constants sufficient for the application. The exact Gamma
transform handles the diagonal part separately.

Corollary~\ref{cor:linear} provides the replacement requested in
\cite[Section~1.4]{ENO24}. It is not needed to claim the current
best approximation ratio, which is already supplied by \cite{AE26}.
The entropic upper certificate in \cite[Eq.~(4) and Theorem~7]{AE26}
does not by itself give trace-deficit decay: on \(A=aI_n\), \(a>0\),
it equals \((4a/e)^n\). Indeed, its logarithm is the maximum of
\[
 n\log a+\sum_i\log X_{ii}+\log\det X-\tr X+n
 \quad (X\succ0).
\]
Hadamard's determinant inequality bounds this by
\(n\log a+\sum_i(2\log X_{ii}-X_{ii}+1)\).
Each summand is maximized at \(X_{ii}=2\), and \(X=2I_n\)
attains equality. Thus this certificate exceeds one for
\(e/4<a<1\), even though the trace deficit is positive.
Theorem~\ref{thm:main} supplies a direct pointwise estimate; its
constant is not asserted to be optimal.


Another algorithmic upper bound is the permanent process of Laddha
and Pittu \cite[Algorithm~1 and Theorem~1.3]{LP25}, valid for real PSD
matrices as well as nonnegative matrices. Its elimination-type
certificate need not decay on contractions: on the rank-one projection
\(J_n/n\), where \(J_n\) is the all-ones matrix, each step doubles
all entries of the remaining submatrix. The product of its pivots is
therefore \(2^{n(n-1)/2}/n^n\), which already exceeds one at \(n=7\).
Yi's recent deterministic approximation scheme
\cite[Theorem~1.1(b)]{Yi26} instead treats nonnegative matrices with
dense support and nonzero entries in a fixed positive interval.
That input regime differs from arbitrary complex PSD contractions.

\section{Gaussian preliminaries}

We write \(X^*\) for the conjugate transpose of a complex matrix \(X\).
The symbols \(\opnorm{\cdot}\) and \(\fnorm{\cdot}\) denote the operator
and Frobenius norms.  A standard circular complex Gaussian random
variable has density
\[
  d\gamma(w)=\frac{1}{\pi}e^{-|w|^2}\,d^2w
  \qquad (w\in\C).
\]
Equivalently, \(W=(G_1+iG_2)/\sqrt2\), where \(G_1,G_2\) are independent
standard real Gaussian variables.

\subsection{Wick's formula}

The following representation is the complex version of Wick's formula.
It also appears as Lemma~2.9 in \cite{ENO24}.

\begin{lemma}[Complex Gaussian representation]\label{lem:wick}
Let \(B\in\C^{n\times n}\) be Hermitian positive semidefinite, and let
\(Z\) be a centered circular complex Gaussian vector with covariance
\(\E[ZZ^*]=B\).  Then
\begin{equation}\label{eq:wick}
  \per(B)=\E\prod_{i=1}^n |Z_i|^2.
\end{equation}
\end{lemma}

\begin{proof}
For a circular complex Gaussian vector, the only nonzero pairings in the
mixed moment
\[
  \E[Z_1\cdots Z_n\overline{Z_1}\cdots\overline{Z_n}]
\]
pair each unbarred coordinate with a barred coordinate.  Such a pairing
is specified by a permutation \(\sigma\in S_n\), and its contribution is
\[
  \prod_{i=1}^n \E[Z_i\overline{Z_{\sigma(i)}}]
  =\prod_{i=1}^n B_{i,\sigma(i)}.
\]
Summing over all \(\sigma\in S_n\) gives \eqref{eq:wick}.  A singular
covariance follows either from the same moment identity or by
approximation with \(B+\delta I_n\).
\end{proof}

\subsection{A size-biased complex Gaussian law}

Define a probability measure \(\nu_1\) on \(\C\) by
\begin{equation}\label{eq:nu}
  d\nu_1(w)=\frac{1}{\pi}|w|^2e^{-|w|^2}\,d^2w.
\end{equation}
It is normalized because \(\E_\gamma|W|^2=1\).  The next lemma records
both a subgaussian estimate in real coordinates and the exact radial
Laplace transform.

\begin{lemma}[Size-biased Gaussian identities]\label{lem:sizebiased}
Let \(W\) have law \(\nu_1\), and set
\[
  \xi=(\sqrt2\,\Re W,\sqrt2\,\Im W)\in\R^2.
\]
Then, for every \(u\in\R^2\),
\begin{equation}\label{eq:blockmgf}
  \E e^{u^{\mathsf T}\xi}
  =\left(1+\frac{\lVert u\rVert_2^2}{2}\right)
    e^{\lVert u\rVert_2^2/2}
  \leq e^{\lVert u\rVert_2^2}.
\end{equation}
Moreover, \(R=|W|^2\) has the \(\operatorname{Gamma}(2,1)\) density
\(xe^{-x}\) on \([0,\infty)\), and therefore
\begin{equation}\label{eq:radial}
  \E e^{-aR}=(1+a)^{-2},
  \qquad
  \E R=2
  \qquad (a\geq0).
\end{equation}
\end{lemma}

\begin{proof}
Under the untilted law \(\gamma\), the vector
\((\sqrt2\,\Re W,\sqrt2\,\Im W)\) is a standard real Gaussian vector
\(G=(G_1,G_2)\), while \(|W|^2=(G_1^2+G_2^2)/2\).  Hence, for every
nonnegative measurable function \(f\),
\[
  \E_{\nu_1}f(\xi)
  =\frac12\E\!\left[(G_1^2+G_2^2)f(G)\right].
\]
Differentiating the standard Gaussian moment-generating function gives
\[
  \E[G_j^2e^{u^{\mathsf T}G}]
    =(1+u_j^2)e^{\lVert u\rVert_2^2/2}.
\]
Summing over \(j=1,2\) and dividing by \(2\) yields the equality in
\eqref{eq:blockmgf}.  Its inequality follows from
\(1+t/2\leq e^{t/2}\) for \(t\geq0\).

Under \(\gamma\), the variable \(|W|^2\) has density \(e^{-x}\) on
\([0,\infty)\).  The size bias in \eqref{eq:nu} changes this to
\(xe^{-x}\).  Direct integration gives
\[
  \int_0^\infty xe^{-(1+a)x}\,dx=(1+a)^{-2},
\]
and differentiating at \(a=0\) gives \(\E R=2\).
\end{proof}

\begin{corollary}[Product-block linear MGF]\label{cor:productmgf}
Let \(\xi_1,\ldots,\xi_n\) be independent copies of the vector in
Lemma~\ref{lem:sizebiased}, and put
\(\Xi=(\xi_1,\ldots,\xi_n)\in\R^{2n}\).  Then
\[
  \E e^{v^{\mathsf T}\Xi}\leq e^{\lVert v\rVert_2^2}
  \qquad\text{for every }v\in\R^{2n}.
\]
\end{corollary}

\begin{proof}
Apply \eqref{eq:blockmgf} to each two-dimensional block of \(v\) and
multiply the resulting estimates.
\end{proof}

\section{An off-diagonal quadratic MGF estimate}

The local permanent estimate will separate the diagonal and
off-diagonal parts of a quadratic form.  The diagonal transform is
explicit by \eqref{eq:radial}.  The following dimension-free estimate
controls the off-diagonal part.

\begin{lemma}[Block-off-diagonal quadratic estimate]
\label{lem:offdiag}
Let \(\Xi=(\xi_1,\ldots,\xi_n)\) be as in
Corollary~\ref{cor:productmgf}.  Let \(R\) be a real symmetric
\(2n\times2n\) matrix whose diagonal \(2\times2\) blocks vanish.  If
\begin{equation}\label{eq:offdiagcondition}
  64s^2\opnorm{R}^2\leq\frac12,
\end{equation}
then
\begin{equation}\label{eq:offdiagbound}
  \log\E e^{s\Xi^{\mathsf T}R\Xi}
  \leq32s^2\fnorm{R}^2.
\end{equation}
\end{lemma}

\begin{proof}
Choose a random set \(\Lambda\subseteq\{1,\ldots,n\}\) by including
each block index independently with probability \(1/2\), and define
\[
  X_\Lambda
  =\sum_{\substack{i\in\Lambda\\j\notin\Lambda}}
    \xi_i^{\mathsf T}R_{ij}\xi_j.
\]
Because the diagonal blocks of \(R\) vanish, every ordered pair
\((i,j)\) with \(i\neq j\) occurs in this sum with probability \(1/4\).
Consequently,
\begin{equation}\label{eq:randomcutidentity}
  \Xi^{\mathsf T}R\Xi=4\E_\Lambda X_\Lambda.
\end{equation}
For every fixed value of \(\Xi\), convexity of the exponential gives
\begin{equation}\label{eq:cutjensen}
  e^{s\Xi^{\mathsf T}R\Xi}
  \leq\E_\Lambda e^{4sX_\Lambda}.
\end{equation}

Fix \(\Lambda\).  Write \(a=\Xi_\Lambda\) and
\(b=\Xi_{\Lambda^c}\), and let \(T_\Lambda\) be the rectangular
cross-cut block of \(R\) for which
\[
  X_\Lambda=b^{\mathsf T}T_\Lambda a.
\]
For \(u\in\R\), conditioning on \(a\) and applying
Corollary~\ref{cor:productmgf} to the independent blocks in \(b\) yields
\begin{equation}\label{eq:firstlinear}
  \E_b[e^{uX_\Lambda}\mid a]
  \leq\exp\!\left(u^2\lVert T_\Lambda a\rVert_2^2\right).
\end{equation}
Let \(g\) be a standard real Gaussian vector of the row dimension of
\(T_\Lambda\), independent of all other variables.  Gaussian
linearization and another use of Corollary~\ref{cor:productmgf} give
\begin{align}
  e^{u^2\lVert T_\Lambda a\rVert_2^2}
  &=\E_g e^{\sqrt2|u|g^{\mathsf T}T_\Lambda a},\label{eq:linearize}\\
  \E_a e^{\sqrt2|u|g^{\mathsf T}T_\Lambda a}
  &\leq
  \exp\!\left(2u^2\lVert T_\Lambda^{\mathsf T}g\rVert_2^2\right).
  \label{eq:secondlinear}
\end{align}
Combining \eqref{eq:firstlinear}--\eqref{eq:secondlinear}, and denoting
the singular values of \(T_\Lambda\) by
\(\sigma_1,\ldots,\sigma_m\), gives
\begin{equation}\label{eq:gaussianquadratic}
  \E e^{uX_\Lambda}
  \leq
  \prod_{r=1}^m(1-4u^2\sigma_r^2)^{-1/2},
\end{equation}
provided \(4u^2\opnorm{T_\Lambda}^2<1\).

For \(0\leq x\leq1/2\), the elementary inequality
\(-\frac12\log(1-x)\leq x\) holds.  It follows from
\eqref{eq:gaussianquadratic} that, whenever
\(4u^2\opnorm{T_\Lambda}^2\leq1/2\),
\begin{equation}\label{eq:crossmgf}
  \log\E e^{uX_\Lambda}
  \leq4u^2\fnorm{T_\Lambda}^2.
\end{equation}
The cross-cut block is a rectangular compression of \(R\), so
\[
  \opnorm{T_\Lambda}\leq\opnorm{R}.
\]
In the decomposition into the coordinates indexed by \(\Lambda\) and
\(\Lambda^c\), the two cross-cut blocks of the symmetric matrix \(R\)
are \(T_\Lambda\) and \(T_\Lambda^{\mathsf T}\).  Thus
\begin{equation}\label{eq:crossfrobenius}
  2\fnorm{T_\Lambda}^2\leq\fnorm{R}^2.
\end{equation}

Set \(u=4s\).  The hypothesis \eqref{eq:offdiagcondition} implies the
condition for \eqref{eq:crossmgf}, and hence
\[
  \log\E e^{4sX_\Lambda}
  \leq64s^2\fnorm{T_\Lambda}^2
  \leq32s^2\fnorm{R}^2.
\]
This bound is uniform in \(\Lambda\).  Taking expectations in
\eqref{eq:cutjensen} and then applying the uniform bound proves
\eqref{eq:offdiagbound}.
\end{proof}

\section{Local stability near the identity}

We now combine the exact radial transform and
Lemma~\ref{lem:offdiag}.  The resulting estimate is local only in
operator norm and has no dependence on the dimension.

\begin{theorem}[Local permanent stability]\label{thm:local}
Let \(K\in\C^{n\times n}\) be Hermitian positive semidefinite and
satisfy
\[
  \opnorm{K}\leq\frac{\sqrt2}{17}.
\]
Then
\begin{equation}\label{eq:local}
  \log\per((I_n+K)^{-1})
  \leq-\tr(K)+17\tr(K^2).
\end{equation}
\end{theorem}

\begin{proof}
Put \(B=(I_n+K)^{-1}\).  The matrix \(B\) is positive definite.  If
\(Z\) is circular complex Gaussian with covariance \(B\), then
Lemma~\ref{lem:wick} and the Gaussian density give
\begin{align}
  \per(B)
  &=
  \frac{1}{\pi^n\det B}
  \int_{\C^n}
    \left(\prod_{i=1}^n|z_i|^2\right)
    e^{-z^*B^{-1}z}\,d^{2n}z \notag\\
  &=
  \det(I_n+K)\,
  \E_\nu e^{-W^*KW},\label{eq:changeofmeasure}
\end{align}
where \(\nu=\nu_1^{\otimes n}\), and the coordinates
\(W_1,\ldots,W_n\) are independent with the density
\eqref{eq:nu}.

Write \(k_i=K_{ii}\geq0\) and decompose the real random variable
\[
  Q=W^*KW=Q_{\mathrm d}+Q_{\mathrm o},
\]
where
\[
  Q_{\mathrm d}=\sum_{i=1}^n k_i|W_i|^2,
  \qquad
  Q_{\mathrm o}=\sum_{i\neq j}\overline{W_i}K_{ij}W_j.
\]
By \eqref{eq:radial},
\[
  \E_\nu Q_{\mathrm d}=2\tr(K),
  \qquad
  \E_\nu Q_{\mathrm o}=0.
\]
Set \(U_{\mathrm d}=Q_{\mathrm d}-2\tr(K)\), and choose the conjugate
Hölder exponents
\[
  p=17,
  \qquad
  q=\frac{17}{16}.
\]
Hölder's inequality yields
\begin{equation}\label{eq:holder}
  \E_\nu e^{-(Q-2\tr K)}
  \leq
  \bigl(\E_\nu e^{-pU_{\mathrm d}}\bigr)^{1/p}
  \bigl(\E_\nu e^{-qQ_{\mathrm o}}\bigr)^{1/q}.
\end{equation}

For the diagonal factor, the exact transform \eqref{eq:radial} gives
\[
  \E e^{-pk_i(|W_i|^2-2)}
  =e^{2pk_i}(1+pk_i)^{-2}.
\]
Independence therefore implies
\begin{equation}\label{eq:diagonalexact}
  \frac1p\log\E_\nu e^{-pU_{\mathrm d}}
  =
  \sum_{i=1}^n
  \left(2k_i-\frac2p\log(1+pk_i)\right).
\end{equation}
The elementary inequality
\(\log(1+x)\geq x-x^2/2\) for \(x\geq0\) turns
\eqref{eq:diagonalexact} into
\begin{equation}\label{eq:diagonalbound}
  \frac1p\log\E_\nu e^{-pU_{\mathrm d}}
  \leq17\sum_{i=1}^n k_i^2.
\end{equation}

It remains to control the off-diagonal factor.  Write
\(K=P+iS\), where \(P\) is real symmetric and \(S\) is real
skew-symmetric.  Its realification is
\[
  \mathcal R(K)=
  \begin{pmatrix}
    P&-S\\
    S&P
  \end{pmatrix}.
\]
For
\(\xi_i=(\sqrt2\,\Re W_i,\sqrt2\,\Im W_i)\) and
\(\Xi=(\xi_1,\ldots,\xi_n)\), after the harmless orthogonal
permutation that groups coordinates by \(i\), one has
\[
  W^*KW=\Xi^{\mathsf T}M\Xi,
  \qquad
  M=\frac12\mathcal R(K).
\]
Let \(H=K-\diag(K)\), and let \(M_{\mathrm o}\) be obtained from
\(M\) by deleting its diagonal \(2\times2\) blocks.  Then
\[
  Q_{\mathrm o}=\Xi^{\mathsf T}M_{\mathrm o}\Xi,
  \qquad
  M_{\mathrm o}=\frac12\mathcal R(H)
\]
up to the same coordinate permutation.  The realification identities
give
\begin{equation}\label{eq:realificationnorms}
  \opnorm{M_{\mathrm o}}=\frac12\opnorm{H},
  \qquad
  \fnorm{M_{\mathrm o}}^2=\frac12\fnorm{H}^2.
\end{equation}
Since \(K\succeq0\),
\[
  \opnorm{\diag(K)}=\max_i k_i\leq\opnorm{K}.
\]
It follows from \eqref{eq:realificationnorms} that
\begin{equation}\label{eq:offop}
  \opnorm{M_{\mathrm o}}
  \leq\frac12\bigl(\opnorm{K}+\opnorm{\diag(K)}\bigr)
  \leq\opnorm{K}.
\end{equation}
The norm hypothesis and \(q=17/16\) now give the exact threshold
\[
  64q^2\opnorm{M_{\mathrm o}}^2
  \leq
  64\left(\frac{17}{16}\right)^2
     \left(\frac{\sqrt2}{17}\right)^2
  =\frac12.
\]
Lemma~\ref{lem:offdiag}, applied with \(R=M_{\mathrm o}\) and \(s=-q\),
therefore yields
\[
  \log\E_\nu e^{-qQ_{\mathrm o}}
  \leq32q^2\fnorm{M_{\mathrm o}}^2.
\]
Because \(H\) is Hermitian with zero diagonal,
\[
  \fnorm{M_{\mathrm o}}^2
  =\frac12\fnorm{H}^2
  =\sum_{i<j}|K_{ij}|^2.
\]
Since \(32q=34\), we obtain
\begin{equation}\label{eq:offdiagonalbound}
  \frac1q\log\E_\nu e^{-qQ_{\mathrm o}}
  \leq34\sum_{i<j}|K_{ij}|^2.
\end{equation}

Combining \eqref{eq:holder}, \eqref{eq:diagonalbound}, and
\eqref{eq:offdiagonalbound}, and using
\[
  \tr(K^2)
  =\sum_i k_i^2+2\sum_{i<j}|K_{ij}|^2,
\]
gives
\begin{equation}\label{eq:centeredlaplace}
  \log\E_\nu e^{-(Q-2\tr K)}
  \leq17\tr(K^2).
\end{equation}
Equivalently,
\[
  \log\E_\nu e^{-Q}
  \leq-2\tr(K)+17\tr(K^2).
\]
Finally, applying \(\log(1+x)\leq x\) to the eigenvalues of \(K\) gives
\(\log\det(I_n+K)\leq\tr(K)\).  Together with
\eqref{eq:changeofmeasure}, this implies
\[
  \log\per(B)
  \leq-\tr(K)+17\tr(K^2),
\]
which is \eqref{eq:local}.
\end{proof}

\section{Loewner comparison and the global estimate}

For completeness, we first prove the monotonicity used in the source
paper as Lemma~2.8 \cite{ENO24}.

\begin{lemma}[Loewner monotonicity]\label{lem:monotonicity}
If \(0\preceq A\preceq B\) are Hermitian \(n\times n\) matrices, then
\[
  \per(A)\leq\per(B).
\]
\end{lemma}

\begin{proof}
In \((\C^n)^{\otimes n}\), define
\[
  v=\frac1{\sqrt{n!}}
  \sum_{\sigma\in S_n}
  e_{\sigma(1)}\otimes\cdots\otimes e_{\sigma(n)}.
\]
Expanding the matrix coefficient and grouping pairs of permutations by
their relative permutation gives
\begin{equation}\label{eq:tensorpermanent}
  \ip{v}{A^{\otimes n}v}=\per(A).
\end{equation}
Moreover, the telescoping identity
\[
  B^{\otimes n}-A^{\otimes n}
  =
  \sum_{j=1}^n
  A^{\otimes(j-1)}
  \otimes(B-A)
  \otimes B^{\otimes(n-j)}
\]
expresses the difference as a sum of positive semidefinite matrices.
Hence \(A^{\otimes n}\preceq B^{\otimes n}\).  Taking the matrix
coefficient at \(v\) and using \eqref{eq:tensorpermanent} proves the
claim.
\end{proof}

\begin{lemma}[Rational Loewner majorant]\label{lem:majorant}
Let \(0\preceq A\preceq I_n\), put \(D=I_n-A\), and let
\(0\leq\theta\leq1\).  Then
\[
  A\preceq(I_n+\theta D)^{-1}.
\]
\end{lemma}

\begin{proof}
For every \(d\in[0,1]\),
\begin{equation}\label{eq:scalarmajorant}
  \frac1{1+\theta d}-(1-d)
  =
  \frac{d(1-\theta+\theta d)}{1+\theta d}
  \geq0.
\end{equation}
Since the spectrum of \(D\) is contained in \([0,1]\), applying
\eqref{eq:scalarmajorant} through functional calculus gives
\[
  I_n-D\preceq(I_n+\theta D)^{-1}.
\]
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:main}]
Set \(D=I_n-A\), so that \(0\preceq D\preceq I_n\), and choose
\[
  \theta=\frac1{34},
  \qquad
  K=\theta D,
  \qquad
  B=(I_n+K)^{-1}.
\]
Lemma~\ref{lem:majorant} gives \(A\preceq B\).  Furthermore,
\[
  \opnorm{K}\leq\frac1{34}\leq\frac{\sqrt2}{17},
\]
so Theorem~\ref{thm:local} applies.  Since \(D^2\preceq D\),
\[
  \tr(K)=\theta\tr(D),
  \qquad
  \tr(K^2)=\theta^2\tr(D^2)
  \leq\theta^2\tr(D).
\]
Therefore,
\begin{align*}
  \log\per(B)
  &\leq-\tr(K)+17\tr(K^2)\\
  &\leq-(\theta-17\theta^2)\tr(D)
   =-\frac1{68}\tr(D).
\end{align*}
By Lemma~\ref{lem:monotonicity},
\[
  \per(A)\leq\per(B)
  \leq\exp\!\left(-\frac1{68}\tr(I_n-A)\right).
\]
\end{proof}

\begin{proof}[Proof of Corollary~\ref{cor:linear}]
The trace hypothesis gives
\(\tr(I_n-A)\geq\varepsilon n\), so Theorem~\ref{thm:main} implies
\[
  \per(A)\leq e^{-\varepsilon n/68}.
\]
The function \(x\mapsto e^{-x/68}\) is convex.  On \([0,1]\), it
therefore lies below the chord joining its endpoint values:
\[
  e^{-\varepsilon/68}
  \leq(1-\varepsilon)+\varepsilon e^{-1/68}
  =1-(1-e^{-1/68})\varepsilon.
\]
Raising this scalar inequality to the \(n\)th power proves the result.
\end{proof}

\section{Examples and remarks}

\begin{example}[Diagonal contractions]\label{ex:diagonal}
For \(A=\diag(a_1,\ldots,a_n)\) with \(0\leq a_i\leq1\),
\[
  \per(A)=\prod_{i=1}^n a_i
  \leq\exp\!\left(-\sum_{i=1}^n(1-a_i)\right)
  =e^{-\tr(I_n-A)}.
\]
Here the first inequality is the scalar bound
\(\log a\leq a-1\), with the case \(a=0\) understood by continuity.
Thus the trace deficit is the natural first-order quantity already in
the diagonal case, although the universal constant furnished by the
noncommutative argument is smaller.
\end{example}

\begin{example}[A restriction on the universal constant]\label{ex:projection}
The rank-one projection
\[
 P=\frac12\begin{pmatrix}1&1\\1&1\end{pmatrix}
\]
has eigenvalues zero and one, \(\per(P)=1/4+1/4=1/2\), and
\(\tr(I_2-P)=1\). For the block diagonal contraction consisting
of \(m\) copies of \(P\), a nonzero permutation term must preserve
each block. The permanent is therefore \(2^{-m}\), while the
trace deficit is \(m\). Consequently any universal inequality
\(\per(A)\leq e^{-\kappa\tr(I-A)}\) must have
\(\kappa\leq\log 2\). In particular, the diagonal-case constant
one does not extend to all PSD contractions.
\end{example}

\begin{remark}[Where the dimension-free error enters]
The key feature of Lemma~\ref{lem:offdiag} is its Frobenius-norm error.
After realification, this becomes the off-diagonal part of
\(\tr(K^2)\).  Together with the exact Gamma transform of the diagonal
part, the entire second-order error in Theorem~\ref{thm:local} is
\(17\tr(K^2)\).  For \(K=\theta D\) and \(0\preceq D\preceq I_n\),
this is at most \(17\theta^2\tr(D)\), which can be absorbed into the
linear term uniformly in \(n\).
\end{remark}

\begin{remark}[Constants]
The choices \(p=17\), \(q=17/16\), and \(\theta=1/34\) were made to
keep the threshold arithmetic transparent.  They are not expected to
be optimal.  The purpose of the estimate is the linear dependence on
\(\tr(I_n-A)\), which is exactly what converts the quadratic
\(\varepsilon\)-dependence in Theorem~\ref{thm:source} into the linear
dependence requested in \cite[Section~1.4]{ENO24}.
\end{remark}

\begin{thebibliography}{9}
\raggedright

\bibitem{ENO24}
F.~Ebrahimnejad, A.~Nagda, and S.~Oveis Gharan,
\emph{On approximability of the permanent of PSD matrices},
STOC 2025, 625--630. Numbered references use the full version,
arXiv:2404.10959v1, 2024.
\url{https://arxiv.org/abs/2404.10959}.

\bibitem{AE26}
N.~Anari and F.~Ebrahimnejad,
\emph{Optimal \(e^{(\gamma+o(1))n}\)-Approximation of the Permanent of
Positive Semidefinite Matrices},
arXiv:2605.21946, 2026.
\url{https://arxiv.org/abs/2605.21946}.


\bibitem{AGGS17}
N.~Anari, L.~Gurvits, S.~Oveis Gharan, and A.~Saberi,
\emph{Simply exponential approximation of the permanent of positive
semidefinite matrices}, FOCS 2017, 914--925.
\url{https://arxiv.org/abs/1704.03486}.

\bibitem{YP22}
C.~Yuan and P.~A.~Parrilo,
\emph{Maximizing products of linear forms, and the permanent of positive
semidefinite matrices}, Mathematical Programming \textbf{193} (2022), 499--510.
\url{https://doi.org/10.1007/s10107-021-01616-3}.

\bibitem{Bar20}
A.~Barvinok,
\emph{A remark on approximating permanents of positive definite matrices},
arXiv:2005.06344, 2020.\par
\url{https://arxiv.org/abs/2005.06344}.

\bibitem{RV13}
M.~Rudelson and R.~Vershynin,
\emph{Hanson--Wright inequality and sub-Gaussian concentration},
Electronic Communications in Probability \textbf{18} (2013), no.~82, 1--9.
\url{https://arxiv.org/abs/1306.2872}.

\bibitem{HKZ12}
D.~Hsu, S.~M.~Kakade, and T.~Zhang,
\emph{A tail inequality for quadratic forms of subgaussian random vectors},
Electronic Communications in Probability \textbf{17} (2012), no.~52, 1--6.
\url{https://arxiv.org/abs/1110.2842}.


\bibitem{LP25}
A.~Laddha and M.~R.~Pittu,
\emph{An algorithmic upper bound for permanents via a permanental
Schur inequality}, arXiv:2509.08121, 2025.
\url{https://arxiv.org/abs/2509.08121}.

\bibitem{Yi26}
Z.~Yi,
\emph{Diffuse Gaussian truncation for deterministic approximate counting},
arXiv:2609.04079, 2026.
\url{https://arxiv.org/abs/2609.04079}.

\end{thebibliography}

\end{document}