Sum of squares function

From Wikipedia, the free encyclopedia

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).

The function is defined as

${\displaystyle 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}\}|}${\displaystyle 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}\}|}

where ${\displaystyle |,円\ |}${\displaystyle |,円\ |} 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, ${\displaystyle r_{2}(1)=4}${\displaystyle r_{2}(1)=4} since ${\displaystyle 1=0^{2}+(\pm 1)^{2}=(\pm 1)^{2}+0^{2}}${\displaystyle 1=0^{2}+(\pm 1)^{2}=(\pm 1)^{2}+0^{2}} where each sum has two sign combinations, and also ${\displaystyle r_{2}(2)=4}${\displaystyle r_{2}(2)=4} since ${\displaystyle 2=(\pm 1)^{2}+(\pm 1)^{2}}${\displaystyle 2=(\pm 1)^{2}+(\pm 1)^{2}} with four sign combinations. On the other hand, ${\displaystyle r_{2}(3)=0}${\displaystyle r_{2}(3)=0} because there is no way to represent 3 as a sum of two squares.

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

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

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

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

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

${\displaystyle r_{2}(n)=4(f_{1}+1)(f_{2}+1)\cdots }${\displaystyle r_{2}(n)=4(f_{1}+1)(f_{2}+1)\cdots }, if all exponents ${\displaystyle h_{1},h_{2},\cdots }${\displaystyle h_{1},h_{2},\cdots } are even. If one or more ${\displaystyle h_{i}}${\displaystyle h_{i}} are odd, then ${\displaystyle r_{2}(n)=0}${\displaystyle r_{2}(n)=0}.

Gauss proved that for a squarefree number n > 4,

${\displaystyle r_{3}(n)={\begin{cases}24h(-n),&{\text{if }}n\equiv 3{\pmod {8}},\0円&{\text{if }}n\equiv 7{\pmod {8}},\12円h(-4n)&{\text{otherwise}},\end{cases}}}${\displaystyle r_{3}(n)={\begin{cases}24h(-n),&{\text{if }}n\equiv 3{\pmod {8}},\0円&{\text{if }}n\equiv 7{\pmod {8}},\12円h(-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]}

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.

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

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

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

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

${\displaystyle r_{6}(n)=4\sum _{d\mid n}d^{2}{\big (}4\left({\tfrac {-4}{n/d}}\right)-\left({\tfrac {-4}{d}}\right){\big )},}${\displaystyle 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 ${\displaystyle \left({\tfrac {\cdot }{\cdot }}\right)}${\displaystyle \left({\tfrac {\cdot }{\cdot }}\right)} is the Kronecker symbol.^[3]

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

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

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

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

where

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

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

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

• Integer partition
• Jacobi's four-square theorem
• Gauss circle problem

Grosswald, Emil (1985). Representations of integers as sums of squares. Springer-Verlag. ISBN 0387961267.

• Weisstein, Eric W. "Sum of Squares Function". MathWorld .
• Sloane, N. J. A. (ed.). "Sequence A122141 (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.). "Sequence A004018 (Theta series of square lattice, r_2(n))". The On-Line Encyclopedia of Integer Sequences . OEIS Foundation.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Sum_of_squares_function&oldid=1278841586"

Categories:

• Arithmetic functions
• Squares in number theory
• Integer factorization algorithms

Hidden categories:

• Articles with short description
• Short description is different from Wikidata