Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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}$

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

share|improve this question
    
Why would you want to do this? –  Qiaochu Yuan Feb 28 '13 at 7:44
    
Such things interest me. I like randomness and all that jazz. How much information is in, or can be extracted from, or what form does the information take in some sequence are a few of my favorite things. –  Cris Stringfellow Feb 28 '13 at 7:51
1  
By random I mean as people would commonly consensus agree random to be... Ironically the consensus here is that it is IMPOSSIBLE to define such a thing as a uniformly distributed random integer--hence I am afraid you will have to explain what you mean by that. –  Did Mar 22 '13 at 8:32
    
@Did haha. Good point. Okay, I was hoping that sentence would avoid having to explain what random is. You found me out. –  Cris Stringfellow Mar 22 '13 at 11:04
1  
The gcd of a randomly selected pair of integers is $1$ with probability $6/\pi^2$, given a plausible interpretation of "randomly selected pair of integers". –  Gerry Myerson Mar 22 '13 at 12:13

1 Answer 1

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

share|improve this answer
    
Okay so we have a possible measure for randomness by sampling the GCDs and seeing if the occurrence of co-primality reproduces the distribution $1/\zeta(i)$, for i samples. This is good. Geometric progression will always have a GCD with probability 1. Arithmetic I am unsure of. Prime gaps will have pairwise GCD = 2 with probability 1 in the limit, and then GCD = 4, 6, ... with some discoverable distribution. The compressed bytes will likely obey the above 'random' metric, and the text of Naruda is a case that would have to be closely examined in the ring mod 257. –  Cris Stringfellow Mar 22 '13 at 19:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.