| Behrend-type constructions for sets of linear equations (2008) | |||||||||||||||
Abstract | |||||||||||||||
| A linear equation on k unknowns is called a (k, h)-equation if it is of the form � k i=1 aixi = 0, with ai ∈ {−h,..., h} and � ai = 0. For a (k, h)-equation E, let rE(n) denote the size of the largest subset of the first n integers with no solution of E (besides certain trivial solutions). Several special cases of this general problem, such as Sidon’s equation and sets without threeterm arithmetic progressions, are some of the most well studied problems in additive number theory. Ruzsa was the first to address the general problem of the influence of certain properties of equations on rE(n). His results suggest, but do not imply, that for every fixed k, all but an O(1/h) fraction of the (k, h)-equations E are such that rE(n)> n 1−o(1). In this paper we address the generalized problem of estimating the size of the largest subset of the first n integers with no solution of a set S of (k, h)-equations (again, besides certain trivial solutions). We denote this quantity by rS(n). Our main result is that all but an O(1/h) fraction of the sets of (k, h)-equations S of size k − ⌊ √ 2k ⌋ + 1, are such that rS(n)> n 1−o(1). We also give several additional results relating properties of sets of equations and rS(n). | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||