# Searching for RH Counterexamples — Search Strategies

We’re glibly searching for counterexamples to the Riemann Hypothesis, to trick you into learning about software engineering principles. In the first two articles we configured a testing framework and showed how to hide implementation choices behind an interface. Next, we’ll improve the algorithm’s core routine. As before, I’ll link to specific git commits in the final code repository to show how the project evolves.

## Superabundant numbers

A superabundant number $n$ is one which has “maximal relative divisor sums” in the following sense: for all $m < n$,

$\displaystyle \frac{\sigma(m)}{m} < \frac{\sigma(n)}{n}$

where $\sigma(n)$ is the sum of the divisors of $n$.

Erdős and Alaoglu proved in 1944 (“On highly composite and similar numbers“) that superabundant numbers have a specific prime decomposition, in which all initial primes occur with non-increasing exponents

$\displaystyle n = \prod_{i=1}^k (p_i)^{a_i},$

where $p_i$ is the i-th prime, and $a_1 \geq a_2 \geq \dots \geq a_k \geq 1$. With two exceptions ($n=4, 36$), $a_k = 1$.

Here’s a rough justification for why superabundant numbers should have a decomposition like this. If you want a number with many divisors (compared to the size of the number), you want to pack as many combinations of small primes into the decomposition of your number as possible. Using all 2’s leads to not enough combinations—only $m+1$ divisors for $2^m$—but using 2′ and 3’s you get $(r+1)(s+1)$ for $2^r3^s$. Using more 3’s trades off a larger number $n$ for the benefit of a larger $\sigma(n)$ (up to $r=s$). The balance between getting more distinct factor combinations and a larger $n$ favors packing the primes in there.

Though numbers of this form are not necessarily superabundant, this gives us an enumeration strategy better than trying all numbers. Enumerate over tuples corresponding to the exponents of the prime decomposition (non-increasing lists of integers), and save those primes to make it easier to compute the divisor sum.

Non-increasing lists of integers can be enumerated in the order of their sum, and for each sum $N$, the set of non-increasing lists of integers summing to $N$ is called the partitions of $N$. There is a simple algorithm to compute them, implemented in this commit. Note this does not enumerate them in order of the magnitude of the number $\prod_{i=1}^k (p_i)^{a_i}$.

The implementation for the prime-factorization-based divisor sum computation is in this commit. In addition, to show some alternative methods of testing, we used the hypothesis library to autogenerate tests. It chooses a random (limited size) prime factorization, and compares the prime-factorization-based algorithm to the naive algorithm. There’s a bit of setup code involved, but as a result we get dozens of tests and more confidence it’s right.

## Search Strategies

We now have two search strategies over the space of natural numbers, though one is obviously better. We may come up with a third, so it makes sense to separate the search strategy from the main application by an interface. Generally, if you have a hard-coded implementation, and you realize that you need to change it in a significant way, that’s a good opportunity to extract it and hide it behind an interface.

A good interface choice is a bit tricky here, however. In the original implementation, we could say, “process the batch of numbers (search for counterexamples) between 1 and 2 million.” When that batch is saved to the database, we would start on the next batch, and all the batches would be the same size, so (ignoring that computing $\sigma(n)$ the old way takes longer as $n$ grows) each batch required roughly the same time to run.

The new search strategy doesn’t have a sensible way to do this. You can’t say “start processing from K” because we don’t know how to easily get from K to the parameter of the enumeration corresponding to K (if one exists). This is partly because our enumeration isn’t monotonic increasing ($2^1 3^1 5^1 = 30$ comes before $2^4 = 16$). And partly because even if we did have a scheme, it would almost certainly require us to compute a prime factorization, which is slow. It would be better if we could save the data from the latest step of the enumeration, and load it up when starting the next batch of the search.

This scheme suggests a nicely generic interface for stopping and restarting a search from a particular spot. The definition of a “spot,” and how to start searching from that spot, are what’s hidden by the interface. Here’s a first pass.

SearchState = TypeVar('SearchState')

class SearchStrategy(ABC):
@abstractmethod
def starting_from(self, search_state: SearchState) -> SearchStrategy:
'''Reset the search strategy to search from a given state.'''
pass

@abstractmethod
def search_state(self) -> SearchState:
'''Get an object describing the current state of the enumeration.'''
pass

@abstractmethod
def next_batch(self, batch_size: int) -> List[RiemannDivisorSum]:
'''Process the next batch of Riemann Divisor Sums'''
pass


Note that SearchState is defined as a generic type variable because we cannot say anything about its structure yet. The implementation class is responsible for defining what constitutes a search state, and getting the search strategy back to the correct step of the enumeration given the search state as input. Later I realized we do need some structure on the SearchState—the ability to serialize it for storage in the database—so we elevated it to an interface later.

Also note that we are making SearchStrategy own the job of computing the Riemann divisor sums. This is because the enumeration details and the algorithm to compute the divisor sums are now coupled. For the exhaustive search strategy it was “integers n, naively loop over smaller divisors.” In the new strategy it’s “prime factorizations, prime-factorization-based divisor sum.” We could decouple this, but there is little reason to now because the implementations are still in 1-1 correspondence.

This commit implements the old search strategy in terms of this interface, and this commit implements the new search strategy. In the latter, I use pytest.parameterize to test against the interface and parameterize over the implementations.

The last needed bit is the ability to store and recover the search state in between executions of the main program. This requires a second database table. The minimal thing we could do is just store and update a single row for each search strategy, providing the search state as of the last time the program was run and stopped. This would do, but in my opinion an append-only log is a better design for such a table. That is, each batch computed will have a record containing the timestamp the batch started and finished, along with the starting and ending search state. We can use the largest timestamp for a given search strategy to pick up where we left off across program runs.

One can imagine this being the basis for an application like folding@home or the BOINC family of projects, where a database stores chunks of a larger computation (ranges of a search space), clients can request chunks to complete, and they are assembled into a complete database. In this case we might want to associate the chunk metadata with the computed results (say, via a foreign key). That would require a bit of work from what we have now, but note that the interfaces would remain reusable for this. For now, we will just incorporate the basic table approach. It is completed in this pull request, and tying it into the main search routine is done in this commit.

However, when running it with the superabundant search strategy, we immediately run into a problem. Superabundant numbers grow too fast, and within a few small batches of size 100 we quickly exceed the 64 bits available to numba and sqlite to store the relevant data.

>>> fac = partition_to_prime_factorization(partitions_of_n(16)[167])
>>> fac2 = [p**d for (p, d) in fac]
>>> fac2
[16, 81, 625, 2401, 11, 13, 17, 19, 23, 29, 31, 37]
>>> math.log2(reduce(lambda x,y: x*y, fac2))
65.89743638933722


Running populate_database.py results in the error

## For work while travelling

My favorite so far is ShareLaTeX.

I’ve used a bunch of online TeX editors, most notably Overleaf (formerly WriteLaTeX). They’re both pretty solid, but a few features tip me toward ShareLaTeX. I’ll italicize these things below.

Mindset: An editor I can use on my Chromebook or a public machine, yet still access my big papers and projects in progress. Needs support for figures, bibliographies, the whole shebang. Basically I need a browser replacement for a desktop LaTeX setup. I generally do not need collaboration services, because the de facto standard among everyone I’ve ever interacted with is that you can only expect people to have Dropbox. You cannot expect them to sign up for online services just to work with you.

Use cases:

• Drafting actual research papers
• Writing slides/talks

Awesome features: Dropbox integration! This is crucial, because I (and everyone I know) does their big collaborative projects using Dropbox. ShareLaTeX (unlike Overleaf) has seamless Dropbox integration. The only caveat is that ShareLaTeX only accesses Dropbox files that are in a specially-named folder. This causes me to use a bunch of symbolic links that would be annoying to duplicate if I got a new machine.

Other than that, ShareLaTeX (like Overleaf) has tons of templates, all the usual libraries, great customer support, and great collaborative features for the once in a blue moon that someone else uses ShareLaTeX.

Vim commands. The problem is that they don’t go far enough here. They don’t support vim-style word-wrapping (gq), and they leave out things like backward search (? instead of /) and any : commands you tend to use.

Github integration. Though literally no mathematicians I know use Github for anything related to research, I think that with the right features Github could become the “right” solution to paper management. The way people store and “archive” their work is horrendous, and everyone can agree a waste of time. I have lots of ideas for how Github could improve academics’ lives and the lives of the users of their research, too many to list here without derailing the post. The point is that ShareLaTeX having Github integration is forward thinking and makes ShareLaTeX more attractive.

How it could improve: Better vim command support. It seems like many of these services are viewed by their creators as a complete replacement for offline work, when really (for me) it’s a temporary substitute that needs to operate seamlessly with my other services. So basically the more seamless integration it has with services I use, the better.

Caveats: Integration comes at a premium of $8/month for students, and$15/month for non-students.

## Work at home

This is where we get into the nitty gritty of terminal tools. Because naively writing papers in TeX on a desktop has a lot of lame steps and tricks. There are (multiple types of) bibliography files to manage, you have to run like four commands to compile a document, and the TeX compiler errors are often nonsense.

I used to have a simple script to compile;display;clean for me, but then I came across the latexmk program. What you can do is configure latexmk to automatically recompile when a change is made to a source file, and then you can configure a pdf viewer (like Skim) to update when the pdf changes. So instead of the workflow being “Write. Compile. View. Repeat,” It’s “Compile. View. Write until done.”

Of course lots of random TeX distributions come with crusty GUIs that (with configuration) do what latexmk does. But I love my vim, and you have your favorite editor, too. The key part is that latexmk and Skim don’t care what editor you use.

For reference, here’s how I got it all configured on OS X Mavericks.

1. Install latexmk (move the perl script downloadable from their website to anywhere on your $PATH). 2. Add alias latexmk='latexmk.pl -pvc' to your .profile. The -pvc flag makes latexmk watch for changes. 3. Add the following to a new file called .latexmkrc in your home directory (it says: I only do pdfs and use Skim to preview): $pdf_mode = 1; $postscript_mode = 0;$dvi_mode = 0; $pdf_previewer = "open -a /Applications/Skim.app";$clean_ext = "paux lox pdfsync out";
4. Install Skim.
5. In Skim’s preferences, go to the Sync tab and check the box “Check for file changes.”
6. Run the following from the command line, which prevents Skim from asking (once for each file!) whether you want to auto reload that file:
\$ defaults write -app Skim SKAutoReloadFileUpdate -boolean true

Now the workflow is: browse to your working directory; run latexmk yourfile.tex (this will open Skim); open the tex document in your editor; write. When you save the file, it will automatically recompile and display in Skim. Since it’s OS X, you can scroll through the pdf without switching window focus, so you don’t even have to click back into the terminal window to continue typing.

Finally, I have two lines in my .vimrc to auto-save every second that the document is idle (or when the window loses focus) so that I don’t have to type :w every time I want the updates to display. To make this happen only when you open a tex file, add these lines instead to ~/.vim/ftplugin/tex.vim

 set updatetime=1000 autocmd CursorHoldI,CursorHold,BufLeave,FocusLost silent! wall 

Caveats: I haven’t figured out how to configure latexmk to do anything more complicated than this. Apparently it’s possible to get it setup to work with “Sync support,” which means essentially you can go back and forth between the source file lines and the corresponding rendered document lines by clicking places. I think reverse search (pdf->vim) isn’t possible with regular vim (it is apparently with macvim), but forward search (vim->pdf) is if you’re willing to install some plugins and configure some files. So here is the place where Skim does care what editor you use. I haven’t yet figured out how to do it, but it’s not a feature I care much for.

One deficiency I’ve found: there’s no good bibliography manager. Sorry, Mendeley, I really can’t function with you. I’ll just be hand-crafting my own bib files until I find or make a better solution.

Have any great tools you use for science and paper writing? I’d love to hear about them.