The Frobenius Postage Stamp Problem, and Beyond

Additive Combinatorics,

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

Let {A \subset \mathbb{Z}} with {\min A = 0}, {\max A = b}, and who has greatest common divisor of all the elements is 1. For positive integer {N}, we are interested in the structure of

\displaystyle NA = \{a_1 + \ldots + a_N : a_i \in A\}.

For instance,

\displaystyle NA \subset \{0, \ldots ,bN\}.\ \ \ \ \ (1)

Equality does not hold in general. For instance if {1 \notin A}, then {1 \not NA} for any {N \geq 1}. We set

\displaystyle \mathcal E(A) = \mathbb{Z}_{\geq 0} \setminus \cup_{M \in \mathbb{Z}_{\geq 1}} MA ,

Thus we can refine (1) to

\displaystyle NA \subset \{0 , \ldots , bN\} \setminus \mathcal E (A)\ \ \ \ \ (2)

It turns out there is one more obstruction. Note that {n \in NA} if and only if {bN-n \in bN- NA} and so

\displaystyle bN -n \notin \mathcal E(b-A).

Thus we may refine (2) to

\displaystyle NA \subset \{0 , \ldots , bN\} \setminus (\mathcal E (A) \cup (bN - \mathcal E(b-A))).\ \ \ \ \ (3)

Our main result is the following.

{\ } Theorem 1: For {N \geq b}, (3) is an equality. {\spadesuit} {\ }

Theorem 1 is close to best possible, as can be seen from {A = \{0,1,b-1,b\}}. For 3 element sets, we actually show Theorem 1 holds for all {N \geq 1}, which contains some of the ideas present in the general case.

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

A key definition is {n_{a,A}}, which is the smallest element in {\mathcal P (A) : = \cup_{M \in \mathbb{Z}_{\geq 1}} MA} that is equivalent to {a \ ({\rm Mod}) \ b}. For instance, it follows from a short argument of Erdös that {n_{a,A} \in bA}. Indeed we have

\displaystyle n_{a,A} = \sum_{j=1}^r a_j.

If any subsum is {0 \ ({\rm Mod}) \ b}, we may remove it to get a smaller element in {\mathcal{P}(A)} that is {a \ ({\rm Mod}) \ b}. Thus no subsum is {0 \ ({\rm Mod}) \  b}. But this quickly implies that {r \leq b}, 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.

Leave a Reply