A Golomb ruler is a set of marks placed on a number line so that no two pairs of marks are the same distance apart. Think of it like a ruler where every measurable distance between marks is unique. A "t-mark" Golomb ruler has exactly t marks. This paper studies how efficiently you can use a collection of these rulers, all with the same number of marks t, to collectively cover as many whole-number distances as possible within a range from 1 to some large number U, with the constraint that no distance appears in more than one ruler in your collection.
The central question is: for which values of t can you find such a collection that covers almost all of the integers up to U, meaning the fraction of integers you miss shrinks toward zero as U grows large? The paper's main result gives a sharp answer: this near-complete coverage is achievable if and only if t is 3, 4, or 5. For t equal to 3 or 4, the result follows from previously known mathematical structures. For t equal to 5, the authors use a clever construction that multiplies rulers together in a way that eventually fills in nearly all the gaps. For t equal to 6 or more, they prove that no matter how cleverly you arrange your collection, you are always forced to miss at least some fixed positive fraction of integers, no matter how large U is.
To prove that coverage must fail for larger t, the authors use a Fourier analysis argument, essentially analyzing how evenly spread the covered distances can be by examining their frequency content. They identify a specific number, approximately 0.4345, that acts as a measure of the fundamental obstruction. For rulers with six marks, this guarantees you must always miss at least about 2.15 percent of integers. For very large t, a separate counting argument shows the unavoidable gap grows toward 50 percent. Together, these results draw a clean dividing line in a natural combinatorial optimization problem, identifying exactly which ruler sizes allow efficient coverage and providing quantitative bounds on how badly large rulers must fail.