Speakers

		David Einstein, Structured Decisions Corporation		When is the Frobenius Problem Easy?
		Leonid Fukshansky, Texas A&M University		Frobenius number, covering radius, and well-rounded lattices
		Daniel Lichtblau, Wolfram Research		Integer Linear Programming, Frobenius Instances, and Frobenius Numbers
		Gretchen Matthews, Clemson University		Fibonacci semigroups and their duals
		Vadim Ponomarenko, San Diego State University		The Multi-Dimensional Frobenius Problem
		Bjarke Hammersholt Roune, Aarhus University		Computing Frobenius Numbers Using Test Sets
		Herbert Scarf, Yale University		My Favorite Simplicial Complex and Applications to the Frobenius Problem
		Amitabha Tripathi, Indian Institute of Technology, Delhi		Frobenius in three variables
		Stan Wagon, Macalester College		Automated Proofs of Quadratic Frobenius Formulas
		Zhi Xu, University of Waterloo		The Frobenius Problem in a Free Monoid

Organizers

General Information

Abstracts

David M Einstein

When is the Frobenius Problem Easy?

Recently, elementary algorithms have been developed that can solve the Frobenius problem in low dimension relatively quickly in most cases, but which take a long time in rare cases. We seek to quickly ditinguish cases where the algorithm will solve the Frobenius problem in a reasonable amount of time from those cases where it may not.

Leonid Fukshansky* & Sinai Robins

Frobenius number, covering radius, and well-rounded lattices

Let N > 1 be an integer, and let 1 < a₁ < ... < 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₁, ..., a_N with non-negative integer coefficients. We use techniques from the geometry of numbers to produce a new upper bound on the Frobenius number, which is symmetric in all of the a_i's, by relating it to the covering radius of the null-lattice of the linear form with coefficients a₁, ..., a_N. We discuss some situations in which our bound is better than the previously known ones; in particular, this is the case when the lattice has equal successive minima, which we show happens infinitely often.

Daniel Lichtblau

Integer Linear Programming, Frobenius Instances, and Frobenius Numbers

I will show how lattice reduction and branch-and-bound methods may be used in tandem to solve Frobenius instance problems. We apply much the same methods to other aspects of finding Frobenius numbers. Moreover the instance solver can be used to give good (as in tight, with high probability) bounds on the Frobenius number, in many cases where the latter computation is intractable with current methods.

Gretchen Matthews

Fibonacci semigroups and their duals

Let a₁, ..., a_n be positive integers which are relatively prime. Then the numerical semigroup generated by a₁, ..., a_n S:= {sum_i=1..n c_i a_i : c_i>=0}. The largest integer not in S is called the Frobenius number of S. The dual of S is formed by adding to S its Frobenius number as well as any additional pseudo-Frobenius numbers. In this talk, we study the duals of semigroups generated by certain Fibonacci numbers and relate them to associated Lipman semigroups. This gives, in a sense, a measure of how close to being Arf a Fibonacci semigroup is.

Jeffrey Amos, Iuliana Pascu, Vadim Ponomarenko*, Enrique Trevino, and Yan Zhang

The Multi-Dimensional Frobenius Problem

We consider the problem of finding maximal (in an appropriate partial order) solutions g to the linear Diophantine system Mx=g. We give conditions for the existence and uniqueness of g, bounds on g, and a reduction formula. This is work done by undergraduates in an REU program.

Bjarke Hammersholt Roune

Computing Frobenius Numbers Using Test Sets

This talk will show how Groebner bases/test sets can be used to compute Frobenius numbers. The presented method also employs irreducible decomposition of a certain monomal ideal, which is closely related to Maximal Lattice Free Bodies (MLFB).

The algorithm can solve some Frobenius problems with previously intractably large numbers. It is in effect an enhancement of the algorithm by Einstein, Lichtblau, Strzebonksi and Wagon.

Herbert Scarf

My Favorite Simplicial Complex and Applications to the Frobenius Problem

The Frobenius Problem for the integers a=(a₁, ..., a_n) is closely related to the simplicial complex of Maximal Lattice Free Bodies based on an n times (n-1) integral matrix A, whose columns generate the lattice {ah=0 : h in Zⁿ}. The talk will discuss some structural properties of this complex which may be useful in the computation of its n-1 dimensional simplicies and consequently the Frobenius number for the vector a.

Amitabha Tripathi

Frobenius in three variables

Stan Wagon

Automated Proofs of Quadratic Frobenius Formulas

Zhi Xu

The Frobenius Problem in a Free Monoid