Formal power series with coefficient in $\{0,1 \}$ which is not rational

Recall that $f \in \mathbb{C}[[x]]$ is rational if $f = ab^{-1}$ where $a, b \in \mathbb{Q}[x]$ (the inclusion $ \mathbb{Q}[x] \to \mathbb{C}[[x]]$ is obvious).

How do I obtain an example of $f \in \mathbb{C}[[x]]$ with coefficients $0,1$ which is not rational? I have an experience of proving that some series is not rational (say, $exp(x)$).I could't come up with an example myself, though.

Solution 1:

One necessary condition for a power series to be rational is for it's image at the rational points to be rational. This is clear since for every $r\in\mathbb{Q}$ with $b(r)\neq 0$, we need to have $f(r)=a(r)/b(r)$. Since $a(x),b(x)\in\mathbb{Q}[x]$, we have $a(r),b(r)\in\mathbb{Q}$.

The transcendece of the Liouville constant (see here) (we choose $r = 10^{-1}$) thus implies that the example provided by @Arthur in the comments is an example of a non-rational power series which has only $0$'s and $1$'s

Solution 2:

This is far from my field, so please check it.

How about $\sum_{n=0}^\infty x^{2^n}$. Then its evaluation at $1/2$ has binary expansion with $1$’s only at places not at powers of two. This expansion is not periodic, even eventually, and so is not a rational number.

Solution 3:

A power series $f = \sum f_n z^n$ is rational over $\mathbb{C}$ (that is, contained in the image of $\mathbb{C}(x)$, not just $\mathbb{Q}(x)$; I think this is the standard meaning of "rational" in this context) iff the sequence $f_n$ of its coefficients satisfies a linear recurrence with constant coefficients (possibly after ignoring finitely many initial terms) iff $f_n$ has the form

$$f_n = \sum_{i=1}^k p_i(n) \lambda_i^n$$

where $p_i \in \mathbb{C}[x]$ are polynomials and $\lambda_i \in \mathbb{C}$, again possibly after ignoring finitely many initial terms. This can be proven in many ways, e.g. using partial fraction decomposition. ($f$ is rational over $\mathbb{Q}$ iff in addition $\lambda_i$ and the coefficients of $p_i$ have values in $\overline{\mathbb{Q}}$ and the sum above is closed under Galois conjugation.)

There are many obstructions to a sequence being of this form; among other things, because it satisfies a linear recurrence of fixed length $k$, any stretch of $k$ consecutive terms of the sequence uniquely determines all future terms (given the coefficients of the recurrence), and in particular if any stretch of $k$ consecutive terms is zero then all subsequent terms must be zero. This proves:

Proposition: If $f_n$ is not eventually zero but for every $k$ there are at least $k$ consecutive zeroes among the terms of $f_n$, then $f = \sum f_n z^n$ is irrational (over $\mathbb{C}$, and hence also over $\mathbb{Q}$).

A power series with this property is said to be lacunary. This implies, for example, that $\sum z^{n^2}$ is irrational as in Raffaele's deleted answer, that $\sum z^{2^n}$ is irrational as in Lubin's answer (but over $\mathbb{C}$ and not just over $\mathbb{Q}$), and that $\sum z^{n!}$ is irrational as Arthur speculates in the comments. A longer argument shows, IIRC, that lacunary power series are even transcendental (not-algebraic), in the sense that they don't satisfy a polynomial relation with coefficients in $\mathbb{C}[x]$.

Various other arguments for these power series being irrational are possible; for example you can show that if $f$ is rational and $f_n$ is 1) bounded and 2) consists of integers, then it must be eventually periodic, analogous to the eventually periodic decimal expansions of ordinary rational numbers. (Sketch: boundedness implies that $|\lambda_i| \le 1$ and that if $|\lambda_i| = 1$ then $p_i$ is constant. Integrality implies the $\lambda_i$ are algebraic and $|\lambda_i| = 1$, and then a cute argument involving the pigeonhole principle shows that this implies the $\lambda_i$ are roots of unity.)