soft question - Quantum Computing Complexity?

First, Alon's summary of applications of quantum computing is not complete. What Shor's algorithm (or more precisely, Simon-Shor-Kitaev) really does is that it fully analyzes any finite abelian group in polynomial time (polynomial in log |G|), provided that inverses and the group law are available in black-box form, and elements have unique names. Thus, you can factor N by analyzing the multiplicative group of Z/N. You can analyze elliptic curves, other abelian varieties, D-modules, etc. You can find the cardinality, find orders of elements, compute discrete logarithms, etc.

There are other quantum algorithms that do black-box things that certainly look like they could be useful. What makes Shor's algorithm special is that there are lots of obvious ways to replace the black box by a "white box", i.e., by an explicit computational problem.

These algorithms provide strong evidence that the quantum polynomial time class, BQP, is larger than P, polynomial time (and BPP, randomized polynomial time).

And that is the original question about the strong Church-Turing thesis. The strong Church-Turing thesis posits that all natural models of polynomial-time computation are equivalent. At the moment, it looks like there are two natural models, P (which is conjectured to equal BPP) and BQP. As Alon says, factoring is not known to be NP-complete, but there is nothing unfortunate about that. It would surprise a lot of people if NP turned out to be a natural class, and it is a standard conjecture that BQP does not contain NP.

nt.number theory - weight 4 eigenforms with rational coefficients---is it reasonable to expect they all come from Calabi-Yaus?

I am not that sure that your question can be answered positively, but the following is merely speculation, so you should not pin me down on it. The basic idea is that there might be "more" weight 4 forms than rigid CY 3-folds.

It seems that (but Kevin probably knows this better than me) that it is still an open question whether there are finitely or infinitely many weight 4 eigenforms up to twisting.

Suppose there were infinitely many weight 4 eigenforms up to twisting. To realize every weight 4 eigenform we then need infinitely many $overline{mathbb{Q}}$-isomorphism classes of rigid CY 3-folds defined over $mathbb{Q}$. All hodge numbers of a rigid CY 3-fold are a priori fixed, except for $h^{1,1}$ and $h^{2,2}$, which coincide. The Euler characteristic of a rigid CY 3-fold is $2h^{1,1}$ and rigid CY 3-folds do not admit deformation, hence in order to realize every weight 4-form we either find a Hodge diamond $D$ such that

{ $X | X$ smooth projective complex variety with Hodge diamand $D$}/deformations

is infinite, or the absolute value of the Euler characteristic of a CY 3-folds can be arbitrarily large. The first conclusion would be quite remarkable, the second would solve an open problem (as far as I know).

Suppose now there were only finitely many weight 4 eigenforms up to twisting.
If you want to avoid the above mentioned problems you need that every eigenform $f$ is realized by a CY 3-fold $Y_f$ admitting an involution, so that a twist of $f$ is realized by a twist of $Y_f$.

Still it is not clear whether there are enough rigid CYs to realize every eigenform. Some computational evidence can be found in the book of Christian Meyer, Modular Calabi-Yau Threefolds. He realizes close to 100 eigenforms (up to twisting). The corresponding list at http://www.fields.utoronto.ca/publications/supplements/weight4.pdf
contains much more forms. The smallest level that he could not realize is 7.

If you allow $h^{2,1}$ to be nonzero, i.e., you allow the motive of the form to be a factor of $H^3$ or if you are happy to work with quasi-projective varieties $Y$ such that its completions is a CY 3-fold then you are in a much better position.

reshetikhin turaev - How do quantum knot invariants change when I pick a funny ribbon element?

Ben,

As I mentioned in response to your previous question about ribbon elements, the element u which is defined from the R-matrix, u=mucirc(Sot id)(R21) has the property that uS(u)=v^2 (well this is not the formula I gave for u in that post, because the one I gave was incorrect; this one appears to be correct according to wikipedia).

This relation v^2=uS(u) is true in any ribbon Hopf algebra, and in particular it implies that v has to be a square root of uS(u). So I think this means that the ribbon element is almost unique.

More precisely, let v and w be two ribbon elements. Then v/w is a grouplike element of order two. I think this implies that the corresponding invariant applied to a link will be multiplied by the constant v/w applied to each link. Now if you choose irreducible representations to label your link, then this number would have to be +/- 1.

Does this seem correct?
-david

ag.algebraic geometry - The fibers of M_{g,n} to M_g and the Fulton-MacPherson compactification

You don't mean that the forgetful map contracts any rational component, only those touching less than three nodes. Also, the n-fold fibered power is not singular where several markings coincide at a smooth point. After all, a fibered product of smooth morphisms is smooth. It will, however, disagree with $overline{M}_{g,n}$ at the locus where three or more markings coincide, so blow-ups will indeed be required.

However, what you wish for in the last paragraph is indeed true. One has to assume that the automorphism group of $C$ is trivial, for otherwise, even the fiber of $overline{M}_{g,1}$ over $overline{M}_g$ will be not $C$ but $C/ Aut C$. (Working with moduli stacks rather than moduli spaces would cure this problem.) But assuming this, the fiber of $overline{M}_{g,n} to overline{M}_g$ is indeed the Fulton-MacPherson configuration space. Indeed, that space is described in the original F-Mac paper as a moduli space of stable configurations of distinct smooth points on a fixed curve $C$ with nodal trees of projective lines attached, modulo projective equivalence on the lines. Here "stable" means that the pointed nodal curve has finite automorphism group, that is, each line carries at least three distinguished points. Those are exactly the configurations that you see in your fiber.

As for your earlier question, it is true in some sense, but it would be quite subtle in practice. Fulton-MacPherson explain how to obtain their space from the product $C^n$ by an explicit sequence of blow-ups. One blows up first the "small diagonal" where all the points come together, and then proper transforms of other diagonals. You could try to blow up all the corresponding loci in the fibered power of $overline{M}_{g,n}$ over $overline{M}_g$.

But you would have to resolve other loci over the boundary too: if two markings coincide with a node, for example, you want to pull apart the node, glue in an extra line, and draw the two markings on that line. But since there is a 1-parameter family of ways to do this (due to the cross-ratio of the two nodes and the two markings), you want to replace the corresponding points in the fibered power with a $P^1$. Even worse, this would not be a blow-up in the obvious sense. The fibered product of two nodes, in local analytic coordinates, looks like $xy = t = wz$, that is, $xy-wz=0$, the cone on a smooth quadric surface. You can resolve this singularity by blowing up the origin, but then the exceptional divisor is $P^1 times P^1$, not $P^1$ as you wish. Instead, you should perform one of the "small resolutions" obtained by blowing up one of the Weil divisors $x=w=0$ or $x=z=0$.

Since any birational morphism is the blow-up at some sheaf of ideals, in some abstract sense you are guaranteed that $overline{M}_{g,n}$ is obtained from the fibered power by blowing up. But that doesn't mean that you can give an explicit list of smooth centers to be blown up in turn. The example with the two markings at the node suggests that this will be a thorny problem.

ac.commutative algebra - Two questions about Cohen-Macaulay rings

Nice questions! The answers are no in both cases, although the examples are more interesting than one would expect.

1) Even when $A$ is regular, one can always find an ideal $I$ with $3$ generators such that $A/I$ has depth $0$. This is due to a very nice result by Bruns, which says you can construct $3$-generated ideal with all kinds of homological patern. The details are explained in this answer.

2) Let $R=k[X^4,X^3Y,XY^3,Y^4]$. Then $R$ is a domain of dimension $2$ which is not Cohen-Macaulay. So one can write $R=S/Q$, where $R=k[a,b,c,d]$ and $Q$ is a prime ideal of height 2. Take $(f,g)$ to be a regular sequence in $Q$ and let $I=(f,g)$. Then $A=S/I$ is Cohen-Macaulay (being a complete intersection), but $Q$ is a minimal prime of $A$ and $R=S/Q$ is not CM.

ag.algebraic geometry - Sections of etale morphisms

We all know that smooth morphisms have sections etale locally. However, the following similar statement is not obvious for me:

If X->Y->Z, X is etale over Y, Y is finite and surjective over Z, then a section of X->Y exists etale locally on Z, i.e. there exists an etale cover U of Z such that X_U->Y_U has a section. Where _U means pullback on U.

I think it is supposed to be easy.

Can anyone explain this to me? Thanks.

dg.differential geometry - chern connection vs levi-civita connection

Hi!
I've always read that on a complex manifold (obviously not kahler), with a given
hermitian metric on tangent bundle, the chern connection and the levi civita connection
on the underlying real bundle could be different.
Please can someone give me an explicit example of this fact?

Thank you in advance

at.algebraic topology - Subgroups of free abelian groups are free: a topological proof?

The "free group" proof rests on proving that that the fundamental group of a graph is free. For the analogue we'd need to essentially prove that the fundamental group of a "torus" (something that looks like a quotient of a vector space by a discrete subgroup) is free abelian. A sketch:

Given a real vector space V, we can put the direct limit topology on it (so that subsets are closed if and only if their intersection with any finite dimensional subspace is closed). This is a contractible topological group.

If A is a free abelian group, then A is a discrete subgroup of the associated real vector space (ℝ ⊗ A) and the quotient space has fundamental group A. Any covering space is a quotient of (ℝ ⊗ A) by a discrete subgroup B of A.

So the question boils down to showing: Any discrete subgroup of a vector space (with the direct limit topology) is free abelian.

Let's say that a partial basis is a set S of elements of B such that

• S is linearly independent, and
• S generates B ∩ Span(S).

Then partial bases are a partial order under containment, and Zorn's lemma implies that there is a maximal element S. I claim that S is a basis of B as a free abelian group.

S is linearly independent by construction, so it generates a free abelian group, and hence it suffices to show that it generates all of B. If b in B is not in S, then it is not in Span(S). Let S' be (S ∪ {b}). Then Span(S')/Span(S) is a 1-dimensional vector space and the image of B ∩ Span(S') must be discrete, because otherwise Span(S') would contain an element (rb + v) for v in Span(S) that we could use to generate a non-discrete subset of B. (If v is a combination of w₁...w_n in S, then it suffices to check that any subgroup of the finite-dimensional space Span(w₁...w_n,b) requiring more than n generators is indiscrete.)

Thus any lift of a generator of B ∩ Span(S') would extend to a larger generating set, contradicting maximality.

(My apologies for the comment last night, which this morning looks snarkier than I intended. I'm a fan of using this topological reasoning for free groups myself, because it compartmentalizes the proof into much more understandable pieces. In particular, I don't think I'd really understand a purely algebraic proof that an index n subgroup of a free group on m generators is free on nm - n + 1 generators.)

rt.representation theory - Matrix representation for $F_4$

Here I quote some GAP code for generating F4 Lie algebra as matrices 27 x 27. It is possible to obtain them in dimension 26 but then you need to use Sqrt(2) or Sqrt(3). In dimension 27 it is more nice.

Matrices L1..L7 are 8x8 matrices of left multiplication by imaginary unit octonions e1..e7. R1..R7 are right multiplications by unit octonions. If you have troubles to obtain such please let me know.

I have also obtained Lie algebra of E6 as complex matrices 27x27 and Lie algebra E7 as quaternion matrices 28x28. I tried to obtain some nice way E8 Lie algebra in shape 31*8 dim matrices but no luck. It was in 2008 when I worked on these scripts. I have used Freudenthal, Tits, Vinberg papers when doing this.

Regards,
Marek

---

v18 := BlockMatrix([[1,1,-R1], [2,2,-L1], [3,3,L1+R1]], 4,4);
v28 := BlockMatrix([[1,1,-R2], [2,2,-L2], [3,3,L2+R2]], 4,4);
v38 := BlockMatrix([[1,1,-R3], [2,2,-L3], [3,3,L3+R3]], 4,4);
v48 := BlockMatrix([[1,1,-R4], [2,2,-L4], [3,3,L4+R4]], 4,4);
v58 := BlockMatrix([[1,1,-R5], [2,2,-L5], [3,3,L5+R5]], 4,4);
v68 := BlockMatrix([[1,1,-R6], [2,2,-L6], [3,3,L6+R6]], 4,4);
v78 := BlockMatrix([[1,1,-R7], [2,2,-L7], [3,3,L7+R7]], 4,4);

S:= DiagonalMat([1,-1,-1,-1,-1,-1,-1,-1]);

Build now elliptic version of F4. The name is from that exp(t*[[0,-1], [2,0]]) is ellipse.
Really exp(t*[[0,-1], [2,0]]/Sqrt(2)) is ellipse.

p1 := [[0, -1, 1]];
p2 := [[-1, 1, 0]];

n := NullMat(8,8);
v:= n+p1;
vt := -2*TransposedMat(v);

This a0 really corresponds to ad([[0,-1,0],[1,0,0],[0,0,0]]) derivation on h3O.
a0 := BlockMatrix([[1,2,S], [2,1,-S], [3,4, v], [4,3, vt]], 4,4);

w := n+p2;
wt := -2*TransposedMat(w);

b0 := BlockMatrix([[2,3,S], [3,2,-S], [1,4, w], [4,1, wt]], 4,4);
mats3 := [ v18, v28, v38, v48, v58,v68,v78, a0, b0];;
ms:=List(mats3, x->x{[1..27]}{[1..27]});
f4_e := LieAlgebra( Rationals, ms);

2016-05-24 I add following matrices more nice for human eye, when I learned how to entered them in MathJax.
There are seven matrices generating $so_8$ (triality on Lie algebra).
$$v_{k,8}=pmatrix{ -R & & & & &
\ & -L & & & &
\ & & L+R & & &
\ & & & 0 & &
\ & & & & 0 &
\ & & & & & 0 } $$
In this notation $L$ and $R$ are matrices of left and right multiplication by imaginary base octonions.
We add two more matrices to obtain $f_4$ Lie algebra. We should understand that vectors 1x8 or 8x1 have element on first position (position of 1 in octonions). Matrix S represent octonions conjugation.
$$a_{0}=pmatrix{ & S & & & &
\ -S & & & & &
\ & & 0 & & -1 & 1
\ & & & 0 & &
\ & & 2 & & 0 &
\ & & -2 & & & 0 } $$

$$b_{0}=pmatrix{ 0 & & & -1 & 1 &
\ & & S & & &
\ & -S & & & &
\ 2 & & & 0 & &
\ -2 & & & & 0 &
\ & & & & & 0 } $$

ag.algebraic geometry - What are the fibres of a representable simplicial sheaf (in the Nisnevich topology)

Let $N:=textrm{Neigh}_{Nis}(U,nu)$ denote the filtered category of Nisnevich neighborhoods of the point $nuin U$. Then $textrm{colim}_{Vin N^{op}} Vcong textrm{spec}(mathcal{O}^{h}_{U,nu})$, where $N^{op}$ denotes the opposite category of $N$ and $mathcal{O}^{h}_{U,nu}$ is the henselization of the local ring $mathcal{O}_{U,nu}$.
My guess now would be that the fiber is the constant simplicial set associated to the set $textrm{Hom}_{k}(textrm{spec}(mathcal{O}^{h}_{U,nu}),X)$.

Maybe someone can clarify this as well as your second question.

ca.analysis and odes - Constructive aspects of Caratheodory's theorem in convex analysis

Let me paraphrase Caratheodory's theorem in a probabilistic setup:

Let $X$ be a real-valued random variable. For $k = 1, ldots, m$, let $f_k: mathbb{R} to mathbb{R}$ be a continuous function such that $mathbb{E}[f_k(X)]$ is finite. There exist a discrete real-valued random variable $Z$ with at most $m+1$ atoms, such that:

(1) $mathbb{E}[f_k(X)] = mathbb{E}[f_k(Z)]$ for $k = 1, ldots m$.

This is a simple consequence of Caratheodory's theorem in convex analysis, because the point $P = (mathbb{E}[f_1(X)], ldots, mathbb{E}[f_m(X)])$ belongs to the convex hull of the set $E = {(f_1(x), ldots, f_m(x)): x in mathbb{R} } subset mathbb{R}^m$. Therefore $P$ can be written as a convex combination of at most $m+1$ points in $E$.

The above is an existence result. Here are my questions:

1) Given the density of $X$ and $f_1, ldots, f_m$, is there an efficient algorithm to compute the location and weights of $Z$? I know how to do this when polynomials are concerned, i.e., $f_k(x) = x^k$. As elucidated by fedja in reply to a question I asked before, this problem is solved by the Gaussian quadrature, and the locations are given by roots of orthogonal polynomials. The problem I am facing is for standard normal $X$ and $f_k(x) = exp(-x^2) x^k$. I do not have a clue how to solve this highly nonlinear problem.

2) Let us take a closer look at the special case when $f$'s are monomials. In this case what Gaussian quadrature achieves is twice better than Caratheodory's theorem, namely, $(m+1)/2$ atoms are enough to satisfy (1). This number is optimal intuitively, because we have $m+1$ equations to solve: $m$ equations in (1) and weights sum up to one. Hence we need at least $m+1$ "degrees of freedoms", half being locations and half being weights. (My friend told me this can be made precise by algebraic geometry, though I do not understand). I wonder what is so special about polynomials in this problem. I do not suppose Caratheodory's theorem can be improved by a factor of two. For non-polynomial functions, like those in my first question, is $m+1$ really necessary?

st.statistics - What is the difference between the Power Law and Zipf's Law?

Zipf's law is a special case of power laws, with power -1. (The harmonic series diverges, so the distribution in Zipf's law is truncated at some point. But the essential character is the point: the probabilities decline like a power of the argument.)

gt.geometric topology - Topological results from geometry

A nice topic to read about is Chern-Weil theory. This is the generalisation of Gauss-Bonnet to higher dimensions and to vector bundles other than the tangent bundle. Put very briefly, topological invariants of a vector bundle over a manifold (its characteristic classes - certain classes in the cohomology of the base) can be computed using the curvature tensor of any choice of connection in the bundle.

The prototype is Gauss-Bonnet in which, as you know, the Euler characteristic of a (compact orientable) surface is equal to a fixed constant times the integral of the scalar curvature of any Riemannian metric on the surface.

at.algebraic topology - Survey articles on homotopy groups of spheres

While my Algebraic Topology book and my unfinished book on spectral sequences (referred to in other answers to this question) contain some information about homotopy groups of spheres, they don't really qualify as a general survey or introduction. One source that fits this bill more closely is Chapter 1 of Doug Ravenel's "green book" Complex Cobordism and Stable Homotopy Groups of Spheres, from 1986. This introductory chapter starts at a reasonably accessible level, with increasing prerequisites in the later sections of the chapter. More recent surveys ought to exist, although at the moment I can't recall any. With the recent solution of the Kervaire invariant problem by Hill-Hopkins-Ravenel, this would be a good time for an updated survey.

Connections between homotopy groups of spheres and low-dimensional geometry and topology have traditionally been somewhat limited, with the Hopf bundle being the thing that comes most immediately to mind. A fairly recent connection is Soren Galatius' theorem that the homology groups of $Aut(F_n)$, the automorphism group of a free group, are isomorphic in a stable range of dimensions to the homology groups of "loop-infinity S-infinity", the space whose homotopy groups are the stable homotopy groups of spheres.

ct.category theory - What does the classifying space of a category classify?

Ieke Moerdijk has written a small Springer Lecture Notes tome addressing this question:"Classifying Spaces and Classifying Topoi" SLNM 1616.

Roughly the answer is: A $G$-bundle is a map whose fibers have a $G$-action, i.e. are $G$-sets (if they are discrete), i.e. they are functors from $G$ seen as a category to $mathsf{Sets}$. Likewise a $mathcal C$-bundle for a category $mathcal C$ is a map whose fibers are functors from $mathcal C$ to $mathsf{Sets}$, or, if you want, a disjoint union of sets (one for each object of $mathcal C$) and an action by the morphisms of $mathcal C$ — a morphism $A to B$ in $mathcal C$ takes elements of the set corresponding to $A$ to elements of the set corresponding to $B$.

There is a completely analogous version for topological categories also.

algebraic number theory - Relative integral basis for CM extensions

Suppose $K=mathbf{Q}(sqrt{d})$; it's well known that $mathcal{O}_K$ is $mathbf{Z}+frac{D+sqrt{D}}{2}mathbf{Z}$, where $D$ is the discriminant.

What is the analogue of this for a CM extension $F(sqrt{-alpha})/F$, where $F$ is totally real (of class number one) and $alpha in mathcal{O}_F$ is totally positive?

Is there a canonical element $xi$ of $F(sqrt{-alpha})$ such that $mathcal{O}_{F(sqrt{-alpha})}=mathcal{O}_F+xi mathcal{O}_F$?

I have looked in the literature, but all I can find are various theorems guaranteeing the nonexistence of relative integral bases in various situations. However a theorem in Chapter 7 of Narkiewicz's book guarantees that some $xi$ does exist in the above situation.

ag.algebraic geometry - The existence of primitive and sufficiently ample line bundles on K3 surfaces?

In Beauville's "Counting rational curves on K3 surfaces" is implictly
assumed the existence of algebraic K3 surfaces with Pic of rank one and generated
by a curve of genus g.

How do we show the existence of such K3 surfaces ?
Edit: See Ferreti's first comment below for an answer.

---

Using the argument pointed out by Ferreti in his first comment and taking care to
avoid the difficulty pointed out in his second comments, we can
reduce the existence of the sought K3 surfaces to the following statement:

There exists infinitely many integers
k for which (2k)(2k +3) is
squarefree.

Start with a smooth quartic S in P(3) and let H be a hyperplane section.
For a fixed r and k>>0, the restriction of kH to S is r-very ample.

Suppose S contains a line L. Then the linear system |E|=|H-L|
defines a fibration by elliptic curves on S.
Thus kH + E is also r-very ample.

Let SS be a family of K3 surfaces
that deforms S in such a way that the class of O(k) is preserved,
and for a generic member of the family every element in H1,1cap
H^2(Z) not proportional to O(k) becomes non-rational. Thus the
generic element has Pic = Z. Since r-very ampleness is an open condition
( the points in the relative Hilb^r(SS) where it does not hold is closed)
we obtain a K3 surface with Pic = Z and a r-very ample line-bundle of
self-intersection 4k^2 + 6k = 2k(2k +3). If this number is squarefree then
the line bundle is primitive.

---

After googling a bit I found general results about squarefree values of polynomials which seems to ensure the existence of infinitely many integers k for which 2k(2k +3) is squarefree.

---

Edit: I would like to know
if it is necessary to impose the number theoretical condition to obtain primitiviness.

ag.algebraic geometry - How to prove that a projective variety is a finite CW complex?

The Lojasiewicz theorem says that every semi-algebraic subset of $mathbf{R}^n$ can be triangulated. Moreover, there is a similar statement for pairs of the form (a semi-algebraic set, a closed subset). See e.g. Hironaka, Triangulations of algebraic sets, Arcata proceedings 1974 and references therein (including the original paper by Lojasiewicz).

The case of an arbitrary (not necessarily quasi-projective) complex algebraic variety follows from Nagata's theorem (every variety can be completed) and Chow's lemma (every complete variety can be blown up to a projective one).