Pattern sets for $$\mathbb {F}_q$$-sequences invariant under the continued fraction operator K (the Berlekamp-Massey algorithm)

Abstract We show that for all infinite sequences $$s\in \mathbb {F}_q^\omega $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>s</mml:mi> <mml:mo>∈</mml:mo> <mml:msubsup> <mml:mi>F</mml:mi> <mml:mi>q</mml:mi> <mml:mi>ω</mml:mi> </mml:msubsup> </mml:mrow> </mml:math> , two properties are preserved under forward and backward application of the continued fraction operator K (the modified Berlekamp-Massey Algorithm). The first preserved property is that if $${\text {supp}}(s)\subset [r]_n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtext>supp</mml:mtext> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>s</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>⊂</mml:mo> <mml:msub> <mml:mrow> <mml:mo>[</mml:mo> <mml:mi>r</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> </mml:math> , that is, the positions of the nonzero elements of s lie in a certain residue class modulo n , then also $${\text {supp}}(\textbf{K}(s))\subset [r]_n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtext>supp</mml:mtext> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>K</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>s</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>⊂</mml:mo> <mml:msub> <mml:mrow> <mml:mo>[</mml:mo> <mml:mi>r</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> </mml:math> . The other property applies only to fields with characteristic two: if the sequence consists of symbol pairs $$(s_{2n-1},s_{2n}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>s</mml:mi> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msub> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>s</mml:mi> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> </mml:mrow> </mml:msub> </mml:mrow> </mml:math> ) with $$s_{2n} = \alpha s_{2n-1}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>s</mml:mi> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> </mml:mrow> </mml:msub> <mml:mo>=</mml:mo> <mml:mi>α</mml:mi> <mml:msub> <mml:mi>s</mml:mi> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msub> </mml:mrow> </mml:math> for a fixed $$\alpha \in \mathbb {F}_{2^k}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>α</mml:mi> <mml:mo>∈</mml:mo> <mml:msub> <mml:mi>F</mml:mi> <mml:msup> <mml:mn>2</mml:mn> <mml:mi>k</mml:mi> </mml:msup> </mml:msub> </mml:mrow> </mml:math> , for all $$n\in \mathbb {N}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>N</mml:mi> </mml:mrow> </mml:math> and $$t:= \textbf{K}(s)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>t</mml:mi> <mml:mo>:</mml:mo> <mml:mo>=</mml:mo> <mml:mi>K</mml:mi> <mml:mo>(</mml:mo> <mml:mi>s</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , then also $$t_{2n} = \alpha t_{2n-1}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>t</mml:mi> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> </mml:mrow> </mml:msub> <mml:mo>=</mml:mo> <mml:mi>α</mml:mi> <mml:msub> <mml:mi>t</mml:mi> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</