﻿ On the Modular Erdös-Burgess Constant

Open Journal of Discrete Mathematics
Vol.09 No.01(2019), Article ID:89631,6 pages
10.4236/ojdm.2019.91003

On the Modular Erdös-Burgess Constant

Jun Hao1, Haoli Wang2*, Lizhen Zhang1

1Department of Mathematics, Tianjin Polytechnic University, Tianjin, China

2College of Computer and Information Engineering, Tianjin Normal University, Tianjin, China    Received: August 16, 2018; Accepted: December 26, 2018; Published: December 29, 2018

ABSTRACT

Let n be a positive integer. For any integer $a$ , we say that $a$ is idempotent modulo n if ${a}^{2}\equiv a\left(\mathrm{mod}n\right)$ . The n-modular Erdös-Burgess constant is the smallest positive integer $\mathcal{l}$ such that any $\mathcal{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.

Keywords:

Erdös-Burgess Constant, Davenport Constant, Modular Erdös-Burgess Constant 1. Introduction

Let $\mathcal{S}$ be a finite multiplicatively written commutative semigroup with identity ${1}_{\mathcal{S}}$ . By a sequence over $\mathcal{S}$ , we mean a finite unordered sequence of terms from $\mathcal{S}$ where repetition is allowed. For a sequence T over $\mathcal{S}$ we denote by $\pi \left(T\right)\in \mathcal{S}$ the product of its terms and we say that T is a product-one sequence if $\pi \left(T\right)={1}_{\mathcal{S}}$ . If $\mathcal{S}$ is a finite abelian group, the Davenport constant $\text{D}\left(\mathcal{S}\right)$ of $\mathcal{S}$ is the smallest positive integer $\mathcal{l}$ such that every sequence T over $\mathcal{S}$ of length $|T|\ge \mathcal{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      for work in the setting of abelian groups, to   for work in case of non-abelian groups, and to      for work in commutative semigroups).

In the present paper we study the Erdös-Burgess constant $\text{I}\left(\mathcal{S}\right)$ of $\mathcal{S}$ which is defined as the smallest positive integer $\mathcal{l}$ such that every sequence T over $\mathcal{S}$ of length $|T|\ge \mathcal{l}$ has a non-empty subsequence ${T}^{\prime }$ whose product $\pi \left({T}^{\prime }\right)$ is an idempotent of $\mathcal{S}$ . Clearly, if $\mathcal{S}$ happens to be a finite abelian group, then the unique idempotent of $\mathcal{S}$ is the identity ${1}_{\mathcal{S}}$ , whence $\text{I}\left(\mathcal{S}\right)=\text{D}\left(\mathcal{S}\right)$ . The study of $\text{I}\left(\mathcal{S}\right)$ for general semigroups is initiated by a question of Erdös and has found renewed attention in recent years (e.g.,      ). For a commutative unitary ring R, let ${\mathcal{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 ${\mathcal{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

$\text{I}\left({\mathcal{S}}_{R}\right)\ge \text{D}\left({R}^{×}\right)+\Omega \left(n\right)-\omega \left(n\right),$

where $\Omega \left(n\right)$ is the number of primes occurring in the prime-power decomposition of n counted with multiplicity, and $\omega \left(n\right)$ 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 $\mathcal{S}$ be a finite multiplicatively written commutative semigroup with the binary operation *. An element $a$ of $\mathcal{S}$ is said to be idempotent if $a\ast a=a$ . Let $\text{E}\left(\mathcal{S}\right)$ be the set of idempotents of $\mathcal{S}$ . We introduce sequences over semigroups and follow the notation and terminology of Grynkiewicz and others (cf.  , Chapter 10] or   ). Sequences over $\mathcal{S}$ are considered as elements in the free abelian monoid $\mathcal{F}\left(\mathcal{S}\right)$ with basis $\mathcal{S}$ . In order to avoid confusion between the multiplication in $\mathcal{S}$ and multiplication in $\mathcal{F}\left(\mathcal{S}\right)$ , we denote multiplication in $\mathcal{F}\left(\mathcal{S}\right)$ by the boldsymbol $\cdot$ and we use brackets for all exponentiation in $\mathcal{F}\left(\mathcal{S}\right)$ . In particular, a sequence $\mathcal{S}\in \mathcal{F}\left(\mathcal{S}\right)$ has the form

$T={a}_{1}{a}_{2}\cdot \cdots \cdot {a}_{\mathcal{l}}=\underset{i\in \left[1,\mathcal{l}\right]}{•}{a}_{i}=\underset{a\in \mathcal{S}}{•}{a}^{\left[{\text{v}}_{a}\left(T\right)\right]}\in \mathcal{F}\left(\mathcal{S}\right)$ (1)

where ${a}_{1},\cdots ,{a}_{\mathcal{l}}\in \mathcal{S}$ are the terms of T, and ${\text{v}}_{a}\left(T\right)$ is the multiplicity of the term a in T. We call $|T|=\mathcal{l}=\underset{a\in \mathcal{S}}{\sum }{\text{v}}_{a}\left(T\right)$ the length of T. Moreover, if ${T}_{1},{T}_{2}\in \mathcal{F}\left(\mathcal{S}\right)$ and ${a}_{1},{a}_{2}\in \mathcal{S}$ , then ${T}_{1}\cdot {T}_{2}\in \mathcal{F}\left(\mathcal{S}\right)$ has length $|{T}_{1}|+|{T}_{2}|,{T}_{1}\cdot {a}_{1}\in \mathcal{F}\left(\mathcal{S}\right)$ has length $|{T}_{1}|+1$ , ${a}_{1}\cdot {a}_{2}\in \mathcal{F}\left(\mathcal{S}\right)$ is a sequence of length 2. If $a\in \mathcal{S}$ and $k\in {ℕ}_{0}$ , then ${a}^{\left[k\right]}=\underset{k}{\underset{︸}{a\cdot \cdots \cdot a}}\in \mathcal{F}\left(\mathcal{S}\right)$ . Any sequence ${T}_{1}\in \mathcal{F}\left(\mathcal{S}\right)$ is called a subsequence of T if ${\text{v}}_{a}\left({T}_{1}\right)\le {\text{v}}_{a}\left(T\right)$ for every element $a\in \mathcal{S}$ , denoted ${T}_{1}|T$ . In particular, if ${T}_{1}\ne T$ , we call ${T}_{1}$ a proper subsequence of T, and let $T\cdot {T}_{1}^{\left[-1\right]}$ denote the resulting sequence by removing the terms of ${T}_{1}$ from T.

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

$\pi \left(T\right)={a}_{1}\ast \cdots \ast {a}_{\mathcal{l}}$ is the product of all terms of T, and

$\prod \left(T\right)=\left\{{\prod }_{j\in J}\text{ }{a}_{j}:\varnothing \ne J\subset \left[1,\mathcal{l}\right]\right\}\subset \mathcal{S}$ is the set of subsequence products of T.

We say that T is

・ a product-one sequence if $\pi \left(T\right)={1}_{\mathcal{S}}$ ,

・ an idempotent-product sequence if $\pi \left(T\right)\in \text{E}\left(\mathcal{S}\right)$ ,

・ product-one free if ${1}_{\mathcal{S}}\notin \prod \left(T\right)$ ,

・ idempotent-product free if $\text{E}\left(\mathcal{S}\right)\cap \prod \left(T\right)=\varnothing$ .

Let $n>1$ be an integer. For any integer $a$ , we denote $\stackrel{¯}{a}$ the congruence class of $a$ modulo n. Any integer $a$ is said to be idempotent modulo n if $aa\equiv a\left(\mathrm{mod}n\right)$ , i.e., $\stackrel{¯}{a}\stackrel{¯}{a}=\stackrel{¯}{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}^{\prime }$ with $\pi \left({T}^{\prime }\right)$ 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 $\underset{a|T}{•}\stackrel{¯}{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}}\cdots {p}_{r}^{{k}_{r}}$ be a positive integer where $r\ge 1$ , ${k}_{1},{k}_{2},\cdots ,{k}_{r}\ge 1$ , and ${p}_{1},{p}_{2},\cdots ,{p}_{r}$ are distinct primes. For any integer $a$ , the congruence ${a}^{2}\equiv a\left(\mathrm{mod}n\right)$ holds if and only if $a\equiv 0\left(\mathrm{mod}{p}_{i}^{{k}_{i}}\right)$ or $a\equiv 1\left(\mathrm{mod}{p}_{i}^{{k}_{i}}\right)$ for every $i\in \left[1,r\right]$ .

Proof. Noted that ${a}^{2}\equiv a\left(\mathrm{mod}n\right)$ if and only if ${p}_{i}^{{k}_{i}}$ divides $a\left(a-1\right)$ for all $i\in \left[1,r\right]$ , since $\mathrm{gcd}\left(a,a-1\right)=1$ , it follows that ${a}^{2}\equiv a\left(\mathrm{mod}n\right)$ holds if and only if ${p}_{i}^{{k}_{i}}$ divides $a$ or $a-1$ , i.e., $a\equiv 0\left(\mathrm{mod}{p}_{i}^{{k}_{i}}\right)$ or $a\equiv 1\left(\mathrm{mod}{p}_{i}^{{k}_{i}}\right)$ for every $i\in \left[1,r\right]$ , completing the proof.

Proof of Theorem 1. 1. Say

$n={p}_{1}^{{k}_{1}}{p}_{2}^{{k}_{2}}\cdots {p}_{r}^{{k}_{r}},$ (2)

where ${p}_{1},{p}_{2},\cdots ,{p}_{r}$ are distinct primes and ${k}_{i}\ge 1$ for all $i\in \left[1,r\right]$ . It is observed that

$\Omega \left(n\right)=\underset{i=1}{\overset{r}{\sum }}\text{ }{k}_{i}$ (3)

and

$\omega \left(n\right)=r.$ (4)

taking a sequence V of integers of length $\text{D}\left({R}^{×}\right)-1$ such that

$\underset{a|V}{•}\stackrel{¯}{a}\in \mathcal{F}\left({R}^{×}\right)$ (5)

and

$\stackrel{¯}{1}\notin \prod \left(\underset{a|V}{•}\stackrel{¯}{a}\right).$ (6)

Now we show that the sequence $V\cdot \left(\underset{i\in \left[1,r\right]}{•}{p}_{i}^{\left[{k}_{i}-1\right]}\right)$ is idempotent-product free modulo n, supposing to the contrary that $V\cdot \left(\underset{i\in \left[1,r\right]}{•}{p}_{i}^{\left[{k}_{i}-1\right]}\right)$ contains a nonempty subsequence W, say $W={V}^{\prime }\cdot \left(\underset{i\in \left[1,r\right]}{•}{p}_{i}^{\left[{\beta }_{i}\right]}\right)$ , such that $\pi \left(W\right)$ is idempotent modulo n, where ${V}^{\prime }$ is a subsequence of V and

${\beta }_{i}\in \left[0,{k}_{i}-1\right]\text{ }\text{\hspace{0.17em}}\text{for}\text{\hspace{0.17em}}\text{all}\text{\hspace{0.17em}}\text{ }i\in \left[1,r\right].$

It follows that

$\pi \left(W\right)=\pi \left({V}^{\prime }\right){p}_{1}^{{\beta }_{1}}\cdots {p}_{r}^{{\beta }_{r}}.$ (7)

If $\underset{i=1}{\overset{r}{\sum }}\text{ }{\beta }_{i}=0$ , then $W={V}^{\prime }$ is a nonempty subsequence of V. By (5) and (6), there exists some $t\in \left[1,r\right]$ such that $\pi \left(W\right)\overline{)\equiv }0\left(\mathrm{mod}{p}_{t}^{{k}_{t}}\right)$ and $\pi \left(W\right)\overline{)\equiv }1\left(\mathrm{mod}{p}_{t}^{{k}_{t}}\right)$ . By Lemma 3.1, $\pi \left(W\right)$ is not idempotent modulo n, a contradiction. Otherwise, ${\beta }_{j}>0$ for some $j\in \left[1,r\right]$ , say

${\beta }_{1}\in \left[1,{k}_{1}-1\right].$ (8)

Since $\mathrm{gcd}\left(\pi \left({V}^{\prime }\right),{p}_{1}\right)=1$ , it follows from (7) that $\mathrm{gcd}\left(\pi \left(W\right),{p}_{1}^{{k}_{1}}\right)={p}_{1}^{{\beta }_{1}}$ . Combined with (8), we have that $\pi \left(W\right)\overline{)\equiv }0\left(\mathrm{mod}{p}_{1}^{{k}_{1}}\right)$ and $\pi \left(W\right)\overline{)\equiv }1\left(\mathrm{mod}{p}_{1}^{{k}_{1}}\right)$ . By Lemma 3.1, we conclude that $\pi \left(W\right)$ is not idempotent modulo n, a contradiction. This proves that the sequence $V\cdot \left(\underset{i\in \left[1,r\right]}{•}{p}_{i}^{\left[{k}_{i}-1\right]}\right)$ is idempotent-product free modulo n. Combined with (3) and (4), we have that

$\text{I}\left({\mathcal{S}}_{R}\right)\ge |V\cdot \left(\underset{i\in \left[1,r\right]}{•}{p}_{i}^{\left[{k}_{i}-1\right]}\right)|+1=\left(|V|+1\right)+\underset{i=1}{\overset{r}{\sum }}\left({k}_{i}-1\right)=\text{D}\left({R}^{×}\right)+\Omega \left(n\right)-\omega \left(n\right).$ (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}=\cdots ={k}_{r}=1$ in (2). It remains to show the equality $\text{I}\left({\mathcal{S}}_{R}\right)=\text{D}\left({R}^{×}\right)+\Omega \left(n\right)-\omega \left(n\right)$ 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|=\text{D}\left({R}^{×}\right)+{k}_{1}-1=\text{D}\left({R}^{×}\right)+\Omega \left(n\right)-\omega \left(n\right)$ , let ${T}_{1}=\underset{\stackrel{a|T}{a\equiv 0\left(\mathrm{mod}{p}_{1}\right)}}{•}a$ and ${T}_{2}=T\cdot {T}_{1}^{\left[-1\right]}$ . By the Pigeonhole Principle, we see that either $|{T}_{1}|\ge {k}_{1}$ or $|{T}_{2}|\ge \text{D}\left({R}^{×}\right)$ . It follows either $\pi \left({T}_{1}\right)\equiv 0\left(\mathrm{mod}{p}_{1}^{{k}_{1}}\right)$ , or $\stackrel{¯}{1}\in {\prod }_{}\left(\underset{a|{T}_{2}}{•}\stackrel{¯}{a}\right)$ . By Lemma 3.1, the sequence T is not idempotent-product free modulo n, which implies that $\text{I}\left({\mathcal{S}}_{R}\right)\le \text{D}\left({R}^{×}\right)+\Omega \left(n\right)-\omega \left(n\right)$ . Combined with (9), we have that $\text{I}\left({\mathcal{S}}_{R}\right)=\text{D}\left({R}^{×}\right)+\Omega \left(n\right)-\omega \left(n\right).$

Case 2. ${k}_{1}=\cdots ={k}_{r}=1$ in (2), i.e., $n={p}_{1}{p}_{2}\cdots {p}_{r}$ .

Then

$\Omega \left(n\right)=\omega \left(n\right)=r.$ (10)

Taking an arbitrary sequence T of integers of length $|T|=\text{D}\left({R}^{×}\right)$ , by the Chinese Remainder Theorem, for any term $a$ of T we can take an integer ${a}^{\prime }$ such that for each $i\in \left[1,r\right]$ ,

${a}^{\prime }\equiv \left\{\begin{array}{ll}1\left(\mathrm{mod}{p}_{i}\right)\hfill & \text{if}\text{\hspace{0.17em}}a\equiv 0\left(\mathrm{mod}{p}_{i}\right);\hfill \\ a\left(\mathrm{mod}{p}_{i}\right)\hfill & \text{otherwise}.\hfill \end{array}$ (11)

Note that $\mathrm{gcd}\left({a}^{\prime },n\right)=1$ and thus $\underset{a|T}{•}{\stackrel{¯}{a}}^{\prime }\in \mathcal{F}\left({R}^{×}\right)$ . Since $|\underset{a|T}{•}{\stackrel{¯}{a}}^{\prime }|=|T|=\text{D}\left({R}^{×}\right)$ , it follows that $\stackrel{¯}{1}\in {\prod }_{}\left(\underset{a|T}{•}{\stackrel{¯}{a}}^{\prime }\right)$ , and so there exists a nonempty subsequence W of T such that $\underset{a|W}{\prod }{a}^{\prime }\equiv 1\left(\mathrm{mod}{p}_{i}\right)$ for each $i\in \left[1,r\right]$ . Combined with (11), we derive that $\pi \left(W\right)\equiv 0\left(\mathrm{mod}{p}_{i}\right)$ or $\pi \left(W\right)\equiv 1\left(\mathrm{mod}{p}_{i}\right)$ , where $i\in \left[1,r\right]$ . By Lemma 3.1, we conclude that $\pi \left(W\right)$ is idempotent modulo n. Combined with (10), we have that $\text{I}\left({\mathcal{S}}_{R}\right)\le \text{D}\left({R}^{×}\right)=\text{D}\left({R}^{×}\right)+\Omega \left(n\right)-\omega \left(n\right)$ . It follows from (9) that $\text{I}\left({\mathcal{S}}_{R}\right)=\text{D}\left({R}^{×}\right)+\Omega \left(n\right)-\omega \left(n\right)$ , 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 $\text{I}\left({\mathcal{S}}_{R}\right)=\text{D}\left({R}^{×}\right)+\Omega \left(n\right)-\omega \left(n\right)$ .

Acknowledgements

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

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

Cite this paper

Hao, J., Wang, H.L. and Zhang, L.Z. (2019) On the Modular Erdös-Burgess Constant. Open Journal of Discrete Mathematics, 9, 11-16. https://doi.org/10.4236/ojdm.2019.91003

References

1. 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. 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. 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. 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. 5. Tao, T. and Van Vu, H. (2006) Additive Combinatorics. Cambridge University Press, Cambridge. https://doi.org/10.1017/CBO9780511755149

6. 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. 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. 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. 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. 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. 11. Wang, G. and Gao, W. (2016) Davenport Constant of the Multiplicative Semigroup of the Ring . arXiv:1603.06030

12. 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. 13. Burgess, D.A. (1969) A Problem on Semi-Groups. Studia Sci. Math. Hungar., 4, 9-11.

14. 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. 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. 16. Wang, G. (2018) Erdos-Burgess Constant of the Direct Product of Cyclic Semigroups. arXiv:1802.08791.

17. 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. 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