How Sridhar Thinks

Consider a simple undirected graph in which every pair of distinct non-adjacent vertices have precisely μ common neighbors, and every pair of adjacent vertices have precisely λ common neighbors. Examples of such graphs are friendship graphs (with μ = 1, λ = 1) and Moore graphs of diameter 2 (with μ = 1, λ = 0). Certain additional conditions force such a graph to be strongly regular, in the sense of all its nodes furthermore having the same degree. One such condition is μ = 0. Another such condition is that μ = 1 while no node is adjacent to all others. At any rate, any two non-adjacent nodes in such a graph have the same number of neighbors. We can see all this as follows:

Hamming codes are well-understood in binary, but here I describe how they generalize to arbitrary fields. (This was apparently first described by Golay in passing in his short article on Golay codes, but I find his description there quite difficult to read.) Let $$V$$ be some vec…

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. (For simplicity of exposition, I'll…

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

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 usuall…

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: By a partition of a natural number n is meant a multiset of positive integers which sum to n. We can…

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 pu…

Here I record some simple thoughts on hylomorphism correspondences. Let $$F$$ be an endofunctor on some category, let $$W : w \to F(w)$$ be an $$F$$-coalgebra, and let $$M : m \to F(m)$$ be an $$F$$-algebra. Then by an $$F$$-hylomorphism, we mean a commutative square of the follo…

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: Suppose given a (possibly large collection) V, along with a small number of opera…

Why is the Yoneda embedding the free cocompletion?

Here, we give a manifestly self-dual presentation of the concept of abelian categories. (We previously discussed abelian categories in terms of their relationship to regular categories.) Consider the following properties a category may have: Has finite limits and finite colimits…

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. For our purposes here, a topos is a category with finite limits, carte…

This is a much more advanced follow-up to our post on elementary prime counting.

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 ar…

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. The proof is in three parts: The first part is the obser…

Let me describe how the free group on countably infinitely many generators embeds inside the free group on two generators: First of all, let's make the observation of Cayley's theorem: Any group embeds into the "concrete" group of its own self-bijections. We can think of each gro…

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 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. We alrea…

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 …

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

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…

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 w…

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 t…

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. Consonant intervals are generally characterized by nice frequency ratios. In particular, n + 1 : n ratios are…

Where does Stirling's approximation $$n! \sim \sqrt{2\pi n} \left(\frac{n}{e}\right)^n$$ come from? Well, $$n! = \prod_{t = 1}^{n} t$$, a discrete product. One obvious way to try to approximate a solution for $$n!$$ is to switch from discrete series to continuous series. People d…

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. Why does this happen? Well, .000 001 002 003… times (1…

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. Suppose also that people show up to the queue as a Poisson p…

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)$$). Also adding up in the same way, albeit this is less obvious perhaps, is "How much doe…

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: The number of partitions of N with distinct parts matches the number of partitions of N with odd parts: Proof: …

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? This is b…

A general discussion of jewels of math concerning GCDs in various contexts. [TODO: Rewrite throughout for general audience, not just people who know math jargon] One of the jewels of mathematics is that a commutative monoid is freely generated on a set (thus, has unique prime fac…

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 c…

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 …

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. Well, here's the clean w…

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 car…

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

1. Jordan decomposition of linear operators.

2. Partial fraction decomposition.

3.1. The Chinese Remainder Theorem.

3.2. Bezout's theorem expressing GCDs as linear combinations

3.3. The Euclidean algorithm for calculating GCDs

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 …

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. The principle in play i…

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. This reproduces th…

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 an…

Let's start with Euler's polyhedron formula. Vertices - Edges + Faces = 2 on a sphere. Why is this? Well, take the sphere, considered as one big face, and draw all the vertices onto it. Then, draw the edges onto it, one by one. Each time you draw an edge connecting two vertices t…

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. One must distinguish between notation and what that notation represents. Different notation can represent the same entity, as in, for example, th…

Suppose you prove B from A and later also prove A from B. Useless, right? Well, no. You’ve proven a wonderful fact. You’ve proven that A and B are equivalent. Each follows, by whatever story you gave, from the other. What you haven’t accomplished is to reach this entailment back …

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. Suppose furthermore that e is essentially surjective on objects (i.…

When polls report a “margin of error”, it doesn’t mean what almost everyone takes it to mean. Tl;dr: In the sense of “margin of error” that you typically see reported for polls, it just means 98% / sqrt(the number of people polled). —— When polls list a margin of error, generally…

Two classic facts are: For symmetric (aka commutative, or abelian, or whatever term you like) monoids, finitary coproducts and finitary products coincide (thus, the underlying set of the finitary coproduct is the Cartesian product of the underlying sets of the individual monoid…

All of the asymmetries1 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. Vaguer thoughts: Indeed, in Set/C…

This is actually quite easy to show. Let’s look at $$e^{-1} = \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \ldots$$. As an alternating series whose terms’ magnitudes keep diminishing (from the second term onward), its limiting value lies strictly inbetween any two …

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 …

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. A span is a pair of maps with a co…