Exact value of the supremum $R$ of reciprocal sums of sum-free sequences (Erdős, 1962)

A sum-free sequence, in the sense introduced by Erdős in 1962, is a strictly increasing sequence of positive integers in which no term is a sum of two or more distinct other terms. Erdős proved its reciprocal sum is bounded ($<103$) and asked for the best constant; writing $R=\sup\sum_i 1/a_i$ over all sum-free sequences, the best published bounds are $2.0648<R<2.8570$ (Abbott 1987; Yang 2015), while as late as 1999 the record was $2.0648<R<4$. No determination of $R$ is known: the problem of determining the exact value of $R$, and thereby settling Levine and O'Sullivan's conjecture that $R$ is much closer to 2 than to 4, remains open.

Background

A strictly increasing sequence $A=\{a_1<a_2<a_3<\cdots\}$ of positive integers is called a sum-free sequence, in the sense introduced by Erdős in 1962, if no term of $A$ can be written as a sum of two or more distinct other terms of $A$. Because the sequence is increasing, it is equivalent to demand that no term $a_k$ is a sum of distinct earlier terms, i.e. that $a_k$ avoids every subset sum $\sum_{i\in I}a_i$ over subsets $I\subseteq\{1,\dots,k-1\}$ with at least two elements. This ordered notion is stronger than — and must not be confused with — the additive-combinatorics notion of a sum-free set (a set of integers containing no solution of $x+y=z$): under the set notion the odd integers are sum-free and have a divergent reciprocal sum, whereas for Erdős's sequences the finiteness of the reciprocal sum is a genuine theorem, indeed the founding one.

Erdős, in "Remarks on number theory. III" (Matematikai Lapok 13, 1962, in Hungarian), proved that every sum-free sequence has asymptotic density zero and reciprocal sum

$$\rho(A)=\sum_{i\ge 1}\frac{1}{a_i}<103,$$

and asked for the best possible constant. The quantity of this problem is

$$R=\sup_{A\ \mathrm{sum-free}}\rho(A),$$

the supremum of reciprocal sums over all sum-free sequences (the later Chinese-school literature writes $\lambda$ or $\rho$ for the same quantity).

Levine and O'Sullivan (1977) improved the upper bound to $R<4$, with an effective version giving about $3.9998$; constructed a sum-free sequence with $\rho>2.0351$; and conjectured that $R$ is "much closer to 2 than to 4". Their method rests on a relaxation that has organized the subject since. Every sum-free sequence satisfies the counting inequality $a_n\ge(k+1)(n-a_k)$ for all $1\le k<n$, a combinatorial consequence of sum-freeness; an increasing sequence satisfying this inequality is called a $\kappa$-sequence. Sum-free sequences form a subclass of $\kappa$-sequences, so an upper bound valid for all $\kappa$-sequences also bounds $R$. Levine and O'Sullivan conjectured that the supremum over $\kappa$-sequences is attained by the sequence $Q$ — the Levine–O'Sullivan sequence, catalogue entry OEIS A014011 — defined by $q_1=1$ and $q_n=\max_{1\le k<n}(k+1)(n-q_k)$, whose reciprocal sum is about $3.029$. Since this conjectural value exceeds the best known upper bound for $R$ itself, the relaxation cannot be expected to settle $R$; this is the structural reason upper-bound progress on $R$ has required exploiting genuine sum-freeness beyond the counting inequality.

Abbott (1987) improved the lower bound to $R>2.0648$ with an explicit construction adjoining carefully chosen blocks to the base $\{1,2,4,8\}$; this is still the best published lower bound. Deshouillers, Erdős and Melfi, "On a question about sum-free sequences" (Discrete Mathematics 200, 1999), settled adjacent questions of the same lineage: they constructed sum-free sequences with no asymptotic gaps, $a_{k+1}/a_k\to 1$, and, for every $\delta>0$, sum-free sequences with $a_k\sim k^{3+\delta}$; Łuczak and Schoen (2000) then proved the sharp density estimate $A(x)\le 403\sqrt{x\log x}$ (where $A(x)$ counts terms of the sequence up to $x$), together with a construction showing this order is essentially best possible. The reciprocal-sum constant $R$, the classical question of this lineage, is not touched by these density and growth results; Melfi's 2004 survey of exactly this literature records Abbott's lower bound and the Levine–O'Sullivan upper bound as the state of the art at that date.

All subsequent progress has been on the upper bound, by forcing longer initial segments of $\kappa$-sequences with large reciprocal sum and refining the case analysis: Chen (2013) proved $R<3.0752$, showing that a $\kappa$-sequence with large reciprocal sum must begin $1,2,4,6,9,12,15,18,21,24,28,32,36,40,45,50$ (the first sixteen terms of $Q$); Wu (2014) proved $\rho(A)<2.526$ for sum-free sequences whose first term satisfies $a_1\ge 2$; Yang (2015) proved $\rho(A)<2.8570$ for all sum-free sequences, the best published upper bound. On the relaxation side, Yang and Jiang (2015) proved $3.028464<\rho(Q)<3.029891$; Hu and Zhang (2016) determined the asymptotics of the terms $q_n$ of $Q$, settling a conjecture of Chen; and Xue (2024) proved $\lim_{n\to\infty}\log s(n)/\log n=-(\sqrt{5}+1)/2$ for an associated quantity $s(n)$ of $Q$, settling further conjectures of Chen.

Problem Statement

Determine the exact value of

$$R=\sup_{\{a_1<a_2<\cdots\}\ \mathrm{sum-free}}\ \sum_{i\ge 1}\frac{1}{a_i},$$

where a sum-free sequence is a strictly increasing sequence of positive integers in which no term is a sum of two or more distinct other terms (Erdős, 1962). Determining $R$ requires matching upper and lower bounds: an explicit sum-free construction, or explicit family of constructions, whose reciprocal sum equals the claimed value or tends to it, together with a proof that every sum-free sequence has reciprocal sum at most that value. Such a determination in particular bears directly on the Levine–O'Sullivan conjecture (1977) that $R$ is much closer to 2 than to 4. The best published bounds at present are $2.0648<R<2.8570$; narrowing the interval is progress toward, but not a completion of, the problem.

References

1. P. Erdős, Remarks on number theory. III, Matematikai Lapok 13 (1962), 28–38 (Hungarian, English and Russian summaries). zbMATH Zbl 0123.25503, https://zbmath.org/?q=an:0123.25503
2. E. Levine and J. O'Sullivan, An upper estimate for the reciprocal sum of a sum-free sequence, Acta Arithmetica 34 (1977), 9–24. DOI 10.4064/aa-34-1-9-24, https://doi.org/10.4064/aa-34-1-9-24
3. E. Levine, An extremal result for sum-free sequences, Journal of Number Theory 12 (1980), 251–257. DOI 10.1016/0022-314X(80)90061-X, https://doi.org/10.1016/0022-314X(80)90061-X
4. H. Abbott, On sum-free sequences, Acta Arithmetica 48 (1987), 93–96. DOI 10.4064/aa-48-1-93-96, https://doi.org/10.4064/aa-48-1-93-96
5. J.-M. Deshouillers, P. Erdős and G. Melfi, On a question about sum-free sequences, Discrete Mathematics 200 (1999), 49–54. DOI 10.1016/S0012-365X(98)00322-7, https://doi.org/10.1016/S0012-365X(98)00322-7
6. T. Łuczak and T. Schoen, On the maximal density of sum-free sets, Acta Arithmetica 95 (2000), no. 3, 225–229. DOI 10.4064/aa-95-3-225-229, https://doi.org/10.4064/aa-95-3-225-229
7. S. Finch, A Convex Maximization Problem: Discrete Case, arXiv math/9912035 (1999). https://arxiv.org/abs/math/9912035
8. G. Melfi, On certain positive integer sequences, arXiv math/0404555 (2004); Rivista di Matematica della Università di Parma (7) 3* (2004), 253–260. https://arxiv.org/abs/math/0404555
9. YongGao Chen, On the reciprocal sum of a sum-free sequence, Science China Mathematics 56 (2013), no. 5, 951–966. DOI 10.1007/s11425-012-4540-6, https://doi.org/10.1007/s11425-012-4540-6
10. Jiandong Wu, On the reciprocal sum of sum-free sequences, Scientia Sinica Mathematica 44 (2014), no. 2, 117–126 (Chinese, English summary). DOI 10.1360/N012013-00102, https://doi.org/10.1360/N012013-00102
11. Shichun Yang, An upper bound for Erdős reciprocal sum of the sum-free sequence, Scientia Sinica Mathematica 45 (2015), no. 3, 213–232 (Chinese, English summary). DOI 10.1360/N012014-00121, https://doi.org/10.1360/N012014-00121
12. Shichun Yang and Ziguo Jiang, Some results of Levine-O'Sullivan sequence, Acta Mathematica Sinica, Chinese Series 58 (2015), no. 4, 529–534 (Chinese, English summary). zbMATH Zbl 1349.11057, https://zbmath.org/?q=an:1349.11057; publisher page https://actamath.cjoe.ac.cn/Jwk_sxxb_cn/CN/10.12386/A2015sxxb0054
13. Jia Yuan Hu and Wen Peng Zhang, On Levine–O'Sullivan's sequence and its conjecture, Acta Mathematica Sinica, English Series 32 (2016), 961–966. DOI 10.1007/s10114-016-5650-9, https://doi.org/10.1007/s10114-016-5650-9
14. Fanggang Xue, On Levine-O'Sullivan sequence, Advances in Mathematics (Beijing) 53 (2024), no. 3, 662–666 (Chinese). DOI 10.11845/sxjz.2022096b, https://doi.org/10.11845/sxjz.2022096b