Skip to content

Instantly share code, notes, and snippets.

@MartinThoma
Created August 27, 2013 13:25
Show Gist options
  • Save MartinThoma/6353473 to your computer and use it in GitHub Desktop.
Save MartinThoma/6353473 to your computer and use it in GitHub Desktop.
Automatically find all homomorphisms between (Z/nZ, *) and (Z/mZ, *). This can easily be adjusted to find homomorphisms between (Z/nZ, +) and (Z/mZ, +)
#!/usr/bin/env python
# -*- coding: utf-8 -*-
def isGroupHomomorphism(phi, group1, group2, verbose=False):
for a, b in product(group1['set'], group2['set']):
inner = group1['operator'](a, b)
outer = group2['operator'](phi(a), phi(b))
if verbose:
print("f(%i) = %i, f(%i) = %i f(%i)=%i=%i" % (a, phi(a), b, phi(b), inner, phi(inner), outer))
if phi(inner) != outer:
return False
return True
def getZModPlusGroup(n):
group = {}
group['name'] = "Z/" + str(n) + "Z"
group['set'] = list(range(1,n))
group['operator'] = lambda x, y: (x*y)%n
return group
if __name__ == "__main__":
group1 = getZModPlusGroup(5)
group2 = getZModPlusGroup(5)
from itertools import product
checkedCounter = 0
homCounter = 0
candidates = len(group2['set'])**len(group1['set'])
if candidates > 10000000:
print("Warning! This will test %i candidates!" % candidates)
for t in product(group2['set'], repeat=len(group1['set'])): #mapping from group1 to elements from group2
checkedCounter += 1
phi = lambda x: t[x-1] #* / +
if 1==2 and phi(0) != 0:
continue
else:
if isGroupHomomorphism(phi, group1, group2):
#isGroupHomomorphism(phi, group1, group2, True)
homCounter += 1
print(group1['name'] + ":\t" + str(group1['set']))
print(group2['name'] + ":\t" + str(t))
print "#"*25
print("Checked %i candidates. %i of them were homomorphisms." % (checkedCounter, homCounter))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment