All Posts, Unorganized

Reflection Rules for Modal Logics

By a reflection rule for a modal logic, I mean a rule that allows the derivation of \(\vdash p\) from \(\vdash \Box p\). In this post, I sketch out an interesting technique for establishing such reflection rule for logics such as K, K4, and GL.

Fixed Points of Cycled Compositions

Suppose given 1-cells \(F : C \to D\) and \(G : D \to C\) in some 2-category. \(\newcommand{\id}{\mathrm{id}}\)

The Hurwitz and Riemann functional equations

Where the celebrated “functional equation” for the Riemann zeta function comes from, as well as for the Hurwitz zeta function more generally. I believe the approach here is cleaner and better motivated than either the contour integration or theta function approaches people usually give, which seem to me a long mess of magic calculation. I think the approach here should make the functional equation even obvious, in hindsight.

Conjugate Partitions As Adjoints

Just a small note on conjugate partitions as adjoint functors (more specifically, Galois connections). Nothing earth-shattering but I wished to remember these thoughts for myself:

Defining Predecessor

There is a famous story about Kleene trying to define a predecessor function on the natural numbers (or the Church numerals, to be clear) in the lambda calculus, not having any idea how to do it, and then figuring it out while at the dentist. In the same vein, I put forth this puzzle and solution.

Hylomorphisms

Here I record some simple thoughts on hylomorphism correspondences.

Small Free Nondeterministic Structures

The following generalization of a certain traditional argument occurred to me today, my needing it in some argument, and so I thought I would record it for my own future use if ever I need it again:

Yoneda Extension

Why is the Yoneda embedding the free cocompletion?

Abelian Categories

Here, we give a manifestly self-dual presentation of the concept of abelian categories.

Presheaf Categories Are Toposes

The category Psh(C) of presheaves on a small category C is a topos (presuming Set itself is one). Why is this? I keep forgetting the cleanest proofs of these facts. I record them here for myself for posterity.

Non-Elementary Prime Counting with the Riemann Zeta Function

This is a much more advanced follow-up to our post on elementary prime counting. [Beware, for dumb reasons, this relative link will not work correctly on the index page, only when you click through to this post.]

Indexed, Enriched, and Internal Categories

In general, there are many things to say about these. I just wanted to record for myself some thoughts I realized today. (There’s things to say about indexed, enriched, and internal STRUCTURES in general, but the particular observation I want to make involves some aspects that are specific to CATEGORIES in particular.)

The Universal Cover of SO(3) is a Double Cover

Let us prove that the universal cover of SO(3) is a double cover (thus, the homotopy group of SO(3) is \(\mathbb{Z}_2\)). This explains the famed Dirac belt trick and the concept of half-spin particles, among other things.

Subgroups of Free Groups

Let me describe how the free group on countably infinitely many generators embeds inside the free group on two generators:

Löb's Theorem Entails 4

A curious fact about modal logic is that any normal (in the Kripke sense) modal logic containing Löb’s theorem (\(\Box (\Box A \Rightarrow A) \vdash \Box A\)) as an axiom also contains 4 (\(\Box A \vdash \Box \Box A\)) as an axiom.

The Yoneda Lemma

The Yoneda Lemma is considered one of the most important observations of category theory. Well, I don’t know who decides what things are to be considered important, but it is certainly good to understand. There are multiple perspectives worth understanding it from, even.

Alternating Series, Generalized Summation, and the Dirichlet Eta Function

A standard observation is that, if \(f\) is a monotonically decreasing function from some point on, approaching zero asymptotically, then the alternating series \(f(0) - f(1) + f(2) - f(3) + f(4) - f(5) + \ldots\) converges. This is easy to see: the partial sums jump up and down and then up a little less and then down a little less, and so on, so that we get a decreasing series of upper bounds on the lim sup alternating with an increasing series of lower bounds on the lim inf. The distance between any two adjacent of these is given by the corresponding value of f, and as this approaches zero in the limit, the lim sup matches the lim inf.

A straight line is the shortest path

A straight line is the shortest path between two points. Why is that?

Egyptian Fractions

Any rational in \([0, 1)\) can be written as a finite sum of reciprocals of natural numbers. For zero, this is trivial, as an empty sum. As for other such values, specifically, if \(\frac{x}{y}\) is the fraction to be represented (whether in lowest terms or not, we can apply this same procedure), we let \(n\) be the smallest whole number such that \(nx \geq y\) (i.e., \(\frac{x}{y} \geq \frac{1}{n}\)), and then rewrite \(\frac{x}{y}\) as \(\frac{1}{n} + \frac{nx - y}{ny}\).

The Y Combinator (aka, diagonalization)

TODO: Rewrite the following into the post I want it to be, about how diagonalization in the Cantor/Russell/Gödel/Lawvere/Yanofsky sense is the same as the Y combinator and also the Y combinator is obvious in retrospect. For now, this post is taken from an old Quora thing I once wrote, in response to the prompt “What is the Y combinator?” or some such thing.

Arrow's Impossibility Theorem

The content of Arrow’s Impossibility theorem is actually extremely closely related to ultrafilters, and, in fact, the eponymous “impossibility” is essentially the same as a very basic fact about ultrafilters on finite sets. Yet, for some reason, I have rarely (if ever) seen the theorem presented in such a way as even mentions this connection (e.g., the word “filter” appears not once in the relevant Wikipedia article, nor in any of the references within it). A shame, which I shall rectify in this post.

The Fundamental Theorem of Equal Temperament Arithmetic

The Fundamental Theorem of Equal Temperament Arithmetic is that log(2) : log(3) : log(5) is 12 : 19 : 28.

What do I mean by this? This is a statement about music theory.

Stirling's approximation

Where does Stirling’s approximation \(n! \sim \sqrt{2\pi n} \left(\frac{n}{e}\right)^n\) come from?

Stupid Digit Tricks

One thing people are often amused by is observations like that \(\frac{1}{998001}\) comes out to .000 001 002 003 004…, with every three digit string appearing in order except for 998, and then repeating back from 999 to 000.

Queues and the Erlang B-Theorem

Suppose you have a queue with finite capacity C, such that the queue can be entered whenever it has less than C people in it already, but the queue permanently turns away anyone who shows up while it has C people in it.

Gauss-Bonnet

Euler characteristic is the sort of thing which adds up as you combine regions (combining them not in the union sense, but in the addition sense. So \(F(A \cup B) + F(A \cap B) = F(A) + F(B)\)).

Partitions

There’s lots to say about partitions. I’ll just write some things scattershot, most of which are due to Euler or from thinking about transposing Ferrers/Young diagrams:

Mean Monkey Time

Suppose you have a monkey banging away at a typewriter with N keys, each keystroke at independent uniform random. Suppose you’re waiting for the first occurrence of a particular string S. On average (in the sense of probabilistic mean), how many keystrokes will it take?

Greatest Common Divisors and Unique Prime Factorization

A general discussion of jewels of math concerning GCDs in various contexts.

Counting Works

A basic fact, so perfectly figured out by ancient mathematicians and internalized by human society ever since that no one ever bothers to think about or question it anymore, is that any two orders in which to count the same finite set yield the same number. That is, each finite cardinal has a unique associated ordinal.

Eulerian Graphs

Suppose given a directed multigraph, and suppose also that at each vertex, we are given a bijection between the edges into the vertex and the edges out of that vertex (think of this bijection as saying that the former edge is “followed by” the latter edge). Then every edge is in a line of edges (the edge after it, and the edge after that, and so on, as well as the edge before it, and the edge before that, and so on); either an infinite line of all distinct edges, or a periodically repeating line (i.e., a finite cycle).

Heron's Formula

When I was young, in middle school, high school, and even college, Heron’s formula was such a bother to me; the one formula in geometry I was aware of, which would be listed in each geometry textbook formula “cheat sheet”, that I didn’t know how to prove.

Permutation Parity

I am fond of saying that the two theorems that laypeople do not know because curricula arbitrarily do not bother to show them, yet which are about phenomena of ubiquitous generality in down-to-Earth grade school mathematics, are Bezout’s theorem and the fact that permutations carry parity. I know of two traditional proofs for this fact, but perhaps they are the same in the end. Let’s see.

Partial Fractions, Jordan, Bezout, Euclid, and the Chinese

There are a number of results which are all essentially the same:

Galois Theory and the Fourier Transform

Consider a base field with a finite degree Galois extension with Galois group cyclic of order \(N\) with generator \(\varphi\). Suppose the base field also contains a primitive \(N\)th root of unity (thus, by the general theory of primitive roots of unity in a field, its \(N\)th roots of unity comprise a cyclic group of order \(N\), and the field also allows division by \(N\)), so that we have the invertible discrete Fourier transform of order \(N\) available to us.

Induction and Recursion

It is often thought that induction only applies to well-founded orderings, not to structures like the reals. But actually, it is very common in mathematics to do induction arguments over the reals, only people do not recognize them as such when they do so.

Unusual Uncountability Proofs

Everyone knows the diagonalization proof of uncountability. Some are familiar with other uncountability proofs as well; e.g., Cantor’s original proof of the uncountability of R [TODO: discuss this, relate it to the diagonalization proof] [TODO: Discuss all the famed antinomies and how they become uncountability proofs; e.g., Burali-Forti/Mirimanoff]. Here’s one I came up with which I’ve never seen anyone else mention, though:

Convergence Entails Countable Support

Consider a multiset of values, all \(\geq 0\) (“semipositive”, as I often say in my head). It is clear how any finite submultiset of these are to be summed, and we can define the sum of the multiset overall as the supremum of the sum of its finite submultisets.

Euler Characteristic

Let’s start with Euler’s polyhedron formula. Vertices - Edges + Faces = 2 on a sphere.

0.999... = 1

This comes up a lot in pop math discussion, so I’ll just post here the thing I’ve written about it in various other places previously.

Margin of Error

When polls report a “margin of error”, it doesn’t mean what almost everyone takes it to mean.

Mac Lane "Parameters" Theorem

Suppose given an isomorphism square in Cat; that is, categories A, B, C, and D, functors e : A -> B, f: A -> C, g : B -> D, and h : C -> D, and a natural isomorphism between the two paths from A to D.

Circular Proofs Aren't Useless

Suppose you prove B from A and later also prove A from B. Useless, right?

Coproducts of Abelian Monoids

Two classic facts are:

The Irrationality of e

This is actually quite easy to show.

Categorical Asymmetry

All of the asymmetries¹ of category theory arise from the fact that we generally talk and think in terms of Set(/Cat/etc.)-like categories and not Set^op-like ones, and in these, everything is a big colimit of simple pieces, but not a big limit.

Prime-Generating Polynomial

Some numbers p have the property that multiplying two consecutive integers and then adding p generates only prime number outputs, so long as both consecutive integers are less than p in size. (By symmetry of multiplication under negation, it suffices to consider just consecutive natural numbers less than p)

Commas and Collages

Subjects: Commas and Cocommas/Collages, Bifibrations (by which I mean two-sided fibrations, which apparently is not what people usually mean by this, oh well…), the Grothendieck construction, (bi)-indexed categories, perhaps profunctors, etc.

The Internal Logic of Effective Regular and Abelian Categories

The internal logic of effective regular categories (aka, “exact categories”, though this term is overloaded, or “Barr-exact categories”) can be given in many different ways, but is perhaps most easily spelt out in terms of thinking of relations, rather than functions as such. Any theory of the following form presents an effective regular category, and any effective regular category has such a presentation:

Borwein Integrals

A result sometimes observed as surprising, shocking, etc, is that \(\int_{0}^{\infty} \mathrm{sinc}(x) dx = \pi/2\), and indeed \(\int_{0}^{\infty} \mathrm{sinc}(x) \mathrm{sinc}(x/3) dx = \pi/2\) and \(\int_{0}^{\infty} \mathrm{sinc}(x) \mathrm{sinc}(x/3) \mathrm{sinc}(x/5) dx = \pi/2\) and \(\int_{0}^{\infty} \mathrm{sinc}(x) \mathrm{sinc}(x/3) \mathrm{sinc}(x/5) \mathrm{sinc}(x/7) dx = \pi/2\) and so on, but once we get up to \(\int_{0}^{\infty} \mathrm{sinc}(x) \mathrm{sinc}(x/3) \ldots \mathrm{sinc}(x/15) dx\), the result is \(q \pi\) for a rational \(q\) strictly less than \(1/2\).

Field Multiplication Cyclicity

Let \(G\) be a finite subgroup of the multiplicative group of a field. We shall show that it is cyclic.

Multiplicative Groups in Modular Arithmetic

By the Chinese Remainder Theorem, the ring of integers modulo N is the product of the rings of integers modulo p^n, for each prime power p^n in the factorization of N. To study the integers modulo p^n, it is helpful to consider the p-adics.

Lambek's lemma, Knaster-Tarski, Adamek

Let \(F\) be an endofunctor and let \(A : FX \to X\) be an algebra for that endofunctor. \(A\) gives rise to another F-algebra \(FA : FFX \to FX\), and this has a “tautological” F-algebra homomorphism back into \(A\) with underlying map \(A\) itself (the relevant commutative square is just \(A \circ FA = A \circ FA\)).

Donvolution

Let’s consider the general problem of determining the volume \(v(K)\) of the region where \(\sum f_i(x_i) < K\); that is, of determining \(\int_{\sum f_i(x_i) < K} \prod dx_i\). Let us define new variables \(y_i = f_i(x_i)\); the problem is now expressed as \(\int_{\sum y_i < K} \prod d g_i(y_i)\), where \(g_i\) is the inverse of \(f_i\). In other words, the derivative of \(v\) is the convolution of the derivatives of the \(g_i\). Let us refer to this sort of relationship by saying \(v\) is the “donvolution” of the \(g_i\).

Möbius Inversion

Let \(\leq\) be an arbitrary binary relation (not necessarily transitive or reflexive, despite the notation). We will impose one condition: \(\{y \mid y \leq x\}\) should be finite for every \(x\) (this finiteness condition can maybe be relaxed in some form for what we’re doing here, but for now we’ll impose it).

Difference Equations, Infinite Sums, Generalized Factorial, Zeta Functions, Etc

Suppose given a difference relation \(F(x + 1) - F(x) = f(x)\), where \(f\) is known but \(F\) is not. What should \(F\) be?

Crystallographic Restriction

Under what circumstances can a regular n-gon be made such that all its points are lattice points, for some lattice?

Confluence

A) Say relation → is “confluent against” ↓ if, given a→b and a↓c, ∃d with b↓d and c→d (ie, given the top and left of a square, you can fill out the rest).

Total Limits Are Empty Colimits

Here’s a simple fact from order theory: Suppose \(X\) is a least element of partial order \(C\). Then \(X\) is the meet of all of \(C\). In fact, for any order-preserving function \(F\), we have that \(F(X)\) is the meet of all of \(F(C)\).

Transfinite Stable Marriage

Suppose you have a set of men \(M\) and women \(W\), and every man comes with a well-order on the women (where we take the smallest woman in a set to be the man’s favorite among that set; a well-order amounts to the same thing as a way of assigning to each inhabited set a favorite, such that the favorite is stable under constraining to any subset of options still containing the former favorite) and vice versa. Actually, we’ll say each man \(m\) comes with a well-order on some \(W_m = W' \cup \{Nobody\}\), where \(W'\) is some subset of \(W\) and \(Nobody\) is the maximal (i.e., least favored) element in this ordering. And symmetrically for the women having well-ordered preferences among the men. (This amounts to having favorites within any set that also includes a \(Nobody\) option)

"Sequent Calculi" vs. "Natural Deduction"

When asked what the difference between sequent calculus and natural deduction logical systems is, everyone (e.g., Wikipedia, but also everyone you meet in the world too) says a bunch of stuff that makes no sense. For example, as to whether sequents are involved, or whether sequents can have more than one disjunct on the right. None of this is relevant.

Order of Operations

Laypeople seem to spend an inordinate amount of mental energy on something called “Order of Operations” that they imagine to be deeply important and fundamental in mathematics.

The Fundamental Theorems of Calculus

How I think about the so-called “Fundamental Theorems of Calculus” is a little different from how others think about them. I don’t even think of these as having to do with derivatives and integrals, as such.

Proofs of The Sine Product Formula

In this post, I will accumulate (and perhaps relate) several different proofs of the sine product formula \(\sin(\pi x) = \pi x \prod_{n \geq 1} \left(1 + \frac{x}{n}\right) \left(1 + \frac{x}{-n}\right)\), or the essentially equivalent (by logarithmic differentiation) cotangent sum formula \(\pi \cot(\pi x) = \frac{1}{x} + \sum_{n \geq 1} \frac{1}{n + x} + \frac{1}{-n + x}\), or the essentially equivalent squared cosecant series obtained by differentiating once more (thus obtaining an absolutely convergent sum of \((n + x)^{-2}\) over ALL integers \(n\), which can also be interpreted in terms of the Hurwitz zeta function at \(s = 2\)).

Type Derivatives

An often observed fact in type theory/functional programming/etc is that that, given a type constructor T(X) [a type T parametrized by an input type X], the corresponding type with one “hole” acts like the derivative of T(X). (See “The Derivative of a Regular Type is its Type of One-Hole Contexts”, discussions of “zippers”, etc.)

Supply Chain Theory: The Economic Order Quantity

I have a job now where I do stuff with supply chains and inventory control/optimization. I’d never thought about or been aware of any of this stuff before, but it turns out there’s a surprisingly large amount of interesting math in “supply chain theory”. So, inbetween my explorations of pure math for pure math’s sake on this (infrequently updated…) blog, I’ll also be posting recaps/explanations of this supply chain math, for my own reference.

Elementary Prime Counting

Consider the question of how many primes are \(\leq n\); let us call this quantity \(\pi(n)\), as is traditional.

The Meta-Formula for 1^n + 2^n + 3^n + ... + x^n

[There’s a better version of this post coming when I copy over https://howsridharthinks.wordpress.com/2019/11/19/difference-equations-infinite-sums-generalized-factorial-zeta-functions-etc/, but it’s not fully ready yet. This is an archive of an old Quora answer, in the meanwhile. This is just for the sake of copying everything from the Wordpress site over to the Github site.]

The Irrationality of π^2, and Therefore of π

There are many “different” proofs of the irrationality of \(\pi\) which are all based on the same underlying idea. The proof I describe in this post is also based on the same underlying idea as all the other ones you’ll find in the wild, but in a different presentation, one I personally find clearest for helping me understand what is going on and in what directions it generalizes. Incidentally, this simple proof shows not only the irrationality of \(\pi\) but also the irrationality of \(\pi^2\).

The Generalized Factorial

Suppose you wanted to extend the factorial function to arbitrary arguments. How might you do it?

Solving the Basel Problem with Calc 101

The Basel problem can be solved by simple integration!

3blue1brown: The Wallis Product and the Sine Product

In a past life, I worked for 3blue1brown, and I discovered and made a video for them on a simple new proof of the Wallis product and the sine product more generally. Alas, I no longer work for 3blue1brown. But I had a post on a number of supplements to that video, which I will keep archived for my own purposes here, as well transcribing the full argument from the video for this blog at some point as well:

A Simple Geometric Proof of the Wallis Product

The \(n\)-dimensional unit sphere (in the indexing in which the Earth is a 3-dimensional sphere) has an inner volume which is its surface area divided by \(n\) (by considering each tiny patch of its surface as the base of a figure tapering down to its center), and at the same time, by the argument that projecting two dimensions outwards to the enveloping “cylinder” is area-preserving (stretching latitudinally and longitudinally in precise cancellation, as in the Lambert map projection), we find that the unit \(n\)-sphere’s surface area is \(\tau\) times the unit \((n - 2)\)-sphere’s volume (\(\tau\) here being the circumference of a unit circle).¹