7
$\begingroup$

Besides prime numbers, is there another physically realizable counting process that exhibits a 1/log density ? The reason I am posting this question is that we are measuring the response of a quantum tunneling based counting device and it is showing 1/log asymptotics which we have matched up to 50 million primes. The measurement results can be found here

https://arxiv.org/abs/1711.11032

In other words, is the 1/log density unique to prime number generation ? Any suggestions would be helpful before we set up an experiment to precisely measure the electron transport process.

Improve this question
$\endgroup$
5
  • $\begingroup$ I thought the density of primes was not $1/\log x$ but $1/\log x - 1/\log^2 x$ --- is the difference significant on the range of your experiment? $\endgroup$
    – Carlo Beenakker
    Commented Dec 4, 2017 at 22:03
  • 1
    $\begingroup$ Primes are $1/\log x$ at least in the sense that $\pi(x)/x$ is asymptotic to $1/\log x$. $\endgroup$
    – Gerry Myerson
    Commented Dec 4, 2017 at 22:20
  • 1
    $\begingroup$ I'm not sure what a "counting process" is here. Do you mean, for example, a sequence $a_n$ solving some counting problem such that $a_n \sim \frac{n}{\log n}$, or do you mean more specifically a subset $S \subseteq \mathbb{N}$ such that $|S \cap [n]| \sim \frac{n}{\log n}$? $\endgroup$
    – Qiaochu Yuan
    Commented Dec 4, 2017 at 23:05
  • 3
    $\begingroup$ I also have no idea what "physically realizable" should mean here. $\endgroup$
    – Qiaochu Yuan
    Commented Dec 4, 2017 at 23:36
  • $\begingroup$ Since in our experiment we are counting electrons, the underlying process measures \sum_n \in \mathcal{N} I(n) where I(.) is an indicator function and n refers to time-instants when the electrons tunnel through. $\endgroup$
    – shantanu
    Commented Dec 4, 2017 at 23:47

1 Answer 1

Reset to default
13
$\begingroup$

No. One can create many sets of integers whose density decays like 1/log. An easy variant of the set of primes is the set of integers $n$ not divisible by any prime less than $n^\alpha$, for some fixed $0<\alpha<\frac12$.

Here's another example: the set of all integers $n$ such that $n$ is divisible by the number of digits of $n$. (So all one digit numbers, all even two-digit numbers, all three-digit multiples of 3, ..., all ten-digit numbers ending in 0, etc.) The number of digits of $n$ is $\lfloor \log_{10}(n) \rfloor + 1$, so the 1/log behavior emerges naturally from the definition.

A stranger possibility is to take numbers $n$ such that both $n$ and $n+1$ can be written as the sum of two squares, $n=a^2+b^2$ and $n+1=c^2+d^2$. The set of numbers that can be written as the sum of two squares has density decaying like 1/sqrt(log), and this "twin" construction essentially multiplies those two "probabilities" together (up to the leading constant).

As a general rule: when people see that the set of primes has a particular property, they tend to overestimate how unique the set of primes is with respect to that property (or how characteristic that property is of the set of primes).

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for the examples. Would you know if there are physical systems that can implement these different discrete process ? For our device, we are counting the number of electrons so the underlying stochastic process is measuring the total counts \sum_{n \in N} I(n) where I(.) is an indicator function and n is time instant representing the occurrence of an event. $\endgroup$
    – shantanu
    Commented Dec 4, 2017 at 23:57
  • $\begingroup$ A program running on a computer is a physical system.... $\endgroup$
    – Greg Martin
    Commented Dec 5, 2017 at 21:13
  • 1
    $\begingroup$ Another simple counting process having the same density would be any (typical) realization of Cramer's random model of the primes. In this model, for each positive integer x you decide independently with probability 1/log x if it is prime or not. Obviously this gives a sequence with density 1/log. Also, I suppose this is "physically realizable" (by throwing some sort of dice), whatever this term might mean. $\endgroup$
    – Kurisuto Asutora
    Commented Dec 6, 2017 at 20:45
  • $\begingroup$ The question is where does the 1/log x probability arise from. At the fundamental level a physical system is a realization of a quantum mechanical system defined by a system evolution. There is this notion of reimannian that defines this evolution but that system is only hypothetical and to our knowledge we dont know of a device that implements it. $\endgroup$
    – shantanu
    Commented Dec 7, 2017 at 13:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .