\documentclass[12pt,leqno]{article}
\usepackage{latexsym}
\textwidth= 6.25in
\textheight= 9.0in
\topmargin = -10pt
\evensidemargin=10pt
\oddsidemargin=10pt
\headsep=25pt
\parskip=10pt
\font\smallit=cmti10
\font\smalltt=cmtt10
\font\smallrm=cmr9 

\newcommand{\fp}{{\bf F}_p}
\newcommand{\ft}{{\bf F}_3}
\newcommand{\esp}{\hspace{0.32mm}}
\newcommand{\espp}{\hspace{1mm}}
\newcommand{\vespa}{\vspace{0mm}}
\newcommand{\ekf}{[{\bf EK}1]}
\newcommand{\eks}{[{\bf EK}2]}
\newcommand{\cop}{\hspace{0.5mm} \coprod \hspace{0.5mm}}
\newcommand{\suchthat}{\hspace{1mm} | \hspace{1mm}}
\newcommand{\mat}[4]{{\left( \begin{array}{cc}
#1 & #2 \\ #3 & #4 \end{array} \right)}}


\begin{document} 
\begin{center}
{\bf RESTRICTED SUMSETS IN FINITE VECTOR SPACES:\\ THE CASE
${\mathbf{p=3}}$}
\vskip 20pt
{\bf Shalom Eliahou} \\ % \footnote{any footnote here}}\\
{\smallit D\'epartement de Math\'ematiques, Universit\'e du Littoral 
C\^ote d'Opale, B.P. 699, 62228 Calais, France}\\
{\tt eliahou@lmpa.univ-littoral.fr}\\ %(optional)
\vskip 10pt
{\bf Michel Kervaire} \\ % \footnote{any footnote here}}\\
{\smallit D\'epartement de Math\'ematiques, Universit\'e de Gen\`eve, 
B.P. 240, 1211 Gen\`eve 24, Suisse}\\
%{\tt you@math.two.edu}\\ (optional)
\end{center}
\vskip 30pt
\centerline{\smallit Received:  3/31/2000, Revised:  1/2/01, Accepted:
2/27/01,
Published:  3/9/01 }
\vskip 30pt 
\centerline{\bf Abstract}

\noindent
 We determine the sharp lower bound for the cardinality of the
restricted sumset $A +' B = \{a + b \suchthat a \in A, b \in B, a \neq b \}$,
where $A, B$ run over all subsets of size $r = s = 1 + 3^{h}$ in a vector
space over $\ft$. This solves a conjecture stated in an earlier paper of ours
on sumsets and restricted sumsets in finite vector spaces.

The analogous problem for an arbitrary prime $p$ remains open. However,
we do prove some partial results concerning more generally special pairs 
of the form $r = s = 1 + ap^{h}$.

We also provide alternate proofs for the formulas satisfied by our general
lower bounds $\beta_{p}(r, s)$ and $\gamma_{p}(r, s)$ for the cardinality of
the ordinary sum and restricted sum of sets of size $r, s$ in a vector space
over $\fp$.


\pagestyle{myheadings}
\markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL 
NUMBER THEORY \smalltt 1 (2001), \#A02\hfill} 
\thispagestyle{empty} 
\baselineskip=15pt 
\vskip 20pt 
\section*{\normalsize 1. Introduction}
Let $V$ be a vector space over the finite field $\fp$. If $A, B \subset
V$ are two non-empty subsets of $V$, we define their restricted sumset
$A+'B$ by
$$
A +' B \espp = \espp \{a+b \suchthat a \in A, b \in B, a \neq b \}.
$$

If $r, s \leq |V|$, we define
$$
\mu_{V}'(r, s) \espp = \espp \mbox{ min }|A +' B|,
$$
where $A, B$ run over all subsets of $V$ of cardinality $r, s$ respectively.

Erd\H{o}s and Heilbronn conjectured in 1964 that if $A$ is a subset of 
cardinality $r$ in $V = \fp$, then $|A +' A| \geq \mbox{ min}\{p, 2r-3\}.$ 
This conjecture was solved 30 years later by Dias da Silva and Hamidoune in 
[{\bf DH}]. Using a different method, Alon, Nathanson and Ruzsa subsequently 
strengthened this result by establishing the equality
$$
\mu'_{\fp}(r,s)=\left\{
\begin{array}{ll}
{\rm min}\{p,2r-3\} \; & \,  \mbox{ if } r = s, \\
{\rm min}\{p,r+s-2\} \; & \, \mbox{ if } r \not = s.
\end{array}
\right.
$$
(See [{\bf ANR}1, {\bf ANR}2].)

The determination of $\mu'_V(r,s)$ for an arbitrary vector space $V$ over $\fp$
was taken up and completed for most pairs $r,s$ in \ekf. In summary, we have
determined the value of $\mu'_V(r,s)$ for all $r,s$ if $p=2$, and for all 
non-special pairs $(r, s)$ is $p$ an odd prime. (See Section 2.) The problem
of determining $\mu'_V(r,s)$ remains open for special pairs $(r,s)$.

A pair of natural numbers $(r, s)$ is said to be {\bf special} for the odd
prime $p$ if $r$ and $s$ have $p$-adic expansions of the form
\begin{equation} \left\{ \begin{array}{ccl}
r & = & 1 + ap^{h} + \sum_{i=h+1}^{n} r_{i}p^{i}, \\
s & = & 1 + ap^{h} + \sum_{i=h+1}^{n} s_{i}p^{i},
\end{array} \right.
\end{equation}

\noindent with $h \geq 1$ and coefficients $a, r_{i}, s_{i}$ satisfying the
conditions
\begin{equation} \left\{ \begin{array}{l}
1 \leq a \leq \frac{p-1}{2}, \espp \mbox{ and } \\
r_{i}+ s_{i} \leq p-1 \espp \mbox{ for } h+1 \leq i \leq n.
\end{array} \right.
\end{equation}

\vespa

We do know that for a special pair $(r, s)$, we have either
$\mu_{V}'(r, s)$ = $r+s-3$ or else $\mu_{V}'(r, s)$ = $r+s-2$.
(See Corollary (7.5) in \ekf.) However resolving this alternative seems
to be quite difficult.

The case $r = s = 1 + p$ has been treated in our previous paper \eks. With
the notation $\mu_{p}'(r, s)$ = min$_{_{V}}\{\mu_{V}'(r, s)\}$, we proved that

\vespa

\centerline{$\mu_{p}'(1+p, 1+p)$ = $2(1+p) - 2$ = $2p$,}

\vespa

\noindent for $p \geq 5$. (See \eks, Theorem (1.1).)

Although we have some partial results for certain special pairs with an
arbitrary prime $p$, we do not have any complete treatment beyond the case
$r = s = 1 + p$, at least for $p \geq 5$.

\vespa

For $p = 3$, there is the example $A = B = \{0,\espp e_1,\espp e_2, 
\espp e_1 + e_2\}$ \espp in the plane $V = \ft e_1 \oplus \ft e_2$ \espp with 
$|A| = |B| = 4$ \espp and \espp $|A +' B|$ $=$ $|\{e_1,\espp e_2,\espp e_1 + e_2,
\espp 2e_1 + e_2, \espp e_1 + 2e_2\}| = 5$ realizing the lower bound \espp 
$\mu_{3}'(4, 4) = 5 = r + s - 3$ \espp for $r = s = 4$.

We know from Theorem (7.10) in {\ekf} that the existence of this simple
example implies that if $r, s$ have 3-adic expansions of the form

\[ \left\{ \begin{array}{ccl}
r & = & 1 + 3 + \sum_{i \geq 2} r_{i}3^{i}, \\
s & = & 1 + 3 + \sum_{i \geq 2} s_{i}3^{i},
\end{array} \right. \]

\noindent where $r_{i} + s_{i} \leq 2$ for all $i \geq 2$, then
$\mu_{3}'(r, s)$ = $r + s - 3$.

\vespa

In the present paper, we solve the question of determining the value of
$\mu_{V}'(r, s)$ at $p = 3$ for the particular special pairs $(r, s)$ of
the form

\vespa

\centerline{$r \espp = \espp s \espp = \espp 1 + 3^{h}$,}

\vespa
\noindent where $h \geq 2$. The corresponding problem for 
$p \geq 5$ remains open.

\vespa

Our main result, which was conjectured in {\ekf} at least for $h = 2$, is :

\noindent
{\bf Theorem.} {\em Let $A, B \subset V$ be subsets of cardinality $1 + 3^{h}$
with $h \geq 2$ in a vector space $V$ over $\ft$. Then, }

\vespa

\centerline{$|A +' B| \espp \geq \espp 2 \cdot 3^{h}$.}

\vespa
\noindent
{\em This lower bound $2 \cdot 3^{h}$  is sharp, {\em i.e.},
$\mu_{3}'(1+3^{h}, 1+3^{h})$ = $2 \cdot 3^{h}$.}

The above examples of special pairs $(r, s)$ with $r \equiv s \equiv 4$
mod $3^{2}$ happen in fact to be the only examples we know of special 
pairs $(r, s)$ for which $\mu_{p}'(r, s)$ attains the lower bound $r+ s-3$.


Although $(1+3^{h}, 1+3^{h})$ is a special pair (for the prime 3), the proof
of the above result requires lower bounds for the cardinalities of
sumsets and restricted sumsets for sets $X, Y \subset V$ whose cardinalities
do not necessarily form a special pair.

Formulas for these lower bounds $\beta_{p}(r, s)$ and $\gamma_{p}(r, s)$,
for arbitrary odd prime $p$, were given in \ekf. In the next section we
provide a somewhat different treatment of their proof and recall some needed
basic facts.

Also, our proof of the Theorem (stated as Theorem (5.1) in Section 5) requires
auxiliary statements which may as well be stated and proved for an arbitrary 
odd prime $p$. These will be discussed in Sections 3 and 4.


It does not seem unreasonable to conjecture that, except for the case
$p = 3$ and $|A| \equiv |B| \equiv 4$ mod 9 we have mentioned above, the
cardinality of a restricted sumset $A +' B$, with $(|A|, |B|) = (r , s)$
forming a special pair, is bounded below by $r + s - 2$. We have no clue
of a method strong enough to prove this statement for an arbitrary special
pair.

Right from the start of the proof (see Proposition (3.1) in Section 3
below), we need the assumption that $A$ and $B$ have cardinality
$|A| = |B| = 1 + ap^{h}$. This assumption is maintained throughout
Section 4.

The case $p = 3$ proper is dealt with in Section 5.

\vskip 20pt


\section*{\normalsize 2. Basic results and explicit formulas for 
$\beta_{p}(r, s)$ and $\gamma_{p}(r, s)$}


Given an odd prime $p$ and positive integers $r, s$, let
$$
\beta_{p}(r, s) \espp = \espp \mbox{ min }\{n \in {\bf N} \espp |
\espp (x+y)^{n} \in (x^{r}, y^{s})\fp[x, y]\}
$$
be the smallest natural number $n$ such that $(x+y)^n$ belongs to the ideal
$I(r, s) = (x^r, y^s)$ generated by $x^r$, $y^s$ in the polynomial ring
$\fp[x, y]$.

We have proved in {\ekf} that for any $A, B \subset V$ of cardinalities
$|A| = r$ and $|B| = s$, one has the inequality
\begin{equation}
|A + B| \geq \beta_{p}(r, s),
\end{equation}

\noindent
using the usual notation $A + B = \{a+b \espp | \espp a \in A, b \in B \}$.

Moreover, this lower bound is sharp, {\em i.e.}, if $\mu_{V}(r, s)$ denotes the
smallest possible value of $|A + B|$ for all $A, B \subset V$ of cardinalities
$|A| = r$, $|B| = s$ then $\mu_{V}(r, s)$  \espp = \espp $\beta_{p}(r, s)$,
provided $r, s \leq |V|$.

\vespa

We also obtained in \ekf, by a similar method, a lower bound $\gamma_{p}(r, s)$
for the size of the {\em restricted} sumset
$A +' B = \{a+b \espp | \espp a \in A, b \in B, a \neq b \}$. More precisely,
let

\vespa

\centerline{$\gamma_{p}(r, s)$ \espp = \espp min$\{n \in {\bf N} \espp |
\espp (x-y)(x+y)^{n} \in (x^{r}, y^{s})\fp[x, y]\}$,}

\vespa

\noindent then we have
\begin{equation}
|A +' B| \geq \gamma_{p}(r, s).
\end{equation}

However, the lower bound $\gamma_{p}(r, s)$ need not be sharp if $(r, s)$ is
a special pair for the odd prime $p$. It is indeed sharp, {\em i.e.},
$\mu_{p}'(r, s) = \gamma_{p}(r, s)$ if $(r, s)$ is {\em not} a special
pair.

\vespa

We now produce explicit formulas for these lower bounds $\beta_{p}(r, s)$
and $\gamma_{p}(r, s)$.

Given positive integers $r$ and $s$, let $r - 1 = \sum_{i=0}^{n}r_{i}p^{i},
s - 1 = \sum_{i=0}^{n}s_{i}p^{i}$ be the $p$-adic expansions of $r-1$ and
$s-1$, {\em i.e.}, $0 \leq r_{i} \leq p-1$ and $0 \leq s_{i} \leq p-1$ for
all $i \in [0, n]$.

Define the integer $m \in {\bf Z}$ by the formula

\vespa

\centerline{$m \espp = \espp \mbox{max}(\{-1\} \esp \cup \esp
\{i \in [0, n] \espp | \espp \espp r_{i} + s_{i} \geq p\})$.}

\vespa

In other words, $m = -1$ if for all $i \in [0, n]$ we have
$r_{i} + s_{i} \leq p-1$. Else, $m$ is characterized by the inequalities
$r_{m} + s_{m} \geq p$ and $r_{i} + s_{i} \leq p-1$ for $i \in [m+1, n]$.
(This last interval being of course empty if $m = n$, {\em i.e.}, if
$r_{n} + s_{n} \geq p$.)

With this notation, the function $\beta_{p}(r, s)$ is given by
\begin{equation}
\begin{array}{lll}
\beta_{p}(r, s) & = & p^{m+1} + \sum_{i=m+1}^{n}(r_{i} + s_{i})p^{i} \\
		& = & s + \sum_{i=m+1}^{n}r_{i}p^{i} + (p^{m+1} - 1 -
		      \sum_{i=0}^{m}s_{i}p^{i}).
\end{array} \end{equation}

Note that $\beta_{p}(r, s) = r + s - 1$ if $m = -1$, {\em i.e.}, if
$r_{i} + s_{i} \leq p-1$ for all $i \in [0, n]$.

The formula for $\gamma_{p}(r, s)$ involves a somewhat more complicated
case distinction.

If $r = s = 1$, then $\gamma_{p}(1, 1) = 0$. If $ r + s \geq 3$, then
\begin{equation}
\hspace{5mm} \gamma_{p}(r, s) = \left\{ \begin{array}{ll}

\beta_{p}(r, s) & \mbox{if } \espp
{r+s-2 \choose r-1} \espp \equiv\espp 0 \espp \espp \mbox{ mod } p, \\

r + s - 3 & \mbox{if } \espp {r+s-2 \choose r-1} \not \equiv 0
\mbox{ and } {r+s-3 \choose r-1} \equiv
{r+s-3 \choose s-1} \mbox{ mod } p, \\

r + s - 2 & \mbox{if } \espp {r+s-2 \choose r-1} \not \equiv 0
\mbox{ and } {r+s-3 \choose r-1} \not \equiv
{r+s-3 \choose s-1} \mbox{ mod } p.

\end{array} \right. \end{equation}

\vespa

The conditions on binomial coefficients in formula (6) can equivalently be
formulated in terms of the respective $p$-adic expansions
$r-1 = \sum_{i \geq 0}r_{i}p^{i}$ and $s-1 = \sum_{i \geq 0}s_{i}p^{i}$ of
$r-1$ and $s-1$, as follows :

\vespa

If $r + s \geq 3$ as above, then
\begin{equation}
\hspace{5mm} \gamma_{p}(r, s) = \left\{ \begin{array}{ll}

\beta_{p}(r, s) & \mbox{if there exists an index } j \\
		& \mbox{such that } r_j + s_j \geq p, \\

r + s - 3 & \mbox{if } r_i + s_i \leq p-1 \mbox{ for all } i, \mbox{ and } \\
	  & \nu_p(r-1) = \nu_p(s-1) = v, \mbox{ say,} \\
	  & \mbox{with } r_v = s_v,\\


r + s - 2 & \mbox{otherwise, {\em i.e.}, still with }
	     r_i + s_i \leq p-1 \\
	  & \mbox{for all } i, \mbox{ but either }
	     \nu_p(r-1) \neq \nu_p(s-1) \\
	  &\mbox{or, with } v \mbox{ as above, } r_v \neq s_v,

\end{array} \right. \end{equation}

\noindent where $\nu_p(r-1)$ is the $p$-valuation of $r-1$, {\em i.e.},
$\nu_p(r-1)= v$ if the $p$-adic expansion of $r-1$ has the form
$r-1 = r_vp^{v} + \sum_{i > v}r_{i}p^{i}$ with $r_v \neq 0$.

\vespa

Note that the definition of a special pair (given in the Introduction)
corresponds exactly to the second case in formula (7), with the further
condition $\nu_p(r-1) = \nu_p(s-1) \geq 1$.

Hence, the statement ``$\mu_{V}'(r, s) = r + s -3$ or else
$\mu_{V}'(r, s) = r + s -2$" in the Introduction amounts for special pairs
to the inequalities
$$\gamma_{p}(r, s) \leq \mu_{V}'(r, s) \leq \gamma_{p}(r, s) + 1$$
which are true in general. (Compare also the version of the
definition of a special pair given in \ekf, Definition (7.8).) It is a
theorem in {\ekf} (see Theorem (7.9)) that $\mu_{V}'(r, s) \espp = \espp
\gamma_{p}(r, s)$ for non-special pairs.

\vespa

The proof of the equivalence of (6) and (7) is easy and left to the reader.
Part of it is reproduced below and the rest is an immediate consequence of
Lemma (7.7) in \ekf.

\vespa

In this section, we provide a direct proof of the formulas (5) and (6)
which is partially independent of \ekf. However, we use but do not reprove
a couple of easy lemmas from our previous paper.

\vespa

We begin with a remark on the binomial coefficient ${r+s-2 \choose r-1}$
which is the content of Lemma (7.2) in \ekf.

Let $r-1 = \sum_{i \geq 0}r_{i}p^{i}$  and $s-1 = \sum_{i \geq 0}s_{i}p^{i}$
be the $p$-adic expansions of $r-1$ and $s-1$. If
$r+s-2 = \sum_{i \geq 0}t_{i}p^{i}$ is the $p$-adic expansion of $r+s-2$, the
well known Lucas formula for binomial coefficients modulo $p$, namely here,
$$
{r+s-2 \choose r-1} \espp \equiv \espp \prod_{i \geq 0} {t_{i}\choose r_{i}}
\espp \espp \espp \mbox{ mod } \espp p,
$$
\noindent shows easily that ${r+s-2 \choose r-1} \not \equiv 0$ \espp
mod $p$ \espp if and only if $0 \leq r_{i} + s_{i} \leq p-1$ \espp for all
$i$.

\vespa

By definition, $\beta_{p}(r, s)$ =
min$\{n \in {\bf N} \espp | \espp (x + y)^{n} \in I(r, s)\}$, where
$I(r, s)$ is the ideal $(x^{r}, y^{s})$ generated by $x^{r}$ and $y^{s}$
in the polynomial ring $\fp [x, y]$.

Since
$(x + y)^{r + s - 1} = \sum_{i=0}^{r+s-1}{r+s-1 \choose i}x^iy^{r+s-1-i}$,
and either $i \geq r$, or if $i \leq r-1$, then $r + s - 1 - i \geq s$, it
follows that $(x+y)^{r+s-1} \in I(r, s)$ and $\beta_{p}(r,s) \leq r+s-1$.

Furthermore, the congruence
$(x+y)^{r+s-2} \equiv {r+s-2 \choose r-1}x^{r-1}y^{s-1}$ mod $I(r, s)$ gives
$\beta_{p}(r,s) = r+s-1$ if ${r+s-2 \choose r-1} \not \equiv 0$ mod $p$.


Thus,

\vespa

\centerline{$ \beta_{p}(r, s) \espp = \espp r + s - 1$, \esp {\em if}
$r_{i} + s_{i} \leq p-1$ \espp {\em for all} $i \geq 0$. }

\vespa

If, on the other hand, there exists an index $m$ such that
$r_{m} + s_{m} \geq p$ and
$r_{i} + s_{i} \leq p-1$ \espp for $i \geq m+1$, then we write
\[ \left\{ \begin{array}{lll}
r-1 & = & a_{0} + a_{1}p^{m+1}, \\
s-1 & = & b_{0} + b_{1}p^{m+1},
\end{array} \right. \]
where $a_0 = \sum_{i=0}^{m}r_{i}p^{i}$ \esp , \espp and
$b_0 = \sum_{i=0}^{m}s_{i}p^{i}$, and of course, $a_1, b_1$ are
non-negative integers.

\vespa

Note for further use that
$p^{m+1} = p \cdot p^{m} \leq (r_m + s_m)p^{m} \leq a_0 + b_0.$


We claim that, using the above notation, $\beta_{p}(r, s)$ is given by
$$
\beta_{p}(r, s) \espp = \espp p^{m+1} + \sum_{i \geq m+1} (r_{i} + s_{i})p^{i}
\espp = \espp p^{m+1}(1 + a_1 + b_1).
$$

In order to prove this, we calculate

\[ \begin{array}{lcl}
(x+y)^{p^{m+1}(a_{1}+b_{1}+1)} \espp & \equiv & \espp
(x^{p^{m+1}} + y^{p^{m+1}})^{a_{1}+b_{1}+1} \espp \mbox{mod} \espp p  \\
& & \\ & \espp = \espp &
\sum_{i=0}^{a_{1}+b_{1}+1}{a_{1}+b_{1}+1 \choose i} x^{p^{m+1}i}y^{p^{m+1}j},
\end{array}
\]

\noindent where $i + j = a_{1}+b_{1}+1$.


For $i \leq a_{1}$, we have $j \geq b_{1} + 1$ and since
$$ s - 1 = b_{0} + p^{m+1}b_{1} \leq p^{m+1} - 1 + p^{m+1}b_{1}
\leq p^{m+1}j - 1$$
it follows that $p^{m+1}j > s$ and $y^{p^{m+1}j} \in (x^{r}, y^{s})$.

Similarly, if $i \geq a_{1}+1$, then $j \leq b_{1}$. As above, we have
$p^{m+1}i > r$ and $x^{p^{m+1}i} \in I(r, s) = (x^{r}, y^{s})$.


Therefore $(x+y)^{p^{m+1}(1 + a_{1}+b_{1})} \in I(r, s)$, and
$\beta_{p}(r, s) \espp \geq \espp  p^{m+1}(1 + a_{1}+b_{1})$ by definition.

\vespa

We now calculate
$$
\begin{array}{ll}
(x+y)^{p^{m+1}(a_{1}+b_{1}+1) - 1} \espp  &\equiv  \espp
(x^{p^{m+1}} + y^{p^{m+1}})^{a_{1}+b_{1}}\cdot
(\frac{x^{p^{m+1}} + y^{p^{m+1}}}{x+y}) \espp \mbox{mod} \espp p\\
\\
& \equiv \espp
\sum_{i=0}^{a_{1}+b_{1}}{a_{1}+b_{1} \choose i} x^{p^{m+1}i}y^{p^{m+1}j} \cdot
\sum_{k=0}^{p^{m+1}- 1} (-1)^{k}x^{k}y^{\ell} \espp \mbox{mod} \espp p,
\end{array}
$$
\vespa


\noindent where $i + j = a_1 + b_1$ and $k + \ell = p^{m+1} - 1$.

\vespa

For $i > a_1$, we have $p^{m+1}i > p^{m+1} - 1 + p^{m+1}a_{1} \geq r - 1$.
It follows that $x^{p^{m+1}i} \in I(r, s)$. Similarly,
$y^{p^{m+1}j} \in I(r, s)$ for $j > b_{1}$. Hence,
$$
(x+y)^{p^{m+1}(a_{1}+b_{1}+1) - 1} \espp  \equiv  \espp
{a_{1}+b_{1} \choose a_{1}} x^{p^{m+1}a_{1}}y^{p^{m+1}b_{1}} \cdot
\sum_{k=0}^{p^{m+1}- 1} (-1)^{k}x^{k}y^{\ell},
$$
modulo $I(r, s)$, with $\ell = p^{m+1} - k - 1$.

\vespa

As noted above, $a_0 + b_0 \geq (r_m + s_m)p^{m} \geq p^{m+1}$. For $k$
in the interval $p^{m+1} - b_0 - 1 \leq k \leq a_0$, we have
$\ell = p^{m+1} - k - 1 \leq b_0$. Therefore, still modulo $I(r, s)$, we
have
$$
(x+y)^{p^{m+1}(a_{1}+b_{1}+1) - 1} \espp  \equiv  \espp
\sum_{p^{m+1} - b_0 - 1 \leq k \leq a_0} (-1)^{k}{a_{1}+b_{1} \choose a_{1}}
x^{k+p^{m+1}a_{1}}y^{\ell + p^{m+1}b_{1}},
$$
and the monomials $x^{k+p^{m+1}a_{1}}y^{\ell + p^{m+1}b_{1}}$,
for the indicated interval of values of $k$ and $\ell$ are part of an
$\fp$-basis of $\fp[x, y]/I(r, s)$.

Now, certainly, $(-1)^{k} \not \equiv$ 0 mod $p$, and using again the
Lucas formula and the inequalities $r_{i} + s_{i} \leq p-1$ for
$i \geq m+1$, we have
$$
{a_{1}+b_{1} \choose a_{1}} \equiv
\prod_{i \geq m+1} {r_{i} + s_{i} \choose r_{i}} \not \equiv 0
\espp \espp \mbox{ mod } \espp p.
$$
Hence,
$$
(x+y)^{p^{m+1}(a_{1}+b_{1}+1) - 1} \espp \not \in \espp I(r, s).
$$

It follows that $\beta_{p}(r, s) \espp = \espp  p^{m+1}(1 + a_{1}+b_{1})$
as asserted.



We now prove the formula (6) for $\gamma_{p}(r, s)$. Let
$\gamma = \gamma_{p}(r, s)$, $\beta =  \beta_{p}(r, s)$, to simplify notation.

Suppose first that there exists an index $n$ for which $r_{n} + s_{n} \geq p$
in the $p$-adic expansions $r-1 = \sum_{i \geq 0}r_{i}p^{i}$ and
$s-1 = \sum_{i \geq 0}s_{i}p^{i}$ of $r-1$ and $s-1$, then
${r+s-2 \choose r-1} \espp \equiv \espp $ 0 mod $p$. Indeed, taking
$n$ such that $r_{i} + s_{i} \leq p-1$ for $i < n$, we have the $p$-adic
expansion $r+s-2 = \sum_{i \geq 0}t_{i}p^{i}$ with
$t_{n} = r_{n} + s_{n} - p < r_{n}$, and by the Lucas formula
$$
{r+s-2 \choose r-1} \espp \equiv \espp \prod_{k \geq 0} {t_{k}\choose r_{k}}
\espp \equiv \espp 0 \espp \espp \espp \mbox{ mod } \espp p,
$$
because the factor ${t_{n} \choose r_{n}}$, where $t_{n} < r_{n}$,
is congruent to 0 mod $p$.

It follows from
$$
(x+y)^{\beta} = \sum_{i}{\beta \choose i}x^{i}y^{\beta - i} \equiv
\sum_{i = \beta - s + 1}^{r-1} {\beta \choose i}
x^{i}y^{\beta - i} \equiv 0 \espp \espp {\rm mod} \espp \espp
I(r, s) = (x^{r}, y^{s}),
$$
that ${\beta \choose i} \equiv 0$ mod $p$ in the range
$i = \beta - s + 1, \ldots, r-1$.


Now, ${\beta \choose i} \espp = \espp {\beta - 1 \choose i - 1} +
 { \beta - 1 \choose i}$ implies that all coefficients
${\beta - 1 \choose i}$ for $i = \beta - s, \ldots, r-1$ are  mutually
congruent modulo $p$, up to sign, and thus are simultaneously $\equiv 0$ or
$\not \equiv 0$ mod $p$.

We must have ${\beta - 1 \choose i} \not \equiv 0$ \espp mod $p$, for
$i = \beta - s, \ldots, r-1$ since $(x + y)^{\beta - 1} \not \in I(r, s)$.

It follows that


\hspace{4mm}$(x-y)(x+y)^{\beta-1} = (x+y)^{\beta} - 2y(x+y)^{\beta - 1}$


\hspace{37.5mm}$\equiv -2\sum_{i = \beta - s + 1}^{r-1} {\beta - 1 \choose i}
x^{i}y^{\beta - i} \not \equiv 0 \espp \espp {\rm mod} (x^{r}, y^{s}),$


\noindent and thus $\gamma_{p}(r, s) \espp =  \espp \beta_{p}(r, s)$ in the
case ${r+s-2 \choose r-1} \espp \equiv \espp 0$ mod $p$.


Suppose now that $r_{i}+ s_{i} \leq p-1$ for all $i \geq 0$ in the $p$-adic
expansions $r-1 = \sum_{i \geq 0}r_{i}p^{i}$ and
$s-1 = \sum_{i \geq 0}s_{i}p^{i}$ of $r-1$ and $s-1$.

An easy calculation shows that, modulo \espp $I(r, s)$ = $(x^r, y^s)\fp[x,y]$,
and for $r+s \geq 3, \espp r \geq s$, we have the congruence
$$(x-y)(x+y)^{r+s-3} \equiv \{ {r+s-3 \choose r-2}
- {r+s-3 \choose r-1}\}x^{r-1}y^{s-1}.$$


It follows easily that $\gamma_{p}(r, s) = r + s - 2$ if
${r+s-2 \choose r-1} \not \equiv 0$ mod $p$ and
$ {r+s-3 \choose s-1} \not \equiv {r+s-3 \choose r-1}$ mod $p$.

Moreover, we see that $\gamma_{p}(r, s) \leq r + s - 3$ if
${r+s-2 \choose r-1} \not \equiv 0$ mod $p$ and
${r+s-3 \choose s-1} \equiv {r+s-3 \choose r-1}$ mod $p$.

\vespa

To prove that in this last case we have $\gamma_{p}(r, s) = r + s - 3$,
it suffices to show that \hfill \\
$(x-y)(x+y)^{r+s-4} \not \equiv 0$ modulo the
ideal $I(r, s)$ =  $(x^r, y^s)\fp[x,y]$.

This is obvious for $r = s = 2$, and for $r \geq 3, s \geq 2$  an easy calculation
shows that \hfill \\
$(x-y)(x+y)^{r+s-4}$ is congruent modulo $I(r, s)$ to
$$\{{r+s-4 \choose r-3} - {r+s-4 \choose r-2}\}x^{r-2}y^{s-1} +
\{{r+s-4 \choose r-2} - {r+s-4 \choose r-1}\}x^{r-1}y^{s-2}.$$



By a simple lemma on binomial coefficients, Lemma (6.5) of \eks, the two
coefficients in this expression could only both vanish if we had
$${r+s-4 \choose r-3} \equiv {r+s-4 \choose r-2} \equiv
{r+s-4 \choose r-1} \equiv 0 \mbox{ mod } p.$$
This would imply
${r+s-2 \choose r-1} \equiv 0$ mod $p$, contrary to the hypothesis.
This finishes our discussion of formulas (5) and (6).

\vespa

As an application of the formulas, note that
$$
\gamma_{p}(1+ap^{h},1+ap^{h}) = 2ap^{h} - 1,\espp \espp \espp
\beta_{p}(1+ap^{h},1+ap^{h})= 2ap^{h}+1
$$
if $1 \leq a \leq \frac{p-1}{2}$. We shall use these values in the next
section.


\vskip 20pt

\section*{\normalsize  3. The case of unequal sets}

Let $A, B \subset V$ be subsets of a vector space $V$ over $\fp$, of
cardinality $|A| = |B| = 1 + ap^{h}$.

The first step in our study of $\mu_{p}'(1+ap^{h}, 1+ ap^{h})$ is to show
that it suffices to consider the instance in which $A = B$.

Indeed, we prove



\noindent
{\bf Proposition (3.1)} {\em Let the subsets $A, B \subset V$ both have
cardinality $1 + ap^{h}$, where $h \geq 1$ and $1 \leq a \leq \frac{p-1}{2}$.
If $A \neq B$ then}

\vespa

\centerline{ $|A +' B| \geq \gamma_{p}(1+ap^{h},1+ap^{h}) + 1 = 2ap^{h}$. }


\noindent
{\it Proof.} 
Let $X = A \cap B$ and $Y = A \cup B$.
If $X = \emptyset$, then $A+'B = A+B$ and
$$|A +' B| = |A + B| \geq \beta_{p}(1+ap^{h},1+ap^{h}) = 2ap^{h}+1.$$

\vespa

Assume now that $X \neq \emptyset$. Set $r = |X| \geq 1$, and thus
$|Y| = 2ap^{h} + 2 - r$.
We have $X +' Y \subset A +' B$. Therefore
$|A +' B| \geq  |X +' Y| \geq \gamma_{p}(r, 2ap^{h} + 2 - r)$.

\vespa

We claim that for $1 \leq r \leq ap^{h}$ we have
$\gamma_{p}(r, 2ap^{h} + 2 - r)$ = $2ap^{h}$.

We set

\vespa

\centerline{$R = r$ \espp, \espp \espp $S = 2ap^{h} + 2 - r$}

\vespa

\noindent and write the $p$-adic expansions

$$
\left \{
\begin{array}{rlr}
R + S - 2 & = &  2ap^{h}, \\
R - 1     & = & r_0 + r_1p + \ldots + r_{h-1}p^{h-1} + r_{h}p^{h},
\end{array}
\right.
$$

\noindent where $r_{h} < a$, since $X = A \cap B \subset A$ and
$A \cap B \neq A$.



We have
$${R+S-2 \choose R-1} = {2ap^{h} \choose r-1} \equiv
{0 \choose r_0} \cdots {0 \choose r_{h-1}} \cdot {2a \choose r_{h}}
\espp \espp \mbox{ mod } \espp p.$$

\vespa

The only case where this number is $\not \equiv 0$ mod $p$ is when
$r_0 = r_1 = \ldots = r_{h-1} = 0$, and thus $r = 1 + cp^{h}$, with
$0 \leq c \leq a - 1$.

Let us begin with this case. If $r = 1 + cp^{h}$, with $0 \leq c \leq a - 1$,
then, by formula (6), the value of $\gamma_{p}(R, S)$ =
$\gamma_{p}(r, 2ap^{h} + 2 - r)$ depends on whether the binomial coefficients
${R + S - 3 \choose R - 1}$ and ${R + S - 3 \choose S - 1}$ are
congruent mod $p$ or not.

We examine the $p$-adic expansions of $R+S-3$, $R-1$ and $S-1$.

$$
  \left \{
  \begin{array}{rlr}
  R+S-3 & = & \sum_{i=0}^{h-1}(p-1)p^{i} + (2a-1)p^{h}, \\
    R-1 & = & cp^{h}, \\
    S-1 & = & (2a - c)p^{h}.
  \end{array}
  \right.
$$

By the formula of Lucas,

\vespa

\centerline{${R+S-3 \choose R-1} \equiv {2a-1 \choose c}$ \espp and \espp
${R+S-3 \choose S-1} \espp \equiv \espp {2a-1 \choose 2a-c}$ \espp \espp
mod \espp $p$.}

\vespa

Now, since $c < a \leq \frac{p-1}{2}$, we have $c \not \equiv a$ mod $p$,
and therefore
$$\gamma_{p}(r, 2ap^{h} + 2 - r) =
r + (2ap^{h} + 2 - r) - 2 = 2ap^{h},$$
in accordance with the claim.



There remains to examine the case where
$$r - 1  =  r_0 + r_1p + \ldots + r_{h-1}p^{h-1} + r_{h}p^{h},$$
with $0 \leq r_{h} \leq a-1$ and
$(r_0, r_1, \ldots, r_{h-1}) \not = (0, 0, \ldots, 0)$. We then have
$${R+S-2 \choose R-1} = {2ap^{h} \choose r-1} \equiv 0 \mbox{ mod } p.$$
Hence $\gamma_{p}(r, 2ap^{h} + 2 - r) = \beta_{p}(r, 2ap^{h} + 2 - r)$.

We claim that $\beta_{p}(r, 2ap^{h} + 2 - r)$ = $2ap^{h}$.


Let $0 \leq m \leq h-1$ be the index defined by $r_0 = \ldots = r_{m-1}= 0$
and $r_{m} \neq 0$.

The $p$-adic expansions of $R-1$ and $S-1$ have the form
$$
  \left \{
  \begin{array}{rrrrr}
    R-1 & = & r_mp^{m} + & \sum_{i=m+1}^{h-1}r_{i}p^{i} + & r_{h}p^{h}, \\

    S-1 & = & (p-r_m)p^{m} + & \sum_{i=m+1}^{h-1} (p-1-r_{i})p^{i} + &
    (2a - 1 - r_{h})p^{h}.
  \end{array}
  \right.
$$

Therefore, we have
$\beta_p(R, S) = (1 + [\frac{R-1}{p^{k+1}]}] + [\frac{S-1}{p^{k+1}}])p^{k+1}$,
where $k$ is the largest index for which the sum of the coefficients of the
$p$-adic expansions is larger than or equal to $p$.

It is easy to see that $k = m$. It follows that
$$\beta_{p}(R, S) \espp = \espp
p^{m+1} + (p-1)p^{m+1} + \ldots + (p-1)p^{h-1} + (2a - 1)p^{h} \espp =
\espp 2ap^{h}.$$



This finishes the proof of the proposition. 
\hfill$\Box$



Henceforth, we shall be dealing with the restricted sumset of a single subset
$A \subset V$ with itself,  {\em i.e.}, $A +' A$.

\vskip 20pt

\section*{\normalsize 4. Slicing the set $A$ by hyperplanes}

Our approach in order to get the sharp lower bound for $|A +' A|$ will consist
in keeping track of the classes of elements of $A$ and $A + 'A$ modulo a
chosen hyperplane $H \subset V$ and slicing the set $A$ by the translates of
$H$. Let $e \neq 0$ be a vector outside $H$, so that $V = \fp e \oplus H$. 
For $c \in \fp$, we denote by $H_{c}$ the (affine) hyperplane $c \cdot e + H$ 
and let $A_{c} = A \cap H_{c}$. A translation of $A$ does not change $|A +' A|$. 
Hence, we may assume that the size of $A_0 = A \cap H$ is maximal in the 
collection of sizes $\{|A_{c}|, c \in \fp \}$. We set $r = |A_0|$.

Let $C = \{0, c_1, \esp \ldots, \esp c_{\ell}\}$ denote the set of classes
$c \in \fp$ such that $A_{c} \neq \emptyset$. We may also assume that the
classes $c_1, \esp \ldots, \esp c_{\ell}$ are ordered so that
$|A_0| \geq |A_{c_{1}}| \geq \ldots \geq |A_{c_{\ell}}| \geq 1$.

We use the notation $s_{i} = |A_{c_{i}}|$ for $1 \leq i \leq \ell$  and
therefore we have the inequalities
$r \geq s_1 \geq \ldots \geq s_{\ell} \geq 1$.

Note that, changing $A$ to a homothetic set if necessary, we may also
assume that $c_1 = 1$, so that $s_1 = |A_1|$.

We call  $(r, s_1, \esp \ldots, \esp s_{\ell})$  the {\em partition}
of $|A|$ (or of $A$, by abuse of language) corresponding to the choice of $H$.

Since we may assume that $A$ is not contained in any hyperplane of $V$,
we may assume $1 \leq \ell \leq p-1$.

The case where $\ell = 1$, when $|A| = 1 + ap^{h}$, with
$1 \leq a \leq \frac{p-1}{2}, h \geq 1$, can be treated at once. This
special case will be used in the next section.


\noindent
{\bf Proposition (4.1)} {\em  Suppose that the subset $A \subset V$ with
cardinality $|A| = 1 + ap^{h}$ has a partition $(r, s)$ of length $2$. Then,
unless $p = 3, a = 1, h = 1$, we have }
$$|A +' A| \espp \geq \espp 2ap^{h} \espp
= \espp \gamma_{p}(1+ap^{h}, 1+ap^{h}) + 1.$$

\vespa

\noindent
{\it Proof.} By hypothesis, $A = A_{0} \esp \coprod \esp A_{1}$, using the
notational convention specified above. Let $r = |A_0|, s = |A_1|$.

We first take care of the case where $s = 1$.

We have $A +' A = (A_0 +' A_0) \cop (A_0 + A_1)$ and therefore
$|A +'A| \geq \gamma_{p}(ap^{h}, ap^{h}) + \beta_{p}(ap^{h}, 1)$.


The $p$-adic expansion of $ap^{h} - 1$ is
$$ap^{h} - 1 \espp = \espp \sum_{i=0}^{h-1}(p-1)p^{i} + (a-1)p^{h}.$$

\vespa

Therefore,
$\gamma_{p}(ap^{h}, ap^{h}) = \beta_{p}(ap^{h}, ap^{h}) = p^{h} + 2(a-1)p^{h}$.

Since $\beta_{p}(ap^{h}, 1) = ap^{h}$, it follows that
$$|A +' A| \geq p^{h} + 2(a-1)p^{h} + ap^{h} = 2ap^{h} + (a-1)p^{h}
\geq 2ap^{h},$$
with equality if and only if $a = 1$.


Suppose now that $s \geq 2$. We have
$$A +' A \espp = \espp (A_0 +' A_0) \esp \coprod \esp (A_0 + A_1)
\esp \coprod \esp (A_1 +' A_1),$$
where the sets are disjoint because they belong to distinct
hyperplanes, namely $H$, $H_{1} =  e + H$ and $H_{2} = 2 e + H$ respectively.

We shall evaluate the right-hand side of the resulting inequality
$$|A+'A| \espp\geq \espp \gamma_{p}(r, r) + \beta_{p}(r, s)
+ \gamma_{p}(s, s).$$

\vespa

Let $r - 1 = \sum_{i=0}^{h}r_{i}p^{i}$ be the $p$-adic expansion of $r-1$.
Since $1+ap^{h} = r + s$, we have $s-1 = (ap^{h} - 1) - (r - 1)$. This
yields the $p$-adic expansion of $s-1$ as follows:
$$s-1 = \sum_{i=0}^{h}s_{i}p^{i} = \sum_{i=0}^{h-1}(p-1-r_{i})p^{i}
+ (a-1-r_{h})p^{h},$$
where $0 \leq a - 1 - r_{h}$ because $r-1 < ap^{h}$ and hence
$r_{h} \leq a-1$.

As a first consequence, we get $\beta_{p}(r, s) = r + s - 1$ by formula (5).
Indeed, $r_{i}+ s_{i} = p-1$, for $i = 0, \ldots, h-1$ and
$r_{h}+ s_{h} = a-1 < p-1$. Thus $\beta_{p}(r, s) = ap^{h}$.

By the formula (6) above, we have for $t = r$ or $s$ and $t_{i} = r_{i}$
or $t_{i} = s_{i}$, respectively,

\[ \gamma_{p}(t, t) = \left\{ \begin{array}{ll}
2t - 3 & \; \mbox{if } \espp 2t_{i} \leq p-1 \espp \mbox{for all}
	     \espp i \in [0, h] \\
p^{m+1} + 2\sum_{i=m+1}^{h}t_{i}p^{i} & \; \mbox{otherwise,} 
\end{array} \right. \]

\noindent where $m \espp = \espp \mbox{max}(\{-1\} \esp \cup \esp
\{i \in [0, h] \espp | \espp \espp 2t_{i} \geq p\})$.

\vespa

We want to evaluate
$\tau = \gamma_{p}(r, r) + \beta_{p}(r, s) + \gamma_{p}(s, s)$.

There are 2 cases for each of $r$ and $s$, and thus 4 cases altogether.

\vespa
\noindent
$\bullet$ If $2r_{i} \leq p-1$ and $2s_{i} \leq p-1$ for all $i \in [0, h]$,
then $\gamma_{p}(r, r)  = 2r - 3$ and $\gamma_{p}(s, s) = 2s - 3$. Note that
this case occurs only if $r = 1 + \frac{p^{h}-1}{2} + r_{h}p^{h}$ and
 $s = 1 + \frac{p^{h}-1}{2} + (a - 1 - r_{h})p^{h}$.

Then, $\tau = \gamma_{p}(r, r) + \beta_{p}(r, s) + \gamma_{p}(s, s) =
2r-3+ap^{h} + 2s-3 = 2ap^{h} + (ap^{h} - 4)$.

Thus, $\tau > 2ap^{h}$ except for $a=1, p=3, h=1$ as we already know.

\vespa
\noindent
$\bullet$ If $2r_{i} \leq p-1$ for all $i = 0, \ldots, h$, but
$r_{j} < \frac{p-1}{2}$ for at least one index $j$, then necessarily
$j \leq h-1$, and $2s_{j} = 2(p-1- r_{j}) \geq p$. Therefore

\[ \begin{array}{lll}
\gamma_{p}(s, s)  & = & s +
\sum_{i=m+1}^{h-1}(p-1- r_{i})p^{i} 
 + (a-1- r_{h})p^{h} + (p^{m+1} - 1 - \sum_{i=0}^{m}s_{i} p^{i}), \\
\\
\mbox{and so} & &  \\
& & \\
\gamma_{p}(s, s)  & \geq & s + (a-1-r_{h})p^{h}.
\end{array} \]

Hence,
\[ \begin{array}{lll}
\tau & \geq & 2r-3 + ap^{h} + s + (a-1- r_{h})p^{h} \\
       & \geq & (r-2) + 2ap^{h} + (a-1- r_{h})p^{h} \\
       & \geq & 2ap^{h}.
\end{array} \]

\noindent
$\bullet$ The case where there exists an index $m \in [0, h-1]$ such that
$2r_{m} \geq p$ and $2r_{i} \leq p-1$ for $i \in [m+1, h]$, and where
$2s_{i} \leq p-1$ for all $i = 0, \ldots, h-1, h$ is quite symmetrical.
Then, $\tau \geq r + \sum_{i=m+1}^{h}r_{i}p^{i} + ap^{h} + 2s - 3$. Thus,
$\tau \geq  2ap^{h}  + (s - 2) + \sum_{i=m+1}^{h}r_{i}p^{i}$. This is
strictly larger than $2ap^{h}$, even if $s = 2$.

\noindent
$\bullet$ Finally, if there exist $m$ and $n$ such that $2r_{m} \geq p$ and
$2s_{n} \geq p$, and $m, n$ are the maximal indices with this property, then
$$
\tau \geq r + \sum_{i=m+1}^{h}r_{i}p^{i} + ap^{h} + s +
\sum_{i=n+1}^{h}s_{i}p^{i}.
$$
Thus, clearly, $\tau \geq 2ap^{h} + 1$. 
\hfill$\Box$

\vskip 20pt


\section*{\normalsize 5. The value of $\mu_{3}'(1+3^{h}, 1+3^{h})$}

In this section we take $p = 3$ and since
$\mu_{3}'(4, 4) = \gamma_{3}(4, 4) = 5$, we assume $h \geq 2$.

\noindent
{\bf Theorem (5.1)} {\em For $h \geq 2$, we have $\mu_{3}'(1+3^{h}, 1+3^{h})$
= $2 \cdot 3^{h}$.}

\noindent
{\it Proof}.

\noindent
{\bf Step 1. Unequal sets $A$ and $B$.}


Let $A, B$ be subsets of cardinality $1 + 3^{h}$ in some vector space $V$ over
$\ft$. We claim that $|A +' B| \geq 2 \cdot 3^{h}$. If $A \neq B$, this is
just Proposition (3.1) with $p = 3$, and $a = 1$.

Thus, from now on, we assume that $B = A$.

\vespa

Let $(r, s, t)$ be the partition of $1 + 3^{h}$ associated with
some decomposition $V = \ft \cdot e \oplus H$, {\em i.e.}, $r = |A \cap H|$,
$s = |A \cap H_1|$, $t = |A \cap H_2|$, where $H_{i} = i\cdot e + H$. We
may assume that $e \in A$ and $r \geq s \geq t$. As above, we set
$A_{i} = A \esp \cap \esp H_{i}$. Of course $A = A_0 \cop A_1 \cop A_2$.

\noindent
{\bf Step 2. Partitions of length 2.}



If $t = 0$, it follows from Proposition (4.1) that
$$|A +' A| \geq 2\cdot 3^{h},$$
 as desired.

\vespa

The proof in the case where $r \geq s \geq t \geq 1$ involves an induction
on $h$ in the case of a flat partition. In this section, we call {\em flat
partition} a partition with $r = 1 + 3^{h-1}$. Note that this is the smallest
possible value of $r$ since $r \geq s \geq t$ and $r + s + t = 1 + 3^{h}$.
There are two flat partitions for $h = 2$, namely $(4, 4, 2)$ and $(4, 3, 3)$.
They will be treated in step 4.


\noindent
{\bf Step 3. Not too flat partitions of length 3.}


Suppose that the partition $(r, s, t)$ of $1 + 3^{h}$ satisfies
$$2 + 3^{h-1} \espp \espp \leq \espp \espp r \espp \leq
\espp 3^{h} - 1,$$
and of course $r \geq s \geq t \geq 1$.

We have
$$A +' A \esp \supset \esp (A_0 +' A_0) \esp \coprod \esp
(A_0 + A_1) \esp \coprod \esp (A_0 + A_2)$$
and therefore,
\[
\begin{array}{lll}
|A +' A| & \geq & |A_0 +' A_0|+ |A_0 + A_1| + |A_0 + A_2| \\
	 & \geq & \gamma(r, r) + \beta(r, s) + \beta(r, t),
\end{array}
\]
where we write $\gamma$ and $\beta$ for $\gamma_3$ and $\beta_3$
respectively to simplify notation.

\noindent
{\bf Assertion.} {\em In the above range for the parameters (r, s, t),
namely 
$2 + 3^{h-1} \leq r \leq 3^{h} - 1$, and  $r \geq s \geq t \geq 1$,
we have {$\gamma(r, r) + \beta(r, s) + \beta(r, t) \geq 2 \cdot
3^{h} + 1$.}}


We first write the 3-adic expansions of $r - 1$, $s - 1$ and $t - 1$ :
\[
\begin{array}{lll}
r - 1 & = & r_0 + r_{1}3 + \ldots + r_{h-2}3^{h-2} + 3^{h-1}, \\
s - 1 & = & s_0 + s_{1}3 + \ldots + s_{h-2}3^{h-2} + s_{h-1}3^{h-1}, \\
t - 1 & = & t_0 + t_{1}3 + \ldots + t_{h-2}3^{h-2} + t_{h-1}3^{h-1}.
\end{array}
\]

In order to calculate $\beta(r, s)$ and $\beta(r, t)$ using formula (5) in
Section 2, we set $m = \mbox{max}(\{-1\} \esp \cup \esp
\{i \in [0, h-1] \espp | \espp \espp r_{i} + s_{i} \geq 3\})$. Similarly, we
also need
$n = \mbox{max}(\{-1\} \esp \cup \esp
\{i \in [0, h-1] \espp | \espp \espp r_{i} + t_{i} \geq 3\})$.

Note that $m \leq h-2$ and $n \leq h-2$ because $s, t \leq r$.

By formulas (5) and (6) or (7), we have
\[ \gamma(r, r) = \left\{
\begin{array}{cc}
\mbox{(a)} & 2r - 3, \\
& \mbox{if} \espp r_{i} \leq 1 \espp \mbox{for all} \espp i = 0, \ldots, h-2 \\
 & \\
\mbox{(b)} & 3^{\ell+1} + 2(\sum_{i = \ell+1}^{h-2}r_{i}3^{i})
+ 2 \cdot 3^{h-1}, \\
& \mbox{if} \espp r_{\ell} = 2 \espp \mbox{and} \espp r_{i} \leq 1 \espp
\mbox{for} \espp i \geq \ell+1
\end{array}
\right. \]
 and
$$\beta(r, s) + \beta(r, t) \espp =
\espp 3^{m + 1} + \sum_{i = m+1}^{h-1}(r_{i} + s_{i})3^{i} +
3^{n+1} + \sum_{i = n+1}^{h-1}(r_{i} + t_{i})3^{i},$$
where $r_{h-1} = 1$.



We set $\sigma = \gamma(r, r) +  \beta(r, s) + \beta(r, t)$ and claim
that $\sigma \geq 1 + 2 \cdot 3^{h}$.



Suppose first that $r_{i} \leq 1$ for all indices $i = 0, \ldots, h-1$ in
the 3-adic expansion of $r-1$, so that case $(a)$ prevails in the formula
above for $\gamma(r, r)$. Then,

\vespa
\[ \begin{array}{lll}
\sigma & \geq & 2r - 3 + s + \sum_{i = m+1}^{h-1}r_{i}3^{i} +
       t + \sum_{i = n+1}^{h-1}r_{i}3^{i}  \\
       & \geq  & (r - 2) + (r+s+t-1) + 2 \cdot 3^{h-1} = r-2 +3^{h}+
       2 \cdot 3^{h-1}.  \\
\end{array} \]

\vespa

Since $r \geq 2 + 3^{h-1}$, we get $\sigma \geq 2 \cdot 3^{h}$.

Note however that for $r = 2 + 3^{h-1}$, the only possibilities for the pair
$(s, t)$ are \hfill \\
$(2+3^{h-1}, -3 + 3^{h-1})$ if $h \geq 3$, and
$(1+3^{h-1}, -2+3^{h-1})$, $(3^{h-1}, -1+3^{h-1})$, for $h \geq 2$.

For $h=2$, we have the partitions $(5, 4, 1)$ and $(5, 3, 2)$ which give
respectively $\sigma = 20 = 2 + 2 \cdot 3^{h}$ and
$\sigma = 19 = 1 + 2 \cdot 3^{h}$.

For $h = 3$, the three partitions \hspace{1mm}
$(2+3^{h-1}, 2+3^{h-1}, -3+3^{h-1})$, 
$(2+3^{h-1}, 1+3^{h-1}, -2+3^{h-1})$, $(2+3^{h-1}, 3^{h-1}, -1+3^{h-1})$,
give respectively $\sigma = 1 + 2 \cdot 3^{h}$, $2 + 2 \cdot 3^{h}$, and
$1 + 2 \cdot 3^{h}$.

\vespa

Hence, in case $(a)$, we have indeed $\sigma \geq 2 \cdot 3^{h}$.



Suppose now that we are in case $(b)$ in the formula above for $\gamma(r, r)$.
Then, still with
$\sigma = \gamma_{p}(r, r) + \beta_{p}(r, s) + \gamma_{p}(s, s)$, we have

\vespa
$$\begin{array}{ll}
\sigma &=  \gamma(r, r) + \beta(r, s) + \beta(r, t)\\
\\
&=3^{\ell+1} + 2(\sum_{i = \ell+1}^{h-1}r_{i}3^{i}) +
3^{m + 1} + \sum_{i = m+1}^{h-1}(r_{i} + s_{i})3^{i} +
3^{n+1} + \sum_{i = n+1}^{h-1}(r_{i} + t_{i})3^{i}
\end{array}
$$
where as before $r_{h-1} = 1$.



Replacing one copy of $\sum_{i = \ell+1}^{h-1}r_{i}3^{i}$ in the first
summation by the equal quantity $r - 1 - \sum_{i = 0}^{\ell}r_{i}3^{i}$, and
similarly, $\sum_{i = m+1}^{h-1}s_{i}3^{i}$ by
$s - 1 - \sum_{i =0}^{m}s_{i}3^{i}$ and $\sum_{i = n+1}^{h-1}t_{i}3^{i}$ by
$t - 1 - \sum_{i =0}^{n}t_{i} 3^{i}$, we get
\[ \begin{array}{lll}
\sigma & = & r + s + t - 3 + \sum_{i = \ell+1}^{h-1}r_{i}3^{i} +
       (3^{\ell+1} - \sum_{i = 0}^{\ell}r_{i}3^{i})  \\
       &   &   \\
       &   & + \sum_{i = m+1}^{h-1}r_{i}3^{i} +
       (3^{m + 1} - \sum_{i =0}^{m}s_{i}3^{i}) \\
       &   &   \\
       &   & + \sum_{i =n+1}^{h-1}r_{i} 3^{i} +
       (3^{n+1} - \sum_{i = 0}^{n}t_{i}3^{i}).
\end{array} \]
Now, $r + s + t = 3^{h} + 1$. Since $\ell, m, n \leq h-2$, the three
summations
$\sum_{i = \ell+1}^{h-1}r_{i}3^{i}$, $\sum_{i = m+1}^{h-1}r_{i}3^{i}$ and
$\sum_{i = n+1}^{h-1}r_{i} 3^{i}$ each actually contain $r_{h-1}3^{h-1} = 3^{h-1}$,
and their sum is not smaller than $3^{h}$. Finally, all three terms of the
form $3^{k+1} - \sum_{i = 0}^{k}u_{i}3^{i}$, with $(k, u_{i}) = (\ell, r_{i}),
\espp (m, s_{i})$ and $(n, t_{i})$ respectively, are at least 1.

\vespa

Summarizing, we get $\gamma(r, r) + \beta(r, s) + \beta(r, t) \espp \geq
\espp 2 \cdot 3^{h} + 1$ also in the case encoded as (b).


\noindent
{\bf Step 4. Flat partitions.}



The argument will proceed by induction on $h$, starting with $h=2$.

\vespa

The induction step is very simple. The main difficulty will consist in the
analysis of the case $h=2$. As already noted above, for $h=2$ there are two
flat partitions, namely $(4, 4, 2)$ and $(4, 3, 3)$. Unfortunately, we do not
have a more conceptual treatment of these two cases than brute force
calculation.



We begin with the partition $(4, 4, 2)$.



Since

\vespa

\centerline{$A +' A \espp \supset \espp (A_0 +' A_0)
\esp \coprod \esp (A_0 + A_1) \esp \coprod \esp (A_0 + A_2)$,}

\vespa

\noindent and $\gamma_3(4,4) = 5$, $\beta_3(4,4) = 7$, $\beta_3(4,2) = 5$ with
sum 17, the assertion $|A +' A|  \geq 18$ follows if any of the three sets
$A_0 +' A_0$, $A_0 + A_1$, $A_0 + A_2$ has a cardinality exceeding its
lower bound $\gamma_3(4,4)$, $\beta_3(4,4)$, $\beta_3(4,2)$ respectively.

\vespa

We will show that if $|A_0+'A_0| = 5$, then $|A_0+A_2| \geq \beta_3(4,2)+1 = 6$.
We express this in a slightly more general statement :

\noindent
{\bf Lemma (5.2)} {\em Let $X,Y$ be subsets of a vector space over
$\ft$. Assume $|X| = 4$, $|Y|=2$ and $|X+'X|=5$. Then, $|X+Y| \geq 6$.}


\noindent
{\it Proof.} We may assume that $0 \in X$ by translating $X$ if necessary.
Note that $X$, being of cardinality 4, must contain two linearly independent
vectors $e_1, e_2$. Thus, $X$ has the form $X = \{0, e_1, e_2, v\}$.

We now show that by proper choice of $e_1, e_2$, we may assume $v = e_1 + e_2$.
Indeed,
$$X +' X  \espp  = \espp
\{e_1, e_2, e_1 + e_2, v, e_1 + v, e_2 + v\},$$
and $|X +' X|  = 5$ implies that exactly two of these vectors must
coincide, {\em i.e.}, one of them is redundant.

If $e_2 + v$ is redundant, we must have $e_2 + v = e_1$. Equality with any
one of the other vectors leads to a contradiction with $v \neq 0, v  \neq e_1,
e_2 \neq 0$, or  $e_1 \neq e_2$. We set $e_1' = v = e_1 - e_2$, $e_2' = e_2$.
Then, $X = \{0, e_1', e_2', e_1'+ e_2'\}$. Similarly, if $e_1 + v$ is
redundant, {\em i.e.}, $e_1 + v \in \{ e_1, e_2, e_1 + e_2, v, e_2 + v\}$,
then $e_1 + v = e_2$ and $X$ can be written as
$X = \{0, e_1', e_2', e_1'+ e_2'\}$ with $e_1' = e_1$, and $e_2' = v$. If
$v$ is redundant, we must have $v = e_1 + e_2$. In all cases we can rename the
elements of $X$ so that $X = \{0, e_1, e_2, e_1+ e_2\}$. Thus,
$$X +' X \espp = \espp \{ e_1, e_2, e_1 + e_2, 2e_1 + e_2,
e_1 + 2e_2 \}.$$

\vespa

Now, we may also assume $0 \in Y$, as $Y$ may be translated independently
of $X$.

Set $Y = \{0,y\}$. If $y$ were linearly independent of the plane $[e_1,e_2]$,
the set $X+Y$ would obviously have cardinality 8.

Without loss of generality, we may assume that $y = e_1 + \lambda e_2$, for
some $\lambda \in \ft$. Indeed, we may interchange $e_1, e_2$ and may change
the sign of $y$ by a translation of $Y$, since $\{0,y\}+\{-y\}=\{0,-y\}$.

But now, $X+Y$ contains the six distinct elements
$0,$ $e_1,$ $e_2,$ $e_1+e_2,$ $-e_1+\lambda e_2,$ $-e_1+(\lambda + 1)e_2$.
\hfill$\Box$
\vespa

This finishes the case of a partition of type (4,4,2).


Suppose now that the partition of $A$ is of type $(4, 3, 3)$, {\em i.e.},
$|A_0| = 4$, $|A_1| = |A_2| = 3$. We have
$$A +' A \supset ((A_0 +' A_0)\esp \cup \esp (A_1 + A_2))
\esp \coprod \esp (A_0 + A_1) \esp \coprod \esp (A_0 + A_2)$$
and thus $|A +' A| \geq 18$ except perhaps if
$|(A_0 +' A_0) \esp \cup \esp (A_1 + A_2)| = 5$, and
$|A_0 + A_1| = |A_0 + A_2| = 6$.

Assuming $|A_0 +' A_0| = 5$, the same argument as in the lemma above
shows that $A_0 = \{0, e_1, e_2, e_1 + e_2\}$. Furthermore, we may assume
the inclusion $A_1 + A_2 \subset A_0 +' A_0$.

Keeping the same notation as above, we assume $V = \ft \cdot e \oplus H$, where
$e \in A_{1}$.

Set $A_2 = 2e + \{x, y, z\}$ with distinct $x, y, z \in H$.
Since $x, y, z \in A_1 + A_2$, e.g., $x = e + (2e + x) \in A_1 + A_2$, we
must have
$$x, y, z \in A_0 +' A_0  =
\{e_1, e_2, e_1 + e_2, e_1 + 2e_2, 2e_1 + e_2\}.$$

\vespa

Each of the ${5 \choose 3} = 10$ choices for the triple $(x, y, z)$ furnishes
a set $A_0 + A_2$ of cardinality $8$ except the 2 choices
$x = e_1, y = e_1 + e_2, z = e_1 + 2e_2$ and
$x = e_2, y = e_1 + e_2, z = 2e_1 + e_2$. The two choices are in fact
equivalent, up to interchange of $e_1$ and $e_2$.

The choice $x = e_1, y = e_2, z = e_1 + e_2$ for example, produces
$$A_0 + A_2 \espp = \espp \{e_1, e_2, e_1 + e_2, 2e_1, 2e_2,
2(e_1 + e_2), e_1 + 2e_2, 2e_1 + e_2 \}.$$

\vespa

The exceptional choice $x = e_1, y = e_1 + e_2, z = e_1 + 2e_2$ on the other
hand, yields
$$
\left \{ \begin{array}{ccc}
A_0 & = & \{0, e_1, e_2, e_1 + e_2\} \\
A_1 & = & e_0 + \{0, u, v\} \\
A_2 & = & 2e_0 + \{e_1, e_1 + e_2, e_1 + 2e_2\}.
\end{array}
\right.
$$
We must have $A_1 + A_2 \subset A_0 +' A_0$ =
$\{e_1, e_2, e_1 + e_2, e_1 + 2e_2, 2e_1 + e_2\}$. We see then, by examining
the  possible candidates for $u + e_1$ and $v + e_1$, that
$u$ and $v$ must belong to the set
$\{e_2, 2e_1 + e_2, e_1 + e_2, 2e_2\}$. In fact, neither $u$ nor $v$ can be
equal to $2e_1 + e_2$ or $e_1 + e_2$, since then $e_1 + e_2 + u$
or $e_1 + e_2 + v$ would be equal to $2e_2$ or $2(e_1 + e_2)$, none of which
belongs to $A_0 +' A_0$.

The only remaining  possibility is $\{u, v\}$ = $\{e_2, 2e_2\}$. But, since
$u \not = v$, this would imply $u + v = 0$ and $2e \in A_1 +' A_1$.
However, $A_0 + A_2$ does not contain $2e$.

Hence, if $A \subset V$, a vector space over $\ft$, has cardinality 10 and
possesses a partition of type (4, 4, 2) or (4, 3, 3), then $|A+'A| \geq 18$.



We now finish up the case of flat partitions for $h \geq 3$ by
induction on $h$. Suppose $H$ is a hyperplane such that
$A_0 = A \esp \cap \esp H$ has cardinality $r = 1 + 3^{h-1}$ and
$r \geq s \geq t$, where as before $r, s,t$ are the cardinalities of the
intersections of $A$ with the various translates of $H$.

\vespa
\noindent
{\bf Claim.} {\em Suppose by induction on $h \geq 3$ that
$|A_0 +' A_0| \geq 2 \cdot 3^{h-1}$. Then, we have
$|A +' A| \geq 2 \cdot 3^{h}$.}

\vespa
\noindent
{\it Proof.} Since we assume $r = 1 + 3^{h-1}$ and $|A| = 1 + 3^{h}$ there
are only two possible partitions:
$$
\begin{array}{cccl}
(1) & (r, s, t) & = & (3^{h-1} + 1, 3^{h-1}, 3^{h-1}), \\
(2) & (r, s, t) & = & (3^{h-1} + 1, 3^{h-1} + 1, 3^{h-1} - 1),
\end{array}
$$
and we have
$$|A +' A| \geq |A_0 +' A_0| + \beta(r, s) + \beta(r, t).$$

\vespa

Using the 3-adic expansions of $r-1, s-1$, and $t-1$, we get in both
cases $\beta(r, s) = r + s - 1$ and $\beta(r, t) = r + t - 1$.

Of course, in both cases $s + t = 2 \cdot 3^{h-1}$ since
$r+s+t = |A| = 1 + 3^{h}$.

\vespa

Therefore, the induction assumption on $|A_0 +' A_0|$ yields
$$|A +' A| \geq 2 \cdot 3^{h-1} + 4 \cdot 3^{h-1} = 2 \cdot 3^{h}.$$ 

\vespa 

This finishes the proof of the claim and of Theorem (5.1). 
\hfill$\Box$


Summarizing our knowledge of $\mu_{3}'(r,s)$,
if $r = 1 + 3 + \sum_{i \geq 2} r_{i}3^{i}$ and
$s = 1 + 3 + \sum_{i \geq 2} s_{i}3^{i}$ form a special pair ({\em i.e.},
$r_{i} + s_{i} \leq 2$ for all $i \geq 2$), we have
$\mu_{3}'(r, s) = r + s - 3$.

If $(r, s)$ is a special pair for $p = 3$ but $r \equiv s \equiv 1$ mod 9, 
then the only case for which we know $\mu_{3}'(r, s)$ is $r = s = 1 + 3^{h}$,
namely $\mu_{3}'(r, s) = r + s - 2$ as proved in this paper. In all other 
cases, $r = 1 + 3^{h} + \sum_{i \geq h+1} r_{i}3^{i}$ and
$s = 1 + 3^{h} + \sum_{i \geq h+1} s_{i}3^{i}$ forming a special pair
with $h \geq 2$ and $(r, s) \neq (1+3^{h}, 1+3^{h})$, it remains an open
problem to decide whether $\mu_{3}'(r, s)$ equals $r+s-3$ or $r+s-2$.

If, still with $p = 3$,  $(r, s)$ is not a special pair at $p=3$, then
$\mu_{3}'(r, s)$ = $\gamma_{3}(r, s)$ as given by formula (6) or (7).

\section*{\normalsize Acknowledgments}
During the preparation of this paper, the first author
has partly benefited from a research contract with the Fonds National
Suisse pour la Recherche Scientifique.


%\centerline{{\large {\bf Bibliography}}}
\section*{\normalsize References}

\vskip -5pt
\noindent
[{\bf ANR}1] \hspace{2mm} N.~Alon, M.~B.~Nathanson and I.~Z.~Ruzsa, 
Adding Distinct Congruences Classes Modulo a Prime, {\it American Math.
Monthly}\, {\bf 102} (1995), 250-255.

\noindent
[{\bf ANR}2] \hspace{2mm} N.~Alon, M.~B.~Nathanson and I.~Z.~Ruzsa, 
The polynomial method and restricted sums of congruences classes,
{\it Journal of Number Theory}\, {\bf 56} (1996), 404-417.

\noindent
[{\bf DH}] \hspace{2mm} J.~A.~Dias da Silva and Y.~O.~Hamidoune, Cyclic spaces
for Grassmann derivatives and additive theory, {\it Bull. London
Math. Soc.}\, {\bf 26} (1994), 140-146.

\noindent
[{\bf EK}1] \hspace{2mm} S.~Eliahou and M.~Kervaire, Sumsets in vector 
spaces over a finite field, {\it Journal of Number Theory}\, {\bf 71} (1998), 12-39.

\noindent
[{\bf EK}2] \hspace{2mm} S.~Eliahou and M.~Kervaire, 
Restricted sums of sets of cardinality $1 + p$\/ in a
vector space over $\fp$, Preprint, Universit\'e du Littoral
C\^ote d'Opale, Cahiers du LMPA Joseph Liouville No. 75 (1998). To appear
in {\it Discrete Mathematics}.

\end{document}