# Square-free sets in $\mathbb F_2^n\oplus\mathbb F_2^n$

A square in $\mathbb F_2^n\oplus\mathbb F_2^n$ is a quadruple of the form $$(u,v)+\{(0,0),(0,d),(d,0),(d,d)\},\quad u,v,d\in\mathbb F_2^n,\ d\ne 0.$$ A set $A\subset\mathbb F_2^n\oplus\mathbb F_2^n$ is square-free if it does not contain a square.

What is the maximum size of a square-free set in $\mathbb F_2^n\oplus\mathbb F_2^n$ (asymptotically, for $n$ growing)?

Equivalently, considering the complements:

What is the minimum size of a set in $\mathbb F_2^n\oplus\mathbb F_2^n$, blocking every square?

(Here "blocking" means "intersecting non-trivially".)

It may be worth noting that there do exist small-degree polynomials in $\mathbb F_2[x_1,\dotsc,y_n]$ vanishing on at least one corner of every square; for instance, assuming for simplicity that $n$ is even, $$(x_1+y_2)(x_3+y_4)\dotsb(x_{n-1}+y_n)$$ (thanks to Peter Pach for this example).

• Set $V=\mathbb F_2^n\oplus \mathbb F_2^n$. Define $\varphi\colon V\to V$ by $\varphi(x,y)=(y,x+y)$. Then $\varphi^3=1$, and $\mathbb F_2[\varphi]\cong \mathbb F_4$.Thus $V$ gets a structure of $\mathbb F_4$-linear space, and a square becomes an affine line of a special form. In particular, every set containing no lines satisfies your requirements. Thus, at least $3^n$ is achievable... – Ilya Bogdanov Oct 3 '16 at 8:26
• There are some issues with this argument. If $n$ is even, $|V|=2^{n+1}$ is not a power of 4. Thus $V$ cannot have a structure of vector space over $\Bbb{F}_4$. – Victor Protsak Oct 3 '16 at 19:48
• @Victor Protsak: $|V|=2^{2n}$. Besides, using a different argument, I can related square-free sets to line-free sets in $(\mathbb Z/4\mathbb Z)^n$, which also gives the lower bound of $3^n$. – Seva Oct 3 '16 at 19:54
• The probabilistic method yields squarefree sets of size $\asymp c^n$ with $c = 2^{\frac{5}{3}} \simeq 3,1748.$ – js21 Oct 5 '16 at 10:35
• For $n=2$ and $n=3$ the optimal values are $12$ and $42$. For $n=4$ the naive program gets stuck, so far it only shows that the optimal value is $\ge144$. (And of course, a trivial upper bound is $4\cdot42=168$.) – Peter Mueller Oct 5 '16 at 21:04

Let $d_n$ be the maximal density of a squarefree set in $\mathbb F_2^n\oplus\mathbb F_2^n$. Then it is unknown whether there exists a constant $c < 1$ such that $d_n = O(c^n)$. Indeed, such a result would imply a similar bound for cornerfree sets, and the best known bound for cornerfree sets is (to my knowledge) that one, which gives a density $= O \left( \frac{\log(\log(n))}{\log(n)} \right)$.

However, it is easy to see that $d_n = o(1)$. This follows for example from the density Hales-Jewett theorem, since any combinatorial line in $(\mathbb F_2 \oplus\mathbb F_2)^n$ is a square.