Solving the diophantine equation x^3=y^2+2

This will be a post illustrating how unique factorization in the ring \mathbb{Z}[\sqrt{-2}]=\{a+b\sqrt{-2}: a, b\in\mathbb{Z}\} helps us solve the diophantine equation x^3=y^2+2. We first start by proving

Lemma: The ring \mathbb{Z}[\sqrt{-2}] is a UFD.

Proof. Define N(a+b\sqrt{-2})=a^2+2b^2. The identity

(a^2+2b^2)(c^2+2d^2)=(ac-2bd)^2+2(ad+bc)^2

proves that

N(a+b\sqrt{-2})N(c+d\sqrt{-2})=N((a+b\sqrt{-2})(c+d\sqrt{-2}))

So N is a multiplicative function. We claim that N is a Euclidean norm on \mathbb{Z}[\sqrt{-2}]. Let \alpha, \beta\in \mathbb{Z}[\sqrt{-2}] with \beta\neq 0. We need to show that there exist elements q, r\in \mathbb{Z}[\sqrt{-2}] such that \alpha=q\beta + r where N(r)<N(\beta). Now \alpha/\beta\in\mathbb{Q}[\sqrt{-2}], so we can write \alpha/\beta=x+y\sqrt{-2} where x, y\in\mathbb{Q}. Let m, n be the closest integers to x and y, respectively. Let q=m+n\sqrt{-2}\in\mathbb{Z}[\sqrt{-2}]. Since |x-m|\leq 1/2 and |y-n|\leq 1/2, it follows that

N(\alpha/\beta - q)= N((x-m)+(y-n)\sqrt{-2})=(x-m)^2+2(y-n)^2\leq \dfrac{3}{4}

Set r=\alpha-q\beta \in\mathbb{Z}[\sqrt{-2}]. Then \alpha=q\beta+r and

\displaystyle N(r)=N(\alpha-q\beta)=N\left(\frac{\alpha}{\beta}-q\right) \cdot N(\beta) \leq \frac{3}{4} N(\beta)<N(\beta)

as desired.

Let’s turn our attention in solving the equation x^3=y^2+2 in integers x and y. Suppose x, y\in\mathbb{Z} satisfy x^3=y^2+2. First, x cannot be even because then y^2+2\equiv (\text{mod } 4) which is impossible. So x must be odd, and as a result y is also odd. Now we have the factorization x^3=(y+\sqrt{-2})(y-\sqrt{-2}) in \mathbb{Z}[\sqrt{-2}]. We first show that y+\sqrt{-2} and y-\sqrt{-2} are relatively prime. Suppose \gamma\in\mathbb{Z}[\sqrt{-2}] divides both y+\sqrt{-2} and y-\sqrt{-2}. Then \gamma divides their difference 2\sqrt{-2}=-(\sqrt{-2})^3. If \gamma is not a unit, then \sqrt{-2} would divide \gamma. This is because \sqrt{-2} is prime: indeed, if \sqrt{-2}=\alpha\beta, then from N(\sqrt{-2})=2, we see that N(\alpha)=1 or N(\beta)=1; so either \alpha or \beta is a unit; i.e \sqrt{-2} is irreducible and hence prime because we are in a UFD. But if \sqrt{-2} divides \gamma, then \sqrt{-2} divides y+\sqrt{-2} and so \sqrt{-2} divides y. But this means y=\sqrt{-2}(k+r\sqrt{-2})=-2r + k\sqrt{-2}, i.e. k=0 and y=-2r. But then y would be even, contradiction. We conclude that \gamma is a unit.

So y+\sqrt{-2} and y-\sqrt{-2} are relatively prime. So if p is any prime that divides x, then p^3 divides x^3 = (y+\sqrt{-2})(y-\sqrt{-2}). So p^3 divides either y+\sqrt{-2} or y-\sqrt{-2}. Hence, y+\sqrt{-2} must be of the form u h^3 for some h\in\mathbb{Z}[\sqrt{-2}] where u is a unit. Since the only units in \mathbb{Z}[\sqrt{-2}] are \pm 1 (units correspond to N(u)=1) which are already cubes, we can absorb them into h^3 term. So write h=a+b\sqrt{-2} for some a, b\in\mathbb{Z}. Then we get

y+\sqrt{-2} = (a+b\sqrt{-2})^3 = a^3-6ab^2+(3a^2b-2b^3)\sqrt{-2}

As a result, y=a(a^2-6b^2) and 1=b(3a^2-2b^2). We deduce that b=\pm 1. This gives 3a^2-2=\pm 1. Clearly 3a^2-2=-1 doesn’t give any solution in integers; so 3a^2-2=1 and consequently, a=\pm 1. So y=a(a^2-6b^2)=\pm 5. Now x^{3}=y^2+2 gives x=3. Therefore, (x, y)=(3, \pm 5) are the only solutions in integers.

 

 

 

Advertisements
Posted in Uncategorized | Leave a comment

Compact space that is not sequentially compact

What is an example of a compact space that is not sequentially compact?

Let’s recall that: A space X is compact if every open cover of X has a finite subcover. And X is sequentially compact if every sequence in X has a convergent subsequence.

When X is a metric space, these two conditions are equivalent (which is already interesting!). But I want to talk about a really cool example of a topological space which is compact but not sequentially compact.

Let X=[0, 1]^{\mathcal{P}(\mathbb{N})} where \mathcal{P}(\mathbb{N}) is the power set of \mathbb{N} (i.e. \mathcal{P}(\mathbb{N}) is the set of all subsets of the positive integers). One can think of the space X in two ways: The formal way is to think of X as the set of all functions \mathcal{P}(\mathbb{N})\to [0, 1]. Or, we can simply say X is the space of all infinite tuples, all of whose entries are coming from [0, 1]. Of course, the infinite tuple will have uncountably many coordinates (namely the cardinality of \mathcal{P}(\mathbb{N})).

In any case, the space X is compact by Tychonoff’s theorem. However, let’s show that X is not sequentially compact. For this, we need to construct some sequence \{a_n\}_{n=1}^{\infty} which does not have a convergent subsequence. The idea comes from the sequence \{(-1)^{n}\}_{n=1}^{\infty} in \mathbb{R} which does not have a convergent subsequence. In order to construct the sequence \{a_n\}_{n=1}^{\infty} in X, we need to specify \mathcal{P}(\mathbb{N})-many coordinates for each a_n. Essentially we want to fill out a grid of dimension |\mathbb{N}|\times|\mathcal{P}(\mathbb{N})|:

a_{1} \ \ \ \        * * * * * * * * \cdots
a_{2} \ \ \ \        * * * * * * * * \cdots
a_{3} \ \ \ \        * * * * * * * * \cdots
\vdots \ \ \ \ \ \ \ \vdots \ \ \vdots \ \ \vdots \ \ \vdots \ \ \vdots \ \cdots

The idea is to fill out the grid column by column! (It would seem more natural to fill the table row by row, since filling out n-th row exactly corresponds to specifying an element a_{n} of the sequence). Recall that columns of the grid is indexed by elements of \mathcal{P}(\mathbb{N}). For every element S\in\mathcal{P}(\mathbb{N}), fill the S-th column by inserting 0, 1, 0, 1, 0, \cdots into the rows indexed by a_{n_{1}}, a_{n_{2}}, a_{n_{3}}, a_{n_{4}}, \cdots respectively, where S_{1}=\{n_{1}, n_{2}, n_{3},\cdots\}, and entering 1/2 (or anything arbitrary) to all other entries of this column. Let’s give an example. For example, if S=\{2, 3, 4, 18\}, then we would insert 0 to the entries (a_2, S), (a_4, S) and insert 1 to the entries (a_3, S), (a_{18}, S), and insert 1/2 for (a_j, S) for all j\notin S. Of course, S could be infinite as well, but hopefully the idea is clear.

Now that the grid is filled, the elements of the sequence are ready. They are simply the rows of the grid. The claim is that the constructed sequence \{a_n\}_{n=1}^{\infty} has no convergent subsequence. Indeed, assume to the contrary, that \{a_{n}\}_{n=1}^{\infty} has some subsequence \{a_{n_k}\}_{k=1}^{\infty} that converges. We take S=\{n_1, n_2, n_3, \cdots\} and look at the S-th column of the grid. What do we see? We see 0, 1, 0, 1, 0, \cdots across the rows indexed by \{a_{n_k}\}_{k=1}^{\infty}. So this shows \{a_{n_k}\}_{k=1}^{\infty} cannot possibly converge, because if it did, it would have to converge componentwise, but S-th component of a_{n_{k}} alternates between 0 and 1. This is a contradiction, and the claim is proved.

So X=[0, 1]^{\mathcal{P}(\mathbb{N})} is an example of compact space which is not sequentially compact.

Remark. Of course, the same idea goes on to show that X=[0, 1]^{\mathbb{R}} is compact but not sequentially compact. The key is to write down a bijection (injection would suffice) f:\mathcal{P}(\mathbb{N})\to\mathbb{R} and work from there…

Posted in Uncategorized | Leave a comment

Every group of order 63 is not simple.

Recently I have been browsing the book “Topics in Group Theory” by Geoff Smith and Olga Tabachnikova. This is a great book to learn advanced group theory at the undergraduate level. I only wish I knew this book earlier in my studies…

The Chapter 4 of the book is titled “Entertainment”. It includes applications of the tools such as group actions and Sylow Theorems to prove a variety of results for both finite and infinite groups. For the finite case, the focus is partly on teaching methods to prove a statement of the form “Every group of order n is not simple.” These are fun problems in my experience. I plan to do a blog post in the future outlining some general tricks concerning this topic. (The algebra qualifying exams tend to ask questions of this type).

For now, let us consider the groups of order 63. Can we prove that every group of order 63 is not simple? Yes:

Easy way: Note that the number of 7-Sylow subgroups is divisor of 9, and is \equiv 1 (\textrm{mod } 7). Hence, there is only one 7-Sylow subgroup, which must therefore be normal.

In their book, Smith and Tabachnikova uses different proof, which I will call the “hard way”. Of course, the authors are fully aware of the simpler proof above, and in fact they hint in parenthetical remark that “but the alert reader will spot a faster proof!” But I quite like the approach they take. It seems like a neat trick to try on other problems.

Hard (but still elegant) way: Let G be a group of order 63. Let’s consider 3-Sylow subgroups of 9. By Sylow Theorems, the number of 3-Sylow subgroups is either 1 or 7. If it is one, then the 3-Sylow subgroup is normal and G is not simple, as claimed. So let’s assume that there are seven 3-Sylow subgroups. Take two distinct 3-Sylow subgroups P and Q. Let T=P\cap Q. Clearly, |P|=|Q|=9 and so by Lagrange’s Theorem |T|=1 or |T|=3. But if |T|=1, then the subset PQ=\{pq: p\in P, q\in Q\} would contain |P|\cdot |Q|=81 distinct elements which is absurd since the group has only 63 elements in total! Thus, |T|=3. Now we use the fact that in a p-group, any proper subgroup is strictly contained in its normalizer (it is a nice exercise; the proof by induction on the order of the group works smoothly. Alternatively, we have the more general fact that in any finite group G, if H is a p-group inside G, then [N_{G}(H): H]\equiv [G:H] (\textrm{mod } p), and this is proved by considering the fixed points for the left-multiplication action of H on the set of left cosets of H). It follows that N_{P}(T)=P and N_{Q}(T)=Q. Therefore, P\subset N_{G}(T) and Q\subset N_{G}(T). Since P is maximal in G, and Q\subsetneq P, it follows that N_{G}(T)=G and the subgroup T is normal in G.

Posted in Uncategorized | Leave a comment

Uncountability of real numbers — Topological proof

Perhaps the fastest proof of uncountability of \mathbb{R} is using the diagonalization trick. However, there’s another proof that I learnt from Topology by Munkres (Theorem 27.7 in page 176) which is nice in its own way.

It is enough to show that the closed interval [0, 1] is uncountable. Note that [0, 1] has the following three properties:

(Definition: If X is a topological space, then x is called an isolated point of X if the singleton \{x\} is an open set in X). And now the general theorem follows:

Theorem. If X is a non-empty compact Hausdorff topological space having no isolated points, then X is uncountable.

Proof. (Following Munkres). The proof proceeds in two steps. The first step will use Hausdorff condition and the non-existence of isolated points. The second step will use compactness (via the equivalent formulation stating that if any family \mathcal{C} of closed sets in X satisfies the finite intersection property, then \bigcap_{C\in\mathcal{C}} C\neq\emptyset).

Step 1: We show that if x\in X and U is any non-empty open set in X then there exists a subset V\subset U such that x\notin\overline{V}. First we choose y\neq x such that y\in U (this is possible: if x\notin U, then let y be any element of U; if x\in U then \{x\}\subsetneq U because \{x\} is not open but U is open, hence we can pick y\in U different from x). Next using Hausdorff condition, we can find disjoint neighbourhoods W_{1} and W_{2} of x and y respectively. It follows that V=W_{2}\cap U satisfies x\notin\overline{V} (Why? If x\in\overline{V}, then every neighbourhood of x would intersect V. But W_{1} is a neighbourhood of x, and W_{1}\cap W_{2}=\emptyset, and so W_{1}\cap V=\emptyset, contradiction).

Step 2. We will show that any function f:\mathbb{N}\to X is not surjective. This will establish uncountability of X. Let x_{n}=f(n). Applying Step 1 to x=x_{1} and U=X, we get a subset V_{1}\subset U such that x_{1}\notin\overline{V}_{1}. We inductively define V_{n} as follows. If V_{k} is already determined, we apply Step 1 to x=x_{k+1} and U=V_{k} to get a subset V_{k+1}\subset V_{k} such that x_{k+1}\notin V_{k+1}. So we have a nested sequence of non-empty closed sets: \overline{V}_{1}\supset\overline{V}_{2}\supset\cdots
Since X is compact, the intersection \bigcap_{n\in\mathbb{N}} \overline{V}_{n} is not empty. If x\in\bigcap_{n\in\mathbb{N}} \overline{V}_{n}, then x\neq x_{n} for each x_{n} (otherwise, x_{n}=x\in \overline{V_{n}} which is a contradiction). Thus, f is not surjective.

Posted in Uncategorized | Leave a comment

Goldbach’s Conjecture over Z/mZ

Goldbach’s Conjecture states that every even integer greater than 2 can be written as sum of 2 primes. This problem is notoriously difficult, and still open.

However, one can prove the following version of Goldbach’s Conjecture for the ring \mathbb{Z}/m\mathbb{Z}:

Proposition. Let m be a positive integer. Given any even integer 2n there exist primes p and q such that 2n=p+q \ (\textrm{mod } m).

The proof will, in fact, show that infinitely many such primes p and q exist. The required ingredients are Dirichlet’s Theorem on Arithmetic Progressions, and the following lemma due to Schinzel (1958):

Lemma. Given positive integers m and n, there exists an integer c such that \textrm{gcd}(c, m) = \textrm{gcd}(2n-c, m)=1.

Proof of Lemma. The case m=1 is trivial, so assume m>1 and write its prime factorization. We have m=p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \cdots p_{r}^{\alpha_{r}} where p_{1}, ... p_{r} are distinct primes, \alpha_{1}, ... \alpha_{2} are some positive integers. For each i\in\{1, 2, ... m\}, we will show that there exists an integer c_{i} such that \textrm{gcd}(c_i, p_i) = \textrm{gcd}(2n-c_i, p_i)=1. If p_i=2, we can let c_i=1. If p_{i} is an odd prime, p_{i} cannot divide both 2n-1 and 2n+1 (otherwise, it would divide their difference which is 2); so if \textrm{gcd}(2n-1, p_i)=1 let c_i=1, and if \textrm{gcd}(2n+1, p_{i})=1 let c_i=-1. Now, by Chinese Remainder Theorem, one can find an integer c such that c\equiv c_i \ (\textrm{mod } p_{i}) for each i. It is evident that  \textrm{gcd}(c, m) = \textrm{gcd}(2n-c, m)=1. (If it is not evident, assume \textrm{gcd}(c, m)>1. Then some prime divisor of m would divide c. But it doesn’t.)

Proof of Proposition. From the lemma, we have \textrm{gcd}(c, m) = \textrm{gcd}(2n-c, m)=1 for some positive integer c. By Dirichlet’s Theorem, there exist primes p and q of the form p=m k + c and q=m \ell + (2n-c). Thus, p + q = m(k+\ell)+2n which proves 2n=p+q \ (\textrm{mod } m), as desired. Indeed, Dirichlet’s Theorem guarantees the existence of infinitely many such primes p and q.

 

Posted in Uncategorized | 2 Comments

Cayley-Hamilton for commutative rings

Many people have told me that Cayley-Hamilton Theorem is their favourite theorem in linear algebra. I also like this theorem a lot (Proof: I am dedicating a blog post about it!)

Let A be a linear transformation on a finite-dimensional vector space V (over F). In other words, A: V\to V satisfies A(v_1+v_2)=A(v_1)+A(v_2), and A(cv)=cA(v) for every scalar c\in F. It is clear that k-fold composition A^{k}: V\to V is also a linear map. So we can ask when A satisfies a polynomial identity. In other words, we are interested in finding some coefficients c_{1}, c_{2}, \cdots, c_{m} such that c_m A^{m}+c_{m-1} A^{m-1}+\cdots + c_0 I = 0 where I is the identity map, and 0 is the zero map (the map that is identically zero).  Since the set of all linear transformations on V forms a n^2 dimensional vector space, where n = \textrm{dim}(V), it follows that the n^2+1 maps I=A^{0}, A, A^2, \cdots, A^{n^2} are linearly dependent, so there exists a linear relation between the powers of A. As a result, we see that A satisfies a polynomial of degree at most n^2.

Cayley-Hamilton Theorem shows that we can do significantly better. Recall the characteristic polynomial p_{A}(x)=\det(Ix-A). It is clear that p_{A}(x) is a polynomial of degree n. Cayley-Hamilton Theorem states that p_{A}(A)=0. I am not going to prove this theorem here. A proof can be found located in wikipedia. I am also going to assume that the reader is familiar with the notion that a linear transformation on a finite-dimensional vector space can be identified with a matrix.

Let me explain why I like this theorem. It is because the theorem is true when the field is replaced by any commutative ring! In other words, if you consider a matrix with entries from some commutative ring R, then define (say, using Laplace expansion) p_{A}(x)=\det(Ix-A) as usual. We still have the conclusion p_{A}(A)=0. Of course, it doesn’t make sense to talk about vector spaces over arbitrary rings (for this purpose, we use related objects called modules), but the Cayley-Hamilton Theorem still holds in the sense I described. This is closely related with the so-called “determinant trick” (cf. Nakayama’s Lemma) which is a very convenient tool in commutative algebra.

Here is something cool I learned today (from Professor Lior Silberman). We can deduce Cayley-Hamilton Theorem for commutative rings using the result of Cayley-Hamilton Theorem for fields. This could at first seem like a hopeless task, because we are trying to prove something stronger. Here is how the proof goes. Cayley-Hamilton is true for the field of rational numbers \mathbb{Q}. Since \mathbb{Z} is a subring of \mathbb{Q}, Cayley-Hamilton holds for \mathbb{Z}. By this, I just mean that the conclusion p_{A}(A)=0 holds whenever A is a matrix with entries from Z. Now consider an arbitrary commutative ring R. Let A be a matrix with entries from R, i.e. A\in M_{n\times n}(R ).  We view A=(a_{ij})_{i, j} as an array n^2 indeterminates. Then p_{A}(A) is a matrix with n^2 polynomials (each of them being multivariate in variables a_{ij} with coefficients in \mathbb{Z}). Now, when these indeterminates a_{ij} are replaced by integers, we get that p_{A}(A) vanishes (precisely because Cayley-Hamilton is true for \mathbb{Z}). Thus, p_{A}(A) vanishes on all of M_{n\times n}(\mathbb{Z}). But each entry of p_{A}(A) is a polynomial of degree n, and no non-zero multivariate polynomial with coefficients in \mathbb{Z} can vanish on all of \mathbb{Z}. It follows that each entry of p_{A}(A) is the zero polynomial. Consequently, p_{A}(A)=0.

It is natural to wonder why \mathbb{Z} plays an important role in the proof above. One of the reasons for this phenomena is that \mathbb{Z} is the initial object in the category of rings.

Posted in Uncategorized | Leave a comment

Continuous bijection from (0, 1) to [0, 1]

I think the following is a good exercise for first course in real analysis.

Does there exist continuous bijection from (0, 1) to [0, 1]?               (1)

Well, it feels like the answer should be “no”. At least if the question was

Does there exist continuous bijection from [0, 1] to (0, 1)?               (2)

the answer would be a trivial “no”. Continuous image of compact set is compact; in particular, [0, 1] is compact, and (0, 1) is not compact, so continuous bijection from [0, 1] to (0, 1) cannot exist. So it is natural to wonder how questions (1) and (2) are related. If f: (0, 1) \to [0, 1] is a continuous bijection, then f^{-1}: [0, 1]\to (0, 1) is well-defined function. But, if in addition, f^{-1} is known to be continuous, then once again we have a continuous bijection from f^{-1}: [0, 1]\to (0,1) which we know is impossible. For general reference:

Definition. When f: X\to Y is a continuous bijection, and f^{-1} is continuous, then we say that f^{-1} is homeomorphism from X to Y.

Thus, being homeomorphic is a stronger property than being continuous and bijective. Roughly speaking, homeomorphisms preserve all intrinsic topological properties (e.g. compactness), just like how group homomorphisms preserve the group structure. To naively answer question (1), it would be very good to know when continuous bijections are homeomorphisms. Because if continuous bijections were always homeomorphisms, then the answer to question (1) is definitive “no” by what we explained above. Unfortunately, that’s not always the case. But not all is lost. We have the following sufficient condition:

Theorem. If f: X\to Y is continuous bijection, where X is compact and Y is Hausdorff, then f is a homeomorphism.

But the domain of f is (0,1), so we can’t apply the above theorem. What a pity! After much teasing, I think it would only be fair to present the complete answer:

Solution to Question (1). Suppose that f: (0, 1)\to [0, 1] is a continuous bijection. Then there exists a unique x\in (0,1) such that f(x)=1. Let \epsilon>0 be so small that (x-\epsilon, x+\epsilon)\subseteq (0, 1). So the intervals [x-\epsilon, x] and [x, x+\epsilon] get mapped under f to intervals [a, 1] and [b, 1], respectively for some a, b\in [0, 1). But then every value in (\max(a, b), 1) would be achieved at least twice by f, contradiction.

Acknowledgement. I learnt the above proof from t.b.’s answer here:

http://math.stackexchange.com/questions/42308/continuous-bijection-from-0-1-to-0-1

Other proofs given in that thread are also very nice.

Posted in Uncategorized | Leave a comment