# Avoiding intersections of given size in finite affine spaces
$\mathrm{AG}(n,2)$

Benedek Kovács ELTE Linear Hypergraphs Research Group, Eötvös Loránd
University, Budapest, Hungary. The author is supported by the ÚNKP-22-3 New
National Excellence Program of the Ministry for Culture and Innovation from
the source of the National Research, Development and Innovation Fund. E-mail:
<EMAIL_ADDRESS>Zoltán Lóránt Nagy ELTE Linear Hypergraphs Research Group,
Eötvös Loránd University, Budapest, Hungary. The author is supported by the
Hungarian Research Grant (NKFI) No. PD 134953. E-mail<EMAIL_ADDRESS>
###### Abstract

We study the set of intersection sizes of a $k$-dimensional affine subspace
and a point set of size $m\in[0,2^{n}]$ of the $n$-dimensional binary affine
space $\mathrm{AG}(n,2)$. Following the theme of Erdős, Füredi, Rothschild and
T. Sós, we partially determine which local densities in $k$-dimensional affine
subspaces are unavoidable in all $m$-element point sets in the $n$-dimensional
affine space.
We also show constructions of point sets for which the intersection sizes with
$k$-dimensional affine subspaces takes values from a set of a small size
compared to $2^{k}$. These are built up from affine subspaces and so-called
subspace evasive sets. Meanwhile, we improve the best known upper bounds on
subspace evasive sets and apply results concerning the canonical signed-digit
(CSD) representation of numbers.
Keywords: unavoidable, affine subspaces, evasive sets, random methods,
canonical signed-digit number system.

##  1 Introduction

In this paper, we address the following general problem. Let $S$ be a subset
of size $m$ of the affine space $\mathrm{AG}(n,q)$. Does there always exist a
$k$-dimensional affine subspace which contains exactly $t$ points of $S$? A
$k$-dimensional affine subspace will be referred to as a $k$-flat, and a
$k$-flat which contains exactly $t$ points of a given set $S$ will be called a
$[k,t]$-flat (induced by $S$). If for every $m$-element set $S$ in the
$n$-dimensional affine space, there is a $k$-flat containing exactly $t$
points of $S$, then we say that the pair $[n,m]$ forces the pair $[k,t]$, or
that $t$-sets are unavoidable in $k$-flats. We use the notation
$[n,m]_{q}\rightarrow[k,t]$ for this concept.

Our main focus will be the case $q=2$, and we will omit the index $q$ except
when we wish to refer to arbitrary finite fields.

The graph theoretic analogue of this problem was initiated by Erdős, Füredi,
Rothschild and T. Sós [10].

Let $G(n,m)$ denote a graph on $n$ vertices and $m$ edges. Fix a positive
integer $k$ and a pair of integers $(n,m)$ such that $0\leq
m\leq\binom{n}{2}$. For which $t$ does it hold that any $n$-vertex graph with
$m$ edges contains an induced subgraph on $k$ vertices having exactly $t$
edges? Equivalently, we are seeking pairs $(k,t)$ such that $k$-vertex induced
subgraphs with $t$ edges are unavoidable in graphs of the form $G(n,m)$.
Erdős, Füredi, Rothschild and T. Sós introduced the notation
$(n,m)\rightarrow(k,t)$ for the case when this is true.

Their main result showed that forced pairs $(k,t)$ are rare in the following
sense. Consider the set $Sp(n;k,t)$ of all edge cardinalities $m$ such that
$(n,m)\rightarrow(k,t)$. Its density is the ratio
$\frac{|Sp(n;k,t)|}{\binom{n}{2}}$. They proved that the limit superior of
this density is bounded from above by $2/3$ apart from a handful cases, and is
$0$ for the majority of the pairs $(k,t)$ for fixed and large enough $k$.
Erdős, Füredi, Rothschild and T. Sós conjectured that in fact it is bounded
from above by $1/2$ apart from finitely many pairs $(k,t)$. This was confirmed
recently by He, Ma and Zhao [16]. Several related problems have been studied
in the last couple of years [1, 2, 6].

Our problem can be viewed as the $q$-analogue of this problem, when we
investigate whether all subspaces of given dimension $k$ can avoid to have an
intersection of size $t$ with an $m$-element set of the space
$\mathrm{AG}(n,q)$, which corresponds to $\mathbb{F}_{q}^{n}$.

Note that problems of similar flavour have gained significant interest in the
past and are trending as well in recent years. The celebrated Sylvester-Gallai
theorem showed that if a set of $m$ points in the Euclidean $2$-dimensional
space is not collinear, then there will be a line which intersects the point
set in exactly $2$ points.
Considering the case $q=3$, $k=1$ and $t=3$, we in turn get the famous cap set
problem, which asks for the maximum number of points in $\mathrm{AG}(n,3)$
without creating a line, or in other words, without containing a $3$-term
arithmetic progression. There has been a recent breakthrough due to Ellenberg
and Gijswijt [9], building upon the ideas of Croot, Lev and Pach [8], which
showed that to avoid complete lines, $|S|/3^{n}$ has to be exponentially
small. The arithmetic removal lemma implies a supersaturation result on the
number of complete lines [13] from which bounds on the case $[1,3]$ translate
to similar bounds for the case of complete $k$-flats, i.e., cases $[k,3^{k}]$.
This connection highlights the complexity of the problem.

There has been significant interest in the case when we want to forbid each
intersection of size larger than or equal to $t$ instead of avoiding only
$t$-sets in $k$-flats. If there exists a set $S\subseteq AG(n,q)$ for which
all $k$-dimensional affine subspaces contain at most $c$ points of $S$, then
$S$ is called $(k,c)$-subspace evasive. The importance of such sets is
highlighted by its connections to explicit constructions of bipartite Ramsey
graphs by Pudlák and Rödl [22] and to list-decodable codes by Guruswami [14].

By a standard application of the first moment method, Guruswami obtained
random subsets of $\mathbb{F}^{n}$ of large size which are $(k,c)$-subspace
evasive. (Here and throughout the paper, $\mathbb{F}$ denotes a finite field.)

######  Theorem 1.1 (Guruswami, [14]).

For any fixed pair $(k,c)$, there exists a $(k,c)$-evasive set in
$\mathbb{F}^{n}$ of size at least $C\cdot|\mathbb{F}|^{n(1-\frac{2k}{c})}$,
where $C>0$ is a constant independent of $n$.

######  Corollary 1.2.

For any fixed pair $(k,t)$ with $t>1$, there exists a constant $C>0$ for which
the following holds: if $m\leq C\cdot 2^{n(1-\frac{2\cdot k}{t-1})}$, then
$t$-sets are avoidable in the $k$-flats of $\mathrm{AG}(n,2)$, i.e., in this
case $[n,m]\not\rightarrow[k,t]$.

Surprisingly it turned out that the obtained bounds are sharp in a weak sense.
Improving the results of Ben-Aroya and Shinkar [3], Sudakov and Tomon proved
the following.

######  Theorem 1.3 (Sudakov and Tomon, [25]).

Let $\mathbb{F}$ be a field, $k\in\mathbb{Z}^{+}$ and
$\varepsilon\in(0,0.05)$. If $n$ is sufficiently large with respect to $k$,
and $S\subseteq\mathbb{F}^{n}$ has size
$m\geq|\mathbb{F}|^{n(1-\varepsilon)}$, then $S$ is not
$(k,\frac{k-\log_{2}(1/\varepsilon)}{8\varepsilon})$-subspace evasive.

Note however that $S$ being non-$(k,c)$-evasive does not necessarily imply
that $S$ contains a $k$-flat with $c+1$ points, except when
$c=|\mathbb{F}|^{n}-1.$ The latter case on the other hand is not covered by
the theorem, as $\frac{k-\log_{2}(1/\varepsilon)}{8\varepsilon}<2^{k-3}$ holds
for every $\varepsilon\in(0,0.05)$.

###  1.1 Our main results

Similarly to the investigation in [10], we define the set of forcing sizes $m$
with respect to $[k,t]$, which are the sizes for which a $[k,t]$-flat is
unavoidable, as follows.

######  Definition 1.4.

$Sp(n;k,t):=\\{m:[n,m]_{q}\rightarrow[k,t]\\}$

is called the set of forcing sizes with respect to $n,k,t$, and we refer to it
as the $(n;k,t)$-spectrum.

$\rho(n;k,t):=\frac{Sp(n;k,t)}{|\mathbb{F}|^{n}}$

is the density of the spectrum.

(We will always assume that $k\leq n$, even if it is not specifically
mentioned.)

Our aim is to characterize the spectra or at least bound the density of the
spectra for various values of $k$ and $t$. Note that from now on, $\mathbb{F}$
is considered to be the binary field.

In their paper [10], Erdős, Füredi, Rothschild and T. Sós construct some graph
families which only induce $k$-vertex subgraphs of specific sizes. These
families are the combination of graphs which are very dense (cliques, or
graphs close to cliques in edit distance) and sparse graphs (forests, or
graphs with high girth).

In that aspect, we follow their footsteps and provide point sets which are
combinations of disjoint full flats and point sets which hit every $k$-flat in
only a small number of points.

These constructions show that the binary representation of $m$ and $t$ will be
key in our results concerning sizes $m$ not in the spectrum.

######  Theorem 1.5.

$Sp(n;k,t)$ will not contain those values $m>0$ which have fewer $1$-digits
than the number of $1$-digits of $t$ in the binary representation, denoted by
$s_{2}(t)$, hence at least

$1+\sum_{i=0}^{s_{2}(t)-1}\binom{n}{i}$

values are missing from the $(n;k,t)$-spectrum provided that $0<t<2^{k}$.

In fact, another numeral system, the so-called canonical signed-digit binary
representation of integers will also have a central role. We formulate the
corresponding Proposition 3.10 in Section 3, which is the analogue of Theorem
1.5.

These results can be combined with the former results on $(k,c)$-subspace
evasive sets. Indeed, if we take a point set $S_{0}$ which avoids
$k$-dimensional subspaces having intersection of size $r$ for all
$r\in[t_{1},t_{2}]$ with $c\leq t_{2}-t_{1}$, then the union of $S_{0}$ and a
$(k,c)$-subspace evasive set $S_{1}$ will avoid $k$-dimensional subspaces with
intersections of size $t\in[t_{1}+c,t_{2}]$.

As we have seen in Corollary 1.2, subsets of large evasive sets provide point
sets of various sizes which do not induce $[k,t]$-flats for large enough $t$.
We improve upon the probabilistic construction of Guruswami in order to obtain
larger point sets and to apply the result for every $t\geq k+1$.

######  Theorem 1.6 (General improved lower bound on evasive sets).

Let $k,c\in\mathbb{Z}^{+}$ with $c\geq k+1$. Then for $n>k$, there exists a
$(k,c)$-evasive set in $\mathbb{F}_{q}^{n}$ of size at least

$K\cdot q^{n\left(1-\frac{k}{c}\right)}$

for some constant $K$ independent of $n$.

The combination of these yields long intervals of missing values from the
spectrum $Sp(n;k,t)$.

######  Theorem 1.7.

Let $k$ and $t$ be fixed integers such that $1\leq t\leq 2^{k}-1$ and suppose
that the difference between the number of nonzero digits of $t$ and $m$ is
greater than $\left\lceil\frac{1}{2}\left(\log_{2}c+1\right)\right\rceil$ for
some positive integers $m$ and $c$ in the so-called canonical signed-digit
binary representation. Then $[n,m^{\prime}]\not\to[k,t]$ holds for every
$m^{\prime}\in\left[m-\left(K\cdot\frac{m}{2^{n}}\cdot
2^{n\left(1-\frac{k}{c}\right)}\right),m+\left(K\cdot\frac{2^{n}-m}{2^{n}}\cdot
2^{n\left(1-\frac{k}{c}\right)}\right)\right]$, where $K$ is a positive
constant depending only on $k$ and $c$.

Our next goal is to prove results on long intervals the spectrum $Sp(n;k,t)$
must contain for certain special values of $t$. Our first results in this
direction concern the case when $t$ is a power of $2$.

######  Theorem 1.8.

Suppose that $k>\ell\geq 1$ are integers. Then there exist absolute constants
$C>0$ and $0<D<1$ such that $[n,m]\rightarrow\left[k,2^{k-\ell}\right]$ for
$m\in\left[C\cdot 2^{n\left(1-\frac{1}{2^{k-\ell-1}}\right)},D\cdot
2^{n}\right]$. Moreover, for each $\varepsilon>0$ and sufficiently large $n$,

$\rho(n;k,2^{k-\ell})\geq\frac{1-\varepsilon}{2^{\ell-1}}.$

As for the case $\ell=0$, it can be shown analogously to the proof of
Szemerédi’s Cube Lemma (see [26, Corollary 2.1]) that in order for a set
$S\subseteq\mathbb{F}_{2}^{n}$ to induce a $[k,2^{k}]$-flat, it suffices for
$\frac{|S|}{2^{n}}$ to be exponentially small, and so
$\lim_{n\to\infty}\rho(n;k,2^{k})=1$. For $\ell=1$, Theorem 1.8 implies that
$\lim_{n\to\infty}\rho(n;k,2^{k-1})=1$ holds as well, and we have an even
stronger result in this case:

######  Theorem 1.9.

Let $k\geq 2$. Then there exists an absolute constant $C>0$ such that
$[n,m]~{}\rightarrow~{}\left[k,2^{k-1}\right]$ for $m\in\left[C\cdot
2^{n\left(1-\frac{1}{2^{k-2}}\right)},2^{n}-C\cdot
2^{n\left(1-\frac{1}{2^{k-2}}\right)}\right]$.

A closely related work to the case of full flats ($\ell=0$) is due to Etzion
and Vardy [11], who determined the minimal number of points needed in
$\mathrm{AG}(n,2)$ (and in general in $\mathrm{AG}(n,q)$) in order to cover
each subspace of a given dimension $k$, under the name of $q$-Turán designs
$\mathcal{T}_{q}(n,k,1)$. Their result
$\mathcal{T}_{q}(n,k,1)=\frac{q^{n-k+1}-1}{q-1}$ highlights how much harder it
is to avoid a complete $k$-flat in our affine variant compared to theirs.

As we have seen, if $t$ is not a power of $2$, then we must expect that the
spectrum is scattered, several values of $m$ are missing from it.

For $k\leq 2$ we have complete characterizations of the spectra, except for
the case $[k,t]=[2,4]$ which corresponds to Sidon sets of binary spaces. We
present the characterization and discuss the results related to the
exceptional case in Section 2.

Finally we discuss a case when $t$ is the sum of two consecutive powers of
$2$. This case is significantly more involved compared to the case of
$t=2^{k-\ell}$.

######  Theorem 1.10.

For every pair $(k,\ell)$ of integers with $2\leq\ell\leq k-1$, the density of
integer values $m$ within the interval $\left[0,\frac{1}{2^{\ell-1}}\cdot
2^{n}\right]$ for which $[n,m]\to[k,3\cdot 2^{k-\ell}]$ holds, tends to $1$ as
$n\to\infty$. Hence $\rho(n;k,3\cdot 2^{k-\ell})\geq\frac{1}{2^{\ell-1}}.$

In general, we have the following conjecture.

######  Conjecture 1.11.

$\lim_{n\to\infty}\rho(n;k,t)=1.$

The paper is organized as follows: in Section 2 we present notations and some
tools we will use, then discuss the cases when $k$ is small. In Section 3 we
refine the probabilistic bound of Guruswami and prove Theorem 1.6. We continue
by collecting the results on sizes $m$ for which $[k,t]$-flats are avoidable.
We discuss the case when $t$ is a power of $2$ in Section 4, and present the
proof of Theorem 1.8 and 1.9. Then we relate the additive energy of a set $S$
with the number of $[2,3]$-flats induced by $S$ in Section 5. We prove bounds
on the additive energy via good estimates on the size of certain cuts in
hypercube graphs, which enables us to derive Theorem 1.10. Finally, the last
section is devoted to concluding remarks and open problems.

##  2 Preliminaries, small cases for $k$

###  2.1 Notations and tools

For a pair of integers $a\leq b$, $[a,b]$ will be used to refer to the set
$\\{a,a+1,...,b\\}\subseteq\mathbb{Z}$. We use the standard additive
combinatorial notation for the sumset $A+B$ of two subsets $A$ and $B$ of an
abelian group $G$ as the set of all sums of an element from $A$ with an
element from $B$, i.e., $A+B=\\{a+b:a\in A,b\in B\\}$. $A-B$ is defined
similarly. If one of the sets consists of a single element, we omit the
brackets for short.
The complement of a set $S$ will be denoted by $\overline{S}$.

It will be useful to define the $k$-dimensional profile $\mathrm{pf}_{k}(L)$
of a set $L\subseteq\mathbb{F}_{2}^{n}$ as the set of all possible
intersection sizes of $L$ and a $k$-flat of $\mathbb{F}_{2}^{n}$. Thus we have
that $t\not\in\mathrm{pf}_{k}(L)$ implies $|L|\not\in Sp(n;k,t)$. We show a
simple but useful lemma concerning the $k$-dimensional profiles.

######  Lemma 2.1.

  1. (i)

Suppose that $L_{1},L_{2}\subseteq\mathbb{F}_{2}^{n}$ are disjoint sets. Then
$\mathrm{pf}_{k}(L_{1}\cup
L_{2})\subseteq\mathrm{pf}_{k}(L_{1})+\mathrm{pf}_{k}(L_{2})$.

  2. (ii)

Suppose that $L_{1}\subseteq L_{2}\subseteq\mathbb{F}_{2}^{n}$. Then
$\mathrm{pf}_{k}(L_{2}\setminus
L_{1})\subseteq\mathrm{pf}_{k}(L_{2})-\mathrm{pf}_{k}(L_{1})$.

###### Proof.

These immediately follow from the fact that for any $k$-flat $H$, $|H\cap
L_{i}|\in\mathrm{pf}_{k}(L_{i})$. ∎

The next lemma will be useful for inductive arguments.

######  Lemma 2.2 (Charbit et al., [7]).

Given any subset $S\subseteq\mathbb{F}_{2}^{n}$ of size $m$, there exists a
linear subspace $H\leq\mathbb{F}_{2}^{n}$ of dimension $n-1$ such that $|H\cap
S|\in\left[\frac{1}{2}m-\frac{1}{2}\sqrt{m},\frac{1}{2}m+\frac{1}{2}\sqrt{m}\right]$.

In order to apply bounds on the number of certain affine subspaces, important
ingredients will be the Gaussian binomials and their estimates.

######  Definition 2.3.

$\begin{bmatrix}n\\\ k\end{bmatrix}_{q}$ denotes the number of $k$-dimensional
subspaces of an $n$-dimensional vector space over $\mathbb{F}_{q}$.

######  Corollary 2.4.

$q^{n-k}\begin{bmatrix}n\\\ k\end{bmatrix}_{q}$ is the number of $k$-flats in
$\mathrm{AG}(n,q).$

We will apply bounds on these Gaussian binomials, i.e. on the number of
subspaces. As it was proved in [17], we have

######  Lemma 2.5 (Héger, Nagy, [17]).

$\begin{bmatrix}n\\\ k\end{bmatrix}_{2}<2^{(n-k)k+1}\cdot e^{2/3}$ and
$\begin{bmatrix}n\\\ k\end{bmatrix}_{q}<q^{(n-k)k}\cdot e^{1/(q-2)}$ for $q>2$
and $k>0$.

We will also use the so-called Euler function
$\phi(q)=\prod_{k=1}^{\infty}(1-q^{k})$ where $q\in\mathbb{C}$, $|q|<1$.

For a graph $G=(V,E)$ and any set $A\subseteq V$, $e(A)$ denotes the number of
edges spanned by $A$, and if $A$ and $B$ are disjoint subsets of $V$ then
$e(A,B)$ denotes the number of edges between $A$ and $B$.

###  2.2 Small cases

We will first investigate $Sp(n;k,t)$ in cases where $k$ is small. Firstly, we
can see that determining the spectrum $Sp(n;k,t)$, or its density, is
essentially the same problem as determining $Sp(n;k,2^{k}-t)$, or its density:

######  Lemma 2.6.

If $n,k\geq 1$ are integers and $0\leq t\leq 2^{k}$, then
$Sp(n;k,t)=2^{n}-Sp(n;k,2^{k}-t)$.

###### Proof.

Suppose $m\in Sp(n;k,t)$. Now take any set $T\subseteq\mathbb{F}_{2}^{n}$ with
$|T|=2^{n}-m$. Then $\overline{T}$ is a set of size $m$, hence there exists a
$k$-flat $F_{k}$ such that $|\overline{T}\cap F_{k}|=t$. Then $|T\cap
F_{k}|=|F_{k}|-t=2^{k}-t$, so $T$ induces a $[k,2^{k}-t]$-flat. So $2^{n}-m\in
Sp(n;k,2^{k}-t)$, meaning that $m\in 2^{n}-Sp(n;k,2^{k}-t)$. The other
containment can be seen by symmetry. ∎

######  Proposition 2.7.

  1. (i)

$Sp(n;1,0)=[0,2^{n}-2]$,

  2. (ii)

$Sp(n;1,1)=[1,2^{n}-1]$,

  3. (iii)

$Sp(n;1,2)=[2,2^{n}]$,

  4. (iv)

$Sp(n;2,1)=[0,2^{n}]\setminus(\\{2^{n}\\}\cup\\{2^{n}-2^{d}:d\in[0,n]\\})$,

  5. (v)

$Sp(n;2,2)=[2,2^{n}-2]$,

  6. (vi)

$Sp(n;2,3)=[0,2^{n}]\setminus(\\{0\\}\cup\\{2^{d}:d\in[0,n]\\})$.

###### Proof.

Consider part (i) first and observe that a $[1,0]$-flat consists of any two
points outside $S$, which in turn implies the claim. Similarly in part (iii),
any two points in $S$ make a $[1,2]$-flat. For part (ii), a $[1,1]$-flat
consists of any two points such that one of them is in $S$ and the other is
not, so a set $S\subseteq\mathbb{F}_{2}^{n}$ induces a $[1,1]$-flat if and
only if $1\leq|S|\leq 2^{n}-1$.
For parts (iv) and (vi), a nonempty set $S$ induces a $[2,3]$-flat if and only
if there exists $x\in\mathbb{F}_{2}^{n}$ and nonzero
$a,b\in\mathbb{F}_{2}^{n}$ such that $x,x+a,x+b\in S$ but $x+a+b\not\in S$.
This is exactly the condition such that $S$ is not an affine subspace of
$\mathbb{F}_{2}^{n}$, hence the sizes forcing a $[2,3]$-flat are exactly those
which are not zero and not powers of 2. By applying Lemma 2.6, we also obtain
the sizes forcing a $[2,1]$-flat.

For part (v), we can see that a $[2,2]$-flat needs at least two points in $S$
and at least two not in $S$, so $Sp(n;2,2)\subseteq[2,2^{n}-2]$. On the other
hand, if $2\leq|S|\leq 2^{n}-2$, then take a pair of points $(s,s^{\prime})$
with $s\in S$ and $s^{\prime}\not\in S$. Letting $v=s^{\prime}-s$, subdivide
$\mathbb{F}_{2}^{n}$ into the pairs determined by the $\langle
v\rangle$-cosets. Note that any two of the pairs form a $2$-flat. Knowing that
the pair $\\{s,s^{\prime}\\}$ contains exactly one element of $S$ (i.e. is a
$[1,1]$-flat), if we found another pair with exactly one element of $S$ then
they together would form a $[2,2]$-flat. Assuming there is no other such pair,
all other pairs must either be $[1,2]$\- or $[1,0]$-flats. But a $[1,2]$-flat
and a $[1,0]$-flat also form a $[2,2]$-flat together, so assuming this does
not happen, either all other pairs are $[1,2]$-flats (in which case
$|S|=2^{n}-1$), or all other flats are $[1,0]$-flats (in which case $|S|=1$),
giving a contradiction in both cases. ∎

The determination of the spectrum $Sp(n;2,4)$ (and its complement $Sp(n;2,0)$)
is still a challenging problem. This problem has been studied under the name
of Sidon sets in binary vector spaces. A subset $S$ of an abelian group $A$ is
a Sidon set if the only solutions to the equation $a+b=c+d$ with $a,b,c,d\in
A$ are the trivial solutions when $(a,b)$ is a permutation of $(c,d)$. Observe
that for $A=\mathbb{F}_{2}^{n}$, $S$ contains a $[2,4]$-flat if and only if it
is not a Sidon set. There are known results on Sidon sets in this setting due
to Bose, Ray-Chaudhuri, by Tait, Won and by Lindström, which imply the
following.

######  Proposition 2.8.

  1. (i)

([5], also see [20, 27]) There exists a constant $C>0$ such that
$[n,m]\to[2,4]$ for every $m\geq C\cdot 2^{n/2}$.

  2. (ii)

([5]) For even $n$, the explicit construction
$\\{(x,x^{3}):x\in\mathbb{F}_{2^{n/2}}\\}$ shows that
$[n,2^{n/2}]\not\to[2,4]$.

The complete characterization of the spectrum for the case $k=3$, $t=4$
requires a combination of various tools, including probabilistic methods.

######  Proposition 2.9.

$Sp(n;3,4)=[4,2^{n}-4]$.

###### Proof.

It is clear that a $[3,4]$-flat requires at least 4 points in $S$ and at least
4 not in $S$, so $Sp(n;3,4)\subseteq[4,2^{n}-4]$.

Firstly we show that in the case $4\leq|S|\leq 2^{n-2}-1$, $S$ induces a
$[3,4]$-flat. Assume on the contrary that it does not. Consider the parallel
classes of $2$-flats. In any given parallel class, there must be at least one
$[2,0]$-flat (otherwise $S$ would have at least $2^{n-2}$ points). If the same
class also contains a $[2,4]$-flat, then together with the $[2,0]$-flat they
would form a $[3,4]$-flat, which is a contradiction. So $S$ cannot induce any
$[2,4]$-flats at all. Take a line $\ell=\\{a,b\\}$ joining any two points of
$S$. The $2$-flats through $\ell$ cover each point outside $\ell$ exactly
once, and there cannot be a $[2,4]$-flat among them, so there must be at least
one $[2,3]$-flat (since $|S|\geq 3$). Take any $[2,3]$-flat $H$, and consider
the parallel class of $H$. If it contains any $[2,1]$-flat, then together with
$H$ it would form a $[3,4]$-flat, which is a contradiction. So the class can
only contain flats of type $[2,0]$, $[2,2]$ and $[2,3]$. There can be at most
one $[2,2]$-flat, as two $[2,2]$-flats again form a $[3,4]$-flat. Now suppose
$H^{\prime}$ is another $[2,3]$-flat in this class. Let
$H=\\{x,~{}x+a,~{}x+b,~{}x+a+b\\}$ with $x,~{}x+a,~{}x+b\in S$ and
$x+a+b\not\in S$. Then $H^{\prime}$ can be written as
$\\{y,~{}y+a,~{}y+b,~{}y+a+b\\}$. If $y,~{}y+a\in S$ then
$\\{x,~{}x+a,~{}y,~{}y+a\\}$ is a $[2,4]$-flat, which is a contradiction.
Similarly if $y,~{}y+b\in S$ we get a contradiction, and also if
$y+a,~{}y+b\in S$ then we would have the $[2,4]$-flat
$\\{x+a,~{}x+b,~{}y+a,~{}y+b\\}$. So all in all, out of the points
$y,~{}y+a,~{}y+b$ at most one can be in $S$, so $H^{\prime}$ contains at most
2 points of $S$ and not $3$, which is a contradiction. So the class cannot
contain a $[2,3]$-flat different than $H$. Summing up all points in the
parallel class, we get that $|S|\leq 5$.

Any set of $4$ points is contained in a $3$-dimensional affine subspace,
resolving the case $|S|=4$. Finally if $|S|=5$, then in the parallel class of
$H$, there must be a $[2,2]$-flat $H^{\prime}$. Letting
$H=\\{x,~{}x+a,~{}x+b,~{}x+a+b\\}$ with $x,~{}x+a,~{}x+b\in S$ and
$x+a+b\not\in S$, and $H^{\prime}=\\{y,~{}y+a,~{}y+b,~{}y+a+b\\}$, one can
easily see that no matter which two points of $H^{\prime}$ are contained in
$S$, $H\cup H^{\prime}$ will always contain a $[2,4]$-flat induced by $S$,
which is a contradiction.

This concludes the proof that any $S$ with $4\leq|S|\leq 2^{n-2}-1$ induces a
$[3,4]$-flat.

Now suppose that $4\leq|S|\leq 2^{n}-4$, and let us show that $S$ induces a
$[3,4]$-flat. We use induction on $n$. For $n=3$, $|S|=4$ so the whole space
is a $[3,4]$-flat, while we have verified the case $n=4$ via exhaustive
search. From now on we assume that $n\geq 5$. The case $4\leq|S|\leq
2^{n-2}-1$ is already covered, and by Lemma 2.6, we are also done in the case
$3\cdot 2^{n-2}+1\leq|S|\leq 2^{n}-4$. Thus the remaining case is when
$2^{n-2}\leq|S|\leq 3\cdot 2^{n-2}$ holds. By complementing, we can actually
assume that $2^{n-2}\leq|S|\leq 2^{n-1}$. We apply lemma 2.2 of Charbit et al.
[7] on $S$, where either $H$ or $\overline{H}$ will be an $n-1$-flat $A$ with
$|S\cap A|\in\left[\frac{1}{2}m,\frac{1}{2}m+\frac{1}{2}\sqrt{m}\right]$.
Since $m\in[2^{n-2},2^{n-1}]$, this means that $|S\cap
A|\in\left[2^{n-3},2^{n-2}+2^{\frac{1}{2}n-\frac{3}{2}}\right]$. Here $n\geq
3$ implies that $\frac{1}{2}n-\frac{3}{2}\leq n-3$, so $|S\cap
A|\in[2^{n-3},3\cdot 2^{n-3}]$. Since $n\geq 5$, we have $2^{n-3}\geq 4$ and
$3\cdot 2^{n-3}\leq 2^{n-1}-4$, so $|S\cap A|\in[4,2^{n-1}-4]$. By the
induction hypothesis, the statement is true in the $n-1$-dimensional flat $A$,
so $S$ induces a $[3,4]$-flat in $A$. ∎

######  Remark 2.10.

We have seen that $Sp(n;k,2^{k-1})=[2^{k-1},2^{n}-2^{k-1}]$ holds for
$k=1,2,3$. However this does not hold for larger $k$. In fact, for $k\geq 4$
there does not exist a constant $C$ independent of $n$ such that
$[n,C]\to[k,2^{k-1}]$ holds for all $n\geq k$, since for $n\geq\max(C-1,k+1)$
we can pick a subset $S$ of size $C$ in general position, and then $k$-flats
only contain at most $k+1$ points of $S$ while $k+1<2^{k-1}$ for $k\geq 4$. As
we will point out in Theorem 3.1 in the next section, even the
$(k,k+1)$-evasive sets can be exponentially large in $n$.

##  3 Avoidable sizes with $k$-dimensional subspaces

In this section we show two types of constructions which have (several)
missing values in their $k$-dimensional profile. These in turn provide a
relatively large set of missing values from the $(n;k,t)$-spectrum. Moreover
we point out that these constructions can be combined via disjoint union and
difference, leading to even more missing values.

The first type corresponds to evasive sets, which were mentioned in the
introduction. Here we refine the probabilistic bounds of Guruswami. Then we
continue by constructing $m$-sets which have a profile of relatively small
size provided that $m$ has small support in its binary or in its canonical
signed-digit binary representation.

###  3.1 Evasive sets

As we mentioned in the introduction, the existence of $(k,c)$-evasive sets in
turn provides sets which avoid every intersection size greater than $c$. The
random construction of Guruswami showed that we can obtain a $(k,c)$-evasive
set on at least $2^{n(1-\frac{2k}{c})}/2^{k+1}$ points. Below we refine his
argument using alteration.

######  Theorem 3.1.

Let $k,c\in\mathbb{Z}^{+}$ with $c\geq k+1$. Then for $n>k$, there exists a
$(k,c)$-evasive set in $\mathbb{F}_{2}^{n}$ of size at least

$\lfloor K\cdot 2^{n\left(1-\frac{k}{c}\right)}\rfloor-1$

where $K=K(k,c):=\frac{c}{c+1}\cdot
2^{k(k+1)/c}\cdot\left(2e^{2/3}(c+1)\binom{2^{k}}{c+1}\right)^{-\frac{1}{c}}$.

###### Proof.

To construct a $(k,c)$-evasive set, we apply the following procedure. First we
suitably choose a value $m\in[c,2^{n}]$. Then we take a random point set of
size $m$ in $\mathbb{F}_{2}^{n}$, and if we find a set of $c+1$ points within
a $k$-flat, we erase one of those points.
Then the expected value of the number of erased points can be bounded from
above by

$2^{n-k}\begin{bmatrix}n\\\
k\end{bmatrix}_{2}\binom{2^{k}}{c+1}\frac{\binom{{2^{n}}-c-1}{m-c-1}}{\binom{2^{n}}{m}}<2^{(n-k)(k+1)+1}e^{2/3}\binom{2^{k}}{c+1}\left(\frac{m}{2^{n}}\right)^{c+1},$

taking into consideration that the number of $k$-flats is
$2^{n-k}\begin{bmatrix}n\\\ k\end{bmatrix}_{2}$ in view of Corollary 2.4 and
Lemma 2.5. The remaining points form a $(k,c)$-evasive set of size at least

$m-2^{(n-k)(k+1)+1}e^{2/3}\binom{2^{k}}{c+1}\left(\frac{m}{2^{n}}\right)^{c+1}$

which we want to maximize in $m$. Note that this is a concave function of $m$,
maximized when its derivative is $0$. This happens when
$C(n,k,c)(c+1)m^{c}=1$, where

$C(n,k,c):=2^{(n-k)(k+1)+1}e^{2/3}\binom{2^{k}}{c+1}\left(\frac{1}{2^{n}}\right)^{c+1}.$

Hence the maximum of this function over $\mathbb{R}$ is attained at

$m=2^{n\left(1-\frac{k}{c}\right)}\cdot
2^{k(k+1)/c}\cdot\left(2e^{2/3}(c+1)\binom{2^{k}}{c+1}\right)^{-\frac{1}{c}},$

while the maximum itself is $\frac{c}{c+1}m$. As $m$ must be an integer, we
get that the expected value is at least $\frac{c}{c+1}m-1$ for

$m=\left\lfloor 2^{n\left(1-\frac{k}{c}\right)}\cdot
2^{k(k+1)/c}\cdot\left(2e^{2/3}(c+1)\binom{2^{k}}{c+1}\right)^{-\frac{1}{c}}\right\rfloor$

Note that the main term is $2^{n\left(1-\frac{k}{c}\right)}$ while its
multiplicative factor is independent of $n$, moreover using Stirling’s
approximation on the constant, we can obtain that the number of remaining
points is at least

$2^{(n-k)(1-\frac{k}{c})}\cdot\frac{c^{2}}{2e(c+1)}-1$

for $c\geq k+1\geq 2.$ This result refines the Theorem 1.1 of Guruswami. ∎

######  Remark 3.2.

Note that in the case $c\leq k$, any set of $c+1$ points is contained in a
$c$-flat thus a $(k,c)$-evasive set can not contain more than $c$ points.
However, for $c>k$ we already have an exponential lower bound on the size of
$(k,c)$-evasive sets in $\mathbb{F}_{q}^{n}$.

If $q>2$, the same proof confirms the following generalization. The only
difference is that we have a different constant for the bound on
$\begin{bmatrix}n\\\ k\end{bmatrix}_{q}$ compared to $\begin{bmatrix}n\\\
k\end{bmatrix}_{2}$ in Lemma 2.5.

######  Theorem 3.3 (General improved lower bound on evasive sets).

Let $k,c\in\mathbb{Z}^{+}$ with $c\geq k+1$ and $q>2$. Then for $n>k$, there
exists a $(k,c)$-evasive set in $\mathbb{F}_{q}^{n}$ of size at least

$\lfloor K\cdot q^{n\left(1-\frac{k}{c}\right)}\rfloor-1,$

where $K=K(k,c):=\frac{c}{c+1}\cdot
2^{k(k+1)/c}\cdot\left(2e^{1/(q-2)}(c+1)\binom{q^{k}}{c+1}\right)^{-\frac{1}{c}}$.

###  3.2 Sets related to binary and canonical signed-digit representations

To prove Theorem 1.5, we will use the following construction.

######  Definition 3.4.

Let $m\in[0,2^{n}]$ be an integer. The lexicographic construction of $m$
points is defined as follows. Take every point
$P=(x_{n-1},x_{n-2},\ldots,x_{0})$ in $\mathbb{F}_{2}^{n}$ for which the
$n$-digit binary representation $\overline{x_{n-1}x_{n-2}\ldots x_{0}}$
represents a number smaller than $m$.
The lexicographic construction of $m$ points will be denoted by
$\mathcal{L}_{m}$. The binary support $\mathrm{Supp}(m)$ of $m$ is the set of
values $d\geq 0$ such that the binary form of $m$ contains a digit 1 at the
place $2^{d}$.
Finally, let $s_{2}(m):=|\mathrm{Supp}(m)|$, i.e., the sum of the digits in
the binary representation of $m$.

The following lemma is a straightforward consequence of the summation
procedure, taking into account the decrease of the digit sum at each carry.

######  Lemma 3.5.

For any natural numbers $a_{1}$, $a_{2}$, …, $a_{\ell}$ we have
$s_{2}\left(\sum_{i=1}^{\ell}a_{i}\right)\leq\sum_{i=1}^{\ell}s_{2}(a_{i})$.

######  Proposition 3.6.

If $s_{2}(t)>s_{2}(m)$ then $[n,m]\not\to[k,t]$, and in particular,
$\mathcal{L}_{m}\subseteq\mathbb{F}_{2}^{n}$ does not induce a $[k,t]$-flat.
Moreover, if $H$ is a $k$-flat in $\mathbb{F}_{2}^{n}$, then the size of
$H\cap\mathcal{L}_{m}$ can admit at most

$1+\sum_{j=0}^{s_{2}(m)}\binom{k}{j}$

values.

###### Proof.

Let $M=s_{2}(m)$, and let $m=\sum_{i=1}^{M}2^{d_{i}}$, thus
$\mathrm{Supp}(m)=\\{d_{1}<d_{2}<\ldots<d_{M}\\}$. Then $\mathcal{L}_{m}$
naturally decomposes into $M$ flats $H_{1},H_{2},\ldots,H_{M}$ of dimension
$d_{1},\ldots,d_{M}$, respectively, where the flat $H_{j}$ of dimension
$d_{j}$ is given by the equations

$x_{k}=\begin{cases}1&\text{for }k>d_{j},k\in\mathrm{Supp}(m)\\\ 0&\text{for
}k>d_{j},k\not\in\mathrm{Supp}(m)\\\ 0&\text{for }k=d_{j}.\end{cases}$

Denote $\dim(H\cap H_{i})$ by $r_{i}$. The size of $H\cap\mathcal{L}_{m}$ can
be expressed as

$\sum_{i:H_{i}\cap H\neq\emptyset}2^{r_{i}}.$

Since the sets $H\cap H_{i}$ are disjoint subsets of $H$ and of
$\mathcal{L}_{m}$, we conclude the sum above is at most $\min\\{2^{k},m\\}$.
Moreover, if the sum is smaller than $2^{k}$, then the binary representation
of the sum consists of at most $k$ digits, of which at most $M$ is one, in
view of Lemma 3.5. This in turn completes the proof. ∎

Theorem 1.5 follows immediately from Proposition 3.6.

Not only the binary digit sum can impose conditions on the spectrum: the
lexicographic construction shows further values of $m$ for which $[k,t]$-flats
are avoidable. Suppose that $m$ is a difference of two powers of $2$. While
$s_{2}(m)$ might be large, the lexicographic construction of $m$ points shows
that $[k,t]$ is avoidable if $t$ cannot be written as a power of $2$ or a
difference of two powers of $2$. It is easy to deduce a statement similar to
Proposition 3.6, after recalling the definition and the properties of the
canonical signed-digit binary representation.

Let $s^{*}_{2}(m)$ denote the number of nonzero values in the non-adjacent
form or canonical signed-digit (CSD) binary representation of $m$. This number
system is a signed-digit number system using three digits, $0,1,\overline{1}$,
which minimizes the number of non-zero digits. $\overline{1}$ corresponds to
$-1$. Its main advantage compared to the binary form is that CSD reduces the
number of operations in a hardware multiplier. A detailed discussion of CSD
can be found in [23]. We apply the following facts concerning this numerical
system.

######  Proposition 3.7.

  * •

The CSD representation of any integer number can be gained easily from the
binary form by iterating the following step: starting from the right, going
left, each sequence of length at least $3$ consisting of a single $0$ in the
first position of the sequence and continued solely by $1$s are replaced by a
sequence of the same length, starting with 1, ending with $\overline{1}$ and
containing only $0$ in between.

  * •

The CSD representation of any integer number is unique.

  * •

There are no two consecutive non-zero digits in the CSD representation of any
integer number. Moreover, finite sequences built up by starting with a digit
$1$ or $\overline{1}$ and continuing with zero or more blocks of the form $0$,
$01$, or $0\overline{1}$ correspond uniquely to the nonzero integers via the
CSD representation.

  * •

For every integer $n$, the CSD representation contains the least number of
nonzero digits compared to any signed-digit binary representation of $n$.

We have an analogue of Lemma 3.5 for the CSD binary representation, which
follows easily from the last property of CSD representation, formulated above.

######  Lemma 3.8.

For any integer numbers $a_{1}$, $a_{2}$, …, $a_{\ell}$ we have
$s_{2}^{*}\left(\sum_{i=1}^{\ell}a_{i}\right)\leq\sum_{i=1}^{\ell}s_{2}^{*}(a_{i})$.

The CSD representation offers a convenient tool to exclude further values from
the spectra $Sp(n;k,t).$

######  Proposition 3.9.

If $s^{*}_{2}(t)>s^{*}_{2}(m)$ then $[n,m]\not\to[k,t]$.

###### Proof.

The proof follows that of Proposition 3.6. Consider again the set
$\mathcal{L}_{m}\subseteq\mathbb{F}_{2}^{n}$. The CSD representation of $m$
corresponding to the form $m=\sum_{i=1}^{M}(-1)^{\alpha_{i}}2^{d_{i}}$ induces
$M$ flats $H_{1},H_{2},\ldots,H_{M}$ of dimension $d_{1},d_{2},\ldots d_{M}$,
respectively, with which the point set of $\mathcal{L}_{m}$ can be composed
via adding the point set of the flats which were assigned a positive sign and
taking away the point set of the flats which were assigned a negative sign.

Denote $\dim(H\cap H_{i})$ by $r_{i}$. The size of $H\cap\mathcal{L}_{m}$ can
be expressed then as

$\sum_{i:H_{i}\cap H\neq\emptyset}(-1)^{\alpha_{i}}2^{r_{i}}.$

By Lemma 3.8, we get that the number of nonzero digits of
$|H\cap\mathcal{L}_{m}|$ is smaller than or equal to that of the CSD
representation of $m$. ∎

######  Proposition 3.10.

$Sp(n;k,t)$ will not contain those values $m>0$ which have fewer nonzero
digits than the number of nonzero digits of $t$ in their respective CSD
representation, hence at least

$n+2+\frac{1}{2}\cdot\sum_{i=2}^{s_{2}^{*}(t)-1}\left[\binom{n+1-i}{i}2^{i}+\binom{n+1-i}{i-1}2^{i-1}\right]$

values are missing from the $(n;k,t)$-spectrum provided that $0<t<2^{k}$.

###### Proof.

We have to count those canonical signed-digit representations
$\overline{x_{n}x_{n-1}...x_{0}}$ of value in $[1,2^{n}]$ which have
$i\in[1,s_{2}^{*}(t)-1]$ nonzero digits. If $i=1$ then there are $n+1$ such
representations. If $i\geq 2$ then consider two cases. If $x_{n}=0$ then
$\overline{x_{n}...x_{0}}$ is a sequence of $i$ blocks $01$ or $0\overline{1}$
and $n+1-2i$ blocks $0$ in some order, but the first two-digit block must be
$01$ (so that the number is positive), so there are
$\frac{1}{2}\cdot\binom{n+1-i}{i}2^{i}$ such representations. If $x_{n}=1$
then $\overline{x_{n-1}...x_{0}}$ is a sequence of $i-1$ blocks $01$ or
$0\overline{1}$ and $n+2-2i$ blocks $0$ in some order, but the first two-digit
block must be $0\overline{1}$ (so that the number is less than $2^{n}$), so
there are $\frac{1}{2}\cdot\binom{n+1-i}{i-1}2^{i-1}$ such representations. ∎

###  3.3 Combination

The propositions above can be combined with the former results on
$(k,c)$-evasive sets. Indeed, consider a lexicographic construction
$\mathcal{L}_{m}$ which avoids $[k,t]$-flats for all $t\in[t_{1},t_{2}]$. Take
a $(k,c)$-subspace evasive set $S$ disjoint from $\mathcal{L}_{m}$. Then
$\mathcal{L}_{m}\cup S$ provides a set of size $m+|S|$ which avoids
$[k,t]$-flats for all $t\in[t_{1}+c,t_{2}]$.

Applying our improvement Theorem 3.1 on $(k,c)$-evasive sets, we obtain the
following result.

######  Theorem 3.11.

Let $k$ and $t$ be fixed integers such that $1\leq t\leq 2^{k}-1$ and suppose
that either $s_{2}(t)-~{}s_{2}(m)>\lfloor\log_{2}c\rfloor+1$ or
$s_{2}^{*}(t)-~{}s_{2}^{*}(m)>\left\lceil\frac{1}{2}\left(\log_{2}c+1\right)\right\rceil$
holds for a pair of positive integers $m,c$. Then $[n,m^{\prime}]\not\to[k,t]$
holds for every integer
$m^{\prime}\in\left[m,m+\left(K\cdot\frac{2^{n}-m}{2^{n}}\cdot
2^{n\left(1-\frac{k}{c}\right)}\right)\right]$, where $K$ is a positive
constant depending only on $k$ and $c$.

###### Proof.

We prove the statement for the digit sum $s_{2}$. The proof for $s_{2}^{*}$ is
identical.
Consider the lexicographic construction $\mathcal{L}_{m}$ on $m$ points, and a
$(k,c)$-evasive set $S$ in $\mathbb{F}_{2}^{n}$ disjoint from
$\mathcal{L}_{m}$.

Lemma 2.1 implies that if the union of $\mathcal{L}_{m}$ and $S$ induces a
$[k,t]$-flat, that is, $t\in\mathrm{pf}_{k}(\mathcal{L}_{m}\cup S)$, then
$t\in\mathrm{pf}_{k}(\mathcal{L}_{m})+\mathrm{pf}_{k}(S)$ holds as well.
$s_{2}(z)\leq s_{2}(m)$ holds for every
$z\in\mathrm{pf}_{k}(\mathcal{L}_{m})$. On the other hand, every $k$-flat
intersects $S$ in at most $c$ points, thus $\mathrm{pf}_{k}(S)\subseteq[0,c]$.
Consequently, $s_{2}(t)\leq s_{2}(m)+\lfloor\log_{2}c\rfloor+1$ for every
$t\in\mathrm{pf}_{k}(\mathcal{L}_{m}\cup S)$ in view of the subadditive
property of the digit sum function $s_{2}$, Lemma 3.5. We thus get that if
$s_{2}(t)>s_{2}(m)+\lfloor\log_{2}c\rfloor+1$, then we can add a
$(k,c)$-evasive set to $\mathcal{L}_{m}$ to gain a set which does not induce a
$[k,t]$-flat. If $s_{2}(t)-s_{2}(m)>\lfloor\log_{2}(k+1)\rfloor+1$, the size
of this subspace evasive set can be exponentially large in $n$, according to
Theorem 3.1. Indeed, we can find a set of size $K\cdot
2^{n\left(1-\frac{k}{c}\right)}$, and we can keep at least a fraction
$\frac{2^{n}-m}{2^{n}}$ of it to obtain a disjoint set from $\mathcal{L}_{m}$.
This follows from the fact that we might consider any translate
$w+\mathcal{L}_{m}$ of the lexicographic construction for
$w\in\mathbb{F}_{2}^{n}$, and on average these contain a fraction
$\frac{m}{2^{n}}$ of the evasive set.
All in all, we get a set which avoids $[k,t]$-flats of size $m+s$ for each
integer $0\leq s\leq\frac{2^{n}-m}{2^{n}}\cdot\left(\left\lfloor K(k,c)\cdot
2^{n\left(1-\frac{k}{c}\right)}\right\rfloor-1\right)$, where
$K(k,c)=\frac{c}{c+1}\cdot
2^{k(k+1)/c}\cdot\left(2e^{2/3}(c+1)\binom{2^{k}}{c+1}\right)^{-\frac{1}{c}}$.
∎

We showed that if $s_{2}(m)$ is small compared to $s_{2}(t)$, then the
integers in a certain right neighbourhood of $m$ will also not be in the
spectrum $Sp(n;k,t)$.

A similar construction can be obtained by erasing a $(k,c)$-evasive set $S$
from a lexicographic construction $\mathcal{L}_{m}$ which avoids $[k,t]$-flats
for all $t\in[t_{1},t_{2}]$. Then $\mathcal{L}_{m}\setminus S$ provides a set
of size $m-|S|$ which avoids $[k,t]$-flats for all $t\in[t_{1},t_{2}-c]$.

######  Theorem 3.12.

Let $k$ and $t$ be fixed integers such that $1\leq t\leq 2^{k}-1$ and suppose
that
$s_{2}^{*}(t)-~{}s_{2}^{*}(m)>\left\lceil\frac{1}{2}\left(\log_{2}c+1\right)\right\rceil$
holds for a pair of positive integers $m,c$. Then $[n,m^{\prime}]\not\to[k,t]$
holds for every integer $m^{\prime}\in\left[m-\left(K\cdot\frac{m}{2^{n}}\cdot
2^{n\left(1-\frac{k}{c}\right)}\right),m\right]$, where $K$ is a positive
constant depending only on $k$ and $c$.

###### Proof.

Consider the lexicographic construction $\mathcal{L}_{m}$, and a
$(k,c)$-evasive set $S$ in $\mathbb{F}_{2}^{n}$ which is a subset of
$\mathcal{L}_{m}$.

By Lemma 2.1, if $t\in\mathrm{pf}_{k}(\mathcal{L}_{m}\setminus S)$, then
$t\in\mathrm{pf}_{k}(\mathcal{L}_{m})-\mathrm{pf}_{k}(S)$ too.
$s_{2}^{*}(z)\leq s_{2}^{*}(m)$ holds for every
$z\in\mathrm{pf}_{k}(\mathcal{L}_{m})$. On the other hand, every $k$-flat
intersects $S$ in at most $c$ points, thus $\mathrm{pf}_{k}(S)\in[0,c]$.
Consequently, $s^{*}_{2}(t)\leq
s^{*}_{2}(m)+\left\lceil\frac{1}{2}\left(\log_{2}c+1\right)\right\rceil$ for
every $t\in\mathrm{pf}_{k}(\mathcal{L}_{m}\setminus S)$ in view of subadditive
property of the function $s_{2}^{*}$, lemma 3.8. We thus get that if
$s_{2}^{*}(t)>s_{2}^{*}(m)+\left\lceil\frac{1}{2}\left(\log_{2}c+1\right)\right\rceil$,
then we can delete a $(k,c)$-evasive set from $\mathcal{L}_{m}$ to gain a set
which does not induce a $[k,t]$-flat. By Theorem 3.1, we can find a
$(k,c)$-evasive set of size $K\cdot 2^{n\left(1-\frac{k}{c}\right)}$, and we
can keep at least a fraction $\frac{m}{2^{n}}$ of it to obtain a subset of
$\mathcal{L}_{m}$, similarly to the proof of Theorem 3.11.
So the resulting set avoids $[k,t]$-flats of size $m-s$ for each $0\leq
s\leq\frac{m}{2^{n}}\cdot\left(\left\lfloor K(k,c)\cdot
2^{n\left(1-\frac{k}{c}\right)}\right\rfloor-1\right)$. ∎

The two theorems above imply Theorem 1.7.

##  4 Avoiding intersection sizes equal to a power of $2$

In the previous section, we proved that $[k,t]$-flats are easier to avoid if
the binary representation of $t$ contains many digits equal to $1$. Here we
discuss the case when $s_{2}(t)$ is $1$ or $2$. The cornerstone will be a
simple theorem which states that if a subset of $\mathbb{F}_{2}^{n}$ contains
a large proportion of the vectors of the space then it must contain a large
affine subspace as well.

###  4.1 Finding $[k,2^{k}]$-flats

We will first consider the case of $t=2^{k}$, which means that we want to find
a full affine subspace of dimension $k$ in $S$. Recall that in Section 2, we
have discussed the cases $k=1$ and $k=2$, with the case $k=2$ corresponding to
Sidon sets. The following theorem extends the result of Bose and Ray-
Chaudhuri, presented in Proposition 2.8(i).

######  Theorem 4.1.

Given integers $n\geq k\geq 1$, and any $m\geq\frac{5}{2}\cdot
2^{n\left(1-\frac{1}{2^{k-1}}\right)}$, we have $[n,m]\to[k,2^{k}]$.

A variant of this claim appeared in a different (weaker) form in the work of
Sanders [24]. The result points out that for a fixed integer $k$, sets with
given positive density will always contain a $k$-flat if $n$ is large enough.
We mention that the result and its proof is closely related to Szemerédi’s
Cube Lemma, see [26, Corollary 2.1].

######  Lemma 4.2.

Suppose that $|S|\geq D\cdot 2^{\alpha n}+1$ for a set
$S\subseteq\mathbb{F}_{2}^{n}$, where $\frac{1}{2}\leq\alpha<1$ and $D>0$ are
real numbers. Then there exists a nonzero vector $d\in\mathbb{F}_{2}^{n}$ such
that the number of unordered pairs of vectors in $S$ with difference $d$ is at
least $\frac{D^{2}}{2}\cdot 2^{(2\alpha-1)n}$.

###### Proof.

Taking the elements of $S$ pairwise, they form $\binom{|S|}{2}$ differences
with multiplicity. The number of possible differences is $2^{n}-1$, so there
must exist a difference appearing at least

$\frac{\binom{|S|}{2}}{2^{n}-1}>\frac{\binom{|S|}{2}}{2^{n}}\geq\frac{D^{2}\cdot
2^{2\alpha n}}{2^{n+1}}=\frac{D^{2}}{2}\cdot 2^{(2\alpha-1)n}$

times. ∎

###### Proof of Theorem 4.1.

We prove that there exist constants $0<C_{k}\leq\frac{5}{2}$ for each $k\geq
1$ such that if $|S|\subseteq\mathbb{F}_{2}^{n}$ has $|S|\geq C_{k}\cdot
2^{n\left(1-\frac{1}{2^{k-1}}\right)}$ then $S$ contains a $k$-flat. For
$k=1$, the result holds with $C_{1}=2$, as any two points form a $1$-flat.

Now suppose that $k\geq 2$. If we know that $|S|\geq D_{k}\cdot
2^{n\left(1-\frac{1}{2^{k-1}}\right)}+1$ for a certain constant $D_{k}>0$,
then we can apply Lemma 4.2 to get a difference $d_{1}$ which appears at least
$\frac{D_{k}^{2}}{2}\cdot 2^{n\left(1-\frac{1}{2^{k-2}}\right)}$ times. We
factorize the space by this vector and define a set
$S_{1}\subseteq\mathbb{F}_{2}^{n}/\langle d_{1}\rangle$ which consists of the
$\langle d_{1}\rangle$-cosets with both elements lying in $S$. Then
$|S_{1}|\geq\frac{D_{k}^{2}}{2}\cdot 2^{n\left(1-\frac{1}{2^{k-2}}\right)}$.

Observe that if we find a $[k-1,2^{k-1}]$-flat induced by $S_{1}$, then it can
be lifted to a $[k,2^{k}]$-flat induced by $S$. So to find such a $(k-1)$-flat
and finish the proof, it suffices to refer to the induction hypothesis for the
subset $S_{1}$ of the $(n-1)$-dimensional space $\mathbb{F}_{2}^{n}/\langle
d_{1}\rangle$. For this, it suffices to have $\frac{D_{k}^{2}}{2}\cdot
2^{n\left(1-\frac{1}{2^{k-2}}\right)}\geq C_{k-1}\cdot
2^{(n-1)\left(1-\frac{1}{2^{k-2}}\right)}$.

This is equivalent to $D_{k}\geq\sqrt{C_{k-1}}\cdot 2^{\frac{1}{2^{k-1}}}$, so
we need a value $C_{k}$ such that $C_{k}\cdot
2^{n\left(1-\frac{1}{2^{k-1}}\right)}\geq\sqrt{C_{k-1}}\cdot
2^{\frac{1}{2^{k-1}}}\cdot 2^{n\left(1-\frac{1}{2^{k-1}}\right)}+1$ holds for
all $n\geq k$. The choice $C_{k}=\sqrt{C_{k-1}}\cdot
2^{\frac{1}{2^{k-1}}}+\frac{1}{2^{k\left(1-\frac{1}{2^{k-1}}\right)}}$ works.

From $C_{1}=2$ this gives $C_{2}=\frac{5}{2}$, and for $k\geq 3$, if we
already know that $C_{k-1}\leq\frac{5}{2}$ then we will get
$C_{k}\leq\sqrt{\frac{5}{2}}\cdot
2^{1/4}+\frac{1}{2^{3\left(1-\frac{1}{2^{2}}\right)}}\approx
2.09<\frac{5}{2}$. ∎

######  Remark 4.3.

In fact, in the argument above the recursive formula gives $C_{k}\to 1$ as
$k\to\infty$. From this argument one can also deduce that for each fixed
$k\geq 1$ and $\delta>0$, $|S|\geq(2+\delta)\cdot
2^{n\left(1-\frac{1}{2^{k-1}}\right)}$ already implies the existence of a
$[k,2^{k}]$-flat for sufficiently large $n$.

###  4.2 Finding $[k,2^{k-\ell}]$-flats for almost all values $|S|$ when $S$
has a low positive density

In the following, we will show that $k$-flats of density exactly
$\frac{1}{2^{\ell}}$ can be found for a long interval of values $m$ which
contains a positive fraction of all values as $n\to\infty$, where this
fraction is $1$ for $\ell=1$.

The proof relies on bounds for flats of smaller dimension, containing a given
number of points.

######  Notation 4.4.

Suppose that a set $S\subseteq\mathbb{F}_{2}^{n}$ is given. If
$\\{v_{1},v_{2},...,v_{d}\\}$ is a set of linearly independent vectors in
$\mathbb{F}_{2}^{n}$, and $0\leq t\leq 2^{d}$ is an integer, let
$F_{d,t}(S;v_{1},v_{2},...,v_{d})$ denote the number of $\langle
v_{1},v_{2},...,v_{d}\rangle$-cosets in $\mathbb{F}_{2}^{n}$ containing
exactly $t$ elements of $S$.
The number of all $[d,t]$-flats induced by $S$ will be denoted by
$F_{d,t}(S)$.
From now on, we apply the simpler notation $F_{d,t}(v_{1},v_{2},...,v_{d})$
and $F_{d,t}$, respectively, if the set $S$ is clear from the context.

We recall the statement of Theorem 1.9.

Theorem 1.9. Let $k\geq 2$. Then there exists an absolute constant $C>0$ such
that $[n,m]~{}\rightarrow~{}\left[k,2^{k-1}\right]$ for $m\in\left[C\cdot
2^{n\left(1-\frac{1}{2^{k-2}}\right)},2^{n}-C\cdot
2^{n\left(1-\frac{1}{2^{k-2}}\right)}\right]$.

###### Proof.

Note that we can assume $n$ to be sufficiently large when needed (by a
suitable choice of $C$).

Let $|S|=m$. The number of ordered pairs $(s,s^{*})$ such that $s\in S$ and
$s^{*}\in\overline{S}$ is $m(2^{n}-m)$. For such pairs, the difference
$s-s^{*}$ can take on at most $2^{n}-1$ possible values, and so there exists a
difference $d$ that appears in at least
$\frac{m(2^{n}-m)}{2^{n}-1}\geq\frac{m(2^{n}-m)}{2^{n}}$ ways as $s-s^{*}$.
Let $d$ be such a difference, and consider the set
$S_{1}\subseteq\mathbb{F}_{2}^{n}/\langle d\rangle$ consisting of those
$\langle d\rangle$-cosets that contain exactly one element of $S$. Then we
have $|S_{1}|\geq\frac{m(2^{n}-m)}{2^{n}}$.

If we can find a $(k-1)$-dimensional affine subspace of
$\mathbb{F}_{2}^{n}/\langle d\rangle$ that consists only of elements in
$S_{1}$, then the lifting of this subspace to $\mathbb{F}_{2}^{n}$ gives rise
to a $[k,2^{k-1}]$-flat induced by $S$, which is what we need.

By Theorem 4.1, we have $[N,M]\to[K,2^{K}]$ for all integers $N\geq K\geq 1$
and $M\geq\frac{5}{2}\cdot 2^{N\left(1-\frac{1}{2^{K-1}}\right)}$.

Using this fact for $N=n-1$ and $K=k-1$, what remains to prove is that
$|S_{1}|\geq\frac{5}{2}\cdot 2^{(n-1)\left(1-\frac{1}{2^{k-2}}\right)}$.

Letting $d=\left|m-\frac{1}{2}\cdot 2^{n}\right|$, we have
$m(2^{n}-m)=\left(\frac{1}{2}\cdot 2^{n}-d\right)\left(\frac{1}{2}\cdot
2^{n}+d\right)=\frac{1}{4}\cdot 2^{2n}-d^{2}$. So it suffices to show that

$\frac{\frac{1}{4}\cdot 2^{2n}-d^{2}}{2^{n}}\geq\frac{5}{2}\cdot
2^{(n-1)\left(1-\frac{1}{2^{k-2}}\right)}$

$\Leftrightarrow d^{2}\leq\frac{1}{4}\cdot 2^{2n}-D\cdot
2^{n\left(2-\frac{1}{2^{k-2}}\right)}$

for a positive constant $D$ depending on $k$ only.

As we have $d\leq\frac{1}{2}\cdot 2^{n}-C\cdot
2^{n\left(1-\frac{1}{2^{k-2}}\right)}$, this means that
$d^{2}\leq\frac{1}{4}\cdot 2^{2n}-C\cdot
2^{n\left(2-\frac{1}{2^{k-2}}\right)}+C^{2}\cdot
2^{n\left(2-\frac{1}{2^{k-3}}\right)}$. For an appropriate choice of $C$ and
sufficiently large $n$, this expression is less than $\frac{1}{4}\cdot
2^{2n}-D\cdot 2^{n\left(2-\frac{1}{2^{k-2}}\right)}$. ∎

The following theorem is a more specific form of Theorem 1.8:

######  Theorem 4.5.

For every pair $(k,\ell)$ of integers such that $k>\ell\geq 1$, there exist
constants $C>0$ and $0<D<1$ such that if we are given a set
$S\subseteq\mathbb{F}_{2}^{n}$ of size between
$C~{}\cdot~{}2^{n\left(1-\frac{1}{2^{k-\ell-1}}\right)}$ and $D\cdot 2^{n}$,
then this set will contain an induced $\left[k,2^{k-\ell}\right]$-flat.
Moreover for each $\varepsilon>0$, $D$ can take the value
$\frac{1-\varepsilon}{2^{\ell-1}}$ (with appropriate $C$).

###### Proof.

Let us choose directions $v_{1},v_{2},...,v_{\ell}$ iteratively such that each
direction $v_{d}$ forms a linearly independent set together with the previous
ones, and the following condition holds for each $1\leq d\leq\ell$ (where
$m=|S|$):

$F_{d,1}(v_{1},v_{2},...,v_{d})\geq\frac{m(2^{n}-m)(2^{n-1}-m)...(2^{n-d+1}-m)}{2^{n}\cdot
2^{n-1}\cdot...\cdot 2^{n-d+1}}$ (1)

First we choose $v_{1}$. In the proof of Theorem 1.9, we have already seen
that it can be chosen such that $F_{1,1}(v_{1})\geq\frac{m(2^{n}-m)}{2^{n}}$,
satisfying (1) for $d=1$.

Now suppose that $v_{1},...,v_{d}$ have already been chosen satisfying (1),
where $1\leq d\leq\ell-1$. Then letting $L_{d}=\langle
v_{1},...,v_{d}\rangle$, consider the $d$-flats parallel to $L_{d}$. There are
$2^{n-d}$ such $d$-flats, and since $|S|=m$, at most $m$ of those contain some
point of $S$. So the number of $d$-flats parallel to $L_{d}$ having empty
intersection with $S$ is at least $2^{n-d}-m$.

Any pair of flats parallel to $L_{d}$ forms a $(d+1)$-flat, and such a
$(d+1)$-flat has exactly 1 point in $S$ if and only if one of the $d$-flats
contained 1 point of $S$ and the other contained 0. So the number of such
$[d+1,1]$-flats is $F_{d,1}(v_{1},...,v_{d})F_{d,0}(v_{1},...,v_{d})$. There
are $2^{n-d}-1$ possible directions for such a flat (that is, the difference
of the two flats in $\mathbb{F}_{2}^{n}/L_{d}$ can have $2^{n-d}-1$ possible
values), so there is a direction $v_{d+1}+L_{d}$ such that the number of
$[d+1,1]$-flats parallel to $L_{d+1}=\langle v_{1},...,v_{d+1}\rangle$ is at
least

$\frac{F_{d,1}(v_{1},...,v_{d})F_{d,0}(v_{1},...,v_{d})}{2^{n-d}-1}\geq\frac{F_{d,1}(v_{1},...,v_{d})\cdot(2^{n-d}-m)}{2^{n-d}}$

$\geq\frac{m(2^{n}-m)(2^{n-1}-m)...(2^{n-d+1}-m)(2^{n-d}-m)}{2^{n}\cdot
2^{n-1}\cdot...\cdot 2^{n-d+1}\cdot 2^{n-d}},$

where we used $(\ref{eq:*})$ for $d$ for the last inequality. This proved
$(\ref{eq:*})$ for $d+1$.

Now that $v_{1},...,v_{\ell}$ have been chosen, let $L_{\ell}=\langle
v_{1},....,v_{\ell}\rangle$. Let
$S^{\prime}\subseteq\mathbb{F}_{2}^{n}/L_{\ell}$ consist of those
$L_{\ell}$-cosets which contain exactly 1 point of $S$.

Again let us use Theorem 4.1, which stated that $[N,M]\to[K,2^{K}]$ for all
integers $N\geq K\geq 1$ and $M\geq\frac{5}{2}\cdot
2^{N\left(1-\frac{1}{2^{K-1}}\right)}$. Using this for $N=n-\ell$ and
$K=k-\ell$ in relation to $\mathbb{F}_{2}^{n}/L_{\ell}$ and its subset
$S^{\prime}$, we would like to obtain a full $(k-\ell)$-flat consisting only
of points in $S^{\prime}$. By lifting such a flat to $\mathbb{F}_{2}^{n}$, we
get a $k$-flat that has $2^{k-\ell}$ points of $S$, which is just what we
need.

To do this, we need to ensure that $|S^{\prime}|\geq\frac{5}{2}\cdot
2^{(n-\ell)\left(1-\frac{1}{2^{k-\ell-1}}\right)}=A\cdot
2^{n\left(1-\frac{1}{2^{k-\ell-1}}\right)}$ for some constant $A$ depending on
$k$ and $\ell$.

If we have $m\leq(1-\varepsilon)2^{n-\ell+1}$ (corresponding to
$D=\frac{1-\varepsilon}{2^{\ell-1}}$), then by $(\ref{eq:*})$,

$|S^{\prime}|=F_{\ell,1}(v_{1},...,v_{\ell})\geq\frac{m(2^{n}-m)(2^{n-1}-m)...(2^{n-\ell+1}-m)}{2^{n}\cdot
2^{n-1}\cdot...\cdot
2^{n-\ell+1}}=m\varepsilon\prod_{k=1}^{\ell-1}\left(1-\frac{1-\varepsilon}{2^{k}}\right)\geq
m\varepsilon\phi\left(\frac{1}{2}\right)$

where $\phi\left(\frac{1}{2}\right)$ is the value of the Euler function at
$\frac{1}{2}$, which is approximately $0.2888$.

This can be ensured to be at least $A\cdot
2^{n\left(1-\frac{1}{2^{k-\ell-1}}\right)}$ by taking
$m\geq\frac{A}{\varepsilon\cdot\phi\left(\frac{1}{2}\right)}\cdot
2^{n\left(1-\frac{1}{2^{k-\ell-1}}\right)}$.

Therefore, if we have
$\frac{A}{\varepsilon\cdot\phi\left(\frac{1}{2}\right)}\cdot
2^{n\left(1-\frac{1}{2^{k-\ell-1}}\right)}\leq
m\leq\frac{1-\varepsilon}{2^{\ell-1}}\cdot 2^{n}$, then
$[n,m]\to[k,2^{k-\ell}]$. ∎

######  Remark 4.6.

Note that Theorem 4.5 does not hold for $D\geq\frac{1}{2^{\ell-1}}$, as taking
$S$ to be a full $(n-\ell+1)$-flat in $\mathbb{F}_{2}^{n}$, it will not induce
any $[k,2^{k-\ell}]$-flats, as for any $k$-flat $\mathcal{F}_{k}$ with
$\mathcal{F}_{k}\cap S\neq\emptyset$, we must have
$\dim\mathcal{F}_{k}-\dim(\mathcal{F}_{k}\cap S)\leq\ell-1$, meaning that
$|\mathcal{F}_{k}\cap S|\geq 2^{k-\ell+1}$.

##  5 Finding $[k,3\cdot 2^{k-\ell}]$-flats for almost all values $|S|$ when
$S$ has a low positive density

We continue our investigation for the case when the binary form of $t$
contains exactly two $1$s which are consecutive. The main focus will be the
proof of Theorem 1.10, which we will recall:

Theorem 1.10. For every pair $(k,\ell)$ of integers with $2\leq\ell\leq k-1$,
the density of integer values $m$ within the interval
$\left[0,\frac{1}{2^{\ell-1}}\cdot 2^{n}\right]$ for which $[n,m]\to[k,3\cdot
2^{k-\ell}]$ holds, tends to $1$ as $n\to\infty$. Hence $\rho(n;k,3\cdot
2^{k-\ell})\geq\frac{1}{2^{\ell-1}}.$

The proof builds on ideas similar to those used for Theorem 4.5, this time
bounding the number of $[2,3]$-flats in $S$ based on its additive energy,
which is an additive combinatorial notion that we will now define.

For a set $S\subseteq\mathbb{F}_{2}^{n}$, let the additive energy of $S$ (a
notion introduced by Tao and Vu [28, Section 2.3]), denoted by $E(S)$ be as
follows:

$E(S)=\\{(u_{1},u_{2},u_{3},u_{4})\in S^{4}:u_{1}+u_{2}=u_{3}+u_{4}\\}.$

If $|S|=m$ then $E(S)\leq m^{3}$ since to each triple $(u_{1},u_{2},u_{3})$,
at most one value $u_{4}$ can belong, and there is equality if and only if $S$
is a flat of $\mathbb{F}_{2}^{n}$ (which is easy to verify using
characteristic $2$). However, this can only happen if $m$ is a power of $2$.

In fact, the bound $E(S)\leq m^{3}$ can be improved in general using the
concept below.

######  Definition 5.1.

For $d\in\mathbb{Z}^{+}$ and $a\in\mathbb{Z}$, define the least absolute
residue of $a$ modulo $d$, denoted $r_{a}(d)$, by

$r_{a}(d)=\min_{k\in\mathbb{Z}}|a-kd|.$

######  Proposition 5.2.

Fix real numbers $\frac{1}{2}\leq\alpha<1$ and $\varepsilon>0$ with
$\alpha+\varepsilon<1$. Then there exists $m_{0}\in\mathbb{Z}^{+}$ such that
for any pair of integers $n>k\in\mathbb{Z}^{+}$, if
$S\subseteq\mathbb{F}_{2}^{n}$ is any set with

$m_{0}\leq|S|=m\in[2^{k},2^{k+1}]\mbox{\ and \
}r_{2^{\lceil{(\alpha+\varepsilon)k\rceil}}}(m)\geq 2^{\alpha k},$

then $E(S)\leq m^{3}-m^{2+\alpha-\varepsilon}$.

Proving this bound requires estimates on sizes of cuts in hypercube graphs
(and disjoint unions thereof), which we will defer to Section 5.2, and the
bound itself will be proven in Section 5.3. For now, let us apply this to
prove our theorem.

###  5.1 Proof of Theorem 1.10

The following lemma gives an alternative expression of the additive energy
which will be helpful.

######  Lemma 5.3.

For a nonzero vector $v\in\mathbb{F}_{2}^{n}$, let us denote by $p_{v}$ the
number of pairs in $S$ with difference $v$. Then we have

$E(S)=|S|^{2}+4\sum_{v\in\mathbb{F}_{2}^{n}\setminus\\{0\\}}p_{v}^{2}.$

###### Proof.

The first term comes from quadruples of the form $(u_{1},u_{1},u_{3},u_{3})$
for arbitrary $u_{1},u_{3}\in S$. For the second term we can choose any pairs
$\\{u_{1},u_{2}\\}$ and $\\{u_{3},u_{4}\\}$ with sum
$u_{1}+u_{2}=u_{3}+u_{4}=v$ and then order each pair in one of two ways. ∎

Now we can relate the additive energy to the number of induced $[2,3]$-flats:

######  Lemma 5.4.

Let $S\subseteq\mathbb{F}_{2}^{n}$ be a set with $|S|=m$. Then the number of
$2$-flats of $\mathbb{F}_{2}^{n}$ containing exactly 3 points of $S$ (denoted
$F_{2,3}$) satisfies $F_{2,3}=\frac{1}{6}(m^{3}-E(S))$.

###### Proof.

Taking a nonzero vector $v\in\mathbb{F}_{2}^{n}$, we clearly have
$F_{1,2}(v)=p_{v}$ and $F_{1,1}(v)=m-2p_{v}$. A $[2,3]$-flat is composed of a
$[1,2]$-flat and a $[1,1]$-flat which are parallel to each other, however each
$[2,3]$-flat can be decomposed in 3 such ways, so

$3F_{2,3}=\sum_{v}F_{1,2}({v})F_{1,1}({v})=\sum_{v}p_{v}(m-2p_{v})=m\binom{m}{2}-2\sum_{v}p_{v}^{2},$

where $\sum_{v}p_{v}^{2}=\frac{E(S)-m^{2}}{4}$. This means that
$3F_{2,3}=\frac{m^{2}(m-1)}{2}-2\cdot\frac{E(S)-m^{2}}{4}=\frac{1}{2}m^{3}-\frac{1}{2}E(S)$,
giving the statement. ∎

###### Proof of Theorem 1.10.

We follow a similar proof method as for Theorem 4.5.

Fix an $\varepsilon_{0}>0$ and take a set $S\subseteq\mathbb{F}_{2}^{n}$ with
$|S|=m\leq(1-\varepsilon_{0})2^{n-\ell+1}$.

Let us choose directions $v_{1},v_{2},...,v_{\ell}$ so that each direction
$v_{d}$ forms a linearly independent set with the previous ones, and the
following condition holds for each $d\in\\{2,3,\ldots,\ell\\}$:

$F_{d,3}(v_{1},v_{2},...,v_{d})\geq\frac{F_{2,3}}{\begin{bmatrix}n\\\
2\end{bmatrix}_{2}}\cdot\frac{(2^{n-2}-m)(2^{n-3}-m)...(2^{n-d+1}-m)}{2^{n-2}\cdot
2^{n-3}\cdot...\cdot 2^{n-d+1}}$

.

This can be done in the same way as in Theorem 4.5, except for the following
first step: for $d=2$, choose $v_{1}$ and $v_{2}$ together such that for
$L_{2}=\langle v_{1},v_{2}\rangle$, the number of $[2,3]$-flats parallel to
$L_{2}$ is at least ${F_{2,3}}{\Large/}{\footnotesize\begin{bmatrix}n\\\
2\end{bmatrix}_{2}}$. (This can be done, as there are
$\footnotesize\begin{bmatrix}n\\\ 2\end{bmatrix}_{2}$ possible directions of
$2$-flats.)

After such directions have been chosen, in order to use Theorem 4.1 to get a
$[k,3\cdot 2^{k-\ell}]$-flat, we need the following condition to hold:

$\frac{F_{2,3}}{\begin{bmatrix}n\\\
2\end{bmatrix}_{2}}\cdot\frac{(2^{n-2}-m)(2^{n-3}-m)...(2^{n-\ell+1}-m)}{2^{n-2}\cdot
2^{n-3}\cdot...\cdot 2^{n-\ell+1}}\geq\frac{5}{2}\cdot
2^{(n-\ell)\left(1-\frac{1}{2^{k-\ell-1}}\right)}$

.

Since $m\leq(1-\varepsilon_{0})2^{n-\ell+1}$, the left hand side is at least
$\frac{6F_{2,3}}{2^{2n}}\varepsilon_{0}\phi\left(\frac{1}{2}\right)$. Here we
used the fact that $\begin{bmatrix}n\\\
2\end{bmatrix}_{2}=\frac{(2^{n}-1)(2^{n}-2)}{6}$. Therefore, it suffices to
require

$F_{2,3}\geq\lambda_{1}\cdot 2^{n\left(3-\frac{1}{2^{k-\ell-1}}\right)}$

for a fixed positive constant $\lambda_{1}$ depending on $k$ and $\ell$ only.

Now if $\delta=\frac{1}{2^{k-\ell-1}}$, let $\alpha=1-\frac{\delta}{4}$ and
$\varepsilon=\frac{\delta}{8}$. Then apply Proposition 5.2 for these values
$\alpha$ and $\varepsilon$, gaining that for sufficiently large $m$ satisfying
$r_{2^{\lceil(\alpha+\varepsilon)t\rceil}}(m)\geq 2^{\alpha t}$ where
$m\in[2^{t},2^{t+1}]$, we have $E(S)\leq m^{3}-m^{3-\frac{3}{8}\delta}$.

By Lemma 5.4, we then have
$F_{2,3}=\frac{1}{6}(m^{3}-E(S))\geq\frac{1}{6}m^{3-\frac{3}{8}\delta}$. For
the guaranteed existence of a $[k,3\cdot 2^{k-\ell}]$-flat by our method, it
suffices to have $\frac{1}{6}m^{3-\frac{3}{8}\delta}\geq\lambda_{1}\cdot
2^{(3-\delta)n}$, equivalent to
$m\geq\lambda_{2}\cdot\left(2^{n}\right)^{\frac{3-\delta}{3-\frac{3}{8}\delta}}$
for a positive constant $\lambda_{2}$. Letting
$\mu\in\left(\frac{3-\delta}{3-\frac{3}{8}\delta},1\right)$ be fixed, we can
freely assume that $m\geq 2^{\mu n}$ since the density of values $m$ below
this value in the range $[0,\frac{1-\varepsilon_{0}}{2^{\ell-1}}\cdot 2^{n}]$
tends to 0. Hence for $n$ sufficiently large, we will then have
$m\geq\lambda_{2}\cdot\left(2^{n}\right)^{\frac{3-\delta}{3-\frac{3}{8}\delta}}$.

Then taking an interval $[2^{t},2^{t+1})$, if $m$ lies uniformly in this
interval then the probability that
$r_{2^{\lceil(\alpha+\varepsilon)t\rceil}}(m)\geq 2^{\alpha t}$ is $\geq
1-\frac{2\cdot\left\lfloor 2^{\alpha
t}\right\rfloor+1}{2^{\lceil(\alpha+\varepsilon)t\rceil}}\geq 1-\frac{2\cdot
2^{\alpha t}+1}{2^{(\alpha+\varepsilon)t}}=1-\frac{2}{2^{\varepsilon
t}}-\frac{1}{2^{(\alpha+\varepsilon)t}}$. With the assumption that $m\geq
2^{\mu n}$, we have $t\geq\mu n$, hence this lower bound for the probability
of correctness of $m$ tends uniformly to $1$ as $n\to\infty$.

So for each $\varepsilon_{0}>0$, the density of integers
$m\in\left[0,\frac{1-\varepsilon_{0}}{2^{\ell-1}}\cdot 2^{n}\right]$ such that
$[n,m]\to[k,3\cdot 2^{k-\ell}]$ tends to $1$ as $n\to\infty$. Therefore the
same holds for $m\in\left[0,\frac{1}{2^{\ell-1}}\cdot 2^{n}\right]$ as well. ∎

###  5.2 Bounding sizes of hypercube cuts

######  Definition 5.5.

The $n$-dimensional hypercube graph $Q_{n}$ is a graph with vertex set
$\mathbb{F}_{2}^{n}$ such that two vertices are connected by an edge if and
only if their Hamming distance is 1.

######  Definition 5.6.

Define the function $\Psi:\mathbb{N}^{+}\to\mathbb{N}$ by
$\Psi(t)=\sum\limits_{i=0}^{t-1}s_{2}(i)$. Recall that $s_{2}$ denotes the
binary digit sum function.

Observe that for any positive integer $k$ we have $\Psi(2^{k})=k\cdot
2^{k-1}$, as for each $1\leq j\leq k$, precisely half of the integers between
$0$ and $2^{k}-1$ have a digit $1$ at the $j^{\mathrm{th}}$ position in the
binary representation.

######  Lemma 5.7 (Hart, [15]).

For a positive integer $t$, let $c(t)$ be the maximum number of edges in a
$t$-vertex subgraph of $Q_{n}$ ranging over all possible values
$n\in\mathbb{N}^{+}$. Then for each $t$ we have $c(t)\leq\Psi(t)$.

See [15] for a proof and a description of the subgraphs attaining the upper
bound for $c(t)$. Notably, one such optimal subgraph is induced by the
lexicographic construction $\mathcal{L}_{t}$, introduced in Definition 3.4.
For any $T\subseteq V(Q_{n})$ we have the simple relation

$2e(T)+e(T,\overline{T})=n|T|$

by double counting all incident edges to each point of $T$ [15]. This yields
the corollary below.

######  Corollary 5.8 (Hart, Theorem 1.5, [15]).

Let $n\geq 1$ and $1\leq t\leq 2^{n}-1$ be fixed integers. Then the minimum
possible value of $e(T,\overline{T})$ for a subset $T\subseteq V(Q_{n})$ of
size $t$ is $nt-2\Psi(t)$.

From this, we derive the following consequence:

######  Proposition 5.9.

Let $n\geq 1$ and $0\leq d\leq n-1$ be integers. Take any cut
$T\cup\overline{T}=\mathbb{F}_{2}^{n}$ of the $n$-dimensional hypercube graph
$Q_{n}$ that has at least $2^{d}$ points in both parts. Then at least
$2^{d}(n-d)$ edges of $Q_{n}$ cross the cut, i.e., $e(T,\overline{T})\geq
2^{d}(n-d)$.

###### Proof.

Suppose that $t=|T|$ and $2^{d}\leq t\leq 2^{n-1}$. Using Corollary 5.8, we
only need to show that $nt-2\Psi(t)\geq 2^{d}(n-d)$ holds.

It is elementary to see that for integers $0\leq k\leq n-1$, the function
$2^{k}(n-k)$ is increasing. This implies that in the case $t=2^{n-1}$, the
statement holds as $nt-2\sum_{i=0}^{t-1}s_{2}(i)=n\cdot
2^{n-1}-2(n-1)2^{n-2}=2^{n-1}=2^{n-1}(n-(n-1))\geq 2^{d}(n-d)$.
So from now on, assume that $2^{d}\leq t<2^{n-1}$. The monotonicity implies
that we can assume $2^{d}\leq t<2^{d+1}$, where $d\leq n-2$.

The function $\Psi$ can be related to the well-known Takagi function $\tau$,
which is a continuous but nowhere differentiable non-negative function on
$[0,1]$. Let $t\in\mathbb{Z}^{+}$ be expressed as $t=2^{d}(1+x)$ for
$d\in\mathbb{N}$ and $x\in[0,1)$. Then

$2\Psi(t)=td+2^{d}(2x-\tau(x)),$ (2)

see Monroe [21, Corollary 5.0.8 (a)]. For a survey on the Takagi function, see
[19].

Now $nt-2\Psi(t)\geq 2^{d}(n-d)\Leftrightarrow 2\Psi(t)\leq n(t-2^{d})+d\cdot
2^{d}$. Since $n\geq d+2$, it suffices to prove that
$2\Psi(t)\leq(d+2)(t-2^{d})+d\cdot 2^{d}$. By (2), this is equivalent to

$td+2^{d}(2x-\tau(x))\leq(d+2)(t-2^{d})+d\cdot 2^{d}\Leftrightarrow
2^{d+1}x-2^{d}\cdot\tau(x)\leq 2\cdot 2^{d}x,$

which holds since $\tau(x)\geq 0$ for all $x$. ∎

Let us prove a slightly different version of this proposition, for the case of
multiple copies of the hypercube graph.

######  Proposition 5.10.

Let $n\geq 1$, $k\geq 1$ and $0\leq d\leq n-2$ be integers. Let $kQ_{n}$
denote the disjoint union of $k$ copies $Q_{n}^{(1)}$, $Q_{n}^{(2)}$, …,
$Q_{n}^{(k)}$ of the hypercube graph $Q_{n}$. Take any cut $kQ_{n}=A\sqcup B$
such that $|A|\geq 2^{d}$, and for each $1\leq i\leq k$, $1\leq|A\cap
Q_{n}^{(i)}|\leq 2^{n-1}$. Then at least $2^{d}(n-d)$ edges of $kQ_{n}$ cross
the cut.

###### Proof.

By [15, Proposition 2.1], the function $\Psi$ satisfies the recursion

$\Psi(t)=\max\limits_{0<m\leq\frac{t}{2}}(\Psi(m)+\Psi(t-m)+m),$

hence for any partition $t=t_{1}+t_{2}$ with $t_{1},t_{2}\in\mathbb{Z}^{+}$,
we have $\Psi(t)\geq\Psi(t_{1})+\Psi(t_{2})$. By induction, this implies that
for any partition $t=t_{1}+t_{2}+...+t_{k}$ (for any $k\geq 1$) with
$t_{1},t_{2},...,t_{k}\in\mathbb{Z}^{+}$, we have
$\Psi(t)\geq\Psi(t_{1})+\Psi(t_{2})+...+\Psi(t_{k})$.

Let $A=\bigsqcup\limits_{i=1}^{k}A_{i}$ where $A_{i}=A\cap Q_{n}^{(i)}$, and
similarly let $B=\bigsqcup\limits_{i=1}^{k}B_{i}$.

We consider two cases depending on $\max\limits_{1\leq i\leq k}|A_{i}|$:

Case 1. There exists an $i$ such that $|A_{i}|\geq 2^{d}$.

In this case, in $Q_{n}^{(i)}$ we have a cut into $A_{i}$ and $B_{i}$ such
that $2^{d}\leq|A_{i}|\leq 2^{n-1}$, which, by Proposition 5.9, intersects at
least $2^{d}(n-d)$ edges on its own.

Case 2. For all values $i$, we have $|A_{i}|<2^{d}$.

In this case, each $i$ satisfies $|A_{i}|<2^{d}\leq 2^{n-2}$. Letting
$\sigma_{j}=\sum_{i=1}^{j}|A_{i}|$ for each $1\leq j\leq k$, we have
$\sigma_{k}=|A|\geq 2^{d}$. Let $j\in\\{1,2,\ldots,k\\}$ be the smallest value
such that $\sigma_{j}\geq 2^{d}$. Then $\sigma_{j-1}<2^{d}$, and
$\sigma_{j}=\sigma_{j-1}+|A_{j}|<2^{d}+2^{d}\leq 2^{n-1}$. Now adding up the
number of edges crossing the cut in the first $j$ hypercubes, we get at least

$\begin{split}n|A_{1}|-2\Psi(|A_{1}|)+n|A_{2}|-2\Psi(|A_{2}|)+...+n|A_{j}|-2\Psi(|A_{j}|)\geq\\\
n(|A_{1}|+|A_{2}|+...+|A_{j}|)-2\Psi(|A_{1}|+|A_{2}|+...+|A_{j}|)=n\sigma_{j}-2\Psi(\sigma_{j})\end{split}$
(3)

by Corollary 5.8.

This in turn completes the proof, as $n\sigma_{j}-2\Psi(\sigma_{j})\geq
2^{d}(n-d)$ by the proof of Proposition 5.9, since $j$ was chosen so that
$2^{d}\leq\sigma_{j}\leq 2^{n-1}$ holds. ∎

###  5.3 Bounding the additive energy

######  Proposition 5.11.

Given integers $m,b,c,d,n\geq 1$ with $d<b$ and $r_{2^{b+1}}(m)\geq 2^{d}$,
the following holds. For any $S\subseteq\mathbb{F}_{2}^{n}$ with $|S|=m$, if
$S$ contains at least $2^{b}$ distinct nonzero differences $v$ with $p_{v}\geq
c$, then $(b+1)(m-2c)\geq 2^{d}(b+1-d)$.

###### Proof.

Take the linear span of the $2^{b}$ distinct differences. This span must have
dimension at least $b+1$ (otherwise the number of vectors would be at most
$|\mathbb{F}_{2}^{b}\setminus\\{0\\}|=2^{b}-1$). Pick $b+1$ linearly
independent differences $(v_{1},v_{2},...,v_{b+1})$ with $p_{v_{i}}\geq c$ for
all $1\leq i\leq b+1$, and let $L=\left\langle
v_{1},v_{2},...,v_{b+1}\right\rangle$. Consider the $L$-cosets of
$\mathbb{F}_{2}^{n}$ based on how many elements of $S$ they contain. A coset
containing $2^{b+1}$ or $0$ elements of $S$ will be called full or empty
respectively. The remaining elements of $S$ (not in full cosets) are spread
across some cosets (say, $\ell$ of them) whose union we will call $U$. Since
$r_{2^{b+1}}(m)\neq 0$, we must have $\ell\geq 1$. On the vertex set $U$,
define the graph with edges joining all pairs of vertices with a difference of
$v_{i}$ for any $1\leq i\leq b+1$. This graph is isomorphic to $\ell Q_{b+1}$;
let the $i$-th copy of $Q_{b+1}$ be $Q_{b+1}^{(i)}$. For each $i$, define a
partition of $Q_{b+1}^{(i)}$ into sets $A_{i}$ and $B_{i}$ as follows: if
$|Q_{b+1}^{(i)}\cap S|\leq\frac{1}{2}\cdot 2^{b+1}$ then let
$A_{i}=Q_{b+1}^{(i)}\cap S$ and $B_{i}=Q_{b+1}\setminus S$, and otherwise let
$B_{i}=Q_{b+1}^{(i)}\cap S$ and $A_{i}=Q_{b+1}\setminus S$. (This way, for
each $1\leq i\leq\ell$ we will have $|A_{i}|\leq|B_{i}|$.) Let
$A=\cup_{i=1}^{\ell}A_{i}$ and $B=\cup_{i=1}^{\ell}B_{i}$. Thus we obtained a
partition $U=A\sqcup B$.

Since for each $i$, we have $p_{v_{i}}\geq c$, this means that at most $m-2c$
elements $w\in S$ satisfy the property that $w+v_{i}\not\in S$. This means
that altogether (summing over all $1\leq i\leq b+1$), the number of pairs
$(w,w^{\prime})$ with $w\in S$ and $w^{\prime}\not\in S$ such that
$w^{\prime}-w=v_{i}$ for some $1\leq i\leq b+1$, which is the same as $e(U\cap
S,U\setminus S)=e(A,B)$, is at most $(b+1)(m-2c)$.

Without loss of generality, let $S\cap U=A_{1}\sqcup A_{2}\sqcup...\sqcup
A_{\ell^{\prime}}\sqcup B_{\ell+1}\sqcup...\sqcup B_{\ell}$. Now if the number
of full cosets is $f$ then

$\begin{split}m&=f\cdot
2^{b+1}+|A|+\sum_{i=\ell^{\prime}+1}^{\ell}(|B_{i}|-|A_{i}|)=f\cdot
2^{b+1}+|A|+\sum_{i=\ell^{\prime}+1}^{\ell}(2^{b+1}-2|A_{i}|)\\\ &=c\cdot
2^{b+1}+\sum_{i=1}^{\ell^{\prime}}|A_{i}|-\sum_{i=\ell^{\prime}+1}^{\ell}|A_{i}|\end{split}$
(4)

for some integer $c$. Hence $2^{d}\leq r_{2^{b+1}}(m)\leq|m-c\cdot
2^{b+1}|\leq\sum_{i=1}^{\ell}|A_{i}|=|A|$.

Let us now apply Proposition 5.10 with $n=b+1$ and $k=\ell$, using the
conditions $|A|\geq 2^{d}$ and $d\leq b-1=n-2$. The number of crossing edges
is at least $2^{d}(n-d)=2^{d}(b+1-d)$ and, as seen previously, at most
$(b+1)(m-2c)$. This completes the proof. ∎

######  Lemma 5.12.

Let $(h_{1},h_{2},...,h_{\alpha})$ be a sequence of non-negative real numbers
with $\sum_{i=1}^{\alpha}h_{i}=N$. Suppose that
$0\leq\alpha^{\prime}\leq\alpha$ for $\alpha^{\prime}\in\mathbb{Z}$ and
$0<M_{1}<M$ for $M_{1},M\in\mathbb{R}$.

If $h_{i}\leq M$ holds for all $i$, and $h_{i}>M_{1}$ for at most
$\alpha^{\prime}$ values of $i$, then

$\sum_{i=1}^{\alpha}h_{i}^{2}\leq\alpha^{\prime}M^{2}+(N-\alpha^{\prime}M)M_{1}.$

###### Proof.

Since $\alpha-\alpha^{\prime}$ of the values lie in $[0,M_{1}]$ and the others
in $[0,M]$, we have

$\sum_{i=1}^{\alpha}\left(h_{i}-\frac{M_{1}}{2}\right)^{2}\leq\alpha^{\prime}\left(M-\frac{M_{1}}{2}\right)^{2}+(\alpha-\alpha^{\prime})\left(\frac{M_{1}}{2}\right)^{2}=\alpha^{\prime}M^{2}-\alpha^{\prime}MM_{1}+\alpha\frac{M_{1}^{2}}{4}.$

This means that
$\sum_{i=1}^{\alpha}h_{i}^{2}=\sum_{i=1}^{\alpha}\left(h_{i}-\frac{M_{1}}{2}\right)^{2}+NM_{1}-\alpha\frac{M_{1}^{2}}{4}\leq\alpha^{\prime}M^{2}-\alpha^{\prime}MM_{1}+NM_{1}$
holds, as required. ∎

Now we are ready to prove Proposition 5.2.

###### Proof of Proposition 5.2.

Throughout the proof, we will use the fact that $m$, and hence $k$, are taken
to be sufficiently large.

In order to bound the additive energy, we will use the expression

$E(S)=|S|^{2}+4\sum\limits_{{v}\in\mathbb{F}_{2}^{n}\setminus\\{0\\}}p_{v}^{2}.$

Firstly, it is clear that for any ${v}\neq 0$, we have
$p_{v}\leq\frac{1}{2}m$. Set
$c=\frac{1}{2}m-\frac{\varepsilon}{4(\alpha+\varepsilon)}2^{\alpha k}$. Let us
put an upper bound on the number of differences
${v}\in\mathbb{F}_{2}^{n}\setminus\\{0\\}$ such that $p_{v}\geq c$. Let
$\Delta$ be the number of such differences.

In order to do this, we will apply Proposition 5.11. Via replacing $c$ by
$\lceil c\rceil$, it is clear that the statement of this proposition holds for
real numbers $c$ as well.

Fix $b=\lceil(\alpha+\varepsilon)k\rceil$. Then we have $r_{2^{b}}(m)\geq
2^{\alpha k}$ and hence $r_{2^{b+1}}(m)\geq 2^{\alpha k}$ too. Set
$d=\lfloor\alpha k\rfloor$; then if $\Delta\geq 2^{b}$ then the conditions of
the Proposition hold, so we have $(b+1)(m-2c)\geq 2^{d}(b+1-d)$.

Via differentiation, it can be seen that the function $d\mapsto 2^{d}(b+1-d)$
is increasing on the real interval $[0,b-1]$, therefore we have
$2^{d}(b+1-d)\geq 2^{\alpha k-1}(b+1-(\alpha k-1))$ if $0\leq\alpha k-1$ and
$\lfloor\alpha k\rfloor\leq b-1$, which is equivalent to $1\leq\alpha k<b$,
which is true for $k\geq 2$.

So we have

$(b+1)(m-2c)\geq 2^{\alpha k-1}(b+1-(\alpha k-1)).$

Using $(\alpha+\varepsilon)k\leq b\leq(\alpha+\varepsilon)k+1$:

$((\alpha+\varepsilon)k+2)\frac{\varepsilon}{2(\alpha+\varepsilon)}2^{\alpha
k}\geq 2^{\alpha k-1}((\alpha+\varepsilon)k-\alpha k+2)$

$\Leftrightarrow\frac{\varepsilon}{\alpha+\varepsilon}\geq\frac{\varepsilon
k+2}{(\alpha+\varepsilon)k+2},$

would be a contradiction. Therefore we must have $\Delta<2^{b}$, so the number
of differences such that $p_{v}\geq c$ is less than $2^{b}$.

Therefore, by using Lemma 5.12 for the $\alpha=2^{n}-1$ values $p_{v}$ with
$N=\sum p_{v}=\binom{|S|}{2}=\frac{m(m-1)}{2}$, $~{}M=\frac{1}{2}m$,
$~{}M_{1}=c$ and $\alpha^{\prime}=2^{b}$ (for $k>b$, we have $2^{b}<2^{k}\leq
m\leq 2^{n}$, so the condition $\alpha^{\prime}\leq\alpha$ holds), we have

$\begin{split}\sum_{{v}}p_{v}^{2}&\leq
2^{b}\left(\frac{1}{2}m\right)^{2}+\left(\frac{m(m-1)}{2}-2^{b}\cdot\frac{1}{2}m\right)c\leq
2^{b}\cdot\frac{1}{4}m^{2}+\left(\frac{1}{2}m^{2}-2^{b}\cdot\frac{1}{2}m\right)\left(\frac{1}{2}m-\frac{\varepsilon}{4(\alpha+\varepsilon)}2^{\alpha
k}\right)\\\
&=\frac{1}{4}m^{3}-\frac{\varepsilon}{8(\alpha+\varepsilon)}m^{2}\cdot
2^{\alpha k}+\frac{\varepsilon}{8(\alpha+\varepsilon)}m\cdot 2^{\alpha
k+b}\leq\frac{1}{4}m^{3}-\frac{\varepsilon}{8(\alpha+\varepsilon)}m^{2}\cdot\frac{m^{\alpha}}{2^{\alpha}}+\frac{\varepsilon}{8(\alpha+\varepsilon)}m\cdot
2m^{2\alpha+\varepsilon}\\\ &=\frac{1}{4}m^{3}-\frac{\varepsilon}{8\cdot
2^{\alpha}\cdot(\alpha+\varepsilon)}m^{2+\alpha}+\frac{\varepsilon}{4(\alpha+\varepsilon)}m^{1+2\alpha+\varepsilon},\end{split}$

where $1+2\alpha+\varepsilon<2+\alpha$ holds, since $\alpha+\varepsilon<1$.
Thus we obtain $m^{1+2\alpha+\varepsilon}=o(m^{2+\alpha})$, and

$E(S)=m^{2}+4\sum\limits_{{v}\in\mathbb{F}_{2}^{n}\setminus\\{0\\}}p_{v}^{2}\leq
m^{3}-\frac{\varepsilon}{2^{\alpha+1}(\alpha+\varepsilon)}m^{2+\alpha}+o(m^{2+\alpha}),$

showing the statement. ∎

##  6 Concluding remarks

For general pairs $(k,t)$, it remained open to decide whether the density of
the spectrum $\rho(n;k,t)=\frac{Sp(n;k,t)}{2^{n}}$ tends to $1$ as $n$ tends
to infinity, or even to obtain a general constant lower bound on this density
for a given pair $(k,t)$ with $0\leq t\leq 2^{k}$. The proof of Theorem 1.10
suggests that such a result might be deduced from a supersaturation type
result on $[k,t]$-flats, similar to the lower bound on $F_{2,3}$ derived from
Proposition 5.2.

We did not elaborate on the case $q>2$. However, note that the approach we
used to exclude several values from the spectra $Sp(n;k,t)$ applies for $q>2$
as well. Indeed, we can construct point sets as a combination of disjoint full
flats and point sets which hit every $k$-flat in small number of points, i.e.,
evasive sets. However, proving density results on the spectrum appear to be
much harder, as it was the case even for $q=3$ with lines (or full flats), as
the general problem contains the determination of the order of magnitude of
the maximum size of $q$-AP-free sets of $\mathbb{F}_{q}^{n}$.

While we focused on the sets in $\mathrm{AG}(n,q)$, $q=2$, we mention that the
analogous question was investigated by Ihringer and Verstraëte [18] for point
sets $X$ in a projective space $\mathrm{PG}(n,q)$ where all $k$-dimensional
subspaces must have a bounded number of points. However their results concern
the case when $q$ is large.

## References

  * [1] Axenovich, M., Weber, L. (2021). Absolutely avoidable order-size pairs for induced subgraphs. arXiv preprint arXiv:2106.14908.
  * [2] Axenovich, M., Balogh, J., Clemen, F. C., Weber, L. (2022). Unavoidable order-size pairs in hypergraphs–positive forcing density. arXiv preprint arXiv:2208.06626.
  * [3] Ben-Aroya, A., Shinkar, I. (2014). A Note on Subspace Evasive Sets, Chicago Journal of Theoretical Computer Science 9, 1–11.
  * [4] Bennett, M. (2019). Bounds on sizes of generalized caps in AG(n, q) via the Croot-Lev-Pach polynomial method. Journal of Combinatorial Theory, Series A, 168, 255-271.
  * [5] Bose, R. C., Ray-Chaudhuri, D.K. (1960). On a Class of Error Correcting Binary Group Codes. Information and Control 3, pp. 68–79.
  * [6] Caro, Y., Lauri, J., Zarb, C. (2023). The feasibility problem for line graphs. Discrete Applied Mathematics, 324, 167-180.
  * [7] Charbit, P., Jeandel, E., Koiran, P., Perifel, S., Thomassé, S. (2008). Finding a vector orthogonal to roughly half a collection of vectors. Journal of complexity, 24(1), 39-53.
  * [8] Croot, E., Lev, V. F., Pach, P. P. (2017). Progression-free sets in are exponentially small. Annals of Mathematics, 331-337.
  * [9] Ellenberg, J. S., Gijswijt, D. (2017). On large subsets of with no three-term arithmetic progression. Annals of Mathematics, 339-343.
  * [10] Erdős, P., Füredi, Z., Rothschild, B. L., Sós, V. T. (1999). Induced subgraphs of given sizes. Discrete mathematics, 200(1-3), 61-77.
  * [11] Etzion, T. (2014). Covering of subspaces by subspaces. Designs, codes and cryptography, 72(2), 405-421.
  * [12] Fox, J., Pham, H. T. (2021). Popular progression differences in vector spaces. International Mathematics Research Notices, 2021(7), 5261-5289.
  * [13] Fox, J., Pham, H. T. (2019). Popular progression differences in vector spaces II. Discrete Analysis, 11002.
  * [14] Guruswami, V. (2011). Linear-algebraic list decoding of folded Reed-Solomon codes, in Proceedings of the 26th IEEE Conference on Computational Complexity.
  * [15] Hart, S. (1975). A note on the edges of the $n$-cube. Discrete Mathematics, Volume 14, Issue 2, 1976, 157-163.
  * [16] He, J., Ma, J., Zhao, L. (2021). Improvements on induced subgraphs of given sizes. arXiv preprint arXiv:2101.03898.
  * [17] Héger, T., Nagy, Z. L. (2021). Short minimal codes and covering codes via strong blocking sets in projective spaces. IEEE Transactions on Information Theory, 68(2), 881-890.
  * [18] Ihringer, F., Verstraëte, J. (2022). Large $(k;r,s;n,q)$-sets in Projective Spaces. arXiv preprint arXiv:2211.04329.
  * [19] Lagarias, J. C. (2012). The Takagi Function and Its Properties. Functions in number theory and their probabilistic aspects, 153–189.
  * [20] Lindström, B. (1969). Determination of Two Vectors from the Sum. Journal of Combinatorial Theory 6, 402–407.
  * [21] Monroe, L. (2021). A Few Identities of the Takagi Function on Dyadic Rationals. arXiv preprint arXiv:2111.05996.
  * [22] Pudlák, P., Rödl, V. (2004). Pseudorandom sets and explicit constructions of Ramsey graphs. Quaderni di Matematica, 13, 327–346.
  * [23] Reitwiesner, G. W. (1960). Binary arithmetic. In Advances in computers (Vol. 1, pp. 231-308). Elsevier.
  * [24] Sanders, T. (2008). Additive structures in sumsets. In Mathematical Proceedings of the Cambridge Philosophical Society (Vol. 144, No. 2, pp. 289-316). Cambridge University Press.
  * [25] Sudakov, B., Tomon, I. (2022). Evasive sets, covering by subspaces, and point-hyperplane incidences. arXiv preprint arXiv:2207.13077.
  * [26] Setyawan, Y. (1998). Combinatorial Number Theory: Results of Hilbert, Schur, Folkman, and Hindman. Simon Fraser University.
  * [27] Tait, M., Won, R. (2021). Improved Bounds on Sizes of Generalized Caps in AG(n,q). SIAM Journal on Discrete Mathematics, 35(1), 521-531.
  * [28] Tao, T., Vu, V. H. (2006). Additive combinatorics (Vol. 105). Cambridge University Press.