USAGE.md

Using stabchain

So, these are some tips and tricks for using the library that might be helpful.

The crate consists of two main section

1. perm
2. group

The first section deals mostly with permutations, which are the basic data structure used. The second is where most of the interesting algorithms lies, which deal with groups generated by finitely many permutations.

Group

The main object you will probably need to understand is the Group object. It stores a group as a finite list of generators, and it can be used for all sort of operations. Note that Group is actually a Group<P>, where P is of type DefaultPermutation. The rationale for this is that we would like in general to be not too verbose to specify a group, but allow the user to specify which permutation they might want. The Group object provides a library of commonly used group types, such as trivial, klein_4, dihedral_2n, cyclic, alternating, symmetric, which are all instantieted in the DefaultPermutation type. Also, it is always possible to create a Group<P> from an iterator of P using FromIterator or from an array of P using Group::new.

We suggest that if the user desires to use other kind of permutation for those groups they create them and use the Group::map operation in the following way: Group::symmetric(32).map(SyncPermutation::from)

Once a group object, say G, is created there are lot of methods that can be used.

Generator Management

This are simple methods to massage the generating set of G

1. deduplicate, make sure the generating set does not contain duplicates
2. random_generators, creates a new generating set, iteratively adding points and computing stabchains until the size matches
3. random_n_generators, tries to create a new generating set of n elements, note this might not terminate
4. conjugate_gens, conjugate all generators by a given element.

Group Algebra

Ways to combine groups to get other groups, at the moment we only have product, which takes two groups and computes the cartesian product of the groups.

Random elements

The methods:

1. rng
2. rng_with_source are used to generate random elements in the group. The second one of course takes in a randomness source that can be used for different needs. They return a RandPerm object, which can be queried using RandPerm::random_permutation to get as many permutations as wished (of course limited by the size of the group).

Orbits and Transversal

It is very important to be able to compute orbits and transversals in permutation groups. We provide these in three methods:

1. orbit, computes the orbit of a point
2. transversal, computes the transversal of a point
3. factored_transversal, computes the transversal of a point, stored in a factored manner.

Each method returns a struct with all the information easily queriable. Each of these has an of_action version, which takes any element of a type that implements Action and allows to compute a general action. For example using MultiplicativeAction::default() will apply those methods with the multiplicative action.

Stabchain

Finally, here is core of the module, the stabchain operations. We start with some glossary. A selector is a type that implements BaseSelector. It is used to control how the base is selected in a stabilizer chain construction. There are three selectors and one adaptor that can be used to combine selectors:

1. LmpSelector and FmpSelector respectively select the last and first moved point by the permutation
2. FixedBaseSelector select a user defined base
3. PartialSelector can be used to combine any two of the above selectors, it will use the first selector for the the initial prefix and then switch to the second selector. For example PartialSelector::new(FixedBaseSelector::new(&base[0..3]), 3, LmpSelector::default()); can be used to select the first 3 points of the fixed base and then switch to the default selection of using last moved point.

Now a strategy is a type that implements BuilderStrategy. It is supposed to be a lightweight struct that specifies how the stabilizer chain should be constructed. There are three main ways strategies:

1. NaiveBuilderStrategy computes a stabilizer chain using the deterministic algorithm and building full transversal. Should be fastest for small groups.
2. IFTBuilderStrategy computes a stabilizer chain using the deterministic algorithm using a factored transversal. Slower than the previous one but should be more memory efficient
3. RandomBuilderStrategyNaive uses the random algorithm to compute stabilizer chains
4. RandomBuilderStrategyShallow uses the random algorithm with an optimization that makes the trees shallower

Each strategy can be created by passing in an action and a selector, and the random ones takes additionally some parameters that will be used in order to set up the constants for the algorithm.

The methods that are exposed on G are as following:

1. stabchain computes a stabilizer chain using the default strategy and the default selector
2. stabchain_base computes a stabilizer chain using the default strategy and a fixed base
3. stabchain_with_selector computes a stabilizer chain using the default strategy and a given selector
4. stabchain_with_strategy computes a stabilizer chain using a given strategy (that will also include a given selector)

As with permutation, we have provided DefaultStrategy and DefaultSelector as type alias for the default strategy and selectors.

Perm

Permutation

The main export of this module is the Permutation trait, which is an "interface" for a general group element. As such you can get an identity element, compute the multiplication of two permutations of the same type and the inverse of any permutation. What distinguishes such an object from a standard group element is that we can apply it to a point, so that we can use it to defines Action on a desired set. We provide many implementation of this permutation trait, namely:

1. DefaultPermutation The default chosen type for a permutation. The idea is that it will be chosen to be the most advantageous and it can be changed at will. It defaults to StandardPermutation.
2. StandardPermutation A permutation which stores a list of images in a reference counted array. Good all size fits all, not thread safe.
3. SyncPermutation Same as StandardPermutation, but the reference counting is done atomically, making it the best choice for multithreaded applications.
4. WordPermutation, a permutation that does lazy multiplication and application, can be useful for some operations such as in the random stabchain algorithm
5. BasedPermutation, a permutation that stores an offset, and will fix all points before that offset. Very useful if you are dealing with things like products which are implemented by shifting permutation
6. MapPermutation, a terrible permutation that stores the images as an HashMap. If it fixes many point it is very memory efficient, but benchmarks show that it is very slow so it is almost never the best choice.

Together with those we have some permutations that are to be used mostly for exporting and userfacing tasks, and as such they do not have computation capabilities. These are:

1. ClassicPermutation which creates a permutation on [1..n] from one on [0..n).
2. CyclePermutation which computes the cycle representation of a permutation
3. ExportablePermutation which can be serialized with serde

All permutation types should be easily (some times not super efficiently) converted to one another, so for example you can seamlessly switch between StandardPermutation and SyncPermutation when needing to do something threaded.

Action

So, the Action trait is used in order to specify different actions for the same permutation group. The idea is that often we can would like to apply the same algorithm with different kind of actions, and we can pass an instance of this interface to select at compile time what that action will be. We provide implementations for the following three:

1. SimpleApplication, uses the apply method in Permutation, so it computes an action on the point set
2. Conjugation, acts on the permutation group itself, and computes the conjugate
3. Multiplication, acts on the permutation group itself by multiplying (on the right?)