Questions tagged [sums-of-squares]
The sums-of-squares tag has no usage guidance.
157
questions
11
votes
2
answers
497
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 $...
1
vote
0
answers
128
views
What is the possible reminders modulo 4 of an "odd part" of a polynomial?
Let $f(x)$ be a polynomial with integer coefficients. Let $f(x) = 2^k \cdot m$ where $m$ is odd. The questions are
What are the possible values of $m \mod 4$ (1, 3 or both)? I want the algorithm ...
5
votes
1
answer
449
views
Is there an upper bound on the number of representations as a sum of squares?
I am interested in finding upper bounds for the Sum of squares function defined as $r_k(n) = |\{(a_1, a_2, \ldots, a_k) \in \mathbb{Z}^k \ : \ n = a_1^2 + a_2^2 + \cdots + a_k^2\}|$ whenever the ...
6
votes
1
answer
352
views
A simple way to bound the density of sums of two odd squares
Define
$$S(x) ~=~ \# \left\{ n^2+m^2\leq x : n,m\in\mathbb{N}\right\}$$
Landau (1908) proved that with
$$ B(x) ~=~ K\,\frac{x}{ \sqrt{\log x}} ~~\text{ one has}~~~ \lim \limits_{x\to \infty} \frac{S(...
0
votes
0
answers
35
views
Finding the minimum representation of a positive integer as the sum of three nonzero squares
[n.b. This is a crosspost/nuancing of this MSE post.]
Assume we have a positive integer $n$ which is already known to be the sum of the squares of three nonzero integers — for example,
$$
n = 451 = 19^...
3
votes
0
answers
209
views
Number of partitions of set restricted by sum of square of part size
Let $p_1^{a_1}p_2^{a_2}\cdots$ denotes the integer partition of $n$, i.e. $a_1p_1+a_2p_2+\cdots=n$. Or equivalently $m_1+m_2+\cdots=n$. It is known that the number of partitions of set $\{x_1,x_2,\...
8
votes
1
answer
602
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 ...
12
votes
3
answers
837
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.
...
0
votes
0
answers
82
views
1-degree SOS proof refutes Linear Programming
I am trying to understand Sums-of-Squares proof systems.
A degree $d$ Sums-of-Squares refutation for a set of polynomial equations $P = \{p_1(x) = 0, ..., p_m(x) = 0\}$ is defined as
$\sum_{i=1}^m g_i(...
2
votes
1
answer
135
views
Asymptotic analysis of a peculiar sum of squares sequence
Let $a,b$ be two positive integers. Let the sequence $\{s_n\}_n$ be the set of all possible sums of squares $a^2+b^2$, such that they are in ascending order
\begin{align*}
& n=1 & s_1=1^2+1^2=...
2
votes
1
answer
230
views
Bounds on largest possible square in sum of two squares
Suppose we are given integers $k,c$ such that $k=1+c^2$.
Let $n$ be an odd integer and suppose that $k^n=a_i^2+b_i^2$ for distinct positive integers $a_i<b_i$ and $i\le d$. That is, there are $d$ ...
0
votes
0
answers
184
views
Sum of squares squared in an arithmetic progression
Let $r(n)$ be the number of ways to write $n$ as a sum of two squares and $(a,q)=1$.
What is known about
$$
\sum_{n \le x,n \equiv a (\text{mod} \, q)} r(n)^2 \quad?
$$
I am looking for uniform ...
4
votes
3
answers
388
views
Infinite sum of Laguerre polynomials: is $\sum_{k=0}^{\infty}\frac{n!}{(k+n)!}x^kL_n^k(x)^2=e^x+P(x)$, with $P$ a polynomial of degree $2n-1$?
I have the following expression:
$$
\sum_{k=0}^{\infty}\frac{n!}{(k+n)!}x^k(L_n^k(x))^2,
$$
where
$$
L_n^k(x)=\sum_{j=0}^n(-1)^j\binom{n+k}{n-j}\frac{x^j}{j!}
$$
is the usual associated Laguerre ...
5
votes
0
answers
282
views
On $w^4+x^4+y^2+z^2$ over a number field
In 1921 Siegel confirmed a conjecture of Hilbert by proving that for any number field $K$ each element of
$$K_{\geq0}=\{a\in K:\ \sigma(a)\geq0\ \mbox{for all}\ \sigma\in\mathrm{Gal}(K/\mathbb Q)\}$$ ...
5
votes
1
answer
288
views
How often is the value of a quadratic polynomial equal to a sum of two integer squares?
Let $b:\mathbb N\to \{0,1\}$ be the indicator function of integers that are a sum of two non-zero integer squares. Let $f(t)\in \mathbb Z[t]$ be an irreducible polynomial of degree $2$ with positive ...
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)$, ...
-3
votes
1
answer
2k
views
Bounding sum of square roots in function of the sum value [closed]
Knowing the value of $S=\sum_{k=1}^n s_k$ with $s_k\geq 0$,
is it possible to obtain an upper bound on $\sum_{k=1}^n\sqrt{s_k}$ better than $n \times \sqrt{\max_{1\leq k\leq n} s_k}$ ?
0
votes
1
answer
203
views
The relationship between the symmetric tensor product and sum of squares
I would like to understand deeply the relationship between the symmetric tensor product of order 2 and the sum of squares.
For me, it is clear that the symmetric tensor product or order $d$ is ...
2
votes
2
answers
278
views
Gaps between combinations of squares of integers
Let $\theta$ be a positive irrational number and $S=\{\theta n^2+m^2: n, m\in \mathbb{N}\}$. The elements of $S$ can be written as a sequence of strictly increasing numbers $\{s_n\}$. My question is ...
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): ...
11
votes
1
answer
471
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 ...
6
votes
1
answer
291
views
Representing a symmetric polynomial as a conical sum of squares
This question in inspired by the recent solution to another question.
The following inequality for monomial symmetric polynomials in 4 positive variables $x_1,x_2,x_3,x_4$:
$$m_{(4, 3, 2, 1)} + m_{(4, ...
4
votes
1
answer
137
views
Witt ring of a field with Pythagoras number $2$
I am currently looking at a few simple properties of the Witt ring of a field $K$ (by which I mean the ring of Witt classes of quadratic forms, not the ring of Witt vectors), which are clearly true ...
0
votes
1
answer
133
views
Linear independence of complex polynomials and a "sum of squares" conjecture
This will take me some time to explain. Let $n \geq 2$ be a fixed integer. Let $p_i(z)$, for $i = 1,\ldots,n$ be $n$ nonzero complex polynomials of degree at most $n-1$. I am interested in ...
3
votes
0
answers
147
views
Representation of a power of a quadratic form
Let $A=A^t$ be a non-singular symmetric matrix. For any multi-index $\gamma=(\gamma_1,\dots,\gamma_n)$ of degree $\vert \gamma\vert=\gamma_1+\dots+\gamma_n=2d$, let $b_\gamma=\frac{\partial}{\partial ...
2
votes
0
answers
52
views
Does there always exist a(n uniform) polynomial that makes a positive definite symmetric matrix with polynomial entries into a sum of squares?
Suppose that I have a square and positive definite for every evaluation $x\in\mathbb{R}^{n}$ symmetric matrix $M(x)\in(\mathbb{R}[x])^{s\times s}.$
Does there always exist a polynomial $p(x)\in\...
1
vote
0
answers
65
views
Lower bounds on lengths of sum-of-squares representations of particular polynomials
I am looking for literature on the problem of finding minimal (in the sense of number of terms) sum-of-squares representations of particular non-negative multivariate polynomials with rational ...
1
vote
1
answer
252
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 ...
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(\...
11
votes
0
answers
356
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 ...
18
votes
1
answer
660
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 ...
-1
votes
1
answer
249
views
Questions on $x^2+y^2+z^2$, $x^2+y^2+2z^2$ and $x^2+2y^2+3z^2$
Question 1. My computation in 2018 suggests that a sum of two integer squares is a sum of three nonzero integer squares if and only if it is not of the form
$$4^km\ \ (k=0,1,2,\ldots;\ \ m=1,2,5,10,13,...
19
votes
0
answers
519
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 ...
-1
votes
1
answer
181
views
$7n=x^2+2y^2+4z^2$ with or without $x^2\equiv y^2\equiv z^2\pmod 7$
It is well known that any positive odd integer can be written as $x^2+2y^2+4z^2$ with $x,y,z\in\mathbb Z$.
Question 1. Whether for any odd integer $n>93$ there are $x,y,z\in\mathbb Z$ such that $7n=...
2
votes
1
answer
524
views
$x^2+7y^2=2^n$ and sums of four squares
Lagrange's four square theorem states that each $m\in\mathbb N=\{0,1,2,\ldots\}$ can be written as a sum of four squares.
Recently, I found that the diophantine equation $x^2+7y^2=2^n$ has certain ...
10
votes
1
answer
993
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. ...
0
votes
1
answer
113
views
On a sum of squares representation
We know $p a^2+q b^2+r ab$ can be represented as square (trivially) when $$p,q\geq0$$
$$r^2=|4pq|$$
holds and as a sum of squares (again trivially) of form $(m a+n b)^2$ under readily explainable ...
4
votes
1
answer
309
views
The power of chi-square test
Under the null hypothesis, if we have
$$\sqrt{n} \vec{x} \, \rightarrow_d \, N(0, I_p),$$
the test statistic can be construct as:
$$\hat{\Psi} = n \vec{x}^{\top} \vec{x} \, \rightarrow_d \,\chi^2_p.$$
...
1
vote
0
answers
106
views
Find the integer part of the sum [closed]
Find the integer part of this
sum
Right answer is 200000000010000000000. But i don’t know how to solve it.
1
vote
0
answers
81
views
What is the relation between different generalizations of linear programming?
Linear programming subsumed by each of
Semidefinite programming (SDP)
Convex programming (CXP)
SOS programming (SSP)
Is there any relation between each pair in the three?
Are all three equivalent in ...
3
votes
0
answers
81
views
Sum of squares of polynomials in one variable with missing powers
As we known, a positive polynomial in $\mathbb{R}\left[x\right]$ can be expressed as a sum of squares of polynomials.
The problem is that whether this holds if some powers is missed.
Let $A$ be a ...
0
votes
1
answer
142
views
Matrix whose entries are given by polynomial $A_{ij} = p(\lambda_i, \lambda_j)$; when is it positive semidefinite?
Let $A$ be a matrix whose entries are given by a polynomial,
$$
A_{ij} = p(\lambda_i, \lambda_j)
$$
where $p(\lambda_i,\lambda_j) = p(\lambda_j,\lambda_i)$ is symmetric.
Are there standard methods ...
1
vote
1
answer
168
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(...
3
votes
1
answer
652
views
Efficient computation of $\sum_{i=1}^{\sqrt{n}} i^2\cdot\left\lfloor{\frac n{i^2}}\right\rfloor$
I need to compute efficiently the sum
$$
\sum_{i=1}^{\sqrt{n}} i^2\cdot\left\lfloor{\frac n{i^2}}\right\rfloor.
$$
We can do this in $O({\sqrt{n}})$ but I need a faster algorithm: for example, it ...
0
votes
1
answer
196
views
Write $n^2$ as $x^2+y^2+2\times4^z$ or $x^2+y^2+5\times 4^z$
In March 2018, I formulated the following somewhat curious question.
Question 1. Whether for any integer $n>1$ there is a nonnegative integer $k$ such that $n^2-2\times 4^k$ or $n^2-5\times 4^k$ ...
3
votes
1
answer
375
views
How are natural numbers that cannot be written as a sum of exactly four squares of naturals characterized? [closed]
This is most probably asked here already in some other form (as it seems to be a very basic question) but since I have't found some question very similar to this one I feel obliged to ask (also ...
9
votes
1
answer
322
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, ...
1
vote
0
answers
92
views
Are those two Sum-Of-Squares approach for unconstrained polynomial optimization related?
I found 2 approaches to solve an unconstrained polynomial optimization problem using the Lasserre / SOS hierarchy:
$$
\inf_{x\in\mathbb{R}^n}\quad p(x),
$$
where $p$ is a polynomial of even degree ...
2
votes
0
answers
210
views
Sums of squares in fields
Which fields $k$ have the property that any sum of squares is a square ?
Are there elegant characterizations and/or classifications known for this type of field ?
And what if we replace "fields" by "...
1
vote
0
answers
96
views
Lagrange's four squares theorem in other fields [duplicate]
Is something known about analogues of Lagrange's four squares theorem in number fields other than $\mathbb{Q}$?
I'm more interested in the case of finite extensions of $\mathbb{Q}$.
For example, is ...