On the possible orders of a basis for a finite cyclic group

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Additive bases, including sumsets (11B13) Other combinatorial number theory (11B75)

Let \({\mathbb Z}_n\) denote the cyclic group of order \(n.\) For a subset \(A\) of \({\mathbb Z}_n\) and a positive integer \(h,\) let \(hA\) be the \(h\)-fold sumset of \(A\) : \[ hA=\{a_1+\cdots+a_h;\;a_i\in A,1\leq i\leq h\}~. \] The subset \(A\) of \({\mathbb Z}_n\) is called a \textit{basis} of \textit{order} \(h\) for \({\mathbb Z}_n\) if \(hA={\mathbb Z}_n\) and \(h\) is minimal. A subset \(A\) of \({\mathbb Z}_n\) is a basis if and only if the greatest common divisor of the elements of \(A\) is relatively prime to \(n.\) Let \(\rho_n(A)\) denote the order of a basis \(A\) of \({\mathbb Z}_n.\) The purpose of this paper is to investigate the set \(R_n\) of all possible values of orders of bases \(A\) of \({\mathbb Z}_n.\) It is clear that \(R_n\subseteq[1,n-1],\) but not every integer in \([1,n-1]\) belongs to \(R_n.\) For instance, \textit{H. Daode} proved in [Linear Algebra Appl. 136, 107--117 (1990; Zbl 0701.15010)] that \[ R_n\cap[\tfrac n2+1,n-2]=\emptyset. \] The main result proved in the paper under review is the following theorem: ``For each positive integer \(k\) there exists a constant \(c_k>0\) such that, for any positive integer \(n,\) if \(A\) is a basis of \({\mathbb Z}_n\) of order \(\rho_n(A)\geq{n\over k},\) then there is some integer \(\ell\in[1,k]\) such that \(|\rho_n(A)-{n\over\ell}|<c_k.\) As a corollary, the authors obtain that \({{R_n}\over n}\) tends to 0, as \(n\) tends to \(+\infty\). They give all sets \(R_n\) for \(n\leq64\) and they conclude with some applications to graph theory.

Recommendations

Cited in

(7)

This page was built for publication: On the possible orders of a basis for a finite cyclic group

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q976738)