I skimmed through a newly acquired mathematics book, as I do, when I came across a section describing something I hadn’t seen before. As the title of this essay suggests, the section defined a Moore-Smith sequence, also known as a “net”, as a generalization of an index set for the usual sequences defined in undergraduate analysis.

I had heard of filters, or more broadly, ultra-filters, in writings I never understood, so I was intrigued to see a seemingly related concept show up in a familiar context.

As a quick recap, a sequence is an indexed set of numbers. For example, the numbers x_i: 1, 2, 3, 4, … form a sequence of increasing integers, where x_0 is 1, x_1 is 2, etc. The indices for the sequence x_1 are positive integers.

The Moore-Smith sequence answers the question, can you have a sequence whose index set is something other than positive integers? And the answer is yes. Here’s how Gerresten and Rau (translated by Gould) present the concept:

I struggled to understand this lemma, which I first encountered in Powell, Chapter 4.¹ This was a problem, as the lemma provides the key to constructing the required matrix to identify eigenvalues for the rational approximation I’m seeking. But don’t worry about that technical jargon for now, let’s focus on making sense of the lemma defining Lagrange polynomials.

TLDR: This lemma provides a formal definition for interpolation on available data by proving that a polynomial of the desired degree exists. It’s used to prove that such a polynomial is unique, a fact that enables us to systematically search for useful approximating functions. The lemma will be used in a future post to create an algorithm for rational approximations by canceling out non-linear terms.

A better discussion of the Lagrange polynomial and its motivation is found in Süli and Mayers²:

If the function values f(x) are known for all x in a closed interval of the real line, then the aim of polynomial interpolation is to approximate the function f by a polynomial over this interval. Given that any polynomial can be completely specified by its (finitely many) coefficients, storing the interpolation polynomial for f in a computer will be, generally, more economical than storing f itself.

This project's guided by the concept that we write mathematics. Thoughts and discussion occur, but mathematics doesn't happen, in my sense, until its been written down.

essay originally published at mathbook.cafe

The way we do mathematics changes across generations. The tools we use to write down thoughts and discussion, thereby doing mathematics, changes as the people who do the writing change. Most recently, the Lean 4 programming language has become an active environment for doing mathematics. Lean allows mathematicians to write down, in compilable code, formal representations of mathematical statements. Before automated theorem provers like Lean, professional mathematicians wrote down, also in code, typesetting directives to display formally presentable mathematical writing. New languages, like Typst, continue to be invented for this task.

Yet in order to have formalities to compile or symbols to typeset, mathematicians must have already specified a language and symbology. Where, for instance, did the Greek letter $\pi$, come to represent the ratio of a circle's circumference to its diameter?

Congressive Information

In the latest issue of the Bulletin of the American Mathematical Society, Eugenia Cheng has written about the ways in which technology can make the mathematics discipline more "congressive", meaning "bringing people with you and bringing people together and unifying and making connections between things."

Her essay made me think about the ways in which we talk about developments in large language models (LLMs) and how our "ingressive" interpretation of these tools may hinder our ability to make good use of them.

Aside: My writing progress has stalled while I work out some bugs in my reconstruction for the error function coefficients. You can view the minimal code here, which does a decent job generating a polynomial approximation, but not at the level of efficiency I want for my essay project.

Remez Exchange Algorithm

Remember that the research plan for this essay series had four components

• rational approximation

• Remez' exchange algorithm

• asymptotic series expansion

• Taylor series expansion

I've deviated from the plan slightly by combining the last two bullet points into a single essay on the Maclaurin series, which is an asmptotic expansion and a generalization of Taylor. Using the key idea regarding the minimax approximation, we're ready to apply Remez' exchange algorithm.

Minimax Approximation - Key Idea

If you've read my previous essay, you might have two questions: (1) how do you prove a Maclaurin series gives an accurate representation of its target function? (2) Why not use the generated series as a computational tool, rather than an approximation? The answer to the first question involves performing a repeated integration by parts on the target function. It's a fun exercise, but we'll leave that for another essay. Here, I want to briefly state why a series expansion falls short computationally, and how polynomial approximations rectify the situation.

Given a Maclaurin series for the error function

Maclaurin Expansion

Working out the correct algorithm we need will require a clear idea of what an exact solution may look like.

Reconsider what I just wrote: taken glibly, I'm saying an approximate solution requires an exact answer. That's not as much a contradictory statement it seems, but a mathematical point of view. A scientist might say, contra-wise, that the approximation requires data acquired via observation. That's the way scientists since Copernicus and Galileo developed models of the universe. That's how the proliferation of AI machines today have been built. We need something "real" to compare with our approximation.

Research Plan

This next phase in my reading of the Go erf and erfc implementations requires a more detailed research plan. I have already set my goals on tracing the development of the POSIX mathematics libraries, written down integrals for the error function and its complement, and identified source code in multiple languages for closer inspection.

As a welcome bonus, all the source code deriving from the original 1993 Sun Microsystems implementation preserves the historical commentary. Both the "who" and the "how" have clear documentation.

In particular, the source code for math.Erf contains a copyright notice identifying the original implementation in the FreeBSD operating system. Likely, the Sun authors copied or modified the code from its predecessor at Berkeley. This same notice, and, what I'm most interested in, the coefficients used for the approximation can be found in MacOS X, in MUSL, in Android Linux, and others.

Software Archeology

How did people build the tools we take for granted?

This question asks for a history and for ideas -- explicit and implicit -- which enabled the development of these technologies. Often, there does not exist a written or even oral record for compiling a history. Sometimes, we can trace, using observed behaviors and uncovered artifacts -- anthropology and archeology -- to recompile a history, sometimes even rebuilding replicas of our present tools, so that we can better understand and appreciate how they enable our world today.

These verbs -- build, develop, compile, trace, recompile, rebuild -- ought to be intimately familiar to software professionals everywhere. They're foundational to the language of the software development lifecycle. They're also instructive of a perspective that I hold dear: that software is about people and the things they do.

Complimentary Error Function

I wrote previously about the error function erf, and how round-off error necessitates the complementary error function, defined as erfc = 1 - erf. In this essay, I want to derive the integral involved.

Begin with the identity

Error Function

Say you expect a normal or Gaussian distribution for some data. How do you calculate the probability that a variate or instance of the data falls within an expected range? Note that, analytically, the distribution does admit all values from negative to positive infinity, just not with the same probability ratio.

Recall that the normal or Gaussian distribution is written as