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

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

Sequence in context: A331246 A331256 A368941 * A091194 A156079 A268708

Adjacent sequences: A283294 A283295 A283296 * A283298 A283299 A283300

Keyword

nonn

Author

Taras Banakh, Mar 04 2017

Status

approved