\def\k#1{^{(#1)}}
\noindent {\bf Computation of Bilinear forms}

\noindent (A C++ program written by Eric M\"uller, 1998--1999)

Let $k$ be a field of zero characteristic, $G$ be a not necessarily
abelian finite group and
let $V$ be a finite dimensional module in the category  $^{k[G]}_{k[G]}YD$
and $U$ a linear basis (consisting of $G$-homogeneous elements, i.~e.~elements
$x$ with coaction $g\otimes x$ for some $g\in G$) of it.
The tensor algebra $T(V)$ of $V$ is a  $^{k[G]}_{k[G]}YD$-Hopf algebra, 
the generators in $V$ are primitive.
There is a certain universal object $B(V)$ which is the tensor algebra $T(V)$
modulo the ideal generated by all primitive elements which do
not belong to $V$.
These objects have been considered first by Nichols in "Bialgebras of
type I" (Comm.~Alg.~15 (1978), 1521--1552) and further investigated
by many other authors including S.~L.~Woronowics and M.~Rosso.
Due to a result of N. Andruskiewitsch and M.~Gra\~na ("Braided Hopf
algebras over non-abelian finite groups", Corollary 3.2.21), they 
can also be described using a bilinear form. The universality of the
object is just equivalent to the condition that the bilinear form
(which is defined on $T(V)\times T(V)$) is non-degenerate. This program
can compute this bilinear form in certain cases and help to investigate
the objects $B(V)$ without any knowledge on the actual relations, i.e.
find some relations, find out whether certain monomials vanish in $B(V)$
or do not vanish, compute rather long non-vanishing monomials in $B(V)$.

The bilinear form is given by the following conditions: $(1,1)=1$,
for all $u,v\in U$ we have $(u,1)=(1,u)=0$, $(u,v)=\delta_{u,v}$.
(The values of $(u,u)$ for $u\in U$ can be normalized to 1, the values
are not important as far as they do not vanish).
Moreover, $(x,yz)=\sum_j (x_{1j}, y)(x_{2j},z)$ for all $x,y,z\in T(V)$, 
where $\Delta(x)= \sum_j x_{1j}\otimes x_{2j}$
denotes the comultiplication in the $^{k[G]}_{k[G]}YD$-Hopf algebra $T(V)$ (which induces
the comultiplication in $B(V)$).

For each $G$-homogeneous element $x$ of $T(V)$ let $|x|$ be its $G$-degree,
i.~e.~the coaction of~$x$ is $|x|\otimes x$.
The program assumes that the action of $|x|$ (for any $x\in U$) on
any $y\in U$ is given by $|x|\cdot y = \chi(x,y) a(x,y)$ where
$\chi(x,y)\in k\setminus\{0\}$ and $a(x,y)\in U$, i. e. the action 
is given by a bicharacter and permutations.
Then the braiding associated to this action is given by
$x\otimes y \mapsto \chi(x,y) a(x,y)\otimes x$.
(Here $\chi$ is a group character or group bicharacter of $G$).

Moreover we fix a root of unity $q\in k$
such that  $\chi(x,y)$ is always a power of $q$.

The program computes the bilinear form for two monomials in the generators
in $U$.
This works as follows: Let $u_1\cdots u_m$ and $v_1\cdots v_n$
be two monomials. The bilinear form of them vanishes if $m\ne n$,
whence $m=n$ may be assumed.
In order to compute the bilinear form, the first monomial must be diagonalized
$n-1$ times, so that we have a sum
$$\left(\sum_{j=1}^n u_1\k j\right)\cdots \left(\sum_{j=1}^n u_n\k j\right)$$
(where $u\k j$ is the $n$-tensor with $u$ at position $j$ and 1 at
all other positions, e.g. for $n=2$, $u\k1 = u\otimes 1$).
In order to multiply the summands $u_1\k{j_1}\cdots u_n\k{j_n}$,
we use the braiding, i.e.
for $i<j$, $u\k i v\k j$ is just the tensor with $u$ at position $i$,
$v$ at position $j$ and 1 at all other positions,
if $i=j$, it is the tensor with $uv$ at position $i=j$ and 1 at
all other positions, if $i>j$, it is $\chi(u,v)(a(u,v))\k j u\k i$.
Finally, for each summand $S=\alpha w_1\otimes \cdots \otimes w_n$
(where $\alpha\in k$, $w_1, \ldots, w_n\in T(V)$), there is the
summand 
$T=\alpha (w_1, v_1)\cdots (w_n,v_n)$ of the bilinear form.
Note that $v_1, \ldots, v_n$ are elements of $U$ so that also 
$w_1, \ldots, w_n$ should be elements of $U$ (and monomials of length 1).
Thus this summand vanishes unless $w_1=v_1, \ldots, w_n=v_n$.
This is a strong condition which can be used to enormously decrease
the number of summands to be considered:
Due to the definition of the braiding, the element $u_1$
appears in each of these summands $S$. Hence if $u_1$ is not contained
in $\{v_1, \ldots, v_n\}$, all summands $T$ must vanish.
If $u_1\k i$ and $u_2\k j$ are factors of one summand $S$ and
$i<j$ then due to the definition of the braiding, the summand $S$
contins $u_1$ at position $i$ and $u_2$ at position $j$, whence
the summand $T$ vanishes unless $v_i=u_1$ and $v_j=u_2$
(likewise if $i>j$, then we get the condition $v_j=u_1$, $v_i=a(u_1,u_2)$).
This means that the "string" $v_1\cdots v_n$ must contain 
$u_1$ and $u_2$ (or $a(u_1,u_2)$ and $u_1$) in this order at some
positions (but not necessarily adjacent), etc. This concept is used by
the program to limit the number of summands to be considered
(some further optimizations in the algorithm can be done if the action by 
permutation is always trivial, but these optimizations are not included in 
this version of the program).

The program uses an obligatory input file which must be the first
parameter, and an optional output file which is the optional second
parameter.
The input file contains fixed information about $q$, $U$,  and
the braiding (and some information about output). (The input file is
practical because the program only computes one value (or one set
of values) of the bilinear form and therefore may often be invoked for the 
same fixed information about $B(V)$).

The input is as follows:

1st line: Order of the root of unity (positive number not exceeding the
constant {\tt maxN} of the program, which is 20 at the moment). It should be 
a prime number in order to make the reduction method for the values of
the bilinear form work correctly (no warning if it is not a prime number).

2nd line: Information whether $\chi(u,v)$ only depends on $u$ or also on $v$.
In the first case write 1, in the second case write 2.
There are optional data to be written after this number (without leaving
blancs):
\item - Information whether the squares of the generators in $U$ vanish in $B(V)$
(this is true in some examples and leads to optimizations when computing
a series of bilinear forms, not used for computing just one bilinear form):
Y: squares vanish, N: squares do not vanish, default: N,
\item - Print out the number of non vanishing summands $T$ of the
bilinear form: Y: print out, N: do not print out, default: Y,
\item - Print out information when a certain number of non vanishing
summands has been computed (normally a dot for each 1000 summands (1000
may be replaced by another number, see below), and
the monomial when computation has been aborted because of reaching a 
certain given limit of the number of non vanishing summands):
Y: print out, N: do not print out, default: Y,
\item - Format of the value of the bilinear form (if $n$ is the order
of the root of unity, then always $q^{n-1}$ is reduced to
$-1-q-\cdots -q^{n-2}$). Choices: 
N: normal format, e. g. the order of the root of unity is 7, and the value
is $1+q-3q^4$, Y: simple format (the previous example
becomes $1 1 0 0 -3 0$), this may be used to generate input for some other
programs in order to compute relations in $B(V)$, default: N.
\item - After these input data there may be a blank followed by a number.
Then the number of computed summands of the bilinear form, after which
information is printed out, is set to this value (default: 1000). This
means that whenever a multiple of this number of summands has been reached,
a dot is printed out. If the value is 1, then not only a dot is printed
out, but also information about the shuffles of the first monomial which
lead to non-zero summands of the bilinear form, are given. They have the following
form: t ($a_1$ $a_2 \ldots a_n$). This means in the above notation that
$$u_1\k {a_1} u_2\k {a_2} \cdots u_n\k{a_n} = q^t v_1\otimes v_2\otimes
\cdots \otimes v_n.$$


Example: If the second line just contains "1", then $\chi$ depends only
on the first argument and all default output options are chosen.
If the second line contains "2NN 5" $\chi$ depends on both arguments,
the squares are not assumed to be zero, but the number of non vanishing
summands is not printed out, a dot is printed out whenever a multiple
of 5 summands of the bilinear form has been computed, 
and all other default options are chosen.

Third line: Contains all elements of $U$ --- each element must be represented
by a single character or digit or other character but not a blank nor a
dot ".". It is
advisable not to choose the characters ":", "(", "!" because they
may appear very closely to the monomials in the output. Uppercase letters
and lowercase letters are distinguished.

The following lines contain information about the braiding:
Some group generators of $G$ may be chosen (they must be different from
the elements of $U$ and not a blank), and the action of 
those on the set $U$ by permutation is given as follows:
\item - A line may start with a new character (=group generator) followed by
a permutation of the characters in the third line (=elements of $U$).
Then this group generator acts on $U$ by this permutation.
Example: If the third line contains "abc" and the group generator $s$ just swaps
"a" and "b", then the action is declared as $sbac$, i.e. the first
\item - If $\chi$ only depends on its first argument, a line may start with a new character (=group generator) followed
by a blank and a {\it nonnegative} number, $n$ say. Then $\chi(s)$ is set to 
$q^n$ (the default value is $\chi(s)=1$). If $\chi$ depends on both
arguments, then $\chi(u,v)=q^n$ is set by the line
starting with "u" and "v" followed by the {\it nonnegative} number $n$ without any blank (default is $\chi(u,v)=1$).
Example: If the third line contains "abc" then in the first case
the line "s 1" sets $\chi(s)=q$ and in the second case
"ab2" sets $\chi(a,b)=q^2$.
\item - The action of the elements $|u|$ for  $u\in U$ by permutation on $U$ is
given as follows: If $s_1, \ldots, s_n$ are group generators such
that $|u| = s_1\ldots s_n$ then the line starts with
"u" followed by the symbols for $s_n, \ldots, s_1$ in reverse order
(whithout blanks). The identity permutation is default and need not be
set in this way. If $\chi$ only depends on the first argument, then
$\chi(a)$ is automatically computed as the product of the values of the $\chi(s_1), \ldots,
\chi(s_n)$. If $\chi$ depends on both argument, then the values have to
be given directly as in the previous paragraph.
Example: If the third line contains "abc" and the group generators "s" and
"t" have been introduced, then $|a|=sst$ is given by
the line "atss". 

Two examples of correct input files:

\goodbreak
First example: 

{\tt\obeylines
5
2
ab
aa2
bb2
ba4
ab4
}

\goodbreak
Second example: {\tt\obeylines

2
1jjn 10
123456
a145236
b213465
c132546
a 1
b 1
c 1
1a
2bab
3cbabc
4b
5cbc
6c
}


After this file has been read in, the program prints out all information:
The order of $q$, the output options of line 2 (one comment for
each positive choice "Y" regardless whether explicitly set or just taken
as default value), the number $r$ such that whenever a multiple of $r$
summands of the bilinear form has been computed, a dot is printed out
(if this information is not suppressed) or a hint that information
about shuffles is given (if $r=1$)
the elements of $U$ and a table containing all information
about the action by permutation and the values of $\chi$.

Now the program asks for the first monomial and then for the second
and computes the bilinear form and exits. If the first monomial is
preceded by a dot, then the following input data (including the
special options) can be applied to several first monomials. The
program asks for these input data and then after the computation
prompts again for the first monomial. This is repeated until a first
monomial of length 1 appears. This loop is restarted with other input
data when another first monomial, preceded with a dot, is given.
If the first monomial
has length $>1$ and the second has length 1, special options
are used: the program asks to input one of 3 modes, A, B, and C.
In mode 'A', the bilinear form of the first monomial and 
all second monomials of the same length is computed (starting
from the monomial which is given by the user; if it is too short,
then the first element of $U$ is joint to it to give it the correct length).
If, for some second monomial, the bilinear form does not vanish, the
second monomial is printed out followed by the number of non-vanishing
summands used to compute the bilinear form (optional) and the value
of the bilinear form. (Actually many values of the second monomial
for which the bilinear must vanish are skipped; if the information that
squares of the elements of $U$ vanish, is given above, then also monomials
with two equal adjacent factors are skipped). This mode can be used 
to prove that certain monomials vanish in $B(V)$ (if the bilinear
form with all other monomials vanishes) or to compute relations:
When this mode has been performed with a set of monomials, then the user
may find a linear combination of them so that for all other monomials
the bilinear form will vanish. For this purpose only the other monomials
have to be considered which give non-vanishing bilinear form and therefore
are contained in the output. Here it may be useful to use the simple
output format (cf.~last output option in line 2 of the input file
as described above) in order to make component-wise linear combinations
more easy.

Mode B is the same as mode A, but the program asks the user for limit
for the number of summands which should contribute to the value of
the bilinear form (when the limit is reached, computation is aborted
at once). This is heuristical and may exclude some second monomials which
give zero values of the bilinear form but use excessive computation
time. If $G$ is non-commutative, sometimes a good limit may be 2.
The limit is ignored if it is smaller than 2. Only in this case, dots
are printed out for whenever a multiple of a certain number of summands
of the bilinear form has been computed.

Mode C is used to (heuristically) find large non-vanishing monomials in 
$B(V)$. Here the bilinear form of the first monomial with itself is computed,
if it vanishes or a limit of summands is reached (cf.~previous paragraph)
then this monomial is skipped and the last factor is replaced by the
next element of $U$ (if it is already the last element, then the last
factor is removed and the last factor of the remaining monomial is
replaced by the next element; this is allowed to happen for more than
one time). If the bilinear form does not vanish then this monomial
must not vanish in $B(V)$ and the first element of $U$ is joint to
the monomial. After this, the bilinear form of the new monomial with itself
is computed. This is done as long as the maximal length of monomials
is exceeded or there is no monomial to examine any more. The program
asks if the length of the monomials should be printed out: if the answer
is yes, then whenever a non-zero monomial has been found, it is preceeded
by its length and a blank. If the action of the generators of B(V) on the
generators is non-trivial, then the program asks whether a non-zero
monomial should be marked (with a dot directly after the monomial) if 
the composition of the actions of the factors of the monomial (evaluated 
from left to right) is the identity (this should hold for longest monomials 
if $B(V)$ is finite-dimensional). If the output of unsuccessful attempts
is not suppressed, a monomial is printed out between "." and "!" if the
limit has been reach and computation is aborted, and ":" is printed out
if the bilinear form of a monomial with itself vanishes (this helps for
very long lasting calculations in order to see how far the program has
already computed).
For some examples with non-commutative groups, the limit 2 and the lowest
monomial of length 2 as first monomial have given very large non-vanishing
monomials in $B(V)$ (which are in some cases longest 
monomials --- unfortunately not in all cases), much better than a random 
choice for a large first monomial. The limit is ignored if it is smaller 
than 2.

If a second parameter is specified then it is regarded as the name of the 
output file. All output on the screen will be appended to the file; if it does
not exist, it will be created. 
If the output file exists and its first character is not a blank, then
the first lines are regarded as input which is normally asked by the
program from the user (Note that the normal output of the program starts 
with a blank. This means that normal output is never regarded to be 
input), in the matter as described above (i. e. starting with the value of the
first monomial). The data should be separated by end-line characters
(i. e. value of the first monomial in the first line, value of the
second monomial in the second line). You should be careful about the
contents of the input file because if errors occur, no line number 
will be specified (but when you check the output file after the error
has occurred, the erroneous data are at the end of the last line). 
The output of the program is written exclusively
to the output file, not on the screen (except for error messages, which
usually happen only in the very beginning). This version can be used
to run the program for a very long time in the background; the advantage
is that there is no output on the screen, or for many sessions with
slightly different input data: only change the first lines of the file,
the output of the next session is appended to the file.
\bigskip
\noindent Examples of sessions: Session for first example input file: {\tt \obeylines\obeyspaces

\ Order of the root of unity:~5
The number of steps is indicated.
Information about lengths and aborted computations is given.
Print out a dot for each multiple of 1000 computed summands
Generators of B(V):~ab
Left generator of B(V) acts on the upper as ...; on the right:~values of chi
\  ab    a  b
a ab    2  4
b ab    4  2
Input of monomials, maximal length 50
First monomial:~abababab
Second monomial (if of length 1:~special modes):~babababa
(576):~-118-63q-33q\^{}2-135q\^{}3
}
\bigskip
The following  computation shows that for the second input file the monomials
"121" and "212" are equal in $B(V)$ (because the bilinear form of each
of these monomials with any monomial has the same value and thus the
difference of these is 0 because the bilinear form is non-degenerate). Session for monomial "121":
{\tt\obeylines\obeyspaces
\ Order of the root of unity:~2
Squares of the generators vanish.
The number of steps is indicated.
Print out a dot for each multiple of 10 computed summands
Generators of B(V):~123456
Left generator of B(V) acts on the upper as ...; on the right:~values of chi
\  123456
1 145236  1
2 426153  1
3 563412  1
4 213465  1
5 321654  1
6 132546  1
Input of monomials, maximal length 50
First monomial:~.121
The following input is considered repeatedly until first monomial has length 1.
Second monomial (if of length 1:~special modes):~1
Special modes (A:~comparison with all monomials
B:~like A, but with limit
C:~automatic search for big non-zero monomial):~a
Start value for the second monomial:~1
The program starts with 111
121(1):~1
142(1):~-1
212(1):~1
241(1):~-1
First monomial:~212
121(1):~1
142(1):~-1
212(1):~1
241(1):~-1
First monomial:~1
}

\bigskip
This output can also be created using the
second parameter which should denote a file consisting of the following lines
(then the above output is appended to these lines). Note that the first
line does not start with a blank so that the file is regarded as input file.
{\tt\obeylines
.121
1
a
1
212
1
}
\bye