🔢 mathematics

Bounds for Greedy $B_h$ -sets

This paper establishes new nontrivial lower and upper bounds for the $k$ -th element of the greedy $B_h$ -set, specifically providing precise asymptotic estimates for $k \ge 5$ and a general lower bound for all $k \ge 1$ , while also proposing a conjecture for the exact asymptotic behavior of the fifth element.

Original authors: Kevin O'Bryant

Published 2026-07-09

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Kevin O'Bryant

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are building a tower out of numbered blocks, but you have a very strict rule: no two different groups of blocks can add up to the same total. If you pick $h$ blocks and add them up, that sum must be unique to that specific group of blocks. Mathematicians call these special collections $B_h$ -sets.

Now, imagine you want to build the smallest possible tower that follows this rule. You start with block 0, then you look for the very next smallest number you can add without breaking the rule. Then you look for the next smallest after that, and so on. This is called the Greedy Algorithm. It's like playing a game where you always pick the cheapest, smallest item available that doesn't break your budget.

The paper by Kevin O'Bryant is all about figuring out how big these "next" blocks get as the tower grows taller. Specifically, the author is trying to predict the size of the 5th, 6th, 7th, and even higher blocks in this greedy tower, depending on how strict the "no duplicate sums" rule is (represented by the number $h$ ).

The Big Discovery: The 5th Block

The author's main achievement is finally putting some solid fences around the size of the 5th block in this tower (denoted as $\gamma_5$ ).

Before this paper, we knew the 5th block was somewhere between 0 and a very large number, but we didn't have a tight grip on it. This paper proves two things:

The Lower Bound (The Floor): The 5th block is definitely at least as big as $\frac{1}{8}h^4 + \frac{1}{2}h^3$ . Think of this as a concrete floor you can't dig under. No matter how you try, the 5th block won't be smaller than this.
The Upper Bound (The Ceiling): The 5th block is definitely smaller than roughly $0.467214 \times h^4$ (plus some smaller terms). This is a ceiling that the block cannot reach.

So, we now know the 5th block lives in a specific "apartment" between these two numbers.

The Bigger Picture: Blocks 6 and Up

For the 6th block and everything after that ( $k \ge 6$ ), the author doesn't give a single perfect formula yet. Instead, they provide a recipe to calculate a "ceiling" for how big these blocks can get.

The paper introduces a sequence of numbers called $\alpha_k$ (like $\alpha_6 = 0.382978$ , $\alpha_7 = 0.269877$ , etc.). These numbers act as a shrinking limit. The author proves that for any block number $k$ (where $k \ge 5$ ), the size of that block will never exceed:
$\alpha_k \times h^{k-1}$
plus a little bit of extra noise that gets smaller as $h$ gets huge.

The paper gives a specific formula to calculate the next $\alpha$ number if you know the current one, but this recursive step specifically starts working for the 7th block and beyond (calculating $\alpha_{k+1}$ from $\alpha_k$ requires $k \ge 7$ ). For the 6th block, the paper provides a specific constant value derived from earlier steps. It's like a mathematical assembly line: you feed in the limit for the 6th block, and the machine spits out the limit for the 7th, and so on.

What the Paper Doesn't Say (and what it rules out)

It is very important to know what this paper doesn't do, because the author is very careful about that:

It does not solve the whole puzzle. The author explicitly states that while they have found the 5th block's limits, they haven't found the exact formula for the 5th block yet.
It does not claim the 5th block is exactly $\frac{1}{3}h^4$ . The author conjectures (guesses based on patterns) that the 5th block might be exactly $\frac{1}{3}h^4$ for large $h$ , but they admit this is just a guess. They have not proved it.
It does not say the blocks are simple polynomials. The author is skeptical that all the blocks follow a simple, smooth polynomial pattern forever. While the first few blocks (0 through 4) are known to be "quasi-polynomials" (polynomials that change slightly based on the remainder of $h$ divided by a number), the author doubts this pattern holds for every single block forever.

The "Forbidden" Zone

The paper also explains a "forbidden zone" for the next block. If you have a tower of blocks, there are only a finite number of integers you can try to add that would break the rules. The paper calculates exactly how many "bad" numbers exist that you cannot pick. It turns out that for any existing tower, there are only so many "trap" numbers that would ruin the $B_h$ property, and they are all located within a specific range.

The Mystery of the 6th Block

The author includes a table of numbers for the 6th block ( $\gamma_6$ ) for different values of $h$ , calculated by a computer. However, looking at these numbers, the author admits: "No formula has yet been guessed."
This is a bit like looking at a sequence of numbers and saying, "We know what they are, but we have no idea what the rule is that generates them." The author even lists the first 33 values of $\gamma_6$ and notes that no one has found a pattern for them yet.

The Open Questions

The paper ends by listing the mysteries that remain unsolved:

Can we prove that the 5th block is exactly $\frac{1}{3}h^4$ ?
Can we find formulas for the 6th, 7th, and higher blocks?
Are these blocks distributed evenly in a mathematical sense, or do they cluster in weird ways? (The author notes that for the 2nd block, they seem to cluster in a way that isn't random).
Is there a specific number (like 33) that can never be the difference between two blocks in the tower? (The author notes that for the 2nd block, every number from 1 to 87 appears as a difference except 33, which is a strange coincidence).

In short, this paper builds a sturdy fence around the 5th block and gives a shrinking ladder for all the blocks above it, but the exact shape of the tower and the secret formulas for the higher blocks remain a mystery waiting for the next explorer.

Technical Summary: Bounds for Greedy $B_h$ -sets

Problem Statement
The paper investigates the asymptotic behavior of the greedy algorithm applied to the construction of $B_h$ -sets. A set $A$ of nonnegative integers is defined as a $B_h$ -set if every solution to the equation $a_1 + \dots + a_h = b_1 + \dots + b_h$ (where $a_i, b_i \in A$ ) implies that the multisets $\{a_1, \dots, a_h\}$ and $\{b_1, \dots, b_h\}$ are identical. The primary object of study is the greedy $B_h$ -set, denoted $G(h) = \{\gamma_0, \gamma_1, \gamma_2, \dots\}$ , which is constructed lexicographically by setting $\gamma_0 = 0, \gamma_1 = 1$ , and defining $\gamma_{k+1}$ as the smallest integer such that $\{\gamma_0, \dots, \gamma_{k+1}\}$ remains a $B_h$ -set.

The central problem addressed is determining the growth rate of the $k$ -th element, $\gamma_k(h)$ , as a function of $h$ for fixed $k$ . While exact formulas are known for $k \le 4$ , the behavior for $k \ge 5$ has remained largely unexplored beyond computational enumeration. The paper seeks to establish nontrivial upper and lower bounds for $\gamma_k(h)$ , specifically targeting the fifth element $\gamma_5(h)$ and general bounds for $k \ge 5$ .

Methodology
The author employs a combination of combinatorial analysis, recursive bounding, and detailed case enumeration:

Combinatorial Bounds: The paper utilizes the observation that the number of distinct $h$ -fold sums of a set of size $k+1$ is $\binom{k+h}{k}$ . Since these sums must lie within the interval $[h\gamma_0, h\gamma_k]$ , this yields a baseline lower bound on $\gamma_k(h)$ .
The "Mex" Characterization: A key lemma establishes that $\gamma_{k+1} = \text{mex}(F^{(k)})$ , where $F^{(k)}$ is the set of all integers representable as $\frac{1}{r}\sum_{i=1}^k \gamma_i(m_i - m'_i)$ under specific constraints on multiplicities $m_i, m'_i$ . This characterization allows the author to bound $\gamma_{k+1}$ by counting the number of "forbidden" values in $F^{(k)}$ that exceed a certain threshold.
Lower Bound Construction ( $\gamma_5$ ): To prove the lower bound for $\gamma_5(h)$ , the author defines a specific set of integer vectors $\Delta$ representing valid coefficient combinations for the first four elements. By ordering these vectors lexicographically (based on a specific "odometer" style ordering) and analyzing the image of these vectors under the dot product with $\langle \gamma_1, \gamma_2, \gamma_3, \gamma_4 \rangle$ , the author demonstrates that the images form a contiguous interval. This ensures that the "mex" (the first missing integer) must be at least the maximum value of a specific subset of these images.
Upper Bound Construction ( $\gamma_k$ ): For the upper bound, the author uses an inductive approach. Assuming a bound $\gamma_k(h) \le \alpha_k h^{k-1} + O(h^{k-2})$ , the author estimates the size of the set $F^{(k)}$ above a threshold $\beta_k h^k$ . By stratifying the set $F^{(k)}$ based on the multiplicities of the largest element $\gamma_k$ , and applying "stars-and-bars" combinatorial counting, the author derives a recurrence relation for the coefficients $\alpha_k$ . The sequence $\alpha_k$ is constructed to be non-increasing and converging to zero.

Key Contributions and Results

Lower Bound for $\gamma_5(h)$ : The paper establishes a nontrivial lower bound for the fifth element of the greedy $B_h$ -set:
$\gamma_5(h) \ge \frac{1}{8}h^4 + \frac{1}{2}h^3$
This result is derived through a rigorous analysis of the forbidden sums generated by the first four elements.
Upper Bounds for $\gamma_k(h)$ ( $k \ge 5$ ): The paper provides the first nontrivial upper bounds for $\gamma_k(h)$ for $k \ge 5$ . Specifically, it proves:
$\gamma_k(h) \le \alpha_k h^{k-1} + O(h^{k-2})$
where the constants $\alpha_k$ are defined recursively. The paper explicitly calculates:
- $\alpha_5 \approx 0.467214$
- $\alpha_6 \approx 0.382978$
- $\alpha_7 \approx 0.269877$
- For $k \ge 7$ , $\alpha_{k+1} = \frac{1}{2} \alpha_k + \frac{1}{2^k k!} \sum_{j=0}^{k-1} \binom{k-1}{j} \binom{k}{j} 2^j$ .
  The sequence $\alpha_k$ is shown to decay rapidly, implying $\gamma_k(h)$ grows slower than previously unproven estimates might suggest.
Conjecture on $\gamma_5(h)$ : Based on computational data for $h \le 47$ , the author conjectures a precise asymptotic formula:
$\gamma_5(h) = \frac{1}{3}h^4 + O(h^3)$
This suggests the lower bound of $1/8$ is not tight, and the true leading coefficient is likely $1/3$ .
General Lower Bound: The paper reiterates and contextualizes the general lower bound $\gamma_k(h) \ge \frac{1}{k!}h^{k-1} + O(h^{k-2})$ , confirming that the greedy algorithm produces sets with the correct order of growth for fixed $k$ .

Significance and Claims
The author frames the significance of this work in three main areas:

Aesthetic and Theoretical Necessity: $B_h$ -sets are fundamental objects in combinatorial number theory. The author argues that understanding the greedy algorithm's output for these sets is a natural problem that deserves answers, independent of immediate applications.
Feasibility of Greedy Analysis: The paper contrasts the difficulty of analyzing the greedy algorithm with non-greedy constructions (like Singer's construction using finite fields). While constructing a $B_{100}$ -set with 11 elements via finite fields requires working in $\mathbb{F}_{101}^{11}$ (which is computationally implausible), finding a formula for the 10th element of the greedy $B_{100}$ -set is described as "hard but plausible." This work represents the first step in making such analysis rigorous for $k \ge 5$ .
Understanding the Greedy Algorithm: The primary motivation is to better understand the greedy algorithm for $B_2$ -sets (Sidon sets), which have physical real-world applications (e.g., Golomb rulers, frequency allocation). Since the greedy algorithm is a standard heuristic for additive problems, establishing bounds for $B_h$ -sets contributes to a broader understanding of greedy strategies in additive number theory.

The paper concludes by listing open problems, including the proof of quasi-polynomial formulas for $\gamma_k$ , the uniform distribution of elements in congruence classes, and the infimum of $s$ for which the sum of reciprocal powers of greedy $B_h$ -sets converges. The author remains modest, noting that while the bounds are nontrivial, they may not be tight, and the exact coefficients for $k \ge 5$ remain conjectural.