Định lý không điểm tổ hợp

Định lý không điểm tổ hợp
Trương Phước Nhân, 30/07/2017

Bài toán : (Combinatorial Nullstellensatz )
Cho đa thức P  x1 , x2 ,..., xn    x1, x2 ,..., xn  có bậc deg P  t1  t2  ...  tn với ti là các số nguyên không
âm và hệ số của đơn thức x1t1 x2t2 ...xntn khác 0. Nếu S1 , S2 ,..., Sn  sao cho Si  ti thì tồn tại bộ
 s1 , s2 ,..., sn   S1  S2  ... Sn sao cho P  s1 , s2 ,..., sn   0 .
Chứng minh thứ 1: (Chứng minh theo lối đệ qui) Ta chứng minh qui nạp theo deg P . Trường hợp
deg P  1 thì khẳng định của bài toán là hiển nhiên. Giả sử khẳng định của bài toán đã được kiểm chứng với
mọi đa thức P sao cho deg P  d .
Ta cần chứng minh bài toán vẫn còn đúng với các đa thức P mà deg P  d .
Giả sử phản chứng rằng tồn tại một đa thức P  s1 , s2 ,..., sn   0 với mọi  s1 , s2 ,..., sn   S1  S2 ...  Sn .(*)
Do deg P  t1  t2  ...  tn  0 . Không mất tính tổng quát ta có thể giả sử t1  0 . Ta có định s1  S1 . Coi P
như một đa thức theo biến x1 còn x2 ,.., xn đóng vài trò là các tham số.
Thực hiện thuật toán chia ta được :
P   x1  s1  Q  R , trong đó deg x1 Q  deg x1 P  deg P  1 và deg x1 R  0 (**)
Do giả thiết , đa thức Q phải chứa đơn thức x1t1 1 x2t2 ...xntn với hệ số khác 0 .
Thay x1  s1 và  s2 ,..., sn   S2  ...  Sn vào (**) và sử dụng (*) ta được :
P  s1 , s2 ,..., sn    s1  s1  Q  s1 , s2 ,..., sn   R  s2 ,..., sn  ( lưu ý : do deg x1 R  0 )
 0  R  s2 ,..., sn 
hay R  s2 ,..., sn   0 với mọi  s2 ,..., sn   S2  ...  Sn
Thay kết quả vừa tìm được vào (**) ta suy ra :
   
Q s1 , s2 ,..., sn  0 với mọi s1 , s2 ,..., sn   S1 \ s1   S2 ...  Sn
S1
Lưu ý : đa thức Q có bậc deg Q   t1  1  t2  ...  tn và hệ số của đơn thức x1t1 x2t2 ...xntn khác 0 và
t1
   
Q s1 , s2 ,..., sn  0 với mọi s1 , s2 ,..., sn  S1  S2 ...  Sn . Điều này mâu thuẫn với giả thiết qui nạp.
S1
Từ đây ta suy ra điều phải chứng minh.

Chứng minh thứ 2: ( Chứng minh theo lối kiến thiết )
Ta cần đến bổ đề sau :
Bổ đề :
Cho P   x1 , x2 ,..., xn  là một đa thức n biến thỏa mãn deg xi P  di với mọi i  1,2,..., n .Cho Si  ,
i  1, 2,..., n là các tập với Si  di  1 .Khi đó , nếu P  s1 , s2 ,..., sn   0 với mọi  s1 , s2 ,..., sn   S1  S2 ...  Sn
thì P  0
Chứng minh bổ đề : Ta thực hiện qui nạp theo số biến. Trường hợp n  1 là hiển nhiên suy ra từ định lí cơ
dn
bản của đại số. Ta viết P  x1 , x2 ,..., xn    Pj  x1 , x2 ,..., xn 1 xnj , trong đó mỗi Pj là một đa thức theo n  1
j 0
biến x1 , x2 ,..., xn và deg xi Pj  di với i  1,2,..., n 1 và j  0,1,..., dn .

Bằng cách cố định  s1 , s2 ,..., sn1   S1  S2  ...  Sn1 thì đa thức theo biến xn , P  s1 , s2 ,..., sn1 , xn  có d n  1
không điểm nghiệm . Do đó ta phải có Pj  x1 , x2 ,..., xn1   0 với j  0,1,..., dn mọi
 s1 , s2 ,..., sn1   S1  S2  ... Sn1 . Theo giả thiết qui nạp ta suy ra Pj  0 với mọi j  0,1,..., dn . Vậy P  0 .
Trở lại với vấn đề ban đầu, tương tự như trong chứng minh thứ 1, giả sử phản chứng rằng tồn tại một đa thức
P  s1 , s2 ,..., sn   0 với mọi  s1 , s2 ,..., sn   S1  S2 ...  Sn .(*)
Để áp dụng bổ đề ta phải xây dựng đa thức P từ đa thức P sao cho deg xi P  ti và giá trị của P và P trùng
nhau trên S1  S2  ...  Sn với Si  ti  1 , không giảm tính tổng quát ta có thể giả sử Si  ti  1 .
Đặt Qi  xi  :   xi  s  . Ta thực hiện thuật toán sau : “Nếu có một đơn thức cx1m1 x2m2 ...xnmn trong P mà
sSi
Qi  xi  ”.
m  ti 1
mi  ti với một chỉ số i nào đó thì ta thay thế ximi bởi ximi  xi i
Ta có một số nhận xét sơ bộ sau: Do deg Qi  Si  ti  1 nên sau mỗi lần ta thực hiện thuật toán trên thì đơn
thức x1m1 x2m2 ...xnmn bị thay thế bởi tổng của một số đơn thức khác , nhưng tất cả các đơn thức đó đều có bậc
nhỏ hơn m1  m2  ...  mn . Do vậy thuật toán này phải dừng lại sau một số hữu hạn bước.
Gọi P là đa thức sau cùng nhận được từ thuật toán. Mỗi phép biến đổi
cx1m1 ...ximi ...xnmn  
cx1m1 ... ximi  xi i  i Qi  xi  ...xnmn tương ứng với một phép trừ đa thức P cho một đa thức
m  t 1
m  ti 1
có dạng RiQi trong đó Ri  cx1m1 ...xi i ...xnmn .Do đó nếu xét quá trình thực hiện cho tất cả các đơn thức
thì ta có P  P   R1Q1  ...  RnQn  , ở đây Ri là tổng của các Ri ( mỗi đơn thức x1m1 x2m2 ...xnmn trong P có
mi  ti đều cho ta một Ri , ta thực hiện thuật toán cho tất cả các đơn thức như vậy , ta sẽ thu được các Ri ).
Bởi vì đa thức P nhận được cuối cùng từ thuật toán nên lũy thừa của mỗi biến xi trong P tối đa chỉ có thể
là ti . Theo cách ta xây dựng thì Qi  si   0 với mọi si  Si . Do đó
P  s1 ,..., sn   P  s1 ,..., sn  với mọi  s1 , s2 ,..., sn   S1  S2  ...  Sn
 P  s1 ,..., sn   0 với mọi  s1 , s2 ,..., sn   S1  S2  ...  Sn
Áp dụng bổ đề cho đa thức P ta suy ra P  0 (*)
Nhận thấy đơn thức cx1t1 x2t2 ...xntn trong đa thức P không hề thay đổi qua quá trình thực hiện thuật toán vì nó
không chứa số mũ quá lớn để phải thay thế hay nói cách khác đa thức P có hệ số của đơn thức x1t1 x2t2 ...xntn là
c  0 ( theo giả thiết đối với đa thức P ) . Điều này mâu thuẫn với (*) . Ta kết thúc chứng minh của định lý
Combinatorial Nullstellatz .
Tài liệu tham khảo :
[1]. Wikipedia
[2]. Trần Nam Dũng, Đa thức và ứng dụng trong các bài toán tổ hợp, Tạp chí Toán học tuổi trẻ
[3]. Vũ Thế Khôi, Định lý Không điểm Tổ Hợp, Tạp chí Pi Tập 1 số 1.
[4]. Trần Minh Hiền, Định lý Cauchy – Davenport và ứng dụng, Tạp chí Epsilon số 10.
[5]. Andrei Frimu, Marcel Teleuca, Applications of Combinatorial Nullstellensataz, Gazeta Matematica

Định lý không điểm tổ hợp

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Định lý không điểm tổ hợp

Uploaded by

Copyright:

Available Formats

Định lý không điểm tổ hợp

Trương Phước Nhân, 30/07/2017

Từ đây ta suy ra điều phải chứng minh.

biến x1 , x2 ,..., xn và deg xi Pj  di với i  1,2,..., n 1 và j  0,1,..., dn .

You might also like