Flat Littlewood polynomials exist (Q2215807)

Consider the class of Littlewood polynomials \[ P(z)= \sum_{k=0} ^n \varepsilon_k z^k,\qquad z\in\mathbb C,\qquad \varepsilon_k\in\{-1,1\}. \] In [\textit{P. Erdős}, Mich. Math. J. 4, 291--300 (1958; Zbl 0081.00102)] Erdős asked whether for every large degree \(n\) we can find a Littlewood polynomial \(P\) as above, which also satisfies \[ \delta \sqrt{n}\leq |P(z)|\leq \Delta \sqrt{n}\qquad \forall z\in\mathbb C\quad\text{with}\quad |z|=1. \] Here \(0<\delta<\Delta\) are absolute constants, in particular they are independent of the degree \(n\). Such polynomials are called flat Littlewood polynomials. It was conjectured by \textit{J. E. Littlewood} [J. Lond. Math. Soc. 41, 367--376 (1966; Zbl 0142.32603) that such flat polynomials should exist. The main result of this remarkable paper is that flat Littlewood polynomials do exist, settling this long-standing conjecture. The main contribution of the authors, and the main difficulty in the conjecture, is the construction of a Littlewood polynomial that also satisfies the lower bound. Indeed explicit Littlewood polynomials satisfying the upper bound \(\Delta\sqrt n\) have been constructed a long time ago by \textit{H. S. Shapiro} [Extremal problems for polynomials and power series. Massachusetts Institute of Technology (SM. Thesis) (1951), \url{http: //hdl.handle.net/1721.1/12198}], and \textit{W. Rudin} [Proc. Am. Math. Soc. 10, 855--859 (1959; Zbl 0091.05706)], while a non-constructive proof was given by Spencer in the 80s, [\textit{J. Spencer}, Trans. Am. Math. Soc. 289, 679--706 (1985; Zbl 0577.05018)], influenced by ideas in discrepancy theory. A detailed account of the rich history of this and related problems is given in the introduction of the paper under review, which is very informative. The strategy of proof is roughly as follows. Firstly it suffices to prove the existence of a flat Laurent-Littlewood polynomial \[ P(z)=\sum_{k=-2n} ^{2n} \varepsilon_k e^{ik\theta},\qquad z=e^{i\theta}, \] with \(n\) large. For a suitable choice of frequencies \(C\subset [2n]=\{1,2,\ldots,n\}\) this polynomial is split in the form \[ P(z)=\varepsilon_0 + 2\sum_{k\in C}\varepsilon_k \cos(k\theta)+2i \sum_{k\in [2n]\setminus C}\varepsilon_k \sin(k\theta )=:\varepsilon_0+c(\theta)+s(\theta). \] The sine polynomial \(s(\theta)\) and the cosine polynomial \(c(\theta)\) are then constructed so that they are both \(O(\sqrt{n})\) for all \(\theta\), and so that that the sine polynomial is large whenever the cosine polynomial is small. The authors construct the cosine polynomial as a modification of the Rudin-Shapiro polynomial. In particular the authors prove the existence of a suitable and well separated collection of disjoint intervals \(\mathcal I\) (the precise definition of these properties is rather technical) in \(\mathbb T=\mathbb R/ 2\pi \mathbb Z\) such that \(|c(\theta)|\geq \delta \sqrt{n}\) for all \(\theta \notin \cup_{I\in\mathcal I}I\) and \(|c(\theta)|\leq \sqrt n\) for all \(\theta\in\mathbb T\). Then the sine polynomial is constructed in the form \(s(\theta)=s_e(\theta)+s_o(\theta)\), where the even sine polynomial \(s_e\) has support on the even remaining frequencies and is small everywhere on \(\mathbb T\). The construction of the odd sine polynomial becomes the main task and the authors construct it so that it is large (\(\gtrsim \sqrt{n}\)) on each \(I\in\mathcal I\) and not too large (\(\lesssim \sqrt{n}\)) everywhere. Here the authors realize a beautiful connection with combinatorial discrepancy and use Spencer's partial colouring lemma [Spencer, loc. cit.], in its constructive reformulation by \textit{S. Lovett} and \textit{R. Meka} [SIAM J. Comput. 44, No. 5, 1573--1582 (2015; Zbl 1330.68343)]; these partial colouring results were based on a technique of \textit{J. Beck} [Combinatorica 1, 319--325 (1981; Zbl 0491.10046)]. The colouring considered is defined on the collection of intervals \(\alpha:\mathcal I\to \{-1,1\}\), and using that one can construct a step function that is large on each \(I\in\mathcal I\). Using partial Fourier series and symmetries the authors approximate this function by a sine polynomial with coefficients in \([-1,1]\). Subtle approximation arguments and a lot more work allow the authors to replace this polynomial by an odd sine polynomial with coefficients in \(\{-1,1\}\) that is still ``large'' on each \(I\in\mathcal I\) and ``small'' everywhere, thus completing the construction of the odd sine polynomial and with that the proof of the main result.