エルデシュ=シュトラウス予想
全ての整数 n ≥ 2 に対して 4/n = 1/x + 1/y + 1/z は正整数解を持つか? | ![]() |
エルデシュ=シュトラウス予想(エルデシュ=シュトラウスよそう、英語: Erdős–Straus conjecture)とは、数論上の未解決問題のひとつである。予想は、2以上の全ての整数 n に対し、 を満たす正の整数 x、y、z が存在するというものである。 すなわち、4/n という数が3つの単位分数の和として表せるかどうかということである。
エルデシュ=シュトラウス予想という名称は1948年にこの予想を提唱したポール・エルデシュとエルンスト・G・シュトラウス(英語版)に由来するが、その内容はより古い時代の数学と関連する。予想のような単位分数の和はエジプト数学で用いられたことから、エジプト式分数として知られる。エルデシュ=シュトラウス予想はエルデシュによって提唱された多くの予想(英語版)のひとつであり、またディオファントス方程式に関する数学上の多くの未解決問題のひとつでもある。
全ての n に対しての解が知られているわけではないものの、ある無限等比数列の無限の多くの値には解の簡単な公式があり、これらの既知の値をスキップすることで反例の探索を高速化することが可能である。さらに、すべての合成数の反例はその素因数により小さな反例を持つはずであるから、n が素数の場合についてのみ議論すればよい。計算機を用いた探索により、少なくとも n ≤ 1017 までは予想が成り立つことが知られている。
予想を負の単位分数まで拡張すれば成立することが知られている。また、分子が5以上となる分数に対する一般化についても研究されている。
背景と歴史
有理数を単位分数の和に展開したものをエジプト式分数と呼ぶ。この表記法は、分数を現代的な a/b(分子 a および分母 b)という形式ではなく、単位分数の和で表したエジプト数学に由来する。エジプト人は、リンド数学パピルス分数表(英語版)などのような、単位分数に2をかけた数(現代的な表記では 2/n となる)に対応するエジプト式分数の表を作成していた。これらの表において、ほとんどの展開は2つか3つの項を用いていた[1]。当時のエジプト数学では分数の展開項がすべて異なることが求められており、自明な展開 2/n = 1/n + 1/n が認められていなかったため、このような表が必要とされた。この(すべての項が異なるという)条件はしばしばエルデシュ=シュトラウス予想にも付け加えられるが、n > 2 において、同じ単位分数が含まれるような 4/n = 1/x + 1/y + 1/z の解はすべて相異なる項をもつものに変換できることが知られており(下記を参照せよ)[2]、そのような条件付けは深い意味を持たない。
エジプト人は必ずしもできるだけ少ない項数の展開を求めなかったものの、後世の数学者たちは展開に必要な最小項数に興味を持った。a/b で表される分数は高々 a 個の項の展開をもつから、2/n は高々2個、3/n は高々3個、4/n は高々4個の項を持つ。2/n は絶対に2個の項が必要であるが、3/n は2項で表現できる場合と3項が必要な場合が存在する。しかしながら、4/n の場合においては、すべての n に対して3項のみで展開できるのか、あるいは4項が必要な n が存在するのかは知られておらず、これがエルデシュ=シュトラウス予想の内容となっている。それゆえ、予想はより一般化された問い(すべての a に対し、分数 a/b の展開に必要な最小の項数はいくつか)の最初の未知な場合である[1]。
短い(ただし最短とは限らない)展開を探す方法として、1202年にフィボナッチが『算盤の書』で発表したエジプト式分数の貪欲法(英語版)が挙げられる。このアルゴリズムは各回の操作ごとに展開の和が対象の数より大きくならないような最大の単位分数を与える。各操作の後、まだ展開されていない分数の分子が小さくなるため、操作の総数は開始時の分子より大きくはなりえないが[1]、小さくなることはある。例えば、3/n に対してこのアルゴリズムを適用すると、n が3を法として2と合同な際に2項を用いる展開を与えるが、実際には n の因数に3を法として2と合同なものが存在するという(より弱い条件下で)2項での展開が必ず存在する。4/n という形式の場合、貪欲法は n が4を法として1と合同な際に4項の展開を与え、それ以外の場合は3項での展開を与える[3]。それゆえ、エルデシュ=シュトラウス予想は 4/n をエジプト式分数で表す際に、貪欲法より少ない項数で表す方法があるのかという問いに言い換えられる[1]。
エルデシュ=シュトラウス予想はポール・エルデシュとエルンスト・G・シュトラウスによって1948年に提唱され、Erdős (1950) で発表された。オブラート・リバールド(ハンガリー語版)もまた、予想に関する初期の研究結果を1948年に執筆し、1950年に発表した論文内で述べている。その中で彼はシュトラウスとHarold N. Shapiroによる既存の計算結果を拡張し、n ≤ 105 の場合において予想内容を検証している[4]。
定式化
予想は整数 n ≥ 2 に対して、 を満たす正の整数 x、y、z が存在すると主張している。例えば、n = 5 の場合には、という2つの解が存在する。
方程式 4/n = 1/x + 1/y + 1/z の両辺に nxyz をかけると、問いと同値な多項式 4xyz = n(xy + xz + yz) が得られる[注釈 1]。
相異なる単位分数
古代エジプトのそれと同じように、整数 x、y、z が全て異なるという条件を付け加える研究者がいる一方で、それらが等しくてもかまわないとする研究者も存在する[1]。n ≥ 3 の場合、同じ単位分数が含まれるような解はすべて相異なる項をもつものに変換できることが知られており、x、y、z が全て異なるかどうかは問題ではない[2]。これは、2つの等しい単位分数が以下の2つの方法のどちらかによって置き換えることが可能だからである。 (得られる分数の分母が偶数か奇数かによって)この置き換えは、重複する分数がなくなるまで繰り返し実行できる[注釈 2]。しかしながら、n = 2 の場合、4/2 = 1/2 + 1/2 + 1/1 およびそれを並びかえたもののみが解となる[1]。
負数解
エルデシュ=シュトラウス予想では、x、y、z のいずれもが正でなければならない。この条件は問題の難易度にとって不可欠なものとなっている。この条件がある場合でも、エルデシュ=シュトラウス予想が困難なのは n が奇数の場合のみであり、もし負の解が認められれば、全ての奇数 n に対して以下の式が解となる[5]。
計算結果
もし予想が偽ならば、単に3項で展開できない 4/n を見つけるだけで偽であると示せる。このことを確かめるため、多くの研究者が力まかせ探索によって予想の反例を探そうと試みてきた[6]。この類の探索によって、1017 までの n において予想が成り立つことが知られている[7]。
このような探索においては、n が素数であるような 4/n のみを対象とすれば良い。なぜならば、4/n が3項解を持つ時、全ての正の整数 m に対して 4/mn も同様に解が存在するからである。4/n の解を見つける時は、4/n の解を以下のように m で割ることで求められる。
合成数 n に対し、もし 4/n が予想の反例ならば、その任意の素因数 p もまた(おそらくは力まかせ探索でより早く見つかるであろう)反例 4/p を与える。それゆえ、合成数解を確かめることは不必要であり、探索において無視できる。その上、予想に対する既知の合同恒等式(下記を参照せよ)を用いることで、解を持つことが知られている値を飛ばし、探索をより効率化できる。例えば、貪欲法によって n が4を法として1と合同でない場合、4/n は高々3項で展開できることが知られているため、4を法として1と合同な場合についてのみ検証すれば良い。この予想の解決に向けた取り組みの一つとして、より多くの合同算術上の特徴を調べ、研究者がより少ない試行でより高い限界まで探索できるようにすることが挙げられる。
4/n 問題の相異なる解の数(n の函数と考える)も研究者によって n が小さい場合について調べられており、それによれば n が大きくなるにつれてやや不規則な増大を見せる。n = 3 の場合から数え始めると、分母が互いに異なる解の数は
- 1, 1, 2, 5, 5, 6, 4, 9, 7, 15, 4, 14, 33, 22, 4, 21, 9, …(オンライン整数列大辞典の数列 A073101)
となる。たとえ n がより大きい場合であっても、解の数が比較的少なくなることがある。例えば n = 73 の時、わずか7個の解しか存在しない。
理論結果
整数の変数を持つ代数方程式 4xyz = n(xy + xz + yz) の形において、エルデシュ=シュトラウス予想はディオファントス方程式の一例である。局所大域原理はこれらの方程式の研究には合同算術が必要であることを示唆している。もし代数方程式が整数解をもつならば、任意の整数 q に対して法 q を取れば、法 q の際の解が得られる。逆に、もし方程式が全ての素数冪 q に対して法 q 上での解を持つ場合、中国の剰余定理に関連した手法を用いてそれらの合同算術解をつなぎ合わせ整数解を得られる。与えられた問題が局所大域原理によって解くことができるかどうかはマニンの障害(英語版)によって制限されるが、エルデシュ=シュトラウス予想の場合にはこの制限は存在しない[8]。
それにもかかわらず、この原理はエルデシュ=シュトラウス予想の解決にはほとんど役に立たない。すべての n に対し、方程式 4xyz = n(xy + xz + yz) は任意の素数を法として容易に解くことができるが、これらの解をつなぎ合わせ、正整数解を得るのは不可能だと考えられている。しかしながら、合同算術およびそれを基にした恒等式はこの予想の研究において極めて重要な道具であることが示されている[9]。
合同恒等式
特定の合同関係を満たす n の値に対し、4/n の展開は多項恒等式の例として即座に見つけられる。例えば、n が3を法として2と合同な際、4/n は と展開できる。この時、3つの分母 n、(n + 1) / 3、n (n + 1) / 3 はそれぞれ n の多項式であり、n が3を法として2と合同な限り整数となる。エジプト式分数の貪欲法(英語版)によって n が24を法として1または17と合同な場合以外において常に3項以下の展開が得られ、また24を法として17と合同な場合においては3を法として2と合同な際の関係で補完できるため、これら2つの方法で3項以下の展開を得られない n は、24を法として1と合同となるような値のみである[10]。
Mordell (1967) によって列記された合同恒等式は、n が以下の条件のうちいずれかを満たす場合の3項でのエジプト式分数による 4/n の展開を与える。
- 2 mod 3 (上記)
- 3 mod 4
- 2 または 3 mod 5
- 3, 5, あるいは 6 mod 7
- 5 mod 8
モーデルの恒等式を組み合わせることで、1, 121, 169, 289, 361, 529 mod 840 の場合以外のすべての n について 4/n が展開可能である。この恒等式の対象外となる最小の素数は1009である。より大きな類の合同恒等式を組み合わせることで、Webbらは予想の反例候補の自然密度(英語版)が0であると示した。変数 N が無限大に向かうと、区間 [1, N] における反例候補の割合が極限において 0 に収束する傾向にある[11]。
恒等式の不在
もし、上記のような解が十分異なる剰余について見つけられ、合同性の完全な被覆系(英語版)を形成できれば、問題は解決される。しかし、Mordell (1967) が示したように、r mod p に合同な n の値に対して解を与える恒等多項式は、r が p のsquare moduloに合同でないときだけ存在しうる(より正確に言うと、この種の恒等式は r が p の平方剰余でないときのみ存在しうる。)。例えば、2は3の平方でない剰余であるから、モーデルの結果によれば2 mod 3と合同な n に対して恒等式が存在しうる。しかしながら、1は3の平方剰余である(1および2 mod 3両者の二乗に等しい)から、1 mod 3と合同な「すべての」n に対して類似する恒等式は存在しえない。より一般的に、1が n > 1 となるすべての n に対して平方剰余となる以上、1が常に含まれないため合同恒等式の完全な被覆系は存在しえない[12]。
モーデルの結果がこの問題に対する合同恒等式の形式を限定しているにもかかわらず、依然として合同恒等式を用いたエルデシュ=シュトラウス予想解決の可能性が残されている。素数は立体数ではないため、ハッセ・ミンコフスキーの定理より、p が素数ならば、p が q の平方剰余とならないような、より大きな素数 q が存在する。証明を解決するための可能性あるアプローチのひとつとして、任意の素数 p に対してより大きな素数 q を探し、p と q に関して合同な、4/n 問題の解となる n を見つけるというものがある。もしそのような例が見つかれば、全ての素数 p は予想の反例とならなくなり、したがって予想が正しいことになる[10]。
解の個数
4/n 問題に対する解の個数の平均(n までの素数について平均したもの)は上界で対数多項的(英語版)であると Elsholtz & Tao (2013) によって示されている。他のディオファントス方程式に関する問題のうちいくつかに関して、解の存在は解の個数に関する漸近下界によって示すことができるが、これは少なくとも解の個数が最低でも多項的増大を見せる時にうまく機能するもので、エルショルツとタオの結果(解の個数の増大がより遅い)からこの形の証明が成り立つ可能性は低いことがわかる。エルショルツとタオは解を x、y、z のうち1つか2つが n によって割り切れるかどうかによって分類している。n が素数の場合は、これらが唯一の可能性だが、(大概)n が合成数の場合は他の形をとる。彼らの証明はボンビエリ=ヴィノグラドフの定理(英語版)、ブルン=ティッチマーシュの定理(英語版)、および合同恒等式の仕組み(任意の互いに素な2正整数 a および b と、a + b の任意の正因数 c に対して、 n が 4ab を法として −c または −1/c と合同な際に有効)を用いている。例えば a = b = 1 とおくと、n が4を法として3と合同な時に有効なモーデルの恒等式の1つが得られる[13]。
一般化
4/n 型の分数と同様に、すべての 5/n 型分数(n > 1)が3つの正単位分数の和として表せられるだろうと予想されている。一般化された予想では、任意の正なる k に対して、有限個の例外を除いたすべての分数 k/n が3つの正単位分数の和として表せられると主張している。5/n 型に対する予想はヴァツワフ・シェルピニスキが1956年に論文で提唱し、その後彼の弟子であるアンジェイ・シンツェル(ポーランド語版)によって完全な予想に発展した[14]。
たとえ一般化された予想が任意の固定された値 k に対して偽であったとしても、1から N の間にある n に対して三項展開を持たないような k/n の数は N の函数として劣線形的にしか増大しない[11]。特にエルデシュ=シュトラウス予想(k = 4 の場合)が偽だったとして、その反例の個数は劣線形的にしか増大しない。より強力に、任意の定数 k に対して、エジプト式分数で展開する際3以上の項が必要な n の個数は劣線形的にすぎない[15]。一般化された予想の内容は展開不可能な分数の個数は劣線形的だけでなく有界であることと等しい。
n が奇数のとき、エジプト式分数に対する奇数貪欲法(英語版)からの類推で k/n = 1/x + 1/y + 1/z (x、y、z は相異なる正奇数)の解を求められる。この方程式の解は k = 3 の時常に存在することが知られている[16]。
脚注
注釈
- ^ x、y、z のうちどれが n で割り切れるかどうかを利用した、より複雑な予想法を用いたより単純なディオファントス方程式の例は Sander (1994) を参照せよ。
- ^ 密接に関連した置き換え法(分数の数を減らすために、偶数分母に関して異なる展開を用いている)の証明は Eppstein (1995) の conflict resolution を参照せよ。
出典
- ^ a b c d e f Graham (2013).
- ^ a b Eppstein (1995), conflict resolution section.
- ^ Eppstein (1995).
- ^ Obláth (1950); Elsholtz & Tao (2013)
- ^ Jaroma (2004).
- ^ Obláth (1950); Rosati (1954); Kiss (1959); Bernstein (1962); Yamamoto (1965); Terzi (1971); Jollensten (1976); Kotsireas (1999).
- ^ Salez (2014).
- ^ Bright & Loughran (2020).
- ^ Elsholtz & Tao (2013).
- ^ a b Ionascu & Wilson (2011).
- ^ a b Webb (1970); Vaughan (1970); Li (1981); Yang (1982); Ahmadi & Bleicher (1998); Elsholtz (2001).
- ^ Mordell (1967).
- ^ On the number of solutions to 4/p = 1/n_1 + 1/n_2 + 1/n_3, Terence Tao, "What's new", July 7, 2011; Counting the number of solutions to the Erdös-Straus equation on unit fractions, Terence Tao, July 31, 2011.
- ^ Sierpiński (1956); Vaughan (1970).
- ^ Hofmeister & Stoll (1985).
- ^ Schinzel (1956); Suryanarayana & Rao (1965); Hagedorn (2000).
参考文献
- Ahmadi, M. H.; Bleicher, M. N. (1998), “On the conjectures of Erdős and Straus, and Sierpiński on Egyptian fractions”, International Journal of Mathematical and Statistical Sciences 7 (2): 169–185, MR1666363 .
- Bernstein, Leon (1962), “Zur Lösung der diophantischen Gleichung m / n = 1 / x + 1 / y + 1 / z, insbesondere im Fall m = 4” (German), Journal für die Reine und Angewandte Mathematik 211: 1–10, doi:10.1515/crll.1962.211.1, MR0142508 .
- Bright, Martin; Loughran, Daniel (2020), “Brauer–Manin obstruction for Erdős–Straus surfaces”, Bulletin of the London Mathematical Society 52 (4): 746–761, arXiv:1908.02526, doi:10.1112/blms.12374, MR4171399 .
- Elsholtz, Christian (2001), “Sums of k unit fractions”, Transactions of the American Mathematical Society(英語版) 353 (8): 3209–3227, doi:10.1090/S0002-9947-01-02782-9, MR1828604 .
- Elsholtz, Christian; Tao, Terence (2013), “Counting the number of solutions to the Erdős–Straus equation on unit fractions”, Journal of the Australian Mathematical Society 94 (1): 50–105, arXiv:1107.1010, doi:10.1017/S1446788712000468, MR3101397, https://terrytao.files.wordpress.com/2011/07/egyptian-count13.pdf .
- Eppstein, David (1995), “Ten algorithms for Egyptian fractions”, Mathematica in Education and Research 4 (2): 5–15 . See in particular the "Small numerators" section
- Erdős, Paul (1950), “Az egyenlet egész számú megoldásairól (On a Diophantine Equation)” (Hungarian), Mat. Lapok. 1: 192–210, MR0043117, http://www.renyi.hu/~p_erdos/1950-02.pdf .
- Graham, Ronald L. (2013), “Paul Erdős and Egyptian fractions”, in Lovász, László; Ruzsa, Imre Z.; Sós, Vera T., Erdös Centennial, Bolyai Society Mathematical Studies, 25, Budapest: János Bolyai Mathematical Society(英語版), pp. 289–309, doi:10.1007/978-3-642-39286-3_9, MR3203600, https://www.math.ucsd.edu/~ronspubs/13_03_Egyptian.pdf
- Guy, Richard K. (2004), Unsolved Problems in Number Theory (3rd ed.), Springer Verlag, pp. D11, ISBN 0-387-20860-7 .
- Hagedorn, Thomas R. (2000), “A proof of a conjecture on Egyptian fractions”, American Mathematical Monthly(英語版) (Mathematical Association of America) 107 (1): 62–63, doi:10.2307/2589381, JSTOR 2589381, MR1745572, https://jstor.org/stable/2589381 .
- Hofmeister, Gerd; Stoll, Peter (1985), “Note on Egyptian fractions”, Journal für die Reine und Angewandte Mathematik 362: 141–145, MR809971 .
- Ionascu, Eugen J.; Wilson, Andrew (2011), “On the Erdös–Straus conjecture”, Revue Roumaine de Mathématiques Pures et Appliquées 56 (1): 21–30, arXiv:1001.1100, MR2848047 .
- Jaroma, John H. (2004), “On expanding 4/n into three Egyptian fractions”, Crux Mathematicorum 30 (1): 36–37, https://cms.math.ca/publications/crux/issue/?volume=30&issue=1 .
- Jollensten, Ralph W. (1976), “A note on the Egyptian problem”, Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing (Louisiana State Univ., Baton Rouge, La., 1976), Congressus Numerantium, XVII, Winnipeg, Man.: Utilitas Math., pp. 351–364, MR0429735 .
- Kiss, Ernest (1959), “Quelques remarques sur une équation diophantienne” (Romanian), Acad. R. P. Romîne Fil. Cluj Stud. Cerc. Mat. 10: 59–62, MR0125069 .
- Kotsireas, Ilias (1999), “The Erdős-Straus conjecture on Egyptian fractions”, Paul Erdős and his mathematics (Budapest, 1999), Budapest: János Bolyai Math. Soc., pp. 140–144, MR1901903 .
- Li, Delang (1981), “On the equation 4/n = 1/x + 1/y + 1/z”, Journal of Number Theory(英語版) 13 (4): 485–494, doi:10.1016/0022-314X(81)90039-1, MR0642923 .
- Mordell, Louis J. (1967), Diophantine Equations, Academic Press, pp. 287–290 .
- Obláth, Richard (1950), “Sur l'équation diophantienne ” (French), Mathesis(英語版) 59: 308–316, MR0038999, "M. Strauss [sic] a vérifié l'hypothèse de M. Erdős pour toute valeur de n < 5.000, et M. Shapiro pour n < 20.000. Nos théorèmes donnent la solution pour tout nombre < 106.128" .
- Rosati, Luigi Antonio (1954), “Sull'equazione diofantea ” (Italian), Boll. Un. Mat. Ital. (3) 9: 59–63, MR0060526 .
- Salez, Serge E. (2014), The Erdős-Straus conjecture New modular equations and checking up to , arXiv:1406.6307, Bibcode: 2014arXiv1406.6307S
- Sander, J. W. (1994), “On 4 / n = 1 / x + 1 / y + 1 / z and Iwaniec' half-dimensional sieve”, Journal of Number Theory 46 (2): 123–136, doi:10.1006/jnth.1994.1008, MR1269248 .
- Schinzel, André (1956), “Sur quelques propriétés des nombres et , où est un nombre impair” (French), Mathesis(英語版) 65: 219–222, MR0080683 .
- Sierpiński, Wacław (1956), “Sur les décompositions de nombres rationnels en fractions primaires” (French), Mathesis(英語版) 65: 16–32, MR0078385 . Reprinted with additional annotations in Sierpiński, Wacław (1974), Oeuvres Choisies, I, Warsaw: PWN—Éditions Scientifiques de Pologne, pp. 169–184, MR0414302 .
- Suryanarayana, D.; Rao, N. Venkateswara (1965), “On a paper of André Schinzel”, J. Indian Math. Soc., New Series 29: 165–167, MR0202659 .
- Terzi, D. G. (1971), “On a conjecture by Erdős-Straus”, Nordisk Tidskr. Informationsbehandling (BIT) 11 (2): 212–216, doi:10.1007/BF01934370, MR0297703 .
- Vaughan, R. C. (1970), “On a problem of Erdős, Straus and Schinzel”, Mathematika(英語版) 17 (2): 193–198, doi:10.1112/S0025579300002886, MR0289409
- Webb, William A. (1970), “On 4 / n = 1 / x1 + 1 / x2 + 1 / x3”, Proceedings of the American Mathematical Society(英語版) (American Mathematical Society) 25 (3): 578–584, doi:10.2307/2036647, JSTOR 2036647, MR0256984, https://jstor.org/stable/2036647 .
- Yamamoto, Koichi (1965), “On the Diophantine equation 4/n = 1/x + 1/y + 1/z”, Memoirs of the Faculty of Science. Kyushu University. Series A. Mathematics 19: 37–47, doi:10.2206/kyushumfs.19.37, MR0177945 .
- Yang, Xun Qian (1982), “A note on 4/n = 1/x + 1/y + 1/z”, Proceedings of the American Mathematical Society 85 (4): 496–498, doi:10.2307/2044050, JSTOR 2044050, MR660589, https://jstor.org/stable/2044050 .
関連項目
- 逆数の和の一覧(英語版)