## Minimal covers by pair-sums

By Warren D. Smith 1 Oct 2006

Puzzle: Let the set {0,1,2,...,N-1} be covered by sums of exactly 2 elements (not necessarily distinct) of a subset Q containing q elements. For each N: what is the minimal q?

Example: N=9, q=4, set={0,1,3,4} means {0,1,2,...,8} is covered thus by pair-sums: 0=0+0, 1=0+1, 2=1+1, 3=0+3, 4=0+4=1+3, 5=1+4, 6=3+3, 7=3+4, 8=4+4 and the cardinality q=4 is minimal since (by the pigeonhole principle) no 3-element subset of {0,1,2,...,8} can work.

Nqset
320,1
430,1,2
530,1,2
640,1,2,3
740,1,2,3
840,1,3,4
940,1,3,4
1050,1,2,4,5
1150,1,2,4,5
1250,1,3,5,6
1350,1,3,5,6
1460,1,2,4,6,7
1560,1,2,4,6,7
1660,1,3,5,7,8
1760,1,3,5,7,8
1870,1,2,4,6,8,9
1970,1,2,4,6,8,9
2070,1,3,5,7,9,10
2170,1,3,5,7,9,10
2280,1,2,4,6,8,10,11
2380,1,2,4,6,8,10,11
2480,1,3,5,7,9,11,12
2580,1,3,5,7,9,11,12
2680,1,3,4,9,10,12,13
2780,1,3,4,9,10,12,13
2890,1,3,5,7,9,11,13,14
2990,1,3,5,7,9,11,13,14
3090,1,3,4,9,10,12,14,15
3190,1,3,4,9,10,12,14,15
3290,1,2,5,8,11,14,15,16
3390,1,2,5,8,11,14,15,16
34100,1,3,4,9,10,12,14,16,17
35100,1,3,4,9,10,12,14,16,17
36100,1,3,5,6,12,13,15,17,18
37100,1,3,5,6,12,13,15,17,18
38100,1,3,5,6,13,14,16,18,19
39100,1,3,5,6,13,14,16,18,19
40100,1,3,4,9,11,16,17,19,20
41100,1,3,4,9,11,16,17,19,20
42110,1,3,5,6,13,14,16,18,20,21
43110,1,3,5,6,13,14,16,18,20,21
44110,1,3,4,6,11,13,18,19,21,22
45110,1,3,4,6,11,13,18,19,21,22
46110,1,2,3,7,11,15,19,21,22,24
47110,1,2,3,7,11,15,19,21,22,24
48120,1,3,5,7,8,16,17,19,21,23,24
49120,1,3,5,7,8,16,17,19,21,23,24
50120,1,3,5,7,8,17,18,20,22,24,25
51120,1,3,5,7,8,17,18,20,22,24,25
52120,1,3,5,6,12,13,20,21,23,25,26
53120,1,3,5,6,12,13,20,21,23,25,26
54120,1,3,5,6,13,14,21,22,24,26,27
55120,1,3,5,6,13,14,21,22,24,26,27
56130,1,3,4,8,9,11,20,21,23,25,27,28
57130,1,3,4,8,9,11,20,21,23,25,27,28
58130,1,3,5,6,13,14,21,22,24,26,28,29
59130,1,3,5,6,13,14,21,22,24,26,28,29
6013 0,1,3,5,6,13,15,17,24,25,27,29,30
6113 0,1,3,5,6,13,15,17,24,25,27,29,30
6213 0,2,3,5,9,13,17,21,25,26,28,30,31
63130,1,2,3,7,11,15,19,23,27,29,30,32
64130,1,3,4,9,11,16,21,23,28,29,31,32
6513 0,1,3,4,9,11,16,21,23,28,29,31,32

The sequence 3, 5, 9, 13, 17, 21, 27, 33, 41, 47, 55, ... does not match anything previously in the Online Encyclopedia of Integer Sequences. Note the N=46, N=47 and N=63 lines in the table above, which are the first known examples where it is necessary for Q-cardinality-minimality that Q include a number greater than N/2 (shown blue).

Asymptotics: We can easily bound N(q) between two quadratics:

(q-3)2/4 ≤ N ≤ (q+1)q/2
by the "pigeonhole principle" N≤(q+1)q/2, while by the construction where numbers in {0,1,2,...,N-1} are regarded as 2-digit numbers in radix ceiling(√N), we can by using the ones with at most one nonzero digit as our set Q, show q≤1+2ceiling(√N), so that (q-3)2/4≤N.

A least-squares fit of a quadratic in q=2,3,4,...,12 to the data N=3,5,9,...,55 yields N = 0.291*q2 + 1.139*q - 0.527 approximately, suggesting that perhaps the lower bound on N is closer to the truth than the upper bound, i.e. indicating the trivial 2-digit construction is actually not so bad.