Restricted set addition in groups. II: A generalization of the Erdős-Heilbronn conjecture

Vsevolod F. Lev

The electronic journal of combinatorics, Tome 7 (2000)

Résumé

In 1980, Erdős and Heilbronn posed the problem of estimating (from below) the number of sums $a+b$ where $a\in A$ and $b\in B$ range over given sets $A,B\subseteq{\Bbb Z}/p{\Bbb Z}$ of residues modulo a prime $p$, so that $a\neq b$. A solution was given in 1994 by Dias da Silva and Hamidoune. In 1995, Alon, Nathanson and Ruzsa developed a polynomial method that allows one to handle restrictions of the type $f(a,b)\neq 0$, where $f$ is a polynomial in two variables over ${\Bbb Z}/p{\Bbb Z}$. In this paper we consider restricting conditions of general type and investigate groups, distinct from ${\Bbb Z}/p{\Bbb Z}$. In particular, for $A,B\subseteq{\Bbb Z}/p{\Bbb Z}$ and ${\cal R}\subseteq A\times B$ of given cardinalities we give a sharp estimate for the number of distinct sums $a+b$ with $(a,b)\notin\ {\cal R}$, and we obtain a partial generalization of this estimate for arbitrary Abelian groups.

Détail

DOI : 10.37236/1482

Classification : 11B75, 05D99, 20F99
Mots-clés : sumsets, restricted set addition, cyclic group of prime order