とある論文の未証明予想を解きました

この記事は東京大学工学部応用物理学系2学科(物工/計数)Advent Calendar 2022の11日目のものです。

はじめに

今年の11月2日に、物理工学専攻准教授の渡辺悠樹先生がトポロジカル秩序相の基本的性質に関する論文をarXivにあげました。この論文中に未証明のconjecture(予想)という形で数学の問題があげられており、それを解きました。

acknowledgement

(論文の謝辞に名前を掲載して頂きました。一文目の内容がこの件に関する言及です。)

数学が嫌いな人でも読める記事を目指したので、難しい話ばかりという訳でもありません。楽しんで頂ければ幸いです。

論文に掲載された方の問題

まず、論文に掲載された方の問題について軽く触れます。この論文で未証明とされていたのは、以下の命題でした。

$1 \leq a_1,a_2 \leq N-1$ を満たす任意の整数 $N,a_1,a_2$ に対し、
\[r_1=\frac{a_1+b_1N}{\mathrm{gcd}(a_1+b_1N,a_2+b_2N)}, \quad d_a=\mathrm{gcd}(a_1,a_2,N)\]
とするとき、
$\exists b_1,b_2 \quad \mathrm{s.t.} \quad \mathrm{gcd}\left(\frac{r_1}{\mathrm{gcd}(r_1,\frac{N}{d_a})},d_a\right)=1$ となるか。

$\mathrm{gcd}$(最大公約数)が既に4つも出てきて嫌になりますね……

恐らくこれはかなり難しい問題で、自分が解けたのも相当運がよかっただけだなとは思っています。この問題について語っても良かったのですが、渡辺先生が極めて簡潔で綺麗な証明を書き直して下さったので、この問題に関しては確実にその証明をご覧いただく方が早いです。

なので、本記事ではこれに直接的には触れません。気になる方は、是非こちらからご覧ください。

本題

さて、そこでこの記事では何を書くか、ということですが、上記の代わりに別の問題を紹介します。

改訂前の論文には、二つのconjectureが掲載されていたのですが、その二つ目について触れます。本来この二つの内どちらかが解ければ良かったため、論文には一つ目の問題に対する証明のみ掲載されています。しかし、実は証明によって最終的に主張される内容というのは互いが互いに包含されない部分があるという、少しややこしいことになっています。

難易度の所感としては、論文に載っている問題の方が数学オリンピックの難しめの整数論、今から紹介する問題の方が(適切な誘導さえつけば、かつ、各ステップ毎に分割して見れば、)東大の入試問題くらいと言った感じで、後者の方が比較的簡単です。

ただ、その前に二つほど前提知識を記させて頂きます。

前提知識A p進付値

まず一つ目はp進付値という概念です。名前は大仰なものですが、(本記事の範囲内では)とても簡単で、「整数nが素数pで割り切れる最大の回数」という、ただそれだけを表します。

このことを素数pのオーダーと呼ぶこともあります。また、本記事ではこれを $v_p(n)$ と表記することにします。

ここで、簡単な例を見てみます。

75という整数は素数5で何回割れるでしょうか?

$75÷5=15$, $15÷5=3$ で、3は5で割り切れないので、答えは2回です。

つまり、$v_5(75)=2$ となります。

シンプルですね!

こんな簡単な話ではあるのですが、一つ目の問題の方では証明に際して非常に重要な道具となってきます。

一見単純な概念でも、名前や記号を与えて議論し始めると非自明な結果が出てくるというのはよくある話かと思います。

尤も、これから紹介する二つの目の問題の方では単なる補助を果たすにとどまっています。

前提知識B modの逆元

そして二つ目に紹介するのがmodの逆元という概念です。

これも、modさえ知っていれば非常に単純な概念で、

    mx \equiv 1 \mod{n}

を満たすような $x$ のことを、$\bmod n$ における $m$ の逆元と言います。特に、これを $m^{-1} \mod n$ と表記することにします。本当はwell-definedなど言わなければならないことは多々あるのですが、省略します。

そして実は、$m^{-1} \mod n$ は、$m$ と $n$ が互いに素ならば必ず存在するということが言えます。特に、これは必要条件でもあります。

具体例として、$\bmod 10$、つまり10で割った余りについて考えてみます。

$3^{-1}\mod{10}$ を考えてみます。すると、$3 \times 7 = 21 \equiv 1 \mod{10}$ となるので、答えは7で良さそうです。

しかし、例えば4の逆元を考えて見ると、$4 \times 1=4,4 \times 2=8,4 \times 3=12,4 \times 4=16,…$ と、10で割った余りが1になる気配はありません。

実際、お察しの通り、4と10は偶数なのに対し、1は奇数なので、4の逆元は確かに存在しないことになります。

3と10は互いに素、4と10は互いに素でないので、丁度上で述べたことと符合していることがお分かりいただけただけると思います。

それではこれを証明してみます。ここでは十分性だけ示します。

まず、一般に $0 < m < n $ が互いに素ならば、

\exists{x,y\in\mathbb{Z}} \quad \mathrm{s.t.} \quad mx+ny=1

となります。これはユークリッドの互除法の過程を逆に辿れば証明が可能です。

$x=qn+r$ とします。$q,r$ はそれぞれ商と余りです。

すると、

mr=1-n(y+mq) \equiv 1 \mod{n}

となります。よって、$m^{-1} \equiv r\mod{n}$ だと分かるので、主張が証明されました。

以上で準備は整いました。

それでは実際に問題と証明を見ていきます。やっていること自体はそこまで難しくもないのですが、ややいかつい数式が出てきたり、少し証明が長かったりするので、ちょっと難しく見えるかも知れません。

興味のない方は次節までスキップして下さい。

問題

$1 \leq a_1,a_2 \leq N-1$ を満たす任意の整数 $N,a_1,a_2$ に対し、

    \exists b_1,b_2 \quad \mathrm{s.t.} \quad \frac{\mathrm{gcd}(a_1,N)}{\mathrm{gcd}(a_1,a_2,N)}\frac{a_2+b_2N}{a_1+b_1N}\in \mathbb{Z}

となるか。

証明

(正当性には万全を期したつもりではいますが、もしも証明に誤りがありましたらご連絡下さい。)

必ず主張は成立する。以下証明を述べる。

    a_1=\prod_{i=1}^{k}{p_i^{e_{i_1}}}, \quad a_2=\left(\prod_{i=1}^{k}{p_i^{e_{i_2}}}\right) q_{a_2}

とおく。ただし、$a_1$ に関しては素因数分解となっている。$p_i$ は素数。また、$1 \leq e_{i_1} , 0 \leq e_{i_2}=v_{p_i}(a_2)$ とする。$q_{a_2}$ は素数とは限らないが $a_1$ と互いに素となる。

この時、主張が成立する十分条件は、

    \exists b_{i_1},b_{i_2}(1 \leq i \leq k) \quad \mathrm{s.t.} \quad \frac{\mathrm{gcd}(a_1,N)}{\mathrm{gcd}(a_1,a_2,N)}\left(\prod_{i=1}^{k}{\frac{p_i^{e_{i_2}}+b_{i_2}N}{p_i^{e_{i_1}}+b_{i_1}N}}\right)q_{a_2}\in \mathbb{Z}

である。理由は以下の通り。分母に関して言えば、

    \prod_{i=1}^{k}{(p_i^{e_{i_1}}+b_{i_1}N)} \equiv \prod_{i=1}^{k}{p_i^{e_{i_1}}} \equiv a_1 \mod{N}

となるので、元の $a_1+b_1N$ の形に変形が可能である。分子に関しても同様。以下では、この変形後の主張の成立を示す。

$\mathrm{gcd}$ 同士の分数となっている箇所に関しては、分母が分子の約数なので、整数であることは明らか。

よって、以下では各 $i$ について、

    \frac{p_i^{e_{i_2}}+b_{i_2}N}{p_i^{e_{i_1}}+b_{i_1}N}

がある $b_{i_1}, b_{i_2}$ に対し、整数になるかどうか考えていく。

$e_{i_2} \geq e_{i_1}$ の時は明らか。例えば $b_{i_1}=b_{i_2}=0$ などと置けば当該部分は整数となる。

以下、$e_{i_2} < e_{i_1}$ とする。

    \displaystyle\frac{\mathrm{gcd}(a_1,N)}{\mathrm{gcd}(a_1,a_2,N)}\displaystyle\frac{p_i^{e_{i_2}}+b_{i_2}N}{p_i^{e_{i_1}}+b_{i_1}N}

に関して、これが整数になることを示せばよい。(正確には、$\mathrm{gcd}$ の部分は他の $i$ と共用なので、注意が必要。)

まず、$\mathrm{gcd}$ の部分について、他に影響を与えない範囲において、則ち、素数 $p_i$ に関しては自由に数を取り出すことが出来る。

具体的には、$f=v_{p_i}(N),N=p_i^f N^\prime$ とおくと、 $p_i^{\min(e_{i_1},f)-\min(e_{i_1},e_{i_2},f)}=p_i^{\min(e_{i_1},f)-\min(e_{i_2},f)}$ が取り出せる。

特に、$N^\prime$ は $p_i$ と互いに素である。

以下、$f,e_{i_2},e_{i_1}$ の大小関係に基づき場合分けを行う。

$f \leq e_{i_2} < e_{i_1}$ の場合

示すべきは、

    \displaystyle\frac{p_i^{e_{i_2}-f}+b_{i_2}N^\prime}{p_i^{e_{i_1}-f}+b_{i_1}N^\prime}\in \mathbb{Z}

である。

これは $b_{i_1}=0$ としてよい。

分子の $\bmod {p_i^{e_{i_1}-f}}$ を考える。 $N^\prime$ が $p_i$ と互いに素のため、特に $p_i^{e_{i_1}-f}$ とも互いに素。よって、$N^\prime$ のmodの逆元が存在する。 (なお、本質的には変わらないが、$e_{i_1}-f>0$ という条件より、$p_i^{e_{i_1}-f} \neq p_i^0 = 1$ である)

よって、条件を満たす $b_{i_2}$ が求まり、

    b_{i_2} \equiv -p_i^{e_{i_2}-f} (N^\prime)^{-1} \pmod{p_i^{e_{i_1}-f}}

を満たす任意の整数とすればよい。

$e_{i_2}< f < e_{i_1}$ の場合

示すべきは、

\begin{align*}
    &p^{f-e_{i_2}}\displaystyle\frac{p_i^{e_{i_2}}+b_{i_2} p_i^f N^\prime}{p_i^{e_{i_1}}+b_{i_1} p_i^f N^\prime}\in \mathbb{Z}\\
    \iff{}& p^{f-e_{i_2}}\displaystyle\frac{p_i^{e_{i_2}}(1+b_{i_2} p_i^{f-e_{i_2}} N^\prime)}{p_i^f(p_i^{e_{i_1}-f}+b_{i_1}N^\prime)}\in \mathbb{Z}\\
    \iff{}& \displaystyle\frac{1+b_{i_2} p_i^{f-e_{i_2}} N^\prime}{p_i^{e_{i_1}-f}+b_{i_1}N^\prime}\in \mathbb{Z}
\end{align*}

である。

これは $b_{i_1}=1$ としてよい。分子の $\bmod {p_i^{e_{i_1}-f}+N^\prime}$ を考えて、それが0になるような場合が存在することを示せば十分。

その為に、$p_i^{e_{i_1}-f}+N^\prime$ と $p_i^{f-e_{i_2}}N^\prime$ が互いに素であることを示す。

    \mathrm{gcd}(p_i^{e_{i_1}-f}+N^\prime,p_i)=1 \land
    \mathrm{gcd}(p_i^{e_{i_1}-f}+N^\prime,N^\prime)=1

であれば良いが、これは、$N^\prime$ と $p_i$ が互いに素ということより共に成立する。

以上より、modの逆元が存在するため、$b_{i_2}$ は

    b_{i_2} \equiv -(p_i^{f-e_{i_2}}N^\prime)^{-1} \pmod{p_i^{e_{i_1}-f}+N^\prime}

を満たす任意の整数とすればよい。

$e_{i_2} < e_{i_1} \leq f$ の場合

示すべきは、

    p_i^{e_{i_1}-e_{i_2}}\displaystyle\frac{1+b_{i_2}p_i^{f-e_{i_2}}N^\prime}{p_i^{e_{i_1}-e_{i_2}}+b_{i_1}p_i^{f-e_{i_2}}N^\prime}\in \mathbb{Z}

であり、$b_{i_1}=b_{i_2}=0$ とおくと、

    \displaystyle\frac{p_i^{e_{i_1}-e_{i_2}}}{p_i^{e_{i_1}-e_{i_2}}}=1\\

より明らか。

以上で場合分けが尽くされた。そして、以上で特定の $i$ に関する議論が完了し、これは整数になると分かった。

これを全ての $1 \leq i\leq k$ について行う事で、

    \exists b_{i_1},b_{i_2} \quad \mathrm{s.t.} \quad \frac{\mathrm{gcd}(a_1,N)}{\mathrm{gcd}(a_1,a_2,N)}\left(\prod_{i=1}^{k}{\frac{p_i^{e_{i_2}}+b_{i_2}N}{p_i^{e_{i_1}}+b_{i_1}N}}\right)q_{a_2}\in \mathbb{Z}

が示され、主張の成立が示される。

以上で証明は終了となります。

感想など

ここまで純粋な整数論の問題が出てくるような研究があるというのが驚きでした。$\mathbb{Z}_N$ toric codeというのが対象らしいです。

とても面白い問題を二問も提供して頂いたり、論文の謝辞に名前を掲載して頂いたりと、渡辺先生には非常に感謝しています。ありがとうございます。

ここまでお読みいただきありがとうございました。

参考文献など

参考文献および、記事中では触れなかった細かな話について述べます。

[1] 財団法人数学オリンピック財団. 数学オリンピック事典 -問題と解法- 演習編. 朝倉書店, 2001年.

この本では素数pのオーダーを表す記号として $v_p(n)$ でなく $\mathrm{ord}_p(n)$ を採用しています。しかし、$\mathrm{ord}_p(n)$ と書くと、他のオーダー(群の位数)と混同しやすく、どちらを採用するかは割れるところです。本記事では、論文において $v_p(n)$ と表記して頂いたことに合わせ、こちらを採用しました。

[2] マスオ. “数オリの整数論（難問）に対するテクニック”. 高校数学の美しい物語.

https://manabitimes.jp/math/945

[3] 雪江明彦. 代数学群論. 日本評論社, 2010年.

modの逆元に関する話で参照させて頂きました。本書では

n\in\mathbb{Z}_{>0} \Rightarrow (\mathbb{Z}/n\mathbb{Z})^{\times}=\lbrace\bar{m}|0<m<n,\mathrm{gcd}(m,n)=1\rbrace

が証明されていますが、本記事ではその一部を使用させて頂きました。

[4] drken(株式会社NTTデータ数理システム). “「1000000007 で割ったあまり」の求め方を総特集！〜逆元から離散対数まで〜”. 2021年01月31日. Qiita

https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a

本記事で軽く触れたmodの逆元について、より詳細に書かれた記事です。

[5] WATANABE, Haruki; CHENG, Meng; FUJI, Yohei. Ground state degeneracy on torus in a family of $\mathbb {Z} _N $ toric code. arXiv preprint arXiv:2211.00299, 2022.

渡辺先生の論文です。

[6] 東京大学工学部応用物理学系2学科(物工/計数)Advent Calendar 2022

https://adventar.org/calendars/7701

最後にadventCalendarを再掲して本記事を締めさせていただきます。

ありがとうございました。

Hiroki Hamaguchi

はじめに

論文に掲載された方の問題

本題

前提知識A p進付値

前提知識B modの逆元

問題

証明

感想など

参考文献など