The Fourth Positive Element in the Greedy B_{h}-Set

Melvyn B. Nathanson Department of Mathematics Lehman College (CUNY) Bronx, NY 10468 USA

            melvyn.nathanson@lehman.cuny.edu

Kevin O’Bryant Department of Mathematics College of Staten Island (CUNY) Staten Island, NY 10314 USA

              kevin.obryant@csi.cuny.edu

Abstract

For a positive integer h, a B_{h}-set is a set of integers A such that every integer n has at most one representation in the form n = x_{1} + ⋯ + x_{h}, where x_{r} ∈ A for all r = 1, …, h and x_{1} ≤ ⋯ ≤ x_{h}. The greedy B_{h}-set is the infinite set of nonnegative integers {a_{0}(h), a_{1}(h), a_{2}(h), …} constructed as follows: a_{0}(h) = 0, and a_{k+1}(h) is least integer greater than a_{k}(h) for which {a_{0}(h), a_{1}(h), a_{2}(h), …, a_{k}(h), a_{k+1}(h)} is a B_{h}-set. Nathanson gave the formulas a_{1}(h) = 1, a_{2}(h) = h + 1, and a_{3}(h) = h^{2} + h + 1, valid for all h. This paper proves that a_{4}(h), the fourth positive term of the greedy B_{h}-set, is (h^{3} + 3h^{2} + 3h + 1) /2 if h is odd and (h^{3} + 2h^{2} + 3h + 2) /2 if h is even. In particular, a_{4}(h) is not a polynomial, but is a quasipolynomial.

1 The greedy algorithm

Let h be a positive integer. A finite or infinite set A of nonnegative integers is a B_{h}-set if no integer has two different representations as sums of h elements of A. Equivalently, the set A is a B_{h}-set if the equation

x_{1} + ⋯ + x_{h} = y_{1} + ⋯ ≤ y_{h}

with x_{i}, y_{i} ∈ A for all r = 1, …, h and

x_{1} ≤ ⋯ ≤ x_{h} and y_{1} ≤ ⋯ y_{h}

implies that x_{i} = y_{i} for all i = 1, …, h. A B_{2}-set is also called a Sidon set.

For every positive integer h, we use a greedy algorithm to construct a B_{h}-set {a_{k}(h) : k = 0, 1, 2, …} as follows: a_{0}(h) = 0 and, if {a_{0}(h), a_{1}(h), …, a_{k}(h)} is a B_{h}-set, then a_{k+1}(h) is the least positive integer such that {a_{0}(h), a_{1}(h), …, a_{k}(h), a_{k+1}(h)} is a B_{h}-set. The greedy B_{1}-set is simply the set ℕ_{0} of nonnegative integers, that is, a_{k}(1) = k for all k ∈ ℕ_{0}. The greedy B_{2}-set is the (shifted) Mian-Chowla sequence (Mian-Chowla [2], Guy [1, Section E28]). In the OEIS [4], the greedy B_{h}-set for 1 ≤ h ≤ 9 are sequences (in order, with various offsets and shifts) \underline{A001477}, \underline{A005282}, \underline{A051912}, \underline{A365300}, \underline{A365301}, \underline{A365302}, \underline{A365303}, \underline{A365304}, \underline{A365305}. The first, second, third, fourth, fifth and sixth positive terms of the greedy B_{h}-set are \underline{A000012}, \underline{A020725}, \underline{A002061} (offset), \underline{A369817}, \underline{A369818}, \underline{A369819}, respectively. These are rows and columns of the table sequences \underline{A365515} and (shifted by 1) \underline{A347570}.

For all h ≥ 1 we have

a_{0}(h) = 0, a_{1}(h) = 1, and a_{2}(h) = h + 1.

From computer calculations of initial segments of B_{h}-sets for small h, the second author conjectured on September 30 2023 that, for all positive integers h, we have

a_{3}(h) = h^{2} + h + 1.

This formula for a_{3}(h) was later proved by the first author [3]. In this paper we obtain an explicit quasi-polynomial for a_{4}(h).

Theorem 1. The fourth positive element in the greedy B_{h}-set is

a_{4}(h) = \begin{cases}\frac{1}{2} (h^{3} + 3h^{2} + 3h + 1) , & if h is odd; \\ \frac{1}{2} (h^{3} + 2h^{2} + 3h + 2) , & if h is even. \end{cases}

Using the floor function, we may also write

a_{4}(h) = ⌊\frac{h + 3}{2}⌋ h^{2} + ⌊\frac{3h}{2}⌋ + 1.

It is an open problem to compute exact values or even asymptotic estimates for a_{k}(h) for k ≥ 5. Indeed, it is not even known if a_{k}(h) < a_{k}(h + 1) for all integers h ≥ 1 and k ≥ 2. We have the upper bound [3]

a_{k}(h) ≤ ∑_{i=0}^{k−1} h^{i} < h^{k−1} + 2h^{k−2}

for all positive integers h and k.

2 Lower bound for a_{4}(h)

In this section we compute a lower bound for a_{4}(h).

For u, v ∈ ℝ, define the interval of integers [u, v] = {n ∈ ℤ : u ≤ n ≤ v}.

Lemma 2. For all integers h ≥ 2 we have

a_{4}(h) ≥ \begin{cases}\frac{1}{2} (h^{3} + 3h^{2} + 3h + 1) , & if h is odd; \\ \frac{1}{2} (h^{3} + 2h^{2} + 3h + 2) , & if h is even. \end{cases}

Proof. Let B be the set of positive integers b such that a_{4}(h) ≠ b. A sufficient condition that b ∈ B is the existence of nonnegative integers x_{1}, x_{2}, y_{1}, y_{2}, y_{3} with

x_{1} + x_{2} ≤ h − 1,  y_{1} + y_{2} + y_{3} ≤ h,  x_{1}y_{1} = x_{2}y_{2} = 0

such that

b + x_{1} + x_{2}(h + 1) = y_{1} + y_{2}(h + 1) + y_{3}(h^{2} + h + 1)

or, equivalently,

b = y_{3}(h^{2} + h + 1) + (y_{2} − x_{2})(h + 1) + (y_{1} − x_{1}).

We consider the following two cases separately: x_{2} = 0 and y_{2} = 0.

Let x_{2} = 0 and let 1 ≤ y_{3} ≤ h and 0 ≤ y_{2} ≤ h − y_{3}. Because

0 ≤ x_{1} ≤ h − 1 and 0 ≤ y_{1} ≤ h − y_{3} − y_{2},

the set B contains the interval

y_{3}(h^{2}+h + 1) + y_{2}(h + 1) + [−(h − 1), h − y_{3} − y_{2}]
= y_{3}(h^{2} + h + 1) + [y_{2}(h + 1) − h + 1, y_{2}h + h − y_{3}] .  (1)

If

0 ≤ y_{2} ≤ h − y_{3} − 1  (2)

then B also contains the interval

y_{3}(h^{2}+h + 1) + [(y_{2} + 1)(h + 1) − h + 1, (y_{2} + 1)h + h − y_{3}]
= y_{3}(h^{2} + h + 1) + [y_{2}(h + 1) + 2, y_{2}h + 2h − y_{3}] .  (3)

Inequality (2) implies that

y_{2}(h + 1) + 2 ≤ y_{2}h + h − y_{3} + 1,

and so intervals (1) and (3) overlap. Therefore, B contains the interval

y_{3}(h^{2} + h + 1) + ⋃_{y_{2}=0}^{h−y_{3}} [y_{2}(h + 1) − h + 1, y_{2}h + h − y_{3}]

= y_{3}(h^{2} + h + 1) + [−h + 1, (h − y_{3})h + h − y_{3}]

= [y_{3}(h^{2} + h + 1) − h + 1, y_{3}h^{2} + h^{2} + h] .  (4)

Let y_{2} = 0 and let 1 ≤ y_{3} ≤ h and 0 ≤ x_{2} ≤ h − y_{3}. Note that h − y_{3} ≤ h − 1. Because

0 ≤ x_{1} ≤ h − 1 − x_{2} and 0 ≤ y_{1} ≤ h − y_{3},

the set B contains the interval

y_{3}(h^{2}+h + 1) − x_{2}(h + 1) + [−(h − 1 − x_{2}), h − y_{3}]
= y_{3}(h^{2} + h + 1) + [−x_{2}h − h + 1, −x_{2}(h + 1) + h − y_{3}] .  (5)

If

0 ≤ x_{2} ≤ h − y_{3} − 1  (6)

then B also contains the interval

y_{3}(h^{2}+h + 1) + [−(x_{2} + 1)h − h + 1, −(x_{2} + 1)(h + 1) + h − y_{3}]
= y_{3}(h^{2} + h + 1) + [−x_{2}h − 2h + 1, −x_{2}(h + 1) − y_{3} − 1] .  (7)

Inequality (6) implies that

−x_{2}h − h ≤ −x_{2}(h + 1) − y_{3} − 1,

and so intervals (5) and (7) overlap. Therefore, B contains the interval

y_{3}(h^{2}+h + 1) + ⋃_{x_{2}=0}^{h−y_{3}} [−x_{2}h − h + 1, −x_{2}(h + 1) + h − y_{3}]

= y_{3}(h^{2} + h + 1) + [−(h − y_{3})h − h + 1, h − y_{3}]

= [y_{3}(h^{2} + 2h + 1) − h^{2} − h + 1, y_{3}(h^{2} + h) + h] .  (8)

Intervals (4) and (8) overlap because y_{3} ≤ h ≤ 2h, and so B contains the interval

I(y_{3}) = [y_{3}(h^{2} + 2h + 1) − h^{2} − h + 1, y_{3}h^{2} + h^{2} + h]  (9)

for y_{3} ∈ [1, h]. These intervals move to the right as y_{3} increases. Intervals (I(y_{3}) and I(y_{3}+1) overlap if

(y_{3} + 1)(h^{2} + 2h + 1) − h^{2} − h + 1 ≤ y_{3}h^{2} + h^{2} + h + 1

or, equivalently, if (2h + 1)y_{3} ≤ h^{2} − 1 or

y_{3} ≤ ⌊\frac{h^{2} − 1}{2h + 1}⌋ = \begin{cases}\frac{h−1}{2}, & if h is odd; \\ \frac{h−2}{2}, & if h is even. \end{cases}

For odd h ≥ 3, the set B contains the interval

⋃_{y_{3}=1}^{(h+1)/2} I(y_{3}) = ⋃_{y_{3}=1}^{(h+1)/2} [y_{3}(h^{2} + 2h + 1) − h^{2} − h + 1, y_{3}h^{2} + h^{2} + h]

= [h + 2, (\frac{h + 1}{2}) h^{2} + h^{2} + h]

= [h + 2, \frac{h^{3} + 3h^{2} + 2h}{2}] .  (10)

For even h ≥ 2, the set B contains the interval

⋃_{y_{3}=1}^{h/2} I(y_{3}) = [y_{3}(h^{2} + 2h + 1) − h^{2} − h + 1, y_{3}h^{2} + h^{2} + h]

= [h + 2, (\frac{h}{2}) h^{2} + h^{2} + h]

= [h + 2, \frac{h^{3} + 2h^{2} + 2h}{2}] .  (11)

For odd h ≥ 3, let

y_{2} = 0,  y_{3} = \frac{h + 3}{2},  x_{2} = \frac{h + 1}{2}.

The set B contains the interval

y_{3}(h^{2} + h + 1) − x_{2}(h + 1) + [−(h − 1 − x_{2}), h − y_{3}]

= (\frac{h + 3}{2}) (h^{2} + h + 1) − (\frac{h + 1}{2}) (h + 1) + [−\frac{h − 3}{2}, \frac{h − 3}{2}]

= [\frac{h^{3} + 3h^{2} + h + 5}{2}, \frac{h^{3} + 3h^{2} + 3h − 1}{2}] .  (12)

Intervals (10) and (12) overlap and so B contains the interval

[h + 2, \frac{h^{3} + 3h^{2} + 3h − 1}{2}] .

It follows that, for odd h ≥ 3, we have the lower bound

a_{4}(h) ≥ \frac{h^{3} + 3h^{2} + 3h − 1}{2} + 1 = \frac{h^{3} + 3h^{2} + 3h + 1}{2}.

For even h ≥ 2, let

y_{2} = 0, y_{3} = \frac{h + 2}{2}, x_{2} = \frac{h}{2}.

The set B contains the interval

y_{3}(h^{2} + h + 1) − x_{2}(h + 1) + [−(h − 1 − x_{2}), h − y_{3}]

= (\frac{h + 2}{2}) (h^{2} + h + 1) − (\frac{h}{2}) (h + 1) + [−\frac{h − 2}{2}, \frac{h − 2}{2}]

= [\frac{h^{3} + 2h^{2} + h + 4}{2}, \frac{h^{3} + 2h^{2} + 3h}{2}] .  (13)

Intervals (11) and (13) overlap and so B contains the interval

[h + 2, \frac{h^{3} + 2h^{2} + 3h}{2}] .

It follows that, for even h ≥ 2, we have the lower bound

a_{4}(h) ≥ \frac{h^{3} + 2h^{2} + 3h}{2} + 1 = \frac{h^{3} + 2h^{2} + 3h + 2}{2}.

This completes the proof of Lemma 2.

3 The upper bound for a_{4}(h)

In this section we compute an upper bound for a_{4}(h). Lemma 3. For all positive integers h we have

a_{4}(h) ≤ \begin{cases}\frac{1}{2} (h^{3} + 3h^{2} + 3h + 1) , & if h is odd; \\ \frac{1}{2} (h^{3} + 2h^{2} + 3h + 2) , & if h is even. \end{cases}

Proof. Let

H = \begin{cases}\frac{1}{2}(h^{2} + 2h + 1), & if h is odd; \\ \frac{1}{2}(h^{2} + h + 2), & if h is even. \end{cases}

We must prove that

a_{4}(h) ≤ (h + 1)H.

This inequality is equivalent to the statement that there do not exist nonnegative integers x_{0}, x_{1}, x_{2}, x_{3} and y_{1}, y_{2}, y_{3} such that

x_{0}(h + 1)H + x_{1} + x_{2}(h + 1) + x_{3}(h^{2} + h + 1)  (14)
= y_{1} + y_{2}(h + 1) + y_{3}(h^{2} + h + 1)

with

x_{0} + x_{1} + x_{2} + x_{3} ≤ h,  y_{1} + y_{2} + y_{3} ≤ h  (15)

and

x_{0} ≥ 1,  x_{1}y_{1} = x_{2}y_{2} = x_{3}y_{3} = 0.  (16)

Suppose that equation (14) has a solution satisfying conditions (15) and (16). Note that

h^{2} + 1 < 2H.

If x_{0} ≥ 2, then

(h + 1)(h^{2} + 1) < 2(h + 1)H ≤ x_{0}(h + 1)H
≤ y_{1} + y_{2}(h + 1) + y_{3}(h^{2} + h + 1)
≤ h(h^{2} + h + 1)
< (h + 1)(h^{2} + 1),

which is absurd. Therefore,

x_{0} = 1.

If y_{3} = 0, then

\frac{(h + 1)(h^{2} + 1)}{2} < (h + 1)H ≤ y_{1} + y_{2}(h + 1) ≤ h(h + 1)

and so (h − 1)^{2} < 0, which is absurd. Therefore,

y_{3} ≥ 1 and x_{3} = 0.

With x_{0} = 1 and x_{3} = 0, equation (14) becomes

x_{1} + (H + x_{2})(h + 1) = y_{1} + y_{2}(h + 1) + y_{3}(h^{2} + h + 1)  (17)
= y_{1} + y_{3} + (y_{2} + y_{3}h)(h + 1).

We obtain the congruence

x_{1} ≡ y_{1} + y_{3} (mod h + 1).

If x_{1} = 0, then y_{1} + y_{3} ≡ 0 (mod h + 1). The inequalities y_{1} ≥ 0 and y_{3} ≥ 1 imply y_{1} + y_{3} ≥ h + 1, which contradicts condition (15). Therefore,

x_{1} ≥ 1 and y_{1} = 0

and

x_{1} ≡ y_{3} (mod h + 1).

Because 1 ≤ y_{3} ≤ h, if x_{1} ≠ y_{3}, then x_{1} ≥ y_{3} + h + 1 > h, which is absurd. Therefore,

x_{1} = y_{3}

and equation (17) becomes, simply,

H + x_{2} = y_{2} + y_{3}h,  (18)

where x_{2}, y_{2}, y_{3} are nonnegative integers such that

x_{2} + y_{3} ≤ h − 1, y_{2} + y_{3} ≤ h, and x_{2}y_{2} = 0.

We consider separately the two cases: h odd and h even.

Let h be odd. If y_{3} ≤ (h + 1)/2, then equation (18) gives

\frac{h^{2} + 2h + 1}{2} ≤ y_{2} + y_{3}h ≤ (h − y_{3}) + y_{3}h

= h + y_{3}(h − 1) ≤ h + \frac{h^{2} − 1}{2}

= \frac{h^{2} + 2h − 1}{2}

which is absurd. It follows that y_{3} > (h + 1)/2 and, because h is odd, that

y_{3} ≥ \frac{h + 3}{2}.

If y_{2} = 0, then

x_{2} = y_{3}h − H ≥ \frac{h^{2} + 3h}{2} − \frac{h^{2} + 2h + 1}{2} ≥ \frac{h − 1}{2},

and so

h + 1 = \frac{h − 1}{2} + \frac{h + 3}{2} ≤ x_{2} + y_{3} ≤ h − 1

which is absurd. Therefore,

y_{2} ≥ 1 and x_{2} = 0.

Equation (18) becomes

H = y_{2} + y_{3}h.

Equivalently,

h^{2} + 2h + 1 = 2H = 2y_{2} + 2y_{3}h ≥ 2y_{2} + h^{2} + 3h,

and so

1 ≥ 2y_{2} + h,

which is absurd. This completes the proof in the odd case.

Let h be even. If y_{3} ≤ h/2, then equation (18) gives

\frac{h^{2} + h + 2}{2} ≤ y_{2} + y_{3}h ≤ (h − y_{3}) + y_{3}h

= h + y_{3}(h − 1) ≤ h + \frac{h^{2} − h}{2}

= \frac{h^{2} + h}{2}

which is absurd. It follows that y_{3} > h/2 and, because h is even, that

y_{3} ≥ \frac{h + 2}{2}.

If y_{2} = 0, then

x_{2} = y_{3}h − H ≥ \frac{h^{2} + 2h}{2} − \frac{h^{2} + h + 2}{2} = \frac{h − 2}{2},

and so

h = \frac{h + 2}{2} + \frac{h − 2}{2} ≤ y_{3} + x_{2} ≤ h − 1,

which is absurd. Therefore,

y_{2} ≥ 1 and x_{2} = 0.

Equation (18) becomes

H = y_{2} + y_{3}h

Equivalently,

h^{2} + h + 2 = 2H = 2y_{2} + 2y_{3}h ≥ 2y_{2} + h^{2} + 2h,

and so

2 ≥ 2y_{2} + h,

which is absurd. This completes the proof in the even case.

Now Theorem 1, the exact formula for a_{4}(h), follows immediately from Lemmas 2 and 3.

References

[1] R. K. Guy, Unsolved Problems in Number Theory, 3rd edition, Springer, 2004.

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

[3] M. B. Nathanson, The third positive element in the greedy B_{h}-set, to appear in

   Palest. J. Math., Available at http://arxiv.org/abs/2310.14426.

[4] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2024. Available

   at https://oeis.org.

2020 Mathematics Subject Classification: Primary 11B13; Secondary 11B34, 11B75, 11P99. Keywords: Sidon set, B_{h}-set, greedy algorithm.

(Concerned with sequences \underline{A000012}, \underline{A001477}, \underline{A002061}, \underline{A005282}, \underline{A020725}, \underline{A051912}, \underline{A347570}, \underline{A365300}, \underline{A365301}, \underline{A365302}, \underline{A365303}, \underline{A365304}, \underline{A365305}, \underline{A365515}, \underline{A369817}, \underline{A369818}, and \underline{A369819}.)

Received March 11 2024; revised version received August 28 2024. Published in Journal of Integer Sequences, August 28 2024.

Return to Journal of Integer Sequences home page.