Today we discuss some generating functions.

Problem 1: Give a finite set of positive integers T. Let \mathfrak{T}_n be the collection of sequences (t_1,t_2,...,t_m), such that \sum_{i=1}^m t_m=n, and each t_i\in T. Let a_n=|\mathfrak{T}_n| for n\ge1 and a_0=1, and f(x)=\sum_{n=0}^{\infty}a_n x^n. Find out what is f(x) explicitly.

Solution: It is not hard to note the recursive relation a_n=\sum_{t\in T} a_{n-t} for n\ge1, if we set a_i=0 for negative i. So that f(x)=1+\sum_{t\in T} x^t f(x) and f(x)=1/(1-\sum_{t\in T} x^t), which is a rational function.

Variantion 1: If T is infinite, what would happen? Would f(x) still be rational?

We first analyze simple cases. If T=\mathbb{N}^+, it is expected that f(x)=1+\sum_{t=1}^{\infty} x^t f(x)=1+f(x) x/(1-x), so that f(x)=(1-x)/(1-2x)=1+\sum_{n=1}^{\infty} 2^{n-1} x^n. Indeed, in this case, counting the sequences amounts to divide a sequence of n objects arbitrarily. You can choose to divide between the ith and i+1th for 1\ge i\ge n-1, so in all 2^{n-1} choices, justifying the expansion.

I think it is equivalent to f being rational.

Theorem: \mathbb{Q}_p(t)\cap\mathbb{Q}[[t]]=\mathbb{Q}(t)

It is very interesting that this theorem is used for the rationality of \zeta-functions for algebraic varieties, which is part of the Weil conjectures.

Wednesday, July 10, 2013