On an example of an eventually oscillating function

This series goes back 100+ years to Hardy: "On certain oscillating series", Quarterly J. Math. 38 (1907), 269-288 (pages 146-168 in the sixth volume of Hardy's collected papers). I did not know of this when I posed the question as a puzzle on my webpage about 10 years ago (puzzle 8, solution); I thank Tanguy Rivoal for the Hardy reference. Shortly afterwards the question appeared in the Fall 2004 issue of MSRI's newsletter EMISSARY.

The easiest proof is surely the computational one that has been noted here already (and which I gave in my puzzle solution): it takes only a dozen terms of the series to confirm that $f(.995) > 1/2$, at which point the functional equation $f(x) = x - f(x^2)$ shows that $f(x) > f(.995) > 1/2$ when $x$ is a $(4^m)$-th root of $0.995$ for some $m=1,2,3,\ldots$ .

One can also give "harder" or "softer" explanations that may feel more satisfactory.

On the "hard" side, as $x \rightarrow 1$ from below the difference $f(x) - 1/2$ approaches a periodic function of $\log_4(\log(1/x))$ that's a nearly pure sine wave of magnitude $$ \frac2{\log 2} \, \bigl|\, \Gamma(\pi i / \log 2) \,\bigr| = 2 \Big/ \sqrt{\log(2)\sinh(\pi^2/\log 2)} \, = \, 0.00274922\ldots $$ (the higher harmonics' coefficients involve the values of $\Gamma$ at higher odd multiples of $\pi i / \log 2$). Hardy obtained this by residue calculations; it can also be recovered from Poisson summation.

On the "soft" side, the fact that $f(x)$ does not converge as $x \rightarrow 1$ from below is a consequence of a Tauberian theorem of Hardy and Littlewood: a subset $S$ of $\{1,2,3,\ldots\}$ has natural density iff $S$ has Abel density, and then the two limits are equal. The Abel density of $S$ is $\lim_{x \rightarrow 1-} (1-x) \sum_{s\in S} x^s$ if the limit exists. If we take $S = \bigcup_{m=0}^\infty [2^{2m}, 2^{2m+1})$ then $(1-x) \sum_{s\in S} x^s = f(x)$; but $S$ is a standard example of a set without natural density, so there's no Abel density either and we're done. Hence there is some $\epsilon > 0$ such that $|f(x) - 1/2| > \epsilon$ for a sequence of $x$'s approaching $1$, and then either $f(x)$ or $f(\sqrt x)$ eventually exceeds $1/2$. I don't know whether Hardy ever observed in print that the non-convergence of $f(x)$ is a consequence of his and Littlewood's theorem. [I found this Tauberian theorem in Persi Diaconis's doctoral thesis (Theorem 4 on p.37), with a reference to page 423 of Feller's An Introduction to Probability Theory and its Applications, Vol. II (Wiley, 1966).]

In addition to Noam Elkies and David Speyer's answers. "Harder" explanation is made somewhat "softer" in http://www.maths.bris.ac.uk/~majpk/papers/37.pdf (Summability of alternating gap series, by J.P. Keating and J.B. Reade). The starting point of the argument is the Poisson summation formula in the form $$\sum\limits_{n=-\infty}^\infty (-1)^nf(n)=\sum\limits_{n=-\infty}^\infty \hat{f}((2n+1)\pi),$$ where $\hat f$ is the Fourier transform of $f$: $$\hat f(u)=\int\limits_{-\infty}^\infty e^{iut}f(t)dt.$$ Now consider the function $$f(t)=x^{2^{|t|}}=e^{-\lambda 2^{|t|}},$$ where $\lambda$ is introduced through $x=e^{-\lambda}$. For its Fourier transform we have $$\hat f(u)=\int\limits_{-\infty}^\infty e^{iut}e^{-\lambda 2^{|t|}}dt=2\,Re\int\limits_0^\infty e^{iut}e^{-\lambda 2^{|t|}}dt= \frac{2}{\ln{2}}\,Re\frac{1}{\lambda^{iu/\ln{2}}}\int\limits_\lambda^\infty s^{(iu/\ln{2})-1}e^{-s}ds,$$ where at the last step we made a substitution $s=\lambda 2^t$. Now $$\int\limits_\lambda^\infty s^{(iu/\ln{2})-1}e^{-s}ds= \Gamma\left(\frac{iu}{\ln{2}}\right)-\int\limits_0^\lambda s^{(iu/\ln{2})-1}e^{-s}ds.$$ In the last integral we can expend $e^{-s}$ in powers of $s$ and then integrate term by term. The final result is $$\hat f(u)=\frac{2}{\ln{2}}\,Re\left[\lambda^{-iu/ln{2}}\,\Gamma\left(\frac{iu}{\ln{2}}\right)-\sum\limits_{k=0}^\infty\frac{(-1)^k}{k!}\frac{\lambda^k} {(iu/\ln{2})+k}\right].$$ Therefore the Poisson summation formula will give $$\sum\limits_{n=-\infty}^\infty (-1)^n x^{2^{|n|}}=2\sum\limits_{n=0}^\infty (-1)^n x^{2^n}-x=$$ $$\frac{2}{\ln{2}}\,Re\sum\limits_{n=-\infty}^\infty\left[\lambda^{-i(2n+1)\pi/ln{2}}\,\Gamma\left(\frac{i(2n+1)\pi}{\ln{2}}\right)-\sum\limits_{k=0}^\infty\frac{(-1)^k}{k!}\frac{\lambda^k}{(i(2n+1)\pi/\ln{2})+k}\right].$$ As $f(-t)=f(t)$, we will have $\hat f(-u)=\hat f(u)$ and hence $\hat f((-2n+1)\pi)=\hat f((2n-1)\pi)$. Therefore $$\sum\limits_{n=-\infty}^\infty \hat f((2n+1)\pi)=\sum\limits_{n=1}^\infty \hat f((-2n+1)\pi)+ \sum\limits_{n=0}^\infty \hat f((2n+1)\pi)=2\sum\limits_{n=0}^\infty \hat f((2n+1)\pi)$$ and we get finally $$\sum\limits_{n=0}^\infty (-1)^n x^{2^n}=\frac{x}{2}+$$ $$\frac{2}{\ln{2}}\,Re\sum\limits_{n=0}^\infty\left[\lambda^{-i(2n+1)\pi/ln{2}}\,\Gamma\left(\frac{i(2n+1)\pi}{\ln{2}}\right)-\sum\limits_{k=0}^\infty\frac{(-1)^k}{k!}\frac{\lambda^k}{(i(2n+1)\pi/\ln{2})+k}\right].$$ It is simple to show (see the paper) that the second term gives zero contribution in the limit $x\to 1_-$, which is equivalent to $\lambda\to 0_+$. As for the first term, introducing $$\mu=-\frac{\ln{\ln{(1/x)}}}{\ln{2}}$$ so that $\lambda=2^{-\mu}$, we will have $$\frac{2}{\ln{2}}\,Re\sum\limits_{n=0}^\infty \lambda^{-i(2n+1)\pi/ln{2}}\,\Gamma\left(\frac{i(2n+1)\pi}{\ln{2}}\right)=\frac{2}{\ln{2}}\,Re\sum\limits_{n=0}^\infty \Gamma\left(\frac{i(2n+1)\pi}{\ln{2}}\right)e^{i(2n+1)\mu\pi}.$$ The first term oscillates with the amplitude $$ \frac{2}{\ln{2}}\left|\Gamma\left(\frac{i\pi}{\ln{2}}\right)\right|=\frac{2}{\sqrt{\ln{2}\sinh{(\pi^2/\ln{2})}}}\approx 2.75\cdot 10^{-3},$$ and it is shown in the paper that the rest is bounded in modulus by $ 1.04\cdot 10^{-9}$.

As a final remark, interestingly enough the series $$\sum\limits_{n=0}^\infty (-1)^n x^{n^2}$$ converges to $1/2$ as $x\to 1_-$ (is Abel summable in contrast to the Hardy series considered above): http://www.hpl.hp.com/techreports/98/HPL-BRIMS-98-03.pdf (Abel Summability of Gap Series, by J.P. Keating and J.B. Reade).

Write $f(x) = g(t)$ where $x = \exp(-1/t)$, and $x \to 1-$ corresponds to $t \to+\infty$. Then $$ g(2t) = \exp(-1/(2t)) - g(t)$$ Thus the set of limit points of $g(t)$ as $t \to \infty$ is symmetric around $1/2$. Now $$ g(4t) = \exp(-1/(4t)) - \exp(-1/(2t)) + g(t)$$ where $\exp(-1/(4t)) - \exp(-1/(2t)) $ is a decreasing function of $t > 0$ with $0 < \exp(-1/(4t)) - \exp(-1/(2t)) < \dfrac{1}{4t}$. In particular, as soon as you get $g(t_1) > g(t_2)$ with $0 < t_1 < t_2$, you can conclude that $g(2^n t_1) - g(2^n t_2) > g(t_1) - g(t_2)$ for all positive integers $n$, and so the set of limit points has length greater than $\delta = g(t_1) - g(t_2)$. Numerically, I get $g(52) \approx .4959378605 > g(85) \approx 0.4935023615$, implying that the set of limit points includes at least the interval $((1-\delta)/2,(1+\delta)/2) \approx (.4987822505, .5012177495)$.