Parametric polyhedra with at least k lattice points: their semigroup structure and the k-Frobenius problem

DOI10.1007/978-3-319-24298-9_29zbMATH Open1358.52016arXiv1409.5259OpenAlexW2263482706MaRDI QIDQ2957201FDOQ2957201

Authors: Jesús A. De Loera, Quentin Louveaux, Iskander Aliev 

Publication date: 25 January 2017

Published in: Recent Trends in Combinatorics (Search for Journal in Brave)

Abstract: Given an integral $dimesn$ matrix $A$, the well-studied affine semigroup $mboxSg(A)=b:Ax=b,xin{mathbbZ}^n,xgeq0$ can be stratified by the number of lattice points inside the parametric polyhedra $P_A(b)=x:Ax=b,xgeq0$. Such families of parametric polyhedra appear in many areas of combinatorics, convex geometry, algebra and number theory. The key themes of this paper are: (1) A structure theory that characterizes precisely the subset $mbox{Sg}_{geqk}(A)$ of all vectors $binmboxSg(A)$ such that $P_A(b)cap{mathbbZ}^n$ has at least $k$ solutions. We demonstrate that this set is finitely generated, it is a union of translated copies of a semigroup which can be computed explicitly via Hilbert bases computations. Related results can be derived for those right-hand-side vectors $b$ for which $P_A(b)cap{mathbbZ}^n$ has exactly $k$ solutions or fewer than $k$ solutions. (2) A computational complexity theory. We show that, when $n$, $k$ are fixed natural numbers, one can compute in polynomial time an encoding of $mbox{Sg}_{geqk}(A)$ as a multivariate generating function, using a short sum of rational functions. As a consequence, one can identify all right-hand-side vectors of bounded norm that have at least $k$ solutions. (3) Applications and computation for the $k$-Frobenius numbers. Using Generating functions we prove that for fixed $n,k$ the $k$-Frobenius number can be computed in polynomial time. This generalizes a well-known result for $k=1$ by R. Kannan. Using some adaptation of dynamic programming we show some practical computations of $k$-Frobenius numbers and their relatives.

Full work available at URL: https://arxiv.org/abs/1409.5259

Recommendations

• The parametric Frobenius problem
• Integer programs with prescribed number of solutions and a weighted version of Doignon-Bell-Scarf's theorem
• scientific article; zbMATH DE number 18540
• Frobenius numbers by lattice point enumeration
• Lattice translates of a polytope and the Frobenius problem

zbMATH Keywords

Frobenius numberslinear Diophantine equationscombinatorial number theoryaffine semigroupsHilbert basescombinatorial commutative algebralattice points in polyhedra

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Combinatorial aspects of commutative algebra (05E40) The Frobenius problem (11D07)

Cited In (11)

• Commutative algebra of generalised Frobenius numbers
• On the number of integer points in translated and expanded polyhedra
• Integer programs with prescribed number of solutions and a weighted version of Doignon-Bell-Scarf's theorem
• Enumerating projections of integer points in unbounded polyhedra
• On \(p\)-Frobenius of affine semigroups
• The generalized Frobenius problem via restricted partition functions
• \(p\)-numerical semigroups with \(p\)-symmetric properties
• On the determination of p-Frobenius and related numbers using the p-Apéry set
• Frobenius Coin-Exchange Generating Functions
• The Frobenius problem over number fields with a real embedding
• Positive semigroups and generalized Frobenius numbers over totally real number fields

This page was built for publication: Parametric polyhedra with at least \(k\) lattice points: their semigroup structure and the \(k\)-Frobenius problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2957201)