Một đồng dư modulo nguyên tố

n.t.tuan · 14-11-2007, 02:06 PM

Một đồng dư modulo nguyên tố

Hao Pan

Người dịch: Nguyễn Trung Tuân
Tặng Thầy nhân dịp 20-11-2007

Trong năm 1961, Erdos, Ginzburg, và Ziv [3] đã tìm ra định lý nổi tiếng sau đây, bây giờ nó là trung tâm của các bài toán $0- $ tổng( về các bài toán này các bạn có thể tìm trong [1],[2] và [5]).

Định lý EGZ. Giả sử $n $ là một số nguyên dương. Khi đó với mỗi dãy $a_1,a_2,\cdots,a_{2n-1} $ gồm $2n-1 $ số nguyên có một dãy con $a_{i_1},a_{i_2},\cdots, a_{i_n} $ độ dài $n $ sao cho tổng $\sum_{j=1}^na_{i_j} $ chia hết cho $n $.

Dễ kiểm tra thấy rằng định lý EGZ là nhân tính, nghĩa là, nếu mệnh đề đúng với $n=k $ và $n=l $ thì nó cũng đúng với $n=k\cdot l $. Do đó chỉ cần chứng minh định lý đúng với $n $ nguyên tố là đủ. Trong các chứng minh cổ điển của định lý, trường hợp $n $ nguyên tố thường có được từ định lý Cauchy-Davenport hoặc định lý Chevalley-Waring (xem [6]). Tuy nhiên, với sự giúp đỡ của định thức Vandermonde, Gao [4] cho một chứng minh khác của định lý EGZ dựa trên đồng dư sau

$\sum_{I\subseteq\{1,\cdots,2p-1\},|I|=p}\;(\sum_{i\in I}a_i)^{p-1}\equiv 0\pmod{p},\; (*) $

ở đó $p $ là một số nguyên tố và $a_1,\cdots,a_{2p-1} $ là các số nguyên bất kì. Chú ý rằng định lý EGZ là một hệ quả đơn giản của $(*) $ vì theo định lý Fermat nhỏ chúng ta có

$\left|\{I\subseteq\{1,2,\cdots,2p-1\}:\sum_{i\in I}a_i\equiv 0\pmod{p},|I|=p\}\right|\equiv $
$\equiv\sum_{I\subseteq\{1,\cdots,2p-1\},|I|=p}\;(1-(\sum_{i\in I}a_i)^{p-1})\equiv C_{2p-1}^p\equiv 1\pmod{p}. $

Trong bài báo này, chúng tôi sẽ chứng minh định lý sau, mà đồng dư của Gao chỉ là một hệ quả đơn giản của nó:

Định lý. Giả sử $p $ là một số nguyên tố và $k $ là một số nguyên dương thỏa mãn $k\leq p $. Cho $f(x_1,\cdots,x_k) $ là một đa thức đối xứng với hệ số nguyên biến $x_1,\cdots,x_k $. Nếu bậc của $f $ nhỏ hơn $k $ thì với một dãy bất kì gồm $p+k-1 $ số nguyên $a_1,a_2,\cdots,a_{p+k-1} $, chúng ta có

$\sum_{1\leq i_1<\cdots<i_k\leq p+k-1}\; f(a_{i_1},\cdots,a_{i_k})\equiv f(0,\cdots,0)\pmod{p} $ nếu $k=p $

và $\equiv 0\pmod{p} $ trong trường hợp còn lại.

Chứng minh. Chứng minh là sơ cấp, chỉ cần đến một tính chất số học cơ bản của hệ số nhị thức: $C_{p+k-1}^k\equiv 1\pmod{p} $ nếu $k=p $ và $\equiv 0\pmod{p} $ nếu $1\leq k<p $.

Chúng tôi sẽ chứng minh định lý bằng quy nạp theo $k $. Khi $k=1 $, vì $\deg f<k $ nên $f $ phải là một hằng số $c $. Trong trường hợp này $\sum_{1\leq i\leq p}f(a_i)=p\cdot c\equiv 0\pmod{p} $. Bây giờ giả sử rằng $k>1 $ và định lý là đúng với tất cả các giá trị nhỏ hơn $k $. Đặt $S_{f,k}(x_1,\cdots,x_{p+k-1})=\sum_{1\leq i_1<\cdots<i_k\leq p+k-1}\; f(x_{i_1},\cdots,x_{i_k}) $ và viết $f(x_1,\cdots, x_k) $ dưới dạng $f(x_1,\cdots,x_k)=\sum_{j=0}^{k-1}g_j(x_1,\cdots,x_{k-1})x_k^j $, ở đây $g_j $ là các đa thức biến $x_1,\cdots,x_{k-1} $. Từ tính đối xứng của $f $ ta có $S_{f,k} $ và tất cả $g_j $ là các đa thức đối xứng.

Tiếp theo chúng ta thấy rằng

$S_{f,k}(a_1,\cdots,a_{p+k-1})=\sum_{1\leq i_1<\cdots<i_k\leq p+k-2}\;f(a_{i_1},\cdots,a_{i_k})+ $
$+\sum_{1\leq i_1<\cdots<i_{k-1}\leq p+k-2}\; f(a_{i_1},\cdots,a_{i_{k-1}},a_{p+k-1}) $.

Do đó $S_{f,k}(a_1,\cdots,a_{p+k-1})-S_{f,k}(a_1,\cdots,a_{p+k-2} ,0) $

$=\sum_{1\leq i_1<\cdots<i_{k-1}\leq p+k-2}\;(f(a_{i_1},\cdots,a_{i_{k-1}},a_{p+k-1})-f(a_{i_1},\cdots,a_{i_{k-1}},0)) $

$=\sum_{1\leq i_1<\cdots<i_{k-1}\leq p+k-2}\;\left(\sum_{j=0}^{k-1}g_j(a_{i_1},\cdots,a_{i_{k-1}})a_{p+k-1}^j-g_0(a_{i_1},\cdots,a_{i_{k-1}})\right) $

$=\sum_{j=1}^{k-1}a_{p+k-1}^j\;\sum_{1\leq i_1<\cdots<i_{k-1}\leq p+k-2}\;g_j(a_{i_1},\cdots,a_{i_{k-1}}) $

$=\sum_{j=1}^{k-1}a_{p+k-1}^jS_{g_j,k-1}(a_1,\cdots,a_{p+k-2}) $.

Vì $k\leq p $ và $\deg g_j\leq \deg f-j<k-j $, chúng ta có thể dùng giả thiết quy nạp để có

$S_{g_j,k-1}(a_1,\cdots,a_{p+k-2})\equiv 0\pmod{p}\forall j=\overline{1,k-1} $. Do đó

$S_{f,k}(a_1,\cdots,a_{p+k-1})\equiv S_{f,k}(a_1,\cdots,a_{p+k-2},0)\pmod{p} $. Từ đây, sử dụng tính đối xứng của $S_{f,k} $, chúng ta có $S_{f,k}(a_1,\cdots,a_{p+k-1})\equiv S_{f,k}(0,\cdots,0)\pmod{p} $.

Cuối cùng, bởi định nghĩa của $S_{f,k} $, ta có $S_{f,k}(a_1,\cdots,a_{p+k-1})=C_{p+k-1}^kf(0,\cdots,0)\equiv f(0,\cdots,0)\pmod{p} $ nếu $k=p $ và $\equiv 0\pmod{p} $ nếu $1\leq k<p $.

Định lý được chứng minh.

Tài liệu tham khảo

[1]N. Alon and M. Dubiner, Zero-sum sets of prescribed size, in: "Combinatorics, Paul Erdos is Eighty", Bolyai Society, Mathematical Studies, Keszthely, Hungary, 1993, 33-50.

[2]Y. Caro, "Zero-sum problems: a survey" Discrete Math. , 152 (1996) pp. 93–113.

[3]Erdos, P., Ginzburg, A., Ziv, A. Theorem in additive number Theory,. Bull. Res. Council, Israel, 10 F(1961) 41–43.

[4]W. D. Gao - Two addition theorems on groups of prime order, J. Number Theory, Vol.56 (1996) 211-213.

[5]W.D. Gao, A. Geroldinger, On zero sum sequences in Zn ⊕ Zn Integers 3 (A8) (2003) 45 (electronic).

[6]M. B. Nathanson, Additive Number Theory: Inverse Problems and the Geometry of Sumsets, 1996.

modular · 14-11-2007, 10:59 PM

Trích:

Nguyên văn bởi n.t.tuan

Dễ kiểm tra thấy rằng định lý EGZ là nhân tính, nghĩa là, nếu mệnh đề đúng với $n=k $ và $n=l $ thì nó cũng đúng với $n=k\cdot l $.

Bác nào chứng minh hộ đoạn này được không? :burnjossstick:

adi · 16-11-2007, 05:59 PM

Mình không chứng minh được cái đó! Có ai biết cách c/m khác của EGZ nếu không dùng đồng dư của Gao không?

asimothat · 17-11-2007, 01:05 PM

anh Tuân có ebook phần này không ,đưa lên diễn đàn,chứ thời gian đâu mà ngồi trước máy tính đọc cơ chứ

n.t.tuan · 17-11-2007, 11:23 PM

Quang chắc chịu không chứng minh được tính nhân tính rồi. Để anh giúp nhé!

Trong $2kl-1 $ số nguyên, chọn $l $ số có tổng chia hết cho $l $(chọn được vì $2kl-1>2l-1 $),sau đó chọn $l $ số từ nhóm còn lại có tổng chia hết cho $l $, cứ làm như thế đến khi còn $l-1 $ số, chúng ta được $2k-1 $ nhóm, mỗi nhóm gồm $l $ số có tổng chia hết cho $l $, trong $2k-1 $ tổng này, ta chọn ra $k $ tổng có tổng chia hết cho $k $. Gom lại có đủ $kl $ số rồi đấy!

Tom · 17-11-2007, 11:37 PM

kl số đó sẽ thỏa mãn nếu gcd(k,l)=1, tuy nhiên trong chứng minh trên, thay vì chọn 2k-1 tổng, ta chọn 2k-1 số là trung bình cộng của các tổng đó là xong.

n.t.tuan · 17-11-2007, 11:42 PM

Cảm ơn Tom, đây là một chứng minh khác của EGZ.
Nguồn: Mathlinks.ro
Người post: ZetaX
[Only registered and activated users can see links. ]

14-11-2007, 02:06 PM	#1
n.t.tuan +Thành Viên+ Tham gia ngày: Nov 2007 Bài gởi: 1,250 Thanks: 119 Thanked 616 Times in 249 Posts	Một đồng dư modulo nguyên tố Một đồng dư modulo nguyên tố Hao Pan Người dịch: Nguyễn Trung Tuân Tặng Thầy nhân dịp 20-11-2007 Trong năm 1961, Erdos, Ginzburg, và Ziv [3] đã tìm ra định lý nổi tiếng sau đây, bây giờ nó là trung tâm của các bài toán $0- $ tổng( về các bài toán này các bạn có thể tìm trong [1],[2] và [5]). Định lý EGZ. Giả sử $n $ là một số nguyên dương. Khi đó với mỗi dãy $a_1,a_2,\cdots,a_{2n-1} $ gồm $2n-1 $ số nguyên có một dãy con $a_{i_1},a_{i_2},\cdots, a_{i_n} $ độ dài $n $ sao cho tổng $\sum_{j=1}^na_{i_j} $ chia hết cho $n $. Dễ kiểm tra thấy rằng định lý EGZ là nhân tính, nghĩa là, nếu mệnh đề đúng với $n=k $ và $n=l $ thì nó cũng đúng với $n=k\cdot l $. Do đó chỉ cần chứng minh định lý đúng với $n $ nguyên tố là đủ. Trong các chứng minh cổ điển của định lý, trường hợp $n $ nguyên tố thường có được từ định lý Cauchy-Davenport hoặc định lý Chevalley-Waring (xem [6]). Tuy nhiên, với sự giúp đỡ của định thức Vandermonde, Gao [4] cho một chứng minh khác của định lý EGZ dựa trên đồng dư sau $\sum_{I\subseteq\{1,\cdots,2p-1\},\|I\|=p}\;(\sum_{i\in I}a_i)^{p-1}\equiv 0\pmod{p},\; () $ ở đó $p $ là một số nguyên tố và $a_1,\cdots,a_{2p-1} $ là các số nguyên bất kì. Chú ý rằng định lý EGZ là một hệ quả đơn giản của $() $ vì theo định lý Fermat nhỏ chúng ta có $\left\|\{I\subseteq\{1,2,\cdots,2p-1\}:\sum_{i\in I}a_i\equiv 0\pmod{p},\|I\|=p\}\right\|\equiv $ $\equiv\sum_{I\subseteq\{1,\cdots,2p-1\},\|I\|=p}\;(1-(\sum_{i\in I}a_i)^{p-1})\equiv C_{2p-1}^p\equiv 1\pmod{p}. $ Trong bài báo này, chúng tôi sẽ chứng minh định lý sau, mà đồng dư của Gao chỉ là một hệ quả đơn giản của nó: Định lý. Giả sử $p $ là một số nguyên tố và $k $ là một số nguyên dương thỏa mãn $k\leq p $. Cho $f(x_1,\cdots,x_k) $ là một đa thức đối xứng với hệ số nguyên biến $x_1,\cdots,x_k $. Nếu bậc của $f $ nhỏ hơn $k $ thì với một dãy bất kì gồm $p+k-1 $ số nguyên $a_1,a_2,\cdots,a_{p+k-1} $, chúng ta có $\sum_{1\leq i_1<\cdots<i_k\leq p+k-1}\; f(a_{i_1},\cdots,a_{i_k})\equiv f(0,\cdots,0)\pmod{p} $ nếu $k=p $ và $\equiv 0\pmod{p} $ trong trường hợp còn lại. Chứng minh. Chứng minh là sơ cấp, chỉ cần đến một tính chất số học cơ bản của hệ số nhị thức: $C_{p+k-1}^k\equiv 1\pmod{p} $ nếu $k=p $ và $\equiv 0\pmod{p} $ nếu $1\leq k<p $. Chúng tôi sẽ chứng minh định lý bằng quy nạp theo $k $. Khi $k=1 $, vì $\deg f<k $ nên $f $ phải là một hằng số $c $. Trong trường hợp này $\sum_{1\leq i\leq p}f(a_i)=p\cdot c\equiv 0\pmod{p} $. Bây giờ giả sử rằng $k>1 $ và định lý là đúng với tất cả các giá trị nhỏ hơn $k $. Đặt $S_{f,k}(x_1,\cdots,x_{p+k-1})=\sum_{1\leq i_1<\cdots<i_k\leq p+k-1}\; f(x_{i_1},\cdots,x_{i_k}) $ và viết $f(x_1,\cdots, x_k) $ dưới dạng $f(x_1,\cdots,x_k)=\sum_{j=0}^{k-1}g_j(x_1,\cdots,x_{k-1})x_k^j $, ở đây $g_j $ là các đa thức biến $x_1,\cdots,x_{k-1} $. Từ tính đối xứng của $f $ ta có $S_{f,k} $ và tất cả $g_j $ là các đa thức đối xứng. Tiếp theo chúng ta thấy rằng $S_{f,k}(a_1,\cdots,a_{p+k-1})=\sum_{1\leq i_1<\cdots<i_k\leq p+k-2}\;f(a_{i_1},\cdots,a_{i_k})+ $ $+\sum_{1\leq i_1<\cdots<i_{k-1}\leq p+k-2}\; f(a_{i_1},\cdots,a_{i_{k-1}},a_{p+k-1}) $. Do đó $S_{f,k}(a_1,\cdots,a_{p+k-1})-S_{f,k}(a_1,\cdots,a_{p+k-2} ,0) $ $=\sum_{1\leq i_1<\cdots<i_{k-1}\leq p+k-2}\;(f(a_{i_1},\cdots,a_{i_{k-1}},a_{p+k-1})-f(a_{i_1},\cdots,a_{i_{k-1}},0)) $ $=\sum_{1\leq i_1<\cdots<i_{k-1}\leq p+k-2}\;\left(\sum_{j=0}^{k-1}g_j(a_{i_1},\cdots,a_{i_{k-1}})a_{p+k-1}^j-g_0(a_{i_1},\cdots,a_{i_{k-1}})\right) $ $=\sum_{j=1}^{k-1}a_{p+k-1}^j\;\sum_{1\leq i_1<\cdots<i_{k-1}\leq p+k-2}\;g_j(a_{i_1},\cdots,a_{i_{k-1}}) $ $=\sum_{j=1}^{k-1}a_{p+k-1}^jS_{g_j,k-1}(a_1,\cdots,a_{p+k-2}) $. Vì $k\leq p $ và $\deg g_j\leq \deg f-j<k-j $, chúng ta có thể dùng giả thiết quy nạp để có $S_{g_j,k-1}(a_1,\cdots,a_{p+k-2})\equiv 0\pmod{p}\forall j=\overline{1,k-1} $. Do đó $S_{f,k}(a_1,\cdots,a_{p+k-1})\equiv S_{f,k}(a_1,\cdots,a_{p+k-2},0)\pmod{p} $. Từ đây, sử dụng tính đối xứng của $S_{f,k} $, chúng ta có $S_{f,k}(a_1,\cdots,a_{p+k-1})\equiv S_{f,k}(0,\cdots,0)\pmod{p} $. Cuối cùng, bởi định nghĩa của $S_{f,k} $, ta có $S_{f,k}(a_1,\cdots,a_{p+k-1})=C_{p+k-1}^kf(0,\cdots,0)\equiv f(0,\cdots,0)\pmod{p} $ nếu $k=p $ và $\equiv 0\pmod{p} $ nếu $1\leq k<p $. Định lý được chứng minh. Tài liệu tham khảo [1]N. Alon and M. Dubiner, Zero-sum sets of prescribed size, in: "Combinatorics, Paul Erdos is Eighty", Bolyai Society, Mathematical Studies, Keszthely, Hungary, 1993, 33-50. [2]Y. Caro, "Zero-sum problems: a survey" Discrete Math. , 152 (1996) pp. 93–113. [3]Erdos, P., Ginzburg, A., Ziv, A. Theorem in additive number Theory,. Bull. Res. Council, Israel, 10 F(1961) 41–43. [4]W. D. Gao - Two addition theorems on groups of prime order, J. Number Theory, Vol.56 (1996) 211-213. [5]W.D. Gao, A. Geroldinger, On zero sum sequences in Zn ⊕ Zn Integers 3 (A8) (2003) 45 (electronic). [6]M. B. Nathanson, Additive Number Theory: Inverse Problems and the Geometry of Sumsets, 1996. __________________ T.

17-11-2007, 01:05 PM	#4
asimothat +Thành Viên+ Tham gia ngày: Nov 2007 Bài gởi: 289 Thanks: 85 Thanked 162 Times in 100 Posts	anh Tuân có ebook phần này không ,đưa lên diễn đàn,chứ thời gian đâu mà ngồi trước máy tính đọc cơ chứ __________________ Ultra

17-11-2007, 11:23 PM	#5
n.t.tuan +Thành Viên+ Tham gia ngày: Nov 2007 Bài gởi: 1,250 Thanks: 119 Thanked 616 Times in 249 Posts	Quang chắc chịu không chứng minh được tính nhân tính rồi. Để anh giúp nhé! Trong $2kl-1 $ số nguyên, chọn $l $ số có tổng chia hết cho $l $(chọn được vì $2kl-1>2l-1 $),sau đó chọn $l $ số từ nhóm còn lại có tổng chia hết cho $l $, cứ làm như thế đến khi còn $l-1 $ số, chúng ta được $2k-1 $ nhóm, mỗi nhóm gồm $l $ số có tổng chia hết cho $l $, trong $2k-1 $ tổng này, ta chọn ra $k $ tổng có tổng chia hết cho $k $. Gom lại có đủ $kl $ số rồi đấy! __________________ T.

17-11-2007, 11:42 PM	#7
n.t.tuan +Thành Viên+ Tham gia ngày: Nov 2007 Bài gởi: 1,250 Thanks: 119 Thanked 616 Times in 249 Posts	Cảm ơn Tom, đây là một chứng minh khác của EGZ. Nguồn: Mathlinks.ro Người post: ZetaX [Only registered and activated users can see links. ] __________________ T.

Ðiều Chỉnh
Tạo trang in Email trang này
Xếp Bài
Chế độ bình thường Chuyển sang chế độ Pha trộn Chuyển sang chế độ dạng cây

16-11-2007, 05:59 PM	#3
adi +Thành Viên+ Tham gia ngày: Nov 2007 Bài gởi: 21 Thanks: 0 Thanked 0 Times in 0 Posts	Mình không chứng minh được cái đó! Có ai biết cách c/m khác của EGZ nếu không dùng đồng dư của Gao không?

17-11-2007, 11:37 PM	#6
Tom +Thành Viên+ Tham gia ngày: Nov 2007 Bài gởi: 16 Thanks: 0 Thanked 0 Times in 0 Posts	kl số đó sẽ thỏa mãn nếu gcd(k,l)=1, tuy nhiên trong chứng minh trên, thay vì chọn 2k-1 tổng, ta chọn 2k-1 số là trung bình cộng của các tổng đó là xong.