THE RECTIFIABILITY THRESHOLD IN ABELIAN GROUPS

VSEVOLOD F. LEV

Abstract. For any abelian group G and integer t ≥ 2 we determine precisely the smallest possible size of a non-t-rectifiable subset of G. Specifically, assuming that G is not torsion-free, denote by p the smallest order of a non-zero element of G. We show that if a subset S ⊆ G satisfies |S| ≤ ⌈log_{t} p⌉, then S is t-isomorphic (in the sense of Freiman) to a set of integers; on the other hand, we present an example of a subset S ⊆ G with |S| = ⌈log_{t} p⌉+1 which is not t-isomorphic to a set of integers.

1. The smallest size of a non-rectifiable subset

The basic notion of modern additive combinatorics is that of Freiman (or local) isomorphism. Informally speaking, two sets are t-isomorphic if they behave identically under t-fold addition. Formally, for a positive integer t, a mapping φ: A → S from a subset A of a semigroup to the (potentially different) semigroup S is called a tisomorphism if the equalities

a′_{1} ⋯ a′_{t} = a′′_{1} ⋯ a′′_{t}

and

φ(a′_{1}) ⋯ φ(a′_{t}) = φ(a′′_{1}) ⋯ φ(a′′_{t})

are equivalent for all a′_{1}, …, a′′_{t} ∈ A; that is, one of them holds if and only if another one holds. We refer the reader to [KL00] or [N96] for discussion and examples.

Suppose that φ: A → S is a t-isomorphism and that the semigroup, in which A resides, is left-cancellative. We notice that if φ(a_{1}) = φ(a_{2}) holds for some a_{1}, a_{2} ∈ A, then we have (φ(a_{1}))^{t} = (φ(a_{1}))^{t−1}φ(a_{2}), implying a_{1}^{t} = a_{1}^{t−1}a_{2} and hence a_{1} = a_{2}. This shows that any t-isomorphism is an injection. On the other hand, any injection is a 1-isomorphism; for this reason the case where t = 1 is of no interest and we mostly assume below that t ≥ 2. Also, we will be concerned with the case where the semigroups in question are actually abelian groups, and we use additive notation for the group operation.

It is well-known (see, for instance, [N96, Corollary 8.2]) that if G is a torsion-free abelian group and t is a positive integer, then any finite subset of G is t-isomorphic to a set of integers. Generally, we say that a set S of group elements is t-rectifiable if it is t-isomorphic to a set of integers. The importance of this notion is explained by the fact that integer sets are often easier to deal with than sets in other abelian groups due to the presence of the order relation.

2000 Mathematics Subject Classification. Primary: 11P70; secondary: 11B75.

In [BLR98] it is shown that any subset S of the cyclic group of prime order p with |S| ≤ log_{2t} p is t-rectifiable, and an example of a subset with |S| ≤ 2 log_{t} p + 1, which is not t-rectifiable, is presented. As a refinement and extension of this result, in the present note for any abelian group G with the non-trivial torsion subgroup we determine precisely the smallest size of a non-t-rectifiable subset of G.

Theorem 1. Let G be an abelian group with the non-trivial torsion subgroup, and let t ≥ 2 be an integer. Denote by p the smallest order of a non-zero element of G. Then any subset S ⊆ G with |S| ≤ ⌈log_{t} p⌉ is t-rectifiable, while there exists a non-t-rectifiable subset S ⊆ G with |S| = ⌈log_{t} p⌉ + 1.

The rest of this section is devoted to the proof of Theorem 1. In the next section we apply Theorem 1 to sharpen a result of Browkin, Diviš, and Schinzel.

We start with the construction of a small non-t-rectifiable set. Fix an element g ∈ G of order p, set k := ⌈log_{t} p⌉, so that k ≥ 1 and t^{k−1} < p ≤ t^{k}, and define

S := \{0, ⌈\frac{p}{t^{k}} ⌉ g, ⌈\frac{p}{t^{k−1}} ⌉ g, …, ⌈\frac{p}{t}⌉ g\} .

Since t ⌈p/t^{i+1}⌉ − ⌈p/t^{i}⌉ ∈ [0, t − 1] for each i ∈ [0, k − 1], and since both 0 and g = ⌈p/t^{k}⌉ g are elements of S, every non-zero element s ∈ S has the property that ts is a sum of exactly t elements of S, at least one of which is distinct from s. On the other hand, any finite set of integers (and hence any set, t-isomorphic to a finite set of integers) contains at least two elements which do not have this property — namely, the smallest and the largest elements of the set. It follows that S is not t-isomorphic to a set of integers, and it remains to notice that |S| = k + 1 = ⌈log_{t} p⌉ + 1.

To proceed we need some tools from linear algebra.

Lemma 1. Let m be a positive integer and suppose that V, V_{1}, …, V_{m} are linear subspaces of a vector space over the field 𝔽. If V ⊆ ∪_{1≤i≤m}V_{i} and either 𝔽 is infinite, or |𝔽| ≥ m, then in fact V ⊆ V_{i} for some i ∈ [1, m].

Proof. We assume, without loss of generality, that V_{1}, …, V_{m} is a minimal (by inclusion) system of subspaces, covering V, and show that then m = 1 holds, making the assertion trivial. Suppose, for a contradiction, that m ≥ 2. We have then V ∩ V_{1} ⊈ V_{2} ∪ V_{3} ∪ ⋯ ∪ V_{m} (otherwise V ⊆ ∪_{2≤i≤m}V_{i} would hold) and similarly, V ∩ V_{2} ⊈ V_{1} ∪ V_{3} ∪ ⋯ ∪ V_{m}. Fix two vectors v_{1} ∈ (V ∩ V_{1}) \ (V_{2} ∪ V_{3} ∪ ⋯ ∪ V_{m}) and v_{2} ∈ (V ∩ V_{2}) \ (V_{1} ∪ V_{3} ∪ ⋯ ∪ V_{m}), and for λ ∈ 𝔽 set v(λ) := v_{1} + λv_{2}. Evidently, we have v(λ) ∈ V, and if λ ≠ 0, then v(λ) ∉ V_{1} ∪ V_{2}. Furthermore, for any j ∈ [3, m] there is at most one value of λ such that v(λ) ∈ V_{j}: for if both v(λ′) ∈ V_{j} and v(λ′′) ∈ V_{j} with λ′, λ′′ ∈ 𝔽 hold, then (λ′′ − λ′)v_{2} ∈ V_{j}, whence λ′′ = λ′ in view of v_{2} ∉ V_{j}. Since the number of non-zero choices for λ is at least m − 1, we can select λ ≠ 0 so that v(λ) ∉ ∪_{3≤i≤m}V_{i}. Along with v(λ) ∉ V_{1} ∪ V_{2} and v(λ) ∈ V, this produces a contradiction. □

The following determinant estimate is due to Schinzel.

Lemma 2 ([Sc77]). Let m be a positive integer, and let A = (a_{ij})_{1≤i,j≤m} be a real matrix. For i ∈ [1, m] set

R_{i}^{+}(A) := ∑_{j∈[1,m]: a_{ij}>0} a_{ij} and R_{i}^{−}(A) := ∑_{j∈[1,m]: a_{ij}<0} |a_{ij}|.

Then

| det A| ≤ ∏_{i=1}^{m} max{R_{i}^{+}(A), R_{i}^{−}(A)}.

In [JN80] the following strengthening of Lemma 2 is established (and shown to be best possible in the sense that there is no better estimate of | det A| in terms of the quantities R_{i}^{+}(A) and R_{i}^{−}(A)).

Lemma 2′ ([JN80]). If m, A, R_{i}^{+}(A), R_{i}^{−}(A) (i ∈ [1, m]) are as in Lemma 2, then

| det A| ≤ ∏_{i=1}^{m} max{R_{i}^{+}(A), R_{i}^{−}(A)} − ∏_{i=1}^{m} min{R_{i}^{+}(A), R_{i}^{−}(A)}.

We include here a proof of Lemma 2′ which is completely distinct from, and much shorter than the proofs, presented in [Sc77] and [JN80].

Proof of Lemma 2′. For i ∈ [1, m] set M_{i}(A) := max{R_{i}^{+}(A), R_{i}^{−}(A)} and μ_{i}(A) := min{R_{i}^{+}(A), R_{i}^{−}(A)}. By continuity and homogeneity, we can assume that A has integer entries.

Consider integer vectors of the following two special types:

(a) vectors with exactly two non-zero coordinates, one of which is equal to 1 and another to −1;

(b) vectors with exactly one non-zero coordinate, equal either to 1 or to −1. It is easy to see that any row vector (a_{ij})_{1≤j≤m} can be represented as a sum of μ_{i} vectors of type (a), and M_{i} − μ_{i} vectors of type (b). (Say, (2, −4, 7) = 2(1, −1, 0) + 2(0, −1, 1) + 5(0, 0, 1).) Accordingly, det A can be represented as a sum of determinants of M_{1} ⋯ M_{m} matrices, all rows of which are either of type (a), or of type (b); moreover, μ_{1} ⋯ μ_{m} of these matrices have all rows of type (a). To complete the proof we observe that if all rows of a matrix are of type (a), then it is degenerate (for all its rows are in a proper subspace), and if all rows are either of type (a), or of type (b), then the determinant of the matrix is at most 1 in absolute value, as it follows by induction on the size of the matrix: if there is a row of type (b), we expand the determinant using this row, while otherwise the determinant is 0. □

For the remainder of this section we adopt the following notation. By ℚ we denote the field of rational numbers. Let m ≥ 1 be an integer. The cartesian product of m copies of G is denoted by G^{m} and considered as an m-dimensional module over the ring ℤ of integers. The standard inner product of two vectors x, y ∈ ℚ^{m} is denoted by ⟨x, y⟩, the span (over ℚ) of a subset K ⊆ ℚ^{m} is denoted by Sp K, and the orthogonal complement (with respect to the standard inner product) of a linear subspace V ⊆ ℚ^{m} is denoted by V^{⊥}. The notation ⟨x, y⟩ is used also in the case where x ∈ ℤ^{m} and y ∈ G^{m} for the “standard bilinear form” ℤ^{m} × G^{m} → G.

Back to the proof of (the first assertion of) Theorem 1, we notice first that the case where t ≥ p is immediate. Suppose now that t < p and that S ⊆ G is not t-rectifiable; we write then n := |S| and show that n ≥ log_{t} p + 1. Ordering in an arbitrary way the elements of S, we arrange them as an element σ ∈ G^{n}.

Denote by C the set of all those integer vectors c = (c_{1}, …, c_{n}) ∈ ℤ^{n} such that

∑_{j∈[1,n]: c_{j}>0} c_{j} = ∑_{j∈[1,n]: c_{j}<0} |c_{j}| = t.

(The elements of C correspond to possible “t-isomorphism equalities”, or constrains.) Let, furthermore, C_{σ} denote the set of all those c ∈ C such that ⟨c, σ⟩ = 0 (corresponding to the set of constrains that σ satisfies), and let I_{σ} be a maximal subset of C_{σ}, linearly independent over ℚ. Finally, set L_{σ} := (Sp I_{σ})^{⊥}.

We observe that for any integer vector l ∈ L_{σ} there is some c ∈ C \ C_{σ} such that ⟨c, l⟩ = 0: for otherwise l would satisfy exactly the same set of t-isomorphism equalities, as σ, and the coordinates of l would be pairwise distinct (if, for instance, the first two coordinates of l are equal, then c := (t, −t, 0, …, 0) ∈ C \ C_{σ} satisfies ⟨c, l⟩ = 0), hence the set of the coordinates of l would be isomorphic to S. This means that

L_{σ} ⊆ ⋃_{c∈C\C_{σ}}(Sp{c})^{⊥},

and by Lemma 1 there exists c ∈ C \ C_{σ} such that L_{σ} ⊆ (Sp{c})^{⊥}; equivalently, (Sp I_{σ})^{⊥} ⊆ (Sp{c})^{⊥}, and hence c ∈ Sp I_{σ}. It follows that there is a mapping κ: I_{σ} → ℤ and a non-zero integer u ∈ ℤ such that

∑_{i∈I_{σ}} κ(i) · i = uc;  (∗)

moreover, gcd{u, κ(i): i ∈ I_{σ}} = 1 can (and will) be assumed without loss of generality.

By the definition of C_{σ} and since I_{σ} ⊆ C_{σ}, we have ⟨i, σ⟩ = 0 for each i ∈ I_{σ}, and therefore u ⟨c, σ⟩ = 0 holds in view of (∗). However, from c ∉ C_{σ} we get ⟨c, σ⟩ ≠ 0 whence u is divisible by the order of a non-zero element of G, and therefore by a prime q ≥ p. Now (∗) shows that the elements of I_{σ} are linearly dependent over the finite field with q elements.

Let A denote the integer matrix with n columns and with |I_{σ}| rows, formed by the elements of I_{σ}. As it follows from the above, there is a non-zero minor of A, divisible by q. Since (1, …, 1) is orthogonal to every vector of I_{σ}, we have |I_{σ}| ≤ n − 1, and by Lemma 2 any minor of A does not exceed t^{n−1} in absolute value. Consequently, we have t^{n−1} ≥ q ≥ p, and therefore n ≥ log_{t} p + 1, as wanted.

2. An application: elements with few representations as a sum or difference

We notice that the linear-algebraic approach we employed to prove Theorem 1 bears some similarity with the method of [KL00] and also that of [BDS76], and that the assertion of Theorem 1 allows one to sharpen some of the results of the latter of these two papers. Specifically, it is shown in [BDS76] that for any field 𝔽 of positive characteristic p and finite non-empty subsets A, B ⊆ 𝔽, writing for brevity m := |A| and n := |B| we have

(i) if p > 2^{m−1}, then there is an element of 𝔽 with a unique representation as a sum of two elements of A, and also one with a unique representation as a difference of two elements of A;

(ii) if p > min{2^{m+n−2}, m^{n−1}, n^{m−1}}, then there is an element of 𝔽 with a unique

representation as a sum of an element of A and an element of B. On the other hand, Theorem 1 readily implies the following. Let G be any abelian group with the non-trivial torsion subgroup, and denote by p the smallest integer such that G has a non-zero element of order p. Let, furthermore, A and B be finite subsets of G. Writing m := |A| and n := |B|, under the assumption that m, n ≥ 2 we have

(I) if p > (u+v)^{m−1}, where u and v are non-negative integers such that u+v > 0, then there are at least two elements of G with a unique representation as a′_{1} + ⋯ + a′_{u} − a′′_{1} − ⋯ − a′′_{v} with a′_{1}, …, a′_{u}, a′′_{1}, …, a′′_{v} ∈ A;

(II) if p > 2^{m+n−3}, then there are at least two elements of G with a unique repre-

sentation as a sum of an element of A and an element of B. To prove (I), write t := u + v, fix a t-isomorphism φ of A onto a set of integers and

choose a_{1}, a_{2} ∈ A so that φ(a_{1}) is the smallest, and φ(a_{2}) is the largest element of φ(A) (the image of A under φ). Then the integers uφ(a_{1})−vφ(a_{2}) and uφ(a_{2})−vφ(a_{1}) have a unique representation in the form φ(a′_{1})+⋯+φ(a′_{u})−φ(a′′_{1})−⋯−φ(a′′_{v}) with a′_{1}, …, a′_{u}, a′′_{1}, …, a′′_{v} ∈ A, hence ua_{1} −va_{2} and ua_{2} −va_{1} have a unique representation in the requested form.

To establish (II), fix arbitrarily an element c ∈ G with at least two representations as c = a + b with a ∈ A and b ∈ B (if no such element exists, then we are done), and let C := A ∪ (c − B). Since |C| = |A| + |B| − |A ∩ (c − B)| ≤ m + n − 2, there is a 2-isomorphism φ of C onto a set of integers. Choose a_{1}, a_{2} ∈ A and b_{1}, b_{2} ∈ B so that

φ(a_{1}) ≤ φ(a) ≤ φ(a_{2})

for each a ∈ A, and

φ(c − b_{1}) ≤ φ(c − b) ≤ φ(c − b_{2})

for each b ∈ B. We claim that then a_{1} + b_{2} and a_{2} + b_{1} are uniquely representable as a sum of an element from A and an element from B. For if, say, a_{1} + b_{2} = a + b with a ∈ A and b ∈ B, then we have a_{1} + (c − b) = a + (c − b_{2}) whence φ(a_{1}) − φ(c − b_{2}) = φ(a) − φ(c − b), implying a = a_{1} and c − b_{2} = c − b and therefore b = b_{2}, as claimed.

References

[BLR98] Y.F. Bilu, V.F. Lev, and I.Z. Ruzsa, Rectification principles in additive number theory, Discrete Comput. Geom. (Special Issue) 19 (3) (1998), 343–353.

[BDS76] J. Browkin, B. Diviš, and A. Schinzel, Addition of sequences in general fields, Monatsh. Math. 82 (4) (1976), 261–268.

[JN80] C.R. Johnson and M. Newman, A surprising determinant inequality for real matrices, Math. Ann. 247 (1980), 179–186.

[KL00] S.V. Konyagin and V.F. Lev, Combinatorics and linear algebra of Freiman’s isomorphism, Mathematika 47 (1–2) (2000), 39–51.

[N96] M. Nathanson, Additive number theory. Inverse problems and the geometry of sumsets, Graduate Texts in Mathematics 165 (1996). Springer-Verlag, New York.

[Sc77] A. Schinzel, An inequality for determinants with real entries, Colloq. Math. 38 (2) (1977/78), 319–321.

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

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