OJDM  Vol.9 No.1 , January 2019
On the Modular Erdös-Burgess Constant
ABSTRACT
Let n be a positive integer. For any integer a, we say that is idempotent modulo n if a2≡a(mod n). The n-modular Erdös-Burgess constant is the smallest positive integer l such that any l integers contain one or more integers, whose product is idempotent modulo n. We gave a sharp lower bound of the n-modular Erdös-Burgess constant, in particular, we determined the n-modular Erdös-Burgess constant in the case when n was a prime power or a product of pairwise distinct primes.

1. Introduction

Let S be a finite multiplicatively written commutative semigroup with identity 1 S . By a sequence over S , we mean a finite unordered sequence of terms from S where repetition is allowed. For a sequence T over S we denote by π ( T ) S the product of its terms and we say that T is a product-one sequence if π ( T ) = 1 S . If S is a finite abelian group, the Davenport constant D ( S ) of S is the smallest positive integer l such that every sequence T over S of length | T | l has a nonempty product-one subsequence. The Davenport constant has mainly been studied for finite abelian groups but also in more general settings (we refer to [1] [2] [3] [4] [5] for work in the setting of abelian groups, to [6] [7] for work in case of non-abelian groups, and to [8] [9] [10] [11] [12] for work in commutative semigroups).

In the present paper we study the Erdös-Burgess constant I ( S ) of S which is defined as the smallest positive integer l such that every sequence T over S of length | T | l has a non-empty subsequence T whose product π ( T ) is an idempotent of S . Clearly, if S happens to be a finite abelian group, then the unique idempotent of S is the identity 1 S , whence I ( S ) = D ( S ) . The study of I ( S ) for general semigroups is initiated by a question of Erdös and has found renewed attention in recent years (e.g., [13] [14] [15] [16] [17] ). For a commutative unitary ring R, let S R be the multiplicative semigroup of the ring R, and R × the group of units of R, noticing that the group R × is a subsemigroup of the semigoup S R . We state our main result.

Theorem 1.1. Let n > 1 be an integer, and let R = n be the ring of integers modulon. Then

I ( S R ) D ( R × ) + Ω ( n ) ω ( n ) ,

where Ω ( n ) is the number of primes occurring in the prime-power decomposition of n counted with multiplicity, and ω ( n ) is the number of distinct primes. Moreover, if n is a prime power or a product of pairwise distinct primes, then equality holds.

2. Notation

Let S be a finite multiplicatively written commutative semigroup with the binary operation *. An element a of S is said to be idempotent if a a = a . Let E ( S ) be the set of idempotents of S . We introduce sequences over semigroups and follow the notation and terminology of Grynkiewicz and others (cf. [4] , Chapter 10] or [6] [18] ). Sequences over S are considered as elements in the free abelian monoid F ( S ) with basis S . In order to avoid confusion between the multiplication in S and multiplication in F ( S ) , we denote multiplication in F ( S ) by the boldsymbol and we use brackets for all exponentiation in F ( S ) . In particular, a sequence S F ( S ) has the form

T = a 1 a 2 a l = i [ 1, l ] a i = a S a [ v a ( T ) ] F ( S ) (1)

where a 1 , , a l S are the terms of T, and v a ( T ) is the multiplicity of the term a in T. We call | T | = l = a S v a ( T ) the length of T. Moreover, if T 1 , T 2 F ( S ) and a 1 , a 2 S , then T 1 T 2 F ( S ) has length | T 1 | + | T 2 | , T 1 a 1 F ( S ) has length | T 1 | + 1 , a 1 a 2 F ( S ) is a sequence of length 2. If a S and k 0 , then a [ k ] = a a k F ( S ) . Any sequence T 1 F ( S ) is called a subsequence of T if v a ( T 1 ) v a ( T ) for every element a S , denoted T 1 | T . In particular, if T 1 T , we call T 1 a proper subsequence of T, and let T T 1 [ 1 ] denote the resulting sequence by removing the terms of T 1 from T.

Let T be a sequence as in (1). Then

π ( T ) = a 1 a l is the product of all terms of T, and

( T ) = { j J a j : J [ 1, l ] } S is the set of subsequence products of T.

We say that T is

・ a product-one sequence if π ( T ) = 1 S ,

・ an idempotent-product sequence if π ( T ) E ( S ) ,

・ product-one free if 1 S ( T ) ,

・ idempotent-product free if E ( S ) ( T ) = .

Let n > 1 be an integer. For any integer a , we denote a ¯ the congruence class of a modulo n. Any integer a is said to be idempotent modulo n if a a a ( mod n ) , i.e., a ¯ a ¯ = a ¯ in n . A sequence T of integers is said to be idempotent-product free modulo n provided that T contains no nonempty subsequence T with π ( T ) being idempotent modulo n. We remark that saying a sequence T of integers is idempotent-product free modulo n is equivalent to saying the sequence a | T a ¯ is idempotent-product free in the multiplicative semigroup of the ring n .

3. Proof of Theorem 1.1

Lemma 3.1. Let n = p 1 k 1 p 2 k 2 p r k r be a positive integer where r 1 , k 1 , k 2 , , k r 1 , and p 1 , p 2 , , p r are distinct primes. For any integer a , the congruence a 2 a ( mod n ) holds if and only if a 0 ( mod p i k i ) or a 1 ( mod p i k i ) for every i [ 1, r ] .

Proof. Noted that a 2 a ( mod n ) if and only if p i k i divides a ( a 1 ) for all i [ 1, r ] , since gcd ( a , a 1 ) = 1 , it follows that a 2 a ( mod n ) holds if and only if p i k i divides a or a 1 , i.e., a 0 ( mod p i k i ) or a 1 ( mod p i k i ) for every i [ 1, r ] , completing the proof.

Proof of Theorem 1. 1. Say

n = p 1 k 1 p 2 k 2 p r k r , (2)

where p 1 , p 2 , , p r are distinct primes and k i 1 for all i [ 1, r ] . It is observed that

Ω ( n ) = i = 1 r k i (3)

and

ω ( n ) = r . (4)

taking a sequence V of integers of length D ( R × ) 1 such that

a | V a ¯ F ( R × ) (5)

and

1 ¯ ( a | V a ¯ ) . (6)

Now we show that the sequence V ( i [ 1, r ] p i [ k i 1 ] ) is idempotent-product free modulo n, supposing to the contrary that V ( i [ 1, r ] p i [ k i 1 ] ) contains a nonempty subsequence W, say W = V ( i [ 1, r ] p i [ β i ] ) , such that π ( W ) is idempotent modulo n, where V is a subsequence of V and

β i [ 0, k i 1 ] for all i [ 1, r ] .

It follows that

π ( W ) = π ( V ) p 1 β 1 p r β r . (7)

If i = 1 r β i = 0 , then W = V is a nonempty subsequence of V. By (5) and (6), there exists some t [ 1, r ] such that π ( W ) 0 ( mod p t k t ) and π ( W ) 1 ( mod p t k t ) . By Lemma 3.1, π ( W ) is not idempotent modulo n, a contradiction. Otherwise, β j > 0 for some j [ 1, r ] , say

β 1 [ 1, k 1 1 ] . (8)

Since gcd ( π ( V ) , p 1 ) = 1 , it follows from (7) that gcd ( π ( W ) , p 1 k 1 ) = p 1 β 1 . Combined with (8), we have that π ( W ) 0 ( mod p 1 k 1 ) and π ( W ) 1 ( mod p 1 k 1 ) . By Lemma 3.1, we conclude that π ( W ) is not idempotent modulo n, a contradiction. This proves that the sequence V ( i [ 1, r ] p i [ k i 1 ] ) is idempotent-product free modulo n. Combined with (3) and (4), we have that

I ( S R ) | V ( i [ 1, r ] p i [ k i 1 ] ) | + 1 = ( | V | + 1 ) + i = 1 r ( k i 1 ) = D ( R × ) + Ω ( n ) ω ( n ) . (9)

Now we assume that n is a prime power or a product of pairwise distinct primes, i.e., either r = 1 or k 1 = = k r = 1 in (2). It remains to show the equality I ( S R ) = D ( R × ) + Ω ( n ) ω ( n ) holds. We distinguish two cases.

Case 1. r = 1 in (2), i.e., n = p 1 k 1 .

Taking an arbitrary sequence T of integers of length | T | = D ( R × ) + k 1 1 = D ( R × ) + Ω ( n ) ω ( n ) , let T 1 = a 0 ( mod p 1 ) a | T a and T 2 = T T 1 [ 1 ] . By the Pigeonhole Principle, we see that either | T 1 | k 1 or | T 2 | D ( R × ) . It follows either π ( T 1 ) 0 ( mod p 1 k 1 ) , or 1 ¯ ( a | T 2 a ¯ ) . By Lemma 3.1, the sequence T is not idempotent-product free modulo n, which implies that I ( S R ) D ( R × ) + Ω ( n ) ω ( n ) . Combined with (9), we have that I ( S R ) = D ( R × ) + Ω ( n ) ω ( n ) .

Case 2. k 1 = = k r = 1 in (2), i.e., n = p 1 p 2 p r .

Then

Ω ( n ) = ω ( n ) = r . (10)

Taking an arbitrary sequence T of integers of length | T | = D ( R × ) , by the Chinese Remainder Theorem, for any term a of T we can take an integer a such that for each i [ 1, r ] ,

a { 1 ( mod p i ) if a 0 ( mod p i ) ; a ( mod p i ) otherwise . (11)

Note that gcd ( a , n ) = 1 and thus a | T a ¯ F ( R × ) . Since | a | T a ¯ | = | T | = D ( R × ) , it follows that 1 ¯ ( a | T a ¯ ) , and so there exists a nonempty subsequence W of T such that a | W a 1 ( mod p i ) for each i [ 1, r ] . Combined with (11), we derive that π ( W ) 0 ( mod p i ) or π ( W ) 1 ( mod p i ) , where i [ 1, r ] . By Lemma 3.1, we conclude that π ( W ) is idempotent modulo n. Combined with (10), we have that I ( S R ) D ( R × ) = D ( R × ) + Ω ( n ) ω ( n ) . It follows from (9) that I ( S R ) = D ( R × ) + Ω ( n ) ω ( n ) , completing the proof.

We close this paper with the following conjecture.

Conjecture 3.2. Let n > 1 be an integer, and let R = n be the ring of integers modulo n. Then I ( S R ) = D ( R × ) + Ω ( n ) ω ( n ) .

Acknowledgements

This work is supported by NSFC (Grant No. 61303023, 11301381, 11501561).

Cite this paper
Hao, J. , Wang, H. and Zhang, L. (2019) On the Modular Erdös-Burgess Constant. Open Journal of Discrete Mathematics, 9, 11-16. doi: 10.4236/ojdm.2019.91003.
References
[1]   Gao, W. and Geroldinger, A. (2006) Zero-Sum Problems in Finite Abelian Groups: A Survey. Expositiones Mathematicae, 24, 337-369.
https://doi.org/10.1016/j.exmath.2006.07.002

[2]   Geroldinger, A. and Halter-Koch, F. (2006) Non-Unique Factorizations. Algebraic, Combinatorial and Analytic Theory. Pure Appl. Math., Vol. 278, Chapman & Hall/CRC.

[3]   Geroldinger, A. and Ruzsa, I. (2009) Combinatorial Number Theory and Additive Group Theory. In Advanced Courses in Mathematics CRM Barcelona, Springer, Birkhauser.
https://doi.org/10.1007/978-3-7643-8962-8

[4]   Grynkiewicz, D.J. (2013) Structural Additive Theory, Developments in Mathematics. Vol. 30, Springer, Cham.
https://doi.org/10.1007/978-3-319-00416-7

[5]   Tao, T. and Van Vu, H. (2006) Additive Combinatorics. Cambridge University Press, Cambridge.
https://doi.org/10.1017/CBO9780511755149

[6]   Cziszter, K., Domokos, M. and Geroldinger, A. (2016) The Interplay of Invariant Theory with Multiplicative Ideal Theory and with Arithmetic Combinatorics, Multiplicative Ideal Theory and Factorization Theory. Springer, Berlin, 43-95.

[7]   Gao, W., Li, Y. and Peng, J. (2014) An Upper Bound for the Davenport Constant of Finite Groups. Journal of Pure and Applied Algebra, 218, 1838-1844.
https://doi.org/10.1016/j.jpaa.2014.02.009

[8]   Wang, G. (2015) Davenport Constant for Semigroups II. Journal of Number Theory, 153, 124-134.
https://doi.org/10.1016/j.jnt.2015.01.007

[9]   Wang, G. (2017) Additively Irreducible Sequences in Commutative Semigroups. Journal of Combinatorial Theory, Series A, 152, 380-397.
https://doi.org/10.1016/j.jcta.2017.07.001

[10]   Wang, G. and Gao, W. (2008) Davenport Constant for Semigroups. Semigroup Forum, 76, 234-238.
https://doi.org/10.1007/s00233-007-9019-3

[11]   Wang, G. and Gao, W. (2016) Davenport Constant of the Multiplicative Semigroup of the Ring . arXiv:1603.06030

[12]   Zhang, L., Wang, H. and Qu, Y. (2017) A Problem of Wang on Davenport Constant for the Multiplicative Semigroup of the Quotient Ring of . Colloquium Mathematicum, 148, 123-130.
https://doi.org/10.4064/cm6707-6-2016

[13]   Burgess, D.A. (1969) A Problem on Semi-Groups. Studia Sci. Math. Hungar., 4, 9-11.

[14]   Gillam, D.W.H., Hall, T.E. and Williams, N.H. (1972) On Finite Semigroups and Idempotents. Bulletin of the London Mathematical Society, 4, 143-144.
https://doi.org/10.1112/blms/4.2.143

[15]   Wang, G. (2019) Structure of the Largest Idempotent-Product Free Sequences in Semigroups. Journal of Number Theory, 195, 84-95.
https://doi.org/10.1016/j.jnt.2018.05.020

[16]   Wang, G. (2018) Erdos-Burgess Constant of the Direct Product of Cyclic Semigroups. arXiv:1802.08791.

[17]   Wang, H., Hao, J. and Zhang, L. (2018) On the Erdos-Burgess Constant of the Multiplicative Semigroup of a Factor Ring of . International Journal of Number Theory. (To Appear)

[18]   Grynkiewicz, D.J. (2013) The Large Davenport Constant II: General Upper Bounds. Journal of Pure and Applied Algebra, 217, 2221-2246.
https://doi.org/10.1016/j.jpaa.2013.03.002

 
 
Top