1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Your second product identity can be generalized to $c_n(k)c_n(n)=0$ if $\binom{n}k$ is even. $\endgroup$ – Richard Jul 23 '18 at 9:38
1
+100
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you! I could never have done it myself. By the way every natural number $m \le n = 2^p$ can be expressed as: $$m = \sum_{i=1}^{p}c_n(2^i)2^i$$ provided that $a_1=\ldots=a_m=1$ and $a_{m+1}=\ldots=a_n=0$. That expression could be used to compute a certain $f(m)$ (for example the Collatz function) over an entire interval $1 \le m \le n$. $\endgroup$ – mbjoe Jul 28 '18 at 7:00
  • $\begingroup$ I guess that's because $c_n(2^i)=\binom{m}{2^i}\pmod{2}$ (with your assignment of $1$'s and $0$'s), which according to Lucas's theorem is the $i$th bit of $m$. I'm not seeing how it applies to the Collatz function, but it could be interesting if it does. $\endgroup$ – Kyle Miller Jul 28 '18 at 17:38
  • $\begingroup$ Because for $m=\sum_{i=0}^{p}m_i2^i$ the Collatz function is: $f(m)=\sum_{i=1}^{p}m_i2^{i-1}+\sum_{i=1}^{p}m_0m_i2^i+m_02$ so it is possible to compute binary coefficients at each step as some $\sum_{i}c_n(k_i)$. Probably not of much use though, since a numeric verification is much faster. $\endgroup$ – mbjoe Aug 6 '18 at 7:13
1
$\begingroup$

$\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$.

$\endgroup$
  • $\begingroup$ Thank you very much, although I preferred to reward the other answer because it looks simpler to me. See the comment below regarding the binary representation with $c_n(2^i)$ coefficients. $\endgroup$ – mbjoe Jul 28 '18 at 7:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.