Vieta jumping

数論におけるVieta jumping（ヴィエタジャンピング）あるいはroot flippingは、証明方法の一つ。2つの整数の関係と解が与えられた問題に用いられる。特にディオファントス方程式の1つの解から新しい解を作る際に使う。Vieta jumpingには多様なバリエーションが存在しており、大抵は根と係数の関係（ヴィエタの公式）を使用した方程式の解を探すことによる無限降下に関連している。

歴史

Vieta jumpingはディオファントス方程式と同次二次形式（英語版）の論理における基本的な解法である。例えば、1879, 1953年のミルズの論文において、マルコフ方程式の解析に使われている^[1]。

1988年の国際数学オリンピックにおいて、コンテストで最も難解であるとされた問題の解法に使用され、数学の競技で注目されるようになった^[2]^[3]。

a, b

を、

ab + 1

が

a 2 + b 2

を割り切るような2つの正の整数とする。

{\frac {a^{2}+b^{2}}{ab+1}}

が平方数であることを示せ^[4]。

アーサー・エンゲル（英語版）はこの問題の難易度について、次のように言及した。

Nobody of the six members of the Australian problem committee could solve it. Two of the members were husband and wife Georg（英語版）and Esther Szekeres（英語版）, both famous problem solvers and problem creators. Since it was a number theoretic problem it was sent to the four most renowned Australian number theorists. They were asked to work on it for six hours. None of them could solve it in this time. The problem committee submitted it to the jury of the XXIX IMO marked with a double asterisk, which meant a superhard problem, possibly too hard to pose. After a long discussion, the jury finally had the courage to choose it as the last problem of the competition. Eleven students gave perfect solutions.

この問題で最高得点を獲得した11人の中にはゴ・バオ・チャウ、ラヴィ・ヴァキル（英語版）、ズヴェズデリナ・スタンコヴァ（英語版）、ニクショル・ダン（英語版）がいる^[5]。ブルガリア代表のエマヌエル・アタナソフ（Emanouil Atanassov）は、一段落でこの問題を解き、特別賞を受賞した^[6]。テレンス・タオやエロン・リンデンシュトラウスは問題を解けず1点に収まった。

Standard Vieta jumping

standard Vieta jumping のコンセプトは背理法であり、次の4つの工程から成る^[7]。

与えられた条件に背くいくつかの解 $a 1, a 2, ...$ が存在するという矛盾を想定する。
最小性の定義に従って、解のうちの最小のものを取る。
式の $a i$ を変数 $x$ に置き換え、 $a i$ が解となる方程式を得る。
ヴィエタの公式を用いて、より小さい解を探し、矛盾を導く。

例

1988年IMO問6: $a, b$ を、 $ab + 1$ が $a 2 + b 2$ を割り切るような2つの正整数とする。 $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}a2 + b2/ab + 1$ が完全平方であることを示せ^[8]^[9]。

非平方数 $k$ を固定する。 $k = a 2 + b 2 / ab + 1$ を満たす正整数 $(a, b)$ の存在を仮定する。
$(A, B)$ を、 $k = A 2 + B 2 / AB + 1$ を満たし $A + B$ が最小となる2つの正整数とする。ただし $A \geq B$ としても一般性を失わない。
$B$ を固定して $A$ を変数 $x$ に置換すると方程式 $x 2 - (kB) x + (B 2 - k) = 0$ が導かれる。この方程式の根の1つは $x 1 = A$ であるから、二次方程式の解と係数の関係より、 $x 2 = kB - A$ と $x 2 = B 2 - k / A$ が分かる。
一つ目の式より $x 2$ が整数であることが分かり、二つ目の式から $k$ が非完全平方なので $x 2 \neq 0$ が分かる。 $x 22 + B 2 / x 2 B + 1 = k > 0$ より $x 2 B > -1$ 、そして $x 2$ が正整数であることが従う。 $A \geq B$ より、 $x 2 = B 2 - k / A < B 2 / A \leq A$ つまり $x 2 < A$ であるから $x 2 + B < A + B$ 。これは $A + B$ の最小性に矛盾する。

Constant descent Vieta jumping

constant descent Vieta jumping は、 $a, b$ の関係と定数 $k$ に何らかの関係があることを証明したいときに用いる^[10]。standard Vieta jumpingとは異なり、 constant descentは背理法を使わない。

等号成立の場合は $a > b$ を仮定して証明する。
$b, k$ を固定し、 $a, b, k$ の関係式を、 $b, k$ を係数とし、 $a$ が1つの解となる二次形式に変形する。他方の解 $x 2$ をヴィエタの公式で表す。
上の任意の基本の場合 $(a, b)$ について、 $0 < x 2 < b < a$ と、 $x 2$ が整数であることを示す。同じ定数 $k$ に対して $(a, b)$ を $(b, x 2)$ に置き換える操作を行い、最初の基本の場合に帰着するまで繰り返す。
$(a, b)$ のケースに対して主張を証明し、 $k$ がこの過程で不動であることからすべてのペアに対して主張が証明される。

例

$a, b$ を、 $ab$ が $a 2 + b 2 + 1$ を割り切る正整数とする。 $3 ab = a 2 + b 2 + 1$ を示せ^[11]。

$a = b$ つまり $a 2$ が $2 a 2 + 1$ を割り切る（すなわち $a 2$ が1を割り切る）ならば $a = b = 1$ で、式 $3(1)(1) = 1 2 + 1 2 + 1$ が成立する。以降 $a > b$ としても一般性を失わない。
条件を満たす $(a, b)$ について、 $k = a 2 + b 2 + 1 / ab$ とする。二次形式に変形して数を置き換えると、 $x 2 - (kb) x + (b 2 + 1) = 0$ となる。この方程式の解の1つは $a$ で、ヴィエタの公式より他方の解を $x 2$ として、 $x 2 = kb - a = b 2 + 1 / a$ が従う。
式より $x 2$ が正整数であることが示される。 $a > b$ と、 $a, b$ がともに正であることから $a \geq b + 1$ でさらに $ab \geq b 2 + b$ となる。 $b > 1$ なので $ab > b 2 + 1$ 。したがって $x 2 = b 2 + 1 / a < b$ が成立する。同じ定数 $k$ に対して $(a, b)$ を $(b, x 2)$ に置換する操作を繰り返し、基本の場合になるまで続ける。
ここで帰着する基本の場合は $b = 1$ の場合である。 $(a, 1)$ が条件を満たすには、 $a$ が $a 2 + 2$ を割り切る必要があるが、これはつまり $a$ は2を割り切る、即ち $a$ は1か2である。 $a = b$ の場合は除外したので $a$ は2に限ることができる。このとき、 $k = a 2 + b 2 + 1 / ab = 6 / 2 = 3$ 。 $k$ はこの過程（Vieta jumping）を通して不動であり、条件をみたす任意の $(a, b)$ について $k = 3$ が証明された。

幾何学的解釈

Vieta jumpingは第一象限内の双曲線上の格子点に関する視点で幾何学的に説明できる^[2]。より小さな根を捜索する過程は下方の格子点を探す操作に等しい。この手順は次のようになる。

与えられた条件より、 $x, y$ を入れ替えても変わらない、つまり $y = x$ に対して対称な双曲線の族の方程式を得る。
双曲線と $y = x$ の交点において主張を証明する。
$x < y$ としても一般性を失わない。 $(x, y)$ を双曲線上の格子点とする。ヴィエタの公式を用いて、 $x$ 座標が同じで異なる枝上にある格子点と対応させる。 $y = x$ における鏡映で元の枝上の新たな格子点を得る。
この操作によって、より $x$ 座標の低い格子点を得て（ $x = 0$ のような）ある条件を達成するまで繰り返すことができることが示される。条件を双曲線の方程式に代入することで、求めるべき結論を証明できる。

例

1988年IMO問6をもう一度例にとって、幾何学的方法で証明する。 $a, b$ を、 $ab + 1$ が $a 2 + b 2$ を割り切るような2つの正整数とする。 $a 2 + b 2 / ab + 1$ が完全平方であることを示せ。

$a 2 + b 2 / ab + 1 = q$ とし、 $q$ の値を固定する。 $q = 1$ のときは明らかに完全平方。 $q = 2$ ならば、 $(a - b) 2 = 2$ となって $a, b$ の整数解は存在しない。 $q > 2$ のとき、方程式 $x 2 + y 2 - qxy - q = 0$ を双曲線 $H$ の式として定義すると、 $(a, b)$ は $H$ 上の格子点である。
$(x, x)$ を $H$ 上の格子点（ただし $x > 0$ ）とすると、（ $q$ は整数なので） $x = 1$ が分かる。命題の主張は点 $(x, x)$ において真である。
今、第一象限 $x, y > 0$ 内の $H$ 上の格子点 $P = (x, y)$ をとる。ただし $x \neq y$ 。対称性より、 $x < y$ かつ $P$ が $H$ の上方の枝にあるとしてもよい。ヴィエタの公式を適用し、 $(x, qx - y)$ は下方の枝の格子点となることが分かる。 $y' = qx - y$ とする。双曲線 $H$ の方程式より、 $1 + x y' > 0$ 。 $x > 0$ より $y' \geq 0$ 。つまり $(x, y')$ は第一象限にある。鏡映より $(y', x)$ もまた第一象限の $H$ 上の点である。さらにヴィエタの公式より $yy' = x 2 - q$ と $y' = x 2 - q / y$ が分かる。 $x < y$ と式を組み合わせて $y' < x$ を示すことができる。新たに取った点 $Q = (y', x)$ は第一象限内かつ $H$ 上にあって、 $P$ の $x, y$ 座標よりもそれぞれの座標が小さい。
$Q$ が正の $x$ 座標を持つときはいつでもこの過程を再現することができる。しかし、これらの点の $x$ 座標は非負整数の減少数列であるから $H$ の上方の枝の点 $Q = (0, y)$ に到達する前までは、有限回だけしか繰り返すことができない。代入によって、 $q = y 2$ つまり $q$ が平方数であることが示された。

出典

^ Mills 1953.
^ ^a ^b Arthur Engel (1998). Problem Solving Strategies. Problem Books in Mathematics. Springer. p. 127. doi:10.1007/b97682. ISBN 978-0-387-98219-9
^ “The Return of the Legend of Question Six”. Numberphile (August 16, 2016). 2021年12月20日時点のオリジナルよりアーカイブ。August 16, 2016閲覧。
^ “International Mathematical Olympiad”. www.imo-official.org. 29 September 2020閲覧。
^ “Results of the 1988 International Mathematical Olympiad”. Imo-official.org. 2013年3月3日閲覧。
^ “Individual ranking of Emanouil Atanassov”. International Mathematical Olympiad. 2024年12月17日閲覧。
^ Yimin Ge (2007). “The Method of Vieta Jumping”. Mathematical Reflections 5.
^ “AoPS Forum – One of my favourites problems, yeah!”. Artofproblemsolving.com. 2023年1月8日閲覧。
^ K. S. Brown. “N = (x^2 + y^2)/(1+xy) is a Square”. MathPages.com. 2016年9月26日閲覧。
^ “AoPS Forum — Lemur Numbers”. Artofproblemsolving.com. 2023年1月8日閲覧。
^ “AoPS Forum – x*y | x^2+y^2+1”. Artofproblemsolving.com (2005年6月7日). 2023年1月8日閲覧。

外部リンク

Vieta Root Jumping at Brilliant.org
Mills, W. H. (1953). “A system of quadratic Diophantine equations”. Pacific J. Math. 3 (1): 209-220.
『数オリのテクニック〜Vieta jumping〜』 - 高校数学の美しい物語
『マルコフのディオファントス方程式～東北大AO入試を通して』 - 高校数学の美しい物語
“Vieta Jumping”. ご注文は数オリですか？. 2024年12月17日閲覧。
アタナソフの解法を解説する動画 Solving the Legendary IMO Problem 6 in 8 minutes ｜ International Mathematical Olympiad 1988 - YouTube

[FOOTNOTEMills1953-1] Mills 1953.

[ReferenceA-2] Arthur Engel (1998). Problem Solving Strategies. Problem Books in Mathematics. Springer. p. 127. doi:10.1007/b97682. ISBN 978-0-387-98219-9

[3] “The Return of the Legend of Question Six”. Numberphile (August 16, 2016). 2021年12月20日時点のオリジナルよりアーカイブ。August 16, 2016閲覧。

[4] “International Mathematical Olympiad”. www.imo-official.org. 29 September 2020閲覧。

[5] “Results of the 1988 International Mathematical Olympiad”. Imo-official.org. 2013年3月3日閲覧。

[6] “Individual ranking of Emanouil Atanassov”. International Mathematical Olympiad. 2024年12月17日閲覧。

[7] Yimin Ge (2007). “The Method of Vieta Jumping”. Mathematical Reflections 5.

[8] “AoPS Forum – One of my favourites problems, yeah!”. Artofproblemsolving.com. 2023年1月8日閲覧。

[9] K. S. Brown. “N = (x^2 + y^2)/(1+xy) is a Square”. MathPages.com. 2016年9月26日閲覧。

[10] “AoPS Forum — Lemur Numbers”. Artofproblemsolving.com. 2023年1月8日閲覧。

[11] “AoPS Forum – x*y | x^2+y^2+1”. Artofproblemsolving.com (2005年6月7日). 2023年1月8日閲覧。

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

歴史

Standard Vieta jumping

Constant descent Vieta jumping

幾何学的解釈

関連項目

出典

外部リンク

関連項目　