enumerating sums of 2/3/4 squares for integers

[dimpase]

Is there an existing issue for this?

• I have searched the existing issues for a bug report that matches the one I want to file, without success.

Problem Description

given $n\in\mathbb{N}$, sometimes one needs all the possible (perhaps up to ordering of parts by size)
decompositions of $n$ into sums of as few squares as possible, not just one, which are currently provided, e.g. in
#6509 for 4 squares.

Not sure whether there are studies for this.

Proposed Solution

impelement!

Alternatives Considered

same situation in sympy, see https://docs.sympy.org/latest/modules/solvers/diophantine.html#sum-of-squares

[jnash10]

Hi,

I'd like to tackle this.

Could you confirm the problem statement for me:

Let $sum\textunderscore of\textunderscore squares(n,k)$ be as defined in Sympy: https://docs.sympy.org/latest/modules/solvers/diophantine.html#sum-of-squares

Given $n$, you want:
$sum\textunderscore of\textunderscore squares(n,1)$, $sum\textunderscore of\textunderscore squares(n,2)$, $sum\textunderscore of\textunderscore squares(n,3)$,.... and so on

Maybe a list containing all of those.

Is that correct?

[dimpase]

Thanks for pointing out that actually sympy already has what I want!

I'd then think that the most natural would be to use this facility in Sage, and replace slow three_squares, four_squares in src/sage/arith/misc.py with sympy's provided implementations. (Sage also has fast versions of these, with _pyx suffix, these are probably faster than what sympy offers).
Of course, care needs to be taken so that Sage default integers, ZZ, are understood and supported.

[jnash10]

If I'm not wrong, Sympy comes already bundled in Sage.

In that case, just importing $sum\textunderscore of\textunderscore squares$ from sympy should do the job.

Please let me know if that's not the desired method? I'm still new to sage development.

[jnash10]

Or do you meant to say:
Inside Sage's $sum\textunderscore of\textunderscore three\textunderscore squares$ we make a function call to sympy's $sum\textunderscore of\textunderscore squares$ to speed things up?

[jnash10]

Sage seems to be faster than sympy:

sage: from arith import misc
sage: misc.three_squares(763)
(3, 5, 27)
sage: %timeit misc.three_squares(763)
895 ns ± 3.21 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
sage: from sympy.solvers.diophantine.diophantine import sum_of_three_squares, sum_of_squares
sage: sum_of_three_squares(763)
(3, 5, 27)
sage: %timeit sum_of_three_squares(763)
15 µs ± 72.1 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
sage: list(sum_of_squares(763, 3))
[(3, 15, 23), (3, 5, 27)]
sage: %timeit list(sum_of_squares(763, 3))
1.72 ms ± 13 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each) 

I hope I didn't misinterpret what you were saying.