16
$\begingroup$

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?

$\endgroup$
3
  • 6
    $\begingroup$ This function has a natural boundary on the unit circle. What "familiar function" has that? $\endgroup$ Feb 11, 2014 at 19:20
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 11, 2014 at 21:50
  • 4
    $\begingroup$ I think $1/f(x)$ gives the generating function for binary partitions. See, e.g., theory.cs.uvic.ca/inf/nump/BinaryPartition.html $\endgroup$ Feb 12, 2014 at 2:56

2 Answers 2

3
$\begingroup$

(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

$\endgroup$
2
  • 2
    $\begingroup$ [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. $\endgroup$
    – Bruno
    Apr 1, 2014 at 8:57
  • 1
    $\begingroup$ :-) Yes, I'm so used to the ps to pdf-conversion by ghostscript in the background that I even forget to mention it... $\endgroup$ Apr 1, 2014 at 9:04
3
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ 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.) $\endgroup$ May 16, 2014 at 21:41
  • $\begingroup$ 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... $\endgroup$ May 16, 2014 at 23:58
  • $\begingroup$ @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. $\endgroup$ May 17, 2014 at 10:34
  • $\begingroup$ @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$ $\endgroup$ May 17, 2014 at 18:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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