Re: question on efficient but exhaustive 3 squares algorithm

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

On Fri, Nov 17, 2023 at 01:54:02PM -0800, American Citizen wrote:
> And I found, comparing the two algorithms that specifically:
> 
>   for n = [1..8] (skipping n=7) the results are identical
> 
>   for n = 9, threesquare only posts [0,0,3], but actually there is [2,2,1]
> also

threesquares() returns a single solution by design.

> It can be seen that threesquare is missing some solutions. Furthermore
> threesquares() blows up for N=7,15,23, etc.

Well, you can call isthreesquares beforehand if you are unsure.

> Can we derive an exhaustive threesquares(N) algorithm which does give all
> solutions for a specific N? and returns [] if
> no such representation occurs. This is the same as solving the [1,1,1,0,0,0]
> ternary quadratric form.

The problem is that the number of solutions grows very quickly (as sqrt(n) in
average), so there is no hope of writing a really fast algorithm, but I can
suggest this simple one

sol3(n)=
{
  Set(concat(vector(sqrtint(n\3+1)+1,j,
    my(i=j-1);
    Set([vecsort(concat(i,abs(v)))|v<-qfbsolve(Qfb(1,0,1),n-i^2,3)])
  )));
}

> P.S.: My imagination is intrigued by a new number type in GP-Pari, called
> "Qft" for Quadratic ternary form and it takes a vector [a,b,c,d,e,f] or 6
> elements for composition. Just a thought ??

It already exist, just set
Qft(a,b,c,d,e,f)=[a,d/2,e/2; d/2,b,f/2; e/2,f/2,c];
and use qfsolve, qfparam, qfisom, qfauto, etc.

Cheers,
Bill