3
$\begingroup$

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))$?

Improve this question
$\endgroup$
8
  • $\begingroup$ I don't understand what you mean by "embeddable." Is f required to satisfy some kind of symmetry with respect to the group or what? (Also, does f have a codomain which is the same finite set from which x and y are taken?) $\endgroup$
    – Qiaochu Yuan
    Commented Dec 29, 2009 at 2:28
  • 2
    $\begingroup$ Oh, I see; f is required to be the group operation. Do you mind if I rewrite your question to be a little clearer? $\endgroup$
    – Qiaochu Yuan
    Commented Dec 29, 2009 at 2:30
  • 1
    $\begingroup$ @Figueroa-O'Farrill, requiring that f is symmetric is neccesary, but it is also sufficient: let G be the free Z_2 module with basis S. Define g to be the obvious inclusion. Define h(x+y) = f(x,y) and define h arbitrarily on all the other elements of G. (Well definedness of h is equivalent to symmetry of f). Thus, we can "embed" f into an abelian group of size 2^|S|. $\endgroup$
    – Jason DeVito - on hiatus
    Commented Dec 29, 2009 at 3:12
  • 1
    $\begingroup$ @Jason: Don't you need Z_3, not Z_2, since otherwise x + x is a constant not depending on x? $\endgroup$
    – Reid Barton
    Commented Dec 29, 2009 at 3:57
  • 1
    $\begingroup$ @Barton: Yes, you're right. I wish there was a good way to edit comments! $\endgroup$
    – Jason DeVito - on hiatus
    Commented Dec 29, 2009 at 4:34

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Dinesh, the way I interpreted your question you wanted to interpret the elements of S as elements of the group in one way (the function g in the notation I gave above), but that embedding you give requires that we have two functions g_1, g_2 instead. Was this your intended meaning? If so, symmetry is unnecessary, but I fail to understand how this can actually help you accomplish what you want since you've only turned the problem of computing f into the problem of computing h, g_1, and g_2. $\endgroup$
    – Qiaochu Yuan
    Commented Dec 29, 2009 at 9:27
  • $\begingroup$ Qiaochu, I see the mistake in that argument. I was trying to get the cardinality of the group down from 2^|S| in Jason's argument to |S|^2. I will edit the post accordingly. Thanks. $\endgroup$
    – Dinesh
    Commented Dec 29, 2009 at 9:31
1
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .