# Average compared with discrete average for some $\lbrace -1,1 \rbrace$ polynomials

Let $k>0$ be a positive integer. Set $n=4k.$ Let $R(t)$ be a polynomial of degree $n-1$ with coefficients in $\lbrace -1,1 \rbrace$.

Consider the discrete average

$$D(n,R) = \frac{\sum_{j=0}^{n-1} \vert R(exp(2\pi i j/n)) \vert}{n}$$

and the average

$$A(n,R) = \frac{\int_{0}^{2\pi} \vert R(exp(it) \vert dt}{2\pi}.$$

When $k=1$ so that $n=4$ we have that for one half of the possible polynomials $R(t)$ $$D(n,R) \leq A(n,R).$$

Question: What happens when $k>1.$

-
I don't know. Your $A(n,R)$ (which doesn't actually depend on $n$) is essentially the Mahler measure of $R$, q.v. – Gerry Myerson Feb 6 '11 at 1:00
Thanks to Gerry and to Or. In order to have a feeling of what happens when $n$ is big (so that computations may become more complicated). Can be useful to observe (besides nice gerry's observation) that $$A(n,R) = \int_{0}^{1} \vert R(exp(2\pi i t) \vert dt$$ so that seems that some kind of Riemann sums are involved ? – Luis H Gallardo Feb 6 '11 at 19:42
You can interpret $D(n,R)$ as a Riemann sum for $A(R)$. There are estimates for the difference between the two in terms of properties of $R$ and of the set $\lbrace0,1/n,\dots,(n-1)/n\rbrace$ - see Koksma's inequality, also the Erdos-Turan inequality. Those inequalities won't tell you anything about the sign of the difference. For that, you'd have to walk through the proofs of the inequalities. One reference is the Kuipers-Niederreiter book on Uniform Distribution of Sequences. – Gerry Myerson Feb 7 '11 at 0:04
Warn to myself: Since the polynomial $R(t)$ has degree $n-1$ (that depends on $n$) seems that we cannot let $n$ go to infinity to recover the integral from the Riemann Sum. – Luis H Gallardo Feb 7 '11 at 18:24
I just discover that these polynomials $R(t)$ are called Littlewood polynomials See the nice paper of Peter Borwein and Michael Mossinghoff (available on the net): The $L_1$ norm of polynomials. – Luis H Gallardo Feb 7 '11 at 19:15

The claims seems to be false. Numerical integration for $k=2, (n=8)$ gives that for $152$ out of the $256=2^8$ polynomials ($59.3\%$) you have $D(n,R) \leq A(n,R)$.

I do not see why having n a multiple of 4 should matter. The fact that for half of polynomials the inequality holds at $n=4$ seems like a coincident. You get the following numbers for different values of $n$: ($m$ is the number of polynomials for which $D \leq A$)

## $n$, $2^n$, $m$, $fraction$

1    2    2    1.000
2    4    4    1.000
3    8    6    0.750
4   16    8    0.500
5   32   16    0.500
6   64   36    0.562
7  128   66    0.515
8  256  152    0.593

-
@Or: Thanks again for calculations. I would know if the inequalities that hold depends or not on the corresponding circulant matrix being singular or not. More precisely we can attach to each such polynomial $R(t)= r_0 + \ldots + r_{n-1}t^{n-1}$ a circulant matrix $C(R)$ that has first row precisely $r_0, \ldots, r_{n-1}.$ Take the inequality $A(n,R) \leq D(n,R)$ for example. Is this inequality satisfied by about the same number of $R$'s with $det(C(R))=0$ as well as about the same number of $R$'s with $\det(C(R)) \neq 0$ ??? – Luis H Gallardo Feb 7 '11 at 18:35
That's interesting. Why is the relation to the circulant matrix? For $n=4$ indeed $A \geq D$ iff $det(C)=0$. In general this doesn't hold but statistically it might be more likely to get $A \geq D$ when $det(C)=0$. For example, for $n=8$ you have $56 (A\geq D,det\neq 0)$, $96 (A\geq D,det=0)$, $72 (A < D,det \neq 0)$, $32 (A < D,det=0)$, – Or Zuk Feb 11 '11 at 6:38