I try to understand arXiv:1909.03562
 by Terence Tao. He uses the following definition of "almost all":

For a finite not empty subset $R$ of $\mathbb{N}$, $\text{Log}(R)$ is defined to be a random variable taking values in $R$ with logarithmically uniform distribution, so we have \begin{align} \mathbb{P}(\text{Log}(R) \in A) =\frac{\sum_{N \in A \cap R}{\frac{1}{N}}}{\sum_{N \in R}{\frac{1}{N}}}\end{align}

With this, the logarithmically density of $A \subset \mathbb{N}$ is defined as $\lim_{x \to \infty} \mathbb{P}(\text{Log}(\mathbb{N} \cap[1, x]) \in A)$.

Then a property $P$ holds for almost all $N$ if $\lim_{x \to \infty}\mathbb{P}(P(\text{Log}(\mathbb{N} \cap[1, x])) )=1$, so if it holds on a set of logarithmically density $1$.

As I have only little experience with probability theory, I do not have an intuition for this definition. How does it relate to the "classical" definition of "almost all": Holding for all, but finitely many elements?

I think, that if a statement holds for almost all in the classical definition it also holds in this sense, but what about the other direction? How large can the size of the set of exceptions get and how does this all relate to logarithms?

Thank you in advance for your help.

  • $\begingroup$ I haven't verified this, but it seems to me that he is using a roundabout way to define "almost all" in a measure-theoretic sense by putting a certain measure on $\mathbb{N}$ which he is calling the "logarithmic density". If you aren't familiar with measures or measure theory, it might be worth looking into a little bit to better understand what "almost all" means. With the Lebesgue measure on $\mathbb{R}$ for example, one can say that "almost every real number is irrational". $\endgroup$
    – Anonymous
    Jun 20, 2020 at 11:24
  • $\begingroup$ I know this example with the Lebesgue measure, but I was confused why he introduces a new measure on $\mathbb(N)$, as there is already a well-known definition for almost all. Do I understand you correctly, that you propose the defintion by Terence Tao is equivalent to "holds on all but finitely many natural numbers"? $\endgroup$
    – Matthias
    Jun 20, 2020 at 11:36
  • $\begingroup$ No, it is certainly a different measure. I'd wager there is a set without finite complement which has full measure under this definition, but I will need to think about it. $\endgroup$
    – Anonymous
    Jun 20, 2020 at 11:40

1 Answer 1


Forget about probability and measure.

Define the logarithmic density of a set $A \subseteq \mathbb{N}$ to be $$d_{\log}(A) = \lim_{N \to \infty} \frac{\sum_{n \in A, n \le N} \frac{1}{n}}{\sum_{n \le N}\frac{1}{n}}.$$ You might complain that the limit does not necessarily exist, but let's just assume it does for now. The value $d_{\log}(A)$ is supposed to represent a notion of how "large" $A$ is. Indeed, $d_{\log}(\emptyset) = 0, d_{\log}(\{2,4,6,8,\dots\}) = \frac{1}{2}$, and $d_{\log}(\mathbb{N}) = 1$. In fact, if $\lim_{N \to \infty} \frac{|A\cap\{1,\dots,N\}|}{N} = d(A)$ exists, then $d_{\log}(A) = d(A)$, and it's very clear that $d(A)$ is measuring one intuitive notion we have of "largeness".

Often times in number theory, one says that almost all numbers have property $P$ if the set $A$ of numbers having property $P$ has $d(A) = 1$, or equivalently if $d(A^c) = 0$. For example, almost all numbers are composite (since $d(\text{primes}) = 0$). In Terry's paper, however, he says that almost all numbers have property $P$ if the set $A$ of numbers having property $P$ has $d_{\log}(A) = 1$. This is a weaker notion of "almost all", since, as mentioned above, if $d(A) = 1$ then $d_{\log}(A) = 1$.

He defines "logarithmic density" and "almost all" with probabilistic notation since that notation (and intuition behind that notation) is useful in his paper, but it is of course completely unnecessary.


You must log in to answer this question.

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