Golomb Rulers and Sets with Unique Sums

136 Views Asked by At

A set of integers ${\displaystyle A=\{a_{1},a_{2},...,a_{m}\}}$ where ${\displaystyle a_{1}<a_{2}<...<a_{m}}$ is a Golomb ruler if and only if $$ \text{for all } i,j,k,l \in \{1,2,...,m\} {\text{ such that }} i\neq j {\text{ and }} k\neq l, a_{i}-a_{j}=a_{k}-a_{l}\iff i=k{\text{ and }}j=l. $$

A modular Goloumb ruler works the same, not on a line but on a circle of length $q$. I wonder how these rulers are connected to sets $B=\{b_1,b_2,...,b_m\}$, where $b_1<b_2<...<b_m$ and the sum $b^\star=\sum_{k=1}^m b_k \bmod q$ is unique, in the sense, that every other sum of $m$ elements of $B$ (e.g. $b^{\text{other}_1}=2b_1+b_3+...b_m \bmod q$), has a value other than $b^\star$. So I don't bother if $b^{\text{other}_k}=b^{\text{other}_l}$, only $b^\star$ shall be unique.

Can Goloumb Ruler help to generate the sets $B$ as well?

They were for example given in this answer, to a question that looks similar to my question...

1

There are 1 best solutions below

8
On BEST ANSWER

Each set $B$ with unique sums $\mod q$ is a Golomb ruler $\mod q$. Indeed, if there exists $i,j,k,l \in \{1,2,...,m\}$ such that $i\neq j$ and $k\neq l$ and ($i\ne k$) or $j\ne l$) but $b_{i}-b_{j}=b_{k}-b_{l} \pmod q $ then $b^*=b^*+b_i+b_l-b_j-b_k \pmod q$, a contradiction.

The condition for $B$ to be a set with unique sums ($\mod q$) is much stronger than to be a (modular) Golomb ruler and the former sets are much sparse than the latter.

Indeed, if $B=\{b_1,\dots, b_m\}$ is a set with unique sums $\mod q$ and $m’=\lfloor m/2\rfloor$ then all ${m\choose m’}$ sums of subsets of $B$ of size $m’$ are distinct, which follows ${m\choose m’}\le q$. By Robbins’ bounds for each $m\ge 2$ we have $$\frac {2^{m-1/2}}{\sqrt{\pi (m+\delta)}}\exp\left(-\frac {1}{4(m+\delta)-1}\right)<{m\choose m’}<\frac {2^{m-1/2}}{\sqrt{\pi (m+\delta)}}\exp\left(-\frac {1}{4(m+\delta)+1}\right),$$ where $\delta$ equals $0$, if $m$ is even and $1$, is $m$ is odd.

On the other hand, the constructions at the page you linked suggest that at least for some $q$ there exist modular Golomb rulers of size close to $\sqrt{q}$.