Can my computer understand more Maths than me - The Imperial College Mathematics Competition

 

Hey folks, long time no see. Life has been pretty busy in the past few months, hasn't it? In order to make life easier for Math students across the UK, several students at Imperial, myself included, ran the 4th edition of the \(\href{https://icmathscomp.org/}{Imperial \ Mathematics \ Competition}\). This year, we went for an online format, kinda like the IMC last summer. Overall, we had an impressive amount of people attending the first round; over 120 students participated at the first round, the top 50 qualifying for the second one.

All problems were exciting and fun, the organizing team was excellent, and it was great working with likeminded individuals. In this post, I'll go over one of the two problems that I proposed: the 3rd problem from the second round. I thought of this problem while working on some integral inequalities. Here it is:

Let \(f,g,h\) be continuous functions and \(X\) a random variable such that \(E(g(X)h(X))=0\) and \(E(g(X)^2) \neq 0 \neq E(h(X)^2)\). Prove that \(E(f^2(X))-\frac{E^2(f(X)h(X))}{E(h^2(X))} \geq \frac{E^2(f(X)g(X))}{E(g^2(X))}\).

Solution: What do expected values and integrals have in common? Well, sure, expected values are integrals, but there is another thing; both can be written as inner products. For instance, \(<f , g> =\int_{0}^{2\pi} f(x) g(x) dx\) is an inner product. Similarly, one can think of \(E(XY)\) as an inner product between two vectors, which in this case are random variables, or functions thereof. Thus, this problem is actually linear algebra in disguise!

Let's rewrite it using only linear algebra. We now have to prove that, if \(f, g, h\) are vectors on a vector space over \(\mathbb{R}\) such that \(<g, h>=0\), \(<g,g> \neq 0 \neq <h,h>\), the following inequality holds:

\(\begin{equation} ||f||^2 \geq \frac{(f,g)^2}{||g||^2} + \frac{(f,h)^2}{||h||^2} \end{equation} \)

For any \(\lambda \in \mathbb{R}\), we have \(\lambda (f,g)= (g,h+\lambda f) \leq ||g|| \cdot ||h+\lambda f||\), by Cauchy. Squaring, we obtain that \(\lambda^2 (f,g)^2 \leq ||g||^2 \cdot ||h+\lambda f||^2\). Now dividing by \(||g||^2 \neq 0\) yields \[\lambda^2 \frac{(f,g)^2}{||g||^2} \leq ||h+\lambda f||^2 = ||h||^2 + 2 \lambda (f,h) + \lambda^2 ||f||^2.\] We can take everything on the right side, to obtain that 

\(\begin{equation} \lambda^2 (||f||^2 - \frac{(f,g)^2}{||g||^2}) + 2 \lambda (f,h) + ||h||^2 \geq 0,\end{equation}\)

for all \(\lambda \in \mathbb R\). We consider this a quadratic equation in \(\lambda\), and use the fact that, for the equation to always be positive, we need the discriminant to be smaller or equal to 0. We conclude that \(||f||^2-\frac{(f,h)^2}{||h||^2} \geq \frac{(f,g)^2}{||g||^2}\), which solves the problem. 

This was fun, right? The inequality stated works for any inner product space; I could have written integrals, or the dot product, or anything that came to mind. Thus, the solution is as general as possible. You know who else likes generalisations? My old buddy Lean. 

I wrote inner products and the Cauchy inequality from scratch; they were already written in Lean's library in a much more efficient way than I could have come up with, but I felt that proving all that I needed myself would be a better exercise. \(\href{https://gist.github.com/Soccolo/0ca77b63d90556dc94897e65845439a8}{Here}\) is the code.

In the beginning, I defined what an inner product is; you may observe that it is the real inner product, as I haven't thought about making the inequality more general. I also proved some properties of inner products; the function \(f\) is a general inner product, so any result about it is a result about the inner products I defined. Cauchy-Schwarz was pretty interesting to prove; I am certain that there is a way easier way of proving it, but I am still a Lean novice. After Cauchy-Schwarz, we delve immediately into the problem at hand; we prove some lemmas and small results, and compile them together in a neat way to get a proof.

Every 'have ...' is some sort of lemma inside a proof. The logic is the classical 'divide and conquer' idea; I split the problem into pieces, then glued them together to get a result. Lean treats each such lemma inside the proof as a proof itself; when you use a result in Lean, you don't quote the result, you actually use a proof of the result. Thus, through each 'have ...', I got lots of results that I used in order to prove the Cauchy inequality and the contest inequality. I am not the best person to explain how Lean works, so why don't you check out the community's \( \href {https://leanprover-community.github.io/}{website}\)?

It's a fun time to be alive if you're a Mathematician. Lean 4 has been released and it's still being worked on, the Maths community is more intertwined than ever, the quantum world is unravelling before our eyes, big data is beginning to play a huge role in the world's affairs. Tune in next time for another dive into what Maths has to offer, or something completely random!

Cris.

What if my laptop could beat me at the Balkan Math Olympiad?

Hey there folks, Cris here, showing you another random Mathematics-related thing that I have recently done!

So, for my UROP project at Imperial, I had to formalize problems from Math contests in Lean. Of course, I really derailed and tried to prove some other things, too, but still. My most recent accomplishment is the formalization of the second problem from the Balkan Math Olympiad 2019. To be fair, I completely forgot about the BMO up until I scrolled through an old Romanian Mathematical Gazette that I had laying around. I read the article in the Gazette about the competition, and, after looking over the solutions, I had an epiphany: I could teach my laptop how to solve them! Being more-or-less familiar with inequalities, I decided to look over the second problem. Here it is: 

Let \(a, b, c \in \mathbb{R}\) such that \(0 \leq a \leq b \leq c\) and \(a + b + c = ab+bc+ca \ge 0\). Prove that \(\sqrt{bc}(a+1)\geq 2 \).

Proof: The Gazette showed the solutions that the students gave, and the following is Dragos Crisan's proof. Let \(t = \sqrt{bc}\). If \(a \geq 1\), then both \(b\) and \(c\) will also be bigger than 1, and the problem is trivial.

If \(a \le 1\), then we can write \(t^2 = bc = a + (1-a)(b+c) \geq a + 2(1-a)t\), where the inequality is due to AM-GM. Thus, we have obtained the fact that \(t^2 - 2(a-1)t-a \geq 0\). From here on, Dragos looks at the roots of the function \(f(x)=x^2-2(1-a)x-a\). A quick calculation with the discriminant shows that the roots are \(x_2 \leq 0 \leq x_1\). 

By observing that \(f(\frac{2}{a+1})=\frac{-a(a-1)^2}{(a+1)^2} \leq 0\), we can deduce that \(\frac{2}{a+1}\) is between the roots. Similarly, since \(f(t) \geq 0\) and \(t \geq 0\), we deduce that \(t \geq x_1 \geq \frac{2}{a+1}\). Multiplying by \(a+1\), we get the conclusion that \(\sqrt{bc}(a+1)\geq 2 \). ⬜

This proof is really clever and short, which adds to its beauty. To us, it seems easily understandable, so I wondered if my laptop would think the same. When I started writing it down, I wasn't sure if it was going to understand it, but apparently it did. \(\href{https://leanprover-community.github.io/lean-web-editor/#url=https%3A%2F%2Fgist.githubusercontent.com%2FSoccolo%2F869caf89d5a9a29864d899791d02b634%2Fraw%2Fd00813da7e9d9ce2ec07329c84a8e546714532ec%2FBalkanMOP2.lean}{Here}\) it is. The online editor is pretty slow; if you want the real deal, feel free to download Lean. Also, in a few months, the code may not work anymore; Lean is constantly getting updated, and some inefficient tactics may be deleted.

You may have noticed in the proof that I ignored some aspects, such as why one root is negative and one is positive, or the calculation of \(f (\frac{2}{a+1})\) and so on. This can't happen with computers, they are a lie detector when it comes to proofs. I even had to prove that \(\sqrt{4}=2\), although it is very probable that there was a one-liner that could have solved that problem. I am new to Lean myself, so the code isn't as good as it should be; the problem could be solved more efficiently. Lean uses something called 'Calculus of Constructions', which basically means that it deals with combining propositions and proofs in order to get something. Each statement to the right, e.g, let's say, 'obs', is actually a proof of whatever it mentions. For instance, if the half-screen on the right, which is called the 'pretty printer' says something about 'obs:\(4=2*2\)', it means that it has a proof that \(4=2*2\). Using different commands and lemmas from the library (e.g the things that I imported in the beginning), the computer does what we did above, but way more rigorously. This is an advantage of computers: they can't be wrong unless we give them wrong info. Since Lean is built on the axioms of Mathematics, such as the Peano Axioms, it can't be wrong. 

On the topic of axioms, here's something interesting. I was formalizing the first problem from the same competition, something about prime numbers, and I wanted to prove that \(2^n-n^2 \geq 0\), for all natural numbers. Normally, I would have done it with induction, but Lean thought it was obvious. Surprised, I checked why it thought that, because it didn't seem obvious to me. Here comes the computer's understanding of axioms: I was working with the natural numbers, where Peano rules. Since I was only using commands and libraries attributed to the natural numbers, Lean only used those axioms, so integers, reals, etc didn't exist for it at that moment! Since Peano stated that \(0 \neq a + 1\), for any \(a \in \mathbb{N}\), Lean considered that 0 is the smallest number, and anything that should normally be smaller than 0 is actually 0, which is axiomatically correct, but intuitively wrong for us. Fortunately, this doesn't lead to wrong results: you can't prove that \(0 \leq 1-2 \to 2 \leq 1\), because Lean understands that it's wrong. 

Another cool fact: Lean actually caught me when I was wrong! I was proving the Heisenberg Uncertainty Principle from Quantum Mechanics in Lean, and, instead of using the complex inner product, I used the real inner product, and I eventually proved something obvious, that describes Classical Mechanics. Lean isn't made for formalizing Physics, but Quantum Mechanics is very mathematical in nature, and if you only deal with the Mathematical Physics part, it's pretty doable. 

In the future, maybe 10-20 years from now, computers may become assistants or actual theorem provers, proving theorems that we can't right now. But, at the moment, they are in need of our help, just like children that are taught Maths. However, the student of today is the teacher of tomorrow, so let's tutor them! 

This was it for today folks! Tune in next time for some Mathematical Physics (aka my newest burning hobby; already done courses in Quantum Mechanics and Special Relativity, also reading 'Foundations of Mathematical Physics' by Sadri Hassani, great book), some Lean, or something completely random!

Cris.

The Experience of the First Online International Mathematics Competition for University Students

Hi there folks! Long time no see! Lots of things happened ever since the last article: I took my exams, summer holiday started, and the first online International Mathematics Competition for University Students took place. It has been a long-while dream of mine to take part in this competition, and I was hell-bent on participating this year. Turns out, however, that I didn't get to participate the way I wanted; due to the Covid-19 pandemic, it was held online.

As a teamless student, I was supervised by Ivan the Confessor, alongside many other teamless students, on a Google Meet call. We had several possible timezones in which we could take the contest: the European timezone, which was from 7 AM UTC to 11 AM UTC, the Asian timezone, from 2 AM UTC to 6 AM UTC, and the American timezone, from 2 PM UTC to 6 PM UTC. Of course, as the chad I am, I woke up at 2 AM UTC aka 5 AM Romanian time and solved the problems then. Just kidding, I took the contest in the European timezone. My computer's camera crashed, and I had to shut it down and use the phone in order to record myself and my desk instead. 

Since the Olympiads ended for me in the 12th grade, I forgot how it felt to actually be in a contest, especially an international one. So, as the contest began, I was incredibly scared. Fortunately, this fear always passes when the subjects come. One important thing to note about me: I cough whenever I'm nervous. It's not a very quiet cough, but an incredibly loud one, with sound waves travelling through all 11 dimensions of M-string theory and beyond. My cough is literally Covid-20. This time, however, I didn't feel the need to cough, which was pretty odd. 

After printing the subjects, I swiftly started working on them. I solved the second problem first, since it was a matrix problem; it couldn't have taken me more than 10 minutes. The problem is as follows:

Let \(A, B \in M_n(\mathbb{R})\) such that \(rk(AB-BA+I)=1\). Prove that \(Tr(ABAB)-Tr(A^2B^2)=\frac{1}{2}n(n-1)\).

Solution: It is a pretty known fact that, if \(A \in M_n(\mathbb{R})\) is a matrix of rank \(r\), then there exist matrices \(E \in M_{n,r}(\mathbb{R})\) and \(F \in M_{r,n}(\mathbb{R})\) such that \(A=EF\). In this case, these matrices were vectors, so \(A^2=EFEF=E(FE)F\), where \(FE\) is a real number due to matrix multiplication. Since \(FE=Tr(FE)=Tr(A)\), we get that \(A^2=Tr(A)A\), which characterizes all matrices of rank 1. Let us apply that in our problem. 

By squaring, we get that 

\((AB-BA+I)^2=\)

\(Tr(AB-BA+I)(AB-BA+I)\), which is equal to \(n(AB-BA+I)\). If we apply trace again, and equalize the traces in \((AB-BA+I)^2\), we get the conclusion. 

The problem wasn't too hard, but it required a trick. Another possible way of doing it would have been with the Jordan canonical form, but it revolved around the same trace idea. 

The first problem of the contest wasn't my cup of tea. It was combinatorics, and I'm not trained in it. It took me about an hour and hour and 45 minutes to finally catch on to it, after failing miserably at calculations that shouldn't have been too hard. Here's the problem:

Let \(n \in \mathbb{N}^*\). Compute the number of words \(w\) that satisfy all the following properties: 

(1): \(w\) consists of \(n\) letters, all of them from the alphabet {a,b,c,d}.

(2): \(w\) has an even number of a-s

(3): \(w\) has an even number of b-s

Solution: First, let us observe that the total number of words is \(4^{n}\), for a certain \(n\). Consider the following sequences: 

\(a_n\) = number of n-words containing an odd number of both a and b;

\(b_n\) = number of n-words containing an odd number of a or an odd number of b, but not an odd number of both;

\(G_n\) = number of n-words containing an even number of both a and b, e.g 'good' words.

Thus, \(a_n+b_n+G_n=4^n\). Now, let's find a recurrence. We can obtain a word with a or b odd, but not both odd, by adding a c or a d to a word with only one odd, an a or a b to a word with both odd, and an a or a b to a good word. Thus, \(b_{n+1}=2(a_n+b_n+G_n)=2 \cdot 4^{n}=2^{2n+1}\).

By a similar argument, \(G_{n+1}=b_n+2G_n\), so we have that \(G_{n+1}-2G_n=2^{2n-1}\). After solving the recurrence, we obtain that \(G_n=4^{n-1}+2^{n-1}\). Of course, I couldn't observe this without making calculation mistakes; still, I eventually solved the problem correctly. 

After solving these 2 problems, I looked over problem 3. Seeing that I couldn't read it, I skipped over to problem 4. Problem 4 was a result about polynomials, and it was solvable, if you knew enough Complex Analysis and had the brilliance to figure out that it was a Complex Analysis problem. I didn't have that brilliance. 

I was pretty pleased with myself for proving 2 of the 4 problems, and I was already envisioning myself winning a first prize. Then, second day came, with 4 new problems for me to attempt. I solved the first one in the first 45 minutes of the contest, and then struggled for the rest of the contest on the second one. Here's the proof that I gave for the first problem:

Find all \(f:\mathbb{R}\to (0,\infty)\) twice differentiable functions such that \(f ''(x)f(x)\geq 2(f '(x))^2\).

Solution: One first observation is that \(f\) is convex. Indeed, since \(f\) and \((f '(x)^2\) are both positive, \(f ''(x)\) is also positive. 

The second observation is the one that took me the most of those 45 minutes. Let's look at \(\frac{1}{f}\). Observe that its second derivative is exactly \(2(f'(x))^2-f''(x)f(x)\leq 0\), so \(\frac{1}{f}\) is concave. It is a known fact that the only strictly positive concave functions are constant ones, so \(\frac{1}{f}\) is constant, and \(f\) is, thus, a positive constant. During the contest, I said that the only functions satisfying \(f\) convex and strictly positive and \(\frac{1}{f}\) concave are constant ones, but I discussed the fact poorly; thus, I lost one point. More on that later. 

Next, for the following 3 hours, I tried solving problem 2. Problem 2 went as follows:

Find all prime numbers \(p\) such that there is only one \(a \in \{1, 2, ... p\} \) such that \(p | a^3-3a+1\). 

Solution: For the rest of the proof, we shall work in \(\mathbb{Z_p}\).  I wanted to prove that, if the equation has a solution, there must also be another one, a function of \(a\). Here's the trick: see that, if \(a\) is a solution, \(a^2-2\) is also a solution. One can also check that \(-a^2-a+2\) is a solution. How could you possibly see these solutions? By looking at the solutions of \(X^3-3X+1\), which you could find through Cardano's formula. By solving the resulting equations, it could be seen that \(p=3\) is the only solution.

Another possible solution, one that one of my friends found, was by working with grade two equations in \(\mathbb{Z_p}\) and discriminants. Another one thought of using a trick found in an old IMO, that said that, if such p exists, then it's of the form \(9k+1\) or \(9k-1\). This trick used field extensions, which were used in one of the official solutions. Problem 3 of the second day was something about groups, which actually looked doable, but I spent all of my time on problem 2, hoping that it was a trick that I'd figure out. 

After the time was up, I scanned the solutions and uploaded them in a Dropbox. Funny story: after the first day, I sent an email, asking if my problems were sent. An organizer replied that they were sent, but that, on problem 3's solution, I only wrote the number of the problem. To that, I replied: 'Yup, it's intentional.' XD

The results started coming the next day. The people at IMC were uploading results problem by problem, and they started uploading them at 2 am Romanian time. One of my friends and I waited for the results for a while. They stopped uploading results at 3:15 am. I kept waiting until 4 am. They resumed uploading results in the morning, and finished at 12:00 Romanian time. The next day, they also announced the prizes. I got 29 points, and a second prize; firsts were given to those with 30 or more. So, because of that faulty explanation, I lost the point that would have gotten me a first. You have no idea how annoyed I was when I saw that XD

Overall, this IMC was a pretty pleasant experience. I haven't prepared too much for it, so life has done me justice; getting a gold medal, the same prize as many people that have been preparing for the whole year, would have been unfair. I'll definitely be participating at next year's IMC, which will hopefully take place IRL, in Blagoevgrad, as it should have taken place this year. Hope that 1 point won't meme me again. 

Before I end this article, I want to announce something: I'm writing a Maths problem book! It will contain problems highlighting interesting techniques and ideas, and it will probably be open access. The book could be used as preparation material for Student Competitions or Romanian Olympiads. I'll probably release an early access version in October, after adding more problems. At the time of speaking, the book has 40 pages with fully solved problems. It includes chapters on Algebra, Analysis, Applied Mathematics, and, something that I've picked up only recently, Formal Theorem Proving! For the last one, I'm using a Proof Assistant Program called Lean. The book will contain problems that I haven't added on this blog, such as the following: 

Anyway, it's time to end this post. Tune in next time for some Algebra, Complex Analysis, Mathematical Physics, my thoughts on stuff, or something completely random!

Cris.

The Cristi Endomorphisms

This has been a long time coming. I have awakened from my long slumber of procrastination, coursework and computer games. 

What a wonderful time to be alive, amirite? The best time to go outside, party with friends... Oh wait. Yup people, stay inside. As much as it pains everyone, in order to ease the pressure that has been put on the medical system, we have to stay inside and avoid getting the virus. Don't be overly-terrified, as the chances of the virus being fatal are small for most of us, but don't be ignorant; COVID-19 is an aggressive virus.

Since I've been staying indoors in self-isolation for two weeks now, I started looking through my old stash of Math results, so I came across the Cristi Endomorphisms. It was either this or a result in Probability and Statistics. 

The problem, which was posed at the Traian Lalescu contest at the Polytechnic University of Bucharest in December, goes as follows: 

Let V be a vector space and T and S two of its endomorphisms such that \(V=Ker(T)+Ker(S)=Im(T)+Im(S)\). 

a) If V has finite dimension, prove that the two are direct sums.

b) Does the result still apply if V has infinite dimension?

Solution:

Part a) is pretty straightforward. We know the following: \(dim(U+W)=dim(U)+dim(W)-dim(U∩W)\).

By applying this on our current problem, we get that 

\(dim(V)=n=dim(Ker(T))+dim(Ker(S))-dim(Ker(S)∩Ker(T))=\)

\(=dim(Im(T))+dim(Im(S))-dim(Im(S)∩Im(T))\)

Sum up the two equalities, and we get that \(2n=dim(Ker(T))+dim(Im(T))+dim(Ker(S))+dim(Im(S))-\)

\(-dim(Ker(T)∩Ker(S))-dim(Im(T)∩Im(S))\) 

By using the rank-nullity theorem, we get that \(dim(Ker(T)∩Ker(S))+dim(Im(T)∩Im(S))=0\), so both dimensions are 0. Thus, \(Ker(T)+Ker(S)=Ker(T)⊕Ker(S), Im(T)+Im(S)=Im(T)⊕Im(S)\).

The second part is a bit tricky. It asks for either a proof or a counterexample. By now you probably figured out that it wants a counterexample; that's how 90% of these problems work. Now, what infinitely dimensional vector spaces do we know? No, not that space of matrices of infinite order. \(R/Q\) of course!

Let us consider \(U={U_1, U_2, ...}\) a countable subdivision of a Hamel basis. For the rest of the solution, we shall deal with this subdivision. The elements of the basis outside of this subdivisions shall be considered fixed under the endomorphisms' actions.

What we want to find out now is how this countable subdivision should behave according to the endomorphisms. Let \(S(U_1)=S(U_2)=U_1, S(U_3)=0, S(U_4)=U_2, ...S(U_n)=S(U_{n-2})\). Why do we have to do this? So that the Kernel of S is generated by the elements \(U_1, U_2, U_3\), while the Image is still the whole V. The Kernel of S is basically \(a(U_1-U_2)+bU_3\). 

Now for T: Choose \(T(U_1)=U_1, T(U_2)=0, T(U_3)=U_3\), and the rest are 0. This way, the Kernel of T is generated by \(U_2\) and all other elements of the Hamel basis other than \(U_1\) and \(U_3\). Thus, the sum of the Kernels is V, the sum of the images is V, and yet the images don't form a direct sum. If you want to upgrade this, so that the Kernels don't form a direct sum either, let \(S(U_4)=0\) and then continue with \(S(U_n)=U_{n-3}\) instead of \(n-2\). Thus, the Kernels intersect in a subspace generated by \(U_4\). 

I really enjoyed this problem, as it challenges the student's understanding of vector spaces. Most problems involve a finitely dimensional space, or are easily translated into matrices, but this problem requires some out-of-the-box thinking, and I felt really pleased with myself for solving it. I admit, I was so pleased with it, that I started telling literally everyone about the Cristi Endomorphisms. I'm certain that most of my friends can agree that I annoyed them a bit with this problem (; 

See you next time with that probability result, some complex analysis that I found, yet another matrix problem, or something completely random! Until then, stay safe people!

Cris 

Two Analysis problems of completely different flavours

Eyy guys, it's your boy Cris here, writing this post during the first day of uni here at Imperial College. Hooray! Today, I shall discuss two problems that I have found or thought about while being here.

The first problem of the day is a limit asked at a contest. This problem was given to me at a party organized by the halls I live in. While the party continued in the background, for about 15 minutes, my universe consisted of me and the limit. I guess that's what happens when you ask STEM people to have fun. The limit is more of an icebreaker for the harder pure Analysis thingy that follows. The limit goes something like this:

Find the limit of \((\frac{a_1^{1/n}+a_2^{1/n}+a_3^{1/n}}{3})^n\) as n approaches infinity, where \(a_1, a_2, a_3\) are real positive numbers.

Solution:

I'm not really a fan of calculating limits or integrals, I'm more of an Algebra person, but here it goes. Write the fraction as \((\frac{a_1^{1/n}+a_2^{1/n}+a_3^{1/n}}{3})^n=(1+\frac{a_1^{1/n}+a_2^{1/n}+a_3^{1/n}-3}{3})^n\). Then, we shall use the exponential limits. Thus, after a bit of calculations, we end up finding that the limit of the initial sequence is the limit of \(e^{\frac{n}{3}(a_1^{1/n}+a_2^{1/n}+a_3^{1/n}-3)}\). Thus, what is left for us to do is calculate the upper limit. However, it is easy to prove that, as \(x\) tends towards 0, the limit of \(\frac{a^x-1}{x}\) is \(ln(a)\), using L'Hospital's rule. Thus, after applying this to our limit, we get that the limit is \((a_1*a_2*a_3)^{\frac{1}{3}}\). Of course, we can generalize the problem by adding m variables instead of 3, and we would get the geometric mean of all the m variables.

The problem appeared on a multi-choice contest, as far as I've been told. The guy who told me the problem gave me the result, and asked me to prove it. I think I solved it in about 20 minutes, after a few failed attempts at trying some inequalities. I'm certain that someone more passionate about Calculus could have solved it way quicker than I did, but the limit was fun to think about nonetheless.

The next problem, and the actual purpose of this article, is a problem about rotating bodies that appeared on this year's Traian Lalescu contest, at the B section; the section for Engineering departments. It caused some troubles among students, as it used a trick that is not that well known. Here it goes:

Let \(f:[a,\infty]→[0,\infty]\) a monotone and continuous function, such that \(\int_{a}^{\infty} f(x) dx\) is convergent. The graph of the function, alongside the coordinate axes, contain a surface of area A.
1. Prove that, for all natural numbers n, there exist the points \(x_1, x_2,...x_n∊[a,\infty]\) such that the lines \(x=x_k\) split the domain in n parts of equal area.
2. Let \(a_n=\frac{\sum_{k=1}^{n} f(x_k)}{n}\) Prove that V, the volume obtained by rotating the curve determined by f around the \(OX\) axis, is finite, and that \(\lim_{n\to\infty} a_n=\frac{V}{πA}\).

Solution:

Part 1 is fairly straightforward to prove, so it is left as an exercise to the reader (mainly because I am too lazy to write it down lmao). The second part is what the problem is all about.

The volume of the rotated solid is \(V=π*\int_{a}^{\infty}f^2(x) dx\), so we want to prove that the limit is equal to \(\frac{\int_{a}^{\infty} f^2(x) dx}{\int_{a}^{\infty} f(x) dx}\).

Now, here comes a dank meme. Kids, don't let your parents try this at home.Now, here comes a dank meme. Kids, don't let your parents try this at home.

Let \(F(x)\) be the integral from a to x of the function. Thus, \(F(x_k)=\frac{k}{n}A\). Also, F is clearly bijective, so we can write \(x_k=F^{-1}(\frac{k}{n}A)\), so \(f(x_k)=f(F^{-1}(\frac{k}{n}A)\). Thus, after a few calculations, we can write \(a_n=A^{-1}\frac{\sum A*f(F^{-1}(\frac{kA}{n})}{n}\). As n tends towards infinity, the sum becomes an integral, so the limit of \(a_n\) will become \(A^{-1}\int_{0}^{A}f(F^{-1}(x))dx\).

We shall prove that \(\int_{0}{A}f(F^{-1}(x))dx=\int_{a}^{\infty}f^2(x)dx\). In order to do this, we apply the change of variable \(t=F^{-1}(x)\), and, after calculations, get the required result.

The big trick with this problem is that it required that \(F^{-1}\) part. That is a well-known trick in Romania, as a problem similar to this one was asked in 2009 at the Olympiad (I think it was in 2009). A similar problem was also asked at the entrance exam for a programme at the Ecole Polytechnique in France. As always, the problem was pretty fun to solve, yet it required a trick fit for the Olympiads. 

Before ending the article, I want to make an announcement: I'm finally launching a theory page! I wish to share my knowledge of stuff among students who wish to partake at College competitions such as the IMC. The first theory page will be for Linear Algebra and it will cover everything from basic vector spaces to the Jordan decomposition. I will update that theory page from time to time, whenever I can; don't expect updates to be constant though, since it is pretty tough to cope with courses, out of class learning (I'm studying Complex Analysis atm; expect the next problem to be about Complex Analysis) and social life all at once. I will, however, do my best. So, as always, tune in next time, for something completely random!

Cris.

Results in Number Theory proved with different integral domains

What's up people? As you can see, this isn't an applied maths post, as I promised before. I still have such a post in mind; basically, my idea is to create a system of differential equations that models all sorts of relationships based on the Sociotype. The idea is there, and so are the mathematical methods, I just need a bit of field work. But asking random people on the street to take an obscure test on the internet alongside their partners and then trying to quantify their enthusiasm and level of involvement in the relationship is a bit too much, so I'll probably end up posting the solution of the Gompertz equation or the prey-predator model.

But, until then, I decided I'd take a look at a subject I didn't really care about throughout high school: number theory. I devoted most of my time to algebra, and a bit of it to analysis, but, after seeing the beauty of these results, I really regret it. I'm probably gonna study some algebraic number theory in my free time to compensate for my lack of knowledge.

So there I was, in Bulgaria, surfing AoPS, when I saw some Number Theory problem, with a guy commenting that it's similar to Lagrange's 4 squares theorem. I checked it out on Wikipedia (great place for that, right?), and, apparently, it is solvable with quaternions, numbers of the form \(x=a+ib+jc+kd\), with \(i^2=j^2=k^2=ijk=-1\), and \(ij=k, jk=i, ki=j, ji=-k, kj=-i, ik=-j\).

The theorem states that any natural number can be written as a sum of 4 squares. More intuitively, it states that, if you have a sphere in 4 dimensions, then that sphere contains an integer point on its contour. In order to prove this, we shall use a sub-field of the quaternions, the Hurwitz quaternions, which are numbers of the form \(x=a+ib+jc+kd\), with \(a,b,c,d\) all integers or halves of odd numbers.

First, let us note that, if two numbers can be written as the sum of 4 squares, then their product can be written in that form, too. Indeed, presume that \(x=a^2+b^2+c^2+d^2, y=e^2+f^2+g^2+h^2\). The sum of 4 squares is the modulus of a quaternion with integer coefficients, and, thus, \(xy\) would be the modulus of the product of quaternions with integer coefficients, which, in turn, is the modulus of a quaternion with integer coefficients. This concludes the fact that \(xy\) can be written as a sum of 4 squares.

With this fact, we can resume to proving that every prime can be written as a sum of 4 squares. We know that any odd prime divides a number of the form \(1+l^2+m^2\). We shall now discuss the Hurwitz primes, which act literally like the normal prime numbers, but belong to the quaternions. They are literally prime quaternions.

Let us presume that a prime odd number \(p\) is a Hurwitz prime. Then, \(p|1+l^2+m^2=(1+li+mj)(1-li-mj)\), so \(p\) divides either \(1+li+mj\) or \(1-li-mj\). However, this means that \(p\) divides each coefficient, so it divides 1 too, which is false. Thus, no odd prime is a Hurwitz prime.

Since \(p\) isn't a Hurwitz prime, we can write it as the product of two different Hurwitz quaternions, so \(p=(a+bi+cj+dk)(e+fi+gj+hk)\). By taking modulus, we get that \((a^2+b^2+c^2+d^2)*(e^2+f^2+g^2+h^2)=p^2\), so both of them are equal to \(p\), because, otherwise, their product wouldn't be an integer. If at least one of the sums is composed only of integers, then everything is great. Otherwise, we shall denote \(x=\frac{+/- 1 +/- i +/-j +/- k}{2}\), such that \(p+x\) has only even coefficients. Let \(y=p+x\). Then, \(p=(y^*x-1)(yx^*-1)\), where \(a^*\) is the conjugate of \(a\), while the products belong to the Hurwitz quaternions with integer coefficients, called Lipschitz quaternions. This concludes the proof.

After this, I thought that maybe I could extend the thought processes of this proof to prove easier results. I wanted to prove that any prime number that is a multiple of 4 plus 1 can be written as the sum of two squares. We know that, for such a prime number \(p\), \(-1\) is a quadratic residue, so there is an \(m\) such that \(p|1+m^2\).

I want to prove that \(p\) isn't a Gaussian prime. If \(p\) were a Gaussian prime, then \(p|1+m^2=(i+m)(m-i)\) implies that \(p\) divides both \(m\) and 1, which is a contradiction. Thus, \(p\) isn't a Gaussian prime, so \(p=(a+ib)(c+id)\), with \(a,b,c,d\) integers. By taking the modulus again, we get that both sums are equal to \(p\), which concludes the proof. As a fun fact, any number of the form \(4k+1\) can be written as a product of conjugate Gaussian primes.

Just reading this article makes me wanna study some Number Theory. In Romania, Number Theory isn't treated too much in schools, and, except for the students that participate at TSTs, everyone else stops learning this subject in the 6th grade. Somehow, though, this makes a bit of sense: Number Theory and Algebra go hand in hand in a majestic way, as I just proved, and any interesting proof in this subject would require some Ring Theory. Anyway, I'm gonna go now. Tune in next time for some Ring Theory, Applied Maths, or something completely random!

Cris.

Basic properties of Markov Matrices

What's up people? A few minutes ago, while I was browsing AoPS, I saw a post about Markov matrices. Being the curious guy that I am, I immediately jumped on Wikipedia to see what they are all about. Apparently, a Markov matrix, also known as a Stochastic matrix (you've got to admit though, Markov matrix sounds a little bit more complex) is a matrix used in probability and statistics in order to find out how a system develops. A Markov matrix usually encodes a Markov chain (this guy surely has many things named after him). Initially, Andrej Markov wanted to use these matrices for linguistic analysis and card shuffling, yet they ended up being used in many other fields. In this article, I want to discuss several interesting properties of these matrices. 

First of all, let me define a Markov matrix. A matrix \(A=(a_{i,j})_{0<i,j<n+1}\) with positive elements is a right stochastic matrix if the sum of the elements on each row is 1, and A is a left stochastic matrix if the sum of the elements on each column is 1. A first, rather obvious property, would be the following:

1. If \(A∈M_n(R)\) is a right stochastic matrix, then \(A^T\) is a left stochastic matrix.

The proof of this property is rather simple and straightforward.

Since the Markov matrix represents how a system goes from one state to another in the Markov chain, the product of two stochastic matrices is also a stochastic matrices.

2. If \(A, B\) are right/left stochastic matrices, then \(AB\) is also a right/left stochastic matrix.

We shall prove that the sum of the elements on the first row is 1. One can observe that the other rows have the same property. 

Let \(C=AB\). Thus, \(c_{11}=a_{11}b_{11}+a_{12}b_{21}+...+a_{1n}b_{n1}\), and, in the end, after summing all the elements and taking the common factor, we'll get exactly what we wanted, that the sum of the elements on the row is 1.

Now, we shall get to the eigenvalues of a Markov matrix.

3. Let \(A\) be a right stochastic matrix. Then all its eigenvalues have absolute value smaller or equal to 1.

Let us consider an eigenvector \(v\) and let \(v_i\) be its greatest element in absolute value. We know that \(Av=av\), where \(a\) is an eigenvalue of \(A\). By finding the value of the product on the i-th column, we get that \(a_{i1}v_1+...+a_{in}v_n=av_i\). We shall write this as a module, and, thus, \(|a_{i1}v_1+...+a_{in}v_n|=a|v_i|≤a_{i1}|v_1|+...+a_{in}|v_n|≤|v_i|\), so \(|a|≤1\), as required.

In fact, I believe that a stronger result can be established.

4. Let \(A\) be both a right and a left stochastic matrix. If \(a\) is an eigenvalue for which there is an eigenvector with the property that the sum of its elements is different than 0. Then, \(a=1\).

Yet again, we look at \(Av=av\). For every row, we have that (a_{i1}v_1+...+a_{in}v_n=av_i\). We sum up these relations for each row, and we get that \(v_1+v_2+...+v_n=a(v_1+v_2+...+v_n)\), because the sum on columns is equal to 1. Since the sum of the elements of the eigenvector is different from 0, we can just divide by it and obtain that \(a=1\).

This property is really interesting, because it tells us that the Markov matrices have one known eigenvalue, if such an eigenvector exists. In fact...

5. 1 is always an eigenvalue of a Markov matrix.

In order to prove this, let us first observe that, if \(A\) is a left stochastic matrix, then \(A^T\) is a right stochastic matrix. By hand, we can check that \([1 1 ... 1]^T\) is an eigenvector of \(A^T\) with eigenvalue 1. Since \(A\) and \(A^T\) have the same eigenvalues, we conclude that \(A\) has eigenvalue 1.

The property that \(A\) and \(A^T\) have the same eigenvalues is well known, yet I believe that a short explanation is in order. Take the characteristic polynomial of \(A\), \(p(X)\). We know that \(p(A)=O\), and, by transposing, \(p(A^T)=O\). Thus, we know that not only does \(A^T\) have the same eigenvalues as \(A\), but the eigenvalues also have the same multiplicities.

This was but an introduction in  the study of Markov matrices. I believe that the properties I described are good enough for a first impression on this topic. I don't know too much probability (you may have seen that I only tackled the STEP 2 probability problems, because I don't know advanced probability), but when I find out more, I'll be sure to discover more properties of these matrices. Tune in next time for probably something regarding the IMO or the IMC (since the IMC starts this week), or something completely random!

Cris.

Matrix problem regarding rational points and a number theory lemma

Eyy there. I was gonna write an article about Markov matrices (which is almost complete, btw), but then, while scrolling through undergrad contests, I found a really neat solution for a problem at the CIIM from last year. The CIIM is a competition for Latin American undergrad students, similar to IMC, Putnam, Seemous and Traian Lalescu. From what I've seen, the problems are a bit harder than those at IMC, but, then again, my opinion isn't necessarily a very competent one. These are the problems (great for you if you know Spanish).



Today, we shall solve the first one (because you know I like matrices). For those that don't know Spanish, here's what it says:

Problem: Prove that there exists a \(2*2\) matrix of order 6 with rational entries, such that the sum of its entries is 2018.

Solution: Let \(A\) be a matrix with the required properties. Since \(A^6=I_2\), we get that \((A-I_2)(A+I_2)(A^2+A+I_2)(A^2-A+I_2)=O_2\). The minimal polynomial of \(A\) is, thus, one of those appearing in the decomposition, since \(A\) is rational. If \(A+I_2=O_2\), then the order of \(A\) is 2. If \(A-I_2=O_2\), then the order of \(A\) is 1. If \(A^2+A+I_2=O_2\), then \(A^3=I_2\). Thus, the only possibility is that \(A^2-A+I_2=O_2\), so \(Tr(A)=1\), \(det(A)=1\). Let \(a, b, c, d\) be the elements of \(A\), in that order. Thus, we know that \(a+d=1\), and \(ad-bc=1\). By writing \(d=1-a\), we get that \(a(1-a)-bc=1\), so \(a-a^2-bc=1\). We want to prove that there exist matrices with these properties such that \(a+b+c+d=2018\), which is equivalent to \(c=2017-b\). Thus, our end goal is proving that \(a-a^2-2017b+b^2=1\) has rational solutions.

Now, we shall write this as the equation of a hyperbola. \(\frac{1}{4}+a-a^2-2017b+b^2+2017^2=\frac{5}{4}+2017^2\), and, by multiplying by 4, we get that \((2b-4034)^2-(2a-1)^2=5+4*2017^2\). However, we know that any odd number can be written as a difference of squares (\(2k+1=(k+1)^2-k^2\), so there exist two real squares for which we get that conclusion. In fact, we can even calculate \(a\) and \(b\), but that is left as an exercise for the reader. Since we found that \(a\) and \(b\) exist, and we found all the rational entries of the matrix according to the rational numbers \(a\) and \(b\), we conclude that there is indeed a matrix with the required properties.

As a fun fact, initially, I made a calculation mistake. Instead of writing the equation as a hyperbola, I wrote it as the equation of a circle. Thus, I got that \((2b-4034)^2+(2a-1)^2=5+4*2017^2\). I do not know whether the above equation has rational solutions, but, while trying to solve it, I remembered of an old problem from Gazeta Matematica 11/2017, proposed by Marian Andronache, which shall be treated as a lemma:

Lemma: Let \(n\) be a natural number bigger than 1 with the sum of its divisors not divisible by 4. Prove that \(n\) can be written as the sum of two squares.

Proof: We shall use the well-known 'sum of two squares theorem', which states that a number can be written as a sum of two squares if and only if any prime divisor of the form \(4k+3\) appears in the decomposition at an even power. I won't get into details regarding the solution to this, but you can see a proof of this theorem here: https://www.math.uchicago.edu/~may/VIGRE/VIGRE2008/REUPapers/Bhaskar.pdf

Getting back to the lemma, let us presume by absurd that \(n\) can't be written as a sum of two squares. Thus, there is an odd number of apparitions of a prime number\(p_i\) of the form \(4m+3\). We know that the sum the divisors is \(S(n)=\prod_{k=1}^{w(n)} \frac{p_k^{a_k+1}-1}{p_k-1}\), where \(a_k+1\) is the power at which a prime number appears in the decomposition. The term from the product associated with \(p_i\) is equal to \(1+p_i+p_i^2+...+p_i^{a_i}\), and, because \(a_i\) is odd, we get that the sum is a multiple of 4, which contradicts our choice of \(n\). The sum is a multiple of 4, because \(p^{2k}\) is a multiple of 4 plus 1, while \(p^{2k+1}\) is a multiple of 4 plus 3, and we can group the terms together.

I was a bit sad to find out that the above lemma doesn't work on the problem. Indeed, the sum of all divisors of \(5+4*2017^2\) is a multiple of 4. It does, however, work on, for example, \(1+4*2017^2\). I was just 4 units away. The lemma that I wrote has some interesting applications, and I might search for some problems to solve using it for the next articles. Thinking about that, I haven't posted any number theory problem so far. I might post something after I'm done with the Markov matrices article. Tune in next time for some properties of stochastic matrices, or something completely random!

Cris.

Two Linear Algebra problems of completely different flavours

Eyy, what's up - what's down? I have my final high school exams this week, and, after that, I'll be free to study anything I want. I already started looking into tensor products and metric spaces (I know, kinda unrelated), and I really hope I can upgrade the level of Maths on this blog by the end of summer. I really wish to learn more advanced Maths topics, so I could also do some neat Physics.

Anyways, before my final exams, I thought that I should post something fun, in case I don't make it lmao. So here are my picks for this article! Of course, they are linear algebra problems, but I promise I will soon change the topic. As much as I'd love linear algebra (it's my favourite part of Mathematics at the moment), this blog is called 'Cris's Science Blog', not 'Cris's Linear Algebra Blog'.

The first problem comes from an Excellence Test from Timisoara. I was searching through some old Mathematical magazines of mine, and I found a remarkable number from the RMT (Revista Matematica Timisoara, the Mathematical Magazine of Timisoara), the one made for the 2017 Maths Olympiad. Of course, it brought back memories, since that was my brightest year. That particular number was dedicated to the memory of one of the greatest Mathematics teachers Romania ever had, Gheorghe Eckstein.

This problem looks like an X and O with matrices. Suppose you have a \(2n * 2n\) matrix, that is 'empty' at first. Two players, A and B, take successive  turns at writing numbers in the matrix. Once a number was written, it can't be erased. A wins if the determinant of the matrix isn't 0, while B wins if the determinant is 0. The question asks if there exists a strategy for which B always wins, no matter what A does.

Solution: After playing with my imaginary friends for a while, I figured out that there is, indeed, a strategy. Since the matrix doesn't involve any known numbers, it was safe to assume that the strategy consisted of doing something with the lines of the matrix.

Consider the first two lines of the matrix. If A puts a number \(x\) on the first line, B should put the same number right under it. By repeating this process, there will be two equal lines. Since the number \(2n\) is even, B will always be the one ending the process, and, thus, he will be in control of the determinant. It doesn't matter what A puts in the other lines; if A puts a number on one of the other lines, B can randomly put a number there, too. Eventually, A will be the one writing a number on one of the first lines, and B will duplicate that number.

The problem wasn't exactly hard, but it was a fun game. That's why I added the 'Intriguing Puzzles' tag.

Now comes a more scientific one. This one is taken from Evan Chen's 'Napkin'. I started studying University Maths from there, and I really recommend checking it out: http://web.evanchen.cc/napkin.html

Let V be a finite dimensional vector space, and let \(T: V->V\) be a linear map, and let \(T^n:V->V\) denote T applied n times. Prove that there exists an integer N such that \(V=Ker(T^N)⊕Im(T^N)\).

Solution: In order to talk about a direct sum, I want to prove that there is an N after which \(Ker(T^N)⋂Im(T^N)=Φ\). It is easy to see that, as N increases, the Kernel of the linear map increases, while the dimension decreases. Since V is finite dimensional, the dimension of the Kernel reaches a maximum, let's call it l. I want to prove that, after it reaches this maximum, the Kernel and the Image become distinct. Since the dimension of the Kernel remains the same, it is obvious that the Kernel will remain the same after iterations. Let N be the iteration of T for which the Kernel remains constant afterwards.

Let \(a\) be in both \(Ker(T^{N+1})\) and \(Im(T^{N+1})\). I want to prove that \(a=0\). We know that \(T^N(a)=O\), and, since a is in the image, we have that \(T^{2N+1}(b)=0\), for b, the pre-image of a. Thus, we know that b is in \(Ker(T^{2N+1})=Ker(T^{N})\). But, since \(T^{N+1}(b)=a\), we get that \(a=0\), exactly as we wanted, so we can talk about a direct sum.

Now, we know that \(dim (Ker(T^N) ⊕ Im(T^N)) = dim Ker(T^N) + dim Im(T^N) = dim V\), and, since the Kernel and the image are subspaces of V, we get that their direct sum is exactly V, as we wanted.

I found this problem rather interesting, and, from what I saw, it works as a lemma. I haven't tried writing this as actual vector spaces instead of abstract notations, but I might look into it. Until then, I have to study Literature for my exam on Monday. Wish me luck, and more posts are coming! At first, they'll still be Linear Algebra, but after a while, trust me, they'll become more diverse. Tune in next time for something completely random about matrices!

Cris.

Equality in Sylvester's Inequality

Alright, back to the monthly posts. I have my final exams at the end of the month, after which I plan on studying more advanced Physics and College Maths. I'm already making progresses, as you may see after this post.

A while ago, one of my good friends showed me the problems he had to solve at the National phase of the Traian Lalescu contest. The first problem seemed rather interesting, and, as the title says, it involves an equality for the Sylvester inequality. As you may know, the Sylvester inequality states that, for two matrices \(A\) and \(B\) in \(M_n(C)\), \(rank(AB)≧ rank(A)+ rank(B)-n\). In this article, I will prove that, for any matrix \(A\) in \(M_n(C)\), \(n≧2\) and for any polynomial \(f\) of degree \(m≧1\) with the free coefficient \(a\) different from 0, we have that \(rank(f(A)*A)=rank(f(A))+rank(A)-n\).

Solution:

We know the fact that the rank of a matrix is the dimension of the image of the morphism associated with the matrix. By the dimension theorem, \((dim(Im (f(A)*A))+dim (Ker (f(A)*A))=n\), so \(dim(Ker (f(A)*A))=n-rank(f(A)*A))\), and, by using the dimension theorem for the other matrices and re-writing the equation in the conclusion, we need to prove that \(dim Ker(f(A)*A))=dim Ker (f(A))+dim Ker (A)\).

We shall now prove that \(Ker (f(A)*A)=KerA⊕Ker(f(A))\). First of all, let's prove that the direct sum between the two vector spaces exists. Let \(Z\) be an element of the Kernel of A different than 0. Thus, \(AZ=O\). Let m be the free coefficient of f. Thus, \(f(A)*Z=m*Z=O\) only if m is 0, which is false. Thus, no element of Ker(A) is in Ker(f(A)) other than the zero vector, so we can talk about a direct sum. We know that \(dim Ker A + dim Ker (f(A)) = dim (Ker A ⊕ Ker (f(A))\). Let us write \(W=Ker A⊕ Ker f(A)\).

We shall get back to proving that \(W=Ker(f(A)*A)\). Let \(Z=xX+yY\) be an element of W. We shall prove that it belongs to \(Ker(f(A)*A)\). \(f(A)*AZ=f(A)*A*(xX+yY)=f(A)*A*xX+A*f(A)*yY=O\), so we have proved that W is included in \(Ker(f(A)*A)\). Conversely, let \(Z\) be an element of \(Ker(f(A)*A)\). \(f(A)*A*Z=O\), so \(AZ\) belongs to Ker(f(A)). \(A*f(A)*Z=O\), so \(f(A)*Z\) belongs to \(Ker(A)\). Since \(AZ\) belongs to Ker(f(A)), \(f(A)*Z-aZ\) belongs to the Kernel, too.  Using the assertion that we've proven earlier, that W is included in \(Ker(f(A)*A)\), we get that \(f(A)Z-f(A)*Z+aZ\) is included in \(Ker(f(A)*A)\), so \(Z\) is included, too, because m is different than 0. Thus, \(Ker(f(A)*A)\) is included in W, and this implies that W is equal to \(Ker(f(A)*A)\). This concludes the proof.

The problem in the contest was a bit different, because the polynomial the jury chose was f(A)=mI-A. The generalized problem that I solved is much more interesting though. I always wondered how to reach the equality in Sylvester's inequality, and this problem sheds some light on that. However, this isn't my biggest curiosity in the realm of linear algebra. Back in the 11th grade, I was so scared of failing at the Olympiad, that I started dreaming problems at night. Here's one that I have no idea how to solve: what is the number of nilpotent matrices of order n with all entries being either 0 or 1? Of course, for n odd, there are no such matrices, but what happens for even n? I asked a friend to make a computer program, so we could compute the number. We did n=2 and n=4, but n=6 would have taken a few days to compute, so we gave up. If you know the solution to the problem I dreamt, make sure to send me a link in the comments! Tune in next time, for something completely random!

Cris.

Two matrix problems from recent Romanian Maths Olympiads

I normally don't do this kind of posts, but this year's ONM (this is the Romanian National Mathematics Olympiad; in Romanian, the adjectives and modifiers are placed after the noun) has been rather... awkward. The problems themselves were beautiful, I can't disagree, yet some were too easy for a National Olympiad, while some were too hard. The median score for the 12th grade was 3 points, and bronze medals were given to those with a score above 3.5, while silver medals were given to those with a score above 5 points. For comparison, at the 11th grade, silver medals were given to those with a score above 20 points.

This post can be regarded as a complaint to the Olympiad Committee. Last year, the subjects at the 11th grade were incredibly hard, while this year, they were incredibly easy. This difference between difficulty makes it harder for students to properly prepare for the Olympiad, and leads to anomalies in the hierarchies: hard subjects imply that students get points based on how much they guess (I put emphasis on the word 'guess') from the official solution, while easy subjects imply that many people solve them. As an example, I will discuss the solutions of the first problem from both Olympiads: the 2018 ONM and the 2019 ONM. I picked these problems because, usually, the first problems are the easiest during the contest. Even at the International Maths Olympiad, the first problem of each day is regarded as the easiest.

Problem one from ONM 2018: For every column vector X in \(M_{n,1}(Z)\), let \(c(X)\) be the least common divisor in the vector. Let A be a nxn matrix with integer entries. Prove that the following affirmations are equivalent:
1) \(|det(A)|\)=1.
2) \(c(AX)=c(X)\), for every vector X.

Solution:
1) implies 2) can be done by a double inequality. Obviously, c(AX) is bigger or equal to c(X), so we get that \(c(X)=c(A*A^{-1}X)≧c(AX)≧c(X)\), so \(c(AX)=c(X)\).
2) implies 1) is a bit harder. The official solution involves something regarding systems of equations, yet I solved it with a theorem regarding integer matrices. Any matrix A with integer entries can be written as A=U*J*V, where U and V are integer matrices with determinant of modulus 1, while J is a diagonal matrix with the integer elements \(d_1, d_2, ...d_n\) on the diagonal, in this order, such that \(d_1 | d_2 |... |d_n\).
By using this property, let us look at \(c(AX)=c(UJVX)\). By choosing \(X=V^{-1}X\), we get that \(c(UJVV^{-1}X)=c(UJX)=c(V^{-1}X)=c(X)\), because of the first implication. We shall now look at \(c(UJX)\) In order to prove that A has determinant plus or minus 1, we have to prove that J has only plus or minus 1 on its diagonal. Also, \(c(UJX)=c(JX)\), because JX is another vector. We shall look at \(c(JX)=c(X)\). Thus, for a vector \(X=(d_n, d_n, ... d_1)\), by doing JX, we get that \(d_1=d_n\). By taking an X such that \(c(X)=1\), we get that \(d_n=1\). Thus, the determinant of J has modulus 1, and A itself has modulus 1. This concludes the problem.

As you can see, the problem had a few intriguing ideas. The theorem made the whole problem easier, but it was still pretty hard. The official solution involved much more creativity. In total, about 5 people managed to solve this problem. I believe that this problem is good for the Olympiad, though it should be more of a problem 4 rather than one of many problems of same difficulty.

Let us get to the present day now...

Problem one from ONM 2019: Let A and B be complex nxn matrices such that there exists an idempotent matrix C with the property that C*=AB-BA. Prove that \((AB-BA)^2=O\).

Solution:
If C is idempotent, that means that its determinant is either 0 or 1. If its determinant is 1, then all its eigenvalues are 1, and, thus, the adjoint matrix has the same eigenvalues. With this in mind, the trace of C would be n, while the trace of AB-BA is 0, which is a contradiction. Thus, the determinant of C is 0. Let us use Sylvester's inequality on this: we have that \(rank(C^{*} C)≧ rank(C) + rank (C^{*}) - n\). With this in mind, \(n≧rank(C)+rank(C^{*})\). If \(rank(C)=n-1\), then rank (C*)=1, which implies that \(C^{*2}=Tr(C^{*})*C=O\) by writing C* in the specific form of a matrix with rank 1. If rank(C) is smaller or equal to n-2, then, by definition, C* is O, so \(AB-BA=O\). In both cases, \((AB-BA)^2=O\)

These properties of the adjoint matrix are well known in the Romanian Olympiad system. The problem is, in essence, hard, but most teachers show their students the properties of the adjoint matrix. I believe that this problem is a good opening problem, though, provided that the test increases in difficulty later on. This problem was solved by 52 students during the contest.

The point I'm really trying to make is that there must be a middle ground. An Olympiad's purpose should be to encourage children in following their passion, yet extremely hard or extremely easy problems might actually discourage them. Both problems become really easy if similar problems have been discussed before during class, yet the difference between them is that the first one involves a theorem that is not normally discussed in high school, while the second one only involves the 11th grade curriculum. A student may be able to solve the second problem even if he's never seen anything like it before, given enough creativity, but it would be impossible for him to re-discover the theorem used in the first problem. The official solution involves much more creativity than should be expected from one of the easier problems in the contest, and only a small fraction of the students, the best of the best, can come up with it. Yet the Olympiad isn't only about the top 5 students, but about all participants. During the 12th grade Olympiad this year, only 6 out of the 59 participants solved at least one problem, while the rest wrote down every idea they had with the hopes of it being in the official solution. Only one student solved more than two problems. I agree, the Olympiad shouldn't be easy, but it shouldn't be borderline impossible either.

This shouldn't be taken as an insult addressed to the Olympiad Committee. It's not. It's simply a complaint and a reason for the complaint. Besides, both problems are very beautiful, they truly represent high school Mathematics. But some problems, even though they are beautiful, just aren't meant for contests.

Alright folks, that's it for today. Tune in next time, for complex numbers, some algebra, or something completely random!

Cris.

Proof of the Riemann Hypothesis using a group with proper subgroups of order 2 and 3

1. Introduction

Back in 1859, German mathematician Bernhard Riemann introduced us to 6 important hypotheses...



Just kidding, did you really think I'd solve the Riemann Hypothesis here? April Fools joke!

Half of the title is correct, though. Today, we shall discuss a problem from the 2016 Maths Olympiad shortlist, proposed by Mihai Piticari. The problem goes as follows: Determine all finite groups which have proper subgroups only of order 2 or 3.

Solution:

First off, let us observe that the cardinal of the required group G is of the form \(2^i3^j\). By the Sylow theorem, we will have a subgroup of order \(2^i\) and a subgroup of order \(3^j\). If both of them are positive and one is bigger than 2, then we will have a subgroup larger than order 2 or 3. Thus, G can only have \(2^k\), \(3^k\) or 6 elements.

In the first case, we get that all elements have order 2, and, thus, \(xy=yx\), for all elements of G. If this happens, we have a subgroup of order 4, made of \(x, y ,xy ,e\), so the only groups working in this case are Klein's group and the group of order 2, C2.

In the second case, we shall use the equation of the classes. Let us observe that, if 2 elements that aren't part of the same subgroup commute, then we shall have a group of order 9. By the equation of the classes, we have that \(3^k=|Z(G)|+Σ\frac{|G|}{|C(G)}\), where the sum is made by a complete system of representatives with non-trivial orbit.. Since \(C(G)<4\) by the observation above, it is easy to see that \(C(G)=3\), and, thus, if k is bigger than 2, we will need the center of G to have a number of elements that is a multiple of 3. Thus, we get that the only possible groups are the group of order 3 and the group of order 9. Thus, G is C3 or C9 or C3xC3.

In the third case, we have that G is either C6 or C3xC3.

This problem might not have been as easy as the Riemann Hypothesis, but it was fun nonetheless. Seriously though, it would be fun if someone actually proposed a correct solution of the actual RH on the first of April and someone disregarded it as a prank. Jokes aside, tune in next time for some stuff about complex numbers, another algebra problem, another Millennium Prize problem, or something completely random!

Cris.

Something similar to Fermat's Last Theorem on non-field finite rings

Finally, another post!

Today I shall discuss a problem from the National Maths Olympiad from 2000, the year I was born. Judging by the usual schedule of the Olympiad, this problem is probably my twin. It caught my eye because it literally disproves Fermat's Last Theorem on finite rings that are not fields (the title already said that). The FLT is, of course, a much harder problem than what I'm about to solve in the next few lines, but that doesn't make this problem less important.

Let (A,+,*) be a finite ring with 1 different from 0. Prove that the following affirmations are equivalent:
1. A is not a field.
2. The equation \(x^n+y^n=z^n\) has a solution for every natural n.

Solution:

We shall first prove that 2 implies 1. Let us presume by absurd that A is a field. Thus, since A is a field, (A\{0},*) is a finite group, with an order equal to a certain \(t\). For that \(t\), \(x^t=1\), for all elements of A\{0}. Thus, since the equation \(x^t+y^t=z^t\) has a solution, \(1+1=1\), so \(1=0\), which is false. Thus, A is not a field.

Conversely, if A is not a field, it means that it has a non-invertible element, let's call it \(x\). Since A is a finite ring, there are \(i<j\) such that \(x^i=x^j\), and, thus, \(x^i (x^{j-i}-1)=0\). By writing \(t=x^{i-1}(x^{j-1}-1)\), we have that \(x*t=t*x=0\). Now, let us take \((x+t)^n\). By the binomial theorem, this is a sum of combinations which revolve around \(x\) and \(t\), and, because \(x*t=t*x=0\), \((x+t)^n=x^n+t^n\), for all n, and, thus, we have a solution of the equation for every n.

Don't you think that this problem is really cute? I mean, it came 5 years after the proof of the FLT, and I am certain that the guy who proposed the problem had this in mind. I hope that my proof is correct, judging by the fact that the FLT has the unique record of having received the greatest amount of wrong solutions. Apparently, the peeps at the Wolfskehl committee received about 3 meters (in height) of wrong proofs. That might not sound like much, but when you think about the amount of pages required, you'll figure out that it's a really big lot. Tune in next time for trigonometric functions defined on complex numbers, another abstract algebra problem, or something completely random!

Cris. 

Two Problems from College Contests

MEME
REVIEW!!
Oh wait, wrong post.

I decided to start preparing for college contests by now, so I tried solving problems from such Maths contests. The first problem comes from the Imperial Mathematics Competition. At first, I didn't know how to solve it, and I told my good friend and classmate Dan about it. When he came up with a solution, I decided that I would solve it, too, and here's the proof I came up with. But first, the problem itself:

Let us presume that we use k>1 colors to color the lattice points of the plane. Is it true that there will always be a rectangle with vertices of the same color?

Solution:

Yes, it is true. In fact, the problem came as a two-parter: the first part of the problem asked you to prove this for k=2. Since this part proves the problem, I decided that I'd only discuss this one.

The proof is rather short, and I was surprised to see that. Due to the countability of the set of integer numbers, we can find, on a horizontal axis we shall call \(d_1\), an infinity of points of a certain color, \(c_1\). We shall now look on another axis, \(d_2\), but directly above the infinity of points of color \(c_1\). Since the infinity of points of color \(c_1\) is countable, with cardinal Aleph Null (I can't find the symbol for this one), we can take another infinity of points directly above these on \(d_2\) so that these new points have color \(c_2\). If \(c_2\) is the same as \(c_1\), then the problem is solved. Let us presume that they are different. If they are different, we can apply the same procedure for a certain \(c_3\) and \(d_3\), and, inductively, for a color \(c_{k+1}\) and \(d_{k+1}\). However, since there are only k colors, \(c_{k+1}\) will be the same as a certain \(c_i\), and, since the points on \(d_{k+1}\) are directly above those on \(d_i\), we will obtain an infinity of rectangles with vertices of the same color.

I found this proof rather interesting, because I was expecting it to be solvable by some sort of weird configuration when I first saw it. But this argument that I presented is way more beautiful, because it not only proves that there is one such rectangle, but rather proves that there is an infinity of such rectangles.

The second problem comes from the Traian Lalescu contest, the University-wide phase from the Universitatea Politehnica from Bucharest, and it's also in a Gazeta Matematica. One of my good friends who attended the contest showed me this problem, and I solved it using Taylor series. It was a bit tricky at parts, so I hope the solution is correct.

Let \(f:(0,\infty)->ℝ\) a derivable function and F one of its primitives. Prove that, if f' is bounded and \(\lim_{x\to\infty} F(x)=0\), then \(\lim_{x\to\infty} f(x)=0\).

Solution:

We shall prove this using Taylor series. For a certain \(x\) and a certain \(h\), we have that \(F(x+h)=F(x)+hf(x)+\frac {h^2}{2} f'(x)\). By taking \(x\) towards infinity, we get that \(\lim_{x\to\infty} hf(x)+\frac {h^2}{2}f'(x)=0\), so \(\lim_{x\to\infty} f(x)+\frac{h}{2}f'(x)=0\). This works for every h. Now we only have to deal with h, so we make it go towards 0. In order to prove that this method works (this is the part I'm not necessarily so sure about). Let us take \(h_n=\frac{1}{n}\). Since \(\lim_{x\to\infty} f(x)+\frac{1}{2n} f'(x)=0\), after a certain ε, every value of said function will be smaller in modulus than a certain Δ, so \(-Δ<f(x)+\frac{1}{2n}f'(x)<Δ\). But, we have that \(-M<f'(x)<M\), so \(-Δ<f(x)+\frac{1}{2n}M\), which implies that \(-Δ-\frac{1}{2n}M<f(x)<Δ+\frac{1}{2n}M\), by the same procedure. Since Δ and \(n\) can be taken as small as possible, we get, of course, that f tends to 0.

I wasn't really certain about the last part, that's why I wrote it with epsilon and delta. I believe that a simple commutation of limits would have been enough, but I wanted to make sure. 

Anyways, this has been it for today, folks. Tune in next time for either a complex number problem, an integral that I found on a shortlist, or something completely random!

Cris.

P.S: As you may know, I am a memer, and one of the greatest meme wars recently has been the Pewdiepie vs T-series war. It would be silly of me not to do my part, especially now, when the subscriber gap is getting smaller...