2
$\begingroup$

Let $B = \{ 0, 1 \}$. For two points $\textbf{x}, \textbf{y} \in B^n$ we will write $\textbf{x} \preceq \textbf{y}$ iff $\textbf{x}_i \leq \textbf{y}_i$ for every $i \in \{ 1, \ldots, n \}$.

A boolean function $f: B^n \rightarrow B$ is called monotone if $f(\textbf{x}) \leq f(\textbf{y})$, whenever $\textbf{x} \preceq \textbf{y}$.

For a monotone boolean function $f: B^n \rightarrow B$ a point $\textbf{x} \in B^n$ is called a maximal zero of $f$, if $f(\textbf{x}) = 0$ and $f(\textbf{y}) = 1$ for every $\textbf{y}$ such that $\textbf{x} \prec \textbf{y}$. Similarly, $\textbf{x}$ is called a minimal one of $f$, if $f(\textbf{x}) = 1$ and $f(\textbf{y}) = 0$ for every $\textbf{y}$ such that $\textbf{y} \prec \textbf{x}$. A point $\textbf{x}$ is called an extremal point of $f$ if it is either maximal zero or minimal one of $f$.

If a monotone function $f: B^n \rightarrow B$ essentially depends on all its coordinates (variables), then $f$ has at least $n+1$ extremal points.

I'm wondering if there is a characterization of monotone boolean functions of $n$-variables (dependeing on all its variables) which have minimum possible number of extremal points, namely, $n+1$.

$\endgroup$

1 Answer 1

4
$\begingroup$

Lemma

The set of functions with the minimum number of extremal points is closed under fixing variables.

That is, if $f\colon B^n\to B$ essentially depends on $k$ variables and has exactly $k+1$ extremal points, then for each index $i$ and each $a\in\{0,1\}$, the function $f_{i\mapsto a}\colon B^n\to B$ defined by

$$f_{i\mapsto a}(\textbf x) = (x_1,\dots,x_{i-1},a,x_{i+1},\dots,x_n)$$

has exactly $k'+1$ extremal points, where $k'$ is the number of variables that $f_{i\mapsto a}$ essentially depends on.

Proof.

We will prove a stronger version of the $k+1$ lower bound, then finally examine the induction to see where the lower bound is attained. The induction hypothesis is that if $f$ depends on each variable in a set $S$, then there are at least $|S|+1$ extremal points $\mathbf x$ of $f$ that happen to "witness" $S$ in the sense that $x_i=f(\mathbf x)$ for some $i\in S$. For $|S|=1$ this is easy, and we invoke induction on $|S|$.

Pick any $i\in S$. Let $S_0$ and $S_1$, respectively, denote the set of variables in $S$ that $f_{i\mapsto 0}$ and $f_{i\mapsto 1}$ essentially depend on. There are two cases:

  1. $S_1\setminus S_0$ is non-empty.

    Note $|S_0\cup S_1|=|S|-1$. $f_{i\mapsto 0}$ has at least $|S_0|+1$ extremal points witnessing $S_0$, and $f_{i\mapsto 1}$ has at least $|S_1\setminus S_0|+1$ extremal points witnessing $S_1\setminus S_0$. These correspond as follows to distinct extremal points of $f$ witnessing $S$, giving at least $|S|+1$ in total. The extremal points of $f_{i\mapsto 0}$ give extremal points of $f$ by setting $x_i=0$, except for those maximal zeros where $x_i=1$ gives a larger zero. Similarly the extremal points of $f_{i\mapsto 1}$ give extremal points of $f$ by setting $x_i=1$, except for those minimal ones where $x_i=0$ gives a smaller one. The extremal points coming from $f_{i\mapsto 0}$ do NOT witness $S_1\setminus S_0$, so do not clash with the extremal points coming from $f_{i\mapsto 1}$.

  2. $S_1\subseteq S_0$.

    As in Case 1 we get $|S_0|+1$ extremal points witnessing $S_0$ coming from $f_{i\mapsto 0}$. All the minimal ones produced in this way have $x_i=0$. Since $f$ essentially depends on $i$, there is a minimal one $\mathbf x$ with $x_i=1$. In total this gives at least $|S_0|+2=|S|+1$ extremal points witnessing $S$.

In both cases we have shown that $f$ has at least $|S|+1$ extremal points witnessing $S$.

Finally, note that if $f$ has exactly $|S|+1$ extremal points, all the above inequalities must become equalities. So $f_{i\mapsto 0}$ has exactly $|S_0|+1$ extremal points, and by a similar argument $f_{i\mapsto 1}$ has exactly $|S_1|+1$ extremal points. This proves the Lemma by taking $S$ to be the set of all variables that $f$ essentially depends on.

Theorem

If $f\colon B^n\to B$ essentially depends on $k$ variables and has exactly $k+1$ extreme points then it is of the form

$$f(\textbf x)=R_1(x_{r(1)}, R_2(x_{r(2)}, \dots, R_{k-1}(x_{r(k-1)}, x_{r(k)})\dots))\tag{*}$$

where each operation $R_i$ is either AND or OR, and $1\leq r(1),\dots,r(k)\leq n$ are distinct indices.

Remark

Conversely any function of this form essentially depends on $k$ variables and has exactly $k+1$ extreme points.

Proof:

We will use induction on $k$. If $f$ has a zero of Hamming weight $n-1$, or a one of Hamming weight $1$, then we're done. For example if $f(0,1,\dots,1)=0$, then $f$ is of the form $\textrm{AND}(x_1,g(x_2,\dots,x_n))$. So we may assume $f(\mathbf x)=0$ for all $\mathbf x$ of Hamming weight 1, and $f(\mathbf x)=1$ for all $\mathbf x$ of Hamming weight $n-1$.

By the Lemma and induction, we can assume that every function of the form $f_{i\mapsto a}$ (with $f$ depending essentially on $i$) has a zero of Hamming weight $n-1$ or a one of Hamming weight $1$. The only way this can happen is for $f_{i\mapsto 1}$ to have a one of Hamming weight $1$, and $f_{i\mapsto 0}$ to have a zero of Hamming weight $n-1$.

So for each $i$ there exists $j$ such that $f(\mathbf x)=1$ where $x_i=x_j=1$ and $x_k=0$ for $k\notin\{i,j\}$. This gives at least $\lceil k/2\rceil$ ones of Hamming weight $2$. A similar argument gives at least $\lceil k/2\rceil$ zeroes of Hamming weight $n-2$. Because $2(\lceil k/2\rceil + 1)>k+1$, one of these inequalities must be an equality. Assume we have $\lceil k/2\rceil$ ones of Hamming weight $2$, and $\lfloor k/2\rfloor+1$ zeros of Hamming weight $n-2$. This is without loss of generality since we can replace $f$ by $1−f(1−x_1,\dots,1−x_n)$ if necessary.

If $k$ is even then, permuting variables if necessary, $f$ is of the form $$f(x_1,\dots,x_n)=(x_1\wedge x_2)\vee (x_3\wedge x_4)\vee\dots\vee(x_{k-1}\wedge x_k).$$ But this function has exactly $2^{k/2}$ minimal zeroes ($x_1\neq x_2$ etc), and $2^{k/2} > k/2+1$ for $k\geq 4$ (the $k=2$ case is obvious).

If $k$ is odd then, permuting variables if necessary, $f$ is of the form $$f(x_1,\dots,x_n)=(x_1\wedge x_2)\vee (x_3\wedge x_4)\vee\dots\vee(x_{k-2}\wedge x_{k-1})\vee(x_{k}\wedge x_{1}).$$ For $k=3$, by distributivity this is $x_1\wedge (x_2\vee x_3)$ which has a minimal zero of Hamming weight $1$. For $k\geq 5$ this function has exactly $2^{(k-1)/2}$ minimal zeroes, and $2^{(k-1)/2} > (k-1)/2+1$.

$\endgroup$
6
  • $\begingroup$ Thanks for the nice proof! Unfortunately, I don't see how to prove your assumption (it doesn't follow from my proof of lower bound). Do you know how to prove the assumption? $\endgroup$
    – Victor
    Commented Jul 26, 2017 at 16:07
  • 1
    $\begingroup$ @Victor: sorry, I don't know what I was thinking there. I found another argument which is a bit cleaner anyway. $\endgroup$
    – Dap
    Commented Aug 3, 2017 at 18:06
  • 1
    $\begingroup$ sorry, I have difficulties with understanding the updated arguments. Could you please clarify what does it mean to 'witness the empty set of variables'. Does every extremal point witness the empty set? For example, if we consider function $f = x_1 x_2 \lor x_1 x_3 \lor x_2 x_3 x_4$, then both projections on variable $x_4$ essentially depends on $x_1,x_2,x_3$, that is $S_0 = S_1 = \{ x_1, x_2, x_3\}$. It is not clear to me what extremal point would come from $f_{4 \mapsto 1}$. Function $f_{4 \mapsto 1}$ has several extremal points and $S_1 \setminus S_0$ is empty. $\endgroup$
    – Victor
    Commented Aug 11, 2017 at 20:04
  • $\begingroup$ @Victor: my apologies again. It was a mistake to talk about witnesses for $\emptyset$ - thanks for spotting this. I have added a separate case. That example $f$ would use the new Case 2, and add a minimal one such as $(0,1,1,1)$ to the extrema derived from $f_{4\mapsto 0}$. $\endgroup$
    – Dap
    Commented Aug 16, 2017 at 12:19
  • $\begingroup$ Thanks, Dap! I'm still a bit confused about Case 2. How do we guarantee that in Case 2 function $f_1$ has exactly $|S_1| + 1$ extremal points? $\endgroup$
    – Victor
    Commented Aug 20, 2017 at 5:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .