Cold and austere

Cross-edges are considerably more. An All-Russian Olympiad problem.

Posted on February 24, 2023 by Shamil Asgarli

I recently saw this really nice problem about graph theory from Dragomir Grozev’s excellent blog. The proof uses such a clever inductive argument, along with a technique that takes advantage of flipping colors in a given configuration.

A Point of View.

A simple connected graph with $latex 2n$ vertices is given. Prove that its vertices can be colored in two colors so that if $latex k$ is the number of edges which ends have different colors and $latex m$ – number of edges with ends of the same color, then $latex k-m geq n$.

Interesting statement since the claim $latex k-mge 0$ is a well known problem usually used as an introduction to the probabilistic method. The idea is simple. If we color the vertices randomly in two colors, the probability that any edge has ends colored differently is $latex 1/2.$ It follows the expected number of edges, with ends of different color, is half of the number of all edges. Hence, there exists a configuration with $latex kge m.$

But here we have a much stronger result. The price is that we narrow down the assumptions. We want the graph…

View original post 963 more words

Posted in Uncategorized | Leave a comment

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

Posted on October 19, 2014 by Shamil Asgarli

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.

Posted in Uncategorized | Leave a comment

Compact space that is not sequentially compact

Posted on September 24, 2014 by Shamil Asgarli

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.

Posted on July 24, 2014 by Shamil Asgarli

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

Posted on June 4, 2014 by Shamil Asgarli

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:

It is compact.
It is Hausdorff.
It has no isolated points.

(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

Posted on April 19, 2014 by Shamil Asgarli

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

Posted on March 4, 2014 by Shamil Asgarli

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]

Posted on October 26, 2013 by Shamil Asgarli

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

Properties of Noetherian modules

Posted on June 16, 2013 by Shamil Asgarli

Suppose $A$ is a commutative ring with $1$ . We say that $A$ -module module $M$ is Noetherian if every ascending chain of submodules in $M$ eventually terminates. This is similar to how we define a ring to be Noetherian (a commutative ring $A$ is Noetherian if every ascending chain of ideals in $A$ eventually terminates).

In “Undergraduate Commutative Algebra” by Miles Reid, the following proposition is proved (page 53), from which some important properties of Noetherian modules can be derived.

Proposition. Let $0\longrightarrow L\overset{\alpha}{\longrightarrow} M\overset{\beta}{\longrightarrow} N\longrightarrow 0$ be a short exact sequence of $A$ -modules. Then,

$\displaystyle M\textrm{ is Noetherian } \Longleftrightarrow L \textrm{ and } N \textrm{ are Noetherian}$

I have written up proof of this here. (I have filled in some details, where Miles have left to the reader).

Here are some consequences:

(1) If $M_i$ are Noetherian modules (for $i=1, 2, ..., r$ ), then $\bigoplus_{i=1}^{r} M_i$ is Noetherian.

(2) If $A$ is a Noetherian ring, then $A$ -module $M$ is Noetherian if and only if it is finitely generated $A$ -module.

(3) If $A$ is a Noetherian ring, $M$ is a finitely generated $A$ -module, then any subdmoule $N\subseteq M$ is again finitely-generated $A$ -module.

Proof. (1) We recall that direct sum $M=M_1\oplus M_2$ can be realized as an exact sequence $0\longrightarrow M_1\overset{\alpha}{\longrightarrow} M\overset{\beta}{\longrightarrow} M_2\longrightarrow 0$ , where $\alpha(m_1)=(m_1, 0)$ , and $\beta((m_1, m_2))=m_2$ . Applying the Proposition, we obtain that $M= M_1\oplus M_2$ is Noetherian module. By simple induction, this is extended to direct sum of any finite number of Noetherian modules.

(2) If $A$ -module $M$ is finitely generated, then we have a surjection $A^{m}\to M$ for some positive integer $m$ , where $A^{m}$ is a free module of rank $m$ . In other words, we have an exact sequence $A^{m}\overset{\beta}{\longrightarrow} M\longrightarrow 0$ . From (1), we know $A^{m}$ is Noetherian. By the one of the directions ( $\Rightarrow$ ) of the Proposition, we obtain that $M$ is also Noetherian. Conversely, if $M$ is a Noetherian $A$ -module, it is clear that $M$ is finitely generated $A$ -module, for otherwise we would obtain ascending chain of submodules

$(m_1)\subsetneq (m_1, m_2)\subsetneq (m_1, m_2, m_3)\subsetneq \cdots$

that does not terminate. Here $(m_1, m_2, ..., m_k)$ is the submodule generated by elements $m_1, m_2, ..., m_k$ .

(3) Since $M$ is finitely generated $A$ -module, we get from (2) that $M$ is a Noetherian $A$ -module. It is clear that any submodule of a Noetherian module is again Noetherian module. So a submodule $N\subseteq M$ is Noetherian. Applying (2) again, we get that $N$ is finitely-generated $A$ -module, as desired.

Posted in Uncategorized | Tagged commutative algebra, modules, Noetherian | Leave a comment

Idempotent elements outside the nilradical

Posted on April 22, 2013 by Shamil Asgarli

Here is a cute exercise in Introduction to Commutative Algebra by Atiyah & Macdonald (A&M), that I recently solved, and felt like writing it up. The problem reads as follows:

Exercise 6 (Chapter 1). A ring $A$ is such that every ideal not contained in the nilradical contains non-zero idempotent (that is, an element $e$ such that $e^2=e\neq 0$ ). Prove that the nilradical and Jacobson radical of $A$ are equal.

Before proceeding to solution, let’s define what each of these terms mean. Even before that, let me note that throughout the word “ring” will mean commutative ring with 1 (multiplicative identity). This is the assumption made in the beginning of A&M. The nilradical $\mathfrak{N}$ of a ring $A$ is the set of all nilpotent elements of $A$ (an element $x\in A$ is called nilpotent if $x^{k}=0$ for some positive integer $k$ .) Proposition 1.8 in A&M gives the following characterization:

Proposition 1.8. The nilradical of $A$ is the intersection of all the prime ideals of $A$ .

On the other hand, Jacobson radical $\mathfrak{R}$ of a ring $A$ is defined to be the intersection of all maximal ideals of $A$ . Proposition 1.9 in A&M gives the following characterization:

Proposition 1.9. $x\in\mathfrak{R} \Longleftrightarrow 1-xy$ is a unit in $A$ for all $y\in A$ .

Using these two results, we can proceed to the solution of the exercise above.

Solution of Exercise 6 (Chapter 1). Since every maximal ideal is a prime ideal, and nilradical is the intersection of all prime ideals, it is clear that nilradical is contained in the intersection of all maximal ideals, that is, nilradical is contained in Jacobson radical. This proves one of the inclusions (note that this inclusion, namely $\mathfrak{N}\subset\mathfrak{R}$ holds generally in any ring). Now we need to show that Jacobson radical is subset of the nilradical. Let $x\in\mathfrak{R}$ . We want to show that $x\in\mathfrak{N}$ . Assume, to the contrary, $x\notin\mathfrak{N}$ . By assumption, the ideal generated by $x$ , namely the principal ideal $x=\{xa \ : \ a\in A\}$ is not contained in the nilradical. By hypothesis, this means that there exists a nonzero idempotent element in $(x)$ . Hence, there exists $a\in A$ such that $(xa)^2=xa\neq 0$ . Now since $x\in\mathfrak{R}$ , using Proposition 1.9 we get that $1-xa$ is a unit. But $1-xa=1-(xa)^2=(1-xa)(1+xa)$ . Since $1-xa$ is a unit, we can multiply this equation from the left by its inverse $(1-xa)^{-1}$ to get $1=1+xa$ , or equivalently, $xa=0$ . This contradicts $xa\neq 0$ , and so we conclude that $x\in \mathfrak{N}$ , as desired. This completes the proof that the nilradical and Jacobson radical of ring $A$ coincide.