On the Index of Sequences over Cyclic Groups

الأصل · EN

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