Farey sequence and approximation of irrational numbers I

Algebra, Analysis, Combinatorics, Diophantine approximation, Number theory, ProofWiki 6 Minutes

Trong bài này chúng ta sẽ tìm hiểu về các dãy Farey. Phần đầu là kiến thức cơ bản về dãy Farey, ở phần thứ hai chúng ta sẽ dùng dãy Farey để chứng minh lại một số định lý xấp xỉ (xem [1]).

Cho số nguyên dương \displaystyle n. Phân số tối giản \displaystyle \frac{p}{q}\in [0;1] được gọi là phân số Farey bậc \displaystyle n nếu \displaystyle 0<q\leq n. Dãy tăng tất cả các phân số Farey bậc \displaystyle n được gọi là dãy Farey bậc \displaystyle n,  ký hiệu là \displaystyle F_n.

Bốn dãy Farey đầu tiên là: 

\displaystyle \displaystyle F_1:\,\frac{0}{1};\frac{1}{1}.

\displaystyle \displaystyle F_2:\,\frac{0}{1};\frac{1}{2};\frac{1}{1}.

\displaystyle \displaystyle F_3:\,\frac{0}{1};\frac{1}{3};\frac{1}{2};\frac{2}{3};\frac{1}{1}.

\displaystyle \displaystyle F_4:\,\frac{0}{1};\frac{1}{4};\frac{1}{3};\frac{1}{2};\frac{2}{3};\frac{3}{4};\frac{1}{1}.

Rõ ràng là với mỗi số nguyên dương \displaystyle n, dãy \displaystyle F_n có đúng \displaystyle 1+\sum_{k=1}^n\varphi (k) số hạng.

Định lý 1. Cho các số tự nhiên \displaystyle a,b,c và \displaystyle d thỏa mãn \displaystyle 0\leq \frac{a}{b}<\frac{c}{d}\leq 1 và \displaystyle bc-ad=1. Khi đó \displaystyle \frac{a}{b} và \displaystyle \frac{c}{d} là hai số hạng liên tiếp của dãy \displaystyle F_n. Ở đây \displaystyle n là một số nguyên dương thỏa mãn \displaystyle \max\{b,d\}\leq n\leq b+d-1.

Chứng minh. Từ \displaystyle bc-ad=1 ta có \displaystyle \displaystyle \frac{a}{b},\frac{c}{d} là hai phân số tối giản, mà \displaystyle \max\{b,d\}\leq n, suy ra chúng là các số hạng của dãy \displaystyle F_n. Nếu chúng không phải là hai số hạng liên tiếp của \displaystyle F_n thì tồn tại phân số Farey bậc \displaystyle n, ký hiệu là \displaystyle \frac{h}{k}, thỏa mãn \displaystyle \frac{a}{b}<\frac{h}{k}<\frac{c}{d}. Vì \displaystyle ck-dh\geq 1 và \displaystyle bh-ak\geq 1 nên

\displaystyle b+d-1\geq n\geq k=(bc-ad)k=b(ck-dh)+d(bh-ak)\geq b+d,

đây là điều không thể xảy ra. \Box

Với các số tự nhiên \displaystyle a,b,c và \displaystyle d thỏa mãn \displaystyle 0\leq \frac{a}{b}<\frac{c}{d}, phân số \displaystyle \dfrac{a+c}{b+d} được gọi là phân số trung gian của hai phân số \displaystyle \frac{a}{b} và \displaystyle \frac{c}{d}. Từ chứng minh trên ta có:

Định lý 2. Cho các số tự nhiên \displaystyle a,b,c và \displaystyle d thỏa mãn \displaystyle 0\leq \frac{a}{b}<\frac{c}{d}\leq 1 và \displaystyle bc-ad=1. Khi đó nếu \displaystyle \dfrac{h}{k} là phân số trung gian của hai phân số \displaystyle \frac{a}{b}, \displaystyle \frac{c}{d} thì \displaystyle \frac{a}{b}<\frac{h}{k}<\frac{c}{d} và \displaystyle bh-ak=1,\quad ck-dh=1.

Từ kết quả này ta thấy trong định lý 1, nếu \displaystyle n>b+d-1 thì \displaystyle a/b và \displaystyle c/d không phải là hai số hạng liên tiếp của \displaystyle F_n. Định lý sau cho một cách xác định các dãy Farey bằng quy nạp.

Định lý 3. Với mọi số nguyên dương n, ta có

(1) Dãy \displaystyle F_{n+1} có được từ dãy \displaystyle F_n bằng cách viết vào giữa hai số hạng liên tiếp của \displaystyle F_n có tổng các mẫu không vượt quá \displaystyle n+1 phân số trung gian của chúng.

(2) Nếu \displaystyle \frac{a}{b}<\frac{c}{d} là hai số hạng liên tiếp của \displaystyle F_n thì \displaystyle bc-ad=1.

Chứng minh. Ta sẽ chứng minh bằng quy nạp theo \displaystyle n. Rõ ràng khẳng định đúng với \displaystyle n=1. Giả sử khẳng định đúng với các số nguyên dương bé hơn \displaystyle n\, (n\geq 2), ta sẽ chứng minh khẳng định đúng với \displaystyle n. Từ các kết quả trước và giả thiết quy nạp ta có nếu \displaystyle \frac{a}{b}<\frac{c}{d} là hai số hạng liên tiếp của \displaystyle F_n thì \displaystyle bc-ad=1. Sau khi viết vào giữa hai số hạng liên tiếp của \displaystyle F_n có tổng các mẫu không vượt quá \displaystyle n+1 phân số trung gian của chúng ta thu được dãy con \displaystyle F^{\prime}_n của \displaystyle F_{n+1}. Nếu trong \displaystyle F_{n+1} có phân số \displaystyle \dfrac{h}{k} không thuộc \displaystyle F'_n thì tồn tại hai số hạng liên tiếp \displaystyle \frac{a}{b}<\frac{c}{d} của \displaystyle F'_n sao cho \displaystyle \frac{a}{b}<\frac{h}{k}<\frac{c}{d}. Vì \displaystyle \frac{h}{k} không thuộc \displaystyle F^{\prime}_n nên nó cũng không thuộc \displaystyle F_n, suy ra \displaystyle k>n, kết hợp với \displaystyle k\leq n+1 ta có \displaystyle k=n+1. Từ chứng minh của các kết quả trên suy ra \displaystyle k=n+1\geq b+d, do đó \displaystyle \frac{a}{b} và \displaystyle \frac{c}{d} là hai phân số liên tiếp của \displaystyle F_n. Mà \displaystyle b+d\leq n+1, suy ra chúng không thể là hai số hạng liên tiếp của \displaystyle F^{\prime}_n, vô lý. \Box

Dãy số Farey được đặt theo tên của nhà địa chất người Anh John Farey, lá thư của ông về những dãy này đã được đăng vào năm 1816. Farey phỏng đoán, mà không đưa ra chứng minh, rằng mỗi số hạng trong một dãy Farey là trung gian của các số liên tiếp trong dãy Farey ngay trước nó. Bức thư của Farey đã được đọc bởi Cauchy, người đã đưa ra chứng minh trong một cuốn sách của mình và cho rằng kết quả này là của Farey. Trên thực tế, một nhà toán học khác, Charles Haros, đã công bố những kết quả tương tự vào năm 1802 mà cả Farey và Cauchy đều không biết. Vì vậy, đó là một sự tình cờ lịch sử đã liên kết tên tuổi của Farey với những dãy này. Một lần nữa, trước đó là Pell, người có tên được đặt cho một mối quan hệ toán học không phải là người đầu tiên tìm ra nó.

Đọc thêm

[1] https://nttuan.org/2007/12/15/pell-equation/

Unknown's avatar

Published by Nguyen Trung-Tuan

A math teacher.

Published

2 thoughts on “Farey sequence and approximation of irrational numbers I”

  1. Pingback: Farey sequence and approximation of irrational numbers II – T's Lab
  2. Pingback: Stern–Brocot tree – T's Lab

Leave a comment