New Proof Shows Infinite Curves Come in Two Types(quantamagazine.org)
quantamagazine.org
New Proof Shows Infinite Curves Come in Two Types
https://www.quantamagazine.org/new-proof-shows-infinite-curves-come-in-two-types-20181107/
65 comments
I'm an undergrad taking some measure theory right now.
This is probably not exactly the mathematical formalism they are using, but it could be similar.
If I asked you to pick a random real number from 0 to 1, what do you think the probability is that the real number is rational? A natural way to answer this question is to try to generalize the way we say the interval from 0 to 1 is length 1 to more kinds of sets. Measure theory does exactly this, but we find out that the measure of the rational numbers is 0! This means that the probability of picking a rational number is 0. But that's clearly impossible you say, because there are an infinite number of rational numbers from 0 to 1! But in a precise mathematical way, the probability is 0.
Now a funny think I said was "pick a random real number". Since the computable numbers are also a measure 0 subset of the real numbers, it's literally impossible to randomly pick a real number with a computer...
This is probably not exactly the mathematical formalism they are using, but it could be similar.
If I asked you to pick a random real number from 0 to 1, what do you think the probability is that the real number is rational? A natural way to answer this question is to try to generalize the way we say the interval from 0 to 1 is length 1 to more kinds of sets. Measure theory does exactly this, but we find out that the measure of the rational numbers is 0! This means that the probability of picking a rational number is 0. But that's clearly impossible you say, because there are an infinite number of rational numbers from 0 to 1! But in a precise mathematical way, the probability is 0.
Now a funny think I said was "pick a random real number". Since the computable numbers are also a measure 0 subset of the real numbers, it's literally impossible to randomly pick a real number with a computer...
Yes, but that doesn't mean that there are only irrational numbers. There are rational numbers, they just have zero measure. Similarly, these curves come in more than two types - those other types just have zero measure in the probability space of the curves.
The much more interesting question is, what is the density of the rational numbers in the set of computable numbers.
Hey, non-mathematician computer science type here.
If I follow correctly, the issue with randomly picking any real number in that interval is that irrational numbers would require infinite computational steps to resolve. So the probability is really 0 that you'll get an irrational. If you have a finite number of computations, you're guaranteed to resolve to a rational, while if you have an infinite number of computations, you never resolve to anything.
Is that a decent lay interpretation?
If I follow correctly, the issue with randomly picking any real number in that interval is that irrational numbers would require infinite computational steps to resolve. So the probability is really 0 that you'll get an irrational. If you have a finite number of computations, you're guaranteed to resolve to a rational, while if you have an infinite number of computations, you never resolve to anything.
Is that a decent lay interpretation?
Uniformly at random picking a number from the interval [0, 1] isn't possible with a turing machine (even giving it access to random coins). I.e. it's not a computable function.
It doesn't even really make sense, you can't represent uncountably many numbers on a turing machine, so it isn't even possible to return all but a tiny subset of the space.
You're imagining some turing machine that attempts to compute it anyways and thinking about the output. You seem to think that you can make a turing machine that
- In the probability 0 case that we should output a rational, will output that number
- Will otherwise infinite loop
This is randomized, so we are getting our randomness from some kind of "coin flip" like process. To know that we are in the that probability 0 case of outputting a rational, we will need to have seen infinitely many coin flips. If we've seen only n coin flips, there is still 1/2^n > 0 of the probability space that we haven't explored. So in fact any such turing machine has to loop infinitely in the rational case as well.
It doesn't even really make sense, you can't represent uncountably many numbers on a turing machine, so it isn't even possible to return all but a tiny subset of the space.
You're imagining some turing machine that attempts to compute it anyways and thinking about the output. You seem to think that you can make a turing machine that
- In the probability 0 case that we should output a rational, will output that number
- Will otherwise infinite loop
This is randomized, so we are getting our randomness from some kind of "coin flip" like process. To know that we are in the that probability 0 case of outputting a rational, we will need to have seen infinitely many coin flips. If we've seen only n coin flips, there is still 1/2^n > 0 of the probability space that we haven't explored. So in fact any such turing machine has to loop infinitely in the rational case as well.
I'd say it's perfectly possible for a Turing machine + a source of randomness to generate a random real number in [0, 1). We just lazily generate more and more digits to the required precision. It's no different from, say, pi being computable.
We can even prove that there's zero probability that a rational number is generated: the decimal representation of a rational always has a repeating group of digits, but since each digit is generated randomly with 100% probability there will be no periodic pattern.
We can even prove that there's zero probability that a rational number is generated: the decimal representation of a rational always has a repeating group of digits, but since each digit is generated randomly with 100% probability there will be no periodic pattern.
See my reply here: https://news.ycombinator.com/item?id=18423881
Replace the role of Turing Machines with Type 2 Turing Machines. Then it is possible. And it's got absolutely nothing to do with computable functions.
[edit] The downvoters can't argue with facts. I am not deleting this comment.
[edit] The downvoters can't argue with facts. I am not deleting this comment.
Computers are not type 2 turing machines, nor are any other physically existing thing that we know of. They aren't really turing machines either because they have a finite tape, but since we are only interested in running the turing machine for a finite amount of time and thus accessing a finite amount of tape that distinction is unimportant.
The standard definition of computable is on a turing machine, not a type 2 turing machine. Of course we can define an alternate model where more things are computable. Edit: And the standard definition of computable is relevant because it happens to be the exact set of functions we can compute on real computers.
While Weihrauch [0] does introduce a different definition of the word computable, that would in a randomized setting allow for sampling from the interval [0, 1] (and not just for rationals as I understand it either). Any algorithm on his "oracle turing machines" will still have to take an infinite amount of time, even to return the rationals. He just allows that in his definition of computable.
[0] https://core.ac.uk/download/pdf/82440448.pdf
The standard definition of computable is on a turing machine, not a type 2 turing machine. Of course we can define an alternate model where more things are computable. Edit: And the standard definition of computable is relevant because it happens to be the exact set of functions we can compute on real computers.
While Weihrauch [0] does introduce a different definition of the word computable, that would in a randomized setting allow for sampling from the interval [0, 1] (and not just for rationals as I understand it either). Any algorithm on his "oracle turing machines" will still have to take an infinite amount of time, even to return the rationals. He just allows that in his definition of computable.
[0] https://core.ac.uk/download/pdf/82440448.pdf
Type 2 Turing Machines are a conservative model of computation. They are as realistic as Type 1 Machines. Both models involve an infinite tape. Your previous comment used the Turing Machine abstraction, so my response was entirely valid, suggesting that replacing your abstraction with another equally valid, and I believe more appropriate for this purpose, abstraction eliminates the problem.
Also, by the way, the distinction between "complete" and "potential" infinity is useful here. The Type 2 Turing Machines features only a "potential" infinity, the same type that's common throughout Theoretical Computer Science. A real number is a only a "potential" infinity -- a process of sorts. You seem to be demanding that a real number be represented as a "complete" infinity, but this isn't needed for anything in physics or engineering or anything else. The demand you're making, which would imply that an infinite amount of time is needed, is unreasonable.
And by the way, the downvoter is somebody who can't argue with facts.
Also, by the way, the distinction between "complete" and "potential" infinity is useful here. The Type 2 Turing Machines features only a "potential" infinity, the same type that's common throughout Theoretical Computer Science. A real number is a only a "potential" infinity -- a process of sorts. You seem to be demanding that a real number be represented as a "complete" infinity, but this isn't needed for anything in physics or engineering or anything else. The demand you're making, which would imply that an infinite amount of time is needed, is unreasonable.
And by the way, the downvoter is somebody who can't argue with facts.
I suppose the argument you are trying to make here is basically "having a machine that if we run it for long enough, will tell us any particular digit of a number, is as good as having that number".
In the concrete example, you would argue that if a machine which after n time steps specifies which 1/2^n sized interval the randomly generated number lies in, then having that machine is equivalent to having the randomly generated number.
I disagree. If I come up with any property of the number that requires seeing arbitrarily many digits to specify (e.g. "is rational", "contains more 1s than 0s", etc) you can never tell me whether or not the number your machine specifies has that property. That said, I can see where you are coming from. There is at least some argument that under this model it's not the number which can't be computed, but the "is rational" function.
Personally, I wouldn't worry about the downvotes. Internet points aren't important in life anyways.
In the concrete example, you would argue that if a machine which after n time steps specifies which 1/2^n sized interval the randomly generated number lies in, then having that machine is equivalent to having the randomly generated number.
I disagree. If I come up with any property of the number that requires seeing arbitrarily many digits to specify (e.g. "is rational", "contains more 1s than 0s", etc) you can never tell me whether or not the number your machine specifies has that property. That said, I can see where you are coming from. There is at least some argument that under this model it's not the number which can't be computed, but the "is rational" function.
Personally, I wouldn't worry about the downvotes. Internet points aren't important in life anyways.
> There is at least some argument that under this model it's not the number which can't be computed, but the "is rational" function.
That's how I see it. I think this perspective results in a rich and natural theory, which has helped me in my studies.
That's how I see it. I think this perspective results in a rich and natural theory, which has helped me in my studies.
What does "to have a number" mean?
A program isn't a black box. The number specified (in binary) by this program
A program isn't a black box. The number specified (in binary) by this program
emit "0."
loop forever:
emit "110"
For arbitrary turing machines, determining what they will output solves the halting problem. E.g. the following machine is pi if M' halts else 0.
simulate machine M'
emit pi
So? That's no different than a number specified in a "conventional" way, ie. by some mathematical formula in propositional logic. Let x be 0 is P if true and pi otherwise.
I'd recommend reading the relevant portions (or just all of) this paper: https://www.scottaaronson.com/papers/philos.pdf
The conventional way of knowing a number is specifying it in a way that we can quickly determine what it is and operate on it.
If I say "the next prime after 9^9^9^9^9^9^9^9^9", or indeed "the next prime after busy beaver(1000)" I have specified a precise number. But you don't think I have it in any useful sense, because I can't compute it quickly (or in my second example at all).
Edit: And it should be noted that the above is more akin to the busy beaver example, no matter how long you operate that turing machine, if M' happens to be of the sort that doesn't halt but doesn't provably not halt, then you will never be able to tell me whether the number I "have" is 0 or pi.
The conventional way of knowing a number is specifying it in a way that we can quickly determine what it is and operate on it.
If I say "the next prime after 9^9^9^9^9^9^9^9^9", or indeed "the next prime after busy beaver(1000)" I have specified a precise number. But you don't think I have it in any useful sense, because I can't compute it quickly (or in my second example at all).
Edit: And it should be noted that the above is more akin to the busy beaver example, no matter how long you operate that turing machine, if M' happens to be of the sort that doesn't halt but doesn't provably not halt, then you will never be able to tell me whether the number I "have" is 0 or pi.
It seems to me that we should have a different measure than lebesgue measure when we speak of picking numbers from an interval.
I wonder if there is a measure under which computable numbers have measure 1 while the others have measure 0. Would it have all the correct properties?
I wonder if there is a measure under which computable numbers have measure 1 while the others have measure 0. Would it have all the correct properties?
That's not necessary with Type 2 Theory. You work with the usual set of real numbers.
The opposite is true. Take the interval [0, 1], "sample a random real number x" from it. P(x is rational) = 0, P(x is irrational) = 1.
Informally, the overwhelming majority of real numbers are irrational.
Informally, the overwhelming majority of real numbers are irrational.
What's weird is there's always a rational number between any 2 irrational numbers, yet there are way more irrational numbers
All this becomes pretty intuitive if you think about numbers in terms of their decimal expansions. A "random number" is one with a random digit in each of its (infinitely long) list of decimal digits. A rational number is one where, at some finite point, all of the digits start to repeat in some finite pattern. The odds of that happening by chance are zero.
Likewise, if you take any two randomly generated list of decimal digits, at some point there will be a digit in the same place that is different between the two. At that point, you can construct a rational between the two by choosing the smaller digit and then adding "1000....".
But yeah, it's kind of weird.
Likewise, if you take any two randomly generated list of decimal digits, at some point there will be a digit in the same place that is different between the two. At that point, you can construct a rational between the two by choosing the smaller digit and then adding "1000....".
But yeah, it's kind of weird.
Corollary: rational numbers must serve double duty separating many different pairs of irrational numbers.
You can keep going with things that sound weird:
There are infinitely many rationals between any two irrational numbers.
There are as many rational numbers between any two finite irrational numbers as there are between positive and negative infinity.
You can keep going with things that sound weird:
There are infinitely many rationals between any two irrational numbers.
There are as many rational numbers between any two finite irrational numbers as there are between positive and negative infinity.
Can you clarify that last point? I don't think it's strictly true. Aside from countable and uncountable infinities, you can have larger and smaller infinites as well. Unless every set S of all rational numbers between any irrational x and irrational y is isomorphic to the set P of all rational numbers, I don't see that this is correct. And I don't immediately see that you can put them into 1-1 correspondence.
Do you agree both sets are countable? If so, any two countable sets can be put into bijection by composing their bijections to the naturals.
Oh, right. Yeah I guess that makes sense by definition.
Any infinite set is either countable or uncountable.
I'm aware, but that's not what I meant.
> If I follow correctly, the issue with randomly picking any real number in that interval is that irrational numbers would require infinite computational steps to resolve.
In mathematics, doing things an infinite number of times is generally no problem, in fact it’s almost always done.
Of course, there are also many different sizes of infinity, and doing things a larger infinite size number of times requires some extra steps... but most branches of math only do things a countable infinite number of times (the smallest infinity).
In mathematics, doing things an infinite number of times is generally no problem, in fact it’s almost always done.
Of course, there are also many different sizes of infinity, and doing things a larger infinite size number of times requires some extra steps... but most branches of math only do things a countable infinite number of times (the smallest infinity).
"Rational" numbers are those that can be expressed as a fraction of two integers. For example, a square root of two is not rational.
"Computable" numbers are those that can be calculated by a computer (with unlimited memory, but finite speed) with arbitrary (not infinite) precision in finite time. As a rule of thumb, anything you can express using words like "plus", "minus", "square root", "logarithm" etc. is going to be computable.
> irrational numbers would require infinite computational steps to resolve
No, this is not the real reason. Both "1/3" and "square root of 2" have infinite number of decimal places, so neither can be fully written by a computer program. However, each of them can be approximated to e.g. one billion decimal places.
To show you how most numbers are not rational, consider only numbers of form "A + B * square root of two", where A and B are rational. Each different pair of A and B gives you a unique number. Among them, the numbers with B = zero are rational, and numbers with B <> zero are irrational. (Furthermore, all rational numbers can be expressed like this, but many irrational numbers, such as "square root of three" are outside of this set.) This should make it intuitively obvious why a randomly picked number is infinitely unlikely to be rational.
But the rabbit hole goes much deeper.
Let's ignore all technical details, and take a set of all numbers you can describe (unambiguously, and without any paradox) by a sentence of a finite length (including any finite number of equations of a finite length). If you need a whole book to define a number, so be it. Take all numbers humans can describe.
The point is that all these numbers are just an infinite minority in the vast ocean of real numbers.
How can that be? What else is missing? This seems tricky, because -- by definition -- I should be unable to give you an example of a number that cannot be described. But even if I can't give you a specific number, I can point you towards a concept: the numbers whose decimal digits are all randomly generated.
Any number that can be described by a finite description, contains a finite amount of information. A number with infinitely many randomly generated digits contains an infinite amount of information. To put it differently, when you generate numbers with infinite number of random decimal digits, you would have to be infinitely lucky to generate a number which only happens to contain a finite amount of information (for example, when all randomly generated digits happen to be zeroes). But the former are the real numbers, and the latter are the computable numbers. So if you take a random real number, you have to be infinitely lucky to get a computable one.
There is actually more, because "infinitely more" does not adequately describe the difference between comparing "rational" with "irrational, but still computable" numbers (both infinities have the same cardinality), and "computable" with "real" numbers (infinities of a different cardinality)... but this part, I am afraid, is beyond lay interpretations and requires paying attention to some technical definitions. A simple version is that the rational numbers and the computable numbers can both be numbered by integers, if we choose a sufficiently smart numbering scheme; but for real numbers, even this is impossible. But it takes some technical details to explain why it is so, and why it matters so much.
"Computable" numbers are those that can be calculated by a computer (with unlimited memory, but finite speed) with arbitrary (not infinite) precision in finite time. As a rule of thumb, anything you can express using words like "plus", "minus", "square root", "logarithm" etc. is going to be computable.
> irrational numbers would require infinite computational steps to resolve
No, this is not the real reason. Both "1/3" and "square root of 2" have infinite number of decimal places, so neither can be fully written by a computer program. However, each of them can be approximated to e.g. one billion decimal places.
To show you how most numbers are not rational, consider only numbers of form "A + B * square root of two", where A and B are rational. Each different pair of A and B gives you a unique number. Among them, the numbers with B = zero are rational, and numbers with B <> zero are irrational. (Furthermore, all rational numbers can be expressed like this, but many irrational numbers, such as "square root of three" are outside of this set.) This should make it intuitively obvious why a randomly picked number is infinitely unlikely to be rational.
But the rabbit hole goes much deeper.
Let's ignore all technical details, and take a set of all numbers you can describe (unambiguously, and without any paradox) by a sentence of a finite length (including any finite number of equations of a finite length). If you need a whole book to define a number, so be it. Take all numbers humans can describe.
The point is that all these numbers are just an infinite minority in the vast ocean of real numbers.
How can that be? What else is missing? This seems tricky, because -- by definition -- I should be unable to give you an example of a number that cannot be described. But even if I can't give you a specific number, I can point you towards a concept: the numbers whose decimal digits are all randomly generated.
Any number that can be described by a finite description, contains a finite amount of information. A number with infinitely many randomly generated digits contains an infinite amount of information. To put it differently, when you generate numbers with infinite number of random decimal digits, you would have to be infinitely lucky to generate a number which only happens to contain a finite amount of information (for example, when all randomly generated digits happen to be zeroes). But the former are the real numbers, and the latter are the computable numbers. So if you take a random real number, you have to be infinitely lucky to get a computable one.
There is actually more, because "infinitely more" does not adequately describe the difference between comparing "rational" with "irrational, but still computable" numbers (both infinities have the same cardinality), and "computable" with "real" numbers (infinities of a different cardinality)... but this part, I am afraid, is beyond lay interpretations and requires paying attention to some technical definitions. A simple version is that the rational numbers and the computable numbers can both be numbered by integers, if we choose a sufficiently smart numbering scheme; but for real numbers, even this is impossible. But it takes some technical details to explain why it is so, and why it matters so much.
Not only that, we should expect to always get an irrational number, but always get rationals from a finite subset of Q. I recently asked a closely related question on Math.SE:
https://math.stackexchange.com/questions/2952087/sampling-fr...
https://math.stackexchange.com/questions/2952087/sampling-fr...
[deleted]
The trouble is with your definition of picking.
If the selection process involves digital steps then for sure you can ONLY pick computable numbers. But if the selection process involves some analog movement then it’s an interesting open question — my guess is that because of Planck Length, you can only pick rational numbers. So in what sense do irrational numbers or transcendental numbers or imaginary numbers exist? They are useful abstractions only.
Who was it that said “God created the integers, man invented everything else”?
If the selection process involves digital steps then for sure you can ONLY pick computable numbers. But if the selection process involves some analog movement then it’s an interesting open question — my guess is that because of Planck Length, you can only pick rational numbers. So in what sense do irrational numbers or transcendental numbers or imaginary numbers exist? They are useful abstractions only.
Who was it that said “God created the integers, man invented everything else”?
Take is why I think AI can’t have qualia. They aren’t embodiesd.
> Now a funny think I said was "pick a random real number". Since the computable numbers are also a measure 0 subset of the real numbers, it's literally impossible to randomly pick a real number with a computer...
I dispute that. See this: http://math.andrej.com/2008/02/06/representations-of-uncompu...
[edit] The downvoters can't argue with facts. Let me hear them.
I am not deleting this comment.
I dispute that. See this: http://math.andrej.com/2008/02/06/representations-of-uncompu...
[edit] The downvoters can't argue with facts. Let me hear them.
I am not deleting this comment.
That blog post was a good read.
I also wanted to say that I certainly believe that you've done real math and got interesting results from the sort of model we were discussing above. It does seem like, as you say, a rich and natural theory.
That said I wanted to make another counter argument here. Particularly based on the meaning of the phrase "pick a random real number". To pick a number at random is a necessarily randomized process, however it should give a classical output. After picking the number I should be able to make two copies of it, put them on ships flying away from eachother at the speed of light, and both ships should be able to perform the same computation (without entangling particle pairs beforehand).
Moreover any reasonable representation of a real number should admit operations like "what is its n^th digit".
Under these two constraints, you would have to flip an infinite number of coins, and it would take infinite time and space to pick a real number. Or in other words, you can't really.
I also wanted to say that I certainly believe that you've done real math and got interesting results from the sort of model we were discussing above. It does seem like, as you say, a rich and natural theory.
That said I wanted to make another counter argument here. Particularly based on the meaning of the phrase "pick a random real number". To pick a number at random is a necessarily randomized process, however it should give a classical output. After picking the number I should be able to make two copies of it, put them on ships flying away from eachother at the speed of light, and both ships should be able to perform the same computation (without entangling particle pairs beforehand).
Moreover any reasonable representation of a real number should admit operations like "what is its n^th digit".
Under these two constraints, you would have to flip an infinite number of coins, and it would take infinite time and space to pick a real number. Or in other words, you can't really.
The way your spaceship analogy works in TTE, is that the random real number would be some kind of radio source that gets listened to by the two ships. Also, the way TTE works, there are diminishing returns from listening to the radio source for longer and longer time - this is because all functions computable in TTE are continuous, and therefore have diminishing returns from knowing their input to greater and greater accuracy (this is exactly the difference between continuous functions and discontinuous functions). Therefore you only have to listen to the radio source for some time before saying "Yep, I'm happy, I know the output of my function to within epsilon". Even the value of Pi in physics only needs to be known to a small number of decimal places - which suggests that all functions that are "physically computable" are continuous, further suggesting how natural TTE is.
Again, my comments are getting downvoted by ignoramuses. This is not the first time.
Again, my comments are getting downvoted by ignoramuses. This is not the first time.
It's not accurate. Looking at the arxiv link (https://arxiv.org/abs/1702.02325), the idea is you fix some elliptic curve E, and you look at its "twists" E^d, where the parameter d is a nonzero integer.
If you only look at twists where |d| < N, you can ask "What proportion of these are rank zero, rank one, rank two, ...?" The Theorem in the paper is that as you let N go off to infinity, these proportions tend to 1/2, 1/2, 0, 0, 0, ... respectively.
Here's the thing: this does not correspond to a measure on the set of rational elliptic curves, and indeed, there is no reasonable way to define a uniform probability measure on a countable set. Consequently, statements like "half of all elliptic curves..." are kind of misleading and meaningless.
If you only look at twists where |d| < N, you can ask "What proportion of these are rank zero, rank one, rank two, ...?" The Theorem in the paper is that as you let N go off to infinity, these proportions tend to 1/2, 1/2, 0, 0, 0, ... respectively.
Here's the thing: this does not correspond to a measure on the set of rational elliptic curves, and indeed, there is no reasonable way to define a uniform probability measure on a countable set. Consequently, statements like "half of all elliptic curves..." are kind of misleading and meaningless.
To back up my last claim, let me prove that 100% of positive integers are even in the same spirit:
Fix any odd positive integer x, and consider its "twists" x{d}, which for positive d I define to be x*2^d. Every integer is of the form x{d} for a unique choice of x and d. Now, for fixed N, if I consider all "twists" for which d<N, the proportion which are even is (N-1)/N. Thus, as N tends to infinity, the proportion tends to 1.
Fix any odd positive integer x, and consider its "twists" x{d}, which for positive d I define to be x*2^d. Every integer is of the form x{d} for a unique choice of x and d. Now, for fixed N, if I consider all "twists" for which d<N, the proportion which are even is (N-1)/N. Thus, as N tends to infinity, the proportion tends to 1.
How does a twist x{d} being even equate to the integer d being even?
The twist x{d} is even as soon as d>0.
Yes, but that doesn't mean the integer d is even.
I never say anything about d being even. Rather, as soon as d > 0, x{d} is even, so "almost all" x{d} are even. As you vary x and d, you cover all integers exactly once, so from this perspective, "almost all" integers are even.
My point is that this is very similar to how elliptic curves are being counted here.
My point is that this is very similar to how elliptic curves are being counted here.
I think that the correct mathematical terminology is that almost all the elliptic curves [of this family] come in only too types. (I'm not sure that this is official.)
For a similar example see https://en.wikipedia.org/wiki/Almost_everywhere
For example, we know that almost all the numbers are normal, but we have a prof that any particular number is normal (but we have some good candidates). Moreover, we know plenty of numbers that are not normal. https://en.wikipedia.org/wiki/Normal_number
For a similar example see https://en.wikipedia.org/wiki/Almost_everywhere
For example, we know that almost all the numbers are normal, but we have a prof that any particular number is normal (but we have some good candidates). Moreover, we know plenty of numbers that are not normal. https://en.wikipedia.org/wiki/Normal_number
> we [don't] have a pro[o]f that any particular number is normal (but we have some good candidates)
https://en.wikipedia.org/wiki/Champernowne_constant ?
https://en.wikipedia.org/wiki/Champernowne_constant ?
Each Ck is normal in base k, but that is a much weaker claim than the claim without limiting it to a base. That, we don’t know (”It is an open problem whether Ck is normal in bases b ≠ k”)
Each Chaitin constant (https://en.wikipedia.org/wiki/Chaitin%27s_constant) is normal in that stronger sense, but we don’t know, and can’t know, much more about them than that they are normal numbers between zero and one.
Each Chaitin constant (https://en.wikipedia.org/wiki/Chaitin%27s_constant) is normal in that stronger sense, but we don’t know, and can’t know, much more about them than that they are normal numbers between zero and one.
I totally forgot the "don't"! Too late for editing :(. Thanks for noticing it.
[deleted]
Probability theory is based on measure theory. You can think measure as abstraction of the size of a set. As others point out in different ways, probability 1 and zero-probability don't mean exactly what you think they mean.
Simply put: it’s possible to have a non-empty set with zero "size".
Simply put: it’s possible to have a non-empty set with zero "size".
This is explained in the article, too.
The article also explains why it is OK to say that elliptic curves come only in two types. Read the two paragraphs starting from "You may be wondering how it’s possible...". It seems like the curves of rank 0 and 1 are infinite and curves of rank greater than 1 are also infinite. But infinities are strange. The infinity of curves with rank 0 and 1 is much much greater than those of rank > 1 so essentially the latter can be ignored. That's what I understood.
I agree it's confusing. If you consider a random variable X whose value is the rank of a randomly chosen elliptic curve. Then I believe this article is saying X converges in probability [1] to 50%/50%.
Similarly related is the concept of "Almost Surely" [2]. Wikipedia includes a great example with throwing a dart.
[1] : https://en.wikipedia.org/wiki/Convergence_of_random_variable...
[2] : https://en.wikipedia.org/wiki/Almost_surely#Throwing_a_dart
Similarly related is the concept of "Almost Surely" [2]. Wikipedia includes a great example with throwing a dart.
[1] : https://en.wikipedia.org/wiki/Convergence_of_random_variable...
[2] : https://en.wikipedia.org/wiki/Almost_surely#Throwing_a_dart
Yes, it’s inaccurate. The rigorous way to say it would be “Almost all ecliptic curves are one of two types” but to a layman not familiar with the technical definition of almost all it may not seem particularly impressive.
Even the phrase almost all is a bit misleading here, since there is no canonical choice of measure on the set of elliptic curves in question.
It's essentially aleph 0 / aleph 1. Aleph 1 is so much larger than aleph 0 that this equation "equals" zero.
The real problem here is that this equation doesn't really make any sense: You can't divide infinity and expect answers that make sense in ordinary language.
So you can have an infinite number of curves of rank > 1, and yet there is 0% chance you'll come across one by accident (since you'll need to sample an infinite number of rank <= 1 curves in order to do that - but of course, you can't, there's an infinite number of them).
The real problem here is that this equation doesn't really make any sense: You can't divide infinity and expect answers that make sense in ordinary language.
So you can have an infinite number of curves of rank > 1, and yet there is 0% chance you'll come across one by accident (since you'll need to sample an infinite number of rank <= 1 curves in order to do that - but of course, you can't, there's an infinite number of them).
They're not really dividing aleph_0 by aleph_1. The important thing is that it has measure 0, but you can easily have a set with cardinality aleph_1 and measure 0.
There are also no ironic quotes around "equals". The measure really is 0.
There are also no ironic quotes around "equals". The measure really is 0.
Infinity has odd properties and there are multiple infinities. See: The Aleph and Beth infinity series.
For example, the natural numbers are infinite. They are aleph-null. The ordinal numbers are also infinite. They are aleph-one. Even thought both are infinite, aleph-one has more elements than aleph-null.
This is the realm of set theory and started with Georg Cantor.
For example, the natural numbers are infinite. They are aleph-null. The ordinal numbers are also infinite. They are aleph-one. Even thought both are infinite, aleph-one has more elements than aleph-null.
This is the realm of set theory and started with Georg Cantor.
Yes, because of the way infinities work.
Even though the quantities of ranks 0/1/2+ are infinities (countable or not), there are vastly more 0/1 than any other, so that mathematically, it's accurate to say that the odds of finding 2+ are zero. But it's not really zero.
Infinity is confusing :)
Even though the quantities of ranks 0/1/2+ are infinities (countable or not), there are vastly more 0/1 than any other, so that mathematically, it's accurate to say that the odds of finding 2+ are zero. But it's not really zero.
Infinity is confusing :)
These statements are consistent modulo zero measure (probability) sets. For instance: there are infinitely many rational numbers, but the probability of picking a rational number at random from the interval [0,1] is zero.
[deleted]
Why do you think the article garnered 7 comments on its website, but 25 here on HN?
A (The?) major purpose of hn is commenting on things. People know what to expect to see in comments and what standards to apply in writing them. The major purpose of quantum magazine is writing and publishing articles about science and mathematics. Most interesting comments from experts in the field will be in the article, not the comments below. Those not quoted who have interesting things to say will probably have written or said them closer to when the preprint came out and won’t be looking for the subject to come up in a popular magazine to make their comment. I don’t think this fully answers the question
A lot of people were confused by the paper's probabilistic claim, and tried to correct each other. At the time I'm writing this comment, only one of them has done so accurately and germanely, as far as I can tell.
It's not unexpected for people to be confused when the article is stretching the truth to the breaking point.
The proof in the article states that there is a 100% chance of a random elliptic curve being either rank 0 (50% chance) or rank 1 (50% chance).
However, the article also informs us that there are an infinite number of elliptic curves with rank 2 or more. For example, the elliptic curve `y2+y=x3+x2−2x` is of rank 2.
So is it truly accurate to say that elliptic curves come only in two types?