Skip to main content
MathOverflow

Return to Question

replaced link to a footnote by a direct link to the Wikipedia article - which was probably the intended link
Source Link
Martin Sleziak
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40

Lagrange's four-squares theoremLagrange'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.)

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.)

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.)

added the (sums-of-squares) tag
Link
Martin Sleziak
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40
Became Hot Network Question
added 1 character in body
Source Link
Tony Huynh
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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.

(IIt 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.)

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.

(I 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.)

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.)

Source Link
ckamath
ckamath
  • 283
  • 1
  • 5