New upper bounds for the Davenport and for the Erdős-Ginzburg-Ziv constants (Q766082)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | New upper bounds for the Davenport and for the Erdős-Ginzburg-Ziv constants |
scientific article |
Statements
New upper bounds for the Davenport and for the Erdős-Ginzburg-Ziv constants (English)
0 references
23 March 2012
0 references
Let \((G, +)\) be a finite abelian group. The Davenport constant \(\mathsf{D}(G)\) of \(G\) is the smallest \(l\) such that each sequence \(g_1, \dots, g_l\) of length \(l\) has a non-empty zero-sum subsequence; that is, there is a non-empty subset \(I \subset \{1, \dots, l\}\) such that \(\sum_{i \in I}g_i = 0\). The Erdős-Ginzburg-Ziv constant \(\mathsf{s}(G)\) is defined in the same way except that \(|I|= \exp(G)\) is imposed as additional condition; that is, there is a zero-sum subsequence of length equal to the exponent. Both constant are intensely studied but in general there exact value is unknown. The paper establishes several new and interesting bounds for these constants, mainly using the Inductive Method. Among others it is shown that \(\mathsf{D}((\mathbb{Z}/n\mathbb{Z})^r) \leq r^{\omega(n)}(n-1)+1\) where \(\omega(n)\) denotes the number of different prime divisors of \(n\). For context we recall that \(\mathsf{D}((\mathbb{Z}/n\mathbb{Z})^r) \geq r(n-1)+1\) and equality is known to hold in case \(n\) is a prime-power or \(r \leq 2\); no example is known where equality does not hold. In addition, a connection of the Davenport constant with the problem of factoring integers using the quadratic sieve is discussed.
0 references
Davenport constant
0 references
zero-sum problem
0 references
finite abelian group
0 references
factoring integers using the quadratic sieve
0 references