mersenneforum.org Quadratic residue counts related to four squares representation counts
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2020-09-20, 12:23 #1 Till     "Tilman Neumann" Jan 2016 Germany 42010 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 1101001002 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

1,429 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 22×3×5×7 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

1,429 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

1A416 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

10111010010012 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 23·181 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 22·3·5·7 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; }

 Thread Tools

 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 06:38.

Tue Jan 19 06:38:46 UTC 2021 up 47 days, 2:50, 0 users, load averages: 1.57, 1.85, 1.78

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.