The greedy 3-sumfree sequence $S_{1,g,g+1}$

기술 요약: 그리디 3-sumfree 수열 $S_{1,g,g+1}$

문제 정의
본 논문은 양의 정수 $x, y, z$로 시작하는 증가하는 수열로서, 각 항이 이전의 서로 다른 세 항의 합으로 표현될 수 없는 가장 작은 (이전 항보다 큰) 정수로 정의되는 그리디 3-sumfree 수열 $S_{x,y,z}$의 특성을 규명한다. 구체적으로, 저자들은 모든 정수 $g \ge 2$에 대하여 $S_{1,g,g+1}$을 조사한다. Bosma 등 [1]은 자동 정리 증명기인 Walnut을 사용하여 특정 작은 사례($g=2, 3, 4$)에 대한 명시적인 설명을 이미 제시하였고 모든 $g \ge 2$에 대한 통일된 공식을 추측하였으나, 일반적인 증명은 미해결 상태로 남아 있었다.

방법론
저자들은 자동 정리 증명에 의존하는 대신 직접적인 구간-합집합(interval-sumset) 논증을 채택한다. 방법론은 다음과 같이 진행된다:

1. 후보 집합 ($A_g$)의 정의: 논문은 나머지 산술(modular arithmetic)을 기반으로 하는 특정 집합 $A_g$를 정의한다. $m = 10g + 3$, $e = 2g + 1$, $f = 6g + 1$이라 하자. 집합 $A_g$는 초기 항 $\{1, e, f\}$와 $k \ge 0$에 대해 정의된 주기적인 구간들의 합집합 $I_k$ 및 $J_k$로 구성된다:

   • $I_k = km + [g, 2g]$
   • $J_k = km + [6g + 2, 7g + 1]$
     집합 $A_g$는 이러한 서로소인 구성 요소들의 합집합으로 구축된다.

2. 두 가지 명제로의 축소: $S_{1,g,g+1} = A_g$임을 증명하는 과정은 "강제성(forced nature)"(정수가 집합의 서로 다른 세 원소의 합인 경우를 의미함)에 관한 두 가지 성질을 검증하는 것으로 축소된다:

   • 명제 2: $A_g$에 속하지 않는 모든 정수 $n > g + 1$은 강제된다 (즉, $A_g$의 세 서로 다른 원소의 합으로 쓰일 수 있다).
   • 명제 3: $A_g$ 내의 어떤 원소도 강제되지 않는다 (즉, $A_g$의 어떤 원소도 $A_g$의 서로 다른 세 원소의 합으로 쓰일 수 없다).

3. 구간 산술: 증명의 핵심은 정의된 구간들의 합집합(sumsets)을 계산하는 것이다. 구간의 합집합에 대한 기초적인 항등식(예: $b_3[u, v] = [3u+3, 3v-3]$)을 사용하여, 저자들은 $A_g$의 간극(gap)들이 $A_g$의 세 서로 다른 원소의 합에 의해 정확히 덮임을 보여주는 한편, $A_g$의 세 원소의 합은 항상 $A_g$의 여집합(구체적으로는 주기적인 여집합 패턴 $C$)에 속함을 입증한다.

4. 귀납적 검증: 저자들은 $n$에 대한 귀납법을 사용하여 그리디 규칙이 정확히 $A_g$의 원소들만을 허용함을 보여준다. 만약 $n \notin A_g$라면, $n$은 (귀납적 가설에 의해 수열에 포함된) $n$보다 작은 원소들에 의해 강제되므로 제외된다. 만 만약 $n \in A_g$라면, $n$은 $n$보다 작은 원소들에 의해 강제되지 않으므로 포함된다.

주요 결과
본 논문은 모든 $g \ge 2$에 대하여 수열 $S_{1,g,g+1}$을 정확하게 규명하는 정리 1을 확립한다:
정수 $z$가 $S_{1,g,g+1}$에 속할 필요충분조건은 다음과 같다:
$$z \in \{1, 2g + 1, 6g + 1\} \quad \text{또는} \quad z \pmod{10g + 3} \in [g, 2g] \cup [6g + 2, 7g + 1].$$

논문은 또한 수열의 구조를 상세히 설명한다:

• 초기 항: 수열은 $1, g, g+1, \dots, 2g, 2g+1, 6g+1$로 시작한다.
• 결과적 주기성: 첫 $g+4$개의 항 이후, 수열은 $m = 10g + 3$에 대해 주기성을 갖는다.
• 주기 구조: 반복되는 블록의 길이는 $2g + 1$이며, 다음과 같은 나머지들로 구성된다:
  $$6g + 2, 6g + 3, \dots, 7g + 1, g, g + 1, \dots, 2g.$$

의의 및 주장
본 논문은 Bosma, Bruin, Fokkink, Grube, Reuijl, Tromp [1]가 제기한 추측에 대한 직접적인 증명을 제공한다고 주장한다. 이 추측은 이전에 $2 \le g \le 10$ 범위에서 기계적으로 검증되었으나, 본 연구는 해석적인 방법을 통해 이를 모든 정수 $g \ge 2$로 확장하였다. 저자들은 자신들의 접근 방식이 이전 연구의 계산적 방법론과 대조되는, 구간-합집합 논증을 사용한 "직접적인 증명"을 제공한다고 명시적으로 밝힌다. 또한 본 논문은 전주기(preperiod)와 반복 블록을 모두 포함하여 수열의 구조를 완전히 해결하는 완전하고 명시적인 설명을 제공한다.