The minimum overlap problem
by Jan Kristian Haugland

Consider a partition of {1, 2, ..., 2n} into two disjoint subsets {a_i} and {b_j} with n elements in each. For a fixed integer k,
denote by M_k the number of solutions to a_i - b_j = k, and let M(n) denote the minimum, over all partitions, of max_k M_k.

To estimate M(n) is the minimum overlap problem of Paul Erdös. I proved that lim M(n)/n exists and conjectured that it is
equal to the infimum, over all step functions f on [0, 2] with values in [0, 1] and ∫ f(x)dx = 1, of α(f) = max_k ∫ f(x)(1-f(x+k))dx.
This was the topic of my project in a young scientists contest in 1993. I had found such a step function f with 11 steps
(i.e., constant in each interval (2i / 11, 2(i+1) / 11)) and α(f) < 0.38209360, and used it to find an actual partition
of {1, 2, ..., 174724} with max M_k = 33695, thus proving lim M(n)/n < 0.38569401 unconditionally.

Peter Swinnerton-Dyer, who assessed my project, proved the conjecture. Later I wrote a paper with a slightly better
step function f with 21 steps and α(f) < 0.38200299, along with Swinnerton-Dyer's proof: Advances in the minimum
overlap problem, J. Number Theory 58(1996), 71-78. The best known lower bound is 0.35639395 by Leo Moser.

In 2009 I came up with a more efficient algorithm for finding good step functions,
and in 2011 I made further improvements with the help of GAMS/BARON.

Here is a list of current record-holders. A step function f with n steps and satisfying f(0) ≤ 1/2 should be included
if and only if the value of α(f) is smaller than or equal to that of any other known step function with at most n steps.

n = 1
f(x) = 1/2 for 0 ≤ x ≤ 2
α(f) = 1/2 = 0.5
∫ f(x)(1-f(x+k))dx maximal for k = 0

n = 2
f(x) = 1/3 for 0 ≤ x < 1
f(x) = 2/3 for 1 ≤ x ≤ 2
α(f) = 4/9 < 0.44444445
∫ f(x)(1-f(x+k))dx maximal for -1 ≤ k ≤ 0

n = 3

f(x) = 1/2 - 1/40		for 0		≤ x < 2/3
f(x) = 1/2 + 1/10		for 2/3		≤ x ≤ 1
f(x) = f(2-x)		for 1		< x ≤ 2

α(f) = 2/5 = 0.4
∫ f(x)(1-f(x+k))dx maximal for |k| ≤ 2/3

n = 4

f(x) = 1/2 - 1/20		for 0		≤ x < 1/2
f(x) = 1/2 + 1/20		for 1/2		≤ x ≤ 1
f(x) = f(2-x)		for 1		< x ≤ 2

α(f) = 2/5 = 0.4
∫ f(x)(1-f(x+k))dx maximal for |k| ≤ 1/2

n = 5

f(x) = 1/2 - ((10+77)/336)		for 0		≤ x < 2/5
f(x) = 1/2 + ((7-2)/84)		for 2/5		≤ x < 4/5
f(x) = 1/2 + ((2+7)/28)		for 4/5		≤ x ≤ 1
f(x) = f(2-x)		for 1		< x ≤ 2

Illustration
α(f) = 11/30 + (7)/105 < 0.39186430
∫ f(x)(1-f(x+k))dx maximal for 2/5 ≤ |k| ≤ 4/5

n = 6

f(x) = 1/2 - 1/12		for 0		≤ x < 1/3
f(x) = 1/2		for 1/3		≤ x < 2/3
f(x) = 1/2 + 1/12		for 2/3		≤ x ≤ 1
f(x) = f(2-x)		for 1		< x ≤ 2

Illustration
α(f) = 7/18 < 0.38888889
∫ f(x)(1-f(x+k))dx maximal for |k| ≤ 2/3

n = 7

f(x) = 0.105078900636553360		for 0		≤ x < 2/7
f(x) = 0.503514170485956264		for 2/7		≤ x < 4/7
f(x) = 0.668195943454623334		for 4/7		≤ x < 6/7
f(x) = 0.946421970845734084		for 6/7		≤ x ≤ 1
f(x) = f(2-x)		for 1		< x ≤ 2

Illustration
α(f) < 0.386120220734884585
∫ f(x)(1-f(x+k))dx maximal for 2/7 ≤ |k| ≤ 6/7

n = 8

f(x) = 0.089641067480915042		for 0		≤ x < 1/4
f(x) = 0.463633234694070334		for 1/4		≤ x < 2/4
f(x) = 0.608616277306427928		for 2/4		≤ x < 3/4
f(x) = 0.838109420518586696		for 3/4		≤ x ≤ 1
f(x) = f(2-x)		for 1		< x ≤ 2

Illustration
α(f) < 0.385071709487211768
∫ f(x)(1-f(x+k))dx maximal for 1/4 ≤ |k| ≤ 3/4

n = 9

f(x) = 0.004837381098458996		for 0		≤ x < 2/9
f(x) = 0.459493974210709653		for 2/9		≤ x < 4/9
f(x) = 0.579753504802302153		for 4/9		≤ x < 6/9
f(x) = 0.723007092664141244		for 6/9		≤ x < 8/9
f(x) = 0.965816094448775908		for 8/9		≤ x ≤ 1
f(x) = f(2-x)		for 1		< x ≤ 2

Illustration
α(f) < 0.382892238905007292
∫ f(x)(1-f(x+k))dx maximal for 2/9 ≤ |k| ≤ 8/9

n = 10

f(x) = 0		for 0		≤ x < 1/5
f(x) = 0.427849980190994044		for 1/5		≤ x < 2/5
f(x) = 0.537828535348129426		for 2/5		≤ x < 3/5
f(x) = 0.663356982483178949		for 3/5		≤ x < 4/5
f(x) = 0.870964501977697581		for 4/5		≤ x ≤ 1
f(x) = f(2-x)		for 1		< x ≤ 2

Illustration
α(f) < 0.382427116707499603
∫ f(x)(1-f(x+k))dx maximal for 1/5 ≤ |k| ≤ 4/5

n = 11

f(x) = 0		for 0		≤ x < 2/11
f(x) = 0.40927102724537031493078911531197074319496439451091		for 2/11		≤ x < 4/11
f(x) = 0.48949727431597144473464116714975062426573698805027		for 4/11		≤ x < 6/11
f(x) = 0.59195016227654047852123164261388200249258432927523		for 6/11		≤ x < 8/11
f(x) = 0.76613894272687659312982232136375498416154510138067		for 8/11		≤ x < 10/11
f(x) = 0.98628518687048233736703150712134329177033837356584		for 10/11		≤ x ≤ 1
f(x) = f(2-x)		for 1		< x ≤ 2

Illustration
α(f) < 0.38209359817161709135358049671482690617182364440023
∫ f(x)(1-f(x+k))dx maximal for 2/11 ≤ |k| ≤ 8/11
Discovered: 1992 (refined 1993)

n = 15

f(x) = 0		for 0		≤ x < 2/15
f(x) = 0.09938602		for 2/15		≤ x < 4/15
f(x) = 0.64299877		for 4/15		≤ x < 6/15
f(x) = 0.36104582		for 6/15		≤ x < 8/15
f(x) = 0.69536426		for 8/15		≤ x < 10/15
f(x) = 0.59241335		for 10/15		≤ x < 12/15
f(x) = 0.89573331		for 12/15		≤ x < 14/15
f(x) = 0.92611694		for 14/15		≤ x ≤ 1
f(x) = f(2-x)		for 1		< x ≤ 2

Illustration
α(f) < 0.38153155
∫ f(x)(1-f(x+k))dx maximal for 2/15 ≤ |k| ≤ 12/15
Discovered: May 2010

n = 17

f(x) = 0		for 0		≤ x < 2/17
f(x) = 0.028007266		for 2/17		≤ x < 4/17
f(x) = 0.631255158		for 4/17		≤ x < 6/17
f(x) = 0.332085547		for 6/17		≤ x < 8/17
f(x) = 0.646927973		for 8/17		≤ x < 10/17
f(x) = 0.539624810		for 10/17		≤ x < 12/17
f(x) = 0.771627728		for 12/17		≤ x < 14/17
f(x) = 0.827417212		for 14/17		≤ x < 16/17
f(x) = 0.946108612		for 16/17		≤ x ≤ 1
f(x) = f(2-x)		for 1		< x ≤ 2

Illustration
α(f) < 0.38143098
∫ f(x)(1-f(x+k))dx maximal for 2/17 ≤ |k| ≤ 14/17
Discovered: May 2010

n = 19

f(x) = 0		for 0		≤ x < 4/19
f(x) = 0.348795091509472207		for 4/19		≤ x < 6/19
f(x) = 0.742684181900847446		for 6/19		≤ x < 8/19
f(x) = 0.207655267155520404		for 8/19		≤ x < 10/19
f(x) = 0.780222086674911898		for 10/19		≤ x < 12/19
f(x) = 0.568104573396874436		for 12/19		≤ x < 14/19
f(x) = 0.689049157609512654		for 14/19		≤ x < 16/19
f(x) = 0.967251286500411737		for 16/19		≤ x < 18/19
f(x) = 0.892476710504898436		for 18/19		≤ x ≤ 1
f(x) = f(2-x)		for 1		< x ≤ 2

Illustration
α(f) < 0.381112263316104816
∫ f(x)(1-f(x+k))dx maximal for 2/19 ≤ |k| ≤ 16/19
Discovered: May 2010

n = 29

f(x) = 0		for 0		≤ x < 6/29
f(x) = 0.2676058656518283		for 6/29		≤ x < 8/29
f(x) = 0.9929440254233889		for 8/29		≤ x < 10/29
f(x) = 0.0570326141757860		for 10/29		≤ x < 12/29
f(x) = 0.5121827619825924		for 12/29		≤ x < 14/29
f(x) = 0.6142279296508323		for 14/29		≤ x < 16/29
f(x) = 0.6313715832167212		for 16/29		≤ x < 18/29
f(x) = 0.4478634372721209		for 18/29		≤ x < 20/29
f(x) = 0.7700613804387751		for 20/29		≤ x < 22/29
f(x) = 0.7534956165417719		for 22/29		≤ x < 24/29
f(x) = 0.8178911132455888		for 24/29		≤ x < 26/29
f(x) = 0.8987824211599151		for 26/29		≤ x < 28/29
f(x) = 0.9730825024813582		for 28/29		≤ x ≤ 1
f(x) = f(2-x)		for 1		< x ≤ 2

Illustration
α(f) < 0.38098987465276
∫ f(x)(1-f(x+k))dx maximal for 2/29 ≤ |k| ≤ 24/29
Discovered: April 2011

n = 35

f(x) = 0		for 0		≤ x < 6/35
f(x) = 0.03238003560575		for 6/35		≤ x < 8/35
f(x) = 0.46469335227746		for 8/35		≤ x < 10/35
f(x) = 1		for 10/35		≤ x < 12/35
f(x) = 0.08179883609036		for 12/35		≤ x < 14/35
f(x) = 0.32969693439226		for 14/35		≤ x < 16/35
f(x) = 0.69700395490768		for 16/35		≤ x < 18/35
f(x) = 0.50267022624400		for 18/35		≤ x < 20/35
f(x) = 0.72207503730147		for 20/33		≤ x < 22/35
f(x) = 0.31005623320619		for 22/35		≤ x < 24/35
f(x) = 0.86664405573480		for 24/35		≤ x < 26/35
f(x) = 0.65866221465766		for 26/35		≤ x < 28/35
f(x) = 0.84471706808832		for 28/35		≤ x < 30/35
f(x) = 0.78739476150616		for 30/35		≤ x < 32/35
f(x) = 0.98857595739413		for 32/35		≤ x < 34/35
f(x) = 0.92726266518752		for 34/35		≤ x ≤ 1
f(x) = f(2-x)		for 1		< x ≤ 2

Illustration
α(f) < 0.38097062715367
∫ f(x)(1-f(x+k))dx maximal for 4/35 ≤ |k| ≤ 30/35
Discovered: May 2011

n = 49

f(x) = 0		for 0		≤ x < 8/49
f(x) = 0.00647468352772		for 8/49		≤ x < 10/49
f(x) = 0.21647681825379		for 10/49		≤ x < 12/49
f(x) = 0.59077752917036		for 12/49		≤ x < 14/49
f(x) = 0.16355762786237		for 14/49		≤ x < 16/49
f(x) = 0.82845576206124		for 16/49		≤ x < 18/49
f(x) = 1		for 18/49		≤ x < 20/49
f(x) = 0.21180974556365		for 20/49		≤ x < 22/49
f(x) = 0.07710650229582		for 22/49		≤ x < 24/49
f(x) = 0.34204906397597		for 24/49		≤ x < 26/49
f(x) = 0.72477988844473		for 26/49		≤ x < 28/49
f(x) = 0.88810141495243		for 28/49		≤ x < 30/49
f(x) = 0.67254960734442		for 30/49		≤ x < 32/49
f(x) = 0.43482515558899		for 32/49		≤ x < 34/49
f(x) = 0.68160979113197		for 34/49		≤ x < 36/49
f(x) = 0.58794531007594		for 36/49		≤ x < 38/49
f(x) = 0.71662625338243		for 38/49		≤ x < 40/49
f(x) = 0.78808131960861		for 40/49		≤ x < 42/49
f(x) = 1		for 42/49		≤ x < 44/49
f(x) = 0.93948581030243		for 44/49		≤ x < 46/49
f(x) = 0.97295024833531		for 46/49		≤ x < 48/49
f(x) = 0.81267493624364		for 48/49		≤ x ≤ 1
f(x) = f(2-x)		for 1		< x ≤ 2

Illustration
α(f) < 0.38096406669462
∫ f(x)(1-f(x+k))dx maximal for 4/49 ≤ |k| ≤ 40/49
Discovered: May 2011

n = 51

f(x) = 0		for 0		≤ x < 10/51
f(x) = 0.0002938681556273		for 10/51		≤ x < 12/51
f(x) = 0.5952882223921177		for 12/51		≤ x < 14/51
f(x) = 0.7844530825484313		for 14/51		≤ x < 16/51
f(x) = 0.8950034338013842		for 16/51		≤ x < 18/51
f(x) = 0.0597964076006748		for 18/51		≤ x < 20/51
f(x) = 0.0189602838469592		for 20/51		≤ x < 22/51
f(x) = 0.7420501628172980		for 22/51		≤ x < 24/51
f(x) = 0.6444559588500921		for 24/51		≤ x < 26/51
f(x) = 0.3549040817844764		for 26/51		≤ x < 28/51
f(x) = 0.8762442385073478		for 28/51		≤ x < 30/51
f(x) = 0.5437907313675501		for 30/51		≤ x < 32/51
f(x) = 0.2679640048997296		for 32/51		≤ x < 34/51
f(x) = 0.8518954615823791		for 34/51		≤ x < 36/51
f(x) = 0.5211171156914872		for 36/51		≤ x < 38/51
f(x) = 1		for 38/51		≤ x < 40/51
f(x) = 0.5506146790047043		for 40/51		≤ x < 42/51
f(x) = 0.9007715390796991		for 42/51		≤ x < 44/51
f(x) = 0.8229000691941086		for 44/51		≤ x < 46/51
f(x) = 0.8879541710440111		for 46/51		≤ x < 48/51
f(x) = 0.9315424878319221		for 48/51		≤ x < 50/51
f(x) = 1		for 50/51		≤ x ≤ 1
f(x) = f(2-x)		for 1		< x ≤ 2

Illustration
α(f) < 0.3809268534330870
∫ f(x)(1-f(x+k))dx maximal for 4/51 ≤ |k| ≤ 36/51 and 40/51 ≤ |k| ≤ 42/51
Discovered: May 2011