Finding the codomain of a monoid homomorphism - MathOverflow

Finding the codomain of a monoid homomorphism

2010-01-14T23:13:37Z

We have a monoid M, and a function $f: M \rightarrow \{0, 1\}$. We're promised that this function factors through a (surjective) homomorphism to a finite abelian group (considered as a commutative monoid), $M \rightarrow G \rightarrow \{0, 1\}$, but not told what the group is.

Can we recover any information about the structure of G, just given $f$? I'm particularly interested in the case where M is the monoid of positive integers under multiplication.

[Edit: As I realized after reading Mariano's comment, we can take f = 0 identically and obtain no information whatsoever about G. So a better question might be, under what assumptions on f can we recover G? Or information about G? In particular, if the function from $G \rightarrow \{0, 1\}$ takes on its two values approximately equally often, can we say anything?]

More generally, and more interestingly: Can we recover any information about the structure of G, assuming that the black-box is allowed to lie about a small fraction of values of the function?

Answer by Mariano Suárez-Alvarez for Finding the codomain of a monoid homomorphism

2010-01-14T23:21:05Z

Every morphism $M\to G$ into a group factors through the group completion $\hat M$ (a.k.a. Grothendieck construction) of $M$. It follows that $G$ is a quotient of $\hat M$ and that $f$ factors through $\hat M$.

If $f$ is an arbitrary function, I don't think you can get any information about the structure of $G$, except that it is a quotient of $\hat M$---and this information is not really provided by $f$, of course.

Answer by Justin Shih for Finding the codomain of a monoid homomorphism

2010-01-15T10:58:25Z

As has been stated, $M \rightarrow G$ factors via the group completion $\hat{M}$. Furthermore, since $G$ is abelian, the map $\hat{M} \rightarrow G$ factors via the abelianization $\hat{M}/[\hat{M},\hat{M}]$ of $\hat{M}$. Since the composite of the maps $M \rightarrow \hat{M} \rightarrow \hat{M}/[\hat{M},\hat{M}]$ is already known, $f$ is uniquely determined by the map $\hat{M}/[\hat{M},\hat{M}] \rightarrow G$, so we may assume $M$ to be an abelian group.

Since $f = 0$ gives us no information, we may assume that $f$ is onto. Suppose we have a $G$ so that $f$ factors via it, and let us write $f = pg$, where $g \colon M \rightarrow G$ and $p \colon G \rightarrow \{0,1\}$.

By $f = pg$ we must necessarily have $\ker(g) \subset \ker(f)$, so that $g$ is isomorphic to the canonical projection $M \rightarrow M/N$, where $N$ is a subgroup of $\ker(f)$. In addition, $|G|$ must be even. (If $f$ is onto, $p$ must take on the values $0$ and $1$ equally, since $|G| = 2|ker(p)|$.)

I claim this is all $f$ tells you. Given $f$, we've just shown that we must have that $g$ is isomorphic to modding out by a subgroup of $\ker(f)$, and that $|G|$ is even.

Conversely, given any map $g \colon M \rightarrow G$, whose kernel is a subgroup of $\ker(f)$, and such that $|G|$ is even, then the image of $\ker(f)$ will be of index 2 in $G$, so we can just compose this map with the map that mods out the image of $\ker(f)$ in $G$.

Edit: Oops, $G \rightarrow \{0,1\}$ is only a set map! Well then, let me at least try to contribute to the discussion! In this case, we can still assume $M$ to be an abelian group. If you can recover $G$ (assuming $G = M$ is not allowed), then certainly the kernel of $M \rightarrow G$ cannot have any subgroups, hence must be a cyclic group of order $p$. In the case where $M = \mathbb{Z}_+$ , then $\hat{M} = \mathbb{Q}_+$ which is torsion free, so no maps $f$ exist which allow you to recover $G$ entirely, unless we allow $G = \hat{M}$.