Why Mathematicians Can’t Find the Hay in a Haystack

http://nautil.us/blog/why-mathematicians-cant-find-the-hay-in-a-haystack

by dnetesn • 8 years ago

68 49 8 years ago

pedrocr• 8 years ago

Irrational numbers occupy the vast, vast majority of space on a number line—so vast, in fact, that if you were to pick a number on the number line at random, there is literally a 100 percent chance that it will be irrational.*

The asterisk at the end doesn't seem to lead to an actual footnote. What is meant by this? That irrational numbers are more than 99.5% of all numbers and so it rounds to 100%?

WhiteSage• 8 years ago

I would guess it means "in some sense". In a measure-theoretic sense, for example. You need to give it meaning somehow, as you cannot really pick a "random" real number with any algorithm (most real numbers are actually not even computable!).

It could also be a remark that in infinite sets 100% (in a measure-theoretic sense) does not mean all of the elements.

reacweb• 8 years ago

The chance to be irrational is 99.9999...% (99 followed by an infinity of 9). And mathematically it is the same number as 100.

mcherm• 8 years ago

Suppose that were to select one number at random from the set of integers in the range from [-1..8]. There is a 1 in 10 chance of selecting -1.

Now suppose you select from the range [-1..98]. There is a 1 in 100 chance of getting the single negative value. In the range [-1..99,998] there is a 1 in 10,000 chance. And so forth.

In the range [-1..x], as we raise x higher the chance of getting the negative value is smaller, and the higher x gets, the closer the chance gets to zero. That is what we mean when we say "the chance of selecting -1 out of [-1..infinity] is zero".

And that is precisely the sense in which the mathematical structures this article refers to (like irrational numbers, or non algebraic solids) have 100% chance of being selected when choosing a (number/solid/whatever) at random.

contravariant• 8 years ago

In statistics there's a slight difference between something that happens 100% of the time and something that always happens.

Or rather just because something has a probability of 0 doesn't mean it can't happen, events with probability 0 happen all the time.

They may also have been referring to the fact that picking a random number over the whole number line is not that as simple as it sounds since the uniform distribution doesn't exist.

JadeNB5• 8 years ago

Or rather just because something has a probability of 0 doesn't mean it can't happen, events with probability 0 happen all the time.

There is definitely a mathematical sense in which events with probability 0 can happen, but I don't know of any 'real-world' setting, e.g., in statistics, in which we correctly assign an event a probability of 0 (rather than just "too small to distinguish from 0") and yet find it happening. Could you give an example?

cygx2• 8 years ago

An idealized 'dot' has zero 'volume', as does a countable number of such dots. The bulk of the real number line is made from irrational numbers, with a countable number of rational dots mixed in.

If you define the 'probability' of hitting a rational dot in terms of ratios of volumina, it will be mathematically zero.

cygx2• 8 years ago

The footnote can be found in the original article at https://www.quantamagazine.org/why-mathematicians-cant-find-...

The reason it’s 100 percent and not 99.9999 percent has to do with the strange things that happen once you start thinking about the probabilities when infinity is involved. Around the turn of the 20th century, the mathematician Henri Lebesque helped to develop “measure theory,” which provided a mathematically rigorous way for calculating the probabilities when infinite outcomes are possible.

shoo2• 8 years ago

the same result holds if you restrict to some subset of the real line, say the closed unit interval `[0, 1]`.

although there are infinitely many rationals and infinitely many irrationals in the unit interval [0, 1], from the perspective of cardinality, there are a lot more irrationals. there are countably many rationals in [0, 1], meaning you can put those rationals into correspondence with the natural numbers 1, 2, 3, ... , but there are uncountably many irrationals in that same interval.

the quote about "100 percent chance" is probably alluding to measure theory. measure theory is used to define integration. in this 1 dimensional case of the real line, or a subset of the real line, you can think of the measure of a set being something like defining its length. the measure of the whole set [0, 1] is 1. the subset of all rationals in [0, 1] has measure zero, i.e. it has the same measure as a single point. there's no measurable length to it. not all subsets can be assigned a sensible notion of a length.

if you think of random sampling a point from the set [0, 1] according to a uniform distribution, then you have a probability of 0 < delta <= 1 of randomly sampling a point that belongs to any pre-defined subset [-0.5 * delta + x, x + 0.5 * delta] of [0, 1] . Informally, if we make delta smaller and smaller, the chance of randomly sampling a point that is arbitrarily close to x is probability delta that becomes arbitrarily close to zero. when you randomly sample from uniform distribution on [0, 1] the chance of sampling any particular pre-specified real number is probability zero. probability zero isn't the same as impossible! see https://en.wikipedia.org/wiki/Almost_surely

on another hand, despite this, the rationals are dense in [0, 1]. this means that for any real number x in [0, 1], for any (small) radius r > 0 we can find some rational y in [0, 1] that is within a ball of radius r from x, i.e. there is some rational y such that |x-y|<r. this means we can pick some sequence y_1, y_2, y_3, ... of rational numbers that become better and better approximations to the target x (which in the interesting case, x is irrational). think a sequence of decimal approximations to the target number x. despite this ability to approximate any irrational with a rational arbitrarily well, there are still a lot more irrationals, in both the cardinality and a crude measure-theoretic sense (if we delete them all it doesnt change the amount of length we started with).

The asterisk at the end doesn't seem to lead to an actual footnote. What is meant by this?

perhaps it is meant to provoke all people who like to see everything clearly defined

cokernel2• 8 years ago

Slogan: "rational numbers exist but do not take up space."

This is in a measure-theoretic sense, so literally 100% (not just 99.5%). On the number line, the measure of an interval is the (absolute) difference between its endpoints (the "length" of the interval). For any measurable set, you can approximate its size from above by covering its points with intervals and shrinking them as much as possible.

But because there are only countably many rational numbers, you can cover all of the rationals with a set of intervals with a finite total sum of lengths.

To be a bit more specific, if your rationals are r_1, r_2, r_3, ..., then for any small number e > 0, you can form the set of intervals

(r_1 - e/2^2, r_1 + e/2^2), (r_2 - e/2^3, r_2 + e/2^3), (r_3 - e/2^4, r_3 + e/2^4), ...

which have a total sum of lengths e/2 + e/4 + e/8 + ... = e and contain all of the rational numbers.

So for any positive number e > 0, the measure of the rational numbers is less than e, meaning that the measure of the rational numbers is 0.

To turn this into actual probabilities requires a little bit more work, since the measure of the number line, and hence that of the irrational numbers, is infinite, not "100%". But you could look at the probability of selecting a rational number in the interval [0, 1] and use the same reasoning as above to get a probability of 100% for an irrational number and 0% for a rational number.

enedil• 8 years ago

It's not less then even, it's exactly e.

FabHK• 8 years ago

You will pick an irrational number "almost surely" or "with probability 1". It's a somewhat counterintuitive* concept, but very well defined mathematically.

https://en.wikipedia.org/wiki/Almost_surely

[*] (For example, any individual number has probability 0 of being picked (exactly, not approximately), yet one is being picked. Or: there are infinitely many rational numbers between 0 and 1, but the probability that any one of them is picked is 0. Thus, the probability that one of the remaining ones is being picked (an irrational number), is 1.)

r41nbowdash• 8 years ago

"the proof is left as an exercise to the reader"

jerf2• 8 years ago

Another way to think of it, other than the other fine posts: Imagine you are selecting your random number by using a ten-sided die and writing down the number of each (fair) roll. Suppose you assume you are going to write down a rational number. What does that imply? It means that your fair die is going to roll some prefix, and then roll some infinitely repeating segment over and over again. As you roll the dice an infinite number of times, what is the probability that your die will ever deviate from the necessary strict repetition of the repeating segment? It is literally 100%, because no matter how many times it happens to conform to the repeating sequence, there remain an infinite number of rolls remaining in which to deviate.

If it absolutely never deviated, over the course of infinite rolls, that would itself be proof that the die is itself not a fair die. e.g., if your putatively "fair ten-sided die" rolls up precisely 1/3, by virtue of rolling an infinite series of 3s, then that would be proof that it is not in fact fair and random.

I think this helps the 100% intuition. It is simply impossible for a truly random selection process to produce a rational number.

JadeNB5• 8 years ago

As you roll the dice an infinite number of times, what is the probability that your die will ever deviate from the necessary strict repetition of the repeating segment? It is literally 100%, because no matter how many times it happens to conform to the repeating sequence, there remain an infinite number of rolls remaining in which to deviate.

While I think that accumulating as much intuition as possible is a good idea, I'm afraid that this intuition may be misleading. The problem is that there's no roll at which we can give up and say "oh well, we deviated from the pattern and aren't rolling a rational number", because we have no idea in advance when we've entered the repeating portion of the decimal expansion. That is, if we roll 0.000123456789, and then roll a 6 rather than a 1, we can't conclude that we're rolling an irrational number; all we can conclude is that, if we roll a rational number, then the repeating portion of its decimal expansion either isn't 123456789, or else hasn't begun yet.

tromp2• 8 years ago

The article points out how rational numbers are the needles amongst the hay of irrational numbers.

In a more discrete setting, we have compressible files being the needles among the hay of incompressible files. Technically; all but a fraction of 2^-k of binary strings of length n need at least n-k bits to describe, but we cannot come up with a single explicit example.

adrianN• 8 years ago

For any fixed compression scheme it's trivial to come up with files that don't compress.

baking• 8 years ago

But any file that is "trivial to come up with" is going to be easy to compress under many other schemes.

shoo2• 8 years ago

i think a dark side to "finding hay in a haystack" is the risk of building up an elegant theory for e.g. a novel calculus of hay, only to realise after some time that the set of hay is in fact empty, or is isomorphic to some other well understood and hence uninteresting structure.

joker3• 8 years ago

That's why as soon as you come up with a list of properties your hay should have, you construct an example of it.

jessup• 8 years ago

"The algebraic numbers are spotted over the plane like stars against a black sky; the dense blackness is the firmament of the transcendentals."

-- E. T. Bell

jarenstein• 8 years ago

Numberphile did a great video on this topic.[0]

[0] https://www.youtube.com/watch?v=p-xa-3V5KO8

protonfish2• 8 years ago

Which is why in computational, science, and engineering mathematics there is the concept of maximum precision. All measurements have an amount of precision and as long as the precision of how you record and calculate numbers is greater than that, the solution will be correct.

Unfortunately, this was not what I was taught in math class (science classes had to teach this separately.) This lead me (and most everyone else I communicate with) to erroneously believe that "good" math requires infinite precision. This leads to things like junior programmers losing their minds when 0.1 + 0.2 doesn't equal 0.3

vanderZwan• 8 years ago

If you've been following the devlopment of the Unum format[0], you'll know that this comes with a whole set of problems of their own.

[0] https://en.wikipedia.org/wiki/Unum_(number_format)

pjc50• 8 years ago

as long as the precision of how you record and calculate numbers is greater than that, the solution will be correct.

Well .. not quite, you have to be very aware of the kinds of operations that may result in loss of precision or error accumulation. Whether you're using floating point or longhand decimal.

Conversely algebra operates as infinite precision, allowing the safe manipulation of numbers with no finite representation.

protonfish2• 8 years ago

I'd rather do my math with a machine even though it requires finite precision. How operations affect precision is well known and not difficult to keep track of. You will only have "error accumulation," as you call it, if your desired precision is at the maximum that your computational machine can tolerate. So don't do that, and everything will work out fine.

Koshkin6• 8 years ago

Sometimes even 0.1 is not equal to 0.1.

PurpleBoxDragon• 8 years ago

This leads to things like junior programmers losing their minds when 0.1 + 0.2 doesn't equal 0.3

Junior programmers lose their mind when 0.1 + 0.2 != 0.3.

Senior programmers lose their mind trying to explain this to the business side.

yen223• 8 years ago

Truly senior programmers use integers to represent money

air7• 8 years ago

It's a nice little puzzle to prove that: Irrational number <=> Never repeating infinite decimal representation.

Koshkin6• 8 years ago

Never repeating

Meaning "non-periodic." Repetitions can occur as many times as one wishes, e.g.

  0.1230123001230001230000123...

is irrational.

QML2• 8 years ago

A more interesting puzzle is to prove or disprove whether every algebraic, irrational number is normal (in some base).

bo1024• 8 years ago

There are lots of examples of this phenomenon connected with "the probabilistic method". There the problem is to prove a certain type of object exists (there is at least one piece of hay in the stack). But it's hard to build one. So what you do is construct one randomly, then prove that on average or with high probability, your construction satisfies the requirements. This proves that at least one thing in the stack is hay, or actually that on average or most of the stack is hay.

I'm thinking of graphs, for example expander graphs; error-correcting codes; and probably lots more I'm forgetting. In these cases it then becomes a research program to construct such objects explicitly (which has a lot of history with expanders and codes).

sn41• 8 years ago

Another nice concept: normal numbers. These are numbers which have a very basic property of randomness: getting the block frequencies right. [1]

The strong law of large numbers implies that almost every number in the unit interval is normal.

Giving a simple construction of a normal, and proving that it is indeed normal, is quite difficult.

[1] https://en.wikipedia.org/wiki/Normal_number

QML2• 8 years ago

In relation to the article posted, there is a conjecture which states all algebraic, irrational numbers are normal.

08-153• 8 years ago

So much for "mainstream math". There is an alternative take called constructive algebra, which I believe to be more useful to a computer programmer. Briefly:

"There are only finitely many numbers."

That's trivially true, because numbers are man-made objects, and man has only had enough time to make finitely many of them. Integral and rational numbers can be made by writing them down, algebraic irrational numbers can be made by writing down an expression for them. (What language? Lambda calculus, obviously, because according to the Church-Turing thesis, nothing more powerful exists.)

Only countably infinitely many numbers can potentially be made this way, only finitely many will ever be made. Those non-algebraic transcendental numbers? Don't exist, because they can never be made. They may "exist" in a philosophical way, but they no impact whatsoever on the real world in which my programs operate.

Ivoirians• 8 years ago

So you can't imagine a world in which our understanding of pi or e might impact or be useful to the real world?

More broadly, you can surely imagine how the study of transcendent numbers might inform results in other fields? I don't usually try to justify math by pointing at its applications, but for example, the transcendence of pi leads to a proof that squaring the circle is impossible. Even if things aren't constructable, they can still be valuable to think about.

08-153• 8 years ago

Brilliant, just like the dimwitted TA at university who claimed full of conviction "NO amount of memory can represent pi!" Which is funny, because he represented it with a single character.

Pi and e are both algebraic numbers, there are expressions (algorithms) for both. And guys like you are funny: Faced with proof that almost all real numbers do not have a name, you immediately try to name an example.

Koshkin6• 8 years ago

numbers are man-made objects

That's plain wrong, animals can count too.

Why Mathematicians Can’t Find the Hay in a Haystack

Related Stories