ランダム行列の行列積 part 3

Part1, Part2に引き続き, 有限体$\mathbb{F}_q$上の二つの独立な一様ランダムな行列$A,B\sim\mathbb{F}_q^{n\times n}$が与えられた時に積$AB$を計算せよという問題は最悪計算量 (任意の与えられた$A,B$に対して$AB$を計算する時の計算量) とほぼ一致することを見ました. 具体的にはPart1,2で以下の二つの定理を証明しました.

定理1(BLR93).

ある$T(n)$時間アルゴリズム$\mathcal{A}$が存在して$\Pr_{A,B\sim\mathbb{F}_q^{n\times n}}[\mathcal{A}(A,B)=AB]\geq 1-\epsilon$を満たすならば, ある$O(T(n))$時間乱択アルゴリズム$\mathcal{A}'$が存在して全ての$A,B\in\mathbb{F}_q^{n\times n}$に対して$\Pr[\mathcal{A}'(A,B)=AB]\geq 1-4\epsilon$を満たす. ここで確率は$\mathcal{A}'$の乱択を考える.

定理2(folklore; explicitly in [Asadi, Golonev, Gur, Shinkar, STOC22]).

ある$T(n)$時間アルゴリズム$\mathcal{A}$が存在して$\Pr_{A,B\sim\mathbb{F}_q^{n\times n}}[\mathcal{A}(A,B)=AB]\geq \alpha$を満たし, かつ$q>\lceil6/\alpha\rceil$ならば, ある$O(T(n)/\alpha^2)$時間乱択アルゴリズム$\mathcal{A}'$が存在して全ての$A,B\in\mathbb{F}_q^{n\times n}$に対して$\Pr[\mathcal{A}'(A,B)=AB]\geq 0.99$を満たす. ここで確率は$\mathcal{A}'$の乱択を考える.

これら二つの定理はそれぞれ

• 定理1では$\mathcal{A}$の成功確率は$0.75$以上でなければ意味をなさない.
• 定理2では$\mathbb{F}_q$のサイズが大きくなければならない.

という課題を抱えていました. この二つの課題は[Asadi, Golonev, Gur, Shinkar, STOC22]によって次のように解決されました:

定理3([Asadi, Golonev, Gur, Shinkar, STOC22]).

ある$T(n)$時間アルゴリズム$\mathcal{A}$が存在して$\Pr_{A,B\sim\mathbb{F}_q^{n\times n}}[\mathcal{A}(A,B)=AB]\geq \alpha$を満たすならば, ある$q^{O(\log^4(1/\alpha)}\cdot T(n)$時間乱択アルゴリズム$\mathcal{A}'$が存在して全ての$A,B\in\mathbb{F}_q^{n\times n}$に対して$\Pr[\mathcal{A}'(A,B)=AB]\geq 0.99$を満たす. ここで確率は$\mathcal{A}'$の乱択を考える.

定理3の帰着$\mathcal{A}'$の計算時間は$q$に依存しますが, $q$が大きい場合は定理2を使えば良いです.

本記事では定理3の計算時間を少し遅くした以下の定理を証明します.

定理4(weark ver of [Asadi, Golonev, Gur, Shinkar, STOC22]).

ある$T(n)$時間アルゴリズム$\mathcal{A}$が存在して$\Pr_{A,B\sim\mathbb{F}_q^{n\times n}}[\mathcal{A}(A,B)=AB]\geq \alpha$を満たすならば, ある$q^{O(\alpha^{-2})}\cdot T(n)$時間乱択アルゴリズム$\mathcal{A}'$が存在して全ての$A,B\in\mathbb{F}_q^{n\times n}$に対して$\Pr[\mathcal{A}'(A,B)=AB]\geq 0.99$を満たす. ここで確率は$\mathcal{A}'$の乱択を考える.

定理4の証明のために二つの道具を用意します. 一つは前回の記事で証明した確率的Bogolyubov--Ruzsaの補題です.

補題1 (確率的Bogolyubov--Ruzsaの補題).

集合$D\subseteq \mathbb{F}_q^n$が$|D|\geq \delta |\mathbb{F}_q^n|$を満たすならば, $\dim V\geq n-\delta^{-2}$を満たす線形部分空間$V$であって,

任意の$x\in V$に対して$\Pr_{a,b,c,d\sim \mathbb{F}_q^n}[a,b,c,d\in D|a+b-c-d=x]\geq \delta^5$

を満たすものが存在する.

もう一つの道具はランダム低ランク行列です. パラメータ$k$を受け取り以下のアルゴリズムによって生成された行列を$R_k$とします.

• $v_1,\dots,v_k\sim\mathbb{F}_q^n$を一様ランダムに生成する.
• $v_{k+1},\dots,v_n$をそれぞれ$v_1,\dots,v_k$のランダムな線形結合とする (結合の各係数が$\mathbb{F}_q$上一様ランダム).
• $v_1,\dots,v_n$を並べた行列を$R_k$として出力する.

この時, 以下が成り立ちます (証明は省略).

補題2.

$\dim(V)\geq N-k$を満たす任意の線形部分空間$V$と任意の行列$C\in\mathbb{F}_q^N$に対し, $\Pr[C+R_k\in V]\geq \frac{1}{2q^k}$.

定理4の証明.

$N=n^2$とし, 行列全体の集合$\mathbb{F}_q^{n\times n}=\mathbb{F}_q^N$を線形空間とみなします. $S=\{(A,B)\colon \mathcal{A}(A,B)=AB\}$を$\mathcal{A}$が成功する入力の集合とします. 行列$A\in\mathbb{F}_q^N$を固定し,

$$D_A = \{B\in\mathbb{F}_q^N\colon (A,B)\in S\}$$

とします. $A\sim\mathbb{F}_q^N$が一様ランダムに与えられたときの$|D_A|$の期待値は　$\geq\alpha|\mathbb{F}_q^N|$です.

最後に, $D=\{A\in\mathbb{F}_q^N\colon |D_A|\geq (\alpha/2)|\mathbb{F}_q^N|\}$とします. 直感的には, $A\in D$は$\mathcal{A}$にとって(平均的に)解きやすいインスタンスであるといえます. $A\sim\mathbb{F}_q^N$の時の確率変数$|D_A|/|\mathbb{F}_q^N|$に対して逆マルコフの不等式(Part2, 補題2参照)を適用すると$\Pr_{A\sim\mathbb{F}_q^N}[|D_A|\geq (\alpha/2)|\mathbb{F}_q^N|]\geq \alpha/2$が成り立ちます. すなわち$|D|\geq (\alpha/2)|\mathbb{F}_q^N|$となります.

ここまでで二つの集合$D,D_A$を定義しました. ここからは二段階に分けた帰着を考えます.

1. $A\in D$を満たす任意の入力$(A,B)$に対して$AB$を計算するアルゴリズム$\mathcal{A}_1$を構成する.
2. $\mathcal{A}_1$をサブルーチンとして呼び出すことで$A\not D$に対しても$AB$を計算できるアルゴリズム$\mathcal{A}_2$を構成する.

ケース1: $A\in D$.

この時は$|D_A|\geq \alpha/2$となります. $D_A$に対して補題1を適用すると, $\dim(V)\geq N-4\alpha^{-2}$を満たすある線形部分空間$V$が存在して

$$\forall x\in V,\Pr_{a,b,c\sim \mathbb{F}_q^N,d=a+b-c-x}[a,b,c,d\in D_A]\geq \alpha^5/32$$

です (ここでは$a+b-c-d=x \iff d=a+b-c-x$に注意). $a,b,c,d\in D_A$ならば$\mathcal{A}$は行列積$Aa,Ab,Ac,Ad$を正しく計算できることになるので, $Ad=Aa+Ab-Ac-Ax$に注意すると$Ax$を計算することができます.

さらに, 与えられた$B$に対して補題2より

$$\Pr[B+R_k\in V]\geq \frac{1}{2q^{4\alpha^{-2}}}$$

となります. よって$x=B+R_k$として上の議論を適用することができます.

まとめると$\mathcal{A}_1$は$B\in\mathbb{F}_q^N$を受け取って次のように計算します.

• $R_k$と$S_1,S_2,S_3\sim \mathbb{F}_q^N$をサンプリングし, $S_4=S_1+S_2-S_3-(B+R_k)$とする.
• $AR_k$を計算する ($R_k$のランクが小さくサンプリングした時に線形結合もわかっているので$O(kn^2)$時間で計算できる).
• $C=\mathcal{A}(A,S_1)+\mathcal{A}(A,S_2)-\mathcal{A}(A,S_3)-\mathcal{A}(A,S_4)-AR_k$とする. $AB=C$かどうかをFreivaldのアルゴリズムで確認し, Yesならば出力. そうでなければ最初のステップに戻る.

各繰り返しは$O(T(n))$時間で計算可能です. 最初のステップで$B+R_k\in V$かつ$S_1,S_2,S_3,S_4\in D_A$を満たせば最後のステップで$C=AB$となります. これが起こる確率は上記の解析より$q^{-O(\alpha^{-2})}$です. 従って全体の繰り返し回数を$q^{O(\alpha^{-2})}$でとれば成功確率を$0.99$にでき, この時の$\mathcal{A}_1$の計算時間は$q^{O(\alpha^{-2})}T(n)$です.

ケース2: $A\not\in D$.

ケース2もケース1とほぼ同じです. ここでは$\mathcal{A}_1$をサブルーチンとして使います. $|D|\geq \alpha/2$より, $D$に対して補題1を適用すると, $\dim(V')\geq N-4\alpha^{-2}$を満たすある線形部分空間$V'$が存在して

$$\forall x\in V',\Pr_{a,b,c\sim \mathbb{F}_q^N,d=a+b-c-x}[a,b,c,d\in D]\geq \alpha^5/32$$

です. $a,b,c,d\in D$ならば$\mathcal{A}_1$は任意の$B$に対して行列積$aB,bB,cB,dB$を正しく計算できることになるので, $dB=aB+bB-cB-xB$に注意すると$xB$を計算することができます.

さらに, 与えられた$A$に対して補題2より

$$\Pr[A+R_k\in V']\geq \frac{1}{2q^{4\alpha^{-2}}}$$

となります. よって$x=A+R_k$として上の議論を適用することができます.

まとめると$\mathcal{A}$は$A,B\in\mathbb{F}_q^N$を受け取って次のように計算します.

• $R_k$と$S'_1,S'_2,S'_3\sim \mathbb{F}_q^N$をサンプリングし, $S_4=S_1+S_2-S_3-(A+R_k)$とする.
• $R_kB$を計算する ($R_k$のランクが小さくサンプリングした時に線形結合もわかっているので$O(kn^2)$時間で計算できる).
• $C=\mathcal{A}_1(S_1,B)+\mathcal{A}_1(S_2,B)-\mathcal{A}_1(S_3,B)-\mathcal{A}(S_4,B)-R_kB$とする. $AB=C$かどうかをFreivaldのアルゴリズムで確認し, Yesならば出力. そうでなければ最初のステップに戻る.

ケース1と同じ解析により, アルゴリズム$\mathcal{A}$の計算時間は$q^{O(\alpha^{-2})}\cdot T(n)$になります. (証明終).

Bogolyubov-Ruzsaの補題 (加法的組合せ論)

加法的組合せ論(additive combinatorics)で知られるBogolyubov--Ruzsaの補題と呼ばれる結果を紹介します. この補題は様々なバリエーションが知られていますが, ここでは以下のタイプの結果を証明します. 

加法的組合せ論は極値グラフ理論(ラムゼー理論)と密接に関連しており, 密な部分集合が持つ構造的特徴を解析します. 例えばRothの定理は$\mathbb{N}$上の任意の密な部分集合$S\subseteq\mathbb{N}$は長さ3の非自明な等差数列 (つまり交差が非ゼロ) を含むことを主張します. ここでは$S$が「密な部分集合」, 「長さ3の等差数列を含む」が「構造的特徴」に対応します. なお, Rothの定理よりも強い主張として, 任意の密な自然数の部分集合は無限に長い等差数列を含むという事実が知られています (Szemerédiの定理).

$\mathbb{F}_q$を素体として$n\in\mathbb{N}$に対して線形空間$\mathbb{F}_q^n$を考えます. $D\subseteq\mathbb{F}_q^n$が密である時にそれはどのような性質を持つかを考えます. 幾つか記号を導入します.

• $D+D = \{a+a'\colon a,a'\in D\}$.
• $-D = \{-a\colon a\in D\}$.
• $k\in\mathbb{N}$に対して$kD=\{a_1+\dots+a_k\colon a_1,\dots,a_k\in D\}$.
• $D-D = D+(-D) = \{a-a'\colon a,a'\in D\}$.

例えば$D$が部分空間ならば$D+D,D-D$などは全て$D$と一致します. イメージとしては$D$と$D-D$などの"ギャップ"を考えることによって$D$の"部分空間っぽさ"を捉えることができます. Bogolyubov--Ruzsaの補題は, $D$が密ならば$2D-2D$は大きな線形部分空間を含むことを主張します.

定理1 (Bogolyubov--Ruzsaの補題).

集合$D\subseteq \mathbb{F}_q^n$が$|D|\geq \delta |\mathbb{F}_q^n|$を満たすならば, $\dim V\geq n-\delta^{-2}$を満たす線形部分空間$V$であって

任意の$x\in V$に対してある$a,b,c,d\in D$が存在して$x=a+b-c-d$

を満たすものが存在する (即ち$V\subseteq 2D-2D$).

本記事ではより強いことを主張する以下の結果を証明します.

定理2 (確率的Bogolyubov--Ruzsaの補題).

集合$D\subseteq \mathbb{F}_q^n$が$|D|\geq \delta |\mathbb{F}_q^n|$を満たすならば, $\dim V\geq n-\delta^{-2}$を満たす線形部分空間$V$であって,

任意の$x\in V$に対して$\Pr_{a,b,c,d\sim \mathbb{F}_q^n}[a,b,c,d\in D|a+b-c-d=x]\geq \delta^5$

を満たすものが存在する.

証明.

フーリエ解析の記法を用いる (定義の記事参照). $D\subseteq \mathbb{F}_q^n$に対し, $\mathbb{1}_D$を指示関数 ($x\in D$なら$\mathbb{1}_D(x)=1$, そうでなければ$\mathbb{1}_D(x)=0$) とする. この関数のフーリエ変換$\widehat{\mathbb{1}}_D$を考え, パラメータ$\epsilon>0$に対して

$$R_\epsilon = \{v\in\mathbb{F}_q^n\colon |\widehat{\mathbb{1}}_D(v)|\geq\epsilon\}$$

とする. Parsevalの等式より

$$\delta = \|\mathbb{1}_D\|^2 = \sum_{v\in\mathbb{F}_q^n}|\widehat{\mathbb{1}}_D(v)|^2 \geq \epsilon^2|R_\epsilon|$$

なので$|R_\epsilon|\leq\delta\epsilon^{-2}$である. $V$を$R$の張る部分空間の直交補空間, すなわち

$$V=\{v\in \mathbb{F}_q^n\colon \forall r\in R_{\epsilon},\langle v,r\rangle=0\}$$

とする. 明らかに$\dim V \geq n-|R_\epsilon|\geq n-\delta\epsilon^{-2}$である.

よって, $\epsilon=\delta^{1.5}$のときに上で定義された$V$が所望の性質を満たすことを言えば良い. 関数$f\colon\mathbb{F}_q^n\to\mathbb{C}$を

$$f=\mathbb{1}_D\ast \mathbb{1}_D \ast \mathbb{1}_{-D}\ast \mathbb{1}_{-D}$$

とする. 畳み込みの定義より

$$f(x) = \Pr_{a,b,c,d\sim\mathbb{F}_q^n}[a,b\in D,c,d\in -D|a+b+c+d=x]$$

であるので, 任意の$x\in V$に対して$|f(x)|\geq \delta^5$を示せばよい.

$f(x)$をフーリエ級数展開する. 畳み込みの性質から$\widehat{f}(v)=\widehat{\mathbb{1}}_D(v)^2\widehat{\mathbb{1}}_{-D}(v)^2$だが,

$$\widehat{\mathbb{1}}_{-D}(v) = \mathbf{E}_{x\sim\mathbb{F}_q^n}\left[\mathbb{1}_{-D}(x) \overline{\omega^{\langle v,x\rangle}}\right] = \mathbf{E}_{x\sim\mathbb{F}_q^n}\left[\mathbb{1}_{D}(x) \omega^{-\langle v,-x\rangle}\right] = \overline{\widehat{\mathbb{1}}_{D}(v)}$$

より, $\widehat{f}(v)=|\widehat{\mathbb{1}}_D|^4$となるので$f(x)=\sum_{v\in\mathbb{F}_q^n}|\widehat{\mathbb{1}}_D(v)|^4\chi_v(x)$である. この和を

1. $v=0$
2. $v\in R_\epsilon$
3. それ以外 ($v\not\in R_\epsilon\cup\{0\}$)

に分けて考える.

• $v=0$の時は$\chi_0\equiv 1$より$\widehat{\mathbb{1}}_D(0)\chi_0(x)=\langle \mathbb{1}_D,1\rangle = \delta$である.
• $v\in R_\epsilon$の時は, $V$の定義より$\langle x,v\rangle = 0$なので$\widehat{\mathbb{1}}_D(v)\chi_v(x)=\widehat{\mathbb{1}}_D(v)$である.

それ以外の場合は, $v\not\in R_\epsilon$より$|\widehat{\mathbb{1}}_D|\leq \epsilon$より

$$\sum_{v\not\in R_\epsilon\cup \{0\}} |\widehat{\mathbb{1}}_D(v)|^4 \leq \epsilon^2\sum_{v\not\in R_\epsilon\cup \{0\}} |\widehat{\mathbb{1}}_D(v)|^2 \leq \epsilon^2\left(\delta -  |\widehat{\mathbb{1}}_D(0)|^2\right)=\epsilon^2(\delta-\delta^2).$$

以上の三つのケース組み合わせると, $\epsilon=\delta^{1.5}$のとき,

$$|f(x)|\geq \delta + \sum_{v\in R_\epsilon}|\widehat{\mathbb{1}}_D(v)|^4 - \epsilon^2(\delta-\delta^2) \geq \delta^5$$

となり主張を得る. (証明終).

ランダム行列の行列積 part 2

前回の記事に引き続き, 独立一様ランダムな二つの行列$A,B\sim\mathbb{F}_q^{n\times n}$が与えられた時に積$AB$を計算せよという問題を考えます.

前回は[Blum, Luby, Rubinfeld, 1993]による以下の定理を証明しました. ここで有限集合$S$に対して$x\sim S$と書いた時は$x$は$S$上一様ランダムに選ばれた元と解釈してください.

定理1(BLR93).

ある$T(n)$時間アルゴリズム$\mathcal{A}$が存在して$\Pr_{A,B\sim\mathbb{F}_q^{n\times n}}[\mathcal{A}(A,B)=AB]\geq 1-\epsilon$を満たすならば, ある$O(T(n))$時間乱択アルゴリズム$\mathcal{A}'$が存在して全ての$A,B\in\mathbb{F}_q^{n\times n}$に対して$\Pr[\mathcal{A}'(A,B)=AB]\geq 1-4\epsilon$を満たす. ここで確率は$\mathcal{A}'$の乱択を考える.

この定理は$\mathcal{A}$の成功確率が$0.75$より小さい (即ち$\epsilon\geq 1/4$) と$\mathcal{A}'$の成功確率が$0$になってしまうため, $\mathcal{A}$は75%より多くのインスタンスに対して正解しなければなりませんでした. 本記事では$\mathbb{F}_q$が大きいという仮定の下でこの課題を乗り越え, 「$\mathcal{A}$の成功確率が1%でも$\mathcal{A}'$は高確率で成功する」ような$\mathcal{A}'$を構成していきます.

定理2(folklore; explicitly in [Asadi, Golonev, Gur, Shinkar, STOC22]).

ある$T(n)$時間アルゴリズム$\mathcal{A}$が存在して$\Pr_{A,B\sim\mathbb{F}_q^{n\times n}}[\mathcal{A}(A,B)=AB]\geq \alpha$を満たし, かつ$q>\lceil6/\alpha\rceil$ならば, ある$O(T(n)/\alpha^2)$時間乱択アルゴリズム$\mathcal{A}'$が存在して全ての$A,B\in\mathbb{F}_q^{n\times n}$に対して$\Pr[\mathcal{A}'(A,B)=AB]\geq 0.99$を満たす. ここで確率は$\mathcal{A}'$の乱択を考える.

定理2の証明は[Asadi, Golonev, Gur, Shinkar, STOC22]によって明示的に与えられていますが, その証明はパーマネントのランダム自己帰着の文脈などでよく知られる手法に基づいています (なおAGGSの本質的な貢献は$\mathbb{F}_q$が小さい場合に帰着を与えたという点にあります). AGGSが与えた帰着では$\mathcal{A}'$の計算時間は$O(T(n)/\alpha^4)$になっていますがここで紹介する帰着はそれより少しだけ高速で$O(T(n)/\alpha^2)$になっています.

1. 準備

定理2の証明のために幾つかの準備をします.

補題1 (Freivald's algorithm).

$A,B,C\in\mathbb{F}_q^{n\times n}$が与えられたとき, $AB=C$かどうかを判定する問題を考える. この問題を成功確率$1-\epsilon$で解く$O(n^2\log(1/\epsilon))$時間アルゴリズムが存在する.

証明.

$v\sim\mathbb{F}_q^n$を一様ランダムなベクトルとして, $ABv=Cv$かどうかをチェックします. 行列とベクトルの積なのでこれは$O(n^2)$時間でチェックできます. もし$ABv\neq Cv$ならば明らかに$AB\neq C$なのでNOと出力し, そうでなければ改めて$v\sim\mathbb{F}_q^{n\times n}$をサンプルしなおして同じことを繰り返し, 一度もNOにならなかったらYESを出力します.

このアルゴリズムは$AB=C$ならば必ずYESを出力する一方で, $AB\neq C$ならば

$$\Pr[ABv= Cv]=\Pr[(AB-C)v= 0]=\Pr[v\in \mathrm{ker}(AB-C)] \leq 1/q$$

なので各試行では確率$1-1/q\geq 1/2$でNOを出力します. 最後の不等式は$AB-C\neq 0$より$\mathrm{ker}(AB-C)$の次元は$n-1$以下であり, $|\mathrm{ker}(AB-C)|\leq |\mathbb{F}_q^n|/q$であることを使いました. (証明終).

補題2 (逆マルコフの不等式).

$X$を$[0,1]$上に値をとる確率変数とし, $\mu=\mathrm{E}[X]\in(0,1)$とすると,

$\Pr[X\geq \mu/2] \geq \mu/2.$

証明.

非負の確率変数$1-X$にマルコフの不等式を適用すると, 任意の$c\in(0,1)$に対して

$$\Pr[X\leq c] = \Pr[1-X\geq 1-c] \leq \frac{1-\mu}{1-c} = 1-\frac{\mu-c}{1-c} \leq 1-(\mu-c).$$

これに$c=\mu/2$を代入すればよい. (証明終)

系3.

$X_1,\dots,X_m$を$\{0,1\}$上に値をとる(独立とは限らない)確率変数で全ての$i\in[m]$に対し$\mathbb{E}[X_i]=\alpha$を満たすとし, $X=\sum_{i=1}^m X_i$とすると, $\Pr[X\geq m\mu/2]\geq \mu/2$.

2. 定理2の証明

与えられた行列を$A,B$とします. $R,S\sim\mathbb{F}_q^{n\times n}$を二つの独立な一様ランダムな行列とし, $f,g\colon\mathbb{F}_q\to\mathbb{F}_q^{n\times n}$を $f(t)=A+tR, g(t)=B+tS$とします. $f(t)$と$g(t)$は各成分が$\mathbb{F}_q[t]$に属する一次多項式行列とみなすことができます. このとき積$f(t)g(t)$の各成分は二次多項式になっているので, 相異なる三つの点$1\leq t_1<t_2<t_3\leq q-1$に対して$f(t_i)g(t_i)$ ($i=1,2,3$)が計算できれば多項式補間によって$f(t)g(t)$の各成分を得ることができます. そうすれば定数項$f(0)g(0)=AB$が計算できます.

各$t=1,\dots,m$ ($m\leq q-1$は後で決めるパラメータ) に対して確率変数$X_t$を, $\mathcal{A}(f(t),g(t))=f(t)g(t)$ならば$X_t=1$, そうでなければ$X_t=0$とします. 固定した$t\neq 0$に対して$f(t)$と$g(t)$はそれぞれ$\mathbb{F}_q^{n\times n}$上一様ランダムな行列なので, $\mathbf{E}[X_t]=\Pr_{R,S}[\mathcal{A}(f(t),g(t))=f(t)g(t)]=\alpha$です. よって系3より

$$\Pr[X\geq m\alpha/2]\geq \alpha/2$$

を得ます. ここで$m=\lceil6/\alpha\rceil$とすれば (ここで$q-1\geq 6/\alpha$の仮定を利用する), 確率$\alpha/2$で$X\geq 3$となり前の段落で述べた$1\leq t_1<t_2<t_3\leq m$が存在します. しかも補題1より$f(t)g(t)=\mathcal{A}(f(t),g(t))$かどうかは効率的に検証できるので$t_1,t_2,t_3$を求めることができます. 最後に求めた$t_1,t_2,t_3$及び$f(t_1)g(t_1),f(t_2)g(t_2),f(t_3)g(t_3)$を使って多項式補間すれば$f(0)g(0)$を計算できます.

まとめると次のアルゴリズムを得ました:

1. $R,S\sim\mathbb{F}_q^{n\times n}$を一様ランダムな行列とする.
2. $f(t)=A+tR,g(t)=B+tS$とし, $m=\lceil 6/\alpha \rceil$とする.
3. 各$t=1,\dots,m$に対して$C_t=\mathcal{A}(f(t),g(t))$を計算し, 補題1のアルゴリズムを使って$f(t)g(t)=C_t$かどうかをチェックし, $f(t)g(t)=C_t$となるような最初の三つの$t$を$t_1,t_2,t_3$とする. そのような$t_i$が三つとれなければステップ1に戻る.
4. $f(t_1)g(t_1), f(t_2)g(t_2), f(t_3)g(t_3)$を使って$f(t)g(t)$の各成分を多項式補間し, $f(0)g(0)$を出力する.

ステップ4に進む確率は$\alpha/2$なので, ステップ1から3を$O(\alpha^{-1})$回繰り返せば高確率で一度はステップ4に進むため, アルゴリズムは成功します. 各繰り返しではステップ3で$m$回$\mathcal{A}$を呼び出しているので, $\mathcal{A}'$の全体の計算時間は$O(T(n)/\alpha^2)$となります. (証明終).

次回のpartでは体$\mathbb{F}_q$が小さい場合に[Asadi, Golonev, Gur, Shinkar, STOC22]によって与えられた帰着を紹介します.

理論計算機科学におけるフーリエ解析 (定義)

フーリエ変換とは関数の良い基底を使って線形和で表すことを指します. 競技プログラミングの文脈などでは畳み込みのフーリエ変換と積の関係が非常に有名だと思いますが, それ以外にも様々な応用があります. 基本的にフーリエ変換と聞くと$\sin$や$\cos$が混じった積分がでてくるというイメージだと思いますが, 理論計算機科学では離散的なものを扱う都合上そういったものは(文脈によるが)登場せず, 全てが初等的に定義されるのでより親しみやすいと個人的に思います. 

本記事では定義と基本的な事実だけ紹介します. 将来的にフーリエ変換を使った証明等を書く時にこの記事を参照していきます.

$n\in\mathbb{N}$に対し$[n]=\{1,\dots,n\}$と略記します. 有限集合$S$上で一様ランダムに$x$が選ばれることを$x\sim S$で表します.

$\mathbb{F}_q$を素体とし, $\omega=\mathrm{e}^{\frac{2\pi i}{q}}$とします. 二つの関数$f,g\colon\mathbb{F}_q^n\to\mathbb{C}$に対し, その内積を

$$\langle f,g\rangle := \mathbb{E}_{x\sim\mathbb{F}_q^n}[f(x)\overline{g(x)}] = \frac{1}{|\mathbb{F}_q^n|}\sum_{x\in\mathbb{F}_q^n}f(x)\overline{g(x)} $$

とします. この内積が誘導するノルム$\|f\|=\sqrt{\langle f,f\rangle}$を考えます.

$v\in\mathbb{F}_q^n$に対し$\chi_v\colon\mathbb{F}_q^n\to\mathbb{C}$を $$\chi_v(x)=\omega^{\sum_{i=1}^n v_ix_i}$$とし, 

$$\widehat{f}(v)=\langle f,\chi_v\rangle$$

で定義される関数$\widehat{f}$を$f$のフーリエ変換といいます.

関数族$(\chi_v)_{v\in\mathbb{F}_q^n}$は基底をなしていることが知られており, 任意の関数$f\colon\mathbb{F}_q^n\to\mathbb{C}$は一意に $f=\sum_{v\in \mathbb{F}_q^n}\widehat{f}(v) \chi_v$ と表せることが知られています. このような$f$の表現を$f$のフーリエ逆変換といいます.

また, $\|f\|^2 = \sum_{v\in\mathbb{F}_q^n}|\widehat{f}(v)|^2$が成り立ちます (Parsevalの等式). これはフーリエ変換がノルムを保つ変換(ユニタリ変換)であると解釈できます.

二つの関数$f,g\colon\mathbb{F}_q^n\to\mathbb{C}$に対し, その畳み込み$f\ast g$を

$$(f\ast g)(x) = \mathbf{E}_{a\sim\mathbb{F}_q^n}[f(a)g(x-a)]$$

とします. よく知られる事実として, $\widehat{f\ast g}(v) = \widehat{f}(v) \widehat{g}(v)$が成り立ちます.

最後に, $f\colon\mathbb{F}_q^n\to\mathbb{C}$と$1\leq p\leq\infty$に対して$f$の$\ell_p$ノルムを$$\|f\|_p=\left(\mathbb{E}_{x\sim\mathbb{F}_q^n}[|f(x)|^p]\right)^{1/p}$$で定めます.

本記事では$\mathbb{F}_q^n$上の関数を対象にしていましたが, より一般にアーベル群上の関数に対して群の表現を考えることで似たような枠組みを考えることができます.

ランダム行列の行列積 part 1

 二つの行列$A,B\in\mathbb{F}_q^{n\times n}$が与えられたときにその積$AB$を計算せよという問題はこれまで多くのアルゴリズムが提案されており, 2022年4月現在では[Alman, Williams, SODA2021]による$O(n^{2.37286})$時間が(漸近的な意味で)最速のアルゴリズムとされています. 行列積は$n^2$個の値を計算する問題なので明らかに$\Omega(n^2)$時間かかるので, $2$と$2.37286$の間に限界があるというわけです.

本記事では「$A,B$が$\mathbb{F}_q^{n\times n}$上一様ランダムに与えられた時に$AB$を計算せよ」というランダム行列に対する行列積を計算する問題を考えます.

幾つかの問題ではランダムなインスタンスに対して比較的効率的に問題が解けるということが知られています. 例えばランダムグラフの文脈ではErdős–Rényiグラフ$G(n,p)$上では$O(n^{4+o(1)})$時間でハミルトン閉路を検出し見つけることができます [Bollobás, Fenner, Frieze, Combinatorica, 1987].

果たして行列積は簡単になるでしょうか？

実は答えは(ある意味で)否です. というのも, ランダムな行列の行列積を高速に計算するアルゴリズムがあればそれとほぼ同等の時間で全ての行列に対して行列を計算する乱択アルゴリズムが存在します.

本記事では以下を証明していきます.

定理1 [Blum, Luby, Rubinfeld, 1993]

ある$T(n)$時間アルゴリズム$\mathcal{A}$が存在して$\Pr_{A,B\sim\mathbb{F}_q^{n\times n}}[\mathcal{A}(A,B)=AB]\geq 1-\epsilon$を満たすならば, ある$O(T(n))$時間乱択アルゴリズム$\mathcal{A}'$が存在して全ての$A,B\in\mathbb{F}_q^{n\times n}$に対して$\Pr[\mathcal{A}'(A,B)=AB]\geq 1-4\epsilon$を満たす. ここで確率は$\mathcal{A}'$の乱択を考える.

証明.

以下で与えられるアルゴリズム$\mathcal{A}'$を考えます. 入力を$A,B$とします.

1. 一様ランダムな行列$R_1,S_1\sim \mathbb{F}_q^{n\times n}$をサンプリングし, $R_2=A-R_1,S_2=B-S_1$とする.
2. $\sum_{i,j\in\{1,2\}}\mathcal{A}(R_i,S_j)$を出力する.

このアルゴリズムは4回$\mathcal{A}$を呼び出しているので計算時間は$O(T(n))$です. さらに, $\Pr_{R_1,S_1}[\mathcal{A}'(A,B)=AB]\geq 1-4\epsilon$を満たします.

実際, $R_2,S_2$の(周辺)分布はそれぞれ$\mathbb{F}_q^{n\times n}$上一様なので, 各$i,j\in\{1,2\}$に対して$\Pr[\mathcal{A}(R_i,S_j)=R_iS_j]\geq 1-\epsilon$です. よってunion boundより$\Pr[\forall i,j\in\{1,2\},\mathcal{A}(R_i,S_j)=R_iS_j]\geq 1-4\epsilon$を得るので, この確率で出力値は

$$\sum_{i,j\in\{1,2\}}R_iS_j=(R_1+R_2)(S_1+S_2)=AB$$

を得ます. (証明終)

BLR93の定理において$\epsilon=1/4-\delta$であれば$\mathcal{A}'$の正答確率が$4\delta$になるので, $100\delta^{-1}$回繰り返せば高確率でそれらの出力の中に一つ以上の正解が含まれています. ところが行列積は乱択を使えば簡単に検証 ($A,B,C$に対して$AB=C$かどうかは$O(n^2)$時間で判定. Freivald's algorithmと呼ばれる.) できるので, 出力された$100\epsilon^{-1}$個の行列の中にある正解がどれかは分かります.

しかしながら証明の解析でunion boundをとっている都合上どうしても$\epsilon\geq 1/4$にはできません.

次回以降のpartではこの$\epsilon\geq 1/4$のケースに対しても上記の定理のような「最悪時から平均時への帰着」が存在することを示した[Asadi, Golovnev, Gur, Shinkar, STOC2022]を紹介したいと思います.