Skip to main content
9 of 15
add some detail; mention [MR78].
BD107
  • 63
  • 2
  • 10

an upper-bound concerning affine hyperplanes and the "cubical lattice"

Fix a field $K$ 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})$, where $n$ is even. Fix an 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 kernel of the functional $A : (x_0, \ldots , x_{n - 1}) \mapsto x_1 + x_3 + \cdots + x_{n - 1}$. 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$.

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