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?

Improve this question
$\endgroup$
3
  • 6
    $\begingroup$ This function has a natural boundary on the unit circle. What "familiar function" has that? $\endgroup$
    – Gerald Edgar
    Commented 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$
    – Gottfried Helms
    Commented 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$
    – Benjamin Dickman
    Commented Feb 12, 2014 at 2:56

2 Answers 2

Reset to default
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

Improve 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
    Commented 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$
    – Gottfried Helms
    Commented 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) $

Improve this answer
$\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$
    – Steven Stadnicki
    Commented 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$
    – Steven Stadnicki
    Commented 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$
    – Gottfried Helms
    Commented 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$
    – Gottfried Helms
    Commented May 17, 2014 at 18:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .