A Proof of Beatty’s Theorem


Cho số thực \alpha. Dãy Beatty của \alpha là dãy (a_n)_{n\geq 1} xác định bởi a_n=[n\alpha],\quad \forall n\geq 1.

Định lý (Beatty). Cho hai số thực dương \alpha và \beta. Khi đó các dãy Beatty của \alpha và \beta làm thành một phân hoạch của tập các số nguyên dương khi và chỉ khi \alpha và \beta là các số vô tỷ và

\displaystyle \frac{1}{\alpha}+\frac{1}{\beta}=1.

Chứng minh. Đặt S_{\alpha}=\{[n\alpha]|n=1,2,\ldots\} và \displaystyle S_{\beta}=\{[n\beta]|n=1,2,\ldots\}.

Giả sử S_{\alpha} và S_{\beta} làm thành một phân hoạch của tập các số nguyên dương. Ta thấy ngay \alpha và \beta lớn hơn 1, suy ra hai dãy Beatty của hai số này là các dãy tăng. Ta sẽ sử dụng phương pháp mật độ trong lý thuyết số giải tích.

Với mỗi số nguyên dương k, cố định nó. Xét một số nguyên dương n, ta có

\displaystyle [n\alpha]\leq k\Leftrightarrow n\alpha < k+1\Leftrightarrow n < \dfrac{k+1}{\alpha}.

Suy ra |S_{\alpha}\cap \{1, 2, \ldots, k\}|=\left[\dfrac{k+1}{\alpha}\right] hoặc \left[\dfrac{k+1}{\alpha}\right]-1 tùy theo \dfrac{k+1}{\alpha} không nằm trong hay nằm trong \mathbb{Z}. Chứng minh tương tự ta có \displaystyle |S_{\beta}\cap \{1, 2, \ldots, k\}|=\left[\dfrac{k+1}{\beta}\right] hoặc \left[\dfrac{k+1}{\beta}\right]-1 tùy theo \dfrac{k+1}{\beta} không nằm trong hay nằm trong \mathbb{Z}.

Mà |S_{\alpha}\cap \{1, 2, \ldots, k\}|+|S_{\beta}\cap \{1, 2, \ldots, k\}|=k, suy ra

\displaystyle -2+\left[\dfrac{k+1}{\alpha}\right]+\left[\dfrac{k+1}{\beta}\right]\leq k\leq \left[\dfrac{k+1}{\alpha}\right]+\left[\dfrac{k+1}{\beta}\right].

Kết hợp với định nghĩa phần nguyên ta được

\displaystyle -4+\dfrac{k+1}{\alpha}+\dfrac{k+1}{\beta} < k\leq \dfrac{k+1}{\alpha}+\dfrac{k+1}{\beta}.

Chia các vế cho k và cho k\to+\infty ta có \dfrac{1}{\alpha}+\dfrac{1}{\beta}=1. Nếu \alpha là số hữu tỷ thì từ đẳng thức này ta có \beta cũng là số hữu tỷ. Viết \displaystyle \alpha=\dfrac{p}{q},\quad \beta=\dfrac{r}{s}, với p, q, r, và s là các số nguyên dương. Ta thấy S_{\alpha}\cap S_{\beta}\not=\emptyset, chẳng hạn pr thuộc cả hai tập này, suy ra vô lý. Bởi vậy \alpha là số vô tỷ, và \beta cũng thế.

Bây giờ giả sử ngược lại, \alpha và \beta là các số vô tỷ và \dfrac{1}{\alpha}+\dfrac{1}{\beta}=1. Ta thấy ngay \alpha và \beta lớn hơn 1, suy ra hai dãy Beatty của hai số này là các dãy tăng. Nếu S_{\alpha}\cap S_{\beta}\not=\emptyset thì tồn tại các số nguyên dương k,m và n sao cho k=[m\alpha]=[n\beta]. Suy ra

\displaystyle k\leq m\alpha < k+1,\quad k\leq n\beta < k+1.

Vì \alpha và \beta là các số vô tỷ nên

\displaystyle k < m\alpha < k+1,\quad k < n\beta < k+1,

suy ra

\displaystyle \frac{k}{\alpha} < m < \frac{k+1}{\alpha},\quad \frac{k}{\beta} < n < \frac{k+1}{\beta},

cộng theo vế ta có k < m+n < k+1, vô lý. Như vậy S_{\alpha}\cap S_{\beta}=\emptyset.

Nếu tồn tại số nguyên dương l sao cho l\not\in S_{\alpha}\cup S_{\beta} thì tồn tại các số nguyên không âm p và q sao cho

\displaystyle [p\alpha] < l < [(p+1)\alpha], \quad [q\beta] < l < [(q+1)\beta].

Vì l là số nguyên nên từ các bất đẳng thức trên ta suy ra p\alpha < l, đồng thời [(p+1)\alpha] \geq l+1 kéo theo (p+1)\alpha \geq l+1. Lập luận tương tự cho \beta, ta được

\displaystyle p\alpha < l < l+1\leq (p+1)\alpha,\quad q\beta < l < l+1\leq (q+1)\beta.

Vì \alpha,\beta là các số vô tỷ nên

\displaystyle p\alpha < l < l+1 < (p+1)\alpha,\quad q\beta < l < l+1 < (q+1)\beta.

Chia các vế cho \alpha,\beta và cộng lại ta có

\displaystyle p+q < l < l+1 < p+q+2,

điều này không thể xảy ra (do khoảng mở (p+q, p+q+2) có độ dài bằng 2 nên chỉ chứa đúng một số nguyên là p+q+1). \blacksquare

An Upper Bound for the Divisor Function (2)


Bài viết hôm nay sẽ đề cập đến một kết quả quan trọng trong lý thuyết số giải tích, liên quan đến tốc độ tăng của hàm số các ước \tau(n) . Chúng ta sẽ cùng xem xét và chứng minh định lý sau:

Định lý. Với mọi số thực dương \epsilon, tồn tại một hằng số dương C_{\epsilon} sao cho \tau(n) \le C_{\epsilon} \cdot n^{\epsilon} với mọi số nguyên dương n.

Chứng minh. Giả sử n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} là phân tích tiêu chuẩn của n ra các thừa số nguyên tố, với p_i là số nguyên tố và a_i là các số nguyên dương. Ta cần tìm chặn trên cho tỉ số:

\displaystyle\frac{\tau(n)}{n^{\epsilon}} = \prod_{i=1}^k \frac{a_i+1}{p_i^{a_i\epsilon}}.

Xét hàm số f(p, a) = \frac{a+1}{p^{a\epsilon}} với p là số nguyên tố và a \ge 1. Ta sẽ chia các số nguyên tố p thành hai nhóm để đánh giá, dựa vào hằng số \epsilon.

Nhóm 1: Các số nguyên tố p \ge 2^{1/\epsilon}

Điều kiện này tương đương với p^\epsilon \ge 2. Với mọi số nguyên dương a \ge 1, ta có \displaystyle p^{a\epsilon}\ge 2^a. Vì ta luôn có 2^a \ge a+1 với mọi a \in \mathbb{Z}^+ nên với các số nguyên tố thuộc nhóm này thì

\displaystyle f(p, a) = \frac{a+1}{p^{a\epsilon}} \le \frac{a+1}{2^a} \le 1.

Nhóm 2: Các số nguyên tố p < 2^{1/\epsilon}

Với một \epsilon > 0 cố định, chỉ có hữu hạn các số nguyên tố thỏa mãn p < 2^{1/\epsilon}. Cố định một số nguyên tố p thuộc nhóm này, xét giới hạn của f(p, a) khi a \to \infty. Vì p^\epsilon > 1 nên \displaystyle\lim_{a \to +\infty} \frac{a+1}{p^{a\epsilon}} = 0.

Vì dãy số hội tụ về 0, giá trị của f(p, a) sẽ bị chặn trên. Tức là tồn tại một giá trị lớn nhất cho \frac{a+1}{p^{a\epsilon}} khi a chạy trên tập số nguyên dương. Bây giờ ta chọn:

\displaystyle C_{\epsilon} = \prod_{p < 2^{1/\epsilon}} \max\left(1, \sup_{a \ge 1} \frac{a+1}{p^{a\epsilon}}\right).

Quay lại tỉ số ban đầu, ta tách tích các thừa số nguyên tố của n ra thành hai phần tương ứng với hai nhóm trên:

\displaystyle \frac{\tau(n)}{n^{\epsilon}} = \left( \prod_{p_i < 2^{1/\epsilon}} \frac{a_i+1}{p_i^{a_i\epsilon}} \right) \cdot \left( \prod_{p_i \ge 2^{1/\epsilon}} \frac{a_i+1}{p_i^{a_i\epsilon}} \right).

Áp dụng các bất đẳng thức đã thiết lập ta có \tau(n) \le C_{\epsilon} \cdot n^{\epsilon} với mọi số nguyên dương n . \Box

The sum of the reciprocals of the primes


Với mỗi số nguyên dương n, ký hiệu p_n là số nguyên tố thứ n trong dãy tăng tất cả các số nguyên tố. Như vậy p_1=2, p_2=3, p_3=5,…

Trong bài này chúng tôi sẽ giới thiệu một chứng minh của kết quả sau:

Định lý. Chuỗi \displaystyle \frac{1}{p_1}+\frac{1}{p_2}+\frac{1}{p_3}+\ldots là một chuỗi phân kỳ.

Chứng minh. Giả sử ngược lại, khi đó với mỗi số nguyên dương k, chuỗi \displaystyle\sum_{m=k}^{+\infty}\frac{1}{p_m} là một chuỗi hội tụ, gọi S_k là tổng của nó. Vì \lim S_k=0 nên tồn tại số nguyên k sao cho \displaystyle S_{k+1}<\frac{1}{2}. Đặt Q=p_1p_2\ldots p_k và xét các số 1+nQ\, (n=1,2,\ldots). Mỗi số trong dãy này đều không có ước nguyên tố thuộc \{p_1, p_2, \ldots, p_k\}, do đó với mỗi số nguyên dương r, tồn tại số nguyên dương K đủ lớn để

\displaystyle\sum_{n=1}^r\frac{1}{1+nQ}\leq\sum_{t=1}^{K}S_{k+1}^t<1.

Điều này không thể xảy ra do chuỗi \displaystyle \sum_{n=1}^{+\infty}\frac{1}{1+nQ} là một chuỗi phân kỳ. \Box

Tham khảo

[1] https://nttuan.org/2018/12/30/series/

[2] https://en.wikipedia.org/wiki/Divergence_of_the_sum_of_the_reciprocals_of_the_primes

Continued fraction expansion of irrational numbers


In this section we use continued fractions for expansion of irrational numbers.

Theorem 1. Let \displaystyle (x_n)_{n\geq 0} be a sequence of intergers with \displaystyle x_i>0 for every \displaystyle i>0. Then the sequence \displaystyle (p_n/q_n)_{n\geq 0} is a convergent sequence, and the its limit is an irrational number. We denote this limit by \displaystyle [x_0;x_1,x_2,\ldots].

Proof. From [1] we have \displaystyle q_1\geq q_0=1>0 and for all \displaystyle n>1, \displaystyle q_n=x_nq_{n-1}+q_{n-2}, hence by induction on \displaystyle n, \displaystyle q_{n+1}>q_n for every \displaystyle n\geq 1. Therefore \displaystyle\lim_{n\to \infty}q_n=\infty.

By the Proposition 4 in [1], for all \displaystyle n\geq 0,

\displaystyle \frac{p_n}{q_n}-\frac{p_{n+1}}{q_{n+1}}=\frac{(-1)^{n-1}}{q_nq_{n+1}},\quad\quad (1)

hence \displaystyle \frac{p_n}{q_n}-\frac{p_{n+2}}{q_{n+2}}=\frac{(-1)^{n-1}(q_{n+2}-q_n)}{q_nq_{n+1}q_{n+2}},\quad \forall n\geq 0. Therefore

\displaystyle \frac{p_1}{q_1}>\frac{p_3}{q_3}>\frac{p_5}{q_5}>\ldots>\frac{p_0}{q_0}

and

\displaystyle \frac{p_0}{q_0}<\frac{p_2}{q_2}<\frac{p_4}{q_4}<\ldots<\frac{p_1}{q_1},

hence \displaystyle (p_{2n}/q_{2n})_{n\geq 0} and \displaystyle (p_{2n+1}/q_{2n+1})_{n\geq 0} are convergent sequences. By (1) and \displaystyle q_n\to\infty we have

\displaystyle\lim_{n\to\infty}\frac{p_{2n}}{q_{2n}}=\lim_{n\to\infty}\frac{p_{2n+1}}{q_{2n+1}}, so \displaystyle (p_n/q_n)_{n\geq 0} is a convergent sequence.

Now we prove \displaystyle \displaystyle \alpha:=\lim_{n\to\infty}\frac{p_n}{q_n} is an irrational number. We have

\displaystyle \frac{p_{2m}}{q_{2m}}<\alpha<\frac{p_{2n+1}}{q_{2n+1}},\quad\forall m,n\geq 0.

Thus, by (1),

\displaystyle\left|\alpha-\frac{p_{2n}}{q_{2n}}\right|\leq \frac{1}{q_{2n}q_{2n+1}}<\frac{1}{q_{2n}^2},\quad\forall n\geq 1.

By the Proposition 2 in [1], \displaystyle p_{2n} and \displaystyle q_{2n} are coprime integers for every \displaystyle n\geq 1, hence there are infinite rational numbers \displaystyle r/s, with \displaystyle s>0 and \displaystyle (r,s)=1, such that

\displaystyle \left|\alpha-\frac{r}{s}\right| <\frac{1}{s^2}.\quad\quad (2)

Assume that \displaystyle \alpha is rational and write \displaystyle \alpha=p/q, where \displaystyle p and \displaystyle q>0 are coprime integers. For all positive integers \displaystyle s, at most two integers \displaystyle r satisfy the equation (2), hence there are coprime integers \displaystyle r_0 and \displaystyle s_0>q such that

\displaystyle\left|\frac{p}{q}-\frac{r_0}{s_0}\right| <\frac{1}{s_0^2}.

From the inequality we have \displaystyle \mid ps_0-qr_0\mid <1, hence \displaystyle ps_0=qr_0, a contradiction. Therefore \displaystyle \alpha is an irrational number. \Box

Theorem 2. Let \displaystyle \alpha be an irrational number. Then there is a unique sequence of integers \displaystyle (a_n)_{n\geq 0} such that

(1) \displaystyle a_i>0 for every \displaystyle i>0.

(2) \displaystyle \alpha =[a_0;a_1,a_2,\ldots].

Proof. In this proof, \displaystyle [x] is the integer part of \displaystyle x. Because \displaystyle \alpha is an irrational number, we have \displaystyle [\alpha]<\alpha<[\alpha]+1, hence there is a real number \displaystyle u_1>1 such that

\displaystyle \alpha=[\alpha]+\frac{1}{u_1}.

Because \displaystyle \alpha is an irrational and \displaystyle [\alpha] is an integer, \displaystyle u_1 is an irrational number. Hence there is an irrational number \displaystyle u_2>1 such that

\displaystyle u_1=[u_1]+\frac{1}{u_2},

and so on. Therefore we have real numbers \displaystyle u_0:=\alpha, u_1>1, \displaystyle u_2>1, \displaystyle \ldots such that \displaystyle u_i is irrationals for every \displaystyle i>0 and

\displaystyle u_k=[u_k]+\frac{1}{u_{k+1}},\quad\forall k\geq 0.

We claim that \displaystyle \alpha=[[u_0];[u_1],[u_2],\ldots]. Fix a \displaystyle k>2. We have

\displaystyle \alpha=[[u_0];[u_1],\ldots, [u_k],u_{k+1}].

Hence, by Proposition 4 in [1],

\displaystyle \left|\alpha-\frac{p_k}{q_k}\right|=\frac{1}{q_k(u_{k+1}q_{k}+q_{k-1})}<\frac{1}{q_k^2},

so \displaystyle \lim_{n\to\infty}\frac{p_n}{q_n}=\alpha. Now assume that

\displaystyle \alpha =[a_0;a_1,a_2,\ldots]=[b_0;b_1,b_2,\ldots],

where \displaystyle (a_n)_{n\geq 0} and \displaystyle (b_n)_{n\geq 0} are two sequences of integers such that \displaystyle a_i>0 and \displaystyle b_i>0 for every \displaystyle i>0.

Because

\displaystyle [a_0;a_1,a_2,\ldots,a_{n}]=a_0+\frac{1}{[a_1;a_2,\ldots,a_n]},\quad\forall n\geq 0,

we have

\displaystyle [a_0;a_1,a_2,\ldots]=a_0+\frac{1}{[a_1;a_2,\ldots]}.

Hence \displaystyle a_0=b_0=[\alpha] and \displaystyle [a_1;a_2,a_3,\ldots] = [b_1;b_2,b_3,\ldots]. Similarly, \displaystyle a_1=b_1 and

\displaystyle [a_2;a_3,a_4,\ldots] = [b_2;b_3,b_4,\ldots],

and so on. Therefore \displaystyle a_i=b_i for every i. \Box

The equality in the theorem is called an expansion of \displaystyle \alpha into a infinite continued fraction. In that expansion we will call \displaystyle [a_0;a_1,a_2,\ldots,a_i] is the \displaystyle i-th convergent of the continued fraction, or \displaystyle i-th convergent of \displaystyle \alpha. The theorem says that for every irrational number has an expansion into a infinite continued fraction, and this expansion is unique.

Example 1. \displaystyle \sqrt{2}=[1;2,2,\ldots].

Example 2. The golden ratio \displaystyle\varphi:=\frac{1+\sqrt{5}}{2}=[1;1,1,\ldots].

Example 3. \displaystyle e=[2;1,2,1,1,4,1,1,6,1,1,8,\ldots].

A sequence \displaystyle (a_n)_{n\geq 0} is called eventually periodic if \displaystyle a_{n+T}=a_n for some positive integer \displaystyle T and sufficiently large \displaystyle n. A real number is called quadratic irrational number, if there is a polynomial \displaystyle P(x) is of degree two with rational coefficients such that \displaystyle P(x) is an irreducible polynomial (see [3]) over the rational numbers and \displaystyle \alpha is a root of \displaystyle P(x).

Theorem 3. Let \displaystyle \alpha be an irrational number and \displaystyle \alpha =[a_0;a_1,a_2,\ldots] is the expansion of \displaystyle\alpha into a infinite continued fraction. Then \displaystyle (a_n)_{n\geq 1} is eventually periodic if and only if \displaystyle \alpha is a quadratic irrational.

References

[1] https://nttuan.org/2008/10/12/continued-fractions-the-basics/

[2] https://nttuan.org/2008/11/14/continued-fraction-expansion-of-rational-numbers/

[3] https://nttuan.org/2009/01/11/poly02/

Least upper bound property


Một tập \displaystyle A \subset\mathbb{R} được gọi là bị chặn trên nếu tồn tại \displaystyle b \in \mathbb{R} sao cho \displaystyle a \leq b với mọi \displaystyle a \in A. Số \displaystyle b được gọi là một cận trên của \displaystyle A. Tương tự, tập \displaystyle A bị chặn dưới nếu tồn tại một cận dưới \displaystyle l \in \mathbb{R} thỏa mãn \displaystyle l \leq a với mọi \displaystyle a \in A. Tập \displaystyle A được gọi là bị chặn nếu nó bị chặn trên và bị chặn dưới.

Bài tập 1. Tìm một tập hợp \displaystyle A các số thực sao cho:

(1) \displaystyle A bị chặn trên.

(2) \displaystyle A bị chặn dưới.

(3) \displaystyle A không bị chặn trên và không bị chặn dưới. \Box

Định nghĩa 1. Một số thực \displaystyle s được gọi là cận trên đúng của \displaystyle A \subset \mathbb{R} nếu nó thỏa mãn đồng thời hai điều kiện:

(1) \displaystyle s là một cận trên của \displaystyle A.

(2) nếu \displaystyle b là một cận trên của \displaystyle A thì \displaystyle s \leq b.

Cận trên đúng cũng thường được gọi là supremum của tập \displaystyle A, ký hiệu \displaystyle \sup A. Cận dưới đúng hay infimum của \displaystyle A được định nghĩa theo cách tương tự và được ký hiệu bởi \displaystyle \inf A. Mặc dù một tập có thể có vô hạn cận trên, nhưng nó chỉ có tối đa một cận trên đúng.  

Ví dụ 1. Cho tập hợp \displaystyle A=\left\{\frac{1}{n}: n \in \mathbb{N}^*\right\}=\left\{1, \frac{1}{2}, \frac{1}{3}, \ldots\right\}.

Tập A bị chặn trên và dưới. Ta thấy \sup A=1 và \inf A=0. \Box

Một bài học quan trọng rút ra từ ví dụ trên là \displaystyle \sup A và \displaystyle \inf A có thể thuộc hoặc không thuộc tập \displaystyle A. Đây là điểm khác nhau cốt yếu giữa phần tử lớn nhất và cận trên đúng (hoặc phần tử nhỏ nhất và cận dưới đúng) của một tập số thực.

Định nghĩa 2. Một số thực \displaystyle a_{0} được gọi là phần tử lớn nhất của tập \displaystyle A, ký hiệu \displaystyle \max A, nếu \displaystyle a_{0} là một phần tử của \displaystyle A và \displaystyle a_{0} \geq a với mọi \displaystyle a \in A. Tương tự, số \displaystyle a_{1} là phần tử nhỏ nhất của \displaystyle A, ký hiệu \displaystyle \min A, nếu \displaystyle a_{1} \in A và \displaystyle a_{1} \leq a với mọi \displaystyle a \in A.

Ví dụ 2. Hai tập \displaystyle [0;2] và \displaystyle (0;2) bị chặn, có cùng cận trên đúng \displaystyle 2, nhưng chỉ \displaystyle [0;2] có phần tử lớn nhất. Như vậy, cận trên đúng có thể tồn tại và không phải là phần tử lớn nhất, nhưng khi phần tử lớn nhất tồn tại, nó cũng là cận trên đúng. \Box

Mặc dù ta có thể thấy rằng không phải mọi tập hợp khác rỗng bị chặn trên nào đều có phần tử lớn nhất, nhưng tiên đề về tính đầy đủ khẳng định rằng mọi tập hợp như vậy đều có một cận trên đúng. Ta sẽ không chứng minh điều này. Tiên đề trong toán học là một giả định được chấp nhận, được sử dụng mà không cần chứng minh.

Tiên đề về tính đầy đủ. Mọi tập các số thực khác rỗng và bị chặn trên đều có cận trên đúng.

Từ tiên đề trên ta có thể chứng minh mọi tập số thực khác rỗng và bị chặn dưới đều có cận dưới đúng. Tiên đề không đúng với tập các số hữu tỷ.

Ví dụ 3. Tập \{r\in\mathbb{Q}\mid r^2<2\} bị chặn trên và khác rỗng nhưng không có cận trên đúng thuộc \mathbb{Q}. \Box

Hai định lý sau cho một định nghĩa tương đương của cận trên đúng và cận dưới đúng.

Continue reading “Least upper bound property” →