Luận án Tiến sĩ: Phương pháp Phổ Đồ Thị trong Bài Toán Tổ Hợp Cộng Tính

VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM VIỆN TOÁN HỌC ———————————- ĐỖ DUY HIẾU PHƯƠNG PHÁP PHỔ CỦA ĐỒ THỊ TRONG MỘT SỐ BÀI TOÁN TỔ HỢP CỘNG TÍNH LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội - 2019 VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM VIỆN TOÁN HỌC ———————————- ĐỖ DUY HIẾU PHƯƠNG PHÁP PHỔ CỦA ĐỒ THỊ TRONG MỘT SỐ BÀI TOÁN TỔ HỢP CỘNG TÍNH Chuyên ngành: Cơ sở toán học cho tin học Mã số: 9.10 LUẬN ÁN TIẾN SĨ TOÁN HỌC Người hướng dẫn: PGS. LÊ ANH VINH Hà Nội - 2019 Tóm tắt Trong Luận án này, chúng tôi sẽ sử dụng phương pháp phổ của đồ thị để nghiên cứu về lực lượng của một số tập hợp trên không gian vectơ trên trường và vành hữu hạn như: Hàm nở hai biến, tập khoảng cách và tập tích, tập tổng - tỉ số, tập khoảng cách trên đa tạp chính quy và tập thể tích khối. Luận án gồm 04 chương chính: Trong Chương 1, chúng tôi nhắc lại kiến thức cơ bản liên quan đến phương pháp đại số tuyến tính trong đồ thị: ma trận kề, phổ của đồ thị, (n, d, λ) - đồ thị, Bổ đề trộn nở. Trong Chương 2, chúng tôi nghiên cứu một số (n, d, λ) - đồ thị trên không gian vectơ Fnq và Znq như đồ thị tổng - tích, đồ thị tích - tổng, đồ thị tổng - bình phương, đồ thị tích, đồ thị Euclid hữu hạn.

Trong Chương 3, chúng tôi sử dụng pháp đồ thị để nghiên cứu một số bài toán tổ hợp cộng tính. Cụ thể, chúng tôi sẽ sử dụng các đồ thị xây dựng trong Chương 2 để đánh giá một số tập hợp như tập khoảng cách, tập tích, tập thể tích khối, tập tổng - tỉ số, hàm nở hai biến trên trường và vành hữu hạn. Trong Chương 4, chúng tôi sử dụng phương pháp phổ của đồ thị mở rộng để nghiên cứu và đưa ra kết quả tổng quát cho tập khoảng cách của một tập trên đa tạp chính quy. 3 Abstract In this thesis, we use the techniques from the spectral graph theory to study the cardinality of some sets in vector spaces over finite fields and finite rings, such as the images of two-variable expanders, the dis- tance sets, the product sets, the sum - ratio sets, the volume set of boxes, and the distance sets in regular varieties.

The thesis consist of four main chapters. In Chapter 1, we recall some basic knowledge related to linear al- gebraic methods in the graph: the adjacency matrix, the spectrum of a graph, the definition and properties of (n, d, λ) - graph, and the ex- pander mixing lemma. In Chapter 2, we study some (n, d, λ) - graphs in vector spacesover finite fields and finite rings, such as the sum - product graph, the prod- uct - sum graph, the sum - square graph, the product graph, and the finite Euclidean graph. In Chapter 3, we use the expanding properties of the graphs in Chap- ter 2 to evaluate the cardinalities of distance sets, product sets, volume sets of boxes, sum - ratio sets, and images of two-variable expanders in vector spaces over finite fields and finite rings.

In Chapter 4, we use the directed version of the expander mixing lemma to study the distance set problem in general regular varieties. 4 Lời cam đoan Tôi xin cam đoan Luận án này là tập hợp các nghiên cứu của tôi. Những kết quả trích từ các bài báo viết chung đã nhận được sự cho phép sử dụng của các đồng tác giả. Các kết quả nêu trong Luận án là trung thực và chưa từng được một ai khác công bố.

5 Lời cảm ơn Tôi xin chân thành cảm ơn PGS. Lê Anh Vinh, người đã dẫn dắt tôi vào con đường nghiên cứu khoa học. Không chỉ là một người hướng dẫn khoa học tận tâm, chia sẻ của thầy với tôi về những buồn, vui đời thường suốt nhiều năm qua là một sự động viên, khích lệ lớn để tôi vững vàng hơn trong cuộc sống. Tôi xin chân thành cảm ơn PGS.

Phan Thị Hà Dương và GS. Ngô Đắc Tân đã góp ý để Luận án của tôi hoàn thiện hơn. Những lời chia sẻ, chỉ dạy của thầy cô trong suốt quá trình làm việc, nghiên cứu của tôi sẽ là hành trang quý báu để tôi tự tin hơn trên những chặng đường sắp tới. Tôi xin cảm ơn TS.

Phạm Văn Thắng đã đồng hành cùng tôi trên con đường nghiên cứu trong suốt thời gian qua. Tôi xin cảm ơn ban lãnh đạo Viện Toán học, Phòng cơ sở toán học cho tin học và Trung tâm Đào tạo sau đại học đã cung cấp cho tôi một nơi làm việc tốt, một môi trường học thuật lành mạnh để học tập, nghiên cứu trong thời gian tôi làm nghiên cứu sinh ở đây. Cuối cùng, tôi xin tỏ lòng biết ơn vô hạn tới gia đình tôi, những người luôn bên cạnh và thương yêu tôi vô điều kiện. Hà Nội, ngày 27 tháng 02 năm 2019 Đỗ Duy Hiếu 6 Bảng các kí hiệu 1.

Cho p là một số nguyên tố lẻ, r ≥ 2 là một số tự nhiên và q = pr. | A| là lực lượng của tập hợpA. Zq là vành hữu hạn có q phần tử. Z0q là tập các phần tử không khả nghịch trên Zq.

Z× q là tập các phần tử khả nghịch trên Zq. Fq là trường hữu hạn có q phần tử. F∗q là các phần tử khác 0 của trường hữu hạn Fq. Cho f , g là các hàm số theo biến t.

f &g có nghĩa là tồn tại hằng số c > 0, sao cho f ≥ cg khi t đủ lớn. f = Θ( g) có nghĩa là tồn tại các hằng số c1 , c2 > 0 sao cho c1 f ≤ g ≤ c2 f khi t đủ lớn. Cho G = (V, E) là một đồ thị. ( x, y) là một cạnh có hướng từ x đến y.

{ x, y} là cạnh vô hướng giữa x và y của đồ thị G. 7 Mục lục Lời mở đầu 9 Giới thiệu chung. 10 1 Kiến thức chuẩn bị 17 1.1 Ma trận kề .2 Phổ của đồ thị .3 (n, d, λ) - đồ thị và Bổ đề trộn nở. 20 2 Một số (n, d, λ) - đồ thị 25 2.1 Đồ thị tổng - bình phương .1 Đồ thị tổng - bình phương trên trường hữu hạn .2 Đồ thị tổng - bình phương trên vành hữu hạn .2 Đồ thị tổng - tích .1 Đồ thị tổng - tích trên trường hữu hạn .2 Đồ thị tổng - tích trên vành hữu hạn .3 Đồ thị tích - tổng .1 Đồ thị tích - tổng trên trường hữu hạn .2 Đồ thị tích - tổng trên vành hữu hạn .1 Đồ thị tích trên trường hữu hạn .2 Đồ thị tích trên vành hữu hạn .5 Đồ thị Euclid hữu hạn.

36 3 Đánh giá lực lượng của một số tập hợp trên trường và vành hữu hạn 37 3.1 Giới thiệu về phương pháp phổ của đồ thị .2 Tập khoảng cách, tập tích .1 Giới thiệu tổng quan về bài toán tập khoảng cách và tập tích .2 Đánh giá tập khoảng cách trên trường và vành hữu hạn .3 Đánh giá tập tích trên trường và vành hữu hạn .3 Tập thể tích khối .1 Giới thiệu tổng quan về tập thể tích khối .2 Một số kết quả cần dùng .3 Đánh giá tập thể tích khối trên trường hữu hạn .4 Đánh giá tập thể tích khối trên vành hữu hạn .4 Tập tổng - tỉ số .1 Giới thiệu tổng quan về bài toán tổng - tỉ số .2 Đánh giá tổng - tỉ số trên trường hữu hạn .3 Đánh giá tổng - tỉ số trên vành hữu hạn .5 Hàm nở hai biến .1 Giới thiệu tổng quan về hàm nở hai biến. 59 4 Tập khoảng cách trên đa tạp chính quy 61 4.1 Giới thiệu tổng quan về bài toán tập khoảng cách trên đa tạp chính quy .2 Đánh giá cho dạng toàn phương không suy biến .3 Đánh giá cho đa thức chéo P(x) = ∑ a j x sj. 69 j =1 Kết luận 72 Tài liệu tham khảo 76 9 Lời mở đầu Trong những năm gần đây, tổ hợp đã được ứng dụng vào các lĩnh vực khoa học khác nhau như: khoa học máy tính, vật lý, hóa học, .Với sự mở rộng đó, nhiều bài toán tổ hợp mới ra đời cùng với nhiều phương pháp vốn thuộc các nhánh toán học khác đã được áp dụng để giải quyết như: xác suất, giải tích, đại số, hình học; nhờ đó đã thu được nhiều kết quả mới không hiển nhiên. Luận án "Phương pháp phổ của đồ thị trong một số bài toán tổ hợp cộng tính" sử dụng (n, d, λ) - đồ thị và Bổ đề trộn nở để nghiên cứu các bài toán tổ hợp cộng tính.

Những kết quả mới của Luận án được trình bày trong Chương 3 và Chương 4. Trong Chương 3, chúng tôi sử dụng phương pháp phổ của đồ thị dựa vào (n, d, λ) - đồ thị và Bổ đề trộn nở để nghiên cứu một số bài toán như tập khoảng cách, tập tích, tập thể tích khối, tập tổng - tỉ số, hàm nở hai biến. Tập khoảng cách, tập tích: Một bài toán mở cổ điển trong hình học tổ hợp là bài toán về khoảng cách của Erdős [20]. Bài toán yêu cầu chúng ta tìm số các khoảng cách khác nhau tối thiểu được xác định bởi một tập N điểm trên mặt phẳng Euclid.

Erdős gọi số khoảng cách tối thiểu này là g( N ) và giả thuyết rằng g( N ) & √ N. Ông cũng quan sát dựa trên một khẳng định hình học LogN đơn giản trên đường tròn, rằng g( N ) & N 1/2. Số mũ 1/2 đã được cải thiện một cách chậm chạp trong vòng hơn 50 năm qua bởi một loạt các lý luận phức tạp, sử dụng công cụ từ nhiều lĩnh vực khác nhau của toán học. Tháng 11 năm 2010, Guth và Katz [26] đã chứng minh được khẳng định gần tối ưu của bài N toán này: trong tập N điểm bất kỳ trên mặt phẳng sẽ có g( N ) & LogN khoảng cách phân biệt.

Một cách tương tự, phiên bản hữu hạn của bài toán khoảng cách của Erdős là việc đi tìm lực lượng tối thiểu của tập các khoảng cách xác định bởi các tập 10 N điểm trong không gian vectơ trên trường/vành hữu hạn. Không gian Euclid hữu hạn Fnq bao gồm các vectơ cột x, với n là số tự nhiên và n ≥ 2. Chúng ta nhắc lại định nghĩa khoảng cách giữa các điểm x, y ∈ Fnq n k x − y k = ∑ ( x j − y j )2. j =1 Cho tập điểm E ⊂ Fnq , tập khoảng cách của E được định nghĩa như sau: ∆(E ) = {k x − yk : x, y ∈ E }.