# Uniformly at Random

## Hadamard’s gap theorem

leave a comment »

We mentioned briefly at the end of this post that Carlson proved that a function whose power series expansion has integer coefficients and radius of convergence 1 is either rational or has a natural boundary.  A function has a natural boundary if every point on its circle of convergence is a singularity.  In particular, it cannot be analytically continued beyond its disc of convergence.

An example of a function with natural boundary is $f(z) = \sum_{n=0}^\infty z^{2^n}$.  It is enough to show that the singularities of $f$ are dense on the unit circle.  Let $k,N$ be positive integers and let $z = re^{2\pi ik/2^N}$ for some $r<1$.  Then $f(z) = \sum_{n=0}^\infty z^{2^n} = \sum_{n=0}^\infty (re^{2\pi ik/2^N})^{2^n}$ $= \sum_{n=0}^{N-1} (re^{2\pi ik/2^N})^{2^n} + \sum_{n=N}^\infty (re^{2\pi ik/2^N})^{2^n}$ $= \sum_{n=0}^{N-1} (re^{2\pi ik/2^N})^{2^n} + \sum_{n=N}^\infty r^{2^n}$.

However, $\sum_{n=N}^\infty r^{2^n}$ is unbounded as $r$ tends to 1.  Thus, $z = e^{2\pi ik/2^N}$ is a singularity of $f$ for every positive $k,N$.  This gives a dense set of singular points on the unit circle, completing the proof of the claim.

This phenomemon is captured by a general theorem of Hadamard, which states that if $\lambda >1$ is a real number and $\{b_n\}$ is a sequence of positive integers such that for all $n$, $b_{n+1} > \lambda b_n$, then $f(z) = \sum_{n=0}^\infty a_n z^{b_n}$ has a natural boundary.

A much more powerful “gap theorem” due to Fabry, replaces the condition $b_{n+1} > \lambda b_n$ with $\lim_{n\to\infty} n/b_n = 0$.  This result is capable, for instance, of establishing that $f(z) = \sum_{n=0}^\infty z^{n^2}$ has a natural boundary.

Advertisements

Written by uncudh

March 28, 2009 at 9:42 pm

Posted in math

Tagged with , ,

## Power series with integer coefficients

leave a comment »

In combinatorial enumeration one often works with generating functions.  The coefficients of the power series expansion of such a generating function are therefore integers, since they are meant to count objects of a certain size.  A curious old result of Fatou states that a function whose power series expansion has integer coefficients and radius of convergence 1 is either rational or transcendental.  This result also appears as Problem VIII.167 of Polya and Szego’s famous Aufgaben book.  We shall attempt to prove this result below.

We begin with the following particular case of Parseval’s identity.  Let $f(z) = \sum_{n=0}^\infty a_n z^n$ be a function with radius of convergence $R$.  Then for $r < R$ we have $\sum_n |a_n|^2 r^{2n} = \frac{1}{2\pi} \int_0^{2\pi} |f(re^{i\theta})|^2 d\theta.$

To see this, first let $\overline{z}$ denote the complex conjugate of $z$.  Then we have $|f(z)|^2 = f(z)\overline{f(z)} = \sum_n a_nz^n \cdot \sum_m \overline{a_m}\overline{z}^m.$

Since these series converge absolutely, we may multiply them to obtain $|f(z)|^2 = \sum_{n,m} a_n \overline{a_m} z^n \overline{z}^m$.

Writing $z = re^{i\theta}$, we have $|f(re^{i\theta})|^2 = \sum_{n,m} a_n \overline{a_m} r^{n+m} e^{i\theta(n-m)}$.

We now integrate term by term to obtain $\int_0^{2\pi} |f(re^{i\theta})|^2 d\theta = \sum_{n,m}\int_0^{2\pi} a_n \overline{a_m} r^{n+m} e^{i\theta(n-m)} d\theta.$

Observe that $\int_0^{2\pi} a_n \overline{a_m }r^{n+m} e^{i\theta(n-m)} d\theta$

equals $2\pi |a_n|^2 r^{2n}$ when $n=m$ and $0$ otherwise.  Thus, $\int_0^{2\pi} |f(re^{i\theta})|^2 d\theta = \sum_n 2\pi |a_n|^2 r^{2n}$,

which is the claimed identity.

Next, let $f(z) = \sum_{n=0}^\infty a_n z^n$ be a power series with integer coefficients such that infinitely many $a_i$ are non-zero.  We claim that if $f(z)$ is convergent in the interior of the unit disc, then it is unbounded there.

Suppose to the contrary that $f(z)$ is bounded in the interior of the unit disc.  In particular, for $r<1$, $f(z)$ is bounded on the circle of radius $r$.  Thus, the integral $\frac{1}{2\pi} \int_0^{2\pi} |f(re^{i\theta})|^2 d\theta$ is also bounded.  However, we have seen that $\frac{1}{2\pi} \int_0^{2\pi} |f(re^{i\theta})|^2 d\theta = \sum_n |a_n|^2 r^{2n},$

and, since the $a_i$ are integers, the series on the right hand side tends to infinity as $r$ tends to 1.  This contradiction proves the claim.

Now, let us suppose that $f(z) = \sum_{n=0}^\infty a_n z^n$ is a power series with integer coefficients and radius of convergence 1.  Suppose contrary to our desired conclusion that $f(z)$ is algebraic but not rational.  Then $f(z)$ satisfies an equation of the form $p_d(z) [f(z)]^d + p_{d-1}(z) [f(z)]^{d-1} + \cdots + p_1(z)f(z) + p_0(z) = 0$,

where $d > 1$ and the $p_i$ are polynomials with integer coefficients.  Since $d>1$, we can multiply through by $[p_d(z)]^{d-1}$ to obtain $[p_d(z)]^d [f(z)]^d + p_{d-1}(z) [p_d(z)]^{d-1} [f(z)]^{d-1} + \cdots + p_1(z) [p_d(z)]^{d-1} f(z) + p_0(z) [p_d(z)]^{d-1} = 0.$

Setting $y = p_d(z)f(z)$, we can rewrite this as $y^d + p_{d-1}(z) y^{d-1} + \cdots + p_1(z) [p_d(z)]^{d-2} y + p_0(z) [p_d(z)]^{d-1} = 0.$

Note that $y^d$ cannot be unbounded in the interior of the unit disc, since this term dominates the other terms of lower order in the left hand side, and if $y^d$ were to be unbounded, then the above equation could not hold.  It follows then that $y^d$ is bounded, and hence $y = p_d(z)f(z)$ is bounded.  However, $y = p_d(z)f(z)$ is a function whose power series has integer coefficients and radius of convergence 1.  We have previously seen that such a function cannot be bounded in the interior of the unit disc.  This contradiction establishes the desired result: i.e., a function whose power series expansion has integer coefficients and radius of convergence 1 is either rational or transcendental.

Polya conjectured a stronger result, namely that either the function is rational or admits the unit circle as a natural boundary (i.e., has no analytic continuation beyond the unit disc).  This was eventually proved by Carlson.

Written by uncudh

March 24, 2009 at 7:58 pm

Posted in math

Tagged with ,