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

- Định lý không điểm tổ hợpTrương Phước Nhân Bài toán : (Combinatorial Nullstellensatz )Cho đa thức P  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.
- S1  S2.
- Sn sao cho P  s1 , s2.
- 0 .Chứng minh thứ 1: (Chứng minh theo lối đệ qui) Ta chứng minh qui nạp theo deg P .
- Giả sử khẳng định của bài toán đã được kiểm chứng vớimọ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.
- 0 với mọi  s1 , s2.
- Sn .(*)Do deg P  t1  t2.
- Coi Pnhư 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.
- ta được : P  s1 , s2.
- s1  s1  Q  s1 , s2.
- sn  hay R  s2.
- 0 với mọi  s2.
- sn  0 với mọi s1.
- Sn S1Lưu ý : đa thức Q có bậc deg Q.
- tn và hệ số của đơn thức x1t1 x2t2 ...xntn khác 0 và t1.
- S1Từ đây ta suy ra điều phải chứng minh.Chứng minh thứ 2.
- 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 là các tập với Si  di  1 .Khi đó , nếu P  s1 , s2.
- xn 1 xnj , trong đó mỗi Pj là một đa thức theo n  1 j 0biến x1 , x2.
- dn .Bằng cách cố định  s1 , s2.
- Sn1 thì đa thức theo biến xn , P  s1 , s2.
- sn1 , xn  có d n  1không điểm nghiệm .
- dn mọi s1 , s2.
- Theo giả thiết qui nạp ta suy ra Pj  0 với mọi j  0,1.
- 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ứcP  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ùngnhau 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.
- 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.
- ti 1mi  ti với một chỉ số i nào đó thì ta thay thế ximi bởi ximi  xi iTa 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ì đơnthứ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ậcnhỏ hơn m1  m2.
- 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.
- 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.
- cx1m1 ...xi i ...xnmn .Do đó nếu xét quá trình thực hiện cho tất cả các đơn thứcthì ta có P  P.
- 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 .
- Do đó P  s1.
- sn  với mọi  s1 , s2.
- Sn  P  s1.
- 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.
- 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]

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt