How close can we come to a parity function when there isn't one?

Details How close can we come to a parity function when there isn't one? How close can we come to a parity function when there isn't one?

2010-05-26

arxiv.org/abs/1005.4897v1

Mathematics

Combinatorics

Scientific paper

Consider a group G such that there is no homomorphism f:G to {+1,-1}. In that case, how close can we come to such a homomorphism? We show that if f has zero expectation, then the probability that f(xy) = f(x) f(y), where x, y are chosen uniformly and independently from G, is at most 1/2(1+1/sqrt{d}), where d is the dimension of G's smallest nontrivial irreducible representation. For the alternating group A_n, for instance, d=n-1. On the other hand, A_n contains a subgroup isomorphic to S_{n-2}, whose parity function we can extend to obtain an f for which this probability is 1/2(1+1/{n \choose 2}). Thus the extent to which f can be "more homomorphic" than a random function from A_n to {+1,-1} lies between O(n^{-1/2}) and Omega(n^{-2}).

Affiliated with

Also associated with

No associations

Rating

How close can we come to a parity function when there isn't one? does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with How close can we come to a parity function when there isn't one?, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and How close can we come to a parity function when there isn't one? will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-606848