nt.number theory - cocompact discrete subgroups of SL_2

For the arithmetic point of view you mention, Maclachlan and Reid's book "The arithmetic of hyperbolic 3-manifolds" is a great reference.

In case you're interested, there are also many geometric ways of doing this too (though you might object that some of them don't explicitly give you the subgroup).

You can explicitly build closed hyperbolic 3-manifolds out of polyhedra.

You can take a finite covolume subgroup and produce a cocompact subgroup via hyperbolic dehn surgery.

By a theorem of R. Brooks ("Circle packings and co-compact extensions of Kleinian groups", Invent. math. 86, 461-469 (1986)), you can take any cocompact subgroup of $mathrm{SL}_2(mathbb{R})$, and after a small quasiconformal conjugacy, it will lie in a cocompact subgroup of $mathrm{SL}_2(mathbb{C})$.

ct.category theory - Strong monics in the category of locales

No. The category of locales is dual to the category of frames, which is monadic (in fact, equationally presented) over Set. Any such category is Barr-exact, and in particular a regular category, which implies that every strong epic of frames is regular—hence every strong monic of locales is regular.

Lower bound on the convergence rate of a specific Markov chain

I have a Markov chain $mathbf{A} = (A_0, A_1, ldots)$ with state space ${0, ldots, n}$ which converges towards a stationary distribution $pi$. There are a lot of well-known results on upper-bounding the convergence rate. However, I'm interested in getting a lower bound.

---

In detail, the problem looks like this: The transition probability is given as

$p_{ij} = {n choose i}left(1-({1over 2})^jright)^ileft(({1over 2})^jright)^{n-i}$ for $jneq 0$,

$p_{ij} = {n choose i}left(1-({1over 2})^nright)^ileft(({1over 2})^nright)^{n-i}$ for $j = 0$,

and the initial distribution $A_0$ is $(1, 0, ldots, 0)^T$, i.e., the chain starts in state $0$ with probability $1$.

Given this information, is it possible to derive a lower bound on the convergence rate? Since I'm particularly interested in state 0, I would like to come up with something like this:

$lvert mathbb{P}(A_k = 0) - pi_0 rvert geq ldots$ some function of $k$ and $n$.

Any hints on how to approach this would be appreciated. Please also speak up if you think that it is unlikely that such a closed-form expression exists and I should stop wasting my time on this problem. I'm a computer scientist, not a mathematician, so it's quite possible that I've overlooked something obvious.

computer science - What algorithm in algebraic geometry should I work on implementing?

My proposal: a usable tool for working with line bundles on toric varieties and their cohomology. There are some tools (Polymake, Latte) for working with polyhedra, but I haven't seen a library dedicated specifically to toric varieties.

For example, you could provide a GUI tool for working with toric surfaces, where you can e.g. blow a point up by a single click (as far as I remember, this corresponds to adding an edge), compute intersections of divisors and cohomology of line bundles.

Also: toric deformations and degenerations, action of the Frobenius morphism (there are two descriptions of Frobenius push-forwards of line bundles, due to Thomsen and Bondal), finding exceptional collections etc.

I think this could be really interesting and useful.

big list - Which journals publish expository work?

I wonder if anyone else has noticed that the market for expository papers in mathematics is very narrow (more so than it used to be, perhaps).

Are there any journals which publish expository work, especially at the "intermediate" level? By intermediate, I mean neither (i) aimed at an audience of students, especially undergraduate students (e.g. Mathematics Magazine) nor (ii) surveys of entire fields of mathematics and/or descriptions of spectacular new results written by veteran experts in the field (e.g. the Bulletin, the Notices).

Let me give some examples from my own writing, mostly just to fix ideas. (I do not mean to complain.)

1) About six years ago I submitted an expository paper "On the discrete geometry of Chicken McNuggets" to the American Mathematical Monthly. The point of the paper was to illustrate the utility of simple reasoning about lattices in Euclidean space to give a proof of Schur's Theorem on the number of representations of an integer by a linear form in positive integers. The paper was rejected; one reviewer said something like (I paraphrase) "I have the feeling that this would be a rather routine result for someone versed in the geometry of numbers." This shows that the paper was not being viewed as expository -- i.e., a work whose goal is the presentation of a known result in a way which will make it accessible and appealing to a broader audience. I shared the news with my officemate at the time, Dr. Gil Alon, and he found the topic interesting. Together we "researchized" the paper by working a little harder and proving some (apparently) new exact formulas for representation numbers. This new version was accepted by the Journal of Integer Sequences:

http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Clark/clark80.html

This is not a sad story for me overall because I learned more about the problem ("The Diophantine Problem of Frobenius") in writing the second version with Gil. But still, something is lost: the first version was a writeup of a talk that I have given to advanced undergraduate / basic graduate audiences at several places. For a long time, this was my "general audience" talk, and it worked at getting people involved and interested: people always came up to me afterward with further questions and suggested improvements, much more so than any arithmetic geometry talk I have ever given. The main result in our JIS paper is unfortunately a little technical [not deep, not sophisticated; just technical: lots of gcd's and inverses modulo various things] to state, and although I have recommended to several students to read this paper, so far nothing has come of it.

2) A few years ago I managed to reprove a theorem of Luther Claborn (every abelian group is isomorphic to the class group of some Dedekind domain) by using elliptic curves along the lines of a suggestion by Michael Rosen (who reproved the result in the countable case). I asked around and was advised to submit the paper to L'Enseignement Mathematique. In my writeup, I made the conscious decision to write the paper in an expository way: that is, I included a lot of background material and explained connections between the various results, even things which were not directly related to the theorem in question. The paper was accepted; but the referee made it clear that s/he would have preferred a more streamlined, research oriented approach. Thus EM, despite its name ("Mathematical Education"), seems to be primarily a research journal (which likes papers taking new looks at old or easily stated problems: it's certainly a good journal and I'm proud to be published in it), and I was able to smuggle in some exposition under the cover of a new research result.

3) I have an expository paper on factorization in integral domains:

http://math.uga.edu/~pete/factorization.pdf

[Added: And a newer version: http://math.uga.edu/~pete/factorization2010.pdf.]

It is not finished and not completely polished, but it has been circulating around the internet for about a year now. Again, this completely expository paper has attracted more attention than most of my research papers. Sometimes people talk about it as though it were a preprint or an actual paper, but it isn't: I do not know of any journal that would publish a 30 page paper giving an intermediate-level exposition of the theory of factorization in integral domains. Is there such a journal?

Added: In my factorization paper, I build on similar expositions by the leading algebraists P. Samuel and P.M. Cohn. I think these two papers, published in 1968 and 1973, are both excellent examples of the sort of "intermediate exposition" I have in mind (closer to the high end of the range, but still intermediate: one of the main results Samuel discusses, Nagata's Theorem, was published in 1957 so was not exactly hot off the presses when Samuel wrote his article). Both articles were published by the American Mathematical Monthly! I don't think the Monthly would publish either of them nowadays.

Added: I have recently submitted a paper to the Monthly:

http://math.uga.edu/~pete/coveringnumbersv2.pdf

(By another coincidence, this paper is a mildly souped up answer to MO question #26. But I did the "research" on this paper in the lonely pre-MO days of 2008.)

Looking at this paper helps me to see that the line between research and exposition can be blurry. I think it is primarily an expository paper -- in that the emphasis is on the presentation of the results rather than the results themselves -- but I didn't have the guts to submit it anywhere without claiming some small research novelty: "The computation of the irredundant linear covering number appears to be new." I'll let you know what happens to it.

(Added: it was accepted by the Monthly.)

nt.number theory - Families of number fields of prime discriminant

I am going to annoy all the people who answered above, but I am pretty sure the answer to Dror's question is basically no. In particular, is it known that there are infinitely many cubic fields of prime discriminant? I have not heard of such a result -- if one is out there then I would be extremely grateful if someone would share the appropriate references with me.

As is pointed out above, there is a classical correspondence between such fields and subgroups of $Cl(mathbb{Q}(sqrt{p}))$ of index 3. However, I'm not aware that this makes the question easier to answer.

There is also the work of Bhargava and Ghate, Delone-Faddeev, Davenport-Heilbronn, etc. which says that cubic (and quartic and quintic) fields are parameterized by integral orbits on nice prehomogeneous vector spaces which meet certain local conditions. For example, in the cubic case, cubic rings are parameterized by integral binary cubic forms up to $GL_2(mathbb{Z})$ equivalence, and maximal cubic orders are those cubic rings which meet a certain local condition at each prime.

This allows you to prove formulas for the number of cubic fields with $Disc(K) < X$ with good error terms, and this works if you ask for the condition $d | Disc(K)$. This allows you to run a sieve.

However sieves are notoriously bad at finding primes! The information above is also essentially available in the twin prime problem, but all we can prove there is that there are infinitely many primes $p$ so that $p + 2$ has at most two prime factors.

You can use this argument to find cubic fields with three (I think) prime factors -- there is a paper of Belabas and Fouvry that does this. Maybe you could push their arguments a little bit better. But one cannot hope to find primes this way.

Of course there are excellent computational results, and I don't want to take anything away from these. But I feel like the question is asking if there are infinite families, and I'm pretty sure this is widely expected but not at all known.

lo.logic - Is non-connectedness of graphs first order axiomatizable?

I haven't thought about model theory in a while but I'll give this a shot. First, by bi-infinte graph, I assume that you mean $mathbb{Z}$ in which the only edges are those adjoining adjacent vertices, right?

Does the theory of cycle-free graphs admit quantifier elimination? If so, elementary equivalence follows from the fact that the isomorphism type of every finite substructure (or "type") in $H$ and $mathbb{Z}$ is expressible by a formula.

However, if I think about a direct back-and-forth argument, I'm worried about the following apparent obstruction. Say $H= H_0 cup H_1$, where $H_i$ are the paths. Suppose that one already has a partial isomorphism
${(h_0, z_0), (h_1, z_1)}$ starting a back-and-forth argument, where $h_iin H_i$. Now $mathbb{Z}$ satisfies a sentence, call it $f$, asserting that $z_0$ and $z_1$ are joined by a path of length $n$; clearly $H notmodels f$.

Did I just prove that the theory cannot not eliminate quantifiers? Sorry, I didn't mean to turn your question into another one.

pr.probability - Wasserstein distance in R^d from one dimensional marginals

This is a test: I am recovering from a hand injury and I think that if I can work a Mathoverflow problem, then I am fit enough to resume work. Here is a non-constructive answer to the question. So, Roberto, let me know soon if I can go back to work.

I don't know of any reference where you can find the solution. I started thinking about the problem and found a simple solution (using standard results).
I read in another question about Wasserstein distance the suggestion of using a finite cover of the unit ball in $Lip(mathbb{R}^d) $ to reduce estimates of $ W_{mathbb{R}^d} $ to a max over a finite set. I see that idea working for Lipschitz functions on a bounded set, but I don't see how to apply that idea when working in the whole $mathbb{R}^d $.

Here is my solution.

Let
$quad Lip1(mathbb{R}^d) = {f:mathbb{R}^d longrightarrowmathbb{R}: forall x,y in mathbb{R} ^d text{ with } x neq y, frac{|f(x)-f(y)|}{|x-y|} leq 1) }$

be the set of 1-Lipschitz functions in $mathbb{R}^d$.

Let $mathcal{G}$ be the set of functions on $ mathbb{R}^d $ of the form:
$(1)quad f(x) = sum_{i in F} a_if_i(xcdot{v_i}) $
where
$quad F$ is a finite set,
$quad a_i in mathbb{R}, a_i geq 0, sum_{i in F} a_i = 1,$
$quad f_i in Lip1(mathbb{R}) ,$
$quad v_i in mathbb{R}^d , |v_i| = 1 text{ (Euclidean norm)}$
i.e.: $mathcal{G}$ is the convex hull of $Lip1(mathbb{R})$ functions composed with one dimensional projections. Clearly
$quad mathcal{G} subseteq overline{mathcal{G}} subseteq Lip1(mathbb{R}^d)$
where
$overline{mathcal{G}}$ is the closure of
$mathcal{G}$ in any topology in which $Lip1(mathbb{R}^d)$ is closed.
We will work with a weak* topology, namely the one in which the neighborhoods of 0 are generated by the sets
$(2)quad mathcal{N} = {f in Lip(mathbb{R}^d):
arrowvert int_{mathbb{R}^d} f(x) u(x) dx +
int_{mathbb{R}^d} nabla f(x) cdot{w(x)} dxarrowvert < epsilon } $
for some $ u in L^1(mathbb{R}^d, (1+|x|)dx)$ with $int u(x) dx = 0$,
some $ w in L^1(mathbb{R}^d)^d $, and some $ epsilon > 0 $.

Here are some known facts:
1) If $f in Lip(mathbb{R}^d)$, then $ f$ is differentiable a.e and $ sup{ frac{|f(x)-f(y)|}{|x-y|}: x neq y} = |nabla f |_infty $ is finite, denoted $|f|_{Lip}$.

2) If $f in Lip(mathbb{R}^d)$, then $ |f(x) - f(0)| leq |f|_{Lip} |x| $, so the integral $int_{mathbb{R}^d} f(x) u(x) dx $ is well defined for any $ u in L^1(mathbb{R}^d ,(1+|x|)dx)$.

3) With this topology $ Lip(mathbb{R}^d) $ is not separable. We will be actually working in $ Lip(mathbb{R}^d)/constants $, but we will not need be very explicit about it.

4) With this topology, any linear continuous function is of the form
$quad int_{mathbb{R}^d} f(x) u(x) dx +
int_{mathbb{R}^d} nabla f(x) cdot{w(x)} dx $
for some $ u in L^1(mathbb{R}^d, (1+|x|)dx)$ with $int u(x) dx = 0$,
and some $ w in L^1(mathbb{R}^d)^d $. The representation is not unique.

Claim 1: Let $mathcal{S}$ be the space of functions like (1) with arbitrary $a_i$, i.e.: $ mathcal{S}=mathbb{R}mathcal{G} $. The closure of $ mathcal{S}$ in the topology defined in (2) is $Lip(mathbb{R}^d)$.

Proof: If $ overline{mathcal{S}} neq Lip(mathbb{R}^d)$ then, by Hahn-Banach, there would by a non-zero linear function $ L(f)=int_{mathbb{R}^d} f(x) u(x) dx +
int_{mathbb{R}^d} nabla f(x) cdot{w(x)} dx$ such that $L(f) = 0$ for all $f in mathcal{S}$.
Let $rho$ be a smooth function with compact support. Since $mathcal{S}$ is invariant under translations it follows that
$(3) quad 0 = int uast{rho}(x) f(x) + wast{rho}(x)cdot{nabla f(x)} dx = $
$quad int (uast{rho}(x) - div(wast{rho})(x))f(x) dx $ for all $f in mathcal{S}$.

The real and imaginary parts of functions of the form $ f(x)=e^{-2pi xcdot{xi}}$ are in $mathcal{S}$, therefore the Fourier transform of $(uast{rho}(x) - div(wast{rho}))$ is zero, so (3) holds for any $f in Lip(mathbb{R}^d)$. Letting $rho longrightarrow delta $, we get that $L(f)=0$ for any $f in Lip(mathbb{R}^d)$, contradicting the fact that $L$ is not null.

Claim 2: $ Lip(mathbb{R}^d) = bigcup_{n in mathbb{N}} noverline{mathcal{G}}$.

Proof: Let $f in Lip(mathbb{R}^d)$. From Claim 1, there is a net ${f_lambda}_lambda$ in $mathcal{S}$ such that $f_lambda rightarrow f$. So the functionals defined as $L_lambda(w)=int_{mathbb{R}^d} w(x)cdot{nabla f_lambda(x)} dx $ for $w in L^1(mathbb{R}^d)^d$ are pointwise bounded. By the uniform boundness theorem, they are uniformly bounded. It follows that
$ sup_lambda | nabla f_lambda |_infty $
is finite, since $ | T_lambda | = | nabla f_lambda |_infty $.
Taking $ n in mathbb{N} $ sufficiently large we have $ sup_lambda | nabla f_lambda |_infty leq n $, and so $ f in noverline{mathcal{G}} $.

Claim 3: $ overline{mathcal{G}} $ is close in the strong topology (i.e.: the topology defined by the (semi) norm $|f|=_{def} | nabla f |_infty $).

Proof: Since $ L^1(mathbb{R}^d) $ is separable, the weak* topology of $ Lip(mathbb{R}^d) $ restricted to $Lip1(mathbb{R}^d) $ is metrizable; let $d$ be a metric on $Lip1(mathbb{R}^d) $ that defines the weak* topology. Let $ f $ be in the closure of $ overline{mathcal{G}} $ with the strong topology. Let $ {f_n}_n$ converge to $f $ in the strong topology, $f_n in overline{mathcal{G}} $, i.e.: $ |nabla f_n - nabla f |_infty rightarrow 0 $; in particular, $ d(f_n,f) rightarrow 0 $.
For each $n$, since $f_n in overline{mathcal{G}} $, there is $ h_n in mathcal{G} $ such that $ d(h_n,f_n) < frac{1}{n} $. Then $ d(h_n,f) leq d(h_n, f_n) + d(f_n,f) rightarrow 0$, so $ f in overline{mathcal{G}} $.

Claim 4: There is a constant $C_d$ such that
$ Lip1(mathbb{R}^d) subseteq C_doverline{mathcal{G}} $.

Proof: From Claim 2, $ Lip(mathbb{R}^d) = bigcup_{n in mathbb{N}} noverline{mathcal{G}}$. From Claim 3, for each $ n in mathbb{N}, noverline{mathcal{G}}$ is closed in the strong topology. From Baire's theorem, at least one of the sets $noverline{mathcal{G}} text{ } (n in mathbb{N}) $ has non-empty interior, i.e.: there is $n in mathbb{N}, epsilon > 0, f in Lip(mathbb{R}^d)$ such that $f + epsilon Lip1(mathbb{R}^d) subseteq noverline{mathcal{G}}$. From Claim 2, there is $a in mathbb{N}$ such that $ f in aoverline{mathcal{G}}$. Therefore,
$ Lip1(mathbb{R}^d) subseteq Coverline{mathcal{G}}$ with $ C = frac{n+a}{epsilon}$.

Finally, we can give a non-constructively answer the question in the affirmative. Since the definition of Wasserstein distance requires integration against functions in $Lip1(mathbb{R}^d)$, we assume the measures involved have finite first moment.

Claim 5: If $mu, nu $ are measures in $mathbb{R}^d$ with finite first moment, then
$ quad W_{R^d}(mu,nu)leq C_dsup_{vin R^d, |v|=1}W_{R}(mu_v,nu_v) $
where $C_d$ is the constant in Claim 4.

Proof: Let's assume first that $ mu, nu $ have densities $ u, w $ with respect to Lebesgue measure in $mathbb{R}^d $. Then
$ quad W_{R^d}(mu,nu) = sup_{f in Lip1(mathbb{R}^d)} int_{mathbb{R}^d} f(x) (u(x)-w(x)) dx leq $
$quad sup_{f in C_doverline{mathcal{G}}} int_{mathbb{R}^d} f(x) (u(x)-w(x)) dx $, by Claim 4 .

But $sup_{f in C_doverline{mathcal{G}}} int_{mathbb{R}^d} f(x) (u(x)-w(x)) dx = sup_{f in overline{mathcal{G}}} int_{mathbb{R}^d} C_d f(x) (u(x)-w(x)) dx =$
$ C_d sup_{f in overline{mathcal{G}}} int_{mathbb{R}^d} f(x) (u(x)-w(x)) dx $.
In turn,
$ sup_{f in overline{mathcal{G}}} int_{mathbb{R}^d} f(x) (u(x)-w(x)) dx =
sup_{f in mathcal{G}} int_{mathbb{R}^d} f(x) (u(x)-w(x)) dx$, since
$L(f)=int_{mathbb{R}^d} f(x) (u(x)-w(x)) dx$ is continuous in the weak* topology (2).
By definition, $mathcal{G}$ is the convex hull of functions on $mathbb{R}^d$ of the form
$f(xcdot{v}) $ with $|v|=1$ and $f in Lip1(mathbb{R})$, so
$quad sup_{f in mathcal{G}} int_{mathbb{R}^d} f(x) (u(x)-w(x)) dx = $
$quad sup_{f in Lip1(mathbb{R}), |v|=1} int_{mathbb{R}^d} f(xcdot{v}) (u(x)-w(x)) dx = sup_{|v|=1} W_{mathbb{R}}(mu_v,nu_v) $.
By continuity of the Wasserstein distance, we can pass from probability distributions with density to arbitrary distributions with finite first moments.$square$

soft question - Theorems with unexpected conclusions

My favorite example of this phenomenon is Goodstein's Theorem.

Take any positive number a₂, such as the number 73, and write it in complete base 2, which means write it as a sum of powers of 2, but write the exponents also in this way.

• a₂ = 73 = 64 + 8 + 1 = 2²²⁺² + 2²⁺¹ + 1.

Now, obtain a₃ by replacing all 2's with 3's, and subtracting 1. So in this case,

• a₃ = 3³³⁺³ + 3³⁺¹ + 1 - 1 = 3³³⁺³ + 3³⁺¹.

Similarly, write this in complete base 3, replace 3's with 4's, and substract one, to get

• a₄ = 4⁴⁴⁺⁴ + 4⁴⁺¹ - 1 = 4⁴⁴⁺⁴ + 3 4⁴ + 3 4³ + 3 4² + 4 + 3.

And so on. The surprising conclusion is that:

Goodstein's Theorem. For any initial positive integer a₂, there is n > 2 for which a_n = 0.

That is, although it seems that the sequence is always growing larger, eventually it hits zero. So our initial impression that this process should proceed to ever larger numbers is simply not correct. The proof of Goodstein's theorem uses transfinite ordinals to measure the complexity of the numbers that arise, and proves that this complexity is strictly descending with each step. Thus, it must hit zero, and the only way this happens is if the number itself is zero. One can see that we had to split up the complexity of the number somewhat in moving from a₃ to a₄, although even in this case the number did get larger. Eventually, the proof goes, the complexity drops low enough that the base exceeds the number, and from this point on, one is just subtracting one endlessly.

This conclusion is very surprising. But this theorem actually packs a one-two punch! Because not only is the theorem itself surprising, but then thee is the following surprise follow-up theorem:

Theorem. Goodstein's theorem is not provable in the usual Peano Axioms PA of arithmetic.

That is, the statement of Goodstein's theorem is independent of PA. It was a statement about finite numbers that is provable in ZFC, but not in PA.

gt.geometric topology - Heegaard genus in hyperbolic 3-manifolds

It is well known that for a closed hyperbolic 3-manifold $M$ the rank of $pi_1(M)$ is bounded above by some universal constant $K$ times the volume of $M$. Using similar methods, i.e. the thick-thin decomposition of $M$, one can also show that the Heegaard genus of $M$ is bounded above by a universal constant times the volume of $M$. (I believe that Thurston showed this first, though I am not sure as to how.)

I am looking to construct a sequence of (closed) hyperbolic 3-manifolds, say {$M_n$} such that the volume grows linearly in the Heegaard genus of $M_n$. That is, I am trying to show that a linear bounded on Heegaard genus in terms of volume is the best one can do. So far, I am having some trouble constructing such an example.

Does anyone have a good method or reference for constructing such an example? Also, another approach to the problem would be wonderful (short of solving the rank versus Heegaard genus conjecture of hyperbolic 3-manifolds, of course).

computability theory - Ackermann-related function

The key to do this is to realize the difference between computation and verification. Although computing value A(a,b) of the Ackermann function cannot be done primitive recursively, verifying whether a proposed number c is the correct value of A(a,b) can be done primitive recursively. (Note that computation and verification is also what distinguishes P and NP.)

In this case, the fact that this can be done hinges on the strong monotonicity properties of Ackermann's function. Indeed, if A(a,b) = c then all the previous values of A needed to compute A(a,b) are bounded by c. Therefore, the search for a valid computation verifying that A(a,b) = c can be bounded by a primitive recursive function B(a,b,c). Knowing this function B we can take a proposed value c for A(a,b), compute the bound B(a,b,c) and search up to this bound for a valid computation verifying that c is indeed equal to A(a,b). If no such computation is found we return 1, otherwise we return 0.

To make this a little more specific, let's say that computation for A(a,b) = c is a (coded) finite sequence of triples (a_i,b_i,c_i) which ends with the triple (a,b,c). Each such triple codes the fact that A(a_i,b_i) = c_i. The computation is valid when each such triple follows from previous triples and the rules for computing the Ackermann function. (Checking this is obviously primitive recursive.) For example a valid computation for A(1,1) = 3 is the sequence (0,1,2), (0,2,3), (1,0,2), (1,1,3).

Using the rules for computing Ackermann function and our specific method for coding finite sequences, we can compute an explicit bound B(a,b,c) on a valid computation verifying A(a,b) = c. The verification that B is primitive recursive should be straightforward if our coding of finite sequences is reasonable. Therefore, verifying A(a,b) = c can be done by a primitive recursive computation.

(The details of the last paragraph are best carried out in the privacy of one's office.)

matrices - conjugate gradient iteration

A search for "conjugate gradient singular matrix" took me to this question. While the answer is obviously given by the responses, the question can be refined: Can CG still give a working algorithm if the matrix is singular, but behaves as a symmetric positive definite form on a (large) subspace?

A standard example is given by the finite element discretization of the Neumann problem on a simply connected domain. The constant functions are both the kernel and the cokernel of the Laplacian. On functions with vanishing mean, the Laplacian is still a positive definite symmetric operator, and we would like to leverage this structure.

This is non-trivial and best our numerical method is derived from a fully analytic setting, because this might provide us the convergence analysis as well. --- This appraoch is for example elaborated in

On the Finite Element Solution of the Pure Neumann Problem
Pavel Bochev and R. B. Lehoucq
SIAM Review
Vol. 47, No. 1 (Mar., 2005), pp. 50-66
Published by: Society for Industrial and Applied Mathematics
Article Stable URL: http://www.jstor.org/stable/20453601

Apart from this canon standard example for the Laplacian, system matrices with larger kernel appear in numerical methods for the de-Rham-complex, in particular if the domain is topologically non-trivial (Finite Element Exterior Calculus, Discrete Exterior Calculus). Singular system solves are still no standard material for education in computational science. As far as I may dare to give an estimate, there is still much room for a better theory building.

gr.group theory - The maximum order of finite subgroups in $GL(n,Q)$

Feit published his paper in the proceedings of the first Jamaican conference, MR1484185. He defines M(n,K) to be the group of monomial matrices whose entries are roots of unity. M(n,Q) is the group of signed permutation matrices.

Theorem A: A finite subgroup of GL(n,Q) of maximum order is conjugate to M(n,Q) and so has order n!2^n except in the following cases... [n=2,4,6,7,8,9,10]. In all cases the finite subgroup of maximum order in GL(n,Q) is unique up to conjugacy.

He notes that the maximum order subgroups of GL(n,Z) need not be unique up to GL(n,Z) conjugacy, since Weyl(Bn) and Weyl(Cn) are GL(n,Q) conjugate but not GL(n,Z) conjugate for n>2.

Theorem B gives a similar result for the cyclotomic fields, Q(l).

Feit published other papers which were very similar, and all of them rely heavily on Weisfeiler's work. However, I believe this is the only published account of his "here is the list" preprint.

nt.number theory - Primes p for which p - 1 has a large prime factor

What are the best known density results and conjectures for primes p where p - 1 has a large prime factor q, where by "large" I mean something greater than $sqrt{p}$.

The most extreme case is that of a safe prime (Wikipedia entry), which is a prime p such that $(p - 1)/2$ is also a prime (the smaller prime is called a Sophie Germain prime). I believe it is conjectured (and not yet proved) that infinitely many safe primes exist, and that the density is roughly $c/log^2 n$ for some constant $c$ (as it should be from a probabilistic model).

For the more general setting, where we are interested in the density of primes p for which p - 1 has a large prime factor, the only general approach I am aware of is the prime number theorem for arithmetic progressions, and some of its strengthenings such as the Bombieri-Vinogradov theorem (conditional to the GRH), the (still open) Elliott-Halberstam conjecture, Chowla's conjecture on the first Dirichlet prime, and some partial results related to this conjecture. All of these deal with the existence of primes $p equiv a pmod q$ for arbitrary q and arbitrary a that is coprime to q.

My question: can we expect qualitatively better results for the situation where q is prime and $a = 1$? Also, I am not interested in specifying q beforehand, so the existence of a p such that there exists any large prime q dividing $p - 1$ would be great. References to existing conjectures, conditional results, and unconditional results would be greatly appreciated.

ag.algebraic geometry - Simplifying the definition of a geometric context using sieves?

On Pages 1-3 of Cours 2 of Toën's Master Course on Stacks, he defines the notion of a Geometric context with a rather extensive list of axioms (they take up about two pages over and above the definition of a Grothendieck topology, which isn't even included). Maybe it's just my prejudices talking, but it seems like there should be a way to simplify this definition using sieves or some other kind of functorial machinery (think about the definition of a sheaf in terms of sieves compared to the definition using the gluing axiom). The reason I ask this is that the important properties of class the geometric structure morphisms (what Toën calls $P$) allow us to define closed and open subsheaves, representable covers, atlases, etc, which all seem like things that sieves were meant to do.

Question: Can we simplify the statements of those axioms using sieves or some other kind of functorial machinery? If not, why not?

Edit: I just remembered that "geometric morphism" already means something else, so I've replaced it. "The name 'geometric structure morphism' is a word that I coined myself, spending a week thinking of nothing else."

mp.mathematical physics - What's algebraic approach to QM good for?

If you want to consider quantum statistical physics properly this approach is necessary. The KMS condition gives a generalization of the quantum Gibbs postulate that allows for the treatment of phase transitions, coexistence of multiple phases, etc.

The functional-analytic approach is also important for other reasons (besides the rigged Hilbert space that is necessary even to understand a free particle): Fock space depends on it, as does axiomatic quantum field theory, and pages 12-13 of Bratteli and Robinson v.1 give some quick background to the KMS approach (both volumes are worth looking at). A book by Sewell called Quantum mechanics and its emergent macrophysics also gives quite a bit of relevant physical background.

BTW, the KMS condition is not as obscure as it might at first seem (the Wikipedia article is one of the few places I recall seeing that demystifies it). In the Heisenberg picture observables evolve under the time evolution map

$tau_t : A mapsto e^{iHt/ hbar}Ae^{-iHt/ hbar}.$

The appropriate generalization of the classical Gibbs rule is

$langle A rangle = Z^{-1}mbox{Tr}(e^{-beta H} A), quad Z := mbox{Tr}(e^{-beta H}).$

To see this, consider the projection observable $Pi_k := lvert k rangle langle k rvert$. We have that

$langle Pi_k rangle = Z^{-1}mbox{Tr}(e^{-beta E_k} lvert k rangle langle k rvert) = Z^{-1}e^{-beta E_k}$

in accordance with classical statistical physics. Now for generic observables $A$ and $C$, we have that

$left langle tau_t(A)C right rangle = Z^{-1}mbox{Tr}(e^{-beta H} e^{iHt/hbar}Ae^{-iHt/hbar}C)$

$= Z^{-1}mbox{Tr}(Ce^{iH(t+ihbarbeta)/hbar}Ae^{-iHt/hbar})$

$= Z^{-1}mbox{Tr}(Ce^{iH(t+ihbarbeta)/hbar}Ae^{-iH(t+ihbarbeta)/hbar}e^{-beta H})$

$= left langle Ctau_{t+ihbarbeta}(A) right rangle$

which gives the KMS condition:

$left langle tau_t(A)C right rangle = left langle Ctau_{t+ihbarbeta}(A) right rangle.$

ac.commutative algebra - When is every submodule pure?

Hmmm, I seem to have found the answer to this question. In

Regular and semisimple modules

by Cheatham and Smith in 1976, they call a module regular if every submodule is pure. Regular is of course an overused word, and maybe other people have called this different things. But the justification makes some sense: if I is a 2-sided ideal of R, then R/I is a regular R-module if and only if R/I is a von Neumann regular ring.

set theory - Does the Continuum Hypothesis hold for sets of a certain rank?

Adding to the previous answers: Note that $V_{aleph_omega}$ is not a model of ZFC.
Hence, what holds or not in $V_{aleph_omega}$ does not formally tell you what follows from ZFC and what doesn't. This issue aside, as mentioned above, $V_{aleph_omega}$ knows whether or not CH holds in the real world.

What Gödel did to show the consistency of CH was to construct a "narrow" class $L$ inside a model of ZFC (resp. ZF if you also want to also prove the consistency of AC with ZF) such that
$L$ satisfies ZFC+CH. The point here is that even if CH fails in the large model of set theory, $L$ contains so few subsets of $omega$ that CH actually holds (roughly).

So, L is narrow, while $V_{aleph_omega}$ is short and wide (it contains all set up to a certain rank). A short wide structure (as long it is long
enough) is correct about CH, a narrow structure might not be.

na.numerical analysis - Finding the local/global minima of Shubert function

At Jacques' cajoling, I'm turning the comments into an answer.

The two dimensional Shubert function is just the product of the one dimensional one by itself. $f(x,y) = g(x)g(y)$ where $g(x) = sum_{j = 1}^5 j cos( (j+1)x + j)$ is the 1 dimensional Shubert function. Observe that the local maxima are all positive, and the local minima all negative. So the minima for $f(x,y)$ occur at points ${(x,y) : g'(x)= g'(y) = 0, f(x,y) < 0}$. In other words, the minima of $f$ occurs at points where a maximum of $g$ is multiplied against a minimum.

Notice that there are 3 global max/min each of $g$ in the interval (-10,10), and 19 max and 20 min overall. This produces the 760 total local min of $f$ with 18 of them being global. (760 = 2 * 19 * 20, 18 = 2 * 3 * 3)

To find the extrema of the 1-d Shubert function, you evaluate its first derivative, and find that it can be simplified to a degree 6 polynomial in $sin(x)$ and $cos(x)$ by using the angle addition formulae. I have not evaluated the computations myself, so cannot tell you whether the expression has a closed-form algebraic solution.

st.statistics - Calculating the "Most Helpful" review

David Eppstein suggests a Bayesian method in his comment. One standard thing to do in this situation is to use a uniform prior. That is, before assessments of a review come in, its probability $p_i$ of being helpful is assumed to be uniformly distributed on [0, 1]. Upon receiving each assessment of the review, apply Bayes' theorem.

This sounds complicated, and it would be for an arbitrary prior distribution. But it turns out that with the uniform prior, the posterior distributions are all beta distributions. In particular, the expected value of $p_i$ after s positive assessments and n-s negative ones is (s+1)/(n+2). This is Laplace's rule of succession, and proofs of the facts I've mentioned can be found in that Wikipedia article. Then one would sort on the score (s+1)/(n+2).

The constants "1" and "2" come from the use of a uniform prior, and don't actually give the same results as the sample data you provide. But if you give a review that s out of n people have said to be helpful the score (s+3)/(n+6), then your reviews have scores

7 of 7: 10/13 = 0.769...

21 of 26: 24/32 = 0.75

9 of 10: 12/16 = 0.75

6 of 6: 9/12 = 0.75

8 of 9: 11/15 = 0.733

5 of 5: 8/11 = 0.727

7 of 8: 10/14 = 0.714

12 of 15: 15/21 = 0.714

This essentially amounts to sorting by the proportion of positive assessments of each review, except that each review starts with some "imaginary" assessments, three positive and three negative. (I don't claim that (3,6) is the only pair of constants that reproduce the order you give; they're just the first pair I found, and in fact (3k, 4k+2) works for any $k ge 1$.)

schemes - Properties stable under base change in algebraic geometry

I remember to have seen a big list in the EGA of properties $(P)$ such that:
if $f : X to Y$ has $(P)$ then, $f_{(S')} : X_{(S')}to Y_{(S')}$ has $(P)$, where $f_{(S')}$ is the morphism $f$ after a base change $S'to S$., etc. but I can't find it now...

Does anyone know where I can find such a list ?

(I am interested by $(P)$ = "to be a closed map")

ct.category theory - Effects of "weak" vs. "strict" categories in Eckmann-Hilton arguments

Here is a nice pictorial proof of the Eckmann-Hilton argument in a higher category (made by Eugenia Cheng). One way to read this is as a proof that in a weak 2-category with one 0-cell and one 1-cell, the composition of 2-cells is commutative: in this case each diagram is equal to the two diagrams next to it, either by a unit law or by an interchange law.

Alternately, we can read it as a proof that in a weak 3-category with unique 0- and 1-cells, the composition on 2-cells is braided. In this case each diagram is isomorphic to those next to it, via either a unit isomorphism or an interchange isomorphism. The braiding is the composite isomorphism along the top half (say), and the fact that it isn't a symmetry arises because the composite all the way around need not be the identity.

Of course, if both interchange and unit isomorphisms were to be identities, the braiding would be a symmetry. It is known in dimension 3 that it's actually good enough (i.e. things don't collapse and become too strict) if either the unit or interchange law is weak, and the other is strict. If interchange is weak but the unit is strict, we get Gray-categories as in the original Gordon-Power-Street paper on tricategories, while if the interchange is weak but the unit is strict, this is the subject of Simpson's conjecture as mentioned by David (for the n=3 case, see here). Note that associativity never enters the picture at all, and at least in dimension 3 it can also be made strict.

There isn't really a "one step" that we want to fail. In a "fully weak" higher category, all of the associativity, unit, and interchange laws would hold only weakly. It so happens that such fully weak categories can be "semi-strictified" to make some, but not (in general) all, of these laws hold strictly, while still being equivalent to the original category in a suitable sense. Such semistrictification can often be technically useful, but I don't regard it as really of foundational importance.

Regarding "intuition for what higher-dimensional coherence isomorphisms we should refrain from demanding to exist," I think it's misleading to view this example in that way. There isn't really a coherence isomorphism that we're refraining from demanding to exist---in a weak 3-category, it's still the case that all coherence isomorphisms exist and all "formally describable" diagrams commute. Rather, what's happening is that accidentally, if we happen to be considering cells whose source and target are both identities, then there are some structural isomorphisms that we happen to be able to compose in a way "unforeseen" by the general theory of weak n-categories. Therefore, in this particular case, the assertion of that general theory that "all diagrams commute" doesn't apply, since the diagram we're looking at is only well-defined by accident. This is kind of vague, but it can be made precise by the theory of contractible globular operads, where it is true that "all diagrams commute" in the formal, operadic, sense, but in some particular algebra over such an operad, there may be accidental "composites" which do not commute. See also this question.

Linear space of translatable functions.

The question, as stated, is about the set of multiples of translates, but from the example quoted, $sin x,$ I suspect that OP really meant the span.

Theorem Let $f$ be a continuous complex-valued function on $mathbb{R}.$ Then the following conditions are equivalent:

1. The translates ${f(x+b) : binmathbb{R}}$ span a finite-dimensional vector space;




2. $f$ satisfies a homogeneous constant coefficient linear differential equation;




3. $f$ is a finite linear combination of functions $f_{k,lambda}(x)=x^k e^{lambda x}.$

Proof. If $f$ is assumed infinitely differentiable then all derivatives of $f$ belong to the $mathbb{R}$-span of translates of $f.$ Thus condition 1 implies that $f$ and its derivatives of order up to $n$ are linearly dependent over $mathbb{R},$ which is condition 2. The smoothness assumption may be removed by using the Fourier or Laplace transform.

The equivalence of conditions 2 and 3 is a basic fact of ODEs. Finally, a direct computation shows that $f_{k,lambda}(x)$ spans the $(k+1)$-dimensional vector space ${P(x)e^{lambda x}: Ptext{ is a polynomial of degree} leq k}$, so condition 3 implies condition 1. $square$

---

Condition 1 – 3 have the following representation-theoretic interpretation. The additive group of $mathbb{R}$ acts on itself by the right multiplication. This gives rise to a linear representation of $mathbb{R}$ on the functions on $mathbb{R}$ via translations called the right regular representation, and condition 1 states that $f$ belongs to a finite-dimensional subrepresentation $V$. Finite-dimensionality of $V$ implies that $V$ contains an irreducible subrepresentation $W$, which must be one-dimensional (Schur's lemma), hence $W$ is spanned by a character of $mathbb{R}.$ All continuous characters are the exponential functions $e^{lambda x}$ for various $lambdainmathbb{C}$; however, using a Hamel basis of $mathbb{R},$ it is easy to see that there are uncountably many others.

Condition 2 is the Lie algebra analogue of condition 1: viewing $mathbb{R}$ as a one-dimensional Lie group, the content of Lie's theorem is that its finite-dimensional (continuous) representations correspond (by differentiation and exponentiation) to f.d. representations of the abelian one-dimensional Lie algebra, i.e. to a single linear transformation on $V.$ The span $V_{n,lambda}$ of the functions $f_{k,lambda}$ with $0leq kleq n-1$ from condition 3 is an $n$-dimensional indecomposable representation of $mathbb{R},$ whose infinitesimal version is a Jordan block of order $n$ with $lambda$ on the diagonal. Moreover, any subrepresentation isomorphic to $V_{n,lambda},$ i.e. corresponding to the same Jordan block, must be $V_{n,lambda}$ itself.

ca.analysis and odes - A sequential optimizing task

I have enough musings to post them as an answer, rather than fill
up comment space.

First : Use a simple recursive construction to get
an upper bound on the supremum. This places x_1 at 1,
x_2n at x_n - 1/2n, and x_(2n+1) at x_n + 1/(2n+1). This
gives an upper bound of sum{i positive integer} 1/(2^i - 1)
which is some number less than 169/105. Of course, you need
to prove this construction works.

Second: viewed as a tree with node n branching to children
x_(2n) and x_(2n+1), note that you can prune and graft the
tree, reshaping it as needed. Specifically, start by
exchanging branches at nodes 11 and 7. (This works because
1/2 + 1/5 + 2/7 < 2* 1/2 = 1.) You may find that repruning
smaller branches leads more quickly to a near optimal bound.
Even with the one graft made, the upper bound is reduced to
less than 1147/759.

Third: start determining optimal placements for the first
n terms for small n, which meet the conditions and stay
below the bounds established above. A computer
simulation should quickly run through placements for n
up to 12 which stay below the lower bound. For example,
by hand one sees that x_1 < x_2 < x_n for n < 80 already
leads to non optimal placements, so that combined with
some analysis should prove that x_2 < x_1 in an optimal
placement.

This approach should lead you quickly to the first four
decimal digits of the supremum.

UPDATE 07.11 : I have what I think are two tools
to tackle the problem. The first tool is the bounded width
branch: Given n, form the branch suggested above starting
with x_n "representing" 1/n, placing x_2n at x_n - 1/2n and
x_2n+1 at x_n + 1/(2n+1), and continuing recursively. The
actual tool is the lemma that this branch meets the criteria
for extending the sequence and does so using up at most 2/n
space, and actually at most 1/n + 1/(2n+1) + 1/(4n+3) + ... .

Formally the lemma should read: Let for j in S be
the subsequence described above, where n in S is given
and for k in S one has both 2k and 2k+1 in S, and no other
integers or objects are in S otherwise. This subsequence
can be part of a sequence that satisfies the spacing
criterion given in the problem, and max(x_i - x_j) for
i,j coming from S is less than 2/n.

The second tool is that, given any starting sequence,
there is a way to extend it using bounded width branches
to get a solution. Formally: Let for m <= M be
a finite subsequence which satisfies the spacing criterion
given. Then there are M+1 bounded width branches that can
be grafted on to the sequence, given a complete sequence
that also satisfies the spacing requirements.

Proof sketch: start with x_M, and place x_2M and x_2M+1
adjacent to it. Then go backwards up to x_M+1, placing
bounded width branches in the space next to the smallest
undecorated leaf. The spacing requirements guarantee that
the branches will fit without needing to move any of the
first M x_i . Also, show that the branches aren't close
enough to each other to conflict with the spacing requirement.

So for any suitable sequence of length M, one can extend
it to a complete suitable sequence at a cost of at most
2/(M+1). Now with this estimate, one can go through the
first few finite sequences and weed out those that are
provably nonoptimal.

END UPDATE 07.11

Gerhard "Ask Me About System Design" Paseman, 2010.07.08

ct.category theory - Adjunctions: Algebras of the induced monad VS. Coalgebras of the induced comonad.

No, they are not generally equivalent. Suppose for example $U: C to D$ is monadic; this means $U$ has a left adjoint $F: D to C$ such that the canonical comparison functor $C to Alg(UF)$ is an equivalence, so that $C$ "is" in effect the category of algebras and $U$ is the forgetful functor. Then you'd be asking whether $Coalg(FU)$ is equivalent to $Alg(UF)$, i.e., whether $C$ is equivalent to the category of $FU$-coalgebras over $C$.

For a simple example where this fails, take $C = Set^G$ (category of sets equipped with an action of a group $G$), and $U: Set^G to Set$ the forgetful functor. The left adjoint is $G times -: Set to Set^G$, and one may check that the category of coalgebras is equivalent to $Set$. But $Set$ and $Set^G$ are not equivalent (e.g., $Set^G$ has lots of indecomposable objects given by transitive actions).

There is a fairly large class where the canonical comparison functor $Coalg(FU) to Alg(UF)$ is an equivalence, namely when either $U$ is fully faithful or $F$ is fully faithful. This occurs for example when $C$ and $D$ are posets [edit: this obviously includes the algebraic geometry situation you were considering], and for various "completion processes" (such as sheafification, or taking Cauchy completions on the category of metric spaces and contractive maps, among many others).

One might inquire whether or under what circumstances adjunctions $F dashv U$ lift to adjunctions $Coalg(FU)$ and $Alg(UF)$. This ought to be easy to investigate, but just now my children are rattling around and I'm finding it difficult to concentrate. :-)

Edit, now that my children have quieted down: there seems to be no reason for there to be an adjunction between $Coalg(FU)$ and $Alg(UF)$ in general: one can write down various functors in either direction, but I don't see any adjoint pairs cropping up this way.

One interesting situation where there is an equivalence between a category of coalgebras and a category of algebras is where a monad has a right adjoint. One may then exhibit a canonical comonad structure on this right adjoint, such that its category of coalgebras is canonically equivalent to the category of algebras of the original monad. This comes up in topos theory, for example, where for a category of presheaves $Set^{C^{op}}$, the evident forgetful functor $Set^{C^{op}} to Set^{Ob(C)}$ is both monadic and comonadic.

sequences and series - Existence of convergent subsequences for all values in range?

Consider sequence $s(n) = sin{nx}$. Are there values of $x$ for which the following holds: For every $y in [-1,1]$ there is a subsequence of $s(n)$ converging to $y$? (Or perhaps just for the open interval...) Someone hypothesised that the answer is yes, and further that every $x$ that is relatively irrational with $pi $ has this property.

The question I am more interested in is the generalised version of this to arbitrary sequences. What are necessary and sufficient conditions for a sequence having subsequences converging to any point in the set of values the sequence visits? Does it have anything to do with properties like the function $f(n)$ being ergodic or mixing?

(suggestions for tags welcome in comments)

rt.representation theory - Octonionic Unitary Group?

As others have pointed out, the nonassociativity of the octonions prevents one from constructing a group. For example, any subgroup of the octonions lives inside of a quaternion subalgebra. Having said that, the Clifford algebra $Cl(mathbb{R}^7)$ has two inequivalent irreducible representations which are each as real vector spaces isomorphic to the octonions (i.e., they are eight-dimensional) and provided that we identify $mathbb{R}^7$ with the imaginary octonions, the action of $Cl(mathbb{R}^7)$ is given by left and right octonionic multiplications. This is analogous to what happens with $Cl(mathbb{R}^3)$ substituting octonion for quaternion in what I said above. Now the Spin group $Spin(3)$ is the one-dimensional quaternionic unitary group and lives naturally inside $Cl(mathbb{R}^3)$, so one could think of the group $Spin(7)$ as being the analogue of the one-dimensional octonionic unitary group.

By the same token, and given the low-dimensional isomorphisms
$$Spin(2,1) cong SL(2,mathbb{R})$$
$$Spin(3,1) cong SL(2,mathbb{C})$$
$$Spin(5,1) cong SL(2,mathbb{H})$$
one would be tempted to think of $Spin(9,1)$ as $SL(2,mathbb{O})$, even though such a group as written does not exist.

lo.logic - Why are universal introduction and existential elimination valid inference rules?

You are getting tripped up by some very traditional, yet very bad, notation.

The $k$ in these formulas are not true constants of the domain of individuals, but rather are Skolem constant. The idea is that if we have, say, the knowledge that an existential formula $exists x. theta(x)$ is true, we can treat it as if it were the formula $theta(k)$, where $k$ is some particular arbitrary constant about which we know nothing. Conversely, if we know that $theta(k)$ holds for any arbitrary constant $k$, then we can conclude $forall x.; theta(x)$. These made-up constants are called Skolem constants.

If we explicitly manage the free variables with a context of free variables $Gamma$, then the introduction and elimiantion rules look the way you expect, and agree with Andrej Bauer's rules.

$$frac{Gamma; Sigma vdash forall x.theta(x) qquad FV(t) subseteq Gamma}
{Gamma; Sigma vdash theta(t)}$$

$$frac{Gamma, x; Sigma vdash theta qquad qquad x notin FV(Sigma)}
{Gamma; Sigma vdash forall x.; theta}$$

dg.differential geometry - Point singularity of a Riemannian manifold with bounded curvature

Suppose you have an incomplete Riemannian manifold with bounded sectional curvature such that its completion as a metric space is the manifold plus one additional point. Does the Riemannian manifold structure extend across the point singularity?

(Penny Smith and I wrote a paper on this many years ago, but we had to assume that no arbitrarily short closed geodesics existed in a neighborhood of the singularity. I was never able to figure out how to get rid of this assumption and still would like someone better at Riemannian geometry than me to explain how. Or show me a counterexample.)

EDIT: For simplicity, assume that the dimension of the manifold is greater than 2 and that in any neighborhood of the singularity, there exists a smaller punctured neighborhood of the singularity that is simply connected. In dimension 2, you have to replace this assumption by an appropriate holonomy condition.

EDIT 2: Let's make the assumption above simpler and clearer. Assume dimension greater than 2 and that for any r > 0, there exists 0 < r' < r, such that the punctured geodesic ball B(p,r'){p} is simply connected, where p is the singular point. The precludes the possibility of an orbifold singularity.

ADDITIONAL COMMENT: My approach to this was to construct a differentiable family of geodesic rays emanating from the singularity. Once I have this, then it is straightforward using Jacobi fields to show that this family must be naturally isomorphic to the standard unit sphere. Then using what Jost and Karcher call "almost linear coordinates", it is easy to construct a C^1 co-ordinate chart on a neighborhood of the singularity. (Read the paper. Nothing in it is hard.)

But I was unable to build this family of geodesics without the "no small geodesic loop" assumption. To me this is an overly strong assumption that is essentially equivalent to assuming in advance that that differentiable family of geodesics exists. So I find our result to be totally unsatisfying. I don't see why this assumption should be necessary, and I still believe there should be an easy way to show this. Or there should be a counterexample.

I have to say, however, that I am pretty sure that I did consult one or two pretty distinguished Riemannian geometers and they were not able to provide any useful insight into this.

graph theory - Complete tree invariants?

If we take a graph invariant to be "a property that depends only on the abstract structure, not on graph representations such as particular labellings or drawings of the graph" (from Wikipedia), I have the feeling that Harrsion's question for complete graph invariants remained basically unanswered, since Greg's answer is mainly about (canonical) labellings.

Thinking - as Harrison did - of "the usual ones (the Tutte polynomial, the spectrum, whatever)", I'd like to repeat Harrison's question, but restrict it to trees:

Are there any known complete tree invariants?

gr.group theory - References on functorially-defined subgroups

I'm interested in results about functorially-defined subgroups (in a loose sense), especially in the non-abelian case, and would like to know about references I may have missed.

The question, it seems, comes up in its simplest form when noticing a number of common subgroups (the center, commutator subgroup, Frattini subgroup, etc) are characteristic. The characteristicity can be justified by the fact that the object mappings that define of those subgroups give rise to subfunctors of the identity functor, on the core category of Grp.

Hence I'm interested in functors F in Grp (or a carefully chosen sub-category) such that

∀ A F(A) ⊆ A and ∀ A,B ∀ f ∈ hom(A, B), f(F(A)) ⊆ F(B)

Does that ring a bell ?

The topic was mentioned a couple of months ago on Mathoverflow, and can be traced back to (at least) 1945, where Saunders MacLane explains it in some detail in the third chapter of A General Theory of Natural Equivalences.

In between, it seems that those functors have been baptised radicals, pre-radicals or subgroup functorials, and studied mostly in the framework of ring theory, notably by A. Kurosh. Among a number of not-so-recent (and therefore quite-hard-to-find) papers mostly dealing with rings, semigroups, or abelian groups, I came across a single reference mentioning the non-abelian case, by B.I. Plotkin : Radicals in groups, operations on classes of groups, and radical classes. Connections seem have been made with closure operators¹, but do not focus much on Grp.

• Do you have ideas of connections from those functors to other parts of algebra or category theory, other than (pre-)radicals ?


• Do you have some pointers to material I may have missed, specially if they mention non-abelian groups ?

¹: Categorical structure of closure operators with applications to topology
By N. Dikranjan, Walter Tholen, p.51

ag.algebraic geometry - The meaning of ${infty}^{k}$.

When we say, that, say, a surface contains ${infty}^{k}$ lines, do we mean that it contains a k-parameter family of lines? Do we assume that this family is parametrized by a $P^{k}$, say, or we use this term more informally?
This is certainly a standard notation, but I didn't see its explanation in standard modern textbooks.

nt.number theory - Least number of non-zero coefficients to describe a degree n polynomial

You might have a look at Polynomial Transformations of Tschirnhaus, Bring and Jerrard. It gives more explicit detail on why you can remove the first three terms after the leading term (covering the cases of degree 5 and 6 you mention above), but it does concentrate on degree 5.

Hamilton's 1836 paper on Jerrard's original work has an elementary explanation of the technique (much of the paper concentrates on showing that certain other reductions Jerrard proposed, including a general degree 6 polynomial to a degree 5, were "illusory"). It also explains Jerrard's trick for eliminating the 2nd, 3rd and 5th terms. Finally, Jerrard has a method for eliminating the second and fourth terms, while bringing the third and fifth coefficients into any specified ratio: this only works in degree 7 or above (Jerrard had mistakenly thought this worked generally, and thus solved the general quintic by reducing it to de Moivre's solvable form -- this all predates Abel's work!)

If by "Bring-Jerrard" form you just mean a certain number of the initial terms (after the first) have been eliminated, then the Hamilton numbers you linked to are indeed exactly what you want.

gt.geometric topology - Branched covering vs Covering space of 0-surgery manifold ??

Let $K$ be a knot in $S^3$ and $M^3$ be a 3-manifold obtained by 0-surgery from $S^3$ along $K$. By using Mayer-Vietoris sequence, we can see that $H_i(M^3)=H_i(S^1times S^2)$. Therefore, we have a surjection from $pi_1(M^3)to H_1(S^1times S^2)=mathbb{Z}$ and for $n>0$, we have n-fold cyclic covering of $M$, say $M_n$.

On the other hand, by using collar neighborhood of Seifert surface in $S^3$, we can make a n-fold branched cyclic covering of $S^3$ over $K$, say $L_n$.

To extract more information by using local coefficient system, we have given a character $phicolon pi_1(L_n)to mathbb{Z}_m$. (For convenience, $m$ and $n$ are prime-power order.)

These two 3-manifolds, $M_n$ and $L_n$ can be used to study knot $K$. Since $Omega(K(mathbb{Z}_m,1))=mathbb{Z}_m$ is torsion group, $rL_n=partial W_n$ and over $mathbb{Z}_m$ for some $r>0$ and some 4-manifold $W_n$.

I feel that concrete understanding on intersection form of $W_n$ is needed and important.

1. Is it true that can we obtain a $V_n$ from $W_n$ by attaching $r$ 2-handle, where $V_n$ satisfies $partial V_n= rM_n$ over $mathbb{Z}_m$ ?




2. What is the difference of intersection form on $H_2(V_n;mathbb{Q})$ and $H_2(L_n;mathbb{Q})$? ($V_n$ is a 4-manifold satisfying condition in Question 1. i.e.)$partial V_n=rM_n$.




3. How about $H_2(V_n;mathbb{Q}(mathbb{Z}_m))$ and $H_2(L_n;mathbb{Q}(mathbb{Z}_m))$? Here I'm using homology with local coefficients.




4. What is the influence of different choice of $W_n$ on intersection form ?
   (i.e. Both $W_n$ and $W_n'$ satisfies $partial W_n= rL_n$ and $partial W_n' = rL_n$.) How much different that intersection form on $H_2(W_n;mathbb{Q})$ and $H_2(W_n';mathbb{Q})$ ?

Please give me any detailed references, if any.

nt.number theory - Integral expression for zeta(2)

The starting point is the integral

$$
Gamma(s) = int_{0}^{infty}e^{-x}x^{s-1}dx
$$

for the gamma function. Make the change of variable $x = nu$ with $n$ an arbitrary positive integer. Then

$$
Gamma(s)n^{-s} = int_{0}^{infty}e^{-nu}u^{s-1}du
$$

and summing over $n$ from $n = 1$ yields

$$
Gamma(s)zeta(s) = int_0^{infty}frac{1}{e^u - 1}u^{s-1}du.
$$

This formula was the starting point of one of Riemann's two proofs of the functional equation. I am not certain who discovered it first, but it may have been Abel.

Substituting $s = 2$ gives

$$
zeta(2) = int_{0}^{infty}frac{u}{e^u - 1}du
$$

and so

$$
zeta(2) =
int_{0}^{infty}frac{ue^u}{e^{2u} - e^u}du =
int_{0}^{infty}frac{u(e^u - 1) + u}{e^{2u} - e^u}du =
int_{0}^{infty}left(ue^{-u} + frac{u}{e^{2u} - e^u}right)du =
1 + int_{0}^{infty}frac{u}{e^{2u} - e^u}du.
$$

tag removed - is there a name for this type of function ?

The class of functions you are describing are known as recursive. For example, the $sum$ function has the following recursive definition:

$sum(x_1) = x_1$

$sum(x_1, x_2, cdots x_{n-1}, x_n) = sum(x_1, x_2, cdots, x_{n-1}) + x_n$.

In this particular situation it was sufficient to know what $sum(x_1, x_2, cdots, x_{n-1})$ is to quickly compute $sum(x_1, x_2, cdots, x_{n-1}, x_n)$. However, in many other situations to compute $f(x_1, cdots x_n)$ you must know the solution to a large number of subproblems of $f$ to be able to compute $sum(x_1,cdots, x_{n})$ quickly. For example, $f$ may be defined recursively as:

$f(x_1) = g(x_1)$

$f(x_1, cdots, x_n) = f(x_1,x_2, cdots x_{frac{n}{2}}) + f(x_{frac{n}{2}+1}, cdots, x_n)$

A general technique from computer science that can be used to compute such functions is dynamic programming. Essentially a table is constructed that stores the solution to all subproblems (or perhaps just some subset of the subproblems which will be needed later) to the original. Since the solution to larger subproblems is constructed using the solutions to smaller subproblems you construct this table in order of increasing size.

EDIT: Dynamic programming is typically used when the solutions to the subproblems needed to compute $f(x_1, cdots, x_n)$ overlap. If they do not overlap a simple recursive definition will usually be simpler.

gn.general topology - What is the "right" universal property of the completion of a metric space?

I'm a little embarrassed to ask this one, but it could help for a class I'm teaching, so here goes:

Let $X$ be a metric space. We all know that $X$ admits a completion, which is a complete metric space $hat{X}$ together with an isometric embedding $iota: X hookrightarrow hat{X}$ with dense image. Moreover, one learns that this completion is essentially unique.

From a modern perspective, one would like to realize the completion as satisfying some universal mapping property: this makes precise the "essentially unique" above and gives some functorial properties. But it seems to me that the completion satisfies two different such properties:

1) It is universal with respect to isometric embeddings into complete metric spaces.

2) It is universal with respect to uniformly continuous maps into complete metric spaces.

Of course 1) is the more obvious one. I gather from some internet research that 2) is supposed to be the "right" choice, and its usefulness is related to the fact that uniformly continuous maps have the extension property (again, I don't quite remember this from my undegraduate days; is it in Rudin's Principles, for instance?). However, it seems strange to me that by taking 2), we also get for free that the mapping $iota$ is an isometric embedding (in particular, from 2) it doesn't even seem completely obvious that it is injective). Certainly one can see this by constructing the completion, but is there a more direct way?

I suspect that this is an instance when the more categorical thinkers have one up on me, and I stand ready to be enlightened.

at.algebraic topology - Is the topological concept of collapsible useful?

To add a little to Ryan's answer:

This topic is maybe not exactly a part of algebraic topology. It's more like an area of application of algebraic topology to certain important special classes of spaces.

When $A$ is a subcomplex of $B$ (both of them finite) and $B$ collapses to $A$, then the inclusion map $Ato B$ is said to be a simple homotopy equivalence, as is any left inverse of such an inclusion, and more generally any map between finite complexes that is homotopic to a composition of such things. A homotopy equivalence $Ato B$ between finite complexes determines an element of the Whitehead group $Wh(G)$ of the fundamental group $G=pi_1(A)$ (a certain abelian group that depends functorially on $G$ -- the quick definition is take the direct limit of $GL_n(Z[G])$ as $n$ goes to infinity, abelianize, and kill the the invertible $1times 1$ matrices $gin G$ and $-1$). It is simple if and only if this element is zero. (Sometimes the latter is taken as definition of simple.) The group $Wh(1)$ is trivial, so every homotopy equivalence between simply-connected finite complexes is simple. The house with two rooms shows that the inclusion of a subcomplex can be simple even if there is no collapse; there is a larger complex collapsing both to the house and to the point.

The question of whether a homotopy equivalence is simple is unchanged by subdivision of a complex, so sometimes you can prove that a given homotopy equivalence is not homotopic to any simplicial or cellular isomorphism by proving that it has nontrivial Whitehead torsion. If you can enumerate all the (homotopy classes of) homotopy equivalences from $A$ to $B$ and you find that all of them have nontrivial torsion, then the spaces are really different. Eventually the topological invariance of Whitehead torsion was proved, making for stronger statements.

$Wh(G)$ is trivial for lots of (potentially for all) torsion-free groups $G$, but is usually nontrivial for finite $G$.

gn.general topology - Are all Hawaiian Earrings homeomorphic?

Mariano is absolutely right. [And so, for the record, is Joel.]

Coincidentally, an equivalent question came up on the blogosphere in late 2008, and I answered it. The original website is

http://mathphdthoughts.blogspot.com/2008/09/hawaiian-earring.html

Here is my post on that page:

---

In order to understand the difference [between the Hawaiian earring and the wedge of circles, that is -- 1/5/10] you need to look explicitly at the definition of the topology on a CW-complex with infinitely many cells. By definition, this is the direct limit over the topologies of the subcomplexes with only finitely many cells.

In other words, a subset of the CW complex is open iff its intersection with each individual cell is open. (Another way of saying this is that this is the strongest topology on the entire complex such that each of the inclusion maps from the cells is continuous. This is an instance of a "final topology." Why it is also sometimes called a "weak topology" is not so clear to me: the only reasonable explanation is that the meanings of 'weak' and 'strong' used to be the reverse of what they now are, which I believe is unfortunately the case.)

Anyway, to compare the Hawaiian earring to the infinite bouquet of circles, look at the neighborhood bases of the central point P. On the Hawaiian earring, any open set containing P must contain the entire nth circle for all sufficiently large n, and for the remaining finitely many circles must contain an open interval about P on that circle. However, on the bouquet of circles, the neighborhoods of P are exactly the subsets which contain an open interval around P on each circle. This is a much larger collection of neighborhoods, and indeed the CW-topology is strictly finer than the earring topology.

From this it is easy to see that the CW-topology is not compact, in any number of ways:

(i) Find a closed, discrete infinite subset.

(ii) Note that it is Hausdorff and apply the fact (which can be found in Rudin's Real and Complex Analysis) that any two compact Hausdorff topologies on the same set are incomparable.

(iii) Convince yourself that any CW-complex is compact iff it has finitely many cells.

---

This generated some discussion on John Armstrong's blog:

http://unapologetic.wordpress.com/2008/09/12/hawai%ca%bbian-earrings/#comments

The very last comment mentions that the earring as the one-point compactification of a countably infinite disjoint union of open intervals. This is a nice observation, the more so since it's completely obvious: the earring is a closed, bounded subset of the Euclidean plane, hence compact. Remove the central point from it and you do indeed get an infinite disjoint union of open intervals. (And, of course, the one-point compactification of a locally compact Hausdorff space is unique up to unique isomorphism.)

This makes clear that the homeomorphism type of the earring does not depend on the radii of the circles -- so long as they converge to 0, of course. (Note that the monotonicity is a superfluous hypothesis. If a sequence converges to $0$, you can reorder it so as to be monotonically decreasing, and the resulting subset of the plane can't tell the difference.)

co.combinatorics - Applications of infinite Ramsey's Theorem (on N)?

Beyond the infinite Ramsey's theorem on N, there is, of course, a kind of super-infinite extension of it to the concept of Ramsey cardinals, one of many large cardinal concepts.

Most of the large cardinal concepts, including Ramsey cardinals, generalize various mathematical properties of the countably infinite cardinal ω to uncountable cardinals. For example, an uncountable cardinal κ is a Ramsey cardinal if every coloring of finite subsets of kappa into 2 colors (or indeed, less than κ many colors) admits a homogeneous set of size κ. Such cardinals are necessarily inaccessible, Mahlo, and much more. The somewhat weaker property, that every coloring of pairs (or for any fixed finite size) from κ to 2 colors has a homogeneous set, is equivalent to κ being weakly compact, a provably weaker notion, since every Ramsey cardinal is a limit of weakly compact cardinals. Similarly, the concept of measurable cardinals generalize the existence of ultrafilters on ω, for an uncountable cardinal κ is said to be a measurable cardinal if there is a nonprincipal κ-complete ultrafilter on κ.

Ramsey cardinals figure in many arguments in set theory. For example, if there is a Ramsey cardinal, then V is not L, and Ramsey cardinals are regarded as a natural large cardinal notion just exceeding the V=L boundary. Another prominent result is the fact that every measurable cardinal is Ramsey (which is not obvious from first notions). Further, if there is a Ramsey cardinal, then 0^# exists. Indeed, this latter argument proceeds as a pure Ramsey style argument, using a coloring. Namely, if κ is Ramsey, then we may color every finite increasing sequence of ordinals with the type that they realize in L. By the Ramsey property, there must be a set of size κ, all of whose increasing finite subsequences realize the same type. That is, there is a large class of order indiscernibles for L. By results of Silver, this is equivalent to the assertion that 0^# exists.

The fact that Ramsey cardinals are strictly stronger than weakly compact cardinals suggests to my mind that there is something fundamentally more powerful about finding homogeneous sets for colorings of all finite subsets than just for pairs or for subsets of some fixed size. This difference is not revealed at ω, for which both are true by the infinite Ramsey theorem. But perhaps it suggests that we will get more power from Ramsey by using the more powerful colorings, since this is provably the case for higher cardinals.

Another point investigated by set theorists is that finding homogeneous sets in the case of infinite exponents---that is, coloring infinite subsets---is known to be inconsistent with the axiom of choice. However, in models of set theory where the Axiom of Choice fails, these infinitary Ramsey cardinals are fruitfully investigated. For example, under the Axiom of Determinacy, there are a great number of cardinals realizing an infinite exponent paritition relation.

nt.number theory - Probabilistic interpretation of prime number theorem

First of all, I assume you understand that this is meant to be a nonrigorous argument, so there will be a limit to how rigorous I can make my answer.

The intuition here is that $n$ is prime if and only if it is not divisible by any prime $<n$. So we "should" have
$$f(n) approx prod_{p < n} left( 1-1/p right).$$
Similarly
$$f(n+1) approx prod_{p<n+1} left( 1-1/p right) = prod_{p < n} left( 1-1/p right) cdot left{ begin{matrix} left( 1-1/n right) mbox{if} n mbox{is prime} \ 1 mbox{if} n mbox{is not prime} end{matrix} right. approx f(n) cdot left{ begin{matrix} left( 1-1/n right) mbox{if} n mbox{is prime} \ 1 mbox{if} n mbox{is not prime} end{matrix} right. .$$
Since $n$ is prime with "probability $f(n)$", we interpolate between the two cases next to the brace by writing:
$$f(n+1) approx f(n) left( 1-f(n)/n right).$$
One might argue that it would be better to interpolate with a factor of $(1-1/n)^{f(n)}$, but this will make no difference in the asymptopics as $(1-1/n)^{f(n)} = 1-f(n)/n+O(1/n^2)$.

This argument is famously fishy, because it gives the right answer, but the intermediate point is wrong! The actual asymptopics of $prod_{p<n} left( 1-1/p right)$ do not look like $1/log n$, but like $e^{-gamma} /log n$. I've never seen a good intuitive explanation for why we get the wrong estimate for $prod_{p<n} left( 1-1/p right)$, but the right estimate for the density of the primes.