28
$\begingroup$

Let $d(a,b) = 1 - \frac{2\gcd(a,b)^3}{ab(a+b)}$ be a metric on natural numbers without $0$.

The metric space $X = \{x_0,x_1,\cdots,x_n\},n>2$ is isometric embeddable in $\mathbb{R}^n$ if and only if the matrix: $$M(x_0,x_1,\cdots,x_n) = (1/2 (d(x_0,x_i)^2+d(x_0,x_j)^2-d(x_i,x_j)^2))_{1 \le i,j \le n}$$ is positive semidefinite.

So my question is:

Is the matrix above for $d$ as above positive semidefinite for all choices of $x_i \in \mathbb{N}$? (Maybe it is possible to prove this using quadratic forms and then transform it to $\sum_{i} a_{ii} y_i^2$ showing then that $a_{ii}\ge 0$?

If it is so, then this would one allow to do euclidean geometry of natural numbers. For instance for three (pairwise distinct) points / natural numbers we would have:

1) a triangle

2) law of sines

3) law of cosines

4) All other theorems concerning triangles

Then in the limit three consecutive numbers / primes would build an equilateral triangle of side length $1$. Hence one could imagine primes ("in the limit") as an infinite dimensional simplex, which would be a funny thing to think about.

Thanks for your help.

Related question: https://math.stackexchange.com/questions/3385102/is-this-metric-matrix-positive-semidefinite

See Theorem 2.4 in https://books.google.de/books?id=7_DuCAAAQBAJ&printsec=frontcover&hl=de&source=gbs_ge_summary_r&cad=0#v=onepage&q&f=false for isometrically embedding of $(\mathbb{N},d)$ in a Hilbert space.

Edit: Here is some Sage code in case one wants to check this numerically for some examples:

def dABC(a,b):
    """ABC"""
    return 1- 2*gcd(a,b)**3/(a*b*(a+b))

def MM(xx,d=dABC):
    N = len(xx)
    return matrix([[1/2*(d(xx[0],xx[i])**2+d(xx[0],xx[j])**2-d(xx[i],xx[j])**2) for i in range(1,N)] for j in range(1,N)])

def skp(a,b,d=dABC):
    return 1/2*(d(a,1)**2+d(b,1)**2-d(a,b)**2)

def schur(M):
    from scipy.linalg import schur
    import numpy as np
    M_np = np.matrix(M,dtype='float64')
    A,B = schur(M_np,output="complex")
    return (matrix(np.asmatrix(A)),matrix(np.asmatrix(B)))

def createEmbedding(rr):
    M = MM(rr)
    n = len(rr)+1
    A,B = schur(M)
    E = diagonal_matrix([sqrt(x) for x in A.diagonal()])
    X = B*E
    ee = [ matrix([[i==j] for i in range(1,n-1)],ring=QQ) for j in range(1,n-1)]
    #print ee
    xx = [ X.transpose()*ee[i] for i in range(n-2)]
    return xx

N = 20
for i in primes(N):
    for j in primes(i+1,N):
        for k in primes(j+1,N):
            a = dABC(i,j)
            b = dABC(j,k)
            c = dABC(k,i)
            s = 1/2*(a+b+c)
            area = sqrt(s*(s-a)*(s-b)*(s-c)).n()
            alpha = pi.n()-arccos((skp(j,k)-skp(j,i)-skp(k,k)+skp(k,i))/(b*c))
            beta = pi.n()-arccos((skp(j,i)-skp(k,j)-skp(i,i)+skp(i,k))/(a*c))
            gamma = pi.n()-arccos((skp(j,k)-skp(k,i)-skp(j,j)+skp(j,i))/(b*a))
            print i,j,k,"area:",area, "sum:",(alpha+gamma+beta).n(),pi.n()
            print i,j,k,"sine law:",a/sin(alpha).n(),b/sin(beta).n(),c/sin(gamma).n()
            print i,j,k,"lengths:", a.n(),b.n(),c.n()
            print i,j,k,"cosine law: c", c**2.0,(a**2+b**2-2*a*b*cos(gamma)).n(),cos(gamma).n()
            print i,j,k,"cosine law: b", b**2.0,(c**2+a**2-2*c*a*cos(beta)).n(),cos(beta).n()
            print i,j,k,"cosine law: a", a**2.0,(c**2+b**2-2*c*b*cos(alpha)).n(),cos(alpha).n()
for n in range(2,101):
    print n, MM(range(1,n)).is_positive_definite()

Second Edit: Just out of curiosity: For $(a,b,c)=(1,2,2k+1)$, so $c \ge 3$ is odd, we get using the sum of angles in a triangle:

$$\alpha + \beta + \gamma = \pi$$

the following curious identity. For each odd $c \ge 3$ we have:

$$\operatorname{acos}(\frac{4 \, c^{5} + 28 \, c^{4} + 62 \, c^{3} + 2 \, c^{2} - 153 \, c - 135}{12 \, {\left(c + 2\right)}^{3} {\left(c + 1\right)} c} ) +$$ $$ \operatorname{acos}(\frac{14 \, c^{5} + 98 \, c^{4} + 226 \, c^{3} + 142 \, c^{2} - 135 \, c - 153}{18 \, {\left(c^{2} + 2 \, c - 1\right)} {\left(c + 2\right)}^{2} {\left(c + 1\right)}}) + $$ $$\operatorname{acos}(\frac{4 \, c^{6} + 24 \, c^{5} + 70 \, c^{4} + 156 \, c^{3} + 187 \, c^{2} - 18 \, c - 135}{12 \, {\left(c^{2} + 2 \, c - 1\right)} {\left(c + 2\right)} {\left(c + 1\right)}^{2} c}) = \pi$$

Third edit:

I think the main property which distinguishes $d$ for example from the Jaccard or other metrics is the proven property ( https://mathoverflow.net/a/342921/6671) :

For all $a \neq b, a\neq c$ we have:

$$d(a,b)+d(a,c) > 1$$

I have tested other metrics with this property and they also seem to embedd in Euclidean Space. On the other hand metrics who do not have this property do not seem to embedd. So I think this is the point to be taken into consideration.

If someone has an idea how to exploit this property that would be very nice!

$\endgroup$
  • 1
    $\begingroup$ Do you have a proof that your $d$ is indeed a metric ? $\endgroup$ – GreginGre Oct 9 at 9:42
  • $\begingroup$ @GreginGre: Yes it is a metric: mathoverflow.net/a/343061/6671 $\endgroup$ – orgesleka Oct 9 at 9:44
  • $\begingroup$ Ok. How do you define your metric if $a=0$ ? $\endgroup$ – GreginGre Oct 9 at 9:53
  • 1
    $\begingroup$ With "natural numbers", I mean $\mathbb{N}$ without $0$. Sorry for not being clear on this point. $\endgroup$ – orgesleka Oct 9 at 9:54
  • $\begingroup$ Ok, i thought so, but wanted to be sure. The easiest case seems to take $x_0=1$ and $x_1,x_2,x_3$ pairwise coprime. Have you tried to write down the $4\times 4$ matrix and see if it is positive semidefinite ? $\endgroup$ – GreginGre Oct 9 at 10:04
8
$\begingroup$

It can be done for the metric

$$d(a,b)^2 = 1 - \frac{(a,b)}{\sqrt{ab}},$$

and other similar ones like $d(a,b)^2 = 1 - \frac{(a,b)^2}{ab}$, with some twists in the construction.

Suppose we want to embed $1,2,..., n$ in $\mathbb{R}^n$. We will first embed these in $\mathbb{R}^m$, where $m = lcm(1,2,...,n)$.

For each natural number $k\in\{1,...,n\}$ map it to the vector $v_k \in \mathbb{R}^m$ whose $i$-th entry is equal to $\sqrt{k}$ if $i$ is a multiple of $k$ and $0$ otherwise. Noticing that the vectors $v_a$ and $v_b$ are only both non-zero at the entries multiple of $[a,b] = lcm(a,b)$ we get:

$$\|v_a-v_b\|^2 = (\frac{m}{a}-\frac{m}{[a,b]})a+(\frac{m}{b}-\frac{m}{[a,b]})b+\frac{m}{[a,b]}(\sqrt{a}-\sqrt{b})^2$$

$$=2m(1 - \frac{\sqrt{ab}}{[a,b]}) = 2m(1-\frac{(a,b)}{\sqrt{ab}}).$$

This means that after normalization by $2m$ we get the desired embedding. For an embedding in $\mathbb{R}^n$ take the induced embedding in the subspace $span(v_1,...v_n)$.


Another nice embedding straight to a Hilbert space follows from the identity for any natural numbers $a,b$

$$\int_0^1 \psi(at)\psi(bt) dt = \frac{1}{12} \frac{(a,b)^2}{ab}.$$

Where $\psi(t) = t - \lfloor t \rfloor - \frac{1}{2}$ is the sawtooth function. Therefore for any natural numbers $a,b$

$$\|\psi(at) - \psi(bt)\|_{L^2}^2 = \frac{1}{6}(1-\frac{(a,b)^2}{ab}).$$

So the embedding $\mathbb{N} \hookrightarrow L^2([0,1])$ taking $n \mapsto \psi(nt)$ (also normalizing by $\frac{1}{6}$) preserves this metric!

From the point of view of Fourier series this construction is similar to the previous one, noticing that $\psi(nt)$ only has non-zero Fourier coefficients at the entries divisible by $n$.

$\endgroup$
  • $\begingroup$ Thanks for your help! $\endgroup$ – orgesleka Oct 12 at 17:11
5
$\begingroup$

Given that the set of integers has fractal dimension -1, I would not be surprized that such trigonometry is possible, it would be trigonometry on a manifold of negative dimension. Particularly, the set of prime numbers would play the role of the -2-sphere.

$\endgroup$
  • $\begingroup$ thanks for your interesting answer. do you know a reference for this? (+1) $\endgroup$ – orgesleka Oct 10 at 11:41
  • 4
    $\begingroup$ @orgesleka fractal dimension is a measure of how much of self-copies the set contains if it is scaled up by a factor. For instance, a cube incleases 8x if we scale it twice, so its dimension is $\ln8/\ln2=3$. For a square the dimension is $\ln 4/\ln2=2$. For a line it is $\ln 2/\ln 2=1$, for a point it is $\ln 1/\ln2=0$. If you take the set of natural numbers and scale it twice, it becomes twice less dense, so we have $\ln(1/2)/\ln2=-1$ $\endgroup$ – Anixx Oct 10 at 12:10
  • 2
    $\begingroup$ In what sense would the primes correspond to the (-2)-sphere? $\endgroup$ – Noah Schweber Oct 11 at 20:39
  • $\begingroup$ @Noah Schweber I think this is not suitable for the metric introduced in the question, but if we consider the number of divisors of a number a norm, then the prime numbers would be the set of elements with norm equal 1, that is a unit "sphere". $\endgroup$ – Anixx Oct 12 at 13:00
  • 2
    $\begingroup$ @Anixx: I don't think considering the number of divisors is a "norm". However you might consider the following which comes close to what you mean: Let $X_a = $ divisors of $a$. Then you can consider the Jaccard metric for example noticing that $|X_a \cap X_b| = \tau(\gcd(a,b))$ where $\tau(a) = $ number of divisors of $a$. You get $d_J(a,b) = 1-\frac{\tau(\gcd(a,b))}{\tau(a)+\tau(b)-\tau(\gcd(a,b))}$. Defining $|a| = d_J(a,1)$ then for a prime $p$ we have $|p| = 1/2$ so scaling this metric with $\times 2$ you get primes of "norm" $1$. But I am not sure if this metric embedds in $R^n$. $\endgroup$ – orgesleka Oct 12 at 14:04
3
$\begingroup$

I just add references for a mentioned identity by previous answer that is a known identity by Franel ([1]), and Landau ([2]).

It is an identity related in the study of an equivalent form to the Riemann hypothesis.

References:

[1] J. Franel, Les suites de Farey et le problème des nombres premiers, Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen, Mathematisch-Physikalische Klasse (1924), pp 198-201.

[2] Edmund Landau, Bemerkungen zu der vorstehenden Abhandlung von Herrn Franel, Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen, (1924), Mathematisch-Physikalische Klasse, pp 202–206.

$\endgroup$
  • $\begingroup$ A very detailed derivation of the identity is in pages 36-38 from (in Spanish) Adrián Delgado del Sol, Algunas formulaciones equivalentes a la hipótesis de Riemann, Trabajos Fin de Máster 2015-2016, Universidad Autónoma de Madrid (28 de junio de 2016). $\endgroup$ – user142929 Oct 12 at 5:50
  • 1
    $\begingroup$ thanks for the reference $\endgroup$ – orgesleka Oct 12 at 5:53
  • $\begingroup$ Thanks to you @orgesleka and to the other mathematicians for such nice posts. As I said you can find the identity in the Spanish document that is online available, where $\text{m.c.d}(a,b)$ is the greatest common divisor and $\text{m.c.m}(a,b)$ denotes the least common multiple. On the oher hand the fractional part function and the floor function have Fourier series expansion that I evoke (I am an amateur, not a professor) that maybe are useful, see the Wikipedia Floor and ceiling functions; other expression that can be useful to do analysis is the MSE question 2807610. $\endgroup$ – user142929 Oct 12 at 6:08
2
$\begingroup$

The answer given are already very good. I just wanted to point, that there are also an infinte family of metrics who embed in euclidean space.

First notice that for finite sets $X,Y$ contained in a larger finite set $Z$, the symmetric difference metric $d(X,Y) = \sqrt{|X|+|Y|-2|X \cap Y|}$ can be embedded in euclidean space by listing the elements of $Z$ in an ordered way and the vector $\phi(X)$ is a binary vector with the $i$-th entry $=1$ if $z_i \in X$ and $0$ otherwise. Then $|\phi(X)| = |X|$ and $|\phi(X)-\phi(Y)|^2 = d(X,Y)$, which shows the embedding.

By considering the sets $X_a = \{ a/k | 1 \le k \le a \}$ and noticing that $|X_a \cap X_b| = \gcd(a,b)$ we get the metric on natural numbers:

$d(a,b) = \sqrt{|X_a|+|X_b|-2|X_a\cap X_b|} = \sqrt{a+b-2 \gcd(a,b)}$ which can be embedded as was shown in Euclidean space.

On the other hand if we consider sets $X_a$ such that $|X_a| = \sigma_k(a)$ where $k \ge 0$ and $\sigma_k(a) = \sum_{d|a}d^k$, which are not difficult to construct, and such that $|X_a \cap X_b| = \sigma(\gcd(a,b))$, we get an infinte sequences of metrics, which can be embedded in Euclidean space:

$$d_{\sigma,k}(a,b) = \sqrt{\sigma_k(a)+\sigma_k(b)-2\sigma_k(\gcd(a,b))}$$. For $k=0$ and $\tau(a) = \sigma_0(a)$ we observe,that primes $p$ have norm equal to one:

$$|p|:= d_{\sigma,0}(1,p) = \sqrt{1+2-2\cdot 1}=1$$

Hence under this metric all primes are on the unit sphere.

Especially for $k=1$ and $p,q,r$ three pairwise distinct primes, we get invoking the law of cosines and $d_1(p,q)^2 = p+q$ the following nice formula:

$$\pi = \operatorname{acos}(\frac{r}{\sqrt{(p+r)(q+r)}})+\operatorname{acos}(\frac{q}{\sqrt{(p+q)(q+r)}})+\operatorname{acos}(\frac{p}{\sqrt{(p+r)(p+q)}})$$

$\endgroup$
  • $\begingroup$ This last formula, and all similar ones, though seem to hold for all reals $p,q,r$ (with obvious restrictions on the ranges)... Is it any easier to get them through these arithmetic constructions than simple trigonometric algebra? $\endgroup$ – Yaakov Baruch Oct 15 at 8:57
  • $\begingroup$ @yaakovbaruch: Yes, it holds for every three point metric space, as it can be embedded in $\mathbb{R}^2$. See math.stackexchange.com/questions/3393140/… $\endgroup$ – orgesleka Oct 15 at 9:01
  • $\begingroup$ Just as aside comment (isn't required a response, additionally I don't know if my comment has a good mathematical content) is that I was thinking in different applications, then for three of such points/integers that can be embedded in $\mathbb{R}^2$ one has the remarkable isoperimetric inequality (the article Isoperimetric inequality from Wikipedia shows the section 2, the section 6 and the section 8. Isoperimetric inequality for triangles) where the area of a triangle can be calculated using Heron's formula. I think that the interesting ones are formulas for pairwise coprime integers. $\endgroup$ – user142929 Oct 15 at 10:13
  • 1
    $\begingroup$ @user142929: I was thinking the in the same direction. But I don't think that 3 points are enough, as one will get inequalities which are true for every 3 point metric space. To make use of embeddability, one has to take at least four points which could build for example a tetrahedron and then maybe use the isoperimetric inequality for this tetrahedron in $\mathbb{R}^3$. $\endgroup$ – orgesleka Oct 15 at 10:43
  • $\begingroup$ Many thanks I add these comments but I do not realize if these have a good mathematical content, the feedback of previous user if I understand well is that it is required try to do specializations and applications of your distances for pairwise coprime integers, because in other case if your specializations are only for prime numbers there is a risk of loss of the arithmetic of the number theoretic functions with which you are working @orgesleka $\endgroup$ – user142929 Oct 15 at 11:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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