# Abstraction

#### Month: October 2016

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…

Complexity theory is a mathematical study of algorithmic problems with regard to how cost-effective solutions they have. Most prominent are the 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.