An Ehrhart theoretic approach to generalized Golomb rulers

A Golomb ruler of length $t$ with $m+1$ markings is a sequence of integers $0=x_{0}<x_{1}<\dots<x_{m-1}<x_{m}=t$ such that the differences $x_{j}-x_{i}$ are all distinct. Golomb rulers were originally considered by Sidon [Sid32] and are also known as Sidon sets or $B_{2}$-sets.

The main question that has been studied about such sets is their maximum density; that is, for a given $t$, what is the maximum possible $m$ such that there exists a Golomb ruler of length $t$ with $m+1$ markings? It has long been known that as $t$ tends to $\infty$, this maximum is asymptotic to $\sqrt{t}$. The lower bound is due to Singer [Sin38] and the asymptotically matching upper bound to Erdós and Turán [ET41]. For a range of more recent and related results, we refer the reader to O’Bryant’s survey [O’B04].

A different problem is to count Golomb rulers given the parameters $m$ and $t$. We denote by $b_{m}(t)$ the number of Golomb rulers of length $t$ with $m+1$ markings. For $m$ fixed and $t$ tending to infinity, almost every possible sequence is a Golomb ruler, so

In order to obtain more algebraically precise results, Beck, Bogart, and Pham [BBP12] introduced the following framework. Since $x_{0}=0$, the sequence $\mathbf{x}=(x_{0},x_{1},\dots,x_{m})$ is equivalently specified by the sequence of successive differences $\mathbf{z}=(z_{1},\dots,z_{m})$, where $z_{i}=x_{i}-x_{i-1}$. The condition that $x_{0}<x_{1}<\dots<x_{m}$ becomes the condition that the $z_{i}$’s are all positive, and the $z_{i}$’s, like the $x_{i}$’s, must all be integers. That is, each Golomb ruler corresponds to a lattice point in the $t$th dilation of the standard $(m-1)$-simplex in $\mathbb{R}^{m}$. Finally, the condition that differences are unique can be written as a collection of linear inequations in the $z_{i}$’s.

In more general terms, we have just observed that Golomb rulers are in bijection with the lattice points in the interior of a certain polytope that do not lie on any of the hyperplanes in a certain arrangement. Beck and Zaslavsky [BZ06] studied such sets of lattice points in general under the name of inside-out polytopes. They extended Ehrhart’s theorem (both quasipolynomiality and reciprocity) to this context. Their theory could thus be brought to bear on the counting function $b_{m}(t)$ (see Theorem 2.2 below.) It also yielded a bijection between the combinatorial types of Golomb rulers and the regions of the hyperplane arrangement that intersect the interior of the polytope.

Golomb rulers have been generalized in several ways.

The asympototic density question is still open in these cases. To our knowledge, the best general upper and lower bounds for the density of $B_{h}[g]$ sets appear in a recent preprint of Johnson, Tait, and Timmons [JTT21]. They also note that in many cases, their upper bound matches one of Green [Gre01], and their lower bound matches one of Caicedo, Gómez, Gómez, and Trujillo [CGGT14]. For $B_{h}$-sets, Dellamonica, Kohayakwawa, Lee, Rödl, and Samotij [DJKL⁺16] give good asymptotic results for the total number of $B_{h}$ sets of length at most $t$.

Returning to the question of enumeration, given $m$ and $t$, we denote by $b_{m}[g](t)$, $b_{m}^{-}[g](t)$, and $b_{m,h}(t)$ the number of rulers of length $t$ with $m+1$ markings that are respectively $B_{2}[g]$-sets. $B_{2}^{-}[g]$-sets, and $B_{h}$-sets. (We will not consider $B_{h}[g]$-sets from now on, but it should be possible to extend our results on $B_{2}[g]$-sets to this case.) In comparison with [DJKL⁺16], our approach deals with the simpler situation in which the number of markings $m+1$ is fixed, but it yields results that are more precise in an algebraic sense.

In Section 2 we state our main theorems about the counting functions of generalized Golomb rulers after laying out the necessary definitions. In Section 3, we extend the approach of Beck, Bogart, and Pham in order to prove these theorems. In all cases, the underlying polytope is still a dilated standard simplex. For $B_{h}$-sets, we explicitly describe the hyperplane arrangement that must be removed. For the other types of generalized Golomb rulers, the conditions yield that not a hyperplane arrangement but a subspace arrangement must be removed, and we explicitly describe these arrangements. Some of the results of Beck and Zaslavsky extend to the situation of subspace arrangements, so in particular we obtain quasipolynomiality results in all cases.

In addition, Beck, Bogart, and Pham gave a combinatorial interpretation of the regions of the inside-out polytope in terms of orientations of a certain mixed graph that satisfy a certain coherence property. Unfortunately, in the course of this project we realized that this result is not correct. There is indeed an explicit injection from regions to orientations but this function is not surjective in general. We review the proof of injectivity and give an explicit counterexample to surjectivity in Section 4. Finally, in Section 5 we extend the construction and the injective map to the case of $B_{h}$-sets, using a more elaborate mixed graph.

Let $\mathbf{x}=(x_{0},\dots,x_{m})$ denote a ruler with $m+1$ markings and again identify the ruler with the sequence of successive differences $\mathbf{z}=(z_{1},\dots,z_{m})$ of $\mathbf{x}$. As we have seen, these differences form a sequence of positive integers that sum to $t$, which can be identified with an integer point in the interior of the $t$-th dilation of the standard $(m-1)$-simplex. That is,

where $\Delta_{m-1}=\{(\mathbf{z}:\,z_{1},\dots,z_{m}\geq 0,\sum_{i=1}^{m}z_{i}=1$.

Now by definition, a Golomb ruler is a ruler for which the differences $x_{j}-x_{i}$ between two markings are all distinct. In terms of the consecutive differences, we have $x_{j}-x_{i}=\sum_{k=i+1}^{j}z_{k}$. Thus a ruler is a Golomb ruler if for every pair of consecutive subsets $U,V$ of $[m]$ we have

Note that if $\mathbf{z}$ is itself a Golomb ruler, then its multiplicity is one.

We extend parts of this result to generalized Golomb rulers as follows.

Our remaining results apply only to $B_{h}$-sets. The reason for this is that (as we will see in Section 3), $B_{h}$-sets are defined by avoidance of certain hyperplanes, while the other types of generalized Golomb rulers are defined by avoidance of certain subspaces.

By definition, a $B_{h}$ set with $m+1$ markings is a ruler $\mathbf{x}$ such that for each pair of distinct sequences $0\leq r_{1}\leq\dots\leq r_{h}\leq m$ and $0\leq s_{1}\leq\dots\leq s_{h}\leq m$ we have

Our results are proved via the theory of inside-out polytopes, developed by Beck and Zaslavsky [BZ06]. Their main ideas, which we now review, extend Ehrhart theory to the situation of a polytope with a hyperplane arrangement or a subspace arrangement removed.

An inside-out polytope in $\mathbb{R}^{d}$ is a pair $(P,\mathcal{H})$ where $P$ is a rational polytope and $\mathcal{H}$ is a rational hyperplane arrangement. A region of $(P,\mathcal{H})$ is a connected component of $\mathcal{P}\setminus\bigcup_{H\in\mathcal{H}}H$ and a closed region (respectively open region) is simply the relative closure (respectively relative interior) of a region. For $\mathbf{x}\in\mathbb{R}^{d}$, the multiplicity $m_{P.\mathcal{H}}$ of $\mathbf{x}$ with respect to $(P,\mathcal{H})$ is defined to be the number of closed regions that contain $\mathbf{x}$. In particular, if $\mathbf{x}$ does not belong to $P$ then $m_{P,\mathcal{H}}(\mathbf{x})=0$ and if $\mathbf{x}$ is contained in an open region of $(P,\mathcal{H})$ then $m_{P,\mathcal{H}}(\mathbf{x})=1$.

By analogy with standard Ehrhart theory (see for example [BR07]), the closed Ehrhart function and the open Ehrhart function of the inside-out polytope $(P,\mathcal{H})$ are respectively defined to be

Note that the Ehrhart reciprocity law involves not the open Ehrhart function $E^{\circ}_{P,\mathcal{H}}$ itself, but the function $E^{\circ}_{P^{\circ},\mathcal{H}}$ for which we remove not only the hyperplanes of $\mathcal{H}$, but also the boundary of $P$. If the facet-defining hyperplanes of $P$ belong to $\mathcal{H}$, then these two functions coincide.

More generally, if $\mathcal{A}$ is a rational affine subspace arrangement in $\mathbb{R}^{d}$ and $P$ is a rational $d$-polytope, then the closed Ehrhart function $E_{P,\mathcal{A}}$ and open Ehrhart function $E^{\circ}_{P,\mathcal{A}}$ can be defined just as above. However, $\mathcal{A}$ no longer divides $P$ into regions and so multiplicity must be defined in a different way. The multiplicity of $x\in P$ is defined to be

where $\mathcal{L}(\mathcal{A})$ is the intersection semilattice of flats of $\mathcal{A}$. If $x\notin P$ then we simply define its multiplicity to be zero. If $\mathcal{A}$ is in fact a hyperplane arrangement then this algebraic definition of multiplicity coincides with the geometric one given above [BZ06, Lemma 3.4].

Theorems 2.3 and 2.5 will thus follow by interpreting the various types of generalized Golomb rulers as lattice points in inside-out polytopes. From their definitions via linear inequations it is not surprising that this will be possible, but we give explicit combinatorial descriptions of the hyperplanes and subspaces in order to be able to calculate examples.

Returning to the original case of Golomb rulers, the combinatorial types are related to acyclic orientations of a certain mixed graph. We have already seen that combinatorial types are in bijection with open regions of an inside-out polytope $(\Delta_{m-1},\mathcal{G}_{m})$, where $\mathcal{G}_{m}$ is the hyperplane arrangement given by the hyperplanes (1) for each pair of consecutive subsets of $[m]$, so we will work directly with these regions.

We first review the construction in [BBP12] of an injective map $\phi$ from regions of the Golomb inside-out polytope $(\Delta_{m-1},\mathcal{G}_{m})$ to acyclic orientations of the Golomb (mixed) graph $\Gamma_{m}$. To do this, let $R$ be a region of the inside-out polytope. Then $R$ is the intersection of half-spaces given by inequalities of the form

where $U$ and $V$ range over all pairs of consecutive subsets of $[m]$. We may assume that both sets are proper, since otherwise the inequality would hold over the entire positive orthant (in particular, over all of $\Delta_{m}$.) Furthermore, we may restrict to disjoint sets because if $A$ and $B$ are consecutive subsets that are not disjoint, then $U:=A\setminus B$, $V:=B\setminus A$, and $W:=A\cap B$ are all consecutive sets, and

For a pair of disjoint proper consecutive sets (dpcs) $(U,V)$, orient the edge $UV$ of $\Gamma_{m}$ by $U\rightarrow V$. If $W$ is disjoint from both $U$ and $V$ and if $A=U\cup W$ and $B=V\cup W$ are consecutive sets, then orient the edge $AB$ by $A\rightarrow B$. Thus the orientation is coherent. It is total because (again) any pair of consecutive sets $A,B$ can be decomposed in this way. Finally, it is acyclic because if there were a cycle then we could take the multiset union $M$ of the sets along the whole cycle and conclude that $\sum_{j\in M}z_{j}<\sum_{j\in M}z_{j}$, which is impossible.

In this section we generalize the injection described in Section 4 to the case of $B_{h}$-sets.

For Golomb graphs, the vertices are consecutive subsets of $[m]$. Here we would need to consider collections of such sets, but in light of the non-uniqueness illustrated in Remark 3.5, it is better to consider unions with repetition of such sets, which are multisets. We represent a multiset $A=\{1^{a_{1}},2^{a_{2}},\dots,m^{a_{m}}\}$ by the vector $\mathbf{a}=(a_{1},a_{2},\dots,a_{m})\in\mathbb{N}^{m}$. In this way, multiset union corresponds to addition of vectors, and multiset containment $A\subseteq B$ corresponds to $\mathbf{a}\leq\mathbf{b}$ with respect to the standard partial order on $\mathbb{N}^{m}$. A single consecutive set $U=\{j,j+1,\dots k\}$ corresponds to a consecutive vector $\mathbf{e}_{[j,k]}:=\mathbf{e}_{j}+\mathbf{e}_{j+1}+\dots+\mathbf{e}_{k}$.

Next, we need to know which pairs of vectors correspond to inequations defining $B_{h}$-sets. In particular, given a vector $y^{\mathbf{a}}$, we need to know the minimum number of consective vectors whose sum is $\mathbf{a}$. The following definition and lemma will help us do this.

Now the Golomb graph is complete in the sense that there is either a directed or an undirected edge between every pair of vertices. However, the analogous graph that we will define for $B_{h}$-sets cannot be complete for the following reason.

On the other hand, it will not suffice to consider only edges between vectors $\mathbf{a}$ and $\mathbf{b}$ such that the sum of the climbs of $\mathbf{a}$ and of $\mathbf{b}$ is at most $h$. The reason is as follows.

In determining which vertices and edges to include in our graph, we must also take into account that climb is not monotonic. For example, the climb of $(1,0,1)$ is two and the climb of $(1,1,1)$ is only one. However, we have the following result for pairs of vectors.