Month: October 2016

Proof sketch of Thue’s theorem

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…

Read More

Abstract divisors

The goal of this blog post is to provide an overview of the general theory of divisors, as described in a book 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.

Read More

IP=PSPACE

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.

Read More

Powered by WordPress & Theme by Anders Norén