Largest Sidon subsets in weak Sidon sets

이 논문은 $(4,5)$-집합이 포함하는 Sidon 부분집합의 최대 크기를 나타내는 상수 $c_*$에 대해 하한을 $\frac{9}{17}$로, 상한을 $\frac{4}{7}$로 개선하여 기존 결과를 정밀화했습니다.

핵심

🍎 1. 기본 개념: 숫자 더하기 놀이

먼저, 이 논문에서 다루는 두 가지 중요한 '숫자 덩어리'를 이해해 봅시다.

• 시돈 집합 (Sidon Set):
  imagine you have a basket of apples (numbers). If you pick any two apples and add their weights together, 그 합이 반드시 유일해야 합니다.

  • 예: {1, 2, 4}라고 합시다.
    • 1+1=2, 1+2=3, 1+4=5, 2+2=4, 2+4=6, 4+4=8.
    • 모든 합 (2, 3, 5, 4, 6, 8) 이 서로 다릅니다.
  • 이런 규칙을 완벽하게 지키는 덩어리를 '완벽한 시돈 집합' 이라고 부릅니다.

• 약한 시돈 집합 (Weak Sidon Set):
  이제 규칙을 조금만 느슨하게 해봅시다. "서로 다른 두 숫자를 더했을 때만 합이 달라지면 된다" 고 칩시다. (같은 숫자를 두 번 더하는 건 허용하되, 그 결과는 다른 조합과 겹쳐도 괜찮습니다.)

  • 이 논문은 바로 이 '약한 규칙'을 따르는 숫자 덩어리 안에서, '완벽한 규칙'을 따르는 숫자 덩어리 (시돈 부분집합) 를 얼마나 많이 찾아낼 수 있는지를 연구했습니다.

🧩 2. 첫 번째 발견: 반은 무조건 찾는다! (Sárközy & Sós 의 문제)

수학자들은 오랫동안 궁금해했습니다. "약한 규칙을 따르는 아주 큰 숫자 덩어리가 있다면, 그 안에서 완벽한 규칙을 따르는 숫자들을 얼마나 골라낼 수 있을까?"

• 논문의 결론: "아무리 큰 덩어리라도, 그 안에 최소 절반 (50%) 은 완벽한 규칙을 따르는 숫자들을 골라낼 수 있다."
• 비유:
  imagine you have a huge bag of mixed candies. Some are 'perfectly sweet' (Sidon), some are 'mostly sweet' (Weak Sidon).
  이 논문은 "가장 나쁜 경우에도, 'mostly sweet'인 캔디들 100 개 중에서 적어도 50 개 이상은 'perfectly sweet'인 캔디로 만들 수 있다"는 것을 증명했습니다.
  • 수학적으로 $n$개의 숫자가 있다면, 그중 $\lceil \frac{n+1}{2} \rceil$개 (즉, $n/2$보다 하나 더 많은 정수) 만큼은 반드시 완벽한 시돈 집합을 이룰 수 있다는 것입니다.

🚧 3. 두 번째 발견: '차이'를 구별하는 능력 (Erdős 의 문제)

두 번째 문제는 조금 더 까다롭습니다. '시돈 집합'은 '더하기'에 초점을 맞췄다면, 이번에는 '빼기 (차이)' 에 초점을 맞춥니다.

• (4, 5) 집합: 숫자 4 개를 아무렇게나 골랐을 때, 그 4 개 숫자끼리 서로 뺀 값 (절대값) 이 최소 5 가지 이상의 서로 다른 숫자로 나와야 합니다.
  • 보통 숫자 4 개를 고르면 6 개의 차이가 나는데, 그중 5 개 이상이 다 달라야 한다는 뜻입니다. (완벽한 시돈 집합은 이 조건을 무조건 만족합니다.)
• 질문: "이런 '차이 구별' 능력을 가진 숫자 덩어리에서, 완벽한 '더하기 규칙 (시돈 집합)'을 따르는 숫자들을 얼마나 골라낼 수 있을까?"
• 과거의 연구: 예전에는 "최소 50% 보다 조금 더, 최대 60% 정도"일 거라고 추측했습니다.
• 이 논문의 개선:
  • 하한 (최소 보장): "최소 약 53% (9/17) 는 반드시 찾을 수 있다." (이전보다 더 많은 숫자를 보장하게 됨)
  • 상한 (최대 한계): "어떤 경우에는 약 57% (4/7) 를 넘을 수 없다." (14 개의 숫자로 구성된 구체적인 예시를 만들어 증명)

🏗️ 4. 어떻게 이걸 증명했을까? (비유로 보는 증명 방법)

저자들은 이 문제를 해결하기 위해 '3 차원 구조물' 을 빌려왔습니다.

1. 숫자를 구조물로 변환: 숫자 덩어리를 보고, "어떤 3 개의 숫자가 나란히 있으면 (등차수열), 그걸 연결해서 벽돌 (하이퍼그래프) 을 쌓는다"고 상상합니다.
2. 벽돌 제거하기: 완벽한 시돈 집합을 찾으려면, 이 벽돌들이 쌓인 구조물에서 '어떤 3 개의 벽돌도 연결되지 않도록' 숫자를 골라야 합니다. (이를 수학적으로 '독립집합'이라고 합니다.)
3. 최적의 제거 전략: "이 구조물에서 벽돌을 얼마나 최소한으로 제거하면 나머지 숫자들이 안전하게 지킬 수 있을까?"를 계산했습니다.
   • 첫 번째 문제 (약한 시돈) 에서는 아주 간단한 규칙으로 절반을 보장했습니다.
   • 두 번째 문제 ((4, 5) 집합) 에서는 더 복잡한 구조물 (특정 모양의 벽돌이 없는 구조) 을 분석하여, 이전보다 더 정교하게 절반보다 조금 더 많은 숫자를 보장할 수 있음을 보였습니다.

🌟 5. 요약: 왜 이 논문이 중요할까?

이 논문은 수학자들이 수십 년간 풀지 못했던 두 가지 난제를 완벽하게 해결했습니다.

1. "약한 규칙" 숫자 덩어리에서 완벽한 규칙 숫자를 얼마나 찾을 수 있는가?
   • 정답: 정확히 절반 (50%) 입니다. (그리고 그 비율이 정확히 1/2 로 수렴한다는 것도 증명했습니다.)
2. "차이 구별" 숫자 덩어리에서 완벽한 규칙 숫자를 얼마나 찾을 수 있는가?
   • 정답: 최소 약 53% 에서 최대 약 57% 사이입니다. (기존의 모호한 추측을 훨씬 더 좁은 범위로 정확히 잡았습니다.)

한 줄 요약:

"숫자 놀이에서 규칙이 조금 느슨하더라도, 그 안에서 완벽한 규칙을 가진 숫자들을 적어도 절반 이상은 반드시 찾아낼 수 있으며, 그 한계는 약 50%~57% 사이임을 수학적으로 완벽하게 증명했다."

이 연구는 단순히 숫자 놀이를 넘어, 복잡한 시스템 안에서 '질서 (규칙)'를 찾아내는 능력의 한계를 이해하는 데 중요한 통찰을 줍니다.

기술 요약

1. 연구 배경 및 문제 정의

이 논문은 가법 조합론 (additive combinatorics) 의 핵심 개념인 Sidon 집합과 관련된 두 가지 주요 문제를 해결합니다.

• Sidon 집합: 집합 $S$의 모든 쌍 $x, y \in S$ ($x \le y$) 에 대해 합 $x+y$가 모두 서로 다른 집합.
• 약한 Sidon 집합 (Weak Sidon set): 집합 $S$의 모든 쌍 $x, y \in S$ ($x < y$) 에 대해 합 $x+y$가 모두 서로 다른 집합. (즉, $x+x$ 형태의 합은 중복될 수 있음).
• (4, 5)-set: 집합 $A$의 임의의 4 개의 서로 다른 원소로 구성된 부분집합이 6 개의 쌍별 절댓값 차이 중 적어도 5 개의 서로 다른 값을 갖는 집합.

논문은 다음과 같은 두 가지 주요 문제를 다룹니다.

문제 1: Sárközy 와 Sós 의 문제 (약한 Sidon 집합)

• 정의: $g(n)$을 크기 $n$인 모든 약한 Sidon 집합 $A$에 대해 포함할 수 있는 최대 Sidon 부분집합의 크기 $h(A)$의 최솟값으로 정의합니다.
  $$g(n) := \min \{ h(A) : A \subset \mathbb{R}, |A|=n, A \text{ is a weak Sidon set} \}$$
• 질문: 극한 $\lim_{n \to \infty} \frac{g(n)}{n}$이 존재하는가? 만약 그렇다면 그 값은 무엇인가?

문제 2: Erdős 의 문제 ((4, 5)-set)

• 정의: $f(n)$을 크기 $n$인 모든 (4, 5)-set $A$에 대해 포함할 수 있는 최대 Sidon 부분집합의 크기 $h(A)$의 최솟값으로 정의합니다.
  $$f(n) := \min \{ h(A) : A \subset \mathbb{R}, |A|=n, A \text{ is a (4, 5)-set} \}$$
• 질문: 모든 (4, 5)-set $A$가 크기 $c^* n$ 이상의 Sidon 부분집합을 포함하도록 하는 최적의 상수 $c^*$는 무엇인가? (즉, $c^* = \lim_{n \to \infty} \frac{f(n)}{n}$).

---

2. 주요 방법론 및 전략

저자들은 두 문제 모두에 대해 **점근적 상수 (asymptotic constant)**의 존재성을 증명하고 정확한 값을 규명하기 위해 다음과 같은 방법론을 사용했습니다.

가. 하위 가법성 (Subadditivity) 과 Fekete 의 보조정리

• $g(n)$과 $f(n)$이 **하위 가법적 (subadditive)**임을 증명했습니다. 즉, $g(m+n) \le g(m) + g(n)$과 $f(m+n) \le f(m) + f(n)$이 성립합니다.
• 이를 위해 두 개의 집합을 서로 충분히 멀리 떨어진 스케일 (scale) 로 변환하여 합집합을 구성하는 기법을 사용했습니다.
  • 약한 Sidon 집합: $C = A \cup (qB + t)$ 형태로 구성하여, 혼합된 합 (mixed sums) 이 기존 합과 충돌하지 않도록 $q$와 $t$를 선택했습니다.
  • (4, 5)-set: 유사하게 혼합된 차이 (mixed differences) 가 기존 차이와 충돌하지 않도록 구성했습니다.
• Fekete 의 보조정리를 적용하여 극한 $\lim_{n \to \infty} \frac{g(n)}{n}$과 $\lim_{n \to \infty} \frac{f(n)}{n}$의 존재성을 증명했습니다.

나. A.P.-하이퍼그래프 (A.P.-hypergraph) 프레임워크

• 집합 $A$에 대한 A.P.-하이퍼그래프 $H(A)$를 정의했습니다. 정점은 $A$의 원소이며, 에지는 $A$ 내의 3 항등차수열 (3-term arithmetic progression) 을 이룬 3 개의 원소 쌍입니다.
• 핵심 연결: $A$가 약한 Sidon 집합일 때, $A$의 Sidon 부분집합은 $H(A)$의 **독립 집합 (independent set)**과 정확히 일치합니다. 즉, $h(A) = \alpha(H(A))$입니다.
• 전달수 (Transversal number, $\tau(H)$) 활용: $\alpha(H) + \tau(H) = |V(H)|$이므로, Sidon 부분집합의 크기를 하한 (lower bound) 으로 추정하기 위해 전달수 $\tau(H)$의 상한을 구하는 문제로 변환했습니다.
• 구조적 제약:
  • (4, 5)-set 의 경우, $H(A)$는 **선형 (linear)**이며 $F_7$-free (특정 7-vertex 3-uniform 하이퍼그래프를 포함하지 않음) 임을 증명했습니다.
  • 약한 Sidon 집합의 경우, $H(A)$의 에지 수 $m_H$가 $n_H - 2$ 이하임을 증명했습니다.

다. 구성적 예시 (Explicit Constructions)

• 상한 (Upper Bound): 최적의 상수 $c^*$를 제한하기 위해 구체적인 집합을 구성했습니다.
  • $g(n)$의 상한을 위해 $A_{2n+1}$이라는 특수한 약한 Sidon 집합을 구성했습니다.
  • $c^*$의 상한을 위해 14 개의 원소로 이루어진 구체적인 (4, 5)-set ($A_{base}$) 을 컴퓨터 탐색을 통해 구성했습니다.

---

3. 주요 결과 및 기여

결과 1: Sárközy 와 Sós 의 문제 완전 해결

• 정리 1.3: 모든 $n \ge 1$에 대해 $g(n)$의 정확한 값을 구했습니다.
  $$g(n) = \left\lceil \frac{n+1}{2} \right\rceil$$
• 결과: 따라서 극한 $\gamma^* = \lim_{n \to \infty} \frac{g(n)}{n} = \frac{1}{2}$입니다.
• 의의: 약한 Sidon 집합은 Sidon 집합에 비해 조건이 느슨하지만, 여전히 그 내부에는 최소한 원소의 절반 정도 ($\approx n/2$) 를 Sidon 부분집합으로 가질 수 있음을 보였습니다.

결과 2: Erdős 의 문제 개선 (상수 $c^*$의 범위)

• 정리 1.5: 극한 $\lim_{n \to \infty} \frac{f(n)}{n}$이 존재하며, 이는 최적 상수 $c^*$와 일치함을 증명했습니다.
• 정리 1.6: 기존 Gyárfás 와 Lehel 의 결과 ($1/2 + \epsilon \le c^* \le 3/5$) 를 개선하여 다음과 같은 새로운 범위를 제시했습니다.
  $$\frac{9}{17} \le c^* \le \frac{4}{7}$$
  • **상한 ($4/7$):** 14 점 (4, 5)-set$A_{base}$를 구성하여, 이 집합의 최대 Sidon 부분집합 크기가 8 임을 확인했습니다. ($8/14 = 4/7$).
  • **하한 ($9/17$):** Henning 과 Yeo 의 3-uniform 선형$F_7$-free 하이퍼그래프에 대한 전달수 부등식 ($17\tau(H) \le 5n_H + 3m_H$) 을 활용하여 개선된 하한을 유도했습니다.

---

4. 의의 및 결론

1. 문제 해결의 완결성: Sárközy 와 Sós 가 제기한 약한 Sidon 집합 내 Sidon 부분집합의 크기 문제에 대해, 극한의 존재성뿐만 아니라 정확한 점근적 상수 ($1/2$) 와 유한$n$에 대한 정확한 식을 제시하여 문제를 완전히 해결했습니다.
2. Erdős 문제의 진전: (4, 5)-set 에 관한 Erdős 의 오랜 난제에 대해, 기존에 알려진 상하한을 모두 개선했습니다. 특히 AI 를 활용하여 구체적인 반례 (상한을 결정하는 집합) 를 찾았다는 점이 주목할 만합니다.
3. 방법론적 기여:
   • 집합론적 조건을 하이퍼그래프 이론 (A.P.-hypergraph) 으로 변환하여 분석하는 프레임워크를 정교화했습니다.
   • 하위 가법성 (subadditivity) 을 통해 극한의 존재성을 증명하는 표준적인 접근법을 두 가지 다른 문제 설정에 성공적으로 적용했습니다.
   • AI 도구를 활용한 구체적인 수치 예시 (14 점 집합) 탐색이 이론적 상한을 개선하는 데 결정적인 역할을 했음을 보여주었습니다.

이 논문은 가법 조합론과 극단적 조합론 (extremal combinatorics) 의 교차점에서 중요한 진전을 이루었으며, Sidon 집합과 그 변형 집합들의 구조적 성질에 대한 이해를 심화시켰습니다.