## First choose generators for Free group so that w = [n,0] in H_1(F)

G := FreeGroup(2);
gens := GeneratorsOfGroup(G);
a := gens[1];
b := gens[2];


Na := function(w)
local z;
z := ExponentSumWord(w,a);
return(z);
end;

Nb := function(w)
local z;
z := ExponentSumWord(w,b);
return(z);
end;

CyclicRed := function(w)
local j,t,z;
z := w;
t := Length(w);
for j in [1 .. Length(w)] do
if Length(Subword(w, 1, j)^-1*w*Subword(w,1,j)) < t
or NumberSyllables(Subword(w, 1, j)^-1*w*Subword(w,1,j)) <
                 NumberSyllables(z)  then
z := Subword(w, 1, j)^-1*w*Subword(w,1,j);
t := Length(z);
fi;
od;
return z;
end;

IsNonGeom := function(w)
local s,t,expsa, expsb,v;
s := 0;
expsa := [];
expsb := [];
v := CyclicRed(w);
for t in [1 .. NumberSyllables(v)] do
if t mod 2 = 1 and not AbsInt(ExponentSyllable(v, t)) in expsa then
Add(expsa, AbsInt(ExponentSyllable(v,t)));
fi;
if t mod 2 = 0 and not AbsInt(ExponentSyllable(v, t)) in expsb then
Add(expsb, AbsInt(ExponentSyllable(v,t)));
fi;
od;
if Length(expsa) > 3 or Length(expsb)> 3 then s := 1;
fi;
return(s);
end;


MakeGensNiceOnHom := function(w1)
local t1,z1,transa,transb;
z1 := w1;


while Minimum([AbsInt(Na(z1)),AbsInt(Nb(z1))]) > 0 do
if AbsInt(Na(z1)) > AbsInt(Nb(z1)) then
transa := a;
transb := a^(-1*SignInt(Nb(z1))*SignInt(Na(z1)))*b;
fi;

if AbsInt(Nb(z1)) > (AbsInt(Na(z1))-1) then
transb := b;
transa := a*b^(-1*SignInt(Nb(z1))*SignInt(Na(z1)));
fi;




if AbsInt(Nb(z1)) = 1 and AbsInt(Na(z1))=1 then
transb := b;
transa := a*b^(-1*SignInt(Nb(z1))*SignInt(Na(z1)));
fi;

t1 := MappedWord(z1,[a,b],[transa,transb]);
z1 := t1;


od;

if Na(z1) = 0 then
transa := b;
transb := a;
t1 := MappedWord(z1,[a,b],[transa,transb]);
z1 := t1;
fi;


return z1;
end;



Width := function(w)
local t,j,k,s;
j := 0;
k := 0;
s := 0;
for t in [1 .. Length(w)] do
if Subword(w,t,t) = a then
j := j+1;
fi;
if Subword(w,t,t) = a^-1 then
j := j-1;
fi;
k := Maximum(j,k);
s := Minimum(j,s);
od;
return k-s+1;
end;



#### Check if M is fibered


SpecWidth := function(w)
local t,j,k,s;
j := 0;
k := 0;
s := 0;
for t in [1 .. Length(w)] do
if Subword(w,t,t) = b then
j := j+1;
fi;
if Subword(w,t,t) = b^-1 then
j := j-1;
fi;
k := Maximum(j,k);
s := Minimum(j,s);
od;
return [s,k];
end;


UpWidth := function(w)
local z;
return SpecWidth(w)[2];
end;

DownWidth := function(w)
local z;
return SpecWidth(w)[1];
end;

Width := function(w)
local z;
z := UpWidth(w) - DownWidth(w) + 1;
return z;
end;


NormalWord := function(w)
local i,k,z,stop;
z := w;
for i in [1 .. Length(z)] do
if  (Subword(z, 1, 1) = b or Subword(z,1,1)= b^-1) and
(Subword(z,Length(z),Length(z)) = a or Subword(z,Length(z),Length(z)) = a^-1)
 then return z;
fi;
z := Subword(z,1,1)^-1 *z *Subword(z,1,1);
od;
return z;
end;


MultAtExtremes := function(w)
local z,t,j,n,mult;
z := NormalWord(w);
mult := 0;
j := 0;
n :=  NumberSyllables(z);
for t in [1 .. n] do
if gens[GeneratorSyllable(z,t)] = b then
j := j+ExponentSyllable(z,t);
if j = UpWidth(z) then
mult := mult + AbsInt(ExponentSyllable(z,t+1));
fi;
fi;


od;
return mult;
end;



IsFibered := function(w)
local z,v;

z := 1;
v := MakeGensNiceOnHom(w);

if MultAtExtremes(v) > 1 then 
z := 0;
fi;

return z;
end;



# Take word w, and say width of w is k
# this function represents lift of w in the k-fold cyclic cover
# (smallest to which w lifts) in terms
# of the free generators of the cover.


LiftWord := function(w,k)
local i,t,z, H, gens, x;

H := FreeGroup(k);
gens := GeneratorsOfGroup(H);
x := gens;

z := x[1]*x[1]^-1;
t := 0;
for i in [1 .. Length(w)] do
if Subword(w,i,i) = b then
t := t+1;
fi;
if Subword(w,i,i) = b^-1 then
t := t-1;
fi;
if Subword(w,i,i) = a then
z := z*x[t-DownWidth(w)+1];
fi;
if Subword(w,i,i) = a^-1 then
z := z*x[t-DownWidth(w)+1]^-1;
fi;
od;
return z;
end;




Multihandle := function(w)
local  k,  z, J, H, gens, x,
 Jgens, TranslateWord, D, bust, nhandles, j, i, wdata, t, data, s, handles,
 good, subhandles, subdata, abmat, V, abmatplus,d, independence;

#Check if b_1(M) = 2.  If so, stop.

if Na(w) = 0 and Nb(w) = 0 then
Print("b_1 = 2");
Print("\n");
return [0,0];
fi;

#Check if M is fibered.  If so, stop.

if IsFibered(w) = 1 then
Print("fibered");
Print("\n");
return [0,0];
fi;

#Change basis so homology becomes obvious

w := MakeGensNiceOnHom(w);
w := CyclicRed(w);

k := Width(w);

H := FreeGroup(k);
gens := GeneratorsOfGroup(H);
x := gens;


#Create lift word z1(x1, .., xk)

z := LiftWord(w,k);

#### Determine how many handles are needed until they are busting


# Might need at most 3k 1-handles for algorithm to terminate
# So start with the fundamental group of the genus 3k handlebody


J := FreeGroup(3*k);
Jgens := GeneratorsOfGroup(J);


## This function gives the nth translate of the lift of a lifted word
## in terms of the above 3k free generators

TranslateWord:= function(w,n)
local i,z,transgens;
transgens := [];
for i in [1 .. k] do
Add(transgens, Jgens[i+n]); 
od;
z := MappedWord(w, gens, transgens);
return z;
end;

## D is the set of all lifted 2-handles which fit on the genus 3k handlebody

D := [1 .. 2*k];
for j in [1 .. 2*k] do
D[j] := TranslateWord(z, j-1);
od;


## Look at first i 2-handles in D.  Convert these words into
## strings of integers so that whitehead function can read them.

bust := 0;
nhandles := 0;
for i in [1 .. 2*k] do
if bust = 0 then
wdata := [];
for t in [1 .. i] do
data := [];
for j in [1 .. Length(D[t])] do
for s in [1 .. 3*k] do
if Subword(D[t], j,j) = Jgens[s]
then Add(data, s);
fi;
if Subword(D[t],j,j) = Jgens[s]^-1
then Add(data, s+k+i-1);
fi;
od;
od;
Add(wdata, data);
od;
nhandles := nhandles+1;

## Now check if they are busting.

bust :=  Whitehead(k+i-1, wdata)[1];
fi;

## Stop when you get an initial  sequence which are busting

od;

## If no initial sequence was busting, terminate in failure

if bust = 0 then
Print("multihandle failure");
Print("\n");
 return [k,0];
fi;


# Let "handles" represent the sequence of busting disks. 
#   For each i, Compute whether handles - (ith handle)  busts. 
#   Moreover, whether the unbusted disks
#   are contained in ab. gp. gen by remaining handles.
#   If not for all i, then by multi-hand add. lemma, report success at n.



handles := [];
for i in [1 .. nhandles] do
 Add(handles, wdata[i]);
od;


good := 1;


if nhandles > 1 then
for i in [1 .. nhandles-1] do
subhandles := ShallowCopy(handles);
RemoveSet(subhandles, handles[i]);

## subdata[3] is number disks busted by handles - (ith handle)
## this checks if handles - (ith handle) busts, and if so returns badness

subdata := Whitehead(k+nhandles-1,subhandles);
if subdata[2] = k+nhandles-1
then good := 0;
fi;

## Let E_1, .., E_{k+nhandles-1}
## be the basis for the disks in the lifted handlebody.
## If handles - (ith handle) does not bust, 
## check if there is an unbusted disk which has an algebraically nonzero
## number of E_j components for some j \leq i.   If so, then
## this disk must be independent from handles_{i+1}, .., handles_{nhandles}
## in H_1(boundary of lifted handlebody), satisfying our multihandle
## addition lemma

if subdata[3] < k+nhandles-1 then

independence := 0;
V := subdata[3];
for s in [1 .. Length(V)] do
for t in [1 .. Length(V[s])] do
if V[s][t] < i+1 then independence := 1;
fi;
od;
od;

if independence = 0 then
good := 0;
fi;

fi;



od;
fi;

if good = 0 then
Print("multi-handle failure");
Print("\n");
return[k,0];
fi;

return [k,nhandles+k-1];
end;