Sum of squares function

Last updated September 21, 2024

In number theory, the sum of squares function is an arithmetic function that gives the number of representations for a given positive integer $n$ as the sum of $k$ squares, where representations that differ only in the order of the summands or in the signs of the numbers being squared are counted as different. It is denoted by $r k (n)$ .

Definition

The function is defined as

{\displaystyle r_{k}(n)=|\{(a_{1},a_{2},\ldots ,a_{k})\in \mathbb {Z} ^{k}\

where $|\,\ |$ denotes the cardinality of a set. In other words, $r k (n)$ is the number of ways $n$ can be written as a sum of $k$ squares.

For example, $r_{2}(1)=4$ since $1=0^{2}+(\pm 1)^{2}=(\pm 1)^{2}+0^{2}$ where each sum has two sign combinations, and also $r_{2}(2)=4$ since $2=(\pm 1)^{2}+(\pm 1)^{2}$ with four sign combinations. On the other hand, $r_{2}(3)=0$ because there is no way to represent 3 as a sum of two squares.

Formulae

k = 2

The number of ways to write a natural number as sum of two squares is given by $r 2 (n)$ . It is given explicitly by

r_{2}(n)=4(d_{1}(n)-d_{3}(n))

where $d 1 (n)$ is the number of divisors of $n$ which are congruent to 1 modulo 4 and $d 3 (n)$ is the number of divisors of $n$ which are congruent to 3 modulo 4. Using sums, the expression can be written as:

r_{2}(n)=4\sum _{d\mid n \atop d\,\equiv \,1,3{\pmod {4}}}(-1)^{(d-1)/2}

The prime factorization $n=2^{g}p_{1}^{f_{1}}p_{2}^{f_{2}}\cdots q_{1}^{h_{1}}q_{2}^{h_{2}}\cdots$ , where $p_{i}$ are the prime factors of the form $p_{i}\equiv 1{\pmod {4}},$ and $q_{i}$ are the prime factors of the form $q_{i}\equiv 3{\pmod {4}}$ gives another formula

r_{2}(n)=4(f_{1}+1)(f_{2}+1)\cdots

, if all exponents

h_{1},h_{2},\cdots

are even. If one or more

h_{i}

are odd, then

r_{2}(n)=0

.

k = 3

Gauss proved that for a squarefree number $n > 4$ ,

r_{3}(n)={\begin{cases}24h(-n),&{\text{if }}n\equiv 3{\pmod {8}},\\0&{\text{if }}n\equiv 7{\pmod {8}},\\12h(-4n)&{\text{otherwise}},\end{cases}}

where $h (m)$ denotes the class number of an integer $m$ .

There exist extensions of Gauss' formula to arbitrary integer $n$ .^[1]^[2]

k = 4

The number of ways to represent $n$ as the sum of four squares was due to Carl Gustav Jakob Jacobi and it is eight times the sum of all its divisors which are not divisible by 4, i.e.

r_{4}(n)=8\sum _{d\,\mid \,n,\ 4\,\nmid \,d}d.

Representing $n = 2 k m$ , where m is an odd integer, one can express $r_{4}(n)$ in terms of the divisor function as follows:

r_{4}(n)=8\sigma (2^{\min\{k,1\}}m).

k = 6

The number of ways to represent $n$ as the sum of six squares is given by

r_{6}(n)=4\sum _{d\mid n}d^{2}{\big (}4\left({\tfrac {-4}{n/d}}\right)-\left({\tfrac {-4}{d}}\right){\big )},

where $\left({\tfrac {\cdot }{\cdot }}\right)$ is the Kronecker symbol.^[3]

k = 8

Jacobi also found an explicit formula for the case $k = 8$ :^[3]

r_{8}(n)=16\sum _{d\,\mid \,n}(-1)^{n+d}d^{3}.

Generating function

The generating function of the sequence $r_{k}(n)$ for fixed $k$ can be expressed in terms of the Jacobi theta function:^[4]

\vartheta (0;q)^{k}=\vartheta _{3}^{k}(q)=\sum _{n=0}^{\infty }r_{k}(n)q^{n},

where

\vartheta (0;q)=\sum _{n=-\infty }^{\infty }q^{n^{2}}=1+2q+2q^{4}+2q^{9}+2q^{16}+\cdots .

Numerical values

The first 30 values for $r_{k}(n),\;k=1,\dots ,8$ are listed in the table below:

n	=	r₁(n)	r₂(n)	r₃(n)	r₄(n)	r₅(n)	r₆(n)	r₇(n)	r₈(n)
0	0	1	1	1	1	1	1	1	1
1	1	2	4	6	8	10	12	14	16
2	2	0	4	12	24	40	60	84	112
3	3	0	0	8	32	80	160	280	448
4	2²	2	4	6	24	90	252	574	1136
5	5	0	8	24	48	112	312	840	2016
6	2×3	0	0	24	96	240	544	1288	3136
7	7	0	0	0	64	320	960	2368	5504
8	2³	0	4	12	24	200	1020	3444	9328
9	3²	2	4	30	104	250	876	3542	12112
10	2×5	0	8	24	144	560	1560	4424	14112
11	11	0	0	24	96	560	2400	7560	21312
12	2²×3	0	0	8	96	400	2080	9240	31808
13	13	0	8	24	112	560	2040	8456	35168
14	2×7	0	0	48	192	800	3264	11088	38528
15	3×5	0	0	0	192	960	4160	16576	56448
16	2⁴	2	4	6	24	730	4092	18494	74864
17	17	0	8	48	144	480	3480	17808	78624
18	2×3²	0	4	36	312	1240	4380	19740	84784
19	19	0	0	24	160	1520	7200	27720	109760
20	2²×5	0	8	24	144	752	6552	34440	143136
21	3×7	0	0	48	256	1120	4608	29456	154112
22	2×11	0	0	24	288	1840	8160	31304	149184
23	23	0	0	0	192	1600	10560	49728	194688
24	2³×3	0	0	24	96	1200	8224	52808	261184
25	5²	2	12	30	248	1210	7812	43414	252016
26	2×13	0	8	72	336	2000	10200	52248	246176
27	3³	0	0	32	320	2240	13120	68320	327040
28	2²×7	0	0	0	192	1600	12480	74048	390784
29	29	0	8	72	240	1680	10104	68376	390240
30	2×3×5	0	0	48	576	2720	14144	71120	395136

Related Research Articles

In number theory, an arithmetic, arithmetical, or number-theoretic function is generally any function f(n) whose domain is the positive integers and whose range is a subset of the complex numbers. Hardy & Wright include in their definition the requirement that an arithmetical function "expresses some arithmetical property of n". There is a larger class of number-theoretic functions that do not fit this definition, for example, the prime-counting functions. This article provides links to functions of both classes.

In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.

<span class="mw-page-title-main">Carmichael number</span> Composite number in number theory

In number theory, a Carmichael number is a composite number ⁠ $⁠$ which in modular arithmetic satisfies the congruence relation:

In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers), the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements . It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations.

In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo of an odd prime number p: its value at a (nonzero) quadratic residue mod p is 1 and at a non-quadratic residue (non-residue) is −1. Its value at zero is 0.

The Jacobi symbol is a generalization of the Legendre symbol. Introduced by Jacobi in 1837, it is of theoretical interest in modular arithmetic and other branches of number theory, but its main use is in computational number theory, especially primality testing and integer factorization; these in turn are important in cryptography.

In number theory, Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime. Precisely,

In number theory, a probable prime (PRP) is an integer that satisfies a specific condition that is satisfied by all prime numbers, but which is not satisfied by most composite numbers. Different types of probable primes have different specific conditions. While there may be probable primes that are composite, the condition is generally chosen in order to make such exceptions rare.

In arithmetic, an odd composite integer n is called an Euler pseudoprime to base a, if a and n are coprime, and

In algebra and number theory, Wilson's theorem states that a natural number n > 1 is a prime number if and only if the product of all the positive integers less than n is one less than a multiple of n. That is, the factorial $satisfies$

In number theory, the partition function $p (n)$ represents the number of possible partitions of a non-negative integer $n$ . For instance, $p (4) = 5$ because the integer 4 has the five partitions $1 + 1 + 1 + 1$ , $1 + 1 + 2$ , $1 + 3$ , $2 + 2$ , and $4$ .

A hexagonal number is a figurate number. The nth hexagonal number h_n is the number of distinct dots in a pattern of dots consisting of the outlines of regular hexagons with sides up to n dots, when the hexagons are overlaid so that they share one vertex.

In number theory, quadratic Gauss sums are certain finite sums of roots of unity. A quadratic Gauss sum can be interpreted as a linear combination of the values of the complex exponential function with coefficients given by a quadratic character; for a general character, one obtains a more general Gauss sum. These objects are named after Carl Friedrich Gauss, who studied them extensively and applied them to quadratic, cubic, and biquadratic reciprocity laws.

In number theory, the Kronecker symbol, written as $or, is a generalization of the Jacobi symbol to all integers . It was introduced by Leopold Kronecker.$

Lucas pseudoprimes and Fibonacci pseudoprimes are composite integers that pass certain tests which all primes and very few composite numbers pass: in this case, criteria relative to some Lucas sequence.

<span class="mw-page-title-main">Carmichael function</span> Function in mathematical number theory

In number theory, a branch of mathematics, the Carmichael function $λ (n)$ of a positive integer $n$ is the smallest member of the set of positive integers $m$ having the property that

In mathematics, Hensel's lemma, also known as Hensel's lifting lemma, named after Kurt Hensel, is a result in modular arithmetic, stating that if a univariate polynomial has a simple root modulo a prime number $p$ , then this root can be lifted to a unique root modulo any higher power of $p$ . More generally, if a polynomial factors modulo $p$ into two coprime polynomials, this factorization can be lifted to a factorization modulo any higher power of $p$ .

In additive number theory, Fermat's theorem on sums of two squares states that an odd prime p can be expressed as:

Anatoly Alexeyevich Karatsuba was a Russian mathematician working in the field of analytic number theory, p-adic numbers and Dirichlet series.

In number theory, the Fermat quotient of an integer a with respect to an odd prime p is defined as

References

↑ P. T. Bateman (1951). "On the Representation of a Number as the Sum of Three Squares" (PDF). Trans. Amer. Math. Soc. 71: 70–101. doi:10.1090/S0002-9947-1951-0042438-4.
↑ S. Bhargava; Chandrashekar Adiga; D. D. Somashekara (1993). "Three-Square Theorem as an Application of Andrews' Identity" (PDF). Fibonacci Quart. 31 (2): 129–133.
1 2 Cohen, H. (2007). "5.4 Consequences of the Hasse–Minkowski Theorem". Number Theory Volume I: Tools and Diophantine Equations. Springer. ISBN 978-0-387-49922-2.
↑ Milne, Stephen C. (2002). "Introduction". Infinite Families of Exact Sums of Squares Formulas, Jacobi Elliptic Functions, Continued Fractions, and Schur Functions. Springer Science & Business Media. p. 9. ISBN 1402004915.

External links

Weisstein, Eric W. "Sum of Squares Function". MathWorld .
Sloane, N. J. A. (ed.). "SequenceA122141(number of ways of writing n as a sum of d squares)". The On-Line Encyclopedia of Integer Sequences . OEIS Foundation.
Sloane, N. J. A. (ed.). "SequenceA004018(Theta series of square lattice, r_2(n))". The On-Line Encyclopedia of Integer Sequences . OEIS Foundation.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] P. T. Bateman (1951). "On the Representation of a Number as the Sum of Three Squares" (PDF). Trans. Amer. Math. Soc. 71: 70–101. doi:10.1090/S0002-9947-1951-0042438-4.

[2] S. Bhargava; Chandrashekar Adiga; D. D. Somashekara (1993). "Three-Square Theorem as an Application of Andrews' Identity" (PDF). Fibonacci Quart. 31 (2): 129–133.

[Cohen2007-3] 1 2 Cohen, H. (2007). "5.4 Consequences of the Hasse–Minkowski Theorem". Number Theory Volume I: Tools and Diophantine Equations. Springer. ISBN 978-0-387-49922-2.

[4] Milne, Stephen C. (2002). "Introduction". Infinite Families of Exact Sums of Squares Formulas, Jacobi Elliptic Functions, Continued Fractions, and Schur Functions. Springer Science & Business Media. p. 9. ISBN 1402004915.

[1]

[2]

[3]

[4]