On Kahane's ultraflat polynomials (Q1024261)

The paper at hand is a serious piece of work. The topic is, unsurprisingly, Kahane's ultraflat polynomials and the authors address two main issues: improving the error term and explicit construction. The authors' main result is that for every \(\epsilon>0\) and positive integer \(N\) there is a function \(f:\{0,\dots,N\}\rightarrow S^1\) such that \[ |\widehat{f}(\theta)| = \sqrt{n} + O_\epsilon(n^{1/2-1/9 + \epsilon}) \text{ for all } \theta \in \mathbb T. \] Moreover, this functions is effectively constructable meaning that all the coefficients are given explicitly in terms of elementary fnctions and Legendre or Jacobi symbols evaluated at square-free numbers in prescribed intervals. This error term considerably improves the previous best and the problem of explicit constructability was previously unresolved. In fact the \(O_\epsilon(n^\epsilon)\) can be improved to a power of \(\log n\) if one isn't concerned about constructability and \(\exp(O(\log n / \log \log n))\) otherwise. There is an extensive introduction and plan of the paper which makes clear how the results proceed and which ingredients are involved; this is a very welcome and arguably necessary part of the paper.