59 ms·

Hmm is there an asymptotic statement underlying this? The powers of 2 are exponentially sparse (N integers contain at most 1/logN powers of 2), whereas primes a

Hmm is there an asymptotic statement underlying this? The powers of 2 are exponentially sparse (N integers contain at most 1/logN powers of 2), whereas primes are polynomially sparse (N integers contains N/LogN primes)

ColinWright 6y ago
I was trying to give people a sense of the statement, giving two examples of "not very dense" and "dense enough", but I don't understand what you're trying to say here. I can't work out whether you are asking a question, or making a conjecture, or ... what. Would you care to clarify? If it's a question then I'll try to answer, but if it's a conjecture, can you make it more precise?
- notafraudster 6y ago
  He is asking "what is the line between too sparse and not too sparse" and attempting to characterize the example you gave of each in terms of approximate relative sparsity.
  - ColinWright 6y ago
    Right ... understood. I don't have an answer, it's not my area, but it does feel a lot like the condition "sum(1/n) diverges" is likely to be close, but that's just a gut feeling.
  - RaptorJ 6y ago
    Ah well there isn't one, from any divergent series you can construct a more slowly growing (but still divergent) series.
Certhas 6y ago
So let's look at n^m. The condition is sum_n n^-m ; and that diverges for m smaller or equal 1. If you have a sequence that grows asymptotically like n^m it means that f(n)/n^m goes to a constant asymptotically. So the question is if this implies that sum 1/f(n) converges. I feel intuitively that it should be possible to prove that. A sketch: For every epsilon there is an N such that |1/f(n) - 1/C n^-m| < epsilon n^-m for n > N. So if we take the difference between the reciprocal partial sums, then that is bounded by eps * the partial sum. That is finite exactly if the reciprocal sums converge. Thus the convergence behaviour is the same for this case...
hansvm 6y ago
There can be. Let f(n) be the count of members of the set in question which are at most n. If ε>0 and f(n)=O(n^(1-ε)) then the sum of reciprocals converges. For denser sets I'd have to think a bit longer about it. It's probably also worth noting that weird density distributions are possible. E.g. one could imagine a kind of oscillation where you include enough values to get the total density up to that point up to some decreasing threshold (e.g. 1-2^-k if we've flip-flopped k times) then omit values to get below a different threshold (e.g. 2^-k if we've flip-flopped k times), and repeat the process indefinitely. The count up to a point n for this construction has the interesting property that it isn't greater in a big-O sense than the count for exponentially sparse sets while also not being less than the count for any sublinear density function in a big-omega sense (using the Knuth interpretation).
- hansvm 6y ago
  Edit: not greater than exponentially sparse sets, something a bit denser -- exponential sparsity is manageable as well, but not with the 2^-k construction I gave.

ColinWright 6y ago

I was trying to give people a sense of the statement, giving two examples of "not very dense" and "dense enough", but I don't understand what you're trying to say here. I can't work out whether you are asking a question, or making a conjecture, or ... what. Would you care to clarify? If it's a question then I'll try to answer, but if it's a conjecture, can you make it more precise?

notafraudster 6y ago
He is asking "what is the line between too sparse and not too sparse" and attempting to characterize the example you gave of each in terms of approximate relative sparsity.
- ColinWright 6y ago
  Right ... understood. I don't have an answer, it's not my area, but it does feel a lot like the condition "sum(1/n) diverges" is likely to be close, but that's just a gut feeling.
- RaptorJ 6y ago
  Ah well there isn't one, from any divergent series you can construct a more slowly growing (but still divergent) series.

Certhas 6y ago

So let's look at n^m. The condition is sum_n n^-m ; and that diverges for m smaller or equal 1. If you have a sequence that grows asymptotically like n^m it means that f(n)/n^m goes to a constant asymptotically. So the question is if this implies that sum 1/f(n) converges. I feel intuitively that it should be possible to prove that. A sketch: For every epsilon there is an N such that |1/f(n) - 1/C n^-m| < epsilon n^-m for n > N. So if we take the difference between the reciprocal partial sums, then that is bounded by eps * the partial sum. That is finite exactly if the reciprocal sums converge. Thus the convergence behaviour is the same for this case...

hansvm 6y ago

There can be. Let f(n) be the count of members of the set in question which are at most n. If ε>0 and f(n)=O(n^(1-ε)) then the sum of reciprocals converges. For denser sets I'd have to think a bit longer about it. It's probably also worth noting that weird density distributions are possible. E.g. one could imagine a kind of oscillation where you include enough values to get the total density up to that point up to some decreasing threshold (e.g. 1-2^-k if we've flip-flopped k times) then omit values to get below a different threshold (e.g. 2^-k if we've flip-flopped k times), and repeat the process indefinitely. The count up to a point n for this construction has the interesting property that it isn't greater in a big-O sense than the count for exponentially sparse sets while also not being less than the count for any sublinear density function in a big-omega sense (using the Knuth interpretation).

hansvm 6y ago
Edit: not greater than exponentially sparse sets, something a bit denser -- exponential sparsity is manageable as well, but not with the 2^-k construction I gave.