Erdős and Szekeres [ErSz59] proved that $\lim f(n)^{1/n}=1$ and $f(n)>\sqrt{2n}$. Erdős proved an upper bound of $\log f(n) \ll n^{1-c}$ for some constant $c>0$ with probabilistic methods. Atkinson [At61] showed that $\log f(n) \ll n^{1/2}\log n$.

This was improved to\[\log f(n) \ll n^{1/3}(\log n)^{4/3}\]by Odlyzko [Od82].

If we denote by $f^*(n)$ the analogous quantity with the assumption that $a_1<\cdots<a_n$ then Bourgain and Chang [BoCh18] prove that\[\log f^*(n)\ll (n\log n)^{1/2}\log\log n.\]Atkinson [At61] noted this is related to the Chowla cosine problem [510], in that if for any set of $n$ integers $A$ there exists $\theta$ such that $\sum_{n\in A}\cos(n\theta) < -M_n$ then\[\log f^*(n) \ll M_n \log n.\]The answer to the specific question asked is no - Belov and Konyagin [BeKo96] proved that\[\log f(n) \ll (\log n)^4.\]

View the LaTeX source

This page was last edited 15 September 2025.