最小重なり問題

数論と集合論において、最小重なり問題はハンガリーの数学者ポール・エルデシュによって1955年に提唱された問題である。 ^[1]^[2]

問題の正式な説明

$A = {a i}$ と $B = {b j}$ を、自然数集合 ${1, 2, \dots, 2$ $n$ $}$ を分割した2つの相補集合とし、両者の基数は同じで $nとする。方程式$ $a$ $i$ $-$ $b$ $j$ $=$ $k$ の解の個数を $M$ $k$ で表す。ここで $k$ $は-2$ $n$ $から 2$ $n$ までの整数である。M $($ $n$ $)$ $は$ 次のように定義される。

M(n):=\min_{A,B}\max_{k}M_{k}.\,\!

問題は $n$ が十分に大きいときに $M (n)を推定することである。$ ^[2]

歴史

この問題は、ポール・エルデシュが組合せ論的数論において提唱した問題の一つであり、英語圏では最小重なり問題として知られています。この問題は、1955年にRiveon Lematematica誌に掲載された論文「数論に関する若干の考察」^{[3] （ヘブライ語）で初めて定式化され、}リチャード・K・ガイの著書「数論における未解決問題」^[1]で解説された古典的な問題の一つとなっています。

部分的な結果

$M$ $($ $n$ $)$ の下限値と上限値の計算は、最初に定式化されて以来継続的に進歩しており、次のような結果が得られています。^[1]^[2]

より低い

限界劣勢	著者	年
$M(n)>n/4$	P.エルデシュ	1955
$M(n)>(1-2^{-1/2})\,n$	P. エルデシュ、シェルク	1955
$M(n)>(4-6^{1/2})\,n/5$	S. スヴィエルツコフスキ	1958
$M(n)>(4-15^{1/2})^{1/2}\,(n-1)$	L. モーザー	1966
$M(n)>(4-15^{1/2})^{1/2}\,n$	JK ホーグランド	1996
$M(n)>0.379005{\,}n$	EPホワイト	2022

アッパー

上限上限	著者	年
$M(n)<(1+o(1))n/2$	P.エルデシュ	1955
$M(n)<(1+o(1))2n/5$	TS モツキン、KE ラルストン、JL セルフリッジ、	1956
$M(n)<(1+o(1))0.382002...n$	JK ホーグランド	1996
$M(n)<(1+o(1))0.380926...n$	JK ホーグランド	2016

JK Hauglandは、 $M$ $($ $n$ $) /$ $n$ の極限が存在し、それが0.385694未満であることを示した。この研究により、彼は1993年に若手科学者コンクールで賞を受賞した。^{[4] 1996年には、}Peter Swinnerton-Dyerの結果を用いて、上限を0.38201まで改善した。^[5]^[2]これは現在、さらに0.38093まで改善されている。^[6] 2022年には、E.P. Whiteによって下限が少なくとも0.379005であることが示された。^[7]

最初に知られた値は $M (n)$

最初の15個の正の整数に対する $M (n)$ の値は次の通りである: ^[1]

$n\,\!$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	...
$M(n)\,\!$	1	1	2	2	3	3	3	4	4	5	5	5	6	6	6	...

それはまさに小数の法則である^[1] $\textstyle \lfloor 5(n+3)/13\rfloor$

参考文献

^ abcde ガイ、リチャード K. (2004)。「C17」。ベンサスにて、カタリン A.ハルモス、ポール R. (編)。整数論における未解決の問題。ニューヨーク: Springer Science+Business Media Inc.、 199 ～ 200ページ。ISBN 0-387-20860-7。
^ abcd Finch, Steven (2004年7月2日). 「エルデシュの最小重なり問題」(PDF) . 2015年4月5日時点のオリジナル(PDF)からアーカイブ。 2013年12月15日閲覧。
^ P.エルデシュ：数論に関するいくつかのコメント（ヘブライ語）、Riveon Lematematika 9（1955）、45-48 MR17,460d。
^ ハウグランド、ヤン・クリスチャン。「最小オーバーラップ問題」。2016 年9 月 20 日に取得。
^ ハウグランド、ヤン・クリスチャン (1996). 「最小オーバーラップ問題の進歩」。数論ジャーナル。58 (1)。オハイオ州 (米国): 71–78 . doi : 10.1006/jnth.1996.0064。ISSN 0022-314X。
^ ハウグランド、ヤン・クリスチャン (2016). 「最小オーバーラップ問題の再検討」。arXiv : 1609.08000 [math.GM]。
^ ホワイト、イーサン・パトリック (2022). 「エルデシュの最小重複問題」。arXiv : 2201.05704 [math.CO]。

[rguy-1] ガイ、リチャード K. (2004)。「C17」。ベンサスにて、カタリン A.ハルモス、ポール R. (編)。整数論における未解決の問題。ニューヨーク: Springer Science+Business Media Inc.、 199 ～ 200ページ。ISBN 0-387-20860-7。

[finch-2] Finch, Steven (2004年7月2日). 「エルデシュの最小重なり問題」(PDF) . 2015年4月5日時点のオリジナル(PDF)からアーカイブ。 2013年12月15日閲覧。

[minimum_overlap-3] P.エルデシュ：数論に関するいくつかのコメント（ヘブライ語）、Riveon Lematematika 9（1955）、45-48 MR17,460d。

[4] ハウグランド、ヤン・クリスチャン。「最小オーバーラップ問題」。2016 年9 月 20 日に取得。

[5] ハウグランド、ヤン・クリスチャン (1996). 「最小オーバーラップ問題の進歩」。数論ジャーナル。58 (1)。オハイオ州 (米国): 71–78 . doi : 10.1006/jnth.1996.0064。ISSN 0022-314X。

[6] ハウグランド、ヤン・クリスチャン (2016). 「最小オーバーラップ問題の再検討」。arXiv : 1609.08000 [math.GM]。

[7] ホワイト、イーサン・パトリック (2022). 「エルデシュの最小重複問題」。arXiv : 2201.05704 [math.CO]。