Journal de Théorie des Nombres de Bordeaux

J. Brian Conrey

Nina C. Snaith

Triple correlation of the Riemann zeros

L. J. P Kilford

On the slopes of the ${U_5}$ operator acting on overconvergent modular forms

Fedor Pakovich

Conservative polynomials and yet another action of $\operatorname{Gal}(\bar{\mathbb{Q}}/\mathbb{Q})$ on plane trees

Tamás Erdélyi

Tamás ERDÉLYI
Extensions of the Bloch–Pólya theorem on the number of real zeros of
polynomials
Tome 20, no 2 (2008), p. 281-287.
<http://jtnb.cedram.org/item?id=JTNB_2008__20_2_281_0>
© Université Bordeaux 1, 2008, tous droits réservés.
L’accès aux articles de la revue « Journal de Théorie des Nom-
bres de Bordeaux » (http://jtnb.cedram.org/), implique l’accord
avec les conditions générales d’utilisation (http://jtnb.cedram.
org/legal/). Toute reproduction en tout ou partie cet article sous
quelque forme que ce soit pour tout usage autre que l’utilisation à
fin strictement personnelle du copiste est constitutive d’une infrac-
tion pénale. Toute copie ou impression de ce fichier doit contenir la
présente mention de copyright.
cedram
Article mis en ligne dans le cadre du
Centre de diffusion des revues académiques de mathématiques
http://www.cedram.org/
Journal de Théorie des Nombres
de Bordeaux 20 (2008), 281-287
Extensions of the Bloch–Pólya theorem on the
number of real zeros of polynomials
par Tamás ERDÉLYI
Résumé. Nous prouvons qu’il existe des constantes absolues c1 >
0 et c2 > 0 telles que pour tout
{a0, a1, . . . , an} ⊂ [1,M ] , 1 ≤ M ≤ exp(c1n1/4) ,
il existe
b0, b1, . . . , bn ∈ {−1, 0, 1}
tels que
P (z) =
n∑
j=0
bjajz
j
a au moins c2n1/4 changements de signe distincts dans ]0, 1[. Cela
améliore et étend des résultats antérieurs de Bloch et Pólya.
Abstract. We prove that there are absolute constants c1 > 0
and c2 > 0 such that for every
{a0, a1, . . . , an} ⊂ [1,M ] , 1 ≤ M ≤ exp(c1n1/4) ,
there are
b0, b1, . . . , bn ∈ {−1, 0, 1}
such that
P (z) =
n∑
j=0
bjajz
j
has at least c2n1/4 distinct sign changes in (0, 1). This improves
and extends earlier results of Bloch and Pólya.
1. Introduction
Let Fn denote the set of polynomials of degree at most n with coefficients
from {−1, 0, 1}. Let Ln denote the set of polynomials of degree n with
coefficients from {−1, 1}. In [6] the authors write
“The study of the location of zeros of these classes of polynomials begins
with Bloch and Pólya [2]. They prove that the average number of real zeros
Manuscrit reçu le 29 janvier 2008.
282 Tamás Erdélyi
of a polynomial from Fn is at most c
√
n. They also prove that a polynomial
from Fn cannot have more than
cn log log n
log n
real zeros. This quite weak result appears to be the first on this subject.
Schur [13] and by different methods Szegő [15] and Erdős and Turán [8]
improve this to c
√
n log n (see also [4]). (Their results are more general,
but in this specialization not sharp.)
Our Theorem [4.1] gives the right upper bound of c
√
n for the num-
ber of real zeros of polynomials from a much larger class, namely for all
polynomials of the form
p(x) =
n∑
j=0
ajx
j , |aj | ≤ 1 , |a0| = |an| = 1 , aj ∈ C .
Schur [13] claims that Schmidt gives a version of part of this theorem.
However, it does not appear in the reference he gives, namely [12], and we
have not been able to trace it to any other source. Also, our method is able
to give c
√
n as an upper bound for the number of zeros of a polynomial
p ∈ Pcn with |a0| = 1, |aj | ≤ 1, inside any polygon with vertices in the unit
circle (of course, c depends on the polygon). This may be discussed in a
later publication.
Bloch and Pólya [2] also prove that there are polynomials p ∈ Fn with
(1.1)
cn1/4√
log n
distinct real zeros of odd multiplicity. (Schur [13] claims they do it for
polynomials with coefficients only from {−1, 1}, but this appears to be
incorrect.)
In a seminal paper Littlewood and Offord [11] prove that the number of
real roots of a p ∈ Ln, on average, lies between
c1 log n
log log log n
and c2 log2 n
and it is proved by Boyd [7] that every p ∈ Ln has at most c log2 n/ log log n
zeros at 1 (in the sense of multiplicity).
Kac [10] shows that the expected number of real roots of a polynomial of
degree n with random uniformly distributed coefficients is asymptotically
(2/π) log n. He writes “I have also stated that the same conclusion holds if
the coefficients assume only the values 1 and −1 with equal probabilities.
Upon closer examination it turns out that the proof I had in mind is inap-
plicable.... This situation tends to emphasize the particular interest of the
Extensions of the Bloch–Pólya theorem 283
discrete case, which surprisingly enough turns out to be the most difficult.”
In a recent related paper Solomyak [14] studies the random series
∑
±λn.”
In fact, the paper [5] containing the “polygon result” mentioned in the
above quote appeared sooner than [6]. The book [4] contains only a few
related weaker results. Our Theorem 2.1 in [6] sharpens and generalizes
results of Amoroso [1], Bombieri and Vaaler [3], and Hua [9] who give
versions of that result for polynomials with integer coefficients.
In this paper we improve the lower bound (1.1) in the result of Bloch
and Pólya to cn1/4. Moreover we allow a much more general coefficient
constraint in our main result. Our approach is quite different from that of
Bloch and Pólya.
2. New result
Theorem 2.1. There are absolute constants c1 > 0 and c2 > 0 such that
for every
{a0, a1, . . . , an} ⊂ [1,M ] , 1 ≤ M ≤ exp(c1n1/4) ,
there are
b0, b1, . . . , bn ∈ {−1, 0, 1}
such that
P (z) =
n∑
j=0
bjajz
j
has at least c2n1/4 distinct sign changes in (0, 1).
3. Lemmas
Let D := {z ∈ C : |z| < 1} be the open unit disk. Denote by SM the
collection of all analytic functions f on the open unit disk D that satisfy
|f(z)| ≤ M
1− |z|
, z ∈ D .
Let ‖f‖A := supx∈A |f(x)|. To prove Theorem 2.1 our first lemma is the
following.
Lemma 3.1. There is an absolute constants c3 > 0 such that
‖f‖[α,β] ≥ exp
(−c3(1 + log M)
β − α
)
for every f ∈ SM and 0 < α < β ≤ 1 with |f(0)| ≥ 1 and for every M ≥ 1.
This follows from the lemma below by a linear scaling:
284 Tamás Erdélyi
Lemma 3.2. There are absolute constants c4 > 0 and c5 > 0 such that
|f(0)|c5/a ≤ exp
(
c4(1 + log M)
a
)
‖f‖[1−a,1]
for every f ∈ SM and a ∈ (0, 1].
To prove Lemma 3.2 we need some corollaries of the following well known
result.
Hadamard three circles theorem. Let 0 < r1 < r2. Suppose f is regular
in
{z ∈ C : r1 ≤ |z| ≤ r2} .
For r ∈ [r1, r2], let
M(r) := max
|z|=r
|f(z)| .
Then
M(r)log(r2/r1) ≤ M(r1)log(r2/r)M(r2)log(r/r1) .
Corollary 3.1. Let a ∈ (0, 1]. Suppose f is regular inside and on the ellipse
Ea with foci at 1− a and 1− a + 14a and with major axis[
1− a− 9a
64
, 1− a + 25a
64
]
.
Let Ẽa be the ellipse with foci at 1− a and 1− a + 14a and with major axis[
1− a− a
32
, 1− a + 9a
32
]
.
Then
max
z∈Ẽa
|f(z)| ≤
(
max
z∈[1−a,1−a+ 14a]
|f(z)|
)1/2 (
max
z∈Ea
|f(z)|
)1/2
.
Proof. This follows from the Hadamard three circles theorem with the sub-
stitution
w =
a
8
(
z + z−1
2
)
+
(
1− a + a
8
)
.
The Hadamard three circles theorem is applied with r1 := 1, r := 2, and
r2 := 4. 
Corollary 3.2. For every f ∈ SM and a ∈ (0, 1] we have
max
z∈Ẽa
|f(z)| ≤
(
64M
39a
)1/2(
max
z∈[1−a,1]
|f(z)|
)1/2
.
Extensions of the Bloch–Pólya theorem 285
Proof of Lemma 3.2. Let f ∈ SM and h(z) = 12(1 − a)(z + z
2). Observe
that h(0) = 0, and there are absolute constants c6 > 0 and c7 > 0 such
that
|h(eit)| ≤ 1− c6t2 , −π ≤ t ≤ π ,
and for t ∈ [−c7a, c7a], h(eit) lies inside the ellipse Ẽa. Now let m :=
bπ/(c7a)c+1. Let ξ := exp(2πi/(2m)) be the first 2m-th root of unity, and
let
g(z) =
2m−1∏
j=0
f(h(ξjz)) .
Using the Maximum Principle and the properties of h, we obtain
|f(0)|2m = |g(0)| ≤ max
|z|=1
|g(z)| ≤
(
max
z∈Ẽa
|f(z)|
)2 m−1∏
k=1
(
M
c6(πk/m)2
)2
=
(
max
z∈Ẽa
|f(z)|
)2
M2m−2 exp(c8(m− 1))
(
mm−1
(m− 1)!
)4
<
(
max
z∈Ẽa
|f(z)|
)2
(Me)c9(m−1)
with absolute constants c8 and c9, and the result follows from Corollary
3.2. 
4. Proof of theorem 2.1
Proof of Theorem 2.1. Let L ≤ 12n
1/2 and
M(P ) := (P (1− n−1/2), P (1− 2n−1/2), . . . , P (1− Ln−1/2))
∈ [−M
√
n, M
√
n]L .
We consider the polynomials
P (z) =
n−1∑
j=0
bjajz
j , bj ∈ {0, 1} .
There are 2n such polynomials. Let K ∈ N. Using the box principle we can
easily deduce that (2K)L < 2n implies that there are two different
P1(z) =
n−1∑
j=0
bjajz
j , bj ∈ {0, 1} ,
and
P2(z) =
n−1∑
j=0
b̃jajz
j , b̃j ∈ {0, 1} ,
286 Tamás Erdélyi
such that
|P1(1− jn−1/2)− P2(1− jn−1/2)| ≤
M
√
n
K
, j = 1, 2, . . . , L .
Let
P1(z)− P2(z) =
n−1∑
j=m
βjajz
j , βj ∈ {−1, 0, 1}, bm 6= 0 .
Let 0 6= Q(z) := z−m(P1(z)− P2(z)). Then Q is of the form
Q(z) :=
n−1∑
j=0
γjajz
j , γj ∈ {−1, 0, 1} , γ0 ∈ {−1, 1} ,
and, since 1− x ≥ e−2x for all x ∈ [0, 1/2], we have
(4.1) |Q(1− jn−1/2)| ≤ exp(2Ln1/2)M
√
n
K
, j = 1, 2, . . . , L .
Also, by Lemma 3.1, there are
ξj ∈ Ij := [1− jn−1/2, 1− (j − 1)n−1/2] , j = 1, 2, . . . , L ,
such that
(4.2) |Q(ξj)| ≥ exp
(
−c3(1 + log M)
√
n
)
, j = 1, 2, . . . , L .
Now let L := b(1/16)n1/4c and 2K = exp(n3/4). Then (2K)L < 2n holds.
Also, if log M = O(n1/4), then (4.1) implies
(4.3) |Q(1− jn−1/2)| ≤ exp(−(3/4)n3/4) , j = 1, 2, . . . , L ,
for all sufficiently large n. Now observe that 1 ≤ M ≤ exp((64c3)−1n1/4)
yields that
|anxn| ≥|x|n ≥ exp(−2(1− x)) ≥ exp(−2Ln1/2)
≥ exp(−(1/8)n3/4) , x ∈ [1− Ln−1/2, 1− (L/2)n−1/2] ,(4.4)
and
|anxn| ≤M exp(−(L/2)n1/2)
≤ exp(−(1/33)n3/4) , x ∈ [1− Ln−1/2, 1− (L/2)n−1/2] ,(4.5)
for all sufficiently large n. Observe also that with log M ≤ (64c3)−1n1/4
(4.2) implies
(4.6) |Q(ξj)| > exp(−(1/63)n3/4) , j = 1, 2, . . . , L ,
for all sufficiently large n. Now we study the polynomials
S1(z) := Q(z)− anzn and S2(z) := Q(z) + anzn .
Extensions of the Bloch–Pólya theorem 287
These are of the requested special form. It follows from (4.3)–(4.6) that
either S1 or S2 has a sign change in at least half of the intervals Ij , j =
L,L−1, . . . bL/2c+2 , for all sufficiently large n, and the theorem is proved.

References
[1] F. Amoroso, Sur le diamètre transfini entier d’un intervalle réel. Ann. Inst. Fourier, Greno-
ble 40 (1990), 885–911.
[2] A. Bloch and G. Pólya, On the roots of certain algebraic equations. Proc. London Math.
Soc. 33 (1932), 102–114.
[3] E. Bombieri and J. Vaaler, Polynomials with low height and prescribed vanishing in an-
alytic number theory and Diophantine problems. Birkhäuser, 1987, pp. 53–73.
[4] P. Borwein and T. Erdélyi, Polynomials and polynomial inequalities. Springer-Verlag,
New York, 1995.
[5] P. Borwein and T. Erdélyi, On the zeros of polynomials with restricted coefficients. Illinois
J. Math. 41 (1997), 667–675.
[6] P. Borwein, T. Erdélyi, and G. Kós, Littlewood-type problems on [0, 1]. Proc. London
Math. Soc. 79 (1999), 22–46.
[7] D. Boyd, On a problem of Byrne’s concerning polynomials with restricted coefficients. Math.
Comput. 66 (1997), 1697–1703.
[8] P. Erdős and P. Turán, On the distribution of roots of polynomials. Ann. Math. 57 (1950),
105–119.
[9] L. K. Hua, Introduction to number theory. Springer-Verlag, Berlin, Heidelberg, New York,
1982.
[10] M. Kac, On the average number of real roots of a random algebraic equation, II. Proc.
London Math. Soc. 50 (1948), 390–408.
[11] J. E. Littlewood and A. C. Offord, On the number of real roots of a random algebraic
equation, II. Proc. Cam. Phil. Soc. 35 (1939), 133–148.
[12] E. Schmidt, Über algebraische Gleichungen vom Pólya–Bloch-Typos. Sitz. Preuss. Akad.
Wiss., Phys.-Math. Kl. (1932), 321.
[13] I. Schur, Untersuchungen über algebraische Gleichungen. Sitz. Preuss. Akad. Wiss., Phys.-
Math. Kl. (1933), 403–428.
[14] B. Solomyak, On the random series
∑
±λn (an Erdős problem). Ann. Math. 142 (1995),
611–625.
[15] G. Szegő, Bemerkungen zu einem Satz von E. Schmidtüber algebraische Gleichungen. Sitz.
Preuss. Akad. Wiss., Phys.-Math. Kl. (1934), 86–98.
Tamás Erdélyi
Department of Mathematics
Texas A&M University
College Station, Texas 77843
E-mail : terdelyi@math.tamu.edu
URL: http://www.math.tamu.edu/~tamas.erdelyi


Extensions of the Bloch–Pólya theorem on the number of real zeros of polynomials

Koopa Tak-Lun Koo

William Stein

Gabor Wiese

On the generation of the coefficient field of a newform by a single Hecke eigenvalue

Ján Mináč

Andrew Schultz

John Swallow

Automatic realizations of Galois groups with cyclic quotient of order ${p^n}$

Élie Mosaki

Partitions sans petites parts (II)

Fumio Sairaiji

Takuya Yamauchi

On rational torsion points of central $\mathbb{Q}$-curves

Mark Watkins

On elliptic curves and random matrix theory

Robert Benedetto

Jean-Yves Briend

Hervé Perdry

Dynamique des polynômes quadratiques sur les corps locaux

Not a member yet

Triple correlation of the Riemann zeros

On the slopes of the ${U_5}$ operator acting on overconvergent modular forms