I was talking to Peter about the following problem:

What is the largest possible size of a set \(X\subset [n]\) where any quadruple \(a,b,c,d\in X^4\) with \(a+b=c+d\) is just a trivial quadruple, i.e., \(\left\{ a,b\right\} = \left\{ c,d\right\}\).

Using the probabilistic method and alterations I think you get \(n^{\frac{1}{3}}/100\). In particular, include each element with probability \(\frac{1}{100 n^{\frac{2}{3}}}\). Then the expected number of bad quadruples \(a,b,c,d\) is \(\frac{1}{100^{4} n^{\frac{8}{3}}}\cdot n^{3} = n^{\frac{1}{3}}/100^{4}\). So you can probably wholesale kill all the bad quadruples and you aren’t really losing that much by way of density.

But for various reasons I wanted a constructive (i.e., non-randomized) algorithm for constructing such a set.

Peter had this idea: Let \(n=4p^{2}\) for some prime \(p\). Take your set to be \(\{2px + (x^2 \mod p)\mid x\in [p]\}\). So, this has density \(\Omega(\sqrt{n})\) which is impossible to beat and its determinstic. Dang nice!

Claim: this is free of the pattern we want to avoid

\[2px+(x^2 \mod p) + 2py + (y^2 \mod p) = 2pz+(z^2 \mod p) + 2pw + (w^2 \mod p)\] basically by construction means

\[x^2+y^2 \equiv z^2+w^2 \mod p\] \[x+y \equiv z+w \mod p\]

So, \[x^2+(z+w-x)^2 \equiv z^2+w^2 \mod p\] \[x^2+(z+w)^2-2x(z+w)+x^2 \equiv z^2+w^2 \mod p\] \[2x^2+z^2+2zw+w^2-2x(z+w) \equiv z^2+w^2 \mod p\] \[x^2 \equiv x(z+w)-zw \mod p\]

This is a quadratic in \(x\) over a field. So it has two solutions. And basically what’s going to happen is we get one solution \(x_0\) which gives \(y_0=z+w-x_0\) so we have \((x_0,y_0)\) and then its going to turn out that \(y_0,x_0\) is also a solution (obviously).

Anyways, we find that the set is free of the pattern as desired.