# A Solution to problem 20 in Scott Aaronson’s “Projects aplenty”

Scott Aaronson has a post in his blog, Projects aplenty, where he proposes many research problems for students. One of them is:

20. Do there exist probability distributions $D_1$, $D_2$ over n-bit strings such that $(D_1^2+D_2^2)/2$ (an equal mixture of two independent samples from $D_1$ and two independent samples from $D_2$) is efficiently samplable, even though $D_1$ and $D_2$ themselves are not efficiently samplable?  (This is closely-related to a beautiful question posed by Daniel Roy, of whether the de Finetti Theorem has a “polynomial-time analogue.”)

In the comments, I proposed one solution to the problem. Scott Aaronson sent me an email pointing out that the conditions in which the solution work are so strong that the solution is effectively trivial. I have thought about the problem more and I believe I have found a much better solution.

To be specific, what I have is: Given data $A$ there are distributions $D_0(A)$ and $D_1(A)$ such that it is possible to efficiently approximately sample $D_0(A)^2 + D_1(A)^2$ given $A$. However, neither $D_0(A)$ nor $D_1(A)$ are efficiently approximately sampleable, even given $O (\log |A|)$ bits of advice. Moreover, it is easy to generate appropiate $A$, in the sense that there is a polynomial-time probablistic algorithm which given $1^\lambda$ creates an $A$ with $|A| = \mathrm{poly} (\lambda)$ and $A$ satisfies these properties.

Before I present the solution, some definitions: If $p$ and $P$ are prime with $p | P-1$ and $n \in \mathbb{Z} / P \mathbb{Z}$, then I define $\left( \frac {n} {P} \right)_p = n ^{P/p} \mod P$. When $N$ is an odd number, not necessarily prime, and $n \in \mathbb{Z} / N \mathbb{Z}$, then $\left( \frac {n} {N} \right)$ is the Jacobi symbol of $n$ mod $N$.

Now, to generate $A$: first, pick primes $p$, $q_0$, and $q_1$ with approximately $\lambda$ bits. Let $P$ and $Q$ be primes with $p | P-1$ and $q_0 q_1 | Q-1$. Set $N = P Q$. Set $n$ to be a natural number with $\log(N) \ll n$, and $m = \lfloor \sqrt{P} \rfloor$. Set $g \in \mathbb{Z}/ P\mathbb{Z}$ to be a random $p$th root of unity. Set $(a_{ij})$ to be a random $n \times n$ of elements of $\mathbb{Z} / n\mathbb{Z}$ subject to these properties:

• For all $0 \leq i,j < n$, $\left( \frac {a_{ij}} {N} \right) = 1$ and $a_{ij} a_{ji}$ is a square.
• For any $0 \leq i_0,i_1,j < n$, we have $\left( \frac {a_{i_0 j}} {Q} \right) _{q_0} = \left( \frac {a_{i_1 j}} {Q}) \right) _{q_0}$.
• Similarly, for any $0 \leq i,j_0,j_1 < n$, we have $\left( \frac {a_{i j_0}} {Q} \right) _{q_1} = \left( \frac {a_{i j_1}} {Q}) \right) _{q_1}$.
• For any $0 \leq i,j < n$, $\left( \frac {a_{ij}} {P} \right)_p = g^i$, where $i$ is chosen randomly from the binomial distribution $B(m, 1/2)$.

Then $A = (N, n, (a_{ij}))$.

Given $A$ and a permutation $\pi \in S_n$, define the value $f(\pi) = \prod _{0 \leq i < n} a_{i \pi(i)}$. Then for random $\pi$, $f(\pi)$ samples from a distribution $D$, which constists of random $x \in \mathbb{Z} / n\mathbb{Z}$ with $(x/Q)_{q_0} = \prod_{i and $(x/Q)_{q_1} = \prod_{j and such that $(x/P)_p = g^i$ where $i$ is sampled from $B(n m, 1/2)$.

It is possible to split the distribution $D = (D_0 + D_1) /2$, where $D_0$ consists of sampling $D$ and post-selecting for squares, and $D_1$ consists of sampling $D$ and post-selecting for nonsquares. Then it is possible to sample $(D_0^2 + D_1^2)/2$ as follows: Pick a random permutation $\pi \in S_n$ and take $(f(\pi), f(\pi^{-1}))$. However, as far as I can tell, it is impossible to sample either $D_0$ or $D_1$ individually.

Note that $m$ must be large. Otherwise, there is a nonnegligable probability that $\left( \frac {a_{i_0 j_0} a_{i_1 j_1}} {P} \right)_p = \left( \frac {a_{i_0 j_1} a_{i_1 j_0}} {P} \right)_p$, in which case both $D_0$ and $D_1$ can be sampled by taking $f(\pi) (a_{i_0 j_0} a_{i_1 j_1} / a_{i_0 j_1} a_{i_1 j_0}) ^{2 k}$ for appropiate $\pi$ and large random $k$.

One concern with this approach is that $(D_0^2 + D_1^2)/2$ is not being sampled exactly. However, I believe what is being sampled has a neglible statistical distance from $(D_0^2 + D_1^2)$, at least for large enough $n$. However, I haven’t proven this.

Added 2013-10-25: I have now written an implementation of this distribution. Find it here.

# A Comment on the Prime Number Theorem

(Note: I’m describing here a topic where I can’t personally follow the proofs. Think of this as being a second-hand account)

The prime number theorem states that asymptotically the number of primes less than $N$ is approximately $N / \log(N)$. It is fairly easy to prove that this is true up to a constant, that is, letting $\pi(x)$ denote the number of primes less than $x$, that

$\frac{1}{C} \frac {N} {\log(N)} < \pi(N) < C \frac {N} {\log(N)}$

for some constant $C$. So the interesting thing is the constant factor.

When you think about it, it’s rather strange that the constant factor is exactly one. Consider a similar case: counting the number of twin primes less than a given $N$. The value is conjectured to be approximately $C N / \log(N)^2$, where

$C = 2 \prod_{p\text{ prime}, p \geq 3} 1 - \frac{1} {(p-1)^2}$

This constant $C$ can be generated as follows: We want to determine the probability that $q, q+2$ are both prime for $q < N-2$. The probability for $q$ to be prime and for $q+2$ to be prime are both $\frac{1} {\log(N}$, so assuming they are independent the probability for both being prime is $\frac{1} {\log(N)^2}$. However, these probabilities are not independent. For example, assuming $q$ and $q+2$ are independent would lead to a probability of $\frac{1}{4}$ of them both
being odd, whereas the actual probability is $\frac{1}{2}$. Taking this into account, the probability estimate should be twice what it was before, up to $\frac{2} {\log{N}^2}$. Similarly, it is possible to calculate that the probability that a certain prime $p \geq 3$ divides neither $q$ nor $q+2$ is different by a factor of $1-1/q^2$ than it would under the indepence assumption. Multiplying all these factors out you get the constant $C$.

You would expect something similar to happen when counting primes: That there should be some constant factor that is some product over all primes, and that by default it would be a fairly random-looking number rather than exactly 1. The naive estimate $\pi (N) \approx N \prod_p (1-1/p) = 0$ fails. Still, it seems strange that the fact that each prime number is odd, which reduces the frequency of prime by a half, and that they are all 1 or 2 mod 3, which reduces by $\frac{2}{3}$, and so, all reduce to a constant factor of exactly 1.

The explanation is this: The frequency of the primes is self-adjusting. For instance, in the interval $[1, N]$ there are less primes than there are supposed to be, that would make any number in $[N, 2 N]$ more likely to be prime. Thus facts like how the specific number 2 is prime in the long run make no difference in the density of prime.

# Proposed terminological change: Replace “Inductive Type” with “Free Type”

The elimination axiom for natural numbers, surreal numbers, lists, and trees can all be properly called induction. However, I don’t think the expression if b then x else y is an example of recursion, and so I don’t think 2 should be called an inductive type. Similarly, I don’t like how the term inductive type is used for dependent sums, unit and null types, and the various new types of homotopy type theory. What all these types share in common is that they have a set of constructors and an elimination axiom which essentially says that these constructors are the only way to obtain an element of these types. A better terminology would be such a type is the free type over a set of
constructors, and to call such a type a free type.

# A Small Insight on Quantum Field Theory

I’ve been thinking about quantum field theory for a while now, trying to
understand it.. Here is a small insight I recently made.

One way of thinking about the configuration space is through the field
perspective. There are observables at every point in space, they obey the
Klein-Gordon equation with nonlinear perturbations. Taking the Fourier
transform, you get at every momentum a set of harmonic oscillators, and the
interactions are couplings between them. Quantizing this, each oscillator gets
an integer spectrum which corresponds to how many particles of a given type
there is in a given momentum. So now we get the particle perspective in momentum
space.

Another perspective, which is usually used in less rigorous descriptions of QFT,
is the particle presentation in position space. For example, this is implicit
in the “cloud of virtual particles” intuition. It seems to work, but nobody uses
it in calculation. Presumably it can described precisely by taking the Fourier
transform of the momentum space particles to get position space particles. Like
the field presentation, it seems to be manifestly local.

My small insight is this: there is a direct way to describe this perspective in
terms of the field perspective. It is this: a field at a given point over time
behaves somewhat like a harmonic oscillator. Take the basis derived from the
fixed energy states of these harmonic oscillators to get position-space particle
presentation.

Some consequences:

• A massless field doesn’t behave like a harmonic oscillator at a fixed position because there is no spring constant. This explains a claim I heard that position
space doesn’t work for massless particles. However, extrapolating the creation
operator as the spring consant goes to zero, it looks like something similar can
be made to work when thinking of particle count as an index for a
Taylor-expansion-like decomposition of the wavefunction into polynomials.
• This position space perspective is not Lorenz-invariant. This partially
explains the claim I heard that position space also doesn’t work for massive
particles in the relativistic theory. It also explains why nobody uses this
perspective seriously.

# Why Scientists Don’t Write Poetry

A pillow’s softness, from how it behaves:
To forces it reacts yet it conforms.
The patient repitition of a wave,
Transforming an atom from form to form.
Matter from matter moving fast away.
How everything is hidden in the sum
Of amplitudes of all the different ways.
Yet all the things I do ’till now express
Are mere fragments of a deeper core.
How would I love to faithfully address
The full wonders with all of their galore.
Yet when I try those feelings to compose
My poetry is hightened into prose.

# Propositions as types in Foundations to Constructive Analysis

I was reading Foundations of Constructive Analysis by Errett Bishop, and I came across this intersting passage:

It is not strictly correct to say that a real number $\{x_n\}$ is an element of $\mathbf{R}^+$. An element of $\mathbf{R}^+$ consists of a real number $\{x_n\}$ and a positive integer $n$, such that $x_n > n^{-1}$, because an element of $\mathbf{R}^+$ is not presented until both $\{x_n\}$ and $n$ are given. One and the same real number $\{x_n\}$ can be associated with two distinct (but equal) elements of $\mathbf{R}^+$. Nevertheless we shall continue to refer loosely to a positive real number $\{x_n\}$. On those occasions when we need to refer to an $n$ for which $x_n > n^{-1}$, we shall take the position that it was there implicitly all along.

In other words, the proposition $x \in \mathbf{R}^+$ really stands for the type
of all $n$ with $x_n > n^{-1}$. Bishop does not appear to be aware of the
propositions-as-types interpretation in this book, but he uses it implicitly.