I'm posting this question since what I've come up sounds twisted!
Check if $g: S_3 \rightarrow \mathbb{Z}_2$ is an homomorfism, given that $$g(id)=0,\ g(12)=1,\ g(13)=1,\ g(23)=1,\ g(123)=0,\ g(132)=0$$
We want to check if $g(s_1 \circ s_2) = g(s_1) + g(s_2)$, where $s_1,s_2 \in S_3$.
Since I can't find a choice of $s_1,s_2$ such that the equality above is not satisfied, I go for a positive proof. Also, since $\circ$ is not commutative, $30$ cases should be tested. I decided to try to see some patterns.
Notice that if at least one between $s_1,s_2$ is the $id$ then the equality is trivially satisfied as $$\text{lhs} = g(s_i \circ id) = g(s_i) = \text{rhs}$$
Also, each transposition is mapped to $1$.
Thus the cases left are: two transpositions, a transposition and a 3-cycle, two 3-cycles.
I used two assumptions that I didn't prove but seemed true in $S_3$ (!):
- if you compose two transpositions then you either get the $id$ permutation or a 3-cycle.
- if you compose a transposition and a 3-cycle you'll get a transposition.
Now:
if $s_1,s2$ are two transpositions then because of (1.) on the lhs the argument of $g$ is either the $id$ or a 3-cycle, both of which map to $0$; on the rhs you'll have the sum of two transpositions, i.e. $1 + 1 \equiv_2 0$.
if $s_1, s_2$ are a transposition and a 3-cycle then because of (2.) you get a transposition, that $g$ maps to $1$. On the rhs, you'll have a $1 + 0$.
if $s_1, s_2$ are both a 3-cycle, you'll have the $id$ permutation on the lhs, and on the rhs $0 + 0$
Is that correct? Does a simpler approach exist?
I think you have simplified things reasonably well. To summarize your approach:
In $S_3$ you have 1 1-cycle, 3 2-cycles, and 2 3-cycles. $g$ maps all of the 2-cycles to $1$ and maps everything else to $0$.
So what's the product of 2 2-cycles? It is either a 3-cycle or a 1-cycle. This means that $g$ is multiplicative on two cycles. You can reason through the other cases similarly. This should help speed up a brute force solution.