Lagrange four-squares theorem — deterministic complexity












13












$begingroup$


Lagrange's four-squares theorem states that every natural number can be represented as the sum of four integer squares. Rabin and Shallit gave a randomised algorithm that finds one of these solutions in quadratic time. My question is if anything is known about the deterministic time complexity of finding one of the solutions? Any pointers would be appreciated.



(It seems that enumerating all the solutions is hard as factoring in certain cases (via Jacobi's four-square theorem), but correct me if I am wrong.)










share|cite|improve this question









New contributor




Occams_Trimmer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$








  • 1




    $begingroup$
    Your parenthetical remark is essentially correct. For instance, this is at least as difficult as factoring semiprimes, because it lets us compute $1+p+q+pq$ given a semiprime $pq$, and from $p+q,pq$ it's easy to compute $p,q$.
    $endgroup$
    – Wojowu
    16 hours ago
















13












$begingroup$


Lagrange's four-squares theorem states that every natural number can be represented as the sum of four integer squares. Rabin and Shallit gave a randomised algorithm that finds one of these solutions in quadratic time. My question is if anything is known about the deterministic time complexity of finding one of the solutions? Any pointers would be appreciated.



(It seems that enumerating all the solutions is hard as factoring in certain cases (via Jacobi's four-square theorem), but correct me if I am wrong.)










share|cite|improve this question









New contributor




Occams_Trimmer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$








  • 1




    $begingroup$
    Your parenthetical remark is essentially correct. For instance, this is at least as difficult as factoring semiprimes, because it lets us compute $1+p+q+pq$ given a semiprime $pq$, and from $p+q,pq$ it's easy to compute $p,q$.
    $endgroup$
    – Wojowu
    16 hours ago














13












13








13


4



$begingroup$


Lagrange's four-squares theorem states that every natural number can be represented as the sum of four integer squares. Rabin and Shallit gave a randomised algorithm that finds one of these solutions in quadratic time. My question is if anything is known about the deterministic time complexity of finding one of the solutions? Any pointers would be appreciated.



(It seems that enumerating all the solutions is hard as factoring in certain cases (via Jacobi's four-square theorem), but correct me if I am wrong.)










share|cite|improve this question









New contributor




Occams_Trimmer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$




Lagrange's four-squares theorem states that every natural number can be represented as the sum of four integer squares. Rabin and Shallit gave a randomised algorithm that finds one of these solutions in quadratic time. My question is if anything is known about the deterministic time complexity of finding one of the solutions? Any pointers would be appreciated.



(It seems that enumerating all the solutions is hard as factoring in certain cases (via Jacobi's four-square theorem), but correct me if I am wrong.)







nt.number-theory computational-complexity






share|cite|improve this question









New contributor




Occams_Trimmer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











share|cite|improve this question









New contributor




Occams_Trimmer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|cite|improve this question




share|cite|improve this question








edited 16 hours ago









Tony Huynh

19.8k672131




19.8k672131






New contributor




Occams_Trimmer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









asked 17 hours ago









Occams_TrimmerOccams_Trimmer

1685




1685




New contributor




Occams_Trimmer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





Occams_Trimmer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






Occams_Trimmer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.








  • 1




    $begingroup$
    Your parenthetical remark is essentially correct. For instance, this is at least as difficult as factoring semiprimes, because it lets us compute $1+p+q+pq$ given a semiprime $pq$, and from $p+q,pq$ it's easy to compute $p,q$.
    $endgroup$
    – Wojowu
    16 hours ago














  • 1




    $begingroup$
    Your parenthetical remark is essentially correct. For instance, this is at least as difficult as factoring semiprimes, because it lets us compute $1+p+q+pq$ given a semiprime $pq$, and from $p+q,pq$ it's easy to compute $p,q$.
    $endgroup$
    – Wojowu
    16 hours ago








1




1




$begingroup$
Your parenthetical remark is essentially correct. For instance, this is at least as difficult as factoring semiprimes, because it lets us compute $1+p+q+pq$ given a semiprime $pq$, and from $p+q,pq$ it's easy to compute $p,q$.
$endgroup$
– Wojowu
16 hours ago




$begingroup$
Your parenthetical remark is essentially correct. For instance, this is at least as difficult as factoring semiprimes, because it lets us compute $1+p+q+pq$ given a semiprime $pq$, and from $p+q,pq$ it's easy to compute $p,q$.
$endgroup$
– Wojowu
16 hours ago










1 Answer
1






active

oldest

votes


















13












$begingroup$

As far as I know, this is still an open problem. This is discussed in Section $5$ of the paper Finding the four squares in Lagrange's theorem by Pollack and Treviño. They mention that there is a deterministic algorithm when $n$ is a prime via quaterion multiplication, due to Bumby. Assuming a conjecture of Heath-Brown, there is a deterministic algorithm that works for all $n$. Finally, they mention that a positive proportion of all numbers can be written as the sum of four squares in deterministic polynomial time. Under the Extended Riemann Hypothesis, almost all numbers can be written as the sum of four squares in deterministic polynomial time.






share|cite|improve this answer









$endgroup$














    Your Answer








    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "504"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });






    Occams_Trimmer is a new contributor. Be nice, and check out our Code of Conduct.










    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f328449%2flagrange-four-squares-theorem-deterministic-complexity%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    13












    $begingroup$

    As far as I know, this is still an open problem. This is discussed in Section $5$ of the paper Finding the four squares in Lagrange's theorem by Pollack and Treviño. They mention that there is a deterministic algorithm when $n$ is a prime via quaterion multiplication, due to Bumby. Assuming a conjecture of Heath-Brown, there is a deterministic algorithm that works for all $n$. Finally, they mention that a positive proportion of all numbers can be written as the sum of four squares in deterministic polynomial time. Under the Extended Riemann Hypothesis, almost all numbers can be written as the sum of four squares in deterministic polynomial time.






    share|cite|improve this answer









    $endgroup$


















      13












      $begingroup$

      As far as I know, this is still an open problem. This is discussed in Section $5$ of the paper Finding the four squares in Lagrange's theorem by Pollack and Treviño. They mention that there is a deterministic algorithm when $n$ is a prime via quaterion multiplication, due to Bumby. Assuming a conjecture of Heath-Brown, there is a deterministic algorithm that works for all $n$. Finally, they mention that a positive proportion of all numbers can be written as the sum of four squares in deterministic polynomial time. Under the Extended Riemann Hypothesis, almost all numbers can be written as the sum of four squares in deterministic polynomial time.






      share|cite|improve this answer









      $endgroup$
















        13












        13








        13





        $begingroup$

        As far as I know, this is still an open problem. This is discussed in Section $5$ of the paper Finding the four squares in Lagrange's theorem by Pollack and Treviño. They mention that there is a deterministic algorithm when $n$ is a prime via quaterion multiplication, due to Bumby. Assuming a conjecture of Heath-Brown, there is a deterministic algorithm that works for all $n$. Finally, they mention that a positive proportion of all numbers can be written as the sum of four squares in deterministic polynomial time. Under the Extended Riemann Hypothesis, almost all numbers can be written as the sum of four squares in deterministic polynomial time.






        share|cite|improve this answer









        $endgroup$



        As far as I know, this is still an open problem. This is discussed in Section $5$ of the paper Finding the four squares in Lagrange's theorem by Pollack and Treviño. They mention that there is a deterministic algorithm when $n$ is a prime via quaterion multiplication, due to Bumby. Assuming a conjecture of Heath-Brown, there is a deterministic algorithm that works for all $n$. Finally, they mention that a positive proportion of all numbers can be written as the sum of four squares in deterministic polynomial time. Under the Extended Riemann Hypothesis, almost all numbers can be written as the sum of four squares in deterministic polynomial time.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered 16 hours ago









        Tony HuynhTony Huynh

        19.8k672131




        19.8k672131






















            Occams_Trimmer is a new contributor. Be nice, and check out our Code of Conduct.










            draft saved

            draft discarded


















            Occams_Trimmer is a new contributor. Be nice, and check out our Code of Conduct.













            Occams_Trimmer is a new contributor. Be nice, and check out our Code of Conduct.












            Occams_Trimmer is a new contributor. Be nice, and check out our Code of Conduct.
















            Thanks for contributing an answer to MathOverflow!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f328449%2flagrange-four-squares-theorem-deterministic-complexity%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            數位音樂下載

            When can things happen in Etherscan, such as the picture below?

            格利澤436b