Erdős-Ginzburg-Ziv theorem for finite commutative semigroups. (Q741647)

From MaRDI portal
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
    0 references
    0 references
    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

    Identifiers