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, 11, 12, 11, 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 and 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 q 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.

Example

From Ed Pegg Jr, Jul 17 2025: (Start)
For a(n), n is the modulus for differences in Z_n. The difference basis here is what Singer called a difference set, also called a circular sparse ruler.
For a(21), basis (0, 1, 4, 14, 16) corresponds to (1, 3, 10, 2, 5), a Singer "perfect partition".
For a(28), (1, 3, 11, 5, 2, 6) is a unique non-perfect cyclic partition for the basis.
For a(95), (1, 2, 6, 11, 13, 14, 8, 15, 16, 5, 4) is one of ten partitions. (End)

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

Extensions

a(93) and a(95) corrected by Ed Pegg Jr, Jul 17 2025

Status

approved