Proof. Suppose for contradiction that \(\alpha:=\mathop{\mathrm{diam}}({\cal G}) \le g + 2b - 3\). The discrete interval \([0,\alpha]\) contains exactly \(\alpha + 1\) integers. Therefore, the exact number of holes \({\cal H}={\cal H}({\cal G})\) is \[|{\cal H}| = (\alpha + 1) - |{\cal G}| = \alpha + 1 - g - b.\]

We analyze the representation function for \(d = 1\). In the complete interval \([0,\alpha]\), there are \(\alpha\) pairs of distance 1. Each hole \(h \in {\cal H}\) removes at most two such pairs: \((h-1, h)\) and \((h, h+1)\). Therefore, \[\begin{align} r_{{\cal G}-{\cal G}}(1) &\ge \alpha - 2|{\cal H}| \\ &= \alpha - 2(\alpha + 1 - g - b) \\ &= 2g + 2b - \alpha - 2 \\ &\ge 2g + 2b - (g + 2b - 3) - 2 \\ &= g+1. \end{align}\] Since \(g+1 > g\), this contradicts the definition of a \(g\)-Golomb ruler. Hence, \(\alpha \ge g+2b-2\). ◻

Proof. Applying the general lower bound from Lemma 6, we know that \(G(g, g+b) \ge g + 2b - 2\). To show equality, we give minimal sets \({\cal G}\) for each case (the shown sets are not always the unique sets with minimum diameter). It is straightforward to verify that these constructions satisfy \(r_{{\cal G}-{\cal G}}(d) \le g\) for all valid distances and are therefore minimal \(g\)-Golomb rulers.

\[\begin{array}{|r|cclc|}\hline \text{valid g} &b & n & \text{g-Golomb Ruler}& G(g,g+b) \\ \hline g \ge 1 & 1 & g+1 & [0, g] & g \\ g \ge 1 & 2 & g+2 & [0, g] \cup \{g+2\} & g+2 \\ g \ge 2 & 3 & g+3 & [0, g-1] \cup \{g+1, g+2\} \cup \{g+4\} & g+4\\ g \ge 4& 4 & g+4 & [0, g-2] \cup \{g, g+1\} \cup \{g+3\} \cup \{g+5, g+6\} & g+6 \\ \hline \end{array}\]

We show these rulers visually in Figure 1. ◻

Proof. Using \(\{ x \}\) for the fractional part of \(x\), i.e., \(x=\lfloor x \rfloor+\{ x \}\), we have \[\begin{align} W_k(m) &= \lfloor \varphi(m+k) \rfloor+\{ \varphi(m+k) \} - \lfloor \varphi(m) \rfloor - \{ \varphi(m) \} \\ &= h_{m+k}-h_m +\{ \varphi(m+k) \}-\{ \varphi(m) \}. \end{align}\] The difference of two fractional parts is in \((-1,1)\), and consequently \(W_k(m)\in (d-1,d+1)\). ◻

Proof. We may write \(\widetilde{W}_k(x) = C\int_{x+2}^{x+k+2} \frac{3}{2}\,t^{1/2}\,dt\). Differentiating with respect to \(x\): \[\begin{align} W_k'(x) = \widetilde{W}_k'(x) &= \frac{3C}{2}\left[(x+k+2)^{1/2} - (x+2)^{1/2}\right] > 0 \\ W_k''(x) = \widetilde{W}_k''(x) &= \frac{3C}{4}\left[(x+k+2)^{-1/2} - (x+2)^{-1/2}\right] < 0 \end{align}\] The signs follow because \(x + k + 2 > x + 2 \ge 3\), so \(W_k\) is strictly increasing and strictly concave on \([1, \infty)\).

The lower bound follows from the concavity of \(f(t) = \frac{3}{2}t^{1/2}\): the chord from \((x+2,f(x+2))\) to \((x+k+2,f(x+k+2))\) lies below the graph, so the integral exceeds the trapezoidal approximation, giving \[\widetilde{W}_k(x) > C \cdot \frac{k}{2}\big(f(x+2) + f(x+k+2)\big) = \frac{3Ck}{4}\big((x+2)^{1/2} + (x+k+2)^{1/2}\big).\qedhere\] ◻

Proof. Since \(W_k(x)\) is strictly increasing for \(x \ge 1\), its minimum on \(\{m \ge 1\}\) occurs at \(m = 1\): \[W_k(1) = C\bigl((k+3)^{3/2} - 3^{3/2} - k\bigr).\] The function \(g(x) := C\bigl((x+3)^{3/2} - 3^{3/2} - x\bigr)\) is strictly increasing for \(x \ge 1\), since \(g'(x) = C\bigl(\frac{3}{2}(x+3)^{1/2} - 1\bigr) > 0\). Therefore, if \(k > K\), then \(W_k(1) = g(k) > g(K) = d+1\). By monotonicity, \(W_k(m) > d+1\) for all \(m \ge 1\), and so \(N_k(d) = 0\). ◻

Proof. If \(W_k(1) \ge d+1\), then \(N_k(d)=0\) by monotonicity; the bound holds trivially. We now assume \(W_k(1) < d+1\).

Since \(W_k\) is continuous, strictly increasing, and unbounded, the condition \(W_k(x) \in (d-1, d+1)\) defines a unique maximal open interval \((x_L, x_R) \subseteq (1,\infty)\), where \(W_k(x_L) = \max\{W_k(1),d-1\}\) and \(W_k(x_R) = d+1\). We have \[\begin{align} N_k(d)&=\#\{ m \in {\mathbb{N}}: x_L < m < x_R\} \le x_R-x_L+1. \end{align}\]

Since \(W_k(x_L) \geq d-1\), we have \(W_k(x_R) - W_k(x_L) \leq 2\). By the Mean Value Theorem, there exists \(\xi \in (x_L, x_R)\) with \(W_k'(\xi)(x_R - x_L) \leq 2\). Since \(W_k\) is concave, \(W_k'(\xi) > W_k'(x_R)\), giving \[\label{eq:discrete95boundv2} N_k(d) \leq x_R - x_L + 1 \leq \frac{2}{W_k'(x_R)} + 1.\tag{1}\]

To bound \(W_k'(x_R)\) from below, we use the derivative in the form \[\label{eq:derivativev2} W_k'(x) = \frac{3Ck/2}{(x+k+2)^{1/2} + (x+2)^{1/2}}.\tag{2}\] At the right boundary, \(W_k(x_R) = d+1\) means \(\widetilde{W}_k(x_R) = d+1+Ck\). Lemma 9 applied at \(x_R\) gives \[\frac{3Ck}{4}\bigl((x_R+2)^{1/2} + (x_R+k+2)^{1/2}\bigr)< d+1+Ck,\] from which we conclude that \[(x_R+2)^{1/2} + (x_R+k+2)^{1/2} < \frac{4(d+1+Ck)}{3Ck}.\] The derivative \(W_k'(x_R)\) given in Equation 2 now yields \[W_k'(x_R) > \frac{3Ck/2}{{4(d+1+Ck)}/({3Ck})} = \frac{9C^2k^2}{8(d+1+Ck)}.\] Inserting into 1 : \[N_k(d) \leq \frac{16(d+1+Ck)}{9C^2k^2} + 1 = \frac{16(d+1)}{9C^2k^2} + \frac{16}{9Ck} + 1.\qedhere\] ◻

Proof. We show that \(r_{{\cal S}-{\cal S}}(d) \le d - 1\) for all \(d \ge 1\). The proof is divided into two cases, according to whether \(d \le 4475\).

First, if \(d\le 4475\), we proceed as follows. The minimum gap in \({\cal S}\) is \(h_1 - h_0 = 3\), so \(r_{{\cal S}-{\cal S}}(d) = 0 \leq d-1\) for \(d \leq 2\). For \(3 \le d \le 4475\), the inequality \(r_{{\cal S}-{\cal S}}(d) \le d-1\) is verified by direct computation. For each \(d\), the contribution from \(h_0\) is at most \(1\) (since \(\varphi\) is strictly increasing, at most one \(k\) satisfies \(h_k = d\)). For each \(k \leq \lfloor K \rfloor\), the values \(x_L\) and \(x_R\) satisfying \[W_k(x_L) = d-1 \quad \text{and} \quad W_k(x_R) = d+1\] are determined, and the exact representation count is computed by checking \(h_{m+k} - h_m = d\) for each integer \(m\) in \((x_L, x_R)\). The total count, including the \(h_0\) contribution, is verified to be at most \(d-1\) in every case.

Now, suppose that \(d \ge 4476\). By Lemma 10, only gap sizes \(k\) up to \(\lfloor K \rfloor\) contribute to the tail sum \(\sum_k N_k(d)\). Since \(\varphi\) is strictly increasing, the \(h_0\) term contributes at most \(1\) to \(r_{{\cal S}-{\cal S}}(d)\). Since \(r_{{\cal S}-{\cal S}}(d)\) is an integer, it suffices to show that the upper bound is strictly less than \(d\), as this implies \(r_{{\cal S}-{\cal S}}(d) \le d-1\). Applying Lemma 11 and using \(\sum_{k=1}^{\infty} \frac{1}{k^2} = \frac{\pi^2}{6}\) and \(\sum_{k=1}^{N} \frac{1}{k} \le 1 + \ln N\): \[\label{eq:rd95boundv2} r_{{\cal S}-{\cal S}}(d) \le 1 + \sum_{k=1}^{\lfloor K \rfloor}\biggl(\frac{16(d+1)}{9C^2 k^2} + \frac{16}{9Ck} + 1\biggr) < 1 + \frac{8\pi^2(d+1)}{27C^2} + \frac{16(1+\ln K)}{9C} + K =: 1 + B(d).\tag{3}\] We must show \(1 + B(d) < d\) for all \(d \ge 4476\).

Now, we examine the reason for the specific value of \(C\). The bound \(B(d)\) consists of three terms. The first, \(\frac{8\pi^2(d+1)}{27C^2}\), is linear in \(d\). The second and third terms, \(\frac{16(1+\ln K)}{9C}\) and \(K\), are sublinear. For \(B(d)\) to be less than \(d\) for all large \(d\), the coefficient of the leading term must satisfy \(\frac{8\pi^2}{27C^2} < 1\). Thus,the condition on \(C\) is \[\label{eq:alpha95conditionv2} \frac{8\pi^2}{27C^2} < 1 \qquad\iff\qquad C > \sqrt{\frac{8\pi^2}{27}} = \frac{2\pi\sqrt{2}}{3\sqrt{3}} \approx 1.71.\tag{4}\] If \(C\) is at or below this threshold, the linear term alone already exceeds \(d\) for large \(d\). If \(C\) is above the threshold, the linear term grows strictly slower than \(d\). So, we choose \(C = \frac{7}{4}\) as it allows for viable direct computation \((d\le4475)\).

Now we verify \(d \ge 4476\).

Define \(\epsilon(d) := (d-1) - B(d)\), so that \(\epsilon(d) > 0\) implies \(1 + B(d) < d\). Substituting \(C = \frac{7}{4}\) and writing \(\beta = \frac{128\pi^2}{1323}\) for the value of \(\frac{8\pi^2}{27C^2}\) at \(C = \frac{7}{4}\): \[\epsilon(d) = (1-\beta)(d+1) - 2 - \frac{64(1+\ln K)}{63} - K.\]

Differentiating implicitly (using \(K\) as a function of \(d\)): \[\epsilon'(d) = (1-\beta) - \left(\frac{64}{63 K} + 1\right)K'.\] The derivative \(K'\) is obtained by differentiating the defining relation \(C\bigl((K+3)^{3/2} - 3^{3/2} - K\bigr) = d+1\): \[K' = \frac{1}{C\bigl(\tfrac{3}{2}(K+3)^{1/2} - 1\bigr)}.\]

Since \(\pi^2 < 9.87\), we have \(\beta < 0.955\), so \(1 - \beta > 0.045\). For \(d \ge 4476\), we have \(K > 194\), so \((K+3)^{1/2} > 14\), giving \[K' < \frac{4}{7\bigl(\tfrac{3}{2}\cdot 14 - 1\bigr)} = \frac{4}{140} = \frac{1}{35} < 0.029.\] Furthermore, \(\frac{64}{63 K} + 1 < \frac{64}{63 \cdot 194} + 1 < 1.006\). Therefore \[\epsilon'(d) > 0.045 - 0.029 \cdot 1.006 > 0.045 - 0.030 = 0.015 > 0.\] Thus \(\epsilon'(d) > 0\) for all \(d \ge 4476\).

A direct computation gives \(\epsilon(4476) > 0\). Since \(\epsilon\) is increasing for all \(d \ge 4476\), it follows that \(\epsilon(d) > 0\) for all \(d \ge 4476\), and hence \(r_{{\cal S}-{\cal S}}(d) \le d-1\) in this range.

Both cases confirm \(r_{{\cal S}-{\cal S}}(d) \le d-1\) for all \(d \ge 1\), so \({\cal S}\) is an LM ruler. The diameter bound \(\mathop{\mathrm{diam}}({\cal S}_n) = h_{n-1} \le C\bigl((n+1)^{3/2} - (n+1)\bigr)\) follows directly from the definition of \(h_m\). ◻

Proof. Suppose that \({\cal A}=\{\lambda_1<\dots<\lambda_n\}\), and set \(s_i=\lambda_{i+1}-\lambda_i\) to be the first differences. Further, let \[s_{(1)} \leq s_{(2)} \leq \cdots \leq s_{(n-1)}\] be a reordering of the first differences \(s_1,\dots,s_{n-1}\).

By the definition of LM ruler, there are at most \(d-1\) differences of size \(d\), and so there are at most \[\sum_{d=1}^\ell (d-1) = \frac{\ell(\ell-1)}{2}\] first differences of size at most \(\ell\). Taking \(\ell=\sqrt{2i}\), we see that there are at most \(\sqrt{2i}(\sqrt{2i}-1)/2<i\) first differences of size \(\sqrt{2i}\) or smaller, whence \[\label{eq:greedy} s_{(i)}>\sqrt{2i}.\tag{5}\]

The diameter equals the sum of the first differences, \[\mathop{\mathrm{diam}}({\cal A}) = \sum_{i=1}^{n-1} s_i = \sum_{i=1}^{n-1} s_{(i)},\] and applying Inequality 5 to each term gives \[\mathop{\mathrm{diam}}({\cal A}) \geq \sum_{i=1}^{n-1} \sqrt{2i} = \sqrt{2}\sum_{i=1}^{n-1}\sqrt{i}.\] Since \(\sqrt{t}\) is increasing, \(\sqrt{i} \geq \int_{i-1}^{i}\sqrt{t}\,dt\) for each \(i \geq 1\). Summing over \(i\) gives \[\sum_{i=1}^{n-1}\sqrt{i} \;\geq\; \sum_{i=1}^{n-1}\int_{i-1}^{i}\sqrt{t}\,dt = \int_0^{n-1}\sqrt{t}\,dt = \frac{2}{3}(n-1)^{3/2}.\] Therefore, \[\mathop{\mathrm{diam}}({\cal A}) \geq \sqrt{2} \cdot \frac{2}{3}(n-1)^{3/2},\] as claimed. ◻

Proof. The setup can be visualized as follows.

If \(d>g+2b-2=\mathop{\mathrm{diam}}({\cal I})\), then no pair in \({\cal I}\) has difference \(d\), so \(r_{{\cal G}-{\cal G}}(d)=0\).

Now suppose \(b\le d\le g+2b-2\). In the full interval \({\cal I}\), the number of pairs with difference \(d\) is \[r_{{\cal I}-{\cal I}}(d)=g+2b-2-d+1=g+2b-1-d.\]

We consider three ranges of \(d\), according to whether \(d\ge 2b-1\). If \(d\ge 2b-1\), then \[r_{{\cal G}-{\cal G}}(d)\le r_{{\cal I}-{\cal I}}(d)=g+2b-1-d\le g.\] On the other hand, suppose that \(b \le d \le 2b-2\). Every pair of elements of \({\cal G}\) with difference \(d\) is a pair of elements of \({\cal I}\) with difference \(d\) in which neither element of the pair is in \({\cal H}\); ergo, we have \[\begin{align} r_{{\cal G}-{\cal G}}(d) &=\#\left\{(x-d,x): x,x-d\in {\cal G}\right\} \notag\\ &=\#\left\{(i-d,i): i,i-d \in {\cal I}\right\} \notag\\ &\qquad\qquad -\#\left\{(h-d,h) : (h\in{\cal H}\text{ or } h-d \in {\cal H}) \text{ and } (h,h-d \in {\cal I}) \right\} \notag\\ &= g+2b-1-d -\#\left\{h \in [d,g+2b-2] : h\in{\cal H}\text{ or } h-d \in {\cal H}\right\} \label{eq:r40d4132as32holes}\\ &\le g+2b-1-d - | {\cal H}\cap [d,g+2b-2]|.\notag \end{align}\tag{6}\] If \(d=b\), then \({\cal H}\cap [d,g+2b-2]={\cal H}\), and we have shown that \(r_{{\cal G}-{\cal G}}(b) \le g\). If \(d>b\), then \({\cal H}\cap [d,g+2b-2] \subseteq {\cal H}\setminus[b,d-1]\), in which case \[| {\cal H}\cap [d,g+2b-2]| \ge |{\cal H}|-|[b,d-1]|=(b-1)-(d-b).\] It follows that \(r_{{\cal G}-{\cal G}}(d) \le g\). ◻

Proof of Theorem 4.. By Lemma 6, we know that \(G(g,g+b)\ge g+2b-2\). We need to show that, given \(g,b\) with \(g\ge L(b-1)+1\), there is a \(g\)-Golomb ruler \({\cal G}\) with \(g+b\) elements contained in \({\cal I}:= [0,g+2b-2]\).

In Lemma 7, we gave examples that achieve this for \(b=1,g\ge 1 = L(0)+1\), \(b=2,g\ge 1=L(1)+1\), \(b=3,g\ge 2, L(2)+1=3\), and \(b=4,g\ge 4, L(3)+1=6\). Recall that the value of \(L(n)\) for \(0\le n \le 18\) is given in Table 2. We henceforth assume \(b\ge 5\).

Our strategy is to take an LM ruler contained in \([b,g+b-1]\) with \(b-1\) elements as \({\cal H}\), and set \({\cal G}:={\cal I}\setminus {\cal H}\).

By Definition 2, there is an LM ruler with \(b-1\) elements and diameter \(L(b-1)\). If \(g\ge L(b-1)+1\), then we can take that ruler to be in the interval \([b,g+b-1]\), which has diameter \(g-1\). We set this as \({\cal H}\), our set of holes.

By Lemma 14, the placement of \({\cal H}\) in \([b,g+b-1]\) immediately gives \[r_{{\cal G}-{\cal G}}(d)\le g\] for all \(d\ge b\), with no further conditions on \({\cal H}\). We now focus on the distances \(d\le b-1\).

By Line 6 in the proof of Lemma 14, we have \[r_{{\cal G}-{\cal G}}(d) = g+2b-1-d -\#\left\{h \in [d,g+2b-2] : h\in{\cal H}\text{ or } h-d \in {\cal H}\right\} .\] Thus, to show that \(r_{{\cal G}-{\cal G}}(d) \le g\), it is sufficient to show that \[\label{eq:to32show} \#\left\{h \in [d,g+2b-2] : h\in{\cal H}\text{ or } h-d \in {\cal H}\right\} \ge 2b-1-d.\tag{7}\]

With \(d\le b-1\), every element of \[{\cal H}\subseteq[b,g+b-1]\subseteq [d,g+b-1+d]\subseteq[d,b+2b-2]\] is counted as both an \(h\) and an \(h-d\), and so \[\begin{align} \#\big\{h \in [d,g+2b-2]&\, : h\in{\cal H}\text{ or } h-d \in {\cal H}\big\} \\ &=|{\cal H}|+|{\cal H}|- \#\left\{h \in [b,g+b-1] : h\in{\cal H}\text{ and } h-d \in {\cal H}\right\} \\ &= 2(b-1)-r_{{\cal H}-{\cal H}}(d). \end{align}\] As \({\cal H}\) is an LM ruler, we know that \(r_{{\cal H}-{\cal H}}(d)\le d-1\), which establishes the inequality on Line 7 . Thus, the main claim of Theorem 4 is proved.

In Theorem 12, we establish that \(L(n+1) \le \frac{7}{4}(n^{3/2}-n)\), from which we know that if \(g\ge \frac{7}{4}(b^{3/2}-b)+1\), then \(G(g,g+b)=g+2b-2\). ◻