On a site, someone asked which number is most interesting and I answered, "Every number is interesting. Give me a number and I shall tell you why it is!".
Now not going into philosophical arguments about validity of my answer, I believe in it firmly, as it can be "proved" too. Let uninteresting positive integers exist, then there must be a smallest uninteresting number. But that would be a very interesting number which is a contradiction!
Question: Is this argument valid? Can we really say that every integer is interesting?
Clearly, "interesting" should be defined here. This is somehow a very vague notion, but it seems likely that some people already worked on the problem. This leads to the following question:
Question: Is there a commonly accepted and formalized notion of "interesting integer"?
Now, some guy took it literally, and gave me the number $373857714078$ as a challenge!
Anyways, I am having a hard time finding something interesting about it, but I am sure there is something somewhere, but then, I am not Ramanujan either. I know it is a very tough question to ask, but maybe someone can hit it!
Here is a start, Prime factorization of $373857714078=2\times 3\times 62309619013.$
Answer
(Let uninteresting positive integers exist, then there must be a smallest uninteresting number. But that would be a very interesting number which is a contradiction!)
This argument has two problems, one of which is mathematical and one of which is linguistic. The linguistic problem comes from ambiguity in the word "interesting." It's a variant of the Sorites paradox, which can be phrased as follows:
Suppose heaps of sand exist. Then there must be a smallest heap of sand. But if I remove a grain of sand from a heap then it doesn't stop being a heap; contradiction!
The mathematical problem remains even after you try to formalize the definition of "interesting." One possible formalization is the following:
Definition: A number is interesting if it has a short description; more formally, if it has low Kolmogorov complexity relative to its size, meaning that it can be printed by a short computer program.
As a simple example, $2^{1000}$ is interesting because it can be printed by a very short computer program (in fact just a for loop) relative to its size (1001 binary digits). Of course I haven't told you what "short" means, but everything I'm about to say goes through for various values of the word "short"; for example, "short" might mean a program less than a tenth as long as the number of binary digits.
With this definition it's actually quite clear that most numbers are uninteresting, since most numbers can't have short descriptions; this is just a straightforward counting argument. Intuitively, the reason that most numbers are uninteresting is that most numbers are noise: they behave as if they were random strings of digits ("high Kolmogorov complexity" happens to be an excellent definition of what it means for a particular string to be "random"), and don't have any human-comprehensible structure.
Now the original argument becomes a variant of the Berry paradox, which can be phrased as follows:
Suppose there is a smallest positive integer definable in less than eleven words. Then that positive integer is "the smallest positive integer definable in less than eleven words," which is a definition involving ten words; contradiction!
It's good to spend some time thinking about how to resolve this paradox, so let me give you some space to do that before telling you what the answer is.
The resolution of the paradox is that it is a proof by contradiction: what it proves, more or less, is that a formal language for writing down descriptions of positive integers cannot be powerful enough to write down self-referential statements that quantify over its own descriptions of positive integers.
In other words, the problem with "the smallest positive integer definable in less than eleven words" as a definition is that the word "definable" is ambiguous: once you disambiguate it, it necessarily refers to a notion of definition which does not, and in fact cannot, include "the smallest positive integer definable in less than eleven words."
No comments:
Post a Comment