정수론 #10-2 :: 디오판토스 근사

10진법 전개에 의한 √2의 유리수 근사:

 

$\begin{gather*} 1.4, \ \ 1.41, \ \ 1.414, \ \ 1.4142, \ \ ... \end{gather*}$

 

유리수열 {r_n}에 대해 다음 부등식이 성립한다.

 

$\begin{gather*} |\sqrt2 -r_n| < \frac{1}{10^n} \end{gather*}$

 

이것은 수렴속도가 느리다.

 

펠 방정식 x_k^2 - 2y_k^2 = 1 의 해 x_k + y_k√2 = (3 + 2√2)^k에 대하여,

 

$\begin{gather*} (\frac{x_k}{y_k})^2-2=\frac{1}{y_k^2} \end{gather*}$

 

이므로

 

$\begin{gather*} \frac{|\sqrt2-\frac{x_k}{y_k}|}{\frac{1}{y_k}}=y_k\cdot \frac{|2-(\frac{x_k}{y_k})^2|}{\sqrt2 +\frac{x_k}{y_k}} \\ = \frac{1}{y_k} \cdot \frac{1}{\sqrt2 + \frac{x_k}{y_k}}=\frac{1}{\sqrt2y_k+x_k} \\ = \frac{1}{(3+2\sqrt2)^k} \ll \frac{1}{y_k} \end{gather*}$

 

펠 방정식의 해로 얻은 수열은 √2에 대한 좋은 유리수 근사 x_k/y_k를 준다.

 

$\begin{gather*} 3/2 = 1/5, \ \ 17/12 = 1.416..., \ \ 99/70 =1.41428..., \ \ 577/408 = 1.4142156..., \end{gather*}$

 

이것은 수렴속도가 빠르다. ⇒ 무리수를 유리수로 근사하는 '좋은' 방법.

 

---

 

디오판토스 근사 정리

D가 제곱수가 아니면 √D는 무리수

⇒ 임의의 자연수 B에 대하여 다음 부등식이 성립하는 자연수 쌍 (p, q)가 무한히 존재한다.

 

$\begin{gather*} |p-q\sqrt D|<\frac{1}{B}\le\frac{1}{q}, \ \ \ \ a\leq B \end{gather*}$

 

즉, √D 에 대한 좋은 유리수 근사가 존재.

 

변형

 

$\begin{gather*} |p-q\sqrt D|<\frac{1}{q} \\ \Rightarrow |\frac{p}{q}-\sqrt D| <\frac{1}{q^2} \end{gather*}$

 

 

참고

 

1. 제곱수가 아닌 D에 대하여 √D는 무리수이다.

    "√D를 유리수라고 가정하면 D는 제곱수이다."의 대우

2. D=2인 경우에 펠 방정식 p_k+q_k√2 = (3+2√2)^k의 해 (p_k, q_k)가 이런 부등식을 만족한다.

3. 유리수 A/B에 대하여 p/q ≠ A/B라면 ||p - qA/B|| = ||(pB-qA)/B|| ≥ 1/B.

    즉, 유리수의 경우엔 좋은 유리수 근사 방법이 존재하지 않는다.

 

---

 

증명

For each k ≥ 0, write k√D = N_k + f_k, where N_k ∈ N and 0 ≤ f_k < 1.

Given any B, consider the B intervals.

 

$\begin{gather*} [0, \frac{1}{B}), \ \ [\frac{1}{B}, \frac{2}{B}), \ \ ..., \ \ [\frac{B-1}{B}, \frac{B}{B}=1). \end{gather*}$

 

k√D는 정수부 N과 소수부 f로 나눌 수 있다.

그렇다면 임의의 자연수 B로 f에 대한 구간을 나눌 수 있다.

⇒ 한 구간의 크기를 1/B로 하여 총 B개의 구간으로 나눈다.

 

By the pigeonhole principle, there is an interval which contains at least two decimals f_k and f_l with 0 ≤ k < l ≤ B.

(Note: B+1 integers 0, 1, ..., B.)

Therefore,

 

$\begin{gather*} \frac{1}{B} > |f_k-k_l| \\ = |(k\sqrt{D}-N_k)-(l\sqrt{D} -N_l)| = |(N_l-N_k)-(l-k)\sqrt{D}| \end{gather*}$

 

pigeonhole principle 비둘기집 원리 
100개의 집에 비둘기 101마리가 들어가야 한다면 적어도 하나 이상의 집에는 두마리가 들어가야 한다.

 

0√D부터 B√D 까지 총 B+1개의 f가 존재한다. 하지만 나누어진 구간은 총 B개이므로 비둘기집 원리에 의하여 한 구간안에 적어도 2개 이상의 f가 들어가야 한다. 즉, 어떤 구간 1/B범위 내에 f_k와 f_l이 같이 존재한다.

⇒ 1/B 범위 내로 그러한 좋은 유리수 근사가 존재한다.

 

Let p = N_l - N_k and q = l - k, Then

 

$\begin{gather*} |p-q\sqrt{D}| < \frac{1}{B} \ \ with \ \ q \leq B. \\ \Rightarrow \frac{1}{q} \geq \frac{1}{B} \\ \Rightarrow |p-q\sqrt{D}| < \frac{1}{B} \leq \frac{1}{q} \end{gather*}$

 

이러한 좋은 유리수 근사를 만족하는 p, q가 존재한다.

 

ex) √2

 

$\begin{gather*} |x_k-y_k\sqrt2| < \frac{1}{B} \leq \frac{1}{y_k} \end{gather*}$

 

만약 유리수에 적용한다면? (D가 제곱수라면)
⇒ 소수부 f는 항상 0이다. ⇒ 0 < 1/B
이것은 자기자신을 사용한 근사이기 때문에 당연하다.
따라서 유리수에선 자기자신을 사용하지 않는다면 위와 같은 좋은 유리수 근사는 존재하지 않는다.

 

---

 

p, q가 무한히 존재?

펠 방정식 때처럼 infinite descent가 가능해서 1/B내에서 무한히 많은 쌍을 얻을 수 있다.

Diophantine approximation -strong version : 양의 무리수 α와 임의의 양의 정수 B에 대하여 다음 부등식이 성립하는 자연수 쌍(p, q)가 무한히 존재한다.

 

$\begin{gather*} |p-qα| \frac{1}{B} \ \ with \ \ q \leq B. \end{gather*}$

 

증명

앞서 weak version 증명에선 √D가 무리수라는 성질만 이용했다. 이때 √D대신 임의의 양의 무리수 α를 사용하여 일반화할 수 있다.

 

1. 부등식 |p_1 - q_1α| < 1/B이 성립하는 (p_1, q_1)을 찾는다.

2. 1\B' < |p_1 - q_1α|이 되도록 큰 정수 B'을 잡는다.

3. |p_2 - q_2α| < 1/B'이 성립하는 (p_2, q_2)를 찾는다.

    ⇒ (p_2, q_2) ≠ (p_1, q_1).

 

$\begin{gather*} ...< \frac{1}{B^{\prime\prime}} < |p_2-q_2α| < \frac{1}{B^\prime} < |p_1 - q_1α| < \frac{1}{B} \end{gather*}$

 

이 과정을 무한히 반복할 수 있으므로 무한히 많은 쌍 (p, q)를 얻을 수 있다.