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.

Advertisements
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!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s