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?

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s