Farey sequence and approximation of irrational numbers I

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/

Pell’s equation

Trong bài này chúng tôi sẽ giới thiệu một số định lí của Dirichlet về xấp xỉ số thực bởi số hữu tỉ, và áp dụng các định lí đó vào lý thuyết phương trình Pell.

Định lí 1 (Dirichlet). Cho số thực $\theta$ và số nguyên dương $Q$ . Khi đó có số nguyên dương $q$ và số nguyên $a$ thỏa mãn $q\leq Q$ và $\displaystyle \left|\theta-\frac{a}{q}\right|\leq\dfrac{1}{q(Q+1)}.$

Chứng minh. Phân hoạch nửa đoạn $[0;1)$ thành $Q+1$ nửa đoạn

$\displaystyle I_k=\left[\frac{k}{Q+1};\frac{k+1}{Q+1}\right),\quad k=0,1,\ldots,Q.$

Xét $Q$ số $\{1.\theta\},\{2.\theta\},\ldots,\{Q.\theta\}$ .

Nếu $I_0$ chứa ít nhất một số trong dãy trên, chẳng hạn $\{m.\theta\}$ , ta chọn $q=m$ . Nếu $I_{Q}$ chứa ít nhất một số trong dãy trên, chẳng hạn $\{n.\theta\}$ , ta chỉ cần chọn $q=n$ . Nếu hai khoảng trên không chứa số nào thì tồn tại một khoảng $I_i$ chứa ít nhất hai số $\{j.\theta\},$ $\{k.\theta\}$ $(j<k)$ trong dãy, ta chọn $q=k-j$ . $\Box$

Như vậy mọi số thực có thể được xấp xỉ bởi một số hữu tỉ có mẫu bị chặn với độ chính xác phụ thuộc vào chặn trên của mẫu. Sau đây là một áp dụng đẹp đẽ của định lí trên:

Hệ quả. Mọi số nguyên tố dạng $4k+1$ có thể viết thành tổng của hai số chính phương.

Chứng minh. Theo định lí Wilson, tồn tại số nguyên dương $c$ sao cho $c^2+1\equiv 0\pmod{p}.$ Theo định lí Dirichlet, tồn tại các số nguyên $a,b$ sao cho $1\leq b\leq [\sqrt{p}]$ và

$\displaystyle \left|\frac{c}{p}-\frac{a}{b}\right|\leq\frac{1}{b([\sqrt{p}]+1)}<\frac{1}{b\sqrt{p}}. \quad (*)$

Từ $(*)$ ta có $|cb-ap|<\sqrt{p}$ , suy ra $0<(cb-ap)^2+b^2<2p$ , mà $(cb-ap)^2+b^2\equiv b^2(c^2+1)\equiv 0\pmod{p},$ suy ra $(cb-ap)^2+b^2=p.$ $\Box$

Định lí 2 (Dirichlet). Cho số vô tỷ $\alpha$ . Khi đó có vô hạn số hữu tỷ $\displaystyle\frac{a}{q}$ sao cho $q>0$ và $\displaystyle \left|\alpha-\frac{a}{q}\right|<\frac{1}{q^2}.$ Hơn nữa ta có thể chọn $q$ lớn tùy ý.

Chứng minh. Ta sẽ xây dựng dãy hữu tỷ thỏa mãn bằng quy nạp.

Với số nguyên $Q\geq 1$ bất kỳ, theo định lí 1, tồn tại phân số $\displaystyle\frac{a}{q}$ sao cho $1\leq q\leq Q$ và

$\displaystyle \left|\alpha-\frac{a}{q}\right|\leq\frac{1}{q(Q+1)}.$

Bằng cách thu gọn $\displaystyle\frac{a}{q}$ nếu cần, ta có thể xem phân số này tối giản. Do $Q+1>q$ nên từ bất đẳng thức trên ta có

$\displaystyle \left|\alpha-\frac{a}{q}\right|\leq\frac{1}{q(Q+1)}<\frac{1}{q^2}.$

Giả sử ta đã xây dựng được dãy các phân số tối giản đôi một khác nhau $\displaystyle\frac{a_1}{q_1},\frac{a_2}{q_2},\ldots,\frac{a_m}{q_m}$ thỏa mãn bất đẳng thức trong định lí. Vì $\alpha$ là số vô tỷ nên $|\alpha-a_i/q_i|>0\,\forall i$ , bởi thế nên ta có thể chọn được số nguyên dương $Q$ để $Q>\max \{|\alpha-a_i/q_i|^{-1}\}.$ Dùng định lí 1 cho số $Q$ này ta tìm được phân số tối giản $\displaystyle\frac{a_{m+1}}{q_{m+1}}$ sao cho $1\leq q_{m+1}\leq Q$ và

$\displaystyle \left|\alpha-\frac{a_{m+1}}{q_{m+1}}\right|\leq\frac{1}{q_{m+1}(Q+1)}<\frac{1}{q_{m+1}^2}.$

Phân số này khác tất cả các phân số trước vì

$\displaystyle \left|\alpha-\frac{a_{m+1}}{q_{m+1}}\right|\leq\frac{1}{q_{m+1}(Q+1)}<\frac{1}{Q}<\min\{|\alpha-a_i/q_i|\}.$

Để kết thúc chỉ cần để ý rằng với mỗi $q>1$ chỉ có nhiều nhất hai giá trị $a$ làm cho bất đẳng thức trong định lí đúng. $\Box$

Continue reading →

Polynomials in one variable: Basic definitions

Trong bài này $K$ là một trong các tập hợp $\mathbb{F}_p$ (tập các số nguyên modulo một số nguyên tố $p$ ), $\mathbb{Q}$ , $\mathbb{R},$ hoặc $\mathbb{C}$ .

Định nghĩa 1. Cho $n$ là một số tự nhiên và $a_0,a_1,...,a_n \in K$ . Mỗi tổng hình thức có dạng

$a_n x^n+a_{n-1} x^{n-1}+\ldots+a_1 x+a_0$

được gọi là một đa thức trên $K$ theo biến $x$ với hệ số $a_0,a_1,...,a_n$ . Nếu $k$ là chỉ số lớn nhất sao cho $a_k \neq 0$ , thì ta nói đa thức $f(x)=a_k x^k+\ldots+a_1x+a_0$ có bậc $k$ , viết $\text{deg}(f(x))=k$ , $a_k$ được gọi là hệ số đầu của đa thức $f(x)$ , và $a_0$ được gọi là hệ số tự do của $f(x)$ . Nếu $a_0$ là hệ số đầu của $f(x)$ , thì $f(x)$ được gọi là đa thức hằng.

Nếu hệ số đầu của $f(x)$ là $1$ , thì $f(x)$ được gọi là đa thức monic. Tập tất cả đa thức với hệ số trong $K$ được ký hiệu bởi $K[x]$ .

Theo định nghĩa này thì đa thức không, đa thức mà mọi hệ số là không, không có bậc. Để thuận tiện, ta qui ước nó là đa thức hằng và có bậc bằng $-\infty$ . Một đa thức hằng $f(x)=a_0$ có bậc $0$ nếu $a_0 \neq 0$ . Hai đa thức bằng nhau nếu chúng có cùng bậc và tất cả các hệ số tương ứng bằng nhau. Cần phân biệt giữa đa thức $f(x)$ và hàm đa thức tương ứng từ $K$ đến $K$ xác định bởi thay một phần tử của $K$ vào vị trí của $x$ . Nếu $f(x)=a_m x^m+\ldots+a_1x+a_0$ và $c \in K$ , thì $f(c)=a_m c^m+\ldots+a_1c+a_0$ được gọi là giá trị của $f(x)$ tại $c$ . Nếu $K$ là $\mathbb{F}_p$ thì có thể có hai đa thức khác nhau xác định cùng một hàm đa thức.

Ví dụ 1. Cho $K$ là $\mathbb{F}_3$ và xét các đa thức $x^3$ và $x$ . Với mỗi $c \in \mathbb{F}_3$ , ta có $c^3 \equiv c\pmod{3},$ do đó các hàm đa thức $f(x)=x^3$ và $g(x)=x$ là bằng nhau như các hàm từ $\mathbb{F}_3$ tới $\mathbb{F}_3$ .

Continue reading →

Siegel’s lemma

Trong bài này tôi sẽ giới thiệu một chứng minh của bổ đề Siegel, một bổ đề có nhiều áp dụng trong số học (xem trong [1], trang 316).

Bổ đề Siegel. Cho hai số nguyên dương $N>M$ và một bảng các số nguyên không đồng thời bằng không $(a_{i,j})$ có cỡ $M\times N$ . Khi đó hệ phương trình

$\displaystyle \sum_{j=1}^Na_{i,j}x_j=0,\quad i=1,2,\ldots,M$

có nghiệm nguyên $(y_1,y_2,\ldots,y_N)$ thỏa mãn $\max \mid y_i\mid \leq \left(N\max \mid a_{i,j}\mid \right)^{\frac{M}{N-M}}$ và các số $y_1,y_2,\ldots,y_N$ không đồng thời bằng không.

Hệ phương trình thuần nhất trên có số ẩn nhiều hơn số phương trình và có hệ số hữu tỷ nên nó có nghiệm hữu tỷ khác không, do đó nó có nghiệm nguyên khác không (xem trong [2], trang 49). Bổ đề nói rằng ta có thể tìm nghiệm nguyên không tầm thường đủ nhỏ của hệ.

Chứng minh. Đặt $a=\max \mid a_{i,j}\mid$ , $\displaystyle L_i(x_1,x_2,\ldots,x_N)=\sum_{j=1}^Na_{i,j}x_j,$
$\displaystyle a_i^{+}=\sum_{j=1}^N\max\{a_{i,j};0\},$ và $\displaystyle a_i^{-}=\sum_{j=1}^N\min \{a_{i,j};0\},$ với $i=1,2,\ldots,M$ .

Xét một số tự nhiên $b$ . Gọi $S$ là tập các bộ số tự nhiên $(x_1,x_2,\ldots,x_{N})$ thỏa mãn $x_i\leq b$ với mọi $i$ . Khi đó $\mid S\mid =(b+1)^N$ và với mỗi $(x_i)\in S$ , bộ

$(L_1(x_1,x_2,\ldots,x_N),L_2(x_1,x_2,\ldots,x_N),\ldots,L_M(x_1,x_2,\ldots,x_N))$

thuộc tập hợp tích $\displaystyle T=\prod_{i=1}^M\{a_i^{-}b,a_i^{-}b+1,\ldots,a_i^{+}b\}$ . Ta có

$\displaystyle \mid T\mid = \prod_{i=1}^M\mid \{a_i^{-}b,a_i^{-}b+1,\ldots,a_i^{+}b\}\mid = \prod_{i=1}^M(b(a_i^+-a_i^-)+1)\leq (bNa+1)^M.$

Giả sử chọn được $b$ thỏa mãn bất đẳng thức

$\displaystyle (bNa+1)^M<(b+1)^N.\quad (*)$

Khi đó tồn tại hai phần tử khác nhau $(x_i)$ và $(x_i^{\prime})$ của $S$ để hai phần tử tương ứng trong $T$ là một. Ta thấy $(y_i)$ , với $y_i=x_i-x_i^{\prime}$ , là một nghiệm nguyên khác không của hệ phương trình thỏa mãn $\mid y_i\mid\leq b$ với mọi $i$ . Bây giờ kiểm tra thấy khi $b= \left[\left(Na\right)^{\frac{M}{N-M}}\right]$ thì có $(*)$ , từ đó có nghiệm $(y_i)$ thỏa mãn bổ đề.

Tài liệu tham khảo

[1] Hindry, M., Silverman, J.H.: Diophantine Geometry. Springer, New York (2000)
[2] Jacobson, N.: Lectures in Abstract Algebra: II. Linear Algebra. Springer, New
York (1975)

ISL1988/4 và một số bài toán liên quan

Gần đây bài toán sau lại tìm đến tôi: Cho số nguyên $n$ lớn hơn $1$ và một bảng ô vuông cỡ $n \times n.$ Viết vào các ô vuông của bảng các số $1, 2, \ldots, n^2$ sao cho hai ô khác nhau được viết hai số khác nhau. Chứng minh rằng tồn tại hai ô vuông có chung cạnh mà hiệu hai số được viết trên đó không bé hơn $n.$

Đây là bài toán số $4$ trong cuốn IMO 1988 Shortlist, mà tôi ký hiệu là ISL1988/4. Để làm tài liệu tham khảo cho các bạn đồng nghiệp và học sinh, tôi giới thiệu nhiều lời giải của bài toán và một số bài toán liên quan. Không có kiến thức đặc biệt nào được sử dụng trong bài, các bạn học sinh lớp $8$ hay $9$ định hướng thi vào các lớp chuyên Toán có thể hiểu được tất cả các lời giải.