16
$\begingroup$

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

$\endgroup$
15
  • $\begingroup$ What range of values have you tried this for? The code only tries up to 50? $\endgroup$
    – R Hahn
    Jan 2, 2020 at 14:50
  • $\begingroup$ I hav tried up to 500. $\endgroup$
    – user6671
    Jan 2, 2020 at 14:51
  • 3
    $\begingroup$ Can you perhaps add a slightly better mathematical explanation of what you're doing here? The reuse of variable names (esp. $X$ and $Y$ vs. $x_i$ and $y_i$) is particularly confusing to me. On what structure is the GCD-kernel being built exactly? Right now this reads as though you're doing GCDs not just on the primes but also on the $y_i$, which seems obviously nonsensical, but my understanding isn't clear enough to grasp what you're actually doing... $\endgroup$ Jan 2, 2020 at 19:25
  • 7
    $\begingroup$ I'm still a little confused, I confess — can you explain the 'kernel trick' in somewhat more detail, and precisely what linear separability means in this context? e.g., as things currently stand the set in 2 dimensions is trivially linearly separable by the line $y=0$, but that does no good whatsoever in determining primality of future values... $\endgroup$ Jan 2, 2020 at 20:00
  • 1
    $\begingroup$ @StevenStadnicki: The "kernel trick" in this context is just a method to do the svm computation, to determine the linear separability of the training set. You are right, for future values, this is useless. In fact the "kernel trick" is not needed technically since we can use the standard dot product after embedding the numbers. For the definition of the embedding $\phi$, see: mathoverflow.net/questions/344229/… $\endgroup$
    – user6671
    Jan 2, 2020 at 20:07

1 Answer 1

12
+50
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ thanks Matt for your insight in this question $\endgroup$
    – user6671
    Jan 4, 2020 at 16:06
  • $\begingroup$ in fact you have proved that any subset of $2,\ldots,n$ is linealry separable. thanks again $\endgroup$
    – user6671
    Jan 4, 2020 at 16:53
  • $\begingroup$ +1. The invertibility of gcd matrices is interesting in its own right, but this version of the question violates the spirit of the "support vector machine" motivation which looks to generate a separating hyperplane that can classify observations using less than the full set of observations. From that perspective, one might ask about the number of non-zero elements of $c$ for a given $n$ (the associated columns are referred to as the "support vectors"). $\endgroup$
    – R Hahn
    Jan 7, 2020 at 8:03

Your Answer

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