In mathematics and theoretical computer science , a k -regular sequence[ 1] k -automatic sequences to alphabets of infinite size.
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
Ruler sequence
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.[ 2] 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 }
Polynomial sequences
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.[ 3]
The n th term in a k -regular sequence grows at most polynomially in n .[ 4]
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.
Notes
^ Allouche & Shallit (1992), Theorem 4.4
^ Allouche & Shallit (1992), Theorem 2.3
^ Allouche & Shallit (1992), Theorem 2.5
^ Allouche & Shallit (1992), Theorem 2.10
References
Allouche, Jean-Paul; Shallit, Jeffrey (1992), "The ring of k -regular sequences" , Theoretical Computer Science , 98 : 163– 197, doi :10.1016/0304-3975(92)90001-v Allouche, Jean-Paul; Shallit, Jeffrey (2003), "The ring of k -regular sequences, II" , Theoretical Computer Science , 307 : 3– 29, doi :10.1016/s0304-3975(03)00090-2 Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations . Cambridge University Press . ISBN 978-0-521-82332-6 Zbl 1086.11015 . 
