Reverse Plane Partition (RPP) là gì?

Trong lý thuyết biểu diễn và đại số tổ hợp, các bảng số điền vào biểu đồ Young (Young diagram) là công cụ trung tâm để xây dựng các hàm đối xứng kinh điển. Khi các điều kiện thứ tự trên hàng và cột thay đổi, ta nhận được những lớp đối tượng khác nhau:

• Bảng Young nửa chuẩn tắc (Semistandard Young Tableau - SSYT): hàng không giảm ($\le$), cột tăng ngặt ($<$). Đây là đối tượng sinh ra đa thức Schur $s_\lambda(x)$.
• Phân hoạch phẳng (Plane Partition): các hàng và cột cùng không tăng ($\ge$), đối tượng đếm nổi tiếng do P. A. MacMahon khởi xướng.
• Phân hoạch phẳng ngược (Reverse Plane Partition - RPP): các hàng và cột cùng không giảm ($\le$).

Bài viết này giới thiệu định nghĩa chuẩn tắc của RPP, đối chiếu nó với SSYT, và giải thích vì sao một quy tắc đếm trọng số theo cột lại biến RPP thành hạt nhân sinh ra đa thức dual Grothendieck.

1. Định nghĩa toán học của Reverse Plane Partition

Cho một phân hoạch nguyên $\lambda = (\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_\ell > 0)$. Biểu đồ Young tương ứng của $\lambda$ là tập hợp các ô $(i, j)$ trong mặt phẳng thỏa mãn $1 \le i \le \ell$ và $1 \le j \le \lambda_i$ (theo quy ước tọa độ ma trận: hàng $i$ từ trên xuống, cột $j$ từ trái sang).

Một Reverse Plane Partition (RPP) hình dạng $\lambda$ với các giá trị bị chặn bởi $n$ là một cách điền các số nguyên từ ${1, 2, \ldots, n}$ vào các ô của $\lambda$, ký hiệu $T(i, j)$, sao cho:

1. Không giảm theo từng hàng: $$T(i, j) \le T(i, j+1) \quad \text{với mọi ô } (i, j), (i, j+1) \in \lambda$$
2. Không giảm theo từng cột: $$T(i, j) \le T(i+1, j) \quad \text{với mọi ô } (i, j), (i+1, j) \in \lambda$$

Tập hợp tất cả các RPP hình dạng $\lambda$ có giá trị không vượt quá $n$ thường được ký hiệu là $\mathrm{RPP}_{\le n}(\lambda)$, hoặc viết gọn là $\mathrm{RPP}(\lambda)$ khi số biến đã được ngầm hiểu.

2. Điểm khác biệt cốt lõi giữa RPP và SSYT

Để nắm bắt trực giác của RPP, cách tốt nhất là đặt nó cạnh SSYT:

Trong SSYT, ràng buộc tăng ngặt trên cột phản ánh nguyên lý loại trừ (Fermionic): mỗi cột không thể chứa hai trạng thái giống nhau. Ở RPP, việc nới lỏng từ $<$ thành $\le$ khiến không gian trạng thái nở rộng hơn rất nhiều.

3. Ví dụ trực quan với $\lambda = (2, 1)$

Xét phân hoạch $\lambda = (2, 1)$ gồm 3 ô:

1
2
3
4
5

┌───┬───┐
│ a │ b │   Hàng 1: ô (1,1) và (1,2)
├───┼───┘
│ c │       Hàng 2: ô (2,1)
└───┘

Lưu ý rằng giữa $b$ và $c$ không có bất kỳ ràng buộc thứ tự trực tiếp nào.

Giả sử ta chỉ dùng hai giá trị trong tập ${1, 2}$. Ta có chính xác 5 RPP hợp lệ:

Trong 5 bảng này, chỉ có $T_3$ và $T_4$ là SSYT (vì cột thứ nhất có hai số khác nhau: $1 < 2$). Ba bảng còn lại ($T_1, T_2, T_5$) đều chứa hai số trùng nhau ở cột thứ nhất ($1 \le 1$ hoặc $2 \le 2$), do đó chúng chỉ là RPP chứ không phải SSYT.

4. Trọng số đếm cột và Đa thức Dual Grothendieck

Trong lý thuyết tổ hợp cổ điển (Richard Stanley, 1971), trọng số của một plane partition thường được tính bằng tổng các giá trị ghi trong các ô: $\sum_{(i,j)} T(i, j)$.

Tuy nhiên, trong hình học đại số và $K$-theory của Grassmannian (Lam & Pylyavskyy 2007, Yeliussizov 2017), RPP xuất hiện cùng một thống kê trọng số nhiều biến hoàn toàn khác, gọi là $\operatorname{ircont}$ (injective reverse content):

Quy tắc đếm cột: Với mỗi giá trị $k \in {1, \ldots, n}$, số mũ của biến $x_k$ là số lượng cột có chứa ít nhất một lần giá trị $k$.

Nói cách khác, dù giá trị $k$ có xuất hiện bao nhiêu lần trong cùng một cột đi nữa, cột đó cũng chỉ đóng góp đúng $1$ vào số mũ của $x_k$:

Hãy tính trọng số $\operatorname{ircont}$ cho 5 RPP của $\lambda = (2, 1)$ ở trên:

1. $T_1 = \begin{pmatrix} 1 & 1 \ 1 \end{pmatrix}$: Cột 1 chứa ${1}$, Cột 2 chứa ${1}$. Giá trị $1$ có mặt ở cả 2 cột, giá trị $2$ không có mặt ở cột nào $\implies x_1^2$.
2. $T_2 = \begin{pmatrix} 1 & 2 \ 1 \end{pmatrix}$: Cột 1 chứa ${1}$, Cột 2 chứa ${2}$. Giá trị $1$ ở cột 1, giá trị $2$ ở cột 2 $\implies x_1 x_2$.
3. $T_3 = \begin{pmatrix} 1 & 1 \ 2 \end{pmatrix}$: Cột 1 chứa ${1, 2}$, Cột 2 chứa ${1}$. Giá trị $1$ có ở 2 cột; giá trị $2$ có ở 1 cột $\implies x_1^2 x_2$.
4. $T_4 = \begin{pmatrix} 1 & 2 \ 2 \end{pmatrix}$: Cột 1 chứa ${1, 2}$, Cột 2 chứa ${2}$. Giá trị $1$ có ở 1 cột; giá trị $2$ có ở 2 cột $\implies x_1 x_2^2$.
5. $T_5 = \begin{pmatrix} 2 & 2 \ 2 \end{pmatrix}$: Cột 1 chứa ${2}$, Cột 2 chứa ${2}$. Giá trị $2$ có mặt ở cả 2 cột $\implies x_2^2$.

Lấy tổng trọng số của cả 5 RPP, ta thu được:

Đây chính là đa thức dual Grothendieck $g_{(2,1)}(x_1, x_2)$. Đa thức này hoàn toàn đối xứng đối với hai biến $x_1$ và $x_2$.

5. Từ định nghĩa tổ hợp đến thách thức thuật toán

Định nghĩa qua RPP đem lại một hình ảnh trực quan và tường minh cho đa thức dual Grothendieck. Tuy nhiên, nếu dùng định nghĩa này để lập trình tính toán trực tiếp:

1. Bùng nổ tổ hợp: Số lượng RPP tăng bùng nổ theo cấp số nhân khi kích thước phân hoạch $|\lambda|$ và số biến $n$ tăng lên. Việc sinh vét cạn (brute-force enumeration) từng RPP sẽ gặp tắc nghẽn bộ nhớ và thời gian tính toán rất nhanh.
2. Bùng nổ đơn thức: Ngay cả khi đối tượng là đối xứng, việc cộng dồn từng đơn thức tự do $x_1^{\alpha_1}\cdots x_n^{\alpha_n}$ sẽ sinh ra hàng triệu phép băm trong Hash Map.

Để giải quyết bài toán tính $g_\lambda(x_1, \ldots, x_n)$ với quy mô lớn, người ta không liệt kê RPP một cách thô mộc, mà chuyển đổi mô hình qua từng tầng trừu tượng:

• Tách bảng theo từng lớp giá trị $k$ (Value-layer recurrence).
• Đổi hệ quy chiếu sang dãy chiều cao các cột (Column-height profiles).
• Mô hình hóa điều kiện biên cục bộ bằng máy biến nạp (Weighted transducer).
• Nén toàn bộ không gian đơn thức vào các quỹ đạo đối xứng ($S_k$-Orbit compression) và tính toán bằng phép nhân ma trận thưa (Transfer-SpMV).

👉 Chi tiết toàn bộ các bước chuyển đổi kiến trúc và thuật toán tối ưu này được trình bày tại bài viết: Thuật toán đằng sau đa thức dual Grothendieck.