Ytukyg

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.

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,Bsubseteqmathbb{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_{nrightarrowinfty}frac{a(n)}{b(n)}
$$
The lower relative natural density of $A$ to $B$ is then defined to be:
$$
underline{rd}(A,B)=liminf_{nrightarrowinfty}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_{nrightarrowinfty}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.