What is the Riemann surface of $y=\sqrt{z+z^2+z^4+\cdots +z^{2^n}+\cdots}$?

Truncating series is a good way to hunt for roots, you just have to do it carefully, as Micah points out. I'll show that there are at least $10$ roots in the unit disc. I would guess there are infinitely many.

Set $$f(z) = z+z^2+z^4+z^8+\cdots \quad \mbox{and} \quad f_0=z+z^2+z^4+\cdots+z^{256}$$ According to Mathematica, $|f_0(z)| > 0.066$ on $|z|=0.99.$

f0 = z + z^2 + z^4 + z^8 + z^16 + z^32 + z^64 + z^128 + z^256;
Minimize[{Abs[f0 /. z -> 0.99 E^(I*t)],  0 <= t <= 2 Pi}, t]

On the other hand, $0.99^{512} < 0.00583$ and $$|f(z)- f_0(z)| \leq |z|^{512} + |z^{1024}| + |z^{2048}| + \cdots < \sum_{k=1}^{\infty} |z|^{512 k} < 0.00583/(1-0.00583) < 0.00586.$$ So, by Rouche's theorem, $f(z)$ and $f_0(z)$ have the same number of roots inside $|z|=0.99$.

Again, according to Mathematica, $f_0(z)$ has $10$ roots inside this circle:

SortBy[Select[z /. NSolve[f0 == 0, z], Abs[#] < 0.99 &], Abs]

Namely

{0., -0.658627, 0.120315 - 0.934606 I, 0.120315 + 0.934606 I, -0.685206 - 0.670534 I,   -0.685206 + 0.670534 I, 0.184591 - 0.958351 I, 0.184591 + 0.958351 I, 0.391863 - 0.898257 I, 0.391863 + 0.898257 I}

(The SortBy command tells Mathematica how to sort the output; I ordered in increasing absolute value.) I'm not sure how you'd do this without technology, Stewart may have expected something less precise?

This answer is closer to a sketch than a proof. If you notice gaps/mistakes/nonsense in this presentation, please let me know...

We want to examine the behavior of the function $f(z)$ inside the square root. It evidently vanishes linearly at the origin. Indeed, for all $|z|<1$ this series is convergent by comparison with the geometric series. If $|z|>1$, however, the series diverges since the terms do not tend to zero. Hence the unit disk is the disk of convergence.

Compared to this straightforward picture, the behavior for $|z|=1$ is more exotic. Consider first a rational rotation, i.e. $z=e^{i\phi}$ for some $\phi\in 2\pi\mathbb{Q}$. Then $2^n\phi$ is either $0$ or $\phi$ modulo $2\pi$ for some sufficiently large integer $N$. (This is equivalent to the binary representation of any rational number eventually terminating or becoming periodic.) In the former case, it follows that $z^{2^n}=1$ for $n\geq N$. For the latter, $z^{2^n}$ is a certain periodic sequence of roots of unity; since this sequence does not include 1, the sum of each period is nonzero and identical. In both cases we may conclude that the series diverges. So every rational rotation gives a singularity.

On the other hand, if $\phi/2\pi$ is irrational, then the sequence $2^n\phi$ modulo $2\pi$ is neither periodic nor terminating: therefore the orbit of $2^n\phi$ will be dense in $[0,2\pi]$. As a consequence, the series sums to zero. So every irrational rotation corresponds to a zero.

Therefore it would appear that the unit circle is interwoven with (countably many) singularities and (uncountably many) zeroes. What does this entail for $y=\sqrt{f(z)}?$ Here my understanding goes from loose to shaky. In the standard case, each zero of $f(z)$ would be a branch point of the corresponding Riemann surface. Consequently one would seem to have a Riemann surface of (uncountably) infinite genus.

Under the (generous) assumption that this is all sound, there are questions which linger for me:

• What is the nature of the singularities at commensurate phases? (Are they poles of some multiplicity, or are they essential singularities?)
• While there are uncountably many zeroes, there is a symmetry under complex conjugation for all roots save $z=0$. Consequently the 'number' of such zeroes is even and we expect to be able to draw branch cuts between all of those on the unit circle. This leaves the branch point at zero; usually I would conclude that there will be a branch point at infinity, but I'm not sure that holds here.
• If one truncates the series expansion at some $2^n$, then the number of zeroes is finite. Most of them are in the neighborhood of the unit circle as would be expected. However, there is also a zero for some $z\in(0,1)$ (as follows from an intermediate value argument.) What happens to this negative real zero when we go to the infinite series?

This is an extended comment to the answer of Semiclassical.

The series $$f(z)=\sum_{k=0}^{\infty}z^{2^k}$$ is a canonical example of a function having natural boundary (the so-called lacunary series). Here the natural boundary is given by the unit circle $|z|=1$, inside which the series is absolutely convergent.

A more general statement is the Ostrowski–Hadamard gap theorem:

Let $\{p_k\}$ be a sequence of positive integers satisfying $\lambda p_k<p_{k+1}$ for any $k\in\mathbb{N}$ with some $\lambda>1$, and let $\{a_k\}$ be a sequence of complex numbers such that the radius of convergence of the series $f(z)=\displaystyle\sum_{k\in\mathbb{N}}a_kz^{p_k}$ is equal to $1$. Then no point on the unit circle $|z|=1$ is a regular point of $f(z)$.

The answers to these MO questions (1, 2) may also be of interest.