Large solution-free sets via combinatorial degenerations

Abstract

Consider the linear form $L(x,y,z,w)=3x+y-2z-2w$. For a positive integer $N$, denote by $r_L(N)$ the largest size of a subset of $\{1,2,\dots ,N\}$ that avoids nontrivial solutions to $L=0$. We show that $r_L(N)=\Omega (N^{0.5608687})$, improving the lower bound for Problem 16 in Green's list of open problems. Our proof uses the method of combinatorial degenerations to turn a finite certificate into large solution-free sets. In fact, we can improve Ruzsa's lower bound of $N^{1/2-o(1)}$ for many four-variable equations. Consider $L(x,y,z,w)=ax+by-cz-dw$ with $a,b,c,d\in {\mathbb{Z}}_{>0}$, $a+b=c+d$, $\{a,b\}\ne \{c,d\}$ and $abcd$ not a square. We show that there is ${\epsilon }_L>0$ such that $r_L(N)={\Omega }_L(N^{1/2+{\epsilon }_L})$. Furthermore, we show that for primitive translation-invariant linear forms $L$ in $s$ variables, the lower bound ${\Omega }_s(N^{1/(s-1)})$ coming from a greedy construction is never optimal.

11 pages