ZEROS OF FEKETE POLYNOMIALS

Brian Conrey, Andrew Granville and Bjorn Poonen

Dirichlet noted that, from the formula

Γ(s) = n^{s} ∫_{0}^{∞} x^{s−1}e^{nx}dx = n^{s} ∫_{0}^{1}(− log t)^{s−1}t^{n−1}dt,

we may obtain the identity

Γ(s)L (s, (\frac{·}{p})) = Γ(s) ∑_{n≥1} \frac{(\frac{n}{p})}{n^{s}} = ∫_{0}^{1}(− log t)^{s−1} ∑_{n≥1} (\frac{n}{p}) t^{n−1}dt

= ∫_{0}^{1} \frac{(− log t)^{s−1}}{t} \frac{f_{p}(t)}{1 − t^{p}} dt (0.1)

where (\frac{·}{p}) is the Legendre symbol and

(1.1)  f_{p}(t) := ∑_{a=0}^{p−1} (\frac{a}{p}) t^{a},

since f_{p}(t)/(1 − t^{p}) = ∑_{n≥1} χ(n)t^{n}. Equation (0.1) allowed Dirichlet to define

L (s, (\frac{·}{p})) as a regular function for all complex s. Fekete observed that if f_{p}(t)

has no real zeros t with 0 < t < 1, then L (s, (\frac{·}{p})) has no real zeros s > 0; and the f_{p}(t) are thus now known as Fekete polynomials. This follows easily from (0.1) since if L (s, (\frac{·}{p})) = 0 then the argument of the integrand in (0.1) must either always be zero, or must take both positive and negative values, in which case it takes the value zero somewhere in-between by the intermediate value theorem. Either way there is some value of t in the range 0 < t < 1 for which the integrand is zero, and thus f_{p}(t) = 0 since \frac{(− log t)^{s−1}}{t} \frac{1}{1−t^{p}} > 0 throughout this range.

As we shall report in section 9, among small primes p, there are only a few for which the Fekete polynomial f_{p}(t) has a real zero t in the range 0 < t < 1 (in fact, for just 23 of the primes up to 1000), which may be verified computationally. This implies that there are no positive real zeros of L (s, (\frac{·}{p})) for most such primes p, and in particular no Siegel zeros (which must be real). Given this implication it is interesting to note that for those primes p ≡ 3 mod 4 for which we did find an appropriate zero of the corresponding Fekete polynomial, the class number of

Typeset by AMS-TEX

Q(\sqrt{−p}) is surprisingly small (like for p = 43, 67, 163, …; see the table in section 8). Unfortunately this trend does not persist: Indeed Baker and Montgomery [1] proved that f_{p}(t) has a large number of zeros in (0, 1) for almost all primes p (that is, the number of such zeros → ∞ as p → ∞, and it seems likely that there are, in fact, ≍ log log p).

In this paper we shall look more systematically at f_{p}(t) by studying its complex zeros. If one uses zero locating software on this polynomial then one finds that, for primes p up to 1000, about half of the zeros lie on the unit circle; leading one to expect this to be the general phenomenon. It turns out to be fairly easy to prove that at least half of the zeros of f_{p}(t) are on the unit circle (that is |t| = 1): First note that

F_{p}(z) := z^{−p/2}f_{p}(z) = ∑_{a=1}^{(p−1)/2} (\frac{a}{p}) (z^{a−p/2} + (\frac{−1}{p}) z^{p/2−a})

by combining the a and p − a terms. Taking z = e^{2iπt} we have

(1.2)  F_{p} (e^{2iπt}) = \{ \begin{matrix}2 ∑_{a=1}^{(p−1)/2} (\frac{a}{p}) cos((2a − p)πt) & if p ≡ 1 mod 4 \\ 2i ∑_{a=1}^{(p−1)/2} (\frac{a}{p}) sin((2a − p)πt) & if p ≡ 3 mod 4 \end{matrix} .

Define H_{p}(t) = F_{p}(e^{2iπt})/2 if p ≡ 1 (mod 4), and H_{p}(t) = F_{p}(e^{2iπt})/2i if p ≡ 3 (mod 4). By (1.2) we see that H_{p}(t) is a periodic real-valued function when t is real.

Now if ζ_{p} = e^{2iπ/p} then, for all k not divisible by p, f_{p}(ζ_{p}^{k}) is a Gauss sum and has absolute value \sqrt{p} (see Lemma 3); therefore |F_{p}(ζ_{p}^{k})| = \sqrt{p}. Moreover

F_{p}(ζ_{p}^{k}) = (ζ_{p}^{k})^{−p/2} ∑_{a=1}^{p−1} (\frac{a}{p}) ζ_{p}^{ak} = (−1)^{k} (\frac{k}{p} ) ∑_{a=1}^{p−1} (\frac{ak}{p} ) ζ_{p}^{ak} = (−1)^{k} (\frac{k}{p} ) F_{p}(ζ_{p}).

Therefore if (\frac{k}{p} ) = (\frac{k+1}{p}) then H_{p}(ζ_{p}^{k}) and H_{p}(ζ_{p}^{k+1}) have different signs. However,

since H_{p}(z) is real-valued on the unit circle, it must change sign as z goes from ζ_{p}^{k} to ζ_{p}^{k+1} along the unit circle, and so must have a zero in-between (by the intermediate value theorem). Thus the number of zeros of H_{p}(z) (and so F_{p}(z)) on the unit circle is ≥ #\{k : 1 ≤ k ≤ p − 2 and (\frac{k}{p} ) = (\frac{k+1}{p})\} = \frac{p−3}{2}, as we shall see in the corollary to lemma 2.

Other than possible zeros at z = −1 and at z = 1, this accounts for all the zeros on the unit circle for each prime p < 500. So the question is, is this all, for all p? The answer is ‘no’:

Theorem 1. There exists a constant κ_{0}, 1 > κ_{0} > \frac{1}{2} such that

#{z : |z| = 1 and f_{p}(z) = 0} ∼ κ_{0}p as p → ∞.

We determine κ_{0} in terms of another constant κ_{1} defined as follows:

Theorem 2. Let F_{J} be the set of polynomials

g(x) = \frac{1}{x} + \frac{1}{1 − x} + ∑_{\begin{matrix}|j|<J \\ j≠0,−1 \end{matrix}} \frac{δ_{j}}{x + j}

where we allow each δ_{j} to take value +1 or −1. There exists a constant κ_{1}, \frac{1}{2} > κ_{1} > 0, such that

#{g ∈ F_{J} : g(x) = 0 for some x ∈ (0, 1)} ∼ κ_{1}#{g ∈ F_{J}}

as J → ∞. In fact κ_{0} = \frac{1}{2} + κ_{1}.

It is still an open question to determine the value of κ_{0}. We do know how to compute it as the value of an infinite dimensional integral, but this is not adequately illuminating. Towards the end of section 4 we give the lower bound κ_{0} ⪆ 0.565 . . .. Jeff Lagarias conjectures that κ_{0} = 1/\sqrt{3}; which is plausible for a number of reasons. First we would not expect our lower bound to be too far away from the correct answer (and indeed 1/\sqrt{3} ≈ 0.577 … is only a little bigger than our lower bound). Also, this is the proportion of zeros on the unit circle, on average over all ‘randomly chosen’ trigonometric polynomials that look like those in (1.2).^{1}

As we have already discussed, Gauss sums ∑_{a=1}^{p−1} (\frac{a}{p}) ζ_{p}^{ak} (and many generalizations) have the surprising property that they have absolute value exactly equal to \sqrt{p}. It is, we think, of interest to ask what happens when we replace the primitive pth root of unity ζ_{p}^{k} in the expression for a Gauss sum above, by some primitive 2pth root of unity. These may be written as ζ_{p}^{k+1/2} or ζ_{2p}^{2k+1}, or −ζ_{p}^{k}; so we must consider the values of f_{p}(−ζ_{p}^{k}). Do these all take on the same absolute value ? The answer we now see is ‘no’, as we evaluate the distribution of these absolute values:

Theorem 3. For any fixed real number ρ

#\{k : 1 ≤ k ≤ p such that H_{p} (ζ_{p}^{k+1/2}) < ρ\sqrt{p}\} ∼ c_{ρ}p

as p → ∞ where

c_{ρ} = \frac{1}{2} + \frac{1}{π} ∫_{x=0}^{∞} sin(ρπx) ∏_{\begin{matrix}n≥1 \\ n odd \end{matrix}} cos^{2} (\frac{2x}{n}) \frac{dx}{x}.

After proving this in section 4, we indicate how our proof may be modified to establish two related results. First, to show that max_{|z|=1} |f_{p}(z)| ≫ \sqrt{p} log log p, so re-establishing a result of Montgomery [3]. Second to understand the distribution of the values of the Fekete polynomial at (p − 1)st roots of unity.

By (1.1) we have

t^{p}f_{p}(1/t) = (\frac{−1}{p}) f_{p}(t)

1See [5] for details of examples of classes of ‘randomly chosen’ trigonometric polynomials for which this holds.

and so the zeros of f_{p}(t), other than t = 0, are symmetric about the unit circle (i.e. they come in pairs other than at t = 0, ±1). We also note that, for |t| > 1,

|f_{p}(t)/t^{p−1}| = |∑_{a=0}^{p−1} (\frac{a}{p}) \frac{1}{t^{p−1−a}} | ≥ 1 − ∑_{a=0}^{p−2} \frac{1}{|t|^{p−1−a}} > 1 − \frac{1}{|t| − 1}.

However if |t| ≥ 2 then 1 − 1/(|t| − 1) ≥ 0, and so f_{p}(t) has no zeros in |t| ≥ 2. By symmetry it has no zeros in |t| ≤ \frac{1}{2}. Thus

Proposition 1. The zeros of f_{p}(t), other than at 0, 1 and −1 come in pairs α, 1/α. Moreover, other than 0, they all lie in the annulus \{r ∈ ℂ : \frac{1}{2} < |r| < 2\}.

If we differentiate H_{p}(t) with respect to t then we get another trigonometric function which is real-valued on [0, 1) (and even the whole real line). Transforming the new function back to one in the variable z, we see it still has no more than p−1 zeros. This will remain true no matter how often we differentiate it. Moreover we shall prove that H_{p}^{(k+1)} has at least as many zeros as H_{p}^{(k)} on the unit circle. In fact this is true for general, finite, real-valued trigonometric functions. If we were able to show that when k is sufficiently large the number of zeros of H_{p}^{(k)} on the unit circle is κ_{0}p, then we would have an easy proof of Theorem 1. However this is not true, since in section 7 we show the following results.

Theorem 4. Consider the trigonometric function

f(t) = ∑_{n=1}^{N}{a_{n} cos(2πnt) + b_{n} sin(2πnt)} for 0 ≤ t < 1,

where a_{n}, b_{n} are real numbers with a_{N}^{2} + b_{N}^{2} ≠ 0 (and let d_{n} = (a_{n}^{2} + b_{n}^{2})^{1/2}). Evidently f^{(k)}(t) is of the same form. Let n_{k} be the number of zeros of f^{(k)}(t) in the range 0 ≤ t < 1. Then

(a) 2 ≤ n_{0} ≤ n_{1} ≤ n_{2} ≤ ⋯ ≤ 2N.

(b) If k is sufficiently large, in fact if

(1.3)  d_{N}N^{k} ≥ d_{1}1^{k} + d_{2}2^{k} + ⋯ + d_{N−1}(N − 1)^{k},

then n_{k} = 2N; that is f(t) has as many zeros as possible on [0, 1). If (1.3) does hold then all the zeros are simple except in the case that we have equality in (1.3), with a_{N} = d_{N}, every other a_{n} = −d_{n}, and every b_{n} = 0. Let t_{0} be chosen in [0, 1) so that tan(2πNt_{0}) = −a_{N}/b_{N}. Then the zeros

of f^{(k)}(t) lie at

(t_{0} + i/4N) (mod 1) + O(e^{−k/N})

where 1 ≤ i ≤ 4N and i ≡ k (mod 2).

Corollary 1. If k ≥ (\frac{1}{2} log 2) p then H_{p}^{(k)}(t) has exactly (p − 1) zeros in [0, 1).

Theorem 4 begs the question of whether a similar phenomena happens with realvalued Fourier series, though of infinite length. That is, is it true that if f(t) is such a Fourier series then the number of zeros of f^{(k)}(t) in [0, 1), tends to infinity as k → ∞? If so then do zeros tend to be dense on every open subset of [0, 1) ? If not, how do they cluster ? It is evident that, by the methods of proof in Theorem 4, if a_{n}^{2} + b_{n}^{2} → 0 very rapidly as n → ∞ then we will get such a result^{2}.

Acknowledgements: We thank Jeff Lagarias for facilitating this joint endeavour; and Neil Dummigan, Hugh Montgomery, Bob Vaughan, Trevor Wooley and especially K. Soundararajan for some helpful discussions.

§2. Facts about finite fields

Lemma 1 (Gauss). For any character χ (mod p) and integer k, not divisible by p, we have

∑_{a=1}^{p−1} χ(a)ζ_{p}^{ak} = χ̄(k) ∑_{a=1}^{p−1} χ(a)ζ_{p}^{a}.

In particular f_{p}(ζ_{p}^{k}) = (\frac{k}{p} ) f_{p}(ζ_{p}), whereas f_{p}(1) = 0.

Proof. Writing b to be the least residue of ak (mod p), we have

∑_{a=1}^{p−1} χ(a)ζ_{p}^{ak} = ∑_{b=1}^{p−1} χ(bk^{−1})ζ_{p}^{b} = χ̄(k) ∑_{b=1}^{p−1} χ(b)ζ_{p}^{b}.

Lemma 2 (Gauss). For any non-principal character χ (mod p), we have

∑_{b=0}^{p−1} χ(b)χ̄(b + k) = \{ \begin{matrix}p − 1 & if p | k \\ −1 & if p |̸ k \end{matrix}

Proof. If p | k then

∑_{b=0}^{p−1} χ(b)χ̄(b + k) = ∑_{b=0}^{p−1} |χ(b)|^{2} = 1.0 + (p − 1) · 1 = p − 1.

If p ∤ k then, letting b ≡ ak (mod p), we get

∑_{b=0}^{p−1} χ(b)χ̄(b + k) = ∑_{a=0}^{p−1} χ(ak)χ̄(ak + k) = ∑_{a=0}^{p−1} χ(b)χ̄(b + k)|χ(k)|^{2} = σ

2For example, we are able to prove such a result if for s_{n} = (a_{n}^{2} + b_{n}^{2})^{1/2} we have s_{n+1} ≤ s_{n}^{2}/16s_{n−1} for all n ≥ 2.

6 BRIAN CONREY, ANDREW GRANVILLE AND BJORN POONEN

say. Thus, summing up over all values of k (mod p) we get

(p − 1)σ + (p − 1) = ∑_{k=1}^{p−1} (∑_{b=0}^{p−1} χ(b)χ̄(b + k)) + ∑_{b=0}^{p−1} χ(b)χ̄(b)

= (∑_{b=0}^{p−1} χ(b)) (∑_{c=0}^{p−1} χ(c)) = 0 letting c ≡ b + k (mod p).

Corollary. # \{b (mod p) : (\frac{b}{p}) = (\frac{b+1}{p})\} = \frac{p−3}{2}

# \{b (mod p) : (\frac{b}{p}) = − (\frac{b+1}{p})\} = \frac{p−1}{2}

Lemma 3. f_{p}(ζ_{p}^{k}) = ±\sqrt{(\frac{−1}{p}) p} Proof. By Lemma 1 we have

(p − 1)f_{p}(ζ_{p}^{k})^{2} = ∑_{j=0}^{p−1} f_{p}(ζ_{p}^{j})^{2} = ∑_{j=0}^{p−1} ∑_{a,b=0}^{p−1} (\frac{ab}{p}) ζ_{p}^{(a+b)j}

= ∑_{a,b=1}^{p−1} (\frac{ab}{p}) ∑_{j=0}^{p−1} ζ_{p}^{(a+b)j} = p ∑_{\begin{matrix}a=1 \\ b=p−a \end{matrix}}^{p−1} (\frac{ab}{p}) = p (\frac{−1}{p}) (p − 1)

and the result follows. Lemma 4. ∏_{j=1}^{p−1} (1 − ζ_{p}^{j}) = p Proof. We take x = 1 in

x^{p−1} + x^{p−2} + ⋯ + 1 = \frac{x^{p} − 1}{x − 1} = ∏_{j=1}^{p−1} (x − ζ_{p}^{j}) .

Lemma 5. ∑_{k=1}^{p−1} \frac{1}{sin^{2}(kπ/p)} = \frac{p^{2}−1}{3} for all integer p ≥ 2. Proof. If ζ^{p} = 1, ζ ≠ 1 then −p/(1 − ζ) = ζ + 2ζ^{2} + ⋯ + (p − 1)ζ^{p−1}, as may be easily verified. Therefore the sum above equals

∑_{ζ^{p}=1,ζ≠1} \frac{−4}{(ζ^{1/2} − ζ^{−1/2})^{2}} = −4 ∑_{ζ^{p}=1,ζ≠1} \frac{ζ}{(1 − ζ)^{2}} = \frac{−4}{p^{2}} ∑_{1≤i,j≤p−1} ij ∑_{ζ^{p}=1,ζ≠1} ζ^{i+j+1}

= \frac{−4}{p^{2}} \{p ∑_{\begin{matrix}1≤i,j≤p−1 \\ p|i+j+1 \end{matrix}} ij − ∑_{1≤i,j≤p−1} ij\}

= \frac{−4}{p^{2}} \{p ∑_{1≤i,j≤p−1} i(p − 1 − i) − ( ∑_{1≤i≤p−1} i)^{2}\}

and the result follows.

Lemma 6. For all characters χ (mod p) and k ≥ 0 we have

\frac{1}{m!p^{m}} ∑_{a=0}^{p−1} χ(a)a^{m} = −τ(χ) ∑_{k=0}^{m} \frac{(1 + (−1)^{k}χ(−1))}{(m − k + 1)!} \frac{L(k, χ̄)}{(2iπ)^{k}}

where τ(χ) := ∑_{a=0}^{p−1} χ(a)e^{2iπa/p}.

Proof. We shall prove that

(2.1)  \frac{1}{k!} ∑_{a=0}^{p−1} χ(a)B_{k}(a/p) = −\frac{τ(χ)}{(2iπ)^{k}} (1 + (−1)^{k}χ(−1))L(k, χ̄).

where B_{k}(t) is the kth Bernoulli polynomial. The result is then deduced by noticing that \frac{1}{m!p^{m}} ∑_{a=0}^{p−1} χ(a)a^{m} is the coefficient of x^{m} in ∑_{a=0}^{p−1} χ(a)e^{(a/p)x}, which is (e^{x} − 1)/x times the generating function for the left side of (2.1).

Proving (2.1) for k = 0 and 1 is straightforward once one knows L(0, χ̄) = 0 if χ(−1) = 1: and Dirichlet’s formula, which is the case for k = 1, χ(−1) = −1 above. If k ≥ 2 then we note, via Fourier analysis, that for 0 ≤ x < 1 we have

\frac{1}{k!}B_{k}(x) = − ∑_{m≠0} \frac{e^{2iπmx}}{(2iπm)^{k}} .

Therefore the left side of (2.1) equals

− ∑_{m≠0} \frac{1}{(2iπm)^{k}} ∑_{a=0}^{p−1} χ(a)e^{2iπ(a/p)m},

and the result follows using Lemma 1, and by pairing up the m and −m terms.

Lemma 7. If p ≡ 1 (mod 4) then f_{p}(t) = t(t−1)^{2}(t+1)f_{p}^{∗}(t); and if p ≡ 3 (mod 4) then f_{p}(t) = t(t − 1)f_{p}^{∗}(t), where f_{p}^{∗}(t) is non-zero (mod p) at t = −1, 0, 1.

Proof. Let’s begin with primes p ≡ 3 (mod 4).

f_{p}(−1) = ∑_{a=1}^{p−1} (\frac{a}{p}) (−1)^{a} = ∑_{\begin{matrix}a=1 \\ aeven \end{matrix}}^{p−1} (\frac{a}{p}) − 2 ∑_{\begin{matrix}b=1 \\ beven \end{matrix}}^{p−1} (\frac{p − b}{p})

where a = p − b is odd in the second sum,

= 2 ∑_{d=1}^{(p−1)/2} (\frac{2d}{p}) = 2 (\frac{2}{p}) ∑_{d=1}^{(p−1)/2} (\frac{d}{p}) = \frac{1}{((\frac{2}{p}) − \frac{1}{2})}h(−p) ≠ 0,

since the class number of ℚ(\sqrt{−p}) is

h(−p) = −\frac{1}{p} ∑_{a=1}^{p−1} a (\frac{a}{p}) = \frac{1}{(2 − (\frac{2}{p}))} ∑_{a=1}^{(p−1)/2} (\frac{a}{p}) .

8 BRIAN CONREY, ANDREW GRANVILLE AND BJORN POONEN

Now, for any p, f_{p}(1) = ∑_{a=1}^{p−1} (\frac{a}{p}) = 0. Moreover if p ≡ 3 (mod 4), p > 3, then

f′_{p}(1) = ∑_{a=1}^{p−1} a (\frac{a}{p}) = −ph(−p) ≠ 0.

However if p ≡ 1 (mod 4) then, by the above manipulations,

f_{p}(−1) = ∑_{\begin{matrix}a=1 \\ a even \end{matrix}}^{p−1} \{(\frac{a}{p}) − (\frac{a}{p})\} = 0

and

f′_{p}(1) = \frac{1}{2} ∑_{a=1}^{p−1} (\frac{a}{p}) (a + p − a) = 0.

However, since L (0, (\frac{.}{p})) = 0, we get by Lemma 6 with m = 2, that

f′′_{p}(1) = ∑_{a=1}^{p−1} a(a − 1) (\frac{a}{p}) = ∑_{a=1}^{p−1} a^{2} (\frac{a}{p}) = \frac{p^{2}}{π^{2}} f_{p}(ζ_{p})L (2, (\frac{.}{p})) ≠ 0.

Finally, we shall show that

(2.2)  f′_{p}(−1) = \frac{1}{p} (1 − 4 (\frac{2}{p})) ∑_{a=1}^{p−1} a^{2} (\frac{a}{p}) ≠ 0,

as noted immediately above. To prove (2.2) we shall make frequent use of the fact that (\frac{a}{p}) = (\frac{p−a}{p}); for example

(2.3)  ∑_{\begin{matrix}a=1 \\ a even \end{matrix}}^{p−1} (\frac{a}{p}) = \frac{1}{2} ∑_{\begin{matrix}a=1 \\ a even \end{matrix}}^{p−1} ((\frac{a}{p}) + (\frac{p − a}{p})) = 0.

So first note that, since a^{2} + (p − a)^{2} = 2a^{2} − 2ap + p^{2}, we have

∑_{a=1}^{p−1} a^{2} (\frac{a}{p}) = ∑_{\begin{matrix}a=1 \\ a even \end{matrix}}^{p−1} (\frac{a}{p}) (2a^{2} − 2ap + p^{2}); and
4 (\frac{2}{p}) ∑_{a=1}^{p−1} a^{2} (\frac{a}{p}) = 4 ∑_{b=1}^{\frac{p−1}{2}} (\frac{2b}{p}) (2b^{2} − 2bp + p^{2}) = ∑_{\begin{matrix}a=1 \\ a even \end{matrix}}^{p−1} (\frac{a}{p}) (2a^{2} − 4ap + 4p^{2})

taking a = 2b in the line above. Combining these two, and using (2.3), we note that the right side of (2.2) equals

∑_{\begin{matrix}a=1 \\ a even \end{matrix}}^{p−1} (\frac{a}{p}) (2a − 3p) = ∑_{\begin{matrix}a=1 \\ a even \end{matrix}}^{p−1} (\frac{a}{p}) (a − (p − a)) = ∑_{a=1}^{p−1} (\frac{a}{p}) (−1)^{a}a = f′_{p}(−1),

and the result is proved.

ZEROS OF FEKETE POLYNOMIALS 9

Lemma 8. Fix δ_{j} ∈ {−1, 1} for each j, |j| < J.

#\{x (mod p) : (\frac{x − j}{p} ) = δ_{j} for all |j| < J\} = \frac{p}{2^{2J−1}} + O(J\sqrt{p})

uniformly for all positive integers J. Proof. The above equals

∑_{x=1}^{p} \frac{1}{2^{2J−3}} ∏_{|j|<J} (1 + δ_{j} (\frac{x − j}{p} )) + O(J) =

= \frac{p}{2^{2J−3}} + O (\frac{1}{2^{2J−3}} ∑_{\begin{matrix}S⊆\{|j|<J\} \\ S≠∅ \end{matrix}} ∑_{x=1}^{p} (\frac{∏_{j∈S}(x − j)}{p}) + J) .

Now, by Weil’s Theorem, if f(x) is a squarefree polynomial (mod p) then

|∑_{x=1}^{p} (\frac{f(x)}{p})| ≪ (degree f)\sqrt{p}

so the above is

= \frac{p}{2^{2J−3}} + O (\frac{\sqrt{p}}{2^{2J−3}} ∑_{m=1}^{2J−3} ( \begin{matrix}2J − 3 \\ m \end{matrix} ) m + J)

and the result follows.

Lemma 9. \frac{2}{π} ∫_{0}^{∞} \frac{sin kx}{x}dx = \{ \begin{matrix}1 & if k > 0 \\ −1 & if k < 0 \end{matrix}

Proof. Changing variables with y = kx gives dy/y = dx/x and so

∫_{0}^{∞} \frac{sin(kx)}{x}dx = ± ∫_{0}^{∞} \frac{sin y}{y} dy

with the sign being + if k > 0, and − if k < 0. The last integral is well-known to equal π/2.

§3. An expansion for f_{p}(z)

By Lemma 1, f_{p}(ζ_{p}^{k}) = (\frac{k}{p} ) f_{p}(ζ_{p}), for 1 ≤ k ≤ p, and f_{p}(1) = 0, so by Lagrangian interpolation we have

f_{p}(z) = ∑_{k=0}^{p−1} (f_{p}(ζ_{p}^{k}) ∏_{\begin{matrix}j=0 \\ j≠k \end{matrix}}^{p−1} \frac{z − ζ_{p}^{j}}{ζ_{p}^{k} − ζ_{p}^{j}} ) .

Let α = ∏_{j=1}^{p−1} (1 − ζ_{p}^{j}) /f_{p}(ζ_{p}). Note that

∏_{\begin{matrix}j=0 \\ j≠k \end{matrix}}^{p−1} (ζ_{p}^{k} − ζ_{p}^{j}) = ∏_{\begin{matrix}j=0 \\ j≠k \end{matrix}}^{p−1} ζ_{p}^{k} (1 − ζ_{p}^{j−k}) = ζ_{p}^{−k} ∏_{i=1}^{p−1} (1 − ζ_{p}^{i})

and so

(3.1)  \frac{αf_{p}(z)}{z^{p} − 1} = ∑_{k=1}^{p−1} \frac{ζ_{p}^{k} (\frac{k}{p} )}{z − ζ_{p}^{k}}

Now note that z^{p/2}−z^{−p/2} ∈ iR for all |z| = 1, so that αz^{−p/2}f_{p}(z)/(z^{p/2}−z^{−p/2}) = αf_{p}(z)/(z^{p} − 1) ∈ iR. We wish to consider f_{p}(z) as z goes around the unit circle from ζ_{p}^{K} to ζ_{p}^{K+1}. To do this we write z = ζ_{p}^{K+x} = ζ_{p}^{K}e^{2iπx/p} and then let

g_{p,K}(x) := i (\frac{K}{p} ) \frac{αf_{p}(z)}{z^{p} − 1}|_{z=ζ_{p}^{K+x}} = i (\frac{K}{p} ) ∑_{k=K−(\frac{p−1}{2})}^{K+(\frac{p−1}{2})} \frac{(\frac{k}{p} )}{ζ_{p}^{K−k+x} − 1}

Note that for g = g_{p,K}, we have

lim_{x→0^{+}} g(x) = ∞ and lim_{x→1^{−}} g(x) = − (\frac{K}{p} ) (\frac{K + 1}{p}) ∞.

Therefore

g′(x) = −i (\frac{K}{p} ) ∑_{|k−K|< \frac{p}{2}} \begin{matrix}( & \frac{k}{p} & ) \\ (ζ_{p}^{K−k+x} − 1) & 2 \end{matrix} ζ_{p}^{K−k+x} · \frac{2iπ}{p}

= − (\frac{K}{p} ) \frac{π}{2p} ∑_{|k−K|< \frac{p}{2}} \begin{matrix}( & \frac{k}{p} & ) \\ sin & 2 & (\frac{π}{p} (K − k + x)) \end{matrix}

Now if (\frac{K}{p} ) = (\frac{K+1}{p}) then, by Lemma 5,

|g′(x)| ≥ \frac{π}{2p} (\frac{1}{sin^{2} (\frac{π}{p} x)} + \frac{1}{sin^{2} \frac{π}{p} (1 − x)} − ∑_{\begin{matrix}j≠0,1 \\ |j|<p/2 \end{matrix}} \frac{1}{sin^{2} \frac{π}{p} (x − j)})

≥ \frac{π}{2p} \{\frac{2}{sin^{2} (\frac{π}{2p})} − \frac{p^{2} − 1}{3}\} > 0

since the sum of the first two terms are evidently minimized when x = 1/2. Therefore g′(x) ≠ 0 for all x ∈ (0, 1). Thus g is monotonic in [0, 1] going from ∞ to −∞, and so has exactly one zero in this interval.

Moreover

g′′(x) = \frac{π^{2}}{p^{2}} (\frac{K}{p} ) ∑_{|k−K|<p/2} \begin{matrix}(\frac{k}{p} ) & cos & (\frac{π}{p} (K − k + x)) \\ sin & 3 & (\frac{π}{p} (K − k + x)) \end{matrix}

Now if (\frac{K}{p} ) = − (\frac{K+1}{p}) then

|g′′(x)| ≥ \frac{π^{2}}{p^{2}} (\frac{cos \frac{π}{p} x}{sin^{3} \frac{π}{p} x} + \frac{cos \frac{π}{p} (1 − x)}{sin^{3} \frac{π}{p} (1 − x)} − ∑_{\begin{matrix}|j|<p/2 \\ j≠0,1 \end{matrix}} \frac{cos \frac{π}{p} (j − x)}{| sin \frac{π}{p} (j − x)|^{3}} )

≥ \frac{π^{2}}{p^{2}} μ (\frac{1}{sin^{2} (\frac{π}{p} x)} + \frac{1}{sin^{2} \frac{π}{p} (1 − x)} − ∑_{\begin{matrix}j≠0,1 \\ |j|<p/2 \end{matrix}} \frac{1}{sin^{2} \frac{π}{p} (x − j)}) > 0

where μ is the minimum of cos (\frac{π}{p} t) / sin^{3} (\frac{π}{p} t) over t = x, 1 − x (the inequality follows from breaking the inequality down to each term because cos t/ sin t decreases rapidly as t goes from 0 to π/2), and the last step follows from Lemma 5.

Thus g′(x) is monotonic in [0, 1] and goes from −∞ to +∞, and so has exactly one zero in the interval. If we suppose g(0) = g(1) = ∞ and g′(x_{0}) = 0 then we must determine whether g(x_{0}) > 0, = 0 or < 0 to find out whether g has 0, 1 or 2 zeros in the interval.

§4. Pseudo-Gauss Sums

We wish to evaluate f_{p} (ζ_{p}^{K+1/2}). Now, by Lemmas 5 and 6, we have |α| = \sqrt{p}, and so by (3.1)

f_{p} (ζ_{p}^{K+ \frac{1}{2}} ) = ±\frac{2}{\sqrt{p}} ∑_{k=1}^{p−1} \frac{(\frac{k}{p} )}{ζ_{p}^{K−k+1/2} − 1} = ±\frac{2}{\sqrt{p}} ∑_{|j|<p/2} \frac{(\frac{K−j}{p} )}{ζ_{p}^{j+1/2} − 1}

where the sign ± is fixed. In (5.0) we shall see that if J → ∞ as p → ∞ then

(4.1)  f_{p} (ζ_{p}^{K+1/2}) = ±\frac{\sqrt{p}}{π} ( ∑_{|j|<J} \frac{(\frac{K−j}{p} )}{j + 1/2} + O (\frac{1}{J^{1/3}} ))

for almost all K, 1 ≤ K ≤ p. Thus, by Lemma 8, we have that for any fixed real number ρ

lim_{p→∞} \frac{#\{K : 1 ≤ K ≤ p and f_{p} (ζ_{p}^{K+1/2}) < ρ\sqrt{p}\}}{p}

exists and equals

lim_{J→∞} Prob(δ_{j} ∈ \{−1, 1\} : |j| < J : ∑_{|j|<J} \frac{δ_{j}}{j + 1/2} < πρ)

Now this probability equals (using Lemma 9)

∏_{|i|<J} (\frac{1}{2} ∑_{δ_{i}∈\{−1,1\}}) (\frac{1}{2} − \frac{1}{π} ∫_{x=0}^{∞} (sin (( ∑_{|J|<J} \frac{δ_{j}}{j + 1/2} − πρ) x))) \frac{dx}{x}

= \frac{1}{2} − \frac{1}{π} ∫_{x=0}^{∞} ∏_{|j|<J} (\frac{1}{2} ∑_{δ_{i}∈\{−1,1\}}) (\frac{e^{ix(∑_{|j|<J} \frac{δ_{j}}{j+1/2} −πρ)} − e^{−ix(∑_{|j|<J} \frac{δ_{j}}{j+1/2} −πρ)}}{2i} ) \frac{dx}{x}

= \frac{1}{2} − \frac{1}{π} ∫_{x=0}^{∞} ∏_{|j|<J} (\frac{e^{\frac{ix}{j+1/2}} + e^{− \frac{ix}{j+1/2}}}{2} ) (\frac{e^{−ixπρ} − e^{ixπρ}}{2i} ) \frac{dx}{x}

= \frac{1}{2} + \frac{1}{π} ∫_{x=0}^{∞} sin(ρπx) ∏_{|j|<J} cos (\frac{2x}{2j + 1}) \frac{dx}{x}.

Therefore, letting J → ∞, we get

c_{ρ} = \frac{1}{2} + \frac{1}{π} ∫_{x=0}^{∞} sin(ρπx)C(x)\frac{dx}{x} where C(x) := ∏_{\begin{matrix}n≥1 \\ n odd \end{matrix}} cos^{2} (\frac{2x}{n}) ,

and thus Theorem 3 is proved. Note that this integral does converge: For any x > 0 we have

C(x) ≪ \frac{1}{2^{3x/π}}

since this estimate is trivial for x ≤ 1, and otherwise we note that | cos (\frac{2x}{n}) | < 1/2 if 3x/π < n < 6x/π. Thus the part of the integral with x ≥ 1 is easily bounded. For x < 1 each cos \frac{2x}{n} = 1 + O (\frac{x^{2}}{n^{2}} ) and so

\frac{sin(ρπx)}{x}C(x) = ρ(1 + O((1 + ρ^{2})x^{2})).

This allows us to bound the rest of the integral.

Remark 1. We now use the above to study the multiplicative average size of f_{p}(ζ_{p}^{k+1/2}). Due to the symmetry of c_{ρ} we have that

\frac{1}{p − 1} log (\frac{∏_{k=1}^{p−1} f_{p}(ζ_{p}^{k+1/2})}{\sqrt{p}}) = 2 ∫_{0}^{∞} log ρ d(c_{ρ} − 1/2).

K. Soundararajan used the expression for c_{ρ} to show that this is^{3},

= \frac{2}{π} ∫_{0}^{∞} \frac{sin πx}{x} log x dx − ∫_{0}^{1} \frac{C(x) − 1}{x} dx − ∫_{1}^{∞} \frac{C(x)}{x} dx.

3We omit the lengthy details.

All of these integrals converge, though we do not know their exact values.

Remark 2. We can use the same technique as above to get a lower bound on κ_{1}. That is we wish to find out how often g(1/2) < 0 for g ∈ F_{J}. Now

\frac{1}{2}g (\frac{1}{2}) = 2 + ∑_{\begin{matrix}|j|≤J \\ j≠0,−1 \end{matrix}} \frac{δ_{j}}{2j + 1};

and so

Prob(g ∈ F_{J} : g(x_{0}) < 0) ≥ Prob(g ∈ F_{J} : g (\frac{1}{2}) < 0)

= \frac{1}{2} − \frac{1}{π} ∫_{0}^{∞} sin(2x) ∏_{\begin{matrix}|j|≤J \\ j≠0,−1 \end{matrix}} cos (\frac{2x}{2j + 1}) \frac{dx}{x}

Therefore

κ_{1} ≥ \frac{1}{2} − \frac{1}{π} ∫_{0}^{∞} sin 2x ∏_{\begin{matrix}n≥3 \\ n odd \end{matrix}} cos^{2} (\frac{2x}{n}) \frac{dx}{x} ≈ .065.

Remark 3. The expansion given here for f_{p}, and the general technique involved, is very similar to that used by Montgomery [3] in showing that,

1) |f_{p}(z)| ≪ \sqrt{p} log p for all |z| = 1.

2) If p is sufficiently large then there exists some value of z with |z| = 1 for which |f_{p}(z)| > \frac{2}{π} \sqrt{p} log log p.

Indeed to prove a result like (2) we note that we may select each δ_{j} equal to the sign of j for |j| < J = ε log p. By lemma 8 there are a lot of such K and we proceed as before with the expansion in (4.1), but now taking a little more care over the set of excluded K.

Remark 4. We can also use these techniques to investigate the distribution of values of F_{p}(z) as z varies over (p − 1)st roots of unity. We note that if K ∼ αp then ζ_{p−1}^{K} = ζ_{p}^{K+α}{1 + O(1/p)}. Therefore we can get an expression similar to (4.1) for

almost all F_{p}(ζ_{p−1}^{K}), but now with ∑_{|j|<J} (\frac{K−j}{p} ) \frac{1}{j+α} replacing the sum in (4.1), and multiplying the whole expression through by sin(απ). Thus the density of those K, for which F_{p}(ζ_{p−1}^{K}) ≤ ρ\sqrt{p}, is

\frac{1}{2} + \frac{1}{π} ∫_{α=0}^{1} ∫_{x=0}^{∞} sin (\frac{ρπx}{sin(απ)}) ∏_{m an integer} cos (\frac{x}{m + α}) \frac{dx}{x}dα.

We cannot see how to obtain a simpler expression.

14 BRIAN CONREY, ANDREW GRANVILLE AND BJORN POONEN

§5. Approximating g(x)

In this section we shall see how Theorem 1 is deduced from a slightly strengthened version of Theorem 2. By taking j = K − k in section 3, we have

g_{p,K}(x) = i (\frac{K}{p} ) ∑_{|j|<p/2} \frac{(\frac{K−j}{p} )}{ζ_{p}^{j+x} − 1}

Note that for J ≤ |j| < p/2,

|\frac{1}{ζ_{p}^{j+x} − 1} − \frac{1}{ζ_{p}^{j} − 1}| = |\frac{ζ_{p}^{x} − 1}{(ζ_{p}^{j+x} − 1)(ζ_{p}^{j} − 1)}| ≍ \frac{px}{j(j + x)} ≪ \frac{p}{j^{2}} ,

and, for |j| < J,

\frac{1}{ζ_{p}^{j+x} − 1} = \frac{p}{2iπ} \frac{1}{(j + x)} + O(1);

so that

(\frac{K}{p} ) g_{p,K}(x) = \frac{p}{2π} ∑_{|j|<J} \frac{(\frac{K−j}{p} )}{j + x} + i ∑_{J≤|j|<p/2} \frac{(\frac{K−j}{p} )}{ζ_{p}^{j} − 1} + O (J + \frac{p}{J} ) .

Now, by Lemma 2,

∑_{K=1}^{p} ( ∑_{J≤|j|<p/2} \frac{(\frac{K−j}{p} )}{ζ_{p}^{j} − 1})^{2} = ∑_{J≤|j_{1}|,|j_{2}|<p/2} \frac{1}{(ζ_{p}^{j_{1}} − 1) (ζ_{p}^{j_{2}} − 1)} ∑_{K=1}^{p} (\frac{K − j_{1}}{p} ) (\frac{K − j_{2}}{p} )

= p ∑_{J≤|j|<p/2} \frac{1}{(ζ_{p}^{j} − 1)^{2}} − ( ∑_{J≤|j|<p/2} \frac{1}{(ζ_{p}^{j} − 1)})^{2}

≪ p ∑_{J≤|j|<p/2} (\frac{p}{j})^{2} + ( ∑_{J≤|j|<p/2} \frac{p}{j})^{2}

≪ p^{3}/J + p^{2} log^{2} p

Therefore if J ≤ \sqrt{p}, and J → ∞ as p → ∞, then

| ∑_{J≤|j|<p/2} \frac{(\frac{K−j}{p} )}{ζ_{p}^{j} − 1}| ≤ \frac{p}{J^{1/3}}

for almost all^{4} K, 1 ≤ K ≤ p; and so

(5.0)  \frac{2π}{p} g_{p,K}(x) = (\frac{K}{p} ) ∑_{|j|<J} \frac{(\frac{K−j}{p} )}{j + x} + O (\frac{1}{J^{1/3}} )

4By ‘almost all’ we mean a fraction tending to 100%, as opposed to ‘all but finitely many’.

for almost all K, 1 ≤ K ≤ p.

In order to prove Theorem 1 we will need to strengthen Theorem 2 by adding:

(5.1) #\{g ∈ F_{J} : |g(x)| < \frac{1}{J^{1/4}} where g′(x) = 0\} = o(#\{g ∈ F_{J}\}) as J → ∞;

that is, not too many g have a very small number as their minimum.

To see that Theorem 1 now follows note that, by the results of section 3,

1) If (\frac{K+1}{p}) = (\frac{K}{p} ) there is exactly one zero of f_{p}(z) on the unit circle between

ζ_{p}^{K} and ζ_{p}^{K+1}.

2) If (\frac{K+1}{p}) = − (\frac{K}{p} ) then the minimum value of \frac{2π}{p} g_{p,K}(x) equals the min-

imum of (\frac{K}{p} ) ∑_{|j|<J} \frac{(\frac{K−j}{p})}{j+x} + O(1/J^{1/3}) for almost all such K. By (5.1)

this latter minimum is almost never O(1/J^{1/3}) in absolute value, since for almost all g ∈ F_{J} and K, we have |g(x)| > 1/J^{1/4} − O(1/J^{1/3}) > 1/2J^{1/4}. Thus, assuming the truth of this strengthened version of Theorem 2, we have proved that for ∼ κ_{0}p of these values of K, the minimum of g_{p,K}(x) is < 0. But then g must have two zeros in (0, 1). Therefore the total number of zeros of f_{p}(t), on the unit circle, in such intervals, is

∼ \frac{p}{2} · κ_{0} · 2 = κ_{0}p

and Theorem 1 follows.

§6. Polynomials with random coefficients

Suppose that g ∈ F_{J}. Then, for any x ∈ (0, 1), we have

(6.1)  \begin{aligned}\frac{1}{2}g′′(x) & = \frac{1}{x^{3}} + \frac{1}{(1 − x)^{3}} + ∑_{\begin{matrix}|j|≤J \\ j≠0,−1 \end{matrix}} \frac{δ_{j}}{(x + j)^{3}} \\ & ≥ \frac{1}{x^{3}} + \frac{1}{(1 − x)^{3}} − ∑_{\begin{matrix}|j|≤J \\ j≠0,−1 \end{matrix}} \frac{1}{(x + j)^{3}} > 2\frac{1}{(1/2)^{3}} − 2ζ(3) > 0. \end{aligned}

Since lim_{t→0^{+}} g′(t) = −∞ and lim_{t→1^{−}} g′(t) = ∞ we deduce that g′(x) has exactly one

zero in (0, 1), call it x_{0}. If 0 ≤ t < 1/π then

−g′(t) ≥ \frac{1}{t^{2}} − 2 (\frac{1}{(1/2)^{2}} + \frac{1}{(3/2)^{2}} + \frac{1}{(5/2)^{2}} + …) = \frac{1}{t^{2}} − π^{2} > 0;

and similarly if 1 − 1/π < t ≤ 1. Thus

(6.2)  x_{0} ∈ [1/π, 1 − 1/π].

Now suppose f ∈ F_{K}, with J < K and δ_{j} as before for |j| < J. Moreover let f′(x_{1}) = 0. Now

|f(x_{1}) − f(x_{0})| = ∑_{|j|<K} |\frac{1}{x_{1} + j} − \frac{1}{x_{0} + j} | ≪ ∑_{|j|<K} \frac{|x_{1} − x_{0}|}{j^{2}} ≪ |x_{1} − x_{0}|,

since x_{0}, x_{1} ∈ [1/π, 1 − 1/π]. On the other hand, by (6.1)

|f′(x_{0})| = |f′(x_{0}) − f′(x_{1})| = |∫_{x_{1}}^{x_{0}} f′′(t)dt| ≫ |x_{0} − x_{1}|.

Combining these last two equations we get

|f(x_{1}) − f(x_{0})| ≪ |f′(x_{0})| = |f′(x_{0}) − g′(x_{0})| = | ∑_{J≤|j|<K} \frac{δ_{j}}{(x_{0} + j)^{2}} | ≪ \frac{1}{J}

Moreover

|f(x_{0}) − g(x_{0})| = | ∑_{J≤|j|<K} \frac{δ_{j}}{x_{0} + j} |

If we look at the mean square of this we get

∏_{J≤|i|<K} (\frac{1}{2} ∑_{δ_{i}∈\{−1,1\}}) | ∑_{J≤|j|<K} \frac{δ_{j}}{x_{0} + j} |^{2}

= ∑_{J≤|j_{1}|,|j_{2}|<K} \frac{1}{(x_{0} + j_{1})(x_{0} + j_{2})} ∏_{J≤|i|<K} (\frac{1}{2} ∑_{δ_{i}∈\{−1,1\}}) δ_{j_{1}}δ_{j_{2}}

= ∑_{J≤|j|<K} \frac{1}{(x_{0} + j)^{2}} ≍ \frac{1}{J}

Thus if ψ_{J} → ∞ as J → ∞ then

| ∑_{J≤|j|<K} \frac{δ_{j}}{x_{0} + j} | < \frac{ψ_{J}}{J^{1/2}}

for almost all choices of the δ_{j}. Therefore

(6.3)  |f(x_{1}) − g(x_{0})| ≤ |f(x_{1}) − f(x_{0})| + |f(x_{0}) − g(x_{0})| < \frac{2ψ_{J}}{J^{1/2}}

for almost all such f.

Now suppose that we can prove (5.1). Combining this with (6.3) we see that for almost all f ∈ F_{K}, f(x_{1}) has the same sign as g(x_{0}) since

f(x_{1}) = g(x_{0}) + (f(x_{1}) − g(x_{0})) and |f(x_{1}) − g(x_{0})| < \frac{1}{J^{1/4}} ≤ |g(x_{0})|.

Thus Theorem 2 follows, since we have now proved that a limit exists. To complete the proofs of Theorems 1 and 2 we now give a

Proof of (5.1). Consider the subset S of F_{J} with all the δ_{j} fixed given values, except when j ∈ [I, I + I^{1/2}] where I = J^{1/4}. Let f ∈ S with δ_{j} = −1 for all j ∈ [I, I + I^{1/2}]. Suppose that f′(x_{1}) = 0 and let

γ = ∑_{\begin{matrix}|i|≤J \\ j∉[I,I+I^{1/2}] \end{matrix}} \frac{δ_{j}}{x_{1} + j}

where δ_{0} = 1, δ_{−1} = −1. Thus, for any g ∈ S with g′(x_{0}) = 0, we have

g(x_{0}) − γ = ∑_{j∈[I,I+I^{1/2}]} \frac{δ_{j}}{x_{0} + j} + O ( ∑_{\begin{matrix}|j|≤J \\ j∉[I,I+I^{1/2}] \end{matrix}} |\frac{1}{x_{0} + j} − \frac{1}{x_{1} + j} |)

= \frac{1}{I} ∑_{j∈[I,I+I^{1/2}]} δ_{j} + O ( ∑_{j∈[I,I+I^{1/2}]} |\frac{1}{I} − \frac{1}{x_{0} + j} | + |x_{1} − x_{0}|)

= \frac{1}{I} ∑_{j∈[I,I+I^{1/2}]} δ_{j} + O (\frac{1}{I})

since each |1/I − 1/(x_{0} + j)| ≪ 1/I^{3/2} and there are I^{1/2} such terms and, as above,

|x_{1} − x_{0}| ≪ |f′(x_{0}) − g′(x_{0})| ≪ ∑_{j∈[I,I+I^{1/2}]} \frac{1}{(x_{0} + j)^{2}} ≪ \frac{1}{I}.

Therefore if |g(x_{0})| < 1/I then

(6.4)  ∑_{j∈[I,I+I^{1/2}]} δ_{j} = −γI + O(1).

Now, the δ_{j} are independent binomial random variables, so the distribution of their sum tends towards the normal distribution. Therefore the maximum probability for (6.4) to occur happens when γ = 0; and so then (6.4) holds with probability O(1/I^{1/4}), for any γ, implying (5.1).

§7. Real zeros of trigonometric polynomials

Note that f(t), as in Theorem 4, is the derivative, with respect to t, of

g(t) := \frac{1}{2π} ∑_{n=1}^{N} \frac{1}{n}\{a_{n} sin(2πnt) − b_{n} cos(2πnt)\}

a function of the same form. Since

0 = g(1) − g(0) = ∫_{0}^{1} f(t)dt

thus f(t) must either equal 0 throughout [0, 1), or it must take both positive and negative values in [0, 1); say f(α) and f(β) have different signs with 0 < α < β < 1. By the intermediate value theorem we must thus have a zero of f in (α, β) and another in (β, 1 + α) since f(1 + α) = f(α). This second zero may already be in (β, 1) ⊂ (0, 1) or may be translated to get a zero in [0, α). Either way we have proved that n_{0} ≥ 2.

Write z = e^{2iπt} so that [0, 1) is mapped to the unit circle. Then

z^{N}f(t) = ∑_{n=1}^{N} \{\frac{a_{n}}{2} (z^{N+n} + z^{N−n}) + \frac{b_{n}}{2i} (z^{N+n} − z^{N−n})\} ,

a polynomial of degree ≤ 2N in z. It thus has no more than 2N zeros in the complex plane, and in particular on the unit circle. Thus n_{0} ≤ 2N and a similar argument gives n_{k} ≤ 2N for all k.

Now let 0 ≤ t_{1} ≤ t_{2} ≤ ⋯ ≤ t_{n_{0}} < 1 be the location of the zeros of f(t). By the mean value theorem f′(t) must have zeros in each interval [t_{j}, t_{j+1}] (including j = n_{0}, which here “means” the union of intervals [t_{n_{0}}, 1) ∪ [0, t_{1}] since f has period 1); and in fact in (t_{j}, t_{j+1}) unless t_{j} = t_{j+1}. In that case, suppose that t_{j−1} < t_{j} = t_{j+1} = ⋯ = t_{j+k} < t_{j+k+1}. Then f has a zero of order k + 1 at t_{j}, so that f′ has a zero of order k at t_{j}; which we can think of as one for each ‘interval’ [t_{j+i}, t_{j+i+1}) i = 0, 1, …, k − 1. Thus f′ has at least one zero in-between each consecutive pair of zeros of f, thought of as a function on the unit circle. Therefore n_{1} ≥ n_{0} and a similar argument gives n_{k+1} ≥ n_{k} for all k ≥ 0.

We shall now give the details of the proof when k is even. At the end we shall explain the (minor) modifications needed to make the proof work when k is odd. Now

(−1)^{k/2}f^{(k)}(t)/(2π)^{k} = ∑_{n=1}^{N} n^{k}(a_{n} cos(2πnt) + b_{n} sin(2πnt))

If t = t_{0} + \frac{2j−1}{4N} then, since sin (\frac{π}{2} (2j − 1)) = (−1)^{j}, we have

a_{N} cos(2πNt)+b_{N} sin(2πNt) = (−1)^{j}(a_{N} sin(2πNt_{0})−b_{N} cos(2πNt_{0})) = (−1)^{j+1}d_{N};

whereas, by Cauchy’s inequality, |a_{n} cos(2πnt) + b_{n} sin(2πnt)| ≤ d_{n}. Thus for t_{1} = t_{0} + \frac{2j−1}{4N} we have

(7.1)  (−1)^{k/2+j+1}f^{(k)}(t_{1})/(2π)^{k} ≥ d_{N}N^{k} − ∑_{n=1}^{N−1} d_{n}n^{k}.

Therefore, if (1.3) holds strictly (that is, if the inequality is strict), then f^{(k)}(t) changes sign between t_{0} + \frac{2j−1}{4N} and t_{0} + \frac{2j+1}{4N} for all j. Thus f^{(k)}(t) must have a zero in-between these two values, by the intermediate value theorem. This accounts for the maximum possible 2N zeros.

In order to locate these zeros we note that, by using the definition of t_{0} and Cauchy’s inequality again, we have

\frac{(−1)^{k/2}}{(2πN)^{k}} f^{(k)} (t_{0} + \frac{x}{4N} ) = sin (\frac{πx}{2}) d_{N} + 0 ( ∑_{n=1}^{N−1} d_{n}(n/N)^{k})

= sin (\frac{πx}{2}) d_{N} + 0 ( ∑_{n=1}^{N−1} d_{n}e^{−k/N}) .

If this equals 0, with 2j − 1 ≤ x ≤ 2j + 1, then x − 2j = O(e^{−k/N}).

Now suppose that the two sides in (1.3) are equal. We get equality in (7.1) if and only if a_{n} = (−1)^{j}d_{n} cos(2πnt_{1}) and b_{n} = (−1)^{j}d_{n} sin(2πnt_{1}) for every n, 1 ≤ n ≤ N − 1, in which case

(−1)^{j+1}f(t) = d_{N} cos(2πN(t − t_{1})) − ∑_{n=1}^{N−1} d_{n} cos(2πn(t − t_{1})).

Note that f^{(k+1)}(t_{1}) = 0 trivially, and so we get a double zero of f^{(k)}(t) at t = t_{1}. This thus accounts for the two zeros predicted between t_{0} + \frac{2j−1}{4N} and t_{0} + \frac{2j+1}{4N} by the argument above. Using the same argument at every such t_{1} we have accounted for at least 2N zeros on the unit circle (and thus exactly 2N).

On the other hand, assume now that d_{N}N^{k} − ∑_{n=1}^{N−1} d_{n}n^{k} < 0 and consider the example

f(t) = d_{N} cos(2πNt) − ∑_{n=1}^{N−1} d_{n} cos(2πnt),

so that (−1)^{k/2}f^{(k)}(0) < 0. Let z = e^{2iπt}, so that the zeros of (−1)^{k/2}f^{(k)}(t) in [0, 1) are in one-to-one correspondence with the zeros of g(z) = d_{N}(z^{N} + z^{−N}) − ∑_{n=1}^{N−1} d_{n}(n/N)^{k}(z^{n} + z^{−n}) on the unit circle. Evidently g(z) is real-valued if z is real; and we have just seen g(1) < 0. However g(z) → +∞ as z → ∞ and so g(z) must have a real zero on (1, ∞). Therefore f^{(k)}(t) must have had fewer than 2N zeros on [0, 1).

When k is odd we proceed in an analogous way to that above; however we determine now that f^{(k)}(t) changes sign at t = t_{0} + \frac{2j}{4N} for each pair of successive values of j, once the inequality in (1.3) is strict (rather than at t = t_{0} + \frac{2j−1}{4N}). Also the function we pick in the last part of the argument, when (1.3) does not hold, is as above, but with the cosines changed to sines.

Remark. If all of the d_{n} = 1 then (1.3) is satisfied for k > (N −3/2) log 2+O(1/N). As we just saw, once (1.3) is satisfied we have all of the roots on the unit circle, and the only way that they are not all simple zeros is if we have equality in (1.3). This corresponds precisely to solutions to

1^{k} + 2^{k} + 3^{k} + ⋯ + (N − 1)^{k} = N^{k}.

The open conjecture of Erdös and Moser states that the only solution to this equation is 1+2 = 3. This example leads, incidentally, via our theorem, to the fact that there six zeros of the first derivative of sin(6πt) − sin(4πt) − sin(2πt) on the unit circle with a double zero at t = 1 (the other zeros are simple).^{5}

Proof of Corollary 1. Let h_{p}(t) = F_{p}(e^{4iπt}), as defined in (1.2). Since h_{p}(t) = h_{p}(t + \frac{1}{2}) and h_{p}(t) = H_{p}(2t), we see H_{p}(t) has exactly half the number of zeros of h_{p}(t) on [0, 1). We may apply Theorem 4 to h_{p}(t). By (a) we know that there are ≤ 2(p − 1) zeros of h_{p}^{(k)}(t) in [0, 1). By the argument above we get this many zeros once k ≥ (p − 1) log(ρ) where

1 = \frac{1}{ρ^{2}} + \frac{1}{ρ^{4}} + ⋯ + \frac{1}{ρ^{p−3}} .

Clearly \frac{1}{ρ^{2}} > \frac{1}{2} so that log(ρ) < \frac{1}{2} log 2, and Corollary 1 follows.

§8 Fekete polynomials and Dirichlet L-functions

As noted in the introduction we have

Proposition 8.1. If f_{p}(t) has no zeros for t ∈ (0, 1) then L(s, χ) has no zeros with s > 0, where χ is the real non-principal character mod p. In particular L(s, χ) has no “Siegel zeros”.

Unfortunately though, f_{p}(t) often does have real zeros in (0, 1): The first examples are p = 43, 67, 163, …, primes for which ℚ(\sqrt{−p}) has surprisingly small class number (that is, precisely those p which are good ‘candidates’ for L(s, χ) to have a Siegel zero). So our Proposition 8.1 is not a particularly useful tool. Some such p were cleverly worked out by hand by Fekete [2] and Pólya [4]. Montgomery [3] showed that almost all Fekete polynomials have real zeros though, as we see from the table below, this only starts being obvious once p is much larger than 1000:

5Thus our result leads to a re-formulation of the Erdös-Moser problem as a question in elementary analysis, albeit somewhat convoluted.

We now give a table of real zeros of f_{p}(t), for each p < 1000. Notice that

h = h (\sqrt{(−1)^{\frac{p−1}{2}} p}) is small whenever there are such zeros.

p  h  Real zeros of f_{p}(t) to 3 decimal places
43  1  .780, .725
67  1  .908, .673
163  1  .975, .671
173  1*  .912, .679
293  1*  .951, .672
331  3  .965, .940
379  3  .976, .863
463  7  .967, .885
487  7  .971, .878
499  3  .986, .832
547  3  .987, .951, .807, .717
643  3  .991, .825
677  1*  .978, .679
683  5  .985, .869
773  1*  .979, .696
797  1*  .793, .722, .946, .977
823  9  .983, .899
853  1*  .942, .890
883  3  .994, .681
907  3  .994, .680
941  1*  .967, .831
947  5  .992, .851
967  11  .976, .955

The class numbers for primes ≡ 1 (mod 4) are marked with an asterisk. These are expected to be small in general. Note that by Descartes’ Rule of Sign, and using the Corollary to Lemma 2 and Lemma 7, it is easy to show that the number of zeros of f_{p}(t) in (0, 1) must be even.

§9 Further explorations

We now re-define

H_{p}(t) = ∏_{a=1}^{p−1} (t − ζ_{p}^{a})^{( \frac{a}{p})} .

Evidently

(9.1)  \frac{tH′_{p}(t)}{H_{p}(t)} = ∑_{a=1}^{p−1} \frac{t (\frac{a}{p})}{t − ζ_{p}^{a}} = ∑_{a=1}^{p−1} (\frac{a}{p}) (1 + \frac{ζ_{p}^{a}}{t − ζ_{p}^{a}} ) = \frac{αf_{p}(t)}{t^{p} − 1}

by (3.1). Substituting into (0.1) gives

−αΓ(s)L(s, χ) = ∫_{0}^{1}(− log t)^{s−1} \frac{H′_{p}(t)}{H_{p}(t)}dt

= [(− log t)^{s−1} log H_{p}(t)]_{0}^{1} + (s − 1) ∫_{0}^{1} \frac{(− log t)^{s−2}}{t} log H_{p}(t)dt.

Taking s = 1 gives

−αΓ(1)L(1, χ) = log H_{p}(1) − log H_{p}(0).

But H_{p}(0) = 1, Γ(1) = 1 and, if p ≡ 1 mod 4 then log H_{p}(1) = −2h log ϵ where h and ϵ > 1 are the class number and fundamental unit of ℚ(\sqrt{p}). So we recover Dirichlet’s class number formula.

Note also that, by the above,

log H_{p}(T) = ∫_{0}^{T} \frac{αf_{p}(t)}{t(t^{p} − 1)}dt.

Let

\frac{1}{2} (α(t) + β(t)\sqrt{(\frac{−1}{p}) p}) = ∏_{\begin{matrix}a=1 \\ (\frac{a}{p})=1 \end{matrix}}^{p−1} (t − ζ_{p}^{a})

where α, β ∈ ℤ[t] by elementary Galois theory (though this appears in Gauss’s work on cyclotomy). Thus

H_{p}(t) = \frac{α + β\sqrt{(−\frac{1}{p})p}}{α − β\sqrt{(−\frac{1}{p})p}}

where α^{2} − (\frac{−1}{p}) pβ^{2} = 4 (\frac{t^{p}−1}{t−1}). Moreover, for γ = β\sqrt{(\frac{−1}{p}) p}

\frac{tH′_{p}(t)}{H_{p}(t)} = t (\frac{(α′ + γ′)}{α + γ} − \frac{(α′ − γ′)}{α − γ}) = \frac{t(α(t)β′(t) − β(t)α′(t))\sqrt{(\frac{−1}{p}) p}}{4(t^{p} − 1)/(t − 1)}

which by (9.1) gives

(9.2)  f_{p}(t) = \frac{1}{4}t(t − 1)(α(t)β′(t) − β(t)α′(t)).

Now

2 (αα′ − (\frac{−1}{p}) pββ′) = 4 (\frac{t^{p} − 1}{t − 1})′ = 4 (\frac{(p − 1)t^{p} − pt^{p−1} + 1}{(t − 1)^{2}}) .

Combining this with (9.2) we have

(α^{′^{2}} − (\frac{−1}{p}) pβ^{′^{2}}) (α^{2} − (\frac{−1}{p}) pβ^{2}) =

= (αα′ − (\frac{−1}{p}) pββ′)^{2} − (\frac{−1}{p}) p (αβ′ − βα′)^{2}

= 4 (\frac{(p − 1)t^{p} − pt^{p−1} + 1}{(t − 1)^{2}})^{2} − 16 (\frac{−1}{p}) p (\frac{f_{p}(t)}{t(t − 1)})^{2} .

Thus

α′(t)^{2} − (\frac{−1}{p}) pβ′(t)^{2} = \{\frac{((p − 1)t^{p} − pt^{p−1} + 1)^{2} − 4 (\frac{−1}{p}) p (\frac{(t−1)}{t}f_{p}(t))^{2}}{(t^{p} − 1)(t − 1)^{3}} \}

Proposition 9.1. (t − 1)^{\frac{p−1}{2}} is the highest power of (t − 1) that divides f_{p}(t) (mod p)

Proof. f_{p}(t) = ∑_{a=0}^{p−1} (\frac{a}{p}) t^{a} ≡ ∑_{a=1}^{p−1} a^{\frac{p−1}{2}} t^{a} (mod p). Thus

f_{p}^{(k)}(t) = ∑_{a=1}^{p−1} a^{\frac{p−1}{2}} · a(a − 1) ⋯ (a − (k − 1)) (mod p). Now since ∑_{a=1}^{p−1} a^{j} ≡ 0 (mod p) for all j not divisible by p − 1 (in which case it is ≡ −1 (mod p)), thus if k < \frac{3(p−1)}{2} then

f_{p}^{(k)}(1) ≡ (−1) × the coefficient of x^{\frac{p−1}{2}} in x(x − 1) ⋯ (x − (k − 1)) (mod p),

(which is a Stirling number). In particular, if k < \frac{p−1}{2} then f_{p}^{(k)}(1) ≡ 0 (mod p), and the result follows.

References

1. R.C. Baker and H.L. Montgomery, Oscillations of Quadratic L-functions, Analytic Number Theory (ed. B.C. Berndt et.al.), Birkhäuser, Boston, 1990, p. 23–40.

2. M. Fekete, Palermo Rend 34 (1912), 89.

3. H.L. Montgomery, An exponential sum formed with the Legendre symbol, Acta Arithmetica 37 (1980), 375–380.

4. G. Pólya, Verschiedene Bemerkung zur Zahlentheorie, Jber. deutsch Math. Verein 28 (1919), 31–40.

5. M. Sambandham and V. Thangaraj, On the average number of real zeros of a random trigonometric polynomial, J. Indian Math. Soc 47 (1983), 139–150.