[math-fun] Number of representations of N as sum of two squares
N=a^2+b^2>0 where a,b are integers (of either sign) #representations = 4*sum(over all divisors d of N) ( [1 if (d mod 4)=1 else 0] - [1 if (d mod 4)=3 else 0] ) I am not sure who first invented this nifty formula (Gauss?). It makes it clear, though, that #representations(N) < #divisors(N) < exp(log(2+o(1))*lnN/lnlnN).
Correction of final line: #representations(N) <= 4*#divisors(N) < exp(log(2+o(1))*lnN/lnlnN) < N^o(1).
From: Warren Smith <warren.wds@gmail.com> To: math-fun@mailman.xmission.com Sent: Saturday, December 17, 2011 9:28 AM Subject: [math-fun] Number of representations of N as sum of two squares
N=a^2+b^2>0 where a,b are integers (of either sign)
#representations = 4*sum(over all divisors d of N) ( [1 if (d mod 4)=1 else 0] - [1 if (d mod 4)=3 else 0] )
I am not sure who first invented this nifty formula (Gauss?). It makes it clear, though, that #representations(N) < #divisors(N) < exp(log(2+o(1))*lnN/lnlnN).
_______________________________________________
Let r[s](n) be the number of representations of n as the sum of s squares. This is counted as the number of distinct s-tuples (x[1], ..., x[s]) such that x[1]^2 + ... + x[s]^2 = n. Then sum(r[s](k), n = 0 ... n) ~ (πn)^(s/2) / (s/2)! . Proof: The sum is the number of integer lattice points in an s-dimensional ball of radius sqrt(n). -- Gene
participants (2)
-
Eugene Salamin -
Warren Smith