Code-based $[3,1]$-avoiders in finite affine spaces $\mathrm{AG}(n,2)$

Abstract

The author, together with Nagy, studied the following problem on unavoidable intersections of given size in binary affine spaces. Given an $m$-element set $S\subseteq {\mathbb{F}}_2^n$, is there guaranteed to be a $[k,t]$-flat, that is, a $k$-dimensional affine subspace of ${\mathbb{F}}_2^n$ containing exactly $t$ points of $S$? Such problems can be viewed as generalizations of the cap set problem over the binary field. They conjectured that for every fixed pair $(k,t)$ with $k\ge 1$ and $0\le t\le 2^k$, the density of values $m\in \{0,...,2^n\}$ for which a $[k,t]$-flat is guaranteed tends to $1$. In this paper, motivated by the study of the smallest open case $(k,t)=(3,1)$, we present explicit constructions of sets in ${\mathbb{F}}_2^n$ avoiding $[k,1]$-flats for exponentially many sizes. These sets rely on carefully constructed binary linear codes, whose weight enumerators determine the size of the construction.

11 pages