## Profile

Verified name
Dan Piponi
Attended King's College London
2,604 followers|4,317,260 views

## Stream

### Dan Piponi

Shared publicly  -

A plugboard (more specifically an n-plugboard) is a board with n holes in it, each of which can accept the end of a wire. Pick one representative plugboard for each n and call it P(n). We can make a vector space over k, say, (which I’ll call PB) whose basis elements are {P(0), P(1), P(2), P(3), …}.

We can define a product ⊗ on this vector space and make it a commutative algebra. Given two plugboards we can stick them together and then plug in some wires with one end in each of the original parts. Each wire used results in one less hole in each of the two parts. For example, after joining an m-plugboard to an n-plugboard and plugging in k wires we have, in effect, an (m+n-k)-plugboard left over. Define the product of P(m) and P(n) in PB as the sum a(i)P(i) where a(i) is the number of ways you can get an i-plugboard by adding wires from a P(m) to a P(n) joined to it. We don’t care about the order in which the wires are added, which way round the wires are or anything else. One wire is the same as any other. We’re only counting the choices of holes they connect. Extend this multiplication to all of PB by linearity. P(0)=1, the unit.

For example P(2)⊗P(3) = P(5)+6P(3)+6P(1). There is one way of adding no wires from a P(2) to a P(3). There are 3+3 ways to add one wire going from a P(2) to a P(3) leaving a P(3). And there are 3x2 ways to add two wires going from a P(2) to a P(3) leaving a P(1). More generally, a ⊗-product of n plugboards enumerates the ways you can hook up any number of wires with each wire going between two different plugboards.

The Enigma machine from World War II had a plugboard pictured above with 26 holes in it and 10 wires. The number of ways those wires could be plugged in is given by the coefficient of P(6) in P(1)⊗P(1)⊗…26 factors in total…⊗P(1).

So here’s a neat theorem I’m not going to prove: there is an isomorphism ϕ from (PB,+,⊗,0,1) to the algebra of polynomials over k (k[x],+,×,0,1) given by PB(n) → H(n,x) where H(n,x) is the nth “probabilist’s” Hermite polynomial [3]. The ⊗-product becomes ordinary multiplication.

For example H(2,x)H(3,x) = H(5,x)+6H(3,x)+6H(1,x). The number of ways to use the Enigma plugboard is the coefficient of H(6,x) when the polynomial x^26 is written as a sum of Hermite polynomials. (Which is also the coeffcient of x^6 in H(26,x) but that’s another story.)

The theorem is essentially Isserlis’ theorem in disguise, aka Wick’s theorem. It forms the cornerstone of quantum field theory and it's what leads to Feynman diagrams. But I like looking at it in terms of plugboards. (Compare also the connection to wiring up modular synths I mentioned a while back [5].)

There’s another operation you can perform on an n-plugboard - you could just block one hole giving an (n-1)-plugboard. If a plugboard has n holes there are n ways you could do this. So if we want to count the ways to block up holes it makes sense to consider the operator ∂:PB → PB such that ∂(P(n)) = nP(n-1). It’s not too hard to convince yourself that ∂ satisfies the Leibniz rule ∂(ab)=a∂b+(∂a)b. When you block a hole in a product you either block a hole in the first component or block a hole in the second. So we have a differential algebra [2].

The map ϕ is actually an isomorphism of differential algebras and ∂ maps to the ordinary derivative under the isomorphism. Many theorems about derivatives of polynomials carry over to plugboards and vice versa. For example, arguing informally now so as to allow infinite sums (or moving to a suitable completion of PB), think about e = P(0)/0!+P(1)/1!+PB(2)/2!+P(3)/3!+… . This satisfies the “differential equation” ∂e = e. So by the isomorphism we must have ∂ϕ(e) = ϕ(e). But ϕ(e) is essentially a formal power series in x. So solving the “differential equation” we get ϕ(e) = Aexp(x) for some constant A. In other words H(0,x)/0!+H(1,x)/1!+H(2,x)/2!+H(3,x)/3!+ … = Aexp(x) for some A. (A is exp(-1/2) BTW. That exp(-1/2) factor is a reminder that we’re not talking about complete trivialities here.) We can "transfer" other familiar functions like sin and cos from the reals to PB.

There’s lots more I could say. PB tells you all about functions of Gaussian random variables. (I was hoping to use this for some statistics computations but it isn't going to work out...) The isomorphism ϕ is, in some sense, a Gaussian blur(!). There is a shadowy conspiracy theory going on behind all this stuff [6]. But this is enough for now.

[1] https://en.wikipedia.org/wiki/Isserlis%27_theorem
[2] https://en.wikipedia.org/wiki/Differential_algebra
[3] https://en.wikipedia.org/wiki/Hermite_polynomials
[4] https://en.wikipedia.org/wiki/Enigma_machine#/media/File:Enigma-plugboard.jpg
[6] https://en.wikipedia.org/wiki/Umbral_calculus﻿
2 photos
14
2

Another interesting connection: an example of a plugboard in nature is the way the bases in RNA can bind to each other. So if you enumerate all the ways a sequence of n bases can bind to itself you're led inevitably to Hermite polynomials. To see what I'm talking about peek here http://ipht.cea.fr/Docspht/articles/t04/135/publi.pdf﻿

### Dan Piponi

Shared publicly  -

If you're trying to solve a real world problem then at the early stages I think you have to tread very carefully in the way your formulate it mathematically. Once you've formulated it, it's easy to imagine that this is now the problem you need to solve and forget about the original problem. You can then spend a long time making progress on solving the formulation, but fail to realise that you're actually stuck in a rut and that there's another formulation of the original problem that works much better.

I had the problem of trying to find optimal (in some sense) paths for moving a large number of vehicles from various A's to various B's. It seemed natural to pick one vehicle and then optimise for that. The problem of finding the optimal path could then be written as something like a calculus of variations problem. At this point I was now trapped in a particular formulation. Trying to solve the calculus of variations problem led to an ODE, but instead of initial conditions it had both initial and terminal conditions. You can discretise time and use a standard ODE solving method, but you can't simply step forward through time from the start as you don't know, for any choice of starting path, whether it will end the right way. It turns into a messy search problem. And then I had the prospect of solving this problem reliably for a large number of paths.

Eventually I realised I had to break out of my original formulation. Instead of solving for one entire path at a time it works better to solve for many paths incrementally and simultaneously. If you can solve and tabulate the solutions to the problem of getting from each A to each B over the time period s to t, and you can solve from the short time period from s-ds to s, then you can combine these to solve for the entire table of solutions from s-ds to t. Now it's just recursion. This is classic dynamic programming, which was in fact originally invented to solve this very problem in the case where the vehicles were missiles. It can be incredibly easy compared to solving millions of ODEs with initial and terminal conditions.

I think I basically recapitulated the history of control theory, which is unsurprising as I was getting my problem solving clues from web pages on control theory and colleagues who had some experience with related problems. The former approach is the Pontryagin principle approach [1] and the latter is the Hamilton-Jacobi-Bellman approach [2] (which is similar to reinforcement learning). The former approach is probably a good choice if there's a chance you can solve the equations exactly and get a simple formula. The latter approach seems to work better when the quantity you're optimising is determined by big tables of numbers.

[1] https://en.wikipedia.org/wiki/Pontryagin%27s_maximum_principle
[2] https://en.wikipedia.org/wiki/Hamilton%E2%80%93Jacobi%E2%80%93Bellman_equation﻿
29
6

It turns out that in this case, the point you mention is related. The Pontryagin principle is guaranteed to give a solution for much weaker conditions. Pontryagin looked down on the Bellman approach with disdain seeing it as more of a heuristic. But it's a damn useful heuristic.﻿

### Dan Piponi

Shared publicly  -

I mentioned a while back that dimensions are a choice. Here's an example illustrating what I meant.

Here are some differential equations for modeling disease spread that I found on Wikipedia [1]. S, I, R and N=S+I+R correspond to the sizes of population groups and t is time.

dS/dt = -βIS/N
dI/dt = βIS/N-γI
dR/dt = γI

If you use standard physics dimensions then S, I, R and N are dimensionless numbers, t has the dimensions of T (time), and both β and γ have the dimensions T^-1.

Let K be a constant. Note that these differential equations are invariant under this substitution:

S → KS
I → KI
R → KR
N → KN

Whenever a set of equations has a scale invariance like this you can choose to introduce a new dimension with the power of K on the right hand side being the power of the dimension. So along with the usual M (mass), L (length) and T we can now add in P, for "person". So we have [S] = [I] = [R] = [N] = P^1 = P. With this new dimension, the left hand side of the first equation has dimension [dS/dt] = P/T and the right hand side has [-βIS/N] = T^-1 PP/P = P/T. So the first equation is consistent. Same goes for the others.

Among other things, you can use this to check your working. Further down that Wikipedia page is the equation

R0 = β/γ

So [R0] = T^-1/T^-1 = 1.

(That also makes intuitive sense as the Wikipedia article describes R0 as a ratio of numbers of people.)

A few lines later we have

S(t) = S(0)exp(-R0(R(t)-R(0)))

The argument of an exp function needs to be dimensionless. But

[R0(R(t)-R(0))] = 1P = P.

So using dimensions has paid off. We've found an error.

I think the Wikipedia article has mixed two conventions. One where S, I and R represent (dimensionless) proportions of the population in the three three groups, and one where S, I and R represent absolute numbers of people.

This is also something you can implement in software. By giving quantities appropriate types you can think of this as a way you can use a C++ or Haskell compiler, say, as a way to statically prove invariance properties of your quantities. In particular, with such a system in place it would be impossible to implement the putative expression for S(t) without the compiler complaining. Or for systems like Matlab and Excel [2] you can use a separate static analyser to check your code. And you can use it for any scale invariance you (or the machine) identify in your equations, not just the standard ones from physics.

[1] https://en.m.wikipedia.org/wiki/Compartmental_models_in_epidemiology#The_SIR_model_without_vital_dynamics
[2] https://web.engr.oregonstate.edu/~erwig/papers/DimErrors_JVLC09.pdf﻿
13
4

​ it might be silly, but I know the feeling and can relate :) ﻿

### Dan Piponi

Shared publicly  -

E(X+Y)=E(X)+E(Y), where E is expectation, is an elementary fact from probability theory. But sometimes my intuition says it can't possibly be true when X and Y aren't independent. Two examples:

(1) A common solution to Buffon's needle problem [1] involves a trig integral. But the seemingly harder and more general Buffon's noodle problem [2] turns out to have a much easier solution. I'm pretty sure I'd come up with the trig integral solution immediately if I hadn't seen this problem before. But I never came up with the Buffon noodle solution despite it being a near-trivial application of E(X+Y)=E(X)+E(Y). I think the reason I found it hard to see was that it was hard to notice that expectations are truly linear for variables that are so clearly non-independent.

(2) In Markov Chain Monte Carlo (MCMC) [3] you generate a sequence of samples from a probability distribution that are often highly correlated with their neighbours. People sometimes deal with this by "thinning", i.e. by picking every Nth sample, for some N, in the hope that samples N apart will be less correlated. But if you're trying to compute expectations using an MCMC simulation then the linearity of expectation means you don't need to do this. In fact, if you're estimating using the sample mean then thinning increases the variance of your estimate.

For both cases I've seen articles online explicitly remind readers that expectations are linear irrespective of the independence of the random variables. So I suspect I'm not the only one with this intuition failure.

[1] https://en.wikipedia.org/wiki/Buffon%27s_needle
[2] https://en.wikipedia.org/wiki/Buffon%27s_noodle
[3] https://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo﻿
20
6

Right.  And a great example shows up when you're doing integration on an infinite-dimensional Hilbert space H.  Any polynomial function on H only depends on finitely many coordinates, so you can integrate it with respect to the Gaussian measure exp(-<x,x>) dx on a finite-dimensional space, normalized so the integral of 1 is 1.    This procedure is consistent and define an integration algebra in Segal's sense.

Using this we can define things like L^infinity(H), which is a commutative von Neumann algebra, and L^2(H), which is a Hilbert space isomorphic to the so-called "Fock space" of H.   They are completions of the polynomial algebra in various norms.  L^2(H) is the completion of the polynomials in the obvious L^2 norm.﻿

### Dan Piponi

Shared publicly  -

I wrote mini-reviews of the two books pictured, both cited in SETI papers. I wrote them on my iPad Pro. But the iPad Pro is a poorly thought out platform for getting anything done and my reviews no longer exist. I'd rewrite them but I already had to rewrite sections of them numerous times because of iOS bugs. Now I understand what people mean when they talk about a consuMption only platform. (And don't ask me to fix that capital M; there has never been a more stupid keyboard than the Smart Keyboard. Computers have had keyboards since the 50s or 60s. It takes a very special kind of stupid to get it so wrong.)

I highly recommend The Golden Age but maybe not Accelerando. Both have a very high density of interesting ideas.﻿
13

I just got there!﻿

### Dan Piponi

Shared publicly  -

We recently attended a concert in Berkeley with a diverse collection of music including a piece played on horns formed from dried kelp. One performance I enjoyed was Deo Gratias by the Estonian composer Sisask. Here's a version from Venezuela.﻿
·  Translate
4

### Dan Piponi

Shared publicly  -

f(x) = O(g(x)) as x→∞ is shorthand for something like "there exist a y and a C such that for all x ≥ y, f(x) ≤ C|g(x)|". The expanded form starts with an existential quantifier. This means you can't disprove it with counterexamples. Any time you find an x for which it's not true that f(x) ≤ C|g(x)| you can just say "oh, I can't have picked y and C big enough". This means that any statements about the physical world (including statements about physical computers) based on such propositions are unfalsifiable and have no place in science.

But people claim propositions like "quicksort takes time O(n log n) on average" are useful. I disagree. This proposition on its own is completely useless as a statement about real computers. What is useful is certain information about the proof of this statement. There's a gentlemen's agreement that if you prove a proposition of the form f(x) = O(g(x)) then either (a) you really mean "there is a y and a C that are not very large such that..." or (b) you call attention to the fact that the statement is hiding some large numbers. (This often implicitly uses a kind of "law of small numbers", the fact that big numbers tend not to arise spontaneously during proofs of propositions in most branches of mathematics.)

There's another gentlemen's agreement that one shouldn't call attention to this issue at all, or the related ones about the smallness of errors in numerical methods.﻿
11

It's common to say that alpha is 4, and log* is 5. The (or, one) problem is that log is like 40 for a lot of programs, and that isn't big enough that if you're worried about it, you shouldn't also be worried about stuff that is hidden by big-O and the like. But practicing programmers do dismiss algorithms for a log factor while ignoring constant factors. And they do that because we teach them to do it.﻿
In his circles
199 people
Have him in circles
2,604 people

### Dan Piponi

Shared publicly  -

Presented without comment, a handful of counts of deaths by various means in US in 2015. In each case I give my source. I didn't make much effort in checking the sources beyond checking the URL and in some cases a check of the web site mission statement.

"Islamic" terrorism: 20
[http://www.snopes.com/toddlers-killed-americans-terrorists/]

Killings by toddler: 21
[http://www.snopes.com/toddlers-killed-americans-terrorists/]

By lightning: 27
[http://www.lightningsafety.noaa.gov/fatalities.shtml]

Fatal bite from pit bull: 28
[http://www.dogsbite.org/dog-bite-statistics-fatalities-2015.php]

Killed by cops: 1186
[http://thinkprogress.org/justice/2015/12/28/3735190/killed-by-police-2015/]

Killed by gun: 12942
[https://www.thetrace.org/2015/12/gun-violence-stats-2015/]

Traffic fatalities: 38300
[http://www.npr.org/sections/thetwo-way/2016/02/18/467230965/2015-traffic-fatalities-rose-by-largest-percent-in-50-years-safety-group-says]

Cancer: 312150
[http://www.cancer.org/acs/groups/content/@editorial/documents/document/acspc-044509.pdf]﻿
20
6

Clearly, we should build a wall. A very short wall.
﻿

### Dan Piponi

Shared publicly  -

Many scientific papers take the form:

1. Stuff X happened
2. If hypothesis Y is false then the chances of something as extreme as X (for some definition of extreme) happening is less than p.
3. p is small, therefore it is likely that Y is true.

I'm going to ignore the fact that this isn't a sound argument. (An example of a sound argument might be "if X happened then Y is true with probability p. X happened and p is large. Therefore Y is likely true.)

One problem with the argument in 1, 2 and 3 is that if you try many different things that result in many different Xs you expect to be able to eventually cherry pick a suitable X that can be used to justify Y even if it's unlikely.

Given how obvious this problem is, why has it been getting a lot of attention so recently? I remember talking about this with researchers 30 years ago and nobody seemed to care.﻿
15
9

Yes, you got it. Because people rarely publish uninteresting experiments, when you read about an apparent correlation in a sample of 100 people you have no idea how many 100s of people the researchers quietly trawled through previously.﻿

### Dan Piponi

Shared publicly  -

I think I’ve mentioned before that I think audio processing might give a nice set of examples for teaching and motivating complex analysis. With the help of a chill dude on youtube, here’s one.

If you build a circuit to transform a complex AC signal using resistors, capacitors and op-amps then the only thing it can do is multiply the signal by some rational function of the frequency of the signal [1,3]. The amplitude of this complex multiplier is a change in signal amplitude and the argument is a change of phase.

Suppose you just want to modify just the phase of the signal. You need to find rational functions that map the real line (of frequencies) to the circle (of unit amplitudes). A good choice is a Möbius transformation [4] like f[a,ω]=(iaω-1)/(iaω+1), with real positive a. This needs just a small number of electronic components and the implementation is called an allpass filter [2]. As you go from ω=0 to ω=∞ the phase change goes from -1 to 1 via i. Varying a allows you to vary where it passes through i.

If you modify a signal with an allpass filter, and average it with the original signal, you expect the signal to approach zero at frequencies where the phase change approaches -1. This gives a nice way to drop out part of the frequency range from a signal while keeping the rest relatively unmodified.

More generally, you can chain a sequence of allpass filter stages so as to multiply the signal by p[ω]=f[a1,ω]f[a2,ω]…f[an,ω], and then average with the original signal. By varying a1…an with respect to time you can make these dropouts sweep up and down the frequency scale.

When such a circuit is placed between a guitar and an amplifier it’s called a phaser [5]. Here’s a demo:
You can try to guess how the various controls relate to n and a1…an. I’m not sure, but the the ‘resonance’ may be moving the quantities a1…an off the real line so it’s no longer simply an allpass filter [6]. And the model I describe is probably only valid for small signals due to nonlinearities.

There is a lot of elementary complex analysis here. For example you’re essentially hearing the winding number of p in the complex plane because the number of times p takes the value -1 is the number of ‘dropouts’ in the frequency scale. That is, of course, related to the number of poles and zeros of p.

[1] By combinations of Ohm’s law and Kirchoff’s laws, and as long as the op amp is operating in a regime where its behaviour is linear.
[2] https://en.wikipedia.org/wiki/All-pass_filter

[3] Also see https://en.wikipedia.org/wiki/Electrical_impedance
[4] https://en.wikipedia.org/wiki/Möbius_transformation
[5] https://en.wikipedia.org/wiki/Phaser_(effect)
[6] Resonances happen when a pole in p approaches the real line so that the amplitude starts rising towards infinity.﻿
3
1

It's the special filters.﻿

### Dan Piponi

Shared publicly  -

<rant>

I broke a bone in my foot while out running this morning. It's going to be disruptive to my ability to get around but I'm happy to say that (right now at least) I have minimal pain.

Anyway, I go into ER. I'm called into the 'Triage' office and asked "What is your pain number?". I refused to answer such a stupid question. "What's your pain number?" she repeats. Without an answer from me she was unable to proceed. She had to fill in the little box on her PC with a number from 1 to 10. "I don't know what a number means," I complain. In the end she pulls out a diagram with a scale from left to right. It went from 1 on the left to 10 on the right. It had a green on the left that was interpolated to red on the right. And it had a series of line art faces going from a happy face to an unhappy looking face with tears on it. I'm not synaesthetic and my emotions at the time didn't really fit any of the faces so I went for the graph of a constant function and picked the one with a straight line mouth, and said "4".

What is going on here? How am I expected to be able to assign a number to my pain just like that? Do American kids get pain level training from a young age? Was this something I missed out on as a kid?

This was the triage department. They're trying to make comparisons between people to decide who needs treatment first. But rather than do triage, they want me to do it. They want me to make an interpersonal comparison of pain level on some scale I have no experience of so they don't have to do their job. In effect, they're asking me to prioritise my treatment relative to other people by choosing a number which will be compared with other people's numbers. It's a complete abdication of their responsibility.

I'm happy with a number as a very informal measure of pain. "Ow! Ow! Ow! This is a 10" seems like a perfectly good exclamation to me. But usually when I'm asked for a pain number by a doctor I ignore the numbers and give a reply like "it kept me awake last night" or "it doesn't bother me except when I do this and then it's excruciating". Doctors usually seem to be able to work with this. (I'm somewhat influenced by Wittgenstein here with his insistence on external criteria for something to be intelligible. See https://en.wikipedia.org/wiki/Private_language_argument) But this is the first time my refusal to give a number has stalled the triage process. Decisions affecting people's health are based on these stupid pseudo-objective measures. Whatever happened to talking to patients to find out what's wrong with them? ("Can you walk?", "Can you put any weight on it?", "Is it painful to touch?")

The reason this makes me grumpy isn't really about pain. This is just a symptom of something more general: substituting a measurable quantity as a proxy for something that is highly subjective and using this to give a patina of scientific objectivity. I see a lot of this kind of nonsense in fMRI publications. I'm also reminded of David Graeber's recent book on bureaucracy.
</rant>﻿
21

​ I didn't say you meant it. What you're commenting now, however, raises other issues. Guessing the guesser seems to me double as unreliable as pretending to achieve 10% accuracy.﻿

### Dan Piponi

Shared publicly  -

Went to a great talk today by Mark Kasevich from Stanford. His team has been working on atom interference with rubidium atoms. Essentially they toss them, in bunches of around 10^6, up the long tube in the picture, whack them with lasers to put them in a state that is a superposition of two different momenta, and then observe them when they fall down. The wave function becomes the sum of two packets that drift apart. They've managed to get them up to about 50 cm apart and then bring them back together again to interfere the way de Broglie hypothesized.

Besides being an amazing stunt that demonstrates QM working on large(ish) widely separated objects, this has practical applications. Interference between these waves tells you a lot about the path the atoms took with very high precision. You can use this to measure gravity very accurately and you can probably use it to detect gravitational waves. In fact, a pair of these setups on satellites might be sensitive enough to detect stochastic gravitational waves left over from inflation in the early universe.

Another application will be to accurately compare the rate at which rubidium 85 and rubidium 87 atoms fall so as to test the equivalence principle http://www.stanford.edu/group/kasevich/cgi-bin/wordpress/?page_id=11﻿
11
2
People
In his circles
199 people
Have him in circles
2,604 people
Collections Dan is following
Education
• King's College London
Mathematics
• Trinity College, Cambridge
Mathematics
Other profiles
Contributor to
Story
Tagline
Homo Sapiens, Hominini, Hominidae, Primates, Mammalia, Chordata, Animalia
Introduction
Blog: A Neighborhood of Infinity
Code: Github