최소 중복 문제

수 이론과 집합 이론에서 최소 중복 문제는 1955년 헝가리 수학자 폴 에르드스가 제안한 문제다.^[1][2]

문제에 대한 공식 성명

A = {a_i}과(와) B_j = {b}은(는) 두 개의 보완적인 하위 집합으로, 자연 숫자 집합 {1, 2, …, 2n}을(를) 분할하여 둘 다 동일한 카디널리티, 즉 n을 갖도록 한다.M으로_k 등식 a_ij - b = k의 용액의 수를 나타내며, 여기서 k는 -2n과 2n 사이에 변하는 정수다. M (n)은 다음과 같이 정의된다.

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

문제는 n이 충분히 클 때 M(n)을 추정하는 것이다.^[2]

역사

이 문제는 Paul Erdős가 제안한 조합수 이론에서 찾을 수 있는데, 영어권 사용자들이 최소 중복 문제로 알고 있다.1955년 리봉 레메테마티카 수 이론에 대한 어떤 언급에서 처음 공식화되었으며, 리처드 K가 기술한 고전적 문제들 중 하나가 되었다. 그의 책 속의 남자 숫자 이론의 미해결 문제들.^[1]

부분 결과

처음 공식화된 이후 M(n)의 하한 및 상한 계산에 지속적인 진전이 있었으며, 그 결과는 다음과 같다.^[1][2]

더 낮게

한계 하한	작성자	연도
$[\displaystyle M(n)]n/4}$	P. 에르데스	1955
${\displaystyle M(n)>(1-2^{-1/2}\,n}$	P. Erdss, Scherk	1955
$[\displaystyle M(n)](4-6^{-1/2})\,n/5}$	S. 쉬에르츠코프스키	1958
${\displaystyle M(n)>(4-15^{1/2}^{1/2}\,(n-1)}$	엘모저	1966
${\displaystyle M(n)>(4-15^{1/2})^{1/2}\,n}$	J. K. 해글랜드	1996

상부

상위 제한	작성자	연도
${\displaystyle M(n)<(1+o(1)n/2}$	P. 에르데스	1955
${\displaystyle M(n)<(1+o(1))2n/5}$	T. S. Motzkin, K. E. Ralston, J. L. Selfridge,	1956
${\displaystyle M(n)<(1+o(1))0.382002...n}$	J. K. 해글랜드	1996
${\displaystyle M(n)<(1+o(1))0.380926...n}$	J. K. 해글랜드	2016

J. K. 하우글랜드는 M(n)/n의 한계가 존재하고 0.385694보다 작다는 것을 보여주었다.그의 연구로, 그는 1993년 젊은 과학자들 대회에서 상을 받았다.^[3]1996년 피터 스윈너튼-다이어의 결과를 이용해 상한을 0.38201로 개선했다.^[4][2]이것은 현재 0.38093으로 더욱 개선되었다.^[5]

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	...

$\lfloor {\displaystyle }$ ${\displaystyle 5}$(${\displaystyle \mathrm{n}}$+ 3${\displaystyle }$)${\displaystyle }$/ ${\displaystyle 13}$ ${\displaystyle \rfloor }$ ${\$인 것은 단지 소수의 법칙일 뿐이다.

참조