ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC VƯƠNG THỊ YẾN ĐA THỨC HOÁN VỊ ĐƯỢC LUẬN VĂN THẠC SỸ TOÁN HỌC Chuyên ngành : PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số : 60 46 40 Giáo viên hướng dẫn: PGS.TS LÊ THỊ THANH NHÀN THÁI NGUYÊN, 2012 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Mục lục Mục lục Lời cảm ơn Lời nói đầu Kiến thức chuẩn bị 1.1 Kiến thức chuẩn bị nhóm 1.2 Kiến thức chuẩn bị vành 10 1.3 Kiến thức chuẩn bị trường 14 1.4 Kiến thức chuẩn bị đa thức 17 Đa thức hoán vị 20 2.1 Khái niệm đa thức hoán vị 20 2.2 Một số lớp đa thức hoán vị trường 26 2.3 Đa thức hoán vị modulo 2k 30 Kết luận 39 Tài liệu tham khảo 40 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Lời cảm ơn Đề tài thực trường Đại học Khoa học - Đại học Thái Nguyên hướng dẫn PGS.TS Lê Thị Thanh Nhàn Tơi xin bày tỏ lịng biết ơn sâu sắc, chân thành Cô Bởi giúp đỡ, bảo, khuyến khích ân cần Cơ góp phần lớn cho thành công luận văn Tơi xin bày tỏ lịng cảm ơn chân thành tới Ban lãnh đạo, Phòng Đào tạo - Khoa học Quan hệ quốc tế, Khoa Toán - Tin Trường Đại học khoa học - Đại học Thái Nguyên tạo điều kiện thuận lợi để bạn học viên cao học Khóa (2010 - 2012) học tập, nghiên cứu Tôi xin cảm ơn Thầy, Cơ GS.TSKH Hà Huy Khối, GS.TSKH Nguyễn Văn Mậu, nhà toán học hàng đầu Việt Nam giảng dạy chuyên đề cho lớp Cuối cùng, xin gửi lời cảm ơn tới gia đình, bạn bè, người thân bên, động viên, giúp đỡ để hồn thành luận văn Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Lời nói đầu Ta biết đa thức f ♣xq vành hữu hạn R gọi hốn vị đa thức hốn vị phần tử vành R, tức ánh xạ ϕ : R Ñ R cho ϕ♣aq ✏ f ♣aq phải song ánh Trong "Finite fields" xuất lần năm 1983, Lidl Niedereiter [LN] nghiên cứu tiêu chuẩn đa thức hoán vị được, dạng đặc biệt đa thức hốn vị được, nhóm đa thức hốn vị được, trường hợp ngoại lệ đa thức hoán vị đa thức hoán vị số dạng bất định Lidl Mullen [LM1,2] nghiên đa thức hoán vị trường hữu hạn Năm 1986, R A Mollin C Small [MS] đưa tiêu chuẩn đa thức hoán vị dạng xn Năm 1999, R Rivest [Riv] đưa tiêu chuẩn đa thức hoán vị modulo 2k Trong đề tài chúng tơi trình bày lại kết hai báo R.A.Mollin C.Small [MS] R.Rivest [Riv] đặc trưng tính hốn vị đa thức dạng xn đa thức dạng xk   bxj   c với ♣k → j ➙ 1q trường hữu hạn, đồng thời xét tính hốn vị đa thức dạng P ♣xq ✏ a0   a1 x     an xn với n ✏ 2k vành Z2k Luận văn gồm chương Chương trình bày kiến thức chuẩn bị nhóm, vành, trường đa thức nhằm phục vụ cho việc chứng minh kết chương sau Trong phần đầu Chương trình bày khái niệm đa thức hốn vị số ví dụ đơn giản Phần thứ Chương giành để chứng minh tiêu chuẩn hoán vị trường hữu hạn số lớp đa thức dạng xn (Định lý 2.1.7) đa thức dạng xk   bxj   c với k → j ➙ (Định lý 2.2.1) Phần cuối Chương nhằm trình bày điều kiện cần đủ để đa thức với hệ số nguyên Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn hoán vị theo modulo 2k , tức hoán vị vành Z2k (Định lý 2.3.10) Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Chương Kiến thức chuẩn bị Chương trình bày khái niệm kết chuẩn bị nhóm, vành, trường đa thức phục vụ cho chứng minh kết chương sau 1.1 Kiến thức chuẩn bị nhóm 1.1.1 Định nghĩa Nhóm tập G với phép tốn (kí hiệu theo lối nhân) thoả mãn điều kiện (i) Phép tốn có tính kết hợp: a♣bcq ✏ ♣abqc, ❅a, b, c € G (ii) G có đơn vị: ❉e € G cho ex ✏ xe ✏ x, ❅x € G (iii) Mọi phần tử G khả nghịch: Với x € G, tồn x✁1 cho xx✁1 ✏ x✁1x ✏ e €G Một nhóm G gọi nhóm giao hốn (hay nhóm Abel) phép tốn giao hốn Nếu G có hữu hạn phần tử số phần tử G gọi cấp G Nếu G có vơ hạn phần tử ta nói G có cấp vơ hạn Sau số ví dụ nhóm: Z, Q, R, C nhóm giao hốn cấp vơ hạn với phép cộng thơng thường Với số nguyên m ➙ 1, tập Zm ✏ ta ⑤ a € Z, a ✏ b a ✁ b chia hết cho m✉ số nguyên modulo m với phép cộng a   b ✏ a   b nhóm giao Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn hoán cấp m Tập Z✝m ✏ ta € Zm ⑤ ♣a, mq ✏ 1✉ số nguyên modulo m nguyên tố với m với phép nhân ✏ ab nhóm giao hốn cấp ϕ♣mq, ϕ hàm Euler, tức ϕ♣1q ✏ m → ϕ♣mq số số tự nhiên nhỏ m ab nguyên tố với m 1.1.2 Định nghĩa Một nhóm G gọi xyclic tồn a €G cho phần tử G luỹ thừa a Trong trường hợp ta viết G ✏ ♣aq ta gọi G nhóm xyclic sinh a Phần tử a gọi phần tử sinh G 1.1.3 Bổ đề Nhóm nhóm xyclic xyclic ✏ ♣aq nhóm xyclic Cho H nhóm G Nếu H ✏ te✉ H nhóm xyclic sinh e Giả sử H ✘ te✉ Chọn e ✘ x € H Viết x ✏ ak Do x ✘ e nên k ✘ Vì H nhóm nên a✁k € H Trong hai số k ✁k phải có số nguyên dương Chứng minh Giả sử G Vì H chứa lũy thừa nguyên dương a Gọi r số nguyên € H Rõ ràng H ❹ ♣ar q Cho y € H Viết y ✏ at với t ✏ rq   s, ↕ s ➔ r Ta có y ✏ at ✏ ♣ar qq as Do as ✏ y ♣ar q✁q € H Từ cách chọn r ta suy s ✏ Do y ✏ at ✏ ♣ar qq € ♣ar q Vậy H ✏ ♣ar q nhóm xyclic dương bé cho ar 1.1.4 Định nghĩa Tập H nhóm G gọi nhóm G e € H , a✁1 € H ab € H với a, b € H Cho G nhóm Khi te✉ nhóm bé G G nhóm lớn G Cho a € G Đặt ♣aq ✏ tan ⑤ n € Z✉ Khi ♣aq nhóm G, gọi nhóm xyclic sinh a Cấp nhóm ♣aq gọi cấp phần tử a Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1.1.5 Bổ đề Cho G nhóm a phần tử G Các phát biểu sau tương đương (i) a có cấp n (ii) n số nguyên dương bé cho an (iii) an ✏ e ✏ e ak ✏ e k bội n với k € Z Chứng minh (i)ñ(ii) Trước hết ta khẳng định tồn số nguyên ✏ e Giả sử ngược lại, với cặp số tự nhiên k ➔ k✶ ta có ak ✁k ✘ e Suy ak ✘ ak Điều chứng tỏ ♣aq có cấp vơ hạn, dương k cho ak ✶ ✶ vơ lí với giả thiết (i) Do đó, tồn số nguyên dương k cho ak ✏ e Gọi r số nguyên dương bé có tính chất ar ✏ e Ta thấy phần tử e, a, a2 , , ar✁1 đôi khác Thật vậy, ✏ aj với ↕ i ↕ j ➔ r aj✁i ✏ e ↕ j ✁ i ➔ r, theo cách chọn r ta có i ✏ j Bây ta chứng minh G ✏ te, a, a2 , , ar✁1 ✉ Rõ ràng G ❹ te, a, a2 , , ar✁1 ✉ Cho b € G Khi b ✏ ak với k € Z Viết k ✏ rq   s q, s € Z ↕ s ↕ r ✁ Ta có b ✏ ak ✏ arq s ✏ ♣ar qq as ✏ as € te, a, a2, , ar✁1✉ Vì G ✏ te, a, a2 , , ar✁1 ✉ nhóm cấp r Suy r ✏ n (ii) chứng minh (ii)ñ(iii) Giả sử ak ✏ e Viết k ✏ nq   r với ↕ r ➔ n Vì an ✏ e nên e ✏ ak ✏ anq ar ✏ ar Theo cách chọn n ta phải có r ✏ 0, suy k chia hết cho n (iii)ñ(i) Gọi r số nguyên dương bé cho ar ✏ e Theo (iii), r bội n Do n số nguyên dương bé thỏa mãn an ✏ e Tương tự chứng minh (i)Ñ(ii) ta suy cấp a n ✏ ♣aq nhóm xyclic cấp n Khi phần tử b ✏ ak phần tử sinh G ♣k, nq ✏ 1.1.6 Hệ Cho G Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ✏ ak phần tử sinh G Khi b có cấp n Đặt d ✏ ♣k, nq Ta có bn④d ✏ ♣an qk④d ✏ e Theo Bổ đề 1.1.5, n④d bội n Vì d ✏ Ngược lại, giả sử ♣k, nq ✏ Ta có bn ✏ ♣an qk ✏ e Giả sử bt ✏ e Khi akt ✏ e Theo Bổ đề 1.1.5, kt bội n Do ♣k, nq ✏ nên t bội n Theo Bổ đề 1.1.5, b có cấp n Vậy G ✏ ♣bq Chứng minh Giả sử b 1.1.7 Định nghĩa Cho G nhóm H nhóm G Với a € G, kí hiệu Ha ✏ tha ⑤ h € H ✉ Ta gọi Ha lớp ghép trái hay lớp kề trái H G ứng với phần tử a Tập lớp ghép trái H G kí hiệu G④H Khi H có hữu hạn lớp ghép trái số lớp ghép trái H gọi số H G kí hiệu ♣G : H q Trong trường hợp này, số H số phần tử G④H Đặc biệt, cấp G ♣G : eq, số nhóm tầm thường te✉ Với H nhóm nhóm G a, b Ha ✏ Hb ab✁1 € H € G, ta dễ dàng kiểm tra 1.1.8 Định lý (Lagrange) Trong nhóm hữu hạn, cấp số nhóm ước cấp tồn nhóm Chứng minh Giả sử G nhóm có cấp n H nhóm G có € G ta có a ✏ ea € Ha Vì thế, phần tử G thuộc lớp ghép trái H Giả sử Ha ❳ Hb ✘ ❍ Khi tồn h, h✶ € H cho ✏ h✶ b Suy a ✏ h✁1 h✶ b Cho xa € Ha, x € H Khi xa ✏ ♣xh✁1 h✶ qb € Hb Suy Ha ❸ Hb Tương tự, Hb ❸ Ha Ha ✏ Hb Vậy hai lớp ghép trái H khác phải rời Với a € G, rõ ràng ánh xạ f : H ÝÑ Ha xác định f ♣hq ✏ song ánh Vì lớp cấp m Với a ghép trái H có m phần tử Gọi số H s Từ lập luận ta suy n ✏ sm Vì s m ước n Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 10 1.1.9 Hệ Cho G nhóm cấp n a ước n Hơn nữa, an ✏ e € G Khi cấp a Chứng minh Gọi cấp a r Khi nhóm xyclic ♣aq có cấp r Theo Định lí Lagrange, r ước n Theo Bổ đề 1.1.5 ta có ar Suy an ✏ e ✏ e 1.1.10 Hệ Mọi nhóm cấp nguyên tố nhóm xyclic Chứng minh Giả sử G nhóm cấp p nguyên tố Lấy a € G, a ✘ e Theo Định lí Lagrange, a có cấp ước p Vì p ngun tố nên cấp a là p Do a ✘ e nên cấp a lớn Vậy cấp a p, tức G nhóm xyclic sinh a 1.2 Kiến thức chuẩn bị vành 1.2.1 Định nghĩa Vành tập V trang bị hai phép toán cộng nhân thỏa mãn điều kiện sau đây: (i) V nhóm giao hốn với phép cộng; (ii) V vị nhóm với phép nhân: Phép nhân có tính chất kết hợp tồn phần tử với x € V ; €V (gọi phần tử đơn vị) cho 1x ✏ x1 ✏ x (iii)Phép nhân phân phối phép cộng Nếu phép nhân giao hốn V gọi vành giao hốn Sau số ví dụ thường gặp vành: 1.2.2 Ví dụ a) Rõ ràng Z, Q, R, C vành giao hoán với phép cộng nhân thông thường; b) Với số tự nhiên n → 0, tập Zn số nguyên modulo n làm thành vành giao hoán với phép cộng phép nhân cho bởi: a   b ✏ a   b a b ✏ ab với a, b € Zn Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 26 tức f ♣rq ✏ f ♣sq, r ✘ s Do f ♣xq khơng hốn vị T , vơ lí 2.2 Một số lớp đa thức hốn vị trường Mục dành để trình bày tiêu chuẩn hoán vị trường số lớp đa thức Trước hết, trình bày mở rộng Mệnh đề 2.1.8 2.2.1 Định lý Cho T trường có q phần tử Giả sử k, j số → j ➙ gcd♣k ✁ j, q ✁ 1q ✏ Khi đa thức f ♣xq ✏ axk   bxj   c với a ✘ hoán vị T b ✏ gcd♣k, q ✁ 1q ✏ Chứng minh Giả sử f ♣xq hoán vị T Trước hết ta chứng minh b ✏ Giả sử b ✘ ta cần tìm mâu thuẫn Đặt g ♣xq ✏ xk   a✁1 bxj Ta khẳng định g ♣xq hoán vị T Cho r, s € T cho g ♣rq ✏ g ♣sq Khi ag ♣rq  c ✏ ag ♣sq  c Suy f ♣rq ✏ f ♣sq Do f ♣xq hoán vị T nên r ✏ s Vì g ♣xq hốn vị Ta có g ♣xq ✏ xj ♣xk✁j  a✁1 bq Vì j ➙ nên g ♣0q ✏ Theo giả thiết, gcd♣k ✁ j, q ✁ 1q ✏ Do tồn số nguyên m, n cho ✏ m♣k ✁ j q  n♣q ✁ 1q Đặt d ✏ ✁a✁1 b Do b ✘ a ✘ nên d € T ✝ Ta có nguyên dương cho k d ✏ d1 ✏ ♣dmqk✁j ♣dq✁1qn Do T ✝ nhóm cấp q ✁ với phép nhân d € T ✝ nên dq✁1 d ✏ ♣dm qk✁j Suy ✏ Vì g ♣dm q ✏ ♣dm qj ♣♣dm qk✁j ✁ dq ✏ ♣dm qj ♣♣dm qk✁j ✁ ♣dm qk✁j q ✏ ✘ nên dm ✘ Như vậy, g♣0q ✏ g♣dmq, dm ✘ Điều chứng tỏ g ♣xq khơng hốn vị T , vơ lí Vậy b ✏ Do d Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 27 Tiếp theo, ta chứng minh gcd♣k, q ✁ 1q ✏ Do b ✏ nên f ♣xq ✏ axk   c Đặt h♣xq ✏ xk Cho h♣rq ✏ h♣sq với r, s € T Khi rk ✏ sk Suy ark   c ✏ ask   c, tức f ♣rq ✏ f ♣sq Do f ♣xq hoán vị T nên r ✏ s Vì h♣xq hốn vị T Theo Định lí 2.1.7, gcd♣k, q ✁ 1q ✏ Ngược lại, giả sử b ✏ gcd♣k, q ✁ 1q ✏ Ta cần chứng minh f ♣xq hoán vị T Vì b ✏ nên f ♣xq ✏ axk   c Do gcd♣k, q ✁ 1q ✏ nên theo Định lí 2.1.7, đa thức xk hốn vị T Giả sử f ♣rq ✏ f ♣sq Khi ark   c ✏ ask   c Suy rk ✏ sk Do xk hoán vị T nên r ✏ s Vậy f ♣xq hoán vị T Hệ sau cho ta lớp đa thức hoán vị 2.2.2 Hệ Cho T trường có q phần tử Giả sử q ✁ không bội 3, 5, Khi đa thức x8   bxt , với t số lẻ nhỏ 8, đa thức hoán vị T b ✏ T có đặc số Chứng minh Xét đa thức f ♣xq ✏ xk   axt với k ✏ Vì t lẻ t ➔ nên k ✁ t ✏ ✁ t € t7, 5, 3, 1✉ Theo giả thiết, q ✁ không bội 3, 5, Do gcd♣k ✁ t, q ✁ 1q ✏ Theo Định lí 2.2.1, đa thức f ♣xq hoán vị T a ✏ gcd♣k, q ✁ 1q ✏ gcd♣8, q ✁ 1q ✏ Chú ý gcd♣8, q ✁ 1q ✏ q số chẵn Gọi p đặc số T Khi p số nguyên tố q lũy thừa p Vì q số chẵn T có đặc số nguyên tố chẵn, tức đặc số T Vậy, f ♣xq hoán vị T a ✏ T có đặc số 2.2.3 Hệ Cho T trường có q phần tử Cho f ♣xq ✏ axk   bxj   c ✘ 0, k → j ➙ ✁ba✁1 lũy thừa bậc k ✁ j phần tử T Khi f ♣xq hoán vị T b ✏ gcd♣k, q ✁ 1q ✏ đa thức T , a Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 28 Chứng minh Giả sử f ♣xq hoán vị T Theo giả thiết, tồn € T cho ✁ba✁1 ✏ rk✁j Đặt g♣xq ✏ xk   ba✁1xj Ta khẳng định g ♣xq hoán vị T Thật vậy, giả sử g ♣sq ✏ g ♣s✶ q với s, s✶ € T Khi ag ♣sq   c ✏ ag ♣s✶ q   c Do f ♣sq ✏ f ♣s✶ q Vì f ♣xq hốn vị T nên s ✏ s✶ Do g ♣xq hốn vị T phần tử r Ta có g ♣xq ✏ xj ♣xk✁j ✁ ♣✁a✁1 bqq ✏ xj ♣xk✁j ✁ rk✁j q ➙ nên g♣0q ✏ Rõ ràng g♣rq ✏ Vì g♣xq hốn vị nên r ✏ Suy ✁a✁1 b ✏ Vì a ✘ nên b ✏ Do g ♣xq ✏ xk Vì g ♣xq hốn vị nên theo Định lí 2.1.7 ta có gcd♣k, q ✁ 1q ✏ Ngược lại, giả sử b ✏ gcd♣k, q ✁ 1q ✏ Khi f ♣xq ✏ axk   c Do gcd♣k, q ✁ 1q ✏ nên theo Định lí 2.1.7 ta suy xk hoán vị T Giả sử f ♣rq ✏ f ♣sq với r, s € T Khi ark   c ✏ ask   c Suy rk ✏ sk Do g ♣xq hoán vị T nên r ✏ s Vì f ♣xq hoán Do j vị T Trong phần cuối mục này, trình bày số ví dụ đa thức hốn vị 2.2.4 Ví dụ Các phát biểu sau đúng: (i) Đa thức x8 ✁ 2x3 hoán vị trường Z11 (ii) Đa thức x8   4x hoán vị trường Z29 Chứng minh Trong Hệ 2.2.2, với giả thiết T trường có q phần tử với q ✁ không bội 3, 5, đa thức f ♣xq ✏ x8   bxt , t lẻ nhỏ 8, hoán vị T b ✏ T có đặc số Ví dụ 2.2.4 giả thiết q ✁ không bội 3, 5, bỏ Mặc dù đa thức x8 ✁ 2x3 mệnh đề (i) có hệ số b ✏ ✁2 ✘ đặc số trường T ✏ Z11 11 ✘ 2, đa Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 29 thức hốn vị T q ✁ ✏ 10 bội Thật vậy, xét đa thức f ♣xq ✏ x8 ✁ 2x3 ta có f ♣0q ✏ 0, f ♣1q ✏ 10, f ♣2q ✏ 9, f ♣3q ✏ 6, f ♣4q ✏ 2, f ♣5q ✏ 7, f ♣6q ✏ 1, f ♣7q ✏ 5, f ♣8q ✏ 4, f ♣9q ✏ f ♣10q ✏ Vì ánh xạ ϕ : Z11 Ñ Z11 cho ϕ♣aq ✏ f ♣aq song ánh Do f ♣xq đa thức hoán vị modulo 11 Tương tự vậy, đa thức x8   4x mệnh đề (ii) có hệ số b ✏ ✘ đặc số trường T ✏ Z29 29 ✘ 2, hốn vị Z29 Sở dĩ q ✁ ✏ 28 bội Thật vậy, xét đa thức f ♣xq ✏ x8   4x ta có f ♣0q ✏ 0, f ♣1q ✏ 5, f ♣2q ✏ 3, f ♣3q ✏ 19, f ♣4q ✏ 12, f ♣5q ✏ 15, f ♣6q ✏ 18, f ♣7q ✏ 6, f ♣8q ✏ 23, f ♣9q ✏ 27, f ♣10q ✏ 7, f ♣11q ✏ 2, f ♣12q ✏ 20, f ♣13q ✏ 10, f ♣14q ✏ 21, f ♣15q ✏ 25, f ♣16q ✏ 22, f ♣17q ✏ 11, f ♣18q ✏ 1, f ♣19q ✏ 14, f ♣20q ✏ 13, f ♣21q ✏ 17, f ♣22q ✏ 8, f ♣23q ✏ 28, f ♣24q ✏ 4, f ♣25q ✏ 9, f ♣26q ✏ 24, f ♣27q ✏ 16 f ♣28q ✏ 26 Vì ánh xạ ϕ : Z29 Ñ Z29 cho ϕ♣aq ✏ f ♣aq song ánh Do f ♣xq đa thức hốn vị modulo 29 2.2.5 Ví dụ Xét đa thức f ♣xq ✏ x8 ✁ 3x Khi (i) f ♣xq khơng hốn vị trường Z5 ; (ii) f ♣xq khơng hốn vị trường Z11 ; (iii) f ♣xq khơng hốn vị trường Z13 Chứng minh Ở ví dụ (i) đa thức f ♣xq ✏ x8 ✁ 3x có q ✁ ✏ không bội 3, 5, b ✏ ✁3 ✘ đặc số trường T ✏ Z5 ✘ Đồng thời đa thức f ♣xq có f ♣0q ✏ 0, f ♣1q ✏ 3, f ♣2q ✏ 0, f ♣3q ✏ f ♣4q ✏ Vì ánh xạ ϕ : Z5 Ñ Z5 cho ϕ♣aq ✏ f ♣aq khơng song ánh Do f ♣xq đa thức khơng hốn vị modulo Ở ví dụ (ii) đa thức f ♣xq ✏ x8 ✁ 3x có q ✁ ✏ 10 bội có b ✏ ✁3 ✘ đặc số trường T ✏ Z11 11 ✘ Đồng thời đa thức f ♣xq có f ♣0q ✏ 0, f ♣1q ✏ 9, f ♣2q ✏ 8, f ♣3q ✏ 7,f ♣4q ✏ 8, f ♣5v q ✏ 0, f ♣6q ✏ 8, f ♣7q ✏ 10, f ♣8q ✏ 3, f ♣9q ✏ f ♣10q ✏ Vì ánh xạ ϕ : Z11 Ñ Z11 cho Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 30 ϕ♣aq ✏ f ♣aq không song ánh ♣f ♣2q ✏ f ♣4q ✏ f ♣6q ✏ 8q Do f ♣xq đa thức khơng hốn vị modulo 11 Tương tự vậy, ví dụ (iii) đa thức f ♣xq ✏ x8 ✁ 3x có q ✁ ✏ 12 bội có b ✏ ✁3 ✘ ✏ Z13 13 ✘ Đồng thời đa thức f ♣xq có f ♣0q ✏ f ♣3q ✏ 0, f ♣1q ✏ f ♣6q ✏ 11, f ♣2q ✏ f ♣8q ✏ 3, f ♣4q ✏ f ♣12q ✏ f ♣9q ✏ f ♣11q ✏ Vì ánh xạ ϕ : Z13 Đ Z13 cho ϕ♣aq ✏ f ♣aq không song ánh Do f ♣xq đa thức khơng hốn vị modulo đặc số trường T 13 2.3 Đa thức hốn vị modulo 2k Mục đích mục trình bày tiêu chuẩn hốn vị đa thức với hệ số nguyên theo modulo 2k báo Ronald Rivest [R] Từ đến hết luận văn, ta giả thiết f ♣xq đa thức với hệ số nguyên Nhắc lại f ♣xq gọi hoán vị modulo n ánh xạ ϕ : Zn Ñ Zn cho ϕ♣aq ✏ f ♣aq song ánh 2.3.1 Chú ý Giả sử X tập hữu hạn Khi ánh xạ ϕ : ÝÑ X song ánh đơn ánh, tồn ánh Do đó, đa thức f ♣xq hoán vị modulo n ánh xạ ϕ : Zn Ñ Zn cho ϕ♣aq ✏ f ♣aq đơn ánh, f ♣aq ✑ f ♣bq ♣mod nq kéo theo a ✑ b ♣mod nq với a, b € Z X 2.3.2 Ví dụ Cho f ♣xq ✏   7x   8x2   3x3   4x4 g ♣xq ✏   2x   2x2 Ta xét tính hốn vị f ♣xq g ♣xq theo modulo 23 Trong Z8 rxs, đa thức f ♣xq có dạng f ♣xq ✏   7x   3x3   4x4 Ta có f ♣0q ✏ 3, f ♣1q ✏ 1, f ♣2q ✏ 4, f ♣3q ✏ 7, f ♣4q ✏ 6, f ♣5q ✏ 2, f ♣6q ✏ f ♣7q ✏ Vì ánh xạ ϕf : Z8 Ñ Z8 cho ϕf ♣aq ✏ f ♣aq song ánh Ta có g ♣0q ✏ 2, g ♣1q ✏ 6, g ♣2q ✏ 6, g ♣3q ✏ 2, g ♣4q ✏ 2, g ♣5q ✏ 6, g ♣6q ✏ g ♣7q ✏ Vì ánh xạ ϕg : Z8 Ñ Z8 cho ϕg ♣aq ✏ g ♣aq không Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 31 song ánh Vậy, f ♣xq hốn vị modulo 23 g ♣xq khơng hốn vị modulo 23 Trước hết trình bày tiêu chuẩn để đa thức f ♣xq hoán vị modulo 2.3.3 Bổ đề Đa thức f ♣xq ✏ a0   a1x     adxd với hệ số nguyên hoán vị modulo a1     ad lẻ Chứng minh Ta ln có f ♣0q ✏ a0 € Z2 Ta xét hai trường hợp a) Giả sử a0 chẵn Khi f ♣0q ✏ € Z2 Vì thế, f ♣xq hoán vị modulo f ♣1q ✏ € Z2 Ta có f ♣1q ✏ a0   a1     ad Vì a0 chẵn nên f ♣1q ✏ € Z2 a1     ad lẻ Do f ♣xq hoán vị modulo a1     ad lẻ b) Giả sử a0 lẻ Khi f ♣0q ✏ € Z2 Vì thế, f ♣xq hốn vị modulo f ♣1q ✏ € Z2 Ta có f ♣1q ✏ a0   a1     ad Vì a0 lẻ nên f ♣1q ✏ € Z2 a1     ad lẻ Do f ♣xq hốn vị modulo a1     ad lẻ 2.3.4 Bổ đề Cho f ♣xq ✏ a0   a1 x     ad xd đa thức với hệ số nguyên Cho n ✏ 2m với m số nguyên chẵn Giả sử f ♣xq hoán vị modulo n Khi a1 số lẻ Chứng minh Ta có ✘ m € Zn Vì f ♣xq hốn vị modulo n nên f ♣0q ✘ f ♣mq € Zn Ta có   ✟ f ♣mq ✏ a0   a1 m   a2 m2     ad md Do m số chẵn nên m2 chia hết cho n Do f ♣mq ✑ a0   a1 m ♣mod nq ✑ ♣mod nq Do f ♣mq ✑ a0 ♣mod nq Rõ ràng f ♣0q ✑ ♣mod nq Vì f ♣mq ✏ f ♣0q € Zn , Giả sử a1 chẵn Vì m chẵn nên a1 m Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 32 ✘ m € Zn Vì f ♣xq khơng hốn vị modulo n, vơ lí Vậy, a1 số lẻ 2.3.5 Ví dụ Cho f ♣xq ✏ 2x   4x2   6x3 Ta xét tính hốn vị f ♣xq theo modulo n ✏ Rõ ràng n ✏ 2.m, với m ✏ số chẵn Ta có a1 ✏ số chẵn Vì thế, theo Bổ đề 2.3.4, đa thức f ♣xq khơng hốn vị modulo Điều thấy dễ dàng từ định nghĩa đa thức hốn vị Trong Z8 ta có f ♣0q ✏ 0, f ♣1q ✏ 4, f ♣2q ✏ 4, f ♣3q ✏ 4, f ♣4q ✏ 0, f ♣5q ✏ 4, f ♣6q ✏ f ♣7q ✏ Vì ánh xạ ϕg : Z8 cho ϕf ♣aq ✏ f ♣aq không song ánh Ñ Z8 2.3.6 Bổ đề Cho f ♣xq ✏ a0   a1x     adxd đa thức với hệ số nguyên Cho n ✏ 2k với k → cho m ✏ 2k✁1 ✏ n④2 Nếu f ♣xq hốn vị modun n hoán vị modulo m Chứng minh Giả sử f ♣xq hoán vị modulo n Với a € Z ta có f ♣a   mq ✏ a0   a1 ♣x   mq     ad ♣x   mqd ✏ a0   a1a     adad   mt, với t số nguyên ✑ a0   a1a     adad ♣mod mq ✑ f ♣aq ♣mod mq ✘ s € Zm cho f ♣rq ✏ f ♣sq € Zm Suy r ✙ s ♣mod mq f ♣rq ✑ f ♣sq ♣mod mq Vì vậy, theo tính chất vừa chứng minh ta có Giả sử f ♣xq khơng hốn vị modulo m Khi có hai giá trị r f ♣rq ✑ f ♣r   mq ✑ f ♣sq ✑ f ♣s   mq ♣mod mq Do đó, tồn số nguyên t1 , t2 cho f ♣rq ✁ f ♣r   mq f ♣rq ✁ f ♣sq ✏ mt1 ✏ mt2 Vì ♣r   mq ✁ r khơng bội n ✏ 2m nên ta có r   m ✘ r € Zn Do f ♣xq hoán vị modulo n nên f ♣r   mq ✙ f ♣rq ♣mod nq Do t1 lẻ Theo giả thiết, r ✙ s ♣mod mq Vì Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 33 ✙ s ♣mod nq Vì f ♣xq hoán vị modulo n nên f ♣rq ✙ f ♣sq ♣mod nq Vì t2 lẻ Suy t2 ✁ t1 chẵn Do r   ✟ f ♣r   mq ✁ f ♣sq ✏ f ♣rq ✁ f ♣sq   ✟ ✁ f ♣rq ✁ f ♣r   mq ✏ m♣t2 ✁ t1q ✑ ♣mod nq Do f ♣xq hoán vị modulo n nên r   m ✁ s ✑ ♣mod nq Do m ước n nên r   m ✁ s ✑ ♣mod mq Vì r ✁ s ✑ ♣mod mq Điều vơ lí với cách chọn r s Nhìn chung, tốn kiểm tra (theo định nghĩa) tính khơng hốn vị f ♣xq modulo 2k k lớn khó Vì thế, nhiều trường hợp ta sử dụng Bổ đề 2.3.6 để giải toán Dưới ví dụ minh họa 2.3.7 Ví dụ Cho đa thức f ♣xq ✏   2x   x2 Khi f ♣xq khơng hốn vị modulo 128 Chứng minh Trong vành Z8 ta có f ♣0q ✏ 1, f ♣1q ✏ 4, f ♣2q ✏ 1, f ♣3q ✏ 0, f ♣4q ✏ 1, f ♣5q ✏ 4, f ♣6q ✏ ✘ € Z8, f ♣0q ✏ f ♣2q ✏ € Z8 Vì ánh xạ ϕf : Z8 Ñ Z8 cho ϕf ♣aq ✏ f ♣aq không song ánh Vì f ♣xq khơng hốn vị modulo Theo Bổ đề 2.3.6, f ♣xq không hoán vị modulo 16 Tiếp tục áp dụng Bổ đề 2.3.6, ta suy f ♣xq khơng hốn vị modulo 2k với k ➙ Đặc biệt, 128 lũy thừa nên f ♣xq khơng hốn vị modulo 128 Đặc biệt, ta có 2.3.8 Bổ đề Cho f ♣xq ✏   a1x     adxd đa thức với hệ số nguyên Cho n ✏ 2m Giả sử f ♣xq hốn vị modulo n Khi f ♣a   mq ✑ f ♣aq   m ♣mod mq với số nguyên a a0 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 34 Chứng minh Cho a € Z Theo chứng minh Bổ đề 2.3.6, tồn số nguyên t cho f ♣a   mq ✁ f ♣aq ✏ mt Vì n ✏ 2m nên ♣a   mq ✁ a không bội n, tức a   m ✘ a € Zn Do f ♣xq hoán vị modulo n nên f ♣a   mq ✘ f ♣aq € Zn Do f ♣aq ✙ f ♣a   mq ♣mod nq Vì mt khơng bội n Suy t số lẻ Vì f ♣a   mq ✏ f ♣aq   mt ✑ f ♣aq   m ♣mod 2mq ✑ f ♣aq   m ♣mod nq 2.3.9 Bổ đề Cho f ♣xq ✏ a0   a1x     adxd đa thức với hệ số nguyên Cho n ✏ 2m với m số chẵn Giả sử f ♣xq hoán vị modulo m Khi f ♣xq hốn vị modulo n a1 số lẻ a3   a5   a7   số chẵn Chứng minh Do m số chẵn nên m2 chia hết cho n ✏ 2m Do với i ✏ 2, , d với số nguyên a ta có ♣a   mqi ✏   imai✁1   tm2 với số nguyên t ✑   imai✁1 ♣mod nq Vì i ➙ nên i ✁ ➙ Do có số i, a, chẵn imai✁1 bội n Trong trường ta có ♣a   mqi ✑ aiai ♣mod nq Còn số i, a, số lẻ ♣imai✁1 q ✑ m ♣mod nq ta có ♣a   mqi ✑ aiai   m ♣mod nq Bây ta xét hai trường hợp Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 35 Trường hợp 1: a số chẵn Theo ta có f ♣a   mq ✑ a0   a1 ♣a   mq   ♣a2 a2     ad ad q ✑ f ♣aq   a1m ♣mod nq Trường hợp 2: a số lẻ Theo ta có   f ♣a   mq ✑ a0   a1 ♣a   mq   a2 a2   a4 a4   ✟   ♣a3a3   mq   ♣a5a5   mq   ✑ f ♣aq   ♣a1   a3   a5   qm ♣mod nq Bây ta chứng minh bổ đề Giả sử f ♣xq hoán vị modulo n Theo Bổ đề 2.3.4, hệ số a1 lẻ Chú ý a   m ✘ a ♣mod nq với số nguyên a Vì f ♣a   mq ✙ f ♣aq ♣mod nq với số nguyên a Chọn a số lẻ (chẳng hạn a ✏ 1) Theo Trường hợp ta có f ♣a   mq ✁ f ♣aq ✑ ♣a1   a3   a5   qm ♣mod nq Do ta có ♣a1   a3   a5   qm ✙ ♣mod nq Suy a1   a3   a5   phải số lẻ Vì a1 lẻ nên a3   a5   a7   số chẵn Ngược lại, giả sử a1 số lẻ a3   a5   a7   số chẵn Giả sử phản chứng f ♣xq không hốn vị modulo n Khi tồn a ✘ b € Zn cho f ♣aq ✏ f ♣bq € Zn Do có hai số nguyên a ✙ b ♣mod nq cho f ♣aq ✑ f ♣bq ♣mod nq Vì m ước n nên f ♣aq ✑ f ♣bq ♣mod mq Theo giả thiết, f ♣xq hốn vị modulo m, a ✑ b ♣mod mq Do a ✙ b ♣mod nq n ✏ 2m nên a ✁ b ✏ mt với t số lẻ Vì có số nguyên t✶ cho b ✏ a ✁ mt ✏ a   m ✁ 2t✶ m ✑ a   m ♣mod nq Suy b ✏ a   m € Zn Vì f ♣aq ✑ f ♣bq ♣mod mq nên ta có f ♣aq ✑ f ♣a   mq ♣mod nq Nếu a số chẵn theo Trường hợp ta có f ♣a   mq ✑ f ♣aq   a1 m ♣mod nq Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 36 Do a1 m bội n Suy a1 chẵn, điều mâu thuẫn với giả thiết a1 lẻ Do a số lẻ Theo Trường hợp ta có f ♣a   mq ✑ f ♣aq   ♣a1   a3   a5   qm ♣mod nq Do ♣a1   a3   a5   qm bội n Suy a1   a3   a5   chẵn Theo giả thiết a1 số lẻ Vì a3   a5   số lẻ, điều mâu thuẫn với giả thiết a3   a5   chẵn Vậy f ♣xq hốn vị modulo n Định lí sau kết mục này, kết luận văn 2.3.10 Định lý Cho f ♣xq ✏ a0   a1 x     ad xd đa thức với hệ ✏ 2k với k ➙ Khi f ♣xq hoán vị modulo n a1 số lẻ, a2   a4   a6   số chẵn a3   a5   a7   số nguyên Cho n số chẵn Chứng minh Giả sử f ♣xq hoán vị modulo n Đặt m1 n ✏ 2m1 Do k ✏ 2k✁1 Khi ➙ nên m1 số chẵn Do theo Bổ đề 2.3.4, hệ số a1 số lẻ Do f ♣xq hoán vị modulo n ✏ 2m1 nên theo Bổ đề 2.3.6, đa thức f ♣xq hoán vị modulo m1 Vì thế, áp dụng Bổ đề 2.3.9, ta có a3   a5   a7   số chẵn Tiếp theo, ta khẳng định quy nạp theo i ✏ 1, , k ✁ f ♣xq hoán vị modulo 2k✁i Với i ✏ 1, ta chứng minh phần f ♣xq hoán vị modulo m1 ✏ 2k✁1 , khẳng định với i ✏ Giả sử kết cho i ✁ với i ↕ k ✁ 1, tức f ♣xq hoán vị modulo 2k✁i 1 Đặt mi ✏ 2k✁i mi✁1 ✏ 2k✁i 1 Khi mi✁1 ✏ 2mi Do f ♣xq hoán vị modulo mi✁1 nên theo Bổ đề 2.3.6, f ♣xq hoán vị modulo mi ✏ 2k✁i Khẳng định chứng minh Với i ✏ k ✁ 1, từ khẳng định ta suy f ♣xq hoán vị modulo Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 37 Do theo Bổ đề 2.3.3 ta có a1   a2   a3     ad số lẻ Vì a1 lẻ nên ♣ a2   a4   a6   q   ♣ a3   a5   a7   q số chẵn Do a3   a5   a7   số chẵn nên a2   a4   a6   số chẵn   a4   a6   số chẵn a3   a5   a7   số chẵn Ta cần chứng minh f ♣xq hoán vị modulo n ✏ 2k Ta chứng minh điều quy nạp theo k Cho k ✏ Vì a1 số lẻ, a2   a4   a6   số chẵn a3   a5   a7   số chẵn nên a1   a2   a3     ad số lẻ Do đó, theo Bổ đề 2.3.3 ta suy f ♣xq hoán vị modulo ✏ 21 Vậy, kết cho trường hợp k ✏ Cho k → giả thiết kết cho trường hợp k ✁ 1, tức f ♣xq hoán vị modulo 2k✁1 trường hợp a1 số lẻ, a2   a4   a6   số chẵn a3   a5   a7   số chẵn Đặt m ✏ 2k✁1 Khi n ✏ 2m Do k → nên m số chẵn Vì a1 số lẻ, a3   a5   a7   số chẵn f ♣xq hoán vị modulo m nên theo Bổ đề 2.3.9 ta suy f ♣xq hoán vị modulo n Ngược lại, giả sử a1 số lẻ, a2 Phần cuối mục trình bày số ví dụ đa thức hốn vị modulo 2k 2.3.11 Ví dụ Các đa thức sau hoán vị modulo 2k (i) ax   bx2 với số lẻ a số chẵn b (ii) x   x2   x4 (iii)   x   x2     xd , d ✑ ♣mod 4q Chứng minh (i) Ta có a1 ✏ a lẻ, a2 ax   bx2 hoán vị modulo 2k ✏ Số hóa Trung tâm Học liệu – Đại học Thái Nguyên b chẵn Theo Định lí 2.3.10, http://www.lrc-tnu.edu.vn 38 (ii) Ta có a1 ✏ lẻ, a2   a4 ✏ chẵn Theo Định lí 2.3.10, x   x2   x4 hoán vị modulo 2k ✏ lẻ, a2   a4     ad✁1 ✏ ♣d ✁ 1q④2 a3   a5     ad ✏ ♣d ✁ 1q④2 Do d ✑ ♣mod 4q nên d ✁ bội Vì ♣d ✁ 1q④2 số chẵn Theo Theo Định lí 2.3.10,   x   x2     xd hoán vị modulo 2k (iii) Từ giả thiết ta suy d số lẻ Ta có a1 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 39 Kết luận Luận văn trình bày số kết đa thức hoán vị hai báo: R Rivest, Permutation polynomials modulo 2w , Finite fields and their applications, (2001), 287-292 R A Mollin and C Small, On permutation polynomials over finite fields, Inter J Math and Math Sciences, 10 (1987), 535-544 Nội dung luận văn là: ✌ Trình bày số kiến thức chuẩn bị nhóm, vành, trường, đa thức phục vụ chứng minh kết Chương ✌ Đưa tiêu chuẩn để đa thức dạng xn hoán vị trường hữu hạn (Định lí 2.1.7) Từ suy tiêu chuẩn hốn vị đa thức bậc không hai ✌ Chứng minh điều kiện cần đủ cho đa thức dạng xk   bxj   c, k → j ➙ hoán vị trường hữu hạn (Định lí 2.2.1) Từ thu tính chất hốn vị số đa thức đặc biệt ✌ Giải trọn vẹn toán tính hốn vị modulo n cho đa thức với hệ số nguyên trường hợp n lũy thừa (Định lí 2.3.10) Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 40 Tài liệu tham khảo [C] Nguyễn Tự Cường, Đại số đại, tập 1, NXB ĐHQGHN, 2001 [HT] Bùi Huy Hiền Phan Doãn Thoại, Bài tập Đại số số học, Tập 2, NXB Giáo dục, 1986 [La] Ngô Thúc Lanh, Đại số số học, Tập 2, NXB Giáo dục, 1986 [LN] R Lidl and H Niedereiter, Finite Fields, Addison - Wesley, 1983 [LM1] R Lidl and G L Mullen, When does a polynomial over a finite field permute the elements of the field? The American Math, Monthly, (1988), 243-246 [LM2] R Lidl and G L Mullen, When does a polynomial over a finite field permute the elements of the field? II The American Math, Monthly, (1993), 71-74 [MS] R A Mollin and C Small, On permutation polynomials over finite fields, Inter J Math and Math Sciences, 10 (1986), 535544 [Riv] R Rivest, Permutation polynomials modulo 2w , Finite fields and their applications, (1999), 287-292 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ... chuẩn đa thức hoán vị được, dạng đặc biệt đa thức hoán vị được, nhóm đa thức hốn vị được, trường hợp ngoại lệ đa thức hoán vị đa thức hoán vị số dạng bất định Lidl Mullen [LM1,2] nghiên đa thức hoán. .. chuẩn bị đa thức 17 Đa thức hoán vị 20 2.1 Khái niệm đa thức hoán vị 20 2.2 Một số lớp đa thức hoán vị trường 26 2.3 Đa thức hoán vị modulo 2k 30 Kết... http://www.lrc-tnu.edu.vn €K 20 Chương Đa thức hoán vị 2.1 Khái niệm đa thức hoán vị 2.1.1 Định nghĩa (i) Cho R vành giao hốn có hữu hạn phần tử Cho f ♣xq € Rrxs Ta nói f ♣xq đa thức hoán vị R ánh xạ ϕ : R Ñ R