Hình học

Hình học nhiệt đới

Thay phép cộng và phép nhân thông thường bằng hai phép toán nhiệt đới $\oplus=\min$ và $\otimes=+$ biến các đường cong đa thức thành các đồ thị tuyến tính từng khúc, với cội nguồn bắt nguồn từ các thuật toán đường đi ngắn nhất và vươn tới các bài toán còn mở trong hình học liệt kê và hình học phi Archimedes.

Trực giácTừ số học thông thường đến số học nhiệt đới

Hãy tưởng tượng mỗi "phép cộng" nghĩa là chọn mức giá rẻ hơn trong hai mức giá, còn mỗi "phép nhân" nghĩa là cộng dồn chi phí dọc theo một tuyến đường. Định nghĩa hai phép toán mới trên tập số mở rộng thêm $+\infty$: phép cộng nhiệt đới $a \oplus b = \min(a, b)$ và phép nhân nhiệt đới $a \otimes b = a + b$. Một đa thức nhiệt đới chính là một đa thức thông thường mà mỗi dấu $+$ được đọc thành $\oplus$ và mỗi dấu $\times$ được đọc thành $\otimes$. Vì $\otimes$ chỉ là phép cộng, nên một đơn thức như $x^{\otimes 3}$ — ba bản sao của $x$ nhân nhiệt đới với nhau — trở thành $3x$, và toàn bộ đa thức sụp xuống thành giá trị nhỏ nhất trong hữu hạn hàm tuyến tính. Thay vì một đường cong trơn, "tập không điểm" của nó trở thành tập các điểm mà giá trị nhỏ nhất đó đồng thời đạt được ở ít nhất hai trong các hàm tuyến tính thành phần: một góc gãy, hay một đồ thị tuyến tính từng khúc.

Vì sao lại gọi là "nhiệt đới"? Cái tên này tôn vinh Imre Simon (1943–2009), một nhà khoa học máy tính người Brazil gốc Hungary, người đã tiên phong nghiên cứu đại số min-cộng trong khoa học máy tính lý thuyết từ cuối những năm 1970. Các đồng nghiệp người Pháp của ông trong lý thuyết ô-tô-mat đã đặt ra tính từ "nhiệt đới" như một cách gọi vui, ám chỉ thành phố quê hương São Paulo của Simon — nằm ở phía nam chí tuyến Nam — mà theo lời Sturmfels và Speyer sau này, "không mang ý nghĩa gì sâu xa cả." Cái tên đã ở lại khi các nhà toán học nhận ra rằng làm hình học đại số trên nửa vành min-cộng lại sinh ra một lý thuyết hình học đích thực và phong phú.

Đại họcNửa vành nhiệt đới và các đường cong nhiệt đới

Một đa thức nhiệt đới trong $n$ biến là một tổng $\oplus$ hữu hạn các đơn thức $\otimes$, tức là một hàm $p : \mathbb{R}^n \to \mathbb{R}$ có dạng $p(x) = \bigoplus_{\alpha \in S} c_\alpha \otimes x^{\otimes \alpha} = \min_{\alpha \in S} \big(c_\alpha + \alpha \cdot x\big)$, trong đó $S$ là một tập hữu hạn các véctơ số mũ $\alpha \in \mathbb{Z}^n$ và $c_\alpha \in \mathbb{R}$. Mọi hàm $p$ như vậy đều là giá trị nhỏ nhất theo điểm của hữu hạn hàm afin tuyến tính với hệ số góc nguyên, do đó tuyến tính từng khúc và lõm. Siêu mặt nhiệt đới (với $n = 2$, một đường cong nhiệt đới) xác định bởi $p$ là quỹ tích góc của nó $V(p) = \{x \in \mathbb{R}^n : \text{the minimum in } p(x) \text{ is attained by at least two terms}\}$ — chính xác là tập các điểm mà tại đó $p$ không tuyến tính, tương tự nhiệt đới của "nơi đa thức triệt tiêu."

Một đa thức nhiệt đới trong $n$ biến là một tổng $\oplus$ hữu hạn các đơn thức $\otimes$, tức là một hàm $p : \mathbb{R}^n \to \mathbb{R}$ có dạng $p(x) = \bigoplus_{\alpha \in S} c_\alpha \otimes x^{\otimes \alpha} = \min_{\alpha \in S} \big(c_\alpha + \alpha \cdot x\big)$, trong đó $S$ là một tập hữu hạn các véctơ số mũ $\alpha \in \mathbb{Z}^n$ và $c_\alpha \in \mathbb{R}$. Mọi hàm $p$ như vậy đều là giá trị nhỏ nhất theo điểm của hữu hạn hàm afin tuyến tính với hệ số góc nguyên, do đó tuyến tính từng khúc và lõm. Siêu mặt nhiệt đới (với $n = 2$, một đường cong nhiệt đới) xác định bởi $p$ là quỹ tích góc của nó, tập các điểm mà tại đó ít nhất hai hàm tuyến tính thành phần cùng đạt giá trị nhỏ nhất: $V(p) = \{x \in \mathbb{R}^n : |\{\alpha \in S : c_\alpha + \alpha \cdot x = p(x)\}| \ge 2\}$ — chính xác là tập các điểm mà tại đó $p$ không tuyến tính, tương tự nhiệt đới của "nơi đa thức triệt tiêu."

Hãy kiểm tra điều kiện cân bằng trên đường thẳng nhiệt đới ở trên: tại gốc tọa độ, ba tia có hướng nguyên thủy $(1,0)$, $(0,1)$, $(-1,-1)$, mỗi tia có trọng số $1$ (vì mọi hệ số của $q$ đều bằng $0$, nên mọi cạnh đối ngẫu trong tam giác Newton có độ dài dàn $1$). Quả thật $1\cdot(1,0) + 1\cdot(0,1) + 1\cdot(-1,-1) = (0,0)$, xác nhận định lý trên ví dụ đơn giản nhất này.

Nâng caoTừ các định giá hình thức đến một lý thuyết thực sự đại số

Đường thẳng nhiệt đới ở trên được dựng bằng tay từ các hệ số tùy ý, nhưng những đường cong nhiệt đới sâu sắc nhất lại đến từ việc nhiệt đới hóa một đa tạp đại số thực thụ. Cho $K$ là một trường trang bị một định giá $\mathrm{val} : K^* \to \mathbb{R}$ — một hàm thỏa $\mathrm{val}(ab) = \mathrm{val}(a) + \mathrm{val}(b)$ và $\mathrm{val}(a+b) \ge \min(\mathrm{val}(a), \mathrm{val}(b))$ — chẳng hạn như trường $\mathbb{C}\{\!\{t\}\}$ các chuỗi Puiseux (nơi $\mathrm{val}$ đọc ra số mũ nhỏ nhất của $t$) hoặc trường số $p$-adic $\mathbb{Q}_p$ (nơi $\mathrm{val}$ là định giá $p$-adic). Mở rộng $\mathrm{val}$ theo từng tọa độ thành ánh xạ $\mathrm{trop} : (K^*)^n \to \mathbb{R}^n$, $\mathrm{trop}(x_1, \dots, x_n) = (\mathrm{val}(x_1), \dots, \mathrm{val}(x_n))$. Với một đa tạp $X \subseteq (K^*)^n$, phép nhiệt đới hóa $\mathrm{trop}(X)$ là bao đóng của ảnh $\mathrm{trop}(X(K))$ trong $\mathbb{R}^n$.

Sự kiện quan trọng nhất kết nối bộ máy hình thức này trở lại với hình học đại số thực thụ là Định lý Cơ bản của Hình học Nhiệt đới: với một đa tạp $X = V(I) \subseteq (K^*)^n$ xác định bởi một iđêan $I$ trên một trường đóng đại số $K$ với một định giá không tầm thường, $\mathrm{trop}(X)$ trùng với tập $V(\mathrm{trop}(I)))$ thu được bằng cách nhiệt đới hóa mọi đa thức trong $I$ rồi lấy giao các quỹ tích góc của chúng — do đó phép nhiệt đới hóa có tính giải tích (dựng từ các điểm thực sự của $X$) trùng khớp với đa tạp nhiệt đới thuần túy tổ hợp dựng chỉ từ iđêan. Mikhail Kapranov đã chứng minh trường hợp siêu mặt (một đa thức xác định duy nhất) vào những năm 1990; phát biểu tổng quát cho iđêan bất kỳ, cùng chứng minh đầy đủ qua lý thuyết Gröbner và iđêan khởi đầu, được phát triển như Định lý Cơ bản trong giáo trình Introduction to Tropical Geometry năm $2015$ của Diane Maclagan và Bernd Sturmfels, dựa trên các kỹ thuật cơ sở Gröbner nhiệt đới được xây dựng trước đó trong những năm 2000.

Rất lâu trước khi ai đó gọi bất cứ điều gì trong số này là "nhiệt đới," các nhà khoa học máy tính đã làm đại số tuyến tính nhiệt đới bằng tay. Bài toán đường đi ngắn nhất giữa mọi cặp đỉnh trên một đồ thị có hướng có trọng số là một ví dụ sách giáo khoa của đại số $(\min, +)$: nếu $A$ là ma trận $n \times n$ với $A_{ij}$ là trọng số cạnh từ $i$ đến $j$ (và $A_{ij} = +\infty$ khi không có cạnh, $A_{ii} = 0$), thì phép nhân ma trận nhiệt đới được định nghĩa hệt như trong đại số tuyến tính thông thường nhưng thay $+$ bằng $\oplus$ và thay $\times$ bằng $\otimes$: $(A \otimes B)_{ij} = \bigoplus_k \big(A_{ik} \otimes B_{kj}\big) = \min_k \big(A_{ik} + B_{kj}\big)$.

Hình học nhiệt đới nằm ở một ngã tư thực sự. Mỗi đa thức nhiệt đới $p$ mang theo một đa diện Newton $\mathrm{conv}(S) \subseteq \mathbb{R}^n$, và các hệ số $c_\alpha$ tạo ra một phép chia nhỏ chính quy của đa diện đó (nâng mỗi $\alpha$ lên độ cao $c_\alpha$ rồi chiếu các mặt phía dưới trở lại xuống) — chính xác là bộ máy đa diện của hình học lồi và rời rạc. Đối ngẫu lại, đa tạp nhiệt đới $\mathrm{trop}(X)$ của một đa tạp đại số cổ điển $X$ mã hóa dữ liệu hình học đại số thực thụ của $X$ (số chiều, bậc, và phần lớn lý thuyết giao của nó) bên trong một đối tượng thuần túy tổ hợp, đó là lý do vì sao rất nhiều phép tính trong hình học đại số có thể thực hiện được theo cách nhiệt đới. Và vì mọi đa thức nhiệt đới đều là giá trị nhỏ nhất của các hàm afin tuyến tính, nên việc tính giá trị của nó tự nó chính là một bài toán quy hoạch tuyến tính nhỏ: hình học nhiệt đới và tối ưu lồi/tuyến tính chia sẻ cùng một cấu trúc $(\min, +)$-tuyến tính nền tảng, và các phương pháp nhiệt đới hiện nay đóng góp trực tiếp vào các thuật toán quy hoạch tuyến tính và lồi.

Nâng caoMột trăm năm hình thành: từ lý thuyết ô-tô-mat đến hình học đại số

Nghiên cứuHình học nhiệt đới hiện đang ở đâu