ac.commutative algebra - Projective dimension of zero module

Although I agree that one can easily decide to not worry about the case of the zero module, but as ashpool points out, it happens that sometimes we end up with the zero module whether we want or not and then each time we need to say (using ashpool's example) if $M/aMneq 0$, then bluh and if $M/aM=0$ than something else happens.

So, I think there is actually something to be gained from making a definition that makes sense for the zero module (or the zero object in a more general situation). Of course, sometimes the definition that makes one (in)equality work does not work for another. However, one could still say in a paper (less likely in a book I suppose) that we are using the following definition for whatever which is the usual one if the object is not zero and gives this or that when it is zero and makes the following inequality work.

So having philosophized about this let me give a definition of projective dimension that gives $-infty$ for the zero module.

Definition Let $(R,mathfrak m,k)$ be a noetherian local ring and $M$ a finite $R$-module. Define the projective dimension of $M$ as
$$
mathrm{proj, dim}_R M:=sup left{ iin mathbb{Z} vert mathrm{Ext}_R^i (M,k)neq 0 right},
$$
where $sup$ is taken in $mathbb{Z}cup{pm,infty}$.

This is actually essentially ashpool's definition (1), except that for $M=0$ it takes the $sup$ of the empty set. (This may have been what samantha's professor told her). It also makes the change of rings formula to work.

In fact, I would argue that this is the "right" definition anyway, because the point is those Ext groups that are non-zero, not those that are.

Regarding adding the ${pm,infty}$ possibilities: We definitely need to allow $+infty$, so it makes sense to allow $-infty$ as well, especially because we need it for $M=0$.

Comment Of course one can start wondering what to do with non-local and/or non-noetherian rings, but I will leave that meditation to the reader.

co.combinatorics - A (known?) hypergeometric identity

Your relation is a particular case of the Karlsson--Minton relations (see Section 1.9 in the $q$-Bible by Gasper and Rahman). It's also a contiguous identity to Pfaff--Saalschütz.

EDIT.
First of all I apologise for giving insufficient comments on the problem.
I learned from Max a very nice graph-theoretical interpretation of the identity
which makes good reasons for not burring it in the list of "ordinary" problems.

The hypergeometric series (function)
$$
{}_ {p+1}F_ pbiggl(begin{matrix} a_ 0, a_ 1, dots, a_ p cr
b_ 1, dots , b_ pend{matrix};xbiggr)
= sum_ {k=0}^infty frac{(a_ 0)_ k(a_ 1)_ kdots (a_ p)_ k}{(b_ 1)_ kdots (b_ p)_ k}frac{x^k}{k!},
$$
where
$$
(a)_ 0=1 quadtext{and}quad
(a)_ k =frac{Gamma(a+k)}{Gamma(a)}= a(a+1)dots (a+k-1) quadtext{for } kin mathbb Z_ {>0}
$$
(I consider the ones with finite domain of convergence $|z|<1$), have very nice
history and links to practically everything in mathematics. There are many
transformation and summation theorems for them, both classical and contemporary.
There are very efficient algorithms and packages for proving them, like
the algorithm of creative telescoping (due to W. Gosper and D. Zeilberger)
and the package HYP
which allows one to manipulate and identify binomial and hypergeometric series
(due to C. Krattenthaler). An example of classical summation theorem is
the Pfaff--Saalschütz sum
$$
{}_ 3F_ 2biggl(begin{matrix} -m, a, b cr
c, 1+a+b-c-mend{matrix};1biggr)
=frac{(c-a)_ m(c-b)_ m}{(c)_ m(c-a-b)_ m}
$$
where $m$ is a negative integer, with a generalisation
$$
{}_ {p+1}F_ pbiggl(begin{matrix} a, b_ 1+m_ 1, dots, b_ p+m_ p cr
b_ 1, dots , b_ pend{matrix};1biggr)=0
quadtext{if } operatorname{Re}(-a)>m_ 1+dots+m_ p
$$
and
$$
{}_ {p+1}F_ pbiggl(begin{matrix} -(m_ 1+dots+m_ p), b_ 1+m_ 1, dots, b_ p+m_ p cr
b_ 1, dots , b_ pend{matrix};1biggr)=(-1)^{m_ 1+dots+m_ p}
frac{(m_ 1+dots+m_ p)!}{(b_ 1)_ {m_ 1}dots (b_ p)_ {m_ p}}
$$
due to B. Minton and Per W. Karlsson (here $m_ 1,dots,m_ p$ are nonnegative integers).
Max's original identity is not a straightforward particular case but a linear combination
of three contiguous Pfaff--Saalschütz-summable hypergeometric series.
(Two hypergeometric functions are said to be contiguous if they are alike except
for one pair of parameters, and these differ by unity.) Because of having three
hypergeometric functions, I do not see any fun in writing the corresponding details
but indicate a simpler hypergeometric derivation.

Applying Thomae's transformation
$$
{}_ 3F_ 2biggl(begin{matrix} -m, a, b cr
c, dend{matrix};1biggr)
=frac{(d-b)_ m}{(d)_ m}cdot{}_ 3F_ 2biggl(begin{matrix} -m, c-a, b cr
c, 1+b-d-mend{matrix};1biggr)
$$
the problem reduces to evaluation of the series
$$
{}_ 3F_ 2biggl(begin{matrix} -m, n+1, m+n cr
1, nend{matrix};1biggr).
$$
Writing
$$
frac{(n+1)_ k}{(n)_ k}=frac{n+k}{n}=1+frac kn
$$
the latter series becomes
$$
{}_ 3F_ 2biggl(begin{matrix} -m, n+1, m+n cr
1, nend{matrix};1biggr)
={}_ 2F_ 1biggl(begin{matrix} -m, m+n cr 1 end{matrix};1biggr)
+frac{(-m)(m+n)}{n} {}_ 2F_ 1biggl(begin{matrix} -m+1, m+n+1 cr 2 end{matrix};1biggr)
$$
and the latter two series are summed with the help of the Chu--Vandermonde summation
(a particular case of the Gauss summation theorem).

As for general forms of Max's identity, I can mention that there is no use of the integrality of $n$
in the last paragraph, and I could even expect something a la Minton--Karlsson in general.

mg.metric geometry - Geometrically interpreting the answer to a vector calculus question involving tangent line segments to ellipses.

There is a geometric way to show that $n$-gon circumscribed around an ellipse has minimal perimeter if it is inscribed in a confocal ellipse. From Poncelet porism (and generalization of optical property) it follows that we have continuous family of "minimal" polygons.

If we know it, then it is easy to understand that the circumscribed rhomb (from your question) and the circumscribed rectangular (with perimeter $4(a+b)$) are minimal polygons. So, side of the rhomb equals $a+b$.

dg.differential geometry - Proving the basic identity which implies the Chern-Weil theorem

Was going to put this as a comment on Willie's answer, but it was getting pretty long:

The idea is that, while a connection is not a section of $Omega^1(M,End(E))$- one may view it as a map $Gamma(E)to Gamma(T^*M otimes E)$- that is, if you give a connection a section, it will give you a peculiar creature which eats up vector fields and spits out what look like sections of E as the $T^*M$ tensor factors go to scalars.

In reality these things that look like sections are morally our connection's choice of lift of the vector field to E (- the confusing factor being that because E is a vector space, it is its own tangent space). Now, as already mentioned above a connection is globally $mathbb{C}$-linear, but not locally (that is not $C^infty(M)$-linear) as would be reqired to have $nabla in Gamma(Omega^1(M,End(E))) $.

This is because any candidate for a lift must perform the dirty deed of differentiating the section along your vector field (this is what the Leibniz rule condition is about). With this in mind, our first draft of a connection would just be $Theta=$ an extended $d_{DeRham}$-taking sections to their derivatives tensored with the duals of the directions in which they are differentiated (a so called 'trivial' connection)- but there is still room for manoevre and we can add to $Theta$ a 1-form $A in Gamma(Omega^1(M,End(E)))$ with coefficients in $End(E)$ and still get something that satisfies our conditions.

In fact for any connection $nabla$ we may write $nabla= Theta +A$ for some $End(E)$ valued 1-form A. Now in $nabla circ nabla$ 'the $Theta circ Theta $ bit' will go straight to zero for the same reason $d^2=0$ in the DeRham complex and you will have yourself just an $End(E)$ valued 2-form left (again, strictly, an $End T_{Gamma (x)}E$ valued 2-form, but who's counting?)- as you said, the curvature $R in Omega ^2 (M,E)$.

So (and this is the actual content of what I was going to put in the comment- the rest was just me getting carried away) what is an $End(E)$ valued 2-form when it's at home?

It's something that takes in pairs of vector fields and spits out an element of $End(E)$

$iff$ It's something that takes in pairs of vector fields and spits out a $Rank(E) times Rank(E)$ matrix

$iff$ It's something that takes in pairs of vector fields and spits out the entries of a $Rank(E) times Rank(E)$ matrix

$iff$ it is a $Rank(E) times Rank(E)$ matrix with entries in $Omega^2 (M)$

So we can add the identity without fear, and we can sensibly take the determinant since even forms commute when we multiply them.

Simply connectedness of algebraic group

To amplify Brian Conrad's semi-answer, I need a more precise definition of
"simply connected" at the outset. In characteristic 0 some of the classical
ways of thinking about this concept can be carried over to the algebraic
setting, but in prime characteristic the most common definition starts with
a connected semisimple group. Over an algebraically closed field,
the algebraic criterion for such a group to be simply connected
is that the character group of a maximal torus be the
full weight lattice.

Here the "fundamental group" of the adjoint group in the compact case
is re-interpreted as the quotient of the weight lattice by the root lattice,
which may also be regarded as the (scheme-theoretic) center of the simply
connected group.

There may be no quotable source earlier than the 1956-58 Chevalley
seminar. The classification work of Tits and others then descends to arbitrary
fields of definition. In SGA 3, Expose 22 (by Demazure), Definition 4.3.3 defines "simply
connected" in terms of the behavior of fibers relative to this
criterion using the root datum language.

gt.geometric topology - Smooth structures on PL 4-manifolds

Very little is known about that question, the same smoothing theory gives something that I'm trying to get people to call "The Cerf-Morlet Comparison Theorem"

$$ Diff(D^n) simeq Omega^{n+1}(PL(n)/O(n)) $$

$Diff(D^n)$ is the group of diffeomorphisms of the $n$-ball where the diffeomorphisms are pointwise fixed on the boundary. Nobody knows if $Diff(D^4)$ is path-connected or not. Very little is known about the homotopy-type of $Diff(D^4)$, no seriously informative statements other than that homotopy-equivalence. I wrote up a paper where I described in detail the iterated loop-space structure and how it arrises naturally. Moreover, I described how that iterated loop-space structure relates to various natural maps. That's my main relation to to topic. The paper is called "Little cubes and long knots" and is on the arXiv. I elaborate on some of these issues in the paper "A family of embedding spaces", also on the arXiv.

There are several natural connections here, one of the big ones being that $Diff(D^n)$ has the homotopy-type of the space of round metrics on $S^n$ -- ie the subspace of the affine-space of Riemann metrics on $S^n$, the subspace is specified by the condition that "$S^n$ with this metric is isometric to the standard $S^n$."

co.combinatorics - Maximum bipartite graph (1,n) "matching"

Last month I discovered a nice question on stackoverflow and thought the 1,n matching problem could be solved via introducing a 1,k tree matching. Look here for my question, but as Moron pointed out this is not known to be solvable in polynomial time.

Now I discovered mathoverflow and would like to know if one could reduce some possibilities or if one could introduce some restrictions so that the 1,n matching could be solved in polytime. Do you have an idea?

Background: I would like to implement a heuristic for that problem. At the moment I am using an algorithm based on the GPA heuristic for weighted maximum matchings in general graphs as described here.

Here is my formulation of the problem:

Instead of the 'normal' "one-to-one" matching in a bipartite graph I want to calculate the maximum "one-to-many" matching for a bipartite graph G. (Should I define it or is this clear?)
For the initial problem 1:n the n was arbitrary. Then I fixed the n to k 'static' choices via trees instead of edges, but this was hard, too.
Now I would like to find a similar graph or different formulation which is solvable in polytime (or at least there should be a high accurate and 'fast' algorithm).
E.g. couldn't I apply the polytime matching algorithm from general graphs and apply it to a slightly changed graph G'? I think about the following graph G':

http://karussell.files.wordpress.com/2010/03/network2.png (don't have rep to include it here :-/)

Clearly there are matchings (red) in the general graph G' which could result in strange/wrong matchings for the corresponding bipartite matching in the bipartite graph G. But maybe one could further tweak the graph G' or the edge weights of G'?

Or how is this related to hypergraphs (e.g. if edge would have 3 nodes)

Missing tag: matching

soft question - Good papers/books/essays about the thought process behind mathematical research

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

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

• a solitary path associated to Thurston's early work on foliations


• a social path associated to Thurston's later work on the Geometrization Conjecture

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

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

• social elements of research can be consciously chosen by individuals


• fundamental mathematics can provide uniquely strong foundations for social enterprises


• healthy mathematical communities make faster progress, and also, a better environment for nurturing the next generation of young mathematicians.

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

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

gt.geometric topology - Is there a knotted torus in 4-sphere whose complement's fundamental group is infinite cyclic ?

I am reading the book 'surface in 4-space' about the unknotting conjecture (Page 97): a 2-knot (2-sphere in 4-sphere) is trival if and only if the fundamental group of the exterior is infinite cyclic.

It said that in TOP category, Freedman proved the statement is true. I don't know why it is also true for general surface. in top category?

nt.number theory - Achieving consecutive integers as norms from a quadratic field

Something small, but maybe useful, which no one seems to have pointed out: as $ptoinfty$, $(mathbb{Z}/pmathbb{Z})^{times}$ contains arbitrarily long strings of consecutive quadratic residues. Indeed, the function

$b(a)=2^{-k}(1+(frac{a}{p}))(1+(frac{a+1}{p}))dots(1+(frac{a+k-1}{p}))$

is $1$ or $0$ according to whether $(a,a+1,dots,a+k-1)$ is a $k$-term string of quadratic residues or not. Summing over $(mathbb{Z}/pmathbb{Z})^{times}$, expanding out and using the bound of Weil,

$lvert sum_{a in (mathbb{Z}/pmathbb{Z})^{times}} (frac{(a+b_1)(a+b_2)dots (a+b_r)}{p}) rvert leq 2rsqrt{p},$

which holds if at least one $b_i$ is distinct from all the others, we derive

$sum_{a in (mathbb{Z}/pmathbb{Z})^{times}}b(a)=2^{-k}p+O(ksqrt{p})$.

The error term here comes from the fact that when we expand out $b(a)$ and sum, we'll get the obvious main term, plus $2^{-k}$ times a sum of $2^{k}-1$ Weil sums, each of which is bounded by $2ksqrt{p}$.

Anyway, the main term dominates the error term if $k2^{k}=o(sqrt{p})$, which certainly holds if (say) $k=o(log{p}).$

What is Chern-Simons theory?

Not sure that I am saying anything that is not in nLab, but let me try a birds eye view. A quantum theory is "mostly specified" by an action, and the CS theory in $2+1$ dimensions with group $G$ has as action the Chern-Simons functional (comes from boundary terms of characteristic classes) on the space of connections on some $3$ manifold. There is a parameter, and you get a well-defined theory whenever the parameter is a root of unity. Because this theory requires no background metric or other geometry to define, any computations in the theory should in principle be topological invariants of the manifold (life gets complicated in the details, but pretty much all you have to add is this extra biframing info to make that correct). Since particles are roughly representations, a sequence of particles interacting and moving around each other in space (a $2$-manifold here) will as a movie trace out linked loops labeled by representations in spacetime (a $3$-manifold). The expectation value of this sequence of interactions (roughly the probability of occurrence) is the value of the Jones polynomial at that value of $q$ (Those who have tried to make the various normalizations of the parameters in the physics and math literature align have gone mad: don't try it at home! It is pretty mysterious why these values combine to a polynomial). The value of the partition function for an ordinary manifold (which technically should not have physical meaning as you are supposed to divide out by it, but it is telling you something about the time-evolution operator, which is constant because it is topologically invariant).

All of that should is because the natural way to build a theory from the action is the path integral, which is a nonrigorous heuristic. The mathematical response to this is, in this case, axiomatic TQFT. Heuristic reasoning argues that the basic building blocks of the theory should have certain properties that should uniquely specify them, and then you can explicitly construct such objects from, say, quantum groups (I do NOT know how to get the quantum groups themselves from the physics) and prove they satisfy the necessary properties. From these you can compute partition functions and expectations to your hearts delight.

computational complexity - Is there a syntactic characterization for BPP, BQP, or QMA?

The complexity classes BPP, BQP, and QMA are defined semantically. Let me try to explain a little bit what is the difference between a semantic definition and a syntactic one. The complexity class P is usually defined as the class of languages accepted in polynomial time by a deterministic Turing machine. Although it seems to be a semantic definition at first, $P$ has an easy syntactic characterization, i.e. deterministic Turing machines with a clock counting the steps up to a fixed polynomial (take a deterministic Turing machine, add a polynomial clock to it such that the new machine will calculate the length of the input $n$, then the value of the polynomial $p(n)$, and simulate the original machine for $p(n)$ steps. The languages accepted by these machines will be in $P$ and there is at least one such machine for each set in $P$). There are also other syntactic characterizations for $P$ in descriptive complexity like $FO(LFP)$, first-order logic with the least fixed point operator.
The situation is similar for PP.
Having a syntactic characterization is useful, for example a syntactic characterization would allow us to enumerate the sets in the class effectively, and if the enumeration is efficient enough, we can diagonalize against the class to obtain a separation result like time and space hierarchy theorems.

---

My main question is:

Is there a syntactic characterization for BPP, BQP, or QMA?

I would also like to know about any time or space hierarchy theorem for semantic classes mentioned above.

---

The motivation for this question came from here.
I used Google Scholar, the only result that seemed to be relevant was a citation to a master's thesis titled "A logical characterization of the computational complexity class BPP and a quantum algorithm for concentrating entanglement", but I was not able find an online version of it.

at.algebraic topology - Cohomology of complex projective spaces with coefficientes in a complex-orientable cohomology theory

Hello everyone,

I'm having problems understanding a basic fact about complex-orientable cohomology theories:

Let $E^{ast}$ be a multiplicative cohomology theory and $xin E^2({mathbb C}text{P}^{infty})$ such that the image of $x$ under

$E^2({mathbb C}text{P}^{infty})to E^2({mathbb C}text{P}^1)cong E^0(ast)$

equals $1$. Then the claim is that for any $ngeq 1$ the map

$E^{ast}[x] / (x^{n+1})longrightarrow E^{ast}({mathbb C}text{P}^n)$

is an isomorphism (this is lemma 1.4 in Mike Hokpin's Lecture Notes on Complex Orientable Cohomology Theories).

The proof goes via the Atiyah-Hirzebruch spectral sequence, the claim being that the AHSS degenerates at the $E_2$-page $E_2^{p,q} cong E^{ast}[x] / (x^{n+1})$. I don't understand why the differentials have to vanish. Could somebody explain this to me in detail? Shouldn't be difficult, but I'm not familiar with the AHSS and don't see it.

Thank you in advance, Hanno

ag.algebraic geometry - plane hyperelliptic curves

I don't know how to answer this question at homework level. If you have a plane curve of degree $d$, it has lots of maps to $P^1$ of degree $d-1$ by projecting from points. If the curve is also hyperelliptic, it has a map of degree two to $P^1$. For at least one of the maps of degree $d-1$, the conditions of the Castelnuovo genus bound (you'll have to look that up) is satisfied and we get that the genus satisfies $g le d-2$. Now, if your plane curve is smooth (which I had not previously assumed) then $g = (d-1)(d-2)/2$, which combined with the previous bound gives, not surprisingly, $d le 3$.

nt.number theory - $L$-functions for $Theta$-lifts

Let $E/F$ be a quadratic extension of number fields. Let $W$ be a hermitian space over $E$ of dimension $2,$ and let $V$ be a skew-hermitian space of dimension $3$ over $E.$ Consider the associated unitary groups $H:=U(W)$ and $G:=U(V).$ Let $sigma$ be an irreducible, cuspidal, automorphic representation of $H(mathbb{A}_F).$ Let $pi=Theta(sigma,psi,gamma)$ be a theta lift of $sigma$ to $G(mathbb{A}_F)$. ($psi:mathbb{A}_F/Fto mathbb{C}^times$ and $gamma:mathbb{A}_E^times/E^timestomathbb{C}^times$ are the splitting data necessary to define the theta-lift for unitary groups.)

My question is, how do automorphic $L$-functions (standard, adjoint, etc.) for $pi$ relate to those for $sigma$?

gt.geometric topology - Generating ribbon diagrams for knots known to be ribbon knots

Is there a source in the literature for ribbon diagrams for the knot-table knots known to be ribbon knots?

For example, I'm interested in doing a computation which needs as input a ribbon diagram for the knot $8_{20}$ (Rolfsen knot table notation). This knot is known to be ribbon, but I don't know a ribbon diagram for the knot.

Usually when I encounter a claim of the sort "knot X is ribbon" either the author supplies the ribbon diagram, or nothing. Citations to information of this sort seem kind of sparse. Or am I just unaware of a standard source for this type of information?

tag removed - What is the mathematical meaning of this symbol?

Hi,

This was supposed to be a comment to Mariano's answer, but it seems too long for a comment.

Somebody gave me that clock for Christmas and all along I thought $B_L'=1$ was some silly Physics constant... but it seems Mariano is right, and this refers to Legendre's constant (at least, that's the case according to this other site).

I was terribly curious, though, to find out where this notation came from and decided to go right to the source, "Essai sur la Theorie des Nombres", by Legendre. Amazingly, our friends at Google have scanned the whole book, and the whole volume is freely available here. It is a large volume, however! So it was not easy to locate the exact place where Legendre talks about the prime counting function. A nice paper by Goldstein in the American Math Monthly, "A history of the prime number theorem"" was very helpful to locate the exact reference: p. 394-398 in the second edition of the "Essai sur..." by Legendre.

In p. 395, Legendre explains that $pi(x)$, the number of primes $leq x$, seems to grow like
$$frac{x}{Alog x + B}$$
and conjectures that $A=1$ and $B=-1.08366ldots$ (now a famous mistake, since later on the proofs of the prime number theorem would show that $B=1$). But, in any case, Legendre himself called this constant $B$ and I suppose somebody added the subscript $L$, to $B_L$, to remind us of Legendre's name.

However, I am still puzzled by the apostrophe, $B_L'$.

lie algebras - Is there a version of Temperley-Lieb using sl(3) rather than sl(2)?

Yes... I saw it first in Stedman's work (Diagram Techniques in Group Theory, G. E. Stedman, Cambridge University Press, 1990), but it may also exist elsewhere. The basic idea is to combine symmetrization and anti-symmetrization across different sets of strands, roughly in correspondence with the Young tableaux.

The other place to look for more general diagrams for general Lie algebras is Cvitanovic (Group Theory: Birdtracks, Lie's, and Exceptional Groups, Predrag Cvitanović, Princeton University Press, 2008, http://birdtracks.eu/). The text is available online and it is extremely impressive.

reference request - Why are local systems and representations of the fundamental group equivalent

I agree that the correspondence between representations of the fundamental group(oid) and locally constant sheaves is not very well documented in the basic literature. Whenever it comes up with my
students, I end up having to sketch it out on the blackboard. However, my recollection is that Spanier's Algebraic Topology gives the correspondence as a set of exercises with hints. In any case, one direction is easy to describe as follows. Suppose that $X$ is a good connected space X (e.g. a manifold). Let $tilde Xto X$ denote its universal cover. Given a representation of its fundamental $rho:pi_1(X)to GL(V)$, one can form the sheaf of sections of the bundle $(tilde Xtimes V)/pi_1(X)to X$. More explicitly, the sections
of the sheaf over U can be identified with the continuous functions $f:tilde Uto V$ satisfying
$$f(gamma x) = rho(gamma) f(x)$$
for $gammain pi_1(X)$. This sheaf can be checked to be locally constant.
Essentially the same procedure produces a flat vector bundle, i.e. a vector bundle with locally constant transition functions. This is yet another object equivalent to a representation of the fundamental group.

With regard to your other comments, perhaps I should emphasize that the Narasimhan-Seshadri correspondence is between stable vector bundles of degree 0 and irreducible
unitary representations of the fundamental group. The bundle is constructed as indicated above.
Anyway, this sounds like a good Diplom thesis problem. Have fun.

gr.group theory - Hausdorff Dimension of Cayley Graphs of Groups

The Cayley graph of a finitely generated countable group is a metric space with respect to the word metric. One includes both edges and vertices in the geometric realization (after all, it's called a graph, not a discrete point set). If the group is nontrivial, the graph is regular of constant finite valence, so small neighborhoods of any point are isometric to line segments or stars. If the group is nontrivial, the Hausdorff dimension of the graph is 1, and this is independent of the choice of generating set. Any countable Cayley graph can be embedded (non-isometrically) in $mathbb{R}^3$ using an enumeration of vertices by natural numbers, e.g., sending the $n$th vertex to $(n,n^2,n^3)$, and taking edges to be straight lines.

The free group on 2 letters can be embedded (non-isometrically) in $mathbb{R}^2$ as a fractal, as shown in the linked image you gave. The Hausdorff dimension of the image in general strongly depends on the choice of embedding. For example, the Cayley graph of $mathbb{Z}$ with generator $1$ is isometric to the real line, but you may be able to embed it in a larger space using some kind of Brownian motion, where the image will have Hausdorff dimension 2 almost surely.

soft question - Most helpful math resources on the web

Sci-Hub is pretty helpful in accessing articles, even for those researchers who already have access to several journals. The interface is great, the site is pretty fast, and the database is huge. See this article and other linked articles there for a nice overview of who all are downloading pirated papers.

Edit: as pointed out in the comments, it should be noted that there is an ongoing lawsuit against the website.

gr.group theory - (co)homology of cyclic groups

The answer to your question is simple. Choose a generator $sigma$ of $G$. Then we have an exact sequence $$0 to mathbb{Z} xrightarrow{m mapsto m 1_G} mathbb{Z}[G] xrightarrow{sigma-1} mathbb{Z}[G] xrightarrow{g in G mapsto 1} mathbb{Z} to 0.$$ Since $mathbb{Z}[G]$ is a free (hence projective) $mathbb{Z}[G]$ module, this means that we have isomorphisms $mathrm{Ext}^n(mathbb{Z},M) cong mathrm{Ext}^{n+1}(mathrm{Im}(sigma-1),M) cong mathrm{Ext}^{n+2}(mathbb{Z},M)$ for $n ge 1$, and since $mathrm{Ext}(mathbb{Z},M) cong H^n(M)$, this gives us the desired periodicity.

This is related to the bar resolution in the sense that the bar resolution gives us group cohomology specifically because $mathrm{Ext}^n(mathbb{Z},M) cong H^n(G,M)$. It follows that $mathrm{Ext}$ can be computed by applying $mathrm{Hom}(-,M)$ to a projective resolution of $mathbb{Z}$, and the bar resolution is precisely such a resolution.

Note that by $mathrm{Ext}$ we mean over the category $mathbb{Z}[G]$-Mod.

it.information theory - Closed form solution to x^(x+1)=(x+1)^x

Really? If you've found a continued fraction expression for this solution, I'd love to see it. The sequence I get

2, 3, 2, 2, 3, 4, 2, 3, 2, 130, 1, 1, 1, 1, 1, 6, 3, 2, 1, 15, 1, 1,
1, 8, 10, 3, 1, 5, 6, 4, 39, 2, 1, 1, 2, 2, 1, 1, 1, 4, 8, 4, 2, 5,
1, 2, 1, 5, 12, 1, 1, 5, 1, 5, 1, 1, 4, 2, 3, 3, 2, 3, 4, 4, 1, 1, 1,
4, 2, 1, 7, 11, 2, 4, 2, 39, 1, 2, 1, 29, 3, 2, 6, 8, 3, 7, 1, 7, 1,
2, 2, 1, 3, 1, 3, 7, 1, 1, 79, 2, 1, 11, 2, 4, 1, 1, 1, 1, 1, 9, 3,
6, 9, 1, 2, 1, 2, 2, 1, 1, 3, 1, 3, 2, 6, 26, 6, 4, 3, 1, 1, 4, 1, 3,
9, 296, 6, 1, 1, 96, 1, 2, 1, 3, 7, 4, 86, 4, 168, 19, 34, 21, 3, 2,
6, 1, 1, 1, 18, 1, 9, 2, 1, 1, 6, 2, 3, 2, 1, 1, 3, 1, 2, 1, 6, 7, 9,
5, 1, 2, 4, 1, 1, 5, 117, 3, 5, 1, 40, 1, 1, 3, 2, 26, 8, 22, 2, 1,
1, 1, 12, 1, 5, 6, 2, 1, 5, 1, 2, 2, 5, 1, 1, 1, 39, 2, 2, 2, 1, 6,
2, 13, 1, 71, 1, 4, 3, 1, 11, 1, 7, 2, 4, 5, 4, 1, 1, 5, 4, 2, 12, 2,
91, 1, 1, 2, 25, 1, 1, 24, 1, 18, 1, 2, 1, 4, 1, 2, 2, 1, 2, 1, 1, 1,
2, 92, 2, 1, 1, 35, 1, 1, 1, 9, 2, 2, 1, 1, 2, 2, 1, 9, 1, 1, 4, 1,
1, 1, 1, 38, 2, 41, 2, 1, 3, 1, 1, 27, 18, 4, 20, 9, 1, 2, 9, 37, 1,
1, 1, 1, 10, 1, 11, 1, 2, 1, 1, 2, 1, 1, 2, 6, 14, 1, 17, 1, 1, 5, 2,
2, 1, 2, 5, 2, 1, 131, 1, 8, 12, 1, 2, 3, 1, 3, 1, 5, 5, 1, 1, 1, 7,
1, 2, 1, 5, 1, 1, 8, 2, 2, 4, 1, 1, 17, 3, 14, 2, 11, 2, 3, 2, 3, 2,
1, 1, 1, 4, 6, 2, 37, 2, 1, 1, 201, 6, 11, 1, 113, 1, 8, 7, 18, 1, 2,
2, 17, 4, 3, 5, 2, 1, 1, 1, 2, 2, 2, 1, 3, 1, 9, 4, 2, 2, 2, 3, 1, 1,
1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 8, 3, 1, 17, 1, 1, 1, 2, 1, 4, 1, 3, 4,
11, 2, 7, 15, 1, 1, 2, 1, 1, 18, 1, 1, 1, 3, 7, 2, 1, 1, 2, 12, 6, 1,
2, 1, 2, 2, 1, 2, 4, 2, 1, 1, 3, 1, 108, 1, 1, 2, 6, 4, 1, 4, 4, 7,
1, 6, 2, 19, 1, 4, 4, 1, 1, 10, 1, 12, 1, 2, 2, 5, 8, 2, 1, 1, 6, 1,
1, 1, 21, 2, 1, 13, 1, 3, 19, 1, 1, 27, 2, 8, 183, 3, 2, 1, 1, 2, 1,
11, 7, 2, 1, 1, 4, 1, 4, 2, 26, 2, ...

looks pretty darn structureless!

Algebraic Geometry in an applied setting?

Well, as Grassmannians parameterize vector subspaces of a vector space, they are pretty much in control of any sort of linear thing, like tensors, so at the least, I don't think it's surprising that they come up. As far as sources on the Grassmannians, I wrote a series of posts on the cohomology of Grassmannians at Rigorous Trivialities, and for a more thorough exposition on some of the same stuff, you can check out the last section of Fulton's "Young Tableux." As far as more analytic properties of Grassmannians, I don't have good references, and most of the time algebraic geometers seem to be interested in cohomology (of various sorts) of flag varieties and of using them to make other moduli spaces. Hope this helps.

Reading list for basic differential geometry?

I'd start with Lee's Introduction to Smooth Manifolds.
It covers the basics in a modern, clear and rigorous manner.
Topics covered include the basics of smooth manifolds, smooth
vector bundles, submersions, immersions, embeddings, Whitney's
embedding theorem, differential forms, de Rham cohomology, Lie
derivatives, integration on manifolds, Lie groups, and Lie algebras.

After finishing with Lee, I'd move on to Hirsch's Differential
Topology. This is more advanced then Lee and leans more
towards topology. Also, the proofs are much more brief then
those of Lee and Hirsch contains many more typos than Lee.
The topics covered include the basics of smooth manifolds,
function spaces (odd but welcome for books of this class),
transversality, vector bundles, tubular neighborhoods, collars,
map degree, intersection numbers, Morse theory, cobordisms,
isotopies, and classification of two dimensional surfaces.

These two should get you through the basics. However, if that
is not enough, I'd move on to Kosinski's Differential Manifolds
which covers the basics of smooth manifolds, submersions, immersions,
embeddings, normal bundles, tubular neighborhoods, transversality,
foliations, handle presentation theorem, h-cobordism theorem,
framed manifolds, and surgery on manifolds.

sheaf theory - Descent of singular cohomology

When proving that singular cohomology of an appropriate space $X$ equals sheaf cohomology of $X$ with "values" (does one say that?) in the sheaf $mathbb{Z}_X$ of locally constant functions, the author of the proof I have read observes that the sheafifications $mathcal{C}^n$ of the singular cochain complexes $C^n(-)=hom_{Ab}(mathbb{Z}hom_{Top}(Delta^n,-),mathbb{Z})$ form an injective resolution
$$
0tomathbb{Z_X}tomathcal{C}^0tomathcal{C}^1toldots
$$
of $mathbb{Z}_X$.

Why must one sheafify the singular cochain complexes? Aren't they sheaves since they satisfy descent (= have the excision property) and "sheaf=presheaf+descent"?

co.combinatorics - Dyck paths on rectangles

Is a sum OK?

I am used to a different rotation of the paths. I think the paths you are looking for can also be described as all paths above the x-axis, with steps (1,1) and (1,-1), that starts at (0,0) and ends on the line x=y+n for some (x,y) from (n,0) to (n+m,m).

(If instead they end at the line x=n, we get the Ballot paths.)

Let B(n,k) be the Ballot numbers, B(n,k)= # paths from (0,0) to (n,k). Now, all paths must pass the line x=n. From there on it is just a binomial path, so the number of paths are
sum_{k=0,2,4,...,n} B(k,n)*( (n-m-k)/2 choose k/2)

(n choose k)= Binomial coefficient, n!/(k!(n-k)!)

at.algebraic topology - Noncompact homology spheres?

If $M$ is a connected, non-compact $n$-manifold, then $H_i(M;R)=0$ for $igeq n$. For a proof, see Proposition 3.29 in Hatcher's Algebraic Topology book.

So, if you are going to have $H_n(M;R)=R$, $M$ had better be compact.

EDIT (to answer about homology $n$-manifolds):

A homology $n$-manifold is a finite dimensional, locally contractible space $X$ whose local homology groups $H_*(X, X-{x})$ are the local homology groups for $mathbb{R}^n$ for every $xin X$. In particular, $mathbb{R}^n$ is a non-compact homology $n$-manifold.

Bringing Number and Graph Theory Together: A Conjecture on Prime Numbers

Some MOers have been skeptic whether something like natural number graphs can be defined coherently such that every finite graph is isomorphic to such a graph. (See my previous questions [1], [2], [3], [4])

Without attempting to give a general definition of natural number graphs, I invite you to consider the following

DEFINITION

A natural number $d$ may be called demi-prime
iff there is a prime number $p$ such
that $d = (p+1)/2$. The demi-primes' distribution is exactly
like the primes, only shrinked by the
factor $2$:

$$2, 3, 4, 6, 7, 9, 10, 12, 15, 16, 19, 21, 22, 24, 27, 30, 31, 34, 36, 37, 40, 42, 45, 49, ...$$

Let D($k,n$) be the set which consists
of the $k$-th up to the $(k+n-1)$-th
demi-prime number.

After some - mildly exhaustive - calculations I feel quite confident to make the following

CONJECTURE

For every finite graph $G$ there is a $k$ and a bijection $d$ from the vertex set
$V(G)$ to D($k,|G|$) such that $x,y$ are adjacent if and only if $d(x),d(y)$ are coprime.

I managed to show this rigorously for all graphs of order $nleq $ 5 by brut force calculation, having to take into account all (demi-)primes $d$ up to the 1,265,487^th one for graphs of order 5. For graphs of order 4, the first 1,233 primes did suffice, for graphs of order 3 the first 18 ones.

Looking at some generated statistics for $n leq$ 9 reveals interesting facts⁽¹⁾⁽²⁾, correlations, and lack of correlations, and let it seem probable (at least to me) that the above conjecture also holds for graphs of order $n >$ 5.

Having boiled down my initial intuition to a concrete predicate, I would like to pose the following

QUESTION

Has anyone a clue how to prove or disprove the above conjecture?

My impression is that the question is about the randomness of prime numbers: Are they distributed and their corresponding demi-primes composed randomly enough to mimick – via D($k,n$) and coprimeness – all (random) graphs?

---

⁽¹⁾ E.g., there is one graph of order 5 - quite unimpressive in graph theoretic terms - that is very hard to find compared to all the others: it takes 1,265,487 primes to find this guy, opposed to only 21,239 primes for the second hardest one. (Lesson learned: Never stop searching too early!) It's – to whom it is of interest – $K_2 cup K_3$:

0 1 0 0 0
1 0 0 0 0
0 0 0 1 1
0 0 1 0 1
0 0 1 1 0

⁽²⁾Added: This table shows the position of the smallest prime (among all primes) needed to mimick the named graphs of order $n$. All values not shown are greater than $approx 2,000,000$

order    |   3     4      5      6       7      8
-------------------------------------------------
empty    |  14    45     89     89      89   3874 
complete |   5    64    336   1040   10864  96515 
path     |   1     6   3063  21814  
cycle    |   5   112  21235  49957 

gr.group theory - On the size of balls in Cayley graphs

In the article

R. Grigorchuk and P. De La Harpe, On problems related to growth, entropy, and spectrum in group theory, Journal of Dynamical and Control Systems, Volume 3, Number 1, 51-89

on the lower part of page 58 the authors mention the manuscript

A. Machi, Growth functions and growth matrices for finitely generated groups. Unpublished manuscript, Univ. di Roma La Sapienza, 1986.

and explain an example due to Machi. Machi showed that the convergence of $b_{n+1}/b_n$ can fail for one generating set of ${mathbb Z}_2 star {mathbb Z}_3$ and hold for another. In particular, the limit does not always exist. The two generating sets are $lbrace s,trbrace$ and $lbrace s,strbrace$, where $s$ and $t$ are the natural generators with $s^2=t^3=e$.

at.algebraic topology - Functorial Whitehead Tower?

The nth stage of the Whitehead tower of X is the homotopy fiber of the map from X to the nth (or so) stage of its Postnikov tower, so you can use your functorial construction of the Postnikov tower plus a functorial construction of the homotopy fiber (such as the usual one using the path space of the target).

The nth stage of the Whitehead tower of X is also the cofibrant replacement for X in the right Bousfield localization of Top with respect to the object Sⁿ (or so). Since Top is right proper and cellular this localization exists by the result of chapter 5 of Hirschhorn's book on localizations of model categories. You might look there to see how the cofibrant replacement functor is constructed. With some care you should be able to define functorially the maps in the tower as well.

(BTW, the Postnikov tower can similarly be obtained functorially by a left Bousfield localization of Top.)

gt.geometric topology - Closed hyperbolic manifold with right-angled fundamental domain

What is an example (as simple as possible, please!) of a closed hyperbolic three-manifold with a right-angled polyhedron as fundamental domain?

If we allow cusps then the Whitehead link or the Borromean rings are good answers (fundamental domains have not too many sides and the gluings can be understood). If we allow orbifolds then the (4,0) filling on all components of the Borromean rings is a good answer. (This is carefully explained in the NotKnot video.) I tried to answer the original question, using SnapPea (see also SnapPy), to build a cyclic, four-fold, manifold cover of the Borromean orbifold. This was not successful. It is "obvious" that the resulting manifold has a right-angled fundamental domain, but the domain is huge (two octagons, eight hexagons, 16 pentagons) and it is hard (for me) to describe the face pairings or check that I haven't messed up in some way.

More generally, I guess that one could use Andreev's theorem to build as "simple as possible" right-angled polyhedra and then look for low index torsion free subgroups of the resulting reflection groups. However I don't know how large an index we'd have to sacrifice or even if the resulting manifold will have a right-angled domain...

Edit: I've accepted bb's answer below, because the first paper cited gives the required construction. However, I didn't understand this until I asked an expert off-line, who puckishly told me that this was equivalent to the four color theorem! Here is the construction:

Suppose that $R$ is a right-angled three-dimensional hyperbolic polyhedron. Note that the edges of $R$ form a cubic graph in $partial R$. Let $G_R$ be the subgroup of isometries of $H^3$ generated by reflections in the sides of $R$. Now, by the four-color theorem there is a four coloring of the faces of $R$ (so no two adjacent faces have the same color). This defines surjective homomorphism from $G_R$ to $(Z/2)^4$. Let $delta = (1,1,1,1) in (Z/2)^4$ and let $Delta$ be the preimage in $G_R$ of the subgroup generated by $delta$. Note that $Delta$ has index eight in $G_R$ and is torsion-free. Finally, a fundamental domain for $Delta$ is a obtained by gluing eight copies of $R$ around a vertex.

Other cryptic tidbits I was fed: There is such a hyperbolic manifold in dimension four, coming from the 120-cell. This is the only example known. There are no such examples in dimensions five and higher. See Bowditch and Mess, referring to Vinberg and Nikulin.

Further edit: In fact the argument using the four-color theorem can be found in the second paper of Vesnin, as cited by bb.

reference request - Telling group algebras apart

It's a big, famous, hard problem in operator algebras to determine if the von Neumann algebras $L(F_2)$ and $L(F_3)$ are isomorphic, or not. Here $F_n$ is the free group on n generators and $L(F_n)$ is the weak-operator-topology closure of the group algebra $mathbb C[F_n]$ acting naturally on the Hilbert space $ell^2(F_n)$.

I presume it must be known if the algebras $mathbb C[F_2]$ and $mathbb C[F_3]$ are isomorphic or not. But from casually asking a few algebraists, I've never had any luck in finding this out (I admit to not working very hard on this!) I'm guessing some (co)homology theories must help...? What about for replacing $mathbb C$ by a more general ring?

ct.category theory - Splitting lemma under assumption of the axiom of choice

This is right: a map $f:A rightarrow B$ is surjectiv $Longleftrightarrow$ $f$ has a right-inverse. The proof needs the axiom of choice, as you pointed out correctly. But this is just a map of sets.

EDIT: In the following I'm talking about groups (vector spaces, vector bundles, presheaves, sheaves,... should also do the job)

Every short exact seqeunce can be seen as a sequence
$$0 overset{inc_0}rightarrow A overset{inc}{rightarrow} B overset{pi}{rightarrow} B/A rightarrow 0$$
where $inc$ denotes the inclusion and $pi$ the projection.

But (as for example Charles Siegel pointed out) surjectivity gives you just a rightinverse $u:C rightarrow B$ as map of sets. So if you have further structures (let's say a group structure, vector space structure, etc.), this doesn't mean, that the map $u$ is an inverse with respect to these structures

ag.algebraic geometry - How do you see the genus of a curve, just looking at its function field?

Let $k$ be the ground field.

The Kahler differentials $Omega_{K/k}$ are the $K$ vector space generated by formal symbols $dg$ subject to $d(f+g)=df+dg$, $d(fg) = f dg + g df$ and $da=0$ for $a in k$. This is a one dimensional $K$ vector space.

Let $omega$ be a differential. For any valuation $v$ on $K$, let $t$ be such that $v(t)=1$. We say that $omega$ is regular at v if $v(omega/dt) geq 0$. We say that $omega$ is regular if it is regular at every valuation of $K/k$. Then the space of regular differentials is a $k$ vector space of dimension $g$.

FURTHER THOUGHTS

Both Ben's answer and mine used the set of valuations of $K/k$. This essentially means that we used the ground field $k$. A valuation of $K/k$ is defined as a valuation of $K$ which is trivial on $k$; conversely, the ground field can be recovered from the valuations that respect it by the formula $k = bigcap_{v} v^{-1}(mathbb{R}_{geq 0})$.

Here is a cautionary example to show that there can not be any solution which only uses properties of the field $K$, without reference to $k$. Let $C$ and $D$ be two irreducible curves of different genuses. Let $K$ be the field of meromorphic functions on $C times D$, let $k$ and $ell$ be the fields of functions on $C$ and $D$. Then $K$ is a transcendence degree 1 extension of both $k$ and $ell$, but has different genuses when considered in these two ways.

soft question - Fundamental Examples

It is not unusual that a single example or a very few shape an entire mathematical discipline. Can you give examples for such examples? (One example, or few, per post, please)

I'd love to learn about further basic or central examples and I think such examples serve as good invitations to various areas. (Which is why a bounty was offered.)

---

Related MO questions: What-are-your-favorite-instructional-counterexamples,
Cannonical examples of algebraic structures, Counterexamples-in-algebra, individual-mathematical-objects-whose-study-amounts-to-a-subdiscipline, most-intricate-and-most-beautiful-structures-in-mathematics, counterexamples-in-algebraic-topology, algebraic-geometry-examples, what-could-be-some-potentially-useful-mathematical-databases, what-is-your-favorite-strange-function; Examples of eventual counterexamples ;

---

To make this question and the various examples a more useful source there is a designated answer to point out connections between the various examples we collected.

---

In order to make it a more useful source, I list all the answers in categories, and added (for most) a date and (for 2/5) a link to the answer which often offers more details. (~year means approximate year, *year means a year when an older example becomes central in view of some discovery, year? means that I am not sure if this is the correct year and ? means that I do not know the date. Please edit and correct.) Of course, if you see some important example missing, add it!

Logic and foundations: $aleph_omega$ (~1890), Russell's paradox (1901),
Halting problem (1936), Goedel constructible universe L (1938), McKinsey formula in modal logic (~1941), 3SAT (*1970), The theory of Algebraically closed fields (ACF) (?),

Physics: Brachistochrone problem (1696), Ising model (1925), The harmonic oscillator,(?) Dirac's delta function (1927), Heisenberg model of 1-D chain of spin 1/2 atoms, (~1928), Feynman path integral (1948),

Real and Complex Analysis: Harmonic series (14th Cen.) {and Riemann zeta function (1859)}, the Gamma function (1720), li(x), The elliptic integral that launched Riemann surfaces (*1854?), Chebyshev polynomials (?1854) punctured open set in C^n (Hartog's theorem *1906 ?)

Partial differential equations: Laplace equation (1773), the heat equation, wave equation, Navier-Stokes equation (1822),KdV equations (1877),

Functional analysis: Unilateral shift, The spaces $ell_p$, $L_p$ and $C(k)$, Tsirelson spaces (1974), Cuntz algebra,

Algebra: Polynomials (ancient?), Z (ancient?) and Z/6Z (Middle Ages?), symmetric and alternating groups (*1832), Gaussian integers ($Z[sqrt -1]$) (1832), $Z[sqrt(-5)]$,$su_3$ ($su_2)$, full matrix ring over a ring, $operatorname{SL}_2(mathbb{Z})$ and SU(2), quaternions (1843), p-adic numbers (1897), Young tableaux (1900) and Schur polynomials, cyclotomic fields, Hopf algebras (1941) Fischer-Griess monster (1973), Heisenberg group, ADE-classification (and Dynkin diagrams), Prufer p-groups,

Number Theory: conics and pythagorean triples (ancient), Fermat equation (1637), Riemann zeta function (1859) elliptic curves, transcendental numbers, Fermat hypersurfaces,

Probability: Normal distribution (1733), Brownian motion (1827), The percolation model (1957), The Gaussian Orthogonal Ensemble, the Gaussian Unitary Ensemble, and the Gaussian Symplectic Ensemble, SLE (1999),

Dynamics: Logistic map (1845?), Smale's horseshoe map(1960). Mandelbrot set (1978/80) (Julia set), cat map, (Anosov diffeomorphism)

Geometry: Platonic solids (ancient), the Euclidean ball (ancient), The configuration of 27 lines on a cubic surface, The configurations of Desargues and Pappus, construction of regular heptadecagon (*1796), Hyperbolic geometry (1830), Reuleaux triangle (19th century), Fano plane (early 20th century ??), cyclic polytopes (1902), Delaunay triangulation (1934) Leech lattice (1965), Penrose tiling (1974), noncommutative torus, cone of positive semidefinite matrices, the associahedron (1961)

Topology: Spheres, Figure-eight knot (ancient), trefoil knot (ancient?) (Borromean rings (ancient?)), the torus (ancient?), Mobius strip (1858), Cantor set (1883), Projective spaces (complex, real, quanterionic..), Poincare dodecahedral sphere (1904), Homotopy group of spheres, Alexander polynomial (1923), Hopf fibration (1931), The standard embedding of the torus in R^3 (*1934 in Morse theory), pseudo-arcs (1948), Discrete metric spaces, Sorgenfrey line, Complex projective space, the cotangent bundle (?), The Grassmannian variety,homotopy group of spheres (*1951), Milnor exotic spheres (1965)

Graph theory: The seven bridges of Koenigsberg (1735), Petersen Graph (1886), two edge-colorings of K_6 (Ramsey's theorem 1930), K_33 and K_5 (Kuratowski's theorem 1930), Tutte graph (1946), Margulis's expanders (1973) and Ramanujan graphs (1986),

Combinatorics: tic-tac-toe (ancient Egypt(?)) (The game of nim (ancient China(?))), Pascal's triangle (China and Europe 17th), Catalan numbers (18th century), (Fibonacci sequence (12th century; probably ancient), Kirkman's schoolgirl problem (1850), surreal numbers (1969), alternating sign matrices (1982)

Algorithms and Computer Science: Newton Raphson method (17th century), Turing machine (1937), RSA (1977), universal quantum computer (1985)

Social Science: Prisoner's dilemma (1950) (and also the chicken game, chain store game, and centipede game), the model of exchange economy, second price auction (1961)

Statistics: the Lady Tasting Tea (?1920), Agricultural Field Experiments (Randomized Block Design, Analysis of Variance) (?1920), Neyman-Pearson lemma (?1930), Decision Theory (?1940), the Likelihood Function (?1920), Bootstrapping (?1975)

pr.probability - Formal definition of 'useful' ?

It seems to me that you have two questions here.

First, you inquire about a formal account of "usefulness". I believe that this is already provided by the formal mathematical accounts of utility in utility theory. The concept of utility in that theory is extremely flexible, not limited to economics or any other specific endeavor. Thus, it seems able to provide for any account of "usefulness" you may have in mind. Let's just say that the utility provided by a given thing is equal to the "usefulness" you had in mind for it.

Your second question is more directly aimed at analyzing the usefulness of various specific mathematical ideas. For this question, I'm not sure that what is lacking is a formal definition of usefulness. After all, even if one knows a lot of formal utility theory, it doesn't help you to find out which flavor of ice cream your child likes best. Rather, what one would seem to want is ways of measuring various specific measurable aspects of that utility function. Thus, it is a problem of measurement, rather than formal theory. In the case of measuring the importance of utility or usefulness of various mathematical theorems or definitions, several people have suggested a page-rank type calculation, based on citation statistics, which I find interesting.

Another approach to this second question is the one I described in my answer to the question here, which is to analyze the mathematical relationships between the various theorems of mathematics, over a very weak base theory. This subject is known as Reverse Mathematics, and one of the most surprising conclusions (not at all obvious) of this research effort is that the great majority of classical mathematical theorems (and contemporary ones as well) fall into one of five equivalence classes. That is, most theorems turn out to be logically equivalent to one of the big five. This kind of analysis may lead you to abandon what might otherwise have been a tempting principle: that logically equivalent theorems should be equally useful.

set theory - The closure of a generic ultrapower

If your ideal is normal, fine, precipitous and has the disjointing property (a consequence of saturation), then the answer is yes. As you likely know, you need more assumptions than you had stated, just in order to know that the ultrapower is well-founded. The difference in closure for the ultrapower that you mentioned appears to be related to the difference between having the disjointing property or not.

For a reference, I recommend Matt Foreman's chapter for the Handbook of Set Theory, which states the following theorem (it is Theorem 2.25 in the preliminary version I have here, but the published number may differ).

Theorem. Suppose I is a normal, fine, precipitous ideal on $Zsubset P(X)$, where $|X|=lambda$. Let $Gsubset P(Z)/I$ be generic, and $M$ the generic ultrapower of $V$ by $G$. Then $P(lambda)cap Vsubset M$. Further, if $I$ has the disjointing property, then $M^lambdacap V[G]subset M$.

Note that this theorem covers your case of $Z=P_kappa(lambda)$.

To prove the first part, you simply observe that $[id]$ represents $j " lambda$, and then for any $Asubsetlambda$ you can get $j"A$ using the function $g(z)=zcap A$. Now, from $j"lambda$ and $j"A$ you can easily build $A$ in $M$.

For the second part, the part you were interested in, you use the disjointing property in order to know that a term for a $lambda$-sequence of elements of $M$ can be transformed into a $lambda$-sequence of terms in $M$. That is, if $langledot a_alpha :alpha<lambdarangle$ is a $lambda$-sequence of terms for objects in $M$, then disjointing allows us to find in $V$ a sequence of functions $vec g = langle g_alpha: alpha<lambdarangle$ such that $[g_alpha]^G = dot a_alpha^G$. From this, it follows that the function $g(z) = langle g_alpha(z) | alphain zrangle$ represents $j(vec g)(j"lambda)$, which is $langle j(g_alpha)_beta(j"lambda) | betain j"lambdarangle$, from which we can construct $langle j(g_alpha)(j"lambda) | alpha <lambdarangle$, which is the desired $lambda$-sequence.

ag.algebraic geometry - Example of restriction of a finite morphism which is not finite

Every closed immersion is a finite morphism. Therefore, restriction of a finite morphism to a closed subset is always a finite morphism itself. Can you give an example of quasi-projective varieties $Xsubset Y$, $Z$ and a finite morphism $f:Yto Z$ such that restriction $f:Xto f(X)$ is not finite? Same with Y -- projective?

PS. Sorry the original version of this question was hilariously stupid.

gr.group theory - Higher-dimensional braid group?

Let $Delta$ be 2-disk. Let $C(Delta;n)$ be a configuration space.

i.e.) $C(Delta;n)= lbrace (z_1,ldots,z_n)in DeltatimesldotsDelta | z_ineq z_j ~textrm{if}~ ineq j rbrace $

Then, it is well known or direct to see that $pi_1(C(Delta;n))= PB_n$, where $PB_n$ is original pure braid group of n-strands.

I heard that by using this configuration space we can easily generalize Braid group in arbitrary topological space $X$.

i.e.) We can define $PB_n(X)$ (Pure Braid group of n-strands in $X$) by $PB_n(X)=pi_1(C(X;n))$.
Also, we can study some exact sequences analogous to original braid group situation if topology of $X$ is good.

Here, but I heard that if $X$ is manifold with dimension greater than 2. Then, the structure of $PB_n(X)$ is somewhat trivial because there are enough rooms to move

I think that this phenomena occurs because we are observing too small objects in large space. Roughly speaking, this seems to be the same situation that Knot theory is trivial in codimension greater than 2.

Instead of this formulation, I hope that we could modify or generalize this configuration space set up by observing some space containg information like distribution or foliation or something like that?

Can I do this business? In short, Can we think nontrivial generalization of Braid group in higher dimensional manifold?

ag.algebraic geometry - Algebraic and Holomorphic Functions

Well, here's a few theorems that might help:

1: On a complex projective variety, a function that is meromorphic on the whole variety is a rational function. You can get this out of the embedding into projective space.

2: On a compact complex manifold, the only globally holomorphic functions are constant. This follows from the maximum principle.

Additionally, if you're looking locally, then on an affine variety, there are a LOT more holomorphic functions than algebraic functions. On $mathbb{C}$, you have $mathbb{C}[z]$ for the algebraic functions, and convergent power series for holomorphic, so $e^z$ is holo but not algebraic. But every algebraic function is holomorphic.

ag.algebraic geometry - Maximally symmetric smooth projective varieties in CP^2

By the same averaging trick that shows that finite-dimensional complex representations of a finite group are unitary with respect to some inner product, your question is equivalent to the one obtained by replacing ambient isotropy groups with linear automorphism groups in the sense of algebraic geometry. Here linear means induced by a linear automorphism of $mathbf{P}^2$. Actually, for a smooth plane curve of degree $d>3$, all automorphisms are linear, by

H. C. Chang, On plane algebraic curves, Chinese J. Math. 6 (1978), 185-189.

Fix $d>3$. Let $mathcal{H}_d$ be the moduli space of smooth degree-$d$ curves in $mathbf{P}^2$, so $mathcal{H}_d$ is an open subscheme of some projective space. Then there is a stratification of $mathcal{H}_d$ into finitely many locally closed subschemes such that the automorphism group is constant on each piece. (This could also be stated in terms of the automorphism group scheme of the universal curve over $mathcal{H}_d$.) In these terms, you are asking for the $0$-dimensional strata, or equivalently the smooth plane curves such that in a punctured neighborhood of the corresponding point of $mathcal{H}_d$ the automorphism group is strictly smaller.

The analogous question with $mathcal{H}_d$ replaced by the full moduli space $mathcal{M}_g$ of curves of genus $g>1$ has been much studied. The direct analogue of your maximally symmetric curves in this setting are the curves said to have "many automorphisms" in Section 3 of the article

Jürgen Wolfart, The obvious part of Belyi's theorem and curves with many automorphisms, pp. 97-112 in: Geometric Galois actions 1, edited by L. Schneps and P. Lochak, LMS Lecture Notes Series 342, Cambridge Univ. Press, 1997.

Wolfart's article contains many references to related work, and mentions some nice theorems. For instance: a smooth projective curve of genus greater than $1$ over $mathbf{C}$ has many automorphisms if and only if it is a Galois cover of $mathbf{P}^1$ ramified only above $0,1,infty$.

abelian varieties - Are Jacobians principally polarized over non-algebraically closed fields?

Incidentally, as I posted this question someone who knew the answer wandered into my office.

The map $M_g to A_g$ factors through the moduli space $tau_g$ of pairs (A,P,L) where A is an abelian variety, P is an A torsor, and L is an ample line bundle on P which is geometrically a principal polarization. The map $M_g to tau_g$ is given by $C mapsto (Pic_0, Pic_{g-1}, L(theta))$, where the theta divisor on $Pic_{g-1}$ is given by the image of $C^{g-1}$.

To construct the map $tau_g to A_g$, note that $Pic_0(A) cong Pic_0(P)$, so that L indeed gives a map $A to A^{vee}$ given by $a mapsto t^*_aL otimes L^{-1}$.

The point is one doesn't need to descend the theta divisor. The reference to this is 5.1 of Martin Olsson's book Compactifying moduli spaces of abelian varieties.

nt.number theory - Galois cohomology of linear groups over local fields

As Hunter and Sean noted, since the inflation map ${rm{H}}^1(L/F,G(L)) rightarrow {rm{H}}^1(F,G)$ is
injective and ${rm{H}}^1(F,G)$ is always finite (Borel-Serre), such an $L$ always exists. Below we give an explicit sufficient condition on $L$ (often satisfied) when $G$ is connected. (One could probably do better with a closer consideration of the Tate local duality aspects of the argument. I am lazy at this step.) This rests on something deeper than the Borel-Serre result: the Kneser-Bruhat-Tits theorem on vanishing of degree-1 Galois cohomology for simply connected semisimple groups over non-archimedean local fields.

First we set up some notation.
Let $U = mathcal{R}_u(G)$ denote the unipotent radical of $G$ (this is a good notion over $F$ since $F$ is perfect), and let $G' = G/U$ denote the maximal reductive quotient. The identity component $Z'$ of the center of $G'$ is an $F$-torus, and the derived group $mathcal{D}(G')$ is a semisimple group, say with simply connected central cover $mathcal{G} twoheadrightarrow mathcal{D}(G')$. The preimage $mu$ of the central
subgroup $Z' cap mathcal{D}(G')$ is a finite $F$-group of multiplicative type.
(It is the kernel of the central covering map if $Z' = 1$.)

Proposition: Assume $G$ is connected and use notation as above.
Let $F'/F$ be a finite Galois splitting field for $G'$ (thus for $Z'$ and dual of
$mu$). If $L/F$ is a finite Galois extension containing $F'$ with $[L:F']$ divisible by the order of $mu$ then ${rm{H}}^1(F,G) = {rm{H}}^1(L/F,G(L))$.

In particular, if $G$ is a split connected reductive $F$-group then $L/F$ works provided that $[L:F]$ is divisible by the order of the center of the simply connected
central cover of $mathcal{D}(G)$.

Remark: If $T$ is a maximal $F$-torus in $G$ then it maps isomorphically onto one for $G'$, so could take $F'/F$ to be splitting field for $T$.

Proof: Since $F$ has characteristic 0, the quotient map $G twoheadrightarrow G'$ admits a section $sigma$ over $F$, which is to say there exists a connected reductive $F$-subgroup $H subseteq G$ such that $H ltimes U simeq G$ via multiplication (this is a so-called Levi $F$-subgroup of $G$); beware that over any algebraically closed field $k$ with nonzero characteristic Levi subgroups can fail to exist. (A basic natural counterexample is, loosely speaking, ${rm{SL}} _2(W _2(k))$ as a $k$-group, where $W _2$ denotes length-2 Witt vectors; see Appendix A.6 in the book "Pseudo-reductive groups".)

Using $sigma$ (or $H$), the natural restriction map ${rm{H}}^1(F,G) rightarrow {rm{H}}^1(F,G')$ is surjective. It is also injective. Indeed, a standard twisting argument (as explained in Serre's book on Galois cohomology) identifies fibers with ${rm{H}}^1(F,U')$ for various $F$-forms $U'$ of $U$. But since the ground field is perfect, every smooth connected unipotent group is split (i.e., admits a composition series whose successive quotients are $mathbf{G}_a$) and hence has trivial ${rm{H}}^1$. Thus, we get the asserted bijectivity. So far we have not used anything about $F$ other than that it has characteristic 0.

We likewise have ${rm{H}}^1(E/F,U'(E)) = 1$ for any smooth connected unipotent $F$-group $U'$ and any Galois extension $E/F$, so the same argument gives that ${rm{H}}^1(E/F,G(E)) rightarrow {rm{H}}^1(E/F,G'(E))$ is bijective for any Galois extension $E/F$. Thus, the injective inflation map
$${rm{H}}^1(E/F,G(E)) rightarrow {rm{H}}^1(F,G)$$
is bijective if and only if the same holds for $G'$ in place of $G$.

Consider the central extension structure
$$1 rightarrow mu rightarrow Z' times mathcal{G} rightarrow G' rightarrow 1$$
over $F$, where the second map uses multiplication. By Kneser-Bruhat-Tits,
we have an exact sequence of pointed sets
$${rm{H}}^1(F,Z') rightarrow {rm{H}}^1(F,G') rightarrow {rm{H}}^2(F,mu)$$
and similarly over $L$, with a commutative diagram using restriction maps.

By local class field theory, the restriction map from ${rm{H}}^2(F',mu)$ to
${rm{H}}^2(L,mu)$ vanishes, so likewise for ${rm{H}}^2(F,mu) rightarrow {rm{H}}^2(L,mu)$. (This is weak; by translating restriction through Tate local duality we can surely give a better sufficient "lower bound" for such an $L$.) For any such $L$, it follows that restriction from ${rm{H}}^1(F,G')$ to ${rm{H}}^1(L,G')$ lands in the image of ${rm{H}}^1(L,Z')$. But this vanishes since the $F$-torus $Z'$ is even $F'$-split, let
alone $L$-split. Thus, ${rm{H}}^1(F,G') rightarrow {rm{H}}^1(L,G')$ vanishes, which is to say that $L$ "works" for $G'$, so the same holds for $G$.
QED

modular forms - Why are functional equations important?

The simplest reason functional equations have importance, for someone learning this stuff for the first time (not knowing about modular forms, automorphic representations, etc.) is that they can be used to verify the Riemann hypothesis numerically up to some height!

To explain this, let's start off with a limitation of methods of complex analysis in detecting zeros of functions. There are theorems in complex analysis which tell you how to count zeros of an analytic function $f(s)$ inside a region by integrating $f'(s)/f(s)$ around the boundary (this is the argument principle). So we could integrate around the boundary of a box surrounding the critical strip up to some height and see there are, say, 10 zeros of the Riemann zeta-function up to that height (yeah, there's a pole on the boundary at $s = 1$ which messes up the argument principle integration, but don't worry about that right now). How can we prove the 10 zeros in the critical strip up to that height are on the critical line? Complex analysis provides no theorems that assure you an analytic function has zeros on a line!

The functional equation comes to the rescue here. I'll illustrate for the Riemann zeta-function $zeta(s)$. Its functional equation is most cleanly expressed in terms of

$$Z(s) = pi^{-s/2}Gamma(s/2)zeta(s)$$

and is the following:

$$Z(1-s) = Z(s).$$

We also need another "symmetry": $Z(s^*)^* = Z(s)$, where ${}^*$ means complex conjugation.
Where does this come from? For an entire function $f(s)$, the function $f(s^*)^*$ is also entire: in fact its local power series expansion at any point a is the one whose coefficients are complex conjugate to the coefficients of $f(s)$ at $a^*$. Or you could directly prove $f(s^*)^*$ is complex-differentiable when $f(s)$ is. The significance of this is that if $f(s)$ is real-valued for some interval of real numbers then $f(s^*)^* = f(s)$ on that interval, so by the rigidity of analytic functions we must have $f(s^*)^* = f(s)$ everywhere when it is true on a real interval (not one point intervals, obviously). Lesson: an entire function $f(s)$ that is real-valued on some interval of the real line satisfies the formula $f(s^*)^* = f(s)$ for all complex numbers $s$. By the way, this also applies to meromorphic functions on $mathbf C$ too (rigidity of meromorphic functions).

Let's now return to the zeta-function. Because $zeta(s), pi^{-s/2}$, and $Gamma(s/2)$ are real-valued for real $s > 1$, their product $Z(s)$ is real for $s > 1$, so $Z(s^*)^* = Z(s)$ for all complex $s$. In particular, for a number $s = frac12 + it$ on the critical line (here $t$ is real),
we have the key calculation

$$Z(s)^* = Z(1/2 + it)^* = Z(1 - (1/2 + it))^* = Z(1/2 - it)^* = Z((1/2 + it)^* )^* = Z(1/2 + it) = Z(s),$$

where we used $Z(s) = Z(1-s)$ in the second equation and $Z(s^*)^* = Z(s)$ in the second to last equation.

This tells us the function $Z(s)$ is real-valued on the critical line. The Riemann zeta-function is not real-valued on the critical line, but this modified (completed) zeta-function $Z(s)$ is. Moreover, because $Z(s)$ differs from $zeta(s)$ by factors that are finite and nonzero inside the critical strip ($pi^{-s/2}$ is a nowhere-vanishing entire function and $Gamma(s/2)$ is meromorphic with no zeros and only has poles at $s = 0, -2, -4, dots$), the zeros of $zeta(s)$ and $Z(s)$ inside the critical strip are the same thing. (In fact, nontrivial zeros of $zeta(s)$ are exactly the same thing as all zeros of $Z(s)$, which is one reason $Z(s)$ is a nicer object that $zeta(s)$: the Riemann hypothesis is a statement about all zeros of $Z(s)$!) So what? Well, we just showed in the key calculation above that the function $Z(1/2 + it)$ is real when $t$ is real, so by computing we can provably detect zeros of $Z(s)$ on the critical line Re($s$) = $frac12$ by looking for sign changes of $Z(1/2 + it)$ as t runs through the real numbers.

So here is a two-step procedure for proving the RH numerically up to height $ T$ (i.e., in the box in the critical strip from the real axis up to height $T$):

1. Use complex analysis (the argument principle) to count how many zeros $Z(s)$ has in the critical strip up to height $T$ by integrating $Z'(s)/Z(s)$ around a box surrounding that region. (If the poles of $Z(s)$ at $s = 0$ and $s = 1 $ bother you, recall the argument principle can account for poles or you might prefer to use $s(1-s)Z(s)$ in place of $Z(s)$ to be working with an entire function which satisfies the same functional equation as $Z(s)$ and is also real-valued on the critical line.)




2. Count sign changes for $Z(1/2 + it)$ when $0 le t le T$. There is a zero between any two sign changes, so $Z(s)$ has at least as many zeros on the critical line as the number of sign changes that were found. (Finding a sign change is a computable thing: if a function value at a point is approximately positive or negative then it is provably so by checking the error in your computation well enough, whereas proving a function value at a point is exactly zero with a computer is basically impossible.)

If the counts in steps 1 and 2 match, then voila: all zeros of $Z(s)$ up to height $T$ in the critical strip are on the critical line, which confirms the Riemann hypothesis up to height $T$.

This method will not work if there are any multiple zeros on the critical line: the argument principle counts each zero with its multiplicity, so if for instance there is a double zero then the argument principle may tell us $Z(s)$ has 10 zeros (with multiplicity!) up to some height while we find only 9 sign changes because one zero is a double zero so it doesn't give us a sign change. (Or if there were a triple zero we get 10 zeros with multiplicity from the argument principle but we find only 8 sign changes.) A graph may suggest that the mismatch in the numbers in the two steps is coming from a multiple zero, but it doesn't rigorously prove anything. Fortunately, this has never happened in practice with the Riemann zeta-function: the two counts always match. In fact the conjecture is that all nontrivial zeros of $zeta(s)$ are simple zeros.

What about more general L-functions $L(s)$? By multiplying $L(s)$ by suitable exponential and Gamma functions, you get a function $Lambda(s)$ whose functional equation is

$$Lambda(1-s^*)^* = wLambda(s),$$

where $w$ is a constant with absolute value 1. (For the Riemann zeta-function, $Lambda(s) = Z(s)$ and $w = 1$. For Dirichlet L-functions, $w$ is usually not equal to 1.) Let $u$ be one of the square roots of $w$, so $w = u^2$. Then using the above functional equation, the function

$$frac1u Lambda(s)$$

is real-valued on the critical line ($s = 1/2 + it$ for real $t$), so we can detect its zeros there by looking for sign changes. The same method described above for detecting zeros of $zeta(s)$ in the critical strip by using $Z(s)$ and its functional equation can be applied also to $L(s)$. This is basically the way all variants on the Riemann hypothesis are checked numerically (modulo important details of practical calculation that I don't get into), and the functional equation is an essential ingredient in justifying the method.

What is crucial here is not just the idea of sign changes, but also the expectation that the zeros are all simple (so we can find all the zeros by sign changes and the argument principle). As with the Riemann zeta-function, it is expected that the nontrivial zeros of Dirichlet $L$-functions are all simple. But there are examples of $L$-functions with a multiple zero on its critical line, thanks to ideas from the Birch and Swinnerton-Dyer conjecture. This does not wreck this approach to verifying the Riemann hypothesis for such L-functions, because such multiple zeros are supposed to happen only at one (known) point which we think we understand.

pr.probability - Formula for the nth convolution of a laplace random variable

One way to generate a Laplace random variable is to generate two IID (independent and identically distributed) exponential random variables and then subtract them:
x_i = y_i - z_i
with y_i and z_i ~ exponential(parameter=b), and of course everything independent.
Then the sum of the x_i is simply (sum y_i) - (sum z_i); each of those two sums have Gamma distributions. To be more specific, since we are summing an integer number of terms, they have Erlang distributions. The difference of two Gammas is called "bilateral gamma", and there are a few papers out there on it. A quick search just found:

Bilateral gamma distributions and processes in financial mathematics
Uwe Küchlera, Stefan Tappe

On the shapes of bilateral Gamma densities
Uwe Küchlera, Stefan Tappe

It would be nice if someone would write a Wikipedia article about bilateral Gammas, I guess.

ca.analysis and odes - Which sequences can be extended to analytic functions? (e. g., Ackermann's function)

Let {a_n} be a sequence of complex numbers indexed by the positive integers. Does there always exist an analytic function f such that f(n) = a_n for n=1,2,...? If not, are there any simple necessary or sufficient conditions for the existence of such f? This analytic function should be defined on some connected domain in the complex plane containing the positive integers.

To make this concrete, consider Ackermann's function, which is defined recursively: first define the sequence of functions A_k, k=1,2,..., as

A₁(n) = 2n,
A_k(1) = 2,
A_k(n) = A_k-1(A_k(n-1)),

and then define Ackermann's function as the diagonal A(n) = A_n(n) for n >= 1. Does there exist an analytic function f such that f(n) = A(n) for n = 1,2,...?

Actually, the individual functions A_k are interesting as well. A₁(n) = 2n, as given above; A₂(n) = 2ⁿ, and A₃(n) = 2^(2^(...2^2)) (with n twos in the expression). Obviously, A₁ and A₂ have analytic extensions. According to Wikipedia (which uses a slightly different definition and notation), analytic extensions of A₃ or A_k for any other k aren't known, but from the language, it isn't clear whether the existence of an extension is itself in question, or whether one simply hasn't been found yet. Also, it doesn't say anything about the diagonal A(n) (unless I missed it).

There are many other obvious sequences that don't seem to have obvious analytic extensions, like the prime-counting function (just to name one!). As far as my knowledge is concerned, this seems more like the rule than the exception. My knowledge here is admittedly very limited, though, so anything at all that you can share will probably teach me something.

gr.group theory - Automatic groups - recent progress

Epstein's (et al.) "Word Processing in Groups" is a quite comprehensive monograph on automatic groups, finite automata in geometric group theory, specific examples like braid groups, fundamental groups of 3-dim manifolds etc. However, the book is from 1992, so much of the material summarizes research done by Cannon, Thurston, Holt etc. back in the '80s. I'm interested in how the theory of automatic groups (and, more generally, applications of formal languages in group theory) has progressed since then - have there been any significant new results, open problems, novel ideas, examples?

co.combinatorics - Seeking reference for the enumerative "mass formula" concept

I do call such things "mass formulas", but then again I am a number theorist, and one of my colleagues is a quadratic form theorist who specializes in such things. So this is mostly an expression of my specific mathematical culture.

I do not think that it is a standard term, at least not the only standard term. For instance, from another MO answer I noticed that some categorists call this the groupoid cardinality. This term in fact seems quite sensible to me, because the concept seems closely related to taking a quotient by the action of a group with nontrivial stabilizers and regarding the quotient set as a groupoid rather than a mere set.

As you say, combinatorially minded people speak of "Polya theory" or "counting with symmetry". Many algebraic geometers, upon seeing this phenomenon, would use the word "stacky". I wouldn't be surprised if there were other terms as well.

Overall I think this has the effect that a lot of people are partially rediscovering what is essentially the same concept. I would very much like to see a reasonably authoritative treatment of this subject appealing to mathematicians from different fields. Of course, I also look forward to seeing (better!) answers to this question.

pr.probability - Distribution under operations

I don't think there's any reason for it to have a nice distribution. After fooling around with it a bit, the following seem to be true:

*It has infinite variance (Not too hard to show, X/Y has infinite variance, and the other random variables just increase it)

*Pretty sure it has an infinite mean (Empirically, the sample-mean seems to be stationary, and theoretically, there's a bounding argument with a Cauchy that I'm not positive of.

Any specific questions about the distribution?

ds.dynamical systems - Is there an intrinsic definition of fractal (i.e. not embedded in euclidean space)?

To the best of my knowledge there is no universally agreed upon precise definition of the word "fractal", so it's not clear to me exactly what would or would not constitute an example of a fractal that is not embedded in Euclidean space.

However, the various quantities referred to as "fractal dimension" -- Hausdorff dimension, box dimension, etc. -- do not actually require an ambient Euclidean space for their definition. All you need is a metric on the set X under consideration -- this is enough to define "balls of radius r", and once you can do that the definition of Hausdorff dimension, box dimension, etc. goes through exactly as in the Euclidean case.

In fact, there's a very general framework for all these dimensional quantities (for me the standard reference is "Dimension Theory in Dynamical Systems" by Yakov Pesin), which can be formulated in a setting completely independent of Euclidean space.

As a possible example of a "non-Euclidean fractal", I would consider the symbolic space $Sigma_2^+ = {0,1}^mathbb{N}$ with a metric such as $d(x,y) = 2^{-t(x,y)}$, where $t(x,y)$ is the first coordinate in which x and y differ. This is homeomorphic to the Cantor set but not embedded in Euclidean space.

traces - Get rid of tr() in SVM kernel trick

If $A,B$ are arbitrary $ntimes n$ matrices, by definition of trace, $textrm{tr}(AB) = sum_{i,j} A_{ij}B_{ji}$. This is $O(n^2)$, but just reading the entries of $A$ is $Omega(n^2)$. Without any special structure on $A,B$, you probably can't do better.

If $A,B$ are (column) vectors, you probably mean the outer product $textrm{tr}(AB^T) = sum_i A_i B_i$.

Edit: andinos clarified to say he wants to know about the implicit mapping of the kernel function. Well I have bad news: It does not exist!! The proof works by showing there exist matrices $A,B$ such that the corresponding kernel matrix is not positive semi-definite. To finish, apply Mercer's theorem.

In particular, set $A = left(begin{array}{cc}1 & 1 \\ -1 & 1end{array}right)$ and $B = A^T = left(begin{array}{cc}1 & -1 \\ 1 & 1end{array}right)$. Therefore $textrm{tr}(AB) = textrm{tr}(AA^T) = 4$, and $textrm{tr}(BA)$ is identical. On the other hand, $textrm{tr}(AA) = textrm{tr}(BB) = 0$. therefore, the kernel matrix $K$ is $left(begin{array}{cc}0 & 4 \\ 4 & 0end{array}right)$. Set $x = left(begin{array}{c} 1 \\ -1end{array}right)$, and observe that $x^T K x = -8 < 0$, and therefore $K$ is not PSD, so the kernel $k(A,B) = textrm{tr}(AB)$ is not PSD.

On the other hand! If you had instead defined your kernel to be $k'(A,B) = textrm{tr}(AB^T)$, notice that $k'(A,B) = sum_{i,j}A_{ij}B_{ij} = Phi(A)^TPhi(B)$ where $Phi$ simply takes its input matrix and outputs it as a column vector.

gr.group theory - Jordan Hölder decomposition for group objects

You can start by looking at the paper by P.J. Hilton and W. Ledermann, "On the Jordan-Hölder theorem in homological monoids", where three axioms are needed to establish the decomposition, and the third one is essentially guaranteeing the second isomorphism theorem.

In "Mal'cev, protomodular, homological and semi-abelian categories" by F. Borceux, D. Bourn, there is a chapter devoted to homological categories (which are pointed, regular and protomodular), these are the categories where certain lemmas of homological algebra hold true (five lemma, nine lemma, snake lemma, Noether isomorphism theorems etc.). The fact that Jordan-Holder holds for these categories is proven in "Jordan-Holder, Modularity and Distributivity in Non-Commutative Algebra" by F. Borceux, M. Grandis.

Congruence Subgroups as Open Subgroups of the Modular Group Under the Right Topology

To expand Henry Wilton's concise answer, the Congruence Subgroup Problem has a distinguished history including important work by Serre and a number of others (exploiting effectively the congruence topology). See for example:
MR0272790 (42 #7671) 14.50,
Serre, Jean-Pierre,
Le probl`eme des groupes de congruence pour SL2. (French)
Ann. of Math. (2) 92 1970 489–527.

This sort of topology on a group originates earlier, but the application here is highly original.

ADDED: Like many other journal articles, the one mentioned here by Serre is available in PDF format but only through JSTOR (or other library resource). There is a lot of literature, including my 1980 Springer Lecture Notes 789 Arithmetic Groups which cover some of the background as well as an expository account of Matsumoto's thesis.

complex dynamics - Help determining the asymptotic behavior of an integral involving rational functions.

If I understand your problem correctly, i.e. that $mu$ is the usual metric on the Riemann sphere, then you're asking if essentially all orbits are expansive, at least with respect to that metric.

This will almost always be the case. For example, it will be so whenever the Julia set is holomorphically removable. The only case which is doubtful is when the Julia set is the whole of the Riemann sphere and the forward orbit of the critical point(s) are dense in the sphere -- which can happen [there are nice non-Lattes examples of this by M. Rees, I think the paper dates from 1984 or so]. It could still be the case that that is not enough to dampen the integral, if return times to a given neighborhood are too long.

I have a sneaky feeling that this might happen only in the case of an invariant line field -- and a little Googling brings up a recent paper by Xiaoguang Wang showing that this (essentially) doesn't happen.

[Take the conjectures with a grain of salt, last time I did complex dynamics was 13 years ago!]

lo.logic - How constructive is Doyle-Conway's 'Division by three'?

The construction in the paper seems to rely on two non-constructive assumptions:

1. We can decide whether two elements in a set (involved in the division by 3) are equal.


2. A countable subset of $mathbb{N}$ is infinite or not infinite.

(By "infinite" I mean "contains an infinite sequence of pairwise distinct elements".)
In computability theory the second assumption corresponds to Turing degree $0''$.

To see where the second assumption is used, consider the proof of Lemma 2 on page 26. There one is given an infinite sequence of 0's, 1's and 2's and one must decide whether there are infinitely many 0's in the sequence (and if not, whether there are infinitely many 1's). Let us show that such a decision procedure is equivalent to the second assumption. In one direction, a ternary sequence contains infinitely many 0's iff the set of indices at which the 0's appear is infinite. Conversely, given a countable subset $A subseteq mathbb{N}$ enumerated by $e$, consider the sequence $a_0, a_1, ldots$ where

$a_k = 0$ if $e$ enumerates a new element at step $k$, and
$a_k = 1$ otherwise.

The sequence has infinitely many 0's iff $A$ is infinite.

Another kind of a typical construction in the paper requires one to determine whether the orbit of an element $x$ under a bijection is finite or infinite. We can do this using our assumptions as follows. Given $x in A$ and a bijection $f : A to A$, construct a sequence $a_0, a_1, ldots$ as follows:

$a_k = 0$ if there is $m leq k$ such that $x = f^m(x)$, and
$a_k = 1$ otherwise.

Here we assumed that $A$ has decidable equality. The sequence $a_k$ contains a zero iff it contains infinitely many zeroes (thus we only require a $0'$ oracle to perform the following steps). If it contains a zero, say $ak = 0$ then the orbit $lbrace x, f(x), f^2(x), ldots rbrace$ is finite with at most $k$ elements. If it does not contain a zero then the orbit is infinite because $f^k(x) neq f^j(x)$ for all $k neq j$, as otherwise we would have $f^{|k-j|+1}(x) = x$.

Let me just remark that one might be tempted to consider a non-constructive assumption such as:

A group generated by a single element is either infinite or finite.

(This would certainly allow us to determine whether orbits of elements under bijections are finite or infinite.) In fact division by 3 follows, but for a rather strange reason, namely that such a principle implies the law of excluded middle. Suppose $p$ is an arbitrary thruth value, and consider the Abelian group $G$ freely generated by the generators $p$ and $top$ (true). Consider the subgroup of $G$ generated by the element $top - p$. If it is infinite then there is $n in mathbb{N}$ such that $n top neq n p$, hence $top neq p$ and so $lnot p$ holds. If the subgroup is finite then there is $n > 0$ such that $n top = n p$, hence $top = p$ and $p$ holds. (I hope I got this right, we have to be careful because finite sets need not have definite sizes.)

This hopefully gives us some idea about how non-constructive are the techniques employed in the proof of division by three (essentially it looks like a $0''$ oracle). It seems hard to quantify how non-constructive the theorem itself is. Knowing that I can divide by 3 does not obviously allow me to derive non-constructive consequences. For all I know, some suitably constructivized version of division by 3 might actually be constructively valid.

Can I have a green flag now, please?