# Some remarks on monotone Boolean functions

This post summarizes some joint research with Charles Celerier, Caroline Melles, and David Phillips.

Let $f:GF(2)^n \to GF(2)$ be a Boolean function. (We identify $GF(2)$ with either the real numbers $\{0,1\}$ or the binary field ${\mathbb{Z}}/2{\mathbb{Z}}$. Hopefully, the context makes it clear which one is used.)

Define a partial order $\leq$ on $GF(2)^n$ as follows: for each $v,w\in GF(2)^n$, we say $v\leq w$ whenever we have $v_1 \leq w_1$, $v_2 \leq w_2$, …, $v_n \leq w_n$. A Boolean function is called monotone (increasing) if whenever we have $v\leq w$ then we also have $f(v) \leq f(w)$.

Note that if $f$ and $g$ are monotone then (a) $f+g+fg$ is also monotone, and (b) $\overline{\Omega_f}\cap \overline{\Omega_g}=\overline{\Omega_{fg}}$. (Overline means bit-wise complement.)

Definition:
Let $f:GF(2)^n \to GF(2)$ be any monotone function. We say that $\Gamma\subset GF(2)^n$ is the least support of $f$ if $\Gamma$ consists of all vectors in $\Omega_f$ which are smallest in the partial ordering $\leq$ on $GF(2)^n$. We say a subset $S$ of $GF(2)^n$ is admissible if for all $x,y\in S$, ${\rm supp}(x)\not\subset {\rm supp}(y)$ and ${\rm supp}(y)\not\subset {\rm supp}(x)$

Monotone functions on $GF(2)^n$ are in a natural one-to-one correspondence with the collection of admissible sets.

Example:
Here is an example of a monotone function whose least support vectors are given by
$\Gamma =\{ (1,0,0,0), (0,1,1,0), (0,1,0,1), (0,0,1,1) \} \subset GF(2)^n,$
illustrated in the figure below.

The algebraic normal form is $x_0x_1x_2 + x_0x_1x_3 + x_0x_2x_3 + x_1x_2 + x_1x_3 + x_2x_3 + x_0$.

The following result is due to Charles Celerier.

Theorem:
Let $f$ be a monotone function whose least support vectors are given by $\Gamma \subset GF(2)^n$. Then
$f(x) = 1+\prod_{v\in\Gamma} (x^v+1).$

The following example is due to Caroline Melles.

Example:
Let $f$ be the monotone function whose least support is
$\Gamma = \{ (1,1,1,1,0,0),(1,1,0,0,1,1),(0,0,1,1,1,1)\}.$
Using the Theorem above, we obtain the compact algebraic form
$f(x_0,x_1,x_2,x_3,x_4,x_5) = x_0x_1x_2x_3 + x_0x_1x_4x_5 + x_2x_3x_4x_5 .$
This function is monotone yet has no vanishing Walsh-Hadamard transform values. To see this, we attach the file afsr.sage available from Celerier (https://github.com/celerier/oslo/), then run the following commands.

sage: V = GF(2)^(6)
sage: L = [V([1,1,0,0,1,1]),V([0,0,1,1,1,1]), V([1,1,1,1,0,0])]
sage: f = monotone_from_support(L)
sage: is_monotone(f)
True


These commands simply construct a Boolean function $f$ whose least support are the vectors in L. Next, we compute the Walsh-Hadamard transform of this using both the method built into Sage’s sage.crypto module, and the function in afsr.sage.

sage: f.walsh_hadamard_transform()
(-44, -12, -12, 12, -12, 4, 4, -4, -12, 4, 4, -4, 12, -4, -4, 4, -12, 4, 4, -4, 4, 4, 4, -4, 4, 4, 4, -4, -4,
-4, -4, 4, -12, 4, 4, -4, 4, 4, 4, -4, 4, 4, 4, -4, -4, -4, -4, 4, 12, -4, -4, 4, -4, -4, -4, 4, -4, -4, -4, 4, 4, 4, 4, -4)
sage: f.algebraic_normal_form()
x0*x1*x2*x3 + x0*x1*x4*x5 + x2*x3*x4*x5
sage: x0,x1,x2,x3,x4,x5 = var("x0,x1,x2,x3,x4,x5")
sage: g = x0*x1*x2*x3 + x0*x1*x4*x5 + x2*x3*x4*x5
sage: Omega = [v for v in V if g(x0=v[0], x1=v[1], x2=v[2], x3=v[3],
x4=v[4], x5=v[5])0]
sage: len(Omega)
10
sage: g = lambda x: x[0]*x[1]*x[2]*x[3] + x[0]*x[1]*x[4]*x[5] + x[2]*x[3]*x[4]*x[5]
sage: [walsh_transform(g,a) for a in V]
[44, 12, 12, -12, 12, -4, -4, 4, 12, -4, -4, 4, -12, 4, 4, -4, 12, -4, -4, 4, -4, -4, -4, 4, -4, -4, -4, 4, 4,
4, 4, -4, 12, -4, -4, 4, -4, -4, -4, 4, -4, -4, -4, 4, 4, 4, 4, -4, -12, 4, 4, -4, 4, 4, 4, -4, 4, 4, 4, -4, -4, -4, -4, 4]


(Note: the Walsh transform method in the BooleanFunction class in Sage differs by a sign from the standard definition.) This verifies that there are no values of the Walsh-Hadamard transform which are $0$.

More details can be found in the paper listed here. I end with two questions (which I think should be answered “no”).

Question: Are there any monotone functions $f$ of $n$ variables having no free variables of degree $\leq n/2$?

Question: Are there any monotone functions $f$ of most than two variables which are bent?