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.

11B75 Other combinatorial number theory
PDF BibTeX Cite
Full Text: DOI