Wednesday 16 May 2007

gr.group theory - "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))$?

No comments:

Post a Comment