Hacker News new | past | comments | ask | show | jobs | submit login
Proving the fundamental theorem of arithmetic (gowers.wordpress.com)
53 points by justinhj on July 18, 2016 | hide | past | web | favorite | 10 comments

Just saw Gowers yesterday in the first row of a conference talk given by Peter Scholze about perfectoid spaces. I left after 10 minutes as I was lost after 5 minutes :-)

In my opinion conference talks are just not the right way to spread mathematical knowledge, except if you are deep into the subject matter. That can be seen because after the talk, there is usually just 1 question (maybe 2 questions), out of politeness. Blog articles like this have a much bigger impact!

It helps that the fundamental theorem of arithmetic is a significantly more approachable topic than perfectoid spaces :)

Which step in the proof succeeds on the integers, but fails when applied to the ring of {a + b*sqrt(-5)} ?

Bezout’s theorem fails in that ring.

The particular proof given of Bezout's theorem here uses the fact that modding out the ambient ring by one of its prime (in the sense of not further factorable) elements yields a resulting ring with a prime (in the sense of not further factorable) cardinality, and therefore no nontrivial additive subgroups.

However, in the ring Z[sqrt(-5)], there are irreducible elements such that modding out by them produces a ring with non-prime cardinality; for example, 2 is irreducible in this ring, but there are 4 values mod 2 in this ring. 4 is not a prime cardinal, of course. Thus, the provided proof of Bezout's Theorem can and does fail in this context. [Indeed, if we look at the range of multiplication by 2 on this particular additive group of size 4, we see that it is neither trivially of size 1 nor trivially of size all 4. It is an intermediate subgroup of size 2, which can exist because 4 has an intermediate factor of 2]

The provided proof works in the integers because integers can be lined up with cardinals so that A) integer arithmetic mod n has cardinality corresponding to n, and B) also, factorizations or lack thereof for an integer are the same as for the corresponding cardinal. This ensures that integer arithmetic mod a prime integer has a prime cardinality. This fails in other contexts.

[The proof of Bezout's theorem provided, incidentally, is not my favorite because it generalizes so very little. A nicer proof of Bezout's theorem, in my mind, is via the Euclidean algorithm, which then generalizes to all Euclidean domains (and, with minor modification, slightly beyond those as well, to principal ideal domains axiomatized in a manner analogous to Euclidean domains)]

How do you define "prime cardinal" without relying on the definition of prime numbers? "Prime" (as distinct from irreducible elements) doesn't have a clear meaning before you prove the Fundamental Theorem of Arithmetic, does it?

I defined it in the relevant way in the post you're responding to (indeed, inbetween the very words "prime" and "cardinal" where I first invoke the concept): the relevant notion is of a cardinal which can't be factored as the (Cartesian) product of cardinals other than 1 and itself. [Yes, people often call this concept "irreducible" instead, but I used "prime" for convenience, and explicitly described what I meant by that.]

This is the concept that is relevant to the provided proof: Gowers argues that, if a group's size is an unfactorable cardinal, then, by Lagrange's Theorem (which tells us |G'| divides |G| whenever G' is a subgroup of G), it has no intermediate subgroups. Thus, if the additive group mod whatever has size an unfactorable cardinal, then every homomorphism into it is either constantly identity or surjective (as its range is a subgroup); accordingly, multiplication by any non-identity element would have to be invertible (modulo whatever), which is the desired instance of Bezout's Theorem.

Thanks for clarifying. I was trying to be careful about understanding meaning since the OP was all about not taking obvious things for granted.

It kind of depends on how you define prime numbers.

Usually, one says an element p of a general ring is prime if p|ab implies p|a or p|b. This property does not necessarily hold for the "smallest" divisor of a given element of your ring, as used in proof 1.

On the other hand, you might be interested in irreducible elements, i.e. those p for which a|p implies a = 1 or p, up to a unit (i.e. a divisor of 1). In fact, you can write any element of your ring as a product of irreducible elements, but not uniquely, not even uniquely up to units. In other words, you can have irreducible elements a, b, c, d, such that ab = cd, but none of them divides any of the others.

Denoting {a + b sqrt(-5) for a, b integers} by Z[sqrt(-5)], it's worth pointing out that you can actually use the norm to get a bit of the FTA--namely that every nonzero nonunit factors into irreducibles. By x being "irreducible", I mean that x is a nonzero nonunit element of Z[sqrt(-5)] and whenever x = yz for y,z in Z[sqrt(-5)] then either y or z is a unit.

So, denoting x = a + b sqrt(-5) in Z[sqrt(-5)], we define the norm[1] of x as follows:

    N(x) = a^2 + 5b^2
Note that, in this case, N is a function from Z[sqrt(-5)] to the natural numbers.

For x, y in Z[sqrt(-5)], it turns out that the following properties of the norm hold (proving them is fairly straightforward, as it's essentially "plug-and-chug" combined with a bit of reasoning about how things work in the natural numbers):

1. N(xy) = N(x)N(y)

2. N(x) = 0 if and only if x = 0

3. N(x) = 1 if and only if x = 1 or -1 (ie x is a unit).

So, if x is a nonzero nonunit that isn't irreducible, then we can, by definition, write x = y*z where y and z are also nonzero nonunits. Applying strong induction via the norm, we can show that x can be written as a product of irreducibles. Of course this product is, in general, not uniquely determined.

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

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