Andrew Granville and I just uploaded, “The Frobenius postage stamp problem, and beyond” to the arXiv.

Let with , , and who has greatest common divisor of all the elements is 1. For positive integer , we are interested in the structure of

For instance,

Equality does not hold in general. For instance if , then for any . We set

Thus we can refine (1) to

It turns out there is one more obstruction. Note that if and only if and so

Thus we may refine (2) to

Our main result is the following.

**Theorem 1:** For , (3) is an equality.

Theorem 1 is close to best possible, as can be seen from . For 3 element sets, we actually show Theorem 1 holds for all , which contains some of the ideas present in the general case.

We prove Theorem.1 for from first principles. To get from to , here are two key additional inputs: a structural result of Savchev and Chen and Kneser’s theorem from additive combinatorics.

A key definition is , which is the smallest element in that is equivalent to . For instance, it follows from a short argument of Erdös that . Indeed we have

If any subsum is , we may remove it to get a smaller element in that is . Thus no subsum is . But this quickly implies that , as desired.

We also study a natural higher dimensional analog of Theorem 1, utilizing some basic tools such as Carathéodory’s Theorem and Mann’s Lemma. In this setting, we provide an analog of Theorem 1, though our bounds are not nearly as good.

### Like this:

Like Loading...