skip to main content


Title: Finite free convolutions of polynomials
Abstract

We study three convolutions of polynomials in the context of free probability theory. We prove that these convolutions can be written as the expected characteristic polynomials of sums and products of unitarily invariant random matrices. The symmetric additive and multiplicative convolutions were introduced by Walsh and Szegö in different contexts, and have been studied for a century. The asymmetric additive convolution, and the connection of all of them with random matrices, is new. By developing the analogy with free probability, we prove that these convolutions produce real rooted polynomials and provide strong bounds on the locations of the roots of these polynomials.

 
more » « less
NSF-PAR ID:
10366318
Author(s) / Creator(s):
; ;
Publisher / Repository:
Springer Science + Business Media
Date Published:
Journal Name:
Probability Theory and Related Fields
Volume:
182
Issue:
3-4
ISSN:
0178-8051
Format(s):
Medium: X Size: p. 807-848
Size(s):
["p. 807-848"]
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    Let $k \leq n$ be positive integers, and let $X_n = (x_1, \dots , x_n)$ be a list of $n$ variables. The Boolean product polynomial$B_{n,k}(X_n)$ is the product of the linear forms $\sum _{i \in S} x_i$, where $S$ ranges over all $k$-element subsets of $\{1, 2, \dots , n\}$. We prove that Boolean product polynomials are Schur positive. We do this via a new method of proving Schur positivity using vector bundles and a symmetric function operation we call Chern plethysm. This gives a geometric method for producing a vast array of Schur positive polynomials whose Schur positivity lacks (at present) a combinatorial or representation theoretic proof. We relate the polynomials $B_{n,k}(X_n)$ for certain $k$ to other combinatorial objects including derangements, positroids, alternating sign matrices, and reverse flagged fillings of a partition shape. We also relate $B_{n,n-1}(X_n)$ to a bigraded action of the symmetric group ${\mathfrak{S}}_n$ on a divergence free quotient of superspace.

     
    more » « less
  2. We investigate the phase diagram of the complex cubic unitary ensemble of random matrices with the potential [Formula: see text], where t is a complex parameter. As proven in our previous paper [Bleher et al., J. Stat. Phys. 166, 784–827 (2017)], the whole phase space of the model, [Formula: see text], is partitioned into two phase regions, [Formula: see text] and [Formula: see text], such that in [Formula: see text] the equilibrium measure is supported by one Jordan arc (cut) and in [Formula: see text] by two cuts. The regions [Formula: see text] and [Formula: see text] are separated by critical curves, which can be calculated in terms of critical trajectories of an auxiliary quadratic differential. In Bleher et al. [J. Stat. Phys. 166, 784–827 (2017)], the one-cut phase region was investigated in detail. In the present paper, we investigate the two-cut region. We prove that in the two-cut region, the endpoints of the cuts are analytic functions of the real and imaginary parts of the parameter t, but not of the parameter t itself (so that the Cauchy–Riemann equations are violated for the endpoints). We also obtain the semiclassical asymptotics of the orthogonal polynomials associated with the ensemble of random matrices and their recurrence coefficients. The proofs are based on the Riemann–Hilbert approach to semiclassical asymptotics of the orthogonal polynomials and the theory of S-curves and quadratic differentials.

     
    more » « less
  3. Abstract

    An $n \times n$ matrix with $\pm 1$ entries that acts on ${\mathbb {R}}^{n}$ as a scaled isometry is called Hadamard. Such matrices exist in some, but not all dimensions. Combining number-theoretic and probabilistic tools, we construct matrices with $\pm 1$ entries that act as approximate scaled isometries in ${\mathbb {R}}^{n}$ for all $n \in {\mathbb {N}}$. More precisely, the matrices we construct have condition numbers bounded by a constant independent of $n$.

    Using this construction, we establish a phase transition for the probability that a random frame contains a Riesz basis. Namely, we show that a random frame in ${\mathbb {R}}^{n}$ formed by $N$ vectors with independent identically distributed coordinate having a nondegenerate symmetric distribution contains many Riesz bases with high probability provided that $N \ge \exp (Cn)$. On the other hand, we prove that if the entries are sub-Gaussian, then a random frame fails to contain a Riesz basis with probability close to $1$ whenever $N \le \exp (cn)$, where $c<C$ are constants depending on the distribution of the entries.

     
    more » « less
  4. We develop the complex-analytic viewpoint on the tree convolutions studied by the second author and Weihua Liu in Jekel and Liu (2020), which generalize the free, boolean, monotone, and orthogonal convolutions. In particular, for each rooted subtree T of the N-regular tree (with vertices labeled by alternating strings), we define the convolution \boxplus_T (µ1, . . . , µN) for arbitrary probability measures µ1, . . . , µN on R using a certain fixed-point equation for the Cauchy transforms. The convolution operations respect the operad structure of the tree operad from Jekel and Liu (2020). We prove a general limit theorem for iterated T -free convolution similar to Bercovici and Pata’s results in the free case (Bercovici and Pata 1999), and we deduce limit theorems for measures in the domain of attraction of each of the classical stable laws. 
    more » « less
  5. Byrka, Jaroslaw ; Meka, Raghu (Ed.)
    In this work, we prove new relations between the bias of multilinear forms, the correlation between multilinear forms and lower degree polynomials, and the rank of tensors over F₂. We show the following results for multilinear forms and tensors. Correlation bounds. We show that a random d-linear form has exponentially low correlation with low-degree polynomials. More precisely, for d = 2^{o(k)}, we show that a random d-linear form f(X₁,X₂, … , X_d) : (F₂^{k}) ^d → F₂ has correlation 2^{-k(1-o(1))} with any polynomial of degree at most d/2 with high probability. This result is proved by giving near-optimal bounds on the bias of a random d-linear form, which is in turn proved by giving near-optimal bounds on the probability that a sum of t random d-dimensional rank-1 tensors is identically zero. Tensor rank vs Bias. We show that if a 3-dimensional tensor has small rank then its bias, when viewed as a 3-linear form, is large. More precisely, given any 3-dimensional tensor T: [k]³ → F₂ of rank at most t, the bias of the 3-linear form f_T(X₁, X₂, X₃) : = ∑_{(i₁, i₂, i₃) ∈ [k]³} T(i₁, i₂, i₃)⋅ X_{1,i₁}⋅ X_{2,i₂}⋅ X_{3,i₃} is at least (3/4)^t. This bias vs tensor-rank connection suggests a natural approach to proving nontrivial tensor-rank lower bounds. In particular, we use this approach to give a new proof that the finite field multiplication tensor has tensor rank at least 3.52 k, which is the best known rank lower bound for any explicit tensor in three dimensions over F₂. Moreover, this relation between bias and tensor rank holds for d-dimensional tensors for any fixed d. 
    more » « less