{{Short description|Number-theoretical function}} In number theory, the '''sum of squares function''' is an arithmetic function that gives the number of representations for a given positive integer ''<math>n</math>'' as the sum of ''<math>k</math>'' 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 <math>r_k(n)</math>.

== Definition == The function is defined as

:<math>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\}|</math>

where <math>|\,\ |</math> denotes the cardinality of a set. In other words, <math>r_k(n)</math> is the number of ways ''<math>n</math>'' can be written as a sum of ''<math>k</math>'' squares.

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

== Formulae ==

=== ''k'' = 2 === thumb|upright=1.25|Integers satisfying the sum of two squares theorem are squares of possible distances between integer lattice points; values up to 100 are shown, with {| |valign="top"|•||Squares (and thus integer distances) in red |- |valign="top"|•||Non-unique representations (up to rotation and reflection) bolded |} {{main|Sum of two squares theorem#Jacobi's two-square theorem}} The number of ways to write a natural number as sum of two squares is given by <math>r_2(n)</math>. It is given explicitly by

:<math>r_2(n) = 4(d_1(n)-d_3(n))</math>

where <math>d_1(n)</math> is the number of divisors of ''<math>n</math>'' which are congruent to 1 modulo 4 and <math>d_3(n)</math> is the number of divisors of ''<math>n</math>'' which are congruent to 3 modulo 4. Using sums, the expression can be written as:

:<math>r_2(n) = 4\sum_{d \mid n \atop d\,\equiv\,1,3 \pmod 4}(-1)^{(d-1)/2}</math> The prime factorization <math>n = 2^g p_1^{f_1}p_2^{f_2}\cdots q_1^{h_1}q_2^{h_2}\cdots </math>, where <math>p_i</math> are the prime factors of the form <math>p_i \equiv 1\pmod 4,</math> and <math>q_i</math> are the prime factors of the form <math>q_i \equiv 3\pmod 4</math> gives another formula :<math>r_2(n) = 4 (f_1 +1)(f_2+1)\cdots </math>, if ''all'' exponents <math>h_1, h_2, \cdots</math> are even. If one or more <math>h_i</math> are odd, then <math>r_2(n) = 0</math>.

=== ''k'' = 3 === {{See also|Legendre's three-square theorem}} Gauss proved that for a squarefree number <math>n>4</math>, :<math>r_3(n) = \begin{cases} 24 h(-n), & \text{if } n\equiv 3\pmod{8}, \\ 0 & \text{if } n\equiv 7\pmod{8}, \\ 12 h(-4n) & \text{otherwise}, \end{cases}</math> where <math>h(m)</math> denotes the class number of an integer ''<math>m</math>''.

There exist extensions of Gauss' formula to arbitrary integer ''<math>n</math>''.<ref>{{cite journal |author=P. T. Bateman |title=On the Representation of a Number as the Sum of Three Squares |journal=Trans. Amer. Math. Soc. |volume=71 |year=1951 |pages=70–101 |doi=10.1090/S0002-9947-1951-0042438-4 |url=https://www.ams.org/journals/tran/1951-071-01/S0002-9947-1951-0042438-4/S0002-9947-1951-0042438-4.pdf}}</ref><ref>{{cite journal |author1=S. Bhargava |author2= Chandrashekar Adiga | author3 = D. D. Somashekara |title=Three-Square Theorem as an Application of Andrews' Identity |journal=Fibonacci Quart |year=1993 |volume=31 |number=2 |pages=129–133 |doi= 10.1080/00150517.1993.12429300 |url=https://www.fq.math.ca/Scanned/31-2/bhargava.pdf}}</ref>

=== ''k'' = 4 === {{main|Jacobi's four-square theorem}} The number of ways to represent ''<math>n</math>'' 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. :<math>r_4(n)=8\sum_{d\,\mid\,n,\ 4\,\nmid\,d}d.</math>

Representing ''<math>n=2^k m</math>'', where ''<math>m</math>'' is an odd integer, one can express <math>r_4(n)</math> in terms of the divisor function as follows: :<math>r_4(n) = 8\sigma(2^{\min\{k,1\}}m).</math>

=== ''k'' = 6 ===

The number of ways to represent ''<math>n</math>'' as the sum of six squares is given by :<math>r_6(n) = 4\sum_{d\mid n} d^2\big( 4\left(\tfrac{-4}{n/d}\right) - \left(\tfrac{-4}{d}\right)\big),</math> where <math>\left(\tfrac{\cdot}{\cdot}\right)</math> is the Kronecker symbol.<ref name="Cohen2007">{{cite book |last=Cohen |first=H. |author-link=Henri Cohen (number theorist) |title=Number Theory Volume I: Tools and Diophantine Equations |chapter=5.4 Consequences of the Hasse–Minkowski Theorem |year=2007 |publisher=Springer |isbn=978-0-387-49922-2}}</ref>

=== ''k'' = 8 === Jacobi also found an explicit formula for the case ''<math>k=8</math>'':<ref name="Cohen2007"/> :<math>r_8(n) = 16\sum_{d\,\mid\,n}(-1)^{n+d}d^3.</math>

== Generating function == The generating function of the sequence <math>r_k(n)</math> for fixed {{math|''k''}} can be expressed in terms of the Jacobi theta function:<ref>{{cite book |last1=Milne |first1=Stephen C. | title = Infinite Families of Exact Sums of Squares Formulas, Jacobi Elliptic Functions, Continued Fractions, and Schur Functions | publisher = Springer Science & Business Media | chapter=Introduction | year = 2002 | isbn=1402004915 |pages=9}}</ref>

:<math>\vartheta(0;q)^k = \vartheta_3^k(q) = \sum_{n=0}^{\infty}r_k(n)q^n,</math>

where

:<math>\vartheta(0;q) = \sum_{n=-\infty}^{\infty}q^{n^2} = 1 + 2q + 2q^4 + 2q^9 + 2q^{16} + \cdots.</math>

== Numerical values == The first 30 values for <math>r_k(n), \; k=1, \dots, 8</math> are listed in the table below: {| class="wikitable" style="text-align:right;" ! ''n'' !! = !! ''<math>r_1(n)</math>''!! ''<math>r_2(n)</math>''!! ''<math>r_3(n)</math>''!! ''<math>r_4(n)</math>''!! ''<math>r_5(n)</math>''!! ''<math>r_6(n)</math>''!! ''<math>r_7(n)</math>''!! ''<math>r_8(n)</math>'' |- | 0||style='text-align:center;'| 0|| 1|| 1|| 1|| 1|| 1|| 1|| 1|| 1 |- | 1||style='text-align:center;'| 1|| 2|| 4|| 6|| 8|| 10|| 12|| 14|| 16 |-style="background-color:#ddeeff;" | 2||style='text-align:center;'| 2|| 0|| 4|| 12|| 24|| 40|| 60|| 84|| 112 |-style="background-color:#ddeeff;" | 3||style='text-align:center;'| 3|| 0|| 0|| 8|| 32|| 80|| 160|| 280|| 448 |- | 4||style='text-align:center;'| 2<sup>2</sup>|| 2|| 4|| 6|| 24|| 90|| 252|| 574|| 1136 |-style="background-color:#ddeeff;" | 5||style='text-align:center;'| 5|| 0|| 8|| 24|| 48|| 112|| 312|| 840|| 2016 |- | 6||style='text-align:center;'| 2×3|| 0|| 0|| 24|| 96|| 240|| 544|| 1288|| 3136 |-style="background-color:#ddeeff;" | 7||style='text-align:center;'| 7|| 0|| 0|| 0|| 64|| 320|| 960|| 2368|| 5504 |- | 8||style='text-align:center;'| 2<sup>3</sup>|| 0|| 4|| 12|| 24|| 200|| 1020|| 3444|| 9328 |- | 9||style='text-align:center;'| 3<sup>2</sup>|| 2|| 4|| 30|| 104|| 250|| 876|| 3542|| 12112 |- | 10||style='text-align:center;'| 2×5|| 0|| 8|| 24|| 144|| 560|| 1560|| 4424|| 14112 |-style="background-color:#ddeeff;" | 11||style='text-align:center;'| 11|| 0|| 0|| 24|| 96|| 560|| 2400|| 7560|| 21312 |- | 12||style='text-align:center;'| 2<sup>2</sup>×3|| 0|| 0|| 8|| 96|| 400|| 2080|| 9240|| 31808 |-style="background-color:#ddeeff;" | 13||style='text-align:center;'| 13|| 0|| 8|| 24|| 112|| 560|| 2040|| 8456|| 35168 |- | 14||style='text-align:center;'| 2×7|| 0|| 0|| 48|| 192|| 800|| 3264|| 11088|| 38528 |- | 15||style='text-align:center;'| 3×5|| 0|| 0|| 0|| 192|| 960|| 4160|| 16576|| 56448 |- | 16||style='text-align:center;'| 2<sup>4</sup>|| 2|| 4|| 6|| 24|| 730|| 4092|| 18494|| 74864 |-style="background-color:#ddeeff;" | 17||style='text-align:center;'| 17|| 0|| 8|| 48|| 144|| 480|| 3480|| 17808|| 78624 |- | 18||style='text-align:center;'| 2×3<sup>2</sup>|| 0|| 4|| 36|| 312|| 1240|| 4380|| 19740|| 84784 |-style="background-color:#ddeeff;" | 19||style='text-align:center;'| 19|| 0|| 0|| 24|| 160|| 1520|| 7200|| 27720|| 109760 |- | 20||style='text-align:center;'| 2<sup>2</sup>×5|| 0|| 8|| 24|| 144|| 752|| 6552|| 34440|| 143136 |- | 21||style='text-align:center;'| 3×7|| 0|| 0|| 48|| 256|| 1120|| 4608|| 29456|| 154112 |- | 22||style='text-align:center;'| 2×11|| 0|| 0|| 24|| 288|| 1840|| 8160|| 31304|| 149184 |-style="background-color:#ddeeff;" | 23||style='text-align:center;'| 23|| 0|| 0|| 0|| 192|| 1600|| 10560|| 49728|| 194688 |- | 24||style='text-align:center;'| 2<sup>3</sup>×3|| 0|| 0|| 24|| 96|| 1200|| 8224|| 52808|| 261184 |- | 25||style='text-align:center;'| 5<sup>2</sup>|| 2|| 12|| 30|| 248|| 1210|| 7812|| 43414|| 252016 |- | 26||style='text-align:center;'| 2×13|| 0|| 8|| 72|| 336|| 2000|| 10200|| 52248|| 246176 |- | 27||style='text-align:center;'| 3<sup>3</sup>|| 0|| 0|| 32|| 320|| 2240|| 13120|| 68320|| 327040 |- | 28||style='text-align:center;'| 2<sup>2</sup>×7|| 0|| 0|| 0|| 192|| 1600|| 12480|| 74048|| 390784 |-style="background-color:#ddeeff;" | 29||style='text-align:center;'| 29|| 0|| 8|| 72|| 240|| 1680|| 10104|| 68376|| 390240 |- | 30||style='text-align:center;'| 2×3×5|| 0|| 0|| 48|| 576|| 2720|| 14144|| 71120|| 395136 |}

== See also ==

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

== References ==

{{reflist}}

== Further reading == {{Cite book |last=Grosswald |first=Emil |author-link=Emil Grosswald |title=Representations of integers as sums of squares |publisher=Springer-Verlag |year=1985 |isbn=0387961267}}

== External links ==

*{{MathWorld|id=SumofSquaresFunction|title=Sum of Squares Function}} *{{cite OEIS|A122141|number of ways of writing n as a sum of d squares}} *{{cite OEIS|A004018|Theta series of square lattice, r_2(n)}}

Category:Arithmetic functions Category:Squares in number theory Category:Integer factorization algorithms