# zbMATH — the first resource for mathematics

Behrend-type constructions for sets of linear equations. (English) Zbl 1149.11012
From the text: “A linear equation on $$k$$ unknowns is called a $$(k,h)$$-equation if it is of the form $$\sum_{i=1}^k a_ix_i=0$$, with $$a_i \in \{-h,\ldots,h\}$$ and $$\sum a_i = 0$$. For a $$(k,h)$$-equation $$E$$, let $$r_E(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 three-term arithmetic progressions, are some of the best studied problems in additive number theory.
I. Z. Ruzsa [Acta Arith. 65, No. 3, 259–282 (1993; Zbl 1042.11525)] was the first to address the general problem of the influence of certain properties of equations on $$r_E (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 $$r_E (n)>n^{1-o(1)}$$.
In this paper the author studies 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 $$r_S (n)$$. His main result is that all but an $$O(1/h)$$ fraction of the sets of $$(k,h)$$-equations $$S$$ of size $$k-\lfloor \sqrt{2k}\rfloor+1$$, are such that $$r_S(n)>n^{1-o(1)}$$. He also gives additional results relating properties of sets of equations and $$r_S (n)$$.”
His proof uses a variant of the well-known construction of F. A. Behrend [Proc. Natl. Acad. Sci. USA 32, 331–332 (1946; Zbl 0060.10302)] which provides a large subset of $$\{1,\dots,N\}$$ free from 3-term progressions.

##### MSC:
 11B75 Other combinatorial number theory
Full Text: