Source-linked AI summary
On the permanent of random Bernoulli matrices
T. Tao, V. Vu
TL;DR
Before this work, it was not known whether the permanent of a random Bernoulli matrix was almost surely nonzero. The paper exposes matrix rows and uses a combinatorial argument to propagate probabilistic lower bounds from small minors to larger ones. Theorem 1.1 is stated as an asymptotically almost-sure result; Theorem 1.2 asserts that a positive constant c exists for every ε > 0 and sufficiently large n depending on ε.
Problem
Before this work, it was not known whether the permanent of a random Bernoulli matrix was almost surely nonzero.
Source: §1 · p. 1Method
The paper exposes matrix rows and uses a combinatorial argument to propagate probabilistic lower bounds from small minors to larger ones.
Source: §1 · p. 2Results
Theorem 1.1 is stated as an asymptotically almost-sure result; Theorem 1.2 asserts that a positive constant c exists for every ε > 0 and sufficiently large n depending on ε.
Source: §1 · p. 2Takeaways & Limitations
The paper addresses the prior uncertainty about whether the permanent of a random Bernoulli matrix is almost surely nonzero.
Source: §1 · pp. 1–2The method does not appear to yield c>1/2, because its final step relies on the Erdős–Littlewood–Offord inequality.
Source: §1 · p. 2
Abstract
from arXiv · showhide
We show that the permanent of an $n \times n$ matrix with iid Bernoulli entries $\pm 1$ is of magnitude $n^{({1/2}+o(1))n}$ with probability $1-o(1)$. In particular, it is almost surely non-zero.
1. Introduction
The asymptotic behavior of random Bernoulli matrix permanents is a central question, but their non-vanishing was previously unknown. This paper pursues a determinant-like magnitude result for the permanent using a combinatorial minor-growth argument.
1. Introduction
- Before this work, it was not known whether the permanent of a random Bernoulli matrix was almost surely nonzero.The asymptotic behavior of both determinant and permanent was a central problem.Source: §1 · p. 1
- The permanent's second moment is easy to compute, but higher moments are difficult to compute and reveal little useful information.The second-moment identity is E|Per(M_n)|² = n!.Source: §1 · pp. 1–2
- The paper's main goal is to establish for the permanent an analogue of the determinant result in (1).Source: §1 · p. 2
- The method does not appear to yield c greater than 1/2 because its final step relies on the Erdős–Littlewood–Offord inequality.The authors note that more advanced Littlewood–Offord inequalities might improve the bound, but they do not know how to restructure the argument to use them.Source: §1 · p. 2
- The Bernoulli distribution is not essential and identical distribution is unnecessary, but independence is critical.The authors say their arguments do not easily yield a non-trivial result for random symmetric Bernoulli matrices.Source: §1 · p. 2
- The proof uses a combinatorial approach that propagates probabilistic lower bounds from small minors to larger ones as matrix rows are exposed.It seeks substantial growth for most steps, then keeps permanents from dropping in the last few steps.Source: §1 · p. 2
2. Probabilistic tools
The section presents probability tools for handling likely events even when correlated, concentration under bounded changes, adapted sequences, and random-sign sums.
First moment
- A sequence of events can be mostly true together even when the events are strongly correlated, provided each is individually likely.The section introduces a first-moment lemma for this purpose.Source: §2 · p. 3
- If each of m events has probability at least 1−δ, at most cm are false with probability at least 1−δ, without requiring independence.This follows from the first-moment argument using indicators and linearity of expectation.Source: §2 · p. 3
Azuma concentration
- A function of independent Bernoulli variables has a concentration result when changing one coordinate changes its value by at most T.The result is presented as a consequence of Azuma’s inequality.Source: §2 · p. 3
Martingale-type concentration
- For an adapted sequence with conditional expectation at most its previous value and increments bounded by 1, the section invokes a one-sided concentration lemma.The sequence is defined relative to nested σ-algebras.Source: §2 · p. 3
Littlewood-Offord-Erdős inequality
- The final probability tool is the classical Littlewood-Offord-Erdős inequality for weighted sums of independent uniform signs.Its stated setup requires at least k coefficients to have absolute value at least λ.Source: §2 · p. 4
3. Preliminary reductions
The section builds lower bounds on permanent minors from small sizes up to the full matrix, aiming to grow the number of large minors or their lower-bound threshold across most sizes. It combines staged propositions with a probabilistic argument, while the endgame leaves the final theorem’s probability bound polynomial.
Overall strategy
- The strategy grows lower bounds on minors from size 1 to n, passing them to many larger minors and improving them by almost n^1/2 for most sizes.The minors use the first k rows and selected k columns.Source: §3 · p. 4
Small-k reduction
- For small k, a crude bound gives exponentially high probability of success without increasing the number of minors or their lower-bound threshold.The intermediate-k range requires more sophisticated estimates.Source: §3 · p. 4
Maintaining large minors
- Proposition 3.1 maintains a single large minor, while Proposition 3.2 extends the maintenance step to many large minors.The latter is introduced because the single-minor result does not grow the number of minors or the threshold.Source: §3 · pp. 4–5
Growing large minors
- Proposition 3.3 introduces a growth step that can increase the number of large minors or their threshold, at a higher failure rate.The section uses this step alongside a lower-failure-rate maintenance proposition.Source: §3 · p. 5
Endgame
- The endgame proposition addresses the last few minor sizes, from (1−ε)n through n.Its stated bound applies when n is sufficiently large depending on ε.Source: §3 · p. 5
Combining the propositions
- The algorithm constructs random variables N_k, λ_k, and W_k for k0 ≤ k ≤ k1, and is successful at terminating time k = k1 when N_k1 ≠ 0 and W_k1 ≤ ε′n/2.Source: §3 · pp. 5–6
- The probability that the tracked minor count reaches zero is exponentially small in ε′n.This bound follows from the initial failure estimate, the maintenance proposition, and a union bound.Source: §3 · p. 6
Probability limitation
- Although the argument for an intermediate bound gives an exponentially small probability bound, the bottom-row endgame yields only a polynomial final bound.The authors attribute this limitation especially to the last step of Proposition 3.4.Source: §3 · p. 7
4. Child and parent minors
The section relates parent and child minors through adding one index, then uses the resulting branching behavior to propagate heavy minors. With high probability, many children of a parent are at least as large in permanent magnitude as the parent.
4. Child and parent minors
- A child minor is formed by adding one index to its parent minor.The permanent relation between these minors is used to prove Propositions 3.1–3.4.Source: §4 · p. 7
- A parent with many independent children amplifies a probability of 1/2 to an exponentially small failure probability.This is the stated mechanism behind the more sophisticated argument for Proposition 3.2.Source: §4 · pp. 7–8
- With probability 1−O(exp(−Ω(|I|))), at least |I|/3 children have permanent magnitude at least that of their parent.The bound applies after fixing the first k rows and exposing row k+1.Source: §4 · pp. 7–8
- If at least half of N parent minors are good, double counting their heavy children yields at least εN/6 elements in the next family.Each good parent has at least εn/3 λ-heavy children, while each child has at most n parents.Source: §4 · p. 8
5. Growing large minors
This section grows a family of heavy minors by counting their shared children and separating children according to how many selected parents they have. The two parent-count regimes yield probabilistic lower bounds on the number and heaviness of the resulting minors.
5. Growing large minors
- Double counting gives lF_l ≤ K(F_1 + … + F_K) + n(F_(K+1) + … + F_n) for children with l selected parents.Each of the N selected parents has at least εn children.Source: §5 · p. 8
- With probability at least 1/3, at least εnN/(8K) of these A′ are λ-heavy; each such A′ has at least one parent in {A1, …, AN} and is λ-heavy with probability at least 1/2.Source: §5 · p. 9
- With probability 1−O(n^(1/2−c)/K^(1/2)), at least εN/4 children are n^(1/2−c)λ-heavy when each has at least K selected parents.The bound follows by applying Lemma 2.4 and Lemma 2.1; K is chosen to establish claim (7).Source: §5 · p. 9
6. The endgame
The endgame constructs many complement-disjoint heavy minors and propagates them toward the full matrix, with a controlled loss in their weight threshold. The argument concludes that the full minor is heavy with probability 1−n^−Ω(1).
6. The endgame
- Starting from a λ-heavy minor, the construction keeps each successive minor λ-heavy with probability at least 1−2^−(n−j), giving this property for all k ≤ j ≤ n−L with probability 1−O(2^−L).The procedure chooses an available heavy child when possible, otherwise adding an arbitrary index.Source: §6 · p. 9
- The final walk drives W_(n−L) to zero with probability 1−exp(−Ω(L)); the resulting minor A_(n−L) is also λ-heavy with that probability.Here W_j counts indices outside B∪A_j; the argument first conditions on W_(n−⌊2.01L⌋)=⌊2.01L⌋−2L.Source: §6 · p. 10
- With probability 1−exp(−Ω(L)) = 1−n^−Ω(1), there are ⌊εn/10L⌋ complement-disjoint λ-heavy minors of order n−L.The argument then propagates these events downward, accepting losses in the weight threshold and population of heavy minors.Source: §6 · p. 10
- With probability 1−n^−Ω(1), the full minor [n] is n^−log n λ-heavy.The proof first obtains at least ⌊n^0.5⌋ such heavy minors and then applies (10) and Lemma 2.4.Source: §6 · p. 11