Some Remarks on the Erdős Distinct Subset Sums Problem

2022/08/25 by Stefan Steinerberger, Steinerberger, Stefan
Mathematics · #Classical Analysis and ODEs (math.CA) #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Number Theory (math.NT)

paper · pdf · doi:10.48550/arxiv.2208.12182

openalex publication_date 2022/08/25 · openalex created_date 2022/08/27 · openalex updated_date 2026/08/04

Abstract

Let \a₁, …, a_n\ ⊂ ℕ be a set of positive integers, a_n denoting the largest element, so that for any two of the 2ⁿ subsets the sum of all elements is distinct. Erdős asked whether this implies a_n ≥ c ⋅ 2ⁿ for some universal c>0. We prove, slightly extending a result of Elkies, that for any a₁, …, a_n ∈ ℝ_>0 ∫_ℝ ( \fracsin x x )² ∏_i=1ⁿ cos( a_i x)² dx ≥ \fracπ2ⁿ with equality if and only if all subset sums are 1-separated. This leads to a new proof of the currently best lower bound a_n ≥ √(2/πn) ⋅ 2ⁿ. The main new insight is that having distinct subset sums and a_n small requires the random variable X = ± a₁ ± a₂ ± … ± a_n to be close to Gaussian in a precise sense.

Related

• Variations on the Erdős distinct-sums problem
• A note on the Erdős distinct subset sums problem
• Variants of the Erdős distinct sums problem and variance method
• The Erdős distinct subset sums problem in a modular setting
• A Generalisation on Erdős Distinct Subset Sums Problem