Solving Density Problems in Number Theory

[DeadOriginal]

I am currently taking a number theory course. The professor who teaches the course is very well known in his research field which is Ergodic Theory.

I find that he really likes to assign problems that deal with the density of a certain set. Sometimes the problems would be about proving whether the density of a certain set exists or not. Other times it would be proving whether the upper density of a given set is what he claims it is. Are there any general ways to tackling these kinds of problems?

 

[brmath]

If you would provide a couple examples of the sort of problems you are looking at it would be helpful. I can't even tell whether you are talking about dense subsets within the real numbers or in a general metric space.

 

[DeadOriginal]

If you would provide a couple examples of the sort of problems you are looking at it would be helpful. I can't even tell whether you are talking about dense subsets within the real numbers or in a general metric space.

Ahh. I am talking about things like shift invariance of density. For example, if we define
$$
d(A)=\lim\limits_{N\rightarrow\infty}\sup\frac{|A\cap\{1,...,N\}|}{N}
$$
then
$d(A-t)=d(A)$ for all $t\in\mathbb{Z}$.

In general, the problems usually consist of finding out whether a given density exists or not. The only problem I am familiar with is the density of the primes which is 0. The way that proof went without using the prime number theorem was to find an upper bound using the binomial coefficient. What if the set A was too abstract to find an upper bound for the density? How would I approach the problem then?

 

[brmath]

Ahh. I am talking about things like shift invariance of density. For example, if we define
$$
d(A)=\lim\limits_{N\rightarrow\infty}\sup\frac{|A\cap\{1,...,N\}|}{N}
$$
then
$d(A-t)=d(A)$ for all $t\in\mathbb{Z}$.

In general, the problems usually consist of finding out whether a given density exists or not. The only problem I am familiar with is the density of the primes which is 0. The way that proof went without using the prime number theorem was to find an upper bound using the binomial coefficient. What if the set A was too abstract to find an upper bound for the density? How would I approach the problem then?

***
Just to be sure: when you say $sup \frac {A \bigcap {1,2,...n}}{n}$ do you mean a/n where a is the largest number in that set?

Assuming that is it, I saw immediately that d(A) = 0 for any finite set; and d(A) = 1 for say A = {2n}.

Looking at the primes, it seems like the intersection would consist of all the prime numbers $\le n$. So if n is a prime p and n+k is the next prime q, we would have a sequence like p/n = 1, p/(n+1), p/(n+2) ... p/(n+k-1), q/(n+k) = 1, q/(n+k+1), ... etc.

This sequence has infinitely many 1's, and I don't see how it could converge to 0, or to anything. Have I misunderstood the problem?

 

[DeadOriginal]

***
Just to be sure: when you say $sup \frac {A \bigcap {1,2,...n}}{n}$ do you mean a/n where a is the largest number in that set?

Assuming that is it, I saw immediately that d(A) = 0 for any finite set; and d(A) = 1 for say A = {2n}.

Looking at the primes, it seems like the intersection would consist of all the prime numbers $\le n$. So if n is a prime p and n+k is the next prime q, we would have a sequence like p/n = 1, p/(n+1), p/(n+2) ... p/(n+k-1), q/(n+k) = 1, q/(n+k+1), ... etc.

This sequence has infinitely many 1's, and I don't see how it could converge to 0, or to anything. Have I misunderstood the problem?

I am sorry for not being more clear. $|A \bigcap {1,2,...n}|$ stands for the number of elements in the intersection of $A$ and ${1,2,...,n}$ as $n\rightarrow\infty$.

 

[Office_Shredder]

To be completely clear, what you wrote is intended to be the limsup of the fraction?

EDIT TO ADD: You can just write that as \limsup in tex.

 

[DeadOriginal]

To be completely clear, what you wrote is intended to be the limsup of the fraction?

Thats right. There should be a bar over d to signify its the upper density. Then d(A) represents the natural density is what my professor said today.

Sorry about that. I can't seem to edit my original post anymore.

 

[brmath]

I am sorry for not being more clear. $|A \bigcap {1,2,...n}|$ stands for the number of elements in the intersection of $A$ and ${1,2,...,n}$ as $n\rightarrow\infty$.

Okay that's clearer. So it is still true that a finite set A will have density 0. But the set {2n} will have density 1/2, which sounds better to me than 1.

I will think a bit about what I might suggest in answer to your question of how to tackle these.

 

[Office_Shredder]

Do you have some specific examples of problems that you were confused about?

 

[brmath]

Your question was really -- is there a general way to approach this kind of problem? Here are some things to consider (but do them only if you really want to know a lot more about this subject):

1. Your prof introduced the upper density before introducing the "natural" density. The upper density uses the lim sup, the lower density uses the lim inf, and the "natural" density uses the plain old limit. Sometimes the lim sup and lim inf are easier to compute than the limit. If you can compute them and show they are equal, you have a natural density. If you can compute them and show they are not equal, there is no natural density. If the lim sup is 0 (as it was for the primes), then the natural density is 0.

2. That said, there is no reason obvious to me why you wouldn't try the plain limit first.

3. Next, you said the only set you have worked with is the primes. Before you jump into how to tackle complex and unobvious sets, you should work out a number of examples on simple sets, so you get a feel for what you are trying to do. You will notice that I myself jumped immediately to look at finite sets; then the set {2n}. The reason was to make sure I understood what was being asked. So why don't you try out some of these simple cases. You might try first {n/2}. Then try something a little more complex such as {$n^2$}. For this second set I would look at the function $y = x^2$ to see if I could get a handle on the intersection. (However, I haven't worked this one out, and it might not be easy -- see what you find out).

4. Once you have done some of that work, you want to look up examples of how people did more complex sets A. They are using quite a variety of tricks. Some of those tricks may be used frequently, in which case you want to remember them. For example, they may compare A to some other set B of which it is a subset. In that case the lim sup for A will be below the lim sup for B ( and vice versa for the lim inf). And maybe with a bound on the lim sup and lim inf for A you can deduce the actual value.

$\hspace{20px}$ However, many of the computations will depend on the specifics of A and will not fall into any particular category. The specifics of A have to do with the distribution of the integers in A, and that can be very hard to determine. If you can find a theorem anywhere that throws light on this distribution, you should use it.

5. I think this is often a very hard problem and some very clever mathematicians have worked out solutions for a variety of A's. That doesn't mean that you, as a student, should be able to match their skill. I would also guess that there are some sets A for which no solutions are known.

6. What I said in point 3 is a good way to start working on any mathematics problem. Look at a simple case, or two or three. That will help you understand what the problem is, how the various hypotheses connect with the conclusion, etc. If you can't solve even a simple case, then you probably don't understand the problem. (My assumption in saying this is that the problem was presented in a class, and thus has a known solution, supposedly within the reach of your mathematical knowledge.)

$\hspace{20px}$If you can solve the simple cases, that may throw a lot of light on how to solve the general case. Suppose for example suppose you have a problem in linear algebra and can solve it for n = 2. It may very well be that your solution doesn't depend in any way on n being 2; so you use the same logic for the general case.

7. Finally, I would like very much to see how you could bound the lim sup for the primes using the binomial coefficient. If you'd share that I'd appreciate it. I would say this probably falls into the category of special tricks, which a student mathematician is not likely to think of.

 

[DeadOriginal]

Your question was really -- is there a general way to approach this kind of problem? Here are some things to consider (but do them only if you really want to know a lot more about this subject):

1. Your prof introduced the upper density before introducing the "natural" density. The upper density uses the lim sup, the lower density uses the lim inf, and the "natural" density uses the plain old limit. Sometimes the lim sup and lim inf are easier to compute than the limit. If you can compute them and show they are equal, you have a natural density. If you can compute them and show they are not equal, there is no natural density. If the lim sup is 0 (as it was for the primes), then the natural density is 0.

2. That said, there is no reason obvious to me why you wouldn't try the plain limit first.

3. Next, you said the only set you have worked with is the primes. Before you jump into how to tackle complex and unobvious sets, you should work out a number of examples on simple sets, so you get a feel for what you are trying to do. You will notice that I myself jumped immediately to look at finite sets; then the set {2n}. The reason was to make sure I understood what was being asked. So why don't you try out some of these simple cases. You might try first {n/2}. Then try something a little more complex such as {$n^2$}. For this second set I would look at the function $y = x^2$ to see if I could get a handle on the intersection. (However, I haven't worked this one out, and it might not be easy -- see what you find out).

4. Once you have done some of that work, you want to look up examples of how people did more complex sets A. They are using quite a variety of tricks. Some of those tricks may be used frequently, in which case you want to remember them. For example, they may compare A to some other set B of which it is a subset. In that case the lim sup for A will be below the lim sup for B ( and vice versa for the lim inf). And maybe with a bound on the lim sup and lim inf for A you can deduce the actual value.

$\hspace{20px}$ However, many of the computations will depend on the specifics of A and will not fall into any particular category. The specifics of A have to do with the distribution of the integers in A, and that can be very hard to determine. If you can find a theorem anywhere that throws light on this distribution, you should use it.

5. I think this is often a very hard problem and some very clever mathematicians have worked out solutions for a variety of A's. That doesn't mean that you, as a student, should be able to match their skill. I would also guess that there are some sets A for which no solutions are known.

6. What I said in point 3 is a good way to start working on any mathematics problem. Look at a simple case, or two or three. That will help you understand what the problem is, how the various hypotheses connect with the conclusion, etc. If you can't solve even a simple case, then you probably don't understand the problem. (My assumption in saying this is that the problem was presented in a class, and thus has a known solution, supposedly within the reach of your mathematical knowledge.)

$\hspace{20px}$If you can solve the simple cases, that may throw a lot of light on how to solve the general case. Suppose for example suppose you have a problem in linear algebra and can solve it for n = 2. It may very well be that your solution doesn't depend in any way on n being 2; so you use the same logic for the general case.

7. Finally, I would like very much to see how you could bound the lim sup for the primes using the binomial coefficient. If you'd share that I'd appreciate it. I would say this probably falls into the category of special tricks, which a student mathematician is not likely to think of.

This was very helpful. I will definitely work on your suggested exercises in 3. As for the binomial coefficient, I will find it in my notes and get back to you.