My Math Forum  

Go Back   My Math Forum > College Math Forum > Abstract Algebra

Abstract Algebra Abstract Algebra Math Forum

LinkBack Thread Tools Display Modes
May 31st, 2017, 03:09 AM   #1
Joined: May 2017
From: France

Posts: 57
Thanks: 1

Title in Fench : "Coup de Boole"


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


Last edited by skipjack; June 3rd, 2017 at 02:49 AM.
Dattier is offline  
June 3rd, 2017, 01:21 AM   #2
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. $
ABVictor is offline  
June 4th, 2017, 07:36 AM   #3
Joined: May 2017
From: France

Posts: 57
Thanks: 1

Dattier is offline  

  My Math Forum > College Math Forum > Abstract Algebra

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" SedaKhold Calculus 0 February 13th, 2012 11:45 AM
"separate and integrate" or "Orangutang method" The Chaz Calculus 1 August 5th, 2011 09:03 PM
sample exeriment-need help finding "statistic" and "result" katie0127 Advanced Statistics 0 December 3rd, 2008 01:54 PM
terms "non-increasing" or "non-decreasing" Ujjwal Number Theory 2 September 29th, 2008 07:06 AM

Copyright © 2018 My Math Forum. All rights reserved.