<p><strong class="pkg">FR</strong> creates new categories for the various objects considered in the package. The first category is <code class="code">FRObject</code>; all objects are in this category, and have an <code class="code">Alphabet</code> method.</p>
<p>There are two categories below: <code class="code">FRMachine</code> and <code class="code">FRElement</code>. An <code class="code">FRMachine</code> must have a <code class="code">StateSet</code>, and methods for <code class="code">Output</code> and a <code class="code">Transition</code>. An <code class="code">FRElement</code> must have an underlying <code class="code">FRMachine</code> and <code class="code">InitialState</code>, and <code class="code">Output</code> and a <code class="code">Transition</code> that use the initial state.</p>
<p>A self-similar group is simply a collections category of FR elements which is also a group.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; FREFamily</code>( <var class="Arg">obj</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: the family of FR elements on alphabet <var class="Arg">obj</var>.</p>
<p>The family of an FR object is the arity of the tree on which elements cat act; in other words, there is one family for each alphabet.</p>
<p>The argument may be an FR machine, an alphabet, or a family of FR machines.</p>
<p>This command applies to the family of any FR object, or to the object themselves. Alphabets are returned as lists, and in pratice are generally of the form <code class="code">[1..n]</code>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; AsPermutation</code>( <var class="Arg">o</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>This method takes as argument an FR object <var class="Arg">o</var>: machine, element, or group, and produces an equivalent object whose outputs are permutations. In particular, it converts Mealy machines from domain representation to int representation.</p>
<p>If this is not possible, the method returns <code class="keyw">fail</code>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; AsTransformation</code>( <var class="Arg">o</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>This method takes as argument an FR object <var class="Arg">o</var>: machine, element, or group, and produces an equivalent object whose outputs are transformations. In particular, it converts Mealy machines from domain representation to int representation.</p>
<p>Since transformations can never be inverted by <strong class="pkg">GAP</strong>, even when they are invertible, this function returns a monoid when applied to a full SC group.</p>
<p>This function is the acceptor for those functionally recursive machines whose stateset (accessible via <code class="func">StateSet</code> (<a href="chap3_mj.html#X8000470D7DA7FFBD"><span class="RefLink">3.4-1</span></a>)) is a free group, monoid or semigroup. The generating set of its stateset is accessible via <code class="func">GeneratorsOfFRMachine</code> (<a href="chap3_mj.html#X7F77F5DD789FA2F4"><span class="RefLink">3.4-2</span></a>).</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsFRMachineStrRep</code>( <var class="Arg">obj</var> )</td><td class="tdright">( filter )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> if <var class="Arg">obj</var> is a standard (group,monoid,semigroup) FR machine.</p>
<p>There is a free object <code class="code">free</code>, of rank <span class="SimpleMath">\(N\)</span>, a list <code class="code">transitions</code> of length <span class="SimpleMath">\(N\)</span>, each entry a list, indexed by the alphabet, of elements of <code class="code">free</code>, and a list <code class="code">output</code> of length <code class="code">N</code> of transformations or permutations of the alphabet.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsMealyMachineIntRep</code>( <var class="Arg">obj</var> )</td><td class="tdright">( filter )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> if <var class="Arg">obj</var> is a Mealy machine in integer representation.</p>
<p>A Mealy machine in <em>integer</em> representation has components <code class="code">nrstates</code>, <code class="code">transitions</code>, <code class="code">output</code> and optionally <code class="code">initial</code>.</p>
<p>Its stateset is <code class="code">[1..nrstates]</code>, its transitions is a matrix with <codeclass="code">transitions[s][x]</code> the transition from state <code class="code">s</code> with input <code class="code">x</code>, its output is a list of transformations or permutations, and its initial state is an integer.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsMealyMachineDomainRep</code>( <var class="Arg">obj</var> )</td><td class="tdright">( filter )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> if <var class="Arg">obj</var> is a Mealy machine in domain representation.</p>
<p>A Mealy machine in <em>domain</em> representation has components <code class="code">states</code>, <code class="code">transitions</code>, <code class="code">output</code> and optionally <code class="code">initial</code>.</p>
<p>Its states is a domain, its transitions is a function with <code class="code">transitions(s,x)</code> the transition from state <code class="code">s</code> with input <code class="code">x</code>, its output is a function with <code class="code">output(s,x)</code> the output from input <code class="code">x</code> in state <code class="code">s</code>, and its initial state is an elemnent of <code class="code">states</code>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsVectorFRMachineRep</code>( <var class="Arg">obj</var> )</td><td class="tdright">( filter )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> if <var class="Arg">obj</var> is a vector machine</p>
<p>A <em>vector machine</em> is a representation of a linear machine by a finite-dimensional vector space (implicit in the structure), a transition tensor (represented as a matrix of matrices), and an output vector (represented as a list).</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsAlgebraFRMachineRep</code>( <var class="Arg">obj</var> )</td><td class="tdright">( filter )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> if <var class="Arg">obj</var> is an algebra machine</p>
<p>An <em>algebra machine</em> is a representation of a linear machine by a finitely generated free algebra, a tensor of transitions, indexed by generator index and two alphabet indices, and an output vector, indexed by a generator index.</p>
<p>The transition tensor's last two entries are the 0 and 1 matrix over the free algebra, and the output tensor's last two entries are the 0 and 1 elements of the left acting domain.</p>
<p>This filter is the acceptor for the <em>functionally recursive element</em> category.</p>
<p>It implies that <var class="Arg">obj</var> has an underlying FR machine, may act on sequences, and has a recursive <code class="func">DecompositionOfFRElement</code> (<a href="chap4_mj.html#X850EB66E7804BA3B"><span class="RefLink">4.2-6</span></a>).</p>
<p>The next filters specify the type of free object the stateset of <var class="Arg">obj</var> is modelled on.</p>
<p>This filter is the acceptor for the <em>functionally recursive element</em> category, with an additional Mealy element stored as attribute for faster calculations. It defines a subcategory of <code class="func">IsFRElement</code> (<a href="chap10_mj.html#X7966F9B982B1DFE1"><span class="RefLink">10.2-11</span></a>). This additional Mealy element may be obtained as <code class="code">UnderlyingMealyElement(obj)</code>.</p>
<p>The next filters specify the type of free object the stateset of <var class="Arg">obj</var> is modelled on.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsFRObject</code>( <var class="Arg">obj</var> )</td><td class="tdright">( filter )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> if <var class="Arg">obj</var> is an FR machine or element.</p>
<p>This function is the acceptor for the most general FR category (which splits up as <code class="func">IsFRMachine</code> (<a href="chap10_mj.html#X7C22A1A28058F754"><span class="RefLink">10.2-14</span></a>) and <code class="func">IsFRElement</code> (<a href="chap10_mj.html#X7966F9B982B1DFE1"><span class="RefLink">10.2-11</span></a>)).</p>
<p>It implies that <var class="Arg">obj</var> has an attribute <code class="func">AlphabetOfFRObject</code> (<a href="chap10_mj.html#X7BC9CD3685C26823"><span class="RefLink">10.1-3</span></a>).</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsFRMachine</code>( <var class="Arg">obj</var> )</td><td class="tdright">( filter )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> if <var class="Arg">obj</var> is an FR machine.</p>
<p>This function is the acceptor for the <em>functionally recursive machine</em> category. It splits up as <code class="func">IsGroupFRMachine</code> (<a href="chap10_mj.html#X7CC0BFD67CE7060E"><span class="RefLink">10.2-1</span></a>), <code class="func">IsSemigroupFRMachine</code> (<a href="chap10_mj.html#X7CC0BFD67CE7060E"><span class="RefLink">10.2-1</span></a>), <code class="func">IsMonoidFRMachine</code> (<a href="chap10_mj.html#X7CC0BFD67CE7060E"><span class="RefLink">10.2-1</span></a>) and <code class="func">IsMealyMachine</code> (<a href="chap10_mj.html#X79C2395A7D65214B"><span class="RefLink">10.2-3</span></a>)).</p>
<p>It implies that <var class="Arg">obj</var> has attributes <code class="func">StateSet</code> (<a href="chap3_mj.html#X8000470D7DA7FFBD"><span class="RefLink">3.4-1</span></a>), <code class="func">GeneratorsOfFRMachine</code> (<a href="chap3_mj.html#X7F77F5DD789FA2F4"><span class="RefLink">3.4-2</span></a>), and <code class="func">WreathRecursion</code> (<a href="chap3_mj.html#X7D95D1498586E5D0"><span class="RefLink">3.4-6</span></a>); the last two are usually not used for Mealy machines.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsInvertible</code>( <var class="Arg">m</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> if <var class="Arg">m</var> is an invertible FR machine.</p>
<p>This function accepts invertible FR machines, i.e. machines <var class="Arg">m</var> such that <span class="SimpleMath">\((m,q)\)</span> is an invertible transformation of the alphabet for all <span class="SimpleMath">\(q\)</span> in the stateset of <var class="Arg">m</var>.</p>
<h4>10.3 <span class="Heading">Some of the algorithms implemented</span></h4>
<p>Few calculations with infinite groups can be guaranteed to terminate --- and especially to terminate within reasonable time. This section describes some of the algorithms implemented in <strong class="pkg">FR</strong>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; FRMachineRWS</code>( <var class="Arg">m</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A record containing a rewriting system for <var class="Arg">m</var>.</p>
<p>Elements of an FR machine are compared using a rewriting system, which records all known relations among states of the machine.</p>
<p>One may specify via an optional argument <code class="code">:fr_maxlen:=n</code>, the maximal length of rules to be added. By default, this maximum length is 5.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">n := FRMachine(["a","b"],[[[],[2]],[[],[1]]],[(1,2),()]);</span>
<FR machine with alphabet [ 1, 2 ] on Group( [ a, b ] )>
<span class="GAPprompt">gap></span> <span class="GAPinput">FRMachineRWS(n);</span>
rec( rws := Knuth Bendix Rewriting System for Monoid( [ a^-1, a, b^-1, b
], ... ) with rules
[ [ a^-1*a, <identity ...> ], [ a*a^-1, <identity ...> ],
[ b^-1*b, <identity ...> ], [ b*b^-1, <identity ...> ] ],
tzrules := [ [ [ 1, 2 ], [ ] ], [ [ 2, 1 ], [ ] ], [ [ 3, 4 ], [ ] ],
[ [ 4, 3 ], [ ] ] ], letterrep := function( w ) ... end,
pi := function( w ) ... end, reduce := function( w ) ... end,
addgprule := function( w ) ... end, commit := function( ) ... end,
restart := function( ) ... end )
</pre></div>
<h5>10.3-2 <span class="Heading">Order of FR elements</span></h5>
<p>The order of an FR element <code class="code">e</code> is computed as follows: the tree is traversed recursively, filling it as follows. For each cycle of <code class="code">e</code> on the first level, the product of the states on that cycle are computed. The method continues recursively with that product, remembering the order of the cycle. Once a state reappears in the traversal, <strong class="pkg">FR</strong> determines if one instance of the state is in the subtree of the other, and if so whether the top one was raised to a non-trivial power to yield the second one as a state. If this happens, then <code class="code">e</code> has infinite order. Otherwise, the least common multiple of the powers that appeared in the traversal is returned.</p>
<p>This method is guaranteed to succeed if <code class="code">e</code> is a bounded element. To improve chances of success, <strong class="pkg">FR</strong> first computes whether <code class="code">e</code> acts by vertex transformations belonging to an abelian group; and if so, if <code class="code">e</code> is conjugate to an adding machine. In that case too, <code class="code">e</code> has infinite order.</p>
<h5>10.3-3 <span class="Heading">Membership in semigroups</span></h5>
<p>The following algorithm is used to determine whether a Mealy element belongs to a self-similar group. The corresponding problem of membership of an FR element in a state-closed self-similar group can be much simpler, because an FR element has an associated FR machine, all of whose states belong to the group.</p>
<p>Assume the group is given by generators. <strong class="pkg">FR</strong> attempts to express the given Mealy element as a product of generators. At the same time, it constructs epimorphisms to finite groups. It is hoped that one of these two processes will stop.</p>
<p>This amounts, in fact, to the following. Consider a group <span class="SimpleMath">\(G\)</span> acting on a tree. It has a natural, profinite closure <span class="SimpleMath">\(\overline G\)</span>. The algorithm then attempts either to write an element <span class="SimpleMath">\(x\)</span> as a product of generators of <var class="Arg">G</var>, or to show that <span class="SimpleMath">\(x\)</span> does not belong to <span class="SimpleMath">\(\overline G\)</span>.</p>
<p>There are groups <span class="SimpleMath">\(G\)</span> such that <span class="SimpleMath">\(\overline G\setminus G\)</span> contains Mealy machines. For these, the above algorithm will not terminate.</p>
<p>An additional refinement is implemented for bounded groups (see <code class="func">IsBoundedFRSemigroup</code> (<a href="chap7_mj.html#X7A6CB30181662C77"><span class="RefLink">7.2-14</span></a>)). The <code class="func">Germs</code> (<a href="chap5_mj.html#X81592E3D79745A40"><span class="RefLink">5.2-24</span></a>) of an element are computed, and compared to the germs of elements in the group.</p>
<p>Finally, for a group that possesses self-similar data (see Section <a href="chap10_mj.html#X8329884F790E1542"><span class="RefLink">10.3-9</span></a>), very fast methods are implemented to recognize and express an FR element as a product of generators.</p>
<p>The conjugacy problem for self-similar branch groups has been implemented by Thorsten Groth, as part of his Diploma Thesis. His code is integrated in <strong class="pkg">FR</strong>.</p>
<p>Specialized algorithms are implemented for the Grigorchuk and Gupta-Sidki groups, and a generic algorithm is implemented, which is however not guaranteed to succeed. The implementation follows <a href="chapBib_mj.html#biBMR3054572">[BBSZ13]</a>.</p>
<p>The following extra attibutes are part of his implementation:</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; OrbitSignalizer</code>( <var class="Arg">g</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: The Orbit Signalizer of the group element <var class="Arg">g</var></p>
<p>This attribute computes the orbit signalizer of an element. This is the set <span class="SimpleMath">\(OS(g) := \{g^{|Orb_g(v)|}@v \mid v \in X^*\}\)</span> where <span class="SimpleMath">\(X\)</span> is the alphabet of the element <var class="Arg">g</var> and <span class="SimpleMath">\(Orb_g(v)\)</span> is the orbit of <span class="SimpleMath">\(v\)</span> under <span class="SimpleMath">\(\langle g \rangle\)</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">a := MealyElement([[2,2],[2,2]],[(1,2),()],1);</span>
<Mealy element on alphabet [ 1 .. 2 ] with 2 states>
<span class="GAPprompt">gap></span> <span class="GAPinput">OrbitSignalizer(a);</span>
[ <Mealy element on alphabet [ 1 .. 2 ] with 2 states>, <Trivial Mealy element on alphabet [ 1 .. 2 ]> ]
</pre></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; FRConjugacyAlgorithm</code>( <var class="Arg">G</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A function which solves the conjugacy problem for <var class="Arg">G</var></p>
<p>This attribute stores a function in three arguments which computes a representative conjugator if exists or fail otherwise.</p>
<p>This attribute is not meant to have a standard setter but to be set if a specialized conjugacy algorithm for a certain group is discovered.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f := FRConjugacyAlgorithm(GrigorchukGroup);</span>
function( G, g, h ) ... end
<span class="GAPprompt">gap></span> <span class="GAPinput">AssignGeneratorVariables(GrigorchukGroup);</span>
#I Assigned the global variables [ "a", "b", "c", "d" ]
<span class="GAPprompt">gap></span> <span class="GAPinput">f(GrigorchukGroup,a,a^b);</span>
<Mealy element on alphabet [ 1 .. 2 ] with 5 states>
</pre></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; FRBranchGroupConjugacyData</code>( <var class="Arg">G</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: The initial data for the branch algorithm for <var class="Arg">G</var></p>
<p>This attribute records the data for the branch algorithm. The record has the following components:</p>
<dl>
<dt><strong class="Mark">initial_conj_dic:</strong></dt>
<dd><p>Dictionary of already known conjugacy pairs with corresponding conjugator tuples. This has to cover at least the TorsionNucleus of <var class="Arg">G</var></p>
</dd>
<dt><strong class="Mark">Branchstructure</strong></dt>
<dd><p>Usally calculated by the function BranchStructure</p>
</dd>
<dt><strong class="Mark">RepSystem</strong></dt>
<dd><p>List of representatives of <span class="SimpleMath">\(G/K\)</span> where <span class="SimpleMath">\(K\)</span> is the branching subgroup of <var class="Arg">G</var></p>
<h5>10.3-8 <span class="Heading">Order of groups</span></h5>
<p>The order of an FR group is computed as follows: if all generators are finitary, then enumeration will succeed in computing the order. If the action of the group is primitive, and it comes from a bireversible automaton, then the Thompson-Wielandt theorem is tested against. This theorem states that, in our context (a group acting on a rooted tree, coming from a larger group acting transitively), if the group is finite then the stabilizer of a sphere of radius 2 is a <span class="SimpleMath">\(p\)</span>-group; see <a href="chapBib_mj.html#biBMR1839488">[BM00a, Proposition 2.1.1]</a>. Then, <strong class="pkg">FR</strong> attempts to find whether the group is level-transitive (in which case it would be infinite). Finally, it attempts to enumerate the group's elements, testing at the same time whether these elements have infinite order.</p>
<p>Needless to say, none except the first few steps are guaranteed to succeed.</p>
<h5>10.3-9 <span class="Heading">Images and preimages of some groups in
f.p. and l.p. groups</span></h5>
<p>Contracting, branched groups admit finite L-presentations (see <a href="chapBib_mj.html#biBMR2009317">[Bar03a]</a>), that is, presentations by finitely many generators, relators and endomorphisms; the (usual) relators are the images of the given relators under iteration by all endomorphisms.</p>
<p>Using the package <strong class="pkg">NQL</strong>, it is possible to construct infinite nilpotent quotients of self-similar groups, and perform fast computations in them.</p>
<p>It is possible to construct, algorithmically, such an L-presentation from a self-similar groups; however, this algorithm has not been implemented yet, mainly because efficiency issues would make it usable only in very few cases.</p>
<p>For groups with an isomorphism to an L-presented group (constructed by <code class="func">IsomorphismLpGroup</code> (<a href="chap7_mj.html#X8740656382656D63"><span class="RefLink">7.2-31</span></a>)), a fast method expresses group elements as words in the L-presented group's generators. It proceeds recursively on the decomposition of the element, mapping elements that are expressible by short words over the nucleus (usually length 1; length 3 is needed for the <code class="func">BrunnerSidkiVieiraGroup</code> (<a href="chap9_mj.html#X7F93EC437B5AE276"><span class="RefLink">9.1-13</span></a>)) to their value in the L-presented group, and using the presentation's endomorphism to construct words with appropriate decompositions.</p>
<p>In particular, the algorithm will stop, returning <code class="keyw">fail</code>, if during the recursion it reaches an element <span class="SimpleMath">\(x\)</span> such that <span class="SimpleMath">\(x\)</span> is a state of <span class="SimpleMath">\(x\)</span> but <span class="SimpleMath">\(x\)</span> does not belong to the nucleus.</p>
<h5>10.3-10 <span class="Heading">Comparison of FR, Mealy, vector,
and algebra elements</span></h5>
<p>FR and Mealy elements can be compared quite efficiently, as long as they are distinct. The algorithm runs as follows: let the two elements be <span class="SimpleMath">\(x\)</span> and <span class="SimpleMath">\(y\)</span>. Considering both in turn, <strong class="pkg">FR</strong> constructs the first entries of minimal Mealy elements expressing <span class="SimpleMath">\(x\)</span> and <span class="SimpleMath">\(y\)</span>; as soon as an output entry is distinct for <span class="SimpleMath">\(x\)</span> and for <span class="SimpleMath">\(y\)</span>, the status of <span class="SimpleMath">\(x<y\)</span> is determined; and similarly for transition entries. Finally, if either of <span class="SimpleMath">\(x\)</span> or <span class="SimpleMath">\(y\)</span> is finite-state and the entries were identical up to that step, then the element with smallest stateset is considered smaller.</p>
<p>In this way, FR and Mealy elements can efficiently be compared. For Mealy elements, it suffices to follow their internal data; while for FR elements, this amounts to constructing Mealy elements approximating them to a sufficient precision so that they can be compared as such.</p>
<p>The algorithm first tries to test its arguments for equality; this test is not guaranteed to succeed.</p>
<p>A similar algorithm applies for linear elements. Here, one constructs vector element approximations; and compares, for ever-increasing values of <span class="SimpleMath">\(i\)</span>, first the output vectors of basis state <span class="SimpleMath">\(i\)</span>; then the transitions from state <span class="SimpleMath">\(i\)</span> to state <span class="SimpleMath">\(j\)</span>, for all <span class="SimpleMath">\(j\in\{1,\ldots,i\}\)</span>; then the transitions from state <span class="SimpleMath">\(j\)</span> to state <span class="SimpleMath">\(i\)</span> for all <span class="SimpleMath">\(j\in\{1,\ldots,i-1\}\)</span>.</p>
<h5>10.3-11 <span class="Heading">Inverses of linear elements</span></h5>
<p>It is probably difficult to compute the inverse of a vector element. The following approach is used: to compute the inverse of <span class="SimpleMath">\(x\)</span>, large (scalar) matrix approximations of <span class="SimpleMath">\(x\)</span> are computed; they are inverted using linear algebra; a vector element representing this inverse is guessed; and the guess is checked. As long as that check fails, larger approximations are computed.</p>
<p>Needless to say, this method need not succeed; for there are vector elements that are invertible, but whose inverse is not a vector element. A good test example appears in <a href="chapBib_mj.html#biBMR2422072">[Bac08]</a>: consider the infinite matrix with 1's on the diagonal, and <span class="SimpleMath">\(\omega\)</span> below the diagonal. This element admits an inverse if and only if <span class="SimpleMath">\(\omega\)</span> is a root of unity. The complexity of the inverse grows as the degree of <span class="SimpleMath">\(\omega\)</span> grows. Here is an illustation:</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">bacher := function(n)</span>
local f;
f := CyclotomicField(n);
return VectorElement(f,One(f)*[[[[1,0],[0,0]],
[[0,0],[0,1]]],[[[0,1],[0,0]],[[1,0],[0,0]]]],[One(f),E(n)],[One(f),Zero(f)]);
end;;
<span class="GAPprompt">gap></span> <span class="GAPinput">Inverse(bacher(3));</span>
<Linear element on alphabet CF(3)^2 with 4-dimensional stateset> 6 gap> Inverse(bacher(5));
<Linear element on alphabet CF(5)^2 with 6-dimensional stateset>
</pre></div>
