3
$\begingroup$

More precisely, I am given a function $f:G\to H$ with the promise that it is a homomorphism. Is there an easy way to determine which homomorphism it is without looking through all of its values?

For example, when $G=\mathbb{Z}_2^n$ and $H=\mathbb{Z}_2$, a homomorphism $f$ is entirely characterized by an element of $\mathbb{Z}_2^n$, $s\in \{0,1\}^n$, such that $f(x)= s\cdot x$ where $\cdot$ is the inner product
($s_1x_1+s_2x_2+\dots+s_nx_n$).

I would be satisfied by an answer for abelian or cyclic groups.

  • 0
    Note, however, that the problem of "are $g\phi_1$ and $g\phi_2$ equal in $G$" is, in general, insoluble. It reduces to the word problem for the group ($g\phi_1=_Gg\phi_2\Rightarrow (g\phi_1)(g\phi_2)^{-1}=_G1$). Therefore, the method of "looking at where the generators go" is, in general, insoluble. Works for finite, automatic, etc. groups though...2011-07-29

3 Answers 3

0

Posting Arturo's comment in community wiki, because I think this is what the OP was actually looking for. (Not that this will lead to the question having an accepted answer, since the OP hasn't been seen for over a year.)

If I understand correctly what you want, you "only" need to know the value of $f$ at a minimal generating set. In your example, your element $s$ encodes the values of $f$ at the "basis" of $G$, the vectors $e_i$. If you know $f$ is a homomorphism, and you know its values at each element of a generating set, then you know its values, in principle, at every element of the group (this is exactly analogous to the fact that if you have a map between vector spaces, and you know it is a linear transformation, then knowing the value at a basis completely determines the map). [Arturo Magidin]

1

The problem of whether two maps define the same homomorphism is insoluble in general. Any (centreless) group $G$ with insoluble word problem gives a counter-example.

Note that the problem is always soluble for finite groups, and for finitely generated abelian groups, by brute-force methods. So this doesn't answer what you actually want to know. But it does answer the question as it is posed...

I will explain why such groups give counter-examples, but first I will explain what the word problem is.

Let $G$ be a group. Then if $\mathcal{P}=\langle X; \mathbf{r}\rangle$ is a presentation for $G$ (and we shall assume both $X$ and $\mathbf{r}$ are finite, but this isn't necessary (what you really need is "recursive")) then $\mathcal{P}$ has insoluble word problem if it is undecidable whether a word $w(X)=_{\mathcal{P}}1$ or not. This is invariant of the presentation, and so we can talk about the word problem for the group defined by $\mathcal{P}$, which is $G$ here.

Right, so, we have a group $G$ which has insoluble word problem. Now, $G$ embeds into $\operatorname{Aut}(G)$ because $G$ is centreless. Thus, $\operatorname{Aut}(G)$ has insoluble word problem (if a group has soluble word problem then so does all its subgroups, so reverse this to get what I just wrote). That is, if $G=\langle a, \ldots, c\rangle$ then it is undecidable whether the map $\phi: a\mapsto A, \ldots, c\mapsto C$ is the trivial automorphism or not. Therefore, we are done.

Two comments: Firstly, I think that the result should hold for all $G$ with insoluble word problem, not just those with trivial centre. Secondly, I would be interested to know if someone can come up with a similar counter-example for when the homomorphisms are proper. Does this just follow from groups where the subgroup membership problem is insoluble? (One can assume the subgroup in question is normal, e.g. for $g\in F_2\times F_2$ it is undecidable whether $g$ is in the kernel of the map $F_2\times F_2\rightarrow F_2\rightarrow H$ where $H$ has insoluble word problem.)

  • 0
    Thank you Sir for your kind supervisions devoted to our answers. Personally, I have learnt more from your remarkable points. Thanks and I appreciate you. :-)2013-03-19
0

The quickest way to compute a homomorphism is to compute the kernel. Then you will know that each coset of the kernel takes the same value in $H$, and you'll only have to do $[G:H]$ computations to completely define the homomorphism in terms of elements of $h$.

  • 0
    Indeed, $\psi$ is an inner automorphisms and $\phi$ is some homomorphism then $\phi$ and $\psi\phi$ have the same kernel.2013-03-05