######################################################################
## Kronecker.txt Save this file as  Kronecker.txt  to use it,        #
# stay in the                                                        #
## same directory, get into Maple (by typing: maple <Enter> )        #
## and then type:  read Kronecker.txt<Enter>                         #
## Then follow the instructions given there                          #
##                                                                   #
## Written by Doron Zeilberger, Rutgers University ,                 #
##  DoronZeil at gmail dot com                                       # 
######################################################################

with(combinat):

print(`First Written: March 2022: tested for Maple 2020 `):
print():
print(`This is Kronecker.txt A Maple package`):
print(`To compute the sequenes that are  of the inner product of (Chi_lamba)^k and Chi_mu for any parttions (of the same length, of course) lambda and mu, and their generating functions`):
print(`as well as the sum with respect to mu of the above, and trying to formulate general conjectures for infinite families`):
print():
print(`It accompaines the paper `):
print(`Experimenting with Kronecker products Related to the characters of the Symmetric Group [temporary title]`):
print(`By Ron Adin, Arvind Ayyer, Shalosh B. Ekhad, and Yuval Roichamn `):
print(``):
print(`The most current version is available on WWW at:`):
print(` http://sites.math.rutgers.edu/~zeilberg/tokhniot/Kronecker.txt .`):
print(`Please report all bugs to: DoronZeil at gmail dot com .`):
print():


print(`For general help, and a list of the MAIN functions,`):
print(` type "ezra();". For specific help type "ezra(procedure_name);" `):
print(`For a list of the supporting functions type: ezra1();`):
print():
 




ezra1:=proc()

if args=NULL then

print(`The supporting procedures are`):
print(` Chi1, Cnu, CoeTnkSeq, GuessPol, IP1, ParToF,  YUVALn1, YUVAL1, YUVAL1Numer`):
else
ezra(args):

fi:


end:

ezra:=proc()
if args=NULL then

print(`The MAIN procedures are`):
print(` ConjYUVAL, GFijn, GFin, PaperAY,  Sijn, Sin, Sn1, Tnk,`):


elif nargs=1 and args[1]=Chi1 then
print(`Chi1(L,M): Chi_L(M) where L and M are partitions given in the decreasing notation. Try`):
print(`Chi1([5,4],[2,2,1]);`):

elif nargs=1 and args[1]=Cnu then
print(`Cnu(nu): inputs a partition, nu, of n, say, and outputs the size of the conjugacy class in S_n. Try:`):
print(`Cnu([5,4];`):

elif nargs=1 and args[1]=CoeTnkSeq then
print(`CoeTnkSeq(N,j): The sequence of coefficients of (n-j)^k in Tnk(n,k) for n from 1 to N. Do`):
print(`CoeTnkSeq(12,0);`):

elif nargs=1 and args[1]=ConjYUVAL then
print(`ConjYUVAL(N,x): conjectues closed-form expressions for the generating function of Tnk(n,k) w.r.t. to k for symbolic n, as far as possible using N data points`):
print(`It assumes that the denominator is (1-x)*(1-2*x)...*(1-(n-3)*x)*(1-n*x).. Try:`):
print(`ConjYUVAL(10,x);`):

elif nargs=1 and args[1]=GFijn then
print(`GFijn(i,j,n,x): Inputs  a positive integer n, two integers i and j between 1 and nops(Partition(n)) and a varible x and outputs the generating function in x`):
print(`Let Lambda:=Partition[i]. and Mu:=Partition[j]. It outputs the generating function of the inner product of Chi[Lambda]^k and the Mu column of the character table. Try:`):
print(`GFijn(2,3,4,x);`):


elif nargs=1 and args[1]=GFin then
print(`GFin(i,n,x): Inputs  a positive integer n, and an integer i between 1 and nops(Partition(n)) and a varible x and outputs the generating function in x`):
print(`The sum of GFijn(i,j,n,x) for all j from 1 to nops(Partition(n)). Try:`):
print(`GFin(2,4,x);`):

elif nargs=1 and args[1]=GuessPol then
print(`GuessPol(L,n,s0): guesses a polynomial of degree d in n for`):
print(` the list L, such that L[i]=P[i] for i>=s0 for example, try: `):

elif nargs=1 and args[1]=IP1 then
print(`IP1(V,j,n): inputs a vector V of length Partition(n), an integer j between 1 and nops(Partition(n)), and n, outputs the inner product of V and the j-th column`):
print(`Corresponding to the partition Partiton(n)[j], of the character table. `):

elif nargs=1 and args[1]=ParToF then
print(`ParToF(P): translates a partition to frequency notation, try:`):
print(`ParToF([3,3,3,2,2]);`):

elif nargs=1 and args[1]=PaperAY then
print(`PaperAY(K): inputs an integer K and outputs all the generating functions GFijn(i,j,n,x) and GFin(i,n,x) for n from 1 to K, and 1<=i,j<=nops(Partition(n))): Try:`):
print(`PaperAY(4);`):


elif nargs=1 and args[1]=S1 then
print(`S1(n,k): The sum of the  inner product of Sum of (Chi{n-1,1)+1)^k  with Chi_mu for all mu`):

elif nargs=1 and args[1]=Sijn then
print(`Sijn(i,j,n,x): Inputs  a positive integer n, two integers i and j between 1 and nops(Partition(n)) and a discete variable k and o`):
print(`Let Lambda:=Partition[i]. and Mu:=Partition[j]. It outputs the sequence of the inner product of Chi[Lambda]^k and the Mu column of the character table. Try:`):
print(`Sijn(2,3,4,k);`):


elif nargs=1 and args[1]=Sin then
print(`Sin(i,n,k): Inputs  a positive integer n, and an integer i between 1 and nops(Partition(n)) and a discrete varible k and outputs the sequence, in terms of k of`):
print(`The sum of Sijn(i,j,n,k) for all j from 1 to nops(Partition(n)). Try:`):
print(`Sin(2,4,k);`):

elif nargs=1 and args[1]=Sn1 then
print(`Sn1(n,j,k): The the inner product of (Chi{n-1,1)+1)^k  with the j-th column of the character table. k must be numeric. Try:`):
print(`Sn1(5,3,k);`):

elif nargs=1 and args[1]=Tnk then
print(`Tnk(n,k): Arvind-style formula in k, for symbolic k, of the quantity S1(n,k) (q.v.). Try`):
print(`Tnk(10,k);`):

elif nargs=1 and args[1]=YUVAL1 then
print(`YUVAL1(n,x): The generating function of the sum of inner product of (Chi{n-1,1)+1)^k  with Chi_mu for all mu. Try:`):
print(`YUVAL1(5,x)`):


elif nargs=1 and args[1]=YUVAL1Numer then
print(`YUVAL1Numer(n,x): The NUMERATOR OF generating function of the sum of inner product of (Chi{n-1,1)+1)^k  with Chi_mu for all mu. It assumes that the denominator is`):
print(` (1-x)*(1-2*x)...*(1-(n-3)*x)*(1-n*x). `):
print(`Try:`):
print(`YUVAL1Numer(5,x)`):

elif nargs=1 and args[1]=YUVALn1 then
print(`YUVALn1(n,j,x): The generating function of the inner product of (Chi{n-1,1)+1)^k  with Chi_j. Try:`):
print(`YUVALn1(5,2,x)`):


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

fi:


end:




#GuessPol1(L,d,n,s0): guesses a polynomial of degree d in n for
# the list L, such that L[i]=P[i] for i>=s0 for example, try: 
#GuessPol1([(seq(i,i=1..10),1,n,1);
GuessPol1:=proc(L,d,n,s0) local P,i,a,eq,var:
if d>=nops(L)-s0-2 then
 ERROR(`the list is too small`):
fi:

P:=add(a[i]*n^i,i=0..d):
var:={seq(a[i],i=0..d)}:
eq:={seq(subs(n=i,P)-L[i],i=s0..s0+d+3)}:

var:=solve(eq,var):

if var=NULL then
 RETURN(FAIL):
fi:

subs(var,P):

end:



#GuessPol(L,n,s0): guesses a polynomial of degree d in n for
# the list L, such that L[i]=P[i] for i>=s0 for example, try: 
#GuessPol([(seq(i,i=1..10),n,1);
GuessPol:=proc(L,n,s0) local d,gu:

for d from 0 to nops(L)-s0-3 do
 gu:=GuessPol1(L,d,n,s0):
 if gu<>FAIL then
    RETURN(gu):
 fi:
od:

FAIL:

end:

#PaperAY(K): inputs an integer K and outputs all the generating functions GFijn(i,j,n,x) and GFin(i,n,x) for n from 1 to K, and 1<=i,j<=nops(Partition(n))):
PaperAY:=proc(K) local gu,i,j,F,t0,x,i1,lu,n:
t0:=time():
print(`Generating functions for Sequences of interest to Arvind Ayyer and Yuval Roichamn`):
print(``):
print(`By Shalosh B. Ekhad `):
print(``):
print(`Let n be a positive integer, and let Lambda and Mu be two partitions of n. Let`):
print(``):
print(`F[Lambda,Mu][k]:= The inner product of the k-th power of the Lambda-column of the Character Table of Sn, and the Mu-column and let`):
print(`f(Lamda,Mu](x):=Sum(F[Lambda,Mu][k]*x^k,k=0..infinity`):
print(``):
print(`Here is everything up to n=`, K):

for n from 1 to K do
print(``):
print(`------------------------------------------`):
print(``):
print(`Doing the symmetric group on`, n, ` elements `):
gu:=Partition(n):
print(`There are`, nops(gu), `partitions of`, n, `here there are in the usual order `):

for i from 1 to nops(gu) do
print(`Regarding Lambda=`, gu[i]):
print(``):
for j from 1 to nops(gu) do
lu:=GFijn(i,j,n,x):
print(F[gu[i],gu[j]](x)=lu):
print(``):
print(`and in Maple notation`):
print(``):
lprint(F[gu[i],gu[j]](x)=lu):

print(``):
print(`The first 20 term , starting with k=1 are `):
print(``):
print(seq(coeff(taylor(lu,x=0,21),x,i1),i1=1..20)):
print(``):
print(`----------------------------------`):
print(``):
print(`Their sum is`):
lu:=GFin(i,n,x):
print(``):
print(lu):
print(``):
print(`and in Maple notation`):
print(``):
lprint(lu):
print(``):
print(``):
print(`The first 20 term , starting with k=1 are `):
print(``):
print(seq(coeff(taylor(lu,x=0,21),x,i1),i1=1..20)):

od:
od:
od:

print(`This ends this book that took`, time()-t0, `seconds to generate `):

end:


#ParToF(P): translates a partition to frequency notation, try:
#ParToF([3,3,3,2,2]);
ParToF:=proc(P) local i,a,mu:
if P=[] then
 RETURN([]):
fi:

a:=P[1]:

for i from 1 to nops(P) while P[i]=a do od:

mu:=[op(i..nops(P),P)]:

mu:=ParToF(mu):
[[a,i-1],op(mu)]:
end:

#Cnu(nu)
Cnu:=proc(nu) local L,n,i:

n:=convert(nu,`+`):

L:=ParToF(nu):

n!/mul(L[i][1]^L[i][2],i=1..nops(L))/mul(L[i][2]!,i=1..nops(L)):

end:


RevMM:=proc(P) local i,N: N:=nops(P): [seq(P[N-i+1]   , i=1..N)]: end:


Partition:=proc(n)
local P,i,N:

P:=partition(n):
N:=nops(P);

RevMM([seq(RevMM(P[i]),i=1..N)]):

end:


#Chi1(L,M): Chi_L(M) where L and M are partitions given in the decreasing notation. Try
#Chi1([5,4],[2,2,1]);
Chi1:=proc(L,M)
Chi(RevMM(L),RevMM(M)):
end:

#IP1(V,j1,n):
IP1:=proc(V,j1,n) local i,P:
P:=Partition(n):

add(Cnu(P[i])*V[i]*Chi1(P[j1],P[i]),i=1..nops(V))/n!;
end:



#GFijn(i,j,n,x): Lambda=Partition(n)[i]; Mu=Partition(n)[j] 
GFijn:=proc(i,j,n,x) local P,i1,V:
P:=Partition(n):
#V:=[seq(1/(1-T[i1][i]*x),i1=1..nops(T))]:
V:=[seq(1/(1-Chi1(P[i], P[i1])*x),i1=1..nops(P))]:
factor(normal(IP1(V,j,n))):

end:



#GFin(i,n,x): Lambda=Partition(n)[i]; 
GFin:=proc(i,n,x) local j:
factor(add(GFijn(i,j,n,x) ,j=1..nops(Partition(n)))):
end:





#YUVALn1(n,j,x): The generating function of the inner product of (Chi{n-1,1)+1)^k  with Chi_j
YUVALn1:=proc(n,j,x) local gu:
gu:=GFijn(2,j,n,x):
gu:=factor(subs(x=x/(1-x),gu)/(1-x)):
end:


#YUVAL1(n,x): The generating function of the inner product of Sum of (Chi{n-1,1)+1)^k  with Chi_mu for all mu
YUVAL1:=proc(n,x) local j:
factor(add(YUVALn1(n,j,x),j=1..nops(Partition(n)))):
end:



#YUVAL1Numer(n,x): The numerator of the generating function of the inner product of Sum of (Chi{n-1,1)+1)^k  with Chi_mu for all mu
YUVAL1Numer:=proc(n,x) local gu,i1:
option remember:
gu:=YUVAL1(n,x):
gu:=expand(normal(gu*mul(1-i1*x,i1=1..n-3)*(1-n*x))):

end:



#Tnk(n,k): Arvind-style formula in k
Tnk:=proc(n,k) local gu,f,a,eq,var,i,i1,x:
option remember:
gu:=YUVAL1(n,x):

var:={seq(a[i],i=1..n-3),a[n]}:

f:=add(a[i]*i^k,i=1..n-3)+a[n]*n^k:

gu:=taylor(gu,x=0,2*n+1):

eq:={seq(coeff(gu,x,i1)-subs(k=i1,f),i1=1..n+3)}:
var:=solve(eq,var):
if var=NULL then
 RETURN(FAIL):
fi:

subs(var,f):


end:



#Sijn(i,j,n,k): Lambda=Partition(n)[i]; Mu=Partition(n)[j] 
Sijn:=proc(i,j,n,k) local P,i1,V:
P:=Partition(n):
V:=[seq(Chi1(P[i], P[i1])^k,i1=1..nops(P))]:
IP1(V,j,n):

end:


#Sin(i,n,x): Lambda=Partition(n)[i]; 
Sin:=proc(i,n,x) local j:
add(Sijn(i,j,n,x) ,j=1..nops(Partition(n))):
end:



#Sn1(n,j,k): The the inner product of (Chi{n-1,1)+1)^k  with the j-th column of the character table
Sn1:=proc(n,j,k) local r:
add(binomial(k,r)*Sijn(2,j,n,r),r=0..k):
end:


#S1(n,k): The sum of the  inner product of Sum of (Chi{n-1,1)+1)^k  with Chi_mu for all mu
S1:=proc(n,k) local j:
add(Sn1(n,j,k),j=1..nops(Partition(n))):
end:


#CoeTnkSeq(N,j): The sequence of coefficients of (n-j)^k in Tnk(n,k) for n from 2 to N. Do
#CoeTnkSeq(12,0);
CoeTnkSeq:=proc(N,j) local n,k:
[seq(coeff(Tnk(n,k),(n-j)^k,1),n=2..N)]:
end:



#ConjYUVAL(N,x): conjectues closed-form expressions for the generating function of Tnk(n,k) w.r.t. to k for symbolic n, as far as possible using N data points
#It assumes that the denominator is (1-x)*(1-2*x)...*(1-(n-3)*x)*(1-n*x).. Try:
#ConjYUVAL
ConjYUVAL:=proc(N,x) local gu,i,n,P,i1,lu,lu1,pol,n1:
print(`Let f_n(x) be the generating function of Sum of (Chi{n-1,1)+1)^k  with Chi_mu for all mu`):
print(`Then it follows from the character table (probably) that the denominator is predicible`):
print(``):
print((1-n*x)*Product(1-i*x,i=1..n-3)):
print(``):
print(`Hence the numerator is a polynomial of degree n-2 and can be written`):
print(``):
print(Sum(P[i](n)*x^i,i=0..n-2)):
print(``):
print(`where we conjecture that P[i](n) is a polynomial of n of degree 2*i`):
lu:=0:
for i from 0 do
lu1:=[seq(coeff(YUVAL1Numer(n1,x),x,i),n1=i+2..N)]:
pol:=GuessPol(lu1,n,i+1):
if pol=FAIL then
print(`The numerator, up to`, x^(i-1), `starts as `):
print(lu):
RETURN(lu):
else
lu:=lu+factor(subs(n=n-2,pol))*x^i:
print(`so far the numerator is`):
print(lu):
fi:
od:

end: