## Paul Balister, Béla Bollobás, Robert Morris, Julian Sahasrabudhe, and Marius Tiba: Flat polynomials exist!

Béla Bollobás and Paul Erdős at the University of Cambridge in 1990. Credit George Csicsery (from the 1993 film “N is a Number”) (source)

(I thank Gady Kozma for telling me about the result.)

An old problem from analysis with a rich history and close ties with combinatorics is now solved!

The paper is: Paul Balister, Béla Bollobás, Robert Morris, Julian Sahasrabudhe, and Marius Tiba,  Flat Littelwood Polynomials exist

Abstract: We show that there exist absolute constants Δ > δ > 0 such that, for all n2, there exists a polynomial P of degree n, with ±1 coefficients, such that

$\delta \sqrt n \le |P(z)| \le \Delta \sqrt n$

for all z C with |z|=1. This confirms a conjecture of Littlewood from 1966.

### A little more about the result

It is still a major open problem to replace $\delta$ by $(1-o(1))$ and $\Delta$ by $1+o(1)$ (ultra-flat polynomials).

The problem can be traced back to a 1916 paper by Hardy and Littlewood.

Shapiro (1959) and Rudin (1959) showed the existence of such polynomials when you only require $P(z) \le \Delta \sqrt n$ for all z C with |z|=1.

The new result confirms a conjecture of Littlewood from 1966 and answers a question by Erdős from 1957.

If one allows complex coefficients of absolute value one, ultra flat polynomials exist by a result of Kahane (1980). Bombieri and Bourgain (2009) gave an explicit construction with sharper bounds.

The proof relies strongly on Spencer’s famous result :”Six standard deviation suffices”.  (In fact, on a version of Spencer’s result by Lovett and Meka.)

### Six standard deviation suffices

Here is a reminder of Spencer’s theorem. (See this GLL post; We talked about it before and also on related results in Discrepancy’s theory, see this post and this one and also this one on Gowers’s blog.)

Spencer’s “Six standard deviation suffices” theorem:  If $L_i(x_1,\dots,x_n)=$ $= a_{i1} x_1 + \dots + a_{in} x_n,$ $\quad 1 \leq i \leq n,$ are $n$ linear forms in $n$ variables with all $|a_{ij}| \leq 1$, then there exist numbers $\varepsilon_1,\dots,\varepsilon_n \in \{-1,+1\}$ such that $|L_i(\varepsilon_1,\dots,\varepsilon_n)| \leq K \sqrt{n},$ for all $i$.

### My favorite (rather) flat polynomial: the determinant

The determinant thought of as a polynomial of $n^2$ variable is rather flat as far as upper bounds are concerned.  (Moreover, if you restrict yourself to matrices where the rows are orthonormal then the determinant is constant.) I will be happy to learn about  other rather-flat examples of explicit and algebraically significant polynomials. (Even on sub-varieties.)

Remark: Here is a paper by the same team on Erdős’ covering systems.

This entry was posted in Analysis, Combinatorics and tagged , , , , , . Bookmark the permalink.

### 1 Response to Paul Balister, Béla Bollobás, Robert Morris, Julian Sahasrabudhe, and Marius Tiba: Flat polynomials exist!

1. amsterguy says:

In the definition of a flat polynomial above, should P(z) be in absolute value?

GK: Indeed. Corrected, thanks!