On the Transcendence of Formal Power Series

Jean-Paul Allouche

L.R.I., Universit Paris-Sud

Algorithms Seminar

December 1, 1997

[summary by Philippe Flajolet]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).

1   Introduction

Algebraicity of generating functions (gf's) is of interest in combinatorial analysis as it is a sure sign of strong structural properties. For instance, any (unambiguous) context-free model leads to algebraic generating functions; in particular generating functions of simple families of trees and random walks (defined by a finite set of node degrees or jumps) are algebraic. In another context, the algebraic character of the gf's associated with 2-dimensional directed animals in percolation theory points to a wealth of puzzling combinatorial bijections; see [7] for a specific illustration.

Conversely, a transcendence result for the gf of a combinatorial class C means a sort of ``structural complexity lower bound'' on C. For instance, elements of C cannot be encoded by an unambiguous context-free grammar. Accordingly, if C already admits context-free descriptions, all such descriptions must be inherently ambiguous.

Methods for establishing the transcendence of generating functions fall broadly into two categories. The analytic approach is reviewed in [6]. The talk focuses on the arithmetic method, and more specifically on the following powerful approach [2, 3, 4, 10].

Principle 1  If f(z)=n fn zn has integer coefficients and is algebraic over Q(z), then its reduction (f(z)mod p):= (fn mod p) zn is algebraic over Fp(z).

Principle 2  For a series g(z)= gn zn over a finite field Fp, the following three properties are equivalent:

This is the classical ``Christol-Kamae-Mends France-Rauzy Theorem'' [4, 5], the equivalence between (i) and (ii) being due to Cobham in 1972. For instance, the Catalan gf,
f(z)=
1-(1-4z)1/2
2
=z+z2+2z3+5z4+14z5+42z6+132z7+429z8+
has a reduction modulo 2
g(z)=z+z2+z4+z8+
where the coefficient gn is 1 exactly when n=2r. Thus the coefficient sequence is computable by a finite automaton from the binary representation of the index n. It is also generated starting from the letter a by the regular substitution
a| a1,     1| 10,     0| 00.

2   Primitive words

An example originally due to Petersen serves to illustrate nicely the methods just introduced. Say that a word over some alphabet is primitive if it is not a ``power'', that is, the repetition of a shorter pattern. Thus abbab is primitive while abbabbabb is not. Let m2 be the alphabet cardinality, W(z)=(1-mz)-1 the gf of all words, and P(z) the gf of primitive words. Then, since each word has a ``root'', one has
W(z)=P(z)+P(z2)+P(z3)+,
so that, with (n) the Moebius function,
P(z)=
 
d 1
(d) W(zd),      Pn=
 
d| n
(d) mn/d.
In particular, the reduction modulo m yields
Pn
n
=(n)+A m (n) mod m.
Thus, the problem is reduced to showing that (n) is the coefficient sequence of a transcendental series.

Now, by a theorem a Cobham, if a sequence has an algebraic gf over a finite field, and if it assumes some fixed value with a limit density d, then d is a rational number. (Think of the characterization by finite automata.) But, here, (n)=1 whenever n is square-free, an event whose density is 6/p2. The transcendence of n (n)zn then follows from the irrationality of p.

Reduction modulo m thus provides a proof of the fact that the language of all primitive words cannot be an unambiguous context free language.

In the analytic perspective, transcendence results from the fact that P(z) has infinitely many poles inside the unit circle. Such poles, at points m-1/rexp(2ikp/r), arise from W(z) and the Moebius inversion formula for P(z).

3   Stanley's conjecture

In his fundamental paper of 1980 on D-finite series, Stanley [9] conjectured that the binomial series
Bt(z):=
 
n0

2n
n

t zn
is transcendental for any integers t2. Of course, we have B1(z)=1/(1-4z)1/2. In the case of even t, Bt is clearly transcendental given the presence of logarithmic elements induced by the asymptotic form of coefficients,

2n
n

2s
42s
ns
.
In addition B2 is also known to be an elliptic integral. The case of odd t is harder. An analytic proof was suggested by Flajolet [6] in 1987 and an algebraic proof was given by Woodcock and Sharif [10] in 1989.

The proof of [10] consists in reducing first Bt(z) modulo a prime p. The resulting series is algebraic, since a theorem of Furstenberg states that algebraic functions over finite fields are closed under Hadamard (termwise) products. (This property is also clear from the characterization by finite automata.) However, by means of arguments from algebraic number theory, Woodcock and Sharif are able to estimate the degree of (Bt(z)mod p) over Fp(z) and deduce that there exists an infinity of special prime values of p for which this degree grows without bound. This in turn implies the transcendence of Bt(z).

In contrast, from the analytic standpoint, it is the examination of the Puiseux expansion of Bt(z) near its singularity z=4-t that leads to the transcendence result via the arithmetic transcendence of the number p.

4   Miscellaneous examples

There are a great many cases where reduction modulo a prime leads to transcendence results for generating functions. Here are a few examples.

In [6], the language {anbv1anv2} was shown to be inherently ambiguous through transcendence of
S(z)=
 
n 1
z2n
1-2z+zn+1
,
since poles accumulate near 1/2. Alternatively, simple manipulations show that, modulo 2, the transcendence of S(z) is equivalent to the transcendence of the divisor series
D(z)=
 
n 1
zn
1-zn
=
 
n1
d(n) zn.
The latter form is transcendental over F2(z) since, upon reduction modulo 2, it is the indicator series of squares, and squares are known not to be automatic (Minsky).

A similar process applies to the Goldstine language whose gf involves the theta function Q(z)=n0 zn(n+1)/2, and to the partition series P(z)= (1-zn)-1 whose logarithmic derivative is closely related to divisor functions.

An amusing example due to Allouche, Betrema, and Shallit is the ``Bourbaki definition of integers''
, {}, {,{}}, {,{},{,{}}}, ...,
which, upon binary encoding, leads to the nonregular substitution [a| aab,   b| b]. The associated infinite word (interpret a as 0, b as 1) has a gf that is transcendental, being related to the series
D2(z)=
 
k2
z
2k-1
 
1-z
2k-1
 
,
that also shows up in a formal language example of [6].

5   Lucas sequences

The talk concludes with a description of some recent results of Allouche, Gouyou-Beauchamps, and Skordev [1]. Lucas showed that

m
n


m0
n0


m1
n1


m2
n2

mod p,
where the mj,nj are the digits of m,n in base p for prime p. More generally, following [8], define a p-Lucas sequence (p prime) by the property
apn+j an aj mod p.
For instance, the Apry numbers
An=
 
k0

n
k

2

n+k
k

2
are p-Lucas. Then, Allouche et alii characterize the strong property for a sequence to be simultaneously algebraic (automatic) over Q and p-Lucas for all large enough p. In essence, the only possibility for such a sequence is to be, up to normalization, the sequence of values of the Legendre polynomials at some rational point. In other words, the corresponding gf F(z) is of the form
F(z)=
1
(1+az+bz2)1/2
.
A particular case is the central binomial coefficient (
2n
n
). From Lucas' property and this characterization, a new proof of Stanley's conjecture can be deduced. There are also interesting extensions to Hadamard products of series involving (
2n
n
), (
3n
n
), etc.

References

[1]
Allouche (J.-P.), Gouyou-Beauchamps (D.), and Skordev (G.). -- Transcendence of binomial and Lucas's formal power series. -- Preprint, December 1997.

[2]
Allouche (Jean-Paul). -- Note on an article of H. Sharif and C. F. Woodcock: ``Algebraic functions over a field of positive characteristic and Hadamard products''. Sminaire de Thorie des Nombres de Bordeaux. Srie 2, vol. 1, n°1, 1989, pp. 163--187.

[3]
Allouche (Jean-Paul). -- Finite automata and arithmetic. In Sminaire Lotharingien de Combinatoire (Gerolfingen, 1993), pp. 1--18. -- Univ. Louis Pasteur, Strasbourg, 1993.

[4]
Christol (G.). -- Ensembles presque-priodiques k-reconnaissables. Theoretical Computer Science, vol. 9, 1979, pp. 141--145.

[5]
Christol (G.), Kamae (T.), Mends France (M.), and Rauzy (G.). -- Suites algbriques, automates et substitutions. Bulletin de la Socit Mathmatique de France, vol. 108, 1980, pp. 401--419.

[6]
Flajolet (P.). -- Analytic models and ambiguity of context--free languages. Theoretical Computer Science, vol. 49, 1987, pp. 283--309.

[7]
Gouyou-Beauchamps (D.) and Viennot (G.). -- Equivalence of the two-dimensional directed animal problem to a one-dimensional path problem. Advances in Applied Mathematics, vol. 9, n°3, 1988, pp. 334--357.

[8]
McIntosh (Richard J.). -- A generalization of a congruential property of Lucas. The American Mathematical Monthly, vol. 99, n°3, 1992, pp. 231--238.

[9]
Stanley (R. P.). -- Differentiably finite power series. European Journal of Combinatorics, vol. 1, 1980, pp. 175--188.

[10]
Woodcock (Christopher F.) and Sharif (Habib). -- On the transcendence of certain series. Journal of Algebra, vol. 121, n°2, 1989, pp. 364--369.

This document was translated from LATEX by HEVEA.