Quadratic residue counts related to four squares representation counts

[Till]

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:
https://github.com/TilmanNeumann/jav...f4Squares.java

[Till]

Sorry, I made a little mistake: It is http://oeis.org/A004215, not A004015...

[R. Gerbicz]

Originally Posted by Till

Hi all,
today I found something curious...

Let X(m) be the number of distinct quadratic residues mod m. (A023105 for m=2^n)

It says that there are floor(2^n+10)/6 quadratic residues mod 2^n.

Originally Posted by Till

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:
https://github.com/TilmanNeumann/jav...f4Squares.java

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.

[Till]

Thanks for your analysis. I submitted the conjecture to OEIS.

[R. Gerbicz]

Originally Posted by Till

Thanks for your analysis. I submitted the conjecture to OEIS.

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.

[Till]

Originally Posted by R. Gerbicz

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.

In my opinion, any cross-reference in OEIS is a big help.

[CRGreathouse]

Originally Posted by Till

In my opinion, any cross-reference in OEIS is a big help.

[Dr Sardonicus]

FWIW, the odd 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.

[Till]

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):

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