8.21

Altheman

Consider $(b_n)_{n\geq 1}$ a sequence of integers such that $b_1=0$
and define $a_1=0$ and $a_{n}=nb_n+a_1b_{n-1}+\cdots+a_{n-1}b_1$ for all $n\geq 2$ .
Prove that $p|a_p$ for any prime number $p$ .

**Posted:** Tue Jul 21, 2009 9:17 pm

_________________
-Alex
Altheman's Problem Column

t0rajir0u

Let $B(x) = \sum_{n \ge 0} b_n x^n$ and $A(x) = \sum_{n \ge 0} a_n x^n$ with $a_0 = b_0 = a_1 = b_1 = 0$ ; then

$A(x) = x B'(x) + A(x) B(x) \Leftrightarrow$
$A(x) = \frac {x B'(x)}{1 - B(x)}$ .

As an equality of (virtual) species this asserts that $A$ counts the number of ways to point to a $B$ -structure and then attach a sequence of $B$ -structures, where there are no zero- or one-element $B$ -structures. If the $b_i$ are non-negative then the following is a legitimate combinatorial proof, and otherwise I believe (but am not certain) that the theory of virtual species justifies it:

$a_p$ counts the number of ways to perform the above construction on an underlying totally ordered set of size $p$ . The cyclic group of order $p$ acts on elements of the above construction in the following way: move the point being pointed to to the next point $\bmod p$ . If the point moves to a $B$ -structure other than the first one, cycle the $B$ -structures so that the second one is now the first one, the first is now the last, and so forth. Since $p$ is prime it follows that a non-identity group element has a fixed point if and only if all the $B$ -structures are identical and have size one, but by assumption this doesn't occur, so every orbit has size $p$ . More generally one sees by Burnside's lemma that the number of orbits of $A$ -structures on an underlying set of size $n$ under the action of the cyclic group of order $n$ is

$\frac {1}{n} \sum_{d | n} \varphi \left( \frac {n}{d} \right) a_d$

since the only possible fixed point of an element of order $\frac {n}{d}$ is an $A$ -structure of size $d$ repeated $\frac {n}{d}$ times. This suggests that one way to attack the original problem is via a Mellin transform, although this is probably overkill.

**Posted:** Wed Jul 29, 2009 10:22 pm

_________________
Annoying Precision (http://qchu.wordpress.com/)

t0rajir0u

What's curious to me about this problem is that there is a "zeta function"-type identity

$\exp \int_{0}^{x} \frac {A(t)}{t} \, dt = \exp \sum_{n \ge 1} \frac {a_n}{n} x^n = \frac {1}{1 - B(x)}$

but I don't know if it affords a faster solution to the problem. The combinatorial interpretation is as follows: the number of sequences of $B$ -structures on $n$ elements is equal to the number of ways to assign an $A$ -structure to each cycle of a permutation on $n$ elements, divided by $n!$ .

Note that if $B$ is a polynomial the RHS may be thought of as the Ihara zeta function of the finite graph with adjacency matrix the companion matrix of the polynomial $1 - B$ (after reversing its coefficients), and $a_n$ then counts the number of closed walks of length $n$ on this graph, with the distinguished point representing the beginning of the walk. I've remarked on the combinatorics of this special case here. It's not hard to extend these ideas to a graph with countable vertices, but in order to handle negative $b_i$ it's necessary to make them formal weights.

As another generalization of the prime result one sees by Mobius inversion that the number of aperiodic $A$ -structures (that is, those having full orbits) up to the action of the cyclic group is

$\frac {1}{n} \sum_{d | n} \mu \left( \frac {n}{d} \right) a_d$ .

Edit: Another application of these ideas is to 9.10. Anyway, I've just realized that since $a_n$ is a polynomial in $b_1, ... b_n$ proving the desired results for non-negative $b_i$ immediately prove it for all integers by finite differences, and the same remark applies to 9.10.

**Posted:** Thu Jul 30, 2009 5:00 pm

_________________
Annoying Precision (http://qchu.wordpress.com/)

darij grinberg

And then there was the $5$ -liner...

Let $x_1$ , $x_2$ , ..., $x_p$ be the roots of the polynomial $X^p + b_1X^{p - 1} + b_2X^{p - 2} + b_3X^{p - 3} + ... + b_p$ . Then, $x_1$ , $x_2$ , ..., $x_p$ are algebraic integers, and $\left( - 1\right)^{i}b_i$ is the $i$ -th elementary symmetric polynomial of $x_1$ , $x_2$ , ..., $x_p$ for every $i\in\left\{1,2,...,p\right\}$ (by Viete's formula). Comparing the identities $a_1 = b_1$ (since $a_1 = 0 = b_1$ ) and $a_{n} = nb_n + a_1b_{n - 1} + \cdots + a_{n - 1}b_1$ for all $n\geq 2$ with the Newton identities, we see that $- a_i = x_1^i + x_2^i + ... + x_p^i$ for every $i\in\left\{1,2,...,p\right\}$ . Thus,

$- a_p = x_1^p + x_2^p + ... + x_p^p\equiv\left(\underbrace{x_1 + x_2 + ... + x_p}_{ = - b_1 = 0}\right)^p\equiv 0\mod p$ ,

where two algebraic integers are said to be congruent modulo $p$ if their difference divided by $p$ is an algebraic integer. Hence, $\frac { - a_p}{p}$ is an algebraic integer. But it is also a rational number, and thus an integer (since $\mathbb{Z}$ is integrally closed), qed.

The same method can be used for t0rajir0u's generalizations $n\mid \sum_{d | n} \mu \left( \frac {n}{d} \right) a_d$ and $n\mid \sum_{d | n} \phi \left( \frac {n}{d} \right) a_d$ for all $n\in\mathbb{N}$ (which are equivalent to $a_{np^k}\equiv a_{np^{k + 1}}\mod p^{k + 1}$ for all $n$ , $k$ and prime $p$ ). We can also replace $\mathbb{Z}$ by any commutative ring with $1$ , but the proof will get a bit more difficult: We will have to prove everything for the polynomial ring $\mathbb{Z}\left[A_1,A_2,...,A_p\right]$ at first, because it is integrally closed, while arbitrary rings are not necessarily so.

darij

**Posted:** Fri Sep 25, 2009 3:50 am

_________________
Now the die is cast, the first step taken, a glimmer of hope lights up our lives
Visions of the past, dreams forsaken forming right under our eyes
We are alive...