Hypergeometric polynomials and integer programming. (English) Zbl 0936.90038

Saito, Mutsumi; Sturmfels, Bernd; Takayama, Nobuki

Compos. Math. 115, No. 2, 185-204 (1999).

Let \(n\geq d\) and let us consider a non-negative integer \(n\times n\)-matrix \(A\) of maximal rank \(d\). The matrix \(A\) induces a map \(T: \mathbb{N}^n\to \mathbb{N}^d\), with \(\mathbb{N}:= \{0,1,2,\dots\}\). Any point \(\alpha\) of \(\mathbb{N}^d\) and any \(n\)-variate linear functional \(\omega\) determine a discrete linear optimization problem with \(T^{-1}(\alpha)\) as the set of feasible points. To \(A\) and \(\alpha\) there corresponds a so-called \(A\)-hypergeometric system of partial differential equations. This system admits for \(T^{-1}(\alpha)\neq \emptyset\) a symbolic solution which is up to scaling unique. This solution is a hypergeometric polynomial \(\Phi (\alpha;x)\) in the variables \(x= (x_1,\dots, x_n)\) (Proposition 2.1).
The following Theorems 3.1 and 3.2 analyze the dependence of the polynomial \(\Phi(\alpha,x)\) on the point \(\alpha\).
In analogy with the classical Frobenius method for solving ordinary differential equations, an indicial ideal is then introduced. Optimal solutions of the discrete linear optimization problem in standard form with feasibility set \(T^{-1} (\alpha)\) are zeros of this indicial ideal (Theorem 4.1).
Finally, Theorem 5.1 characterizes the case where the indicial ideal is principal.
All algebraic objects introduced in this paper (e.g. indicial polynomials) are computable by means of Gröbner basis techniques from the initial data.

Reviewer: Joos Heintz (Buenos Aires)

MSC:

90C10	Integer programming
33C90	Applications of hypergeometric functions

Keywords:

integer programming; \(A\)-hypergeometric system; partial differential equations; discrete linear optimization; indicial polynomials; Gröbner basis