MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.$

share|cite|improve this question
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
up vote 1 down vote accepted

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
share|cite|improve this answer
@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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.