On a conjecture of Lemke and Kleitman

Xiangneng Zeng¹ ; Yuanlin Li² ; Pingzhi Yuan³

¹ Sino–French Institute of Nuclear Engineering and Technology Sun Yat-Sen University Guangzhou 510275, P.R. China
² Department of Mathematics and Statistics Brock University St. Catharines, ON, Canada L2S 3A1
³ School of Mathematics South China Normal University Guangzhou 510631, P.R. China

Acta Arithmetica, Tome 168 (2015) no. 3, pp. 289-299

Résumé

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.

Détail

DOI : 10.4064/aa168-3-5

Keywords: finite cyclic group order every sequence written form cdot ldots cdot where ldots mathop ord index mathop ind defined minimum cdots mathop ord mathop ord paper shown sequence length nmid having element multiplicity least has subsequence mathop ind other positive integers d provide example sequence length having element multiplicity d d has subsequence mathop ind giving general counterexample conjecture lemke kleitman