Estimates for Symmetric Functions - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T21:50:53Z http://mathoverflow.net/feeds/question/60030 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/60030/estimates-for-symmetric-functions Estimates for Symmetric Functions ght 2011-03-30T02:05:29Z 2011-04-01T11:32:51Z <p>Let $z_1,z_2,\ldots,z_n$ be i.i.d. random variables in the unit circle. Consider the polynomial $$p(z)=\prod_{i=1}^{n}{(t-z_i)}=t^n+a_{1}t^{n-1}+\cdots+a_{n-2}t^2+a_{n-1}t+a_n$$ where the $a_i$ are the symmetric functions $$a_{1}=(-1)\sum_{i=1}^{n}{z_{i}}\hspace{0.3cm},\quad a_{2}=(-1)^2\sum_{1\leq i&lt; j\leq n}{z_{i}z_{j}}\hspace{0.3cm} \quad\ldots\quad a_{n}=(-1)^{n}z_{1}z_{2}\ldots z_{n}.$$</p> <p>How can we estimate the random variable $Z$ defined as $$Z=\sum_{j=1}^{n}{|a_{j}|}$$ asymptotically as $n\to\infty$?</p> <p>It is not very difficult to estimate $|\sum_{j=1}^{n}{a_{j}}|$ by estimating $\log p(1)$ via the CLT. However, $Z$ seems to be much more difficult. Any idea of what can work here? </p> <blockquote> <p><strong>Update:</strong> If we look at the term at the central symmetric random variable $a_{\lfloor n/2 \rfloor}$ $$a_{\lfloor n/2 \rfloor}=\text{sum of the products of \lfloor n/2 \rfloor of different z_{i}'s}$$ it is not hard to see that it has uniform distributed phase in $(-\pi,\pi]$. </p> <p>However, its magnitude is blowing up extremely fast!</p> <p>Does anyone knows how to compute the limit distribution of $|a_{\lfloor n/2 \rfloor}|$ under the appropriate normalizations? </p> </blockquote> <p>Thanks!</p> http://mathoverflow.net/questions/60030/estimates-for-symmetric-functions/60279#60279 Answer by fedja for Estimates for Symmetric Functions fedja 2011-04-01T11:32:51Z 2011-04-01T11:32:51Z <p>OK, here is my argument (sorry for the delay).</p> <p>First of all, $Z$ is essentially the maximum of the absolute value of the polynomial $P(z)=\prod_j(1-z_jz)$ on the unit circumference (up to a factor of $n$, but it is not noticeable on the scale we are talking about).</p> <p>Second, the maximum of the absolute value of a (trigonometric) polynomial of degree $K$ can be read from any $AK$ uniformly distributed points on the unit circumference $\mathbb T$ (say, roots of unity of degree $AK$) with relative error of order $A^{-1}$.</p> <p>Now let $\psi(z)=\log(1-z)$. We want to find the asymptotic distribution of the $\max_z n^{-1/2}Re\sum_j \psi(zz_j)$ where $z_j$ are i.i.d. random variables uniformly. Since it is the logarithm of $|P(z)|$, the maximum can be found using $10n$ points. </p> <p>Decompose $\psi(z)$ into its Fourier series $-\sum_{k\ge 1}\frac 1kz^k$. Then, formally, we have $n^{-1/2}\sum_j \psi(zz_j)=-\sum_k\left(n^{-1/2}\sum_j z_j^k\right)\frac{z^k}{k}$. It is tempting to say that the random variables $\xi_n,k=n^{-1/2}\sum_j z_j^k$ converge to the uncorrelated standard complex Gaussians $\xi_k$ by the CLT in distribution and, therefore, the whole sum converges in distribution to the random function $F(z)=\sum_k\xi_k\frac{z^k}k$, so $n^{-1/2}\log Z$ converges to $\max_z\Re F(z)$ (the $-$ sign doesn't matter because the limiting distribution is symmetric). This argument would be valid literally if we had a finite sum in $k$ but, of course, it is patently false for the infinite series (just because if we replace $\max$ by $\min$, we get an obvious nonsense in the end). Still, it can be salvaged if we do it more carefully.</p> <p>Let $K$ run over the powers of $2$. Choose some big $K_0$ and apply the above naiive argument to $\sum_{k=1}^{K_0}$. Then we can safely say that the first $K_0$ terms in the series give us essentially the random function $F_{K_0}(z)$ which is the $K_0$-th partial sum of $F$ when $n$ is large enough. </p> <p>Our main task will be to show that the rest of the series cannot really change the maximum too much. More precisely, it contributes only a small absolute error with high probability. </p> <p>To this end, we need </p> <p>Lemma: Let $f(z)$ be an analytic in the unit disk function with $f(0)=0$, $|\Im f|\le \frac 12$. Then we have $\int_{\mathbb T}e^{\Re f}dm\le \exp\left(2\int_{\mathbb T}|f|^2dm\right)$ where $m$ is the Haar measure on $\mathbb T$.</p> <p>Proof: By Cauchy-Schwartz, $$\left(\int_{\mathbb T}e^{\Re f}dm\right)^2\le \left(\int_{\mathbb T}e^{2\Re f}e^{-2|\Im f|^2}dm\right)\left(\int_{\mathbb T}e^{2|\Im f|^2}dm\right)$$ Note that if$|\Im w|\le 1$, we have $e^{\Re w}e^{-|\Im w|^2}\le \Re e^w$. So the first integral does not exceed $\int_{\mathbb T}\Re e^{2f}dm=\Re e^{2f(0)}=1$. Next, $e^s\le 1+2s$ for $0\le s\le\frac 12$, so $\int_{\mathbb T}e^{2|\Im f|^2}dm\le 1+4\int_{\mathbb T}|\Im f|^2dm\le 1+4\int_{\mathbb T}|f|^2dm$. Taking the square root turns $4$ into $2$ and it remains to use that $1+s\le e^s$ </p> <p>The immediate consequence of Lemma 1 is a Bernstein type estimate for $G_K(z)=\sum_{k\in (K,2K]}\left(n^{-1/2}\sum_j z_j^k\right)\frac{z^k}{k}$ $$P(\max|\Re G_K|\ge 2T)\le 20Ke^{-T^2K/9}$$ if $0\le TK\le \sqrt n$, say.</p> <p>Indeed, just use the Bernstein trick on the independent random shifts of $g_K(z)=\sum_{k\in (K,2K]}\frac{z^k}{k}$: $$E e^{\pm t\Re G_K(z)}\le \left(\int_{\mathbb T}e^{\Re tn^{-1/2}g_K}dm\right)^n\le e^{2t^2/K}$$ for every $t\le \sqrt n/2$ (we used the Lemma to make the last estimate) and put $t=\frac{TK}{3}$. After that read the maximum from $10K$ points with small relative error and do the trivial union bound.</p> <p>Choosing $T=K^{-1/3}$, we see that we can safely ignore the sum from $K=K_0$ to $K=\sqrt n$ if $K_0$ is large enough. Now we are left with $$G_K(z)=\sum_{k\ge \sqrt n}\left(n^{-1/2}\sum_j z_j^k)\right)\frac{z^k}{k}$$ to deal with. Recall that all we want here is to show that it is small at $10n$ uniformly distributed points. Again, if $g(z)=\sum_{k\ge \sqrt n}\frac{z^k}{k}$, we have $|\Im g|\le 10$, say so we can use the same trick and get $$P(\max_{10n\text{ points}}|\Re G|\ge 2T)\le 20n e^{n^{-1/2}t^2-tT}$$ if $0\le t\le \sqrt n/20$, say. Here we do not need to be greedy at all: just take a fixed small $T$ and choose $t=\frac{2\log n}T$.</p> <p>Now, returning to your original determinant problem, we see that the norm of the inverse matrix is essentially $Z/D$ where $D=\min_i\prod_{j:j\ne i}|z_i-z_j|$. We know the distribution of $\log Z$ and we have the trivial Hadamard bound $D\le n$. This already tells you that the typical $\lambda_1$ is at most $e^{-c\sqrt n}$. The next logical step would be to investigate the distribution of $\log D$. </p>