6 3AP-free subsets of \({\mathbb {Z}}_4^n\), if \(n \le 4\)
Now, we are ready to prove Theorem
3.1. In this section we give a proof for
\(n\le 4\), the case
\(n=5\) is covered in the next section.
Before starting the proof we give a brief outline of the main strategy. If we take a look at condition \((*)\) or \((**)\), then heuristically it seems to be a good idea to use sets with small doubling, since \((*)\) and \((**)\) seem to be less restrictive for sets with a small doubling. Subspaces have a small doubling, and working with them is easier, an important step will be to show that it can be assumed (up to \(n\le 5\)) that in a maximal configuration all the (non-empty) subsets are subspaces. To arrive at this all-subspace state, we can use arguments of the following type. If \(A(x)+A(x)\supseteq V\) for a large subspace V (where “large” means that \(|V|\ge |A(x)|\)), then we can replace A(x) by V, since \((*)\) (or \((**)\)) remains true (that is, the corresponding subset is still 3AP/4AP-free) and the total size of the subsets is larger (not smaller). So the general plan is to replace the subsets with subspaces, and then solve the subspace version of the problem. If the dimension is small, then for almost all subsets A(x) we can do this reduction step easily, there are just a few cases, when \(A(x)+A(x)\) does not contain a sufficiently large subspace. However, even in these exceptional cases \(A(x)+A(x)\) turns out to be too large, so these cases can be excluded, as well. As the dimension increases, both the reduction step and both handling the all-subspace problem is getting more difficult. The 5-dimensional case is considerably more difficult than the previous cases, the proof of it is presented in the next section. Now, we continue with the proof of the cases \(1\le n\le 4\).
Proof of Theorem 3.1in the cases \(n\le 4\). According to Lemma
5.1 and Corollary
3.4 it suffices to show that
\(r_3'(1)\le 2,r_3'(2)\le 6,r_3'(3)\le 16,r_3'(4)\le 42\).
Case 1: \(n=1\). If the dimension is 1, then it is trivial that every 2-element subset of \({\mathbb {Z}}_4\) is 3AP-free and any three elements form a 3AP, so \(r_3({\mathbb {Z}}_4)=2\).
We continue with some general observations that are going to be used when the dimension is at least 2. Let us take a system of subsets \(A(x)(\subseteq {\mathbb {F}}_2^n)\) (indexed by elements \(x\in {\mathbb {F}}_2^n\)) satisfying \((*)\). For brevity let \(S=\sum _{x\in {\mathbb {F}}_2^n} |A(x)|\).
Case 2: \(n=2\).
Now, we continue with the case when the dimension is 2. If none of the subsets is empty, then all of them can have size at most 1, thus \(S\le 4\). Otherwise, by Observation 1 we can assume that every nonempty subset has size at most 2, thus \(S\le 6\), since there must be an empty set.
Case 3: \(n=3\).
If the dimension is 3, then let \(e_1,e_2,e_3\) be a basis for \({\mathbb {F}}_2^3\).
According to Observations 1-3 we can assume that all subsets have size at most 4 and every nonempty subset is a subspace (of dimension at most 2).
Let k denote the number of 2-subspaces and l the number of empty sets. If \(k=0\), then \(S\le 2\cdot 8=16\), and we are done. Note that in fact \(S<16\), since either all subsets have size at most 1 or at least one of them is empty.
So we can assume that \(k>0\). If \(A(x)=\langle u,v\rangle \) a 2-subspace, then \(A(x+u),A(x+v),A(x+u+v)\) are all empty, that is, we can assign an “empty triple” \(\{x+u,x+v,x+u+v\}\) to each 2-subspace. To different 2-subspaces we assign different triples, as the sum of the elements in the triple is x. That is, \(k\le \left( {\begin{array}{c}l\\ 3\end{array}}\right) \). We have \(S\le 4k+2(8-k-l)=16+2k-2l\le 16+2\left( {\begin{array}{c}l\\ 3\end{array}}\right) -2l\le 16\), if \(l\le 4\), equality holds if and only if \(l=4\). If \(5\le l\), then \(S\le 3\cdot 4= 12\). Therefore, \(S\le 16\) is shown and the maximum occurs when \(k=l=4\).
We continue with the 4-dimensional case.
Case 4: \(n=4\).
We will show that if the system of subsets \(\{ A(x)\subseteq {\mathbb {F}}_2^4\ |\ x\in {\mathbb {F}}_2^4 \}\) satisfies \((*)\), then \(\sum _{x\in {\mathbb {F}}_2^4} |A(x)|\le 42\).
At first it is going to be shown that “in most of the cases” it can be assumed that all the nonempty A(x) subsets are linear subspaces, then we will prove the statement for the special case when the non-empty A(x) subsets are all linear subspaces and finally we will also cover the remaining cases.
By Observations 1-3 we can assume that all subsets have size at most 8 and every nonempty subset of size at most 4 is a subspace (of dimension at most 2).
Let \(5\le |A(x)|\le 8\). As \(\dim \langle A(x) \rangle \ge 3\), we may choose three linearly independent vectors from A(x). Let these be \(f_1,f_2,f_3\) and let \(A'(x)=\langle f_1,f_2,f_3\rangle \). As \(0,f_1,f_2,f_3\in A(x)\), we have that \(\{0,f_1,f_2,f_3,f_1+f_2,f_1+f_3,f_2+f_3\}\subseteq A(x)+A(x)\), that is, \(A(x)+A(x)\) contains all the elements of the subspace \(\langle f_1,f_2,f_3 \rangle \), possibly with the exception of \(f_1+f_2+f_3\).
We claim that if there exists some \(0\ne g\in (A(x)\cap A'(x))\setminus \{f_1,f_2,f_3\}\), then \(A(x)+ A(x)\supseteq \langle f_1,f_2,f_3 \rangle \). To see this, we only need to show that \(f_1+f_2+f_3\in A(x){\hat{+}} A(x)\). However, either \(g=f_i+f_j\) (with some distinct \(i,j\in \{1,2,3\}\)) and \(f_1+f_2+f_3=g+f_k\) (where \(\{i,j,k\}=\{1,2,3\}\)) or \(g=f_1+f_2+f_3\) and \(f_1+f_2+f_3=g+0\) is a good representation. Therefore, in this case we can replace A(x) by \(\langle f_1,f_2,f_3 \rangle \). It remains to check the case when any four vectors in \(A(x)\setminus \{0\}\) are linearly independent.
Step 1. Assuming that A(x) is not a subspace, and any four vectors in \(A(x)\setminus \{0\}\) are linearly independent we prove \(S<42\) under the additional assumption that at most two subsets have size 8.
Without loss of generality it can be assumed that \(\{0,f_1,f_2,f_3,f_4\}\subseteq A(x)\), where \(f_1,f_2,f_3,f_4\) is a basis. The 3-subspaces spanned by three out of these basis vectors cover \({\mathbb {F}}_2^4\) with the exception of \(f_1+f_2+f_3+f_4\). That is, if \(|A(x)|\ne 5\), then \(A(x)=\{0,f_1,f_2,f_3,f_4,f_1+f_2+f_3+f_4\}\), but in this case \(A(x){\hat{+}}A(x)\supseteq A'(x){\hat{+}} A'(x)\) for \(A'(x)=\langle f_1,f_2,f_3 \rangle \), so we can replace A(x) by a larger set \(A'(x)\). So, it suffices to check the case when \(A(x)=\{0,f_1,f_2,f_3,f_4\}\). The system of subsets \(\{A(y)\ |\ y\in {\mathbb {F}}_2^4\}\) can be replaced by a “translate” of itself: \(\{A'(y)\ |\ y\in {\mathbb {F}}_2^4\}\) where \(A'(y)=A(y+c)\) for some fixed \(c\in {\mathbb {F}}_2^4\) (not depending on y). So by taking \(c=x\) we may suppose that \(A(0)=\{0,f_1,f_2,f_3,f_4\}\). Then \(|0+A(0){\hat{+}}A(0)|=10\), so at least 10 subsets are empty. The size of A(0) is 5 and the size of the other five (possibly) nonempty subsets is at most 8. If at least two out of these five subsets have size at most 5, then \(S\le 5+5+5+3\cdot 8=39<42\). If this does not hold, then at least four of them are of size 8. We will cover this case later: indeed, it is going to be shown that if at least three subsets are of size 8, then \(S<42\).
Step 2. From now on, we will assume that
-
either all the nonempty A(x) sets are linear subspaces of dimension at most 3, or
-
some of the subsets are of size 5 but there are at least three subsets of size 8,
and show that
\(S\le 42\) in these cases, too.
Let
h be the number of 3-subspaces. We distinguish 4 subcases.
-
Subcase 1 (\(h=0\)) In this case all of the subsets are of size at most 4. If \(A(x)=\langle u,v\rangle \) is a 2-dimensional subspace for some x, then \(A(x){\hat{+}}A(x)=\{u,v,u+v\}\), thus \(A(x+u),A(x+v)\) and \(A(x+u+v)\) are all empty. So for each 2-subspace A(x) we can assign an “empty triple”, since the subsets assigned to the elements of \(x+A(x){\hat{+}}A(x)\) are all empty. Moreover, the triple \(\{x+u,x+v,x+u+v\}\) determines x, since the sum of the vectors in the triple is x. Let k be the number of 2-subspaces and l be the number of empty subsets (among the A(x) sets). As empty triples can be assigned to the 2-subspaces by an injective mapping, we have \(k\le \left( {\begin{array}{c}l\\ 3\end{array}}\right) \).
Hence, \(S\le 4k+2(16-k-l)=32+2k-2l\le 32+2\left( {\begin{array}{c}l\\ 3\end{array}}\right) -2l\). If \(l\le 4\), then this yields \(S\le 32\). Moreover, for \(l=5\) we obtain that \(S\le 42\). If \(l\ge 6\), then \(S\le 10\cdot 4=40\).
In all cases we obtained that \(S\le 42\).
-
Subcase 2 (\(h=1\)) Let \(|A(0)|=8\). As \(|0+A(0){\hat{+}}A(0)|=7\), at least 7 subsets are empty and consequently \(S\le 8+(16-1-7)\cdot 4=40\).
-
Subcase 3 (\(h=2\)) Let A(u) and A(v) be the two 3-subspaces. Then \(U=u+A(u)+A(u)\) and \(V=v+A(v)+A(v)\) are 3-dimensional affine subspaces. If \(U\cap V=\emptyset \), then \(U\cup V={\mathbb {F}}_2^4\) and \(A(x)=\emptyset \) for all \(x\notin \{ u,v\}\), so \(S\le 2\cdot 8=16\). Otherwise, \(U\cap V\) is a 2-dimensional affine subspace, so \(|(U\cup V)\setminus \{u,v\}|=(16-4)-2=10\), that is, at least 10 subsets are empty. Then \(S\le 2\cdot 8+4\cdot 4=32\).
-
Subcase 4 (\(h\ge 3\)) Finally, let us assume that A(u), A(v), A(w) are 3-subspaces. Note that in this case it can happen that some of the nonempty subsets are not subspaces (these sets have size 5 and contain 5 affine independent vectors). According to Subcase 3, at least 10 subsets are empty. If at least 11 subsets are empty, then \(S\le 5\cdot 8=40\), and we are done. So it can be assumed that exactly 10 subsets are empty. Let \(U=u+A(u)+A(u),V=v+A(v)+A(v),W=w+A(w)+A(w)\). Since there are only 10 empty subsets, from the argument of Subcase 3 it follows that these are exactly the 10 subsets A(x) which are assigned to the 10 elements \(x\in (U\cup V)\setminus \{u,v\}\). However, \(U, V, U\cap V\) are all affine subspaces, so the sum of the vectors in U adds up to 0 and the same holds for V and \(U\cap V\). Thus the sum of the vectors in \(U\cup V\) is also 0. Hence, the sum of all vectors to which the empty set is assigned is \(u+v\). However, we can repeat this argument with U and W and get that the sum is also equal to \(u+w\), which is a contradiction. We are done.
\(\square \)
Proof of Theorem 3.19
We are going to use the implications of the previous proof.
When \(n=2\), one of the sets must be empty and all other sets must have size 2 in order to get 6 elements. If, say, \(A(x_0)=\emptyset \), then for any \(x\ne x_0\) the set A(x) must contain two elements whose difference is x. Two such configurations always can be mapped to each other in the required way.
When \(n=3\), then we need four empty sets and four 2-subspaces to get the total size of 16. Assume that \(A(x_1)=A(x_2)=A(x_3)=A(x_4)=\emptyset \). We claim that \(x_1,x_2,x_3,x_4\) are affine independent. Otherwise they form an affin 2-subspace, however, taking some \(x\notin \{x_1,x_2,x_3,x_4\}\) the affine 2-subspace \(x+A(x)+A(x)\) would have to contain exactly three of \(x_1,x_2,x_3,x_4\) (and x as the fourth element) which is impossible. Therefore, \(x_1,x_2,x_3,x_4\) are affine independent, and by some affine linear transformation \(\varphi \) these can be mapped to \(0,e_1,e_2,e_3\), for simplicity. Now, we can assume that 0 is contained in every nonempty A(x) (by suitable translations). Then it follows that \(A(e_i+e_j)=\langle e_i,e_j\rangle \), for \(1\le i<j\le 3\) and \(A(e_1+e_2+e_3)=\langle e_1+e_2,e_2+e_3\rangle \).
Finally, let \(n=4\). Note that \(S=42\) can hold only in Subcase 1 when \(k=10,l=5\).
From the proof it follows that \(S=42\) is possible only if there are exactly five empty sets, ten 2-subspaces and one 1-subspace. Moreover, if \(u_1,u_2,u_3,u_4,u_5\) are the vectors to which the empty set is assigned, then the 3-term sums made out of these 5 vectors have to be all distinct. Clearly, by applying a suitable affine linear transformation \(\varphi \) we can assume that \(u_1=0\) and \(u_2,u_3,u_4\) are linearly independent. If \(u_5\in \langle u_2,u_3,u_4\rangle \), then all the 10 triple sums lie in a 3-subspace, so they can not be all distinct. Thus \(u_2,u_3,u_4,u_5\) are linearly independent. Therefore, by renaming \(u_1,\dots ,u_5\) (if necessary), let \(A(0)=A(e_1)=A(e_2)=A(e_3)=A(e_4)=\emptyset \), where \(e_1,e_2,e_3,e_4\) is a basis. The set \(A(e_1+e_2+e_3+e_4)\) can not be a 2-subspace, since all vectors in it must have Hamming-weight at least 3 to satisfy \(e_1+e_2+e_3+e_4+A(e_1+e_2+e_3+e_4){\hat{+}}A(e_1+e_2+e_3+e_4) \subseteq \{0,e_1,e_2,e_3,e_4\}\). So it is the unique 1-subspace, for instance \(A(e_1+e_2+e_3+e_4)=\langle e_1+e_2+e_3+e_4 \rangle \) is an appropriate choice, but \(\langle e_i+e_j+e_k\rangle \) is also fine with any 3-subset \(\{i,j,k\}\) of \(\{1,2,3,4\}\). By permuting \(0,e_1,e_2,e_3,e_4\) with a suitable affine linear transformation we might assume that \(A(e_1+e_2+e_3+e_4)=\langle e_1+e_2+e_3+e_4 \rangle \).
The remaining 10 sets need to be 2-subspaces. For \(A(e_i+e_j)\) the unique appropriate choice is \(A(e_i+e_j)=\langle e_i,e_j\rangle \), with this choice \(e_i+e_j+A(e_i+e_j){\hat{+}}A(e_i+e_j)=\{0,e_i,e_j\}\) holds. For \(A(e_i+e_j+e_k)\) the unique appropriate choice is \(A(e_i+e_j+e_k)=\langle e_i+e_j,e_i+e_k \rangle =\{0,e_i+e_j,e_j+e_k,e_k+e_i\}\), with this choice \(e_i+e_j+e_k+A(e_i+e_j+e_k){\hat{+}}A(e_i+e_j+e_k)=\{e_i,e_j,e_k\}\) is satisfied. \(\square \)
7 Proof of \(r_3({\mathbb {Z}}^5_4)=124\)
We will show that if the system of subsets \(\{ A(x)\subseteq {\mathbb {F}}_2^5\ |\ x\in {\mathbb {F}}_2^5 \}\) satisfies \((*)\), then \(S{:}{=}\sum _{x\in {\mathbb {F}}_2^5} |A(x)|\le 124\).
Again, by Observations 1-3 we can assume that all subsets have size at most 16 and every nonempty subset of size at most 4 is a subspace (of dimension at most 2).
Now, let us assume that \(8<|A(x)|\le 16\). The set A(x) must contain at least 4 linearly independent vectors. (Note that by Observation 2 we have \(0\in A(x)\).)
Step 1. First, let us assume that a set A(x) with size \(8<|A(x)|\le 16\) spans a 4-dimensional subspace. Our aim is to show it can be assumed that A(x) itself is a 4-subspace.
Let \(f_1,f_2,f_3,f_4\in A(x)\) be linearly independent. Then \(A(x){\hat{+}}A(x)\) contains all the pairwise sums \(f_i+f_j\). If \(f_1+f_2+f_3+f_4\) also lies in A(x), then \(A(x)+A(x)=\langle f_1,f_2,f_3,f_4\rangle \), since the 3-term sums like \(f_1+f_2+f_3\) can be obtained as \((f_1+f_2+f_3+f_4)+f_4=f_1+f_2+f_3\) and \(f_1+f_2+f_3+f_4=(f_1+f_2+f_3+f_4)+0\in A(x){\hat{+}}A(x)\). Hence, if \(f_1+f_2+f_3+f_4\in A(x)\), then A(x) can be replaced by \(A'(x)=\langle f_1,f_2,f_3,f_4\rangle \).
Now, let us assume that \(f_1+f_2+f_3+f_4\notin A(x)\). Let us call the 2-term sums \(f_i+f_j\) (with \(i\ne j\)) pairs and the 3-term sums \(f_i+f_j+f_k\) (with i, j, k distinct) triples. The pair \(f_i+f_j\) can be identified with the set of indices \(\{i,j\}\), let us call this subset \(\{i,j\}\subseteq \{1,2,3,4\}\) also a pair, and similarly the 3-element subset \(\{i,j,k\}\) will be called a triple corresponding to the vector \(f_i+f_j+f_k\). As the size of A(x) is at least 9, the set A(x) must contain at least \((9-4-1=)4\) elements among the six pairs and four triples.
Now, we will prove that (at least) one of following cases holds:
(i)
A(x) contains two disjoint pairs: for instance \(f_1+f_2,f_3+f_4\in A(x)\),
(ii)
A(x) contains a pair and a triple such that their intersection has size 1: for instance: \(f_1+f_2\) and \(f_2+f_3+f_4\),
(iii)
A(x) contains all triples,
(iv)
A(x) contains a triple and all the three pairs contained in it: for instance: \(f_1+f_2+f_3,f_1+f_2,f_1+f_3,f_2+f_3\in A(x)\).
For the sake of contradiction let us assume that none of (i-iv) holds. Since we need at least four more vectors, at least one triple is contained in
A(
x), by symmetry we shall assume that
\(f_1+f_2+f_3\in A(x)\). Note that the pairs
\(f_1+f_4,f_2+f_4,f_3+f_4\) are not in
A(
x), since (ii) does not hold. Therefore, there must be (at least) one more triple in
A(
x), otherwise (iv) would hold. We may assume that
\(f_1+f_2+f_4\in A(x)\). Now, it follows that the pairs
\(f_1+f_3,f_2+f_3\) are not in
A(
x). However,
A(
x) must contain at least one pair, this pair can only be
\(f_1+f_2\) (since the other five pairs are already excluded). The two remaining triples (
\(f_1+f_3+f_4\) and
\(f_2+f_3+f_4\)) intersect the pair
\(f_1+f_2\) in a single element, so they are not contained in
A(
x) which contradicts that
A(
x) contains at least 4 elements from the 4 triples and 6 pairs.
Finally, we show that the equality \(A(x)+A(x)=\langle f_1,f_2,f_3,f_4\rangle \) holds in all of the four cases (i)-(iv).
In case (i) we have \(f_1+f_2+f_3+f_4=(f_1+f_2)+(f_3+f_4)\) and each triple contains either \(\{1,2\}\) or \(\{3,4\}\), thus they can be expressed like \(f_1+f_2+f_3=(f_1+f_2)+f_3\).
In case (ii) we have \(f_1+f_2+f_3+f_4=f_1+(f_2+f_3+f_4)\), the triples \(\{1,2,3\}\) and \(\{1,2,4\}\) can be obtained like \(f_1+f_2+f_3=(f_1+f_2)+f_3\), furthermore, \(f_2+f_3+f_4=0+(f_2+f_3+f_4)\) and \(f_1+f_3+f_4=(f_1+f_2)+(f_2+f_3+f_4)\), as all \(f_1,f_2,f_3,f_4\in A(x)\).
In case (iii) all the triples can be written like \(f_1+f_2+f_3=(f_1+f_2+f_3)+0\) and \(f_1+f_2+f_3+f_4=(f_1+f_2+f_3)+f_4\).
In case (iv) all the triples can be written like \(f_1+f_2+f_3=(f_1+f_2+f_3)+0\) or \((f_1+f_2+f_4)=(f_1+f_2)+f_4\) and \(f_1+f_2+f_3+f_4=(f_1+f_2+f_3)+f_4\).
Thus in all cases we get \(A(x)+A(x)=\langle f_1,f_2,f_3,f_4 \rangle \). Hence, if A(x) is a set of size at least 9 (and at most 16) such that A(x) is not a 4-subspace, then we can assume that \(\dim \langle A(x) \rangle =5\).
Step 2. We show that it can be assumed that there is no subset for which \(8<|A(x)|\le 16\) and \(\dim \langle A(x) \rangle =5\). Our aim is to show that A(x) can be replaced by a 4-subspace. Together with Step 1 this implies that we can assume that all sets having size larger than 8 are 4-subspaces. Moreover, we show that there can be at most one such subset.
Our aim is to show that either there is a 4-subspace \(A'(x)\) such that \(A'(x)\subseteq A(x)+A(x)\) or the total size S of the sets is at most 124.
Let us assume that \(0,f_1,f_2,f_3,f_4,f_5\in A(x)\), where \(f_1,\dots ,f_5\) is a basis. Then all singletons \(f_i\) and pairs \(f_i+f_j\) lie in \(A(x){\hat{+}}A(x)\). If a 4-term sum, like \(f_1+f_2+f_3+f_4\) lies in A(x), then \(A(x)+A(x)\) contains \(\langle f_1,f_2,f_3,f_4\rangle \) and we are done: A(x) can be replaced by \(\langle f_1,f_2,f_3,f_4\rangle \). More generally we can formulate the following observation:
Therefore,
\(f_1+f_2+f_3+f_4+f_5\notin A(x)\), since
\(\{f_1,f_2,f_3,f_4,f_5,f_1+f_2+f_3+f_4+f_5\}\) adds up to 0. Thus the remaining elements of
A(
x) are all pairs and triples. We claim that the following cases can be excluded with the help of Observation 4:
(i)
there are two disjoint pairs, e.g. \(f_1+f_2,f_3+f_4\in A(x)\)
(ii)
there are two triples intersecting each other in a single element, e.g. \(f_1+f_2+f_3,f_3+f_4+f_5\in A(x)\)
(iii)
there is a pair and a triple intersecting each other in a single element, e.g. \(f_1+f_2,f_2+f_3+f_4\in A(x)\)
-
In case (i) \(f_1+f_2+f_3+f_4+(f_1+f_2)+(f_3+f_4)=0\).
-
In case (ii) \((f_1+f_2+f_3)+(f_3+f_4+f_5)+f_1+f_2+f_4+f_5=0\).
-
In case (iii) \((f_1+f_2)+(f_2+f_3+f_4)+f_1+f_3+f_4+0=0\).
Finally, let us assume that (i-iii) do not hold. From (i) it follows that the pairs either form a star or a triangle. If they form a triangle, let us assume that it is
\(f_1+f_2,f_2+f_3,f_1+f_3\). Since
\(f_1+f_2+f_3\in A(x)\) would imply
\(\langle f_1,f_2,f_3,f_4\rangle \subseteq A(x)+A(x)\), we have
\(f_1+f_2+f_3\notin A(x)\). Furthermore, (iii) implies that none of the other triples is in
A(
x). Hence,
\(A(x)=\{0,f_1,f_2,f_3,f_4,f_5,f_1+f_2,f_2+f_3,f_1+f_3\}\), we will refer to this as case (a). From now on, we assume that the pairs in
A(
x) form a star.
If this star contains 4 vectors, e.g. \(f_1+f_2,f_1+f_3,f_1+f_4,f_1+f_5\in A(x)\), then A(x) can not contain any triples because of (iii). (Case (b).)
If this star contains 3 vectors, e.g. \(f_1+f_2,f_1+f_3,f_1+f_4\), then A(x) can not contain any triples because of (iii). (Case (c).)
If this star contains 2 vectors, e.g. \(f_1+f_2,f_1+f_3\). At least one triple must lie in A(x) and (iii) implies that this triple is \(f_1+f_2+f_3\). (Case (d).)
If only one pair is in A(x), e.g. \(f_1+f_2\in A(x)\). There are at least two more vectors (thus triples) in A(x). If one of them is \(f_3+f_4+f_5\), then the other triple intersects the pair \(\{1,2\}\) or the triple \(\{3,4,5\}\) in one element, contradicting (ii) or (iii). Thus, by (iii) these two triples must contain \(\{1,2\}\), which gives case (e).
If there are no pairs, then there are at least three triples. Any two of them have an intersection of size 2, giving case (f) or case (g).
We summarize this:
(a)
\(A(x)=\{0,f_1,f_2,f_3,f_4,f_5,f_1+f_2,f_2+f_3,f_1+f_3\}\)
(b)
\(A(x)=\{0,f_1,f_2,f_3,f_4,f_5,f_1+f_2,f_1+f_3,f_1+f_4,f_1+f_5\}\)
(c)
\(A(x)=\{0,f_1,f_2,f_3,f_4,f_5,f_1+f_2,f_1+f_3,f_1+f_4\}\)
(d)
\(A(x)=\{0,f_1,f_2,f_3,f_4,f_5,f_1+f_2,f_1+f_3,f_1+f_2+f_3\}\)
(e)
\(A(x)=\{0,f_1,f_2,f_3,f_4,f_5,f_1+f_2,f_1+f_2+f_3,f_1+f_2+f_4\}\)
(f)
\(A(x)=\{0,f_1,f_2,f_3,f_4,f_5,f_1+f_2+f_3,f_1+f_2+f_4,f_1+f_2+f_5\}\)
(g)
\(A(x)=\{0,f_1,f_2,f_3,f_4,f_5,f_1+f_2+f_3,f_1+f_2+f_4,f_1+f_3+f_4\}\)
Note that the size of
A(
x) is 10 in case (b) and 9 in the remaining cases (a) and (c-g). Also, the size of
\(A(x){\hat{+}}A(x)\) is 21 in cases (b), (c), (e), (f) and 22 in cases (a), (d), (g).
Let us assume that there is at least one subset A(x) having size at least 9 and not being a 4-subspace. Then at least 21 subsets out of the 32 sets A(y) are empty, so at most 11 subsets are non-empty. Let k denote the number of 4-subspaces among the subsets A(x). Then \(S=\sum |A(y)|\le 16k+10(11-k)=110+6k\). If \(k\le 2\), then this is at most 122. So let us assume that there are at least three 4-subspaces, namely, A(y), A(z), A(u). Let \(K=y+A(y), L=z+A(z), M=u+A(u)\), then K, L, M are affine subspaces of dimension 4.
If two of them are disjoint, for instance \(K\cap L=\emptyset \), then \(K\cup L={\mathbb {F}}_2^5\), giving that \(A(t)=\emptyset \) for every \(t\notin \{y,z\}\), which is a contradiction. So any two of them intersect nontrivially each other, and then any pairwise intersection is a 3-dimensional affine subspace. As \(y\notin L\cup M\), we have that \((K\cap L)\cap (K\cap M)\ne \emptyset \), since both of them is an 8-element subset of the 15-element set \(K\setminus \{y\}\), hence \(K\cap L\cap M\ne \emptyset \). Then \(K\cap L\cap M\) has size 4 or 8. By inclusion-exclusion principle, in both cases \(|K\cup L\cup M|=|K|+|L|+|M|-|K\cap L|-|K\cap M|-|L\cap M|+|K\cap L\cap M|\ge 28\), therefore, at least \(28-3=25\) subsets are empty and \(S\le 7\cdot 16=112\).
Therefore, it can be assumed that all subsets having at least 9 elements are 4-subspaces, moreover there are at most 2 such subsets. If there are 2 such subsets A(x) and A(y), then \(|A(x)\cup A(y)|=|A(x)|+|A(y)|-|A(x)\cap A(y)|\ge 16+16-8=24\), so at least \(24-2=22\) subsets are empty and \(S\le 2\cdot 16 + 8\cdot 8=96\). Hence, it can be assumed that there is at most one 4-subspace.
Step 3. Now we show that if \(|A(x)|\in [5,8]\), then it can be assumed that A(x) is either a 3-subspace or a set of 5 or 6 affine independent points.
Let us assume that \(4<|A(x)|\le 8\). If \(\langle A(x)\rangle \) has dimension 3, then A(x) can be replaced with this 3-subspace. If \(\dim \langle A(x)\rangle =4\), then it can be assumed that \(0,f_1,f_2,f_3,f_4\in A(x)\). If at least one more element is in A(x), then \(A(x)+A(x)\) contains a 3-subspace and we can replace A(x) by this 3-subspace, otherwise \(A(x)=\{0,f_1,f_2,f_3,f_4\}\), we will refer to this case as case (A).
If \(\dim \langle A(x)\rangle =5\), then it can be assumed that \(0,f_1,f_2,f_3,f_4,f_5\in A(x)\). If at least one more element with Hamming-weight at most 4 is in A(x), then \(A(x)+A(x)\) contains a 3-subspace. If \(f_1+f_2+f_3+f_4+f_5\in A(x)\), then \(\langle f_1+f_2,f_2+f_3,f_3+f_4\rangle \subseteq A(x)+A(x)\), otherwise \(A(x)=\{0,f_1,f_2,f_3,f_4,f_5\}\), we will refer to this case as case (B).
Hence, it can be assumed that if there is a subset
A(
x) (with size in [5, 8]) which is not a subspace, then it contains 5 or 6 affine independent points:
(A)
\(A(x)=\{0,f_1,f_2,f_3,f_4\}\)
(B)
\(A(x)=\{0,f_1,f_2,f_3,f_4,f_5\}\)
Note that the size of
A(
x) in these cases is either 5 or 6.
Step 4. We show that it can be assumed that all subsets have size at most 8.
Note that we have already seen (in Step 2) that there can be at most one 4-subspace, so let us assume that there exists a (unique) 4-subspace A(y). Then \(|A(y){\hat{+}}A(y)|=15\), so there are at least 15 empty subsets. All the other subsets are 3-subspaces or have size at most 6. If there is no 3-subspace, then \(S\le 16+16\cdot 6=112\), and we are done. Let A(x) be a 3-subspace and \(K=y+A(y),L=x+A(x)\). As \(|K\cap L|\le 4\), we have \(|K\cup L|\ge 16+8-4=20\), so there are at least \(20-2=18\) empty subsets, thus at most 14 non-empty ones implying \(S\le 16+13\cdot 8=120\), and we are done. Therefore, none of the subsets can be a 4-subspace, and consequently all the subsets have size at most 8.
Step 5. We show that it can be assumed that all nonempty subsets are subspaces of dimension at most 3 or a set of 5 or 6 affine independent points. Furthermore, the number of empty sets among the A(x) subsets is at most 16 and there exists a subset of size at least 5.
If \(0<|A(x)|\le 4\), then by Observations 1-3 it can be assumed that A(x) is a subspace.
Now, we can assume that all the subsets have size at most 8 and all those non-empty subsets that are not subspaces are of type (A) or (B).
If there are at least 17 empty subsets, then \(S\le 8\cdot 15=120\), so it can be assumed that at most 16 subsets are empty.
If there is no subset with size larger than 2, then \(S\le 64\). If there is no subset with size larger than 4, then there must be a subset with size 4 and there are at most 29 non-empty sets, so \(S\le 29\cdot 4=116\). So there is a subset of size at least five, this can be either of type (A) or (B) or a 3-subspace.
Now our aim is to show that we can assume that there is no subset of type (A) neither of type (B).
Step 6. We show that there is no subset of type (B).
Let us assume that there is a subset of type (B). Without loss of generality this is \(A(0)=\{0,e_1,e_2,e_3,e_4,e_5\}\). Then \(A(0){\hat{+}}A(0)=\{e_1,\dots ,e_5,e_1+e_2,\dots ,e_4+e_5\}{=}{:}T\), that is, \(A(0){\hat{+}}A(0)\) has size 15 and \(A(e_i)=\emptyset ,A(e_i+e_j)=\emptyset \) for every \(i\ne j\). As \(17\cdot 6=102=124-22\), at least 11 subsets are 3-subspaces. Let A(x) be a 3-subspace and \(K{:}{=}x+A(x)\). As \(A(0)\ne \emptyset \), we have \(0\notin K\). We claim that \(K\setminus \{x\} \not \subseteq T\).
For the sake of contradiction, let us assume the contrary. Let \(U=(e_1+e_2+e_3+e_4+e_5)^\perp \) and \({\overline{U}}={\mathbb {F}}_2^5\setminus U\). As \(|T\cap {\overline{U}}|=5\), the set \(K\cap {\overline{U}}\) can not be a 3-subspace. If \(K\cap {\overline{U}}\) is a 2-subspace, then without loss of generality, \(x=e_1+e_2+e_3\) and \(K\cap {\overline{U}}=\{e_1+e_2+e_3,e_1,e_2,e_3\}\). However, none of the translates of this set is contained in \(K\cap U\), thus we must have \(K\subseteq U\), which leads to a contradiction, as well.
Hence, there exists some \(y\notin T\) such that \(A(y)=\emptyset \), so the number of the empty subsets is at least 16. If the number of 3-subspaces is at most 14, then \(S\le 14\cdot 8+2\cdot 6=124\), and we are done. So we can suppose that the number of 3-subspaces is at least 15 and one subset has size 6. The set \(A(e_1+e_2+e_3+e_4+e_5)\) is not a 3-subspace, since any affine 3-subspace containing \(e_1+e_2+e_3+e_4+e_5\) contains at least 2 more elements that are not in T. Hence \(A(e_1+e_2+e_3+e_4+e_5)\) is the 16th empty subset. Now, we claim that \(A(e_1+e_2+e_3+e_4)\) is not a 3-subspace. This holds, since any affine 3-subspace containing \(e_1+e_2+e_3+e_4\) has at least one more element outside of \(T\cup \{e_1+e_2+e_3+e_4+e_5\}\).
Therefore, there is no subset of type (B).
Step 7. We show that there is no subset of type (A).
Let us assume that there is a subset of type (A), it can be assumed that it is \(A(0)=\{0,e_1,e_2,e_3,e_4\}\). Then \(|A(0)|=5\) and \(A(0){\hat{+}}A(0)=\{e_1,\dots ,e_4,e_1+e_2,\dots ,e_3+e_4\}\) has size 10. That is, we already have 10 empty subsets.
For brevity let us write
\(A(i_1i_2\dots i_l)\) for
\(A(e_{i_1}+e_{i_2}+\dots +e_{i_l})\) if
$$\begin{aligned} \{i_1,i_2,\dots , i_l\}\subseteq \{1,2,3,4,5\}. \end{aligned}$$
(E.g.
\(A(1)=A(e_1), A(123)=A(e_1+e_2+e_3)\), and so on.)
Let us assume first that the total size of the subsets
$$\begin{aligned} A(123),A(124),A(134),A(234),A(1234) \end{aligned}$$
is at most 32.
Consider the following 16 subsets:
\(A(z+e_5)\) (
\(z\in \langle e_1,e_2,e_3,e_4 \rangle \)). Let
k denote the number of 3-subspaces among these and
l the number of empty ones. If
\(S\ge 125\), then
\(\sum |A(z+e_5)|\ge 125-5-32=88\), thus
\(8k+5(16-k-l)\ge 88\), and then
$$\begin{aligned} 3k\ge 5l+8. \end{aligned}$$
(3)
If
\(A(z+e_5)\) is a 3-subspace, then
\(K_z=z+e_5+A(z+e_5)\) is an affine 3-subspace containing
\(z+e_5\). The 1-codimensional affine subspace
\(R=\{x:xe_5=1\}\) contains either all 8 elements of
\(K_z\) or 4 elements of
\(K_z\). In the first case we get 7 new empty subsets, so the total number of empty subsets is at least 17 and we are done:
\(S\le 15\cdot 8=120\). So for every 3-subspace
\(K_z\) exactly 4 elements of
\(K_z\) lie in
R. The sum of these 4 vectors is 0, so the sum of the three vectors in
\((K_z\cap R)\setminus \{z+e_5\}\) is
\(z+e_5\). Hence, for every 3-subspace
\(K_z\) we get an “empty triple” of vectors from
R, therefore,
$$\begin{aligned} \left( {\begin{array}{c}l\\ 3\end{array}}\right) \ge k. \end{aligned}$$
(4)
By (
3) and (
4) we obtain that
\(l(l-1)(l-2)/2\ge 5l+8\), which yields
\(l\ge 6\). Then (
3) implies that
\(k\ge 13\), which is a contradiction, since
\(6+13>16=|R|\).
Hence, it can be assumed that the total size of the sets
$$\begin{aligned}A(123),A(124),A(134),A(234),A(1234)\end{aligned}$$
is at least 33, on the other hand, it is clearly at most 40. It follows that none of them is empty and at least three of them are 3-subspaces, so we can assume that
A(123) is a 3-subspace.
\(A(123)\le \langle e_1,e_2,e_3,e_4\rangle \) is not possible, since then
\(e_1+e_2+e_3+A(123)\) would contain
\(e_1+e_2+e_4\) or
\(e_1+e_3+e_4\) or
\(e_2+e_3+e_4\) or
\(e_1+e_2+e_3+e_4\). Since, if an affine 3-subspace of
\(\langle e_1,e_2,e_3,e_4\rangle \) contains
\(e_1+e_2+e_3\) but none of the other 4 vectors, then it is
\(\langle e_1,e_2,e_3\rangle \), however,
\(\langle e_1,e_2,e_3\rangle \) contains 0, as well, contradiction.
So
\(e_1+e_2+e_3+A(123)\) intersects nontrivially
R, so
\(|(e_1+e_2+e_3+A(123))\cap R|=4\), thus at least 4 subsets (among subsets
A(
x) with
\(x\in R\)) are empty:
\(l\ge 4\). Note that that the sum of the four corresponding vectors is 0. Also, note that in this case (similarly to (
3) in the previous case) we shall assume that
$$\begin{aligned} 3k\ge 5l. \end{aligned}$$
(5)
Now (
5) yields that at least 7 such subsets are 3-subspaces:
\(k\ge 7\). Then (
4) implies that the number of empty ones is at least 5. Again, by (
5) we get
\(k\ge 9\). If
\(l=5\), then we have
\(\left( {\begin{array}{c}5\\ 3\end{array}}\right) =10\) triples, but there is a 4-term zero-sum, so 4 triples can not be “empty triples”, thus there is a 6th empty subset:
\(l\ge 6\), and by (
5) we obtain that
\(k\ge 10\). So
\(\sum |A(z+e_5)|=10\cdot 8=80\). As
\(125-5-80=40\), all the sets
A(123),
A(124),
A(134),
A(234),
A(1234) must be 3-subspaces. If
\(v\in \{e_1+e_2+e_3,e_1+e_2+e_4,e_1+e_3+e_4,e_2+e_3+e_4,e_1+e_2+e_3+e_4\}\), then
\(v+A(v)\) intersects
R in 4 vectors whose sum is 0. It can be checked that this set of 4 vectors can not be the same for all the 5 possible
v-s. (Otherwise
\({\mathbb {F}}_2^5\setminus R\) would contain at least 15 vectors to which the empty set is assigned, however, there are only 10 such vectors.) So there must be at least two such 4-element sets. Their intersection has size at least 2, since we have only 6 vectors in
R to which the empty set is assigned, and also at most 2, since otherwise they would be the same. Let
\(A(z_1+e_5),\dots ,A(z_6+e_5)\) be the empty ones, and let us assume that the two 4-zero-sum-sets are
\(\{z_{1},\dots ,z_4\}\) and
\(\{z_3,\dots ,z_6\}\). Then
\(z_1+z_2=z_3+z_4=z_5+z_6\). 20 triples can be chosen out of these 6 vectors, but just 8 of them can be “empty triples”, contradiction.
Therefore, we can assume that there is no subset of type (A), that is, all the nonempty subsets are subspaces of dimension at most 3. According to Step 5 there must be at least one 3-subspace among the subsets, as Steps 6-7 imply that all the sets of size at least 5 are 3-subspaces.
Step 8. We show that the number of empty subsets is at least 13.
Let \(1\le k\) be the number of 3-subspaces and l the number of empty subsets. Let us colour the elements of \({\mathbb {F}}_2^5\): x is coloured red if \(A(x)=\emptyset \) and x is coloured blue if A(x) is a 3-subspace. (If A(x) is a subspace of dimension at most 2, then x is not coloured.) Let \({\tilde{A}}(x)=x+A(x)\), specially, if x is blue, then \({\tilde{A}}(x)\) is a 3-dimensional affine subspace containing x and seven red vectors.
If \(125\le S\), then \(125\le 8k+(32-k-l)4\) which yields \(l\le k\). Now we are going to show that \(l\ge 13\). If x is blue, then in \({\tilde{A}}(x)\) there are two kinds of triples: the 2-subspace spanned by them either contains x or not. The number of triples in \({\tilde{A}}(x)\setminus \{x\}\) is 35 and 7 of these triples span a 2-subspace containing x. These triples are not contained in any other affine 3-subspace \({\tilde{A}}(y)\).
Furthermore, we claim that if \(l<13\), then a triple can appear in at most two 3-subspaces. For the sake of contradiction, let us assume that a triple is contained in \(K\cap L\cap M\), where \(K={\tilde{A}}(x), L={\tilde{A}}(y),M={\tilde{A}}(z)\) are 3-subspaces. Let H be the 2-subspace spanned by this triple, then \(H=K\cap L\cap M\) and \(K\setminus H\), \(L\setminus H\), \(M\setminus H\) are disjoint, thus \(|K\cup L\cup M|=16\). However, in \(K\cup L\cup M\) all the vectors are red except x, y, z, hence \(16-3=13\le l\), contradiction.
Now, since each triple appears in at most two 3-subspaces, we obtain that
$$\begin{aligned} 7l+\frac{28l}{2}\le 7k+\frac{28k}{2}\le \left( {\begin{array}{c}l\\ 3\end{array}}\right) , \end{aligned}$$
thus
$$\begin{aligned} 126\le (l-1)(l-2), \end{aligned}$$
implying that
\(l\ge 13\).
Therefore, \(k\ge l\ge 13\), as we claimed.
Step 9. We show that if A(x), A(y), A(z) are 3-subspaces (with distinct x, y, z), then \(A(x)\cap A(y)\cap A(z)\) is not an affine 2-subspace.
Now, for the sake of contradiction, assume that there are three 3-subspaces, A(x), A(y), A(z) whose intersection is an affine 2-subspace L. Without loss of generality we can assume that L is a linear (2-)subspace. Note that \({\tilde{A}}(x)=L\cup (L+x),{\tilde{A}}(y)=L\cup (L+y),{\tilde{A}}(z)=L\cup (L+z)\).
Note that
\({\mathbb {F}}_2^5\) can be partitioned into 8 translates of
L. Every affine 3-subspace contains the same number of vectors from those
L-translates that has a nonempty intersection with it. That is, given a 2-subspace
L, we can distinguish three types of affine 3-subspaces, we are going to say that a 3-subspace is of
-
type-1, if it contains 1-1 vector from each L-translate,
-
type-2, if it contains 2-2 vectors from four L-translates (and none from the remaining four L-translates),
-
type-4, if it contains 4-4 vectors from two L-translates (and none from the remaining six L-translates).
In
\(M=L\cup (L+x)\cup (L+y)\cup (L+z)\) there are 13 red elements, namely, all the vectors except
x,
y,
z. If
\(t\notin M\) is blue, then
\({\tilde{A}}(t)\) is a 3-subspace of type-1, type-2 or type-4 which contains
t and 7 seven red vectors.
If at least two L-translates do not contain any red vector, then the elements of these translates can not be blue, so \(k\le 11\), contradiction. Hence, there is at most one L-translate without any red vector. In particular, this means that \(l\ge 16\), since there are 13 red vectors in M and at least 3 red vectors outside of M.
Thus \(k=l=16\). Let us assume that the red vectors outside of M are \(v_1,v_2,v_3\), these vectors must be in different L-translates. Let \(L'=\{u_1,u_2,u_3,u_4\}\) be the unique L-translate not containing any red vector. If \(v_1+v_2+v_3\in L'\), then at most one of the \(A(u_i)\) sets can be a 3-subspace (namely, \(A(v_1+v_2+v_3)\)), contradiction. Now assume that \(v_1+v_2+v_3\notin L'\). By symmetry we can assume that \(v_1+v_2+v_3\notin L+x\) also holds. But then the union of the \({\tilde{A}}(u_i)=\langle u_i,v_1,v_2,v_3\rangle _{aff}\) sets (that are all affine 3-subspaces of type-1) cover \(L+x\) and the (unique) \(u_i\) for which \(x\in {\tilde{A}}(u_i)\) can not be blue (since x is not red). Hence, no three-wise intersection of 3-subspaces can be a 2-subspace.
Step 10. Now we know that \(13\le l\le k\) and no three-wise intersection of 3-subspaces is a 2-subspace. We finish the proof of the upper bound 124 by verifying the statement in these cases.
Let
N be the number of those pairs of 3-subspaces whose intersection is a 2-subspace. Then
$$\begin{aligned} 35k\le \left( {\begin{array}{c}l\\ 3\end{array}}\right) +4N, \end{aligned}$$
(6)
since each of the
k 3-subspaces contain 35 empty triples. Hence, for
\(l<16\) we have
\(N>0\), that is, two of the 3-subspaces assigned to blue vectors intersect each other in a 2-subspace. In the following subcases we always take two such subsets first.
Subcase 1. If \(l=13\), then we can assume that L is a linear 2-subspace and \({\tilde{A}}(x)=L\cup (L+x),{\tilde{A}}(y)=L\cup (L+y)\) are 3-subspaces corresponding to blue vectors x and y. At least 2 translates of L does not contain any red vector, and in these translates there can not be any blue vectors, either. So the number of blue vectors is at most \(32-13-8=11\), contradiction.
Subcase 2. If \(l=14\), then again let L be a linear 2-subspace and \({\tilde{A}}(x)=L\cup (L+x),{\tilde{A}}(y)=L\cup (L+y)\) be 3-subspaces corresponding to blue vectors x and y. Note that in \(L\cup (L+x)\cup (L+y)\) there are 10 red vectors. We have 4 more red vectors, say, \(v_1,v_2,v_3,v_4\), which must lie in different L-translates. (Otherwise there would be two L-translates without any red vector, which would imply that the 8 vectors in these translates are not coloured, contradicting that that the number of non-coloured vectors is at most 4.)
Note that all the 3-subspaces assigned to some blue vector different from x, y are of type-1 or type-2. To get a 3-subspace of type-2 we need to take 2-2 red vectors from \(L,L+x,L+y\). Moreover, these pairs must determine parallel vectors in these three L-translates (that is, in each pair the sum of the two vectors is the same), so there are at most 6 such subspaces. A type-1 3-subspace must correspond to a (blue) vector from the last L-translate, so there are at most 4 such subspaces. Hence \(k\le 4+6+2=12\), contradiction.
Subcase 3. Let us assume that \(l=15\). Again, we can assume that for some linear 2-subspace L the sets \(A(x)=L\cup (L+x),A(y)=L\cup (L+y)\) are two 3-subspaces. Let \(L_4,\dots ,L_8\) be the remaining five L-translates. They contain altogether 5 red vectors. If at least two of them do not contain any red vector, then in these two L-translates there aren’t any blue vectors either, so the number of blue vectors is at most 9, contradiction. So without the loss of generality it can be assumed that either (i) \(L_4\) contains two red vectors and \(L_5,L_6,L_7\) contain one-one red vector: \(v_i\) in \(L_i\) (\(5\le i\le 7\)) or (ii) \(L_4,\dots ,L_8\) contain one-one red vector: \(v_i\) in \(L_i\) (\(4\le i\le 8\)).
In case (i) let \(\alpha ,\beta \) be the two directions that are different from the direction determined by the two red vectors of \(L_4\). That is, \(\alpha \) and \(\beta \) are those two nonzero elements of L that are different from the sum of the two red vectors in \(L_4\). Let us consider the following 6 vectors in \(L_5,L_6,L_7\): \(v_i+\alpha ,v_i+\beta \) (for \(5\le i\le 7\)). If such a vector is blue, then the corresponding 3-subspace is of type-2, moreover, \(L_1,L_2,L_3\) contain one-one red pair of this 3-subspace, and in each pair the sum is the same, either \(\alpha \) or \(\beta \). There are only 4 such triples (of pairs of vectors) meaning that at least two of the vectors \(v_i+\alpha ,v_i+\beta \) (\(5\le i\le 7\)) are not blue. To get 15 blue vectors all vectors in \(L_8\) must be blue (as there are at most 2 non-coloured vectors). Note that the corresponding 3-subspaces must be of type-1. If \(v_5+v_6+v_7\in L_8\), then there can be at most one blue element in \(L_8\) (namely \(v_5+v_6+v_7\)). If \(v_5+v_6+v_7\notin L_8\), then by symmetry we can also assume that \(v_5+v_6+v_7\notin L_2\). If \(t\in L_8\) is blue, then the corresponding 3-subspace is \({\tilde{A}}(t)=\langle v_5,v_6,v_7,t \rangle _{aff}\), but these four 3-subspaces cover \(L_2\), which contradicts that \(L_2\) contains only 3 red vectors.
In case (ii) there are two 3-subspaces of type-4. To get a 3-subspace of type-2, we have to choose one-one red pair from \(L_1,L_2,L_3\) in such a way that these pairs determine parallel directions. This can be done in 6 ways, and every affine 3-subspace is determined by 6 points of it, so there are at most six 3-subspaces of type-2. To get a 3-subspace of type-1 we have to choose a red vector from all but one of the L-translates. First assume that no four-element subset of \(\{v_4,\dots ,v_8\}\) is a 2-subspace. Then the (at least) four red vectors chosen to be in this 3-subspace from \(\{v_4,\dots ,v_8\}\) determine uniquely a 3-subspace, so the number of 3-subspaces of type-1 is at most 5, thus \(k\le 2+6+5=13\), a contradiction. Now assume that a 4-element subset, say, \(\{v_4,v_5,v_6,v_7\}\) forms a 2-subspace. Each 3-subspace of type-1 contains at least 3 elements of \(\{v_4,v_5,v_6,v_7\}\), hence all of them contain all these four vectors. Then the blue vector is in \(L_8\setminus \{v_8\}\), so there are at most 3 such subspaces, thus, \(k\le 2+6+3=11\), a contradiction.
Subcase 4. Finally, let us assume that
\(l=k=16\), that is, all vectors are either red or blue. First we show that there are two 3-subspaces whose intersection is a 2-subspace. For the sake of contradiction, assume the contrary. Let
\(S_1,S_2,S_3,S_4\) be four 3-subspaces assigned to blue vectors. If every pairwise intersection has size less than 4 (that is, the intersection is either empty or has size 2), then
$$\begin{aligned} |S_1\cup S_2\cup S_3\cup S_4|\ge \sum |S_i|-\sum |S_i\cap S_j|\ge 4\cdot 8-6\cdot 2=20, \end{aligned}$$
(7)
so
\(S_1\cup S_2\cup S_3\cup S_4\) contains at least
\(20-4=16\) red vectors. Since there are only 16 red vectors, we must have equality in (
7), so each pairwise intersection has size 2 and each triple-intersection has size 0. Clearly, these hold for any four 3-subspaces assigned to blue vectors. Pick such a 3-subspace, for instance,
\(S_1\). Then the other fifteen 3-subspaces have to intersect
\(S_1\) in pairwise disjoint pairs, which is impossible. Therefore, there are two 3-subspaces whose intersection is a 2-subspace.
Hence, we can assume that this 2-subspace is a linear 2-subspace L and the sets \(A(x)=L\cup (L+x),A(y)=L\cup (L+y)\) are two 3-subspaces corresponding to blue vectors x and y. Let \(L_4,\dots ,L_8\) be the remaining five L-translates. These contain 6 more red vectors. As there can be at most one L-translate without any red vector, we can assume that the number of red vectors among them is i) 3-1-1-1-0 or ii) 2-2-1-1-0 or iii) 2-1-1-1-1.
In case (i) let \(v_5,v_6,v_7\) be the red vectors in \(L_5,L_6,L_7\). If \(v_5+v_6+v_7\in L_8\), then in \(L_8\) there is at most one blue vector (namely, \(v_5+v_6+v_7\)), contradiction. Assume that \(v_5+v_6+v_7\notin L_8\). We can assume that \(v_5+v_6+v_7\notin L_2\). If \(t\in L_8\) is blue, then \({\tilde{A}}(t)=\langle t,v_5,v_6,v_7\rangle _{aff}\), but these cover \(L_2\), which contradicts that \(L_2\) contains a blue element.
In case (ii) let us assume that the direction \(0\ne \alpha \in L\) is different from the direction(s) determined by the pairs in \(L_4,L_5\). Let \(v_6\in L_6,v_7\in L_7\) be the red vectors in these translates. Consider the blue vectors \(v_6+\alpha \) and \(v_7+\alpha \). The 3-subspaces corresponding to them are of type-2, and both of them contain one-one pair from \(L_1,L_2,L_3\), moreover, all these pairs determine direction \(\alpha \). In \(L_2\) and \(L_3\) these pairs are uniquely determined. In \(L_1\) there are two choices (two disjoint pairs). However, these two pairs in \(L_1\) together with the pairs from \(L_2\) and \(L_3\) determine two pairs in the same L-translate, which contradicts the existence of such a pair in both \(L_6\) and \(L_7\).
Finally, we consider case (iii). Let \(l_1=0,l_2=e_3,l_3=e_4,l_4=e_3+e_4,l_5=e_5,l_6=e_3+e_5,l_7=e_4+e_5,l_8=e_3+e_4+e_5\) and \(L=\langle e_1,e_2\rangle \). For every \(1\le i\le 8\) let \(L_i=L+l_i\). We can assume that \(L_1\) contains 4 red vectors and \(L_2,L_3\) contains 3-3 red vectors.
First assume that the L-translate containing 2 red vectors is \(L_4\), we can assume that these vectors are \(e_3+e_4\) and \(e_1+e_3+e_4\). Let t be a blue vector in one of the four L-translates \(L_5,\ldots ,L_8\). Then \({\tilde{A}}(t)\) is either of type-2 or type-1. However, only \(L_1,L_2,L_3,L_4\) contain at least two red vectors, which means that any 3-subspace of type-2 must contain at least 6 vectors from \(L_1\cup L_2\cup L_3\cup L_4\), which is a 4-subspace, thus the remaining two vectors of the 3-subspace must also lie in this subspace, too. So \({\tilde{A}}(t)\) is of type-1. As \(L_5\cup L_6\cup L_7\cup L_8\) is an affine 4-subspace, it intersects \({\tilde{A}}(t)\) in an affine 2-subspace. Therefore, if, say, \(t\in L_8\), then t and the red vectors from \(L_5,L_6,L_7\) form an affine 2-subspace, that is, t is the sum of these three red vectors. But then in \(L_8\) the only blue vector is t, contradiction.
Hence, \(L_4\) contains one red vector. By symmetry, we can assume that \(L_5\) contains 2 red vectors and these are \(e_5\) and \(e_1+e_5\). Let the red vector in \(L_i\) be \(l_i+t_i\) for \(i\in \{4,6,7,8\}\).
Let \(i\in \{6,7,8\}\). We claim that \({\tilde{A}}(l_i+t_i+e_2)\) and \({\tilde{A}}(l_i+t_i+e_1+e_2)\) must be of type-1. Otherwise, \({\tilde{A}}(l_i+t_i+e_2)\) or \({\tilde{A}}(l_i+t_i+e_1+e_2)\) would contain at least two vectors from \(L_5\cup L_6\cup L_7\cup L_8\), so it would have to contain two more red vectors from one of the L-translates \(L_5,L_6,L_7,L_8\), these could only be \(e_5\) and \(e_5+e_1\) from \(L_5\). But then the blue vector \(l_i+t_i+e_1\) would also lie in the 3-subspace (to get parallel pairs from the different translates), a contradiction. Hence, \({\tilde{A}}(l_i+t_i+e_2)\) and \({\tilde{A}}(l_i+t_i+e_1+e_2)\) are of type-1.
Consider
\({\tilde{A}}(l_6+t_6+e_2)\) and
\({\tilde{A}}(l_6+t_6+e_1+e_2)\). Each of these two subspaces contain either
\(e_5\) or
\(e_5+e_1\) and they contain
\(l_7+t_7\) and
\(l_8+t_8\). As the intersection of
\({\tilde{A}}(l_6+t_6+e_2)\cap {\tilde{A}}(l_6+t_6+e_1+e_2)\) with the 1-codimensional affine subspace
\(L_5\cup L_6 \cup L_7\cup L_8\) must be of size 2, they contain different elements from
\(L_5\). Without loss of generality we can assume that
\({\tilde{A}}(l_6+t_6+e_2)\) contains
\(e_5\). Then
\(e_5+(l_6+t_6+e_2)+(l_7+t_7)+(l_8+t_8)=0\), that is,
\(t_6+t_7+t_8=e_2\). Now
\({\tilde{A}}(l_6+t_6+e_2)\) and
\({\tilde{A}}(l_6+t_6+e_2+e_1)\) are determined, since they must contain
\(l_4+t_4\):
$$\begin{aligned}&{\tilde{A}}(l_6+t_6+e_2)\\&\quad = \{l_1+t_4+t_8,l_2+t_4+t_6+t_8+e_2,l_3+t_4+t_7+t_8,l_4+t_4,l_5,\\&\qquad l_6+t_6+e_2,l_7+t_7,l_8+t_8\},\\&{\tilde{A}}(l_6+t_6+e_2+e_1)\\&\quad =\{l_1+t_4+t_8+e_1,l_2+t_4+t_6+t_8+e_2 +e_1,l_3+t_4+t_7+t_8,l_4+t_4,\\&\qquad l_5+e_1,l_6+t_6+e_2+e_1,l_7+t_7,l_8+t_8\}. \end{aligned}$$
Similarly, the type-1 3-subspaces containing 2-2 blue vectors from
\(L_7\) and
\(L_8\) are:
$$\begin{aligned}&\{l_1+t_4+t_8,l_2+t_4+t_6+t_8,l_3+t_4+t_7+t_8+e_2,l_4+t_4,\\&\quad l_5,l_6+t_6,l_7+t_7+e_2,l_8+t_8\},\\&\{l_1+t_4+t_8,l_2+t_4+t_6+t_8,l_3+t_4+t_7+t_8+e_2+e_1,l_4+t_4,\\&\quad l_5+e_1,l_6+t_6,l_7+t_7+e_2+e_1,l_8+t_8\},\\&\{l_1+t_4+t_8+e_2,l_2+t_4+t_6+t_8+e_2,l_3+t_4+t_7+t_8+e_2,l_4+t_4,\\&\quad l_5,l_6+t_6,l_7+t_7,l_8+t_8+e_2\},\\&\{l_1+t_4+t_8+e_2+e_1,l_2+t_4+t_6+t_8+e_2+e_1,l_3+t_4+t_7+t_8+e_2+e_1,l_4+t_4,\\&\quad l_5+e_1,l_6+t_6,l_7+t_7,l_8+t_8+e_2+e_1\}. \end{aligned}$$
So the set of red vectors in
\(L_2\) is
\(\{l_2+t_4+t_6+t_8,l_2+t_4+t_6+t_8+e_2,l_2+t_4+t_6+t_8+e_2+e_1\}\) and in
\(L_3\) is
\(\{l_3+t_4+t_7+t_8,l_3+t_4+t_7+t_8+e_2,l_3+t_4+t_7+t_8+e_2+e_1\}\).
Now consider
\(l_8+t_8+e_1\) which is a blue vector in
\(L_8\). Note that
\({\tilde{A}}(l_8+t_8+e_1)\) is of type-2 (otherwise the three 3-subspaces corresponding to blue vectors from
\(L_8\) would have a 2-subspace intersection, contradicting Step 9). Also, it must contain
\(l_8+t_8\). As it contains at least 2 vectors from the 1-codimensional affine subspace
\(L_5\cup L_6\cup L_7 \cup L_8\), it must contain two more, which can only be
\(l_5,l_5+e_1\). The remaining two red pairs are in two of
\(L_1,L_2,L_3\). As
\(L_8=L_5+(e_3+e_4)\), these two
L-translates must be
\(L_2\) and
\(L_3\). Also, the difference of the vectors from the same
L-translate must be
\(e_1\), so the 3-subspace is:
$$\begin{aligned}&\{l_2+t_4+t_6+t_8+e_2,l_2+t_4+t_6+t_8+e_2+e_1,l_3+t_4+t_7\\&\quad +t_8 +e_2,l_3+t_4+t_7+t_8+e_2+e_1,\\&\quad l_5,l_5+e_1,l_8+t_8,l_8+t_8+e_1\} . \end{aligned}$$
As
\(\{l_2+t_4+t_6+t_8+e_2,l_2+t_4+t_6+t_8+e_2+e_1\}=\{l_5,l_5+e_1\} +e_5+e_3+t_4+t_6+t_8+e_2\), we get that
\(\{l_8+t_8,l_8+t_8+e_1\}+e_5+e_3+t_4+t_6+t_8+e_2=\{l_3+t_4+t_6 +e_2,l_3+t_4+t_6+e_2+e_1\}\) has to coincide with
\(\{l_3+t_4+t_7+t_8+e_2, l_3+t_4+t_7+t_8+e_2+e_1 \}\). However, this leads to
\(t_6+t_7+t_8\in \{0,e_1\}\), contradiction.