えびちゃんの日記

えびちゃん（競プロ）の日記です。

α(m, n) のお勉強 + 定数時間 decremental neighbor query

\(\alpha(n)\) や \(\alpha(m, n)\) というのがありますね。union-find の計算量解析で出てくる？らしい、ほぼ定数？みたいな関数？だと思われていがちなやつです。

一度お勉強したつもりですが、実はなにもわかっていなかったのでまたやりました（別にリンク先は読まなくてもいいです）。かなり長いので、暇なときにちょっとずつかいつまんで読むくらいにしてくれたらうれしいです。

rsk0315.hatenablog.com

わかっていない気がしていたこと：

  • \(\alpha(n)\) とはなにか + どんな性質を持つか
  • Ackermann 関数 \(A_m(n)\) とはなにか
    • \(\alpha(n)\) と \(A_m(n)\) の関係はどんなものか
  • \(\alpha(m, n)\) とはなにか + どんな性質を持つか
  • 計算量解析の文脈で、\(\alpha(n)\) や \(\alpha(m, n)\) はどういう過程で出てくるか

それから、これらの解析を用いて decremental neighbor query を \(\langle O(n), O(1)\rangle\) (amortized) で処理できるデータ構造を作れるので、それの話も書きます。何度か別で言及したりしていますが、このデータ構造によって線形時間でオフラインで LCA を処理できます。

これらを順を追って書いていきます。特に前半はやや天下りに感じますが許してください。

\(\alpha\) の性質に関する話

Ackermann 関数の逆関数として言及されがちですが、ここでは Ackermann 関数は介さずに定義していきます*1。Ackermann 関数との関係は後で示します。

Inverse Ackermann hierarchy

まずは \(\alpha(n)\) を定義する前に、inverse Ackermann hierarchy と呼ばれるものを定義します。 これは、\(\angled{\alpha_1(n), \alpha_2(n), \dots}\) という関数の（無限）列で、各関数の定義は以下です。

  • \(\alpha_1(n) = \ceil{n/2}\) for \(n\ge 1\),
  • \(\alpha_k(1) = 0\) for \(k\gt 1\),
  • \(\alpha_k(n) = 1 + \alpha_k(\alpha_{k-1}(n))\) for \(k\gt 1, n\gt 1\).
    • \(\alpha_k(n)\) は、\(\alpha_{k-1}\) を \(n\) に適用するのを繰り返して \(1\) にするための回数。
\(n\) 1 2 3 4 5 6 7 8 9 ... 15 16 17 ...
\(\alpha_1(n)\) 1 1 2 2 3 3 4 4 5 ... 8 8 9 ...
\(\alpha_2(n)\) 0 1 2 2 3 3 3 3 4 ... 4 4 5 ...
\(\alpha_3(n)\) 0 1 2 2 3 3 3 3 3 ... 3 3 4 ...

たとえば、\(\alpha_2(n) = \ceil{\log_2(n)}\) となります。また、\(\alpha_3(n)\) は反復対数 (iterated logarithm) と呼ばれる関数で、\(\log^{\star}(n)\) と書かれます。 より一般に、\(f\) を \(n\) に適用するのを繰り返して \(1\) にするための回数を表す関数を \(f^{\star}(n)\) と書くようなので、\(\alpha_k(n) = {\alpha_{k-1}}^{\star}(n)\) と書けそうです。

二変数バージョンであるところの \(\alpha(m, n)\) がもっと下で定義されるのですが、これとは別物なので注意してください。

さて、こうして定義される \(\alpha_k(n)\) が持つ性質を挙げていきます。

Claim 1: 任意の \(k\ge 1\) に対して以下が成り立つ。

  • \(\alpha_k(2) = 1\),
  • \(\alpha_k(3) = \alpha_k(4) = 2\),
  • \(\alpha_k(5) = \alpha_k(6) = 3\).

Proof: クリックして展開（以下同様）

\(k\) に関する帰納法で示す。

\(\alpha_1(2) = 1\) は明らか。 \(\alpha_k(2) = 1\) とすると、定義から \[ \begin{aligned} \alpha_{k+1}(2) &= 1 + \alpha_{k+1}(\alpha_k(2)) \\ &= 1 + \alpha_{k+1}(1) \\ &= 1 + 0 \\ &= 1. \quad\qed \end{aligned} \]

\(\alpha_k(3)\) から \(\alpha_k(6)\) についても同様に示せる。\(\qed\)

Claim 2: 任意の \(k\ge 1\) に対し、\(n\ge 4\implies \alpha_k(n) \le n-2\)。

Proof

\( (k, n)\) に関する帰納法で示す。 \(k = 1\) のときは明らかなので、以下 \(k\ge 2\) とする。\(4\le n\le 6\) については Claim 1 より成り立つ。

\( (k, n)\) より辞書順で小さいものについては成り立つとすると、 \[ \begin{aligned} \alpha_k(n) &= 1 + \alpha_k(\alpha_{k-1}(n)) \\ &\le 1 + \alpha_k(n-2) \\ &\le 1 + ( (n-2)-2) \\ &\lt n-2. \quad\qed \end{aligned} \]

Claim 3: 任意の \( (n, k)\) について \(\alpha_{k+1}(n)\le\alpha_k(n)\) が成り立つ。

さらに、\(k\ge 2\) のとき \(\alpha_k(n)\ge 4 \iff \alpha_{k+1}\lt \alpha_k(n)\)。

Proof

\(\alpha_k(n)\le 3\) のときは Claim 1 と同様にして \(\alpha_{k+1}(n)\le \alpha_k(n)\) が示せる。

\(\alpha_k(n)\ge 4\) のとき、Claim 2 から \[ \begin{aligned} \alpha_{k+1}(n) &= 1 + \alpha_{k+1}(\alpha_k(n)) \\ &= 1 + \alpha_k(n) - 2 \\ &\lt \alpha_k(n). \quad\qed \end{aligned} \]

Note: \(\alpha_2(1) = 0 \lt 1 = \alpha_1(1)\) なので、\(k=1\) では \(\Longleftarrow\) が成り立たなさそう。

Claim 4: \(k\ge 2 \implies \alpha_k(n) = o(n)\)*2。

Proof

\(\alpha_2(n) = \ceil{\log_2(n)} = o(n)\) と \(\alpha_{k+1}(n)\le \alpha_k(n)\) から従う。\(\qed\)

Claim 5: \(k\ge 1 \implies \alpha_{k+1}(n) = o(\alpha_k(n))\)。

さらに、任意の正整数 \(r=O(1)\) に対して \(\alpha_{k+1}(n) = o({\alpha_k}^{(r)}(n))\)*3。

Proof

Claim 4 より、 \[ \begin{aligned} \alpha_{k+1}(n) &= 1 + \alpha_{k+1}(\alpha_k(n)) \\ &= o(\alpha_k(n)). \quad\qed \end{aligned} \]

\(r\) についても \[ \begin{aligned} \alpha_{k+1}(n) &= r + \alpha_{k+1}({\alpha_k}^{(r)}(n)) \\ &= o({\alpha_k}^{(r)}(n)). \quad\qed \end{aligned} \]

\(\alpha(n)\) の話

本題ひとつめです*4。

Claim 1, 3 より、任意の \(n\ge 5\) に対して \[ \alpha_1(n), \alpha_2(n), \alpha_3(n), \dots \] で定義される列は、最初は狭義単調減少し、その後 \(3, 3, 3, \dots\) となります。 たとえば、\(n = 9876!\) とすると、 \[ 3.06\times 10^{35163}, 116812, 6, 4, 3, 3, 3, \dots \] となります*5。 そこで、\(\alpha(n)\) を「何項目で \(3\) 以下になるか？」というのを返す関数として定義します。 \[ \alpha(n) \coloneqq \min\,\{k\mid \alpha_k(n)\le 3\}. \] 上記の例でいえば、\(\alpha(9876!) = 5\) となります。

いくつか値を示しておきます。

\(i\) \(\alpha(j) = i\) なる最小の \(j\)
1 1
2 7
3 9
4 17
5 65537

さて、こうして定義した \(\alpha(n)\) が持つ性質を挙げていきます。

Claim 6: 任意の定数 \(k\) に対して、\(\alpha(n) = o(\alpha_k(n))\)。

Proof

\(m = \alpha_{k+1}(n)\) とする。このとき、列 \[ \alpha_{k+1}(n), \alpha_{k+2}(n), \alpha_{k+3}(n), \dots \] を考えると、Claim 3 より \(\alpha_{k+m-2}(n) \le 3\) となる。 よって、 \[ \begin{aligned} \alpha(n) &\le k+m-2 \\ &= k+\alpha_{k+1}(n)-2 \\ &= o(\alpha_k(n)). \quad\qed \end{aligned} \]

Ackermann 関数との関係

さて、\(\alpha(n)\) を定義していくつか性質をわかったので、「union-find の計算量解析で出てくる？らしい、ほぼ定数？みたいな関数？」のようなふわっとした認識よりは成長した気がします。 それはそれとして、「Ackermann 関数の逆関数」などと呼ばれているのが妥当なのか？というのはよくわかっていません。

そこで、まず Ackermann 関数 \(A_m(n)\) を定義します。

  • \(A_0(n) = n + 1\) for \(n\ge 0\),
  • \(A_m(0) = A_{m-1}(1)\) for \(m\gt 0\),
  • \(A_m(n) = A_{m-1}(A_m(n-1))\) for \(m\gt 0, n\gt 0\).
    • \(A_m(n) = A_{m-1}^{(n+1)}(1)\) となります。

これらから、以下のことがわかります。

  • \(A_1(n) = n + 2\),
  • \(A_2(n) = 2n+3 = 2(n+3) - 3\),
  • \(A_3(n) = 2^{n+3}-3\).

+3 とか -3 とかがちょっと嫌な感じがしますが、諦めます。 さて、次のことが言えます。

Claim 7: \(m\ge 2 \implies \alpha_{m-1}(A_m(n)+3) = n+3\)。

Proof

\( (m, n)\) に関する帰納法で示す。

まず、\(m = 2\) のとき \[ \begin{aligned} \alpha_1(A_2(n)+3) &= \alpha_1( (2\cdot(n+3)-3) +3) \\ &= \alpha_1(2\cdot(n+3)) \\ &= n+3 \end{aligned} \] より成り立つ。

次に、固定した \(m\) 未満では成り立つとして、\(n = 0\) のとき \[ \begin{aligned} \alpha_{m-1}(A_m(0)+3) &= \alpha_{m-1}(A_{m-1}(1)+3) \\ &= 1 + \alpha_{m-1}(\alpha_{m-2}(A_{m-1}(1)+3)) \\ &= 1 + \alpha_{m-1}(1+3) \\ &= 1 + \alpha_{m-1}(4) \\ &= 3 \end{aligned} \] より成り立つ。Claim 1 より \(\alpha_{m-1}(4) = 2\) に注意せよ。

\( (m, n)\) より辞書順で小さいものについて成り立つとすると、 \[ \begin{aligned} \alpha_{m-1}(A_m(n)+3) &= \alpha_{m-1}(A_{m-1}(A_m(n-1))+3) \\ &= 1 + \alpha_{m-1}(\alpha_{m-2}(A_{m-1}(A_m(n-1))+3)) \\ &= 1 + \alpha_{m-1}(A_m(n-1)+3) \\ &= 1 + (n-1) + 3 \\ &= n + 3. \quad\qed \end{aligned} \]

Claim 8: \(n\ge 2\implies\alpha_{n-1}(n+3) = 3\)。

Proof

\(2\le n \le 3\) のとき、Claim 1 より \(\alpha_1(5) = \alpha_2(6) = 3\)。

\(n\gt 3\) とし、\(\alpha_1(n+3) = \ceil{(n+3)/2}\) と Claim 3 より、 \[ \begin{aligned} \alpha_{n-1}(n+3) &\le \max\,\{3, \alpha_1(n+3) - (n-3)\} \\ &= 3. \quad\qed \end{aligned} \]

Claim 9: \(\alpha(A_1(1)+3) = 1\) および \(n\ge 2\implies \alpha(A_n(n)+3) = n+1\)。

Proof

\(A_1(1) = 3\) より \(\alpha(A_1(1)+3) = 1\)。

以下 \(n\ge 2\) とする。 Claim 1, 7, 8 より、 \[ \begin{aligned} \alpha_{n-1}^{(2)}(A_n(n)+3) &= \alpha_{n-1}(n+3) = 3; \\ \alpha_{n-1}^{(3)}(A_n(n)+3) &= \alpha_{n-1}(3) = 2; \\ \alpha_{n-1}^{(4)}(A_n(n)+3) &= \alpha_{n-1}(2) = 1. \end{aligned} \] よって、定義から \(\alpha_n(A_n(n)+3) = 4\) とわかり、 \[ \begin{aligned} \alpha_{n+1}(A_n(n)+3) &= 1 + \alpha_{n+1}(\alpha_n(A_n(n)+3)) \\ &= 1 + \alpha_{n+1}(4); \\ &= 1 + 2 = 3; \\ \alpha(A_n(n)+3) &= n+1. \quad\qed \end{aligned} \]

こうして、（たかだか定数の差を厳密には示していないものの）\(\alpha(n)\) は \(f(n) = A_n(n)\) の逆関数くらいのものであることがわかりました。

\(A_m(\alpha_{m-1}(n))\) や \(A_n(\alpha_n(n))\) みたいなのについては割愛します*6。

\(\alpha(m, n)\) の話

天下り感が強い気もしますが、次のように定義します。 \[ \alpha(m, n) \coloneqq \min\,\{k\mid \alpha_k(n)\le 3 + m/n\}. \]

Claim 10: \(\alpha(m, n) \le \alpha(n)\)。

Proof

\(\alpha_k(n)\le 3 \implies \alpha_k(n)\le 3+m/n\) より従う。\(\qed\)

Claim 11: \(\alpha(n\cdot\alpha_i(n), n) \le i\)。特に、\(\alpha(n\ceil{\log_2(n)}, n) \le 2\)。

Proof

\[ \alpha_i(n)\le 3 + (n\cdot\alpha_i(n))/n) = 3 + \alpha_i(n) \] が自明に成り立つことから従う。後者は、\(i = 2\) の場合。\(\qed\)

注意書き

\(\alpha(n)\) は、\(A\) を使わずに定義する場合と \(A\) を使って定義する場合があります。 \(A\) を使う場合は \(\alpha(n) = \min\,\{k\mid A_k(1)\ge n\}\) のような感じの形で定義したりしますが、中身の右辺が \(n\) ではなく \(\log_2(n)\) とかだったり亜種があります。あるいは、\(A\) の定義自体にも亜種があります。 また、inverse Ackermann hierarchy で定義する場合も、\(\alpha_1(n)\) が \(\floor{n/2}\) だったり \(\ceil{n/2}\) だったり亜種があります。 各定義で高々定数の差はあったりはします*7。

文脈に合わせて都合よく定義して、オーダーは同じなので ok！みたいな感覚でやっちゃっていい気がします*8。

\(\alpha\) の計算量解析での話

ある程度 \(\alpha_k(n)\) や \(\alpha(n)\) と仲よしになったと思うので、ここからは計算量解析の文脈でどう出てくるかというのを書いていきます。 \(A_m(n)\) はもう御役御免です、ごめんね。

この辺は、参考文献に載せたスライドを読むとわかりやすいかもしれません。 数式の部分だけ読みたい人は数式の部分だけ探して読んでもいいかもしれません。

\(\alpha(n)\) が出てくるデータ構造

モノイドの区間積を答えるデータ構造を考えます*9。更新はないものとしてよいです。

まず、「前処理をなるべく少なく行いつつ、各クエリでは 1 回のモノイド演算で済むようにしたい」というのを考えます。

要素数が 1 のときは自明なので、2 以上とします。 中間で半分に分けて、前半は「その要素から中間までの累積モノイド積」、後半は「中間からその要素までの累積モノイド積」を求めておきます。 これにより、中間をまたぐ区間のクエリについてはそれを用いて 1 回の演算で答えられます。 中間をまたがない区間のために、再帰的に各々処理します*10。

各段でのモノイド演算の回数はたかだか \(n\) で、段数は \( (n/2)^{\star} = \log_2(n)\) なので、前処理は \(n\log_2(n)\) 回程度です。

「長さ \(n\) の配列のモノイド区間積に対し、各クエリを \(i\) 回のモノイド演算で済ませるための前処理の最小回数」を \(S_i(n)\) と書くことにすると、\(S_1(n) \le n\log_2(n)\) と書けます。

次に、このデータ構造を用いて、クエリあたり 3 回で済ませるデータ構造を考えます。

  • 配列を \(\log_2(n)\) 個ずつのブロック \(n/\log_2(n)\) 個に分ける
    • 各ブロックについて、前から・後ろからの累積モノイド積を求めておく
    • 高々 \(2n\) 回
  • ブロック全体のモノイド積を 1 要素と見たときの、区間クエリの前処理をする
    • 配列サイズが \(n/\log_2(n)\) となる
    • 高々 \(S_1(n/\log_2(n)) \le n\) 回
  • ブロック内のクエリを 3 回で済ませられるようにする。
    • 再帰的に行い、\(n/\log(n)\cdot S(\log_2(n))\) 回

再帰の段数は \(\log_2^{\star}(n)\) となり、\(S_3(n)\le 3n\log_2^{\star}(n)\) となります。

同様の手続きを繰り返し、\(S_{2k-1}(n)\le (2k-1)\cdot n\cdot f(n)\) を達成するデータ構造を用いて \(S_{2k+1}(n)\le (2k+1)\cdot n\cdot f^{\star}(n)\) を達成できます。すなわち、以下のようになります。 \[ S_{2k+1}(n) = (2k+1)\cdot n\cdot\log\overbrace{{}_{\!2}^{\star\star\,\dots\,\star}}^{k\text{ times}}(n). \] この \(\log^{\star\star\,\dots\,\star}\) の部分を定数にするには \(k\) をいくらにすればよいでしょう。というのを考えると、次のような関数が欲しくなります。 \[ \alpha(n) = \min\,\{k\mid \log\overbrace{{}_{\!2}^{\star\star\,\dots\,\star}}^{k\text{ times}}(n)\le 2\}. \] 前述の \(\alpha\) と違って \(\ceil{\;}\) をしていなかったりする関係で定数部分が違ったりしますが、同じようなものです。こうした過程で出てくるわけですね。

すなわち、\(S_{2\alpha(n)+1} \le (2\cdot\alpha(n)+1)\cdot n = O(n\cdot\alpha(n))\) となります*11。

\(\alpha(m, n)\) が出てくるデータ構造

みんな大好き union-find。

ちょっと疲れちゃったので、導出は抜きにして数式だけ書きます。 図や詳細などが必要な人は、同じくリンク先のスライドを見てください。

「頂点数 \(n\) かつランクの最大値 \(r\) の rank forest に対して操作を任意に \(m\) 回行うときの最大コスト」を \(f(m, n, r)\) と定義します。

さて、 \[ f(m, n, r) \le k\cdot m+2n\cdot g(r) \implies f(m, n, r) \le (k+1)\cdot m+2n\cdot g^{\diamond}(r) % ({\ceil{\log_2}}\circ g)^{\star}(r) \] が言えるらしいです。ここで、\(g^{\diamond} = ({\ceil{\log_2}}\circ g)^{\star}\) です。あるいは次のように書けます。 \[ g^{\diamond}(r) = \begin{cases} 0, & \text{if }r\le 1; \\ 1 + g^{\diamond}(\ceil{\log_2(g(r))}), & \text{otherwise}. \end{cases} \] \(m\) 側の項をちょっと悪くして \(n\) 側の項をめちゃよくするみたいなイメージだと思います。

自明な上界として \(f(m, n, r) \le (r-1)\cdot n\) があるらしい*12ことから、\(g_0(r) = \ceil{(r-1)/2}\) とします*13。また \(r\le\floor{\log_2(n)}\) を踏まえて「\(n\) 側の項を定数にするには？」というのを考えると、次のようになります。 \[ \alpha(n) = \min\,\{k\mid g\,\overbrace{{}_{\!0}^{\diamond\diamond\,\dots\,\diamond}}^{k\text{ times}}(\floor{\log_2(n)})\le 2\}. \] あるいは、「\(n\) 側の項を \(O(m)\) にするには？」というのを考えると、次のようになります*14。 \[ \alpha(m, n) = \min\,\{k\mid g\,\overbrace{{}_{\!0}^{\diamond\diamond\,\dots\,\diamond}}^{k\text{ times}}(\floor{\log_2(n)})\le 2+m/n\}. \] こうすれば、 \[ \begin{aligned} f(m, n, r) &\le \alpha(m, n)\cdot m+2n\cdot (2+m/n) \\ &\le \alpha(m, n)\cdot m + 4n+2m \end{aligned} \] となり、操作が \(m\) 回なので、操作 1 回あたり \(O(\alpha(m, n))\) となります*15。

こちらも前述の \(\alpha(m, n)\) とは若干違いますが、大した影響ではないでしょう。\(\alpha_k = {\alpha_{k-1}}^{\star}\) で定義したものと \(\alpha_k = {\alpha_{k-1}}^{\diamond}\) で定義したものでオーダーが変わるかは考えていません。\(\ceil{\log{}\circ}\) をつけた程度では \(\alpha\) に影響しないのではないかという気がしています。Claim 5 あたりを使うとよいかもしれません。

Decremental neighbor query

さて、後半です。えびちゃんは疲れてきました。記事を分けるべきだったかもしれません。

問題設定

  • \(A \gets \{0, 1, \dots, n-1\}\) で初期化。
  • 与えられた \(i\) に対して \(A \gets A \setminus \{i\}\) で更新。
  • 与えられた \(i\) に対して \(\min\,\{j\in A\mid j\ge i\}\) を出力。
  • 与えられた \(i\) に対して \(\max\,\{j\in A\mid j\le i\}\) を出力。
    • Note: \(i\in A\) とは限らない。

後者二つ (successors query, predecessor query) を合わせて neighbor query と呼びます。 要素が減るだけなので decremental です。初期化は任意の \(S\subseteq \{0, 1, \dots, n-1\}\) を与えてもよいです。

解法

熨斗袋先生ありがとう*16。

word size \(w \ge \log_2(n)\) で考えます。 長さ \(n/\log_2(n)\) の配列を取り、各要素は \(\log_2(n)\) bits です。 neighbor query の答えが、\(i\) を含む要素と同じ要素にあるときは、\(O(1)\)-time MSB やビット演算などを用いて定数時間でできます*17。

そうでないときのこと考えます。隣り合う要素に対して、それらの要素の bit がすべて 0 になったとき、union-find でそれらをつなぎます。 根を管理するのと同様にして、「その連結成分（区間）の最左はどこか？」「最右はどこか？」というのも管理しておきます。 その位置を union-find で求めた後は、上記同様に要素内で neighbor query が完結するので、定数時間で答えられます。

さて、union-find の計算量について考えます。 この union-find の要素数は \(n/\log(n)\) なので、\(n \ge n/\log(n)\cdot \log(n/\log(n))\) 回クエリをすると一回あたり \(\alpha(n, n/\log(n)) \le 2 = O(1)\) 時間です。 \(n\) 回操作をしたとき \(O(n)\) 時間になるので、\(n\) 回操作をする前のコストに関しては初期化のコストにでも押しつけておけばよいです。

これにより、\(\angled{O(n), O(1)}\) (amortized) で decremental neighbor query が解けたことになります。

これを使って解ける問題たち：

参考文献

そういえば、元ツイ時点でのえびちゃんは、配列で（dancing links をやるときみたいに）連結リストを持っていたので、neighbor query には答えられませんでした。

こっちは論文たちです。

  • Tarjan, Robert Endre. "Efficiency of a good but not linear set union algorithm." Journal of the ACM (JACM) 22, no. 2 (1975): 215–225.
    • union-find の計算量解析の元論文
  • Gabow, Harold N., Zvi Galil, Thomas Spencer, and Robert E. Tarjan. "Efficient algorithms for finding minimum spanning trees in undirected and directed graphs." Combinatorica 6, no. 2 (1986): 109–122.
    • \(\beta(m, n) = \min\,\{i\mid\log^{(i)}(n)\le m/n\}\) で定義される関数が出てくる

ツイート振り返りのコーナー

こんなツイートがきっかけでこの記事を書くことになったらしいです。信じられません。

そういえば、\(\arcsin\) を先に定義して、その逆関数として \(\sin\) を定義する話もあったような気がします。

これは別件ですが、これはこれで面白いです。

帰納法で詰まっていたときのツイートです。

おまけ

ここでは記事中で最初の \(\alpha_k(n)\) や \(\alpha(n)\) に関する定義を採用するものとして、Claim たちをいくつか書きます。あんまり詰めてません。

Claim 12: \(\alpha_k(n+1) - \alpha_k(n) \le 1\)。

Proof

\( (k, n)\) の帰納法で示す。

\(k = 1\) および \(\alpha_k(n)\le 3\) については成り立つ。 \( (k, n)\) 未満について成り立つとすると、 \[ \begin{aligned} \alpha_k(n+1) - \alpha_k(n) &= (1 + \alpha_k(\alpha_{k-1}(n+1))) - (1 + \alpha_k(\alpha_{k-1}(n))) \\ &= \alpha_k(\alpha_{k-1}(n+1)) - \alpha_k(\alpha_{k-1}(n)) \\ &\le \alpha_k(\alpha_{k-1}(n)+1) - \alpha_k(\alpha_{k-1}(n)). \end{aligned} \] \(\alpha_{k-1}(n) = 3\) であれば \(\alpha_k(4)-\alpha_k(3)=0\le 1\) より成り立つ。 そうでないとき、Claim 3 より \(n\lt\alpha_{k-1}(n)\) なので、帰納法の仮定より成り立つ。\(\qed\)

\(\alpha_k(n+\bullet)-\alpha_k(n)\le 1\) の \(\bullet\) の部分をもっと大きくできる？ 端数は適当だけど \(A_k(2)-A_k(1)\) かなんかそんな感じに。

Claim 13: 非負整数 \(r\) に対して \(\alpha_{k+1}(n+r)-\alpha_{k+1}(n) \le \alpha_k(n+r)-\alpha_k(n)\)。

Proof

\[ \alpha_{k+1}(n+r)-\alpha_k(n+r) \le \alpha_{k+1}(n)-\alpha_k(n) \] より、\(f_k(n) = \alpha_{k+1}(n) - \alpha_k(n)\) が \(n\) に対して単調減少であることを示す。 \[ \begin{aligned} f_k(n) &= \alpha_{k+1}(n) - \alpha_k(n) \\ &= 1 + \alpha_{k+1}(\alpha_k(n)) - \alpha_k(n). \end{aligned} \] \(m = \alpha_k(n)\) とすると、Claim 12（と \(m\) の単調性）から \[ \begin{aligned} 1 + \alpha_{k+1}(m + 1) - (m + 1) &\le 1 + 1 + \alpha_{k+1}(m) - (m + 1) \\ &= 1 + \alpha_{k+1}(m) - m \end{aligned} \] より従う。\(\qed\)

Claim 14: \(k\ge 2 \implies \alpha_k(2n)-\alpha_k(n)\le 1\)。

Proof

\(\ceil{\log_2(2n)}-\ceil{\log_2(n)} = 1\) と Claim 13 より従う。

Claim 15: \(\alpha(\alpha_k(n)) = \Theta(\alpha(n))\)。

Proof

\(n\) は十分大きいとする。

\(\alpha_{k+1}(n) - \alpha_{k+1}(\alpha_k(n)) = 1\) より、Claim 12 を繰り返し適用したりして \(\alpha_{\alpha(n)-1}(\alpha_k(n)) \le 4\) になって、\(\alpha(\alpha_{k+1}(n)) \in\{\alpha(n)-1, \alpha(n)\}\) とかになりそう。\(\qed\)

Claim 16: \(m\ge 3, n\ge 1 \implies \alpha_{m-2}(A_m(n)+3) = A_m(n-1)+3\) および \(m\ge 3 \implies \alpha_{m-2}(A_m(0)+3) = 4\)。

Proof Claim 7 と \(A_m\) の定義から \[ \begin{aligned} \alpha_{m-2}(A_m(n)+3) &= \alpha_{m-2}(A_{m-1}(A_m(n-1))+3) \\ &= A_m(n-1)+3. \end{aligned} \] また、 \[ \begin{aligned} \alpha_{m-2}(A_m(0)+3) &= \alpha_{m-2}(A_{m-1}(1)+3) \\ &= 1+3 = 4.\quad\qed \end{aligned} \]

Claim 17: \(m\ge 1, n\ge 0 \implies A_m(n) \ge n + 2\)。

Proof

\( (m, n)\) に関する帰納法で示す。

\(m = 1\) のとき定義より等号が成り立つ。

固定した \(m\) 未満で成り立つとすると、\(A_m(0) = A_{m-1}(1) \ge 1 + 2 \ge 0 + 2\) より成り立つ。

\( (m, n)\) より辞書順で小さいものについて成り立つとすると、 \[ \begin{aligned} A_m(n) &= A_{m-1}(A_m(n-1)) \\ &\ge A_m(n-1) + 2 \\ &\ge n+1 + 2 \\ &\ge n+2. \quad\qed \end{aligned} \]

Claim 2 と似ている。

Claim 18: \(m\ge 2, n\ge 1 \implies A_m(n)-2 \ge A_m(n-1)\)。

Proof

帰納法で示す。

\(m = 2\) のとき \(A_2(n)-2 = 2n+1 = A_2(n-1)\) より成り立つ。

固定した \(m\) 未満で成り立つとすると、Claim 17 より \[ \begin{aligned} A_m(n) - 2 &= A_{m-1}(A_m(n-1)) - 2 \\ &\ge (A_m(n-1)+2) - 2 \\ &= A_m(n-1). \quad\qed \end{aligned} \]

Claim 19: 固定した正整数 \(i = O(1)\) に対して、\(\alpha'_i = \alpha_i\) および \(\alpha'_{i+1} = (\alpha_i\circ\alpha'_i)^{\star}\) とし、\(\alpha'(n) = \min\,\{k\mid \alpha'_k(n)\le 3\}\) とする。このとき、\(\alpha'(n) = \Theta(\alpha(n))\)。

Proof

Note: \(i = 2\) のとき、上での \(g_0^{\diamond}\) に対応する。

\(\alpha'_m(n) \le \alpha_m(n)\) は明らか。

まず、\(\alpha'_{i+1} = (\alpha_i\circ\alpha_i)^{\star}\) なので、\(\alpha'_{i+1}(n) = \ceil{\alpha_{i+1}(n)/2}\)。

\[ \begin{aligned} \alpha_{i+2}(A_{i+3}(n)+3) &= 1 + \alpha_{i+2}(\alpha_{i+1}(A_{i+3}(n)+3)) \\ &= 1 + \alpha_{i+2}(A_{i+3}(n-1)+3) \\ &= n + \alpha_{i+2}(A_{i+3}(0)+3) = n+3 \end{aligned} \] であるが、 \[ \begin{aligned} \alpha'_{i+2}(A_{i+3}(n)+3) &= 1 + \alpha'_{i+2}( (\alpha_i\circ\alpha'_{i+1})\,(A_{i+3}(n)+3)) \\ &= 1 + \alpha'_{i+2}(\alpha_i(\alpha'_{i+1}(A_{i+3}(n)+3))) \\ &= 1 + \alpha'_{i+2}(\alpha_i(\ceil{\alpha_{i+1}(A_{i+3}(n)+3)/2})) \\ &\ge 1 + \alpha'_{i+2}(\alpha_i(2\ceil{\alpha_{i+1}(A_{i+3}(n)+3)/2})-1) \\ &\ge 1 + \alpha'_{i+2}(\alpha_i(\alpha_{i+1}(A_{i+3}(n)+3))-1) \\ &\ge 1 + \alpha'_{i+2}(\alpha_i(A_{i+3}(n-1)+3)-1) \\ &= 1 + \alpha'_{i+2}(\alpha_i(A_{i+2}(A_{i+3}(n-2))+3)-1) \\ &= 1 + \alpha'_{i+2}(A_{i+2}(A_{i+3}(n-2)-1)+3-1) \\ &\ge 1 + \alpha'_{i+2}(A_{i+2}(A_{i+3}(n-2)-2)+3) \\ &\ge 1 + \alpha'_{i+2}(A_{i+2}(A_{i+3}(n-3))+3) \\ &= 1 + \alpha'_{i+2}(A_{i+3}(n-2)+3) \\ &\ge \begin{cases} \frac{n}{2} + \alpha'_{i+2}(A_{i+3}(0)+3), & \text{if }n\equiv 0\pmod{2}; \\ \frac{n-1}{2} + \alpha'_{i+2}(A_{i+3}(1)+3), & \text{otherwise}. \end{cases} \end{aligned} \] ここで、 \[ \begin{aligned} \alpha'_{i+2}(A_{i+3}(0)+3) &\ge 1; \\ \alpha'_{i+2}(A_{i+3}(1)+3) &= 1 + \alpha'_{i+2}(\alpha_i(\ceil{\alpha_{i+1}(A_{i+3}(1)+3)/2})) \\ &= 1 + \alpha'_{i+2}(\alpha_i(\ceil{(A_{i+3}(0)+3)/2})) \\ &\ge 1 + \alpha'_{i+2}(\alpha_i(2\ceil{(A_{i+3}(0)+3)/2})-1) \\ &\ge 1 + \alpha'_{i+2}(\alpha_i(A_{i+3}(0)+3)-1) \\ &= 1 + \alpha'_{i+2}(\alpha_i(A_{i+2}(1)+3)-1) \\ &= 1 + \alpha'_{i+2}(A_{i+2}(0)+3-1) \\ &= 2 \end{aligned} \] なので、 \[ \begin{aligned} \alpha'_{i+2}(A_{i+3}(n)+3) &\ge \Floor{\frac{n+3}{2}} \\ &= \Floor{\frac{\alpha_{i+2}(A_{i+3}(n)+3)}{2}} \end{aligned} \] が言える。

同様にして、\(m\gt i+2\) についても \(\alpha'_m(A_{m+1}(n)+3) \ge \floor{\alpha_m(A_{m+1}(n))/2}\) が示せる。 これより、\(\alpha'(n) = \Theta(\alpha(n))\) も従う。\(\qed\)

もっとちゃんと見積もればもっと綺麗に示せそう。

Claim 20: \(k\ge 2\) に関して、\(\log_2(n)\) に関するいい感じの不等式が成り立つならば、その不等式の \(\log_2\) を \(\alpha_k\) に置き換えた不等式も成り立つ。

これは Claim か？

おきもち

Claim 14 の「\(\log_2\) で成り立つので Claim 13 から従う」の一般化みたいなことがしたかったです。Claim 14 の引数部分を \(A_m\) とか \(\alpha_m\) とかにしたいのかも。

このレベルの \(\alpha_k\) でもこの処理を無効化できるのだからもっと上のレベルなら当然無効でしょみたいな。

おわり

にゃんこです。つかれましたね。

*1:サンタさんとは独立にサンタさんの帽子を定義できるという例え話があります。

*2:ざっくり言って、\(o(f(n) )\) はオーダーが \(f(n)\) より真に小さいことを表す。

*3:\(f^{(r)}(n)\) は \(f\) を \(n\) に \(r\) 回適用したものを表す。\(f^{(0)}(r) = r\) と \(f^{(r)}(n) = f(f^{(r-1)}(n) )\)。\(r\) 階微分ではないです。

*4:残りの本題がどこだと思うかは読む人の主観に任せます。

*5:\(9876!\) がめちゃ大きいのに対し、すぐ \(3, 3, \dots\) が現れるなぁというのが実感できます。

*6:\(n\) が \(\alpha\) によって小さく丸められた後 \(A\) によって大きく飛ばされるので、\(n\) 自体とはそれなりに差が出てきそう。上からよしなに抑えられるとかの関係を示すのかなぁ。

*7:これを読んでいる人も定数倍を気にしない人が多いでしょうから、差なんてさらに気にしないことと思います。

*8:定数の差しかないことはちゃんと示した方がいいと思います。

*9:RMQ みたいなのだと思ってください。任意の演算で。

*10:disjoint sparse table ですね。

*11:「\(\alpha(n)\) は定数」学派の人的には、任意のモノイド積の区間クエリを、線形時間前処理・定数時間クエリ処理できるわけですね。まぁ「log は定数」学派の人はセグ木でそれができるんですけど。ちなみに、ちょっと工夫するだけで \(\angled{O(n), O(\alpha(n) )}\) にできます。

*12:trivial bound と書かれていますが、今ぼーっとしていてよくわかりません。疲れてきました。

*13:\(k=0\) として \(g(r) = g_0(r)\) とすればいい感じになるはず。

*14:スライドでは \(1+m/n\) になっていますが、\(1\) で問題ないかはあまりわかっていません。どうせ定数の差だと思うのですが。あるいは \(m\ge n\) を仮定しているかも。

*15:\(n\) に関する項は、初期化のコストにでも押しつければいいと思います。

*16:えびちゃんのツイートに対して熨斗袋先生が言ってくれたデータ構造なので思い入れが深いです。

*17:あるいは、leading zero を求める演算などがマシン語命令にあるので \(O(1)\) 時間でできるという仮定にしてもよいと思います。