On a conjecture of Lemke and Kleitman
Volume 168 / 2015
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_1g)\cdot \ldots \cdot (n_lg)$ where $g \in G$ and $n_1, \ldots , n_l \in [1, \mathop{\rm ord} (g)]$, and the index $\mathop{\rm ind} (S)$ of $S$ is defined as the minimum of $(n_1 +\cdots + n_l )/ \mathop{\rm ord} (g)$ over all $g\in G$ with $\mathop{\rm ord} (g) = n$. In this paper it is shown that any sequence $S$ over $G$ of length $|S| \ge n \ge 5$, $2 \nmid n$, having an element with multiplicity at least ${n/3}$ has a subsequence $T$ with $\mathop{\rm ind} (T ) = 1$. On the other hand, if $n, d\ge 2$ are positive integers with $d\,|\,n$ and $n>d^2(d^3-d^2+d+1)$, we provide an example of a sequence $S$ of length $|S| \ge n$ having an element with multiplicity $l={n/d}-d(d-1)-1$ such that $S$ has no subsequence $T$ with $\mathop{\rm ind} (T ) = 1$, giving a general counterexample to a conjecture of Lemke and Kleitman.
