ON THE GAPS BETWEEN ZEROS OF TRIGONOMETRIC POLYNOMIALS

GADY KOZMA AND FERENC ORAVECZ

Abstract. We show that for every finite set 0 ∉ S ⊂ ℤ^{d} with the property −S = S, every real trigonometric polynomial f on the d dimensional torus 𝕋^{d} = ℝ^{d}/ℤ^{d} with spectrum in S has a zero in every closed ball of diameter D (S), where

D (S) = ∑_{λ∈S} \frac{1}{4||λ||_{2}} ,

and investigate tightness in some special cases.

1. Introduction and presentation of the main results

We are interested in the following question: for real trigonometric polynomials with a given spectrum, what is the maximal possible distance between two consecutive real zeros? Of course, if we can use enough frequencies for building our trigonometric polynomial, the size of the largest gap can be as close to 2π (or to 1, if one uses the transformation used throughout this paper) as we want. The question gets more interesting when the number of frequencies is relatively small.

The first theorem is a very general result, partially answering the above question. We state it for multivariate trigonometric polynomials on the d-dimensional torus 𝕋^{d} = ℝ^{d}/ℤ^{d}.

Theorem 1. Let 0 ∉ S ⊂ ℤ^{d} be a finite set s.t. −S = S. Let

f(x) = ∑_{λ∈S} c(λ) exp 2πi⟨x, λ⟩

be a real value trigonometric polynomial on 𝕋^{d}. Then f has a zero in any closed ball of diameter D(S) where

D(S) := ∑_{λ∈S} \frac{1}{4||λ||_{2}} ,

||λ||_{2} = \sqrt{⟨λ, λ⟩} = \sqrt{∑_{j=1}^{d} λ_{j}^{2}} .

Note that the requirement −S = S is necessary because we are interested in real trigonometric polynomials.

How sharp is this theorem? To answer that we have to analyze specific cases. From now on we concentrate on the one dimensional situation. For a finite set 0 ∉ S ⊂ ℤ define

Key words and phrases. trigonometric polynomials, zeros, roots.

Supported by EEC Research Training Network “Classical Analysis, Operator Theory, Geometry of Banach spaces, their interplay and their applications”, contract HPRN-CT-00116-2000.

M (S) := sup_{spec f⊂S} sup_{\begin{matrix}I⊂[0,1] \\ f|_{I}≠0 \end{matrix}} |I| ,

where spec f is the spectrum of f i.e. the support of the the Fourier transform f̂. The second supremum is over all intervals I such that f is never zero on I. Here and also later on |I| stands for the length of I. With this notation theorem 1 is shortened to the formula

M(S) ≤ D(S) .

The easiest case to investigate is when the spectrum is a (discrete) interval, or rather, two intervals situated symmetrically around 0. It turns out that in this case it is possible to get an explicit formula for the supremum (maximum does not exist) of the gap size:

Theorem 2. For S = [−N − K, −N] ∪ [N, N + K] ⊂ ℤ with N, K ∈ ℕ,

M(S) = \frac{K + 1}{2N + K} .

As the proof will show, we can also demonstrate an explicit formula for the trigonometric polynomial corresponding to the supremum (being a polynomial with “touching zeros” — e.g. non-negative on an interval of length (K + 1) / (2N + K)). We see that the general result applied for this specific case is sharp only asymptotically when K ≪ N. This leaves many questions. As examples, we formulate some of them:

Question 1. Theorem 2 can be generalized to linear progressions with stepping b smaller than twice the starting element, i.e. when S = ± {N + nb : n ∈ 0, 1, 2, … K} for some K, b ∈ ℕ, b < 2N (see Theorem 3 on page 4). What happens when b ≥ 2N? Can an explicit formula for M (S) be found in this case too?

Question 2. What is the maximum when the spectrum points are perfect squares, i.e. S = {±n^{2}}_{n=N}^{N+K} ?

Theorem 1 states that in this case the maximum tends to zero as N → ∞ even if K → ∞, a result which by itself is intriguing. However, is the asymptotic truly O(1/N) or is it even lower?

Question 3. What can we say when S is a random set? In this case we should handle random trigonometric polynomials where instead of the coefficients, the frequencies are chosen randomly.

Question 4. What about nets? A net of order n is a set with 2^{n+1} elements, defined by parameters {a_{0}, …, a_{n}} as follows: S := ± {a_{0} + ∑_{i=1}^{n} {0, a_{i}}}. In many questions nets behave like generalized arithmetic sequences. Is it true in our case as well?

We should remark that the specific case of k = 1 in theorem 2, together with the extremal polynomial, has been known for a while. The question was asked in [T65] and answered in [B84], which actually showed that this polynomial maximizes the measure of the positive part. The same polynomial reappears attributed to Arnold in [T97] and again in [GS00] (which also handles the question of positive coefficients). For our needs, though, the case k = 1 is not enough to make a meaningful comparison between M and D since we are even more interested in the case when they are both small, and the proofs in these papers do not seem to generalize nicely. See also [Y96] for inexact multidimensional results. Finally, [BH84, MDS99] deal with the related question of completely positive polynomials with some bounds on the zeroth coefficient.

2. Proof of Theorem 1 and Theorem 2

Proof of theorem 1. We will use induction on the cardinality of S. Due to the symmetry of S, we have #S = 2k, k = 0, 1, 2, … The case k = 0 is trivial as then f ≡ 0.

In general, given k > 0, assume we have proven the statement for all sets S with cardinality smaller than 2k. Take a set S with cardinality 2k and a trigonometric polynomial f (x) = ∑_{λ∈S} c (λ) exp 2πi ⟨x, λ⟩. Arguing by contradiction, assume that f does not have a zero, say is strictly positive, on a d-dimensional ball of radius R centered at y = (y_{1}, …, y_{d}), which we denote as usual by B(y, R). Pick a frequency ν = (ν_{1}, …, ν_{d}) ∈ S, and translate f by μ := \frac{ν}{2||ν||_{2}^{2}} . Since f is strictly positive on the ball B (y, R), the translate is strictly positive on the translated ball B(y − μ, R). Adding the translate to f (x) we get a new function

f̃(x) := f (x) + f (x + μ)

which is strictly positive on the closed ball

B (y − \frac{1}{2}μ, R − \frac{1}{2}||μ||_{2}) ⊆ B (y, R) ∩ B (y − μ, R)  (1)

whose diameter is 2R − \frac{1}{2||ν||_{2}} .

The Fourier expansion of the translated function is

f (x + μ) = ∑_{λ∈S} c (λ) exp 2πi ⟨x + μ, λ⟩
= ∑_{λ∈S} c(λ) exp 2πi⟨μ, λ⟩ exp 2πi⟨x, λ⟩

and thus

f̃(x) = ∑_{λ∈S} c(λ)(1 + exp 2πi⟨μ, λ⟩) exp 2πi ⟨x, λ⟩ .

Since for λ = ±ν we get exp 2πi⟨μ, λ⟩ = e^{±πi} = −1, the spectrum Sf̃:= spec(f̃) of f̃ is contained in S but definitely does not contain ±ν. Thus D(S) − \frac{1}{2||ν||_{2}} ≥ D(Sf̃), and so we find that we have a new set Sf̃ of cardinality smaller than 2k and a trigonometric polynomial f̃ with spectrum Sf̃ which is strictly positive on the closed ball B(y − μ, R(Sf̃)) of radius R(Sf̃) = \frac{1}{2}D(Sf̃) centered at y − μ. This contradicts our inductive hypothesis.

Remark. A similar proof can be applied to shapes different from balls. For example, for cubes we get the following version of theorem 1: If spec f = S then f has a zero in every closed cube of side length L(S) where

L(S) := ∑_{λ∈S} \frac{||λ||_{∞}}{4||λ||_{2}^{2}} .

The only proof element that needs modification is (1), as for cubes we have (denoting by C(y, L) the cube of side length L based at y),

C(y, L − ||μ||_{∞}) ⊂ C(y, L) ∩ C(y − μ, L)

and ||μ||_{∞} = ||ν||_{∞}/||ν||_{2}^{2}.

Proof of Theorem 2. Theorem 2 is a specific case of the following

Theorem 3. For S = {−N − Kb, …, −N − b, −N} ∪ {N, N + b, …, N + Kb} with N, K, b ∈ ℕ and b < 2N we have

M(S) = \frac{K + 1}{bK + 2N} .

Proof. First we show

M (S) ≤ \frac{K + 1}{bK + 2N}  (2)

by proving that for every trigonometric polynomial f (t) = ∑_{λ∈S} c (λ) e^{2πiλt}, if f > 0 on an interval I then |I| ≤ \frac{K+1}{bK+2N} . We may assume w.l.o.g. that I = [0, a]. One can write f (x) = Re F (t) with F (t) := e^{2πiNt}Q (e^{2πit}) , where Q is a polynomial of degree Kb, that is

Q (z) = c ∏_{j=1}^{Kb} (z − ξ_{j}) .  (3)

The condition f > 0 on I is equivalent to arg F ∈ (−π/2, π/2) on I. Since e^{2πiNt} does a rotation of 2πNa in the positive direction as t goes from 0 to a, f > 0 on I requires that Q (e^{2πit}) does a rotation of at least 2πNa − π in the negative direction on I. In other words, if ãrgQ is any continuous version of arg on the arc {e^{2πit} : t ∈ I} (ãrg exists because f|_{I} > 0 gives Q ≠ 0 on the arc, so for example take ãrg Q (e^{2πit}) := Im ∫_{0}^{t} \frac{Q′}{Q}) then a necessary condition is

ind Q := ãrg Q (e^{2πia}) − ãrg Q (1) ≤ π − 2πNa .  (4)

Clearly the index ind Q of Q does not depend on the choice of ãrg (all versions of ãrg differ by a constant 2πk). As we want an upper bound for a = |I|, we want to maximize − ind Q. Clearly

ind Q = ∑_{j=1}^{Kb} ind (z − ξ_{j}) .

Now it is obvious that if ξ is inside the unit disc, then ind (z − ξ) is positive (draw a picture!) — this is not what we want. If ξ is outside the disc, then ind (z − ξ) is harmonic (as a function of ξ) and therefore has no maxima in any open subset outside the disc, thus we need to investigate only the limiting behavior as ξ tends to infinity and to the unit circle.^{1} Both can be calculated explicitly. When ξ → ∞ clearly ind (z − ξ) → 0. On the other hand, a simple calculation shows that

lim_{ξ→e^{2πis}} ind (z − ξ) = \begin{cases}πa − π & if s ∈ (0, a) \\ πa & if s ∉ [0, a] \end{cases}  (5)

1The fact that the supremum occurs when ξ converges to the unit circle from outside can also be deduced by elementary geometric arguments.

where the limit is taken from the outside of the unit circle. A geometric note may be due here: the limit lim_{ξ→e^{2πis}} (ãrg (e^{2πia} − ξ) − ãrg (1 − ξ)), viewed as a function of a, for s ∈ I is not continuous — it has a −π jump discontinuity at s, this gives the −π factor in (5).

A similar calculation shows that if ξ → 1 or ξ → e^{2πia} then the limit of ind (z − ξ) depends on the angle of approach, but in any case is bounded from below by πa−π. These three cases (ξ inside the disc, outside, and approaching the boundary) totally give

ind (z − ξ) ≥ π (a − 1) ∀ξ ∈ ℂ \ {e^{2πis} : s ∈ I} .  (6)

The case b = 1 is now immediate from (4) and (6). The case b > 1 is not much harder. Let τ = e^{2πi/b}. If ξ is a zero of Q then so are τξ, τ^{2}ξ, …, τ^{b−1}ξ so we can rearrange ξ_{j} such that ξ_{j+K} = τξ_{j}. In particular this gives the following representation using the first K zeros:

Q (z) = c ∏_{j=1}^{K} (z^{b} − ξ_{j}^{b}) .

Now the analog of (6) is

ind (z^{b} − ξ^{b}) ≥ π (ba − 1)  (7)

which holds for a < 1/b — we will justify this assumption later. The reasoning is similar: if ξ is inside the unit disc so are all the conjugates and the index is positive. For ξ outside the disc the index is harmonic in ξ so we need to investigate only ξ converging to the circle, but as for a < 1/b only one of the conjugates of ξ may converge to the arc {e^{2πis} : s ∈ (0, a)}. Summing b copies of (5) gives (7). Summing the K copies of (7) gives (with (4))

Kπ (ba − 1) ≤ ind Q ≤ π − 2πNa  (8)

which, again, holds for a < 1/b. As according to our conditions 2N/b > 1, for a = \frac{1}{b} − ϵ with ϵ > 0 sufficiently small (8) cannot hold, thus no such f can have an interval of length \frac{1}{b} − ϵ with no zeros. This justifies our a priori assumption a < 1/b, and we can use (8) to get the largest a allowed, proving (2).

We turn to the proof of

M (S) ≥ \frac{K + 1}{bK + 2N} .  (9)

The first step will be to construct an extremal function f which will only satisfy f ≥ 0 (i.e. will have zeros in the interval I = [0, a] where a = \frac{K+1}{bK+2N}). The analysis above suggests that we try f = Re F, F (t) = e^{2πiNt}Q (e^{2πit}) , for Q satisfying (3), with K zeros on the arc {e^{2πis} : s ∈ I} (the other zeros are the conjugates, which are of course also an the unit circle but not on the arc). It turns out that it is enough to space the zeros evenly, namely define

Q (z) := c ∏_{j=1}^{K} (z^{b} − τ^{jb})

where τ := e^{2πiη} with η := \frac{1}{bK+2N}, and c is some constant such that F (0) = Q (0) = −1. Now arg F can be calculated explicitly, where this time arg is in the usual sense, i.e. a discontinuous function between −π and π. Elementary geometry shows that

arg (e^{iφ} − e^{iν}) ≡ \begin{cases}\frac{ν+φ−π}{2} & if ν > φ \\ \frac{ν+φ+π}{2} & if ν < φ \end{cases} mod 2π

Summing this for all the roots we get that on each segment (kη, (k + 1) η) arg F is a linear function with derivative π (bK + 2N). Thus, on (0, η) it is increasing from −π/2 to π/2, at η it has a jump of −π, then on (η, 2η) it is again linear with the same slope, so it again rises from −π/2 to π/2, then has another jump of −π and so on. This argument works till (K + 1) η = a. Thus we get arg F ∈ [−π/2, π/2] on I and therefore f ≥ 0 on I having its only zeros at the points {0, η, 2η, …, Kη, a}.

Taking f (t) + f (t + ϵ) (whose Fourier transform is also supported on S) for ϵ small enough one gets a strictly positive function on any interval interior to I. This proves (9) and the theorem.

3. Corollaries and remarks

Let’s compare the results of theorems 1 and 2. A simple calculation shows that

D(S) = ∑_{n=N}^{N+K} \frac{1}{2n} = \frac{K + 1}{2N + K} + O (\frac{K^{2}}{N^{3}} ) .

It is interesting to note that the true value, i.e. M(S) = \frac{K+1}{2N+K} is the unique approximation of D(S) by a rational function of order 1 with this error term.

The following fact is a corollary of Theorem 2:

Corollary. For every interval I ⊂ [0, 1] with |I| < 1 there exists some constant α such that for all N ∈ ℕ there exists a real trigonometric polynomial f with

spec f ⊂ [−αN, −N] ∪ [N, αN]

such that f > 0 on I.

Proof. Let δ := 1 − |I|. Let α := 1 + 4/δ. Apply Theorem 2 for N, K := (α − 1)N and ϵ := δ/2. Then as in this case

(\frac{K + 1}{2N + K} − ϵ) − |I| = \frac{1 + Nδ}{2N + K} > 0,

there exists a real trigonometric polynomial f_{1} with spec (f_{1}) ⊂ [−αN, −N] ∪ [N, αN] s.t. f_{1} > 0 on an interval of length bigger than |I| (namely, on the interval [0, \frac{K+1}{2N+K} − ϵ]). If I ⊂ [0, \frac{K+1}{2N+K} − ϵ] we are done. Otherwise, we need another shift and f (t) := f_{1} (t − a) will do, where I = (a, b) .

Here is a simple but slightly disappointing corollary to theorem 3:

Corollary. M and D may be significantly different even when they are both small.

Proof. Take b = K and N = K^{2}. Then easily

M(S) = \frac{1}{3}K^{−1} + O(K^{−2}) D(S) = (log 2)K^{−1} + O(K^{−3/2}).

References

[BH84] Brown, G. and Hewitt, E., A class of positive trigonometric sums, Math. Ann. 268/1, 1984, 91–122.

[B84] Babenko, A. G., An exremal problem for polynomials. Mat. Zametski 35/3, 1984, 349– 356. English translation: Math. Notes 35/3–4, 1984, 181–186.

[GS00] Gilbert, A. D. and Smyth, C. J., Zero-mean cosine polynomials which are non-negative for as long as possible, J. London Math. Soc. 2, 62/2, 2000, 489–504.

[MDS99] MacDonald, J. N. and Siefker, A., Nonnegative trigonometric sums, J. Math. Anal. Appl. 238/2, 1999, 580–586.

[T97] Tabachnikov, S. L., On functions with zero mean with respect to a finite group, Funktsional. Anal. i Prilozhen, 31/1, 1997, 93–94. English translation: Funct. Anal. Appl. 31/1, 1997, 73–74.

[T65] Taikov, L. V., A series of extremal problems for trigonometric polynomials, Usp. Mat. Nauk, 20/3, 1965, 205–211.

[Y96] Yudin, V. A., Two extremal problems for trigonometric polynomials, Mat. Sb. 187/11,

1996, 145–160. English translation: Sb. Math. 187/11, 1996, 1721–1736. Current address: Weizmann Institute of Science

E-mail address: gadykozma@hotmail.com

Current address: Tel Aviv University, School of Mathematics, Tel Aviv, Israel

E-mail address: oravecz@post.tau.ac.il, oravecz@renyi.hu
URL: http://www.renyi.hu/oravecz