8
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Am I using $\leq_P$ correctly? $\endgroup$ – Mason Jun 18 '18 at 12:42
  • 1
    $\begingroup$ 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. $\endgroup$ – Shaull Jun 18 '18 at 12:47
  • 1
    $\begingroup$ Instead of "satisfying a circle", a better term could be "being a sum of two squares". $\endgroup$ – Yuval Filmus Jun 18 '18 at 12:56
  • 1
    $\begingroup$ @Shaull, I changed some language to reflect your comment. $\endgroup$ – Mason Jun 18 '18 at 16:02
  • 1
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Jun 19 '18 at 16:16
5
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

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.