Number of p-adic strings of length l without t-consecutive zeros

Question

Firstly I define a p-adic string of length l as a list $a = [a_1,...,a_l]$ where $0 \leq a_i \leq p-1$ for $i \in [l] $. Then what is the number of such lists without t- consecutive zeros? My approach: break the l-length string into $l/t$ lists of size t, and now we can get an upper bound of $(p^t - 1)^{l/t}$. My question is can we improve this bound as if we take a fixed $l$ and make $p$ very large this bound does not become $o(p^l)$, but if we fix $p$ and let $l$ be very large, then we get $o(p^l)$. Can we, in general, say that the number of such lists is $o(p^l)$? Furthermore, suppose we have m such p-adic strings such that none of them has t - consecutive zeros at the same place the can we say number of such strings is $o(p^{ml})$.

Answer 1

As requested in the comments, here is a way of computing the generating function for the exact number of strings of length $\ell$ in an alphabet $\Sigma$ of size $p$ (including a “zero”) that do not contain $m$ consecutive zeros. (I'm renaming the $t$ in the question to $m$.) This is a straightforward application of the algorithm that computes the generating function for any rational language on a finite alphabet from a finite automaton recognizing the language in question (here the DFA has $m+1$ states, labeled $0$ through $m-1$ and $\bot$, described implicitly below: $L_q$ defined below is the set of words which bring the automaton to state $q$).

(In what follows, the phrase “the generating function for the language $L$” means $f := \sum_{\ell=0}^{+\infty} c_\ell z^\ell \in \mathbb{C}[[z]]$ where $z$ is a formal indeterminate and $c_\ell := \#\{w \in L : |w|=\ell\}$ is the number of words of length $\ell$ in $L$. For example, the generating function of the language $\Sigma^*$ of all words on an alphabet of size $p$ is $1 + pz + p^2z^2 + \cdots = \frac{1}{1-pz}$.)

For $0\leq i\leq m-1$, let $L_i$ be the set of words on $\Sigma$ which (a) do not contain $m$ consecutive zeros (anywhere), and additionally (b) end in precisely $i$ zeros. Furthermore, let $L_\bot$ be the set of words which do contain $m$ consecutive zeros (somewhere). Let $f_0,\ldots,f_{m-1},f_\bot$ be the generating functions for $L_0,\ldots,L_{m-1},L_\bot$ respectively. (Evidently, $\Sigma^*$ is the disjoint union of $L_0,\ldots,L_{m-1},L_\bot$, so $f_0+\cdots+f_{m-1}+f_\bot = \frac{1}{1-pz}$.) Our goal is to compute the generating function $g := f_0+\cdots+f_{m-1}$ of $L_0\cup\cdots\cup L_{m-1}$.

Now a word in $L_0$ is either the empty word or is obtained by adding one of the $p-1$ nonzero symbols at the end of a (uniquely defined) word in $L_0\cup\cdots\cup L_{m-1}$. This means that:

• $f_0 = 1 + (p-1)z f_0 + \cdots + (p-1)z f_{m-1}$

A word in $L_{i+1}$ for $0\leq i\leq m-2$, on the other hand, is obtained by adding a zero at the end of a (uniquely defined) word in $L_i$. In other words:

• $f_{i+1} = z f_i$

Finally, for a word of length $\ell$ in $L_\bot$, there are two possibilities: either the $\ell-1$ first letters are in $L_{m-1}$ and the last letter is a zero, or the $\ell-1$ first letters are already in $L_\bot$ (and the last letter is anything). This translates as:

• $f_\bot = z f_{m-1} + p z f_\bot$

To summarize, we have the following linear relation on $(f_0,\ldots,f_{m-1},f_\bot)$:

$$ \begin{pmatrix}f_0\\f_1\\f_2\\\vdots\\f_\bot\end{pmatrix} = \begin{pmatrix}1\\0\\0\\\vdots\\0\end{pmatrix} + \begin{pmatrix} (p-1)z&(p-1)z&\cdots&(p-1)z&0\\ z&0&\cdots&0&0\\ 0&z&\cdots&0&0\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&\cdots&z&pz\\ \end{pmatrix} \begin{pmatrix}f_0\\f_1\\f_2\\\vdots\\f_\bot\end{pmatrix} $$

Call $M$ the $(m+1)\times(m+1)$ matrix with coefficients in $\mathbb{C}[[z]]$ appearing above, so we are to solve $\vec f = \vec e + M \vec f$ where $\vec f$ is the column vector $(f_0,\ldots,f_{m-1},f_\bot)$ and $\vec e$ is the column vector $(1,0,\ldots,0)$. Its unique solution is $\vec f = (1-M)^{-1}\, \vec e$ since $1-M$ is invertible since it is congruent to $1$ mod $(z)$.

Now I claim that the solution is given by:

• $f_i = z^i/(1 - (p-1)\,z\,(1+\cdots+z^{m-1}))$ for $0\leq i\leq m-1$

• $f_\bot = z^m/((1-pz)\, (1 - (p-1)\,z\,(1+\cdots+z^{m-1})))$

Since the solution is unique, this is proved by simply checking that the expressions in question satisfy the linear relations written above, which is straightforward.

Finally the desired generating function is $g := f_0+\cdots+f_{m-1} = \frac{1}{1-pz} - f_\bot$. Rewriting $1+\cdots+z^{m-1}$ as $(1-z^m)/(1-z)$ and putting $\frac{1}{1-pz} - \frac{1}{(1-pz)\, (1 - (p-1)\,z\,\frac{1-z^m}{1-z})}$ on a common denominator, this gives the following final generating function: $$ \frac{1-z^m}{1-pz-z^{m+1}+pz^{m+1}} $$ for the words that do not contain $m$ consecutive zeros.