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 - Đỗ Duy Hiếu

b · d. Ta có định lí sau: Định lí 2.2.4. Cho d là một số tự nhiên lớn hơn 1, đồ thị tổng - tíchRq, d là một( qd+1, qd, √ 2rp(2r−1)d ) − đồ thị. Chứng minh. Trước hết, ta nhận xét rằng Rq, d là một đồ thị qd - chính quy và có qd+1 đỉnh. Bây giờ chúng ta đi tìm chặn trên cho giá trị trị riêng thứ hai của đồ thịRq, d. Với U = (a, b) 6= V = (c, d) ∈ V(Rq, d) ta đếm số nghiệm của hệ phương trình a+ u = b · v, c+ u = d · v vớiW = (u, v) ∈ V(Rq, d). (2.2.1) Với mỗi nghiệm v của phương trình (b− d) · v = a− c (2.2.2) tồn tại duy nhất u thỏa mãn (2.2.1). Vì vậy, chúng ta chỉ cần đếm số nghiệm của phương trình (2.2.2). Giả sử pα là ước lớn nhất của q (0 ≤ α ≤ r) sao cho tất cả các tọa độ của b − d đều chia hết cho pα. Nếu pα - a− c khi đó phương trình (2.2.2) vô nghiệm. Giả sử pα | a − c. Đặt γ = a−cpα ∈ Zpr−α và x = b−dpα ∈ Zdpr−α . Bây giờ chúng ta đếm số nghiệm v ∈ Zdpr−α của x · v = γ. (2.2.3) Do pα là ước lớn nhất của q sao cho tất cả các tọa độ của b− d chia hết cho pα, tồn tại chỉ số xj không là ước của p. Với mỗi cách chọn vk ∈ Zpr−α , k 6= j, ta có duy nhất một vj ∈ Zpr−α thỏa mãn phương trình (2.2.3). Có nghĩa là số nghiệm của phương trình (2.2.3) là p(d−1)(r−α). Với mỗi nghiệm của phương trình (2.2.3), thay vào phương trình (2.2.2) ta được pdα nghiệm. Do đó, phương trình (2.2.2) có qd−1pα nghiệm nếu pα | a− c. Từ đó ta có, với hai đỉnh bất kì U = (a, b) và V = (c, d) ∈ V(Rq, d). Giả sử pα là ước lớn nhất của q sao cho tất cả các tọa độ của b− d cũng chia hết 31 cho pα, khi đó U và V có qd−1pα đỉnh chung nếu pα | a− c và không có đỉnh chung trong trường hợp còn lại. Giả sử A là ma trận kề củaRq, d. Khi đó ta có: A2 = qd−1 J+ (qd− qd−1)I − qd−1 ∑ 0≤α<r Eα+ ∑ 0<α<r (qd−1pα− qd−1)Fα, (2.2.4) trong đó J là ma trận có tất cả các phần tử đều bằng một, I là ma trận đơn vị, Eα là ma trận kề của đồ thị BE, α. Hai đỉnh bất kì U = (a, b) và V = (c, d) ∈ V(Rq, d), {U, V} là một cạnh của BE, α khi và chỉ khi pα là ước lớn nhất của q sao cho tất cả các tọa độ của b− d chia hết cho pα nhưng c− a không chia hết cho pα. Fα là ma trận kề của đồ thị BF, α, với hai đỉnh bất kì U = (a, b) và V = (c, d) ∈ V(Rq, d), {U, V} là một cạnh của BF, α khi và chỉ khi pα là ước lớn nhất của q sao cho tất cả các tọa độ của b− d chia hết cho pα và c− a cũng chia hết cho pα. Với α > 0 bất kì, khi đó BE,α là đồ thị chính quy, bậc của mỗi đỉnh nhỏ hơn p(r−α)d và BF, α là đồ thị chính quy, bậc của mỗi đỉnh nhỏ hơn p(r−α)(d+1). Do đó, tất cả các giá trị riêng của Eα bị chặn bởi p(r−α)d và tất cả các giá trị riêng của Fα bị chặn bởi p(r−α)(d+1). E0 là ma trận có tất cả các phần tử đều bằng không. Do Rq, d là một đồ thị qd - chính quy nên qd là một giá trị riêng của A với vectơ riêng tương ứng là 1. Đồ thịRq, d là đồ thị liên thông nên qd có bội một. Bên cạnh đó, chọn b, d ∈ Zdq sao cho b · d = 2a 6= 0 khi đó Rq, d có chứa tam giác với ba đỉnh là (−a, 0), (a, b) và (a, d), có nghĩa là đồ thịRq, d không phải là đồ thị hai phần. Gọi θ là giá trị riêng khác qd của A thì |θ| < qd. Giả sử vθ là vectơ riêng ứng với giá trị riêng θ. Ta có vθ ∈ 1⊥, suy ra Jvθ = 0. Từ (2.2.4) ta có (θ2 − qd + qd−1)vθ = ( qd−1 ∑ 0≤α<r Eα + ∑ 0<α<r (qd−1pα − qd−1)Fα ) vθ. Do đó, vθ là một vectơ riêng của qd−1∑0≤α<r Eα +∑0<α<r(qd−1pα − qd−1)Fα. Suy ra θ2 ≤ qd − qd−1 + qd−1 ∑ 0≤α<r qp(r−α)d + ∑ 0<α<r (qd−1pα − qd−1)p(r−α)(d+1) < qd + 2q2d ∑ 0<α<r p−rd < 2rp(2r−1)d, 32 từ đó ta có điều phải chứng minh. 2.3. Đồ thị tích - tổng 2.3.1. Đồ thị tích - tổng trên trường hữu hạn Cho λ ∈ F∗q bất kì, đồ thị tích - tổng PSq(λ) được định nghĩa như sau: Tập đỉnh của đồ thị tích - tổngPSq(λ) là tậpF∗q ×Fq. Hai đỉnh a = (a1, a2) và b = (b1, b2) ∈ V(PSq(λ)) được nối với nhau bởi một cạnh {a, b} ∈ E(PSq(λ)) khi và chỉ khi a1b1(a2 + b2) = λ. Vinh [58] đã thu được kết quả sau: Định lí 2.3.1. ([58, Định lí 3.6]) Đồ thị PSq(λ) là một( (q− 1)q, q− 1, √3q)− đồ thị. 2.3.2. Đồ thị tích - tổng trên vành hữu hạn Đồ thị tích - tổng PSRq được định nghĩa như sau: Tập đỉnh V(PSRq) = Z×q ×Zq. Hai đỉnh a = (a1, a2) và b = (b1, b2) ∈ V(PSRq) được nối với nhau bởi một cạnh khi và chỉ khi a1b1(a2 + b2) = 1. Ta có định lí sau: Định lí 2.3.2. Đồ thị tích - tổng PSRq là một( p2r − p2r−1, pr − pr−1, √ (2r− 1)p2r−1 ) − đồ thị. Chứng minh. Trước hết, ta nhận xét rằng đồ thị tích - tổng PSRq là một đồ thị (pr − pr−1) - chính quy và có p2r − p2r−1 đỉnh. Với a = (a1, a2) 6= b = (b1, b2) ∈ V(PSRq) ta đếm số nghiệm của hệ phương trình sau: a1x1(a2 + x2) = 1 và b1x1(b2 + x2) = 1 với x = (x1, x2) ∈ V(PSRq). Điều đó tương đương với x2 = 1 a1x1 − a2, (2.3.1) x1 = (a2 − b2) = 1a1 − 1 b1 . (2.3.2) Vớimỗi x1 thỏamãn phương trình (2.3.2) tồn tại duy nhất x2 thỏamãn phương trình (2.3.1). Suy ra số nghiệm của hệ phương trình trên là số nghiệm của 33 phương trình (2.3.2). Giả sử 0 ≤ α ≤ r− 1 thỏa mãn pα = (a2− b2, pr). Ta xét hai trường hợp sau: Trường hợp 1. Nếu ( 1a1 − 1b1 , pr) 6= pα thì phương trình (2.3.2) vô nghiệm. Trường hợp 2. Nếu ( 1a1 − 1b1 , pr) = pα, ta đặt β = a2− b2/pα, γ = ( 1 a1 − 1b1 )/pα, khi đó x1 = γ/β. Thay vào phương trình (2.3.2) ta được pα nghiệm x1 thỏa mãn phương trình (2.3.2). Suy ra hai đỉnh a = (a1, a2) và b = (b1, b2) ∈ V(PSRq) bất kì thỏa mãn pα = (a2 − b2, pr) = ( 1a1 − 1b1 , pr) thì có pα đỉnh chung và không có đỉnh chung trong trường hợp khác. Gọi A là ma trận kề của đồ thị PSRq, khi đó ta có: A2 = J + (pr − pr−1 − 1)I − r−1∑ α=0 Eα + r−1 ∑ α=1 (pα − 1)Fα, trong đó I là ma trận đơn vị, J là ma trận có tất cả các phần tử đều bằng một. Đồ thị Eα có tập đỉnh trùng với tập đỉnh của PSRq. Hai đỉnh a = (a1, a2) và b = (b1, b2) ∈ V(PSRq) được nối với nhau bởi một cạnh khi và chỉ khi pα=(a2 − b2, pr) 6= ( 1a1 − 1b1 , pr). Cố định đỉnh a = (a1, a2), đỉnh b = (b1, b2) được nối với đỉnh a bởi một cạnh khi và chỉ khi a2 − b2 = pαt1 với t1 ∈ Z×r−α và 1 a1 − 1 b1 6= pαt2 với t2 ∈ Z×r−α. Từ đó ta suy ra Eα là một đồ thị (pr−α − pr−α−1)(pr − pr−α + pr−α−1) - chính quy. Đồ thị Fα có tập đỉnh trùng với tập đỉnh của PSRq. Hai đỉnh a = (a1, a2) và b = (b1, b2) ∈ V(Fα) được nối với nhau bởi một cạnh khi và chỉ khi pα = (a2 − b2, pr) = ( 1a1 − 1b1 , pr). Cố định đỉnh a = (a1, a2), đỉnh b = (b1, b2) được nối với đỉnh a bởi một cạnh khi và chỉ khi a2 − b2 = pαt1 với t1 ∈ Z×r−α và 1 a1 − 1 b1 = pαt2 với t2 ∈ Z×r−α. Từ hệ phương trình trên, ta suy ra Fα là một đồ thị (pr−α − pr−α−1)2 - chính quy. Ta có PSRq là đồ thị (pr − pr−1) - chính quy nên ma trận A có một giá trị riêng bằng λ = pr − pr−1, với vectơ riêng tương ứng là 1. Gọi θ là một giá trị riêng của A khác λ, ta có |θ| < λ. Giả sử vθ là vectơ riêng ứng với giá trị riêng θ thì vθ ∈ 1⊥. 34 Do đó ta có (θ2 − pr + pr−1 + 1)vθ = (− r−1 ∑ α=0 Eα + r−1 ∑ α=1 (pα − 1)Fα)vθ. Từ đó, vθ cũng là một vectơ riêng của ma trận −r−1∑ α=0 Eα + r−1 ∑ α=1 (pα − 1)Fα. Vì vậy θ2 ≤ pr − pr−1 − 1+ r−1∑ α=0 (pr−α − pr−α−1)(pr − pr−α + pr−α−1) + r−1 ∑ α=1 (pα − 1)(pr−α − pr−α−1)2. Từ đó suy ra điều phải chứng minh. 2.4. Đồ thị tích 2.4.1. Đồ thị tích trên trường hữu hạn Cho dạng song tuyến tính không suy biến B(·, ·) trên Fdq , với λ ∈ F bất kì, đồ thị tích Bq, d(λ) được định nghĩa như sau: Tập đỉnh của đồ thị tích Bq, d(λ) là tập V(Bq, d(λ)) = Fd\(0, . . . , 0). Hai đỉnh a và b ∈ V(Bq, d(λ)) được nối với nhau bởi một cạnh {a, b} ∈ E(Bq, d(λ)) khi và chỉ khi B(a, b) = λ. Khi λ = 0, đồ thị tích trở thành đồ thị Erdo˝s - Rényi, đồ thị này đã được tính giá trị riêng trong [3]. Với λ 6= 0, Vinh [59] có định lí sau: Định lí 2.4.1. ([59, Bổ đề 9.2]) Cho d là một số tự nhiên lớn hơn 1 và λ ∈ F∗, đồ thị tích Bq,d(λ) là một ( qd − 1, qd−1, √ 2qd−1 ) − đồ thị. 2.4.2. Đồ thị tích trên vành hữu hạn Với λ ∈ Zq tùy ý, đồ thị tích Bq(d, λ) được định nghĩa như sau: Tập đỉnh của đồ thị Bq(d, λ) là tập Zdpr\(Z0pr)d. Hai đỉnh a và b ∈ V(Bq(d, λ)) được nối với nhau bởi một cạnh {a, b} ∈ E(Bq(d, λ)) khi và chỉ khi a · b = λ. Khi λ = 0, đồ thị tích Bq(d,λ) cũng trở thành đồ thị Erdo˝s - Rényi. Với λ 6= 0, Vinh [56] thu được định lí sau: 35 Định lí 2.4.2. ([56, Định lí 2.4]) Cho d là một số tự nhiên lớn hơn 1 và λ ∈ Z×pr , đồ thị tích Bq(d,λ) là một( prd − p(r−1)d, pr(d−1), √ 2rp(d−1)(2r−1) ) − đồ thị. 2.5. Đồ thị Euclid hữu hạn Cho Q là một dạng toàn phương không suy biến trên Fdq . Với t ∈ Fq bất kì, đồ thị Euclid hữu hạn Eq(d, Q, t) được định nghĩa như sau: Tập đỉnh là tập Fdq và tập cạnh là E = { {x, y} ∈ Fdq ×Fdq | x 6= y, Q(x− y) = t } . Bannai và đồng nghiệp [8] và Kwok [38] thu được định lí sau: Định lí 2.5.1. ([8, 38]) Cho Q là một dạng toàn phương không suy biến trên Fdq . Với t ∈ F∗q bất kì, đồ thị Eq(d, Q, t) là một( qd, (1+ o(1))qd−1, 2q(d−1)/2 ) − đồ thị. 36 Chương 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 3.1. Giới thiệu về phương pháp phổ của đồ thị Đối tượng nghiên cứu đầu tiên chúng tôi quan tâm là bài toán mở cổ điển trong hình học tổ hợp, bài toán về khoảng cách của Erdo˝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 gồm N điểm trên mặt phẳng Euclid. Có nghĩa là chúng ta cần đánh giá lực lượng cho tập khoảng cách được xác định bởi tập điểm này. Có liên quan đến đánh giá lực lượng của các tập hợp cũng được nhiều người quan tâm là đánh giá lực lượng của tập tích vô hướng, đánh giá tổng - tích, đánh giá lực lượng của tập thể tích khối, đi tìm các hàm nở... Trong mặt phẳng, bài toán khoảng cách của Erdo˝s, đánh giá tổng - tích có thể sử dụng nhiều tính chất hình học để giải quyết. Tuy nhiên, trên không gian hữu hạn nhiều tính chất hình học không còn đúng. Vì thế, không thể áp dụng phương pháp trên mặt phẳng cho không gian hữu hạn và dẫn đến nhiều phương pháp nghiên cứu được ra đời. Điển hình như phương pháp sử dụng giải tích Fourier đuợc phát triển rất mạnh mẽ bởi nhóm nghiên cứu của Iosevich. Cách tiếp cận bằng giải tích Fourier kế thừa được những công cụ mạnh từ giải tích và có lợi hơn phương pháp tiếp cận bằng đồ thị là có sử dụng các cấu trúc của bài toán trên một không gian vectơ. Ngoài ra, gần đây xuất hiện phương pháp sử dụng liên thuộc điểm và đường thẳng của Rudnev [46] để nghiên cứu một số bài toán tổ hợp cộng tính cho các tập nhỏ. Năm 2008, Vũ Hà Văn và Lê Anh Vinh đã đồng thời sử dụng (n, d, λ) - đồ 37 thị và Bổ đề trộn nở để nghiên cứu về một số bài toán tổ hợp cộng tính. Cụ thể, Vu [54] nghiên cứu về bài toán đánh giá tổng - tích và Vinh [55] nghiên cứu về bài toán khoảng cách của Erdo˝s. Trong Luận án này nhóm chúng tôi sẽ tiếp tục sử dụng (n, d, λ) - đồ thị và Bổ đề trộn nở để nghiên cứu các bài toán nêu trên. Chúng tôi gọi phương pháp này là "phương pháp phổ của đồ thị". Phương pháp phổ của đồ thị: • Bước 1: Xây dựng một (n, d, λ) - đồ thị trên không gian R chúng ta đang nghiên cứu bài toán (R = Fq hoặc Zq). – Tập đỉnh thường là V = R× R× ....× R hoặc R× × R× × ....× R×. – Hai đỉnh a, b của đồ thị được nối với nhau bởi một cạnh khi và chỉ khi f (a, b) = t, trong đó t ∈ R và f : V × V → R là một hàm số. Trong mỗi bài toán chúng ta sẽ chọn một hàm f phù hợp. • Bước 2: Tìm các tham số (n, d, λ) của đồ thị trên. • Bước 3: Áp dụng Bổ đề trộn nở: – Đếm số nghiệm của phương trình f (a, b) = t với a ∈ A, b ∈ B. – Đồng nhất số nghiệm của phương trình này với số cạnh giữa hai tập đỉnh A, B của đồ thị trên. – Sử dụng Bổ đề trộn nở để đưa ra đánh giá về số cạnh của đồ thị, tương ứng với những đánh giá cho tập hợp mà chúng ta quan tâm. Phương pháp phổ của đồ thị mặc dù có thể sử dụng để chứng minh lại và cải thiện được một số kết quả gần đây của nhiều nhà nghiên cứu và đưa ra một số kết quả khá thú vị khác nhưng lại yêu cầu rất ít cấu trúc trong bài toán. Từ quan điểm hình học, sử dụng phương pháp này chúng ta rất ít khi quan tâm đến lợi thế rằng bài toán của chúng ta có cấu trúc trên một không gian vectơ. Điều này giải thích tại sao phương pháp đó được ứng dụng vào rất nhiều bài toán khác nhau nhưng nó cũng chỉ rõ cho chúng ta thấy sự khó khăn để cải thiện các kết quả này là do sự phức tạp của hình học trên trường 38 hay vành hữu hạn. Trong chương này của Luận án, chúng tôi sẽ sử dụng phương pháp phổ của đồ thị để nghiên cứu một số bài toán đang được rất nhiều người quan tâm: tập khoảng cách, tập tích, tập thể tích khối, tập tổng - tỉ số và đi tìm các hàm nở hai biến. 3.2. Tập khoảng cách, tập tích 3.2.1. Giới thiệu tổng quan về bài toán tập khoảng cách và tập tích Sử dụng giải tích Fourier trên trường hữu hạn, Iosevich và Rudnev [34] chứng minh rằng nếu |E | ≥ 2q(n+1)/2 thì ∆(E) = Fq. Hart và Iosevich [30] đã tìm điều kiện của tập E để |∆(E)| & q. Cụ thể, họ thu được định lí sau: Định lí 3.2.1. ([30, Định lí 1.1, Hệ quả 1.2]) Với E = E1 × . . . × En, trong đó E1, . . . , En ⊂ Fq thỏa mãn |E | & q n2 2n−1 . Khi đó |∆(E)| & q. Hart, Iosevich, Koh và Rudnev [28] cũng thu được các kết quả tương tự cho tập tích trong không gian vectơ trên trường hữu hạn, được cụ thể trong định lí sau: Định lí 3.2.2. ([28, Định lí 2.5]) Với E = E1× . . .× En, trong đó E1, . . . , En ⊂ Fq thỏa mãn |E | & q n 2 2n−1 . Khi đó |Π(E)| & q. Từ Định lí 3.2.1 và Định lí 3.2.2, nếu A ⊂ Fq có lực lượng |A| & q n2n−1 thì |∆(An)|, |Π(An)| & q. Sử dụng phương pháp phổ của đồ thị, chúng tôi chỉ ra một cách chứng minh khác ngắn gọn hơn cho các kết quả trên. Cụ thể, chúng tôi [31] đã thu được kết quả sau: Định lí 3.2.3. ([31, Định lí 2.3]) Với A ⊂ Fq thỏa mãn |A| & q1/2. Khi đó, ta có: |∆F(An)| & min { q, |A|2n−1 qn−1 } . Định lí 3.2.4. ([31, Định lí 2.4]) Với A ⊂ Fq thỏa mãn |A| & q1/2. Khi đó, ta có: |ΠF(An)| & min { q, |A|2n−1 qn−1 } . 39 Covert, Iosevich và Pakianathan [16] sử dụng giải tích Fourier cũng đã thu được kết quả tương tự trên vành hữu hạn. Định lí 3.2.5. ([16, Định lí 1.3.1]) Với E ⊂ Znq thỏa mãn |E | & r(r+ 1)q (2r−1)n2r + 12r , ta có: Z×q ⊂ ∆Zq(E). Định lí 3.2.6. ([16, Định lí 1.3.2]) Với E ⊂ Znq thỏa mãn |E | & rq (2r−1)n2r + 12r , ta có: Z×q ⊂ ΠZq(E). Sử dụng phương pháp phổ của đồ thị, chúng tôi [31] đã đưa ra điều kiện của tập A ⊂ Zq để |∆Zq(An)|, |ΠZq(An)| & q. Định lí 3.2.7. ([31, Định lí 2.7]) Với A ⊂ Zq thỏa mãn |A| & q1− 12r , ta có: |∆Zq(An)| & min { q, |A|2n−1 (rq2−1/r)n−1 } . Định lí 3.2.8. ([31, Định lí 2.8]) Với A ⊂ Zq thỏa mãn |A| & q1− 12r , ta có: |ΠZq(An)| & min { q, |A|2n−1 (rq2−1/r)n−1 } . Lưu ý, từ Định lí 3.2.5 và Định lí 3.2.6, với A ⊂ Zq có lực lượng |A| & r2/nq1+ 12rn− 12r thì Z×q ⊂ ∆Zq(An) và Z×q ⊂ ΠZq(An). Từ Định lí 3.2.7 và Định lí 3.2.8, với A ⊂ Zq có lực lượng |A| & r n−12n−1 q1+ 12r(2n−1)− 12r thì |∆Zq(An)|, |ΠZq(An)| & q. 40 3.2.2. Đánh giá tập khoảng cách trên trường và vành hữu hạn Đánh giá tập khoảng cách trên trường hữu hạn Trong phần này, chúng ta sẽ chứng minh Định lí 3.2.3. Trước hết, sử dụng phương pháp phổ của đồ thị cho đồ thị tổng - bình phương, ta có bổ đề sau: Bổ đề 3.2.9. Với A, B, C ⊂ Fq, ta có:∣∣∣{a+ (b− c)2 : a ∈ A, b ∈ B, c ∈ C}∣∣∣ & min{q, |A||B||C| q } . Chứng minh. Giả sử D = { a+ (b− c)2 : a ∈ A, b ∈ B, c ∈ C} ⊂ Fq. Gọi N là số nghiệm của phương trình −d + a + (b − c)2 = 0, (a, b, c, d) ∈ A × B × C × D. Với mỗi a ∈ A, b ∈ B, c ∈ C ta có duy nhất một giá trị d ∈ D thỏa mãn phương trình trên nên N = |A||B||C|. Mặt khác, N là số cạnh giữa hai tập đỉnh (−D)× B và A× (−C) của đồ thị tổng - bình phương FSq. Từ Bổ đề 1.3.1 và Định lí 2.1.1, ta có:∣∣∣∣|A||B||C| − |A||B||C||D|q ∣∣∣∣ ≤ √2q|A||B||C||D|, tương đương với |A||B||C| ≤ |A||B||C||D| q + √ 2q|A||B||C||D|. Đặt t = √|D| ≥ 0, ta được:√|A||B||C| q t2 + √ 2qt− √ |A||B||C| ≥ 0, suy ra √ |D| ≥ − √ 2q+ √ 2q+ 4|A||B||C|/q 2 √|A||B||C|/q = 2 √|A||B||C|√ 2q+ √ 2q+ 4|A||B||C|/q & min { √ q, √ |A||B||C| q } . Bình phương hai vế suy ra điều phải chứng minh. 41 Tiếp theo chúng ta chứng minh Định lí 3.2.3 bằng phương pháp quy nạp theo n. Chứng minh. Với n = 2 tập X = {(a − b)2 : a, b ∈ A}, Y = Z = A. Do |X| ≥ |A|/2, từ Bổ đề 3.2.9 ta có: |∆F(A2)| = ∣∣∣{x+ (y− z)2 : x ∈ X, y ∈ Y, z ∈ Z}∣∣∣ & min { q, |X||Y||Z| q } & min { q, |A|3 q } . Giả sử định lí đúng với n. Chúng ta chứng minh định lí cũng đúng với n+ 1. Tập X = ∆F(An), Y = Z = A. Theo giả thiết quy nạp, ta có: |X| & min { q, |A|2n−1 qn−1 } . (3.2.1) Áp dụng Bổ đề 3.2.9 và sử dụng điều kiện (3.2.1), ta thu được: |∆F(An+1)| = ∣∣∣{x+ (y− z)2 : x ∈ X, y ∈ Y, z ∈ Z}∣∣∣ & min { q, |X||Y||Z| q } & min { q, |A|2n+1 qn } , suy ra điều cần chứng minh. Đánh giá tập khoảng cách trên vành hữu hạn Trong phần này, chúng ta sẽ chứng minh Định lí 3.2.7. Tương tự đánh giá tập khoảng cách trên trường hữu hạn, trước hết chúng ta cần chứng minh bổ đề sau: Bổ đề 3.2.10. Với A, B, C ⊂ Zq, ta có:∣∣∣{a+ (b− c)2 : a ∈ A, b ∈ B, c ∈ C}∣∣∣ & min{q, |A||B||C| rq2−1/r } . 42 Chứng minh. Giả sử D = { a+ (b− c)2 : a ∈ A, b ∈ B, c ∈ C} ⊂ Zq. Gọi N là số nghiệm của phương trình −d+ a+ (b− c)2 = 0, (a, b, c, d) ∈ A× B× C × D. Với mỗi a ∈ A, b ∈ B, c ∈ C ta có duy nhất một giá trị d ∈ D thỏa mãn phương trình trên nên N = |A||B||C|. Mặt khác, N là số cạnh giữa hai tập đỉnh (−D)× B và A× (−C) của đồ thị tổng - bình phương trên vành hữu hạn. Từ Bổ đề 1.3.1 và Định lí 2.1.2, ta có:∣∣∣∣|A||B||C| − |A||B||C||D|q ∣∣∣∣ ≤ √2rq2−1/r|A||B||C||D|, tương đương với |A||B||C| ≤ |A||B||C||D| q + √ 2rq2−1/r|A||B||C||D|. Đặt t = √|D| ≥ 0, khi đó√|A||B||C| q t2 + √ 2rq2−1/rt− √ |A||B||C| ≥ 0, từ đó ta có: √ |D| ≥ − √ 2rq2−1/r + √ 2rq2−1/r + 4|A||B||C|/q 2 √|A||B||C|/q = 2 √|A||B||C|√ 2rq2−1/r + √ 2rq2−1/r + 4|A||B||C|/q & min { √ q, √ |A||B||C| rq2−1/r } . Bình phương hai vế ta suy ra điều phải chứng minh. Tiếp theo, chúng ta chứng minh Định lí 3.2.7 bằng phương pháp quy nạp theo n. Chứng minh. Với n = 2. Tập X = {(a − b)2 : a, b ∈ A}, X′ = X ∩Z×q và Y = Z = A. Do a, b ∈ Z×q , a2 = b2 khi đó a = ±b, ta có: |X| ≥ |X′| ≥ |A− A| − |Z 0 q| 2 ≥ |A| − p r−1 2 & |A|. 43 Từ Bổ đề 3.2.10, ta có |∆Zq(A2)| = ∣∣∣{x+ (y− z)2 : x ∈ X, y ∈ Y, z ∈ Z}∣∣∣ & min { q, |X||Y||Z| rq2−1/r } & min { q, |A|3 rq2−1/r } . Giả sử định lí đúng với n. Chúng ta chứng minh cũng đúng với n + 1. Tập X = ∆Zn(A n), Y = Z = A. Theo giả thiết quy nạp, ta có: |X| & min { q, |A|2n−1 (rq2−1/r)n−1 } . (3.2.2) Áp dụng Bổ đề 3.2.10 và sử dụng điều kiện (3.2.2), ta được: |∆Zq(An+1)| = ∣∣∣{x+ (y− z)2 : x ∈ X, y ∈ Y, z ∈ Z}∣∣∣ & min { q, |X||Y||Z| rq2−1/r } & min { q, |A|2n+1 (rq2−1/r)n } , suy ra điều phải chứng minh. 3.2.3. Đánh giá tập tích trên trường và vành hữu hạn Trong phần này, chúng ta sẽ chứng minh Định lí 3.2.4 và Định lí 3.2.8. Tương tự chứng minh của đánh giá tập khoảng cách trên trường và vành hữu hạn, sử dụng phương pháp phổ của đồ thị và các Định lí 2.2.1, Định lí 2.2.3, ta có các bổ đề sau: Bổ đề 3.2.11. Với A, B,C ⊂ Fq, ta có: |{a+ bc : a ∈ A, b ∈ B, c ∈ C}| & min { q, |A||B||C| q } . Bổ đề 3.2.12. Với A, B,C ⊂ Zq, ta có: |{a+ bc : a ∈ A, b ∈ B, c ∈ C}| & min { q, |A||B||C| rq2−1/r } . Định lí 3.2.4 và Định lí 3.2.8 được suy ra từ Bổ đề 3.2.11 và Bổ đề 3.2.12 tương ứng. 44 3.3. Tập thể tích khối 3.3.1. Giới thiệu tổng quan về tập thể tích khối Cho A ⊂ Fq, tập thể tích khối Vn(A) của tập A được định nghĩa như sau: Vn(A) = (A− A) · (A− A) · · · (A− A)︸ ︷︷ ︸ n . Sử dụng giải tích Fourier, Hart, Iosevich và Solymosi [29] thu được kết quả sau: Định lí 3.3.1. ([29, Định lí 1.4]) Với A ⊂ Fq thỏa mãn |A| & q 12+ 12n , ta có: Vn(A) = Fq. Sử dụng bất đẳng thức tam giác Ruzsa, Balog [7] đã cải thiện kết quả trên. Định lí 3.3.2. ([7, Định lí 1.1]) Với A ⊂ Fq thỏa mãn |A| ≥ q 1 2+ 1 2k , trong đó k là số tự nhiên và k > 1. Khi A là một nhóm con cộng của Fq chúng ta cần thêm điều kiện |A| ≥ q 12 + 1. Khi đó, ta có: V2k+1(A) = Fq. Hệ quả 3.3.3. ([7, Hệ quả 1]) Với A ⊂ Fq thỏa mãn |A| ≥ q 12 . Nếu A là một nhóm con cộng của Fq thỏa mãn |A| ≥ q 12 + 1. Khi đó, ta có: |Vk(A)| ≥ q1− 1 2k . Sử dụng phương pháp phổ của đồ thị và Hệ quả 3.3.3, chúng tôi [32] cũng thu được kết quả về tập thể tích khối. Định lí 3.3.4. ([32, Định lí 1.4]) Với A ⊂ Fq thỏa mãn |A| & q 12 , ta có: |Vn(A)| & min q, |A|2q 12n−1  . Trong trường hợp đặc biệt, từ Định lí 3.3.4 dẫn đến nếu A ⊂ Fq thỏa mãn |A| & q 12+ 12n 45 thì |Vn(A)| & q. Với A ⊂ Zq chúng ta định nghĩa tập thể tích khối tương tự như trên trường hữu hạn. Khi sử dụng phương pháp phổ của đồ thị cho đồ thị tích - tổng trên vành hữu hạn, chúng ta cũng thu được kết quả tương tự cho tập thể tích khối trên vành hữu hạn. Cụ thể, chúng tôi [32] chứng minh được kết quả sau: Định lí 3.3.5. ([32, Định lí 1.5]) Với A ⊂ Zq thỏa mãn |A| & q1− 12r , ta có: |Vn(A)| & min pr, |A|22rpr−1+ 12n−1  . Sử dụng phương pháp phổ của đồ thị và Định lí 3.3.4, chúng tôi [32] đã cải thiện được kết quả của Định lí 3.3.2. Định lí 3.3.6. ([32, Định lí 1.6]) Với A ⊂ Fq thỏa mãn |A| & q 1 2+ 2 3 1 2k , trong đó k > 1, ta có: V2k+1(A) = Fq. Chúng tôi [32] cũng có kết quả tương tự trên vành hữu hạn. Định lí 3.3.7. ([32, Định lí 1.7]) Với A ⊂ Zq thỏa mãn |A| & √ 2rq 1− 12r+ 13/2·r2k , ta có: Z×q ⊂ V2k+1(A). 3.3.2. Một số kết quả cần dùng Để chứng minh Định lí 3.3.7, chúng ta cần một số kết quả sau: Bổ đề 3.3.8. Với A, B ⊂ Zq thỏa mãn |A||B| > q2− 1r , ta có: Z×q ⊂ A− A (B− B) \Z0q . 46 Chứng minh. Với x ∈ Z×q bất kì, xét tập A− xB ⊂ Zq . Do |A− xB| ≤ pr < |A||B| pr−1 nên tồn tại pr−1 cặp phân biệt (a1, b1), (a2, b2), . . . , (apr−1 , bpr−1) sao cho ai − xbi = aj − xbj, tương đương với x(bi − bj) = ai − aj. Nếu ai = aj thì bi = bj nên aj 6= aj với mọi i 6= j. Đặt M = {a1, a2, . . . , apr−1}. Do |M−M| > |M| = pr−1, nên tồn tại io, jo sao cho aio − ajo ∈ Z×q , suy ra x = bio−bjo aio−ajo ∈ A−A (B−B)\Z0q , dẫn tới điều phải chứng minh. Bổ đề dưới đây được gọi là Bất đẳng thức tam giác Ruzsa, đây là một kết quả rất quan trọng trong tổ hợp. Bổ đề 3.3.9. ([47]) Cho U, V, W là các tập con hữu hạn của nhóm G bất kì. Khi đó, ta có: |UV−1||W| ≤ |UW||VW|. Từ Bổ đề 3.3.8 và Bổ đề 3.3.9 chúng ta thu được được kết quả sau trên vành hữu hạn: Bổ đề 3.3.10. Với A ⊂ Zq thỏa mãn |A| ≥ q1− 12r . Khi đó, ta có: |Vn(A)| & q1− 1r2n . Chứng minh. ĐặtU = V = (A− A) \Z0q vàW = Vn. Áp dụng Bổ đề 3.3.9 với G = Zq ta được: |UV−1||Vn| ≤ |Vn+1|2. Từ Bổ đề 3.3.8, nếu |A| > pr− 12 thì Z×q ⊂ A−A(A−A)\Z0q . Vì Z × q là tập các phần tử khả nghịch của Zq nên suy ra Z×q ⊂ (A−A)\Z0q (A−A)\Z0q . Từ đó, ta có |UV −1| ≥ pr − pr−1, kéo theo (pr − pr−1)|Vn| ≤ |Vn+1|2. Sử dụng phương pháp quy nạp ta thu được: (pr − pr−1)2n−1|V| ≤ |Vn+1|2n . Mặt khác, dễ thấy |V| = |(A− A) \Z0q| > pr− 1 2 − pr−1, vì thế |Vn(A)| ≥ |Vn| & q1− 1r2n , ta có điều phải chứng minh. 47 Sử dụng phương pháp phổ của đồ thị, ta có bổ đề sau: Bổ đề 3.3.11. Với A, B ⊂ F∗q và C, D ⊂ Fq thỏa mãn |A||B||C||D| ≥ 3q3. Khi đó, ta có: AB(C− D) = Fq. Chứng minh. Đặt H = {(a, b, c, d) ∈ A × B × C × D : ab(c − d) = λ}, với λ ∈ F∗q bất kì. Ngoài ra, |H| là số cạnh giữa hai tập đỉnh A× C và B× D của đồ thị tích - tổng PSq(λ). Từ Bổ đề 1.3.1 và Định lí 2.3.1, ta có:∣∣∣∣|H| − |A||B||C||D|q ∣∣∣∣ ≤ √3q|A||B||C||D|, tương đương với |H| ≥ |A||B||C||D| q − √ 3q|A||B||C||D|. Nếu |A||B||C||D| > 3q3 khi đó |H| > 0, từ đó suy ra AB(C− D) = Fq, đây là điều phải chứng minh. Tương tự, chúng ta cũng chứng minh được bổ đề sau trên vành hữu hạn: Bổ đề 3.3.12. Với A, B ⊂ Z×q và C, D ⊂ Zq thỏa mãn |A||B||C||D| ≥ 2rq4− 1 r . Khi đó, ta có: Z×q ⊂ AB(C− D). Chứng minh. Đặt H = {(a, b, c, d) ∈ A × B × C × D : ab(c − d) = λ}, với λ ∈ Z×q bất kì. Ngoài ra, |H| là số cạnh giữa hai tập đỉnh A× C và B× D của đồ thị tích - tổng PSRq. Từ Bổ đề 1.3.1 và Định lí 2.3.2, ta có:∣∣∣∣|H| − |A||B||C||D|pr ∣∣∣∣ ≤ √2rp2r−1|A||B||C||D|, tương đương với |H| ≥ |A||B||C||D| pr − √ 2rp2r−1|A||B||C||D|. Nếu |A||B||C||D| > 2rp4r−1, khi đó |H| > 0, từ đó suy ra Z×q ⊂ AB(C− D), điều phải chứng minh. 48 3.3.3. Đánh giá tập thể tích khối trên trường hữu hạn Trong phần này, chúng ta sẽ chứng minh Định lí 3.3.4 và Định lí 3.3.6 bằng phương pháp phổ của đồ thị. Trước hết, ta sẽ chứng minh Định lí 3.3.4. Chứng minh. Với A ⊂ F∗q và B, C ⊂ Fq, ta đặt D = {a(b− c) : a ∈ A, b ∈ B, c ∈ C} ∩F∗q . Giả sử N là số nghiệm của phương trình ad(b− c) = 1, (a, b, c, d) ∈ A× B× C × D−1. Với mỗi a ∈ A, b ∈ B, c ∈ C và b 6= c thì có duy nhất một d ∈ D thỏa mãn phương trình ad(b− c) = 1 nên N = |A||B||C| − |A||B ∩ C|. Mặt khác, N là số cạnh giữa hai tập đỉnh A× B và D−1 × (−C) của đồ thị tích - tổng PSq. Từ Bổ đề 1.3.1 và Định lí 2.3.1, ta có:∣∣∣∣|A||B||C| − |A||B ∩ C| − |A||B||C||D|q ∣∣∣∣ ≤ √3q|A||B||C||D|, tương đương với |A||B||C| − |A||B ∩ C| ≤ |A||B||C||D| q + √ 3q|A||B||C||D|. Đặt t = √|D| ≥ 0, ta được:√|A||B||C| q t2 + √ 3q t− √ |A||B||C|+ √ |A| |B||C| |B ∩ C| ≥ 0, suy ra √ |D| ≥ − √ 3q+ √