# If the series Σ pᵃ⁽ʷ⁾·xᴵʷᴵ is rational, is Σ a(w)·xᴵʷᴵ also rational (summation over words w in a regular language)?

Let $p$ be a prime number and let $a_i$ be a sequence of natural numbers such that the series $\sum_{i=1}^\infty p^{a_i} x^i$ is rational. A warm-up question:

Question 1. Does it follow that the series $\sum_{i=1}^\infty a_i x^i$ is rational?

Let $p$ be a prime number and let $L$ be a regular language. Let $a\colon L\to \mathbb N$ be a function such that the series $$\sum_{w\in L} p^{a(w)}x^{|w|}$$ is rational.

Queston 2. Does it follow that the series $\sum_{w\in L} a(w) x^{|w|}$ is rational?

# Motivation

Let $L$ be a regular language and let $T=T_w$, $w\in L$, be a family of finite dimensional matrices with integral coefficients. Consider the series $$F(T,p)(x) := \sum_{w\in L} \dim_{\mathbb F_p}\ker_{\mathbb F_p} T_w \cdot x^{|w|},$$ and the series $$G(T,p)(x) := \sum_{w\in L} |\ker_{\mathbb F_p} T_w| \cdot x^{|w|},$$ where $|\ker_{\mathbb F_p} T_w|$ is the number of elements in $\ker_{\mathbb F_p} T_w$. The relation between $G$ and $F$ is as in the questions above. In my specific situation the series $G$ is rational, roughly because the elements of $\ker_{\mathbb F_p} T_w$ also form a regular language. I would like to know that the series $F$ is rational because $F(T,p)(\frac{1}{2})$ is a so called $l^2$-Betti number over $\mathbb F_p$ and it would be very nice to know that these are rational in the case at hand.

# Remarks

In the key example I have (section 2-C is the relevant one) the series $$F(T)(x) := \sum_{w\in L} \dim_{\mathbb C}\ker_{\mathbb C} T_w \cdot x^{|w|}$$ is transcendental, but all the series $F(T,p)$ are rational, because $a(w)$ are bounded, and in this case the answer to Question 2 is, as explained by Dylan below, positive. Reason for transcendality over complex numbers is that the family of vectors which make it transcendental have rapidly growing coefficients, and so no single prime number can detect this family. Questions above can be informally seen as asking whether "unboundedness of elements in the kernels" can also be a reason for the series not being rational.

• @Lukasz: if G is rational for all primes p, do you know if G is also rational in p? If so, the result follows by taking the derivative with respect to p and setting p = 1. – Qiaochu Yuan Oct 17 '10 at 22:38
• @Qiaochu: I also thought about it, but so far I don't see a reason why should it be rational in p. Moreover, in my specific situation the sequence a_i depends on p, i.e. although G(T,p) is rational for all p, it's "not the same series with just p exchanged with p'". – Łukasz Grabowski Oct 18 '10 at 10:37

On question 1: Did you think about the case when $p=2$, $a_i$ are bounded, say take values 0,1,2? Suppose $\Sigma=\sum 2^{a_i} x^i$ and $\Sigma'=\sum a_i x^i$ are rational. Then their difference is rational as well, etc. It is easy to deduce this way that the sum $\Sigma_0=\sum_{a_i=0} x^i$, is also a rational function. Thus your statement implies that if $\Sigma$ is rational, then $\Sigma_0$ is rational. But that seems unlikely. I do not know an example, though.

• This is fine if the sequence a_i is periodic. More generally I think it can be a "quasi-polynomial of degree 1." – Qiaochu Yuan Oct 16 '10 at 19:36
• In the specific situation I have (i.e. a(w) (or a_i) are dimensions of some kernels) I can actually prove the statement as soon as a(w) are bounded. – Łukasz Grabowski Oct 16 '10 at 19:37
• Qiaochu: my first crude guess was that in the sequence case a_i is always (linear in i) + (periodic in i). Is that what you mean by "quasi-polynomial"? I tried to show it using the fact that $p^{a_i}$ fulfill a recurrence but I failed. – Łukasz Grabowski Oct 16 '10 at 19:41
• @Lukasz: You can prove that Question 1 has positive answer whenever $a_i$ are bounded or only in your specific case when $a_i$ are dimensions of some kernels? – Steve Richards Oct 16 '10 at 20:08
• @Qiaochu: What is fine if $a_i$ is periodic. In general $\sum a_i x^i$ is rational then $a_i$ satisfy some rational recurrent relation, but may be far from periodic. – Steve Richards Oct 16 '10 at 20:10

There are many papers dealing with the largest prime divisor of elements from a recurrent sequence. See for example the paper "On the greatest prime factor of terms of a linear recurrence sequence" by C.L. Stewart. Since in your case the largest prime factor remains bounded this implies that the sequence is degenerate in some sense (Polya 1921) and I beleieve these cases can be checked to show that the $a_i$'s form a recurrent sequence as well.

If there are only finitely many values for the $a_i$, then I believe the answer to both questions is affirmative for somewhat silly reasons. If you have any rational power series $f(x)$ with only finitely many different coefficients, then I believe the power series $f_c(x)$ with a coefficient of 1 when $f(x)$ has $c$ (and 0 otherwise) is also rational. (Restivo and Reutenauer, "On cancellation properties of languages which are supports of rational power series", cite Sontag, "On some questions of rationality and decidability" for this fact. I couldn't find the precise statement, but the techniques are plausibly related.) Then you can easily rearrange the coefficients as in Question 1. (This would also work for a slightly weaker version of Question 2 that seems likely to be relevant for you: instead of power series in $x$, work in non-commutative power series in the alphabet of $L$ and do the rearranging there. For this, you need to know that $\sum p^{a_i} w$ is rational, but it sounds like you do.)

(The theorems above can be made easier by assuming that the power series like $\sum p^{a_i} x^i$ are the weighted generating series of a regular language with positive weights, which again sounds like the relevant case; then you can just use the usual NDFA -> DFA reduction.)

However, your $a_i$ are not bounded, it sounds like. The linear recurrence on the coefficients is going to give strong constraints on the $a_i$, but I don't yet see how to finish this to a proof.

• Thanks; It certainly seems to me now that the interesting case is when $a_i$ are unbounded. You're right that in my situation the series $\sum p^{a(w)}w$ is rational. BTW: what is "weighted generating series of a regular language with positive weights"? – Łukasz Grabowski Oct 17 '10 at 19:27
• If you have an NDFA for a language L, its weighted generating series is $\sum_{w \in L}\text{(# of ways of reaching }w)\cdot w$. More generally, you can have weights on your transition edges, so that, eg, weight 2 is the same as having two disjoint edges between the same pair of states. – Dylan Thurston Oct 17 '10 at 20:07

Here is an idea for a proof, but I don't know if it can actually be carried out. Suppose that $\Sigma p^{a_i}x^i$ is rational. Then for $n$ sufficiently large, we have a linear recurrence $$c_0 p^{a_n} + c_1 p^{a_{n-1}} +\cdots+c_k p^{a_{n-k}}=0,$$ where each $c_i$ is an integer. Write each $c_i$ in base $p$ and distribute, so now the terms have the form $d_{ij} p^{a_{n-i}+j}$, where $0\leq d_{ij}\leq p-1$. Move all the terms with minus signs to the other side. Compare the base $p$ expansions of both sides. This will involve some care since there could be "carrying," i.e., after collecting the powers of $p$ some coefficients could exceed $p-1$. But it seems as if the possibilities are limited and that a proof may be possible.