Brik's sequence: a strange recursion

기술적 요약: 브릭의 수열: 기이한 재귀

문제 제기
본 논문은 2018 년 가로 브릭 (Garo Brik) 이 제안한 특정 재귀적 반복에 의해 생성된 이진 단어 $(B_i)_{i \ge 1}$의 수열과 그 결과인 무한 이진 수열 $b$의 성질을 조사한다. 이 수열은 기본 사례 $B_1 = 101$과 $i \ge 1$에 대한 재귀 관계식 $B_{i+1} = B_i C_i$로 정의되며, 여기서 $C_i$는 $B_i$의 첫 $i$개의 기호를 제거하여 얻은 $B_i$의 접미사이다. 모든 $i \ge 2$에 대해 $B_{i-1}$이 $B_i$의 접두사이므로, 이러한 단어들은 유일한 무한 수열 $b$로 수렴한다. 본 논문은 $b$의 재귀성, 인자 복잡도 (factor complexity), 형태적 성질 (morphic nature), 그리고 기호 '1'의 밀도를 포함하여 $b$의 조합론적 및 산술적 성질을 규명하고자 한다.

방법론
분석은 귀납적 증명, 단어 인자에 대한 조합론적 논증, 그리고 해석적 정수론 기법의 결합을 활용한다.

• 구조 분석: 저자들은 자명한 귀납법을 통해 단어 $B_i$의 길이와 그 접미사 성질을 확립한다. 그들은 "경계 (borders)" (접두사이면서 동시에 접미사인 것) 의 개념을 활용하여 특정 인덱스가 "양호 (good)"함을 증명하는데, 이는 $B_i$가 $B_{\ell_i}$의 경계임을 의미한다.
• 재귀성과 복잡도: 본 논문은 재귀적 성질을 결정하기 위해 $b$ 내에서의 인자 발생을 분석한다. 금지된 부분 문자열을 식별함으로써 모든 유효 인자의 집합을 규명한다.
• 성장 분석: 특정 패턴 (특히 $1$들의 연속) 의 시작 위치는 재귀 관계를 사용하여 추적되며, 성장률은 커스 (Knuth) 의 테트레이션 표기법을 사용하여 분석된다.
• 밀도 계산: $1$들의 밀도는 길이$\ell_n = |B_n|$인 접두사 내의$1$의 개수를 분석함으로써 유도된다. 저자들은 수열 자체의 이진 전개와 관련된 극한 공식을 유도하고, 오차항 분석 ($E(N)$) 을 사용하여 극한을 특정 접두사에서 임의의 접두사로 확장한다.
• 초월성 증명: 밀도 극한 $\alpha$의 성질을 결정하기 위해, 본 논문은 수열의 반복 구조와 그 이진 전개로 형성된 수의 초월성 사이의 관계를 다루는 아담체프스키 (Adamczewski) 와 뷔고 (Bugeaud) 의 "더듬거림 (stammering)" 기준의 단순화된 버전을 적용한다.

주요 기여 및 결과

1. 재귀적 성질:

   • 무한 단어 $b$는 재귀적임 (모든 유한 인자가 무한히 자주 등장함) 이지만 균일 재귀적이지는 않음이 증명된다.
   • 본 논문은 $b$가 임의로 긴 $1$들의 연속 ($모든 n$에 대한$1^n$) 을 포함함을 보여주는데, 이는 균일 재귀성을 배제한다.$1^n$의 첫 번째 발생 위치$r_n$은$n \ge 2$에 대해$r_{n+1} = 2^{r_{n-2}} + r_n$이라는 재귀 관계를 따르며, 이는 극도로 빠른 성장 (테트레이션) 으로 이어진다.

2. 인자 복잡도:

   • $b$의 인자에 대한 완전한 규명이 제공된다: 이진 단어가 $b$의 인자일 필요충분조건은 두 개의 연속된 $0$을 포함하지 않는 것이다.
   • 결과적으로, 길이 $n$인 서로 다른 인자의 개수는 정확히 $F_{n+2}$ ( $(n+2)$ 번째 피보나치 수) 이다. 이는 $b$가 지수적 인자 복잡도를 가짐을 확립한다.

3. 비형태적 성질:

   • 지수적 인자 복잡도에 기반하여, 본 논문은 $b$가 형태적 (morphic) 이 아님을 결론짓는다. 이는 에렌푸히트 (Ehrenfeucht), 리 (Lee), 로젠버그 (Rozenberg) 의 결과에 따른 것으로, 형태적 수열은 다항식 인자 복잡도 (특히 $O(n^2)$) 를 가져야 함을 명시한다.

4. 1 의 밀도:

   • 본 논문은 $b$ 내의 $1$들의 점근적 밀도$\alpha = \lim_{n \to \infty} \frac{a(n)}{n}$가 존재함을 증명한다.
   • 그 값은 $\alpha = 2 - 2\sum_{i \ge 1} b_i 2^{-i}$라는 공식으로 주어지며, 여기서 $b_i$는 수열의 $i$번째 비트이다.
   • 수치적 값은 약 $0.64505878493452$이다.

5. 초월성:

   • 밀도 $\alpha$는 초월수임이 증명된다. 증명은 더듬거림 기준을 사용하여 연관된 수 $\beta = \sum b_i 2^{-i}$가 초월수임을 보이는 데 의존한다. $\beta$는 유한한 인자 복잡도를 의미할 수 없으므로 유리수가 될 수 없으며, 수열이 필요한 "더듬거림" 구조 ($B_{n+1}$은 $B_n$을 포함하고 그 뒤에 접미사의 반복이 따름) 를 보이므로, $\beta$ (따라서 $\alpha$) 는 초월수여야 한다.

의의 및 주장
본 논문은 단순한 반복 규칙으로 정의되었음에도 불구하고 즉시 명확하지 않은 미묘하고 복잡한 성질을 보이는 수열을 제시한다. 주요 의의는 균일 재귀적이지는 않지만 재귀적인 수열, 지수적 인자 복잡도를 갖는 수열, 그리고 초월적인 $1$의 밀도를 생성하는 수열의 발견에 있다. 저자들은 해당 수열이 OEIS 에 등장함 (초기 항을 제외한 A334820) 을 언급하며, 재귀적 정의와 결과적인 산술적 성질 간의 상호작용을 강조한다.

본 논문은 명시적으로 이러한 결과들이 2026 년 5 월 APL 을 통한 실험과 ChatGPT 5.5 와의 협업을 통해 얻어졌으며, 모든 주장은 이후 저자에 의해 재작성되고 검증되었음을 인정한다. 이 작업은 재귀적으로 정의된 이진 단어의 성질과 조합론적 수열에 대한 초월성 기준의 적용에 관한 사례 연구로 기능한다.