mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Analysis & Analytic Number Theory

Reply
 
Thread Tools
Old 2020-09-20, 12:23   #1
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

3·139 Posts
Default 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
Till is offline   Reply With Quote
Old 2020-09-20, 16:38   #2
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

3·139 Posts
Default

Sorry, I made a little mistake: It is http://oeis.org/A004215, not A004015...
Till is offline   Reply With Quote
Old 2020-09-20, 16:58   #3
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

23×3×59 Posts
Default

Quote:
Originally Posted by Till View Post
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 View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2020-09-21, 14:44   #4
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

1101000012 Posts
Default

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

Last fiddled with by Till on 2020-09-21 at 14:47 Reason: simplified
Till is offline   Reply With Quote
Old 2020-09-21, 15:41   #5
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

141610 Posts
Default

Quote:
Originally Posted by Till View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2020-09-21, 16:27   #6
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

3×139 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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.
Till is offline   Reply With Quote
Old 2020-09-22, 14:21   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×2,969 Posts
Default

Quote:
Originally Posted by Till View Post
In my opinion, any cross-reference in OEIS is a big help.
CRGreathouse is online now   Reply With Quote
Old 2020-09-26, 12:11   #8
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3,779 Posts
Default

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.
Dr Sardonicus is offline   Reply With Quote
Old 2020-10-11, 18:11   #9
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

3×139 Posts
Default

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;
}
Till is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
post counts Raman Forum Feedback 67 2016-01-07 18:35
Why different shift counts are important Madpoo Data 6 2015-10-11 03:55
I don't understand these relation counts fivemack Msieve 4 2012-10-29 11:26
Dedidicated rig; What counts in Prime Crunching? kaffikanne Hardware 10 2009-12-12 23:46
Curve Counts Prime95 Factoring 23 2005-03-22 16:43

All times are UTC. The time now is 04:30.

Tue Nov 24 04:30:31 UTC 2020 up 75 days, 1:41, 4 users, load averages: 1.32, 1.63, 2.17

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.