Absolute difference between increasing sum of squares

[JohnnyGui]

TL;DR Summary

Given are non-negative integer squared variables according to $C=x^2+y^2+z^2$. I am trying to deduce the absolute difference between a certain value of $C=x^2+y^2+z^2$ and the very next smallest increase in $C$ possible so I can (dis)prove the following

- Whether small absolute differences occur less frequently at higher values of $C$
- Whether larger absolute differences start appearing at higher values of $C$

Given are non-negative integer variables $x$, $y$ and $z$. I am trying to deduce the absolute difference between a certain value of $C=x^2+y^2+z^2$ and the very next smallest increase in $C$ possible.

I'd like to do this so I can (dis)prove the following:

• Whether small absolute differences occur less frequently at higher values of $C$
• Whether larger absolute differences start appearing at higher values of $C$

Legendre's three-square theorem states that any value coming out of the equation $n=4^a(8b+7)$ (where $a$ and $b$ are independent integers) are values that can not be expressed by $C$. Knowing this, I'd suggest trying to approach this problem by looking how often $\frac{n}{4^a}-7 \mod 8$ resolves to 0 with increasing $n$ and $a$ within a certain $C$ range (since non-zero values means $b$ can not be an integer) and also see how close the corresponding $n$ values are.

However, I'm not sure how to do this and/or whether there is another simpler approach to this problem.

 

[anuttarasammyak]

• Whether small absolute differences occur less frequently at higher values of C
• Whether larger absolute differences start appearing at higher values of

Though I am not sure I got what you mean, $\sqrt{C}$ is distance from Origin (0,0,0) to lattice points (x,y,z) where integers x,y,z>0. I hope this geometry image may help you. For an example sphere shell of radius R and thickness dR centered at Origin contains roughly $\frac{1}{8} 4\pi R^2 dR$ numbers lattice points of positive integers.

 

[FactChecker]

Please describe the problem more fully. Are the values of x, y, z any real number? Are they random variables? Are you talking about a set of random values of C from those random values of x, y, z? It's hard for us to guess what you mean.

 

[hutchphd]

This seems equivalent to earlier posts of yours
https://www.physicsforums.com/threads/accuracy-of-the-density-of-states.987668/
Perhaps you can explain what you don't understand about those answers ?

 

[JohnnyGui]

This seems equivalent to earlier posts of yours
https://www.physicsforums.com/threads/accuracy-of-the-density-of-states.987668/
Perhaps you can explain what you don't understand about those answers ?

How is this equivalent? The linked question is about the accuracy of calculating the number of possible combinations of squared integer values that also give the same fixed value, by using a continuous non-integer n-space volume. This question is about the mathematical behaviour when a sum of squared integer values changes to the next smallest possible integer step.

Please describe the problem more fully. Are the values of x, y, z any real number? Are they random variables? Are you talking about a set of random values of C from those random values of x, y, z? It's hard for us to guess what you mean.

I'm not sure what extra info you are asking for. As stated, x, y and z are any non-negative integer values, thus they are any real positive rational numbers without any decimals. There is no set of $C$. I'm asking how large the next smallest possible step of $C$ is at higher and higher $C$ values. So x, y and z can be any random variable as long as it fulfills this condition. Note that, for example, there are cases in which the next smallest step of $C$ can be achieved by substracting 1 from one or two variables and adding 1 to the remaining variable.

Though I am not sure I got what you mean, $\sqrt{C}$ is distance from Origin (0,0,0) to lattice points (x,y,z) where integers x,y,z>0. I hope this geometry image may help you. For an example sphere shell of radius R and thickness dR centered at Origin contains roughly $\frac{1}{8} 4\pi R^2 dR$ numbers lattice points of positive integers.

Thanks but the question is not about the number of lattice points because this would also include the number of squared integer combinations with the same $C$ value, while I am merely focusing on the smallest integer change of $C$ possible and how large that change would be at higher values of $C$. It's kind of finding the derivative of a formula with 3 integer variables but taking into account what the next smallest possible integer step in $C$ is.

 

[Office_Shredder]

I think the number of points in the shell might be instructive. Every time you increase the radius of the circle by 1, you get something proportional to $R^2$ more points. So we are going to have on the order of $R^2$ points giving values for $C$ between $R^2$and $(R+1)^2$, of which there are only $2R+1$ valid choices of $C$. Obviously the $C$s can only take integer values so you're going to have lots of points that give the same value, but this is pretty suggestive that you do not in general expect large gaps to start showing up, unless there's a reason to think that the number of integer points that maps to the same $C$ grows fast enough.

 

[JohnnyGui]

I think the number of points in the shell might be instructive. Every time you increase the radius of the circle by 1, you get something proportional to $R^2$ more points. So we are going to have on the order of $R^2$ points giving values for $C$ between $R^2$and $(R+1)^2$, of which there are only $2R+1$ valid choices of $C$. Obviously the $C$s can only take integer values so you're going to have lots of points that give the same value, but this is pretty suggestive that you do not in general expect large gaps to start showing up, unless there's a reason to think that the number of integer points that maps to the same $C$ grows fast enough.

So in the case of 3 integer variables (i.e. a sphere) you mean $3R^2-3R+1$ lattice points when increasing $R$ by 1?

Aside from that, the issue here is that the smallest possible integer step of $C$ can sometimes be 3 from what I noticed when graphing the mod function, while increasing the radius of a sphere by 1 would always imply there are more integer points possible.
So I'm not sure to what extent this approach could give an accurate answer to my problem.

 

[FactChecker]

I'm not sure what extra info you are asking for. As stated, x, y and z are any non-negative integer values, thus they are any real positive rational numbers without any decimals.

Sorry. I missed that they were integers.

There is no set of $C$. I'm asking how large the next smallest possible step of $C$ is at higher and higher $C$ values. So x, y and z can be any random variable as long as it fulfills this condition. Note that, for example, there are cases in which the next smallest step of $C$ can be achieved by substracting 1 from one or two variables and adding 1 to the remaining variable.

In your original post, what do you mean by 'frequency"? Do you mean some density per unit volume in (x,y,z)? For any squared integer, say $n^2$, there are a cluster of values giving C=$n^2$, C=$n^2$+1 or C=$n^2$+2, where one of {x,y,z} is $n$ and the other two are in {0,1}. That holds no matter what the size of $n$ is. I don't know how you want to interpret that in terms of "frequency". Beyond that, I will have to leave this for others to answer.

The second question of whether there are larger differences at larger values of C is easier to answer. If C is small, then all of x, y, and z, are small. So there can not be a large change in any of the squared terms caused by a reduction.

 

[hutchphd]

Sorry. I missed that they were integers.

It would have helped if that were part of the original problem statement.

Please @JohnnyGui restate the problem carefully and completely. I will otherwise not waste my time.

 

[JohnnyGui]

It would have helped if that were part of the original problem statement.

Please @JohnnyGui restate the problem carefully and completely. I will otherwise not waste my time.

It was already stated from the very beginning that the problem is about integers. FactChecker is merely apologising about missing that part. Perhaps you reading the OP carefully and completely would help?

In your original post, what do you mean by 'frequency"? Do you mean some density per unit volume in (x,y,z)? For any squared integer, say n2, there are a cluster of values giving C=n2, C=n2+1 or C=n2+2, where one of {x,y,z} is n and the other two are in {0,1}. That holds no matter what the size of n is. I don't know how you want to interpret that in terms of "frequency". Beyond that, I will have to leave this for others to answer.

This helped me a bit, thanks. As for the frequency, is it correct to deduce that at higher $C$ values, more and more combinations of different values of x,y and z are possible between your repeating scenario of "one of {x,y,z} being $n$ and the other two in {0,1}"? I am thinking this because the distance between, say, $C=n^2+0+1^2$ and $C=(n+1)^2+0^2+1^2$ increases as $n$ increases.

 

[anuttarasammyak]

From OP, I have got my interpretation of the problem as follows.

------------------
Let F(n) be a function for non-negative integer n so that
F(n)=1 when there exist integers $0\leq x \leq y \leq z$; $n=x^2+y^2+z^2$
F(n)=0 otherwise.

For first small n
F(0)=F(1)=F(2)=F(3)=F(4)=F(5)=F(6)=1 F(7)=0

Q1 Do we have an algorithm to get value of F(n) for any given n ?

Let us regard F(n) as the numerical sequence
F(0),F(1),F(2),F(3),F(4),F(5),F(6),F(7),F(8),... = 1,1,1,1,1,1,1,1,0,1,...

Q2 Do we have anything to say about distribution of 0,1 according to n in this sequence ?
---------------------

In geometry of #2, sphere shell of radius $\sqrt{7}$ contains no lattice points.

We may need 3D version of Fermat's theorem on sums of two squares ref. https://en.wikipedia.org/wiki/Fermat's_theorem_on_sums_of_two_squares
Taking the third one zero at least we know
For prime number n=1(mod 4), F(n)=1. Oh you already quote Legendre's three-square theorem !
ref. https://en.wikipedia.org/wiki/Legendre's_three-square_theorem

So as for the first question
F(n)=0 when there exists integer 0$\leq$a,b, $n=4^a(8b+7)$ https://oeis.org/A004215/list
F(n)=1 otherwise

As for the second question, in https://oeis.org/A004215/graph I observe F(n)=0 appears with frequency of approximately 1/6. Almost constant frequency continues up to n=60,000.

I hope it will help you to state your problem more clearly.

 

[willem2]

Legendre's three-square theorem states that any value coming out of the equation n=4a(8b+7) (where a and b are independent integers) are values that can not be expressed by C.

Legendre's problem also states that these values $4^a (8b+7)$ are the only values of C that aren't possible.
From this it isn't hard to find that
- the maximum number of consecutive values of C can't be a sum of 3 squares is 2.

- if you choose a random number in the range 1...N, where N is large, the probability that the number can't be a sum of 3 squares is very close to 1/6 = (1/8 + 1/32 + 1/128 +...)

 

[anuttarasammyak]

First 55 numbers that are the sum of 4 but no fewer nonzero squares by increasing order are

n	a(n)	a(n)-a(n-1)
1	7
2	15	8
3	23	8
4	28	5
5	31	3
6	39	8
7	47	8
8	55	8
9	60	5
10	63	3
11	71	8
12	79	8
13	87	8
14	92	5
15	95	3
16	103	8
17	111	8
18	112	1
19	119	7
20	124	5
21	127	3
22	135	8
23	143	8
24	151	8
25	156	5
26	159	3
27	167	8
28	175	8
29	183	8
30	188	5
31	191	3
32	199	8
33	207	8
34	215	8
35	220	5
36	223	3
37	231	8
38	239	8
39	240	1
40	247	7
41	252	5
42	255	3
43	263	8
44	271	8
45	279	8
46	284	5
47	287	3
48	295	8
49	303	8
50	311	8
51	316	5
52	319	3
53	327	8
54	335	8
55	343	8
average		6.22

- the maximum number of consecutive values of C can't be a sum of 3 squares is 2.

- if you choose a random number in the range 1...N, where N is large, the probability that the number can't be a sum of 3 squares is very close to 1/6 = (1/8 + 1/32 + 1/128 +...)

As for the first one, we can say that three consecutive numbers should have two even numbers 0(mod 4) or two odd numbers 7(mod 8) with difference 2. The both are impossible.

I am curious to know how you deduce the second. Your teaching would be highly appreciated.

 

[mfb]

For the possible sums of three squares: https://oeis.org/A000408
Found by plugging in the first few elements of the sequence.

a(n) = 6n/5 + O(n/sqrt(log n)), i.e. we cover 5/6 of the numbers in the limit for n->infinity.

 

[anuttarasammyak]

a(n) = 6n/5 + O(n/sqrt(log n)), i.e. we cover 5/6 of the numbers in the limit for n->infinity.

For completion may I confirm that the contribution of numbers of one square and that of two squares, e.g. 1,2, 4, are relatively small ?

 

[willem2]

I am curious to know how you deduce the second. Your teaching would be highly appreciated.

There are no duplicate values in the set $4^a (8b+7)$.
for any value of a, one in $4^{a-3}$ of the numbers won't be a sum of 3 squares. For a = 0 that's one in 8, for a=1, one in 32 etc.
You only have to know to compute the sum of a geometric series.

Interestingly, the density of numbers that is the sum of 2 squares isn't constant, but is proportional to $$\frac {1} {\sqrt {log(n)}}$$

 

[JohnnyGui]

Thanks for the insightful replies. The first question regarding the frequency (expressed in terms of probability) has been answered. As for the 2nd question:

From this it isn't hard to find that
- the maximum number of consecutive values of C can't be a sum of 3 squares is 2.

As for the first one, we can say that three consecutive numbers should have two even numbers 0(mod 4) or two odd numbers 7(mod 8) with difference 2. The both are impossible.

I may be missing something obvious, but I'm not grasping how the maximum number of consecutive values being 2 can be deduced from this. And why are 0(mod 4) and 7(mod 8) chosen for this conclusion? Shouldn't one be using $\frac{n}{4^a}-7 \mod 8$?

 

[anuttarasammyak]

There are no duplicate values in the set ${4^a (8b+7)$.
for any value of a, one in 4a−3 of the numbers won't be a sum of 3 squares. For a = 0 that's one in 8, for a=1, one in 32 etc.
You only have to know to compute the sum of a geometric series.

Thanks. I would restate in my words
Take a number say N.
Is N a multiple of 4^0 ? Yes with probability 1. Then multiply 1/8 for probability that N is 7(mod 8).
Is N a multiple of 4^1 ? Yes with probability 1/4^1. Then multiply 1/8 for probability that N is 7(mod 8).
Is N a multiple of 4^2 ? Yes with probability 1/4^2. Then multiply 1/8 for probability that N is 7(mod 8).
----
Is N a multiple of 4^n ? Yes with probability 1/4^n. Then multiply 1/8 for probability that N is 7(mod 8).
----

In summation the probability is
$$\frac{1}{8} \sum_{n=0}^\infty (\frac{1}{4})^n=\frac{1}{8} \frac{1}{1-\frac{1}{4}}=\frac{1}{6}$$

But for an example 112, when a=2, b=0, seems to be triple counted in 4^0, 4^1 and 4^2 checks.
Am I wrong ?

 

[anuttarasammyak]

I may be missing something obvious, but I'm not grasping how the maximum number of consecutive values being 2 can be deduced from this. And why are 0(mod 4) and 7(mod 8) chosen for this conclusion? Shouldn't one be using n4a−7mod8?

$$n=4^a(8b+7)$$
odd n: a=0 n=8b+7=7,15,23,31,39,47,... They have interval 8.
even n: n=0(mod 4). Even n's must have interval 4 or 8 or 12,... .
So three or more consecutive sequence of n is impossible.

 

[willem2]

But for an example 112, when a=2, b=0, seems to be triple counted in 4^0, 4^1 and 4^2 checks.
Am I wrong ?

4^a (8b+7) has exactly a factors of 4 (since 8b+7 is odd). So you'll never get out the same number for different values of a. Only a=2 works for 112.

 

[anuttarasammyak]

Thanks. This is to show my understanding on an example of mine 112
112=0(mod 8) No good
112/4=28=4(mod 8) No good
28/4=7=7(mod 8 ) OK
No plural counts.

 

[mfb]

Interestingly, the density of numbers that is the sum of 2 squares isn't constant, but is proportional to $$\frac {1} {\sqrt {log(n)}}$$

1/sqrt(n) for a single square, 1/sqrt(log(n)) for two squares, 5/6 for three squares, and approaching 1 for four (and more) squares. The constant 5/6 is surprising here.

 

[WWGD]

Isn't this the curse of dimensionality?