Bounds for greedy \(B_h\)-sets

Kevin O'Bryant¹

¹City University of New York, College of Staten Island and The Graduate Center

The electronic journal of combinatorics, Tome 32 (2025) no. 2

Résumé

A set ${\cal A}$ of nonnegative integers is called a $B_h$-set if every solution to\(a_1+\dots+a_h = b_1+\dots+b_h\), where $a_i,b_i \in {\cal A}$,has $\{a_1,\dots,a_h\}=\{b_1,\dots,b_h\}$ (as multisets). Let $\gamma_k(h)$ be the $k$-th positive element of the greedy $B_h$-set. We give a nontrivial lower bound on $\gamma_5(h)$, and a nontrivial upper bound on $\gamma_k(h)$ for $k\ge 5$. Specifically, $\frac 18 h^4 +\frac12 h^3 \le \gamma_5(h) \le 0.467214 h^4+O(h^3)$, although we conjecture that $\gamma_5(h)=\frac13 h^4 +O(h^3)$. We show that $\gamma_k(h) \ge \frac{1}{k!} h^{k-1} + O(h^{k-2})$ for $k\ge 1$ and $\gamma_k(h) \le \alpha_k h^{k-1}+O(h^{k-2})$, where $\alpha_6 := 0.382978$, $\alpha_7 := 0.269877$, and for $k\ge 7$, $\alpha_{k+1}:= \frac{1}{2^k k!} \sum_{j=0}^{k-1} \binom{k-1}j\binom kj 2^j$. This work begins with a thorough introduction and concludes with a section of open problems.

Détail

DOI : 10.37236/12977

Classification : 11B13, 05B10