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 khác rỗng các số nguyên A,B. Với mỗi tập X các số nguyên, ký hiệu (X)_p là tập tất cả các số tự nhiên r<p sao cho tồn tại x\in X thỏa mãn x\equiv r\pmod{p}. Khi đó ta có |(A+B)_p|\geq\min (p,|(A)_p|+|(B)_p|-1).


Chứng minh. Ta chứng minh bằng quy nạp theo |(B)_p|.
Khi |(B)_p|=1 ta có |(A+B)_p|=|(A)_p|=\min (p,|(A)_p|)=\min (p,|(A)_p|+|(B)_p|-1). Suy ra khẳng định đúng với |(B)_p|=1.
Khi |(B)_p|=2 ta viết (B)_p=\{b_1,b_2\}(A)_p=\{a_1,a_2,\cdots,a_m\}.
Ta có |(A+B)_p|\geq m, nếu |(A+B)_p|= m thì
\{(b_1+a_1)_p,(b_1+a_2)_p,\cdots,(b_1+a_m)_p\}=\{(b_2+a_1)_p,(b_2+a_2)_p,\cdots,(b_2+a_m)_p\}.
Suy ra tồn tại song ánh f:[m]\to [m] sao cho
(b_1+a_i)_p=(b_2+a_{f(i)})_p\,\,\forall i\in [m],
do đó mb_1\equiv mb_2\pmod{p}, vì b_1\not\equiv b_2\pmod{p} nên từ đó ta có m=p, suy ra
|(A+B)_p|=p\geq\min (p,|(A)_p|+|(B)_p|-1).
Nếu |(A+B)_p|>m thì
|(A+B)_p|\geq m+1\geq\min (p,m+1)=\min (p,|(A)_p|+|(B)_p|-1).
Vậy khẳng định đúng với |(B)_p|=2.
Giả sử khẳng định đúng với mỗi tập B thỏa mãn |(B)_p|<n\,\, (n\geq 3,n\in\mathbb{Z}).
Bây giờ ta xét một tập B thỏa mãn |(B)_p|=n.
Đặt |(A+B)_p|=l,|(A)_p|=m và viết (B)_p=\{b_1,b_2,\cdots,b_n\}.
Xét ba trường hợp:
Trường hợp 1: l\geq p

Ta có |(A+B)_p|=l\geq p\geq\min (p,|(A)_p|+|(B)_p|-1).
Trường hợp 2: m+n>p
Ta có (A+B)_p=\{0,1,2,\cdots,p-1\}, thật vậy với mỗi g\in \{0,1,2,\cdots,p-1\}, hai tập (g-A)_p(B)_p có giao khác rỗng vì chúng là các tập con của \{0,1,2,\cdots,p-1\} và có tổng số phần tử lớn hơn p. Lấy h\in (g-A)_p\cap (B)_p ta có ngay g=(b)_p=(g-a)_p\,\, (a\in A,b\in B), suy ra g=(a+b)_p\in (A+B)_p.
Từ đây ta có |(A+B)_p|=p\geq\min (p,|(A)_p|+|(B)_p|-1).
Trường hợp 3: l<pm+n\leq p
Ở trường hợp này thì \min (p,|(A)_p|+|(B)_p|-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\{b_1,b_n\} ta có
|(C+\{b_1,b_n\})_p|\geq\min (p,|(C)_p|+|(\{b_1,b_n\})_p|-1)=\min (p,l+1)=l+1, suy ra (C+b_1)_p\not = (C+b_n)_p, do đó tồn tại số nguyên x sao cho (x-b_1)_p\in (A+B)_p(x-b_n)_p\not\in (A+B)_p. Từ đây ta thấy tồn tại số nguyên dương r<n sao cho (x-b_i)_p\in (A+B)_p\,\,\forall i=\overline{1,r}(x-b_i)_p\not\in (A+B)_p\,\,\forall i=\overline{r+1,n}. (1)
Áp dụng giả thiết quy nạp cho hai tập AB'=\{b_{r+1},b_{r+2},\cdots,b_n\} ta có
|(A+B')_p|\geq \min (p,|(A)_p|+|(B')_p|-1)=\min (p,m+n-r-1)=m+n-r-1.
Ta có (x-b_i)_p\not\in (A+B')_p\,\,\forall i=\overline{1,r}, vì nếu chẳng hạn (x-b_1)_p\in (A+B')_p thì x-b_1\equiv a+b_{s}\pmod{p}\,(n\geq s>r,a\in A)\Rightarrow (x-b_s)_p\in (A+B)_p,
điều này trái với cách chọn r.
Vậy |(A+B)_p|\geq r+|(A+B')_p|\geq r+m+n-r-1=m+n-1.
Định lý được chứng minh.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s