On the Modular Erdös-Burgess Constant

Jun Hao¹, Haoli Wang^2*, Lizhen Zhang¹

¹Department of Mathematics, Tianjin Polytechnic University, Tianjin, China.
²College of Computer and Information Engineering, Tianjin Normal University, Tianjin, China.

DOI: 10.4236/ojdm.2019.91003                

Abstract

Let n be a positive integer. For any integer a, we say that is idempotent modulo n if a²≡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.

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 $\left|T\right|\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 [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 $\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 $\left|T\right|\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., [13] [14] [15] [16] [17] ). For a commutative unitary ring R, let ${\mathcal{S}}_R$ be the multiplicative semigroup of the ring R, and $R^{\times }$ the group of units of R, noticing that the group $R^{\times }$ 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={\mathbb{Z}}_n$ be the ring of integers modulon. Then

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

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. [4] , Chapter 10] or [6] [18] ). 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[\mathrm{1,}\mathcal{l}\right]}{{\displaystyle •}}{a}_i=\underset{a\in \mathcal{S}}{{\displaystyle •}}{a}^{\left[{\text{v}}_a\left(T\right)\right]}\in \mathcal{F}\left(\mathcal{S}\right)$ (1)

where $a_1\mathrm{,}\cdots \mathrm{,}{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 $\left|T\right|=\mathcal{l}={\displaystyle \underset{a\in \mathcal{S}}{\sum }}{\text{v}}_a\left(T\right)$ the length of T. Moreover, if $T_1\mathrm{,}{T}_2\in \mathcal{F}\left(\mathcal{S}\right)$ and $a_1\mathrm{,}{a}_2\in \mathcal{S}$ , then $T_1\cdot T_2\in \mathcal{F}\left(\mathcal{S}\right)$ has length $\left|T_1\right|+\left|T_2\right|\mathrm{,}{T}_1\cdot a_1\in \mathcal{F}\left(\mathcal{S}\right)$ has length $\left|T_1\right|+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 {\mathbb{N}}_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

・ ${\displaystyle \prod }\left(T\right)=\left\{{\displaystyle {\prod }_{j\in J}}{a}_j\mathrm{<mo>\; :\; </mo>}\varnothing \ne J\subset \left[\mathrm{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 {\displaystyle \prod }\left(T\right)$ ,

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

Let $n>1$ be an integer. For any integer $a$ , we denote $\bar{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., $\bar{a}\bar{a}=\bar{a}$ in ${\mathbb{Z}}_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}{{\displaystyle •}}\bar{a}$ is idempotent-product free in the multiplicative semigroup of the ring ${\mathbb{Z}}_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\mathrm{,}{k}_2\mathrm{,}\cdots \mathrm{,}{k}_r\ge 1$ , and $p_1\mathrm{,}{p}_2\mathrm{,}\cdots \mathrm{,}{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[\mathrm{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[\mathrm{1,}r\right]$ , since $\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[\mathrm{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\mathrm{,}{p}_2\mathrm{,}\cdots \mathrm{,}{p}_r$ are distinct primes and $k_i\ge 1$ for all $i\in \left[\mathrm{1,}r\right]$ . It is observed that

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

and

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

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

$\underset{a|V}{{\displaystyle •}}\bar{a}\in \mathcal{F}\left(R^{\times }\right)$ (5)

and

$\bar{1}\notin {\displaystyle \prod }\left(\underset{a|V}{{\displaystyle •}}\bar{a}\right)\mathrm{.}$ (6)

Now we show that the sequence $V\cdot \left(\underset{i\in \left[\mathrm{1,}r\right]}{{\displaystyle •}}{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[\mathrm{1,}r\right]}{{\displaystyle •}}{p}_i^{\left[k_i-1\right]}\right)$ contains a nonempty subsequence W, say $W=V^{\prime }\cdot \left(\underset{i\in \left[\mathrm{1,}r\right]}{{\displaystyle •}}{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[\mathrm{0,}{k}_i-1\right]\text{for}\text{all}i\in \left[\mathrm{1,}r\right]\mathrm{.}$

It follows that

$\pi \left(W\right)=\pi \left(V^{\prime }\right)p_1^{{\beta }_1}\cdots p_r^{{\beta }_r}.$ (7)

If ${\displaystyle \underset{i=1}{\overset{r}{\sum }}}{\beta }_i=0$ , then $W=V^{\prime }$ is a nonempty subsequence of V. By (5) and (6), there exists some $t\in \left[\mathrm{1,}r\right]$ such that $\pi \left(W\right)\cancel{\equiv }0\left(\mathrm{mod}{p}_t^{k_t}\right)$ and $\pi \left(W\right)\cancel{\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[\mathrm{1,}r\right]$ , say

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

Since $\gcd \left(\pi \left(V^{\prime }\right)\mathrm{,}{p}_1\right)=1$ , it follows from (7) that $\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)\cancel{\equiv }0\left(\mathrm{mod}{p}_1^{k_1}\right)$ and $\pi \left(W\right)\cancel{\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[\mathrm{1,}r\right]}{{\displaystyle •}}{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 \left|V\cdot \left(\underset{i\in \left[\mathrm{1,}r\right]}{{\displaystyle •}}{p}_i^{\left[k_i-1\right]}\right)\right|+1=\left(\left|V\right|+1\right)+{\displaystyle \underset{i=1}{\overset{r}{\sum }}}\left(k_i-1\right)=\text{D}\left(R^{\times }\right)+\Omega \left(n\right)-\omega \left(n\right)\mathrm{.}$ (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^{\times }\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 $\left|T\right|=\text{D}\left(R^{\times }\right)+k_1-1=\text{D}\left(R^{\times }\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)}}{{\displaystyle •}}a$ and $T_2=T\cdot T_1^{\left[-1\right]}$ . By the Pigeonhole Principle, we see that either $\left|T_1\right|\ge k_1$ or $\left|T_2\right|\ge \text{D}\left(R^{\times }\right)$ . It follows either $\pi \left(T_1\right)\equiv 0\left(\mathrm{mod}{p}_1^{k_1}\right)$ , or $\bar{1}\in {\displaystyle {\prod }_{}}\left(\underset{a|T_2}{{\displaystyle •}}\bar{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^{\times }\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^{\times }\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 $\left|T\right|=\text{D}\left(R^{\times }\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[\mathrm{1,}r\right]$ ,

$a^{\prime }\equiv \{\begin{array}{ll}1\left(\mathrm{mod}{p}_i\right)\hfill & \text{if}a\equiv 0\left(\mathrm{mod}{p}_i\right)\mathrm{<mo>\; ;\; </mo>}\hfill \\ a\left(\mathrm{mod}{p}_i\right)\hfill & \text{otherwise}\mathrm{.}\hfill \end{array}$ (11)

Note that $\gcd \left(a^{\prime },n\right)=1$ and thus $\underset{a|T}{{\displaystyle •}}{\bar{a}}^{\prime }\in \mathcal{F}\left(R^{\times }\right)$ . Since $\left|\underset{a|T}{{\displaystyle •}}{\bar{a}}^{\prime }\right|=\left|T\right|=\text{D}\left(R^{\times }\right)$ , it follows that $\bar{1}\in {\displaystyle {\prod }_{}}\left(\underset{a|T}{{\displaystyle •}}{\bar{a}}^{\prime }\right)$ , and so there exists a nonempty subsequence W of T such that ${\displaystyle \underset{a|W}{\prod }}{a}^{\prime }\equiv 1\left(\mathrm{mod}{p}_i\right)$ for each $i\in \left[\mathrm{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[\mathrm{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^{\times }\right)=\text{D}\left(R^{\times }\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^{\times }\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\mathrm{<mo>\; =\; </mo>}{\mathbb{Z}}_n$ be the ring of integers modulo n. Then $\text{I}\left({\mathcal{S}}_R\right)=\text{D}\left(R^{\times }\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.

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