Hypergeometric polynomials and integer programming. (English) Zbl 0936.90038

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.


90C10 Integer programming
33C90 Applications of hypergeometric functions
Full Text: DOI