"Embedding" functions in groups Hi all, I am looking for some help with the following question. Take a discrete bivariate function $f(x,y)$ (i.e., $x$,$y$ take values in some finite sets). Is there a way to quantify how "embeddable" this function is in Abelian groups. For example, if $x,y$ are binary and f(x,y) = x XOR y, then f is clearly embeddable in $Z_2$ (the cyclic group on 2 elements). But if f(x,y) = x AND y, f's action can only be mimicked in $Z_3$. (i.e., treat $x$ and $y$ as elements of $Z_3$, add them in $Z_3$ and map the outputs as {0,1}->0, 2->1 to mimic the AND function). Is there a formal way to characterize the smallest Abelian group in which a given f(x,y) can be embedded? I would greatly appreciate any help/reference/pointers.
Thanks,
Dinesh.

More precisely, let $S$ be a finite set and let $f : S \times S \to S$ be a function.  How do we determine the smallest abelian group $(G, +)$ for which there exist functions $g : S \to G$ and $h : G \to S$ such that $f(x, y) = h(g(x) + g(y))$?  
 A: Thanks to all of you for your responses. For some reason (not enough rep points?), I don't see an "add comment" and so am posting this as an answer.
@Barton: I am interested in distributed function reconstruction where $x$ and $y$ are separately communicated to a computer who is interested in computing $f(x,y)$ and the problem is to minimize the rate of transmission of $x$ and $y$. I have a scheme that can do this whenever the function to be reconstructed is the group operation of some Abelian group (based on linear codes over that group). For other functions, I simply argue that they can be "embedded" in some group and thus can be reconstructed. My formal notation for this is very cumbersome and I was merely wondering if there is a neater way to characterize this notion. Towards this end, I would be interested in the following problem too: Given $f(x,y)$, is there an easy way to characterize all the Abelian groups (not necessarily the smallest) in which it can be embedded?
@Figueroa-O'Farrill: It is true that we need the function to be symmetric. Thanks for pointing it out.
A: To attempt to stir things up, I will suggest a different direction.  The hope is that someone else will recognize something which will steer this answer back towards the original question.
I once had to present some work of Zamjatin on undecidability of certain first-order theories in the language of groups.  Zamjatin had an interesting technique of emdedding a finite graph into a product (perhaps power) of groups.  This was an introduction for me into the general topic of interpretation or embeddability of one theory into another.  While my advisor (Ralph McKenzie) has results that deal more with infinite structures, it could be that there was some work done in the finite case as well, perhaps for Abelian groups.
(Now we'll see what storm this butterfly creates.)
Gerhard "Ask Me About System Design" Paseman, 2010.02.09
