a Littlewood–Offord-type problem concerning the "cubical lattice"

Question

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

Answer 1

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.

Answer 2

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.