Fix even $n$ and consider the boolean function $f : \{0, 1\}^n \rightarrow \{0, 1\}$, $f : (x\_0, \ldots , x\_{n - 1}) \mapsto (x\_0 \vee x\_1) \wedge (x\_2 \vee x\_3) \wedge \cdots \wedge (x\_{n - 2} \vee x\_{n - 1})$. Fix a field $K$ and any affine hyperplane $A \subset K^n$.


**Conjecture.** If $A \cap \{0, 1\}^n \subset f^{-1}(1)$, then $\left| A \cap \{0, 1\}^n \right| \leq 2^{\frac{n}{2}}$.


**Notes.**


* Because $\left| f^{-1}(1) \right| = 3^{\frac{n}{2}}$, the claimed bound on $\left| A \cap \{0, 1\}^n \right|$ is exponentially smaller than the *a priori* maximum.
* The claimed upper bound can easily be attained: indeed, set $K := \mathbb{F}\_p$ for $p > n$ (e.g.) and set $A$ as the hyperplane $x\_1 + x\_3 + \cdots + x\_{n - 1} = \frac{n}{2}$. It's easy to check that $A \cap \{0, 1\}^n \subset f^{-1}(1)$ and $\left| A \cap \{0, 1\}^n \right| = 2^{\frac{n}{2}}$. Thus the claim is that this is the best you can do.
* Viewed as a poset with the natural ordering inherited from $\{0, 1\}^n$, $f^{-1}(1)$ is exactly the $\frac{n}{2}$-dimensional "cubical lattice" of e.g. [Metropolis and Rota, 1978](https://www.jstor.org/stable/2100984) (i.e., the facets of the $\frac{n}{2}$-cube, ordered by inclusion). $2^{\frac{n}{2}}$ is exactly the number of *vertices* (minimal elements) of this lattice.
* The problem can also be phrased "dually" in terms of subset sums. It says that if an array of field elements $a\_0, \ldots , a\_{n - 1}, a$'s subset sums "lacks adjacent elements", in the sense that every $\{i\_0, \ldots , i\_{k - 1}\} \subset \{0, \ldots , n -1 \}$ such that $\sum\_{j = 0}^{k - 1} a\_{i\_j} = a$ also satisfies $\{2 j, 2 j + 1 \} \cap \{i\_0, \ldots , i\_{k - 1}\} \neq \emptyset$ for each $j \in \{0, \ldots , \frac{n}{2} - 1\}$, then there can be at most $2^{\frac{n}{2}}$ subsets $\{i\_0, \ldots , i\_{k - 1}\} \subset \{0, \ldots , n - 1\}$ such that $\sum\_{j = 0}^{k - 1} a\_{i\_j} = a$.
* The problem is related to certain Littlewood–Offord-type problems. Indeed, a [1993 paper of Griggs](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.104.5579&rep=rep1&type=pdf) shows that any $A$ with nonzero coefficients satisfies $A \cap \{0, 1\}^n \leq {n \choose \frac{n}{2}}$. Thus the goal is to instead assume that $A \cap \{0, 1\}^n \subset f^{-1}(1)$, and then again try to upper-bound the size of $A \cap \{0, 1\}^n$.
* The problem seems possibly related to the "Eventown" problem (see [Babai and Frankl](https://people.cs.uchicago.edu/%7Elaci/CLASS/HANDOUTS-COMB/BaFrNew.pdf), Ex. 2.3.11). That theorem states that if a family $\mathcal{F} = \{F\_0, \ldots , F\_{m - 1}\}$ of subsets of the powerset $\mathcal{P}(\{0, \ldots , n - 1\})$ satisfies $\left| F\_i \cap F\_j \right| \equiv 0 \pmod{2}$ for each $i, j \in \{0, \ldots , m - 1\}$, then $m \leq 2^{\frac{n}{2}}$. I have been unable to reduce the problem at hand to the Eventown problem.


**EDIT:** Thanks @Antoine Labelle for the nice answer in characteristic 2. I think the general case is much harder, so I will ideally wait for that before accepting.


I care most about the case $\mathbb{F}\_p$, for $p$ a "large" prime (say, in $p \in \{2^{n-1}, \ldots , 2^n - 1\}$), and that's what I have in mind for the bounty. **I believe** this should be true for any field!



a Littlewood–Offord-type problem concerning the "cubical lattice"
An asymptotic reformulation of this conjecture has now been solved by Diamond and Yehudayoff in the paper *Explicit Exponential Lower Bounds for Exact Hyperplane Covers*. Preprint is available [here](https://eccc.weizmann.ac.il/report/2021/148/). The sharp form of the conjecture is still open.


