Subconvex sequences

Trong bài này tôi sẽ giới thiệu một lớp dãy hay gặp trong các đề thi chọn học sinh giỏi các cấp. Chứng minh định lí chính trong bài là của Adrian Sandovichi. Để theo dõi cho dễ, các em học sinh nên đọc lại bài sau:

https://nttuan.org/2023/09/15/limit-of-a-sequence/

Định nghĩa. Cho dãy số thực không âm $(x_n)_{n\geq 1}$ và số nguyên $k>0$ . Dãy số $(x_n)_{n\geq 1}$ được gọi là một dãy lồi dưới cấp $k$ nếu có các số thực $\alpha_1,$ $\alpha_2,\ldots,$ $\alpha_k$ sao cho hai điều kiện sau được thỏa mãn đồng thời:

(1) $\alpha_i\in (0;1),\quad \forall i=\overline{1,k}$ và $\alpha_1+\alpha_2+\cdots+\alpha_k\leq 1.$

(2) $x_{n+k}\leq \alpha_1x_{n+k-1}+\alpha_2x_{n+k-2}+\cdots+\alpha_kx_n,\quad \forall n\geq 1.$

Mọi dãy lồi dưới cấp $1$ đều có giới hạn bằng $0.$ Trong định nghĩa trên, nếu dãy số $(x_n)$ có giới hạn hữu hạn và $\sum\alpha_i<1$ thì $\lim x_n=0.$

Định lí. Cho số nguyên dương $k$ . Khi đó mọi dãy lồi dưới cấp $k$ đều có giới hạn hữu hạn.

Chứng minh. Gọi $(x_n)$ là một dãy lồi dưới cấp $k$ . Khi đó tồn tại các số thực $\alpha_1,$ $\alpha_2,\ldots,$ $\alpha_k$ sao cho hai điều kiện sau được thỏa mãn đồng thời:

(1) $\alpha_i\in (0;1),\quad \forall i=\overline{1,k}$ và $\alpha_1+\alpha_2+\cdots+\alpha_k\leq 1.$

(2) $x_{n+k}\leq \alpha_1x_{n+k-1}+\alpha_2x_{n+k-2}+\cdots+\alpha_kx_n,\quad \forall n\geq 1.$

Xét dãy số $(y_n)_{n\geq 1}$ xác định bởi $\displaystyle y_n=\max_{0\leq i\leq k-1}x_{n+i}$ với mọi số nguyên $n>0.$ Ta thấy $(y_n)_{n\geq 1}$ là một dãy số không tăng và bị chặn dưới bởi $0$ nên nó có giới hạn hữu hạn không âm, đặt $L=\lim y_n$ . Ta sẽ chứng minh $(x_n)$ có giới hạn hữu hạn và $L=\lim x_n$ .

Với mọi số thực dương $\epsilon$ , cố định nó.

Đặt $\displaystyle t=\min\left\{1;\frac{\alpha_1^k}{2^k(1-\alpha_1)}\right\}.$ Vì $t>0$ và $L$ là giới hạn của dãy số không tăng $(y_n)$ nên tồn tại số nguyên dương $n_{\epsilon}$ để

$x_n\leq y_n<L+t\epsilon\leq L+\epsilon,\quad \forall n\geq n_{\epsilon}.\quad (*)$

Bây giờ ta chứng minh $x_m>L-\epsilon,\quad \forall m\geq k+n_{\epsilon}.\quad (**)$

Giả sử tồn tại số nguyên dương $m\geq k+n_{\epsilon}$ sao cho $x_m\leq L-\epsilon.$

Mệnh đề. $\displaystyle x_{m+p}\leq L-\epsilon\left(\frac{\alpha_1}{2}\right)^p,\quad \forall p=\overline{1,k-1}.$

Chứng minh. Ta chứng minh bằng quy nạp theo $p.$ Với $p=1$ , từ $(*)$ và cách chọn $t$ ta có

$x_{m+1} \leq \alpha_1x_m+\alpha_2x_{m-1}+\cdots+\alpha_kx_{m-k+1}$

$\leq\alpha_1x_m+(\alpha_2+\cdots+\alpha_k)(L+t\epsilon)$

$\leq\alpha_1(L-\epsilon)+(1-\alpha_1)(L+t\epsilon)$

$\leq L-a_1\epsilon+\left(\frac{\alpha_1}{2}\right)^k\epsilon$

$\leq L-a_1\epsilon+\left(\frac{\alpha_1}{2}\right)^1\epsilon$

$=L-\epsilon\left(\frac{\alpha_1}{2}\right).$

Suy ra khẳng định đúng với $p=1.$ Giả sử khẳng định đúng đến $p<k-1$ , ta chứng minh nó đúng với $p+1.$ Theo giả thiết quy nạp, $(*)$ và cách chọn $t$ ta có

$x_{m+p+1} \leq \alpha_1x_{m+p}+\alpha_2x_{m+p-1}+\cdots+\alpha_kx_{m+p-k+1}$

$\leq\alpha_1\left(L-\epsilon\left(\frac{\alpha_1}{2}\right)^p\right)+(1-\alpha_1)(L+t\epsilon)$

$=L-a_1\epsilon \left(\frac{\alpha_1}{2}\right)^p+(1-\alpha_1)t\epsilon$

$\leq L-a_1\epsilon \left(\frac{\alpha_1}{2}\right)^p+\left(\frac{\alpha_1}{2}\right)^k\epsilon$

$\leq L-a_1\epsilon \left(\frac{\alpha_1}{2}\right)^p +\left(\frac{\alpha_1}{2}\right)^{p+1}\epsilon$

$=L-\epsilon\left(\frac{\alpha_1}{2}\right)^{p+1}.$

Suy ra khẳng định đúng với $p+1$ . Theo nguyên lý quy nạp toán học, mệnh đề là đúng. $\Box$

Continue reading →

A proof of Cauchy–Davenport theorem

Trong bài này tôi sẽ giới thiệu một chứng minh của định lí Cauchy-Davenport.

Định lí Cauchy – Davenport. Cho số nguyên tố $p$ và hai tập con khác rỗng $A,B$ của $\mathbb{Z}/p\mathbb{Z}.$ Khi đó

$|A+B|\geq\min (p,|A|+|B|-1).$

Chứng minh. Ta chứng minh khẳng định bằng quy nạp theo $|B|$ . Khi $|B|=1$ ta có

$|A+B|=|A|=\min (p,|A|)=\min (p,|A|+|B|-1).$ Suy ra khẳng định đúng khi $|B|=1$ . Khi $|B|=2$ ta viết $B=\{b_1,b_2\}$ và $A=\{a_1,a_2,\ldots,a_m\},$ ta có ngay $|A+B|\geq m$ .

Nếu $|A+B|= m$ thì $\{b_1+a_1,\ldots,b_1+a_m\}=\{b_2+a_1,\ldots,b_2+a_m\},$ suy ra $mb_1\equiv mb_2\pmod{p}$ , hay $m=p$ . Khi đó $|A+B|=p\geq\min (p,|A|+|B|-1).$

Nếu $|A+B|>m$ thì $|A+B|\geq m+1\geq\min (p,m+1)=\min (p,|A|+|B|-1).$

Vậy khẳng định đúng khi $|B|=2$ . Giả sử khẳng định đúng với mỗi tập $B$ thỏa mãn $|B|<n,$ trong đó $n\geq 3.$ Ta sẽ chứng minh khẳng định đúng với mọi tập $B$ có $|B|=n.$ Xét một tập $B$ thỏa mãn $|B|=n$ . Đặt $|A+B|=l,|A|=m$ và viết $B=\{b_1,b_2,\ldots,b_n\}.$ Xét ba trường hợp

Trường hợp 1. $l\geq p.$

Ta có $|A+B|=l\geq p\geq\min (p,|A|+|B|-1).$

Trường hợp 2. $m+n>p.$

Ta có $A+B=\{0,1,2,\ldots,p-1\}$ , thật vậy với mỗi $g\in \{0,1,2,\ldots,p-1\}$ , hai tập $g-A$ và $B$ có giao khác rỗng vì chúng là các tập con của tập $\{0,1,2,\ldots,p-1\}$ và có tổng số phần tử lớn hơn $p$ . Lấy $h\in g-A\cap B$ ta có ngay $g=b=g-a\,\, (a\in A,b\in B),$ suy ra $g=a+b\in A+B$ . Từ đây ta có $|A+B|=p\geq\min (p,|A|+|B|-1).$

Trường hợp 3. $l<p$ và $m+n\leq p.$

Ở trường hợp này thì $\min (p,|A|+|B|-1)=\min (p,m+n-1)=m+n-1.$ Áp dụng giả thiết quy nạp cho hai tập $C=A+B$ và $\{b_1,b_n\}$ ta có $|C+\{b_1,b_n\}|\geq\min (p,|C|+|\{b_1,b_n\}|-1)=\min (p,l+1)=l+1,$ suy ra $C+b_1\not = C+b_n$ , do đó tồn tại số nguyên $x$ sao cho $x-b_1\in A+B$ và $x-b_n\not\in A+B$ . Từ đây ta thấy tồn tại số nguyên dương $r<n$ sao cho $x-b_i\in A+B,\,\forall i=\overline{1,r}$ và $x-b_i\not\in A+B,\,\forall i=\overline{r+1,n}$ . Áp dụng giả thiết quy nạp cho hai tập $A$ và $B^{\prime}=\{b_{r+1},b_{r+2},\ldots,b_n\}$ ta có

$|A+B^{\prime}|\geq \min (p,|A|+|B^{\prime}|-1)=\min (p,m+n-r-1)=m+n-r-1.$ Ta có $x-b_i\not\in A+B^{\prime},\,\forall i=\overline{1,r}$ , vì nếu chẳng hạn $x-b_1\in A+B^{\prime}$ thì

$x-b_1= a+b_{s}\Rightarrow x-b_s\in A+B,$ điều này trái với cách chọn $r$ . Vậy $|A+B|\geq r+|A+B^{\prime}|\geq r+m+n-r-1=m+n-1,$ và định lí được chứng minh. $\Box$

Bằng quy nạp ta chứng minh được kết quả sau.

Hệ quả. Cho số nguyên dương $h>1,$ số nguyên tố $p$ và $h$ tập con khác rỗng $A_1,$ $A_2,\ldots,$ $A_h$ của $\mathbb{Z}/p\mathbb{Z}.$ Khi đó $\displaystyle \mid A_1+A_2+\cdots+A_h\mid \geq \min \left(p,\sum_{i=1}^h\mid A_i\mid-h+1\right).$

Combinatorial Nullstellensatz

Trong bài này chúng tôi giới thiệu một chứng minh ngắn của định lý không điểm tổ hợp của Noga Alon, và sử dụng nó chứng minh định lý Cauchy – Davenport (xem [1]). Từ bây giờ, khi nói đến trường thì các bạn hiểu là nói đến $\displaystyle \mathbb{C}$ , $\displaystyle \mathbb{R}$ , $\displaystyle \mathbb{Q}$ , hay $\displaystyle \mathbb{Z}/p\mathbb{Z}$ .

Định lý 1 (N. Alon, 1999). Cho $\displaystyle \mathbb{F}$ là một trường bất kỳ, và cho $\displaystyle P\left(x_{1}, \ldots, x_{n}\right)$ là một đa thức trong $\displaystyle \mathbb{F}\left[x_{1}, \ldots, x_{n}\right]$ . Giả sử bậc của $\displaystyle P$ là $\displaystyle \sum_{i=1}^{n} k_{i}$ , trong đó $\displaystyle k_{i}$ là một số nguyên không âm, và hệ số của đơn thức $\displaystyle x_{1}^{k_{1}} x_{2}^{k_{2}} \cdots x_{n}^{k_{n}}$ trong $\displaystyle P$ khác không. Khi đó với mỗi tập con $\displaystyle A_{1}, \ldots, A_{n}$ của $\displaystyle \mathbb{F}$ thỏa mãn $\displaystyle \left|A_{i}\right| \geq k_{i}+1$ với mỗi $\displaystyle i=1,2, \ldots, n$ , tồn tại $\displaystyle a_{1} \in A_{1}, \ldots, a_{n} \in A_{n}$ để $\displaystyle P\left(a_{1}, \ldots, a_{n}\right) \neq 0$ .

Định lý trên được gọi là định lý không điểm tổ hợp, nó là một tổng quát của kết quả: Với mỗi đa thức khác không $\displaystyle f(x)$ với hệ số thuộc một trường $\displaystyle \mathbb F$ , số nghiệm của $\displaystyle f$ trong $\displaystyle \mathbb F$ không vượt quá $\displaystyle \deg f$ .

Chứng minh (Mateusz Michalek). Khẳng định là đúng một cách hiển nhiên khi $\displaystyle P$ là đa thức hằng, bây giờ ta xét trường hợp còn lại.

Quy nạp theo $\displaystyle \deg P$ . Nếu $\displaystyle \deg(P)=1$ thì định lý là đúng. Giả sử $\displaystyle \deg(P)>1$ và $\displaystyle P$ thỏa mãn các giả thiết của định lý nhưng kết luận là sai. Nghĩa là $\displaystyle P(x)=0$ với mọi $\displaystyle x \in A_{1} \times \ldots \times A_{n}$ . Không mất tính tổng quát, giả sử $\displaystyle k_{1}>0$ . Xét một $\displaystyle a \in A_{1}$ và viết

$\displaystyle P=\left(x_{1}-a\right) Q+R\quad \quad (1)$

bằng cách sử dụng thuật toán chia. Xem (1) là một đẳng thức của các đa thức một biến $\displaystyle x_{1}$ với hệ số thuộc $\displaystyle \mathbb{F}\left[x_{2}, \ldots, x_{n}\right]$ . Vì bậc của $\displaystyle R$ theo biến $\displaystyle x_{1}$ là bé hơn $\displaystyle \deg\left(x_{1}-a\right)$ , đa thức $\displaystyle R$ không chứa $\displaystyle x_{1}$ . Từ giả thiết về $\displaystyle P$ ta có $\displaystyle Q$ phải có một đơn thức không bị triệt tiêu có dạng $\displaystyle x_{1}^{k_{1}-1} x_{2}^{k_{2}} \cdots x_{n}^{k_{n}}$ và

$\displaystyle \deg(Q)=\sum_{i=1}^{n} k_{i}-1=\deg(P)-1.$

Lấy mỗi $\displaystyle x \in\{a\} \times A_{2} \times \ldots \times A_{n}$ và thay vào (1). Vì $\displaystyle P(x)=0$ ta có $\displaystyle R(x)=0$ . Nhưng $\displaystyle R$ không chứa $\displaystyle x_{1}$ , suy ra $\displaystyle R$ cũng bằng không trên $\displaystyle \left(A_{1}-\{a\}\right) \times A_{2} \times \ldots \times A_{n}$ .

Bây giờ thay mỗi $\displaystyle x \in\left(A_{1}-\{a\}\right) \times A_{2} \times \ldots \times A_{n}$ vào (1). Vì $\displaystyle x_{1}-a$ khác không, ta có $\displaystyle Q(x)=0$ . Vậy là $\displaystyle Q$ bằng không trên $\displaystyle \left(A_{1}-\{a\}\right) \times A_{2} \times \ldots \times A_{n}$ , trái với giả thiết quy nạp. $\Box$

Một áp dụng đầu tiên là chứng minh ngắn của định lý Cauchy – Davenport trong lý thuyết số cộng tính. Định lý được chứng minh đầu tiên bởi Cauchy vào năm 1813 và bởi Davenport vào năm 1935. Cho $\displaystyle A$ và $\displaystyle B$ là hai tập con khác rỗng của $\displaystyle \mathbb{Z}/{p}\mathbb{Z}$ với $\displaystyle \mid A\mid =a$ và $\displaystyle \mid B\mid =b$ . Hỏi tập

$\displaystyle A+B:=\{a+b\mid (a,b)\in A\times B\}$

có thể có ít nhất bao nhiêu phần tử?

Định lý 2 (Cauchy – Davenport). Cho số nguyên tố $\displaystyle p$ và cho $\displaystyle A$ và $\displaystyle B$ là hai tập con khác rỗng của $\displaystyle \mathbb{Z}/{p}\mathbb{Z}$ với $\displaystyle \mid A\mid =a$ và $\displaystyle \mid B\mid =b$ . Khi đó

$\displaystyle |A+B|\geq\min \{p,a+b-1\}.$

Chứng minh. Nếu $\displaystyle a+b>p$ thì $\displaystyle \mid A+B\mid =p$ . Thật vậy, với mỗi $\displaystyle g\in \mathbb{Z}/{p}\mathbb{Z}$ , hai tập $\displaystyle g-A$ và $\displaystyle B$ có giao khác rỗng vì $\displaystyle a+b>p$ . Lấy $\displaystyle h\in (g-A)\cap B$ ta có ngay $\displaystyle h=b=g-a\quad (a\in A,b\in B),$ suy ra $\displaystyle g=a+b\in A+B$ . Từ đây ta có $\displaystyle |A+B|=p=\min \{p,a+b-1\}.$

Bây giờ ta xét $\displaystyle a+b\leq p$ và giả sử bất đẳng thức là sai. Gọi $\displaystyle C$ là một tập có cỡ $\displaystyle a+b-2$ trong $\displaystyle \mathbb{Z}/{p}\mathbb{Z}$ chứa $\displaystyle A+B$ . Xét đa thức

$\displaystyle f(x, y)=\prod_{c \in C}(x+y-c)$

trên $\displaystyle \mathbb{Z}/{p}\mathbb{Z}$ . Đây là một đa thức hai biến có bậc $\displaystyle a+b-2$ . Ta sẽ chứng minh

$\displaystyle \left[x^{a-1} y^{b-1}\right] f(x, y)=\left(\begin{array}{c}a+b-2 \\ a-1\end{array}\right) \not =0.$

Để hình thành hệ số này khi khai triển $\displaystyle f$ , ta chọn $\displaystyle x$ đúng $\displaystyle a-1$ lần và $\displaystyle y$ đúng $\displaystyle b-1$ lần trong $\displaystyle a+b-2$ thừa số. Như vậy ta có đẳng thức đầu. Hệ số nhị thức khác không là vì $\displaystyle a+b-2<p$ và $\displaystyle p$ là số nguyên tố.

Vì $\displaystyle |A|=a$ và $\displaystyle |B|=b$ , định lý không điểm tổ hợp cho ta $\displaystyle x \in A$ và $\displaystyle y \in B$ mà $\displaystyle f(x, y) \neq 0$ . Điều này không thể xảy ra vì $\displaystyle f$ đã được dựng để triệt tiêu trên mọi cặp $\displaystyle (x, y)$ như vậy. $\Box$

Bài đọc thêm

[1] https://nttuan.org/2014/09/29/cauchy-davenport/

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

Perfect rulers

Giả sử ta có một cái thước kẻ dài $\displaystyle 6$ , trên đó đã đánh dấu các điểm $\displaystyle 0$ , $\displaystyle 1$ , $\displaystyle 2$ , $\displaystyle 3$ , $\displaystyle 4$ , $\displaystyle 5$ , $\displaystyle 6$ . Sử dụng chiếc thước này ta có thể tạo mọi đoạn có độ dài thuộc $\displaystyle [6]$ , nhưng ta không cần đánh dấu trên thước nhiều điểm như thế để đạt được điều này. Ta có thể đánh dấu $\displaystyle 0$ , $\displaystyle 1$ , $\displaystyle 4$ , $6$ là đủ (đoạn độ dài $2$ được đo giữa hai điểm $4$ và $6$ , đoạn độ dài $3$ được đo giữa $1$ và $4$ , đoạn độ dài $4$ được đo giữa $0$ và $4$ , đoạn độ dài $5$ được đo giữa $1$ và $6$ ). Vì $C_4^2=6$ nên hoàn cảnh này là hoàn hảo.

Bài toán. Cho một số nguyên $n$ lớn hơn $4$ . Chứng minh rằng không tồn tại $n$ số tự nhiên phân biệt $a_1$ , $a_2$ , $\ldots$ , $a_n$ sao cho mọi số nguyên dương không vượt quá $C_n^2$ đều có dạng $a_i-a_j$ .

Lời giải. Giả sử ngược lại, tồn tại $n$ số tự nhiên phân biệt $a_1$ , $a_2$ , $\ldots$ , $a_n$ sao cho mọi số nguyên dương không vượt quá $C_n^2$ đều có dạng $a_i-a_j$ .

Xét đa thức $\displaystyle A(z) = \sum_i z^{a_i}$ . Theo tính chất của các số $a_1$ , $a_2$ , $\ldots$ , $a_n$ , ta có