ds.dynamical systems - Linearization at equilibrium points

As Victor says:

I am confident that the system

$$x' = -y + ( x^2 + y^2) x,$$
$$y' = x + ( x^2 + y^2) y$$
has the origin repelling nearby trajectories, while
$$x' = -y - ( x^2 + y^2) x,$$
$$y' = x - ( x^2 + y^2) y$$
has the origin attracting nearby trajectories, and
$$x' = -y$$
$$y' = x$$
has just periodic orbits near the origin. But all three
linearize to the same thing at the origin,
$$left( begin{array}{rr} 0 & -1 \ 1 & 0 end{array} right) .$$
with eigenvalues $pm i.$

EDIT: Indeed, given a constant real number $lambda$ and system

$$x' = -y + lambda ( x^2 + y^2) x,$$
$$y' = x + lambda ( x^2 + y^2) y ,$$
we find that
$$frac{d}{dt} ; (x^2 + y^2) = 4 lambda (x^2 + y^2)^2.$$

EDIT some more: so, for the nonconstant paths, if we set time to $0$ when the trajectory crosses the unit circle, we get

$$x^2 + y^2 = frac{1}{1 - 4 lambda t}$$
showing that when $lambda > 0$ the path reaches infinite radius in finite time, while with
$lambda < 0$ the path spirals in to the origin, as expected.
Then, if we set $$x = r cos theta, ; y = r sin theta$$
as usual, the rate of change of $theta$ does not depend on $lambda$ and $forall lambda,t$ we have
$$frac{d theta}{d t} = 1.$$

nt.number theory - Terminology occuring in automorphic representation and relationship between them

‘Square-integrable’ and ‘cuspidal’ are definitely not equivalent; the former latter representations are among the latter former, but do not exhaust them. To the best of my knowledge, ‘supercuspidal’ and ‘cuspidal’ are just the same concept with different etymologies behind them; and ‘absolutely cuspidal’ is meant to refer to representations that remain cuspidal upon extension of the ground field, hence is only interesting for representations in non-algebraically-closed fields. (For $p$-adic groups, the terminology ‘supercuspidal’ is used almost exclusively. I think one sees ‘cuspidal’ more in the global- or finite-field setting.)

I find it amusing that ‘very cuspidal’ (as used by Carayol, for example) is more restrictive than ‘supercuspidal’!

In the automorphic-forms settings, discrete-series representations are those that appear as direct summands of $L^2$ of our symmetric space. In this sense, they should be viewed as subrepresentations of the part of $L^2$ that decomposes ‘discretely’, as a direct sum, rather than continuously, as a direct integral. (In a measure-theoretic sense, the discrete series contains the atoms for the Plancherel measure. I think, but wouldn't swear to it, that Plancherel measure is absolutely continuous on the remainder of the tempered spectrum.) The cuspidal representations are those that appear in the space of $L^2$ functions that die off rapidly—in other words, that vanish at the cusps of a suitable compactification of the symmetric space. It is a theorem that they automatically appear as direct summands.

at.algebraic topology - Loop Spaces as Generalized Smooth spaces or as Infinite dimensional Manifolds?

There are two ways to define smooth mapping spaces and I want to know how they compare.

Let's take the concrete special case of free loops spaces. I think this is the most studied example so will probably have the best chance of an answer. Roughly the free loop space is a space which is supposed to be the space of maps from the circle to a given space X. It is usually denoted LX. This is all fine and good for topological spaces. You get a nice mapping space LX by equipping the set of maps with the compactly generated compact open topology. It even satisfies the adjunction:

$Map(Y, LX) = Map( Y times S^1, X)$

However things get complicated when we want to work with manifolds. The first thing is that we want something that represents smooth maps from the circle into the manifold X.

There are basically two approaches to making such an object precise, and I want to know how they compare.

The first approach actually tries to construct an actual space of smooth maps. Here you start with the set of smooth maps LX, and with analytical muscle you give it the structure of an infinite dimensional Fréchet manifold. When X = G is a Lie group, this is an inifinite dimensional Lie group and is the thing whose (projective) representations make an appearence in conformal field theory.

The second approach is to study the loop space as a generalized smooth space. What is a generalized smooth space, you ask? Well there was a lot of discussion about it at the N-category Cafe, here and here. Roughly LX is thought of as a kind of sheaf via the formula:

$LX(Y) = Maps(Y, LX) = Maps(Y times S^1, X)$

In some models it must be a concrete sheaf (i.e. it has a underlying set of points and every map from it to anything else which is concrete is a particular set map. The technical details appear in the Baez-Hoffnung paper in the second link). Clearly this model has its own desirable properties.

How does the manifold version of loop space compare to the sheaf theoretic version?

Presumably the Fréchet manifold model gives a sheaf (since we can just map into it). Does this agree with the sheaf defined by the adjunction formula? If they are not the same sheaf, they do seem to have the same points, right? And I think there is a comparison map from the manifold LX to the sheaf LX, which should be helpful. Can anyone explain their relationship? How similar/different are they?

ag.algebraic geometry - Why is one interested in the mod p reduction of modular curves and Shimura varieties?

Kevin's answer gives a very good explanation of the role of mod $p$ reduction in the theory of Galois representations and automorphic forms. In this answer I will try to say something a little more technical about one way in which understanding the mod $p$ reduction of modular curves can be applied in arithmetic. The precise application that I will discuss is that of constructing congruences of modular forms.

If $f$ is a Hecke eigenform (of weight 2, to fix ideas), then associated to $f$ is a Galois representation $rho_f:G_{mathbb Q} to GL_2(overline{mathbb Q}_{ell})$ (for any prime $ell$). Say the level
of $f$ is equal to $N p$, where $p$ is a prime not dividing $N$. One can ask: is there an eigenform $g$ of level $N$ such that $f equiv g bmod ell$. (Here congruence means congruence
in $q$-expansions.) This is the question that Ribet solved in his famous Inventiones 100 paper (the paper which reduced FLT to Shimura--Taniyama).

Note that since $p$ is not in the level of $g$, the representation $rho_g$ will be
unramified locally at $p$. (This comes from knowing that the modular curve of level $N$
has good reduction at $p$, since $p$ does not divide $N$ --- a first application of the theory of reduction of modular curves.) (If $p = ell$ one must be more careful here,
but I will suppress this point.)

Thus if $f equiv g bmod ell,$ so that $rho_f$ and $rho_g$ coincide mod $ell$,
we see that $rho_f$, when reduced mod $ell$, must be unramified at $p$. So this
is a necessary condition for the existence of $g$.

It turns out (and Ribet proved) that (under some additional technical hypotheses) this
necessary condition is also sufficient. The way the argument goes is the following:
the modular curve of level $N p$ has semi-stable singular reduction: it is two smooth
curves (coming from level $N$) crossing each other a bunch of times (this is the contribution from the $p$-part of the level). Now the mod $ell$ Galois representation
$overline{rho}_f$ (the reduction of $rho_f$ mod $ell$) is consructed out of
the $ell$-torsion subgroup of the Picard group of this singular curve. Since it
is unramified at $p$, it can't be entirely explained by the singularities; some part of it
must be arising from the smooth curves, which are of level $N$. (If you like, this is an application of the a certain form of the criterion of Neron--Ogg--Shafarevic.) The Eichler--Shimura
relations then show that the system of Hecke eigenvalues attached to $f$, when reduced
mod $ell$, must arise at level $N$: in other words, there is an eigenform $g$ of level $N$ that is congruent to $f$ mod $ell$.

This is just one typical argument that uses a detailed knowledge of the good and bad reduction of modular curves in various situations. Since the Galois representation attached to modular forms are constructed geometrically from the modular curves, tools
like the Neron--Ogg--Shafarevic criterion, and variants thereof, show that there are
very close ties between the local properties of the Galois representations at a prime $p$,
and the reduction properties of modular curves mod $p$.

at.algebraic topology - Explanation for the Thom-Pontryagin construction (and its generalisations)

In 1950, Pontryagin showed that the n-th framed cobordism group of smooth manifolds was equal to n-th stable homotopy group of spheres:

$$lim_{k to infty} pi_{n+k}(S^k) cong Omega_n^{text{framed}}.$$

Later on, in his 1954 paper, Thom generalises this with the now called Thom spaces, and shows that there is a similar correspondence for more general types of cobordism: manifolds with a $(B,f)$ structure on their normal bundle; for example, unoriented cobordism for $B = BO$, oriented cobordism for $B = BSO$, complex cobordism for $B = BU$, framed cobordism for $B = BI$ for the identity $I$ in $O$, etc. (Thom considers the cases $BO$ and $BSO$.)
The generalisation he arrived to, now called the Thom-Pontryagin construction, is the following:

$$lim_{k to infty}pi_{n+k}(TB_k) cong Omega_n^{(B,f)},$$

where $TB$ is the Thom space of the universal bundle over $B$ given by the classifying map $B to BO$; $TB$ is obtained by adding a point at infinity to each fiber and gluing all these added points to a single point in the total space of the bundle.

In fact, the result can be generalised further by considering cobordism as a homology theory, and one arrives at the following:

$$Omega_n^{(B,f)}(X,Y) cong lim_{k to infty} pi_{n+k}(X/Y wedge TB_k),$$

where, if $Y$ is empty, $X/Y$ is the disjoint union of $X$ with a point (and $wedge$ is the smash product). Here $Omega_n(X,emptyset)$ is to be understood as a relative cobordism over $X$. This clearly generalises the previous result by taking $X$ to be a point (and $Y$ empty).

Now, my question is, how do you understand the Thom-Pontryagin construction? I've seen a few mentions of a particularly visual way of understanding it, but without much to actually back this up (besides from, I remember, a few mentions of blobs of ink). The standard proofs (in Stong's Notes on Cobordism Theory or in Thom's original paper for example) are quite long and I have trouble keeping hold of my geometric intuition throughout.

An assumption in pcf theory

Often in theorems of pcf theory one has the assumption that the length of sequences of functions has to respect some bound so things can be well-defined. For instance, let $a=[aleph_2,...,aleph_n,...:n<omega]$ be a set of regular cardinals, say you have a sequence $f_beta$ in $prod a$ of length at most $|a|^+$. Then $sup_beta f_beta in prod a$ since $|a|^+ < min(a)$. But why is this true? If you have for example an $omega_2$ sequence of functions $f:kappa rightarrow kappa$ such that $f(kappa)in kappa$, $kappa$ some $aleph_n$, $n$ not 0 and not 1,then why is $f_beta$ for $beta=omega_2$ outside of the product, as far as we know, we don't know if $2^{aleph_0}= aleph_2$ since $a$ is a countable set of regular cardinals (say the set of $aleph_n$'s)? Thanks

fa.functional analysis - Gradient of the energy functional in $H^{1,2}$-norm

I have to use estimates for the gradient of the energy functional on the free loop space of a fixed compact manifold $Q$. As such, one considers $H^{1,2}$-maps of the circle into $Q$. The energy functional is given by
$mathcal{E}:H^{1,2}(S^1,Q)rightarrow IR ,quad gammamapsto frac{1}{2}int_0^1|dot{gamma}(t)|^2dt$. Is there a neat formula for the gradient w.r.t. the $H^{1,2}$ inner product?

ag.algebraic geometry - The topological analog of flatness?

Recall that a map $f:Xto Y$ of schemes is called flat iff for any $xin X$ the ring $O_{X,x}$ is a flat $O_{Y,f(x)}$-module.
Briefly the question is: what is the topological analog of this?

Many notions and constructions in scheme theory have obvious topological counterparts (which probably were the inspiration at least in some cases, but I'm not a historian to tell this for sure). Gluing schemes is analogous to gluing smooth manifolds out of copies of Euclidean balls. Proper, 'etale and smooth morphisms all have obvious topological analogs: these are proper maps, local homeomorphisms and smooth maps of smooth manifolds such that the differential at each point is surjective (submersions). A separated scheme is the analog of a Hausdorff space. Moreover, in all these cases it seems clear that there is just one way of translating the corresponding topological notion in the language of schemes.

Flat morphisms seem trickier (to me). I'm aware of two interpretations. One is too vague ("a map such that the preimages of points don't vary too wildly"). The other ("a Serre fibration") is not completely satisfactory: all fibers of a Serre fibration are homotopy equivalent and are even homeomorphic if the fibration is locally trivial. However, there are plenty of flat maps which do not look like Serre fibrations at all: for example the projection of the union of the lines $x=pm y$ in the plane onto the $x$-axis.

One way to make the above question a bit more precise is this: is there a way to define the notion of a "flat" map (of sufficiently nice topological spaces, say smooth manifolds or CW complexes or polyhedra) in terms of topology or differential geometry so that when $X(mathbf{C})$ and $Y(mathbf{C})$ are the sets of closed points of varieties (= reduced separated schemes of finite type) $X$ and $Y$ over $mathbf{C}$ a morphism $Xto Y$ is flat if and only if induced map $X(mathbf{C})to Y(mathbf{C})$ of topological spaces is "topologically" flat? Maybe this is too much to ask for, in which case I'd be interested to know if there is a variation of this which holds.

An obvious guess: one should take the notion of a submersion and relax it, but I'm not sure how.

ra.rings and algebras - Characterizations of UFD and Euclidean domain by ideal-theoretic conditions

This questions is inspired by an exercise in Hungerford that I have only partially solved. The exercise reads: "A domain is a UFD if and only if every nonzero prime ideal contains a nonzero principal ideal that is prime." (For Hungerford, 'domain' means commutative ring with $1neq 0$ and no zero divisors).

One direction is easy: if $R$ is a UFD, and $P$ is a nonzero prime ideal, let $ain P$, $aneq 0$. Then factor $a$ into irreducibles, $a = c_1cdots c_m$. Since $P$ is a prime ideal in a commutative ring, it is completely prime so there is an $i$ such that $c_iin P$, and therefore, $(c_i)subseteq P$. Since $c_i$ is a prime element (because $R$ is a UFD), the ideal $(c_i)$ is prime.

I confess I am having trouble with the converse, and will appreciate any hints.

But on that same vein, I started wondering if there was a similar "ideal theoretic" condition that describes Euclidean domains. Other classes of domains have ideal theoretic definitions: PID is obvious, of course, but less obvious perhaps are that GCD domains can be defined by ideal-theoretic conditions (given any two principal ideals $(a)$ and $(b)$, there is a least principal ideal $(d)$ that contains $(a)$ and $(b)$, least among all principal ideals containing $(a)$ and $(b)$), as can Bezout domains (every finitely generated ideal is principal). Does anyone know if there is an ideal theoretic definition for Eucldean domains?

ca.analysis and odes - What does Gibbs phenomenon shows the nature of Fourier Series

Hi there,

I think there is a bit more to answering your question than considering just the strict $L^2$ convergence however. The Gibbs phenomenon is important when considering the pointwise convergence of the partial sums of the fourier series. When $f^{prime}$ is continuous on a compact interval, you will get pointwise convergence of the partial sums $S_N$ so $S_N(x) to f(x)$ as $N to infty$. (You only get uniform convergence if in addition the function $f$ is compatible with the boundary conditions for your expansion but this is not your question anyway).

Now what happens when $f$ is discontinuous? It turns out that $S_N(x) to frac{1}{2}[f(x_-) + f(x_+)]$, the average of the left and right limits of the function. However, this is really only true for $N to infty$. Otherwise for any finite $N$ there is a small width of order $1/N$ around your discontinuous point $x$ where your partial sums are uniformly bounded away from either value $f(x_+)$, $f(x_-)$ by some fixed percentage (I recall $9$% of the jump size or something but don't quote me on that). Check out the photos at:http://en.wikipedia.org/wiki/Gibbs_phenomenon
That little wiggle of the wave where the jump of $f$ occurs stays uniformly bounded away from the value of the function but the width of this region ($1/N$) goes to zero as $N to infty$ so that technically you still get the full pointwise convergence.

nt.number theory - Legitimacy of reducing mod p a complex multiplication action of an elliptic curve?

I scoured Silverman's two books on arithmetic of elliptic curves to find an answer to the following question, and did not find an answer:

Given an elliptic curve E defined over H, a number field, with complex multiplication by R, and P is a prime ideal in the maximal order of H and E has good reduction at P. Is it legitimate to reduce an endomorphism of E mod P?

In the chapter "Complex Multiplication" of the advanced arithmetic topics book by Silverman, a few propositions and theorems mention reducing an endomorphism mod P.

A priori, this doesn't seem trivial to me. Sure, the endomorphism is comprised of two polynomials with coefficients in H. But I still don't see why if a point Q is in the kernel of reduction mod P, why is phi(Q) also there. When I put Q inside the two polynomials, how can I be sure that P is still in the "denominator" of phi(Q)?

(*) I looked at the curves with CM by sqrt(-1), sqrt(-2) and sqrt(-3), and it seems convincing that one can reduce the CM action mod every prime, except maybe in the case of sqrt(-2) at the ramified prime.

ag.algebraic geometry - sheafifying a projective limit of presheaves

CORRECTED ANSWER: I believe that the answer is no, at least in some contexts.

For example, suppose that
$X =$Spec $k$, with $k$ a field, and $F = {mathbb Z}_{ell}(1)$. Then
$U =$Spec $l$ for some finite separable extension $l$ of $k$, and $H^1(U,F) = ell$-adic completion of $l^{times}$, which I will denote by $widehat{l^{times}}$.

Thus the stalk of the presheaf $U mapsto H^1(U,F)$ (and hence of the associated sheaf)
at the (unique) geometric point of $X$ is the direct limit over $l$ of $widehat{l^{times}}.$

This direct limit need not vanish. For example, if $k$ is finite, then so is $l$,
and $widehat{l^{times}}$ is just the $ell$-Sylow subgroup of $l$. Thus the stalk
in this case is just $bar{k}^{times}[ell^{infty}],$ the group of $ell$-power roots of unity in $bar{k}$.

This fits with a certain intuition, namely that one has to go to smaller and small etale neighbourhoods to trivialize $F_n$ as $n$ increases, and hence one can't kill of cohomology
classes in $H^i(U,F)$ just by restricting to some $V$.

I think that the answer is yes. Here is a proof (hopefully blunder-free):

It is true for the presheaf $U mapsto H^i(U,F_1).$ In other words, if we fix $U$,
then for each element $h in H^i(U,F_1)$ and each geometric point $x$ of $U$,
there is an etale n.h. $V$ of $x$ such that $h_{| V} = 0.$ Since $H^i(U,F_1)$
is finite dimensional, there is a $V$ that works for the whole of $H^i(U,F_1)$ at once.

I claim that then $H^i(U,F_n)$ restricts to $0$ on $V$ as well.

To see this, consider the exact sequence $0 to F_n to F_{n+1} to F_1 to 0.$
Applying $H^i(U,text{--})$ to this yields a middle exact sequence
$H^i(U,F_n) to H^i(U,F_{n+1}) to H^i(U,F_1).$ Applying $H^i(V,text{--})$
yields a middle exact sequence
$H^i(V,F_n)to H^i(V,F_{n+1}) to H^i(V,F_1).$ Restriction gives a map from the
first of these sequences to the second. It is zero on the two outer terms, by induction
together with the case $n = 1$ proved above, and so is zero on the inner term.

This shows that restricting from $U$ to $V$ kills $H^i(U,F_n)$ for all $n$, and hence
$H^i(U,F)$, as required.

EDIT: As was noted in the comment below, this proof assumes that $F$ is
${mathbb Z}_{ell}$ -flat. Let me sketch an argument that hopefully handles the general case:

Put $F$ in a short exact sequence $0 to F_{tors} to F to F_{fl} to 0.$ The same kind
of argument as above reduces us to checking $F_{fl}$ and $F_{tors}$ separately. The above proof handles the case of $F_{fl}$, while $F_{tors} = F_{tors,n}$ for some large enough $n$,
and so the projective limit collapses in this case and there is nothing to check.

(Note: I am assuming some basic kind of finiteness assumption on $F$ here, so that the above
makes sense. Constructibility should be enough.)

polymath5 - Analytic continuation of Dirichlet series with completely multiplicative coefficients of modulus 1

As a matter of fact, it isn't hard to construct a multiplicative sequence $a_n$ such that $f(z)$ is an entire function without zeroes. Unfortunately, it is completely useless for the questions that you brought up as "motivation".

Here is the construction.

Claim 1: Let $lambda_jin [0,1]$ ($j=0,dots,M$). Assume that $|a_j|le 1$ and $sum_ja_jlambda_j^p=0$ for all $0le ple P$. Then, if $P>2eT$, we have $left|sum_j a_je^{lambda_j z}right|le (M+1)(eT/P)^P$

Proof: Taylor decomposition and a straightforward tail estimate.

Claim 2: Let $P$ be large enough. Let $Delta>0$, $M>P^3$ and $(M+1)Delta<1$. Let $I_j$ ($0le jle M$) be $M+1$ adjacent intervals of length about $Delta$ each arranged in the increasing order such that $I_0$ contains $0=lambda_0$. Suppose that we choose one $lambda_j$ in each interval $I_j$ with $jge 1$. Then for every $|a_0|le 1$, there exist $a_jinmathbb C$ such that $|a_j|le 1$ and $sum_{jge 0} a_jlambda_j^p=0$ for $0le ple P$.

Proof: By duality, we can restate it as the claim that $sum_{jge 1}|Q(lambda_j)|ge |Q(0)|$ for every polynomial $Q$ of degree $P$. Now, let $I$ be the union of $I_j$. It is an interval of length about $MDelta$, so, by Markov's inequality, $|Q'|le CP^2(MDelta)^{-1} Ale CP^{-1}Delta^{-1}A$ where $A=max_I |Q|ge |Q(0)|$. But then on the 5 intervals $I_j$ closest to the point where the maximum is attained, we have $|Q|ge A-5Delta CP^{-1}Delta^{-1}Age A/2$. The rest is obvious.

Claim 3: Suppose that $a_0$ is fixed and $a_j$ ($jge 1$) satisfy $sum_{jge 0} a_jlambda_j^p=0$ for $0le ple P$. Then we can change $a_j$ with $jge 1$ so that all but $P+1$ of them are exactly $1$ in absolute value and the identities still hold.

Proof: As long as we have more than $P+1$ small $a_j$, we have a line of solutions of our set of $P+1$ linear equations. Moving along this line we can make one of small $a_j$ large. Repeating this as long as possible, we get the claim.

Now it is time to recall that the logarithm of the function $f(z)$ is given by

$$L(z)=sum_{ninLambda}a_ne^{-zlog n}$$
where $Lambda$ is the set of primes and prime powers and $a_n=m^{-1}a_p^m$ if $n=p^m$. We are free to choose $a_p$ for prime $p$ in any way we want but the rest $a_n$ will be uniquely determined then. The key point is that we have much more primes than prime powers for unit length.

So, split big positive numbers into intervals from $u$ to $e^Delta u$ where $Delta$ is a slowly decaying function of $u$ (we'll specify it later). Formally we define the sequence $u_k$ by $u_0=$something large, $u_{k+1}=e^{Delta(u_k)}u_k$ but to put all those backward apostrophes around formulae is too big headache, so I'll drop all indices. Choose also some slowly growing functions $M=M(u)$ and $P=P(u)$ to be specified later as well.

We need a few things:

1) Each interval should contain many primes. Since the classical prime number theorem has the error term $ue^{-csqrt{log u}}$, this calls for $Delta=exp{-log^{frac 13} u}$
Then we still have at least $u^{4/5}$ primes in each interval (all we need is to beat $u^{1/2}$ with some margin).

2) We should have $MDeltall 1$, $M>P^3$, and $uleft(frac{eT}Pright)^Ple (2u)^{-T-3}$ for any fixed $T>0$ and all sufficiently large $u$. This can be easily achieved by choosing $P=log^2 u$ and $M=log^6 u$.

3) At last, we'll need $M(P+sqrt u)ll u^{4/5}$, which is true for our choice.

Now it is time to run the main inductive construction. Suppose that $a_n$ are already chosen for all $n$ in the intervals up to $(u,e^{Delta}u)$ and we still have almost all primes in the intervals following the current interval free (we'll check this condition in the end). We want to assign $a_p$ for all $p$ in our interval for which the choice hasn't been made yet or was made badly. We start with looking at all $a_p$ that are not assigned yet or assigned in a lame way, i.e., less than one in absolute value. Claim 3 (actually a small modification of it) allows us to upgrade all of them but $P+1$ to good ones (having absolute value $1$) at the expense of adding an entire function that in the disk of radius $T$ is bounded by $(2u)^{T} uleft(frac{eT}Pright)^Ple u^{-3}$ to $L(z)$. Now we are left with at most $sqrt u$ powers of primes and $P+1$ lame primes to take care of. We need the prime powers participate in small sums as they are and we need the small coefficients to be complemented by something participating in small sums too. For each of them, we choose $M$ still free primes in the next $M$ intervals (one in each) and apply Claim 2 to make a (lame) assignment so that the corresponding sum is again bounded by $u^{-3}$ in the disk of radius $T$. We have at most $u$ such sums, so the total addition will be at most $u^{-2}$. This will finish the interval off. Now it remains to notice that we used only about $sqrt u+P$ free primes in each next interval and went only $M$ intervals ahead. This means that in each interval only $M(sqrt u+P)$ free primes will ever be used for compensating the previous intervals, so we'll never run out of free primes. Also, the sum of the blocks we constructed will converge to an entire function. At last, when $Re z>1$, we can change the order of summation and exponentiate finally getting the Dirichlet series representation that we need.

The end.

lo.logic - In model theory, does compactness easily imply completeness?

There are indeed many proofs of the Compactness theorem. Leo Harrington once told me that he used a different method of proof every time he taught the introductory graduate logic course at UC Berkeley. There is, of course, the proof via the Completeness Theorem, as well as proofs using ultrapowers, reduced products, Boolean-valued models and so on. (In my day, he used Boolean valued models, but that was some time ago, and I'm not sure if he was able to keep this up since then!)

Most model theorists today appear to regard the Compactness theorem as the significant theorem, since the focus is on the models---on what is true---rather than on what is provable in some syntactic system. (Proof-theorists, in contast, may focus on the Completeness theorem.) So it is not because Completness is too hard that Marker omits it, but rather just that Compactness is the important fact. Surely it is the Compactness theorem that has deep applications (or at least pervasive applications) in model theory. I don't think formal deductions appear in Marker's book at all.

But let's get to your question. Since the exact statement of the Completeness theorem depends on which syntactic proof system you set up---and there are a huge variety of such systems---any proof of the Completeness theorem will have to depend on those details. For example, you must specify which logical axioms are formally allowed, which deduction rules, and so on. The truth of the Completness Theorem depends very much on the details of how you set up your proof system, since if you omit an important rule or axiom, then your formal system will not be complete. But the Compactness theorem has nothing to do with these formal details. Thus, there cannot be hands-off proof of Completeness using Compactness, that does not engage in the details of the formal syntactic proof system. Any proof must establish some formal properties of the formal system, and once you are doing this, then the Henkin proof is not difficult (surely it fits on one or two pages). When I prove Completeness in my logic courses, I often remark to my students that the fact of the theorem is a foregone conclusion, because at any step of the proof, if we need our formal system to be able to make a certain kind of deduction or have a certain axiom, then we will simply add it if it isn't there already, in order to make the proof go through.

Nevertheless, Compactness can be viewed as an abstract Completness theorem. Namely, Compactness is precisely the assertion that if a theory is not satisfiable, then it is because of a finite obstacle in the theory that is not satisfiable. If we were to regard these finite obstacles as abstract formal "proofs of contradiction", then it would be true that if a theory has no proofs of contradiction, then it is satisfiable.

The difference between this abstract understanding and the actual Completness theorem, is that all the usual deduction systems are highly effective in the sense of being computable. That is, we can computably enumerate all the finite inconsistent theories by searching for formal syntactic proofs of contradiction. This is the new part of Completness that the abstract version from Compactness does not provide. But it is important, for example, in the subject of Computable Model Theory, where they prove computable analogues of the Completeness Theorem. For example, any consistent decidable theory (in a computable language) has a decidable model, since the usual Henkin proof of Completeness is effective when the theory is decidable.

---

Edit: I found in Arnold Miller's lecture
notes
an entertaining account of an easy proof of (a fake version of) Completeness from Compactenss (see page 58). His system amounts to the abstract formal system I describe above. Namely, he introduces the MM proof system (for Mickey Mouse),
where the axioms are all logical validities, and the only
rule of inference is Modus Ponens. In this system, one can
prove Completeness from Compactness easily as follows: We
want to show that T proves φ if and only if every model
of T is a model of φ. The forward direction is
Soundness, which is easy. Conversely, suppose that every
model of T is a model of φ. Thus, T+¬φ has no
models. By Compactness, there are finitely many axioms
φ₀, ..., φ_n in T such that
there is no model of them plus ¬φ. Thus,
(φ₀∧...∧φ_n implies
φ) is a logical validity. And from this, one can easily
make a proof of φ from T in MM. QED!

But of course, it is a joke proof system, since the
collection of validities is not computable, and Miller uses this example to illustrate the point as follows:

The poor MM system went to the Wizard of OZ and said, “I
want to be more like all the other proof systems.” And the
Wizard replied, “You’ve got just about everything any other
proof system has and more. The completeness theorem is easy
to prove in your system. You have very few logical rules
and logical axioms. You lack only one thing. It is too hard
for mere mortals to gaze at a proof in your system and tell
whether it really is a proof. The difficulty comes from
taking all logical validities as your logical axioms.” The
Wizard went on to give MM a subset Val of logical
validities that is recursive and has the property that
every logical validity can be proved using only Modus
Ponens from Val.

And he then goes on to describe how one might construct
Val, and give what amounts to a traditional proof of
Completeness.

algorithms - Enumerating m-tuples of Integers Subject to Implication Constraints

Unless m is small, some of the cij are small, or a lot of the dij are small, ( or you know something else which tells you the resulting list is small), you aren't going to save a lot by recoding.

At the moment, you have N many possible tuples where N is the product of m integers. Until I know more, I will say N "looks like" n^m. You know minimal values you need to check: say c_i is the mimimum over j of the cij, and C is the product of the c_i. N/C might be big enough to motivate you, but to me it looks just like (n/c)^m, and since you have to do C many tuples already, and extra cycles to decide about the rest, you may find that simple and right is better than complex and buggy. It's your call.

If the dij are such that, once outside the C-many unconstrained examples, they are close enough to the cij that you expect to toss most of the N-C possibilities away, then you want to organize the constraints so that the small loops are on the outside, and that you fail and toss a partial tuple sooner. The idea (which if you look at constraint programming literature) is that the tighter constraints narrow the search space, and you waste less time on failure. Thus you might see where dij-cij is smallest once you head outside C.

Your brief description in the comments does not give me much guidance. If you want more practical suggestions, some estimates of all the parameters (m, ns,cs,ds) as well as good guesses on C, N, and the expected size of the output would help give me such guidance.

My advice would be different if the tuples lay in a hyperplane sandwich ( e.g. sum of coordinates lie in a small range of numbers). Efficient enumeration would be harder but worthwhile, especially if you can memoize certain computations.

Gerhard "Or Try A Constraint Solver" Paseman, 2015.11.09

lo.logic - Coherent spaces

In Proofs and Types, Girard discusses coherent (or coherence) spaces, which is defined as a set family which is closed downward ($ain A,bsubseteq aRightarrow bin A$), and binary complete (If $Msubseteq A$ and $forall a_1,a_2in M (a_1cup a_2in A)$, then $cup Min A$)

It was informally related to topological spaces. Anyway, I have a couple pretty general questions:
Are they particularly useful outside of type theory? Perhaps more specifically, do coherent spaces show up in topology?

The last one raises up a philosophical question I've been pondering: Why is it that some structures seem to show up all over the place, while others that seem like they "should" be more or less equivalently useful don't seem to show up much at all? An example would be matroids versus topologies. I feel, morally, that matroids should be more useful than they seem to be.

The last question probably doesn't have any sort of solid answer, but it would be nice to hear some thought from people with a stronger background.

Cheers and thanks,
Cory

Edit:
After thinking about this some more, it has occurred to me that coherent spaces are a sort of "dual" to ultrafilters. I really don't have the background to be terribly formal, but, let me try to explain:

Let $(X,C)$ be a coherent space, and call the elements of $C$ "open" (I think the analogy is justified, because adding $X$ to $C$ makes it a topology), then the closed sets form an ultrafilter. The one problem is that the closure under intersection is a bit strong (the set of closed sets is closed under arbitrary intersections).
On the other hand, if $(X,U)$ is an ultrafilter, the set of complements of open sets almost forms a coherent space-- but the conditions on unions is just a little too weak.

So, my next question is: Has this link been explored at all? Is there even anything there to explore?

Thanks again.

ho.history overview - completeness axiom for the real numbers

Do any treatises on real analysis take the following as the basic completeness axiom for the reals?

"Let $A$ and $B$ be set of real numbers such that
(a) every real number is either in $A$ or in $B$;
(b) no real number is in $A$ and in $B$;
(c) neither $A$ nor $B$ is empty;
(d) if $alpha in A$, and $beta in B$, then $alpha < beta$.
Then there is one (and only one) real number $gamma$ such that
$alpha leq gamma$ for all $alpha in A$, and $gamma leq beta$
for all $beta in B$."

This appears as Theorem 1.32 in Walter Rudin's "Principles of Mathematical Analysis", and can be traced back to Dedekind's "Continuity and Irrational Numbers" (section V, subsection IV). Both Rudin and Dedekind derive this result from the construction of the reals via cuts of the rationals.

Authors who prefer to axiomatize the reals directly (instead of constructing them from the rationals) might be expected to take the above property as an axiom, but I haven't found anyone who does this. Instead, they all assume the least upper bound property as an axiom, or the nested interval property, or the convergence of Cauchy sequences.

I personally think the way to go is to take Rudin's Theorem 1.32 as an axiom (because it is simple and compelling) and then derive the least upper bound property (since it is more useful in practice than 1.32) and then get to work building up the apparatus of real analysis. But leaving aside the issue of whether this is the right way to go: have any authors taken this approach?

I should remark that the geometrical analogue of Theorem 1.32, characterizing the completeness of the line, appears to be well known to geometers (especially those interested in the foundations of geometry; see for instance Marvin Jay Greenberg's very nice article in the March 2010 issue of the Monthly).

pr.probability - Finding a distribution family that is preserved under mixture.

Below I propose a solution to the difference equation

$$f_{t+1}(z) =p_{12} f_t(z/A) + p_{21}f_t(z/B) + p_{22} f_t(z/(A+B)),$$

where the $p_{ij}$'s are positive,

$$p_{12}+p_{21}+p_{22}le 1$$ and $f_t$ is a pdf.

By integrating both sides of the given equation from $-infty$ to $infty$ we obtain after appropriate change of variables in the right hand side integrals

$$1=Ap_{12}+Bp_{21}+(A+B)p_{22}.$$

Now we look for a solution of our initial problem in the form

$$f_t (z) =sum_{n=0}^{infty} q_n (t) z^n .$$

Substituting the above ansatz into our equation yields after elementary manipulation

$$q_n (t+1) =left ( p_{12} A^{-n} +p_{21} B^{-n} +(A+B)^{-n} right ) q_n (t).$$

For fix $n$, the last equation is a linear difference equation that can be easily solved to produce

$$a_n(t) = b_n t^{ p_{12} A^{-n} +p_{21} B^{-n} +(A+B)^{-n}}$$ ,
where $a_n$ is independent of $t$ i.e. it's a pure constant.
Finally we obtain the closed-form solution
$$f_t (z) =sum_{n=0}^{infty} b_n t^{ p_{12} A^{-n} +p_{21} B^{-n} +(A+B)^{-n}} z^n.$$
Note that $$f_1(z) =sum_{n=0}^{infty} b_n z^n.$$
Thus our solution is completely specified given the initial pdf $f_1(z)$.
What is left is to tackle the issue of convergence and possible look for alternative representation of the solution.

fa.functional analysis - The "ultimate" indefinite inner product space

I think that it is possible with a large enough vector space $V$. I first misread the question, and constructed something where the inner product depends on $f$ while the mapping $F$ does not. The construction can be adapted to the true question as stated, so I'll still give it first as a warmup.

Version 1

I'll construct $F$ and $V$ together, and then construct the bilinear pairing last. Let $V_0 = mathbb{R}$ with its basis vector $1$. Then let $V_{n+1}$ be the direct sum of $V_n$ and the vector space $W_n$ of formal linear combinations of elements of $V_n setminus V_{n-1}$, where in this formula $V_{-1} = emptyset$. If $x in V_n setminus V_{n-1}$, let $[x]$ denote the corresponding element in $W_n subset V_{n+1}$. Let $V$ be the union of all $V_n$, and let $F(x) = [x]$. Note that every $x in V$ has a degree $d(x)$, by definition the first $n$ such that $x in V_n$.

To construct the pairing, let $langle 1,1 rangle = 1$. We need to choose values of $langle e,f rangle$ for every other unordered pair of basis vectors $e,f$. I claim that your constraints are triangular with respect to degree, in other words that the values can be constructed by induction. Also the diagonal values $langle e, e rangle$ are unrestricted. To see this, consider your equation

$$langle F(x), F(x) rangle + langle F(y),F(y) rangle - 2langle F(x), F(y) rangle = langle F(x) - F(y), F(x) - F(y) rangle = f(langle x-y, x-y rangle)$$
with $x ne y$. By construction, the arguments of the cross-term $langle F(x), F(y) rangle$ are both basis vectors, and only occur once for any given $x$ and $y$. Let's say that $max(d(x), d(y)) = n$. Then $d(x-y) le n$. In defining the inner product on $V_{n+1}$, the right side of your equation is already chosen, two terms on the left are unrestricted, and the third term can be chosen to satisfy the equality.

Version 2

Suppose instead that the inner product is to be fixed and instead $F$ can change with $f$. In this case, let $W_n$ be the vector space of formal linear combinations of elements of $(V_n setminus V_{n-1}) times mathbb{R}^mathbb{R}$, and as before let $V_{n+1} = V_n oplus W_n$. In this case, $W_n$ has a basis vector $[x,f]$ for every $f$ and every suitable $v$. For any fixed $f$, define $F(x) = [x,f]$.

As before, say that $langle 1,1 rangle = 1$ and that $langle [x,f], [x,f] rangle$ is unrestricted. Also $langle [x,f], [y,g] rangle$ is unrestricted when $f ne g$, for all $x$ and $y$. Finally, as before,

$$langle F(x), F(y) rangle = langle [x,f], [y,f] rangle$$
with $x ne y$ is uniquely determined by induction on $max(d(x),d(y))$.

Version 3

Ady reminds me that the second version still misses the condition that the bilinear form on $V$ should be non-degenerate. I think that the same trick works a third time: We can just enlarge $V$ to also guarantee this condition. This time let $W_n$ be as in the second version, and let

$$V_{n+1} = V_n oplus W_n oplus V_n^*,$$
where $V_n^*$ is the (algebraic) dual vector space to $V_n$.
Define the bilinear form on $V_n oplus W_n$ as in version 2, and define $F$ as in version 2. The bilinear form on $V_n^*$ is unrestricted, and so is the bilinear pairing between $V_n^*$ and $W_n$. Finally the bilinear pairing between $V_n^*$ and $V_n$ should be the canonical pairing $langle phi, x rangle = phi(x)$. This guarantees that for every vector $x in V_n$, there exists $y in V_{n+1}$ such that $langle y,x rangle = 1$.

Every version of the construction is cheap in the sense that the image of $F$ is a linearly independent set. Moreover, in the second and third versions, the image of $F$ is far from a basis. My feeling is that it is difficult to ask for much better than that in a universal construction.

soft question - Which are the best mathematics journals, and what are the differences between them?

I seem to remember this being discussed not too long ago on a certain blog not a long way from here ... but then maybe your question is a little more specific than that one was.

To the extent that this information is subjective, I don't think you'll get a good answer. To make it more objective, you need some way of classifying "this sort of article". One simple way is by subject, specifically MSC. Then one can do it by looking at MathSciNet and comparing, say, the last 100 articles published in a given journal. With a little bit of data munging (technical term), you can figure out which journals publish in which areas.

Unfortunately, if you read the AMS copyright, you can't distribute this information. In fact, you're not even allowed to keep it on your own computer for very long so you have to redo it every time.

I've got some scripts for automating this stuff here on my website (I hope that putting links to ones own website isn't considered Bad Form here!)

But maybe you have a different classification scheme in mind - do you?

ds.dynamical systems - How to construct a topological conjugacy?

Let me throw in some speculations based on my limited involvement in dynamical systems.

The conjugation formula $f=h^{-1}gh$ is in general not a type of a functional equation that can be solved by iterative approximations or a clever fixed-point trick. The problem is that you cannot determine how badly a particular $h$ fails by looking at the difference between LHS and RHS of this equation. The obstructions are not local and you don't see them until you consider all iterations of $f$ and $g$. Sometimes you can do approximations (e.g. Anosov system more or less survive under perturbations) but this works only in special types of systems (some kind of "hyperbolicity" is needed).

It seems that the only "general" way for constructing a topological conjugation is to study the orbits of $f$ and $g$ and send each orbit of $f$ to a similar orbit of $g$ so that the whole map is continuous. (A dense set of orbits is sufficient, e.g. the set of periodic points of an Anosov system.) The problem is, of course, that the structure of orbits can be really complicated. But if it is simple, one can hope to construct a conjugation directly.

For example, consider two homeomorphisms $f,g:mathbb Rtomathbb R$ satisfying $f(x)>x$ and $g(x)>x$ for all $x$. They are conjugate. To see this, consider an orbit $dots,x_{-1},x_0,x_1,x_2,dots$ of a point $x_0$ under the iterations of $f$. This is an increasing sequence and the intervals $[x_i,x_{i+1}]$ cover $mathbb R$. Every other orbit "interleaves" with this one: for example, if $y_0in(x_0,x_1)$, then $y_i:=f^i(y_0)$ lies between $x_i$ and $x_{i+1}$. So every orbit has a unique member in the interval $[x_0,x_1)$. In a sense, this interval (or rather the closed one with the endpoints glued together) naturally represents the set of all orbits.

So take any orbit $(x_i')$ of $g$ and let $h_0$ be any order-preserving bijection from $[x_0,x_1]$ to $[x_0',x_1']$. This defines a unique conjugacy map $h:mathbb Rtomathbb R$ such that $h|_{[x_0,x_1]}=h_0$: the orbit ${f^i(y)}$ of a point $yin [x_0,x_1]$ is mapped to the $g$-orbit ${g^i(h_0(y))}$ of the point $h_0(y)$. And all conjugations can be obtained this way.

Already in this simple example, you can see how fragile things can be. Even if $f$ and $g$ are smooth and have bounded derivatives, you have no control over how big the derivatives of $h$ can grow. (And you actually lose smoothness if you do the same on a closed interval rather than $mathbb R$.)

If you vary the map $g$, it remains conjugate to $f$ while the condition $g(x)>x$ holds true. But it suddenly stops being conjugate once a fixed point appears. However trivial this fact is, is shows that limit of conjugacy maps does not make sense in general.

The exercise you mention can be solved in a similar fashion as my toy example; the orbits are not much more complicated. In fact, given any two homeomorphisms $mathbb Rtomathbb R$, it is easy to understand whether they are conjugate or not (just study the intervals between fixed points). But the next step - homeomorphisms of the circle - is much more difficult: there are beautiful theorems, unexpected conterexamples, connections to number theory and other signs of a rich theory around such a seemingly trivial object. See Denjoy theorem and especially its smoothness requirements to get an idea how interesting these things can be.

gr.group theory - Does a Cayley graph on a minimal symmetric set of generators determine a finite group up to isomorphism?

Let $G = Z_4$ be the cyclic group on 4 elements, generated by $S = {-1,1 }$, let $H = Z_2 times Z_2$ be the Klein four group, generated by $T = {(0,1),(1,0)}$. Then $|S| = |T|$ and both Cayley graphs are isomorphic to $C_4$, the cycle of length 4.

For $n > 2$ each even cycle $C_{2n}$ is a Cayley graph for the cyclic group $Z_{2n}$ and for the dihedral group $D_n$ of order $2n$.

Another well-known example is the graph of a cube $Q_3$ which is a Cayley graph for the abelian group $Z_4 times Z_2$ and for the dihedral group $D_4$. In the previous example the dihedral group was generated by two involutions, while in the latter case it is generated by an involution and an element of order 4.

If only generators are counted, without their inverses, the first two examples do not give matching counts.

nt.number theory - Smallest k-term AP of primes

I'm not sure that your elementary argument is correct. Not only does the PNT not bite fast enough, but also the fact that every prime less than $k$ must divide $q$ gives only that $S(k)>(k-1)prod_{p_i< k}p_i$, or (using the primorial notation) $S(k)>(k-1)(k-1)#$. It is easy to show that $n#>n$, and hence we get the lower bound

$$S(k)>(k-1)^2$$
Let $l=lfloor log_2(k-1)rfloor$. Then it is slightly harder (e.g. see http://godplaysdice.blogspot.com/2007/09/hand-waving-asymptotics-of-primorial.html) to show that
$$(k-1)#>frac{(k-1)^l}{2^{l(l+1)/2}}$$

This gives us

$$S(k)>frac{(k-1)^{l+1}}{2^{l(l+1)/2}}>(k-1)^{(l+1)/2}$$
I'm not sure (barring using improved bounds for the primorial) whether these methods can get anything better.

You can regain your original $prod_{p_ileq k}p_i$ if you can rule out the possibility that the AP can start with $k$ itself, and this then gives you a lower bound

$$S(k)>(k-1)k^{(l-1)/2}$$
where $l=lfloorlog_2krfloor$.

Update: Of course, you can also gain a slight improvement by noting that the first term of the AP must be at least k, and hence

$$S(k)>k+(k-1)^{(l+1)/2}$$
since if we write our AP as $a,a+q,...,a+(k-1)q$then we're trying to find a lower bound for $a+(k-1)q$. This combines our best known bounds for both $a$ and $q$. I suspect that asymptotically $q$ will behave like $k#$, and so the $e^k$ is best possible, and the $(k-1)$ factor is fixed, so any improvements must come from better lower bounds for $a$, but these would be negligible compared to $e^k$. In summary, I think your given lower bound is essentially best possible.

linear algebra - Slick proof?: A vector space has the same dimension as its dual if and only if it is finite dimensional

It is clearly enough to show that an infinite dimensional vector space $V$ has smaller dimension that its dual $V^*$.

Let $B$ be a basis of $V$, let $mathcal P(B)$ be the set of its subsets, and for each $Ainmathcal P(B)$ let $chi_Ain V^*$ be the unique functional on $V$ such that the restriction $chi_A|_B$ is the characteristic function of $A$. This gives us a map $chi:Ainmathcal P(B)mapstochi_Ain V^*$.

Now a complete infinite boolean algebra $mathcal B$ contains an independent subset $X$ such that $|X|=|mathcal B|$---here, that $X$ be independent means that whenever $n,mgeq0$ and $x_1,dots,x_n,y_1,dots,y_min X$ we have $x_1cdots x_noverline y_1cdotsoverline y_nneq0$. (This is true in this generality according to [Balcar, B.; Franěk, F. Independent families in complete Boolean algebras. Trans. Amer. Math. Soc. 274 (1982), no. 2, 607--618. MR0675069], but when $mathcal B=mathcal P(Z)$ is the algebra of subsets of an infinite set $Z$, this is a classical theorem of [Fichtenholz, G. M; Kantorovich L. V. Sur les opérations linéaires dans l'espace des fonctions bornées. Studia Math. 5 (1934) 69--98.] and [Hausdorff, F. Über zwei Sätze von G. Fichtenholz und L. Kantorovich. Studia Math. 6 (1936) 18--19])

If $X$ is such an independent subset of $mathcal P(B)$ (which is a complete infinite boolean algebra), then $chi(X)$ is a linearly independent subset of $V^*$, as one can easily check. It follows that the dimension of $V^*$ is at least $|X|=|mathcal P(B)|$, which is strictly larger than $|B|$.

Later: The proof of the existence of an independent subset is not hard; it is given, for example, in this notes by J. D. Monk as Theorem 8.9. In any case, I think this proof is pretty because it captures precisely the intuition (or, rather, my intuition) of why this is true. I have not seen the paper by Fichtenhold and Kantorovich (I'd love to get a copy!) but judging from its title one sees that they were doing similar things...

Localization of power series and module structure

Let $R=mathbb{Q}[X,Y]$ be the polynomial ring of two commuting variable.
Let $S$ be the multiplicative subset of $R$ generated by homogeneous linear polynomials.
Let also $widehat{R}$ be the ring of formal power series in $X,Y,$
and $widehat{R}_S$ be the localization of $widehat{R}$ at $S.$
$widehat{R}_S$ is a $R-$module in the natural way.
Let $widehat{R}_S^0$ be the quotient $widehat{R}_S/mathbb{Q},$ all three
considered as Abelian groups.

Question: Is there a $R-$module structure on $widehat{R}_S^{0},$
which makes the quotient map a morphism of $R-$modules?

The question showed up when trying to make a distribution valued modular symbol.
The distributions map to power series via a Fourier transform.
One kills the constants as one way to make the Manin relations work.

computational complexity - What is the probability a random Turing machine is isomorphic to a DFA?

Let me focus on the question of your title, and mention
that there is another quite robust way to understand what
it means to say that a random Turing machine has
such-and-such property.

Specifically, we use the concept of asymptotic density as
the size of the program increases. For any natural number
$n$, there are only finitely many Turing machine program
using $n$ states. The asymptotic density or asymptotic probability
of a set $A$ of Turing machine programs is the limit (if it
exists)

• $lim_{ntoinfty} frac{|Acap P_n|}{|P_n|}$,

where $P_n$ is finite the set of Turing machine programs
with exactly $n$ states. Thus, the asymptotic probability
of a set $A$ of Turing machine programs is simply the limit
of the proportion of $n$-state programs in $A$. In
particular, if a set $A$ has asymptotic density $1$, then
it means that more than $99%$, more than $99.9%$, of
Turing machine programs are in $A$, as close to $1$ as
desired as the number of states increases. In this case, we
would seem to be justified in saying that almost every
Turing machine program is in $A$.

One can interpret your title question this way as
inquiring: what is the asymptotic density of the set of
Turing machine programs that decide sets that are
equivalent to a DFA?

To give an elementary sample calculation, a Turing machine
program $p$ in finite alphabet $Sigma$ with states $S$
(not counting the halt state) is a function
$Sigmatimes Sto Sigmatimes (Scup{halt})times{L,R}$. For example, if the alphabet
has $2$ symbols and there are $n$ states, then there are
$(4(n+1))^{2n}$ many programs. The number of programs that
never transition to the halt state, however, is
$(4n)^{2n}$, which has proportion $(frac{n}{n+1})^{2n}$,
which goes to $frac{1}{e^2}$ as $ntoinfty$. Thus, the
density of programs that never halt at all, because they
can never transition to the halt state, is $frac{1}{e^2}$,
or about $13.5%$. Of course, all such programs decide the
empty language, which is also decided by a DFA, so this is
a lower bound on the title question.

This way of thinking is the foundation of the topic of
generic case
complexity.
A central concern of this topic is the fact that many
undecidable or unfeasible decision problems admit a black
hole, a very small region where the problem is difficult,
outside of which it is easy. For example, it is not good to
base a financial encryption scheme on a problem whose
difficulty is confined to a black hole---a robber is after
all satisfied to rob the bank even only $90%$ of the time,
or even only $1%$ of the time. Alexei Miasnikov inquired
whether the halting problem itself admits a black hole, and
it turned out that for one of the standard models of
computability, the answer is yes:

Theorem.(Hamkins+Miasnikov) For the Turing machine
model with one-way infinite tapes, there is a set of Turing
machine programs $A$ such that

• $A$ has asymptotic density $1$, so almost every program
  is in $A$.


• $A$ is polynomial time decidable.


• The halting problem is polynomial time decidable for
  programs in $A$.

Thus, for this model of computation, the halting problem is
decidable with probability $1$. The reason has to do with
the fact that for the one-way infinite tape Turing machine
model, it turns out that almost every Turing machine
program, like Polya's drunken man, falls off the tape
before repeating a state. And this is something that can be
detected in linear time. It follows that with asymptotic
probability one, a Turing machine program computes a finite
set. Since all finite sets are DFA computable, we conclude:

Corollary. For the standard one-way infinite tape
model of Turing machines, with asymptotic probability one,
a random Turing machine computes a set that is DFA
decidable.

See J. D. Hamkins, A. Miasnikov, The halting problem is
decidable on a set of asymptotic probability
one, Notre Dame Journal
of Formal Logic, Notre Dame J. Formal Logic 47 (2006),
515–524.

See also this MO
answer,
which mentions similar ideas.

dg.differential geometry - Variational characterization of curvature?

The curvature is a local invariant. There is such a thing as the curvature at a point. The curvature is described as a tensor, after all. It is different in, say, symplectic geometry, where because of the Darboux theorem all symplectic manifolds of the same dimension are locally symplectomorphic; a fact usually paraphrased as "there is no symplectic curvature". This probably means that there is no "global invariant" formulation for the curvature.

As for the variational formulation, one possible line of approach would be to set up an action functional on algebraic curvature tensors; that is, sections of $S^2Lambda^2T^*M$ which are in the kernel of the Bianchi map

$$S^2Lambda^2T^*M to Lambda^4T^*M$$

cooked up in such a way that the Euler-Lagrange equations are the differential Bianchi identities, since then such a tensor would be the Riemann curvature tensor of the metric you use to define the action functional and whose Levi-Civita connection appears in the Euler-Lagrange equations.

Your idea about the action functional on the space of connections is what usually goes by the name of the Palatini (or first-order) formalism in GR. It is convenient in action functionals to treat the conenction and the soldering forms as independent quantities and let the Euler-Lagrange equations impose the torsion-free condition on the connection.

As a typical example, consider the Palatini action

$$int_M R(e,omega) mathrm{dvol}$$
where $R$ is formally the scalar curvature but written in terms of the soldering form $e$ and the connection $omega$. If you vary the action with respect to $e$ and $omega$ separately you find that $omega$ has no torsion and that the $M$ is Ricci-flat. To see what you gain in this formalism you just have to contemplate the calculation of the Euler-Lagrange equations for the Einstein-Hilbert action for the same Ricci-flatness condition, namely,
$$int_M R(e) mathrm{dvol}$$
where now the connection is written explicitly in terms of $e$.

nt.number theory - Reference of primitive root mod p

There are two things that you might want.

1) your example of 2 being a primitive root for $p=4q+1$ where $q$ is also prime comes from the more general criterion that if $p-1 = q_1^{e_1} dots q_r^{e_r}$ is a prime factorization then a non-zero reside $a$ is a primitive root if and only if

$a^{(p-1)/q_i} ne 1 bmod p$ for all $i$.

In the particular case you give $p-1 = 2^2 q$. So the criterion reduces to:

$2^{(p-1)/2} ne 1 bmod p$ and $2^2 ne 1 bmod p$. The second is certainly true if $p ne 3$. The first is true if and only if 2 is quadratic non-residue $bmod p$, which is true (by the law of quadratic reciprocity) if and only if $p equiv 3,5 bmod 8$. However, since if $q$ is odd, $p equiv 5 bmod 8$.

2) You might be interested in Artin's conjecture on primitive roots:

If $a$ is an integer $ne 0,pm 1$ or a square then there are an infinite set of primes $p$ for which $a$ is a primitive root. In fact this set is a positive proportion of all primes, where the constant of proportionality depends on $a$, see http://en.wikipedia.org/wiki/Artin%27s_conjecture_on_primitive_roots

Artin's original conjecture was amended due to computations by D.H. and Emma Lehmer (in a paper entitled "Heuristics Anyone"), and the amended conjecture was proved conditional on various extended Riemann Hypotheses by Hooley. Without the GRH it isn't known that there are even an infinite number of primes for which 2 is a primitive root (in particular it isn't known if there are an infinite number of primes $q$ for which $4q+1$ is prime)

ac.commutative algebra - An example of two elements without a greatest common divisor

It deserves to be much better known that nonexistant GCDs (and, similarly, nonprincipal ideals)
arise immediately from any failure of Euclid's Lemma, and this provides an illuminating way to view many of the standard examples. Below is a detailed explanation extracted from one of my sci.math.research posts [2]. The results below hold true in any domain D.

LEMMA: (a,b) = (ac,bc)/c if (ac,bc) exists

Proof: d|a,b <=> dc|ac,bc <=> dc|(ac,bc) <=> d|(ac,bc)/c. QED

EUCLID'S LEMMA: a|bc and (a,b)=1 => a|c, if (ac,bc) exists

Proof: a|ac,bc => a|(ac,bc) = (a,b)c = c via Lemma. QED

Therefore if a,b,c fail to satisfy the implication in Euclid's Lemma,
namely if (a,b) = 1 and a|bc, not a|c, then one
immediately deduces that the gcd (ac,bc) fails to exist in D.

E.g. David Speyer's example above, and Khurana's example in [1] (= Theorem 31 in Pete L. Clark's [0]) are simply specializations where a,b,c = p,1+w,1-w in a quadratic number (sub)ring Z[w], ww = -d.

[0] Clark, Pete. L. Factorization in integral domains. 29pp. 2009.
http://math.uga.edu/~pete/factorization.pdf

[1] D. Khurana, On GCD and LCM in domains: A Conjecture of Gauss.
Resonance 8 (2003), 72-79.
http://www.ias.ac.in/resonance/June2003/pdf/June2003Classroom.pdf

[2] sci.math.research, 3/12/09, seeking comments on expository article on factorization
http://groups.google.com/group/sci.math.research/msg/88343de90a4cf6b7
http://google.com/groups?selm=gparte%24si4%241%40dizzy.math.ohio-state.edu

fa.functional analysis - Selecting basic sequences

Not a basic sequence. Consider $e_0 oplus e_gamma$ in $Roplus H$ for $H$ a non separable Hilbert space, or, if you want a separable example, make $e_gamma$ a Hamel basis for a separable Hilbert space.

EDIT: Aug 2. Every separated sequence of unit vectors contains a minimal subsequence with bounded biorthogonal functionals. There remains the case where your linearly independent set has compact closure. I have an example of such a set where any minimal sequence in the set has only unbounded biorthogonal functionals, but I do not know whether such a set must contain a minimal sequence.

Too bad you did not ask this a day earlier when we could have discussed it face to face. I'll write something down when I get a chance.

EDIT: Aug 2. It was not so bad to write--I was able to do it on the plane.

If $x_n$ is a separated subset of the unit sphere of $X$, then $x_n$ has a minimal subsequence whose biorthogonal functionals are uniformly bounded. Indeed, if $x_n$ does not have weakly compact closure, then it has a basic subsequence (see e.g. the book of Albiac-Kalton), so we can assume that $x_nto x$ weakly. If $x=0$, then $x_n$ has a basic subsequence. If not, let $Q$ be the quotient map from $X$ onto $X/[x]$, where $[x]$ is the linear span of $x$. $Qx_nto 0$ weakly and is bounded away from zero by the separation assumption, hence has a basic subsequence $Qx_{n(k)}$, whence $x_{n(k)}$ is minimal with uniformly bounded biorthogonal functionals.

I don't know what can happen when $A$ is a linearly independent subset of the unit sphere of $X$ that is totally bounded, but there exists such sets so that every minimal sequence in the set has biorthogonal functionals that are not uniformly bounded. Consider the Cantor set as the branches of the infinite binary tree and let the nodes index the unit vector basis of $c_0$. Given a branch $t=(t(n))$ (where $t_1<t_2<dots$ in the tree ordering) of the tree, let $x_t=sum 2^{-n} e_{t(n)}$. By compactness (which is really just pigeonholing), any sequence $y_k$ of $x_t$-s has a subsequence that converges to some $x_s$, which means that for any $n$, if $kge k(n)$ then $y_k(j)=x_s(j)$ for $1le j le n$. From this it is easy to see that $y_k$ cannot be uniformly minimal.

In the above argument, try replacing the unit vector basis of $c_0$ with an appropriate normalized countably linearly independent sequence that has no minimal subsequence. I think it is known that such sequences exist. Probably an example is in Kadec's book. Maybe this will give an example that has no infinite minimal subset.

gt.geometric topology - Free actions of finite groups on products of even-dimensional spheres

Suppose a finite 2-group G acts freely on X = $prod_{i=1}^k$ *S*$^{2n_i}$, a product of k even-dimensional spheres, k > 2. Is it possible for G to be non-abelian? What if we additionally assume that spheres in the product are equidimensional?

Some comments: The equality 2^k = $chi(X)$ = |G|$chi(X/G)$ coming from the covering X $to$ X/G ensures that a finite group acting freely on X is a 2-group and also answers the question for k = 1, 2. (Actually, for k = 1 this gives a proof of a classical theorem: the only group which can act freely on an even-dimensional sphere is the cyclic group of order 2. Does anyone know who is this result originally due to? Sorry for a question inside the question; perhaps someone can comment on this one.) Hence if one would like to construct a sort of "minimal" example, it should involve an action of either the quaternion group Q₈ or the dihedral group Dih₄ for k = 3. I thought about this a little bit, but I feel like I'm not comfortable enough with non-abelian groups.

I've stumbled across some papers where authors characterize arbitrary finite groups acting freely on X in terms of existence of particular representations, but explicit examples are given only in the abelian case.

higher category theory - When are two natural transformations of infinity-categories equivalent?

No, not necessarily, since a transformation involves "higher structure" in addition to its 1-cell components. For example, let C be the "walking arrow" category with two objects 0 and 1 and one nonidentity morphism from 0 to 1, and let D be an abelian group regarded as a (2,1)-category with one object and one morphism, and thereby as an (∞,1)-category. There is exactly one functor from C to D. An endo-natural-transformation of this functor consists of giving, for each object of C, a morphism in D, and for each morphism in C, a 2-cell in D, subject to certain axioms.

There is only one morphism in D, so any two such transformations will have equal 1-cell components, but their 2-cells might be different. The axioms say that the 2-cell corresponding to an identity morphism is the identity, and that the 2-cell corresponding to a composite is the composite of the 2-cells corresponding to the individual factors; thus for the C and D above, to give a transformation is exactly to give an arbitrary element of the abelian group D (the 2-cell component corresponding to the single nonidentity arrow of C).

Now two transformations are equivalent when there is a modification between them, which consists of for each object of C, a 2-cell in D between the corresponding 1-cell components, and for each morphism of C, a 3-cell relating the 2-cell components etc. Since 3-cells in D are all identities, this latter means that there is a diagram that must commute. Since C has one object, a modification thus consists of giving a single element of the abelian group D, and the diagram which must commute means that it conjugates the element corresponding to the first transformation to the element corresponding to the second one. Thus, the equivalence classes of such transformations (all of which have the same 1-cell component) are the conjugacy classes of D.

sg.symplectic geometry - When should a moment polytope have "smooth" faces?

A codimension $d$ face of a polytope is called rationally smooth if it lies on only $d$ facets, because this is exactly the condition for the corresponding toric variety to have only orbifold singularities (not worse) there.

Is there some good reason that the moment polytope of a full flag manifold $G/B$ should have only smooth faces? It's easy to prove, and it doesn't hold for partial flag manifolds like $Gr(2,4)$ (whose moment polytope is an octahedron). Both of these varieties are smooth, of course, and neither is a toric variety; what the rational smoothness of the faces tells you is that the normalization of a generic $T$-orbit closure in the full flag manifold is orbifold, and in a Grassmannian it's not.

[Added: in general, if $X$ carries an algebraic action of a torus $T$, then $overline{Tcdot x}$ for a generic $xin X$ will be a variety with the same moment polytope as $X$. That doesn't make it a toric variety under Fulton's book's definition, as it may not be normal.]

Is there any other reason to predict that a given Hamiltonian space $X$ should have a moment polytope with this property?

Motivation: I have another such $X$, that isn't smooth actually, and its nonabelian moment polytope has this property inside the positive Weyl chamber. I would like to know "why".

gr.group theory - A functor that comes from a morphism in a bigger category

My loose question is like this: what would you say about an equivalence of categories where both are concrete categories, and the equivalence functor is induced from a set-theoretic bijection at the level of objects? It should be something like "equivalence of categories induced by a natural isomorphism over the category of Set" but I am not sure if that makes sense. Since this is not very clear, I will give the motivating example.

There is a construction involving finite p-groups and I'm looking for the right category-theoretic language that would describe the properties of this construction. The full construction is called the Lazard correspondence, but since the Lazard correspondence is hard to describe, I'll stick with a simple case: the Baer correspondence (I briefly describe it below, see here for more).

Let p be an odd prime. The Baer correspondence gives an equivalence between two categories:

p-groups of nilpotency class at most two $leftrightarrow$ Lie rings whose order is a power of p and nilpotency class is at most two

Here, a Lie ring is an abelian group with alternating biadditive Lie bracket satisfying the Jacobi condition. It can be thought of as a Lie algebra over the ring of integers.

The Baer correspondence is more than just an equivalence of categories, and even more than an isomorphism of categories, because it includes the following even more specific information: for a p-group of nilpotency class at most two, it actually constructs a p-Lie ring with the same underlying set, and hence it gives a set-theoretic bijection between each p-group and the corresponding p-Lie ring. For instance, in the direction from Lie ring to group, the group corresponding to a Lie ring L has the same underlying set and group operation:

$$xy := x + y + frac{1}{2}[x,y]$$

There's a similar formula for going from group to Lie ring.

Moreover, the functor between the categories is the same as the one induced by completing the square in this bijection. For instance, if $f:L_1 to L_2$ is a Lie ring homomorphism, and if $a_1:L_1 to G_1$ and $a_2:L_2 to G_2$ are the set bijections to their respective corresponding groups, then the functorially induced homomorphism from $G_1$ to $G_2$ is $a_2 circ f circ a_1^{-1}$ as a set map.

co.combinatorics - Finding monochromatic rectangles in a countable coloring of $R^{2}$

This is equivalent to CH.

Quoting "Problems and Theorems in Classical Set Theory" by Komjath and Totik, chapter 16, Continuum hypothesis:

CH holds if and only if the plane can be decomposed into countably many parts none containing 4 different points a,b,c,d such that dist(a,b)=dist(c,d)

This is a stronger requirement than your problem, so assuming CH the answer is no. Their solution, assuming CH is false, proves that there's a monochromatic rectangle.

---

Previous version, with added explanation about Hamel basis:

Using

CH holds if and only if R can be colored by countably many colors such that the equation x+y=u+v has no solution with different x,y,u,v of the same color.

This gives a negative answer assuming CH. Explanation: consider R as a vector space over Q. Let A be some basis. Take any bijection A -> A + A, where + is disjoint sum. It induces a linear isomorphism f: R -> R * R. (You can think that there's a linear isomorphism between reals and complexes if that helps.) Then, if you were given a monochromatic rectangle a=(x1, y1), b=(x1+x2, y1), c=(x1, y1+y2), d=(x1+x2, y1+y2), certainly a+d=b+c. Using that isomorphism, f(a)+f(d)=f(b)+f(c) gives a monochromatic solution of quoted equation.

gn.general topology - References for homotopy colimit

(1) What are some good references for homotopy colimits?

(2) Where can I find a reference for the following concrete construction of a homotopy colimit? Start with a partial ordering, which I will think of as a category and also as a directed graph (objects = vertices, morphisms = edges). Assume we have a functor $F$ from the graph into (say) chain complexes. We will construct a big chain complex (the homotopy colimit) in stages.

Stage 0: direct sum over all vertices $v$ of $F(v)$

Stage 1: direct sum over all edges $e$ of the mapping cylinder of $F(e)$, with the ends of the mapping cylinder identified with the appropriate parts of stage 0.

Stage 2: direct sum over all pairs of composable edges $(e_1, e_2)$ of a higher order mapping cylinder, with appropriate identifications to parts of stage 1. This implements a relation between the three stage 1 mapping cylinders corresponding to $e_1, e_2$ and $e_1*e_2$.

Stage 3: direct sum over all triples of composable edges $(e_1, e_2, e_3) dots$

at.algebraic topology - Proofs of Bott periodicity

Here is my attempt to address Eric's actual question. Given a real $n$-dimensional vector bundle $E$ on a space $X$, there is an associated Thom space that can be understood as a twisted $n$-fold suspension $Sigma^E X$. (If $E$ is trivial then it is a usual $n$-fold suspension $Sigma^n X$.) In particular, if $E=L$ is a complex line bundle, it is a twisted double suspension. In particular, if $X = mathbb{C}P^infty$, the twisted double suspension of the tautological line bundle $L$ satisfies the equation

$$Sigma^Lmathbb{C}P^infty = mathbb{C}P^infty.$$
As I understand it, Eric wants to know whether this periodicity can be interpreted as a Bott map, maybe after some modification, and then used to prove Bott periodicity. What I am saying matches Eric's steps 1 and 2. Step 3 is a modification to make the map look more like Bott periodicity.

I think that the answer is a qualified no. On the face of it, Eric's map does not carry the same information as the Bott map. Bott periodicity is a theorem about unitary groups and their classifying spaces. What Eric has in mind, as I understand now, is a result of Snaith that constructs a spectrum equivalent to the Bott spectrum for complex K-theory by modifying $mathbb{C}P^infty$. Snaith's model has been called "Snaith periodicity", but the existing arguments that it is the same are a use and not a proof of Bott periodicity. (In that sense, Snaith's model is stone soup, although that metaphor is not really fair to his good paper.)

For context, here is a quick definition of Bott's beautiful map as Bott constructed it in the Annals is beautiful. In my opinion, it doesn't particularly need simplification. The map generalizes the suspension relation $Sigma S^n = S^{n+1}$. You do not need Morse theory to define it; Morse theory is used only to prove homotopy equivalence. Bott's definition: Suppose that $M$ is a compact symmetric space with two points $p$ and $q$ that are connected by many shortest geodesics in the same homotopy class. Then the set of these geodesics is another symmetric space $M'$, and there is an obvious map $Sigma M' to M$ that takes the suspension points to $p$ and $q$ and interpolates linearly. For example, if $p$ and $q$ are antipodal points of a round sphere $M = S^{n+1}$, the map is $Sigma(S^n) to S^{n+1}$. For complex K-theory, Bott uses $M = U(2n)$, $p = q = I_{2n}$, and geodesics equivalent to the geodesic $gamma(t) = I_n oplus exp(i t) I_n$, with $0 le t le 2pi$. The map is then

$$Sigma (U(2n)/U(n)^2) to U(2n).$$
The argument of the left side approximates the classifying space $BU(n)$. Bott show that this map is a homotopy equivalence up to degree $2n$. Of course, you get the nicest result if you take $n to infty$. Also, to complete Bott periodicity, you need a clutching function map $Sigma(U(n)) to BU(n)$, which exists for any compact group. (If you apply the general setup to $M = G$ for a simply connected, compact Lie group, Bott's structure theorem shows that $pi_2(G)$ is trivial; c.f. this related MO question.)

At first glance, Eric's twisted suspension is very different. It exists for $mathbb{C}P^infty = BU(1)$, and of course $mathbb{C}P^infty$ is a $K(mathbb{Z},2)$ space with a totally different homotopy structure from $BU(infty)$. Moreover, twisted suspensions aren't adjoint to ordinary delooping. Instead, the space of maps $Sigma^L X to Y$ is adjoint to sections of a bundle over $X$ with fiber $mathcal{L}^2 Y$. The homotopy structure of the twisted suspension depends on the choice of $L$. For instance, if $X = S^2$ and $L$ is trivial, then $Sigma^L S^2 = S^4$ is the usual suspension. But if $L$ has Chern number 1, then $Sigma^L S^2 = mathbb{C}P^2$, as Eric computed.

However, in Snaith's paper all of that gets washed away by taking infinitely many suspensions to form $Sigma_+^{infty}mathbb{C}P^infty$, and then as Eric says adjoining an inverse to a Bott element $beta$. (I think that the "+" subscript just denotes adding a disjoint base point.) You can see what is coming just from the rational homotopy groups of $Sigma^infty mathbb{C}P^infty$. Serre proved that the stable homotopy of a CW complex $K$ are just the rational homology $H_*(K,mathbb{Q})$. (This is related to the theorem that stable homotopy groups of spheres are finite.) Moreover, in stable, rational homotopy, twisted and untwisted suspension become the same. So Snaith's model is built from the fact that the homology of $mathbb{C}P^infty$ equals the homotopy of $BU(infty)$. Moreover, there is an important determinant map

$$det:BU(infty) to BU(1) = mathbb{C}P^infty$$
that takes the direct sum operation for bundles to tensor multiplication of line bundles. Snaith makes a moral inverse to this map (and not just in rational homology).

Still, searching for a purely homotopy-theoretic proof of Bott periodicity is like searching for a purely algebraic proof of the fundamental theorem of algebra. The fundamental theorem of algebra is not a purely algebraic statement! It is an analytic theorem with an algebraic conclusion, since the complex numbers are defined analytically. The best you can do is a mostly algebraic proof, using some minimal analytic information such as that $mathbb{R}$ is real-closed using the intermediate value theorem. Likewise, Bott periodicity is not a purely homotopy-theoretic theorem; it is a Lie-theoretic theorem with a homotopy-theoretic conclusion. Likewise, the best you can do is a mostly homotopy-theoretic proof that carefully uses as little Lie theory as possible. The proof by Bruno Harris fits this description. Maybe you could also prove it by reversing Snaith's theorem, but you would still need to explain what facts you use about the unitary groups.

(The answer is significantly revised now that I know more about Snaith's result.)

books - reference for weak*-semigroup

I don't quite follow your notation, but I'll answer what I think you might be asking.

A $C_0$ or strongly continuous semigroup of operators $T_t$ on a Banach space $X$ is one such that $T_t x to x$ in norm as $t to 0$, i.e. $||T_t x - x||_X to 0$. In other words, $T_t to I$ in the strong operator topology.

A weakly continuous semigroup $T_t$ has $T_t x to x$ weakly as $t to 0$, i.e. $f(T_t x) to f(x)$ for each $f in X^*$. In other words, $T_t to I$ in the weak operator topology.

In fact, these two conditions are equivalent. This appears as Theorem 1.6 of K.-J. Engel and R. Nagel, A Short Course on Operator Semigroups.

So this is why you never hear anyone talking about weakly continuous semigroups.

ramsey theory - Magnitude of Graham's Number?

Such numbers are best understood in terms of some computability hierarchy. A common starting point is Ackermann's function, a version of which grows faster than any primitive recursive function (i.e. any fortran function definable with for loops, successor, and unlimited resources) . I will let you look up the function so that I do not misstate its definition. A(4,4) is something like the number of quarks in the universe, A(5,5) the number of arrangements of such quarks, and Graham's number is something like A(6,6). (I am making these up. Check elsewhere for the actual numbers. The above is just to give you an idea of scale.)

EDIT: Another poster has fixed the idea of scale, showing that Graham's number is much larger than I represent above. That poster also goes on to mention n(4) from the article mentioned below is in turn much larger than Graham's number which is much larger than n(3).
END EDIT

However, Graham's number is near the beginning of a list of enormous numbers. Harvey Friedman has a paper on some nice combinatorial problems whose answers go far beyond Graham's number. One of them is a simple sequence problem which starts out something like 2, 12, B, where B is somewhere near A(300,300). If more details come to mind, I will post them here.

In fact, I will post a section from Friedman's paper, 'Enormous Integers in Real Life'. He asked several people to guess at the size of B, which in the quote below is n(3), including L. Lovasz, given the description of the sequence. Lovasz guessed 20,000; Friedman uses A(n) instead of A(n,n):

"THEOREM 8.2. n(3) > A(7,184).

Lovasz wins, as his guess is closer to A(7,184) than the
other guesses. "

Gerhard "Ask Me About System Design" Paseman, 2010.01.15

gt.geometric topology - Necessary and sufficient criteria for a surface to cover a surface

I don't know the reference for this question, but I am pretty sure that it should follow from some known statement. Anyway let me give the answer in the case when S has negative Euler characteristic, orientable and CONNECTED. At least you can compare with your own answer. Denote by p(S) the number of punctures.

1) chi(S')/chi(S)=d with $d$ positive integer

2) $p(S)le p(S') le p(S)d$.

3) $p(S)d-p(S')$ should be even.

Moreover, in the case Genus(S)=0 you have an additional condition

$p(S)d-p(S')>d-2$. This condition assures that S' is connected.

I think that these conditions are necessary and sufficient. It is obvious that 1), 2) are necessary. Condition 3) comes from the fact, that the permutation corresponding to going around all punctures on S is a commutator, so it should be even.

In order to show that these conditions are sufficient, you could use the old result of Ore that tells that every even permutation is a commutator of two permutations.
Oystein Ore. Some remarks on commutators. Proc. Amer. Math. Soc., 2:307–314, 1951. Let me prove that conditions are sufficient in the case when genus of S is two or more.

Sketch of a proof. We want to show that there exists a collection of permutation in $S_d$,
$s_1,...,s_{2g}, t_1,...,t_p$ ($p=p(S)$) that act transitively on ${1,...,d}$ such that
$s_1s_2s_1^{-1}s_2^{-1}...=t_1...t_p$, where $t_1,...,t_p$ are given permutations with the product in the alternating group $A_d$. Then we chose $s_1$ and $s_2$ in such a way that $s_1s_2s_1^{-1}s_2^{-1}=t_1...t_p$ (Ore result) and take $s_3=s_4$ - cycles of length $d$, while all other permutations $s_i$ should be trivial. Clearly the action on ${1,...d}$ is transitive. Now the existence of a cover follows by standard arguments.

If you manage to make the proof very short it is worth to put it in the article, or at least give a hint. Otherwise, indeed, as Pete said it would be nice to find a reference.

ag.algebraic geometry - Degree of an embedded algebraic variety

There is a more geometric way to explain Felipe's answer. To compute the degree of a closed subvariety $Y$ of projective space, of dimension $n$ say, you intersect it with $n$ different hyperplanes in sufficiently general position (with respect to each other and also with respect to $Y$), so that the result is a collection of points, and you add up the number of points. This is the degree of $Y$.

In other words, degree has three properties that serve to define it:

(a) it is additive with respect to unions (EDIT: of distinct varieties of the same dimension, say, to avoid scheme-theoretic issues).

(b) the degree of a point is one.

(c) degree is preserved by taking sufficiently general hyperplane sections.
(I could omit the caveat sufficiently general here is I was willing to work
with scheme structures, and not just varieties).

(It is then an exercise, using these conditions, to relate the degree as defined this way
to the degree defined via the Hilbert polynomial.)

Now if $Y$ is the image of $X$ under the emdedding given by $|m A|$, then the intersection
of a hyperplane with $Y$ pulls back, under the isomorphism $X buildrel sim over to Y$,
to a member of the linear system $|m A|.$ (This is by the very definition of the embedding
given by $|m A|$.) When you intersect $n$ such divisors, the number of points you get is
then (m A)^n. (Because intersection is invariant under deformation of the cycles being
intersected, you can replace all the divisors by the linearly equivalent divisor $m A$.)

mg.metric geometry - Constructing a metric over a lattice

Consider a lattice $({cal L}, wedge, vee)$ with an antimonotonic function $f: {cal L} rightarrow {mathbb R}$ defined on it (i.e $x preceq y implies f(x) ge f(y)$).

$f$ is said to be submodular if for all $x,y in {cal L}$,

$$f(x) + f(y) ge f(x wedge y) + f(x vee y)$$ and supermodular if the inequality is flipped (again for all $x,y$).

It's generally known (there's an easy proof), that a submodular $f$ induces a metric on ${cal L}$ via the defn

$$d_s(x,y) = 2f(x wedge y) - f(x) - f(y)$$ . If $f$ is supermodular, then the construction $$d^s(x,y) = f(x) + f(y) - 2f(x vee y)$$ yields a metric.

Question I'm dealing with an $f$ that is nether sub- nor supermodular. I can define the "distance"

$$d(x,y) = min ( d^s(x,y), d_s(x,y))$$

Conjecture: $d(x,y)$ is a metric.

I have very little sound mathematical intuition for why this conjecture should be true, and bucketloads of empirical evidence (from a lattice I'm actually working with). This seems like the kind of thing that if true, would be reasonably well known to experts, and if false, might have a clear counterexample. So this is a plea for help.

Since it might make a difference, I should mention that the lattice I'm working with is nondistributive in general, but it has distributive sublattices where I'm still unable to prove the conjecture.

Is there a canonical Hopf structure on the center of a universal enveloping algebra?

Let $mathfrak g$ be a finite-dimensional Lie algebra over $mathbb C$. Define $mathcal Z(mathfrak g)$ to be the center of the universal enveloping algebra $mathcal Umathfrak g$, and define $(mathcal Smathfrak g)^{mathfrak g}$ to be the ring of invariant elements of the symmetric algebra $mathcal Smathfrak g$ under the induced adjoint action of $mathfrak g$. (Clearly $mathcal Z(mathfrak g) = (mathcal Umathfrak g)^{mathfrak g}$ via the adjoint action.) The Duflo isomorphism is an isomorphism of algebras $mathcal Z(mathfrak g) cong (mathcal Smathfrak g)^{mathfrak g}$. At the level of vector spaces, the trick is to realize that the PBW map $mathcal Umathfrak g to mathcal S mathfrak g$ is an isomorphism of $mathfrak g$-modules. For the isomorphism of algebras in the semisimple case, see for example my unedited notes on the class by V. Serganova.

(I read here that this isomorphism can be realized as a composition of the PBW vector-space isomorphism $mathcal Umathfrak g to mathcal Smathfrak g$ with the map $mathcal Smathfrak g to mathcal Smathfrak g$ given by $x mapsto sinh(x/2)/(x/2)$. But it's not at all obvious that this composition is even well-defined or linear when restricted to $mathcal Z(mathfrak g)$. I should mention that $mathcal Z$ is not a functor, I think. The PBW isomorphism is non-canonical, although a canonical version can be given via the symmetrization map, and I guess on the center it is canonical.)

When $mathfrak g$ is semisimple of rank $n$, at least, one can further show that $(mathcal Smathfrak g)^{mathfrak g} cong mathbb C[x_1,dots,x_n]$, although you have some choice about how to make this isomorphism. Thus, at least when $mathfrak g$ is semisimple, $mathcal Z(mathfrak g)$ is a polynomial ring.

But any polynomial ring can be given a Hopf structure. By choosing an isomorphism with $mathbb C[x_1,dots,x_n]$, we can take the Hopf structure generated by $Delta: x_i mapsto x_i otimes 1 + 1 otimes x_i$. In fact, this structure doesn't depend quite on the full choice of isomorphism. A Hopf structure on a commutative algebra $R$ is by definition the same as an algebraic group structure on $text{Spec}(R)$. But $text{Spec}(mathbb C[x_1,dots,x_n])$ is $n$-dimensional affine space — the algebra isomorphisms of $mathbb C[x_1,dots,x_n])$ are precisely the affine maps — so picking a commutative group structure is the same as picking an origin. (For certain values of $n$ there are also non-commutative group structures on affine $n$-space, and so non-cocommutative Hopf structures on the polynomial ring. For example, the group of upper-triangular matrices with $1$s on the diagonal is affine.)

My question is whether this Hopf structure can be picked out canonically.

Question: If $mathfrak g$ is a finite-dimensional Lie algebra over $mathbb C$, can the center $mathcal Z(mathfrak g)$ of the universal enveloping algebra be given a canonical (cocommutative) Hopf algebra structure? If no, how much extra structure on $mathfrak g$ is needed?

Here by "canonical" I of course don't mean that there is a unique one, so you may make choices once and for all. But there should be some definition/construction that does not require the user to make any choices to implement it. By "extra structure" I mean either extra structure (an invariant metric, for example) or extra properties (semisimplicity, for example).

My suspicion is that the answer is "yes" for a metric Lie algebra, which is a Lie algebra $mathfrak g$ along with a choice of an invariant nondegenerate metric, i.e. a chosen isomorphism of $mathfrak g$-modules $mathfrak g cong mathfrak g^*$. Metric Lie algebras include the semisimples and the abelians, and certain extensions of these (in fact, I believe that there is a structure theorem that any metric Lie algebra is a metric extension of semisimples and abelians, but don't quote me), but generally there are many choices of metric (e.g. any metric on an abelian Lie algebra $mathfrak a$ is invariant, so there are $mathfrak{gl}(dim mathfrak a)$ many choices).

The motivation for my question is this: by studying Vassiliev invariant and/or perturbative Chern-Simons theory, Bar Natan and others have defined a certain commutative and cocommutative Hopf algebra $A$ of "diagrams". Any choice of metric Lie algebra $mathfrak g$ determines an algebra homomorphism $A to mathcal Z(mathfrak g)$. I would like to know if this can be made into a Hopf algebra homomorphism.

gt.geometric topology - Reducible 3d torus bundles

Yes - surface bundles over the circle are irreducible (*) as long as the fiber is not a two-sphere. This follows from the fact that the universal cover of such a surface bundle is homeomorphic to $mathbb{R}^3$ and Proposition 1.6 of Hatcher's three-manifold notes.

(*) in the sense of connect sum.

EDIT: To answer the question posed by Juan in the comment. A orientation preserving homeomorphism $h$ of $T^2$ is reducible (that is, preserves the isotopy class of some essential multicurve) if and only if $h$ is a power of a Dehn twist or is the power of a Dehn twist followed by the hyperelliptic element. Here is a "cut-and-paste" proof: if $h$ preserves a multicurve then it preserves a curve, say $alpha$. Now, $h$ either preserves or reverses the orientation of $alpha$. If the latter case replace $h$ by $h$ followed by the hyperelliptic, to reduce to the former case. Isotope $h$ so that $alpha$ is fixed pointwise. Note that, as $h$ preserves orientation of $T^2$, the sides of $alpha$ are preserved as well. Thus $h$ restricts to a homeomorphism of the annulus, fixing the boundary pointwise. By the classification of mapping classes in the annulus, $h$ is a Dehn twist.

As a bit of an advertisement: Farb and Margalit have written a primer on the maping class group. You can find a discussion of the mapping class groups of the disk, annulus, and torus in Section 2.4, on the "Alexander Method". (In particular they give the usual proof that the group of orientation oreserving classes on $T^2$ is $SL(2,Z)$. They also give as an exercise the characterization of Dehn twists.)

I'll end by pointing out that there is not a contradiction between my answer and Hatcher's. If the monodromy is reducible then the resulting torus bundle is Seifert fibered and in fact has Nil geometry.

ct.category theory - Collapsing objects in a category

Domenicos comment lead to the following idea (I am posting this as an answer, as it is too long for a comment):

Let $CAT$ denote the category of small categories and $CAT'$ denote the category, whose objects are small categories except for the fact that the composition needn't be defined on the whole of $Mor(A,B)times Mor(B,C)$ (but just on a subset of it). Associativity and so on should hold, whenever it is defined.

Then there is a obvious inclusion Functor $CATrightarrow CAT'$. One should check, whether it has a left adjoint $L:CAT'rightarrow CAT$. Then one can make out of the data above a object in CAT' by adding an additional isomorphism from $X$ to $Y$ and one doesn't have to worry aboutthe compositions of that iso with the morphisms in CAT. Using $L$ one could make a honest category out of this.