Luận văn Thạc sĩ Toán học: Nửa nhóm số và đa thức chia đường tròn

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:41

Thêm vào BST

Báo xấu

32
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục đích của đề tài là tìm hiểu về chứng minh của kết quả này nói riêng và tìm hiểu về mối liên hệ giữa nửa nhóm số dạng S(p, q) và đa thức chia đường tròn nói chung. Theo đó, luận văn có trình bày hai chứng minh cho kết quả cổ điển nói trên, trong phiên bản bao gồm cả trường hợp cặp (p,q) không nhất thiết nguyên tố (xem Định lý 2.2.1), đồng thời có đưa ra một vài hệ quả.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Nửa nhóm số và đa thức chia đường tròn

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– LÊ THỊ NGỌC BÍCH NỬA NHÓM SỐ VÀ ĐA THỨC CHIA ĐƯỜNG TRÒN LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2017
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– LÊ THỊ NGỌC BÍCH NỬA NHÓM SỐ VÀ ĐA THỨC CHIA ĐƯỜNG TRÒN Chuyên ngành: Phương pháp toán sơ cấp Mã số: 60 46 01 13 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC TS. NGUYỄN DUY TÂN Thái Nguyên - 2017
1 Mục lục Lời nói đầu 2 1 Nửa nhóm số 6 1.1 Một số định nghĩa và tính chất . . . . . . . . . . . . . . . . 6 1.2 Tập Apéry . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2 Mối liên hệ giữa nửa nhóm số và đa thức bù trừ 16 2.1 Đa thức chia đường tròn và đa thức bù trừ . . . . . . . . . . 16 2.2 Định lý chính . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.3 Đa thức bù trừ nhị phân . . . . . . . . . . . . . . . . . . . . 24 3 Một vài ứng dụng 27 3.1 Nửa nhóm số đối xứng . . . . . . . . . . . . . . . . . . . . . 27 3.2 Mọi nửa nhóm số với chiều nhúng 2 là đối xứng . . . . . . . 29 3.3 Phân bố gián đoạn và độ gián đoạn . . . . . . . . . . . . . . 30 3.3.1 Độ gián đoạn cực đại trong đa thức chia đường tròn nhị phân . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.3.2 Tổng Sylvester và số Bernoulli . . . . . . . . . . . . . 35 Kết luận 38 Tài liệu tham khảo 39
2 Lời nói đầu Ta xét tập S = S(3, 7) gồm các tổ hợp tuyến tính nguyên không âm của 3 và 7, tức là S = {3u + 7v | u, v ∈ Z≥0 } = {0, 3, 6, 7, 9, 10, 12, 13, 14, 15, 16, . . .}. Khi đó S là một ví dụ của nửa nhóm số: S tập con của Z≥0 mà đóng với phép cộng và Z≥0 \ S là tập hữu hạn. Đối với nửa nhóm số S = S(3, 7), ta liên kết với nó một chuỗi lũy thừa hình thức sau đây, gọi là chuỗi Hilbert của S: X HS (x) = xs = 1 + x3 + x6 + x7 + x9 + x10 + x12 + x13 + x14 + · · · ∈ Z[[x]]. x∈S Ta nhân chuỗi HS (x) với (1 − x) ta sẽ nhận được một đa thức, gọi là đa thức nửa nhóm của S: PS (x) =(1 − x)HS (x) =(1 − x)(1 + x3 + x6 + x7 + x9 + x10 )+ (1 − x)(x12 + x13 + x14 + · · · ) =(1 + x3 + x6 + x7 + x9 + x10 ) − (x + x4 + x7 + x8 + x10 + x11 ) + x12 =1 − x + x3 − x4 + x6 − x8 + x9 − x11 + x12 . Bằng tính toán trực tiếp ta kiểm tra được đẳng thức đáng ngạc nhiên sau
3 PS (x) = 1 − x + x3 − x4 + x6 − x8 + x9 − x11 + x12 x14 + x7 + 1 = 2 x +x+1 (x21 − 1)(x − 1) = 3 . (x − 1)(x7 − 1) (x21 − 1)(x − 1) Nhận xét rằng 3 bằng đa thức chia đường tròn Φ21 (x). Do (x − 1)(x7 − 1) vậy ta có PS(3,7) (x) = Φ21 (x). Như vậy ta thấy đa thức nửa nhóm của S(3, 7) bằng với đa thức chia đường tròn Φ21 (x). Một kết quả cổ điển nói rằng ta vẫn có đẳng thức tương tự khi ta thay cặp (3, 7) bởi cặp số nguyên tố phân biệt (p, q) và ta xét nửa nhóm số tương ứng S(p, q), tức là ta vẫn có PS(p,q) (x) = Φpq (x). Mục đích của đề tài là tìm hiểu về chứng minh của kết quả này nói riêng và tìm hiểu về mối liên hệ giữa nửa nhóm số dạng S(p, q) và đa thức chia đường tròn nói chung. Theo đó, luận văn có trình bày hai chứng minh cho kết quả cổ điển nói trên, trong phiên bản bao gồm cả trường hợp cặp (p, q) không nhất thiết nguyên tố (xem Định lý 2.2.1), đồng thời có đưa ra một vài hệ quả. Đặc biệt luận văn còn trình một số ứng dụng trong việc xét số các gián đoạn một nửa nhóm số. Ngoài phần lời nói đầu, kết luận và tài liệu tham khảo luận văn gồm 3 chương: Chương 1. Nửa nhóm số: Trong chương này chúng tôi trình bày định nghĩa nửa nhóm số và một số bất biến liên quan của nửa nhóm số như: số Frobenius, chiều nhúng, bội, chuỗi Hilbert của nửa nhóm số, đa thức nửa nhóm số. Chúng tôi chủ yếu sử dụng tài liệu [4] và [5] cho nội dung của chương này.
4 Chương 2. Mối liên hệ giữa nửa nhóm số và đa thức bù trừ: Trình bày một tổng quát hóa của đa thức chia đường tròn: Đa thức bù trừ, được giới thiệu bởi Bachman. Đồng thời trình bày một kết quả (folklore) về đa thức nửa nhóm số chiều nhúng 2 với đa thức bù trừ nhị phân. Chương 3. Một vài ứng dụng: Trong chương này chúng tôi đưa ra định nghĩa nửa nhóm số đối xứng và trình bày kết quả chứng minh mọi nửa nhóm số với chiều nhúng 2 là đối xứng. Bên cạnh đó chúng tôi cũng trình bày một số ứng dụng trong việc xét số các gián đoạn một nửa nhóm số và trình bày kết quả của Hong-Lee-Lee-Park về độ gián đoạn cực đại trong đa thức chia đường tròn nhị phân. Luận văn được viết dựa theo bài báo Numerical semigroups, cyclotomic polynomials, and Bernoulli numbers của tác giả P. Moree (2004) và một phần trong cuốn sách Numerical semigroups của tác giả J. C. Rosales and P. A. García-Sánchez (2009). Luận văn này được thực hiện tại Trường Đại học Khoa học - Đại học Thái Nguyên và hoàn thành dưới sự hướng dẫn của TS. Nguyễn Duy Tân. Tác giả xin được bày tỏ lòng biết ơn chân thành và sâu sắc tới người hướng dẫn khoa học của mình, người đã đặt vấn đề nghiên cứu, dành nhiều thời gian hướng dẫn và tận tình giải đáp những thắc mắc của tác giả trong suốt quá trình làm luận văn. Tác giả cũng đã học tập được rất nhiều kiến thức chuyên ngành bổ ích cho công tác và nghiên cứu của bản thân. Tác giả xin bày tỏ lòng cảm ơn sâu sắc tới các thầy giáo, cô giáo đã tham gia giảng dạy lớp Cao học Toán K9B2 (khóa 2015 - 2017); nhà trường và các phòng chức năng của trường; khoa Toán - Tin, trường Đại học Khoa học - Đại học Thái Nguyên đã quan tâm và giúp đỡ tác giả trong suốt thời gian học tập tại trường. Tác giả cũng xin gửi lời cảm ơn tới tập thể lớp Cao học Toán K9B2 (khóa 2015 - 2017) đã luôn động viên và giúp đỡ tác giả rất nhiều trong
5 quá trình học tập, nghiên cứu. Cuối cùng, tác giả xin gửi lời cảm ơn chân thành tới gia đình, bạn bè, lãnh đạo đơn vị công tác và đồng nghiệp đã động viên, giúp đỡ và tạo điều kiện tốt nhất cho tác giả khi học tập và nghiên cứu. Thái Nguyên, 2017 Lê Thị Ngọc Bích Học viên lớp Cao học Toán K9B2 Khoa Toán Tin - Trường Đại học Khoa học - Đại học Thái Nguyên
6 Chương 1 Nửa nhóm số 1.1 Một số định nghĩa và tính chất Định nghĩa 1.1.1. Xét a1 , . . . , am là các số nguyên dương. Ta đặt S = S(a1 , . . . , am ) là tập tất cả những tổ hợp tuyến tính nguyên không âm của a1 , . . . , am , nghĩa là, S = {x1 a1 + · · · + xm am | xi ∈ Z≥0 , ∀i = 1, . . . , m} . Khi đó, S là nửa nhóm (nghĩa là nó đóng với phép cộng). Nửa nhóm S được gọi là nửa nhóm số nếu như phần bù của nó Z≥0 \S là hữu hạn. Tập {a1 , . . . , am } được gọi là một hệ sinh của nửa nhóm số S. Mệnh đề 1.1.2. Ta có S(a1 , . . . , am ) là nửa nhóm số khi và chỉ khi a1 , . . . , am là nguyên tố cùng nhau. Chứng minh. "⇒": Giả sử S := S(a1 , . . . , am ) là một nửa nhóm số, tức là Z≥0 \ S hữu hạn. Gọi d là ước chung lớn nhất của a1 , . . . , am . Khi đó mọi phần tử s của S đều chia hết cho d. Vì Z≥0 \ S hữu hạn, nên tồn tại x sao cho x và x + 1 đều thuộc S. Điều này suy ra d là ước của cả x và x + 1. Do vậy d = 1. "⇐": Ta giả sử rằng ước chung lớn nhất của a1 , . . . , am là bằng 1. Khi đó tồn tại z1 , . . . , zm ∈ Z sao cho z1 a1 + · · · + zm am = 1. Bằng cách chuyển
7 các giá trị zi sang bên vế phải, ta tìm được i1 , . . . , ik , j1 , . . . , jl sao cho zi1 ai1 + · · · + zik aik = 1 + (−zj1 )aj1 + · · · + (−zjl )ajl . Đặt s = (−zj1 )aj1 +· · ·+(−zjl )ajl . Khi đó s và s+1 đều thuộc S. Ta chứng minh rằng nếu n ≥ (s − 1)s + (s − 1) = s2 − 1 thì n thuộc S. Thật vậy ta chia n cho s ta được n = qs + r với 0 ≤ r < s. Vì n ≥ (s − 1)s + (s − 1) nên q ≥ s − 1 ≥ r. Do đó n = (rs + r) + (q − r)s = r(s + 1) + (q − r)s ∈ S, vì s và s + 1 đều thuộc S. Như vậy Z≥0 \ S là tập con của tập hữu hạn {1, 2, . . . , s2 − 1} và S là nửa nhóm số. Định nghĩa 1.1.3. Nếu S là nửa nhóm số, thì max(Z≥0 \S) =: F (S) là số Frobenius của S. Ta có một cách phát biểu khác như sau. Đặt d(k, a1 , ..., am ) là số các cách biểu diễn của k thành tổ hợp tuyến tính nguyên không âm của a1 , . . . , am . Khi đó F (S) chính là số k lớn nhất sao cho d(k, a1 , ..., am ) = 0. Định lý 1.1.4 (Sylvester). Nếu a, b là hai số nguyên dương nguyên tố cùng nhau thì F (S(a, b)) = ab − a − b. Chứng minh. Ta chứng minh rằng phương trình ab − a − b = ax + by không có nghiệm nguyên không âm x, y. Giả sử phản chứng rằng ab − a − b = ax + by, với x, y nguyên không âm nào đó. Khi đó a(b − x − 1) = b(y + 1). Suy ra y + 1 chia hết cho a (vì a và b nguyên tố cùng nhau). Do đó y ≥ a − 1 và ax + by ≥ b(a − 1) = ab − b > ab − a − b, mâu thuẫn. Mặt khác, xét k là một số nguyên dương bất kỳ lớn hơn ab − a − b. Ta sẽ chứng minh rằng phương trình k = ax + by có nghiệm nguyên không âm x, y. Thật vậy, vì a, b nguyên tố cùng nhau nên tồn tại x, y ∈ Z sao cho
8 k = ax + by. Gọi x0 là số dư của x cho b, tức là x = bq + x0 , với q ∈ Z và 0 ≤ x0 ≤ b − 1. Khi đó k = ax + by = ax0 + b(y + q) = ax0 + by0 , với y0 = y + q. Vì ab − a − b + 1 ≤ k = ax0 + by0 ≤ a(b − 1) + by0 nên 1 1 ≤ b(y0 + 1). Do vậy y0 ≥ > −1 và do đó y0 ≥ 0 vì y0 là số nguyên. b−1 Ta có điều phải chứng minh. Chú ý 1.1.5. (1) Ở chương sau ta sẽ đưa ra một chứng minh khác cho định lý này của Sylvester. (2) Việc tính toán số Frobenius của một nửa nhóm nói chung là một vấn đề khó (xem [5]). Định nghĩa 1.1.6. Một hệ sinh của nửa nhóm số S được gọi là một hệ sinh tối tiểu nếu như không có bất kỳ một tập con thực sự nào của nó sinh ra nửa nhóm số S. Người ta chứng minh được rằng nửa nhóm số S có duy nhất một hệ sinh tối tiểu, đồng thời hệ sinh tổi tiểu này là hữu hạn (ta chứng minh khẳng định này ở dưới đây). Lực lượng của hệ sinh tối tiểu được gọi là chiều nhúng của nửa nhóm số S và được kí hiệu là e(S). Phần tử nhỏ nhất trong hệ sinh tối tiểu được gọi là bội của nửa nhóm số S và được kí hiệu là m(S). Chú ý 1.1.7. (1) Dễ thấy m(S) chính là số nguyên dương nhỏ nhất trong S. Thật vậy giả sử {a1 = m(S) < a2 < . . . < ae } là hệ sinh tối tiểu của S. Xét s là một số nguyên dương bất kỳ trong S. Khi đó s = λ1 a1 + . . . + λe ae , với a1 , . . . , ae ∈ Z≥0 nào đó. Vì s 6= 0 nên tồn tại i sao cho λi 6= 0. Khi đó ta có s ≥ λi ai ≥ ai ≥ a1 , ta có điều phải chứng minh. (2) Người ta có thể chứng minh được rằng e(S) ≤ m(S).
9 Với hai tập A và B gồm các số nguyên, ta gọi A + B = {a + b | a ∈ A, b ∈ B}. Với S là một nửa nhóm số, ta ký hiệu S ∗ = S \ {0}. Mệnh đề 1.1.8. Cho S là một nửa nhóm số. Khi đó S ∗ \ (S ∗ + S ∗ ) là một hệ sinh của S. Hơn nữa mọi hệ sinh của S đều chứa S ∗ \ (S ∗ + S ∗ ). Tức là, S ∗ \ (S ∗ + S ∗ ) là hệ sinh tối thiểu duy nhất của S. Chứng minh. Lấy s là một phần tử của S ∗ . Nếu s 6∈ S ∗ \ (S ∗ + S ∗ ) thì tồn tại x, y ∈ S ∗ sao cho s = x+y. Ta lặp lại việc này đối với x và y, thì sau một số hữu hạn bước (vì x, y < s) ta có thể tìm được s1 , . . . , sn ∈ S ∗ \ (S ∗ + S ∗ ) sao cho s = s1 + · · · + sn . Như vậy ta chứng minh được rằng S ∗ \ (S ∗ + S ∗ ) là một hệ sinh của S. Bây giờ xét A là một hệ sinh bất kỳ của S. Lấy x ∈ S ∗ \ (S ∗ + S ∗ ). Khi đó tồn tại n ≥ 1, λ1 , . . . , λn ∈ Z>0 và a1 , . . . , an ∈ A \ {0} sao cho x = λ1 a1 + · · · + λn an . Vì x 6∈ (S ∗ + S ∗ ) nên ta suy ra n = 1 và λ = 1, tức là x = a1 ∈ A. Như vậy S ∗ \ (S ∗ + S ∗ ) chứa trong A. Mệnh đề sau cho ta một cách để kiểm tra một hệ sinh của nửa nhóm số S có phải là hệ sinh tối tiểu. Mệnh đề 1.1.9. Giả sử nửa nhóm số S có một hệ sinh là {0 6= a1 < a2 < . . . < am }. Khi đó {a1 < a2 < . . . < am } là một hệ sinh tối tiểu khi và chỉ khi ai+1 6∈ S(a1 , . . . , ai ) với mọi i = 1, . . . , m − 1. Chứng minh. "⇒": Giả sử {a1 < a2 < . . . < am } là hệ sinh tối tiểu của S. Khi đó với mọi i = 1, . . . , m − 1 ta có ai+1 6∈ S(a1 , . . . , ai ). Thật vậy, giả sử phản chứng rằng tồn tại i sao cho ai+1 ∈ S(a1 , . . . , ai ). Khi đó {a1 , . . . , ai−1 , ai+1 , . . . , am } cũng là một hệ sinh của S, điều này là mâu thuẫn.
10 "⇐": Giả sử ai+1 6∈ S(a1 , . . . , ai ) với mọi i = 1, . . . , m − 1. Ta chứng minh ai+1 6∈ S(a1 , . . . , ai , ai+2 , . . . , am ). Thật vậy giả sử phản chứng rằng ai+1 = λ1 a1 + · · · + λi ai + λi+2 ai+2 + · · · + λm am , với λj ∈ Z≥0 nào đó. Vì ai+1 < aj với mọi j > i + 1 nên ta có λi+2 = · · · = λm = 0. Điều này suy ra ai+1 = λ1 a1 + · · · + λi ai ∈ S(a1 , . . . , ai ), mâu thuẫn với giả thiết. Như vậy với mọi i thì {a1 , . . . , ai , ai+2 , . . . , am } không là hệ sinh của S và ta có điều phải chứng minh. Định nghĩa 1.1.10. Chuỗi Hilbert của nửa nhóm số S có dạng chuỗi lũy thừa hình thức X HS (x) = xs ∈ Z[[x]]. s∈S Trong thực hành ta thường nhân chuỗi trên với 1 − x và khi đó ta nhận được một đa thức được gọi là đa thức nửa nhóm: X X PS (x) = (1 − x) HS (x) = (1 − x)( xs + xs ) 0≤s≤F (S) s≥F (S)+1 s∈S X X = (1 − x) xs + xF (S)+1 = 1 + (x − 1) xs . 0≤s≤F (S) s∈S / s∈S Nhận xét rằng PS cho ta thông tin về số Frobenius: deg (PS (x)) = F (S) + 1. aS (k)xk . Khi đó ta có P Định lý 1.1.11. Ta viết PS (x) = k≥0     1 nếu k ∈ S, k − 1 6∈ S;  aS (k) = −1 nếu k 6∈ S, k − 1 ∈ S;    0  trong trường hợp còn lại. Chứng minh. Theo định nghĩa ta có X X X PS (x) = aS (k)xk = (1 − x) xj = (xj − xj+1 ). k≥0 j∈S j∈S
11 Ta so sánh hệ số của đồng nhất trên. Nếu k ∈ S và k − 1 6∈ S, thì ta có aS (k) = 1 (vì tổng bên phải chứa hạng tử (xk − xk+1 ) mà số hạng xk không giản ước được). Nếu k 6∈ S nhưng k − 1 ∈ S thì ta có aS (k) = −1 (vì tổng bên phải chứa hạng tử (xk−1 − xk ) mà số hạng xk không giản ước được). Trong các trường hợp còn lại, k ∈ S và k − 1 ∈ S hoặc k 6∈ S và k − 1 6∈ S thì ta đều có aS (k) = 0. Định lý trên suy ra ngay tính chất sau về hệ số của đa thức nửa nhóm số. Hệ quả 1.1.12. Các hệ số khác 0 của PS (x) là xen kẽ giữa 1 và −1. Ví dụ 1.1.13. Xét S = S(2, 7). Khi đó S = {0, 2, 4, 6, →}. Ở đây (và sau này) ”n, → ” để chỉ các số nguyên bắt đầu từ n đều thuộc S. Ta có F (S) = 2 · 7 − 2 − 7 = 5. Tức là 5 là số nguyên dương lớn nhất k sao cho phương trình k = 2x + 7y không có nghiệm không âm. Chiều nhúng của S là e(S) = 2 và bội của S là m(S) = 2. Chuỗi Hilbert của S là X HS (x) = xs = 1 + x2 + x4 + x6 + x7 + x8 + · · · ∈ Z[[x]]. s∈S Đa thức nửa nhóm của S là PS (x) = (1 − x)HS (x) = (1 − x)(1 + x2 + x4 ) + (1 − x)(x6 + x7 + x8 + · · · ) = 1 + x2 + x4 − (x + x3 + x5 ) + x6 = 1 + (x2 + x4 + x6 ) − (x + x3 + x5 ) = 1 + (x − 1)(x + x3 + x5 ). Chú ý rằng ta có (x14 − 1)(x − 1) x7 + 1 = (x2 − 1)(x7 − 1) x+1 = x6 − x5 + x4 − x3 + x2 − x + 1 = PS(2,7) (x). Ví dụ 1.1.14. Xét S = S(4, 7). Khi đó S = {0, 4, 7, 8, 11, 12, 14, 15, 16, 18, →}
12 và F (S) = 4 · 7 − 4 − 7 = 17. Tức là 17 là số nguyên dương lớn nhất k sao cho phương trình k = 4x + 7y không có nghiệm không âm. Chiều nhúng của S là e(S) = 2 và bội của S là m(S) = 4. Chuỗi Hilbert của S là X X HS (x) = xs = 1+x4 +x7 +x8 +x11 +x12 +x14 +x15 +x16 + xi ∈ Z[[x]]. s∈S i≥18 Đa thức nửa nhóm của S là PS (x) =(1 − x)HS (x) =(1 − x)(1 + x4 + x7 + x8 + x11 + x12 + x14 + x15 + x16 ) X + (1 − x) xi i≥18 =1 − x + x4 − x5 + x7 − x9 + x11 − x13 + x14 − x17 + x18 . Tương tự như ví dụ trước, ta có thể kiểm tra được rằng 4 5 7 9 11 13 14 17 18 (x28 − 1)(x − 1) PS (x) = 1−x+x −x +x −x +x −x +x −x +x = 4 . (x − 1)(x7 − 1) Ví dụ 1.1.15. Xét S = S(4, 7, 9). Khi đó S = {0, 4, 7, 8, 9, 11, →} và F (S) = 10. Tức là 10 là số nguyên dương lớn nhất k sao cho phương trình k = 4x + 7y + 9z không có nghiệm không âm. Chiều nhúng của S là e(S) = 3 và bội của S là m(S) = 4. Chuỗi Hilbert của S là X X HS (x) = xs = 1 + x4 + x7 + x8 + x9 + xi ∈ Z[[x]]. s∈S i≥11 Đa thức nửa nhóm của S là PS (x) =(1 − x)HS (x) X =(1 − x)(1 + x4 + x7 + x8 + x9 ) + (1 − x) xi i≥11 =1 − x + x4 − x5 + x7 − x10 + x11 .
13 1.2 Tập Apéry Cho S là một nửa nhóm số và n ∈ S là một phần tử thuộc S khác 0. Tập Apéry của n trong S là tập hợp Ap(S; n) = {s ∈ S | s − n 6∈ S}. Ví dụ xét nửa nhóm số S = S(2, 7) = {0, 2, 4, 6, 7, 8, . . .}. Khi đó Ap(S; 2) = {0, 7}; Ap(S; 7) = {0, 2, 4, 6, 8, 10, 12}; Ap(S; 4) = {0, 2, 7, 9}. Ta có các kết quả tổng quát sau (xem [6, Lemma 2.4] và [6, Lemma 2.6]). Bổ đề 1.2.1. Cho S là một nửa nhóm số và n ∈ S \ {0}. Ta có Ap(S; n) = {0 = w(0), w(1), . . . , w(n − 1)}, ở đây với mỗi i = 0, . . . , n − 1 thì w(i) là số nhỏ nhất trong S mà đồng dư với i modulo n. Chứng minh. Với mỗi i = 0, . . . , n − 1 hiển nhiên ta có w(i) ∈ S. Vì w(i) − n < w(i) và w(i) − n ≡ w(i) ≡ i (mod n), nên w(i) − n không thuộc S (do tính nhỏ nhất của w(i)). Như vậy w(i) thuộc Ap(S, n). Ngược lại giả sử s ∈ Ap(S, n). Gọi i là số dư của s khi chia cho n. Ta có s ≡ w(i) ≡ i mod n. Từ tính nhỏ nhất của w(i), ta suy ra s ≥ w(i) và s − w(i) = kn với k ≥ 0. Giả sử k ≥ 1. Khi đó s − n = w(i) + (k − 1)n ∈ S, mâu thuẫn. Vậy k = 0 và s = w(i). Như vậy khi n ∈ S \ {0} thì Ap(S, n) có n phần tử và lập nên một hệ thặng dư đầy đủ modulo n. Bổ đề 1.2.2. Cho S là một nửa nhóm số và n ∈ S \ {0}. Khi đó với mọi s ∈ S, tồn tại duy nhất (k, w) ∈ Z≥0 × Ap(S, n) sao cho s = kn + w.
14 Chứng minh. Xét s ∈ S bất kỳ. Gọi i là số dư của s khi chia cho n. Như vậy s ≡ w(i) (mod n). Do vậy s = kn + w(i). Vì tính nhỏ nhất của w(i), ta suy ra k ≥ 0. Tính duy nhất của k và w(i) là hiển nhiên. Bổ đề trên suy ra rằng S = Ap(S; n) + nZ≥0 . Chú ý 1.2.3. Người ta có thể định nghĩa nửa nhóm số như sau. Tập con S của Z≥0 được gọi là một nửa nhóm số nếu nó đóng với phép cộng và phần bù Z≥0 \ S là hữu hạn (*). Khi đó ta có thể chứng minh được rằng mọi S như vậy đều có dạng S(a1 , . . . , am ) với một bộ các số nguyên dương a1 , . . . , am nào đó. Thật vậy, các Bổ đề 1.2.1 và Bổ đề 1.2.2 vẫn đúng cho nửa nhóm số S theo nghĩa (*). Hơn nữa, lấy n ∈ S ∗ bất kỳ. Khi đó theo Bổ đề 1.2.2, tập Ap(S; n) ∪ {n} là một hệ sinh của S và tập này là tập hữu hạn theo Bổ đề 1.2.1. Như vậy, nếu viết Ap(S; n) ∪ {n} = {a1 , . . . , am } thì S = S(a1 , . . . , am ). Hệ quả 1.2.4. Cho S là một nửa nhóm số và n ∈ S \ {0}. Khi đó 1 X HS (x) = n xw . 1−x w∈Ap(S;n) Chứng minh. Từ Bổ đề 1.2.1 và Bổ đề 1.2.2 ta có ∞ X s X w X 1 X HS (x) = x = x xkn = xw . 1 − xn s∈S w∈Ap(S;p) k=0 w∈Ap(S;n) Hệ quả 1.2.5. Cho S là một nửa nhóm số và n ∈ S \ {0}. Khi đó F (S) = max Ap(S; n) − n. Chứng minh. Theo định nghĩa PS (x) = (1 − x)HS (x). Do vậy từ Hệ quả trên ta suy ra F (S) = deg PS − 1 = max Ap(S; n) − n.
15 Trong chương sau ta sẽ cần kết quả sau đây: Bổ đề 1.2.6. Cho p và q là hai số nguyên tố cùng nhau. Khi đó Ap(S(p, q); p) = {0, q, 2q, . . . , (p − 1)q}. Chứng minh. Xét s ∈ Ap(S(p, q); p) bất kỳ. Khi đó vì s ∈ S nên s = px+qy với x, y không âm nào đó. Mặt khác vì s − p = p(x − 1) + qy 6∈ S nên x = 0. Do vậy s = qy. Gọi i là số dư của s = qy cho p. Khi đó qy là số nhỏ nhất trong S mà đồng dư với i modulo p. Do vậy y ≤ p − 1. Như vậy ta có Ap(S(p, q); p) ⊆ {0, q, 2q, . . . , (p − 1)q}. Ta đã biết rằng Ap(S(p, q); p) có đúng p. Điều này suy ra Ap(S(p, q); p) = {0, q, 2q, . . . , (p − 1)q}. Chú ý 1.2.7. Ta có thể chứng minh bổ đề trên bằng cách sử dụng (phần đầu chứng minh) Định lý của Sylvester như sau. Xét s = kq với 0 ≤ k ≤ p − 1. Hiển nhiên s ∈ S. Ta có kq − p ≤ (p − 1)q − p = pq − p − q. Do vậy kp − q 6∈ S. Như vậy kp ∈ Ap(S(p, q), p) và ta có {0, q, 2q, . . . , (p − 1)q} ⊆ Ap(S(p, q); p). Nhưng cả tập bên trái và tập bên phải của bao hàm trên đều có p phần tử, nên hai tập này phải bằng nhau và ta có điều phải chứng minh.
16 Chương 2 Mối liên hệ giữa nửa nhóm số và đa thức bù trừ 2.1 Đa thức chia đường tròn và đa thức bù trừ Định nghĩa 2.1.1. Đa thức chia đường tròn thứ n, Φn (x) được định nghĩa bởi ϕ(n) Y X Φn (x) = (x − ζnj ) = an (k)xk , 1≤j≤n k=0 (j,n)=1 2πi 2π 2π với ζn = e n = cos + i sin là căn bậc n của đơn vị. n n Sau đây là một số tính chất cơ bản của đa thức chia đường tròn. 1. Đa thức chia đường tròn có bậc ϕ(n), với ϕ là hàm Euler. 2. Đa thức Φn (x) là đa thức với hệ số nguyên và nó bất khả quy trên trường số hữu tỷ. 3. Ta cũng có phân tích đa thức xn − 1 thành tích Y xn − 1 = Φd (x). d|n
17 Dùng phép nghịch đảo M¨obius ta suy ra Y µ(n/d) Φn (x) = xd − 1 , d|n trong đó µ(n) là hàm M¨obius. Ta nhắc lại rằng hàm µ(n) được định nghĩa như sau. Ta có µ(1) = 1 và với n ≥ 2 thì      1 nếu n là tích của một số chẵn các số nguyên tố phân biệt,  µ(n) = −1 nếu n là tích của một số lẻ các số nguyên tố phân biệt,    0  trong trường hợp còn lại. Nói riêng nếu p |n là một số nguyên tố, thì Φpn (x) = Φn (xp ). Ví dụ 2.1.2. (1) Nếu p là một số nguyên tố thì Φp (x) = 1 + x + · · · + xp−1 . (2) Nếu p, q là hai số nguyên tố phân biệt thì pq xp − 1 xq − 1 x − 1 = Φ1 (x)Φp (x)Φq (x)Φpq (x) = (x − 1). . .Φpq (x) x−1 x−1 Do vậy (xpq − 1)(x − 1) Φpq (x) = p . (x − 1)(xq − 1) Sau đây ta sẽ xem xét đa thức bù trừ do Bachman đưa ra [?], có thể xem như là một tổng quát hóa của đa thức chia đường tròn. Xét ρ = {r1 , r2 , . . . , rs } là một tập gồm một số số nguyên thỏa mãn ri > 1 và (ri , rj ) = 1 với i 6= j. Ta đặt Y n0 n0 n0 = ri , ni = , nij = [i 6= j] , . . . i ri ri rj Với mỗi ρ như trên, ta định nghĩa một hàm Qρ bởi công thức (xn0 − 1) · i
18 Định lý 2.1.3. Ta có Y Qρ (x) = (x − ω), ω ở đây tích lấy trên tập các ω mà ω n0 = 1 nhưng ω ni 6= 1 ∀ 1 ≤ i ≤ s. Q Hơn nữa bậc của đa thức Qρ (x) bằng d := i (ri − 1). Chứng minh. Với mỗi i = 0, 1, . . . , s ta đặt Ai = {ω | ω ni = 1}. Với mỗi tập con I của tập {1, . . . , s} ta đặt AI = ∩i∈I Ai . Ta kiểm tra được rằng A{i,j} = {ω | ω nij = 1}, ∀i < j, A{i,j,k} = {ω | ω nijk = 1}, ∀i < j < k, ... Đặt s ! [ B = A0 \ Ai = {ω | ω n0 = 1, ω ni 6= 1 ∀ 1 ≤ i ≤ s}. i=1 Ta khai triển tất cả các nhân tử trên cả tử và mẫu của Qρ (x) ra thừa số dạng x − ω. Bây giờ ta xét một thừa số dạng x − ω như vậy. Hiển nhiên ta có ω n0 = 1. Giả sử ω 6∈ B. Khi đó gọi I là tập các chỉ số i ∈ {1, . . . , s} sao cho ω ∈ Ai . Khi đó I là tập khác rỗng. Ta đặt k = |I| ≥ 1. Ta có số nhân tử (x − ω) xuất hiện trên tử số của Qρ (x) là k k 1+ + + ··· . 2 4 Số nhân tử (x − ω) xuất hiện trên mẫu số của Qρ (x) là k k k + + + ··· . 1 3 5 Vì ki=0 ki = 0 nên số nhân tử (x − ω) xuất hiện trên tử số của Qρ (x) sẽ P triệt tiêu số nhân tử (x − ω) xuất hiện ở mẫu số của Qρ (x).