Integers: Store exactly using binary representation.

$$ 26 \leftrightarrow 11010 $$

Rationals: Store as pair of integers.

$$ \frac{2}{3} \leftrightarrow (2,3) $$

Algebraic Numbers (roots of polys in \(\mathbb{Z}[x]\)): Store implicitly 
using an integer polynomial and numeric information.

$$\sqrt{2} \quad\leftrightarrow\quad p(x)=x^2-2 \;\;\text{ and }\;\; x>0 $$

Some algebraic numbers cannot be represented exactly.

We use mathematical tools to manipulate algebraic numbers implicitly through their defining polynomials.

Some algebraic numbers cannot be represented exactly.

We use mathematical tools to manipulate algebraic numbers implicitly through their defining polynomials.

The Resultant

If \(f,g \in A[y]\) then \(\text{resultant}_y(f,g) \in A\) equals \(0\) if and only if \(f\) and \(g\) share a root.

Some algebraic numbers cannot be represented exactly.

We use mathematical tools to manipulate algebraic numbers implicitly through their defining polynomials.

The Resultant

If \(P(\alpha)=0\) and \(Q(\beta)=0\) then \(R(\alpha+\beta)=0\) where

$$ R(x) = \text{resultant}_y(P(x-y),Q(y))$$

Some algebraic numbers cannot be represented exactly.

We use mathematical tools to manipulate algebraic numbers implicitly through their defining polynomials.

The Resultant

If \(P(\alpha)=0\) and \(Q(\beta)=0\) then \(R(\alpha+\beta)=0\) where

$$ R({\color{lightblue}\alpha+\beta}) = \text{resultant}_y(P({\color{lightblue}\alpha+\beta}-y),Q(y))$$

Some algebraic numbers cannot be represented exactly.

We use mathematical tools to manipulate algebraic numbers implicitly through their defining polynomials.

The Resultant

If \(P(\alpha)=0\) and \(Q(\beta)=0\) then \(R(\alpha+\beta)=0\) where

$$ R(x) = \text{resultant}_y(P(x-y),Q(y))$$

Some algebraic numbers cannot be represented exactly.

We use mathematical tools to manipulate algebraic numbers implicitly through their defining polynomials.

The Resultant

If \(P(\alpha)=0\) and \(Q(\beta)=0\) then \(R(\alpha \,{\color{lightblue}-}\, \beta)=0\) where

$$ R(x) = \text{resultant}_y(P(x \,{\color{lightblue}+}\, y),Q(y))$$

Some algebraic numbers cannot be represented exactly.

We use mathematical tools to manipulate algebraic numbers implicitly through their defining polynomials.

The Resultant

If \(P(\alpha)=0\) and \(Q(\beta)=0\) then \(R(\alpha \,{\color{lightblue}/}\, \beta)=0\) where

$$ R(x) = \text{resultant}_y(P(x \,{\color{lightblue}\cdot}\, y),Q(y))$$

Some algebraic numbers cannot be represented exactly.

We use mathematical tools to manipulate algebraic numbers implicitly through their defining polynomials.

The Resultant

If \(P(\alpha)=0\) and \(Q(\beta)=0\) then \(R(\alpha \,{\color{lightblue}\cdot}\, \beta)=0\) where

$$ R(x) = \text{resultant}_y({\color{lightblue}y^d}P(x \,{\color{lightblue}/}\, y),Q(y))$$

Theorem (Ramanujan)

$$ \frac{\sin\left(\frac{2\pi}{7}\right)}{\sin\left(\frac{3\pi}{7}\right)^2} - \frac{\sin\left(\frac{\pi}{7}\right)}{\sin\left(\frac{2\pi}{7}\right)^2} + \frac{\sin\left(\frac{3\pi}{7}\right)}{\sin\left(\frac{\pi}{7}\right)^2} = 2\sqrt{7}$$

Exercise 6.7 in Algorithmes Efficaces en Calcul Formel by Bostan et al. (2017)

Theorem (Ramanujan)

$$ \frac{\sin\left(\frac{2\pi}{7}\right)}{\sin\left(\frac{3\pi}{7}\right)^2} - \frac{\sin\left(\frac{\pi}{7}\right)}{\sin\left(\frac{2\pi}{7}\right)^2} + \frac{\sin\left(\frac{3\pi}{7}\right)}{\sin\left(\frac{\pi}{7}\right)^2} = 2\sqrt{7}$$

Note: \(\sin(\theta) = \frac{e^{i\theta}-e^{-i\theta}}{2i}\) is algebraic if \(\theta\) is a rational multiple of \(\pi\).

Exercise 6.7 in Algorithmes Efficaces en Calcul Formel by Bostan et al. (2017)

Theorem (Ramanujan)

$$ \frac{\sin\left(\frac{2\pi}{7}\right)}{\sin\left(\frac{3\pi}{7}\right)^2} - \frac{\sin\left(\frac{\pi}{7}\right)}{\sin\left(\frac{2\pi}{7}\right)^2} + \frac{\sin\left(\frac{3\pi}{7}\right)}{\sin\left(\frac{\pi}{7}\right)^2} = 2\sqrt{7}$$

Exercise 6.7 in Algorithmes Efficaces en Calcul Formel by Bostan et al. (2017)

$$-\frac{i \, x^{2} - \frac{i}{x^{2}}}{2 \, {\left(-\frac{1}{2} i \, x^{3} + \frac{i}{2 \, x^{3}}\right)}^{2}} + \frac{i \, x - \frac{i}{x}}{2 \, {\left(-\frac{1}{2} i \, x^{2} + \frac{i}{2 \, x^{2}}\right)}^{2}} - \frac{i \, x^{3} - \frac{i}{x^{3}}}{2 \, {\left(-\frac{1}{2} i \, x + \frac{i}{2 \, x}\right)}^{2}}$$

Exercise 6.7 in Algorithmes Efficaces en Calcul Formel by Bostan et al. (2017)

Theorem (Ramanujan)

$$ \frac{\sin\left(\frac{2\pi}{7}\right)}{\sin\left(\frac{3\pi}{7}\right)^2} - \frac{\sin\left(\frac{\pi}{7}\right)}{\sin\left(\frac{2\pi}{7}\right)^2} + \frac{\sin\left(\frac{3\pi}{7}\right)}{\sin\left(\frac{\pi}{7}\right)^2} = 2\sqrt{7}$$

The theorem then follows from checking that the left-hand side is positive.

Now suppose we have a sequence \((f_n)=f_0,f_1,\dots\) which could
 

• count objects in a combinatorial class

• capture the probability that an event occurs

• track the runtime of an algorithm

Goal: Say something interesting about the sequence.

Nice exact formulas do not always exist — and even if they do they can be hard to find and prove.

A. Cayley. A Theorem on Trees. Quart. J. Pure Appl. Math. Vol 23, 376–378, 1889.

Gathering data can be useful for studying sequences, and conjecturing formulas, but doesn’t fully capture behaviour.

$$ \text{\# unlabelled graphs on \(n\) nodes } \sim \frac{2^\binom{2n}{n}}{n!}$$

$$ \text{\# partitions of } n \sim \frac{n^{-1}}{4\sqrt{3}}\exp\left(\pi\sqrt{\frac{2n}{3}}\right) $$

Instead focus on approximating \(f_n\) as \(n\rightarrow\infty\).

$$ \text{\# unlabelled graphs on \(n\) nodes } \sim \frac{2^\binom{2n}{n}}{n!}$$

$$ \text{\# partitions of } n \sim \frac{n^{-1}}{4\sqrt{3}}\exp\left(\pi\sqrt{\frac{2n}{3}}\right) $$

Conjecture (Wilf 1982): There is no polynomial time algorithm to enumerate unlabelled graphs exactly.

Instead focus on approximating \(f_n\) as \(n\rightarrow\infty\).

We encode a sequence \((f_n)\) using its generating function

$$F(z) = \sum_{n \geq 0}f_nz^n = f_0 + f_1z + f_2z^2 + \cdots$$

A generating function is a formal object. It represents* a complex function when \(f_n\) grows at most exponentially.
 

We encode a sequence \((f_n)\) using its generating function

$$F(z) = \sum_{n \geq 0}f_nz^n = f_0 + f_1z + f_2z^2 + \cdots$$

A generating function is a formal object. It represents* a complex function when \(f_n\) grows at most exponentially.

Example
The series \(\displaystyle\sum_{n \geq 0}n!\, z^n\) converges only when \(z=0\).

The series \(\displaystyle\sum_{n \geq 0}2^n\, z^n\) converges when \(|z|<1/2\).

A combinatorial class consists of

such that there are a finite number of objects of any size.

• a set of objects \(\mathcal{C}\)
• a size function \(|\cdot|:\mathcal{C}\rightarrow\mathbb{N}\)

A combinatorial class consists of

such that there are a finite number of objects of any size.

Example

The set of binary strings \(\mathcal{C}=\{\epsilon,0,1,00,01,\dots\}\) with size given by length is a combinatorial class.


 

• a set of objects \(\mathcal{C}\)
• a size function \(|\cdot|:\mathcal{C}\rightarrow\mathbb{N}\)

A combinatorial class consists of

such that there are a finite number of objects of any size.

Example

The set of binary strings \(\mathcal{C}=\{\epsilon,0,1,00,01,\dots\}\) with size given by length is a combinatorial class.

Non-Example
The set of binary strings with size given by number of zeroes is not a combinatorial class as \(|\epsilon|=|1|=|11|=\cdots\)
 

• a set of objects \(\mathcal{C}\)
• a size function \(|\cdot|:\mathcal{C}\rightarrow\mathbb{N}\)

The counting sequence of a class \(\mathcal{C}\) is the sequence \((c_n)\) where \(c_n = \#\) objects in \(\mathcal{C}\) with size \(n\).

The generating function of \((\mathcal{C},|\cdot|)\) is

$$C(z) = \sum_{n \geq 0}c_nz^n = \sum_{\sigma \in \mathcal{C}}z^{|\sigma|}. $$

Example
The generating function for the class of binary strings with size given by length is

$$C(z) = 1 + 2z + 4z^2 + \cdots = \frac{1}{1-2z}. $$

The generating function for rolls of two standard dice with size given by sum of dots is
 

$$ P(z) = (z+z^2+z^3+z^4+z^5+z^6)^2.$$

The generating function for rolls of two standard dice with size given by sum of dots is
 

$$ P(z) = (z+z^2+z^3+z^4+z^5+z^6)^2.$$

Generating functions let us use mathematical methods to study combinatorial objects.

The generating function for rolls of two standard dice with size given by sum of dots is
 

$$ P(z) = (z+z^2+z^3+z^4+z^5+z^6)^2.$$

Generating functions let us use mathematical methods to study combinatorial objects.

By manipulating the factors we find that
 

$$\begin{aligned}P(z) &= {\Big(}z(z+1)(z^2+z+1){\Big)}{\Big(}z(z+1)(z^2+z+1)(z^2-z+1)^2{\Big)}\end{aligned}$$

By manipulating the factors we find that
 

$$\begin{aligned}P(z) &= {\Big(}z(z+1)(z^2+z+1){\Big)}{\Big(}z(z+1)(z^2+z+1)(z^2-z+1)^2{\Big)}\\[+5mm]&= {\Big(}z+2z^2+2z^3+z^4{\Big)}{\Big(}z+z^3+z^4+z^5+z^6+z^8{\Big)}\end{aligned}$$

By manipulating the factors we find that
 

$$\begin{aligned}P(z) &= {\Big(}z(z+1)(z^2+z+1){\Big)}{\Big(}z(z+1)(z^2+z+1)(z^2-z+1)^2{\Big)}\\[+5mm]&= {\color{salmon}{\Big(}z+2z^2+2z^3+z^4{\Big)}}{\color{lightblue}{\Big(}z+z^3+z^4+z^5+z^6+z^8{\Big)}}\end{aligned}$$

George Sicherman, Letter to Martin Gardiner (January 1977)

By manipulating the factors we find that
 

$$\begin{aligned}P(z) &= {\Big(}z(z+1)(z^2+z+1){\Big)}{\Big(}z(z+1)(z^2+z+1)(z^2-z+1)^2{\Big)}\\[+5mm]&= {\color{salmon}{\Big(}z+2z^2+2z^3+z^4{\Big)}}{\color{lightblue}{\Big(}z+z^3+z^4+z^5+z^6+z^8{\Big)}}\end{aligned}$$

George Sicherman, Letter to Martin Gardiner (January 1977)

Gallian & Rusin, Discrete Math (1979)
Broline, Mathematics Magazine (1979)

How can we find algebraic/differential/function equations satisfied by a generating function?

There are many domain specific methods (integer partitions, lattice path models, maps, permutations, etc.)

How can we find algebraic/differential/function equations satisfied by a generating function?

There are many domain specific methods (integer partitions, lattice path models, maps, permutations, etc.)

Can also build generating functions recursively.

Atomic Class: \(\mathcal{Z}\) has 1 object of size 1 and GF \(z\)
 

Neutral Class: \(\mathcal{E}\) has 1 objects of size 0 and GF \(1\)

Example

A (rooted planar) binary tree is either empty or is a root vertex followed by a left binary tree and a right binary tree.

A C-finite sequence \((f_n)\) satisfies a linear recurrence

$$ f_n + c_1f_{n-1} + \cdots + c_rf_{n-r}=0 \qquad (\star)$$
for all \(n \geq r\) where \(c_1,\dots,c_r\in\mathbb{Q}\).


Example
The Virahanka-Fibonacci numbers \((f_n)\) satisfy

$$ f_n - f_{n-1} - f_{n-2} = 0 \qquad (n \geq 2) $$
together with the initial conditions \(f_0=f_1=1\).

A C-finite sequence \((f_n)\) satisfies a linear recurrence

$$ f_n + c_1f_{n-1} + \cdots + c_rf_{n-r}=0 \qquad (\star)$$
for all \(n \geq r\) where \(c_1,\dots,c_r\in\mathbb{Q}\).

Theorem 
\((f_n)\) is C-finite if and only if its GF \(F(z)\) is rational

A. de Moivre, The Doctrine of Chances or a Method of Calculating the Probabilities of Events in Play, 1718.

A C-finite sequence \((f_n)\) satisfies a linear recurrence

$$ f_n + c_1f_{n-1} + \cdots + c_rf_{n-r}=0 \qquad (\star)$$
for all \(n \geq r\) where \(c_1,\dots,c_r\in\mathbb{Q}\).

Theorem  
\((f_n)\) satisfies \((\star)\) if and only if

$$F(z) = \sum_{n \geq 0}f_nz^n = \frac{G(z)}{H(z)} = \frac{g_0 + g_1z + \cdots + g_{r-1}z^{r-1}}{1 + c_1z + \cdots + c_rz^r}$$
with \( g_k = f_k + c_1f_{k-1} + \cdots + c_rf_{k-r}\) (define \(f_k=0\) if \(k<0\)).

A C-finite sequence \((f_n)\) satisfies a linear recurrence

$$ f_n + {\color{red}c_1}f_{n-1} + \cdots + {\color{red}c_r}f_{n-r}=0 \qquad (\star)$$
for all \(n \geq r\) where \(c_1,\dots,c_r\in\mathbb{Q}\).

Theorem  
\((f_n)\) satisfies \((\star)\) if and only if

$$F(z) = \sum_{n \geq 0}f_nz^n = \frac{G(z)}{{\color{red}H(z)}} = \frac{g_0 + g_1z + \cdots + g_{r-1}z^{r-1}}{{\color{red}1 + c_1z + \cdots + c_rz^r}}$$
\(H\) depends only on the coefficients \(c_1,\dots,c_r\) in \((\star)\)

A C-finite sequence \((f_n)\) satisfies a linear recurrence

$$ f_n + c_1f_{n-1} + \cdots + c_rf_{n-r}=0 \qquad (\star)$$
for all \(n \geq r\) where \(c_1,\dots,c_r\in\mathbb{Q}\).

Theorem  
\((f_n)\) satisfies \((\star)\) if and only if

$$F(z) = \sum_{n \geq 0}f_nz^n = \frac{{\color{lightgreen}G(z)}}{H(z)} = \frac{{\color{lightgreen}g_0 + g_1z + \cdots + g_{r-1}z^{r-1}}}{1 + c_1z + \cdots + c_rz^r}$$
 

\(G\) depends on the \(c_i\) and \(f_0,\dots,f_{r-1}\) 

A C-finite sequence \((f_n)\) satisfies a linear recurrence

$$ f_n + c_1f_{n-1} + \cdots + c_rf_{n-r}=0 \qquad (\star)$$
for all \(n \geq r\) where \(c_1,\dots,c_r\in\mathbb{Q}\).

Theorem  
\((f_n)\) satisfies \((\star)\) if and only if

$$F(z) = \sum_{n \geq 0}f_nz^n = \frac{G(z)}{H(z)} = \frac{g_0 + g_1z + \cdots + g_{r-1}z^{r-1}}{1 + c_1z + \cdots + c_rz^r}$$
If \(G\) and \(H\) are coprime a root of \(H\) is a singularity of \(F\).

Write \(H(z) = C(z-\lambda_1)^{d_1}\cdots(z-\lambda_s)^{d_s}\) with the \(\lambda_k\) distinct and non-zero.
 

Partial Fraction Decomposition

There exist constants \(C_{i,j}\) such that

$$ F(z) = \sum_{i=1}^s \sum_{j=1}^{d_i} \frac{C_{i,j}}{(1-z/\lambda_i)^j} $$

Write \(H(z) = C(z-\lambda_1)^{d_1}\cdots(z-\lambda_s)^{d_s}\) with the \(\lambda_k\) distinct and non-zero.

Partial Fraction Decomposition

There exist constants \(C_{i,j}\) such that

$$ F(z) = \sum_{i=1}^s \sum_{j=1}^{d_i} \frac{C_{i,j}}{(1-z/\lambda_i)^j} $$

Negative Binomial Theorem

For any \(n\in\mathbb{N}\),
$$[z^n](1-z/\lambda)^{-j} = \lambda^{-n} \binom{n+j-1}{j-1} = \lambda^{-n} \; \frac{(n+j-1)\cdots(n+1)}{(j-1)!}$$

Corollary
If \((f_n)\) satisfies the C-finite recurrence \((\star)\) then

$$f_n = p_1(n)\lambda_1^{-n} + \cdots + p_s(n)\lambda_s^{-n}$$
for all \(n \geq 0\) where the \(\lambda_i\) are the distinct roots of the characteristic polynomial
 

$$ H(z) = 1 + c_1 + \cdots + c_rz^r$$
and \(p_i(n)\) is a polynomial in \(n\) of degree at most \(d_i-1\).

$$\frac{1}{2}\left(1 + \frac{1}{\sqrt{5}}\right)\left(\frac{1+\sqrt{5}}{2}\right)^n + \frac{1}{2}\left(1 - \frac{1}{\sqrt{5}}\right)\left(\frac{1-\sqrt{5}}{2}\right)^n$$

Conway's Look-and-Say Sequence

$$(\ell_n) = 1, 11, 21, 1211, \dots$$
If \(d_n\) denotes the number of (base 10) digits of \(\ell_n\) then Conway proved \(d_n\) has a rational GF.

Conway's Look-and-Say Sequence

$$(\ell_n) = 1, 11, 21, 1211, \dots$$
If \(d_n\) denotes the number of (base 10) digits of \(\ell_n\) then Conway proved \(d_n\) has a rational GF.

Conway's Look-and-Say Sequence

$$(\ell_n) = 1, 11, 21, 1211, \dots$$
If \(d_n\) denotes the number of (base 10) digits of \(\ell_n\) then Conway proved \(d_n\) has a rational GF.

Recall that \(f_n = p_1(n)\lambda_1^{-n} + \cdots + p_s(n)\lambda_s^{-n}\).

Lemma
If \(\lambda_k\) is a root of \(H\) with multiplicity \(m\) then

$$ p_k(n) = \frac{m \; G(\lambda_k)}{(-\lambda_k)^{m} H^{(m)}(\lambda_k)} \, n^{m-1} + O\left(n^{m-2}\right).$$

 

Recall that \(f_n = p_1(n)\lambda_1^{-n} + \cdots + p_s(n)\lambda_s^{-n}\).

Lemma
If \(\lambda_k\) is a root of \(H\) with multiplicity \(m\) then

$$ p_k(n) = \frac{m \; G(\lambda_k)}{(-\lambda_k)^{m} H^{(m)}(\lambda_k)} \, n^{m-1} + O\left(n^{m-2}\right).$$

Proof Idea
$$\displaystyle \frac{G(z)}{H(z)} = \frac{C}{(z-\lambda_k)^m} + \frac{J(z)}{I(z)(z-\lambda_k)^{m-1}}$$
Multiply by \((z-\lambda_k)^m\) then set \(z=\lambda_k\).

Corollary
If \(G\) and \(H\) are coprime and \(|\lambda_1| < |\lambda_k|\) for all \(k=2,\dots,s\) then

$$ f_n = p_1(n)\lambda_1^{-n} + O\left(w^{-n}n^{\alpha-1}\right)$$
where \(\displaystyle w = \min_{2 \leq k \leq s}|\lambda_k|\) and \(\alpha\) is the largest multiplicity of the roots of \(H\) with modulus \(w\).

Corollary
If \(G\) and \(H\) are coprime and \(|\lambda_1| < |\lambda_k|\) for all \(k=2,\dots,s\) then

$$ f_n = p_1(n)\lambda_1^{-n} + O\left(w^{-n}n^{\alpha-1}\right)$$
where \(\displaystyle w = \min_{2 \leq k \leq s}|\lambda_k|\) and \(\alpha\) is the largest multiplicity of the roots of \(H\) with modulus \(w\).

Corollary
If \(G\) and \(H\) are coprime and \(|\lambda_1| < |\lambda_k|\) for all \(k=2,\dots,s\) then

$$ f_n = p_1(n)\lambda_1^{-n} + O\left(w^{-n}n^{\alpha-1}\right)$$
where \(\displaystyle w = \min_{2 \leq k \leq s}|\lambda_k|\) and \(\alpha\) is the largest multiplicity of the roots of \(H\) with modulus \(w\).

Daniel Bernoulli, Observationes de seriebus quae formantur ex additione vel subtractione quacunque terminorum se mutuo consequentium, 1728

Daniel Bernoulli, Observationes de seriebus quae formantur ex additione vel subtractione quacunque terminorum se mutuo consequentium, 1728

Daniel Bernoulli, Observationes de seriebus quae formantur ex additione vel subtractione quacunque terminorum se mutuo consequentium, 1728

Daniel Bernoulli, Observationes de seriebus quae formantur ex additione vel subtractione quacunque terminorum se mutuo consequentium, 1728

Because there is only one root of minimal modulus, we get exponential convergence.

$$\begin{aligned} & -0.{\color{red}2}857142857 \\ & -0.{\color{red}2}800000000 \\ & -0.{\color{red}2}688172043 \\ & -0.{\color{red}27}27272727 \\ & -0.{\color{red}27}19298246 \\ & -0.{\color{red}2720}173536 \\ & -0.{\color{red}2720}245471 \\ & -0.{\color{red}27201}81056 \\ & -0.{\color{red}272019}9449 \\ & -0.{\color{red}2720196}208 \\ & -0.{\color{red}2720196}457 \\ & -{0.\color{red}2720196}521 \\ & -0.{\color{red}27201964}88 \\ & -0.{\color{red}272019649}6 \\ & -0.{\color{red}2720196495} \\ & -0.{\color{red}2720196495140690?}\end{aligned}$$

Corollary
If \(G\) and \(H\) are coprime and \(|\lambda_1| \leq |\lambda_k|\) for all \(k=2,\dots,s\) and \(\lambda_1\) has higher multiplicitly \(m\) than all other roots \(\lambda_k\) of \(H\) with \(|\lambda_1|=|\lambda_k|\) then

$$ f_n = \frac{m \; G(\lambda_1)}{(-\lambda_1)^{m} H^{(m)}(\lambda_1)} \, n^{m-1} \lambda_1^{-n} + O(n^{m-2}\lambda_1^{-n}).$$

Corollary
If \(G\) and \(H\) are coprime and \(|\lambda_1| \leq |\lambda_k|\) for all \(k=2,\dots,s\) and \(\lambda_1\) has higher multiplicitly \(m\) than all other roots \(\lambda_k\) of \(H\) with \(|\lambda_1|=|\lambda_k|\) then

$$ f_n = \frac{m \; G(\lambda_1)}{(-\lambda_1)^{m} H^{(m)}(\lambda_1)} \, n^{m-1} \lambda_1^{-n} + O(n^{m-2}\lambda_1^{-n}).$$
Note
In this case we only get a polynomially smaller error.
 

Corollary
If \(G\) and \(H\) are coprime and \(|\lambda_1| \leq |\lambda_k|\) for all \(k=2,\dots,s\) and \(\lambda_1\) has higher multiplicitly \(m\) than all other roots \(\lambda_k\) of \(H\) with \(|\lambda_1|=|\lambda_k|\) then

$$ f_n = \frac{m \; G(\lambda_1)}{(-\lambda_1)^{m} H^{(m)}(\lambda_1)} \, n^{m-1} \lambda_1^{-n} + O(n^{m-2}\lambda_1^{-n}).$$
Example
The GF for the number \(c_n\) of ways to make change for \(n\) cents in euro coins is

$$ \frac{1}{(1-z)(1-z^2)(1-z^5)(1-z^{10})(1-z^{20})(1-z^{50})(1-z^{100})(1-z^{200})}$$

Corollary
If \(G\) and \(H\) are coprime and \(|\lambda_1| \leq |\lambda_k|\) for all \(k=2,\dots,s\) and \(\lambda_1\) has higher multiplicitly \(m\) than all other roots \(\lambda_k\) of \(H\) with \(|\lambda_1|=|\lambda_k|\) then

$$ f_n = \frac{m \; G(\lambda_1)}{(-\lambda_1)^{m} H^{(m)}(\lambda_1)} \, n^{m-1} \lambda_1^{-n} + O(n^{m-2}\lambda_1^{-n}).$$
Example
The GF for the number \(c_n\) of ways to make change for \(n\) cents in euro coins is

$$ \frac{1}{(1-z)(1-z^2)(1-z^5)(1-z^{10})(1-z^{20})(1-z^{50})(1-z^{100})(1-z^{200})}$$
Thus \(c_n=\frac{8}{H^{(8)}(1)} \cdot n^7 + O(n^6) \sim \frac{n^7}{2(5)(10)(20)(50)(100)(200)7!}.\)

How do we find dominant singularities (of minimal modulus)?

 

How do we find dominant singularities (of minimal modulus)?

Vivanti-Pringsheim Theorem
If \(f_n \geq 0\) for all \(n \geq 0\) and \(G\) and \(H\) are coprime then one root of \(H\) with minimal modulus is positive and real.

How do we find dominant singularities (of minimal modulus)?

Vivanti-Pringsheim Theorem
If \(f_n \geq 0\) for all \(n \geq 0\) and \(G\) and \(H\) are coprime then one root of \(H\) with minimal modulus is positive and real.

To find rational GF asymptotics:

1. Find the smallest \(\lambda>0\) with \(H(\lambda)=0\).

How do we find dominant singularities (of minimal modulus)?

Vivanti-Pringsheim Theorem
If \(f_n \geq 0\) for all \(n \geq 0\) and \(G\) and \(H\) are coprime then one root of \(H\) with minimal modulus is positive and real.

To find rational GF asymptotics:

1. Find the smallest \(\lambda>0\) with \(H(\lambda)=0\).

2. Find all (other) roots of \(H\) with modulus \(\lambda\).

How do we find dominant singularities (of minimal modulus)?

Vivanti-Pringsheim Theorem
If \(f_n \geq 0\) for all \(n \geq 0\) and \(G\) and \(H\) are coprime then one root of \(H\) with minimal modulus is positive and real.

To find rational GF asymptotics:

1. Find the smallest \(\lambda>0\) with \(H(\lambda)=0\).

2. Find all (other) roots of \(H\) with modulus \(\lambda\).

3. Compute the asymptotic contributions of each.

How do we find dominant singularities (of minimal modulus)?

Vivanti-Pringsheim Theorem
If \(f_n \geq 0\) for all \(n \geq 0\) and \(G\) and \(H\) are coprime then one root of \(H\) with minimal modulus is positive and real.

To find rational GF asymptotics:

1. Find the smallest \(\lambda>0\) with \(H(\lambda)=0\).

2. Find all (other) roots of \(H\) with modulus \(\lambda\).

3. Compute the asymptotic contributions of each.

What could go wrong?

Open Problem 1 (Skolem's Problem)

Is there an algorithm that takes a C-finite sequence \((f_n)\) and determines whether \(f_n=0\) for any \(n\in\mathbb{N}\).

Open Problem 1 (Skolem's Problem)

Is there an algorithm that takes a C-finite sequence \((f_n)\) and determines whether \(f_n=0\) for any \(n\in\mathbb{N}\).

Theorem (Skolem, 1933)

The indices of zeroes of a C-finite sequence over \(\mathbb{Q}\) form a finite set together with a finite set of arithmetic progressions.

Open Problem 1 (Skolem's Problem)

Is there an algorithm that takes a C-finite sequence \((f_n)\) and determines whether \(f_n=0\) for any \(n\in\mathbb{N}\).

Theorem (Skolem, 1933)

The indices of zeroes of a C-finite sequence over \(\mathbb{Q}\) form a finite set together with a finite set of arithmetic progressions.

Orders 1 and 2: Easy
 

Open Problem 1 (Skolem's Problem)

Is there an algorithm that takes a C-finite sequence \((f_n)\) and determines whether \(f_n=0\) for any \(n\in\mathbb{N}\).

Theorem (Skolem, 1933)

The indices of zeroes of a C-finite sequence over \(\mathbb{Q}\) form a finite set together with a finite set of arithmetic progressions.

Orders 1 and 2: Easy
Orders 3 and 4: Mignotte, Shorey, and Tijdeman (1984)
                              Vereshchagin (1985)
 

Open Problem 1 (Skolem's Problem)

Is there an algorithm that takes a C-finite sequence \((f_n)\) and determines whether \(f_n=0\) for any \(n\in\mathbb{N}\).

Theorem (Skolem, 1933)

The indices of zeroes of a C-finite sequence over \(\mathbb{Q}\) form a finite set together with a finite set of arithmetic progressions.

Orders 1 and 2: Easy
Orders 3 and 4: Mignotte, Shorey, and Tijdeman (1984)
                              Vereshchagin (1985)
Simple recurrences: Bilu, Luca, Nieuwveld, Ouaknine, Purser,
                                       Worrell (2022) + NT conjectures

Open Problem 1 (Skolem's Problem)

Is there an algorithm that takes a C-finite sequence \((f_n)\) and determines whether \(f_n\;{\color{red}=}\;0\) for any \(n\in\mathbb{N}\).

Open Problem 1 (Skolem's Problem)

Is there an algorithm that takes a C-finite sequence \((f_n)\) and determines whether \(f_n\;{\color{red}=}\;0\) for any \(n\in\mathbb{N}\).

Open Problem 2 (Strict Positivity Problem)

Is there an algorithm that takes a C-finite sequence \((f_n)\) and determines whether \(f_n \;{\color{red}>}\; 0\) for all \(n\in\mathbb{N}\).
 

Open Problem 1 (Skolem's Problem)

Is there an algorithm that takes a C-finite sequence \((f_n)\) and determines whether \(f_n\;{\color{red}=}\;0\) for any \(n\in\mathbb{N}\).

Open Problem 2 (Strict Positivity Problem)

Is there an algorithm that takes a C-finite sequence \((f_n)\) and determines whether \(f_n \;{\color{red}>}\; 0\) for all \(n\in\mathbb{N}\).
 

Open Problem 3 (Positivity Problem)

Is there an algorithm that takes a C-finite sequence \((f_n)\) and determines whether \(f_n \;{\color{red}\geq}\; 0\) for all \(n\in\mathbb{N}\).

Open Problem 4 (Ultimate Positivity Problem)

Is there an algorithm that takes a C-finite sequence \((f_n)\) and determines whether \(f_n\;{\color{red}\geq}\;0\) for all but finitely many \(n\).

Open Problem 4 (Ultimate Positivity Problem)

Is there an algorithm that takes a C-finite sequence \((f_n)\) and determines whether \(f_n\;{\color{red}\geq}\;0\) for all but finitely many \(n\).

Order at most 5: Ouaknine and Worrell (2014)
 

Open Problem 4 (Ultimate Positivity Problem)

Is there an algorithm that takes a C-finite sequence \((f_n)\) and determines whether \(f_n\;{\color{red}\geq}\;0\) for all but finitely many \(n\).

Order at most 5: Ouaknine and Worrell (2014)

Simple recurrences: Ouaknine and Worrell (2014)

Open Problem 4 (Ultimate Positivity Problem)

Is there an algorithm that takes a C-finite sequence \((f_n)\) and determines whether \(f_n\;{\color{red}\geq}\;0\) for all but finitely many \(n\).

Order at most 5: Ouaknine and Worrell (2014)

Simple recurrences: Ouaknine and Worrell (2014)

An algorithm for order 6 would be significant breakthrough in analytic number theory (computability of Lagrange constant)

Open Problem 4 (Ultimate Positivity Problem)

Is there an algorithm that takes a C-finite sequence \((f_n)\) and determines whether \(f_n\;{\color{red}\geq}\;0\) for all but finitely many \(n\).

Order at most 5: Ouaknine and Worrell (2014)

Simple recurrences: Ouaknine and Worrell (2014)

An algorithm for order 6 would be significant breakthrough in analytic number theory (computability of Lagrange constant)

What happens in practice?

The set of \(\mathbb{N}\)-rational functions:

• contains 1 and the variable \(z\)
• is closed under addition and multiplication
• is closed under pseudoinverse \(f \mapsto 1/(1-zf)\)

The set of \(\mathbb{N}\)-rational functions:

• contains 1 and the variable \(z\)
• is closed under addition and multiplication
• is closed under pseudoinverse \(f \mapsto 1/(1-zf)\)

These are the generating functions of regular languages 
(classes using only \(+, \times, \text{SEQ}\) with no recursion).

The set of \(\mathbb{N}\)-rational functions:

• contains 1 and the variable \(z\)
• is closed under addition and multiplication
• is closed under pseudoinverse \(f \mapsto 1/(1-zf)\)

These are the generating functions of regular languages 
(classes using only \(+, \times, \text{SEQ}\) with no recursion).

Theorem (Berstel 1971)
If \(F(z)\) is \(\mathbb{N}\)-rational then its dominant singularities consist of some \(\rho>0\) and (potentially) some \(\rho \, \zeta_k\) for roots of unity \(\zeta_k\).

Example (Of a Horrible Name)
Let \(\theta = \arccos(1/3)\). The function

$$ F(z) = \frac{2(1+3z)^2}{(1-9z)(1+14z+81z^2)} = \frac{1/2}{1-9ze^{2i\theta}} + \frac{1/2}{1-9ze^{-2i\theta}} + \frac{1}{1-9z}$$
is not \(\mathbb{N}\)-rational as \(e^{2i\theta}\) not a root of unity, but

$$ [z^n]F(z) = 9^n(1+\cos(2n\theta)) \geq 0 $$
implies \(F\) has series coefficients in \(\mathbb{N}\).

Theorem (Berstel and Reutenauer, 1988)

If \(F\) is \(\mathbb{N}\)-rational then there exists some \(p>0\) with
 

$$ F(z) = S_0(z^p) + zS_1(z^p) + \cdots + z^{p-1}S_{p-1}(z^p) $$
where each \(S_k\) is an \(\mathbb{N}\)-rational series with a unique singularity of minimal modulus.

Theorem (Berstel and Reutenauer, 1988)

If \(F\) is \(\mathbb{N}\)-rational then there exists some \(p>0\) with
 

$$ F(z) = S_0(z^p) + zS_1(z^p) + \cdots + z^{p-1}S_{p-1}(z^p) $$
where each \(S_k\) is an \(\mathbb{N}\)-rational series with a unique singularity of minimal modulus.

Barcucci et al. (2001)

Algorithm to test for \(\mathbb{N}\)-rationality and (if positive) construct corresponding regular language.

Meta Theorem

Any "naturally occurring" combinatorial generating function that is rational is actually \(\mathbb{N}\)-rational.

Meta Theorem

Any "naturally occurring" combinatorial generating function that is rational is actually \(\mathbb{N}\)-rational.

Bousquet-Mélou (2006 ICM): "I have never met a counting problem that would yield a rational, but not \(\mathbb{N}\)-rational, GF".

Koutschan (2005 Diplomarbeit): "From about 60 rational series with nonnegative coefficients taken from [the OEIS], not one single [one] turned out to be not \(\mathbb{N}\)-rational."

Meta Theorem

Any "naturally occurring" combinatorial generating function that is rational is actually \(\mathbb{N}\)-rational.

Bousquet-Mélou (2006 ICM): "I have never met a counting problem that would yield a rational, but not \(\mathbb{N}\)-rational, GF".

Koutschan (2005 Diplomarbeit): "From about 60 rational series with nonnegative coefficients taken from [the OEIS], not one single [one] turned out to be not \(\mathbb{N}\)-rational."

We don't need to worry about computability of asymptotics. 
It is still interesting to ask about complexity of asymptotics.

The most expensive step in finding asymptotics is finding the roots of minimal modulus.

Let \(P\in\mathbb{Z}[z]\) have degree \(d\) and coefficient size at most \(2^h\).

The most expensive step in finding asymptotics is finding the roots of minimal modulus.

Let \(P\in\mathbb{Z}[z]\) have degree \(d\) and coefficient size at most \(2^h\).

Lemma (Mahler, Mignotte, ...)

If \(P(\alpha)=P(\beta)=0\) and \(\alpha \neq \beta\) then

$$|\alpha-\beta| \geq D_d \cdot 2^{-h(d-1)} $$

where \(D_d\) is an explicit constant depending only on \(d\).

The most expensive step in finding asymptotics is finding the roots of minimal modulus.

Let \(P\in\mathbb{Z}[z]\) have degree \(d\) and coefficient size at most \(2^h\).

Lemma (Mahler, Mignotte, ...)

If \(P(\alpha)=P(\beta)=0\) and \(\alpha \neq \beta\) then

$$|\alpha-\beta| \geq D_d \cdot 2^{-h(d-1)} $$

where \(D_d\) is an explicit constant depending only on \(d\).

What about \(||\alpha|-|\beta||\)?

Let \(P\in\mathbb{Z}[z]\) have degree \(d\) and coefficient size at most \(2^h\).

Theorem (Bugeaud et al., 2022)

Suppose \(P(\alpha)=P(\beta)=0\) and \(|\alpha| \neq |\beta|\).

$$\begin{aligned} &\text{If \(\alpha,\beta\in\mathbb{R}\) then \qquad\quad\;\,\;\, \(||\alpha|-|\beta|| \geq A_d \cdot 2^{-h(d-1)}\)} \\[+2mm] &\text{If \(\alpha\in\mathbb{R}\) and \(\beta\notin\mathbb{R}\) then \; \(||\alpha|-|\beta|| \geq B_d \cdot 2^{-2h(d-1)(d-2)}\)} \\[+2mm] &\text{In general \qquad\qquad\qquad\,\; \(||\alpha|-|\beta|| \geq C_d \cdot 2^{-h(d-1)(d-2)(d-3)/2}\)}\end{aligned}$$
for explicit constants \(A_d,B_d,C_d\) depending only on \(d\).

 

Let \(P\in\mathbb{Z}[z]\) have degree \(d\) and coefficient size at most \(2^h\).

Theorem (Bugeaud et al., 2022)

Suppose \(P(\alpha)=P(\beta)=0\) and \(|\alpha| \neq |\beta|\).

$$\begin{aligned} &\text{If \(\alpha,\beta\in\mathbb{R}\) then \qquad\quad\;\,\;\, \(||\alpha|-|\beta|| \geq A_d \cdot 2^{-h(d-1)}\)} \\[+2mm] &\text{If \(\alpha\in\mathbb{R}\) and \(\beta\notin\mathbb{R}\) then \; \(||\alpha|-|\beta|| \geq B_d \cdot 2^{-2h(d-1)(d-2)}\)} \\[+2mm] &\text{In general \qquad\qquad\qquad\,\; \(||\alpha|-|\beta|| \geq C_d \cdot 2^{-h(d-1)(d-2)(d-3)/2}\)}\end{aligned}$$
Corollary: Find all dominant singularities in \(\tilde{O}(hd^3)\) bit operations when \(f_n \geq 0\) for all \(n\).

Let \(P\in\mathbb{Z}[z]\) have degree \(d\) and coefficient size at most \(2^h\).

Theorem (Bugeaud et al., 2022)

Suppose \(P(\alpha)=P(\beta)=0\) and \(|\alpha| \neq |\beta|\).

$$\begin{aligned} &\text{If \(\alpha,\beta\in\mathbb{R}\) then \qquad\quad\;\,\;\, \(||\alpha|-|\beta|| \geq A_d \cdot 2^{-h(d-1)}\)} \\[+2mm] &\text{If \(\alpha\in\mathbb{R}\) and \(\beta\notin\mathbb{R}\) then \; \(||\alpha|-|\beta|| \geq B_d \cdot 2^{-2h(d-1)(d-2)}\)} \\[+2mm] &\text{In general \qquad\qquad\qquad\,\; \(||\alpha|-|\beta|| \geq C_d \cdot 2^{-h(d-1)(d-2)(d-3)/2}\)}\end{aligned}$$
Corollary: Find all dominant singularities in \(\tilde{O}(hd^{\color{red}3})\) bit operations when \(f_n \geq 0\) for all \(n\).

Let \(P\in\mathbb{Z}[z]\) have degree \(d\) and coefficient size at most \(2^h\).

Theorem (Bugeaud et al., 2022)

Suppose \(P(\alpha)=P(\beta)=0\) and \(|\alpha| \neq |\beta|\).

$$\begin{aligned} &\text{If \(\alpha,\beta\in\mathbb{R}\) then \qquad\quad\;\,\;\, \(||\alpha|-|\beta|| \geq A_d \cdot 2^{-h(d-1)}\)} \\[+2mm] &\text{If \(\alpha\in\mathbb{R}\) and \(\beta\notin\mathbb{R}\) then \; \(||\alpha|-|\beta|| \geq B_d \cdot 2^{-2h(d-1)(d-2)}\)} \\[+2mm] &\text{In general \qquad\qquad\qquad\,\; \(||\alpha|-|\beta|| \geq C_d \cdot 2^{-h(d-1)(d-2)(d-3)/2}\)}\end{aligned}$$
Corollary: Find all dominant singularities in \(\tilde{O}(hd^{\color{red}4})\) bit operations in general.

Let \(P\in\mathbb{Z}[z]\) have degree \(d\) and coefficient size at most \(2^h\).

Theorem (Bugeaud et al., 2022)

Suppose \(P(\alpha)=P(\beta)=0\) and \(|\alpha| \neq |\beta|\).

$$\begin{aligned} &\text{If \(\alpha,\beta\in\mathbb{R}\) then \qquad\quad\;\,\;\, \(||\alpha|-|\beta|| \geq A_d \cdot 2^{-h(d-1)}\)} \\[+2mm] &\text{If \(\alpha\in\mathbb{R}\) and \(\beta\notin\mathbb{R}\) then \; \(||\alpha|-|\beta|| \geq B_d \cdot 2^{-2h(d-1)(d-2)}\)} \\[+2mm] &\text{In general \qquad\qquad\qquad\,\; \(||\alpha|-|\beta|| \geq C_d \cdot 2^{-h(d-1)(d-2)(d-3)/2}\)}\end{aligned}$$
Open Problem: Find the optimal complexity for asymptotics of C-finite sequences.

Consider the sequence defined by \(\displaystyle (u_0,u_1,u_2) = \left(\frac{1}{8}, -\frac{7}{64}, \frac{121}{512}\right)\)

$$ 8u_{n+3} + 7u_{n+2} - 9u_{n+1} - 17u_n = 0,$$
with generating function \(1/(8 + 7z - 9z^2 -17z^3)\).

Consider the sequence defined by \(\displaystyle (u_0,u_1,u_2) = \left(\frac{1}{8}, -\frac{7}{64}, \frac{121}{512}\right)\)

$$ 8u_{n+3} + 7u_{n+2} - 9u_{n+1} - 17u_n = 0,$$
with generating function \(1/(8 + 7z - 9z^2 -17z^3)\).

Consider the sequence defined by \(\displaystyle (u_0,u_1,u_2) = \left(\frac{1}{8}, -\frac{7}{64}, \frac{121}{512}\right)\)

$$ 8u_{n+3} + 7u_{n+2} - 9u_{n+1} - 17u_n = 0,$$
with generating function \(1/(8 + 7z - 9z^2 -17z^3)\).

Consider the sequence defined by \(\displaystyle (u_0,u_1,u_2) = \left(\frac{1}{8}, -\frac{7}{64}, \frac{121}{512}\right)\)

$$ 8u_{n+3} + 7u_{n+2} - 9u_{n+1} - 17u_n = 0,$$
with generating function \(1/(8 + 7z - 9z^2 -17z^3)\).

Consider the sequence defined by \(\displaystyle (u_0,u_1,u_2) = \left(\frac{1}{8}, -\frac{7}{64}, \frac{121}{512}\right)\)

$$ 8u_{n+3} + 7u_{n+2} - 9u_{n+1} - 17u_n = 0,$$
with generating function \(1/(8 + 7z - 9z^2 -17z^3)\).

Consider the sequence defined by \(\displaystyle (u_0,u_1,u_2) = \left(\frac{1}{8}, -\frac{7}{64}, \frac{121}{512}\right)\)

$$ 8u_{n+3} + 7u_{n+2} - 9u_{n+1} - 17u_n = 0,$$
with generating function \(1/(8 + 7z - 9z^2 -17z^3)\).

Consider the sequence defined by \(\displaystyle (u_0,u_1,u_2) = \left(\frac{1}{8}, -\frac{7}{64}, \frac{121}{512}\right)\)

$$ 8u_{n+3} + 7u_{n+2} - 9u_{n+1} - 17u_n = 0,$$
with generating function \(1/(8 + 7z - 9z^2 -17z^3)\).

Consider the sequence defined by \(\displaystyle (u_0,u_1,u_2) = \left(\frac{1}{8}, -\frac{7}{64}, \frac{121}{512}\right)\)

$$ 8u_{n+3} + 7u_{n+2} - 9u_{n+1} - 17u_n = 0,$$
with generating function \(1/(8 + 7z - 9z^2 -17z^3)\).

Consider the sequence defined by \(\displaystyle (u_0,u_1,u_2) = \left(\frac{1}{8}, -\frac{7}{64}, \frac{121}{512}\right)\)

$$ 8u_{n+3} + 7u_{n+2} - 9u_{n+1} - 17u_n = 0,$$
with generating function \(1/(8 + 7z - 9z^2 -17z^3)\).

Consider the sequence defined by \(\displaystyle (u_0,u_1,u_2) = \left(\frac{1}{8}, -\frac{7}{64}, \frac{121}{512}\right)\)

$$ 8u_{n+3} + 7u_{n+2} - 9u_{n+1} - 17u_n = 0,$$
with generating function \(1/(8 + 7z - 9z^2 -17z^3)\).

 

Positive root is                           0.77781401...
Complex pair has modulus     0.77782634...

Consider the sequence defined by \(\displaystyle (u_0,u_1,u_2) = \left(\frac{1}{8}, -\frac{7}{64}, \frac{121}{512}\right)\)

$$ 8u_{n+3} + 7u_{n+2} - 9u_{n+1} - 17u_n = 0,$$
with generating function \(1/(8 + 7z - 9z^2 -17z^3)\).

 

Positive root is                           0.77781401...
Complex pair has modulus     0.77782634...

Give asymptotic terms
 

$$ (0.03962...)\cdot({\color{red}1.2856}5...)^n \qquad (0.60093...)\cdot({\color{red}1.2856}3...)^n$$

Consider the sequence defined by \(\displaystyle (u_0,u_1,u_2) = \left(\frac{1}{8}, -\frac{7}{64}, \frac{121}{512}\right)\)

$$ 8u_{n+3} + 7u_{n+2} - 9u_{n+1} - 17u_n = 0,$$
with generating function \(1/(8 + 7z - 9z^2 -17z^3)\).

 

Positive root is                           0.77781401...
Complex pair has modulus     0.77782634...

Real positive root doesn't dominate until index 223,200

Consider the sequence defined by \(\displaystyle (u_0,u_1,u_2) = \left(\frac{1}{8}, -\frac{7}{64}, \frac{121}{512}\right)\)

$$ 8u_{n+3} + 7u_{n+2} - 9u_{n+1} - 17u_n = 0,$$
with generating function \(1/(8 + 7z - 9z^2 -17z^3)\).

 

Positive root is                           0.77781401...
Complex pair has modulus     0.77782634...

Real positive root doesn't dominate until index 223,200

Such pathological issues are rare in practice. Thus, we start at reasonable precision and refine further only if necessary.

Theorem

The class of binary trees cannot be recognized by a finite automaton.

Theorem

The class of binary trees cannot be recognized by a finite automaton.

Proof

Any language recognized by a finite automaton is regular and thus has a rational generating function.

Binary trees have the irrational generating function
 

$$ C(z) = \frac{1- \sqrt{1-4z}}{2z}.$$

Theorem

The series \(\displaystyle F(z) = \sum_{n\geq1}\frac{z^n}{n^5}\) is irrational.

Theorem

The series \(\displaystyle F(z) = \sum_{n\geq1}\frac{z^n}{n^5}\) is irrational.

Proof

The coefficient sequence \(f_n=n^{-5}\) is not C-finite by the C-finite Coefficient Theorem.

Note: Irrationality of \(F(1) = \zeta(5)\) is still open.

Theorem

The sequence of prime numbers \(p_n\) satisfies no linear recurrence with constant coefficients.

Theorem

The sequence of prime numbers \(p_n\) satisfies no linear recurrence with constant coefficients.

Proof

The prime number theorem implies
 

$$p_n = n\log n + n\log n \log \log n + O(n).$$

Theorem

The sequence of prime numbers \(p_n\) satisfies no linear recurrence with constant coefficients.

Proof

The prime number theorem implies
 

$$p_n = n\log n + n\log n \log \log n + O(n).$$

Note: The \(\log \log n\) term will imply that \(p_n\) satisfies no linear recurrence with polynomial coefficients.

Many combinatorial methods to encode generating functions with algebraic/differential/functional equations.

We get a hierarchy of generating functions
 

$$ \text{rational} \;\subset\; \text{algebraic} \;\subset\; \text{D-finite} \;\subset\; \text{D-algebraic}$$

Univariate rational generating functions:
 

• simplest (non-trivial) family to study for asymptotics
• already have interesting computability and complexity questions