Quadratic residue counts related to four squares representation counts
Hi all,
today I found something curious... Let X(m) be the number of distinct quadratic residues mod m. (A023105 for m=2^n) Let Y(m) be the number of n < m that can be expressed as a sum of 4 squares, but not by a sum of less than four squares. (A004015) Then it appears that X(2^n) == Y(2^n) + 2 for all n. A simple Java test program can be found here: [URL]https://github.com/TilmanNeumann/javamathlibrary/blob/master/src/de/tilman_neumann/jml/SumOf4Squares.java[/URL] 
Sorry, I made a little mistake: It is [url]http://oeis.org/A004215[/url], not A004015...

[QUOTE=Till;557404]Hi all,
today I found something curious... Let X(m) be the number of distinct quadratic residues mod m. (A023105 for m=2^n) [/QUOTE] It says that there are floor(2^n+10)/6 quadratic residues mod 2^n. [QUOTE=Till;557404] Let Y(m) be the number of n < m that can be expressed as a sum of 4 squares, but not by a sum of less than four squares. (A004015) Then it appears that X(2^n) == Y(2^n) + 2 for all n. A simple Java test program can be found here: [URL]https://github.com/TilmanNeumann/javamathlibrary/blob/master/src/de/tilman_neumann/jml/SumOf4Squares.java[/URL][/QUOTE] You need 4 squares for x iff x=4^e*(8*k+7) it is pretty old fact. If you want the count for this for x<2^n then you can set e<=(n3)/2, and for a given e you can choose k in exactly 2^(n32*e) ways. So you need 4 squares for 2^(n3)+2^(n5)+2^(n7)+... numbers and this is a geometric progression, its sum is roughly 2^n/6. So it looks like your conjecture is true. Note that for any m Y(m) is "close" to m/6. 
Thanks for your analysis. I submitted the conjecture to OEIS.

[QUOTE=Till;557473]Thanks for your analysis. I submitted the conjecture to OEIS.[/QUOTE]
It is a triviality, once you know the sum of a geometric serie, could be known for 2400 years. To make things easier split the proof for odd/even n. 
[QUOTE=R. Gerbicz;557479]It is a triviality, once you know the sum of a geometric serie, could be known for 2400 years. To make things easier split the proof for odd/even n.[/QUOTE]
In my opinion, any crossreference in OEIS is a big help. 
[QUOTE=Till;557484]In my opinion, any crossreference in OEIS is a big help.[/QUOTE]
:bow: 
FWIW, the [i]odd[/i] quadratic residues (mod 2^n) are represented by the numbers congruent to 1 (mod 8) in [1, 2^n). This would appear to allow a counting of all quadratic residues similar to that for sums of four squares.

For completeness I'ld like to add that it's more than counting.
For any n>2, we can obtain the values of A004215 (natural numbers representable by 4 squares but no less) < 2^n from the set of quadratic residues mod 2^n as follows (pseudocode): [CODE] computeA004215Mod2PowN(int n) { Set input = {quadratic residues modulo 2^n}; // the set of quadratic residues modulo 2^n Set output = new Set(); for (qr in input) { output.add(2^n  qr); } output.remove(2^n); if (n is odd) { output.remove(2^(n1)); } else { output.remove(2^(n1) + 2^(n2)); } return output; } [/CODE] 
All times are UTC. The time now is 10:06. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2021, Jelsoft Enterprises Ltd.