Minimum overlap calculator for a split of 1 to 2n

What this calculator does

Split the numbers from 1 to 2n into two halves of equal size. Now slide one half along and count how many of its members land on the other. Some shift always produces a sizeable overlap, and Erdős asked in 1955 how small that unavoidable worst case can be made.

The surprising part is that the average overlap is the same for every split. Summed over all shifts, the total is always n squared, because every member of one half meets every member of the other at exactly one shift. So the problem is not about reducing the overlap, which is fixed, it is entirely about flattening it: spreading the same total as evenly as possible so that no single shift carries a spike.

The formula

Formulafor a split into A and B, score = max over every shift k of |A ∩ (B + k)|, reported against n

The split is given as a repeating pattern of 0s and 1s, where 0 puts a number in A and 1 puts it in B. The pattern repeats to fill 2n places and is then adjusted so each half has exactly n members. For every shift k the calculator counts how many members of B land on a member of A when moved by k, and reports the largest such count along with the ratio to n. That ratio is the quantity being minimised, and as n grows its best value approaches a constant.

Term	Meaning
A and B	The two halves, each containing exactly n of the numbers from 1 to 2n.
Shift	An integer k. The overlap at k is how many pairs satisfy a − b = k.
Worst overlap	The largest overlap over all shifts, which is the score of the split.
M(n)/n	The score divided by n. The best achievable value tends to a constant now known to lie between about 0.3790 and 0.38087.

The inputs explained

Field	What to enter
Split pattern (0 = A, 1 = B, repeated to length 2n)	A pattern of 0s and 1s, repeated to fill the 2n places. Anything other than 0 and 1 is ignored. Regular patterns score badly, which is the point.
Half-size n	Half the count of numbers being split, so the numbers run from 1 to 2n. Capped at 2,000 because every shift is checked.

When to use it

Seeing why regular splits fail

Try the pattern 01, which puts odds in one half and evens in the other. A shift of one lines them up perfectly and the overlap is n, the worst possible. The same happens for any block pattern: a shift of one block length maps one half exactly onto the other.

Testing an irregular split

The default pattern scores about 0.53 at n = 40, roughly half what a regular split gives. It was found by random search, which is in miniature exactly what the machine systems did at much greater scale.

Watching the constant emerge

Hold the pattern and raise n. The ratio settles down, because the quantity being measured is asymptotic. Short patterns stop improving once n is large enough that their periodicity shows.

Worked examples

Every figure in the tables below is produced by this page’s own calculator at build time, so the numbers and the tool always agree. Select any row to load that scenario.

How do regular and irregular splits compare?

The same question asked of five different patterns.

Half-size n fixed at 100

Pattern	Overlap ÷ n	Worst shifted overlap	Average overlap across shifts
01	1.000	100	25.06
0011	1.000	100	25.06
0000000011111111	0.9600	96	25.06
0110100110010110	0.9600	96	25.06
0110101100001001…	0.5800	58	25.06

The first two patterns score exactly 1.0, the worst possible, because each has a short period and a shift of one period maps one half onto the other precisely. The two sixteen-character patterns do only slightly better at 0.96, and the irregular twenty-four-character pattern in the last row reaches 0.58. The average column is identical in every row at 25.06, which is the invariant: no split changes the total, only its distribution.

Does the score settle as n grows?

The pattern repeats to fill larger and larger ranges.

The same irregular pattern throughout

Half-size n	Overlap ÷ n	Worst shifted overlap	Shift where it happens
20	0.5500	11	-6
40	0.5250	21	-18
100	0.5800	58	-26
200	0.5800	116	-54
500	0.5840	292	-145
1,000	0.5820	582	-290

The ratio starts at 0.55 for a small range and settles near 0.58 once n is past about 100, which is where the 24-character pattern has repeated often enough for its own periodicity to dominate. A fixed short pattern cannot approach the true constant of roughly 0.3809, because beating it needs structure that does not repeat.

Questions

What is the answer to the problem?

Not known exactly. The limiting value of M(n)/n is pinned between about 0.379005, a lower bound proved by E. P. White in 2022, and 0.380868, an upper bound from 2026. The gap is in the fourth decimal place.

What did AI contribute?

Three successive improvements to the upper bound. AlphaEvolve reached 0.380924 in 2025, the first progress since 2016. TTT-Discover improved it to 0.380876 in 2026, and SimpleTES to 0.380868 shortly after. Each found a better split than the last.

Why is the average overlap the same for every split?

Because summing the overlap over all shifts counts every pair of one member from each half exactly once, giving n squared regardless of how the split was made. Only the distribution across shifts can be changed.

Why do regular patterns score so badly?

A periodic pattern maps onto itself under a shift of one period. If the two halves alternate with period p, then shifting by p lines them up exactly and every member overlaps, giving the worst possible score of n.

Can this calculator find a record?

No. It scores a split you give it rather than searching for one, and a short repeating pattern cannot get near the record. The records come from long, irregular, carefully optimised constructions.

For the counting underneath, see permutations and combinations. For another problem where a machine moved a bound by a tiny margin that mattered, see cap set growth rate. The three improvements to this bound are covered in the piece on the minimum overlap problem.

Minimum overlap of a split calculator