ADDITIVE BASES IN ABELIAN GROUPS

VSEVOLOD F. LEV, MIKHAIL E. MUZYCHUK, AND ROM PINCHASI

Abstract. Let G be a finite, non-trivial abelian group of exponent m, and suppose that B_{1}, …, B_{k} are generating subsets of G. We prove that if k > 2m ln log_{2} |G|, then the multiset union B_{1} ∪ ⋯ ∪ B_{k} forms an additive basis of G; that is, for every g ∈ G there exist A_{1} ⊆ B_{1}, …, A_{k} ⊆ B_{k} such that g = ∑_{i=1}^{k} ∑_{a∈A_{i}} a. This generalizes a result of Alon, Linial, and Meshulam on the additive bases conjecture. As another step towards proving the conjecture, in the case where B_{1}, …, B_{k} are finite subsets of a vector space we obtain lower-bound estimates for the number of distinct values, attained by the sums of the form ∑_{i=1}^{k} ∑_{a∈A_{i}} a, where A_{i} vary over all subsets of B_{i} for each i = 1, …, k.

Finally, we establish a surprising relation between the additive bases conjecture and the problem of covering the vertices of a unit cube by translates of a lattice, and present a reformulation of (the strong form of) the conjecture in terms of coverings.

1. Introduction and statement of the results

Given an abelian group G and a multiset B = {b_{1}, …, b_{n}} ⊆ G, we say that B is an additive basis of G if for every group element g ∈ G there exists an index set I ⊆ [1, n] such that g = ∑_{i∈I} b_{i}.

Jaeger et al conjectured in [JLPT92] that for any prime p there is an integer k(p) > 0 with the property that if B_{1}, …, B_{k(p)} are (linear) bases of the finite-dimensional vector space V over the p-element field, then the multiset union B_{1} ∪ ⋯ ∪ B_{k(p)} is an additive basis of V. This statement is known as the additive basis conjecture. Alon et al proved in [ALM91], in two different ways, that there exists a function c(p) such that if |V | = p^{n}, k > c(p) ln n, and B_{1}, …, B_{k} are bases of V, then the multiset union B_{1} ∪ ⋯ ∪ B_{k} is an additive basis of V. One of their proofs, using the polynomial method and properties of the permanent, shows that B_{1} ∪ ⋯ ∪ B_{k} is an additive basis of V, provided that k ≥ (p − 1) ln n + p − 2; another proof, using exponential sums, requires k ≥ (p^{2}/2) ln 2pn+1. In this paper we introduce yet another approach allowing us to establish the following generalization.

Theorem 1. Let G be a finite, non-trivial abelian group of exponent m, and suppose that B_{1}, …, B_{k} are generating subsets of G. If k > 2m ln log_{2} |G|, then the multiset union B_{1} ∪ ⋯ ∪ B_{k} is an additive basis of G.

Our argument is based on the following interpretation of the problem. For a subset B of an abelian group G write

B^{∗} := { ∑_{a∈A} a: A ⊆ B, |A| < ∞}

(the subset sum set of B), and given subsets B_{1}, …, B_{k} ⊆ G let

B_{1} + ⋯ + B_{k} := {b_{1} + ⋯ + b_{k}: b_{1} ∈ B_{1}, …, b_{k} ∈ B_{k}}

(the sumset of B_{1}, …, B_{k}). Clearly, in order for the multiset union B_{1} ∪ ⋯ ∪ B_{k} to form an additive basis of G, it is necessary and sufficient that B_{1}^{∗} + ⋯ + B_{k}^{∗} = G. Accordingly, Theorem 1 can be equivalently restated as follows.

Theorem 1′. Let G be a finite, non-trivial abelian group of exponent m, and suppose that B_{1}, …, B_{k} are generating subsets of G. If k > 2m ln log_{2} |G|, then B_{1}^{∗}+⋯+B_{k}^{∗} = G.

We notice that if B_{1}, …, B_{k} are bases of a vector space, then the sumset B_{1}^{∗} + ⋯ + B_{k}^{∗} has a transparent geometric meaning: namely, it is the Minkowski sum of the vertex sets of the parallelepipeds, spanned by B_{1}, …, B_{k}. One may hope that studying sumsets of this form can eventually lead to a proof of the additive basis conjecture. We establish two results in this direction.

Theorem 2. Let k be a positive integer. If B_{1}, …, B_{k} are finite subsets of the vector space V over a field of zero characteristic, then

|B_{1}^{∗} + ⋯ + B_{k}^{∗}| ≥ 2^{rk(B_{1})} (3/2)^{rk(B_{2})} ⋯ ((k + 1)/k)^{rk(B_{k})}.

In particular, if dim V = n and B_{1}, …, B_{k} are bases of V, then

|B_{1}^{∗} + ⋯ + B_{k}^{∗}| ≥ (k + 1)^{n}.

Notice, that in the second estimate of the theorem equality is attained if B_{1} = ⋯ = B_{k}.

A slight generalization of the second assertion of Theorem 2 is that if B_{1}, …, B_{k} are finite subsets of a vector space over a field of zero characteristic, then

|B_{1}^{∗} + ⋯ + B_{k}^{∗}| ≥ (k + 1)^{(rk(B_{1})+···+rk(B_{k}))/k}.

We give a partial extension of this estimate onto the fields of non-zero characteristic, confining ourselves to the case k = 2. (See, however, a remark at the end of Section 2.)

Theorem 3. If B_{1} and B_{2} are finite subsets of a vector space V over a field of odd characteristic, then

|B_{1}^{∗} + B_{2}^{∗}| ≥ (\frac{8}{3})^{(rk(B_{1})+rk(B_{2}))/2} .

In particular, if dim V = n and B_{1}, B_{2} are bases of V, then

|B_{1}^{∗} + B_{2}^{∗}| ≥ (\frac{8}{3})^{n} .

It is difficult to expect that the constant 8/3 is best possible in this context. On the other hand, it cannot be replaced by a value larger than \sqrt{8}, at least for the underlying field of characteristic 3: for, if V is an even-dimension vector space over such a field, and if B_{1} = {e_{1}, …, e_{2l}} is a basis of V, then for the basis

B_{2} := {e_{1} + e_{2}, e_{1} − e_{2}, e_{3} + e_{4}, e_{3} − e_{4}, …, e_{2l−1} + e_{2l}, e_{2l−1} − e_{2l}}

we have |B_{1}^{∗} + B_{2}^{∗}| = 8^{l}.

Yet another, completely different approach is presented in Section 3, where the additive bases conjecture is interpreted in terms of coverings of the vertices of the unit cube by translates of an integer lattice. We postpone the discussion and exact statement of the result to avoid aggregating notation and terminology at this stage.

2. The proofs

Proof of Theorem 1′. For m = 2 the assertion is immediate, as in this case B^{∗} = G for any generating subset B ⊆ G. Assume for the rest of the proof that m ≥ 3, and for j ∈ [1, k] let S_{j} := B_{1}^{∗} + ⋯ + B_{j}^{∗}.

The key ingredient of our argument is the Ruzsa sum triangle inequality, which says that for any positive integer n and any finite subsets A_{0}, A_{1}, …, A_{n} of an abelian group one has

|A_{0}|^{n−1}|A_{1} + ⋯ + A_{n}| ≤ |A_{0} + A_{1}| ⋯ |A_{0} + A_{n}|;

see [R89]. Applying this inequality with n = m − 1, A_{0} = S_{j−1}, and A_{1} = ⋯ = A_{n} = B_{j}^{∗}, we obtain

|S_{j−1}|^{m−2}|(m − 1)B_{j}^{∗}| ≤ |S_{j−1} + B_{j}^{∗}|^{m−1}; j ∈ [2, k].

As (m − 1)B_{j}^{∗} = G and S_{j−1} + B_{j}^{∗} = S_{j}, we derive that

|S_{j}| ≥ |S_{j−1}|^{1− \frac{1}{m−1}} |G|^{\frac{1}{m−1}}

and consequently

\frac{|G|}{|S_{j}|} ≤ (\frac{|G|}{|S_{j−1}|})^{1− \frac{1}{m−1}}

for every j ∈ [2, k]. Iterating, we obtain

ln \frac{|G|}{|S_{j}|} ≤ (1 − \frac{1}{m − 1})^{j−1} ln \frac{|G|}{|S_{1}|} ≤ e^{− \frac{j−1}{m}} ln \frac{|G|}{|S_{1}|}; j ∈ [1, k].

Let r denote the rank of G. Since |G| ≤ m^{r} and |S_{1}| = |B_{1}^{∗}| ≥ 2^{r} (for if C is a minimal generating subset of B_{1}, then |B_{1}^{∗}| ≥ |C^{∗}| = 2^{|C|} ≥ 2^{r}), using some basic calculus it is not difficult to deduce that

ln \frac{|G|}{|S_{j}|} < e^{− \frac{j+1}{m}} ln |G|; j ∈ [1, k].

Thus, if j = ⌊m ln log_{2} |G|⌋ (so that k > 2j > 0), then

|B_{1}^{∗} + ⋯ + B_{j}^{∗}| = |S_{j}| > \frac{1}{2} |G|,

and similarly

|B_{j+1}^{∗} + ⋯ + B_{2j}^{∗}| > \frac{1}{2} |G|.

We now use the fact that if two sets S, T ⊆ G satisfy |S| + |T | > |G|, then for any element g ∈ G the sets S and g − T have non-empty intersection in view of

|S ∩ (g − T)| = |S| + |g − T | − |S ∪ (g − T)| ≥ |S| + |T | − |G| > 0;

hence g ∈ S +T and therefore S +T = G. Applying this to the sets S := B_{1}^{∗}+⋯+B_{j}^{∗} and T := B_{j+1}^{∗} + ⋯ + B_{2j}^{∗}, we get

B_{1}^{∗} + ⋯ + B_{2j}^{∗} = G,

which implies the result. □

Proof of Theorem 2. We use induction on k, and for any fixed value of k induction on

min{rk(B_{1}), …, rk(B_{k})}.

The case k = 1 follows from the observation that if r = rk(B_{1}) and b_{1}, …, b_{r} ∈ B_{1} are linearly independent, then all 2^{r} sums

∑_{i∈I} b_{i}; I ⊆ [1, r]

are pairwise distinct. The case where k ≥ 2 and min{rk(B_{1}), …, rk(B_{k})} = 0 follows easily by the induction hypothesis. Suppose, therefore, that k ≥ 2 and rk(B_{1}), …, rk(B_{k}) are all positive. Fix arbitrarily b ∈ B_{k} and write B_{0} := B_{k} \ {b}.

ADDITIVE BASES IN ABELIAN GROUPS 5

Choose a linear subspace L complementing Sp {b} to the whole vector space, and let π denote the projection onto L along b. We have then

B_{1}^{∗} + ⋯ + B_{k}^{∗} = (B_{1}^{∗} + ⋯ + B_{k−1}^{∗} + B_{0}^{∗}) ∪ (B_{1}^{∗} + ⋯ + B_{k−1}^{∗} + B_{0}^{∗} + b),

and since

|(B_{1}^{∗} + ⋯ + B_{k−1}^{∗} + B_{0}^{∗} + b) \ (B_{1}^{∗} + ⋯ + B_{k−1}^{∗} + B_{0}^{∗})| ≥ |π(B_{1}^{∗} + ⋯ + B_{k−1}^{∗} + B_{0}^{∗})| = |(π(B_{1}))^{∗} + ⋯ + (π(B_{k}))^{∗}|,

it follows by the induction hypothesis (and in view of rk(B_{0}) ≥ rk(B_{k}) − 1 and rk(π(B)) ≥ rk(B) − 1, for any vector set B) that

|B_{1}^{∗} + ⋯ + B_{k}^{∗}| = |B_{1}^{∗} + ⋯ + B_{k−1}^{∗} + B_{0}^{∗}|

+ |(B_{1}^{∗} + ⋯ + B_{k−1}^{∗} + B_{0}^{∗} + b) \ (B_{1}^{∗} + ⋯ + B_{k−1}^{∗} + B_{0}^{∗})|

≥ ∏_{j=1}^{k−1} (1 + \frac{1}{j})^{rk(B_{j})} · (1 + \frac{1}{k})^{rk(B_{k})−1} + ∏_{j=1}^{k} (1 + \frac{1}{j})^{rk(B_{j})−1}

= ∏_{j=1}^{k} (1 + \frac{1}{j})^{rk(B_{j})} ,

as desired. □

For a finite subset B of an abelian group, let

T (B) := {(b_{1}, b_{2}, b_{3}, b_{4}) ∈ B × B × B × B: b_{1} + b_{2} = b_{3} + b_{4}}.

The proof of Theorem 3 is based on

Proposition 1. For any finite, non-empty subsets A and B of an abelian group we have

|A + B| ≥ \frac{|A|^{2}|B|^{2}}{\sqrt{T (A)T (B)}}.

Proof. For a group element z write

ν_{A−A}(z) := |{(a_{1}, a_{2}) ∈ A × A: z = a_{1} − a_{2}}|,
ν_{B−B}(z) := |{(b_{1}, b_{2}) ∈ B × B: z = b_{1} − b_{2}}|,

and

ν_{A+B}(z) := |{(a, b) ∈ A × B: z = a + b}|.

By the Cauchy-Schwarz inequality, we have

\frac{|A|^{2}|B|^{2}}{|A + B|} = \frac{1}{|A + B|} (∑_{z} ν_{A+B}(z))^{2} ≤ ∑_{z} (ν_{A+B}(z))^{2}.

The sum in the right-hand side is the number of solutions of the equation x_{1} + y_{1} = x_{2} + y_{2} in the variables x_{1}, x_{2} ∈ A and y_{1}, y_{2} ∈ B. Rewriting this equation as x_{1} − x_{2} = y_{2} − y_{1} we see that the number of its solutions is equal to

∑_{z} ν_{A−A}(z)ν_{B−B}(z) ≤ (∑_{z} (ν_{A−A}(z))^{2})^{1/2} (∑_{z} (ν_{B−B}(z))^{2})^{1/2}
= \sqrt{T (A)T (B)},

and the result follows. □

Proof of Theorem 3. Removing dependent vectors from the sets B_{i}, we assume without loss of generality that rk(B_{i}) = |B_{i}| and |B_{i}^{∗}| = 2^{|B_{i}|} for i ∈ {1, 2}. We apply Proposition 1 to the sets B_{1}^{∗} and B_{2}^{∗}. The quantities T (B_{i}^{∗}) can be explicitly calculated as follows. For a group element z let

ν_{i}(z) := |{(b′, b′′) ∈ B_{i}^{∗} × B_{i}^{∗}: z = b′ − b′′}|; i ∈ {1, 2},

so that

T (B_{i}^{∗}) = ∑_{z∈B_{i}^{∗}−B_{i}^{∗}}(ν_{i}(z))^{2}.

Fix i ∈ {1, 2}, set n := |B_{i}|, and write B_{i} = {b_{1}, …, b_{n}}. The condition z ∈ B_{i}^{∗} − B_{i}^{∗} means that z = ε_{1}b_{1} +⋯+ε_{n}b_{n} with ε_{1}, …, ε_{n} ∈ {−1, 0, 1}, and it is easily seen that in this case

ν_{i}(z) = 2^{n−|ε_{1}|−···−|ε_{n}|}.

Consequently, we have

T (B_{i}^{∗}) = ∑_{ε_{1},...,ε_{n}=−1}^{1} 2^{2n−2|ε_{1}|−···−2|ε_{n}|}

= 2^{2n} ∏_{i=1}^{n} ∑_{ε_{i}=−1}^{1} 2^{−2|ε_{i}|}

= 6^{n}

and it follows that

|B_{1}^{∗} + B_{2}^{∗}| ≥ \frac{2^{2|B_{1}|+2|B_{2}|}}{\sqrt{6^{|B_{1}|+|B_{2}|}}} = (\frac{8}{3})^{(|B_{1}|+|B_{2}|)/2} = (\frac{8}{3})^{(rk(B_{1})+rk(B_{2}))/2} .

□

We remark that the approach used in the proof of Proposition 1 can be combined with character sum technique in the spirit of [ALM91], to show that for any system of bases B_{1}, …, B_{k} of an r-dimensional vector space over a field of characteristic p > 2 one has

|B_{1}^{∗} + ⋯ + B_{k}^{∗}| ≥ \frac{p^{r}}{(1 + σ_{p}(k))^{r}} ,

where

σ_{p}(k) = ∑_{u=1}^{p−1} (cos π \frac{u}{p})^{2k} .

(Hint for the interested reader: if ν(g) denotes the number of representations of the vector g in the form g = b_{1}+⋯+b_{k} with b_{i} ∈ B_{i}^{∗} for i ∈ [1, k], then the sum ∑_{g}(ν(g))^{2} counts the number of 2k-tuples (x_{1}, …, x_{k}, y_{1}, …, y_{k}) with x_{1}+⋯+x_{k} = y_{1}+⋯+y_{k} and x_{i}, y_{i} ∈ B_{i}^{∗} for i ∈ [1, k]. This number is easily expressed using character sums.) Since 1 + σ_{p}(2) = 3p/8 for any prime p > 2, the estimate above extends the result of Theorem 3.

3. Additive bases via lattice coverings

Suppose that k ≥ 2 and r ≥ 1 are fixed integers. Given a prime p, we say that a lattice in ℤ^{kr} is p-oblique if, whenever for some i_{0} ∈ [1, k] a lattice vector

(z_{11}, …, z_{1r}, …, z_{k1}, …, z_{kr})

satisfies

z_{ij} ≡ 0 (mod p) for all i ∈ [1, k] \ {i_{0}}, j ∈ [1, r],

it also satisfies

z_{i_{0}j} ≡ 0 (mod p) for all j ∈ [1, r].

(The term oblique is meant as an indication that the lattice is not aligned with the coordinate hyperplanes.) Furthermore, we define the covering number of a lattice Λ ≤ ℤ^{kr} to be the minimal number of translates of Λ, containing in their union all vertices of the unit cube [0, 1]^{kr}, and we denote this quantity by C(Λ); thus,

C(Λ) = min{|S|: S ⊆ ℤ^{kr}, {0, 1}^{kr} ⊆ S + Λ}.

We conclude this paper with the following, somewhat surprising, result.

8 VSEVOLOD F. LEV, MIKHAIL E. MUZYCHUK, AND ROM PINCHASI

Theorem 4. For any integer k ≥ 2 and r ≥ 1, prime p, and field 𝔽 of characteristic p, we have

min_{B_{1},...,B_{k}⊆𝔽^{r}} |B_{1}^{∗} + ⋯ + B_{k}^{∗}| ≥ min_{Λ≤ℤ^{kr}} C(Λ),

where the minimum in the left-hand side extends over all systems of k bases of 𝔽^{r}, and in the right-hand side over all p-oblique lattices in ℤ^{kr}. If k ≤ |𝔽| then, indeed, equality holds; moreover, in this case there is a p-oblique lattice pℤ^{kr} ≤ Λ ≤ ℤ^{kr} with det Λ = p^{r}, on which the minimum in the right-hand side is attained.

Remark. It is not clear to us to what extent the condition k ≤ |𝔽| is essential and whether the assertion of Theorem 4 fails in a critical way if this condition is dropped.

We notice that if k, r, and p are as in Theorem 4, then the lattice Λ of all integer vectors (z_{11}, …, z_{kr}) with

z_{1j} + ⋯ + z_{kj} ≡ 0 (mod p); j = 1, …, r

has covering number C(Λ) = min{(k + 1)^{r}, p^{r}}. To see this, observe that different translates of Λ correspond in a natural way to integer vectors of the form (z_{11}, …, z_{1r}, 0, …, 0) with z_{11}, …, z_{1r} ∈ [0, p − 1], and on the other hand, such a vector is congruent modulo Λ to a vector from {0, 1}^{kr} if and only if z_{11}, …, z_{1r} ≤ k.

By Theorem 4, the additive bases conjecture will follow if one can show that there are no p-oblique lattices with the covering number smaller than p^{r}; that is, to show that for any prime p there exists an integer k = k(p) > 0 such that the set {0, 1}^{kr} cannot be covered by fewer than p^{r} translates of a p-oblique lattice, for any integer r ≥ 1. By all we know, the conjecture may even be true with k(p) = p. Theorem 4 shows this strong form of the conjecture is equivalent to the assertion that one cannot cover the set {0, 1}^{pr} by fewer than p^{r} translates of a p-oblique lattice.

Proof of Theorem 4. Suppose that B = {B_{1}, …, B_{k}} is a system of bases of 𝔽^{r}. We write

B_{i} = {b_{i1}, …, b_{ir}}; i = 1, …, k

and define a linear mapping φ_{B}: ℤ^{kr} → 𝔽^{r} by

φ_{B}(x_{11}, …, x_{kr}) = x_{11}b_{11} + ⋯ + x_{1r}b_{1r} + ⋯ + x_{k1}b_{k1} + ⋯ + x_{kr}b_{kr},

so that the sumset B_{1}^{∗} + ⋯ + B_{k}^{∗} is the image of {0, 1}^{kr} under φ_{B}.

Let Λ_{B} := ker φ_{B}; thus, Λ_{B} is a sublattice of ℤ^{kr}, lying above pℤ^{kr}, and hence a full-rank sublattice. From the fact that for any integer x_{11}, …, x_{k−1,r} there are unique x_{k1}, …, x_{kr} ∈ [0, p) with (x_{11}, …, x_{kr}) ∈ Λ_{B}, it follows that det Λ_{B} = p^{r}. Furthermore, Λ_{B} is (evidently) p-oblique.

ADDITIVE BASES IN ABELIAN GROUPS 9

Since for u, v ∈ ℤ^{kr}, and in particular for u, v ∈ {0, 1}^{kr}, the equality φ_{B}(u) = φ_{B}(v) is equivalent to v ≡ u (mod Λ_{B}), we have

|B_{1}^{∗} + ⋯ + B_{k}^{∗}| = |φ_{B}({0, 1}^{kr})| = C(Λ_{B}).

This proves the first assertion of the theorem, and to complete the proof we assume that k ≤ |𝔽| and show that for every p-oblique lattice Λ ≤ ℤ^{kr} there exists a system B of k bases of 𝔽^{r} with Λ_{B} ≥ Λ and consequently, with C(Λ_{B}) ≤ C(Λ).

Replacing Λ with Λ + pℤ^{kr} we can assume that Λ is of full rank. Let ℤ^{kr} = V_{1} ⊕⋯⊕V_{k}, where V_{i} is the rank-r sublattice, spanned over ℤ by the “ith coordinate block” (for each i = 1, …, k), fix a basis {l^{(1)}, …, l^{(kr)}} of Λ, and for each t ∈ [1, kr] consider the decomposition

l^{(t)} = l_{1}^{(t)} + ⋯ + l_{k}^{(t)}; l_{i}^{(t)} ∈ V_{i} for i = 1, …, k.

What we want B to satisfy is that φ_{B}(l^{(t)}) = 0 for every t ∈ [1, kr]. Writing B = {B_{1}, …, B_{k}} and B_{i} = {b_{i1}, …, b_{ir}} for each i = 1, …, k, the condition to secure takes the shape

B_{1}l_{1}^{(t)} + ⋯ + B_{k}l_{k}^{(t)} = 0; t ∈ [1, kr],

where B_{i} is the r × r matrix over 𝔽, whose columns are formed by the vectors b_{i1}, …, b_{ir}. Thus, if for each i = 1, …, k by L_{i} we denote the r × kr matrix over ℤ, whose columns are formed by the vectors l_{i}^{(1)}, …, l_{i}^{(kr)}, then what we ultimately want to prove is the existence of B_{1}, …, B_{k} ∈ GL_{r}(𝔽) satisfying B_{1}L_{1} +⋯+B_{k}L_{k} = 0.

We notice that the matrices L_{i} actually have integer entries, but we treat them in the last equality, and will continue to treat for the rest of the proof, as matrices over the p-element field 𝔽_{p} ≤ 𝔽, and we also seek B_{i} with the entries in 𝔽_{p}. With this convention, the assumption that Λ is p-oblique (which has not been used yet) guarantees that for each i ∈ [1, k], the intersection

ker L_{1} ∩ ⋯ ∩ ker L_{i−1} ∩ ker L_{i+1} ∩ ⋯ ∩ ker L_{k}

is contained in ker L_{i}. The proof is concluded by using

Proposition 2. Suppose that r, n ≥ 1 and k ≥ 2 are integers and L_{1}, …, L_{k} are matrices of size r × n over a field 𝔽 with |𝔽| ≥ k. If for each i ∈ [1, k] we have

⋂_{j∈[1,k]: j≠i} ker L_{j} ⊆ ker L_{i},

then there exist matrices B_{1}, …, B_{k} ∈ GL_{r}(𝔽) satisfying

B_{1}L_{1} + ⋯ + B_{k}L_{k} = 0.

The proof of Proposition 2 is presented in the Appendix. □

10 VSEVOLOD F. LEV, MIKHAIL E. MUZYCHUK, AND ROM PINCHASI

Appendix: Proof of Proposition 2.

The assumptions ⋂_{j∈[1,k]: j≠i} ker L_{j} ⊆ ker L_{i} shows that if a vector in 𝔽^{n} is orthogonal to every row of every matrix L_{j} with j ∈ [1, k] \ {i}, then it is also orthogonal to every row of the matrix L_{i}; in other words, every row of L_{i} is a linear combination of the rows of L_{j} for j ∈ [1, k] \ {i}. Thus, there exist matrices A_{ij} of size r × r over the field 𝔽, for each pair of indices i, j ∈ [1, k] with i ≠ j, such that

L_{i} = ∑_{j∈[1,k]: j≠i} A_{ij}L_{j}; i ∈ [1, k].

For i ∈ [1, k] we define A_{ii} := −I_{r}, where I_{r} is the identity matrix of size r × r, to get

A_{i1}L_{1} + ⋯ + A_{ik}L_{k} = 0; i ∈ [1, k].

(The reader may find it useful to consider the matrices A_{ij} being organized themselves into a k × k matrix, and the matrices L_{1}, …, L_{k} written as a “column vector”.)

If we can find matrices M_{1}, …, M_{k} of size r × r so that none of the linear combinations

B_{j} := M_{1}A_{1j} + ⋯ + M_{k}A_{kj}; j ∈ [1, k]

is degenerate, then we are done in view of

∑_{j=1}^{k} B_{j}L_{j} = ∑_{i=1}^{k} M_{i} ∑_{j=1}^{k} A_{ij}L_{j} = 0.

We complete the proof of the proposition establishing the existence of such matrices M_{1}, …, M_{k}.

Lemma 1. Suppose that r, k ≥ 1 are integers and that A_{ij} (i, j ∈ [1, k]) are matrices of size r × r over a field 𝔽 such that A_{ii} is non-degenerate for each i ∈ [1, k]. If |𝔽| ≥ k, then there exist matrices M_{1}, …, M_{k} over 𝔽 of size r × r so that none of

M_{1}A_{1j} + ⋯ + M_{k}A_{kj}; j ∈ [1, k]

is degenerate.

Proof. We use induction on k. The case k = 1 trivial; suppose that k ≥ 2.

If A_{k1}, …, A_{k k−1} are all non-degenerate, then we can take M_{1} = ⋯ = M_{k−1} = 0 and M_{k} = I_{r}. Assume therefore that one of the matrices A_{ki} with i ∈ [1, k − 1], say A_{k1}, is degenerate. Applying the induction hypothesis, find M_{1}, …, M_{k−1} so that

B_{j} := M_{1}A_{1j} + ⋯ + M_{k−1}A_{k−1 j}; j ∈ [1, k − 1]

ADDITIVE BASES IN ABELIAN GROUPS 11

are non-degenerate, and let

B_{k} := M_{1}A_{1k} + ⋯ + M_{k−1}A_{k−1 k}.

Recalling that A_{k1}, and thus also A_{k1}B_{1}^{−1}, are degenerate, we find U, V ∈ GL_{r}(𝔽) so that the matrix VA_{k1}B_{1}^{−1}U is upper-triangular with zeroes on the main diagonal, and we seek M_{k} in the form M_{k} = UDV with a diagonal matrix D. Thus, D is to be found so that none of B_{j} + UDVA_{kj} for j ∈ [1, k] are degenerate. Since

B_{1} + UDVA_{k1} = U(I_{r} + D · VA_{k1}B_{1}^{−1}U)U^{−1}B_{1},

this matrix is non-degenerate. Therefore, it remains to show that there is a diagonal matrix D such that

B_{2} + UDVA_{k2}, …, B_{k} + UDVA_{kk}

are non-degenerate.

To this end we consider the polynomial in r variables over the field 𝔽, defined by

P (t_{1}, …, t_{r}) := ∏_{j=2}^{k} det(B_{j} + UDVA_{kj}); D = diag(t_{1}, …, t_{r}).

This is a non-zero polynomial, as each factor is distinct from 0: indeed, the coefficient of t_{1} ⋯ t_{r} in the last factor is det(UVA_{kk}) ≠ 0, and for each j ∈ [2, k − 1] the constant term of the j th factor is det(B_{j}) ≠ 0. Furthermore, each factor is linear in every variable t_{i}; hence the degree of P in every variable is k −1. It is well-known, however, that a non-zero polynomial in r variables cannot vanish on a cartesian product of r sets, provided that the cardinality of each set exceeds the degree of the polynomial in the corresponding variable; see, for instance, [AT92, Lemma 2.1]. This implies the existence of t_{1}, …, t_{r} ∈ 𝔽 with P (t_{1}, …, t_{r}) ≠ 0, and hence the existence of D with the required property. □

References

[ALM91] N. Alon, N. Linial, and R. Meshulam, Additive Bases of Vector Spaces over Prime Fields, J. Comb. Theory, Ser. A 57 (1991), 203–210.

[AT92] N. Alon and M. Tarsi, Colorings and orientations of graphs, Combinatorica 12 (1992), 125–134.

[JLPT92] F. Jaeger, N. Linial, C. Payan, and M. Tarsi, Group connectivity of graphs — a nonhomogeneous analogue of nowhere-zero flow properties, J. Comb. Theory, Ser. B 56 (2) (1992), 165–182.

[R89] I.Z. Ruzsa, An application of graph theory to additive number theory, Sci. Ser. A Math. Sci. (N.S.) 3 (1989), 97–109.

12 VSEVOLOD F. LEV, MIKHAIL E. MUZYCHUK, AND ROM PINCHASI

E-mail address: seva@math.haifa.ac.il

Department of Mathematics, The University of Haifa at Oranim, Tivon 36006, Israel

E-mail address: muzy@netanya.ac.il

Department of Computer Science and Mathematics, Netanya Academic College, Netanya 42365, Israel

E-mail address: room@math.technion.ac.il

Department of Mathematics, Technion — Israel Institute of Technology, Haifa 32000, Israel