# The Frobenius Problem and the Covering Radius of a Lattice

## Document Type

Lecture

## Department

Mathematics (CMC)

## Publication Date

12-2005

## Abstract

Let *N *> 1 be an integer, and let 1 < *a*_{1} < ... < *a _{N} *be relatively prime integers. Frobenius number of this

*N*-tuple is defined to be the largest positive integer that cannot be expressed as a linear combination of

*a*

_{1}, ...,

*a*with non-negative integer coefficients. The condition that

_{N}*a*

_{1}, ...,

*a*are relatively prime implies that such a number exists. The general problem of determining the Frobenius number given

_{N}*N*and

*a*

_{1}, ...,

*a*is known to be NP-hard, but there has been a number of different bounds on the Frobenius number produced by various authors. We use techniques from the geometry of numbers to produce a new bound, relating Frobenius number to the covering radius of the null-lattice of the linear form with coefficients

_{N}*a*

_{1}, ...,

*a*In case when this lattice has equal successive minima, our bound is better than the previously known ones. This is joint work with Sinai Robins.

_{N. }## Rights Information

© 2005 Lenny Fukshansky

## Terms of Use & License Information

## Recommended Citation

Fukshansky, Lenny. "The Frobenius Problem and the Covering Radius of a Lattice." West Coast Number Theory, Pacific Grove, CA. December 2005.

## Comments

This lecture is related to an article written by Lenny Fukshansky and Sinai Robins, "Frobenius Problem and the Covering Radius of a Lattice" in

Discrete and Computational GeometryVolume 37, Issue 3, pages 471-483.The lecture was given during West Coast Number Theory in Pacific Grove, CA, December 2005. It was also given during the Colloquium at Temple University in February 2006, the Combinatorics Seminar at UCLA in May 2010, and the Number Theory Seminar at Texas A&M University in October 2005.