Frobenius problem: Applications

Jorge Ramirez

Universite de Paris VI

Abstract

Note the unusual place!

This is a third part of the special series of lectures about Frobenius problem. (The first two are on Wednesday, on 9:00, and on 15:40, both in S6.)

Lecture I (Wednesday 29 October) Frobenius problem: Algorithms and complexity

F.G. Frobenius raised the following problem (called, Frobenius diophantine Problem [FP]): given relatively prime positive integers a_1,a_2,...,a_n, find the largest natural number, called the Frobenius number and denoted by g(a_1,a_2,...,a_n), that is not representable as a nonnegative integer combination of a_1,a_2,...,a_n. This lecture will be devoted to the computational aspects of FP. After showing that FP is NP-hard (under Turing reductions), we shall present a variety of algorithms to compute g(a_1,a_2,...,a_n) for general n. We will also discuss polynomial time methods that solve FP for some particular cases, for instance, when a_1,a_2,...,a_n is an almost arithmetic sequence.

Lecture II (Wednesday 29 October) Frobenius problem: Formulas and gaps

FP is easy to solve when n=2. Indeed, g(a_1,a_2)=a_1a_2-a_1-a_2. However, the computation of a (simple) formula when n=3 is much more difficult. After giving a proof of the latter equality (which uses the well-known Pick's theorem), we will present some known upper and lower bounds for g(a_1,a_2,...,a_n) as well as formulas for particular sequences, for exemple, when a_1,a_2,...,a_n is a generilized arithmetic sequence. The behaviour of gaps in numerical semigroups will also be discussed.

Lecture III (Thursday 30 October) Frobenius problem: Applications

We will present some applications of the Frobenius number to a variety of problems. We will explain how FP can be used to the complexity analysis of the Shell-sort method (a fundamental sorting algorithm). We will also mention an application of FP to the study of partitions of vector spaces. Finally, we shall present a recent application of FP to the study of tiling problems.