DerivationAnalyzer Class Reference

#include <derive.H>

Inheritance diagram for DerivationAnalyzer:

List of all members.

---

Detailed Description

a class (mostly) for computing the kernel of a derivation

Given a GradedAlgebra over F_2, here written *source, and a derivation d on it, the chief purpose of this is to compute the kernel of d, which is a subalgebra.

However, this is mostly an abstract class. One should create a class which inherits from this and which is optimized for the case at hand (this is what we do with MilnorAnalyzer). The methods which can be re-used without modifications are:

• constant_subalgebra(), which conducts the right operations with syzygies,
• write_gens(), which is useful for listing generators (see below).

We provide more methods, which were a first attempt at solving the general problem, but considerations of efficiency will prevent them from working on large examples (the sensitivity on "large" is exponential).

Important: *source must have a Grobner basis.

Tricky Notation: we call 'squares' the subalgebra of *source generated by all the squares. Thus we talk of *source viewed as a squares-module, etc. However, in a class which inherits from DerivationAnalyzer, the user will be likely to use the word 'squares', as well as the algebra with the same name, in the more general sense of 'elements which are in the kernel of the derivation for some trivial reason'.

Simple use of this class:The first idea is, thus, to consider *source as a finitely generated module over 'squares', since the derivation d on *source is squares-linear (we are in char=2). The problem then reduces to a computation of syzygies. Helped by setup() and coords_of(), the user can setup d with something like

   DerivationAnalyzer der;
   der.setup( &A );
   long i;
   for(i=1; i< der.mod_gens.size(); i++)
     der.d[i]= der.coords_of( A.Sq(1, der.mod_gens[i]) );

(in this example A is an UnstableAlgebra and d= Sq^1). Then one may call constant_subalgebra(), and after execution find the kernel of d as the algebra 'constants' together with the inclusion homomorphism cs_inclusion. The variables will be named after the variables in *source but prefixed with an s (as in square) for those which map to, well, the squares of the variables in *source -- while the other generators will be named according to the arguments you pass to constant_subalgebra().

Possible improvements: A modification that is worth doing (and we do so in MilnorAnalyzer) is to start by checking which variables in *source satisfy d()=0, and put them in the algebra of squares. This requires modifying setup() (the changes are rather easy, since write_gens() has a flexible syntax). Then one needs to modify coords_of() in order to take the changes into account.

We recommend reading the comments to constant_subalgebra() now, for a more formal explanation.

Definition at line 73 of file derive.H.

Public Member Functions
void	setup (GradedAlgebra< F_2 > *thesource)
	sets up the data
void	write_gens (list< Polynomial< F_2 > > &result, long ext, long first, long last)
	used by setup
virtual multiPolynomial< F_2 >	coords_of (PowProd P)
virtual multiPolynomial< F_2 >	coords_of (const Polynomial< F_2 > &P)
	given a member of source, this computes its coordinates when source is viewed as a squares-module
void	constant_subalgebra (string prefix, long offset)
	does the actual computation using syzygies
virtual	~DerivationAnalyzer ()
	virtual destructor needed
Public Attributes
GradedAlgebra< F_2 > *	source
	the algebra on which there is a derivation
GradedAlgebra< F_2 >	squares
	the subalgebra of squares
AffineHomomorphism< F_2 >	sq_inclusion
	the inclusion homomorphism of squares into *source
Tuple< multiPolynomial< F_2 > >	d
	the derivation itself
GradedAlgebra< F_2 >	constants
	the algebra of constants, ie elements x satisfying d(x)=0
AffineHomomorphism< F_2 >	cs_inclusion
	the inclusion homomorphism of constants into *source
Tuple< Polynomial< F_2 > >	mod_gens
	generators for source as a module over the subalgebra of squares
map< PowProd, long >	index_of
	this will find a PowProd in the tuple mod_gens and return its index

---

Constructor & Destructor Documentation

virtual DerivationAnalyzer::~DerivationAnalyzer (   )  [inline, virtual]

virtual destructor needed Definition at line 170 of file derive.H.

---

Member Function Documentation

void DerivationAnalyzer::constant_subalgebra (  string  prefix, long  offset )

does the actual computation using syzygies The precise assumptions for this to work are as follows: (the information below should be enough to rewrite setup() and coords_of(), if needed) *source is a graded algebra, with a grobner basis already computed. 'squares' is a polynomial algebra (no relations, in principle), and sq_inclusion turns *source into a squares modules which is finitely generated. mod_gens contains elements which are generators for *source as a squares-modules, and mod_gens[0] is the unit of *source d[i] gives the image of mod_gens[i] under some differential d (whose kernel we are trying to figure out). given an element x in *source, coords_of(x) gives its coordinates as a squares-linear combination of the elements in mod_gens. In particular d[i] has been written (as a tuple) with the same conventions. d is zero on 'squares', and so it is squares-linear. 'constants' initially is "equal" (that is, mathematically equal) to 'squares', and cs_inclusion is its inclusion into *source cs_inclusion has called populate_associated_algebra() already, and was not altered since. Check carefully all this before using the method (the last point in particular is easy to forget). Todo: give a reference to a paper Parameters: prefix,offset  : the new variables to create will be named prefix_offset+1, ..., prefix_offset+n. Returns: Definition at line 130 of file derive.cpp. References Polynomial< K >::alphabet, constants, cs_inclusion, d, Ideal< K >::generators, multiIdeal< K >::generators, multiIdeal< K >::grobnerize_with_coefficients(), GradedAlgebra< K >::hom_degree_of(), GradedAlgebra< K >::hom_part_of(), Polynomial< K >::is_zero(), AffineHomomorphism< K >::kernel, AffineHomomorphism< K >::maps_onto(), mod_gens, GradedAlgebra< K >::new_variable(), Table< T >::nlines(), AbstractHomomorphism< K >::of(), AffineHomomorphism< K >::populate_associated_algebra(), AffineAlgebra< K >::reduced_form(), AffineAlgebra< K >::relations, Table< T >::resize(), AbstractHomomorphism< K >::set_image(), Polynomial< K >::sets_to_zero(), Tuple< T >::size(), source, sq_inclusion, multiIdeal< K >::syzygy(), and SimpleAlphabet::variables_in_use(). Referenced by MilnorAnalyzer::start().

multiPolynomial< F_2 > DerivationAnalyzer::coords_of (  const Polynomial< F_2 > &  P  )  [virtual]

given a member of source, this computes its coordinates when source is viewed as a squares-module Reimplemented in MilnorAnalyzer. Definition at line 115 of file derive.cpp. References Polynomial< K >::coeffs, mod_gens, multiPolynomial< K >::resize(), multiPolynomial< K >::set_alphabet(), Tuple< T >::size(), and squares. Referenced by MilnorAnalyzer::coords_of().

void DerivationAnalyzer::setup (  GradedAlgebra< F_2 > *  thesource  )

sets up the data This computes a number of things, including the generators 'mod_gens' of *source when viewed as a squares-module. Quite simply, if *source is generated by x, y and z, then the generators taken will be I (one), x, y, z, xy, xz, yz and xzy. The function coords_of() knows this, and computes the coordinates of a member of *source in this basis. Definition at line 5 of file derive.cpp. References constants, cs_inclusion, d, AffineAlgebra< K >::get_variables(), GradedAlgebra< K >::hom_degrees, index_of, mod_gens, SimpleAlphabet::nameof(), GradedAlgebra< K >::new_variable(), AffineAlgebra< K >::one(), AffineHomomorphism< K >::populate_associated_algebra(), Tuple< T >::resize(), AbstractHomomorphism< K >::set_image(), AffineHomomorphism< K >::source, source, sq_inclusion, squares, AffineHomomorphism< K >::target, SimpleAlphabet::variables_in_use(), and write_gens().

void DerivationAnalyzer::write_gens (  list< Polynomial< F_2 > > &  result, long  ext, long  first, long  last )

used by setup Recursive function whose job is to pick the generators, see setup() and example below. Parameters: result  : a list of polynomials, will be updated with the answer. ext  : this triggers the computation of the generators which are product of 'ext' many variables (the funny name is here because the code is mostly a copy & paste of something related to exterior powers, sorry). first,last  : take only into consideration the variables whose index is between 'first' and 'last'. Example: If *source is generated by x, y and z, then write_gens(res, 1, 1, 3) writes x, y and z in res, while write_gens(res, 2, 2, 3) writes yz. Definition at line 56 of file derive.cpp. References AbstractHomomorphism< K >::clear(), AffineAlgebra< K >::one(), and source. Referenced by MilnorAnalyzer::re_setup(), setup(), and MilnorAnalyzer::setup_for_Sq1().

---

Member Data Documentation

GradedAlgebra<F_2> DerivationAnalyzer::constants

the algebra of constants, ie elements x satisfying d(x)=0 Definition at line 84 of file derive.H. Referenced by constant_subalgebra(), and setup().

AffineHomomorphism<F_2> DerivationAnalyzer::cs_inclusion

the inclusion homomorphism of constants into *source Definition at line 86 of file derive.H. Referenced by constant_subalgebra(), and setup().

Tuple< multiPolynomial<F_2> > DerivationAnalyzer::d

the derivation itself Definition at line 82 of file derive.H. Referenced by constant_subalgebra(), and setup().

map< PowProd, long > DerivationAnalyzer::index_of

this will find a PowProd in the tuple mod_gens and return its index Definition at line 94 of file derive.H. Referenced by setup().

Tuple< Polynomial<F_2> > DerivationAnalyzer::mod_gens

generators for source as a module over the subalgebra of squares See also: setup() Definition at line 92 of file derive.H. Referenced by constant_subalgebra(), coords_of(), and setup().

GradedAlgebra<F_2>* DerivationAnalyzer::source

the algebra on which there is a derivation Definition at line 76 of file derive.H. Referenced by constant_subalgebra(), setup(), and write_gens().

AffineHomomorphism<F_2> DerivationAnalyzer::sq_inclusion

the inclusion homomorphism of squares into *source Definition at line 80 of file derive.H. Referenced by constant_subalgebra(), and setup().

GradedAlgebra<F_2> DerivationAnalyzer::squares

the subalgebra of squares Definition at line 78 of file derive.H. Referenced by coords_of(), and setup().

---

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

• include/derive.H
• src/derive.cpp

---