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 $\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.

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