Một bài toán về tập hợp thỏa mãn điều kiện tổng tự do

Trong bài viết này, chúng ta sẽ nói về một kết quả trong lý thuyết số tổ hợp liên quan tới tổng tự do của một tập con trong một nhóm abel $G$. 

Định nghĩa. Một tập con $A$ của nhóm abel $G$ được gọi là tổng tự do nếu $(A+A) \cap A = \emptyset$, nghĩa là, không tồn tại $a,b,c \in A$ sao cho $a+b = c$. 

Năm 1965, Paul Erdos đưa ra kết quả dưới đây: 

Định lý 1. Trong một tập $n$ số nguyên bất kì, luôn tồn tại một tập con $X$ với $|X| > n/3$ sao cho không tồn tại $a,b,c \in X$ thỏa mãn $a+b = c$. 

Chứng minh. Gọi tập hợp $n$ số nguyên là $A = \{a_1,a_2,\dots,a_n\}$. Xét $p = 3k + 2$ là một số nguyên tố thỏa mãn $ p > 2 \max_{i} |a_i|$ và đặt $B = \{k+1,k+2,\dots, 2k+1\}.$ Khi đó $B$ là một tập thỏa mãn điều kiện tổng tự do trong nhóm cyclic $\mathbb{Z}_p$ và 

$$ \dfrac{|B|}{p-1} = \dfrac{k+1}{3k+2} > 0.$$ 

Bây giờ, chọn ngẫu nhiên một số tự nhiên $x$ từ tập $\{1,2,\dots,p-1\}$ với xác suất các phần tử được chọn tuân theo phân bố đều và định nghĩa $d_i$ với $0\leq d_i \leq p-1$ xác định bởi 

$$ xa_i \equiv d_i \, (\mathrm{mod}\, p)  \quad \text{ với mọi  } i = 1,2,\dots, n.$$

Rõ ràng, với mỗi $i$ cố định, $1 \leq i \leq n$, vì $x$ chọn ngẫu nhiên trong các số $1,2,\dots,p-1$ nên $d_i$ nhận ra trị ngẫu nhiên trong các số $1,2,\dots,p-1,$ do đó ta thu được 

$$Pr\left( d_i \in B \right) = \dfrac{|B|}{p-1} > \dfrac{1}{3}.$$  

Suy ra giá trị kỳ vọng của số lượng $a_i$ sao cho $d_i \in B$ lớn hơn $\dfrac{n}{3}$. Điều này dẫn tới tồn tại $x \in \{1,2,\dots,p-1\}$ và tập con $X$ của $A$ sao cho $|X| \dfrac{n}{3}$ sao cho $xa \, (\mathrm{mod}\, p) \in B$ với mọi $a \in X$. Rõ ràng, $X$ thỏa mãn tính chất tổng tự do, tức không tồn tại $a,b,c \in X$ sao cho $a+b = c$, vì ngược lại thì $xa + xb \equiv xc (\mathrm{mod} \, p)$ và $xa, xb, xc \in B$, mâu thuẫn với việc $B$ thỏa mãn tính chất tổng tự do.  Ta chứng minh xong kết quả của Định lý 1. 

Một câu hỏi tự nhiên được đặt ra là liệu Định lý 1 có đúng cho trường hợp số thực hay không?  Câu là trả lời là có, tuy nhiên chúng ta không thể áp dụng trực tiếp cách chứng minh của trường hợp số nguyên cho câu hỏi tổng quát này. Phần còn lại của bài viết này, chúng ta sẽ tìm hiểu một chứng minh cho trường hợp các số thực, và rất đặc biệt, cách chứng minh sắp được nêu dưới đây sử dụng một ý tưởng khá thú vị để chuyển trường hợp các số thực về số nguyên thông qua việc xem $\mathbb{R}$ là một $\mathbb{Q}$-không gian vector. 

Mệnh đề 2. Trong một tập hợp $n$ số thực bất kì, luôn tồn tại một tập con $X$ với $|X| > \dfrac{n}{3}$ thỏa mãn tính chất tổng tự do, tức không tồn tại $a,b,c \in X$ sao cho $a+b = c$. 

Chứng minh. Gọi tập hợp $n$ số thực là $A = \{a_1,a_2,\dots,a_n\}$. Ta sẽ chuyển bài toán về trường hợp các số nguyên, từ đó ta chứng minh xong bài toán. 

Xem $\mathbb{R}$ là một $\mathbb{Q}$-không gian vector, gọi $B$ là một tập độc lập tuyến tính cực đại trong $A$. Giả sử $B = \{b_1, \dots, b_m\}$ với $m \leq n,$ khi đó với mỗi $a_i \in A$, tồn tại duy nhất các số $\alpha_{1_i},\alpha_{2_i}, \dots, \alpha_{m_i} \in \mathbb{Q}$ sao cho  

$$ a_i = \alpha_{1_i} b_1 + \alpha_{2_i} b_2 + \dots + \alpha_{m_i} b_m.$$

Để ý rằng, việc chứng minh mệnh đề cho các số $a_1,a_2,\dots,a_n$ cũng tương đương với việc chứng minh mệnh đề với $k a_1, ka_2, \dots, ka_n$ vì thế, không mất tính tổng quát ta có thể giả sử $\alpha_{1_i},\alpha_{2_i}, \dots, \alpha_{m_i} \in \mathbb{Z}$. Đến đây, ta tương ứng mỗi số $a_i$ với số nguyên $f(a_i)$ xác định bởi 

$$f(a_i) = \alpha_{1_i} + \alpha_{2_i} p + \dots \alpha_{m_i} p^{m-1}$$

trong đó $p$ đủ lớn sao cho $f(a_i) \neq f(a_j)$ với mọi $i \neq j$.  Việc chọn $p$ chắc chắn tồn tại khi khi ta xem $f(a_i)$ là một đa thức theo $p$.  Đến đây, bài toán chứng minh bài toán cho các số nguyên $f(a_1), f(a_2), \dots, f(a_m)$ vì điều kiện $a+b = c$ kéo theo 

 $$f(a) + f(b) = f(c).$$

Bình luận. Nếu chúng ta làm yếu giả thiết $|X| > \dfrac{n}{3}$ thành $|X| \geq \dfrac{n}{3}$ ta có một lời giải tương tự giống chứng minh của Định lý $1$. Bằng cách xét phần lẻ của $n$ số thực ban đầu, các phần lẻ này rơi vào một trong trong ba khoảng $[0,1/3), [1/3, 2,3), [2/3, 1).$  Để ý rằng nếu hai số $a,b$ có phần lẻ cùng rơi vào một khoảng thì tổng $a+b$ có phần lẻ không rơi vào khoảng đó, vì thế theo Nguyên lý Dirichlet, ta chọn được một tập $|X| \geq \dfrac{n}{3}$ thỏa mãn điều kiện tổng tự do. 

Tài liệu tham khảo. 

[1]  N. Alon and J. Spencer, The probabilistic method 4th, Wiley series in Discrete Mathamtics and Optimization. 

Phương pháp xác suất trong tổ hợp

Tiếp theo trong chuỗi bài mình đăng trong thời gian tới sẽ nói về Phương pháp xác suất trong tổ hợp.

Hôm nay, mình sẽ bắt đầu bằng các ví dụ cơ bản và những cách tiếp cận cơ bản đầu tiên.

Số Ramsey $R(k,m)$ là số tự nhiên $n$ nhỏ nhất sao cho trong bất kì một cách tô màu các cạnh đồ thị đầy đủ $K_n$ bởi hai màu xanh và đỏ thì hoặc tồn tại một đồ thị con đơn sắc đỏ $K_k$ hoặc tồn tại một đồ thị con đơn sắc xanh $K_m.$ Năm $1929,$ Ramsey chỉ ra rằng $R(k,m)$ là một số hữu hạn với mỗi $k$ và $n.$ Mệnh đề dưới đây được cho ta một chặn dưới của số Ramsey.

Mệnh đề 1. Nếu $\binom{n}{k} \cdot 2^{1-\binom{k}{2}} < 1$ thì $R(k,k) > n.$ Do đó $R(k,k) > [2^{k/2}]$ với mọi $k \ge 3.$ Ở đây $[x]$ là phần nguyên của $x.$

Chứng minh. Ta sẽ tiếp cận bài toán này bằng phương pháp xác suất.

Xét một cách tô màu ngẫu nhiên các cạnh của $K_n$ bởi hai màu thu được bằng cách tô màu các cạnh một cách độc lập bởi hai màu xanh và đỏ với xác suất như nhau. Với một tập $R$ cố định gồm $k$ đỉnh, gọi $A_R$ là biến cố được sinh bởi đồ thị con của $K_n$ trên $R$ là đơn sắc (tức tất cả các cạnh hoặc đều được tô đỏ hoặc đều được tô xanh). Rõ ràng ta có 

$$ Pr(A_R) = \dfrac{2}{2^{\binom{k}{2}}} = 2^{1- \binom{k}{2}}.$$

Vì có tất cả $\binom{n}{k}$ cách chọn $R$ nên xác suất để có một biến cố $A_R$ xuất hiện là 

$$ \binom{n}{k} 2^{1 - \binom{n}{k}} < 1.$$

Điều này dẫn tới, tất cả các $A_R$ đều không xuất hiện có thể xảy ra với một xác suất dương, tức là không có đồ thị con đơn sắc $K_k$ của $K_n.$ Điều này dẫn tới $R(k,k) > n.$  

Chú ý với $k \geq 3$ và lấy $n = [2^{k/2}]$ thì ta có 

$$ \binom{n}{k} 2^{1-\binom{k}{2}} < \frac{2^{1+\frac{k}{2}}}{k!} \cdot \frac{n^k}{2^{k^2/2}} < 1$$

và do đó $R(k,k) > [2^{k/2}]$ với mọi $k \geq 3.$ 

Nhận xét: Về cơ bản cách giải trên có thể thực hiện lại dưới dạng phương pháp đếm trong tổ hợp.  Tuy nhiên, nó được sử dụng một cách sáng tạo hơn và trong thực tế nó là một công cụ mạnh khi chúng ta có các kết quả về xác suất như kì vọng hay các hàm moment.

Tiếp theo, chúng ta sẽ sử dụng phương pháp xác suất vào lý thuyết đồ thị để chứng minh một vài kết quả cơ bản.  

Một giải đấu trên tập $V$ có $n$ người chơi là một tập định hướng $T = (V,E)$ gồm các cạnh của đồ thị đầy đủ trên tập hợp $V.$  Theo định nghĩa được xác định đồ thị đầy đủ thì với hai phần tử $x$ và $y$ bất kì của $V$ thì hoặc $(x,y) \in E$ hoặc $(y,x) \in E$ nhưng cả hai không cùng thuộc $E.$ Cái tên giải đấu là tự nhiên, khi chúng ta có thể xem các phần tử của một tập $V$ như là các người chơi, hai phần tử $(x,y)$ là một trận đấu khi và chỉ khi $x$ đánh bại $y.$ 

Chúng ta nói $T$ có tính chất $S_k$ nếu với mọi tập hợp gồm $k$ người chơi, luôn tồn tại một người chơi khác đánh bại tất cả $k$ người chơi đó. 

Một câu hỏi được đặt ra bởi Erdos vào năm 1963: 

"Liệu có phải với mọi số k hữu hạn luôn tồn một giải đấu $T$ (có nhiều hơn $k$ đỉnh) sao cho $T$ có tính chất $S_k$?"

Vì tính hữu hạn nên chúng ta có thể cảm nhận được tính chất này đúng. 

Ta sẽ chứng minh tính chất trên bởi mệnh đề sau. 

Mệnh đề 2. Cho $n$ và $k$ là hai số tự nhiên thỏa mãn $\binom{n}{k}(1-2^{-k})^{n-k} < 1.$ Khi đó tồn tại một giải đấu trên $n$ người chơi có tính chất $S_k.$

Chứng minh. Xét một giải đấu ngẫu nhiên trên tập $V = \{ 1, 2, \dots, n \}.$ Với mỗi tập con $K$ cố định của $V$ với $|K| = k,$ gọi $A_k$ là biến cố: "Không có người chơi nào đánh bại tất cả các người chơi trong $K$". Vì với mọi $v \in V - K$ cố định thì xác suất để $v$ không đánh bại tất cả các người chơi trong $K$ là $1-2^{-k}$ nên theo tính độc lập ta có 

$$ Pr(A_K) = (1 - 2^{-k})^{n-k}.$$ 

Đều này dẫn tới 

$$Pr\left( \bigcup_{K \subset V, |K| = k } A_K \right) \leq \sum_{S \subset V, |K| =k} Pr(A_K) = \binom{n}{k}(1 - 2^{-k})^{n-k} < 1. $$

Điều này chứng tỏ, với một xác suất dương thì không có biến cố $A_K$ nào xuất hiện. Do đó, tồn tại một giải đấu trên $n$ người chơi có tính chất $S_k.$

Về cơ bản, cách tiếp cận của Mệnh đề 2 và Mệnh đề 1 là như nhau. Tuy nhiên ở Mệnh đề 2, chúng ta bắt đầu sử dụng nhiều hơn một chút của lý thuyết xác suất.  Ví dụ tiếp theo sẽ là một cách tiếp cận mới, bằng việc sử dụng Kỳ vọng của một biến ngẫu nhiên. Để bắt đầu, chúng ta nhắc lại định nghĩa tập thống trị (dominating set) của một đồ thị. 

Định nghĩa.  Một tập thống trị của đồ thị vô hướng $G = (V,E)$ là một tập $U \subset V$ sao cho mọi đỉnh $v \in V - U$ có một đỉnh kề trong $U.$ 

Ta có định lý sau. 

Định lý 3.  Cho $G  = (V,E)$ là một đồ thị có $n$ đỉnh và bậc của mỗi đỉnh không nhỏ hơn $\delta > 1.$ Khi đó $G$ có một tập thống trị có không quá $n \cdot \dfrac{ 1 + \ln(\delta + 1)}{\delta + 1}$ đỉnh. 

Chứng minh. Xét $ p \in [0,1]$ là một số tùy ý. Lấy một cách ngẫu nhiên, độc lập mỗi cạnh đỉnh của $V$ với xác suất $p.$ Gọi $X$ là tập hợp (ngẫu nhiên) của các định được chọn và $Y = Y_X$ là một tập hợp ngẫu nhiên gồm tất cả các định thuộc $V - X$ sao cho nó không có đỉnh kề trong $X.$ Rõ ràng $|X|$ là phân bố nhị thức nên $E(|X|) = np.$ Với mỗi $v \in V$ cố định, ta có 

$$ Pr(v \in Y) = Pr ( v \text{ và lân cận của } v  \text{ không thuộc } Y) \leq (1-p)^{1+\delta}.$$ 

Sử dụng tính tuyến tính của kì vọng, chú ý rằng biến ngẫu nhiên $|Y|$ có thể viết thành tổng của $n$ biến ngẫu nhiên $\chi_v (v \in V)$ trong đó $\chi_v  = 1$ nếu $v \in Y$ và $\chi_v = 0$ nếu ngược lại.  Từ đây ta thu được 

$$ E(|X| + |Y| ) = E(|X|) + E(|Y|) = np + \sum_{ v \in V} E(\chi_v) \leq np + n(1-p)^{1+\delta}.$$ 

Điều này dẫn tới, tồn tại ít nhất một cách chọn $X \subset V$ sao cho $|X| + |Y_X| \leq np + n(1-p)^{1+\delta}.$ 

Đặt $U = X \cup Y_X,$ thì rõ ràng $U$ là một tập thống trị của $G$ với lực lượng không vượt quá $np + n(1-p)^{1+\delta}.$  

Chú ý rằng vì $p$ được chọn tùy ý nên ta sẽ chọn $p$ sao cho $np + n(1-p)^{1+\delta}$ đạt giá trị nhỏ nhất. Bằng đạo hàm và tính toán trực tiếp, ta thu được $np+n(1-p)^{1+\delta}$ nhỏ nhất khi 

$$ p = \frac{\ln(1+\delta)}{1 + \delta}.$$ 

Thay $p$ vào ta thu được $|U|$ không vượt quá $n \cdot \frac{1 + \ln(1+\delta)}{1 + \delta}.$

Nhận xét. Phía trên là các ví dụ đầu tiên trong việc sử dụng phương pháp xác suất để chứng minh các định lý và mệnh đề trong tổ hợp. Nó là các ví dụ đơn giản nhưng chứa các ý tưởng quan trọng trong việc tiếp cận vấn đề. 

Các Blog tiếp theo của mình sẽ tiếp tục trình bày về phương pháp này với các vấn đề sâu hơn. Cũng như sử dụng các công cụ mạnh hơn của xác suất để giải quyết các bài toán tổ hợp trong hình học tổ hợp cũng như tổ hợp cộng tính.

Representation Theory

Trong bài viết này, chúng ta sẽ đề cập đến lý thuyết biểu diễn nhóm.
Kí hiệu
         $\mathbb{F}$ là một trường
         $V$ là một không gian vecto trên $\mathbb{F}.$
         $G$ là một nhóm hữu hạn.
         $GL_n(\mathbb{F})$ là nhóm các ma trận trong nghịch với các phần tử của ma trận nằm trong trường $\mathbb{F}.$

Định nghĩa 1. Cho $G$ là một nhóm hữu hạn, $\mathbb{F}$
       (1) Một biểu diễn tuyến tính của $G$ là một đồng cầu đi từ $G$ vào $GL(V).$ Bậc của biểu diễn là chiều của không gian $V.$
       (2) Cho $n \in \mathbb{Z}^+$. Một biểu diễn ma trận của $G$ là một đồng cấu từ $G$ vào $GL_n(\mathbb{F}).$
       (3) Một biểu diễn tuyến tính hay một biểu diễn ma trận được gọi là trung thành nếu nó là đơn ánh.
        (4) Vành nhóm của $G$ trên $\mathbb{F}$ là tập hợp các tổng hình thức có dạng $$ \sum_{g \in G} \alpha_g g, \alpha_g \in \mathbb{F}$$ với hai phép tính cộng và nhân $(\alpha g) (\beta h) = (\alpha \beta)(gh).$

Khi chúng ta muốn làm rõ trường biểu diễn $\mathbb{F}$ thì ta sẽ nói $\mathbb{F}-representation.$
Chú ý rằng, trong trường hợp $V$ là một không gian vecto có chiều bằng $n,$ khi đó bằng cách cố định một cơ sở của $V$ ta thu thu được một đẳng cấu $GL(V) \cong GL_n(\mathbb{F}).$ Do đó, một biểu thị tuyến tính của $G$ trên một không gian vecto hữu hạn chiều cho ta một biểu diễn ma trận và ngược lại.

Sau đây, chúng ta sẽ đi vào một vài ví dụ của thể của biểu diễn và thảo luận về sự tương ứng giữa biểu diễn của $G$ và $\mathbb{F}G - modules$
Đầu tiên, giả sử rằng $\varphi: G \to GL(V)$ là một  biểu diễn của $G$ trên $\mathbb{F}-$ không gian vecto $V.$ Khi đó nếu $G = \{ g_1, g_2, \dots, g_n\}$ thì với mọi $i \in \{1,2,\dots,n\}$ ta có $\varphi(g_i)$ là một phép biến đổi tuyến tính từ $V$ và chính nó. Xem $V$ như là một $\mathbb{F}G-modules$ bằng cách định nghĩa tác động của vành phần tử lên các phần của $V$ như sau:
$$ \left( \sum_{i=1}^{n} \alpha_i g_i\right)\cdot v = \sum_{i=1}^{n} \alpha_i \varphi(g_i) (v),$$ với mọi  $\sum_{i=1}^{n} \alpha_i g_i \in \mathbb{F}G, v \in V.$


Định lý 2. Có một tương tương 1-1 giữa $\mathbb{F}G-modules$ và cặp $(V,\varphi).$  Cụ thể
$$\left\{ V \text{ là một } FG-module \right\} \leftrightarrow \left\{ V \text{ là một không gian vecto và } \varphi : G \to GL(V) \text{ là một biểu diễn}\right\} $$

Như vậy khi với một biểu diễn $\varphi: G \to GL(V)$ trên $F$-kgvt V$ thì tương đương với cho một $FG-module V.$

Ví dụ 
 (1) Cho $V$ là một không gian vecto một chiều trên $F$ và đặt $V$ vào trong một $FG-module$ bởi phép tác động trái $gv  = v$ với mọi $g \in G, v \in V.$ Khi đó module này cho ta biểu diễn $\varphi: G \to GL(V)$ được định nghĩa bởi $\varphi(g) = Id_V,$ với mọi $V \in G.$  Tương ứng với biểu diễn ma trận của $G$ vào $GL_1(F)$ gửi tất cả các phần tử của nhóm vào ma trận đơn vị $1 \times  1.$

(2) Đặt $V = FG$ và xét vành như là một module trái với chính nó. Khi đó $V$ cho ta một biểu diễn của $G$ với bậc bằng |G|.

(3) Nếu $\phi : H \to GL(V)$ là motoj biểu diễn bất kì của $H$ và $\varphi: G \to H$ là một đồng cấu nhóm bất khi, khi đó hợp thành $\phi \circ \varphi$ là một biểu diễn của $G.$

(4) Một đồng cấu của $G$ vào nhóm nhân $F^{\times} = GL_1(F)$ là một biểu diễn có bậc bằng 1. Ví dụ, giả sử $G = <g> \cong Z_n$ là một nhóm cyclic cấp $n$ và $\xi$ là một căn bậc $n$ của $1$ cố định trong $F.$ Cho $g^i \mapsto \xi^i$ với mọi $i \in \mathbb{Z}.$ Biểu diễn này của $<g>$ là một biểu diễn trung thành khi và chỉ khi $\xi$ là một căn nguyên thủ bậc $n$ của $1.$

Bài viết đầu tiên

Blog này được lập ra với mục đích viết ra những gì chàng sinh viên năm cuối đang làm trên con đường tập tành học toán.
Vào cuối năm ba, tôi bắt đầu có một sự thú vị với toán học đặc biệt là tổ hợp cộng tính và lý thuyết đồ thị.
Từ nay, tôi sẽ chia sẻ những vấn đề về tổ hợp cộng tính và lý thuyết đồ thị lên Blog này để mọi người có thể theo dõi.