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.