The Golden Sieve

이 논문은 자연수에 적용될 때 위토프 쌍을 생성하는 자기 참조적 삭제 과정인 '황금 체'를 재검토하고, 산술 수열에 대한 적용을 통해 Fokkink 와 Joshi 의 'hiccup' 수열 및 Fraenkel 의 보완 분할과 연결하며, 새로운 추출 체를 도입하여 산술 수열에 대한 작용을 명시적 아핀 변환으로 규명합니다.

핵심

1. 황금 체 (The Golden Sieve) 란 무엇일까요?

비유: 숫자 줄서기 게임

가상의 장면을 상상해 보세요. 1 부터 시작하는 모든 자연수 (1, 2, 3, 4, 5...) 가 줄을 서 있습니다. 이제 우리는 이 줄에서 숫자들을 하나씩 지워나가는 게임을 합니다.

• 규칙: "현재 줄의 n 번째에 있는 숫자를 보아라. 그 숫자가 가리키는 위치에 있는 숫자를 지워라."
  • 예를 들어, 1 번째 숫자는 '1'입니다. '1'이 가리키는 1 번째 숫자를 지웁니다. (1 이 사라짐)
  • 이제 줄은 (2, 3, 4, 5...) 가 됩니다. 2 번째 숫자는 '3'입니다. '3'이 가리키는 3 번째 숫자 (현재 줄에서 3 번째인 4) 를 지웁니다.
  • 이 과정을 무한히 반복합니다.

이 게임에서 **남아있는 숫자들 (생존자)**과 **지워진 숫자들 (삭제자)**은 놀라운 규칙성을 보입니다. 마치 황금비 (약 1.618...) 라는 신비로운 비율이 숨어있는 것처럼요.

2. 주요 발견들: 숫자들의 비밀

이 논문은 이 게임이 단순한 자연수뿐만 아니라, "2, 4, 6, 8..."처럼 일정한 간격으로 늘어난 숫자열 (등차수열) 에도 적용된다는 것을 발견했습니다.

① 생존자와 삭제자의 춤 (두 가지 간격)

숫자들을 지워나가면, 남은 숫자들 사이의 간격은 항상 두 가지 값만 가집니다.

• 비유: 생존자들이 줄을 서 있을 때, 서로의 거리가 항상 "1 걸음" 또는 "2 걸음"만 됩니다. 이걸로만 리듬을 타는 것입니다.
• 이 리듬은 마치 피보나치 수열이나 황금비와 같은 고전적인 수학 패턴을 따릅니다. 특히 자연수 (1, 2, 3...) 로 시작할 때는 '위토프 (Wythoff)'라는 유명한 게임의 규칙과 정확히 일치합니다.

② 자기 참조 (Self-Reference): "나를 보고 나를 결정해"

가장 재미있는 점은, "다음에 얼마나 걸을지 (간격)"를 결정할 때 스스로의 과거를 참고한다는 것입니다.

• 비유: "내가 지금 5 번째에 서 있는데, 내 이름표 (숫자 값) 가 5 라면, 다음엔 2 걸음을 걸어라. 아니면 1 걸음을 걸어라."
• 이 규칙은 마치 거울을 보고 자신을 결정하는 것과 같습니다. 논문의 저자는 이를 **"hiccup (hiccup, 'hic' 소리를 내는 것)"**이라고 부르며, 이 패턴이 수학적으로 매우 정교하게 작동함을 증명했습니다.

3. 새로운 도구: "은색 체 (Silver Sieve)"와 "추출 체 (Extraction Sieve)"

저자는 황금 체뿐만 아니라, 조금 다른 방식으로 숫자를 골라내는 **'추출 체'**라는 새로운 도구를 소개했습니다.

• 황금 체: 줄의 특정 위치를 보고 그 위치의 숫자를 지웁니다. (위치 중심)
• 추출 체: 줄의 **가장 앞쪽 (최소값)**을 뽑아 생존자로 만들고, 그 뒤에 따라오는 숫자들을 규칙에 따라 지웁니다. (가장 작은 숫자 중심)

이 '추출 체'는 **은색 체 (Silver Sieve)**라고도 불리는데, 이걸로 만들면 황금비가 아니라 **1 + √2 (약 2.414)**라는 다른 신비로운 비율이 나타납니다. 마치 황금 체가 '황금'을 만들어내듯, 은색 체는 '은' (또는 다른 금속) 같은 새로운 수학적 보석을 만들어냅니다.

4. 왜 이 연구가 중요할까요?

이 연구는 단순한 숫자 놀이를 넘어, 다음과 같은 깊은 의미를 가집니다:

1. 게임 이론과의 연결: 이 숫자 게임은 실제로 두 명이 하는 전략 게임 (Nim 게임 등) 의 승패를 결정하는 규칙과 같습니다. 어떤 숫자 조합이 이기는지 (P-position) 를 이 '체'를 통해 찾을 수 있습니다.
2. 예측 가능한 무작위성: 숫자를 지우는 과정은 복잡해 보이지만, 결국 매우 단순한 규칙 (두 가지 간격만 반복) 으로 정리됩니다. 이는 자연계의 복잡한 현상들이 단순한 법칙으로 설명될 수 있음을 시사합니다.
3. 새로운 수열의 발견: 이 방법을 통해 수학자들이 아직 잘 몰랐던 새로운 숫자 열들을 찾아내고, 그 패턴을 설명할 수 있게 되었습니다.

5. 결론: 숫자의 마법

이 논문은 **"숫자들을 줄 세우고, 규칙에 따라 지워내면, 그 속에 숨겨진 황금비나 은색비 같은 아름다운 패턴이 튀어나온다"**는 것을 보여줍니다.

마치 숫자들로 만든 모래성 (체) 을 빗질하듯 쓸어내면, 그 아래에서 황금빛 결정체 (수학적 법칙) 가 드러나는 것과 같습니다. 저자는 이 발견이 게임 이론, 암호학, 그리고 컴퓨터 과학 등 다양한 분야에서 새로운 통찰을 줄 것이라고 기대합니다.

한 줄 요약:

"숫자 줄에서 규칙대로 지우기만 해도, 황금비와 같은 신비로운 패턴이 자동으로 만들어지는 마법의 수학적 놀이입니다."

기술 요약

논문 요약: The Golden Sieve (황금 체)

저자: Benoit Cloitre (파리, 프랑스)
날짜: 2026 년 3 월
주제: 자기 참조적 삭제 과정을 통한 정수 수열의 생성, 히컥 (hiccup) 수열, 베어티 (Beatty) 분할, 그리고 게임 이론적 해석.

---

1. 문제 제기 및 배경

이 논문은 저자가 2002 년에 처음 소개한 황금 체 (Golden Sieve) 라는 자기 참조적 삭제 과정을 재조명합니다. 황금 체는 증가하는 양의 정수 수열 $W_0$에서 시작하여, 현재 수열의 $n$번째 원소를 '포인터'로 사용하여 해당 위치의 원소를 삭제하는 결정론적 과정입니다.

• 핵심 메커니즘: $n$단계에서 현재 수열 $W_{n-1}$의 $n$번째 원소 $h_n$을 읽습니다. 이 값 $h_n$을 위치 인덱스로 사용하여 $W_{n-1}$의 $h_n$번째 원소 $d_n$을 삭제합니다.
• 목표: 이 과정을 통해 생성되는 생존자 수열 (survivor sequence) 과 삭제된 수열 (deletion sequence) 의 구조를 규명하고, 특히 자연수 집합 $\mathbb{N}$과 산술 수열 $aN+b$에 적용했을 때의 수론적, 조합론적 성질을 분석하는 것입니다.

2. 방법론

논문은 다음과 같은 수학적 도구와 접근법을 사용합니다:

• 정규화 (Normalization): 산술 수열 $W_0 = aN+b$를 자연수 집합 $\mathbb{N}$으로 변환하여 분석을 단순화합니다.
• 순위 항등식 (Rank Identity): 생존자와 삭제된 수열 간의 아핀 (affine) 관계를 유도합니다.
• 히컥 수열 (Hiccup Sequences): Fokkink 와 Joshi 가 최근 연구한 자기 참조적 2 간격 (two-gap) 재귀 수열 이론을 적용합니다. 간격이 수열 자체의 값 집합에 대한 소속성 테스트에 의해 결정되는 구조를 분석합니다.
• 비교 분석: 기존에 알려진 '은색 체 (Silver Sieve, 추출 체)'와의 비교를 통해 다양한 자기 참조적 과정의 차이를 규명합니다.
• 연속 분수 및 점근적 분석: 수열의 점근적 기울기 (slope) 를 구하기 위해 고정점 정리와 연속 분수 이론을 활용합니다.

3. 주요 기여 및 결과

3.1 자연수 집합 ($W_0 = \mathbb{N}$) 에 대한 분석

• 위토프 쌍 (Wythoff Pair) 의 도출: 자연수에 황금 체를 적용하면, 생존자 수열과 삭제된 수열은 위토프 게임 (Wythoff's game) 의 P-위치 (이전 플레이어가 승리하는 위치) 를 구성하는 위토프 쌍과 일치함이 증명되었습니다.
• 황금 비율 ($\phi$): 생존자 수열은 $\lfloor n\phi \rfloor$ 형태의 베어티 수열 (Beatty sequence) 로, 간격은 1 또는 2 를 가집니다.
• 피보나치 수열의 불변성: 피보나치 수 $F_k$에 대한 생존자 값은 $F_{k+1}$이 되며, 피보나치 수열은 생존자 함수의 불변 부분집합을 이룹니다.
• 히컥 규칙: 삭제된 수열과 생존자 수열 모두 $(j, x, y, z)$-히컥 수열의 성질을 가지며, 간격 선택은 수열 자체의 값 집합에 대한 소속성 테스트에 의해 결정됩니다.

3.2 산술 수열 ($W_0 = aN+b$) 에 대한 일반화

• 포인터 - 생존자 항등식: $a \ge 2$인 경우, 포인터 $h_n$은 항상 생존자 수열의 $n$번째 원소 $s_n$과 일치함이 증명되었습니다. 이는 수열의 접두사가 초기 단계에서 안정화됨을 의미합니다.
• 2 간격 성질: 정규화된 생존자 간격은 항상 $\{1, 2\}$ 중 하나이며, 삭제된 수열의 간격은 $\{a+1, 2a+1\}$ 중 하나입니다.
• 순위 항등식 (Rank Identity): 생존자 $\sigma_n$과 삭제된 수열 $\delta_n$ (정규화됨) 사이에는 $\delta_n = a\sigma_n + n + (b-1)$이라는 아핀 관계가 성립합니다.
• 히컥 규칙의 적용: 생존자 수열은 명확한 히컥 규칙을 따르지만, 삭제된 수열의 간격 결정은 $W_0$ 내에서의 필터링된 자기 참조 테스트를 통해 이루어집니다.
• Fraenkel 의 보완 방정식: 이 분할은 Fraenkel 이 제안한 $NIM(a, 1)$ 게임의 P-위치와 일치하며, $a \ge 2$인 경우 베어티 수열로 표현될 수 없음을 보입니다.

3.3 추출 체 (Extraction Sieve) 와 은색 체

• 추출 체 정의: 기존 황금 체가 '위치'를 기반으로 삭제하는 반면, 추출 체는 현재 수열의 최소값을 생존자로 추출하고, 자기 참조 테스트에 따라 추가 최소값들을 삭제하는 새로운 체를 도입했습니다.
• 히컥 수열의 동적 실현: 추출 체는 자연수 $\mathbb{N}$에서 직접 히컥 수열을 생성하며, 산술 수열 $aN+b$에 적용 시 히컥 매개변수가 아핀 변환을 통해 변환됨을 보였습니다.
• 은색 체 (Silver Sieve): Bosma-Dekking-Steiner 수열 (OEIS A086377) 은 추출 체 $C_{1,3,2}$의 결과물임을 규명했습니다. 이 수열은 황금 체가 아닌 은색 체에서 비롯된 것으로, 황금 비율 대신 $1+\sqrt{2}$를 기울기로 가집니다.

3.4 제곱수 집합 ($W_0 = \{n^2\}$) 에 대한 분석

• 이차 중첩 (Quadratic Nesting): 제곱수에 황금 체를 적용하면, 간격 결정 규칙이 생존자 수열의 제곱 ($\mu_n^2$) 에 의존하는 더 복잡한 중첩 구조를 보입니다.
• 점근적 성장: 생존자 수열의 루트 인덱스 $\mu_n$은 $n + n^{1/2} - n^{1/4} + \dots$ 형태의 점근적 전개를 가집니다.

4. 의의 및 결론

• 수론적 통합: 황금 체는 단순한 삭제 규칙이 위토프 게임, Fraenkel 의 $NIM$ 게임, Kimberling 의 순위 변환 (Rank Transform) 등 다양한 수론적 및 게임 이론적 구조와 깊이 연결되어 있음을 보여줍니다.
• 히컥 수열의 체계화: 다양한 산술 수열과 추출 메커니즘을 통해 생성되는 히컥 수열들의 매개변수 변환 규칙을 체계화했습니다.
• 개방적 문제: $a \ge 2$인 경우 생성되는 이진 간격 단어 (binary gap word) 가 자동 수열 (automatic sequence) 인지, 혹은 그 조합론적 복잡도 (factor complexity) 는 무엇인지에 대한 미해결 문제를 제시했습니다. 특히 Walnut 이라는 자동 증명 도구를 활용한 분석의 필요성을 강조했습니다.

이 논문은 자기 참조적 수열 생성 과정에 대한 깊은 통찰을 제공하며, 단순한 알고리즘이 어떻게 복잡한 수론적 구조 (황금 비율, 피보나치 수열, 게임 이론적 균형) 를 만들어내는지를 명확히 규명했습니다.