Tổng quan luận án

Luận án tiến sĩ toán học "Phương pháp phổ của đồ thị trong một số bài toán tổ hợp cộng tính" của nghiên cứu sinh Đỗ Duy Hiếu, thực hiện dưới sự hướng dẫn khoa học của PGS. Lê Anh Vinh tại Viện Toán học – Viện Hàn lâm Khoa học và Công nghệ Việt Nam (chuyên ngành Cơ sở toán học cho tin học, mã số 9.10, bảo vệ năm 2019), tập trung nghiên cứu ứng dụng của lý thuyết phổ đồ thị vào việc ước lượng lực lượng của các tập hợp cấu trúc trong không gian vectơ trên trường hữu hạn $\mathbb{F}_q$ và vành hữu hạn $\mathbb{Z}_q$.

Tính cấp thiết và khoảng trống nghiên cứu

Trong những năm gần đây, tổ hợp đã có nhiều bước phát triển và được ứng dụng mạnh mẽ vào khoa học máy tính, vật lý, hóa học. Khi mở rộng các bài toán hình học tổ hợp và tổ hợp cộng tính từ không gian Euclid liên tục $\mathbb{R}^n$ sang không gian rời rạc trên trường hữu hạn $\mathbb{F}_q^n$ hoặc vành hữu hạn $\mathbb{Z}_q^n$, các công cụ hình học giải tích cổ điển không còn áp dụng được trực tiếp do tính chất topo và hình học vi phân biến mất.

Để giải quyết các bài toán này trên không gian hữu hạn, các công cụ như giải tích Fourier (phát triển bởi nhóm nghiên cứu của Iosevich) hoặc phương pháp liên thuộc điểm - đường thẳng (Rudnev) đã được sử dụng. Tuy nhiên, giải tích Fourier đòi hỏi cấu trúc không gian phức tạp và các biến đổi giải tích tương đối cồng kềnh. Khoảng trống nghiên cứu đặt ra là xây dựng một tiếp cận đại số rời rạc thuần túy, có tính chất tổ hợp rõ nét, sử dụng phương pháp phổ của $(n, d, \lambda)$-đồ thị và Bổ đề trộn nở (Expander Mixing Lemma) nhằm đưa ra các chứng minh ngắn gọn hơn, cải thiện các cận số mũ đã có trên trường hữu hạn $\mathbb{F}_q$, đồng thời mở rộng việc giải quyết các bài toán tương ứng trên vành hữu hạn $\mathbb{Z}_q$ (nơi xuất hiện các ước của 0 gây phức tạp cho phép tính đại số).

Mục tiêu và các bài toán nghiên cứu cụ thể

Mục tiêu chính của luận án là ứng dụng phương pháp phổ của đồ thị để khảo sát và đưa ra các đánh giá định lượng về lực lượng của các tập hợp cấu trúc trên không gian vectơ thuộc trường hữu hạn và vành hữu hạn. Các bài toán cụ thể được tác giả giải quyết bao gồm:

  1. Bài toán tập khoảng cách $\Delta(E)$ và tập tích $\Pi(E)$: Đánh giá chặn dưới lực lượng của tập khoảng cách và tập tích vô hướng sinh bởi tập điểm $E$, đặc biệt với các tập tích Descartes $E = A^n$ trên $\mathbb{F}_q^n$ và $\mathbb{Z}_q^n$.
  2. Bài toán tập thể tích khối $V_n(A)$: Đánh giá lực lượng của tập tích các hiệu $V_n(A) = (A - A) \cdot (A - A) \cdots (A - A)$ ($n$ lần) và tìm điều kiện của tập $A$ để tập thể tích khối phủ kín toàn bộ trường hữu hạn ($V_n(A) = \mathbb{F}_q$) hoặc phủ kín tập khả nghịch của vành hữu hạn ($\mathbb{Z}_q^\times \subset V_n(A)$).
  3. Bài toán tập tổng - tỉ số: Đánh giá chặn dưới lực lượng cho các tập cấu trúc tổng và tỉ số trên trường hữu hạn và vành hữu hạn.
  4. Bài toán hàm nở hai biến: Chứng minh tính chất nở của các hàm hai biến $f(x, y) = x(y + 1)$ và $g(x, y) = x + y^2$ trên $\mathbb{F}_q$ và $\mathbb{Z}_q$ khi tập $A$ có kích thước $|A| \gtrsim q^{1/2}$.
  5. Bài toán tập khoảng cách trên đa tạp chính quy: Sử dụng Bổ đề trộn nở mở rộng cho đồ thị có hướng để nghiên cứu tập khoảng cách tổng quát $\Delta_{k, D}(E)$ của tập con $E$ nằm trên một đa tạp chính quy với dạng toàn phương không suy biến và đa thức chéo $P(x) = \sum_{j=1}^d a_j x_j^s$.

Đối tượng và phạm vi nghiên cứu

  • Đối tượng nghiên cứu: Các $(n, d, \lambda)$-đồ thị vô hướng và có hướng (đồ thị tổng - bình phương, đồ thị tổng - tích, đồ thị tích - tổng, đồ thị tích, đồ thị Euclid hữu hạn), ma trận kề, phổ của đồ thị, các tập hợp điểm và cấu trúc tổ hợp cộng tính ($\Delta(E)$, $\Pi(E)$, $V_n(A)$, hàm nở hai biến).
  • Phạm vi nghiên cứu: Không gian vectơ $\mathbb{F}_q^n$ trên trường hữu hạn $\mathbb{F}_q$ ($q = p^r$ với $p$ là số nguyên tố lẻ, $r \ge 1$) và không gian vectơ $\mathbb{Z}_q^n$ trên vành hữu hạn $\mathbb{Z}_q = \mathbb{Z}/p^r\mathbb{Z}$ ($r \ge 2$, $p$ nguyên tố lẻ).

Tổng quan tài liệu và vị trí của luận án

Luận án đã tổng hợp và điểm lại hệ thống các công trình nghiên cứu tiền đề trong hình học tổ hợp và tổ hợp cộng tính:

Các hướng nghiên cứu trước đây

  • Bài toán khoảng cách của Erdős và phiên bản trường hữu hạn: Erdős (1946) [20] đặt bài toán tìm số khoảng cách tối thiểu $g(N)$ xác định bởi $N$ điểm trên mặt phẳng Euclid, dự đoán $g(N) \gtrsim N/\sqrt{\log N}$ và chứng minh $g(N) \gtrsim N^{1/2}$. Năm 2010, Guth và Katz [26] đã chứng minh được kết quả gần tối ưu $g(N) \gtrsim N/\log N$. Trên trường hữu hạn $\mathbb{F}_q^2$, Bourgain, Katz và Tao (2004) [12] đưa ra kết quả không hiển nhiên đầu tiên ($|E|^{1/2+c}$). Iosevich và Rudnev (2007) [34] sử dụng giải tích Fourier đưa ra kết quả định lượng tổng quát trên $\mathbb{F}_q^d$. Vũ Hà Văn (2008) [54] dùng phổ đồ thị có hướng nghiên cứu đánh giá tổng - tích và đưa ra chứng minh khác cho kết quả của Iosevich – Rudnev. Lê Anh Vinh (2008, 2011) [55, 59] độc lập dùng phổ đồ thị nghiên cứu bài toán khoảng cách và đồ thị Euclid/phi Euclid trên trường hữu hạn. Trên vành hữu hạn $\mathbb{Z}_q$, Covert, Iosevich và Pakianathan (2011) [16] dùng Fourier nghiên cứu điều kiện để tập khoảng cách và tập tích chứa toàn bộ các phần tử khả nghịch $\mathbb{Z}_q^\times$.
  • Bài toán tập thể tích khối: Hart, Iosevich và Solymosi (2007) [29] dùng Fourier chứng minh với $A \subset \mathbb{F}_q$ thỏa mãn $|A| \ge C q^{1/2 + 1/2n}$ thì tích $n$ hiệu phủ kín $\mathbb{F}q$. Balog (2012) [7] dùng bất đẳng thức tam giác Ruzsa cải thiện điều kiện cho số lẻ các hiệu: với $|A| \ge q^{1/2 + 1/(2 \cdot 2^k)}$ thì $V{2k+1}(A) = \mathbb{F}_q$.
  • Bài toán tổng - tích và tổng - tỉ số: Erdős và Szemerédi (1983) [19] chứng minh $\max(|A+A|, |A \cdot A|) \gtrsim |A|^{1+\varepsilon}$ trên $\mathbb{N}$ và đưa ra giả thuyết chặn dưới $|A|^{2-\delta}$. Kết quả này được mở rộng bởi Elekes (1997) [22], Mockenhaupt (2000) [37], Nathanson (2000) [40], Roche-Newton (2011) [41], và Solymosi (2009) [51] với cận $|A|^{4/3-\varepsilon}$ (cũng đúng trên $\mathbb{C}$). Trên trường hữu hạn, các kết quả ban đầu của Bourgain, Katz, Tao [12], Bourgain, Glibichuk, Konyagin [11], Bukh, Tsimerman [14] đã xác lập mối liên hệ này. Roche-Newton, Rudnev, Shkredov (2016) [44] đạt kết quả $|A|^{1+1/5}$ với $|A| \le p^{5/8}$. Roche-Newton (2015) [43] thu được kết quả cho tập tổng - tỉ số.
  • Hàm nở: Bourgain (2005) [13], Hart và Iosevich (2007, 2008) [28, 30], Sárközy (2008) [48, 49], Shparlinski (2008) [50], Glibichuk và Konyagin (2007) [24], Wigderson (2006) [9] khảo sát các dạng hàm nở đa biến. Garaev và Shen (2010) [23] cùng Timothy, Jones, Roche-Newton (2013) [52] chứng minh $f(x, y) = x(y+1)$ là hàm nở hai biến. Vinh, Thang, De Zeeuw (2017) [53] và Aksoy-Yazici et al. (2017) [1] nghiên cứu hàm nở ba biến.
  • Khoảng cách trên đa tạp chính quy: Iosevich và Rudnev (2007) [34], Covert, Koh, Pi (2017) [18] dùng Fourier nghiên cứu tập khoảng cách $\Delta_{k, D}(E)$ trên mặt cầu đơn vị và các đa tạp chính quy.

Khoảng trống luận án giải quyết

Luận án định vị việc sử dụng phương pháp phổ đồ thị ((n, d, \lambda)-đồ thị kết hợp Bổ đề trộn nở) như một công cụ đại số nhất quán để:

  1. Đưa ra chứng minh ngắn gọn hơn cho các đánh giá tập khoảng cách và tập tích trên trường hữu hạn so với giải tích Fourier của Hart và Iosevich.
  2. Cải thiện số mũ kích thước tập hợp của Balog [7] đối với bài toán thể tích khối trên trường hữu hạn từ số mũ $1/2 + 1/(2 \cdot 2^k)$ thành $1/2 + 1/(3 \cdot 2^k)$.
  3. Mở rộng đồng bộ các kết quả từ trường hữu hạn $\mathbb{F}_q$ sang vành hữu hạn $\mathbb{Z}_q = \mathbb{Z}/p^r\mathbb{Z}$, thiết lập các điều kiện tường minh để các tập khoảng cách, tập tích, tập thể tích khối và ảnh hàm nở chứa các phần tử khả nghịch $\mathbb{Z}_q^\times$.

Cơ sở lý thuyết và phương pháp nghiên cứu

Cơ sở lý thuyết và khái niệm sử dụng

  1. Phổ của đồ thị: Cho đơn đồ thị vô hướng $G = (V, E)$ có ma trận kề đối xứng $A = (a_{ij}){n \times n}$ ($a{ij} = 1$ nếu ${i, j} \in E$, $0$ nếu ngược lại). Phổ của đồ thị là tập các giá trị riêng thực $\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_n$ của $A$. Đại lượng $\lambda(G) = \max{\lambda_2, |\lambda_n|}$ là giá trị riêng thứ hai.
  2. $(n, d, \lambda)$-đồ thị vô hướng: Đồ thị $d$-chính quy gồm $n$ đỉnh có giá trị riêng thứ hai thỏa mãn $\lambda(G) \le \lambda$. Khi $\lambda \ll d$, đồ thị có tính chất phân bố cạnh tương tự đồ thị ngẫu nhiên $G(n, d/n)$.
  3. $(n, d, \lambda)$-đồ thị có hướng chuẩn tắc: Đồ thị có hướng $G = (V, E)$ có bậc vào và bậc ra đều bằng $d$ ($|N^+(x)| = |N^-(x)| = d$), ma trận kề $A_G$ thỏa mãn tính chuẩn tắc $A_G^t A_G = A_G A_G^t$ (tương đương $|N^+(x, y)| = |N^-(x, y)|$ với mọi cặp đỉnh $x, y$), và giá trị riêng thứ hai $\lambda(G) = \max_{|\lambda_i| \neq d} |\lambda_i| \le \lambda$.
  4. Bổ đề trộn nở (Expander Mixing Lemma):
    • Dạng vô hướng chuẩn (Alon – Chung): Với $S, T \subset V$, số cạnh nối giữa $S$ và $T$ thỏa mãn: $$\left| E(S, T) - \frac{d|S||T|}{n} \right| \le \lambda \sqrt{|S||T|}$$
    • Dạng vô hướng cho đa tập đỉnh (Hanson, Lund, Roche-Newton [27], Bổ đề 1.1): Với hai đa tập đỉnh $B, C$, $$\left| E(B, C) - \frac{d|B||C|}{n} \right| \le \lambda \sqrt{\sum_{b \in B} m_B(b)^2 \sum_{c \in C} m_C(c)^2}$$
    • Dạng có hướng (Vu [54], Bổ đề 1.2): Cho $(n, d, \lambda)$-đồ thị có hướng, với $B, C \subset V$: $$\left| E(B, C) - \frac{d|B||C|}{n} \right| \le \lambda \sqrt{|B||C|}$$
    • Dạng có hướng cho đa tập đỉnh (Bổ đề 1.3 của luận án): $$\left| E(B, C) - \frac{d|B||C|}{n} \right| \le \lambda \sqrt{\sum_{b \in B} m_B(b)^2 \sum_{c \in C} m_C(c)^2}$$
  5. Bất đẳng thức tam giác Ruzsa: Cho các tập con hữu hạn $U, V, W$ trong một nhóm $G$, ta có $|U V^{-1}||W| \le |UW||VW|$.

Khung phương pháp nghiên cứu (Phương pháp phổ của đồ thị)

Luận án thực hiện quy trình nghiên cứu 3 bước quy chuẩn:

  • Bước 1: Xây dựng đồ thị đại số. Thiết lập đồ thị $G = (V, E)$ trên không gian $\mathbb{F}_q^d$ hoặc $\mathbb{Z}_q^d$ với tập đỉnh $V = R \times \dots \times R$. Hai đỉnh $a, b$ được nối với nhau bởi một cạnh khi và chỉ khi phương trình đại số $f(a, b) = t$ được thỏa mãn ($t \in R$).
  • Bước 2: Xác định các tham số phổ $(n, d, \lambda)$. Đếm số nghiệm chung của hệ phương trình $f(a, x) = t$ và $f(b, x) = t$ để biểu diễn đại số bình phương ma trận kề $A^2 = h(A) = J + \alpha I + \sum \beta_k E_k$. Từ tính chất của ma trận đối xứng và tính chính quy, xác định chặn trên chính xác cho giá trị riêng thứ hai $\lambda$.
  • Bước 3: Đánh giá lực lượng thông qua Bổ đề trộn nở. Biểu diễn số nghiệm của phương trình đại số cần khảo sát tương ứng với số cạnh $E(S, T)$ giữa hai tập đỉnh trong đồ thị. Áp dụng Bổ đề trộn nở để chặn $E(S, T)$, từ đó suy ra các bất đẳng thức đại số nhằm giải ra chặn dưới cho lực lượng của tập hợp cần đánh giá.

Nội dung chính theo từng chương

Chương 1: Kiến thức chuẩn bị

Chương 1 hệ thống hóa các khái niệm nền tảng của đại số tuyến tính trong lý thuyết đồ thị:

  • Trình bày định nghĩa ma trận kề $A$, phổ của ma trận kề, đa thức đặc trưng $\det(A - xI)$, và tính chất của đồ thị đẳng cấu (hai đồ thị đẳng cấu có cùng phổ, nhưng hai đồ thị đồng phổ như $K_{1,4}$ và $C_4 \cup K_1$ chưa chắc đẳng cấu).
  • Phân tích chi tiết phổ của đồ thị đầy đủ $K_n$: ma trận kề $A = J - I$, có giá trị riêng $\lambda_1 = n - 1$ (bội 1) ứng với vectơ riêng toàn 1 ($\mathbf{1}$), và giá trị riêng $\theta = -1$ (bội $n - 1$).
  • Thiết lập định nghĩa $(n, d, \lambda)$-đồ thị vô hướng và trình bày chứng minh chặt chẽ Bổ đề trộn nở bằng cách phân tích vectơ đặc trưng $\chi_S, \chi_T$ theo cơ sở trực chuẩn các vectơ riêng của $A$ và áp dụng bất đẳng thức Cauchy – Schwarz.
  • Trình bày mở rộng Bổ đề trộn nở cho đa tập đỉnh (Bổ đề 1.1).
  • Trình bày lý thuyết về đồ thị có hướng chính quy chuẩn tắc ($|N^+(x, y)| = |N^-(x, y)|$, $A_G^t A_G = A_G A_G^t$), chứng minh Bổ đề trộn nở cho đồ thị có hướng (Bổ đề 1.2 theo Vu [54]) và mở rộng cho đa tập đỉnh trong đồ thị có hướng (Bổ đề 1.3).

Chương 2: Một số (n, d, λ) - đồ thị

Chương 2 tập trung xây dựng và tính toán tường minh các tham số phổ của 5 họ đồ thị đại số trên trường hữu hạn $\mathbb{F}_q$ và vành hữu hạn $\mathbb{Z}_q$ ($q = p^r$).

Tên đồ thị Không gian / Ký hiệu Định nghĩa cạnh $E(G)$ Số đỉnh ($n$) Bậc ($d$) Chặn giá trị riêng thứ hai ($\lambda$)
Tổng - bình phương Trường $\mathbb{F}_q$ ($FS_q$) $a_1 + b_1 + (a_2 - b_2)^2 = 0$ $q^2$ $q$ $\sqrt{2q}$
Tổng - bình phương Vành $\mathbb{Z}_q$ ($RS_q$) $a_1 + b_1 + (a_2 - b_2)^2 = 0$, $a_2, b_2 \in \mathbb{Z}_q^\times$ $p^{2r} - p^{2r-1}$ $p^r - p^{r-1}$ $\sqrt{(2r - 1)p^{2r-1}}$
Tổng - tích Trường $\mathbb{F}_q$ ($FP_q(\lambda)$) $a_1 + b_1 + a_2 b_2 = \lambda$ $q^2$ $q$ $\sqrt{2q}$
Tổng - tích Trường $\mathbb{F}q^{d+1}$ ($\mathbb{F}{q, d}$) $a + c = b \cdot d$ ($b, d \in \mathbb{F}_q^d$) $q^{d+1}$ $q^d$ $q^{d/2}$
Tổng - tích Vành $\mathbb{Z}_q$ ($RP_q$) $a_1 + b_1 = a_2 b_2$ $p^{2r}$ $p^r$ $\sqrt{2r p^{2r-1}}$
Tổng - tích Vành $\mathbb{Z}q^{d+1}$ ($R{q, d}$) $a + c = b \cdot d$ ($b, d \in \mathbb{Z}_q^d$) $q^{d+1}$ $q^d$ $\sqrt{2r p^{(2r-1)d}}$
Tích - tổng Trường $\mathbb{F}_q$ ($PS_q(\lambda)$) $a_1 b_1 (a_2 + b_2) = \lambda$ $q(q - 1)$ $q$ $\sqrt{3q}$
Tích - tổng Vành $\mathbb{Z}_q$ ($PSR_q$) $(a_1 + b_1)(a_2 + b_2) = 1$, $a_1, b_1 \in \mathbb{Z}_q^\times$ $p^{2r} - p^{2r-1}$ $p^r - p^{r-1}$ $\sqrt{(2r - 1)p^{2r-1}}$
Tích Trường $\mathbb{F}q^d$ ($B{q, d}(\lambda)$) $B(a, b) = \lambda$ ($\lambda \in \mathbb{F}_q^*$) $q^d - 1$ $q^{d-1}$ $\sqrt{2q^{d-1}}$
Tích Vành $\mathbb{Z}_q^d$ ($B_q(d, \lambda)$) $a \cdot b = \lambda$ ($\lambda \in \mathbb{Z}_q^\times$) $p^{rd} - p^{(r-1)d}$ $p^{r(d-1)}$ $\sqrt{2r p^{(d-1)(2r-1)}}$
Euclid hữu hạn Trường $\mathbb{F}_q^d$ ($E_q(d, Q, t)$) $Q(x - y) = t$ ($t \in \mathbb{F}_q^*$) $q^d$ $(1 + o(1))q^{d-1}$ $2q^{(d-1)/2}$

Kỹ thuật tính toán tiêu biểu: Với đồ thị tổng - bình phương $FS_q$, hệ phương trình $a_1 + x_1 + (a_2 - x_2)^2 = 0$ và $b_1 + x_1 + (b_2 - x_2)^2 = 0$ có nghiệm duy nhất khi $a_2 \neq b_2$ và vô nghiệm khi $a_2 = b_2$. Từ đó ma trận kề $M$ thỏa mãn $M^2 = J + (q - 1)I - E$ (với $E$ là ma trận kề của đồ thị $(q-1)$-chính quy $S_E$ xác định bởi $a_2 = b_2$). Nhờ tính chất $v_\theta \perp \mathbf{1} \Rightarrow Jv_\theta = 0$, ta thu được $\theta^2 \le 2(q - 1) < 2q$, chứng minh $\lambda(FS_q) \le \sqrt{2q}$.

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

Chương 3 áp dụng các đồ thị xây dựng từ Chương 2 vào 4 bài toán tổ hợp cộng tính:

1. Đánh giá tập khoảng cách và tập tích

  • Trên trường hữu hạn $\mathbb{F}_q$:
    • Bổ đề 3.9: Với $A, B, C \subset \mathbb{F}_q$, lực lượng tập ${a + (b - c)^2 : a \in A, b \in B, c \in C} \gtrsim \min\left(q, \frac{|A||B||C|}{q}\right)$.
    • Định lý 3.3 & 3.4: Với $A \subset \mathbb{F}q$ thỏa mãn $|A| \gtrsim q^{1/2}$, bằng phương pháp quy nạp theo số chiều $n$, ta có: $$|\Delta{\mathbb{F}}(A^n)| \gtrsim \min\left(q, \frac{|A|^{2n-1}}{q^{n-1}}\right), \quad |\Pi_{\mathbb{F}}(A^n)| \gtrsim \min\left(q, \frac{|A|^{2n-1}}{q^{n-1}}\right)$$ Hệ quả: Khi $|A| \gtrsim q^{\frac{n}{2n-1}}$ thì $|\Delta_{\mathbb{F}}(A^n)| \gtrsim q$ và $|\Pi_{\mathbb{F}}(A^n)| \gtrsim q$.
  • Trên vành hữu hạn $\mathbb{Z}_q$ ($q = p^r$):
    • Bổ đề 3.10: Lực lượng tập ${a + (b - c)^2 : a \in A, b \in B, c \in C} \gtrsim \min\left(q, \frac{|A||B||C|}{r q^{2 - 1/r}}\right)$.
    • Định lý 3.7 & 3.8: Với $A \subset \mathbb{Z}q$ thỏa mãn $|A| \gtrsim q^{1 - \frac{1}{2r}}$, quy nạp theo $n$ cho: $$|\Delta{\mathbb{Z}q}(A^n)| \gtrsim \min\left(q, \frac{|A|^{2n-1}}{(r q^{2 - 1/r})^{n-1}}\right), \quad |\Pi{\mathbb{Z}q}(A^n)| \gtrsim \min\left(q, \frac{|A|^{2n-1}}{(r q^{2 - 1/r})^{n-1}}\right)$$ Hệ quả: Khi $|A| \gtrsim r^{\frac{n-1}{2n-1}} q^{1 + \frac{1}{2r(2n-1)} - \frac{1}{2r}}$ thì $|\Delta{\mathbb{Z}q}(A^n)| \gtrsim q$ và $|\Pi{\mathbb{Z}_q}(A^n)| \gtrsim q$.

2. Đánh giá tập thể tích khối $V_n(A)$

Tập thể tích khối được định nghĩa là $V_n(A) = (A - A) \cdot (A - A) \cdots (A - A)$ ($n$ lần).

  • Bổ đề 3.11: Với $A, B \subset \mathbb{F}_q^*$ và $C, D \subset \mathbb{F}_q$ thỏa mãn $|A||B||C||D| \ge 3q^3$, áp dụng Bổ đề trộn nở cho đồ thị tích - tổng $PS_q(\lambda)$, ta có $AB(C - D) = \mathbb{F}_q$.
  • Bổ đề 3.12: Tương tự trên vành hữu hạn, nếu $|A||B||C||D| \ge 2r q^{4 - 1/r}$ ($A, B \subset \mathbb{Z}_q^\times$) thì $\mathbb{Z}_q^\times \subset AB(C - D)$.
  • Bổ đề 3.10 (Bất đẳng thức kiểu Ruzsa trên vành): Với $A \subset \mathbb{Z}_q$ có $|A| \ge q^{1 - \frac{1}{2r}}$, ta có $|V_n(A)| \gtrsim q^{1 - \frac{1}{r 2^n}}$.
  • Định lý 3.4 & 3.5: Luận án chứng minh $|V_n(A)| \gtrsim \min\left(q, \frac{|A|^2}{q^{1/2^{n-1}}}\right)$ trên trường $\mathbb{F}_q$, và $|V_n(A)| \gtrsim \min\left(p^r, \frac{|A|^2}{2r p^{r - 1 + 1/2^{n-1}}}\right)$ trên vành $\mathbb{Z}_q$.
  • Cải thiện kết quả của Balog (Định lý 3.6 & 3.7):
    • Trên trường hữu hạn $\mathbb{F}_q$: Với $k > 1$, nếu $A \subset \mathbb{F}q$ thỏa mãn $|A| \gtrsim q^{\frac{1}{2} + \frac{1}{3 \cdot 2^k}}$ thì $V{2k+1}(A) = \mathbb{F}_q$ (kết quả của Balog [7] trước đó yêu cầu $|A| \ge q^{1/2 + 1/(2 \cdot 2^k)}$).
    • Trên vành hữu hạn $\mathbb{Z}_q$: Nếu $A \subset \mathbb{Z}_q$ thỏa mãn $|A| \gtrsim \sqrt{2r} q^{\frac{1}{2} + \frac{1 - 1/2r}{(3/2) \cdot r 2^k}}$ thì $\mathbb{Z}q^\times \subset V{2k+1}(A)$.

3. Đánh giá tập tổng - tỉ số

Sử dụng phổ của các đồ thị liên quan, luận án thiết lập các đánh giá chặn dưới tổng quát cho tập tổng - tỉ số trên cả trường hữu hạn $\mathbb{F}_q$ và vành hữu hạn $\mathbb{Z}_q$.

4. Hàm nở hai biến

Luận án chứng minh rằng hai hàm $f(x, y) = x(y + 1)$ và $g(x, y) = x + y^2$ là các hàm nở hai biến trên cả trường hữu hạn $\mathbb{F}_q$ và vành hữu hạn $\mathbb{Z}_q$ với mọi tập con $A$ thỏa mãn điều kiện kích thước $|A| \gtrsim q^{1/2}$.

Chương 4: Tập khoảng cách trên đa tạp chính quy

Chương 4 mở rộng việc sử dụng phương pháp phổ đồ thị cho bài toán khoảng cách của tập con $E$ nằm trên một đa tạp chính quy $V \subset \mathbb{F}_q^d$:

  • Thay thế Bổ đề trộn nở thông thường bằng Bổ đề trộn nở mở rộng cho đồ thị có hướng (Vu [54], Hanson – Lund – Roche-Newton [27]).
  • Khảo sát tập khoảng cách tổng quát $\Delta_{k, D}(E) = {D(x_1 + \dots + x_k) : x_i \in E, 1 \le i \le k}$.
  • Thiết lập điều kiện về kích thước của tập $E \subset V$ để $\Delta_{k, D}(E) = \mathbb{F}q$ hoặc $|\Delta{k, D}(E)| \gtrsim q$ trong hai trường hợp:
    1. Hàm khoảng cách được thay bằng dạng toàn phương không suy biến tổng quát.
    2. Hàm khoảng cách được thay bằng đa thức chéo $P(x) = \sum_{j=1}^d a_j x_j^s \in \mathbb{F}_q[x_1, \dots, x_d]$ ($s \ge 2, a_j \neq 0$).

Kết quả và những đóng góp mới

Đóng góp về mặt lý luận và phương pháp

  1. Hoàn thiện khung phương pháp phổ đồ thị trong tổ hợp cộng tính: Luận án hệ thống hóa và chứng minh tính hiệu quả của phương pháp phổ đồ thị $((n, d, \lambda)$-đồ thị và Bổ đề trộn nở) như một phương pháp độc lập, đưa ra các chứng minh thuần túy đại số rời rạc, ngắn gọn hơn đáng kể so với phương pháp giải tích Fourier truyền thống của Hart, Iosevich, Pakianathan.
  2. Kỹ thuật phổ đồ thị đại số: Xây dựng thành công 5 lớp đồ thị đại số ($FS_q, RS_q, FP_q, RP_q, PS_q, PSR_q, B_{q,d}, B_q, E_q$) và tính toán tường minh các chặn giá trị riêng thứ hai $\lambda$ thông qua phương pháp ma trận kề $A^2 = h(A)$.
  3. Mở rộng Bổ đề trộn nở cho đa tập đỉnh và đồ thị có hướng: Chứng minh và ứng dụng thành công Bổ đề trộn nở mở rộng cho đa tập đỉnh trên đồ thị có hướng để xử lý các bài toán trên đa tạp chính quy.

Đóng góp cụ thể về mặt kết quả toán học

  1. Cải thiện kết quả của Balog về tập thể tích khối trên trường hữu hạn $\mathbb{F}_q$: Chứng minh được rằng điều kiện kích thước tập hợp để tích của $2k+1$ hiệu phủ kín $\mathbb{F}q$ ($V{2k+1}(A) = \mathbb{F}_q$) giảm từ $|A| \ge q^{1/2 + 1/(2 \cdot 2^k)}$ (của Balog [7]) xuống còn $|A| \gtrsim q^{1/2 + 1/(3 \cdot 2^k)}$.
  2. Mở rộng đồng bộ sang vành hữu hạn $\mathbb{Z}_q$: Đưa ra các đánh giá định lượng đầu tiên bằng phương pháp phổ đồ thị cho tập khoảng cách $\Delta_{\mathbb{Z}q}(A^n)$, tập tích $\Pi{\mathbb{Z}_q}(A^n)$, tập thể tích khối $V_n(A)$, và tập tổng - tỉ số trên vành $\mathbb{Z}_q = \mathbb{Z}/p^r\mathbb{Z}$, xác định tường minh điều kiện để các tập này chứa toàn bộ nhóm phần tử khả nghịch $\mathbb{Z}_q^\times$.
  3. Mở rộng hàm nở hai biến: Chứng minh $f(x, y) = x(y+1)$ và $g(x, y) = x + y^2$ là các hàm nở trên cả trường $\mathbb{F}_q$ và vành $\mathbb{Z}_q$ khi $|A| \gtrsim q^{1/2}$.
  4. Tổng quát hóa bài toán khoảng cách trên đa tạp chính quy: Mở rộng kết quả của Covert, Koh, Pi [18] từ dạng Euclid thông thường sang dạng toàn phương không suy biến bất kỳ và đa thức chéo bậc cao $P(x) = \sum_{j=1}^d a_j x_j^s$.

Hạn chế và hướng nghiên cứu tiếp

Hạn chế

  • Yêu cầu ít cấu trúc không gian: Phương pháp phổ đồ thị chỉ khai thác các tham số bậc và phổ của đồ thị mà ít tận dụng cấu trúc hình học chi tiết của không gian vectơ. Do đó, phương pháp gặp rào cản khi muốn tối ưu hóa sâu hơn các số mũ cho các tập có kích thước nhỏ ($|A| \ll q^{1/2}$).
  • Cấu trúc đại số trên vành hữu hạn $\mathbb{Z}_q$: Các đánh giá trên vành $\mathbb{Z}_q$ chịu sự chi phối mạnh của số mũ lũy thừa $r$ và lực lượng của ideal các phần tử không khả nghịch $\mathbb{Z}_q^0$ ($|\mathbb{Z}_q^0| = p^{r-1}$), khiến các chặn thu được trên vành phụ thuộc vào tham số $r$.

Hướng nghiên cứu tiếp

  1. Khảo sát các lớp hàm nở đa biến tổng quát hơn trên vành hữu hạn $\mathbb{Z}_q$.
  2. Kết hợp phương pháp phổ đồ thị với phương pháp liên thuộc điểm - đường thẳng (kỹ thuật của Rudnev [46]) để cải thiện đánh giá lực lượng tập hợp cho trường hợp các tập $A$ có kích thước nhỏ.
  3. Nghiên cứu bài toán khoảng cách trên các đa tạp đại số tổng quát không chính quy hoặc trên các vành giao hoán hữu hạn bất kỳ.

Giá trị tham khảo

Luận án là tài liệu tham khảo chuyên khảo hữu ích cho:

  • Nghiên cứu sinh, học viên cao học và giảng viên ngành Toán học, Toán tin: Đặc biệt là các hướng chuyên sâu về Cơ sở toán học cho tin học, Toán rời rạc, Lý thuyết đồ thị cực trị, Tổ hợp cộng tính (Additive Combinatorics), Hình học tổ hợp rời rạc và Lý thuyết biểu diễn / Phổ đồ thị.
  • Nhà nghiên cứu trong lĩnh vực Mật mã học và Khoa học máy tính lý thuyết: Phương pháp xây dựng $(n, d, \lambda)$-đồ thị (đồ thị nở - expander graphs) và tính toán giá trị riêng thứ hai là công cụ nền tảng trong thiết kế mạng kết nối, hàm băm mật mã học, mã sửa sai và các thuật toán giả ngẫu nhiên.
  • Phần đáng tham khảo nhất:
    • Chương 2 với kỹ thuật tính giá trị riêng thứ hai thông qua phương trình ma trận kề $A^2 = h(A)$ cho 5 lớp đồ thị đại số.
    • Chương 3 với kỹ thuật áp dụng Bổ đề trộn nở để chuyển đổi số nghiệm phương trình đại số thành đánh giá lực lượng tập hợp.

Câu hỏi thường gặp

1. Bổ đề trộn nở (Expander Mixing Lemma) cho $(n, d, \lambda)$-đồ thị có phát biểu toán học như thế nào?

Cho $G = (V, E)$ là một $(n, d, \lambda)$-đồ thị vô hướng (tức là đồ thị $d$-chính quy gồm $n$ đỉnh với giá trị riêng thứ hai của ma trận kề bị chặn bởi $\lambda$). Với hai tập đỉnh con bất kỳ $S, T \subset V$, số cặp cạnh $E(S, T)$ nối giữa $S$ và $T$ thỏa mãn bất đẳng thức: $$\left| E(S, T) - \frac{d|S||T|}{n} \right| \le \lambda \sqrt{|S||T|}$$ Bổ đề này cho thấy khi $\lambda \ll d$, phân bố cạnh giữa hai tập con bất kỳ tiệm cận rất gần với phân bố cạnh trong đồ thị ngẫu nhiên $G(n, d/n)$.

2. Đồ thị tổng - bình phương $FS_q$ trên trường hữu hạn $\mathbb{F}_q$ được định nghĩa thế nào và có các tham số phổ là bao nhiêu?

Đồ thị tổng - bình phương $FS_q$ có tập đỉnh là $V = \mathbb{F}_q \times \mathbb{F}_q$. Hai đỉnh $a = (a_1, a_2)$ và $b = (b_1, b_2)$ được nối với nhau bởi một cạnh khi và chỉ khi $a_1 + b_1 + (a_2 - b_2)^2 = 0$. Luận án chứng minh $FS_q$ là một $(q^2, q, \sqrt{2q})$-đồ thị (tức có $q^2$ đỉnh, bậc $q$, và giá trị riêng thứ hai $\lambda \le \sqrt{2q}$).

3. Kết quả đánh giá tập thể tích khối $V_{2k+1}(A)$ của luận án đã cải thiện kết quả của Balog như thế nào?

Với $A \subset \mathbb{F}q$ và $k > 1$, Balog (2012) [7] sử dụng bất đẳng thức tam giác Ruzsa chứng minh rằng nếu $|A| \ge q^{\frac{1}{2} + \frac{1}{2 \cdot 2^k}}$ thì $V{2k+1}(A) = \mathbb{F}q$. Luận án (Định lý 3.6) sử dụng phương pháp phổ của đồ thị tích - tổng đã cải thiện điều kiện kích thước của tập $A$ xuống còn $|A| \gtrsim q^{\frac{1}{2} + \frac{1}{3 \cdot 2^k}}$ mà vẫn đảm bảo $V{2k+1}(A) = \mathbb{F}_q$.

4. Khó khăn cốt lõi khi mở rộng nghiên cứu từ trường hữu hạn $\mathbb{F}_q$ sang vành hữu hạn $\mathbb{Z}_q$ ($q=p^r$) là gì?

Trên vành hữu hạn $\mathbb{Z}_q = \mathbb{Z}/p^r\mathbb{Z}$ ($r \ge 2$), cấu trúc đại số xuất hiện tập các phần tử không khả nghịch $\mathbb{Z}_q^0$ (các phần tử chia hết cho $p$) với lực lượng $|\mathbb{Z}q^0| = p^{r-1}$. Do đó, các phép chia không thể thực hiện tự do như trên trường $\mathbb{F}q$, hệ phương trình đại số khi xác định số láng giềng chung có thể có nhiều nghiệm phụ thuộc vào ước chung lớn nhất của các hiệu tọa độ với $p^r$. Ma trận kề bình phương $A^2$ vì thế không chỉ phân rã thành $J$ và $I$ mà phân rã thành tổ hợp của nhiều ma trận $E\alpha, F\alpha$ ứng với các bậc lũy thừa $p^\alpha$, đòi hỏi kỹ thuật ước lượng giá trị riêng phức tạp hơn.

5. Những hàm hai biến nào được chứng minh là hàm nở trong Luận án khi xét trên tập $A$ có kích thước $|A| \gtrsim q^{1/2}$?

Luận án chứng minh hai hàm số $f(x, y) = x(y + 1)$ và $g(x, y) = x + y^2$ là các hàm nở hai biến trên cả trường hữu hạn $\mathbb{F}_q$ và vành hữu hạn $\mathbb{Z}_q$ với mọi tập con $A$ thỏa mãn điều kiện $|A| \gtrsim q^{1/2}$.

Kết luận

Luận án tiến sĩ của tác giả Đỗ Duy Hiếu đã nghiên cứu có hệ thống và ứng dụng thành công phương pháp phổ đồ thị ((n, d, \lambda)-đồ thị và Bổ đề trộn nở) để giải quyết một loạt bài toán quan trọng trong tổ hợp cộng tính trên không gian vectơ thuộc trường hữu hạn $\mathbb{F}_q$ và vành hữu hạn $\mathbb{Z}_q$. Tác giả đã xây dựng tường minh các lớp đồ thị đại số, tính toán chính xác chặn giá trị riêng thứ hai, từ đó đưa ra các chứng minh ngắn gọn cho bài toán khoảng cách và tích vô hướng, cải thiện cận kích thước tập hợp của Balog đối với tập thể tích khối, xác lập tính chất nở của các hàm hai biến và tổng quát hóa bài toán khoảng cách trên đa tạp chính quy. Các kết quả của luận án đóng góp tư liệu lý thuyết giá trị cho chuyên ngành Cơ sở toán học cho tin học và Toán rời rạc.