If Colmin(N) is the lowest value reached by iterating the process from initial value N, Tao proved that

Colmin(N) < f(N)

for arbitrary f provided f tends to infinity, for almost all N. Here, "almost all" means something like "exceptions(N) / N, tends to 0 for large N", where exceptions(N) is the count of values that do not obey the inequality [0]

So it's an asymptotic result. The first million integers could all be exceptions - but eventually the proportion of exceptions dies out.

The ability to pick arbitrary f is very powerful. Pick the slowest-growing function you can think of. e.g. Tenfold-iterated logarithm. The inequality says for all but a negligible fraction of integers, Colmin grows slower than that function.

[0] Nitpick: I'm describing the natural density, but Tao needs the logarithmic density, where each exception n is weighted by 1/n.

Try the inverse Ackerman function instead: https://en.m.wikipedia.org/w/index.php?title=Ackermann_funct...

If non-computable functions are on the table, define f(n) to be the smallest k such that BB-k >= n, where BB-n is the n-th Busy Beaver number: https://en.wikipedia.org/wiki/Busy_beaver

Edit: looks like @tromp managed to reply before I added the bit about BB-n. :-)

Or the inverse TREE() function [1]. There's also the inverse Busy Beaver function if you don't insist on computability...

[1] https://en.wikipedia.org/wiki/Kruskal%27s_tree_theorem#TREE(...

Non-computable functions are indeed on the table as long as they tend to infinity in the limit..at the cost that figuring out when you start to hit that limit is undoubtably itself non-computable.

Actually it's a fair nitpick because logarithmic density 0 does not imply natural density 0 - so the claim in the article is misleading in more than one way.

For example, the set of numbers with a perfect square number of digits has log density 0 but natural density non-existent (inf 0 and sup 0.9). I believe it holds in the other direction though - natural density 0 implies log density 0.

If you choose giant starting numbers(like "Tree(3)"), then maybe "quite close" is 10^100.

Yes, I believe the key phrase was ”along the lines of” and Tao’s result doesn’t actually prove any particular constant bound which would indeed be a much stronger result.

You can make sense of a percentage of natural numbers with the concept of natural density: https://en.wikipedia.org/wiki/Natural_density

The natural density of a set is the limit as N goes to infinity of the proportion of the numbers up to N which are in the set.

For instance the natural density of primes, squares and cubes is 0 and the natural density of even numbers is 1/2. But all these sets are infinite so the same cardinality.

Thank you, but your last sentence is not really correct. The concept of cardinality captures different sizes of infinity. This is why I mentioned countable and uncountable infinites upfront: a countably infinite set and an uncountably infinite set do not have the same cardinality, but both are infinite.

This is not correct.

I think your basic mistake here is thinking that sizes of infinite sets has to be measured by cardinality. Yes, that's one way, but usually not the most useful way; it's a very crude measure. Its only real advantage is the fact that it doesn't need any context to work. In most cases, though, more context-dependent measures of size are more appropriate.

For instance, typically, "almost everywhere" doesn't mean "except on a subset of smaller cardinality", it means "on a subset of measure 0".

It's easy to see why you might get these confused. In many of the typical cases of measure theory -- let's say R^n with Lebesgue measure for concreteness -- you're looking at a set of cardinality 2^(aleph_0), and any countable subset will have measure 0. (Indeed, any set of intermediate cardinality will also have measure 0, if such a thing exists, although famously the question of whether it does cannot be resolved.)

But you can also have subsets also of cardinality 2^(aleph_0) which nonetheless have measure 0. E.g., in R, the Cantor set has measure 0, although its cardinality is equal to that of R itself. If a certain statement was true except on the Cantor set, we'd still say it was true "almost everywhere".

(And all this is assuming we're using "almost everywhere" in the measure sense. Sometimes it's instead used to mean, except on a meagre set, which is a different notion; but that's not the usual meaning, so someone using it that way would hopefully say what they mean explicitly.)

In the case of the natural numbers, we frequently measure sizes of subsets by their natural density. The natural density of a subset S of the natural numbers is simply the limit of |S&cap;{1,...,n}|/n as n goes to infinity (this limit is not guaranteed to exist, of course). So when talking about the natural numbers, if we say something holds "almost everywhere", typically this means it holds except on a set of natural density 0.

(Remember, math terms are heavily overloaded!)

I hear there may be some people use "almost everywhere" when talking about the natural numbers to mean "except on a finite set", but I'd consider this use confusing; if that's what you mean, just say that.

Hope that clears things up.

Edit: It turns out that Tao is actually using the logarithmic density here, not the natural density. Oy. The importance of actually reading the paper, I guess...

Thanks, this is a great comment! You've cleared things up for me a lot.

From Tao’s blog post, it sounds like the result is more in terms of things like: for almost all n<N, the maximum value of n’s Collatz orbit is bounded by extremely slow-growing functions of N (e.g. log log log log N).

Nice. This means that any resulting limit cycle will be tiny, thus hard to hit. So he actually proved that it's hard to disprove the conjecture.

Speculation only, but the method of proof might, in its key step, only bound to ~200. This is a more meaningful result to present if your reader knows that 200 is a as good as 1 because it loses nothing and also highlights something about the bound produced.