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?

  • $\begingroup$ Can you provide an example of what you have in mind? Why do you think (or why not) one can recover information about $G$? About what motivated the question? $\endgroup$ – Mariano Suárez-Álvarez Jan 15 '10 at 0:26
  • $\begingroup$ Sure! An example: write n in base 5; set f(n) = 0 if the last nonzero digit is 2 or 4, f(n) = 1 otherwise. (This factors through (Z/5)*.) I actually don't really know either way if you can recover information about G; the motivation comes from some discussion over at Tim Gowers' blog on the latest polymath project. $\endgroup$ – Harrison Brown Jan 15 '10 at 1:01

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.

  • $\begingroup$ I guess that's true -- take f to be always 0, for instance. $\endgroup$ – Harrison Brown Jan 15 '10 at 0:14

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}$.

  • $\begingroup$ Ah, I think you may be misunderstanding the question. The function from G to {0,1} isn't a group homomorphism, just a function. $\endgroup$ – Harrison Brown Jan 15 '10 at 11:10
  • $\begingroup$ Whoops! I thought that "monoid homomorphism" in the title referred to the function $f$ instead of the map $M \rightarrow G$. $\endgroup$ – mediocrates Jan 15 '10 at 11:50
  • $\begingroup$ I can understand why it would be confusing -- I should probably change the title (and maybe make the question a little clearer) $\endgroup$ – Harrison Brown Jan 15 '10 at 11:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.