1
$\begingroup$

I have to deal with a situation where I am trying to decompose numbers written as $2K^2, K\ge0$ into sums of squares, i.e. find: $$S_K=\{(x, y)\ |\ x^2+y^2 = 2K^2\}$$

One of the obvious solutions is $(K, K)$.

I have looked into several papers and found a number of algorithms pertaining to this. Basically the solution seems to be to decompose $K$ into its prime factors, decompose said factors as sums of two squares and apply the Brahmagupta-Fibonacci identity to obtain the decomposition, as in this answer. However, the fact that the only primes (aside from 2) that can be decomposed that way are the primes written as $4k+1$, it lead me to the following question:

Given the unique decomposition $$K = P*Q\\ P=\prod_{i=1}^{m_1}p_i^{\alpha_i}\\ Q=\prod_{j=1}^{m_2}q_j^{\beta_j}$$ Where $p_i$ and $q_j$ are all primes such as $p_i \equiv 1\ [4]$ and $q_j \equiv -1\ [4]$, and $\alpha_i, \beta_j\ge1$.

Can we assert that $S_K = \{(P^2x',P^2y')\ |\ x'^2+y'^2=2Q^2\}$ (reduced problem)? Or can this miss any decompositions?

One inclusion seems right, but I'd like to be sure that this generates all the possible solutions.

$\endgroup$

migrated from mathoverflow.net Dec 14 '16 at 5:00

This question came from our site for professional mathematicians.

  • 1
    $\begingroup$ you don't in fact need to factor K to be able to decompose the number 2K^2 into a sum of squares ( provided of course that 2K^2 is not of the form 4j+3). I provided a method to do that in the link below but I don't know if that will answer your question (which I don't really understand). math.stackexchange.com/questions/1972771/… $\endgroup$ – user25406 Dec 16 '16 at 19:17
  • $\begingroup$ I will take a look at this, it seems very interesting. Thank you very much. $\endgroup$ – pie3636 Dec 18 '16 at 23:27
1
$\begingroup$

This is completely answered in this Physics Forums discussion thread.

$\endgroup$
  • $\begingroup$ Thank you, but this does not actually quite answer it. In the thread you linked, the OP is asking about the same problem as me, but the solutions that are given by the other posters are for $x^2+y^2=(2k)^2$, as the OP noticed in his last post at the bottom of the thread. It was then left unanswered. $\endgroup$ – pie3636 Dec 14 '16 at 3:03
  • $\begingroup$ Also, my question wasn't really about the set of solutions, but rather about whether the reduced problem is equivalent to the first one, since it would imply a much lower computational complexity for me (in terms of algorithmic efficiency rather than pure mathematical solution). $\endgroup$ – pie3636 Dec 14 '16 at 3:08
  • $\begingroup$ @pie3636 Firstly, no, they are talking about the same equation, and the observation is that $x+y, x-y, 2 K$ (in your notation) form a Pythagorean triple. Pythagorean triples are rationally parametrized, so the computational complexity is thus lowered (finding solutions to $x^2 + y^2 = K^2,$ where $K$ is fixed, is equivalent to finding all ways of writing $K$ as the sum of two squares). $\endgroup$ – Igor Rivin Dec 14 '16 at 3:24
  • $\begingroup$ Thank you again, reading the discussion thread again, I indeed see my mistake. That said, finding the solutions still involves writing $z=d(m^2+n^2)/2$ (their $z$ is indeed my $K$), which means that I still have to decompose the factors of $z$ as sums of two squares in order to find possible values of $m$ and $n$ and therefore the solutions, unless I'm mistaken. Which is the part I am trying to optimize by factoring $z$. I apologize if my question wasn't clear enough. $\endgroup$ – pie3636 Dec 14 '16 at 3:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.