Polynomials on the Unit Circle - MathOverflow

Polynomials on the Unit Circle

2011-04-30T13:57:41Z

I asked this question in math.stackexchange but I didn't have much luck. It might be more appropiate for this forum. Let $z_1,z_2,…,z_n$ be i.i.d random points on the unit circle ($|z_i|=1$) with uniform distribution on the unit circle. Consider the random polynomial $P(z)$ given by $$ P(z)=\prod_{i=1}^{n}(z−z_i). $$ Let $m$ be the maximum absolute value of $P(z)$ on the unit circle $m=\max\{|P(z)|:|z|=1\}$.

How can I estimate $m$? More specifically, I would like to prove that there exist $\alpha>0$ such that the following holds almost surely as $n\to\infty$ $$ m\geq \exp(\alpha\sqrt{n}). $$ Or at least that for every $\epsilon>0$ there exists $n$ sufficiently large such that $$ \mathbb{P}(m\geq\exp(\alpha\sqrt{n}))>1-\epsilon $$ for some $\alpha$ independent on $n$.

Any idea of what can be useful here?

Answer by Seva for Polynomials on the Unit Circle

2011-05-02T10:26:38Z

I believe you can obtain very reasonable bounds for your problem using the following approach. (I myself was too lazy to carry out the computations.) Split the unit circle into the union of an interval $I$ of length $4\pi/(n\log n)$ and $N\sim \pi n/\log n$ intervals $J_k$ of length about $2\log n/n$ each. (You may need to adjust the logarithmic factors at the optimization stage.) Almost surely, the interval $I$ will not contain any point $z_i$, whereas each of the intervals $J_k$ will contain at most $3\log n$ points. Now choose your point $z$ to be in the middle of the interval $I$ and compute $|P(z)|$ for the worst-case scenario, where each of the two intervals $J_k$ abating to $I$ contains $3\log n$ points $z_i$, all of these points at the distance $2\pi/(n\log n)$ from $z$, the two "next" intervals $J_k$ also contain $3\log n$ points each at the minimum possible distance from $z$ and so on.

Answer by Johan Wästlund for Polynomials on the Unit Circle

2011-05-02T12:19:17Z

I think $z$ should be chosen so that the deviations tend to go in the positive direction on all scales. The following approach seems to work: Suppose $n$ is a power of 2 (some fix is needed if it isn't). Suppose the points $z_i$ are sorted, say in counter-clockwise direction, and assume without loss of generality that we have $z_0 = z_n = 1$ (indexing modulo $n$). The points $z_0$ and $z_{n/2}$ split the unit circle in two sectors. We pick the larger of those two, and look at the point whose index is the mean of the indices at the endpoints (either $z_{n/4}$ or $z_{3n/4}$, the point that we expect to be near the midpoint of that larger sector). That point splits the sector in two, and we pick the larger of those two and continue. In the end we arrive at two consecutive points $z_i$, and we let $z$ be the midpoint of the sector between them.

It should now be possible to get a high-probability lower bound on $\log(P(z))$. I haven't done this in detail, but a simulation for $n=64,128,\dots,4096$ indicates that $\log(P(z))$ is rarely much smaller than $\sqrt{n}$. Since you ask for an idea that might be useful, I dare post this as an answer.

UPDATE: Here's a simple argument that should almost, but not quite, give the desired bound. What it ought to show, although some precision in the analysis is still missing, is that for every $\epsilon>0$ there is an $\alpha>0$ such that $m\geq \exp(\alpha\sqrt{n})$ with probability at least $1-\epsilon$.

Here's how it works: Since the mean value of $\log\left|P(z)\right|$ is 0, we can always find a $z$ such that $\left|P(z)P(-z)\right| = 1$. Notice that $P(z)P(-z)$ is unchanged if we replace $z_i$ by $-z_i$. Therefore we can start by randomly generating $n$ pairs of diametrically opposite points ${z_i, -z_i}$, then find $z$ with $\left|P(z)P(-z)\right|=1$ given only this information, and finally fix the $z_i$'s by $n$ independent coin flips.

Now condition on the outcome of the first stage of the process, so that the $n$ pairs ${z_i, -z_i}$ are fixed. With high probability there is a bunch of say $n/2$ such pairs for which the quantity $\log\left|P(z)\right| - \log\left|P(-z)\right|$ is affected by at least some constant depending on a coin flip (this just requires $z_i$ to be substantially closer to one of $z$ and $-z$ than to the other). Therefore the standard deviation of $\log\left|P(z)\right| - \log\left|P(-z)\right|$ is at least some constant times $\sqrt{n}$, which means that $\max\left(\log\left|P(z)\right|, \log\left|P(-z)\right|\right)$ should be of order $\sqrt{n}$ most of the time.

I guess the argument can be made precise, but this choice of $z$ doesn't let us fix $\alpha>0$ and get a.a.s. the bound asked for.

Perhaps this helps to at least clarify the question. What the OP asks for is just beyond what we get with this argument.

EDIT: The more I think about it, the more I suspect that the first statement asked for in the OP is not true. Of course $\log\left|P(z)\right|$ will take large negative values when $z$ is extremely close to a $z_i$, but when it isn't, it seems that the irregularities in distribution of the $z_i$ on a smaller scale will be less significant than the large scale distribution. Roughly speaking this is because by the nature of the logarithm, the points $z_i$ close to $z$ will have only a mildly stronger influence on $\log\left|P(z)\right|$ than the points farther away. If the points $z_i$ happen to be unusually but not extremely uniformly distributed on the large scale, it seems that $\max\left(\log\left|P(z)\right|\right)$ need not be larger than any particular constant times $\sqrt{n}$.

If this is correct, it means that the values of $\log\left|P(z)\right|$ for different $z$ are significantly correlated even on a larger scale. Needless to say, these speculations are still nothing close to a proof.

The second, weaker version, seems to be equivalent to what is claimed in the update above, and it should not be too hard to fill in the missing details.

Answer by Johan Wästlund for Polynomials on the Unit Circle

2011-05-05T23:17:22Z

Here is a more careful (EDIT: even more careful!) argument that gives an affirmative answer to the weaker version of the question (as stated in the edit to my previous post, I doubt that the stronger version is true).

The argument uses the following lemma, which ought to be known. If someone has a reference, please leave a comment.

Lemma: Let $a_1,\dots, a_n$ be real numbers with each $a_i\geq 1$, and let $X_1,\dots,X_n$ be independent random variables, each uniform on $\pm 1$. Let $I$ be an interval of length $2r$. Then $$Pr(a_1X_1+\cdots+a_nX_n\in I) \leq \frac{1+r}{\sqrt{\pi n/2}}.$$

Proof: Let $f(X)$ denote $a_1X_1+\cdots+a_nX_n$. In the Boolean lattice of all assignments of $\pm 1$ to the variables $X_1,\dots,X_n$, consider a random walk starting from the point where all $X_i$'s are $-1$, and moving in $n$ steps to the point where they are all $+1$, in each step choosing uniformly and independently of the history a variable which is $-1$ and changing it to $+1$.

What is the expectation of the number $N(I)$ of steps of this walk at which $f(X) \in I$? On one hand, $N(I)\leq 1+r$, since $f(X)$ increases by at least 2 in each step.

On the other hand, the probability that the walk passes through any given point in the Boolean lattice is at least $2^{-n}\sqrt{\pi n/2}$ (this probability is minimized at the middle level(s) of the lattice, and the claim follows by well-known estimates of the central binomial coefficient). Therefore $$EN(I) \geq \frac{\#\{X:f(X)\in I\}}{2^n}\cdot \sqrt{\pi n/2} = Pr(f(X)\in I) \cdot \sqrt{\pi n/2}.$$

It follows that $$Pr(f(X)\in I) \leq \frac{1+r}{\sqrt{\pi n/2}}. \qquad \square$$

As was explained in the earlier post, we can randomly choose $n$ pairs of opposite points ${z_i, -z_i}$, then find $z$ with $\left|P(z)P(-z)\right|=1$ given only this information, and finally fix the $z_i$'s by $n$ independent coin flips.

In order to apply the lemma, we want to have, before the coin flipping, $n/2$ pairs $z_i, -z_i$ making an angle of say at most $60$ degrees with $z, -z$, so that each of the $n/2$ corresponding coin flips determine the sign of a term of at least $\log 3$ in $\log\left|P(z)\right| - \log\left|P(-z)\right|$. Actually, after choosing the $n$ pairs $z_i, -z_i$, this a. a. s. holds for every $z$. The idea is to divide the circle into, say, 100 equally large sectors. With high probability, every pair of opposite sectors will contain at least $n/51$ pairs (as opposed to the expected number, $n/50$).

We now condition on the outcomes of the coin flips for the smaller terms (pairs $z_i, -z_i$ more or less orthogonal to $z$). The lemma above tells us that for any interval $I$ of length $4\alpha\sqrt{n}$, the probability that $\log\left|P(z)\right| - \log\left|P(-z)\right| \in I$ is at most $4\alpha/\sqrt{\pi} + O(1/\sqrt{n})$.

In particular, with probability at least $1-O(\alpha)$, the absolute value of $\log\left|P(z)\right| - \log\left|P(-z)\right|$ is at least $2\alpha\sqrt{n}$, and since $\log\left|P(z)\right|=-\log\left|P(-z)\right|$, $\max\left(\log\left|P(z)\right|, \log\left|P(-z)\right|\right)\geq \alpha\sqrt{n}$ as required.

Answer by Joe Silverman for Polynomials on the Unit Circle

2011-07-16T16:34:41Z

I have a couple of comments regarding Chandru's answer, but they're too long to fit in the comment box, so I'm making this a separate answer. First, the quantity $$ F(P) = \int_0^{2\pi} \log|P(e^{i\phi})| d\phi $$ is not non-negative without some further assumption. The easiest is to assume that the polynomial $P$ is monic. But as a trivial counterexample in general, one can take $P(z)=c$ with $|c|<1$. For Chandru's argument, somewhere one needs to use the assumption that $P(0)=1$ to make the conclusion that $F(P)\ge0$.

Second, the quantity $F(P)$ is essentially the logarithm of the classical Mahler measure, which is defined by $$ \log M(P) = \frac{1}{2\pi} \int_0^{2\pi} \log|P(e^{i\phi})| d\phi. $$ Factoring $P$ as $$ P(z) = c(z-z_1)\cdots(z-z_n), $$ it is an elementary classical computation to show that $$ \log M(P) = \log|c|+\sum_{i=1}^n \log\max(1,|z_i|). $$ In particular, if $|c|=1$, then $\log M(P)\ge0$.