######################################################################
##MNTD.txt: Save this file as  MNTD.txt                              #
## To use it, stay in the                                            #
##same directory, get into Maple (by typing: maple <Enter> )         #
##and then type:  read `MNTD.txt`<Enter>                             #
##Then follow the instructions given there                           #
##                                                                   #
##Written by Doron Zeilberger, Rutgers University ,                  #
#DoronZeil at gmail dot com                                          #
######################################################################
 
#Created: May 29, 2018
 
print(`Created:  May 29, 2018`):
print(`This version: May 30, 2018, thanks to Joe Buhler`):
print(` This is MNTD.txt `):
print(`It is fo implement `):
print(` the interesting article "Maxially nontransitive dice" by Joe Buhler, Ron Graham, and Al Hales" `):
print(` Amer. Math. Monthly v. 125 No.5 (May 2018), 387-399 `):
print(` http://www.math.ucsd.edu/~ronspubs/pre_nontransitive.pdf `):
print(``):
print(`Please report bugs to DoronZeil at gmail dot com `):
print(``):
 print(`The most current version of this  package and paper`):
 print(` are  available from`):
 print(`http://www.math.rutgers.edu/~zeilberg/  .`):


print(`---------------------------------------`):
 print(`For a list of the Supporint procedures type ezra1();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):
print(`---------------------------------------`):

print(`---------------------------------------`):
 print(`For a list of the MAIN procedures type ezra();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):
print(`---------------------------------------`):

ezra1:=proc()

if args=NULL then
 print(` The supporting procedures are:  AmB, IsBGH, IsSat, LtoD, Sx, Skv  `):
 print(``):

else
ezra(args):
fi:

end:

ezra:=proc()

if args=NULL then
 print(`The main procedures are:  BGH, Conjn0, Dab, PL, PW, Tou, TouS, TouSv `):
 print(` `):

elif nops([args])=1 and op(1,[args])=AmB then
print(`AmB(A,B,x): given two lists of numbers A and B representing the denominations in fair dice, finds the`):
print(`prob. gen. function of A-B. Try:`):
print(`AmB([2,6,7],[1,5,9],x);`):

elif nops([args])=1 and op(1,[args])=BGH then
print(`BGH(k,x): the Buhler-Graham-Hales maximally non-transitive dice constructed in the proof of Theorem 1 of`):
print(`the article "Maxially nontransitive dice" by Joe Buhler, Ron Graham, and Al Hales" `):
print(`Amer. Math. Monthly v. 125 No.5 (May 2018), 387-399. Try: `):
print(`BGH(3,x);`):

elif nops([args])=1 and op(1,[args])=Conjn0 then
print(`Conjn0(a,b,N): conjectures the value of n0 in Theorem 2, by trying N values, and then confirming with another N`):
print(`Conjn0(2,3,40);`):


elif nops([args])=1 and op(1,[args])=Dab then
print(`Dab(a,b,x): the die with span b and shift a given in Theorem 4 of the `):
print(`the article "Maxially nontransitive dice" by Joe Buhler, Ron Graham, and Al Hales" `):
print(`Amer. Math. Monthly v. 125 No.5 (May 2018), 387-399. Try: `):
print(`Dab(2,3,x);`):


elif nops([args])=1 and op(1,[args])=IsBGH then
print(`IsBGH(L): inputs a list of pairs [[ai,bi]] decides whether it meets the [BGH] criteria, i.e. that`):
print(`the dice [Dab(a1,b1,x), ..., Dab(ak,bk,x)] is  maximally transitive. Try`):
print(`IsBGH([[2,3],[5,7],[8,11]]);`):

elif nops([args])=1 and op(1,[args])=IsSat then
print(`IsSat(v), is the vector v saturated? (see  Def. at top of p. 392 of [BGH]). Try`):
print(`IsSat([1/2,1/3,1/5]);`):

elif nops([args])=1 and op(1,[args])=LtoD then
printt(` LtoD(L,x): inputs a list of numbers, outputs the prob. gen. function of a nops(L)-sided fair die with these values.`):
print(`Try:`):
print(`LtoD([1,2,3,4,5,6],x);`):

elif nops([args])=1 and op(1,[args])=PL then
print(`PL(D1,x): given a die D1, expressed in terms of its probability generating function, outputs its probability of losing.`):
print(`Try: PL((x^(-2)+x+x^2)/3,x);`):

elif nops([args])=1 and op(1,[args])=PW then
print(`PW(D1,x): given a die D1, expressed in terms of its probability generating function, outputs its probability of winning.`):
print(`Try: PW((x^(-2)+x+x^2)/3,x);`):

elif nops([args])=1 and op(1,[args])=Skv then
print(`Skv(v): S_k([v1, ..., vk])= [Sx(v1), ..., Sx(vk)]. See p. 391 of [BGH]. Try`):
print(`Skv([1/2,3/4,6/11]); `):


elif nops([args])=1 and op(1,[args])=Sx then
print(`The sign of trunc(x)-1/2. Try:`):
print(`Sx(11/5);`):

elif nops([args])=1 and op(1,[args])=Tou then
print(`Tou(L,x): inputs a list of dice (given in terms of their probability  generating function, in the variable x`):
print(`and outputs the tournament as a list of length nops(L) of lists of length nops(L)`):
print(` call it T, such that T[i][j]=1 if `):
print(` L[i] beats L[j] and -1 otherwise, it is 0 a tie. Of course T[i][j]=-T[j][i].  Try: `):
print(` Tou([(x^2+x^6+x^7)/3,  (x+x^5+x^9)/3, (x^3+x^4+x^8)/3],x); `):
print(`Also try, for the Efron dice`):
#A = [1, 1, 5, 5, 5, 5] , B = [4, 4, 4, 4, 4, 4] , C = [3, 3, 3, 3, 7, 7] , D = [2, 2, 2, 6, 6, 6]
print(` Tou([LtoD([1,1,5,5,5,5 ],x)  , LtoD([4$6 ],x)  , LtoD([3$4,7,7 ],x)  , LtoD([2$3,6$3 ],x)  ], x); `):

elif nops([args])=1 and op(1,[args])=TouS then
print(`TouS(L,x,N): inputs a list of dice (given in terms of their probability  generating function, in the variable x`):
print(`as well as a positive integer N`):
print(`and outputs the lists of Tou(L^i,x) for i from 1 to N.`):
print(`Try:`):
print(`TouS([(x^2+x^6+x^7)/3,  (x+x^5+x^9)/3, (x^3+x^4+x^8)/3],x,20);`):
print(`For the dice in remark 5 of the B-R-H paper`):
print(`TouS([(16*t^2+7*t^(-8)+2*t^12)/25, (11*t^(-9)+33*t+6*t^11)/50, (6*t^(-11)+33*t^(-1)+11*t^9)/50 ],t,20);`):

elif nops([args])=1 and op(1,[args])=TouSv then
print(`TouSv(L,x,N): Same input as TouS, but outputs a list of pairs: [[Tournament, Set Of n such that L^n gives that tournament ]]`):
print(`in first order of appearance`):
print(`To see the output of Figure 1 in [BGH], (in the last tournament the arrow from C to B should be reversed). Type`):
print(`Try:`):
print(`TouSv([(x^2+x^6+x^7)/3,  (x+x^5+x^9)/3, (x^3+x^4+x^8)/3],x,20);`):
print(``):
print(`For the dice in remark 5 of the B-R-H paper`):
print(`TouSv([(16*t^2+7*t^(-8)+2*t^12)/25, (11*t^(-9)+33*t+6*t^11)/50, (6*t^(-11)+33*t^(-1)+11*t^9)/50 ],t,20);`):


else

print(`There is no ezra for`,args):
fi:
 
end:


#LtoD(L,x): inputs a list of numbers, outputs the prob. gen. function of a nops(L)-sided fair die with these values.
#Try:
#LtoD([1,2,3,4,5,6],x);
LtoD:=proc(L,x) local i:
add(x^L[i],i=1..nops(L))/nops(L):
end:

#PW(D1,x): given a die D1, expressed in terms of its probability generating function, outputs its probability of winning.
#Try: PW((x^(-2)+x+x^2)/3,x);
PW:=proc(D1,x) local i,gu:
gu:=expand(D1):
add(coeff(gu,x,i),i=1..degree(gu,x)):
end:

#PL(D1,x): given a die D1, expressed in terms of its probability generating function, outputs its probability of losing
#Try: PL((x^(-2)+x+x^2)/3,x);
PL:=proc(D1,x) local i,gu:
gu:=expand(D1):
add(coeff(gu,x,i),i=ldegree(gu,x)..-1):
end:

#AmB(A,B,x): given two lists of numbers A and B representing the denominations in fair dice, finds the
#prob. gen. function of A-B. Try
#AmB([2,6,7],[1,5,9],x);
AmB:=proc(A,B,x):
expand(LtoD(A,x)*LtoD(B,1/x)):
end:

#Tou(L,x): inputs a list of dice (given in terms of their probability  generating function, in the variable x
#and outputs the tournament as a list of length nops(L) of lists of length nops(L)
#, call it T, such that T[i][j]=1 if
#L[i] beats L[j] and -1 otherwise, it is 0 a tie. Of course T[i][j]=-T[j][i].  Try:
#Tou([(x^2+x^6+x^7)/3,  (x+x^5+x^9)/3, (x^3+x^4+x^8)/3],x);
Tou:=proc(L,x) local i,j,T,gu1,gu2:
for i from 1 to nops(L) do

for j from i+1 to nops(L) do
 gu1:=PW(L[i]*subs(x=1/x,L[j]),x ):
 gu2:=PL(L[i]*subs(x=1/x,L[j]),x ):
 if gu1>gu2 then
   T[i,j]:=1:
   T[j,i]:=-1:
  elif gu1<gu2 then
     T[i,j]:=-1:
     T[j,i]:=1:
   elif gu1=gu2 then
    T[i,j]:=0:
    T[j,i]:=0:
 fi:
od:
T[i,i]:=0:
od:

[seq([seq(T[i,j],j=1..nops(L))],i=1..nops(L))]:

end:


#TouS(L,x,N): inputs a list of dice (given in terms of their probability  generating function, in the variable x
#as well as a positive integer N
#and outputs the lists of Tou(L^i,x) for i from 1 to N.
#Try:
#TouS([(x^2+x^6+x^7)/3,  (x+x^5+x^9)/3, (x^3+x^4+x^8)/3],x,20);
TouS:=proc(L,x,N) local i,j:

[seq( Tou([seq(L[i]^j,i=1..nops(L))],x),j=1..N)]:

end:


#TouSv(L,x,N): Same input as TouS, but outputs a set of pairs: {[Tournament, SetOfn such that L^n gives that tournament ]}
TouSv:=proc(L,x,N) local gu,mu,T,i:

gu:=TouS(L,x,N):
mu:=[]:

for i from 1 to N do
if not member(gu[i],mu) then
mu:=[op(mu),gu[i]]:
 T[gu[i]]:={i}:
else
 T[gu[i]]:= T[gu[i]] union {i}:
fi:
od:

[seq( [mu[i],T[mu[i]] ] ,i=1..nops(mu))]:

end:


#Dab(a,b,x): the die with span b and shift a given in Theorem 4 of the 
#the article "Maxially nontransitive dice" by Joe Buhler, Ron Graham, and Al Hales"
#Amer. Math. Monthly v. 125 No.5 (May 2018), 387-399. Try
#Dab(2,3,x);
Dab:=proc(a,b,x) local x1,x2,x3,v,vs,i:

x1:=a: x2:=a-2*b: x3:=a+3*b:

v:=[(x3^2-x2^2)/x1, (x1^2-x3^2)/x2,(x2^2-x1^2)/x3]:
vs:=convert(v,`+`):
v:=normal([seq(v[i]/vs,i=1..3)]):

v[1]*x^x1+v[2]*x^x2+v[3]*x^x3:

end:






#Sx(x): the sign of {x}-1/2
Sx:=proc(x) local x1:
 x1:=frac(x):
  if x1>0 and x1<1/2 then
   1:
 elif x1>1/2 and x1<1 then
  -1:
 elif x1=0 or x1=1/2 then
   0:
  else
   FAIL:
 fi:
end:

#Skv(v): S_k([v1, ..., vk])= [Sx(v1), ..., Sx(vk)]. See p. 391 of [BGH]
Skv:=proc(v) local i:
[seq(Sx(v[i]),i=1..nops(v))]:
end:


#IsTh2(a,b,n): checks Theorem 2 of the BGH paper for a,b and n. Try
#IsTh2(2,3,20);
IsTh2:=proc(a,b,n) local x,gu,lu:
option remember:
gu:=Dab(a,b,x):
 lu:=PW(gu^n,x):
 if n*a mod b<>0 and n*a mod b<>b/2 and
   sign(lu-1/2)<>sign(1/2-frac(n*a/b)) then
   false:
  else
  true:
 fi:
end:

#Conjn0(a,b,N):
Conjn0:=proc(a,b,N) local i,n0:

for i from N by -1 to 1 while IsTh2(a,b,i)=true do od:
i:
n0:=i+1:

for i from N+1 to 2*N do
if not IsTh2(a,b,i) then
 print(n0, `did not work out, since it i false at`, i):
 RETURN(FAIL):
fi:
od:
n0:

end:


#BGH(k,x): the Buhler-Graham-Hales maximally non-transitive dice constructed in the proof of Theorem 1 of
#the article "Maxially nontransitive dice" by Joe Buhler, Ron Graham, and Al Hales" `):
#Amer. Math. Monthly v. 125 No.5 (May 2018), 387-399`). Try
#BGH(3,x);
BGH:=proc(k,x) local i:
[seq(Dab(2^i,2^((k-i)*(k+i+1)/2),x),i=0..k-1)]:
end:


#SignV(k): all the sign vectors of length k. Try:
#SignV(4);
SignV:=proc(k) local gu,gu1:
if k=0 then
 RETURN({[]}):
fi:
gu:=SignV(k-1):
{seq([op(gu1),1],gu1 in gu), seq([op(gu1),-1],gu1 in gu)}:
end:



#IsSat(v), is the vector v saturated? (see  Def. at top of p. 392 of [BGH]). Try
#IsSat([1/2,1/3,1/5]);
IsSat:=proc(v) local i, M,n:
M:=lcm(seq(denom(v[i]),i=1..nops(v))):
if SignV(nops(v)) minus {seq(Skv(n*v),n=1..M)}={} then
 true:
else
false:
fi:

end:


#IsBGH(L): inputs a list of pairs [[ai,bi]] decides whether it meets the [BGH] criteria, i.e. that
#the dice [Dab(a1,b1,x), ..., Dab(ak,bk,x)] is  maximally transitive. Try
#IsBGH([[2,3],[5,7],[8,11]]);
IsBGH:=proc(L) local i,j,v:
v:=[seq(seq((L[i][1]-L[j][1])/L[j][2],i=1..j-1),j=2..nops(L))]:
IsSat(v):
end: