# On $k$-regularity of sequences of valuations and last nonzero digits

Bartosz Sobolewski  Institute of Mathematics, Faculty of Mathematics and
Computer Science, Jagiellonian University in Kraków, Łojasiewicza 6, 30-348,
Kraków, Poland<EMAIL_ADDRESS>
###### Abstract.

Let $b\geq 2$ be an integer base with prime factors $p_{1},\ldots,p_{s}$. In
this paper we study sequences of “$b$-adic valuations” and last nonzero digits
in $b$-adic expansions of the values $f(n)=(f_{1}(n),\ldots,f_{s}(n))$, where
each $f_{i}$ is a $p_{i}$-adic analytic function. We give a complete
classification concerning $k$-regularity of these sequences, which generalizes
a result for $b$ prime obtained by Shu and Yao. As an application, we
strengthen a theorem by Murru and Sanna on $b$-adic valuations of Lucas
sequences of the first kind. Moreover, we derive a method to determine
precisely which terms of these sequences can be represented by certain ternary
quadratic forms.

###### Key words and phrases:

$p$-adic valuation, last nonzero digits, $k$-regular sequences, $k$-automatic
sequences, linear recurrence sequences

##  1\. Introduction

Let $k\geq 2$ be an integer. We say that a sequence $\mathbf{a}=(a_{n})_{n\geq
0}$ is $k$-automatic if its $k$-kernel

$\mathcal{K}_{k}(\mathbf{a})=\\{(a_{k^{i}n+j})_{n\geq 0}:i\geq 0,\>0\leq j\leq
k^{j}-1\\}$

is a finite set. Automatic sequences were initially introduced by Cobham [9]
by means of finite automata. Allouche and Shallit [1, 3] generalized this
notion to so-called $k$-regular sequences. When the sequence $\mathbf{a}$
takes values in a ${\mathbb{Z}}$-module $R$, it is said to be $k$-regular if
the ${\mathbb{Z}}$-submodule of $R^{{\mathbb{N}}}$ generated by the $k$-kernel
of $\mathbf{a}$ is finitely generated (we use the convention
${\mathbb{N}}=\\{0,1,2,\ldots\\}$). We say that a sequence is automatic (resp.
regular) if it is $k$-automatic (resp. $k$-regular) for some $k$.

There has been a lot of interest in studying $p$-regularity of sequences of
$p$-adic valuations of subsequent terms of linear recurrence sequences, where
$p$ is prime. For the Fibonacci sequence $(F_{n})_{n\geq 0}$ Lengyel [24]
essentially proved that $(\nu_{p}(F_{n}))_{n\geq 0}$ is $p$-regular for all
primes $p$ (without phrasing it that way). Later Medina and Rowland [28]
computed the rank of this sequence, that is, the rank of the
${\mathbb{Z}}$-submodule generated by its $p$-kernel. Similar results for
general nondegenerate Lucas sequences of the first kind $(u_{n})_{n\geq 0}$,
were obtained by Sanna [33] and Murru, Sanna [30]. Recall that Lucas sequences
of the first kind are defined by $u_{0}=0,u_{1}=1$ and
$u_{n+2}=Au_{n+1}+Bu_{n}$ for $n\in{\mathbb{N}}$, where $A,B\in{\mathbb{Z}}$
are fixed.

Also in [30] the $b$-adic valuation $\nu_{b}$ of the terms $u_{n}$ was
studied, where $\nu_{b}(0)=+\infty$ and for $m\in{\mathbb{Z}}\setminus\\{0\\}$
we define

(1.1) $\nu_{b}(m)=\sup\\{v\geq 0:\ b^{v}\mid m\\}.$

Although $\nu_{b}$ is not a valuation in the strict sense unless $b$ is prime,
we are going use to this abuse of terminology by analogy with $\nu_{p}$. In
the context of the present paper, the following result is particularly
interesting (with the original notation slightly altered).

######  Theorem 1.1 (Murru, Sanna [30]).

If $b\geq 2$ is an integer relatively prime to $B$, then
$(\nu_{b}(u_{n+1}))_{n\geq 0}$ is $b$-regular.

Regularity of $p$-adic valuations of linear recurrence sequences of higher
order has also been investigated. The $2$-adic valuation of a family of
generalized Fibonacci sequences $(T_{n}(k))_{n\geq 0}$ of order $k\geq 2$
turns out to be $2$-regular when $k=3$ or $k$ is even, which quickly follows
from the results of Lengyel and Marques [25, 26] and the author [35]. The more
complicated case of $k\geq 5$ odd and the shifted values $T_{n}(k)+1$ were
studied by Young [39, 40]. Results by Bravo, Díaz, and Ramírez [6] on so-
called Tripell sequence imply that for $p=2,3$ the corresponding sequences of
$p$-adic valuations are $p$-regular.

The results mentioned above (except for Theorem 1.1) illustrate a general
theorem by Shu and Yao [34], stated in the setting of $p$-adic analysis. For a
prime number $p$ let ${\mathbb{Z}}_{p}$ be the ring of $p$-adic integers,
${\mathbb{Q}}_{p}$ its field of fractions, and ${\mathbb{C}}_{p}$ the
topological completion (with respect to the $p$-adic norm $|\cdot|_{p}$) of a
fixed algebraic closure of ${\mathbb{Q}}_{p}$. We say that a function
$f\colon{\mathbb{Z}}_{p}\to{\mathbb{C}}_{p}$ is locally analytic if it can be
expanded into a Taylor series in a neighborhood of any point in
${\mathbb{Z}}_{p}$.

######  Remark 1.1.

In [34] such functions $f$ were simply called analytic. In the present paper,
however, by an analytic function we mean a function $f$ given by a Taylor
series convergent in all ${\mathbb{Z}}_{p}$.

######  Theorem 1.2 (Shu, Yao [34]).

Let $f\colon{\mathbb{Z}}_{p}\to{\mathbb{C}}_{p}$ be a locally analytic
function which does not have any root in ${\mathbb{N}}$. Then the sequence
$(\nu_{p}(f(n)))_{n\geq 0}$ is $p$-regular if and only if all the roots of $f$
in ${\mathbb{Z}}_{p}$ are contained in ${\mathbb{Q}}$.

Using interpolation of linear recurrence sequences (along arithmetic
progressions) by $p$-adic analytic functions combined with Theorem 1.2, Shu
and Yao supplied some easy to check criteria for $p$-regularity of
$(\nu_{p}(s_{n}))_{n\geq 0}$ when $(s_{n})_{n\geq 0}$ is a sequence satisfying
a quadratic linear recurrence. In particular, they managed to prove
$p$-regularity of $p$-adic valuations for Lucas sequences of the first and
second kind for every prime $p$ (without giving explicit formulas).

In view of Theorem 1.1 and the above discussion, it seems natural to try to
extend Theorem 1.2 to any base $b\geq 2$. One of the primary goals of this
paper is to obtain such a generalization. More precisely, let
$p_{1},\ldots,p_{s}$ be the prime factors of $b$ and for $i=1,\ldots,s$ let
$f_{i}\colon{\mathbb{Z}}_{p_{i}}\to{\mathbb{Q}}_{p_{i}}$ be analytic. Assuming
that for all $n\in{\mathbb{N}}$ we have

(1.2) $f_{1}(n)=\cdots=f_{s}(n)\in{\mathbb{Z}}$

and letting $f(n)$ these common values, the terms $\nu_{b}(f(n))$ are well-
defined and for $k\geq 2$ we can study $k$-regularity of the resulting
sequence. However, in the course of our investigation, we have found that the
assumption (1.2) can be relaxed, yielding more general results with simpler
statements. This requires us to give meaning to $\nu_{b}$ evaluated at tuples
of the form $x=(x_{1},\ldots,x_{s})$, where the $i$-th component is a
$p_{i}$-adic number. A precise definition is given in Section 4. Summing up,
we want to answer the following question.

######  Question 1.

Let $f=(f_{1},\ldots,f_{s})$, where for each $i=1,\ldots,s$ the function
$f_{i}\colon{\mathbb{Z}}_{p_{i}}\to{\mathbb{Q}}_{p_{i}}$ is analytic. When is
$(\nu_{b}(f(n)))_{n\geq 0}$ a $k$-regular sequence?

Apart from valuations, we simultaneously consider another family of functions
characterizing base-$b$ expansions, which can be collectively called last
nonzero digits. More precisely, for a fixed integer $d\geq 1$ and any
$n\in{\mathbb{Z}}$ we define

$\mathcal{L}_{b}(n)=\begin{cases}b^{-\nu_{b}(n)}n&\text{if }n\neq 0,\\\
0&\text{if }n=0.\end{cases}$

and

$\ell_{b,d}(n)=\mathcal{L}_{b}(n)\bmod{b^{d}},$

where $x\bmod m$ denotes the remainder of $x\in{\mathbb{Z}}$ from division by
$m$. For example, writing $2400=15040_{6}$ in base $6$, we have
$\nu_{6}(2400)=1,$ and hence

$\displaystyle\mathcal{L}_{6}(2400)$ $\displaystyle=1504_{6}=400,$
$\displaystyle\ell_{6,2}(2400)$ $\displaystyle=04_{6}=4.$

It is clear that for $n\in{\mathbb{N}}$ the value $\mathcal{L}_{b}(n)$ is the
integer represented by deleting all the trailing zeros from the base-$b$
expansion of $n$. Similarly, $\ell_{b,d}(n)$ is represented by the last block
of $d$ digits not ending with $0$. In short, we will write
$\ell_{b}=\ell_{b,1}$ to denote the single last nonzero digit.

A number authors have investigated the behavior of $\ell_{b,d}$, evaluated at
the terms of interesting integer sequences. The most extensively studied
example was the sequence $(\ell_{b,d}(n!))_{n\geq 0}$, with most emphasis put
on its automaticity and the frequencies with which all possible values occur.
One can find relevant results for various values of $b$ and $d$ in the works
of Kakutani [21], Dekking [10], Dresden [15, 16], Deshouillers and Luca [13],
Deshouillers and Ruzsa [14], Deshouillers [11, 12], Lipka [27], the author of
the present paper [36], Byszewski and Konieczny [7]. In all cases the sequence
$(\ell_{b,d}(n!))_{n\geq 0}$ turns out to either be $p$-automatic for some
prime factor $p$ of $b$, or coincide with such a sequence on a set of
asymptotic density $1$. We would like to highlight the result of Deshouillers
and Luca [13] who apply a characterization of last nonzero digits of $n!$ to
deduce how often it can be expressed as a sum of three squares of integers.
This is a natural approach, as by the famous Legendre’s three-square theorem
this condition is equivalent to $\ell_{4,2}(n!)\not\in\\{7,15\\}$.

Last nonzero digits of terms other than $n!$ have been studied as well,
although to a lesser extent. The classification of Fibonacci and Lucas numbers
expressible as a sum of three squares was given by Robbins [31] and
rediscovered by Latushkin and Ushakov [23]. Dresden [16] showed transcendence
of three real numbers, whose decimal expansions are given by
$\ell_{10}(n^{n})$, $\ell_{10}(F_{n})$, $\ell_{10}(n!)$. Grau and Oller-Marcén
[20] essentially proved that the sequence $(\ell_{p}(n^{n}))_{n\geq 0}$ is
$p$-automatic for $p$ prime. Some results on periodicity and automaticity of
last nonzero digits of sequences of combinatorial origin can be found in the
papers by Miska and Ulas [29, Corollary 4.8], and also Ulas and Żmija [38,
Theorems 3.5 and 4.1].

Motivated by the above results, we are interested in the behavior last nonzero
digits of linear recurrence sequences in any base $b$. Under the same premise
as before, our goal is to answer the following questions.

######  Question 2.

When is $(\mathcal{L}_{b}(f(n)))_{n\geq 0}$ a $k$-regular sequence?

######  Question 3.

When is $(\ell_{b,d}(f(n)))_{n\geq 0}$ a $k$-automatic sequence?

We now give an outline of the remainder of the paper. A complete
classification, addressing each of the Questions 1–3, is provided in Section
2. Our results reveal that the answers to all posed questions are intimately
tied to each other. We also give a few simple examples. Section 3 contains
preliminaries on regular and automatic sequences. In Section 4 we extend the
definitions of $\nu_{b},\mathcal{L}_{b},$ and $\ell_{b,d}$ from integers to
tuples of $p$-adic numbers and study their general properties. Section 5 is
dedicated to the applications of our methods and contains more complex
examples. In particular, we generalize Theorem 1.1 and establish an analogous
result for last nonzero digits. Moreover, we provide a general method of
determining which terms of a given Lucas sequence of the first kind can be
expressed as a sum of three squares. The remaining sections are devoted to the
proofs of our main results.

This paper is partially based on a chapter of the author’s PhD thesis [37,
Chapter 3].

##  2\. Main results

Let $b\geq 2$ be an integer base with prime factorization

$b=p_{1}^{l_{1}}p_{2}^{l_{2}}\cdots p_{s}^{l_{s}},$

where $p_{1},\ldots,p_{s}$ are distinct primes, and $l_{1},\ldots l_{s}$
positive integers. Also let $b_{i}=p_{i}^{l_{i}}$ for each $i=1,\ldots,s$.
Consider an $s$-tuple $f=(f_{1},\ldots,f_{s})$, where for each for
$i=1,\ldots,s$ the function
$f_{i}\colon{\mathbb{Z}}_{p_{i}}\to{\mathbb{Q}}_{p_{i}}$ is analytic. Denoting

$\displaystyle{\mathbb{Z}}_{b}$
$\displaystyle={\mathbb{Z}}_{p_{1}}\times\cdots\times{\mathbb{Z}}_{p_{s}},$
$\displaystyle{\mathbb{Q}}_{b}$
$\displaystyle={\mathbb{Q}}_{p_{1}}\times\cdots\times{\mathbb{Q}}_{p_{s}},$

we can treat $f$ as a function from ${\mathbb{Z}}_{b}$ to ${\mathbb{Q}}_{b}$.
We identify ${\mathbb{Q}}$ with its embedding in ${\mathbb{Q}}_{b}$ via the
map $x\mapsto(x,\ldots,x)$, and in the sequel simply write $x$ to denote a
rational element of ${\mathbb{Q}}_{b}$. In particular, when $n\in{\mathbb{N}}$
by $f(n)$ we mean $f(n,\ldots,n)=(f_{1}(n),\ldots,f_{s}(n))$.

We first identify and exclude some degenerate cases from the further
considerations. If all $f_{i}$ are identically zero, then
$\nu_{b}(f(n))=\nu_{b}(0)=+\infty$ and
$\mathcal{L}_{b}(f(n))=\ell_{b,d}(f(n))=0$ for any $d\geq 1$ and all
$n\in{\mathbb{N}}$. The following proposition lets us deal with the situation
when some (but not all) of the $f_{i}$ are zero.

######  Proposition 2.1.

Assume that $f_{i}=0$ for some $i\in\\{1,\ldots,s\\}$ and let
$\overline{b}=b/b_{i}$ and
$\overline{f}=(f_{1},\ldots,f_{i-1},f_{i+1},\ldots,f_{s})$. Then for any
integer $k\geq 2$ we have the following:

  1. (i)

the sequence $(\nu_{b}(f(n)))_{n\geq 0}$ is $k$-regular if and only if
$(\nu_{\overline{b}}(\overline{f}(n)))_{n\geq 0}$ is $k$-regular;

  2. (ii)

the sequence $(\mathcal{L}_{b}(f(n)))_{n\geq 0}$ is $k$-regular if and only if
$(\mathcal{L}_{\overline{b}}(\overline{f}(n)))_{n\geq 0}$ is $k$-regular;

  3. (iii)

the sequence $(\ell_{b,d}(f(n)))_{n\geq 0}$ is $k$-automatic if and only if
$(\ell_{\overline{b},d}(\overline{f}(n)))_{n\geq 0}$ is $k$-automatic.

This motivates us to restrict our attention to the set

$\mathcal{A}_{b}=\\{f=(f_{1},\ldots,f_{s}):\
f_{i}\colon{\mathbb{Z}}_{p_{i}}\to{\mathbb{Q}}_{p_{i}}\text{ is analytic and
}f_{i}\neq 0\text{ for }i=1,\ldots,s\\}.$

Furthermore, it turns out that the sequence $(\mathcal{L}_{b}(f(n)))_{n\geq
0}$ cannot be $k$-regular for any $k\geq 2$ unless all $f_{i}$ are
polynomials.

######  Proposition 2.2.

Let $f=(f_{1},\ldots,f_{s})\in\mathcal{A}_{b}$ be such that the sequence
$(\mathcal{L}_{b}(f(n)))_{n\geq 0}$ is regular. Then for each $i=1,\ldots,s$
the function $f_{i}$ is a polynomial.

Therefore, we distinguish a subset $\mathcal{P}_{b}\subset\mathcal{A}_{b}$
consisiting of $s$-tuples of polynomials:

$\mathcal{P}_{b}=\\{f=(f_{1},\ldots,f_{s})\in\mathcal{A}_{b}:\
f_{i}\in{\mathbb{Q}}_{p_{i}}[X]\text{ for }i=1,\ldots,s\\}.$

We introduce some further notation and terminology needed to state our
results. For a prime $p$ and an analytic function
$f\colon{\mathbb{Z}}_{p}\to{\mathbb{Q}}_{p}$ we let
$\mathcal{R}_{f}\subset{\mathbb{Z}}_{p}$ denote the set of $p$-adic integer
roots of $f$. By virtue of Strassman’s Theorem (see [19, Theorem 4.4.6]) this
set is finite. Also for any $\theta\in\mathcal{R}_{f}$ we define
$m_{f}(\theta)$ to be the multiplicity of $\theta$ as a root of $f$. In
general, when $f=(f_{1},\ldots,f_{s})\in\mathcal{A}_{b}$ we let
$\mathcal{R}_{f}=\mathcal{R}_{f_{1}}\times\cdots\times\mathcal{R}_{f_{s}}\subset{\mathbb{Z}}_{b}$.

In the statements of our main results we adhere to a classification which
follows from the celebrated theorem of Cobham [8] and its generalization by
Bell [4] (both formulated as a part of Proposition 3.1 below). More precisely,
a sequence $(a_{n})_{n\geq 0}$ can be:

  1. (a)

$k$-regular for all $k\geq 2$;

  2. (b)

$k$-regular for some $k$ and not $m$-regular for $m$ multiplicatively
independent with $k$;

  3. (c)

not regular.

In particular, this distinction holds for automatic sequences and the result
of Cobham says that in the case (a) such a sequence $(a_{n})_{n\geq 0}$ must
be eventually periodic. In the sequel we say that a sequence is strictly
$k$-regular if it falls under case (b). Similarly, we consider strictly
$k$-automatic sequences. We point out that this is not standard terminology.

######  Remark 2.1.

When talking about an eventually periodic sequence $(a_{n})_{n\geq 0}$, by its
period we mean any positive integer $T$ such that $a_{n+T}=a_{n}$ for all
sufficiently large $n\in{\mathbb{N}}$. Unless specified otherwise, $T$ is not
assumed to be minimal.

We are now ready to to give the main results of this paper, answering the
questions in Section 1. The statements are split into two parts, depending on
whether $b$ is a prime power or has several prime factors. We start with the
sequence $(\nu_{b}(f(n)))_{n\geq 0}$.

######  Theorem 2.3.

Assume that $b=p^{l}$ is a prime power and let $f\in\mathcal{A}_{p}$. Then the
sequence $(\nu_{p^{l}}(f(n)))_{n\geq 0}$ is

  1. (a)

periodic if $\mathcal{R}_{f}=\varnothing$, where a power of $p$ can be chosen
as a period;

  2. (b)

strictly $p$-regular if $\varnothing\neq\mathcal{R}_{f}\subset{\mathbb{Q}}$;

  3. (c)

not regular if $\mathcal{R}_{f}\not\subset{\mathbb{Q}}$.

In particular, the above conditions are independent of $l$.

For $l=1$ this is a generalization of Theorem 1.2 for functions
$f\colon{\mathbb{Z}}_{p}\to{\mathbb{Q}}_{p}$ in the sense that $k$-regularity
of $(\nu_{p}(f(n)))_{n\geq 0}$ is considered for all $k\geq 2$.

######  Theorem 2.4.

Assume that $b$ has $s\geq 2$ prime factors and let
$f=(f_{1},\ldots,f_{s})\in\mathcal{A}_{b}$. Then the sequence
$(\nu_{b}(f(n)))_{n\geq 0}$ is

  1. (a)

periodic if $\mathcal{R}_{f}=\varnothing$, where a power of $b$ can be chosen
as a period;

  2. (b)

strictly $k$-regular if $\mathcal{R}_{f}=\\{\theta\\}$ for some
$\theta\in{\mathbb{Q}}\cap{\mathbb{Z}}_{b}$, where $k=b_{1}^{w_{1}}\cdots
b_{s}^{w_{s}}$ and $w_{1},\ldots,w_{s}$ are positive integers satisfying

$w_{1}m_{f_{1}}(\theta)=\cdots=w_{s}m_{f_{s}}(\theta);$

  3. (c)

not regular otherwise.

The particular choice of $w_{1},\ldots,w_{s}$ satisfying the equality in
Theorem 2.4 is irrelevant because a $k$-regular sequence is also
$k^{\prime}$-regular when $k,k^{\prime}$ are powers of the same positive
integer (see Proposition 3.1(i) below).

######  Remark 2.2.

In contrast to Theorem 1.2, here and in the sequel we choose to allow $f$ to
have roots in ${\mathbb{N}}$ even though $\nu_{b}(0)=+\infty$. One can omit
this problem entirely by replacing the (finitely many) zeros in $(f(n))_{n\geq
0}$ with arbitrary values or by shifting this sequence by a sufficiently large
integer. Proposition 3.2 below guarantees that these operations do not affect
regularity of $(\nu_{b}(f(n)))_{n\geq 0}$.

We move on to regularity of the sequence $(\mathcal{L}_{b}(f(n)))_{n\geq 0}$.
In the case $b=p^{l}$ the conditions on the roots of $f$ determining which of
the cases (a)–(c) holds, are exactly the same as in the preceding two results.

######  Theorem 2.5.

Assume that $b=p^{l}$ is a prime power and let $f\in\mathcal{P}_{p}$. Then the
sequence $(\mathcal{L}_{p^{l}}(f(n)))_{n\geq 0}$ is

  1. (a)

$k$-regular for every $k\geq 2$ if $\mathcal{R}_{f}=\varnothing$;

  2. (b)

strictly $p$-regular if $\varnothing\neq\mathcal{R}_{f}\subset{\mathbb{Q}}$;

  3. (c)

not regular if $\mathcal{R}_{f}\not\subset{\mathbb{Q}}$.

In particular, the above conditions are independent of $l$.

When $b$ has several prime factors, in order to have strict regularity of the
sequence we additionally need the multiplicities of $m_{f_{i}}(\theta)$ to be
equal.

######  Theorem 2.6.

Assume that $b$ has $s\geq 2$ prime factors and let
$f=(f_{1},\ldots,f_{s})\in\mathcal{P}_{b}$. Then the sequence
$(\mathcal{L}_{b}(f(n)))_{n\geq 0}$ is

  1. (a)

$k$-regular for every $k\geq 2$ if $\mathcal{R}_{f}=\varnothing$;

  2. (b)

strictly $b$-regular if $\mathcal{R}_{f}=\\{\theta\\}$ for some
$\theta\in{\mathbb{Q}}\cap{\mathbb{Z}}_{b}$ and

$m_{f_{1}}(\theta)=\cdots=m_{f_{s}}(\theta);$

  3. (c)

not regular otherwise.

The third and final pair of results concerns automaticity of the sequence
$(\ell_{b,d}(f(n)))_{n\geq 0}$. The situation turns out to be a bit more
complicated when $b=p^{l}$ is a prime power. Consider a function
$f\in\mathcal{A}_{p}$. For each $\theta\in\mathcal{R}_{f}$ let
$g_{\theta}\in\mathcal{A}_{p}$ be defined by

$f(x)=(x-\theta)^{m_{f}(\theta)}g_{\theta}(x)$

for all $x\in{\mathbb{Z}}_{p}$. Let $\lambda$ denote the Carmichael function.
Recall that for a positive integer $n$ the value $\lambda(n)$ is the smallest
positive integer $m$ such that $a^{m}\equiv 1\pmod{n}$ for all integers $a$
coprime with $n$. In particular, for a prime $p$ and exponent $t\geq 1$ we
have

$\lambda(p^{t})=\begin{cases}p^{t-1}(p-1)&\text{if }p\geq 3,\\\
2^{t-2}&\text{if }p=2,t\geq 3,\\\ 2^{t-1}&\text{if }p=2,t\leq 2.\end{cases}$

Consider the subset
$\mathcal{R}^{\prime}_{f}=\mathcal{R}^{\prime}_{f}(l,d)\subset\mathcal{R}_{f}$,
given by

$\mathcal{R}^{\prime}_{f}(l,d)=\\{\theta\in\mathcal{R}_{f}:l\nmid
m_{f}(\theta)\text{ or
}\lambda(p^{ld-\nu_{p}(g_{\theta}(\theta))\bmod{l}})\nmid m_{f}(\theta)\\}.$

In the case $l=1$ we obtain a simpler form

$\mathcal{R}^{\prime}_{f}(1,d)=\\{\theta\in\mathcal{R}_{f}:\lambda(p^{d})\nmid
m_{f}(\theta)\\}.$

In a sense, the set $\mathcal{R}_{f}\setminus\mathcal{R}^{\prime}_{f}$
contains the roots $\theta$ such that the factor $(n-\theta)^{m_{f}(\theta)}$
has no effect on automaticity of $(\ell_{p^{l},d}(f(n)))_{n\geq 0}$. It is
then no surprise that compared to the previous statements, the set
$\mathcal{R}^{\prime}_{f}$ essentially replaces $\mathcal{R}_{f}$.

######  Theorem 2.7.

Assume that $b=p^{l}$ is a prime power, $d\geq 1$ an integer, and let
$f\in\mathcal{A}_{p}$. Then the sequence $(\ell_{p^{l},d}(f(n)))_{n\geq 0}$ is

  1. (a)

periodic if $\mathcal{R}^{\prime}_{f}=\varnothing$, where a power of $p$ can
be chosen as a period;

  2. (b)

strictly $p$-automatic if
$\varnothing\neq\mathcal{R}^{\prime}_{f}\subset{\mathbb{Q}}$;

  3. (c)

not automatic if $\mathcal{R}^{\prime}_{f}\not\subset{\mathbb{Q}}$.

When $b$ has several prime factors, the classification again mirrors the one
in the earlier theorems.

######  Theorem 2.8.

Assume that $b$ has $s\geq 2$ prime factors and let
$f=(f_{1},\ldots,f_{s})\in\mathcal{A}_{b}$. Let $d\geq 1$ be an integer. Then
the sequence $(\ell_{b,d}(f(n)))_{n\geq 0}$ is

  1. (a)

periodic if $\mathcal{R}_{f}=\varnothing$, where a power of $b$ can be chosen
as a period;

  2. (b)

strictly $k$-automatic if $\mathcal{R}_{f}=\\{\theta\\}$ for some
$\theta\in{\mathbb{Q}}\cap{\mathbb{Z}}_{b}$, where $k=b_{1}^{w_{1}}\cdots
b_{s}^{w_{s}}$ and $w_{1},\ldots,w_{s}$ are positive integers satisfying

$w_{1}m_{f_{1}}(\theta)=\cdots=w_{s}m_{f_{s}}(\theta);$

  3. (c)

not automatic otherwise.

In particular, the above conditions are independent of $d$.

The proofs of all the theorems stated in this section as well as Propositions
2.1 and 2.2 are provided in Sections 6 and 7.

As a corollary, we can relate $b$-regularity of the sequences
$(\nu_{b}(f(n)))_{n\geq 0}$, $(\mathcal{L}_{b}(f(n)))_{n\geq 0}$, and
$(\ell_{b,d}(f(n)))_{n\geq 0}$ for any base $b\geq 2$.

######  Corollary 2.9.

Assume that $b=p^{l}$ is a prime power and let $f\in\mathcal{A}_{p}$. Then the
following conditions are equivalent:

  1. (i)

$\mathcal{R}_{f}\subset{\mathbb{Q}}$;

  2. (ii)

the sequence $(\nu_{p^{l}}(f(n)))_{n\geq 0}$ is $p$-regular;

  3. (iii)

for all $d\geq 1$ the sequence $(\ell_{p^{l},d}(f(n)))_{n\geq 0}$ is
$p$-automatic.

If additionally $f\in\mathcal{P}_{p}$, then the above conditions are also
equivalent to the following:

  1. (iv)

the sequence $(\mathcal{L}_{p^{l}}(f(n)))_{n\geq 0}$ is $p$-regular.

###### Proof.

The condition (i) is equivalent with (ii) and (iv) (when
$f\in\mathcal{P}_{p}$). Moreover, as a consequence of Theorem 2.7, we have
that (iii) follows from (i), and it remains to prove the converse. By the same
result, (iii) implies that $\mathcal{R}^{\prime}_{f}(l,d)\subset{\mathbb{Q}}$
for all $d\geq 1$. Observe that for all sufficiently large $d$ the condition
$\lambda(p^{ld})\nmid p^{\nu_{p}(g_{\theta}(\theta))\bmod{l}}m_{f}(\theta)$ in
the definition of $\mathcal{R}^{\prime}_{f}(l,d)$ is always satisfied, so
$\mathcal{R}_{f}=\mathcal{R}^{\prime}_{f}(l,d)\subset{\mathbb{Q}}$. ∎

######  Corollary 2.10.

Assume that $b$ has $s\geq 2$ prime factors and let
$f=(f_{1},\ldots,f_{s})\in\mathcal{A}_{b}$. Then the following conditions are
equivalent:

  1. (i)

either $\mathcal{R}_{f}=\varnothing$ or $\mathcal{R}_{f}=\\{\theta\\}$ and
$m_{f_{1}}(\theta)=\cdots=m_{f_{s}}(\theta)$ for some
$\theta\in{\mathbb{Q}}\cap{\mathbb{Z}}_{b}$;

  2. (ii)

the sequence $(\nu_{b}(f(n)))_{n\geq 0}$ is $b$-regular;

  3. (iii)

for all $d\geq 1$ the sequence $(\ell_{b,d}(f(n)))_{n\geq 0}$ is
$b$-automatic.

If additionally $f\in\mathcal{P}_{b}$, then the above conditions are also
equivalent to the following:

  1. (iv)

the sequence $(\mathcal{L}_{b}(f(n)))_{n\geq 0}$ is $b$-regular.

###### Proof.

Equivalence of (i) to all other conditions follows immediately from parts (a),
(b) of Theorems 2.4, 2.6, and 2.8. ∎

We now briefly discuss some implications of our results and provide a few
simple examples. First, for two bases $b,b^{\prime}$ having the same set of
prime factors we obtain $\mathcal{A}_{b}=\mathcal{A}_{b^{\prime}}$. It is
natural to ask whether replacing $b$ with $b^{\prime}$ in
$\nu_{b},\mathcal{L}_{b}$, and $\ell_{b,d}$ results in a different behavior of
the considered sequences, in terms of their regularity. When $b$ has at least
two prime factors we see that such a modification does not affect which of the
cases (a)–(c) in Theorems 2.4, 2.6, and 2.8 holds. Only the value of $k$ in
the case (b) may change, as demonstrated by the following example.

######  Example 2.1.

Let $b=50=2\cdot 5^{2},b^{\prime}=20=2^{2}\cdot 5$ and define
$f=(f_{1},f_{2})\in\mathcal{P}_{10}$ by $f(x,y)=(x,y^{2})$ for
$(x,y)\in{\mathbb{Z}}_{2}\times{\mathbb{Z}}_{5}={\mathbb{Z}}_{10}$. We see
that $\mathcal{R}_{f}=\\{0\\}$, so case (b) of Theorems 2.4 and 2.8 holds.
Following the notation of these results, we have $m_{f_{1}}(0)=1$ and
$m_{f_{2}}(0)=2$, so taking $w_{1}=2$ and $w_{1}=1$, we obtain
$m_{f_{1}}(0)w_{1}=m_{f_{2}}(0)w_{2}$. It follows that the sequence
$(\nu_{50}(f(n)))_{n\geq 0}$ is strictly $100$-regular (equivalently, strictly
$10$-regular), while $(\nu_{20}(f(n)))_{n\geq 0}$ is strictly $80$-regular. We
obtain similar results concerning automaticity of $(\ell_{50,d}(f(n)))_{n\geq
0}$ and $(\ell_{20,d}(f(n)))_{n\geq 0}$ for any $d\geq 1$. On the other hand,
neither $(\mathcal{L}_{50}(f(n)))_{n\geq 0}$, nor
$(\mathcal{L}_{20}(f(n)))_{n\geq 0}$ are regular, since the multiplicities
$m_{f_{1}}(0)=1$ and $m_{f_{2}}(0)=2$ are not equal.

When $b=p^{l}$ is a prime power, replacing $b$ with any other power of $p$ has
no effect on regularity in the case of the functions
$\nu_{b},\mathcal{L}_{b}$. However, in Example 2.2 below we show that the case
of $\ell_{p^{l},d}$ is different, namely modifying $l,d$ may even turn a
periodic into a nonautomatic sequence (and vice versa). To this end, recall
that for a prime $p\geq 3$, a $p$-adic integer $\sigma$ with
$\nu_{p}(\sigma)=0$ is a square in ${\mathbb{Z}}_{p}$ if and only if
$\sigma\bmod{p}$ is a square in the finite field $\mathbb{F}_{p}$. In the case
$p=2$ a sufficient and necessary condition is that $\sigma\equiv 1\pmod{8}$.
This fact follows directly from the famous Hensel’s Lemma and a proof can be
found in [32, p. 50].

######  Example 2.2.

Let $p=5$, and $f(x)=5(x^{2}+1)^{4}\in\mathcal{P}_{5}$. By the above
discussion $-1$ is a square in ${\mathbb{Z}}_{5}$ so $f$ has irrational roots
$\theta,-\theta\in{\mathbb{Z}}_{5}$ of multiplicity $4$. One can quickly check
that $\mathcal{R}^{\prime}_{f}(l,d)=\varnothing$ if and only if
$(l,d)\in\\{(1,1),(2,1)\\}$, and otherwise
$\mathcal{R}^{\prime}_{f}(l,d)=\\{\theta,-\theta\\}\not\subset{\mathbb{Q}}$.
Therefore, for example the sequence $(\ell_{5^{2}}(f(n)))_{n\geq 0}$ is
periodic but $(\ell_{5,2}(f(n)))_{n\geq 0}$ is not automatic.

One may also wonder how regularity of $(\nu_{b}(f(n)))_{n\geq 0}$ relates to
regularity of the sequences $(\nu_{b_{i}}(f_{i}(n)))_{n\geq 0}$ for
$i=1,\ldots,s$. A similar question can also be asked, concering the functions
$\mathcal{L}_{b}$ and $\ell_{b,d}$. In this regard, the following simple
example was at first quite unexpected to the author.

######  Example 2.3.

Let $f(x)=x(x+1)$. Then the sequence $(\nu_{p^{l}}(f(n)))_{n\geq 0}$ is
$p$-regular for all prime powers $p^{l}$. However, $(\nu_{b}(f(n)))_{n\geq 0}$
is not regular for any base $b$ having at least two prime factors.

On the other hand, knowing that $(\nu_{b}(f(n)))_{n\geq 0}$ is strictly
$k$-regular for some $k$, we can infer from part (b) of Theorems 2.4 and 2.3
that all the sequences $(\nu_{b_{i}}(f_{i}(n)))_{n\geq 0}$ are strictly
$p_{i}$-regular. However, if $(\nu_{b}(f(n)))_{n\geq 0}$ is $k$-regular for
all $k\geq 2$, then only one of $(\nu_{b_{i}}(f_{i}(n)))_{n\geq 0}$ is
guaranteed to be $p_{i}$-regular (strictly or not). In the following example
we show that this implication cannot be strengthened.

######  Example 2.4.

Let $b=10$ and consider the polynomial $f(x)=x^{2}+1$. Then $f$ has an
irrational root in ${\mathbb{Z}}_{5}$ but no root in ${\mathbb{Z}}_{2}$.
Hence, $(\nu_{10}(f(n)))_{n\geq 0}$ is $k$-regular for every $k\geq 2$.
However, out of the two sequences $(\nu_{2}(f(n)))_{n\geq 0}$ and
$(\nu_{5}(f(n)))_{n\geq 0}$, only the former is regular. Analogous
observations can be made concerning $\mathcal{L}_{b}$ and $\ell_{b,d}$.

Finally, our results allow to easily produce examples of sequences with values
in ${\mathbb{Z}}_{b}$ whose reductions modulo $b^{d}$ are automatic, but which
are not regular themselves.

######  Example 2.5.

The sequence $(\mathcal{L}_{10}(n,n^{2}))_{n\geq
0}\subset{\mathbb{Z}}_{10}={\mathbb{Z}}_{2}\times{\mathbb{Z}}_{5}$ is not
regular. On the other hand, for each $d\geq 1$ its reduction modulo $10^{d}$,
namely $(\ell_{10,d}(n,n^{2}))_{n\geq 0}$, is $20$-automatic.

##  3\. Preliminaries on automatic and regular sequences

In this section we recall some standard facts concerning automatic and regular
sequences which will be essential in proving our main results. Whenever
regular sequences are concerned, we implicitly assume their terms belong to a
${\mathbb{Z}}$-module. For a more detailed treatment of the topic we refer the
reader to the monograph of Allouche and Shallit [2] and their papers [1, 3].

To begin, any $k$-automatic sequence is $k$-regular. Conversely, a $k$-regular
sequence which takes on only finitely many values is $k$-automatic. Hence, the
results below stated for regular sequences also apply to automatic sequences.

The following proposition justifies the case distinction in the theorems in
Section 2, where the first part of (ii) is the celebrated theorem by Cobham
[8], while (iii) can be extracted from the results of Bell [4].

######  Proposition 3.1.

Let $\mathbf{a}=(a_{n})_{n\geq 0}$ be a sequence and $k,l\geq 2$
multiplicatively independent integers. We have the following.

  1. (i)

For any integer $t\geq 1$ the sequence $\mathbf{a}$ is $k$-regular if and only
if it is $k^{t}$-regular.

  2. (ii)

If $\mathbf{a}$ is simultaneously $k$\- and $l$-automatic, then it is
eventually periodic. Conversely, if $\mathbf{a}$ is eventually periodic, then
it is $m$-automatic for all $m\geq 2$.

  3. (iii)

If $\mathbf{a}$ is simultaneously $k$\- and $l$-regular, then it is
$m$-regular for all $m\geq 2$.

We move on to closure properties of automatic and regular sequences. It is
known that changing a finite number of terms in a $k$-regular sequence again
yields a $k$-regular sequence. We can also relate $k$-regularity of a sequence
and its subsequences along arithmetic progressions.

######  Proposition 3.2.

Let $(a_{n})_{n\geq 0}$ be a sequence and $b\geq 1$, $k\geq 2$ integers. We
have the following.

  1. (i)

If $(a_{n})_{n\geq 0}$ is $k$-regular, then for each $c\in{\mathbb{Z}}$ the
subsequence $(a_{bn+c})_{n\geq 0}$ is $k$-regular (arbitrary values can be
assigned to terms with $bn+c<0$).

  2. (ii)

If for each $c=0,1,\ldots,b-1$ the subsequence $(a_{bn+c})_{n\geq 0}$ is
$k$-regular, then $(a_{n})_{n\geq 0}$ is $k$-regular.

We now look at term-wise operations which preserve regularity.

######  Proposition 3.3.

Let $(a_{n})_{n\geq 0}$ and $(b_{n})_{n\geq 0}$ be sequences taking values in
a set $R$ and let $k\geq 2$ an integer. Then we have the following.

  1. (i)

If $(a_{n})_{n\geq 0}$ is $k$-automatic, then for any set $\Delta$ and
function $\rho\colon R\to\Delta$ the sequence $(\rho(a_{n}))_{n\geq 0}$ is
$k$-automatic.

  2. (ii)

If $(a_{n})_{n\geq 0}$ is $k$-regular and $\phi\colon R\to S$ is a
homomorphism of ${\mathbb{Z}}$-modules, then the sequence
$(\phi(a_{n}))_{n\geq 0}$ is $k$-regular.

  3. (iii)

If $(a_{n})_{n\geq 0}$ and $(b_{n})_{n\geq 0}$ are $k$-regular and $R$ is a
commutative ring, then for any $\lambda\in R$ the sequences $(\lambda
a_{n})_{n\geq 0}$, $(a_{n}+b_{n})_{n\geq 0}$, and $(a_{n}b_{n})_{n\geq 0}$ are
also $k$-regular.

  4. (iv)

The sequence $((a_{n},b_{n}))_{n\geq 0}$ is $k$-regular if and only if both
$(a_{n})_{n\geq 0}$ and $(b_{n})_{n\geq 0}$ are $k$-regular.

We have not found a suitable reference for the parts (ii) and (iv) of
Proposition 3.3, however these assertions quickly follow from the definition
of a $k$-regular sequence. Finally, we state two corollaries which will be
used often in our considerations.

######  Corollary 3.4.

Let $(a_{n})_{n\geq 0}$ be a $k$-regular sequence taking values in
${\mathbb{Z}}_{b}$. Then for all integers $m\geq 1$ the sequence $(a_{n}\bmod
b^{m})_{n\geq 0}$ is $k$-automatic.

######  Corollary 3.5.

Let $R$ be a commutative ring and $f\in R[X]$. Then the sequence
$(f(n))_{n\geq 0}$ is $k$-regular for every $k\geq 2$.

##  4\. Basic properties of last nonzero digits

Let $d\geq 1$ and $b\geq 2$ be integers. As in Section 2, write the prime
factorization of $b$ as

$b=p_{1}^{l_{1}}\cdots p_{s}^{l_{s}},$

where $p_{1},\ldots,p_{s}$ are distinct primes, and $l_{1},\ldots l_{s}$
positive integers. Also let $b_{i}=p_{i}^{l_{i}}$ for each $i=1,\ldots,s$. Our
first goal is to extend the defininiton of the functions
$\nu_{b},\mathcal{L}_{b}$, and $\ell_{b,d}$ to the product ring

${\mathbb{Q}}_{b}={\mathbb{Q}}_{p_{1}}\times\cdots\times{\mathbb{Q}}_{p_{s}}.$

We note that ${\mathbb{Q}}_{b}$ only depends on the set of prime factors of
$b$, in particular ${\mathbb{Q}}_{p^{l}}={\mathbb{Q}}_{p}$ for $p$ prime. Also
recall that

${\mathbb{Z}}_{b}={\mathbb{Z}}_{p_{1}}\times\cdots\times{\mathbb{Z}}_{p_{s}}$

and that we identify $x\in{\mathbb{Q}}$ with
$(x,\ldots,x)\in{\mathbb{Q}}_{b}$.

######  Remark 4.1.

The ring ${\mathbb{Z}}_{b}$ is usually defined as the inverse limit
$\varprojlim{\mathbb{Z}}/b^{n}{\mathbb{Z}}$ (see [17, 18], cf. [22, pp. 47–50]
for another approach). Equipping each ${\mathbb{Z}}/b^{n}{\mathbb{Z}}$ with
the discrete topology, we obtain an isomorphism of topological rings
${\mathbb{Z}}_{b}\simeq{\mathbb{Z}}_{p_{1}}\times\cdots\times{\mathbb{Z}}_{p_{s}}$,
which extends to a natural isomorphism
$\pi_{b}\colon{\mathbb{Q}}_{b}\to{\mathbb{Q}}_{p_{1}}\times\cdots\times{\mathbb{Q}}_{p_{s}}$.
The elements of ${\mathbb{Q}}_{b}$ can in turn be identified with $b$-adic
expansions

$x=\cdots+a_{2}b^{2}+a_{1}b+a_{0}+a_{-1}b^{-1}+\cdots+a_{-m}b^{-m},$

where $a_{j}\in\\{0,1,\ldots,b-1\\}$ and $m\in{\mathbb{N}}$. In particular,
$x\in{\mathbb{Z}}_{b}$ if and only if $a_{j}=0$ for all $j<0$. The isomorphism
$\pi_{b}$ thus induces the functions
$\widetilde{\nu}_{b}=\nu_{b}\circ\pi_{b}$,
$\widetilde{\mathcal{L}}_{b}=\mathcal{L}_{b}\circ\pi_{b}$, and
$\widetilde{\ell}_{b,d}=\ell_{b,d}\circ\pi_{b}$ defined for $b$-adic
expansions. It can be checked that $\widetilde{\mathcal{L}}_{b}$ and
$\widetilde{\ell}_{b,d}$ (and consequently $\mathcal{L}_{b}$ and $\ell_{b,d}$)
retain the original interpretation concerning last nonzero digits. Keeping
this in mind, we choose to identify ${\mathbb{Q}}_{b}$ with
${\mathbb{Q}}_{p_{1}}\times\cdots\times{\mathbb{Q}}_{p_{s}}$ for the sake of
calculations, as we find it more convenient to deal with tuples of $p$-adic
numbers.

For any $x=(x_{1},\ldots,x_{s})\in{\mathbb{Q}}_{b}$ let

$\nu_{b}(x)=\min_{1\leq i\leq s}\nu_{b_{i}}(x_{i})=\min_{1\leq i\leq
s}\left\lfloor\frac{\nu_{p_{i}}(x_{i})}{l_{i}}\right\rfloor,$

where $\lfloor\cdot\rfloor$ denotes the floor function. It can be easily
checked that for any integer $n$ the value $\nu_{b}(n)$ coincides with the
original definition (1.1). By reduction $x\bmod{b^{d}}$ of
$x=(x_{1},\ldots,x_{s})\in{\mathbb{Z}}_{b}$ we mean the unique solution
$y\in\\{0,1,\ldots,b^{d}-1\\}$ to the system of congruences

$\begin{cases}y\equiv x_{1}\pmod{b_{1}^{d}},\\\ \quad\vdots\\\ y\equiv
x_{s}\pmod{b_{s}^{d}}.\\\ \end{cases}$

More explicitly, if we put $q_{i}=b/b_{i}$, $y_{i}=x_{i}$, and let $r_{i}$ be
an integer satisfying $q_{i}r_{i}\equiv 1\pmod{b_{i}^{d}}$, then for any
$x=(x_{1},\ldots,x_{s})\in{\mathbb{Z}}_{b}$ we have

(4.1) $x\bmod{b^{d}}=\sum_{i=1}^{s}q_{i}^{d}r_{i}^{d}y_{i}\bmod{b^{d}}.$

Having extended $\nu_{b}$ to ${\mathbb{Q}}_{b}$, we can now define in general
the functions $\mathcal{L}_{b}\colon{\mathbb{Q}}_{b}\to{\mathbb{Z}}_{b}$ and
$\ell_{b,d}\colon{\mathbb{Q}}_{b}\to{\mathbb{Z}}/b^{d}{\mathbb{Z}}$ precisely
as Section 1, namely

$\displaystyle\mathcal{L}_{b}(x)$
$\displaystyle=\begin{cases}b^{-\nu_{b}(x)}x&\text{if }x\neq 0,\\\ 0&\text{if
}x=0,\end{cases}$ $\displaystyle\ell_{b,d}(x)$
$\displaystyle=\mathcal{L}_{b}(x)\bmod{b^{d}}.$

In the following two propositions we give some immediate properties of the
$b$-adic valuation and last nonzero digits.

######  Proposition 4.1.

For any $x,y\in{\mathbb{Q}}_{b}$ we have the following:

  1. (i)

$\nu_{b}(xy)\geq\nu_{b}(x)+\nu_{b}(y)$;

  2. (ii)

if $b=p^{l}$ is a prime power, then $\nu_{b}(xy)\leq\nu_{b}(x)+\nu_{b}(y)+1$;

  3. (iii)

$\nu_{b}(x+y)\geq\min\\{\nu_{b}(x),\nu_{b}(y)\\}$ with equality if
$\nu_{b}(x)\neq\nu_{b}(y)$.

######  Proposition 4.2.

For any $x,y\in{\mathbb{Q}}_{b}$ we have the following:

  1. (i)

$\mathcal{L}_{b}(bx)=\mathcal{L}_{b}(x)$ and $\ell_{b,d}(bx)=\ell_{b,d}(x)$;

  2. (ii)

if $\nu_{b}(xy)=\nu_{b}(x)+\nu_{b}(y),$ then

$\displaystyle\mathcal{L}_{b}(xy)$
$\displaystyle=\mathcal{L}_{b}(x)\mathcal{L}_{b}(y),$
$\displaystyle\ell_{b,d}(xy)$
$\displaystyle\equiv\ell_{b,d}(x)\ell_{b,d}(y)\pmod{b^{d}}.$

Observe that the assumption of Proposition 4.2(ii) is always satisfied for $b$
prime.

In the following proposition we show how to express the function $\ell_{b,d}$
in terms of $\ell_{b_{i},d}$. Here and in the sequel we use the convention

(4.2) $m^{+\infty}\equiv 0\pmod{m^{d}}$

for any integers $d,m\geq 1$.

######  Proposition 4.3.

Let $x=(x_{1},\ldots,x_{s})\in{\mathbb{Q}}_{b}\setminus\\{0\\}$. Then for each
$i=1,\ldots,s$ we have

(4.3) $\ell_{b,d}(x)\equiv
b_{i}^{\nu_{b_{i}}(x_{i})-\nu_{b}(x)}r_{i}^{\nu_{b}(x)}\ell_{b_{i},d}(x_{i})\pmod{b_{i}^{d}}.$

Moreover, for any prime number $p$, integer $l\geq 1$, and nonzero
$x\in{\mathbb{Q}}_{p}$ we have

$\displaystyle\mathcal{L}_{p^{l}}(x)$
$\displaystyle=\mathcal{L}_{p}(x)p^{\nu_{p}(x)\bmod{l}},$
$\displaystyle\ell_{p^{l},d}(x)$
$\displaystyle\equiv\ell_{p,ld}(x)p^{\nu_{p}(x)\bmod{l}}\pmod{p^{ld}}.$

###### Proof.

By definition, for each $i=1,\ldots,s$ we have

$\ell_{b,d}\equiv b^{-\nu_{b}(x)}x_{i}\pmod{b_{i}^{d}}.$

The right-hand side can be written as

$b^{-\nu_{b}(x)}x_{i}=\begin{cases}b_{i}^{\nu_{b_{i}}(x_{i})-\nu_{b}(x)}q_{i}^{-\nu_{b}(x)}\mathcal{L}_{b_{i}}(x_{i})&\text{if
}x_{i}\neq 0,\\\ 0&\text{if }x_{i}=0.\end{cases}$

After reducing modulo $b_{i}^{d}$ the two cases can be merged into one by the
convention (4.2) with $m=b_{i}$, and thus (4.3) follows.

In order to prove the second part of the statement, we write
$\nu_{p}(x)=l\nu_{p^{l}}(x)+u$, where $0\leq u\leq l-1$. We have

$\mathcal{L}_{p^{l}}(x)=\left(p^{-(l\nu_{p^{l}}(x)+u)}x\right)p^{u}=\mathcal{L}_{p}(x)p^{u},$

as desired. Reduction modulo $p^{ld}$ gives the corresponding formula for
$\ell_{p^{l},d}(x)$. ∎

By the equality (4.1), we obtain an explicit expression:

(4.4) $\displaystyle\ell_{b,d}(x)$
$\displaystyle\equiv\sum_{i=1}^{s}b_{i}^{\nu_{b_{i}}(x_{i})-\nu_{b}(x)}q_{i}^{d}r_{i}^{\nu_{b}(x)+d}\ell_{b_{i},d}(x_{i})\pmod{b^{d}}$
$\displaystyle\equiv\sum_{i=1}^{s}p_{i}^{\nu_{p_{i}}(x_{i})-l_{i}\nu_{b}(x)}q_{i}^{d}r_{i}^{\nu_{b}(x)+d}\ell_{p_{i},l_{i}d}(x_{i})\pmod{b^{d}}.$

The following immediate corollary of Proposition 4.3 will be very important
later.

######  Corollary 4.4.

Let $x=(x_{1},\ldots,x_{s})\in{\mathbb{Q}}_{b}$ be nonzero and fix
$j\in\\{1,\ldots,s\\}$. Then $\nu_{b_{j}}(\ell_{b}(x))=0\text{ if and only if
}\nu_{b_{j}}(x_{j})=\nu_{b}(x).$

Combining this with Proposition 3.3(i), we deduce that $k$-automaticity of
$(\ell_{b}(f(n)))_{n\geq 0}$ for some $k$ implies $k$-automaticity of the
characteristic sequence of the set

$\\{n\in{\mathbb{N}}:\ \nu_{b_{j}}(f(n))>\nu_{b}(f(n))\\}.$

We conclude this section by showing $b$-regularity of $(\nu_{b}(n))_{n\geq 0}$
and $(\mathcal{L}_{b}(n))_{n\geq 0}$, as well as $b$-automaticity of
$(\ell_{b,d}(n))_{n\geq 0}$. This is a special case of the results in Section
2. As already mentioned in Remark 2.2, we are not concerned with the fact that
$\nu_{b}(0)=+\infty$, as this term can be replaced with any value without
affecting regularity.

######  Proposition 4.5.

We have the following:

  1. (i)

the sequence $(\nu_{b}(n))_{n\geq 0}$ is $b$-regular;

  2. (ii)

the sequence $(\mathcal{L}_{b}(n))_{n\geq 0}$ is $b$-regular;

  3. (iii)

the sequence $(\ell_{b,d}(n))_{n\geq 0}$ is $b$-automatic.

###### Proof.

For all $n\in{\mathbb{N}}$ and $a=1,\ldots,b-1$ we have the relations
$\nu_{b}(bn)=\nu_{b}(n)+1$ and $\nu_{b}(bn+a)=0$. It follows that the
${\mathbb{Z}}$-module generated by $\mathcal{K}_{b}((\nu_{b}(n))_{n\geq 0})$
is generated by the sequence $(\nu_{b}(n))_{n\geq 0}$ and the constant
sequence $(1)_{n\geq 0}$. This implies (i).

Similarly, for all $n\geq 0$ and $a=1,\ldots,b-1$ we have
$\mathcal{L}_{b}(bn)=\mathcal{L}_{b}(n)$ and $\mathcal{L}_{b}(bn+a)=bn+a$. We
can thus write

$\mathcal{K}_{b}((\mathcal{L}_{b}(n))_{n\geq
0})=\\{(\mathcal{L}_{b}(n))_{n\geq
0}\\}\cup\bigcup_{a=1}^{b-1}\mathcal{K}_{b}((bn+a)_{n\geq 0}).$

For each $a=1,\ldots,b-1$ the sequence $(bn+a)_{n\geq 0}$ is $b$-regular due
to Corollary 3.5, and thus the ${\mathbb{Z}}$-module generated by
$\mathcal{K}_{b}((bn+a)_{n\geq 0})$ is generated by some finite set
$S_{a}\subset{\mathbb{Z}}^{{\mathbb{N}}}$. Consequently, the
${\mathbb{Z}}$-module generated by
$\mathcal{K}_{b}((\mathcal{L}_{b}(n))_{n\geq 0})$ is generated by

$\\{(\mathcal{L}_{b}(n))_{n\geq 0}\\}\cup\bigcup_{a=1}^{b-1}S_{a},$

again a finite set.

Part (iii) follows immediately from (ii) due to Corollary 3.4. ∎

##  5\. Further examples and applications

In this section we present some more involved examples and give various
applications of our main results and methods. To begin, we consider the family
of Lucas sequences of the first kind. Recall that $(u_{n})_{n\geq 0}$ is a
Lucas sequence of the first kind if $u_{0}=0,u_{1}=1$ and

$u_{n+2}=Au_{n+1}+Bu_{n}$

for some fixed integers $A,B$ and all $n\in{\mathbb{N}}$. It is called
nondegenerate if the ratio of the complex roots $\alpha,\beta$ of the
characteristic polynomial $P(X)=X^{2}-AX-B$ is not a root of unity. This
implies that $\alpha,\beta$ are distinct and the discriminant
$\Delta=A^{2}+4B=(\alpha-\beta)^{2}$ of $P$ is nonzero.

The following result of Sanna [33] will be of use.

######  Theorem 5.1 (Sanna).

Let $(u_{n})_{n\geq 0}$ be a nondegenerate Lucas sequence of the first kind.
If $p$ is a prime number such that $p\nmid B$, then

$\nu_{p}(u_{n})=\begin{cases}\nu_{p}(n)+\nu_{p}(u_{p})-1&\text{if
}p\mid\Delta,p\mid n,\\\ 0&\text{if }p\mid\Delta,p\nmid n,\\\
\nu_{p}(n)+\nu_{p}(u_{p\uptau(p)})-1&\text{if }p\nmid\Delta,\uptau(p)\mid
n,p\mid n,\\\ \nu_{p}(u_{p\uptau(p)})&\text{if }p\nmid\Delta,\uptau(p)\mid
n,p\nmid n,\\\ 0&\text{if }p\nmid\Delta,\uptau(p)\nmid n,\end{cases}$

for each positive integer $n$, where $\uptau(p)=\min\\{n>0:\ p\mid u_{n}\\}$.

For $(u_{n})_{n\geq 0}$ nondegenerate we have the Binet-like formula

(5.1) $u_{n}=\frac{\alpha^{n}-\beta^{n}}{\alpha-\beta}.$

This formula can also be considered in the $p$-adic setting, when treating
$\alpha,\beta$ as elements of the extension
${\mathbb{Q}}_{p}(\sqrt{\Delta})\subset{\mathbb{C}}_{p}$.

We also recall some basic properties of the $p$-adic exponential $\exp_{p}$
and $p$-adic logarithm $\log_{p}$ (not to be confused with base-$p$
logarithm). They are defined for $x\in{\mathbb{C}}_{p}$ by the usual formulas

$\displaystyle\exp_{p}(x)$
$\displaystyle=\sum_{k=0}^{\infty}\frac{x^{k}}{k!},$
$\displaystyle\log_{p}(1+x)$
$\displaystyle=\sum_{k=1}^{\infty}(-1)^{k-1}\frac{x^{k}}{k}.$

Contrary to the classical case $\exp_{p}(x)$ is convergent for
$|x|_{p}<r_{p}$, where $r_{p}=p^{-1/(p-1)}$. The $p$-adic logarithm
$\log_{p}(1+x)$ is convergent for $|x|_{p}<1$. Moreover, for $|x|_{p}<r_{p}$
and $|y|_{p}<r_{p}$ we have the standard identities

$\displaystyle\exp_{p}(x+y)$ $\displaystyle=\exp_{p}(x)\exp_{p}(y),$
$\displaystyle\log_{p}((1+x)(1+y))$
$\displaystyle=\log_{p}(1+x)+\log_{p}(1+y),$
$\displaystyle\exp_{p}(\log_{p}(1+x))$ $\displaystyle=1+x,$
$\displaystyle\log_{p}(\exp_{p}(x))$ $\displaystyle=x.$

When $|\gamma-1|<r_{p}$, we can thus define for $x\in{\mathbb{Z}}_{p}$ the
function

$\gamma^{x}=\exp_{p}(x\log_{p}(\gamma)),$

which ich analytic on ${\mathbb{Z}}_{p}$ and coincides with usual
exponentiation for $x\in{\mathbb{Z}}$. This cannot be immediately applied to
the formula (5.1) as the condition $|\alpha-1|_{p}=|\beta-1|_{p}<r_{p}$ might
not be satisfied. However, when $p\nmid B$, there exists a positive integer
$\pi_{p}$ such that $|\alpha^{\pi_{p}}-1|_{p}=|\beta^{\pi_{p}}-1|_{p}<r_{p}$ ,
and thus for each $j=0,1,\ldots,\pi_{p}-1$ and $m\in{\mathbb{N}}$ we can
interpolate $u_{\pi_{p}m+j}=f_{j}(m)$, where

$f_{j}(x)=\frac{1}{\alpha-\beta}\left(\alpha^{j}\exp_{p}(x\log_{p}(\alpha^{\pi_{p}})-\beta^{j}\exp_{p}(x\log_{p}(\beta^{\pi_{p}})\right).$

When $b\geq 2$ is a base coprime with $B$, we can perform this procedure
simultaneously for each prime factor of $b$. More precisely, let
$p_{1},\ldots,p_{s}$ be the prime factors of $b$ and let $\pi$ denote the
least common multiple of all $\pi_{p_{i}}$. Then we obtain $\pi$ tuples
$f_{j}=(f_{j,1},\ldots,f_{j,s})\in\mathcal{A}_{b}$ for $j=0,1,\ldots,\pi-1$
such that

$u_{\pi m+j}=f_{j,1}(m)=\cdots=f_{j,s}(m).$

Using this construction and our results, we can strengthen the theorem of
Murru and Sanna (Theorem 1.1) concerning $b$-regularity $\nu_{b}(u_{n})$, by
adding the word “strictly”. Moreover, we immediately obtain a similar
statement about last nonzero digits of $u_{n}$.

######  Corollary 5.2.

Let $(u_{n})_{n\geq 0}$ be a nondegenerate Lucas sequence of the first kind.
If $b$ and $B$ are relatively prime, then:

  1. (i)

the sequence $(\nu_{b}(u_{n}))_{n\geq 0}$ is strictly $b$-regular;

  2. (ii)

for every $d\geq 1$ the sequence $(\ell_{b,d}(u_{n}))_{n\geq 0}$ is strictly
$b$-automatic.

###### Proof.

By Theorem 1.1 and Proposition 3.2, for each $j=0,1,\ldots,\pi-1$ the
subsequence $(\nu_{b}(u_{\pi n+j}))_{n\geq 0}$ is $b$-regular. More precisely,
Theorem 5.1 implies that $\mathcal{R}_{f_{0}}=\\{0\\}$ and
$\mathcal{R}_{f_{j}}=\varnothing$ for $j\neq 0$. Hence, by Theorem 2.3 or 2.4
(depending on the number of prime factors of $b$) the sequence
$(\nu_{b}(u_{\pi n}))_{n\geq 0}$ is strictly $b$-regular. This implies (i),
again by Proposition 3.2.

If $b$ has $s\geq 2$ prime factors, part (ii) follows by Theorem 2.8. If
$b=p^{l}$ we use the fact that $m_{f_{0}}(0)=1$ to conclude that
$\mathcal{R}^{\prime}_{f_{0}}(l,d)=\\{0\\}$, and then apply Theorem 2.7. ∎

Another application of our methods is concerned with the representation

$u_{n}=x^{2}+y^{2}+z^{2},$

where $x,y,z\in{\mathbb{Z}}$. In Section 1 we have already mentioned the
following result of Robbins [31] and Latushkin, Ushakov [23] on the
representation of $F_{n}$ as a sum of three squares.

######  Theorem 5.3 (Robbins; Latushkin, Ushakov).

The $n$th Fibonacci number $F_{n}$ is a sum of three squares of integers if
and only if

$n\not\in\\{12l+10:l\in{\mathbb{N}}\\}\cup\\{4^{k+1}(24l+21):k,l\in{\mathbb{N}}\\}.$

We show that a similar statement holds in general for certain nondegenerate
Lucas sequences of the first kind.

######  Theorem 5.4.

Let $(u_{n})_{n\geq 0}$ be a nondegenerate Lucas sequence of the first kind
such that $u_{n}\geq 0$ for all $n\in{\mathbb{N}}$ and $2\nmid B$. Let $\pi$
be given by

$\pi=\begin{cases}4&\text{if }2\mid A,\\\ 6&\text{if }2\nmid A.\end{cases}$

Then the set of $n\in{\mathbb{N}}$ such that $u_{n}$ is not a sum of three
squares is a finite union of sets of the form

(5.2) $\\{2^{t}\pi l+j:l\in{\mathbb{N}}\\},$

and

(5.3) $\\{2^{t+2k}\pi(8l+c):k,l\in{\mathbb{N}}\\},$

where $t\in{\mathbb{N}}$, $j\in\\{1,\ldots,2^{t}\pi-1\\}$, and
$c\in\\{0,1,\ldots,7\\}$.

###### Proof.

To begin, we show that the subsequences $(u_{\pi m+j})_{m\geq 0}$, with
$i=0,1,\ldots,\pi-1$, can be interpolated by a $2$-adic analytic functions. By
the earlier discussion it is sufficient to prove that the $2$-adic valuation
of $\alpha^{\pi}-1$ and $\beta^{\pi}-1$ is greater than $1$. Let

$C=\begin{bmatrix}0&1\\\ B&A\end{bmatrix}$

be the companion matrix of the recurrence defining $(u_{n})_{n\geq 0}$ and
observe that $P$ is its characteristic polynomial. Direct computation shows
that $C^{\pi}\equiv I\pmod{4}$, where $I$ denotes the $2\times 2$ identity
matrix. Since $\alpha^{\pi}-1,\beta^{\pi}-1$ are the eigenvalues of
$C^{\pi}-I$, it follows that
$\nu_{2}(\alpha^{\pi}-1)=\nu_{2}(\beta^{\pi}-1)\geq 2$. Therefore, $u_{\pi
m+j}=f_{j}(m)$, where for $x\in{\mathbb{Z}}_{2}$ we define

$f_{j}(x)=\frac{1}{\alpha-\beta}\left(\alpha^{j}\exp_{2}(x\log_{2}(\alpha^{\pi})-\beta^{j}\exp_{2}(x\log_{2}(\beta^{\pi})\right).$

From Theorem 5.1 we deduce that $0$ is the only $2$-adic integer root of
$f_{0}$ and has multiplicity $1$. On the other hand, the functions
$f_{1},\ldots,f_{\pi-1}$ have no roots in ${\mathbb{Z}}_{2}$.

Now, by Legendre’s three-square theorem, a nonnegative integer $r$ is not a
sum of three squares if and only if $\ell_{2,3}(r)=7$ and $\nu_{2}(r)$ is
even, or equivalently, $\ell_{4,2}(r)\in\\{7,15\\}$. By part (a) of Theorem
2.7, for each $j=1,\ldots,\pi-1$ the sequence $(\ell_{4,2}(u_{\pi
m+j}))_{m\geq 0}$ is periodic with period $2^{t}$ for some $t\in{\mathbb{N}}$.
It follows that for each $j=1,\ldots,\pi-1$ the set of $n\equiv j\pmod{\pi}$
such that $u_{n}$ is not a sum of three squares, is a finite union of sets of
the form (5.2).

In the case $i=0$ we can write

$f_{0}(x)=xg(x),$

where $g$ has no root in ${\mathbb{Z}}_{2}$. The integer $f_{0}(m)$ is not a
sum of three squares if and only if

(5.4) $\displaystyle\ell_{2,3}(m)\ell_{2,3}(g(m))$ $\displaystyle\equiv
7\pmod{8},$ (5.5) $\displaystyle\nu_{2}(m)+\nu_{2}(g(m))$ $\displaystyle\equiv
0\pmod{2}.$

Let $2^{T}$ be the minimal common period of the sequences
$(\ell_{2,3}(g(m)))_{m\geq 0}$ and $(\nu_{2}(g(m)))_{m\geq 0}$. We consider
the solutions of the congruences depending on $m\bmod{2^{T}}$. If $m\equiv
0\pmod{2^{T}}$, they are of the form $m=2^{t+2k}(8l+c)$ with
$k,l\in{\mathbb{N}}$, where $t=T+(\nu_{2}(g(0))\bmod{2})$ and $c\equiv
7\ell_{2,3}^{-1}(g(0))\pmod{8}$. Putting $n=\pi m$, we obtain precisely the
set (5.3).

If $m\equiv v\pmod{2^{T}}$ for some $v\in\\{1,\ldots,2^{T}-1\\}$ write
$m=2^{T+2}l+2^{T}w+v$, where $l\in{\mathbb{N}}$ and $w\in\\{0,1,2,3\\}$. In
this case we obtain the equalities $\ell_{2,3}(m)=\ell_{2,3}(2^{T}w+v)$ and
$\nu_{2}(m)=\nu_{2}(v)$, which do not depend on $l$. Plugging them into (5.4)
and (5.5) and replacing $g(m)$ with $g(v)$, we see that for each fixed $w$
there are either no solutions $m\equiv v\pmod{2^{T}}$ or they are of the form
given above. In the latter case, for $n=\pi m$, we obtain a set of the form
(5.2) with $t=T+2$ and $j=\pi(2^{T}w+v)$. ∎

Along the same lines, one can prove results for other ternary quadratic forms
$q$ such that the set of integers not represented by $q$ can be expressed in
terms of last nonzero digits. We refer the interested reader to [5], where
appropriate conditions are given for several quadratic forms.

Knowing a concrete formula for the $2$-adic valuation of $u_{n}$, one can
explicitly determine the set considered in Theorem 5.4.

######  Example 5.1.

Consider the sequence of Pell numbers $(P_{n})_{n\geq 0}$, defined by
$P_{0}=0,P_{1}=1$, and $P_{n}=2P_{n-1}+P_{n-2}$ for $n\geq 2$. We will
determine which Pell numbers can be written as a sum of three squares by
loosely following the proof of Theorem 5.4. We can write

$P_{n}=\frac{\alpha^{n}-\beta^{n}}{\alpha-\beta},$

where $\alpha=1+\sqrt{2}$ and $\beta=1-\sqrt{2}$ (treated as elements of
${\mathbb{Q}}_{2}(\sqrt{2})$). Inspecting for $i=1,2,3$ the subsequences
$(P_{4m+i})_{m\geq 0}$ modulo $8$, we deduce that all of their terms are sums
of three squares.

Moving on to the subsequence $(P_{4m})_{m\geq 0}$, we have $P_{4m}=f(m)$,
where

$f(x)=\frac{1}{\alpha-\beta}\left(\exp_{2}(x\log_{2}(\alpha^{4})-\exp_{2}(x\log_{2}(\beta^{4})\right)=\sum_{k=1}^{\infty}c_{k}x^{k},$

where

$c_{k}=\frac{1}{(\alpha-\beta)k!}\left(\log_{2}^{k}(\alpha^{4})-\log_{2}^{k}(\beta^{4})\right).$

From Theorem 5.1 we get the simple formula $\nu_{2}(P_{n})=\nu_{2}(n)$, and so
$f(x)=xg(x)$, where $g$ has no root in ${\mathbb{Z}}_{2}$. We immediately
obtain that $\nu_{2}(g(m))=\nu_{2}(P_{4m})-\nu_{2}(m)=2$ is constant for all
$m\in{\mathbb{N}}$. As seen in the proof of Theorem 5.4, we also need to
determine a period of $(\ell_{2,3}(g(m)))_{m\geq 0}$.

To this end, we first show that the coefficients $c_{k}$ have positive
$2$-adic valuation. Since $\alpha-\beta=2\sqrt{2}$, we obtain
$\nu_{2}(\alpha-\beta)=3/2$. By Legendre’s formula for the $p$-adic valuation
of a factorial (see for example [32, pp. 241–242]), we obtain
$\nu_{2}(k!)=k-s_{2}(k)$, where $s_{2}$ is the sum of binary digits. Finally,
direct calculation gives $\nu_{2}(\alpha^{4}-1)=\nu_{2}(\beta^{4}-1)=5/2$, and
thus by [32, Proposition 1 on p. 252] we have
$\nu_{2}(\log_{2}(\alpha^{4}))=\nu_{2}(\log_{2}(\beta^{4}))=5/2$. Combining
all of the above, we obtain

$\nu_{2}(c_{k})\geq-\frac{3}{2}-k+s_{2}(k)+\frac{5}{2}k\geq\frac{3}{2}(k-1)+s_{2}(k)\geq
1.$

We claim that $16$ is a period $(\ell_{2,3}(g(m)))_{m\geq 0}$. For any fixed
$m\in{\mathbb{N}}$ we have the Taylor expansion:

(5.6) $g(m+16)=g(m)+\sum_{i=1}^{\infty}\frac{g^{(i)}(m)}{i!}16^{i},$

where $g^{(i)}$ denotes the $i$-th derivative of $g$. Since $g$ has
coefficients with $2$-adic valuation at least $1$, so do the functions
$g^{(i)}/i!$. Hence, the $2$-adic valuation of the sum on the right-hand side
of (5.6) is at least $5$. Dividing both sides by $4$ and reducing modulo $8$,
we obtain

$\ell_{2,3}(g(m+16))=\ell_{2,3}(g(m)),$

as claimed. Knowing this, we can directly compute that $\ell_{2,3}(g(m))$ is
in fact constantly equal to $3$.

Therefore, the term $P_{4m}$ is not a sum of three squares if and only if
$\nu_{2}(m)\equiv 0\pmod{2}$ and $\ell_{2,3}(m)\equiv 7\cdot 3^{-1}\equiv
5\pmod{8}$. Such $m$ can be written in the form $m=2^{2k}(8l+5)$ with
$k,l\in{\mathbb{N}}$. Returning to $n=4m$, we conclude that $P_{n}$ is a sum
of three squares if and only if $n$ belong to the set

${\mathbb{N}}\setminus\\{4^{k+1}(8l+5):k,l\in{\mathbb{N}}\\}.$

In the following two examples we showcase the computation of last nonzero
digits for a base with several prime factors.

######  Example 5.2.

Consider the Fibonacci sequence $(F_{n})_{n\geq 0}$. Theorem 2.8 implies that
the sequence $(\ell_{10}(F_{n}))_{n\geq 0}$ is strictly $10$-automatic. We are
going to derive an explicit formula for the last decimal digit of $F_{n}$ in
an elementary way.

It is convenient to compute $\ell_{10}$ evaluated at the subsequences
$(F_{30m+j})_{m\geq 0}$ for $j=0,1,\ldots,29$. For any $j\neq 0$ it can be
checked, by examining the sequence modulo $100$, that
$(\ell_{10}(F_{30m+j}))_{m\geq 0}$ is periodic and $10$ is a common period of
all these subsequences.

In the case $j=0$ we will use the congruence (4.4), which for $b=10$ and
nonzero rational $x$ becomes

(5.7) $\ell_{10}(x)\equiv 2^{\nu_{2}(x)-\nu_{10}(x)}\cdot
5+5^{\nu_{5}(x)-\nu_{10}(x)}\cdot 6\cdot 3^{\nu_{10}(x)}\ell_{5}(x)\pmod{10}.$

By the results of Lengyel [24], we have $\nu_{5}(F_{n})=\nu_{5}(n)$ and

$\nu_{2}(F_{n})=\begin{cases}0&\text{if }n\equiv 1,2\pmod{3},\\\ 1&\text{if
}n\equiv 3\pmod{6},\\\ \nu_{2}(n)+2&\text{if }n\equiv 0\pmod{6}.\end{cases}$

It follows from the Binet formula that

$2^{n-1}F_{n}=\sum_{k=0}^{\lfloor(n-1)/2\rfloor}\binom{n}{2k+1}5^{k},$

for all $n\geq 1$. As in [24, Lemma 1], for $k\neq 0$ we deduce that

$\nu_{5}\left(\binom{n}{2k+1}5^{k}\right)>\nu_{5}(n),$

which in turn implies

(5.8) $\ell_{5}(F_{n})\equiv 3^{n-1}\ell_{5}(n)\pmod{5}.$

We apply the formula (5.7) to $x=F_{30m}/40m$ rather than $x=F_{30m}$. This
approach is more convenient, as $\nu_{2}(F_{30m}/40m)=\nu_{5}(F_{30m}/40m)=0$
so all the exponents in (5.7) vanish. Using (5.7) and (5.8), we obtain

$\ell_{10}\left(\frac{F_{30m}}{40m}\right)\equiv
5+6\ell_{5}\left(\frac{30m\cdot 3^{30m-1}}{40m}\right)\\\
\equiv(-1)^{m-1}\pmod{10}.$

We can now recover the value of $\ell_{10}(F_{30m})$ from the congruence

$\ell_{10}(F_{30m})=\ell_{10}\left(\frac{F_{30m}}{40m}\cdot
40m\right)\equiv\ell_{10}\left(\frac{F_{30m}}{40m}\right)\ell_{10}(4m)\equiv(-1)^{m-1}\ell_{10}(4m)\pmod{10}.$

In order to obtain an expression in terms of $n=30m$, we first compute

$\ell_{10}(4m)\equiv\ell_{10}\left(\frac{1}{3}\right)\ell_{10}(120m)\equiv
7\ell_{10}(4n)\pmod{10}.$

Taking all into account, we obtain

$\ell_{10}(F_{n})=\begin{cases}\ell_{10}(F_{j})&\text{if }n\equiv
j\pmod{300}\\\ &\text{for some }j\not\equiv 0\pmod{30},\\\
3\ell_{10}(4n)\bmod{10}&\text{if }n\equiv 0\pmod{60},\\\
7\ell_{10}(4n)\bmod{10}&\text{if }n\equiv 30\pmod{60}.\end{cases}$

In the following example we provide a sequence of integers $(a_{n})_{n\geq 0}$
such that $(\ell_{b}(a_{n}))_{n\geq 0}$ is strictly $k$-automatic but $b,k$
are multiplicatively independent.

######  Example 5.3.

Consider the last nonzero digit of $a_{n}=(2n-1)(16^{n}-4)$ in the base
$b=15$. The sequence $(a_{n})_{n\geq 0}$ can be intepolated by the functions
$f_{3}\in\mathcal{A}_{3}$ and $f_{5}\in\mathcal{A}_{5}$, defined by

$f_{p}(x)=(2x-1)(\exp_{p}(x\log_{p}16)-4)$

for $p=3,5$. By the well-known Lifting the Exponent Lemma, for all
$n\in{\mathbb{N}}$ we obtain

$\nu_{3}(16^{n}-4)=\nu_{3}(4^{2n-1}-1)=\nu_{3}(2n-1)+1.$

At the same time $\nu_{5}(16^{n}-4)=0$. This means $1/2$ is the only $p$-adic
integer root of both $f_{3}$ and $f_{5}$ with $m_{f_{3}}(1/2)=2$ and
$m_{f_{5}}(1/2)=1$. Theorem 2.8 implies that the sequence
$(\ell_{15}(a_{n}))_{n\geq 0}$ is strictly $75$-automatic.

In order to compute its terms in a more explicit way, write

$\displaystyle f_{3}(x)$ $\displaystyle=(2x-1)^{2}g_{3}(x),$ $\displaystyle
f_{5}(x)$ $\displaystyle=(2x-1)g_{5}(x),$

where $g_{p}\in\mathcal{A}_{p}$ for $p=3,5$. By the above, we have
$\nu_{3}(g_{3}(x))=1$ and $\nu_{5}(g_{5}(x))=0$ so

$\ell_{15}(a_{n})=\ell_{15}(f_{3}(n),f_{5}(n))\equiv\ell_{15}\left((3(2n-1)^{2},(2n-1)\right)\cdot\left(\frac{g_{3}(n)}{3},g_{5}(n)\right)\pmod{15}.$

We have $g_{5}(n)=16^{n}-4\equiv 2\pmod{5}$ and it remains to compute
$(g_{3}(n)/3)\bmod{3}$. Write

$g_{3}(x)=\frac{\exp_{p}(x\log_{p}16)-4}{2x-1}=\sum_{k=0}^{\infty}c_{k}x^{k}.$

Multiplying by $2x-1$ and comparing the coefficients, we obtain $c_{0}=3$ and

$c_{k}=2c_{k-1}-\frac{\log_{3}^{k}16}{k!}$

for $k\geq 1$. We are going to prove that $\nu_{3}(c_{k})\geq 2$ for all
$k\geq 1$. Expanding the logarithm, we see that $\nu_{3}(c_{1})\geq 2$. For
$k\geq 2$ Legendre’s formula gives

$\nu_{3}\left(\frac{\log_{3}^{k}16}{k!}\right)=k-\frac{k-s_{3}(k)}{2}\geq 2,$

and thus our claim holds by induction on $k$. Consequently,
$g_{3}(x)=3+9xh_{3}(x),$ where $\nu_{3}(h_{3}(x))\geq 0$ for all
$x\in{\mathbb{Z}}_{3}$. This implies that for all $n\in{\mathbb{N}}$ we have

$\left(\frac{g_{3}(n)}{3},g_{5}(n)\right)\equiv(1,2)\equiv 7\pmod{15}.$

Finally, we obtain

$\ell_{15}(a_{n})\equiv 7\ell_{15}\left(3(2n-1)^{2},2(2n-1)\right)\pmod{15}.$

##  6\. Proofs for $b=p^{l}$

The goal of this section is to prove Theorems 2.3, 2.5, and 2.7. Propositions
2.1 and 2.2 are proved in the next section for a general base $b$. Here, let
$b=p^{l}$, where $p$ is a prime and $l\geq 1$ an integer. We retain the
notation used in Section 2. In particular, we let $\mathcal{A}_{p}$ denote the
set of nonzero analytic functions $f\colon{\mathbb{Z}}_{p}\to{\mathbb{Q}}_{p}$
and $\mathcal{P}_{p}$ its subset consisting of polynomials. The set of
$p$-adic integer roots of $f\in\mathcal{A}_{p}$ is denoted by
$\mathcal{R}_{f}$, while the multiplicity of $\theta$ is $m_{f}(\theta)$. For
the sake of convenience, for a $p$-adic integer $\theta\in{\mathbb{Z}}_{p}$
and $t\in{\mathbb{N}}$ we introduce the notation

$\displaystyle\theta[t]$ $\displaystyle=\theta\bmod{p^{t}},$
$\displaystyle\theta\\{t\\}$ $\displaystyle=p^{-t}(\theta-\theta[t]).$

In terms of the $p$-adic expansion of $\theta$, the number $\theta[t]$ is
represented by its $t$ initial digits, while $\theta\\{t\\}$ by the remaining
digits.

We now outline the general structure of our reasoning. We first condsider the
simpler case when the function $f\in\mathcal{A}_{p}$ has at most one distinct
root in ${\mathbb{Z}}_{p}$. If there is no such root, then the corresponding
assertion (covered in case (a) of our theorems) is rather easily shown using
uniform continuity of $f$. On the other hand, if $f$ has precisely one root
$\theta\in{\mathbb{Z}}_{p}$, it can be written in the form

$f(x)=(x-\theta)^{m_{f}(\theta)}g(x),$

where $g\in\mathcal{A}_{p}$ has no roots in ${\mathbb{Z}}_{p}$. This further
boils down to studying terms of the form $c(x-\theta)^{m}$, where
$c\in{\mathbb{Q}}_{p}$, $m\geq 1$, which is our main focus throughout this
section.

For general $f$ the idea is to find an integer $T\geq 0$ large enough so that
each of the functions $f(p^{T}x+a)$ for $a=0,1,\ldots,p^{T}-1$ has at most one
root in ${\mathbb{Z}}_{p}$. Combined with the basic properties of regular
sequences (Proposition 3.2), this reduces our investigation to the previous
case.

The whole reasoning is split into a number of auxiliary results, whose proofs
are rather elementary, though quite technical in some places. At the very end
of this section we combine them to prove the main theorems. We begin with the
simplest case, namely when $f$ has no root in ${\mathbb{Z}}_{p}$.

######  Proposition 6.1.

Assume that $f\in\mathcal{A}_{p}$ has no root in ${\mathbb{Z}}_{p}$. Then we
have the following:

  1. (i)

the sequence $(\nu_{p^{l}}(f(n)))_{n\geq 0}$ is periodic;

  2. (ii)

when $f\in\mathcal{P}_{p}$, the sequence $(\mathcal{L}_{p^{l}}(f(n))_{n\geq
0}$ is $k$-regular for every $k\geq 2$;

  3. (iii)

the sequence $(\ell_{p^{l},d}(f(n)))_{n\geq 0}$ is periodic.

Moreover, the period in (i) and (iii) can be chosen to be a power of $p$.

###### Proof.

We first prove (i) and (iii) simultaneously. Since $f$ has no root in
${\mathbb{Z}}_{p}$, for some $V\in{\mathbb{N}}$ we have the inequality
$\nu_{p^{l}}(f(x))<V$ for all $x\in{\mathbb{Z}}_{p}$. By uniform continuity of
$f$ there exists $T\in{\mathbb{N}}$ such that for all $x,y\in{\mathbb{Z}}_{p}$
there holds

$\nu_{p^{l}}(f(x+p^{T}y)-f(x))\geq V+d.$

Equivalently, we can write

$f(x+p^{T}y)=f(x)+p^{l(V+d)}\sigma$

for some $\sigma\in{\mathbb{Z}}_{p}$ depending on $x,y$. Putting
$x=n\in{\mathbb{N}}$ and $y=1$, we obtain both
$\nu_{p^{l}}(f(n+p^{T}))=\nu_{p^{l}}(f(n))$ and
$\ell_{p^{l},d}(f(n+p^{T}))=\ell_{p^{l},d}(f(n))$, as desired.

To see why (ii) holds we write

$\mathcal{L}_{p^{l}}(f(n))=p^{-\nu_{p^{l}}(f(n))}f(n).$

The first factor on the right-hand side is periodic with respect to $n$, thus
$k$-regular for all $k\geq 2$. The same can be said about the second factor
due to Corollary 3.5. Since the term-wise product of $k$-regular sequences is
$k$-regular, we obtain (ii). ∎

We move on to the expressions of the form $c(x-\theta)^{m}$, where
$c\in{\mathbb{Q}}_{p}$, $\theta\in{\mathbb{Z}}_{p}$, and $m$ is a positive
integer. To begin, we prove $p$-regularity of the considered sequences when
$\theta$ is rational.

######  Proposition 6.2.

Assume that $\theta\in\mathbb{Q}\cap{\mathbb{Z}}_{p}$. Then we have the
following:

  1. (i)

the sequence $(\nu_{p^{l}}(c(n-\theta)^{m}))_{n\geq 0}$ is $p$-regular;

  2. (ii)

the sequence $(\mathcal{L}_{p^{l}}(c(n-\theta)^{m}))_{n\geq 0}$ is
$p$-regular;

  3. (iii)

for all $d\geq 1$ the sequence $(\ell_{p^{l},d}(c(n-\theta)^{m}))_{n\geq 0}$
is $p$-automatic.

###### Proof.

Letting $\theta=q/r$ be written in lowest terms with $r$ positive, we can
write

$c(n-\theta)^{m}=\frac{c}{r^{m}}(rn-q)^{m}.$

Due to Proposition 3.2, without loss of generality we can assume $\theta=0$.

Staring with $\nu_{p^{l}}$, consider the subsequences
$(\nu_{p^{l}}(c(p^{l}n+a)^{m}))_{n\geq 0}$, where $a=0,1,\ldots,p^{l}-1$. For
$a=0$ we have

$\nu_{p^{l}}(c(p^{l}n)^{m})=m+\nu_{p^{l}}(cn^{m}).$

Now take $0<a<p^{l}$ and write $a=p^{k}e$, where $k,e\in{\mathbb{N}}$ and
$\nu_{p}(e)=0$. Since $k<l$, for all $n\in{\mathbb{N}}$ we obtain

$\nu_{p^{l}}(c(p^{l}n+a)^{m})=\nu_{p^{l}}(cp^{km}(p^{l-k}n+e)^{m})=\left\lfloor\frac{\nu_{p}(c)+km}{l}\right\rfloor,$

a constant. Therefore, the ${\mathbb{Z}}$-module generated by the $k$-kernel
of $(\nu_{p^{l}}(cn^{m}))_{n\geq 0}$ is generated by
$(\nu_{p^{l}}(cn^{m})_{n\geq 0})$ itself and the constant sequence $(1)_{n\geq
0}$.

Moving on to (ii), by Proposition 4.3(ii) and the multiplicative property of
$\mathcal{L}_{p}$, for all $n\geq 1$ we have

(6.1)
$\mathcal{L}_{p^{l}}(cn^{m})=p^{(\nu_{p}(c)+m\nu_{p}(n))\bmod{l}}(\mathcal{L}_{p}(n))^{m}.$

The sequence $((\nu_{p}(c)+m\nu_{p}(n))\bmod{l})_{n\geq 0}$ is $p$-automatic
as a reduction modulo $l$ of a $p$-regular sequence. We deduce that the first
factor on the right-hand side of (6.1) is $p$-regular. By Proposition 4.5(ii)
so is $(\mathcal{L}_{p}(n))_{n\geq 0}$, which implies that
$(\mathcal{L}_{p^{l}}(cn^{m}))_{n\geq 0}$ is also $p$-regular as a termwise
product of $p$-regular sequences.

Part (iii) follows immediately from (ii) by Corollary 3.4. ∎

We ultimately need to prove that the properties in Proposition 6.2 hold in the
strict sense (under extra assumptions in the case of $\ell_{p^{l},d}$). The
following technical lemma is a step in this direction and will also be useful
later in proving nonautomaticity.

######  Lemma 6.3.

Let $\theta,\sigma\in{\mathbb{Z}}_{p}$ be such that $\theta\neq\sigma$. Then
we have the following:

  1. (i)

for any $t\in{\mathbb{Z}}\setminus\\{0\\}$ there exist infinitely many
$n\in{\mathbb{N}}$ such that $\nu_{p}(n-\theta)=\nu_{p}(n-\sigma)+t$;

  2. (ii)

for any integer $\delta\geq 1$ and $x\in\\{1,\ldots,p^{\delta}-1\\}$ such that
$p\nmid x$ and $x\neq\ell_{p,\delta}(\theta-\sigma)$ there exist infinitely
many $n\in{\mathbb{N}}$ such that $\ell_{p,\delta}(n-\theta)=x$ and
$\ell_{p,\delta}(n-\sigma)=\ell_{p,\delta}(\theta-\sigma)$.

###### Proof.

Put $v=\nu_{p}(\theta-\sigma)$. In (i), by renaming $\theta$ and $\sigma$ we
can assume without loss of generality that $t>0$. It is enough to take any $n$
such that $\nu_{p}(n-\theta)=v+t$, for example

$n=p^{v+t+1}j+p^{v+t}+\theta[v+t+1],$

where $j\geq 1$ is arbitrary. Then $\nu_{p}(n-\theta)>\nu_{p}(\theta-\sigma)$
so

$\nu_{p}(n-\sigma)=\nu_{p}((n-\theta)+(\theta-\sigma))=v,$

and (i) follows.

Moving on to (ii), if $p=2$ and $\delta=1$ there is nothing to prove.
Otherwise, let

$n=p^{v+\delta}(x+p^{\delta}j)+\theta[v+2\delta],$

where $j\geq 1$ is again arbitrary. We obtain that

$\frac{n-\theta}{p^{v+\delta}}=x+p^{\delta}(j-\theta\\{v+2\delta\\}),$

which yields $\nu_{p}(n-\theta)=v+\delta$ and $\ell_{p,\delta}(n-\theta)=x$.
Again, we can write $n-\sigma=(n-\theta)+(\theta-\sigma)$ and observe that
$\nu_{p}(n-\theta)=\nu_{p}(\theta-\sigma)+\delta$, which gives
$\ell_{p,\delta}(n-\sigma)=\ell_{p,\delta}(\theta-\sigma)$. ∎

In order to prove that the sequence $(\nu_{p^{l}}(c(n-\theta)^{m}))_{n\geq 0}$
is strictly $p$-regular, it suffices to show that its reduction modulo some
positive integer is not eventually periodic. At the same time, if
$(\ell_{p^{l},d}(c(n-\theta)^{m}))_{n\geq 0}$ is eventually periodic, then so
is $(\nu_{p}((n-\theta)^{m})\bmod{l})_{n\geq 0}$, and we would like to know
when the latter possibility can be ruled out. In both situations we will use
the following auxiliary result.

######  Lemma 6.4.

Let $t,u$ be positive integers such that $u\nmid m$. Then
$(\nu_{p^{t}}(c(n-\theta)^{m})\bmod{u})_{n\geq 0}$ is not eventually periodic.

###### Proof.

Suppose for the sake of contradiction that
$(\nu_{p^{t}}((n-\theta)^{m})\bmod{u})_{n\geq 0}$ is eventually periodic with
period $T>0$. We have

(6.2)
$\nu_{p^{t}}(c(n-\theta)^{m})=\left\lfloor\frac{\nu_{p}(c)+m\nu_{p}(n-\theta)}{t}\right\rfloor.$

Lemma 6.3(i) applied to $\sigma=\theta-T$ provides infinitely many
$n\in{\mathbb{N}}$ such that $\nu_{p}(n+T-\theta)=\nu_{p}(n-\theta)+t$. Using
the formula (6.2) twice, for such $n$ we obtain

$\nu_{p^{t}}(c(n+T-\theta)^{m})=\nu_{p^{t}}(c(n-\theta)^{m})+m$

so these two valuations are not congruent modulo $u$, thus a contradiction. ∎

We are now ready to prove a necessary and sufficient condition for eventual
periodicity of $(\ell_{p^{l},d}(c(n-\theta)^{m}))_{n\geq 0}$. For later
reference we highlight it below:

(C) $l\mid m\text{ and }\lambda(p^{ld-\nu_{p}(c)\bmod{l}})\mid m.$

Note that $\mathcal{R}^{\prime}_{f}$, as defined in Section 2, contains
precisely these $\theta$ for which the condition (C) with
$c=g_{\theta}(\theta),m=m_{f}(\theta)$ does not hold.

######  Proposition 6.5.

The condition (C) is equivalent to the following:

  1. (i)

the sequence $(\ell_{p^{l},d}(c(n-\theta)^{m}))_{n\geq 0}$ is eventually
periodic;

  2. (ii)

$\ell_{p^{l},d}(c(n-\theta)^{m})=\ell_{p^{l},d}(c)$ for all
$n\in{\mathbb{N}}$.

###### Proof.

When multiplying $c$ by an integer power of $p^{l}$ the value
$\ell_{p^{l},d}(c(n-\theta)^{m})$ does not change, hence without loss of
generality we can assume that $\nu_{p}(c)\in\\{0,1,\ldots,l-1\\}$.

We first prove the implication (C)$\implies$(ii). Since $l\mid m$, by
Propositions 4.2(ii) and 4.3 we have

(6.3)
$\ell_{p^{l},d}(c(n-\theta)^{m})\equiv\ell_{p^{l},d}(c)\ell_{p^{l},d}((n-\theta)^{m})\equiv
c(\ell_{p,ld}(n-\theta))^{m}\pmod{p^{ld}}.$

At the same time, $\lambda(p^{ld-\nu_{p}(c)})\mid m$ implies

$(\ell_{p,ld}(n-\theta))^{m}\equiv 1\pmod{p^{ld-\nu_{p}(c)}}.$

Combining the two congruences we obtain (ii).

Since the implication (ii)$\implies$(i) is obvious, we are left with proving
(i)$\implies$(C). Suppose that the sequence
$(\ell_{p^{l},d}(c(n-\theta)^{m}))_{n\geq 0}$ is eventually periodic with
period $T$. As $\nu_{p}(\ell_{p^{l},d}(x))=\nu_{p}(x)\bmod{l}$ for any
$x\in{\mathbb{Z}}_{p}$ , the sequence
$(\nu_{p}((n-\theta)^{m})\bmod{l})_{n\geq 0}$ is eventually periodic as well
with the same period. Lemma 6.4 applied to $t=1,u=l$ implies that $l\mid m$,
and thus again we get (6.3).

For the sake of contradiction suppose further that
$\lambda(p^{ld-\nu_{p}(c)})\nmid m$. This means that there exists
$x\in\\{1,\ldots,p^{ld-\nu_{p}(c)}-1\\}$ not divisible by $p$ and such that
$x^{m}\not\equiv(\ell_{p,ld}(T))^{m}\pmod{p^{ld-\nu_{p}(c)}}$. Applying Lemma
6.3(ii) to $\sigma=\theta-T$ and $\delta=ld$ gives infinitely many values of
$n$ such that

$(\ell_{p,ld}(n+T-\theta))^{m}\equiv(\ell_{p,ld}(T))^{m}\not\equiv
x^{m}\equiv(\ell_{p,ld}(n-\theta))^{m}\pmod{p^{ld-\nu_{p}(c)}}.$

This non-congruence still holds when both sides are multiplied by $c$ and the
modulus is changed to $p^{ld}$. Using (6.3), we obtain
$\ell_{p^{l},d}(c(n+T-\theta)^{m})\neq\ell_{p^{l},d}(c(n-\theta)^{m})$ for
infinitely many $n$, which contradicts periodicity. ∎

We now turn to the case when $\theta$ is an irrational $p$-adic integer, with
the aim to prove nonregularity of the considered sequences. In this regard,
the following result is an analogue of Lemma 6.4.

######  Lemma 6.6.

Assume that $\theta\in{\mathbb{Z}}_{p}\setminus{\mathbb{Q}}$ and let $t,u$ be
positive integers such that $u\nmid m$. Then the sequence
$(\nu_{p^{t}}(c(n-\theta)^{m})\bmod{u})_{n\geq 0}$ is not automatic.

###### Proof.

Fix an integer $k\geq 2$ and write $k=p^{e}r$, where $e,r\in{\mathbb{N}}$ and
$\nu_{p}(r)=0$. By Proposition 3.1(i) without loss of generality we can
replace $k$ with $k^{ut}$, and thus assume that $e$ is divisible by $ut$. We
will prove directly that the $k$-kernel of the considered sequence is
infinite. More precisely, we claim that for $j\in{\mathbb{N}}$ the
subsequences $(\nu_{p^{t}}(c(k^{j}n+\theta[ej]-\theta))\bmod{u})_{n\geq 0}$
are all distinct. First, we compute

$\nu_{p}(k^{j}n+\theta[ej]-\theta)=ej+\nu_{p}(n-r^{-j}\theta\\{ej\\}),$

which implies that

$\displaystyle\nu_{p^{t}}(c(k^{j}n+\theta[ej]-\theta)^{m})$
$\displaystyle=\left\lfloor\frac{\nu_{p}(c)+m\nu_{p}(k^{j}n+\theta[ej]-\theta)}{t}\right\rfloor$
(6.4)
$\displaystyle\equiv\left\lfloor\frac{\nu_{p}(c)+m\nu_{p}(n-r^{-j}\theta\\{ej\\})}{t}\right\rfloor\pmod{u},$

where we used $ut\mid e$.

Now, fix any $i,j\in{\mathbb{N}}$ such that $i\neq j$. Since $\theta$ is
irrational, we have $r^{-i}\theta\\{ei\\}\neq r^{-j}\theta\\{ej\\}$, and thus
by Lemma 6.3(i) we obtain $n\in{\mathbb{N}}$ such that

$\nu_{p}(n-r^{-j}\theta\\{ej\\})=\nu_{p}(n-r^{-i}\theta\\{ei\\})+t.$

Plugging this in (6), we obtain

$\nu_{p^{t}}(c(k^{j}n+\theta[ej]-\theta)^{m})\equiv\nu_{p^{t}}(c(k^{i}n+\theta[ei]-\theta)^{m})+m\pmod{u}.$

As $m\nmid u$, we have found an index $n$ at which the two subsequences
corresponding to $i,j$ differ, and the result follows. ∎

It turns out that when $\theta\not\in{\mathbb{Q}}$, the sequence
$(\ell_{p^{l},d}(p^{v}(n-\theta)^{m}))_{n\geq 0}$ is not automatic at all that
unless the condition (C) is satisfied.

######  Proposition 6.7.

Assume that $\theta\in{\mathbb{Z}}_{p}\setminus{\mathbb{Q}}$. Then we have the
following:

  1. (i)

the sequence $(\nu_{p^{l}}(c(n-\theta)^{m}))_{n\geq 0}$ is not regular;

  2. (ii)

the sequence $(\mathcal{L}_{p^{l}}(c(n-\theta)^{m})))_{n\geq 0}$ is not
regular;

  3. (iii)

if (C) does not hold, the sequence $(\ell_{p^{l},d}(c(n-\theta)^{m})))_{n\geq
0}$ is not automatic.

###### Proof.

If the sequence $(\nu_{p^{l}}(c(n-\theta)^{m}))_{n\geq 0}$ were $k$-regular
for some $k$, then its reduction modulo any positive integer $u$ would be
$k$-automatic. Lemma 6.6 applied to $t=l$ shows that this is not the case.

Part (ii) follows immediately from (iii), again by the fact that the reduction
modulo $p^{ld}$ of a $k$-regular sequence of $p$-adic integers yields a
$k$-automatic sequence.

Therefore, we have left to prove (iii). Similarly as in Proposition 6.5,
without loss of generality $\nu_{p}(c)\in\\{0,1,\ldots,l-1\\}$. If $l\nmid m$,
then Lemma 6.6 applied to $t=1,u=l$ shows that
$(\nu_{p}(c(n-\theta)^{m})\bmod{l})_{n\geq 0}$ is not automatic, and the
assertion follows.

Otherwise, if $l\mid m$, we must have $\lambda(p^{ld-\nu_{p}(c)})\nmid m$. Fix
an integer $k\geq 2$ and write $k=p^{e}r$, where $e,r\in{\mathbb{N}}$ and
$\nu_{p}(r)=0$. Raising $k$ to a suitable power, we can assume $r\equiv
1\pmod{p^{ld}}$. We claim that for $j\in{\mathbb{N}}$ the subsequences
$(\ell_{p^{l},d}(c(k^{j}n+\theta[ej]-\theta)^{m}))_{n\geq 0}$ are all
distinct, which further implies that the considered sequence in not
$k$-automatic. As $l\mid m$, we the congruence (6.3) holds, yielding after
some simplifications

(6.5) $\ell_{p^{l},d}(c(k^{j}n+\theta[ej]-\theta)^{m})\equiv
c(\ell_{p,ld}(n-r^{-j}\theta\\{ej\\}))^{m}\pmod{p^{ld}}.$

Again, we have $r^{-i}\theta\\{ei\\}\neq r^{-j}\theta\\{ej\\}$ for any
distinct $i,j\in{\mathbb{N}}$. Hence, by Lemma 6.3 we can find
$n\in{\mathbb{N}}$ such that

$(\ell_{p,ld}(n-r^{-i}\theta\\{ei\\}))^{m}\not\equiv(\ell_{p,ld}(n-r^{-j}\theta\\{ej\\}))^{m}\pmod{p^{ld-\nu_{p}(c)}}.$

Multiplying both sides $c$, the modulus by $p^{\nu_{p}(c)}$ and using (6.5),
we get

$\ell_{p^{l},d}(c(k^{i}n+\theta[ei]-\theta)^{m})\not\equiv\ell_{p^{l},d}(c(k^{j}n+\theta[ej]-\theta)^{m})\pmod{p^{ld}}.$

The result follows. ∎

We now state the final auxiliary result, which allows us to reduce studying
general functions $f\in\mathcal{A}_{p}$ to those having at most one root in
${\mathbb{Z}}_{p}$.

######  Proposition 6.8.

Let $f\in\mathcal{A}_{p}$ and $\delta\geq 1$ be an integer. Then there exists
an integer $T\geq 0$ such that for each $a=0,1,\ldots,p^{T}-1$ the function
$f_{a}\in\mathcal{A}_{p}$, defined by

$f_{a}(x)=f(p^{T}x+a),$

has at most one root in ${\mathbb{Z}}_{p}$. More precisely:

  1. (i)

if $a\neq\theta[T]$ for all $\theta\in\mathcal{R}_{f}$, then $f_{a}$ has no
root in ${\mathbb{Z}}_{p}$;

  2. (ii)

if $a=\theta[T]$ for some $\theta\in\mathcal{R}_{f}$, then $f_{a}$ has
precisely one root in $\theta\\{T\\}\in{\mathbb{Z}}_{p}$.

Furthermore, for each $\theta\in\mathcal{R}_{f}$ let

$f(x)=(x-\theta)^{m_{f}(\theta)}g_{\theta}(x),$

where $g_{\theta}\in\mathcal{A}_{p}$. Then $T$ can be chosen in such a way
that for all $\theta\in\mathcal{R}_{f}$ and $x\in{\mathbb{Z}}_{p}$ we have

(6.6) $\displaystyle\nu_{p}(g_{\theta}(p^{T}x+\theta[T]))$
$\displaystyle=\nu_{p}(g_{\theta}(\theta)),$ (6.7)
$\displaystyle\ell_{p,\delta}(g_{\theta}(p^{T}x+\theta[T]))$
$\displaystyle=\ell_{p,\delta}(g_{\theta}(\theta)).$

###### Proof.

Consider the partition of ${\mathbb{Z}}_{p}$ into $p^{T}$ balls
$a+p^{T}{\mathbb{Z}}_{p}$, where $a=0,1,\ldots,p^{T}-1$. Let $T_{0}$ be the
minimal value of $T$ such that distinct roots of $f$ lie in distinct balls.
Then for any $T\geq T_{0}$ it is easy to verify that (i) and (ii) hold.

We now show how to refine this choice. For each $\theta\in\mathcal{R}_{f}$ the
function $h_{\theta}\in\mathcal{A}_{p}$ defined by
$h_{\theta}(x)=g_{\theta}(p^{T_{0}}x+\theta[T_{0}])$, has no root in
${\mathbb{Z}}_{p}$. By Proposition 6.1 the sequences
$(\nu_{p}(h_{\theta}(n)))_{n\geq 0}$ and
$(\ell_{p,\delta}(h_{\theta}(n)))_{n\geq 0}$ are periodic. Let $T_{1}$ be such
that $2^{T_{1}}$ is a common period of these sequences for all
$\theta\in\mathcal{R}_{f}$. We claim that for $T=T_{1}+T_{0}$ (or larger) both
equalities (6.6) and (6.7) are satisfied. For each $\theta\in\mathcal{R}_{f}$
the functions $\nu_{p}\circ g_{\theta}$ and $\ell_{p,d}\circ g_{\theta}$ are
constant on balls of the form
$\theta[T_{0}]+p^{T_{0}}(a+p^{T_{1}}{\mathbb{Z}}_{p})=\theta[T_{0}]+p^{T_{0}}a+p^{T}{\mathbb{Z}}_{p}$
for all $a=0,1,\ldots,p^{T_{1}}-1$. In particular, for
$a=p^{-T_{0}}(\theta[T]-\theta[T_{0}])$ we obtain the ball
$\theta[T]+p^{T}{\mathbb{Z}}_{p}$. Since this ball contains $\theta$, we get
(6.6) and (6.7). ∎

We are now ready to combine all the intermediate results in order to prove
Theorems 2.3, 2.5, and 2.7. First, the functions $f\in\mathcal{A}_{p}$ having
no root in ${\mathbb{Z}}_{p}$ fall under part (a) of each theorem, and
Proposition 6.1 implies the corresponding assertions. Therefore, we can focus
on $f$ having at least one root in ${\mathbb{Z}}_{p}$, in which case we will
make use of the following setup in the proofs. Let $T$ be an integer
satisfying the assertion of Proposition 6.8 with $\delta=ld$, and such that
$l\mid T$. For each $a=0,1,\ldots,p^{T}-1$ let $f_{a}\in\mathcal{A}_{p}$ be
defined by

$f_{a}(x)=f(p^{T}x+a),$

precisely as in the proposition. Note that the sequence
$(\nu_{p^{l}}(f(n)))_{n\geq 0}$ is periodic with a period being a power of $p$
if and only if all the sequences $(\nu_{p^{l}}(f_{a}(n)))_{n\geq 0}$ have the
same property. By Proposition 3.2, for fixed $k\geq 2$ a similar observation
can be made regarding $k$-regularity of $(\mathcal{L}_{p^{l}}(f(n)))_{n\geq
0}$ and $k$-automaticity of $(\ell_{p^{l},d}(f(n)))_{n\geq 0}$.

Now, if $a$ is not equal to $\theta[T]$ for any $\theta\in\mathcal{R}_{f}$,
then $f_{a}$ has no root in ${\mathbb{Z}}_{p}$. Therefore, by Proposition 6.1
and the above discussion it is enough to consider the functions
$f_{\theta[T]}$, where $\theta$ ranges over $\mathcal{R}_{f}$. Since $T$ is
fixed, we are going to write $f_{\theta}$ as a shorthand for $f_{\theta[T]}$.
With $g_{\theta}$ as in Proposition 6.8, we have

(6.8)
$f_{\theta}(x)=p^{Tm_{f}(\theta)}\left(x-\theta\\{T\\}\right)^{m_{f}(\theta)}g_{\theta}(p^{T}x+\theta[T]).$

If for each $\theta\in\mathcal{R}_{f}$ we put

$c_{\theta}=p^{Tm_{f}(\theta)}g_{\theta}(\theta),$

then by the equalities (6.6), (6.7), and (6.8) together with the assumption
$l\mid T$, we obtain for all $n\in{\mathbb{N}}$ the following:

(6.9) $\displaystyle\nu_{p^{l}}(f_{\theta}(n))$
$\displaystyle=\nu_{p^{l}}(c_{\theta}(n-\theta\\{T\\})^{m_{f}(\theta)}),$
(6.10) $\displaystyle\mathcal{L}_{p^{l}}(f_{\theta}(n))$
$\displaystyle=\mathcal{L}_{p^{l}}(c_{\theta}(n-\theta\\{T\\})^{m_{f}(\theta)})\cdot\frac{g_{\theta}(p^{T}n+\theta[T])}{g_{\theta}(\theta)},$
(6.11) $\displaystyle\ell_{p^{l},d}(f_{\theta}(n))$
$\displaystyle=\ell_{p^{l},d}(c_{\theta}(n-\theta\\{T\\})^{m_{f}(\theta)}).$

Having this representation, it is rather easy to finish the proofs by
utilizing the earlier results, where $c=c_{\theta}$, $m=m_{f}(\theta)$, and
$\theta$ is replaced with $\theta\\{T\\}$.

###### Proof of Theorem 2.3.

In the case (b) we have $\mathcal{R}_{f}\subset{\mathbb{Q}}$ so for all
$\theta\in\mathcal{R}_{f}$ we also get $\theta\\{T\\}\in{\mathbb{Q}}$.
Equality (6.9) together with Proposition 6.2(i) implies $p$-regularity of
$(\nu_{p^{l}}(f_{\theta}(n)))_{n\geq 0}$. This in turn gives $p$-regularity of
$(\nu_{p^{l}}(f(n)))_{n\geq 0}$ by the above discussion.

At the same time, if this sequence were $k$-regular for some $k$
multiplicatively independent with $p$, then for any positive integer $u$ and
any $\theta\in\mathcal{R}_{f}$ the sequence
$(\nu_{p^{l}}(f_{\theta}(n))\bmod{u})_{n\geq 0}$ would be simultaneously $p$\-
and $k$-automatic. Due to Cobham’s Theorem it would then be eventually
periodic, and this is not the case when $u\nmid m_{f}(\theta)$, as Proposition
6.4 shows.

In the case (c) Proposition 6.7 says that $(\nu_{p^{l}}(f_{\theta}(n)))_{n\geq
0}$ is not regular for any $\theta\in\mathcal{R}_{f}$. Therefore,
$(\nu_{p^{l}}(f(n)))_{n\geq 0}$ cannot be regular either. ∎

###### Proof of Theorem 2.5.

In the case (b) the first factor on the right-hand side of (6.10) is
$p$-regular due to Proposition 6.2(ii). The second factor is $p$-regular as
well as a polynomial in $n$, and therefore
$(\mathcal{L}_{p^{l}}(f_{\theta}(n)))_{n\geq 0}$ is $p$-regular as a termwise
product of such sequences. Hence, $(\mathcal{L}_{p^{l}}(f(n)))_{n\geq 0}$ is
$p$-regular too. At the same time, it cannot be $k$-regular for $k$
multiplicatively independent with $p$, as then for all $d$ the sequence
$(\ell_{p^{l},d}(f(n)))_{n\geq 0}$ would be $k$-automatic, and this
possibility is ruled out by Theorem 2.7(b).

In a similar fashion, in the case (c) Theorem 2.7(c) implies that
$(\mathcal{L}_{p^{l}}(f(n)))_{n\geq 0}$ is not $k$-regular for any $k$. ∎

###### Proof of Theorem 2.7.

If $\mathcal{R}^{\prime}_{f}=\varnothing$, as in (a), then for all
$\theta\in\mathcal{R}_{f}$ the condition (C) holds with $c=c_{\theta}$ and
$m=m_{f}(\theta)$. Here it is important that $l\mid T$ so that
$\nu_{p}(c_{\theta})\equiv\nu_{p}(g_{\theta}(\theta))\pmod{l}$. By Proposition
6.5 applied to (6.11), this implies that
$(\ell_{p^{l},d}(f_{\theta}(n)))_{n\geq 0}$ is periodic for all
$\theta\in\mathcal{R}_{f}$, and thus so is $(\ell_{p^{l},d}(f(n)))_{n\geq 0}$.

In the case (b), the condition (C) holds for all irrational
$\theta\in\mathcal{R}_{f}$ in the same sense as above. Propositions 6.5 and
6.2(iii) together imply $p$-automaticity of $(\ell_{p^{l},d}(f(n)))_{n\geq
0}$. At the same time, there exists some rational $\theta\in\mathcal{R}_{f}$
for which (C) does not hold. As a consequence,
$(\ell_{p^{l},d}(f_{\theta}(n)))_{n\geq 0}$ is not eventually periodic, thus
neither is $(\ell_{p^{l},d}(f(n)))_{n\geq 0}$.

Finally, in the case (c) there exists some irrational
$\theta\in\mathcal{R}_{f}$ for which (C) does not hold. By Proposition 6.7,
the sequence $(\ell_{p^{l},d}(f_{\theta}(n)))_{n\geq 0}$ is not automatic so
$(\ell_{p^{l},d}(f(n)))_{n\geq 0}$ is not automatic either. ∎

##  7\. Proofs for $b$ having several prime factors

Like before, let $b\geq 2$ be an integer base with prime factorization

$b=p_{1}^{l_{1}}\cdots p_{s}^{l_{s}},$

where $p_{1},\ldots,p_{s}$ are distinct primes and $l_{1},\ldots,l_{s}$ are
positive integers. For $i=1,\ldots,s$ we put $b_{i}=p_{i}^{l_{i}}$. Throughout
the whole section we assume that $s\geq 2$, unless specified otherwise. We
retain the notation from the preceding sections, namely
${\mathbb{Q}}_{b},{\mathbb{Z}}_{b},\mathcal{A}_{b},\mathcal{P}_{b},\mathcal{R}_{f}$
and so on.

To begin, we prove Propositions 2.1 and 2.2, dealing with degenerate cases.

###### Proof of Proposition 2.1.

Without loss of generality we can assume $i=s$, so that $f_{s}=0$,
$\overline{b}=b/b_{s}$, and $\overline{f}=(f_{1},\ldots,f_{s-1})$. Since
$\nu_{b_{s}}(f_{s}(n))=+\infty$ for all $n\in{\mathbb{N}}$, we get

$\nu_{b}(f(n))=\nu_{\overline{b}}(\overline{f}(n))$

which immediately gives (i).

By the above equality we can write

$\mathcal{L}_{b}(f(n))=\left(\mathcal{L}_{\overline{b}}(\overline{f}(n)),0\right).$

Since the zero sequence is $k$-regular for all $k\geq 2$, by Proposition
3.3(iv) we obtain (ii).

Finally, let $(\gamma_{1}(n),\ldots,\gamma_{s}(n))$ be the image of
$\ell_{b,d}(f(n))$ through the natural isomorphism between
${\mathbb{Z}}/b^{d}{\mathbb{Z}}$ and
${\mathbb{Z}}/b_{1}{\mathbb{Z}}\times\cdots\times{\mathbb{Z}}/b_{s}{\mathbb{Z}}$.
We can deduce from Proposition 3.3(iv) that the sequence
$(\ell_{b,d}(f(n)))_{n\geq 0}$ is $k$-automatic if and only if for each
$i=1,\ldots,s$ the sequence $(\gamma_{i}(n))_{n\geq 0}$ is $k$-automatic. By
our assumption $\gamma_{s}(n)=0$ for all $n\in{\mathbb{N}}$, and so this
sequence is $k$-automatic for all $k\geq 2$. Since the same equivalence holds
for $\ell_{\overline{b},d}(\overline{f}(n))$ and
$(\gamma_{1}(n),\ldots,\gamma_{s-1}(n))$, we obtain (iii). ∎

In the following proof we allow $s=1$.

###### Proof of Proposition 2.2.

There exist $T,a\in{\mathbb{N}}$ such that for each $i=1,\ldots,s$ the
function $h=(h_{1},\ldots,h_{s})$, given by $h(x)=f(b^{T}x+a)$, has no roots
in ${\mathbb{Z}}_{b}$. (One can take $T$ sufficiently large and
$a\not\equiv\theta\pmod{b^{T}}$.) Proposition 7.2(i) below says that the
sequence $(\nu_{b}(h(n)))_{n\geq 0}$ is periodic with period being a power of
$b$. By increasing $T$ if necessary, we can assume that it is constant.
Letting $v=\nu_{b}(h(n))$, we obtain

$\mathcal{L}_{b}(h(n))=b^{-v}h(n).$

If the original sequence $(\mathcal{L}_{b}(f(n)))_{n\geq 0}$ is $k$-regular,
then Proposition 4.3 implies that so is $(b^{-v}h_{i}(n))_{n\geq 0}$ for
$i=1,\ldots,s$. It is thus enough to prove for a prime $p$ and
$h\in\mathcal{A}_{p}$ that if $(h(n))_{n\geq 0}$ is $k$-regular, then $h$ is a
polynomial.

Write

$h(x)=\sum_{m=0}^{\infty}a_{m}x^{m},$

where $a_{m}\in{\mathbb{Q}}_{p}$ for all $m\in{\mathbb{N}}$. Consider the
${\mathbb{Z}}$-submodule generated by the family of subsequences
$\mathbf{h}_{j}=(h(k^{j}n))_{n\geq 0}$, where $j\in{\mathbb{N}}$. If
$(h(n))_{n\geq 0}$ is $k$-regular, then said ${\mathbb{Z}}$-submodule is
generated by $\mathbf{h}_{0},\mathbf{h}_{1},\ldots,\mathbf{h}_{J}$ for some
$J\in{\mathbb{N}}$. In particular, there exist
$\beta_{0},\beta_{1},\ldots,\beta_{J}\in{\mathbb{Z}}$ such that for all
$n\in{\mathbb{N}}$ we have

$h(k^{J+1}n)=\sum_{j=0}^{J}\beta_{j}h(k^{j}n).$

As ${\mathbb{N}}$ is dense in ${\mathbb{Z}}_{p}$, the coefficients on both
sides must be equal, which yields

$a_{m}\left(k^{(J+1)m}-\sum_{j=0}^{J}\beta_{j}k^{jm}\right)=0$

for all $m\in{\mathbb{N}}$. However, as $m$ tends to infinity, then so does
the expression in the parentheses (as a real number) so only finitely many
$a_{m}$ can be nonzero. ∎

From now on we will only deal with $f=(f_{1},\ldots,f_{s})$ having nonzero
components, namely $f\in\mathcal{A}_{b}$. The general structure of our
reasoning leading to Theorems 2.4, 2.6, and 2.8 is similar as in the previous
section. The main idea is again to reduce the general case to considering $f$
such that $f_{i}$ either has no root in ${\mathbb{Z}}_{p_{i}}$ or is of the
form $c_{i}(x-\theta_{i})^{m_{i}}$. However the technical details involved in
the auxiliary results are rather different.

The following technical lemma plays a similar role to Lemma 6.3.

######  Lemma 7.1.

Let $\rho_{i},\sigma_{i}\in{\mathbb{Z}}_{p_{i}}$ for $i=1,\ldots,s$ and assume
that $(\rho_{1},\ldots,\rho_{s})\neq(\sigma_{1},\ldots,\sigma_{s})$. Let
$m_{i}$ be positive integers and $c_{i},d_{i}\in{\mathbb{Q}}_{p_{i}}$. Then we
have the following.

  1. (i)

There exists $j\in\\{1,\ldots,s\\}$ and infinitely many $n\in{\mathbb{N}}$
such that

$\displaystyle\nu_{b_{j}}(c_{j}(n-\rho_{j})^{m_{j}})$
$\displaystyle>\nu_{b}\left(c_{1}(n-\rho_{1})^{m_{1}},\ldots,c_{s}(n-\rho_{s})^{m_{s}}\right),$
$\displaystyle\nu_{b_{j}}(d_{j}(n-\sigma_{j})^{m_{j}})$
$\displaystyle=\nu_{b}\left(d_{1}(n-\sigma_{1})^{m_{1}},\ldots,d_{s}(n-\sigma_{s})^{m_{s}}\right).$

  2. (ii)

Let $C\in{\mathbb{N}}$ be such that $C\geq 3+2\max_{1\leq i\leq
s}(m_{i}/l_{i})$ and $\nu_{p_{i}}(c_{i})\equiv\nu_{p_{i}}(d_{i})\pmod{l_{i}C}$
for all $i=1,\ldots,s$. Then there exist infinitely many $n$ such that

$\nu_{b}\left(c_{1}(n-\rho_{1})^{m_{1}},\ldots,c_{s}(n-\rho_{s})^{m_{s}}\right)\not\equiv\nu_{b}\left(d_{1}(n-\sigma_{1})^{m_{1}},\ldots,d_{s}(n-\sigma_{s})^{m_{s}}\right)\pmod{C}.$

###### Proof.

Up to renumbering, we can assume that $\rho_{i}\neq\sigma_{i}$ for $i\leq I$,
for some $I\in\\{2,\ldots,s\\}$, and $\rho_{i}=\sigma_{i}$ otherwise. In
particular, we have at least $\rho_{1}\neq\sigma_{1}$.

In part (i) we will show that the assertion holds with $j=1$. It is sufficient
to find infinitely many $n$ satisfying the inequalities

(7.1) $\displaystyle\nu_{b_{2}}(c_{2}(n-\rho_{2})^{m_{2}})$
$\displaystyle<\nu_{b_{1}}(c_{1}(n-\rho_{1})^{m_{1}}),$ (7.2)
$\displaystyle\nu_{b_{1}}(d_{1}(n-\sigma_{1})^{m_{1}})$
$\displaystyle\leq\min_{2\leq i\leq
s}\nu_{b_{i}}(d_{i}(n-\sigma_{i})^{m_{i}}).$

To begin, observe that for any choice of $v_{1},\ldots,v_{s}\in{\mathbb{N}}$
there exist infinitely many $n\in{\mathbb{N}}$ such that

$\begin{cases}\nu_{p_{1}}(n-\rho_{1})=v_{1},\\\
\nu_{p_{i}}(n-\sigma_{i})=v_{i},&i\geq 2,\end{cases}$

which is a consequence of the Chinese Remainder Theorem.

If $\rho_{2}\neq\sigma_{2}$, then as we increase $v_{1},\ldots,v_{s}$, the
right-hand side of both (7.1) and (7.2) grows to infinity, while the left-hand
side remains bounded. Hence, it is enough to take $v_{1},\ldots,v_{s}$
sufficiently large, and the corresponding values $n$ all satisfy the
assertion. If $\rho_{2}=\sigma_{2}$, choosing large $v_{1},\ldots,v_{s}$ also
works, except in order for (7.1) to hold we additionally require $v_{1},v_{2}$
to satisfy

$\left\lfloor\frac{\nu_{p_{2}}(c_{2})+m_{2}v_{2}}{l_{2}}\right\rfloor<\left\lfloor\frac{\nu_{p_{1}}(c_{1})+m_{1}v_{1}}{l_{1}}\right\rfloor.$

We now move on to part (ii). Put $u_{i}=\nu_{p_{i}}(\rho_{i}-\sigma_{i})$ for
$i\leq I$ and assume (up to further renumbering) that

(7.3) $\frac{\nu_{p_{1}}(d_{1})+m_{1}u_{1}}{l_{1}}=\min_{i\leq
I}\frac{\nu_{p_{i}}(d_{i})+m_{i}u_{i}}{l_{i}}.$

In order to prove the assertion it is sufficient to find infinitely many
$n\in{\mathbb{N}}$ such that

(7.4) $\displaystyle\nu_{b_{1}}(c_{1}(n-\rho_{1})^{m_{1}})$
$\displaystyle\leq\min_{2\leq i\leq s}\nu_{b_{i}}(c_{i}(n-\rho_{i})^{m_{i}}),$
(7.5) $\displaystyle\nu_{b_{1}}(d_{1}(n-\sigma_{1})^{m_{1}})$
$\displaystyle\leq\min_{2\leq i\leq
s}\nu_{b_{i}}(d_{i}(n-\sigma_{i})^{m_{i}}),$

and also

(7.6)
$\nu_{b_{1}}(c_{1}(n-\rho_{1})^{m_{1}})\not\equiv\nu_{b_{1}}(d_{1}(n-\sigma_{1})^{m_{1}})\pmod{C}.$

This time, we put

$v_{1}=u_{1}+2\left\lceil\frac{l_{1}}{m_{1}}\right\rceil$

and choose $v_{2},\ldots,v_{s}$ in such a way that for all $i=2,\ldots,s$ we
have

$\displaystyle u_{i}$ $\displaystyle<v_{i},$ (7.7)
$\displaystyle\frac{\nu_{p_{1}}(c_{1})+m_{1}v_{1}}{l_{1}}$
$\displaystyle\leq\frac{\nu_{p_{i}}(c_{i})+m_{i}v_{i}}{l_{i}},$

and also for all $i>I$ (if any)

(7.8)
$\frac{\nu_{p_{1}}(d_{1})+m_{1}u_{1}}{l_{1}}\leq\frac{\nu_{p_{i}}(d_{i})+m_{i}v_{i}}{l_{i}}.$

Again, there exist infinitely many $n\in{\mathbb{N}}$ simultaneously
satisfying the equalities

$\nu_{p_{1}}(n-\rho_{i})=v_{i}$

for all $i=1,\ldots,s$. For such $n$ the inequality (7.4) is precisely the
condition (7.7). Moreover, the inequalities $v_{i}>u_{i}$ for $i\leq I$ yield

$\nu_{p_{i}}(n-\sigma_{i})=\begin{cases}u_{i}&\text{if }i\leq I,\\\
v_{i}&\text{if }i>I.\end{cases}$

Combined with (7.3) (for $i\leq I$) and (7.8) (for $i>I$), this gives (7.5).
Finally, by the assumption
$\nu_{p_{1}}(c_{1})\equiv\nu_{p_{1}}(d_{1})\pmod{l_{1}C}$, we obtain

$\displaystyle\nu_{b_{1}}(c_{1}(n-\rho_{1})^{m_{1}})-\nu_{b_{1}}(d_{1}(n-\sigma_{1})^{m_{1}})$
$\displaystyle\equiv\left\lfloor\frac{\nu_{p_{1}}(c_{1})+v_{1}m_{1}}{l_{1}}\right\rfloor-\left\lfloor\frac{\nu_{p_{1}}(d_{1})+u_{1}m_{1}}{l_{1}}\right\rfloor$
$\displaystyle\equiv\left\lfloor\frac{v_{1}m_{1}}{l_{1}}\right\rfloor-\left\lfloor\frac{u_{1}m_{1}}{l_{1}}\right\rfloor\pmod{C}$

By the choice of $v_{1}$ and the inequality $x-y-1\leq\lfloor x\rfloor-\lfloor
y\rfloor\leq x-y+1$ valid for any real $x,y$, we get

$0<\left\lfloor\frac{v_{1}m_{1}}{l_{1}}\right\rfloor-\left\lfloor\frac{u_{1}m_{1}}{l_{1}}\right\rfloor<C.$

The non-congruence (7.6) follows. ∎

We now treat the case where for $f=(f_{1},\ldots,f_{i})$ the functions $f_{i}$
have no root in ${\mathbb{Z}}_{p_{i}}$. In contrast to Proposition 6.1, here
all the considered conditions are equivalent, as there is no counterpart to
(C). For the sake of convenience while proving necessity we allow each $f_{i}$
to have at most one root, an assumption which will ultimately be relaxed.

######  Proposition 7.2.

Let $f\in\mathcal{A}_{b}$ be such that for each $i\in\\{1,\ldots,s\\}$ the
function $f_{i}$ either has no root in ${\mathbb{Z}}_{p_{i}}$ or it is of the
form

(7.9) $f_{i}(x)=c_{i}(x-\theta_{i})^{m_{i}},$

for some $c_{i}\in{\mathbb{Q}}_{p_{i}}$, $\theta_{i}\in{\mathbb{Z}}_{p_{i}}$,
and positive integer $m_{i}$. Then the following conditions are equivalent:

  1. (i)

for some $i\in\\{1,\ldots,s\\}$ the function $f_{i}$ has no root in
${\mathbb{Z}}_{p_{i}}$;

  2. (ii)

the sequence $(\nu_{b}(f(n)))_{n\geq 0}$ is eventually periodic;

  3. (iii)

for all $d\geq 1$ the sequence $(\ell_{b,d}(f(n)))_{n\geq 0}$ is eventually
periodic;

  4. (iv)

the sequence $(\ell_{b}(f(n)))_{n\geq 0}$ is eventually periodic.

If either case holds, then the sequences $(\nu_{b}(f(n)))_{n\geq 0}$ and
$(\ell_{b,d}(f(n)))_{n\geq 0}$ are purely periodic and a power of $b$ can be
chosen as a period.

Furthermore, if $f\in\mathcal{P}_{b}$, then the conditions (i)–(iv) are also
equivalent to:

  1. (v)

the sequence $(\mathcal{L}_{b}(f(n)))_{n\geq 0}$ is $k$-regular for all $k\geq
2$.

###### Proof.

We will prove the chain of implications
(i)$\implies$(ii)$\implies$(iii)$\implies$ (iv) $\implies$(i). In the case
when $f\in\mathcal{P}_{b}$ we additionally show that
(ii)$\implies$(v)$\implies$(iii).

First, if some $f_{i}$ has no root in ${\mathbb{Z}}_{p_{i}}$, there exists
$V\in{\mathbb{N}}$ such that $\nu_{b_{i}}(f_{i}(n))<V$ for all
$n\in{\mathbb{N}}$, and therefore also $\nu_{b}(f(n))<V$. By uniform
continuity of $f_{i}$ there exists $T_{i}\in{\mathbb{N}}$ such that for all
$x,y\in{\mathbb{Z}}_{p_{i}}$ we have

$\nu_{b_{i}}(f_{i}(x+b_{i}^{T_{i}}y)-f_{i}(x))\geq V.$

Letting $b^{T}$ be a common multiple of $b_{1}^{T_{1}},\ldots,b_{s}^{T_{s}}$
and putting $y=b^{T}/b^{T_{i}}$, we can write

(7.10) $f_{i}(x+b^{T})=f_{i}(x)+b_{i}^{V}h_{i}(x),$

where $h_{i}(x)\in{\mathbb{Z}}_{p_{i}}$. For each $i=1,\ldots,s$ let

$v_{i}(x)=\min\\{\nu_{b_{i}}(f_{i}(x)),V\\}.$

We have $\nu_{b}(f(n))=\min_{1\leq i\leq s}v_{i}(n)$ and, at the same time,
(7.10) implies $v_{i}(n+b^{T})=v_{i}(n)$ for all $n\in{\mathbb{N}}$.
Therefore, we also get

$\nu_{b}(f(n+b^{T}))=\nu_{b}(f(n)),$

which proves (ii). In particular, the sequence $(\nu_{b}(f(n)))_{n\geq 0}$ is
purely periodic and a power of $b$ is a period.

Now assume that (ii) holds and assume without loss of generality that the
sequence $(\nu_{b}(f(n)))_{n\geq 0}$ is purely periodic (by shifting the
original sequence). Let $\pi$ be its period. Then for each
$a=0,1,\ldots,\pi-1$ and all $n\in{\mathbb{N}}$ we have

$\mathcal{L}_{b}(f(\pi n+a))=b^{-\nu_{b}(f(a))}f(\pi n+a).$

Fix $a$ and let $g_{i}(x)$ denote the $i$th component of
$\mathcal{L}_{b}(f(\pi x+a))$. Then $g_{i}\in\mathcal{A}_{p_{i}}$ and uniform
continuity shows that the sequence $(g_{i}(n)\bmod{b_{i}^{d}})_{n\geq 0}$ is
purely periodic, where a power of $p_{i}$ can be chosen as a period. Since
$\ell_{b,d}(f(\pi n+a))=(g_{1}(n),\ldots,g_{s}(n))\bmod{b^{d}}$, we obtain
that $(\ell_{b,d}(f(\pi n+a)))_{n\geq 0}$ is also purely periodic, where a
power of $b$ can be chosen as a period. A similar claim thus holds for the
whole sequence $(\ell_{b,d}(f(n)))_{n\geq 0}$ which proves (iii). Moreover,
observe that if $\pi=b^{T}$, then a power of $b$ is also a period of this
sequence.

In the case when $f\in\mathcal{P}_{b}$, each component of
$\mathcal{L}_{b}(f(\pi n+a))$ is a polynomial in $n$ so it constitutes a
sequence $k$-regular for all $k\geq 2$. Hence, (v) follows from (ii). At the
same time, (v) immediately implies (iii) due to Cobham’s theorem.

The implication from (iii) to (iv) is trivial.

Finally, we prove that (iv) implies (i). Suppose that $(\ell_{b}(f(n)))_{n\geq
0}$ is eventually periodic with period $\pi$ but all $f_{i}$ are of the form
(7.9). We are going to arrive at a contradiction with eventual periodicity of
the characteristic sequences of the set

$\\{n\in{\mathbb{N}}:\ \nu_{b_{j}}(f_{j}(n))=\nu_{b}(f(n))\\}$

for some $j\in\\{1,\ldots,s\\}$. In order to do this we apply Lemma 7.1(i) to
$\rho_{i}=\theta_{i},\sigma_{i}=\theta_{i}-\pi$, and $d_{i}=c_{i}$. As a
result, for some $j\in\\{1,\ldots,s\\}$ we obtain infinitely many
$n\in{\mathbb{N}}$ such that

$\nu_{b_{j}}(f_{j}(n))>\nu_{b}(f(n))$

but also

$\nu_{b_{j}}(f_{j}(n+\pi))=\nu_{b}(f(n+\pi)),$

thus a contradiction. ∎

In the following few results we assume that

$f_{i}(x)=c_{i}(x-\theta_{i})^{m_{i}},$

where $c_{i}\in{\mathbb{Q}}_{p_{i}}$, $\theta_{i}\in{\mathbb{Z}}_{p_{i}}$ and
$m_{i}$ is a positive integer. We first study $k$-regularity of the considered
sequences ich the case $\theta_{1}=\ldots=\theta_{s}$, where $k$ is a specific
value depending on $m_{1},\ldots,m_{s}$.

######  Proposition 7.3.

Let $\theta\in{\mathbb{Q}}\cap{\mathbb{Z}}_{b}$. For each $i=1,\ldots,s$ let

$f_{i}(x)=c_{i}(x-\theta)^{m_{i}}.$

Let $k=b_{1}^{w_{1}}\cdots b_{s}^{w_{s}}$ where $w_{1},\ldots,w_{s}$ are
positive integers satisfying

$m_{1}w_{1}=\cdots=m_{s}w_{s}.$

We have the following:

  1. (i)

the sequence $(\nu_{b}(f(n)))_{n\geq 0}$ is $k$-regular;

  2. (ii)

if $m_{1}=\cdots=m_{s}$, then the sequence $(\mathcal{L}_{b}(f(n)))_{n\geq 0}$
is $b$-regular;

  3. (iii)

for all $d\geq 1$ the sequence $(\ell_{b,d}(f(n)))_{n\geq 0}$ is
$k$-automatic.

###### Proof.

Writing $\theta=q/r$ in lowest terms with $r>0$, we obtain

$f_{i}(n)=\frac{c_{i}}{r^{m_{i}}}(rn-q)^{m_{i}}$

By Proposition 3.2, without loss of generality we may thus assume that
$\theta=0$, namely

$f_{i}(x)=c_{i}x^{m_{i}}.$

We first prove parts (i) and (iii) simultaneously. For the sake of (iii), by
raising $k$ to a suitable power, we can assume that $\ell_{b_{i},d}(k)=1$ and
$(b/b_{i})^{D}\equiv 1\pmod{b_{i}^{d}}$ for each $i=1,\ldots,s$, where $D$
denotes the common value of $m_{i}w_{i}$.

Consider the subsequences $(f(kn+a))_{n\geq 0}$ with $a=0,1,\ldots,k-1$. For
$a=0$ have

$f(kn)=(k^{m_{1}},\ldots,k^{m_{s}})\cdot f(n)=b^{D}Kf(n),$

where $K=b^{-D}(k^{m_{1}},\ldots,k^{m_{s}})\in{\mathbb{Z}}_{b}$. Since
$\nu_{p_{i}}(b^{-D}k^{m_{i}})=0$, we obtain

$\nu_{b}(f(kn))=D+\nu_{b}(f(n)).$

By the conditions imposed on $k$, we get

$\ell_{b_{i},d}(b^{-D}k^{m_{i}})\equiv
b^{-D}k^{m_{i}}\equiv\left(\frac{b_{i}}{b}\right)^{D}\left(\frac{k}{b_{i}^{w_{i}}}\right)^{m_{i}}\equiv(\ell_{b_{i},d}(k))^{m_{i}}\equiv
1\pmod{b_{i}^{d}}.$

This implies $\ell_{b,d}(K)=1,$ and hence Proposition 4.2(ii) yields

$\ell_{b,d}(f(kn))\equiv\ell_{b,d}(K)\ell_{b,d}(f(n))\equiv\ell_{b,d}(f(n))\pmod{b^{d}}.$

Now, for $a\neq 0$ we must have $\nu_{p_{i}}(a)<\nu_{p_{i}}(k)$ for some $i$
so the function $f_{i}(kx+a)$ of $x\in{\mathbb{Z}}_{p_{i}}$ has no root in
${\mathbb{Z}}_{p_{i}}$. As a consequence of Proposition 7.2, both sequences
$(\nu_{b}(f(kn+a)))_{n\geq 0}$ and $(\ell_{b,d}(f(kn+a)))_{n\geq 0}$ are
periodic, and thus $k$-automatic. An argument similar to the one in
Proposition 4.5 gives the assertion of (i) and (iii).

In part (ii), if we let $m$ denote the common value of $m_{i}$, then
$f(bn)=b^{m}f(n)$, and consequently

$\mathcal{L}_{b}(f(bn))=\mathcal{L}_{b}(f(n)).$

For each $a=1,\ldots,b-1$ the sequence $(\mathcal{L}_{b}(f(bn+a)))_{n\geq 0}$
is $b$-regular by Proposition 7.2, and again we deduce $b$-regularity of
$(\mathcal{L}_{b}(f(n)))_{n\geq 0}$. ∎

On the other hand, in the case when $\theta_{1},\ldots,\theta_{s}$ are not all
equal, we obtain nonregular sequences.

######  Proposition 7.4.

For each $i=1,\ldots,s$ let

$f_{i}(x)=c_{i}(x-\theta_{i})^{m_{i}}.$

If $\theta_{1},\ldots,\theta_{s}$ are not all equal, then:

  1. (i)

the sequence $(\nu_{b}(f(n)))_{n\geq 0}$ is not regular;

  2. (ii)

the sequence $(\mathcal{L}_{b}(f(n)))_{n\geq 0}$ is not regular;

  3. (iii)

the sequence $(\ell_{b,d}(f(n)))_{n\geq 0}$ is not automatic for any $d\geq
1$.

###### Proof.

To begin, observe that (ii) follows immediately from (iii), as the reduction
modulo $b^{d}$ of a $k$-regular sequence is $k$-regular. By the same argument,
in (iii) it is sufficient to consider $d=1$.

Hence, we shall prove that the sequences $(\nu_{b}(f(n)))_{n\geq 0}$ and
$(\ell_{b}(f(n)))_{n\geq 0}$ are not $k$-regular for any integer $k\geq 2$. We
begin with some preparatory steps. Let $C\geq 3+2\max_{1\leq i\leq
s}(m_{i}/l_{i})$ be an integer, as in the statement of Lemma 7.1(ii). By
raising $k$ to a suitable power, we may assume that it is of the form

$k=b_{1}^{w_{1}}\cdots b_{s}^{w_{s}}e,$

where $w_{1},\ldots,w_{s},e$ are nonnegative integers such that $C\mid w_{i}$
for $i=1,\ldots,s$ and $b,e$ are coprime.

Let $(n_{t})_{t\geq 0}$ be the sequence integers given by

$\left\\{\begin{aligned} n_{t}&\equiv\theta_{1}\pmod{b_{1}^{w_{1}t}},\\\
&\;\vdots\\\ n_{t}&\equiv\theta_{s}\pmod{b_{s}^{w_{s}t}},\end{aligned}\right.$

where $0\leq n_{t}<(b_{1}^{w_{1}}\cdots b_{s}^{w_{s}})^{t}\leq k^{t}$. In
particular, if $b,k$ are coprime, then $n_{t}=0$ for all $t\in{\mathbb{N}}$.
We are going to consider $\nu_{b}$ and $\ell_{b}$ evaluated at the
subsequences $(f(k^{t}n+n_{t}))_{n\geq 0}$. The $i$-th component of
$f(k^{t}n+n_{t})$ can be written in the form

$f_{i}(k^{t}n+n_{t})=c_{i}k^{tm_{i}}\left(n-\frac{\theta_{i}-n_{t}}{k^{t}}\right)^{m_{i}}$

for all $n\in{\mathbb{N}}$. Fix any distinct $t,r\in{\mathbb{N}}$ and put
$\rho_{i}=(\theta_{i}-n_{t})/k^{t}$ and $\sigma_{i}=(\theta_{i}-n_{r})/k^{r}$.

We argue that the assumption
$(\rho_{1},\ldots,\rho_{s})\neq(\sigma_{1},\ldots,\sigma_{s})$ of Lemma 7.1 is
satisfied. Observe that the equality $\rho_{i}=\sigma_{i}$ holds if and only
if

$\theta_{i}=\frac{k^{t}n_{r}-k^{r}n_{t}}{k^{t}-k^{r}},$

and the expression on the right-hand side does not depend on $i$. Since
$\theta_{1},\ldots,\theta_{s}$ are not all equal, we must have
$\rho_{i}\neq\sigma_{i}$ for some $i$.

We now focus on part (i). If the sequence $(\nu_{b}(f(n)))_{n\geq 0}$ were
$k$-regular, then its reduction modulo $C$ would be $k$-automatic. Since
$\nu_{p_{i}}(c_{i}k^{tm_{i}})\equiv\nu_{p_{i}}(c_{i}k^{rm_{i}})\pmod{Cl_{i}}$,
all the assumptions of Lemma 7.1(ii) are satisfied (where $c_{i}$ is replaced
with $c_{i}k^{tm_{i}}$ and $d_{i}=c_{i}k^{rm_{i}}$). Hence, there exists
$n\in{\mathbb{N}}$ (in fact, infinitely many) such that

$\nu_{b}(f(k^{t}n+n_{t}))\not\equiv\nu_{b}(f(k^{r}n+n_{r}))\pmod{C}.$

But this means that the $k$-kernel of $(\nu_{b}(f(n))\bmod{C})_{n\geq 0}$
contains infinitely many distinct subsequences, a contradiction.

Similarly, if the sequence $(\ell_{b}(f(n)))_{n\geq 0}$ were $k$-automatic,
then so would be the characteristic sequence of the set

$\\{n\in{\mathbb{N}}:\ \nu_{b_{j}}(f_{j}(n))=\nu_{b}(f(n))\\}$

for each fixed $j\in\\{1,\ldots,s\\}$. But then again, Lemma 7.1(i) provides
some $j\in\\{1,\ldots,s\\}$ and infinitely many $n\in{\mathbb{N}}$ such that

$\nu_{b_{j}}(f_{j}(k^{t}n+n_{t}))>\nu_{b}(f(k^{t}n+n_{t}))$

and

$\nu_{b_{j}}(f_{j}(k^{r}n+n_{r}))=\nu_{b}(f(k^{r}n+n_{r})).$

Therefore, the $k$-kernel of said characteristic sequence contains infinitely
many distinct subsequences. ∎

The final step before the proofs of the main results is to show nonregularity
of the sequence $(\mathcal{L}_{b}(f(n)))_{n\geq 0}$ when all $f_{i}$ have the
same, unique root in ${\mathbb{Z}}_{b}\cap{\mathbb{Q}}$ but its multiplicity
varies with $i$. To this end we need a standard fact which essentially says
that for any base $b$ the $b$-adic expansion of a rational number is
eventually periodic. Since we have not been able to find a suitable reference
for non-prime $b$, we provide a short proof for the sake of completeness. For
$\theta\in{\mathbb{Z}}_{b}$ we extend the notation from the previous section
by writing $\theta[t,b]=\theta\bmod{b^{t}}$ and
$\theta\\{t,b\\}=(\theta-\theta[t,b])/b^{t}$ for each $t\in{\mathbb{N}}$. Here
it is important to specify the base $b$, as any $b^{\prime}$ having identical
prime factors to $b$ yields the same ring ${\mathbb{Z}}_{b}$ but (usually)
distinct values $\theta[t,b^{\prime}],\theta\\{t,b^{\prime}\\}$. Only when
there is no danger of confusion, $b$ will be suppressed from the notation.

######  Lemma 7.5.

Let $b\geq 2$ be an integer and $\theta\in{\mathbb{Q}}\cap{\mathbb{Z}}_{b}$.
Then the sequence $(\theta\\{t,b\\})_{t\geq 0}$ is eventually periodic.

###### Proof.

Considering $b$ fixed, we omit it in the notation. We first prove that
$(\theta\\{t+r\\})=(\theta\\{t\\})\\{r\\}$ for each fixed $t$ and all
$r\in{\mathbb{N}}$. This is obvious for $r=0$. For $r=1$ we first compute

$(\theta\\{t\\})[1]\equiv\frac{\theta-\theta[t]}{b^{t}}\equiv\frac{\theta[t+1]-\theta[t]}{b^{t}}\pmod{b},$

which implies

$(\theta\\{t\\})\\{1\\}=\frac{\theta\\{t\\}-(\theta\\{t\\})[1]}{b}=\frac{\frac{\theta-\theta[t]}{b^{t}}-\frac{\theta[t+1]-\theta[t]}{b^{t}}}{b}=\theta\\{t+1\\}.$

For general $r$ the claim follows by induction.

Moving on to the statement of the lemma, write $\theta=v/u$ in lowest terms.
Since $u\theta[t]\equiv v\pmod{b^{t}}$, the number
$u\theta\\{t\\}=(v-u\theta[t])/b^{t}$ is an integer for each $t$. Moreover, we
have the bound

$\left|\frac{v-u\theta[t]}{b^{t}}\right|\leq|v|+|u|\frac{\theta[t]}{b^{t}}<|v|+|u|.$

Therefore, there exist indices $r>t$ such that

$\frac{\theta-\theta[r]}{b^{r}}=\frac{\theta-\theta[t]}{b^{t}},$

which yields $\theta\\{r\\}=\theta\\{t\\}$. Consequently,
$\theta\\{r+w\\}=\theta\\{t+w\\}$ for all $w\in{\mathbb{N}}$. ∎

We can now prove the aforementioned result.

######  Lemma 7.6.

Let $f=(f_{1},\ldots,f_{s})\in\mathcal{P}_{b}$ and assume that for each
$i=1,\ldots,s$ the function $f_{i}$ is of the form

$f_{i}(x)=(x-\theta)^{m_{i}}g_{i}(x),$

where $m_{i}\geq 1$ is an integer,
$\theta\in{\mathbb{Q}}\cap{\mathbb{Z}}_{b}$, and $g_{i}\in\mathcal{P}_{p_{i}}$
is such that the values $\nu_{p_{i}}(g_{i}(x))$,
$\ell_{p_{i},l_{i}}(g_{i}(x))$ are constant with respect to
$x\in{\mathbb{Z}}_{p_{i}}$. If the exponents $m_{i}$ are not all equal, then
the sequence $(\mathcal{L}_{b}(f(n)))_{n\geq 0}$ is not regular.

###### Proof.

If the sequence $(\mathcal{L}_{b}(f(n)))_{n\geq 0}$ were $k$-regular for some
$k\geq 2$, then $(\ell_{b}(f(n)))_{n\geq 0}$ would be $k$-automatic. Letting
$c_{i}=p_{i}^{\nu_{p_{i}}(g_{i}(n))}\ell_{p_{i},l_{i}}(g_{i}(n))$ for
$i=1,\ldots,s$, we get

$\displaystyle\ell_{b}(f(n))$
$\displaystyle\equiv\ell_{b}\left(\frac{g_{i}(n)}{c_{i}},\ldots,\frac{g_{s}(n)}{c_{s}}\right)\ell_{b}\left(c_{1}(n-\theta)^{m_{1}},\ldots,c_{s}(n-\theta)^{m_{s}}\right)$
$\displaystyle\equiv\ell_{b}\left(c_{1}(n-\theta)^{m_{1}},\ldots,c_{s}(n-\theta)^{m_{s}}\right)\pmod{b}.$

From Proposition 7.3 we deduce that $k=b_{1}^{w_{1}}\cdots b_{s}^{w_{s}},$ for
some $w_{1},\ldots,w_{s}\in{\mathbb{N}}$ satisfying
$m_{1}w_{1}=\ldots=m_{s}w_{s}$.

By Lemma 7.5 the sequence $(\theta\\{l,k\\})_{l\geq 0}$ is eventually periodic
with period $T$. More precisely, assume that
$\theta\\{l+T,k\\}=\theta\\{l+T,k\\}$ for $l\geq L$. Now, $k$-regularity of
$(\mathcal{L}_{b}(f(n)))_{n\geq 0}$ implies $k$-regularity of
$(\mathcal{L}_{b}(f(k^{L}n+\theta[L,k])))_{n\geq 0}$, and the components of
$f(k^{L}n+\theta[L,k])$ have the same form as those of $f(n)$, namely

$f_{i}(k^{L}n+\theta[L,k])=(n-\theta\\{L,k\\})^{m_{i}}k^{Lm_{i}}g_{i}(k^{L}n+\theta[L,k])).$

Hence, without loss of generality we can assume that $L=0$. Moreover, we have
$\theta\\{l,k^{T}\\}=\theta\\{lT,k\\}$ for all $l\in{\mathbb{N}}$, and thus,
replacing $k$ with $k^{T}$, we can further assume that
$\theta\\{l,k\\}=\theta$ is constant with respect to $l$. In the sequel we
suppress $k$ in the notation and simply write $\theta[l]=\theta[l,k]$.

Renumber the primes so that $m_{1}$ is minimal among $m_{1},\ldots,m_{s}$. It
is sufficient to show that the first component of
$(\mathcal{L}_{b}(f(n)))_{n\geq 0}$, namely
$(b^{-\nu_{b}(f(n))}f_{1}(n))_{n\geq 0}$, is not a $k$-regular sequence. More
precisely, for all $l\in{\mathbb{N}}$ we define

$\beta_{l}(n)=b^{-\nu_{b}(f(k^{l}n+\theta[l]))}f_{1}(k^{l}n+\theta[l]).$

and claim that the ${\mathbb{Z}}$-submodule generated by the family
$\\{(\beta_{l}(n))_{n\geq 0}:l\in{\mathbb{N}}\\}$ is not finitely generated.

First, we compute the exponent of $b$ in the formula defining $\beta_{l}(n)$.
Writing

$f_{i}(k^{l}n+\theta[l])=k^{lm_{i}}(n-\theta)^{m_{i}}g_{i}(k^{l}n+\theta[l])$

and letting $D$ denote the common value of $m_{i}w_{i}$, we obtain

$\nu_{b_{i}}(f_{i}(k^{l}n+\theta[l]))=lD+\nu_{b_{i}}(f_{i}(n)),$

and thus also

(7.11) $\nu_{b}(f(k^{l}n+\theta[l]))=lD+\nu_{b}(f(n)).$

Now, for the sake of contradiction suppose that for some $t\in{\mathbb{N}}$
the sequences $(\beta_{l}(n))_{n\geq 0}$ with $l=0,1,\ldots,t$ generate said
${\mathbb{Z}}$-submodule. In particular there exist integers
$\alpha_{0},\alpha_{1},\ldots,\alpha_{t}$ such that for all $n\in{\mathbb{N}}$
we have

$\sum_{l=0}^{t}\alpha_{l}\beta_{l}(n)=\beta_{t+1}(n).$

Using (7.11), after some simplification we obtain

$\sum_{l=0}^{t}\alpha_{l}C^{l}g_{1}(k^{l}n+\theta[l])=C^{t+1}g_{1}(k^{t+1}n+\theta[t+1]),$

where $C=k^{m_{1}}/b^{D}$. Because ${\mathbb{N}}$ is dense in
${\mathbb{Z}}_{p_{1}}$, we can replace $n$ with $x\in{\mathbb{Z}}_{p_{1}}$. In
particular, for $x=\theta$ we obtain
$g_{1}(k^{l}\theta+\theta[l])=g_{1}(k^{t+1}\theta+\theta[t+1])=g_{1}(\theta)$,
and thus

(7.12) $\sum_{l=0}^{t}\alpha_{l}C^{l}=C^{t+1}.$

However, since not all $m_{i}$ are equal and $m_{1}$ is minimal among them,
$C$ is a rational number lying in the interval $(0,1)$. After reducing both
sides of (7.12) to the lowest terms, the denominator on the right-hand side
remains larger, thus a contradiction. ∎

We now move on to prove Theorems 2.4, 2.6, and 2.8. As in the prime power
case, we first make some preparations. Consider
$f=(f_{1},\ldots,f_{s})\in\mathcal{A}_{b}$. If some $f_{i}$ has no root in
${\mathbb{Z}}_{p_{i}}$, then Proposition 7.2 immediately implies part (a) of
each theorem. Hence, in the following considerations we assume that all the
functions $f_{i}$ have a root in ${\mathbb{Z}}_{p_{i}}$, or equivalently, the
set $\mathcal{R}_{f}$ is nonempty. For each $i=1,\ldots,s$ let
$T_{i}\in{\mathbb{N}}$ be an integer obtained from Proposition 6.8 applied to
$f_{i}$. Choose $T\in{\mathbb{N}}$ such that $T\geq T_{i}/l_{i}$ for all
$i=1,\ldots,s$, so that $b_{i}^{T}$ is a multiple of $p_{i}^{T_{i}}$. We will
focus on the subsequences $(f(b^{T}n+a))_{n\geq 0}$ with
$a=0,1,\ldots,b^{T}-1$. If there is no
$\theta=(\theta_{1},\ldots,\theta_{s})\in\mathcal{R}_{f}$ such that
$a\equiv\theta\pmod{b^{T}}$, then at least one of the functions
$f_{i}(b^{T}x+a)$ of $x\in{\mathbb{Z}}_{p_{i}}$ has no root in
${\mathbb{Z}}_{p_{i}}$. For the same reason as in the prime power case, due to
Proposition 7.2 these subsequences $(f(b^{T}n+a))_{n\geq 0}$ have no effect on
$k$-regularity of $(f(n))_{n\geq 0}$. Therefore, it remains to consider
$a=\theta[T,b]$ for $\theta\in\mathcal{R}_{f}$. To this end, we define the
functions
$f^{(\theta)}=(f^{(\theta)}_{1},\ldots,f^{(\theta)}_{s})\in\mathcal{A}_{b}$
(not to be confused with derivatives) by

$f^{(\theta)}(x)=f(b^{T}x+\theta[b,T]).$

Its components may be written in the form

(7.13)
$f^{(\theta)}_{i}(x)=\left(x-\theta\\{b,T\\}_{i}\right)^{m_{i}}q^{(\theta)}_{i}(x),$

where $\theta\\{b,T\\}_{i}=(\theta_{i}-\theta[b,T])/b^{T}$ is the only root of
$f^{(\theta)}_{i}$ in ${\mathbb{Z}}_{p_{i}}$, $m_{i}=m_{f_{i}}(\theta_{i})$ is
its multiplicity, and $q^{(\theta)}_{i}\in\mathcal{A}_{p_{i}}$. Moreover, the
choice of $T$ also guarantees that for each $i=1,\ldots,s$ the values
$\nu_{p_{i}}(q^{(\theta)}_{i}(x))$ and
$\ell_{p_{i},l_{i}d}(q^{(\theta)}_{i}(x))$ are constant with respect to
$x\in{\mathbb{Z}}_{p_{i}}$.

Also, for $i=1,\ldots,s$ put

$c^{(\theta)}_{i}=p_{i}^{\nu_{p_{i}}(q^{(\theta)}_{i}(x_{1}))}\ell_{p_{i},l_{i}d}(q^{(\theta)}_{i}(x_{s}))$

and for $x=(x_{1},\ldots,x_{s})\in{\mathbb{Z}}_{b}$ define

$\displaystyle q^{(\theta)}(x)$
$\displaystyle=\left(q^{(\theta)}_{1}(x),\ldots,q^{(\theta)}_{2}(x)\right),$
$\displaystyle h^{(\theta)}(x)$
$\displaystyle=\left(c^{(\theta)}_{1}\left(x_{1}-\theta\\{b,T\\}_{1}\right)^{m_{1}},\ldots,c^{(\theta)}_{s}\left(x_{s}-\theta\\{b,T\\}_{s}\right)^{m_{s}}\right).$

We can thus use Proposition 4.2 to obtain for all $n\in{\mathbb{N}}$ the
equalities

$\displaystyle\nu_{b}(f^{(\theta)}(n))$
$\displaystyle=\nu_{b}(h^{(\theta)}(n)),$
$\displaystyle\mathcal{L}_{b}(f^{(\theta)}(n))$
$\displaystyle=\mathcal{L}_{b}(h^{(\theta)}(n))\cdot\frac{q^{(\theta)}(n)}{(c_{1}^{(\theta)},\ldots,c_{s}^{(\theta)})},$
$\displaystyle\ell_{b,d}(f^{(\theta)}(n))$
$\displaystyle=\ell_{b,d}(h^{(\theta)}(n)).$

The results proved earlier in this section can be applied to $h^{(\theta)}$ so
by extension also to $f^{(\theta)}$.

###### Proof of Theorem 2.4.

In part (b) there exists precisely one
$\theta=(\theta,\ldots,\theta)\in\mathcal{R}_{f}$, a rational number. Let
$k=b^{w_{1}}\cdots b^{w_{s}}$, where $w_{1},\ldots,w_{s}$ are nonnegative
integers satisfying $m_{1}w_{1}=\cdots=m_{s}w_{s}$. Proposition 7.3(i) implies
$k$-regularity of the sequence $(\nu_{b}(h^{(\theta)}(n)))_{n\geq 0}$, and
therefore also of $(\nu_{b}(f(n))_{n\geq 0}$, by the above discussion.

If this sequence were not strictly $k$-regular, then its reduction modulo any
positive integer would be eventually periodic. Let $C$ be an integer as in
Lemma 6.3(ii) and suppose that $\pi$ is a period of the subsequence
$(\nu_{b}(h^{(\theta)}(n))\bmod{C})_{n\geq 0}$. However, the lemma applied to
$\rho_{i}=\theta\\{b,T\\}$ and $\sigma_{i}=\theta\\{b,T\\}-\pi$ for all
$i=1,\ldots,s$ leads to a contradiction with eventual periodicity.

Finally, under the assumption of part (c) we can find irrational
$\theta=(\theta_{1},\ldots,\theta_{s})\in\mathcal{R}_{f}$, namely such that
not all $\theta_{i}$ are equal. For any such $\theta$ the sequences
$(\nu_{b}(h^{(\theta)}(n)))_{n\geq 0}$ is not regular by Proposition 7.4(i),
and the result follows.∎

###### Proof of Theorem 2.6.

In part (b) we have $m_{1}=\cdots=m_{s}$, and $b$-regularity of the sequence
$(\mathcal{L}_{b}(h^{(\theta)}(n)))_{n\geq 0}$ follows from Proposition
7.3(ii). Since each component $(q_{i}^{(\theta)}(n)/c^{(\theta)}_{i})_{n\geq
0}$ is $k$-regular for all $k\geq 2$, the same holds for
$(q^{(\theta)}(n)/(c^{(\theta)}_{1},\ldots,c^{(\theta)}_{s}))_{n\geq 0}$.
Thus, $(\mathcal{L}_{b}(f^{(\theta)}(n)))_{n\geq 0}$ and consequently
$(\mathcal{L}_{b}(f^{(\theta)}(n)))_{n\geq 0}$ are $b$-regular.

If this sequence were not strictly $b$-regular, then the sequence
$(\ell_{b}(f(n)))_{n\geq 0}$, and thus also
$(\ell_{b,d}(h^{(\theta)}(n))_{n\geq 0}$ would be eventually periodic, but
this is ruled out by Proposition 7.2.

In part (c) the set $\mathcal{R}_{f}$ contains some irrational $\theta$ or
rational $\theta$ with varying multilplicities $m_{f_{i}}(\theta)$. In the
former case nonregularity of the sequence
$(\mathcal{L}_{b}(h^{(\theta)}(n)))_{n\geq 0}$ follows from Proposition
7.4(ii). In the latter case we apply Lemma 7.6 to the function $f^{(\theta)}$
with components written in the form (7.13). ∎

###### Proof of Theorem 2.8.

In part (b), $k$-automaticity of $(\ell_{b,d}(f(n)))_{n\geq 0}$ again follows
from Proposition 7.3(iii), while Proposition 7.2 implies that this property
holds in the strict sense.

Part (c) is a consequence of Proposition 7.4(iii). ∎

## Acknowledgements

The research is supported by the grant of the National Science Centre (NCN),
Poland, no. UMO-2019/34/E/ST1/00094.

## References

  * [1] Jean-Paul Allouche and Jeffrey Shallit, _The ring of $k$-regular sequences_, Theoret. Comput. Sci. 98 (1992), no. 2, 163–197.
  * [2] by same author, _Automatic sequences: Theory, applications, generalizations_ , Cambridge University Press, Cambridge, 2003.
  * [3] by same author, _The ring of $k$-regular sequences. II_, Theoret. Comput. Sci. 307 (2003), no. 1, 3–29.
  * [4] Jason P. Bell, _A generalization of Cobham’s theorem for regular sequences_ , Sém. Lothar. Combin. 54A (2005/07), Art. B54Ap, 15 pp.
  * [5] Sarah Blackwell, Gabriel Durham, Katherine Thompson, and Tiffany Treece, _A generalization of a method of Mordell to ternary quadratic forms_ , Int. J. Number Theory 12 (2016), no. 8, 2081–2105.
  * [6] Jhon Jairo Bravo, Maribel Díaz, and José Luis Ramírez, _The 2-adic and 3-adic valuation of the Tripell sequence and an application_ , Turkish J. Math. 44 (2020), no. 1, 131–141. MR 4059528
  * [7] Jakub Byszewski and Jakub Konieczny, _A density version of Cobham’s theorem_ , Acta Arith. 192 (2020), no. 3, 235–247.
  * [8] Alan Cobham, _On the base-dependence of sets of numbers recognizable by finite automata_ , Math. Systems Theory 3 (1969), 186–192.
  * [9] by same author, _Uniform tag sequences_ , Math. Systems Theory 6 (1972), 164–192.
  * [10] F. Michel Dekking, _Regularity and irregularity of sequences generated by automata_ , Seminar on Number Theory, 1979–1980 (French), Univ. Bordeaux I, Talence, 1980, pp. Exp. No. 9, 10.
  * [11] Jean-Marc Deshouillers, _A footnote to the least non zero digit of $n$! in base $12$_, Unif. Distrib. Theory 7 (2012), no. 1, 71–73.
  * [12] by same author, _Yet another footnote to the least non zero digit of $n!$ in base $12$_, Unif. Distrib. Theory 11 (2016), no. 2, 163–167.
  * [13] Jean-Marc Deshouillers and Florian Luca, _How often is $n!$ a sum of three squares?_, The legacy of Alladi Ramakrishnan in the mathematical sciences, Springer, New York, 2010, pp. 243–251.
  * [14] Jean-Marc Deshouillers and Imre Z. Ruzsa, _The least nonzero digit of $n!$ in base $12$_, Publ. Math. Debrecen 79 (2011), no. 3-4, 395–400.
  * [15] Gregory P. Dresden, _Two irrational numbers from the last nonzero digits of $n!$ and $n^{n}$_, Math. Mag. 74 (2001), no. 4, 316–320.
  * [16] by same author, _Three transcendental numbers from the last non-zero digits of $n^{n},\ F_{n}$, and $n!$_, Math. Mag. 81 (2008), no. 2, 96–105.
  * [17] Mikhail Ershov, _Completions of rings_ , Retrieved February 18, 2022, from https://m-ershov.github.io/7751_Fall2009/lecture26.pdf.
  * [18] by same author, _$l$ -adic integers (continued)_, Retrieved February 18, 2022, from https://m-ershov.github.io/7751_Fall2009/lecture27.pdf.
  * [19] Fernando Q. Gouvêa, _$p$ -adic numbers: An introduction_, second ed., Springer-Verlag, Berlin, 1997.
  * [20] José María Grau and Antonio M. Oller-Marcén, _On the last digit and the last non-zero digit of $n^{n}$ in base $b$_, Bull. Korean Math. Soc. 51 (2014), no. 5, 1325–1337.
  * [21] Shizuo Kakutani, _Ergodic theory of shift transformations_ , Proc. Fifth Berkeley Sympos. Math. Statist. and Probability (Berkeley, Calif., 1965/66), Vol. II: Contributions to Probability Theory, Part 2, Univ. California Press, Berkeley, Calif., 1967, pp. 405–414.
  * [22] Svetlana Katok, _$p$ -adic analysis compared with real_, Student Mathematical Library, vol. 37, American Mathematical Society, Providence, RI; Mathematics Advanced Study Semesters, University Park, PA, 2007. MR 2298943
  * [23] Yaroslav A. Latushkin and Vladimir N. Ushakov, _On the representation of Fibonacci and Lucas numbers as the sum of three squares_ , Math. Notes 91 (2012), no. 5-6, 663–670.
  * [24] Tamás Lengyel, _The order of the Fibonacci and Lucas numbers_ , Fibonacci Quart. 33 (1995), no. 3, 234–239.
  * [25] Tamás Lengyel and Diego Marques, _The 2-adic order of the Tribonacci numbers and the equation $T_{n}=m!$_, J. Integer Seq. 17 (2014), no. 10, Article 14.10.1, 8.
  * [26] by same author, _The 2-adic order of some generalized Fibonacci numbers_ , Integers 17 (2017), Paper No. A5, 10 pp.
  * [27] Eryk Lipka, _Automaticity of the sequence of the last nonzero digits of $n!$ in a fixed base_, J. Théor. Nombres Bordeaux 31 (2019), no. 1, 283–291.
  * [28] Luis A. Medina and Eric Rowland, _$p$ -regularity of the $p$-adic valuation of the Fibonacci sequence_, Fibonacci Quart. 53 (2015), no. 3, 265–271.
  * [29] Piotr Miska and Maciej Ulas, _On some properties of the number of permutations being products of pairwise disjoint $d$-cycles_, Monatsh. Math. 192 (2020), no. 1, 125–183.
  * [30] Nadir Murru and Carlo Sanna, _On the $k$-regularity of the $k$-adic valuation of Lucas sequences_, J. Théor. Nombres Bordeaux 30 (2018), no. 1, 227–237.
  * [31] Neville Robbins, _On Fibonacci and Lucas numbers which are sums of precisely four squares_ , Fibonacci Quart. 21 (1983), no. 1, 3–5.
  * [32] Alain M. Robert, _A course in $p$-adic analysis_, Graduate Texts in Mathematics, vol. 198, Springer-Verlag, New York, 2000.
  * [33] Carlo Sanna, _The $p$-adic valuation of Lucas sequences_, Fibonacci Quart. 54 (2016), no. 2, 118–124.
  * [34] Zhang Shu and Jia-Yan Yao, _Analytic functions over ${\mathbb{Z}}_{p}$ and $p$-regular sequences_, C. R. Math. Acad. Sci. Paris 349 (2011), no. 17-18, 947–952.
  * [35] Bartosz Sobolewski, _The 2-adic valuation of generalized Fibonacci sequences with an application to certain Diophantine equations_ , J. Number Theory 180 (2017), 730–742.
  * [36] by same author, _On the last nonzero digits of $n!$ in a given base_, Acta Arith. 191 (2019), no. 2, 173–189.
  * [37] by same author, _Last nonzero digits and $p$-adic valuations of special sequences_, Ph.D. thesis, Jagiellonian University in Kraków, 2021.
  * [38] Maciej Ulas and Błażej Żmija, _On $p$-adic valuations of certain $m$ colored $p$-ary partition functions_, Ramanujan J. 55 (2021), no. 2, 623–660. MR 4260165
  * [39] Paul Thomas Young, _2-adic valuations of generalized Fibonacci numbers of odd order_ , Integers 18 (2018), Paper No. A1, 13 pp.
  * [40] by same author, _$2$ -adic properties of generalized fibonacci numbers_, Integers 20 (2020), Paper No. A71, 10 pp.