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/java-math-library/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/java-math-library/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<=(n-3)/2, and for a given e you can choose k in exactly 2^(n-3-2*e) ways. So you need 4 squares for
2^(n-3)+2^(n-5)+2^(n-7)+... 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 cross-reference in OEIS is a big help.

[QUOTE=Till;557484]In my opinion, any cross-reference 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^(n-1));
} else {
output.remove(2^(n-1) + 2^(n-2));
}
return output;
}
[/CODE]