RESTRICTED SUMSETS IN FINITE VECTOR SPACES: THE CASE p = 3

Shalom Eliahou

Département de Mathématiques, Université du Littoral Côte d’Opale, B.P. 699, 62228 Calais, France

                      eliahou@lmpa.univ-littoral.fr

Michel Kervaire

Département de Mathématiques, Université de Genève, B.P. 240, 1211 Genève 24, Suisse

Received: 3/31/2000, Revised: 1/2/01, Accepted: 2/27/01, Published: 3/9/01

Abstract

We determine the sharp lower bound for the cardinality of the restricted sumset A+′ B = {a + b | a ∈ A, b ∈ B, a ≠ b}, where A, B run over all subsets of size r = s = 1 + 3^{h} in a vector space over F_{3}. 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 β_{p}(r, s) and γ_{p}(r, s) for the cardinality of the ordinary sum and restricted sum of sets of size r, s in a vector space over F_{p}.

1. Introduction

Let V be a vector space over the finite field F_{p}. If A, B ⊂ V are two non-empty subsets of V, we define their restricted sumset A +′ B by

A +′ B = {a + b | a ∈ A, b ∈ B, a ≠ b}.

If r, s ≤ |V |, we define

μ′_{V} (r, s) = min |A +′ B|,

where A, B run over all subsets of V of cardinality r, s respectively.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 1 (2001), #A02 2

Erdős and Heilbronn conjectured in 1964 that if A is a subset of cardinality r in V = F_{p}, then |A +′ A| ≥ min{p, 2r − 3}. This conjecture was solved 30 years later by Dias da Silva and Hamidoune in [DH]. Using a different method, Alon, Nathanson and Ruzsa subsequently strengthened this result by establishing the equality

μ′_{F_{p}}(r, s) = \{ \begin{matrix}min\{p, 2r − 3\} & if r = s, \\ min\{p, r + s − 2\} & if r ≠ s. \end{matrix}

(See [ANR1, ANR2].)

The determination of μ′_{V} (r, s) for an arbitrary vector space V over F_{p} was taken up and completed for most pairs r, s in [EK1]. In summary, we have determined the value of μ′_{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 μ′_{V} (r, s) remains open for special pairs (r, s).

A pair of natural numbers (r, s) is said to be special for the odd prime p if r and s have p-adic expansions of the form

\{ \begin{matrix}r & = & 1 + ap^{h} + ∑_{i=h+1}^{n} r_{i}p^{i}, \\ s & = & 1 + ap^{h} + ∑_{i=h+1}^{n} s_{i}p^{i}, \end{matrix} (1)

with h ≥ 1 and coefficients a, r_{i}, s_{i} satisfying the conditions

\{ \begin{matrix}1 ≤ a ≤ \frac{p−1}{2}, and \\ r_{i} + s_{i} ≤ p − 1 for h + 1 ≤ i ≤ n. \end{matrix} (2)

We do know that for a special pair (r, s), we have either μ′_{V} (r, s) = r + s − 3 or else μ′_{V} (r, s) = r + s − 2. (See Corollary (7.5) in [EK1].) However resolving this alternative seems to be quite difficult.

The case r = s = 1 + p has been treated in our previous paper [EK2]. With the notation μ′_{p}(r, s) = min_{V} {μ′_{V} (r, s)}, we proved that

μ′_{p}(1 + p, 1 + p) = 2(1 + p) − 2 = 2p,

for p ≥ 5. (See [EK2], 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 ≥ 5.

For p = 3, there is the example A = B = {0, e_{1}, e_{2}, e_{1} + e_{2}} in the plane V = F_{3}e_{1} ⊕ F_{3}e_{2} with |A| = |B| = 4 and |A +′ B| = |{e_{1}, e_{2}, e_{1} + e_{2}, 2e_{1} + e_{2}, e_{1} + 2e_{2}}| = 5 realizing the lower bound μ′_{3}(4, 4) = 5 = r + s − 3 for r = s = 4.

We know from Theorem (7.10) in [EK1] that the existence of this simple example implies that if r, s have 3-adic expansions of the form

\{ \begin{matrix}r & = & 1 + 3 + ∑_{i≥2} r_{i}3^{i}, \\ s & = & 1 + 3 + ∑_{i≥2} s_{i}3^{i}, \end{matrix}

where r_{i} + s_{i} ≤ 2 for all i ≥ 2, then μ′_{3}(r, s) = r + s − 3.

In the present paper, we solve the question of determining the value of μ′_{V} (r, s) at p = 3 for the particular special pairs (r, s) of the form

r = s = 1 + 3^{h},

where h ≥ 2. The corresponding problem for p ≥ 5 remains open.

Our main result, which was conjectured in [EK1] at least for h = 2, is :

Theorem. Let A, B ⊂ V be subsets of cardinality 1 + 3^{h} with h ≥ 2 in a vector space V over F_{3}. Then,

|A +′ B| ≥ 2 · 3^{h}.

This lower bound 2 · 3^{h} is sharp, i.e., μ′_{3}(1 + 3^{h}, 1 + 3^{h}) = 2 · 3^{h}.

The above examples of special pairs (r, s) with r ≡ s ≡ 4 mod 3^{2} happen in fact to be the only examples we know of special pairs (r, s) for which μ′_{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 ⊂ V whose cardinalities do not necessarily form a special pair.

Formulas for these lower bounds β_{p}(r, s) and γ_{p}(r, s), for arbitrary odd prime p, were given in [EK1]. 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| ≡ |B| ≡ 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.

2. Basic results and explicit formulas for β_{p}(r, s) and γ_{p}(r, s)

Given an odd prime p and positive integers r, s, let

β_{p}(r, s) = min {n ∈ N | (x + y)^{n} ∈ (x^{r}, y^{s})F_{p}[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 F_{p}[x, y].

We have proved in [EK1] that for any A, B ⊂ V of cardinalities |A| = r and |B| = s, one has the inequality |A + B| ≥ β_{p}(r, s), (3)

using the usual notation A + B = {a + b | a ∈ A, b ∈ B}.

Moreover, this lower bound is sharp, i.e., if μ_{V} (r, s) denotes the smallest possible value of |A + B| for all A, B ⊂ V of cardinalities |A| = r, |B| = s then μ_{V} (r, s) = β_{p}(r, s), provided r, s ≤ |V |.

We also obtained in [EK1], by a similar method, a lower bound γ_{p}(r, s) for the size of the restricted sumset A +′ B = {a + b | a ∈ A, b ∈ B, a ≠ b}. More precisely, let

γ_{p}(r, s) = min{n ∈ N | (x − y)(x + y)^{n} ∈ (x^{r}, y^{s})F_{p}[x, y]},

then we have |A +′ B| ≥ γ_{p}(r, s). (4)

However, the lower bound γ_{p}(r, s) need not be sharp if (r, s) is a special pair for the odd prime p. It is indeed sharp, i.e., μ′_{p}(r, s) = γ_{p}(r, s) if (r, s) is not a special pair.

We now produce explicit formulas for these lower bounds β_{p}(r, s) and γ_{p}(r, s).

Given positive integers r and s, let r − 1 = ∑_{i=0}^{n} r_{i}p^{i}, s − 1 = ∑_{i=0}^{n} s_{i}p^{i} be the p-adic expansions of r − 1 and s − 1, i.e., 0 ≤ r_{i} ≤ p − 1 and 0 ≤ s_{i} ≤ p − 1 for all i ∈ [0, n].

Define the integer m ∈ Z by the formula m = max({−1} ∪ {i ∈ [0, n] | r_{i} + s_{i} ≥ p}).

In other words, m = −1 if for all i ∈ [0, n] we have r_{i} + s_{i} ≤ p − 1. Else, m is characterized by the inequalities r_{m} + s_{m} ≥ p and r_{i} + s_{i} ≤ p − 1 for i ∈ [m + 1, n]. (This last interval being of course empty if m = n, i.e., if r_{n} + s_{n} ≥ p.)

With this notation, the function β_{p}(r, s) is given by

\begin{aligned}β_{p}(r, s) & = & p^{m+1} + ∑_{i=m+1}^{n}(r_{i} + s_{i})p^{i} \\ & = & s + ∑_{i=m+1}^{n} r_{i}p^{i} + (p^{m+1} − 1 − ∑_{i=0}^{m} s_{i}p^{i}). \end{aligned} (5)

Note that β_{p}(r, s) = r + s − 1 if m = −1, i.e., if r_{i} + s_{i} ≤ p − 1 for all i ∈ [0, n].

The formula for γ_{p}(r, s) involves a somewhat more complicated case distinction.

If r = s = 1, then γ_{p}(1, 1) = 0. If r + s ≥ 3, then

(6) γ_{p}(r, s) = \{ \begin{matrix}β_{p}(r, s) & if \binom{r+s−2}{r−1} ≡ 0 mod p, \\ r + s − 3 & if \binom{r+s−2}{r−1} ≢ 0 and \binom{r+s−3}{r−1} ≡ \binom{r+s−3}{s−1} mod p, \\ r + s − 2 & if \binom{r+s−2}{r−1} ≢ 0 and \binom{r+s−3}{r−1} ≢ \binom{r+s−3}{s−1} mod p. \end{matrix}

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

If r + s ≥ 3 as above, then

(7) γ_{p}(r, s) = \{ \begin{matrix}β_{p}(r, s) & if there exists an index j \\ & such that r_{j} + s_{j} ≥ p, \\ r + s − 3 & if r_{i} + s_{i} ≤ p − 1 for all i, and \\ & ν_{p}(r − 1) = ν_{p}(s − 1) = v, say, \\ & with r_{v} = s_{v}, \\ r + s − 2 & otherwise, i.e., still with r_{i} + s_{i} ≤ p − 1 \\ & for all i, but either ν_{p}(r − 1) ≠ ν_{p}(s − 1) \\ & or, with v as above, r_{v} ≠ s_{v}, \end{matrix}

where ν_{p}(r − 1) is the p-valuation of r − 1, i.e., ν_{p}(r − 1) = v if the p-adic expansion of r − 1 has the form r − 1 = r_{v}p^{v} + ∑_{i>v} r_{i}p^{i} with r_{v} ≠ 0.

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 ν_{p}(r−1) = ν_{p}(s−1) ≥ 1.

Hence, the statement “μ′_{V} (r, s) = r + s − 3 or else μ′_{V} (r, s) = r + s − 2” in the Introduction amounts for special pairs to the inequalities

γ_{p}(r, s) ≤ μ′_{V} (r, s) ≤ γ_{p}(r, s) + 1

which are true in general. (Compare also the version of the definition of a special pair given in [EK1], Definition (7.8).) It is a theorem in [EK1] (see Theorem (7.9)) that μ′_{V} (r, s) = γ_{p}(r, s) for non-special pairs.

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 [EK1].

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

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 1 (2001), #A02 6

We begin with a remark on the binomial coefficient \binom{r+s−2}{r−1} which is the content of Lemma (7.2) in [EK1].

Let r − 1 = ∑_{i≥0} r_{i}p^{i} and s − 1 = ∑_{i≥0} s_{i}p^{i} be the p-adic expansions of r − 1 and s − 1. If r + s − 2 = ∑_{i≥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,

\binom{r + s − 2}{r − 1} ≡ ∏_{i≥0} \binom{t_{i}}{r_{i}} mod p,

shows easily that \binom{r+s−2}{r−1} ≢ 0 mod p if and only if 0 ≤ r_{i} + s_{i} ≤ p − 1 for all i.

By definition, β_{p}(r, s) = min{n ∈ N | (x + y)^{n} ∈ 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 F_{p}[x, y].

Since (x + y)^{r+s−1} = ∑_{i=0}^{r+s−1} \binom{r+s−1}{i}x^{i}y^{r+s−1−i}, and either i ≥ r, or if i ≤ r − 1, then r + s − 1 − i ≥ s, it follows that (x + y)^{r+s−1} ∈ I(r, s) and β_{p}(r, s) ≤ r + s − 1.

Furthermore, the congruence (x+y)^{r+s−2} ≡ \binom{r+s−2}{r−1}x^{r−1}y^{s−1} mod I(r, s) gives β_{p}(r, s) = r + s − 1 if \binom{r+s−2}{r−1} ≢ 0 mod p.

Thus,

β_{p}(r, s) = r + s − 1, if r_{i} + s_{i} ≤ p − 1 for all i ≥ 0.

If, on the other hand, there exists an index m such that r_{m}+s_{m} ≥ p and r_{i}+s_{i} ≤ p−1 for i ≥ m + 1, then we write

\{ \begin{matrix}r − 1 & = & a_{0} + a_{1}p^{m+1}, \\ s − 1 & = & b_{0} + b_{1}p^{m+1}, \end{matrix}

where a_{0} = ∑_{i=0}^{m} r_{i}p^{i} , and b_{0} = ∑_{i=0}^{m} s_{i}p^{i}, and of course, a_{1}, b_{1} are non-negative integers. Note for further use that p^{m+1} = p · p^{m} ≤ (r_{m} + s_{m})p^{m} ≤ a_{0} + b_{0}. We claim that, using the above notation, β_{p}(r, s) is given by

β_{p}(r, s) = p^{m+1} + ∑_{i≥m+1}(r_{i} + s_{i})p^{i} = p^{m+1}(1 + a_{1} + b_{1}).

In order to prove this, we calculate

\begin{aligned}(x + y)^{p^{m+1}(a_{1}+b_{1}+1)} & ≡ & (x^{p^{m+1}} + y^{p^{m+1}})^{a_{1}+b_{1}+1} mod p \\ & = & ∑_{i=0}^{a_{1}+b_{1}+1} \binom{a_{1}+b_{1}+1}{i}x^{p^{m+1}i}y^{p^{m+1}j}, \end{aligned}

where i + j = a_{1} + b_{1} + 1.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 1 (2001), #A02 7

For i ≤ a_{1}, we have j ≥ b_{1} + 1 and since

s − 1 = b_{0} + p^{m+1}b_{1} ≤ p^{m+1} − 1 + p^{m+1}b_{1} ≤ p^{m+1}j − 1

it follows that p^{m+1}j > s and y^{p^{m+1}j} ∈ (x^{r}, y^{s}).

Similarly, if i ≥ a_{1} + 1, then j ≤ b_{1}. As above, we have p^{m+1}i > r and x^{p^{m+1}i} ∈ I(r, s) = (x^{r}, y^{s}).

Therefore (x+y)^{p^{m+1}(1+a_{1}+b_{1})} ∈ I(r, s), and β_{p}(r, s) ≥ p^{m+1}(1+a_{1} +b_{1}) by definition. We now calculate

\begin{aligned}(x + y)^{p^{m+1}(a_{1}+b_{1}+1)−1} & ≡ (x^{p^{m+1}} + y^{p^{m+1}})^{a_{1}+b_{1}} · (\frac{x^{p^{m+1}}+y^{p^{m+1}}}{x+y}) mod p \\ & ≡ ∑_{i=0}^{a_{1}+b_{1}} \binom{a_{1}+b_{1}}{i}x^{p^{m+1}i}y^{p^{m+1}j} · ∑_{k=0}^{p^{m+1}−1}(−1)^{k}x^{k}y^{ℓ} mod p, \end{aligned}

where i + j = a_{1} + b_{1} and k + ℓ = p^{m+1} − 1.

For i > a_{1}, we have p^{m+1}i > p^{m+1}−1+p^{m+1}a_{1} ≥ r−1. It follows that x^{p^{m+1}i} ∈ I(r, s). Similarly, y^{p^{m+1}j} ∈ I(r, s) for j > b_{1}. Hence,

(x + y)^{p^{m+1}(a_{1}+b_{1}+1)−1} ≡ \binom{a_{1} + b_{1}}{a_{1}}x^{p^{m+1}a_{1}}y^{p^{m+1}b_{1}} · ∑_{k=0}^{p^{m+1}−1}(−1)^{k}x^{k}y^{ℓ},

modulo I(r, s), with ℓ = p^{m+1} − k − 1.

As noted above, a_{0} + b_{0} ≥ (r_{m} + s_{m})p^{m} ≥ p^{m+1}. For k in the interval p^{m+1} − b_{0} − 1 ≤ k ≤ a_{0}, we have ℓ = p^{m+1} − k − 1 ≤ b_{0}. Therefore, still modulo I(r, s), we have

(x + y)^{p^{m+1}(a_{1}+b_{1}+1)−1} ≡ ∑_{p^{m+1}−b_{0}−1≤k≤a_{0}}(−1)^{k}\binom{a_{1} + b_{1}}{a_{1}}x^{k+p^{m+1}a_{1}}y^{ℓ+p^{m+1}b_{1}},

and the monomials x^{k+p^{m+1}a_{1}}y^{ℓ+p^{m+1}b_{1}}, for the indicated interval of values of k and ℓ are part of an F_{p}-basis of F_{p}[x, y]/I(r, s).

Now, certainly, (−1)^{k} ≢ 0 mod p, and using again the Lucas formula and the inequalities r_{i} + s_{i} ≤ p − 1 for i ≥ m + 1, we have

\binom{a_{1} + b_{1}}{a_{1}} ≡ ∏_{i≥m+1} \binom{r_{i} + s_{i}}{r_{i}} ≢ 0 mod p.

Hence,

(x + y)^{p^{m+1}(a_{1}+b_{1}+1)−1} ∉ I(r, s).

It follows that β_{p}(r, s) = p^{m+1}(1 + a_{1} + b_{1}) as asserted.

We now prove the formula (6) for γ_{p}(r, s). Let γ = γ_{p}(r, s), β = β_{p}(r, s), to simplify notation.

Suppose first that there exists an index n for which r_{n}+s_{n} ≥ p in the p-adic expansions r − 1 = ∑_{i≥0} r_{i}p^{i} and s − 1 = ∑_{i≥0} s_{i}p^{i} of r − 1 and s − 1, then \binom{r+s−2}{r−1} ≡ 0 mod p. Indeed, taking n such that r_{i} + s_{i} ≤ p − 1 for i < n, we have the p-adic expansion r + s − 2 = ∑_{i≥0} t_{i}p^{i} with t_{n} = r_{n} + s_{n} − p < r_{n}, and by the Lucas formula

\binom{r + s − 2}{r − 1} ≡ ∏_{k≥0} \binom{t_{k}}{r_{k}} ≡ 0 mod p,

because the factor \binom{t_{n}}{r_{n}}, where t_{n} < r_{n}, is congruent to 0 mod p.

It follows from

(x + y)^{β} = ∑_{i} \binom{β}{i}x^{i}y^{β−i} ≡ ∑_{i=β−s+1}^{r−1} \binom{β}{i}x^{i}y^{β−i} ≡ 0 mod I(r, s) = (x^{r}, y^{s}),

that \binom{β}{i} ≡ 0 mod p in the range i = β − s + 1, …, r − 1.

Now, \binom{β}{i} = \binom{β−1}{i−1} + \binom{β−1}{i} implies that all coefficients \binom{β−1}{i} for i = β − s, …, r − 1 are mutually congruent modulo p, up to sign, and thus are simultaneously ≡ 0 or ≢ 0 mod p.

We must have \binom{β−1}{i} ≢ 0 mod p, for i = β − s, …, r − 1 since (x + y)^{β−1} ∉ I(r, s).

It follows that

(x − y)(x + y)^{β−1} = (x + y)^{β} − 2y(x + y)^{β−1}

≡ −2 ∑_{i=β−s+1}^{r−1} \binom{β−1}{i}x^{i}y^{β−i} ≢ 0 mod(x^{r}, y^{s}),

and thus γ_{p}(r, s) = β_{p}(r, s) in the case \binom{r+s−2}{r−1} ≡ 0 mod p.

Suppose now that r_{i}+s_{i} ≤ p−1 for all i ≥ 0 in the p-adic expansions r−1 = ∑_{i≥0} r_{i}p^{i} and s − 1 = ∑_{i≥0} s_{i}p^{i} of r − 1 and s − 1.

An easy calculation shows that, modulo I(r, s) = (x^{r}, y^{s})F_{p}[x, y], and for r + s ≥ 3, r ≥ s, we have the congruence

(x − y)(x + y)^{r+s−3} ≡ \{\binom{r + s − 3}{r − 2} − \binom{r + s − 3}{r − 1}\}x^{r−1}y^{s−1}.

It follows easily that γ_{p}(r, s) = r + s − 2 if \binom{r+s−2}{r−1} ≢ 0 mod p and \binom{r+s−3}{s−1} ≢ \binom{r+s−3}{r−1} mod p.

Moreover, we see that γ_{p}(r, s) ≤ r + s − 3 if \binom{r+s−2}{r−1} ≢ 0 mod p and \binom{r+s−3}{s−1} ≡ \binom{r+s−3}{r−1} mod p.

To prove that in this last case we have γ_{p}(r, s) = r + s − 3, it suffices to show that (x − y)(x + y)^{r+s−4} ≢ 0 modulo the ideal I(r, s) = (x^{r}, y^{s})F_{p}[x, y].

This is obvious for r = s = 2, and for r ≥ 3, s ≥ 2 an easy calculation shows that (x − y)(x + y)^{r+s−4} is congruent modulo I(r, s) to

\{\binom{r + s − 4}{r − 3} − \binom{r + s − 4}{r − 2}\}x^{r−2}y^{s−1} + \{\binom{r + s − 4}{r − 2} − \binom{r + s − 4}{r − 1}\}x^{r−1}y^{s−2}.

By a simple lemma on binomial coefficients, Lemma (6.5) of [EK2], the two coefficients in this expression could only both vanish if we had

\binom{r + s − 4}{r − 3} ≡ \binom{r + s − 4}{r − 2} ≡ \binom{r + s − 4}{r − 1} ≡ 0 mod p.

This would imply \binom{r+s−2}{r−1} ≡ 0 mod p, contrary to the hypothesis. This finishes our discussion of formulas (5) and (6).

As an application of the formulas, note that

γ_{p}(1 + ap^{h}, 1 + ap^{h}) = 2ap^{h} − 1, β_{p}(1 + ap^{h}, 1 + ap^{h}) = 2ap^{h} + 1

if 1 ≤ a ≤ \frac{p−1}{2}. We shall use these values in the next section.

3. The case of unequal sets

Let A, B ⊂ V be subsets of a vector space V over F_{p}, of cardinality |A| = |B| = 1 + ap^{h}.

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

Indeed, we prove

Proposition (3.1) Let the subsets A, B ⊂ V both have cardinality 1 + ap^{h}, where h ≥ 1 and 1 ≤ a ≤ \frac{p−1}{2}. If A ≠ B then

|A +′ B| ≥ γ_{p}(1 + ap^{h}, 1 + ap^{h}) + 1 = 2ap^{h}.

Proof. Let X = A ∩ B and Y = A ∪ B. If X = ∅, then A +′ B = A + B and

|A +′ B| = |A + B| ≥ β_{p}(1 + ap^{h}, 1 + ap^{h}) = 2ap^{h} + 1.

Assume now that X ≠ ∅. Set r = |X| ≥ 1, and thus |Y | = 2ap^{h} + 2 − r. We have X +′ Y ⊂ A +′ B. Therefore |A +′ B| ≥ |X +′ Y | ≥ γ_{p}(r, 2ap^{h} + 2 − r).

We claim that for 1 ≤ r ≤ ap^{h} we have γ_{p}(r, 2ap^{h} + 2 − r) = 2ap^{h}.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 1 (2001), #A02 10

We set

R = r , S = 2ap^{h} + 2 − r

and write the p-adic expansions

\{ \begin{matrix}R + S − 2 & = & 2ap^{h}, \\ R − 1 & = & r_{0} + r_{1}p + … + r_{h−1}p^{h−1} + r_{h}p^{h}, \end{matrix}

where r_{h} < a, since X = A ∩ B ⊂ A and A ∩ B ≠ A.

We have

\binom{R + S − 2}{R − 1} = \binom{2ap^{h}}{r − 1} ≡ \binom{0}{r_{0}} ⋯ \binom{0}{r_{h−1}} · \binom{2a}{r_{h}} mod p.

The only case where this number is ≢ 0 mod p is when r_{0} = r_{1} = … = r_{h−1} = 0, and thus r = 1 + cp^{h}, with 0 ≤ c ≤ a − 1.

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

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

\{ \begin{matrix}R + S − 3 & = & ∑_{i=0}^{h−1}(p − 1)p^{i} + (2a − 1)p^{h}, \\ R − 1 & = & cp^{h}, \\ S − 1 & = & (2a − c)p^{h}. \end{matrix}

By the formula of Lucas,

\binom{R+S−3}{R−1} ≡ \binom{2a−1}{c} and \binom{R+S−3}{S−1} ≡ \binom{2a−1}{2a−c} mod p.

Now, since c < a ≤ \frac{p−1}{2}, we have c ≢ a mod p, and therefore

γ_{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_{1}p + … + r_{h−1}p^{h−1} + r_{h}p^{h},

with 0 ≤ r_{h} ≤ a − 1 and (r_{0}, r_{1}, …, r_{h−1}) ≠ (0, 0, …, 0). We then have

\binom{R + S − 2}{R − 1} = \binom{2ap^{h}}{r − 1} ≡ 0 mod p.

Hence γ_{p}(r, 2ap^{h} + 2 − r) = β_{p}(r, 2ap^{h} + 2 − r).

We claim that β_{p}(r, 2ap^{h} + 2 − r) = 2ap^{h}.

Let 0 ≤ m ≤ h − 1 be the index defined by r_{0} = … = r_{m−1} = 0 and r_{m} ≠ 0.

The p-adic expansions of R − 1 and S − 1 have the form

\{ \begin{matrix}R − 1 & = & r_{m}p^{m}+ & ∑_{i=m+1}^{h−1} r_{i}p^{i}+ & r_{h}p^{h}, \\ S − 1 & = & (p − r_{m})p^{m}+ & ∑_{i=m+1}^{h−1}(p − 1 − r_{i})p^{i}+ & (2a − 1 − r_{h})p^{h}. \end{matrix}

Therefore, we have β_{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

β_{p}(R, S) = p^{m+1} + (p − 1)p^{m+1} + … + (p − 1)p^{h−1} + (2a − 1)p^{h} = 2ap^{h}.

This finishes the proof of the proposition. □

Henceforth, we shall be dealing with the restricted sumset of a single subset A ⊂ V with itself, i.e., A +′ A.

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 ⊂ V and slicing the set A by the translates of H. Let e ≠ 0 be a vector outside H, so that V = F_{p}e ⊕ H. For c ∈ F_{p}, we denote by H_{c} the (affine) hyperplane c · e + H and let A_{c} = A ∩ H_{c}. A translation of A does not change |A +′ A|. Hence, we may assume that the size of A_{0} = A ∩ H is maximal in the collection of sizes {|A_{c}|, c ∈ F_{p}}. We set r = |A_{0}|.

Let C = {0, c_{1}, …, c_{ℓ}} denote the set of classes c ∈ F_{p} such that A_{c} ≠ ∅. We may also assume that the classes c_{1}, …, c_{ℓ} are ordered so that |A_{0}| ≥ |A_{c_{1}}| ≥ … ≥ |A_{c_{ℓ}}| ≥ 1.

We use the notation s_{i} = |A_{c_{i}}| for 1 ≤ i ≤ ℓ and therefore we have the inequalities r ≥ s_{1} ≥ … ≥ s_{ℓ} ≥ 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}, …, s_{ℓ}) the 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 ≤ ℓ ≤ p − 1.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 1 (2001), #A02 12

The case where ℓ = 1, when |A| = 1 + ap^{h}, with 1 ≤ a ≤ \frac{p−1}{2}, h ≥ 1, can be treated at once. This special case will be used in the next section. Proposition (4.1) Suppose that the subset A ⊂ 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| ≥ 2ap^{h} = γ_{p}(1 + ap^{h}, 1 + ap^{h}) + 1.

Proof. By hypothesis, A = A_{0} ∐ 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}) ∐(A_{0} + A_{1}) and therefore |A +′ A| ≥ γ_{p}(ap^{h}, ap^{h}) + β_{p}(ap^{h}, 1).

The p-adic expansion of ap^{h} − 1 is

ap^{h} − 1 = ∑_{i=0}^{h−1}(p − 1)p^{i} + (a − 1)p^{h}.

Therefore, γ_{p}(ap^{h}, ap^{h}) = β_{p}(ap^{h}, ap^{h}) = p^{h} + 2(a − 1)p^{h}.

Since β_{p}(ap^{h}, 1) = ap^{h}, it follows that

|A +′ A| ≥ p^{h} + 2(a − 1)p^{h} + ap^{h} = 2ap^{h} + (a − 1)p^{h} ≥ 2ap^{h},

with equality if and only if a = 1.

Suppose now that s ≥ 2. We have

A +′ A = (A_{0} +′ A_{0}) ∐(A_{0} + A_{1}) ∐(A_{1} +′ A_{1}),

where the sets are disjoint because they belong to distinct hyperplanes, namely H, H_{1} = e + H and H_{2} = 2e + H respectively.

We shall evaluate the right-hand side of the resulting inequality |A +′ A| ≥ γ_{p}(r, r) + β_{p}(r, s) + γ_{p}(s, s).

Let r − 1 = ∑_{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 = ∑_{i=0}^{h} s_{i}p^{i} = ∑_{i=0}^{h−1}(p − 1 − r_{i})p^{i} + (a − 1 − r_{h})p^{h},

where 0 ≤ a − 1 − r_{h} because r − 1 < ap^{h} and hence r_{h} ≤ a − 1.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 1 (2001), #A02 13

As a first consequence, we get β_{p}(r, s) = r+s−1 by formula (5). Indeed, r_{i}+s_{i} = p−1, for i = 0, …, h − 1 and r_{h} + s_{h} = a − 1 < p − 1. Thus β_{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,

γ_{p}(t, t) = \{ \begin{matrix}2t − 3 & if 2t_{i} ≤ p − 1 for all i ∈ [0, h] \\ p^{m+1} + 2 ∑_{i=m+1}^{h} t_{i}p^{i} & otherwise, \end{matrix}

where m = max({−1} ∪ {i ∈ [0, h] | 2t_{i} ≥ p}).

We want to evaluate τ = γ_{p}(r, r) + β_{p}(r, s) + γ_{p}(s, s).

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

• If 2r_{i} ≤ p−1 and 2s_{i} ≤ p−1 for all i ∈ [0, h], then γ_{p}(r, r) = 2r−3 and γ_{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, τ = γ_{p}(r, r) + β_{p}(r, s) + γ_{p}(s, s) = 2r − 3 + ap^{h} + 2s − 3 = 2ap^{h} + (ap^{h} − 4). Thus, τ > 2ap^{h} except for a = 1, p = 3, h = 1 as we already know.

• If 2r_{i} ≤ p − 1 for all i = 0, …, h, but r_{j} < \frac{p−1}{2} for at least one index j, then necessarily j ≤ h − 1, and 2s_{j} = 2(p − 1 − r_{j}) ≥ p. Therefore

γ_{p}(s, s) = s + ∑_{i=m+1}^{h−1}(p − 1 − r_{i})p^{i} + (a − 1 − r_{h})p^{h} + (p^{m+1} − 1 − ∑_{i=0}^{m} s_{i}p^{i}),

and so

γ_{p}(s, s) ≥ s + (a − 1 − r_{h})p^{h}.

Hence,

τ ≥ 2r − 3 + ap^{h} + s + (a − 1 − r_{h})p^{h}
≥ (r − 2) + 2ap^{h} + (a − 1 − r_{h})p^{h}
≥ 2ap^{h}.

• The case where there exists an index m ∈ [0, h − 1] such that 2r_{m} ≥ p and 2r_{i} ≤ p − 1 for i ∈ [m + 1, h], and where 2s_{i} ≤ p − 1 for all i = 0, …, h − 1, h is quite symmetrical. Then, τ ≥ r + ∑_{i=m+1}^{h} r_{i}p^{i} + ap^{h} + 2s − 3. Thus, τ ≥ 2ap^{h} + (s − 2) + ∑_{i=m+1}^{h} r_{i}p^{i}. This is strictly larger than 2ap^{h}, even if s = 2.

• Finally, if there exist m and n such that 2r_{m} ≥ p and 2s_{n} ≥ p, and m, n are the maximal indices with this property, then

τ ≥ r + ∑_{i=m+1}^{h} r_{i}p^{i} + ap^{h} + s + ∑_{i=n+1}^{h} s_{i}p^{i}.

Thus, clearly, τ ≥ 2ap^{h} + 1. □

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 1 (2001), #A02 14

5. The value of μ′_{3}(1 + 3^{h}, 1 + 3^{h})

In this section we take p = 3 and since μ′_{3}(4, 4) = γ_{3}(4, 4) = 5, we assume h ≥ 2. Theorem (5.1) For h ≥ 2, we have μ′_{3}(1 + 3^{h}, 1 + 3^{h}) = 2 · 3^{h}. Proof. Step 1. Unequal sets A and B.

Let A, B be subsets of cardinality 1 + 3^{h} in some vector space V over F_{3}. We claim that |A +′ B| ≥ 2 · 3^{h}. If A ≠ B, this is just Proposition (3.1) with p = 3, and a = 1.

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

Let (r, s, t) be the partition of 1+3^{h} associated with some decomposition V = F_{3}·e⊕H, i.e., r = |A ∩ H|, s = |A ∩ H_{1}|, t = |A ∩ H_{2}|, where H_{i} = i · e + H. We may assume that e ∈ A and r ≥ s ≥ t. As above, we set A_{i} = A ∩ H_{i}. Of course A = A_{0} ∐ A_{1} ∐ A_{2}. Step 2. Partitions of length 2.

If t = 0, it follows from Proposition (4.1) that

|A +′ A| ≥ 2 · 3^{h},

as desired.

The proof in the case where r ≥ s ≥ t ≥ 1 involves an induction on h in the case of a flat partition. In this section, we call flat partition a partition with r = 1 + 3^{h−1}. Note that this is the smallest possible value of r since r ≥ s ≥ 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. 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} ≤ r ≤ 3^{h} − 1,

and of course r ≥ s ≥ t ≥ 1.

We have

A +′ A ⊃ (A_{0} +′ A_{0}) ∐(A_{0} + A_{1}) ∐(A_{0} + A_{2})

and therefore,

\begin{aligned}|A +′ A| & ≥ & |A_{0} +′ A_{0}| + |A_{0} + A_{1}| + |A_{0} + A_{2}| \\ & ≥ & γ(r, r) + β(r, s) + β(r, t), \end{aligned}

where we write γ and β for γ_{3} and β_{3} respectively to simplify notation.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 1 (2001), #A02 15

Assertion. In the above range for the parameters (r, s, t), namely 2+3^{h−1} ≤ r ≤ 3^{h} −1, and r ≥ s ≥ t ≥ 1, we have γ(r, r) + β(r, s) + β(r, t) ≥ 2 · 3^{h} + 1.

We first write the 3-adic expansions of r − 1, s − 1 and t − 1 :

\begin{aligned}r − 1 & = & r_{0} + r_{1}3 + … + r_{h−2}3^{h−2} + 3^{h−1}, \\ s − 1 & = & s_{0} + s_{1}3 + … + s_{h−2}3^{h−2} + s_{h−1}3^{h−1}, \\ t − 1 & = & t_{0} + t_{1}3 + … + t_{h−2}3^{h−2} + t_{h−1}3^{h−1}. \end{aligned}

In order to calculate β(r, s) and β(r, t) using formula (5) in Section 2, we set m = max({−1} ∪ {i ∈ [0, h − 1] | r_{i} + s_{i} ≥ 3}). Similarly, we also need n = max({−1} ∪ {i ∈ [0, h − 1] | r_{i} + t_{i} ≥ 3}).

Note that m ≤ h − 2 and n ≤ h − 2 because s, t ≤ r.

By formulas (5) and (6) or (7), we have

γ(r, r) = \{ \begin{matrix}(a) & 2r − 3, \\ & if r_{i} ≤ 1 for all i = 0, …, h − 2 \\ (b) & 3^{ℓ+1} + 2(∑_{i=ℓ+1}^{h−2} r_{i}3^{i}) + 2 · 3^{h−1}, \\ & if r_{ℓ} = 2 and r_{i} ≤ 1 for i ≥ ℓ + 1 \end{matrix}

and

β(r, s) + β(r, t) = 3^{m+1} + ∑_{i=m+1}^{h−1}(r_{i} + s_{i})3^{i} + 3^{n+1} + ∑_{i=n+1}^{h−1}(r_{i} + t_{i})3^{i},

where r_{h−1} = 1.

We set σ = γ(r, r) + β(r, s) + β(r, t) and claim that σ ≥ 1 + 2 · 3^{h}.

Suppose first that r_{i} ≤ 1 for all indices i = 0, …, h − 1 in the 3-adic expansion of r − 1, so that case (a) prevails in the formula above for γ(r, r). Then,

\begin{aligned}σ & ≥ & 2r − 3 + s + ∑_{i=m+1}^{h−1} r_{i}3^{i} + t + ∑_{i=n+1}^{h−1} r_{i}3^{i} \\ & ≥ & (r − 2) + (r + s + t − 1) + 2 · 3^{h−1} = r − 2 + 3^{h} + 2 · 3^{h−1}. \end{aligned}

Since r ≥ 2 + 3^{h−1}, we get σ ≥ 2 · 3^{h}.

Note however that for r = 2 + 3^{h−1}, the only possibilities for the pair (s, t) are (2 + 3^{h−1}, −3 + 3^{h−1}) if h ≥ 3, and (1 + 3^{h−1}, −2 + 3^{h−1}), (3^{h−1}, −1 + 3^{h−1}), for h ≥ 2.

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

For h = 3, the three partitions (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 σ = 1 + 2 · 3^{h}, 2 + 2 · 3^{h}, and 1 + 2 · 3^{h}.

Hence, in case (a), we have indeed σ ≥ 2 · 3^{h}.

Suppose now that we are in case (b) in the formula above for γ(r, r). Then, still with σ = γ_{p}(r, r) + β_{p}(r, s) + γ_{p}(s, s), we have

\begin{aligned}σ & = γ(r, r) + β(r, s) + β(r, t) \\ & = 3^{ℓ+1} + 2(∑_{i=ℓ+1}^{h−1} r_{i}3^{i}) + 3^{m+1} + ∑_{i=m+1}^{h−1}(r_{i} + s_{i})3^{i} + 3^{n+1} + ∑_{i=n+1}^{h−1}(r_{i} + t_{i})3^{i} \end{aligned}

where as before r_{h−1} = 1.

Replacing one copy of ∑_{i=ℓ+1}^{h−1} r_{i}3^{i} in the first summation by the equal quantity r −1− ∑_{i=0}^{ℓ} r_{i}3^{i}, and similarly, ∑_{i=m+1}^{h−1} s_{i}3^{i} by s−1−∑_{i=0}^{m} s_{i}3^{i} and ∑_{i=n+1}^{h−1} t_{i}3^{i} by t−1−∑_{i=0}^{n} t_{i}3^{i}, we get

σ = r + s + t − 3 + ∑_{i=ℓ+1}^{h−1} r_{i}3^{i} + (3^{ℓ+1} − ∑_{i=0}^{ℓ} r_{i}3^{i})
+ ∑_{i=m+1}^{h−1} r_{i}3^{i} + (3^{m+1} − ∑_{i=0}^{m} s_{i}3^{i})
+ ∑_{i=n+1}^{h−1} r_{i}3^{i} + (3^{n+1} − ∑_{i=0}^{n} t_{i}3^{i}).

Now, r+s+t = 3^{h}+1. Since ℓ, m, n ≤ h−2, the three summations ∑_{i=ℓ+1}^{h−1} r_{i}3^{i}, ∑_{i=m+1}^{h−1} r_{i}3^{i} and ∑_{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} − ∑_{i=0}^{k} u_{i}3^{i}, with (k, u_{i}) = (ℓ, r_{i}), (m, s_{i}) and (n, t_{i}) respectively, are at least 1.

Summarizing, we get γ(r, r) + β(r, s) + β(r, t) ≥ 2 · 3^{h} + 1 also in the case encoded as (b).

Step 4. Flat partitions.

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

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

A +′ A ⊃ (A_{0} +′ A_{0}) ∐(A_{0} + A_{1}) ∐(A_{0} + A_{2}),

and γ_{3}(4, 4) = 5, β_{3}(4, 4) = 7, β_{3}(4, 2) = 5 with sum 17, the assertion |A +′ A| ≥ 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 γ_{3}(4, 4), β_{3}(4, 4), β_{3}(4, 2) respectively.

We will show that if |A_{0} +′ A_{0}| = 5, then |A_{0} + A_{2}| ≥ β_{3}(4, 2) + 1 = 6. We express this in a slightly more general statement :

Lemma (5.2) Let X, Y be subsets of a vector space over F_{3}. Assume |X| = 4, |Y | = 2 and |X +′ X| = 5. Then, |X + Y | ≥ 6.

Proof. We may assume that 0 ∈ 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 = {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, 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 ≠ 0, v ≠ e_{1}, e_{2} ≠ 0, or e_{1} ≠ 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, i.e., e_{1} + v ∈ {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 = {e_{1}, e_{2}, e_{1} + e_{2}, 2e_{1} + e_{2}, e_{1} + 2e_{2}}.

Now, we may also assume 0 ∈ 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} + λe_{2}, for some λ ∈ F_{3}. 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} + λe_{2}, −e_{1} + (λ + 1)e_{2}. □

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), i.e., |A_{0}| = 4, |A_{1}| = |A_{2}| = 3. We have

A +′ A ⊃ ((A_{0} +′ A_{0}) ∪ (A_{1} + A_{2})) ∐(A_{0} + A_{1}) ∐(A_{0} + A_{2})

and thus |A +′ A| ≥ 18 except perhaps if |(A_{0} +′ A_{0}) ∪ (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} ⊂ A_{0} +′ A_{0}.

Keeping the same notation as above, we assume V = F_{3} · e ⊕ H, where e ∈ A_{1}.

Set A_{2} = 2e + {x, y, z} with distinct x, y, z ∈ H. Since x, y, z ∈ A_{1} + A_{2}, e.g., x = e + (2e + x) ∈ A_{1} + A_{2}, we must have

x, y, z ∈ A_{0} +′ A_{0} = {e_{1}, e_{2}, e_{1} + e_{2}, e_{1} + 2e_{2}, 2e_{1} + e_{2}}.

Each of the \binom{5}{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} = {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}}.

The exceptional choice x = e_{1}, y = e_{1} + e_{2}, z = e_{1} + 2e_{2} on the other hand, yields

\{ \begin{matrix}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{matrix}

We must have A_{1} + A_{2} ⊂ 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 ≠ v, this would imply u + v = 0 and 2e ∈ A_{1} +′ A_{1}. However, A_{0} + A_{2} does not contain 2e.

Hence, if A ⊂ V, a vector space over F_{3}, has cardinality 10 and possesses a partition of type (4, 4, 2) or (4, 3, 3), then |A +′ A| ≥ 18.

We now finish up the case of flat partitions for h ≥ 3 by induction on h. Suppose H is a hyperplane such that A_{0} = A ∩ H has cardinality r = 1 + 3^{h−1} and r ≥ s ≥ t, where as before r, s, t are the cardinalities of the intersections of A with the various translates of H.

Claim. Suppose by induction on h ≥ 3 that |A_{0} +′ A_{0}| ≥ 2 · 3^{h−1}. Then, we have |A +′ A| ≥ 2 · 3^{h}.

Proof. Since we assume r = 1 + 3^{h−1} and |A| = 1 + 3^{h} there are only two possible partitions:

\begin{aligned}(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{aligned}

and we have

|A +′ A| ≥ |A_{0} +′ A_{0}| + β(r, s) + β(r, t).

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

Of course, in both cases s + t = 2 · 3^{h−1} since r + s + t = |A| = 1 + 3^{h}.

Therefore, the induction assumption on |A_{0} +′ A_{0}| yields

|A +′ A| ≥ 2 · 3^{h−1} + 4 · 3^{h−1} = 2 · 3^{h}.

This finishes the proof of the claim and of Theorem (5.1). □

Summarizing our knowledge of μ′_{3}(r, s), if r = 1+3+∑_{i≥2} r_{i}3^{i} and s = 1+3+∑_{i≥2} s_{i}3^{i} form a special pair (i.e., r_{i} + s_{i} ≤ 2 for all i ≥ 2), we have μ′_{3}(r, s) = r + s − 3.

If (r, s) is a special pair for p = 3 but r ≡ s ≡ 1 mod 9, then the only case for which we know μ′_{3}(r, s) is r = s = 1 + 3^{h}, namely μ′_{3}(r, s) = r + s − 2 as proved in this paper. In all other cases, r = 1+3^{h} +∑_{i≥h+1} r_{i}3^{i} and s = 1+3^{h} +∑_{i≥h+1} s_{i}3^{i} forming a special pair with h ≥ 2 and (r, s) ≠ (1 + 3^{h}, 1 + 3^{h}), it remains an open problem to decide whether μ′_{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 μ′_{3}(r, s) = γ_{3}(r, s) as given by formula (6) or (7).

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.

References

[ANR1] N. Alon, M. B. Nathanson and I. Z. Ruzsa, Adding Distinct Congruences Classes Modulo a Prime, American Math. Monthly 102 (1995), 250-255.

[ANR2] N. Alon, M. B. Nathanson and I. Z. Ruzsa, The polynomial method and restricted sums of congruences classes, Journal of Number Theory 56 (1996), 404-417.

[DH] J. A. Dias da Silva and Y. O. Hamidoune, Cyclic spaces for Grassmann derivatives and additive theory, Bull. London Math. Soc. 26 (1994), 140-146.

[EK1] S. Eliahou and M. Kervaire, Sumsets in vector spaces over a finite field, Journal of Number Theory 71 (1998), 12-39.

[EK2] S. Eliahou and M. Kervaire, Restricted sums of sets of cardinality 1 + p in a vector space over F_{p}, Preprint, Université du Littoral Côte d’Opale, Cahiers du LMPA Joseph Liouville No. 75 (1998). To appear in Discrete Mathematics.