비티 수열

수학에서 비티 수열(Beatty sequence) 또는 동차 비티 수열(homogeneous Beatty sequence)은 1보다 큰 무리수의 양의 배수의 바닥 함수를 취하여 얻어지는 정수의 수열이다. 비티 수열은 1926년에 이 수열에 대해 저술한 새뮤얼 비티의 이름을 따서 명명되었다.

레일리 경의 이름을 딴 레일리 정리는 비티 수열에 속하지 않는 양의 정수로 구성된 비티 수열의 여집합이 다른 무리수에 의해 생성되는 비티 수열 자체임을 명시한다.

비티 수열은 슈투름 단어를 생성하는 데도 사용될 수 있다.

정의

1보다 큰 모든 무리수 $r$은 다음 비티 수열을 생성한다. $${ℬ}_r=\{\lfloor r\rfloor ,\lfloor 2r\rfloor ,\lfloor 3r\rfloor ,\dots \}$$ 두 무리수 $r$과 $s=r/(r-1)$은 자연스럽게 $1/r+1/s=1$ 방정식을 만족한다. 이들이 생성하는 두 비티 수열 ${ℬ}_r$과 ${ℬ}_s$는 상호 보완적인 비티 수열 쌍을 이룬다. 여기서 "상호 보완적"이란 모든 양의 정수가 이 두 수열 중 정확히 하나에 속한다는 의미이다.

예시

$r$이 황금비 $r=(1+\sqrt{5})/2\approx 1.618$일 때, $r$의 정수 배수 수열은 대략 다음과 같은 값을 갖는다.

1.618, 3.236, 4.854, 6.472, 8.090, 9.708, ...

이 숫자들을 정수로 내림하면 다음 수열 $(\lfloor nr\rfloor )$이 얻어지며, 이는 하위 위토프 수열로 알려져 있다.

1, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 24, 25, 27, 29, ... (OEIS의 수열 A000201).

이 경우, 상호 보완적인 비티 수열은 다음으로부터 생성된다. $$s=\frac{r}{r-1}=\frac{(1+\sqrt{5})/2}{(-1+\sqrt{5})/2}=\frac{3+\sqrt{5}}{2}\approx \mathrm{2.618.}$$ 그 정수 배수는 대략 다음과 같은 값을 갖는다.

2.618, 5.236, 7.854, 10.472, 13.090, 15.708, ...

이 값들을 정수로 내림하면 $(\lfloor ns\rfloor )$ 상위 위토프 수열이 생성된다.

2, 5, 7, 10, 13, 15, 18, 20, 23, 26, 28, 31, 34, 36, 39, 41, 44, 47, ... (OEIS의 수열 A001950).

모든 양의 정수는 이 두 수열 중 정확히 하나에 속한다. 이 수열들은 위토프의 게임에 대한 최적 전략을 정의하며, 위토프 배열의 정의에 사용된다.

또 다른 예로, 제곱근 2에 대해 $r=\sqrt{2}\approx 1.414$ 이고 $s=\sqrt{2}/(\sqrt{2}-1)=2+\sqrt{2}\approx 3.414$이다. 이 경우 수열은 다음과 같다.

1, 2, 4, 5, 7, 8, 9, 11, 12, 14, 15, 16, 18, 19, 21, 22, 24, ... (OEIS의 수열 A001951), 그리고

3, 6, 10, 13, 17, 20, 23, 27, 30, 34, 37, 40, 44, 47, 51, 54, 58, ... (OEIS의 수열 A001952).

$r=\pi \approx 3.142$ 및 $s=\pi /(\pi -1)\approx 1.467$ 의 경우 수열은 다음과 같다.

3, 6, 9, 12, 15, 18, 21, 25, 28, 31, 34, 37, 40, 43, 47, 50, 53, ... (OEIS의 수열 A022844), 그리고

1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 24, 26, ... (OEIS의 수열 A054386).

첫 번째 수열의 어떤 숫자도 두 번째 수열에는 없고 그 반대도 마찬가지다.

역사

비티 수열은 1926년 새뮤얼 비티가 The American Mathematical Monthly에 제기한 문제에서 이름을 얻었다. 하지만 그보다 훨씬 이전인 1894년, 레일리 경이 그의 저서 "소리의 이론" 2판에서 이러한 수열을 간략하게 언급했다.

레일리 정리

레일리 정리(또는 비티 정리)는 무리수 $r>1,$이 주어지면, 양의 정수 집합을 분할하는 $s>1$이 존재하여 비티 수열 ${ℬ}_r$과 ${ℬ}_s$가 모든 양의 정수가 두 수열 중 정확히 하나에 속하게 됨을 명시한다.

첫 번째 증명

$r>1,$이 주어졌을 때, $s=r/(r-1)$라고 하자. 우리는 모든 양의 정수가 두 수열 ${ℬ}_r$과 ${ℬ}_s$ 중 하나에만 속함을 보여야 한다. 우리는 양의 정수 j와 k에 대해 모든 분수 $j/r$과 $k/s$가 비내림차순으로 함께 나열될 때 차지하는 순서 위치를 고려하여 이를 수행할 것이다.

두 숫자 중 어떤 두 개도 같은 위치를 차지할 수 없음을 (단일 숫자로서) 확인하기 위해, 어떤 j와 k에 대해 $j/r=k/s$라고 가정하자. 그러면 $r/s$ = $j/k$는 유리수가 되지만, $r/s=r(1-1/r)=r-1,$은 유리수가 아니다. 따라서 어떤 두 숫자도 같은 위치를 차지하지 않는다.

어떤 $j/r$에 대해, $i/r\le j/r$인 양의 정수 $i$가 $j$개 있고, $k/s\le j/r$인 양의 정수 $k$가 $\lfloor js/r\rfloor$개 있으므로, 목록에서 $j/r$의 위치는 $j+\lfloor js/r\rfloor$이다. $1/r+1/s=1$ 방정식은 다음을 의미한다. $$j+\lfloor js/r\rfloor =j+\lfloor j(s-1)\rfloor =\lfloor js\rfloor .$$

마찬가지로, 목록에서 $k/s$의 위치는 $\lfloor kr\rfloor$이다.

결론: 모든 양의 정수(즉, 목록의 모든 위치)는 $\lfloor nr\rfloor$ 또는 $\lfloor ns\rfloor$의 형태이지만, 둘 다는 아니다. 역 진술도 참이다: p와 q가 모든 양의 정수가 위 목록에 정확히 한 번 나타나도록 하는 두 실수라면, p와 q는 무리수이고 그 역수의 합은 1이다.

두 번째 증명

충돌: 정리와 반대로, j > 0과 k, m과 같은 정수가 있다고 가정하자. $$j=\lfloor k\cdot r\rfloor =\lfloor m\cdot s\rfloor .$$ 이는 다음 부등식과 동등하다. $$j\le k\cdot r<j+1\text{ and }j\le m\cdot s<j+1.$$

0이 아닌 j에 대해, r과 s의 무리성은 등식과 양립할 수 없으므로, $$j<k\cdot r<j+1\text{ and }j<m\cdot s<j+1,$$ 이는 다음으로 이어진다. $$\frac{j}{r}<k<\frac{j+1}{r}\text{ and }\frac{j}{s}<m<\frac{j+1}{s}.$$

이들을 모두 더하고 가설을 사용하면 다음을 얻는다. $$j<k+m<j+1$$ 이는 불가능하다 (두 인접한 정수 사이에 정수가 있을 수 없다). 따라서 가설은 거짓이어야 한다.

비충돌: 정리와 반대로, j > 0과 k, m과 같은 정수가 있다고 가정하자. $$k\cdot r<j\text{ and }j+1\le (k+1)\cdot r\text{ and }m\cdot s<j\text{ and }j+1\le (m+1)\cdot s.$$

j + 1이 0이 아니고 r과 s는 무리수이므로, 등식은 제외할 수 있으므로, $$k\cdot r<j\text{ and }j+1<(k+1)\cdot r\text{ and }m\cdot s<j\text{ and }j+1<(m+1)\cdot s.$$

그러면 다음을 얻는다. $$k<\frac{j}{r}\text{ and }\frac{j+1}{r}<k+1\text{ and }m<\frac{j}{s}\text{ and }\frac{j+1}{s}<m+1$$

해당하는 부등식을 더하면 다음을 얻는다. $$k+m<j\text{ and }j+1<k+m+2$$ $$k+m<j<k+m+1$$

이 또한 불가능하다. 따라서 가설은 거짓이다.

특성

숫자 $m$이 비티 수열 ${ℬ}_r$에 속하는 것은 다음 조건이 성립할 때만이다. $$1-\frac{1}{r}<{\left[\frac{m}{r}\right]}_1$$ 여기서 $[x{]}_1$는 $x$의 소수 부분을 나타낸다. 즉, $[x{]}_1=x-\lfloor x\rfloor$이다.

증명: $m\in B_r$ $\iff \mathrm{\exists }n,m=\lfloor nr\rfloor$ $\iff m<nr<m+1$ $\iff \frac{m}{r}<n<\frac{m}{r}+\frac{1}{r}$ $\iff n-\frac{1}{r}<\frac{m}{r}<n$ $\iff 1-\frac{1}{r}<{\left[\frac{m}{r}\right]}_1$

더 나아가, $m=\lfloor (\lfloor \frac{m}{r}\rfloor +1)r\rfloor$이다.

증명: $m=\lfloor (\lfloor \frac{m}{r}\rfloor +1)r\rfloor$ $\iff m<(\lfloor \frac{m}{r}\rfloor +1)r<m+1$ $\iff \frac{m}{r}<\lfloor \frac{m}{r}\rfloor +1<\frac{m+1}{r}$ $\iff \lfloor \frac{m}{r}\rfloor +1-\frac{1}{r}<\frac{m}{r}<\lfloor \frac{m}{r}\rfloor +1$ $\iff 1-\frac{1}{r}<\frac{m}{r}-\lfloor \frac{m}{r}\rfloor ={\left[\frac{m}{r}\right]}_1$

슈투름 수열과의 관계

무리수 $r$과 관련된 비티 수열의 첫 번째 차분 $$\lfloor (n+1)r\rfloor -\lfloor nr\rfloor$$ 는 알파벳 $\{\lfloor r\rfloor ,\lfloor r\rfloor +1\}$에 대한 특성 슈투름 단어이다.

일반화

약간 수정하면 레일리 정리는 양의 실수(반드시 무리수일 필요는 없음)와 음의 정수로도 일반화될 수 있다. 양의 실수 $r$과 $s$가 $1/r+1/s=1$을 만족하면, 수열 $(\lfloor mr\rfloor {)}_{m\in \mathbb{Z}}$과 $(\lceil ns\rceil -1{)}_{n\in \mathbb{Z}}$은 정수의 분할을 이룬다. 예를 들어, 피아노 건반의 흰색 건반과 검은색 건반은 $r=12/7$과 $s=12/5$에 대한 그러한 수열로 분포된다.

람베크–모저 정리는 레일리 정리를 일반화하며 정수 함수와 그 역함수로부터 정의된 더 일반적인 수열 쌍이 정수를 분할하는 동일한 특성을 가짐을 보여준다.

우스펜스키 정리는 ${\alpha }_1,\dots ,{\alpha }_n$이 $(\lfloor k{\alpha }_i\rfloor {)}_{k,i\ge 1}$에 모든 양의 정수가 정확히 한 번씩 포함되는 양의 실수라면 $n\le 2$임을 명시한다. 즉, 세 개 이상의 비티 수열에 대한 레일리 정리와 동등한 것은 없다.

더 읽을거리

• Holshouser, Arthur; Reiter, Harold (2001). 《A generalization of Beatty's Theorem》. 《Southwest Journal of Pure and Applied Mathematics》 2. 24–29쪽. 2014년 4월 19일에 원본 문서에서 보존된 문서. 
• Stolarsky, Kenneth (1976). 《Beatty sequences, continued fractions, and certain shift operators》. 《Canadian Mathematical Bulletin》 19. 473–482쪽. doi:10.4153/CMB-1976-071-6. MR 0444558.  많은 참고 자료를 포함한다.

외부 링크

• Weisstein, Eric Wolfgang. “Beatty Sequence” (영어). 《Wolfram MathWorld》. Wolfram Research. 
• 알렉산더 보고몰니, 비티 수열, Cut-the-knot