Teaching and I Ching

LONDON

When I started my PhD, I took on a part time job teaching a research course titled “Applied Quantum Algorithms”. I was told to expect undergraduates with a strong background in STEM subjects.

Then one student introduced themselves:

> “My name is Amara.

> I majored in philosophy many years ago.

> I am a yoga teacher and an amateur photographer.

> I have great interest in I Ching,

> I came here because I hope to understand I Ching in a scientific way.

> My primary aim this year is to upgrade every cell in my brain and my body.

> I think this course is a great method to help me achieve my aim.

> I am not good at computers, but I hope we can make a breakthrough in quantum computing by finding the hidden wisdom in I Ching.”

Such words raise red flags for physicists.

The I Ching is an ancient Chinese book about divination. It advocates that we accept change and understand its patterns so we can live peacefully and harmoniously. It contains a formal system of 64 figures called “hexagrams” that build upon the dual concepts of Yin and Yang. Each hexagram corresponds to a type of scenario one might encounter in life and the text provides advice for how one should approach it.

It’s fascinating, but it has nothing to do with algorithms for quantum computers. I was planning to teach students the postulates of quantum computing and some basic quantum algorithms. My curriculum did not prioritise spiritual growth.

I wonder what sequence of events led to her signing up for my course. The word “quantum” is dangerously alluring, often misappropriated to give scientific legitimacy to baseless ideas. “Quantum healing,” the “quantum realm” in Marvel films, and now the quantum wisdom of the I Ching. This works because few understand it. Allegedly, not even physicists. Feynman is quoted as saying: “If you think you understand quantum mechanics, then you don’t”. But I think this quote misrepresents the situation, because a lot of people do understand a lot of things about quantum mechanics even if they find some of it counterintuitive. Importantly, we know enough about it that you are not entitled to your own opinion about quantum mechanics. She must have read something that carelessly used the word quantum.

Amara was questioning excessively. She refused to accept the physical laws that govern quantum information, which form the basic assumptions of quantum computing. Her initial progress was painstakingly slow. She asked philosophical questions that sprawled far beyond her technical grasp. After I explained the mathematics of a simple scenario of two entangled qubits, she asked me if parents were entangled to their children or whether wearing clothes entangled them with us. I pulled out my undergraduate experience with philosophy and made a quick distinction between the use of the word “entanglement” as mathematical jargon, and its use in poetic metaphors.

One day I asked the class to list examples of quantum logic gates they had come across. Amara excitedly began reading from detailed notes she’d prepared over the week, confidently naming gates and describing their functions. At the end, she smiled and said: “I knew you would ask, so I prepared.”

It came as a surprise, but I still believed that she was likely to lose interest in the maths eventually and judge the course to be too different from her expectations. I said to her, “Great work! It will all pay off in the end, as linear algebra is the language of the universe.” 

After that, Amara began coming to class armed with precise, well-thought-out questions about exercises from a quantum computing textbook she’d ordered online. She found it all challenging and clearly worked many more hours each week than other students, but she was becoming socialised with the rigor of mathematical sciences. Yet even after this transformation, once in a while she would passionately bring up philosophy, for example suggesting that the quantum interference of computational branches could symbolize a deeper cosmic balance.

Eventually, she cited a Calvin and Hobbes comic:

“Calvin: You know, I don’t think math is a science, I think it’s a religion.
Hobbes: A religion?
Calvin: Yeah. All these equations are like miracles. You take two numbers and when you add them, they magically become one NEW number! No one can say how it happens. You either believe it or you don’t.”,

and she commented:

“I think quantum is a religion too. You either believe it or not. Sorry for using the non-jargon words, I will try my best to use precise and serious words.”

Plato insisted on ten years of mathematical training before studying philosophy. Mathematics trains the mind in logical reasoning from sound facts, whereas philosophy grapples with tentative ones. I’m glad that Amara was multiplying matrices competently by the end of the course. That was a victory for me. I’m also glad she kept sharing her musings.

We all get into science because of our grandiose and crazy ideas. Excitement is important. But socialising and disciplining someone into the technicalities and procedures of science is also important. 

Or perhaps Amara was playing along and exemplifying the openness to change advocated by the I Ching. 

(Name and details of the student were changed to protect their identity)

The Barrier is only as high as we make it

PARIS

Today is Singapore’s National Day. I’m in Paris (not Marseille) looking for a stream to watch Max Maeder win a medal. Yesterday I saw the Indian Men’s Hockey team, led by Harmanpreet Singh, win the Bronze Medal.

I would like to repost a reader submission from my father that was published 19 years ago in TODAY newspaper. He writes well, and I hope he will write more soon.

WRONG = BOMB

LONDON

Check out this song about von Neumann and the nuclear bomb. I have bolded the parts of the lyrics I really like.

[Verse]
Von Neumann, theory crafting, bomb strategist
Genius mind, splitting atoms, grab the catalyst
Blueprints in hand, equations never static
Thinking nuclear, moves that ain’t diplomatic

[Verse 2]
Manhattan squad, minds sharp as diamond drills
Geopolitical checkmates, no cheap thrills
Cold War calculus, the game ain’t sane
Push a button, whole regions go up in flames

[Chorus]
Brains vs. brawn, equations in the dusk till dawn
Neumann’s logic strong, where the wrong leads to bomb
Numbers crunch, the world holds on, atomic chess drawn
King to E4, and the pawns just gone

[Verse 3]
Coding warfare, with every algorithm’s heart
Cipher tight as a bomb shelter, tricks up the cart
Data strings, flipping bits to blaze
Mankind’s fate, pressed under theories and gaze

[Bridge]
Eyes on the future, past just an afterthought
Calculated endgames, the world’s store bought
Nuclear fission, Neumann’s vision
Logic’s precision leaves no decision

[Chorus]
Brains vs. brawn, equations in the dusk till dawn
Neumann’s logic strong, where the wrong leads to bomb
Numbers crunch, the world holds on, atomic chess drawn
King to E4, and the pawns just gone

Miraculously, this song is AI generated. Try Suno here: https://suno.com/invite/@perturbingchirp432

Hand drawn circles in Logo

TREVONE

I was introduced to my first programming language at age nine: Logo. This was part of the two-decades-long effort by my father to make me a computer scientist.

Logo is a programming language where you control a virtual pen (called the “turtle”) on the screen and draw things. Logo was built for children to get familiar with programming. It’s kind of like Microsoft Paint, but you write code to control the cursor.

Apps to write and run Logo are almost always structured like a Read-Execute-Print-Loop (REPL), which is jargon describing how after each command you write for the computer, you see the outcome before writing the next line, et cetera.

If you’d like to give it a try, download Logo here.

But I never got hold of a language reference manual as a child. The only language features I knew were: forward, backward, right, left, repeat, penup and pendown. You can make some polygons, circles and stars with these keywords, but not too much more.

I knew many things were possible from the inspiring demo that ships with this implementation of Logo but I didn’t know what the keywords to use them were.

Yesterday on a train from London to Cornwall I downloaded Logo again after 15 years and gave it another go. At age nine, I wouldn’t even have known to ask for a language reference manual. At 25, I know how to find and read one, and what to expect it to contain.

I wanted to play around with loops and randomness. First take a look at this simple program to draw a circle. It repeats 360 times, moving forward one dot, and then rotating 1 degree clockwise.

I modified the program to rotate a random number of degrees between each forward move, and to repeat for longer than 360.

This is cool, it makes some sort of loopy doodles that look hand drawn. It made me wonder – can I draw a circle that looks hand drawn?

The first attempt would be to just repeat this loop 360 times to complete a circle, and to ensure that if we are moving forward by one dot, then the rotated angle is 1 degree in expectation, even if it is drawn at random.

Here’s what that looks like (I made it draw five so you can see the variety).

for [x 0 600 135] [pu setpos [-400 0] setheading 0 rt 90 fd :x pd lt 90 repeat 360 [fd 1 rt (random 21)/10]] hideturtle

These are alright, and definitely look like hand drawn circles. But whenever I hand draw my circles, I always make sure the ends meet. I wanted to incorporate that into my circles as well.

I thought about how I might do that, maybe I could track the total angle I have rotated so far, and ensure that not only is the average angle rotated 360 degrees, but make sure that I rotate exactly 360 degrees each time. But some experiments with that showed me that that’s not how the mathematics of this works. The order in which we do forwards and rotates matters, and one doesn’t get a circle just by ensuring a total of 360 forwards and 360 angles rotated in some random order.

I thought about it for a while longer just before bed and figured it out. It took two tricks:

  1. The turtle starts at a position [0 0]. Throughout the drawing of a perfect circle, it’s x position increases to positive values and then returns to 0, but it never becomes negative. In the above incomplete circles, you can see circles 1, 2 and 5 having this issue of finishing further left than they started. I coded up the logic to ensure that if the turtle crosses into negative x values it should immediately rotate itself to point vertically and complete the circle. This is reminiscent of hand drawn circles that have a short straight edge near to where the two ends are made to meet
  2. The other problem was when the turtle didn’t return to [0 0] because it stopped too far to the right. This is the problem in incomplete circle 4 above. For this I added a hacky solution that after rotating 340 degrees, the turtle just goes straight, after which at some point it will cross into negative x values and fall into the logic of trick 1.
setpos [0 0] repeat 364 [ifelse (and (heading > 340) ((first pos) > 0)) [fd 2 + random 3] [ifelse ((first pos) < 0) [setheading 0 fd 2 + random 3] [fd 2 + random 3 rt 1]]] while [((last pos) < 0)] [fd 1]

This was hacky but it worked well. Here is a random circle completed only with the logic of trick 1

And here is one completed primarily with trick 2.

This was really fun to do. I’ve had the weight of the world on my shoulders as a privileged computer science student. There’s an infinity of potential projects to build and companies to start. You always feel like you should be doing more, that you could have done so much more by now.

It’s nice to reconnect with the simpler time of drawing shapes on a screen. When programming was just for fun, not political nor profitable.

I hope to continue this momentum and code for pleasure more often.

Book review: Elementary Number Theory by David Burton

Book review: Elementary Number Theory by David Burton

LONDON

Introduction

Over the Christmas break, I had the pleasure of reading Elementary Number Theory by David Burton. I picked this book up from the office bookshelf just as I left home for the break. I had studied number theory for maths olympiads in high school. Back then, I had owned some other number theory textbook, but I never made it past the second chapter. I was a very busy high school student. I was trying to make it to the IMO, but I was also trying to do too many other things, so I never made it. This is one of the failures I have regretted the most in my life, and that has left me with a slight unease whenever I confronted maths olympiad topics like number theory, inequalities and Euclidean geometry. It turns out – all I had to do was give it some time and read good textbooks.

Number theory is the study of integers and their properties. I picked up Elementary Number Theory because number theory has surfaced as an important tool in my research. I was doing something in which the following question arose:

Let p_i denote the i-th prime number, that is p_1 = 2, p_2 = 3, p_3 = 5 and so on.
The function s(k), is defined as the sum of the first k primes. That is, s(k) = p_1 + ... + p_k. How fast does s(k) grow? Is it roughly linear in k? or quadratic? or something else?

(There are mathematical interruptions throughout this book review, but you don’t have to read them all)

The great computer scientist Donald Knuth once said, “Virtually every theorem in elementary number theory arises in a natural, motivated way in connection with the problem of making computers do high-speed numerical calculations”. I experienced this natural connection between number theory and computer science first hand in my research in quantum computing. This is especially remarkable because before the advent of computing, number theory was thought to be a discipline “unsullied by any application”.

Apart from my trauma from maths olympiad, another reason that I feared number theory is that contemporary number theorists work on some of the hardest problems in mathematics. In my first year at Oxford, I attended a lecture by Andrew Wiles, which I excitedly told everyone about as if I had attended a concert, but in truth I learnt nothing there. Andrew Wiles is a famous mathematician who solved a long-standing open problem called Fermat’s Last Theorem, but this achievement took an arduous 10-year effort on his part. So great is his achievement that the Oxford Maths Institute building is named after him.

The buzzwords Riemann Hypothesis, Twin Prime Conjecture, and Fermat’s Last Theorem were what I thought number theory was about: lots of very difficult open questions that require decades of study to crack open. As a mathematician with a more practical bent, I thought it best that I avoid such difficult problems.

Praise

All this fear and trauma is now gone. Elementary Number Theory is my new favourite book. There are three things about this book that make it excellent. The first is that it offers a complete and systematic treatment of elementary number theory. “Elementary” in the title refers to the fact that the book only uses proof techniques that are taught to high school students. Apart from comfort with mathematical writing, the only mathematical background needed for this book is high school algebra, and basic proof techniques like induction and proof by contradiction. Burton’s work is therefore a treatise on everything that can be understood clearly and distinctly in the realm of number theory using a basic toolkit. Moreover, the fact that the book organizes the topics so well and gives a thorough treatment of each topic makes the work a great reference book. Someone recently mentioned to me in a conversation that the best way to learn something is not to read a textbook but rather to organize the information in a way that your brain is ready to accept. The linear flow of a textbook is supposedly unwelcome to our brains. While this may be true of other textbooks, I think Burton’s Elementary Number Theory is structured so as to fit in your brain.

The second admirable quality of this book is its coverage of the history of number theory. Every chapter in the book begins with a few pages of prose describing the mathematician whose work is going to be featured in that chapter. I have learned many interesting things about Euclid, Pythagoras, Fermat, Euler, et cetera. The quality of the scholarship is of a top level, for the author can even tell us which textbooks these great men learned their number theory from and how that influenced their writing and work. Reading Burton has made me want to obtain copies of the small number of canonical number theoretic texts that have accompanied humanity for the last two and a half thousand years such as Euclid’s Elements and Diophantus’ Arithmetica. What’s more, many of the exercises in the book are problems that great mathematicians created and wrote down in their treatises or letters to each other.

Finally, the book’s confidence in the face of any problem, no matter how big or how small, was inspiring to me as a young researcher. After setting up fairly basic notions like division and the greatest common divisor, Chapter 3 of the textbook concerns Goldbach’s Conjecture! Goldbach’s Conjecture states that every even integer greater than two can be written as the sum of two prime numbers. This is exactly the kind of long-standing open mathematical problem that shied me away from number theory in the past. Why would a textbook titled Elementary Number Theory have Chapter 3 on Goldbach’s Conjecture? I realized that the chapter was about what can be said about Goldbach’s Conjecture using elementary mathematics. While the final resolution of such large open questions might only come from more advanced techniques, elementary techniques can still do something for the problem. Elementary techniques can, for example, clarify what key theorems or lemmas need to be tackled with more advanced techniques. They can also point out how slight modifications to the question make the question break open in a very easy way. For example, although it is hard to prove Fermat’s Last Theorem in general, to prove it for the case of the fourth power is just one page in this textbook. A short argument in the book also establishes that Fermat’s Last Theorem need only be proved for prime powers for the whole result to follow.

Fermat’s Last Theorem: For n > 2, no integer solutions (a,b,c) exist for the equation a^n + b^n = c^n.

For example we definitely have things like 13^1 + 2^1 = 15^1 and even 3^2 + 4^2 = 5^2, but if someone wrote down 13^5 + 16^5 = 17^5, you can be sure this is wrong because of Fermat’s last theorem.

It took 350 years to prove this theorem for all n. For the case where n=4, there is an elementary proof covered in Elementary Number Theory.

A tour of Number Theory

I will now describe the contents of this book, and thus at the same time, give an overview of elementary number theory.

Induction and Well Ordering

Number theory is about integers. We articulate and prove a large number of properties of the integers.

Every whole number is either zero, or it is the successor of a whole number.

One set of tools to prove theorems about whole numbers (non-negative integers) comes from mathematical induction. Whole numbers can be seen as built from the number zero, and by the successor function. This axiomatic characterisation is of great utility in proofs. There are infinitely many whole numbers, to prove some property of all of them we have to tame this infinity. One way to do it, is to tackle these two primitives: zero and the successor function. The principle of mathematical induction says that one can prove something about the entire infinite set of numbers by simply proving it for zero and also proving that if the fact holds for some number, it will also hold for its successor. The principle of mathematical induction, like other techniques we will see, is thus a way of taming the infinite size of the set of all numbers.

Induction example: How can you prove that an every domino in an infinte chain of dominos will fall if the first one is pushed?
Answer: We already know the first domino falls because we know it is pushed. We also know that if the i-th domino falls, then the one next to it (the (i+1)-th domino), will also fall. Thus by the Principle of Mathematical Induction, every domino will fall.

A related result is the well-ordering principle, which states that any set of positive integers has a minimum element. While obvious, this is a powerful statement that enables the proof technique called “minimal counterexample”. Sometimes, you can prove something just by arguing that if exceptions existed, there would be a smallest exception, and that the existence of a smallest exception would lead to a contradiction. Some sets can’t exist because they can’t support a smallest element.

Boring numbers: While this is not a real mathematical proof it serves to illustrate the proof by minimal counterexample.
Every number has some cool property. 1 acts as identity when you multiply by it, 2 is the only even prime, 3 is the smallest odd prime, 4 is both 2+2 and 2 x 2, etc.
Prove that there is no “boring” number.
Pseudo-proof (by minimal counterexample): Suppose (for the sake of proof by contradiction) that there exist boring numbers. Consider the set of all boring numbers, and take the smallest number in that set. This number would have the cool property that it is the smallest boring number. This is a contradiction, as this number is both boring (it’s in the set of boring numbers) and cool (it is the smallest boring number). Therefore there are no boring numbers.

Division

Number theory gets really interesting when the notions of division, prime numbers, and the greatest common divisor are introduced. Addition, subtraction, and multiplication are straightforward in the sense that you can always add, subtract, or multiply any two given integers. Division is different. Dividing two integers might not result in an integer. There’s a lot more structure in division to understand and explain. Number theory properly begins by formally defining division and with it, the notions of quotient and remainder.

Division: For any pair of integers n\geq 0 and d > 0, we can write n = dq +r, where q and r are non-negative integers, and r < d. We then call n the dividend, d the divisor, q the quotient, and r the remainder.
If r=0, we say that d divides n, or that n is divisible by d.

Division gives us a different way of taming infinities. We can partition the infinite set of integers based on remainders for some fixed divisor. For example with the divisor 2, we can partition numbers into the set of even numbers (remainder = 0) and odd numbers (remainder = 1). To prove something for all numbers, we then just have to consider two cases: odd and even.

Primes and greatest common divisor

As we tame infinities, we have to reckon with the fact that some interesting properties don’t apply to all numbers. A prime number is one that has no divisors other than one and itself. This is important in number theory, as some important facts don’t apply to all numbers. Often, they apply only to prime numbers (or sometimes only to powers of prime numbers, or only to odd primes, etc.).

What’s special about prime numbers is that they are building blocks for all other numbers, under the lens of multiplication. We saw earlier how all numbers can be built from 0 and the successor function – suggesting that from the perspective of addition, these two tools are all you need to build all the numbers. Multiplication is very different. To be able to build all numbers by multiplying some simpler numbers, you need an infinitely large set of numbers: these are the prime numbers. This insight is captured by the Fundamental Theorem of Arithmetic, which states that every number can be written as the product of primes in a unique way.

The GCD (Greatest Common Divisor) of two numbers is the largest number that divides them both. If two numbers have a GCD of 1, they are said to be relatively prime. When proving facts in number theory about pairs of numbers, it is often the case that some theorem holds only for pairs of relatively prime numbers. For example 14 = 2 x 7 and 15 = 3 x 5 are relatively prime. There’s no number other than 1 that divides both of them. However 15 = 3 x 5 and 35 = 5 x 7 are not relatively prime, they have a GCD of 5.

The rest of the book builds stronger tools from the basic tools mentioned above. It also applies all these tools to natural questions.

Modular Arithmetic

Using the theory of division and remainders, we can develop one of the most widely used tools in number theory: the theory of congruences, also known as modular arithmetic (from the root word modulus, NOT module). Modular arithmetic is like the maths you do on a clock. If the time is 1700 hrs, then 10 hours later is not 2700 hrs, but rather 0300 hours. Time of day loops back and 2400 is “equivalent” to 0000.

With this same idea, we define modular arithmetic as shown:

Definition of Modular Arithmetic
If a and b have the same remainder when divided by d, we write this in modular arithmetic as: a \equiv b \mod d.
Examples:
11\equiv 3 \mod 2
24 \equiv 1254 \mod 10.

Modular arithmetic is used, as discussed above, to divide the set of all numbers into a small list of cases where we can be sure all numbers within a case behave the same. If we work modulo d, then we have at most d cases to consider. The number of cases can be less if we know something else about the number. For example a square number can only be 0 or 1 mod 4. When proving facts about square numbers, we often use this to divide into two cases and prove them separately.

Application of modular arithmetic:
The last digit (mod 10) of a square number must be: 0,1,4,5,6,9
The last two digits (mod 100) of a square number must come from the following list:
01, 21, 41, 61, 81,
04, 24, 44, 64, 84,
09, 29, 49, 69, 89,
00, 25,
16, 36, 56, 76, 96

We can use this to quickly check if a number is NOT a square. E.g. 128317566 is definitely not a square number. The test is inconclusive in the case of 132480176, as this might be a square number but isn’t definitely one.

Algebra in modular arithmetic

Modular arithmetic also sets up a nice world in which to do algebra. Notice how modular equivalence behaves like equality in many ways:

Modular equivalence is a lot like equality
x + y \equiv y + x \mod d
If x \equiv y \mod d and y \equiv z \mod d, then x \equiv z \mod d.
If x \equiv y \mod d and w \equiv z\mod d, then w +x \equiv y+z \mod d.
xy \equiv yx \mod d.
If x \equiv y \mod d then for any positive integer k: x^k \equiv y^k \mod d

We have to learn to walk again in the modular world. In school, we learn how to solve linear and quadratic equations over real or complex numbers in high school. So, very naturally, number theory has also considered linear and quadratic equations in modular arithmetic. In modular arithmetic, solving these equations requires a different set of techniques. This is the subject of Sections 2.4, 4.4, and Chapter 9.

Linear equations in modular arithmetic
ax + b = 0, can be solved easily: x = -b/a , as long as a \neq 0.

Now consider ax + b \equiv 0 \mod d.
We can rewrite it as ax \equiv -b \mod d, but how do we divide by a?

This introduces the concept of modular inverses.

For some pairs (a,d), there exists a number a^{-1} \mod d such that a \cdot a^{-1} \equiv 1 \mod d

When this exists, we get the solution x \equiv a^{-1} b \mod d.
But when does this exist?
The answer is: whenever gcd(a,d) = 1.

This exemplifies what was mentioned above that concepts like prime numbers and GCD are important because some properties only hold for prime or relatively prime numbers.

Quadratic equations in modular arithmetic
Consider ax^2 + bx + c \equiv 0 \mod p, where p is prime.
The way such equations are solved involves some algebra trick similar to completing the square to reparameterise and obtain the simpler equation:
y^2 \equiv k \mod p

This equation doesn’t always have a solution.
So we just have to understand this very natural problem, namely: which numbers have square roots in modular arithmetic? Remember that we looked at this problem in the case of mod 10 and mod 100 above.
There is very clear set of rules to help us determine this, see the topics: Legendre symbol and Quadratic reciprocity law.

Then there’s the Chinese remainder theorem, which is about how we can combine different modulo facts together.

Chinese Remainder Theorem
Example: There are certain things whose number is unknown. If we count them by threes, we have two left over; by fives, we have three left over; and by sevens, two are left over. How many things are there? (Sunzi)
That is, find x where
x\equiv 2 \mod 3,
x\equiv 3 \mod 5, and
x \equiv 2 \mod 7 .
Answer: We can combine these three equivalences to the following:
x \equiv 23 \mod 105
So the number of items is one of: 23, 128, 233, …

Chapter 5, 7 and 8 are about exponentiation in the modular world. A common pattern for math olympiad questions looks like: Find the remainder when 2^{2024} is divided by 11. Two theorems known as Fermat’s Little Theorem, and Euler’s Totient Theorem capture these situations very well. They tell us some conditions under which a^b \equiv 1 \mod d , which allows us to quickly simplify large exponentials.

We can also say more fine grained things about exponentiation. Consider:

3^1 \equiv 3 \mod 7
3^2 \equiv 2 \mod 7
3^3 \equiv 6 \mod 7
3^4 \equiv 4 \mod 7
3^5 \equiv 5 \mod 7
3^6 \equiv 1 \mod 7
3^7 \equiv 3 \mod 7

as opposed to

2^1 \equiv 2 \mod 6
2^2 \equiv 4 \mod 6
2^3 \equiv 2 \mod 6

By raising 3 to different powers modulo 7, we are able to get all the numbers from 1 to 6, however when raising 2 to different powers modulo 6, we only get 2 and 4. We say that 3 is a primitive root modulo 7.

There is a complete characterisations of which moduli have primitive roots, and how many. Primitive roots are really useful because they allow us to systematically solve equations of the form x^k \equiv a \mod d, which is a very natural algebra problem. They are also an important proof technique giving us nice theorems about orders (how long is the cycle when exponentiating modulo something) and indices (the “logarithm” in the modular world).

Miscellaneous topics

Chapter 6 defines multiplicative functions – a natural class of functions in which many important number theoretic functions fall. It also describes the the Divisor Convolution and the Möbius Inversion Formula, which allow us to reason about such functions. I was really impressed by these concepts, and their use in a beautiful proof. Understanding this proof was really the moment while reading this book that I realised how much fun I was having. Let \psi(k) denote the number of integers modulo p that have order k. It was shown in the book that \psi = \phi (that is, it’s equal to Euler’s totient function). This proof rested on properties of multiplicative functions in general, equipped with which we can conclude the functions are equal just from the fact that \psi and \phi are both multiplicative, and that they satisfy \sum_{k|n} \psi(k) = \sum_{k|n} \phi(k) =n.

Chapters 10, 11, and 12 concern interesting theorems and serve as ground on which to test the tools developed earlier in the book. One interesting result from these chapters is that every integer can be written as the sum of four square numbers, you never need more. Another thing to know is that we have a complete theory of all Pythagorean triples; we know the formula to generate all of them. I love that when the power is 3 and above we have no solutions (Fermat’s Last Theorem), but when its 2 we have infinitely many and we know all of them.

Pythagorean triples
All the positive integer solutions of x^2 + y^2 = z^2 are of the form:
x = 2kst
y = k(s^2 - t^2)
z = k(s^2 + t^2)
where s>t are any relatively prime numbers that are not both odd, and k is any positive integer.
Any Pythagorean triple can be generated from these formulas.

Finally, Chapter 13 sets up the interesting theory of continued fractions. Continued fractions turn out to be an alternative scheme for representing numbers. Instead of representing a number in decimal form, we can represent it as a continued fraction. I had learned about continued fractions in primary school maths olympiads – I always thought they were nothing more than a contrived way of testing young kids on their mathematical ability. However, there is a theory of continued fractions which is very natural and linked to Diophantine equations (equations where we are only interested in integer solutions). It is also important for finding rational representations and approximations of numbers.

Continued fraction representation of Euler’s number
While e = 2.71828182845904523... has a very random looking decimal representation, it’s continued fraction representation has a pattern:
e = 2 + \cfrac{1}{1 + \cfrac{1}{2 + \cfrac{2}{3 + \cfrac{3}{4 + \cfrac{4}{5 + \cfrac{5}{6 + \cfrac{6}{7 + \cfrac{7}{8 + \ddots}}}}}}}}

Finally, I should mention that throughout the book, a number of algorithms and heuristics are given to achieve common number theoretic computations. These include how to find the GCD (Greatest Common Divisor) of two numbers efficiently using Euclid’s algorithm, how to factorize using Fermat’s factorization method, how to check divisibility by some special numbers using techniques developed through modular arithmetic, and so on.

I started this journey because of a question about the distribution of primes that appeared in my research. Coincidentally this was the subject of an appendix! As a close friend advised me once on reading textbooks: make sure there are some topics at the end of the book that you really want to understand, it will motivate you to finish the book. Perfect!

Elementary Number Theory is a book that I’m glad I read cover to cover, and I will keep it at hand as a reference for all my number theory needs (whether research or math olympiad teaching). If I were designing a degree programme for computer scientists I would include a semester on number theory instructed through this book. This book has introduced me to the joy of reading textbooks cover to cover and I hope to keep this going. I hope reading this has given you a sense for what number theory is about, and how important a good textbook can be.

Appendices

Stack

Here is an excerpt from the book on history:
“During his stay in Berlin, Euler acquired the habit of writing memoir after memoir, placing each when finished at the top of a pile of manuscript. Whenever material was needed to fill the Academy’s journal, the printers would help themselves to a few papers from the top of the stack. As the height of the pile increased more rapidly than the demands made upon it, memoirs at the bottom tended to remain in place a long time. This explains how it happened that various papers of Euler were published, while extensions and improvements of the material contained in them had previously appeared in print under his name.”

Contents

Chapter 1. Some Preliminary Considerations

  • 1.1 Mathematical Induction
  • 1.2 The Binomial Theorem
  • 1.3 Early Number Theory

Chapter 2. Divisibility Theory in the Integers

  • 2.1 The Division Algorithm
  • 2.2 The Greatest Common Divisor
  • 2.3 The Euclidean Algorithm
  • 2.4 The Diophantine Equation ax + by = c

Chapter 3. Primes and Their Distribution

  • 3.1 The Fundamental Theorem of Arithmetic
  • 3.2 The Sieve of Eratosthenes
  • 3.3 The Goldbach Conjecture

Chapter 4. The Theory of Congruences

  • 4.1 Karl Friedrich Gauss
  • 4.2 Basic Properties of Congruence
  • 4.3 Special Divisibility Tests
  • 4.4 Linear Congruences

Chapter 5. Fermat’s Theorem

  • 5.1 Pierre de Fermat
  • 5.2 Fermat’s Factorization Method
  • 5.3 The Little Theorem
  • 5.4 Wilson’s Theorem

Chapter 6. Number-Theoretic Functions

  • 6.1 The Functions and o
  • 6.2 The Möbius Inversion Formula
  • 6.3 The Greatest Integer Function

Chapter 7. Euler’s Generalization of Fermat’s Theorem

  • 7.1 Leonhard Euler
  • 7.2 Euler’s Phi-Function
  • 7.3 Euler’s Theorem
  • 7.4 Some Properties of the Phi-Function
  • 7.5 An Application to Cryptography

Chapter 8. Primitive Roots and Indices

  • 8.1 The Order of an Integer Modulo n
  • 8.2 Primitive Roots for Primes
  • 8.3 Composite Numbers Having Primitive Roots
  • 8.4 The Theory of Indices

Chapter 9. The Quadratic Reciprocity Law

  • 9.1 Euler’s Criterion
  • 9.2 The Legendre Symbol and its Properties
  • 9.3 Quadratic Reciprocity
  • 9.4 Quadratic Congruences with Composite Moduli

Chapter 10. Perfect Numbers

  • 10.1 The Search for Perfect Numbers
  • 10.2 Mersenne Primes
  • 10.3 Fermat Numbers

Chapter 11. The Fermat Conjecture

  • 11.1 Pythagorean Triples
  • 11.2 The Famous “Last Theorem”

Chapter 12. Representation of Integers as Sums of Squares

  • 12.1 Joseph Louis Lagrange
  • 12.2 Sums of Two Squares
  • 12.3 Sums of More than Two Squares

Chapter 13. Fibonacci Numbers and Continued Fractions

  • 13.1 The Fibonacci Sequence
  • 13.2 Certain Identities Involving Fibonacci Numbers
  • 13.3 Finite Continued Fractions
  • 13.4 Infinite Continued Fractions
  • 13.5 Pell’s Equation

Appendix: The Prime Number Theorem

Singapore travel guide

SINGAPORE

I wrote this up for 6 friends that visited Singapore in October 2023. It has been rare until now for my friends from Britain to visit Singapore. This was the first time I really had to show anyone around. I expect to host many more friends from Europe and America in the years to come.

Main things you should know about Singapore:

  • Geographically fortunate to be located on Maritime trade routes connecting India/China/South East Asia
  • Established as a British colony in 1819
  • Briefly under Japanese occupation 1942-1945
  • Briefly part of Malaysia after independence from 1963-1965
  • Independent since 1965. 
  • No natural resources, less than half the size of London but its a whole country.
  • 5.6 million population – Three main people groups: Chinese, Malays and Indians. Lots of diversity and mixing of cultures.
  • Lingua franca: English/Singlish
  • Total quantum investment: ~ GBP 200 million. 5-6 quantum startups, one large Centre for Quantum Technologies
  • Top 5 in the world in GDP per capita. One of the safest, cleanest, and most well ordered places in the world.

Tourist attractions

Main areas to explore in Central Singapore:

(I have listed them in order in which you could choose to walk through and see them, I think you will need two days to enjoy all of them so pace yourself accordingly)

  • Little India
  • Kampong Glam (Malay heritage area)
  • Bugis street (shopping)
  • Fort Canning Park
  • Singapore River (You can take a boat ride on it, Clarke Quay has good nightlife)
  • Chinatown (good food and a street market)
  • Marina Bay
  • Marina Bay Sands
  • Gardens by the Bay

Make sure to visit Jewel at Changi Airport either on your way in or out of Singapore

Other attractions:

  • Sentosa Island
  • Universal Studios
  • Botanic Gardens
  • Orchard Road (shopping)
  • Bird Paradise
  • Singapore Zoo
  • Night Safari
  • River Safari

Malls:

  • Vivo city
  • Shoppes at Marina Bay Sands
  • Jewel at Changi Airport
  • Orchard Road has many malls

Bars:

  • Long Bar at Raffles Hotel

Nature:

  • Lazarus Island
  • Pulau Ubin
  • Tree top walk

Hawker Centres:

  • Lau Pa Sat (go at night, they close a road to set it up)
  • Satay by the Bay (upmarket)
  • People’s Park Complex (big hawker centre in Chinatown)
  • Newton Food Centre (dinner)
  • Makansutra (upmarket)
  • Maxwell Food Centre (lunch)
  • Tekka centre (hawker centre and market in Little India)

I spent 5 days on a narrowboat

I spent 5 days on a narrowboat

LONDON.

I went on a canalboat holiday with Mayank, Raj and Ashwin. I found that canalboating was pretty easy, beginner friendly and I realised it’s a really good holiday option in the UK (- it’s pretty cheap as well!)

We rented the boat from a town called Devizes, then drove it to Bath and back. It took us 4 days to do this, driving for roughly 5-6 hours a day. The boat moves really slowly – the speed limit on canals is 5 mph (or 8 km/h).

Devizes Map
Map of Kennet and Avon Canal that connects Bristol to Reading. (Source: Foxhangers)

Our boat was 64 feet long. It had two sleeping areas with two single beds each, two toilets, a kitchen area, a dining area, a small bow deck and a stern deck with the driving controls. The boat allegedly slept up to 8 if the beds were set up in the right way, so it felt spacious for four people. It was not too long as to be a problem to drive, though I felt that a smaller boat would have made for easier manouevrability. The facilities were in great condition, and there was a lot of helpful equipment on board (microwave, cooking hobs, oven, fridge, etc.).

Layout of Lazy Fox
Well-used kitchen on board

We were given an hour long briefing and trusted with the boat. The briefing covered:

  • an introduction to the boat and equipment
  • an introduction to the route
  • demonstration on how to do a lock
  • demonstration of how to drive the boat
  • some daily boat checks
  • rules of the road
  • guidance on mooring
  • safety and emergency procedures.

The induction was given by a gentleman working for the company we rented from, but his credibility was established when he pointed to a canalboat and said that that was his home.

No drivers license is required for canalboating in the UK. However, I felt that my time studying for the Powered Pleasure Craft Driving License in Singapore prepared me well for some aspects of canalboating such as an eye for safety, knowledge of boating terminology, and familiarity with steering and berthing.

Boat driving POV
Graphic depicting the stages in the use of a canal lock (Source: Parks Canada)

It was lovely to be out in the countryside. People were friendly and would great you as they passed along the towpath. We saw many animals and greenspaces as is usual for the country side. There was a farm we stopped at both times we passed it to get a lovely ginger and honey flavoured ice cream. We had perfect weather – five sunny days.

Along the route, we had to do locks. In order to make the canals usable in both directions, locks were placed along the canal to stop the flow of water. Locks are pairs of dams that can be open and closed in such a way as to allow boats on the canal to go uphill or downhill.

Even without the need for a license, boating is an activity requiring undivided attention and various skills that have to be developed. One incredible aspect of our trip was the willingness of passerbys and residents along the canal who were willing to stop and help us through whatever situation we were in. On the first evening we were trying to moor (i.e. “park” the boat) at a canalside pub for the night. A gentleman enjoying his summer evening at the pub came from quite a distance to help us bring the boat in. He taught us a sequence of manouevres that help turn the boat in place. He also guided us on how to pull the boat in using ropes and tie it to the bank. We used the lessons he taught us throughout the rest of our trip.

Pub mooring on first night

There were other such moments throughout our journey. As if in by design, there was a house right next to the very first lock on our journey. In this house lived a friendly man who enjoyed spending time in his yard from which he could see first time holidayboaters do their first lock.

We also had some difficulty turning our boat around. We decided not to take the boat all the way into Bath as we enjoyed a more leisurely pace. We opted instead to stop at Avoncliff Aqueduct and take a train or taxi into Bath. This meant we had to find somewhere to turn our boat around. Note that the canals are not nearly as wide as the length of the boat. We found a slightly wider area at a right angle turn after the aqueduct which had just enough space to draw a circle whose diameter would be the length of our boat. It took us about half an hour, a pole, a paddle and advice from two onlooking canalboaters to turn it around. After our turn was completed they said with admirable simplicity, “That was entertaining!”.

We also had people compliment us on a mooring manouevre. They came from across the canal to say “We live on a boat and that was excellent”. Another situation we encountered was that it was getting dark and someone came to warn us that there are no free mooring sites up ahead on the river and that its best to moor early at the free space on a watering point. We were told during the briefing not to moor at watering points as other boats might need to use them, but it seemed like the right call in this situation and we simply made sure to leave early in the morning so we wouldn’t be blocking anyone.

Crew fully engaged in doing a lock
Re-enactment of Raj muscling locks open

I enjoyed captaining the vessel. This brought tricky situations and I got to enjoy navigating the self-defining moments that come leadership. One member of the crew was repeatedly making jumps over long distances to get off the boat when we were mooring. He would do this out of impatience as the boat moves very slowly when it approaches the bank during mooring. I had to negotiate that he not make such jumps in the name of safety. In navigating this conversation, I realised that there was a difference in values between us. As someone getting into boating, I was taking pride in doing things properly and safely. For me, you don’t jump far onto the bank because you will not be able to do this as your boats get bigger, and you might as well put in the practice to get good at mooring the boat close to the bank and doing things properly. On the other hand, he did not expect to boat much. In that case you might as well do things quickly, and jumping to the bank seemed like it had a very small chance of going wrong.

However this crew member eventually made a very risky jump across a half closed lock! A fall in that situation would be a fall of a few meters near stone and metal infrastructure that could easily have led to bad cuts. Not to mention the canal water is not the cleanest, so an exposed cut in that water would require some practiced first aid and medical attention. Fortunately it didn’t go wrong but at that point it was easier for me to convince him that he was taking significant risks. The one time it did go wrong for him was when he unrealisingly jumped into a whole bush of nettle which was hurting them for hours afterwards AND they lost one of their wireless earbuds in the process. Safety 1 – 0 Haste.

The boat moves very leisurely

Another disagreement occured at our only stop at a watering point. The water tank was filling up slowly. To fill it up all the way might have taken half an hour. Over the course of 3.5 days we had only depleted the full water tank to 60% full. One crew member suggested that once the water tank was 80% full we would definitely have enough for the rest of the trip. I had a strong intuition that we should fill the water tank all the way – It was mentioned in passing during the briefing as well. Again I had to be the “boring adult” in the situation and try to defend the case of safety. I wasn’t able to do it well at the time but the next morning I woke up to the answer. If you fill a tank to 100% full, it overflows and you are absolutely sure that it is full. On the other hand, you only know that it is 80% full because of an electronic meter on the boat, which might be faulty at any time!

I am grateful that even though my crew at times disagreed with me, when it came to matters of safety they did come around when I explained the reasons to them.

Finally one proactive decision that I made was to ask one of our crew to postpone their shower to after we completed the complicated U-turn manouevre mentioned above. At first it felt like I was asking for too much as the other three were already handling the turn, but it turned out that the crew member who postponed their shower prevented us from coliding with the bank two times! In the Singapore powerboat course we were taught – “everyone has lookout duty at all times, even grandmas and babies on board”. The only reason it was hard to make this decision was that I was afraid of being too controlling of my crew, but I think this is a helpful fear to balance at the back of your mind as people do get annoyed when they are micromanaged.

We were very close to ducks (and other birds like swans and herons)

Four felt like a good number of people to share the load of the various tasks involved. One person has to drive at most times, two are needed to do a lock elegantly, and a fourth person might be engaged in cooking. Perhaps five would have been just perfect as the chef could also have a sous chef. Another pair of hands could have helped with photography as well.

In the evenings we enjoyed conversation over unending games of Hearts and the soundtrack of Om Shanti Om. Mayank and Ashwin did a fantastic job preparing all the food, notable dishes were Thai boat noodles and Butter Chicken.

Crew getting ready for dinner and enjoying the evening together
Bath

The boat rental was cheap. For four nights we paid just under GBP 200 per person. This is inclusive of fuel and insurance. We did note that the price went down between when we did our first search and when we booked the boat so I suspect the company was fearing the boat would go unbooked and put some discounts in place. We booked the boat only about two weeks before the trip. The other costs were groceries, pub trips, trains and cabs.

Feelings

The world suddenly felt bigger. Holiday boating can be enjoyed so much more, and a few months ago I wouldn’t even have thought to do it. If anyone is making a plan, please invite me to be a part of your crew. I would love to share this experience with so many people I know.

Beyond canalboating, the British waterways are an amazing public space. It is great to see the national effort to maintain them. I would like to explore them in other ways – perhaps by kayak or paddleboard. I’ve also recently been on a run along a canal in London and enjoyed that very much.

Every activity done on a boat has more meaning associated with it. Conversations, meals, thoughts, experiences – everything is enhanced by the fact that for a short while, this boat has become your whole world, and the people on it are everyone that matters for now.

I’ve always been a theoretician. I’ve enjoyed academics, maths, philosophy, theoretical computer science. It felt great to see my boating mindset and skills develop during the trip. Doing something so hands-on and improving at it has inspired me to take on new types of challenges and take pride in the way I handle real-world situations. I have particularly enjoyed the risk management perspective that boating has inculcated in me.

The trip got me really tired. I wanted to be there for every moment and didn’t rest well enough. Next time I will manage my energies better.

In summary, boating is great, let’s do it sometime!

Appendix – What are these waterways?

Waterways played a crucial role in the success of the Industrial Revolution in the UK. Canals were constructed to transport raw materials and finished products between factories and markets, allowing manufacturers to expand their operations and increase efficiency. The UK was the first country to build such a nationwide canal network. Most of the British waterways were built between the 1770s and 1830s, after which rail transport became a more popular means of transporting goods. These waterways still exist today, but are primarily used for leisure activities – such as canal boat holidays.

Further reading

This all began with my powerboat course in Singapore: read about it here.

I made an Anki deck for PPCDL/COLREG study

Find the Anki deck here: https://ankiweb.net/shared/info/1751096568

See also my other study resources for PPCDL:

I only made these to be useful in my revision, so there are many ways in which they can be better. There are also many other resources online to study from. I share my notes in the hope that my perspective on some of the points will be helpful to you. If so, please leave a comment so I am affirmed in my decision to share my learning journey 🙂

PPCDL Handling Assessment (aka PPCDL Practical Test)

I’m taking the PPCDL Practical Test tomorrow. Here are my notes to prepare.

Approach: The test is very institutionalised. You only need to focus on whats in the mark sheet. You can’t be marked down for reasons other than that.

Note that the test boat is the Dynaglass 20DX, should be the same as the boat you had your training in.

Pre-sea Check

Preparations to get Underway:

  • Boat Berthing lines: Check condition of lines and check that they are secured
  • Boat Hull: Check the condition of the hull (bow, midship, stern on both port and starboard) for any cracks or signs of damage by craning your neck over the edge of the boat to look at the part of the hull visible over the water
  • Boat Compartments: There are 5 on the 20DX. Check for flooding (any water at all must be bailed out) and rubbish.
  • License Check: Check for four things: Registration number matches that on boat, number of passengers is adhered to, Expiry date of license and read the conditions of license
  • Equipment Check: See below.
  • Passenger Check: Remind passengers to help you keep a look out for any risk of collision and to promptly inform you if there is any risk of collision. Check that everyone is wearing a life jacket.
  • Passenger Rope Assistant: Appoint an assistant to untie the ropes, starting with stern then bow and finally midship

11 Equipment check

Fire(2):

  • Fire extinguisher – check expiry date and that the gauge is pointing in the green sector.
  • Fire bucket – check the condition of attached rope

Making presence known(4):

  • Flares – check that you have 3 for open deck boat (20DX) , and that they are not expired
  • AIS – ensure mounted and green light flashing every 6 seconds
  • Horn – check it works
  • Navigation lights – turn on and check top light and side lights

Drowning related(3):

  • Life jacket – everyone on board is wearing one, and spares up to capacity of the boat should be onboard
  • Life buoy – At least one for every four people on board
  • Bailer

Boat(2):

  • Anchor – check that anchor, chain and rope are connected and in good condition
  • Oars

Preparations to start engine:

  • Propellor check: Using either the button on the side of the outboard motor, or the button on the side of the throttle, raise the propellor of the outboard motor out of the water to check the propellor for damage or entanglement. Then lower the propellor. Can also check at this time if the OBM is securely fastened to the boat.
  • Controls check: Check that the throttle moves freely and all the way in both directions, then return it to neutral. Check that the helm rotates motor all the way in both directions (free movement and following helm). This is also a good time to remind yourself how many turns the helm allows from the central position.
  • Battery check: Check that wires are firmly connected to the battery
  • Fuel check: Check that there is sufficient fuel in the tank. If necessary, prime the engine by pressing the fuel pump 4-5 times until resistance is felt.
  • Kill switch: Explain that the kill switch is meant to connect to the driver but since the examiner is a qualified driver on board, we won’t do that. Just connect the kill switch.
  • Start engine: Ask examiner for permission and start the engine
  • Cooling check: Check that the cooling system of the engine is working. You should see a stream of water leaving the engine.

Unberthing

  • Lookout: Check your surroundings to ensure it is safe to move out. Assess direction of wind and current if any.
  • Manouevring: Turn helm hard away from the jetty and engage minimal astern propulsion. Straighten the helm slightly if that helps avoid collision between bow and jetty. Reverse out of tight spaces if there isn’t enough room to make a turn safely. Maintain a lookout as you reverse and keep to starboard side of narrow channel.

Man Overboard

  • Immediate action: Slow down, confirm by looking which side the man is overboard. Turn helm hard to that side. E.g. on hearing “Man overboard Port side!” -> Slow down immediately -> Check man is really on port side -> Hard to port
  • Follow up action – buoy: Ask the crew to throw a buoy to the man: “Crew throw a buoy!”
  • Follow up action – lookout: Ask the crew to maintain a constant lookout for the man (and by right, report the bearing of the man at short intervals). Do the same as the driver.
  • Follow up action – leeward side: Manouevre boat to rescue man on the leeward side. Announce to crew: “Crew prepare to rescue man on Port/Starboard side”.
  • Retrieve man: Bring the boat to a complete stop with the man abeam of the boat and within arms reach.
  • Check condition of man

Berthing

  • Tying knots: Make sure you are familiar with both knots (tying the boat to cleats or to a bar)

Oral assessment of Theory

Refer to my other blogpost where I discuss more about PPCDL theory.

Anchoring Theory:

  • First select an area to anchor. It should be sheltered (from wind, current and traffic), approved for anchoring, have plenty of space for swinging and have good holding ground (mud or sand).
  • Use a chart to determine depth and bottom conditions. Calculate the amount of scope as 4-7x the depth of the water.
  • Check the anchor, prepare it by laying out so it wont entangle, and cleat off at the point you want it to stop. Always anchor by the bow.
  • Face the wind and move astern slowly. Lower the anchor slowly until it lies on the seabed. Then keep lowering slowly as the boat is reversing. Once the anchor is set the line will stop shaking.
  • While anchored, monitor the bearing to two or more reference points to ensure that you are not drifting.
  • To release the anchor move forward while pulling the anchor up.

Helpful resources: