On the Index of Sequences over Cyclic Groups

Abstract

Let $G$ be a finite cyclic group of order $n\ge 2$. Every sequence $S$ over $G$ can be written in the form $S=(n_{1}g)\cdot ...\cdot (n_{l}g)$ where $g\in G$ and $n_1,..., n_l \in [1,\ord(g)]$, and the index $\ind (S)$ of $S$ is defined as the minimum of $(n_1+ ... + n_l)/\ord (g)$ over all $g\in G$ with $\ord (g) = n$. In this paper we prove that a sequence $S$ over $G$ of length $|S|=n$ having an element with multiplicity at least $\frac{n}{2}$ has a subsequence $T$ with $\ind (T) = 1$, and if the group order $n$ is a prime, then the assumption on the multiplicity can be relaxed to $\frac{n-2}{10}$. On the other hand, if $n=4k+2$ with $k\ge 5$, we provide an example of a sequence $S$ having length $|S|>n$ and an element with multiplicity $\frac{n}{2}-1$ which has no subsequence $T$ with $\ind (T) = 1$. This disproves a conjecture given twenty years ago by Lemke and Kleitman.

This manusript replaces the previous one entitled 'Index of sequences'(arXiv:0909.2461). The present version has been accepted by Acta Arith