Skip to main content
2 of 2
deleted 338 characters in body
Peter Taylor
  • 7.2k
  • 1
  • 21
  • 29

The optimal value for $k$ is $n$.

An example construction for $k = n$ is $W = [x_0, x_1, \ldots, x_{n-1}, x_0 + 1, x_1 + 1, \ldots, x_{n-1} + 1]$. Then the products which must be non-zero are $\prod_i (x_i + a_i)$ for all $\vec{a_i} \in \{0, 1\}^n$ and each is a sum of monomials containing at the very least $\prod_i x_i$.


To show that $k \le n$ it's convenient to work in an isomorphic ring. Stone's representation theorem for Boolean rings gives us the existence of a ring $K'$ isomorphic to $K$. The elements of $K'$ are subsets of $[2^n]$, the addition operation is symmetric difference, and the multiplication operation is intersection. An explicit construction can be given by placing the atoms of $K'$ in bijection with the set $\{ \prod_i (x_i + a_i) : a \in \{0,1\}^n \}$.

The construction of $W$ can be rephrased as two injective functions $w: [k] \to 2^{[2^n]}$ and $\overline{w}: [k] \to 2^{[2^n]}$ such that their images are disjoint and $\forall i \in [k]: w(i) \cap \overline{w}(i) = \emptyset$. Then the condition is that for every $S$ in the Cartesian product ${\large\times}_i \{w(i), \overline{w}(i)\}$ the intersection ${\large\cap} S \neq \emptyset$.

Let's break the Cartesian product down: let $P_j = \{ \cap s: s \in {\large\times}_{i \le j} \{w(i), \overline{w}(i)\} \}$, so that the condition is that $\emptyset \not\in P_k$. We prove by induction that $\min_{p \in P_j} |p| \le 2^{n-j}$.

  • Base case: $j=1$. Then $P_1 = \{w(1), \overline{w}(1)\}$. Since their intersection is empty, every element of $[2^n]$ is not in at least one of them, so $\min_{p \in P_j} |p| \le \frac12 2^n = 2^{n-1}$.
  • Inductive case. Let $q$ be an element of $P_{j-1}$ for which $|q| \le 2^{n-j+1}$. Either at least half of the elements of $q$ are not in $w(j)$ or at least half of them are not in $\overline{w}(j)$. Therefore at least one of $q \cap w(j)$ or $q \cap \overline{w}(j)$ meets the indicated threshold.

Therefore $P_{n+1}$ must contain $\emptyset$ and we require $k \le n$.

Peter Taylor
  • 7.2k
  • 1
  • 21
  • 29