Do random $\pm 1$ polynomials have $\sim n/2$ roots in the unit disc almost surely? (Erdős #522)
Statement
Let $(\epsilon_k)_{k\geq 0}$ be a single infinite sequence of independent random variables, each uniform on $\{-1,+1\}$, and for each $n$ let $f_n(z)=\sum_{0\leq k\leq n}\epsilon_k z^k$ (a random Littlewood/Kac polynomial with Rademacher coefficients). If $R_n$ denotes the number of roots of $f_n$ in the closed unit disc $\{z\in\mathbb{C} : \lvert z\rvert\leq 1\}$, is it true that $$\frac{R_n}{n/2}\to 1$$ almost surely? (The almost-sure statement is with respect to the joint law of the whole coefficient sequence, all $f_n$ being built from the same $\epsilon_0,\epsilon_1,\ldots$.)
Acceptance. FULLY RESOLVES: a complete proof that $R_n/(n/2)\to 1$ almost surely — machine-checkable (Lean, e.g. against the formal-conjectures statement) preferred, else a full written proof; OR a proof that almost-sure convergence fails (e.g. establishing that with probability 1 the deviations $\lvert R_n-n/2\rvert/n$ exceed some fixed $\delta>0$ along a random subsequence). ADVANCES: (a) an improved concentration bound — a proof of $\mathbb{P}(\lvert R_n-n/2\rvert\geq t_n)\leq q_n$ with $t_n=o(n^{9/10})$, or with $\sum_n q_n<\infty$ for some $t_n=o(n)$ (which yields almost-sure convergence along the full sequence via Borel–Cantelli), strictly improving the deviation bound stated in the background; (b) almost-sure convergence along explicit structured subsequences (e.g. $n=2^j$), with proof; (c) resolution of the $\{0,1\}$-coefficient variant mentioned in the background, with proof. Deliver the proof file(s).
Background
Posed by Erdős [Er61, p.252]; listed as open on erdosproblems.com/522 (fetched 2026-07-13, status 'open', tagged 'analysis | polynomials | probability'). Random polynomials with i.i.d. coefficients are called Kac polynomials; this problem is the Rademacher ($\pm 1$) case. Classical context: Erdős and Offord [EO56] showed the number of REAL roots of a random $\pm 1$ polynomial of degree $n$ is $(\tfrac{2}{\pi}+o(1))\log n$ — the real-root analogue is Erdős #521 (erdosproblems.com/521). The site notes an ambiguity over whether Erdős intended coefficients in $\{-1,1\}$ or $\{0,1\}$. The weaker in-probability version of this problem was solved by Yakir (arXiv:2011.06234, published 2021): $R_n = n/2 + O(n^{9/10})$ with probability tending to 1, i.e. $R_n/(n/2)\to 1$ in probability — precisely, $\lim_{n\to\infty}\mathbb{P}(\lvert R_n - n/2\rvert\geq n^{9/10})=0$; that weaker form was also asked by Erdős and appears in Hayman's collection [Ha67]. What remains open is exactly the upgrade from convergence in probability to almost-sure convergence. Caution: as of the fetch, the problem page's banner records an unverified claimed solution in the (login-gated) comment thread, not incorporated into the site's remarks and not corroborated in the teorth/erdosproblems AI-contributions registry or by literature search — verify the current status before investing. A Lean formalization of the statement exists in google-deepmind/formal-conjectures. The attacker's tool: proof-shaped probability — sharpen Yakir's deviation estimate to a summable-in-$n$ tail bound and combine Borel–Cantelli with coupling/interlacing between consecutive degrees to pass from subsequences to full almost-sure convergence; simulation can only illustrate.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #522 (T. F. Bloom) | website |
| REF-02 | Yakir, 'Approximately half of the roots of a random Littlewood polynomial are inside the disk' (in-probability version) | arxiv |
| REF-03 | Formalized statement of Erdős #522 (google-deepmind/formal-conjectures) | website |
| REF-04 | Erdős Problem #521 — the real-roots analogue | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.