Skip to main content
1 of 5
mathoverflowUser
  • 3.1k
  • 1
  • 9
  • 36

How to define a fractal from the lexicographic sorting on the prime factorization of natural numbers?

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 < n \iff [p_1^{a_1},p_2^{a_2},\cdots,p_r^{a_r}]<[q_1^{b_1},q_2^{b_2},\cdots,q_s^{b_s}]$$

where the right hand side $<$ is the lexicographic sorting of the two lists and for two prime powers this coincides with the usual sorting $p^a < q^b$.

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

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

I used this sorting to visualize the following kernel 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:

prime_factorization_fractal_with_lexicographi_sorting

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.

mathoverflowUser
  • 3.1k
  • 1
  • 9
  • 36