Skip to main content
15 of 15
deleted 38 characters in body
BD107
  • 63
  • 2
  • 10

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

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!

BD107
  • 63
  • 2
  • 10