Winter Self-Study

Here comes the winter update! Well, it's unfortunately sad this winter. There are a lot of (both expected and unexpected) failures. I'm feeling I'm more stupid than before, lol. However, as always, I won't lose hope this easily :) Codeforces rating goes down, confused in algebra classes, being unable to solve a few (relatively) easy problems.

This post is written on the 1st of February, so it shouldn't be the final version of the self-study diary. (If things work out, this will be updated with newer versions)

Back to Thailand

The trip to Thailand was a very good break, albeit too short. I visited my family (not much really), attended MIT Media Lab Southeast Asia Forum, visited some of my developer friends, tried some "electrical" stuffs (mostly playing toys and a little bit of fixing them, was planning to modify them but I don't have enough time). Visited IPST (just a random walk). Visited computer engineering friends and professors at CU and KU (and continued the salad-croissant debate, of course). Found a motivation to study "Concrete Mathematics". (Note: I thought it was going to be super easy, but it turns out real difficult and challenging)

Distributed Algorithms

Yes, it was relatively new for me. I learnt about a powerful technique called "graph sketching" from AGM12 which samples relatively small data from the main graph to compute some property of the big one. I learnt about the $\textsf{CONGEST}$ model of distributed algorithm, allowing messages to be sent in the size of $O(\log V)$ bits for each round, but local computation can take as much time as wanted. Learnt the basics (very shallow basics) of PP22 on the computation of small vertex cuts.

Competitive Programming and Mathematics

Among the fear and sorrow, you can see the decrease of the rating. However, I won't quit anytime soon. Recently I joined the mathematics problem sessions (they're preparing for competitions). The linear algebra problems were very difficult (too difficult for me, obviously) but that's ok. I plan to do some mathematical problem solving, as a practice exercise, on my free time (if I have any). The teacher recommended the book "Problems and Theorems in Linear Algebra" by Prasolov. It's a bit hard but I'll try.

Algebra (Reduction of Endomorphisms)

The algebra in this semester is really difficult. The contents were interesting, the problems were fun, but the exams were way too much. But, of course, that's why it's challenging. Here I'll state the first exercise of the exam:

Exercise. Consider the set $\mathcal{C}([0,1], \R)$ of continuous functions from $[0,1]$ to $\R$, equipped with regular addition and multiplication, as a commutative ring.

• Prove that $\mathcal{J} := \{f \in \mathcal{C}([0,1],\R) \colon f(0) = 0\}$ is an ideal of $\mathcal{C}([0,1], \R)$.
• Prove that for any ideal $\mathcal{I}$ of $\mathcal{C}([0,1], \R)$, if $\mathcal{J} \subsetneq \mathcal{I}$ then $\mathcal{I} = \mathcal{C}([0,1], \R)$.

The last one took me half an hour, and still hadn't figured it out during the exam. I finally solved it two days after the exam. Here's my attempt:

Proof. Let $\mathcal{I}$ be an ideal such that $\mathcal{J} \subsetneq \mathcal{I} \subseteq \mathcal{C}([0,1],\R)$, then there exists $i \in \mathcal{C}([0,1],\R) \setminus \mathcal{J}$ so that $i(0) \ne 0$. Now let us show that for any $f \in \mathcal{C}([0,1],\R), f \in \mathcal{I}$. Take any $f \in \mathcal{C}([0,1],\R)$. If $f(0) = 0$ then $f \in \mathcal{J} \subseteq \mathcal{I}$. Otherwise $f(0) \ne 0$ and so we can define $g \colon x \mapsto \frac{f(0)}{i(0)}$. Observe that $g$ is a constant function, hence $g \in \mathcal{C}([0,1],\R)$. But $\mathcal{I}$ is an ideal so $gi \colon x \mapsto \frac{f(0)i(x)}{i(0)} \in \mathcal{I}$ also. Then consider $f - gi$, we have $(f - gi)(0) = f(0) - (gi)(0) = f(0) - \frac{f(0)i(0)}{i(0)} = 0$, and since $f$ and $gi$ are both continuous, this means $f - gi \in \mathcal{J} \subset \mathcal{I}$. But both $f - gi$ and $gi$ are in $\mathcal{I}$, so their sum must also be in $\mathcal{I}$. Hence $f \in \mathcal{I}$. Therefore, $\mathcal{C}([0,1],\R) = \mathcal{I}$. This completes the proof.

This is just a (not-too-hard) exercise, of course, which took me hours to think upon the solution haha. But the other ones are insanely hard! How can one solve them in two hours!?

Whatever. It would be a shame if I spent the whole semester learning about ideals. The most important part would be about the theory of eigenvalues and eigenvectors, the minimal polynomial, the characteristic polynomial, Cayley-Hamilton theorem, eigenspaces, diagonalizability and trigonalizability, Jordan-Chevalley decomposition (they call it Dunford in France), Frobenius reduction (this one, to be honest, I don't understand it completely), and Jordan normal form (I also don't understand this completely, I just know the result).

The motivation was quite vague, like, why should I even begin studying the matrix "similarity" relation? Hmm... no idea. Maybe one day I'll use it.

Complexity?

This has been bugging me for years. And now I still want to understand the Cook-Levin theorem, but I don't have enough time to carefully listen and follow the proof.

On fine-grained complexity, there seems to be classes of problems which are $O(n^c)-$reducible to one another. This gives a kind of "equivalence" (i.e. $\textsf{3SUM}$-hardness, $\textsf{APSP}$-hardness, etc.), which is kinda interesting to me.

Read a few pages on Computers and Intractability: A Guide to the Theory of NP-Completeness during the preparation for the finals. (Still, I wasn't able to reduce $\textsf{3SAT}$ to $\textsf{ILP}$ during the exam)

Quadratic forms?

Why on earth would I study quadratic forms? Well, at first (and still now, actually), I don't really understand why people (serious mathematicians) care about quadratic forms this much. I read the first lecture in "The Sensual (Quadratic) Form" by Conway and it was really fun and amazing. The "topograph"-based approach was a really innovative way to study this (compared to other books, which, are almost impossible for me to begin with).

I did a (very little) revisit on "Introduction to Analytic Number Theory" by Apostol, in particular, on the theory of finite abelian groups and their characters (with the hope that characters would be an applicable tool for other uses outside analytic number theory).

C++ Project

Yes, closedfish. Not the best, not a success, but not a bad attempt either. I tried writing a simple game using SFML. It looks extendable. If I have more time, I really want to learn more on game development (not just C++ from scratch, but also using engines like Unity).

By the way, not much, but I should mention that I've tried Haskell in the Advent of Code 2022 and tried Coq in a course in Logic and Proofs here. Hoping to try Rust on some projects when possible.

task-pdf-writer-v2

In progress... I'm thinking of changing the philosophy of development from "making a platform to assist the development process of tasks" to "making a lightweight tool to help making tasks". This will be a standalone component which renders PDFs from a set of given markdown files.

Maybe make a chatbot also. Haha.

Open problems / Studies in progress

Surely, I won't solve any, but at least they're worth a try.

• Distributed ($\textsf{CONGEST}$) $k$-vertex cuts in $\widetilde{O}(kD)$ for small $k > 2$.
• Boolean matrix multiplication in $O(n^{2+o(1)})$.
• Bostan's conjecture: The last digit of Catalan numbers is never $3$.
• Distribution of prime numbers in an interval $[L, R]$. (instead of the traditional $[1, n]$, which we have the PNT nowadays)
• Convexity conjecture: $\pi(x) + \pi(y) \geq \pi(x+y)$ for all $x, y \in \N^*$.