SYMMETRIC SUBSETS OF LATTICE PATHS

Oleg Verbitsky^{1}

Institute of Information Systems, Vienna University of Technology, Favoritenstraße 9, 1090 Wien,

Austria

                            oleg@dbai.tuwien.ac.at

Received: 11/10/99, Revised: 3/30/00, Accepted: 4/13/00, Published: 5/19/00

Abstract

Let [n] = {0, 1, …, n}. A subset S of [n] is symmetric if S = g − S for a natural number g. We show that, for every f : [n] → [2n] with the restriction 1 ≤ f(i + 1) − f(i) ≤ 2 for all i < n, there is some S ⊂ [n] such that |S| ≥ 2 ln n − O(1), with the property that both S and f(S) are symmetric. We prove this result by finding a lower bound for the length of a symmetric pattern whose abelian occurrences are encountered in all binary words of length n. We also show that if M is such that for every f : [n] → [2n] as above, there is at least one S ⊂ [n] with |S| ≥ M and both S and f(S) symmetric, then M ≤ (7 + o(1))\sqrt{n}. This result is based on the construction of appropriate Sidon B_{2}-sequences. In another interpretation, our results can be formulated as lower and upper bounds for M such that every path of length n along basis vectors of a two-dimensional lattice contains an M-point centrally symmetric set.

1. Introduction

Let [n] = {0, 1, 2, …, n}, with 0 included for our convenience. We consider injective orderpreserving transformations f : [n] → [2n] with restriction f(i + 1) − f(i) ≤ 2 for all i < n. We wonder to which extent such transformations can violate the regular structure of [n]. Namely, suppose that P is a regularity property of a set of integers, say, one of being an arithmetic progression. We then wish to know the maximum M = M(n) such that, for every f as above, at least one set S ⊆ [n] with |S| ≥ M has property P and its image f(S) still has the same property.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 0 (2000), #A05 2

In the case of arithmetic progressions, it is easy to observe an equivalent reformulation of the question. Let V = {v_{0}, …, v_{n}} be a sequence of points in the grid ℤ^{2} with each difference v_{i+1} −v_{i} being either a = (1, 1) or b = (1, 2). Now the question is what is the maximum M such that every V contains an M-term arithmetic progression of vectors. To see the equivalence of the two problems, it suffices to view a set V as the graph of a map f. Clearly, f preserves an arithmetic progression S ⊆ [n] iff {(x, f(x)) : x ∈ S} is an arithmetic progression in V. Notice that the specification of differences a and b is actually irrelevant — those could be any other pair of non-collinear vectors as well, say, a = (1, 0) and b = (0, 1).

1On leave from the Department of Mechanics & Mathematics, Lviv University, Ukraine. Research supported in part by a Lise Meitner Fellowship of the Austrian Science Foundation (FWF) and by grant INTAS-96-0753.

As the choice of the initial point v_{0} does not affect anything, a set V is characterized by the sequence of differences v_{1} − v_{0}, …, v_{n} − v_{n−1}, which can be regarded as a word w(V) of length n over alphabet {a, b}. In this way we arrive at yet another reformulation of the problem under consideration. We call an arbitrary sequence of variables a pattern. An abelian occurrence of a pattern in a word is a subword obtainable from the pattern by substituting nonempty words in place of variables so that words replacing the same variable may differ only in order of letters (see Section 2 for more details). It is not hard to observe a one-to-one correspondence between (m + 1)-term arithmetic progressions in V and abelian occurrences of the pattern x^{m} in w(V). Thus, the value of M(n) is the maximum number M such that every word of length n over the binary alphabet has an abelian occurrence of x^{M−1}.

Dekking [11] constructs an infinite word in the binary alphabet without abelian occurrences of x^{4}. It immediately follows [21, theorem 6.13] that M(n) ≤ 4, i.e. 5-term arithmetic progressions can all be destroyed by some transformation f.

This motivates an extension of property P. A set S ⊆ ℤ^{k} such that S = g − S for a lattice point g ∈ ℤ^{k} is called symmetric (with respect to the center at rational point \frac{1}{2}g). From now on the property P extended to being symmetric will be our main concern. Given V ⊆ ℤ^{k}, let MS(V) denote the maximum cardinality of a symmetric subset of V.

A pattern is symmetric if it reads the same backward as forward, like xyx. With notation introduced above, we again have a one-to-one correspondence between sets S ⊆ [n] whose symmetry is preserved by f, symmetric subsets of the graph V of f, and abelian occurrences of symmetric patterns in the word w(V). Correspondingly, we have the following equivalences whose proof is given in more detail in Section 2.

Lemma 1.1 The statements below are equivalent.

1. M(n) = min_{f:[n]→[2n]} max_{S⊆[n]} {|S| : both S and f(S) are symmetric}, where the minimum is taken over all f with

1 ≤ f(i + 1) − f(i) ≤ 2 for i < n.  (1)

2. M(n) is the minimum of MS(V) over all subsets V = {v_{0}, v_{1}, …, v_{n}} of ℤ^{2} with each v_{i+1} − v_{i} equal to either a or b, where a and b are arbitrarily fixed non-collinear vectors.

3. M(n) is the maximum M such that every word of length n over the binary alphabet has abelian occurrence of a symmetric pattern of length at least M − 1.

In contrast to the case of arithmetic progressions, M(n) now grows with n, that is, no f is able to destroy symmetric subsets so well as arithmetic progressions. To show this, consider an infinite sequence of symmetric patterns

P_{1} = x, ; P_{2} = xyx, ; P_{3} = xyxzxyx, ; P_{4} = xyxzxyxuxyxzxyx, ; ⋮  (2)

where P_{i+1} is the result of inserting a new variable between two copies of P_{i}. In combinatorics of words, members of this sequence are called sesquipowers or Zimin’s patterns. Coudrain and Schützenberger [10] proved that each P_{i} must occur in all long enough words over a finite alphabet. Here we mean literal rather than abelian occurrence, i.e. the same variable is substituted everywhere by the same word. The unavoidability of sesquipowers immediately implies that M(n) goes to the infinity with n increasing. However, this argument gives a very small lower bound for M(n), actually, a kind of the inverse tower function (see Lemma 2.3).

In Section 3 we prove a better lower bound M(n) = Ω(ln n) based on estimation of how long symmetric pattern is represented by an abelian occurrence in every binary word of length n. Similarly to the O-notation, we write Ω(h(n)) to refer to a function of n that everywhere exceeds c · h(n) for a positive constant c.

In Section 4 we prove upper bound M(n) = O(\sqrt{n}). As the main technical tool we use B_{2}-sequences introduced by Sidon and investigated by many authors (see [21, section 4.1] for survey and references). A set X of integers is called a B_{2}-sequence if for any integer g the equation x + y = g has at most one solution in X with x ≤ y. In other words, a B_{2}-sequence X is a highly asymmetric set characterized by MS(X) ≤ 2. There are several constructions [24, 6, 13, 14, 9, 7, 19] of dense B_{2}-sequences in [n]. We employ a fairly simple and explicit construction of [19], making use of an additional uniformity property of it.

We conclude the paper with discussion of open problems in Section 5.

Related work. The van der Waerden theorem can be restated so that every infinite subsequence v_{0}, v_{1}, … of ℕ with v_{i+1} − v_{i} = O(1) contains arbitrarily long arithmetic progressions (see [8]). As Dekking’s result shows, a similar statement in ℤ^{2} is false. However, Ramsey and Gerver [23] prove that every infinite sequence v_{0}, v_{1}, … in ℤ^{2} with bounded distances ||v_{i+1}−v_{i}|| between any two successive points contains arbitrarily large subsets of collinear points. Pomerance [22] shows this holds true even under the weaker assumption that

lim inf_{n→∞} \frac{1}{n} ∑_{i=1}^{n} ||v_{i+1} − v_{i}|| < ∞.  (3)

These results can be viewed as two-dimensional analogs of the van der Waerden theorem and its density version of Szemerédi, with collinear subsets instead of arithmetic progressions. In this respect our result on behavior of M(n), in view of item 2 of Lemma 1.1, can serve as yet another two-dimensional analog of van der Waerden’s theorem, with arithmetic progressions replaced by symmetric subsets. The multi-dimensional analog of Szemerédi’s theorem is also true as shown by Banakh [5], who observed that condition (3) guarantees the existence of arbitrarily long symmetric subsequences in an infinite sequence v_{0}, v_{1}, … of points in ℤ^{k}, k ≥ 1. It should be noted that in the case of k = 2 the latter result strengthes the claim that M(n) → ∞ but provides no satisfactory lower bound for M(n).

Banakh and Protasov [3, 4] prove that the minimal number of colors required for coloring the n-dimensional integer grid ℤ^{n} avoiding infinite symmetric monochromatic subsets is n + 1. Unavoidable symmetries in words are investigated by Fouché [16].

2. Preliminaries

In this section we prove Lemma 1.1 and then show that M(n) → ∞ as n → ∞. Recall that throughout the paper MS(V) denotes the cardinality of the largest symmetric subset of V.

The proof of the equivalence of statements 1 and 2 of Lemma 1.1 in the case that

a = (1, 1), b = (1, 2)  (4)

follows arguments outlined in the introduction for arithmetic progressions. With a function f we associate its graph V = {v_{0}, …, v_{n}}, where v_{i} = (i, f(i)). The bounds (1) imply that v_{i+1} − v_{i} ∈ {a, b}. Vice versa, any set V = {v_{0}, …, v_{n}} in ℤ^{2} with the latter condition can be viewed as the graph of a function f of the prescribed kind. A set S ⊆ [n] and its image f(S) are both symmetric iff S′ = {(i, f(i)) : i ∈ S} is a symmetric subset of V. This completes the proof in the case (4).

The case of arbitrary non-collinear a and b reduces to the case (4). Really, consider two sets V = {v_{0}, …, v_{n}} and V′ = {v′_{0}, …, v′_{n}} in ℤ^{2} with all v_{i+1} − v_{i} ∈ {(1, 1), (1, 2)} and v′_{i+1} − v′_{i} ∈ {a, b}, where a and b are non-collinear. Let ϕ be the affine transformation of ℤ^{2} into itself that takes v_{0} to v′_{0}, (1, 1) to a, and (1, 2) to b. Then ϕ establishes a one-to-one correspondence between V and V′ that matches symmetric subsets in V and symmetric subsets in V′. It follows that MS(V) = MS(V′), thereby proving the equivalence of statements 1 and 2.

Before proving the equivalence of statements 2 and 3, let us recall the relevant notions of the formal language theory. A pattern is a word over the alphabet of variables {x_{1}, x_{2}, …}. Pattern x_{i_{1}}x_{i_{2}} … x_{i_{l}} is symmetric if i_{j} = i_{l+1−j} for all j ≤ l. Let A = {a_{1}, …, a_{m}} be a finite alphabet. The number of occurrences of letter a_{i} in a word w over A is denoted by |w|_{a_{i}}. A commutative index of w is the tuple ⟨|w|_{a_{1}}, …, |w|_{a_{m}}⟩. A subword u of a word w is an occurrence of a pattern P = x_{i_{1}} … x_{i_{l}} if u can be obtained from P by substituting nonempty words in place of each variable, where the same variable is everywhere replaced with the same word. If the same variable may be replaced by (possibly distinct) words with the same commutative index, u is called an abelian occurrence of P.

Example. In word a_{1}a_{1}a_{2}a_{1}a_{2}a_{1}a_{3}, subwords a_{1}a_{1}, a_{1}a_{2}a_{1}a_{2}, and a_{2}a_{1}a_{2}a_{1} are occurrences of pattern x_{1}x_{1}. In addition, a_{1}a_{1}a_{2}a_{1}a_{2}a_{1} is an abelian occurrence of the same pattern.

Given a sequence of vectors V = {v_{0}, v_{1}, …, v_{n}} in ℤ^{k} with all v_{i} − v_{i−1} in a finite set A ⊂ ℤ^{k}, we associate with V the sequence w(V) of differences v_{1} − v_{0}, v_{2} − v_{1}, …, v_{k} − v_{k−1} which will be viewed as a word of length n over alphabet A.

Lemma 2.1

1. If w(V) has an abelian occurrence of a symmetric pattern of length l, then MS(V) ≥ l+1.

2. Conversely, suppose that A is a linearly independent set of vectors. Then w(V) has an abelian occurrence of a symmetric pattern of length at least MS(V) − 1.

Proof. 1. Recall that word w(V) is a sequence of vectors v_{1} − v_{0}, …, v_{n} − v_{n−1}. Given a subword u = v_{i+1} − v_{i} … v_{j} − v_{j−1}, i < j, we call v_{i} the initial point and v_{j} the terminal point of u. Let u = u_{1} … u_{l} be an abelian occurrence of a symmetric pattern P of length l, where u_{s} is substituted in place of s-th variable of P. Let v_{i_{s−1}} and v_{i_{s}} be the initial and terminal points of u_{s}. Then the set {v_{i_{0}}, …, v_{i_{l}}} is symmetric. This can be shown by easy induction. Really, assume that v_{i_{1}} and v_{i_{l−1}} are symmetric with respect to the center \frac{1}{2}g, that is, v_{i_{1}} + v_{i_{l−1}} = g. As u_{1} and u_{l} differ only in order of their letters, we have v_{i_{1}} − v_{i_{0}} = v_{i_{l}} − v_{i_{l−1}}. Consequently, v_{i_{0}} and v_{i_{l}} are symmetric with respect to \frac{1}{2}g too.

2. Let l = MS(V) and v_{i_{0}}, …, v_{i_{l}} be a symmetric subsequence of V. Denote a subword of w(V) whose initial and terminal points are v_{i_{s−1}} and v_{i_{s}} by u_{s}. Then u = u_{i} … u_{l} is an abelian occurrence of a symmetric pattern of length l. It suffices to show that commutative indices of words u_{s} and u_{l+1−s} are the same. Those are uniquely determined by expansions of vectors v_{i_{s}} − v_{i_{s−1}} and v_{i_{l+1−s}} − v_{i_{l−s}} in basis A. It remains to notice that the last two vectors are equal by symmetricalness of {v_{i_{0}}, …, v_{i_{l}}}. □

The equivalence of statements 2 and 3 of Lemma 1.1 now follows directly from Lemma 2.1. The proof of Lemma 1.1 is complete.

Proposition 2.2 M(n) → ∞ as n → ∞.

At this point we prefer the statement 3 of Lemma 1.1. Let L^{non−abel}(n) be the maximal l such that every word of length n over the binary alphabet has an occurrence of a symmetric pattern of length at least l. As M(n) > L^{non−abel}(n), it suffices to show that L^{non−abel}(n) → ∞ for n → ∞. The latter follows from a result of Coudrain and Schützenberger [10] which we state below in a form convenient for our purposes.

Lemma 2.3 ([10]) If L^{non−abel}(n) ≥ l, then L^{non−abel}((n + 1)(2^{n} + 1)) ≥ 2l + 1.

Proof. Assume that every binary word of length n has occurrence of a symmetric pattern P of length l. Any binary word of length (n + 1)(2^{n} + 1) contains two identical subwords of length n separated by a nonempty word. Thus, there is an occurrence of the symmetric pattern P xP, where x is a new variable absent in P. □

Notice that the above argument ensures that each pattern P_{i} of the sequence (2) occurs in any long enough binary word.

3. Lower Bound

The proof of Proposition 2.2 based on Lemma 2.3 gives us an extremely small lower bound for M(n) that is even smaller than the inverse tower function. In this section we improve it to M(n) ≥ 2 ln n − O(1). We first prove an auxiliary fact. Notice that whenever below we refer to the number of subwords of a word, we distinguish all occurrences of a subword, that is, a subword is counted each time it occurs in the word.

Lemma 3.1 Given a word w, let ν(w) denote the number of pairs {u_{1}, u_{2}}, where u_{1} and u_{2} are disjoint subwords of w with the same commutative index. Let N(n) be the minimum of ν(w) over all binary words w of length n. Then

N(n) ≥ (ln n − O(1))n^{2}/4.

Proof. Consider a binary word w of length n and estimate the value ν(w) from below. Expand ν(w) to the sum ∑_{t} ν_{t}(w), where the t-th term counts pairs of subwords with length t. Let σ_{t}(i) denote the number of subwords of w with length t and commutative index ⟨i, t − i⟩. As the total number of subwords of length t is equal to n + 1 − t, notice the equality σ_{t}(0) + σ_{t}(1)+…+σ_{t}(t) = n+1−t. As a subword of length t can overlap with at most 2t−1 subwords of the same length, we have

ν_{t}(w) ≥ \frac{1}{2} ∑_{i=0}^{t} σ_{t}(i)(σ_{t}(i) − (2t − 1)).

Taking into account that

∑_{i=0}^{t} σ_{t}(i)^{2} ≥ (t + 1) (\frac{∑_{i=0}^{t} σ_{t}(i)}{t + 1})^{2} ,

we conclude that

ν_{t}(w) ≥ \frac{1}{2} ((t + 1) (\frac{n + 1 − t}{t + 1})^{2} − (2t − 1)(n + 1 − t))
= \frac{(n + 2)^{2}}{2(t + 1)} − (t + \frac{1}{2})(n + 1) + t^{2} − \frac{1}{2}.

Let us sum these inequalities over t from 1 to s, dropping the last term t^{2} − \frac{1}{2} in the right hand side (anyway it would give us no gain). Summing the first term in the right hand side, we take into account that ∑_{t=1}^{s} 1/t − ln s approaches Euler’s constant as s increases. Therefore,

∑_{t=1}^{s} ν_{t}(w) ≥ \frac{1}{2}(ln s − O(1))(n + 2)^{2} − \frac{s(s + 2)}{2}(n + 1).

Setting s = ⌈\sqrt{n} ⌉, we obtain the proclaimed bound for ν(w) and hence for N(n). □

Theorem 3.2 M(n) ≥ 2 ln n − O(1).

Proof. We adhere to the statement 2 of Lemma 1.1. Let V = {v_{0}, v_{1}, …, v_{n}} be a set of points in ℤ^{2} with v_{i+1} − v_{i} ∈ \{a, b\}. Denote G = \{ \frac{1}{2}(v_{i} + v_{j}) : 0 ≤ i ≤ j ≤ n\}, the set of all potential centers of symmetry. Let m_{g} denote the “multiplicity” of an element g in G, that is, the number of pairs (i, j) such that g = \frac{1}{2}(v_{i} + v_{j}) and i ≤ j. Clearly,

∑_{g∈G} m_{g} = (n + 1)(n + 2)/2.

Furthermore, let N denote the total number of quadruples

(v_{l}, v_{i}, v_{j}, v_{k}) with l < i ≤ j < k and v_{i} − v_{l} = v_{k} − v_{j}.  (5)

Clearly,

N ≤ ∑_{g∈G} \binom{m_{g}}{2}

(actually, the linear independence of a and b implies the equality here). It follows that

N < \frac{1}{2} ∑_{g∈G} m_{g}^{2} ≤ \frac{1}{2} (max_{g∈G} m_{g}) ∑_{g∈G} m_{g} = \frac{1}{4}n^{2} (1 + O(\frac{1}{n})) max_{g∈G} m_{g}.  (6)

Recall that with the set V we associate a word w(V) over alphabet {a, b}. It is easy to observe a one-to-one correspondence between quadruples (5) in V and pairs of disjoint subwords u_{1} and u_{2} with the same commutative index in w(V). By Lemma 3.1 we have

N ≥ (ln n − O(1))n^{2}/4.

Together with (6), this gives

max_{g∈G} m_{g} ≥ ln n − O(1).

It remains to observe that, for every center g ∈ G, the set V contains a subset that is symmetric with respect to g and has at least 2m_{g} − 1 elements. □

4. Upper Bound

In this section we prove an upper bound for M(n).

Theorem 4.1 M(n) ≤ (7 + o(1))\sqrt{n}.

We use a two-dimensional geometric interpretation of M(n) given by statement 2 of Lemma 1.1. We will construct a set V = {v_{0}, v_{1}, …, v_{n}} of points in ℤ^{2} such that each difference v_{i+1} − v_{i} is either (1, 0) or (0, 1) and MS(V) ≤ (7 + o(1))\sqrt{n}.

Our construction will be completely determined by two sets of integers X = {x_{1}, …, x_{q}} and Y = {y_{1}, …, y_{q}} listed in the ascending order. Given X and Y, consider a sequence of points in ℤ^{2}

(x_{1}, y_{1}), (x_{2}, y_{1}), (x_{2}, y_{2}), (x_{3}, y_{2}), (x_{3}, y_{3}), …, (x_{q}, y_{q})  (7)

We define V by V = V_{1} ∪ V_{2}, where

V_{1} = ⋃_{i=1}^{q} {(x_{i}, y) : y_{i−1} < y ≤ y_{i}} and V_{2} = ⋃_{i=1}^{q−1} {(x, y_{i}) : x_{i} < x ≤ x_{i+1}}

(we set y_{0} = y_{1} − 1 for convenience). Thus, (7) are “corner” points of V, at which difference v_{i+1} − v_{i} changes its value from (1, 0) to (0, 1) or vice versa. Clearly, V consists of x_{q} + y_{q} + 1 − x_{1} − y_{1} points.

Given a set Z = {z_{1}, …, z_{q}} of integers listed in the ascending order, define D(Z) = max_{1≤i<q}(z_{i+1} − z_{i}).

Lemma 4.2 Suppose that V has been constructed based on q-element sets X and Y as described above. Then

MS(V) < MS(X)D(Y) + MS(Y)D(X) + 2q.  (8)

Proof. Let S be the maximum subset of V symmetric with respect to center \frac{1}{2}g, i.e. S = V ∩ (g − V). Clearly,

S = (V_{1} ∩ g − V_{1}) ∪ (V_{2} ∩ g − V_{2}) ∪ (V_{1} ∩ g − V_{2}) ∪ (V_{2} ∩ g − V_{1}).

Let us estimate the cardinality of each member of the union.

V_{1} ∩ g − V_{1} is a symmetric subset of V_{1}. As the projection of V_{1} ∩ g − V_{1} onto the first coordinate is symmetric too, the cardinality of this projection does not exceed MS(X). As any cut of V_{1} by vertical line (i.e. along the second coordinate) containes at most D(Y) points, we have |V_{1} ∩ g − V_{1}| ≤ MS(X)D(Y). Similarly, |V_{2} ∩ g − V_{2}| ≤ MS(Y)D(X).

Observe now that all points of V_{1} differ in the second coordinate and have only q values for the first coordinate, while all points of V_{2} differ in the first coordinate and have only q values for the second coordinate. As a consequence, both V_{1} ∩ g − V_{2} and V_{2} ∩ g − V_{1} have less than q points. The bound (8) follows. □

We now need to choose X and Y so as to make the right hand side of (8) as small as possible. The idea is to use a B_{2}-sequence X = Y, which gives us the best possible MS(X) = MS(Y) = 2. It easily follows from [13] that D(X) ≥ q(1 − o(1)) for any B_{2}-sequence X = {x_{1}, …, x_{q}}. We use a construction of [19] that provides us with D(X) ≤ (3 + o(1))q.

Lemma 4.3 (Krückeberg [19]) For any prime q there is a sequence of integers X = {x_{1}, …, x_{q}} with MS(X) = 2 and D(X) < 3q. Moreover, x_{1} = 0 and x_{q} = 2q^{2} − 2q − 1.

We include the proof of this lemma given in [19], because it contains a simple explicit construction of the needed B_{2}-sequences, thereby making our construction of V explicit too.

Proof. Set x_{i+1} = 2qi − (i^{2} mod q) for 0 ≤ i < q, where expression i^{2} mod q stands for the least non-negative residue of i^{2} modulo q. Obviously, q < x_{i+1} − x_{i} < 3q. To show that X is a B_{2}-sequence, assume that x_{i} + x_{j} = x_{i′} + x_{j′}, i ≤ j, i′ ≤ j′. It is easy to derive from this that

\{ \begin{matrix}i + j & = & i′ + j′ & (mod q) \\ i^{2} + j^{2} & = & (i′)^{2} + (j′)^{2} & (mod q) \end{matrix}

Since in the field 𝔽_{q} a system of kind

\{ \begin{matrix}i + j & = & a \\ i^{2} + j^{2} & = & b \end{matrix}

can have only a unique solution i, j with i ≤ j, we conclude that i = i′ and j = j′. □

Let us summarize our construction of the set V = {v_{0}, v_{1}, …, v_{n}}. Let q be the prime next to (\sqrt{n + 3} + 1)/2 and X be the B_{2}-set given by Lemma 4.3. Applying the construction described in the beginning of the section with Y = X, we obtain a set V′ = {v_{0}, v_{1}, …, v_{n}, …} of 4q^{2} − 4q − 1 ≥ n + 1 points in ℤ^{2}. Leaving aside some last elements of V′, we get the set V. By Lemma 4.2, MS(V) ≤ MS(V′) < 14q. Since the prime next to m does not exceed m + O(m^{α}), where 0 < α < 1 ([18], see also [2, pp. 225, 256] for references on the best current values of α), we have MS(V) ≤ (7 + o(1))\sqrt{n}. The proof of Theorem 4.1 is complete.

Remark 4.4 The choice of Krückeberg’s B_{2}-sequence is essentially best possible, because the right hand side of (8) cannot be smaller than \sqrt{2n}, whatever sets X and Y are. Let us prove this fact. First, observe relation

MS(X) ≥ q/D(X).  (9)

for a set of integers X = {x_{1}, …, x_{q}}. This is a consequence of inclusion X ⊆ ⋃_{g=0}^{D(X)−1}(g + x_{1} + x_{q} − X) which implies |X ∩ (g − X)| ≥ q/D(X) for some g. By (9)

MS(X)D(Y) + MS(Y)D(X) ≥ 2(MS(X)D(Y)MS(Y)D(X))^{1/2} ≥ 2q

and therefore the right hand side of (8) is at least 4q.

Further, observe that MS(V) > max{D(X), D(Y)}. Using this, we have n = |V | − 1 ≤ q(D(X) + D(Y)) < 2q MS(V). Therefore, the right hand side of (8) exceeds 2n/MS(V). It remains to notice that one of the values MS(V) and 2n/MS(V) is at least \sqrt{2n}.

Remark 4.5 Consider a random set V = {v_{0}, v_{1}, …, v_{n}} in ℤ^{2} with v_{i+1} − v_{i} ∈ {a, b} for non-collinear a and b. We mean that the underlying word w(V) is uniformly distributed on {a, b}^{n}. The mean value of MS(V) could serve as an upper bound for M(n). Unfortunately, this probabilistic argument cannot give anything better that the constructive bound of Theorem 4.1 by the following reason.

Just for simplicity assume that n = 2m is even. Let s denote the cardinality of the maximum subset of V symmetric with respect to the center at the medium point v_{m}. Consider now two independent sequences ξ_{1}, …, ξ_{m} and ζ_{1}, …, ζ_{m} of unbiased Bernoulli trials, that is, all ξ_{i} and ζ_{j} are mutually independent random variables that take on equiprobable values 0 and 1. Denote the number of k such that ∑_{i=1}^{k} ξ_{i} = ∑_{i=1}^{k} ζ_{i} by t. In coding a = 0 and b = 1, it becomes clear that s = 2t + 1. Estimate the expectation of t from below.

Let p_{k} = ℙ [∑_{i=1}^{k} ξ_{i} = ∑_{i=1}^{k} ζ_{i}]. By linearity of mathematical expectation, 𝔼 [t] = ∑_{k=1}^{m} p_{k}. Using Chernoff’s bound, we have

p_{k} = ∑_{l=0}^{k} ℙ [∑_{i=1}^{k} ξ_{i} = l]^{2} > ∑_{k/2−\sqrt{k}≤l≤k/2+\sqrt{k}} ℙ [∑_{i=1}^{k} ξ_{i} = l]^{2} ≥

(2\sqrt{k} − 1) (\frac{ℙ [k/2 − \sqrt{k} ≤ ∑_{i=1}^{k} ξ_{i} ≤ k/2 + \sqrt{k}]}{2\sqrt{k} + 1})^{2} ≥ \frac{(1 − 2 exp(−2))^{2}}{2\sqrt{k} + 7} .

Therefore, 𝔼 [t] = Ω (∑_{k=1}^{m} 1/\sqrt{k}) = Ω(\sqrt{m}). As 𝔼 [s] = 2𝔼 [t] + 1, we conclude that the mean value of MS(V) is Ω(\sqrt{n}).

In conclusion we discuss one more aspect of the upper bound proven in this section. Given n, we have constructed a set {v_{0}, v_{1}, …, v_{n}} with

MS(\{v_{0}, v_{1}, …, v_{n}\}) = O(\sqrt{n}).  (10)

Question 4.6 Is it possible to construct an infinite set {v_{0}, v_{1}, v_{2} …} such that (10) is true for all n?

We could achieve this goal with the same construction, if we had an infinite B_{2}-sequence X = {x_{1}, x_{2}, …} with D({x_{1}, …, x_{q}}) = O(q) for all q. However, the latter condition implies |X ∩ [m]| = Ω(\sqrt{m}) for all m, whereas no B_{2}-sequence satisfies this condition by a result of Erdős. Erdős proves that there is a constant c such that for any infinite B_{2}-sequence X the inequality |X ∩ [m]| ≤ c\sqrt{m/ ln m} is true for infinitely many m (see [15]). The best known construction of [1] gives |X ∩ [m]| = Ω ((m ln m)^{1/3}). Nevertheless, we are able at least to approach (10) with an infinite V.

Proposition 4.7 There is an infinite sequence V = {v_{0}, v_{1}, v_{2}, …} with each difference v_{i+1}−v_{i} either (1, 0) or (0, 1) and such that

MS({v_{0}, v_{1}, …, v_{n}}) = n^{1/2+O(1/ ln ln n)}  (11)

for all n.

Proof. We apply the straightforward infinite version of the construction described in the beginning of this section with X = Y = {1, 4, 9, 16, …}, the set of integer squares. By Lemma 4.2, for any integer q and n = 2q^{2} − 2

MS({v_{0}, v_{1}, …, v_{n}}) < 2MS({1, 4, …, q^{2}})D({1, 4, …, q^{2}}) + 2q.

We obviously have D({1, 4, …, q^{2}}) = 2q − 1 and, by Lemma 4.8 below,

MS({1, 4, …, q^{2}}) = q^{O(1/ ln ln q)}.

This proves (11) for all n = 2q^{2} − 2. Equality (11) is true for any other n as well, because the next to n number of kind 2q^{2} − 2 does not exceed n + \sqrt{(n + 2)/2} + 1 = n(1 + o(1)). □

The following lemma in other terms estimates the number of representations of an integer as a sum of two squares. Though this estimate easily follows from the well-known number-theoretic facts, we give a proof for the sake of completeness.

Lemma 4.8 MS({1, 4, …, q^{2}}) = q^{O(1/ ln ln q)}.

Proof. It is easy to see that the maximum subset of {1, 4, …, q^{2}} symmetric with respect to \frac{1}{2}g has as many elements as the number of solutions of equation z_{1} + z_{2} = g in \{1, 4, …, q^{2}\}. The Jacobi theorem (see e.g. [12, theorem 65]) says that if g = 2^{k}m with odd m, then the total number of integer solutions of the equation x^{2} + y^{2} = g is equal to 4E, where E is the excess of the number of divisors t ≡ 1 (mod 4) of m over the number of divisors t ≡ 3 (mod 4) of m. We use the bound E ≤ d(m), where d(m) denotes the total number of positive divisors of m. It is known that d(m) = m^{O(1/ ln ln m)} ([25], see also [20] for the best currently known constant in the exponent). As m ≤ g and it makes sense to consider only g < 2q^{2}, we have d(m) = q^{O(1/ ln ln q)}. Summarizing, we obtain MS({1, 4, …, q^{2}}) ≤ 4E ≤ 4d(m) = q^{O(1/ ln ln q)}. □

5. Concluding Remarks And Open Problems

5.1 The Main Problem

The main problem left open is to make closer the exponential gap between our bounds

2 ln n − O(1) ≤ M(n) ≤ (7 + o(1))\sqrt{n}.

Remark 4.4 shows that our method for upper bounding M(n) cannot do it better. As for possibilities to improve our lower bound, it is a question if one can improve the intermediate lower bound of Lemma 3.1.

5.2 An Observation

It turns out that if we impose some (strong at first sight) restrictions on the structure of V ⊆ ℤ^{2}, then the minimal possible value of MS(V) will not change much. We first prove the following auxiliary fact.

Lemma 5.1 Let V, U, and A be finite subsets of ℤ^{k}. Suppose that for any u ∈ U there is v ∈ V with u − v ∈ A. Then MS(V) ≥ MS(U)/|A|^{2}.

Proof. Fix a correspondence ϕ : U → V such that u − ϕ(u) ∈ A for all u. Let S be a symmetric subset of U containing MS(U) elements. Among all MS(U) ordered pairs (u_{1}, u_{2}) of symmetric points of S, let us consider those for which the pair (u_{1}−ϕ(u_{1}), u_{2}−ϕ(u_{2})) is the same. We can pick up at least MS(U)/|A|^{2} such pairs. The corresponding pairs (ϕ(u_{1}), ϕ(u_{2})) are clearly pairwise distinct and, moreover, have a common center g+ \frac{1}{2}(ϕ(u_{1})−u_{1})+ \frac{1}{2}(ϕ(u_{2})−u_{2}), where g is the center of symmetry of S. Therefore, they form a symmetric subset of V with at least MS(U)/|A|^{2} elements. □

As before, let a and b be arbitrary but fixed non-collinear vectors in ℤ^{2}. Define M′(n) to be the minimum of MS(U) over all subsets U = {u_{0}, v_{1}, …, u_{n}} of ℤ^{2} with each difference u_{i+1} − u_{i} in {a, b} and such that the underlying word w(U) does not contain subwords aa and bbb.

Proposition 5.2 \frac{1}{9}M′(2n − 1) ≤ M(n) ≤ M′(n).

Proof. The second inequality is trivial. To prove the first one, consider a set V = {v_{0}, v_{1}, …, v_{n}} of points of ℤ^{2} with each v_{i+1} − v_{i} either (1, 1) or (1, 2). Extend V to U = {u_{0}, u_{1}, …} inserting a new point v_{i} + (1, 0) between v_{i} and v_{i+1} with v_{i+1} − v_{i} = (1, 1) and two new points v_{i} + (1, 0) and v_{i+1} − (0, 1) between v_{i} and v_{i+1} with v_{i+1} − v_{i} = (1, 2). Notice that for any u_{j} there is v_{i} with u_{j} −v_{i} ∈ {(0, 0), (1, 0), (0, −1)}. By Lemma 5.1, MS(V) ≥ MS(U)/9. In its turn MS(U) ≥ M′(2n − 1), because difference between any two successive points of U is either a = (1, 0) or b = (0, 1), and word w(U) is free of subwords a^{2} and b^{3} and has length at least 2n − 1. The proposition follows. □

Similarly with item 3 of Lemma 1.1, M′(n) could be alternatively defined as the maximum m such that every binary word of length n without squares of one letter and cubes of another letter has abelian occurrence of a symmetric pattern of length at least m − 1. Proposition 5.2 shows that the function M(n) and its restricted version M′(n) have the same order of magnitude.

Question 5.3 Can prohibition of a^{2} and b^{3} help? Is estimating M′(n) somehow easier than estimating M(n)?

5.3 Higher Dimensions

The function M(n), if considered from the geometric point of view in accordance with item 2 of Lemma 1.1, admits a natural generalization. Given A ⊂ ℤ^{k}, define

M_{k,A}(n) = min {MS({v_{0}, v_{1}, …, v_{n}}) : v_{i} ∈ ℤ^{k}, v_{i+1} − v_{i} ∈ A} .

Remark 5.4 We assume that V = {v_{0}, v_{1}, …, v_{n}} is an (n + 1)-element set, or a sequence without self-crossing. Nevertheless, if we allow self-crossing and consider V to be multiset, then everything that is claimed below holds true under the suitable definition of a symmetric multisubset.

If A ⊂ ℤ^{k} is a linearly independent system of k vectors, then M_{k,A}(n) does not depend on the particular choice of A. In this case we will drop subscript A and write simply M_{k}(n). In this notation M(n) = M_{2}(n).

Define also L_{k}(n) to be the maximal l such that every word of length n over k letter alphabet has an abelian occurrence of a symmetric pattern of length at least l. The proof of Lemma 1.1 can be directly extended to show that

M_{k}(n) = L_{k}(n) + 1,
M_{k,A}(n) ≥ L_{|A|}(n) + 1 = M_{|A|}(n).  (12)

Let us focus on the case of difference set A_{c} = {v : 0 < ∥v∥ ≤ c}, where the norm ∥ · ∥ on ℤ^{k} is defined by ∥(z_{1}, …, z_{k})∥ = ∑_{i=1}^{k} |z_{i}|. As long as we are concerned with asymptotics in n and consider parameters k and c fixed, we may restrict our attention to the difference set A_{1}, consisting of k unit vectors of the standard basis and k more opposite vectors. We will not loose much, because

\frac{M_{k,A_{1}}(n)}{(2c + 1)^{2k}} ≤ M_{k,A_{c}}(n) ≤ M_{k,A_{1}}(n).

The first inequality follows from Lemma 5.1 (given a set V = {v_{0}, v_{1}, …, v_{n}} with difference set A_{c}, we extend it to a set U with difference set A_{1} inserting intermediate points between v_{i} and v_{i+1} whenever ∥v_{i+1} − v_{i}∥ > 1, and then relate MS(V) with MS(U)). To facilitate notation, denote M_{k}^{±}(n) = M_{k,A_{1}}(n). Notice relations

M_{2k}(n) ≤ M_{k}^{±}(n) ≤ M_{k}(n),

where the first inequality is true by (12).

If k > 2, all that we can say is that

M_{k}(n) → ∞ as n → ∞.  (13)

This fact is a consequence of inequalities M_{k}(n) > L_{k}(n) > L_{k}^{non−abel}(n), where L_{k}^{non−abel}(n) generalizes the function L^{non−abel}(n) introduced in Section 2 to the k-letter alphabet. Similarly with Lemma 2.3, if L_{k}^{non−abel}(n) ≥ l, then L_{k}^{non−abel}((n + 1)(k^{n} + 1)) ≥ 2l + 1. This results in a lower bound for M_{k}(n) that tends to the infinity but more slowly than the inverse tower function.

Question 5.5 Prove better (than the inverse tower function) lower bounds for M_{3}(n) and M_{2}^{±}(n).

Question 5.6 For k > 2 prove a better (than O(\sqrt{n})) upper bound for M_{k}(n).

Question 5.7 Try to prove a better (than O(\sqrt{n})) upper bound for M_{2}^{±}(n).

5.4 Odd Vs. Even Cardinality

Dekking [11] proves that in the binary alphabet there is an infinite word without abelian occurences of pattern x^{4} and that in the ternary alphabet there is an infinite word without abelian occurences of pattern x^{3}. Kera̋nen [17] reports a (computer aided) proof that in the 4letter alphabet there is an infinite word free of abelian occurences of pattern x^{2}. The latter result implies that there is an infinite sequence of points in ℤ^{4} with differences between consequtive points only (1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0), and (0, 0, 0, 1) and without symmetric subsets of odd cardinality (excepting singletons). At the same time by (13) it must contain arbitrarily long symmetric subsets of even cardinality.

Acknowledgments.

I am grateful to Taras Banakh, whose proof of Proposition 2.2 in geometric terms inspired this work, and to Oleg Pikhurko, whose observation improved the original proof of Theorem 3.2 and led to a better lower bound for M(n). I thank an anonymous referee for several corrections and useful expository suggestions.

References

[1] M. Ajtai, J. Komlós and E. Szemerédi. A dense infinite Sidon sequence. European J. Combin., 2:1–11, 1981.

[2] E. Bach and J. Shallit. Algorithmic number theory. Vol. 1, MIT Press, Cambridge, 1996.

[3] T. Banakh. On asymmetric colorings of Abelian groups. In: Paul Erdős and his Mathematics. Research Communications of the conference held in the memory of Paul Erdős, July 4–11, 1999, Budapest, Janos Bolyai Mathematical Society, 30–32.

[4] T. O. Banakh and I. V. Protasov. Asymmetric partitions of Abelian groups (in Russian). Mat. Zametki, 66(1):10–19, 1999.

[5] T. Banakh, I. Kmit, and O. Verbitsky. On asymmetric colorings of integer grids. September 1999, accepted for publication in Ars Combinatoria.

[6] R. C. Bose. An affine analogue of Singer’s theorem. J. Indian Math. Soc. (new series), 6:1–15, 1942.

[7] R. C. Bose and S. Chowla. Theorems in the additive theory of numbers. Comment. Math. Helv., 37:141–147, 1962.

[8] T. C. Brown. Variations on van der Waerden’s and Ramsey’s theorems. Am. Math. Mon., 82:993–995, 1975.

[9] S. Chowla. Solution of a problem of Erdős and Turan in additive number theory. Proc. Natl. Acad. Sci. India, 14:1–2, 1944.

[10] M. Coudrain and M. P. Schützenberger. Une condition de finitude des monoides finiment engendres. C. R. Acad. Sci., Paris, Ser. A, 262:1149–1151, 1966.

[11] F. M. Dekking. Strongly non-repetitive sequences and progression-free sets. J. Combin. Theory, 27:181–185, 1979.

[12] L. E. Dickson. Introduction to the theory of numbers. Dover Publ., New York, 1957.

[13] P. Erdős and P. Turan. On a problem of Sidon in additive number theory, and on some related problems. J. London Math. Soc., 16:212–215, 1941.

[14] P. Erdős. On a problem of Sidon in additive number theory and on some related problems. Addendum. J. London Math. Soc., 19:208, 1944.

[15] P. Erdős, message to A. Stöhr, published in: A. Stöhr, Gelöste und ungelöste Fragen über Basen der natürlichen Zahlenreihe. II. J. Reine Angew. Math., 194:132–133, 1955.

[16] W. L. Fouché. Unavoidable regularities and factor permutations of words. Proc. Royal Soc. Edinb., 125A(3):519–524, 1995.

[17] V. Kera̋nen. Abelian squares are avoidable on 4 letters. In: Proc. of ICALP’92, LNCS vol. 623, Springer, 41–52, 1992.

[18] G. Hoheisel. Primzahlprobleme in der Analysis. Sitzungsberichte der Preussischen Akademie der Wissenschaften, 573:580–588, 1930.

[19] F. Krückeberg. B_{2}-Folgen und verwandte Zahlenfolgen. J. Reine Angew. Math., 206:53–60, 1961.

[20] J.-L. Nicolas and G. Robin. Majorations explicites pour le nombre de diviseurs de N. Canad. Math. Bull., 26:485–492, 1983.

[21] C. Pomerance and A. Sárközy. Combinatorial number theory. In Handbook of Combinatorics, chapter 20, pages 967–1018. Elsevier Publ., 1995.

[22] C. Pomerance. Collinear subsets of lattice point sequences — an analog of Szemerédi’s theorem. J. Combin. Theory A, 28:140–149, 1980.

[23] L. T. Ramsey and J. L. Gerver. On certain sequences of lattice points. Pacific J. Math, 83:357–363, 1979.

[24] J. Singer. A theorem in finite projective geometry and some applications to number theory. Trans. Am. Math. Soc., 43:377–385, 1938.

[25] S. Wigert. Sur l’odre de grandeur du nombre des diviseurs d’un entier. Arkiv för Matematik, Astronomi och Fisik, 3(18):1–9, 1906–1907.