Homogeneous structures in subset sums and applications

Abstract: In recent joint works with David Conlon and Jacob Fox, we develop novel techniques which allow us to prove a diverse range of results relating to subset sums. In the one-dimensional case, our techniques imply the existence of long homogeneous arithmetic progressions in the set of subset sums under a variety of assumptions. This allows us to resolve a number of longstanding open problems, including: solutions to the three problems of Burr and Erdos on Ramsey complete sequences, for which Erdos later offered a combined total of 350; analogous results for the new notion of density complete sequences; the solution to a conjecture of Alon and Erdos on the minimum number of colors needed to color the positive integers less than n so that n cannot be written as a monochromatic sum; the exact determination of an extremal function introduced by Erdos and Graham on sets of integers avoiding a given subset sum; and, answering a question reiterated by several authors, a homogeneous strengthening of a result of Szemeredi and Vu on long arithmetic progressions in subset sums. In follow-up work in the multi-dimensional case, we show the existence of large homogeneous generalized arithmetic progressions in the set of subset sums of sufficiently large subsets of [n], yielding a strengthening of a seminal result of Szemeredi and Vu. As an application, we make progress on the Erdos--Straus non-averaging sets problem, showing that every subset A of [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 Erdos and Sarkozy from 1990.

number theory

Audience: researchers in the discipline

Combinatorial and additive number theory (CANT 2022)