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?
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?
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