3

By "class" I mean sets of natural numbers with a given specific property (i.e. prime numbers or perfect numbers). Obviously all infinitely large sets have the same "size", but for example solitary (as opposed to friendly) numbers occur more frequently than prime numbers, because prime numbers are all solitary, but there are solitary numbers that are not prime. Perfect numbers would be a great answer to this question (because they occur so infrequently) if it were proved that there are infinitely many of them, but that hasn't happened yet.

To be clear, this question is about classes of numbers with intrinsic properties that can't be generated by a function, computable or otherwise, so infinite sets like the Fibonacci numbers, nth powers, and "the set of numbers that are in the range of the TREE function" are excluded.

If I had to make a guess without having asked this question, I might choose "the set of numbers for which π(x) > li(x)" (where π is the prime counting function and li is the logarithmic integral function), which was proved to be infinitely large a century ago but the first value of which has been proved to be larger than 10^19.

cbmanica
  • 131
  • 1
    Welcome to MSE! I am going to offer just a few critiques. "Obviously, all infinitely large sets have the same 'size.' " That sentence seems to be worth avoiding. At a minimum it's worth rewording. This isn't generically true of infinite sets. It is true of infinite subsets of the natural numbers which seems to be what your asking about. Also, I would include links to the friendly numbers and solitary numbers to make your question more accessible. I didn't know the definition of these terms. – Mason Jan 07 '19 at 01:16
  • Oh, I'm not a mathematician at all, so I'd love help rewording this so it makes more sense. I don't really know how much context the average commenter here has, it seems it may be less than I thought. I'll add some links. – cbmanica Jan 07 '19 at 01:18
  • 3
    What classes of numbers "can't be generated by a function, computable or otherwise"? How about the function $g(n)$ defined as "the $n$'th natural number in the class"? – Robert Israel Jan 07 '19 at 01:18
  • 2
    I have no idea what the second paragraph is actually trying to explain. Seems meaningless as currently phrased. You seem to have excluded everything. – Andrés E. Caicedo Jan 07 '19 at 01:19
  • 2
    It's hard to give a solid answer about "least" frequent class of numbers, as one can always (somewhat artificially) remove every second number from a given class and obtain a class that occurs "less" frequently. Also, the distinction about classes "generated by functions" is extremely artificial. Even the primes could be expressed as, say, the set of $n$ such that $n - \varphi(n) = 1$, where $\varphi$ is Euler's Totient function. – Theo Bendit Jan 07 '19 at 01:20
  • I knew I wasn't being precise enough, I just don't know how to phrase the difference between, say, perfect squares (for which you can find the nth one by applying a simple function) and, say, prime numbers (which don't have a function that generates all of them). – cbmanica Jan 07 '19 at 01:22
  • 1
    Of course there is a function that generates the prime numbers. – Andrés E. Caicedo Jan 07 '19 at 01:24
  • 2
    Yeah. So the $n$th prime number is given by whatever function does that. That is $f(n)=p_n$ where $p_n$ is the $n$th prime number is this function. What you might mean is that there isn't such a pretty algorithm that does this... (by the way there is an algorithm that does this and halts in finite time). I think you might enjoy a primer on computational complexity. I think that is probably the route you'll have to take to formalize your question. – Mason Jan 07 '19 at 01:24
  • Oh, I know a little about computational complexity. Maybe "numbers that don't have an algorithm to generate them" is what I meant. If I changed the wording to that, would it make more sense? (sorry for being such a n00b here) – cbmanica Jan 07 '19 at 01:28
  • 1
    There are algorithms that generate the primes, the Fibonacci numbers, and the values of the Tree function. – Andrés E. Caicedo Jan 07 '19 at 01:32
  • Right, if you know the first n Fibonacci numbers, you can just compute the next one, but that's not true of primes, right? (or perfect numbers, or various other kinds of numbers) Maybe repairing this question is impossible sighs sorry, appreciate all the comments in any case – cbmanica Jan 07 '19 at 01:35
  • 1
    Those particular subsets of the natural numbers are "recursive" or "computable" or "decidable." so the way you have currently phrased the question it seems like you are not quite asking what you want to be asking but the comments may help you nonetheless. My point is that you can still learn stuff by asking irreparable questions. – Mason Jan 07 '19 at 01:41
  • 1
    And I have, so thanks to everyone who's commented! – cbmanica Jan 07 '19 at 01:44
  • 1
    "but that's not true of primes, right?" No, that's not right. Given any number, you can always compute the next prime. – Andrés E. Caicedo Jan 07 '19 at 01:46
  • (I didn't know that, so thank you!) – cbmanica Jan 07 '19 at 01:47
  • This sounds as though it ought to be fundamentally unanswerable: eg because their definition or impossible to prove self consistent or something. – timtfj Jan 07 '19 at 02:54

1 Answers1

5

What a fun chain of comments you have; allow me to add some insight that is probably too large to be a comment itself.

The phrase "least frequently" that you used could possibly be best interpreted to refer to the natural density of your class of naturals. This is probably the first and most natural idea that everyone comes up with when forced to pin down the intuitive idea that "there are twice as many natural numbers as there are even natural numbers".

There are some problems with this concept when it comes to your question however. For one, the natural density of a set of naturals need not exist; the upper and lower densities might not be equal. But even among those classes that have well defined natural densities, many will end up with the same density (particularly $0$) despite being more or less "rare" than others. You could of course try to generalize the notion of natural density to other types of density functions (as they do on the bottom of the page), but I think trying to define a kind of "relative density" might be easier and more naturally capture the idea of when a class is "more rare" or "more common" than another.

What might such a definition look like? Perhaps...

Let $A,B\subseteq\mathbb{N}$ be two nonempty sets (possibly finite) of natural numbers, and define $A(n)=\{1,\ldots,n\}\cap A$, $B(n)=\{1,\ldots,n\}\cap B$, $a(n)=|A(n)|$, and $b(n)=|B(n)|$.

The upper relative natural density of $A$ to $B$ is then defined to be: $$ \overline{rd}(A,B)=\limsup_{n\rightarrow\infty}\frac{a(n)}{b(n)} $$ The lower relative natural density of $A$ to $B$ is then defined to be: $$ \underline{rd}(A,B)=\liminf_{n\rightarrow\infty}\frac{a(n)}{b(n)} $$ The relative natural density of $A$ to $B$ is (if it exists) then defined to be: $$ rd(A,B)=\lim_{n\rightarrow\infty}\frac{a(n)}{b(n)} $$

With these definitions you recover normal natural density arguments when $B=\mathbb{N}$, but you can also make meaningful distinctions between the "rarity" of classes of numbers like $A$ being the set of primes and $B$ being the set of primes of even index. Both have natural density $0$, but "clearly" it is also the case that primes are "twice as common" as primes of even index.

If you want to run with these ideas, we can then definitively answer your original question; there is no such thing as the least frequent infinite class of natural numbers. I can always cut my sets finer and finer to get more and more rare, and I can even make this idea rigorous through the use of these relative density arguments.

ItsJustCountingBro
  • 51
  • 2
  • As a final remark, this argument will resolve the question regardless of which classes of natural numbers finally pass muster. Right now it is unclear what the OP wants to count as "intrinsic", but there are only two cases to consider: if it ends up that no subsets of naturals are "intrinsically defined", then the problem is vacuous. If there is at least one set $A$ which fits the bill, there are infinitely many; order the elements of $A$ in increasing order and then take subsets of odd and even indices. At least one of these must also be "intrinsic", and we can repeat ad infinitum. – ItsJustCountingBro Jan 07 '19 at 04:07