# Monthly Archives: February 2019

## Talk: Finding Congruent Numbers, Arithmetic Progressions of Squares, and Triangles

Here are some notes for my talk Finding Congruent Numbers, Arithmetic Progressions of Squares, and Triangles (an invitation to analytic number theory), which I’m giving on Tuesday 26 February at Macalester College.

The slides for my talk are available here.

The overarching idea of the talk is to explore the deep relationship between

1. right triangles with rational side lengths and area $n$,
2. three-term arithmetic progressions of squares with common difference $n$, and
3. rational points on the elliptic curve $Y^2 = X^3 – n^2 X$.

If one of these exist, then all three exist, and in fact there are one-to-one correspondences between each of them. Such an $n$ is called a congruent number.

By understanding this relationship, we also describe the ideas and results in the paper A Shifted Sum for the Congruent Number Problem, which I wrote jointly with Tom Hulse, Chan Ieong Kuan, and Alex Walker.

Towards the end of the talk, I say that in practice, the best way to decide if a (reasonably sized) number is congruent is through elliptic curves. Given a computer, we can investigate whether the number $n$ is congruent through a computer algebra system like sage.1

For the rest of this note, I’ll describe how one can use sage to determine whether a number is congruent, and how to use sage to add points on elliptic curves to generate more triangles corresponding to a particular congruent number.

Firstly, one needs access to sage. It’s free to install, but it’s quite large. The easiest way to begin using sage immediately is to use cocalc.com,  a free interface to sage (and other tools) that was created by William Stein, who also created sage.

In a sage session, we can create an elliptic curve through


> E6 = EllipticCurve([-36, 0])
> E6
Elliptic Curve defined by y^2 = x^3 - 36*x over Rational Field


More generally, to create the curve corresponding to whether or not $n$ is congruent, you can use


> n = 6   # (or anything you want)
> E = EllipticCurve([-n**2, 0])


We can ask sage whether our curve has many rational points by asking it to (try to) compute the rank.


> E6.rank()
1


If the rank is at least $1$, then there are infinitely many rational points on the curve and $n$ is a congruent number. If the rank is $0$, then $n$ is not congruent.2

For the curve $Y^2 = X^3 – 36 X$ corresponding to whether $6$ is congruent, sage returns that the rank is $1$. We can ask sage to try to find a rational point on the elliptic curve through


> E6.point_search(10)
[(-3 : 9 : 1)]


The 10 in this code is a limit on the complexity of the point. The precise definition isn’t important — using $10$ is a reasonable limit for us.

We see that this output something. When sage examines the elliptic curve, it uses the equation $Y^2 Z = X^3 – 36 X Z^2$ — it turns out that in many cases, it’s easier to perform computations when every term is a polynomial of the same degree. The coordinates it’s giving us are of the form $(X : Y : Z)$, which looks a bit odd. We can ask sage to return just the XY coordinates as well.


> Pt = E6.point_search(10)[0]  # The [0] means to return the first element of the list
> Pt.xy()
(-3, 9)


In my talk, I describe a correspondence between points on elliptic curves and rational right triangles. In the talk, it arises as the choice of coordinates. But what matters for us right now is that the correspondence taking a point $(x, y)$ on an elliptic curve to a triangle $(a, b, c)$ is given by
$$(x, y) \mapsto \Big( \frac{n^2-x^2}{y}, \frac{-2 \cdot x \cdot y}{y}, \frac{n^2 + x^2}{y} \Big).$$

We can write a sage function to perform this map for us, through


> def pt_to_triangle(P):
x, y = P.xy()
return (36 - x**2)/y, (-2*x*6/y), (36+x**2)/y

> pt_to_triangle(Pt)
(3, 4, 5)


This returns the $(3, 4, 5)$ triangle!

Of course, we knew this triangle the whole time. But we can use sage to get more points. A very cool fact is that rational points on elliptic curves form a group under a sort of addition — we can add points on elliptic curves together and get more rational points. Sage is very happy to perform this addition for us, and then to see what triangle results.


> Pt2 = Pt + Pt
> Pt2.xy()
(25/4, -35/8)
> pt_to_triangle(Pt2)
(7/10, 120/7, -1201/70)


Another rational triangle with area $6$ is the $(7/10, 120/7, 1201/70)$ triangle. (You might notice that sage returned a negative hypotenuse, but it’s the absolute values that matter for the area). After scaling this to an integer triangle, we get the integer right triangle $(49, 1200, 1201)$ (and we can check that the squarefree part of the area is $6$).

Let’s do one more.


> Pt3 = Pt + Pt + Pt
> Pt3.xy()
(-1587/1369, -321057/50653)
> pt_to_triangle(Pt3)
(-4653/851, -3404/1551, -7776485/1319901)


That’s a complicated triangle! It may be fun to experiment some more — the triangles rapidly become very, very complicated. In fact, it was very important to the main result of our paper that these triangles become so complicated so quickly!

## Writing a Python Script to be Used in Vim

It is no secret that I love vim. I’ve written and helped maintain a variety of vim plugins, but I’ve mostly restricted my attention to direct use of vimscript or to call external tools and redirect their output to a vim buffer.

Only recently did I learn how easy it is to use python to interact directly with vim objects through the vim-python package. And it was so easy that this felt a bit like writing a quick shell script to facilitate some immediate task — it allows quick and dirty work.

In this note, I’ll review how I recently wrote a quick python function (to be used in vim) to facilitate conversion of python f-strings (which I love) to python 3.5 (which I also love, but which is admittedly a bit behind).

Of course the real reason is to remind future me just how easy this is.

## Description of the Problem

In python 3.7+, one can use f-strings to format strings. This syntax looks like

x = 4
print(f"Python has at least {x} many ways to format strings now.")

I love them, they’re great. But they are not backportable since they are a change to fundamental syntax. Thus systems relying on previous versions of python (be it python2 or even python3.5) can’t parse python files containing f-strings.

The goal is this: given a line containing an f-string, write an equivalent line containing no f-string.

The formula I choose is simple: use .format() instead. Thus given

s = f"string with {some} {variables}"

we will convert this to

s = "string with {} {}".format(some, variables)

I will assume that the string takes place on one line for simplicity (and because in my application this was almost always true), but that there are any number of variables included in the line.

## Background on python in vim

Some good insight is gained through reading :h python-vim. In fact, this is essentially the only documentation on the python-vim interface (though it is pretty good documentation — perhaps the actual best source of learning this interface is to read some plugins which leverage the python connection).

I will assume that vim has been compiled with python3 support (which can be checked by looking for +python3 in vim --version). Then the key idea is that one can use :py3 to call python functions. For example,

:py3 print("Hello")

Being restricted to one line is inconvenient, and it is far more useful to use the form

:py3 << EOF
def say_hello():
print("Sup doc.")
EOF
:py3 say_hello()

In this way, we can define and use python functions. Right now, the output of these functions simply appears in the status lines at the bottom of the screen. This is of limited value. Often, we will really want to interact directly with the vim buffer. The key to do this is the vim module for python.1

The vim module for python can be used through

import vim

# do vim things

This is what :h python-vim actually documents, and I defer to the list of methods there. The important thing is that it provides direct access to vim buffers.

Today, we will use only the direct access to the current line, vim.current.line.

## A Solution

I very routinely open scratch buffers (i.e. buffers that I call scratch.tmp). Sometimes I momentary notes, or I edit vim macros in place, or I define vim functions for short-term use. I will assume that we have opened up a scratch buffer and our pythonfile withfstrings.py. (In fact, I usually open it in a vsplit). I also very routinely assign Q to do whatever convenient function I have written in my scratch buffer (or whatever macro I want to repeat most simply). Of course, these are my idiosyncratic habits — the ideas are easy enough to translate.

In our scratch buffer, we can write a vim function, which is internally a python function, and map the symbol Q to call it.

function! Convert()
py3 << EOF

import vim

import re
bracketed = re.compile("{.*?}")

def convert():
line = vim.current.line
single = line.find("'")
double = line.find('"')
if single == -1:
sep = '"'
elif double == -1 or single < double:
sep = "'"
else:
sep = '"'

# l sep inner sep post
l, _, m = line.partition(sep)
inner, _, post = m.partition(sep)

#get rid of f
l = l[:-1]

ret = ""
var_names = bracketed.findall(inner)
var_names = list(map(lambda x: x[1:-1], var_names))

ret += l + sep + inner + sep
ret += ".format("
for var in var_names:
ret += "{}={}, ".format(var, var)
ret = ret[:-2]
ret += ")" + post
vim.current.line = ret

convert()
EOF

endfunction

com! Conv call Convert()
nnoremap Q :Conv<CR>

To use, one sources the scratch buffer (either directly, like :source scratch.tmp, or through navigating to its split and using :so %). Then one can find a line containing an f-string and hit Q (or alternately use :Conv).

## Why is this good?

Although nontrivial, writing a simple python script like this takes only a few minutes. And then converting f-strings became the least important part of my backporting project.2

And more broadly, this is such an easy process. Off-loading the mental burden of repeating annoying tasks is valuable. The most revelatory aspect of this experience for me is that it’s easy enough to allow throwaway functions for momentary ease.

In my recent application, I converted 482 f-strings using this function. A few of them were multiline strings and my (admittedly simple) function failed — and so I did those by hand. But it took me less than 10 minutes to write the function (maybe even less than 5, though my first function expected double quotes only). Overall, this was a great gain.

## Keeping the Script

Having come this far, it’s worth considering how we might keep the script around if we wanted to.

One good approach is to separate the python from the vim (allowing, for instance, testing on the python itself) and have a thin vim wrapper. We’ll look at this in two possible levels of encapsulation.

1. Separate the python from the vim.
2. Make the function a plugin. (Presumably for slightly more meaningful functions than this one).

### Separate the Files

Let’s separate the python from the vim. In this was we can approach the python as proper little python script, merely waiting for a thin vim wrapper around it at the end.

We can separate the python out into the following file, convert_fstring.py.

# convert_fstring.py
import re
bracketed = re.compile("{.*?}")

def convert(line):
single = line.find("'")
double = line.find('"')
if single == -1:
sep = '"'
elif double == -1 or single < double:
sep = "'"
else:
sep = '"'

# l sep inner sep post
l, _, m = line.partition(sep)
inner, _, post = m.partition(sep)

# get rid of f
l = l[:-1]

ret = ""
var_names = bracketed.findall(inner)
var_names = list(map(lambda x: x[1:-1], var_names))

ret += l + sep + inner + sep
ret += ".format("
for var in var_names:
ret += "{}={}, ".format(var, var)
ret = ret[:-2]
ret += ")" + post
return ret

if __name__ == "__main__":
test_input = 'mystr = f"This {is} an {f}-string".reverse()'
expected  = 'mystr = "This {is} an {f}-string".format(is=is, f=f).reverse()'
assert expected == convert(test_input)

This is a raw python file. I included a mock unit-test (in case one was testing the function while writing it… I didn’t compose the function like this because I didn’t think about it, but in the future I probably will).

Now let’s write a thin vim wrapper around it.

" convert_string.vim

let s:script_dir = fnamemodify(resolve(expand('<sfile>', ':p')), ':h')

function! Convert()
py3 << EOF

import sys
import vim

script_dir = vim.eval('s:script_dir')
sys.path.insert(0, script_dir)

import convert_fstring

def convert():
out = convert_fstring.convert(vim.current.line)
vim.current.line = out

convert()
EOF

endfunction

com! Conv call Convert()
nnoremap Q :Conv<CR>

This is mostly pretty clear, with (I think) two exceptions concerning s:script_dir.

The problem comes from trying to import convert_fstring — it’s not in our PYTHONPATH, and the current working directory for python from within vim is a bit weird. It would be possible to directly code in the current directory into the PYTHONPATH, but I think it is more elegant to have convert_fstring.vim add the location of convert_fstring.py to python’s path.3 One can do that through

There are two additions of note that address this import. The first is the line

let s:script_dir = fnamemodify(resolve(expand('<sfile>', ':p')), ':h')

This sets a script-local variable (the prefix s:) containing the directory in which the script was sourced from. (This is where we use the assumption that the vimfile is in the same directory as the python file. If they’re in relative directories, then one much change the path addition to python appropriately).

The string <sfile> is populated automatically by vim to contain the filename of the sourcefile. Calling expand with the :p filemodifier returns the complete path of <sfile>. Calling resolve follows symlinks so that the path is absolute. And the final fnamemodify with the :h modifier returns the head, or rather the directory, of the file. Thus the result is to get an absolute path to the directory containing the script (and in this case also the python file).

Then in the python function, we add this location to the path through

script_dir = vim.eval('s:script_dir')
sys.path.insert(0, script_dir)

The first line has vim convert the vim variable into a python string, and the second inserts this directory into the PYTHONPATH.

I have a collection of loosely organized helper scripts in a (creatively named) ~/scripts directory. Some of these were written as pure python shellscripts that I’ve added some vim wrappers around.

### Writing a Plugin

To reiterate, I consider this excessive for my sample application. But we’ve covered so many of the ideas that we should touch on it now.

Any plugin should follow Tim Pope’s Pathogen design model, with the ultimate goal of having a structure that looks like

myplugin/
myplugin.vim
...
plugin/
...

Pathogen (or Pathogen-compatible plugin managers, which as far as I know means all of them… like Vundle or vim-plug) will allow plugins to be installed in ~/.vim/bundle, and each plugin there will be added to vim’s rtp. 4 Each plugin manager installs plugins (i.e. adds to the runtimepath) in its own way. For Vundle, I include an extra line in my .vimrc.

Suppose I want to package my script as a plugin called fstring_converter. Then I’ll create the directory structure

fstring_converter/
ftplugin/
python.vim
convert_fstring.py

where python.vim is what I called convert_fstring.vim before. Placing fstring_converter in ~/.vim/bundle (or symlinking it, or installing it there through e.g. Vundle) will “install it”. Then opening a python file will load it, and one can either Conv a line or (as it’s currently written) use Q. (Although I think it’s a bit unkind and certainly unsustainable to create this mapping for users).

I note that one should generically use autoload/ when available, but I don’t touch that now.

As an additional note, vim does add some directories to the PYTHONPATH under the hood. For each directory in vim’s runtimepath, vim adds the subdirectory python3 (and also pythonx) to the python module search path. As a result, we could omit the explicit path addition to the python.vim (aka convert_fstring.vim) file if we organized the plugin like

fstring_converter/
ftplugin/
python.vim
python3/
convert_fstring.py

Regardless, this describes a few ways to make a vim plugin out of our python script.