Namespaces
Variants
Actions

Difference between revisions of "Ultimately periodic sequence"

From Encyclopedia of Mathematics
Jump to: navigation, search
(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}$\infty a_k x^k \in F[[x]] \ .
+
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]]).
+
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=39284
This article was adapted from an original article by Dieter Jungnickel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article