Optimal Diameters of High Multiplicity g-Golomb Rulers
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909042912264192 |
|---|---|
| author | Gupta, Aditya O'Bryant, Kevin |
| author_facet | Gupta, Aditya O'Bryant, Kevin |
| contents | A set $\mathcal{G}$ of integers is called a $g$-Golomb ruler of length $n$ if the difference between any two distinct elements of $\mathcal{G}$ is repeated at most $g$ times. If $g=1$, these are also called $B_2$-sets, Sidon sets, and Babcock sets. We define $G(g,n)$ to represent the minimum diameter of a $g$-Golomb Ruler. In this paper, we prove that for all $b\ge 1$, if $g \ge \frac{7}{4}\left(b^{3/2} -b\right)+1,$ then $G(g,g+b)=g+2b-2$. Sharper bounds are given for $b\le 18$. The main technique is through an arithmetic property of the integers that are \emph{not} in a $g$-Golomb ruler, leading us to introduce LM rulers, a new class of rulers where every distance $d$ occurs as a difference at most $d-1$ times. We show that the minimum diameter of an $n$-element LM ruler $L(n)$ is $\sqrt{8/9} \cdot (n-1)^{3/2} \le L(n) \le \frac{7}{4}\left((n+1)^{3/2}-(n+1)\right).$ |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_14229 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Optimal Diameters of High Multiplicity g-Golomb Rulers Gupta, Aditya O'Bryant, Kevin Combinatorics 05B10 (Primary), 11B13 (Secondary), 11B34 A set $\mathcal{G}$ of integers is called a $g$-Golomb ruler of length $n$ if the difference between any two distinct elements of $\mathcal{G}$ is repeated at most $g$ times. If $g=1$, these are also called $B_2$-sets, Sidon sets, and Babcock sets. We define $G(g,n)$ to represent the minimum diameter of a $g$-Golomb Ruler. In this paper, we prove that for all $b\ge 1$, if $g \ge \frac{7}{4}\left(b^{3/2} -b\right)+1,$ then $G(g,g+b)=g+2b-2$. Sharper bounds are given for $b\le 18$. The main technique is through an arithmetic property of the integers that are \emph{not} in a $g$-Golomb ruler, leading us to introduce LM rulers, a new class of rulers where every distance $d$ occurs as a difference at most $d-1$ times. We show that the minimum diameter of an $n$-element LM ruler $L(n)$ is $\sqrt{8/9} \cdot (n-1)^{3/2} \le L(n) \le \frac{7}{4}\left((n+1)^{3/2}-(n+1)\right).$ |
| title | Optimal Diameters of High Multiplicity g-Golomb Rulers |
| topic | Combinatorics 05B10 (Primary), 11B13 (Secondary), 11B34 |
| url | https://arxiv.org/abs/2605.14229 |