User Tools

Site Tools


Matthias Beck (Binghamton)

The Linear Diophantine Problem of Frobenius

Abstract for the Combinatorics and Number Theory Seminar 2002 February 5

Given relatively prime positive integers a1 , …, an , we call an integer t representable if there exist nonnegative integers m1 , …, mn such that

t = m1 a1 + … + mn an .
We study the linear diophantine problem of Frobenius: namely, to find the largest integer which is not representable.

We translate this problem into a geometric one: consider N(t), the number of nonnegative integer solutions (m1 , …, mn ) to m1 a1 + … + mn an = t for any positive integer t. N(t) enumerates the integer points in a polytope. Solving the Frobenius problem now simply means finding the largest zero of N(t). N(t) turns out to be a quasi-polynomial, thereby yielding a straightforward analytic tool to recover and extend some well-known results on this classical problem.

seminars/comb/abstract.200202beck.txt · Last modified: 2020/01/29 14:03 (external edit)