Let $X\_1,\cdots,X\_n$ be finite subsets of some set $Z$. Then the symmetric difference metric space:


$$d(X\_i,X\_j) = \sqrt{ |X\_i|+|X\_j|-2|X\_i\cap X\_j|}$$
can be embedded in Euclidean space. The value $|X\_i \cap X\_j| = \langle \phi(X\_i),\phi(X\_j) \rangle$ is equal to the dot product of the embeddings $\phi(X\_i),\phi(X\_j)$.
Taking $X\_i = \{ i/k | 1 \le k \le i\}$ for a natural number $i \ge 2$, then one observes that $X\_i \cap X\_j = X\_{\gcd(i,j)}$ hence $\langle \phi(X\_i),\phi(X\_j) \rangle =|X\_i \cap X\_j| = |X\_{\gcd(i,j)}|=\gcd(i,j)$


and the gcd-matrix $\gcd(i,j)$ is a matrix which consists of pairwise dot-products, hence a Gram-Matrix, which is positive definite. Thus we might want to "define" a kernel $K(i,j) := \gcd(i,j)$ and apply the kernel trick in Support Vector Machines to decide if the "training set" $2 \le i \le n, (i,\pm 1),$ where $+1$ if $i$ is prime, $-1$ otherwise, is linear separable or not.


The "kernel trick" in this context is just a method to do the svm computation without explicitly constructing the embedding $\phi$, to determine the linear separability of the training set. For future values, this might or not be useless. In fact the "kernel trick" is not needed technically since we can use the standard dot product after embedding the numbers (but for this one would have to explicitly construct the embedding $\phi$). For the definition of the embedding $\phi$, see: [Is this function embeddable in Euclidean space?](https://mathoverflow.net/questions/344229/is-this-function-embeddable-in-euclidean-space)


I have implemented this idea in scikit learn and it seems that primes are in this sense linear separable. However, I do not understand why this is so. Is there any theoretical explanation for this?


Thanks for your help.



```
import math
import math,csv
import numpy as np
import pandas as pd
import csv,math,collections
import math,csv, random
import numpy as np
import re
from collections import Counter
from sklearn import svm, metrics
from functools import partial
from sklearn.model_selection import cross_val_score
from sklearn.decomposition import KernelPCA
from sklearn.neighbors import NearestNeighbors
from sklearn.metrics import confusion_matrix
import random,nltk,sys
from fractions import gcd


def is_prime(n):
    if int(math.sqrt(n))**2 == n:
        return(False)
    for i in range(2,int(math.ceil(math.sqrt(n)))):
        if n%i==0:
            return(False)
    return(True)

X = range(2,50)
y = [ is_prime(x)*1 for x in X]

def d1(a,b):
    return np.sqrt(a+b-2*gcd(a,b))

def d2(a,b):
    return np.sqrt(np.abs(a-b))

dd = d1

def simLeinster(x,y,dist=dd):
    return np.exp(-dist(x,y))

def psdKern(x,y,dist=dd):
    """This is a psd-Kernel if dist can be embedded in Euclidean Space
    """
    t = 1.0/2.0*( dist(x,1)**2+dist(y,1)**2-dist(x,y)**2)
    return( t )

def proxy_kernel(X,Y,K):
    gram_matrix = np.zeros((X.shape[0], Y.shape[0]),dtype=np.float64)
    for i, x in enumerate(X):
        for j, y in enumerate(Y):
            gram_matrix[i, j] = K(x[0], y[0])
    return gram_matrix



XX_train = np.array(X).reshape(-1,1) 
Y = np.array(y) 

kernel = partial(proxy_kernel, K=gcd)
Gram = (kernel(XX_train,XX_train))
clf = svm.SVC(kernel=kernel)
print(Gram.shape)
import scipy.linalg
print(Gram)
print(scipy.linalg.eigvalsh(Gram))

scores = cross_val_score(clf, XX_train, Y, cv=5,scoring="accuracy")
print(scores)
#The mean score and the 95% confidence interval of the score estimate are hence given by:
print("Score: %0.2f (+/- %0.2f)" % (scores.mean(), scores.std() * 2))
clf = clf.fit(XX_train,Y)
y_pred = clf.predict(XX_train)
print( sum(Y==y_pred)/len(Y) )
print(confusion_matrix(Y,y_pred))
print(y_pred)

```

Related:
[Is this function embeddable in Euclidean space?](https://mathoverflow.net/questions/344229/is-this-function-embeddable-in-euclidean-space)


[Trigonometry / Euclidean Geometry for natural numbers?](https://mathoverflow.net/questions/343479/trigonometry-euclidean-geometry-for-natural-numbers)


**Edit**:
The linear separability of primes in this case might be stated as this conjecture:


Let $x\_i=i+1, 1\le i \le n$, $y\_i = +1,$ if $x\_i$ is prime, $-1$ otherwise.


Then (?) there exists $b,c\_i \in \mathbb{R}, 1 \le i \le n$ such that for all $j=1,\ldots,n$:


$$y\_j = \text{ sgn }\left(\left[\sum\_{i=1}^n c\_iy\_i\gcd( x\_i, x\_j)\right] - b\right)$$


After waiting 2 days also posted on MSE:
<https://math.stackexchange.com/questions/3497098/can-gcd-separate-primes-from-composite-numbers>



Are primes linearly separable?
The purely number-theoretic problem can be stated as: For every $n$, are there reals $b$ and $c\_i$ such that
$$j\text{ is prime iff }\sum\_{i=2}^n c\_i \gcd(i,j)>b\ ?$$
This is the same as the version above, after removing the $x$'s and $y$'s, shifting the indices by 1, and incorporating a factor of $y\_i$ into the $c\_i$.


For example, for $n=6$, this is asking for reals $b$ and $c\_i$ such that
$$
\begin{pmatrix}
2 & 1 & 2 & 1 & 2 \\
1 & 3 & 1 & 1 & 3 \\
2 & 1 & 4 & 1 & 2 \\
1 & 1 & 1 & 5 & 1 \\
2 & 3 & 2 & 1 & 6 \\
\end{pmatrix}
\begin{pmatrix}
c\_2 \\ c\_3 \\ c\_4 \\ c\_5 \\ c\_6
\end{pmatrix}
\text{ is of the form }
\begin{pmatrix}
>b \\ >b \\ <b \\ >b \\ <b
\end{pmatrix}
$$
So long as this matrix $M\_n$ of gcd's is invertible, we can take $b=0$, consider the vector $v$ with values $v\_i=1$ if $i-1$ is prime, $v\_i=-1$ if $i-1$ is composite, and let $c=M\_n^{-1}v$.


In fact these matrices are always invertible, as shown by Scott Beslin and Steven Ligh, "Greatest Common Divisor Matrices" ([here](https://www.sciencedirect.com/science/article/pii/0024379589905727)). So in that sense the primes are linearly separable.


*Update:* The determinant of the matrix above is 104; the sequence of determinants $\det(M\_n)$ begins with $2, 5, 10, 44, 104$, and is now in the OEIS as [A330967](https://oeis.org/A330967).


