# Sum of squares function

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Sum_of_squares_function
> Markdown URL: https://mediated.wiki/source/Sum_of_squares_function.md
> Source: https://en.wikipedia.org/wiki/Sum_of_squares_function
> Source revision: 1353924086
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Number-theoretical function}}
In [number theory](/source/number_theory), the '''sum of squares function''' is an [arithmetic function](/source/arithmetic_function) that gives the number of representations for a given positive [integer](/source/integer) ''<math>n</math>'' as the sum of ''<math>k</math>'' [squares](/source/Square_number), where representations that differ only in the order of the [summand](/source/summand)s 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](/source/Function_(mathematics)) 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](/source/cardinality) of a [set](/source/Set_(mathematics)). 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](/source/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](/source/divisor_function) of ''<math>n</math>'' which are [congruent](/source/Modular_arithmetic) to 1 [modulo](/source/Modulo_(mathematics)) 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](/source/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](/source/Table_of_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](/source/Parity_(mathematics)). If one or more <math>h_i</math> are [odd](/source/Parity_(mathematics)), then <math>r_2(n) = 0</math>.

=== ''k'' = 3 ===
{{See also|Legendre's three-square theorem}}
Gauss proved that for a [squarefree number](/source/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](/source/Class_number_(number_theory)) 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](/source/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](/source/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](/source/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](/source/Closed-form_expression) 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](/source/generating_function) of the [sequence](/source/sequence) <math>r_k(n)</math> for fixed {{math|''k''}} can be expressed in terms of the [Jacobi theta function](/source/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](/source/Integer_partition)
*[Jacobi's four-square theorem](/source/Jacobi's_four-square_theorem)
*[Gauss circle problem](/source/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

---
Adapted from the Wikipedia article [Sum of squares function](https://en.wikipedia.org/wiki/Sum_of_squares_function) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Sum_of_squares_function?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.