The randomness of modular squaring

For each arithmetic function $$f:\mathbb{N}\rightarrow \mathbb{N}$$ and each $$n\in \mathbb{N}$$ you can define a relation $$f_{\textsf{mod } n}:[n]\times[n] \rightarrow \{0,1\}$$ with

$$f_{\textsf{mod } n}(i,j) = 1 \iff f(i) \equiv j \textsf{ mod } n$$

for $$[n] = \{0,1,\dots,n-1\}$$.

Plotting this relation (the "modular graph") shows highly regular patterns for simple functions like addition $$k \mapsto k + c$$ or multiplication $$k \mapsto c \times k$$. To the left the graph with all nodes arranged on a circle, to the right the adjacency matrix. (If you want you can check it all here.)

But the modular graphs for multiplication look more diverse, intricate and somehow more "random" than the graphs for addition. The modular graphs for squaring $$k \mapsto k^2$$ look even more "random" and have no apparent symmetry:

But to my surprise, the modular graphs for higher powers look more regular again:

Note that the modular graphs for the third and the fifth power have at least one symmetry even when $$n$$ is chosen to be a prime number:

My question is two-fold:

1. How do I understand the exceptional status of squaring with respect to the "randomness" of the modular graphs?

2. Are there genuinely different sequences of operations that yield ever more random graphs?

• Just a heads-up: neither the random-matrices tag nor the mirror-symmetry tag were appropriate for this question. Both have specific technical meanings that are not at all related to the substance of your question. While the effort you put in to look for relevant tags is laudable, please try to make sure that the tags you pick are really applicable to your question. – dvitek Sep 27 at 22:18
• @dvitek: Thanks for the hint, I'll consider it. – Hans-Peter Stricker Sep 27 at 22:30

Plotting things on a circle like this focuses attention on dihedral symmetry, which is implemented on the integers $$\bmod n$$ by translation $$t \mapsto t+1$$ and negation $$t \mapsto -t$$. Addition $$t \mapsto t + k$$ is itself a translation, so of course it has translational symmetry (it commutes with translations). Scaling $$t \mapsto kt$$ always at least commutes with negation, and it has a simple behavior with respect to translation: the result of translating and then scaling is

$$t \mapsto k_1(t + k_2) = k_1 t + k_1 k_2$$

and so scaling sends translations to different translations. In the example you plotted where $$k_1 = 30$$ and $$n = 120$$ we see that taking $$k_2 = 4$$ gives $$30(t + 4) = 30t + 120 \equiv 30t \bmod 120$$ which explains some of the regularity of that graph, and $$30(t + 30) = 30t + 900 \equiv 30t + 30 \bmod 120$$ which explains some more of it.

For powers $$t \mapsto t^k$$ we can argue as follows. If $$k$$ is odd then taking powers comutes with negation so we have a reflection symmetry. If $$k = p$$ is a prime dividing the modulus $$n$$ then $$(t + k_2)^p \equiv t + k_2 \bmod p$$ so we have a translation symmetry $$\bmod p$$ which becomes a partial translation symmetry $$\bmod n$$ by the Chinese remainder theorem; in particular it implies a symmetry with respect to the translation $$t + \frac{n}{p}$$ which explains some of the regularity in the graphs for $$p = 3, 5$$.

When $$k = 2$$ we no longer have a reflection symmetry, and the moduli you picked were either odd or divisible by $$4$$, so so we don't have any obvious translation symmetry either. In fact we don't have any translation symmetry at all: if squaring commuted with $$t \mapsto t + k$$ then we must have

$$(t + k)^2 \equiv t^2 + k \bmod n$$

for all $$t$$, which gives $$2kt + (k^2 - k) \equiv 0 \bmod n$$ for all $$t$$. Taking $$t = 0, 1$$ and subtracting gives $$2k \equiv 0 \bmod n$$ and $$k^2 - k \equiv 0 \bmod n$$ which has no nonzero solutions if $$n$$ is odd, and if $$4 \mid n$$ the only nonzero possibility is $$k \equiv \frac{n}{2} \bmod n$$, but then $$\frac{n}{2} - 1$$ is odd and so $$k^2 - k$$ is divisible by one less power of $$2$$ than $$n$$. We only get at best a translation symmetry by $$\frac{n}{2}$$ if $$n \equiv 2 \bmod 4$$.

• Thanks, Qiaochu, for this comprehensive answer. Maybe you want to have a look at my "answer" below. – Hans-Peter Stricker Sep 28 at 8:22

With most such maps you should get some sort of uniform distribution result. For example, J. Beck and I did this for the map x^{-1} mod n. See "On the uniform distribution of inverses modulo n", Periodica Math. Hungarica, Vol 44 (2) 2002, 147-155. (Forgive the self-serving PR, but as one gets older one loses all sense of propriety or modesty! Also this is the age of Trump!) It follows from estimates for Kloostermann sums.

As long you have good estimates for the relevant exponential sum, you should get something interesting.

In reply to your question in the comments it depends what you mean by "randomness". All I am saying that if you look at pictures of the set of points (x/n,(x^{-1} mod n)/n) in the unit square, then, as you let n go to infinity, it fills up the square in an uniform way. However, it is rare to get 3 or more points to lie on a line. This never happens when n is prime. Composite is a different matter. So one can "argue" that the points are distributed uniformly in a "random" way.

In 1963 Renyi and Sulanke published about random polytopes. The paper is frequently cited. It was about the properties of polytopes that are the convex hull of n points where the points are chosen with regard to a uniform distribution function. Something like that. Barany has a 2007 preprint online about this. You may want to look at these articles.

• @MizanKhan: Thanks for the answer. To be honest, I don't quite get it. With "uniform distribution" you mean "randomness"? But uniform distribution of what? Furthermore, I am looking for an answer, why squaring seems to be - in a sense - more "random" than the other basic arithmetic operations. – Hans-Peter Stricker Sep 25 at 15:13
• Maybe you want to have a look at my answer below. – Hans-Peter Stricker Sep 28 at 8:06

This partially answers my second question: negative powers work in a similar way as positive powers.

Following a hint by M. Khan I investigated the sequence of inverses $$i \equiv j^{-k}$$ modulo $$n$$, especially the adjancency matrices with

$$a_{ij}^{(kn)} = 1 \iff i\,j^{\,k} \equiv 1 \textsf{ mod } n \iff i \equiv \,j^{-k} \textsf{ mod } n$$

Even though it may be true that the adjacency matrices for $$i \equiv j^{-1} \textsf{ mod } n$$ ($$i \equiv_n j^{-1}$$ for short) are uniformly distributed in the sqare for $$n \rightarrow \infty$$ (i.e. have almost no structure/symmetries), there is still a lot of structure/symmetries for smaller $$n$$, e.g. for $$n=113$$ or $$n=257$$:

[Compare Fig. 1 on p. 112 here]

For $$i \equiv_n j^{\,-2}$$ – as for $$i \equiv_n j^{\,2}$$ – there is in turn no apparent symmetry to be seen:

But as for $$i \equiv_n j^{\,k}$$, for $$i \equiv_n j^{\,-k}$$, $$k > 2$$ there are more symmetries again (at least for $$k=3$$ and $$k=5$$, and possibly only one – the one along the second diagonal):

The explanation for this may be found in Qiaochu Yuan's answer, but I still haven't tried to.

M. Khan adviced me to have a look at $$i \equiv_n j^{-1}$$ for $$n = 47, 55, 249, 555$$. Here you go:

• Try working with the moduli 47, 88 and 249. When we looked at x^{-1} mod n for these we got images of a butterfly, dragonfly and scholar (or possibly a clown). I would also try n=555. If I remember correctly that also gave a nice picture. When I was playing with such pictures many years I felt I was a "pointillist" (and arguably pointless!) mathematician – M. Khan Sep 28 at 14:37
• @M.Khan: I remember to have been looking for butterflies, dragonflies and scholars in another context. These pictures arose while investigating epicycles. – Hans-Peter Stricker Sep 28 at 15:07
• @M.Khan: I added the butterflies, dragonflies, and scholars to my post. – Hans-Peter Stricker Sep 29 at 10:36