September 2014 – T's Lab

Trong bài này tôi sẽ giới thiệu một chứng minh của định lí Cauchy-Davenport.

Định lí Cauchy – Davenport. Cho số nguyên tố $p$ và hai tập con khác rỗng $A,B$ của $\mathbb{Z}/p\mathbb{Z}.$ Khi đó

$|A+B|\geq\min (p,|A|+|B|-1).$

Chứng minh. Ta chứng minh khẳng định bằng quy nạp theo $|B|$ . Khi $|B|=1$ ta có

$|A+B|=|A|=\min (p,|A|)=\min (p,|A|+|B|-1).$ Suy ra khẳng định đúng khi $|B|=1$ . Khi $|B|=2$ ta viết $B=\{b_1,b_2\}$ và $A=\{a_1,a_2,\ldots,a_m\},$ ta có ngay $|A+B|\geq m$ .

Nếu $|A+B|= m$ thì $\{b_1+a_1,\ldots,b_1+a_m\}=\{b_2+a_1,\ldots,b_2+a_m\},$ suy ra $mb_1\equiv mb_2\pmod{p}$ , hay $m=p$ . Khi đó $|A+B|=p\geq\min (p,|A|+|B|-1).$

Nếu $|A+B|>m$ thì $|A+B|\geq m+1\geq\min (p,m+1)=\min (p,|A|+|B|-1).$

Vậy khẳng định đúng khi $|B|=2$ . Giả sử khẳng định đúng với mỗi tập $B$ thỏa mãn $|B|<n,$ trong đó $n\geq 3.$ Ta sẽ chứng minh khẳng định đúng với mọi tập $B$ có $|B|=n.$ Xét một tập $B$ thỏa mãn $|B|=n$ . Đặt $|A+B|=l,|A|=m$ và viết $B=\{b_1,b_2,\ldots,b_n\}.$ Xét ba trường hợp

Trường hợp 1. $l\geq p.$

Ta có $|A+B|=l\geq p\geq\min (p,|A|+|B|-1).$

Trường hợp 2. $m+n>p.$

Ta có $A+B=\{0,1,2,\ldots,p-1\}$ , thật vậy với mỗi $g\in \{0,1,2,\ldots,p-1\}$ , hai tập $g-A$ và $B$ có giao khác rỗng vì chúng là các tập con của tập $\{0,1,2,\ldots,p-1\}$ và có tổng số phần tử lớn hơn $p$ . Lấy $h\in g-A\cap B$ ta có ngay $g=b=g-a\,\, (a\in A,b\in B),$ suy ra $g=a+b\in A+B$ . Từ đây ta có $|A+B|=p\geq\min (p,|A|+|B|-1).$

Trường hợp 3. $l<p$ và $m+n\leq p.$

Ở trường hợp này thì $\min (p,|A|+|B|-1)=\min (p,m+n-1)=m+n-1.$ Áp dụng giả thiết quy nạp cho hai tập $C=A+B$ và $\{b_1,b_n\}$ ta có $|C+\{b_1,b_n\}|\geq\min (p,|C|+|\{b_1,b_n\}|-1)=\min (p,l+1)=l+1,$ suy ra $C+b_1\not = C+b_n$ , do đó tồn tại số nguyên $x$ sao cho $x-b_1\in A+B$ và $x-b_n\not\in A+B$ . Từ đây ta thấy tồn tại số nguyên dương $r<n$ sao cho $x-b_i\in A+B,\,\forall i=\overline{1,r}$ và $x-b_i\not\in A+B,\,\forall i=\overline{r+1,n}$ . Áp dụng giả thiết quy nạp cho hai tập $A$ và $B^{\prime}=\{b_{r+1},b_{r+2},\ldots,b_n\}$ ta có

$|A+B^{\prime}|\geq \min (p,|A|+|B^{\prime}|-1)=\min (p,m+n-r-1)=m+n-r-1.$ Ta có $x-b_i\not\in A+B^{\prime},\,\forall i=\overline{1,r}$ , vì nếu chẳng hạn $x-b_1\in A+B^{\prime}$ thì

$x-b_1= a+b_{s}\Rightarrow x-b_s\in A+B,$ điều này trái với cách chọn $r$ . Vậy $|A+B|\geq r+|A+B^{\prime}|\geq r+m+n-r-1=m+n-1,$ và định lí được chứng minh. $\Box$

Bằng quy nạp ta chứng minh được kết quả sau.

Hệ quả. Cho số nguyên dương $h>1,$ số nguyên tố $p$ và $h$ tập con khác rỗng $A_1,$ $A_2,\ldots,$ $A_h$ của $\mathbb{Z}/p\mathbb{Z}.$ Khi đó $\displaystyle \mid A_1+A_2+\cdots+A_h\mid \geq \min \left(p,\sum_{i=1}^h\mid A_i\mid-h+1\right).$