Fractals – How to Define a Fractal from Lexicographic Sorting on Prime Factorization

Question

Consider on the natural number the lexicographic ordering on the prime factorization:
If $m = p_1^{a_1}\cdots p_r^{a_r},n = q_1^{b_1}\cdots q_s^{b_s}$ then we define:

$$m \vartriangleleft n :\iff [(p_1,a_1),(p_2,a_2),\cdots,(p_r,a_r)] \prec [(q_1,b_1),(q_2,b_2),\cdots,(q_s,b_s)]$$

where the right hand side $\prec$ is the lexicographic ordering of the two lists, where $(p,a) \prec (q,b) :\iff p < q \text{ or } ( p=q \text{ and } a < b)$ and the primes in the factorization list are sorted by usual absolute value: $p_i < p_{i+1}$.

Example:

1. For instance for $n=1,\cdots , 10 $ we get the following sorting:

$$1, 2, 6, 10, 4, 8, 3, 9, 5, 7$$

2)

Examples :

sorted by absolute value: $[2, 7, 11, 30, 60, 121]$

lexicographically sorted: $[2, 30, 60, 7, 11, 121]$

[(2, 1)] = [(2, 1)]
[(2, 1)] < [(7, 1)]
[(2, 1)] < [(11, 1)]
[(2, 1)] < [(2, 1), (3, 1), (5, 1)]
[(2, 1)] < [(2, 2), (3, 1), (5, 1)]
[(2, 1)] < [(11, 2)]
[(7, 1)] > [(2, 1)]
[(7, 1)] = [(7, 1)]
[(7, 1)] < [(11, 1)]
[(7, 1)] > [(2, 1), (3, 1), (5, 1)]
[(7, 1)] > [(2, 2), (3, 1), (5, 1)]
[(7, 1)] < [(11, 2)]
[(11, 1)] > [(2, 1)]
[(11, 1)] > [(7, 1)]
[(11, 1)] = [(11, 1)]
[(11, 1)] > [(2, 1), (3, 1), (5, 1)]
[(11, 1)] > [(2, 2), (3, 1), (5, 1)]
[(11, 1)] < [(11, 2)]
[(2, 1), (3, 1), (5, 1)] > [(2, 1)]
[(2, 1), (3, 1), (5, 1)] < [(7, 1)]
[(2, 1), (3, 1), (5, 1)] < [(11, 1)]
[(2, 1), (3, 1), (5, 1)] = [(2, 1), (3, 1), (5, 1)]
[(2, 1), (3, 1), (5, 1)] < [(2, 2), (3, 1), (5, 1)]
[(2, 1), (3, 1), (5, 1)] < [(11, 2)]
[(2, 2), (3, 1), (5, 1)] > [(2, 1)]
[(2, 2), (3, 1), (5, 1)] < [(7, 1)]
[(2, 2), (3, 1), (5, 1)] < [(11, 1)]
[(2, 2), (3, 1), (5, 1)] > [(2, 1), (3, 1), (5, 1)]
[(2, 2), (3, 1), (5, 1)] = [(2, 2), (3, 1), (5, 1)]
[(2, 2), (3, 1), (5, 1)] < [(11, 2)]
[(11, 2)] > [(2, 1)]
[(11, 2)] > [(7, 1)]
[(11, 2)] > [(11, 1)]
[(11, 2)] > [(2, 1), (3, 1), (5, 1)]
[(11, 2)] > [(2, 2), (3, 1), (5, 1)]
[(11, 2)] = [(11, 2)]

I used this sorting to visualize the following Jaccard similarty kernel, where $\Omega$ counts the prime divisors with multiplicity:

$$\frac{\Omega(\gcd(a,b))}{\Omega(\operatorname{lcm}(a,b))}$$

where the entries $n=1,\ldots, N=1400$ of the matrix are sorted by the lexicographic ordering above:

Q: While there seems to be some visual fractal pattern, I am asking myself, how does one quantify / define this fractal pattern?

One idea would be to let $N \rightarrow \infty$ and make the matrix larger, so that one can zoom in but I am not sure how to formalize this idea.

Edit:
Here is another image for the kernel $\omega(\gcd(a,b))$ whose Gram matrix of size $n \times n$ has rank $\pi(n)$, where $\omega$ counts the distinct prime divisors of $n$ and $\pi$ is the prime counting function:

Counting the size of the blocks on the main diagonal, we find the following OEIS sequence:

$$0, 1, 1, 1, 2, 1, 2, 1, 1, 3, 1, 1, 3, 1, 1, 1, 4, 1, 1, 1, 4, 2, 1, 1, 5, 2, 1, 1, 5, 2, 1, 1, 1, 6, 2, 1, 1, 1, 6, 2, 1, 1, 1, 1, 7, 2, 1, 1, 1, 1, 7, 3, 1, 1, 1, 1, 8, 3, 1, 1, 1, 1, 8, 3, 1, 1, 1, 1, 1, 9, 3, 1, 1, 1, 1, 1, 9, 3, 1, 1, 1, 1, 1, 1, 10, 3, 1, 1, 1, 1, 1, 1, 10, 4, 1, 1, 1, 1, 1, 1, 11, 4, 1, 1, 1, 1, 1, 1, 11, 4, 1, 1, 1, 1, 1, 1, 1$$

SageMath-script

Answer 1

I will try to answer my question based on my findings so far:

First, I will slightly change the definition of $\trianglelefteq$ without changing the fractal appereance of the image much:

If $m = p_1 p_2 \cdots p_r$ and $n = q_1 q_2 \cdots q_s$ are the decompositions of $m,n$ in prime factors with repetitions allowed and $p_i \le p_{i+1}$ then we define $m \trianglelefteq n$ as :

$$m \trianglelefteq n :\iff (p_1,\cdots,p_r) \le (q_1,\cdots,q_s)$$

where the right hand side is the lexicographic ordering which coincides with the usual ordering on tuples of length one.

Let us look at the matrix $m_{a,b}$ defined by $m_{a,b} = 1$ if $\gcd(a,b)>1$ and $0$ otherwise, where the numbers $1,\cdots,n$ are sorted by $\trianglelefteq$. Plotting this matrix for some large number, we get the following picture:

To explain the visually perceived self-similarity, let me introduce for each natural number $n$, a factorization tree $T_n$ as follows:

Let $P_1(n) := 1$ if $n=1$ and $\max_{q|n, \text{ }q\text{ prime}} q$ otherwise, denote the largest prime divisor of $n$.

Let us define some rooted trees $T_{n,m}$ for $1 \le m \le n$ by:

1. $T_{n,m}$ has as root the number $m$.
2. If there are primes $p$ such that $P_1(m) \le p \le \frac{n}{m}$, then the children of $m$ are $T_{n,mp}$, otherwise $m$ is a leaf.

We set $T_n := T_{n,1}$.

Here are some examples of these tree:

These trees can also be defined by successively puttting the node $n+1$ into the tree $T_n$ to get the rooted and ordered tree $T_{n+1}$, if one knows the prime factorization of $n+1$. The tree has the following property:

Sorting the nodes by pre-order, we get the same ordering as $\trianglelefteq$.

Furthermore, by this definition, we see that the tree has some self-similar property, which explains some of the visually perceived self-similarity on the image.

Also notice that the blocks on the main diagonal of the blue fractal image have size $a_p(n)$ equal to the sizes of the smaller subtrees in the recursive definition.