Homogeneous Structures in Subset Sums and Non-averaging Sets
Presenter
March 7, 2023
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, ..., n} of size at least C n^{1/k}, then, for some d \leq 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, ..., 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.