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 Parity of Divisor Functions

Bổ đề. Xét một số nguyên dương $n$ . Khi đó
(1) $\tau(n)$ là số lẻ khi và chỉ khi $n$ là một số chính phương.
(2) $\sigma(n)$ là số lẻ khi và chỉ khi $n$ hoặc $n/2$ là số chính phương.

Chứng minh. Giả sử phân tích tiêu chuẩn ra thừa số nguyên tố của số nguyên dương $n$ là:

$n = 2^{\alpha} \cdot p_1^{\alpha_1} \cdot p_2^{\alpha_2} \dots p_k^{\alpha_k}$ .

trong đó $p_1, p_2, \dots, p_k$ là các số nguyên tố lẻ phân biệt, và $\alpha, \alpha_1, \alpha_2, \dots, \alpha_k$ là các số tự nhiên (các số mũ này có thể bằng $0$ nếu thừa số đó không xuất hiện trong $n$ ).

(1) Số lượng các ước dương của $n$ được tính bởi:

$\tau(n) = (\alpha + 1)(\alpha_1 + 1)(\alpha_2 + 1) \dots (\alpha_k + 1)$ .

Một tích các số nguyên là số lẻ khi và chỉ khi tất cả các nhân tử trong tích đều là số lẻ. Do đó, $\tau(n)$ là số lẻ tương đương với việc $\alpha + 1$ và $\alpha_i + 1$ (với mọi $i = 1, \dots, k$ ) đều là các số lẻ.

Điều này xảy ra khi và chỉ khi $\alpha$ và tất cả các $\alpha_i$ đều là số chẵn. Khi các số mũ trong phân tích thừa số nguyên tố đều chẵn, $n$ chính là bình phương của một số nguyên dương. Vậy $\tau(n)$ là số lẻ khi và chỉ khi $n$ là một số chính phương.

(2) Tổng các ước dương của $n$ được tính bởi:

$\sigma(n) = (1 + 2 + 2^2 + \dots + 2^{\alpha}) \prod_{i=1}^k (1 + p_i + p_i^2 + \dots + p_i^{\alpha_i})$ .

Để $\sigma(n)$ là số lẻ, điều kiện cần và đủ là mỗi nhân tử trong tích trên đều là số lẻ.

Đầu tiên ta xét nhân tử $S_0 = 1 + 2 + 2^2 + \dots + 2^{\alpha}$ . Nếu $\alpha = 0$ thì $S_0 = 1$ (là số lẻ). Nếu $\alpha \ge 1$ thì $S_0 = 1 + 2(1 + 2 + \dots + 2^{\alpha-1})$ , luôn là một số lẻ bất chấp tính chẵn lẻ của $\alpha$ . Do đó, số mũ $\alpha$ không bị ràng buộc điều kiện để tổng này lẻ.

Bây giờ xét nhân tử ứng với các số nguyên tố lẻ $p_i$ ( $i = 1, 2, \dots, k$ ):

$S_i = 1 + p_i + p_i^2 + \dots + p_i^{\alpha_i}$ .

Tổng $S_i$ bao gồm $\alpha_i + 1$ số hạng. Vì $p_i$ là số lẻ nên lũy thừa $p_i^j$ luôn là số lẻ với mọi $j$ . Một tổng gồm các số lẻ sẽ nhận giá trị lẻ khi và chỉ khi số lượng các số hạng tham gia vào tổng là một số lẻ.
Suy ra $\alpha_i + 1$ phải là số lẻ, tương đương với $\alpha_i$ phải là số chẵn với mọi $i = 1, 2, \dots, k$ .

Từ đó, ta có thể viết lại $n$ dưới dạng $n = 2^{\alpha} \cdot \left(p_1^{\frac{\alpha_1}{2}} p_2^{\frac{\alpha_2}{2}} \dots p_k^{\frac{\alpha_k}{2}}\right)^2 = 2^{\alpha} \cdot M^2$ , trong đó $M$ là một số nguyên dương lẻ.

Xét hai trường hợp đối với $\alpha$ :

Trường hợp 1: Nếu $\alpha$ là số chẵn (giả sử $\alpha = 2m$ với $m \in \mathbb{N}$ ), ta có:

$n = 2^{2m} \cdot M^2 = (2^m \cdot M)^2$

Khi đó, $n$ là một số chính phương.

Trường hợp 2: Nếu $\alpha$ là số lẻ (giả sử $\alpha = 2m + 1$ với $m \in \mathbb{N}$ ), ta có:

$n = 2^{2m+1} \cdot M^2 = 2 \cdot (2^m \cdot M)^2 \implies \frac{n}{2} = (2^m \cdot M)^2$

Khi đó, $n/2$ là một số chính phương.

Tóm lại, $\sigma(n)$ là số lẻ khi và chỉ khi $n$ hoặc $n/2$ là một số chính phương. $\Box$

Finite Unions of Proper Subspaces Over an Infinite Field

A vector space over an infinite field cannot be the union of finitely many proper subspaces.

Proof. Assume for the sake of contradiction that $V$ is a vector space over an infinite field $\mathbb{F}$ and $V = \bigcup_{i=1}^n W_i$ , where $n$ is the smallest positive integer satisfying this property and the $W_i$ are proper subspaces of $V$ .
Since $V$ cannot be a proper subspace of itself, $n$ must be greater than or equal to $2$ . Since $n$ is minimal, $W_n$ is not contained in the union of the remaining subspaces. Thus there exists a vector $u \in W_n$ such that $u \notin W_i$ for all $i < n$ . On the other hand, since $W_n$ is a proper subspace of $V$ , there exists a vector $v \notin W_n$ .
Consider the infinite set of vectors of the form $v + c u$ with $c \in \mathbb{F}$ . Since $V$ is the union of $n$ subspaces and the field $\mathbb{F}$ has infinitely many elements, by the pigeonhole principle there exists a subspace $W_k$ containing at least two distinct vectors from the considered set. Suppose $v + c_1 u \in W_k$ and $v + c_2 u \in W_k$ with $c_1, c_2 \in \mathbb{F}$ and $c_1 \neq c_2$ . Then the difference of these two vectors is $(c_1 - c_2) u \in W_k$ . Since $c_1 \neq c_2$ , the scalar $c_1 - c_2$ is non-zero, hence we have $u \in W_k$ . If $k = n$ , then from $v + c_1 u \in W_n$ and $u \in W_n$ we deduce that $v \in W_n$ , which contradicts the choice of $v$ . If $k < n$ , then $u \in W_k$ , which contradicts the choice of $u$ . All cases lead to a contradiction. Therefore, a vector space over an infinite field cannot be the union of finitely many proper subspaces. $\Box$

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$