# 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.