Maximum Distinct Differences

The maximum distinct differences problem asks for the largest number of distinct positive differences determined by a -element subset of the integers 0, 1, ..., , where is a nonnegative integer and . Explicitly,

(1)

where the maximum is over the stated -element subsets. Pikhurko and Schoen (2007, pp. 1-2) use for the largest cardinality of , including zero and both signs, so . The number of unordered pairs and the available differences give

(2)

Attaining the first bound requires all pairwise differences to be distinct, as in a Golomb ruler. Attaining the second requires every distance from 1 through to occur. A sparse ruler minimizes the number of marks needed for that complete coverage, whereas this problem fixes the number of marks and maximizes the number of distances attained.

A sequence of particular interest takes , where the two elementary bounds agree,

(3)

Beginning with , the recorded values are 3, 6, 9, 13, 19, 26, 32, 40, 49, 58, 68, 79, ... (OEIS A399997). This sequence was a runner-up in the OEIS 400K celebration contest (OEIS Foundation Inc. 2026).

For , the marks 0, 1, 3, 13, 20, 27, 31, 35, 36attain 32 distances, missing only 6, 21, 25, and 29 (Pegg 2026). Adding a mark at 6 gives all 36 distances, illustrating the distinction between maximizing partial coverage and requiring complete coverage. Pegg (2026) also supplies larger constructions. For example, his 15-mark construction attains 90 distinct positive differences and therefore establishes , with equality conjectural.

For any fixed , Pikhurko and Schoen (2007, pp. 3-4) proved that

(4)

exists whenever , independently of the choice of the integer-valued function . Here denotes a quantity tending to zero. Consequently, the special sequence satisfies

(5)

This limit concerns asymptotic density and does not establish exact finite values.