最小重複問題

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

A = { a _i }とB = { b _j }を、自然数の集合{1, 2, …, 2 n }の分割である、互いに補集合となる 2 つの部分集合とする。ただし、両方の部分集合の濃度は同じnである。方程式a _i − b _j = kの解の数をM _kと表す。ここで、kは−2 nから 2 nまで変化する整数である。M ( n )は次のように定義される。    

${\displaystyle M(n):=\min _{A,B}\max _{k}M_{k}.\,\!}$

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

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

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