Extra comparisons in Python’s timsort

Reading through the comp.lang.python mailing list, I saw an interesting question concerning the behavior of the default sorting algorithm in python. This led to this post.

Python uses timsort, a clever hybrid sorting algorithm with ideas borrowing from merge sort and (binary) insertion sort. A major idea in timsort is to use the structure of naturally occuring runs (consecutive elements in the list that are either monotone increasing or monotone decreasing) when sorting.

Let’s look at the following simple list.

10, 20, 5

A simple sorting algorithm is insertion sort, which just advances through the list and inserts each number into the correct spot. More explicitly, insertion sort would

  1. Start with the first element, 10. As a list with one element, it is correctly sorted tautologically.
  2. Now consider the second element, 20. We insert this into the correct position in the already-sorted list of previous elements. Here, that just means that we verify that 20 > 10, and now we have the sorted sublist consisting of 10, 20.
  3. Now consider the third element, 5. We want to insert this into the correct position in the already-sorted list of previous elements. A naively easy way to do this is to either scan the list from the right or from the left, and insert into the correct place. For example, scanning from the right would mean that we compare 5 to the last element of the sublist, 20. As 5 < 20, we shift left and compare 5 to 10. As 5 < 10, we shift left again. As there is nothing left to compare against, we insert 5 at the beginning, yielding the sorted list 5, 10, 20.

How many comparisons did this take? This took 20 > 10, 5 < 20, and 5 < 10. This is three comparisons in total.

We can see this programmatically as well. Here is one implementation of insertion_sort, as described above.

def insertion_sort(lst):
    '''
    Sorts `lst` in-place. Note that this changes `lst`.
    '''
    for index in range(1, len(lst)):
        current_value = lst[index]
        position = index
        while position > 0 and lst[position - 1] > current_value:
            lst[position] = lst[position - 1]
            position = position - 1
        lst[position] = current_value

Let’s also create a simple Number class, which is just like a regular number, except that anytime a comparison is done it prints out the comparison. This will count the number of comparisons made for us.

class Number:
    def __init__(self, value):
        self.value = value

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return self.__str__()

    def __lt__(self, other):
        if self.value < other.value:
            print("{} < {}".format(self, other))
            return True
        print("{} >= {}".format(self, other))
        return False

    def __eq__(self, other):
        if self.value == other.value:
            print("{} = {}".format(self, other))
            return True
        return False

    def __gt__(self, other):
        return not ((self == other) or (self < other))

    def __le__(self, other):
        return (self < other) or (self == other)

    def __ge__(self, other):
        return not (self < other)

    def __nq__(self, other):
        return not (self == other)

With this class and function, we can run

lst = [Number(10), Number(20), Number(5)]
insertion_sort(lst)
print(lst)

which will print

10 < 20
20 >= 5
10 >= 5
[5, 10, 20]

These are the three comparisons we were expecting to see.

Returning to python’s timsort — what happens if we call python’s default sorting method on this list? The code

lst = [Number(10), Number(20), Number(5)]
lst.sort()
print(lst)

prints

20 >= 10
5 < 20
5 < 20
5 < 10
[5, 10, 20]

There are four comparisons! And weirdly, the method checks that 5 < 20 twice in a row. What’s going on there?1

At its heart, this was at the core of the thread on comp.lang.python. Why are there extra comparisons in cases like this?

Poking around the implementation of timsort taught me a little bit more about timsort.2

Timsort approaches this sorting task in the following way.

  1. First, timsort tries to identify how large the first run within the sequence is. So it keeps comparing terms until it finds one that is out of order. In this case, it compares 20 to 10 (finding that 20 > 10, and thus the run is increasing), and then compares 5 to 20 (finding that 5 < 20, and thus that 5 is not part of the same run as 10, 20). Now the run is identified, and there is one element left to incorporate.
  2. Next timsort tries to insert 5 into the already-sorted run. It is more correct to say that timsort attempts to do a binary insertion, since one knows already that the run is sorted.3 In this binary insertion, timsort will compare 5 with the middle of the already-sorted run 10, 20. But this is a list of length 2, so what is its middle element? It turns out that timsort takes the latter element, 20, in this case. As 5 < 20, timsort concludes that 5 should be inserted somewhere in the first half of the run 10, 20, and not in the second half.
  3. Of course, the first half consists entirely of 10. Thus the remaining comparison is to check that 5 < 10, and now the list is sorted.

We count4 all four of the comparisons. The doubled comparison is due to the two tasks of checking whether 5 is in the same run as 10, 20, and then of deciding through binary insertion where to place 5 in the smaller sublist of 10, 20.

Now that we’ve identified a doubled comparison, we might ask Why is it this way? Is this something that should change?

The short answer is it doesn’t really matter. A longer answer is that to apply this in general would cause additional comparisons to be made, since this applies in the case when the last element of the run agrees in value with the central value of the run (which may occur for longer lists if there are repeated values). Checking that this happens would probably either involve comparing the last element of the run with the central value (one extra comparison, so nothing is really saved anyway), or perhaps adding another data structure like a skip list (which seems sufficiently more complicated to not be worth the effort). Or it would only apply when sorting really short lists, in which case there isn’t much to worry about.

Learning a bit more about timsort made me realize that I could probably learn a lot by really understanding an implementation of timsort, or even a slightly simplified implementation. It’s a nice reminder that one can choose to optimize for certain situations or behaviors, and this might not cover all cases perfectly — and that’s ok.

Posted in Programming, Python | Tagged , | Leave a comment

Speed talks should be at every conference

I recently attended Building Bridges 4, an automorphic forms summer school and workshop. A major goal of the conference is to foster communication and relationships between researchers from North America and Europe, especially junior researchers and graduate students.

It was a great conference, and definitely one of the better conferences that I’ve attended. What made it so good? For one thing, it was in Budapest, and I love Budapest. Many of the main topics were close to my heart, which is a big plus.

But what I think really set it apart was that there were lots of relatively short talks, and almost everyone attended almost every talk.1

The amount of time allotted to a talk carries extreme power in deciding what sort of talk it will be. A typical hour-long seminar talk is long enough to give context, describe a line of research leading to a set of results, discuss how these results fit into the literature, and even to give a non-rushed description of how something is proved. Sometimes a good speaker will even distill a few major ideas and discuss how they are related. A long talk can have multiple major ideas (although just one presented very well can make a good talk too).

In comparison, 50, 40, and 30 minute talks require much more discipline. As the amount of time decreases, the number of ideas that can be inserted into a talk decreases. And this relationship is not linear! Thirty minutes is just about long enough to describe one idea pretty well, and to do anything more is very hard.2

Something interesting happens for shorter talks. For 20 minute, 15 minute, and 10 minute talks, the limitation almost serves as a source of inspiration.3 Being forced to focus on what’s important is a powerful organizing force.

The median talk length was 20 minutes, which is a very comfortable number. This is long enough to state a result and give context. It’s also long enough to tempt speakers into describing methodology behind a proof, but not long enough to effectively teach someone how the proof works.

An extraordinary aspect of a 20 minute talk is also that it’s short enough to pay attention to, even if it’s only an okay talk. It is perhaps not a surprise to most conference goers that most talks are not so great. To be a skilled orator is to be exceptional.

At Building Bridges, I was introduced to math speed talks. These are two minute talks. I’ve seen many programming lightning talks (often used to plug a particular product or solution to a common programming problem), but these math speed talks were different.

People used their two minutes to introduce an idea, or a result. And they either chose to give the broadest possible context, or a singular idea in the proof.

People were talking about real mathematics in two minutes. And I loved it.

Simply having a task where you distill some real mathematics into a two minute coherent description is worthwhile. What’s important? What do you really want to say? Why?

Two minutes is so short that it feels silly. And silly means that it doesn’t feel dangerous or scary, and thus many people felt willing to give it a try. At Building Bridges, the organizers gamified the speed talks, so that getting the closest to 2 minutes was rewarded with applause and going over two minutes resulted in a buzzer going off. It was a game, and it was fun. It was encouraging.

I firmly support any activity that encourages people who normally don’t speak so much, especially students and junior researchers. You learn a lot by giving a talk, even if it’s only a two minute talk.4

This conference had 19 (I think) speed talks over a three day stretch. They were given in clumps after the last regular talk each day. Since people were there for the big talk, everyone attended the speed talks. This is also important! In conferences like the Joint Math Meetings, where there might even be something like speed talks, it’s essentially impossible to pay attention since there are too many people in too many places and you never can step in the same river twice. Here, speed talks were given on the same stage as long talks, to the same audience, and with the same equipment.

Every conference should have speed talks. And they should be treated as first-class talks, with the exception that they are irrefutably silly.

Go forth and spread the speed talk gospel.

Posted in Mathematics | Tagged , , | Leave a comment

A bookmarklet to inject colorblind friendly CSS into Travis CI

In my previous post, I noted that the ability to see in color gave me an apparent superpower in quickly analyzing Travis CI and pytest logs.

I wondered: how hard is it to use colorblind friendly colors here?

I had in the back of my mind the thought of the next time I sit down and pair program with someone who is colorblind (which will definitely happen). Pair programming is largely about sharing experiences and ideas, and color disambiguation shouldn’t be a wedge.

I decided that loading customized CSS is the way to go. There are different ways to do this, but an easy method for quick replicability is to create a bookmarklet that adds CSS into the page. So, I did that.

You can get that bookmarklet here. (Due to very sensible security reasons, WordPress doesn’t want to allow me to provide a link which is actually a javascript function. So I make it available on a static, handwritten page).1

Here’s how it works. A Travis log looks typically like this:

After clicking on the bookmarklet, it looks like

This is not beautiful, but it works and it’s very noticable. Nonetheless, when the goal is just to be able to quickly recognize if errors are occuring, or to recognize exceptional lines on a quick scroll-by, the black-text-on-white-box wins the standout crown.

The LMFDB uses pytest, which conveniently produces error summaries at the end of the test. (We used to use nosetest, and we hadn’t set it up to have nice summaries before transitioning to pytest). This bookmark will also effect the error summary, so that it now looks like

Again, I would say this is not beautiful, but definitely noticeable.


As an aside, I also looked through the variety of colorschemes that I have collected over the years. And it turns out that 100 percent of them are unkind to colorblind users, with the exception of the monotone or monochromatic schemes (which are equal in the Harrison Bergeron sense).

We should do better.

Posted in LMFDB, Programming | Tagged , , , , | Leave a comment

Seeing color shouldn’t feel like a superpower

In the last month, I have found myself pair programming with three different people. All three times involved working on the LMFDB. I rarely pair program outside a mentor-mentee or instructor-student situation.1

This is fun. It’s fun seeing other people’s workflows. (In these cases, it happened to be that the other person was usually the one at the keyboard and typing, and I was backseat driving). I live in the terminal, subscribe to the Unix-is-my-IDE general philosophy: vim is my text editor; a mixture of makefiles, linters, and fifos with tmux perform automated building, testing, and linting; git for source control; and a medium-sized but consistently growing set of homegrown bash/python/c tools and scripts make it fun and work how I want.

I’m distinctly interested in seeing tools other people have made for their own workflows. Those scripts that aren’t polished, but get the work done. There is a whole world of git-hooks and aliases that amaze me.

But my recent encounters with pair programming exposed me to a totally different and unexpected experience: two of my programming partners were color blind.2

At first, I didn’t think much of it. I had thought that you might set some colorblind-friendly colorschemes, and otherwise configure your way around it. But as is so often the case with accessibility problems, I underestimated both the number of challenges and the difficulty in solving them (lousy but true aside: most companies almost completely ignore problems with accessibility).

I first noticed differences while trying to fix bugs and review bugfixes in the LMFDB. We use Travis CI for automated testing, and we were examining a build that had failed. We brought up the Travic CI interface and scroll through the log. I immediately point out the failure, since I see something like this.3

an image from Travic CI showing "FAIL" in red and "PASS" in green.
How do you know something failed? asks John, my partner for the day. Oh, it’s because the output is colored, isn’t it? I didn’t know. With the help of the color-blindness.com color-blindness simulator, I now see that John saw something like
an image from Travic CI that has been altered to appear with contrast as a red-green colorblind person might see it. Now "FAIL" and "PASS" appear in essentially the same shade.
With red-green colorblindness, there is essentially no difference in the shades of PASSED and FAILED. That’s sort of annoying.

We’d make a few changes, and then rerun some tests. Now we were running tests in a terminal, and the testlogs are scolling by. We’re chatting about emacs wizardy (or c++ magic, or compiler differences between gcc and clang, or something), and I point out that we can stop the tests since three tests have already failed.

He stared at me a bit dumbfoundedly. It was like I had superpowers. I could recognize failures without paying almost any attention, since flashes of red stand out.

But if you don’t recognize differences in color, how would you even know that the terminal outputs different colors for PASSED and FAILED? (We use pytest, which does). A quick look for different colorschemes led to frustration, as there are different sorts of colorblindness and no single solution that will work for everyone (and changing colorschemes is sort of annoying anyway).4

I should say that the Travis team has made some accessibility improvements for colorblind users in the past. The build-passing and build-failing icons used to be little circles that were red or green, as shown here.

That means the build status was effectively invisible to colorblind users. After an issue was raised and discussed, they moved to the current green-checkmark-circle for passing and red-exed-circle for failing, which is a big improvement.

The colorscheme used for Travic CI’s online logs is based on the nord color palette, and there is no colorscheme-switching option. It’s a beautiful and well-researched theme for me, but not for everybody.

The colors on the page are controllable by CSS, but not in a uniform way that works on many sites. (Or at least, not to my knowledge. I would be interested if someone else knew more about this and knew a generic approach. The people I was pair-programming with didn’t have a good solution to this problem).

Should you really need to write your own solution to every colorblind accessibility problem?

In the next post, I’ll give a (lousy but functional) bookmarklet that injects CSS into the page to see Travis CI FAILs immediately.

Posted in LMFDB, Programming | Tagged , , , , | Leave a comment

Notes from a Talk at Building Bridges 4

On 18 July 2018 I gave a talk at the 4th Building Bridges Automorphic Forms Workshop, which is hosted at the Renyi Institute in Budapest, Hungary this year. In this talk, I spoke about counting points on hyperboloids, with a certain focus on counting points on the three dimensional hyperboloid

$$\begin{equation} X^2 + Y^2 = Z^2 + h \end{equation}$$

for any fixed integer $h$.

I gave a similar talk at the 32nd Automorphic Forms Workshop in Tufts in March. I don’t say this during my talk, but a big reason for giving these talks is to continue to inspire me to finish the corresponding paper. (There are still a couple of rough edges that need some attention).

The methodology for the result relies on the spectral expansion of half-integral weight modular forms. This is unfriendly to those unfamiliar with the subject, and particularly mysterious to students. But there is a nice connection to a topic discussed by Arpad Toth during the previous week’s associated summer school.

Arpad sketched a proof of the spectral decomposition of holomorphic modular cusp forms on $\Gamma = \mathrm{SL}(2, \mathbb{Z})$. He showed that
$$\begin{equation} L^2(\Gamma \backslash \mathcal{H}) = \textrm{cuspidal} \oplus \textrm{Eisenstein}, \tag{1}
\end{equation}$$
where the cuspidal contribution comes from Maass forms and the Eisenstein contribution comes from line integrals against Eisenstein series.

The typical Eisenstein series $$\begin{equation} E(z, s) = \sum_{\gamma \in \Gamma_\infty \backslash \Gamma} \textrm{Im}(\gamma z)^s \end{equation}$$ only converges for $\mathrm{Re}(s) > 1$, and the initial decomposition in $(1)$ implicitly has $s$ in this range.

To write down the integrals appearing in the Eisenstein spectrum explicitly, one normally shifts the line of integration to $1/2$. As Arpad explained, classically this produces a pole at $s = 1$ (which is the constant function).

In half-integral weight, the Eisenstein series has a pole at $s = 3/4$, with the standard theta function

$$\begin{equation} \theta(z) = \sum_{n \in \mathbb{Z}} e^{2 \pi i n^2 z} \end{equation}$$

as the residue. (More precisely, it’s a constant times $y^{1/4} \theta(z)$, or a related theta function for $\Gamma_0(N)$). I refer to this portion of the spectrum as the residual spectrum, since it comes from often-forgotten residues of Eisenstein series. Thus the spectral decomposition for half-integral weight objects is a bit more complicated than the normal case.

When giving talks involving half-integral weight spectral expansions to audiences including non-experts, I usually omit description of this. But for those who attended the summer school, it’s possible to at least recognize where these additional terms come from.

The slides for this talk are available here.

Posted in Expository, Math.NT, Mathematics | Tagged , , , , | Leave a comment

Splitting Easy MathSE Questions into a New NoviceMathSE Is a Bad Idea

(But there are some positive changes that can be made)

This is the final chapter in my series about the state of internet fora, and Math.SE and StackOverflow in particular. The previous chapters are Challenges Facing Community Cohesion and Ghosts of Forums Past. Unlike the previous entries, this also sits on Meta.Math.SE (and was posted there a week before here). (As I write this as a moderator of Math.SE, I refer to the Math.SE community as “we”, “us”, and “our” community).

A couple of weeks ago, there was a proposal on meta.Math.SE to introduce a third level of math site to the SE network. Many members of the the MathSE community have reacted very positively to this proposal, to the extent that even some of the moderators have considered throwing their weight behind it.

But a NoviceMathSE site would be doomed to fail, and such a separation would not solve the underlying problems facing the site.

To explain my point of view, we need to examine more closely the arguments in favor of NoviceMathSE.

Continue reading

Posted in Mathematics, SE | Tagged , | Leave a comment

Ghosts of Forums Past

This is the second in a miniseries of posts on internet fora, and Math.SE and StackOverflow in particular. In the previous entry in the miniseries, I described some of the common major problems facing community cohesion. I claimed that when communities get large, they tend to fracture and the ratio of meaningful communication to noise plummets. To combat this tendency, communities use some mixture of core moderation, peer moderation, membership requirements, or creating subcommunities/splitting off in to other communities.

In this chapter I focus more on Math.SE and StackOverflow. Math.SE is now experiencing growing pains and looking for solutions. But many users of Math.SE have little involvement in the rest of the StackExchange network and are mostly unaware of the fact that StackOverflow has already encountered and passed many of the same trials and tribulations (with varying degrees of success).

Thinking more broadly, many communities have faced these same challenges. Viewed from the point of view from the last chapter, it may appear that there are only a handful of tools a community might use to try to retain group cohesion. Yet it is possible to craft clever mixtures of these tools synergistically. The major reason the StackExchange model has succeeded where other fora have stalled (or failed outright) is through its innovations on the implementation of communition cohesion strategies while still allowing essentially anyone to visit the site.

Imaginary Internet Points

Slashdot1 popularized the idea of associating imaginary internet points to different users. It was called karma. You got karma if other users rated your comments or submissions well, and lost karma if they rated your posts as poor. But perhaps most importantly, each user can set a threshold for minimum scores of content to see. Thus if people have reasonable thresholds and you post crap, then most people won’t even see it after it’s scored badly.

Continue reading

Posted in Programming, SE | Tagged , , | 1 Comment

Challenges facing community cohesion (and Math.StackExchange in particular)

In about a month, Math.StackExchange will turn 8. Way back when I was an undergrad, I joined the site. This was 7 years ago, during the site’s first year.

Now with some perspective as a frequent contributor/user/moderator of various online newsgroups and fora, I want to take a moment to examine the current state of Math.SE.

To a certain extent, this is inspired by Joel Spolsky’s series of posts on StackOverflow (which he is currently writing and sending out). But this is also inspired by recent discussion on Meta.Math.SE. As I began to collect my thoughts to make a coherent reply, I realized that I have a lot of thoughts, and a lot to say.

So this is chapter one of a miniseries of writings on internet fora, and Math.SE and StackOverflow in particular.

Continue reading

Posted in Programming, SE | Tagged , , | 2 Comments

Paper Announcement: A Shifted Sum for the Congruent Number Problem

Tom Hulse, Chan Ieong Kuan, Alex Walker, and I have just uploaded a new paper to the arXiv titled A Shifted Sum for the Congruent Number Problem. In this charming, short paper, we investigate a particular sum of terms which are products of square-indicator functions and show that its asymptotics are deeply connected to congruent numbers. This note serves to describe and provide additional context for these results. (This note is also available as a pdf).

Congruent Numbers

We consider some triangles. There are many right triangles, such as the triangle with sides $(3, 4, 5)$ or the triangle with sides $(1, 1, \sqrt{2})$. We call a right triangle rational when all its side lengths are rational numbers. For illustration, $(3, 4, 5)$ is rational, while $(1, 1, \sqrt{2})$ is not. $\DeclareMathOperator{\sqfree}{sqfree}$

There is mythology surrounding rational right triangles. According to legend, the ancient Greeks, led both philosophcally and mathematically by Pythagoras (who was the first person to call himself a philosopher and essentially the first to begin to distill and codify mathematics), believed all numbers and quantities were ratios of integers (rational). When a disciple of Pythagoras named Hippasus found that the side lengths of the right triangle $(1, 1, \sqrt{2})$ were not rational multiples of each other, the other followers of Pythagoras killed him by casting him overboard while at sea for having produced an element which contradicted the gods. (It with some irony that we now attribute this as a simple consequence of the Pythagorean Theorem).

This mythology is uncertain, but what is certain is that even the ancient Greeks were interested in studying rational right triangles, and they began to investigate what we now call the Congruent Number Problem. By the year 972 the CNP appears in Arabic manuscripts in (essentially) its modern formulation. The Congruent Number Problem (CNP) may be the oldest unresolved math problem.

We call a positive rational number $t$ congruent if there is a rational right triangle with area $t$. The triangle $(3,4,5)$ shows that $6 = 3 \cdot 4 / 2$ is congruent. The CNP is to describe all congruent numbers. Alternately, the CNP asks whether there is an algorithm to show definitively whether or not $t$ is a congruent number for any $t$.

We can reduce the problem to a statement about integers. If the rational number $t = p/q$ is the area of a triangle with legs $a$ and $b$, then the triangle $aq$ and $bq$ has area $tq^2 = pq$. It follows that to every rational number there is an associated squarefree integer for which either both are congruent or neither are congruent. Further, if $t$ is congruent, then $ty^2$ and $t/y^2$ are congruent for any integer $y$.

We may also restrict to integer-sided triangles if we allow ourselves to look for those triangles with squarefree area $t$. That is, if $t$ is the area of a triangle with rational sides $a/A$ and $b/B$, then $tA^2 B^2$ is the area of the triangle with integer sides $aB$ and $bA$.

It is in this form that we consider the CNP today.

Congruent Number Problem

Given a squarefree integer $t$, does there exist a triangle with integer side lengths such that the squarefree part of the area of the triangle is $t$?

We will write this description a lot, so for a triangle $T$ we introduce the notation
\begin{equation}
\sqfree(T) = \text{The squarefree part of the area of } T.
\end{equation}
For example, the area of the triangle $T = (6, 8, 10)$ is $24 = 6 \cdot 2^2$, and so $\sqfree(T) = 6$. We should expect this, as $T$ is exactly a doubled-in-size $(3,4,5)$ triangle, which also corresponds to the congruent number $6$. Note that this allows us to only consider primitive right triangles.

Main Result

Let $\tau(n)$ denote the square-indicator function. That is, $\tau(n)$ is $1$ if $n$ is a square, and is $0$ otherwise. Then the main result of the paper is that the sum
\begin{equation}
S_t(X) := \sum_{m = 1}^X \sum_{n = 1}^X \tau(m-n)\tau(m)\tau(nt)\tau(m+n)
\end{equation}
is related to congruent numbers through the asymptotic
\begin{equation}
S_t(X) = C_t \sqrt X + O_t\Big( \log^{r/2} X\Big),
\end{equation}
where
\begin{equation}
C_t = \sum_{h_i \in \mathcal{H}(t)} \frac{1}{h_i}.
\end{equation}
Each $h_i$ is a hypotenuse of a primitive integer right triangle $T$ with $\sqfree(T) = t$. Each hypotnesue will occur in a pair of similar triangles $(a,b, h_i)$ and $(b, a, h_i)$; $\mathcal{H}(t)$ is the family of these triangles, choosing only one triangle from each similar pair. The exponent $r$ in the error term is the rank of the elliptic curve
\begin{equation}
E_t(\mathbb{Q}): y^2 = x^3 – t^2 x.
\end{equation}

What this says is that $S_t(X)$ will have a main term if and only if $t$ is a congruent number, so that computing $S_t(X)$ for sufficiently large $X$ will show whether $t$ is congruent. (In fact, it’s easy to show that $S_t(X) \neq 0$ if and only if $t$ is congruent, so the added value here is the nature of the asymptotic).

We should be careful to note that this does not solve the CNP, since the error term depends in an inexplicit way on the desired number $t$. What this really means is that we do not have a good way of recognizing when the first nonzero term should occur in the double sum. We can only guarantee that for any $t$, understanding $S_t(X)$ for sufficiently large $X$ will allow one to understand whether $t$ is congruent or not.

Intuition and Methodology

There are four primary components to this result:

  1. There is a bijection between primitive integer right triangles $T$ with
    $\sqfree(T) = t$ and arithmetic progressions of squares $m^2 – tn^2, m^2,
    m^2 + tn^2$ (where each term is itself a square).
  2. There is a bijection between primitive integer right triangles $T$ with
    $\sqfree(T) = t$ and points on the elliptic curve $E_t(\mathbb{Q}): y^2 = x^3
    – t x$ with $y \neq 0 $.
  3. If the triangle $T$ corresponds to a point $P$ on the curve $E_t$, then
    the size of the hypotenuse of $T$ can be bounded below by $H(P)$, the
    (naive) height of the point on the elliptic curve.
  4. Néron (and perhaps Mordell, but I’m not quite fluent in the initial
    history of the theory of elliptic curves) proved strong (upper) bounds on
    the number of points on an elliptic curve up to a given height. (In fact,
    they proved asymptotics which are much stronger than we use).

In this paper, we use $(1)$ to relate triangles $T$ to the sum $S_t(X)$ and we use $(2)$ to relate these triangles to points on the elliptic curve. Tracking the exact nature of the hypotenuses through these bijections allows us to relate the sum to certain points on elliptic curves. In order to facilitate the tracking of these hypotenuses, we phrase these bijections in slightly different ways than have appeared in the literature. By $(3)$ and $(4)$, we can bound the number and size of the hypotenuses which appear in terms of numbers of points on the elliptic curve up to a certain height. Intuitively this is why the higher the rank of the elliptic curve (corresponding roughly to the existence of many more points on the curve), the worse the error term in our asymptotic.

I would further conjecture that the error term in our asymptotic is essentially best-possible, even though we have thrown away some information in our proof.

Additional Context

We are not the first to note either the bijection between triangles $T$ and arithmetic progressions of squares or between triangles $T$ and points on a particular elliptic curve. The first is surely an ancient observation, but I don’t know who first considered the relation to elliptic curves. But it’s certain that this was a fundamental aspect in Tunnell’s famous work A Classical Diophantine Problem and Modular Forms of Weight 3/2 from 1983, where he used the properties of the elliptic curve $E_t$ to relate the CNP to the Birch and Swinnerton-Dyer Conjecture.

One statement following from the Birch and Swinnerton-Dyer conjecture (BSD) is that if an elliptic curve $E$ has rank $r$, then the $L$-function $L(s, E)$ has a zero of order $r$ at $1$. The relation between lots of points on the curve and the existence of a zero is intuitive from the approximate relation that
\begin{equation}
L(1, E) \approx \lim_{X} \prod_{p \leq X} \frac{p}{\#E(\mathbb{F}_p)},
\end{equation}
so if $E$ has lots and lots of points then we should expect the multiplicands to be very small.

On the other hand, the elliptic curve $E_t: y^2 = x^3 – t^2 x$ has the interesting property that any point with $y \neq 0$ generates a free group of points on the curve. From the bijections alluded to above, a primitive right integer triangle $T$ with $\sqfree(T) = t$ corresponds to a point on $E_t$ with $y \neq 0$, and thus guarantees that there are lots of points on the curve. Tunnell showed that what I described as “lots of points” is actually enough points that $L(1, E)$ must be zero (assuming the relation between the rank of the curve and the value of $L(1, E)$ from BSD).

Tunnell proved that if BSD is true, then $L(1, E) = 0$ if and only if $n$ is a congruent number.

Yet for any elliptic curve we know how to compute $L(1, E)$ to guaranteed accuracy (for instance by using Dokchitser’s algorithm). Thus a corollary of Tunnell’s theorem is that BSD implies that there is an algorithm which can be used to determine definitively whether or not any particular integer $t$ is congruent.

This is the state of the art on the congruent number problem. Unfortunately, BSD (or even the somewhat weaker between BSD and mere nonzero rank of elliptic curves as is necessary for Tunnell’s result for the CNP) is quite far from being proven.

In this context, the main result of this paper is not as effective at actually determining whether a number is congruent or not. But it does have the benefit of not relying on any unknown conjecture.

And there is some potential follow-up questions. The sum $S_t(X)$ appears as an integral transform of the multiple Dirichlet series
\begin{equation}
\sum_{m,n} \frac{\tau(m-n)\tau(m)\tau(nt)\tau(m+n)}{m^s n^w}
\approx
\sum_{m,n} \frac{r_1(m-n)r_1(m)r_1(nt)r_1(m+n)}{m^s n^w},
\end{equation}
where $r_1(n)$ is $1$ if $n = 0$ or $2$ if $n$ is a positive square, and $0$ otherwise. Then $r_1(n)$ appears as the Fourier coefficients of the half-integral weight standard theta function
\begin{equation}
\theta(z)
= \sum_{n \in \mathbb{Z}} e^{2 \pi i n^2 z}
= \sum_{n \geq 0} r_1(n) e^{2 \pi i n z},
\end{equation}
and $S_t(X)$ is a shifted convolution sum coming from some products of modular forms related to $\theta(z)$.

It may be possible to gain further understanding of the behavior of $S_t(X)$ (and therefore the congruent number problem) by studying the shifted convolution as coming from theta functions.

I would guess that there is a deep relation to Tunnell’s analysis in his 1983 paper, as in some sense he constructs appropriate products of three theta functions and uses them centrally in his proof. But I do not understand this relationship well enough yet to know whether it is possible to deepen our understanding of the CNP, BSD, or Tunnell’s proof. That is something to explore in the future.

Posted in Expository, Math.NT, Mathematics | Tagged , | Leave a comment

Cracking Codes with Python: A Book Review

How do you begin to learn a technical subject?

My first experience in “programming” was following a semi-tutorial on how to patch the Starcraft exe in order to make it understand replays from previous versions. I was about 10, and I cobbled together my understanding from internet mailing lists and chatrooms. The documentation was awful and the original description was flawed, and to make it worse, I didn’t know anything about any sort of programming yet. But I trawled these lists and chatroom logs and made it work, and learned a few things. Each time Starcraft was updated, the old replay system broke completely and it was necessary to make some changes, and I got pretty good at figuring out what changes were necessary and how to perform these patches.

On the other hand, my first formal experience in programming was taking a course at Georgia Tech many years later, in which a typical activity would revolve around an exciting topic like concatenating two strings or understanding object polymorphism. These were dry topics presented to us dryly, but I knew that I wanted to understand what was going on and so I suffered the straight-faced-ness of the class and used the course as an opportunity to build some technical depth.

Now I recognize that these two approaches cover most first experiences learning a technical subject: a motivated survey versus monographic study. At the heart of the distinction is a decision to view and alight on many topics (but not delving deeply in most) or to spend as much time as is necessary to understand completely each topic (and hence to not touch too many different topics). Each has their place, but each draws a very different crowd.

The book Cracking Codes with Python: An Introduction to Building and Breaking Ciphers by Al Sweigart1 is very much a motivated flight through various topics in programming and cryptography, and not at all a deep technical study of any individual topic. A more accurate (though admittedly less beckoning) title might be An Introduction to Programming Concepts Through Building and Breaking Ciphers in Python. The main goal is to promote programmatical thinking by exploring basic ciphers, and the medium happens to be python.

But ciphers are cool. And breaking them is cool. And if you think you might want to learn something about programming and you might want to learn something about ciphers, then this is a great book to read.

Sweigart has a knack for writing approachable descriptions of what’s going on without delving into too many details. In fact, in some sense Sweigart has already written this book before: his other books Automate the Boring Stuff with Python and Invent your own Computer Games with Python are similarly survey material using python as the medium, though with different motivating topics.

Each chapter of this book is centered around exploring a different aspect of a cipher, and introduces additional programming topics to do so. For example, one chapter introduces the classic Caesar cipher, as well as the “if”, “else”, and “elif” conditionals (and a few other python functions). Another chapter introduces brute-force breaking the Caesar cipher (as well as string formatting in python).

In each chapter, Sweigart begins by giving a high-level overview of the topics in that chapter, followed by python code which accomplishes the goal of the chapter, followed by a detailed description of what each block of code accomplishes. Readers get to see fully written code that does nontrivial things very quickly, but on the other hand the onus of code generation is entirely on the book and readers may have trouble adapting the concepts to other programming tasks. (But remember, this is more survey, less technical description). Further, Sweigart uses a number of good practices in his code that implicitly encourages good programming behaviors: modules are written with many well-named functions and well-named variables, and sufficiently modularly that earlier modules are imported and reused later.

But this book is not without faults. As with any survey material, one can always disagree on what topics are or are not included. The book covers five classical ciphers (Caesar, transposition, substitution, Vigenere, and affine) and one modern cipher (textbook-RSA), as well as the write-backwards cipher (to introduce python concepts) and the one-time-pad (presented oddly as a Vigenere cipher whose key is the same length as the message). For some unknown reason, Sweigart chooses to refer to RSA almost everywhere as “the public key cipher”, which I find both misleading (there are other public key ciphers) and giving insufficient attribution (the cipher is implemented in chapter 24, but “RSA” appears only once as a footnote in that chapter. Hopefully the reader was paying lots of attention, as otherwise it would be rather hard to find out more about it).

Further, the choice of python topics (and their order) is sometimes odd. In truth, this book is almost language agnostic and one could very easily adapt the presentation to any other scripting language, such as C.

In summary, this book is an excellent resource for the complete beginner who wants to learn something about programming and wants to learn something about ciphers. After reading this book, the reader will be a mid-beginner student of python (knee-deep is apt) and well-versed in classical ciphers. Should the reader feel inspired to learn more python, then he or she would probably feel comfortable diving into a tutorial or reference for their area of interest (like Full Stack Python if interested in web dev, or Python for Data Analysis if interested in data science). Or he or she might dive into a more complete monograph like Dive into Python or the monolithic Learn Python. Many fundamental topics (such as classes and objects, list comprehensions, data structures or algorithms) are not covered, and so “advanced” python resources would not be appropriate.

Further, should the reader feel inspired to learn more about cryptography, then I recommend that he or she consider Cryptanalysis by Gaines, which is a fun book aimed at diving deeper into classical pre-computer ciphers, or the slightly heavier but still fun resource would “Codebreakers” by Kahn. For much further cryptography, it’s necessary to develop a bit of mathematical maturity, which is its own hurdle.

This book is not appropriate for everyone. An experienced python programmer could read this book in an hour, skipping the various descriptions of how python works along the way. An experienced programmer who doesn’t know python could similarly read this book in a lazy afternoon. Both would probably do better reading either a more advanced overview of either cryptography or python, based on what originally drew them to the book.

Posted in Book Review, Programming, Python | Leave a comment