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}}$.


  • 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 (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 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, 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!

  • 1
    $\begingroup$ Interesting. Do you have a reference from the literature or is the problem original? $\endgroup$
    – kodlu
    May 29, 2021 at 20:26
  • 1
    $\begingroup$ it's an original problem; posed it myself, with some inspiration from a colleague as well. $\endgroup$
    – BD107
    May 29, 2021 at 22:16
  • 2
    $\begingroup$ Can you clarify the definition of the function? The title suggests that the three dots should be filled as $(\overline{x_0}\lor\overline{x_1})\land(\overline{x_1}\lor\overline{x_2})\land(\overline{x_2}\lor\overline{x_3})\land(\overline{x_3}\lor\overline{x_4})\land\dots$ (which is also the most obvious reading), but then the numbers don’t work out. Based on the “dual formulation”, do you actually mean $(\overline{x_0}\lor\overline{x_1})\land(\overline{x_2}\lor\overline{x_3})\land(\overline{x_4}\lor\overline{x_5})\land(\overline{x_6}\lor\overline{x_7})\land\dots$? $\endgroup$ May 31, 2021 at 14:06
  • $\begingroup$ you are absolutely correct, clarified. thanks. $\endgroup$
    – BD107
    May 31, 2021 at 14:08
  • $\begingroup$ Another phrasing would be that we define the $j$th excluded affine hyperplane $E_j = \{ (x_0, x_1, \ldots, x_n) \mid x_{2j} + x_{2j+1} = 2 \}$ and then the question becomes: "If $A \cap \{0,1\}^n \cap (\cup E_j) = \emptyset$, how big can $A \cap \{0,1\}^n$ be?" There must surely be some geometry tag which is at least as good a fit for the question as nt.number-theory? $\endgroup$ Jun 1, 2021 at 14:06

2 Answers 2


Here is a simple proof in the case when $K$ has characteristic $2$.

Let $m = \frac{n}{2}$. For $0\le i < m$, and $x\in K^n$, let $p_i(x)=(x_{2i},x_{2i+1})$.

I claim that for any fixed $0\le i < m$, $p_i(x)$ can take only $2$ possible values as $x$ runs through $A\cap \{0,1\}^n$ (this clearly gives the desired bound $|A\cap \{0,1\}^n|\le 2^m$). By assumption, $p_i(x)\ne (0,0)$. Suppose, for the sake of contradiction, that there exists $x,y,z \in A\cap \{0,1\}^n$ such that

  • $p_i(x)=(1,1)$
  • $p_i(y)=(0,1)$
  • $p_i(z)=(1,0)$

Then $y+z-x\in A$ since $A$ is an affine subspace, $y+z-x\in \{0,1\}^n$ since $K$ has characteristic $2$ and $p_i(y+z-x)=p_i(y)+p_i(z)-p_i(x)=(0,0)$, which is a contradiction.

In other characteristics, the argument doesn't quite work since $y+z-x$ doesn't need to be in $\{0,1\}^n$ anymore, but maybe a variation of the idea could work.

  • $\begingroup$ $y+z-x\in \{0,1\}^n$ does not assume that $A$ contains zero in characteristic 2, it follows from $\{0,1\}^n$ being an $\mathbb{F}_2$ subspace (if $A$ contains zero then my argument works in any characteristic actually but that's not needed for characteristic 2). $\endgroup$ Jun 2, 2021 at 12:57
  • $\begingroup$ Even in arbitrary characteristic, it's not enough to assume that $A$ contains 0, because you still have to worry about whether $y + z - x \in \{0, 1\}^n$ or not (as you point out). $\endgroup$
    – BD107
    Jun 2, 2021 at 13:01
  • $\begingroup$ Yeah you're right so that really only works for characteristic 2. I think that the main claim in my proof is actually false in other characteristics. $\endgroup$ Jun 2, 2021 at 13:04
  • $\begingroup$ Yeah, for example, consider the affine subspace of $\mathbb{Q}^4$ satisfying $x_0 + x_1 + x_2 + x_3 = 1$. In that setting both $p_0$ and $p_1$ take on all 3 values. Yet it remains true that $A \cap \{0, 1\} \subset f^{-1}(1)$. $\endgroup$
    – BD107
    Jun 2, 2021 at 13:07
  • 1
    $\begingroup$ @BD107 Actually the new version of the answer looks even nicer $\endgroup$ Aug 14, 2021 at 14:13

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. The sharp form of the conjecture is still open.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.