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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.