Let $M_n$ be an $n\times n$ random matrix whose entries are independent Rademacher random variables, and put $N=\binom n2$. We prove \[ Pr(M_nM_n^T=M_n^TM_n)=2^{-N+O(n)}. \] This gives the sharp exponential order for the probability that a random sign matrix is normal. The lower bound is supplied by symmetric sign matrices. We also record the immediate consequence that random $0$-$1$ matrices have the same sharp exponential normality probability. The proof of the matching upper bound is combinatorial: after conditioning on the symmetric/skew-symmetric type pattern of the off-diagonal entries, a mod-$4$ reduction gives a system of linear equations over $F_2$; a rank-duality argument converts the sum over type patterns into a count of commuting symmetric pairs over $F_2$; and this count is bounded by summing over rational canonical types, using balanced symmetric bilinear forms and the standard finite-field centralizer formula.
Let $M_n$ be an $n\times n$ matrix with independent uniform sign entries. We prove that there exist absolute constants $C,c>0$ such that, for all sufficiently large $n$, \[ \mathbb{P}\!\left( \left|\operatorname{Per}(M_n)\right| \ge e^{-Cn}\sqrt{n!} \right) \ge 1-n^{-c}. \] Our proof tracks the total squared permanent of minors under successive row exposure. Up to $k=\lfloor n/2\rfloor$, the total squared permanent grows deterministically via the Boolean lattice up-operator; for larger $k$, the row exposure increments are governed by positive semidefinite Rademacher quadratic forms. Therefore, we confirms the exponential scale lower bound suggested by Tao and Vu.
We give explicit complex polynomials $P,Q$ in three independent standard real Gaussian variables such that \[ {\mathbb E}(P^m)=0,\qquad {\mathbb E}(QP^m)=m!\neq0 \] for every $m\geq1$. In natural complex linear coordinates, $P$ has five terms and total degree $4$. Hence the Gaussian Moments Conjecture is false in every dimension $n\geq3$. We also give a six-term cubic example in four variables, which was found first and already proves failure for every $n\geq4$. Both examples follow from the same coefficient identity. The search was prompted by Levent Alp\"oge's public announcement of an explicit three-dimensional counterexample to the Jacobian Conjecture. Although the main theorem of Derksen, van den Essen, and Zhao is stated globally in dimension, its proof has fixed-dimensional content: a noninvertible cubic-homogeneous Keller map in $r$ variables forces the failure of ${\mathrm GMC}(2r)$. Tracking a standard Bass--Connell--Wright reduction of the announced map gives a conservative cubic-homogeneous counterexample in $79$ variables, and hence a route-based failure of ${\mathrm GMC}(158)$. That route is nonconstructive at the final Gaussian step and does not furnish explicit polynomials $P,Q$. The much smaller explicit failures in dimensions $4$ and $3$ below were not derived from the announced Jacobian map.
Let $q$ be an odd prime power, and let $A_n=(a_{ij})\in\mathbb F_q^{n\times n}$ be a random matrix whose entries are independent and uniformly distributed on $\mathbb F_q$. The permanent of $A_n$ is defined by $\operatorname{per}(A_n)=\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)}$, where $S_n$ denotes the symmetric group on $[n]$. Ghasemi, Gross, and Kopparty conjectured the zero-mass asymptotic $\Pr[\operatorname{per}(A_n)=0]=1/q+o(1)$ for every fixed odd prime power $q$, and Hunter, Kwan, and Sauermann subsequently stated its equivalent full-distribution formulation: for every fixed $q$ and every $x\in\mathbb F_q$, \[ \lim_{n\to\infty}\Pr[\operatorname{per}(A_n)=x]=\frac1q. \] In this paper, we prove this conjecture. More precisely, we prove that there is an absolute constant $C>0$ such that \[\frac12\sum_{x\in\mathbb F_q}\left|\Pr[\operatorname{per}(A_n)=x]-\frac1q\right|\le C\frac{\log n}{n}\] for every odd prime power $q$ and every $n\ge 7$. The estimate is uniform in $q$, so the conclusion remains valid for every sequence $q=q(n)$ of odd prime powers.
We consider the probability that a discrete random matrix $M_n(\xi)$ is \emph{strongly non-singular}, meaning all its leading principal submatrices are non-singular. This property is equivalent to the existence of an LU factorization. We show that for any discrete random variable $\xi$ with finite support and $|\xi|_\infty<1$, there is a constant probability that $M_n(\xi)$ is strongly non-singular with a growth factor bounded by $n^{5/2+\delta}$. Furthermore, we provide a tight asymptotic lower bound for this probability as $|\xi|_\infty \to 0$. Finally, we provide exact counts for strongly non-singular binary matrices up to $n=9$ and use these to derive improved upper bounds for the Bernoulli case.
S. Mateo, John Urschel, Nicholas West· 0 citations
The rows and columns of the character table of the symmetric group $S_n$ are both naturally indexed by partitions of $n$. Let $D(n)$ denote the number of conjugacy classes of $S_n$ whose column contains no zero entry. The identity column is always zero-free, so $D(n)\geq 1$. It is known that $D(n)\ll n^2$. We prove that $D(n)\ll n^{3/4}$. Second, we prove for almost all positive integers $n$ that $D(n)\ll_B n^{1/2}(\log n)^B$ for every $B>5/6$, with a quantitative bound for the exceptional set, using work of Matom\"aki and Radziwill. Finally, we offer a heuristic supporting our conjecture that $D(n)\ll_{\varepsilon} n^{\varepsilon}$. AxiomProver formalized the results in this paper in Lean assuming preexisting literature.
Colin Defant, S. Hariharan, Kenny Lau et al.· 0 citations
Via the method of marked permutation tables presented in this paper, we generalize the formula for the sixth moment of a random determinant to account for entries with arbitrary distribution. That is, let $f_6(n) = \mathbb{E}(\det A)^6$, where $A$ is an $n$ by $n$ random matrix with independent and identically distributed entries. We show that the exponential generating function $F_6(t) = \sum_{n=0}^\infty f_6(n)t^n/(n!)^2$ is D-finite and we present it in a closed form. Our method relies on carefully decomposing marked permutation tables into a shell, a core, and a floating component, each of which has a separate contribution to $F_6(t)$. After this decomposition, it is sufficient to enumerate over a finite number of possible shells, which we did using a highly intricate computer program. We verified our result up to $n = 7$ in the general case and up to $n = 9$ for random matrices whose entries only take two values by using a different method for computing $f_6(n)$ for these cases.