Arithmetic properties of sets with a small basis

In modern language, the Goldbach conjecture asserts that the set of primes is an additive basis for the set of even integers greater then two, which simply means that any such integer is a sum of two primes. In the beginning of 20th century it became clear, thanks to the work of Shnirelmann, Linnik, Mann, that one can make progress on hard classical problems by studying properties of additive bases on their own right. However, it seems that until the paper of Erdös and Newman published in 1976, the sets in question where assumed to be infinite, perhaps due to the fact that classical problems in additive number theory deal with infinite sets of numbers. Instead, Erdös and Newman suggested to look at additive bases of finite sets. The authors asked what is the most economical way to cover a given set by the pairwise sums of another set, which one wants to make as small as possible. The minimal basis size tells exactly how economical such a covering can be, and in general it is rather hard to estimate. In comparison to a significant corpus of papers authored by Erdös and collaborators on infinite additive bases, the paper of Erdös and Newman went relatively unnoticed. The present project aims to fill the gap by a more systematic study of sets with small basis (e.g. efficiently covered by sums). To our knowledge, any result in this direction is likely to be new. On the other hand, a better understanding of sets admitting a small basis would provide insights for known open problems in the areas of additive number theory and discrete geometry. Last, but not least, sets with small bases appear naturally in cryptographic attacks related to computing a discrete logarithm, which is a cornerstone of many modern public-key encryption protocols. The main hypothesis of the project is that the minimal basis size (e.g. how efficient it can be covered by sums) reflects some subtle structural properties of the original set which in turn can be combined with intuition inspired by a well-known phenomenon in the field of arithmetic combinatorics. In very rough terms, it says that a set cannot look like a geometric and an arithmetic progression at the same time. One of the goals of the project is to explore how far this connection can be pushed, as certain limitations are already visible from the work of the present author. The methods of the project vary from arguments in arithmetic combinatorics to a fusion of analytic, number-theoretic and algebraic techniques which is shown by a broad spectrum of relevant publications.