Solving Density Problems in Number Theory

  • Thread starter DeadOriginal
  • Start date
  • Tags
    Density
In summary: For example, find the density of all numbers divisible by a fixed integer k. Find the density of all numbers that contain the digit 3. Find the density of all numbers that have the same number of 1's and 0's in their binary expansion. Find the density of all numbers that contain exactly two prime factors.5. These are all easy to do; but they should get you warmed up for the more complex examples. If you can't do these, then you have no chance on the more complex ones.6. Okay, so you can do those. Now try a little harder: what is the density of all numbers whose sum of digits is
  • #1
DeadOriginal
274
2
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?
 
Physics news on Phys.org
  • #2
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.
 
  • #3
brmath said:
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?
 
Last edited:
  • #4
DeadOriginal said:
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?
 
  • #5
brmath said:
***
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##.
 
  • #6
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.
 
  • #7
Office_Shredder said:
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.
 
Last edited:
  • #8
DeadOriginal said:
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.
 
  • #9
Do you have some specific examples of problems that you were confused about?
 
  • #10
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.
 
  • Like
Likes 1 person
  • #11
brmath said:
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.
 

What is density in number theory?

In number theory, density refers to the proportion of numbers in a specific set that satisfy a certain condition or property. It is often used to measure the distribution of numbers within a set.

How do you solve density problems in number theory?

To solve density problems in number theory, you need to first determine the set of numbers and the condition or property that needs to be satisfied. Then, you can use various techniques such as counting, combinatorics, and algebra to calculate the proportion of numbers that meet the given criteria.

What is the difference between arithmetic density and natural density?

Arithmetic density is the proportion of numbers in a given set that satisfy a specific condition, while natural density is the limit of the arithmetic density as the set size approaches infinity. In other words, natural density takes into account the infinite set of numbers, while arithmetic density only considers a finite set.

How is density used in prime number theory?

In prime number theory, density is often used to analyze the distribution of prime numbers within a given set of numbers. This can help mathematicians understand the patterns and properties of prime numbers, which are fundamental building blocks in number theory.

Are there any limitations to using density in number theory?

Yes, there are some limitations to using density in number theory. One limitation is that it may not always be possible to accurately calculate the density of a set, especially if the set is infinite. Additionally, density does not provide a complete understanding of the distribution of numbers within a set, as it only considers one specific condition or property.

Similar threads

  • General Math
Replies
1
Views
1K
  • Special and General Relativity
Replies
11
Views
1K
  • Computing and Technology
Replies
9
Views
1K
  • General Math
Replies
1
Views
953
  • Set Theory, Logic, Probability, Statistics
2
Replies
54
Views
3K
  • Quantum Interpretations and Foundations
9
Replies
309
Views
8K
Replies
2
Views
2K
  • High Energy, Nuclear, Particle Physics
Replies
1
Views
3K
  • STEM Academic Advising
Replies
14
Views
551
Back
Top