The goal of this blog post is to provide a novel proof of the following result:

**Proposition:** Let \(A\) be a finite set and let \(B\) be a subset of \(A\). Then \(B\) is finite.

The goal of this blog post is to provide a novel proof of the following result:

**Proposition:** Let \(A\) be a finite set and let \(B\) be a subset of \(A\). Then \(B\) is finite.

In this post a proof of the following theorem is going to be sketched, following the treatment in Borevich and Shafarevich’s *Number Theory*. This sketch is by no means meant to be highly detailed and I am writing it mostly for my own purposes, so I avoid proving some things, even if they aren’t that straightforward.

**Thue’s theorem:** Suppose \(f(x,y)=a_0x^n+a_1x^{n-1}y+\dots+a_ny^n\) is a binary form which has degree \(n\geq 3\), is irreducible (i.e. \(f(x,1)\) is an irreducible polynomial in \(x\)) and \(f(x,1)\) has at least one nonreal root in \(\mathbb C\). Then for any nonzero integer \(c\) the equation \(f(x,y)=c\) has only finitely many integral solutions.

**Proof:** Suppose otherwise…

*Number Theory* by Borevich and Shafarevich. The point of this post is for it to be somewhat expository, so it will avoid the longer proofs, sometimes just sketching the ideas.

*decision problems*, which are yes-no questions for which answer depends on some further input, for example, “Is \( n\) a prime number?” is a decision problem depending on the input \( n\). I assume that a reader of this post has some familiarity with the basic concepts of this theory, in particular, what PSPACE complexity class is and what does it mean that a problem is PSPACE-complete. A well-known theorem due to Shamir states that the class PSPACE and another class, IP (which I explain below, since I wouldn’t count it as a “basic” concept), are equal. The goal of this post is to prove this theorem. It is not based on a single source, but there is a very detailed exposition due to B.J. Mares, which I shall leave as a reference.

Warning to PROMYS students: this blog post contains major spoilers regarding problems 4 and 6 of the Open Door Problem Set. Read at your own risk.

The following problem has appeared as problem P3 on the short exam #2 during PROMYS Europe 2016:

Let \(p,n\in\mathbb N\) with \(p\) prime. How many irreducible polynomials of degree \(n\) are there in \(\mathbb Z_p[x]\)?

In part upon request of one of my friends, below I am typing up, verbatim (apart from minor typos), a solution which I have written down during the exam, between the following two horizontal lines. Below I am adding further explanations and comments, for anyone interested.

This post is based on Marcus’s *Number Fields*. More specifically, it is based on a series of exercises following chapter 4.

Recall the definition of the intertia group of a prime \(\frak P\) in \(\mathcal O_L\) lying over a prime \(\frak p\) in \(\mathcal O_K\) (\(L/K\) is a Galois extension of number fields) – it’s the set of all \(\sigma\in G=\mathrm{Gal}(L/K)\) such that, for all \(\alpha\in L\), we have \(\sigma(\alpha)\equiv\alpha\pmod{\frak P}\). We now generalize this group.

**Definition:** In setting as above, we define the \(n\)*th ramification group* \(E_n\) to be the set of all \(\sigma\in G\) such that \(\sigma(\alpha)\equiv\alpha\pmod{\frak P^{n+1}}\). The groups \(E_n,n>1\) are called the *higher ramification groups*.

*Number Fields*.

**Alice:** Fine, but I want to move first.

**Bob:** What? This is my game!

**A:** Precisely! I’m sure you have figured out the strategy to win by now, so let me at least enjoy the game for a little bit.

**B:** Alright, fine. Are you sure you’ve got all the rules?

**A:** It’s not like there are too many of them.

**B:** So we first agree on the number of moves \(q\) and another number \(p\).

**A:** Sure enough. Then I choose a number \(x_1\) and take its square…

**B:** …then I choose another number \(x_2\) and add its square to yours…

**A:** …and we just keep adding squares, summing \(q\) of them in total.

**B:** That’s right, and you want to prevent the total sum from being a multiple of \(p\).

**A:** It doesn’t sound like a very exciting game, I don’t really think I want to play it.

**B:** Really? Not even once?

**A:** I mean, that’s just adding numbers! And after all, shouldn’t we be sending encrypted messages to each other or something instead of playing games?

**B:** You know, cryptography can be a bit like a game as well… either way, I just wanted to do something else for one. What should I do with the game now? Just forget about it?

**A:** If you care about your game so much we can try to work something out with it *without* playing it.

Powered by WordPress & Theme by Anders Norén