Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The functional equation $f(x) = (1-x)f(x^2)$ (with $f(0)=1$) has a simple solution that can be expressed as a rapidly converging infinite product $$f(x) = \prod_{n=0}^\infty (1 - x^{2^n}) = (1-x)(1-x^2)(1-x^4)(1-x^8)\cdots$$ and as a more slowly converging power series $$f(x) = \sum_{n=0}^\infty (-1)^{H(n)}x^n = 1 - x - x^2 + x^3 -\cdots,$$ where $H(n)$ is the Hamming weight of $n$ (i.e., the number of 1's in the binary representation of $n$).

Is anything known about this function $f$? Does it have a simple description in terms of more familiar functions?

share|improve this question
This function has a natural boundary on the unit circle. What "familiar function" has that? –  Gerald Edgar Feb 11 '14 at 19:20
For $x=1/2$ this gives the "Thue-Morse"-constant (or something rational tightly related) . There is a bit of discussion about it online available. –  Gottfried Helms Feb 11 '14 at 21:50
I think $1/f(x)$ gives the generating function for binary partitions. See, e.g., theory.cs.uvic.ca/inf/nump/BinaryPartition.html –  Benjamin Dickman Feb 12 '14 at 2:56

2 Answers 2

(I made this comment an answer so that the question can be "completed" by "accepting" this answer)

There is an interesting discussion around the Thue-Morse-sequence/constant in the following two articles of J. Shallit/JP Allouche, where the function in question occurs in a wider context.
See links at Jeffrey Shallit's homepage:

  • The ubiquituous Thue-Morse-Sequence (this is a postscript file and can be converted (for instance by Ghostscript) to pdf to be readable.) In the paper your formula occurs in proposition 2.
  • A powerpoint-like overview is in this pdf-file (somehow a summary, possibly an extension) of the first paper. Again you find your function discussed (in short) and referenced from a wider context (see page 36 "Another definition").

[update] I included the hint to Ghostscript due to the comments to this answer

share|improve this answer
[A non-mathematical comment] "this is a postscript file and should be converted to pdf to be readable": This is not true! You can use for instance Ghostscript (free software, available at least for Linux and Windows and I imagine for a number of other platforms too: ghostscript.com) to read the Postscript file. –  Bruno Apr 1 '14 at 8:57
:-) Yes, I'm so used to the ps to pdf-conversion by ghostscript in the background that I even forget to mention it... –  Gottfried Helms Apr 1 '14 at 9:04

I don't know, whether the following counts as "is anything known", but I found it interesting.
Consider the separation according to the Hamming weight: $$ \begin{array}{} a_0(x) &= 1 &\\ a_1(x) &= & x^1+x^2 + x^4 + x^8 + ... \\ a_2(x) &= & x^3+x^5 + x^6 + x^9 + ... \\ a_3(x) &= & x^7+x^{11} + x^{13} + x^{14} + ... \\ ... & = ... \end{array}$$ which are all convergent for $|x| \lt 1$, then $$ s_0(x) = a_0(x) +a_1(x)+a_2(x)+ ... \\ = \sum_{k=0}^\infty a_k(x) \\ = \sum_{k=0}^\infty x^k \\ = { 1 \over 1-x } \tag2$$ and $$ s_1(x) = a_0(x) -a_1(x)+a_2(x)- ... \\ = \sum_{k=0}^\infty (-1)^k a_k(x) \\ = \sum_{k=0}^\infty (-1)^{H(k)} x^k \\ = f(x) \tag3$$ I found it then interesting, that at $x=1/2$ the evaluation $a_1(1/2)$ is known to be a transcendental number. But what about the other $a_k(1/2)$ ? If I recall it correctly they are all transcendental numbers, but don't have it at hand how this has been shown; I think they might be rational multiples of each other): just (another) infinite set of transcendental numbers adding up to a rational one.

[update] If I recall correctly the $a_k(1/2)$ can be generated as rational compositions of $a_1(1/2),a_1(1/2^2),a_1(1/2^3),...$ (or very similar) applying the Newton-method of converting a sequence of powersums into symmetric polynomials. For instance, $$a_1(1/2) \approx 0.816421509022 \\ a_2(1/2) \approx 0.175061285686 \\$$ and also $$ [(a_1(1/2)^2-(a_1(1/2) -1/2) )/2,a_2(1/2)] \\ [0.175061285686, 0.175061285686] $$ using Pari/GP, reflecting the second power $(x^1 + x^2 + x^4+x^8+...)^2= 2(x^3 + x^5+x^6 + ...) + (x^2+x^4+x^8+...) \\ = 2 a_2(x)+ a_1(x^2) = 2 a_2(x)+ (a_1(x)-x) $

share|improve this answer
This follows from some results about numbers whose binary (actually arbitrary-base, but binary is the relevant case here) representations form automatic sequences ; see en.wikipedia.org/wiki/Automatic_sequence#Automatic_real_number for more pointers. (The automata for recognizing each individual sequence is fairly trivial, just a 'count-to-$k$' FSM. There's no uniform automaton that covers all the sequences, but that's irrelevant here.) –  Steven Stadnicki May 16 '14 at 21:41
Incidentally, Alpha gives $\frac{a_1(1/2)}{a_2(1/2)}$ as approximately $4.663632$, and passing that into the ISC doesn't yield anything particularly interesting. I imagine it's probably transcendental as well. Perhaps if the ratio of two automatic reals is also automatic... –  Steven Stadnicki May 16 '14 at 23:58
@Steven: in fact there should be a rational composition in terms of powers of $a_1(x)$ and thus all $a_k(1/2)$ should come out to be transcendental ; I've put that idea into my answer. –  Gottfried Helms May 17 '14 at 10:34
@Steven: the ratio gives $ \displaystyle 4.663632...= {a_1 \over a_2 } = { 2 \over a_1 -1 + {1 \over 2 a_1}}$ as a rational composition of $a_1$ and $a_1^2$ –  Gottfried Helms May 17 '14 at 18:40

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.