On the Possible Orders of a Basis for a Finite Cyclic Group

  • Peter Dukes
  • Peter Hegarty
  • Sarada Herke

Abstract

We prove a result concerning the possible orders of a basis for the cyclic group ${\Bbb Z}_n$, namely: For each $k \in {\Bbb N}$ there exists a constant $c_k > 0$ such that, for all $n \in {\Bbb N}$, if $A \subseteq {\Bbb Z}_n$ is a basis of order greater than $n/k$, then the order of $A$ is within $c_k$ of $n/l$ for some integer $l \in [1,k]$. The proof makes use of various results in additive number theory concerning the growth of sumsets. Additionally, exact results are summarized for the possible basis orders greater than $n/4$ and less than $\sqrt{n}$. An equivalent problem in graph theory is discussed, with applications.

Published
2010-05-25
Article Number
R79