User john sidles - MathOverflow

For which Millennium Problems does undecidable -> true?

2012-09-30T01:56:35Z

Gregory Chaitin has quoted Marcus du Sautoy to the effect that:

If the Riemann Hypothesis (RH) is undecidable this implies that it's true, because if the RH were false it would be easy to confirm that a particular zero of the zeta function is in the wrong place.

Question(s) Which of the other five (at present) unsolved Clay Institute Millenium Prize Problems similarly have the attribute $\text{undecidable}\to\text{true}$? And do any of the five have the attribute $\text{undecidable}\to\text{false}$?

Context This question first arose in the discussion of "a whole lot of basic questions" that were asked by Tim Gowers on Dick Lipton and Ken Regan's weblog Gödel's Lost Letter and P-NP.

Edit Dick and Ken subsequently posted an essay Why We Lose Sleep Some Nights in which (in a comment) the question is associated to the immanence of the eschaton (or perhaps not) in computational complexity theory. ☺

Answer by John Sidles for What does the adjective "natural" actually mean?

2011-03-01T00:40:01Z

Edit As an example of the increasing prevalence of the notion of naturality in contemporary mathematics, it is notable that Shinichi Mochizuki’s four preprints asserting a proof of the ABC conjecture employ the word "natural" and its derivatives on more than six hundred occasions (for details and several related quotations, see this post on Gödel's Lost Letter and P=NP).

In accord with Daniel Miller's answer above, the study of "naturality" as a formal abstraction in mathematics can be traced back largely to two articles by Saunders Mac Lane and Samuel Eilenberg: Natural isomorphisms in group theory (1942) and General theory of natural equivalences (1945). Both articles are well worth reading.

How did these ideas arise? Roughly speaking, Eilenberg and MacLane began by recognizing that if an arbitrary choice of coordinates makes a difference to the quantities you are calculating and/or the theorems you are proving, then those quantities and theorems are not natural. Mac Lane has described this process in The development and prospects for category theory (1996) as follows:

I emphasize that the notions category and functor were not formulated or put in print until the idea of a natural transformation was also at hand.

Thus, one good start for students is to acquire a thorough practical grasp of naturality in the context of coordinate transformations in linear algebra and differential geometry.

A concrete example of a canonical usage of "naturality", which is accompanied by an extensive motivating discussion, is given in John Lee's Introduction to Smooth Manifolds as the following lemma:

Lemma 12.16: (Naturality of the Exterior Derivative)

If $G\colon M\to N$ is a smooth map, then the pullback map $G^\star\colon \mathcal{A}^k(N)\to \mathcal{A}^k(M)$ commutes with $d$. That is, for all $\omega \in \mathcal{A}^k(N)$, we have $G^\star(d\omega) = d(G^\star\omega)$.

As a commutative diagram the above lemma exhibits a canonical form:

$$\begin{array}{c@{}ccc@{}c} &&d&&\\ &\mathcal{A}^k(N)&\longrightarrow&\mathcal{A}^{k+1}(N)\\[2ex] G^\star\!\!\!\!\!\!&\big\downarrow&&\big\downarrow&\!\!\!\!\!\!\!G^\star\\[2ex] &\mathcal{A}^k(M)&\longrightarrow&\mathcal{A}^{k+1}(M)\\ &&d&& \end{array}$$

Being interested in practical applications of geometrically "natural" formalisms for quantum systems engineering, I've studied the usage in MacSciNet reviews of the words "natural*" (chiefly "natural" and "naturality") and "universal*" (chiefly "universal" and "universality").

Here are the numbers; their use is burgeoning!

Year-Range (natural*, universal*)
2001-2005: (16788 uses, 05288 uses)
1996-2000: (14880, 04977)
1991-1995: (12550, 04432)
1986-1990: (10335, 03343)
1981-1985: (08775, 03013)
1976-1980: (07402, 02412)
1971-1975: (05668, 02040)
1966-1970: (03466, 01167)
1961-1965: (02211, 00610)
1956-1960: (01368, 00406)
1951-1955: (00880, 00253)
1946-1950: (00502, 00107)
1941-1945: (00251, 00060)

So to judge by the literature, it seems that we are entering into a Golden Era of mathematical "naturality" and "universality" ... we can hope so, anyway! :)

Does equality of Hodge star and symplectic star imply Kähler structure?

2012-05-16T21:48:44Z

Question

The question asked is:

On a manifold $M$ equipped with a Riemann metric $g$ and a symplectic structure $\omega$, with $\ast$ the Hodge star and $\ast_s$ the symplectic star, does $\ast=\ast_s$ iff $(M,g,\omega)$ is Kähler?

Answer: no

For the reason posted below.

Definitions

Here the star operators $\ast$ and $\ast_s$ are defined in the usual way (see for example, equation 2.9 of Tseng and Yau Cohomology and Hodge Theory on Symplectic Manifolds: II):

$$ A\wedge \ast B := \langle A,B\rangle_{g^{-1}} dV_g$$ $$A\wedge \ast_{s} B := \langle A,B\rangle_{\omega^{-1}} dV_\omega $$

where $A$ and $B$ are $k$-forms, $\langle\cdot,\cdot\rangle_{g^{-1}}$ is the inner product associated to $g$, $dV_g$ is the volume form associated to $g$, and $\langle\cdot,\cdot\rangle_{\omega^{-1}}$ and $dV_\omega$ are defined analogously with respect to $\omega$.

Motivation

In seeking a mathematically natural link between Hilbert-space expositions of quantum mechanics and product space expositions, both the Hodge star operator and the symplectic star operator enter naturally (for example, in the context of Onsager theory). Moreover, in cases of practical quantum systems engineering interest it is commonly observed that:

the two star operations are identical, and
the dynamical state-manifold is Kählerian.

Does each of these observations mathematically imply the other? An engineer-friendly reference for this fact (if it is a fact) would be very welcome---it's not easy to find discussion of the practical relevance of the symplectic star operation.

Answer by John Sidles for Does equality of Hodge star and symplectic star imply Kähler structure?

2012-05-17T22:07:04Z

To answer the question myself, the answer is (trivially) "no". A fast way to see this is via the following identities, valid for $k$-forms on a manifold of dimension $n$:

$$\ast\ast = (-1)^{k(n-k)}\ \mathrm{Id}$$

$$\ast_s\ast_s = \mathrm{Id}$$

Thus for odd-$k$ forms on even-$n$ manifolds, we have $\ast \ne \ast_s$.

Perhaps some amended version of the postulate could be proved … if anyone posts such amended postulate (or even provides some nice references), then I will rate that answer as "accepted".

Quantum dynamics on varieties and Salmon Prizes

2012-02-10T19:39:50Z

Concluding Progressive Remarks

A new finding is Bates and Oeding's preprint "Toward a salmon conjecture" (arXiv:1009.6181), with its reference to the Salmon Prize.

The Salmon Prize (photo of the prize here) is offered by mathematician/biologist Elizabeth Allman, and can be appreciated in the broad mathematical context that is provided by Topics in Tensors: A Summer School by Shmuel Friedland.

Until such time as further comments are offered, a working answer is:

An introduction to multilinear varieties considered as algebraic/geometric objects may be found on page 99ff of Joe Harris' Algebraic Geometry: a First Course.
A recent comprehensive survey is chapter 7 of Joseph Landsberg's brand-new book Tensors: Geometry and Applications (December 2011), which begins (encouragingly)

"This chapter includes nearly all that is known about defining equations for secant varieties of Segre and Veranese varieties …"
At the conclusion of the meta thread that was started by Andy Putman (who wondered why this question was being downvoted) concrete examples now are given of higher-order 'almost-Hilbert' varieties. The following intent is posted there:

Last night I discovered a brand-new monograph by Joseph Landsberg that encompasses more-or-less the answer sought, and so I have amended the beginning of the question to be a pointer to Landsberg's monograph.

Sometime in the next week or two I will post a concrete mathematical question — framed within the context that Landsberg's monograph supplies — asking for a classification of all multilinear varieties having unit-dimension defect with respect to their natural Segre embedding.

At that time I will request closure of the original question, to be supplanted by this classification question.
A shorter, accessibly written, and free-as-in-freedom introduction to these multilinear varieties is Joseph Landsberg's relatively recent — and much-cited — Bulletin of the AMS survey article "Geometry and the complexity of matrix multiplication" (2008).

Please let me apologize for the deficiencies of original question in conveying to MOF readers the mathematical depth and breadth of these multilinear varieties, their implications for fundamental quantum physics, and their numerous practical applications in engineering fields ranging from the computational complexity matrix multiplication to the simulation of quantum transport.

Fortunately, Joseph Landsberg's recent writings have done an immensely better job of this than the original draft of my MOF question did!

My appreciation and thanks are extended to all who have provided comments, and in particular, sincere congratulations are extended to Theo Johnson-Freyd for providing an answer that has received MOF's first-ever Gold Reversal Medal. It has been great fun to help this happen!

The question asked (as clarified per Joseph Landsberg)

For the theorem of algebraic geometry that is specified below, please provide a reference (or references) that:

states the theorem rigorously,
proves the theorem explicitly,
within a framework that extends naturally to multi-linear algebraic varieties

The theorem for which mathematical references are sought

Let $k\ge1$ be an integer and let $\boldsymbol{\psi}=\{\psi_{(mn)}\}$ and $\boldsymbol{\xi}=\{\xi_{(srm)}\}$ be vectors in $\mathbb{C}^{k^2}$ and $\mathbb{C}^{2(k-1)k}$ respectively. Here ${(}\dots{)}$ is a multi-index, repeated indices are summed, and the indices $\{s,r,m,n\}$ range over $s \in \{1,2\}$ , $r \in \{1,\dots,k-1\}$ , and $m,n \in \{1,\dots,k\}$ . Then we have:

The Second-Hand Lion Theorem (SHLT) $$ %\forall\ \boldsymbol{\psi}\ \colon\ \ \det_{mn}\ \psi_{(mn)} = 0 \quad\Longleftrightarrow\quad \exists\ \boldsymbol{\xi}\ \colon\ \ \psi_{(mn)} = \xi_{(1rm)}\,\xi_{(2rn)}. $$

Context of the question in multilinear algebraic geometry

Primary consideration should be given to references that prove the theorem and/or discuss related theorems within a mathematical framework that extends naturally to multilinear algebraic varieties.

Secondary consideration should be given to references that are reasonably accessible to the (many) engineers and physicists for whom these multilinear varieties increasingly are finding practical applications.

In the context of algebraic geometry, $r$ may be regarded as an index over $(k{-}1)$ order-2 Segre varieties that enter in a rank-$(k{-}2)$ secant join having the natural Segre embedding in the tensor product space $\mathcal{H}_1 \otimes \mathcal{H}_2$ .

In the notation of Joe Harris' Algebraic Geometry: a First Course, the theorem asserts the identity of the preceding Segre embedding with what is called the generic determinantal variety $\mathcal{M}^{(kk)\!}_{k{-}1}$ that comprises (by definition) the set of $k\times k$ complex matrices having matrix rank $k-1$.

Attention is directed particularly to a passage in Harris (page 100) that states:

"We should draw a fundamental and important distinction between bi- and tri- or multilinear objects […] whose invariants are far from being completely understood."

Thus, although the theorem stated can be solved via specialized techniques that apply uniquely to bilinear varieties, a broader and deeper grounding is sought for this theorem within the context that modern algebraic geometry provides, with regard especially to techniques that extend naturally to generic multilinear algebraic varieties. To borrow a phrase from Richard Hamming, "The purpose of the question is insight, not theorems."

Quantum physics and engineering applications

In the context of quantum physics, $s$ may be regarded as an index over two $k$-dimensional Hilbert spaces $\mathcal{H}_1$ and $\mathcal{H}_2$ , each equipped with an $k$-element orthonormal basis, such that $(mn)$ is a multi-index over the quantum amplitudes $\psi_{(mn)}$ that are naturally associated to the $k^2$ orthonormal basis vectors of the bipartite Hilbert space $\mathcal{H}_1 \otimes \mathcal{H}_2$ .

In quantum systems engineering (QSE), determinantal varieties are the bread-and-butter state-spaces of large-scale quantum simulations, because they support both the natural geometric pullback of thermodynamical relations and conservation laws and the numerically efficient integration of dynamical trajectories that respect these relations.

The origin of the SHLT name

The name "SHLT" is a homage to the following dialog line in the film Second Hand Lions:

Uncle Garth (Michael McCaine): This lion's no good … it's … it's … defective.

The word defective refers specifically to a $\mathcal{M}^{(kk)\!}_{k{-}1}$ determinantal variety's one-dimensional (nonlinear) rank-defect as a quantum state-space, relative to the $k^2$ -dimensional Hilbert space in which it is immersed (see below).

As a starting-point, the SHLT is mentioned — but regrettably only in passing and with no derivation given — in the paragraphs following Example 9.2 on page 99 of Harris.

Two quantum physics conjectures

By definition, let a quantum state $\psi \in \mathcal{H} = \mathcal{H}_1 \otimes \mathcal{H}_2$ (so that $\dim \mathcal{H} = k^2$ ) be called $k$-Lion iff $\psi \in \mathcal{M}^{(kk)\!}_{k{-}1}$ (in Harris' notation for $\mathcal{M}\,$ ).

Then we have:

The Weak $k$-Lion Hypothesis

There exists a finite integer $k\lesssim 2^5$ such that no practicable quantum experiment can observationally disprove the hypothesis that the state-space of a symmetrically bipartite dynamical system is $k$-Lion rather than Hilbert.

Physically, the limit $k\lesssim 2^5$ corresponds to the case of quantum entanglement in a bipartite dynamical system having $5+5=10$ qubits in total.

The Weak $k$-Lion Hypothesis is sufficiently difficult to test — although by construction the required tests are far easier than demonstrating fault-tolerant quantum computing (FTLC) — that it is reasonable to suppose that Weak $k$-Lion Hypothesis cannot be feasibly be disconfirmed even for for quite small values of $k$. Hence it is both mathematically and physically natural to conjecture:

The Strong $k$-Lion Hypothesis

There exists a constant of Nature in the form of a finite integer $k$ , such that no experiment can observationally disprove the hypothesis that the state-space of a symmetrically bipartite dynamical system is $k$-Lion rather than Hilbert, for the fundamental reason that the dynamical state-space of Nature is a determinantal variety rather than a Hilbert space.

This question's three four five-level reward structure

Associated to this question is a ~~three~~ ~~four~~ five-level reward structure:

Gain MathOverflow reputation by providing good math literature references.
Contribute to the (wonderful) ongoing GLL debate between Aram Harrow and Gil Kalai, and thereby help also to accelerate the medical goals of the UW/ISH Naturality and Guidance Seminar.
Demonstrate either $k$-Lion Hypothesis to win $100,000 from Scott Aaronson.
Receive MOF's first-ever award of the Gold Reversal Medal. Congratulations, Theo!
Best of all, the Salmon Prize is offered by mathematician/biologist Elizabeth Allman.

Quantum dynamics on varieties: asymptotic quantum trace distance on SHL varieties

2012-02-11T18:13:52Z

The Question Asked

Definition: the Second-Hand Lion trace distance $D_k$

Let $\mathcal{M}^{(kk)}_r$ be the set of $k\times k$ complex matrices of rank $\le r$ having unit trace norm. Then the Second-Hand Lion trace distance $D_k$ is by definition $$D_k = \max_{M_1\in \mathcal{M}^{(kk)}_k}\ \, \min_{M_2\in \mathcal{M}^{(kk)}_{k{-}1}}\ \,\tfrac{1}{2} \text{tr}\,|M_1-M_2|$$

The question asked is, what is the asymptotic behavior of $D_k$ for $k\gg1$?

Physics and Engineering Motivation

The set $\mathcal{M}^{(kk)}_k$ is isomorphic to the quantum Hilbert space $\mathbb{C}^{k^2}$, and the set $\mathcal{M}^{(kk)}_{k{-}1}$ is an determinantal variety that we shall call the SHL variety of order $k-1$; and the SHL variety has a natural embedding in the larger Hilbert space.

Moreover the Second-Hand Lion Theorem assures us:

The SHL variety of order $k-1$ has dimension $k^2-1$, that is, the SHL variety lacks precisely one dimension with respect to the embedding Hilbert space $\mathbb{C}^{k^2}$.
The SHL variety of order $k-1$ is naturally equipped with algebraic coordinates that are well-suited to the efficient numerical integration of trajectories (both metric and symplectic) on the SHL variety.

Physically the question asked therefore amounts to this: For quantum states adversarially chosen within a $k\times k$ Hilbert space, what is the worst-case quantum fidelity with which that Hilbert state can be approximated as an SHL varietal state of order $k-1$?

This question is motivated partly by numerical experiments that indicate (for example) $D_8 \simeq 0.0568$. A reasonable conjecture (for example) may be $D_k = \mathcal{O}\,(1/k)$ .

Broader Motivations

More broadly, the question asked was conceived with a view toward illuminating the general problems of approximating Hilbert-space dynamics with varietal dynamics, in regard to the mathematically natural, physically fundamental, computationally practicable (and perennially surprising) features of these varietal dynamical systems.

Answer by John Sidles for A Book You Would Like to Write

2011-07-21T22:05:58Z

Acknowledgments The following three-volume answer to Gil Kalai's MathOverflow question “A Book You Would Like to Write” is chiefly inspired by Tim Gowers' thoughtful comments on Gödel's Lost Letter and P=NP, which he wrote in response to Dick Lipton's question “Make your own world: what would you do if you could do anything?”

Prologue Here is an excerpt from Gowers' comment on Gödel's Lost Letter:

Gowers' choice “If on the other hand P!=NP, then the price I ask … is that we come to understand far better the subclass of mathematical statements and proofs we are actually interested in. … I would like a world where exactly one of the statements ‘P=NP’ and ‘mathematical creativity can be automated’ is true.”

Let us regard Gowers' choice (as we will call it) not as a wish, but as an engineering directive whose fulfillment requires a bespoke mathematical toolset such that “creativity can be automated.” Specifically, we regard Gowers' choice as a path toward Bill Thurston's goal:

Thurston's goal “The goal of mathematics is to develop enhanced ways for humans to see and think about the world. Mathematics is a transforming journey, and progress in it can better be measured by changes in how we think than by the external truths we discover.

To associate Gowers' choice to Thurston's goal, we embrace Abraham Lincoln's view that our broad objective should be:

Lincoln's objective “To make mutual exchange [of] discovery, information, and knowledge; so that, at the end, all may know every thing, which may have been known to but one, or to but a few [and] to stimulate that discovery and invention into extraordinary activity.”

Balancing these various ideas, we design the mathematical formalisms of the Gowers-Thurston world with a view toward providing “enhanced ways for humans to see and think about” their individual participatory roles in the emerging “extraordinary activities” of the 21st century.

To concretely specify this world's mathematical toolset, we apply a template that physicist Julian Schwinger's students affectionately distilled from his lectures:

Schwinger's template “Although ‘1’ is not perfectly ‘0’ we can effectively regard …”

Applying Schwinger's template, we “effectively regard” the mathematical toolset of Gowers' choice and Thurston's goal as arising from this ansatz:

The Gowers-Thurston-Schwinger (GTS) Ansatz “Although ‘NP’ is not known to be formally separable from ‘P’ we can effectively regard it as such whenever our main purpose is mathematical understanding. Similarly, although ‘Hilbert space’ is not known to be perfectly a ‘low-dimension secant variety of a Segre variety’ we can effectively regard it as such whenever our main purpose is dynamical understanding.”

The first part of the GTS ansatz restricts NP (and thus P) to those algorithms whose runtime attributes are decidable and whose outputs (including random samples) are verifiable; Juris Hartmanis has suggested that this restriction (suitably formalized) might render P and NP provably separable. In effect, the ansatz restricts P and NP to those algorithms that are humanly understandable in the Gowers-Thurston sense. The second part of the GTS ansatz focuses upon systems (both classical and quantum) whose trajectories are dynamically compressed onto low-dimension algebraic manifolds. In effect, the ansatz restricts computational simulations to the noisy and/or low-energy and/or highly symmetric dynamical trajectories that are commonly encountered in nature, in technology, and in the laboratory.

These considerations lead us to envision the Gowers-Thurston-Schwinger world as becoming a concrete 21st century reality via a 10-year path that (if we are lucky) will be described retrospectively by the following three MathSTEMnet reviews. In answer to Gil Kalai's question, the math of Volume I exists today; the math of Volume II foreseeably will exist within the next 36 months or so; the math of Volume III will be the work of many decades.

Needless to say, the MathSTEMnet reviews are entirely imaginary; in particular, the review of Volume III seeks to retell a classic Robert Heinlein medical narrative from 1958 in the dryly arch mathematical voice of Joseph Doob's 1948 review of Claude Shannon's Mathematical theory of communication (MR0026286).

MR2739833
Lane, Alice; Lane, Bob
Elements of Naturality in Simulation and Sensing
Volume I of Surveys of Engineering for Enterprise
Constancy Press, Seattle, 2015. xviii+475 pp.
58-01 (53-01 57-01)

This volume aims to provide solid foundations for classical and quantum simulation. In the first of its three parts students learn the basics of differential and algebraic geometry at the same time that they learn the basics of Hamiltonian dynamics, first in the context of classical molecular dynamics, then in the context of classical interacting spins. From the beginning all state-spaces are treated as algebraic varieties (specifically, secant varieties of Segre varieties) that are endowed with symplectic and metric structure. The second of three parts treats (classical) thermostats and (quantum) Lindbladian processes within a mathematically natural Hamiltonian/Stratonovich formalism. In the final part, classical and quantum tools are merged in the practical context of quantum spin biomicroscopy, viewed both as a Shannon communication channel and as a target for simulation and sensing in synthetic biology.

The resulting volume reads as though Saunders Mac Lane, Vladimir Arnold, and Joe Harris teamed up to cover in one volume the dynamical elements of three classic texts: (1) Charlie Slichter's Principles of Magnetic Resonance, (2) Nielsen and Chuang's Quantum Computation and Quantum Information and (3) Frenkel and Smit's Understanding Molecular Simulation: from Algorithms to Applications — all in the flowing example-filled style of Jack Lee's Introduction to Smooth Manifolds. It is suitable for a senior undergraduate or first-year graduate course (that requires students to unlearn some of what they previously have been taught).

• reviewed by Caradoc Dearborn

MR2739833
Lane, Carla; Lane, David
Elements of Naturality in Surveys and Enterprises
Volume II of Surveys of Engineering for Enterprise
Constancy Press, Seattle, 2020. xxi+560 pp.
58-01 (53-01 57-01)

Volume II in this series takes up where Volume I leaves off: with the description of the molecular dynamics and quantum spin imaging of biological molecules. The first of three parts surveys the quantum theory of spin polarization transport, with an emphasis on transport-based techniques for generating order-unity dynamic nuclear polarization (T-DNP). Substantial emphasis is placed on efficient iterative evaluation of “musical” isomorphisms in trajectory integrations. The second part discusses 3D imaging methods that are enabled by the coherent polarization so achieved. The third part discusses the “crossover region”of imaging at 0.5 nm resolution, below which molecular dynamical simulations carry more information than direct imaging. Each chapter is accompanied by two-part design exercises, the first consisting of a pencil-and-paper (or SymPy) symbolic analysis, the second consisting of a large-scale (SAGE/PyQSE) numerical simulation; working code is provided for most exercises.

The concluding chapter requires students to design an enterprise for spin-imaging the entire nucleus of a eukaryotic cell (via quantum spin microscopy) at 0.5 nm resolution, then refining that imaging information (via molecular simulation) to sub-Angstrom scales. Present rapid developments in quantum spin microscopy, sample hyperpolarization, and molecular dynamic simulation ensure that this section will be outdated within a very few years …and yet no book better conveys the mathematical toolset that is so greatly in-demand to support the burgeoning global enterprise of observational synthetic biology.

• reviewed by Dilys Derwent

MR2739833
Pomfrey, Ella; Longbottom, Finn
Elements of Naturality in Healing and Regeneration
Volume III of Surveys of Engineering for Enterprise
Constancy Press, Seattle, 2025. xxix+870 pp.
58-01 (53-01 57-01)

It is now ten years since Volume I of this series appeared, heralding a new era of comprehensive quantum spin imaging of biomolecular structure, and comprehensive simulation of the the molecular dynamics of these structures. It is now five years since Volume II heralded a new era of synoptic information regarding the workings of “every atom in its place”, very much as von Neumann and Feynman foresaw last century. Now Volume III has appeared, and the authors promise to provide a mathematical “natural” toolset for applying these capabilities in healing and regeneration.

Authors Ella Pomfrey and Finn Longbotton are members of the new breed of physician that are comfortable with symplectic structure and with bone structure, with individual molecules and with individual patients, with genetic and epigenetic variation, with complexity theory and with the evolving cognition of healing brains. They have mastered, both abstractly and in practice, the geometrically, algebraically, combinatorically, and informatically natural tools that previous generation of mathematicians brought to bear in the microscopic theory of healing and regeneration. Now in this volume, Pomfrey and Longbottom seek to bring this same natural toolset to bear on macroscopic healing processes. The emphasis throughout is upon practical clinical verification and validation procedures that ensure that bone, nerves, and minds all cleave to a path that leads to a satisfactory healing.

This reviewer entertains some doubt as to whether our understanding of healing and regeneration, in particular their epigenetic aspects, can ever match the naturality of our microscopic understanding … but no-one is better qualified than the authors, who have a distinguished record in the regenerative treatment of battle trauma, to meet the 21st century's grand challenge of healing, by evolving a mathematically natural understanding of it.

• reviewed by Mungo Bonham

Answer by John Sidles for A Book You Would Like to Write

2011-02-04T20:56:35Z

Note this answer is superseded by a more detailed answer to which the reader is referred.

I would very much like to write the book (or much easier, read someone else's book) Geometric Dynamics with Practical Applications in Classical and Quantum Systems Engineering.

The envisioned book would encompass, via geometric methods, many of the dynamical and informatic themes that Michael Nielsen and Isaac Chuang so excellently cover via algebraic methods, in their Quantum Computation and Quantum Information (2000).

It would be the book that—in an alternative history of 20th century quantum physics—would have grown from Saunders Mac Lane's 1970 Chauvenet Lecture Hamiltonian mechanics and geometry, had Mac Lane first read Nielsen and Chuang's now-classic text, and then read Abhay Ashtekar and Troy Schilling's Geometrical formulation of quantum mechanics (1999), and finally read Carlton Caves' (on-line) note Completely positive maps, positive maps, and the Lindblad form (2000, revised 2002 and 2008).

As for notation, this book would embrace the notation of Jack Lee's admirably clear Introduction to Smooth Manifolds (2003) ... no need for "bras" and "kets"!

Our UW Quantum Systems Engineering (QSE) Group first explored these ideas in an article Practical recipes for the model order reduction, dynamical simulation and compressive sampling of large-scale open quantum systems. This article is sufficiently lengthy (at 96 pages) as to provide much of the material for a short textbook. However, an all-recipe textbook on quantum simulation would lack an overall ordering perspective.

Thus, a void in the existing quantum dynamics literature is an integrative synthesis of the above references by Mac Lane, Nielsen and Chuang, Ashtekar and Schilling, Caves; moreover many other authors—Arnold, Carmichael, Abraham and Marsden, Thurston, etc.—could be added to this list. It takes quite a bit of reading to appreciate that these authors' ideas and formalisms are naturally congruent.

The arxiv preprint Elements of naturality in dynamical simulation frameworks for Hamiltonian, thermostatic, and Lindbladian flows on classical and quantum state-spaces (arXiv:1007.1958) is a first-draft summary of those results needed to establish a coherent set of geometric ideas associated to practical large-scale quantum simulation (fortunately, not very many new results are needed).

Current research interests focus on verification, validation, and runtime estimation (VVR), with a view toward establishing consonance between practical VVR and various "no go" results that complexity theory provides. These investigations are still in an early stage; they largely motivate our TCS StackExchange questions "Are runtime bounds in P decidable? (answer: no)" and "Do runtimes for P require EXP resources to upper-bound? … are concrete examples known? (answer: yes and yes)".

We are working on a narrative that integrates these ideas, our MathOverflow answer to the question "What a Geometer Should Know" is our working outline for that narrative.

The PNAS article "Spin Microscopy's Heritage, Achievements, and Prospects" describes our technical objectives, which originate in roadmaps set forth by von Neumann, Wiener, and Feynman in the era 1946-59; most of my questions and answers here on MathOverflow, and also on TCS StackExchange, are conditioned upon these concrete (and predominantly medical) objectives.

And finally, this first book Geometric Dynamics with Practical Applications in Classical and Quantum Systems Engineering is envisioned as the first of two books ... the second book will be Applications of Quantum Spin Microscopy in Regenerative Medicine. That second book will someday be a topic for a second post.

Answer by John Sidles for What notions are used but not clearly defined in modern mathematics?

2011-03-02T16:26:36Z

In response to Colin Tan's request (below), I have posted these remarks as the TCS StackExchange question "Do the undecidable attributes of P pose an obstruction to deciding P versus NP?"

That a mathematical idea be "clearly defined" is itself an idea that perhaps could be more clearly defined ... one candidate for a more rigorous assertion is that a mathematical intuition be formally decidable. Moreover, widespread intuitions that are eventually proved to be decidable versus undecidable have an illustrious history in mathematics.

These reflections lead to the suggestion this community wiki's question would be better-posed mathematically (and might perhaps be more useful too) if it were amended to read:

"What intuitions are commonly embraced and/or have proved to be broadly useful, but nonetheless are formally undecidable, in modern mathematics?"

One specific example that comes to mind is Emanuele Viola's theorem, with its implication that the set of Turing machines {M} associated to P has no decidable runtime ordering. Viola's proof of undecidability was eye-opening to me, and it has filled the valuable role of leading me to wonder "What else is out there?"

To show the utility of these reflections, Section 1.5.2 of Sanjeev Arora and Boaz Barak's well-respected textbook Computational Complexity: a Modern Approach is titled "Criticisms of P and some eﬀorts to address them". I have often wished that Arora and Barak had written more on this theme. With the help of Viola theorem, this wich becomes specific and rigorous: a section titled "What properties of P are not decidable in modern mathematics?"

No doubt many more examples of "undecidable intuitions of modern mathematics" could be posted, and it would be great fun to read other people's examples. However, it seems inappropriate to amend the topic of a community wiki in such a fundamental respect, and so I am posting this amended question as a suggested general "answer" instead.

Partially in response to Colin Tan's request (in the comments below), I have posted on TCS StackExchange the specific question "What is the proper role of verification in quantum sampling, simulation, and extended-Church-Turing (E-C-T) testing?".

More broadly, on Lance Fortnow's weblog, under the topic "75 Years of Computer Science", the question is raised

"Do there exist languages $L$ that are recognized solely by those Turing machines in $P$ whose runtime exponents are undecidable? Can examples of these machines and languages be finitely constructed?"

... but I am not (yet) prepared to post this as a MathOverflow and/or TCS StackExchange question. Thanks and appreciation are extended to Colin.

In quantum dynamical simulations, what is the symmetric (Riemannian) analog of a Poisson bracket?

2011-05-31T00:13:31Z

The question narrowly posed is:

What is the accepted name of the bracket operation that is obtained by replacing the (antisymmetric) symplectic structure of the Poisson bracket with a (symmetric) Riemann metric?

In the (likely?) event that this bracket operation is known by various names in various disciplines, preferred answer(s) will relate to algebras that are associated to Hamiltonian flows on (low-dimension) Kählerian varieties that are naturally immersed in a (large-dimension) Hilbert space, whose dynamical potentials are the operator symbol functions pulled back from that Hilbert space.

Specifically, in practical applications, the Kählerian varieties generically are (low-dimension) rank-$r$ secant varieties of $n$-factor (equivalently, $n$-particle) Segre varieties.

As explained below, this question is stimulated by Michael Nielsen's recent weblog post Survey Notes on Fermi algebras and the Jordan-Wigner Transform, which points to Michaels's GitHub release titled The-Fermionic-canonical-commutation-relations-and-the-Jordan-Wigner-transform

Michael's write-up poses this broader question:

For what algebraic/geometric reason(s) are fermionic quantum dynamical flows (seemingly) harder to simulate on low-dimension varieties than bosonic quantum dynamical flows?

Background

The key ideas of Charles Slichter's classic 1963 textbook Principles of Magnetic Resonance (still in print, and presently in its 3rd edition) are developed in Chapter 3: Magnetic Dipolar Broadening In Rigid Lattices.

Mathematically speaking, a lot has happened since 1963, and it proves to be very instructive to supplement Slichter's Chapter 3 with material describing quantum spin dynamics in the language of Hamiltonian flow, and quantum simulation in the language of pullback (draft of "Slichter redux" here)

The key to reconciling the old and new ways of thinking about spin dynamics is summarized in the following theorem, which physically speaking, asserts that pullback onto low-dimension varieties preserves much of the algebraic and thermodynamic "quantum goodness" of Hilbert space:

(the above graphic is hosted on GitHub).

This theorem describes how to pullback operator commutator algebras onto low-dimension simulation varieties, and so it is natural to ask (inspired by Michael's GitHub notes):

Onto what algebraic varieties do canonical (fermionic) anticommutators pullback naturally?

A partial answer is supplied by the following lemma, namely, the above theorem goes through if in the Poisson bracket $\langle ds_{\mathcal{H}},dh_{\mathcal{H}}\rangle_{\phi^{-1}_\omega}$ the simple replacement $\omega\to g$ is made, that is, if we simply replace the canonical Kählerian symplectic structure with the canonical Kählerian metric structure. Algebraically speaking, this means that anticommutation relations pullback just as naturally as commutation relations.

So in essence, we would like to extend our quantum pullback theorem, and its umbral discussion of practical applications, to encompass the fermionic dynamics of Michael Nielsen's notes, as well the spin dynamics of Charlie Slichter's textbook.

The practical problem is, it's not so easy (for me) to construct low-dimension algebras that realize (even approximately) the canonical anticommutation relations … whereas low-dimension constructions are easy for (say) angular momentum commutators … this is where expert mathematical advice (even starting name(s) for the symmetric bracket operation) would be welcome.

Applications

The above may seem pretty dry, but these algebraic/geometric considerations are of central importance in the practical pursuit of a goal set in the 1940s and 1950s by von Neumann, Wiener and Feynman (among many mathematicians and scientists of that generation), namely (in von Neumann's words) "to look at an $H$ atom." Very broadly speaking, the relevance to the question asked is that bosonic (commutator-respecting) pullbacks characterize the quantum communication channels by which we see the atoms, while fermionic (anticommutator-respecting) pullbacks characterize their chemical dynamics.

To appreciate the attraction this challenge had for von Neumann, Wiener, and Feynman, it is instructive to start with Feynman's celebrated question: What good would it be to see individual atoms distinctly? and restrict it to: Which is numerically the greater challenge, to catalogue every individual star in the universe, or to catalogue every individual atom in the human body?

Then it is easy to compute, that if a 1.7 meter human body were scaled to the size of the observable universe (at present $\sim45.7\times10^9$ light-years), then the individual atoms would be separated by 4 light-years ... and so the answer is, the two great challenges are numerically comparable.

As Stephane Guisard's and Jose Salgado's awe-inspiring VLT timelapse video shows, the astronomers have made a very good start at their challenge … and as our practical mathematical understanding of spin-and-atom dynamics approaches the astronomer's practical understanding of photon dynamics (hopefully with help from MathOverflow) … well, it will be mighty interesting to participate in both of these great challenges.

Answer by John Sidles for What are some applications of other fields to mathematics?

2011-05-31T22:26:35Z

Misha Gromov's recent Bull. AMS article "Crystals, proteins, stability and isoperimetry" (2011) can be read as a 29-page essay on the requested topic, with a focus particularly on mathematical inspiration arising in evolutionary biology, neurophysiology, and cognitive science. Gromov sets the stage as follows:

One may conjecture that neither cell nor brain would be possible if not for profound mathematical “somethings” behind these, Nature’s inventions. But what are these “somethings”? Why do we, mathematicians, remain unaware of them? … The history of mathematics shows how slow we are when it comes to inventing/recognizing new structures even if they are spread before our eyes, such as hyperbolic space, for instance. … One has to browse through myriad stars—structural specks of Life revealed by biologists—in order to identify the “essential ones”, and when (if ?) we ﬁnd them, we may start on the long road toward new mathematics.

Gromov then goes on to suggest many dozens of concrete questions, arising in many bio-related disciplines, that uniformly direct our vision (to use Scott Aaron's nice similes) from the "leaves" of life to the "roots" of fundamental mathematics.

What does Gromov see (that everyone sees) that inspires him so frequently to conceive mathematics (that no one previously has conceived (Szent-Gyrgyi))? Gromov has written this essay, to tell us precisely what it is, that he presently sees.

Since this is a community Wiki, I will informally suggest that it is great fun to read Gromov's inspiring essay either immediately before, or immediately after, viewing Stephane Guisard and Jose Salgado's similarly inspiring VLT (Very Large Telescope) HD Timelapse Footage.

Gromov is concerned largely with very small (molecular-scale) evolved systems, while Guisard and Salgado are concerned mainly with very large (galactic scale) evolved systems … and yet they are tapping the same source.

Is an immersed Kronecker join always a multilinear variety on a Hilbert space?

2011-05-09T15:33:59Z

The question asked is:

Is the implicitization of an arbitrary-rank immersed Kronecker join always a multilinear variety on a Hilbert space?

This is related to another MathOverflow question

In quantum dynamical simulations, what is the symmetric (Riemannian) analog of a Poisson bracket?

Examples: Let $ {\mathcal{H}}$ be a Hilbert space of vectors $ {\psi}$ that is spanned by a preferred basis that is given as an orthonormal set of $ {n}$-spin (equivalently, $ {n}$-qudit) Kronecker products, with the individual spin bases having possibly varying dimension.

Define the Kronecker join ${\mathcal{K}_{r} \subseteq \mathcal{H}}$ to be the rank- $r$ join of the (nonlinear) subspace of vectors in ${\mathcal{H}}$ that are given as Kronecker products in the preferred basis. Formally speaking, $\mathcal{K}_{r}$ is the naturally immersion in $ {\mathcal{H}}$ of the rank-$r$ secant variety of the $n$-factor Segre variety (see Definitions and synopsis, below).

For example, let $ {\mathcal{H}}$ be spanned by the Kronecker basis associated to two spin-$ {1/2}$ particles, such that the rank-1 states ${\psi\in \mathcal{K}_1}$ have the parametric representation

$\displaystyle \left[\begin{array}{c} \psi_{1}\\ \psi_{2}\\ \psi_{3}\\ \psi_{4} \end{array}\right] = \left[\begin{array}{c} \xi_{a,1}\\ \xi_{a,2} \end{array}\right] \otimes \left[\begin{array}{c} \xi_{b,1}\\ \xi_{b,2} \end{array}\right] = \left[\begin{array}{c} \xi_{a,1}\,\xi_{b,1}\\ \xi_{a,1}\,\xi_{b,2}\\ \xi_{a,2}\,\xi_{b,1}\\ \xi_{a,2}\,\xi_{b,2} \end{array}\right]$

Then we easily verify that ${\mathcal{K}_1}$ , viewed as an projective algebraic variety immersed in ${\mathcal{H}}$ is represented implicitly by the multilinear variety $0 = {\psi_{1} \psi_{4}-\psi_{2}\psi_{3}}$.

Less obviously, let $ {\mathcal{H}}$ be spanned by the Kronecker basis associated to two spin-$ {1}$ particles, such that the rank-2 Kronecker join states ${\psi\in \mathcal{K}_2}$ are represented by

$ \displaystyle \left[\begin{array}{c} \psi_{1}\\ \vdots\\ \psi_{9} \end{array}\right] = \left[\begin{array}{c} \xi^1_{a,1}\\ \xi^1_{a,2}\\ \xi^1_{a,3} \end{array}\right] \otimes \left[\begin{array}{c} \xi^1_{b,1}\\ \xi^1_{b,2}\\ \xi^1_{b,3} \end{array}\right] + \left[\begin{array}{c} \xi^2_{a,1}\\ \xi^2_{a,2}\\ \xi^2_{a,3} \end{array}\right] \otimes \left[\begin{array}{c} \xi^2_{b,1}\\ \xi^2_{b,2}\\ \xi^2_{b,3} \end{array}\right] = \left[\begin{array}{c} \xi^1_{a,1}\,\xi^1_{b,1} + \xi^2_{a,1}\,\xi^2_{b,1} \\ \vdots\\ \xi^1_{a,3}\,\xi^1_{b,3} + \xi^2_{a,3}\,\xi^2_{b,3}\end{array}\right]$

Then we again verify that ${\mathcal{K}_2}$ has a multilinear implicit representation, namely $0 = { \psi_{2} \psi_{6} \psi_{7} + \psi_{3} \psi_{4} \psi_{8} + \psi_{1} \psi_{5} \psi_{9} - \psi_{3} \psi_{5} \psi_{7} - \psi_{1} \psi_{6} \psi_{8} - \psi_{2} \psi_{4} \psi_{9} }$ .

Least obviously (to me), it is empirically the case that every $ {n}$-spin Kronecker join, of every join rank (that can be computed in a reasonable time via Groebner basis implicitization methods) has a multilinear implicit representation on $ {\mathcal{H}}$.

That is why I would be very grateful for a reference and/or a proof that all immersed Kronecker joins have a multilinear implicit representation …or for a counterexample.

Practical Motivation: Kronecker joins are ubiquitous in modern algorithms for large-scale quantum simulation, as they are the main building block for almost all state spaces (tensor network state-spaces, for example). Physically speaking, Kronecker joins loosely "fill up" Hilbert space with a geometry "foamy" algebraic manifold that nonetheless retains sufficient linear and symplectic structure that thermodynamical constraints and standard quantum limits are adequately respected.

Issues relating to multilinearity arise naturally when we seek to describe quantum flows in the language of geometric dynamics, specifically in the context of the following theorem:

In particular, even though in practical calculations we always use multilinear parametric representations of $\mathcal{K}$ , nonetheless it would be very nice to know (as a fundamental mathematical insight) whether parametric multilinearity implies implicit multilinearity too (as seems empirically to be the case).

More broadly, any and all references and/or remarks regarding similar theorems in algebraic geometry, dynamics, etc., and/or regarding better ways of stating this theorem (and similar ones) would be very welcome.

Answer by John Sidles for The half-life of a theorem, or Arnold's principle at work

2011-05-27T16:35:59Z

I ran across the following (to me startling) example in Robert Cromie 1895 techno-thriller The Crack of Doom (reprinted in The End of the World: Classic Tales of Apocalyptic Science Fiction, Michael Kelehan, ed.)

Page 102: "If you consult a common text-book on the physics of the aether, you will find that one grain of matter, contains sufficient energy, if etherised, to raise a hundred thousand tons nearly two miles."

Here "grain" is a standard unit of jewelers (one gram = 15.4 grains). Then it is easy to verify, that within ±2% error, Cromie's "etherised" mass-energy relation is $E = m c^2/2$.

Einstein was 16 years old when Cromie's book appeared (published by a European publishing house) ... a very impressionable age, needless to say. Yet despite the clue that Cromie so generously provided to science fiction fans in Europe, ten years passed before Einstein got the factor of two right.

Kro-necker versus Kron-ecker: which hyphenation is preferred?

2011-05-24T17:05:31Z

Synopsis and concrete practices

Everyone is thanked for their comments, and in view of the diversity of views expressed, I have converted this question to a community wiki.

Here is a working synopsis:

With regard to the alternative hyphenations Kron-ecker versus Kro-necker, the "advanced search" feature of Google Books establishes that both hyphenations are in common usage.
The rules of German-language orthography are sufficiently intricate, and the etymology of the name Kronecker is sufficiently obscure, as to provide well-founded justifications for either hyphenation.
No one has come forth with a set of standardized hyphenations for mathematician's names that is in-use by a major mathematical journal or publishing house.

In light of the preceding findings, one reasonable practice is the following:

Include in the LaTex preamble a list of problematic mathematician's names that (by default) forbids their hyphenation (this was Theo Johnson-Freyd's excellent recommendation):

\hyphenation{Kronecker Riemann Spivak}
Upon the (rare) occasions that acceptable typography requires hyphenation of one of these names, then in the body of the manuscript optional hyphens can be inserted in the LaTeX file:

\LaTeX optionally hyphenates Kron\-ecker Rie\-mann Spi\-vak
In placing optional hyphens, lend equal weight to common usage and correct orthography (recognizing that these can be ambiguous upon occasion).
Search methods help resolve problematic cases, for example the hyphenation Rie-mann is overwhelmingly preferred over Riem-ann.

And finally, we should all remember to be grateful to Donald Knuth, who gave us the wonderful tools that allow us to balance good orthography with good typography.

Original question

The question asked is:

Kro-necker versus Kron-ecker: which hyphenation is preferred?

Equivalently, in TeX/LaTeX should one include "\hyphenation{Kron-ecker}" in the preamble? Or should one simply accept the default TeX/LaTeX hyphenation "Kro-necker"?

A search of the tex-hyphen archives provides neither guidance specifically on "Kronecker," nor general guidance on preferred hyphenations for mathematician's names (except to show that there is a community of people who care passionately about these lexicographical issues).

Therefore, instantly "accepted" will be any MathOverflow answer that provides a standardized "\hyphenation{...}" file (including mathematician's names) from any respected mathematical journal or publishing house.

Although this question is perhaps not the most important ever asked on MatherOverflow, such a preferred-hyphenation list would be welcomed by me, and (IMHO) by many mathematical writers. For example, are there other problematic mathematical names?

Recognizing too that some folks are relatively indifferent to mathematical hyphenation, these folks can provide instruction and amusement by offering opinions on the question "Why has the usage of 'Kronecker' been increasing inexorably for the past fifty years?"

As Mark Twain might have put it:

Any calm person, who is not blind or idiotic, can see that in the year 52,011 or thereabouts, every book produced by human civilization will consist solely of the sentence "Kronecker, Kronecker, Kronecker,…"

There is something fascinating about Google's Books Ngram Viewer. One gets such wholesale returns of conjectures, out of such a trifling investment of fact.

However, any opinions offered in this regard, no matter how erudite or amusingly stated, will not be considered as answers.

Answer by John Sidles for Describe a topic in one sentence.

2011-05-20T14:52:02Z

Terry Tao, in a post on Google Buzz, has given an overview of mathematics in the form of multiple "punch-lines" of the requested variety.

Here are three examples from Tao's post:

Algebra is the mathematics of the "equals" sign, of identity, and of the "main term"; analysis is the mathematics of the "less than" sign, of magnitude, and of the "error term".

Algebra prizes structure, symmetry, and exact formulae; analysis prizes smoothness, stability, and estimates.

Most of geometry would not be classified as either algebra or analysis, but simply as geometry.

Definitely Tao's aphorisms are thought-provoking and inspiring ... but are they useful ? Don't ask me! :)

Partly inspired by Tao's essay, here is a one-sentence definition of quantum mechanics (as optimized for systems engineers) …

Quantum mechanics is the algebraic geometry of $n$-particle Hamiltonian flows and Lindbladian compressions as pulled-back onto the natural $r$-indexed stratification of $r$'th secant varieties of $n$-factor Segre varieties whose $r\to\infty$ limit is … $n$-particle Hilbert space.

… and it turns out to be very useful (and great fun) to rewrite standard quantum physics texts like Charles Slichter's Principles of Magnetic Resonance based upon this one sentence definition.

Joseph Landsberg's recent Bull. AMS review "Geometry and the complexity of matrix multiplication" (2008), which has been praised in multiple MathOverflow posts, provides an overview of the broad utility—despite their unwieldy name—of stratifications of secant varieties of Segre varieties (which extends far beyond quantum physics).

Answer by John Sidles for The phenomena of eventual counterexamples

2011-05-01T16:13:29Z

Hmmm ... as yet, no examples have been given from geometry or dynamics. So here's one.

Supposing that we interpret $P(a)=T$ for $a<n$ to mean "geometric objects have property $P$ for most objects that arise naturally", and let $P$ be the ergodic property, then the Kolmogorov–Arnold–Moser theorem suggests itself as providing the "eventual counterexample."

Domokos Szasz' article "Boltzmann's Ergodic Hypothesis, a Conjecture for Centuries?" (1994) provides an historical overview of the long slow process by which dynamical conjectures that for centuries were widely believed, were eventually proved to be wrong.

Another (related) answer:

In Conway's LIFE game, if the starting patterns are arranged in lexical order, the first self-replicating life-form (known at present) is Andrew J. Wade's Gemini.

The Gemini life-form can be viewed as the first (known) counter-example to the hypothesis "life-forms are not self-replicating". The lexical index of Gemini (as computed from its bounding-box) is $2^{4217807\times4220191}$ ... obviously too large to find by a blind search.

It seems to be generically true of life-forms (both biological-type and Conway-type)—and perhaps formal proofs too?—that special properties are emergent at very large lexical order-number of starting structures.

Answer by John Sidles for Toy Models of Quantum Mechanics

2011-03-21T12:07:24Z

The preceding "toy models" focus mainly on algebraic properties of quantum state-spaces. Students who prefer a more geometric and/or PDE perspective on quantum dynamics may find it instructive to consider classical dynamical systems, which (historically) have always been a rich source of quantum dynamical "toy models".

Classical: The state-spaces of classical dynamical systems typically are endowed with both a symplectic structure and a metric structure. Canonical examples ("toy problems") include the Bloch equations and the Landau-Lifshitz-Gilbert equations: both have $S^2$ as their state-space; the symplectic and metric structures are natural; and in both cases dynamical trajectories unravel according to canonical fluctuation-dissipation relations.

Quantum: $C^n$ is the state-space; the symplectic and metric structures are natural (that is, Kählerian); and dynamical trajectories unravel according to canonical fluctuation-dissipation (that is, Lindbladian) relations.

In this geometric dynamical framework, what are often regarded as "spooky mysteries" of quantum mechanics are seen to be similarly present in classical theories; the main change is that global spectral theorems that apply in $C^n$ appear classically as local theorems involving dynamical flow.

These ideas are scattered throughout in the literature of math and physics, but there is at present no single textbook that develops this unified classical/quantum dynamical point of view. This for me defines " a book that you would like to write" (in Gil Kalai's phrase); further references to the literature can be found in that post.

In the meantime, a good "toy" exercise is to write down the symplectic and metric structures, and the Hamiltonian and Lindbladian potentials, that describe the Bloch equations in geometrically natural terms. In particular, an illuminating exercise is to derive via classical geometric methods the results that Charles Slichter's Principles of magnetic resonance derives quantum mechanically in Section 3.2, equation 3.7.

Note added: At the 52nd ENC Conference at Asilomar conference, we reduced the above ideas to practice, by redrafting Chapter III of Slichter's Principles of magnetic resonance in the language of geometric dynamics (PDF here). Here is the main theorem:

In essence, it turns out to be surprisingly easy to construct nonlinear quantum state-spaces that respect both thermodynamic "goodness" (that is, Kählerian structure) and quantum "goodness" (that is, Lindbladian structure).

Ought we to regard Kronecker state-spaces as legitimate quantum foil theories? Or are they merely useful computational idioms? Don't ask us ... as quantum simulations become more-and-more realistic, the division between quantum foil theories and practical computational tools is becoming less distinct.

Answer by John Sidles for "Closed-form" functions with half-exponential growth

2010-12-07T22:36:11Z

On Dick Lipton's weblog, I posted a brief essay on demi-exponential functions, which I repeat here:

To expand upon Ken's remarks regarding demi-exponential functions (which is a fine name for them!), the analytic structure of these functions derives from the Lambert $W$ function, which is the subject of a classic article On the Lambert W Function (1996) by Corless, Gonnet, Hare, Jeffrey, and Knuth (yes, one somehow knew that Donald Knuth's name would arise in connection to such an interesting function ... to date this article has received more than 1600 references).

The connection arises via the following construction. Suppose that a demi-exponential function $d$ satisfies $d \circ d \circ \dots \circ d \circ z = \gamma \beta^z$, where $d$ is composed $k$ times. We say that $k$ is the order of the demi-function, $\gamma$ is the gain and $\beta$ is the base. It is easy to show that the fixed points of $d$ are given explicitly in terms of the $n$-th branch of the Lambert function as $z_f = -W_n(-\gamma \ln \beta)/\ln \beta$. Then by a series expansion about these fixed points (optionally augmented by a Pade resummation) it is straightforward to construct the demi-exponential functions both formally and numerically.

Provided the demi-exponential base and gain satisfy $\gamma \le 1/(e \ln \beta)$, such that the fixed points associated to the $n=-1$ branch of the $W$-function are real and positive, this construction yields smooth demi-exponential functions that pleasingly accord with our intuition of what demi-exponential functions ``should'' look like.

Counter-intuitively though, whenever the specified gain and base are sufficiently large that $\gamma > 1/(e \ln \beta)$, then the demi-exponential function has no real-valued fixed points, but rather develops jump-type singularities. In particular, the seemingly reasonable parameters $\beta=e$ and $\gamma=1$ have no smooth demi-exponential function associated to them (at least, that's the numerical evidence).

Perhaps this is one reason that demi-exponential functions have a reputation for being difficult to construct ... it is indeed very difficult to construct smooth functions for ranges of parameters such that no function has the desired smoothness!

It might be feasible (AFAICT) to write an article On demi-exponential functions associated to the Lambert W Function, and to include these functions in standard numerical packages (SciPy, MATLAB, Mathematica, etc.).

Some tough challenges would have to be met, however. Especially, there is at present no known integral representation of the demi-exponential functions (known to me, anyway), and yet such a representation would be very useful (perhaps even essential) in rigorously proving the analytical structures that the numerical Pade approximants show us so clearly.

Mathematica script here (PDF).

Here's what these functions look like:

Final note: Inspired by the recent burst of interest in these demi-exponential functions, and mainly for my own recreational enjoyment, I have verified (numerically) that demi-exponential functions $d$ having (1) fixed point $z_f = d(z_f) = 1$, and (2) any desired asymptotic order, gain, and base can readily be constructed.

I'd be happy to post details of this construction ... but it's not clear that anyone has any practical interest in computing numerical values of demi-exponential functions.

What folks mainly wanted to know was: (1) Do smooth demi-exponential functions exist? (answer: yes), (2) Can demi-exponential functions be computed to any desired accuracy? (answer: yes), and (3) Do demi-exponential functions have a tractable closed form, either exact or asymptotic? (answer: no such closed-form expressions are known).

Answer by John Sidles for What should be taught in a 1st course on smooth manifolds?

2011-03-21T16:38:13Z

Update: it may be Spivak's new book Physics for Mathematicians: Mechanics I covers most of the material that this answer had in mind. I've just ordered a copy, and will report on it when it arrives.

Neither Milnor's book nor Guillemin and Pollack's book contains the word "symplectic" ... which is a great pity!

Since the manifolds under study are smooth, they have a cotangent bundle; this bundle is associated to a tautological one-form whose exterior derivative is a (canonical) symplectic form.

If in addition the base manifold has a metric, then a canonical (quadratic) Hamiltonian function too is defined on the tangent bundle.

Hmmm ... what might be the integral curves of this Hamiltonian function? It is instructive for students to discover for themselves that the curves are simply the geodesics of the base manifold.

In this way, students gain an appreciation that all of dynamics (both classical and quantum) is intimately linked to the geometry and topology of smooth manifolds ... this appreciation is good preparation for many careers in math, science, and engineering.

Answer by John Sidles for (Preferably rare) Audio/Video recordings of famous mathematicians?

2011-03-16T00:18:49Z

The voice of John von Neumann dedicating the NORC computer in 1954 (short excerpt and full speech).

The wire recording is a bit murky; here is my best-effort transcript of the short excerpt:

"Those of you present who have lived with this field, and who have lived with and suffered with computing machines of various sorts, and know what kind of regime it is to invest in one, I'm sure have appreciated the fact that it appears that this machine has been completely assembled less than two months ago, has been run on problems less than two weeks ago, and yesterday already ran for four hours without making a mistake. Those of you who have not been exposed to computing machines, and who do not have the desolate feeling which goes with living with their mistakes, will appreciate what it means that a computing machine, after about two weeks of breaking in, has really a faultless run of four hours. It is completely fantastic on an object of this size; I doubt it has ever been achieved before, and it is an enormous reassurance regarding the state of the art and regarding the complexities to which one will be able to go in the future, that this has been achieved."

Here is the BibTeX reference to a printed version (which differs slightly from the speech).

@incollection{vonNeumann:54,
Author = {J. von Neumann},
Booktitle = {John von Neumann Collected Works},
Editor = {A. H. Taub},
Publisher = {Pergamon Press},
Title = {The N.O.R.C.~and Problems in High Speed Computing},
Volume = {5},
Year = 1954,
Pages = 238--247}

Answer by John Sidles for Is there a mathematical axiomatization of time (other than, perhaps, entropy)?

2011-03-10T14:46:03Z

Hmmm ... the question asked intimately blends quantum mechanics and general relativity, in the sense that time (as we experience it in everyday life) is associated to our ability to causally order events.

For example, we readily communicate information forward in time, but not backwards in time, and in particular, we cannot send information faster than speed-of-light. How does this work?

Even more challenging: how can we reduce these physical puzzles to well-posed mathematical problems?

The discussion in Nielsen and Chuang's textbook Quantum Computation and Quantum Information of "The Principles of Deferred and Implicit Measurement" bears directly upon these mysteries ... and in turn, the Nielsen and Chuang discussion derives largely from work by Kraus, Lindblad, and Choi ... and in turn, Kraus, Lindblad, and Choi based their work largely on theorems derived in a dry 1955 article by W. Forrest Stinespring titled "Positive Functions on {$C^\ast$}-Algebras."

So we are lead to ask, how does one explicitly link Stinespring's dry algebraic theorems to the juicy physical mysteries of causality, relativity, and quantum mechanics?

Well, I had occasion earlier this week to post about this link on Scott Aaronson's Shtetl Optimized weblog, and I append that discussion.

The short answer is "A seminal 1955 experiment by Hanbury Brown and Twiss established the connexion" ... and the details are very interesting.

Entire books have been written upon this subject, and so I hope MathOverflow readers don't mind a fairly length answer ... which nonetheless covers only a tiny fraction of this fascinating topic ...

(from a post on Shtetl Optimized)

One wonderful aspect of (of many IMHO) of Scott [Aaronson] and Alex [Arkhipov's] new class of linear optics experiments is the motivation these experiments provide for students to go beyond Feynman's celebrated Lectures on Physics in understanding the physics of photon counting.

[note added: in particular, photon counting as a causal communication channel.]

The quantum physics of photon detection is a subtle topic that even Richard Feynman got wrong on occasion. The story of Feynman's mistake is vividly told in the Physics Today's obituary for Robert Hanbury Brown (volume 55(7), 2002), which tells of Feynman standing up during a talk Hanbury Brown, proclaiming (wrongly) "It can't work!", and walking out of the lecture.

The quantum physics associated to this Feynman story is summarized in series of six short letters, totaling 12 pages in all, that appeared in Nature during 1955-6. These letters describe what is today called the "Hanbury Brown and Twiss Effect"—the first-ever observation of higher-order photon counting correlations.

The story of the Hanbury Brown and Twiss Effect, as recounted on the pages of Nature, in effect has six thrilling episodes:

Episode 1: Hanbury Brown and Twiss announce (in effect) "In the laboratory, we observe nontrivial correlations in photons generated by glowing gases." (Correlation between photons in two coherent beams of light, Nature 177(4497), 1956).
Episode 2: Brannen and Ferguson announce (in effect) "The claims of Hanbury Brown and Twiss, if true, would require major revision of some fundamental concepts of quantum mechanics; moreover when we did a more careful experiment, we saw nothing." (The question of correlation between photons in coherent light rays, Nature 178(4531), 1956).
Episode 3: Not yet having seen Brannen and Ferguson's criticism, Hanbury Brown and Twiss further announce (in effect) "We observe nontrivial correlations even in photons from the star Sirius, and our theory allows us to determine its diameter" (Test of new type of stellar interferometer on Sirius, Nature 178(4541), 1956).
Episode 4: Hanbury Brown and Twiss reply "The experiment of Brannen and Ferguson was grossly lacking in sensitivity; had they analyzed their experiment properly, they would have expected to see no effect" (The question of correlation between photons in coherent light rays, Nature 178(4548), 1956).
Episode 5: In an accompanying letter, Ed Purcell announces (in effect) "Hanbury Brown and Twiss are right, moreover their theoretical predictions and their experiments data are in accord with quantum mechanics as properly understood." (Nature 178(4548), 1956).
Episode 6: Hanbury Brown and Twiss announce (in effect) "When the experimental methods of Brannen and Ferguson are implemented with higher sensitivity, and analyzed with due respect for quantum theory as explained by Purcell, the results wholly confirm our earlier findings." (Correlation between photons, in coherent beams of light, detected by a coincidence counting technique, Nature 180(4581), 1956).

When we read the 12-page story of Hanbury Brown and Twiss side-by-side with the discussion of photon counting in The Feynman Lectures on Physics, we are struck by three aspects of the Hanbury Brown and Twiss experiments that are not emphasized in the Feynman Lectures.

First, the Hanbury Brown and Twiss articles exhibit a charming physicality that is largely absent from the Feynman Lectures. For example, Hanbury Brown and Twiss describe the use of an "integrating motor" to measure the total current associated to photon detection during an experimental run. Modern physics students will wonder "What the heck is an integrating motor?", yet in the physics literature of the 1950s this concept was viewed as being so intuitively obvious as to require no explanation: the total number of revolutions of an electric motor (as counted by purely mechanical means!) obviously can be made proportional to the integral of the current flowing through it ... that's how electric meters work, right?"

As Ed Purcell's letter to Nature rightly observes, the observation of subtle quantum correlations with purely mechanical counters "adds lustre to the notable achievement of Hanbury Brown and Twiss."

Second, the experimental protocol of Hanbury Brown and Twiss includes elements that are highly sophisticated from the viewpoint of modern quantum information theory. In particular, while aligning their apparatus, they reverse the flow of photons by placing their eyes at the position of the source, and while physically looking at two photodetectors through a half-silvered mirror, they adjust the mirrors such that the images of the photodectors are coherently superimposed. We nowadays appreciate that from the viewpoint of QED, this time-reversed coherence is necessary to ensure that quantum fluctuations in the photon detector currents are deterministically associated to quantum fluctuations in the photon source currents.

Third, it follows that in the observations of Sirius recorded by Hanbury Brown and Twiss, their experimental record of correlated photocurrents here on earth is deterministically associated to currents that span the surface of the remote star Sirus -- eight light-years away! This counterintuitive implication was why many theoretical physicists (including Feynman) at first considered the results of Hanbury Brown and Twiss to be (literally) incredible.

Nowadays we appreciate that this seeming paradox is naturally reconciled via the quantum informatic mechanism that Nielsen and Chuang call the "Principles of Deferred and Implicit Measurement" -- principles that are formally associated to work by Kraus and Lindblad in the 1970s; principles that were not readily appreciated by Feynman and his colleagues in the 1950s.

[note added: although Stinespring published his theorems in 1955, it took decades for physicists to appreciate their implications.]

Moreover, the experiments of Hanbury Brown and Twiss were vastly wasteful of photonic resources. The star Sirius emits about $10^{46}$ photons/second, of which Hanbury Brown and Twiss detected about $10^{9}$ two-photon entangled states/second ... the relative production efficiency thus was a dismal $10^{-37}$. Even today, more than 50 years later, the production of six-photon entangled states still is dismally inefficient: in recent experiments $10^{18}$ photons/second of pump power yield about one six-photon state per thousand seconds, for a relative production efficiency of order $10^{-21}$.

We see that one of the fundamental challenges (among many!) that Scott and Alex's experiment poses for 21st century physicists, is to devise methods for generating entangled photon states that are exponentially more efficient than existing methods. To achieve this, modern physicists will have to do exactly what Hanbury Brown and Twiss did ... "look" at the photon detectors from the time-reversed viewpoint of the photon source ... and then (by careful design) arrange for the photon source currents to have near-unity correlation with the photon detector currents.

This is an immense practical challenge in cavity quantum electrodynamics, that we are certain to learn a great deal in trying to solve. At present we are similarly far from having scalable quantum-coherent n-photon sources, as we are far from having scalable quantum-coherent n-gate quantum computers.

These considerations are why, from an engineeering point-of-view, it is prudent to regard n-photon linear optics experiments, not as being obviously easier than building n-gate quantum circuits, but rather as being comparably challenging from a technical point-of-view. And this is why it will not be surprising (to me) if the Aaronson/Arkhipov distribution-sampling algorithms prove in the long run to be similarly seminal mathematically and theoretically—and similarly challenging experimentally—to Peter Shor's number-factoring algorithms.

Summary: A satisfactory understanding of mathematical/physical time is intimately bound-up with our understanding of experiments like that of Hanbury Brown and Twiss ... and even after many decades of work, we still have a long way to go, to achieve this understanding.

In particular, despite more than a century of work, we still lack a mathematical roadmap that naturally accommodates the quantum dynamics of field theory, the informatic causality of Stinespring/Kraus/Choi/Lindblad, and the dynamical state-space geometry of Riemann and Einstein ... see the concluding section of Ashtekar and Schilling's arxiv manuscript Geometrical formulation of quantum mechanics, and also Troy Schilling's thesis Geometry of Quantum Mechanics (Penn State, 1996) for further discussion.

Added comment: Troy Schilling's 1996 thesis Geometry of Quantum Mechanics is well-conceived, and I have often wondered about Schilling's subsequent career. If anyone has information, please post a comment.

Answer by John Sidles for Good papers/books/essays about the thought process behind mathematical research

2011-03-05T17:38:58Z

Not mentioned so far is Bill Thurston's On proof and progress in mathematics (1994). With more than three hundred citations, it surely qualifies as a classic ... it is a permanent left-column link on Terry Tao's weblog, for example.

Thurston's essay is unique, relative to other such essays, in that it describes (in Section 6, "Some Personal Experiences") not one path, but two distinct paths relating to thought processes in mathematical research:

a solitary path associated to Thurston's early work on foliations
a social path associated to Thurston's later work on the Geometrization Conjecture

Thurston's latter approach is the topic of much research today, under various rubrics that include "social media", "social networks", and "roadmapping".

The foresighted points -- by 17 years -- of Thurston's essay include:

social elements of research can be consciously chosen by individuals
fundamental mathematics can provide uniquely strong foundations for social enterprises
healthy mathematical communities make faster progress, and also, a better environment for nurturing the next generation of young mathematicians.

A recent well-respected essay that amounts to a consensus abstraction of Thurston's ideas is the International Roadmap Committee (IRC) More-than-Moore White Paper. For modern-day systems engineers especially, it is very instructive to read-out the main themes of Thurston's 1994 essay from the IRC's 2010 white paper, and thus to appreciate that Thurston's ideas were far ahead of their time.

In particular, the IRC's five consensus preconditions for successful roadmapping are anticipated with near-perfection by Thurston's essay ... and this is why Thurston's essay no doubt will continue to gather new citations through decades to come.

Answer by John Sidles for Discrete Fourier Transform of the Möbius Function

2011-03-05T15:59:00Z

The high level of abstraction that number theorists sustain is a continual source of amazement to me ... doesn't anyone want to see what $\hat\mu(k,n)$ concretely looks like?

So let's do it! Mainly for fun (and as a gesture of respect for Gil), here is a density plot of $n^{1/2} \hat\mu(k,n)$ for all values $(n,k) \in 1,1024$ (note that a normalizing factor $n^{1/2}$ is included; this scaling yields near-uniform luminance in the plot):

As usual, the argument (phase) of $\hat\mu(k,n)$ is encoded as hue, and the magnitude as saturation and value. For details, see the Mathematica code that produced the above plot (for many people, the most interesting aspect of the code will be the idiom for exporting Mathematica graphics to png files; certainly this is by far the longest part of the code, and the toughest to debug).

Such codes code encourages us to do numerical experiments ...

What happens if we randomize the sign of the Möbius function?

Hmmm ... when we randomize the sign of the Möbius function, $\hat\mu(k,n)$ doesn't look much different, does it?

On the other hand, we know (from other numerical experiments) that when we compute a pseudo-Riemann function $\zeta^\prime(s) = (\sum_{r=1}^\infty \mu(r)/r^s)^{-1}$ using a randomized-sign Möbius function, then the resulting $\zeta^\prime(s)$ has a distribution of zeros that is grossly different from the distribution of zeros in $\zeta(s)$ (to see this, just try it).

In summary, the special properties of the distribution of primes (relative to randomized distributions) that are so plainly evident when we "look" at the zeros of $\zeta(s)$, are not immediately evident when we "look" at the magnitude and phase of $\hat\mu(k,n)$.

As for what this observation means (if anything at all) ... well ... that is for the number theorists to comment upon, not me! :)

Answer by John Sidles for What are the most attractive Turing undecidable problems in mathematics?

2011-02-19T00:50:32Z

The following undecidable problem is natural for engineers in the sense that runtime estimation is an ubiquitous engineering problem associated to (for example) control theory and circuit design.

Viola's theorem Given an integer $k$ and Turing machine $M$ promised to be in P, the question "Is the runtime of $M$ of ${O}(n^k)$ with respect to input length $n$ ?" is undecidable.

The proof of this problem's undecidability was given on TCS StackExchange by Emanuele Viola in answer to the question Are runtime bounds in P decidable?

Background

This question arose in parsing Luca Tevisan's answer on TCS StackExchange to the question Do runtimes for P require EXP resources to upper-bound? … are concrete examples known? (answer: yes and yes).

The illumination sought in asking/answering this question was a better appreciation/intuition regarding the practical aspects of runtime estimation in the complexity class P, in the sense of runtime estimates that are feasible (that is, require computational resources in P), versus infeasible (that is, require computational resources in EXP), versus formally undecidable (the instance above).

What this problem's undecidability shows us, perhaps, is that some aspects of P are richer and more subtle than is readily appreciated upon first acquaintance.

Do runtimes for P require EXP resources to upper-bound? ... are concrete examples known? (answer: yes and yes)

2011-02-02T18:50:43Z

Update #6:

Wow, quick service on TCS StackExchange! Emanuele Viola has provided an answer Are runtime bounds in P decidable? Answer: No.

Emanuele's answer illuminates (for me) Luca Trevisan's answer Do runtimes for P require exp resources to upper-bound? Answer: yes.

Thus, I am becoming pretty optimistic of being able to post, pretty soon, a reasonably reliable (partial) summary of the computational complexity of runtime estimation for algorithms in P (it's harder than one might guess).

In the meantime, please see Emanuele's and Luca's answers, which in aggregate I regard as an answer to the question posed (and I have modified the title to reflect this).

Update #5:

I am pleased to report slow-but-steady progress toward a summary answer -- a key remaining question, that has just been asked on TCS StackExchange, is Are runtime bounds in P decidable?

My thanks go to all who have helped/are helping this particular researcher.

Update #4

Rather slowly, an answer is crystallizing both here and in a parallel discussion on TCS StackExchange.

At the present rate of progress there is reason to hope that before the end of February there will be a summary answer that is technically correct, reasonably comprehensive, solidly referenced ... and fun to read too. In the meantime, the short answer is (AFAICT) "yes" and "yes".

If you think that you already know the longer answer ... then please don't wait on me or anyone else, to post it.

Update #3:

To appreciate why it may take awhile for a concluding summary answer to appear, please see Luca Trevisan's comment (below) that begins "By the way, your question, and my answer, do not affect the proof that $BQP^P=BQP$ ..." (and also my response).

Informally, the accepted usages and proof methods of complexity theory sometimes appear to engineers as what Dick Lipton and Ken Regan, on their weblog Gödel's Lost Letter and P-NP, have called "Flaming Arrows".

By "flaming arrow" is meant, a piece of proof machinery that causes the reader to exclaim “Are they allowed to do that?”

By engineering standards, the machinery of complexity theory contains multiple flaming-arrow elements ... in particular, cross-disciplinary discrepancies in the accounting of computational costs associated to verification and validation processes take awhile to grasp.

Thank you all for your patience, and thanks go to Luca Trevisan, especially, for his comments.

Update #2:

Over on TCS StackExchange, I have rated as "accepted" an ingenious construction by Luca Trevisan, which answers a two-part question (as reframed by Tsuyoshi Ito) that is the same as the one asked here, "Do runtimes for P require EXP resources to upper-bound? … are concrete examples known?"

Hopefully I have grasped correctly that, in brief, Luca's construction yields the answers "yes" and "yes for all practical purposes" (FAPP).

It will take awhile (for me anyway) to appreciate whether Luca's $M$-machines obstruct the $P$-time uniform reduction of ${BQP}^{P}\,\to\,{BQP}$ that is at the heart of the original question posed here on on MathOverflow, that question being, "Does BQP^P = BQP? ... and what proof machinery is available?", which in turn generalized a question that was posed by Dick Lipton and Ken Regan on their weblog Gödel's Lost Letter and P=NP, the question "Is Factoring Really In BQP? Really?"

After some further reflection (which may take a few days) I will attempt a summary back-trace of this chain of questions, which so enjoyably unites elements of mathematics, science and practical engineering, and will post that summary both here and on TCS StackExchange.

In the meantime, my thanks and appreciation are extended to everyone ... and further comments are very welcome, of course!

Update #1:

On TCS Stackexchange, Chicago's Joshua Grochow has suggested (provisional) answers that amount to "yes" (EXP resources are required) and "no" (no concrete instance given as yet). There are still several technical issues to be addressed (these issues reflect mainly my slow imperfect understanding), and I will post a summary when the dust settles. My thanks as always go to all who so kindly and generously contribute to these forums.

Do runtimes for algorithms in P require EXP resources to upper-bound? ... are concrete examples known?

The practical motivation for this question arises from a previous MathOverflow question "Does $BQP^P = BQP$? That is, is $P$ low for $BQP$?" (to which Aram Harrow supplied the answer "yes", accompanied by good references). The present question asks about the computational resources that are required to accomplish this reduction.

As before, P is the standard complexity class that is associated to polynomial-time algorithms implemented on (classical) Turing machines, and BQP is the standard (quantum) complexity class Bounded Error Quantum Polynomial Time. We have specifically in mind a logic-gate instantiation of BQP, and for P we have in mind a single-tape Turing machine.

Thus in practical terms, the question concerns the generic computational complexity of converting a Turing algorithm (stipulated to be in P) to a circuit representation.

The number of gates in the circuit provides a prima facie upper bound (hmmmm ... within a coefficient?) for the runtime of P, and for any given input length $n$ this gate-number can always be upper-bounded as the maximum over an exhaustive sample of $2^n$ inputs.

The following questions then are natural. Are there algorithms in P whose runtime estimation provably requires a survey of runtimes for exponentially many inputs? If so, are concrete examples of such hard-to-runtime-estimate algorithms known? Or is the converse true ... every algorithm in P has a runtime that can be upper-bounded by an algorithm that also is in P? If so, what is that runtime estimation algorithm?

These algorithm-to-circuit conversions have considerable practical interest for engineers, and so my appreciation and thanks go to all the mathematicians who contribute to this fine site.

For me, the most enjoyable answer would be a concrete algorithm in P, whose runtime estimate requires more-than-P resources to upper-bound ... it would be fun just to contemplate such an algorithm. Of course, it would be similarly fun, to appreciate that P contains no such algorithms ... and mysteriously fun to discover that such algorithms provably exist in P, and yet no concrete example can be exhibited ... and so I am greatly looking forward to any and all answers.

Once this runtime estimation question is answered, I will incorporate it into a summary answer for the previous question "Does $BQP^P = BQP$? That is, is $P$ low for $BQP$?" ... along with my thanks to all who answer.

Answer by John Sidles for How should one present curl and divergence in an undergraduate multivariable calculus class?

2011-02-16T15:21:58Z

This is a good question and there are already a lot of good answers. Why add one more answer? Because there is a pedagogic option that nicely synthesizes these good questions and answers.

(1) The question recognizes undergraduate students exposed to div, grad, curl, etc. commonly ask questions whose answers are associated to higher-level concepts like one-forms, Hodge duals, etc.

(2) Numerous comments and answers recognize that wading into these advanced topics will slow, confuse, discourage, and distress many undergraduate students. How then to proceed?

(3) A reasonable response is to refer that subset of students (generally a minority) who are willing to work (for no academic credit) toward a broader understanding, to a (free) on-line book by William L. Burke titled Div, Grad, Curl are Dead.

Note: do not confuse Div, Grad, Curl are Dead with the above-recommended book Div, Grad, Curl and All That: the former is modern and polemic, while the latter is traditional and tutorial. Students who like either one generally will not like the other one; it is useful therefore to point students toward both books.

The on-line text of Div, Grad, Curl are Dead is an uncorrected publisher's proof because sadly, Prof. Burke was killed in an accident before the final corrections were done. So the Burke's proof pages have to be read carefully and critically, imperfections and all, this in itself is a good practice for thoughtful students.

Some of Burke's lively prose:

I am going to include some basic facts on linear algebra, multilinear algebra, affine algebra, and multi-affine algebra. Actually I would rather call these linear geometra, etc., but I follow the historical use here. You may have taken a course on linear algebra. This to repair the omissions of such a course, which now is typically only a course on matrix manipulation.

Another example is:

Mathematician: When do you guys [scientists and engineers] treat dual spaces in linear algebra?
Scientist / Engineer: We don't.
Mathematician: What! How can that be?

Burke's lively exposition supplies in abundance what many undergraduates crave: a dramatic narrative about why the geometric aspects of differential calculus are useful and important ... and a dawning realization that undergraduate mathematics is just the preliminary chapter of a wonderful story.

Bill Thurston's Foreword to Mircea Pitici's recent book The Best Writing on Mathematics: 2010 makes this same point, and is recommended to undergraduates who ask "How can two mathematics texts on the same topic be so very different?"

For many undergraduate students, Div, Grad, Curl are Dead will be the wrong textbook. But for those students who ask tough questions and refuse to accept glib answers, it's an excellent textook that gives undergraduate students explicit permission—indeed, seduces them—into reading more deeply.

Answer by John Sidles for What a geometer should know ...

2011-02-13T14:31:25Z

The question asked effectively is "What does one have to know ... to call oneself a geometer?" and as several comments note, that question is tough to answer, nonspecific, and the answers are scary ... and yet the question swiftly picked up two "favorite" votes too.

If the question were rephrased as "What ideas are geometers pursuing?" then the MathOverflow community might be able to supply answers that are more specific, useful, and inspiring to students beginning their research.

Notable mathematicians have written many fine essays on this topic. Commonly these essays are more-or-less centered around a guiding idea that was articulated by Mac Lane in his Mathematics, Form and Function (1986) as follows (and I'm posting this as an "answer" solely to be able to format this quotation properly):

Analysis is full of ingenious changes of coordinates, clever substitutions, and astute manipulations. In some of these cases, one can find a conceptual background. When so, the ideas so revealed help us understand what's what. We submit that this aim of understanding is a vital aspect of mathematics. [...]

Effective or tricky formal manipulations are introduced by Mathematicians who doubtless have a guiding idea---but it is easier to state the manipulations than to formulate the idea in words.

Just as the same idea can be realized in different forms, so can the same formal success be understood by a variety of ideas. A perspicacious exposition of a piece of Mathematics would let the ideas shine through the display of manipulations.

Nowadays the notion of "geometry" has become so broadly generalized, as to be effectively identical to Mac Lane's notion of "a piece of mathematics whose ideas shine through the display of manipulations."

For systems engineers nowadays (me in particular) geometry is largely about the dynamical flow of complex systems ... and of course we want our engineering understanding to "shine through the display of manipulations" .. but it would be a grave mistake to imagine that geometric understanding of dynamical systems is all that geometry is about ... because geometry has evolved to become a much broader notion than that.

Therefore, a reasonable piece of advice to young researchers nowadays—in math, science, engineering, and even medicine, it doesn't much matter which—is not to ask oneself "What articles and books should I read?" without first asking oneself the organizing question "What articles and books will I someday want to write? What will be the core ideas? How will I explain these core ideas clearly?"

As soon as you can write down those ideas in even a hazy and uncertain form, then your research career will have begun ... as you learn, your ideas will slowly take concrete form ... and almost certainly you will be led to the study of geometry in its many modern forms.

Perhaps this is why, 2400 years after Plato's Academy first affirmed it, the members emblem of the American Mathematical Society until recently (and maybe still?) said in greek: "Let none but geometers enter here".

Answer by John Sidles for New proofs to major theorems leading to new insights and results?

2011-02-11T02:58:32Z

The classic example from mathematical physics is Richard Feynman's Space-Time approach to nonrelativistic quantum mechanics (1948), which (in essence) proved that the Green function of the Schroedinger equation was equal to a path integral. The article begins:

It is a curious historical fact that modern quantum mechanics began with two quite different mathematical formulations: the differential equation of Schroedinger, and the matrix algebra of Heisenbert. [...] This paper will describe what is essentially a third formulation of non-relativistic quantum theory.

As for the value of seeking multiple derivations, we have Feynman's Nobel Address The Development of the Space-Time View of Quantum Electrodynamics (1965):

There is always another way to say the same thing that doesn't look at all like the way you said it before. I don't know what the reason for this is. I think it is somehow a representation of the simplicity of nature. [...] Perhaps a thing is simple if you can describe it fully in several different ways without immediately knowing that you are describing the same thing.

In a classical context, we have Saunders Mac Lane in Hamiltonian mechanics and geometry (1970) presenting new geometric analyses of old dynamical problems:

Mathematical ideas do not live fully till they are presented clearly, and we never quite achieve that ultimate clarity. Just as each generation of historians must analyse the past again, so in the exact sciences we must in each period take up the renewed struggle to present as clearly as we can the underlying ideas of mathematics.

In the mid-1970s these various derivations came together as Fadeev and Popov's (1974) Covariant quantization of the gravitational field, which provided the foundations for todays' gold-standard method of BRST quantization, for which van Holten's Aspects of BRST quantization (2002) is a good review:

Quite often the preferred dynamical equations of a physical system are not formulated directly in terms of observable degrees of freedom, but in terms of more primitive quantities [...] Out of these roots has grown an elegant and powerful framework for dealing with quite general classes of constrained systems using ideas borrowed from algebraic geometry.

By this 90-year process of successive rederivations, we nowadays have arrived at a more nearly global appreciation—encompassing both classical and quantum dynamics—of the ideas that Terry Tao's essay What is a Gauge? discusses.

Cutting-edge research in classical, quantum, and (increasingly common) hybrid dynamical systems uses all of these mathematical approaches, each formally equivalent to all the others ... but with very different ideas behind them. The resulting naturality has lent new passion to the longstanding romance between mathematics and physics.

Answer by John Sidles for Dual Riemannian metric and the Dual Metric Form

2011-02-08T21:34:32Z

In some cases, the notion of a Riemann manifold is overly general. If should happen that the problem(s) one has in mind admit a Kählerian complex structure, then the vanishing of the Nijenhuis tensor—which expresses an integrability condition—can provide the "non-messy" global structure that is requested. Associated to the vanishing Nijenhuis tensor is a closed symplectic form that in dynamical models usefully specifies Hamiltonian vector fields.

Does BQP^P = BQP ? ... and what proof machinery is available?

2011-01-27T15:27:53Z

Update #3:

Over on TCS StackExchange, I have rated as "accepted" an ingenious construction by Luca Trevisan, which answers a two-part question (as reframed by Tsuyoshi Ito) that is in essence "Do runtimes for P require EXP resources to upper-bound? … are concrete examples known?"

Hopefully I have grasped correctly that, in brief, Luca's construction yields the answers "yes" and "yes for all practical purposes" (FAPP).

In the meantime, my thanks and appreciation are extended to everyone ... and further comments are very welcome, of course!

Update #2:

I've plowed through a pretty considerable portion of the (excellent) references that Aram provided, and hope to write a summary soon. One topic that I have not found addressed in these references (or it may be that I am too inexpert to perceive it) has been asked as a separate MathOverflow question "Do runtimes for P require EXP resources to upper-bound? … are concrete examples known?".

Update #1:

So far, this topic has a ratio of views-to-answers (presently 285-to-1) that is large relative to other MathOverflow questions ... greater diversity in the answers would be good ... perhaps this draft summary posted on Shtetl Optimized will stimulate more of the "flaming arrow" responses that were hoped-for ... although the references that Aram's answer provides are terrific, needless to say.

Does $BQP^P = BQP$ ? That is, is $P$ low for $BQP$?

Here P is the standard complexity class that is associated to polynomial-time algorithms implemented on (classical) Turing machines, and BQP is the standard (quantum) complexity class Bounded Error Quantum Polynomial Time.

We have specifically in mind a logic-gate instantiation of BQP, that is, a polynomial-time uniform family of quantum circuits (that is, a standard gate-based quantum computer), and for P we have in mind a single-tape Turing machine. So in practical terms, the proposition $BQP^P = BQP$ is about the feasiblity of compiling algorithms in P into polynomially-many reversible logic gates.

This question arose on Dick Lipton and Ken Regan's weblog Gödel's Lost Letter and P=NP as a natural generalization of the question: "Is Shor's algorithm for factoring in BQP?," and it is intimately linked to what Nielsen and Chuang's textbook calls "the Principles of Deferred and Implicit Measurement."

For engineers, proof machinery associated to this question is at least as interesting as the answer itself, because this class of problems arises commonly in engineering practice, in the guise (for example) of compiling a procedural algorithm (written in C and instantiated in a thread, for example) into a circuit diagram (written in Verilog and instantiated on an FPGA, for example). In practice, these algorithm-to-circuit translations are not so easy to solve ... particularly when there is no formal proof that the procedural algorithm is in $P$, but rather, only the empirical (ie, oracular) observation that it so behaves.

One point is that in both practical engineering and in computational complexity theory, procedural algorithms are in general not accompanied by documentation of how they work—perhaps it is infeasible even in principle to document how all the algorithms in the complexity class P work? (an answer to this question too would be very welcome).

Hence the proof machinery for dealing with undocumented (and even undocumentable?) algorithms, both classical and quantum, has both fundamental and practical significance, beyond the significance of the answer to the question asked. This practical/physical context is discussed more fully on Dick and Ken's weblog.

It wasn't so easy to decide whether to post this question of here on MathOverflow versus TCS StackExchange ... in the end, MathOverflow was chosen in hope that the question will attract a mathematically broad range of answers.

Suggestions are especially welcomed, as to how this question might be amended, to make it better-posed and/or more broadly interesting. Thanks! :)

Comment by John Sidles

2012-09-13T20:24:20Z

As a striking example of the increasing prevalence of the notion of naturality in contemporary mathematics, Mochizuki’s four preprints employ the word "natural" and its derivatives on more than six hundred separate occasions (for details and related mathematical quotations, see [this post](rjlipton.wordpress.com/2012/09/12/…) on Gödel's Lost Letter and P=NP).

Comment by John Sidles

2012-08-29T14:05:52Z

LOL ... I upvoted it! Upon the same theme, the (Hungarian) physicist Val Telegdi was fond of the following (Hungarian) maxim: "It is not enough to be rude; one must also be wrong!" :)

Comment by John Sidles

2012-05-29T17:24:57Z

Congratulations on your first accepted answer! :)

Comment by John Sidles

2012-05-17T16:46:35Z

Just as a remark, I am beginning to appreciate that the postulate is (rather obviously) not true. For supposing that M is Kahler, then the volume forms $dV_g$ and $dV_\omega$ are identical. In which case for $B=A$ the definition yields $A\wedge\ast A \ne A\wedge\ast_s A$. I will verify this reasoning against a few concrete cases (like $S^2$), and post it as an answer.

Comment by John Sidles

2012-02-22T11:46:05Z

As a further update, it turns out that the Salmon Prize is offered for progress in this class of conjecture, and the question-asked now links to this prize.

Comment by John Sidles

2012-02-22T11:44:29Z

@Theo and @Todd, on further literature review it turns out that the Salmon Prize is offered for progress in this class of conjecture, and the question now links to this prize.

Comment by John Sidles

2012-02-14T11:51:12Z

As an update, a key reference regarding quantum dynamics on projective varieties turns out to be Hirotachi Abo; Giorgio Ottaviani; Chris Peterson, "Induction for secant varieties of Segre varieties", Transactions of the AMS (2008). Combining the proof technologies of Abo et al. with numerical experiments via our quantum systems engineering software yields a plausible conjecture for a complete classification of "lion" varieties, and this conjectured varietal classification will be the subject of an MOL question in the next couple of weeks.

Comment by John Sidles

2012-02-14T01:45:10Z

@Qiaochu, in agreement with your point, the unique virtue of MOF surely is its exclusive focus upon well-posed math questions. And yet in agreement too with Gil Kalai, many folks (but not all) appreciate physical/practical motivations. And finally (in my own opinion) it is neither necessary, nor feasible, nor even desirable that everyone think & post alike in these matters. So to strike a three-way balance, my next post will be a double-distilled pure-math question, whose physical/practical motivations are described separately, below a bar (where folks can ignore them or not, as preferred).

Comment by John Sidles

2012-02-14T00:43:12Z

@Gil Kalai and @Marcin Kotowski, you are both entirely correct. The question asked arose when our UW QSE Group noticed certain numerical "miracles" in our quantum spin simulation software. In this regard, please let me commend in Joseph Landsberg's book Tensors: Geometry and Applications his short essay of Section 0.3, titled "Clash of Cultures" (books.google.com/…). Thus, next week I hope to post a focused question to help reconcile these cultures, in accord with Hestenes' saying: "Geometry without algebra is dumb, algebra without geometry is blind."

Comment by John Sidles

2012-02-13T14:57:12Z

@Qiaochu your suggestion is sound, and in response the question now is shortened, focused, and now begins with a suggested answer than draws upon Joseph Landsberg's very recent (and dauntingly comprehensive) monograph Tensors: Geometry and Applications (December 2011). It turns out too that certain key results are accessibly surveyed in Landsberg's Bull. AMS article "Geometry and the complexity of matrix multiplication" (2008). These essentially are the references sought, and so I thank you and everyone here on MOF for comments and suggestions that have helped in finding them.

Comment by John Sidles

2012-02-12T23:11:44Z

@Theo and @Todd (and others), the amended question has now been posted, and in particular it quotes a passage from Harris' textbook that addresses the "odd circumstance" that questions regarding bilinear algebraic varieties commonly can be answered by elementary methods, yet the analogous questions for generic multilinear varieties are deep. The amended question seeks to clarify that the state-spaces of practical concern to quantum systems engineers nowadays, and hence the mathematical tools of greatest interest, are associated to generic multilinear varieties. Thank you all very much! :)

Comment by John Sidles

2012-02-12T18:42:49Z

Please let me say that I consider the various comments on my question to have been (all of them) very valuable, and so later today (Sunday) I will post an amended version that attempts to address these comments all-at-once. Especially I appreciate and am grateful for Theo Johnson-Freyd's comments---as pertaining both narrowly to notation and broadly to mathematical context---and it has been exceedingly enjoyable to watch this question help Theo (albeit inadvertently) earn MOF's first Gold Reversal Medal. So thank you all very much!

Comment by John Sidles

2012-02-12T17:51:07Z

@Theo and @Todd (and others), thank you for your considerate remarks! Per Theo's request, I will clarify the question's notation and characterize more precisely the type of reference that is desired. My access to Harris' text via Google Books is (frustratingly!) partial, yet for quantum systems engineers (QSEs) the intent is captured by Harris' passage (page 100) "We should draw a fundamental and important distinction between bi- and tri- or multilinear objects." In practice, QSEs require a mathematical toolset that extends naturally to the multilinear algebraic objects of Harris' remark.

Comment by John Sidles

2012-02-11T20:37:01Z

Michael, your $\Rightarrow$ argument is entirely correct, and the $\Leftarrow$ implication is no harder ... e.g., the SVD of a zero-determinant $\psi$ must have at least one zero principal value, such that the SVD constructs a (non-unique) solution set of $k-1$ pairs $\{\xi_{1r},\xi_{2r}\}$ ... but such constructions are not the answer to the question asked (which was a request for references) and neither do they correspond to the answer that Theo supplied (to be sure, Theo's answer was well-reasoned, but it did not address the question asked).

Comment by John Sidles

2012-02-11T14:09:09Z

@Theo, I have added a technical caveat regarding linearity to the question, in the hope that you might augment your answer to address it... in which event it would be my pleasure to upvote your suggested answer. Thank you!