15
$\begingroup$

Motivation. In a coin game, a player flips all their coins every turn, starting with just one coin. If the coins all land heads then the game stops; otherwise, the number of coins is doubled for the following turn. While the game may clearly terminate on any turn, there is in fact a positive probability that it will never terminate: this is the infinite product $$p = \prod_{i=1}^\infty \left(1-\frac{1}{2^{(2^i)}}\right).$$

Questions. Do we have $p \in \mathbb{R}\setminus \mathbb{Q}$? Is $p$ transcendental?

Improve this question
$\endgroup$
6
  • 10
    $\begingroup$ this is the Euler function $\phi(1/2)$, see oeis.org/A048651 --- I don't think it is known whether it is transcendental or not. $\endgroup$
    – Carlo Beenakker
    Commented Jan 19, 2022 at 13:47
  • 2
    $\begingroup$ As a funny recreational remark, with a certain combination of (poorly designed) cards, this probabilistic model actually occurred in the card game Magic: the Gathering: see boardgames.stackexchange.com/questions/55075/…. EDIT: whoops, not quite the same, only adding one coin every iteration, not doubling them. $\endgroup$
    – Sam Hopkins
    Commented Jan 19, 2022 at 14:16
  • 6
    $\begingroup$ @SamHopkins Actually the formula given does not match the verbal description but does match (up to replacing $2$ with another constant) the numerical formula. To actually match the verbal description it should be $\prod_{i=0}^{\infty} \left(1 -\frac{1}{2^{2^i}} \right)$. $\endgroup$
    – Will Sawin
    Commented Jan 19, 2022 at 14:26
  • 3
    $\begingroup$ @WillSawin: Ah yes, good catch! The question should be edited then! $\endgroup$
    – Sam Hopkins
    Commented Jan 19, 2022 at 14:28
  • 1
    $\begingroup$ sage: numerical_approx(prod([1-1/(2^(2^i)) for i in range(1,20)]),digits=100) 0.7003677308791392177331090539323577352841730043538435394129646772096512610737392882895636761103029328 $\endgroup$
    – Sebastien Palcoux
    Commented Jan 26, 2022 at 7:13

3 Answers 3

Reset to default
18
$\begingroup$

I can prove that the number actually described by the word problem, which is $$ \prod_{i=0}^{\infty} \left( 1- \frac{1}{2^{2^i}} \right),$$ is irrational, by a method similar to David Speyer's.

Expanding out the product, we get $$\sum_{j=0}^{\infty} \frac{(-1)^{t_j} }{2^j}= 1+\sum_{j=1}^{\infty} \frac{(-1)^{t_j} }{2^j} = \sum_{j=1}^{\infty} \frac{1}{ 2^j} + \sum_{j=1}^{\infty} \frac{(-1)^{t_j} }{2^j} = \sum_{j=1}^{\infty} \frac{1+ (-1)^{t_j} }{2^j} = \sum_{j=1}^{\infty} \frac{1+ (-1)^{t_j} }{2} \cdot 2^{1-j} $$ where $t_j$ is the number of $1$s in the binary expansion of $j$.

Thus the binary digit in the $j-1$th place is $1$ if $t_j$ is even and $0$ if $t_j$ is odd.

Since this sequence is not periodic, the number is irrational.

Improve this answer
$\endgroup$
4
  • 20
    $\begingroup$ In fact, this number is transcendental: en.wikipedia.org/wiki/… $\endgroup$
    – Emil Jeřábek
    Commented Jan 19, 2022 at 14:50
  • 1
    $\begingroup$ Brilliant, thanks Emil! And the link to the Thue-Morse sequence is amazing! $\endgroup$
    – Dominic van der Zypen
    Commented Jan 20, 2022 at 0:14
  • 4
    $\begingroup$ @DominicvanderZypen I'm a little bothered that, in your question, the verbal description and the formula don't match. Which one do you really mean? I would have assumed that the verbal description takes precedence, but if so, then it would seem that this answer by Will and Emil should be the accepted answer. $\endgroup$
    – Timothy Chow
    Commented Jan 20, 2022 at 2:46
  • $\begingroup$ You are absolutely right Timothy, will correct my error $\endgroup$
    – Dominic van der Zypen
    Commented Jan 20, 2022 at 16:20
27
$\begingroup$

This number is irrational. By Euler's pentagonal number theorem, we have $$\prod_{i=1}^{\infty} (1-2^{-i}) = 1 + \sum_{k=1}^{\infty} (-1)^k \left( 2^{-k(3k+1)/2} +2^{-k(3k-1)/2} \right).$$ This shows that the binary expansion is clearly not periodic.

I have no idea whether this number is transcendental. Your number is closely related to the value of various modular forms like the Dedekind eta function at $\tau = \tfrac{\log 2}{2 \pi} i$, so $q = \tfrac{1}{2}$. Chapter 27 of Transcendental numbers, by Murty and Rath, discusses evaluating modular forms when $\tau$ is an algebraic number, but a quick search didn't show me anything about evaluating modular forms when $q$ is algebraic.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ For posterity: this answer addresses the original version of the question, which was about the infinite product $\prod_{i=1}^{\infty} (1-\frac{1}{2^i})$. As mentioned in the comments under the question, that product also has a probabilistic interpretation, where instead of doubling the number of coins each turn, we add one one. $\endgroup$
    – Sam Hopkins
    Commented Jan 20, 2022 at 16:30
9
$\begingroup$

Q: Is $\prod_{i=1}^\infty(1-2^{-i})$ transcendental?
The question as posed originally by the OP.

A: This is the Euler function $\phi(1/2)$, see https://oeis.org/A048651 --- I don't think it is known whether it is transcendental or not [as is the case for other instances of $\phi(q)$].

Improve this answer
$\endgroup$
0

You must log in to answer this question.

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