Erdős-Ginzburg-Ziv theorem for finite commutative semigroups. (Q741647): Difference between revisions
From MaRDI portal
Revision as of 00:44, 9 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Erdős-Ginzburg-Ziv theorem for finite commutative semigroups. |
scientific article |
Statements
Erdős-Ginzburg-Ziv theorem for finite commutative semigroups. (English)
0 references
12 September 2014
0 references
It has been shown by \textit{P. Erdős} et al. [Bull. Res. Council Israel 10F, 41-43 (1961; Zbl 0063.00009)] that in an additive Abelian group \(G\) of order \(n\) every sequence of \(2n-1\) elements contains an \(n\)-element subsequence with zero sum. If \(E(G)\) denotes the minimal integer \(d\) such that every sequence of at least \(d\) elements of \(G\) contains a subsequence of length \(n\) and zero sum, then it follows from a result of the second author [J. Number Theory 58, No. 1, 100-103 (1996; Zbl 0892.11005); Discrete Math. 271, No. 1-3, 51-59 (2003; Zbl 1089.11012)] generalizing the Erdős-Ginzburg-Ziv theorem, that \[ E(G)=D(G)+n-1,\tag{*} \] where \(D(G)\) denotes the Davenport constant of \(G\). The authors are interested in a generalization of (*) to semigroups. Let \(S\) be a finite commutative semigroup, denote by \(\mathcal F(S)\) the set of all finite sequences \((s_1,s_2,\ldots,s_r)\) of elements of \(S\), and for \(A\in\mathcal F(S)\) let \(\sigma(s)\) be the set of all subsums of \(s_1+s_2+\cdots+s_r\). For \(a\in S\) the period of \(a\) is the smallest \(t>1\) such that for some \(u>0\) one has \((u+t)a=ua\), and \(\exp(S)\) is the least common multiple of periods of elements of \(S\). Let \(E(S)\) be the smallest integer \(d\) such that if \(A\in\mathcal F(S)\) has \(d\) elements, then it contains a subsequence \(B\) with \(\sigma(B)=\sigma(A)\), and \(|A|-|B|=\kappa(S)\), where \[ \kappa(S)=\left\lceil{n\over\exp(S)}\right\rceil\exp(S). \] This agrees with \(E(G)\) in case when \(S=G\) is a finite Abelian group. The authors conjecture the inequality \(E(S)\leq D(S)+\kappa(S)-1\) for all finite commutative semigroups, \(D(S)\) being the large Davenport constant for semigroups (see \textit{G. Wang} and \textit{W. Gao} [Semigroup Forum 76, No. 2, 234-238 (2008; Zbl 1142.20043)]), and establish it in the following three cases: a) \(S\) is group-free, i.e. \(\exp(S)=1\), b) \(S\) is subdirectly irreducible, and c) \(S\) is Archimedean, i.e., for any \(a,b\in S\) there exist \(m,n>0\) and \(x,y\in S\) such that \(ma=b+x\) and \(nb=a+y\).
0 references
Erdős-Ginzburg-Ziv theorem
0 references
zero sum sequences
0 references
finite commutative semigroups
0 references
elementary semigroups
0 references
Archimedean semigroups
0 references
0 references