Zero divisors in the boolean polynomial ring $\mathbb{F}_2[x_1,x_2,...,x_n]/(x_1^2-x_1,x_2^2-x_2,...x_n^2-x_n)$

Question

Related to this question.

Let $n$ be positive integer and let $K$ be the boolean polynomial ring $\mathbb{F}_2[x_1,x_2,...,x_n]/(x_1^2-x_1,x_2^2-x_2,...x_n^2-x_n)$.

For all $a$ in $K$ we have $a= -a$ and $a^2=a$ and $a(1+a)=0$.

All $a$ except $1$ are zero divisors with co-divisor $1+a$.

$|K|=2^{2^n}$ as confirmed in comments.

Let $W$ be a subset of $K$ and $|W|=2k$ for $k$ as large as possible.

$W$ must satisfy:

1. For $0 \le i \le k-1$ we have $W[i] \cdot W[i+k]=0$. If you prefer set $W[i+k]=1+W[i]$

2. For all $S \subset [0,2k-1]^k, |S|=k$ we have $\prod_{i \in S} W[i]=0$ iff there exist integer $m$ such that $m \in S$ and $m+k \in S$.

The if part directly follows from (1), but the only if part breaks our constructions so far.

Q1 How large $k$ can be in terms of $n$?

Q2 If the optimal bound is hard, what are bounds for $k$?

sage has implementation of $K$ Boolean Polynomials

Answer 1

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$.