Est-ce que l'écriture d'un nombre en deux carrés et l'écriture des facteurs d'un nombre sont également difficiles?

Soit et les suivants:$L_1$$L_2$

$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} \}$

Revendication$L_1 \leq_P L_2$

Preuve de croquis

Si je veux savoir si .$r\in L_1$

Le nombre de solutions entières à est donné par$x^2+y^2=r$

$g(r)=\sum_{d|r}{\chi{(d)}}$ où$\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 }$

Alors . Alors, pour répondre est " ?" est tout aussi difficile à répondre que "quels sont les diviseurs de ?"$L_1=\{r: g(r)\neq 0\}$$r\in L_1$$r$

$\square$

Ce que j'aimerais savoir, c'est si c'est vrai dans l'autre sens. Est-il vrai que si j'avais une machine qui pourrait me dire en temps constant si je pourrais créer une machine qui pourrait répondre "is ?" en temps polynomial?$r\in L_1$$(M,N)\in L_2$

Les motivations

Cette question est sortie d'une discussion sur cette question .

Excuses Je ne suis vraiment qu'un membre de math.se qui s'est perdu et a erré sur cs.se. Faites-moi savoir si ma question est claire et conforme aux normes de ce site. Je suis heureux de faire des corrections.

Voici la situation pour autant que je sache:

Le moyen le plus efficace connu pour tester l'appartenance à $L_1$ est de factoriser $r$. Aucun algorithme plus efficace ne semble connu.

Cependant, il n'y a pas de réduction évidente à prouver $L_2 \le_P L_1$. En d'autres termes, si nous avions une machine pour décider$L_1$, il n'y a pas de moyen facile de l'utiliser pour factoriser. Si nous voulons factoriser un nombre$N$, nous pouvons vérifier si $N \in L_1$, mais cela ne nous donne qu'un peu d'informations sur les facteurs de $N$. Test de multiples de$N$ (c.-à-d. $cN \in L_1$ pour un entier $c$) ne nous donne aucune information supplémentaire, car savoir si $N \in L_1$ suffit de prédire si $cN \in L_1$ pour tous $c>0$. Tester d'autres nombres ne semble pas non plus aider de manière évidente. (Tester si$N' \in L_1$ pour un autre numéro $N'$ ne semble donner aucune information utile, si $\gcd(N,N') =1$; et si nous avions un moyen de trouver un autre numéro$N'$ tel que $\gcd(N,N')\ne 1$, nous saurions déjà comment factoriser, mais bien sûr nous ne savons pas comment le faire - donc tout nombre que nous savons générer est peu susceptible de nous fournir des informations utiles sur les facteurs de $N$.) Ce n'est pas une preuve; c'est juste une intuition ondulée.

Il semble donc plausible que $L_1$ pourrait être plus facile que $L_2$, et il semble également plausible qu'ils puissent être de la même difficulté. Je n'ai connaissance d'aucun autre résultat à ce sujet.