페리 수열

1. 개요

페리 수열은 1802년 샤를 아로에 의해 처음 도입되었으며, 존 페리에 의해 재발견되어 널리 알려진 수열이다. 이 수열은 0과 1 사이의 모든 기약 분수를 분모의 크기 순으로 나열한 것으로, 수열의 길이는 오일러 피 함수를 사용하여 표현할 수 있다. 페리 수열의 인접한 항 사이에는 특정 관계가 성립하며, 연분수와 포드 원과도 밀접한 관련이 있다. 페리 수열은 무리수의 유리수 근삿값 계산, 물리 시스템의 공진 위치 계산, 경로 계획 연구 등 다양한 분야에 응용되며, 리만 가설과도 연관성을 갖는다.

2. 역사

페리 수열은 1802년 프랑스의 수학자 샤를 아로/Charles Haros^영어가 처음으로 도입하였다. 1816년 영국의 지질학자 존 페리 1세(John Farey, Sr.)가 페리 수열을 재발견하고, 이 수열의 성질에 대한 추측을 발표하면서 널리 알려지게 되었다. 페리의 추측은 오귀스탱 루이 코시에 의해 증명되었으며, 이후 페리 수열이라는 이름으로 불리게 되었다. 비록 페리가 최초 발견자는 아니지만, 그의 이름을 따서 명명된 것은 스티글러의 명명법칙의 한 예시로 볼 수 있다.

3. 성질

3.1. 수열의 길이

n번째 페리 수열 $F_n$의 길이는 오일러 피 함수(φ)를 이용하여 표현할 수 있다. $F_n$의 길이와 $F_{n+1}$의 길이 차이는 n+1보다 작으면서 n+1과 서로소인 자연수의 개수와 같다. 페리 수열의 길이에 관한 점화식은 다음과 같다.
* $|F_{n+1}| = |F_n| + \varphi(n+1)$
$|F_n|$은 계차가 $\varphi(n)$인 계차수열이고 $|F_1|=2$이기 때문에, 시그마 기호를 사용하여 $F_n$의 일반항을 나타낼 수 있다.
* $|F_n| = 1 + \sum_{m=1}^n \varphi(m)$
$F_n$의 점근적 행동은 다음과 같다.
* $|F_n| \sim \frac {3n^2}{\pi^2}$

3.2. 인접한 항

페리 수열 $F\_n$의 연속된 두 항을 $h\_1/k\_1$, $h\_2/k\_2$라고 하면, $k\_1h\_2\; -\; k\_2h\_1\; =\; 1$이 성립한다. 따라서 연속된 두 항의 차는 $\backslash frac\{h\_2\}\{k\_2\}-\backslash frac\{h\_1\}\{k\_1\}=\backslash frac\{1\}\{k\_1k\_2\}$ 와 같이 각 항의 분모를 곱한 값의 역수로 표현된다.

연속된 세 항 $h\_1/k\_1$, $h\_2/k\_2$, $h\_3/k\_3$에 대해서는, $\backslash frac\{h\_2\}\{k\_2\}=\backslash frac\{h\_1+h\_3\}\{k\_1+k\_3\}$가 성립한다. 이 두 성질은 서로를 함축한다.

한편, 인접한 두 항의 중항 $\backslash frac\{h\_1+h\_2\}\{k\_1+k\_2\}$의 분모 $k\_1+k\_2$는 항상 $n$보다 크다. 이 중앙값은 $k\_1+k\_2$번째 페리 수열 $F\_\{k\_1+k\_2\}$에 처음 등장하며, 항상 $\backslash left(\; \backslash frac\{h\_1\}\{k\_1\}\; ,\; \backslash frac\{h\_2\}\{k\_2\}\; \backslash right)$ 구간 사이에 존재한다.

만약 $\backslash frac\{a\}\{b\}$와 $\backslash frac\{c\}\{d\}$가 어떤 페리 수열에서 인접한다면, 이 두 분수 사이에 새로운 분수가 더해지는 것은 차수 $b+d$의 페리 수열에서이며, 이는 $\backslash frac\{a\}\{b\}$와$\backslash frac\{c\}\{d\}$의 중간수(Mediant (mathematics))인 $\backslash frac\{a+c\}\{b+d\}$이다. 예를 들어, $F\_5$에서는 인접한 $\backslash frac\{1\}\{3\}$과 $\backslash frac\{2\}\{5\}$ 사이에 나타나는 첫 번째 항은 $F\_8$의 $\backslash frac\{3\}\{8\}$이다.

페리 수열의 연속된 두 유리수 쌍은 면적이 1로 같다.

슈테른-브로코 나무(Stern–Brocot tree)는 0과 1에서 시작하여 연속적인 중항을 취하여 페리 수열이 구성되는 방식을 보여주는 데이터 구조이다.

3.3. 연분수

페리 수열에서 인접한 분수는 연분수 전개와 밀접한 관련이 있다. 모든 분수는 마지막 항이 1인 두 가지 연분수 전개를 가진다. 페리 수열에 처음 나타나는 분수의 연분수 전개를 통해, 이웃하는 분수의 연분수 전개를 구할 수 있다.

예를 들어, 3/8은 [0; 2, 1, 1, 1]과 [0; 2, 1, 2] 두 가지 연분수 전개를 가지며, F₈에서의 이웃은 2/5로 [0; 2, 1, 1]로 전개될 수 있고, 1/3은 [0; 2, 1]로 전개될 수 있다.

3.4. 포드 원

페리 수열은 포드 원과 관련이 있다.

모든 기약 분수 p/q에 대해, 반지름이 1/(2q²)이고 중심이 (p/q, 1/(2q²))인 포드 원 C[p/q]가 존재한다. 서로 다른 분수에 대한 두 포드 원은 서로소이거나 접하며, 교차하지 않는다. 0 < p/q < 1인 경우, C[p/q]에 접하는 포드 원은 페리 수열에서 p/q의 이웃인 분수에 대한 포드 원이다.

4. 예시

n=1…8까지의 페리 수열은 다음과 같다.

:F₁ = {0/1, 1/1}
:F₂ = {0/1, 1/2, 1/1}
:F₃ = {0/1, 1/3, 1/2, 2/3, 1/1}
:F₄ = {0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1}
:F₅ = {0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1}
:F₆ = {0/1, 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6, 1/1}
:F₇ = {0/1, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 2/5, 3/7, 1/2, 4/7, 3/5, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 1/1}
:F₈ = {0/1, 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8, 1/1}

5. 응용

페리 수열은 무리수의 유리수 근삿값을 찾는 데 매우 유용하다. 예를 들어, Eliahou는 3x+1 과정에서 비자명 사이클의 길이에 대한 하한을 구성할 때 페리 수열을 사용했다.

공진 현상이 있는 물리적 시스템에서 페리 수열은 1차원 및 2차원에서 공진 위치를 계산하는 효율적인 방법을 제공한다.

페리 수열은 사각형 격자에서 임의 각도 경로 계획 연구에서 계산 복잡성 또는 최적성을 특성화하는 데 사용된다.

비선형 역학에서 두 진동자가 비선형적인 영향을 서로 주고받을 때, 이들의 진동수가 특정한 유리수 비를 갖는 인입 현상이 발생할 수 있다. 이 때 유리수 비가 나타나는 순서는 슈테른-브로코 나무의 구성과 관련이 있다.

6. 리만 가설과의 관계

페리 수열은 리만 가설의 두 가지 동치 표현에 사용된다. 의 항을 $\backslash \{a\_\{k,n\}\; :\; k\; =\; 0,\; 1,\; \backslash ldots,\; m\_n\backslash \}.$이라고 하자. $d\_\{k,n\}\; =\; a\_\{k,n\}\; -\; \backslash tfrac\{k\}\{m\_n\}$으로 정의한다. 다시 말해 $d\_\{k,n\}$은 번째 페리 수열의 번째 항과 단위 구간에 균등하게 분포된 동일한 수의 점 집합의 번째 멤버 간의 차이이다. 1924년 제롬 프랑넬은 다음 명제가 리만 가설과 동치임을 증명했고, 이후 에드문트 란다우는 (프랑넬의 논문 직후) 다음 명제 또한 리만 가설과 동치임을 언급했다.

:$$\backslash sum\_\{k=1\}^\{m\_n\}\; d\_\{k,n\}^2\; =\; O\; (n^r)\; \backslash quad\; \backslash forall\; r\; >\; -1$$

:$$\backslash sum\_\{k=1\}^\{m\_n\}\; |d\_\{k,n\}|\; =\; O\; (n^r)\; \backslash quad\; \backslash forall\; r\; >\; \backslash frac\{1\}\{2\}$$