# Difference between revisions of "Ultimately periodic sequence"

(Importing text file) |
(Tex done) |
||

Line 1: | Line 1: | ||

− | A sequence | + | 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)f(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]]). | |

− | <table | + | ====References==== |

+ | <table> | ||

+ | <TR><TD valign="top">[a1]</TD> <TD valign="top"> D. Jungnickel, "Finite fields: Structure and arithmetics" , Bibliographisches Inst. Mannheim (1993)</TD></TR> | ||

+ | </table> | ||

− | + | {{TEX|done}} | |

− | |||

− | |||

− |

## Revision as of 15:38, 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)f(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=39284