# Symmetric boolean functions as Zhegalkin polynomials

Let $\mathbb{B} = \mathbb{Z}_2 = \{0, 1\}$ be the set of booleans. A symmetric boolean function in $n$ arguments is a function $f_S : \mathbb{B}^n \to \mathbb{B}$ that checks if the number of its true arguments is in $S$, i. e. a function $f_S$ such that

$$f_S(\alpha_1, \alpha_2, \ldots, \alpha_n) = \left(\sum_{1 \le i \le n}\alpha_{i}\right) \in S$$

or equivalently

$$f_S(\alpha_1, \alpha_2, \ldots, \alpha_n) = |\{ i : \alpha_i \}| \in S.$$

These functions are called symmetric boolean function because they are all the boolean function that do not depend on argument order.

The set of boolean numbers forms a field, conventionally denoted $GF(2)$, where multiplication is logical and ($\wedge$) and addition is exclusive or ($\oplus$). This field has the properties that $-\alpha = \alpha$, $\alpha / \beta = \alpha \wedge \beta$ (for all $\beta \neq 0$), $\alpha \oplus \alpha = 0$ and $\alpha \wedge \alpha = \alpha$ for all $\alpha$ in addition to the field properties. For convenience, I am going to write $\oplus$ as $+$ and leave out $\wedge$ in the next paragraphs. For example, I will write $\alpha \oplus \beta \oplus \alpha \wedge \beta$ as $\alpha + \beta + \alpha\beta$.

Every boolean function can be expressed as a polynomial over the field of boolean numbers. Such a polynomial is called a Zhegalkin polynomial, the representation is canonical, i. e. there is exactly one polynomial that represents a given boolean function. Here are some examples for boolean functions and their corresponding Zhegalkin polynomials:

• $\alpha \vee \beta = \alpha + \beta + \alpha\beta$
• $\alpha \wedge \neg\beta = \alpha + \alpha\beta$
• $(\alpha \to \beta) \oplus \gamma = 1 + \alpha + \gamma + \alpha\beta$
• $\neg(\alpha \wedge \beta) \vee \gamma = 1 + \alpha\beta + \alpha\beta\gamma$
• $f_{\{1, 4\}}(\alpha, \beta, \gamma, \delta) = \alpha + \beta + \gamma + \delta + \alpha\beta\gamma + \alpha\beta\delta + \alpha\gamma\delta + \beta\gamma\delta + \alpha\beta\gamma\delta$
where the triple terms $(\alpha\beta\gamma + \alpha\beta\delta + \alpha\gamma\delta + \beta\gamma\delta)$ are required because otherwise we would have $f(1,1,1,0) = 1$, and $3 \not\in \{1, 4\}$.

One observation we can make is that due to symmetry, the Zhegalkin polynomial for a symmetric boolean function always has the form

$$f_S(\alpha_1, \alpha_2, \ldots, \alpha_n) = \sum_{i \in T_{S,n}}t_{n,i}$$

where $\sum$ denotes summation with exclusive or and $t_{n, i}$ is the sum of all product terms that use $i$ out of the $n$ arguments to $f_S$ and $T_{S,n} \subseteq \{0, 1, \ldots, n\}$ is a set describing those $t_{n, i}$ we need to construct $f_S(\alpha_1, \alpha_2, \ldots, \alpha_n)$. Here are some examples for $t_{n, i}$ so you can get an idea what they look like:

• $t_{4, 1} = \alpha + \beta + \gamma + \delta$
• $t_{3, 2} = \alpha\beta + \alpha\gamma + \beta\gamma$
• $t_{4, 4} = \alpha\beta\gamma\delta$
• for all $n$: $t_{n, 0} = 1$

We can thus describe an $f_S$ in $n$ arguments completely by $n$ and $T_{S, n}$. Here are some test cases:

• $T_{\{1, 4\}, 4} = \{1, 3, 4\}$
• $T_{\{2, 3, 4\}, 4} = \{2, 4\}$
• $T_{\{2\}, 4} = \{2, 3\}$
• $T_{\{1, 2\}, 2} = \{1, 2\}$ (logical or)
• $T_{\{2, 3\}, 3} = \{2\}$ (median function)

The task in this challenge is to compute $T_{S, n}$ given $S$ and $n$. You can choose an appropriate input and output format as you like. This challenge is code-golf, the shortest solution in octets wins. As a special constraint, your solution must run in polynomial time $O(n^k)$ where $n$ is the $n$ from the input.

• I think T_{2, 3}, 3 should be {2}. Nov 5, 2015 at 3:37
• @alephalpha Of course. Nov 5, 2015 at 9:21
• @alephalpha: what about if x1=x2=x3=True? Then f{2}(x1,x2,x3) should be False, but sum(t_n,i), for i in {T_{2,3]}} = sum(t_n,i) for i in {2} = t_3,2 = x1 * x2 + x1 * x3 + x2 * x3 = T * T + T * T + T * T = T. Or am i misunderstanding the notation here? Nov 5, 2015 at 18:50
• @njnnja T_{2,3},3 describes f{2,3}(x1,x2,x3), not f{2}(x1,x2,x3). I hope this clears up your misunderstanding. Nov 5, 2015 at 18:54
• @PeterTaylor No. If α = β = γ = 1 and δ = 0 you would get 1 + 1 + 1 + 0 + 1∧1∧1∧0 = 1 which is wrong for f_{1, 4} as 3 is not in {1, 4}. I admit the description is a bit ambiguous: In the first paragraph (and only there), ∑ denotes a sum over integers, not over booleans. Nov 5, 2015 at 22:47

## Dyalog APL, 15 bytes

{2|⍺⌹⍉∘.!⍨0,⍳⍵}


Matrix division, basically. Takes input like 0 0 1 1 1 {2|⍺⌹⍉∘.!⍨0,⍳⍵} 4 for T4({2,3,4}).

{              }        Dyadic function:
⍵         Right argument          4
⍳          Index vector            1 2 3 4
0,           Append 0                0 1 2 3 4
∘.                Outer product           ——————————
⍨             |With itself              1 0 0 0
!               |By binomial coeff.       2 1 0 0
⍉                  Matrix transpose          3 3 1 0
Result at this step: ->   4 6 4 1
⍺                    Left argument
⌹                   Matrix division (A⌹B is A^-1 B, not A B^-1)
(implicitly converts ⍺ to column vector)
2|                     Modulo 2


Since the transposed matrix of binomial coefficients is lower triangular with determinant 1, its inverse will only contain integers. So to matrix-divide over F2 we can just matrix-divide over the reals, then mod by 2.

Matrix division is an O(n^3) operation, and calculating each of the O(N^2) binomial coefficients is well below O(n^3), so this runs in O(N^5).

Try it on TryAPL.

• Neato! I expected nothing less than this from APL. Nov 6, 2015 at 0:01

## CJam (25 24 bytes)

{_,{1$_,,2$~f&:!.*:^t}/}


This is an anonymous function which takes an array of 0 or 1 which serves as an indicator function for $S$ and returns an array of 0 or 1 which serves as an indicator function for $T$. E.g. to find $T_{\{1, 4\}, 4}$ you pass [0 1 0 0 1] and it returns [0 1 0 1 1].

Online demo

### Explanation

Recall that $t_{n,i}$ is the sum of all product terms that use $i$ out of the $n$ arguments to $f_S$. Suppose that $s$ of the $n$ arguments are true. Then we have three cases for $t_{n,i}(\alpha_0, \ldots, \alpha_{n-1})$:

• $i > s$ : none of the terms is true, so $t_{n, i}(\alpha_0, \ldots, \alpha_{n-1}) = 0$
• $i = s$ : exactly one of the terms is true, so $t_{n, i}(\alpha_0, \ldots, \alpha_{n-1}) = 1$
• $i < s$ : there are $\binom{s}{i}$ terms which are true, so $t_{n, i}(\alpha_0, \ldots, \alpha_{n-1}) = \binom{s}{i} \bmod 2$

If we let $\sigma$ be the indicator function for $S$ and $\tau$ be the indicator function for $T_{S, n})$, we therefore get the matrix identity

$$\begin{pmatrix}1 & 0 & 0 & \ldots & 0 \\ \binom{1}{0} & 1 & 0 & \ldots & 0 \\ \binom{2}{0} & \binom{2}{1} & 1 & \ldots & 0 \\ \vdots & \vdots & \vdots & \ddots & 0 \\ \binom{n}{0} & \binom{n}{1} & \binom{n}{2} & \ldots & 1 \end{pmatrix} \begin{pmatrix}\tau(0) \\ \tau(1) \\ \tau(2) \\ \vdots \\ \tau(n) \end{pmatrix} = \begin{pmatrix}\sigma(0) \\ \sigma(1) \\ \sigma(2) \\ \vdots \\ \sigma(n) \end{pmatrix}$$

which is dead easy to solve because the coefficient matrix is already in row-reduced echelon form.

Note that this is quite a well-known matrix, because it's the binomial coefficients modulo 2, which famously forms a Sierpiński triangle. I calculate them using Lucas' theorem and bit-twiddling as 2\$~f&:!

• Notice that all three cases can be reduced to the third. Nov 7, 2015 at 0:55
• Yes, and I'm implicitly relying on that when calculating the matrix, but from a didactic point of view I think it's preferable to split them up. Nov 7, 2015 at 7:42

# R, 115 bytes

function(S,n)which(abs(solve(sapply(1:n,function(k)(sapply(1:n,function(j)choose(j,k)%%2))),is.element(1:n,S)))==1)


The key is realizing that the sum of t's that evaluate to a T value is just the choose function. A slightly ungolfed version that doesn't calculate in polynomial time is below, but illustrates the derivation of the t's a little better (just run the middle line).

function(S,n)which(abs(solve(
sapply(1:n,function(k)(sapply(1:n,function(j)sum(apply(combn(c(rep(T,j),rep(F,max(0,k-j))),k),2,all))%%2))),
is.element(1:n,S)))==1)

• Are you sure choose(j,k) computes in polynomial time? I doubt that since the binomials grow exponentially. Nov 5, 2015 at 22:49
• The binomials grow exponentially in n, but the number of digits goes linearly. You mean polynomial time in n, not polynomial time in log n (size of input), right? Nov 5, 2015 at 23:04
• The golfed version does. The ungolfed version expands all the necessary combinations and is O(n!) (or worse, just guessing). But the golfed function uses the choose function, which is a closed formula =n!/(n-k)!k! which only requires 2 extra calculations when incrementing n by 1, and is therefore O(n^1). Note that we are looking at the binomial expansion in the ungolfed version; but in the golfed version we just multiply n integers together. I.e. g(n)=n! is not O(n!) complexity Nov 5, 2015 at 23:10
• @ThomasKwa Yeah, polynomial time in n, not in log n. Nov 5, 2015 at 23:57