Questions tagged [sums-of-squares]
The sums-of-squares tag has no usage guidance.
27 questions
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
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,182
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
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
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
1
vote
2
answers
221
views
Sharply Estimating Pythagorean Triples [closed]
Given $m,n\in\Bbb N$ with $m<n$, how many pythagorean triples $p^2+r^2=q^2$ satisfy $$m\leq p<r\leq n?$$
Is there a way to give a sharp estimate?
user76479
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
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
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
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): ...
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
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.6k
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
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
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
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
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,057
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
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
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
6
votes
0
answers
535
views
When is $ \sigma(n!-1) $ a perfect square?
I am looking for pairs of positive integers $(m,n)$ such that $ \sigma(n!-1) =m^2$, where $\sigma$ is the sum of divisors function. Examples occur with $(m,n)=(12,5),(1,2)$.
Question: Are there ...
user99666
2
votes
1
answer
361
views
Question on Sums of Squares
Is it possible for two different $n$-element sets, each of which consists of $n$ unique positive integers (they can appear in both sets, though) to have the same sum when the squares of their elements ...
- 23
1
vote
1
answer
173
views
Small linear relations between primitive Pythagorean triples $\mathsf I$
Say $a^2+b^2=c^2$ is a primitive Pythagorean triple. Then consider the Linear Diophantine Equation
$$ua^2+vb^2+xab+ybc+zca=0$$ where $(u,v,x, y, z)\in\mathbb Z^4$ are variables. If $(u,v,x, y, z)\neq(...
- 1,826
1
vote
1
answer
268
views
Can I prove that a polynomial representing the 4th moment of a weighted-sum of random variables is a sos?
I am looking at the 4th central moment of a weighted-sum of correlated random variables, which takes the form
$$\mu_4 = \sum_{i,j,k,l=1}^n w_i w_j w_k w_l \mu_{ijkl}$$
where $\mu_{ijkl}$ are the ...
- 173
0
votes
0
answers
129
views
Do many homogeneous polynomials help in faster integer root extraction?
Given $n$ homogeneous algebraically independent total degree $2$ polynomials with no $x_1^2,\dots,x_n^2$ variable in $\mathbb Z[x_1,\dots,x_n]$ with promise that it has non-zero integer roots with ...
- 1,826