Re: Finding coefficients in linear combination

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Wed, Mar 13, 2024 at 03:37:32PM +0000, Swati, NoFirstName wrote:
> Hello all,
> I am trying to look for an efficient way to compute the coefficients a_{i} in the linear combination of  the form
> \Delta^{129} \mid T_{17} \equiv \sum{j = 1}^{i} a_{i} \Delta^{i} \pmod{3}
> using pari/gp.
> I figured out if I compute the LHS first and accordingly, keep subtracting
> terms from RHS, it takes way longer time. Could someone refer to a better way
> for performing this computation?

You can do this, I think:

Deltamod3(n)=q*prod(k=1,n,1-q^k*Mod(1,3)+O(q^(n+1)))^24;
T(f,m)=f=truncate(f);sum(n=0,poldegree(f)\m,sumdiv(gcd(m,n),r,polcoeff(f,m*n/r^2)*r)*q^n) + O(q^(poldegree(f)\m +1));

A = T(Deltamod3(1700)^129,17)
B = Deltamod3(100)

lindep(concat(A,vector(30,i,B^(6+9*i))))

which gives
  [1,1,2,1,2,2,2,1,2,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]~

So

a_15:Mod(2,3)
a_24:Mod(1,3)
a_33:Mod(2,3)
a_42:Mod(1,3)
a_51:Mod(1,3)
a_60:Mod(1,3)
a_69:Mod(2,3)
a_78:Mod(1,3)
a_87:Mod(0,3)
a_96:Mod(0,3)
a_105:Mod(2,3)

and all the others are 0.

Cheers,
Bill.