ĐẠ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∈S
(cid:88) xs = 1 + x3 + x6 + x7 + x9 + x10 + x12 + x13 + x14 + · · · ∈ Z[[x]]. HS(x) =
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 x2 + x + 1 (x21 − 1)(x − 1) (x3 − 1)(x7 − 1)
Nhận xét rằng bằng đa thức chia đường tròn Φ21(x). Do (x21 − 1)(x − 1) (x3 − 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 = {x1a1 + · · · + xmam | 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 z1a1 + · · · + zmam = 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
zi1ai1 + · · · + zikaik = 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 ≤ b(y0 + 1). Do vậy y0 ≥ > −1 và do đó y0 ≥ 0 vì y0 là số nguyên. 1 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 = λ1a1 + . . . + λeae,
với a1, . . . , ae ∈ Z≥0 nào đó. Vì s (cid:54)= 0 nên tồn tại i sao cho λi (cid:54)= 0. Khi đó ta có s ≥ λiai ≥ 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 (cid:54)∈ 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 = λ1a1 + · · · + λnan.
Vì x (cid:54)∈ (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 (cid:54)= a1 < a2 <
. . . < am}. Khi đó {a1 < a2 < . . . < am} là một hệ sinh tối tiểu khi và chỉ
khi ai+1 (cid:54)∈ 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 (cid:54)∈ 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 (cid:54)∈ S(a1, . . . , ai) với mọi i = 1, . . . , m − 1. Ta chứng
minh ai+1 (cid:54)∈ S(a1, . . . , ai, ai+2, . . . , am). Thật vậy giả sử phản chứng rằng
ai+1 = λ1a1 + · · · + λiai + λi+2ai+2 + · · · + λmam,
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 = λ1a1 + · · · + λiai ∈ 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
s∈S
(cid:88) xs ∈ Z[[x]]. HS(x) =
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:
s≥F (S)+1
0≤s≤F (S) s∈S
(cid:88) (cid:88) xs + xs) PS(x) = (1 − x) HS(x) = (1 − x)(
s /∈S
0≤s≤F (S) s∈S
(cid:88) (cid:88) = (1 − x) xs + xF (S)+1 = 1 + (x − 1) xs.
Nhận xét rằng PS cho ta thông tin về số Frobenius:
deg (PS(x)) = F (S) + 1.
k≥0
Định lý 1.1.11. Ta viết PS(x) = (cid:80) aS(k)xk. Khi đó ta có
nếu k ∈ S, k − 1 (cid:54)∈ S; 1
aS(k) = −1 nếu k (cid:54)∈ S, k − 1 ∈ S;
trong trường hợp còn lại. 0
Chứng minh. Theo định nghĩa ta có
j∈S
j∈S
k≥0
(cid:88) (cid:88) (cid:88) xj = (xj − xj+1). PS(x) = aS(k)xk = (1 − x)
11
Ta so sánh hệ số của đồng nhất trên. Nếu k ∈ S và k − 1 (cid:54)∈ 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 (cid:54)∈ 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 (cid:54)∈ S và k − 1 (cid:54)∈ 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à
s∈S
(cid:88) xs = 1 + x2 + x4 + x6 + x7 + x8 + · · · ∈ Z[[x]]. HS(x) =
Đ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) (x2 − 1)(x7 − 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à
i≥18
s∈S
(cid:88) (cid:88) xs = 1+x4+x7+x8+x11+x12+x14+x15+x16+ xi ∈ Z[[x]]. HS(x) =
Đ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)
i≥18
(cid:88) + (1 − x) xi
=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
. PS(x) = 1−x+x4−x5+x7−x9+x11−x13+x14−x17+x18 = (x28 − 1)(x − 1) (x4 − 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à
i≥11
s∈S
(cid:88) (cid:88) xs = 1 + x4 + x7 + x8 + x9 + xi ∈ Z[[x]]. HS(x) =
Đa thức nửa nhóm của S là
PS(x) =(1 − x)HS(x)
i≥11
(cid:88) =(1 − x)(1 + x4 + x7 + x8 + x9) + (1 − x) xi
=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 (cid:54)∈ 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 đó
w∈Ap(S;n)
(cid:88) xw. HS(x) = 1 1 − xn
Chứng minh. Từ Bổ đề 1.2.1 và Bổ đề 1.2.2 ta có
∞ (cid:88)
s∈S
k=0
w∈Ap(S;p)
w∈Ap(S;n)
(cid:88) (cid:88) (cid:88) xs = xw xkn = xw. HS(x) = 1 1 − xn
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 (cid:54)∈ 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 (cid:54)∈ 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
ϕ(n) (cid:88)
bởi
n) =
k=0
1≤j≤n (j,n)=1
n = cos
(cid:89) (x − ζ j an(k)xk, Φn(x) =
+ i sin là căn bậc n của đơn vị. với ζn = e 2πi 2π n 2π 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
d|n
(cid:89) xn − 1 = Φd(x).
17
Dùng phép nghịch đảo M¨obius ta suy ra
d|n
(cid:89) (cid:0)xd − 1(cid:1)µ(n/d) , Φn(x) =
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ì
nếu n là tích của một số chẵn các số nguyên tố phân biệt, 1
µ(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ì
. xpq − 1 = Φ1(x)Φp(x)Φq(x)Φpq(x) = (x − 1). .Φpq(x) xp − 1 x − 1 xq − 1 x − 1
Do vậy
. Φpq(x) = (xpq − 1)(x − 1) (xp − 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 (cid:54)= j.
Ta đặt
i
(cid:89) [i (cid:54)= j] , . . . n0 = ri, ni = , nij = n0 ri n0 rirj
Với mỗi ρ như trên, ta định nghĩa một hàm Qρ bởi công thức
i . Qρ(x) = (cid:81) (xn0 − 1) · (cid:81)
i (xni − 1) · (cid:81) Ví dụ, nếu ρ = {p, q}, thì . Q{p,q} (x) = (xpq − 1) (x − 1)
(xp − 1) (xq − 1) i (ri − 1). Ta có thể chứng minh rằng Qρ (x) là một đa thức bậc d := (cid:81) 18 Định lý 2.1.3. Ta có ω (cid:89) (x − ω), Qρ(x) = ở đây tích lấy trên tập các ω mà ωn0 = 1 nhưng ωni (cid:54)= 1 ∀ 1 ≤ i ≤ s. i (ri − 1). Hơn nữa bậc của đa thức Qρ(x) bằng d := (cid:81) 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∈IAi. Ta kiểm tra được rằng ∀i < j, ∀i < j < k, A{i,j} = {ω | ωnij = 1},
A{i,j,k} = {ω | ωnijk = 1}, . . . Đặt i=1 (cid:33) (cid:32) s
(cid:91) = {ω | ωn0 = 1, ωni (cid:54)= 1 ∀ 1 ≤ i ≤ s}. Ai B = A0 \ 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ử ω (cid:54)∈ 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à
(cid:19) (cid:19) + + · · · . 1 + (cid:18)k
2 (cid:18)k
4 Số nhân tử (x − ω) xuất hiện trên mẫu số của Qρ(x) là
(cid:19) (cid:19) (cid:19) + · · · . + + (cid:18)k
1 (cid:18)k
3 i=0 Vì (cid:80)k (cid:18)k
5
(cid:1) = 0 nên số nhân tử (x − ω) xuất hiện trên tử số của Qρ(x) sẽ (cid:0)k
i triệt tiêu số nhân tử (x − ω) xuất hiện ở mẫu số của Qρ(x). 19 Hiển nhiên rằng nếu ω ∈ B thì nhân tử (x − ω) xuất hiện đúng một lần
trên tử số của Qρ(x) (trong thừa số xn0 − 1) và không xuất hiện lần nào ở mẫu số của Qρ(x). Từ đó ta có khẳng định thứ nhất của định lý. Từ nguyên lý bù trừ ta có deg Qρ(x) = |B| = |A0| − | ∪s i=1 Ai|
(cid:88) i i i (cid:88) (cid:88) = n0 − ( ni − nijk − · · · ) nij + = (r1 − 1)(r2 − 1) · · · (rs − 1) = d, tức là ta đã chứng minh khẳng định thứ hai của định lý. Định nghĩa 2.1.4. Một đa thức Qρ như trên được gọi là một đa thức bù trừ. k≥0 Ta định nghĩa các hệ số aρ (k) của đa thức này bởi Qρ (x) = (cid:80) aρ (k) xk. Chú ý rằng Qρ (x) là tự thuận nghịch; nghĩa là aρ (k) = aρ (d − k), cũng có nghĩa là (cid:19) . Qρ (x) = xdQρ (cid:18) 1
x (Ở chương sau, ta sẽ kiểm tra tính tự thuận nghịch của đa thức Qρ trong trường hợp ρ = {p, q}.) Nếu tất cả những phần tử của ρ là nguyên tố, thì ta có Qρ (x) = Φr1r2···rs (x) . Cho n là một số nguyên tùy ý và gọi γ(n) = p1 · · · ps là tích của các ước
nguyên tố phân biệt của n. Khi đó, ta có Q{p1,··· ,ps}(xn/γ(n)) = Φn(x). Như
vậy đa thức bù trừ là tổng quát hóa của đa thức chia đường tròn. Đa thức bù trừ có thể biểu diễn như là tích của các đa thức chia đường tròn, theo như kết quả sau cũng của Bachman [1]. Định lý 2.1.5. Cho trước ρ = {r1, . . . , rs} và i (cid:40) (cid:41) (cid:89) d | d là ước của . Dρ = ri và (d, ri) > 1 với mọi i 20 Khi đó d∈Dρ (cid:89) Qρ (x) = Φd(x). Chứng minh. Vì hai vế của đẳng thức cần chứng minh là hai đa thức chuẩn (monic) với các nghiệm đều là nghiệm đơn, nên ta chỉ cần chứng minh chúng có cùng tập nghiệm. Xét ω là một nghiệm bất kỳ của Qρ và gọi d là số nguyên dương nhỏ
nhất sao cho ωd = 1. Khi đó ω là một nghiệm của Φd(x). Hơn nữa theo Định lý 2.1.3, ta có d ∈ D vì d | n0 và (d, ri) > 1 với mọi i. Đối với chiều ngược lại, ta cố định một d ∈ D và gọi ω là một nghiệm
bất kỳ của Φd. Khi đó ωn0 = 1. Hơn nữa vì (d, ri) > 1 nên d (cid:45) ni. Ta suy ra
ωni (cid:54)= 1. Do vậy theo Định lý 2.1.3, ω là một nghiệm của Qρ. Ví dụ 2.1.6. Xét ρ = {4, 7}. Khi đó D = {14, 28} và ta có Q{4,7}(x) = Φ28(x)Φ14(x). Tổng quát hơn nếu ρ = {p, q} với p và q nguyên tố cùng nhau, thì d|pq,d(cid:45)p,d(cid:45)q 2.2 Định lý chính (cid:89) Φd(x). Q{p,q}(x) = Định lý sau đây là định lý chính của chương này. Nó cho ta mối liên hệ giữa nửa nhóm số chiều nhúng 2 với đa thức bù trừ nhị phân. Định lý 2.2.1. Nếu p, q > 1 là những số nguyên tố cùng nhau, khi đó PS(p,q) (x) = Q{p,q} (x). Ta sẽ đưa ra hai chứng minh cho định lý này. Chứng minh đầu tiên sẽ sử dụng một trong những công cụ đa năng nhất trong lý thuyết nửa nhóm số, đó là sử dụng tập Apéry trình bày ở Chương 1, Mục 1.2. 21 Chứng minh đầu tiên của Định lý 2.2.1. Từ Hệ quả 1.2.4 và Bổ đề 1.2.6, ta có (cid:88) xw HS(p,q)(x) = 1
1 − xp w∈Ap(S(p,q);p)
1 + xq + x2q + · · · + x(p−1)q
1 − xp = = . 1 − xpq
(1 − xp)(1 − xq) Do vậy PS(p,q)(x) = (1 − x)HS(p,q)(x) = = Q{p,q}(x). (1 − x)(1 − xpq)
(1 − xp)(1 − xq) Ta có điều phải chứng minh. Định lý trên cho ta một chứng minh khác cho định lý sau của Sylvester Hệ quả 2.2.2 (Sylvester). Cho p, q là hai số nguyên dương nguyên tố cùng nhau. Khi đó F (S(p, q)) = pq − p − q. Chứng minh. Ta có F (S(p, q)) = deg PS(p,q)(x) − 1 = deg Q{p,q}(x) − 1 = pq − p − q, điều phải chứng minh Chứng minh thứ hai sử dụng điểm xuất phát là nhận xét rằng a≥0 j≥0 b≥0 (cid:32) (cid:33) (cid:32) (cid:33) (cid:88) (cid:88) (cid:88) = xa xb = r(j)xj, 1
(1 − xp)(1 − xq) ở đây r(j) là số phần tử của tập {(a, b) | a ≥ 0, b ≥ 0, ap + bq = j}. Như vậy r (j) = d (j; p, q). Liên quan tới r(j), ta có bổ đề sau đây. Bổ đề 2.2.3. Giả sử k ≥ 0, khi đó r(k + pq) = r(k) + 1. Chứng minh. Đặt α ≡ kp−1 (mod q), với 0 ≤ α < q; đặt β ≡ kq−1 (mod q), với 0 ≤ β < q; và đặt k0 = αp + βq. Ta có k ≡ k0 (mod pq). 22 Rõ ràng rằng k0 < 2pq. Nhận xét thêm rằng α, β là nghiệm nguyên không âm duy nhất thỏa mãn k0 = αp + βq. Thật vậy giả sử ta có k0 =
α(cid:48)p + β(cid:48)q với α(cid:48), β(cid:48) không âm. Ta xét trường hợp α ≤ α(cid:48). Ta có (α(cid:48) − α)p = (β − β(cid:48))q. Do vậy α − α(cid:48) chia hết cho q. Ta đặt α(cid:48) − α = qn với n nguyên không âm nào đó. Khi đó k0 = α(cid:48)p + β(cid:48)q = αp + (β(cid:48) + np)q. Suy ra β = β(cid:48) + np. Vì β < p nên n = 0 và α = α(cid:48), β = β(cid:48). Trường hợp α ≥ α(cid:48) thì β ≤ β(cid:48) và tương tự như trên ta cũng suy ra α = α(cid:48), β = β(cid:48). Tóm lại ta có r(k0) = 1. Bây giờ giả sử k /∈ S. Khi đó k < k0 vì ngược lại thì k = k0 + npq với n ≥ 0 nào đó, điều này dẫn đến k ∈ S, mâu thuẫn. Vì k0 < 2pq nên k + pq = k0 ∈ S. Từ đó suy ra, nếu r(k) = 0 thì r(k + pq) = r(k0) = 1. Tiếp theo ta giả sử k ∈ S. Khi đó k = k0 + tpq với t ≥ 0. Ta có k = (α + tq)p + βq = (α + (t − 1)q)p + (β + p)q = · · · = αp + (β + tp)q. Giả sử k = α(cid:48)p + β(cid:48)q với α(cid:48), β(cid:48) nguyên không âm. Vì k ≡ k0 = αp + βq
(mod pq) và (p, q) = 1 nên α(cid:48) ≡ α (mod p). Do đó α(cid:48) = α + qa với a ≥ 0 nguyên nào đó. Tương tự β(cid:48) = β + pb với b ≥ 0 nào đó. Do vậy k = αp + βq + pq(a + b) = k0 + pq(a + b). Suy ra a + b = t và phương trình k = xp + yq có đúng t + 1 nghiệm nguyên không âm. Do vậy r(k) = t + 1 và r(k + pq) = 1 + t + 1 = r(k) + 1. Bổ đề 2.2.4. Ta có r(j) ≤ 1 nếu j < pq và r(j) ≥ 1 nếu j ≥ pq. Chứng minh. Chứng minh tương tự như Bổ đề trên, ta suy ra r(j) ≤ 1 với j < pq. Thật vậy giả sử j = αp + βq = α(cid:48)p + β(cid:48)q với α, β, α(cid:48), β(cid:48) nguyên không âm. Khi đó 0 ≤ α, α(cid:48) < q vì j < pq. Ta cũng có p(α−α(cid:48)) = q(β(cid:48) −β). Suy ra α − α(cid:48) chia hết cho q vì (p, q) = 1. Điều này lại suy ra α = α(cid:48) và do đó β = β(cid:48), điều phải chứng minh. 23 Ta ghi lại một hệ quả sau đây của chứng minh của Bổ đề 2.2.3 và Bổ đề 2.2.4. Hệ quả này sẽ được sử dụng ở mục sau trong nghiên cứu về đa thức bù trừ nhị phân. Hệ quả 2.2.5. Cho p, q > 1 là hai số nguyên nguyên tố cùng nhau. Cho 0 ≤ k < pq. Khi đó hoặc k = αp+βq hoặc k = αp+βq−pq với 0 ≤ α ≤ q−1 là số nguyên duy nhất thỏa mãn αp ≡ k (mod q) và 0 ≤ β ≤ p − 1 là số nguyên duy nhất thỏa mãn βq ≡ k (mod p). Chứng minh. Nếu k ∈ S(p, q) thì theo Bổ đề trên ta có r(k) = 1, tức là tồn tại duy nhất α, β không âm sao cho k = αp + βq. Vì k = αp + βq = k < pq nên 0 ≤ α ≤ q − 1 và αp ≡ k (mod q). Tương tự, ta có 0 ≤ β ≤ p − 1 và βq ≡ k (mod p). Nếu k (cid:54)∈ S(p, q) thì theo chứng minh của Bổ đề 2.2.3, ta có k + pq = αp + βq, ở đây 0 ≤ α ≤ q − 1 là số nguyên dương duy nhất thỏa mãn αp ≡ k (mod q) và 0 ≤ β ≤ p − 1 là số nguyên dương duy nhất thỏa mãn βq ≡ k (mod p). Chú ý 2.2.6. Ta có thể tìm ra công thức cụ thể cho r(n). Gọi p−1 là nghịch đảo của p modulo q. Gọi q−1 là nghịch đảo của q modulo p. Khi đó ta có công thức (cid:27) (cid:27) r(n) = − − + 1 n
pq (cid:26)p−1n
q (cid:26)q−1n
p ở đây {x} là hàm phần thập phân. Chú ý rằng Bổ đề 2.2.3 là một hệ quả của công thức này. Chứng minh thứ hai cho Định lý 2.2.1. Từ Bổ đề 2.2.3, ta suy ra rằng pq−1
(cid:88) ∞
(cid:88) j≥0 j=0 j=pq pq−1
(cid:88) (cid:88) (1 − xpq) r(j)xj = r(j)xj + (r(j) − r(j − pq)) xj j=0 j≥pq j∈S(p,q) (cid:88) (cid:88) = r(j)xj + xj = xj, ở đây ta đã sử dụng bổ đề ngay phía trên rằng r(j) ≤ 1 nếu j < pq. 24 2.3 Đa thức bù trừ nhị phân Bổ đề 2.3.1. Cho p, q > 1 là hai số nguyên dương nguyên tố cùng nhau. Khi đó tồn tại duy nhất hai số không âm ρ, σ sao cho 1 + pq = ρp + σq. Chứng minh. Bổ đề này có thể chứng minh trực tiếp. Tuy nhiên để cho ngắn gọn ta sẽ sử dụng Bổ đề 2.2.3 để chứng minh nó. Vì p, q > 1 nên r(1) = 0. Theo Bổ đề 2.2.3, ta có r(1 + pq) = r(1) + 1, tức là tồn tại duy nhất σ, ρ không âm sao cho 1 + pq = ρp + σq. thức Q{p,q} = (cid:80) Xét p, q > 1 là hai số nguyên dương nguyên tố cùng nhau. Khi đó đa
m≥0 a{p,q}(m)xm được gọi là một đa thức bù trừ nhị phân.
Mệnh đề sau cho thông tin cụ thể về hệ số của đa thức bù trừ nhị phân. Mệnh đề 2.3.2. Cho p, q > 1 là hai số nguyên nguyên tố cùng nhau. Gọi ρ và σ là những số nguyên không âm (duy nhất) sao cho 1 + pq = ρp + σq. Cho 0 ≤ m < pq. Khi đó hoặc là m = αp + βq hoặc m = αp − βq − pq với 0 ≤ α ≤ q − 1 là số nguyên duy nhất sao cho αp ≡ m (mod q) và 0 ≤ β ≤ p − 1 là số nguyên duy nhất sao cho βq ≡ m (mod p). Hệ số a{p,q} (m) của đa thức Q{p,q}(x) bằng nếu m = αp + βq với 0 ≤ α ≤ ρ − 1, 0 ≤ β ≤ σ − 1;
1 −1 nếu m = αp + βq − pq với ρ ≤ α ≤ p − 1, σ ≤ β ≤ q − 1; 0 trong các trường hợp còn lại.
ρ−1
(cid:88) q−1
(cid:88) p−1
(cid:88) σ−1
(cid:88) Chứng minh. Ta thấy rằng i=0 i=ρ j=σ xip xip xjq xjq − x−pq j=0
xρp − 1
xp − 1 · · = xσq − 1
xq − 1 − x−pq xpq − xρp
xp − 1 xpq − xσq
xq − 1 25 = − xpq − xρp − xσq + x
(xp − 1)(xq − 1) = xpq+1 − xρp − xσq + 1
(xp − 1)(xq − 1)
xpq+1 − xpq − x + 1
(xp − 1)(xq − 1) = Q{p,q}(x). ρ−1
(cid:80)
i=0 σ−1
(cid:80)
j=0 q−1
(cid:80)
i=ρ p−1
(cid:80)
j=σ Khi khai triển hai tích trong biểu thức xip xjq − x−pq xip xjq, các đơn thức nhận được có số mũ là ip + jq với 0 ≤ i ≤ ρ − 1, 0 ≤ j ≤ σ − 1 và số mũ ip + jq − pq với ρ ≤ i ≤ q − 1 và σ ≤ j ≤ p − 1. Theo Hệ quả 2.2.5 các số mũ này là phân biệt, do vậy ta có điều phải chứng minh. Hệ quả 2.3.3. Số những hệ số dương trong Q{p,q} (x) bằng ρσ và số những hệ số âm trong Q{p,q} (x) bằng ρσ − 1. Chứng minh. Suy ngay ra từ mệnh đề trên. Mệnh đề 2.3.2 có thể được mô tả một cách đẹp đẽ với sơ đồ LLL (viết tắt cho Lenstra, Lam và Lung). Dưới đây là một trong những sơ đồ như vậy trong trường hợp p = 5 và q = 7. Chú ý rằng ρ = σ = 3 trong trường hợp này 1 + 5 · 7 = 36 = 3 · 5 + 3 · 7 8 13 18 23 28 33 3 1 6 11 16 21 26 31 14 19 24 29 34 4 9 7 12 17 22 27 32 2 0 5 10 15 20 25 30 Ta bắt đầu với số 0 ở phía dưới cùng bên trái và thêm p cho mỗi bước di chuyển sang phải và thêm q cho mỗi bước di chuyển lên trên. Sau đó ta rút gọn modulo pq. Mọi số nguyên 0, . . . , pq − 1 sẽ được nhận một cách 26 chính xác một lần bằng cách này (theo Định lý thặng dư Trung Hoa). Ta kẻ một dòng kẻ ngang bên dưới giá trị 1 và một dòng kẻ đứng bên trái giá trị 1. Khi đó ta được sơ đồ LLL cho hai giá trị p và q. Mệnh đề 2.3.2 có thể được phát biểu lại theo cách sau. Mệnh đề 2.3.4. Cho p, q > 1 là những số nguyên dương nguyên tố cùng nhau. Những số trong góc dưới, bên trái của sơ đồ LLL là số mũ của những số hạng trong Q{p,q} với hệ số 1. Những số trong góc trên, bên phải là số mũ của những số hạng trong Q{p,q} với hệ số −1. Tất cả những hệ số còn lại bằng 0. Ví dụ 2.3.5. Xét p = 4 và q = 7. Trong trường hợp này 1 + 4 · 7 = 29 = 2 · 4 + 3 · 7 và sơ đồ LLL là bảng dưới đây. 1 5 9 13 17 21 25 14 18 22 26 2 6 10 7 11 15 19 23 27 3 8 12 16 20 24 0 4 Như vậy Q{4,7}(x) = 1 + x4 + x7 + x11 + x14 + x18 − x − x5 − x9 − x13 − x17
= 1 − x + x4 − x5 + x7 − x9 + x11 − x13 + x14 − x17 + x18 = PS(4,7)(x). 27 3.1 Nửa nhóm số đối xứng Định nghĩa 3.1.1. Một nửa nhóm số S được gọi là đối xứng nếu S ∪ (F (S) − S) = Z, ở đây F (S) − S = {F (S) − s |s ∈ S }. Ví dụ 3.1.2. Xét S = S(2, 7) = {0, 2, 4, 6, 7, 8, →}. Khi đó F (S) = 5 và F (S) − S = {F (S) − s | s ∈ S} = {5, 3, 1, −1, −2, −3, ←}. Do vậy S ∪ (F (S) − S) = Z và S = S(2, 7) là đối xứng. Ví dụ 3.1.3. Xét S = S(4, 7). Khi đó, F (S) = 17 và S = {0, 4, 7, 8, 11, 12, 14, 15, 16, 18, →}, và F (S) − S = {17, 13, 10, 9, 6, 5, 3, 2, 1, 0, ←}. Do vậy S ∪ (F (S) − S) = Z, và S = S(2, 7) là đối xứng. Tổng quát hơn ta luôn có S(p, q) là đối xứng ([6, Corollary 4.7]). Ta sẽ đưa ra một chứng minh cho kết quả này ở mục sau. 28 Ví dụ 3.1.4. Xét S = S(3, 4, 5) = {0, 3, →}. Khi đó F (S) = 2 và F (S) − S = {2, −1, ←}. Ta có S ∪ (F (S) − S) không chứa 1, tức là nó là tập con
thực sự của Z. Do vậy S = S(3, 4, 5) không đối xứng. Ví dụ 3.1.5. Xét S = S(4, 6, 7) = {0, 4, 6, 7, 8, 10, →}. Khi đó F (S) = 9 và F (S) − S = {9, 5, 3, 2, 1, 0, ←}, và S là đối xứng. Định lý 3.1.6. Cho S là một nửa nhóm số. Khi đó S là đối xứng nếu và chỉ nếu PS(x) là tự thuận nghịch. Chứng minh. Nếu s ∈ S ∩(F (S) − S), thì s = F (S)−s1 với s1 ∈ S nào đó. Điều này dẫn đến F (S) = s + s1 ∈ S, mâu thuẫn. Do vậy S và F (S) − S là hai tập rời nhau. Do đó {j | 0 ≤ j ≤ F (S), j ∈ S}(cid:116){F (S)−j | 0 ≤ j ≤ F (S), j ∈ S} ⊆ {0, 1, . . . , F (S)}. Vì mọi số nguyên n ≥ F (S) + 1 thuộc S và mọi số nguyên n ≤ −1 thuộc F (S) − S nên S là đối xứng khi và chỉ khi {0, 1, . . . , F (S)} = {j | 0 ≤ j ≤ F (S), j ∈ S}(cid:116){F (S)−j | 0 ≤ j ≤ F (S), j ∈ S}, điều này lại tương đương với 0≤j≤F (S)
j∈S 0≤j≤F (S)
j∈S (cid:88) (cid:88) xj + xF (S)−j = 1 + x + · · · + xF (S). ((*)) Mặt khác PS(x) là đa thức bậc F (S) + 1 và 0≤j≤F (S)
j∈S (cid:88) xj. PS(x) = xF (S)+1 + (1 − x) 29 Do vậy (cid:19) xF (S)+1PS − PS (x) =1 − xF (S)+1+ (cid:18) 1
x 0≤j≤F (S)
j∈S 0≤j≤F (S)
j∈S (cid:88) (cid:88) (x − 1) xj + xF (S)−j .
(cid:19) Từ đó ta suy ra xF (S)+1PS = PS (x) nếu và chỉ nếu có đẳng thức (*). (cid:18) 1
x Như vậy PS(x) là tự thuận nghịch nếu và chỉ nếu S là đối xứng. Hệ quả 3.1.7. Cho S là một nửa nhóm số và cho n là một số nguyên dương thuộc S. Giả sử Ap(S; n) = {0 = a0 < a1 < · · · < an−1} là tập Apéry của n trong S. Khi đó S là đối xứng khi và chỉ khi ai + an−1−i = an−1 với mọi i ∈ {0, . . . , n − 1}. Chứng minh. Ta có w∈Ap(S;n) (cid:88) xw PS(x) = 1 − x
1 − xn = 1 − x
1 − xn (1 + xa1 + · · · + xan−1) . có bậc bằng deg PS(x) = an−1 − n + 1. Do vậy (cid:0)1 + x−a1 + · · · + x−an−1(cid:1) xan−1−n+1PS( 1
x ) = xan−1−n+1 1 − x−1
1 − x−n = (cid:0)xan−1 + xan−1−a1 + · · · + x0(cid:1) = (cid:0)1 + xan−1−an−2 + · · · + xan−1(cid:1) . x − 1
xn − 1
1 − x
1 − xn Do đó S là đối xứng khi và chỉ khi PS(x) là tự thuận nghịch khi và chỉ khi 3.2 Mọi nửa nhóm số với chiều nhúng 2 là đối xứng ai + an−1−i = an−1 với mọi i ∈ {0, . . . , n − 1}. Sử dụng Định lý 3.1.6 và Định lý 2.2.1, ta nhận được kết quả cơ bản (đã biết) sau. 30 Định lý 3.2.1. Mọi nửa nhóm số với chiều nhúng 2 là đối xứng. Chứng minh. Giả sử S là nửa nhóm số với chiều nhúng 2. Khi đó S = S(p, q) với p, q là hai số nguyên dương nguyên tố cùng nhau nào đó. Khi là đa thức bậc (p − 1)(q − 1). Ta có đó PS(p,q) = (xpq − 1)(x − 1)
(xp − 1)(xq − 1) x(p−1)(q−1)PS(p,q)( 1
x ) = xpq+1−p−q (x−pq − 1)(x−1 − 1)
(x−p − 1)(x−q − 1) = (1 − xpq)(1 − x)
(1 − xp)(1 − xq ) = PS(p,q)(x). Như vậy PS(p,q) là tự thuận nghịch và do vậy S(p, q) là đối xứng. Định lý 2.1.5 cùng với Định lý 2.2.1 chỉ ra rằng nếu e(S) = 2 thì PS (x) có thể được viết như một tích của những đa thức chia đường tròn. Điều này dẫn tới bài toán sau đây. Bài toán. Đặc trưng hóa nửa nhóm số S mà ở đó PS (x) có thể được biểu diễn như tích của những đa thức chia đường tròn. Một nửa nhóm số S mà PS(x) là tích của các những đa thức chia đường tròn được gọi là nửa nhóm số chia đường tròn, theo [2]. Vì x − 1 luôn không là ước của PS(x) và vì các đa thức chia đường tròn Φn(x) với n ≥ 2 là tự thuận nghịch, ta suy ra rằng nếu S là chia đường tròn thì PS(x) là tự thuận nghịch, do vậy S là đối xứng. Tuy nhiên chiều ngược lại nói chung không đúng, tức là có những nửa nhóm đối xứng S mà S không là chia đường tròn. Trong [2], các tác giả chỉ ra rằng nếu S là đối xứng với 3.3 Phân bố gián đoạn và độ gián đoạn e(S) = 3 thì ta cũng có S là chia đường tròn. Cho đa thức f = c1xe1 + · · · + csxes, với những hệ số ci là khác 0 và e1 < e2 < ... < es. Khi đó khoảng trống lớn nhất của f được kí hiệu bởi 31 g(f ), được định nghĩa là (ei+1 − ei) , g (f ) = 0 g(f ) = max
1≤i khi s = 1. Chẳng hạn với f (x) = PS(2,7)(x) = 1 − x + x2 − x3 + x4 − x5 + x6 và
g(f ) = 1. Trong mục này ta sẽ đi chứng minh kết quả sau của Hong-Lee- Lee-Park [3]. Định lý. Nếu p và q là những số nguyên tố cố định với 2 < p < q, khi đó g (Φpq) = p − 1. Thực tế ta sẽ chứng minh kết quả tổng quát hơn kết quả trên, xem Hệ quả 3.3.8. Cho S là một nửa nhóm số. Những số nguyên không âm không nằm trong S được gọi là những khoảng trống của S. Số những khoảng trống của S được gọi là giống của S và kí hiệu bởi N (S). Tập hợp gồm những khoảng trống được kí hiệu là G(S). Ví dụ, ta xét S = S(4, 7) = {0, 4, 7, 8, 11, 12, 14, 15, 16, 18, →}. Khi đó tập những khoảng trống của S(4, 7) G(S(4, 7)) = {1, 2, 3, 5, 6, 9, 10, 13, 17}, và giống của S(4, 7) là N (S(4, 7)) = 9. Ta có kết quả sau. Định lý 3.3.1. Cho S là một nửa nhóm số. Khi đó ta có 2N (S) ≥ F (S)+1 với đẳng thức xảy ra nếu và chỉ nếu S là đối xứng. Chứng minh. Chứng minh của Định lý 3.1.6 chỉ ra rằng 2# {0 ≤ j ≤ F (S) : j ∈ S} ≤ F (S) + 1, và đẳng thức xảy ra nếu và chỉ nếu S là đối xứng. Mặt khác, từ định nghĩa của N (S) ta suy ra # {0 ≤ j ≤ F (S) : j ∈ S} = F (S) + 1 − N (S) . 32 Do vậy, ta có 2(F (S) + 1 − N (S)) ≤ F (S) + 1 với dấu bằng xẩy ra nếu và chỉ nếu S là đối xứng. Từ đó ta suy ra 2N (S) ≥ F (S) + 1 với dấu bằng xảy ra khi và chỉ khi S là đối xứng. Hệ quả 3.3.2 (Sylvester). Cho p, q > 1 là hai số nguyên dương nguyên tố cùng nhau. Khi đó N (S (p, q)) = (p − 1)(q − 1)
2 Chứng minh. Theo Định lý 2.2.1, S(p, q) là nửa nhóm đối xứng. Do vậy N (S) = = . F (S) + 1
2 (p − 1)(q − 1)
2 3.3.1 Độ gián đoạn cực đại trong đa thức chia đường tròn nhị phân Cho S là một nửa nhóm số. Định nghĩa 3.3.3. Một tập B = {a + 1, a + 2, . . . , a + t} của t số nguyên liên tiếp được gọi là một khối khoảng trống nếu nó thỏa mãn hai điều kiện: (a) B ∩ S = ∅, (b) a ∈ S và a + t + 1 ∈ S. Độ dài của một khối khoảng trống dài nhất của S được ký hiệu là g(G(S)). Định nghĩa 3.3.4. Một tập E = {a + 1, a + 2, . . . , a + t} của t số nguyên liên tiếp được gọi là một khối phần tử nếu nó thỏa mãn hai điều kiện: (a) E ⊆ S, (b) a (cid:54)∈ S và a + t + 1 (cid:54)∈ S. 33 Độ dài của khối phần tử dài nhất của S được ký hiệu là g(S). Ví dụ 3.3.5. Xét S = S(4, 7) = {0, 4, 7, 8, 11, 12, 14, 15, 16, 18, →}. Khi đó các khối khoảng trống của S(4, 7) là {1, 2, 3}, {5, 6}, {9, 10}, {13}, {17}. Các khối phần tử của S(4, 7) là {0}, {4}, {7, 8}, {11, 12}, {14, 15, 16}. Ta có g(G(S)) = 3 và g(S) = 3. Chú ý rằng trong ví dụ này ta có PS(4,7)(x) = 1 − x + x4 − x5 + x7 − x9 + x11 − x13 + x14 − x17 + x18, và g(PS(4,7)(x)) = 3. Nhắc lại rằng bội m(S) của nửa nhóm số S là số nguyên dương nhỏ nhất thuộc S. Bổ đề 3.3.6. Cho S là một nửa nhóm số. Ta có các khẳng định sau. 1. g(G(S)) = m(S) − 1. 2. g(S) ≤ m(S) − 1. 3. Nếu S là đối xứng thì g(S) = m(S) − 1. Chứng minh. (1) Ta viết các phần tử của S theo thứ tự tăng dần: S = {0 = s0, s1 = m(S), s2, s3, . . .}, 0 = s0 < s1 = m(S) < s2 < s3 < · · · Vì s0 = 0 và s1 = m(S), nên ta có g(G(S)) ≥ m(S) − 1. Bây giờ ta giả sử g(G(S)) ≥ m(S). Khi đó tồn tại một khối khoảng trống E với độ dài lớn hơn hoặc bằng m(S). Vì độ dài của E lớn hơn hoặc bằng m(S), nên E phải chứa một bội km(S) của m(S). Nhưng vì mọi bội của m(S) đều nằm trong S nên ta suy ra E chứa một phần tử trong S, mâu thuẫn. 34 Như vậy ta có g(G(S)) = m(S) − 1. (2) Giả sử phản chứng rằng g(S) ≥ m(S). Khi đó ta tìm được dãy gồm m(S) phần tử liên tiếp đều thuộc S: k, k + 1, . . . , k + m(S) − 1 sao cho k + m(S) (cid:54)∈ S. Nhưng điều này rõ ràng là mâu thuẫn vì k và m(S) đều thuộc S. (3) Ta giả sử S là một nửa nhóm đối xứng. Từ chứng minh của Định lý 3.1.6, ta có {0, 1, . . . , F (S)} = {j | 0 ≤ j ≤ F (S), j ∈ S}(cid:116){F (S)−j | 0 ≤ j ≤ F (S), j ∈ S}. Từ đó ta suy ra rằng nếu E là một khối các phần tử của S thì F (S) − E = {F (S) − j | j ∈ E} là một khối khoảng trống của S. Ngược lại, nếu B là một khối các khoảng trống thì F (S) − B là một khối các phần tử của S. Do vậy g(S) = g(G(S)) = m(S) − 1. Định lý 3.3.7. Cho S là một nửa nhóm số. Khi đó g(PS(x)) = m(S) − 1. Chứng minh. Ta có s(cid:54)∈S 0≤s (cid:88) (cid:88) xs = 1 + (x − 1) xs. PS(x) = xF (S)+1 + (1 − x) Giả sử E = {a + 1, a + 2, . . . , a + t} là một khối phần tử của S. Khi đó ta có s∈E (cid:88) (1 − x) xs = xa+1 − xa+t+1. Nếu E1 = {a1 + 1, . . . , a1 + t1 và E2 = {a2 + 1, . . . , a2 + t2} là hai khối phần tử liền nhau của S, tức là tập {a1 + t1 + 1, . . . , a2} là một khối khoảng trống với độ dài (a2 + 1) − (a1 + t1 + 1), thì ta có s∈E1(cid:116)E2 (cid:88) (1 − x) xs = xa1+1 − xa1+t1+1 + xa2+1 − xa2+t2+1. 35 Từ đó ta suy ra g(PS(x)) = max{g(S), g(G(s))}. Theo Bổ đề 3.3.6, ta có max{g(S), g(G(s))} = m(S) − 1. Do vậy g(PS(x)) = m(S) − 1. Hệ quả 3.3.8. Cho 1 < p < q là số nguyên dương nguyên tố cùng nhau. Khi đó g(P{p,q}(x)) = p − 1. Chứng minh. Ta có m(S(p, q)) = p − 1. Do vậy theo Định lý 3.3.7 ta có g(P{p,q}(x)) = m(S(p, q)) = p − 1. Nói riêng, ta thu được kết quả sau của Hong-Lee-Lee-Park [3]. Định lý 3.3.9 ([3]). Nếu p và q là hai số nguyên tố với 2 < p < q thì g(Φpq) = p − 1. Chứng minh. Ta chỉ cần chú ý rằng khi p và q là nguyên tố thì Q{p,q} = Φpq. 3.3.2 Tổng Sylvester và số Bernoulli Thông tin bổ sung về những khoảng trống được cho bởi tổng Sylvester: s /∈S(p,q) (cid:88) sk. σk (p, q) := . Ta sẽ đi tìm công thức Theo Hệ quả trên, ta có σ0 (p, q) = (p − 1) (q − 1)
2 xác định σk(p, q). Ta sẽ cần những số Bernoulli Bn. ∞
(cid:88) Số Bernoulli Bn có thể được định nghĩa bởi n=0 = , |z| < 2π. Bn z
ez − 1 zn
n! Một số giá trị của số Bernoulli là B0 = 1, B1 = , B2 = , B3 = 0, B4 = −1
2 1
6 −1
30 và Bn = 0 với mọi n lẻ n ≥ 3. Quan hệ truy hồi cơ bản nhất trong các số Bernoulli là với n ≥ 1, ta có n
(cid:88) (cid:19) j=0 Bj = 0. (cid:18)n + 1
j 36 k=0 kj. Ta có, Số Bernoulli xuất hiện lần đầu trong khi nghiên cứu tổng lũy thừa Sj (n) :=
(cid:80)n−1 j
(cid:88) (cid:19) i=0 Sj(n) = Binj+1−i. 1
j + 1 (cid:18)j + 1
i Bây giờ ta quay lại việc tìm công thức cho σk(p, q). Từ Định lý 2.2.1 ta suy ra j /∈S(p,q) (cid:88) = = − . xj = PS(p,q)(x) − 1
x − 1 Q{p,q}(x) − 1
x − 1 xpq − 1
(xp − 1)(xq − 1) 1
x − 1 k≥0 Bằng cách thay x = ez và sử dụng khai triển Taylor ez = (cid:80) , ta zk
k! nhận được đẳng thức k≥0 j /∈S(p,q)
j /∈S(p,q)
(cid:88) (cid:88) (cid:88) − = ejz = epqz − 1
(epz − 1)(eqz − 1) 1
ez − 1 (jz)k
k! k≥0
∞
(cid:88) (cid:88) (cid:88) jk = zk
k! j /∈S(p,q)
zk
k! k=0 = . σk(p, q) ∞
(cid:88) ∞
(cid:88) ∞
(cid:88) Nhân cả hai vế đẳng thức trên với z và sử dụng khai triển Taylor, ta được m=1 k=0 = = mσm−1(p, q) σm−1(p, q) σk(p, q) zm
m! zm
(m − 1)! zk+1
k! m=1
pz
epz − 1
∞
(cid:88) = − · · z
ez − 1 ∞
(cid:88) m=0 i=0 j=0 k=0 qz
eqz − 1
∞
(cid:88) epqz − 1
pqz
∞
(cid:88) = − . Bm Bipi zi
i! Bjqj zj
j! (pqz)k
(k + 1)! zm
m! Đồng nhất hệ số của zm ta nhận được kết quả sau đây. Định lý 3.3.10. Với m ≥ 1 ta có m−i
(cid:88) m
(cid:88) (cid:18) (cid:19) i=0 j=0 BiBjpm−jqm−i − Bm. mσm−1(p, q) = m + 1
i, j, m + 1 − i − j 1
m + 1 37 Sử dụng công thức này ta có thể tìm được (p − 1)(q − 1)(2pq − p − q − 1), σ1 (p, q) = 1
12 và (p − 1)(q − 1)pq(pq − p − q). σ2 (p, q) = 1
12 Từ định lý trên ta suy ra đẳng thức m
(cid:88) (cid:19) r=0 mσm−1(p, q) = pm−r−1Bm−rqrSr(p) − Bm. (cid:18)m
r Đẳng thức cho ta công thức truy hồi sau cho Bm: m−1
(cid:88) (cid:19)r r=0 Bm = BrSm−r(p). σm−1(p, q) + (cid:18)m
r m
pm − 1 qm
p(1 − pm) (cid:19) (cid:18)p
q Chẳng hạn, bằng cách lấy p = 4 và p = 7, ta nhận được công thức truy hồi sau của Bm: (cid:0)1 + 2m−1 + 3m−1 + 5m−1 + 6m−1 + 9m−1 + 10m−1 + 13m−1 + 17m−1(cid:1) Bm = m
4m − 1 m−1
(cid:88) r=0 (cid:19)r m + (cid:0)1 + 2m−r + 3m−r(cid:1) Br. 7m
4 (1 − 4m) (cid:18)4
7 r Những số tự nhiên 1, 2, 3, 5, 6, 9, 10, 13 và 17 là những số không nằm trong nửa nhóm số S(4, 7). 38 Trong luận văn này, chúng tôi đã trình bày các nội dung sau đây về nửa nhóm số và đa thức chia đường tròn. • Trình bày định nghĩa nửa nhóm số và một số bất biến liên kết với nửa nhóm số. • Trình bày về mối liên hệ giữa nửa nhóm số chiều nhúng 2 và đa thức bù trừ nhị phân (một tổng quát hóa của đa thức chia đường tròn nhị phân). • Trình bày một số ứng dụng của mối liên hệ trên trong việc chứng minh tính đối xứng của nửa nhóm số với chiều nhúng 2 và trong nghiên cứu khoảng trống lớn nhất của đa thức chia đường tròn nhị phân. 39 [1] G. Bachman (2010), "On ternary inclusion-exclusion polynomials", Integers, 10, pp. 623–638. [2] E.-A. Ciolan, P. A. García-Sánchez and P. Moree (2016), "Cyclo- tomic Numerical Semigroups", SIAM J. Discrete Math, 30(2), pp. 650-668. [3] H. Hong, E. Lee, H.-S. Lee, and C.-M. Park (2012), "Maximum gap in (inverse) cyclotomic polynomial", J. Number Theory, 132 (10), pp. 2297-2315. [4] P. Moree (2004), "Numerical semigroups, cyclotomic polynomials, and Bernoulli numbers", Amer. Math. Monthly, 121(10), pp. 890- 902. [5] J. L. Ramírez Alfonsín (2005), The Diophatine Frobenius Problem, Oxford Lecture Series in Mathematics and Its Applications, 30, Oxford Univ. Press, Oxford. [6] J. C. Rosales and P. A. García-Sánchez (2009), Numerical semi- groups, Development in Mathematies, 20, Springer New York.Chương 3
Một vài ứng dụng
Kết luận
Tài liệu tham khảo
