Luận văn Thạc sĩ Toán học: Về định lý Van Der Waerden, số Ramsey và tập đơn sắc

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

Thêm vào BST

Báo xấu

13
lượt xem 2
download

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

Mục đích của luận văn là tìm hiểu và trình bày một số vấn đề của lý thuyết số tổ hợp. Cụ thể, luận văn trình bày về Định lý Van der Waerden về sự tồn tại một cấp số cộng đơn sắc trong một tập số tự nhiên liên tiếp được tô màu, về Định lý Szemerédi về mật độ cấp số cộng trong tập hợp các số tự nhiên liên tiếp, về khái niệm hệ phủ đồng dư và ứng dụng trong giải toán, về số Ramsey và tập đơn sắc trong bài toán tô màu.

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: Về định lý Van Der Waerden, số Ramsey và tập đơn sắc

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC --------------------------- NGUYỄN XUÂN VINH VỀ ĐỊNH LÝ VAN DER WAERDEN, SỐ RAMSEY VÀ TẬP ĐƠN SẮC LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2018
ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC --------------------------- NGUYỄN XUÂN VINH VỀ ĐỊNH LÝ VAN DER WAERDEN, SỐ RAMSEY VÀ TẬP ĐƠN SẮC Chuyên ngành: Phƣơng pháp Toán sơ cấp Mã số: 8460113 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC GS.TSKH. Hà Huy Khoái THÁI NGUYÊN - 2018
1 Mục lục Mở đầu 2 1 Tổng quan về lý thuyết số tổ hợp 4 1.1. Định lý Van der Waerden và Định lý Szemerédi . . . . . . 4 1.1.1. Định lý Van der Waerden 1927 . . . . . . . . . . 4 1.1.2. Số Van der Waerden . . . . . . . . . . . . . . . . . 8 1.1.3. Định lý Szemerédi . . . . . . . . . . . . . . . . . . 9 1.2. Hệ phủ đồng dư . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2.1. Định nghĩa . . . . . . . . . . . . . . . . . . . . . . 10 1.2.2. Giả thuyết Selfridge và Schinzel và một số bài toán 13 2 Số Ramsey và tập đơn sắc 16 2.1. Số Ramsey . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.1. Định nghĩa . . . . . . . . . . . . . . . . . . . . . . 16 2.1.2. Tính chất số Ramsey . . . . . . . . . . . . . . . . . 17 2.1.3. Tiệm cận số Ramsey . . . . . . . . . . . . . . . . . 18 2.1.4. Số Ramsey cho trường hợp tổng quát . . . . . . . . 22 2.2. Tập đơn sắc . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.2.1. Định nghĩa . . . . . . . . . . . . . . . . . . . . . . 27 2.2.2. Tập đơn sắc và các vấn đề liên quan . . . . . . . . 28 Kết luận 34 Tài liệu tham khảo 35
2 Mở đầu Lý thuyết số tổ hợp là một trong những chủ đề được nhiều người quan tâm nghiên cứu trong lý thuyết số. Các kết quả của lý thuyết số tổ hợp có nhiều ứng dụng trong nghiên cứu các bộ môn khoa học khác cũng như ứng dụng vào trong các vấn đề thực tế. Ngoài ra, nhiều vấn đề của lý thuyết số tổ hợp còn được đề cập đến trong các đề thi học sinh giỏi toán. Mục đích của luận văn là tìm hiểu và trình bày một số vấn đề của lý thuyết số tổ hợp. Cụ thể, luận văn trình bày về Định lý Van der Waerden về sự tồn tại một cấp số cộng đơn sắc trong một tập số tự nhiên liên tiếp được tô màu, về Định lý Szemerédi về mật độ cấp số cộng trong tập hợp các số tự nhiên liên tiếp, về khái niệm hệ phủ đồng dư và ứng dụng trong giải toán, về số Ramsey và tập đơn sắc trong bài toán tô màu. Ngoài phần kết luận, mở đầu và tài liệu tham khảo nội dung chính của luận văn trình bày thành 2 chương: Chương 1: Tổng quan về lý thuyết số tổ hợp. Mục đích của chương này là trình bày về Định lý Van der Waerden, Định lý Szemerédi, nêu ra một vài giá trị đã biết về số Van der Waerden và một số vấn đề liên quan tới hệ phủ đồng dư. Chương 2: Số Ramsey và tập đơn sắc. Mục đích của chương này là trình bày khái niệm về số Ramsey và một số kết quả về số Ramsey, tập đơn sắc và một số vấn đề liên quan tới tập đơn sắc trong bài toán tô màu. Luận văn được hoàn thành với sự hướng dẫn, chỉ bảo tận tình của GS.TSKH. Hà Huy Khoái và sự đóng góp ý kiến sát sao của các thầy, cô trường Đại học Khoa học - Đại học Thái nguyên. Qua luận văn này em xin được bày tỏ lòng biết ơn đến sự hướng dẫn tận tình của thầy hướng dẫn và các thầy, cô trường Đại học Khoa học - Đại học thái nguyên đã góp ý sâu sắc, tạo điều kiện thuận lợi để em hoàn thành luận văn nay.
3 Tôn xin trân trọng cám ơn đến Sở Giáo dục và Đào tạo Bắc Ninh, tập thể sư phạm trường THPT Lý Thường Kiệt đã tạo điều kiện cho tôi hoàn thành khóa học.
4 Chương 1 Tổng quan về lý thuyết số tổ hợp Trong Chương 1, luận văn trình bày hai định lý, gồm Định lý Van der Waerden và Định lý Szemerédi, một vài giá trị đã biết về số Van der Waerden và các khái niệm cơ bản về hệ phủ đồng dư. Tài liệu tham khảo chính của chương này là các tài liệu [1], [4]. 1.1. Định lý Van der Waerden và Định lý Szemerédi Định lý Van der Waerden và Định lý Szemerédi là hai định lý quan trọng trong lý thuyết số nghiên cứu về cấp số cộng và mật độ của cấp số, đồng thời hai định lý này cũng là tiền đề để tìm hiểu và phát triển các kết quả mới về cấp số cộng. Nhắc lại rằng cấp số cộng là một dãy số (hữu hạn hoặc vô hạn) mà trong đó, kể từ số hạng thứ hai trở đi, mỗi số hạng đều bằng tổng của số hạng đứng ngay trước nó với một số d không đổi. Ta có thể biểu diễn cấp số cộng dưới dạng như sau: a, a + d, a + 2d, . . . , a + (m − 1)d, ..., trong đó: m là số nguyên dương bất kỳ, a, d ∈ R, a được gọi là số hạng đầu tiên và d gọi là công sai của cấp số cộng. Với mọi n là số tự nhiên, ta kí hiệu [n] = {1, 2, . . . ., n} là tập hợp các số tự nhiên từ 1 đến n. Cho một tập hợp X và t ∈ N, khi đó X(t) = {A ⊂ X, |A| = t} , tức là X(t) là tập hợp gồm các tập con của X có lực lượng t. 1.1.1. Định lý Van der Waerden 1927 Định lý Van der Waerden phát biểu rằng: Với hai số nguyên dương m, k cho trước tồn tại một số nguyên N = N (m, k) sao cho với mọi
5 n ≥ N nếu [n] được tô bởi k màu thì luôn tồn tại một cấp số cộng đơn sắc độ dài m trong [n]. Giả sử Định lý Van der Waerden được chứng minh. Do tập [n] được tô bởi k màu nên ta có thể chia tập [n] thành k tập con được xác định bởi k màu riêng biệt. Theo Định lý Van der Waerden thì khi đó sẽ tồn tại một tập con trong k tập con trên mà trong đó tồn tại một cấp số cộng độ dài m. Ta có thể phát biểu lại Định lý Van der Waerden dưới dạng sau: Định lý 1.1 Đối với mọi cặp số tự nhiên k, l luôn tồn tại số tự nhiên n(k, l) sao cho nếu một đoạn bất kỳ của dãy số tự nhiên có độ dài n(k, l) được phân hoạch theo cách tuỳ ý thành k lớp, thì sẽ có ít nhất một lớp trong k lớp đó chứa một cấp số cộng độ dài l. Để chứng minh Định lý Van der Waerden, ta sẽ chứng minh một định lý tổng quát hơn: Định lý 1.2 Cho trước dãy vô hạn số tự nhiên: t1 , t2 , ..., tq , ... (1.1) Đối với mỗi cặp số tự nhiên k, l luôn tồn tại một số tự nhiên n(k, l) sao cho nếu một đoạn bất kỳ của dãy số tự nhiên có dộ dài n(k, l) được phân hoạch theo cách tuỳ ý thành k lớp, thì sẽ có ít nhất một lớp mà trong đó tồn tại dãy số c1 , c2 , ..., cl thỏa mãn diều kiện sau: (c2 − c1 ) : (c3 − c2 ) : ... : (cl − cl−1 ) = t1 : t2 : ... : tl−1 . Nói một cách ngắn gọn, l số đó lập nên một cấp số cộng tổng quát độ dài l được tạo ra bởi dãy số (1.1). Định lý Van der Waerden là trường hợp riêng của Định lý 1.2 trong trường hợp t1 = t2 = · · · = tq = · · · = 1. Chứng minh Định lý 1.2. Đặt số hạng đầu tiên của dãy (1.1) bằng đơn vị: t1 . Dễ thấy rằng Định lý 1.2 là hiển nhiên với l = 2 và với mọi k (bởi vì số n(k, l) có thể nhận giá trị k + 1), tức là tồn tại một cấp số cộng trong dãy có độ dài là 2, điều này luôn đúng. Giả sử định lý đúng với mọi số l ≥ 2 và k bất kỳ. Đặt: q0 = 1, n0 = n(k, l), qs = (1 + t1 )ns−1 qs−1 , ns = n(k qs , l) > 0. (1.2)
6 Ta sẽ chứng minh định lý đúng với l + 1, tức là số n(k, l + 1) có thể lấy bằng qk . Giả sử đoạn 4 của dãy số tự nhiện có độ dài qk được phân hoạch thành k lớp. Hai số a và b của đoạn 4 được gọi là cùng loại nếu chúng cùng nằm trong một lớp và được viết là a ∼ b. Hai đoạn 40 (a, a + 1, ..., a + r) và 400 (a, a0 + 1, ..., a0 + r) có độ dài bằng nhau và cùng nằm trong đoạn 4 sẽ được gọi là cùng loại và được viết 40 ∼ 400 , nếu a + j ∼ a0 + j, j = 0, 1, ..., r. Rõ ràng đối với các đoạn có độ dài m, thì số các loại khác nhau có thể sẽ bằng k m . Vì qk = (1 + tl )nk−1 qk−1 nên đoạn 4 có thể được xem như gồm hai phần không bằng nhau: Phần bên trái là một dãy gồm nk−1 đoạn có độ dài qk−1 , còn phần bên phải là một dãy gồm tl nk−1 đoạn có độ dài qk−1 . Ta sẽ nói rằng các đoạn có độ dài bằng nhau tạo nên một cấp số cộng tổng quát nếu cấp số đó được lập nên bởi các số đầu tiên của chúng. Do định nghĩa của số nk−1 nên ta có thể khẳng định được rằng: Phần bên trái của đoạn 4 chứa một cấp số cộng tổng quát từ l đoạn cùng loại với nhau 41 , 42 , ..., 4l và cùng có độ dài là qk−1 . Ký hiệu các khoảng cách giữa các đầu mút bên trái của hai đoạn kề nhau (tức là hiệu giữa hai số đầu tiên của hai đoạn kề nhau) là: d1 , d1 t2 , ..., d1 tl−1 . Đối với cấp số cộng tổng quát, từ các đoạn cùng loại đó ta gắn thêm vào nó phần tử thứ l + 1 là 4l+1 , phần tử ấy có thể không cùng loại với các phần tử đứng trước và nó có thể vượt quá phần tử đầu tiên của đoạn 4, nhưng vẫn nằm trong đoạn 4. Bây giờ ta lấy một phần tử 4i1 bất kỳ từ l phần tử của cấp số cộng tổng quát, đó là đoạn có độ dài qk−1 . Ta sẽ tiến hành trên đoạn đó tương tự như đã tiến hành với đoạn 4 (tức là coi đoạn 4 như là dãy (1 + tl )nk−1 đoạn có độ dài qk−1 ). Do định nghĩa của số nk−1 , ta có thể khẳng định rằng, phần bên trái của đoạn 4i1 bao gồm nk−1 đoạn có độ dài qk−2 chứa cấp số cộng tổng quát từ l đoạn cùng loại 4i2 i2 (1 ≤ i2 ≤ l) có cùng độ dài qk−1 . Ta ký hiệu các khoảng cách giữa các đầu mút trái của hai đoạn kề nhau 4i2 i2 là: d2 , d2 t2 , ..., d2 tl−1 . Một lần nữa, ta lại nối thêm vào cấp số cộng tổng quát này phần tử thứ l + 1 và rõ ràng phần tử ấy cũng vẫn nằm trong đoạn 4i1 . Việc xây dựng như vậy được tiến hành với tất cả các đoạn 4i1 (1 ≤ i1 ≤ l + 1) và trong tất cả các đoạn đó ta sẽ lấy các đoạn 4i2 i2 (1 ≤ i2 ≤ l + 1) theo vị trí tương ứng. Bởi vì tất cả là cùng loại nên rõ ràng mọi 4i2 i2 sẽ là cùng loại, nếu 1 ≤ i1 ≤ l, 1 ≤ i2 ≤ l. Quá trình xây dựng được tiếp tục k lần. Kết quả sau lần cuối cùng ta
7 sẽ nhận được các đoạn có độ dài q0 = 1, tức là một đoạn đơn giản 4 mà một cách tổng quát ta có thể ký hiệu là 4i1 i2 ...ik (1 ≤ i1 , i2 , ..., ik ≤ l+1). Như vậy ta dễ thấy rằng, với 1 ≤ s ≤ k, 1 ≤ ir ≤ l, 1 ≤ i0r ≤ l(1 ≤ r ≤ s) thì 4i1 i2 ...is ∼ 4i01 i02 ...i0s . (1.3) Hai nhận xét sau đây là rất quan trọng đối với phần còn lại trong chứng minh định lý. 1) Giả sử: 1 ≤ s ≤ k, 1 ≤ ir ≤ l, 1 ≤ i0r ≤ l(1 ≤ r ≤ s), 1 ≤ im ≤ l + 1 (s + 1 ≤ m ≤ k). Khi đó 4i1 i2 ...is is+1 ...ik ∼ 4i01 i02 ...i0s i0s+1 ...ik . (1.4) Thật vậy, do hai số đó đứng ở các vị trí giống nhau trong các đoạn cùng loại 4i1 i2 ...is và 4i01 i02 ...i0s . 2) Với số s ≤ k, is ≤ l, i0s = is + 1, các đoạn 4i1 ...is−1 is và 4i1 ...is−1 i0s là các đoạn kề nhau ở bước xây dựng thứ s của chúng ta, nên đối với mọi chỉ số is+1 , ...ik , các số 4i1 i2...s−1 is is+1 ...ik và 4i1 i2...s−1 i0s is+1 ...ik sẽ chiếm các vị trí giống nhau trong hai đoạn kề nhau, sao cho: 4i1 i2...s−1 i0s is+1 ...ik − 4i1 i2...s−1 is is+1 ...ik = ds tis . (1.5) Để ngắn gọn, ta đặt l0 = l + 1. Xét k + l số ar = 41 · · · 1 l0 · · · l0 , r = 0, 1, ..., k. (1.6) | {z } | {z } r k−r Trong các số đó, ta luôn tìm được hai số ar và as cùng nằm trong một lớp 41 · · · 1 l0 · · · l0 ∼ 41 · · · 1 l0 · · · l0 . (1.7) | {z } | {z } | {z } | {z } r k−r s k−s Xét các số ar = 41 · · · 1 i · · · i l0 · · · l0 (1 ≤ i ≤ l0 ). (1.8) | {z } | {z } | {z } r s−r k−s Ta sẽ chứng minh rằng chúng cùng nằm trong một lớp, và tạo thành một cấp số cộng tổng quát. Thật vậy, các số cl0 và c1 cùng loại do (1.7), còn tất cả các ci (i < l0 ) là cùng loại do (1.4). Vì vậy tất cả các số ci (1 ≤ i ≤ l0 ) cùng nằm trong một lớp. Phần còn lại, ta cần phải chỉ ra rằng các số đó lập thành một cấp số cộng, tức là: (c2 − c1 ) : (c3 − c2 ) : · · · : (cl0 − cl ) = 1 : t2 : · · · : tl0 . (1.9)
8 Để ngắn gọn, ta đặt i0 = i + 1. Ta đưa vào xét các số sau: ci,m = 41 · · · 1 i0 · · · i0 i · · · i l0 · · · l0 (0 ≤ m ≤ s − r). | {z } | {z } | {z } | {z } s m s−r−m k−s s−r P Khi đó ci+1 − ci = (ci,m − ci,m−1 ) bởi vì ci,0 = ci và ci,s−r = ci+1 . m=1 Nhưng do (1.5) ta có ci,m −ci,m−1 = 41 · · · 1 i0 · · · i0 i · · · i l0 · · · l0 −41 · · · 1 i0 · · · i0 i · · · i l0 · · · l0 = | {z } | {z } | {z } | {z } | {z } | {z } | {z } | {z } r m s−r−m k−s r m−1 s−r−m+1 k−s s−r P dr+m ti , có nghĩa là: ci+1 − ci = dr+m ti . m=1 s−r P Nhưng do dr+m không phụ thuộc vào i, và do đó điều kiện (1.9) m=1 được thỏa mãn. Do đó định lý được chứng minh với giả thiết rằng, phần tử đầu tiên của dãy số (1.1) bằng đơn vị (tức là bằng 1). Nếu t1 khác đơn vị, thì ta xét dãy số sau đây: 1, t1 , · · · , tq , · · · . (1.10) Khi đó l + 1 số ci (i = 1, 2, · · · , l + 1) lập thành một cấp số cộng tổng quát độ dài l + 1, được tạo ra bởi dãy số (1.10) cùng nằm trong một lớp, vì thế đương nhiên nó chứa l số lập thành cấp số cộng tổng quát độ dài l, được tạo ra bởi dãy số (1.1) và cùng nằm trong một lớp. Do đó định lý được chứng minh. 1.1.2. Số Van der Waerden Định nghĩa 1.1 Số tự nhiên nhỏ nhất N = N (m, k) thỏa mãn Định lý Van der Waerden được gọi là số Van der Waerden, và kí hiệu là w(m, k). Một số giá trị chính xác của w(m, k) đã được chỉ ra. Ta có w(m, 1) = m và w(2, k) = k + 1. Với các giá trị khác của k và m, chúng ta đã biết w(3, 2) = 9, w(4, 2) = 35, w(5, 2) = 178, w(6, 2) = 1132, w(3, 3) = 27 và w(4, 3) = 76. Sau đây ta kiểm tra lại, chẳng hạn hai kết quả w(m, 1) = m và w(2, k) = k + 1. Thật vậy: +) w(m, 1) = m, khi đó tất cả các phần tử của [n] được tô bằng 1 màu. Như vậy, nếu đặt N = m thì với mọi n ≥ N, trong [n] tồn tại cấp
9 số cộng độ dài m (chính là m số liên tiếp). Khi n < m thì hiển nhiên không thể tồn tại cấp số cộng độ dài m trong [n]. Vậy N (m, 1) = m chính là số nhỏ nhất cần tìm, tức là w(m, 1) = m. +) w(2, k) = k + 1, khẳng định này tương đương với việc khi tô tập hợp [n] với n ≥ k + 1 bởi k màu, thì trong k + 1 phần tử tuỳ ý, phải tồn tại cấp số cộng hai số hạng cùng màu. Nhưng điều này là hiển nhiên, vì trong k + 1 số, có ít nhất hai số cùng màu, và dĩ nhiên chúng lập thành cấp số cộng 2 số hạng. Nếu chỉ lấy k số thì có thể xẩy ra trường hợp k số đó được tô bởi k màu khác nhau. Vậy số nhỏ nhất thoả mãn là k + 1, tức là w(2, k) = k + 1. 1.1.3. Định lý Szemerédi Trong lý thuyết số, Định lý Szemerédi là một kết quả mà trước đó mang tên "giả thuyết Erd˝os–Turán". Năm 1936 Erd˝os và Turán đưa ra giả thuyết rằng: “Với mọi giá trị d, gọi là mật độ, thỏa mãn 0 < d < 1 và số nguyên k, tồn tại số nguyên N = N (d, k) sao cho mọi tập hợp con A của 1, ..., N với lực lượng lớn hơn hoặc bằng dN đều chứa một cấp số cộng độ dài k. Đây là một tổng quát hóa của Định lý Van der Waerden. Trường hợp k = 1 và k = 2 là tầm thường. Trường hợp k = 3 được chứng minh năm 1956 bởi Klaus Roth bằng phương pháp đường tròn Hardy–Littlewood. Trường hợp k = 4 được chứng minh năm 1969 bởi Endre Szemerédi bằng phương pháp tổ hợp. Bằng phương pháp tương tự như cho trường hợp k = 3, Roth đưa ra một chứng minh khác cho kết quả này năm 1972. Cuối cùng trường hợp tổng quát cho mọi k được chứng minh năm 1975, bằng một mở rộng phức tạp của chứng minh tổ hợp trước đó cũng bởi Szemerédi (đây là "một kiệt tác của lập luận tổ hợp", như đánh giá của R. L. Graham). Định lý 1.3 (Định lý Szemerédi) Mọi dãy số nguyên mật độ dương đều chứa cấp số cộng độ dài tuỳ ý. Ngày nay nhiều chứng minh khác của kết quả này đã được tìm ra, một vài chứng minh quan trọng trong số đó là của Hillel F¨ urstenberg năm 1977 bằng lý thuyết Ergodic và bởi Timothy Gowers năm 2001 bằng giải tích Fourier và toán học tổ hợp.
10 1 Giả sử k là một số nguyên dương và 0 < δ ≤ . Một phiên bản 2 hữu hạn của định lý khẳng định rằng, tồn tại số nguyên N = N (k, δ) sao cho mọi tập hợp con của {1, 2, ..., N } với kích thước δN đều chứa một cấp số cộng độ dài k. Chặn chặt nhất đến nay cho N (k, δ) là k+9 −22 log(1/δ)k−1 2δ C ≤ N (k, δ) ≤ 2 . Với C > 1, chặn dưới là của Behrend (cho k = 3) và Rankin, chặn trên là của Gowers. Trong trường hợp đặc −2 biệt k = 3 chặn trên chặt nhất đến nay là N (3, δ) ≤ C δ log(1/δ) . 1.2. Hệ phủ đồng dư 1.2.1. Định nghĩa Hệ phủ đồng dư hay tập phủ đồng dư là một tập hữu hạn (a1 , n1 ), (a2 , n2 ), · · · , (ar , nr ), với ai ∈ Z và n1 < n2 < · · · < nk , là các số tự nhiên sao cho với mọi số nguyên x, tồn tại chỉ số j, sao cho ta có đồng dư thức: x ≡ aj (mod nj ). (1.11) Một câu hỏi cơ bản được đặt ra từ năm 1934 là: n1 có được chọn tùy ý không? Đặc biệt nó có thể lớn tuỳ ý không? Giá trị kỉ lục của nó cho đến nay là 20, do S.R. L Choi tìm ra. Một câu hỏi khác: “Đúng hay không, với mọi số d > 0, tồn tại một hệ phủ đồng dư với (ni , d) = 1"? Một tập số nguyên 1 < n1 < · · · < nk được gọi là hệ phủ đồng dư nếu chúng có thể lấy làm các modulo của hệ (1.11). Hệ phủ đồng dư được gọi là bất khả quy hay hệ phủ đồng dư thu gọn nếu không có tập con nào của nó là một hệ phủ đồng dư. Dễ thấy chỉ tồn tại một số hữu hạn hệ phủ đồng dư bất khả quy độ lớn k. Ví dụ 1.1 . (0,2); (0,3); (1,4); (1,6); (11,12) là một phủ đồng dư có thể viết đơn giản (2,3,4,6,12) là một tập phủ đồng dư. Chứng minh (Erd˝os). Xét các hệ đồng dư, mà có thể chỉ ra rằng chúng lập thành một hệ phủ: 0 (mod 2), 0 (mod 3), 1 (mod 4), 3 (mod 8), 7 (mod 12), và 23 (mod 24). Mỗi một đồng dư thức kéo theo một đồng dư tương ứng đối với lũy thừa nào đó của 2. Ví dụ, đồng dư thức k ≡ 1 (mod 4) cùng với
11 24 ≡ 1(mod 5) kéo theo 2k ≡ 2(mod 5). Để thấy rõ điều này, giả sử k = 4n + 1 và nhận xét rằng: 2k ≡ 24n+1 ≡ 2(24 )n ≡ 2 (mod 5). Tương tự, nếu k là một số nguyên không âm thì ít nhất một trong các đồng dư sau nghiệm đúng: 2k ≡ 1 (mod 3), 2k ≡ 1 (mod 7), 2k ≡ 2 (mod 5), 2k ≡ 8 (mod 17), 2k ≡ 27 (mod 13) hoặc 2k ≡ 23 (mod 241). Bây giờ xét các đồng dư thức: 1 (mod 3), 1 (mod 7), 2 (mod 8), 8 (mod 17), 27 (mod 13), và 223 (mod 241). Vì các modulo đôi một nguyên tố cùng nhau, tồn tại vô hạn số nguyên thỏa mãn tất cả các đồng dư thức trên (theo định lý phần dư Trung Hoa). Bây giờ nếu số nguyên lẻ a thỏa mãn tất cả các đồng dư, thì tất cả các số nguyên có dạng a − 2k chia hết cho một trong các modulo 3, 7, 5, 17, 13 hoặc 241. Suy ra rằng a − 2k không là số nguyên tố và do đó a không có dạng 2k + p. Một ví dụ khác về ứng dụng hệ phủ đồng dư được biết đến bởi R. L Graham trong cuốn "A Fibonacci-like sequence of composite number", xuất bản năm 1964. Kết quả của ông về nghĩa nào đó là ngược lại với một giả thuyết được biết, nói rằng dãy Fibonacci, xác định bởi f0 = 0, f1 = 1, và với n ≥ 0, fn+2 = fn+1 + fn , chứa vô hạn số nguyên tố. Graham sử dụng hệ phủ đồng dư để chỉ ra rằng, có thể chọn các giá trị ban đầu f0 và f1 nguyên tố cùng nhau, sao cho dãy tương ứng chỉ chứa các hợp số. Giá trị nhỏ nhất được biết đến là: f0 = 331636535998274737472200656430763 và f1 = 1510028911088401971189590305498785. Một bài toán mở quan trọng trong chủ đề này là giả thuyết của Erd˝os nói rằng: “Với mọi c ≥ 2, tồn tại hệ phủ đồng dư với n1 ≥ c và các modulo khác nhau”. Điều này được biết đến là đúng với một vài giá trị của c, kỷ lục cho đến nay là c = 20. Nếu có một hệ phủ đồng dư với các modulo khác nhau và n1 ≥ c với mọi c ≥ 2 thì ta nhận được một kết quả về cấp số cộng “với mọi số nguyên dương m, tồn tại một cấp số cộng mà không có số hạng nào của nó là tổng của một lũy thừa 2 và một số nguyên có không quá m ước nguyên tố". Bài toán dưới đây cho chúng ta một áp dụng của hệ phủ đồng dư trong giải toán. Bài toán 1.1 (Kỳ thi toán học Mỹ (AIME)) Harold, Tanya và Ulysses sơn một hàng rào rất dài. Harold bắt đầu sơn từ cột thứ nhất
12 và sơn mỗi cột cách đều h cột, Tanya bắt đầu sơn từ cột thứ 2 và sơn mỗi cột cách đều t cột, Ulysses bắt đầu sơn từ cột thứ 3 và sơn mỗi cột cách đều u cột. Giả sử mỗi cột được sơn đúng một lần, hãy tìm tất cả các bộ ba có thể (h, t, u). Lời giải. Ta đánh số các cột lần lượt là 1, 2, 3, . . . , theo bài ra, Harold sơn cột 1 và mỗi cột cách đều h, Tanya sơn cột 2 và mỗi cột cách đều t, Ulysses sơn cột thứ 3 và mỗi cột cách đều u. Do đó Ulysses không thể sơn cột thứ 4, vì nếu ngược lại thì Ulysses sơn tất cả các cột tiếp theo. Giả sử rằng Harold sơn cột 4, khi đó Ulysses không thể sơn cột 5, vì nếu ngược lại thì cả Harold và Ulysses đều sơn cột 7. Do đó Tanya sơn cột 5, Ulysses sơn cột 6 và (h, t, u) = (3, 3, 3). Mặt khác, giả sử rằng Tanya sơn cột 4, khi đó Ulysses không thể sơn cột 5, vì nếu ngược lại thì không còn cột nào cho Harold sơn. Vì vậy Ulysses sơn cột 7 và (h, t, u) = (4, 2, 4). Bài toán này thực chất là hỏi rằng “làm thế nào có thể phân hoạch tập hợp các số nguyên thành 3 cấp số cộng”. Bộ ba thứ 2 (4,2,4) thú vị hơn một chút so với bộ ba (3,3,3) vì không phải tất cả các công sai đều bằng nhau. Trong lý thuyết số sơ cấp, cấp số cộng được gọi một cách tương đương là các lớp thặng dư với modulo khác nhau. Với cách đặt vấn đề như vậy, cấp số cộng a + km với k nguyên được ký hiệu bởi a (mod m). Ta có thể tổng quát hóa bài toán trên như sau: “Tồn tại hay không một tập hữu hạn đồng dư với modulo khác nhau, lớn hơn hoặc bằng 2, sao cho chúng lập thành một phân hoạch của tập số nguyên” . Trong bài báo “New problems and results in combinatorialnumbertheory, Monogr. Enseign Math 28, L’EnseignementMathematique, Geneva, 1980” P. Er- dos và R. L. Graham đã chứng minh điều này là không thể. Khi giảm nhẹ một chút giả thiết, ta thay điều kiện phân hoạch bởi điều kiện tồn tại hữu hạn các đồng dư sao cho mọi số nguyên thuộc ít nhất một trong chúng. Mục đích của chúng ta là trình bày một chứng minh sơ cấp về mối quan hệ giữa hai giả thuyết nổi tiếng đã biết. Năm 1849, A.de Poligna giả thuyết rằng, mọi số nguyên lẻ n (n ≥ 3) có thể biểu diễn dưới dạng 2k + p, ở đây k là một số nguyên không âm và p hoặc là số nguyên tố, hoặc là 1. Erd˝os đã bác bỏ điều này bằng cách chứng minh rằng, tồn tại một cấp số cộng mà không có số hạng nào của nó có dạng trên.
13 1.2.2. Giả thuyết Selfridge và Schinzel và một số bài toán Trong mục này ta quan tâm đến hai giả thuyết quan trọng khác của Selfridge và Schinzel. Giả thuyết Selfridge nói rằng “Không tồn tại hệ phủ đồng dư với modulo là các số lẻ khác nhau”; Giả thuyết Schinzel nói rằng "Trong mỗi hệ phủ đồng dư ai (mod n1 ) với 1 ≤ n ≤ r, tồn tại i 6= j sao cho ni | nj ". Schinzel đã chứng minh rằng giả thuyết của Selfridge kéo theo giả thuyết Schinzel bằng cách sử dụng tính bất khả quy của một số đa thức. Định lý 1.4 Giả thuyết của Sefridge kéo theo Schinzel. Chứng minh. Giả sử giả thuyết của Sefridge đúng nhưng giả thuyết của schinzel không đúng. Khi đó tồn tại một hệ phủ đồng dư thu gọn as (mod ns ) sao cho mi 6 |mj với mọi i 6= j. Giả sử mi = 2βi Oi ở đây Oi là số lẻ với 1 ≤ i ≤ r. Ta giả sử rằng các đồng dư được đánh số theo cách sao cho nếu i < j thì βi ≤ βj . Từ giả thuyết Selfridge suy ra rằng βr > 0 và rõ ràng tất cả các số Oi là khác nhau. Nếu Oi ≥ 3 với mọi i, thì ta có mâu thuẫn với giả thuyết Selfridge. Vì nếu x ≡ ai (mod 2βi Oi ) và 2βi |(2βi Oi ) thì x ≡ ai (mod Oi ) khi đó ta sẽ có hệ phủ đồng dư với tất cả các modulo lẻ. Cho nên, nếu ai (mod ni ) là một hệ phủ đồng dư và ni |mi với mọi i, thì ai (mod ni ) cũng là một hệ phủ đồng dư. Vì vậy, tồn tại i0 sao cho Oi0 = 1 và do đó mi0 = 2i0 . Suy ra rằng i0 = r nếu ngược lại ta có mi0 |mi0 +1 . Tiếp theo ta nâng hệ phủ đồng dư bởi −ar có nghĩa là thay đổi biến x thành x+ar , để sao cho có thể giả sử rằng đồng dư thứ r có dạng 0 (mod 2βr ). Xét số nguyên có dạng x2βr − 1 với x ∈ Z, khi đó không có số nguyên nào trong các số đó được phủ bởi đồng dư thức 0 (mod 2βr ) . Tuy nhiên tất cả chúng là được phủ bởi các đồng dư thức còn lại vì hệ là một hệ phủ đồng dư. Hệ của chúng ta bây giờ có dạng: x2βr − 1 ≡ as (mod ms ), 1 ≤ s ≤ r − 1. (1.12) Chú ý rằng có thể xảy ra trường hợp không phải tất cả các đồng dư thức có nghiệm, tuy nhiên khi một đồng dư thức có nghiệm ta phải có: gcd(2βr , ms )|as + 1.
14 Vì gcd(2βs , ms ) = 2βs nên suy ra rằng 2βs |as + 1. Đặt U = {s : 1 ≤ s ≤ r − 1 sao cho 2βs |as + 1}. Với mỗi s ∈ U hệ đồng dư thức (1.12) có dạng x2βr −βs ≡ (as + 1)/2βs (mod Os ) hoặc x ≡ cs (mod Os ) với số nguyên cs nào đó. Bài toán 1.2 Tìm số lớn nhất trong hệ phủ đồng dư thu gọn 1 ≤ n1 < · · · < nk và có bao nhiêu hệ phủ đồng dư thu gọn có dạng 1 ≤ n1 < · · · < n` ≤ x với ` tùy ý. Để giải quyết được bài toán này Erd˝os đã chỉ ra rằng cần phải ước P 1 lượng hoặc xác định giá trị max . Khi đó có một câu hỏi là “liệu có ni bao nhiêu số nguyên n sao cho các ước lớn hơn 2 của n lập thành một hệ phủ thu gọn”. Ví dụ với n = 12 thì tập {2, 3, 4, 6, 12} là các ước của 12 và lập thành hệ phủ đồng dư thu gọn. Erd˝os giả thuyết giả rằng với mọi C tồn tại số nguyên N với σ(N )/N > C sao cho các ước của N không lập thành hệ phủ đồng dư, trong đó σ(N ) là tổng các ước của N . J. Haight đã chứng minh giả thuyết này trong bài báo của ông. Bây giờ có thể phát biểu Bài toán cực trị như sau: Đặt f (x) = max σ(m)/m, ở đây cực đại được lấy theo mọi m mà m
15 cho một số nguyên tố thuộc P . Nếu jx dần đến vô cùng hoặc tương đương, tồn tại hệ (1.11) với n lớn tuỳ ý, thì với mỗi r tồn tại một cấp số cộng mà không có phần tử nào của nó có dạng 2k + Qr , trong đó Qr có không quá r ước nguyên tố. Chắc chắn mỗi n đủ lớn đều có dạng 2k + Qr , r < log log n nhưng người ta vẫn chưa chứng minh được điều này. Như vậy, ta vẫn chưa biết được rằng: Tồn tại hay không vô hạn số nguyên lẻ n sao cho n − 2u , 1 ≤ 2u ≤ n, không bao giờ là số Squarefree (số không có ước chính phương khác 1)? Thậm chí có tồn tại số nguyên nào thoả mãn tính chất đó không?
16 Chương 2 Số Ramsey và tập đơn sắc Chương 2 được dành để trình bầy về số Ramsey và một số kết quả mới về số Ramsey, cũng như nghiên cứu tập đơn sắc và các bài toán ứng dụng. Tài liệu tham khảo chính được sử dụng trong chương này là các tài liệu [2], [3], [6], [7]. 2.1. Số Ramsey 2.1.1. Định nghĩa Để đi đến định nghĩa số Ramsey ta xét bài toán sau đây. Bài toán 2.1 Trong mặt phẳng cho 6 điểm được nối với nhau từng đôi một bởi các đoạn màu xanh hoặc màu đỏ. Chứng minh rằng luôn tìm được 3 điểm sao cho các đoạn nối chúng có cùng một màu? Vấn đề đặt ra sau bài toán này là liệu số 6 trong bài toán trên đã là số nhỏ nhất hay chưa để tìm được 3 điểm nối với nhau bằng các cạnh được tô cùng màu. Nếu bài toán này thay vì cho 6 điểm ta cho 5 điểm hoặc ít hơn nữa thì có tìm được 3 điểm được nối với nhau cùng màu hay không? Câu trả lời là không thể và số 6 nêu trong bài toán trên là số nhỏ nhất để tìm được 3 điểm được nối với nhau bằng các cạnh được tô cùng màu. Mở rộng phạm vi bài toán hơn nữa thì để tìm được 4 điểm, 5 điểm, ..., nối với nhau bằng các cạnh được tô cùng màu thì số nhỏ nhất phải cho ban đầu là bao nhiêu? Đây vẫn là câu hỏi khó trả lời khi ta cho số điểm được nối với nhau bằng các cạnh được tô cùng màu tăng lên. Một cách phát biểu khác của bài toán trên là: Trong số 6 người tại một bàn tiệc luôn tìm được hoặc ba người đôi một quen nhau hoặc ba
17 người đôi một không quen nhau. Con số nhỏ nhất vừa nói đến trong các vấn đề vừa đặt ra được gọi là các số Ramsey, mang tên nhà toán học người Anh đã chứng minh được định lý nổi tiếng trong lý thuyết tập hợp là sự tổng quát hoá nguyên lý Dirichlet. Để có thể phát biểu những kết quả tổng quát hơn chúng ta có một số định nghĩa. Định nghĩa 2.1 Đồ thị Kn là bộ gồm hai tập V, E, trong đó V là tập gồm n điểm còn E là tập các đoạn nối giữa tất cả các cặp điểm trong V . Ta ký hiệu Kn = (V, E), gọi các phần tử của V là các đỉnh và V là tập đỉnh của Kn . Mỗi đoạn nối hai đỉnh u, v ∈ V sẽ được gọi là một cạnh của Kn và ký hiệu là (u, v) và tập E được gọi là tập cạnh của Kn . Khi đó ta có thể phát biểu lại bài toán 2.1 như sau: Giả sử mỗi cạnh của K6 được tô bởi một trong hai màu xanh hoặc đỏ. Khi đó, K6 luôn chứa hoặc K3 với tất cả các cạnh được tô màu xanh hoặc được tô màu đỏ. Để giải quyết bài toán trên Ramsey năm 1930 đã chứng minh định lý sau: Định lý 2.1 Cho hai số nguyên m1 , m2 ≥ 2. Khi đó luôn tồn tại một số nguyên N = N (m1 , m2 ) sao cho với mọi n ≥ N, nếu đồ thị Kn được tô bởi 2 màu thì luôn tồn tại hoặc một đồ thị Km1 được tô bởi màu thứ nhất hoặc Km2 được tô bởi màu thứ hai. Định nghĩa 2.2 Giả sử i và j là hai số nguyên dương sao cho i ≥ 2, j ≥ 2. Số nguyên dương m được gọi là có tính chất (i, j)-Ramsey nếu trong Km mỗi cạnh được tô bởi một trong hai màu xanh, đỏ thì Km luôn chứa hoặc là Ki đỏ, hoặc Kj xanh. Ta có định nghĩa số Ramsey như sau. Định nghĩa 2.3 Số Ramsey R(i, j) là số nguyên dương nhỏ nhất có tính chất (i, j)-Ramsey. Chẳng hạn, ta có R(3, 3) = 6, vì 6 có tính chất (3,3)- Ramsey và những số nguyên dương nhỏ hơn nó không có tính chất này. 2.1.2. Tính chất số Ramsey Dưới đây ta trình bày một số tính chất cơ bản sau đây của số Ramsey R(i, j).
18 a) Số Ramsey khi đổi chỗ m và n thì không thay đổi, tức là R(n, m) = R(m, n). b) R(2, m) = R(m, 2) = m. Kết hợp với tính chất a), ta có R(2, m) = R(m, 2), nên suy ra R(2, m) = R(m, 2) = m. c) Nếu m có tính chất (i, j) - Ramsey thì mọi số n > m cũng có tính chất này. Chứng minh. Số m có tính chất (i, j)-Ramsey có nghĩa là nếu tô màu đầy đủ đồ thị Km bởi hai màu xanh hoặc đỏ thì Km chứa Ki được tô màu xanh, hoặc Kj được tô màu xanh. Dễ thấy, khi đó đồ thị đầy đủ Kn , n > m được tô bởi hai màu xanh và đỏ sẽ chứa ít nhất Ki đỉnh được tô màu xanh hoặc Kj đỉnh được tô màu đỏ. Tương tự ta dễ dàng chứng minh được hai tính chất sau: d) Nếu m không có tính chất (i, j)-Ramsey thì mọi số n < m cũng không có tính chất này. e) Nếu i1 ≥ i2 thì R(i1 , j) ≥ R(i2 , j). 2.1.3. Tiệm cận số Ramsey Từ kết quả ở mục trước ta thấy 6 có tính chất (3,3)- Ramsey. Nhưng vấn đề là 6 có phải là số nhỏ nhất có tính chất này hay không? Giả sử các cạnh của K5 được tô màu như chỉ ra trong hình vẽ dưới đây (đỏ - đậm , xanh - nhạt). Rõ ràng không thể tìm được K3 đỏ (đậm) cũng như không thể tìm được K3 xanh (nhạt). Như vậy số 5 không có tính chất (3,3)- Ramsey. Dễ thấy rằng mọi số nguyên dương nhỏ hơn 5 cũng không có tính chất (3,3)-Ramsey. Vậy 6 là số nhỏ nhất có tính chất này. (Hình 2.1) Hình 2.1: Đỏ màu đậm, xanh màu nhạt