거의 골롬 수열 (Almost Golomb Sequences) 에 대한 기술적 요약

이 논문은 벤와 클로이트르 (Benoît Cloitre) 가 저술한 것으로, 정수 수열의 고전적인 문제인 **골롬 수열 (Golomb's sequence)**을 변형하여 새로운 수열 클래스인 **'거의 골롬 수열 (Almost Golomb Sequences)'**을 도입하고 분석합니다.

1. 문제 제기 및 배경

1.1 골롬 수열의 한계

골롬 수열 $G(n)$은 "정수 $n$이 정확히 $G(n)$번 등장하는" 유일한 비감소 양의 정수 수열로 정의됩니다. 이는 다음과 같은 전역적 자기 참조 규칙을 따릅니다.
$$G\left(\sum_{k=1}^{n} G(k)\right) = n$$
이 수열은 $\phi$ (황금비) 와 관련된 멱함수 ($n^{\phi-1}$) 로 부드럽게 성장하며, 어떤 $k \ge 2$에 대해서도 $k$-정규 (k-regular) 가 아닙니다.

1.2 새로운 접근: 유한 메모리 슬라이딩 윈도우

저자는 골롬 수열의 정의에서 '전체 누적 합 (full cumulative sum)'을 **고정된 크기 $r$의 슬라이딩 윈도우 (최근 $r$개의 항의 합)**로 대체하여 새로운 수열을 정의합니다. 이를 $r$차 거의 골롬 수열 $a_r(n)$이라 합니다.
$$a_r\left(\sum_{i=0}^{r-1} a_r(n-i)\right) = n$$
이러한 '유한 메모리'의 도입은 수열의 본질을 완전히 변화시킵니다.

2. 주요 방법론

1. 구체적 공식 유도 (Explicit Denesting): $r=2, 3, 4, 5$에 대해 수열을 $r$진법 (radix-$r$) 기반의 분할 정복 (divide-and-conquer) 공식으로 변환합니다.
2. 자동화 및 정규성 증명 (Automata & Regularity): 수열의 차분 시퀀스 $d(n) = a(n+1) - a(n)$이 유한 상태 오토마타 (DFAO) 로 생성됨을 증명하여 수열이 $r$-정규 (r-regular) 임을 보입니다.
3. Walnut 정리 증명기 활용: $r=4, 5$의 경우, 복잡한 재귀 관계를 Walnut 이라는 자동 증명 도구를 사용하여 검증하고, 이진 보정 시퀀스 (binary correction sequences) 의 자동성을 확인합니다.
4. 점근적 분석: 수열의 비율 $a(n)/n$이 수렴하지 않고 진동함을 보이기 위해 특정 부분수열 (pivotal subsequences) 을 추적합니다.

3. 주요 결과 및 기여

3.1 보편적 $r$-정규성 (Universal r-regularity)

• 결과: 모든 $r \ge 2$에 대해 거의 골롬 수열은 $r$-정규입니다.
• 의미: 골롬 수열이 $k$-정규가 아니었던 것과 대조적으로, 유한 메모리 규칙은 수열을 자동 수열 (automatic sequence) 의 영역으로 이동시킵니다. 이는 수열의 값이 $r$진법 표현에 따라 선형 재귀를 따름을 의미합니다.

3.2 명시적 분해 공식 (Explicit Denesting Formulas)

각 $r$에 대해 수열을 $r$진법 블록별로 분해하는 공식을 도출했습니다.

• $r=2$ (이진법):
  • $a(2n) = a(n) + a(n+1) - 1$
  • $a(2n+1) = a(n) + a(n+1)$
  • 이는 골롬 수열의 Mallows 재귀식과 유사한 중첩 재귀 (nested recurrence) 를 가집니다.
• $r=3$ (삼진법):
  • 기본 공식에 이진 보정 시퀀스 $\varepsilon(n)$이 추가됩니다.
  • $a(3n) = a(n-2) + a(n-1) + a(n) + 1 + \varepsilon(n-1)$ 등.
• $r=4, 5$:
  • 더 복잡한 보정 시퀀스들 ($\varepsilon_i$ 또는 쌍 $(\varepsilon, \eta)$) 이 필요하며, Walnut 을 통해 그 자동성이 증명되었습니다.

3.3 수렴하지 않는 비율 $a(n)/n$

골롬 수열이 $n^{\phi-1}$로 수렴하는 것과 달리, 거의 골롬 수열은 **선형 성장 ($a(n) \asymp n$)**을 보이지만 비율 $a(n)/n$은 수렴하지 않고 두 개의 유리수 극한 사이를 진동합니다.

• $r=2$: 극한값은 $3/4$와 $2/3$.
• $r=3$: 극한값은 $8/15$와 $5/8$.
• $r=4, 5$: 각각 다른 유리수 쌍 ($25/48, 10/21$ 등) 으로 진동합니다.
• 원인: 이는 수열 내 '실행 길이 (run length)'가 국소적 밀도에 따라 지연 피드백 메커니즘을 통해 조절되기 때문입니다.

3.3 조합론적 해석

• $r=2$: 값의 중복도 (multiplicity) 가 이진 표현의 두 번째 최상위 비트에 의해 결정되며, 이는 간단한 부울 셀룰러 오토마타 규칙으로 설명됩니다.
• $r=3$: 차분 시퀀스가 회문 (palindromic) 구조를 가지며, 이는 지연 피드백 시스템으로 해석됩니다.

3.4 골롬 메타 구조 (Golomb Meta-structure) 가설

가장 흥미로운 발견 중 하나는 골롬 수열 자체가 거의 골롬 수열 가족을 지배한다는 것입니다.

• $M(r) = \sup_n N_r(n)$을 $r$차 수열에서 나타나는 최대 중복도라고 할 때, $M(r)$이 특정 값 $k$에 도달하는 최소 $r$의 값 $j_k$를 분석했습니다.
• 가설: $k \ge 4$에 대해 $j_{k+1} - j_k = G(k)$ (골롬 수열) 이 성립합니다.
• 즉, 유한 메모리로 잘라낸 수열들이 만들어낸 가족의 구조적 한계 (최대 중복도) 를 원래의 골롬 수열이 결정한다는 놀라운 역설을 제시합니다.

4. 의의 및 결론

이 논문은 다음과 같은 점에서 중요한 의의를 가집니다:

1. 수열 이론의 확장: 자기 참조 수열의 클래스를 유한 메모리 규칙으로 확장하여, 무한 메모리 (골롬) 와 유한 메모리 (거의 골롬) 사이의 위상 전이를 명확히 했습니다.
2. 정규성과 자동성: 유한 메모리 규칙이 수열을 $r$-정규로 만든다는 것을 증명하여, 이러한 수열들이 계산 이론 (automata theory) 과 깊은 연관이 있음을 보였습니다.
3. 동역학적 통찰: 수열의 진동 행동이 국소적 규칙과 전역적 구조 사이의 상호작용에서 비롯됨을 조합론적 및 동역학적 관점에서 설명했습니다.
4. 새로운 가설 제시: 골롬 수열이 그 변형 수열들의 '메타 구조'를 지배한다는 가설은 수열 이론의 새로운 연구 방향을 제시합니다.

결론적으로, 이 연구는 골롬 수열의 단순한 변형이 아닌, 완전히 새로운 수학적 구조와 동역학적 성질을 가진 수열 가족을 발견하고 체계적으로 분석한 선구적인 작업입니다.