4
$\begingroup$

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).

$\endgroup$
7
  • 4
    $\begingroup$ 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... $\endgroup$ Oct 3, 2016 at 8:26
  • $\begingroup$ 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$. $\endgroup$ Oct 3, 2016 at 19:48
  • 1
    $\begingroup$ @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$. $\endgroup$
    – Seva
    Oct 3, 2016 at 19:54
  • 2
    $\begingroup$ The probabilistic method yields squarefree sets of size $\asymp c^n$ with $c = 2^{\frac{5}{3}} \simeq 3,1748.$ $\endgroup$
    – js21
    Oct 5, 2016 at 10:35
  • 1
    $\begingroup$ 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$.) $\endgroup$ Oct 5, 2016 at 21:04

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.