A Berry-Esseen type theorem for finite free convolution

Octavio Arizmendi Centro de Investigación en Matemáticas, A.C., Jalisco S/N, Col. Valenciana CP: 36023 Guanajuato, Gto, México and Daniel Perales

Abstract.

We prove that the rate of convergence for the central limit theorem in finite free convolution is of order $n^{-1/2}$ .

^†^†

This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922.

1. Introduction

In recent years, the convolution of polynomials, first studied by Walsh [10], was revisited by Marcus, Spielman and Srivastava [8], in order to exhibit bounds for the eigenvalues of expected characteristic polynomials of certain $d$ -regular graphs, in their aim to construct bipartite Ramanujan graphs of all sizes [9]. The authors refer to this convolution as finite free additive convolution because of its relation to free convolution, see [1, 7, 9].

In [7], Marcus showed that the Central Limit Theorem for this convolution is given by the polynomial $D_{1/\sqrt{d}}(H_{d}),$ where $H_{d}$ is an Hermite polynomial and may be written as

H_{d}(x)=d!\sum_{i=0}^{\lfloor{\tfrac{d}{2}}\rfloor}{\frac{(-1)^{i}}{i!(d-2i)!}}{\frac{x^{d-2i}}{2^{i}}},

and in general for any $\lambda>0$ and polynomial $p$ of degree $d$ , $D_{\lambda}p(x):=\lambda^{d}p(x/\lambda)$ is the dilation by $\lambda$ of the polynomial $p$ .

In this note we are interested in the rate of convergence in the Central Limit Theorem for finite free convolution. Recall that for the central limit theorem in probability, the Berry-Esseen Theorem [2, 4] states that if $\mu$ is a probability measure with $m_{1}(\mu)=0$ , $m_{2}(\mu)=1$ , and $\int_{\mathbb{R}}|x|^{3}d\mu<\infty$ , then the distance to the standard Gaussian distribution $\mathcal{N}$ is bounded as follows

d_{kol}(D_{\frac{1}{\sqrt{n}}}\mu^{\ast n},\mathcal{N})\leq C\frac{\int_{\mathbb{R}}|x|^{3}d\mu}{\sqrt{n}},

where $d_{kol}$ denotes the Kolmogorov distance between measures, $D_{b}\mu$ denotes the dilation of a measure $\mu$ by a factor $b>0$ , $\ast$ denotes the classical convolution, and $C$ is an absolute constant. Our main reasult shows that as for the classical and free case [3, 5], in finite free probability we also achieve a rate of order $n^{-1/2}$ . However, we use the Lévy distance (see Section 2.3 for more details) instead of Kolmogorov distance, the reason being that we are dealing with measures supported in $d$ atoms with size $1/d$ and thus we cannot expect better.

Thus, for two polynomials of degree $d$ , $p$ and $q$ , let us define the distance between them to be $L(p,q):=d_{L}(\mu_{p},\mu_{q}),$ where $d_{L}$ is the Lévy distance and the measures $\mu_{p}$ and $\mu_{q}$ are the distributions of $p$ and $q$ , respectively.

In this language we can state our contribution as follows.

Theorem 1.1.

Let $d\in\mathbb{N}$ and let $p$ be a real polynomial of degree $d$ such that the first two moments of $\mu_{p}$ are $m_{1}=0$ and $m_{2}=1$ . Then, there exists an absolute constant $C_{d}$ , only depending on $d$ , such that for all $n>0$ ,

L\left(D_{1/\sqrt{n}}(p^{\boxplus_{d}n}),D_{1/\sqrt{d}}(H_{d})\right)<\frac{C_{d}}{\sqrt{n}},

The main tool to prove the above rate of convergence are the cumulants for finite free convolution, as we defined in [1]. These cumulants give a combinatorial approach to investigate this convolution and its relation to free probability. In particular we showed that finite free cumulants approach free cumulants, providing a combinatorial perspective to the fact that finite free convolution approaches free convolution in the limit. Using these cumulants we were able to show that some properties of free convolution are valid already in the finite free case. The above theorem is another instance of the fact that many properties in free probability already appear in the finite level.

Apart from this introduction this note consists of two sections. Section 2 gives the preliminaries for the theory of finite free probability and in Section 3 we give the proof of the main theorem, Theorem 1.1.

2. Preliminaries

We give very basic preliminaries on finite free convolution we refer to [1, 7] for details.

2.1. Finite Free Convolution

For two polynomials, $p(x)=\sum_{i=0}^{d}x^{d-i}(-1)^{i}a^{p}_{i}$ and $q(x)=\sum_{i=0}^{d}x^{d-i}(-1)^{i}a^{q}_{i}$ , the finite free additive convolution of $p$ and $q$ is given by

p(x)\boxplus_{d}q(x)=\sum_{k=0}^{d}x^{d-r}(-1)^{r}\sum_{i+j=r}\frac{(d-i)!(d-j)!}{d!(d-i-j)!}a^{p}_{i}a^{q}_{j}.

The finite $R$ -transform of a polynomial is defined by

(2.1)

\mathcal{R}^{d}_{p}(s)\equiv-\frac{1}{d}\frac{\partial}{\partial s}\ln\left(\sum_{i=0}^{d}\frac{(-d)^{i}a^{p}_{i}}{(d)_{i}}s^{i}\right)\qquad\text{mod }[s^{d}],

when $p$ is the monic polynomial $p(x)=\sum_{i=0}^{d}x^{d-i}(-1)^{i}a^{p}_{i}$ .

We consider the truncated $R$ -transform given by the sum of the first $d$ terms in the series expansion of $\mathcal{R}^{d}_{p}$ , which will have the cumulants as coefficients.

Definition 2.1 ([1]).

Let $p$ be a monic polynomial of degree $d$ , and suppose the $\mathcal{R}^{d}_{p}(s)$ satisfies

\mathcal{R}^{d}_{p}(s)\equiv\sum_{j=0}^{d-1}\kappa_{j+1}(p)s^{j}\quad\text{ mod }[s^{d}].

(1)

We call the sum of the first $d$ terms in the series expansion of $\mathcal{R}^{d}$ the truncated $R$ -transform and denote by $\mathcal{\tilde{R}}^{d}_{p}(s)$ , i.e.

$\mathcal{\tilde{R}}^{d}_{p}(s):=\sum_{j=0}^{d-1}\kappa_{j+1}(p)s^{j}.$
(2)

The numbers $\kappa_{1}(p),\kappa_{2}(p),\dots,\kappa_{d}(p)$ will be called the finite free cumulants. To simplify notation we will omit the dependence on $p$ when we deal with only one polynomial.

We want to use the combinatorial framework in terms of moments for these cumulants. Hence, for a polynomial $p$ with roots $\lambda_{1},....,\lambda_{n}$ we define the moments of $p$ , by the formula $m_{n}(p)=\frac{1}{d}\sum^{d}_{i=1}\lambda_{i}^{n}$ .

These finite free cumulants satisfy the following properties which are the analog of the properties in the axiomatization of cumulants by Lehner [6], in non-commutative probability.

(1)

Polynomial in the first $n$ moments: $k_{n}(p)$ is a polynomial in the first $n$ moments of $p$ with leading term

$\frac{d^{n}}{(d)_{n}}m_{n}(p).$
(2)

Homogeneity: for all monic polynomials $p$ and $\lambda\neq 0$ we have

$\kappa_{n}(D_{\lambda}(p))=\lambda^{n}\kappa_{n}(p).$
(3)

Additivity: for all monic polynomials $p$ and $q$ , we have

$\kappa_{n}(p\boxplus_{d}q)=\kappa_{n}(p)+\kappa_{n}(q).$

2.2. Moment-cumulant formula

Moment-cumulant formulas involve summing over partitions on the set $[n].$ Let us introduce this definition and some notation.

Definition 2.2.

We call $\pi=\{V_{1},...,V_{r}\}$ a partition of the set $[n]:=\{1,2,\dots,n\}$ if $V_{i}$ $(1\leq i\leq r)$ are pairwise disjoint, non-void subsets of $[n]$ , such that $V_{1}\cup V_{2}...\cup V_{r}=\{1,2,\dots,n\}$ . We call $V_{1},V_{2},\dots,V_{r}$ the blocks of $\pi$ . The number of blocks of $\pi$ is denoted by $\left|\pi\right|$ . We will denote the set of partitions of $[n]$ by $\mathcal{P}(n)$ .

The set $\mathcal{P}(n)$ can be equipped with the partial order $\leq$ of reverse refinement ( $\pi\leq\sigma$ if and only if every block of $\pi$ is completely contained in a block of $\sigma$ ). With this order the minimum is given by the partition with $n$ blocks, $0_{n}=\{\{1\},\{2\},\cdots,\{n\}\}$ , and the maximum is given by the partition with $1$ block, $1_{n}=\{\{1,2,\cdots,n\}\}$ .

Thus one can consider the incidence algebra of $\mathcal{P}(n)$ . For two partitions $\sigma,\rho$ in the set of partitions $\mathcal{P}(n)$ the Möbius function is given by

\mu(\sigma,\rho)=(-1)^{{|\sigma|-|\rho|}}(2!)^{{r_{3}}}(3!)^{{r_{4}}}\cdots((n-1)!)^{{r_{n}}},

where $r_{i}$ is the number of blocks of $\rho$ that contain exactly $i$ blocks of $\sigma$ . In particular, for $\sigma=0_{n}$ we have

\mu(0_{n},\rho)=(-1)^{n-{|\rho|}}(2!)^{{t_{3}}}(3!)^{{t_{4}}}\cdots((n-1)!)^{{t_{n}}},

where $t_{i}$ is the number of blocks of $\rho$ of size $i$ .

Given a sequence of complex numbers $f=\{f_{n}\}_{n\in\mathbb{N}}$ we may extend $f$ to partitions in a multiplicative way by the formula

f_{\pi}=f_{|V_{1}|}f_{|V_{2}|}\cdots f_{|V_{n}|},

where $V_{1},\dots,V_{n}$ are the blocks of $\pi.$ In this note we will frequently use the multiplicative extensions of the Pochhammer sequence $(d)_{n}=(d)(d-1)\cdots(d-n+1)$ and the factorial sequence $n!$ , whose extensions will be denoted by $(d)_{\pi}$ and $N!_{\pi}$ , respectively.

In [1], we gave formulas that relate the moments and coefficients of a polynomial with its finite free cumulants. First, we have a formula that writes coefficients in terms of cumulants.

Proposition 2.3 (Coefficient-cumulant formula).

Let $p(x)=\sum_{i=0}^{d}x^{d-i}(-1)^{i}a_{i}$ be a polynomial of degree $d$ and let $(\kappa_{n})^{d}_{n=1}$ be its finite free cumulants. The following formulas hold.

(2.2)

a_{n}=\frac{(d)_{n}}{d^{n}n!}\sum_{\pi\in\mathcal{P}(n)}d^{|\pi|}\mu(0_{n},\pi)\kappa_{\pi},\qquad n\in\mathbb{N}.

We also have a moment-cumulant formula for finite free cumulants:

Proposition 2.4.

Let $p$ be a monic polynomial of degree $d$ and let $(m_{n})^{\infty}_{n=1}$ and $(\kappa_{n})^{d}_{n=1}$ , be the moments and cumulants of $p$ , respectively. Then

\displaystyle\kappa_{n}

\displaystyle=\frac{(-d)^{n-1}}{(n-1)!}\sum_{\sigma\in\mathcal{P}(n)}d^{|\sigma|}\mu(0,\sigma)m_{\sigma}\sum_{\pi\geq\sigma}\frac{\mu(\pi,1_{n})}{(d)_{\pi}},

for $n=1,\ldots,d$ and

\displaystyle m_{n}

\displaystyle=\frac{(-1)^{n}}{d^{n+1}(n-1)!}\sum_{\sigma\in\mathcal{P}(n)}d^{|\sigma|}\mu(0,\sigma)\kappa_{\sigma}\sum_{\pi\geq\sigma}-\mu(\pi,1_{n})(d)_{\pi},

for $n\in\mathbb{N}$ .

Remark 2.5.

The explicit moment-cumulant formulas of the first three finite cumulants are

	$\displaystyle\kappa_{1}$	$\displaystyle=$	$\displaystyle m_{1},\qquad\kappa_{2}=\frac{d}{d-1}(m_{2}-m_{1}^{2}),$
	$\displaystyle\kappa_{3}$	$\displaystyle=$	$\displaystyle\frac{d^{2}}{(d-1)(d-2)}(2m_{1}^{3}-3m_{1}m_{2}+m_{3}),$

and the explicit moment-cumulant formulas of the first three finite moments are

	$\displaystyle m_{1}$	$\displaystyle=$	$\displaystyle\kappa_{1},\qquad m_{2}=\frac{d-1}{d}\kappa_{2}+\kappa_{1}^{2},$
	$\displaystyle m_{3}$	$\displaystyle=$	$\displaystyle\frac{(d-1)(d-2)}{d^{2}}\kappa_{3}+\frac{3(d-1)}{d}\kappa_{2}\kappa_{1}+\kappa_{1}^{3}.$

2.3. Convergence of polynomials and Lévy distance

In this setting of [1, 7] convergence of polynomials is pointwise convergence of the coefficients. We prefer to consider the weak convergence of the induced measures since it is common with the free probability setting. Thus, for a polynomial $p$ , with roots $\lambda_{1},\lambda_{2},\dots,\lambda_{n}$ , we define its distribution $\mu_{p}$ as the uniform measure on the roots of $p$ , $\mu_{p}=\tfrac{1}{d}\sum_{i}\delta_{\lambda_{i}}$ .

To quantify this convergence we use the Lévy distance

d_{L}(\mu,\nu):=\inf\{\epsilon>0\>|\>F(x-\epsilon)-\epsilon\leq G(x)\leq F(x+\epsilon)+\epsilon\>\>\>\text{for all }x\in\mathbb{R}\},

where $F$ and $G$ are the cumulative distribution functions of $\mu$ and $\nu$ respectively.

3. Proof of Theorem 1.1

Before going in to the proof of the main theorem we prove a couple of lemmas about the support and cumulants of polynomials with mean $0$ and variance $1$ .

Lemma 3.1.

Let $p$ be a real polynomial of degree $d$ with $\kappa_{1}=0$ and $\kappa_{2}=1$ . Then the support of $p$ is contained in $(-\sqrt{d-1},\sqrt{d-1})$ .

Proof.

If $\kappa_{1}=0$ and $\kappa_{2}=1$ then

1=\kappa_{2}=\frac{d}{d-1}m_{2}=\frac{1}{d-1}\sum_{i=1}^{d}\lambda_{i}^{2}.

This means that $\lambda_{i}^{2}<d-1$ (strict because there is at least another non-zero $\lambda$ ) and thus $|\lambda_{i}|<\sqrt{d-1}$ for all $i=1,\dots,d$ . ∎

Lemma 3.2.

Let $p$ be a real polynomial of degree $d$ with $\kappa_{1}=0$ and $\kappa_{2}=1$ . Then there exists a constant $c_{d}$ , depending only on $d$ , such that $\max_{2\leq s\leq d}|\kappa_{s}(p)|<c_{d}.$

Proof.

By the previous lemma $m_{n}\leq(d-1)^{n}$ and then $\max_{2\leq s\leq d}|m_{s}(p)|<(d-1)^{d}$ , so we can bound uniformly $\kappa_{n}$ by the moment-cumulant formulas. ∎

Now we are able to prove the main theorem which we state again for convenience of the reader.

Proposition 3.3.

Let $p$ be a real polynomial with $\kappa_{1}=0$ and $\kappa_{2}=1$ . Then, there exists $C_{d}$ such that for all $n>0$

L\left(D_{1/\sqrt{n}}(p^{\boxplus_{d}n}),D_{1/\sqrt{d}}(H_{d})\right)<\frac{C_{d}}{\sqrt{n}}.

Proof.

Let us denote $h=D_{1/\sqrt{d}}(H_{d})$ , $p_{n}=p^{\boxplus_{d}n}$ and $q_{n}=D_{1/\sqrt{n}}(p_{n})$ . By the coefficient-cumulant formula, we know that

	$\displaystyle a_{j}^{q_{n}}$	$\displaystyle=$	$\displaystyle\frac{(d)_{j}}{d^{j}j!}\sum_{\pi\in\mathcal{P}(j)}d^{\|\pi\|}\mu(0_{j},\pi)\kappa_{\pi}(q_{n})$
		$\displaystyle=$	$\displaystyle a_{j}^{h}+\frac{(d)_{j}}{d^{j}j!}\sum_{\pi\in\mathcal{P}(j)\backslash\mathcal{P}_{12}(j)}d^{\|\pi\|}\mu(0_{j},\pi)\kappa_{\pi}(q_{n}),$

where $\mathcal{P}_{12}(j)$ is the set of partitions $\pi=(V_{1},\ldots,V_{r})\in\mathcal{P}(j)$ such that $|V_{i}|\leq 2$ for all $i\in\{1,\ldots,r\}$ (i.e., $\pi=(V_{1},\ldots,V_{r})\in\mathcal{P}(j)\backslash\mathcal{P}_{12}(j)$ , if $|V_{i}|>2$ for some $i\in\{1,\ldots,r\}$ ).

Recall that

|\kappa_{s}(q_{n})|=|\kappa_{s}(D_{1/\sqrt{n}}(p_{n}))|=\frac{n}{n^{s/2}}|\kappa_{s}(p)|\leq n^{1-s/2}c,

for $s=3,\ldots,d$ , where $c:=c_{d}$ from Lemma 3.2. Thus, for any $3\leq j\leq d$ and $\pi=(V_{1},\ldots,V_{r})\in\mathcal{P}(j)\backslash\mathcal{P}_{12}(j)$ we get

(3.1)

|\kappa_{\pi}(q_{n})|\leq c^{r}\cdot n^{r}\cdot n^{-\frac{|V_{1}|+\cdots+|V_{r}|}{2}}=c^{r}n^{r-\frac{j}{2}}\leq c^{r}n^{\frac{j}{3}-\frac{j}{2}}=c^{r}n^{-\frac{j}{6}}\leq c^{d}n^{-\frac{1}{2}}.

Then,

|a_{j}^{q_{n}}-a_{j}^{h}|\leq\frac{c^{d}K_{1}(d)}{\sqrt{n}},\qquad\forall j\in\{1,\ldots,d\}

where

K_{1}(d)=\max_{1\leq j\leq d}\frac{(d)_{j}}{d^{j}j!}\sum_{\pi\in\mathcal{P}(j)\backslash\mathcal{P}_{12}(j)}d^{|\pi|}|\mu(0_{j},\pi)|.

Let’s denote $z_{1},z_{2},\cdots,z_{d}$ the $d$ distinct roots of $h$ and $\delta=\frac{1}{2}\min_{1\leq i<j\leq d}|z_{i}-z_{j}|$ . For $0<\varepsilon<\delta$ we define $B_{i}=\{z\in\mathbb{C}:|z-z_{i}|\leq\varepsilon\}$ and $\partial B_{i}=\{z\in\mathbb{C}:|z-z_{i}|=\varepsilon\}$ . For a fixed root $i$ , using the previous bound we can see that for any $z\in\partial B_{i}$ we have that

|q_{n}(z)-h(z)|\leq\left|\sum_{j=0}^{d}z^{d-j}(-1)^{j}(a^{q_{n}}_{j}-a_{j}^{h})\right|\leq\sum_{j=1}^{d}|z|^{d-m}|a^{q_{n}}_{j}-a_{j}^{h}|

\leq\frac{c^{d}K_{1}(d)}{\sqrt{n}}\sum_{j=1}^{d}(|z_{i}|+|\varepsilon|)^{d-j}\leq\frac{c^{d}K_{1}(d)K_{2}(d)}{\sqrt{n}}

where

K_{2}(d)=\max_{1\leq i\leq d}\sum_{j=1}^{d}(|z_{i}|+|\varepsilon|)^{d-j}.

On the other hand, if $z\in\partial B_{i}$ , we know that

|h(z)|=|(z-z_{0})\cdots(z-z_{n-1})|=|z-z_{1}|\cdots|z-z_{n}|\geq|z-z_{i}|\delta^{d-1}=\varepsilon\delta^{d-1}.

Finally, if we take

n>\frac{c^{2d}K(d)}{\varepsilon^{2}},

where $K(d)=\frac{K^{2}_{1}(d)K^{2}_{2}(d)}{\delta^{2d-2}}$ . Since $c^{2d}K(d)$ does not depend on $i$ , we get that for any $i=1,\ldots,n$ , if $z\in\partial B_{i}$ , then

|q_{n}(z)-h(z)|\leq\frac{c^{d}K_{1}(d)K_{2}(d)}{\sqrt{n}}<\varepsilon\delta^{d-1}\leq|h(z)|\leq|h(z)|+|q_{n}(z)|.

Thus, Rouché’s theorem implies that $q_{n}$ and $h$ have the same number of roots (counting multiplicity) in $B_{i}$ for $i=1,\ldots,n$ . By the definition of the $B_{i}$ we know that they are pairwise disjoint and each one contains exactly one of the $d$ roots of $h$ . Thus, each $B_{i}$ contains exactly one of the $d$ roots of $q_{n}$ implying that distance between the roots of $q_{n}$ and $h$ , (and therefore the Lévy distance) is less than $\varepsilon$ . ∎

Observe that Theorem 1.1 directly gives a bound for $T$ in the next proposition.

Proposition 3.4 ([1]).

Let $p\neq x^{d}$ be a real polynomial, then there exists $T>0$ such that for all $t>T$ the polynomial $p^{\boxplus_{d}t}$ has $d$ different real roots.

Finally, we show that one cannot do better than $O(\sqrt{n})$ as long as $m_{3}(p)\neq 0$ .

Proposition 3.5.

Let $p$ be a real polynomial with $\kappa_{1}=0$ and $\kappa_{2}=1$ and $|m_{3}|=\alpha\neq 0$ . Then, for all $n>0$

L\left(D_{1/\sqrt{n}}(p^{\boxplus_{d}n}),D_{1/\sqrt{d}}(H_{d})\right)\geq\frac{\alpha}{3d\sqrt{n}}.

Proof.

We use again the notation $h=D_{1/\sqrt{d}}(H_{d})$ , $p_{n}=p^{\boxplus_{d}n}$ and $q_{n}=D_{1/\sqrt{n}}(p_{n})$ and suppose that $L(q_{n},h)<\frac{\alpha}{3d\sqrt{n}}.$ Since $\kappa_{1}(q_{n})=0$ , from the moment cumulant formulas we have $m_{3}(q_{n})=\frac{(d-1)(d-2)}{d^{2}}\kappa_{3}(q_{n})$ and then

|m_{3}(q_{n})|=\tfrac{(d-1)(d-2)}{d^{2}}|\kappa_{3}(q_{n})|=\tfrac{(d-1)(d-2)}{d^{2}}\frac{n}{n^{3/2}}|\kappa_{3}(p)|=\frac{|m_{3}(p)|}{\sqrt{n}}=\frac{\alpha}{\sqrt{n}}.

Since $m_{3}(h)=0$ , we can compute

m_{3}(q_{n})=\frac{1}{d}\sum_{i=1}^{d}\lambda^{3}_{i}(q_{n})=\frac{1}{d}\sum_{i=1}^{d}\lambda^{3}_{i}(q_{n})-\frac{1}{d}\sum_{i=1}^{d}\lambda^{3}_{i}(h),

and thus

$\displaystyle\|m_{3}(q_{n})\|$	$\displaystyle\leq$	$\displaystyle\frac{1}{d}\sum_{i}\|\lambda^{3}_{i}(q_{n})-\lambda^{3}_{i}(h)\|$
	$\displaystyle=$	$\displaystyle\frac{1}{d}\sum_{i=1}^{d}\|\lambda_{i}(q_{n})-\lambda_{i}(h)\|\|\lambda_{i}^{2}(q_{n})+\lambda_{i}(q_{n})\lambda_{i}(h)+\lambda_{i}^{2}(h)\|$
	$\displaystyle<$	$\displaystyle\frac{1}{d}\sum_{i=1}^{d}\left(\frac{\alpha}{3d\sqrt{n}}\right)(d+d+d)=\frac{\alpha}{\sqrt{n}.}$

Where we used in the last inequality the assumption that $L(q_{n},h)<\frac{\alpha}{3d\sqrt{n}}.$ This is a contradiction since the inequality is strict. ∎

Remark 3.6.

A specific example with $\kappa_{3}\neq 0$ is the finite free Poisson distribution which has cumulants $\kappa_{n}=\alpha$ for all $n$ . If $\alpha d$ is a positive integer we obtain a valid polynomial. This is a modification of a Laguerre polynomial, thus we obtain a precise estimate for the distance between the roots of certain Laguerre polynomials and the Hermite polynomials.

Remark 3.7.

A closer look at (3.1) shows that if $m_{3}(p)=0$ then the convergence rate is of order $1/n.$ Indeed, $m_{3}(p)=0$ implies $\kappa_{3}(q_{n})=\kappa_{3}(p)=0$ . So in (3.1) we only need to consider partitions with $|V_{i}|\geq 4$ . In this case, for any $4\leq j\leq d$ we have

|\kappa_{\pi}(p)|\leq c^{r}n^{r-\frac{j}{2}}\leq c^{r}n^{\frac{j}{4}-\frac{j}{2}}=c^{r}n^{-\frac{j}{4}}\leq c^{d}n^{-1}.

Finally, let us mention that while it is very tempting to let $d$ go to infinity, possibly together with $n$ , to obtain a Berry-Esseen bound in free probability, there are two problems. First, the quantity $C_{d}$ , as we obtained it, increases broadly as $d\to\infty$ , and second, there is, for the moment not a good bound between finite free and free convolutions.

References

[1] O. Arizmendi and D. Perales. Cumulants for finite free convolution. Journal of Combinatorial Theory, Series A, 155:244–266, 2018.
[2] A. C. Berry. The accuracy of the gaussian approximation to the sum of independent variates. Transactions of the American Mathematical Society, 49(1):122–136, 1941.
[3] G. P. Chistyakov and F. Götze. Limit theorems in free probability theory. i. The Annals of Probability, pages 54–90, 2008.
[4] C.-G. Esseen. On the Liapounoff limit of error in the theory of probability. Almqvist & Wiksell, 1942.
[5] V. Kargin. Berry–esseen for free random variables. Journal of Theoretical Probability, 20(2):381–395, 2007.
[6] F. Lehner. Free cumulants and enumeration of connected partitions. European Journal of Combinatorics, 23(8):1025–1031, 2002.
[7] A. Marcus. Polynomial convolutions and (finite) free probability. Preprint, 2015.
[8] A. Marcus, D. A. Spielman, and N. Srivastava. Finite free convolutions of polynomials. arXiv preprint arXiv:1504.00350, 2015.
[9] A. Marcus, D. A. Spielman, and N. Srivastava. Interlacing families IV: Bipartite ramanujan graphs of all sizes. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pages 1358–1377. IEEE, 2015.
[10] J. L. Walsh. On the location of the roots of certain types of polynomials. Transactions of the American Mathematical Society, 24(3):163–180, 1922.