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. 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 x = 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 x 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 |x| 2/3
Discovered: 1992

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 |x| 1/2
Discovered: 1992

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 |x| 4/5
Discovered: 1992

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 |x| 2/3
Discovered: 1992

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 |x| 6/7
Discovered: June 2010 (attained 0.386133... in 1992)

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 |x| 3/4
Discovered: June 2010 (attained 0.385092... in 1992)

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 |x| 8/9
Discovered: June 2010 (attained 0.382989... in 1992)

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 |x| 4/5
Discovered: June 2010 (attained 0.382604... in 1992)

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 = 34

f(x) = 0		for 0		x < 3/17
f(x) = 0.0930549480181		for 3/17		x < 4/17
f(x) = 0.5434645159888		for 4/17		x < 5/17
f(x) = 0.8721757560595		for 5/17		x < 6/17
f(x) = 0.0347312605022		for 6/17		x < 7/17
f(x) = 0.5123362141989		for 7/17		x < 8/17
f(x) = 0.5599782603767		for 8/17		x < 9/17
f(x) = 0.6605344637625		for 9/17		x < 10/17
f(x) = 0.5122399437387		for 10/17		x < 11/17
f(x) = 0.5013802820089		for 11/17		x < 12/17
f(x) = 0.8227318392270		for 12/17		x < 13/17
f(x) = 0.7117859948872		for 13/17		x < 14/17
f(x) = 0.8198363894737		for 14/17		x < 15/17
f(x) = 0.8776707303918		for 15/17		x < 16/17
f(x) = 0.9780794013660		for 16/17		x 1
f(x) = f(2-x)		for 1		< x 2

Illustration
α(f) < 0.3811062442303
∫ f(x)(1-f(x+k))dx maximal for 2/17 |k| 15/17
Discovered: August 2009

n = 52

f(x) = 0		for 0		x < 5/26
f(x) = 0.0939054096654871		for 5/26		x < 6/26
f(x) = 0.4183670276617741		for 6/26		x < 7/26
f(x) = 0.8737828276896925		for 7/26		x < 8/26
f(x) = 0.5932588813441947		for 8/26		x < 9/26
f(x) = 0.4392084241327522		for 9/26		x < 10/26
f(x) = 0.0377882475396368		for 10/26		x < 11/26
f(x) = 0.5182593767499687		for 11/26		x < 12/26
f(x) = 0.5854237837177492		for 12/26		x < 13/26
f(x) = 0.6500154024864767		for 13/26		x < 14/26
f(x) = 0.4950194563454981		for 14/26		x < 15/26
f(x) = 0.7545166468874106		for 15/26		x < 16/26
f(x) = 0.4411172791729476		for 16/26		x < 17/26
f(x) = 0.3722882891771239		for 17/26		x < 18/26
f(x) = 0.9297779185072845		for 18/26		x < 19/26
f(x) = 0.6595448650953440		for 19/26		x < 20/26
f(x) = 0.7603074629581672		for 20/26		x < 21/26
f(x) = 0.7801019058217693		for 21/26		x < 22/26
f(x) = 0.8041927591901891		for 22/26		x < 23/26
f(x) = 0.8966122096192302		for 23/26		x < 24/26
f(x) = 0.9040623054391411		for 24/26		x < 25/26
f(x) = 0.9924495207981624		for 25/26		x 1
f(x) = f(2-x)		for 1		< x 2

Illustration
α(f) < 0.3810964913311364
∫ f(x)(1-f(x+k))dx maximal for 3/26 |k| 23/26
Discovered: August 2009