A problem of Erdős, Herzog, and Piranian [EHP58].

The lower bound is easy: this is $\geq n$ and equality holds if and only if $p(z)=z^n$. The assumption that the set is connected is necessary, as witnessed for example by $p(z)=z^2+10z+1$.

The Chebyshev polynomials show that $n^2/2$ is best possible here. Erdős originally conjectured this without the $o(1)$ term but Szabados observed that was too strong. Pommerenke [Po59a] proved an upper bound of $\frac{e}{2}n^2$.

Eremenko and Lempert [ErLe94] have shown this is true, and in fact Chebyshev polynomials are the extreme examples.

Conjectured by Erdős, Herzog, and Piranian [EHP58]. The lower bound $\mu(A) \gg n^{-4}$ follows from a result of Pommerenke [Po61]. The stronger lower bound $\gg (\log n)^{-O(1)}$ is still open.

Wagner [Wa88] proves, for $n\geq 3$, the existence of such polynomials with \[\mu(A) \ll_\epsilon (\log\log n)^{-1/2+\epsilon}\] for all $\epsilon>0$.

The weaker conjecture that $\limsup M_n=\infty$ was proved by Wagner [Wa80], who show that there is some $c>0$ with $M_n>(\log n)^c$ infinitely often.

The second question was answered by Beck [Be91], who proved that there exists some $c>0$ such that \[\max_{n\leq N} M_n > N^c.\] The third question seems to remain open.

This was solved independently by Kristiansen [Kr74] (only in the case when $c_k\in\mathbb{R}$) and Saff and Sheil-Small [SSS73] (for general $c_k\in \mathbb{C}$).

More generally, if $A,B\subseteq \mathbb{R}$ are two countable dense sets then is there an entire function such that $f(A)=B$?

Solved by Barth and Schneider [BaSc70], who proved that if $A,B\subset\mathbb{R}$ are countable dense sets then there exists a transcendental entire function $f$ such that $f(z)\in B$ if and only if $z\in A$. In [BaSc71] they proved the same result for countable dense subsets of $\mathbb{C}$.

Clunie (unpublished) proved this if $a_n\geq 0$ for all $n$. This was disproved in general by Clunie and Hayman [ClHa64], who showed that the limit can take any value in $[0,1/2]$.

See also [513].

Originally a conjecture of Littlewood. The answer is yes (for all $n\geq 2$), proved by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST19].

See also [230].

Solved in the affirmative by Barth and Schneider [BaSc72].

The lower bound of $\sqrt{n}$ is trivial from Parseval's theorem. The answer is no (contrary to Erdős' initial guess). Kahane [Ka80] constructed 'ultraflat' polynomials $P(z)=\sum a_kz^k$ with $\lvert a_k\rvert=1$ such that \[P(z)=(1+o(1))\sqrt{n}\] uniformly for all $z\in\mathbb{C}$ with $\lvert z\rvert=1$, where the $o(1)$ term $\to 0$ as $n\to \infty$.

For more details see the paper [BoBo09] of Bombieri and Bourgain and where Kahane's construction is improved to yield such a polynomial with \[P(z)=\sqrt{n}+O(n^{\frac{7}{18}}(\log n)^{O(1)})\] for all $z\in\mathbb{C}$ with $\lvert z\rvert=1$.

See also [228].

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 $f(n) < \exp(n^{1-c})$ for some constant $c>0$ with probabilistic methods. Atkinson [At61] showed that $f(n) <\exp(cn^{1/2}\log n)$ for some constant $c>0$.

This was improved to \[f(n) \leq \exp( cn^{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 \[f^*(n)< \exp(c(n\log n)^{1/2}\log\log n).\]

A reverse Littlewood-Offord problem. Erdős originally asked this with $\sqrt{2}$ replaced by $1$, but Carnielli and Carolino [CaCa11] observed that this is false, choosing $z_1=1$ and $z_k=i$ for $2\leq k\leq n$, where $n$ is even, since then the sum is at least $\sqrt{2}$ always.

Solved in the affirmative by He, Juškevičius, Narayanan, and Spiro [HJNS24]. The bound of $1/n$ is the best possible, as shown by taking $z_k=1$ for $1\leq k\leq n/2$ and $z_k=i$ otherwise.

See also [498].

First investigated by Rényi and Rédei [Re47]. Erdős [Er49b] proved that $f(k)<k^{1-c}$ for some $c>0$. The conjecture that $f(k)\to \infty$ is due to Erdős and Rényi.

This was solved by Schinzel [Sc87], who proved that \[f(k) > \frac{\log\log k}{\log 2}.\] In fact Schinzel proves lower bounds for the corresponding problem with $P(x)^n$ for any integer $n\geq 1$, where the coefficients of the polynomial can be from any field with zero or sufficiently large positive characteristic.

Schinzel and Zannier [ScZa09] have improved this to \[f(k) \gg \log k.\]

A problem of Selfridge and Straus [SeSt58], who prove that this is true if $k=2$ and $\lvert A\rvert \neq 2^l$ (for $l\geq 0$). On the other hand, there are examples with two distinct $A,B$ both of size $2^l$ such that $A_2=B_2$.

More generally, they prove that $A$ is uniquely determined by $A_k$ if $n$ is divisible by a prime greater than $k$. Selfridge and Straus sound more cautious than Erdős, and it may well be that for all $k>2$ there exist $A,B$ of the same size with identical $A_k=B_k$.

(In [Er61] Erdős states this problem incorrectly, replacing sums with products. This product formulation is easily seen to be false, as observed by Steinerberger: consider the case $k=3$ and subsets of the 6th roots of unity corresponding to $\{0,1,2,4\}$ and $\{0,2,3,4\}$ (as subsets of $\mathbb{Z}/6\mathbb{Z}$). The correct problem statement can be found in the paper of Selfridge and Straus that Erdős cites.)

A strong form of the Littlewood-Offord problem. Erdős [Er45] proved this is true if $z_i\in\mathbb{R}$, and for general $z_i\in\mathbb{C}$ proved a weaker upper bound of \[\ll \frac{2^n}{\sqrt{n}}.\] This was solved in the affirmative by Kleitman [Kl65], who also later generalised this to arbitrary Hilbert spaces [Kl70].

See also [395].

Cartan proved this is true with $2$ replaced by $2e$, which was improved to $2.59$ by Pommerenke [Po61]. Pommerenke [Po59] proved that $2$ is achievable if the set is connected (in fact the entire set is covered by a single circle with radius $2$).

Chowla's cosine problem. The best known bound currently, due to Ruzsa [Ru04] (improving on an earlier result of Bourgain [Bo86]), replaces $N^{1/2}$ by \[\exp(O(\sqrt{\log N}).\] The example $A=B-B$, where $B$ is a Sidon set, shows that $N^{1/2}$ would be the best possible here.

Littlewood's conjecture, proved independently by Konyagin [Ko81] and McGehee, Pigno, and Smith [MPS81].

It is trivial that this value is in $[1/2,1)$. Kövári (unpublished) observed that it must be $>1/2$. Clunie and Hayman [ClHa64] showed that it is $\leq 2/\pi-c$ for some absolute constant $c>0$. Some other results on this quantity were established by Gray and Shah [GrSh63].

See also [227].

Boas (unpublished) has proved the first part, that such a path must exist.

Huber [Hu57] proved that for every $\lambda>0$ there is such a path $C_\lambda$ such that this integral is finite.

A problem of Pólya. Results of Wiman [Wi14] imply that if $(n_{k+1}-n_k)^2>n_k$ then $\limsup \frac{m(r)}{M(r)}=1$. Erdős and Macintyre [ErMa54] proved this under the assumption that \[\sum_{k\geq 2}\frac{1}{n_{k+1}-n_k}<\infty.\]

A conjecture of Fejér and Pólya. Fejér [Fe08] proved that if $\sum\frac{1}{n_k}<\infty$ then $f(z)$ assumes every value at least once, and Biernacki [Bi28] showed that this holds under the assumption that $n_k/k\to \infty$.

A problem of Turán, who proved that this maximum is $\gg 1/n$. This was solved by Atkinson [At61b], who showed that $c=1/6$ suffices. This has been improved by Biró, first to $c=1/2$ [Bi94], and later to an absolute constant $c>1/2$ [Bi00]. Based on computational evidence it is likely that the optimal value of $c$ is $\approx 0.7$.

Erdős and Offord [EO56] showed that the number of real roots of a random degree $n$ polynomial with $\pm 1$ coefficients is $(\frac{2}{\pi}+o(1))\log n$.

See also [522].

Random polynomials with independently identically distributed coefficients are sometimes called Kac polynomials - this problem considers the case of Rademacher coefficients, i.e. independent uniform $\pm 1$ values. Erdős and Offord [EO56] showed that the number of real roots of a random degree $n$ polynomial with $\pm 1$ coefficients is $(\frac{2}{\pi}+o(1))\log n$.

Solved by Yakir [Ya21], who proved that almost all such polynomials have \[\frac{n}{2}+O(n^{9/10})\] many roots in $\{ z\in \mathbb{C} : \lvert z\rvert \leq 1\}$.

See also [521].

Salem and Zygmund [SZ54] proved that $\sqrt{n\log n}$ is the right order of magnitude, but not an asymptotic.

This was settled by Halász [Ha73], who proved this is true with $C=1$.

A problem of Salem and Zygmund [SZ54]. Chung showed that, for almost all $t$, there exist infinitely many $n$ such that \[M_n(t) \ll \left(\frac{n}{\log\log n}\right)^{1/2}.\] Erdős (unpublished) showed that for almost all $t$ and every $\epsilon>0$ we have $\lim_{n\to \infty}M_n(t)/n^{1/2-\epsilon}=\infty$.

Random polynomials with independently identically distributed coefficients are sometimes called Kac polynomials - this problem considers the case of Rademacher coefficients, i.e. independent uniform $\pm 1$ values. The first problem asks whether $m(f)<1$ almost surely. Littlewood [Li66] conjectured that the stronger $m(f)=o(1)$ holds almost surely.

The answer to both questions is yes: Littlewood's conjecture was solved by Kashin [Ka87], and Konyagin [Ko94] improved this to show that $m(f)\leq n^{-1/2+o(1)}$ almost surely. This is essentially best possible, since Konyagin and Schlag [KoSc99] proved that for any $\epsilon>0$ \[\limsup_{n\to \infty} \mathbb{P}(m(f) \leq \epsilon n^{-1/2})\ll \epsilon.\] Cook and Nguyen [CoNg21] have identified the limiting distribution, proving that for any $\epsilon>0$ \[\lim_{n\to \infty} \mathbb{P}(m(f) > \epsilon n^{-1/2}) = e^{-\epsilon \lambda}\] where $\lambda$ is an explicit constant.

It is unclear to me whether Erdős also intended to assume that $\lvert a_{n+1}\rvert\leq \lvert a_n\rvert$.

It is 'well known' that, for almost all $\epsilon_n=\pm 1$, the series diverges for almost all $\lvert z\rvert=1$ (assuming only $\sum \lvert a_n\rvert^2=\infty$).

Dvoretzky and Erdős [DE59] showed that if $\lvert a_n\rvert >c/\sqrt{n}$ then, for almost all $\epsilon_n=\pm 1$, the series diverges for all $\lvert z\rvert=1$.

Bernstein [Be31] proved that for any choice of $a_i^n$ there exists $x_0\in [-1,1]$ such that \[\limsup_{n\to \infty} \sum_{1\leq i\leq n}\lvert p_{i}^n(x)\rvert=\infty.\] Erdős and Vértesi [ErVe80] proved that for any choice of $a_i^n$ there exists a continuous $f:[-1,1]\to \mathbb{R}$ such that \[\limsup_{n\to \infty} \lvert \mathcal{L}^nf(x)\rvert=\infty\] for almost all $x\in [-1,1]$.

Erdős [Er82e] writes that this was solved in the affirmative 'more than ten years ago', but gives no reference or indication who solved it. From context he seems to attribute this to Barth and Schneider [BaSc72], but this paper contains no such result.

A conjecture of Erdős from the early 1950s. Answered in the affirmative by de Bruijn [dB51].

See also [908].

A conjecture of de Bruijn and Erdős. Answered in the affirmative by Laczkovich [La80].

See also [907].

The space of rational points in Hilbert space has this property for $n=1$. This was proved for general $n$ by Anderson and Keisler [AnKe67].