Why isn’t the fundamental theorem of arithmetic obvious? (2011) • Hacker News Board

Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)

#131

Post by schoen » Wed, Jun 22, 2016, 6:30 PM UTC

serge2k wrote: post #128

schoen wrote: post #108

Earlier quoted context omitted.

The mod-cycling-predictably property also holds for composite numbers, while I think the "can't get a number divisible by 3 by multiplying numbers that are not divisible by 3" part relies on the fundamental theorem of arithmetic! (Otherwise, how do we know that you can't get a number divisible by 3 by multiplying numbers that are not divisible by 3, yet the same doesn't hold for 4? I think that's the fundmental theor…

You could probably build that up from the peano axioms and the definition of multiplication and divisibility.

It seems a bit tricky to do so without proving the fundamental theorem along the way, given another commenter's observation that the same principle doesn't hold for divisibility by composite numbers (you can get 726=22×33, where 726 is divisible by 6 yet neither 22 nor 33 is).

Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)

#132

Post by Chinjut » Wed, Jun 22, 2016, 6:36 PM UTC

serge2k wrote: post #126

Chinjut wrote: post #94

Earlier quoted context omitted.

Who says "if it's divisible by a number, the number must appear in its factorization"? Why is that true? For example, 24 is divisible by 6, though 24 has the prime factorization 2 * 2 * 2 * 3, with no 6 to be found. "Right, but all the prime factors of 6 appear in the prime factorization of 24. If X is divisible by the prime p, then there is a unique prime factorization of X, which must include a factor of p", you ma…

> Who says "if it's divisible by a number, the number must appear in its factorization"? Why is that true? No one. If an integer is divisible by a prime then that number must appear in it's unique factorization.

Why? How do we know factorizations are unique? That is the claim under contention. That is precisely what Gowers in the original article is noting as non-obvious [but often mistakenly taken to be obvious].

If we don't already know (prime) factorizations are unique, how do we know that, if an integer is divisible by a prime, that prime must appear in every possible factorization of that integer?

"Prime factorizations are unique" is equivalent, in a straightforward way, to "If p is a prime factor of x, then p appears in every prime factorization of x". It's easy to deduce either of these from the other. But neither of these statements is obviously true.

They turn out to be true for the integers, but seeing why they are true requires an extra, not at all obvious insight (the reasoning invoked above via the Euclidean algorithm).

Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)

#133

Post by nilkn » Wed, Jun 22, 2016, 6:36 PM UTC

archgoon wrote: post #127

nilkn wrote: post #110

I know I'm going up against a brilliant mathematician and Fields medalist here, but I find this article to be unenlightening. It seems that Gowers has glossed over something about the integers that's built incredibly deeply into our intuition about them when he talks about Z[sqrt(-5)]: > These numbers have various properties in common with the integers: you can add them and multiply them, there are identities for bot…

The Gaussian integers are well ordered as well. That '<' respects arithmetic operations isn't an aside; it's the core feature.

I did mention that part for a reason. And of course if one accepts the axiom of choice then every set can be well-ordered, but that would not force every ring to be a UFD.

Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)

#134

Post by ellyagg » Wed, Jun 22, 2016, 6:39 PM UTC

jerf wrote: post #114

bluecalm wrote: post #83

Earlier quoted context omitted.

>>So why is this false in Z[ sqrt(-5) ] I don't know, I don't know what sqrt is, let alone sqrt for a negative number. It's like asking someone who made a nice geometric proof of Pitagoras theorem why it doesn't work on a 4 dimensional sphere for stuff which is kinda like triangles. It's different multiplication you are mentioning here. I can't do (1-sqrt(-5) x (1 + sqrt(-5) by putting some stones in a rectangle and…

You're approaching this with a hostile attitude, which is preventing you from understanding and/or addressing what other people are saying, and substituting (light) mockery for attempts to understand what others are saying. You're not going to learn anything or convince anybody of anything this way. The point of using the ring with the sqrt in it is to conveniently demonstrate that the FTA is non-obvious. Since it is…

But he clearly does understand, and some gentle mockery at the other side is called for when they play dumb.

I'm sure the fundamental theorem of arithmetic has a non-obvious proof. And perhaps that's precisely what a mathematician means every time they say "non-obvious". If that were all just made explicit to this general interest site in the first place, perhaps we'd have nothing to discuss.

But if we are trying to play coy here, 1+1=2 also requires a non-obvious proof to anyone not versed in formal methods. I looked a proof up:

http://mathforum.org/library/drmath/view/51551.html

I don't know how long it would take me, working alone, to come up with that proof. It's non-obvious because it took humans probably 100,000 years to come up with it, even though we've had the IQ to do it for a long time. I don't think we could agree on what constitutes a proof of it without some social aspect and convention, so non-obvious by means of proof.

But, we've been using and making predictions about the world using 1+1=2 for very much longer. That seems like a pretty worthwhile definition of obvious.

Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)

#135

Post by mnx » Wed, Jun 22, 2016, 6:46 PM UTC

hugh4 wrote: post #35

CarolineW wrote: post #30

Earlier quoted context omitted.

Of course they are more likely to believe their intuitions. They also believe that it makes no difference whether or not you swap doors in the Monty Hall problem, and don't believe that with only 23 people the odds of a shared birthday are more than 50%. To some extent, there is the problem. People trust their intuitions, and their intuitions are often wrong. That's why for some things we need proper proofs.

But proofs always come back to axioms, and on what basis do we accept axioms? That they sound intuitively right. So we've just kicked the problem upstairs a bit, we can't avoid using our intuition. Personally I'm more likely to believe 2 + 2 = 4, something I can easily check to my own satisfaction using four objects, than I am to believe the Axiom of Choice.

Well, the whole idea is to pick simple axioms, so it's harder to get wrong. And also, every successful prediction that math makes based on the axioms, is in a sense a verification of them.

Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)

#136

Post by Arnavion » Wed, Jun 22, 2016, 6:47 PM UTC

scott_s wrote: post #120

ColinWright wrote: post #86

Earlier quoted context omitted.

So what you are saying is that if you don't know what can go wrong then it's "obviously true." Let's try some other things. * If you draw a distorted circle in the plane then it's obviously true that it has an inside and an outside. * The inside is obviously contractable to a point, and the outside is obviously contractable to a plane with a hole in it. * In three dimensions if you have a distorted sphere then it obv…

Please eventually provide the answer, because I'm curious!

The correct spelling "contractible" yields useful Google results, namely that spheres in 3 dimensions (point 4) are not contractible to a single point.

Edit: ... and maybe circles (point 2) too? Not a mathematician.

Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)

#137

Post by ColinWright » Wed, Jun 22, 2016, 6:49 PM UTC

scott_s wrote: post #120

ColinWright wrote: post #86

Earlier quoted context omitted.

So what you are saying is that if you don't know what can go wrong then it's "obviously true." Let's try some other things. * If you draw a distorted circle in the plane then it's obviously true that it has an inside and an outside. * The inside is obviously contractable to a point, and the outside is obviously contractable to a plane with a hole in it. * In three dimensions if you have a distorted sphere then it obv…

Please eventually provide the answer, because I'm curious!

You have email.

Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)

#138

Post by Chinjut » Wed, Jun 22, 2016, 6:55 PM UTC

nilkn wrote: post #110

I know I'm going up against a brilliant mathematician and Fields medalist here, but I find this article to be unenlightening. It seems that Gowers has glossed over something about the integers that's built incredibly deeply into our intuition about them when he talks about Z[sqrt(-5)]: > These numbers have various properties in common with the integers: you can add them and multiply them, there are identities for bot…

Yes, but the only way in which that ordering compels the integers to be a unique factorization domain is through the fact that it allows us the Euclidean algorithm; put another way, through the fact that, for any bunch of integers, their smallest positive combination (in the sense of adding or subtracting various multiples of them together) divides all of them.

But this fact about the integers actually doesn't seem to be obvious to many people! If I were to ask "What's the smallest positive value of the form 98X - 60Y?", how many people would say "Psh, obviously it's 2"? If I were to pick three particular primes p, q, and r, and ask what the smallest positive value I could get by adding and subtracting copies of p * q, p * r, and q * r together was, how many people would see right off the bat "Oh, it has to be possible to get 1 itself, as that is their only common factor"? Not many, I suspect.

And if your magic integers-with-< intuition doesn't even give you that, then I don't think it's in any sound way giving you uniqueness of prime factorization. I think you're just back-rationalizing your sense that uniqueness of prime factorization must be obvious because you've never seen it fail and heard people talk about it a lot and so on, instead of having access to genuine grounds for certainty.

Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)

#139

Post by tel » Wed, Jun 22, 2016, 7:00 PM UTC

pflats wrote: post #96

I'm going to be a little bit contrarian and disagree. I totally see where the author is coming from, but it comes across of mathematical self-aggrandizement. I especially disagree with his interpretation of the layman's experience. They're not assuming the proof or begging the question; they have a secondary unrealized assumption that is not at all their fault. The fundamental theorem of arithmetic is "obvious" becau…

I definitely get where you're coming from, but the introduction of Z[sqrt(-5)] was just there to illustrate that proof is hard. Even if you never invoke an exotic example it's hard to have proof that FTA holds.

The simplest way to get at that perhaps is to just increase the scope. It's obvious to you that 10 and 15 have unique factorizations. You can compute them and convince yourself that nothing else would work.

It's harder to do the same for 9^87654321-1 but you could in principle. Furthermore, you believe it would work (you could, e.g., program a computer to do it and wait a few hours? days? something like that) but only basically because you see no reason for your experience with small numbers to eventually stop.

But now let me tell you about the Ackermann function and ask you about A(1000, 1000). Let's be clear, this is just a really large number, but now we're at a point where a computer couldn't write down the factorization in the lifetime of the universe. Are you still sure it's obvious?

It might at this point become more clear that "I see no reason for my intuition about small numbers to stop" is weaker than "I know this always works".

Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)

#140

Post by cousin_it » Wed, Jun 22, 2016, 7:01 PM UTC

evanpw wrote: post #118

Every one of the bad arguments that Gowers points out have been made in this thread full of smart people, even after everyone read the article. I think that's pretty good evidence that the theorem really isn't obvious.

I've kinda stopped believing that high intelligence always leads to high quality discussions. Every HN thread about math or physics has many misguided comments, coming from people who are probably very smart in their own fields. I've seen that on LessWrong too, really smart math/CS people talking about biology can get demolished by a second year biology student. Noticing my own cluelessness about a topic is a very subtle skill, it took me years to learn and I'm probably not there yet. Sometimes I even feel that math/CS education has damaged me in some ways, made me too arrogant, though obviously it gave me a huge advantage in other ways.