Since the set $\{\log(p) \mid p \text{ is prime, } p \le n \}$ for a natural number $n$ is $\mathbb{Q}$-linear independent and since:
$$\log(m) = \sum_{p\mid m} v_p(m) \log(p)$$
we can view each $\log(m)$ as a vector in $\mathbb{Q}$-vector space.
The inner-product is given by:
$$k(a,b) = \sum_{p\mid\gcd(a,b)} v_p(a) v_p(b)$$
The Euclidean distance is given by:
$$d(a,b) = \sqrt{k(a,a)+k(b,b)-2k(a,b)}$$
We can look at the $1$-nearest neighbor graph with vertex set $\{1,\cdots,n\}$ and edges:
$$a \approx b \iff d(a,b)=1$$
which might be written as:
$$ a \approx b \iff \frac{a}{b} \text{ or } \frac{b}{a} \text{ is prime}$$
This graph is connected, since every vertex $v$ has a path to $1$.The number of edges of this graph is equal to $\sum_{k=1}^n \omega(k)$ and this graph is bipartite with partition $A_n = \{k \mid \lambda(k) = +1 \}$ and $B_n = \{k \mid \lambda(k) = -1 \}$ which I think can be proved by induction on $n$ and since $G_n$ is a subgraph of $G_{n+1}$, where $\omega(k)$ counts the prime divisors of $k$ with multiplicity one and $\lambda$ is the Liouville function. This graph is also triangle free, since otherwise if $u \le v \le w$ was a triangle with $v/u = p, w/v = q, w/u = r$ then $w = ur = qv = qup$ so $r=qp$ is a prime and a product of two primes, which is a contradiction.These are properties, which I observed after Sagemath computations. One observation, which might be wrong in general, is that the graph is a partial cube:
https://en.wikipedia.org/wiki/Partial_cube
Is there any reason for this graph to be a partial cube, and if so, what is the labeling of the vertices?
Here is a picture for the graph with $n=12$ vertices:
and labeling produced by Sagemath:
$$\{10: 00000000, 2: 00000001, 1: 00000011, 3: 00000111, 6: 00000101, 12: 00100101, 4: 00100001, 8: 10100001, 9: 01000111, 5: 00000010, 7: 00001011, 11: 00010011\}$$
Is there any "pattern" which describes these labelings?
Edit:
I think it is a partial cube, and the reason is a binary representation of the natural numbers in which it is very easy to multiply and factor numbers but possibly difficult to add two numbers:
Here is some sagemath code.
1 000000000000000000000000000000
2 000000000000000000000000000001
3 000000000000000000000000000010
4 000000000000000000000000000101
5 000000000000000000000000001000
6 000000000000000000000000000011
7 000000000000000000000000010000
8 000000000000000000000000100101
9 000000000000000000000001000010
10 000000000000000000000000001001
11 000000000000000000000010000000
12 000000000000000000000000000111
13 000000000000000000000100000000
14 000000000000000000000000010001
15 000000000000000000000000001010
16 000000000000000000001000100101
17 000000000000000000010000000000
18 000000000000000000000001000011
19 000000000000000000100000000000
20 000000000000000000000000001101
21 000000000000000000000000010010
22 000000000000000000000010000001
23 000000000000000001000000000000
24 000000000000000000000000100111
25 000000000000000010000000001000
26 000000000000000000000100000001
27 000000000000000100000001000010
28 000000000000000000000000010101
29 000000000000001000000000000000
30 000000000000000000000000001011
31 000000000000010000000000000000
32 000000000000100000001000100101
33 000000000000000000000010000010
34 000000000000000000010000000001
35 000000000000000000000000011000
36 000000000000000000000001000111
37 000000000001000000000000000000
38 000000000000000000100000000001
39 000000000000000000000100000010
40 000000000000000000000000101101
41 000000000010000000000000000000
42 000000000000000000000000010011
43 000000000100000000000000000000
44 000000000000000000000010000101
45 000000000000000000000001001010
46 000000000000000001000000000001
47 000000001000000000000000000000
48 000000000000000000001000100111
49 000000010000000000000000010000
The relevant OEIS sequence is this sequence: http://oeis.org/A248906
However I am not so sure how to implement or describe it best in mathematical terms?
It is very exciting that from this binary representation one can see "immediately" the factorization of a number, its divisors and the multiplication of two numbers is also very easy I think. Very cool! 🙂
Best Answer
This graph is contained in a box in a cubic grid graph of dimension $\pi(n)$, the number of primes $p \leq n$. Such a box is a product of paths, and each path is a "partial cube", so their product is a partial cube too.
Explicitly, the box has coordinates indexed by primes $p \leq n$, with the $p$ coordinate ranging from $0$ to $m_p := \left\lfloor \log_p n \right\rfloor$: if $n = \prod_p p^{i_p}$ then the $p$ coordinate of $n$ is $i_p$. A path of length $m$ can be embedded in a cube of dimension $m$ by taking each vertex $v_i$ ($0 \leq i \leq m$) to the bit vector $(b_1,\ldots,b_m)$ with $b_j = 0$ or $b_j = 1$ according as $i < j$ or $i \geq j$. Then the product of these paths in a cube of dimension $\sum_{p \leq n} m_p$ contains your graph.
(For large $n$ the graph can also be accommodated in a cube of considerably smaller dimension, but that takes somewhat more work.)