Comment by nilkn | Hacker News Reader

Comment by nilkn | Hacker News Reader

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 both addition and multiplication, and every number has an additive inverse. And as with integers, if you divide one by another, you don’t always get a third, so the notion of divisibility makes sense too. That means that we could if we wanted try to define a notion of a “prime” number of the form a+b\sqrt{-5}.

He skipped over the fact that the positive integers are well-ordered by < (and in fact < also respects the arithmetic operations on the positive integers as well). I just can't take the comparison seriously without this being explicitly discussed, because the ordering of the integers is incredibly fundamental to human intuition about them.

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.

> 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.

I don't think it's fair for you to make assumptions like this about me. I have a degree in mathematics and have a fair amount of experience with this stuff. I certainly do not have the same level of experience as Gowers, but the odds are very high that you don't either.

> 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.

What do you mean by "only"? You'll need to use something roughly equivalent to this, but you certainly don't have to use it stated in this precise form.

For instance, a proof has already been given in this very comment thread which does not require the Euclidean algorithm in the form in which you've stated it. It requires only a much more intuitive statement about modular arithmetic, which can be proven relatively easily using the properties I've mentioned (as was done by makomk).

If you're still not satisfied, I encourage you to read this thread:

http://math.stackexchange.com/questions/385967/origin-of-wel...

---

The other questions you've posed seem irrelevant to me. Any mathematical fact can be spun so as to make it seem difficult or counter-intuitive. For instance, I might tell you that a very simple and elementary proof of the infinitude of primes makes it obvious that

n^8+4n^7+8n^6+10n^5+9n^4+6n^3+3n^2+n

has at least three prime factors for all positive integers n. But how obvious is that to you?

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.

As for the remark at the end: you're right, it may be difficult to un-obfuscate phrased in that form, but had you phrased it "Make a table of two columns. Take the very top-most, left-most entry to be n, take every entry in the right column to be 1 plus the value to its left, and take every further entry in the left column to be the product of all previous entries in the right column. I claim the value three cells below the initial n has three prime factors (and similarly the value below that has four prime factors, etc.)", and I couldn't see why that would be the case, then, yes, this would give some real pause as to whether I could truly claim sound understanding (to the point of considering it obvious) of the reason for the infinitude of primes.

And if, analogously, the obstacle to someone seeing "the smallest positive value of the form 98X - 60Y is 2" is merely inability to factorize 98 or 60, well, that doesn't mean much. But I don't think that's the obstacle for most; I don't think people would do much better were it phrased "What is the smallest value of the form 2 * 7^2 * X - 2 * 3 * 5 * Y? (BTW, 2, 3, 5, and 7 are all prime)". And I do think, while not definitive in itself, the fact that this sort of thing is not obvious at all to people suggests we shouldn't presume sound reasoning behind uniqueness of prime factorization/Euclid's lemma/etc. is implicitly obvious either. When people claim it to be obvious, it's not because they have a dim view of the correct reasoning, seen through a glass, darkly. It's just because they're making complete logical leaps.

Here's a stumper then: why do Z[sqrt(-1)] and Z[sqrt(-3)] have unique factorization but Z[sqrt(-5)] doesn't?

Did you mean to write Z[sqrt(-2)] instead of Z[sqrt(-3)]?

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

But Z[sqrt(-3)] is not the ring of Eisenstein integers.

Regardless, the fact that Z[sqrt(-n)] is a UFD for n = 1,2 but not for n >= 3 is indeed quite counter-intuitive. But Gowers isn't asking whether it's intuitive for Z[sqrt(-n)]. He's asking about the positive integers, and the positive integers have a very special well-ordering which respects the arithmetic operations and for which humans have quite a powerful intuition.

I maintain that Z[sqrt(-n)] is more different from Z than Gowers is letting on and that if you actually look at all the differences, rather doing the opposite and trying to make it seem similar to Z, you'll quickly realize why people feel that the FTA is not very bizarre for Z but it is for Z[sqrt(-n)].

Do mathematicians actually have an answer for this? Or is it considered an open question.

There's a pretty good handle on it, in the form of the ideal class group[1].

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

https://en.wikipedia.org/wiki/Quadratic_integer#Definition

This might help.

Z[sqrt(-3)] does not have unique factorization. However, Z[w] does, where w = (-1 + sqrt(-3))/2 denotes a primitive third root of unity.

In particular,

    2 * 2 = (-1 + sqrt(-3)) * (-1 - sqrt(-3))

gives two irreducible factorizations of 4 in Z[sqrt(-3)] (you can use norm arguments in Z[w] to show irreducibility). Note that the right hand side can also be written as

    (2w) * (2w^2)

however, since w is not in Z[sqrt(-3)], the two factorizations above are distinct in Z[sqrt(-3)]. They become the same factorization in Z[w].

Edit: Another way to think about why Z[sqrt(-3)] doesn't have unique factorization is because it isn't integrally closed[1]--that is, there is a monic polynomial (ie a polynomial with a leading coefficient of 1) with coefficients in Z[sqrt(-3)] that doesn't have roots in Z[sqrt(-3)]. In particular, since w^2 + w + 1 == 0, w is a root of the polynomial x^2 + x + 1, which is monic over Z[sqrt(-3)]. It turns out that any unique factorization domain[2] is integrally closed. Since Z[sqrt(-3)] is not integrally closed, it is not a UFD.

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

[2]: https://en.wikipedia.org/wiki/Unique_factorization_domain

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.

You mentioned it as as an aside. The well ordering property is completely irrelevant.

I appreciate that you're trying to clarify my post, although I did not intend my use of parentheses to imply that the enclosed fact was not important. But I'm unclear on what your ultimate point is. It's certainly not true that well ordering is "completely irrelevant", and I think you must know that if you have the confidence to make such a bold statement, which makes me wonder why you made it in the first place. It plays a very prominent role in many proofs of these facts for the positive integers. It alone is not sufficient to establish unique factorization, but I never claimed it was.

Are you agreeing with me? Disagreeing with me? What sort of response are you expecting? I'd like to have a productive discussion about this, but you're giving me a single bread crumb to go off of here.

Reply on news.ycombinator.com