11 April, 2005

MATH CHALLENGE! Find the error in this article excerpt

Since my upcoming degree will be in mathematics, I guess I should post some mathematics from time to time. Here we go.

Recently, a professor emailed everyone in the department an article that was pretty interesting in its own right, but which contained a major error. I emailed the professor, and he agreed that it was an error, but observed:

I guess that the author is taking liberties to a general audience. If he were speaking to just mathematicians, I doubt he would put it that way. Anyway, he didn't mean to be taken literally.
The professor makes a good point.

Nevertheless, since the error is on a topic that really confused me for a long time, I thought I would post an excerpt that contains the error, and you readers can try to find it. I'll provide the answer in a day or two; you can email me or leave a remark in the comments.
Last spring, two mathematicians proved that there exist strings (separated not by 210 but by other intervals) that contain an arbitrarily-long run of primes. That is, you can find a number, keep adding another number to it and get a run of primes as long as you like. Because prime numbers underlie digital cryptography and Internet security, such deep truths have become more than mere oddities.

An early discovery about the primes was that there is an infinite number of them, sprinkled "like indivisible stars scattered without end throughout a boundless numerical universe," Prof. Rockmore writes. But how infinite? Although most of us think of infinity as one big number, some infinities are bigger than others. The number of numbers divisible by 2 is infinite, and so is the number divisible by 9. But the first infinity is bigger. There also is an infinite number of squares (4, 9, 16 ...) and cubes (8, 27, 64 ...), but more primes than either.

In 1859, Riemann got an inkling of how the primes thin out as you go along the number line. The number of primes around a particular number, he knew, equals the reciprocal of (that is, 1 divided by) the natural logarithm of that number. The natural logarithm of a number equals how many times you have to multiply a number called e (about 2.718) by itself to get that number. At around one million, whose logarithm is about 13, every 13th number or so is prime. At one billion, whose log is about 21, about every 21st number is prime.
Good luck :-)

30 comments:

jack perry said...

No takers. Too bad. :-(

The problem is with the comparison of differently-sized infinities. The author is correct that some infinities are "bigger" than others. The author is incorrect that some of the sets he has listed are bigger than any that he has listed. In fact, all the infinite sets that he lists are the same size: they're the same size as that of the set of all integers. Why? In "layman's terms," because we can create an ordered list of them: {2,4,6,...} and {9,18,27,...} and we can identify each set with a "first" element, a "second" element, and so forth, without omitting a single element in either set.

In math-speak: we can create "one-to-one, onto functions" from these sets to the set of integers. The functions would be (respectively) n/2 and n/9.

Similarly with the sets of squares, cubes, and primes. The necessary function is "easily" identified for squares (square root) and cubes (cube root), but I forget offhand the correct name for the primes.

Trivia: The size of the integers is ℵ_0. (That should look like the Hebrew letter aleph, which looks a little like a capital N.)

Alessandra said...

You know, ever since I stumbled in my philosophy readings and discovered there is such a thing as infinity math (the cardinality thing, right?), I came to wonder if the concept of infinity is really sound. Can we truly conceive of the infinite? I have my doubts at this moment, but it's nothing conclusive, just something I've been wondering now and then. I don't have much time to spend elaborating on why the concept itself may be being our minds or our frame of thinking, but it doesn't sit very well with me.

Alessandra said...

mistake:
I don't have much time to spend elaborating on why the concept itself may be being our minds or our frame of thinking, but it doesn't sit very well with me.

should be:
I don't have much time to spend elaborating on why the concept itself may be beyond our minds or our frame of thinking, but it doesn't sit very well with me.

jack perry said...

We can certainly imagine things that are infinite (from the Latin: without an end). So I would say that we can "conceive" them. There is certainly an immense amout of mathematics that has been done regarding infinity. In fact, without a good understanding of infinity, one doesn't have Calculus, and Calculus must be valid in some respect, because its applications work so well in the real world!

On the other hand, I would agree that we cannot really "comprehend" the infinite. We are finite, and we can only comprehend finite things, and in fact most mathematics involves reducing questions about infinitely-sized sets (which we can't answer) to questions about finitely-sized sets (which we can).

I gotta run, but I hope that answers your question somewhat.

Alessandra said...

I was thinking along the lines of the problem that infinity is outside the scope of rational thought, or logical thought.
With infinity, everything we know does not make sense anymore.
I think we always employ this reduction to the finite as if we were still being able to handle the infinite, like fooling ourselves, but the infinite seems outside our capability of precision.

You said:
'We can certainly imagine things that are infinite (from the Latin: without an end). So I would say that we can "conceive" them.'

For example, what can you conceive as infinite?

jack perry said...

What can you conceive as infinite?

The presence, and ability, of God. The space of the universe. The sets of natural, integer, rational, real, and complex numbers, along with all sorts of vector spaces and polynomial ideals. The number of measurable distances between two points. In some respect, all these things can be conceived as infinite.

Since it was so easy to write these things, I am sure that I must have misunderstood your question :-)

With infinity, everything we know does not make sense anymore.

I don't agree. In mathematics at least, I would say that we only began to understand many things once we threw in the concept of infinity — the calculus, for example — just as we only began to understand many things once we threw in the concept of zero, or of negatives, or of imaginary numbers, or of irrational numbers, or of any of the major advances in mathematical thought.

Alessandra said...

I am having difficulty conceptualizing and articulating what I find is the problem with infinity. So I asked you this question about the examples to help me think things through. Tell me what you understand of what I've written below:

Leaving out metaphysical subjects, such as God, I think you gave other examples that have helped me conceptualize the problem. This is attempt two, I think I've been able to make some distinctions but I'm still confused. Regarding the conception/comprehension distinction:

1) To conceive - is to conceive simply to think of an idea regardless if this idea makes sense? If so, then I agree we can conceive "infinity." For example, if I say " a triangle with 4 vertixes" this is an idea, but it doesn't make sense, it's not logical. I can put words together that gramatically may be correct, but the concept itself makes no sense. We can't put together "triangle" with "4 vertixes". Or is a conception something that necessarily must make sense?

2) Let's examine the concept of infinite space. Can you actually conceive of infinite space? Is "conceiving of infinite space" simply coming up with a definition of what that is, even if the definition may not make sense or be real? Let me see if I can clarify the issue:
Take a picture of finite space. You have a region ( 3 dimensional) and it extends in all directions until it stops. Finite space is inside a larger space. Let's conceptualize with objects. You have a cube, it occupies a finite amount of space. The cube sits in a room with certain dimensions. So I think when people talk about the infinite, they fool themselves that the room is infinity, when the room sits inside another larger space region. Because visually and spacially we cannot conceive of something that extends *infinitely* in all directions. To picture visually infinite space is not possible with our minds. Your mind stops at certains limits, rational thought forces you to stop somewhere. Which is why I really appreciated what you said regarding how we reduce questions of infinity to finity and pretend we are still talking about infinity. Is this what you meant when you said we cannot comprehend infinity?

3) Take an infinite line. A person who thinks they can think about an infinite line will say the line starts here and it just goes forever. Where? To infinity. So infinity is posited as a place you can go to but that you can never reach. See the logical contradiction? If it is infinite, it doesn't stop going, if it doesn't stop going, it no longer makes sense, because places we can go to are finite.

4) Is it too complicated to explain to me what Calculus has to do with infinity? (I don't know much math).

5) "The number of measurable distances between two points."
This is an interesting example, because this I think is something that is not illogical regarding infinity.

I think what I am trying to get at is the problem of infinity applied to concrete things, such as space, and probably time.

Let me know if you have any thoughts on the above.

jack perry said...

To conceive - is to conceive simply to think of an idea regardless if this idea makes sense?

I guess I can agree with that definition, although I think the notion of "infinity" makes perfect logical sense. A triangle with 4 vertices is self-contradictory, whereas an infinite number (="unbounded" number) of galaxies is not.

So I think when people talk about the infinite, they fool themselves that the room is infinity, when the room sits inside another larger space region.

I don't agree with this image of infinity. Imagine infinite space this way instead: a comet is ejected from our solar system, and proceeds outward from the galaxy without ever encountering another galaxy or other object. Assume it continues traveling and never meets another object. Assuming this is possible (which, due to gravity, it probably would not be), the space it could travel would be infinite.

Because visually and spacially we cannot conceive of something that extends *infinitely* in all directions. To picture visually infinite space is not possible with our minds.

There appears to be an assumption what you're saying: that what we know is only what we can imagine. I disagree with that assumption.

Which is why I really appreciated what you said regarding how we reduce questions of infinity to finity and pretend we are still talking about infinity. Is this what you meant when you said we cannot comprehend infinity?

I didn't use the word "pretend". :-)

We can say something about infinite sets, because we know characteristics of all the elements of these sets. These characteristics constitute a finite amount of knowledge. Then we reason on these characteristics.

For example: all even numbers are divisible by 2. Therefore, no even number is prime (except 2 itself). I have just said something about an infinite set: it is logically consistent, therefore true. However, I only used a finite number of statements.

So infinity is posited as a place you can go to but that you can never reach. See the logical contradiction?

Yes, except that infinity isn't posited as a "place" at all. The definition you give is not one that mathematicians would usually use (for example) and I don't think it's one that theologians would use, either. One can define it as a place, and in some models it is defined like that (so-called "projective space" has a "point at infinity", for example), but it's done very carefully, so as to avoid contradictions.

Is it too complicated to explain to me what Calculus has to do with infinity?

Here's an example: add 1 + 1/2 + 1/4 + 1/8 + ... (Zeno's paradox) This is an infinite number of summands; you can't find the sum if you try to add the fractions manually. Calculus provides a logical framework that finds this sum successfully (the sum is 2).

Alessandra said...

So infinity is posited as a place you can go to but that you can never reach. See the logical contradiction?

Yes, except that infinity isn't posited as a "place" at all. The definition you give is not one that mathematicians would usually use (for example) and I don't think it's one that theologians would use, either. One can define it as a place, and in some models it is defined like that (so-called "projective space" has a "point at infinity", for example), but it's done very carefully, so as to avoid contradictions.
=======================
So if it's not a place, than you can't go to it. If you can't go to it, it's no longer concrete, it's no longer real.
What is the definition of infinite regarding space?

Alessandra said...

In mathematics at least, I would say that we only began to understand many things once we threw in the concept of infinity — the calculus, for example — just as we only began to understand many things once we threw in the concept of zero, or of negatives, or of imaginary numbers, or of irrational numbers, or of any of the major advances in mathematical thought.
=======================
You see mathematics is not concrete, space is, things which are physical are concrete.

I'm not sure concrete things are the same as non-concrete things. Maybe this is what I am grappling with.

Alessandra said...

I don't agree with this image of infinity. Imagine infinite space this way instead: a comet is ejected from our solar system, and proceeds outward from the galaxy without ever encountering another galaxy or other object. Assume it continues traveling and never meets another object. Assuming this is possible (which, due to gravity, it probably would not be), the space it could travel would be infinite.
==================
But see, you've made an assumption that it would be possible for this comet to travel endlessly. Why is this assumption a reality? It's the endlessly that I have a problem with. How can something not have an end? If the comet were travelling along a path, we could potentially, by definition of what travel is (to be at a certain position at each instant), identify its position always. So how can something not end, not have a position somewhere? The definition of infinity just seems to equal a blank. You are here, then you go there and there and there and then... it's infinity, like a big blank. How can the comet not stop somewhere? To me it falls off the plane of reality and goes into the imaginary. That´s why your example of infinite numbers I can kind of handle, it's not concrete. (although I wish I knew Calculus to mathematically understand what you said :-)

To have a position is a concept that works within an identifiable finite space, not some imaginary space made on assumptions.

Does what I am asking make sense to you? Or do you think I have misunderstood something about the concept of infinity?

jack perry said...

So if it's not a place, than you can't go to it.

Correct (as long as we're in affine space).

If you can't go to it, it's no longer concrete, it's no longer real.

You're not expressing yourself well. I can't go to Pluto, but that doesn't make Pluto any less real. Now, I can say that Pluto is real because I could hypothetically go there, but that's an assumption.

What is the definition of infinite regarding space?

Unbounded. That is, there is no finite (bounded) number that describes the volume of space.

You see mathematics is not concrete...

...therefore not real? ;-)

Anyway, I don't agree. I think mathematics is very concrete. I would agree that mathematics is not material; maybe that's what you mean.

I'm not sure concrete things are the same as non-concrete things.

You have hit on an important question of modern philosophy: ideas vs. the objects they represent. Ideas do not necessarily correspond to the objects they represent, and in some cases our ideas do not even represent "material" objects, but characteristics of such objects.

But see, you've made an assumption that it would be possible for this comet to travel endlessly. Why is this assumption a reality?

Why shouldn't it be a reality? Is that any less reasonable than to assume that it can't travel endlessly when nothing is in its way? You've made no argument that would support that statement, so it would have to be an assumption. The fact that I can't experience something doesn't mean that I can't think about it, and therefore talk about it logically.

If the comet were travelling along a path, we could potentially, by definition of what travel is (to be at a certain position at each instant), identify its position always.

Correct.

So how can something not end, not have a position somewhere?

I don't understand what you're asking. To say that an object's journey doesn't end, does not at all suggests that it doesn't have a position somewhere. I could identify the comet's position at any time, and measure the distance from its stopping point. Unless some boundary (finis in Latin) obstructs the comet, it continues traveling, and those distances continue to increase. Because they can continue to increase without limit/boundary, the potential distance traveled is infinite: without boundary/end/etc.

To have a position is a concept that works within an identifiable finite space, not some imaginary space made on assumptions.

Actually, the concept of position works very well in infinite space; in fact, I think it's safe to say that it works better than in finite space. Otherwise, you have to have a boundary on position: a "furthest" position, or a "largest" distance, from a fixed point. But that doesn't make much sense, since you can always increase the distance by addition.

In any case, I would like you to name a single field of knowledge that is not based on at least one unproven assumption. The fact is that you can't: all knowledge is based on some unproven assumptions.

Or do you think I have misunderstood something about the concept of infinity?

Yes. To start with, your confusing the noun and the adjective. Infinite describes a property of an object; it is not by itself a place or size. Infinity describes neither a place nor size; it is simply the notion that something can be infinite.

Alessandra said...

Anyway, I don't agree. I think mathematics is very concrete. I would agree that mathematics is not material; maybe that's what you mean.
==========================
I understood how you used material, as in physical. So, yes, math is not physical, that's why I think it makes sense to talk about infinite things in math (like numbers and quantities, they are abstract things).

But now I don't understand your definition of concrete. What did you mean when you said math is concrete?

Alessandra said...

If you can't go to it, it's no longer concrete, it's no longer real.

You're not expressing yourself well. I can't go to Pluto, but that doesn't make Pluto any less real. Now, I can say that Pluto is real because I could hypothetically go there, but that's an assumption.
=======================
I understand what the definition of infinite material things is (unbounded), but I question that physical things can be infinite. And it all has to do with space. No material thing can be infinite in any aspect if there is no infinite space.

I'll try to think of an analogy.

Alessandra said...

I found this:
The horizon problem

OUR universe appears to be unfathomably uniform. Look across space from one edge of the visible universe to the other, and you'll see that the microwave background radiation filling the cosmos is at the same temperature everywhere. That may not seem surprising until you consider that the two edges are nearly 28 billion light years apart and our universe is only 14 billion years old.

Nothing can travel faster than the speed of light, so there is no way heat radiation could have travelled between the two horizons to even out the hot and cold spots created in the big bang and leave the thermal equilibrium we see now.

This "horizon problem" is a big headache for cosmologists, so big that they have come up with some pretty wild solutions. "Inflation", for example.

You can solve the horizon problem by having the universe expand ultra-fast for a time, just after the big bang, blowing up by a factor of 1050 in 10-33 seconds. But is that just wishful thinking? "Inflation would be an explanation if it occurred," says University of Cambridge astronomer Martin Rees. The trouble is that no one knows what could have made that happen.

So, in effect, inflation solves one mystery only to invoke another. A variation in the speed of light could also solve the horizon problem - but this too is impotent in the face of the question "why?" In scientific terms, the uniform temperature of the background radiation remains an anomaly.

13 things that do not make sense

* 19 March 2005
* NewScientist.com news service
* Michael Brooks

==================
Does this idea that the universe is expanding makes sense to you? If the universe is space, how can it be expanding? It's weird. If the universe is space, it can't be sitting and expanding inside some empty space, otherwise, the latter empty space would be the universe.
So how can the universe expand? It doesn't seem to have logic to me.

Alessandra said...

also found this:
http://instruct1.cit.cornell.edu/courses/astro101/lec31.htm

jack perry said...

What did you mean when you said math is concrete?

Yeah, that's a problem. I wrote it, and I know exactly what I mean by it, but I can't express it in words. I actually thought about that when I wrote it, and I was starting to explain, until I realized that I couldn't.

I'm thinking about it, though.

No material thing can be infinite in any aspect if there is no infinite space.

Okay, that's fine. I agree with that. In fact, I don't think most people do think of anything material as being infinite. There's a hypothesis that the universe is infinite, but as I understand it, most scientists don't believe it's true.

Does this idea that the universe is expanding makes sense to you?

Yes.

If the universe is space, how can it be expanding?

Go to a Barnes & Noble or a Borders or a public library, and take a look at the latest Scientific American. (I think it's still the latest.) They have a really good article explaining it, much better than I could here. They have a nice series of figures that show how people misunderstand the universe, and what the correct understanding is.

Alessandra said...

I'll look for the Sci Am article.

Did you mean math is concrete as in rational? following certain rational logic rules?

Like a triangle with 3 vertices is math, but a triangle with 4 vertices is not math. or 2+3=5 is math, 2+4=9 is not math.

or is it concrete in the sense that we can apply math to material things and that physical things sometimes function along math precepts or logic?

jack perry said...

Did you mean math is concrete as in rational? following certain rational logic rules?

No. I don't think there's a precise definition; it's a matter of connotation rather than denotation. For example, if I give an example of a theorem, I think of it as a "concrete" instance of the theorem. The theorem itself may or may not be concrete; that depends on how close it is to the objects we are actually studying. My field (computer algebra) can be either concrete (as demonstrated by the abundance of effective software in wide release) or non-concrete (a lot of the journal articles that come from Europe).

A lot of mathematics developed during the19th and 20th centuries was driven by a European school of thought that had little interest in "real-world" applications; as a result, mathematics became more and more abstract and esoteric. This process was driven by some very important considerations — there is only so much computation that a human can do by hand, and there were no computers — and today many of these theories are finding "real-world" applications. For example, Gauß once asserted that Number Theory's beauty lay in the fact that it had no "real-world" application; today, however, it is one of the most applied fields of mathematics in existence because of its utility in coding theory and cryptography.

The advent of computers has changed this somewhat; computers were born from mathematics, and they have made "computational" mathematics both feasible and desirable once again. So, when I speak of "concrete" mathematics; I mean computational mathematics, which is where most of the research and money is these days :-) or mathematics that has "obvious" application (either in mathematics itself, or outside the field).

Steven said...

Dear Jack,

There's another, albeit extremely subtle error in the definition of primes, which probably results from the use of quotations. Primes are not "indivisible"--they are divisible by themselves and by 1, to start with, and they are divisible by any number, the result will simply not be an integer.

And the phases (degrees, varieties) of Aleph is another problem. In addition, refering to aleph (null) as a "number" is of course technically incorrect.

shalom,

Steven

jack perry said...

Steven,

on the primes: Good eye. I wish I could say that I was blinded by the outrageous error on differently-sized infinities, but the truth is that I'm a little more flexible on writing than that, so I just didn't notice. You're absolutely right.

on aleph: Did someone refer to it as a number? maybe me? somehow I missed that.

Nevertheless, Mathworld's strict definition of a number and their discussion of cardinality seem to suggest that one could safely refer to the aleph's as (cardinal) numbers.

Do I misunderstand you? or do I misunderstand them?

Steven said...

Dear Jack,

From the original article:

"Although most of us think of infinity as one big number. . ."

It's possible that inifinity is now considered a "number" but I was always taught that strictly speaking infinity is beyond numbers--one can't get to it, count to it, or normally use it in caluculations. In a sense, it was rather like the universe the "container" of all numbers, or the largest possible set. But, admittedly, it's been a very long time since number theory, so that well could have changed--moreover, it was never a particularly strong interest for me.

On the primes thing--I write science for children, so I tend to be extremely sensitive to points that would lead to misconceptions. What confuses children often confuses adults as well. For example, most adults do not realize that pounds and kilograms are not equivalent measures. As you may know, kilograms measure mass, pounds measure force. The only reason they are (mostly) interconvertible at Earth's surface is that the acceleration due to gravitation is constant and so results in a particular mass at the surface having a certain weight.

However, we teach children all the time to convert kilograms to pounds and vice versa. When we get to advanced physics and start to talk about newtons, we've suddenly lost half the class. Hence, I tend to be very persnickety about important definitions--and primes is one of those. But as I said, it is a very subtle error and found only by those used to subtle errors and cognizant of the trouble they cause. (Don't even get me started on the misuse of the words "power" and "force")

shalom,

Steven

jack perry said...

Steven,

I follow now.

You're right that "infinity" per se is not a number, as I try to hammer into every Calculus class that I teach. My impression from the article is that the author was dancing around the reader's previous mis-impression to make a larger point, with forgivable "abuse of notation" until he got to the example. ("Abuse of notation" is common mathematical jargon, and practice.) The example, however, crossed the lines of forgivable.

On the other hand, the aleph's are considered (cardinal) numbers. I would argue that they are numbers inasmuch as they measure the size of something (infinite sets). By way of comparison, the Pythagoreans denied that the irrational numbers were numbers, either — as the story goes, they drowned at sea the member who discovered that √2 was irrational — but since they measured something necessary, there was no choice. And of course there is Kronecker's famous quote: God created the integers; all else is the work of man.

I'll try to check a set theory book sometime today & see what they have to say about it.

Yes, I do know the difference between pounds and kilograms :-) No, I don't know the difference between force and power :-( but it doesn't surprise me that there is one. In fact, I think I've had this discussion with my officemates. Can you tell me remind me of the difference?

jack

Alessandra said...

you wrote:
Here's an example: add 1 + 1/2 + 1/4 + 1/8 + ... (Zeno's paradox) This is an infinite number of summands; you can't find the sum if you try to add the fractions manually. Calculus provides a logical framework that finds this sum successfully (the sum is 2).
========
how many Calculus courses does one need to take to understand this mathematically? is this intro to Calculus or more advanced?

Steven said...

Dear Jack--

Force is easyl--mass times acceleration

Power is work per unit time. Thus power is force time distance (work) divided by time.

Thus power has two terms not directly considered by force. Although time is included as a measure of acceleration. One is measure in Newtons, the other in watts or joules/second.

So much for the physics of the day.

As for the alephs, about them as I said, my number theory is creaky. When I use aleph null I use it synonyously with infinity as we understand it normally-- let us say the infinity of integers.

shalom,

Steven

O?

jack perry said...

Alessandra,

I was thinking of second-semester Calculus (sequences and series).

However, I've seen it done in precalculus. Exactly how solid the reasoning is behind it, I'm not so sure (I don't remember the proof offhand) but I've seen it done (and done it myself). It's a classical geometric series.

jack perry said...

Steven,

I checked a set theory book today. Their definite of "number" has to do with sets (I've forgotten it now) and thus they have infinite numbers (ordinal as well as cadinal).

Steven said...

Dear Jack,

Is definite a mathematical term I have forgotten or did you mean definition. (I'm not being snarky, I just want to make sure.)

I would grant an infinity of numbers, but does that make infinity itself a number. Is that what you read the definite(ion) to mean. Just want to get it straightened out in my head. Infinity as a number I find more boggling than the concept of what it encompasses anyway. Or the Alephs as numbers, which I can readily accept as measures.

Anyway, thank you for this wonderful discussion.

shalom,

Steven

jack perry said...

Steven,

I meant "definition". :-) Stupid fingers, stupid eyes (I did preview the comment once or twice).

I will make a new blog post on the rest of your question sometime today or tomorrow. I need to go get that book & look at it anew. What I recall for certain that they defined ordinal numbers as sets: 0 is the empty set, and for any k, k+1is defined as the successor of k, where "successor" is defined in a certain way which ends up leading (naturally enough) to infinite numbers.

Details to follow. Sorry for not elaborating yet, but my mind has never been the photographic mind that my grandfather had in his youth :-(

jack perry said...

Steven,

In the meantime, you may wish to check out Wikipedia's take on infinity (I've linked to the specific discussion on "infinity in set theory", but the surrounding stuff is also good).