Sum of squares function

The function is defined as

:$r\_k(n)\; =\; |\backslash \{(a\_1,\; a\_2,\; \backslash ldots,\; a\_k)\; \backslash in\; \backslash mathbb\{Z\}^k\; \backslash \; :\; \backslash \; n\; =\; a\_1^2\; +\; a\_2^2\; +\; \backslash cdots\; +\; a\_k^2\backslash \}|$

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

For example, $r\_2(1)\; =\; 4$ since $1\; =\; 0^2\; +\; (\backslash pm\; 1)^2\; =\; (\backslash pm\; 1)^2\; +\; 0^2$ where each sum has two sign combinations, and also $r\_2(2)\; =\; 4$ since $2\; =\; (\backslash pm\; 1)^2\; +\; (\backslash 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.

[[File:Sum_of_two_squares_theorem.svg|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

{{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₂(n)}}. It is given explicitly by

:$r\_2(n)\; =\; 4(d\_1(n)-d\_3(n))$

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

:$r\_2(n)\; =\; 4\backslash sum\_\{d\; \backslash mid\; n\; \backslash atop\; d\backslash ,\backslash equiv\backslash ,1,3\; \backslash pmod\; 4\}(-1)^\{(d-1)/2\}$

The prime factorization $n\; =\; 2^g\; p\_1^\{f\_1\}p\_2^\{f\_2\}\backslash cdots\; q\_1^\{h\_1\}q\_2^\{h\_2\}\backslash cdots$, where $p\_i$ are the prime factors of the form $p\_i\; \backslash equiv\; 1\backslash pmod\; 4,$ and $q\_i$ are the prime factors of the form $q\_i\; \backslash equiv\; 3\backslash pmod\; 4$ gives another formula

:$r\_2(n)\; =\; 4\; (f\_1\; +1)(f\_2+1)\backslash cdots$, if all exponents $h\_1,\; h\_2,\; \backslash cdots$ are even. If one or more $h\_i$ are odd, then $r\_2(n)\; =\; 0$.

{{See also|Legendre's three-square theorem}}

Gauss proved that for a squarefree number {{math|n > 4}},

:$r\_3(n)\; =\; \backslash 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}

where {{math|h(m)}} denotes the class number of an integer {{math|m}}.

There exist extensions of Gauss' formula to arbitrary integer {{math|n}}.{{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}}{{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}}

{{main|Jacobi's four-square theorem}}

The number of ways to represent {{math|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\backslash sum\_\{d\backslash ,\backslash mid\backslash ,n,\backslash \; 4\backslash ,\backslash nmid\backslash ,d\}d.$

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

:$r\_4(n)\; =\; 8\backslash sigma(2^\{\backslash min\backslash \{k,1\backslash \}\}m).$

The number of ways to represent {{math|n}} as the sum of six squares is given by

:$r\_6(n)\; =\; 4\backslash sum\_\{d\backslash mid\; n\}\; d^2\backslash big(\; 4\backslash left(\backslash tfrac\{-4\}\{n/d\}\backslash right)\; -\; \backslash left(\backslash tfrac\{-4\}\{d\}\backslash right)\backslash big),$

where $\backslash left(\backslash tfrac\{\backslash cdot\}\{\backslash cdot\}\backslash right)$ is the Kronecker symbol.{{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}}

Jacobi also found an explicit formula for the case {{math|1=k = 8}}:

:$r\_8(n)\; =\; 16\backslash sum\_\{d\backslash ,\backslash mid\backslash ,n\}(-1)^\{n+d\}d^3.$

The generating function of the sequence $r\_k(n)$ for fixed {{math|k}} can be expressed in terms of the Jacobi theta function:{{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}}

:$\backslash vartheta(0;q)^k\; =\; \backslash vartheta\_3^k(q)\; =\; \backslash sum\_\{n=0\}^\{\backslash infty\}r\_k(n)q^n,$

where

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

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

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

{{reflist}}

{{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}}

• {{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