A k -regular sequencesequence satisfying recurrence equations of a certain type, in which the n th term is a linear combination of m th terms for some integers m whose base-k representations are close to that of n .
Regular sequences generalize automatic sequences to infinite alphabets.
Definition
Let
k
≥
2
{\displaystyle k\geq 2}
s
(
n
)
n
≥
0
{\displaystyle s(n)_{n\geq 0}}
k -regular
{
s
(
k
e
n
+
r
)
n
≥
0
:
e
≥
0
and
0
≤
r
≤
k
e
−
1
}
{\displaystyle \{s(k^{e}n+r)_{n\geq 0}:e\geq 0{\text{ and }}0\leq r\leq k^{e}-1\}}
is contained in a finite-dimensional vector space over the field of rational numbers.
Examples
Let
s
(
n
)
=
ν
2
(
n
+
1
)
{\displaystyle s(n)=\nu _{2}(n+1)}
2
{\displaystyle 2}
of
n
+
1
{\displaystyle n+1}
s
(
n
)
n
≥
0
=
0
,
1
,
0
,
2
,
0
,
1
,
0
,
3
,
…
{\displaystyle s(n)_{n\geq 0}=0,1,0,2,0,1,0,3,\dots }
OEIS : A007814
2
{\displaystyle 2}
{
s
(
2
e
n
+
r
)
n
≥
0
:
e
≥
0
and
0
≤
r
≤
2
e
−
1
}
{\displaystyle \{s(2^{e}n+r)_{n\geq 0}:e\geq 0{\text{ and }}0\leq r\leq 2^{e}-1\}}
is contained in the
2
{\displaystyle 2}
s
(
n
)
n
≥
0
{\displaystyle s(n)_{n\geq 0}}
1
,
1
,
1
,
…
{\displaystyle 1,1,1,\dots }
s
(
2
n
)
=
0
s
(
4
n
+
1
)
=
s
(
2
n
+
1
)
−
s
(
n
)
s
(
4
n
+
3
)
=
2
s
(
2
n
+
1
)
−
s
(
n
)
,
{\displaystyle {\begin{aligned}s(2n)&=0\\s(4n+1)&=s(2n+1)-s(n)\\s(4n+3)&=2s(2n+1)-s(n),\end{aligned}}}
which, along with initial conditions
s
(
0
)
=
0
{\displaystyle s(0)=0}
s
(
1
)
=
1
{\displaystyle s(1)=1}
Every k -automatic sequence is k -regular.[ 1] Thue–Morse sequence
T
(
n
)
n
≥
0
=
0
,
1
,
1
,
0
,
1
,
0
,
0
,
1
,
…
{\displaystyle T(n)_{n\geq 0}=0,1,1,0,1,0,0,1,\dots }
2
{\displaystyle 2}
{
T
(
2
e
n
+
r
)
n
≥
0
:
e
≥
0
and
0
≤
r
≤
2
e
−
1
}
{\displaystyle \{T(2^{e}n+r)_{n\geq 0}:e\geq 0{\text{ and }}0\leq r\leq 2^{e}-1\}}
consists of the two sequences
T
(
n
)
n
≥
0
{\displaystyle T(n)_{n\geq 0}}
T
(
2
n
+
1
)
n
≥
0
=
1
,
0
,
0
,
1
,
0
,
1
,
1
,
0
,
…
{\displaystyle T(2n+1)_{n\geq 0}=1,0,0,1,0,1,1,0,\dots }
If
f
(
x
)
{\displaystyle f(x)}
integer-valued polynomial , then
f
(
n
)
n
≥
0
{\displaystyle f(n)_{n\geq 0}}
k -regular for every
k
≥
2
{\displaystyle k\geq 2}
Properties
The class of k -regular sequences is closed under termwise addition and multiplication.[ 2]
The n th term in a k -regular sequence grows at most polynomially in n .[ 3]
Generalizations
The notion of a k -regular sequence can be generalized to a ring
R
{\displaystyle R}
R
′
{\displaystyle R'}
Noetherian subring of
R
{\displaystyle R}
s
(
n
)
n
≥
0
{\displaystyle s(n)_{n\geq 0}}
R
{\displaystyle R}
(
R
′
,
k
)
{\displaystyle (R',k)}
R
′
{\displaystyle R'}
{
s
(
k
e
n
+
r
)
n
≥
0
:
e
≥
0
and
0
≤
r
≤
k
e
−
1
}
{\displaystyle \{s(k^{e}n+r)_{n\geq 0}:e\geq 0{\text{ and }}0\leq r\leq k^{e}-1\}}
is finitely generated.
References
^ Allouche & Shallit (1992) Theorem 2.3
^ Allouche & Shallit (1992) Theorem 2.5
^ Allouche & Shallit (1992) Theorem 2.10
Allouche, Jean-Paul; Shallit, Jeffrey (1992), "The ring of k -regular sequences" , Theoretical Computer Science , 98 : 163– 197 Allouche, Jean-Paul; Shallit, Jeffrey (2003), "The ring of k -regular sequences, II" , Theoretical Computer Science , 307 : 3– 29 Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations . Cambridge University Press . ISBN 978-0-521-82332-6 Zbl 1086.11015 . 
