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

Improve this question
$\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$
    – Ilya Bogdanov
    Commented 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$
    – Victor Protsak
    Commented 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
    Commented 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
    Commented 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$
    – Peter Mueller
    Commented Oct 5, 2016 at 21:04

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .