Lagrange four-squares theorem — deterministic complexity Planned maintenance scheduled April...
Lagrange four-squares theorem — deterministic complexity
Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern)
Announcing the arrival of Valued Associate #679: Cesar Manara
Unicorn Meta Zoo #1: Why another podcast?Lagrange four-squares theorem: efficient algorithm with units modulo a prime?The Green-Tao theorem and positive binary quadratic formsApplications of finite continued fractionsWhat are the consequences of a polynomial time algorithm for finding out if a given number is expressible as the sum of two squares?A 'generalized Four Squares Theorem'?Polynomial-time complexity and a question and a remark of SerreFinding integer representation as difference of two triangular numbersComplexity of a variant of Four coloring theoremSeeking references for finding primes infinitely oftenLagrange four squares theorem
$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.)
nt.number-theory computational-complexity
edited 19 mins ago
Tony Huynh
19.8k671130
asked 1 hour ago
Occams_TrimmerOccams_Trimmer
1334
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$
add a comment |
$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.)
nt.number-theory computational-complexity
edited 19 mins ago
Tony Huynh
19.8k671130
asked 1 hour ago
Occams_TrimmerOccams_Trimmer
1334
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
1 hour ago
add a comment |
$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.)
nt.number-theory computational-complexity
edited 19 mins ago
Tony Huynh
19.8k671130
asked 1 hour ago
Occams_TrimmerOccams_Trimmer
1334
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
nt.number-theory computational-complexity
edited 19 mins ago
Tony Huynh
19.8k671130
asked 1 hour ago
Occams_TrimmerOccams_Trimmer
1334
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.
edited 19 mins ago
Tony Huynh
19.8k671130
asked 1 hour ago
Occams_TrimmerOccams_Trimmer
1334
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.
edited 19 mins ago
Tony Huynh
19.8k671130
edited 19 mins ago
Tony Huynh
19.8k671130
edited 19 mins ago
Tony Huynh
19.8k671130
19.8k671130
asked 1 hour ago
Occams_TrimmerOccams_Trimmer
1334
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 1 hour ago
Occams_TrimmerOccams_Trimmer
1334
asked 1 hour ago
Occams_TrimmerOccams_Trimmer
1334
1334
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
1 hour ago
add a comment |
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
1 hour 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
1 hour 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
1 hour ago
add a comment |
1 Answer
1
active
oldest
votes
$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.
answered 22 mins ago
Tony HuynhTony Huynh
19.8k671130
$endgroup$
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
$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.
answered 22 mins ago
Tony HuynhTony Huynh
19.8k671130
$endgroup$
add a comment |
$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.
answered 22 mins ago
Tony HuynhTony Huynh
19.8k671130
$endgroup$
add a comment |
$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.
answered 22 mins ago
Tony HuynhTony Huynh
19.8k671130
$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.
answered 22 mins ago
Tony HuynhTony Huynh
19.8k671130
answered 22 mins ago
Tony HuynhTony Huynh
19.8k671130
answered 22 mins ago
Tony HuynhTony Huynh
19.8k671130
answered 22 mins ago
Tony HuynhTony Huynh
19.8k671130
19.8k671130
add a comment |
add a comment |
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.
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
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
1 hour ago