Characterizing and counting boolean functions with all influences 1/2

Question

Is there a characterization of boolean functions $f:\{-1,1\}^n \longrightarrow \{-1,1\}$, so that $\mathbf{Inf_i}[f]=\frac{1} {2}$, for all $1\leq i\leq n$? Is it known how many such functions there are?

Answer 1

For a random function $f : \{-1,1\} \rightarrow \{-1,1\}$, we have that $\mathbf{Pr}[\mathbf{Inf}_i(f) = \frac12]$ is roughly $2^{-n/2}$; it's the probability that a binomial random variable with $2^{n-1}$ trials with success probability $\frac12$ has exactly $2^{n-2}$ successes. These events for $i = 1,2,\ldots,n$ don't seem too negatively correlated over a choice of random $f$, so heuristically you might expect that a $2^{-n^2/2}$ fraction or so of the $2^{2^n}$ Boolean functions satisfy your condition.

For something rigorous, I can tell you that there are at least $2^{2^{n/2}}$ such functions satisfying your condition. This is because the class of bent functions satisfy this condition. Let's think of Boolean functions as objects of the form $f : \mathbb{F}_2^n \rightarrow \mathbb{F}_2$, and take $n$ to be even. A Boolean function is a bent function if and only if $\mathbf{Pr}[f(x) \neq f(x+h)] = \frac12$ for all nonzero $h \in \mathbb{F}_2^n$. Your condition only requires this when $h$ is a standard basis vector, a vector in $\mathbb{F}_2^n$ with a single $1$.

The number of bent functions is quite a challenging open problem. It is known that there are at least $2^{2^{n/2}}$ functions in this class; this is the size of the class of Maiorana-McFarland bent functions (this links to the same page as above; the name Maiorana-McFarland is not given there). If I recall correctly, the number of bent functions is only known to be between $2^{2^{n/2+o(1)}}$ and $2^{2^{n-o(1)}}$.

Disclaimer: The links above are to Ryan O'Donnell's excellent book concerning analysis of Boolean functions (which seems like what you're interested in), although it is not the best resource on bent functions.

Answer 2

Here are some minor comments and a few counts LATER and a (rather weak) lower bound of $$4\binom{2^{n-1}}{2^{n-2}} \approx 2^{2^{n-1}-n/2}$$

Another way to say this is label the $2^n$ vertices of an $n$-cube so that in each of the $n$ directions exactly half (i.e. $2^{n-2}$ ) of the edges are labelled $0,1$ . So for $n=2$ We need three corners the same and one different giving $8$.

This is $(2^{n-1}-1)2^{n+1}$ which is all the possibilities $\sum_{i\in I} a_i \vee \sum_{j\in J} a_j$ mentioned by Bjorn (allowing some all or none of the variables to be replaced by their negations as well as negating the entire thing) .

For $n=3$ that would give $48$.There are actually $64$, $16$ each with two or six $1$'s and another $32$ with equally many $1$'s and $0$'s. The $16$ with two $1$'s is any pair not on a common edge (so $12$ on the same face and $4$ more antipodal pairs). The complements give the $16$ with $6$ $1$'S. With $4$ $1$'S the options are a vertex and the $3$ neighbors ($8$ ways) and a path of length $3$ not all on one face (so $1/2\cdot 8 \cdot 3 \cdot 2 \cdot 1=24$ ways)

For $n=4$ I come up with $4128.$ This is $2^{12}+2^5$ although I don't know how significant that is. These come out to be $228$ each with $4$ or $12$ $1$'S, $1152$ with $6$ or $10$ and $1368$ with equally many $0$'s and $1$'s.

At least $2^{n-2}$ vertices must be labelled $1$. This gives a valid function exactly when no two of those are adjacent. One (rather lazy) way to achieve this is to split the vertices in two in an alternating fashion (so one set would be those whose coordinates have even sum) and then from one class select half (i.e. $2^{n-2}$) of vertices to get the value $1$. Since we can choose either class AND we can take the complement, we get the count above of $$4\binom{2^{n-1}}{2^{n-2}} $$. Then $\binom{2t}{t} \approx \frac{2^{2t}}{\sqrt{\pi t}}$ gives the asymptotics.

Note that that

• The counts $2\binom{2^{n-1}}{2^{n-2}}$ enumerate for $n=2,3,4$ only $4,12$ and $140$ cases with the minimum number of $1$'s whereas we found actual counts of $8,32$ and $228.$

• The case of this few (or many) $1$'s is the marginal one. There seem many more possibilities with closer to an even split.

Answer 3

We are looking at functions where each variable has a 50% chance of mattering. Let $c_n$ be the number of such functions. I'll just prove that $4^n\le c_n$ (of course $c_n\le 2^{2^n}$) for $n\ge 3$. These will be non bent in contrast to KEW'S answer.

We start by working out the smallest values of $n$ to gain a grip on the question.

For $n=0$ there are $2$ (out of 2) such functions (no variable influences $\top$ and $\bot$, but there are no variables).

For $n=1$ there are $0$ (out of $4$) such functions (the variable $a$ has 0 influence on $\top$ and $\bot$ and 1 influence on $a$ and $\neg a$).

For $n=2$ there are $8$ (out of $16$) such functions. (Of the 16 there are 6 that only depend on 0 or 1 many variables. There are then eight "cognates of $a\vee b$", namely $$a\vee b,\quad\neg a\vee b,\quad a\vee\neg b,\quad\neg a\vee\neg b.$$ and their negations, that all have influence $1/2$ in each variable. And $a\leftrightarrow b$ and its negation, which have influence 1 in each variable.)

For $n=3$ there are somewhere between $16$ and $224$ out of $256$. For instance there are 16 that include some of the terms of $a+b+c+1$, and none of these qualify. Then there are $a\vee b\vee c$ and its 16 cognates, which don't qualify. But there is $$ \boxed{a\vee (b\leftrightarrow c)} $$ which does qualify.

For general $n$, at least you can take $a_1 \vee (a_2 + a_3 + \dots a_n)$ and its $2^{n+1}$ cognates. Moreover you can take $$ \sum_{i\in I} a_i \vee \sum_{j\in J} a_j $$ for an arbitrary partition $\{I,J\}$ of $\{1,\ldots,n\}$ where both $I\ne\varnothing\ne J$. To count the number of such partitions, note that for a fixed element, there are $2^{n-1}-1$ choices of which other elements are in the same partition as it (any subset of $[n-1]$ except the whole set).

For each such partition we may take cognates, giving a total of $(2^{n-1}-1)(2^{n+1})$.

Answer 4

I didn't really understand the original question, but from the comments of others you are looking for correlation-immune boolean functions of order 1. These go under many other names as well, including binary orthogonal arrays of strength 1 and balanced hypercube colourings. The last image is the simplest to understand: place equal weights at some vertices of a hypercube such that the centre of mass is at the centre of the hypercube. It can be generalised in multiple ways with extra parameters.

A complicated exact formula and a table of small values appeared in Palmer, Read and Robinson, J. Algebraic Combinatorics, 1 (1992) 257-273. Several people published on the asymptotics (including one Denisov who got the right answer and later incorrectly retracted it). My paper with Canfield, Gao, Greenhill and Robinson here gives the following: Let $q=q(n)$ be a function which is always an even integer in the interval $[0,2^{n-1}]$. Then the number of ways to place $2q$ equal weights on the vertices of a hypercube such that the centre of mass is at the centre of the hypercube is asymptotically $$ \binom{2^n}{2q} \left( \frac{\binom{2^{n-1}}{q}^2}{\binom{2^n}{2q}} \right)^n (1 + o(n^52^{-n/5})) $$ uniformly over $q$. For the sum over $q$, see Corollary 1.2 of the linked paper with $k=1$.

WITHDRAWN: Although I have answered an interesting question, it was not the question asked. Thanks to Seva for pointing this out.

Answer 5

Apparently such functions have been studied before, in cryptography. This condition is called the Strict Avalanche Criterion, and a guy called Daniel K. Biss proved a lower bound of $2^{2^{n-o(1)}}$.

http://ac.els-cdn.com/S0012365X97001805/1-s2.0-S0012365X97001805-main.pdf?_tid=5d5aa18e-fd17-11e3-91cc-00000aacb35e&acdnat=1403776434_39a67c01ad84f7a6f980f85a9c23ca91