Content-Type: multipart/mixed; boundary="-------------1705030935824"
This is a multi-part message in MIME format.
---------------1705030935824
Content-Type: text/plain; name="17-54.comments"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment; filename="17-54.comments"
8 pages
---------------1705030935824
Content-Type: text/plain; name="17-54.keywords"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment; filename="17-54.keywords"
0 - 1 matrices, permanents, statistical independence
---------------1705030935824
Content-Type: application/x-tex; name="typing.tex"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline; filename="typing.tex"
\documentclass{article}
\usepackage{amsfonts,amsmath}
\mathchardef\mhyphen="2D % Define a "math hyphen"
\usepackage[a4paper]{geometry}
\usepackage{microtype}
\usepackage{relsize}
\def\Z{\mathbb Z}
\def\zo/{$0\mkern2mu\mhyphen1$}%0-1
\def\Ex{E_{\times}}
\def\nn/{$n \times n$}
\def\a{\alpha}
\newtheorem{conj}{Conjecture}
\DeclareMathOperator\perm{perm}
\title{On the Approximate Asymptotic Statistical Independence of the Permanents of 0-1 Matrices, I}
\date{\today}
\author{Paul Federbush\\
Department of Mathematics\\
University of Michigan\\
Ann Arbor, MI, 48109-1043}
\begin{document}
\maketitle
\begin{abstract}
We consider the ensemble of $n \times n$ \zo/ matrices with all column and row sums equal $r$. We give this ensemble the uniform weighting to construct a measure $E$. We conjecture
\begin{equation}
\label{A1}
\tag{A1}
E\left(\prod_{i=1}^N \left(\perm_{m_i}(A)\right)\right) = \prod_{i=1}^N \left(E\left(\perm_{m_i}(A)\right)\right) \left(1+\mathcal{O}\left(1/n^3\right)\right)
\end{equation}
In this paper we prove
\begin{equation}
\label{A2}
\tag{A2}
E_1\left(\prod_{i=1}^N \left(\perm_{m_i}(A)\right)\right) = \prod_{i=1}^N \left(E_1\left(\perm_{m_i}(A)\right)\right)\left(1+\mathcal{O}\left(1/n^2\right)\right)
\end{equation}
and in the sequel paper, number II in this sequence, we show
\begin{equation}
\label{A3}
\tag{A3}
E_1\left(\prod_{i=1}^N \left(\perm_{m_i}(A)\right)\right) = \prod_{i=1}^N \left(E_1\left(\perm_{m_i}(A)\right)\right) \left(1+\mathcal{O}\left(1/n^3\right)\right)
\end{equation}
where $E_1$ is the measure constructed on the ensemble of $n \times n$ matrices with non-negative integer entries realized as the sum of $r$ random permutation matrices. $E_1$ is often used as an ``approximation'' to $E$, and the truth of \eqref{A3} explains why we support the conjecture \eqref{A1}.
\end{abstract}
\section{Introduction}
We consider the ensemble of $n\times n$ \zo/ matrices whose row and column sums all equal $r$. We define the uniform measure in this ensemble, calling it $E$. Our conjecture is that
\begin{equation}
\label{1.1}
\tag{1.1}
E\left(\prod_{i=1}^N \left(\perm_{m_i}(A)\right)\right) = \prod_{i=1}^N \left(E\left(\perm_{m_i}(A)\right)\right) \left(1+\mathcal{O}\left(1/n^3\right)\right)
\end{equation}
We let $E_1$ be the measure on $n \times n$ matrices with non-negative integer entries, constructed as the uniform measure on a sum of $r$ random permutations on $n$ objects. We here prove
\begin{equation}
\label{1.2}
\tag{1.2}
E_1\left(\prod_{i=1}^N \left(\perm_{m_i}(A)\right)\right) = \prod_{i=1}^N \left(E_1\left(\perm_{m_i}(A)\right)\right)\left(1+\mathcal{O}\left(1/n^2\right)\right)
\end{equation}
and in a sequel paper that
\begin{equation}
\label{1.3}
\tag{1.3}
E_1\left(\prod_{i=1}^N \left(\perm_{m_i}(A)\right)\right) = \prod_{i=1}^N \left(E_1\left(\perm_{m_i}(A)\right)\right) \left(1+\mathcal{O}\left(1/n^3\right)\right)
\end{equation}
$E_1$ is often used as an `approximation' to $E$. In \cite{f} and \cite{fa} certain aesthetic relations seem to hold in the same form for $E$ and $E_1$ expectations. Similarly we believe eq (\ref{1.3}) presages the truth of eq (\ref{1.1}). However section 7 presents a computation that may cause one some hesitation.
We note that we know eq (\ref{1.3}) does not hold with
$\mathcal{O}\left(1/n^3\right)$ replaced by $\mathcal{O}\left(1/n^5\right)$. We have evidence that $\mathcal{O}\left(1/n^3\right)$ can be replaced by $\mathcal{O}\left(1/n^4\right)$, but proving this, if it is true, is too complex by the techniques we know.
In a future paper I plan to relate eq (\ref{1.1}) and eq (\ref{1.3}) to graph positivity, \cite{bfp}. In particular we plan to use these equations to prove a weak form of the positivity of $\Delta^2 d(i)$, see Section II of \cite{bfp}. It was a study of such `graph positivity' that got me involved with the conjecture of this paper.
One can only appreciate the magic of conjecture eq (\ref{1.1}), or proved results eq (\ref{1.2}) and eq (\ref{1.3}), by seeing the complicated calculations and cancellation involved in the proofs. We do not have any understanding %TBC
why the necessary cancellations take place!
There are some excursions in this paper not necessary to the present calculation that will be useful in the sequel paper. The reader will be forced to embed himself or herself in the world of \cite{f} to follow developments within. But better yet, find another way to attack the study of this conjecture!
A final note before plunging into the calculation, is the observation that both the conjecture of this paper, and the computation in \cite{f}, can be viewed as an asymptotic statistical independence of the permanents of \zo/ matrices.
\section{The Strategy}
We depend on the reader being familiar with the first five pages of \cite{f}. In that paper one studies a product of two permanents, here we deal with a product of $N$ permanents, but the ideas are the same. A single permanent $\perm_m(A)$, we view as a sum of `terms', $\binom{n}{m}^2 m!$ such, each term a product of $m$ `entries', $\prod_{i=1}^N \perm_{m_i}(A)$ we view as a sum of `multiterms', each multiterm a product of $N$ `subterms'. Given a fixed multiterm, let $1 \leq i < j \leq N$, and look at the subterms $i$ and $j$. Each entry in the $j$ subterm is in class $1, 2, 3, 4$, or $5$ with respect to the $i$ subterm, in the language of \cite{f}. In this paper we study those types of multiterms in the expansion of $E_1 \left(\prod_{i=1}^N \perm_{m_i}(A)\right)$ that contribute a value larger than $\mathcal{O}\left(1/n^2\right) E_1 \left(\prod_{i=1}^N \perm_{m_i}(A)\right)$.
More exactly, the sum of all the multiterms of the excluded types is bounded by
\noindent$\mathcal{O}\left(1/n^2\right) E_1 \left(\prod_{i=1}^N \perm_{m_i}(A)\right)$. The result is that we need consider multiterms that have at most one pair $i < j$ of subterms with one entry of subterm $j$ that is in class other than class 1 to the subterm $i$. In other words, of all the $\sum_{j=1}^N m_j$ entries in the multiterm we consider those that have at most two that share a row or a column! In the following sections we will treat each of the types of multiterms that might contribute to a $1/n$ correction in eq (\ref{1.2}): only class 1 entries, a single class 2 entry, a single class 3 or class 4 entry. Loosely speaking, as is easy to believe, each time two entries share a row or a column one loses a power of $n$.
\section{Pure Class 1 Multiterms}
We first consider the multiterms where no two entries share a row or a column. In the factor $\left(1+\mathcal{O}\left(1/n^2\right)\right)$ in eq (\ref{1.2}), these multiterms give rise to the $1$, as well as $\mathcal{O}\left(1/n\right)$ corrections canceled to order $1/n^2$ by contributions of the other type multiterms.
We first write down the exact expression for $\prod_{i=1}^N E_1 \left(\perm_{m_i}(A)\right)$, which we call $I$.
\begin{equation}
\label{3.1}
\tag{3.1}
I = \prod_{k=1}^N \left[\underset{\underset{\sum_i m_{k,i}=m_k}{m_{k,i}}}{\sum} \frac{1}{\left(n!\right)^r} \binom{n}{m_k}^2 m_k! \frac{m_k!}{m_{k,1}! \cdots m_{k,r}!} \prod_i \left(n-m_{k,i}\right)!\right]
\end{equation}
$II$ is then the contribution of all pure class 1 multiterms to $E_1\left(\prod_{i=1}^N \left(\perm_{m_i}(A)\right)\right) $.
\begin{equation}
\label{3.2}
\tag{3.2}
II = \frac{1}{\left(n!\right)^r} \prod_{k=1}^N \left[\underset{\underset{\sum_i m_{k,i}=m_k}{m_{k,i}}}{\sum} \binom{n-\sum_{t