Articles
BY OUR STUDENT CONTRIBUTORS
Nitya Nigam You are probably aware of some quick tricks to tell whether a large number is divisible by a smaller one - numbers ending in 0 or 5 are divisible by 5, numbers ending in 0, 2, 4, 6 or 8 are divisible by 2, and so on. But you may not be aware of quick tricks to tell whether a large number is divisible by 7 or 11. In this article, we'll outline and give examples for the divisibility rules from 2 to 12.
2: must end in 0, 2, 4, 6 or 8 198754 --> ends in 4, so is divisible by 2 (= 2 x 99377) 178725 --> ends in 5, so is not divisible by 2 3: sum of digits must be divisible by 3 48726 --> 4 + 8 + 7 + 2 + 6 = 27 which is divisible by 3, so it is divisible by 3 (= 3 x 16242) 92863 --> 9 + 2 + 8 + 6 + 3 = 28 which is not divisible by 3, so it is not divisible by 3 4: last 2 digits must be divisible by 4 987064 --> 64 is divisible by 4, so it is divisible by 4 (= 4 x 246766) 469254 --> 54 is not divisible by 4, so it is not divisible by 4 5: must end in 0 or 5 24975 --> ends in 5, so is divisible by 5 (= 5 x 4995) 82751 --> ends in 1, so is not divisible by 5 6: must end in 0, 2, 4, 6 or 8 and the sum of digits must be divisible by 3 98274 --> ends in 4 and 9 + 8 + 2 + 7 + 4 = 30 which is divisible by 3, so it is divisible by 6 (= 6 x 16379) 72956 --> ends in 6 but 7 + 2 + 9 + 5 + 6 = 29 which is not divisible by 3, so it is not divisible by 6 28683 --> 2 + 8 + 6 + 8 + 3 = 27 which is divisible by 3 but ends in 3, so it is not divisible by 6 92875 --> ends in 5 and 9 + 2 + 8 + 7 + 5 = 31 which is not divisible by 3, so it is not divisible by 6 7: double the last digit and subtract it from the number made by the remaining digits; result must be divisible by 7 (repeatable) 29862 --> 2x2 = 4; 2986 - 4 = 2982; 2x2 = 4; 298 - 4 = 294; 4x2 = 8; 29 - 8 = 21 which is divisible by 7, so it is divisible by 7 (= 7 x 4266) 55497 --> 7x2 = 14; 5549 - 14 = 5535; 5x2 = 10; 553 - 10 = 543; 3x2 = 6; 54 - 6 = 48 which is not divisible by 7, so it is not divisible by 7 8: last 3 digits must be divisible by 8 98272 --> 272 is divisible by 8 (= 8 x 34), so it is divisible by 8 (= 8 x 12284) 27594 --> 594 is not divisible by 8, so it is not divisible by 8 9: sum of digits must be divisible by 9 28746 --> 2 + 8 + 7 + 4 + 6 = 27 which is divisible by 9, so it is divisible by 9 (= 9 x 3194) 92875 --> 9 + 2 + 8 + 7 + 5 = 31 which is not divisible by 9, so it is not divisible by 9 10: must end in 0 29850 --> ends in 0, so is divisible by 10 (= 10 x 2985) 92875 --> ends in 5, so is not divisible by 10 11: add and subtract alternating digits; result must be divisible by 11 80256 --> 8 - 0 + 2 - 5 + 6 = 11 which is divisible by 11, so it is divisible by 11 (= 11 x 7296) 92875 --> 9 - 2 + 8 - 7 + 5 = 13 which is not divisible by 11, so it is not divisible by 11 12: last 2 digits must be divisible by 4 and the sum of digits must be divisible by 3 35820 --> 20 is divisible by 4 and 3 + 5 + 8 + 2 + 0 = 18 which is divisible by 3, so it is divisible by 12 92876 --> 76 is divisible by 4 but 9 + 2 + 8 + 7 + 6 = 32 which is not divisible by 3, so it is not divisible by 12 28475 --> 2 + 8 + 4 + 8 + 5 = 27 which is divisible by 3 but 75 is not divisible by 4, so it is not divisible by 12 97654 --> 54 is not divisible by 4 and 9 + 7 + 6 + 5 + 4 = 31 which is not divisible by 3, so it is not divisible by 12 Let us know in the comments if you found this article useful, and what mental maths tricks you'd like to see next!
0 Comments
Malhar Rajpal In my previous mental maths article I outlined a technique to quickly square two-digit numbers in your head, which is an invaluable skill in maths competitions. Today, we will look at a trick to quickly solve a familiar type of question: finding the day of the week for any given date in the 21st century. This article will describe the method while my next article will explain why it works. The method itself is quite straightforward. It follows the formula: Day of week code = Remainder of [(Date + Month Code + (Last two digits of year + 6) + Quotient of [Last two digits of year / 4]) / 7] This may look confusing at first but let’s break it down: Date: The number for date is simple, it’s simply the day of the month. For example during April 27th, the date would be 27 and during December 9th, the date would be 9. Month Code: The month code is a single digit number that is associated with every month of the year. I have listed the codes below in a table and the reasoning behind each of these codes will be explained in the next article. This will require a little bit of memorisation and I recommend using some kind of key word or phrase to help you remember each month's code, it’s not that difficult with some effort! *On a leap year, the month codes for January and February become 6 and 2 respectively(1 less than their usual code) Remember that leap years occur on every year that is divisible by 4 except end of century years that are not divisible by 400. So 1904 and 2000 are leap years, yet 1900 is not because although it is divisible by 4, is an end of century year and isn’t divisible by 400. (Last two digits of year + 6) + Quotient of [Last two digits of year / 4]: The last two digits of year section is pretty self explanatory: for example if the year is 2024, the last two digits are 24, or if the year is 2001, the last two digits are 01. Make sure you add the +6 to the last two digits of the year - that is necessary to make the calculation correct. The quotient of [last two digits of year / 4] is simply the answer to the division problem of the last two digits / 4 without the remainder. So if the year is 2027, The quotient of [last two digits of year / 4] is the integer part of 27/4 = [6.75] = 6, and if the year is 2085, the quotient of [85 / 4] is 21. Putting it all together: Let’s take a random date in the 21st century, 6th May 2045, and try to find the day of the week. Using the formula: Day of week = Remainder of [(Date + Month Code + (Last two digits of year + 6) + Quotient of [Last two digits of year / 4]) / 7], We quickly see the date of May 6th 2045 is simply 6, the month code for May (referring to the table above) is 1, the last two digits of the year + 6 is simply 45 + 6 = 51, and the quotient of [last two digits of year/4] is [45/4] = 11. Plugging all of these numbers into the formula: Day of week code = Remainder of [(6 + 1 + 51 + 11)/7] = Remainder of [(69/7)]. The remainder of 69/7 is 6 since 69/7 is 9 with 6 leftover. And thus we get day of week = 6. What does this mean? To find out the day of the week, we follow this table: Since we got 6 as a remainder, we can use our table to figure out that the associated day of the week is Saturday. Hence, we can confidently say that May 6th, 2045 will occur on a Saturday!
Try it for yourself, choose a random date in the 21st century and try out the method! In the next article, I will prove why this formula works. Nitya Nigam The Collatz Conjecture is one of maths' most notorious problems. Its statement is deceptively simple: take any positive integer, n. If it is odd, multiply it by 3 and add 1 (giving 3n+1). If it is even, divide it by 2 (giving n/2). Then repeat these steps with the result, forming a sequence of numbers. If we start with, say, 5, this sequence would be 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1.... - as you can see, it gets to 1 and then repeats the 4-2-1 sequence ad infinitum. The Collatz Conjecture states that regardless of which positive integer you start with, the sequence will end in the 1-4-2-1 loop. Posited in 1937, the Collatz Conjecture remains one of math's most well-known unsolved problems. However, new computational methods may shed light on the problem.
The biggest recent breakthrough using traditional mathematical methods was in 2019, when mathematical supercelebrity Terence Tao of UCLA released a proof implying that about 99% of numbers greater than a quadrillion eventually reduce to values less than 200, which means 99% of numbers satisfy the Collatz Conjecture since all numbers less than 200 have manually been shown to end in the 1-4-2-1 loop. Tao's method was analogous to how you sample a population for an election: you have to pick a sample that is representative of the full population. Similarly, Tao tried using a sample of positive integers to see whether the conjecture would hold. The problem with such a method is that each number in the sample changes its character with each iteration - numbers change from even to odd and become multiples of different numbers. The sample must therefore be constructed keeping this in mind. Tao managed to create a method to select samples that would maintain their original character through each iteration, making it easier to keep track of how the sample would behave. This method resulted in what was at the time "arguably the strongest result in the long history of the Conjecture." More recently, Marijn Heule, a computer scientist at Carnegie Mellon University, has tried applying computational methods that provided successful proofs of the Pythagorean triple problem and Schur number 5 to the Collatz Conjecture. Heule and his team created a rewriting system that simulates the Collatz sequence on mixed binary–ternary representations of positive integers. They also proved that similar rewriting systems using unary representations of positive integers do not allow the sequence to terminate, as required by the conjecture. Although their paper doesn't prove the Collatz Conjecture, it presents novel approaches that may yet prove useful in solving this problem. More broadly, this paper demonstrates the significant influence that computational methods hold in mathematics today. We discussed the Ramanujan machine in a previous article - this is yet another example of modern computing proving to be extremely useful in pure maths. Malhar Rajpal The quadratic formula is used by most secondary students to solve quadratic equations in the form ax^2 + bx + c = 0. But most of these students don’t know where the formula comes from. In this article, I will explain the derivation of the quadratic formula. The idea of the quadratic formula is to isolate x from the initial equation, ax^2 + bx + c = 0. We can subtract c from both sides of the equation to get ax^2 + bx = -c. We then proceed by dividing both sides by the coefficient of x^2, namely a: The next step requires some creativity since these steps are unintuitive and rather inventive. Firstly, we must identify the coefficient of the linear (x) term in the above equation. This is b/a. We then divide this term by 2 and square it to get: (b/2a)^2=(b^2)/(4a^2). We add this term to both sides of the above equation to get: That was the creative step. We can now simplify the equation by making the terms on the RHS of the same denominator, and by completing the square on the LHS: We now take the square root of both sides: Finally we subtract b/2a from both sides to get the quadratic formula: Now you know how to derive the quadratic formula, you can use it in a classroom situation without worrying whether it actually makes sense!
Nitya Nigam Pascal's triangle, as many of you may already know, is a mathematical pattern where the nth row is the sum of nCk from k=0 to k=n. As shown in the diagram on the left, each number is obtained by adding together the two numbers directly above it. In this article, we will investigate some of the patterns hidden in Pascal's triangle. As mentioned in the solution to May 24th's problem of the week, the sum of nCk from k=0 to k=n is 2^n, which means that the sum of rows in Pascal's triangle is 2^n. We can prove this quite easily using the binomial theorem. The binomial theorem states that: Letting x=y=1: which proves our claim. Another interesting pattern in the triangle is that the squares of the numbers on the second diagonal are equal to the sum of the two numbers directly next to and below it, as shown in the diagram below: To prove this, we need to recognise that the third diagonal is the triangular numbers, which have formula n(n+1)/2. The sum of two consecutive triangular numbers is: which is the necessary square number.
Pascal's triangle is full of many more interesting patterns - let us know in the comments what you'd like to learn about next! Malhar Rajpal Most high school students will have heard of the infinite geometric series formula as well as the sum of an arithmetic sequence formula. Most of us just accept these blindly without an explanation as to why they truly work. However, today we will prove both the formulas infinite and finite geometric series sums as well as the formula for the sum of an arithmetic sequence! For those who haven’t encountered these terms before, an arithmetic sequence is a sequence of numbers such that the difference between consecutive terms is constant. The nth sum of an arithmetic progression is thus the sum of all the numbers in the sequence up to the nth term of the sequence. Evidently, since the difference between consecutive terms is constant, the numbers will eventually be either very large and positive or very low and negative and the infinite sum of an arithmetic sequence is thus divergent. An infinite geometric series is the sum of an infinite number of terms in a sequence wherein there is a constant ratio between successive terms (sum of infinite values in a geometric sequence). It is important to note than an infinite geometric series only converges if the absolute value of the common ratio r is less than 1. As the name suggests, a finite geometric series is the sum of a finite number of terms (up to the denoted nth term) of a geometric sequence. Arithmetic Series formula proof: The formula for an arithmetic series, adding up each of the first n terms of an arithmetic progression is given by: where S_n the sum of the first n terms of an arithmetic sequence, a is the first term of the sequence, n is the number of terms we want in the sum, and d is the common difference between successive terms in the arithmetic sequence. To prove this formula, we must first look at the base definition of an arithmetic series which is adding up the first n terms of an arithmetic sequence: S_n=a+(a+d)+(a+2d)+(a+3d)+...+(a+(n-2)d)+(a+(n-1)d), or Sn=(a+(n-1)d)+(a+(n-2)d)+...+(a+3d)+(a+2d)+(a+d)+a (which is the same as above but backwards. If we add the first term of the first S_n formula with the first term of the second S_n formula, and the second term of the first S_n formula with the second term of the second Sn formula, and so on, we see that each term adds up to 2a+(n-1)d: For example: a+(a+(n-1)d) = 2a+(n-1)d and (a+d)+(a+(n-2)d) = 2a+(n-1)d… Hence by adding both the S_n together, we get: 2S_n=(2a+(n-1)d)+(2a+(n-1)d)+...+(2a+(n-1)d) Since we are adding the first n terms of the arithmetic sequence, there are thus n occurrences of 2a+(n-1)d in the formula for 2S_n. Thus: 2S_n=n(2a+(n-1)d) And by dividing two from both sides, we reach our desired formula: S_n=(n/2)(2a+(n-1)d) And the arithmetic series formula is proven. Finite Geometric Series Proof: The formula for the sum of a finite geometric series is: where S_n in this case denotes the sum of the first n terms of a geometric sequence. r is the common ratio between consecutive terms and n is the number of terms we want to sum. To prove this formula, let’s look at the defining formula for a finite geometric sequence, which includes summing up the n terms of the sequence: Sn=a+ar+ar^2+...+ar^(n-2)+ar^(n-1) We can create another formula by multiplying each term by r: rSn=ar+ar^2+....+ar^(n-2)+ar^(n-1)+ar^n The difference between these two formulas is that the formula for S_n has the term a while the formula for rS_n has the term ar^n. Both the formulas have all the other terms, ar+ar^2+...+ar^(n-1). Because of this, we can subtract rS_n from S_n to get: S_n-rS_n=a-ar^n. Factoring out both sides: S_n(1-r)=a(1-r^n) Dividing both sides by 1-r (which is possible since we don’t consider r=1 in this case) to get our desired formula: S_n=a(1-rn)/(1-r) , r≠1 And we have proven the formula for a finite geometric series! Infinite Geometric Series Proof: The textbook formula for the sum of an infinite geometric series is: S_∞=a/(1-r), -1<r<1 To determine the proof, we can evaluate the S_n formula for a finite geometric series as n tends to ∞. We thus get: The limit can only be solved if -1<r<1 since if r doesn’t fall within this range, the r^n term diverges as n tends to ∞. However, if r falls within the range -1<r<1, as n approaches ∞, the r^n term approaches 0. Thus we get our desired formula: And the final formula for this article is proven!
Nitya Nigam Graph theory is having a great year. Following the proof of lower bounds on Ramsey numbers (link is to our coverage) from Asaf Ferber and David Conlon in late 2020, a new proof has proved a special case of the Erdős-Hajnal conjecture. Essentially, the conjecture implies that forbidding certain structures at a small scale impacts the macroscopic structure of the graph, which has powerful consequences for graph theory (we'll go into more detail later in the article). The new proof, published in February by Maria Chudnovsky and Paul Seymour of Princeton University, Alex Scott of the University of Oxford, and Sophie Spirkl of the University of Waterloo, proves two special cases of the conjecture, so although a complete proof still evades us, significant progress is being made. More formally, the Erdős–Hajnal conjecture states that if a graph does not contain a certain structure (known as an induced subgraph), then the graph will inevitably have either a large clique or a large independent set. Let's define these terms: Clique: A subset of vertices in a graph such that every vertex is connected to every other member of the subset via at least one edge. Independent set: A subset of vertices in a graph such that every vertex in the subset is not connected to any of the other vertices in the subset. Large: A large clique or independent set in a certain graph with V vertices is defined as a clique or independent set with more vertices than would arise if a random graph with V vertices was drawn. Chudnovsky and her colleagues proved the conjecture for two special cases. One was the specific forbidden induced subgraph of a "five-cycle" - a set of 5 vertices where each vertex is connected to exactly two others in the set. The other was a "five-cycle with a hat" - a set of 6 vertices similar to a 6-cycle, but with an extra edge joining two vertices (shown on the left). While most conjectures are formed with mathematical consensus agreeing they are likely to be true, the mathematicians working on this problem actually expected that they would disprove the conjecture: that is, that it would be false. “We were all a little shocked,” said Chudnovsky. Prior to this paper, the conjecture had only been proven true for induced subgraphs of four vertices or fewer, as well as another special 5-vertex subgraph ("The Bull" below) by Chudnvosky and Shmuel Safra in 2005. This leaves just the five-vertex path as the last possible five-vertex induced subgraph, and the clear next step for eventually proving the full conjecture. “The five-vertex path has to be next. If you can’t do that, you’re still nowhere,” said Paul Seymour. We're excited to see what developments are still to come!
Malhar Rajpal In my last article, I talked about László Lovász, one of this year’s winners of the prestigious Abel Prize. In this article, I will talk about the background and accomplishments of this year's other recipient, Avi Wigderson.
On 9th September 1956, Avi Wigderson was born in Haifa, Israel. He graduated with a B.Sc. in Computer Science from the Technion (The Israeli Institute of Technology) in 1980. He then went to Princeton University in the USA for his graduate studies, where he completed his PhD in computational complexity under Richard Lipton. Wigderson's major contributions are in the field of computational complexity, which is the study of how quickly computer problems can be solved. You may have heard of the P=NP problem, which is the fundamental question of computational complexity. Computer problems are designated as P (meaning they can be easily solved in polynomial time) or NP (meaning it would take a very long time to solve the problem with known algorithms, but the answer can be verified quickly). Computational complexity is thus founded on the question of whether all the hard to solve problems in the NP set can be reduced to problems that are easy to solve and are in the set P, and thus whether P = NP. This is an unsolved and hotly debated question in mathematics. Wigderson made remarkable developments in this field. One of his biggest achievements is researching how randomness can be used to solve computational problems in a quicker period of time. He showed that if a computer can “flip coins” during the computational process, rather than if the computer chooses each decision, then a solution to a computational problem can be reached in a quicker period of time. This was massive, and it showed that randomness could be used to facilitate a great deal of tasks in the computational world. Dealing with randomness, however, increases the chance of an error in the solution, and therefore Wigderson, with Noam Nisan and Russell Impagliazzo, showed that for any algorithm that uses coin flipping to solve a difficult problem, there is another algorithm that is nearly as fast that uses deterministic (non-random) methods to reach the same solution, under certain conditions. This finding was a huge accomplishment, as it proved that the problem class known as “BPP” in the computer science world was actually the same as the complexity class P, revolutionising the way random algorithms were perceived. Perhaps what Wigderson is most famous for is his co-discovery of the zig-zag product in 2000. The zig-zag product is an innovative finding that links several different fields such as group theory, graph theory, and complexity theory. Very simply put, the zig-zag product of regular graphs is when one takes a large graph and a smaller graph and produces a new graph with the approximate size of the large graph but the degree of the smaller one. According to Wikipedia, it is “a method of combining smaller graphs to produce larger ones used in the construction of expander graphs”. There are, of course, several intricacies to this finding, however they are beyond the scope of this article. The zig-zag product is extremely powerful and carries a huge number of applications, such as finding the optimal way to solve a maze problem. Although he has co-authored over 100 research papers, it would be impossible to cover all of his brilliant ideas in one article. Nonetheless, these achievements alone are truly extraordinary. Nitya Nigam As promised in March 22nd’s Problem of the Week (apologies for the delay, it’s been a busy month), this is an article explaining the connection between choose functions and polynomial functions. More specifically, we’re going to prove why sequences of the form T_n = nCk (where k is a constant integer) are equivalent to specific polynomial sequences of degree k, as well as find the specific polynomial sequence that fits our POTW. While we will be showing this algebraically, there is also a very interesting analogy to Pascal’s Triangle that shows this, which we’ll leave to our readers to think about (and share their ideas about in the comments!) The example used in our POTW was T_n = nC3 for n≥3. The first few terms of this sequence are 3C3=1,4C3=4, 5C3=10, 6C3=20. We can observe that the differences between consecutive terms (what we call the “first difference”) are 1, 3, 6, 10. While some of you may already have noticed that this sequence is the triangle number sequence, we can go a step further, observing that the difference between these differences (the second differences) are 2, 3, 4 so the third difference is constant at 1. When a sequence has its kth difference constant, the sequence can be written as a polynomial. We can prove this using basic calculus. Say we have a polynomial sequence of the following form: When we differentiate this, the constant term disappears, and the powers on the rest of the terms decrease by 1, giving: When we differentiate this k times, we get: As this expression doesn’t contain any n terms, the kth derivative of a kth-degree polynomial sequence is constant. As the kth difference is simply the rate of change between integer terms, and the kth derivative is the rate of change in general (which is independent of the value of n, so will apply to integers), the two are equal. Therefore, we have shown that the kth difference of a polynomial sequence is constant, and that it is equal to k! times the coefficient on the n^k term. In our example, the third (or kth, as k=3) difference is 1. Since k! x a_0 = 1, a_0 = 1 / k! = 1 / (3x2) = 1/6. Now that we have the leading coefficient, we can simply use simultaneous equations (by plugging in the first three values of n [3, 4, 5]) to obtain the other coefficients. We’ll leave the process of simplifying and solving these equations to you (or your graphic calculator). The result you should get is a_1 = -1/2, a_2 = 0 and a_3 = 1/3, giving the following definition: After showing this analytically for the case k=3, let’s generalise. Sequences of the form nCk can be written, from their definition, as: The first difference of these sequences will be T_(n+1) – T_n: Now, if we’ve shown that the first difference of a sequence nCk is nC(k-1), then by extending this downwards by applying the same thing to the first difference sequence, we can say that the second difference is nC(k-2), and the kth difference is nC(k-k) = nC0, which is just 1. Since the kth difference is constant (which is the condition for a kth-degree polynomial sequence), these sequences can be written as polynomial sequences using the technique described above.
We hope you enjoyed this article, especially since it contained original mathematical ideas from us! Let us know in the comments if you see the link to Pascal’s Triangle, and tell us what you’d like to read next! Malhar Rajpal A few weeks ago, two extremely renowned mathematicians, Avi Wigderson and László Lovász, won the prestigious Abel Prize. Becoming an Abel Prize laureate is not an easy feat, since it is only awarded to the most accomplished mathematicians in a given year. Known colloquially as the Nobel Prize pf mathematics, it has a substantial cash prize of 7.5 million Norwegian Kroner. In this article, I will talk about one of the 2021 Abel Prize winners, László Lovász and his work.
On March 9, 1948, Lovász was born in Budapest, Hungary. He was an extremely talented mathematician from an early age and managed to win three gold medals and a silver medal at the renowned International Mathematical Olympiad, the most competitive and largest high school math competition in the world, where countries send teams of their six best mathematicians to compete. Winning a medal is not an easy feat with only around the top 8% of already brilliant participants receiving a gold medal. Achieving four medals, thus, is quite an amazing achievement and truly showed Lovász’s outstanding mathematical ability at a young age. As a prodigious mathematician, he had the opportunity to meet and learn about game theory from Paul Erdös in his youth. After studying mathematics at the undergraduate and postgraduate level at Hungary's top universities, Lovász became increasingly prominent as a researcher in the field of mathematics and computer science. He worked under the supervision of Tibor Gallai through his doctoral research in the 1970s. He also worked closely with Erdös to develop methods to complement Erdös’ graph theory techniques. One of his largest accomplishments was developing the Lovász local lemma in graph theory which states that as long as a certain number of events are ‘mostly’ independent from each other, and aren’t individually very likely, then there will be a probability that none of them occurs. Of course, there are several intricacies to this lemma that are beyond the scope of this article but it was a vital development because it led to breakthroughs in creating existential proofs for rare graphs and is used in the probabilistic method. Relating to graph theory, he also contributed to the formulation of the Erdös-Faber-Lovász conjecture in 1972 which stated that ‘If k complete graphs, each having exactly k vertices, have the property that every pair of complete graphs has at most one shared vertex, then the union of the graphs can be properly colored with k colors’. This conjecture remains unsolved, however, in 2021, a proof of the conjecture was made for all sufficiently large values of k by a team of five researchers. He also proved Kneser’s conjecture in 1978, where Martin Kneser conjectured in 1955 that the chromatic number (the minimum number of colours needed to colour the nodes of a graph such that no two nodes that share an edge have the same colour) of the Kneser graph K(n, k), for n >= 2k is exactly n-2k+2. Lovász proved it by using topological methods which was significant because it made developments to the huge field of topological combinatorics. Further, in 1982, Lovász worked with Arjen Lenstra and Hendrik Lenstra to create the LLL algorithm which is a polynomial time reduction algorithm. This algorithm was a huge breakthrough for Lovász since it led to massive developments in cryptography and polynomial factorisation, the basis of RSA cryptography. This is, by no means, an exhaustive list of Lovász’s numerous accomplishments, and Lovász has made a considerable impact in the fields of mathematics and computer science over the last five decades. He has been rewarded with several prestigious awards and has worked in numerous outstanding institutions including Yale University, Microsoft Research Center, and the Hungarian Academy of Sciences. His Abel Prize for significant contributions to theoretical computer science and discrete mathematics is therefore fully deserved. |
Our AuthorsWe are high school and college students from around the world who are passionate about maths, and want to share that passion with others. Categories
All
|