My Math Forum Title in Fench : "Coup de Boole"

 Abstract Algebra Abstract Algebra Math Forum

 May 31st, 2017, 03:09 AM #1 Member   Joined: May 2017 From: France Posts: 57 Thanks: 1 Title in Fench : "Coup de Boole" Hi, $\displaystyle \textbf{Coup de Boole : } n\geq 3, f\text{ function boolean to n variables.} \\ \text{ Is it true that, } \sum \limits_{\sigma \in S_n} f(x_{\sigma(1)},...,x_{\sigma(n)}) \mod 2=0 \text{ ?}$ $\displaystyle S_n$ the permutation group. Cordially. Last edited by skipjack; June 3rd, 2017 at 02:49 AM.
 June 3rd, 2017, 01:21 AM #2 Member   Joined: May 2017 From: Russia Posts: 34 Thanks: 5 There is an idea how to prove it. $\displaystyle f$ can be represented in the form of Zhegalkin polynomial (algebraic form of Boolean function). One uses conjunction and exclusive OR. Let's denote conjunction as $\displaystyle \cdot$ and exclusive OR as +. Let $\displaystyle x_{i_1}x_{i_2}\cdot\ldots\cdot x_{i_t}$ be one of the monomials of the polynomial which represents $\displaystyle f$. Let $\displaystyle (a_1, \ \ldots,\ a_n)$ be an arbitrary vector of arguments. Every $\displaystyle a_j$ is equal to 0 or 1. Let suppose that there exists $\displaystyle \sigma \in S_n$ such that product (conjunction) $\displaystyle a_{\sigma(i_1)}\cdot\ \ldots\ \cdot a_{\sigma(i_t)}=1.$ And let $\displaystyle p$ be the number of units among $\displaystyle a_1, \ \ldots,\ a_n.$ The number of substitutions from $\displaystyle S_n$ which fixes algebraic relation $\displaystyle a_{\sigma(i_1)}\cdot\ \ldots\ \cdot a_{\sigma(i_t)}=1$ is equal to $\displaystyle \frac{p!}{(p-t)!}\cdot (n-t)!.$ The last number is even. So, it implies that $\displaystyle \sum_{\sigma\in S_n} a_{\sigma(i_1)}\cdot\ \ldots\ \cdot a_{\sigma(i_t)}\ {\rm mod}\ 2 = 0.$ And $\displaystyle \sum_{\sigma\in S_n} f(a_{\sigma(i_1)}, \ \ldots,\ a_{\sigma(i_n)})\ {\rm mod}\ 2 = 0.$
 June 4th, 2017, 07:36 AM #3 Member   Joined: May 2017 From: France Posts: 57 Thanks: 1 Bravo.

 Tags coup de boole, fench, title

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post SedaKhold Calculus 0 February 13th, 2012 11:45 AM The Chaz Calculus 1 August 5th, 2011 09:03 PM katie0127 Advanced Statistics 0 December 3rd, 2008 01:54 PM Ujjwal Number Theory 2 September 29th, 2008 07:06 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top