Frobenius problem and the covering radius of a lattice

Details Frobenius problem and the covering radius of a lattice Frobenius problem and the covering radius of a lattice

2005-12-06

arxiv.org/abs/math/0512134v2

Discrete Comput. Geom. 37 (2007), no. 3, 471--483

Mathematics

Number Theory

12 pages; minor revisions; to appear in Discrete and Computational Geometry

Scientific paper

Let $N \geq2$ 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 $\sum_{i=1}^N a_i x_i$ where $x_1,...,x_N$ are non-negative integers. The condition that $gcd(a_1,...,a_N)=1$ implies that such number exists. The general problem of determining the Frobenius number given $N$ and $a_1,...,a_N$ is 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 this $N$-tuple. Our bound is particularly interesting in the case when this lattice has equal successive minima, which, as we prove, happens infinitely often.

Affiliated with

Also associated with

No associations

Rating

Frobenius problem and the covering radius of a lattice does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Frobenius problem and the covering radius of a lattice, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Frobenius problem and the covering radius of a lattice will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-697960