Knightの問題

2021.04.22 お知らせ：こちらの記事につきまして、本質的な内容の誤りがありましたので修正させていただきました。元の記事の記述を赤字で残しつつ、訂正した個所を青字で記しております。以前のバージョンの記事をご覧になったことにより、誤解を与えてしまった方が居たとしたら申し訳ありません。今一度内容のご確認をいただければ幸いです。また、ご指摘いただきました、Hisayasu Nakao様には感謝申し上げます。

今日は Knightの問題を紹介します。Knightの問題は、ぱっと見はただの初等的な整数問題に見えるのですが、実は楕円曲線と関連する面白い問題です。

Knightの問題は、正の整数 $n$ が与えられたとき

$\displaystyle n = (X + Y + Z)\left(\frac{1}{X} + \frac{1}{Y} + \frac{1}{Z}\right) \tag{1}$

を満たす整数 $X, Y, Z$ を求めよという問題です。

たとえば、 $n = 11$ としたとき

$\displaystyle 11 = (2 + 3 + 6)\left(\frac{1}{2} + \frac{1}{3} + \frac{1}{6}\right)$

が成り立ちますから、 $(X, Y, Z) = (2, 3, 6)$ が解になります。

もし、解 $(X, Y, Z)$ が見つかったとすると、0 でない数 $k$ をかけて $(kX, kY, kZ)$ としても

$\displaystyle \begin{align} &(kX + kY + kZ)\left(\frac{1}{kX} + \frac{1}{kY} + \frac{1}{kZ}\right) \\ &= (X + Y + Z)\left(\frac{1}{X} + \frac{1}{Y} + \frac{1}{Z}\right) = n \end{align}$

が成り立つため、 $(kX, kY, kZ)$ も解になります。したがって、整数解を見つけることと有理数解を見つけることは同等です。したがって、Knightの問題は有理数解を求める問題としてもよいことに注意します。

実はこのKnightの問題、与えられた $n$ によって、解を持つ場合と持たない場合があります。解を持つ条件は次節で述べるように簡単ではありません。

Knightの問題は $X, Y, Z$ の3変数の問題ですが、2変数や4変数の問題に拡張してみると話はまた変わってきます。

たとえば2変数の場合は

$\displaystyle n = (X + Y)\left(\frac{1}{X} + \frac{1}{Y}\right)$

となりますが、この場合は $n = 0, 4$ のときのみ解を持ちます。 $n = 0$ のときは $(X, Y) = (1, -1)$ として、 $n = 4$ のときは $(X, Y) = (1, 1)$ とすればよいでしょう。

4変数の場合は、

$\displaystyle n = (X + Y + Z + W)\left(\frac{1}{X} + \frac{1}{Y} + \frac{1}{Z} + \frac{1}{W}\right)$

となりますが、任意の $n$ に対して解を持つことが知られています。説明しませんが
$(X, Y, Z, W) = (m^2+m+1, m(m+1)(n-1), (m+1)(n-1), -m(n-1))$
が上式の解であることが確認できます（ $m$ は任意）。

こういった意味で、3変数の問題は「ちょうどいい」問題といえそうです。

一見初等的に解けそうな感じがする問題ですが、いろいろ検討してみるとそれほど簡単な問題ではないとわかります。しかしながら、実はこの問題、楕円曲線の理論を使うと鮮やかに解けてしまうのです。

楕円曲線との関連

Knightの問題が楕円曲線と関連することを示しましょう。

固定した $n$ に対して、式 $(1)$ が有理数解 $(X, Y, Z)$ を持つとします。このとき、新しい変数 $x, y$ を用いて

$\begin{align} x &= \frac{-4(XY + YZ + ZX)}{Z^2} \\ y &= \frac{2(x - 4n)Y}{Z} - (n-1)x\end{align}$

とおきます。すると $x, y$ は

$y^2 = x^3 + (n^2 - 6n - 3)x^2 + 16nx \tag{2}$

という式を満たします。この式を $K_n$ と呼びましょう。

$K_n$ の右辺は $x$ についての3次式となっています。判別式をとると $\Delta_n = 2^{12}n^2(n-1)^3(n-9)$ となり、 $n \neq 0, 1, 9$ であれば $\Delta_n \neq 0$ になり、このとき $K_n$ は楕円曲線となります。

したがって、 $n \neq 0, 1, 9$ であれば、Knightの問題の有理数解は楕円曲線 $K_n$ の有理点に対応することがわかります。

$(X, Y, Z) \;\; \leadsto \;\; (x, y) \in K_n(\mathbb{Q})$

この逆を考えたいのですが、 $K_n$ のすべての有理点がKnightの問題の解に対応するわけではありません。

ここで少し楕円曲線の一般論が必要になります。モーデルの定理により、 $\mathbb{Q}$ 上定義された楕円曲線の有理点全体は、有限生成アーベル群をなします。また、有限生成アーベル群の基本定理より、楕円曲線のモーデル・ヴェイユ群（有理点全体のなす群）は自由部分とねじれ部分の直和で表せます。

つまり、楕円曲線 $K_n$ に対しては、そのモーデル・ヴェイユ群 $K_n(\mathbb{Q})$ について以下の群同型が成り立ちます：

$K_n(\mathbb{Q}) \simeq \mathbb{Z}^r \oplus K_n(\mathbb{Q})_{\text{tors}}$

ここで、 $K_n(\mathbb{Q})_{\text{tors}}$ は $K_n(\mathbb{Q})$ のねじれ部分（つまり、位数有限の点全体のなす部分群）です。 $r$ は $K_n(\mathbb{Q})$ の階数（rank）といって $\text{rank}\, K_n(\mathbb{Q})$ と表します。

さて、 $K_n(\mathbb{Q})$ について詳しく調べると、そのねじれ部分は

$\require{cancel} \cancel{K_n(\mathbb{Q})_{\text{tors}} = \{ \mathcal{O}, (0, 0), (4, \pm 4(n-1)), (4n, \pm 4n(n-1)) \} \simeq\mathbb{Z}/6\mathbb{Z}}$

であると分かります。実は、これらの位数有限の有理点はKnightの問題の解にはなりません。

（2021.04.22訂正）上記のように書いておりましたが、実は $K_n(\mathbb{Q})$ のねじれ部分は任意の $n$ について必ずしも上記の通りにならないことをご指摘いただきました。

実際、 $n = 10$ のときに例外となるねじれ点が存在します。その点も含めて正確に記述をすると次のようになります。

$\displaystyle K_n(\mathbb{Q})_{\text{tors}} = \begin{cases} \{ \mathcal{O}, (0, 0), (4, \pm 4(n-1)), (4n, \pm 4n(n-1)) \} \simeq\mathbb{Z}/6\mathbb{Z} & (n \neq 0, 1, 9, 10) \\ \{\mathcal{O}, (0, 0), (-20, \pm 60), (4, \pm 36), (-5, 0), (-8, \pm 24), (40, \pm 360), (-32, 0)\} \simeq \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/6\mathbb{Z} & (n = 10) \end{cases} \tag{3}$

たとえば、 $n = 10$ のケースにおいて、上記の点はNagell-Lutzの定理により発見でき、またねじれ点であることは $6P = \mathcal{O}$ であることから確認できます。

$n \neq 0, 1, 9, 10$ において $\mathbb{Z}/6\mathbb{Z}$ に同型であることは、証明が必要な事項です。
一般の $n$ について判別式 $\Delta_n = 2^{12} n^2 (n-1)^3 (n-9)$ の約数を考えることで、Nagell-Lutzより

$\{ \mathcal{O}, (0, 0), (4, \pm 4(n-1)), (4n, \pm 4n(n-1)) \}$

がねじれ点の候補であることがわかり、また実際にねじれ点であることもわかります。

したがって、 $n = 10$ を含む $n\neq 0, 1, 9$ において

$K_n(\mathbb{Q})_{\text{tors}} \subset \{ \mathcal{O}, (0, 0), (4, \pm 4(n-1)), (4n, \pm 4n(n-1)) \}$

であることまではいうことができます。ここで、さらに強く「等号である」としてよいと考えてしまったのが私の勘違いです。

実際、参考資料に挙げた後藤先生の記事にて $K_n(\mathbb{Q})_{\text{tors}} \simeq \mathbb{Z}/6\mathbb{Z}$ と記載があり、これで合っているものと勘違いをしたまま記事にしてしまっておりました。私自身の手で十分確認することを怠ったのが良くなかったと思います。申し訳ありません。

$n \neq 0, 1, 9, 10$ のケースにおいて、ねじれ点のなす群が $\mathbb{Z}/6\mathbb{Z}$ に同型であることついては、本件をご指摘いただいたNakao様より証明をご連絡いただいております。ねじれ点に関するMazurの定理を用いることで

$\mathbb{Z}/6\mathbb{Z}$ または $\mathbb{Z}/2\mathbb{Z}\times \mathbb{Z}/6\mathbb{Z}$ または $\mathbb{Z}/12\mathbb{Z}$

のいずれかであることがわかります。位数4の点が存在しないことを示すことにより $\mathbb{Z}/12\mathbb{Z}$ を除外できます。また $n\neq 10$ では位数2の点が $(0, 0)$ 以外に存在しないことを示すことで $\mathbb{Z}/2\mathbb{Z}\times \mathbb{Z}/6\mathbb{Z}$ を除外でき、 $\mathbb{Z}/6\mathbb{Z}$ であると特定できるという方針のようです。

まだ私自身、証明の細部を理解できていない部分があり、今後もこちらに掲載する予定はありませんが、念のため証明があるということを付記させていただきます。
（参考文献のBremnerの記事において、上記のねじれ点の構造についての記載があるようです。）

一方で、位数無限の有理点があったとして、それを $(x, y)$ としたとき

$\begin{align} X &= y - (n-1)x \\ Y &= -y - (n-1)x \\ Z &= 2(4n-x) \end{align}$ 　　　　　(4)

とおくことで、 $(X, Y, Z)$ はKnightの問題の有理数解となります。

よって

$(x, y) \in K_n(\mathbb{Q}), \;\; (x, y)$ は位数無限 $\;\; \leadsto \;\; (X, Y, Z)$

がいえたということです。

以上のことから、Knightの問題の必要十分条件が次の通り得られます：

$(1)$ が整数解を持つ $\displaystyle \;\; \cancel{\Longleftrightarrow \;\; \text{rank}\, K_n(\mathbb{Q}) > 0}$

（2021.04.22 訂正）
上記にも誤りがありますので、訂正させていただきます。

前述したねじれ点のなす群の構造 $(3)$ を前提としたときに、 $n = 10$ について

$A = \{ \mathcal{O}, (0, 0), (4, \pm 4(n-1)), (4n, \pm 4n(n-1)) \}$

に属さない6点

$(-20, \pm 60), (-5, 0), (-32, 0), (-8, \pm 24)$

はすべて $(4)$ の式変形によってKnightの問題の整数解にうつることが確認できます。したがって、 $n = 10$ のケースを別途考慮する必要があります。実際、たとえば Sagemath 等でランクを計算してみると、 $K_{10}(\mathbb{Q})$ のランクは $0$ であるので、上の同値は誤りであることが確認できます。

一方、 $A$ に属する点については、Knightの問題には対応しないことが分かります。というのも、 $A$ の任意の点を具体的に $(4)$ に入れると、 $X, Y, Z$ のいずれか１つが $0$ になってしまうからです。 $1/X, 1/Y, 1/Z$ が存在しないので、これらは解にならないというわけです。

逆に、式 $(4)$ において $X, Y, Z$ のいずれかが $0$ になる条件を逆算することで、そのような点は $A$ の点に限られることが示せます。

したがって、 $K_n$ が楕円曲線である $n \neq 0, 1, 9$ に関して言えば

$(1)$ が整数解を持つ $\displaystyle \;\; \Longleftrightarrow \;\; n = 10 \;\; \text{または} \;\; \text{rank}\, K_n(\mathbb{Q}) > 0$

が正しい主張となります。

また、 $n = 0, 1, 9$ においても、実はKnightの問題の整数解があることが具体的に確認できます。（この例についてもNakao様より教えていただきました。）

$\displaystyle 0 = (1 + (-2) + 1)\left(\frac{1}{1} + \frac{1}{(-2)} + \frac{1}{1}\right)$

$\displaystyle 1 = (1 + (-1) + 1)\left(\frac{1}{1} + \frac{1}{(-1)} + \frac{1}{1}\right)$

$\displaystyle 9 = (1 + 1 + 1)\left(\frac{1}{1} + \frac{1}{1} + \frac{1}{1}\right)$

よって、 $K_n$ は楕円曲線にならないケースも含めると

$(1)$ が整数解を持つ $\displaystyle \;\; \Longleftrightarrow \;\; n = 0, 1, 9, 10 \;\; \text{または} \;\; \text{rank}\, K_n(\mathbb{Q}) > 0$

が最終的な結論となります。

具体例の計算

具体的に、冒頭で述べた $n = 11$ について、楕円曲線を使って解を求めてみましょう。せっかくなので、SageMath のプログラムを使って確認してみたいと思います。

$n = 11$ のとき、 $K_{11}$ は

$y^2 = x^3 + 52x^2 + 176x$

となります。SAGEで

sage: n = 11
sage: Kn = EllipticCurve([0,(n^2-6*n-3),0,16*n,0]); Kn

と打ち込むと

Elliptic Curve defined by y^2 = x^3 + 52*x^2 + 176*x over Rational Field

と出てきて確認できます。判別式は

sage: Kn.discriminant()
991232000

より、ゼロではないので楕円曲線の条件を満たします。

続いて $K_{11}(\mathbb{Q})$ の生成元を確認しましょう。

sage: Kn.gens()
[(-44 : 88 : 1)]

という結果より、 $(x, y) = (-44, 88)$ が生成元であるとわかります。生成元が一つであり、先のねじれ点に属さないので無限位数であることもわかります。よって

$\text{rank}\,K_{11}(\mathbb{Q}) = 1$

であることがわかり、 $\text{rank}\,K_{11}(\mathbb{Q}) > 0$ より条件を満たします。したがって、Knightの問題は $n = 11$ で解を持つことが結論付けられるわけです。

最後に、有理点 $(x, y) = (-44, 88)$ が、 $n = 11$ のKnightの問題の解に対応することを確認しましょう。

sage: x = -44
sage: y = 88

sage: X = y - (n-1)*x; X
sage: Y = -y - (n-1)*x; Y
sage: Z = 2*(4*n - x); Z
528
352
176

sage: (X + Y + Z)*(1/X + 1/Y + 1/Z)
11

たしかに、楕円曲線を使って、Knightの問題の解を得ることが出来ましたね！めでたしめでたし！

それでは、今日はこの辺で。

参考資料

後藤丈志「古典的 Diophantus 問題に対応する楕円曲線のセルマー群と有向グラフ」，2006年度整数論サマースクール報告集
http://www.ma.noda.tus.ac.jp/u/ha/SS2006/Data/Hokoku/goto.pdf

横山俊一「計算する立場からの楕円曲線論入門」，山形大学理学部数理科学科2014 年度後期「数理情報特選F/数理科学特別講義E」講義資料1
http://www2.math.kyushu-u.ac.jp/~s-yokoyama/lectures/2015-2018/files/2014Yamagata.pdf

（2021.04.22追記）
Nakao様よりKnightの問題に関する基本的な文献として、次をご紹介いただきました。

Andrew Bremner, Richard K. Guy, Richard J. Nowakowski, "Which integers are representable as the product of the sum of three integers with the sum of their reciprocals?", Math Comp, Volume 61, Number 203, July 1993, pages 117-130.

以前のバージョンの記事の時点では、上記の後藤先生、横山先生の記事を読むに留まっておりまして、これ以上の文献を調べることはありませんでした。
十分内容を理解できていない点をご承知おきいただいた上で、"4. The torsion group" の節を確認すると、たしかに $n = 10$ について $\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/6\mathbb{Z}$ に同型であること、それ以外の $n \neq 0, 1, 9$ のケースにおいては $\mathbb{Z}/6\mathbb{Z}$ に同型であることが示されているように見えます。