Timeline for Square-free sets in $\mathbb F_2^n\oplus\mathbb F_2^n$
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 6, 2016 at 17:24 | answer | added | js21 | timeline score: 3 | |
| Oct 5, 2016 at 21:04 | comment | added | Peter Mueller | 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$.) | |
| Oct 5, 2016 at 17:25 | comment | added | Seva | @js21: it might be even possible to improve this slightly by finding a particular example for some small $n$ and then blowing it up. What would be of interest in this problem is to understand whether there is an upper bound of the form $c^n$ with $c<4$. | |
| Oct 5, 2016 at 10:35 | comment | added | js21 | The probabilistic method yields squarefree sets of size $\asymp c^n$ with $c = 2^{\frac{5}{3}} \simeq 3,1748.$ | |
| Oct 3, 2016 at 19:57 | comment | added | Victor Protsak | You are right! Objection withdrawn. | |
| Oct 3, 2016 at 19:54 | comment | added | Seva | @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$. | |
| Oct 3, 2016 at 19:48 | comment | added | Victor Protsak | 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$. | |
| Oct 3, 2016 at 8:26 | comment | added | Ilya Bogdanov | 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... | |
| Oct 3, 2016 at 7:51 | history | asked | Seva | CC BY-SA 3.0 |