×

zbMATH — the first resource for mathematics

A multiple set version of the \(3k-3\) theorem. (English) Zbl 1078.11059
The authors introduce to Freiman’s inverse theorems and prove the following theorem, which is a classification of sets with small sumsets: Let \(A\) be a set of non-negative integers with \(\min A=0, \max A=M\),and \(\gcd A=1\). Let \(j\geq 2\) be an integer. Let \(jA\) denote the \(j\)-fold sumset. If the upper bound \(| jA | \leq \frac{j(j+1)}{2} ( | A| -1)\) holds, then one of the following happens:
\(| A | \geq 1+ \frac{M}{j}\).
\(A\) is the union of two arithmetic progressions with the same common difference.
\(A\) is an arithmetic progression modulo \(M\).
\(M\) is even and \(A\) is of the form \(A=\{0,M/2,M,x,x+M/2, 2x\}\) for some positive integer \(x<M/2\).
The special case \(j=2\) is a famous theorem by G. A. Freiman [Izv. Vyssh. Uchebn. Zaved., Mat. 1959, No. 6(13), 202–213 (1959; Zbl 0096.25904)]. Freiman’s theorem is also called the \(3k-3\) theorem; the third alternative does not occur in this case.
The paper concludes with an application to the Frobenius problem.

MSC:
11P70 Inverse problems of additive number theory, including sumsets
11B75 Other combinatorial number theory
PDF BibTeX XML Cite
Full Text: DOI EuDML
References:
[1] Cauchy, A.-L.: Recherches sur les nombres. J. École Polytech. 9 (1813), 99-123.
[2] Davenport, H.: On the addition of residue classes. J. London Math. Soc. 10 (1935), 30-32. · Zbl 0010.38905 · doi:10.1112/jlms/s1-10.37.30
[3] Dixmier, J.: Proof of a conjecture by Erdös and Graham concerning the problem of Frobenius. J. Number Theory 34 (1990), 198-209. · Zbl 0695.10012 · doi:10.1016/0022-314X(90)90150-P
[4] Erdös, P., Graham, R. L.: On a linear Diophantine problem of Frobe- nius. Acta Arith. 21 (1972), 399-408. · Zbl 0246.10010 · eudml:205124
[5] Freiman, G. A.: On the addition of finite sets. I. Izv. Vys\check s. U\check cebn. Zaved. Matematika 6 (13) (1959), 202-213.
[6] Freiman, G. A.: Inverse problems of additive number theory. VI. On the addition of finite sets. III. The method of trigonometric sums. Izv. Vys\check s. U\check cebn. Zaved. Matematika 3 (28) (1962), 151-157.
[7] Freiman, G. A.: Foundations of a structural theory of set addition. Tran- sations of Mathmatical Monographs 37. American Mathematical Society, Providence, R. I., 1973. · Zbl 0271.10044
[8] Freiman, G. A.: Structure theory of set addition. Astérisque 258 (1999), 1-33. 161 · Zbl 0958.11008
[9] ould Hamidoune, Y.: Some results in additive number theory I: The critical pair theory. Acta Arith. 96 (2000), no. 2, 97-119. · Zbl 0985.11011 · doi:10.4064/aa96-2-1
[10] ould Hamidoune, Y.: On the Diophantine Frobenius problem. Portugal. Math. 55 (1998), no. 4, 425-449. · Zbl 0923.11044 · eudml:48257
[11] ould Hamidoune, Y., Plagne, A.: A generalization of Freiman’s 3k - 3 theorem. Acta Arith. 103 (2002), no. 2, 147-156. · Zbl 1007.11011 · doi:10.4064/aa103-2-4
[12] ould Hamidoune, Y., Plagne, A.: A new critical pair theorem applied to sum-free sets in Abelian groups. Comment. Math. Helv. 79 (2004), no. 1, 183-207. · Zbl 1045.11072 · doi:10.1007/s00014-003-0786-5
[13] Lev, V. F., Smeliansky, P. Y.: On addition of two distinct sets of inte- gers. Acta Arith. 70 (1995), no. 1, 85-91. · Zbl 0817.11005 · eudml:206738
[14] Lev, V. F.: Structure theorem for multiple addition and the Frobenius problem. J. Number Theory 58 (1996), 79-88. · Zbl 0853.11017 · doi:10.1006/jnth.1996.0065
[15] Lewin, M.: A bound for a solution of a linear Diophantine problem. J. Lon- don Math. Soc. (2) 6 (1972), 61-69. · Zbl 0246.10009 · doi:10.1112/jlms/s2-6.1.61
[16] Nathanson, M. B.: Additive number theory. Inverse problems and the geometry of sumsets. Graduate Texts in Mathematics 165. Springer-Verlag, New York, 1996. · Zbl 0859.11003
[17] Steinig, J.: On Freiman’s theorems concerning the sum of two finite sets of integers. Astérisque 258 (1999), 129-140. · Zbl 0962.11032
[18] Sylvester, J. J.: Mathematical questions with their solutions. Educa- tional Times 41 (1884), 21.
[19] Vosper, A. G.: The critical pairs of subsets of a group of prime order. J. London Math. Soc. 31 (1956), 200-205. Addendum to “The critical pairs of subsets of a group of prime order”, J. London Math. Soc. 31 (1956), 280-282. · Zbl 0072.03402 · doi:10.1112/jlms/s1-31.2.200
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.