Có thể bạn có cảm giác rằng tiêu đề của bài viết này hơi khoa trương. Đúng là (đối với bạn) có thể có những bí mật toán học khác dễ nhận ra hơn, cơ mà, tôi đã thu hút sự chú ý của bạn, phải không? Tốt. Bởi vì tôi muốn kể cho bạn nghe về một chủ đề quan trọng trong toán học - một câu thần chú toán học, hi vọng bạn sẽ thích. Đây là một kĩ thuật mà các nhà toán học luôn sử dụng để làm toán.
Lí thuyết phạm trù (category theory) nhìn toán học từ trên cao. Từ trên cao, tuy không thể nhìn thấy các chi tiết, nhưng ta có thể nhận ra các mô thức (patterns) mà từ mặt đất không thể phát hiện được.
Thay vì đưa ra một loạt định nghĩa — khá dễ kiếm trên internet nhưng bạn có thể sẽ cảm thấy hơi khó hiểu khi mới tiếp xúc — tôi nghĩ sẽ thú vị hơn nếu chúng ta cùng nhìn nhận lí thuyết phạm trù (category theory) trong bức tranh lớn hơn của toán học. Lí thuyết này khác biệt so với các nhánh toán học khác. Thay vì là một lĩnh vực ngang hàng với các ngành khác, nó giống như một “gen chung” kết nối chúng lại ngay từ gốc rễ.
Các đa thức đối xứng (symmetric polinomials) đóng vai trò quan trọng trong việc hiểu mối quan hệ giữa các nghiệm (root) của các phương trình đa thức và các hệ số (coefficient) của chúng. Trong bài viết này, chúng ta sẽ khám phá sâu hơn về mối liên hệ này, từ định nghĩa cơ bản đến các ứng dụng thực tiễn.
Đa thức đối xứng với các biến $x_1, x_2, \ldots, x_n$ là một đa thức không thay đổi dưới bất kì phép hoán vị (permutation) nào của các biến. Cụ thể, với bất kì phép hoán vị $\sigma$ nào của các chỉ số ${1, 2, \ldots, n}$:
Chúng ta cần chuyển bài toán quy hoạch tuyến tính từ dạng tổng quát (general form) sang dạng chuẩn (standard form). Tức là:
Trong đó, (1),(2) và (3) là các yêu cầu bắt buộc. (4) và (5) không bắt buộc phải đảm bảo trong dạng chuẩn, nhưng đó sẽ là điều kiện bắt buộc khi giải bài toán tối ưu bằng phương pháp đơn hình về sau.
$$\lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_r$$$$ n = \lambda_1 + \dots + \lambda_r .$$Tham khảo chủ yếu từ https://docs.oscar-system.org/stable/Combinatorics/EnumerativeCombinatorics/partitions/#partition
Các $\lambda_i$ được gọi là các phần tử (part) của phân hoạch và $r$ được gọi là độ dài (length). Tham khảo thêm tại Ful97 và Knu11, Mục 7.2.1.4.
Một phân hoạch có thể được mã hóa (encoded) dưới dạng một mảng (array) với các phần tử (element) là $\lambda_i$.
OSCAR cung cấp kiểu tham số (parametric type) Partition{T} và đây là một kiểu con (subtype) của AbstractVector{T}.
Ở đây, T có thể là bất kì kiểu con nào của IntegerUnion.
Hiệu suất không bị hảnh hưởng khi sử dụng kiểu riêng cho phân hoạch thay vì chỉ sử dụng mảng.
Kiểu tham số này cho phép tăng hiệu suất bằng cách sử dụng các kiểu số nguyên nhỏ hơn.
