ukmuiik

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:

$smallc_3(1)c_3(3) = c_3(3)$,
$smallc_3(2)c_3(3) = c_3(3)$

$smallc_4(1)c_4(2) = c_4(3)$,
$smallc_4(1)c_4(3) = c_4(3)$,
$smallc_4(1)c_4(4) = 0$,
$smallc_4(2)c_4(3) = c_4(3)$,
$smallc_4(2)c_4(4) = 0$,
$smallc_4(3)c_4(4) = 0$

$smallc_5(1)c_5(2) = c_5(3)$,
$smallc_5(1)c_5(3) = c_5(3)$,
$smallc_5(1)c_5(4) = c_5(5)$,
$smallc_5(1)c_5(5) = c_5(5)$,
$smallc_5(2)c_5(3) = c_5(3)$,
$smallc_5(2)c_5(4) = 0$,
$smallc_5(2)c_5(5) = 0$,
$smallc_5(3)c_5(4) = 0$,
$smallc_5(3)c_5(5) = 0$,
$smallc_5(4)c_5(5) = c_5(5)$

$smallc_6(1)c_6(2) = c_6(3)$,
$smallc_6(1)c_6(3) = c_6(3) $,
$smallc_6(1)c_6(4) = c_6(5)$,
$smallc_6(1)c_6(5) = c_6(5)$,
$smallc_6(1)c_6(6) = 0$,
$smallc_6(2)c_6(3) = c_6(3)$,
$smallc_6(2)c_6(4) = c_6(6)$,
$smallc_6(2)c_6(5) = 0$,
$smallc_6(2)c_6(6) = c_6(6)$,
$smallc_6(3)c_6(4) = 0$,
$smallc_6(3)c_6(5) = 0$,
$smallc_6(3)c_6(6) = 0$,
$smallc_6(4)c_6(5) = c_6(5)$,
$smallc_6(4)c_6(6) = c_6(6)$,
$smallc_6(5)c_6(6) = 0$

$smallc_7(1)c_7(2) = c_7(3)$,
$smallc_7(1)c_7(3) = c_7(3)$,
$smallc_7(1)c_7(4) = c_7(5)$,
$smallc_7(1)c_7(5) = c_7(5)$,
$smallc_7(1)c_7(6) = c_7(7)$,
$smallc_7(1)c_7(7) = c_7(7)$,
$smallc_7(2)c_7(3) = c_7(3)$,
$smallc_7(2)c_7(4) = c_7(6)$,
$smallc_7(2)c_7(5) = c_7(7)$,
$smallc_7(2)c_7(6) = c_7(6)$,
$smallc_7(2)c_7(7) = c_7(7)$,
$smallc_7(3)c_7(4) = c_7(7)$,
$smallc_7(3)c_7(5) = c_7(7)$,
$smallc_7(3)c_7(6) = c_7(7)$,
$smallc_7(3)c_7(7) = c_7(7)$,
$smallc_7(4)c_7(5) = c_7(5)$,
$smallc_7(4)c_7(6) = c_7(6)$,
$smallc_7(4)c_7(7) = c_7(7)$,
$smallc_7(5)c_7(6) = c_7(7)$,
$smallc_7(5)c_7(7) = c_7(7)$,
$smallc_7(6)c_7(7) = c_7(7)$

$smallc_8(1)c_8(2) = c_8(3)$,
$smallc_8(1)c_8(3) = c_8(3)$,
$smallc_8(1)c_8(4) = c_8(5)$,
$smallc_8(1)c_8(5) = c_8(5)$,
$smallc_8(1)c_8(6) = c_8(7)$,
$smallc_8(1)c_8(7) = c_8(7)$,
$smallc_8(1)c_8(8) = 0$,
$smallc_8(2)c_8(3) = c_8(3)$,
$smallc_8(2)c_8(4) = c_8(6)$,
$smallc_8(2)c_8(5) = c_8(7)$,
$smallc_8(2)c_8(6) = c_8(6)$,
$smallc_8(2)c_8(7) = c_8(7)$,
$smallc_8(2)c_8(8) = 0$,
$smallc_8(3)c_8(4) = c_8(7)$,
$smallc_8(3)c_8(5) = c_8(7)$,
$smallc_8(3)c_8(6) = c_8(7)$,
$smallc_8(3)c_8(7) = c_8(7)$,
$smallc_8(3)c_8(8) = 0$,
$smallc_8(4)c_8(5) = c_8(5)$,
$smallc_8(4)c_8(6) = c_8(6)$,
$smallc_8(4)c_8(7) = c_8(7)$,
$smallc_8(4)c_8(8) = 0$,
$smallc_8(5)c_8(6) = c_8(7)$,
$smallc_8(5)c_8(7) = c_8(7)$,
$smallc_8(5)c_8(8) = 0$,
$smallc_8(6)c_8(7) = c_8(7)$,
$smallc_8(6)c_8(8) = 0$,
$smallc_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) =
begincases
c_n(k lor j), & textif $k < n$ and $j < n$ \[2ex]
0, & textif $k = n$ and $n choose j$ is even or $j = n$ and $n choose k$ is even \[2ex]
c_n(n), & textif $k = n$ and $n choose j$ is odd or $j = n$ and $n choose k$ is odd
endcases$$

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

Your second product identity can be generalized to $c_n(k)c_n(n)=0$ if $binomnk$ is even. — Jul 23 at 9:38

score 0 · Accepted Answer · 2018-07-26 18:16:05Z

The elementary symmetric polynomials are related to your function by $$e_k(a_1,a_2,dots,a_n)equiv c_n(k)pmod2$$
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^bbinombjx^a+b-j(-1)^j$. Modulo $2$, we get
$$sum_i=0^ne_i(a_1,dots,a_n)x^n-iequivsum_j=0^bbinombjx^n-jpmod2.$$
Matching up coefficients, $e_k(a_1,dots,a_n)equivbinombkpmod2$. That is, $c_n(k)equivbinombkpmod2$ 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_min0,1$. That is, as base-2 representations. Then $binombkequivprod_i=0^mbinomb_ik_ipmod2$, where recall $binom01=0$. Logically, with $p,qin0,1$, $binompq$ is $qto 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)equivbinombkbinombjequiv prod_i=0^mbinomb_ik_ibinomb_ij_i$$
Recall that $(k_ito b_i)wedge(j_ito b_i)$ is logically $(k_ivee j_i)to b_i$, so we have
$$c_n(k)c_n(j)equivprod_i=0^mbinomb_ik_ivee j_iequivbinombkvee j$$
using your bitwise-OR notation.

This holds for all $b$. Thus, if $kvee jleq n$, $c_n(k)c_n(j)=c_n(kvee j)$. Otherwise, if $kvee 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(kvee 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 $kgeq 1$. So, the identity
$$ke_k(a_1,dots,a_n)=sum_i=1^k(-1)^i-1e_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)equivsum_i=1^ke_k-i(a_1,dots,a_n)e_1(a_1,dots,a_n)pmod2$$
or
$$kc_n(k)equiv c_n(1)sum_j=0^k-1c_n(j)pmod2.$$

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.

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^pc_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$. — Jul 28 at 7:00
I guess that's because $c_n(2^i)=binomm2^ipmod2$ (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. — Jul 28 at 17:38
Because for $m=sum_i=0^pm_i2^i$ the Collatz function is: $f(m)=sum_i=1^pm_i2^i-1+sum_i=1^pm_0m_i2^i+m_02$ so it is possible to compute binary coefficients at each step as some $sum_ic_n(k_i)$. Probably not of much use though, since a numeric verification is much faster. — Aug 6 at 7:13

Alex Francisco 15.6k92047 · Answer 2 · 2018-07-27 15:02:13Z

$defpeqmathrelphantom=$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:

$A, B subseteq 1, cdots, n$,

$|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 fracm!(m - k)!, (m - l)!, (k + l - m)! pmod2.
$$

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 $dfracm!(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 fraca2^j right + left fracb2^j right + left fracc2^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[ fracn2^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[ fraca + b + c2^j right] = sum_j = 1^Ã¢ÂˆÂž left( left[ fraca2^j right] + left[ fracb2^j right] + left[ fracc2^j right] right).
$$
Becausebeginalign*
&peq sum_j = 1^Ã¢ÂˆÂž left( left[ fraca + b + c2^j right] - left( left[ fraca2^j right] + left[ fracb2^j right] + left[ fracc2^j right] right) right)\
&= sum_j = 1^Ã¢ÂˆÂž left[ fraca + b + c2^j - left( left[ fraca2^j right] + left[ fracb2^j right] + left[ fracc2^j right] right) right]\
&= sum_j = 1^Ã¢ÂˆÂž left[ left fraca2^j right + left fracb2^j right + left fracc2^j right right],
endalign*
thenbeginalign*
&mathrelphantomlongleftrightarrow sum_j = 1^Ã¢ÂˆÂž left[ fraca + b + c2^j right] = sum_j = 1^Ã¢ÂˆÂž left( left[ fraca2^j right] + left[ fracb2^j right] + left[ fracc2^j right] right)\
&Longleftrightarrow forall j geqslant 1: left[ left fraca2^j right + left fracb2^j right + left fracc2^j right right] = 0\
&Longleftrightarrow forall j geqslant 1: left fraca2^j right + left fracb2^j right + left fracc2^j right < 1.
endalign*

Lemma 2: For any $m, n in mathbbN_+$, there exists $a in mathbbN$ such that $left dfracmn right = dfracan$. (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 frac2m_0 - 2k_02 right + left frac2m_0 - 2l_02 right + left frac2k_0 + 2l_0 - 2m_02 right = 0 < 1.
$$
For $j geqslant 2$, by lemma 1 and induction hypothesis,beginalign*
&peq left frac2m_0 - 2k_02^j right + left frac2m_0 - 2l_02^j right + left frac2k_0 + 2l_0 - 2m_02^j right\
&= left fracm_0 - k_02^j - 1 right + left fracm_0 - l_02^j - 1 right + left frack_0 + l_0 - m_02^j - 1 right < 1.
endalign*
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 fracm - 2k_02 right + left fracm - 2l_02 right + left frac2k_0 + 2l_0 - m2 right = frac32 > 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,beginalign*
&peq left fracm_1 - k_02^j right + left fracm_1 - l_02^j right + left frack_0 + l_0 - m_12^j right\
&= left frac2m_1 - 2k_02^j + 1 right + left frac2m_1 - 2l_02^j + 1 right + left frac2k_0 + 2l_0 - 2m_12^j + 1 right < 1,
endalign*
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 frac2m_0 + 1 - 2k_0 - 12 right + left frac2m_0 + 1 - 2l_02 right + left frac2k_0 + 1 + 2l_0 - 2m_0 - 12 right = frac12 < 1.
$$
For $j geqslant 2$, note that$$
2m_0 + 1 - 2l_0 notequiv 0 pmod2^j Longrightarrow left frac2m_0 + 1 - 2l_02^j right geqslant frac12^j,
$$
thusbeginalign*
&peq left frac2m_0 + 1 - 2k_0 - 12^j right + left frac2m_0 + 1 - 2l_02^j right + left frac2k_0 + 1 + 2l_0 - 2m_0 - 12^j right\
&= left fracm_0 - k_02^j - 1 right + left frac2m_0 - 2l_02^j right + frac12^j + left frack_0 + l_0 - m_02^j - 1 right\
&= left fracm_0 - k_02^j - 1 right + left fracm_0 - l_02^j - 1 right + left frack_0 + l_0 - m_02^j - 1 right + frac12^j.
endalign*
By lemma 1 and induction hypothesis,$$
left fracm_0 - k_02^j - 1 right + left fracm_0 - l_02^j - 1 right + left frack_0 + l_0 - m_02^j - 1 right < 1,
$$
and lemma 2 implies$$
left fracm_0 - k_02^j - 1 right + left fracm_0 - l_02^j - 1 right + left frack_0 + l_0 - m_02^j - 1 right leqslant 1 - frac12^j - 1,
$$
then$$
left fracm_0 - k_02^j - 1 right + left fracm_0 - l_02^j - 1 right+ left frack_0 + l_0 - m_02^j - 1 right + frac12^j leqslant 1 - frac12^j - 1 + frac12^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 fracm - 2k_0 - 12 right + left fracm - 2l_02 right + left frac2k_0 + 1 + 2l_0 - m2 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 frac2m_1 + 1 - 2k_0 - 12^j + 1 right + left frac2m_1 + 1 - 2l_02^j + 1 right + left frac2k_0 + 1 + 2l_0 - 2m_1 - 12^j + 1 right < 1.
$$
Note that$$
2m_1 + 1 - 2l_0 notequiv 0 pmod2^j + 1 Longrightarrow left frac2m_1 + 1 - 2l_02^j + 1 right geqslant frac12^j + 1,
$$
thusbeginalign*
&peq left fracm_1 - k_02^j right + left fracm_1 - l_02^j right + left frack_0 + l_0 - m_12^j right\
&= left fracm_1 - k_02^j right + left frac2m_1 + 1 - 2l_02^j + 1 - frac12^j + 1 right + left frack_0 + l_0 - m_12^j right\
&= left fracm_1 - k_02^j right + left frac2m_1 + 1 - 2l_02^j + 1 right - frac12^j + 1 + left frack_0 + l_0 - m_12^j right\
&= left frac2m_1 + 1 - 2k_0 - 12^j + 1 right + left frac2m_1 + 1 - 2l_02^j + 1 right + left frac2k_0 + 1 + 2l_0 - 2m_1 - 12^j + 1 right - frac12^j + 1\
&< 1 - frac12^j + 1 < 1,
endalign*
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) = begincases
c_n(k lor l); & k lor l leqslant n\
0; & k lor l > n
endcases.
$$

Proof: From the proof of step 2, $f$ satisfies the following recurrence relations for $k, l geqslant 2$:$$
f(k, l) = begincases
2 fleft( frack2, fracl2 right); & 2 mid k, 2 mid l\
2 fleft( left[ frack2 right], left[ fracl2 right] right) + 1; & textotherwise
endcases,
$$
and $f(k, 1) = f(1, k) = 2 left[ dfrack2 right] + 1$ for $k geqslant 1$. If further define $f(k, 0) = f(0, k) = k$ for $k geqslant 0$, then$$
f(k, l) = begincases
2 fleft( frack2, fracl2 right); & 2 mid k, 2 mid l\
2 fleft( left[ frack2 right], left[ fracl2 right] right) + 1; & textotherwise
endcases
$$
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$.

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. — Jul 28 at 7:07

score 0 · Accepted Answer · 2018-07-26 18:16:05Z