Sorting natural numbers based on metric?

115 Views Asked by At

Let $$d^J_k(a,b) = 1-\frac{\sigma_k(\gcd(a,b))}{\sigma_k(a)+\sigma_k(b)-\sigma_k(\gcd(a,b))}$$ for $a,b$ two natural numbers $k\ge 0$, $\sigma_k(a) = \sum_{d|a} d^k$. Then this is a (Jaccard) metric on the natural numbers. Consider $d(a,b) = d^J(a,b) = \sum_{k=0}^\infty \frac{1}{2^k}d^J_k(a,b)$ and define $a \unlhd b$ iff $d(a,1)\le d(b,1)$

Questions:

  1. If $a \unlhd b$ and $c$ is a natural number, then $ac \unlhd bc$? False

  2. If $a \unlhd b$ and $b \unlhd a$, then $a=b$? might be true

  3. If $a \unlhd b$ and $c \unlhd e$, then $ ac \unlhd be$? False

  4. If $\gcd(a,c)=\gcd(b,c)=1$ then $d(a,b)=d(ca,cb)$. (This is easy to prove, since $\sigma_k$ is multiplicative.)


Edit:

It seems that the ordering is a lexicographic one. By this I mean that construct the vector:

$$V(a) = (d_0(a,1),d_1(a,1),d_2(a,1)\ldots d_k(a,1) \ldots)$$

Then it seems like $a \unlhd b$ iff $V(a) \le V(b)$ where $\le$ is the lexicographic order of the given vectors.

Some Sage scripts:

def dd(a,b,k):
    return 1-sigma(gcd(a,b),k)/(sigma(a,k)+sigma(b,k)-sigma(gcd(a,b),k))

def dvec(a,K=10):
    return [dd(a,1,k).n() for k in range(K+1)]

def d(a,b,K=10):
    return sum([1/(2.0**k)*dd(a,b,k) for k in range(K+1)])

sorted([ (d(a,1,10),a) for a in range(1,100)])    

[(0.000000000000000, 1),
 (1.26352353560690, 2),
 (1.34364319712592, 3),
 (1.40497170796791, 5),
 (1.43113204316485, 7),
 (1.45520927484247, 11),
 (1.46177941791487, 13),
 (1.47035738224924, 17),
 (1.47331411564775, 19),
 (1.47770790490320, 23),
 (1.48205464375133, 29),
 (1.48313429769773, 31),
 (1.48568055948408, 37),
 (1.48696820697958, 41),
 (1.48752307533606, 43),
 (1.48849243175490, 47),
 (1.48967436265919, 53),
 (1.49061769251944, 59),
 (1.49089119792606, 61),
 (1.49161439830309, 67),
 (1.49202905783214, 71),
 (1.49221945289014, 73),
 (1.49273313109042, 79),
 (1.49303455213995, 83),
 (1.49343614594272, 89),
 (1.49389469153245, 97),
 (1.58038164357392, 4),
 (1.62430622092945, 9),
 (1.64916894831869, 25),
 (1.65681510482431, 49),
 (1.70181166355779, 6),
 (1.71251996065963, 8),
 (1.71920616143290, 10),
 (1.72714814044250, 14),
 (1.72719187491448, 15),
 (1.73288513480220, 21),
 (1.73471402834227, 22),
 (1.73621232562853, 27),
 (1.73681810775224, 26),
 (1.73839844837180, 33),
 (1.73841153706667, 35),
 (1.73958889336088, 34),
 (1.73994574914563, 39),
 (1.74054992940204, 38),
 (1.74198349871905, 46),
 (1.74199186845917, 51),
 (1.74199942675375, 55),
 (1.74270372005527, 57),
 (1.74301404059068, 65),
 (1.74340792482690, 58),
 (1.74376265890517, 62),
 (1.74376756472425, 69),
 (1.74377384596954, 77),
 (1.74436044828411, 85),
 (1.74452957378555, 91),
 (1.74460070007059, 74),
 (1.74482689550047, 87),
 (1.74483006361155, 95),
 (1.74502525419037, 82),
 (1.74509104929573, 93),
 (1.74520835591782, 86),
 (1.74552845631242, 94),
 (1.78213363982812, 16),
 (1.79485710740475, 81),
 (1.81324507872647, 12),
 (1.81896789031508, 18),
 (1.81998016814039, 20),
 (1.82318502936399, 28),
 (1.82423371804470, 32),
 (1.82583952513618, 45),
 (1.82630550851183, 44),
 (1.82690273055893, 50),
 (1.82718391487045, 52),
 (1.82749364950621, 63),
 (1.82828582492105, 75),
 (1.82834711474068, 68),
 (1.82875220479996, 76),
 (1.82912899954912, 99),
 (1.82935797699558, 92),
 (1.82941227603807, 98),
 (1.85218308685392, 64),
 (1.86538817693823, 24),
 (1.86688267571898, 30),
 (1.86835304078615, 40),
 (1.86871364331448, 42),
 (1.86979510882916, 54),
 (1.86979732014398, 56),
 (1.87050985618865, 66),
 (1.87051243084219, 70),
 (1.87101760800471, 78),
 (1.87122139031876, 88),
 (1.88228470237312, 36),
 (1.89491690092618, 48),
 (1.89630685447653, 80),
 (1.91266763629169, 60),
 (1.91309339654707, 72),
 (1.91343397284113, 84),
 (1.91353207281394, 90),
 (1.91368754226931, 96)]


# checking numerically if lexicographic sorting:
[x[1] for x in sorted([(dvec(a),a) for a in range(1,100)])] == [x[1] for x in sorted([(d(a,1),a) for a in range(1,100)])]    

True

Also a related question:

How are sequences in a metric space called where the distance between two consecutive points converges? (For Cauchy sequences this distance converges to 0). (We might call them Cauchy-like)

I am posing this question, since it seems that with the above metric, if we have a sequece $a_1 \unlhd a_2 \unlhd \ldots a_n \ldots$ such that for each $n$ there does not exist a natural numbers $x$ with $a_n \unlhd x \unlhd a_{n+1}$. We might call such a sequence "complete". Now it seems like (numerically) that every such "complete" sequence with the given metric is Cauchy-like. For example it seems that the primes are complete Cauchy-like sequence.

Of course if someone has a proof or any insight of the above statements that would be very interesting!