素数の絡み方について

この記事は「WACUL Advent Calendar 2017」の23日目です．

こんにちは，WACULのアルバイトエンジニア @Niiboy です．
というわけで今日は数学をやっていこうと思います．

##はじめに
皆さんは素数が好きでしょうか．
この記事はかなり純粋数学的な疑問をpython使ってやってみたら意外な事実が出て来たよ！というだけのかなり数学寄りで趣味寄りの記事です．
プログラミングに関しては特に真新しいことはしていません．ご注意を．
こんな数学あるんだぐらいに思っていただければ幸いです．

この記事の概略：

1. 素数の絡まりというのを紹介．
2. どの素数がどのぐらい絡まっているのかを見る．
3. 結論．

準備：ルジャンドル記号とガウスの平方剰余の相互法則について

素数の絡まりを紹介したいのですが，その準備としてとある記号を紹介します．
$p$を4で割って1余る素数とし，$a$を整数とします．
この時平方剰余記号（又の名をルジャンドル記号）が以下で定義されます．

\left( \frac{a}{p} \right) = 
\begin{cases}
    1 & \exists x \ \text{  s. t. } x^2 \equiv a \mod p \\
    -1 & \text{(otherwise)}
  \end{cases}

要は，2乗して$p$で割ると余りが$a$になる数が存在すれば1を返し，存在しなければ-1を返しますという意味です．二乗の余りを考えるので平方剰余記号と呼ぶわけですね．

簡単な例で計算してみましょう．
例えば$2^2$ を5で割ると余りは4, $1^2$を5で割ると余りは1なので

\left( \frac{4}{5} \right) = \left( \frac{1}{5} \right) = 1,

となります．
また，$1^2=1, 2^2 = 4, 3^2 = 9, 4^2 = 16$はそれぞれ5で割ると余りが1, 4となるので，2乗すると2, 3になる数は存在しません．したがって

\left( \frac{3}{5} \right) = \left( \frac{2}{5} \right)＝-1

となります．

ルジャンドル記号に関する有名な定理を一つ紹介しておきます．
簡単のため$p$, $q$を4で割って1余る素数とします（5とか13とか17とか）．
この時以下の等式が成立します．

\left( \frac{q}{p} \right) = \left( \frac{p}{q} \right) 

これを平方剰余の相互法則と呼び，ガウスによって証明が初めて与えられました．
ガウスはこの定理が大好きで生涯で証明を7通りも与えたという逸話が残されています．
この定理の面白ポイントは「$p$で割った余りの世界」と「$q$で割った余りの世界」という一見全然関係のない二つの世界が実は相互法則により互いに関連しているという点にあります．
また，この定理を起点として数学の一大理論（類体論）が築かれていくのですが，それは割愛します．

二つの素数の絡まりについて

ここから今回の記事の主題である素数の絡まりについてご紹介します．
$p$, $q$を4で割って1余る素数とするときに

\left( \frac{q}{p} \right) = -1

なら$p$と$q$は図のように絡まって見えると定義します．

赤が$p$で青が$q$．
図はwikipediaのHopf linkより．

先ほどの計算例からすると

\left( \frac{17}{5} \right) = \left( \frac{2}{5} \right)＝-1

だったので17と5は図のように絡まっているわけですね．

なぜそう見えるのか？という話はQiitaの趣旨と少し逸れるので記事の一番下におまけ程度に載せます（興味がある人向けにふわっと書いています）．

以下は素数$p$, $q$は上記の条件を満たす時に絡まっているして話を続けます．
私は次のような素朴な疑問を抱きました．

具体的にどんな素数がどのぐらい絡まっているのか？

やっていきましょう．

絡まってる素数を探す

絡まっている紐と言えばオリンピックの記号です．

絵に描いたようなオリンピックですね．こういう絡まり方をしている素数たちを見つけていこうと思います．
まず平方剰余記号を計算する関数を作ります．

def quadratic_residue(integer, prime):
    if integer == prime:
        return 0

    integer = integer % prime
    for x in range(prime):
        if (x * x) % prime == integer:
            return 1
    return -1

あとは素数の配列を突っ込むと欲しい長さの素数列を返す関数を作りましょう．

def get_chained_pair(primes):
    """素数の集合から絡まっているペアーを配列として返す"""
    pairs = []
    for p in primes:
        for q in primes:
            if quadratic_residue(p,q) == -1:
                pairs.append([p,q])
    return pairs

def is_chained(chained_primes, p):
    """繋がってる素数列に対して素数が繋げられるかを返す"""
    for i in range(len(chained_primes)):
        # 最後の数以外で繋がっていると False
        if i != len(chained_primes) - 1:
            if quadratic_residue(chained_primes[i], p) != 1:
                return False
        # 最後の数で繋がっていると True
        else:
            if quadratic_residue(chained_primes[i],p) == -1:
                return True
            return False

def add_chaine(chained_primes, prime):
    """繋がってる素数列に対して素数が繋げられるなら繋げて配列を返す"""
    for chained_prime in chained_primes:
        if is_chained(chained_prime, prime):
            chained_prime.append(prime)
    return chained_primes

def get_linked_primes(source_primes):
    """Key:素数列の長さ， Value:素数列からなる配列として辞書を返す"""
    pairs = get_chained_pair(source_primes)
    linked_primes = {}
    
    for length in [3,4,5]:
        linked_primes[length] = []
        for p in source_primes:
            chains = add_chaine(pairs, p)
            for chain in chains:
                if len(chain) == length:
                    linked_primes[length].append(chain)
    return linked_primes

これで好きな長さの素数の列を得られます．
今回欲しかった長さ5の繋がった素数列を見てみると

source_primes = [5,13,17,29,37,41,53,149]
linked_primes = get_linked_primes(source_primes)
print(linked_primes[5])

>>> [[5, 37, 29, 41, 149], [29, 17, 5, 13, 149], [37, 5, 53, 41, 149], [149, 13, 5, 17, 29], [5, 37, 29, 41, 149], [29, 17, 5, 13, 149], [37, 5, 53, 41, 149], [149, 13, 5, 17, 29], [5, 37, 29, 41, 149], [29, 17, 5, 13, 149], [37, 5, 53, 41, 149], [149, 13, 5, 17, 29], [5, 37, 29, 41, 149], [29, 17, 5, 13, 149], [37, 5, 53, 41, 149], [149, 13, 5, 17, 29], [5, 37, 29, 41, 149], [29, 17, 5, 13, 149], [37, 5, 53, 41, 149], [149, 13, 5, 17, 29], [5, 37, 29, 41, 149], [29, 17, 5, 13, 149], [37, 5, 53, 41, 149], [149, 13, 5, 17, 29], [5, 37, 29, 41, 149], [29, 17, 5, 13, 149], [37, 5, 53, 41, 149], [149, 13, 5, 17, 29], [5, 37, 29, 41, 149], [29, 17, 5, 13, 149], [37, 5, 53, 41, 149], [149, 13, 5, 17, 29]]

となんか色々出て来ます．
$5, 37, 29, 41, 149$ はこの順番でオリンピックのように絡まっているわけですね．
出力された結果は合ってるのかテストする関数も実装しましょう．

def test(primes, length):
    c = 0
    for p in primes:
        for q in primes:
            if quadratic_residue(p,q) == -1:
                c += 1
    if c == (length - 1) * 2:
        return True
    return False

for primes in linked_primes[5]:
    print(test(primes, 5))

試してみると良い感じでした．

結論

オリンピックみたいな絡み方してる素数は結構ある．よかった．

今後の課題

オリンピックは5つの素数が次々と繋がっていたが，これ無限に繋げられる気がする．というか有限個だと直感的におかしい．
数学的に定式化して予想として述べて終わらせておきます．

###　予想
$p_1, p_2, ..., p_n, ...$ を素数列とする． 全ての$i,j$について

i \neq j, |i - j| < 2 ならば
\left( \frac{p_j}{p_i} \right) = -1　かつ \\
i \neq j , |i-j| \geq 2 ならば \left( \frac{p_j}{p_i} \right) = 1

を満たすような無限の素数列が存在するか？

もしかしたら知られてる結果かもしれないし未解決問題かもしれません．
既存の定理を使えば示せそうな気配がなんとなくしますね．

おまけ：なぜ絡まって見えるか

ふわっとした話：
結び目と素数の類似の観点から数論，低次元トポロジーを研究する数論的位相幾何学という分野があります．
非常に粗くいうと， 「素数は紐のように見え，紐は素数のように見える」という話です．今回は素数を紐のように見ました．
紐が絡まっているという話は見てすぐにわかるのですが，素数が絡まっているという話は心の目が必要です．

専門家向けの話：
あんまり数式を書いて説明するような場所でもないので言葉で説明しますが， 結び目$K$で分岐する二次被覆を構成すると，他の結び目$K'$はmod 2 の絡み数がガロア群の元として見れる．
その類似として素数$p$のみで分岐する二次エタール被覆を構成すると素数$q$に関するFrobenius自己同型がガロア群の元として見れ，これをmod 2 の絡み数と定義することができる．
この時に定義にしたがって絡み数を計算すると平方剰余記号が現れる．
という流れで上記の計算が行われました．よかったですね．

##参考文献:
Masanori Morishita, Knots and Primes -- An Introduction to Arithmetic Topology, Springer, 2011.