Boolean functions

A Boolean Function with Small Degree and Many Variables

Recently, while working on a research project, I got on a tangent. From this tangent, I got on another tangent and that is what I want to write about today: a very nice Boolean function. This example got rediscovered several times for different reasons and, as I try to emphasize from time, I believe that things that are getting rediscovered many times must be of particular importance.

So let us define our Boolean function. I will give three very similar definitions throughout this post, but I will start with only one. Put {\ell(d) := 3 \cdot 2^{d-1} - 2}. Our Boolean function {F_d: \{ 0, 1\}^{\ell(d)} \rightarrow \{ 0, 1\}} is defined as follows: Put {F_1(x) = x} (as {\ell(1)=1}). For {d > 1}, write {x \in \{ 0, 1\}^{\ell(d)}} as {x=(s,t,y,z)} with {s,t \in \{ 0,1 \}} and {y, z \in \{ 0, 1\}^{\ell(d-1)}}. Then use this rule:

  • If {s=t=1}, then {F_d(1,1,y,z) = F_{d-1}(y)}.
  • If {s \neq t=0}, then {F_d(1,0,y,z) = F_{d-1}(z)}.
  • If {s= t = 0}, then {F_d(0,0,y,z) = 1-F_{d-1}(y)}.
  • If {s \neq t = 1}, then {F_d(0,1,y,z) = 1-F_{d-1}(z)}.

In the following, we list some properties of this function. Many of the concepts here are also discussed in an earlier post of mine.