\documentclass[12pt]{amsart}
\usepackage{amscd}
\usepackage{amssymb}
\textheight 8.3in
\textwidth 6.2in
\evensidemargin 0pt
\oddsidemargin 0pt
\topmargin -0.1in
\vfuzz 1.75pt
\let\normalshape\upshape
\title{Restricted set addition in groups, II.\\ A generalization of the Erd\H os-Heilbronn conjecture}
\subjclass{Primary: 11B75; Secondary: 11P99, 05C25, 05C35}
\thanks{Partially supported by the Edmund Landau Center for Research in
Mathematical Analysis and Related Areas, sponsored by the Minerva Foundation
(Germany).}
\newcommand{\del}{\delta}
\newcommand{\eps}{\varepsilon}
\newcommand{\lam}{\lambda}
\newcommand{\Gam}{\Gamma}
\newcommand{\cR}{\mathcal{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Zp}{\Z/p\Z}
\newcommand{\seq}{\subseteq}
\newcommand{\stm}{\setminus}
\newcommand{\est}{\varnothing}
\newcommand{\longc}{,\dotsc,}
\newcommand{\longp}{+\dotsb+}
\newcommand{\mmod}[1]{\!\!\!\pmod{#1}}
\newcommand{\rplus}{\mathop{\dot+}}
\newcommand{\tplus}{\mathop{\overset{\tau}{+}}}
\newcommand{\Rplus}{\mathop{\overset{\cR}{+}}}
\newcommand{\pt}[1]{\put(#1){\circle*{3}}}
\newcommand{\li}[3]{\put(#1){\line(#2){#3}}}
\newcommand{\step}[1]{\smallskip\noindent #1\,}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem{conjecture}{Conjecture}
\newtheorem{thprime}{Theorem}
\theoremstyle{definition}
\newtheorem{example}{Example}
\newcommand{\reft}[1]{\ref{t:#1}}
\newcommand{\refc}[1]{\ref{c:#1}}
\newcommand{\refs}[1]{\ref{s:#1}}
\newcommand{\refb}[1]{\cite{b:#1}}
\newcommand{\refe}[1]{\eqref{e:#1}}
\begin{document}
\thispagestyle{empty}
\thinlines
\def\auuu{\begin{center}
\Large
\smallskip
Vsevolod F. Lev\\[0.15in]
\large
Institute of Mathematics\\
Hebrew University\\
Jerusalem 91904, Israel\\[0.1in]
\normalsize \tt
seva@math.huji.ac.il\\[0.15in]
\rm
Submitted: June 18, 1998; Accepted: January 29, 2000
\end{center}}
\author{\auuu}
\begin{abstract}
In 1980, Erd\H os 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\seq\Zp$ 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
$\Zp$.
In this paper we consider restricting conditions of general type and
investigate groups, distinct from $\Zp$. In particular, for $A,B\seq\Zp$ and
$\cR\seq A\times B$ of given cardinalities we give a sharp estimate for the
number of distinct sums $a+b$ with $(a,b)\notin\cR$, and we obtain a partial
generalization of this estimate for arbitrary Abelian groups.
\end{abstract}
\maketitle
\pagestyle{myheadings}
\markboth{\hfill{\sc the electronic journal of combinatorics 7 (2000), \#R4}}
{{\sc the electronic journal of combinatorics 7 (2000), \#R4}\hfill}
\section{Background: mapping restrictions}
For two subsets $A$ and $B$ of the set of elements of a group $G$ we write
$$ A\rplus B = \{a+b\colon a\in A,\; b\in B,\ a\neq b\}. $$
(The group $G=\Zp$ of residues modulo a prime $p$ was historically first to
emerge in this context, hence the additive notation.) In other words,
$A\rplus B$ is the set of all elements of $G$, representable as a sum of two
{\em distinct} elements from $A$ and $B$.
The Erd\H os-Heilbronn conjecture (see \cite[p. 95]{b:EG80}), resolved
(affirmatively) in \refb{DH94} (cf. also \cite{b:ANR95,b:ANR96}) is the
following.
\begin{conjecture}[Erd\H os and Heilbronn]\label{j:EH}
For any two sets $A,B\seq\Zp$,
\begin{equation}\label{e:EH}
|A\rplus B| \ge \min\{|A|+|B|-3,\, p\}.
\end{equation}
\end{conjecture}
The set $A\rplus B$ is obtained from $A+B=\{a+b\colon a\in A,\; b\in B\}$ by
excluding those sums with $b=a$. It seems plausible that \refe{EH} remains
valid even if the sums to be excluded are chosen according to a more general
pattern.
Specifically, given a mapping $\tau\colon A\to B$, we define $A\tplus B$ to
be the set of all the sums $a+b$ such that $b\neq\tau(a)$:
$$ A\tplus B = \{a+b\colon a\in A,\; b\in B,\ b\neq\tau(a)\}. $$
In \refb{BLR98}, we conjectured the following.
\begin{conjecture}[Lev]\label{c:initial}
Let $A$ and $B$ be subsets of $\Zp$ satisfying $|A|\le|B|$, and let
$\tau\colon A\to B$ be an arbitrary mapping from $A$ to $B$. Then
$$ |A\tplus B|\ge \min\{|A|+|B|-3,\, p\}. $$
\end{conjecture}
It turns out, however, that this latter conjecture was too optimistic. Fix
two integers $k,d\ge 1$ such that $(2k+1)(2d-1)\le 2p+1$ and let
\begin{align*}
%1
A &= \{-1,-2,-3\longc -kd\} \mmod p, \\
%2
B &= \{0,d,2d\longc (k+1)d,(k+1)d+1\longc p-1\} \mmod p.
\end{align*}
Furthermore, define $\tau\colon A\to B$ by
$$ \tau(-td+r)=td;\quad 1\le t\le k,\ 0\le r0$ (that is, $\cR\neq\est$). Plainly, when $\cR$ is
induced by a mapping $\tau\colon A\to B$, we have $r=m$.
Our main result for the group $\Zp$ is the following.
\begin{theorem}\label{t:mainp}
Let $A,B\seq\Zp$, and let $\cR\seq A\times B$. Assume for definiteness
$m\le n$. Then
$$ |A\Rplus B| \ge
\begin{cases}
m+n-2\sqrt r-1,\ &\text{if}\quad m+n\le p+\sqrt r\ %
\text{and}\ \sqrt r\le m, \\
p-\frac r{m+n-p},\ &\text{if}\quad m+n\ge p+\sqrt r, \\
n-\frac rm,\ &\text{if}\quad \sqrt r\ge m.
\end{cases} $$
\end{theorem}
Observe, that $m+n\ge p+\sqrt r$ and $\sqrt r\ge m$ can occur simultaneously
only when $n=p$ and $m=\sqrt r$, in which case the two last estimates of
Theorem \reft{mainp} coincide.
Theorem \reft{mainp} is extremely sharp and in fact, establishes the minimum
possible value of the cardinality of the restricted sum $A\Rplus B$. To see
this, consider the following example.
\begin{example}
Let $A=\{0\longc m-1\}\mmod p$ and $B=\{0\longc n-1\}\mmod p$, where
$1\le m\le n\le p$. Fix a positive integer $k$ such that
$$ \frac{m+n-1-p}2 \le k\le \frac{m+n-1}2 $$
and define
$$ \cR := \{(a,b)\colon a\in A,\, b\in B,\ a+b\notin[k,m+n-2-k]\mmod p\}. $$
(Notice, that $\cR$ ``eliminates'' sums $a+b$ with minimal number of
representations. The condition that $k$ is positive ensures that $\cR\neq\est$.)
We have then $A\Rplus B\seq[k,m+n-2-k]\mmod p$, whence
\begin{equation}\label{e:ex}
|A\Rplus B| \le m+n-2k-1.
\end{equation}
Now, if $k$ is chosen to satisfy $m\le k\le (m+n-1)/2$, one can verify that
$$ r=m(2k+1-m)>m^2, $$
% [0,k-1] \cap [k,m+n-2-k] \mmod p = \est
% [m+n-1-k,m+n-2] \cap [k,m+n-2-k] \mmod p = \est
% r= mn-m(m+n-1-2k)
and by \refe{ex},
$$ |A\Rplus B| \le n-\frac rm. $$
If $m+n-p\le k\le m-1$, then
$$ r=k(k+1)p+\sqrt r$ and
$$ |A\Rplus B|\le p-\frac r{m+n-p}. $$
\end{example}
We now turn to generalizations onto groups, distinct from $\Zp$. The second
estimate of Theorem \reft{mainp} has an analog even in the non-commutative
case.
\begin{theorem}\label{t:O}
Let $A,B\seq G$ be subsets of a finite group $G$ of order $q=|G|$, and let
$\cR\seq A\times B$. Suppose that $m+n\ge q+1$. Then
$$ |A\Rplus B|\ge q-\frac r{m+n-q}. $$
\end{theorem}
\begin{corollary}\label{c:O}
Let $G,A,B$ and $\cR$ be as in Theorem \reft{O}. Assume that $m+n\ge(1+\eps)q$
and $r\le C\min\{m,n\}$ for some $\eps,C>0$.
$$ |A\Rplus B|\ge q-C\eps^{-1}. $$
\end{corollary}
\begin{proof}
$$ \frac r{m+n-q} \le
\frac C2\,\frac{m+n}{(m+n)-q} \le
\frac C2\,\frac1{1-(1+\eps)^{-1}} =
\frac C2\left(1+\frac1{\eps}\right) < C\eps^{-1}. $$
\end{proof}
A refinement is possible when $\cR$ is induced by an injective mapping and
the sum $m+n$ only slightly exceeds $q$.
\begin{theorem}\label{t:rectangle}
Let $A,B\seq G$ be subsets of a finite group $G$ of order $q=|G|$, and let
$\tau\colon A\to B$ be an injective mapping from $A$ to $B$. Suppose that
$m+n\ge q+1$. Then
$$ |A\tplus B|>q-\sqrt q-\frac 12. $$
\end{theorem}
In a certain (rather narrow) range of $m,n$ and in the particular case of
$\cR$ induced by an injective mapping, Theorem \reft{rectangle} improves
Theorem \reft{mainp}.
To deal with the generalization of the most important and most difficult case
of Theorem \reft{mainp} --- that of small $m+n$ --- we make a simplifying
assumption that $\cR$ satisfies the following conditions:
\begin{itemize}
\item[(a)] to any fixed $a_0\in A$ there corresponds at most one $b\in B$
such that $(a_0,b)\in\cR$;
\item[(b)] to any fixed $b_0\in B$ there corresponds at most one $a\in A$
such that $(a,b_0)\in\cR$.
\end{itemize}
We note that these conditions automatically hold when $\cR$ is induced by an
injective mapping; in general, they are not vital, but make possible certain
simplifications. Furthermore, for real $L>0$ we consider an additional
condition:
\begin{itemize}
\item[(c)] for any $c\in G$ there are at most $L$ pairs $(a,b)\in\cR$ such
that $a+b=c$.
\end{itemize}
The relevance of this condition for the estimates of $|A\Rplus B|$ is hinted
to by \cite[Conjecture 2]{b:L00} and \cite[Theorem 3]{b:L00}: when $\cR$ is
induced by the equality relation, $L$ can be chosen to be the ``doubling
constant'' of \refb{L00}.
Our next result is parallel to \cite[Theorem 3]{b:L00}. The difference is that
in \refb{L00} we were only concerned with the ``classical'' restriction
$b\neq a$ and considered only the case $B=A$; on the other hand, the latter
allowed us to cover non-commutative groups.
\begin{theorem}\label{t:maing}
Let $G$ be an Abelian group, let $A,B\seq G$ be subsets of $G$, and let $\cR$
satisfy conditions {\normalshape (a)--(c)}. Suppose that $A\Rplus B\neq A+B$.
Then
\begin{equation}\label{e:maing}
|A\Rplus B| > (1-\del)(m+n)-(L+2),
\end{equation}
where
$$ \del=\frac{mn}{(m+n)^2}\le \frac 14. $$
\end{theorem}
The condition $A\Rplus B\neq A+B$ may look odd at first sight and is worth
explanation. The point is that there is such a powerful tool as Kneser's
theorem to estimate the number of elements of the {\em non-restricted} sum
$A+B$ from below. If $A\Rplus B=A+B$, this theorem automatically yields
lower-bound estimates for the number of elements of the {\em restricted} sum
$A\Rplus B$; Theorem \reft{maing} deals with the complementary case
$A\Rplus B\neq A+B$. To be more specific, if \refe{maing} fails, while
$A\Rplus B=A+B$, then it follows immediately from Kneser's theorem that $A$
and $B$ posses a very rigid structure:
\begin{itemize}
\item[--] either there exist elements $a\in A,\,b\in B$ and a subgroup
$H\seq G$ such that $A\seq a+H,\,B\seq b+H,\,m+n\ge 4(|H|+L+2)/3$, and
$$ A\Rplus B=A+B=a+b+H; $$
\item[--] or there exist elements $a_1,a_2\in A,\,b\in B$ and a subgroup
$H\seq G$ such that
$A\seq(a_1+H)\cup(a_2+H),\,B\seq b+H,\,m+n\ge 8(|H|+L+2)/3$, and
$$ A\Rplus B=A+B=(a_1+b+H)\cup(a_2+b+H), $$
\item[--] or there exist elements $a\in A,\,b_1,b_2\in B$ and a subgroup
$H\seq G$ such that
$A\seq a+H,\,B\seq(b_1+H)\cup(b_2+H),\,m+n\ge 8(|H|+L+2)/3$, and
$$ A\Rplus B=A+B=(a+b_1+H)\cup(a+b_2+H). $$
\end{itemize}
%The last result of this paper is a uniform version of Theorem \reft{maing}.
%
%\begin{thprime}
%Let $G$ be an Abelian group, let $A,B\seq G$ be subsets of $G$, and let $\cR$
%satisfy conditions (a) and (b). Suppose that $A\Rplus B\neq A+B$. Then
%\begin{equation}
% |A\Rplus B| > (1-\del)(m+n)-(2\sqrt r+2),
%\end{equation}
%where $\del$ is defined as above.
%\end{thprime}
The coefficient $1-\del$ in Theorem \reft{maing} can be slightly improved using
the methods of \refb{L00}; in particular, for $B=A$ it can be increased to
$(\sqrt 5+1)/4\approx 0.80$.
The proofs of Theorems \reft{mainp}--\reft{maing} are mostly combinatorial,
with a somewhat surprising interference of graph theory in the proof of
Theorem \reft{rectangle} --- see also Section \refs{conclusion}, the
Conclusion.
\section{Proofs}\label{s:proofs}
\begin{proof}[Proof of Theorem 1]
For $i=1,2,\dots$ we denote by $N_i$ the number of residues $c\in A+B$ with at
least $i$ representations of the form $c=a+b\ (a\in A,\,b\in B)$, and by $N_i'$
the number of residues $c\in(A+B)\stm(A\Rplus B)$ with at least $i$
representations of this form. Obviously, $N_i-N_i'$ counts the number
of elements of $A\Rplus B$ with at least $i$ representations, whence
$N_i-N_i'\le |A\Rplus B|$ and
\begin{equation}\label{e:tARB}
t|A\Rplus B| \ge (N_1-N_1')\longp(N_t-N_t')
\end{equation}
for any integer $t\ge 1$.
Now, by Pollard's theorem (see \refb{P74}) we have
$$ N_1\longp N_t\ge t\min\{p,m+n-t\}, $$
provided $t\le m$, and at the same time, clearly
$$ N_1'\longp N_t'\le N_1'\longp N_t'+\dotsb =
\sum_{c\in(A+B)\stm(A\Rplus B)}\nu(c) \le r, $$
where $\nu(c)$ is the number of representations of $c$. Comparing to
\refe{tARB} we conclude that
\begin{align*}
%1
t|A\Rplus B| &\ge t\min\{p,m+n-t\}-r, \\
%2
|A\Rplus B| &\ge \min\{p-r/t,m+n-(t+r/t)\},
\end{align*}
and it remains to optimize in $t$ by choosing
$$ t = \begin{cases}
\lceil\sqrt r\,\rceil,\ &\text{if}\quad m+n\le p+\sqrt r\ %
\text{and}\ \sqrt r\le m, \\
m+n-p,\ &\text{if}\quad m+n\ge p+\sqrt r, \\
m,\ &\text{if}\quad \sqrt r\ge m.
\end{cases} $$
\end{proof}
\begin{proof}[Proof of Theorem \reft{O}]
Let $S$ be the complement of $A\Rplus B$ in $G$, so that $|S|=q-|A\Rplus B|$.
By the Dirichlet boxing principle, to any $s\in S$ there correspond at least
$m+n-q$ pairs $(a,b)$ (with $a\in A,\,b\in B$) such that $a+b=s$, and for any
such pair we have $(a,b)\in\cR$. Totally, we have at least $|S|(m+n-q)$ pairs
$(a,b)\in\cR$. On the other hand, the number of these pairs is $r$, whence
$|S|\le r/(m+n-q)$, and the result follows.
\end{proof}
\begin{proof}[Proof of Theorem \reft{rectangle}]
We define $S$ as above, and we want to prove that $|S|<\sqrt q+1/2$.
It is convenient to use graph-theoretic terminology. Consider the
$|S|$-regular bipartite graph $\Gam$ on two disjoint copies of $G$, obtained
by joining each vertex $x\in G$ of the first copy to the $|S|$ vertices
$-x+s;\ s\in S$ of the second copy. Formally, we write
$$ \Gam=(X\cup Y,E);\quad E=\{(x,y)\colon x\in X,\, y\in Y,\, x+y\in S\}, $$
where $X$ and $Y$ are thought of as two disjoint copies of $G$. Furthermore,
consider the subgraph $\Gam_0\seq\Gam$, induced by all elements of $A$ in the
first copy and all elements of $B$ in the second copy:
$$ \Gam_0 = \langle(X\cap A)\cup(Y\cap B)\rangle. $$
We claim that $\Gam_0$ contains no paths of length two. Indeed, a path
$x_1,y,x_2$ with $x_1,x_2\in X\cap A$ and $y\in Y\cap B$ would mean
$x_1+y\in S$ and $x_2+y\in S$, which is impossible: either $\tau(x_1)\neq y$
(in which case $x_1+y\notin S$), or $\tau(x_2)\neq y$ (in which case
$x_2+y\notin S$). Similarly, a path of the type $y_1,x,y_2$ cannot occur in
$\Gam_0$ as $\tau(x)=y_1$ and $\tau(x)=y_2$ cannot happen simultaneously.
Our next observation is that $\Gam$ contains no rectangles. Indeed, any single
rectangle $x_1,y_1,x_2,y_2$ can be translated to produce $q$ rectangles
$$ x_1+u,-u+y_1,x_2+u,-u+y_2;\quad u\in G, $$
each containing at most two vertices of $\Gam_0$: a subgraph induced by any
{\em three} vertices of a rectangle necessarily contains a path of length two.
Summation over all $u\in G$ gives $2(|A|+|B|)\le 2q$, contradicting the
assumptions.
We now essentially repeat an Erd\H os' argument to show that if $\Gam$
contains no rectangles, then $|S|$ (the degree of $\Gam$) is small. We first
count all paths of the form $x_1,y,x_2\ (x_1,x_2\in X,\, y\in Y)$ in $\Gam$.
Obviously, there are totally $q\binom{|S|}2$ such paths, as any vertex
$y\in Y$ participates in $\binom{|S|}2$ paths. On the other hand, there are
only $\binom q2$ pairs $(x_1,x_2);\ x_i\in X$ with $x_1\neq x_2$. Since no
two distinct paths can share a common pair (this would yield a rectangle),
we have
\begin{gather}
%1
q\binom{|S|}2\le\binom q2, \notag \\
%2
|S|^2-|S|+1\le q \label{e:sidcard}
\end{gather}
whence $|S|<\sqrt q+1/2$, as required.
There is another way to complete the proof by making a funny observation that
$S$ is a Sidon set in $G$: an equality $s_1-s_2=s_1'-s_2'$ with
$s_1\neq s_2,\ s_1\neq s_1'$ creates a rectangle
$s_1,0,s_2,-s_2+s_2'=-s_1+s_1'$. It is easy to verify, however, that the
cardinality of any Sidon set $S\seq G$ satisfies \refe{sidcard}.
\end{proof}
\begin{proof}[Proof of Theorem \reft{maing}]
We break the proof in three steps.
\step{i)}
Since $A\Rplus B\neq A+B$, there exist $a_0\in A$ and $b_0\in B$ such that
$c=a_0+b_0\notin A\Rplus B$. Then
$$ |(A-b_0)\cap(a_0-B)|\le L, $$
as any equality $a-b_0=a_0-b$ gives rise to the representation $c=a+b$ with
$(a,b)\in\cR$ (in view of $c\notin A\Rplus B$), and there are at most $L$
such representations. Letting $A-B=\{a-b\colon a\in A,\,b\in B\}$ we obtain
\begin{equation}\label{e:A-B}
|A-B| \ge |(A-b_0)\cup(a_0-B)| \ge m+n-L.
\end{equation}
\step{ii)}
Fix any $c=a_0-b_0\in A-B$ (where $a_0\in A,\,b_0\in B)$ and let
$$ A_0=\{a\in A\colon (a,b_0)\notin\cR\}, \quad
B_0=\{b\in B\colon (a_0,b)\notin\cR\}, $$
so that $|A_0|\ge m-1$ and $|B_0|\ge n-1$ by the conditions (a) and (b).
Write $\nu(c)$ for the number of representations
$c=a-b\ (a\in A,\,b\in B)$. Then
\begin{align}
%1
\nu(c) &\ge |(a_0+B_0)\cap(A_0+b_0)| \ge |A_0|+|B_0|-|A\Rplus B| \notag \\
%2
&\ge m+n-2-|A\Rplus B|, \label{e:nu}
\end{align}
as $(a_0+B_0)\cup(A_0+b_0)\seq A\Rplus B$.
\step{iii)}
By \refe{A-B} and \refe{nu},
\begin{align*}
%1
mn &= \sum_{c\in A-B} \nu(c) \ge (m+n-L)(m+n-2-|A\Rplus B|), \\
%2
|A\Rplus B| &\ge m+n-2-\frac{mn}{m+n-L} \\
%3
&> m+n-\frac{mn}{m+n}-(L+2),
\end{align*}
the latter inequality being equivalent to $mn<(m+n)(m+n-L)$,
which follows from $L<(1-\del)(m+n)$ --- otherwise, the assertion of the
theorem is trivial.
The result follows.
\end{proof}
\section{Conclusion}\label{s:conclusion}
We re-state here explicitly several problems that remain open.
\medskip
{\em Does \refe{newc} hold for any two sets $A,B\seq\Zp$ and any injective
mapping $\tau\colon A\to B$? In particular, is it true that
$|A\tplus B|\ge p-2$, provided $|A|+|B|\ge p+2$? Do similar estimates hold
when $A$ and $B$ are subsets of an arbitrary finite group? If some of the
answers are negative, what are the best possible estimates of this sort?}
\medskip
A slight modification of the approach used in the proof of Theorem
\reft{rectangle} shows that for $|A|+|B|\ge p+2$, this problem can be
reformulated in the graph-theoretic language as follows.
\medskip
{\em Let $c\neq 0,1$ be any fixed residue modulo $p$. Consider a cubic
bipartite graph $\Gam(c)$ on two copies of $\Zp$ such that any vertex $x$ of
the first copy is adjacent to the vertices $x,x+1$ and $x+c$ of the second
copy. Is it true that any induced subgraph of order $p+2$ of any such
$\Gam(c)$ contains a path of length two?}
\medskip
The answer is certainly positive if $c=-1,2$ or $(p+1)/2$ (in which cases
$\Gam(c)$ contains a rectangle). In general, the situation is not clear,
however.
The major open problem for generic restriction is that of improving the
coefficient $1-\del$ in Theorem \reft{maing}. Quite likely, this coefficient
can be replaced by $1$ or at least by $1-\eps$ for any positive $\eps$,
provided $r$ is sufficiently (in terms of $\eps$) small compared to $m+n$.
\section*{Acknowledgment}
The (core of the) present form of Theorem \reft{mainp} and an idea
incorporated in the proof of Theorem \reft{rectangle} are due to Noga Alon,
whom we are greatly indebted for this contribution.
\begin{thebibliography}{99999}
\bibitem{b:ANR95} {\sc N.~Alon, M.B.~Nathanson} and {\sc I.Z.~Ruzsa}, Adding
distinct congruence classes modulo a prime, {\em American Math. Monthly},
{\bf 102} (1995), 250--255.
\bibitem{b:ANR96} {\sc N.~Alon, M.B.~Nathanson} and {\sc I.Z.~Ruzsa}, The
Polynomial Method and Restricted Sums of Congruence Classes, {\it J.~Number
Theory}, {\bf 56} (1996), 404--417.
\bibitem{b:BLR98} {\sc Y.~Bilu, V.F.~Lev} and {\sc I.Z.~Ruzsa}, Rectification
principles in additive number theory, {\em Disc. and Comput. Geometry},
{\bf 19} (1998), 343--353.
\bibitem{b:DH94} {\sc J.A.~Dias~da~Silva} and {\sc Y.O.~Hamidoune}, Cyclic
spaces for Grassmann derivatives and additive theory, {\em Bull. London
Math. Soc.} {\bf 26} (1994), 140--146.
\bibitem{b:EG80} {\sc P.~Erd\H os} and {\sc R.L.~Graham}, {\em Old and new
problems and results in combinatorial number theory}, L'{E}nseignement
Math\'ematique, Geneva, 1980.
\bibitem{b:L00} {\sc V.F.~Lev}, Restricted set addition in groups. I. The
classical setting, {\em Journal of the London Mathematical Society}, to
appear.
\bibitem{b:P74} {\sc J.M.~Pollard}, A generalization of the theorem of Cauchy
and Davenport, {\em J.~London Math. Soc.} {\bf 2} (8) (1974), 460--462.
\end{thebibliography}
\end{document}