Growth of $M_n(t)=\max_{x\in[-1,1]}|\sum_{k\le n}(-1)^{\epsilon_k(t)}x^k|$ for random signs (Erdős #524)
Statement
For $t\in(0,1)$ write its binary expansion $t=\sum_{k=1}^\infty \epsilon_k(t)2^{-k}$ with digits $\epsilon_k(t)\in\{0,1\}$ (for Lebesgue-almost-all $t$ the signs $(-1)^{\epsilon_k(t)}$ behave as independent fair coin flips). Define $$M_n(t)=\max_{x\in [-1,1]}\left\lvert \sum_{k\leq n}(-1)^{\epsilon_k(t)}x^k\right\rvert.$$ What is the correct order of magnitude of $M_n(t)$, as $n\to\infty$, for almost all $t\in(0,1)$? That is, determine a normalizing function $\varphi(n)$ such that almost surely $M_n(t)$ grows like $\varphi(n)$ (with matching upper and lower bounds up to constants).
Acceptance. FULLY RESOLVES: a proof determining the correct almost-sure order of magnitude of $M_n(t)$ — i.e. an explicit normalization $\varphi(n)$ together with proofs of both an upper bound ($M_n(t)\ll\varphi(n)$ for almost all $t$, in the appropriate liminf/limsup sense, clearly stated) and a matching lower bound ($M_n(t)\gg\varphi(n)$), superseding both bounds stated in the background. Machine-checkable (Lean/Coq) formalization preferred; otherwise a complete written proof with all steps. If the liminf and limsup orders differ, determining both with matching bounds also fully resolves. ADVANCES: a proof strictly improving either side of the frontier stated in the background (e.g. raising the almost-sure lower bound above $n^{1/2-\epsilon}$-type growth to an explicit $\sqrt{n}$-power with log corrections, or sharpening/extending Chung's subsequence upper bound to all $n$); or a rigorous determination of the order along an explicit subsequence; or a reproducible large-scale simulation study (code + data) estimating the empirical growth law of $M_n$ with quantified uncertainty, clearly flagged as evidence rather than proof. Deliver the proof file (or Lean sources), or the simulation code, raw data, and fitted normalization with confidence bands.
Background
A problem of Salem and Zygmund [SaZy54] on random $\pm 1$ polynomials, recorded by Erdős [Er61, p.253]; listed as open on erdosproblems.com/524 (fetched 2026-07-13, status 'open', tagged 'analysis | probability | polynomials'). The known frontier brackets the answer near $\sqrt{n}$ but does not close it: Chung proved that for almost all $t$ there exist infinitely many $n$ with $M_n(t) \ll (n/\log\log n)^{1/2}$, while Erdős (unpublished) showed that for almost all $t$ and every $\epsilon>0$ one has $M_n(t)/n^{1/2-\epsilon}\to\infty$. Note the trivial specialization $x=1$: the value there is a simple random walk $S_n=\sum_{k\le n}(-1)^{\epsilon_k(t)}$, so $M_n(t)\ge |S_n|$, which by the law of the iterated logarithm reaches order $(n\log\log n)^{1/2}$ infinitely often; the subtlety is the almost-sure behavior of the full sup over $[-1,1]$, where cancellation can make $M_n$ smaller along subsequences (Chung's bound). The gap between $n^{1/2-\epsilon}$ (below) and $n^{1/2}$-type behavior with $\log\log$ corrections (above) is exactly what remains: is $M_n(t)\asymp \sqrt{n}$, or do logarithmic factors intervene, and do liminf and limsup normalizations differ? As of the 2026-07-13 fetch the site's activity widget reports unincorporated forum claims of partial results and/or a path to a solution (11 comments), so a literature/forum check is advised before major effort. The attacker's tools: Salem–Zygmund-type chaining and sup-norm estimates for random trigonometric/algebraic polynomials for a proof, and large-scale Monte Carlo simulation of $M_n$ over random sign sequences to pin down the empirical normalization $\varphi(n)$ (including liminf/limsup separation) as evidence to guide the proof.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #524 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.