Boolean algebra/ring: Compute product of sum of combinations of variables

Question

Let's say I have a set of variables $a_1, ... ,a_n \in \{0, 1\}$ and a boolean algebra where multiplication is $\land$ and sum is $\oplus$ (exclusive or). This is like in bit operations in computers.

Let's define $c_n(k)$ as the sum of the products of all the ${n \choose k}$ $k$-combinations of the $n$ variables. For example:

$$c_3(1) = a_1 \oplus a_2 \oplus a_3$$ $$c_3(2) = a_1a_2 \oplus a_1a_3 \oplus a_2a_3 = a_1 \land a_2 \oplus a_1 \land a_3 \oplus a_2 \land a_3$$

I would like to be able to get a general formula for all $c_n(k)c_n(j)$ products. For example I can compute:

$$c_3(2)c_3(1) = c_3(3)$$ $$c_4(1)c_4(4) = 0$$

and obviously:

$$c_n(k)c_n(k) = c_n(k)$$

The formula could be restricted to some $n$ values only, but arbitrarily large, for example only to $n$ even or odd, or only e.g. $n = 2^m$, or $n = 2^{2m}$, or something else, if it is simpler.

Where to start? Should I use induction? Is there already some work done on this? Thank you for any idea!

After making a calculator program I was able to compute also the following:

$\small{c_3(1)c_3(3) = c_3(3)}$, $\small{c_3(2)c_3(3) = c_3(3)}$

$\small{c_4(1)c_4(2) = c_4(3)}$, $\small{c_4(1)c_4(3) = c_4(3)}$, $\small{c_4(1)c_4(4) = 0}$, $\small{c_4(2)c_4(3) = c_4(3)}$, $\small{c_4(2)c_4(4) = 0}$, $\small{c_4(3)c_4(4) = 0}$

$\small{c_5(1)c_5(2) = c_5(3)}$, $\small{c_5(1)c_5(3) = c_5(3)}$, $\small{c_5(1)c_5(4) = c_5(5)}$, $\small{c_5(1)c_5(5) = c_5(5)}$, $\small{c_5(2)c_5(3) = c_5(3)}$, $\small{c_5(2)c_5(4) = 0}$, $\small{c_5(2)c_5(5) = 0}$, $\small{c_5(3)c_5(4) = 0}$, $\small{c_5(3)c_5(5) = 0}$, $\small{c_5(4)c_5(5) = c_5(5)}$

$\small{c_6(1)c_6(2) = c_6(3)}$, $\small{c_6(1)c_6(3) = c_6(3) }$, $\small{c_6(1)c_6(4) = c_6(5)}$, $\small{c_6(1)c_6(5) = c_6(5)}$, $\small{c_6(1)c_6(6) = 0}$, $\small{c_6(2)c_6(3) = c_6(3)}$, $\small{c_6(2)c_6(4) = c_6(6)}$, $\small{c_6(2)c_6(5) = 0}$, $\small{c_6(2)c_6(6) = c_6(6)}$, $\small{c_6(3)c_6(4) = 0}$, $\small{c_6(3)c_6(5) = 0}$, $\small{c_6(3)c_6(6) = 0}$, $\small{c_6(4)c_6(5) = c_6(5)}$, $\small{c_6(4)c_6(6) = c_6(6)}$, $\small{c_6(5)c_6(6) = 0}$

$\small{c_7(1)c_7(2) = c_7(3)}$, $\small{c_7(1)c_7(3) = c_7(3)}$, $\small{c_7(1)c_7(4) = c_7(5)}$, $\small{c_7(1)c_7(5) = c_7(5)}$, $\small{c_7(1)c_7(6) = c_7(7)}$, $\small{c_7(1)c_7(7) = c_7(7)}$, $\small{c_7(2)c_7(3) = c_7(3)}$, $\small{c_7(2)c_7(4) = c_7(6)}$, $\small{c_7(2)c_7(5) = c_7(7)}$, $\small{c_7(2)c_7(6) = c_7(6)}$, $\small{c_7(2)c_7(7) = c_7(7)}$, $\small{c_7(3)c_7(4) = c_7(7)}$, $\small{c_7(3)c_7(5) = c_7(7)}$, $\small{c_7(3)c_7(6) = c_7(7)}$, $\small{c_7(3)c_7(7) = c_7(7)}$, $\small{c_7(4)c_7(5) = c_7(5)}$, $\small{c_7(4)c_7(6) = c_7(6)}$, $\small{c_7(4)c_7(7) = c_7(7)}$, $\small{c_7(5)c_7(6) = c_7(7)}$, $\small{c_7(5)c_7(7) = c_7(7)}$, $\small{c_7(6)c_7(7) = c_7(7)}$

$\small{c_8(1)c_8(2) = c_8(3)}$, $\small{c_8(1)c_8(3) = c_8(3)}$, $\small{c_8(1)c_8(4) = c_8(5)}$, $\small{c_8(1)c_8(5) = c_8(5)}$, $\small{c_8(1)c_8(6) = c_8(7)}$, $\small{c_8(1)c_8(7) = c_8(7)}$, $\small{c_8(1)c_8(8) = 0}$, $\small{c_8(2)c_8(3) = c_8(3)}$, $\small{c_8(2)c_8(4) = c_8(6)}$, $\small{c_8(2)c_8(5) = c_8(7)}$, $\small{c_8(2)c_8(6) = c_8(6)}$, $\small{c_8(2)c_8(7) = c_8(7)}$, $\small{c_8(2)c_8(8) = 0}$, $\small{c_8(3)c_8(4) = c_8(7)}$, $\small{c_8(3)c_8(5) = c_8(7)}$, $\small{c_8(3)c_8(6) = c_8(7)}$, $\small{c_8(3)c_8(7) = c_8(7)}$, $\small{c_8(3)c_8(8) = 0}$, $\small{c_8(4)c_8(5) = c_8(5)}$, $\small{c_8(4)c_8(6) = c_8(6)}$, $\small{c_8(4)c_8(7) = c_8(7)}$, $\small{c_8(4)c_8(8) = 0}$, $\small{c_8(5)c_8(6) = c_8(7)}$, $\small{c_8(5)c_8(7) = c_8(7)}$, $\small{c_8(5)c_8(8) = 0}$, $\small{c_8(6)c_8(7) = c_8(7)}$, $\small{c_8(6)c_8(8) = 0}$, $\small{c_8(7)c_8(8) = 0}$

Based on these experimental results I suspect that the formula might be something like this:

$$c_n(k)c_n(j) = \begin{cases} c_n(k \lor j), & \text{if $k < n$ and $j < n$} \\[2ex] 0, & \text{if $k = n$ and ${n \choose j}$ is even or $j = n$ and ${n \choose k}$ is even} \\[2ex] c_n(n), & \text{if $k = n$ and ${n \choose j}$ is odd or $j = n$ and ${n \choose k}$ is odd} \end{cases}$$

where $k \lor j$ is the number obtained as the bitwise OR of the binary representations of $k$ and $j$.

Answer 1

The elementary symmetric polynomials are related to your function by $$e_k(a_1,a_2,\dots,a_n)\equiv c_n(k)\pmod{2}$$ where multiplication mod $2$ is $\wedge$ and addition mod $2$ is $\oplus$. For completeness, let $c_n(0):=1$.

Vieta's formula is that a polynomial with roots $a_1,\dots,a_n$ with multiplicity is given by $f(x)=\sum_{i=0}^n(-1)^ie_i(a_1,\dots,a_n)x^{n-i}$. If we think of a particular assignment of $0$'s and $1$'s to $a_1,\dots,a_n$, then we can also write $f(x)=x^a(x-1)^b$, where $a,b$ are the numbers of $0$'s and $1$'s (with $a+b=n$). Expanded, this is $f(x)=\sum_{j=0}^b\binom{b}{j}x^{a+b-j}(-1)^j$. Modulo $2$, we get $$\sum_{i=0}^ne_i(a_1,\dots,a_n)x^{n-i}\equiv\sum_{j=0}^b\binom{b}{j}x^{n-j}\pmod{2}.$$ Matching up coefficients, $e_k(a_1,\dots,a_n)\equiv\binom{b}{k}\pmod{2}$. That is, $c_n(k)\equiv\binom{b}{k}\pmod{2}$ when $b$ is the number of variables set to $1$. (By the way, construct Pascal's triangle modulo $2$ if you haven't already. Do it out far enough until you recognize the shape.)

Lucas's theorem can be used to understand these binomial coefficients. Write $b=\sum_{i=0}^m b_i2^i$ and $k=\sum_{i=0}^m k_i2^i$, with $b_0,\dots,b_m,k_0,\dots,k_m\in\{0,1\}$. That is, as base-2 representations. Then $\binom{b}{k}\equiv\prod_{i=0}^m\binom{b_i}{k_i}\pmod{2}$, where recall $\binom{0}{1}=0$. Logically, with $p,q\in\{0,1\}$, $\binom{p}{q}$ is $q\to p$ ($q$ implies $p$) since if $q=0$ the coefficient is $1$, and if $q=1$, then the coefficient is $p$.

Let $j$ be another number and let $j_0,\dots,j_m$ be similar. Then, $$c_n(k)c_n(j)\equiv\binom{b}{k}\binom{b}{j}\equiv \prod_{i=0}^m\binom{b_i}{k_i}\binom{b_i}{j_i}$$ Recall that $(k_i\to b_i)\wedge(j_i\to b_i)$ is logically $(k_i\vee j_i)\to b_i$, so we have $$c_n(k)c_n(j)\equiv\prod_{i=0}^m\binom{b_i}{k_i\vee j_i}\equiv\binom{b}{k\vee j}$$ using your bitwise-OR notation.

This holds for all $b$. Thus, if $k\vee j\leq n$, $c_n(k)c_n(j)=c_n(k\vee j)$. Otherwise, if $k\vee j > n$, $c_n(k)c_n(j)=0$.

If you define $c_n(m)=0$ when $m>n$, then it is just $$c_n(k)c_n(j)=c_n(k\vee j).$$

---

There might be other interesting identities one can get from Newton's identities, but I couldn't find any. They involve $p_k(a_1,\dots,a_n)=a_1^k+\dots+a_n^k$, which is just $e_1(a_1,\dots,a_n)$ when mod $2$ and $k\geq 1$. So, the identity $$ke_k(a_1,\dots,a_n)=\sum_{i=1}^k(-1)^{i-1}e_{k-i}(a_1,\dots,a_n)p_i(a_1,\dots,a_n)$$ when reduced mod $2$ is $$ke_k(a_1,\dots,a_n)\equiv\sum_{i=1}^ke_{k-i}(a_1,\dots,a_n)e_1(a_1,\dots,a_n)\pmod{2}$$ or $$kc_n(k)\equiv c_n(1)\sum_{j=0}^{k-1}c_n(j)\pmod{2}.$$

For example, if $k=3$, we get $c_n(3)=c_n(1)(1+c_n(1)+c_n(2))$.

But, distributing the right hand side we get $c_n(1)+c_n(1)+c_n(1)c_n(2)=c_n(3)$, which is nothing new.

Answer 2

$\def\peq{\mathrel{\phantom{=}}{}}$Step 1: Preliminary analysis.

Note that in this system, $a + a = 0$ and $a^2 = a$ for any $a$. For any $1 \leqslant k, l \leqslant n$, suppose$$ c_n(k) c_n(l) = \sum_{m = 1}^{\min(k + l, n)} b_m c_n(m), $$ where $b_1, \cdots, b_{\min(k + l, n)} \in \{0, 1\}$. Note that for any $A, B \subseteq \{1, \cdots, n\}$, there is$$ \left( \prod_{i \in A} a_i \right)\left( \prod_{j \in B} a_j \right) = \prod_{i \in A \cup B} a_i, $$ and $|A| = k,\ |B| = l \Rightarrow |A \cup B| \geqslant \max(k, l)$, thus $b_m = 0$ for $1 \leqslant m < \max(k, l)$. For $\max(k, l) \leqslant m \leqslant \min(n, k + l)$, in order to determine $b_m$, it suffices to find the number of set pairs $(A, B)$ that satisfy the following requirements:

1. $A, B \subseteq \{1, \cdots, n\}$,
2. $|A| = k$, $|B| = l$, $A \cup B = \{1, \cdots, m\}$.

First, there are $C(m, k)$ ways to select $A$. After fixing $A$, note that $\{1, \cdots, m\} \setminus A \subseteq B$, thus there are $C(k, l - (m - k))$ ways to select $B$. Therefore,$$ b_m \equiv C(m, k) C(k, l - (m - k)) \equiv \frac{m!}{(m - k)!\, (m - l)!\, (k + l - m)!} \pmod{2}. $$

Step 2: For any $k, l \geqslant 1$, there exists a unique $m = f(k, l)$ such that $\max(k, l) \leqslant m \leqslant k + l$ and $\dfrac{m!}{(m - k)!\, (m - l)!\, (k + l - m)!}$ is odd.

Proof: Two lemmas first.

Lemma 1: For any $a, b, c \ge 0$,$$ \frac{(a + b + c)!}{a!\, b!\, c!} \text{ is odd} \Longleftrightarrow \forall j \geqslant 1:\ \left\{ \frac{a}{2^j} \right\} + \left\{ \frac{b}{2^j} \right\} + \left\{ \frac{c}{2^j} \right\} < 1, $$ where $\{x\} = x - [x]$ is the fractional part of $x$.

Proof: Note that for any $n \geqslant 0$, Legendre's formula $$ ν_2(n) = \sum_{j = 1}^∞ \left[ \frac{n}{2^j} \right] $$ gives the exponent of the largest power of $2$ that divides $n!$. Since $a!\, b!\, c! \mid (a + b + c)!$, then$$ \frac{(a + b + c)!}{a!\, b!\, c!} \text{ is odd} \Longleftrightarrow \sum_{j = 1}^∞ \left[ \frac{a + b + c}{2^j} \right] = \sum_{j = 1}^∞ \left( \left[ \frac{a}{2^j} \right] + \left[ \frac{b}{2^j} \right] + \left[ \frac{c}{2^j} \right] \right). $$ Because\begin{align*} &\peq \sum_{j = 1}^∞ \left( \left[ \frac{a + b + c}{2^j} \right] - \left( \left[ \frac{a}{2^j} \right] + \left[ \frac{b}{2^j} \right] + \left[ \frac{c}{2^j} \right] \right) \right)\\ &= \sum_{j = 1}^∞ \left[ \frac{a + b + c}{2^j} - \left( \left[ \frac{a}{2^j} \right] + \left[ \frac{b}{2^j} \right] + \left[ \frac{c}{2^j} \right] \right) \right]\\ &= \sum_{j = 1}^∞ \left[ \left\{ \frac{a}{2^j} \right\} + \left\{ \frac{b}{2^j} \right\} + \left\{ \frac{c}{2^j} \right\} \right], \end{align*} then\begin{align*} &\mathrel{\phantom{\longleftrightarrow}}{} \sum_{j = 1}^∞ \left[ \frac{a + b + c}{2^j} \right] = \sum_{j = 1}^∞ \left( \left[ \frac{a}{2^j} \right] + \left[ \frac{b}{2^j} \right] + \left[ \frac{c}{2^j} \right] \right)\\ &\Longleftrightarrow \forall j \geqslant 1:\ \left[ \left\{ \frac{a}{2^j} \right\} + \left\{ \frac{b}{2^j} \right\} + \left\{ \frac{c}{2^j} \right\} \right] = 0\\ &\Longleftrightarrow \forall j \geqslant 1:\ \left\{ \frac{a}{2^j} \right\} + \left\{ \frac{b}{2^j} \right\} + \left\{ \frac{c}{2^j} \right\} < 1. \end{align*}

Lemma 2: For any $m, n \in \mathbb{N}_+$, there exists $a \in \mathbb{N}$ such that $\left\{ \dfrac{m}{n} \right\} = \dfrac{a}{n}$. (Proof omitted.)

Now back to step 2. It will be proved by induction on $r \geqslant 0$ that the proposition holds for $1 \leqslant k, l \leqslant 2^r$.

For $r = 0$, if $k = l = 1$, then $1 \leqslant m \leqslant 2$ and the only $m$ that satisfies the requirements is $m = 1$. Now assume that the proposition holds for $1 \leqslant k, l \leqslant 2^r$. For $1 \leqslant k, l \leqslant 2^{r + 1}$, there are three cases.

Case 1: Both $k$ and $l$ are even. Suppose $k = 2k_0$ and $l = 2l_0$, then $k_0, l_0 \geqslant 1$. On the one hand, suppose $m_0 = f(k_0, l_0)$ and $m = 2m_0$, then$$ \left\{ \frac{2m_0 - 2k_0}{2} \right\} + \left\{ \frac{2m_0 - 2l_0}{2} \right\} + \left\{ \frac{2k_0 + 2l_0 - 2m_0}{2} \right\} = 0 < 1. $$ For $j \geqslant 2$, by lemma 1 and induction hypothesis,\begin{align*} &\peq \left\{ \frac{2m_0 - 2k_0}{2^j} \right\} + \left\{ \frac{2m_0 - 2l_0}{2^j} \right\} + \left\{ \frac{2k_0 + 2l_0 - 2m_0}{2^j} \right\}\\ &= \left\{ \frac{m_0 - k_0}{2^{j - 1}} \right\} + \left\{ \frac{m_0 - l_0}{2^{j - 1}} \right\} + \left\{ \frac{k_0 + l_0 - m_0}{2^{j - 1}} \right\} < 1. \end{align*} Thus by lemma 1, $m = 2m_0$ satisfies the requirements. On the other hand, for any $m$ that satisfies the requirements, if $m$ is odd, then$$ \left\{ \frac{m - 2k_0}{2} \right\} + \left\{ \frac{m - 2l_0}{2} \right\} + \left\{ \frac{2k_0 + 2l_0 - m}{2} \right\} = \frac{3}{2} > 1, $$ a contradiction by lemma 1. Suppose $m = 2m_1$, then $\max(k_0, l_0) \leqslant m_1 \leqslant k_0 + l_0$. For any $j \geqslant 1$, by lemma 1,\begin{align*} &\peq \left\{ \frac{m_1 - k_0}{2^j} \right\} + \left\{ \frac{m_1 - l_0}{2^j} \right\} + \left\{ \frac{k_0 + l_0 - m_1}{2^j} \right\}\\ &= \left\{ \frac{2m_1 - 2k_0}{2^{j + 1}} \right\} + \left\{ \frac{2m_1 - 2l_0}{2^{j + 1}} \right\} + \left\{ \frac{2k_0 + 2l_0 - 2m_1}{2^{j + 1}} \right\} < 1, \end{align*} which by lemma 1 and induction hypothesis implies $m_1 = f(k_0, l_0)$.

Case 2: One of $k$ and $l$ is odd and the other is even. Without loss of generality, suppose $k = 2k_0 + 1$ and $l = 2l_0$, then $l_0 \geqslant 1$. If $k_0 = 0$, then $2l_0 \leqslant m \leqslant 2l_0 + 1$ and $m = 2l_0 + 1$ is the only $m$ that satisfies the requirements.

Now assume that $k_0 \geqslant 1$. On the one hand, suppose $m_0 = f(k_0, l_0)$ and $m = 2m_0 + 1$, then$$ \left\{ \frac{2m_0 + 1 - 2k_0 - 1}{2} \right\} + \left\{ \frac{2m_0 + 1 - 2l_0}{2} \right\} + \left\{ \frac{2k_0 + 1 + 2l_0 - 2m_0 - 1}{2} \right\} = \frac{1}{2} < 1. $$ For $j \geqslant 2$, note that$$ 2m_0 + 1 - 2l_0 \not\equiv 0 \pmod{2^j} \Longrightarrow \left\{ \frac{2m_0 + 1 - 2l_0}{2^j} \right\} \geqslant \frac{1}{2^j}, $$ thus\begin{align*} &\peq \left\{ \frac{2m_0 + 1 - 2k_0 - 1}{2^j} \right\} + \left\{ \frac{2m_0 + 1 - 2l_0}{2^j} \right\} + \left\{ \frac{2k_0 + 1 + 2l_0 - 2m_0 - 1}{2^j} \right\}\\ &= \left\{ \frac{m_0 - k_0}{2^{j - 1}} \right\} + \left\{ \frac{2m_0 - 2l_0}{2^j} \right\} + \frac{1}{2^j} + \left\{ \frac{k_0 + l_0 - m_0}{2^{j - 1}} \right\}\\ &= \left\{ \frac{m_0 - k_0}{2^{j - 1}} \right\} + \left\{ \frac{m_0 - l_0}{2^{j - 1}} \right\} + \left\{ \frac{k_0 + l_0 - m_0}{2^{j - 1}} \right\} + \frac{1}{2^j}. \end{align*} By lemma 1 and induction hypothesis,$$ \left\{ \frac{m_0 - k_0}{2^{j - 1}} \right\} + \left\{ \frac{m_0 - l_0}{2^{j - 1}} \right\} + \left\{ \frac{k_0 + l_0 - m_0}{2^{j - 1}} \right\} < 1, $$ and lemma 2 implies$$ \left\{ \frac{m_0 - k_0}{2^{j - 1}} \right\} + \left\{ \frac{m_0 - l_0}{2^{j - 1}} \right\} + \left\{ \frac{k_0 + l_0 - m_0}{2^{j - 1}} \right\} \leqslant 1 - \frac{1}{2^{j - 1}}, $$ then$$ \left\{ \frac{m_0 - k_0}{2^{j - 1}} \right\} + \left\{ \frac{m_0 - l_0}{2^{j - 1}} \right\}+ \left\{ \frac{k_0 + l_0 - m_0}{2^{j - 1}} \right\} + \frac{1}{2^j} \leqslant 1 - \frac{1}{2^{j - 1}} + \frac{1}{2^j} < 1. $$ Thus by lemma 1, $m = 2m_0 + 1$ satisfies the requirements. On the other hand, for any $m$ that satisfies the requirements, if $m$ is even, then$$ \left\{ \frac{m - 2k_0 - 1}{2} \right\} + \left\{ \frac{m - 2l_0}{2} \right\} + \left\{ \frac{2k_0 + 1 + 2l_0 - m}{2} \right\} = 1, $$ a contradiction by lemma 1. Suppose $m = 2m_1 + 1$, then $\max(k_0, l_0) \leqslant m_1 \leqslant k_0 + l_0$ (note that $2m_1 + 1 \geqslant 2l_0 \Rightarrow m_1 \geqslant l_0$). For any $j \geqslant 1$, by lemma 1,$$ \left\{ \frac{2m_1 + 1 - 2k_0 - 1}{2^{j + 1}} \right\} + \left\{ \frac{2m_1 + 1 - 2l_0}{2^{j + 1}} \right\} + \left\{ \frac{2k_0 + 1 + 2l_0 - 2m_1 - 1}{2^{j + 1}} \right\} < 1. $$ Note that$$ 2m_1 + 1 - 2l_0 \not\equiv 0 \pmod{2^{j + 1}} \Longrightarrow \left\{ \frac{2m_1 + 1 - 2l_0}{2^{j + 1}} \right\} \geqslant \frac{1}{2^{j + 1}}, $$ thus\begin{align*} &\peq \left\{ \frac{m_1 - k_0}{2^j} \right\} + \left\{ \frac{m_1 - l_0}{2^j} \right\} + \left\{ \frac{k_0 + l_0 - m_1}{2^j} \right\}\\ &= \left\{ \frac{m_1 - k_0}{2^j} \right\} + \left\{ \frac{2m_1 + 1 - 2l_0}{2^{j + 1}} - \frac{1}{2^{j + 1}} \right\} + \left\{ \frac{k_0 + l_0 - m_1}{2^j} \right\}\\ &= \left\{ \frac{m_1 - k_0}{2^j} \right\} + \left\{ \frac{2m_1 + 1 - 2l_0}{2^{j + 1}} \right\} - \frac{1}{2^{j + 1}} + \left\{ \frac{k_0 + l_0 - m_1}{2^j} \right\}\\ &= \left\{ \frac{2m_1 + 1 - 2k_0 - 1}{2^{j + 1}} \right\} + \left\{ \frac{2m_1 + 1 - 2l_0}{2^{j + 1}} \right\} + \left\{ \frac{2k_0 + 1 + 2l_0 - 2m_1 - 1}{2^{j + 1}} \right\} - \frac{1}{2^{j + 1}}\\ &< 1 - \frac{1}{2^{j + 1}} < 1, \end{align*} which by lemma 1 and induction hypothesis implies $m_1 = f(k_0, l_0)$.

Case 3: Both $k$ and $l$ are odd. Suppose $k = 2k_0 + 1$, $l = 2l_0 + 1$. If at least one of $k_0$ and $l_0$ is $0$, without loss of generality, assume that $k_0 = 0$, then $2l_0 + 1 \leqslant m \leqslant 2l_0 + 2$ and $m = 2l_0 + 1$ is the only $m$ that satisfies the requirements.

Now suppose $k_0, l_0 \geqslant 1$ and take $m_0 = f(k_0, l_0)$. By deduction analogous to case 2, $m = 2m_0 + 1$ is the only $m$ that satisfies the requirements.

Therefore, the proposition holds for $1 \leqslant k, l \leqslant 2^{r + 1}$. End of induction.

Step 3: For any $k, l \geqslant 1$, there is $f(k, l) = k \lor l$, where $\lor$ represents bitwise OR (e.g. $5 \lor 13 = (0101)_2 \lor (1101)_2 = (1101)_2 = 13$), and for any $n \geqslant 1$,$$ c_n(k) c_n(l) = \begin{cases} c_n(k \lor l); & k \lor l \leqslant n\\ 0; & k \lor l > n \end{cases}. $$

Proof: From the proof of step 2, $f$ satisfies the following recurrence relations for $k, l \geqslant 2$:$$ f(k, l) = \begin{cases} 2 f\left( \frac{k}{2}, \frac{l}{2} \right); & 2 \mid k,\ 2 \mid l\\ 2 f\left( \left[ \frac{k}{2} \right], \left[ \frac{l}{2} \right] \right) + 1; & \text{otherwise} \end{cases}, $$ and $f(k, 1) = f(1, k) = 2 \left[ \dfrac{k}{2} \right] + 1$ for $k \geqslant 1$. If further define $f(k, 0) = f(0, k) = k$ for $k \geqslant 0$, then$$ f(k, l) = \begin{cases} 2 f\left( \frac{k}{2}, \frac{l}{2} \right); & 2 \mid k,\ 2 \mid l\\ 2 f\left( \left[ \frac{k}{2} \right], \left[ \frac{l}{2} \right] \right) + 1; & \text{otherwise} \end{cases} $$ hold for $k, l \geqslant 1$. Now it is easy to prove by induction on $k \geqslant 0$ that $f(k, l) = k \lor l\ (\forall l \geqslant 0)$.

Finally, for any $n \geqslant 1$ and $1 \leqslant k, l \leqslant n$, if $k \lor l \leqslant n$, then step 1 and step 2 imply $b_{k \lor l} = 1$, $b_m = 0\ (m ≠ k \lor l)$ and $c_n(k) c_n(l) = c_n(k \lor l)$. Otherwise, step 1 and step 2 imply $b_m = 0$ for all $m$ and $c_n(k) c_n(l) = 0$.