Mathematica 9 is now available

Wolfram Library Archive


Courseware Demos MathSource Technical Notes
All Collections Articles Books Conference Proceedings
Title Downloads

Frobenius Numbers by Lattice Points: Applications of Integer Optimization to a Classic Computational Problem
Authors

Stan Wagon
Organization: Macalester College
Daniel Lichtblau
Organization: Wolfram Research, Inc.
Conference

2006 Wolfram Technology Conference
Conference location

Champaign IL
Description

The Frobenius number a of a finite set of positive integers is the least integer that is not representable as a nonnegative combination of entries in a. For example, Chicken McNuggets® come in serving sizes of 6, 9, and 20. One cannot buy 43 McNuggets, but any larger target is representable. Thus a. Finding the Frobenius number, and solving Frobenius instances (finding a solution to a in nonnegative integers a) are closely related to more general problems in integer optimization. For example, minimizing a subject to the constraints that this quantity is nonnegative and each entry of a is nonnegative will solve the instance problem, since the target a is representable iff 0 is the minimum.

In this talk we will show how a study of a certain lattice of integer vectors leads to a geometric object—the fundamental domain—that encodes enough information to find the Frobenius number. Getting this information about the domain requires developing several algorithms, many of which have had an impact on some of Mathematica’s kernel functions, such as a and a. Letting a be the number of integers in a, we can find a (with rare exceptions) when a, but with no restriction on the size of the entries in a. The algorithm seems to have complexity that, when a is fixed, is close to quadratic on average. The previous best algorithm for this problem was polynomial-time in the input size, but with polynomial degree a. Here is an example with a (in Mathematica 5.2). Needs["NumberTheory`"] A = {10000000001, 20100000000, 30000000017, 40000000039, 50999000101}; g = FrobeniusF[A] 529710001010385 FrobeniusInstance[A, g + 100] {122, 900, 3, 8, 10000} The main points are best illustrated when a. Letting a be the integers a, there is a natural map a given by a. The kernel of a is the lattice a consisting of triples a such that a is divisible by a. The classic relationship a raises the question of finding a geometric form for a; by this we mean choosing a representative vector for each equivalence class. We do this in a natural way, and call the resulting set of a vectors , for fundamental domain; it sets in the first octant and includes the origin. There is then a tiling of a induced by translating copies of  by vectors in a. Here is picture of the domain—the gray cubes—when a. The trick then is to capture concisely the geometric structure of the domain, so that it can be easily described even when it has a entries. We do this by getting the elbows of , by which we mean vectors a that are not in , but such that subtracting 1 in any nonzero coordinate yields a point that is in ; these are the nine tetrahedra in the diagram. It follows that  is obtained by deleting the cones defined by all the elbows. Having the elbows in hand allows us to get the corners of , and one of the corners yields the Frobenius number of a.

Our algorithm for doing this is complicated, with many steps. But it appears that, when n is fixed, the average complexity is close to quadratic. Other consequences of our work are a very fast algorithm when a (it can handle million-digit inputs) and some new theoretical results about the Frobenius number of special sequences. An important part of our algorithm involves solving linear Diophantine equations to give important information about the domain . Such problems are also of importance in their own right, with applications in computational number theory, operations research, and elsewhere. A particular application, closely related to the problem at hand, is solving a specific Frobenius instance: Given our set a and a target value a, we find a nonnegative a that solves a. We will discuss how this is done efficiently in Mathematica, and mention how similar Diophantine equations relate to finding Frobenius numbers.
Subject

*Mathematics > Number Theory
Keywords

Frobenius numbers, integer linear programming, lattices
Downloads Download Wolfram CDF Player

Download
Frobenius Numbers.nb (3.3 MB) - Mathematica Notebook [for Mathematica 5.2]
Download
TechConf2006_ilp_talk_v5.nb (935.4 KB) - Mathematica Notebook [for Mathematica 5.2]