Some remarks on the Erdős Distinct subset sums problem

Abstract: Let

l e f t a_{1}, d o t s, a_{n} i g h t s u b s e t m a t h b b N

be a set of positive integers,

a_{n}

denoting the largest element, so that for any two of the

2^{n}

subsets the sum of all elements is distinct. ErdH{o}s asked whether this implies

a_{n} g e q c c d o t 2^{n}

for some universal

c > 0

. We prove, slightly extending a result of Elkies, that for any

a_{1}, d o t s, a_{n} i n m a t h b b R_{> 0}

int_{mathbb{R}} left( frac{sin{ x}}{ x} ight)^2 prod_{i=1}^{n} cos{( a_i x)^2} dx geq frac{pi}{2^{n}}

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} g e q s q r t 2 / p i n c d o t 2^{n}

. The main new insight is that having distinct subset sums and

a_{n}

small requires the random variable

X = p m a_{1} p m a_{2} p m d o t s p m a_{n}

to be close to Gaussian in a precise sense.

Recommendations

Cites Work

Cited In (2)

This page was built for publication: Some remarks on the Erdős Distinct subset sums problem