Hacker News new | past | comments | ask | show | jobs | submit login

Oh, don't worry; the "you" in "I think you're..." was generic (for anyone who claims complete and utter obviousness of unique prime factorization without ability to explicate the reasoning behind it or even grasp that reasoning might be required) and not targeted at YOU per se; I'm not accusing you of lacking mathematical sophistication. It was clear from your other comments that you have significant background in mathematics.

I'm just accusing you of being misguided when claiming that humans are able to access uniqueness of prime factorization as obvious because of special inbuilt integers-with-< intuition. I acknowledge that you clearly know perfectly well the sort of reasoning Gowers and I would claim is necessary to soundly claim understanding of UPF, but you seem to feel this reasoning is something people are actually implicitly aware of when considering UPF obvious, and I think that is erroneous.

That is:

Sure, all you need is that, in arithmetic modulo a prime, nonzero values are closed under multiplication.

But this fact is not obvious! The only reason to believe this is via, implicitly or explicitly, the reasoning that tells us how to compute GCDs as linear combinations (what I have referred to as "the Euclidean algorithm" for shorthand, though I do not mean to fixate on any particular presentation of such reasoning).

Here is makomk's argument: "Brief outline of an argument: suppose nm = 0 mod p (p prime) and m != 0 mod p. We can write this as n(ap+b) = 0 mod p for some integers a, 0<b<p, and trivially nb = 0 mod p. So there is some smallest b', 0<b'<p for which nb' = 0 mod p. We can also see nb'r = 0 mod p for all integers r. Find the smallest r for which b'r >= p. If b' != 1, then since p is prime b'r != p and we get a smaller b'' := b'r-p for which n*b'' = 0 mod p, a contradiction. Therefore b' = 1 and n = 0 mod p."

That is good, that is fine, that is the sort of argument one needs. But I would not consider that to be at all "obvious" in the way laypeople often claim UPF to be. It takes some insight or work to see the possibility of that argument! There's no reason to consider that sort of argument as deep-in-our-bones obvious, implicit to laypeople by basic intuition about integers-with-<. There are myriad quite closely related facts about integers-with-< that laypeople have no awareness of, so why should we consider the reasoning in this particular case to be built-in? Especially when calls to make such reasoning explicit fail entirely.

(FWIW, makomk's argument is also closely related to the following natural algorithm for computing the gcd of A and B: starting with an initial guess x which is any combination of A and B, keep replacing x with any nonzero value among either A % x or B % x (up to negation, if you like), till eventually one cannot continue reducing x in this way; at all times, x is a combination of A and B, and one must stop by finding such a combination that divides both A and B (and is therefore their GCD). This isn't quite the Euclidean algorithm as usually presented, but serves just as well as an algorithm computing GCDS-as-combinations recursively, and makomk's argument essentially follows the structure of computing the GCD of m and p in this way)

But nevermind the full generality of GCD computation. That may be a distraction from the point I intended to make. (I phrased things in terms of this because it was the easiest wording, but that's not quite what I'm concerned about). Even just the special case of this reasoning used by makomk is not something "obvious". I do not believe the layperson who claims UPF to be obvious has an argument like makomk's latent in their head. I think they are just making unjustified leaps. I think they are, as I said, just presuming UPF obvious because they've never seen it fail and have heard it discussed so many times and so on, to the point that they can't even conceptualize that any further reasoning could be called for.

As for "using the properties I've mentioned", presumably in reference to the integers being a well-ordered ring: sure, being a unique factorization domain follows from being a well-ordered commutative ring where the ordering interfaces with the ring structure in the expected ways... because the ONLY well-ordered ring is the integers, and the integers are a UFD. But I still don't think the average person, when looking at uniqueness of factorization as "obvious", is accessing the reasoning that goes into this.

> As for "using the properties I've mentioned", presumably in reference to the integers being a well-ordered ring: sure, being a unique factorization domain follows from being a well-ordered commutative ring where the ordering interfaces with the ring structure in the expected ways... because the ONLY well-ordered ring is the integers, and the integers are a UFD

In my opinion, this is the heart of the issue.

Most people take the ordered structure of the integers for granted to such a degree that they won't think it's necessary to isolate it as an axiom of any attempted proof. They won't bother thinking about whether each step does or does not make use of this structure.

This means two things:

(1) they're very, very liable to produce a "proof" that appears to erroneously apply to other more exotic structures because it will implicitly make use of the structure of the integers.

(2) they're unlikely to agree that something like Z[sqrt(-5)] is "similar" in any way to Z.

Here's an example of something I take issue with from Gowers's post:

> Here’s an example of how you can use \mathbb{Z}(\sqrt{-5}) to defeat somebody who claims that the result is obvious in \mathbb{Z}. Let’s take the argument that you can just work the factorization out by repeatedly dividing by the smallest prime that goes into your number. Well, you can do that in \mathbb{Z}(\sqrt{-5}) as well. Take 6, for instance. The smallest prime (in the sense of having smallest modulus) that goes into 6 is 2. Dividing by 2 we get 3, which is prime.

From the perspective of a layperson, what's this "modulus"? Is a layperson really going to just unthinkingly agree that this is the "correct" way of finding the "smallest" prime that goes into 6 in this other ring? I seriously doubt it. I think they're going to immediately feel that there's a very natural and powerful order intrinsic to the positive integers, and the same is just not true of Z[sqrt(-5)], even if you can define a modulus or a norm. That modulus will feel arbitrary and meaningless to a layperson. It's going to immediately shoot up red flags that this is a completely different domain.

Yes, I agree that a layperson is unlikely to feel Z[sqrt(-5)] is similar to Z. That's empirically just true. On this point, we are in no contention.

But I disagree that laypeople are correct to consider unique prime factorization (or Euclid's lemma, or any such thing) for integers obvious, or have correct reasoning for it latent in their head.

You gave for example a perfectly correct argument in https://news.ycombinator.com/item?id=11957549. I disagree that laypeople have anything like that in mind when they are claiming these facts to be obvious.

The process that leads laypeople to consider these facts obvious is not based on their having any special intuitive understanding of the multiplicative structure of the integers. It's just the process of "I've never seen it fail, and I keep hearing it's true, so... yeah, how could it be otherwise? How COULD it be otherwise?", the same process that leads them awry in other cases where they draw actually wrong conclusions.

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact