1 Introduction
The study of Littlewood polynomials enjoys a long and outstanding history [Reference Montgomery22]. A polynomial with all coefficients in $\{-1,1\}$ is called a Littlewood polynomial, and we denote by $\mathcal {L}_n$ the family of Littlewood polynomials of degree $n-1$ ; that is,
The $L^p$ norm of Littlewood polynomials on the unit circle has been a fascinating and classical subject of many studies over the last 60 years [Reference Borwein and Lockhart7, Reference Borwein and Mossinghoff8, Reference Erdős10, Reference Erdős11, Reference Littlewood20, Reference Littlewood21, Reference Newman23, Reference Newman and Byrnes24]. Here, the $L^p$ norm $(1\leq p<\infty )$ of $q_n\in \mathcal {L}_n$ on the unit circle is given by
while $||q_n||_{\infty }$ is the supremum of $|q_n(z)|$ on the unit circle. The $L^1, L^4$ , and $L^{\infty }$ norms hold special significance in the field of analysis.
Littlewood [Reference Littlewood20, Section 6] asked how slowly the $L^4$ norm of $q_n\in \mathcal {L}_n$ can grow with n. Subsequently, the $L^4$ norm has been studied extensively, which is of interests in communication theory [Reference Borwein5, Reference Borwein, Choi and Jedwab6, Reference Golay12, Reference Høholdt and Jensen14, Reference Jedwab, Helleseth, Sarwate, Song and Yang15, Reference Jensen, Jensen and Høholdt17]. There are two natural measures which are often used in the investigation of how small the $L^4$ norm can be. The first one is the ratio $||q_n||_4/||q_n||_2$ ; that is, $||q_n||_4/\sqrt {n}$ . The other is the merit factor
which is considered in the context of the theory of communications [Reference Beenker, Claasen and Hermens3], where Littlewood polynomials with large merit factor correspond to signals with uniformly distributed energy over frequency. Obviously, a small $L^4$ norm corresponds to a large merit factor. Moreover, establishing the minimum achievable $L^4$ norm for Littlewood polynomials has demonstrated substantial importance in theoretical physics [Reference Bernasconi4], where Littlewood polynomials with the largest merit factor correspond to the ground states of Bernasconi’s Ising spin model.
Littlewood’s question has sparked much interest among mathematicians and physicists (see [Reference Jedwab, Helleseth, Sarwate, Song and Yang15] for a survey of relevant results and historical developments). In 1968, Littlewood [Reference Littlewood21] constructed a sequence of polynomials, of Rudin–Shapiro type, with asymptotic merit factor $3$ ; that is, the ratio $||q_n||_4/\sqrt {n}$ is asymptotically $\sqrt [4]{4/3}$ . In 1988, Hødoldt and Jensen [Reference Høholdt and Jensen14], working in information theory, showed that this ratio for a sequence of Littlewood polynomials derived from Fekete polynomials is asymptotically $\sqrt [4]{7/6}$ , correspondingly, with the asymptotic merit factor $6$ . They conjectured that the asymptotic value of this ratio cannot be further reduced, and in fact, $\sqrt [4]{7/6}$ has remained the smallest published asymptotic value for more than two decades. In 2013, Jedwab, Katz, and Schmidt [Reference Jedwab, Katz and Schmidt16] made a major discovery indicating that this is not the minimum asymptotic value, thus disproving the abovementioned conjecture. They proved that there exists a sequence of Littlewood polynomials, derived from Fekete polynomials, with the limit of the ratio less than $\sqrt [4]{22/19}$ .
The roots of all these explorations actually go back to the original Littlewood’s conjecture [Reference Littlewood20] from 1966 which states that, for all $n\geq 1$ , there exists a polynomial $q_n\in \mathcal {L}_n$ such that
for all complex z of modulus 1, where $C_1$ and $C_2$ are positive absolute constants. Polynomials satisfying (2) are known as flat polynomials. This conjecture was discussed in detail in his well-known 1968 monograph [Reference Littlewood21, Problem 19], in which he laid out his $30$ favorite problems. A significant result by Kahane [Reference Kahane18, Reference Kahane19] establishes that there exist ultra-flat polynomials with coefficients of modulus 1, namely, polynomials that satisfy
for all z with $|z|=1$ . Subsequently, an interesting result, due to Beck [Reference Beck2], states that flat polynomials exist with coefficients being 400th roots of unity. However, for the more restrictive class of Littlewood polynomials, much less progress has been made over the next few decades until 2020. Then Littlewood’s conjecture was famously confirmed by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [Reference Balister, Bollobás, Morris, Sahasrabudhe and Tiba1], who showed that flat Littlewood polynomials exist and answered the question of Erdős [Reference Erdős10, Problem 26].
Newman and Byrnes [Reference Newman and Byrnes24] calculated the expected $L^4$ norm of $q_n\in \mathcal {L}_n$ , specifically,
and therefore the expected merit factor is 1. Borwein and Lockhart [Reference Borwein and Lockhart7] showed that the ratio $||q_n||_4/\sqrt {n}$ converges to $\sqrt [4]{2}$ in probability for $q_n\in \mathcal {L}_n$ , equivalently, MF $(q_n)\rightarrow 1$ in probability. In [Reference Borwein and Mossinghoff8], Borwein and Mossinghoff explicitly calculated the $L^4$ norm of Rudin–Shapiro-like polynomials. In [Reference Salem and Zygmund26], Salem and Zygmund showed that the supremum of Littlewood polynomials on the unit disk lies between $c_1\sqrt {n\log {n}}$ and $c_2\sqrt {n\log {n}}$ . Indeed, Halász [Reference Halász13] proved that $\lim ||q_n/\sqrt {n\log {n}}||_{\infty }=1$ almost surely.
The aim of this paper is to prove the almost sure convergence of $L^4$ norm of Littlewood polynomials. Our main result is the following.
Theorem 1 Let $q_n\in \mathcal {L}_n$ . Then
almost surely.
This result has been conjectured by Borwein and Lockhart and numerical simulations were performed by Robinson in her master’s thesis [Reference Robinson25], confirming the rationality of this conjecture and consistent with our theoretical result. An extension of Theorem 1 to a more general case is included in Section 4, where only a fourth moment condition is assumed.
2 Preliminary results
In this section, we present several lemmas before we prove Theorem 1. We let ${A_n^m=n!/(n-m)!}$ and the combinatorial number of selecting m elements from n distinct elements is denoted by $\binom {n}{m} = n!/ (n-m)!m!$ . To ensure convenience in calculations, we will adjust the indices from “ $0$ to $n-1$ ” to “ $1$ to n” at a few places, given that the $L^4$ norms of $\sum _{k=0}^{n-1}\varepsilon _k z^{k}$ and $\sum _{k=1}^{n}\varepsilon _k z^{k}$ on the unit circle are the same.
Lemma 2 Let $q_n\in \mathcal {L}_n$ . The following assertions hold:
-
(i) If n is even, then
$$ \begin{align*}\mathbb{E}(||q_n||_4^8 )=4n^4+\frac{4}{3}n^3-19n^2+\frac{56}{3}n.\end{align*} $$ -
(ii) If n is odd, then
$$ \begin{align*}\mathbb{E}(||q_n||_4^8 )=4n^4+\frac{4}{3}n^3-19n^2+\frac{56}{3}n-4.\end{align*} $$ -
(iii) If n is even, then
$$ \begin{align*}\mathbb{E}(||q_{n+1}||_4^4 \cdot ||q_n||_4^4 )=4n^4+\frac{28}{3}n^3-21n^2+\frac{53}{3}n.\end{align*} $$ -
(iv) If n is odd, then
$$ \begin{align*}\mathbb{E}(||q_{n+1}||_4^4 \cdot ||q_n||_4^4)=4n^4+\frac{28}{3}n^3-21n^2+\frac{53}{3}n-4.\end{align*} $$
In particular, the values in (i)–(iv) are positive integers.
Proof By observation,
Therefore, we obtain
and
Our goal is to count the number of terms with nonvanishing expectation, namely, we concern the terms such that $\mathbb {E}\big (\varepsilon _j\varepsilon _k\varepsilon _l\varepsilon _m\varepsilon _{j'} \varepsilon _{k'} \varepsilon _{l'} \varepsilon _{m'}\big )=1$ .
For (i), as shown in Figure 1, we divide the eight parameters into two groups. The proof proceeds by considering three cases according to the choice of the subscripts $j,k,l,m,j' , k', l', m'$ .
Case 1 Each group has two equal pairs of subscripts.
We take the Group A as an example. There are three options for subscripts $j,k,l,m$ :
The three types above correspond to
respectively. A similar approach works for Group B. Thus, there are nine different subcases in Case 1 (see Table 1 for the quantity corresponding to each subcase).
Consequently, the sum of these quantities is $4n^4-4n^3+n^2$ . Incidentally, Case 1 is the most numerous.
Case 2 Each group has only one pair of equal subscripts.
Since we are concerned with the terms such that $\mathbb {E}\big (\varepsilon _j\varepsilon _k\varepsilon _l\varepsilon _m\varepsilon _{j'} \varepsilon _{k'} \varepsilon _{l'} \varepsilon _{m'}\big )=1$ , if one of the Groups A and B has only one pair of equal subscripts, then so does the other group.
Let us take the subcase $j\neq k,~l=m$ in Group A as an example. Under this assumption, it is worth noting that both j and k are either odd or even. Hence, if j and k have been determined, then there must be $l=m=\frac {j+k}{2}$ . Now, correspondingly, Group B has the following options:
Bearing in mind that n is even, whether j and k are both odd or even, the corresponding quantity is $A_{\frac {n}{2}}^2\cdot 4=n^2-2n$ . Hence, for such a subcase, the quantity of options is $2n^2-4n$ . Similarly, in the subcase $j=k,~l\neq m$ , the quantity is also $2n^2-4n$ . Consequently, the quantity of options in Case 2 is $4n^2-8n$ .
Case 3 Each group has no pair of equal subscripts.
In this case, we suppose that $j\neq k\neq l \neq m$ for Group A. Recall that $j+k=l+m,~1\leq j,k,l,m\leq n$ . Let us take $\varepsilon _1\varepsilon _5\varepsilon _2\varepsilon _4$ as a simple example. Since we want $\mathbb {E}\big (\varepsilon _j\varepsilon _k\varepsilon _l\varepsilon _m\varepsilon _{j'} \varepsilon _{k'} \varepsilon _{l'} \varepsilon _{m'}\big )=1$ , if $\varepsilon _1\varepsilon _5\varepsilon _2\varepsilon _4$ appears in Group A, then, correspondingly, one of the following must appear in Group B:
Therefore, it suffices to consider Group A, and for every choice in Group A, there are eight choices in Group B correspondingly.
Now the problem naturally transforms into considering how many options there are for $j,k,l,m$ to satisfy the following conditions:
For example, we observe that this set of subscripts $\{1,2,4,5\}$ will appear eight times in Group A by adjusting the order reasonably, as shown in (9). For brevity, we first consider the non-repeating case, regardless of the order. For any even number n, the quantity of options in non-repeating case is
As was mentioned earlier, each set of subscripts has eight different kinds of ordering. Therefore, the quantity of options for Group A is $\frac {2}{3}n^3-3n^2+\frac {10}{3}n$ . Combined with the previous analysis for Group B, we obtain that the quantity of options in Case 3 is $\frac {16}{3}n^3-24n^2+\frac {80}{3}n$ . Summing the quantities in all cases, we obtain (i), as desired.
A reasoning similar to the proof of (i) leads to (ii). For reader’s convenience, we outline the proof. For Case 1, it is exactly the same as before, since it makes no difference whether n is odd or even. For Case 2, there are two subcases for Group A, $j\neq k,~l=m$ and $j=k,~l\neq m$ . Take the subcase $j\neq k,~l=m$ as an example. Bearing in mind that n is odd,
-
• if j and k are both odd, then the corresponding quantity is $A_{\frac {n+1}{2}}^2\cdot 4$ ,
-
• if j and k are both even, then the corresponding quantity is $A_{\frac {n-1}{2}}^2\cdot 4$ .
Hence, the quantity of options for such a subcase is $2n^2-4n+2$ . For the other subcase, the argument is the same as above. Consequently, the quantity of options in Case 2 is $4n^2-8n+4$ . For Case 3, as discussed in (i), it suffices to solve the following problem: how many options there are for $j,k,l,m$ to satisfy the following conditions:
where n is odd. Similarly, we still consider the non-repeating case first. For any odd number n, the quantity of options in non-repeating case is
Therefore, the quantity of options for Group A is $\frac {2}{3}n^3-3n^2+\frac {10}{3}n-1$ . Further, with consideration of Group B, there are $\frac {16}{3}n^3-24n^2+\frac {80}{3}n-8$ options in Case 3. Consequently, combing three cases, we get the assertion in (ii).
For (iii) and (iv), we divide the eight parameters into two groups as shown in Figure 2 and the proof proceeds by considering three cases as in (i).
We prove (iii) first. Case 1 has the following nine subcases and the corresponding quantity of options for each subcase is shown in Table 2. Therefore, the sum of these quantities in Case 1 is $4n^4+4n^3-n^2-n$ . For Cases 2 and 3, if we want $\mathbb {E}\big (\varepsilon _j\varepsilon _k\varepsilon _l\varepsilon _m\varepsilon _{j'} \varepsilon _{k'} \varepsilon _{l'} \varepsilon _{m'}\big )=1$ , then it suffices to consider $1\leq j,k,l,m\leq n$ . Therefore, the problems transform to the same one as in (i). Consequently, the quantity of options in Cases 2 and 3 is $4n^2-8n$ and $\frac {16}{3}n^3-24n^2+\frac {80}{3}n$ , respectively. Hence, we complete the proof of (iii).
Finally, we prove (iv). The proof is divided into three cases as before. Case 1 is the same as in (iii) since it makes no difference whether n is odd or even. For Cases 2 and 3, in fact, it suffices to consider $1\leq j,k,l,m\leq n$ and thus follow the same arguments in (ii). Hence, we obtain (iv) and complete the proof of Lemma 2.
Notations Let $T_0=0$ . For any positive integer $n\geq 1$ , define
and
It is worth noting that
Lemma 3 One has
Proof Since
by Lemma 2, a direct calculation yields the assertion, as desired.
Lemma 4 Let $i,j$ be positive integers such that $1<i<j<\infty $ . Then
where C is a constant independent of $i,j$ .
Proof Observe that
Without loss of generality, we assume that i is even. Following similar arguments in the proof of Lemma 2, we obtain the following:
-
• $\mathbb {E}(||q_i||_4^4\cdot ||q_j||_4^4)=4A_i^2 A_j^2+2jA_i^2+2iA_j^2+ij+4i^2-8i+\frac {16}{3}i^3-24i^2+\frac {80}{3}i,$
-
• $\mathbb {E}(||q_i||_4^4\cdot ||q_{j-1}||_4^4)\,=\,4A_i^2 A_{j-1}^2\,+\,2(j-1)A_i^2\,+\,2iA_{j-1} ^2+i(j-1)+4i^2-8i +\frac {16}{3}i^3-24i^2+\frac {80}{3}i,$
-
• $\mathbb {E}(||q_{i-1}||_4^4\cdot ||q_j||_4^4) {\kern-1pt}={\kern-1pt}4A_{i-1}^2 A_j^2{\kern-1pt}+{\kern-1pt}2jA_{i-1}^2+2(i-1)A_j^2+(i-1)j +4(i-1)^2-8(i-1) +4+\frac {16}{3}(i-1)^3-24(i-1)^2+\frac {80}{3}(i-1)-8,$
-
• $\mathbb {E}(||q_{i-1}||_4^4\cdot ||q_{j-1}||_4^4)\, =\,4A_{i-1}^2 A_{j-1}^2\,+\,2(j-1)A_{i-1}^2+2(i-1)A_{j-1}^2+(i-1)(j-1) +4(i-1)^2-8(i-1)+4+\frac {16}{3}(i-1)^3-24(i-1)^2+\frac {80}{3}(i-1)-8.$
Therefore, we have
Bearing in mind $i<j$ , we deduce (11). A similar reasoning leads to the proof when i is odd. The proof is complete now.
3 Proof of Theorem 1
In this section we prove the main theorem. We first introduce some probabilistic tools involved in the proof of Theorem 1. The first lemma is a general method for establishing almost sure convergence, known as the method of subsequences.
Lemma 5 [Reference Stout27]
Let $\{Y_n\}_{n=1}^{\infty }$ be a sequence of random variables. Suppose that there exist a random variable Y and an increasing sequence of positive integers $\{n_k\}_{k=1}^{\infty }$ such that
and
Then
The next lemma is the so-called Serfling’s maximal inequality. Let $\{\xi _n\}_{n=1}^{\infty }$ be a sequence of random variables. For each $a\geq 0$ and $n\geq 1$ , let $F_{a,n}$ be the joint distribution function of $\xi _{a+1}, \ldots , \xi _{a+n}$ , that is,
for each $(x_1, x_2, \ldots , x_n)\in \mathbb {R}^n$ . Let
Then, Serfling’s maximal inequality provides a good upper bound for $\mathbb {E} M_{a,n}^2$ .
Lemma 6 [Reference Stout27]
Suppose that g is a nonnegative functional defined on the collection of joint distribution functions such that
for all $1\leq k<k+m$ and $a\geq 0$ ,
for all $n\geq 1$ and $a\geq 0$ . Then
for all $n\geq 1$ and $a\geq 0.$
Remark It is perhaps clear that the choice of the nonnegative functional g is the crucial part when applying Serfling’s maximal inequality.
The following lemma follows from the Chebyshev inequality and the Borel–Cantelli lemma.
Lemma 7 [Reference Stout27]
Let $\{\xi _n\}_{n=1}^{\infty }$ be a sequence of random variables. Suppose that
for some $p>0$ . Then
The following lemma provides a sufficient condition for almost sure convergence, with the main component of its proof being the Borel–Cantelli lemma.
Lemma 8 [Reference Cinlar9, Proposition 2.6, p. 98]
Suppose that
for any $\varepsilon>0$ . Then $\xi _n \rightarrow \xi $ almost surely.
Now we are ready to prove Theorem 1.
Proof of Theorem 1
Set $T_n=||q_n||_4^4/n^2$ for any positive integer n. The key to the proof is the following:
Given the above estimate, the proof can be completed by the method of subsequences as follows. By Markov’s inequality and Lemma 2, we have
which together with Lemma 8 implies
In addition, combining (12) and Lemma 7, we get
It follows from Lemma 5, (13), and (14) that
as desired.
Now it remains to prove (12). To accomplish this, we use Serfling’s maximal inequality. Recall that $X_n:= T_n-T_{n-1}$ . For each $a\geq 0$ and $n\geq 1$ , let $F_{a,n}$ be the joint distribution function of $X_{a+1}, \ldots , X_{a+n}$ , and $M_{a,n}$ be defined by
Now we need to construct an appropriate nonnegative functional g, defined on the collection of joint distribution functions, which, after some experimentation, we opt to be
Then, a direct calculation shows that the following (17) and (18) hold:
and
for all $a\geq 0$ , $1\leq k<k+m$ and $n\geq 1$ . Thus, by Lemma 6, we obtain
Bearing in mind (10) and combining (15), (16), and (19), we deduce that
Set
and
Next we show that both I and II are finite. Note that
so by Lemma 3, we get $\text {I}<\infty $ . In addition, Lemma 4 yields
which together with (20) implies (12). This completes the proof.
4 Extension for general random variables
In this section, we extend Theorem 1 to encompass a much more general case, requiring only an assumption on the fourth moment. The main new ingredient is Doob’s maximal inequality instead of Serfling’s.
Theorem 9 Let $p_n(z)=\sum _{k=0}^{n-1}\epsilon _k z^k$ , where the random variables $\{\epsilon _k, k\geq 0\}$ are independent and identically distributed, with mean $0$ , variance $\sigma ^2$ and a finite fourth moment $\mathbb {E}(\epsilon _k^4)<\infty $ . Then
almost surely.
Proof Analogous to (3), we observe that
Now we decompose $||p_n||_4^4$ into four parts. Let
That is, the indices $j,k,l$ , and m are mutually different from each other. Let
and
Then one has
By the strong law of large numbers, the last term of (22) converges to 0 almost surely. In addition, the third term of (22) converges to $2\sigma ^4$ almost surely by adding $2(\sum _{j=1}^{n} \epsilon _j^4)/n^2$ to it and applying SLLN again.
For the first two terms of (22), we observe that $\mathbb {E} B_n=0$ and a simple estimation yields
Using Markov’s inequality, we obtain
for any $\delta>0$ . Then Lemma 8 yields $B_n/n^2\rightarrow 0$ almost surely. Lastly, for the first term of (22), we observe that the sequence $\{M_n\}_{n\geq 1}$ forms a martingale with respect to the standard filtration
Using $\mathbb {E} M_n=0$ and the calculations leading to (i) and (ii) of Lemma 2, we have
For any increasing sequence of integers $\{n_k\}_{k=1}^{\infty }$ , Doob’s maximal inequality implies that for any $\delta>0$ ,
By choosing $n_k=2^k$ , we deduce that
By Lemma 8, we get
which in turn implies that $M_n/n^2\rightarrow 0$ almost surely. This completes the proof.
Acknowledgements
The authors thank the anonymous referee for a meticulous reading of the manuscript and for suggesting the second proof in Section 4.