Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add tests for homomorphisms #5806

Open
ChrisJefferson opened this issue Sep 29, 2024 · 1 comment
Open

Add tests for homomorphisms #5806

ChrisJefferson opened this issue Sep 29, 2024 · 1 comment

Comments

@ChrisJefferson
Copy link
Contributor

A common mistake is for people to define ActionHomomorphisms which are not valid.

It isn't reasonable for us to test every ActionHomomorphism, but we could provide helper functions we can at least point people at. It might be possible in some cases where code fails to then run these to see if we can tell why it failed. There are two functions here, one that does a random check if 10,000 elements, and one that checks the full group (which will of course only work for small, finite, G and Omega).

I've had these pieces of code lying around for a while, I'm curious if anyone has any comments, before I polish them up and make a PR:

FullTestActionHomomorphism := function(G, Omega, act)
	local p1,p2,j;

	p1 := One(G);
	for j in Omega do
		if act(j,p1) <> j then
			Error("Identity: act(",j,",",p1, "<>",j);
		fi;
	od;

	for p1 in G do
		for j in Omega do
			if not(act(j,p1) in Omega) then
				Error("Closure: act(",j,",",p1, "not in Omega");
			fi;
		od;
	od;

	for p1 in G do
		for p2 in G do
			for j in Omega do
				if act(act(j,p1),p2) <> act(j,p1*p2) then
					Error("Homomorphism: act(act(",j,",",p1,"),",p2,") != act(",j,",",p1*p2,"))");
				fi;
			od;
		od;
	od;
end;


RandomTestActionHomomorphism := function(G, Omega, act)
	local p1,p2,j, loop;

	p1 := One(G);
	for loop in [1..10000] do
		j := Random(Omega);
		if act(j,p1) <> j then
			Error("Identity: act(",j,",",p1, "<>",j);
		fi;
	od;

	for loop in [1..10000] do
		p1 := Random(G);
		p2 := Random(Omega);
		if not(act(j,p1) in Omega) then
			Error("act(Closure: ",j,",",p1, "not in Omega");
		fi;
	od;

	for loop in [1..10000] do
		p1 := Random(G);
		p2 := Random(G);
		j := Random(Omega);
		if act(act(j,p1),p2) <> act(j,p1*p2) then
			Error("Homomorphism: act(act(",j,",",p1,"),",p2,") != act(",j,",",p1*p2,"))");
		fi;
	od;
end;



FullTestActionHomomorphism(SymmetricGroup(4), Arrangements([1..4], 4), OnTuples);
RandomTestActionHomomorphism(SymmetricGroup(4), Arrangements([1..4], 4), OnTuples);
FullTestActionHomomorphism(SymmetricGroup(4), Combinations([1..4], 3), OnSets);
RandomTestActionHomomorphism(SymmetricGroup(4), Combinations([1..4], 3), OnSets);
@hulpke
Copy link
Contributor

hulpke commented Oct 17, 2024

I agree that illegal actions are an recurring issue of "errors between keyboard and chair".

There is already TestIdentityAction that is used to map one point under the identity and catches situations of actions that are not well-defined. One could add more. The main problem I see is what tests to do in which situations, so that the tests do not impact performance.

  • Actions might be a low-level call to convert from an intractable group to a permutation group
  • Actions can be very expensive (say when acting on subgroups) and we don't want to do this for generic testing
  • How many tests would be plausible to do. Basically you want to do a far less if the routine is called within extra code. So maybe do it based on an assertion level >1.
  • Random might rely on a NiceMonomorphism that uses an action. Probably use PseudoRandom.

One cheap test would be for a fail in ``Permutation` (either image not found, or not a valid permutation and not throw an error about a list access a[fail] being illegal, but that an image wasn't found and that could mean that an action was ill defined.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants