Say there is a a sequence of integers, $a_k$, that keeps coming toward you, and you have an infinite memory of the sequence, and the only measure you can do on the sequence is the following :
($a_k$,$a_{k_1}$) = $d_{k_1}$, ($a_k$,$a_{k_2}$) = $d_{k_2}$, ($a_k$,$a_{k_3}$) = $d_{k_3}$, ($a_k$,$a_{k_4}$) = $d_{k_4}$, $...$ ($a_k$,$a_{k_n}$) = $d_{k_n}$
- For each new number that comes in you can select up to $n$ previous numbers, $a_{k_i}$, and for each of these $n$ previous numbers, you can calculate the greatest common divisor of the new number and that previous number.
I conjecture that the gcd of randomly selected pairs of integers is 1 with high unknown probability and then :
2 with probability 0.25
3 with probability 0.11
and so on by terms in the Basel problem series.
My question is :
Using only this metric is it possible to distguish between the following sequences:
- A. A sequence of compressed bytes from a streaming youtube video
- B. The English text of a poem by Neruda, with characters mapped to ASCII codes
- C. Some 'random' noise generated by http://random.org
- D. A geometric progression.
- E. An arithmetic progression.
- F. The prime gaps sequence : 1, 2, 2, 4, 2, 4, 2, 4, 6, 2, etc...
By, using only, I mean you are not even allowed to see the individual elements of the sequence, only to query about the GCD between elements i, and j at any index in the past.
A way to approach rigorously the nonexistent notion of an integer chosen uniformly randomly is to consider the probability measures $\mu_s$ on $\mathbb N$ defined for each $s\gt1$ by $\mu_s(n)=1/(n^s\zeta(s))$ for every $n$ in $\mathbb N$. The pointwise limit of $\mu_s$ when $s\to1$ has some nice features, for example, $\mu_s(k\mathbb N)=1/k^s$ hence $\mu_s(k\mathbb N)\to1/k$, for every $k\geqslant1$, a property one might view as desirable. Likewise, being divisible by $n$ and by $m$ are two independent events for every $\mu_s$ when $n\wedge m=1$ since then $(n\mathbb N)\cap(m\mathbb N)=(nm)\mathbb N$. Beware though that there is no limiting probability measure to the family $(\mu_s)$ when $s\to1$ since, for example, $\mu_s(n)\to0$ for every $n$ in $\mathbb N$.
In this setting, consider two random variables $N_s$ and $M_s$ i.i.d. with distribution $m_s$, that is, assume that, for every $n$ and $m$ in $\mathbb N$, $\mathbb P(N_s=n,M_s=m)=1/(n^sm^s\zeta(s)^2)$. Then the gcd $D_s$ of $N_s$ and $M_s$ is such that $[D_s\in k\mathbb N]=[N_s\in k\mathbb N]\cap[M_s\in k\mathbb N]$. This implies that $\mathbb P(D_s\in k\mathbb N)=1/k^{2s}$ for every $k\geqslant1$, in particular, $\mathbb P(D_s\in k\mathbb N)\to1/k^{2}$ when $s\to1$. Furthermore, $[D_s=1]$ is the complement of the union of the independent events $[D_s\in p\mathbb N]$ for every $p$ in the set $\mathfrak P$ of prime numbers. Thus, $$ \mathbb P(D_s=1)=\prod_{p\in\mathfrak P}\left(1-\frac1{p^{2s}}\right)\to\prod_{p\in\mathfrak P}\left(1-\frac1{p^2}\right)=\left(\sum_{n\geqslant1}\frac1{n^2}\right)^{-1}=\frac1{\zeta(2)}=\frac6{\pi^2}. $$ (A shortcut to this formula is to note that $D_s$ converges in distribution to a random variable $D$ with distribution $\mu_2$, hence $\mathbb P(D_s=1)\to\mu_2(1)$.)
In this sense, one may ascribe the "probability" $1/k^2$ to the "event" that two random integers independent and "uniformly distributed" are both multiples of some $k\geqslant1$, the "probability" $1/(k^2\zeta(2))=6/(\pi^2k^2)$ to the "event" that the gcd of two random integers independent and "uniformly distributed" is exactly $k\geqslant1$, and, in particular, the "probability" $1/\zeta(2)=6/\pi^2$ to the "event" that two random integers independent and "uniformly distributed" are relatively prime. Likewise, for every $i\geqslant2$, the "probability" that $i$ random integers independent and "uniformly distributed" are relatively prime is $1/\zeta(i)$.