20200920, 12:23  #1 
"Tilman Neumann"
Jan 2016
Germany
13·37 Posts 
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: https://github.com/TilmanNeumann/jav...f4Squares.java Last fiddled with by Till on 20200920 at 12:33 Reason: A023105 
20200920, 16:38  #2 
"Tilman Neumann"
Jan 2016
Germany
13·37 Posts 
Sorry, I made a little mistake: It is http://oeis.org/A004215, not A004015...

20200920, 16:58  #3  
"Robert Gerbicz"
Oct 2005
Hungary
10111111011_{2} Posts 
Quote:
Quote:
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. 

20200921, 14:44  #4 
"Tilman Neumann"
Jan 2016
Germany
741_{8} Posts 
Thanks for your analysis. I submitted the conjecture to OEIS.
Last fiddled with by Till on 20200921 at 14:47 Reason: simplified 
20200921, 15:41  #5 
"Robert Gerbicz"
Oct 2005
Hungary
1,531 Posts 

20200921, 16:27  #6 
"Tilman Neumann"
Jan 2016
Germany
13×37 Posts 

20200922, 14:21  #7 
Aug 2006
3·1,993 Posts 

20200926, 12:11  #8 
Feb 2017
Nowhere
2×2,677 Posts 
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.

20201011, 18:11  #9 
"Tilman Neumann"
Jan 2016
Germany
13×37 Posts 
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; } 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
post counts  Raman  Forum Feedback  67  20160107 18:35 
Why different shift counts are important  Madpoo  Data  6  20151011 03:55 
I don't understand these relation counts  fivemack  Msieve  4  20121029 11:26 
Dedidicated rig; What counts in Prime Crunching?  kaffikanne  Hardware  10  20091212 23:46 
Curve Counts  Prime95  Factoring  23  20050322 16:43 