[svat]

The word “most” is indeed not very surprising if taken to mean >50% (as you do), but the surprising fact (admittedly not relevant for 2^64 in the quoted sentence) is that “most” can be replaced with “almost all” in the technical sense meaning “tending to 1” i.e. “1 - o(1)”, i.e. “eventually greater than 1-epsilon for any epsilon”.

Here's the multiplication table up to 9 (so for n=10 in place of n=2^64), and it already contains only 37 distinct products among its 100 entries:

     × |  0  1  2  3  4  5  6  7  8  9
    ---+------------------------------
     0 |  0  0  0  0  0  0  0  0  0  0
     1 |  0  1  2  3  4  5  6  7  8  9
     2 |  0  2  4  6  8 10 12 14 16 18
     3 |  0  3  6  9 12 15 18 21 24 27
     4 |  0  4  8 12 16 20 24 28 32 36
     5 |  0  5 10 15 20 25 30 35 40 45
     6 |  0  6 12 18 24 30 36 42 48 54
     7 |  0  7 14 21 28 35 42 49 56 63
     8 |  0  8 16 24 32 40 48 56 64 72
     9 |  0  9 18 27 36 45 54 63 72 81

That is, in decimal, only 37% of (up to) two-digit numbers can be written as products of two one-digit numbers. This fraction, which drops to 28% at n=100, only drops to 17% at n=2^64 (per the article). So it decreases VERY slowly, and it's nontrivial that it actually goes to 0.

[Dylan16807]

It's an interesting fact, but it's weakened a lot by happening so slowly and not matching the everyday definition of "almost all".

And it's weakened even more by realizing that while you can get the raw fraction as low as you want, shrinking your list of products by n digits requires numbers with an exponential number of digits.

[svat]

I think your second paragraph is the same as “so slowly”, just quantified. And I'd argue that the technical meaning of “almost all” does match the everyday definition: if you told someone that “for sufficiently large N, almost all 2N-bit numbers are not the product of two N-bit numbers”, they'd probably think of “almost all” as a fraction like 99.99% or 99.999999% or whatever, and whatever fraction they picked, the statement would be true (with the threshold for “sufficiently large” depending on the fraction they picked).

So whether “only 17%” is interesting or not depends on whether you see it as a stand-in for “less than half”, or “a number close to 0”.

(Posting this comment mainly to correct an error in my previous comment: in both places that I wrote “n=2^64” I should have instead written “n=2^32”.)

[Dylan16807]

> if you told someone that “for sufficiently large N, almost all 2N-bit numbers are not the product of two N-bit numbers”, they'd probably think of “almost all” as a fraction like 99.99% or 99.999999% or whatever, and whatever fraction they picked, the statement would be true (with the threshold for “sufficiently large” depending on the fraction they picked).

I think people would agree with that, yes. But that's a significantly weaker claim than your original one. The original version was "tends to 1 at large n" = "almost all", but this version is that once you reach large n it's "almost all". These different tests give completely different answers for the numbers you'd ever actually use.

And entirely separate from that, if you laid it out as "for 8 million* digit numbers, only one in a billion are products of 4 million digit numbers, so only enough to fill out 7,999,991 digits", I don't know if that really qualifies for "almost all" anymore. The fraction of hits is important, but so is the fraction of digits and entropy, and as you make the numbers bigger you approach 0.0% loss of digits and entropy.

* Placeholder number, I did not do the actual calculation here.