Ramseyan variations on symmetric subsequences

A theorem of Dekking in the combinatorics of words implies that there exists an injective order-preserving transformation f : {0, 1, . . . , n} → {0, 1, . . . , 2n} with the restriction f(i + 1) ≤ f(i) + 2 such that for every 5-term arithmetic progression P its image f(P) is not an arithmetic prog...

Full description

Saved in:

Bibliographic Details
Published in:	Algebra and Discrete Mathematics
Date:	2003
Main Author:	Verbitsky, O.
Format:	Article
Language:	English
Published:	Інститут прикладної математики і механіки НАН України 2003
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/154678
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Ramseyan variations on symmetric subsequences / O. Verbitsky // Algebra and Discrete Mathematics. — 2003. — Vol. 2, № 1. — С. 111–124. — Бібліогр.: 16 назв. — англ.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-154678
record_format	dspace
spelling	Verbitsky, O. 2019-06-15T17:45:34Z 2019-06-15T17:45:34Z 2003 Ramseyan variations on symmetric subsequences / O. Verbitsky // Algebra and Discrete Mathematics. — 2003. — Vol. 2, № 1. — С. 111–124. — Бібліогр.: 16 назв. — англ. 1726-3255 https://nasplib.isofts.kiev.ua/handle/123456789/154678 A theorem of Dekking in the combinatorics of words implies that there exists an injective order-preserving transformation f : {0, 1, . . . , n} → {0, 1, . . . , 2n} with the restriction f(i + 1) ≤ f(i) + 2 such that for every 5-term arithmetic progression P its image f(P) is not an arithmetic progression. In this paper we consider symmetric sets in place of arithmetic progressions and prove lower and upper bounds for the maximum M = M(n) such that every f as above preserves the symmetry of at least one symmetric set S ⊆ {0, 1, . . . , n} with \|S\| ≥ M. en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics Ramseyan variations on symmetric subsequences Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Ramseyan variations on symmetric subsequences
spellingShingle	Ramseyan variations on symmetric subsequences Verbitsky, O.
title_short	Ramseyan variations on symmetric subsequences
title_full	Ramseyan variations on symmetric subsequences
title_fullStr	Ramseyan variations on symmetric subsequences
title_full_unstemmed	Ramseyan variations on symmetric subsequences
title_sort	ramseyan variations on symmetric subsequences
author	Verbitsky, O.
author_facet	Verbitsky, O.
publishDate	2003
language	English
container_title	Algebra and Discrete Mathematics
publisher	Інститут прикладної математики і механіки НАН України
format	Article
description	A theorem of Dekking in the combinatorics of words implies that there exists an injective order-preserving transformation f : {0, 1, . . . , n} → {0, 1, . . . , 2n} with the restriction f(i + 1) ≤ f(i) + 2 such that for every 5-term arithmetic progression P its image f(P) is not an arithmetic progression. In this paper we consider symmetric sets in place of arithmetic progressions and prove lower and upper bounds for the maximum M = M(n) such that every f as above preserves the symmetry of at least one symmetric set S ⊆ {0, 1, . . . , n} with \|S\| ≥ M.
issn	1726-3255
url	https://nasplib.isofts.kiev.ua/handle/123456789/154678
citation_txt	Ramseyan variations on symmetric subsequences / O. Verbitsky // Algebra and Discrete Mathematics. — 2003. — Vol. 2, № 1. — С. 111–124. — Бібліогр.: 16 назв. — англ.
work_keys_str_mv	AT verbitskyo ramseyanvariationsonsymmetricsubsequences
first_indexed	2025-11-26T10:17:12Z
last_indexed	2025-11-26T10:17:12Z
_version_	1850620243280396288
fulltext	Jo ur na l A lg eb ra D is cr et e M at h.Algebra and Discrete Mathematics RESEARCH ARTICLE Number 2. (2003). pp. 111–124 c© Journal “Algebra and Discrete Mathematics” Ramseyan variations on symmetric subsequences Oleg Verbitsky Communicated by V. I. Sushchansky Abstract. A theorem of Dekking in the combinatorics of words implies that there exists an injective order-preserving trans- formation f : {0, 1, . . . , n} → {0, 1, . . . , 2n} with the restriction f(i + 1) ≤ f(i) + 2 such that for every 5-term arithmetic progres- sion P its image f(P ) is not an arithmetic progression. In this pa- per we consider symmetric sets in place of arithmetic progressions and prove lower and upper bounds for the maximum M = M(n) such that every f as above preserves the symmetry of at least one symmetric set S ⊆ {0, 1, . . . , n} with \|S\| ≥ M . 1. Introduction Let [n] = {0, 1, 2, . . . , n}, with 0 included for our convenience. We con- sider injective order-preserving transformations f : [n] → [2n] with re- striction 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. In the case of arithmetic progressions, it is easy to observe an equiva- lent reformulation of the question. Let V = {v0, . . . , vn} be a sequence of points in the grid Z2 with each difference vi+1−vi 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 An extended version of this paper has been published in INTEGERS: Electronic Journal of Combinatorial Number Theory. Jo ur na l A lg eb ra D is cr et e M at h.112 Ramseyan variations on symmetric subsequences 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). As the choice of the initial point v0 does not affect anything, a set V is characterized by the sequence of differences v1 − v0, . . . , vn − vn−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 xm 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 xM−1. Dekking [6] constructs an infinite word in the binary alphabet without abelian occurrences of x4. It immediately follows [13, 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 ⊆ Zk such that S = g − S for a lattice point g ∈ Zk is called symmetric (with respect to the center at rational point 1 2g). From now on the property P extended to being symmetric will be our main concern. Given V ⊆ Zk, 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) = minf :[n]→[2n] maxS⊆[n] { \|S\| : both S and f(S) are symmetric}, where the minimum is taken over all injective f with 1 ≤ f(i + 1) − f(i) ≤ 2 (1) for i < n. Jo ur na l A lg eb ra D is cr et e M at h.O. Verbitsky 113 2. M(n) is the minimum of MS(V ) over all subsets V = {v0, v1, . . . , vn} of Z2 with each vi+1 − vi 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 P1 = x, P2 = xyx, P3 = xyxzxyx, P4 = xyxzxyxuxyxzxyx, ... (2) where Pi+1 is the result of inserting a new variable between two copies of Pi. In combinatorics of words, members of this sequence are called sesquipowers or Zimin’s patterns. Coudrain and Schützenberger [5] proved that each Pi 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 un- avoidability 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) = Ω(lnn) 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( √ n). As the main technical tool we use B2-sequences introduced by Sidon and investigated by many authors (see [13, section 4.1] for survey and references). A set X of integers is called a B2-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 B2-sequence X is a highly asymmetric set characterized by MS(X) ≤ 2. There are several constructions of dense B2-sequences in [n]. We employ a fairly simple and explicit construction of [12], making use of an additional uniformity property of it. Jo ur na l A lg eb ra D is cr et e M at h.114 Ramseyan variations on symmetric subsequences Related work. The van der Waerden theorem can be restated so that every infinite subsequence v0, v1, . . . of N with vi+1 − vi = O(1) contains arbitrarily long arithmetic progressions (see [4]). As Dekking’s result shows, a similar statement in Z2 is false. However, Ramsey and Gerver [15] prove that every infinite sequence v0, v1, . . . in Z2 with bounded dis- tances \|\|vi+1−vi\|\| between any two successive points contains arbitrarily large subsets of collinear points. Pomerance [14] shows this holds true even under the weaker assumption that lim inf n→∞ 1 n n ∑ i=1 \|\|vi+1 − vi\|\| < ∞. (3) These results can be viewed as two-dimensional analogs of the van der Waerden theorem and its density version of Szemerédi, with collinear sub- sets instead of arithmetic progressions. In this respect our result on be- havior 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 ana- log of Szemerédi’s theorem is also true as shown by Banakh [3], who observed that condition (3) guarantees the existence of arbitrarily long symmetric subsequences in an infinite sequence v0, v1, . . . of points in Zk, 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 [2] prove that the minimal number of colors required for coloring the n-dimensional integer grid Zn avoiding infinite symmetric monochromatic subsets is n + 1. Unavoidable symmetries in words are investigated by Fouché [10]. 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 cardinal- ity 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 progres- sions. With a function f we associate its graph V = {v0, . . . , vn}, where vi = (i, f(i)). The bounds (1) imply that vi+1 − vi ∈ {a, b}. Vice versa, any set V = {v0, . . . , vn} in Z2 with the latter condition can be viewed as the graph of a function f of the prescribed kind. A set S ⊆ [n] and its Jo ur na l A lg eb ra D is cr et e M at h.O. Verbitsky 115 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 = {v0, . . . , vn} and V ′ = {v′0, . . . , v′n} in Z2 with all vi+1 − vi ∈ {(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 Z2 into itself that takes v0 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 {x1, x2, . . .}. Pattern xi1xi2 . . . xil is symmetric if ij = il+1−j for all j ≤ l. Let A = {a1, . . . , am} be a finite alphabet. The number of occurrences of letter ai in a word w is denoted by \|w\|ai . A commutative index of w over A is the tuple 〈\|w\|a1 , . . . , \|w\|am 〉. A subword u of a word w is an occurrence of a pattern P = xi1 . . . xil 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 a1a1a2a1a2a1a3, subwords a1a1, a1a2a1a2, and a2a1a2a1 are occurrences of pattern x1x1. In addition, a1a1a2a1a2a1 is an abelian occurrence of the same pattern. Given a sequence of vectors V = {v0, v1, . . . , vn} in Zk with all vi − vi−1 in a finite set A ⊂ Zk, we associate with V the sequence w(V ) of differences v1 − v0, v2 − v1, . . . , vk − vk−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 v1−v0, . . . , vn− vn−1. Given a subword u = vi+1 − vi . . . vj − vj−1, i < j, we call vi the initial point and vj the terminal point of u. Let u = u1 . . . ul be an abelian occurrence of a symmetric pattern P of length l, where us is Jo ur na l A lg eb ra D is cr et e M at h.116 Ramseyan variations on symmetric subsequences substituted in place of s-th variable of P . Let vis−1 and vis be the initial and terminal points of us. Then the set {vi0 , . . . , vil} is symmetric. This can be shown by easy induction. Really, assume that vi1 and vil−1 are symmetric with respect to the center 1 2g, that is, vi1 + vil−1 = g. As u1 and ul differ only in order of their letters, we have vi1 − vi0 = vil − vil−1 . Consequently, vi0 and vil are symmetric with respect to 1 2g too. 2. Let l = MS(V ) and vi0 , . . . , vil be a symmetric subsequence of V . Denote a subword of w(V ) whose initial and terminal points are vis−1 and vis by us. Then u = ui . . . ul is an abelian occurrence of a sym- metric pattern of length l. It suffices to show that commutative indices of words us and ul+1−s are the same. Those are uniquely determined by expansions of vectors vis − vis−1 and vil+1−s − vil−s in basis A. It remains to notice that the last two vectors are equal by symmetricalness of {vi0 , . . . , vil}. 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 Lnon−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) > Lnon−abel(n), it suffices to show that Lnon−abel(n) → ∞ for n → ∞. The latter follows from a result of Coudrain and Schützenberger [5] which we state below in a form conve- nient for our purposes. Lemma 2.3 ([5]). If Lnon−abel(n) ≥ l, then Lnon−abel((n+1)(2n +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)(2n+1) contains two identical subwords of length n separated by a nonempty word. Thus, there is an occurrence of the symmetric pattern PxP , where x is a new variable absent in P . Notice that the above argument ensures that each pattern Pi 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 Jo ur na l A lg eb ra D is cr et e M at h.O. Verbitsky 117 function. In this section we improve it to M(n) ≥ 2 lnn − 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 {u1, u2}, where u1 and u2 are disjoint subwords of w with the same com- mutative index. Let N(n) be the minimum of ν(w) over all binary words w of length n. Then N(n) ≥ (lnn − O(1))n2/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) ≥ 1 2 t ∑ i=0 σt(i)(σt(i) − (2t − 1)). Taking into account that t ∑ i=0 σt(i) 2 ≥ (t + 1) ( ∑t i=0 σt(i) t + 1 )2 , we conclude that νt(w) ≥ 1 2 ( (t + 1) ( n + 1 − t t + 1 )2 − (2t − 1)(n + 1 − t) ) = (n + 2)2 2(t + 1) − (t + 1 2 )(n + 1) + t2 − 1 2 . Let us sum these inequalities over t from 1 to s, dropping the last term t2− 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 ∑s t=1 1/t− ln s approaches Euler’s constant as s increases. Therefore, s ∑ t=1 νt(w) ≥ 1 2 (ln s − O(1))(n + 2)2 − s(s + 2) 2 (n + 1). Setting s = ⌈√n ⌉, we obtain the proclaimed bound for ν(w) and hence for N(n). Jo ur na l A lg eb ra D is cr et e M at h.118 Ramseyan variations on symmetric subsequences Theorem 3.2. M(n) ≥ 2 lnn − O(1). Proof. We adhere to the statement 2 of Lemma 1.1. Let V = {v0, v1, . . . , vn} be a set of points in Z2 with vi+1−vi ∈ {a, b}. Denote G = { 1 2(vi + vj) : 0 ≤ i ≤ j ≤ n } , the set of all potential centers of symmetry. Let mg denote the “multiplicity” of an element g in G, that is, the number of pairs (i, j) such that g = 1 2(vi + vj) and i ≤ j. Clearly, ∑ g∈G mg = (n + 1)(n + 2)/2. Furthermore, let N denote the total number of quadruples (vl, vi, vj , vk) with l < i ≤ j < k and vi − vl = vk − vj . (5) Clearly, N ≤ ∑ g∈G ( mg 2 ) (actually, the linear independence of a and b implies the equality here). It follows that N < 1 2 ∑ g∈G m2 g ≤ 1 2 (max g∈G mg) ∑ g∈G mg = 1 4 n2(1 + O( 1 n ))max g∈G mg. (6) Recall that with the set V we associate a word w(V ) over alpha- bet {a, b}. It is easy to observe a one-to-one correspondence between quadruples (5) in V and pairs of disjoint subwords u1 and u2 with the same commutative index in w(V ). By Lemma 3.1 we have N ≥ (lnn − O(1))n2/4. Together with (6), this gives max g∈G mg ≥ lnn − 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 2mg − 1 elements. 4. Upper bound In this section we prove an upper bound for M(n). Theorem 4.1. M(n) ≤ (7 + o(1)) √ n. Jo ur na l A lg eb ra D is cr et e M at h.O. Verbitsky 119 We use a two-dimensional geometric interpretation of M(n) given by statement 2 of Lemma 1.1. We will construct a set V = {v0, v1, . . . , vn} of points in Z2 such that each difference vi+1 − vi is either (1, 0) or (0, 1) and MS(V ) ≤ (7 + o(1)) √ n. Our construction will be completely determined by two sets of inte- gers X = {x1, . . . , xq} and Y = {y1, . . . , yq} listed in the ascending order. Given X and Y , consider a sequence of points in Z2 (x1, y1), (x2, y1), (x2, y2), (x3, y2), (x3, y3), . . . , (xq, yq) (7) We define V by V = V1 ∪ V2, where V1 = q ⋃ i=1 { (xi, y) : yi−1 < y ≤ yi} and V2 = q−1 ⋃ i=1 { (x, yi) : xi < x ≤ xi+1} (we set y0 = y1 − 1 for convenience). Thus, (7) are “corner” points of V , at which difference vi+1 − vi changes its value from (1, 0) to (0, 1) or vice versa. Clearly, V consists of xq + yq + 1 − x1 − y1 points. Given a set Z = {z1, . . . , zq} of integers listed in the ascending order, define D(Z) = max1≤i<q(zi+1 − zi). 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 1 2g, i.e. S = V ∩ (g − V ). Clearly, S = (V1 ∩ g − V1) ∪ (V2 ∩ g − V2) ∪ (V1 ∩ g − V2) ∪ (V2 ∩ g − V1). Let us estimate the cardinality of each member of the union. V1 ∩ g − V1 is a symmetric subset of V1. As the projection of V1 ∩ g − V1 onto the first coordinate is symmetric too, the cardinality of this projection does not exceed MS(X). As any cut of V1 by vertical line (i.e. along the second coordinate) containes at most D(Y ) points, we have \|V1 ∩ g − V1\| ≤ MS(X)D(Y ). Similarly, \|V2 ∩ g − V2\| ≤ MS(Y )D(X). Observe now that all points of V1 differ in the second coordinate and have only q values for the first coordinate, while all points of V2 differ in the first coordinate and have only q values for the second coordinate. As a consequence, both V1 ∩ g − V2 and V2 ∩ g − V1 have less than q points. The bound (8) follows. Jo ur na l A lg eb ra D is cr et e M at h.120 Ramseyan variations on symmetric subsequences 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 B2-sequence X = Y , which gives us the best possible MS(X) = MS(Y ) = 2. It easily follows from [8] that D(X) ≥ q(1 − o(1)) for any B2-sequence X = {x1, . . . , xq}. We use a construction of [12] that provides us with D(X) ≤ (3 + o(1))q. Lemma 4.3 (Krückeberg [12]). For any prime q there is a sequence of integers X = {x1, . . . , xq} with MS(X) = 2 and D(X) < 3q. Moreover, x1 = 0 and xq = 2q2 − 2q − 1. We include the proof of this lemma given in [12], because it contains a simple explicit construction of the needed B2-sequences, thereby making our construction of V explicit too. Proof. Set xi+1 = 2qi−(i2 mod q) for 0 ≤ i < q, where expression i2 mod q stands for the least non-negative residue of i2 modulo q. Obviously, q < xi+1 − xi < 3q. To show that X is a B2-sequence, assume that xi + xj = xi′ + xj′ , i ≤ j, i′ ≤ j′. It is easy to derive from this that { i + j = i′ + j′ (mod q) i2 + j2 = (i′)2 + (j′)2 (mod q) Since in the field Fq a system of kind { i + j = a i2 + j2 = b 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 = {v0, v1, . . . , vn}. Let q be the prime next to ( √ n + 3 + 1)/2 and X be the B2-set given by Lemma 4.3. Applying the construction described in the beginning of the section with Y = X, we obtain a set V ′ = {v0, v1, . . . , vn, . . .} of 4q2 − 4q − 1 ≥ n + 1 points in Z2. 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 [11], we have MS(V ) ≤ (7 + o(1)) √ n. The proof of Theorem 4.1 is complete. Remark 4.4. The choice of Krückeberg’s B2-sequence is essentially best possible, because the right hand side of (8) cannot be smaller than √ 2n, whatever sets X and Y are. Let us prove this fact. First, observe relation MS(X) ≥ q/D(X). (9) Jo ur na l A lg eb ra D is cr et e M at h.O. Verbitsky 121 for a set of integers X = {x1, . . . , xq}. This is a consequence of inclusion X ⊆ ⋃D(X)−1 g=0 (g + x1 + xq − 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 √ 2n. Remark 4.5. Consider a random set V = {v0, v1, . . . , vn} in Z2 with vi+1 − vi ∈ {a, b} for non-collinear a and b. We mean that the underly- ing 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 vm. 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 ∑k i=1 ξi = ∑k i=1 ζ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 pk = P [ ∑k i=1 ξi = ∑k i=1 ζi ] . By linearity of mathematical ex- pectation, E [t] = ∑m k=1 pk. Using Chernoff’s bound, we have pk = k ∑ l=0 P [ k ∑ i=1 ξi = l ]2 > ∑ k/2− √ k≤l≤k/2+ √ k P [ k ∑ i=1 ξi = l ]2 ≥ (2 √ k − 1)   P [ k/2 − √ k ≤ ∑k i=1 ξi ≤ k/2 + √ k ] 2 √ k + 1   2 ≥ ≥ (1 − 2 exp(−2))2 2 √ k + 7 . Therefore, E [t] = Ω ( ∑m k=1 1/ √ k ) = Ω( √ m). As E [s] = 2E [t] + 1, we conclude that the mean value of MS(V) is Ω( √ n). Jo ur na l A lg eb ra D is cr et e M at h.122 Ramseyan variations on symmetric subsequences In conclusion we discuss one more aspect of the upper bound proven in this section. Given n, we have constructed a set {v0, v1, . . . , vn} with MS({v0, v1, . . . , vn}) = O( √ n). (10) Question 4.6. Is it possible to construct an infinite set {v0, v1, v2 . . .} such that (10) is true for all n? We could achieve this goal with the same construction, if we had an infinite B2-sequence X = {x1, x2, . . .} with D({x1, . . . , xq}) = O(q) for all q. However, the latter condition implies \|X ∩ [m]\| = Ω( √ m) for all m, whereas no B2-sequence satisfies this condition by a result of Erdős. Erdős proves that there is a constant c such that for any infinite B2- sequence X the inequality \|X ∩ [m]\| ≤ c √ m/ lnm is true for infinitely many m (see [9]). The best known construction of [1] gives \|X ∩ [m]\| = Ω ( (m lnm)1/3 ) . Nevertheless, we are able at least to approach (10) with an infinite V . Proposition 4.7. There is an infinite sequence V = {v0, v1, v2, . . .} with each difference vi+1 − vi either (1, 0) or (0, 1) and such that MS({v0, v1, . . . , vn}) = n1/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 = 2q2 − 2 MS({v0, v1, . . . , vn}) < 2MS({1, 4, . . . , q2})D({1, 4, . . . , q2}) + 2q. We obviously have D({1, 4, . . . , q2}) = 2q − 1 and, by Lemma 4.8 below, MS({1, 4, . . . , q2}) = qO(1/ ln ln q). This proves (11) for all n = 2q2 − 2. Equality (11) is true for any other n as well, because the next to n number of kind 2q2 − 2 does not exceed n + √ (n + 2)/2 + 1 = n(1 + o(1)). The following lemma in other terms estimates the number of repre- sentations 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, . . . , q2}) = qO(1/ ln ln q). Jo ur na l A lg eb ra D is cr et e M at h.O. Verbitsky 123 Proof. It is easy to see that the maximum subset of {1, 4, . . . , q2} sym- metric with respect to 1 2g has as many elements as the number of so- lutions of equation z1 + z2 = g in {1, 4, . . . , q2}. The Jacobi theorem (see e.g. [7, theorem 65]) says that if g = 2km with odd m, then the total number of integer solutions of the equation x2 + y2 = 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 [16] that d(m) = mO(1/ ln ln m). As m ≤ g and it makes sense to consider only g < 2q2, we have d(m) = qO(1/ ln ln q). Summarizing, we obtain MS({1, 4, . . . , q2}) ≤ 4E ≤ 4d(m) = qO(1/ ln ln q). Acknowledgments I am grateful to Taras Banakh, whose proof of Proposition 2.2 in geomet- ric 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 of the electronic journal “INTEGERS” for several corrections. References [1] M. Ajtai, J. Komlós and E. Szemerédi. A dense infinite Sidon sequence. European J. Combin., 2:1–11, 1981. [2] T. O. Banakh and I. V. Protasov. Asymmetric partitions of Abelian groups (in Russian). Mat. Zametki, 66(1):10–19, 1999. [3] T. Banakh, I. Kmit, and O. Verbitsky. On asymmetric colorings of integer grids. Ars Combinatoria, 62:257–271, 2002. [4] T. C. Brown. Variations on van der Waerden’s and Ramsey’s theorems. Am. Math. Mon., 82:993–995, 1975. [5] M. Coudrain and M. P. Schützenberger. Une condition de finitude des monoides finiment engendres. C. R. Acad. Sci., Paris, Ser. A, 262:1149–1151, 1966. [6] F. M. Dekking. Strongly non-repetitive sequences and progression-free sets. J. Combin. Theory, 27:181–185, 1979. [7] L. E. Dickson. Introduction to the theory of numbers. Dover Publ., New York, 1957. [8] P. Erdő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. [9] P. Erdős, message to A. Stöhr, published in: A. Stöhr, Gelöste und ungelöste Fra- gen über Basen der natürlichen Zahlenreihe. II. J. Reine Angew. Math., 194:132– 133, 1955. [10] W. L. Fouché. Unavoidable regularities and factor permutations of words. Proc. Royal Soc. Edinb., 125A(3):519–524, 1995. [11] G. Hoheisel. Primzahlprobleme in der Analysis. Sitzungsberichte der Preussischen Akademie der Wissenschaften, 573:580–588, 1930. Jo ur na l A lg eb ra D is cr et e M at h.124 Ramseyan variations on symmetric subsequences [12] F. Krückeberg. B2-Folgen und verwandte Zahlenfolgen. J. Reine Angew. Math., 206:53–60, 1961. [13] C. Pomerance and A. Sárközy. Combinatorial number theory. In Handbook of Combinatorics, chapter 20, pages 967–1018. Elsevier Publ., 1995. [14] C. Pomerance. Collinear subsets of lattice point sequences — an analog of Sze- merédi’s theorem. J. Combin. Theory A, 28:140–149, 1980. [15] L. T. Ramsey and J. L. Gerver. On certain sequences of lattice points. Pacific J. Math, 83:357–363, 1979. [16] S. Wigert. Sur l’odre de grandeur du nombre des diviseurs d’un entier. Arkiv för Matematik, Astronomi och Fisik, 3(18):1–9, 1906–1907. Contact information O. Verbitsky Department of Algebra Faculty of Mechanics & Mathematics Kyiv National University Volodymyrska 60 01033 Kyiv, Ukraine E-Mail: oleg@ov.litech.net Received by the editors: 13.12.2002.

Ramseyan variations on symmetric subsequences

Institution

Similar Items