🔢 mathematics

Solution of Erd\H{o}s problem $\# 443$

이 논문은 집합 $\{k(m-k)\}$ 와 $\{l(n-l)\}$ 의 곱들의 교집합의 크기가 $(mn)^{o(1)}$ 에 의해 유계되지만 여전히 임의로 커질 수 있음을 증명함으로써 에르되시 문제(Erdős problem) #443을 해결한다.

원저자: Stijn Cambie

게시일 2026-07-29

📖 3 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Stijn Cambie

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

숫자가 단순히 차갑고 딱딱한 숫자가 아니라, 거대하고 보이지 않는 숨바꼭질 게임의 플레이어인 세상을 상상해 보십시오. 이것은 정수를 고유한 캐릭터와 비밀스러운 정체성을 가진 존재로 다루는 수학의 한 분야인 정수론의 영역입니다. 이 게임에서 우리는 종종 특정 규칙을 따름으로써 만들어진 "집합"—숫자들의 모임을 일컫는 멋진 표현이죠—을 살펴봅니다. 예를 들어, 어떤 숫자를 가져와서 그 파트너(특정 합계에 도달하기 위해 더해지는 수)와 곱하고 그 결과들을 모두 나열하면, 당신은 독특한 패턴을 얻게 됩니다. 수학자들은 다음과 같은 질문을 던지기를 좋아합니다: "만약 내가 서로 다른 규칙을 사용하여 두 개의 서로 다른 패턴을 만든다면, 그들은 얼마나 많은 숫자를 공통으로 가질까?" 이는 마치 고대 시집의 사전과 현대 속어 사전 양쪽 모두에 등장하는 단어가 몇 개인지 묻는 것과 같습니다. 이 질문은 수학 동아리의 퍼즐처럼 보일 수도 있지만, 이는 우리가 숫자의 숨겨진 구조를 이해하고, 패턴이 희귀한지, 흔한지, 혹은 완전히 예측 불가능한지를 밝혀내는 데 도움을 줍니다.

당신이 곧 듣게 될 논문은 전설적인 수학자 폴 에르되시(Paul Erdős)가 제기한 특정한 수수께끼를 다룹니다. 그는 두 가지 특별한 숫자 모음에 대해 궁금해했습니다. 첫 번째 모음은 숫자 $m$ 을 가져와서, $m$ 의 절반 이하인 더 작은 숫자 $k$ 를 선택하고, 곱 $k(m-k)$ 를 계산하여 만들어집니다. 두 번째 모음은 다른 숫자 $n$ 을 사용하여 똑같은 작업을 수행합니다. 큰 질문은 이것입니다: 이 숫자들( $m$ 과 $n$ )이 엄청나게 커질 때, 그들은 얼마나 많은 "공통의 친구들"(두 목록에 모두 등장하는 숫자)을 공유할 수 있을까요? 에르되시는 공유되는 친구의 수가 늘어나기는 하겠지만, 매우 느리게 늘어날 것이라고 추측했습니다. 즉, 어떤 아주 작은 오차 범위를 선택하더라도, 그 개수는 결국 숫자의 크기와 관련된 특정 수학적 공식보다 작아질 만큼 느리게 늘어날 것이라고 말입니다. 그는 또한 이 공유되는 친구의 수가 멈추지 않고 계속 늘어날 수 있는지, 아니면 천장에 부딪힐 것인지에 대해서도 물었습니다.

이 논문의 저자인 스틴 캄비(Stijn Cambie)는 이 수십 년 된 미스터리를 해결하는 탐정 역할을 합니다. 그는 공유되는 친구의 수가 실제로 유계(unbounded)임을 확인합니다. 즉, 적절한 $m$ 과 $n$ 을 선택한다면 그 수는 당신이 원하는 만큼 커질 수 있다는 뜻입니다. 이를 증명하기 위해 그는 영리한 트릭을 사용합니다: 그는 특정 제곱 차이를 두 개의 작은 조각으로 나누는 방법을 찾는 것이 공유되는 숫자를 찾는 것과 같다는 것을 보여줍니다. 이는 이 문제를 숫자의 "약수"(구성 요소)를 세는 문제로 바꿉니다. 우리는 어떤 숫자들은 엄청나게 많은 약수를 가지고 있다는 것을 알고 있으므로, 캄비는 우리가 항상 방대한 수의 공유되는 친구들을 만들어내는 $m$ 과 $n$ 의 쌍을 찾을 수 있음을 증명합니다.

하지만 이 논문은 또한 이 성장에 엄격한 속도 제한을 둡니다. 캄비는 공유되는 친구의 수가 매우 커질 수는 있지만, 그 성장이 믿기 힘들 정도로 느리다는 것을 입증합니다. 즉, 에르되시가 제안한 "작은 오차"의 범위 안에 들어올 만큼 느리다는 것입니다. 그는 그 개수가 관련된 숫자의 크기에 비해 본질적으로 "거의 상수"에 가까운 함수에 의해 제한된다는 것을 보여줍니다. 쉬운 말로 하면, 비록 당신이 겹치는 부분을 극대화하기 위해 최선의 숫자를 선택하더라도, 공유되는 친구의 수는 결코 폭발적으로 늘어나지 않을 것이며, 전체 숫자 중 아주 작은 비율로 계속 남을 것이라는 뜻입니다.

흥도하게도, 이 논문은 이야기의 반전을 드러냅니다: 이 문제는 사실 새로운 발견이 아니었습니다. 저자는 수학자 노르베르트 헤기바리(Norbert Hegyvári)가 40년 전에 이 정확한 문제를 해결했지만, 그의 증명은 최근에야 발표되었다고 언급합니다. 따라서 이 논문이 신선하고 명쾌한 설명을 제공하고 정답을 확인해주기는 하지만, 이 문제가 "해결된" 상태라는 사실은 그 이전의, 오랫동안 숨겨져 있던 연구의 공로입니다. 이 논문은 단순히 추측하는 것이 아니라, 수학적 증명을 제공하여 공유되는 친구의 수가 정확히 어떻게 행동하는지 보여주며, 그 수가 유계이면서도 동시에 사용된 숫자의 크기에 비해 놀라울 정도로 작다는 것을 확인해 줍니다.

기술 요약: 에르되시 문제(Erdős Problem) #443의 해법

문제 정의
본 논문은 1980년 에르되시와 그레이엄의 저작 [1]에서 제기된 문제 #443을 다룬다. 이 문제는 이차 형식 $k(m-k)$ 와 $\ell(n-\ell)$ 에 의해 생성되는 두 정수 집합에 관한 것이다. 여기서 $1 \le k \le m/2$ 및 $1 \le \ell \le n/2$ 이다. 구체적으로, $S(m) = \{k(m-k) : 1 \le k \le m/2\}$ 와 $S(n) = \{\ell(n-\ell) : 1 \le \ell \le n/2\}$ 라고 하자. 핵심 질문은 다음과 같다:

공통 정수의 개수 $f(n, m) = \#(S(m) \cap S(n))$ 를 추정할 수 있는가?
$m$ 과 $n$ 이 변함에 따라 이 숫자가 무한히 커지는가?
$mn $이 충분히 클 때, 이 숫자가 모든$ \epsilon > 0 $에 대하여$ (mn)^\epsilon$보다 엄격히 작은가?

방법론 및 유도
저자 스테인 캄비(Stijn Cambie)는 $f(n, m)$ 이라는 표기법을 채택하고, 일반성을 잃지 않고 $m > n$ 이라고 가정한다. 방법론의 핵심은 교집합 조건을 제곱의 차(difference of squares)로 변환하는 것이다.

$k(2m-k) = m^2 - (m-k)^2$ 임을 관찰함으로써, 저자는 $c = m-k$ 로 둔다. 두 집합에 공통으로 포함되는 정수에 대한 조건인 $k(2m-k) = \ell(2n-\ell)$ 은 다음과 같이 재작성된다:
$m^2 - c^2 = n^2 - d^2$
여기서 $d = n-\ell$ 이다. 항을 정리하면 다음과 같다:
$m^2 - n^2 = c^2 - d^2 = (c-d)(c+d)$
이 변환은 해의 개수가 정수 $m^2 - n^2$ 의 약수의 개수인 $\tau(m^2 - n^2)$ 의 절반에 의해 제한됨을 보여준다. $c-d$ 가 $\sqrt{m^2 - n^2}$ 보다 작은 약수여야 한다는 제약 조건이 이 상한을 설정하는 데 활용된다.

주요 결과

상한(Upper Bound): 본 논문은 $f(n, m) \le \lfloor \tau(m^2 - n^2) / 2 \rfloor$ 임을 입증한다. 약수 함수 $\tau(x)$ 에 관한 잘 알려진 결과, 즉 $\tau(x) \le 2^{(1+o(1))\frac{\log x}{\log \log x}} = x^{o(1)}$ 를 인용함으로써, 저자는 $f(n, m) = (mn)^{o(1)}$ 임을 확인한다. 이는 $mn $이 충분히 클 때 공통 정수의 개수가 임의의$ \epsilon > 0 $에 대하여$ (mn)^\epsilon$보다 작다는 추측을 확증한다.
무한성(Unboundedness): 공통 정수의 개수가 무한히 커지는지를 다루기 위해, 저자는 $m = n+1$ 인 특수한 경우를 고려한다. 이 시나리오에서 $m^2 - n^2 = 2n+1$ 이다. 해의 개수는 $\lfloor \tau(2n+1)/2 \rfloor - 1$ 과 관련이 있음이 밝혀진다. $\tau(x)$ 는 (고도로 합성된 수들에 대해 큰 값을 가지며) 무한히 커지므로, $f(2n+2, 2n)$ 은 무한하다. 이 구성은 $2n+1 = pq $(단,$ p \ge q \ge 2$)의 인수분해를 유효한 정수 해로 명시적으로 매핑한다.

의의 및 주장
본 논문은 에르되시 문제 #443에 대한 완전한 해법을 제공하며, 교집합 크기의 하다항 성장률(sub-polynomial growth rate)과 그 무한한 성질을 모두 확증한다고 주장한다.

저자는 해법의 역사와 관련하여 특정 언급을 포함한다: 노르베르트 헤기바리(Norbert Hegyvári) [2]가 이 문제를 40년 전에 독립적으로 해결하였다. 그러나 헤기바리의 증명은 이 노트의 제출 이후 최근에야 출판되었다. 본 논문은 헤기바리의 지연된 선행 연구를 인정하면서도, 이를 독립적인 검증이자 문제에 대한 해법으로 위치시킨다.

논문에서 인용된 참고문헌

[1] P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory, 1980.
[2] N. Hegyvári, (최근 출판된 문제의 해법).
[3] 약수 함수 $\tau(x)$ 에 관한 표준 결과.

유사한 논문