Subset sums in binary spaces. (English) Zbl 0772.11004

Zémor, Gilles

Eur. J. Comb. 13, No. 3, 221-230 (1992).

Sei \(G=Z_ 2^ L\) die Gruppe der binären Vektoren der Länge \(L\). Dann zeigt Verf. den folgenden Satz (Theorem 1.4): Sei \(S\) eine Teilmenge von \(G\) und \(k\in\mathbb{N}_ 0\). Dann gilt entweder (i) es gibt eine echte Untergruppe \(H\) von \(G\), so daß \(| S+H|-| S|<| H|+k\) oder (ii) für jede Teilmenge \(T\) von \(G\) mit \(k\leq| T|^ 2-2\) und \(2\leq| G|-| S+T|\) gilt \(| S+T|\geq | S|+| T|+k\). Am Schluß wird auf zwei Anwendungen hingewiesen.

Reviewer: E.Härtter (Mainz)

MSC:

11B05	Density, gaps, topology
20D60	Arithmetic and combinatorial problems involving abstract finite groups
20K01	Finite abelian groups

Keywords:

sum sets; lower bound; cardinality; sets of binary vectors of given length; abelian group; Kneser’s theorem

References:

[1]	Alon, N., Subset sums, J. Number Theory, 27, 2, 196-205 (1987) · Zbl 0622.10042
[2]	Cohen, G.; Ze´mor, G., An application of combinatorial theory to coding, Ars Combin., 23A, 84-94 (1987)
[3]	Deza, M., Racine minimum d’un groupee´le´mentaire abe´lien, Can. J. Math., XXVII, 4, 819-826 (1975) · Zbl 0308.20045
[4]	Diderrich, G. T., On Kneser’s addition theorems in groups, (Proc. Am. Math. Soc., 38 (1973)), 443-451, (3) · Zbl 0266.20041
[5]	Eggleton, R. B.; Erdo¨s, P., Two combinatorial problems in group theory, Acta Arith., XXI, 111-116 (1972) · Zbl 0248.20068
[6]	Hamidoune, Y. O., Sur la se´paration dans les graphes de Cayley abe´liens, Discr. Math., 55, 323-326 (1985) · Zbl 0567.05027
[7]	Harper, L. H., Optimal numberings and isoperimetric problems on graphs, J. Combin. Theory, 1, 385-393 (1966) · Zbl 0158.20802
[8]	Kneser, M., Abscha¨tzung der asymptotischen Dichte von Summenmengen, Math. Z., 58, 549 (1953) · Zbl 0051.28104
[9]	Mann, H. B., (Addition Theorems: The Addition Theorems of Group Theory and Number Theory (1965), Interscience: Interscience New York) · Zbl 0127.27203
[10]	Mann, H. B.; Olson, J. E., Sums of sets in the elementary abelian group of type (p, p), J. Combin. Theory, 2, 275-284 (1967) · Zbl 0168.01501
[11]	Olson, J. E., An addition theorem mod \(p\), J. Combin. Theory, 5, 45-52 (1968) · Zbl 0174.05202
[12]	Olson, J. E., An addition theorem for finite abelian groups, J. Number Theory, 9, 1, 63-70 (1977) · Zbl 0351.20032
[13]	Olson, J. E., A problem of Erdo¨s on abelian groups, Combinatorica, 7, 3, 285-289 (1987) · Zbl 0643.20031
[14]	Ze´mor, G., Proble“mes combinatoires lie´sa‘l”e´criture sur des me´moires, (doctoral dissertation (November 1989), Ecole Nationale Supe´rieure des Te´le´communications)
[15]	Ze´mor, G., An extremal problem related to the covering radius of binary codes, (First French-Soviet Workshop on Algebraic Coding, Proceedings. First French-Soviet Workshop on Algebraic Coding, Proceedings, Lecture Notes in Computer Science 573 (1992), Springer-Verlag) · Zbl 0859.94032