Skip to content

Erdős Problem #256

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: analysis.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

Documentary explanation. Editorial acceptance is determined by the protected V2 admissions ledger and the exact manuscript source hash. This article does not confer mathematical certification.

The question in plain language

Take positive integers \(a_1\leq\cdots\leq a_n\), repetitions allowed, and form the polynomial

\[ P_a(z)=\prod_{i=1}^{n}(1-z^{a_i}). \]

On the unit circle \(|z|=1\), let \(M(a_1,\ldots,a_n)\) be the largest value of \(|P_a(z)|\). Erdős and Szekeres ask how small this largest value can be when the exponents are chosen as cleverly as possible. A safe extremal definition is

\[ f(n)=\inf_{1\leq a_1\leq\cdots\leq a_n} \max_{|z|=1}\left|\prod_{i=1}^{n}(1-z^{a_i})\right|. \]

The old wording says that \(f(n)\) is “maximal” subject to being a lower bound for every tuple; Atkinson writes “greatest lower bound,” while the 1959 paper writes “minimum.” These formulations express the intended extremal quantity, but the infimum notation avoids assuming that an optimal tuple is attained.

The specific question asks whether there are constants \(c>0\) and an implicit positive constant in the comparison such that

\[ \log f(n)\gg n^c \]

as \(n\) tends to infinity. In plain language: must the smallest possible worst-case size still grow faster than every fixed power of \(n\) after taking logarithms? The answer to that specific question is no. That negative answer does not determine the true order of \(f(n)\).

It is important not to replace the original problem by its stricter cousin. The quantity \(f^*(n)\) requires \(a_1<\cdots<a_n\), so it forbids repeated exponents. Results about \(f^*(n)\) do not automatically answer the repeated-exponent problem for \(f(n)\).

A small example

A fully checkable example comes from the tuple \((a_1,a_2)=(1,2)\). Write \(z=e^{it}\) and \(x=\cos t\). Then

\[ |1-z|^2=2(1-x),\qquad |1-z^2|^2=4(1-x)(1+x), \]

so

\[ |(1-z)(1-z^2)|^2=8(1-x)^2(1+x),\qquad -1\leq x\leq 1. \]

Differentiating the last cubic shows that its interior maximum occurs at \(x=-1/3\); both endpoints give zero. Therefore

\[ \max_{|z|=1}|(1-z)(1-z^2)|=\frac{16}{3\sqrt{3}}\approx 3.079201435678004. \]

This gives the rigorous finite conclusion

\[ f(2)\leq\frac{16}{3\sqrt{3}}. \]

It is only an upper bound because \(f(2)\) is an infimum over every pair of positive integer exponents; it does not prove that \((1,2)\) is optimal. The calculation is independently reproducible from the displayed identity, and the original source records the same extremal setup. As an even simpler check, for \(n=1\) and any positive \(a_1\), the values \(z^{a_1}\) run around the unit circle, so the maximum of \(|1-z^{a_1}|\) is \(2\) and \(f(1)=2\).

What is known

The classical 1959 paper of Erdős and Szekeres proves

\[ \lim_{n\to\infty} f(n)^{1/n}=1 \]

and the general lower bound \(f(n)\geq\sqrt{2n}\). The limit says that \(f(n)\) is subexponential in \(n\) on the scale of its nth root; it does not say that \(f(n)\) is small in an absolute or polynomial sense.

The published upper-bound progression is substantial. Atkinson obtained \(\log f(n)=O(n^{1/2}\log n)\), and Odlyzko improved this to

\[ \log f(n)=O\bigl(n^{1/3}(\log n)^{4/3}\bigr). \]

Belov and Konyagin later proved, through their estimates for nonnegative trigonometric polynomials together with the relevant transfer, that

\[ \log f(n)=O\bigl((\log n)^4\bigr). \]

Since \((\log n)^4=o(n^c)\) for every fixed \(c>0\), this published result settles the specific question negatively. The current Erdős Problems page reports this conclusion and cites the 1996 paper.

For the lower side, the original \(\sqrt{2n}\) bound stood for decades. Quanyu Tang’s 2025 preprint, listed with a 2026 Proceedings of the AMS publication reference, reports the improvement \(f(n)\geq 2\sqrt n\). This strengthens what is known but remains far below the logarithmic-power upper bound. The broad question of the correct growth rate, and of substantially stronger lower bounds, is currently unresolved.

GCL's current state

The protected GCL catalogue registry binds Problem 256 to original issue #1526 and records the issue-body hash 2fc2ff3235d9cf8c357dc10a22702be054af27c9018aa8efc8fa721f65c61e7a. The complete authenticated audit is the RESULT/1 comment. It records disposition PARTIAL, preserves the pinned catalogue source at teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, and identifies the entry blob as 4e60263a80af6207aca494d2e1388e44fa372889.

That pinned entry says open, unformalized, and not formalized, with last update 2025-08-31. The live official problem page, accessed for the audit on 12 October 2026, retains the repeated-exponent statement and says that the specific superpolynomial question was answered negatively by Belov–Konyagin. Its 2025 wording edit clarifies the positive-integer domain; it does not change the mathematical issue.

GCL has no admitted Formal Conjectures statement for Problem 256 at the pinned provider snapshot. The audit’s source-normalization work and finite example are evidence for exposition, not an independently rebuilt proof. In particular, a published external theorem, a returned issue comment, and this manuscript must not be described as a GCL-certified result. No original GCL theorem is asserted here.

What remains

The yes/no question about a lower bound of the form \(\log f(n)\gg n^c\) is settled negatively by the externally published Belov–Konyagin result. The open mathematical work is finer: determine the actual scale of \(f(n)\), improve the lower bound, and reconcile the best upper and lower estimates. The gap between

\[ 2\sqrt n\leq f(n)\leq \exp\!\bigl(O((\log n)^4)\bigr) \]

is enormous, and no statement here claims that either endpoint is close to the truth.

Formalization has a separate unfinished path. A future GCL task would first need a pinned formal statement with the exact infimum, positive-integer domain, nondecreasing tuple, and repeated-exponent convention. It would then need a source-faithful formal bridge for any use of the Belov–Konyagin trigonometric-polynomial theorem. A formal statement or a finite check would not, by itself, certify the deep published argument.

Sources and claim boundaries

The pinned catalogue hash and source commit identify what was audited; they do not certify that every live page or later paper is covered by that snapshot. The mathematical claims above are attributed to their named external sources, while GCL’s state is reported only as documented evidence. Any editorial acceptance depends on the separately protected admissions ledger and the exact rendered-source verification.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1526 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: STATEMENT_CAPTURE_REQUIRED.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction