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$

An Upper Bound for the Divisor Function

Bổ đề. Với mỗi số nguyên dương $n$ , ta có $\tau (n)\leq \sqrt{3n}$ .

Lời giải. Với $n=1$ ta có ngay bất đẳng thức cần chứng minh. Giả sử $n>1$ và phân tích tiêu chuẩn ra thừa số nguyên tố của nó là $\displaystyle n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$ , trong đó $p_i$ là các số nguyên tố ( $p_1 < p_2 < \dots < p_k$ ) và $\alpha_i \ge 1$ là các số nguyên dương.

Bất đẳng thức cần chứng minh $\tau(n) \le \sqrt{3n}$ có thể được viết lại dưới dạng

$\displaystyle\prod_{i=1}^k \frac{\alpha_i + 1}{p_i^{\alpha_i / 2}} \le \sqrt{3}.$

Để tiện đánh giá, ta xét hàm số $f(p, \alpha) = \frac{\alpha + 1}{p^{\alpha / 2}}$ với $p$ là số nguyên tố và $\alpha \ge 1$ . Ta sẽ tìm giá trị lớn nhất của hàm $f(p, \alpha)$ đối với từng số nguyên tố $p$ .

Với $p = 2$ , giá trị lớn nhất của của $f(2, \alpha)$ là $\frac{3}{2}$ , đạt được khi và chỉ khi $\alpha = 2$ . Với $p = 3$ , giá trị lớn nhất của $f(3, \alpha)$ là $\frac{2}{\sqrt{3}}$ , đạt được khi và chỉ khi $\alpha = 1$ . Với $p\geq 5$ , ta có
$\displaystyle f(p, \alpha) \le \frac{2}{\sqrt{5}} < 1$
với mọi số nguyên dương $\alpha$ .

Từ các đánh giá trên, ta quay lại tích ban đầu $\displaystyle\frac{\tau(n)}{\sqrt{n}} = \prod_{p_i \mid n} f(p_i, \alpha_i).$

Nếu trong phân tích của $n$ có chứa các thừa số nguyên tố $p \ge 5$ , các thành phần này sẽ kéo giá trị của tích xuống (vì chúng nhỏ hơn 1). Do đó để biểu thức đạt giá trị lớn nhất, $n$ chỉ có thể chứa các ước nguyên tố là 2 và 3. Với các $n$ này ta có

$\displaystyle \frac{\tau(n)}{\sqrt{n}} \le f(2, \alpha_2) \cdot f(3, \alpha_3) \le \frac{3}{2} \cdot \frac{2}{\sqrt{3}} = \sqrt{3}.$

Bất đẳng thức $\tau(n) \le \sqrt{3n}$ đã được chứng minh hoàn toàn. $\Box$

Chú ý. Dấu đẳng thức xảy ra khi và chỉ khi các điều kiện sau phải được thỏa mãn đồng thời:

$f(2, \alpha_2) = \frac{3}{2}$ .
$f(3, \alpha_3) = \frac{2}{\sqrt{3}}$ .
$n$ không có bất kỳ ước nguyên tố nào khác ngoài 2 và 3.

Vậy dấu đẳng thức xảy ra khi và chỉ khi $n = 2^2 \cdot 3^1 = 12$ .

Burnside’s lemma

Cho $X$ là một tập hợp và $G$ là một nhóm. Ta nói $G$ tác động trên $X$ , hay $X$ là một $G-$ tập, nếu có hàm $G\times X\to X$ , $(g,x)\mapsto gx$ thoả mãn $ex=x\forall x\in X$ và $g_1(g_2x)=(g_1g_2)x\forall x\in X\forall g_1,g_2\in G$ , ở đây $e$ là phần tử đơn vị của $G$ .

Gìơ ta xét một $G-$ tập $X$ , với mỗi $x\in X$ , ta gọi quỹ đạo của $x$ là tập $\{gx|g\in G\}$ . Các quỹ đạo khác nhau của các phần tử trong $X$ làm thành một phân hoạch của $X$ , thật vậy, quan hệ $xRy$ nếu có $g\in G$ để $x=gy$ là một quan hệ tương đương trên $X$ . Khi $X$ và $G$ là các tập hữu hạn thì ta có thể tính số khối của phân hoạch này theo bổ đề sau đây.

Bổ đề Burnside. Nếu $X$ là một $G-$ tập hữu hạn (nghĩa là $X$ và $G$ là các tập hữu hạn và $X$ là một $G-$ tập) và $N$ là số các quỹ đạo khác nhau của các phần tử trong $X$ thì $N=\dfrac{1}{|G|}\sum_{g\in G}F(g)$ , trong đó với mỗi $g\in G$ , $F(g)$ là số phần tử của tập $\{x\in X|gx=x\}$ .

Tôi sẽ không đưa ra chứng minh nào của bổ đề này ở đây, các bạn có thể tìm một chứng minh trong sách Tổ hợp của Ngô Đắc Tân hay sách về lý thuyết nhóm của Rotman. Gìơ ta đi xét các áp dụng của bổ đề này vào giải các bài toán đếm, các bài tập này đều có trong sách của Rotman.

Bài 1. Cho $n$ và $q$ là các số nguyên dương. Hỏi có bao nhiêu lá cờ gồm $n$ mảnh sao cho mỗi mảnh mang một trong $q$ màu cho trước?(Ví dụ một lá cờ như vậy là cờ của Pháp gồm $3$ mảnh).

Lời giải. Vì khi ta tô màu một mặt của lá cờ thì mặt sau sẽ được xác định hoàn toàn màu. Nên số lá cờ bằng số cách tô bảng $1\times n$ bởi $q$ màu, hai cách tô là như nhau nếu nó ở dạng như hình dưới đây.

(Trong hình trên các $c_i$ là các màu.)

Gọi $X$ là tập các bộ $(c_1,c_2,\cdots,c_n)$ với $c_i$ là một trong $q$ màu đã cho với mỗi $i$ . Ký hiệu $S_n$ là nhóm các hoán vị trên $\{1,2,\cdots,n\}$ , $G$ là nhóm con cyclic sinh bởi hoán vị $f$ của $S_n$ , ở đây $f(i)=n+1-i\forall i$ . Ta cho $G$ tác động trên $X$ theo luật $f(c_1,c_2,\cdots,c_n)=(c_n,c_{n-1},\cdots,c_1)$ . Như trên đã phân tích, ta chỉ cần đếm số $N$ các quỹ đạo của các phần tử của $x$ theo tác động này là xong. Theo bổ đề Burnside, ta chỉ cần tính $F(id)$ và $F(f)$ . Dễ thấy $F(id)=|X|=q^n$ theo quy tắc nhân. Để tính $F(f)$ , ta chú ý rằng $(c_1,c_2,\cdots,c_n)\in X$ không thay đổi khi tác động $f$ nếu và chỉ nếu $c_1=c_n,c_2=c_{n-1},\cdots$ , vậy cùng theo quy tắc nhân ta có $F(f)=q^{[\dfrac{n+1}{2}]}$ . Như thế đáp số của bài toán là $\dfrac{1}{2}(q^n+q^{[\dfrac{n+1}{2}]}).$

Bài 2. Cho $n$ và $q$ là các số nguyên dương. Chứng minh rằng có

$\dfrac{1}{4}(q^{n^2}+2q^{[\dfrac{n^2+3}{4}]}+q^{[\dfrac{n^2+1}{2}]})$ cách tô màu bảng vuông $n\times n$ bởi $q$ màu.

Lời giải sơ lược. Lời giải y hệt như trường hợp trên. Ta đánh số các ô của bảng theo kiểu xoáy ốc, chia hai trường hợp $n$ chẵn, lẻ cho dễ đánh số. Tập $X$ bây giờ là tập tất cả các bộ $(c_1,c_2,\cdots,c_{n^2})$ , nhóm $G$ bây giờ là nhóm con cyclic cấp $4$ sinh bởi phép quay $+90^0$ của $S_{n^2}$ .

Chú ý. Khi $n=3,q=n$ ta có bài số 5 trong VMO 2010.

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$