Re: Looking for a smaller solution...

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

On Wed, Jan 25, 2023 at 11:13:58AM +0100, Bill Allombert wrote:
> > b(x,y,P)={G=znstar(x,1);matsolvemod(matconcat(vector(#P,i,znlog(P[i],G))),G.cyc~,znlog(y,G))}
> > which "outputs a vector giving the exponents that each of the primes in P
> > need to be raised to in the product."  ie B = product(P[i]^e[i]) where e[i]
> > is the output of the above function.
> 
> There is an option to matsolvemod to give all solutions:
> b(x,y,P)={G=znstar(x,1);matsolvemod(matconcat(vector(#P,i,znlog(P[i],G))),G.cyc~,znlog(y,G),1)}
> 
> ? [E,M]=b(97929,83261,[1171, 1429, 1811, 2339])
> %5 = [[843,1311,325,330]~,[270,204,204,23;0,18,12,6;0,0,6,3;0,0,0,1]]
> 
> All the solutions can be written as E+M*v where v is a column vector with integral entries.
> 
> So you can try to pick v to get smaller entries, for example take v=[0,0,0,-36]~
> ? E+M*[0,0,0,-36]~
> %13 = [15,1095,217,294]~

Finding the best v in general can be difficult. In this example it was easy:

? A=matconcat([M,E;0,1]);U=qflll(A);A*U
%52 =
[2  4  0  3   6]

[3  0 -6 -3   0]

[4 -4  6 -3   2]

[1 -4  0  6   0]

[1  2  0  3 -10]

The first column is positive and ends by 1, so it gives the solution [2,3,4,1]~
(with v=U[1..4,1] = [-31, -37, 111, -329]~)

and indeed:

? factorback([1171, 1429, 1811, 2339],[2,3,4,1])%97929
%54 = 83261

But in general, we might only find small solutions with rational coefficients.

Cheers,
Bill