COMBINATORICS AND LINEAR ALGEBRA OF FREIMAN’S ISOMORPHISM

SERGEI V. KONYAGIN AND VSEVOLOD F. LEV

Abstract. We develop an original linear algebraic approach to the basic notion of Freiman’s isomorphism and use it in conjunction with a combinatorial argument to answer two questions, posed by Freiman about 35 years ago.

First, we establish the order of grows of t(n), the number of classes of isomorphic n-element sets of integers: t(n) = n^{(2+o(1))n}. Second, we prove that linear Roth sets (sets of integers free of arithmetic progressions and having Freiman’s rank 1) exist and moreover, the number t′_{1}(n) of classes of such sets of cardinality n is amazingly large; in fact, it is “the same as above”: t′_{1}(n) = n^{(2+o(1))n}.

1. Introduction and summary of results

Freiman’s structure theory of set addition dates back to the early 60’s and constitutes now one of the most general and powerful tools in additive combinatorial number theory, especially when finite sets are regarded. The basic concept of this theory is what is now called by most authors “Freiman’s isomorphism.”

We start with simple introductory examples. The set {0, 1, 5} ⊆ 𝔽_{19} of residues modulo 19 behaves under addition like the set of integers {0, 1, 5} ⊆ ℤ: all the sums a_{i} + a_{j} in these two sets are pairwise distinct, and there are no non-trivial equalities of the form

(1)  a_{i} + a_{j} = a_{u} + a_{v}

between elements of either of these sets. (By trivial we mean those equalities where either i = u, j = v or i = v, j = u.) They also both behave like the set {−5, 7, 10} ⊆ ℤ or the set {(0, 1), (0, 0), (1, 0)} ⊆ ℤ^{2}. The set {6, 2, 9} ⊆ 𝔽_{11}, however, behaves differently, as in this case the non-trivial equality

a_{1} + a_{3} = 2a_{2}

holds. In this sense, this last set is identical to any of the arithmetic progressions^{1} {−9, 5, 19} ⊆ ℤ or {(−2, 3), (2, 5), (6, 7)} ⊆ ℤ^{2}.

The first author was supported by grants 96-01-00378 from the Russian Foundation for Basic Research and 96-15-96072 from the Programme of Development of Scientific Schools.

1For the reader seeking perfection: an arithmetic progression in an (additively written) abelian group A is a set A ⊆ A of the form A = {a, a + d, …, a + (|A| − 1)d}, where a and d are fixed elements of A.

We consider equalities (1) as identities, some of which are and some are not satisfied for a given set A = {a_{1}, …, a_{n}}.

Definition 1. Let A and B be two additively written abelian groups, and let A = {a_{1}, …, a_{n}} ⊆ A and B = {b_{1}, …, b_{n}} ⊆ B be subsets of the sets of all elements of these two groups. We say that A is isomorphic to B if they “behave similarly under two-fold addition”: specifically, for any quadruple of indices i, j, u, v ∈ [1, n],

a_{i} + a_{j} = a_{u} + a_{v}

if and only if

b_{i} + b_{j} = b_{u} + b_{v}.

Remark 1. The aforementioned perfectionist will say that the notion just defined is that of isomorphic sequences, and will proceed then to define two sets to be isomorphic if their elements can be arranged to produce two isomorphic sequences. Though this is correct, we prefer simplicity and clarity of exposition to formal rigorousness. At the same time, we reserve the right to speak about isomorphic sequences, whenever the “naïve” set approach can lead to a confusion.

As long as only two-fold sums 2A = A + A are considered, isomorphic sets are indistinguishable. Similarly, in algebra we consider as indistinguishable isomorphic objects, defining particular kinds of isomorphism to reflect algebraic operations we are interested in for a particular algebraic structure. Not surprisingly, the role of Freiman’s isomorphism in structure theory is as important as that of regular isomorphisms in algebra. Its shadow is present in the background of most of the results in this area, even those that do not appeal to it explicitly.

Clearly, if A = {a, a+d, …, a+(n−1)d} ⊆ A and ord (d) ≥ 2n−1, then A is isomorphic to {0, 1, …, n−1} ⊆ ℤ; thus, in torsion-free groups all arithmetic progressions of the same length are isomorphic to each other. Moreover, arithmetic progressions are preserved by Freiman’s isomorphism: if we consider an isomorphic mapping of a set A ⊆ ℤ to ℤ^{m}, then the image of any arithmetic progression contained in A is itself a progression and therefore lies on a straight line.

It is easy to see that any two-element set of integers A is isomorphic to {0, 1} as no non-trivial identities of type (1) can hold. Therefore we have only one class of isomorphic two-element sets of integers.

Next, any three-element set of integers is either an arithmetic progression in which case it is isomorphic to {0, 1, 2} (with a_{1} + a_{3} = 2a_{2} as the only non-trivial identity), or consists of three elements not in arithmetic progression in which case it is isomorphic to the plane set {(0, 0), (0, 1), (1, 0)} (no non-trivial identities).

COMBINATORICS AND LINEAR ALGEBRA 3

Definition 2. The rank r(A) of a finite set A ⊆ ℤ^{m} is the maximum positive integer r such that A can be mapped isomorphically onto a subset of ℤ^{r}, not situated on an affine hyperplane.

(Affine hyperplanes of an r-dimensional linear space L are linear manifolds of dimension r − 1, that is shifts of (r − 1)-dimensional subspaces by vectors of L.)

Clearly, for any n-element set A we have 1 ≤ r(A) ≤ n − 1. Sets of the maximum possible rank r = n − 1 are, evidently, those sets for which no non-trivial identity of the form (1) is satisfied; they are known as Sidon sets and as such were intensively studied in numerous papers. Sets of the minimum possible rank r = 1 are called linear and so far have not received much attention. By the definition, they are sets which can not be mapped isomorphically to ℤ^{r} with r > 1, except for degenerate mappings. As we saw above, the image of an arithmetic progression is always on a straight line, hence arithmetic progressions are linear. Those sets which contain “many” arithmetic progressions are linear also. For instance, if {b_{1}, b_{2}, b_{3}, b_{4}} ∈ ℤ^{m} is an isomorphic image of A = {0, 1, 2, 4} ∈ ℤ, then b_{1}, b_{2} and b_{3} are on the same straight line (as 0, 1 and 2 are in an arithmetic progression), and similarly, b_{1}, b_{3} and b_{4} are on the same straight line; hence all b_{i} are on the same line and thus A is linear. This shows that arithmetic progressions contained in a set play the role of a “glue” preventing this set from crumbling and keeping its rank low. In particular, any linear set A ⊆ ℤ of small cardinality seems to contain a progression, and in fact, several of them. This motivated Freiman to ask in 1966 (see [1]) the following question: is it true that any linear set necessarily contains a 3-term arithmetic progression? Since sets without 3-term arithmetic progressions are also known as Roth sets, Freiman’s question can be formulated in this form: does there exist a linear Roth set?

We return to the classification of integer sets. As we have mentioned, there are only two classes of three-element sets, one linear and one planar (of rank two).

A routine, though instructive examination shows that there are 5 classes of isomorphic four-element sets of integers: two of them linear (with representatives {0, 1, 2, 3} and {0, 1, 2, 4}, say), two planar (with representatives {(0, 0), (1, 0), (2, 0), (0, 1)} and {(0, 0), (1, 0), (0, 1), (1, 1)}) and one of rank 3 (with representative {(0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0)}).

Similarly, there are 22 classes of isomorphic five-element sets in ℤ: 11 linear, 8 planar, two of rank 3 and one of rank 4 — see [1] for details, including the list of representatives.

Though six-element integer sets have also been classified (there are 281 classes, see [2]), neither the exact value nor even the order of magnitude of the number t(n) of classes of isomorphic n-element sets of integers is known for n ≥ 7. The problem of finding this order of magnitude was also raised by Freiman in 1966.

4 SERGEI V. KONYAGIN AND VSEVOLOD F. LEV

In fact, it is not difficult to establish the finiteness and give an upper bound estimate of t(n). Let A be an n-element integer set. Any identity (1) that A satisfies can be rewritten so that for the indices i, j, u, v we have i > u ≥ v > j, and the number of quadruples i, j, u, v ∈ [1, n] under this condition is

\binom{n}{4} + \binom{n}{3} = \binom{n + 1}{4}.

Since A is determined up to isomorphism by its set of identities, we obtain

t(n) ≤ 2^{\binom{n+1}{4}}.

Unfortunately, this nice and simple estimate is far from being sharp. For instance, it gives

t(3) ≤ 2, t(4) ≤ 32, t(5) ≤ 2^{15} = 32768, t(6) ≤ 2^{35} = 34359738368,

while the real values, as indicated above, are

t(1) = t(2) = 1, t(3) = 2, t(4) = 5, t(5) = 22, t(6) = 281.

One of the two main results of the present paper is the following theorem, proved in Section 3.

Theorem 1. The number of classes of n-element integer sets is

t(n) = n^{(2+o(1))n} (n → ∞).

The second of our two results deals with linear Roth sets and is proven in Section 4. Not only do we establish the mere existence of such sets, but also show that there are a lot of them.

Theorem 2. The number of classes of linear n-element integer sets free of arithmetic progressions is

t′_{1}(n) = n^{(2+o(1))n} (n → ∞).

Remark 2. With our perfectionist in mind: the subscript 1 refers to linear sets, the dash superscript indicates that we are interested not in all linear sets but only in those not containing arithmetic progressions.

The smallest linear Roth set we were able to find is A = {0, 4, 6, 13, 14, 18, 19, 21, 31}. It is easily verified that this set is free of arithmetic progressions, and the way to verify linearity will be clear from Section 2. We will explain later how this set was found.

An implicit goal of our paper is to introduce a new linear algebraic method that allowed us to prove Theorems 1 and 2 and that, we believe, can be fruitful in investigating other problems in this area. Last but not least, in Section 5 we present a number of open questions.

COMBINATORICS AND LINEAR ALGEBRA 5

2. Linear algebraic method

In fact, some linear algebraic considerations were used already by Freiman himself. For example, it follows immediately from the definition that any non-singular (injective) affine transformation φ: ℝ^{m} → ℝ^{l} that maps a set A ⊆ ℤ^{m} onto a set of integer vectors actually induces an isomorphism between the two sets. The converse is not true: given two isomorphic sets A and B there may not exist an affine transformation which maps A onto B. (Consider the example of A = {0, 1, 10, 11} and B = {0, 1, 100, 101} in ℤ.) However, Freiman has proven the following.

Theorem 3 (Freiman, [1]). Let A ⊆ ℤ^{m} be a finite set of rank r, and let K ⊆ ℤ^{r} be a set in ℤ^{r}, not in an affine hyperplane, and isomorphic to A. Then there exists an affine transformation φ: ℤ^{r} → ℤ^{m} that maps K onto A.

This theorem shows that all isomorphic sets from the same class have one “underlying pre-image” in ℤ^{r} which can be considered as a canonical (up to linear algebraic affine isomorphisms) representative of the class, and minimal experience in the field convinces one that common additive properties isomorphic sets share are best described through this representative.

In this paper we are interested primarily in linear sets of integers: r = m = l = 1. By Theorem 3, an isomorphic image of a linear set A ⊆ ℤ can be obtained by an affine transformation of A, and this has a simple direct proof (that can be easily modified to produce an alternative proof of the general case). Let A = {a_{1}, …, a_{n}} ⊆ ℤ, and assume that A′ = {a′_{1}, …, a′_{n}} ⊆ ℤ is isomorphic to A. Then the set on the plane {(a_{1}, a′_{1}), …, (a_{n}, a′_{n})} is clearly isomorphic to both A and A′, and hence lies on a straight line, say y = λx + b; thus a′_{i} = λa_{i} + b and A′ is an affine image of A.

A practical conclusion we will need later: assuming that A and A′ are isomorphic linear sets of integers such that min(A) = min(A′) = 0 and gcd(A) = gcd(A′) = 1, we have either A′ = A or A′ = max(A) − A.

Our key idea is to give a linear algebraic definition to the very notion of isomorphism. Given an abelian group A, we consider A^{n} = A × ⋯ × A as an n-dimensional module over the ring of integers, and we regard (ordered) n-element subsets A ⊆ A as elements of this module. Let S ⊆ ℤ^{n} be the set of all n-dimensional integer vectors s, such that either two of the coordinates of s equal 1, two equal −1, and the rest are zero, or two of the coordinates of s equal 1, one equals −2, and the rest are zero; for instance, typical vectors for n = 7 can be s = (0, −1, 0, 1, −1, 0, 1) or s = (1, 0, 0, 1, 0, −2, 0). Any vector of this type corresponds, of course, to an identity of the type (1), and we identify the vectors with the corresponding identities. (Notice, that left out of this correspondence are trivial identities and more generally, all identities (1) whose left and right hand sides

6 SERGEI V. KONYAGIN AND VSEVOLOD F. LEV

share a common index.) This allows us to speak about linearly dependent and linearly independent identities. Now, each n-element set A ⊆ A is determined up to isomorphism by the system of all identities it satisfies, that is by the set of all vectors from S to which it is orthogonal. We denote this set by S_{A}; thus, A is isomorphic to B if and only if S_{A} = S_{B}. Notice, that this does not require A and B to reside in the same group.

Let 1 = (1, …, 1)^{t} be the column vector with all the coordinates equal 1. We write L_{0} = Sp {1} ⊆ ℝ^{n}, so that (L_{0})^{⊥} is the (n−1)-dimensional subspace of all vectors whose coordinates add up to 0, and S_{A} ⊆ S ⊆ (L_{0})^{⊥}. We define L_{A} to be the subspace of all those real vectors which satisfy all the identities for A:

L_{A} = (Sp S_{A})^{⊥}.

Clearly, S ∩ L_{A}^{⊥} = S_{A} and L_{0} ⊆ L_{A}. By k(A) we denote the maximal number of linearly independent identities that A satisfies; thus, dim L_{A} = n − k(A).

The linear algebraic core of out method is the following theorem.

Theorem 4. For any set A ⊆ ℤ^{m} of n integer vectors, we have r(A) = n − 1 − k(A). Moreover, let {f^{(1)}, …, f^{(r)}} be a set of r = r(A) integer vectors complementing 1 (the basis of L_{0}) to a basis of L_{A}, and let F = ∥f_{i}^{(j)}∥ ∈ M_{n×r}[ℤ] be the integer matrix whose columns are formed by the vectors f^{(j)}. Then the rows f_{i} of this matrix form a set of n vectors in ℤ^{r} which is isomorphic to A and is not contained in an affine hyperplane.

Proof. We write ρ = n − 1 − k(A) (the equality ρ = r will be established later) and we choose f^{(j)} ∈ ℤ^{n} (j = 1, …, ρ) so that

(2)  {f^{(1)}, …, f^{(ρ)}, 1}

is a basis of L_{A}. We then proceed to define f_{i} ∈ ℤ^{ρ} (i = 1, …, n) to be the rows of the matrix F = ∥f_{i}^{(j)}∥.

We observe first that f_{i} are not in an affine hyperplane of ℤ^{ρ}, as the vectors in (2) are linearly independent. Next, we show that the set of identities satisfied by {f_{1}, …, f_{n}} is precisely S_{A}. Indeed, let s = (s_{1}, …, s_{n}) ∈ S. Obviously, s_{1}f_{1} + ⋯ + s_{n}f_{n} = 0 holds if and only if (s, f^{(j)}) = 0 for all j = 1, …, ρ, which is equivalent to s ∈ L_{A}^{⊥}, that is to s ∈ S_{A} (in view of s ∈ S). This proves that the set of ρ-dimensional vectors {f_{i}} is isomorphic to the original set A, whence r ≥ ρ, and it remains to establish the inverse inequality r ≤ ρ.

To this end, let {g_{1}, …, g_{n}} ∈ ℤ^{r} be a set of n vectors in ℤ^{r}, isomorphic to A and not in an affine hyperplane. Let G ∈ M_{n×r}[ℤ] be the matrix whose i-th row is g_{i} (for i = 1, …, n), and let g^{(j)} (j = 1, …, r) be the columns of G. Since

g^{(1)}, …, g^{(r)}, 1

are linearly independent vectors lying in L_{A}, it follows that dim L_{A} ≥ r + 1 and ρ = dim L_{A} − 1 ≥ r, as required. □

Corollary 1. Let A ⊆ ℤ^{m} be a linear set, and suppose that a ∉ A satisfies a_{i}+a_{j} = a_{k}+a with some a_{i}, a_{j}, a_{u} ∈ A. Then A′ = A ∪ {a} is linear also.

Proof. We have |A′| = |A| + 1 and t(A′) ≥ t(A) + 1, as the new identity is obviously independent of those satisfied by the elements of A. Thus,

r(A′) = |A′| − 1 − t(A′) ≤ |A| − 1 − t(A) = 1.
□

With the above developed tools handy, we are in a position to prove Theorems 1 and 2.

3. Proof of Theorem 1

Below, we denote the number of classes of isomorphic n-element integer sets of rank r by t_{r}(n).

We first prove the lower bound of Theorem 1 by an explicit construction. We let

A = {0, 1, …, m − 1, m, 2m, …, m^{2}} ∪ {a_{0}, a_{1}, …, a_{n−2m}},

where m = m(n) ∈ [2, n/2) will be determined later, and a_{i} are arbitrary integers, satisfying

a_{0} = m^{2}, 1 ≤ a_{i} − a_{i−1} ≤ m^{2} (i = 1, …, n − 2m − 1),

2 ≤ a_{n−2m} − a_{n−2m−1} ≤ m^{2}. (3)

By Corollary 1, all these sets are linear, as so is the progression {0, 1, …, m} and as each subsequent element of A is easily seen to yield a new identity. Next, none of these sets are isomorphic, since gcd(A) = 1 for all A and the left inequality in (3) shows that max(A) − A = a_{n−2m} − A is never a set of the same type. Finally, the number of sets of this form is

(m^{2})^{n−2m−1}(m^{2} − 1);

choosing m ≍ n/ ln n we obtain

t(n) ≥ t_{1}(n) ≥ n^{(2+o(1))n}.

To prove the upper bound, we estimate separately t_{r}(n) for each r = 1, …, n − 1. We consider all possible identities (1) such that no common index is shared by both sides, and moreover, either i ≠ j, or u ≠ v. Those identities that can be obtained one from another by switching their sides, or by switching the summands in the same side, will not be distinguished. The total number of identities is then

N = 3\binom{n}{4} + 3\binom{n}{3} = 3\binom{n + 1}{4}.

The total number of ways to choose k = n − 1 − r linearly independent identities from these N is at most \binom{N}{k}, and each choice results in a class of isomorphic sets of rank r. Our plan is to employ the fact that distinct systems of identities can result in the same class.

Let A be a set of n integers, and let s_{1}, …, s_{k} be a maximum system of independent identities that A satisfies. Next, let {f_{1}, …, f_{n}} ⊆ ℤ^{r} be a set of n vectors in ℤ^{r}, not in an affine hyperplane and isomorphic to A. By F_{1} we denote the n × (n − k) matrix whose rows are vectors f_{i}, and with the vector 1 adjacent at the right. The row rank of the matrix F_{1} equals to its column rank, which is n − k; to simplify the presentation we assume that it is n − k last rows of F_{1} which are linearly independent. Now, consider a permutation σ of the first k coordinates of ℝ^{n}. This permutation maps s_{1}, …, s_{k} into another system of identities s′_{1}, …, s′_{k} that results in the same class of sets, isomorphic to A. We show that the new system {s′_{i}} is distinct from the original system {s_{i}}; then any class is induced by at least k! different systems of identities, whence

(4)  t_{r}(n) ≤ \frac{1}{k!}\binom{N}{k}.

Assume, on the contrary, that {s′_{i}} coincides with {s_{i}}. The matrix F_{1} has the property that every its column is orthogonal to any identity s_{i}, and our assumption implies that the matrix F′_{1}, obtained from F_{1} by permuting its first k rows according to σ, has the same property. Thus, the column spaces of both F_{1} and F′_{1} equal to the orthogonal complement of S_{A} (that is to L_{A}). It follows that any column of F′_{1} can be written uniquely as a linear combination of columns of F_{1}; coincidence of last n − k coordinates shows now that each column of F′_{1} is equal to the corresponding column of F_{1}. This shows that F_{1} has coinciding rows, unless σ is the identical permutation. However, this is impossible, as an identity f_{i} = f_{j} would yield a similar identity for two elements of A, while A is assumed to be a set with no repetitions.

Thus, (4) is established and the rest is the matter of simple technique:

t(n) = ∑_{r=1}^{n−1} t_{r}(n) ≤ ∑_{k=0}^{n−2} \frac{1}{k!}\binom{N}{k} < ∑_{k=0}^{n−2} \frac{N^{k}}{(k!)^{2}}

< n\frac{N^{n−2}}{((n − 2)!)^{2}} < n^{5} \frac{N^{n−2}}{(n!)^{2}} < n^{5} \frac{n^{4n−8}}{8^{n−2}(n/e)^{2n}} = (\frac{e^{2}}{8} )^{n} \frac{64}{n^{3}} n^{2n} < n^{2n},

taking into account that N < n^{4}/8 and assuming n ≥ 4.

4. Proof of Theorem 2

We start with the 9-element set

A_{0} = {0, 4, 6, 13, 14, 18, 19, 21, 31}

which is immediately verified to be free of arithmetic progressions and which is linear, satisfying 7 linearly independent identities that are represented by the rows of the matrix

( \begin{matrix}1 & −1 & 0 & 0 & −1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & −1 & 0 & 0 & −1 & 1 \\ 0 & 0 & 0 & 1 & −1 & −1 & 1 & 0 & 0 \\ 1 & 0 & 0 & −1 & 0 & −1 & 0 & 0 & 1 \\ 0 & 1 & −1 & 0 & 0 & 0 & −1 & 1 & 0 \\ 0 & 0 & 1 & −1 & −1 & 0 & 0 & 1 & 0 \\ 1 & 0 & −1 & −1 & 0 & 0 & 1 & 0 & 0 \end{matrix} ) .

The very existence of sets like this was questioned by Freiman, and we want to explain at this point how this particular set was found before we proceed with the proof of Theorem 2. Our idea was to find a “compact” set of rank 2 on the plane free of arithmetic progressions, and to add a new independent identity to the system of those already satisfied so that the linear set produced in this way will keep the property of being free of progressions. We were able to achieve it for the “butterfly set” shown on Figure 1. The identities of this set are represented by the first 6 lines of the matrix above, and the additional identity is represented by the last line. (In fact, the first set for which we could carry out our plan is that shown on Figure 2; the “butterfly set” is a subset of this larger set.)

[figure: 1; 2; 3; 4; 5; 6; 7; 8; 9; Figure 1.; Figure 2.]

We next extend A_{0} to the 17-element set

A_{1} = {0, 4, 6, 13, 14, 18, 19, 21, 31, 46, 63, 82, 103, 127, 147, 169, 194}

10 SERGEI V. KONYAGIN AND VSEVOLOD F. LEV

which is also free of arithmetic progressions, linear (each element starting from 46 is involved in an identity with some preceding elements) and has the additional property that

(5)  a_{j} − a_{j−1} > a_{⌊j/2⌋} for j ≥ 10.

The elements 46, 63, …, 169 were found essentially by trial and error using a Maple program.

We now present an algorithm that allows one to extend a given set A = {a_{1}, …, a_{n}} of n ≥ 17 integers which is linear, satisfies (5) and contains no progressions, to an (n + 1)- element set A′ = A ∪ {a_{n+1}} with the same properties. We distinguish two cases:

(6)  a_{n} > 2a_{n−⌊\sqrt{n}/2⌋}

in which case n will be called a good index, and

(7)  a_{n} ≤ 2a_{n−⌊\sqrt{n}/2⌋},

in which case n is a bad index.

1) If n is good (that is, (6) holds) we define a_{n+1} by

a_{n+1} = a_{n} + a_{j} − a_{i},

where i, j ∈ [1, n] are some indices, satisfying

(8)  i ≤ \frac{j}{2}, j ≥ 1 + ⌊\frac{n + 1}{2}⌋

(whence j ≥ 10). We notice that (5) holds with j = n + 1, as

a_{n+1} − a_{n} = a_{j} − a_{i} = a_{j−1} + (a_{j} − a_{j−1} − a_{i}) > a_{j−1} ≥ a_{⌊(n+1)/2⌋},

and that all the values of a_{n+1} that can be obtained in this way are distinct, as

a_{j+1} − a_{i} = (a_{j+1} − a_{j}) + a_{j} − a_{i} > a_{⌊(j+1)/2⌋} + a_{j} − a_{i} ≥ a_{j} = a_{j} − a_{1}

for any i, j under (8) (and j ≤ n − 1). The total numbers of pairs (i, j) allowed is

#\{(i, j)\} = ∑_{j=⌊(n+1)/2⌋+1}^{n} ⌊\frac{j}{2}⌋ = \frac{1}{2} ∑_{j=⌊(n+1)/2⌋+1}^{n} j − \frac{1}{2} ⌊\frac{n + 1}{4}⌋ > \frac{3}{16}n^{2} − \frac{1}{8}n − 1,

while the number of pairs that result in an arithmetic progression of the form {a_{μ}, a_{ν}, a_{n+1}} does not exceed

∑_{ν=n−⌊\sqrt{n}/2⌋+1}^{n}(ν − 1) ≤ \frac{1}{2}n\sqrt{n} − \frac{1}{8}n − 1.

(We omit routine calculations above.) It follows that the number of choices of a_{n+1} such that A′ satisfies all the required properties is more than

\frac{3}{16}n^{2} − \frac{1}{2}n\sqrt{n} = \frac{3}{16}n^{2} (1 − \frac{8}{3\sqrt{n}}) .

2) If n is bad (that is, (7) holds), we define

a_{n+1} = a_{n} + a_{n−1} − a_{i},

where i = 1 or i = 2. In either case (5) holds with j = n + 1, as

a_{n+1} − a_{n} ≥ a_{n−1} − a_{2} > a_{n−2} > a_{⌊(n+1)/2⌋}.

Moreover, at least one choice of i yields no progressions of the form {a_{μ}, a_{ν}, a_{n+1}}. Indeed, in view of a_{n+1} > 2a_{n} in such a progression we necessarily have ν = n, whence

a_{n} − a_{μ} = a_{n−1} − a_{i}

and therefore

a_{μ_{2}} − a_{μ_{1}} = a_{2} − a_{1} = 4,

assuming that both i = 1 and i = 2 yield a progression. In view of (5), this last equality is only possible if μ_{2} ≤ 6, in contradiction to

a_{μ_{2}} − a_{2} = a_{n} − a_{n−1} ≥ a_{⌊n/2⌋}.

It follows that for n bad there is always at least one choice of a_{n+1} such that A′ satisfies the required properties.

For n ≥ 10 we define m = m(n) = n − ⌊\sqrt{n}/2⌋ + 1, so that 10 ≤ m ≤ n. Suppose that {a_{1}, …, a_{m}, …, a_{n}} is obtained from A_{1} using the algorithm above; we claim that at most one of the indices m, …, n is bad. Indeed, if m ≤ i < j ≤ n and if i is bad, then

a_{j} ≥ a_{i+1} ≥ a_{i} + a_{i−1} − a_{2} > 2a_{i−1} ≥ 2a_{m−1} = 2a_{n−⌊\sqrt{n}/2⌋} ≥ 2a_{j−⌊\sqrt{j}/2⌋}

and j is good.

We can now complete the proof of Theorem 2. We use induction on n to show that the number of n-element sets that our algorithm produces is at least

C (\frac{3}{16})^{n} ((n − 1)!)^{2} n^{−15\sqrt{n}}

for a (sufficiently small) positive constant C > 0. Since all these sets are linear, they are pairwise non-isomorphic by Corollary 1.

Small values of n present no problem as the constant C can be chosen as small as we wish. Now, if n is sufficiently large and if m is defined as above, then by the induction hypothesis, the number of n-element sets is

≥ C (\frac{3}{16})^{m} ((m − 2)!)^{2} (m − 1)^{−15\sqrt{m−1}} ∏_{j=m−1}^{n−2} \frac{3}{16}j^{2} (1 − \frac{8}{3\sqrt{j}} )

≥ C (\frac{3}{16})^{n} ((n − 1)!)^{2} \frac{1}{(n − 1)^{2}} (1 − \frac{3}{\sqrt{m}})^{n−m} n^{−15\sqrt{m}}

≥ C (\frac{3}{16})^{n} ((n − 1)!)^{2} n^{−3−15\sqrt{m}}

≥ C (\frac{3}{16})^{n} ((n − 1)!)^{2} n^{−15\sqrt{n}},

since n − m = \sqrt{m}(1 + o(1)), and \sqrt{n} − \sqrt{m} = \frac{1}{4} + o(1), as n → ∞.

Notice, that this argument gives an alternative proof of the lower bound of Theorem 1.

5. Concluding remarks

Below, we state some related problems.

5.1. “Short” representatives of isomorphism classes. The set {0, 1, 2, 4, …, 2^{n−2}} is linear and as such is not isomorphic to any “shorter” integer set. This is believed to be the extremal case.

Conjecture 1. Any n-element integer set A is isomorphic to a subset of [0, 2^{n−2}].

For A linear this is established in [1, Theorem 1.22] and can also be proven using our method. On the other hand, all Sidon sets (r = n − 1) are isomorphic, and it is wellknown that n-element Sidon sets exist in [0, l], provided l = n^{2}(1 + o(1)). The general case, however, remains open.

5.2. “Compact” representatives of isomorphism classes. It is as natural, given a set A of rank r, to seek a “compact” subset of ℤ^{r}, isomorphic to A. Based on several numerical examples, we dare to come out with the following amazing conjecture.

Conjecture 2. For any n-element integer set A of rank r there exist non-negative integers l_{1}, …, l_{r} and a set A′ ⊆ ℤ^{r}, isomorphic to A, so that

A′ ⊆ [0, 2^{l_{1}}] × ⋯ × [0, 2^{l_{r}}]

and l_{1} + ⋯ + l_{r} ≤ n − r − 1.

For r = 1, this reduces to the linear case of Conjecture 1, and thus is settled; the case r = n − 1 (Sidon sets) is trivial. Otherwise, Conjecture 2 is open.

COMBINATORICS AND LINEAR ALGEBRA 13

5.3. The shortest set of a given rank. The question of Section 5.1 can be further specialized as follows: what is the minimum integer l(r) such that any n-element set of rank r is isomorphic to a subset of [0, l(r)]? However, it seems to be more reasonable to ask for short, and not for long sets of a given rank.

Problem 1. Find or estimate l(r), the minimum integer l such that there exists an n-element integer set A ⊆ [0, l] of the rank r(A) ≥ r.

The problem is trivial for r = 1 (l(1) = n − 1), and for r = n − 1 a classical result about Sidon sets gives l(n − 1) = n^{2} + O(n^{3/2}). (Reducing the exponent 3/2 is a famous open problem.) To obtain an estimate in the general case, one can use [1, Lemma 1.14], which implies that

|2A| := #\{a′ + a′′ | a′, a′′ ∈ A\} ≥ (r + 1) n − \frac{r(r + 1)}{2}.

As, on the other hand, assuming A ⊆ [0, l(r)] we have |2A| ≤ 2l(r) + 1, one easily derives

l(r) ≥ \frac{r + 1}{2} n − \frac{r^{2} + r + 2}{4}.

For Sidon sets, this yields

l(n − 1) ≥ \frac{1}{4} n^{2} (1 + o(1)),

which is not far from the true value indicated above. For r = 2, this yields

(9)  l(2) ≥ \frac{3}{2} n − 2

which is sharp: letting

n_{1} = ⌊\frac{n}{2}⌋ , n_{2} = ⌈\frac{n}{2}⌉ , l = ⌈\frac{3}{2}n⌉ − 2

and

A = {0, …, n_{1} − 1} ∪ {l − n_{2} + 1, …, l},

one could verify that r(A) = 2 (in fact, A is isomorphic to the plane set {(0, 0), …, (0, n_{1}− 1)} ∪ {(1, 0), …, (1, n_{2} − 1)}), whence by (9),

l(2) = ⌈\frac{3}{2}n⌉ − 2.

This suggests that it could be possible to obtain rather precise estimates for r ∈ [3, n−2].

5.4. Proportion of linear sets among all integer sets. Further refinements of Theorems 1 and 2 would be interesting. In particular, it seems natural to conjecture that for large n, “almost all” classes of isomorphic n-element sets are linear:

Conjecture 3.

lim_{n→∞} \frac{t_{1}(n)}{t(n)} = 1.

Also, it would be interesting to determine the proportion of linear classes, free of arithmetic progressions, among all linear classes.

References

[1] G. Freiman, Foundations of a structure theory of set addition, Kazan 1966 [Russian]. English translation in: Translations of Math. Monographs 37 (1973), American Math. Soc., Providence.

[2] G.A. Asaphova, On one type of Latin squares of order 6, in: Number-theoretic investigations in Markov spectrum and structure theory of set addition, Kalinin State University, Moscow, 1973 [Russian].

Department of Mechanics and Mathematics, Moscow State University, Moscow, 119899, Russia.

E-mail address: kon@@nw.math.msu.su

Department of Mathematics, The University of Georgia, Athens, GA 30602, USA.

E-mail address: seva@@math.uga.edu