Semigroups with the Erdös-Turán Property

Semigroups with the Erd˝os-Tur´an Property J. Neˇsetˇril Department of Applied Mathematics Institute of Theoretical Computer Science (ITI) Charles University, Praha [email protected] and O. Serra∗ Dept. Applied Mathematics IV Polytechnical University of Catalonia, Barcelona [email protected]c.es Abstract A set Xin a semigroup Ghas the Erd˝os-Tur´an property ET if, for any basis Aof X, the representation function rAis ubounded, where rA(x) counts the number of representations of xas a product two elements in A. We show that, under some conditions, operations on binary vectors whose value at each coordinate depends only on neighbouring coordinates of the factors give rise to semigroups with the ET –property. In particular countable powers of semigroups with no mutually inverse elements have the ET –property. As a consequence, for each kthere is N(k) such that, for every finite subset Xof a group Gwith X∩X−1={1}, the representation function of every basis of XN⊂GN,N≥N(k), is not bounded by k. This is in contrast with the known fact that each p–elementary group admits a basis of the whole group whose representation function is bounded by an absolute constant. 1 Introduction Let (G, ∗) be a set with a binary operation and X⊂G. A subset A⊂Xis abasis of Xif X⊂A∗A. When Xis an infinite set, Ais an asymptotic ∗Supported by the Spanish Research Council under project BFM2002-00412 1 basis if X\(A∗A) is finite. For g∈Gwe denote by rA(g) the number of pairs (a, a0)∈A×Asuch that g=a∗a0. The function rAis the representation function of A. Given a positive integer k, we say that Xhas the k-Erd˝os-Tur´an property ET(k) if, for any base Aof X, there is an element x∈Xwith rA(x)≥k. We say that Xhas the Erd˝os-Tur´an property ET if it has ET(k) for every k∈N. A famous conjecture of Erd˝os and Tur´an [5] formulated in 1942 states that the set of positive integers with addition has the ET property. The conjecture was proved to be true for the class of so-called d-bounded additive basis of N, see [10]. However it is still wide open in its general formulation. Erd˝os showed that the function rA(n) can have logarithmic growth. Ruzsa [12] gives a construction of a base Afor which the number of representations is bounded in the square mean. These results indicate the difficulties involved in the conjecture and leads to the consideration of the problem in other semigroups. The situation for the integers with multiplication is different. Erd˝os [1] proved in 1964 that (N,·) does have the ET property. Neˇsetˇril and R¨odl [9] gave a simple proof of this result by using Ramsey Theorem. Puˇs [11] extended this result by showing that an abelian semigroup with an infinite set of primes and a finite number of units has the ET property. On the negative side, it is not difficult to show that the group of integers with addition has basis with unique representation (up to commutativity), a result which can be extended to any abelian free group. Nathanson [8] even showed that the direct product of a countable semigroup with an infinite abelian group Gsuch that {12g;g∈G}is infinite, admits an asymptotic base whose representation function can be arbitrarily prescribed. Ruzsa [12] shows that, for any prime psuch that 2 is a square, there are bases of Zp×Zpwhose representation function is bounded by 18. This result has been recently extended by Haddad and Helou [6] to the additive group of F×Ffor any finite field Fof odd order. These authors also show [7] that there is an absolute constant Csuch that no cyclic group has the property ET(k) for k > C. In particular, the p–elementary groups with p > 2 do not have the ET(k)–property for k > 18C. In this paper we place the Ramsey argument of [9] in a natural broader setting by considering operations in the set of binary vectors. We show that locally bounded operations, a notion explained in Section 2, on binary 2 vectors of length Ndo have the ET(k) property for each positive integer k and large enough N. This result allows one to show that several classes of semigroups have the ET property. Among these there are the class of direct products of semigroups with no mutually inverse elements, the class of finite or cofinite sets of a countable set with union, or the class {(Nk,+), k ∈N} of powers of Nwith componentwise addition. As a consequence of these results, combined with the negative results for abelian groups mentioned above, we can formulate the following statement: Theorem 1 Let Gbe a group of prime order p > 2and ka positive integer. Let R⊂Gsuch that R∩(−R) = {0}. There is N(k)such that RN⊂GN has the ET(k)property for each N≥N(k), while GNhas basis Awith representation function bounded by 18C. Theorem 1 shows that there are abelian groups which admit basis with bounded representation function, while containing asymmetric subsets with the ET property. The Erd˝os–Tur´an conjecture says that this is the case for the group of integers. 2 Locally bounded operations on binary vectors Let BN={0,1}Ndenote the set of all binary vectors of length N. We denote by s(x) the support of vector x∈BN, that is, the set of nonzero coordinates of x. We denote by BNthe set of infinite binary sequences with finite support. Given a nonnegative integer rwe denote by Ir= [−r, r] the integer interval of length 2r+ 1 centered at 0. The r–neighborhood of a subset U⊂[1, N] is defined as the set (U)r= (Si∈U(i+Ir)) ∩[1, N].For a vector x∈BNwe denote by (x)U= (xi;i∈U) the vector of length |U|of the entries of xin U. Let α:N0→N0be a function. A binary operation ‘∗’ defined in BNis said to be α–locally bounded if, for every three vectors x, x0, y, and every i, 1≤i≤N, the following conditions hold: if (x)(i)r= (x0)(i)rthen also (x∗y)i= (x0∗y)i,(1) if (x)(i)r= (0,· · · ,0) then (x∗y)i= (y∗x)i,(2) s(x∗y)⊂(s(x)∪s(y))rand s(x)∪s(y)⊂(s(x∗y))r.(3) 3 where r=α(|s(x∗y)|). Condition (1) says that the i–th coordinate of x∗y depends only on the coordinates of xand yin the r–neighborhood of i. This is the essential property of a locally bounded operation. Condition (3) specifies that the r–neighborhood of a coordinate iin x∗yis the zero vector only if both xand yhave zero entries in the iterated r–neighborhood of i, while (2) states that the zero vector commutes ‘locally’ with every vector. Theorem 2 Let kbe a positive integer and α:N0→N0a function. There is N(k, α)such that (BN,∗)has the ET(k)–property for every α–locally bounded operation ‘∗’ on BNand all N≥N(k, α). Proof. Given k, let t=dlog2k+1eand set r=α(t). Define N=N(k, α) = (5r+1)(R(2t2, t, 2t(2r+1))+2), where R(m, t, l) denotes the Ramsey number which ensures the existence of an homogeneous subset of [1, R(m, t, l)] of cardinality mall of whose t-subsets are monochromatic for any coloring of the t-subsets with lcolors. Let Abe a basis of (BN,∗). Take the subset Y⊂[1, N] of multiples of 5rif r≥1 and Y= [1, N] if r= 0. Define a coloring cof the t-subsets of Yas follows. Given a t–subset X={i1< i2<· · · < it}, let xbe the vector with the support X. Choose a pair y, z ∈Asuch that x=y∗z. By (3) we have s(x)⊂(s(y)∪s(z))r. Since two consecutive elements in s(x) are at least at distance 4r+ 1, we can choose one of yand z, say y, such that s(y) intersects at least t/2 of the disjoint intervals (i1)r,(i2)r, . . . , (it)r. Color Xby the binary vector of length rt given by c(X) = ((y)(i1)r,(y)(i2)r, . . . , (y)(it)r). By (3) again, we have s(y)⊂(s(x))r, so that this coloring gives an encoding of yexcept that we do not keep track of the position of its support in [1, N]. Since Ais a base, cis a coloring of all t-subsets of Yand it uses at most 2t(2r+1) colors. By the definition of N, there is a subset Z⊂Yof cardinality |Z|= 2t2all of whose t-subsets have the same color u= (u1, u2, . . . , utr). Let u(1) = (u1, . . . , ur), u(2) = (ur+1, . . . u2r), . . . , u(t)= (u(t−1)r+1, . . . utr). By the construction of the coloring, at least t/2 of the vectors u(1), u(2), . . . , u(t) have nonempty support. Let u(i1), u(i2), . . . , u(is)be these vectors. Choose a subset J={j1< j2<· · · < j2s} ⊂ Zof cardinality 2ssuch that there are at least telements of Zbetween two consecutive elements of J. 4 Denote by Ji={j2i−1, j2i}, 1 ≤i≤s. Recall that, by the choice of Y, every two consecutive elements in Jare at distance at least t(4r+ 1). Let K={k1<· · · < ks}be a s-subset of Jobtained by picking one element in each Ji. Since there are telements of Zbetween any two consecutive elements in J, this set can be completed to a t-subset by inserting an element from Z\Jin each position isuch that u(i)is the zero vector. In other words, we construct a t-set K0={k0 1,···< k0 t} ⊂ Zsuch that k0 il=klfor l= 1, . . . s. Since Zis an homogeneous set, the vector a=a(K)∈BNwhose support is contained in (K)rand (a)(K)r= (u(i1), u(i2), . . . , u(is)) belongs to the base A. By the same argument, the similarly defined vector a(J\K) also belongs to the base. Denote by b(K) the vector which coincides with a(K) on the r–neighborhood of Kand with a(J\K) in the r–neighborhood of J\Kand has zero coordinates elsewhere (this is a correct definition as in our situation these r–neighborhoods are pairwise disjoint.) We have (b(K))(J)r= (u(i1), u(i1), u(i2), u(i2), . . . , u(is), u(is)). By (3), the support of a(K)∗a(J\K) is contained in the r–neighborhood of s(b(K)) = s(a(K)) ∪s(a(J\K)). This r–neighborhood is a subset of ((J)r)r. Since two consecutive elements in Jare at least at distance 4r+ 1, the set (s(b(K)))ris again the disjoint union of the r–neighborhoods of each element in s(b(K)). Let K0⊂Jbe another choice of a s–subset with exactly one element in each Ji. The vectors a(K) and a(K0) differ in the r–neighborhood of the symmetric difference K∆K0. On the other hand, b(K) = b(K0). By (1) and (2), for each coordinate iin the r–neighborhood of (K0∆K)rwe have ((a(K0)∗a(J\K0))i= ((a(J\K)∗a(K))i= (a(K)∗(a(J\K))i, while for the remaining coordinates in ((J)r)r, we have ((a(K0)∗a(J\K0))i= ((a(K)∗a(J\K))i. Therefore a(K0)∗a(J\K0) = a(K)∗a(J\K). There are 2s−1choices leading to different pairs of vectors {a(K), a(J\K)}. Hence, for u=a(K)∗a(J\K), we have rA(u)≥2t/2−1≥k. This completes the proof. 5 3 Semigroups with the Erd˝os–Tur´an property Let (G, ∗) be a semigroup with a distinguished idempotent element e∈G which commutes with every element in G. We say that a subset R⊂G is antisymmetric if e∈Rand the equation x∗y=eholds for x, y ∈Rif and only if x=y=e. We will consider the direct product GN. By the support of an vector g∈Gnwe mean the set of coordinates of gwhich are different from e. We denote by GNthe set of infinite sequences of elements of Gwith finite support, where the product is defined componentwise. As a direct application of Theorem 2 we have the following result. Theorem 3 Let (G, ∗)be a semigroup and e∈Gan idempotent element which commutes with every element in G. Let Rbe a finite antisymmetric set of a semigroup with |R|>1. For each positive integer kthere is N(k) such that RNhas the ET(k)property for all N≥N(k). In particular, RN has the ET property. Proof. Define an encoding φof the elements of Rby binary vectors of length m=dlog2|R|e such that φ(e) = (0,· · · ,0) and φ(x) = (0, . . . , 0,1) for some element x6=ein R. Let B0 Nm = (φ(R))N⊂BNm and define an operation in B0 Nm according to the operation in G, that is, for x, y ∈B0 Nm, (x∗y)[(i−1)r+1,ir]=φ(φ−1(x)[(i−1)r+1,ir]∗φ−1(y)[(i−1)r+1,ir])i= 1,2, . . . , m. In this way we have a locally bounded operation in B0 Nm with α(t) = mt. Indeed, condition (1) is verified by definition, condition (3) follows from the asymmetry of Rand (2) holds since ecommutes with every element in G. We can now apply the proof of Theorem 2 even if the operation is not defined for all vectors in BNm: all vectors whose support lies in the set Y⊂[1, Nm] of coordinates multiple of 5rin that proof do belong to φ({e, x})N⊂B0 Nm, and we only use the fact that each of these vectors belong to A∗Afor any base A, which is the case in our present situation. This shows that GN has the ET(k) property for N≥(5mt + 1)(R(2t2, t, 2t(2mt+1)) + 2) where t=dlog2k+ 1e. The result follows for RNsince each of its basis contains a base of RNfor every N. The positive part of Theorem 1 follows from Theorem 3 by taking an antisymmetric set in Z/pZ. 6 Let Gbe a class of semigroups and Ra family of subsets of ∪G∈GG. We say that Rhas the ET–property if for every kthere is N(k) such that every member R∈ R with |R| ≥ N(k) has the ET (k)–property. As a specialization of Theorem 3 we have the following examples of semigroups with the Erd˝os-Tur´an property. Corollary 1 The following classes have the ET property. 1. {(PN,∨), N ∈N}and (PN,∨), where Pis a finite semilattice with supremum and with a minimum element. 2. The family of finite (or cofinite) subsets of a countable set Xwith respect to union, (2X,∪), and with respect to intersection, (2X,∩). 3. {([0, m]N,+), N ∈N}and ([0, m]N,+), where [0, m]is the interval of integers 0≤i≤mand the sum is componentwise. 4. {(NN,+), N ∈N}and (NN,+), where the sum is componentwise. Proof. For {(PN,∨), N ∈N}and for (PN,∨), the conditions of Theorem 3 are satisfied with R=Pand ethe minimum element of P. In particular, for P={0,1}with the usual supremum function, (Pk,∨) corresponds to the family of subsets of [1, N] with union and (PN,∨) to the family of finite subsets of an infinite countable set. By taking complements we get the result for cofinite sets with intersection. To prove (2) it remains to show that the class of finite subsets of Nwith intersection does have the ET–property. Let Abe a basis of (2N,∩) and Xa nonempty set in A. Since for each integer nthe set X∪ {n}must be obtained as the intersection of two sets in A, there are infinitely many sets in Acontaining Xand, for each such set Y,Xitself can be written as X∩Y. Part (3) follows directly from Theorem 3 with R= [0, m]. Finally, (4) follows from (3) since every base of (Nk,+) contains a base of [0, m]kfor each m≥1. Note that the multiplicative semigroup of the positive integers can be viewed as (NN,+) by considering a vector (xi, i ∈N) with finite support as the integer Qi∈Npxi iwhere p1, p2, . . . is the sequence of prime numbers. Thus Corollary 1 (4) includes the result that (N,·) has the ET property. 7 4 Final remarks The condition in Theorem 3 that the set Ris antisymmetric is essential for the proof. Although we were always more interested in the positive results (i.e. structures with the ET property) we add a few examples in the opposite direction. We say that a basis Aof an abelian semigroup (G, ∗) is a unique representation basis if every element g∈Gcan be uniquely represented in A∗A(up to commutativity.) A simple greedy algorithm produces unique representation basis of GNfor certain semigroups with units. Proposition 1 Let (G, ∗)be an abelian semigroup with identity eand a, b ∈ G\ {e}two distinct elements such that a∗b=eand a2, b2and 0are pairwise distinct. Let R⊂Gcontaining a, b and e. Then RNhas unique representation basis. Proof. Take a linear ordering in Rand consider the following ordering in RN:x≤yif and only if either max s(x)<max s(y) or max s(x) = max s(y) = mand xis smaller than yin lexicographic order. Construct recursively a basis Aas follows. Let A0={e}. For each i > 0, let gbe the minimum element which is not in Ai∗Ai. Let mithe largest element in the support of elements in (Ai∗Ai)∪ {g}. Let gacoincide with gexcept that the (mi+ 1)–th coordinate of gais a. Let all the coordinates of gbbe eexcept (gb)mi+1 =b. Now define Ai+1 =Ai∪ {ga, gb}. We have g∈Ai+1 ∗Ai+1. Moreover, if every element in Ai∗Aican be uniquely expressed, then the same is true in Ai+1 ∗Ai+1 since each product involving any of the two new elements takes a different value on the (mi+1)- th coordinate. Therefore, A=∪i∈NAiis a unique representation basis. A similar argument as in the above proof shows that finitely generated free groups do not have the ET–property. Proposition 2 Let Xbe a finite set. The free group F(X)generated by X does not have the ET property. Proof. Consider the Cayley graph Γ of F(X) with respect to X. Order the elements of F(X) by its distance to the identity ein Γ and lexicographically within a sphere of radius kwith respect to some ordering of the elements in X. 8 As in Proposition 1, construct recursively a basis A. Let A0={e}. For each i > 0, let gbe the minimum element which is not in Ai∗Ai. Let kbe the largest distance to ein Γ (Ai∗Ai)∪ {g}. Let g1=gx2k+1 and g2=x−2k−1. Now define Ai+1 =Ai∪ {g1, g2}. We have g=g1g2∈Ai+1 ∗Ai+1 and any product involving any of the two new elements is at distance at least k+ 1 from ein Γ. Therefore, A=∪i∈NAiis a unique representation basis. On the other hand, the problem for free semigroups is as hard as for additive basis of positive integers. Proposition 3 Let Xbe a finite set. The free semigroup FS(X)generated by Xhas the ET–property if and only if (N,+) has the ET–property. Proof. For the if part, note that any base Aof FS(X) contains a base of the semigroup generated by a single element, which is isomorphic to (N,+). Suppose now that FS(X) has the ET–property. For every base A⊂N consider the set A0of words in Nwhose lengths belong to A,A0={w∈ F(X) : |w| ∈ A}. This is clearly a base of FS(X). If w=x1∗y1=· · · = xk∗ykare kdifferent representations of a word w∈FS(X) in elements of the basis A0, then |x1|+|y1|=· · · =|xk|+|yk|are kdifferent representations of |w|in elements of A. This shows the only if part. We have dealt with basis of order two. More generally, for an integer h≥2, a subset A⊂Xis a basis of Xof order hif X⊂A∗A∗ · · · ∗ A | {z } h =Ah. Accordingly we say that Xhas the ETh(k) property if, for every base of order h, there is an element in Xwith at least krepresentations in Ah. If X has ETh(k) for every k∈Nthen we say that it has the EThproperty. The proof of Theorem 2 can be easily extended to prove the following statement. Theorem 4 Let h≥2and kbe positive integers and α:N0→N0an arbitrary function. There is N(h, k, α)such that (BN,∗)has the ETh(k)– property for every α–locally bounded operation ‘∗’ on BNand all N≥ N(h, k, α). In particular, RNhas the ETh(k)–property for every antisymmetric set Rwith respect to ein a semigroup G, where eis an idempotent element commuting with all elements in R, and all Nlarge enough. In connection with the Erd˝os-Newman problem (cf. [3]) we may ask the following question. Let Abe a basis with unbounded representation function 9