Revista Matemática Iberoamericana


Full-Text PDF (208 KB) | Metadata | Table of Contents | RMI summary
Volume 21, Issue 1, 2005, pp. 133–161
DOI: 10.4171/RMI/418

Published online: 2005-04-30

A multiple set version of the $3k-3$ Theorem

Yahya ould Hamidoune[1] and Alain Plagne[2]

(1) Université Pierre et Marie Curie, Paris, France
(2) Ecole Polytechnique, Palaiseau, France

In 1959, Freiman demonstrated his famous $3k-4$ Theorem which was to be a cornerstone in inverse additive number theory. This result was soon followed by a $3k-3$ Theorem, proved again by Freiman. This result describes the sets of integers $\mathcal{A}$ such that $| \mathcal{A}+\mathcal{A} | \leq 3 | \mathcal{A} | -3$. In the present paper, we prove a $3k-3$-like Theorem in the context of multiple set addition and describe, for any positive integer $j$, the sets of integers $\mathcal{A}$ such that the inequality $|j \mathcal{A} | \leq j(j+1)(| \mathcal{A} | -1)/2$ holds. Freiman's $3k-3$ Theorem is the special case $j=2$ of our result. This result implies, for example, the best known results on a function related to the Diophantine Frobenius number. Actually, our main theorem follows from a more general result on the border of $j\mathcal{A}$.

Keywords: $3k-3$ theorem, multiple set addition, $3k-4$ theorem, structure theory of set addition, Frobenius problem

Hamidoune Yahya ould, Plagne Alain: A multiple set version of the $3k-3$ Theorem. Rev. Mat. Iberoam. 21 (2005), 133-161. doi: 10.4171/RMI/418