Homogeneous structures in subset sums and non-averaging sets

Abstract

We show that for every positive integer $k$ there are positive constants $C$ and $c$ such that if $A$ is a subset of $\{1,2,\dots ,n\}$ of size at least $C{n}^{1/k}$, then, for some $d\le k-1$, the set of subset sums of $A$ contains a homogeneous $d$-dimensional generalized arithmetic progression of size at least $c|A{|}^{d+1}$. This strengthens a result of Szemerédi and Vu, who proved a similar statement without the homogeneity condition. As an application, we make progress on the Erdős--Straus non-averaging sets problem, showing that every subset $A$ of $\{1,2,\dots ,n\}$ of size at least $n^{\sqrt{2}-1+o(1)}$ contains an element which is the average of two or more other elements of $A$. This gives the first polynomial improvement on a result of Erdős and Sárközy from 1990.

34 pages