Luận văn Thạc sĩ Toán học: Dãy Farey và áp dụng

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

Thêm vào BST

Báo xấu

25
lượt xem 3
download

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

Mục đích chính của luận văn là trình bày lại một số kết quả được công bố của Farey và các ứng dụng với các lí thuyết khác. Để hiểu rõ hơn, mời các bạn tham khảo chi tiết nội dung luận văn này.

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: Dãy Farey và áp dụng

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ————————————————— VŨ NGỌC TÚ DÃY FAREY VÀ ÁP DỤNG LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - Năm 2015
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ————————————————— VŨ NGỌC TÚ DÃY FAREY VÀ ÁP DỤNG 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 PGS.TS ĐÀM VĂN NHỈ Thái Nguyên - Năm 2015
1 Lời cảm ơn Để hoàn thành được luận văn một cách hoàn chỉnh, tôi luôn nhận được sự hướng dẫn và giúp đỡ nhiệt tình của PGS.TS Đàm Văn Nhỉ (Trường Đại học Sư Phạm Hà Nội). Tôi xin chân thành bày tỏ lòng biết ơn sâu sắc đến thầy và xin gửi lời tri ân nhất của tôi đối với những điều thầy đã dành cho tôi. Tôi xin chân thành cảm ơn ban lãnh đạo phòng sau Đại học, quý thầy cô giảng dạy lớp Cao học K7C (2014- 2016) Trường Đại học Khoa Học - Đại học Thái Nguyên đã tận tình truyền đạt những kiến thức quý báu cũng như tạo điều kiện cho tôi hoàn thành khóa học. Tôi xin gửi lời cảm ơn chân thành nhất tới gia đình, bạn bè, những người đã luôn động viên, hỗ trợ và tạo mọi điều kiện cho tôi trong suốt quá trình học tập và thực hiện luận văn. Xin trân trọng cảm ơn! Thái Nguyên, tháng 11 năm 2015 Người viết luận văn Vũ Ngọc Tú
2 Mục lục Lời cảm ơn 1 Mục lục 2 Mở đầu 1 1 Dãy Farey 3 1.1 Các tính chất của dãy Farey . . . . . . . . . . . . . . . . . 3 1.1.1 Một số kiến thức chuẩn bị . . . . . . . . . . . . . . 3 1.1.2 Dãy Farey . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.3 Tính chất của dãy Farey . . . . . . . . . . . . . . . 7 1.2 Độ dài của dãy Farey . . . . . . . . . . . . . . . . . . . . . 11 1.3 Xấp xỉ số vô tỉ qua dãy Farey . . . . . . . . . . . . . . . . 13 1.3.1 Xấp xỉ tốt . . . . . . . . . . . . . . . . . . . . . . . 13 1.3.2 Mô tả hình học của phép xấp xỉ vô tỉ dựa vào dãy phân số Farey . . . . . . . . . . . . . . . . . . . . . 16 1.4 Đường tròn Ford . . . . . . . . . . . . . . . . . . . . . . . . 19 1.5 Từ đại số đến hình học và ngược lại . . . . . . . . . . . . . 26
3 2 Áp dụng 29 2.1 Hàm Zeta . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2 Áp dụng của dãy phân số Farey . . . . . . . . . . . . . . . 30 2.2.1 Dãy phân số Farey và các giả thuyết . . . . . . . . . 32 2.2.2 Chứng minh chiều xuôi mệnh đề tương đương . . . . 33 2.2.3 Chứng minh chiều ngược lại . . . . . . . . . . . . . 35 2.3 Một số ví dụ khác về áp dụng của dãy phân số Farey . . . . 41 Kết luận 45 Tài liệu tham khảo 46
1 Mở đầu Số học là một trong những lĩnh vực cổ xưa nhất của toán học và cũng là những lĩnh vực tồn tại nhiều nhất những bài toán, những giả thuyết chưa có câu trả lời. Trên con đường tìm kiếm lời giải cho những giả thuyết đó, nhiều lý thuyết lớn của toán học đã nảy sinh. Nếu như trước đây số học vẫn được xem là một trong những ngành lý thuyết xa rời thực tiễn nhất thì ngày nay nhiều thành tựu mới nhất của số học có ứng dụng trực tiếp vào các vấn đề của đời sống như thông tin, mật mã, kĩ thuật máy tính. Trong số học có những con số đặc biệt ngoài những tính chất đẹp đẽ kì diệu của nó những con số này còn có những ứng dụng bất ngờ và sâu sắc trong toán học và các lĩnh vực khác. Dãy Farey được đặt theo tên của nhà địa lý học John Farey, ông mô tả dãy phân số Farey vào năm 1816. Trong bài viết của Farey đưa ra câu hỏi sau: Có bao nhiêu số các phân số tối giản có giá trị khác nhau trong khoảng (0,1)?. Với mong muốn tìm hiểu vấn đề dãy Farey chúng tôi chọn đề tài “Dãy Farey và áp dụng”. Mục đích chính của luận văn là trình bày lại một số kết quả được công bố của Farey và các ứng dụng với các lí thuyết khác. Luận văn gồm có 2 chương Chương 1: Trong chương này chúng tôi trình bày lại về dãy Farey, như các tính chất, độ dài, xấp xỉ các số qua dãy Farey, mối quan hệ giữa dãy phân số Farey và đường tròn Ford.
2 Chương 2: Đưa ra các áp dụng của dãy Farey vào các lý thuyết khác. Mặc dù đã cố gắng rất nhiều nhưng trong luận văn này không thể tránh khỏi những thiếu sót. Tôi rất mong có được những ý kiến đóng góp của các thầy cô và các bạn. Thái Nguyên, tháng 11 năm 2015 Tác giả Vũ Ngọc Tú
3 Chương 1 Dãy Farey 1.1 Các tính chất của dãy Farey 1.1.1 Một số kiến thức chuẩn bị Định nghĩa 1.1.1. Một hàm số f xác định trên N+ và nhận các giá trị trong trường số thực R được gọi là hàm số học. Nói một cách khác, một hàm số học là một ánh xạ f : N+ → R. Định nghĩa 1.1.2. Cho f : N+ → R là một hàm số học. Hàm f được gọi là một hàm nhân nếu f 6= 0 ( nghĩa là tồn tại ít nhất một số n ∈ N+ để f (n) 6= 0) và nếu với mọi a, b ∈ N+ thỏa mãn (a, b) = 1 thì f (ab) = f (a).f (b).) Ví dụ 1. Hàm số học f : N+ → R xác định bởi f (a) = am , m ∈ Z là một hàm nhân. Định lí 1.1.3. (Công thức tổng trải) Nếu số nguyên dương n có phân tích tiêu chuẩn n = pα1 1 pα2 2 ...pαs s thì với mọi hàm nhân f ta có   s αj X Y X f (d) = 1 + f (pji ) . d|n i=1 j=1
4 Chứng minh. Khai triển tích ở vế phải của hệ thức trên ta có:   s αj Y X 1 + f (pji ) i=1 j=1 X = f (pλ1 1 )f (pλ2 2 ) · · · f (pλs s ), trong đó 0 ≤ λi ≤ αi , i = 1, ..., s, X = f (pλ1 1 pλ2 2 · · · pλs s ), vì f là hàm nhân, X = f (d), d = pλ1 1 p2λ2 · · · pλs s . d|n Định lý được chứng minh. Định nghĩa 1.1.4. Hàm số học φ : N+ → R, n 7→ ϕ(n), trong đó φ(n) là các số nguyên m thỏa mãn:   0 1 và (m, n) = 1, ta viết tất cả các số từ 1 đến mn theo bảng sau: 1 2 3 ··· n n+1 n+2 n+3 ··· 2n ··· ··· ··· ··· ··· (m − 1)n + 1 (m − 1)n + 2 (m − 1)n + 3 · · · (m − 1)n + n Ta thấy các số nguyên tố với n là tất cả các số nằm ở cột i ∈ {1, 2, ..., n} sao cho (i, n) = 1. Mỗi cột là một hệ thặng dư đầy đủ theo modulo(m) nên trong mỗi cột có đúng φ(m) số nguyên tố với m. Do đó các số nguyên tố với cả m và n là φ(m)φ(n).
5 Mặt khác ta lại có φ(mn) là các số tự nhiên k mà 1 6= k 6= mn sao cho (k, mn) = 1. Nhưng (k, mn) = 1 nếu và chỉ nếu (k, m) = (k, n) = 1. Do đó φ(mn) chính là các số nguyên dương không vượt quá mn nguyên tố đồng thời với cả m và n. Điều này chứng tỏ rằng φ(mn) = φ(m)φ(n). 1 1 Ví dụ 2. Ta có 36 = 22 .32 , khi đó: φ(36) = 36.(1 − )(1 − ) = 12. 2 3 Do đó có 12 phân số duy nhất với mẫu số 36. Hàm Euler đã được sử dụng để trả lời cho câu hỏi có bao nhiêu phân a số tối giản nằm giữa 0 và 1 với b bất kì, a < b, (a, b) = 1. Một dãy các b phân số tối giản như vậy được gọi là dãy Farey. 1.1.2 Dãy Farey a Định nghĩa 1.1.6. Tập hợp các phân số tối giản thỏa mãn 0 ≤ a < b b ≤ n, (a, b) = 1, b = 6 0 và sắp xếp theo thứ tự tăng dần được gọi là dãy phân số Farey cấp n, kí hiệu là Fn . Các số 0, 1 gọi là các phần tử cơ sở của mọi tập hợp phân số Farey và 0 1 viết được dưới dạng và . 1 1 0 1 Ví dụ 3. F1 = { , } 1 1 0 1 1 F2 = { , , } 1 2 1 0 1 1 2 1 F3 = { , , , , } 1 3 2 3 1 0 1 1 1 2 3 1 F4 = { , , , , , , } 1 4 3 2 3 4 1 Ta cũng có thể biểu diễn dãy phân số Farey như sau:
6 Hoặc dưới dạng cây Stern:
7 1.1.3 Tính chất của dãy Farey Từ phần này trở đi của luận văn ta kí hiệu Fn là dãy phân số Farey. a c Định lí 1.1.7. Nếu và là hai phần tử liên tiếp của Fn thì (b + d) > n. b d a+c Chứng minh. Xét phân số (phân số này được gọi là trung bình của b+d a c và ). Khi đó: b d a+c a bc − ad − = >0 b+d b b(b + d) và c a+c bc − ad − = >0 d b + d d(b + d) Do đó: a+c a c ∈( , ) b+d b d a+c a c Nên nếu b + d ≤ n thì ∈ Fn . Điều này là vô lý vì và là hai phần b+d b d tử liên tiếp của Fn . Định lí 1.1.8. Hai phần tử liên tiếp của Fn không có mẫu số giống nhau. a c Chứng minh. Nếu b > 1 và , là hai phần tử liên tiếp trong Fn khi đó b d a + 1 ≤ c < d. Mặt khác: a a a+1 c < < ≤ b b−1 b b a a c Do đó là một phần tử nằm giữa hai phần tử liên tiếp và vô lý. b−1 b d Ta có điều phải chứng minh. a c Định lí 1.1.9. (Tính chất lân cận) Nếu và là hai phần tử liên tiếp b d của Fn thì ac − bd = 1. Chứng minh. Đầu tiên ta cần chứng minh một bổ đề sau:
8 Bổ đề 1.1.10. Nếu (a, b) = 1 thì khi đó tồn tại các số nguyên dương (x, y) sao cho: bx − ay = 1 (1.1) Chứng minh. Xét các số nguyên : b, 2b, 3b, ..., (a − 1)b và số dư của chúng khi chia cho a. Các số dư này đều khác nhau. Thật vậy, nếu: b1 b = q1 a + r b2 b = q2 a + r Với b1 , b2 ∈ {1, 2, ..., (a − 1)} thì: (b1 − b2 )b = (q1 − q2 )a ≡ 0(moda) mà b1 b2 ∈ {1, 2, ..., (a − 1)} nên b1 − b2 < a do đó b1 − b2 = 0. Dễ thấy rằng bd 6≡ 0(moda) với mọi b ∈ {1, 2, ..., (a − 1)}. Do đó ít nhất một trong các số b, 2b, 3b, ..., (a − 1)b có số dư là 1 khi chia cho a, suy ra tồn tại x ∈ {1, 2, ..., (a − 1)} và y ∈ Z+ . Ta chứng minh định lý (1.1.9) Nếu (x0 , y0 ) là nghiệm của (1.1), khi đó (x0 + ra, y0 + ra) cũng là một nghiệm với mọi số nguyên r. Chúng ta có thể chọn r sao cho: n − b < y0 + ra ≤ n đặt x = x0 + rb, y = y0 + rb khi đó (x, y) là một nghiệm của phương trình trên và thỏa mãn: (x, y) = 1, 0 ≤ n − b < y ≤ n
9 x x do đó tối giản và y ≤ n nên là một phần tử của Fn . Ta cũng có: y y x a 1 a = + > y b by b x a x c x a suy ra nằm sau trong Fn . Nếu 6= thì cũng nằm sau , khi đó: y b y d y b x c dx − cy 1 − = ≥ y d dy dy mà c a bc − ad 1 − = ≥ d b bd bd vì vậy: 1 bx − ay x a 1 1 b+y n 1 = = − ≥ + = ≥ ≥ by by y b dy bd bdy bdy dy (theo định lí (1.1.7)) x c Vô lý, vậy = do đó, bc − ad = 1 y d 28 Ví dụ 4. Tìm số hạng tiếp theo của trong F3451 . 39 h Lời giải: Giả sử là số hạng cần tìm. Theo định lý (1.1.9) ta có: k 28k − 39h = 1 Đây là phương trình Diophant trong đó 28 và 39 là nguyên tố cùng nhau 28 ( là một số hạng của dãy Farey). Do đó, phương trình này là giải được 39 và có các nghiệm tổng quát là: h = −5 + 28t (1.2) k = −7 + 39t h Lúc này chúng ta xác định với giá trị nào của t thì là số hạng tiếp theo k 28 của trong F3451 . 39
10 h 28 Ta thấy, vì là hạng tử tiếp theo của nên theo Định lý (1.1.8), ta k 39 có: 39 + k > 3451. Ngoài ra: k ≤ 3451 suy ra: 3412 < k ≤ 3451 Nhưng: k = −7 + 39t Bởi vậy: 3419 < 39t ≤ 3458. Nên t = 88 h 3459 Khi t = 88 thay vào h và k ở (1.2) ta có: = k 3425 a e c Định lí 1.1.11. (Tính chất trung bình) Nếu , , là ba phần tử liên b f d tiếp của Fn thì: e a+b = f c+d Chứng minh. Từ định lý (1.1.9) ta thu được: be − af = 1, f c − ed = 1 (1.3) Giải hệ hai phương trình trên theo ẩn e và f ta có: a+c b+d e= ,f = bc − ad bc − ad Hay: e a+c = f b+d Ta được điều phải chứng minh.
11 1 1 2 1+2 Ví dụ 5. i) ; ; là các số hạng liên tiếp của F6 và ta thấy rằng = 4 3 5 4+5 3 1 = . 9 3 1 3 2 3 1+2 ii) ; ; là các số hạng liên tiếp của F11 . Ở đây = . 4 11 7 11 4 + 7 Nhận xét 1.1.12. Tính chất trung bình luôn tạo ra các phân số tối giản. 2 Vì vậy, phân số sẽ không được tạo ra bằng cách lấy trung bình. 4 1.2 Độ dài của dãy Farey Trong phần trước ta đã làm quen với một số tính chất cơ bản của dãy Farey, vấn đề đặt ra ở đây là có bao nhiêu phân số Farey trong một dãy Farey bậc n? Do tất cả các phân số Farey đều ở dạng tối giản, nên với một mẫu số b cho trước ta kí hiệu φ(b) là số các phân số Farey trong dãy Farey bậc b. Ta có thể tính được số các phân số có trong Fn ( kể cả hai 0 1 phân số cơ sở là và ) dựa vào công thức sau : 1 1 N = 2 + φ(2) + φ(3) + ... + φ(n) ta có thể tính được φ(n) với n > 1 qua công thức: Y 1 φ(n) = n. 1− p p|n Ví dụ 6. Khi n = 7 ta có N = 2 + φ(2) + φ(3) + ... + φ(7) = 2 + 1 + 2 + 2 + 4 + 2 + 6 = 19 Do φ(n) luôn là số chẵn ngoại trừ trường hợp n = 1, 2 nên ta có: N = 2 + φ(2) + φ(3) + ... + φ(n) 1 luôn là một số lẻ, do đó số các phân số cách đều luôn bằng nhau. 2
12 Với n rất lớn thì việc tính N trở nên khó khăn hơn rất nhiều. Nhưng nhờ một tính chất của phi-hàm Euler ta có thể tính toán dễ dàng hơn. 3n2 φ(1) + φ(2) + ... + φ(n) ≈ 2 π 3n2 tức là N = 2 + 2 . Giá trị xấp xỉ này sẽ ngày càng chính xác hơn khi giá π trị của n tăng. Ta có thể lập bảng tính như sau: SỐ PHẦN TỬ CỦA DÃY FAREY
13 1.3 Xấp xỉ số vô tỉ qua dãy Farey 1.3.1 Xấp xỉ tốt
x