
Abstract Algebra Abstract Algebra Math Forum 
 LinkBack  Thread Tools  Display Modes 
May 31st, 2017, 04: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 03:49 AM. 
June 3rd, 2017, 02:21 AM  #2 
Member Joined: May 2017 From: Russia Posts: 33 Thanks: 4 
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!}{(pt)!}\cdot (nt)!.$ 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, 08:36 AM  #3 
Member Joined: May 2017 From: France Posts: 57 Thanks: 1 
Bravo.


Tags 
coup de boole, fench, title 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A "simple" application of dirac delta "shift theorem"...help  SedaKhold  Calculus  0  February 13th, 2012 12:45 PM 
"separate and integrate" or "Orangutang method"  The Chaz  Calculus  1  August 5th, 2011 10:03 PM 
sample exerimentneed help finding "statistic" and "result"  katie0127  Advanced Statistics  0  December 3rd, 2008 02:54 PM 
terms "nonincreasing" or "nondecreasing"  Ujjwal  Number Theory  2  September 29th, 2008 08:06 AM 