How to compute the series $\sum_{n=0}^\infty q^{n^2}$?

Let $q\in (0,1)$. Is there a way of computing the series $$\sum_{n=0}^\infty q^{n^2}$$ explicitly? Is there at least a nice accurate estimate?

All I could get is the estimate $$\sqrt{\frac{\pi}{4\cdot\mathrm{ln}\frac{1}{q}}}\leq\sum_{n=0}^\infty q^{n^2}\leq 1+\sqrt{\frac{\pi}{4\cdot\mathrm{ln}\frac{1}{q}}}$$ via integration (quite possibly flawed).

For $q=\frac{1}{2}$, Maple gives the values $$1.064467020\leq 1.564468414\leq 2.064467020,$$ showing that my estimate is not very precise. (Of course, the sum of the two errors will always be $1$. Here both errors are coincidentally almost exactly $\frac{1}{2}$.)

-
Are you sure it's a coincidence? I wouldn't be surprised if the average of your two estimates was accurate for small q and you can probably use Euler-Maclaurin to prove it. Alternately, this is a theta function, and the literature on theta functions is vast. – Qiaochu Yuan Mar 2 '11 at 17:43
You're probably aware that this is related to theta functions en.wikipedia.org/wiki/Theta_function You can thus be pretty sure that there are good estimates in the literature. – t.b. Mar 2 '11 at 17:43
The series itself is obviously very quickly converging and using a partial sum gives a good estimate. You can use the identity $\theta(-1/\tau) = (-i\tau)^{1/2}\theta(\tau)$ where $\theta(\tau) = \sum_{n=-\infty}^\infty q^{n^2}$ with $q=e^{\pi i \tau}$ to move $q$ near $1$ to near $0$ to get faster convergence for those more slowly convergent points. – Apollo Mar 2 '11 at 18:22
If you want some reassurance about the two errors always being very close to $1/2$ before you sit down and do the dirty work of proving it, try some different values of $q$. – Michael Lugo Mar 2 '11 at 18:41

As Qiaochu says, the Euler-Maclaurin formula is useful here. It gives the error in the approximation

$$\sum_{n=0}^{\infty} q^{n^2} \approx \sqrt{\frac{\pi}{4 \log (1/q)}} + \frac{1}{2}$$

to be exactly

$$\lim_{a \to \infty} \int_0^a 2xq^{x^2} (\log q) \left(x - \lfloor x \rfloor - \frac{1}{2}\right) dx.$$

Since $q^{x^2} \to 0$ quite rapidly, the value of this integral can be approximated closely by using small values of $a$.

For example, if $q = 1/2$, the integral (i.e., the error in the approximation) evaluates to $1.39417 \times 10^{-6}$ (via Mathematica).

-

$\theta_3(q)=\sum_{n=-\infty}^\infty q^{n^2}$ where $q=e^{-\pi s}$ and since, for $Re(s)>0,$

$$\sqrt{s} \theta_ 3(e^{-\pi s}) = \theta_3(e^{-\pi/s})$$

we have

$$\sum_{n=0}^\infty q^{n^2} = \sqrt{ \frac{\pi} {4 \log \left( \frac{1}{q} \right) } } \theta_3(e^{-\pi/s}) + \frac12.$$

But if $s$ is small then $e^{-\pi/s}$ is large and so $\theta_3(e^{-\pi/s}) \approx 1,$ and hence you obtain the result you noticed:

$$\sum_{n=0}^\infty q^{n^2} \approx \sqrt{ \frac{\pi} {4 \log \left( \frac{1}{q} \right) } } + \frac12.$$

For greater accuracy take more terms in the sum defining $\theta_3(e^{-\pi/s}).$

-
Could you please explain, how to see your first (centered) equation and why we can assume that $s$ is small? Doesn't $s$ being small imply $q$ being closed to $1$? I am interested in the general case $q\in (0,1)$. – Rasmus Mar 3 '11 at 11:27
@Rasmus: Just note that $\sum_{n=-\infty}^\infty q^{n^2} = \frac12 (\theta_3(q)+1)$ and $\theta_ 3(e^{-\pi s}) = \frac{1}{\sqrt{s}}\theta_3(e^{-\pi/s})$ where $s= - \frac{1}{\pi} \log(q),$ since $q=e^{-\pi s}.$ Yes, $s$ being small does imply that we are close-ish to $1$ but that's why we make the transformation to accelerate the convergence and make sure that we sum the series with a $q^\prime \in (0,e^{-\pi}]$ so it will converge rapidly. – Derek Jennings Mar 3 '11 at 14:01
@Rasmus: That first sum in my previous comment should, of course, say $\sum_{n=0}^\infty ...$ – Derek Jennings Mar 3 '11 at 15:07
I meant to ask why $$\sqrt{s} \theta_ 3(e^{-\pi s}) = \theta_3(e^{-\pi/s}).$$ Sorry for asking imprecisely. – Rasmus Mar 3 '11 at 15:11
@Rasmus: It's because $\theta_3$ is an entire modular form: en.wikipedia.org/wiki/Modular_form – Derek Jennings Mar 3 '11 at 15:24

The comment above, pointing out that the partial sums converge quickly, suggests you can improve your estimate nicely by using a bound for $R_n$, the remainder after the nth partial sum, given by the integral of $q^{x^2}$: $$R_n = \int_n^\infty q^{x^2}\, dx = \sqrt{ \frac{\pi}{2\ln(1/q)}} ( 1- \mathrm{erf}( n \sqrt{\ln(1/q)}))$$

Even taking only $n=3$, for example, gives (for $q=1/2$) $$0.56401 < \sum_{n=1}^{\infty} q^{x^2} < 0.56489$$

-

An elementary lower bound can be found using the four square theorem. Let

$$f(q)=\sum_{n=0}^\infty {q^{n^2}}$$. Then:

$$f(q)^4 = \sum_{n=0}^\infty {a_n q^n}$$

Where $a_n$ is the number of ways of expressing $n$ as the sum of four squares.

We know that $a_n \geq 4$ if $n>0$, so when $0<q<1$,

$$f(q)^4 > 1 + 4q + 4q^2 + ... = 4/(1-q) - 3 = \frac{3q+1}{1-q}$$

So $$f(q) > {(\frac{3q+1}{1-q})}^{\frac{1}{4}}$$

When $q=\frac{1}{2}$, this gives a lower bound of $5^{\frac{1}{4}} \approx 1.493$

Edit: Of course, that's pretty ridiculous, because it is trivially true that $f(q)>1+q$.

-