# Difference between revisions of "Ultimately periodic sequence"

(Tex done) |
m (better) |
||

Line 9: | Line 9: | ||

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]] | 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} | + | 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) | + | 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]]). |

====References==== | ====References==== |

## Latest revision as of 15:39, 24 September 2016

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).

#### References

[a1] | D. Jungnickel, "Finite fields: Structure and arithmetics" , Bibliographisches Inst. Mannheim (1993) |

**How to Cite This Entry:**

Ultimately periodic sequence.

*Encyclopedia of Mathematics.*URL: http://encyclopediaofmath.org/index.php?title=Ultimately_periodic_sequence&oldid=39286