<p>We show that for all infinite sequences <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(s\in \mathbb {F}_q^\omega \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>s</mi> <mo>∈</mo> <msubsup> <mi mathvariant="double-struck">F</mi> <mi>q</mi> <mi>ω</mi> </msubsup> </mrow> </math></EquationSource> </InlineEquation>, two properties are preserved under forward and backward application of the continued fraction operator <b>K</b> (the modified Berlekamp-Massey Algorithm). The first preserved property is that if <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\({\text {supp}}(s)\subset [r]_n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>supp</mtext> <mrow> <mo stretchy="false">(</mo> <mi>s</mi> <mo stretchy="false">)</mo> </mrow> <mo>⊂</mo> <msub> <mrow> <mo stretchy="false">[</mo> <mi>r</mi> <mo stretchy="false">]</mo> </mrow> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation>, that is, the positions of the nonzero elements of <i>s</i> lie in a certain residue class modulo <i>n</i>, then also <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\({\text {supp}}(\textbf{K}(s))\subset [r]_n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>supp</mtext> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="bold">K</mi> <mrow> <mo stretchy="false">(</mo> <mi>s</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">)</mo> </mrow> <mo>⊂</mo> <msub> <mrow> <mo stretchy="false">[</mo> <mi>r</mi> <mo stretchy="false">]</mo> </mrow> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation>. The other property applies only to fields with characteristic two: if the sequence consists of symbol pairs <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\((s_{2n-1},s_{2n}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msub> <mi>s</mi> <mrow> <mn>2</mn> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>s</mi> <mrow> <mn>2</mn> <mi>n</mi> </mrow> </msub> </mrow> </math></EquationSource> </InlineEquation>) with <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(s_{2n} = \alpha s_{2n-1}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>s</mi> <mrow> <mn>2</mn> <mi>n</mi> </mrow> </msub> <mo>=</mo> <mi>α</mi> <msub> <mi>s</mi> <mrow> <mn>2</mn> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </msub> </mrow> </math></EquationSource> </InlineEquation> for a fixed <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(\alpha \in \mathbb {F}_{2^k}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>α</mi> <mo>∈</mo> <msub> <mi mathvariant="double-struck">F</mi> <msup> <mn>2</mn> <mi>k</mi> </msup> </msub> </mrow> </math></EquationSource> </InlineEquation>, for all <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(n\in \mathbb {N}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>∈</mo> <mi mathvariant="double-struck">N</mi> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(t:= \textbf{K}(s)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>t</mi> <mo>:</mo> <mo>=</mo> <mi mathvariant="bold">K</mi> <mo stretchy="false">(</mo> <mi>s</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, then also <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(t_{2n} = \alpha t_{2n-1}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>t</mi> <mrow> <mn>2</mn> <mi>n</mi> </mrow> </msub> <mo>=</mo> <mi>α</mi> <msub> <mi>t</mi> <mrow> <mn>2</mn> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </msub> </mrow> </math></EquationSource> </InlineEquation> for all <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(n\in \mathbb {N}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>∈</mo> <mi mathvariant="double-struck">N</mi> </mrow> </math></EquationSource> </InlineEquation>. We furthermore determine all sets <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(V\subset \mathbb {F}_q^m\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>V</mi> <mo>⊂</mo> <msubsup> <mi mathvariant="double-struck">F</mi> <mi>q</mi> <mi>m</mi> </msubsup> </mrow> </math></EquationSource> </InlineEquation> invariant under <b>K</b> for certain finite fields, that is, for which <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\(\textbf{K}:V^\omega \rightarrow V^\omega \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold">K</mi> <mo>:</mo> <msup> <mi>V</mi> <mi>ω</mi> </msup> <mo stretchy="false">→</mo> <msup> <mi>V</mi> <mi>ω</mi> </msup> </mrow> </math></EquationSource> </InlineEquation> and conjecture that there are no others even in the general case. In the binary case, <InlineEquation ID="IEq15"> <EquationSource Format="TEX">\(\mathbb {F}_{2^k}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="double-struck">F</mi> <msup> <mn>2</mn> <mi>k</mi> </msup> </msub> </math></EquationSource> </InlineEquation>, we apply the result to a certain binary tree associated with the isometry&#xa0;<b>K</b>.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

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

  • Mónica del P. Canales,
  • Sergio Jara C.,
  • Michael Vielhaber

摘要

We show that for all infinite sequences \(s\in \mathbb {F}_q^\omega \) s F q ω , 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\) supp ( s ) [ r ] n , 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\) supp ( K ( s ) ) [ r ] n . The other property applies only to fields with characteristic two: if the sequence consists of symbol pairs \((s_{2n-1},s_{2n}\) ( s 2 n - 1 , s 2 n ) with \(s_{2n} = \alpha s_{2n-1}\) s 2 n = α s 2 n - 1 for a fixed \(\alpha \in \mathbb {F}_{2^k}\) α F 2 k , for all \(n\in \mathbb {N}\) n N and \(t:= \textbf{K}(s)\) t : = K ( s ) , then also \(t_{2n} = \alpha t_{2n-1}\) t 2 n = α t 2 n - 1 for all \(n\in \mathbb {N}\) n N . We furthermore determine all sets \(V\subset \mathbb {F}_q^m\) V F q m invariant under K for certain finite fields, that is, for which \(\textbf{K}:V^\omega \rightarrow V^\omega \) K : V ω V ω and conjecture that there are no others even in the general case. In the binary case, \(\mathbb {F}_{2^k}\) F 2 k , we apply the result to a certain binary tree associated with the isometry K.