この記事は東京大学工学部応用物理学系2学科(物工/計数)Advent Calendar 2022の11日目のものです。
はじめに
おおよそ題名の通りですが。
今年の11月2日に、東京大学物理工学専攻准教授の渡辺悠樹先生がトポロジカル秩序相の基本的性質に関する論文をarXivに掲載されました。
この論文中に未証明のconjecture(予想)という形で数学の問題があげられており、それを解きました、というお話です。
これ私が解きました。やったぜ。
— 玻璃 (@hari64boli64) November 6, 2022
金曜の夜に迷走した挙句の長い長いぐちゃぐちゃ証明を投げたら、今日の朝にはめちゃくちゃ綺麗さっぱりになったものが返って来て、流石すぎるなぁみたいに思っていました。
数オリと競プロで培った整数論の知識が先生の研究にお役に立って良かったです。 https://t.co/I0zLzniQKz
学科同期の方などが沢山祝ってくれて嬉しかったです。ありがとうございます。
ところで、この件に関して、ありがたいことに学科同期の方で「アドカレに是非とも解説記事書いてほしい…」と仰ってくれる方がいました。
丁度、渡辺先生は物工の先生ですし、物工/計数のアドベントカレンダーにはぴったりの題材ですね。
という訳で、本記事ではこのお話をさせて頂きます。
数学が嫌いな人でも読める記事を目指したので、難しい話ばかりという訳でもありません。
楽しんで頂ければ幸いです。
論文に掲載された方の問題
まず、論文に掲載された方の問題について軽く触れます。
この論文で未証明とされていたのは、以下の命題でした。
$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つも出てきて嫌になりますね……
恐らくこれはかなり難しい問題で、自分が解けたのも相当運がよかっただけだなとは思っています。
この問題について語っても良かったのですが、先述のtweetにもある通り、渡辺先生が極めて簡潔で綺麗な証明を書いて下さったので、この問題に関しては確実にその証明をご覧いただく方が早いです。
なので、本記事ではこれに直接的には触れません。気になる方は、是非こちらからご覧ください。
(そして分かる方はこの2+1次元のトポロジカル秩序相に関する論文自体を読んでみて下さい。私には宇宙語に見えますが……)
本題
さて、そこでこの記事では何を書くか、ということですが、上記の代わりに別の問題を紹介します。
改訂前の論文には、二つの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$となります。
シンプルですね!
こんな簡単な話ではあるのですが、一つ目の問題の方では証明に際して非常に重要な道具となってきます。
一見単純な概念でも、名前や記号を与えて議論し始めると非自明な結果が出てくるというのはよくある話かと思います。
(そして、オーダーに関する議論の帰結として、最も非自明かつ著名と思われるのがLTEの補題です。数学が好きな方は是非、本記事末尾の参考文献を覗いてみて下さい)
尤も、これから紹介する二つの目の問題の方では単なる補助を果たすにとどまっています。
前提知識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}
$$
が整数になるかどうか考えていく。
$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}$の時
示すべきは、
$$
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}\
\Leftrightarrow 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}\
\Leftrightarrow \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}\
$$
である。
これは$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}
$$
が示され、題意は成立となる。
以上で証明は終了となります。お疲れ様でした。
感想など
まず思う事として、渡辺先生はやはり凄い……、ということですね。
私は物理は全く分からないのですが、ここまで純粋な整数論の問題が出てくるような研究というのは皆目見当がつきません。一体どんな研究内容なのでしょう? 説明されても私にはチンプンカンプンでしょうが……。
追記 本Advent Calendarの19日目の記事として、めいずさんという方が$\mathbb{Z}_N$ toric codeという題で、この論文にまつわる記事を書いて下さいました。(とても分かりやすい!)
物理の方に興味がある方は、是非そちらもご覧ください。(追記終わり)
とても面白い問題を二問も提供して頂いたり、論文の謝辞に名前を掲載して頂いたりと、渡辺先生には非常に感謝しています。ありがとうございます。
また、冒頭の私のtweetに関連して色々コメントなどを頂いたのですが、物工と計数の関係性に言及してるものが多く、それは確かだなぁと私は思っていました。
(例えば、以下のような話です)
本記事が参加しているadventCalendarも物工と計数が合同して行っていることからも分かる通り、物工と計数は密な関係です。
学生の立場である私からすると、この二つの学科がなぜよく一緒に扱われるのか疑問だったのですが、今回の件で、確かに、少し異なる分野の人同士が積極的に交流できるというのはかなりの強みになるのかな、と思うようになりました。
これからも計数の方は勿論、物工の方とも交流があると嬉しいですね。
ここまでお読みいただきありがとうございました。
参考文献など
参考文献とありますが、記事中では触れなかった細かな話もついでに記します。
[1] 財団法人数学オリンピック財団. 数学オリンピック事典 -問題と解法- 演習編. 朝倉書店, 2001年.
この本では素数pのオーダーを表す記号として$v_p(n)$でなく$\mathrm{ord}_p(n)$を採用しています。しかし、$\mathrm{ord}_p(n)$と書くと、他のオーダー(群の位数)と混同しやすく、どちらを採用するかは割れるところです。本記事では、論文において$v_p(n)$と表記して頂いたことに合わせ、こちらを採用しました。
[2] マスオ. "数オリの整数論（難問）に対するテクニック". 高校数学の美しい物語.
[3] じゅんにー. "LTEの補題とその応用". 2020年07月26日. Mathlog.
上記2つのサイトは$v_p(n)$の応用として紹介したLTEの補題について紹介されています。どちらも非常に素晴らしい記事です。面白い補題なので、興味のある方は是非。
[4] 雪江明彦. 代数学群論. 日本評論社, 2010年.
modの逆元に関する話で参照させて頂きました。本書では
$$
n\in\mathbb{Z}_{>0} \Rightarrow (\mathbb{Z}/n\mathbb{Z})^{\times}={\bar{m}|0<m<n,\mathrm{gcd}(m,n)=1}
$$
が証明されていますが、本記事ではその一部を使用させて頂きました。
[5] drken(株式会社NTTデータ数理システム). "「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜". 2021年01月31日. Qiita
本記事で軽く触れたmodの逆元について、より詳細に書かれた記事です。著者であるdrkenことけんちょんさんは、競技プログラミング界の泰斗ととも言える方で、いつもお世話になっています。
[6] 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.
渡辺先生の論文です。
[7] 東京大学工学部応用物理学系2学科(物工/計数)Advent Calendar 2022
最後にadventCalendarを再掲して本記事を締めさせていただきます。
どの記事も非常に素晴らしいですね!
明日はzkouさんのLaTexに関する記事です。楽しみ~