4
$\begingroup$

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: enter image description here

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! :-)

$\endgroup$
2

3 Answers 3

6
$\begingroup$

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.)

$\endgroup$
5
  • $\begingroup$ thanks for your insight in this question. I do not quite understand the construction of the bit vector. $\endgroup$ Oct 8, 2022 at 17:20
  • $\begingroup$ You're welcome. To see what the bit vector does, look at a small example such as m=4: the path v0,v1,v2,v3,v4 becomes 0000, 1000, 1100, 1110, 1111 in the 4-cube. $\endgroup$ Oct 8, 2022 at 17:37
  • $\begingroup$ By curiosity: do you have more details about the "considerably smaller dimension"? $\endgroup$
    – Wolfgang
    Oct 8, 2022 at 17:52
  • 1
    $\begingroup$ @Wolfgang for starters you can fit long paths into much lower-dimensional cubes. For example, a 4-path already fits in a 3-cube (000, 100, 110, 111, 011). $\endgroup$ Oct 8, 2022 at 18:00
  • 4
    $\begingroup$ As I read the Wikipedia article on partial cubes, the embedding into the cube has to be distance preserving, so the n-path can't fit into any cube smaller than the n-cube. $\endgroup$ Oct 9, 2022 at 1:08
1
$\begingroup$

The limitation to numbers of magnitude at most $n$ obscures the simplicity of the problem. If we take all numbers then and consider for all primes the occurring multiplicity then we get that the graph is exactly $N^{\infty}$.

The question is then expressed as: Can we embed the natural numbers $N$ into $\{0,1\}^{\infty}$? Yes: A number $k\in N$ is mapped to the $\{0,1\}$-vector $1^k 0^{\infty}$ and this respects the distance.

If one restricts to numbers of magnitude $n$ then all this infinite construction collapses to finite vectors. And yes the distances are the same so the graph is a partial cube.

$\endgroup$
1
  • $\begingroup$ Thank you for your answer. The distance which should be respected is $d(a,b) = \Omega(ab/\gcd(a,b)^2)$. In your answer, as I understand it, the distance $D(a,b) = |a-b|$ is respected. But I might be wrong in my interpretation of your answer, so feel free to correct me. $\endgroup$ Oct 14, 2022 at 16:17
1
$\begingroup$

Since the answer already given proposes an embedding but is different from the suggested embedding and I have found a bitstring embedding which seems to work. I wanted to answer for myself for reference this question as follows:

Any shortest path from $a$ to $b$ goes through $\gcd(a,b)$. If $a=v_1,v_2,\cdots,v_r=b$ is a shortest path from $a$ to $b$, then

$$\prod_{i=1}^{r-1} \max\{ \frac{v_i}{v_{i+1}},\frac{v_{i+1}}{v_i}\} = \frac{ab}{\gcd(a,b)^2}$$

and each $\max\{ \frac{v_i}{v_{i+1}},\frac{v_{i+1}}{v_i}\}$ is a prime number. Hence the shortest path distance is given by $d_s(a,b) = \Omega(\frac{ab}{\gcd(a,b)^2})$ where $\Omega$ counts the prime divisors with multiplicity.

The "bitstring" $\beta(a)$ is computed as follows

def getBitVector(n,padto=30):
    ll = []
    for p in prime_divisors(n):
        for k in range(1,valuation(n,p)+1):
            ll.append(p**k)
    ll = sorted(ll)
    pp = prime_powers(1,n+1)
    
    ii = [ pp.index(l)+1  for l in ll]
    if ii==[]:
        mmax = 0
    else:
        mmax = max(ii)
    bb = [1*(j in ii) for j in range(1,mmax+1)]
    bb.reverse()
    nv = sum([2**i*bb[len(bb)-1-i] for i in range(len(bb))])
    dd = Integer(nv).digits(2,padto=padto)
    dd.reverse()
    return dd

In mathematical terms it is expressed as follows: Let $\hat{\pi}(x)$ denote the number of prime powers $p^k\le x$ for $k\ge 1,p$ a prime. Let $a = \prod_{i=1}^r p_i^{a_i}$ with $p_1 \le p_2 \le \cdots \le p_r$. Let $I := \{ \hat{\pi}(p_i^k)| i=1,\cdots,r, k=1,\cdots,a_i\}, M := \max(I)$. Then $\beta(a) = (b_M,b_{M-1},\cdots,b_2,b_1)$ where $b_i = 1$ if $i \in I$, $0$ if $i \notin I$.

Example: $a=8 = 2^3$, $I = \{ \hat{\pi}(2^k)| k=1,2,3 \} = \{\hat{\pi}(8),\hat{\pi}(4),\hat{\pi}(2)\}=\{6,3,1\}$ which means that $\beta(8) = (1,0,0,1,0,1)$.

What needs to be proven is:

  1. $d_H(\beta(a),\beta(b)) =^! d_s(a,b) = \Omega(\frac{ab}{\gcd(a,b)^2})$ where $d_H$ denotes the Hamming distance of the two bitstrings $\beta(a)$ and $\beta(b)$.

  2. $\beta(a) * \beta(b) = \beta( \frac{ab}{\gcd(ab)})$, where $*$ denotes $\text{ bitwise or }$

  3. This follows from 2): If $\gcd(a,b)=1$ then $\beta(a) * \beta(b) = \beta(ab)$

Edit Sketch of proof of 1):

Let $$S_a := \{p^k:1\le k \le v_p(a),p \text{ prime }\}$$

Then

$$S_a \approx S_b :\iff |S_a \Delta S_b| = 1 \iff a/b \text{ or } b/a \text{ is a prime number}$$

(where $\Delta$ denotes the symmetric difference of the two sets: $A \Delta B := (A \cup B)-(A \cap B)$ )

Let $H_n$ be the undirected graph with vertex set $S_1,\cdots,S_n$ and edges defined through $\approx$. Hence we get a bijection of undirected graphs $H_n$ to $G_n$ which is a graph isomorphism and so it follows:

$$d_G(a,b) = d_H(S_a,S_b) = |S_a \Delta S_b| = |\beta(a)-\beta(b)|_1$$

where $d_H(S_a,S_b)$ denotes the length of the shortest path in $H_n$, which was to be proven.

$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.