0
$\begingroup$

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...

$\endgroup$
1
  • $\begingroup$ The sets from the linked answer are related to Golomb rulers, but they differ from sets with unique sums. The sequences to sum consist of $m$ elements for the latter, but of consecutive elements for the former. $\endgroup$ Commented Jul 6, 2020 at 3:09

1 Answer 1

2
+50
$\begingroup$

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}$.

$\endgroup$
8
  • 1
    $\begingroup$ +1, thanks, are you saying that, when I ask, for $\b^\star$ being unique, among all other sums with the same number of terms (dupes allowed), I get a exponentially large set of unique sums of $B$ for free? Concerning the other hand: Would you suggest to just scan Singer/Bose/Ruzka constructions for my additional condition? $\endgroup$
    – draks ...
    Commented Jul 6, 2020 at 6:49
  • 1
    $\begingroup$ @draks... Yes for the first question. For the other hand, I don’t see how modular Golomb rules can help to construct a set with unique sums $\mod q$. Or what additional condition do you mean? PS. The upper bound above for a size of a set with unique sums $\mod q$ is rather tight, because if $m\ge 2$ and $(m-2)2^{m-1}+1<q$ then a set $\{2^0,2^1,\dots, 2^{m-1}\}$ has unique sums $\mod q$. $\endgroup$ Commented Jul 6, 2020 at 8:01
  • $\begingroup$ Ok, but what then do mean by "the page you linked suggests that at least for some $q$ there exist modular Golomb rulers of size close to $\sqrt{q}$."? $\endgroup$
    – draks ...
    Commented Jul 6, 2020 at 8:13
  • $\begingroup$ @draks... I guess the lenght of the modular Golomb rulers for the constructions mentioned there is about $q$. I tried to check this looking at “James B. Shearer's Golomb Ruler page with a piece on modular Golomb Rulers” linked there, but the page doesn’t exist. $\endgroup$ Commented Jul 6, 2020 at 9:14
  • $\begingroup$ Hi, I found a cached version of the linked page at web.archive.org/web/20171225101048/http://www.research.ibm.com/… but it is not very helpful in my opinion... $\endgroup$
    – draks ...
    Commented Jul 8, 2020 at 7:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .