Berlekamp–Massey algorithm

この記事ではBerlekamp–Massey algorithmの「気持ち」を形式的べき級数（母関数）を用いて説明します。
（日本語で詳しく説明しているサイトが見つからなかったので）
間違った説明はしていないつもりですが、（故意に）不正確な記述があるかもしれません。
連分数を使うという発想はhttp://www.math.sci.hiroshima-u.ac.jp/~m-mat/TEACH/sentan2005.pdfを参考にしました。
アルゴリズムの説明のみであり、実装については一切説明していません。

(2021/09/01追記)
この記事には誤りがあります。
元ネタとしている上述のpdfの記述は恐らく正確なのでそちらを参照してください。

すみません。 A を monic としても未知数 2n 個なので mod x^(2n)でした。あと、単に連分数展開すると、
・分母分子の次数が同じ速さで増えてしまって、deg A = n, deg B = nとなる
・誤差が無視できない
の二点が問題になるケースがあるようです。 pic.twitter.com/ruKa4Ql5JM
— 37zigen (@37zigen) 2021年8月8日

(追記終わり)

○Berlekamp–Massey algorithmとは何か
線形漸化式で与えられる数列の最初の何項かが与えられたとき、その漸化式を求めるアルゴリズム。
正確には「線形漸化式で与えられる数列の最初の2N項が与えられた時、その数列を生成するN次以下の最小の線形漸化式を求めるアルゴリズム」
（N次の漸化式なら必ず最初の2N項を一致させられることに留意）

○形式的べき級数体
多項式とは $\sum_{i=0}^n a_i x^i$ という形で書ける式のことだった。
ここで、高次の項は無限に存在してもよいような物を考える。つまり $\sum_{i=0}^\infty a_i x^i$ を考えよう。
例えば $1+x+x^2+x^3+\ldots$ というようなもの。
このようなもの全体は環をなし、「形式的べき級数環」と呼ばれる。
（環とは、足し算、引き算、掛け算の３つが自由にできるようなもののこと）
これの商体を「形式的べき級数体」という。
（体とは、加減乗除が自由にできるようなもののこと）
証明は省略するが、形式的べき級数体の元は $\sum_{i=-k}^\infty a_i x^i$ というような形で書ける。
（負ベキの項が有限個しかないべき級数として書ける）
さらに、有理関数体は形式的べき級数体に含まれる。
つまり有理式はべき級数で書ける（収束半径を気にせずに、0を中心としてローラン展開したものだと思えばよい）

○線形漸化式の母関数
・特性方程式
$g(a_{n+k},a_{n+k-1},\ldots,a_{n+1},a_n)=0$ という線形漸化式で与えられる数列を考える。
このとき、 $f(x):=g(x^k,x^{k-1},\ldots,x,1)$ をこの数列の特性方程式という。
例えばフィボナッチ数列なら $a_{n+2}-a_{n+1}-a_n=0$ なので特性方程式は $x^2-x-1$ となる。
・母関数
数列 $\{a_n\}$ に対し、形式的べき級数 $\sum_{i=0}^\infty a_i x^i$ を母関数という。
例えばフィボナッチ数列の母関数は $0+1x+1x^2+2x^3+3x^4+5x^5+\ldots$ となる。
・母関数と特性方程式
線形漸化式で与えられる数列 $\{a_n\}$ があり、母関数を $F(x)$ 、特性方程式を $f(x)$ 、 $k=\deg f(x)$ とする。
このとき、 $x^kf(1/x)F(x)$ は多項式である。
（ $x^kf(1/x)$ は $f(x)$ の「xの冪を逆順にしたもの」であり多項式。例えば、 $f(x)=x^2-x-1$ なら $x^kf(1/x)=1-x-x^2$ となる）
（ $x^kf(1/x)F(x)$ が多項式になることは $k$ 次以上の項について具体的に係数を計算すると0になることから分かる）
つまり $F(x)$ は $x^kf(1/x)$ を分母とする有理式として表すことができる。

○ここまでのまとめ
ここまでをまとめると
「線形漸化式で与えられる数列の最初の何項かが与えられたとき、その漸化式を求めよ」
という問題は
「有理式を形式的べき級数で表したものの低次の項が与えられたとき、元の有理式（特にその分母）を求めよ」
と同じであることが分かる

○ユークリッドの互除法と連分数
・連分数
連分数とは、次のような形をした分数のことである。
$a+\cfrac{1}{b+\cfrac{1}{c+\cfrac{1}{d+\dots}}}$
詳しい説明はwikipediaなどに譲るが「有理数を連分数の形で表すと、有限ステップで止まる」という重要な性質がある。
つまり、任意の有理数 $\dfrac{p}{q}$ に対して、ある整数の有限列 $\{a_i\}_{i=0}^n$ が存在して
$\dfrac{p}{q}=a_0+\cfrac{1}{a_1+\cfrac{1}{\dots+\cfrac{\dots}{a_{n-1}+\cfrac{1}{a_n}}}}$
となる。このことは連分数で表すことが本質的にユークリッドの互除法と対応していることから分かる
・ユークリッドの互除法と連分数
例えば $\dfrac{27}{10}$ を連分数の形で書くことを考えてみる。
$\cfrac{27}{10}\\ =2+\cfrac{7}{10}\\ =2+\cfrac{1}{\cfrac{10}{7}}\\ =2+\cfrac{1}{1+\cfrac{3}{7}}\\ =2+\cfrac{1}{1+\cfrac{1}{\cfrac{7}{3}}}\\ =2+\cfrac{1}{1+\cfrac{1}{2+\cfrac{1}{3}}}\\$
よく見れば分かる通り、これはユークリッドの互除法をしていることにほかならない
$27=10*2+7\\ 10=7*1+3\\ 7=3*2+1\\ 3=1*3\\$

○線形漸化式の母関数と連分数
・形式的べき級数における割り算のあまり
形式的べき級数体においても「あまりのある割り算」を適切に定める事ができるので、ユークリッドの互除法が適用できる。
形式的べき級数の世界においては「次数」とは「最低次」の事を指す。
（x=0でのローラン展開だったので、低次の項ほど影響力が強い……という「気持ち」）
例えば $x+x^2+2x^3+\ldots$ の次数は1であり、 $x^{-2}+x^{-1}+1+x+x^2+\ldots$ の次数は-2である。
割り算をする際の余りは、「割る数」よりも「余り」の次数の方が大きくなるように求める。
（次数が大きい方が影響力が弱い……という「気持ち」だったので）
例えば、 $(1-x) \div (1+x)$ は商が $1$ で余りが $-2x$ となり、
$1 \div (x+x^2)$ は商が $x^{-1}-1$ で余りが $x^2$ となる。
・形式的べき級数表示での連分数展開
フィボナッチ数列の場合を例とする。
まずは有理式の形の場合についてやってみる。
母関数は $\dfrac{x}{1-x-x^2}$ だったので
$\cfrac{x}{1-x-x^2}\\ =\cfrac{1}{\cfrac{1-x-x^2}{x}}\\ =\cfrac{1}{(x^{-1}-1)+\cfrac{-x^2}{x}}\\ =\cfrac{1}{(x^{-1}-1)+\cfrac{1}{-x^{-1}}}\\$
となる。ではこれをべき級数の形のままやってみよう
$\cfrac{x+x^2+2x^3+3x^4+5x^5+\ldots}{1}\\ =\cfrac{1}{\cfrac{1}{x+x^2+2x^3+3x^4+5x^5+\ldots}}\\ =\cfrac{1}{(x^{-1}-1)+\cfrac{-x^2-x^3-2x^4-3x^5-\ldots}{x+x^2+2x^3+3x^4+5x^5+\ldots}}\\ =\cfrac{1}{(x^{-1}-1)+\cfrac{1}{\cfrac{x+x^2+2x^3+3x^4+5x^5+\ldots}{-x^2-x^3-2x^4-3x^5-\ldots}}}\\ =\cfrac{1}{(x^{-1}-1)+\cfrac{1}{-x^{-1}}}\\$
ということで同じ結果が得られた。
つまり、「べき級数の世界で連分数の形にする」→「連分数を有理式の世界で戻す」という操作によって、有理式が得られる。

○実装について
互除法の部分を非再帰で上手く実装したものがBerlekamp–Massey algorithmである。（と理解しているが、間違っていれば指摘してください）
具体的な実装はwikipediaの英語版か、ドイツ語版を参考にするとよい。
微妙に異なる実装がなされており、自分には後者の方が理解しやすかった。
いずれにせよ、「一個前の値を保存しておいて、それを定数倍して足す」という操作が、互除法を戻す操作と対応していると理解すると分かりやすいかと思います。

メモ

yukicoderでゆるふわgolf

Berlekamp–Massey algorithm