On the length of Golomb Ruler: A function construction approach based on difference triangle

Yanqing Wang, Xiaoming LiarXiv 2014 · DOI · arXiv

TL;DR

This paper presents a novel method for constructing "near-optimal" Golomb rulers—sequences of marks where all pairwise distances are unique—using a structured "difference triangle" approach. The authors successfully halve the length of previously known general constructions and provide a rigorous proof that simple quadratic formulas cannot be used to generate these sequences for large sets of marks.

What Problem Does This Paper Address?

A Golomb Ruler is a set of marks at integer positions along a ruler such that no two pairs of marks are the same distance apart. For example, a ruler with marks at $\{0, 1, 4, 6\}$ is a Golomb ruler because the distances are $\{1, 4, 6, 3, 5, 2\}$—all unique.

The "Holy Grail" in this field is finding the shortest possible ruler for a given number of marks ($n$). This is a notoriously difficult combinatorial problem with applications in radio frequency allocation, sonar signal design, and the placement of elements in phased-array antennas. Because finding the absolute shortest (optimal) ruler is computationally exhaustive for large $n$, researchers look for "graceful sequences"—mathematical formulas that can generate valid, though perhaps not perfectly optimal, Golomb rulers of a predictable length.

Methods

The authors utilize a tool called a Difference Triangle (DT). A DT is a way of organizing all possible differences between marks in a sequence into a triangular array. If every number in this triangle is unique, the sequence is a valid Golomb ruler.

The core of their approach involves:

  1. Function Construction: Defining a sequence $x_i$ based on a cubic-style formula.
  2. Modular Packing: Using a lemma based on modular arithmetic to ensure that differences in different "columns" of the triangle don't collide.
  3. Block Splitting: In Theorem 2, the authors refine their construction by splitting the difference triangle into two blocks and using a smaller modulus ($N \approx n/2$). This allows them to "pack" the marks more tightly while still proving that no two differences can be equal.

Datasets

As this is a theoretical paper focused on mathematical proofs and functional construction, no external datasets or empirical benchmarks were used. The work is evaluated against existing mathematical bounds in the literature, specifically improving upon results previously published in 1990.

Key Insights and Ideas

  • The Power of the Triangle: By transforming the problem of "unique distances" into a "Difference Triangle," the authors can use row and column properties to prove uniqueness more easily than checking every pair manually.
  • Halving the Bound: The most significant insight is that by carefully choosing the modulus $N$ based on whether $n$ is even or odd, the "density" of the ruler can be significantly increased. This effectively cuts the length of the generated ruler in half compared to the previous state-of-the-art general construction.
  • The Quadratic Barrier: A common hope in combinatorics is that a simple polynomial (like a quadratic) might generate an infinite family of optimal solutions. The authors dash this hope for Golomb rulers by proving that any sequence generated by a general quadratic formula $x_i = ai^2 + bni + ci + dn^2 + en + f$ will eventually produce duplicate differences as $n$ grows.

Key Results

  • Improved Upper Bound: The authors establish a new upper bound for the length of a Golomb ruler with $n$ marks:
  • For $n$ odd: $x_n \le (n-1) + \frac{(n-1)^2(n-2)}{4}$
    • For $n$ even: $x_n \le (n-1) + \frac{n(n-1)(n-2)}{4}$
  • Order of Growth: The construction results in a ruler length of order $O(n^3/4)$. While this is still larger than the theoretical lower bound of $O(n^2)$, it represents a 50% reduction in length over the previous $O(n^3/2)$ construction.
  • Impossibility Proof: They successfully proved that rational quadratic polynomials are insufficient for generating graceful sequences for large $n$.

Limitations and Future Work

The main limitation is the gap between the $O(n^3)$ construction provided here and the conjectured $O(n^2)$ optimal length. The authors acknowledge that their rulers are "near-optimal" rather than truly optimal.

For future work, the authors suggest that machine proving and automated theorem provers could be an "assistant way" to help researchers construct more complex Difference Triangles efficiently. This points toward a hybrid approach where human mathematical intuition sets the framework, and computational power finds the densest possible packing within that framework.

Summary updated

Abstract

Since the significance of Golomb Ruler Problem in some context, we proposes a function construction approach based on difference triangle to generate near-optimal Golomb rulers. Let x1, x2, ..., xn be an increasing sequence of integers, where x1 = 0, which satisfies the following conditions: if abs(xi-xj) = abs(xp-xq) then {i, j} = {p,q}. Our objective is to find the order of minimum xn for any given n. In this paper, the two results in a paper are both improved. In addition, it will be shown that the length of Golomb Ruler have been shortened to a half, and that the satisfying sequence can not be generated by such a quadratic formula as $xi = ai^2+bni+ci+dn^2+en+f$ for any rational a, b, c, d, e and f.
BibTeX
@misc{wang2014length,
  author = {Yanqing Wang and Xiaoming Li},
  title = {{On the length of Golomb Ruler: A function construction approach based on difference triangle}},
  year = {2014},
  eprint = {1401.5556},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1401.5556},
}
Figure