Emile Timothy

The parity function on $n$ inputs is defined as $\bigoplus\limits_n (x_1, ..., x_n) = x_1 \oplus ... \oplus x_n$. Here, $\oplus$ is the XOR function which is just the bitwise addition of bits modulo $2$. So, for instance: $$1 \oplus 1 = 0$$ $$0 \oplus 1 = 1$$ $$1 \oplus 0 = 1$$ $$0 \oplus 0 = 0$$ Back to topic, $\bigoplus\limits_n (x_1, ..., x_n)$ is basically the $\text{XOR}$ of the $n$ variables $x_1, ..., x_n$. Intuitively, it is $1$ if there are an odd number of $1$s in the inputs, and $0$ otherwise. Next, to introduce some notation, for any Boolean function $f$, let $L(f)$ denote the leaf-size of the smallest boolean formula consisting exclusively of its inputs $x_1, ..., x_n$ and the operations $\wedge, \vee, \neg$.

The purpose of this blog post is to portray a pretty cool result that the leaf-size of the parity function on $n$ inputs is $n^2$. It's really neat that the leaf-size of the parity function is quadratic in the size of inputs, and it's also quite unexpected. The following proof goes in stages. We first prove an upper bound on this result and then use the notion of formal complexity (through the Krapchenko function) to prove a lower bound to show that this quadratic result is tight.

Given that $\bigoplus\limits_n(x_1, x_2, ..., x_n) = x_1 \oplus ... \oplus x_n$ and $n = 2^k$, we can show that $L(\bigoplus_n) \leq n^2$ by mathematical induction on the power that $n$ is raised to.

Base Case: $k = 0 \Rightarrow n = 2^0 = 1$:

To show that $L(\bigoplus_1) \leq 1$, note that the leaf-size of the smallest formula that computes $\bigoplus_1$ is just $1$.

This is because the formula would just be composed of a single literal. Hence shown.

Assumptive Case: We now assume that this formula is true for $k < p$:

Therefore, $L(\bigoplus_{2k}) \leq 2^k$, $\forall k < p$ is now assumed to be true.

Inductive Case: To verify that the formula still holds true for $k = p$:

We need to show that $L(\bigoplus_{2^p}) \leq 2^p$. To do this, we note that $L(\bigoplus_{2^p}) = L(\bigoplus_{2^{p/2}} \oplus \bigoplus_{2^{p/2}})$. So, let

$$A = (x_1 \oplus ... \oplus x_p), \quad B = (x_{p+1} \oplus ... \oplus x_p)$$

Thus, $L(\bigoplus_{2^p}) = L(A\oplus B)$.

Since A and B are formulas of size $p$, we have that the leaf sizes of $A$ and $B$ are $\leq (\frac{p}{2})^2$ (by the assumptive case).

So, we can compute $A \oplus B$ through the following Boolean formula (which follows by definition):

$$A \oplus B = (A \wedge \neg B) \vee (\neg A \wedge B)$$

Then, since this computation involves four of these leaves, we have that $L(\bigoplus_{2^p}) = 4L(\bigoplus_{2^{p/2}}) \leq 4(\frac{p}{2})^2 \leq p^2$.

Conclusive Case: We know that if the formula is true for $n^k$, then it is true for $n^{k+1}$, for $k \in \{\mathbb{Z}_+ \cup 0\}$. From the base case, we know that it is true when $k = 0$ or $n = 1$. Hence, the inequality is true $\forall k, k \in \{\mathbb{Z}_+ \cup 0\}$.

Therefore, we conclude that $L(\bigoplus\limits_n)\leq n^2$, when $n$ is a power of 2.

Definition 1: Formal Complexity Measures:
A formal complexity measure (FC) is a function that maps Boolean functions on $n$ variables to the natural numbers $\mathbb{N}$, and satisfy the following properties:

$1)$ $FC(x_i) = 1$ for $1 \leq i \leq n$

$2)$ $FC(f) = FC(\neg f)$ for all $f$

$3)$ $FC(f \wedge g) \leq FC(f) + FC(g)$ for all $f, g$

We can show that $FC(f) \leq L(f)$ for optimal formulas in $f$ by using mathematical induction on $L(f)$. Note that

Base Case: $L(f) = 1$

𝐿(𝑓) = 1 implies that 𝑓 is a literal (a formula of size 0). By definition, we have that $𝐿(𝑥_1) = 1$.

Note then that from property 1, $𝐹𝐶(𝑥_1) = 1$ and by extension from property 2, $𝐹𝐶(¬𝑥_1) = 𝐹𝐶(𝑥_1) = 1$.

Therefore, for literals $𝐹𝐶(𝑓) = 𝐿(𝑓) = 1$, so $𝐹𝐶(𝑓) ≤ 𝐿(𝑓)$ is satisfied. This satisfies the base case.

Assumptive Case: Assume that $FC(f) \leq L(f)$ for optimal formulas for $f$.

Inductive Case: For Boolean functions that act on optimal formulas to form more complex formulas:

Given the previous assumption, we can now consider operations that act on optimal Boolean functions.

Note that we only need to consider ∧,∨ operations, since negations can be transferred down to the leaves.

In the leaves, the literal on the corresponding leaves is negated the appropriate number of times.

Therefore, for $\wedge$ operations that act on optimal formulas $A$ and $B$, let a Boolean function be $f = A \wedge B$.

Then, the leaf size of the full formula will be:

$$L(A \wedge B) = L(A) + L(B)$$

Since $FC(A) \leq L(A)$ and $FC(B) \leq L(B)$ from the assumptive case, we have:

$$L(A \wedge B) \geq FC(A) + FC(B)$$

From property 3, we have that $FC(A) + FC(B) = FC(A \wedge B)$. Therefore, for $\wedge$ operations,

$$L(A\wedge B) \geq FC(A\wedge B) \Rightarrow FC(f) \leq L(f)$$

Then, for $\vee$ operations that act on optimal formulas $A$ and $B$, let a Boolean function be $f = A \vee B$.

Then, using De Morgan’s law: $(A\vee B) = \neg(\neg A \wedge \neg B)$. So,

$$𝐹𝐶(𝐴 ∨ 𝐵) = 𝐹𝐶(¬(¬𝐴 ∧ ¬𝐵))$$ $$\text{From property 2: } 𝐹𝐶(¬(¬𝐴 ∧ ¬𝐵)) = 𝐹𝐶(¬𝐴 ∧ ¬𝐵) \Rightarrow 𝐹𝐶(𝐴 ∨ 𝐵) = 𝐹𝐶(¬𝐴 ∧ ¬𝐵)$$ $$\text{From property 3: } 𝐹𝐶(¬𝐴 ∧ ¬𝐵) = 𝐹𝐶(¬𝐴) + 𝐹𝐶(¬𝐵) \Rightarrow 𝐹𝐶(𝐴 ∨ 𝐵) = 𝐹𝐶(¬𝐴) + 𝐹𝐶(¬𝐵)$$ $$\text{From property 2: } 𝐹𝐶(¬𝐴) = 𝐹𝐶(𝐴), 𝐹𝐶(¬𝐵) = 𝐹𝐶(𝐵) \Rightarrow 𝐹𝐶(𝐴 ∨ 𝐵) = 𝐹𝐶(𝐴) + 𝐹𝐶(𝐵)$$

Then, from the assumptive case we have that:

$$𝐹𝐶(𝐴) ≤ 𝐿(𝐴), 𝐹𝐶(𝐵) ≤ 𝐿(𝐵)$$

Therefore, we have that:

$$𝐹𝐶(𝐴 ∨ 𝐵) ≤ 𝐿(𝐴) + 𝐿(𝐵)$$

Additionally, note that $L(A) + L(B) = L(A\vee B)$. Therefore,

$$𝐹𝐶(𝐴 ∨ 𝐵) ≤ 𝐿(𝐴 ∨ 𝐵) → 𝐹𝐶(𝑓) ≤ 𝐿(𝑓)$$

Thus, the inductive case is shown.

Therefore, we have now shown that $FC(f) \leq L(f)$ is true for Boolean functions that act on optimal expressions, provided that $FC(f) \leq L(f)$ is true for optimal expressions. Since we already know that the inequality is true for all literals (and their negations), it is then also true that for any optimal expression that builds on literals (every expression has some leaf-literals). Therefore, for every complexity measure $FC$, we have that $FC(f) \leq L(f)$.

Definition 2: Krapchenko Formal Complexity Measures: Let $A, B \subseteq \{0, 1\}^n$.
Let $H(A, B) = \{(a, b): a \in A, b \in B,$ and a and b differ in exactly 1 coordinate$\}$. Define $$ K(f) = \max\limits_{A \subseteq f^{-1}(1), B \subseteq f^{-1}(0)} \frac{|H(A, B)|^2}{|A||B|}$$

To show that K is a formal complexity measure, we need to show that for some arbitrary Boolean formula $f$, that each of the three properties defined in Definition 1 are valid.

Property 1: To show that $K(x_i) = 1, \forall i, 1 \leq i \leq n$

We show that when $f$ is a literal such that $f(x) = x_i$, then $K(f(x)) = K(x_i) = 1$. Then, define the following:

$$A = \{0^n\}, \quad B = \{0^{n-1}10^{i-1}\}$$

Since $A$ and $B$ differ in exactly $1$ coordinate by our construction of $A$ and $B$,

$$|𝐻(𝐴, 𝐵)| = |𝐴| = |𝐵| = 1$$ $$|𝐻(𝐴, 𝐵)|^2 ≤ |𝐴||𝐵|$$ $$K(x_i) = \max\limits_{A \subseteq x_i^{-1}(1), B\subseteq x_i^{-1}(0)} \frac{|H(A, B)|^2}{|A||B|} \leq 1 \quad \text{(an upper bound of 1)}$$

Additionally, for sets $A \subseteq f^{-1}(0), B\subseteq f^{-1}(1)$,

$$\frac{|𝐻(𝐴,𝐵)|}{|A|} \leq 1 \text{ and } \frac{|𝐻(𝐴,𝐵)|}{|B|} \leq 1$$ $$K(x_i) = \max\limits_{A \subseteq x_i^{-1}(1), B\subseteq x_i^{-1}(0)} \frac{|H(A, B)|^2}{|A||B|} \geq 1 \quad \text{(a lower bound of 1)}$$

Since we have that $K(x_i) \geq 1$ and $K(x_i) \leq 1$, we have that $K(x_i) = 1$.

Property 2: To show that $𝐾(𝑓) = 𝐾(¬𝑓)$:

Note that we can simply interchange A and B since the formula would not change:

$$K(f) = \max\limits_{A \subseteq f^{-1}(1), B \subseteq f^{-1}(0)} \frac{|H(A, B)|^2}{|A||B|} = \max\limits_{B \subseteq f^{-1}(1), A \subseteq f^{-1}(0)} \frac{|H(A, B)|^2}{|A||B|} = K(\neg f)$$

Therefore, negating the boolean formula would not change the output. Hence, $𝐾(𝑓) = 𝐾(¬𝑓)$.

Property 3: To show that $𝐾(𝑓 ∧ 𝑔) ≤ 𝐾(𝑓) + 𝐾(𝑔)$:

Let $A$ and $B$ be subsets maximizing the expression that defines $𝐾(𝑓 ∧ 𝑔)$.

Next, partition $𝐴$ into $𝐴_𝑓 ⊆ 𝑓^{−1}(1)$ and $𝐴_𝑔 ⊆ 𝑔^{−1}(1)$. Then,

$$𝐻 ( 𝐴 , 𝐵 ) = 𝐻 ( 𝐴_𝑓 , 𝐵 ) \cup 𝐻 ( 𝐴_𝑔 , 𝐵 )$$

Note that

$$\frac{|H(A_f, B_f)|^2}{|A_f||B_f|} \leq K(f), \quad \text{where }B_f \subseteq f^{-1}(0)$$ $$\frac{|H(A_g, B_g)|^2}{|A_g||B_g|} \leq K(g), \quad \text{where }B_g \subseteq g^{-1}(0)$$

Therefore, the onus of this proof is to show that:

$$K(f\wedge g) = \frac{|H(A_f, B_f) + H(A_g, B_g)|^2}{(|A_f| + |A_g|)|B|} \leq \frac{|H(A_f, B_f)|^2}{|A_f||B|} + \frac{|H(A_g, B_g)|^2}{|A_g||B|}$$

To show this, we try to reduce the above expression to a known statement:

$$\frac{|H(A_f, B_f) + H(A_g, B_g)|^2}{(|A_f| + |A_g|)|B|} \leq \frac{|H(A_f, B_f)|^2}{|A_f||B|} + \frac{|H(A_g, B_g)|^2}{|A_g||B|}$$

Multiplying both sides by $(|𝐴_𝑓| + |𝐴_𝑔|)|𝐴_𝑓||𝐴_𝑔||𝐵|$:

$$|𝐻(𝐴_f, 𝐵_f) + 𝐻(𝐴_g, 𝐵_g)|^2 |𝐴_f||𝐴_g| ≤ (|𝐴_f|+ |𝐴_g|)|𝐴_f|(|𝐻(𝐴_f,𝐵_f)|^2 +|𝐻(𝐴_g,𝐵_g)|^2|𝐴_f|)$$

Expanding the terms out:

$$(𝐻(𝐴_f,𝐵_f)^2|𝐴_f||𝐴_g|+𝐻(𝐴_g,𝐵_g)^2|𝐴_f||𝐴_g|+2𝐻(𝐴_f,𝐵_f)𝐻(𝐴_g,𝐵_g)|𝐴_f||𝐴_g|)$$ $$\leq |𝐻(𝐴_f ,𝐵-f )|^2|𝐴_f ||𝐴_f |+|𝐻(𝐴_f ,𝐵_f )|^2|𝐴_f ||𝐴_g |+|𝐻(𝐴_g ,𝐵_g )|^2|𝐴_g||𝐴_f| + |𝐻(𝐴_g,𝐵_g)|^2|𝐴_g||𝐴_g|$$

Subtracting congruent terms and taking everything to the RHS, we have:

$$0 ≤ |𝐻(𝐴_f ,𝐵_f )|^2|𝐴_f|2 +|𝐻(𝐴_g ,𝐵_g )|^2|𝐴_g|2 −2𝐻(𝐴_f ,𝐵_f )𝐻(𝐴_g ,𝐵_g )|𝐴_f ||𝐴_g |$$

Factorizing:

$$0 ≤ (|𝐻(𝐴_f , 𝐵_f )| |𝐴_f | − |𝐻(𝐴_g , 𝐵_g )| |𝐴_g | )^2$$

However, note that this is just the factorized form of $(𝑎 − 𝑏)^2 ≥ 0$, which is known to be true. Hence,

$$K(f\wedge g) = \frac{|H(A_f, B_f) + H(A_g, B_g)|^2}{(|A_f| + |A_g|)|B|}$$ $$\frac{|H(A_f, B_f)|^2}{|A_f||B|} + \frac{|H(A_g, B_g)|^2}{|A_g||B|}$$ $$≤ 𝐾(𝑓) + 𝐾(𝑔)$$ Since we have shown that $𝐾(𝑓)$ satisfies all $3$ properties of formal complexity measures, we have that $𝐾(𝑓)$ is a $FC$ measure.

Let $A \subseteq \bigoplus_n^{-1}(0), B \subseteq \bigoplus_n^{-1}(1) $.

It follows then that $∀𝑥$ s.t. $\bigoplus_n(𝑥) = 0$, all the $n$ neighbors will have parity $1$, and $∀𝑥 s.t. \bigoplus\limits_n(x) = 1$, all the $n$ neighbors will have parity $0$ in the Boolean formula. Therefore,
$$|𝐻(𝐴, 𝐵)| = \frac{𝑛(2^𝑛)}{2} = 2^{𝑛−1}𝑛$$

Additionally, we have that:

$$|𝐴| = |𝐵| = 2^{𝑛−1}$$

Therefore, from the Krapchenko’s formal complexity measure defined in part c, we have that:

$$𝐹𝐶(\bigoplus_n) = \frac{|𝐻(𝐴,𝐵)|^2}{|𝐴||𝐵|}$$ $$=\frac{(2^{𝑛−1}𝑛)^2}{(2^{n-1})^2} = \frac{2^{2n-2}n^2}{2^{2n-2}} $$ $$𝐹𝐶(\bigoplus\limits_𝑛)=n^2$$ However, from part b, we know that $$𝐹𝐶(\bigoplus_𝑛) ≤ 𝐿(\bigoplus_𝑛)$$

Then, substituting our result that $𝐹𝐶(\bigoplus_n) = 𝑛^2$ into the above inequality, we have that

$$𝐿 (\bigoplus_n) ≥ 𝑛^2 $$

Hence shown.

Combining Lemma 1 ($L(\bigoplus_n) \leq n^2$) and Lemma 4 ($L(\bigoplus_n) \geq n^2$) gives us the result that $L(\bigoplus_n) = n^2$.

Blog