Thứ Tư, 31 tháng 3, 2021

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. 



Không có nhận xét nào:

Đăng nhận xét