5
$\begingroup$

A classic result on the way to the Lagrange Four Squares theorem — for instance proven by Theorem 87 of Hardy & Wright, as noted by this remark on the Four Squares theorem — is that for odd primes $N$ there are solutions $0 \leqslant x,y < N$ to $$ 1 + x^2 + y^2 \equiv 0 \pmod{N}. $$ It follows that there are solutions for arbitrary composite $N$ odd as well, by the Chinese Remainder Theorem. Other combinatorial results imply that for primes $N \ne 5$, one may require $x,y > 0$; so that in the case of $N$ composite but coprime to $30$ one may require $x$ and $y$ to be coprime to $N$.

Can one construct — deterministically, and in time $O(\mathop{\mathrm{polylog}} N)$ — such a pair $0 < x,y < N$ for arbitrary $N$ coprime to 10 (that is, only having odd prime factors $\ne 5$)? If so, how?

$\endgroup$
2
  • $\begingroup$ Using Dirichlet's theorem on arithmetic progressions, we may try to find a prime $p = n\cdot 4N + (2 N - 1) \equiv 1 \pmod4$ for some $n$. Decomposing $p = x^2 + y^2$ in the integers then gives us a solution for the Hardy-Wright congruence. Linnik's Theorem guarantees an upper bound on the smallest such $p$, but a terrible one: even if the conjectured result $\exists p < (4N)^2$ holds, this is too large for a simple search. $\endgroup$
    – Niel de Beaudrap
    Jul 19, 2013 at 9:36
  • 1
    $\begingroup$ I've discovered that the above remark is essentially the contents of the discussion following Eq. (2.2) of Rabin & Shallit's Randomized algorithms in number theory, who go on to describe a randomised algorithm on that basis which depends on the (as yet unproven) Extended Riemann Hypothesis. Theorem 3.1 of the same paper also presents an efficient randomised algorithm to solve $x^2 + y^2 \equiv k \pmod{N}$ for an arbitrary $N$ odd and unit $k$. My question might then amount to whether these can be derandomised for $k = N-1$ and $\gcd(N,10) = 1$. $\endgroup$
    – Niel de Beaudrap
    Jul 19, 2013 at 14:47

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .