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.

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

Functional equations on real line I

Trong mục này, qua các ví dụ và bài tập, chúng tôi sẽ giới thiệu các kỹ thuật cơ bản để giải các phương trình hàm trên tập số thực.

Ví dụ 1. Tìm tất cả các hàm số $f:\mathbb{R}\to\mathbb{R}$ sao cho

$f(x)f(y)=xy-f(x+y),\quad \forall x,y\in\mathbb{R}.$

Lời giải. Giả sử $f$ là một hàm số thỏa mãn yêu cầu của đề bài, khi đó

$f(x)f(y)=xy-f(x+y),\quad \forall x,y\in\mathbb{R}.\quad (1)$

Trong (1), cho $x=y=0$ ta có $f(0)^2=-f(0)$ , suy ra $f(0)=0$ hoặc $f(0)=-1$ . Nếu $f(0)=0$ thì trong (1), chọn $y=0$ ta có $f(x)=0$ với mọi số thực $x$ . Kiểm tra ta thấy hàm số này không thỏa mãn. Bây giờ ta xét trường hợp $f(0)=-1$ .

Trong (1), cho $x=1$ và $y=-1$ ta có $f(1)f(-1)=0$ , suy ra $f(1)=0$ hoặc $f(-1)=0$ .

Trường hợp 1: $f(1)=0$ .

Trong (1), chọn $y=1$ , ta có $f(x+1)=x$ với mọi số thực $x$ , suy ra $f(x)=x-1,\quad\forall x\in\mathbb{R}.$

Trường hợp 2: $f(-1)=0$ .

Trong (1), chọn $y=-1$ , ta có $f(x-1)=-x$ với mọi số thực $x$ , suy ra $f(x)=-x-1,\quad\forall x\in\mathbb{R}.$

Khi $f(x)=x-1$ thì với mỗi số thực $x$ và $y$ , ta có

$xy-f(x+y)=xy-(x+y-1)=(x-1)(y-1)=f(x)f(y),$

suy ra hàm số này thỏa mãn yêu cầu của đề bài.

Khi $f(x)=-x-1$ thì với mỗi số thực $x$ và $y$ , ta có

$xy-f(x+y)=xy+(x+y+1)=(-x-1)(-y-1)=f(x)f(y),$

suy ra hàm số $f(x)=-x-1$ cũng thỏa mãn.

Vậy có hai hàm số thỏa mãn yêu cầu của đề bài, đó là $f(x)=x-1$ và $f(x)=-x-1$ . $\Box$

Ví dụ 2. Tìm tất cả các hàm số $f:\mathbb{R}\to\mathbb{R}$ thỏa mãn

$f(f(x)+y)=yf(x-f(y)),\quad\forall x,y\in\mathbb{R}.$

Lời giải. Giả sử $f$ là một hàm số thỏa mãn yêu cầu của đề bài. Khi đó

$f(f(x)+y)=yf(x-f(y)),\quad\forall x,y\in\mathbb{R}.\quad (1)$

Trong (1), chọn $y=0$ , ta có $f(f(x))=0$ với mọi số thực $x$ . Từ đây, bằng cách thay $x$ bởi $f(y)$ vào (1), ta có $f(y)=f(0)y$ với mọi số thực $y$ . Suy ra $f(0)=0$ và $f(x)=0$ với mọi số thực $x$ . Ngược lại, kiểm tra thấy hàm số $f(x)=0$ thỏa mãn.

Vậy có đúng một hàm số thỏa mãn yêu cầu của đề bài, đó là $f(x)=0$ với mọi số thực $x$ . $\Box$

Ví dụ 3. Tìm tất cả các hàm số $f:\mathbb{R}\to\mathbb{R}$ thỏa mãn

$\displaystyle f(xy)=\frac{f(x)+f(y)}{x+y}$

với mọi số thực $x$ và $y$ sao cho $x+y\not=0.$

Lời giải. Giả sử $f$ là một hàm số thỏa mãn yêu cầu của đề bài. Khi đó

$\displaystyle f(xy)=\frac{f(x)+f(y)}{x+y}$

với mọi số thực $x$ và $y$ sao cho $x+y\not=0. \quad (*)$

Từ $(*)$ , với $x=0$ và $y=1$ ta có $f(1)=0$ . Vẫn từ $(*)$ , chọn $y=1$ ta được

$xf(x)=0,\quad\forall x\in\mathbb{R}\setminus\{-1\}.$

Nói riêng, $f(2)=0$ . Từ $(*)$ , với $x=2$ và $y=0$ , ta có $f(0)=0$ . Cuối cùng, với $y=0$ , từ $(*)$ ta có $f(x)=0$ với mọi số thực $x\not=0$ . Suy ra $f(x)=0$ với mọi số thực $x$ . Ngược lại, kiểm tra thấy hàm số $f(x)=0$ thỏa mãn.

Vậy có đúng một hàm số thỏa mãn yêu cầu của đề bài, đó là $f(x)=0$ với mọi số thực $x$ . $\Box$

Ví dụ 4. Tìm tất cả các hàm số $f:\mathbb{R}\to\mathbb{R}$ thỏa mãn

$xf(y)+yf(x)=(x+y)f(x)f(y),\quad\forall x,y\in\mathbb{R}.$

Lời giải. Giả sử $f$ là một hàm số thỏa mãn yêu cầu của đề bài. Khi đó

$xf(y)+yf(x)=(x+y)f(x)f(y),\quad\forall x,y\in\mathbb{R}.\quad (1)$

Từ (1), với $x=y=1$ ta có $f(1)^2=f(1)$ , suy ra $f(1)=0$ hoặc $f(1)=1$ . Nếu $f(1)=1$ thì với $y=1$ , từ (1) ta có $f(x)=0$ với mọi số thực $x$ . Kiểm tra ta thấy hàm số này thỏa mãn. Bây giờ ta xét trường hợp $f(1)=1$ .

Trong (1), chọn $y=1$ và để ý $f(1)=1$ , ta có $xf(x)=x$ với mọi số thực $x$ . Suy ra tồn tại số thực $a$ để

$f(x)=\begin{cases}1,\quad x\not=0\\ a,\quad x=0.\end{cases}$

Kiểm tra cẩn thận ta thấy hàm số này cũng thỏa mãn.

Vậy các hàm số phải tìm là $f(x)=0$ với mọi số thực $x$ , hoặc

$f(x)=\begin{cases}1,\quad x\not=0\\ a,\quad x=0.\end{cases}$

Ở đây $a$ là một số thực. $\Box$

Ví dụ 5. Tìm tất cả các hàm số $f:\mathbb{R}\to\mathbb{R}$ thỏa mãn

$f(x+y) = \max(f(x),y) + \min(f(y),x)$

với mọi số thực $x$ và $y$ .

Lời giải. Giả sử $f$ là một hàm số thỏa mãn yêu cầu của đề bài. Khi đó

$f(x+y) = \max(f(x),y) + \min(f(y),x)$

với mọi số thực $x$ và $y.\quad (*)$

Từ $(*)$ , lần lượt thay $x=0$ và $y=0$ , ta có

$f(y) = \max(f(0),y) + \min(f(y),0),\quad\forall y\in\mathbb{R},$

và

$f(x) = \max(f(x),0) + \min(f(0),x),\quad\forall x\in\mathbb{R}.$

Suy ra với mỗi số thực $x$ ,

$2f(x)=f(x)+f(x)=(f(0)+x)+(f(x)+0),$

do đó $f(x)=x+f(0),\quad\forall x\in\mathbb{R}$ . Sử dụng điều này, khi thay $x=0$ và $y=f(0)$ , từ $(*)$ ta có $f(0)=\min (2f(0),0)$ . Suy ra $f(0)=0$ , và $f(x)=x$ với mọi số thực $x$ . Ngược lại, kiểm tra thấy hàm số $f(x)=x$ thỏa mãn.