Do Flat Skew-Reciprocal Littlewood Polynomials Exist?

Abstract

Polynomials with coefficients in $\{-1,1\}$ are called Littlewood polynomials. Using special properties of the Rudin–Shapiro polynomials and classical results in approximation theory such as Jackson’s Theorem, de la Vallée Poussin sums, Bernstein’s inequality, Riesz’s Lemma, and divided differences, we give a significantly simplified proof of a recent breakthrough result by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba stating that there exist absolute constants $\eta _2> \eta _1 > 0$ and a sequence $(P_n)$ of Littlewood polynomials $P_n$ of degree n such that

$$\begin{aligned} \eta _1 \sqrt{n} \le |P_n(z)| \le \eta _2 \sqrt{n} , \qquad z \in {{\mathbb {C}}}, |z| = 1 , \end{aligned}$$

confirming a conjecture of Littlewood from 1966. Moreover, the existence of a sequence $(P_n)$ of Littlewood polynomials $P_n$ is shown in a way that in addition to the above flatness properties a certain symmetry is satisfied by the coefficients of $P_n$ making the Littlewood polynomials $P_n$ close to skew-reciprocal.

1 The Theorem

Polynomials with coefficients in $\{-1,1\}$ are called Littlewood polynomials.

Theorem 1.1

There exist absolute constants $\eta _2> \eta _1 > 0$ and a sequence $(P_n)$ of Littlewood polynomials $P_n$ of degree n such that

$$\begin{aligned} \eta _1 \sqrt{n} \le |P_n(z)| \le \eta _2 \sqrt{n} , \qquad z \in {{\mathbb {C}}}, |z| = 1 . \end{aligned}$$

(1.1)

Note that Beck [4] showed the existence of flat unimodular polynomials $P_n$ of degree n satisfying (1.1) with coefficients in the set of kth roots of unity and gave the value $k = 400$, but correcting a minor error in Beck’s paper Belshaw [1] showed that the value of k in [4] should have been 851. Repeating Spencer’s calculation Belshaw improved the value 851 to 492 in Beck’s result, and an improvement of Spencer’s method, due to Kai-Uwe Schmidt, allowed him to lower the value of k to 345. The recent breakthrough result by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [2] formulated in Theorem 1.1 confirms a conjecture of Littlewood from 1966. Using special properties of the Rudin–Shapiro polynomials and classical results in approximation theory such as Jackson’s Theorem, de la Vallée Poussin sums, Bernstein’s inequality, Riesz’s Lemma, and divided differences, in this paper we give a significantly simplified proof of this beautiful and deep theorem. Moreover, the existence of a sequence $(P_n)$ of Littlewood polynomials $P_n$ is shown so that in addition to (1.1) a certain symmetry is satisfied by the coefficients of $P_n$.

Theorem 1.2

There exist absolute constants $0< \eta _1 < \eta _2$, $\eta > 0$, and a sequence $(P_{2n})$ of Littlewood polynomials $P_{2n}$ of the form

$$\begin{aligned} P_{2n}(z) = \sum _{j=0}^{2n}{a_{j,n}z^j} , \qquad a_{j,n} \in \{-1,1\} , j=0,1,\ldots ,2n, n=1,2,\ldots , \end{aligned}$$

such that in addition to (1.1) with n replaced by 4n the coefficients of $P_{2n}$ satisfy

$$\begin{aligned} a_{j,n} = -a_{2n-j,n} , \qquad 0 \le j < n-m_n , \end{aligned}$$

and

$$\begin{aligned} a_{j,n} = (-1)^{n-j}a_{2n-j,n} , \qquad n-m_n \le j \le n , \end{aligned}$$

with some integers $0 \le \eta n \le m_n \le n$.

The theorem above may be viewed as a result in an effort to answer the following question.

Problem 1.3

Are there absolute constants $0< \eta _1 < \eta _2$ and a sequence $(P_{4n})$ of skew-reciprocal Littlewood polynomials $P_{4n}$ of the form

$$\begin{aligned} P_{4n}(z) = \sum _{j=0}^{4n}{a_{j,n}z^j} , \qquad a_{j,n} \in \{-1,1\} , j=0,1,\ldots ,4n, n=1,2,\ldots , \end{aligned}$$

such that in addition to (1.1) with n replaced by 4n the coefficients of $P_{4n}$ satisfy

$$\begin{aligned} a_{j,n} = (-1)^{-j}a_{4n-j,n} , \qquad j=0,1,\ldots ,4n\,? \end{aligned}$$

This problem remains open. We remark that it is easy to see that every self-reciprocal Littlewood polynomial of the form

$$\begin{aligned} P_{n}(z) = \sum _{j=0}^{n}{a_{j,n}z^j} , \qquad a_{j,n} \in \{-1,1\} , j=0,1,\ldots ,n , \end{aligned}$$

satisfying

$$\begin{aligned} a_{j,n} = a_{n-j,n} , \qquad j=0,1,\ldots ,n , \end{aligned}$$

has at least one zero on the unit circle, see Theorem 2.8 in [8], or Corollary 6 in [16], for example. Hence, there are no absolute constant $\eta _1 > 0$ and a sequence $(P_n)$ of self-reciprocal Littlewood polynomials $P_n$ of degree n such that

$$\begin{aligned} \eta _1 \sqrt{n} \le |P_n(z)| , \qquad z \in {{\mathbb {C}}}, |z| = 1 , n=1,2,\ldots . \end{aligned}$$

2 Rudin–Shapiro Polynomials

Section 4 of [5] is devoted to the study of Rudin–Shapiro polynomials. A sequence of Littlewood polynomials that satisfy just the upper bound of Theorem 1.1 is given by the Rudin–Shapiro polynomials. The Rudin–Shapiro polynomials appear in Harold Shapiro’s 1951 thesis [17] at MIT and are sometimes called just Shapiro polynomials. They also arise independently in Golay’s paper [13]. The Rudin–Shapiro polynomials are remarkably simple to construct. They are defined recursively as follows:

$$\begin{aligned} \begin{aligned} P_0(z)&:=1 , \qquad Q_0(z) := 1 , \\P_{m+1}(z)&:= P_m(z) + z^{2^m}Q_m(z) , \\Q_{m+1}(z)&:= P_m(z) - z^{2^m}Q_m(z) , \\\end{aligned} \end{aligned}$$

for $m=0,1,2,\ldots .$ Note that both $P_m$ and $Q_m$ are polynomials of degree $M-1$ with $M := 2^m$ having each of their coefficients in $\{-1,1\}$. It is well known and easy to check by using the parallelogram law that

$$\begin{aligned} |P_{m+1}(e^{it})|^2 + |Q_{m+1}(e^{it})|^2 = 2(|P_m(e^{it})|^2 + |Q_m(e^{it})|^2) , \qquad t \in {{\mathbb {R}}} . \end{aligned}$$

Hence,

$$\begin{aligned} |P_m(e^{it})|^2 + |Q_m(e^{it})|^2 = 2^{m+1} = 2M , \qquad t \in {{\mathbb {R}}} . \end{aligned}$$

(2.1)

Observing that the first $2^m$ terms of $P_{m+1}$ are the same as the $2^m$ terms of $P_m$, we can define the polynomial $P_{<n}$ of degree $n-1$ so that its terms are the first n terms of all $P_m$ for all m for which $2^m \ge n$. The following bound, which is a straightforward consequence of (2.1), was proved by Shapiro [17].

Lemma 2.1

We have

$$\begin{aligned} |P_{<n}(e^{it})| \le 5\sqrt{n} , \qquad t \in {{\mathbb {R}}} . \end{aligned}$$

It is also well known that

$$\begin{aligned} P_m(1) = \Vert P_m(e^{it})\Vert := \max _{t \in {{\mathbb {R}}}}{|P_m(e^{it})}|= 2^{(m+1)/2} \end{aligned}$$

for every odd m and $P_m(1) = 2^{m/2}$ for every even m.

Our next lemma is stated as Lemma 3.5 in [9], where its proof may also be found. It plays a key role in [10,11,12] as well.

Lemma 2.2

If $P_m$ and $Q_m$ are the m-th Rudin–Shapiro polynomials of degree $M-1$ with $M := 2^m$, $\delta := \sin ^2(\pi /8)$, and

$$\begin{aligned} z_j := e^{it_j} , \quad t_j := \frac{2\pi j}{M} , \qquad j \in {{\mathbb {Z}}} , \end{aligned}$$

then

$$\begin{aligned} \max \{|P_m(z_j)|^2,|P_m(z_{j+1})|^2\} \ge \delta 2^{m+1} = 2\delta M . \end{aligned}$$

Lemma 2.3

Using the notation of Lemma 2.2, we have

$$\begin{aligned} |P_m(e^{it})|^2 \ge \delta M , \qquad t \in \left[ t_j - \frac{\delta }{2M}, t_j + \frac{\delta }{2M} \right] , \end{aligned}$$

for every $j \in {{\mathbb {Z}}}$ such that

$$\begin{aligned} |P_m(z_j)|^2 \ge \delta 2^{m+1} = 2\delta M . \end{aligned}$$

Proof

The proof is a simple combination of the mean value theorem and Bernstein’s inequality (Lemma 3.4) applied to the (real) trigonometric polynomial of degree $M-1$ defined by $S(t) := P_m(e^{it})P_m(e^{-it})$. Recall that (2.1) implies $0 \le S(t) = |P_m(e^{it})|^2 \le 2M$ for every $t \in {{\mathbb {R}}}$. $\square$

Let, as before, $M := 2^m$ with an odd m. We define

$$\begin{aligned} T(t):= & {} \text{ Re }((1 + e^{iMt} + e^{2iMt} + \cdots + e^{8iMt}) P_m(e^{it})) \nonumber \\ {}= & {} \text{ Re } \left( \frac{e^{9iMt}-1}{e^{iMt}-1} \, P_m(e^{it})\right) . \end{aligned}$$

(2.2)

Observe that T is a real trigonometric polynomial of degree $\mu -1 := 9M-1$. For every sufficiently large natural number n, there is an odd integer m such that

$$\begin{aligned} 2^{-75} \le \gamma := \frac{\mu }{n} = \frac{9 \cdot 2^m}{n} < 2^{-73} . \end{aligned}$$

(2.3)

Observe that

$$\begin{aligned} \Vert T\Vert:= & {} \max _{t \in {{\mathbb {R}}}}{|T(t)|} = |T(0)| = 9|P_m(1)| = 9 \cdot 2^{(m+1)/2} \nonumber \\ {}= & {} 9(2M)^{1/2} = 3 \sqrt{2\gamma n} . \end{aligned}$$

(2.4)

Lemma 2.4

In the notation of Lemmas 2.2 and 2.3, for every $j \in {{\mathbb {Z}}}$ satisfying

$$\begin{aligned} |P_m(z_j)|^2 \ge \delta 2^{m+1} = 2\delta M \end{aligned}$$

there are

$$\begin{aligned} a_j \in \left[ t_j - \frac{3\pi }{32M},t_j - \frac{\pi }{32M}\right] \qquad \text {and} \qquad b_j \in \left[ t_j + \frac{\pi }{32M}, t_j + \frac{3\pi }{32M} \right] \end{aligned}$$

such that

$$\begin{aligned}&|T(a_j)| \ge (0.005) \Vert T\Vert = (0.015)\sqrt{2\gamma n} \qquad \text {and} \\&|T(b_j)| \ge (0.005) \Vert T\Vert = (0.01)\sqrt{2\gamma n} . \end{aligned}$$

Proof

We prove the statement about the existence of $b_j$ as the proof of the statement about the existence of $a_j$ is essentially the same. Let

$$\begin{aligned} P_m(e^{it}) = R(t) e^{i\alpha (t)} , \qquad R(t) = |P_m(e^{it})| , \end{aligned}$$

where the function $\alpha$ could be chosen so that it is differentiable on any interval where $P_m(e^{it})$ does not vanish. Then

$$\begin{aligned} ie^{it}P_m^\prime (e^{it}) = R^\prime (t) e^{i\alpha (t)} + R(t) e^{i\alpha (t)}(i\alpha ^\prime (t)) , \end{aligned}$$

hence

$$\begin{aligned} \alpha ^\prime (t) = \text {Re} \left( \frac{e^{it}P_m^\prime (e^{it})}{P_m(e^{it})} \right) \end{aligned}$$

on any interval where $P_m(e^{it})$ does not vanish. Combining Bernstein’s inequality (Lemma 3.4), Lemma 2.3, and $\Vert P_m\Vert \le (2M)^{1/2}$, we obtain

$$\begin{aligned} |\alpha ^\prime (t)| \le \frac{M(2M)^{1/2}}{(\delta M)^{1/2}} = \left( \frac{2}{\delta } \right) ^{1/2} M \le (3.7)M , \qquad t \in \left[ t_j, t_j + \frac{\delta }{2M} \right] . \end{aligned}$$

(2.5)

Now let

$$\begin{aligned} \frac{e^{9iMt}-1}{e^{iMt}-1} = \left| \frac{e^{9iMt}-1}{e^{iMt}-1} \right| e^{4Mt} , \qquad t \in \left( t_j -\frac{2\pi }{9M}, \, t_j + \frac{2\pi }{9M} \right) . \end{aligned}$$

(2.6)

By writing

$$\begin{aligned} (1 + e^{iMt} + e^{2iMt} + \cdots + e^{8iMt}) P_m(e^{it}) = \left| \frac{e^{9iMt}-1}{e^{iMt}-1} P_m(e^{it}) \right| e^{i(\alpha (t) + 4Mt)} , \end{aligned}$$

we see by (2.5) and (2.6) that $\beta (t) := \alpha (t) + 4Mt$ satisfies

$$\begin{aligned} (0.3)M = 4M - (3.7)M \le 4M - |\alpha ^\prime (t)| \le |\beta ^\prime (t)| , \qquad t \in \left[ t_j,t_j + \frac{\delta }{M} \right] . \end{aligned}$$

(2.7)

It is also simple to see that

$$\begin{aligned} \left| \frac{e^{9iMt}-1}{e^{iMt}-1} \right|\ge & {} \, \left| \frac{e^{iM\pi }-1}{e^{iM\pi /9}-1} \right| \nonumber \\ {}= & {} \frac{2}{2\sin (\pi /18)} \ge \frac{18}{\pi } , \qquad t \in \left[ t_j - \frac{\pi }{9M},t_j + \frac{\pi }{9M} \right] . \end{aligned}$$

(2.8)

Observe that (2.7) and (2.8) imply that there are

$$\begin{aligned} b_j \in \left[ t_j + \frac{\pi }{32M},t_j + \frac{3\pi }{32M} \right] \end{aligned}$$

for which

$$\begin{aligned} \left| \frac{e^{9iMb_j}-1}{e^{iMb_j}-1} \right| \ge \frac{18}{\pi } \end{aligned}$$

(2.9)

and

$$\begin{aligned} \cos (\beta (b_j)) \ge \cos \left( \frac{\pi }{2} - \frac{(0.15)\pi }{16} \right) \ge 0.0294 . \end{aligned}$$

(2.10)

Combining (2.9), (2.10), Lemma 2.3, and (2.4), we obtain

$$\begin{aligned} \begin{aligned} |T(b_j)|&= \, \left| \text{ Re } \left( \frac{e^{9iMb_j}-1}{e^{iMb_j}-1} \, P_m(e^{ib_j})\right) \right| = \left| \frac{e^{9iMb_j}-1}{e^{iMb_j}-1} \right| \, \left| P_m(e^{ib_j}) \right| |\cos (\beta (b_j)| \\&\ge \, \frac{18}{\pi } (\delta M)^{1/2} (0.0294) \ge \frac{(0.5292) \sin (\pi /8)}{9\sqrt{2}\pi } 9(2M)^{1/2} \ge (0.005) 9(2M)^{1/2} \\&\ge \, (0.005)\Vert T\Vert . \end{aligned} \end{aligned}$$

$\square$

3 Tools from Approximation Theory

Let ${\mathcal {T}}_\nu$ denote the set of all real trigonometric polynomials of degree at most $\nu$. Let $\Vert T\Vert$ denote the maximum modulus of a trigonometric polynomial T on ${{\mathbb {R}}}$.

Definition 3.1

Let $n > 0$ be an integer divisible by 10. Let ${\mathcal {I}}$ be a collection of disjoint closed intervals (with nonempty interiors) in ${{\mathbb {R}}}/{2\pi {\mathbb {Z}}}$. We call the collection ${\mathcal {I}}$ suitable if

• (a) the endpoints of each interval in ${\mathcal {I}}$ are in $(10\pi /n){{\mathbb {Z}}}$;

• (b) ${\mathcal {I}}$ is invariant under the maps $\theta \rightarrow \pi \pm \theta$;

• (c) $|{\mathcal {I}}| = 4N$ for some $N \le \gamma n$.

We call a suitable collection ${\mathcal {I}}$ of disjoint closed intervals (with nonempty interiors) in ${{\mathbb {R}}}/(2\pi {{\mathbb {R}}})$ well-separated if

• (d) $|I| \le 3990\pi /n$ for each $I \in {\mathcal {I}}$;

• (e) $d(I,J) \ge 10\pi /n$ for each $I,J \in {\mathcal {I}}$ with $I \ne J$;

• (f) the sets $\bigcup _{I \in {\mathcal {I}}}{I}\,$ and $\,(\pi /2){{\mathbb {Z}}} + (-5\pi /n, 5\pi /n)$ are disjoint;

where in (e) d(I, J) denotes the distance between the intervals I and J.

We will denote the intervals in a suitable and well-separated collection ${\mathcal {I}}$ by

$$\begin{aligned} I_j, \qquad j=1,2,\ldots ,4N , \end{aligned}$$

where $I_1, I_2, \ldots , I_N \subset (0,\pi /2)$. Associated with an interval $[a,b] \subset [-\pi +5\pi /n,\pi -5\pi /n]$, we define

$$\begin{aligned} \Phi _{[a,b]}(t) := {\left\{ \begin{array}{ll} 1, \quad &{} \text {if } t \in [a,b] , \\ 0, \quad &{} \text {if } t \in [-\pi ,a-5\pi /n] \cup [b+5\pi /n,\pi ] , \\ (n/(5\pi ))(t-(a-5\pi /n)), \quad &{} \text {if } t \in [a-5\pi /n,a] , \\ (n/(5\pi ))((b+5\pi /n)-t), \quad &{} \text {if } t \in [b,b+5\pi /n] . \end{array}\right. } \end{aligned}$$

We call the coloring $\alpha : {\mathcal {I}} \rightarrow \{-1,1\}$ symmetric if $\alpha (I) = \alpha (\pi -I)$ and $\alpha (I) = -\alpha (\pi +I)$. Associated with a symmetric ${\mathcal {I}}: \rightarrow \{-1,1\}$, let

$$\begin{aligned} g_{\alpha } := \sum _{j=1}^{4N}{\alpha (I_j) \Phi _{I_j}} \qquad \text {and} \qquad G_{\alpha } := K\sqrt{n}\,g_{\alpha } . \end{aligned}$$

Let $S_o := \{1,3,\ldots ,2n-1\}$ be the set of odd numbers between 1 and $2n-1$. Let $C_{2\pi }$ denote the set of all continuous $2\pi$ periodic functions defined on ${{\mathbb {R}}}$. Associated with $f \in C_{2\pi }$, we define the nth partial sums

$$\begin{aligned} S_n(f,t) := a_0 + \sum _{k=1}^n{(a_k\cos (kt) + b_k \sin (kt))} \end{aligned}$$

of the Fourier series expansion of f, where

$$\begin{aligned} a_0= & {} a_0(f) := \frac{1}{2\pi } \, \int _{-\pi }^{\pi }{f(t) \, {\mathrm{d}}t} , \\ a_k= & {} a_k(f) := \frac{1}{\pi } \, \int _{-\pi }^{\pi }{f(t) \cos (kt)\, {\mathrm{d}}t} , \qquad k=1,2,\ldots , \end{aligned}$$

and

$$\begin{aligned} b_k = b_k(f) := \frac{1}{\pi } \, \int _{-\pi }^{\pi }{f(t) \sin (kt)\, {\mathrm{d}}t} , \qquad k=1,2,\ldots . \end{aligned}$$

Observe that if $\alpha : {\mathcal {I}} \rightarrow \{-1,1\}$ is symmetric, then

$$\begin{aligned} S_{2n}(G_\alpha ,t) = S_{2n-1}(G_\alpha ,t) = \sum _{k=1}^n{b_{2k-1}(G_\alpha ) \sin ((2k-1)t)} . \end{aligned}$$

Associated with $f \in C_{2\pi }$, we also define

$$\begin{aligned} E_n(f) := \min _{Q \in {\mathcal {T}}_n}{\Vert f-Q\Vert } \end{aligned}$$

and

$$\begin{aligned} \omega (f,\delta ) := \max _{t \in {{\mathbb {R}}}}{|f(t+\delta ) - f(t)|} . \end{aligned}$$

In the proof of Theorem 6.1, we will use D. Jackson’s theorem on best uniform approximation of continuous periodic functions with exact constant. The result below is due to Korneichuk [14].

Lemma 3.2

If $f \in C_{2\pi }$ then

$$\begin{aligned} E_n(f) \le \omega \left( f,\frac{\pi }{n+1} \right) . \end{aligned}$$

In the proof of Theorem 6.1, we will also use the following result of De La Vallée Poussin, the proof of which may be found on pages 273–274 in [7].

Lemma 3.3

Associated with $f \in C_{2\pi }$ let

$$\begin{aligned} V_n(f,t) := \frac{1}{n} \sum _{j=n}^{2n-1}{S_j(f,t)} . \end{aligned}$$

We have

$$\begin{aligned} \max _{t \in {{\mathbb {R}}}}{|V_n(f,t) - f(t)|} \le 4E_n(f) . \end{aligned}$$

The following inequality is known as Bernstein’s inequality and plays an important role in the proof of Lemma 3.5.

Lemma 3.4

We have

$$\begin{aligned} \Vert U^{(k)}\Vert \le \nu ^k \Vert U\Vert , \qquad U \in {\mathcal {T}}_{\nu } , \qquad \nu = 1,2,\ldots , \quad k = 1,2,\ldots . \end{aligned}$$

Lemma 3.5

Suppose $U \in {\mathcal {T}}_\nu$, $\tau \in [0,2\pi /\nu ]$, $A \ge 0.005$, and $|U(\tau )| \ge A \Vert U\Vert$. Let

$$\begin{aligned} I_{j,\nu } := \left[ \frac{j\eta }{\nu }, \frac{(j+1)\eta }{\nu } \right] \subset \left[ \tau , \tau + \frac{18\pi }{\nu } \right] , \qquad j = u,u+1,\ldots , k . \end{aligned}$$

(3.1)

We have

$$\begin{aligned} \min _{t \in I_{j,\nu }}{|U(t)|} \ge \frac{A}{400} \left( \frac{\eta }{18\pi } \right) ^{200} \Vert U\Vert \end{aligned}$$

for at least one $j \in \{v,v+1,\ldots ,v+399\}$ for every $v \in \{u,u+1,\ldots ,k-399\} .$

Proof

Suppose the statement of the lemma is false, and there are $v \in \{u,u+1,\ldots ,k-399\}$ and

$$\begin{aligned} x_j \in I_{j,\nu } := \left[ \frac{j\eta }{\nu }, \frac{(j+1)\eta }{\nu } \right] \subset \left[ \tau , \tau + \frac{18\pi }{\nu } \right] \end{aligned}$$

(3.2)

such that

$$\begin{aligned} |U(x_j)| < \frac{A}{400} \left( \frac{\eta }{2\pi } \right) ^{200} \Vert U\Vert , \qquad j \in \{v,v+1,\ldots ,v+399\} . \end{aligned}$$

Let $y_j := x_{v+2j-1}$ for $j \in \{1,2,\ldots ,200\}$. Then, the points $y_j$ satisfy

$$\begin{aligned} y_1 - \tau \ge \frac{\eta }{\nu }\, \quad \text {and} \quad y_{j+1}-y_j \ge \frac{\eta }{\nu } , \qquad j \in \{1,2,\ldots ,200\} . \end{aligned}$$

By the well-known formula for divided differences, we have

$$\begin{aligned} U(\tau ) \prod _{h=1}^{200}{(\tau -y_h)^{-1}} + \sum _{j=1}^{200}{U(y_j) (\tau -y_j)^{-1} \prod _{\begin{array}{c} h=1 \\ h \ne j \end{array}}^{200}{(y_h-y_j)^{-1}}} = \frac{1}{200!} U^{(200)}(\xi ) , \end{aligned}$$

and combining this with $|U(\tau )| \ge A \Vert U\Vert$, (3.1), and (3.2), we get

$$\begin{aligned} A \Vert U\Vert \left( \frac{18\pi }{\nu } \right) ^{-200} \le 200 \, \frac{A}{400} \left( \frac{\eta }{18\pi } \right) ^{200} \Vert U\Vert \left( \frac{\eta }{\nu } \right) ^{-200} + \frac{1}{200!} |U^{(200)}(\xi )| , \end{aligned}$$

with some $\xi \in [\tau , \tau + 18\pi /\nu ]$. Therefore, Bernstein’s inequality (Lemma 3.4) yields that

$$\begin{aligned} A \Vert U\Vert \left( \frac{18\pi }{\nu } \right) ^{-200} \le 200 \, \frac{A}{400} \left( \frac{\eta }{18\pi } \right) ^{200} \Vert U\Vert \left( \frac{\eta }{\nu } \right) ^{-200} + \frac{1}{200!} \nu ^{200} \Vert U\Vert , \end{aligned}$$

that is,

$$\begin{aligned} A \le \frac{2(18\pi )^{200}}{200!} \le 2 \left( \frac{18\pi e}{200} \right) ^{200} < 0.005 , \end{aligned}$$

which contradicts our assumption $A \ge 0.005$. $\square$

The following lemma ascribed to M. Riesz is well known and can easily be proved by a simple zero counting argument (see [6], for instance).

Lemma 3.6

If $T \in {\mathcal {T}}_\nu$, $t_0 \in {{\mathbb {R}}}$, and $|T(t_0)| = \Vert T\Vert$, then

$$\begin{aligned} |T(t)| \ge |T(t_0)| \, \cos (\nu (t-t_0)) , \qquad t \in {{\mathbb {R}}}, |t-t_0| \le \frac{\pi }{2\nu } . \end{aligned}$$

We will also need the following simple corollary of the above lemma.

Lemma 3.7

If $L = 32n$,

$$\begin{aligned} t_r := \frac{(2r-1)\pi }{4L} , \qquad r=1,2,\ldots ,4L , \end{aligned}$$

and $T \in {\mathcal {T}}_{2n}$, then

$$\begin{aligned} \max _{t \in {{\mathbb {R}}}}{|T(t)|} \le (\cos (\pi /64))^{-1} \max _{1 \le r \le 4L}{|T(t_r)|} \le (1.0013) \, \max _{1 \le r \le 4L}{|T(t_r)|} . \end{aligned}$$

4 Minimizing Discrepancy

Associated with a vector ${\textbf {x}} = \langle x_1,x_2,\ldots ,x_v \rangle \in {{\mathbb {R}}}^v$, let

$$\begin{aligned} \Vert {\textbf {x}}\Vert _\infty := \max \{|x_1|,|x_2|,\ldots ,|x_v|\} . \end{aligned}$$

A crucial ingredient in [2] is the main “partial coloring” lemma of Spencer [18] based on a technique of Beck [3]. In section 4 of [2], a simple consequence of a variant of this due to Lovett and Meka [15,  Theorem 4] is observed, and it plays an important part in the proof of Theorem 6.1. This can be stated as follows.

Lemma 4.1

Let ${\textbf {y}}_1, {\textbf {y}}_2,\ldots ,{\textbf {y}}_u \in {{\mathbb {R}}}^v$ and ${\textbf {x}}_0 \in [-1,1]^v$. If $c_1,c_2,\ldots ,c_u \ge 0$ are such that

$$\begin{aligned} \sum _{r=1}^u\exp (-(c_r/14)^2) \le \frac{v}{16} , \end{aligned}$$

(4.1)

then there exists an ${\textbf {x}} \in \{-1,1\}^v$ such that

$$\begin{aligned} |\langle {\textbf {x}} - {\textbf {x}}_0, {\textbf {y}}_r \rangle | \le (c_r + 30)\sqrt{u} \, \Vert {\textbf {y}}_r\Vert _\infty , \qquad r=1,2,\ldots ,u . \end{aligned}$$

5 The Cosine Polynomial

Theorem 5.1

Let $n > 0$ be a sufficiently large integer divisible by 10. Let $\mu = \gamma n$ defined by (2.3). There exists a cosine polynomial

$$\begin{aligned} c(t) = \sum _{k=0}^{\mu }{\varepsilon _k\cos (2kt)} , \qquad \varepsilon _0 = 1 , \quad \varepsilon _k \in \{-1,1\} , \quad k=1,2,\ldots ,\mu , \end{aligned}$$

(5.1)

and a suitable and well-separated collection ${\mathcal {I}}$ of disjoint closed intervals (with nonempty interiors) in ${{\mathbb {R}}}/(2\pi {{\mathbb {Z}}})$ such that

$$\begin{aligned} c(t) \ge \eta _1 \sqrt{n} , \qquad t \notin \bigcup _{I \in {\mathcal {I}}}{I} , \end{aligned}$$

and

$$\begin{aligned} c(t) \le \sqrt{n} , \qquad t \in {{\mathbb {R}}} , \end{aligned}$$

where $\eta _1 > 0$ is an absolute constant.

Proof

Let $c(t) := U(t) := T(2t)$, where $T \in {\mathcal {T}}_{\mu -1}$ with $\mu := 9M$ is defined by (2.2) and $U \in {\mathcal {T}}_{\nu -2}$ with $\nu := 2\mu$. Observe that c is of the form (5.1). It follows from (2.1), (2.3), and (2.4) that

$$\begin{aligned} |c(t)| \le 9\sqrt{2M} \le 3\sqrt{2\mu } \le \sqrt{n} . \end{aligned}$$

Set

$$\begin{aligned} \eta := 20\pi \gamma = 20\pi \mu /n = 10\pi \nu /n \qquad \text {and} \qquad \eta _1 := \frac{0.005}{400} \left( \frac{\eta }{18\pi } \right) ^{200} . \end{aligned}$$

We partition ${{\mathbb {R}}}/(2\pi {{\mathbb {Z}}})$ into n/5 intervals

$$\begin{aligned} I_j := \left[ \frac{10\pi j}{n}, \frac{10\pi (j+1)}{n} \right] , \qquad j=0,1,\ldots ,n/5-1 , \end{aligned}$$

and say that an interval $I_j$ is good if

$$\begin{aligned} \min _{t \in I_j}{|U(t)|} \ge \frac{0.005}{400} \left( \frac{\eta }{18\pi } \right) ^{200} \Vert U\Vert . \end{aligned}$$

Let ${\mathcal {J}}$ be the collection of maximal unions of consecutive good intervals $I_j$, and let ${\mathcal {I}}$ be the collection of the remaining intervals (that is, the maximal unions of consecutive bad intervals). We claim that ${\mathcal {I}}$ is the required suitable and well-separated collection.

First, to see that ${\mathcal {I}}$ is suitable, note that the endpoints of each of the intervals $I_j$ are in $10\pi {{\mathbb {Z}}}$. The set ${\mathcal {I}}$ is invariant under the maps $\theta \rightarrow \pi \pm \theta$ by the symmetries of the functions $\cos (2kt)$, $k=0,1,\ldots ,\mu$. To see that $4N = |{\mathcal {I}}| \le 4\gamma n$, note that a real trigonometric polynomial of degree at most $\nu$ has at most $2\nu$ real zeros in a period, and hence there are at most $4\nu$ values of t in a period for which

$$\begin{aligned} U(t) = \frac{\pm 0.005}{400} \left( \frac{\eta }{18\pi } \right) ^{200} \Vert U\Vert . \end{aligned}$$

Since each $I \in {\mathcal {I}}$ must contain at least two such points (counted with multiplicities), we have $4N := |{\mathcal {I}}| \le 2\nu = 4\mu = 4\gamma n$. Thus, ${\mathcal {I}}$ has each of the properties (a), (b), and (c) in the definition of a suitable collection.

We now show that ${\mathcal {I}}$ is well separated. By Lemmas 2.2, 3.4, and 3.5, any 400 consecutive intervals $I_j$ must contain a good interval, and hence $|I| \le 3990\pi /n$ for each $I \in {\mathcal {I}}$. Thus, ${\mathcal {I}}$ has property (d) in the definition of a well-separated collection. The fact that ${\mathcal {I}}$ has property (e) in the definition of a suitable collection is obvious by the construction. Finally observe that for an odd m we have $|P_m(1)| = 2^{(m+1)/2} = \Vert P_m(e^{it})\Vert ,$ from which

$$\begin{aligned} |T(0)| = |T(\pi )| = \Vert T\Vert \end{aligned}$$

follows. Hence, property (f) in the definition of a well-separated collection follows from the Riesz’s Lemma stated as Lemma 3.6 (recall that $\nu = 2\mu = 2\gamma n < 2^{-72}n$). $\square$

6 The Sine Polynomials

Theorem 6.1

Let $n > 0$ be an integer divisible by 10. Let ${\mathcal {I}}$ be a suitable and well-separated collection of disjoint closed intervals (with nonempty interiors) in ${{\mathbb {R}}}/(2\pi {{\mathbb {Z}}})$. There exists a sine polynomial

$$\begin{aligned} s_o(t) = \sum _{k=1}^n{\varepsilon (2k-1)\sin ((2k-1)t)} , \qquad \varepsilon (2k-1) \in \{-1,1\} , \end{aligned}$$

such that

$$\begin{aligned} |s_o(t)| \ge 36 \sqrt{n} , \qquad t \in \bigcup _{I \in {\mathcal {I}}}{I} , \qquad \text {and} \qquad |s_o(t)| \le 1090\sqrt{n} , \qquad t \in {{\mathbb {R}}} . \end{aligned}$$

To prove Theorem 6.1, we need some lemmas.

Lemma 6.2

Let ${\mathcal {I}}$ be a suitable and well-separated collection of disjoint closed intervals (with nonempty interiors) in ${{\mathbb {R}}}/(2\pi {{\mathbb {R}}})$. There exists a symmetric coloring $\alpha : {\mathcal {I}} \rightarrow \{-1,1\}$ such that

$$\begin{aligned} a_k(G_\alpha )= & {} 0 , \qquad k=0,1,\ldots ,2n , \\ b_{2k}(G_\alpha )= & {} 0 \quad \text {and} \quad |b_{2k-1}(G_\alpha )| \le 1 , \qquad k=1,2,\ldots ,n . \end{aligned}$$

Proof

As before, we denote the intervals in a suitable and well-separated collection ${\mathcal {I}}$ by $I_j$, $j=1,2,\ldots ,4N$, where $I_1, I_2, \ldots , I_N \subset (0,\pi /2)$. As we have already observed before, we have $a_k(G_\alpha ) = 0, k=0,1,\ldots ,2n$, and $b_{2k}(G_\alpha ) = 0, k=1,2,\ldots ,n$, for every symmetric coloring $\alpha : {\mathcal {I}} \rightarrow \{-1,1\}$, so we have to show only that there exists a symmetric coloring $\alpha : {\mathcal {I}} \rightarrow \{-1,1\}$ such that $|b_{2k-1}(G_\alpha )| \le 1, k=1,2,\ldots ,n$. To this end, let

$$\begin{aligned} {\textbf {y}}_k := \langle y_{k,1},y_{k,2},\ldots ,y_{k,N} \rangle , \qquad k=1,2,\ldots ,n , \end{aligned}$$

with

$$\begin{aligned} y_{k,j} := \frac{4K\sqrt{n}}{\pi } \int _{-\pi }^{\pi } {\Phi _{I_j}(t)\sin ((2k-1)t) \, {\mathrm{d}}t} , \qquad k=1,2,\ldots ,n, j=1,2,\ldots ,N . \end{aligned}$$

If $\alpha : {\mathcal {I}} \rightarrow \{-1,1\}$ is a symmetric coloring, then by the symmetry conditions on ${\mathcal {I}}$ we have

$$\begin{aligned} b_{2k-1}(G_\alpha ) := \frac{1}{\pi } \int _{-\pi }^{\pi }{G_\alpha (t) \sin ((2k-1)t)) \, {\mathrm{d}}t} = \sum _{j=1}^N{\alpha (I_j)y_{k,j}} , \qquad k=1,2,\ldots ,n . \end{aligned}$$

We apply Lemma 4.1 with $u := n$, $v := N$, ${\textbf {x}}_0 := {\textbf {0}} \in [-1,1]^N$, and

$$\begin{aligned} c_1 = c_2 = \cdots = c_n := 14\sqrt{\log (16n/N)} . \end{aligned}$$

Observe that

$$\begin{aligned} \sum _{r=1}^u{\exp (-c_r^2/14^2)} = n \frac{N}{16n} = \frac{N}{16} , \end{aligned}$$

so (4.1) is satisfied. It follows from Lemma 4.1 that there exists an

$$\begin{aligned} \langle \alpha (I_1),\alpha (I_2),\ldots ,\alpha (I_N) \rangle = {\textbf {x}} \in \{-1,1\}^N \end{aligned}$$

such that

$$\begin{aligned} |\langle {\textbf {x}},{\textbf {y}}_k \rangle | \le (c_k+30)\sqrt{N} \, \Vert {\textbf {y}}_k\Vert _\infty , \qquad k=1,2,\ldots ,n . \end{aligned}$$

As ${\mathcal {I}}$ is well separated, by part (d) of the definition we have

$$\begin{aligned} |y_{k,j}| \le \frac{4K \sqrt{n}}{\pi }(|I_j| + 10\pi /n) \le \frac{4K \sqrt{n}}{\pi }\frac{4000\pi }{n} = \frac{16000K}{\sqrt{n}} \end{aligned}$$

for every $k = 1,2,\ldots ,n$ and $j = 1,2,\ldots ,N .$ It follows that

$$\begin{aligned} |b_{2k-1}(G_\alpha )|= & {} |\langle {\textbf {x}},{\textbf {y}}_k \rangle | \\ {}\le & {} (14\sqrt{\log (16n/N)} + 30) \sqrt{N/n} \cdot 16000 K , \qquad k=1,2,\ldots ,n . \end{aligned}$$

As the right-hand side above is an increasing function of N for $N/n \le \gamma < 1$, we have

$$\begin{aligned} |b_{2k-1}(G_\alpha )|= & {} |\langle {\textbf {x}},{\textbf {y}}_k \rangle | \\ {}\le & {} (14\sqrt{\log (16/\gamma )} + 30) \sqrt{\gamma } \cdot 16000 K \le 1 , \qquad k=1,2,\ldots ,n , \end{aligned}$$

where the last inequality follows from $K := 2^9$ and the inequality $2^{-75} \le \gamma < 2^{-73}$. Hence, the desired symmetric coloring is given by setting

$$\begin{aligned} \langle \alpha (I_1),\alpha (I_2),\ldots ,\alpha (I_N) \rangle := {\textbf {x}} . \end{aligned}$$

$\square$

From now on let $\alpha :{\mathcal {I}} \rightarrow \{-1,1\}$ denote the symmetric coloring guaranteed by Lemma 6.2. Then, we have

$$\begin{aligned} V_n(G_\alpha ,t) = \sum _{k=0}^n{{\widetilde{\varepsilon }}(2k-1)\sin ((2k-1)t)} , \qquad |{\widetilde{\varepsilon }}(2k-1)| \le 1 . \end{aligned}$$

Lemma 6.3

There is a coloring $\varepsilon : S_o \rightarrow \{-1,1\}$ such that with the notation

$$\begin{aligned} s_o(t) = \sum _{k=1}^n{\varepsilon (2k-1)\sin ((2k-1)t)} \end{aligned}$$

we have

$$\begin{aligned} |s_o(t) - V_n(G_\alpha ,t)| \le 66\sqrt{n} , \qquad t\in {{\mathbb {R}}} . \end{aligned}$$

Proof

Let $L := 32n$,

$$\begin{aligned}&t_r := \frac{(2r-1)\pi }{4L} , \qquad r=1,2,\ldots ,4L , \\&y_{r,k} := \sin ((2k-1)t_r) , \qquad r=1,2,\ldots ,L , k=1,2,\ldots ,n , \\&{\textbf {y}}_r := \langle y_{r,1}, y_{r,2}, \ldots ,y_{r,n} \rangle , \qquad r=1,2,\ldots ,L . \end{aligned}$$

Observe that

$$\begin{aligned} s_o(t_r) - V_n(G_\alpha ,t_r) = \sum _{k=1}^n{(\varepsilon (2k-1) - {\widetilde{\varepsilon }}(2k-1))y_{r,k}} = \langle {\textbf {e}} - \widetilde{{\textbf {e}}}, {\textbf {y}}_r \rangle , \end{aligned}$$

(6.1)

where

$$\begin{aligned} {\textbf {e}} := \langle \varepsilon (1), \varepsilon (3),\ldots , \varepsilon (2n-1) \rangle \qquad \text {and} \qquad \widetilde{{\textbf {e}}} := \langle {\widetilde{\varepsilon }}(1), {\widetilde{\varepsilon }}(3),\ldots , {\widetilde{\varepsilon }}(2n-1) \rangle . \end{aligned}$$

We apply Lemma 4.1 with $u := L$, $v := n$, ${\textbf {x}}_0 := \widetilde{{\textbf {e}}}$, and

$$\begin{aligned} c_1 = c_2 = \cdots = c_n := 42\sqrt{\log 2} . \end{aligned}$$

Observe that

$$\begin{aligned} \sum _{r=1}^u{\exp (-c_r^2/14^2)} = L2^{-9} = \frac{n}{16} , \end{aligned}$$

so (4.1) is satisfied. It follows from Lemma 4.1 that there exists an ${\textbf {e}} \in \{-1,1\}^n$ such that

$$\begin{aligned} |\langle {\textbf {e}} - \widetilde{{\textbf {e}}}, {\textbf {y}}_r \rangle |\le & {} (c_r + 30)\sqrt{n} \Vert {\textbf {y}}_r\Vert _\infty \nonumber \\ {}\le & {} (c_r + 30)\sqrt{n} \le 65\sqrt{n} , \qquad r=1,2,\ldots ,L . \end{aligned}$$

(6.2)

Combining (6.1) and (6.2), we obtain

$$\begin{aligned} |s_o(t_r) - V_n(G_\alpha ,t_r)| \le 65 \sqrt{n} , \qquad r=1,2,\ldots ,L . \end{aligned}$$

Note that by the special form of the trigonometric polynomials $s_o$ and $V_n(G_\alpha ,\cdot )$, we have

$$\begin{aligned} \max _{1 \le r \le L}{|s_o(t_r) - V_n(G_\alpha ,t_r)|} = \max _{1 \le r \le 4L}{|s_o(t_r) - V_n(G_\alpha ,t_r)|} , \end{aligned}$$

hence

$$\begin{aligned} |s_o(t_r) - V_n(G_\alpha ,t_r)| \le 65 \sqrt{n} , \qquad r=1,2,\ldots ,4L . \end{aligned}$$

This, together with Lemma 3.7 gives the lemma. $\square$

Lemma 6.4

We have

$$\begin{aligned} |V_n(G_\alpha ,t)| \ge \frac{K\sqrt{n}}{5} , \qquad t \in \bigcup _{I \in {\mathcal {I}}}{I} , \qquad \text {and} \qquad |V_n(G_\alpha ,t)| \le 2K\sqrt{n} , \qquad t \in {{\mathbb {R}}} . \end{aligned}$$

Proof

Combining Lemmas 3.3 and 3.2 we have

$$\begin{aligned} \max _{t \in {{\mathbb {R}}}}{|V_n(G_\alpha ,t) - G_\alpha (t)|} \le 4E_n(G_\alpha ) \le 4\omega (G_\alpha ,\pi /n) \le \frac{4K\sqrt{n}}{5} , \end{aligned}$$

and the lemma follows. $\square$

Let $\mu = 9M = 9 \cdot 2^m$ be the same as in Sect. 2, and let

$$\begin{aligned} s_e(t) := \text {Im}(P_{<(n+1)}(e^{2it})) - \text {Im}(P_{< \mu }(e^{2it})) . \end{aligned}$$

Lemma 6.5

We have

$$\begin{aligned} \Vert s_e\Vert \le 6\sqrt{n} . \end{aligned}$$

Proof

This is an obvious consequence of Lemma 2.1. Recall that $\mu = \gamma n < 2^{-73}n$. $\square$

Proof of Theorem 6.1

Let ${\mathcal {I}}$ be a suitable and well-separated collection of disjoint closed intervals (with nonempty interiors) in ${{\mathbb {R}}}/(2\pi {{\mathbb {Z}}})$. By Lemma 6.3, there is a coloring $\varepsilon :S_o \rightarrow \{-1,1\}$ such that if $\alpha : {\mathcal {I}} \rightarrow \{-1,1\}$ is the symmetric coloring given by Lemma 6.2, then

$$\begin{aligned} |s_o(t) - V_n(G_\alpha ,t)| \le 66\sqrt{n} , \qquad t\in {{\mathbb {R}}} . \end{aligned}$$

Hence by Lemma 6.4 and $K := 2^9$, we have

$$\begin{aligned} |s_o(t)|\ge & {} |V_n(G_\alpha ,t)| - |s_o(t) - V_n(G_\alpha ,t)| \\ {}\ge & {} 102\sqrt{n} - 66\sqrt{n} \ge 36\sqrt{n} , \qquad t \in \bigcup _{I \in {\mathcal {I}}}{I} , \end{aligned}$$

and

$$\begin{aligned} |s_o(t)|\le & {} |V_n(G_\alpha ,t)| + |s_o(t) - V_n(G_\alpha ,t)| \le 2^{10}\sqrt{n} + 66\sqrt{n} \\ {}\le & {} 1090\sqrt{n} , \quad t \in {{\mathbb {R}}} . \end{aligned}$$

$\square$

7 Proof of Theorems 1.1 and 1.2

Proof of Theorems 1.2

It is sufficient to prove the theorem with 2n replaced by 4n, and without loss of generality we may assume that $n > 0$ is an integer divisible by 10. Since the Littlewood polynomial $P_{4n}(z) := 1-z-z^2-\cdots -z^{4n}$ does not vanish on the unit circle, we may assume also that n is sufficiently large. By Theorems 5.1 and 6.1 the Littlewood polynomial $P_{4n}$ of degree 4n defined by

$$\begin{aligned} P_{4n}(e^{it})e^{-2int} = (-1 + 2c(t)) + 2i(s_o(t) + s_e(t)) \end{aligned}$$

has the properties required by the theorem. It is obvious from the construction that the coefficients of $P_{4n}$ satisfy the requirements. To see that the required inequalities are satisfied let ${\mathcal {I}}$ be a suitable and well-separated collection of disjoint closed intervals (with nonempty interiors) in ${{\mathbb {R}}}/(2\pi {{\mathbb {Z}}})$ on which (5.1) holds. Then, Theorem 5.1 gives that

$$\begin{aligned} |P_{4n}(e^{it})| \ge |-1 + 2c(t)| \ge \eta _1 \sqrt{n} , \qquad t \notin \bigcup _{I \in {\mathcal {I}}}{I} , \end{aligned}$$

while Theorem 6.1 gives that

$$\begin{aligned} |P_{4n}(e^{it})|\ge & {} |2(s_o(t) + s_e(t))| \ge |2s_o(t)| \\&- |2s_e(t)| \ge 72\sqrt{n} - 12\sqrt{n} = 60\sqrt{n} , \quad t \in \bigcup _{I \in {\mathcal {I}}}{I} . \end{aligned}$$

Combining the two inequalities above gives the lower bound of the theorem. The upper bounds of the theorem follow from combining the upper bounds of Theorems 5.1 and 6.1 by

$$\begin{aligned} \begin{aligned} |P_{4n}(e^{it})|&\le \, |-1 + 2c(t)| + |2(s_o(t) + s_e(t))| \le 1 + 2\sqrt{n} + 2180\sqrt{n} + 12 \sqrt{n} \\&\le \, 1 + 2194 \sqrt{n} , \quad {t \in {\mathbb {R}}} . \\\end{aligned} \end{aligned}$$

For the value $m_n$ in the theorem, we have $m_n = 2\mu = 2\gamma n$, so $\eta = 2\gamma > 0$ can be chosen. $\square$