Minimum number of maps such that their product is identically zero

Question

I have a problem that I translated into set theory notation as best I could: let $S=\{1,\dots,n\}$ and $C=\binom{S}{4}$, the set of 4-combinations from the set $S$, and let $\Pi=\{\pi:S\to\{-1,1\}\}$. Finally, define $\phi_{\pi}(\{s_{i_1},\dots,s_{i_4}\})=\sum\limits_{j=1}^4 \pi(s_{i_j})$. What is the minimum $m$ such that $\exists\pi_1,\dots,\pi_m\in\Pi:\prod\limits_{j=1}^m \phi_{\pi_j}$ is identically zero on $C$?

For example, if $n=8$, we can choose (abusing some notation) $\pi_1:(1,2,3,4,5,6,7,8)\to(1,-1,1,-1,1,-1,1,-1)$, $\pi_2:(1,2,3,4,5,6,7,8)\to(1,1,-1,-1,1,1,-1,-1)$, $\pi_3:(1,2,3,4,5,6,7,8)\to(1,-1,-1,1,1,-1,-1,1)$ and then $\prod\limits_{j=1}^3 \phi_{\pi_j}$ is identically zero.

This feels like the kind of question that would be studied, despite the notation-heavy construction of the question I've provided here. Is there any literature on this? We can replace 4 with any even $k$ for a more general question. The heart of the question is finding a minimum set of maps of a certain type that spans all the possible zeros.

Answer 1

I used the OPTMODEL procedure in SAS to solve an integer linear programming formulation of the set covering problem. Note the use of the BAND "bitwise and" function to extract the elements from each integer.

proc optmodel;
   num n = 8;
   num k = 4;
   set ELEMENTS = 0..n-1;
   set SUBSETS = 0..2^n-1;
   set ELEMENTS_s {s in SUBSETS} = {i in ELEMENTS: band(s,2^i)};
   set KSUBSETS = {s in SUBSETS: card(ELEMENTS_s[s]) = k};

   var Select {SUBSETS} binary;

   min NumSelected = sum {s in SUBSETS} Select[s];

   con Cover {t in KSUBSETS}:
      sum {s in SUBSETS: card(ELEMENTS_s[s] inter ELEMENTS_s[t]) = 2} Select[s] >= 1;

   solve;
   for {s in SUBSETS: Select[s].sol > 0.5} put ELEMENTS_s[s]=;
quit;

For $n=8$, the solver immediately returns an optimal solution with three subsets: $\{0,2,6,7\}, \{1,4,6,7\}, \{3,5,6,7\}$

For $n=11$, here's an optimal solution with five subsets: $\{1,5,7,10\}, \{0,1,4,6,8,10\}, \{1,2,3,9,10\}, \{0,1,5,6,7,9,10\}, \{1,4,5,7,8,9,10\}$

And another one with five subsets, each with five elements: $\{0,1,2,3,4\}, \{0,1,2,3,6\}, \{0,1,5,6,7\}, \{2,3,5,6,8\}, \{2,3,5,8,9\}, \{0,1,8,9,10\}$