ポートフォリオ
数学のこと
音楽のこと
ゲームのこと
プログラミングのこと
その他色々
ポートフォリオ
数学のこと
音楽のこと
ゲームのこと
プログラミングのこと
その他色々
ここでは，さとしんの勉強・研究している領域についての説明や，見つけたもの，作ったものについて説明していく．
私は格子理論，格子基底簡約について研究しています．とはいってもなんやねんそれという方もいるかもしれないので，取り敢えず表面的どころか表面にそっと触れている空気くらいの薄っぺらーい所を書いておきます．
\(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である．
これもそこそこ有名．
絶対に止まるとか，思っている人もいるらしいがそんなことはない．なぜか知らないが止まったり，あるいはどこかで強制停止させているだけで停止性は証明されていない．
BKZ基底簡約について説明する前に，一つ記号を定義しておく：
\(n\)次元格子\(L\)の基底を\(\{\mathbf{b}_1,\ldots,\mathbf{b}_n\}\)として，各\(1\le i\le n\)に対して写像\(\pi_i\)を\(\mathbb{R}\)-ベクトル空間\(\langle\mathbf{b}_1, \ldots, \mathbf{b}_{i-1}\rangle_\mathbb{R}\)の直交補空間への直交射影とする（但し，\(\pi_1=\mathrm{id}\)とする）． このとき，任意の\(1\le k\le \ell\le n\)に対して\((\ell-k+1)\)次元格子\(L_{[k, \ell]}\)を\(\{\pi_{k}(\mathbf{b}_k), \pi_k(\mathbf{b}_{k+1}),\ldots,\pi_k(\mathbf{b}_\ell)\}\)を基底として持つ格子とする．
\(n\)次元格子の基底\(\{\mathbf{b}_1,\ldots,\mathbf{b}_n\}\)がブロックサイズ\(\beta\)に対してBKZ簡約されているとは
$$\left\{\begin{aligned} &1\le ^\forall j<^\forall i\le n, |\mu_{ij}|\le\frac{1}{2}\\ &1\le {}^\forall k\le n-\beta+1\text{に対して，}\beta\text{次元格子}L_{[k, k+\beta-1]}\text{の基底}\{\pi_k(\mathbf{b}_k),\pi_k(\mathbf{b}_{k+1}),\ldots,\pi_k(\mathbf{b}_{k+\beta-1})\}\text{がHKZ簡約されている．}\end{aligned}\right.$$
の二つの条件を満足するときをいう．
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の変化を見てみよう．