Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. There is an integer n0n_0 such that, for every integer n≥n0n\ge n_0, the number of sets S⊆{1,…,n}S\subseteq\{1,\ldots,n\} with ∑s∈S1/s≤1\sum_{s\in S}1/s\le1 is at most 20.93n2^{0.93n}. The sets with reciprocal sum exactly one are among them, so the count asked for in the problem is also at most 20.93n2^{0.93n} for large nn.

Covers. The eventual upper bound only: it rules out the count 2n−o(n)2^{n-o(n)} that had been considered possible. The value disproved records what the bound decides: the 1980 monograph of Erdős and Graham asks, on its printed page 36, whether there are 2cn2^{cn} such subsets and whether there are 2n−o(n)2^{n-o(n)}, and the bound answers the second question no. It does not give the exponential rate, a lower bound for the exact-sum count, an explicit n0n_0, or the claim that 0.930.93 is sharp. The rate itself is settled by the two full claims, Conlon and collaborators' Theorem 1 and Liu and Sawhney's Theorem 1.2.

Acceptance. The site's curator, Thomas Bloom, credits this bound in the problem's commentary, independently of the author. The note is not refereed: its arXiv v5 of 28 April 2024 says that it is kept for archival purposes and was not submitted to a journal. The arXiv record was first posted on 25 March 2024 and revised four times, the last on 28 April 2024; the library read v5, holds no file of it, and has not compared the earlier versions. The library's theorem page gives a complete ordinary reconstruction of the proof, which maps subset indicators to independent signs and bounds one tail of the signed sum by a split product of exponential moments.