Skip to main content
8 of 15
added an edit regarding Antoine Labelle's answer.
BD107
  • 63
  • 2
  • 10

hyperplanes whose intersection with $\{0, 1\}^n$ is contained in the on-set of the Achilles heel function

Fix a field $K$ and consider the boolean function $f : \{0, 1\}^n \rightarrow \{0, 1\}$, $f : (x_0, \ldots , x_{n - 1}) \mapsto (\overline{x_0} \vee \overline{x_1}) \wedge (\overline{x_2} \vee \overline{x_3}) \wedge \cdots \wedge (\overline{x_{n - 2}} \vee \overline{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 much smaller than the a priori maximum.
  • The claimed upper bound can easily be attained: indeed, set $K := \mathbb{Q}$ (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.
  • 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 \} \not \subset \{i_0, \ldots , i_{k - 1}\}$ 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.

In fact, it would be nice to have an answer of the following form: for any subset $S \subset f^{-1}(1)$ of cardinality $|S| > 2^{\frac{n}{2}}$, there is an affine $\mathbb{Z}$-linear combination of $S$'s elements (i.e., with coefficients adding to 1) which is in $f^{-1}(0)$; i.e., $\sum_{i = 0}^{|S| - 1} \alpha_i \cdot s_i \in f^{-1}(0)$. This is like Antoine's approach but with coefficients in $\mathbb{Z}$; and thus would imply the result for any field it seems?

BD107
  • 63
  • 2
  • 10