Ultimately periodic sequence

From Encyclopedia of Mathematics
Jump to: navigation, search

A sequence $\mathbf{a} = (a_k)$ over some set $A$ satisfying the condition $$ a_{k+r} = a_k $$ for all sufficiently large values of $k$ and some $r$ is called ultimately periodic with period $r$; if this condition actually holds for all $k$, then $\mathbf{a}$ is called (purely) periodic (with period $r$). An aperiodic sequence is one which is not ultimately periodic.

The smallest number $r_0$ among all periods of $\mathbf{a}$ is called the least period of $\mathbf{a}$. The periods of $\mathbf{a}$ are precisely the multiples of $r_0$. Moreover, if $\mathbf{a}$ should be periodic for some period $r$, it is actually periodic with period $r_0$.

One may characterize the ultimately periodic sequences over some field $F$ by associating an arbitrary sequence $\mathbf{a} = (a_k)$ over $F$ with the formal power series $$ a(x) = \sum_{k=0}^\infty a_k x^k \in F[[x]] \ . $$

Then $\mathbf{a} = (a_k)$ is ultimately periodic with period $r$ if and only if $(1-x^r)a(x)$ is a polynomial over $F$. Any ultimately periodic sequence over a field is a shift register sequence. The converse is not true in general, as the Fibonacci sequence over the rationals shows (cf. Shift register sequence). However, the ultimately periodic sequences over a Galois field are precisely the shift register sequences. Periodic sequences (in particular, binary ones) with good correlation properties are important in engineering applications (cf. Correlation property for sequences).


[a1] D. Jungnickel, "Finite fields: Structure and arithmetics" , Bibliographisches Inst. Mannheim (1993)
How to Cite This Entry:
Ultimately periodic sequence. Encyclopedia of Mathematics. URL:
This article was adapted from an original article by Dieter Jungnickel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article