Ineffective Theory

Links for November 2021

Bidirectional unicode features can be used (e.g. in rust) to produce code that apparently says one thing, but compiles to another.

More from Hannania. I think the way to read him is to ignore all of the conclusions. He does seem to have some talent for picking out interesting, important, and underrated facts.

Claims about politics and technology. From the abstract:

How has mobile internet affected political polarization in the United States? Using Gallup Daily Poll data covering 1,765,114 individuals in 31,499 ZIP codes between 2008 and 2017, I show that, after gaining access to 3G internet, Democratic voters became more liberal in their political views and increased their support for Democratic congressional candidates and policy priorities, while Republican voters shifted in the opposite direction. This increase in polarization largely did not take place among social media users. Instead, following the arrival of 3G, active internet and social media users from both parties became more pro-Democratic, whereas less-active users became more pro-Republican.

Urbanicity and mental health — the correlation goes in the expected direction.

Links for October 2021

Vitalik Buterin discusses finance, the political theory behind cryptoeconomics, and collusion.

Advice on chess improvement. I would interpret this post as a list of things to try.

Orwell on nationalism. See also Paul Graham and Bryan Caplan, but Orwell’s article is descriptive more than normative, and has correspondingly more meat. Some striking claims are included, for instance:

After the fall of France, the French pacifists, faced by a real choice which their English colleagues have not had to make, mostly went over to the Nazis[…]

There’s something rather astonishing about Orwell’s writing, maybe more noticeable in this text than in any other. There is no hint of the Straussian; no indication that there was any group he feared to displease.

Lectures on geometric complexity theory.

This video is deeply offensive — perhaps moreso with context:

The sign problem is not caused by rapid oscillations

It’s tempting to think that the sign problem is due to rapid oscillations of the integrand. In fact, the Wikipedia article on the topic basically says as much:

In applied mathematics, the numerical sign problem is the problem of numerically evaluating the integral of a highly oscillatory function of a large number of variables.

It’s easy to pick up on this intuition. An easy way to obtain a sign problem in one dimension is to consider the integral $$ I(\xi) = \int dx\; e^{-x^2}\cos\left(\xi x\right)\text. $$ This integral has no sign problem at $\xi = 0$, of course, and the sign problem gets exponentially worse as we increase $|\xi|$. Simultaneously, the oscillations of the integrand get more and more rapid.

As far as I can tell, though, the general intuition that rapid oscillations are the fundamental cause of the “hard” sign problem is just not true.

Let’s start looking at another unrealistic example in one dimension. I won’t bother finding a “nice” analytic form to demonstrate, because the difficulty of the sign problem does not usually have anything to do with the analytic structure of the integrand. Here’s a simple integrand with a sign problem: $$ f(x) = e^{-|x|}\begin{cases} 1&x \le 0\\
\epsilon-1&x > 0 \end{cases} $$ The integral $\int f$ is proportional to $\epsilon$, while the quenched integral is always of order unity. As a result, we have $\langle\sigma\rangle \sim \epsilon$, and the sign problem can be made arbitrarily bad without ever making the oscillations more rapid. A similar example is the integral of $\epsilon + \cos \theta$ that features here. The mean-field restriction of the Thirring model has similar behavior, see here.

What creates the sign problem in all these cases is not the rapidness of the oscillations, but rather the fact that there are two regions that cancel each other. One region has positive sign, one has negative sign, and in order to work out the cancellations to decide whether the net integral is positive or negative, each region’s integral must be measured to very high precision. This problem is independent of the shapes of the regions. Even when we know exactly how to sample from the positive region alone, and exactly how to sample from the negative region alone, we still cannot solve the sign problem easily!

Now, these are only one-dimensional integrals, and have little to do with the interesting “physical” sign problems. What about a realistic example? Let’s consider a scalar path integral obtained by Trotterizing $e^{-i H t}$ for the harmonic oscillator (although little would change if we switched to an interacting scalar field theory). The path integral is $$ \int \mathcal D \phi\; e^{i S}\text{, with } S = \int dx\; \frac 1 2 \left(\partial\phi\right)^2 - \frac{m^2}{2} \phi^2 $$ This is a pretty typical example of a sign problem that’s hard to solve in practice. Does it feature rapid oscillations of the integrand? The “speed” with which the integrand is oscillating is easily measured by the derivative of the imaginary part of the action: $\frac{\partial}{\partial \phi} S_I$. This is not particularly large! In fact, this derivative gets no larger as we increase the number of sites on the lattice, while the sign problem is exponentially bad in the number of sites. Meanwhile, this derivative does become large as we take $m$ to be small, which does not make the sign problem particularly worse.

One last way to phrase this, hearkening back to what I said earlier about the sign problem being independent of the shapes of the positive and negative regions. Suppose you are asked not to calculate an integral, but a sum of two integrals: $$ \sigma = \int dx\;f(x) + \int dy\;g(y)\text. $$ Each integrand by itself is perfectly well behaved and sign-problem-free. However, $f(x) < 0$ for all $x$, and $g(y) > 0$ for all $y$. Can you compute the sum efficiently? Monte Carlo methods will yield each integral individually with some error bars — which will overlap, so we will have a hard time deciding whether $\sigma > 0$. You can try pairing points off, but in general $f(x) + g(x)$ may be positive or negative, so we just create an ordinary sign problem again unless we know of a special pairing with nice properties.

And, of course, this sort of sign problem has no oscillations at all.