# On an example of an eventually oscillating function

For $x\in(0,1)$, put $$f(x):=\sum_{n=0}^{\infty}(-1)^{n}x^{2^{n}}.$$ This function possesses interesting properties. It grows monotonically from $0$ up to certain point. Then it starts to oscillate around the value $1/2$ on a left neighborhood of $1$, see Figure 1.

So there is at least a numerical evidence that $f(x)>1/2$ for some $x\in(0,1)$, for instance $f(0.995)\dot{=}0.500882$. Nevertheless, I did not find an analytic way to prove this observation.

Thus, I have two questions concerning the function $f$.

First, I would like to ask if there is an analytic proof (simple at best $\sim$ understandable for undergraduate students) that there exists $x\in(0,1)$ such that $f(x)>1/2$.

Second, since the limit of $f(x)$ as $x\to1-$ does not exists, I would like to know at least something about the value $$\limsup_{x\to1-}f(x).$$

Many thanks.

• Stepping back from Robert Israel's answer a bit, you can use the functional relation x = f(x) + f(x^2) to produce values of f near 1/2 when x is near 1. For well chosen values of x, you might show f(x) greater than 1/2. – The Masked Avenger Feb 27 '15 at 21:59
• Hmm,I just tried to get some advantage from a reformulation for $x$ near $1$, so using $x=1-t$ and then to centralize (+ smooth) the oscillation of the result around $1/2$ by writing $g(t)=((1-t)-1) - ((1-t)^2-1)+((1-t)^4-1) - ... + ...$ and $f(x)=g(1-x)+1/2$), then expand the binomial expressions (by the powers of $(1-t)$ and collect like powers of $t$. This gives at each power of $t$ an infinite divergent series but which is alternating and can be normalized by decomposition into geometric series. This gives vanishing coefficients at the $g(t)$-series. But I've not yet arrived anywhere... – Gottfried Helms Feb 28 '15 at 14:26
• I've found heuristically more properties of $d(x)$, detailed that aspects and gave some hypothetical explanations but still cannot provide proofs. So my followup-question (and possible answeres) might be interesting. Please see here mathoverflow.net/questions/201098 – Gottfried Helms Mar 26 '15 at 4:29

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).

• Anent the "final remark": Abel summability of $\sum_{n=0}^\infty (-1)^n x^{n^k}$ for any $k=1,2,3,\ldots$ follows quickly from the easy ("Abelian") direction of the Hardy-Littlewood result I cited. The very fast convergence for $k=2$ is still remarkable (it follows from modularity of the theta function $\sum_{n=-\infty}^\infty (-1)^n q^{n^2}$). – Noam D. Elkies Feb 28 '15 at 22:13

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).]

• I am amazed with this answer. Thanks! – Bombyx mori Feb 28 '15 at 6:25
• As usual, pretty much every answer given by Noam is amazing! – Suvrit Feb 28 '15 at 17:29

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)$.

The point of this answer is to spell out the details behind Prof. Elkies statement that "If we change variables from $x$ to $\log_4(\log(1/x))$, we get in the limit an odd periodic oscillation of period 1". In other words, if we write $x = \exp(- 4^{-y})$, then, as $y \to \infty$, the function $f(x)$ approaches a periodic function.

Fix $y \in \mathbb{R}$. We'll study the limit of $f(\exp(-4^{-M-y}))$ as $M \to \infty$ through integers.

$$\begin{array}{rcl} f(\exp(4^{-M+y})) &=& \sum_{k=0}^{\infty} \exp(-4^{k-M-y}) - \exp(- 4^{k-M-y+1/2}) \\ &=& \sum_{j=-M}^{\infty} \exp(-4^{j-y}) - \exp(4^{j-y+1/2}). \\ \end{array}$$

Setting $h(y) = \exp(-4^{-y}) - \exp(-4^{-y+1/2})$, we see that $$\lim_{M \to \infty} f(\exp(4^{-M+y})) = \sum_{j=-\infty}^{\infty} h(y+j) =: g(y).$$ The function $h$ decays rapidly as $y \to \pm \infty$, so the sum converges. Here is a plot of $h$:

The function $g$ is clearly periodic, and its Fourier expansion can be found by Poisson summation. The constant term is $$\int_{-\infty}^{\infty} h(y) dy =\lim_{T \to \infty} \int_{-\infty}^{T} \exp(-4^{-y}) - \exp(-4^{1/2-y}) dy = \lim_{T \to \infty} \int_{T-1/2}^T \exp(-4^{-y}) dy = \frac{1}{2}$$ explaining why the function oscillates around $1/2$.

At this point the surprise that $\lim_{x \to 1^{-1}} f(x)$ doesn't exist turns into the extremely plausible fact that the Fourier coefficients $\int h(y) e^{(2 \pi i)k y } dy$ are nonzero. I don't see how to do the integrals in closed form, but numeric computation gives $$\int_{-\infty}^{\infty} h(y) \cos(2 \pi y) dy \approx -0.00137235.$$

Here's an unenlightening proof of part $1$, assuming you believe my computer's ability to multiply six-digit numbers correctly. If not you could do the $22$ six-digit multiplications by hand. If you run the python program below, it prints $500715$. At each step it computes integers which are lower and upper bounds to $10^6x^{2^n}$. It does the alternating sum in the pessimal way, adding lower bounds and subtracting upper bounds, for the terms $n=0$ to $n=10$. It then bounds the magnitude of the rest of the series as being less than the geometric series $x^{2^{11}}(1+x+x^2+\ldots) = \frac{x^{2^{11}}}{1-x} \leq 2x^{2^{11}}$ and subtracts an upper bound for this.

precision = int(1e6)
x = int(precision*0.995)

up = x
low = x

z = 0

for n in xrange(11):
if n % 2:
z -= up
else:
z += low
up = up*up/precision + 1
low = low*low/precision

print z - 2*up


This is more an extended comment than an answer.

I refer to your function $$f(x) = \sum_{k=0}^\infty (-1)^k x^{2^k} \qquad \qquad 0 \lt x \lt 1 \tag 1$$ and as generalization $$f_b(x)= \sum_{k=0}^\infty (-1)^k x^{b^k} \qquad \qquad 1 \lt b \tag 2$$

[update 8'2016] The same values as for the function $g(x)$ as described below one gets seemingly simply by the completing function of $f(x)$ -the sum where the index goes to negative infinity, such that, using Cesarosummation $\mathfrak C$ for the alternating divergent series in $h(x)$ , we have that $$h(x) \underset{\mathfrak C}=\sum_{k=1}^\infty (-1)^k x^{2^{-k}} \qquad \qquad \underset{\text{apparently } }{=} -g(x) \tag{2.1}$$ (Note, the index starts at $1$) .
The difference-curve $d(x)$ as shown in the pictures of my original answer below occurs then similarly by $$d(x)= h(x)+f(x) \underset{\mathfrak C}= \sum_{k=-\infty}^\infty (-1)^k x^{2^k} \tag {2.2}$$ Using the derivation provided in @Zurab Silagadze's answer I get the alternative description (using the constants $l_2=\log(2)$ and $\rho = \pi i/l_2$ ) $$d^*(x) \underset{ \lambda=\log(1/x) \\ \tau = \lambda^\rho}{=} \quad {2\over l_2 } \sum_{\begin{matrix}k=0 \\ j=2k+1 \end{matrix}}^\infty \Re\left[{\Gamma( \rho \cdot j ) \over \tau^j}\right] \tag {2.3}$$ which agrees numerically very well with the direct computation of $d(x)$.
(I don't have yet a guess about the relevance of this, though, and whether $d(x)$ has also some other, especially closed form, representation)
[end update]

To get possibly more insight into the nature of the "wobbling" I also looked at the (naive) expansion into double-series. By writing $u=\ln(x)$ and expansion of the powers of $x$ into exponential-series we get the following table: $$\small \begin{array} {r|rr|rrrrrrrrrrrrrr} +x & & +\exp(u) &&= +(& 1&+u&+u^2/2!&+u^3/3!&+...&) \\ -x^2 & & -\exp(2u)& &= -(& 1&+2u&+2^2u^2/2!&+2^3u^3/3!&+...&) \\ +x^4 & & +\exp(4u)& &= +(& 1&+4u&+4^2u^2/2!&+4^3u^3/3!&+...&) \\ -x^8 & & -\exp(8u)& &= -(& 1&+8u&+8^2u^2/2!&+8^3u^3/3!&+...&) \\ \vdots & & \vdots & \\ \hline f(x) & & ??? &g(x) &=( & 1/2 & +{1 \over1+2} u &+{1 \over1+2^2} {u^2 \over 2!} &+{1 \over1+2^3} {u^3 \over 3!} & +... &) \end{array}$$ where $g(x)$ is computed using the closed forms of the alternating geometric series along the columns.
The naive expectation is, that $f(x)=g(x)$ but which is not true. However, $$g(x)=\sum_{k=0}^\infty {(\ln x)^k\over (1+2^k) k! } \tag 3$$ is still a meaningful construct: it defines somehow a monotonuous increasing "core-function" for the wobbly function $f(x)$ , perhaps so to say a functional "center of gravity".
The difference $$d(x)=f(x)-g(x) \tag 4$$ captures then perfectly the oscillatory aspect of $f(x)$. Its most interesting property is perhaps, that it seems to have perfectly constant amplitude ($a \approx 0.00274922$) . The wavelength however is variable and well described by the transformed value $x=1-4^{-y}$ as already stated by others. With this transformation the wavelength approximates $1$ very fast and very well for variable $y$.

For the generalizations $f_b(x)$ with $b \ne 2$ the amplitude increases with $b$, for instance for $b=4$ we get the amplitude $A \approx 0.068$ and for $b=2^{0.25}$ is $a \approx 3e-12$

Here are pictures of the function $f(x)$, $g(x)$ and $d(x)= f(x)-g(x)$ :

The blue line and the magenta line are nicely overlaid over the whole range $0<x<1$ and the amplitude of the red error-curve (the $y$-scale is at the right side) seems to be constant.
In the next picture I rescaled also the x-axis logarithmically (I've used the hint from Robert Israel's anwer to apply the exponentials to base $4$):

Having the x-axis a logarithmic scale, the curve of the $d(x)$ looks like a perfect sine-wave (with a slight shift in wave-length). If this is true, then because $g(0)=1/2$ the non-vanishing oscillation of $f(x)$, focused in the OP, when $x \to 1$ is obvious because it's just the oscillation of the $d(x)$-curve...
For the more critical range near $y=0.5$ I've a zoomed picture for this:

But from here my expertise is exhausted and I've no tools to proceed. First thing would be to look at the Fourier-decomposition of $d(x)$ which might be simpler than that of $f(x)$. Possibly we have here something like in the Ramanujan-summation of divergent series where we have to add some integral to complete the divergent sums, but I really don't know.

A reference to this answer is Hardy's 'Divergent Series'. Although we do not obtain a magnitude of oscillation, the divergence of $\lim_{x\rightarrow 1-} f(x)$ follows from the following method. Here, we do not need numerical values, nor the Tauberian theorems, just a little bit of Complex Analysis.

After solving this problem, I realized that the same method applies here.

Let $f(x)=\sum_{n=0}^{\infty} (-1)^n x^{2^n}$ as given. Let $g(x)=\sum_{n=0}^{\infty} \frac{(\log x)^n}{(2^n+1)n!}$. Then $$f(x)+f(x^2)=x, \ \ g(x)+g(x^2)=x.$$ Let $\Phi(x)=f(x)-g(x)$. Then we have $$\Phi(x)=-\Phi(x^2)=\Phi(x^4).$$ If we prove that $\Phi$ is not a constant, then it follows that $\lim_{x\rightarrow 1-} f(x)$ does not exist.

Taking the principal branch of logarithm, we see that $\Phi(z)=f(z)-g(z)$ is analytic on $D=\{z: |z|<1, \ \ z\notin (-1,0]\}$.

Let $z=re^{2\pi i /3}$, and let $r\rightarrow 1-$. Then we have $$\Im(f(z))\rightarrow \infty, \textrm{ hence }|f(z)|\rightarrow\infty,$$ $$g(z) \textrm{ is bounded.}$$ Thus, $\Phi(z)$ is not a constant on $D$. Hence, $\Phi(x), \ \ 0<x<1$ is not a constant.