# Is writing a number as two squares and writing the factors of a number equally hard?

Let $L_1$ and $L_2$ be the following:

$L_1=\{r:\exists x,y \in \mathbb{Z} \text{ such that } x^2+y^2=r\}$

$L_2=\{(N,M): M<N, \exists 1<d\leq M \text{ such that d|N} \}$

Claim $L_1 \leq_P L_2$

Sketch Proof

If I want to know whether $r\in L_1$.

The number of integer solutions to $x^2+y^2=r$ is given by

$g(r)=\sum_{d|r}{\chi{(d)}}$ where $\chi (x)=sin(\frac{\pi x}{2})=\cases{ 1\text{ when }x\cong 1 \text{ mod }4 \\ -1 \text{ when }x\cong 3 \text{ mod }4 \\ 0 \text{ when } 2|x }$

Then $L_1=\{r: g(r)\neq 0\}$. So then to answer is "$r\in L_1$?" is at most as hard to answer as "what are the divisors of $r$?"

$\square$

What I would like to know is if this is true the other way around. Is it true that if I had a machine which could tell me in constant time whether $r\in L_1$ could I create a machine which could answer "is $(M,N)\in L_2$?" in polynomial time?

Motivations

This question came out of a discussion on this question.

Apologies I am really just a math.se member who has gotten lost and wandered on to cs.se. Let me know if my question is clear and up to the standards of this site. I am happy to make corrections.

• Am I using $\leq_P$ correctly? – Mason Jun 18 '18 at 12:42
• Your reduction $L_1\le_p L_2$ is correct, but your conclusion that $L_1$ is "as hard as" $L_2$ is incorrect. You just show that $L_1$ is at most as hard as $L_2$. Specifically, you actually show that $L_1$ is at most as hard as a very restricted case of $L_2$, which might be very easy. – Shaull Jun 18 '18 at 12:47
• Instead of "satisfying a circle", a better term could be "being a sum of two squares". – Yuval Filmus Jun 18 '18 at 12:56
• @Shaull, I changed some language to reflect your comment. – Mason Jun 18 '18 at 16:02
• Computing $\sum_{d\mid n}d$ is in fact known to be as hard as factoring, up to a randomized polynomial time reduction. See Bach, Miller, and Shallit: Sums of divisors, perfect numbers, and factoring. – Emil Jeřábek Jun 19 '18 at 16:16

## 1 Answer

Here's the situation as far as I can tell:

The most efficient way known to test membership in $L_1$ is to factor $r$. No more efficient algorithm seems to be known.

However, there is no obvious reduction to prove $L_2 \le_P L_1$. In other words, if we had a machine to decide $L_1$, there's no easy way to use that to factorize. If we want to factor a number $N$, we can check whether $N \in L_1$, but this only gives us one bit of information about the factors of $N$. Testing multiples of $N$ (i.e., whether $cN \in L_1$ for some integer $c$) doesn't give us any additional information, as knowing whether $N \in L_1$ suffices to predict whether $cN \in L_1$ for all $c>0$. Testing other numbers doesn't seem to help in any obvious way, either. (Testing whether $N' \in L_1$ for some other number $N'$ doesn't seem to give any useful information, if $\gcd(N,N') =1$; and if we had a way to find another number $N'$ such that $\gcd(N,N')\ne 1$, we'd already know how to factor, but of course we don't know how to do that -- so any number we know how to generate is unlikely to give us any useful information on the factors of $N$.) This is not a proof; it is just handwavy intuition.

So it seems plausible that $L_1$ might be easier than $L_2$, and it also seems plausible that they might be of the same difficulty. I'm not aware of any further results on this subject.