Questions tagged [sums-of-squares]
The sums-of-squares tag has no usage guidance.
163 questions
50
votes
6
answers
6k
views
Intuition for the last step in Serre's proof of the three-squares theorem
Serre's A Course in Arithmetic gives essentially the following proof of the three-squares theorem, which says that an integer $a$ is the sum of three squares if and only if it is not of the form $4^m (...
- 118k
47
votes
3
answers
12k
views
Testing whether an integer is the sum of two squares
Is there a fast (probabilistic or deterministic) algorithm for determining whether an integer $n$ is a sum of two squares?
By "fast" here I mean polynomial time (i.e. time $O((\log n)^{O(1)})$). Note ...
- 20.2k
40
votes
2
answers
4k
views
Euler and the Four-Squares Theorem
There are several questions in the Euler-Goldbach correspondence that
I am unable to answer. Sometimes it does not take very much: in his
letter to Goldbach dated June 9th, 1750, Euler conjectured
...
- 32.5k
35
votes
3
answers
2k
views
Lagrange four squares theorem
Lagrange's four square theorem states that every non-negative integer is a sum of squares of four non-negative integers. Suppose $X$ is a subset of non-negative integers with the same property, that ...
- 1,651
31
votes
5
answers
38k
views
Enumerating ways to decompose an integer into the sum of two squares
The well known "Sum of Squares Function" tells you the number of ways you can represent an integer as the sum of two squares. See the link for details, but it is based on counting the factors of the ...
- 415
26
votes
3
answers
2k
views
Sum of squares and divisibility
Consider an integer of the form $$N = 1 + \sum_{i=1}^r d_i^2$$ where $d_i \in \mathbb{N}_{\ge 3}$ and $d_i^2$ divides $N$.
Question: Must $r$ be greater than or equal to $9$?
Checking (with SageMath): ...
26
votes
1
answer
786
views
Distribution of $a^2+\alpha b^2$
It is well known that size of the set of positive integers up to $n$ that can be written as $a^2+b^2$ is asymptotic to $C \frac{n}{\sqrt{\log n}}$. Here I'm interested mostly in the weaker fact that ...
- 1,235
21
votes
1
answer
1k
views
Primes that are sums of two squares with constraints on the squares
It is well known that there are infinitely many primes of the form $a^2+b^2$ (namely all primes congruent to $1$ modulo $4$). On the other hand, Euler raised the problem as to whether there are ...
- 213
19
votes
1
answer
677
views
Is it true that $\{x^4+y^2+z^2:\ x,y,z\in\mathbb Z[i]\}=\{a+2bi:\ a,b\in\mathbb Z\}$?
Recall that the ring of Gaussian integers is
$$\mathbb Z[i]=\{a+bi:\ a,b\in\mathbb Z\}.$$
Clearly
$$(a+bi)^2=a^2-b^2+2abi\ \ \mbox{and}\ \ (a+bi)^4=(a^2-b^2)^2-4a^2b^2+4ab(a^2-b^2)i.$$
Question. Is it ...
- 15.6k
19
votes
1
answer
2k
views
Legendre and sums of three squares
The Three-Squares-Theorem was proved by Gauss in his Disquisitiones, and this proof was studied carefully by various number theorists. Three years before Gauss, Legendre claimed
to have given a proof ...
- 32.5k
19
votes
0
answers
523
views
univariate integer version of Hilbert's 17th problem
Let $f(x)$ be a polynomial of degree $d$ with integer coefficients such that $f(x)\geqslant 0$ for all real $x$. Is it necessarily true that there exists an integer $N(d)$ such that $N(d)\cdot f$ is a ...
- 109k
18
votes
2
answers
3k
views
Many representations as a sum of three squares
Let $r_3(n) = \left|\{(a,b,c)\in {\mathbb Z}^3 :\, a^2+b^2+c^2=n \}\right|$. I am looking for the maximum asymptotic size of $r_3(n)$. That is, the maximum number of representations that a number can ...
- 1,072
18
votes
2
answers
6k
views
Efficient computation of integer representation as a sum of three squares
Recently I've been studying the problem of integer representation as sum of three squares. Most of the articles that I've found study the function $r_m(n)$ which counts the number of representations ...
- 1,625
18
votes
1
answer
871
views
What's the probability that k + n^2 is squarefree, for fixed k?
While playing around with this question (when is the sum of two squares squarefree?), from some experimental computations (and bolstered by the fact that the density of squarefree positive integers is ...
- 14k
18
votes
1
answer
926
views
Lagrange four-squares theorem --- deterministic complexity
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 ...
- 283
16
votes
2
answers
1k
views
Representing $x^3-2$ as a sum of two squares
Prove that there exist infinitely many integers $x$ such that integer $P(x)=x^3-2$ is a sum of two squares of integers.
Ideally, I am looking for a proof method that also applies for other $P(x)$, ...
- 7,172
16
votes
0
answers
588
views
The number 1680 and Lagrange's four-square theorem
The number $1680$ has the factorization $2^4\times3\times5\times7$. Rather to my surprise, I found that this number has certain mysterious connection with Lagrange's four-square theorem.
QUESTION: ...
- 15.6k
15
votes
4
answers
2k
views
Square roots and prime numbers
Definitions:
Here I present a novel conjecture using basic mathematical tools like the sum of the
divisors of an integer $n$ called $\sigma(n)$, the sum of the squares of the positive divisors of n ...
- 127
15
votes
3
answers
2k
views
Polynomials that are sums of squares
Is any algorithm known for determining whether or not a multivariate polynomial with integer coefficients can be written as a sum of squares of such polynomials?
By way of background, if we one ...
- 151
15
votes
1
answer
579
views
Why sum of three squares of real polynomials is a sum of two squares?
If $f(x),g(x)$ are real polynomials, then $f^2+g^2+1$ is a sum of two squares of polynomials. This easily follows from Fundamental Theorem of Algebra, but is there an argument avoiding it? What are ...
- 109k
15
votes
0
answers
631
views
Does every integer $n>1$ have the form $a^2+b^2+3^c+5^d$ with $a,b,c,d$ nonnegative integers?
Lagrange's four-square theorem states that every nonnegative integer is the sum of four squares. I have tried to replace two of the four squares by two powers. This leads to my following question: ...
- 15.6k
14
votes
4
answers
3k
views
Jacobi's theorem on sums of two squares (reference request)
One of Jacobi's theorems states that the number of representations of a positive integer $n$ as a sum of two squares of integers equals
$$4(d_1(n)-d_3(n)),$$
where the function $d_i$ counts the number ...
- 3,062
14
votes
0
answers
481
views
If $ab^2$ is a sum of three squares, then so is $a$. How to see it quickly?
Here $a, b$ are positive integers, and the squares are the squares of integers. This follows from Legendre's three squares theorem, but is there a direct way?
- 109k
13
votes
2
answers
1k
views
Sums of Squares
Every prime $p = 4k + 1$ can be uniquely expressed as sum of two squares, but for which
integers $x$ is $x^2 + y^2 =$ some prime $p$? Stated differently, does the square of
every positive integer ...
- 131
13
votes
1
answer
674
views
Realization of numbers as a sum of three squares via right-angled tetrahedra
De Gua's theorem
is a $3$-dimensional analog of the Pythagorean theorem:
The square of the area of the diagonal face of a right-angled tetrahedron
is the sum of the squares of the areas of the other ...
- 151k
13
votes
1
answer
2k
views
For a proof of the three-square theorem without using Dirichlet's theorem on primes in arithmetic progressions
The three-square theorem states that $n\in\mathbb N=\{0,1,2,\ldots\}$ is the sum of three squares if and only if it is not of the form $4^k(8m+7)$ ($k,m\in\mathbb N$). This was first proved by ...
- 15.6k
12
votes
3
answers
884
views
Symmetric version of Hilbert's seventeenth problem?
Artin's solution to Hilbert's seventeenth problem tells us that a multivariate polynomial $f$ takes only non-negative values over the reals if and only if it is a sum of squares of rational functions.
...
- 82.6k
12
votes
2
answers
499
views
"Pythagoras number" for integral matrices
It is classically known that every positive integer is a sum of at most four squares of integers, i.e. every sum of squares of integers is a sum of four squares of integers. Now consider a symmetric $...
- 3,031
11
votes
2
answers
410
views
Extension of Dickson's theorem on integers of the form $a^2+b^2+2c^2$
Theorems V in this paper of L.E. Dickson states that the following two sets are equal. $$E=\{a^2+b^2+2c^2 \ | \ a,b,c \in \mathbb{Z}\} \ \text{ and } \ F=\mathbb{N} \setminus \{4^k(16n+14) \ | \ k,n \...
11
votes
2
answers
614
views
Jacobi symbols for two-square sums of primes
Given a prime $p\equiv 1\pmod 4$, Fermat's two-squares theorem discovered by Girard
states that there exists two integers $A,B$ such that
$p=A^2+B^2$.
For all primes up to $10^7$ the integers $A$ and $...
- 17.9k
11
votes
1
answer
478
views
Explanation of several unpublished remarks of Gauss on representations of a given number as sums of two, three and four squares
Remark 1: On p.384 of volume 3 of Gauss's Werke, which is a part of an unpublished treatise on the arithmetic geometric mean, Gauss makes the following remark:
On the theory of the division of ...
- 2,099
11
votes
0
answers
363
views
Is there yet an example of a non-negative convex polynomial that cannot be written as a sum-of-squares?
I have read that it remains an open question, whether an example can be constructed of a non-negative convex polynomial that cannot be written as a sum-of-squares. My reading includes the following ...
- 173
11
votes
0
answers
410
views
Sums of squares via semidefinite programming for the complex free group algebra
In the algebra of real noncommutative polynomials (the “free monoid algebra” over the real field) it is possible to reduce the question of whether an element is a sum of hermitian squares and ...
- 7,047
10
votes
4
answers
3k
views
Sum of squares modulo a prime
What is the probability that the sum of squares of n randomly chosen numbers from $Z_p$ is a quadratic residue mod p?
That is, let $a_1$,..$a_n$ be chosen at random. Then how often is $\Sigma_i a^2_i$...
- 101
10
votes
1
answer
1k
views
SOS polynomials with rational coefficients
Suppose we are given a univariate polynomial with rational coefficients, $p \in \Bbb Q [x]$, and are told that $p$ can be expressed as the sum of $k$ squares of polynomials with rational coefficients. ...
- 1,703
10
votes
1
answer
1k
views
Representations by positive definite binary quadratic forms
It's known that the number of representations of an integer $k$ by sum of two squares is
$$
4\;\sum_{d|k}\left(\frac{-4}{d}\right)
$$
or
$$
4\sum_{d|k,\; d \textrm{ odd}} (-1)^{\frac{d-1}{2}}= 4(d_1(k)...
- 2,446
10
votes
1
answer
493
views
Is 100 the only Leyland number that is a square?
Leyland numbers (named for Paul Leyland) are positive integers of the form $x^y + y^x$ , where x and y are naturals > 1, and also the number 3. The OEIS link is https://oeis.org/A076980
I thought ...
- 221
9
votes
2
answers
2k
views
The four-square theorem from the Gauss-Legendre three-square theorem
I've been studying some proofs of the four-square theorem. Some of them are pretty clear. However, I came across a statement that the four-square theorem can be easily derived from Gauss-Legendre ...
- 91
9
votes
1
answer
1k
views
Sums of two squares in arithmetic progressions
Let $r(n)$ denote the number of representations of $n$ as the sum of two squares. Are there any known results on $$\sum _{n\leq x\atop {n\equiv a(q)}}r(n)$$ and in particular is there an asymptotic ...
- 143
9
votes
1
answer
2k
views
Sums of two squares in (certain) integral domains
While giving the first of eight lectures on introductory model theory and its applications yesterday, I stated Hilbert's 17th problem (or rather, Artin's Theorem): if $f \in \mathbb{R}[t_1,\ldots,t_n]$...
- 65.4k
9
votes
3
answers
5k
views
Efficient method to write number as a sum of four squares?
Wikipedia states that there randomized polynomial-time algorithms for writing $n$ as a sum of four squares
$n=x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2}$
in expected running time $\mathrm {O} (\log^{2}...
- 101
9
votes
1
answer
636
views
Representing $x^6-4$ as a sum of two squares
Prove that there exist infinitely many integers $x$ such that integer $P(x)=x^6-4$ is a sum of two squares of integers.
Equivalently, prove that $x^3-2$ and $x^3+2$ are simultaneously sums of two ...
- 7,172
9
votes
1
answer
331
views
Hahn's approach to Hilbert's 17th problem?
The Wikipedia article on Hahn Series mentions mentioned that these were studied by Hahn "in his approach to Hilbert's seventeenth problem".
Is this correct? If so, what was this approach, ...
- 6,406
8
votes
9
answers
5k
views
Ways to prove an inequality
It seems that there are three basic ways to prove an inequality eg $x>0$.
Show that x is a sum of squares.
Use an entropy argument. (Entropy always increases)
Convexity.
Are there other means?
...
user2529
8
votes
2
answers
1k
views
A generalization of partition function to the sums of squares
The well known partition function $p(n)$ is defined as the number of ways to represent $n$ as the sum of natural numbers. An asymptotic formula for $p(n)$ is
$$p(n)\sim\frac{1}{4n\sqrt{3}}\exp\left(\...
user167505
8
votes
2
answers
675
views
The number of solution of $x_1^2 + \cdots + x_k^2 \equiv \lambda \bmod q$
I'm playing with exponential sums...
If $q$ is an odd prime and $a$ an integer such that $q \nmid a$, then the following formula for the Gaussian sum is known
$$\sum_{x=0}^{q-1} e_q(ax^2) = \left(\...
user40023
8
votes
1
answer
611
views
Can a positive polynomial on sphere be represented as the sum of squares of spherical harmonics
Let $p\in {\mathbb{R}}[x_1,\ldots, x_d]$ be a homogenous polynomial degree $2n$. We know that if $p$ is positive on $[-\pi,\pi]^d$, $p$ is sum of squares polynomial, i.e. $p$ can be witten as sum of ...
- 83
8
votes
1
answer
416
views
Every odd integer greater than $1$ is of the form $a+b$ with $a^2+b^2$ being prime
Let $m$ be an odd integer greater than $1$. Is it true that there are positive $a, b$ such that $m=a+b$ and $a^2+b^2$ is a prime number?
It seems that for every odd $m$ there are many $(a,b)\in \...
- 3,866
8
votes
1
answer
2k
views
Lattice points on the boundary of an ellipse
How many points of the integer lattice ${\mathbb Z}^2$ can an axis-parallel ellipse of radius $r$ contain on its boundary? (that is, we consider ${\mathbb Z}^2$ as lying in ${\mathbb R}^2$). ...
- 1,072
7
votes
2
answers
746
views
Would such polynomial identity exist? (related to sum of four squares)
Let $f_1,f_2,f_3,f_4,f_5 \in \mathbb{Q}[x]$ be linear and
coprime and not all constant.
Is it possible $ f_1^2+f_2^2+f_3^2+f_4^2=f_5^2$?
I suppose the answer is negative.
If this is possible, ...
- 25.4k