Sum of squares mod n uniformly distributed

Let s be an integer equal to at least 5 and let n be a positive integer.

Look at all tuples of s integers, each integer being between 0 and n-1 inclusive, and look at the sum of their squares mod n. About 1/n will fall into each possible value.

So, for example, if you look at a lists of 6 digits, sum the squares of the digits in each list, then about 1/10 of the results will end in 0, about 1/10 will end in 1, about 1/10 will end in 2, etc.

This is the gist of a theorem discussed on Math Overflow here.

And here is Python code to demonstrate it.

 from itertools import product n = 10 s = 6 counts = [0]*n for p in product(range(n), repeat=s): counts[ sum(x**2 for x in p) % n ] += 1 print(counts)

The result is

 [103200, 99200, 99200, 99200, 99200, 103200, 99200, 99200, 99200, 99200]

and so between 99,200 and 103,200 sums end in each digit.

Let's run it again with n = 11 and s = 5. Now we get

 [14641, 14762, 14520, 14762, 14762, 14762, 14520, 14520, 14520, 14762, 14520]

which shows the counts are between 14,520 and 14,762. If they were perfectly uniformly distributed we'd expect 11⁴ = 14,641 in each bin. The maximum deviation from a uniform distribution is 0.83%.

The code becomes impractical as s or n get larger, but we can try s = 7 and keep n = 11. Then we get a maximum deviation from uniformity of 0.075%, i.e. about 10 times closer to being uniform.

The post Sum of squares mod n uniformly distributed first appeared on John D. Cook.