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
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
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
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
so
Differentiating the last cubic shows that its interior maximum occurs at \(x=-1/3\); both endpoints give zero. Therefore
This gives the rigorous finite conclusion
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
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
Belov and Konyagin later proved, through their estimates for nonnegative trigonometric polynomials together with the relevant transfer, that
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
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
- Erdős Problems #256 and its revision history: current statement, bibliography, and the page’s report of the negative answer to the specific question. The page is an external catalogue, not GCL proof authority.
- Erdős and Szekeres, On the product, Publ. Inst. Math. 13 (1959), 29–34: original extremal setup, \(\lim f(n)^{1/n}=1\), and \(f(n)\geq\sqrt{2n}\). The scan is the primary source used for those classical claims.
- Atkinson, On a Problem of Erdős and Szekeres, Canadian Math. Bull. 4 (1961), 7–12, especially the definition and upper-bound argument on pp. 7–12.
- Odlyzko, Minima of Cosine Sums and Maxima of Polynomials on the Unit Circle, J. London Math. Soc. 26 (1982), 412–420: the intermediate upper bound.
- Belov and Konyagin, An estimate of the free term of a non-negative trigonometric polynomial with integer coefficients, Izv. Math. 60 (1996), 1123–1182, and the MathNet record: primary source for the logarithmic-power trigonometric-polynomial estimate and the externally reported transfer to \(f(n)\).
- Tang, An improved lower bound for Erdős–Szekeres products, with the listed 2026 journal reference: later lower-bound result; the source was read as an external report, not replayed by GCL.
- GCL issue #1526 and its RESULT/1 audit: exact source packet, hash identifiers, status drift, finite check, and current GCL limitations.
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.