A Golomb ruler can be described as a set of marks on a line having integer positions, such that no two pairs of marks are separated by the same distance. Call the spectrum of a ruler the (multi-)set of distances measured by the ruler. For example, consider a ruler $G_3$ on $n=3+1$ marks, with marks at $\{0,1,4,6\}$. The spectrum of $G_3$ is $\{1,2,3,4,5,6\}$. In this case, $G_3$ is perfect, in that every distance between $1$ and $6$ inclusive can be measured.

Define the $L^2$ norm of a set of marks as the square root of the sum of squares of the multiplicity of the spectrum. For example, a ruler with marks at $\{0,1,3,5,8\}$ has a spectrum of $\{1,2,2,3,3,4,5,5,7,8\}$, and thus an $L^2$ norm of $(1^2+2^2+2^2+1^2+2^2+1^2+1^2)^{1/2}=4$.

The requirement of having no two distances measured twice seems overly narrowing. For example, there may be some applications, in, say, radio astronomy, where allowing a repeat measurement every now and then may be acceptable. Thus, I consider a "generalized" optimal ruler $G_{m,k}$ (not great name) that, instead of having no two pairs of marks separated by the same distance, minimizes such an $L^2$ norm over all rulers on $m$ marks of length $k$. For a Golomb ruler, the $L^2$ norm of an $(m+1)$-mark ruler is $\sqrt{m(m-1)/2}$, but there might be clever constructions to stuff marks onto a ruler that has a nice spectrum with small $l^2$ norm.

Have such rulers been studied, perhaps in relation to Sidon sets? Is there anything nontrivial known about the relation of the $L^2$ norm to the number of marks $m$ or the length of the ruler $k$?

  • $\begingroup$ Have you computed the norm for extreme examples, like say a ruler from the hardware store? It may be the L2 norm is not fine enough. Gerhard "Perhaps Measure A Different Way?" Paseman, 2018.11.20. $\endgroup$ – Gerhard Paseman Nov 20 '18 at 23:59

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.