数学のこと
音楽のこと
ゲームのこと
プログラミングのこと
その他色々
数学のこと
音楽のこと
ゲームのこと
プログラミングのこと
その他色々
ここでは、さとしんの勉強・研究している領域についての説明や、見つけたもの、作ったものについて説明していく。
私は格子理論、格子基底簡約について研究しています。とはいってもなんやねんそれという方もいるかもしれないので、取り敢えず表面的どころか表面にそっと触れている空気くらいの薄っぺらーい所を書いておきます。
\(n\)次元格子とは一次独立なベクトル\(~\mathbf{b}_1,\ldots,\mathbf{b}_n\in\mathbb{R}^m\)の整数係数全体の集合
$$L = \mathcal{L}(\mathbf{b}_1, \dots, \mathbf{b}_n) := \left\{\left. \sum_{i = 1}^n x_i \mathbf{b}_i \in \mathbb{R}^m \right| x_i \in \mathbb{Z} \right\}$$
を格子という。
また、\(\{\mathbf{b}_1,\ldots,\mathbf{b}_n\}\)を基底、基底を並べて作った行列
$$\mathbf{B}:=\begin{bmatrix}\mathbf{b}_1\\ \vdots\\ \mathbf{b}_n\end{bmatrix}\in\mathbb{R}^{n\times m}$$
を基底行列と呼ぶ。
基底簡約は、恐ろしく簡単に言えばこの行列\(~\mathbf{B}\)に良い感じの行基本変形を施してできる限り各基底が短く、且つ直交に近くなるようにしましょうというお話です。
これはそこそこ有名
\(n\)次元格子の基底\(\{\mathbf{b}_1,\ldots,\mathbf{b}_n\}\)が\(\delta\)-LLL簡約基底であるとは
$$\left\{\begin{aligned}&1\le{}^\forall j<{}^\forall i\le n: |\mu_{i, j}|\le\frac{1}{2}\\ &2\le{}^\forall k\le n:\|\mathbf{b}_k^*\|^2\ge (\delta-\mu_{k, k-1}^2)\|\mathbf{b}_{k-1}^*\|^2\end{aligned}\right.$$
なるときをいう。但し、
$$\left\{\begin{align}\mathbf{b}_1^*&:=\mathbf{b}_1\\ \mathbf{b}_i^*&:=\mathbf{b}_i-\sum_{j=1}^{i-1}\mu_{i, j}\mathbf{b}_j^*\quad (2\le i\le n)\end{align}\right.$$
はGram-Schmidt直交化ベクトル（GSO-ベクトル）である。
これはちょっとマイナー。でも研究ではよく使うので書いておく。
\(n\)次元格子の基底\(\mathbf{B}:=\{\mathbf{b}_1,\ldots,\mathbf{b}_n\}\)が\(\delta\)-LLL簡約基底であるとは
$$\left\{\begin{aligned}&1\le{}^\forall j<{}^\forall i\le n: |\mu_{i, j}|\le\frac{1}{2}\\ &1\le{}^\forall k<\ell \le n: \delta\cdot\mathrm{Pot}(\mathbf{B})\le \rm{Pot}(\sigma_{\mathit{k}, \ell}(\mathbf{B}))\end{aligned}\right.$$
なるときをいう。但し、
$$\mathrm{Pot}(\mathbf{B}):=\prod_{i=1}^n \|\mathbf{b}_i^*\|^{2(n-i+1)}$$
は格子基底のpotentialである。
これもそこそこ有名。
絶対に止まるとか、思っている人もいるらしいがそんなことはない。なぜか知らないが止まったり、あるいはどこかで強制停止させているだけで停止性は証明されていない。
\(n\)次元格子の基底\(\{\mathbf{b}_1,\ldots,\mathbf{b}_n\}\)がブロックサイズ\(\beta\)に対してBKZ簡約されているとは
GSAは幾何級数仮定（Geometry Series Assumption）の略だが、ここでは簡単に言えばGram-Schmidtベクトルのノルムの対数値のことを言っている。
これは私が勝手に言ってるわけではなく、（論文とかではあまり見かけないが）そこそこ研究室での会話などでは使う言い回しである。
なんで、GSAなんてのがGram-Schmidtベクトルのノルムなんかを表すかと言えば、そもそも幾何級数仮定というのは簡約基底\(\{\mathbf{b}_1,\ldots,\mathbf{b}_n\}\)のGram-Schmidtベクトル\(\mathbf{b}_1^*,\ldots,\mathbf{b}_n^*\)について、
$$\begin{aligned} &\quad\quad \quad \ \ \!\frac{3}{4}\le{}^\exists q<1~\text{s.t.}~1\le{}^\forall i\le n,~\frac{\|\mathbf{b}_i^\star\|^2}{\|\mathbf{b}_1\|^2}\approx q^{i-1}\\ &\left(\iff \frac{3}{4}\le{}^\exists q<1~\text{s.t.}~1\le{}^\forall i\le n,~ \log\|\mathbf{b}_i^\star\|\approx(i-1)\frac{\log q}{2}+\log\|\mathbf{b}_1\|\right)\end{aligned}$$
が成立するっぽいというやつなので、それに因んでだと思われる。
ここでは幾つかのアルゴリズムにおけるGSAの変化を見てみよう。