A283297 - OEIS

A283297

The smallest cardinality of a difference-basis in the cyclic group of order n.

1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 5, 6, 6, 6, 6, 6, 6, 6, 7, 7, 6, 7, 7, 7, 7, 7, 7, 8, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 8, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 9, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 10, 11, 12, 12, 12, 12, 12, 12, 12, 12

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

A subset B is called a difference-basis for an Abelian group G if B-B=G. This sequence is calculated by computer. For n=1+q+q*q where q is a power of a prime number the smallest cardinality of a difference-basis equals q+1, which is witnessed by the difference set of Singer. The problem of calculating the values of the sequence seems to be of exponential complexity.

LINKS

Table of n, a(n) for n=1..100.

T. Banakh, V. Gavrylkiv, Difference bases in cyclic and dihedral groups, arXiv:1702.02631 [math.CO], 2017.

MathOverflow, What is the smallest cardinality of a self-linked set in a finite cyclic group?, Feb 15 2017.

J. Singer, A theorem in finite projective geometry and some applications to number theory, Trans. Amer. Math. Soc. 43 (1938), 377-85.

FORMULA

a(n) = q+1 if n=1+q+q*q for a power of a prime number.

a(n) >= (1+sqrt(4n-3))/2;

a(n) <= sqrt(2n) for n != 4;

a(n) < sqrt(2n) if n>=5 and sqrt(n/8) is not integer.

It is an open problem whether a(n) = (1+o(1))sqrt(n). See the MathOverflow link.

CROSSREFS