Nosimpler

Network measures that reflect the most salient properties of complex large-scale networks are in high demand in the network research community. In this paper we adapt a combinatorial measure of negative curvature (also called hyperbolicity) to parameterized finite networks, and show that a variety of biological and social networks are hyperbolic. This hyperbolicity property has strong implications on the higher-order connectivity and other topological properties of these networks. Specifically, we derive and prove bounds on the distance among shortest or approximately shortest paths in hyperbolic networks. We describe two implications of these bounds to cross-talk in biological networks, and to the existence of central, influential neighborhoods in both biological and social networks.

It is generally believed that random search processes based on scale-free, Lévy stable jump length distributions (Lévy flights) optimize the search for sparse targets. Here we show that this popular search advantage is less universal than commonly assumed. We study the efficiency of a minimalist search model based on Lévy...

• It seems to be too early for April Fool’s day, and yet the arXiv has Dark Matter as a Trigger for Periodic Comet Impacts by Lisa Randall and Matt Reece, a preprint described as “Accepted by Physical Review Letters, 4 figures, no dinosaurs.” The Register has a story: Dark matter killed the dinosaurs, boffins suggest.

  Also recently at the arXiv in a similar “too early for April 1″ category is Crossing Stocks and the Positive Grassmannian I: The Geometry behind Stock Market, which deals with the “stockmarkethedron”, also known as the Geometrical Jewel at the Heart of Finance.

• The president’s FY2015 budget request is out, with news for HEP not so good: a 6.6% cut proposed in DOE HEP funding. No details about the NSF budget, but the proposal is basically for flat funding (an overall cut of .03% in the research budget). The NSF is proposing one big increase, 13.5% for management. This is just an initial proposal from the administration, with the possibility of something different ultimately emerging from Congress.
• The particle physics documentary Particle Fever opens here in New York at Film Forum tonight, with appearances tonight and this weekend by the director and “physicists from the film”. There’s a review in today’s New York Times.

  I saw the film last fall at the New York Film festival and wrote about it here, with the summary:

  most of it I thought was fantastically good and I really hope it finds distribution and gets widely seen. On the other hand, some of it I thought was a really bad idea.

  The film is a very inspiring inside look at the LHC experimental search for and discovery of the Higgs. My misgivings were about the theoretical framing of the story, which was the Arkani-Hamed point of view that this is all about two alternatives: SUSY or the multiverse. The NYT review shows that these misgivings were quite justified, with the reviewer’s summary of what they learned about the significance of the Higgs from the film:

  While the discovery of the Higgs may not have immediate consequences for the way we live, or applications in the world of technology and industry, its implications, according to “Particle Fever,” could hardly be more profound. Through most of the film, the scientists are awaiting a specific bit of data, a single number that will either vindicate a theory of the universe known as supersymmetry or suggest the possibility of multiple universes.

  The differences between these two outcomes seem very stark. In the first case, more particles are likely to be found, contributing to a detailed and orderly picture of the nature of things. In the second, the Standard Model will be thrown into chaos, and the stability of the universe itself may be called into question. It won’t be the end of the world, but for some theorists, it will feel that way.

  Mr. Kaplan is hoping for supersymmetry. His friend and sometime table tennis partner, Nima Arkani-Hamed of the Institute for Advanced Study in Princeton, is in the multiverse camp.

  Physicists often get outraged when they feel journalists badly misrepresent science to the public. Will they get equally outraged when it is physicists doing the misrepresenting?

• For some insight into the current concerns of particle theorists, you can watch some of the videos at last week’s KITP conference. In particular, there’s Matt Strassler’s talk, where he got all Peter Woit and argued that “one could make the argument” that not seeing SUSY (or anything else stringy) at the LHC “would be significant circumstantial evidence against string theory as a description of nature” and that just seeing the SM at the LHC would be “circumstantial evidence against effective quantum field theory as a complete description of known particle physics”. This got him an argument from Gross about his insufficient enthusiasm for a 100 TeV collider. Gross then also got all Peter Woit, arguing that the failure of the “naturalness” argument for new physics was no big deal since it wasn’t a very good argument to begin with (I get all sorts of grief when I do this..).
  The conference ended with a session of people trying to predict the future of the field 30 years hence. This was mostly pretty discouraging, with a lot of people envisioning more of the same: endless generalities about quantum gravity, firewalls etc. Prominent by its absence was any role of mathematics in theoretical physics, with only Greg Moore speaking up for the question of the significance of now popular 6d superconformal theories, and Nati Seiberg mentioning that connections of the field to mathematics were a good thing.

  Lots of talks mentioned people’s good experiences working with and interacting with Polchinski, who seems to be a very nice guy. I’ve never met him personally, but people have speculated to me that he had something to do with the decision of the arXiv to block links to my blog (he was unhappy about my characterization of his Scientific American article promoting the multiverse). What the truth is about that particular story I suppose I’ll never know.

Update: Another review of Particle Fever leads with this explanation of the main point they got from the film:

Stakes come no higher than in Particle Fever, a dazzling, dizzying documentary about nothing less than whether we exist in a coherent universe of ordered, even beautiful laws — or whether, as Princeton physicist Nima Arkani-Hamed theorizes, our universe is one of an infinite set of other universes defined by a chaotic mash-up of unstable, inexplicable, random conditions.

Update: Reddit has a live Q and A with physicists involved in the film. Savas Dimopoulos (described as “considered the most likely to have a theory confirmed by the LHC”) argues for the multiverse and tells questioners that “We may know about whether Nature prefers the Multiverse or the more traditional (super)symmetry path after the second run of the LHC which will start in a year.” Arkani-Hamed also gives the multiverse argument, also claiming “I envy anyone who is jumping into fundamental physics as a grad student today!”. No theorists in sight who might think there’s more significance to the negative LHC results about SUSY than “must be the multiverse”.

Update: Reddit the next day hosted a live Q and A with Michio Kaku. He there explains to the public that:

The best theory comes from string theory, which states that dark matter is nothing but a higher vibration of the string. We are, in some sense, the lowest octave of a vibrating string. The next octave is dark matter….

The next big accelerator might be the ILC in Japan, a linear collider which might be able to probe the boundaries of string theory…

In the coming decades, I hope we find evidence of dark matter in the lab and in outer space. This would go a long way to proving the correctness of string theory, which is what I do for a living. That is my day job. So string theory is a potentially experimentally verifiable theory.

Seems that well-known theorists going on Reddit to mislead the public is now a daily phenomenon…

I heard an NPR report yesterday with Emily Steel, reporter from the Financial Times, about what kind of attributes make you worth more to advertisers. She has developed an ingenious online calculator here, which you should go play with.

As you can see it cares about things like whether you’re about to have a kid or are a new parent, as well as if you’ve got some disease where the industry for that disease is well-developed in terms of predatory marketing.

For example, you can bump up your worth to $0.27 from the standard $0.0007 if you’re obese, and another $0.10 if you admit to being the type to buy weight-loss products. And of course data warehouses can only get that much money for your data if they know about your weight, which they may or may not since if you don’t buy weight-loss products.

The calculator doesn’t know everything, and you can experiment with how much it does know, but some of the default assumptions are that it knows my age, gender, education level, and ethnicity. Plenty of assumed information to, say, build an unregulated version of a credit score to bypass the Equal Credit Opportunities Act.

Here’s a price list with more information from the biggest data warehouser of all, Acxiom.

There are thousands of natural PC problems. Assuming P NE NP how many natural problems are there that are
in NP-P but are NOT NPC? Some candidates are Factoring, Discrete Log, Graph Isom, some in group theory, and any natural sparse set. See
here for some more.

A student asked me WHY there are so few natural intermediary problems. I don't know but here are some
options:

1. Bill you moron, there are MANY such problems. You didn't mention THESE problems (Followed by a list of problems
   that few people have heard of but seem to be intermediary.)
   
2. This is a question of Philosophy and hence not interesting.
   
3. This is a question of Philosophy and hence very interesting.
   
4. That's just the way it goes.
   
5. By Murphy's law there will be many problems that we can't solve quickly.
   

At least in complexity theory there are SOME candidates for intermediary sets.
In computability theory, where we know Sigma_1 \ne \Sigma_0, there are no
candidates for natural problems that are c.e., not decidable, but not complete. There have been some attempts to show that there can't be any
such sets, but its hard to define ``natural'' rigorously. (There ARE sets that are c.e., not dec, not complete, but they are
constructed for the sole purpose of being there. My darling would call them `dumb ass' sets,
a terminology that my class now uses as well.)

A long time ago an AI student was working on classifying various problems in planning. There was one that was c.e. and not decidable
and he was unable to show it was complete. He asked me to help him prove it was not complete. I told him, without looking at it,
that it was COMPLETE!!!!!!!!! My confidence inspired him to prove it was complete.

So, aside from the answers above, is there a MATH reason why there are so few
intermediary problems in Complexity, and NONE in computability theory?
Is there some other kind of reason?

When do microcircuits produce beyond-pairwise correlations?

Front Comput Neurosci. 2014;8:10

Authors: Barreiro AK, Gjorgjieva J, Rieke F, Shea-Brown E

Abstract
Describing the collective activity of neural populations is a daunting task. Recent empirical studies in retina, however, suggest a vast simplification in how multi-neuron spiking occurs: the activity patterns of retinal ganglion cell (RGC) populations under some conditions are nearly completely captured by pairwise interactions among neurons. In other circumstances, higher-order statistics are required and appear to be shaped by input statistics and intrinsic circuit mechanisms. Here, we study the emergence of higher-order interactions in a model of the RGC circuit in which correlations are generated by common input. We quantify the impact of higher-order interactions by comparing the responses of mechanistic circuit models vs. "null" descriptions in which all higher-than-pairwise correlations have been accounted for by lower order statistics; these are known as pairwise maximum entropy (PME) models. We find that over a broad range of stimuli, output spiking patterns are surprisingly well captured by the pairwise model. To understand this finding, we study an analytically tractable simplification of the RGC model. We find that in the simplified model, bimodal input signals produce larger deviations from pairwise predictions than unimodal inputs. The characteristic light filtering properties of the upstream RGC circuitry suppress bimodality in light stimuli, thus removing a powerful source of higher-order interactions. This provides a novel explanation for the surprising empirical success of pairwise models.

PMID: 24567715 [PubMed]

We apply here the principle of affine symmetry to the nested fullerene cages (carbon onions) that arise in the context of carbon chemistry. Previous work on affine extensions of the icosahedral group has revealed a new organisational principle in virus structure and assembly. We adapt this group theoretic framework here to the physical requirements dictated by carbon chemistry, and show that we can derive mathematical models for carbon onions within this affine symmetry approach. This suggests the applicability of affine symmetry in a wider context in Nature, as well as offering a novel perspective on the geometric principles underpinning carbon chemistry.

Nature Neuroscience 17, 338 (2014). doi:10.1038/nn.3663

Authors: Terence D Sanger & John F Kalaska

A study finds that, during movement preparation, when motor cortex is active, but elicits no muscle output, firing of individual neurons in dorsal premotor and primary motor cortex cancels out at the level of population activity.

You may recall how Tom Leinster, Tobias Fritz and I cooked up a neat category-theoretic characterization of entropy in a long conversation here on this blog. Now Tobias and I have a sequel giving a category-theoretic characterization of relative entropy. But since some people might be put off by the phrase ‘category-theoretic characterization’, it’s called:

• A Bayesian characterization of relative entropy.

I’ve written about this paper before, on my other blog:

• Relative Entropy (Part 1): how various structures important in probability theory arise naturally when you do linear algebra using only the nonnegative real numbers.
• Relative Entropy (Part 2): a category related to statistical inference, FinStat,\mathrm{FinStat}, and how relative entropy defines a functor on this category.
• Relative Entropy (Part 3): statement of our main theorem, which characterizes relative entropy up to a constant multiple as the only functor F:FinStat→[0,∞)F : \mathrm{FinStat} \to [0,\infty) with a few nice properties.

But now the paper is actually done! Let me give a compressed version of the whole story here… with sophisticated digressions buried in some parenthetical remarks that you’re free to skip if you want.

Our gives a new characterization of the concept of relative entropy, also known as ‘relative information’, ‘information gain’ or—by people who like to use jargon to make their work seem obscure—‘Kullback-Leibler divergence’.

Here’s the basic idea. Whenever you have two probability distributions pp and qq on the same finite set X,X, you can define the entropy of qq relative to pp:

S(q,p)=∑x∈Xqxln(qxpx) S(q,p) = \sum_{x\in X} q_x \ln\left( \frac{q_x}{p_x} \right)

Here we set

qxln(qxpx)q_x \ln\left( \frac{q_x}{p_x} \right)

equal to ∞\infty when px=0,p_x = 0, unless qxq_x is also zero, in which case we set it equal to 0. Relative entropy thus takes values in [0,∞].[0,\infty].

Intuitively speaking, S(q,p)S(q,p) measures how surprised you’d be if you thought a situation was described by a probability distribution pp… but then someone came along and said no, it’s really qq.

Or if ‘surprise’ sounds too subjective, it’s the expected amount of information gained when you discover the probability distribution is really q,q, when you’d thought it was p.p.

Tobias and I wanted to use category theory to say what’s so great about relative entropy. We did it using a category FinStat\mathrm{FinStat} where:

• an object (X,q)(X,q) consists of a finite set XX and a probability distribution x↦qxx \mapsto q_x on that set;
• a morphism (f,s):(X,q)→(Y,r)(f,s) : (X,q) \to (Y,r) consists of a measure-preserving function ff from XX to Y,Y, together with a probability distribution x↦sxyx \mapsto s_{x y} on XX for each element y∈Yy \in Y, with the property that sxy=0s_{x y} = 0 unless f(x)=yf(x) = y.

If the raw math seems hard to swallow, perhaps some honey-coated words will help it go down. I think of an object of FinStat\mathrm{FinStat} as a system with some finite set of states together with a probability distribution on its states. This lets me think of a morphism

(f,s):(X,q)→(Y,r) (f,s) : (X,q) \to (Y,r)

in a nice way. First, there’s a measurement process f:X→Yf : X \to Y, a function from the set XX of states of some system being measured to the set YY of states of some measurement apparatus. The condition that ff be measure-preserving says the probability that the apparatus winds up in any state y∈Yy \in Y is the sum of the probabilities of all states of XX leading to that outcome:

ry=∑x∈f−1(y)qx \displaystyle{ r_y = \sum_{x \in f^{-1}(y)} q_x }

Second, there’s a hypothesis ss. This is a guess about the probability that the system being measured is in the state x∈Xx \in X given any measurement outcome y∈Y.y \in Y. The guess is the number sxys_{x y}.

Now, suppose we have any morphism

(f,s):(X,q)→(Y,r) (f,s) : (X,q) \to (Y,r)

in FinStat.\mathrm{FinStat}. From this we get two probability distributions on XX. First, we have the probability distribution pp given by

px=∑y∈Ysxyry♡♡♡ \displaystyle{ p_x = \sum_{y \in Y} s_{x y} r_y } \qquad \qquad \heartsuit\heartsuit\heartsuit

This is our best guess about the the probability that the system is in any given state, given our hypothesis and the probability distribution of measurement results. Second, we have the ‘true’ probability distribution qq.

In fact, this way of assigning relative entropies to morphisms defines a functor

RE:FinStat→[0,∞] RE : \mathrm{FinStat} \to [0,\infty]

where we use [0,∞][0,\infty] to denote the category with one object, the numbers 0≤x≤∞0 \le x \le \infty as morphisms, and addition as composition. More precisely, if

(f,s):(X,q)→(Y,r) (f,s) : (X,q) \to (Y,r)

is any morphism in FinStat,\mathrm{FinStat}, we define

RE(f,s)=S(q,p) RE(f,s) = S(q,p)

where pp is defined as in equation ♡♡♡\heartsuit\heartsuit\heartsuit. This tells us how surprised we are when we learn the true probability distribution qq, if our measurement results were distributed according to rr and our hypothesis was ss.

The fact that RERE is a functor is nontrivial and rather interesting! It says that given any composable pair of measurement processes:

(X,q)⟶(f,s)(Y,r)⟶(g,t)(Z,u) (X,q) \stackrel{(f,s)}{\longrightarrow} (Y,r) \stackrel{(g,t)}{\longrightarrow} (Z,u)

the relative entropy of their composite is the sum of the relative entropies of the two parts:

RE((g,t)∘(f,s))=RE(g,t)+RE(f,s). RE((g,t) \circ (f,s)) = RE(g,t) + RE(f,s) .

We prove that RERE is a functor. However, we go further: we characterize relative entropy by saying that up to a constant multiple, RERE is the unique functor from FinStat\mathrm{FinStat} to [0,∞][0,\infty] obeying three reasonable conditions.

Lower semicontinuity

The first condition is that RERE is lower semicontinuous. The set P(X)P(X) of probability distibutions on a finite set XX naturally has the topology of an (n−1)(n-1)-simplex when XX has nn elements. The set [0,∞][0,\infty] has an obvious topology where it’s homeomorphic to a closed interval. However, with these topologies, the relative entropy does not define a continuous function

S:P(X)×P(X)→[0,∞](q,p)↦S(q,p). \begin{array}{rcl} S : P(X) \times P(X) &\to& [0,\infty] \\ (q,p) &\mapsto & S(q,p) . \end{array}

The problem is that

S(q,p)=∑x∈Xqxln(qxpx)\displaystyle{ S(q,p) = \sum_{x\in X} q_x \ln\left( \frac{q_x}{p_x} \right) }

and qxln(qx/px)q_x \ln(q_x/p_x) is ∞\infty when px=0p_x = 0 and qx>0q_x > 0 — but it’s 00 when px=qx=0.p_x = q_x = 0.

So, it turns out that SS is only lower semicontinuous, meaning that if pi,qip^i , q^i are sequences of probability distributions on XX with pi→pp^i \to p and qi→qq^i \to q then

S(q,p)≤liminfi→∞S(qi,pi) S(q,p) \le \liminf_{i \to \infty} S(q^i, p^i)

We give the set of morphisms in FinStat\mathrm{FinStat} its most obvious topology, and show that with this topology, RERE maps morphisms to morphisms in a lower semicontinuous way.

(Lower semicontinuity may seem like an annoying property. But there’s a way to redeem it. There’s a sneaky topology on [0,∞][0,\infty] such that a function taking values in [0,∞][0,\infty] is lower semicontinuous (in the lim inf sense above) if and only if it’s continuous with respect to this sneaky topology!

Using this idea, we can make FinStatFinStat and [0,∞][0,\infty] into topological categories — that is, categories internal to Top — in such a way that lower semicontinuity simply says

RE:FinStat→[0,∞] RE : FinStat \to [0,\infty]

is a continuous functor.

A bit confusingly, this sneaky topology on [0,∞][0,\infty] is called the upper topology. I’ve fallen in love with the upper topology on [0,∞][0,\infty]. Why?

Well, [0,∞][0,\infty] is a very nice rig, or ‘ring without negatives’. Addition is defined in the obvious way, and multiplication is defined in the almost-obvious way, except that

0⋅∞=∞⋅0=0 0 \cdot \infty = \infty \cdot 0 = 0

Even this is actually obvious if you remember that it’s required by the definition of a rig. But if you try to put the ordinary closed interval topology on [0,∞][0,\infty], you’ll see multiplication is not continuous, because a⋅∞a \cdot \infty is infinite when a>0a \gt 0 but then it suddenly jumps down to zero when aa hits zero. However, multiplication is continuous if we give [0,∞][0,\infty] the upper topology! Then [0,∞][0,\infty] becomes a topological rig.)

Convex linearity

The second condition is that RERE is convex linear. We describe how to take convex linear combinations of morphisms in FinStat,\mathrm{FinStat}, and then the functor RERE maps any convex linear combination of morphisms in FinStat\mathrm{FinStat} to the corresponding convex linear combination of numbers in [0,∞].[0,\infty].

Intuitively, this means that if we take a coin with probability PP of landing heads up, and flip it to decide whether to perform one measurement process or another, the expected information gained is PP times the expected information gain of the first process plus 1−P1-P times the expected information gain of the second process.

(Operadically, the point is that both FinStatFinStat and [0,∞][0,\infty] are algebras of an operad P whose operations are convex linear combinations. The nn-ary operations in P are just probability distributions on an nn-element set. In other words, they’re points in the (n−1)(n-1)-simplex.

So, saying that RERE is convex linear means that

RE:FinStat→[0,∞] RE: FinStat \to [0,\infty]

is a map of P-algebras. But we avoid discussing this in our paper because FinStatFinStat, being a category, is just a ‘weak’ P-algebra, and we decided this would be too much for our poor little readers.

For those who like fine nuances: P is a topological operad, and FinStatFinStat and [0,∞][0,\infty] are algebras of this in the topological category TopCat. As I mentioned, FinStatFinStat is a ‘weak’ P-algebra, meaning the laws for convex linear combinations hold only up to coherent natural isomorphism. [0,∞][0,\infty] is strict… but to get convex linear combinations like λ⋅0+(1−λ)∞\lambda \cdot 0 + (1 - \lambda) \infty to behave continuously, we have to give [0,∞][0,\infty] the upper topology!)

Vanishing on a subcategory

The third condition is that RERE vanishes on morphisms (f,s):(X,q)→(Y,r)(f,s) : (X,q) \to (Y,r) where the hypothesis ss is optimal. By this, we mean that equation ♡♡♡\heartsuit\heartsuit\heartsuit gives a probability distribution pp equal to the ‘true’ one, qq.

That makes a lot of sense conceptually: we don’t gain any information upon learning the truth about a situation if we already knew the truth!

(But the subcategory of FinStatFinStat where we keep all the objects but only these ‘optimal’ morphisms also has a nice category-theoretic significance. Tom Leinster called it FP in this post:

• An operadic introduction to entropy.

That’s because it’s the ‘free P-algebra on an internal P-algebra’, where P is the operad I mentioned. I won’t explain what this means here, because Tom did it! Suffice it to say that it’s a shockingly abstract piece of operad theory that nonetheless manages to capture the concept of entropy very neatly. But that’s plain old entropy, not relative entropy.)

The result

Here, then, is our main result:

Theorem. Any lower semicontinuous, convex-linear functor

F:FinStat→[0,∞] F : \mathrm{FinStat} \to [0,\infty]

that vanishes on every morphism with an optimal hypothesis must equal some constant times the relative entropy. In other words, there exists some constant c∈[0,∞]c \in [0,\infty] such that

F(f,s)=cRE(f,s) F(f,s) = c RE(f,s)

for any any morphism (f,s):(X,p)→(Y,q)(f,s) : (X,p) \to (Y,q) in FinStat.\mathrm{FinStat}.

The proof

The proof is surprisingly hard. Or maybe we’re just surprisingly bad at proving things. But the interesting thing is this: the proof is swift and effective in the ‘generic’ case — the case where the support of the probability measures involved is the whole set they’re living on, and the constant cc is finite.

It takes some more work to handle the case where the probability measures have smaller support.

But the really hard work starts when we handle the case that, in the end, has c=∞c = \infty. Then the proof becomes more like analysis than what you normally expect in category theory. We slowly corner the result, blocking off all avenues of escape. Then we close in, grab its neck, and strangle it, crushing its larynx ever tighter, as it loses the will to fight back and finally expires… still twitching.

You’ve got to read the proof to understand what I mean.

This paper describes an regularized variational framework for developing a spatially localized basis, compressed plane waves, that spans the eigenspace of a differential operator, for instance, the Laplace operator. Our approach generalizes the concept of plane waves to an orthogonal real-space basis with multiresolution capabilities.

We construct schemes for self-replicating clusters of spherical particles, validated with computer simulations in a finite-temperature heat bath. Each particle has stickers uniformly distributed over its surface, and the rules for self-replication are encoded into the specificity and strength of interactions. Geometrical constraints imply that a compact cluster can copy...

Now that we’ve had several results about sequences and series, it seems like a good time to step back a little and discuss how you should go about memorizing their proofs. And the very first thing to say about that is that you should attempt to do this while making as little use of your memory as you possibly can.

Suppose I were to ask you to memorize the sequence 5432187654321. Would you have to learn a string of 13 symbols? No, because after studying the sequence you would see that it is just counting down from 5 and then counting down from 8. What you want is for your memory of a proof to be like that too: you just keep doing the obvious thing except that from time to time the next step isn’t obvious, so you need to remember it. Even then, the better you can understand why the non-obvious step was in fact sensible, the easier it will be to memorize it, and as you get more experienced you may find that steps that previously seemed clever and nonobvious start to seem like the natural thing to do.

For some reason, Analysis I contains a number of proofs that experienced mathematicians find easy but many beginners find very hard. I want to try in this post to explain why the experienced mathematicians are right: in a rather precise sense many of these proofs really are easy, in the sense that if you just repeatedly do the obvious thing you will solve them. Others are mostly like that, with perhaps one smallish idea needed when the obvious steps run out. And even the hardest ones have easy parts to them.

I feel so strongly about this that a few years ago I teamed up with a colleague of mine, Mohan Ganesalingam, to write a computer program to solve easy problems. And after a lot of effort, we produced one that can solve several (but not yet all — there are still difficulties to sort out) problems of the kind I am talking about: easy for the experienced mathematician, but hard for the novice. Now you have some huge advantages over a computer. For example, you understand the English language. Also, you can be presented with a vague instruction such as “Do any obvious simplifications to the expression and then see whether it reminds you of anything,” and you will be able to follow it. (In principle, so could the program, but only if we spent a long time agonizing about what exactly constitutes an “obvious” simplification, what kind of similarity should be sufficient for one mathematical expression to trigger the program to call up another, and so on.) So if a mere computer can solve these problems, you should definitely be able to solve them.

What I plan to do in this post is basically explain how the program would go about proving some of the theorems we’ve proved in the course. To explain exactly how it works would be complicated. However, because you are humans, there are lots of technical details that I don’t need to worry about, and what remains of the algorithm when you ignore those details is really pretty simple.

The rough idea is that you should equip yourself with a small set of “moves” and simply apply these moves when the opportunity arises. That is an oversimplification, since sometimes one can do the moves in “silly” ways, but merely being consciously aware of the moves is very useful. (Incidentally, the notion of “silliness” is hard to define formally but is something that humans find easy to recognise when they see examples of it. So that’s another example of the kind of advantage you have over the computer.)

Subsequences of Cauchy sequences

I’m going to describe a way of keeping track of where you have got to in your discovery of a proof. It’s not something I suggest you do for the rest of your mathematical lives. Rather, it is something that you might like to consider doing if you find it hard to come up with typical Analysis I proofs. If you use this technique a few times, then it should get easier, and after a while you will find that you don’t need to use the technique any more.

The technique is simply to record what statements you are likely to want to use, and what statement you are trying to prove. Both of these can change during the course of your proof discovery, as we shall see.

I think the easiest way to explain this and the moves is to begin by giving an example of the whole process in action. Then I’ll talk about the moves in a more abstract way. Let’s take as an example the proof that if a Cauchy sequence has a convergent subsequence then the sequence itself is convergent.

To begin with, we have nothing we obviously need to use, and a statement that we want to prove. That statement is the following.

—————————————————-
Every Cauchy sequence with a convergent subsequence converges

Let us begin by writing that very slightly more formally, to bring out the fact that it starts with .

—————————————————-
is Cauchy and has a convergent subsequence
converges

The next step is to apply the “let” move, which I’ve talked about several times in lectures. If you ever have a statement to prove of the form “For every such that holds, also holds,” then you can just automatically write “Let be such that holds,” and change your target to that of establishing that holds.

In our case, we write, “Let be a Cauchy sequence that has a convergent subsequence,” and modify our target to that of proving that converges. So now we represent where we’ve got to as follows.

is a Cauchy sequence
has a convergent subsequence
——————————————-
converges

Maybe the purpose of those strange horizontal lines is becoming clearer at this point. I am listing statements that we can assume above the line and ones that we are trying to prove below the line.

At this point it seems natural to give a name to the convergent subsequence that we are given. Let us call it . This again is just one instance of a very general move: if you are told you’ve got something, then give it a name. This sequence has two properties: it is a subsequence of and it converges. I’ll list those two properties separately.

is a Cauchy sequence
is a subsequence of
converges
——————————————-
converges

Having done that, I think I’ll remove the second hypothesis, since the fact that is a subsequence of is implicit in the notation.

is a Cauchy sequence
converges
——————————————-
converges

The second hypothesis here is again telling us we’ve got something: a limit of the subsequence. So let’s apply the naming move again, calling this limit .

is a Cauchy sequence

——————————————-
converges

That’s enough reformulation of our assumptions. It’s time to think about what we are trying to prove. To do that, we use a process called expansion. That means taking a definition and writing it out in more detail. It tends to be good to avoid expanding definitions unless you are genuinely stuck: that way you won’t miss opportunities to use results from the course rather than proving everything from first principles. However, here a proof from first principles is what is required. I’m going to do a partial expansion to start with: a sequence converges if there exists a real number that it converges to.

is a Cauchy sequence

——————————————-
converges to

Now our target has changed to an existential statement. How are we going to find an that the sequence converges to?

Sometimes proving existential statements is very hard, but here it is easy, since we have a candidate for the limit staring us in the face, and better still it is the only candidate around. So let us make a very reasonable guess that the sequence is going to converge to , and make proving that our new target.

is a Cauchy sequence

——————————————-

That’s nice because we’ve got rid of that existential quantifier. But what do we do next? We must continue to expand: this time the definition of . Note that if you want to be able to do this, it is absolutely vital that you know your definitions. Otherwise, you obviously can’t do this expansion move. And if you can’t do that, then you can kiss goodbye to any hopes you might have had of proving this kind of result.

is a Cauchy sequence

——————————————-

Now we have a target that begins with a universal quantifier, so it’s time for the “let” move again.

is a Cauchy sequence


——————————————-

Now things become slightly harder, because this time we do not have a candidate staring us in the face for the thing we are trying to find. (The thing we are trying to find is .) It’s not a bad idea in this situation to try to write out in vague terms what the key statements mean. One can do something like this.

Eventually all terms of are close to each other
Eventually all terms of are close to
————————————————
Eventually all terms of are close to

The rough idea of the proof should now be clear: if all terms in the subsequence are close to and all terms are close to each other, then eventually for each term we can say that it is close to a term in the subsequence, which is itself close to .

Since we are going to need to take two steps from a term in , one to the subsequence and one from the subsequence to , it seems a good idea to apply the two main hypotheses with . So let’s just go ahead and do that and see what we get.

——————————————-

Now we are once again in a position where we have been “given” something — in this case and . So let’s quietly drop the existential quantifiers and use the names and . (Purists might object to using the same names for the particular choices of and that we used when merely asserting that they exist. But this is very common practice amongst mathematicians and does not lead to confusion.)

——————————————-

How do we propose to “force” to be less than ? We are going to try to ensure, for suitable , that and . The first hypothesis tells us that we will be able to get the first condition if and are both at least , and the third hypothesis tells us that we we will be able to get the second condition if .

So our plan is going to be to choose and . For the plan to work, we shall need , , and .

We are now in a position to choose . We want our conclusion to hold when , and the tool we use works when , so it makes sense to take . If we substitute that in, we lose the existential quantifier in the target and arrive at the following.

——————————————-

Now we can apply the “let” move again, to get rid of the universal quantifier in the target statement.

——————————————-

We know we’re going to take , and that we can, since , so let’s go ahead and choose that value for in the first hypothesis. That leaves us with the following.

——————————————-

Just to make clear what I did there, it was a move called substitution. If you have a hypothesis of the form and a hypothesis , then you can substitute in for and get out . (One can also call this modus ponens: I prefer to call it substitution in this case because the condition is somehow not a very serious hypothesis, but more like a “restriction” applied on .)

Since I’ve used the hypothesis and am unlikely to need it again. I have deleted it.

Now we have to decide how to choose and how to choose . Recall that we needed and . In a human proof one just writes, “Let be such that and .” It’s a bit trickier for a computer to find it obvious that such a exists, but again that doesn’t matter to us here. I’ll use to denote the I’m choosing, and write down the conditions I’ve made sure satisfies.

——————————————-

Now we can substitute into the first hypothesis.

——————————————-

We can also substitute into the second hypothesis.

——————————————-

And now we are done by the triangle inequality.

What were the moves we used?

Now that we have gone through a proof, let me list the main proof-generating moves we used.

The “let” move

If you are trying to prove a statement of the form “For every such that holds, also holds,” then write, “Let be such that holds,” (or words to that effect) and adjust your target to proving that holds.

The “naming” move

If you are told that something exists, then give it a name. For example, if you are given the hypothesis is convergent, then you are told that a limit exists. So give it a name such as and change the hypothesis to .

Expansion

If you are trying to prove something and you can’t find a high-level argument (by which I mean one that uses results from the course that are relevant to the statement you are trying to prove), and if what you are trying to prove involves concepts such as convergence or continuity that can be written out in low-level language (often, but not always, involving quantifiers), then rephrase what you are trying to prove in this lower-level way. That is, expand out the definition.

Substitution into a hypothesis

If you are given a hypothesis of the form , then given any object of the same type as , you are free to substitute it in for and obtain the hypothesis .

For example, in the proof above, we had the hypothesis “ is Cauchy”. In expanded form, this reads

We decided to substitute in , which is of the same type of thing as (both are positive real numbers), and yielded for us the statement

(We then applied the “naming” move to get rid of the .)

Modus ponens

Often a hypothesis takes a slightly more general form, where conditions are assumed. That is, it takes the form

or still more generally

There the symbol means “and”, so this is saying that whenever you can find a that satisfies the conditions , then you can give yourself the hypothesis .

Substitution into a target

Suppose that you are trying to prove a statement of the form , and suppose you have identified an object of the same type as that you believe is going to do the job. Then you can change your target statement from to . (In words, instead of trying to show that there exists something that satisfies , you are going to try to show that satisfies .)

We did this when we moved from trying to prove that converges to something to trying to prove that it converges to .

---

This is not a complete set of useful moves. However, it is a start, and I hope it will help to back up my assertion that a large fraction of the proof steps that I take when writing out proofs in lectures are fairly automatic, and steps that you too will find straightforward if you put in the practice. I’ll try to discuss more moves in future posts.

From an interesting essay by Thomas Frank in the June 2013 issue of Harper's:

What was really sick-making, though, was [the] easy assumption that creativity was a thing our society valued.  Our correspondent had been hearing this all his life, since his childhood in the creativity-worshipping 1970s. He had even believed it once, in the way other generations had believed in the beneficence of government or the blessings of Providence. And yet his creative friends, when considered as a group, were obviously on their way down, not up. The institutions that made their lives possible — chiefly newspapers, magazines, universities, and record labels — were then entering a period of disastrous decline. The creative world as he knew it was not flowering, but dying.

When he considered his creative friends as individuals, the literature of creativity began to seem even worse — more like a straight-up insult. Our writer-to-be was old enough to know that, for all its reverential talk about the rebel and the box breaker, society had no interest in new ideas at all unless they reinforced favorite theories or could be monetized in some obvious way. The method of every triumphant intellectual movement had been to quash dissent and cordon off truly inventive voices. This was simply how debate was conducted. Authors rejoiced at the discrediting of their rivals (as poor Jonah Lehrer would find in 2012). Academic professions excluded those who didn’t toe the party line. Leftist cliques excommunicated one another. Liberals ignored any suggestion that didn’t encourage or vindicate their move to the center. Conservatives seemed to be at war with the very idea of human intelligence. And business thinkers were the worst of all, with their perennial conviction that criticism of any kind would lead straight to slumps and stockmarket crashes...

And what was the true object of this superstitious stuff? A final clue came from Creativity: Flow and the Psychology of Discovery and Invention (1996), in which Mihaly Csikszentmihalyi acknowledges that, far from being an act of individual inspiration, what we call creativity is simply an expression of professional consensus. Using Vincent van Gogh as an example, the author declares that the artist’s “creativity came into being when a sufficient number of art experts felt that his paintings had something important to contribute to the domain of art.” Innovation, that is, exists only when the correctly credentialed hivemind agrees that it does. And “without such a response,” the author continues, “van Gogh would have remained what he was, a disturbed man who painted strange canvases.” What determines “creativity,” in other words, is the very faction it’s supposedly rebelling against: established expertise. 

Consider, then, the narrative daisy chain that makes up the literature of creativity. It is the story of brilliant people, often in the arts or humanities, who are studied by other brilliant people, often in the sciences, finance, or marketing. The readership is made up of us — members of the professional-managerial class — each of whom harbors a powerful suspicion that he or she is pretty brilliant as well. What your correspondent realized, relaxing there in his tub one day, was that the real subject of this literature was the professional-managerial audience itself, whose members hear clear, sweet reason when they listen to NPR and think they’re in the presence of something profound when they watch some billionaire give a TED talk. And what this complacent literature purrs into their ears is that creativity is their property, their competitive advantage, their class virtue. Creativity is what they bring to the national economic effort, these books reassure them — and it’s also the benevolent doctrine under which they rightly rule the world.

In the wake of all the Superbowl hoopla, it seems appropriate to offer some excerpts from a trenchant article in The Atlantic:

Last year was a busy one for public giveaways to the National Football League. In Virginia, Republican Governor Bob McDonnell, who styles himself as a budget-slashing conservative crusader, took $4 million from taxpayers’ pockets and handed the money to the Washington Redskins, for the team to upgrade a workout facility. Hoping to avoid scrutiny, McDonnell approved the gift while the state legislature was out of session. The Redskins’ owner, Dan Snyder, has a net worth estimated by Forbes at $1 billion. But even billionaires like to receive expensive gifts...

In Minnesota, the Vikings wanted a new stadium, and were vaguely threatening to decamp to another state if they didn’t get it. The Minnesota legislature, facing a $1.1 billion budget deficit, extracted $506 million from taxpayers as a gift to the team...

A year after Hurricane Katrina hit New Orleans, the Saints resumed hosting NFL games: justifiably, a national feel-good story. The finances were another matter. Taxpayers have, in stages, provided about $1 billion to build and later renovate what is now known as the Mercedes-Benz Superdome... Taxpayers even footed the bill for the addition of leather stadium seats.. Though Louisiana Governor Bobby Jindal claims to be an anti-spending conservative, each year the state of Louisiana forcibly extracts up to $6 million from its residents’ pockets and gives the cash to Benson as an “inducement payment”—the actual term used—to keep Benson from developing a wandering eye...

That’s right—extremely profitable and one of the most subsidized organizations in American history, the NFL also enjoys tax-exempt status. On paper, it is the Nonprofit Football League... The insertion of professional football leagues into the definition of not-for-profit organizations was a transparent sellout of public interest. This decision has saved the NFL uncounted millions in tax obligations..

Baseball, basketball, ice hockey, and other sports also benefit from this same process. But the fact that others take advantage of the public too is no justification.

The Pentagon wants to give away 13,000 mine-resistant, ambush-protected trucks because they have outlived their original purpose.

Although the trucks' armored bodies are credited with protecting U.S. troops from roadside bombs in Iraq and Afghanistan, military planners want more-versatile vehicles that can be deployed quickly as troop levels decrease. A full-size MRAP (pronounced EM-rap, of course) weighs about 40,000 pounds, stands 10 feet tall and costs the Pentagon about $500,000 new...

Interest from foreign militaries has been tepid. But they are a hit with stateside police agencies. Almost 200 trucks have been distributed to police departments since August and requests are pending for an additional 750 trucks. The vehicles, many of which feature machine-gun turrets, are off-limits to private citizens and businesses.

Lucky recipients run from the Ohio State University campus police force to Florence County, S.C., which replaced an armored vehicle from the 1970s that the sheriff department's SWAT team had used for about 15 years. A new armored truck would have cost at least $188,000...

"Nobody will want them," says Dean Lockwood, an analyst with Forecast International Inc. "The Afghan terrain is hell on vehicles. It's eating them alive."

For police, though, the bulky trucks project a show of force at hostage incidents, civil disturbances and other situations where SWAT officers with military-grade weapons, uniforms and helmets are deployed.

Thirteen thousand surplus vehicles that cost a half-million dollars each.
Going to American urban and campus police forces.
To be replaced by even more vehicles.

I'm going to defer commentary.

Not an electric telephone obviously, but a true "phone" designed to transmit sounds over distances, created in South America before the era of European contact.  Smithsonian has the story:

The marvel of acoustic engineering—cunningly constructed of two resin-coated gourd receivers, each three-and-one-half inches long; stretched-hide membranes stitched around the bases of the receivers; and cotton-twine cord extending 75 feet when pulled taut—arose out of the Chimu empire at its height. The dazzlingly innovative culture was centered in the Río Moche Valley in northern Peru, wedged between the Pacific Ocean and the western Andes. “The Chimu were a skillful, inventive people,” Matos tells me as we don sterile gloves and peer into the hollowed interiors of the gourds. The Chimu, Matos explains, were the first true engineering society in the New World, known as much for their artisanry and metalwork as for the hydraulic canal-irrigation system they introduced, transforming desert into agricultural lands...

More at the link.  I've been unable to locate a better photograph than the embed, but it's clear that this was the equivalent of a modern tin-can telephone.

I was looking at a collection of perfectly looped gifs on Buzzfeed and thinking about how they remind me of sample-based electronic music. In both cases, you’re taking a piece of a linear recording and making it cyclical. Do it wrong and it’s extremely irritating. Do it right and it’s mesmerizing. I’ve given a lot of thought to how looping a segment of audio changes its meaning, but am only just starting to think about the visual equivalent.

Like samples in hip-hop and techno, good animated gifs take something familiar and make it strange, or they take something strange and make it familiar. And like samples, gifs are especially expressive when they come from pop culture. Unlike hip-hop and techno producers, gif creators are quite anonymous; I can’t name a single one, and their work is almost always unattributed on the web.

Usually gifs are silly, but sometimes they can be moving. I like this one of a kid riding a dirtbike through the desert from Breaking Bad. No spoilers, but like every character on the show, the kid meets with tragedy; it’s nice to imagine him riding through the desert forever unharmed.

Pairing video loops with sound has so far been mostly super irritating. There’s a TV commercial in rotation right now that does that, and it just looks like an epileptic seizure. Maybe because it’s very difficult to align the optimally satisfying video loop points with the optimally satisfying audio ones. There are some wonderful video remixes based on the idea of looping short segments, but there the priority is sound; the video edits are totally nonsensical, though still satisfying in their own way.

Maybe the only way to pair audio and video loops is to have one of them necessarily be meaningless. Or maybe we should just enjoy the sample and the gif on their own terms.

Author(s): Jianyong Cen, Ping Yuan, and Simin Xue

Ball lightning (BL) has been observed with two slitless spectrographs at a distance of 0.9 km. The BL is generated by a cloud-to-ground lightning strike. It moves horizontally during the luminous duration. The evolution of size, color, and light intensity is reported in detail. The spectral analysis...

[Phys. Rev. Lett. 112, 035001] Published Fri Jan 17, 2014

Sparse Matrix Factorization by Behnam Neyshabur, Rina Panigrahy

We investigate the problem of factorizing a matrix into several sparse matrices and propose an algorithm for this under randomness and sparsity assumptions. This problem can be viewed as a simplification of the deep learning problem where finding a factorization corresponds to finding edges in different layers and values of hidden units. We prove that under certain assumptions for a sparse linear deep network with n nodes in each layer, our algorithm is able to recover the structure of the network and values of top layer hidden units for depths up to O~(n1/6). We further discuss the relation among sparse matrix factorization, deep learning, sparse recovery and dictionary learning.

The attendant slides are here. Of interest is the following slide for the hardware pêople


Highly relevant:
Provable Bounds for Learning Some Deep Representations by Sanjeev Arora, Aditya Bhaskara, Rong Ge, Tengyu Ma

We give algorithms with provable guarantees that learn a class of deep nets in the generative model view popularized by Hinton and others. Our generative model is an n node multilayer neural net that has degree at most n for some \gamma less than 1 and each edge has a random edge weight in [-1; 1]. Our algorithm learns almost all networks in this class with polynomial running time. The sample complexity is quadratic or cubic depending upon the details of the model. The algorithm uses layerwise learning. It is based upon a novel idea of observing correlations among features and using these to infer the underlying edge structure via a global graph recovery procedure. The analysis of the algorithm reveals interesting structure of neural networks with random edge weights.

see also Rong Ge's PhD thesis: Provable Algorithms for Machine Learning Problems and

• Sunday Morning Insight: Randomization is not a dirty word
• Sunday Morning Insight: Sharp Phase Transitions in Machine Learning ?

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

A "no-knowledge" measurement of an open quantum system yields no information about any system observable; it only returns noise input from the environment. Surprisingly, performing such a no-knowledge measurement can be advantageous. We prove that a system undergoing no-knowledge monitoring has reversible noise, which can be cancelled by directly feeding back the measurement signal. We show how no-knowledge feedback control can be used to cancel decoherence in an arbitrary quantum system coupled to a Markovian reservoir that is being monitored. Since no-knowledge feedback does not depend on the system state or Hamiltonian, such decoherence cancellation is guaranteed to be general, robust and can operate in conjunction with any other quantum control protocol. As an application, we show that no-knowledge feedback could be used to improve the performance of dissipative quantum computers subjected to local loss.

When I lived in London, I noticed that bus drivers would tend to wave you on board if you looked like someone who could afford the fare but maybe forgot your travel card or similar. If you seemed to be genuinely poor - as in, didn't have the fare because you were broke - they wouldn't.

Our criminal justice system is a bit like that

A former Halliburton manager was sentenced Tuesday to one year of probation for destroying evidence in the aftermath of BP's massive 2010 oil spill in the Gulf of Mexico.

Owing to the complexity of neuronal circuits, precise mathematical descriptions of brain functions remain an elusive ambition. A more modest focus of many neuroscientists, central pattern generators, are more tractable neuronal circuits specialized to generate rhythmic movements, including locomotion. The relative simplicity and well-defined motor functions of these circuits provide...

EMBO reports:

The new approach is possible due to recent advances in mathematics and  computer technologies. The system involves giving all scientists an annual, unconditional fixed amount of funding to conduct their research. All funded scientists are, however, obliged to donate a fixed percentage of all of the funding that they previously received to other researchers. As a result, the funding circulates through the community, converging on researchers that are expected to make the best use of it. “Our alternative funding system is inspired by the mathematical models used to search the internet for relevant information,” said Bollen. “The decentralized funding model uses the wisdom of the entire scientific community to determine a fair distribution of funding.”

The authors believe that this system can lead to sophisticated behavior at a global level. It would certainly liberate researchers from the time-consuming process of submitting and reviewing project proposals, but could also reduce the uncertainty associated with funding cycles, give researchers much greater flexibility, and allow the community to fund risky but high-reward projects that existing funding systems may overlook.

“You could think of it as a Google-inspired crowd-funding system that encourages all researchers to make autonomous, individual funding decisions towards people, not projects or proposals,” said Bollen. “All you need is a centralized web site where researchers could log-in, enter the names of the scientists they chose to donate to, and specify how much they each should receive.”

The authors emphasize that the system would require oversight to prevent misuse, such as conflicts of interests and collusion.

The (short) paper itself is here, by Johan Bollen, David Crandall, Damion Junk, Ying Ding, and Katy Börner.

For the pointer I thank Charles Klingman.

Interneuron cell types are fit to function

Nature 505, 7483 (2014). doi:10.1038/nature12983

Authors: Adam Kepecs & Gordon Fishell

Understanding brain circuits begins with an appreciation of their component parts — the cells. Although GABAergic interneurons are a minority population within the brain, they are crucial for the control of inhibition. Determining the diversity of these interneurons has been a central goal of neurobiologists,

A Deventer scribe, writing around 1420, found his manuscript ruined by a urine stain left there by a cat the night before. He was forced to leave the rest of the page empty, drew a picture of a cat and cursed the creature with the following words:

“Hic non defectus est, sed cattus minxit desuper nocte quadam. Confundatur pessimus cattus qui minxit super librum istum in nocte Daventrie, et consimiliter omnes alii propter illum. Et cavendum valde ne permittantur libri aperti per noctem ubi cattie venire possunt.”

[Here is nothing missing, but a cat urinated on this during a certain night. Cursed be the pesty cat that urinated over this book during the night in Deventer and because of it many others [other cats] too. And beware well not to leave open books at night where cats can come.]

From Medieval Fragments, via Erik Kwakkel.