mersenneforum.org Quadratic residue counts related to four squares representation counts
 Register FAQ Search Today's Posts Mark Forums Read

 2020-09-20, 12:23 #1 Till     "Tilman Neumann" Jan 2016 Germany 24×31 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 2020-09-20 at 12:33 Reason: A023105
 2020-09-20, 16:38 #2 Till     "Tilman Neumann" Jan 2016 Germany 24×31 Posts Sorry, I made a little mistake: It is http://oeis.org/A004215, not A004015...
2020-09-20, 16:58   #3
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

25·72 Posts

Quote:
 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.
Quote:
 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.

 2020-09-21, 14:44 #4 Till     "Tilman Neumann" Jan 2016 Germany 24×31 Posts Thanks for your analysis. I submitted the conjecture to OEIS. Last fiddled with by Till on 2020-09-21 at 14:47 Reason: simplified
2020-09-21, 15:41   #5
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

156810 Posts

Quote:
 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.

2020-09-21, 16:27   #6
Till

"Tilman Neumann"
Jan 2016
Germany

24×31 Posts

Quote:
 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.

2020-09-22, 14:21   #7
CRGreathouse

Aug 2006

3×1,993 Posts

Quote:
 Originally Posted by Till In my opinion, any cross-reference in OEIS is a big help.

 2020-09-26, 12:11 #8 Dr Sardonicus     Feb 2017 Nowhere 5,791 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.
 2020-10-11, 18:11 #9 Till     "Tilman Neumann" Jan 2016 Germany 7608 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^(n-1)); } else { output.remove(2^(n-1) + 2^(n-2)); } return output; }

 Similar Threads Thread Thread Starter Forum Replies Last Post Raman Forum Feedback 67 2016-01-07 18:35 Madpoo Data 6 2015-10-11 03:55 fivemack Msieve 4 2012-10-29 11:26 kaffikanne Hardware 10 2009-12-12 23:46 Prime95 Factoring 23 2005-03-22 16:43

All times are UTC. The time now is 16:05.

Fri May 27 16:05:25 UTC 2022 up 43 days, 14:06, 1 user, load averages: 2.01, 1.80, 1.82