An improved lower bound for Erdős--Szekeres products

Abstract

In 1959, Erdős and Szekeres posed a series of problems concerning the size of polynomials of the form $$P_n(z)=\prod _{j=1}^n(1-z^{s_j}),$$ where $s_1,\dots ,s_n$ are positive integers. Of particular interest is the quantity $$f(n)=\underset{s_1,\dots ,s_n\ge 1}{\inf }\underset{|z|=1}{\max }|P_n(z)|.$$They proved that ${\lim }_{n\to \infty }f(n{)}^{1/n}=1$, and also established the classical lower bound $f(n)\ge \sqrt{2n}$. However, despite extensive effort over more than six decades, no stronger general lower bound had been established. In this paper, we obtain the new bound $$f(n)\ge 2\sqrt{n}.$$This gives the first improvement of the classical lower bound for the Erdős--Szekeres problem in the general case since 1959. In particular, our result confirms a remark of Billsborough et al., who observed that if the original Erdős--Szekeres proof could be fixed, the O'Hara--Rodriguez bound would yield exactly this inequality.

arXiv comment7 pages. v2: Added more references and corrected some typos