Constructing Thick B_{h}-Sets

Kevin O’Bryant City University of New York The Graduate Center and The College of Staten Island 2800 Victory Boulevard, 1S215 Staten Island, NY 10314 USA

                  kevin.obryant@csi.cuny.edu

Abstract A subset A of a commutative semigroup X is called a B_{h}-set in X if the only

solutions to

a_{1} + ⋯ + a_{h} = b_{1} + ⋯ + b_{h}, a_{i}, b_{i} ∈ A

are the trivial solutions {a_{1}, …, a_{h}} = {b_{1}, …, b_{h}} (as multisets). With h = 2 and X = ℤ, these sets are also known as Sidon sets, Golomb rulers, and Babcock sets. In this work, we generalize constructions of Bose-Chowla and Singer and give the resultant bounds on the diameter of a k element B_{h}-set in ℤ for h = 3, k ≤ 28 and h = 4, k ≤ 16. We conclude with a list of open problems.

1 Introduction

A subset A of a commutative semigroup X is called a B_{h}-set in X if the only solutions to

a_{1} + ⋯ + a_{h} = b_{1} + ⋯ + b_{h}, a_{i}, b_{i} ∈ A

are the trivial solutions {a_{1}, …, a_{h}} = {b_{1}, …, b_{h}} (as multisets). With h = 2 and X = ℤ, these sets are also known as Sidon sets, Golomb rulers, and Babcock sets. For an extensive bibliography of related mathematics literature we direct the reader to [14]. The purpose of this work is to give new parameterized constructions of B_{h}-sets for h ≥ 3, and to give criteria on the parameters for these sets to be affinely inequivalent.

One application of B_{h}-sets in ℤ is in electrical engineering; this literature starts in Babcock [1] and continues for dozens of articles in IEEE journals not covered by Math Sci-Net. Specifically, a nonlinear amplifier for channel frequencies a_{1}, a_{2}, a_{3}, … produces “ghost” signals at frequencies of the form a_{1} + a_{2}, a_{1} + a_{2} − a_{3}, and so on. The strongest relevant ghosts are at a_{1} + a_{2} − a_{3} (third-order intermodulation) and a_{1} + a_{2} + a_{3} − a_{4} − a_{5} (fifth-order intermodulation). Thus, the set of frequencies should avoid equations of the sort a_{4} = a_{1} +a_{2} −a_{3} and a_{6} = a_{1} + a_{2} + a_{3} − a_{4} − a_{5}. That is, to avoid third-order intermodulation, the channels should form a B_{2}-set, and to avoid fifth-order intermodulation, the channels should be a B_{3}-set.

The first published usage of the “B_{h}” terminology that we have found is in the introduction of the famous Erdős & Turán paper [8], where they state “Such sequences, called B_{2} sequences by Sidon, occur in the theory of Fourier series.” Singer [17] had already constructed thick finite B_{h}-sets in 1939, and Bose gave a different thick finite construction of B_{2}-sets in [3], which was generalized to B_{h}-sets by Bose & Chowla in [4]. The constructions given in this work subsume those of Singer and Bose & Chowla.

Definition 1. For an integer h ≥ 2 and a prime power q, set M = q^{h} − 1. For a generator θ of the multiplicative group 𝔽_{q^{h}}^{×}, and b ∈ ℤ/(q^{h} − 1)ℤ for which θ^{b} has algebraic degree h over 𝔽_{q}, we define the set

BoseCh_{h}(q, b) := {a ∈ ℤ/Mℤ : θ^{a} = θ^{b} + v, v ∈ 𝔽_{q}} .

Definition 2. For an integer h ≥ 2, a prime power q, set M = \frac{q^{h+1}−1}{q−1}. For a generator θ of the multiplicative group 𝔽_{q^{h+1}}^{×}, and b ∈ ℤ/Mℤ for which θ^{b} has algebraic degree h + 1, we define the set

Singer_{h}(q, b) := {a ∈ ℤ/Mℤ : θ^{a} = uθ^{b} + v, u, v ∈ 𝔽_{q}} .

We comment that it may seem that the modulus should be q^{h+1} − 1. However, for any a with θ^{a} = uθ^{b} + v, one also has θ^{a+(q^{h+1}−1)/(q−1)} = u_{1}θ^{b} + v_{1}, where u_{1}, v_{1} are in 𝔽_{q} because all of u, v, θ^{(q^{h+1}−1)/(q−1)} are in 𝔽_{q}.

A cautious reader will object that the choice of the generator impacts the right side of these definitions, and so should be included in the notation BoseCh_{h}(q, b) and Singer_{h}(q, b). While the choice of θ does matter, we will eventually show that it does not matter in a meaningful way. To avoid this technicality, we set θ in the above definitions to be a root of the Conway polynomial [11] that generates the appropriate field. The only facts about Conway polynomials that we will use is that for each prime power q = p^{e}, the Conway polynomial C_{p,e}(x) ∈ 𝔽_{p}[x] is uniquely defined, irreducible, and

𝔽_{p}[x]/C_{p,e}(x) ≅ 𝔽_{q}, ⟨θ⟩ = 𝔽_{q}^{×}.

There are additional properties that make Conway polynomials a computationally pleasant approach to working in finite fields, particularly concerning subfields, and Luebeck [12] has provided an extensive database. The specific presentation of the finite fields is not relevant to the theory in this work, and is only useful if one wants to compare explicit computations.

The b = 1 cases of the following theorem are exactly the constructions of Bose-Chowla and Singer. The first sentence of Theorem 3 is Observation #1 in [9].

Theorem 3. If h, q, b are in the domain of BoseCh, then BoseCh_{h}(q, b) is a B_{h} set in ℤ/(q^{h} − 1)ℤ with q distinct elements.

If h, q, b are in the domain of Singer, then Singer_{h}(q, b) is a B_{h} set in ℤ/(\frac{q^{h+1}−1}{q−1}ℤ) with q + 1 distinct elements.

We say that sets A_{1}, A_{2} ∈ ℤ/Mℤ are affinely equivalent, writing A_{1} ∼ A_{2}, if there is some d relatively prime to M and some s with A_{2} = {da + s : a ∈ A_{1}}. Clearly, if A_{1} is a B_{h} set in ℤ/Mℤ and A_{1} ∼ A_{2}, then A_{2} is also a B_{h} set in ℤ/Mℤ. We use the notation d ∗ A := {da : a ∈ A} and A + s := {a + s : a ∈ A} to denote dilations and translations of sets.

We identify when the B_{h}-sets given in Theorem 3 are affinely equivalent in the following theorem.

Theorem 4. Suppose that h, q = p^{r}, b and h, q, e are in the domain of BoseCh. If (i) b ≡ e (mod \frac{q^{h}−1}{q−1}), or

(ii) θ^{b} − θ^{e} ∈ 𝔽_{q}, or
(iii) b ≡ p^{i}e (mod q^{h} − 1) for some integer i,

then BoseCh_{h}(q, b) ∼ BoseCh_{h}(q, e).

Suppose that h, q, b and h, q, e are in the domain of Singer. If (iv) b ≡ e (mod \frac{q^{h+1}−1}{q−1}), or

(v) b ≡ p^{i}e (mod q^{h+1} − 1) for some integer i, where p is the prime that divides q, or (vi) θ^{b} − θ^{e} ∈ 𝔽_{q}, or (vii) rθ^{b} + tθ^{e+b} + wθ^{e} ∈ 𝔽_{q} for some r, t, w ∈ 𝔽_{q}, and r, t are not both 0,

then Singer_{h}(q, b) ∼ Singer_{h}(q, e).

One sad consequence is that for h = 2 and any allowed q, b, e, we have BoseCh_{2}(q, b) ∼ BoseCh_{2}(q, e). That is, we do not produce any new (up to affine equivalence) Sidon sets. However, BoseCh_{3}(5, 1) ≁ BoseCh_{3}(5, 4) and for h > 2 and most (but not all) prime powers q we generate previously unknown B_{h}-sets.

In the number theory literature, the thickness of a B_{h}-set A is sometimes measured by a lower bound on the cardinality |A| in terms of the diameter max A − min A, while in recreational, computational, and engineering literature it is more common to see an upper bound on the diameter in terms of cardinality. To serve all audiences, we define both R_{h}(n) as the maximum possible cardinality of a B_{h}-set contained in [1, n], and R_{h}^{−1}(k) be the smallest n such that there is a B_{h}-set with k elements contained in [1, n].

Sequence \underline{A227358} from the On-Line Encyclopedia of Integer Sequences (OEIS) gives the minimum diameter of B_{3}-sets with up to 10 elements. We are not aware of any such computation for h > 3. As comparison, we have also computed the smallest diameters achievable by any subset of any shift of dilations of BoseCh_{3}(q, b), BoseCh_{4}(q, b), Singer_{3}(q, b), and Singer_{4}(q, b) for all b and small q (projected from ℤ/Mℤ to ℤ in the obvious way). In my opinion, this data suggests that the BoseCh and Singer constructions are not close to optimal for h > 2, in contrast to the apparent situation for h = 2.

The lower bound on R_{h}(n) and upper bound on R_{h}^{−1}(k) implied by our constructions is not better than that achieved by Singer’s construction alone. Nevertheless, we give several statements using up-to-date results on the distribution of primes, as these results are frequently misstated in the literature.

Theorem 5.

(a) For all n ∈ ℤ, we have R_{h}(n) ≥ n^{1/h} − 2^{44}n^{154/(155h)} and R_{h}^{−1}(k) ≤ k^{h} + 3^{155h}k^{h−1/155}.

(b) If k, n ≥ e^{e^{34}}, we have R_{h}(n) ≥ n^{1/h} − 7n^{2/(3h)} and R_{h}^{−1}(k) ≤ k^{h} + (3k)^{h−1/3}.

(c) If k, n are sufficiently large, then R_{h}(n) ≥ n^{1/h}−n^{21/(40h)} and R_{h}^{−1}(k) ≤ k^{h}+2^{h}k^{h−19/40}.

(d) If the Riemann Hypothesis holds, then

R_{h}^{−1}(k) < k^{h} + log(20k)k^{h−1/2} + 2k^{h−1} log^{2h}(20k), R_{h}(n) ≥ n^{1/h} − (7 + \frac{log n}{h})n^{1/(2h)}.

2 Two explicit examples

2.1 A BoseCh example.

Let h = 3 and q = 11; we first compute the various BoseCh_{3}(11, b), and will then give Singer_{3}(11, b).

The Conway polynomial for 11^{3} is C_{11,3}(x) = 9 + 2x + x^{3} ∈ 𝔽_{11}[x]. We have 𝔽_{q^{3}} ≅ 𝔽_{q}[x]/C_{11,3}(x), and θ (whose minimal polynomial is C_{11,3}(x)) generates the multiplicative group.

Our first task is to find a suitably small set of candidates for b. From Theorem 4(i), we only need to consider values between 1 and \frac{q^{h}−1}{q−1} = 133, inclusive. As the 𝔽_{q^{3}} has only 𝔽_{q} as a subfield, only b = 133 has θ^{b} having algebraic degree less than 3. Further, by Theorem 4(ii) each b is equivalent to 11b and 11^{2}b. These equivalences combine to give additional equivalences, e.g., BoseCh_{3}(11, 3) ∼ BoseCh_{3}(11, 11^{2} · 3) ∼ BoseCh_{3}(11, 97). The second condition given in Theorem 4 is much harder to use, as it requires arithmetic inside the field. For instance,

θ^{21} − θ^{1} = (θ^{3})^{7} − θ = (−9 − 2θ)^{7} − θ = 2^{7}(1 − θ)^{7} − θ = ⋯ = 3 ∈ 𝔽_{11},

and so BoseCh_{3}(11, 1) ∼ BoseCh_{3}(11, 21). With some computerized labor, we find that each b value is equivalent to one of 1, 2, 4, 6. We have used the Conway polynomial representation, but any finite field representation will lead to four equivalence classes for b, but not necessarily these as the smallest representatives of each class.

We then compute inside the field using Definition 1 that

BoseCh_{3}(11, 1) = {1, 21, 65, 100, 111, 238, 324, 523, 535, 1137, 1214},
BoseCh_{3}(11, 2) = {2, 16, 132, 237, 330, 338, 389, 419, 764, 1174, 1254},
BoseCh_{3}(11, 4) = {4, 56, 116, 174, 354, 626, 782, 905, 979, 1147, 1183}, and
BoseCh_{3}(11, 6) = {6, 152, 261, 295, 311, 352, 367, 891, 1092, 1113, 1228}.

By Theorem 3, these four sets are B_{3}-sets in ℤ/1330ℤ, and by direct computation we can verify that no two are affinely equivalent. We are not aware of any affine equivalences that are not dictated by Theorem 4.

By directly examining all sets affinely equivalent to these, we notice that

167 ∗ BoseCh_{3}(11, 6) + 330 = {1, 2, 27, 167, 385, 397, 439, 444, 484, 586, 594}

has a particularly small diameter. Consequently R_{3}(594) ≥ 11 and R_{3}^{−1}(11) ≤ 594.

2.2 A Singer example.

We now compute Singer_{3}(11, b). The Conway polynomial for 11^{4} is C_{11,4}(x) = 2 + 10x + 8x^{2} + x^{4} ∈ 𝔽_{11}[x].

Our first task is find a suitably small set of candidates for b. From Theorem 4(iv), we only need to consider values between 1 and \frac{q^{h+1}−1}{q−1} = 1464. We require θ^{b} to have algebraic degree h + 1 = 4, and that reduces the number of b values to 1452. Including Theorem 4(v) reduces the number of possible inequivalent b values to 366. Theorem 4(vi) is significantly more computationally intensive, but reduces the number of inequivalent to b values to at most 36. Using Theorem 4(vii) is much more time-consuming. With the additional assumptions that r = 0, t = 1, we find that each b is equivalent to one of 1, 2, 3, 6, 8 or 14. We have the B_{3}-sets in ℤ/1464ℤ:

Singer_{3}(11, 1) = {1, 418, 502, 679, 846, 1050, 1164, 1187, 1285, 1319, 1339, 1464}
Singer_{3}(11, 2) = {2, 273, 377, 432, 500, 665, 674, 887, 908, 1192, 1257, 1464}
Singer_{3}(11, 3) = {3, 201, 309, 425, 664, 700, 876, 1061, 1105, 1239, 1357, 1464}
Singer_{3}(11, 6) = {6, 76, 388, 593, 702, 734, 950, 1147, 1208, 1440, 1457, 1464}
Singer_{3}(11, 8) = {8, 128, 582, 624, 739, 774, 841, 922, 1143, 1311, 1369, 1464}
Singer_{3}(11, 14) = {14, 40, 85, 492, 529, 621, 683, 722, 940, 969, 1151, 1464}

By direct computation, no two of these are affinely equivalent. We are not aware of any affine equivalences that are not dictated by Theorem 4.

We further find, after some computation, that

481 ∗ Singer_{3}(11, 1) + 102 = {1, 4, 36, 72, 89, 102, 229, 379, 583, 592, 629, 738}.

Thus, R_{3}(738) ≥ 12 and R_{3}^{−1}(12) ≤ 738. Moreover,

653 ∗ Singer_{3}(11, 2) + 564 = {1, 22, 31, 81, 92, 108, 225, 406, 564, 568, 592, 793}.

Thus, dropping the last element, we find that R_{3}(592) ≥ 11 and R_{3}^{−1}(11) ≤ 592. This is slightly better than the bound from BoseCh_{h}(11, b) sets.

3 Generalized Bose-Chowla sets

Fix an integer h ≥ 2 and a prime power q, and set M := q^{h} − 1. Let τ be a multiplicative generator of 𝔽_{q^{h}}^{×} (not necessarily in line with the Conway polynomial). Take β ∈ 𝔽_{q^{h}} with algebraic degree h. We define S_{h} as follows:

S_{h}(τ, β) := {a ∈ ℤ/Mℤ : τ^{a} = β + v, v ∈ 𝔽_{q}} .

Further, let α_{1}, α_{2}, …, α_{h} be a basis for 𝔽_{q^{h}} over 𝔽_{q} as a vector space, with α_{1} = 1 and α_{2} = β.

As 1, β, …, α_{h} is a basis, each x′ ∈ 𝔽_{q} corresponds to a distinct x ∈ ℤ/Mℤ by the equation θ^{x} = 1 · x′ + 1 · β + ∑_{i=3}^{h} 0 · α_{i}, so that S_{h}(τ, β) has exactly q elements.

Consider k ∈ ℤ/Mℤ, and suppose that a_{1}, …, a_{h}, b_{1}, …, b_{h} ∈ S_{h}(τ, β) satisfy

k = a_{1} + ⋯ + a_{h} ≡ b_{1} + ⋯ + b_{h} (mod M).

As τ has multiplicative order q^{h} − 1 = M, we have

τ^{k} = τ^{a_{1}+···+a_{h}} = ∏_{i=1}^{h} τ^{a_{i}} = ∏_{i=1}^{h}(β + a′_{i})

for some a′_{i} ∈ 𝔽_{q}. In the same manner,

τ^{k} = ∏_{i=1}^{h}(β + b′_{i}).

Now define polynomials f, g ∈ 𝔽_{q}[x] by

f(x) = ∏_{i=1}^{h}(x + a′_{i}), g(x) = ∏_{i=1}^{h}(x + b′_{i}).

Then β (which has algebraic degree h) is a root of f(x) − g(x) (which has degree at most h − 1), from which we learn that f(x) − g(x) is identically 0, i.e., f(x) = g(x). We have unique factorization over finite fields, so that

{a′_{1}, …, a′_{h}} = {b′_{1}, …, b′_{h}}

as multisets. As noted above, that α_{1}, …, α_{h} is a basis implies that a′_{i}, b′_{i} ∈ 𝔽_{q} uniquely define a_{i}, b_{i} in ℤ/Mℤ, and consequently

{a_{1}, …, a_{h}} = {b_{1}, …, b_{h}}

as multisets. That is, S_{h}(τ, β) is a B_{h}-set in ℤ/Mℤ.

We can take τ to be θ, the generator provided in the Conway polynomial representation of 𝔽_{q^{h}}, and note that β = θ^{b} for some b ∈ ℤ/Mℤ, so that S_{h}(τ, β) = BoseCh_{h}(θ, b). We have proven the claims in Theorem 3 concerning BoseCh_{h}(q, b) sets.

Before proceeding into the proof of Theorem 4 as it pertains to BoseCh sets, we spend a few words noting some tempting generalizations that aren’t really meaningful generalizations. First, fix any basis α_{1}, …, α_{h} of 𝔽_{q^{h}} over 𝔽_{q}, and any constants c_{1}, …, c_{h−1} ∈ 𝔽_{q}, not all 0 and with (c_{1}α_{1} + ⋯ + c_{h−1}α_{h−1})α_{h}^{−1} having degree h. Then the set

{a ∈ ℤ/Mℤ: τ^{a} = c_{1}α_{1} + ⋯ + c_{h−1}α_{h−1} + vα_{h}, v ∈ 𝔽_{q}}

is a B_{h}-set with q elements. By details we spare the reader, each such set is affinely equivalent to BoseCh_{h}(q, b) for some integer b. Second, we note that if τ is also a generator of the multiplicative group of 𝔽_{q^{h}}, then S_{h}(τ, β) ∼ S_{h}(θ, β). Specifically, τ = θ^{t} for some t, and since τ is a generator, gcd(t, M) = 1; let t^{−1} be the inverse of t modulo m. Then

S_{h}(τ, β) := {a ∈ ℤ/Mℤ : τ^{a} = β + v, v ∈ 𝔽_{q}} = {a ∈ ℤ/Mℤ : θ^{ta} = β + v, v ∈ 𝔽_{q}} = t^{−1} ∗ S_{h}(θ, β).

We now turn to the task of determining when

BoseCh_{h}(q, b) ∼ BoseCh_{h}(q, e).

First, suppose that b ≡ e (mod \frac{q^{h}−1}{q−1}). Then for some integer x we have b = e + x\frac{q^{h}−1}{q−1} and θ^{b} = θ^{e}θ^{x(q^{h}−1)/(q−1)} = wθ^{e}, and w = (θ^{(q^{h}−1)/(q−1)})^{x} ∈ 𝔽_{q} because θ^{(q^{h}−1)/(q−1)} is in 𝔽_{q}. We have

BoseCh_{h}(q, b) := {a ∈ ℤ/Mℤ : θ^{a} = θ^{b} + v, v ∈ 𝔽_{q}}
= {a ∈ ℤ/Mℤ : θ^{a} = wθ^{e} + v, v ∈ 𝔽_{q}}
= {a ∈ ℤ/Mℤ : θ^{a−x(q^{h}−1)/(q−1)} = θ^{e} + vw^{−1}, v ∈ 𝔽_{q}}
= x\frac{q^{h}−1}{q−1} + \{a ∈ ℤ/Mℤ : θ^{a} = θ^{e} + v, v ∈ 𝔽_{q}\}
= x\frac{q^{h}−1}{q−1} + BoseCh_{h}(q, e).

Thus, BoseCh_{h}(q, b) ∼ BoseCh_{h}(q, e).

Now, suppose that pb ≡ e (mod M), where p is the characteristic of the field 𝔽_{q^{h}}. The map u ↦ u^{p}, the Frobenius automorphism, is a bijection and satisfies (u + v)^{p} = u^{p} + v^{p} for any u, v ∈ 𝔽_{q^{h}}. We have

BoseCh_{h}(q, b) := {a ∈ ℤ/Mℤ : θ^{a} = θ^{b} + v, v ∈ 𝔽_{q}}
= {a ∈ ℤ/Mℤ : (θ^{a})^{p} = (θ^{b} + v)^{p}, v ∈ 𝔽_{q}}
= {a ∈ ℤ/Mℤ : θ^{ap} = θ^{pb} + v^{p}, v ∈ 𝔽_{q}}
= p^{−1} ∗ {a ∈ ℤ/Mℤ : θ^{ap} = θ^{e} + v, v ∈ 𝔽_{q}}
= p^{−1} ∗ BoseCh_{h}(q, e).

It follows that if b ≡ p^{i}e (mod M) for any i, then BoseCh_{h}(q, b) ∼ BoseCh_{h}(q, e). Now suppose that w := θ^{e} − θ^{b} ∈ 𝔽_{q}. Then

BoseCh_{h}(q, b) := {a ∈ ℤ/Mℤ : θ^{a} = θ^{b} + v, v ∈ 𝔽_{q}}
= {a ∈ ℤ/Mℤ : θ^{a} = θ^{e} − w + v, v ∈ 𝔽_{q}}
= BoseCh_{h}(q, e).

Thus, S_{h}(q, θ, θ^{b}) ∼ S_{h}(q, θ, θ^{e}).

This concludes the proof of all of the claims regarding BoseCh sets made in Theorems 3 and 4.

4 Generalized Singer sets

Fix an integer h ≥ 2 and a prime power q, and set M := (q^{h+1} − 1)/(q − 1). Let τ be a multiplicative generator 𝔽_{q^{h+1}}^{×}. Suppose further that β has algebraic degree h + 1. We define S_{h} as follows:

S_{h}(τ, β) := {a ∈ ℤ/Mℤ : τ^{a} = uβ + v, u, v ∈ 𝔽_{q}} .

Further, let α_{1}, α_{2}, …, α_{h} be a basis for 𝔽_{q^{h}} over 𝔽_{q} as a vector space, with α_{1} = 1 and α_{2} = β. Note that τ^{M} ∈ 𝔽_{q}, as is τ^{kM} for any integer k.

We first argue that S_{h}(τ, β) has q + 1 distinct elements. As 1, β, α_{3}, …, α_{h} is a basis, for each u, v ∈ 𝔽_{q}, not both 0, there is a unique a in [1, q^{h+1} − 1] with τ^{a} = u + vβ. That is, there are q^{2} − 1 such a. For each particular a, there is also a solution (with different u, v) with a + kM for any integer k, as

τ^{a+kM} = τ^{kM}(uβ + v) = (wu)β + (wv),

where w = τ^{kM} ∈ 𝔽_{q}, and so wu, wv ∈ 𝔽_{q}. Thus, the q^{2} − 1 solutions with 1 ≤ a ≤ q^{h+1} − 1 fall into congruence classes modulo M. Each congruence class modulo M has q − 1 elements in 1 ≤ a ≤ q^{h+1} − 1, so that S_{h}(τ, β) consists of (q^{2} − 1)/(q − 1) = q + 1 distinct elements.

We now prove that S_{h}(τ, β) is a B_{h}-set in ℤ/Mℤ. Define functions u, v: S_{h}(τ, β) → 𝔽_{q} by

τ^{k} = u(k)β + v(k).

Note that u(M) = 0 since τ^{M} ∈ 𝔽_{q}. Clearly the pair (u(k), v(k)) uniquely determines k ∈ S_{h}(τ, β). But more surprisingly, the value −v(k)u(k)^{−1} (possibly undefined) uniquely determines k ∈ S_{h}(τ, β), as we now explain. Suppose −v(k)u(k)^{−1} is undefined, whence u(k) = 0. Then τ^{k} = v(k) ∈ 𝔽_{q}, so that k ≡ 0 (mod M). Since S_{h}(τ, β) ⊆ ℤ/M/ZZ, we must have k = M. Otherwise, w := −v(k)u(k)^{−1} is defined, whence wu(k) = v(k). This means that τ^{k} = u(k)β + wu(k). We know β and w, and therefore know the value y ∈ [1, q^{h+1} − 1] with τ^{y} = β + w. Since u(k) ∈ 𝔽_{q}, we have y ≡ k (mod M), whence there is a unique candidate for k in [1, M].

Now suppose that

a_{1} + ⋯ + a_{h} ≡ b_{1} + ⋯ + b_{h} (mod M),  (1)

with a_{i}, b_{i} ∈ S_{h}(τ, β), and we must show that

{a_{1}, …, a_{h}} = {b_{1}, …, b_{h}}  (2)

as multisets. From line (1), there is an integer x with

a_{1} + ⋯ + a_{h} = kM + b_{1} + ⋯ + b_{h}.

Let w = τ^{kM} ∈ 𝔽_{q}. We then have, using that a_{i}, b_{i} ∈ S_{h}(τ, β),

∏_{i=1}^{h} (u(a_{i})β + v(a_{i})) = ∏_{i=1}^{h} τ^{a_{i}}

= τ^{∑_{i=1}^{h} a_{i}}

= τ^{xM+∑_{i=1}^{h} b_{i}}

= w ∏_{i=1}^{h} τ^{b_{i}}

= w ∏_{i=1}^{h} (u(b_{i})β + v(b_{i})).

We define the polynomials (each with degree at most h) in 𝔽_{q}[x]

f(x) := ∏_{i=1}^{h} (u(a_{i})x + v(a_{i})), g(x) := ∏_{i=1}^{h} (u(b_{i})x + v(b_{i})).

Then β, which by hypothesis has degree h + 1, is a root of the polynomial f(x) − wg(x), which has degree at most h. Thus f(x) = wg(x), and f, g must have the same roots in the same multiplicities. That is, the multisets are equal

{−v(a_{i})u(a_{i})^{−1} : 1 ≤ i ≤ h} = {−v(b_{i})u(b_{i})^{−1} : 1 ≤ i ≤ h} ,

including the number of occurrences of undefined elements. As noted above, the value of −v(a_{i})u(a_{i})^{−1} uniquely determines a_{i}, so that the multiset equality

{a_{1}, …, a_{h}} = {b_{1}, …, b_{h}}

holds.

We can take τ to be θ, the generator provided in the Conway polynomial representation, and we can locate b ∈ ℤ/Mℤ so that β = θ^{b}, and then S_{h}(τ, β) = Singer_{h}(θ, b). We have proven the claims in Theorem 3 concerning Singer_{h}(q, b) sets.

Before proceeding into the proof of Theorem 4 as it pertains to Singer sets, we note that as with BoseCh sets, neither the completion of 1, β into a basis (which we do not elaborate upon) nor the particular choice of generator actually matters, up to affine equivalence, which we now elaborate. Suppose τ = θ^{k}, β = θ^{b}. Then

S_{h}(τ, β) := {a ∈ ℤ/Mℤ : τ^{a} = uβ + v, u, v ∈ 𝔽_{q}}
= {a ∈ ℤ/Mℤ : θ^{ka} = uθ^{b} + v, u, v ∈ 𝔽_{q}} = k^{−1} ∗ Singer_{h}(q, b).

Thus, we have lost nothing by defining Singer_{h}(q, b) with respect to a specific generator. Now suppose that b ≡ e (mod M), whence b = e + kM for some integer k and

θ^{b} = θ^{e}θ^{kM} = wθ^{e}

for some 0 ≠ w ∈ 𝔽_{q}. We have

Singer_{h}(q, b) := {a ∈ ℤ/Mℤ : θ^{a} = uθ^{b} + v, u, v ∈ 𝔽_{q}}
= {a ∈ ℤ/Mℤ : θ^{a} = uwθ^{e} + v, u, v ∈ 𝔽_{q}} = Singer_{h}(q, e).

Recall that the Frobenius automorphism u ↦ u^{p}, where p is the characteristic of 𝔽_{q^{h}} fixes each element of 𝔽_{q}, and satisfies the “children’s binomial theorem”: (u + v)^{p} = u^{p} + v^{p} for all u, v ∈ 𝔽_{q^{h}}. Suppose that e ≡ pb (mod M). Then

Singer_{h}(q, b) := {a ∈ ℤ/Mℤ : θ^{a} = uθ^{b} + v, u, v ∈ 𝔽_{q}}
= {a ∈ ℤ/Mℤ : θ^{ap} = u^{p}θ^{bp} + v^{p}, u, v ∈ 𝔽_{q}}
= {a ∈ ℤ/Mℤ : θ^{ap} = uθ^{bp} + v, u, v ∈ 𝔽_{q}}
= p^{−1} ∗ Singer_{h}(q, bp).

It follows that if b ≡ p^{i}e (mod q^{h+1}−1) for some integer i, then Singer_{h}(q, b) ∼ Singer_{h}(q, e).

While Theorem 4(vi) is a special case of Theorem 4(vii), we provide a separate proof of the easier (vi) as it is independently useful in computations. Suppose that w := θ^{e} − θ^{b} ∈ 𝔽_{q}. Then

Singer_{h}(q, b) := {a ∈ ℤ/Mℤ : θ^{a} = uθ^{b} + v, u, v ∈ 𝔽_{q}}
= {a ∈ ℤ/Mℤ : θ^{a} = u(θ^{e} − w) + v, u, v ∈ 𝔽_{q}}
= {a ∈ ℤ/Mℤ : θ^{a} = uθ^{e} + v − uw, u, v ∈ 𝔽_{q}}
= Singer_{h}(q, e).

We now address Theorem 4(vii). Suppose that r, t, w, s ∈ 𝔽_{q}, and at least one of r, t is nonzero, and

rθ^{b} + tθ^{e+b} + wθ^{e} = s.

Then (r + tθ^{e})θ^{b} = s − wθ^{e}. Since 1, θ^{e} are linearly independent over 𝔽_{q} and at least one of r, t is nonzero, we know that r + tθ^{e} is nonzero, say θ^{k} = r + tθ^{e}. We have

Singer_{h}(q, b) := {a ∈ ℤ/Mℤ : θ^{a} = uθ^{b} + v, u, v ∈ 𝔽_{q}}
= {a ∈ ℤ/Mℤ : θ^{k}θ^{a} = (r + tθ^{e})(uθ^{b} + v), u, v ∈ 𝔽_{q}}
= {a ∈ ℤ/Mℤ : θ^{k}θ^{a} = rv + u(r + tθ^{e})θ^{b} + vtθ^{e}, u, v ∈ 𝔽_{q}}
= {a ∈ ℤ/Mℤ : θ^{k}θ^{a} = rv + u(s − wθ^{e}) + vtθ^{e}, u, v ∈ 𝔽_{q}}
= {a ∈ ℤ/Mℤ : θ^{k}θ^{a} = rv + us + (vt − uw)θ^{e}, u, v ∈ 𝔽_{q}}
= −k + {a ∈ ℤ/Mℤ : θ^{a} = u′θ^{e} + v′, u′, v′ ∈ 𝔽_{q}} .
= −k + Singer_{h}(q, e).

The equality of the last line relies upon the nonsingularness of the equations u′ = rv+us, v′ = rt − uw, which follows from θ^{b} being outside 𝔽_{q} and the equation (r + tθ^{e})θ_{b} = s − wθ^{e}

This concludes the proof of all of the claims regarding Singer sets made in Theorems 3 and 4.

5 Lower bounds on R_{h}(n) and upper bounds on R_{h}^{−1}(k)

Computing R_{2}^{−1}(k) is an old game already [18]. Babcock [1] computed by hand for k ≤ 10 (his value of R_{2}^{−1}(10) is incorrect). More recently, the OGR Project [6] has computed R_{2}^{−1}(28) = 585; the computation took 8.5 years on thousands of machines. We refer the reader to the Wikipedia page for Golomb rulers [19] for R_{2}^{−1}(k) for k ≤ 28 and for the sets that are optimal.

Another massive computation for R_{2}^{−1}(k) was carried out by Dogon & Rokicki [16]. With several clever optimizations, they computed the bound achieved by all subsets of all sets affinely equivalent to BoseCh_{2}(q, 1) and Singer_{2}(q, 1) for all q ≤ 40 000. In this section, we report on a similar computation, much smaller in scale, for h = 3 and h = 4.

The asymptotic growth of R_{h}(n) (respectively, R_{h}^{−1}(k)) is not known for h > 2. The best lower bounds on R_{h}(n) (upper bounds on R_{h}^{−1}(k)) arise from the construction of Singer [17]. Our generalization produces many more such sets, but they are of roughly the same size. Nevertheless, we feel it would be a contribution to the literature to record the resulting bounds under several hypotheses.

Clearly, R_{h}^{−1}(1) = 1, R_{h}^{−1}(2) = 2, and R_{h}^{−1}(3) = max{1, 2, h + 2} = h + 2. We therefore restrict our attention to k ≥ 4 and n ≥ h + 3.

By “Bose B_{h}-set”, we mean any affine image of BoseCh_{h}(q, θ, b) for any q, θ, b in the domain of BoseCh_{h}. By “Singer B_{h}-set”, we mean any affine image of Singer_{h}(q, b) for any q, θ, b in the domain of Singer_{h}.

While Singer B_{h}-sets are slightly thicker than Bose B_{h}-sets, it is easier to work with Bose sets. First, if q is a prime power, then BoseCh_{h}(q, 1) is a set with q elements modulo q^{h} −1. Thus, R_{h}(q^{h} − 1) ≥ q and R_{h}^{−1}(q) ≤ q^{h} − 1. Consequently, if k ≤ q then R_{h}^{−1}(k) ≤ R_{h}^{−1}(q) < q^{h}. The difficulty is now reduced to locating a prime power greater than k, but not too much greater.

We will state results that work for every k, for k > k_{0} with explicit k_{0}, and for k sufficiently large assuming the Riemann Hypothesis. The bounds are either impracticably bad for small k, or only apply for impracticably large k, or use an impracticably difficult hypothesis. Except for h = 2, we do not believe that the main terms reported below even have the “correct” coefficient. We start with the most explicit unconditional result.

Theorem 6 (Cully-Hugill [5]). For all integers n ≥ 1, there is a prime between n^{155} and (n + 1)^{155}.

It follows that there is a prime between ⌈k^{1/155}⌉^{155} and ⌈k^{1/155} + 1⌉^{155}. As

⌈k^{1/155} + 1⌉^{155h} < (k^{1/155} + 2)^{155h} < k^{h} + 3^{155h}k^{h−1/155},

we have the statement in the theorem below for R_{h}^{−1}(k). Assuming that

k^{155} < q < (k + 1)^{155} < n^{1/h} ≤ (k + 2)^{155}

and using the straightforward k^{155} > (k + 2)^{155} − 2^{44}(k + 1)^{154} yields the R_{h}(n) result.

Theorem 7. For all k ≥ 4 and n ≥ h + 3 ≥ 5, we have R_{h}^{−1}(k) < k^{h} + 3^{155h}k^{h−1/155} and R_{h}(n) ≥ n^{1/h} − 2^{44}n^{154/(155h)}.

For large k, we can do somewhat better.

Theorem 8 (Cully-Hugill [5]). For all integers n > exp(exp(32.537)), there is a prime between n^{3} and (n + 1)^{3}.

Hence:

Theorem 9. For all k > e^{e^{34}}, we have R_{h}^{−1}(k) < k^{h} + (3k)^{h−1/3} and R_{h}(n) > n^{1/h} − 7n^{2/(3h)}.

The following famed result [2] is beautifully straightforward to use.

Theorem 10 (Baker & Harman & Pintz [2]). If x is sufficiently large, then there is a prime in the interval [x − x^{21/40}, n], and in the interval [x, x + x^{21/40}].

This leads to:

Theorem 11. If k, n are sufficiently large, then R_{h}^{−1}(k) < k^{h} + 2^{h}k^{h−19/40} and R_{h}(n) ≥ n^{1/h} − n^{21/(40h)}.

Assuming the Riemann Hypothesis, we naturally have stronger results. The best result along these lines of which this author is aware follows [7].

Theorem 12 (Dudek & Grenié & Loïc [7]). Assuming the Riemann Hypothesis, for all n ≥ 2, there is a prime between n^{2} and (n + (1 + \frac{1}{log n})^{2} log n)^{2}.

This leads directly to the following.

Theorem 13. Assume the Riemann Hypothesis, and that k ≥ 4, n ≥ h + 3. Then

R_{h}^{−1}(k) < k^{h} + log(20k)k^{h−1/2} + 2k^{h−1} log^{2h}(20k), R_{h}(n) ≥ n^{1/h} − (7 + \frac{log n}{h})n^{1/(2h)}.

6 Explicit computations

For k ≤ 9, we computed the minimum-diameter B_{3}-sets in ℤ by brute force. This allowed us to find the sequence in the OEIS (\underline{A227358}), where R_{3}^{−1}(10) is also reported. These results are shown in Table 1.

k R_{3}^{−1}(k)  witness
1  1  {0}
2  2  {0, 1}
3  5  {0, 1, 4}
4  12  {0, 1, 7, 11}, {0, 1, 8, 11}
5  24  {0, 1, 15, 18, 23}, {0, 1, 15, 20, 23}
6  46  {0, 2, 11, 26, 42, 45}
7  83 {0, 1, 7, 50, 59, 78, 82}, {0, 2, 23, 45, 72, 79, 82}
{0, 4, 23, 32, 75, 76, 82}
8 130  {0, 2, 5, 34, 74, 107, 120, 129}
9 209  {0, 1, 17, 26, 127, 138, 185, 204, 208}
{0, 1, 18, 76, 83, 162, 188, 193, 208}
10 310

Table 1: \underline{A227358}, computations by John Tromo, sets and k ≤ 9 independently computed by the author.

We have computed all translations of all dilations of all subsets of the Singer and Bose B_{3}-sets generated with small q and any b. These results are shown in Table 2. The same computation was performed for B_{4}-sets, and those results are given in Table 3.

k R_{3}^{−1}(k) from Greedy from BoseCh with q from Singer with q
1  1  1  1  2  1  2
2  2  2  2  2  2  2
3  5  5  5  4  5  2
4 12  14  12  5  14  3
5 24  33  33  5  28  4
6 46  72  73  11  57  5
7 83  125  122  7  121  7
8 130  219  202  8  157  7
9 209  376  306  9  258  8
10 310  573  493  11  365  9
11  745  594  11  592  11
12  1209  894  13  738  11
13  1557  1044  13  1014  13
14  2442  1612  17  1236  13
15  3098  1874  17  1877  16
16  4048  2247  16  2071  16
17  5298  2537  17  2392  16
18  6704  3433  19  2960  17
19  7839  3821  19  3679  19
20  10987  5578  23  4326  19
21  12332  6060  23  5849  23
22  15465  6212  23  6476  23
23  19144  6997  23  7229  23
24  24546  8846  25  8010  23
25  28974  9624  25  8854  25
26  34406  11447  27  10177  25
27  37769  12088  27  12143  27
28  45864  14272  29  13432  27
29  50877  15544  29
30  61372  17999  31

Table 2: The upper bounds on R_{3}^{−1} that arise from Singer and Bose B_{3}-sets, and also the greedy B_{3}-set (\underline{A096772}).

k R_{4}^{−1}(k) from Greedy from BoseCh with q from Singer with q
1  1  1  1  2  1  2
2  2  2  2  2  2  2
3  6  6  6  3  6  2
4 16  22  26  5  18  3
5 42  56  89  5  71  5
6 101  154  212  7  156  5
7  369  404  7  388  7
8  857  959  8  693  7
9  1425  1731  11  1290  9
10  2604  2878  11  2345  9
11  4968  4469  11  4053  11
12  8195  7967  13  5174  11
13  13664  9903  13  9328  13
14  22433  15907  16  11348  13
15  28170  20849  16
16  47689  25397  16
17  65546  35282  17
18  96616  45783  19
19  146249  58033  19

Table 3: The upper bounds on R_{4}^{−1} that arise from Singer and Bose B_{4}-sets, and the greedy B_{4}-set (\underline{A365300}).

7 Open questions

The following questions are interesting to the author, who does not know of solutions.

1. The greedy B_{2}-set is called the Mian-Chowla sequence [13], and the first terms were computed in the 1940s. I’m not aware of any computation of the greedy B_{h} sequence for h > 2. I have added these sequences to the OEIS for 4 ≤ h ≤ 9 (sequences \underline{A365300} through \underline{A365305}).

2. The conditions in Theorem 4 are necessary for BoseCh_{h}(q, e) ∼ BoseCh_{h}(q, b); are they sufficient? Also, for Singer sets.

3. Is there a faster way to interpret Theorem 4(ii)? Theorem 4(vii) is particularly time consuming, can one assume without loss of generality that r = 0 and t = 1?

4. Does BoseCh_{2}(q, 1) always have two elements whose difference is relatively prime to q^{2} − 1? Equivalently, is there an affine image of BoseCh_{2}(q, θ, 1) that contains {1, 2}?

Is there any m, s, q with

{0, 1, 4, 10, 18, 23, 25} ⊆ m ∗ BoseCh_{2}(q, 1) + s (mod q^{2} − 1)?

Halberstam & Laxton [10] considered the m for which there is an s with BoseCh_{2}(q, 1) = m ∗ BoseCh_{2}(q, 1) + s. Can this be generalized to h > 2? Also for Singer sets.

5. Does the largest modular gap between consecutive elements of BoseCh_{2}(q, 1), Singer_{2}(q, 1) have order O(q)? It seems not, even if one chooses an affine image to make the largest gap as small as possible.

6. It is obvious that affine maps preserve the B_{h} property. The existence of Bose sets that are not affine images of each other suggests that there may be some more general arithmetic (or geometric) operation (beyond affine equivalence) that preserves the B_{h} property in cyclic groups.

References

[1] Wallace C. Babcock, Intermodulation interference in radio systems, Bell System Technical Journal 32 (1953), 63–73.

[2] R. C. Baker, G. Harman, and J. Pintz, The difference between consecutive primes. II, Proc. London Math. Soc. 83 (2001), 532–562.

[3] R. C. Bose, An affine analogue of Singer’s theorem, J. Indian Math. Soc. 6 (1942), 1–15.

[4] R. C. Bose and S. Chowla, Theorems in the additive theory of numbers, Comment. Math. Helv. 37 (1962/63), 141–147.

[5] Michaela Cully-Hugill, Primes between consecutive powers, J. Number Theory 247 (2023), 100–117.

[6] Distributed.net, Completion of OGR-28 project. A collaborative computing ef-

   fort. Published electronically at https://blogs.distributed.net/2022/11/23/03/
   28/bovine/.

[7] Adrian W. Dudek, Loïc Grenié, and Giuseppe Molteni, Primes in explicit short intervals on RH, Int. J. Number Theory 12 (2016), 1391–1407.

[8] P. Erdös and P. Turán, On a problem of Sidon in additive number theory, and on some related problems, J. London Math. Soc. 16 (1941), 212–215.

[9] Carlos Alexis Gómez Ruiz and Carlos Alberto Trujillo Solarte, Una nueva construcción de conjuntos B_{h} modulares, Matemáticas: Enseñanza Universitaria 19 (2011), 53–62.

[10] H. Halberstam and R. R. Laxton, On perfect difference sets, Quart. J. Math. Oxford Ser. 14 (1963), 86–90.

[11] Lenwood S. Heath and Nicholas A. Loehr, New algorithms for generating Conway polynomials over finite fields, J. Symbolic Comput. 38 (2004), 1003–1024.

[12] Frank Lübeck, Conway polynomials for finite fields. Published electronically at http://

    www.math.rwth-aachen.de/~Frank.Luebeck/data/ConwayPol/index.html.

[13] Abdul Majid Mian and S. Chowla, On the B_{2} sequences of Sidon, Proc. Nat. Acad. Sci. India. Sect. A. 14 (1944), 3–4.

[14] Kevin O’Bryant, A complete annotated bibliography of work related to Sidon sequences, Electron. J. Combin. DS11 (2004), Paper # 39.

[15] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, 2023. Published electronically at https://oeis.org.

[16] Tomas Rokicki and Gil Dogon, Larger Golomb rulers, Gathering4Gardner 12 Exchange Book 1 (2016), 155–166. Available at https://www.gathering4gardner.org/

    g4g12gift/Rokicki_Dogon-Larger_Golomb_Rulers.pdf.

[17] James Singer, A theorem in finite projective geometry and some applications to number theory, Trans. Amer. Math. Soc. 43 (1938), 377–385.

[18] Oswald Veblen, Diophantine analysis: problem 132, Amer. Math. Monthly 13 (1906), 46. Solution by F. H. Safford appears in 13 (1906), 215.

[19] Wikipedia, Golomb ruler, 2023-12-20. https://en.wikipedia.org/wiki/Golomb_
    ruler.

2020 Mathematics Subject Classification: Primary 05B10; Secondary 11B83. Keywords: B_{h}-set, Sidon set, Golomb ruler.

(Concerned with sequences \underline{A096772}, \underline{A227358}, \underline{A365300}, \underline{A365301}, \underline{A365302}, \underline{A365303}, \underline{A365304}, \underline{A365305}.)

Received August 24 2023; revised versions received August 26 2023; January 3 2024. Published in Journal of Integer Sequences, January 4 2024.

Return to Journal of Integer Sequences home page.