HomFinder Class Reference

#include <homfinder.H>

List of all members.

---

Detailed Description

HomFinder class: looks for all reasonable homomorphisms between two graded algebras.

Given A=*source and B=*target, this will (help) find all homomorphisms between A and B which

• are isomorphisms in degree 1
• turn B into a finitely generated A-module.

In the comments, we shall say that f and g are equivalent when:

• they have the same kernel
• the images of f and g generate the same ideal in B. In other words, the identity of B induces an isomorphism between B/ <f(A)> and B/ <g(A)>. So if we want to find a minimal set of elements in B which together with the images of the generators of A will be generators of B (ie a basis for B/ <f(A)>) then the answer will be the same with f or with g.

Also, we shall say that a variable is polynomial if it does not appear in the relations.

In order to use this, the normal procedure is to:

• set source and target
• call init()
• call start()
• call define_polynomial_variables(). At this point, a bunch of solutions have been found, but not quite all of them: in order to reduce the time needed to complete the calculation (which rapidly becomes silly if you want all solutions), we only keep some representatives. Any actual solution corresponds to at least one representative, in the sense that they agree on non-polynomial variables, and on polynomial variables they agree modulo the ideal generated by the images of non-polynomial variables. (see below)
• call identify() and see if there is only one equivalence class
• if not, you can run more tests like test_steenrod() or restrict_to_elemab() in order to get rid of inconsistent solutions.
• If at this point, there is only one equivalence class, you can add missing variables to A (and thus obtain an algebra A') and extend the homomorphisms so as to make them surjective. Then run identify() again.
• If there is only one equivalence class at this point, you should check whether the polynomial variables are still polynomial in A'/ker f. If so, it is easy to see that taking other representatives in step 4 above would not have changed the result. The computation is complete !

Definition at line 61 of file homfinder.H.

Public Member Functions
	HomFinder (GradedAlgebra< F_2 > *thesource, GradedAlgebra< F_2 > *thetarget)
void	read_solutions_from (ifstream &file)
	reads from file
void	write_solutions_to (ofstream &file)
	writes to file
void	init ()
	sets up some of the data
void	start ()
	sets up the possible values for the variables showing up in the relations
void	define_polynomial_variables ()
	sets up the remaining variables -- Step 3 and Test 1
void	define_polynomial_variables_brutally ()
	Step 3 and Test 1 without the time-saving trick.
void	old_define_polynomial_variables ()
void	identify ()
	classify the solutions up to equivalence
long	weight (const Polynomial< F_2 > &relation, const AffineHomomorphism< F_2 > &phi)
	gives an integer measuring the complexity of 'relation'
void	sort ()
	sorts the relation in *source
void	test_steenrod ()
	checks if the kernels are stable under the steenrod operations
void	restrict_to_elemab (ifstream &res_file)
	see if the kernels are compatible with restriction to elementary abelian subgroups
void	get_equivalence_class (const list< AffineHomomorphism< F_2 > > &homs, const AffineHomomorphism< F_2 > &f)
	erase 'solutions' and replace it with those homs with are equivalent to f
bool	polvars_are_involved_in (const AffineHomomorphism< F_2 > &f)
	checks if the polynomial variables show up in the kernel of f
long	extend (AffineHomomorphism< F_2 > &f)
	extends both *source and f so as to make f surjective
long	extend_all ()
	extends both *source and all solutions so they become surjective
bool	polynomial_test ()
	perform Test 2
void	compute_all_kernels ()
	what is says, really
Public Attributes
bool	verbose
bool	very_verbose
GradedAlgebra< F_2 > *	source
const GradedAlgebra< F_2 > *	target
list< AffineHomomorphism< F_2 > >	solutions
ZZ	solution_count
	the number of solutions found
Private Member Functions
ZZ	populate_GL (long n)
	computes (=lists) all invertible matrices
ZZ	filter_GL ()
	keep only the compatible matrices
void	set_hom_from_matrix (AffineHomomorphism< F_2 > &phi, const list< long > &basics, const Matrix< F_2 > &M)
	defines a homomorphism from a matrix
void	set_f_from_matrix (const Matrix< F_2 > &M)
void	set_f_from_integer (ZZ code)
void	branch (const AffineHomomorphism< F_2 > &phi, list< Polynomial< F_2 > >::iterator next, long depth)
	recursively try all possibilities
Private Attributes
list< Matrix< F_2 > >	GL
list< long >	basic_variables
list< long >	target_basic_variables
list< long >	higher_variables
list< long >	polvars
map< long, Tuple< Polynomial< F_2 > > >	monomials
	contains an F_2 basis of *source, in certain degrees
ZZ	possibilities
GradedAlgebra< F_2 >	basic_source
	a copy of *source, with only the basic relations
list< Polynomial< F_2 > >	higher_relations
AffineHomomorphism< F_2 >	f

---

Member Function Documentation

void HomFinder::branch (  const AffineHomomorphism< F_2 > &  phi, list< Polynomial< F_2 > >::iterator  next, long  depth )  [private]

recursively try all possibilities This is at the heart of start(). Parameters: phi  : a partially defined homomorphism, for which some of the relations in *source are compatible (ie phi(relation)=0). next  : the next relation for which phi is (possibly) not compatible yet. Given this, it could be that phi is defined on *next, and we only have to check if phi(*next)=0. If so, we call branch() recursively on the next relation. If not, we return. Or, if phi is not defined on *next, we try all the possibilities to extend it and call branch() recursively on each. Finally, of course, if next points to the end of the list, we have a solution, and we add it to 'solutions'. Definition at line 293 of file homfinder.cpp. References AbstractHomomorphism< K >::has_image_set(), GradedAlgebra< K >::hom_degrees, Polynomial< K >::is_zero(), monomials, AbstractHomomorphism< K >::of(), AffineAlgebra< K >::one(), AffineAlgebra< K >::reduced_form(), AbstractHomomorphism< K >::set_image(), Polynomial< K >::sets_to_zero(), solution_count, and SimpleAlphabet::variables_in_use(). Referenced by start().

void HomFinder::compute_all_kernels (   )

what is says, really This computes the kernels of all the solutions. Definition at line 1109 of file homfinder.cpp.

void HomFinder::define_polynomial_variables (   )

sets up the remaining variables -- Step 3 and Test 1 After start() has been called, we have a list of partially defined homomorphisms from *source to *target. The variables left out do not show up in the relations, so they generate a polynomial algebra. Any choice for their images gives a well defined homomorphism ! This method tries some of them (see comments to HomFinder for more information or better, the accompanying paper), and only keeps the choices for which *target is finitely generated as a *source-module. This is Step 3 and Test 1 combined together, in the notations of the paper. The list 'solutions' is updated. Definition at line 562 of file homfinder.cpp. References GradedAlgebra< K >::add_relation(), AffineAlgebra< K >::find_grobner_basis(), AffineAlgebra< K >::fix_alphabets(), GradedAlgebra< K >::hom_degrees, GradedAlgebra< K >::list_monomials(), AffineAlgebra< K >::one(), Polynomial< K >::sets_to_zero(), Tuple< T >::size(), solution_count, and SimpleAlphabet::variables_in_use().

void HomFinder::define_polynomial_variables_brutally (   )

Step 3 and Test 1 without the time-saving trick. Similar to define_polynomial_variables() but really tries ALL of them, which creates A LOT of solutions. However, in certain cases, there is no other choice. Definition at line 655 of file homfinder.cpp. References AffineAlgebra< K >::fix_alphabets(), GradedAlgebra< K >::hom_degrees, GradedAlgebra< K >::list_monomials(), AffineAlgebra< K >::one(), Polynomial< K >::sets_to_zero(), Tuple< T >::size(), and solution_count.

long HomFinder::extend (  AffineHomomorphism< F_2 > &  f  )

extends both *source and f so as to make f surjective For each variable in B which is nonzero in B/<f(A)>, we add a variable with the same name in A, and we extend f in the obvious way. This returns the number of variables added. Definition at line 991 of file homfinder.cpp. References GradedAlgebra< K >::add_relation(), AffineAlgebra< K >::find_grobner_basis(), AffineAlgebra< K >::fix_alphabets(), AffineAlgebra< K >::get_variables(), GradedAlgebra< K >::hom_degrees, Polynomial< K >::is_zero(), SimpleAlphabet::nameof(), GradedAlgebra< K >::new_variable(), AbstractHomomorphism< K >::of_generator(), AffineAlgebra< K >::reduced_form(), AbstractHomomorphism< K >::set_image(), and SimpleAlphabet::variables_in_use(). Referenced by polynomial_test().

long HomFinder::extend_all (   )

extends both *source and all solutions so they become surjective This is similar to extend(), except that we process all the solutions at once. For this to make sense, we assume that they are all equivalent (so that *source extends to the same algebra for all of them). Another difference is that we compute all the kernels if there are indeed new variables showing up (and only in this case). Definition at line 1028 of file homfinder.cpp. References GradedAlgebra< K >::add_relation(), AffineAlgebra< K >::find_grobner_basis(), AffineAlgebra< K >::fix_alphabets(), AffineAlgebra< K >::get_variables(), GradedAlgebra< K >::hom_degrees, Polynomial< K >::is_zero(), SimpleAlphabet::nameof(), GradedAlgebra< K >::new_variable(), AbstractHomomorphism< K >::of_generator(), AffineAlgebra< K >::reduced_form(), and SimpleAlphabet::variables_in_use().

ZZ HomFinder::filter_GL (   )  [private]

keep only the compatible matrices Must be invoked AFTER init() (so after populate_GL()). We keep only those matrices which are compatible with the basic relations. Returns: the number of matrices kept Definition at line 85 of file homfinder.cpp. References basic_source, Matrix< T >::inverse(), AffineHomomorphism< K >::is_well_defined(), AffineHomomorphism< K >::make_identity(), and set_hom_from_matrix(). Referenced by init().

void HomFinder::get_equivalence_class (  const list< AffineHomomorphism< F_2 > > &  homs, const AffineHomomorphism< F_2 > &  f )

erase 'solutions' and replace it with those homs with are equivalent to f Typically this is called when there is only one homomorphism left in 'solutions'. Then one may want to call this with homs= some backup of a bunch of solutions obtained at some earlier stage, and f= the remaining solution. The result is that 'solutions' contains all the homomorphisms in 'homs' which are equivalent to f. Definition at line 950 of file homfinder.cpp. References AffineHomomorphism< K >::factors_through(), AffineHomomorphism< K >::is_essentially_contained_in(), AffineHomomorphism< K >::kernel, and solution_count.

void HomFinder::identify (   )

classify the solutions up to equivalence Call this after init(), start(), and define_polynomial_variables(). This compares the kernels and images and keeps exactly one solution up to equivalence. Definition at line 740 of file homfinder.cpp. References solution_count.

void HomFinder::init (   )

sets up some of the data What this is doing: populate basic_variables (ie those of degree 1), higher_variables (all the others), and target_basic_variables populate GL, ie compute all invertible matrices of the right size (= number of basic variables), then call filter_GL() to keep only the ones giving a well defined homomorphism. put the basic relations in basic_source, and the others in the list higher_relations. See also: basic_source. Sort the relations in *source (note that *source is not const !) so as to speed up the search. Definition at line 133 of file homfinder.cpp. References GradedAlgebra< K >::add_relation(), basic_source, filter_GL(), Ideal< K >::generators, GradedAlgebra< K >::hom_degrees, GradedAlgebra< K >::list_monomials(), monomials, populate_GL(), AffineAlgebra< K >::relations, sort(), Ideal< K >::variable_shows_up(), and SimpleAlphabet::variables_in_use().

bool HomFinder::polvars_are_involved_in (  const AffineHomomorphism< F_2 > &  f  )

checks if the polynomial variables show up in the kernel of f It is assumed that the source of f is *source, and that the kernel of f has already been computed. Definition at line 980 of file homfinder.cpp. References AffineHomomorphism< K >::kernel, and Ideal< K >::variable_shows_up(). Referenced by polynomial_test().

bool HomFinder::polynomial_test (   )

perform Test 2 We extend each solution so that it becomes surjective, and then we check whether the polynomial variables are still polynomial in A/ker(solution). If this is so for all the solutions, this returns true, otherwise this returns false at once. The kernels are all computed after this (only the kernels of the homomorphisms that we start with are kept, not the kernels of the extended homomorphisms). Definition at line 1077 of file homfinder.cpp. References extend(), GradedAlgebra< K >::kill_top_variable(), AffineAlgebra< K >::one(), polvars_are_involved_in(), and Polynomial< K >::sets_to_zero().

ZZ HomFinder::populate_GL (  long  n  )  [private]

computes (=lists) all invertible matrices Definition at line 50 of file homfinder.cpp. References AbstractHomomorphism< K >::clear(), and Matrix< T >::is_invertible(). Referenced by init().

void HomFinder::read_solutions_from (  ifstream &  file  )

reads from file Definition at line 13 of file homfinder.cpp. References solution_count.

void HomFinder::restrict_to_elemab (  ifstream &  res_file  )

see if the kernels are compatible with restriction to elementary abelian subgroups Definition at line 895 of file homfinder.cpp. References Polynomial< K >::is_zero(), Tuple< T >::resize(), and solution_count.

void HomFinder::set_hom_from_matrix (  AffineHomomorphism< F_2 > &  phi, const list< long > &  basics, const Matrix< F_2 > &  M )  [private]

defines a homomorphism from a matrix This defines the homomorphism phi on the basic variables only, using the given matrix, which expresses the image of each basic variable in terms of the basic variables in *target. Parameters: phi  : an AffineHomomorphism whose source is basic_source (or 'source', or any GradedAlgebra<F_2> with the same variables as those), and whose target is 'target'. It is assumed that phi is completely undefined (though this is not a requirement). Definition at line 202 of file homfinder.cpp. References monomials, Table< T >::nlines(), AffineAlgebra< K >::one(), AbstractHomomorphism< K >::set_image(), and Polynomial< K >::sets_to_zero(). Referenced by filter_GL().

void HomFinder::sort (   )

sorts the relation in *source Relying on weight(), this puts the relations in *source in such an order as to minimalize the number of choices to make in start(). Definition at line 804 of file homfinder.cpp. References AffineAlgebra< K >::one(), AbstractHomomorphism< K >::set_image(), Polynomial< K >::sets_to_zero(), and weight(). Referenced by init().

void HomFinder::start (   )

sets up the possible values for the variables showing up in the relations This writes into 'solutions' a bunch of partially defined homomorphisms from *source to *target. These are only defined on the variables which show up in the relations of *source (or are of degree 1), and in fact all the possibilities for such homomorphisms are listed up to equivalence. Much more precisely, any well-defined homomorphism from this subalgebra of *source to *target, which is an isomorphism in degree 1, is equivalent to at least one homomorphism in the list 'solutions', after this method is called. (We need to add 'equivalent to' rather than 'equal to' because during init(), the call to filter_GL() has got rid of some choices for the variables in degree 1 which would give rise to equivalent final solutions.) Relies on branch() Definition at line 241 of file homfinder.cpp. References branch(), solution_count, AffineHomomorphism< K >::source, and AffineHomomorphism< K >::target.

void HomFinder::test_steenrod (   )

checks if the kernels are stable under the steenrod operations Definition at line 848 of file homfinder.cpp. References GradedAlgebra< K >::add_relation(), AffineAlgebra< K >::find_grobner_basis(), UnstableAlgebra::fix_alphabets(), UnstableAlgebra::is_saturated(), Polynomial< K >::is_zero(), AffineAlgebra< K >::reduced_form(), and solution_count.

long HomFinder::weight (  const Polynomial< F_2 > &  relation, const AffineHomomorphism< F_2 > &  phi )

gives an integer measuring the complexity of 'relation' Given a partially defined homomorphism phi, this method gives an integer which is all the larger as there are possibilities to extend phi in such a way that phi(relation)=0. So this is all the larger as there are variables in 'relation' for which phi is not defined, and as *target has a large dimension in the corresponding degrees. This is used by sort(). Definition at line 779 of file homfinder.cpp. References AbstractHomomorphism< K >::has_image_set(), GradedAlgebra< K >::hom_degrees, Polynomial< K >::involves_variable(), and monomials. Referenced by sort().

void HomFinder::write_solutions_to (  ofstream &  file  )

writes to file Definition at line 34 of file homfinder.cpp. References solution_count.

---

Member Data Documentation

GradedAlgebra<F_2> HomFinder::basic_source [private]

a copy of *source, with only the basic relations it is convenient to store the basic relations in an algebra, so that AffineHomomorphism::is_well_defined() may be used. Definition at line 77 of file homfinder.H. Referenced by filter_GL(), and init().

map< long, Tuple< Polynomial<F_2> > > HomFinder::monomials [private]

contains an F_2 basis of *source, in certain degrees Definition at line 69 of file homfinder.H. Referenced by branch(), init(), set_hom_from_matrix(), and weight().

ZZ HomFinder::solution_count

the number of solutions found Instead of using solutions.size(), which returns a funny type which may well be a 32 bit unsigned integer on some implementations, we keep track of the size in a ZZ. Indeed the number of solutions may easily exceed 4 billions (especially when experimenting new things...) Definition at line 146 of file homfinder.H. Referenced by branch(), define_polynomial_variables(), define_polynomial_variables_brutally(), get_equivalence_class(), identify(), read_solutions_from(), restrict_to_elemab(), start(), test_steenrod(), and write_solutions_to().

---

The documentation for this class was generated from the following files:

• include/homfinder.H
• src/homfinder.cpp

---