MathOverflow

Questions tagged [sums-of-squares]

Ask Question

The tag has no usage guidance.

118 questions
Newest
Active
Bountied
Unanswered
Filter by
Sorted by
Tagged with
-2
votes
0answers
113 views

Sum of four squares from sum of $k\geq5$ squares - exact version $\mathsf{II}$

Every natural number is sum of $4$ squares and every natural number bigger than $169$ is sum of five squares. Suppose $n>169$ and $x'x=n$ at a vector $x\in\mathbb Z^5$ then can we find two ...
0
votes
0answers
48 views

Sum of four squares from sum of $k\geq5$ squares - scaled version $\mathsf I$

Every natural number is sum of $4$ squares and every natural number bigger than $169$ is sum of five squares. Suppose $n>169$ and $x'x=n$ at a vector $x\in\mathbb Z^5$ then can we find a matrix $M\...
-2
votes
0answers
55 views

Distribution of gaps between uniform random variables

Pick $k$ uniform independent random integers $x_1,\dots,x_k\in\{0,1,\dots,2^t-2,2^t-1\}$ and denote $y_{\sigma(i)}=x_i$ where $\sigma$ is a permutation in $S_n$ such that $y_1\leq y_2\leq\dots\leq y_{...
-1
votes
0answers
45 views

Probability distribution of sum of squares of sum/difference of uniform random variables

If we pick $k$ uniformly random integers $x_1,\dots,x_k\in\{0,1,\dots,2^t-2,2^t-1\}$ then what is the probability distribution of the quantities $$\sum_{\substack{i,j=1\\i\leq k}}^n(x_i-x_j)^2$$ $$\...
0
votes
1answer
118 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
1answer
141 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
1answer
250 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
0answers
58 views

Why $n$ or $n+1$ has the form $x^4+T_y+T_z$?

For $n\in\mathbb N=\{0,1,2,\ldots\}$ let $T_n$ denote the triangular number $n(n+1)/2$. By an observation of Euler, $$\{T_y+T_z:\ y,z\in\mathbb N\}=\{y^2+z(z+1):\ y,z\in\mathbb N\}.$$ It is well known ...
0
votes
1answer
161 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
1answer
169 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 ...
6
votes
0answers
144 views

Hahn's approach to Hilbert's 17th problem?

The Wikipedia article on Hahn Series mentions that these were studied by Hahn "in his approach to Hilbert's seventeenth problem". Is this correct? If so, what was this approach, and where can I ...
1
vote
0answers
62 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
0answers
111 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
0answers
83 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 ...
6
votes
1answer
175 views

Spherical Bessel functions. Sum of squares

In (1) there is a property of spherical Bessel functions, which's derivation I can not find in the literature. ${\mathsf{j}_{n}^{2}}\left(z\right)+{\mathsf{y}_{n}^{2}}\left(z\right)=\sum_{k=% 0}^{n}\...
4
votes
0answers
451 views

Four-square Conjecture

Lagrange's four-square theorem states that every nonnegative integer can be written as the sum of four squares. My following conjecture is much stronger than this classical theorem. Four-square ...
-2
votes
1answer
331 views

Positive integers written as $\frac{a(a+1)}2+\frac{b(b+1)}2+4^c5^d$

Let $\mathbb N=\{0,1,2,\ldots\}$. Those $T_n:=n(n+1)/2$ with $n\in\mathbb N$ are called triangular numbers. It is well known that $$\{T_a+T_b+T_c:\ a,b,c\in\mathbb N\}=\mathbb N\tag{1}$$ which was ...
1
vote
1answer
90 views

Constrained optimization of sum of squares polynomials

Consider the problem $$ \min p(x) \text{ subject to } g_j(x)\le 0 \quad p,g_j\in\text{SOS}, \qquad (*) $$ i.e. $p,g_j$ ($j=1,\ldots,m$) are sum of squares (SOS) polynomials. Can this problem be ...
2
votes
0answers
38 views

Sums of squares lengths in coordinates rings of plane curves

let $C\subseteq\mathbb{P}^2$ be a plane algebraic curve and let $\mathbb{R}[C]$ be its real coordinate ring. Let $d\geq 1$ and let $p(d)$ be the smallest number such that every sum of squares in $\...
18
votes
1answer
606 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 ...
9
votes
1answer
668 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 ...
0
votes
0answers
80 views

Does positivstellensatz and SOS proof system help here?

I have a system of $m$ homogeneous degree $2$ polynomial equations in $\mathbb Z[x_1,\dots,x_n]$ where $m=poly(n)$. Take $$f_1(x_1,\dots,x_n)=0$$ $$\dots$$ $$f_m(x_1,\dots,x_n)=0$$ to be the system. ...
0
votes
0answers
109 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 ...
3
votes
0answers
158 views

On sums of three squares

Let $\mathbb N=\{0,1,2,\ldots\}$. By the Gauss-Legendre theorem on sums of three squares, any $n\in\mathbb N$ with $n\equiv1,2\pmod4$ can be written as $x^2+y^2+z^2$ with $x,y,z\in\mathbb N$. Clearly, ...
7
votes
0answers
234 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 ...
5
votes
2answers
802 views

Sums of squares of primes [closed]

Question: What is the least number that is a sum of three squares of primes in exactly six ways? ... I know it is not research mathematics. Happy new year! EDIT: Now that it is answered I should ...
2
votes
1answer
160 views

Sieve bound for the sum of two squares

Let $$S(n) = \sum_{p \le n} b(n-p),$$ where $b(a)=1$ is $a$ is a sum of two squares of positive integers and $b(a)=0$ otherwise. Trivially by PNT we have $$S(n) \ll \sum_{p \le n}1 \le \frac{n}{\log n}...
5
votes
0answers
214 views

Can we write each positive integer as $x^2+y^2+\varphi(z^2)$?

As odd squares are congruent to $1$ modulo $8$, any integer of the form $4^k(8m+7)$ with $k,m\in\mathbb N=\{0,1,2,\ldots\}$ cannot be written as the sum of three squares. To avoid such congruence ...
6
votes
0answers
238 views

Legendre's three-square theorem and squared norm of integer matrices

Let $\mathbb{N}$ be the set of non-negative integers. Let $E_n$ be the set of integers which are the sum of $n$ squares. Let $F_n$ be the set of integers of the form $\Vert A \Vert^2$ with $A \in M_n(...
11
votes
2answers
377 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 \...
35
votes
3answers
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 ...
7
votes
1answer
314 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 ...
2
votes
2answers
281 views

Number of ways to write an integer as a sum of squares modulo $k$

Given a natural number $n$ and an element $k \in \mathbb{Z}_n$, how many solutions are there in $\mathbb{Z}_n$ to the equation $x^2+y^2 =k$? That is, I'm wondering whether there is a mod-$n$ version ...
10
votes
1answer
557 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 ...
16
votes
0answers
515 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: ...
3
votes
0answers
47 views

Points of intersection of summand of sums of squares of real polynomials

$\newcommand\R{\mathbb R} \newcommand\Q{\mathbb Q} $I am thinking of something related to Blekhermans 2012 paper Nonnegative Polynomials and Sums of Squares (Journal of the AMS, 25, 2012, 617-635). ...
3
votes
1answer
302 views

An inequality involving sums of squares and sums of cubes

Assume that we have $m$ real numbers $x_1,x_2,...,x_m\in[0,1/4]$ satisfying the following equations: $$ \sum_{i=1}^m x_i=a_1, \sum_{i=1}^mx_i^2=a_2,\sum_{i=1}^mx_i^3\geq a_3,$$ where $a_1,a_2,a_3$ are ...
2
votes
1answer
648 views

Efficient sum of squares decomposition

Sum of 4 squares decomposition is the well-known result. I'm interested only in negative/non-negative separation with focus on efficiency and large numbers. I'm looking for alternatives or extensions ...
15
votes
0answers
512 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: ...
14
votes
0answers
424 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?
1
vote
1answer
69 views

For univariate polynomial is non-negativity on an interval equivalent to having a nonnegative scalar product with non-negative polynomials

Let $\mathbb R_d[t]$ be the set of univariate polynomials in the variable $t$ of degree $d$, and $S$ be the set of elements of $\mathbb R_d[t]$ that are nonnegative on $[0, 1]$. Does the following ...
8
votes
1answer
356 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 \...
5
votes
0answers
165 views

Translation of Hilbert's paper on sums of squares

Does anyone know if there is a French or English translation of Hilbert's paper on sums of squares: Ueber die Darstellung definiter Formen als Summe von Formenquadraten?
2
votes
0answers
126 views

Computing harmonic sum [closed]

I want to show the following equalities for harmonic sum $$\sum_{k=1}^{\infty}\frac{(-1)^k}{k^3}=\lim_{n\to\infty}\int_0^{2n}\frac{-3}{x^4}([x]-2[\frac{x}{2}])dx$$ Any idea?
4
votes
1answer
100 views

Specific quaternary quartic that is positive semi-definite but not sum of squares

Does there exist a quaternary quartic $f$ (a form in $\mathbb{R}[x_1,x_2,x_3,x_4]$ of degree $4$), which is positive semi-definite ($f \geq 0$ on $\mathbb{R}^4$) but not a sum of squares, such that ...
5
votes
1answer
231 views

polynomial maps from reducible plane curves to conics

It is classically known that every smooth plane quartic curve $C$ can be represented by an equation $q_1 q_3 = q_2^2,$ with $q_j\in\mathbb{C}[X,Y,Z]$, $1\leq j\leq 3$ quadratic forms, and the same is ...
4
votes
2answers
322 views

what is this sum of squares of algebraic functions?

This question is inspired by the MO query here, although it has no direct implications. Define the family of polynomial functions $$f_n(x)=n^2x^{n-1}-\frac{d}{dx}\left(\frac{x^n-1}{x-1}\right),$$ and ...
8
votes
3answers
1k 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}...
4
votes
1answer
225 views

Ensuring that a sum of squares is non-zero (in a finite field)

The following problem bears some similarity to the Additive Basis Conjecture [ALM91,JLPT92] saying (in characteristic $3$) that there is an absolute constant $N$ such that for any positive integer $m$,...
8
votes
0answers
484 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 ...

1
2 3