A Universe of Sorts

Fiction, in the tradition of Stanislaw Lem's reviews of imaginary books .

Samples from the moduli space of all possible mathematics.

§ Hamiltonian FRP

We should be able to write functional reactive programming in a style that's reminiscent of classical mechanics. We currently write it in terms of newton's laws. We should be writing it in terms of hamiltonians --- conserved quantities. What does this mean? I don't really know. Here is a post by Baez about getting to the bottom of noether's theorem which seems relevant.

§ Consensus complexity theory

Consensus is a physical resource. We are currently running out of it, fast.

§ Cohomology of haskell types

We know that some types such as $3x^2$ can be integrated to fill a hole, giving us $x^3$ . On the other hand, $x^2$ cannot be integrated: it gives $x^3/3$ . Is there some kind of cohomology that governs this? Note that right now we don't have $d^2 = 0$ --- This is something we will need to find.

This sort of thinking might help if we are trying to identify how to lay data down in memory; having zero homology would imply that there's no gaps, so we can lay it out contiguously in-memory.

§ Finite differences of haskell types

What happens if we take finite differences? We know that real derivatives give us one-hole contexts.

\begin{aligned} &fdiff(list x) \\ &= fdiff(1/[1-x]) \\ &= 1/[1-(x+h)] - 1/[1-x] \\ &= ([1-x] - [1-(x+h)])/[1-x][1 - (x+h)] \\ &= ([1-x] - [1-x-h])/[1-x][1 - (x+h)] \\ &= (1 - x - 1 + x + h)/[1-x][1 - (x + h)] \\ &= h/[1-x][1 - (x + h)] \\ &= (h, list x, list (either x h)) \end{aligned}

\begin{aligned} &bdiff(list x) \\ &= fdiff(1/[1-x]) \\ &= 1/[1-x] - 1/[1-(x - h)] \\ &= ([1-x] - [1-(x-h)])/[1-x][1-(x-h)] \\ &= ([1-x] - [1-x+h])/[1-x][1-(x-h)] \\ &= (1-x - 1 +x-h))/[1-x][1-(x-h)] \\ &= -h/[1-x][1-(x-h)] \\ \end{aligned}

Divided differences

§ Derivatives of function spaces

we can write $\texttt{list}(x)$ as $f: \texttt{nat} \rightarrow x \simeq x^{\texttt{nat}}$ . If we attempt to compute the derivative, we get:

\begin{aligned} &\frac{d}{dx} (x^{\texttt{nat}}) \\ &= \texttt{nat} x^{\texttt{nat} - 1} \end{aligned}

which is saying "tell me the index of the missing element" --- that is nat, and also keep a list with a hole: that is, $x^{\texttt{nat} - 1}$ .

§ Segment Trees from Mobius Inversion

Mobius inversion allows us to collect information about $g(\leq x)$ in a function $f$

Segment trees / fenwick trees also let us do this. They let us collect information about lists.

If we have an algebra of indexees Ix List and an algebra of 'segments of a list' Seg List, then the fenwick tree is a way to go from repr. to the other. Refer to the orbit representation.

What happens if we replace List with Tree? Ix is easy. What about Seg? Can we have the euler tour 'pop out' from this? How?

This is quite easy. We can use Traversable to fill any data structure; we can use the APL technique of fold /= 0 to check for beginning-and-ending of matching parity.

§ On the geometry of distributed algorithms

§ Abstract

We begin with what a model of computation for distributed systems: processes on a graph which send values from semi-lattices; state variables updated with a monotonic join; conditionals are upward filters. This implicitly ensures parallelism, idempotence, and strong eventual consistency. We then recast this setting into a more computational regime, where states are vectors in $\mathbb Z^n$ , join is pointwise max, and computations are piecewise-linear functions. We then proceed to move to tropical geometry, to associate a tropical varietry to the above distributed algorithm. This allows us re-interpret all previously known ideas of distributed algorithms in a purely geometric setting. From this pivot, we compute cohomology groups, from which we derive clasically known impossibilities --- the PAC theorem, byzantine one-in-third-impossibility, as statements about the non-triviality of the first and higher cohomology groups of the geometry. Finally, present many previously known communication complexity invariants as being topological invariants of the scheme.

§ Samples from the Moduli Space of Mathematics