A generalization of Kruyswijk-Olson theorem on Davenport constant in commutative semigroups

1.   Introduction

Let $G$ be a finite abelian group written additively. The Davenport constant of $G$, denoted ${\rm D}(G)$, is defined as the smallest positive integer $\ell$ such that every sequence of terms from $G$ of length at least $\ell$ must contain one or more terms with the sum being the identity element of $G$. This invariant was popularized by H. Davenport in the 1960's, notably for its link with algebraic number theory (as reported in ^[21]), and has been investigated extensively in the past over 50 years. This combinatorial invariant was found with applications in other areas, including Factorization Theory of Algebra (see ^[5,12,13]), Classical Number Theory, Graph Theory, and Coding Theory. For example, the Davenport constant has been applied by W.R. Alford, A. Granville and C. Pomerance ^[1] to prove that there are infinitely many Carmichael numbers, by N. Alon ^[2] to prove the existence of regular subetaaphs, and by L.E. Marchan, O. Ordaz, I. Santos and W.A. Schmid ^[19] to establish a link between variant Davenport constants and problems of linear codes. What is more important, a lot of researches were motivated by the Davenport constant together with the celebrated EGZ Theorem obtained by P. Erdős, A. Ginzburg and A. Ziv ^[9] in 1961 on additive properties of sequences in groups, which have been developed into a branch, called zero-sum theory (see ^[11] for a survey), in Combinatorial Number Theory.

As a consequence of the Fundamental Theorem for finite abelian groups, any nontrivial finite abelian group can be written as the direct sum $\mathbb{Z}_{n_1}\oplus\cdots\oplus \mathbb{Z}_{n_r}$ of cyclic groups $\mathbb{Z}_{n_1}, \ldots, \mathbb{Z}_{n_r}$ with $1 < n_1 \mid \cdots \mid n_r$. D. Kruyswijk ^[7] and J.E. Olson ^[22] independently proved the crucial inequality

On the other hand, P. Van Emde Boas and D. Kruyswijk ^[8] and R. Meshulam ^[20] proved that

A lot of efforts were also made to find the precise value of Davenport constant of finite abelian groups. However, up to date, besides for the groups of types given in Theorem A (proved independently by D. Kruyswijk (as reported in ^[7]) and by J.E. Olson ^[22]) and Theorem B as below, the precise value of this constant was known only for groups of specific forms such as $\mathbb{Z}_{2}\oplus \mathbb{Z}_2 \oplus \mathbb{Z}_{2d}$ (see ^[7]), or $\mathbb{Z}_3\oplus \mathbb{Z}_3 \oplus \mathbb{Z}_{3d}$ (see ^[3]), etc. Even to determine the precise value of ${\rm D}(G)$ in the case when $G$ is a direct sum of three finite cyclic groups remains open for over 50 years (see ^[11], Conjecture 3.5). Note that the conclusion ${\rm D}(\mathbb{Z}_{n}) = n$ follows by a simple application of the pigeonhole principle.

Theorem A. (Kruyswijk-Olson Theorem) ${\rm D}(\mathbb{Z}_{n_1}\oplus \mathbb{Z}_{n_2}) = n_1+n_2-1$ where $n_1\mid n_2$.

Theorem B. (J.E. Olson ^[21]) ${\rm D}(\mathbb{Z}_{p^{\alpha_1}}\oplus\cdots\oplus\mathbb{Z}_{p^{\alpha_r}}) = 1+\sum\limits_{i = 1}^r (p^{\alpha_i}-1)$ where $p$ is prime and $r, \alpha_1, \ldots, \alpha_r$ are positive integers.

For the progress about ${\rm D}(G)$ the reader may consult ^{[10,14,18,23,24]}. Recently, the Davenport constant was generalized in the setting of commutative semigroups (see ^{[6,25,26,28,29]}). Although the above Kruyswijk-Olson Theorem is the first classical result on the value of Davenport constant, it has not yet been generalized into semigroups.

Another motivation of this manuscript comes from the following question (see ^[4,15]) posed by P. Erdős to D.A. Burgess:

"Let $\mathcal{S}$ be a finite nonempty semigroup of order $n$. A sequence of terms from $\mathcal{S}$ of length $n$ must contain one or more terms whose product, in some order, is idempotent?"

Burgess ^[4] in 1969 gave an answer to this question in the case when $\mathcal{S}$ is commutative or contains only one idempotent. This question was completely affirmed by D.W.H. Gillam, T.E. Hall and N.H. Williams ^[15], and was extended to infinite semigroups by the author ^[27] in 2019. Naturally, one combinatorial invariant was aroused by the Erdős' question with respect to commutative semigroups (for noncommutative semigroup there is also a similar invariant).

Definition. (^[27], Definition 4.1) For any commutative semigroup $\mathcal{S}$ written additively, define the Erdős-Burgess constant of $\mathcal{S}$, denoted $\text{I}(\mathcal{S})$, to be the least $\ell\in \mathbb{N}\cup \{\infty\}$ such that every sequence $T$ of terms from $\mathcal{S}$ and of length at least $\ell$ must contain one or more terms with sum being an idempotent.

Note that if the commutative semigroup $\mathcal{S}$ is finite, Gillam-Hall-Williams Theorem definitely tells us that the Erdős-Burgess constant of $\mathcal{S}$ exists, i.e., $\text{I}(\mathcal{S})\in \mathbb{N}$ is finite. In particular, when the semigroup $\mathcal{S}$ happens to be a finite abelian group, the Erdős-Burgess constant reduces to the Davenport constant, because the identity element is the unique idempotent in a group.

Therefore, in this manuscript by studying the Erdős-Burgess constant for the direct sum of two finite cyclic semigroups, we extend the Kruyswijk-Olson Theorem into commutative semigroups. Our main result is as follows.

Theorem 1.1. For any positive integers $k_1, k_2, n_1, n_2$, let $\mathcal{S} = {\rm C}_{k_1; n_1}\oplus {\rm C}_{k_2; n_2}$. Then

Moreover, the equality holds whenever one of the following conditions holds.

(i) $n_1\mid n_2$ or $n_2\mid n_1$;

(ii) there exists some $\epsilon\in \{1, 2\}$ such that $(\left\lceil\frac{k_{\epsilon}}{n_{\epsilon}}\right\rceil-1)n_{\epsilon} = \max\left((\left\lceil\frac{k_1}{n_1}\right\rceil-1)n_1, \ (\left\lceil\frac{k_2}{n_2}\right\rceil-1)n_2 \right)$ and $\frac{n_{3-\epsilon}}{\gcd(n_1, \ n_2)}$ divides $\left\lceil\frac{k_{\epsilon}}{n_{\epsilon}}\right\rceil-1$.

2.   Notation and terminologies

For integers $a, b\in \mathbb{Z}$, we set $[a, b] = \{x\in \mathbb{Z}: a\leq x\leq b\}$. For a real number $x$, we denote by $\lfloor x\rfloor$ the largest integer that is less than or equal to $x$, and by $\lceil x\rceil$ the smallest integer that is greater than or equal to $x$.

Let $\mathcal{S}$ be a commutative semigroup written additively, where the operation of $\mathcal{S}$ is denoted as $+$. For any positive integer $m$ and any element $a\in \mathcal{S}$, we denote by $ma$ the sum $\underbrace{a+\cdots+a}\limits_{m}$. An element $e$ of $\mathcal{S}$ is said to be idempotent if $e+ e = e$. A cyclic semigroup is a semigroup generated by a single element $x$, denoted $\langle x\rangle$, consisting of all elements which can be represented as $m x$ for some positive integer $m$. If the cyclic semigroup $\langle x\rangle$ is infinite then $\langle x\rangle$ is isomorphic to the semigroup of $\mathbb{N}$ with addition (see ^[16], Proposition 5.8), and if $\langle x\rangle$ is finite then the least integer $k > 0$ such that $kx = tx$ for some positive integer $t\neq k$ is called the index of $x$, then the least integer $n > 0$ such that $(k+n)x = k x$ is called the period of $x$. We denote a finite cyclic semigroup of index $k$ and period $n$ by $C_{k; n}$.

$\bullet$ Note that if $k = 1$ the semigroup $C_{k; n}$ reduces to a cyclic group of order $n$ which is isomorphic to the additive group $\mathbb{Z}_{n}$ of integers modulo $n$.

We also need to introduce notation and terminologies on sequences over semigroups and follow the notation of A. Geroldinger, D.J. Grynkiewicz and others used for sequences over groups (cf. [^[17], Chapter 10] or [^[13], Chapter 5]). Let ${\cal F}(\mathcal{S})$ be the free commutative monoid, multiplicatively written, with basis $\mathcal{S}$. We denote multiplication in $\mathcal{F}(\mathcal{S})$ by the boldsymbol $\cdot$ and we use brackets for all exponentiation in $\mathcal{F}(\mathcal{S})$. By $T\in {\cal F}(\mathcal{S})$, we mean $T$ is a sequence of terms from $\mathcal{S}$ which is unordered, repetition of terms allowed. Say $T = a_1a_2\cdot\ldots\cdot a_{\ell}$ where $a_i\in \mathcal{S}$ for $i\in [1, \ell]$. The sequence $T$ can be also denoted as $T = \mathop{\bullet}\limits_{a\in \mathcal{S}}a^{[{\rm v}_a(T)]},$ where ${\rm v}_a(T)$ is a nonnegative integer and means that the element $a$ occurs ${\rm v}_a(T)$ times in the sequence $T$. By $|T|$ we denote the length of the sequence, i.e., $|T| = \sum\limits_{a\in \mathcal{S}}{\rm v}_a(T) = \ell.$ By $\varepsilon$ we denote the empty sequence in $\mathcal{S}$ with $|\varepsilon| = 0$. We call $T'$ a subsequence of $T$ if ${\rm v}_a(T')\leq {\rm v}_a(T)\ \ \mbox{for each element}\ \ a\in \mathcal{S},$ denoted by $T'\mid T,$ moreover, we write $T^{''} = T\cdot T'^{[-1]}$ to mean the unique subsequence of $T$ with $T'\cdot T^{''} = T$. We call $T'$ a proper subsequence of $T$ provided that $T'\mid T$ and $T'\neq T$. In particular, the empty sequence $\varepsilon$ is a proper subsequence of every nonempty sequence. Let $\sigma(T) = a_1+\cdots +a_{\ell}$ be the sum of all terms from $T$. We call $T$ a zero-sum sequence provided that $\mathcal{S}$ is a monoid and $\sigma(T) = 0_{\mathcal{S}}$. In particular, if $\mathcal{S}$ is a monoid, we allow $T = \varepsilon$ to be empty and adopt the convention that $\sigma(\varepsilon) = 0_\mathcal{S}.$ We say the sequence $T$ is

● an idempotent-sum sequence if $\sigma(T)$ is an idempotent;

● an idempotent-sum free sequence if $T$ contains no nonempty idempotent-sum subsequence.

It is worth remarking that when the commutative semigroup $\mathcal{S}$ is an abelian group, the notion zero-sum sequence and idempotent-sum sequence make no difference.

Let $\mathcal{S}_1$ and $\mathcal{S}_2$ be two commutative semigroups written additively with additions $+_{\mathcal{S}_1}$ and $+_{\mathcal{S}_2}$ respectively. The direct sum of $\mathcal{S}_1$ and $\mathcal{S}_2$, denoted $\mathcal{S}_1\oplus \mathcal{S}_2$, is the commutative semigroup whose underlying set is the Cartesian product of the sets $\mathcal{S}_1$ and $\mathcal{S}_2$ and whose binary operation $+$ is given by

Let $\mathcal{S} = {\rm C}_{k_1; n_1}\oplus {\rm C}_{k_2; n_2}$, where the finite cyclic semigroup ${\rm C}_{k_i; n_i}$ is generated by $g_i$ for each $i\in \{1, 2\}$. For any element $a$ of $\mathcal{S}$ and each $i\in \{1, 2\}$, let $a(i)$ be the $i$-th component of $a$, i.e., $a = (a(1), \ a(2))$, and let ${\rm ind}_{g_i}(a(i))$ be the least positive integer $t_i$ such that $t_i g_i = a(i)$. Let

be the direct sum of two additive groups of integers modulo $n_1$ and $n_2$, which is the largest group contained in $\mathcal{S}$. Define a map $\psi:\mathcal{S}\rightarrow G_\mathcal{S}$ given by

for any element $a\in \mathcal{S}$, where $\overline{{\rm ind}_{g_i} (a(i))}$ denotes the congruence class of the integer ${\rm ind}_{g_i} (a(i))$ modulo $n_i$. We extend $\psi$ to the map $\Psi:\mathcal{F}(\mathcal{S})\rightarrow \mathcal{F}(G_{\mathcal{S}})$ given by

for any sequence $T\in \mathcal{F}(\mathcal{S})$.

3.   Proof of Theorem 1.1

We begin this section with two necessary lemmas.

Lemma 3.1. (^[16], Chapter I, Lemma 5.7, Proposition 5.8, Corollary 5.9) Let $\mathcal{S} = C_{k; n}$ be a finite cyclic semigroup generated by the element $x$. Then $\mathcal{S} = \{x, \ldots, k x, (k+1)x, \ldots, (k+n-1)x\}$ with

Moreover, there exists a unique idempotent, $\ell x$, in the cyclic semigroup $\langle x\rangle$, where

By Lemma 3.1, it is easy to derive the following.

Lemma 3.2. Let $\mathcal{S} = {\rm C}_{k_1; n_1}\oplus {\rm C}_{k_2; n_2}$ where ${\rm C}_{k_i; n_i} = \langle g_i\rangle$ for $i = 1, 2$. Then there exists a unique idempotent $e$ in $\mathcal{S}$, where

for both $i = 1, 2$. In particular, a sequence $W\in \mathcal{F}(\mathcal{S})$ is an idempotent-sum sequence if, and only if, $\sum\limits_{a\mid W}{\rm ind}_{g_i}(a(i))\geq \left\lceil\frac{k_i}{n_i}\right\rceil n_i$ and $\sum\limits_{a\mid W}{\rm ind}_{g_i}(a(i))\equiv 0\pmod{n_i}$ for both $i = 1, 2$.

Note that in Lemma 3.2, the condition that $\sum\limits_{a\mid W}{\rm ind}_{g_i}(a(i))\equiv 0\pmod{n_i}$ for both $i = 1, 2$ is equivalent to that $\Psi(W)$ is a zero-sum sequence in the group $G_{\mathcal{S}}$.

Now we are in a position to prove Theorem 1.1.

Proof of Theorem 1.1. Say ${\rm C}_{k_i; n_i} = \langle g_i\rangle$ for each $i\in \{1, 2\}$. Note that $G_{\mathcal{S}}\cong\mathbb{Z}_{n_1}\oplus \mathbb{Z}_{n_2}\cong \mathbb{Z}_{\gcd(n_1, \ n_2)}\oplus\mathbb{Z}_{{\rm lcm}(n_1, \ n_2)}.$ By Theorem A, we have that

Since ${\rm C}_{k_1; n_1}\oplus {\rm C}_{k_2; n_2}\cong {\rm C}_{k_2; n_2} \oplus {\rm C}_{k_1; n_1}$, we can assume without loss of generality that

Let $T\in \mathcal{F}(\mathcal{S})$ be an arbitrary sequence of length

Take a nonempty subsequence $L$ of $T$ such that $\Psi(L)$ is a zero-sum sequence over the group $G_{\mathcal{S}}$, i.e.,

with $|L|$ being maximal. By the maximality of $|L|$, we have that $|T\cdot L^{[-1]}|\leq {\rm D(G_{\mathcal{S}})}-1$. By (3.1), (3.2) and (3.3), we have that $\sum\limits_{a\mid L}{\rm ind}_{g_i}(a(i))\geq |L|\geq (\left\lceil\frac{k_2}{n_2}\right\rceil-1)n_2+1\geq (\left\lceil\frac{k_i}{n_i}\right\rceil-1)n_i+1$, and thus $\sum\limits_{a\mid L}{\rm ind}_{g_i}(a(i))\geq \left\lceil\frac{k_i}{n_i}\right\rceil n_i$ by (3.4), where $i\in \{1, 2\}$. By Lemma 3.2, we have that $L$ is a nonempty idempotent-sum subsequence of $T$. By (3.2), (3.3) and the arbitrariness of choosing the sequence $T$, we conclude that

Now we assume one of Conditions (ⅰ) and (ⅱ) holds. To prove ${\rm I}(\mathcal{S}) = \max\left((\left\lceil\frac{k_1}{n_1}\right\rceil-1)n_1, \ (\left\lceil\frac{k_2}{n_2}\right\rceil-1)n_2 \right)+\gcd(n_1, \ n_2)+{\rm lcm}(n_1, \ n_2)-1$, by (3.2) and (3.5) it suffices to show that there exists an idempotent-sum free sequence of terms from $\mathcal{S}$ with length exactly $(\left\lceil\frac{k_2}{n_2}\right\rceil-1)n_2+\gcd(n_1, \ n_2)+{\rm lcm}(n_1, \ n_2)-2$.

Consider the case when Condition (ⅰ) $n_1\mid n_2$ or $n_2\mid n_1$ holds. Take two elements $\beta, \gamma\in \mathcal{S}$ with

and

Let

Since $\gcd(n_1, \ n_2)+{\rm lcm}(n_1, \ n_2) = n_1+n_2$, it follows that $|T_1| = (n_1-1)+(\left\lceil\frac{k_2}{n_2}\right\rceil n_2-1) = (\left\lceil\frac{k_2}{n_2}\right\rceil -1)n_2+n_1+n_2-2 = (\left\lceil\frac{k_2}{n_2}\right\rceil -1)n_2+\gcd(n_1, \ n_2)+{\rm lcm}(n_1, \ n_2)-2$. We need only to verify that the sequence $T_1$ is idempotent-sum free. Assume to the contrary that $T_1$ contains a nonempty idempotent-sum subsequence

where

and

It follows from (3.6), (3.7), (3.8) and Lemma 3.2 that

and

By (3.9) and (3.11), we have $t_1 = 0$, and then combined with (3.10) and (3.12), we derive a contradiction, done.

Now we consider the case when Condition (ⅱ) holds. Combined with (3.2), we assume that

Let

and

where ${\rm pot}_p(n)$ denotes the largest integer $h$ such that $p^{h}$ divides $n$. Note that

Take $b, c\in \mathcal{S}$ such that

and

Take the sequence

We see that $|T_2| = (\left\lceil\frac{k_2}{n_2}\right\rceil-1)n_2+\frac{n_1n_2}{\gcd(n_1, \ n_2)}-1+\gcd(n_1, \ n_2)-1 = (\left\lceil\frac{k_2}{n_2}\right\rceil-1)n_2+{\rm lcm}(n_1, \ n_2)+\gcd(n_1, \ n_2)-2$. To prove $T_2$ is idempotent-sum free, we assume to the contrary that $T_2$ contains a nonempty idempotent-sum subsequence $V$. Say

with

and

By Lemma 3.2, (3.16), (3.17) and (3.18), we derive that

and

and that $s + t \frac{n_2}{\gcd(n_1, \ n_2)} = \sum\limits_{a\mid V}{\rm ind}_{g_2}(a(2))\geq \left\lceil\frac{k_2}{n_2}\right\rceil n_{2}$, combined with (3.20), then

By (3.14), we have $\gcd(m_1, \ \frac{n_1}{m_1}) = 1$, combined with (3.21), we have that

and that $m_1\mid t,$ combined with (3.15), (3.22), then

Note that $\gcd(\frac{n_1}{m_1}, \ \frac{n_2}{m_2}) = 1$. It follows from (3.15), (3.24) and (3.25) that

By (3.13), we have $\frac{n_1n_2}{\gcd(n_1, \ n_2)}\mid (\left\lceil\frac{k_2}{n_2}\right\rceil-1)n_2$. Combined with (3.19) and (3.23), we derive a contradiction to (3.26). This proves Theorem 1.1.

4.   Concluding remarks

In Theorem 1.1, by taking $k_1 = k_2 = 1$, both cyclic semigroups ${\rm C}_{k_1; n_1}$ and ${\rm C}_{k_2; n_2}$ reduce to $\mathbb{Z}_{n_1}$ and $\mathbb{Z}_{n_2}$ respectively, and thus

We also see that $\left\lceil\frac{k_{i}}{n_{i}}\right\rceil-1 = 0$ for both $i\in \{1, 2\}$ and Condition (ⅱ) holds. By the conclusion of Theorem 1.1, we have that ${\rm D}(\mathbb{Z}_{n_1}\oplus\mathbb{Z}_{n_2}) = {\rm I}(\mathcal{S}) = \max\left((\left\lceil\frac{k_1}{n_1}\right\rceil-1)n_1, \ (\left\lceil\frac{k_2}{n_2}\right\rceil-1)n_2 \right)+\gcd(n_1, \ n_2)+{\rm lcm}(n_1, \ n_2)-1 = \gcd(n_1, \ n_2)+{\rm lcm}(n_1, \ n_2)-1$. That is, Condition (ⅱ) of Theorem 1.1 implies Kruyswijk-Olson Theorem as a consequence (Condition (ⅰ) deduce Kruyswijk-Olson Theorem clearly).

For a finite cyclic semigroup ${\rm C}_{k; n}$, since ${\rm C}_{k; n}\cong {\rm C}_{1; 1}\oplus{\rm C}_{k; n}$ and Condition (ⅰ) holds for ${\rm C}_{1; 1}\oplus{\rm C}_{k; n}$, by applying Theorem 1.1, we have that ${\rm I}({\rm C}_{k; n}) = {\rm I}({\rm C}_{1; 1}\oplus{\rm C}_{k; n}) = \left\lceil\frac{k}{n}\right\rceil n.$

We remark that there exists some direct sum of two finite cyclic semigroups for which the Erdős-Burgess constant is strictly less than that upper bound $\max\left((\left\lceil\frac{k_1}{n_1}\right\rceil-1)n_1, \ (\left\lceil\frac{k_2}{n_2}\right\rceil-1)n_2 \right)+\gcd(n_1, \ n_2)+{\rm lcm}(n_1, \ n_2)-1$ given in Theorem 1.1. For example, by a straightforward case distinction, we can show that any sequence over ${\rm C}_{1; 3}\oplus {\rm C}_{3; 2}$ of length $7$ must contain a nonempty idempotent-sum subsequence, i.e., ${\rm I}({\rm C}_{1; 3}\oplus {\rm C}_{3; 2})$ is strictly less than that upper bound $8$ given as Theorem 1.1. Therefore, we close this paper with the following conjecture.

Conjecture 4.1. Let $\mathcal{S} = {\rm C}_{k_1; n_1}\oplus {\rm C}_{k_2; n_2}$. If ${\rm I}(\mathcal{S}) = \max\left((\left\lceil\frac{k_1}{n_1}\right\rceil-1)n_1, \ (\left\lceil\frac{k_2}{n_2}\right\rceil-1)n_2 \right)+\gcd(n_1, \ n_2)+{\rm lcm}(n_1, \ n_2)-1$ then one of the following conditions holds.

(i) $n_1\mid n_2$ or $n_2\mid n_1$;

(ii) there exists some $\epsilon\in \{1, 2\}$ such that $(\left\lceil\frac{k_{\epsilon}}{n_{\epsilon}}\right\rceil-1)n_{\epsilon} = \max\left((\left\lceil\frac{k_1}{n_1}\right\rceil-1)n_1, \ (\left\lceil\frac{k_2}{n_2}\right\rceil-1)n_2 \right)$ and $\frac{n_{3-\epsilon}}{\gcd(n_1, \ n_2)}$ divides $\left\lceil\frac{k_{\epsilon}}{n_{\epsilon}}\right\rceil-1$.

Acknowledgments

This work is supported by NSFC (grant no. 11971347, 11501561).

Conflict of interest

The author declares no conflicts of interest.