26
$\begingroup$

A philosopher asked me an interesting math question today! We know that there are sets S of integers which don't have a "natural" or "naive" density -- that is, the quantity (1/n)|S intersect [1..n]| doesn't approach a limit. The "analytic" or "Dirichlet" density exists whenever the naive density does, and is equal to it -- but sometimes is well-defined even when the naive density is not, for instance when S is the "Benford set" of integers whose first digit is 1. (See this related MO question.)

Anyway, the philosopher asked: why stop at Dirichlet density? Is there a sequence of probability measures p_1, p_2, p_3, .... on the natural numbers such that

  • Whenever S has a Dirichlet density, the limit of p_i(S) exists and is equal to the Dirichlet density, but

  • there are subsets of the natural numbers such that p_i(S) approaches a limit but S has no Dirichlet density?

(Possibly clarifying addition: to obtain naive density, one can take p_i to be the measure assigning probability 1/i to each integer in [1..i] and 0 to integers greater than i. To get Dirichlet density, take p_i to be the measure with p_i(n) = 1/(n^{1+1/i}zeta(1+1/i)). In either case, the corresponding density of S is the limit in i of p_i(S), whenever this limit exists. So what I have in mind is densities which can be thought of as limits of probability measures, though perhaps there are reasons to have yet more general entities in mind?)

If so, are there any examples which are interesting or which are used for anything in practice?

$\endgroup$
14
  • 7
    $\begingroup$ Dear JSE: Where did you find a philosopher who knows about Dirichlet density? $\endgroup$
    – BCnrd
    Nov 2, 2010 at 2:56
  • 2
    $\begingroup$ He didn't know about Dirichlet density -- he is a philosopher of probability who was asking me about what pure mathematicians mean when they talk about the "probability that a random integer" has this property or that. He had in mind the notion of naive density, and when I told him about Dirichlet density he asked this natural question. $\endgroup$
    – JSE
    Nov 2, 2010 at 2:57
  • 3
    $\begingroup$ What about the "logarithmic density" used in Rubinstein-Sarnak? $\endgroup$ Nov 2, 2010 at 3:00
  • 3
    $\begingroup$ Number theorists don't use probability measures on the (positive) integers; all those densities (natural, Dirichlet, logarithmic) are finitely additive, not countably additive. Take a look at Tenenbaum's book "Introduction to Analytic and Probabilistic Number Theory". There is a section in there where he compares several concepts of density on Z. $\endgroup$
    – KConrad
    Nov 2, 2010 at 4:05
  • 11
    $\begingroup$ Dirichlet density was not chosen because it had any nice properties, but because density results usually are proved with the help of zeta functions; the fact that the behaviour of such functions in the vicinity of poles is closely connected to densities of primes made Marcus, in his excellent textbook "Number Fields", introduce the name "polar density". Introducing weaker notions of density would make perfect sense if there were methods of proof which would produce results related to different notions of density. $\endgroup$ Nov 2, 2010 at 16:18

2 Answers 2

15
$\begingroup$

The best way to impress a philosopher is to tell him/her about ultrafilters. A (non-principal) filter on $\mathbb N$ is a set of infinite subsets of $\mathbb N$ closed under intersections and taking super-sets. A maximal filter (under inclusion) is called an ultrafilter. There are plenty of those but nobody saw them since their existence depends on the axiom of choice. For every filter $\omega$ one can define the concept of convergence of sequences of real numbers: a sequence $b_n$ converges to $b$ if for every $\epsilon$ the set of $i$'s such that $|b-b_i|\le \epsilon$ is in $\omega$. If $\omega$ is an ultrafilter, then every bounded sequence of real numbers has unique $\omega$-limit. It is not true if $\omega$ is not an ultrafilter. The smallest interesting filter (called Fréchet filter) consists of all sets with finite complements. The limit corresponding to that filter is the ordinary limit studied in Calculus. You can start from the Fréchet filter and add sets to it to produce bigger and bigger filters. Each filter gives you a Dirichlet-like density. If $\omega$ is an ultrafilter, then all sets will have density (between 0 and 1). Otherwise there will always be sets without density assigned.

$\endgroup$
4
  • 6
    $\begingroup$ "What is the best way to impress a philosopher?" would be a great community wiki question. $\endgroup$
    – JSE
    Nov 3, 2010 at 6:19
  • $\begingroup$ Let me see if I understand where you're getting your sequence of real numbers: is b_n taken to be the proportion of elements of [-n,..n] that lie in S? $\endgroup$
    – JSE
    Nov 3, 2010 at 6:35
  • $\begingroup$ @JSE: Yes. If you consider subsets of $\mathbb Z$. If only natural numbers are considered, take the interval $[1,..,n]$. $\endgroup$
    – user6976
    Nov 3, 2010 at 10:03
  • $\begingroup$ @JSE: Yes, judging by the success of the recent questions about "primes in nature" and others, this question would be very popular. An even more popular wiki question would be "what is your favorite math pick up line?" $\endgroup$
    – user6976
    Nov 16, 2010 at 2:03
10
$\begingroup$

Tenenbaum's book on analytic and probabilistic number theory has something to say on this subject. He mentions that it is "easy" to construct a set without Dirichlet density, but unfortunately he doesn't provide such a construction.

A good place to start is with the logarithmic density: Tenenbaum shows that the Dirichlet density exists if and only if

$\lim_{n \rightarrow \infty} \frac{1}{\log n} \sum_{n \in S} \frac{1}{n}$

exists.

The reason naive density fails to exist for the Benford set (call it $B$) is that oscillations between elements in $B$ and elements not in $B$ grow exponentially with $n$. I would conjecture that a set with superexponential gaps does not have a Dirichlet density - for example the set of integers $n$ where the number of digits of $n$ begins with a 1. One might have to sum over a series like $e^{-\log(\log(n))}$ to get convergence.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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