2025-11-10T03:15:48.044021

Balanced Fibonacci word rectangles, and beyond

Shallit, Vukusic

Following a recent paper of Anselmo et al., we consider $m \times n$ rectangular matrices formed from the Fibonacci word, and we show that their balance properties can be solved with a finite automaton. We also generalize the result to every Sturmian characteristic word corresponding to a quadratic irrational. Finally, we also examine the analogous question for the Tribonacci word.

academic

균형잡힌 피보나치 단어 직사각형, 그 이상

기본 정보

논문 ID: 2509.25994
제목: Balanced Fibonacci word rectangles, and beyond
저자: Jeffrey Shallit (University of Waterloo), Ingrid Vukusic (University of York)
분류: math.NT cs.DM cs.FL math.CO
발표 시간: 2025년 10월 15일 (ArXiv 프리프린트)
논문 링크: https://arxiv.org/abs/2509.25994

초록

본 논문은 Anselmo 등의 최신 연구를 기반으로 피보나치 단어로 형성된 $m \times n$ 직사각형 행렬을 고려하며, 이들의 균형 성질이 유한 자동기계로 해결될 수 있음을 증명합니다. 연구는 이차 무리수에 대응하는 모든 Sturmian 특성 단어로 결과를 일반화하고, Tribonacci 단어의 유사한 문제를 검토합니다.

연구 배경 및 동기

문제 정의

본 논문이 연구하는 핵심 문제는 단어 직사각형의 균형성입니다: 무한 수열 $(a_i)_{i≥0}$ 이 주어졌을 때, 무한 행렬 $A = (a_{k,\ell})_{k,\ell≥0}$ 을 구성합니다. 여기서 $a_{k,\ell} = a_{k+\ell}$ 입니다. $m \times n$ 부분행렬 $A(i,m,n)$ 에 대해, 모든 원소의 합은 다음과 같습니다: $T(i,m,n) := \sum_{k=0}^{m-1}\sum_{\ell=0}^{n-1} a_{i+k+\ell}$

균형성 문제는: 어떤 $(m,n)$ 쌍에 대해 모든 $T(i,m,n)$ 값이 최대 두 개의 서로 다른 값만을 가질까요?

연구 동기

이론적 중요성: 피보나치 단어는 조합론의 고전적 대상이며, 그 균형 성질은 수론 및 자동기계 이론과 밀접한 관련이 있습니다
기존 한계: Anselmo 등은 $\max(m,n)$ 이 피보나치 수일 때 직사각형이 균형잡혀 있음을 증명했지만, 완전한 특성화는 여전히 부족합니다
방법론적 혁신: 유한 자동기계를 사용하여 이러한 문제를 해결하는 것은 새로운 계산 도구를 제공합니다

핵심 기여

완전한 특성화: 피보나치 단어 직사각형 균형성의 완전한 자동기계 특성화 제공 (정리 2 및 추론 3)
일반화된 결과: 모든 이차 무리수에 대응하는 Sturmian 단어로 결과 확장 (정리 2)
알고리즘 구현: Walnut 소프트웨어 기반의 구체적인 구현 및 검증 제공
밀도 결과: 균형 쌍 $(m,n)$ 의 밀도 성질 증명 (명제 6)
Tribonacci 확장: Tribonacci 단어의 유사한 문제 연구 (정리 10)

방법론 상세 설명

작업 정의

무한 수열 $(a_i)_{i≥0}$ 이 주어졌을 때, Hankel 행렬을 구성합니다: $A(i,m,n) := \begin{pmatrix} a_i & a_{i+1} & \cdots & a_{i+n-1} \\ a_{i+1} & a_{i+2} & \cdots & a_{i+n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{i+m-1} & a_{i+m} & \cdots & a_{i+m+n-2} \end{pmatrix}$

목표: 모든 $T(i,m,n)$ 값이 최대 두 개의 서로 다른 값을 가지도록 하는 $(m,n)$ 쌍을 결정합니다.

핵심 이론 프레임워크

Sturmian 단어의 성질

Sturmian 단어에 대해, $\Delta(i,m,n) := T(i+1,m,n) - T(i,m,n)$ 을 정의하면: $\Delta(i,m,n) \in \{-1, 0, 1\}$

핵심 보조정리 1: $(m,n)$ 이 균형잡혀 있을 필요충분조건은 수열 $(\Delta(i,m,n))_{i≥0}$ 이 $1,0,0,\ldots,0,1$ 또는 $-1,0,0,\ldots,0,-1$ 형태의 블록을 포함하지 않는 것입니다.

자동기계 방법

이차 무리수 $\alpha$ 에 대해, 유한 자동기계 $M$ 이 존재하여, Ostrowski $\alpha$ -진법 표현의 $n$ 과 $x$ 를 입력받고, $x = \lfloor n\alpha \rfloor$ 일 때만 수락합니다.

주요 정리 2: 알고리즘이 존재하여, 이차 무리수 $\alpha \in (0,1)$ 이 주어졌을 때, 유한 자동기계를 구성할 수 있습니다. 이 자동기계는 Ostrowski $\alpha$ -진법 표현의 $(m,n)$ 쌍을 입력받고, $m \times n$ 블록이 균형잡혀 있을 때만 수락합니다.

기술적 혁신점

균형 판정 기준의 자동기계 구현: 보조정리 1의 조건을 1차 논리 공식으로 변환한 후 자동기계로 변환
Zeckendorf 표현 처리: 음수 문제를 교묘하게 처리하여 $T(i+1,m,n) - T(i,m,n) + 1 \in \{0,1,2\}$ 사용
Walnut 구현: 완전한 코드 구현 제공, 15개 상태의 자동기계 생성

실험 설정

도구 및 구현

Walnut 소프트웨어: 자동기계 구성 및 검증용 전문 도구
Zeckendorf 표현: 피보나치 수의 표준 표현 시스템
Tribonacci 표현: Tribonacci 단어 분석용

검증 방법

자동기계 구성: Walnut을 통한 bal 자동기계 생성 (15개 상태)
정리 검증: Anselmo 등의 결과를 특수한 경우로 검증
밀도 분석: 균형 쌍의 분포 성질 계산

실험 결과

피보나치 단어의 주요 결과

추론 3: 그림 1의 15개 상태 자동기계가 피보나치 단어 직사각형의 균형성 문제를 완전히 해결합니다.

추론 4: Anselmo 등의 정리 검증: $\max(m,n)$ 이 피보나치 수이면, $m \times n$ 행렬은 균형잡혀 있습니다.

구조적 성질

명제 5: $n ≥ 2$ 에 대해:

$(i,j)$ 가 균형잡혀 있을 필요충분조건은 $(i',j)$ 가 균형잡혀 있는 것입니다. 여기서 $F_{n+1} < i,i' < F_{n+2}$ 이고 $j ≥ F_{n-1}$ 입니다
$(F_{n+1}+i,j)$ 가 균형잡혀 있을 필요충분조건은 $(F_{n+2}-i,j)$ 가 균형잡혀 있는 것입니다