Uniformization in Descriptive Set Theory

I'm a beginner in descriptive set theory.

There is a series of connected exercises (1C.6, 1C.7, 1C.8) in Moschovakis' classic text (new edition) on uniformization. They are simple case uniformization, reduction (by uniformization), and separation of sets (via reduction).

It seems like with such layout, the point of uniformization is to give us a way to separate sets.

My question is, why are we interested in uniformization and reduction? What I can see is that uniformization can always be carried out with AC, pretty obvious. So, has it anything to do with Choice?

What about reduction?

ag.algebraic geometry - K3 over fields other than C?

The "standard" definition of a K3 surface is field independent (unless you are a physicist):

$p_g=1, q=0$, and trivial canonical class.

Some results:

• Mumford and Bombieri showed that you get (just as in the complex case) a 19 dimensional family of K3 surfaces for any degree (the 19 dimensional thingy is a deformation theory argument which is completely algebraic).


• Deligne showed that all the K3 surfaces in finite characteristics are reductions mod p.

What you obviously don't get is the fact that all these spaces sit together in a nice 20 dimensional complex ball. I also don't know if you can carry over any of the recent Kodaira dimension computation of these moduli (which are very analytic in nature).

Reference: Complex algebraic surfaces (Beauville): Chapter VIII and Appendix A.

ac.commutative algebra - Flatness and local freeness

By request, my earlier comments are being upgraded to an answer, as follows. For finitely generated modules over any local ring $A$, flat implies free (i.e., Theorem 7.10 of Matsumura's CRT book is correct: that's what proofs are for). So the answer to the question asked is "no". The CRT book uses the "equational criterion for flatness", which isn't in Atiyah-MacDonald (and so is why the noetherian hypothesis was imposed there). This criterion is in the Wikipedia entry for "flat module", but Wikipedia has many entries on flatness so it's not a surprise that this criterion under "flat module" would not be appropriately invoked in whatever Wikipedia entry was seen by the OP.

An awe-inspiring globalization by Raynaud-Gruson (in their overall awesome paper, really with authors in that order) is given without noetherian hypotheses: if $A$ has finitely many associated primes (e.g., any noetherian ring, or any domain whatsoever) and if $M$ is a finitely generated flat $A$-module then it's finitely presented (so Zariski-locally free!). See 3.4.6 (part I) of Raynaud-Gruson (set $X=S$ there). By 3.4.7(iii) of R-G, the finiteness condition on the set of associated primes cannot be removed, as any absolutely flat ring that isn't a finite product of fields provides a counterexample. (An explicit counterexample is provided by the link at the end of Daniel Litt's answer, namely a finitely generated flat module that is not finitely presented, over everyone's favorite crazy ring $prod_{n=0}^{infty} mathbf{F}_2$.)

complex geometry - Prevalence of B-fields

The short answer is that both B-fields are the same object!

The way the B-field comes to us from string theory it doesn't come alone, but comes together (among other fields) with the Riemannian metric. Due to the way both originate in the string, they are interrelated by what is called T-duality that mixes them and shows that both fields have to be regarded as two aspects of one and the same unified entity.

Physicists had understood various aspects of how these two fields unify, when Nigel Hitchin came along and noticed that there is a nice and useful mathemtical formalization of what is going on. This is the origin of generalized complex geometry.

But some aspects of the picture are still mising. For instance it is well-know that in full beauty the B-field is a gerbe with connection . Last I checked, this is represented in generalized complex geometry only rationally , meaning that the integral degree 3 class of this gerbe is seen only in its image in deRham cohomology.

This has to do with the fact that generalized complex geometry is really a theory of Couran algebroids (certain Lie 2-algebroids) and it is only their integration that knows about the full Lie 2-groupoids that yield the gerbe.

(I think I know the full story, but it is not written up yet.)

ho.history overview - What is the situation with Hilbert's Fifth Problem ?

The OP says:

" ...Recently, Palais wrote about it in the Notices but he only treats the old story from the 1950s and seems not to be aware of Olver’s facts."

Actually, I am aware of Olver's work and also Sören Illman's contribution.

Sören is an old friend and wrote to me somewhat miffed that I did not mention his work on the problem. What he proved was a very nice fact---that if a proper Lie group action is differentiable, then it can be made real analytic. As I pointed out in my article, there are very simple examples that Hilbert should have noticed (see my article---linked below---if you think I am being hard on Hilbert) that show that without properness this is false.

As for Olver, his contribution is also nice but a little off the beaten track. Here is a quick version. One facet of what Hilbert asked was whether a "local Lie group" (i.e., an open set in $R^n$ with a continuous group operation and inverse defined near the identity) could always be embedded in a global Lie group. Cartan anwered that in a way that suffices for all practical purposes; he showed that after cutting back the original neighborhood to a smaller one it could be embedded. However a number of people (including Malcev and Douady) showed that without cutting back the answer could be "no". Their examples were infinite dimensional however, and Olver in his paper "Non-Associative Local Lie Groups" provided a class of finite dimensional examples.

OK, so why didn't I mention the work of Illman, Olver and a host of others who worked on the Fifth Proble after the 1950s. If you look at my article, available for download here:

http://www.ams.org/notices/200910/rtx091001236p.pdf

the answer is clear. My article was part of a larger memorial artcle for Andy Gleason (my PhD advisor) and it was titled "Gleason's Contribution to the Solution of the Hilbert Fifth Problem". There was plenty to talk about there, and a discussion of other contributions to the Fifth Problem that happened decades later would have been out of place.

By the way, in regard to what is called "Route B" in an answer above, the first section of my article is titled "What IS Hilbert's Fifth Problem" in which I try to explain aat least a little bit about how and why Hilbert's original statement of the Fifth Problem morphed over time.

dg.differential geometry - Geometric calculations using Grassmann variables

Physicists seem to get huge computational value by introducing Grassmann variables and Grassmann integration into differential geometric calculations.

See: http://en.wikipedia.org/wiki/Grassmann_number

Can someone here motivate these techniques mathematically, and include the simplest pure-math example where their use and value can be illustrated. I have thought they were invented for computing volumes of constrained moduli spaces, although physicists did not originally describe them this way. Do any mathematicians use them rigorously to actually solve problems?

nt.number theory - Proving non-existence of solutions to $3^n-2^m=t$ without using congruences

I made a passing comment under Max Alekseyev's cute answer to this question and Pete Clark suggested I raise it explicitly as a different question. I cannot give any motivation for it however---it was just a passing thought. My only motivation is that it looks like fairly elementary number theory but I don't know the answer.

OK so one problem raised in the question linked to above was "prove there are no solutions to $3^n-2^m=41$ in non-negative integers" and Aleksevev's answer was "go mod 60". It was remarked afterwards that going mod 601 or 6553 would also nail it. For example, modulo 6553 (which is prime), 3 has order 39, 2 has order 117, but none of the 39 values of $3^n-41$ modulo 6553 are powers of 2 modulo 6553.

My question (really just a passing remark) is:

Is there an integer $t$ such that the equation $3^n-2^m=t$ has no solutions in non-negative integers $m$, $n$, but for which there are solutions modulo $N$ for all $Ngeq1$? (By which of course I mean that for each $Ngeq1$ the equation is satisfied mod $N$ for some integers $m,ngeq0$ depending on $N$; I am not suggesting that $m$ and $n$ be taken modulo $N$ or are independent of $N$).

This for me looks like a "Hasse principle" sort of thing---in general checking congruences doesn't give enough information about solvability of the polynomial in integers and there are many examples of such phenomena in mathematics. As exponential Diophantine equations are harder than normal ones I would similarly expect the Hasse Principle to fail here, but others seemed to be more optimistic.

ho.history overview - Papers that debunk common myths in the history of mathematics

I like this question very much - many popular history of mathematics books seem filled with legends more than history.

I would expand the question "What are some good papers that debunk common myths...?" to include books as well as papers. Maybe the best books to debunk myths are books that directly discuss and include the primary source material (in translation, perhaps). A fantastic recent book in this spirit is "The Mathematics of Egypt, China, India, and Islam: A Sourcebook," edited by Victor J. Katz. This is a great value as well! For example, an scholarly translation of the Chinese "Nine Chapters on the Mathematical Art" costs around 350 dollars on Amazon -- but one can instead find it in this sourcebook, together with a multitude of other translated texts, for around 50 or 60 dollars.

To demonstrate that this book addresses your specific question, on pages 467-477 you can find a translation of the Bijaganita of Bhaskara II. At the end is Verse 129, the end of which is translated, "Hence, for the sake of brevity, the square-root of the sum of the squares of the arm and upright is the hypotenuse: thus it is demonstrated. And otherwise, when one has set down those parts of the figure there, [merely] seeing [it is sufficient].

The author of this section then mentions "These verses are presumably the ultimate source of the widespread legend that Bhaskara gave a proof of the Pythagorean theorem containing only the square figure shown in figure 4.19 and the word 'Behold!' "

The figure (4.19 in the book) is not among the verses in an old text, as far as I know. I think that Indian texts of the period were traditionally written on palm leaves (which degrade somewhat quickly), and copied every generation or two, so we don't have very old texts. In any case, the "Behold!" legend for the Pythagorean theorem seems to be a myth or at least a vigorous embellishment of history.

st.statistics - Boxplot IQR and confidence interval

My answer didn't seem to score any points with anyone, and rdchat's answer is lousy, so let's look more closely.

Suppose $X_1,dots,X_n$ are an i.i.d. sample from a normally distributed population with unknown mean $mu$ and unknown variance $sigma^2$, and we seek a confidence interval for the population mean. As usual, let $overline{X} = left(X_1 + cdots + X_nright)/n$ be the sample mean and $S^2 = 1/(n-1)sum_{i=1}^n (X_i - overline{X})^2$ be the (unbiased) sample variance. (BTW, unbiasedness is overrated. Everybody knows that, except some non-statisticians. Apparently there are lots of those.)

Now
$$
frac{overline{X} - mu}{sigma/sqrt{n}}
$$
is normally distributed with mean 0 and variance 1, and
$$
frac{overline{X} - mu}{S/sqrt{n}}
$$
has a Student's t-distribution with $n-1$ degrees of freedom (called "Student's" because it's named after William Sealey Gosset, of course---and some of the content of this forum makes one suspect that a lot of people here don't know that standard bit of folklore). Go to the table and look up the value of $A_n$ for which
$$
Prleft( -A_n < frac{overline{X} - mu}{S/sqrt{n}} < A_n right) = frac{1}{2},
$$
or in other words
$$
Prleft(overline{X} - A_n frac{S}{sqrt{n}} < mu < overline{X} + A_n frac{S}{sqrt{n}}right) = frac{1}{2}.
$$
Then
$$
overline{X} pm A_n frac{S}{sqrt{n}}
$$
are the endpoints of a 50% confidence interval for $mu$.

Important point: The length of the confidence interval goes to 0 as the sample size increases, since $sqrt{n}$ is in the denominator (and $A_n$ approaches the value one would get for the normal distribution rather than for Student's distribution). But the sample quartiles do not get closer together in the limit as $n$ grows, since ("almost surely") they approach the population quartiles.

So the answer is NO.

functional equations - approximately linear functions -- more

Suppose $f,g$ are continuous functions from $mathbb R$ to $mathbb R$, with the property that
$$f(x)+f(y)=g(x+y)$$
for all $x,y$. Taking $x=y=z/2$ implies that $g(x)=2f(x/2)$ so that the above condition becomes
$$f(x)+f(y)=2f((x+y)/2).$$
This is known as Jensen's functional equation, and it implies that $f$ is linear.

There's also a generalization of Jensen's equation (I've seen it in work of Rassias, but it could be earlier): if $|f(x)+f(y)-2f((x+y)/2)|leqepsilon$ (and assuming WLOG that $f(0)=0$), then there is a linear function $L$ such that $|f(x)-L(x)|leq epsilon$.

What I am interested in a generalization of all this: Suppose there are independent random variables $X,Y$ such that
$$E[(f(X)+f(Y)-g(X+Y))^2]leqepsilon.$$
Is it possible to say anything about $f$ being (appropriately) approximately linear?

ag.algebraic geometry - Are any two K3 surfaces over C diffeomorphic?

Let $S$ be a K3 surface over $mathbb{C}$, that is, $S$ is a simply connected compact smooth complex surface whose canonical bundle is trivial. I recall reading somewhere that any two such surfaces are diffeomorphic, however I can't for the life of me remember where, or how the proof goes.

Does anybody know a good reference to a proof, or can provide a proof?

Thanks,
Dan

ag.algebraic geometry - Why does the naive definition of compactly supported étale cohomology give the wrong answer?

It is important in etale cohomology, as it is topology, to define cohomology
groups with compact support --- we saw this already in the case of curves in
Section 14. They should be dual to the ordinary cohomology groups.

The traditional definition (Greenberg 1967, p162) is that, for a manifold
$U$,
$
H_{c}^{r}(U,mathbb{Z})=dlim_{Z}H_{Z}^{r}(U,mathbb{Z})
$
where $Z$ runs over the compact subsets of $U$. More generally (Iversen 1986,
III.1) when $mathcal{F}$ is a sheaf on a locally compact topological space
$U$, define
$
Gamma_{c}(U,mathcal{F})=dlim_{Z}Gamma_{Z}(U,mathcal{F})
$
where $Z$ again runs over the compact subsets of $U$, and let $H_{c}%
^{r}(U,-)=R^{r}Gamma_{c}(U,-)$.

For an algebraic variety $U$ and a sheaf $mathcal{F}$ on $U_{mathrm{et}}$,
this suggests defining
$
Gamma_{c}(U,mathcal{F})=dlim_{Z}Gamma_{Z}(U,mathcal{F}),
$
where $Z$ runs over the complete subvarieties $Z$ of $U$, and setting
$H_{c}^{r}(U,-)=R^{r}Gamma_{c}(U,-)$. However, this definition leads to
anomolous groups. For example, if $U$ is an affine variety over an
algebraically closed field, then the only complete subvarieties of $U$ are the
finite subvarieties, and for a finite subvariety $Zsubset
U$,
$
H_{Z}^{r}(U,mathcal{F})=oplus_{zin Z}H_{z}^{r}(U,mathcal{F}).
$
Therefore, if $U$ is smooth of dimension $m$ and $Lambda$ is the constant
sheaf $mathbb{Z}/nmathbb{Z}$, then
$
H_{c}^{r}(U,Lambda)=dlim H_{Z}^{r}(U,Lambda)=oplus_{zin U}H_{z}%
^{r}(U,Lambda)=oplus_{zin U}Lambda(-m)$ if $r=2m$, and it is 0 otherwise
These groups are not even finite. We need a different definition...

If $jcolon Urightarrow X$ is a homeomorphism of the topological space $U$
onto an open subset of a locally compact space $X$, then
$
H_{c}^{r}(U,mathcal{F})=H^{r}(X,j_{!}mathcal{F})
$
(Iversen 1986, p184).
We make this our definition.

From Section 18 of my notes: Lectures on etale cohomology.

qa.quantum algebra - Suppose C and D are Morita equivalent fusion categories, can you say anything about R I: C->Z(C)=Z(D)->D?

If C and D are (higher) Morita equivalent fusion categories, then the Drinfel'd centers Z(C) and Z(D) are braided equivalent. Given any fusion category C we have a restriction functor Z(C)->C (by forgetting the "half-braiding"), and adjoint to that an induction functor C->Z(C).

If C and D are Morita equivalent then you can compose the induction and restriction to get a functor C->Z(C)=Z(D)->D. (Actually now that I think about you may need to fix the Morita equivalence in order to actually identify Z(C) and Z(D)?) Is there anything nice one can say about this composition? If C=D then Etingof-Nikshych-Ostrik says that $R circ I(V) = sum_X X otimes V otimes X^*$.

The reason that I ask is that Izumi calculated the induction and restriction graphs for the Drinfel'd center of one of the even parts of the Haagerup subfactor, and I would like to understand the same picture for the other even part.

nt.number theory - When is $n/ln(n)$ close to an integer?

[Edited mostly to extend the computation from $1.5 cdot 10^{13}$
to a bit over $2^{50} > 10^{15}$ and give the heuristics for expected number of
records for $| r(n) |$ vs. $log n cdot | r(n) |$]

Just ran across this. I see that Kevin's answer completely settles the
original question, but meanwhile Will Jagy raised the question of
finding new record lows for
$$
log n cdot left| frac{n}{log n} right|
$$
and proving their infinitude. I next outline a proof that there are
infinitely many such record lows, and then report on a computation of
all such $n$ up to $1.5 cdot 10^{13}$.

For the infinitude: Since $r(n) := n / log n$ can never be an exact integer,
it is enough to prove that for each $epsilon > 0$
there exist infinitely many solutions of $| r(n) | < epsilon/log n$.
In fact it's not hard to show that $| r(n) |$ can get as small as some
negative power of $n$, because $r(n)$ is almost linear
(its second derivative is $o(n^{-1})$ as $n rightarrow infty$)
and we can choose $n_0$ to make $r'(n_0)$ as far as possible from
any rational number. If I did this right, we can find intervals
$|n - n_0| leq h$ in which $min_n | r(n) | ll h^{-1}$
where $h^{-1} = |r''(n_0)|^{1/3} sim (n_0 log^2 n_0)^{-1/3}$.
For instance, we may choose $n_0$ so that
$r'(n_0) = 1 / (k + sqrt 2)$ for $k = 1, 2, 3, ldots$
[that is, so that $log n_0$ solves the quadratic equation
$lambda^2 = (k+sqrt2) (lambda-1)$].
On such an interval, $r(n)$ is approximated by $r(n_0) + r'(n_0)(n-n_0)$
to within $O(r''(n_0) (n-n_0)^2) = O(h^2/h^3) = O(h^{-1})$, and
(since $h$ grows much faster than $k$)
the arithmetic sequence with common difference $r'(n_0)$
is close enough to being equidistributed that it comes within
$O(1/h)$ of an integer. [We probably expect that $| r(n) |$
is random enough that it gets as small as $c/n$ or even $o(1/n)$,
but proving such a result must be well out of reach.]

For the numerical search, the problem is quite similar to
MO.19170
on nearly-integral values of $log_{10} n!$ (since $n/ log n$,
like $log_{10} n!$, is nearly linear in $n$). Again it takes time
only $tilde O(N^{2/3})$ to find all examples with $n < N$ using
a linear-approximation technique such as described at the bottom of
page 15 of
Lefèvre's slides.
This is actually the same idea as in the previous paragraph:
partition $[1,N]$ into intervals $|n-n_0| leq h sim (n_0 log^2 n_0)^{1/3}$;
in general $r'(n_0)$ might be so close to a rational number that
equidistribution fails, but we can still use continued fractions
to find all $n$ in that interval for which $|r(n)| ll h^{-1}$.

I ran this with $N = 2^{50} > 10^{15}$ on ten alhambra heads.
Most finished in under two days; two took an extra day or two,
probably spending most of them on $n_0$ for which
$r'(n_0)$ was nearly rational (in this case one can do much better than
trying every $n in [n_0-h,n_0+h]$ for which
$| r(n_0) + r'(n_0)(n-n_0) |$ is small,
but I didn't take the extra time to implement that refinement).
The computation found fourteen new records beyond the
12 initial terms 2, 17, 163, 715533, 1432276, 6517719, 11523158,
11985596, 24102781, 254977309, 451207448, 1219588338
of OEIS sequence A178806, namely

2048539023, 10066616717, 42116139191, 47657002570,
73831354169, 122478947521, 143949453227, 3152420311977,
5624690531099, 14964977749017, 25999244327633, 92799025313425,
164330745650026, and 604329910739082.

There is also a new example, namely $n = 3040705645816$, of a number
that is not in this sequence but does belong in the closely
related OEIS sequence A178805,
which consists of $n$ that achieve record low values of $| r(n) |$
instead of $log n cdot | r(n) |$. In general a
$log n cdot | r(n) |$ record is automatically also an
$| r(n) |$ record, but the converse can fail on occasion.
If we imagine that the $| r(n) |$ are independent random numbers
uniformly distributed on $(0,1/2)$ then the probability that
$| r(n) |$ is a new record is $1/n$, so we expect $log N + O(1)$
record values with $n leq N$. The same question for
$log n cdot | r(n) |$ is trickier, but if I did this right
the probability that $| r(n) |$ is a new record but
$log n cdot | r(n) |$ is not one is approximately $1 / n log n$,
so we expect only $loglog N + O(1)$ examples such as
$n = 3040705645816$ up to $N$, and might never see another one
even though there should be infinitely many more.

Here is a table of the values of $n < 2^{50}$
for which $| r(n) |$ attains a new record low, together with
the signed fractional part of $r(n)$, and $log n$ times that fractional part:
$$
begin{array}{rrrc}
2 & -0.1146099 & -0.0794415 & \
5 & 0.1066747 & 0.1716863 & ! \
9 & 0.0960765 & 0.2111017 & ! \
13 & 0.0683262 & 0.1752532 & ! \
17 & 0.0002541 & 0.0007199 & \
163 & -1.26 cdot 10^{-6} & -6.43 cdot 10^{-6} & \
53453 & 1.22 cdot 10^{-6} & 1.33 cdot 10^{-5} & ! \
110673 & 6.68 cdot 10^{-7} & 7.76 cdot 10^{-6} & ! \
715533 & 3.84 cdot 10^{-7} & 5.17 cdot 10^{-6} & \
1432276 & 2.33 cdot 10^{-7} & 3.30 cdot 10^{-6} & \
6517719 & -2.00 cdot 10^{-7} & -3.14 cdot 10^{-6} & \
11523158 & -9.95 cdot 10^{-8} & -1.62 cdot 10^{-6} & \
11985596 & -7.26 cdot 10^{-8} & -1.18 cdot 10^{-6} & \
24102781 & 4.43 cdot 10^{-9} & 7.53 cdot 10^{-8} & \
254977309 & 9.12 cdot 10^{-10} & 1.76 cdot 10^{-8} & \
451207448 & 3.68 cdot 10^{-10} & 7.33 cdot 10^{-9} & \
1219588338 & -2.57 cdot 10^{-10} & -5.38 cdot 10^{-9} & \
2048539023 & -5.89 cdot 10^{-11} & -1.26 cdot 10^{-9} & \
10066616717 & 4.85 cdot 10^{-11} & 1.12 cdot 10^{-9} & \
42116139191 & -4.47 cdot 10^{-11} & -1.09 cdot 10^{-9} & \
47657002570 & -2.43 cdot 10^{-11} & -5.97 cdot 10^{-10} & \
73831354169 & 1.35 cdot 10^{-11} & 3.38 cdot 10^{-10} & \
122478947521 & 7.53 cdot 10^{-13} & 1.92 cdot 10^{-11} & \
143949453227 & -5.50 cdot 10^{-13} & -1.41 cdot 10^{-11} & \
3040705645816 & 5.18 cdot 10^{-13} & 1.49 cdot 10^{-11} & ! \
3152420311977 & -3.36 cdot 10^{-13} & -9.67 cdot 10^{-12} & \
5624690531099 & 1.28 cdot 10^{-13} & 3.76 cdot 10^{-12} & \
14964977749017 & -7.15 cdot 10^{-14} & -2.17 cdot 10^{-12} & \
25999244327633 & -2.02 cdot 10^{-14} & -6.25 cdot 10^{-13} & \
92799025313425 & 6.01 cdot 10^{-15} & 1.93 cdot 10^{-13} & \
164330745650026 & -1.00 cdot 10^{-15} & -3.28 cdot 10^{-14} & \
604329910739082 & -4.59 cdot 10^{-16} & -2.27 cdot 10^{-14} &
end{array}
$$
the "!"'s mark the $| r(n) |$ records that aren't $log n cdot | r(n) |$ records.

Is there any geometry where the triangle inquality fails?

There are a number of good answers from differential geometry, analysis, etc. But I suspect the questioner had axiomatic geometries in mind. So here's another take from that perspective.

There are two statements of the triangle inequality in plane geometry.
(1) If A,B,C are noncollinear points, then $AClt AB+BC$;
(2) If A,B,C are any three points, then $ACleq AB+BC$.

In any system which includes a Ruler Postulate, (1) is stronger than (2).
In neutral geometry (which includes all of the axioms of Euclidean geometry except the parallel postulate), statement (1) can be proven pretty directly from the SAS congruence postulate. (Does anyone know if they're equivalent in the presence of the other neutral geometry axioms?) Statement (2), on the other hand, is the one needed to show that the plane is a metric space, and is strictly weaker, as shown by the "taxicab geometry" mentioned above, which satisfies all of the postulates for neutral geometry except for SAS, and has property (2) but not property (1).

So, to summarize, the triangle inequality is true in neutral geometry, so any model of it (including the Euclidean and hyperbolic planes, etc.) will satisfy the triangle inequality. But of course we can consider weaker axiom systems in which models do not satisfy it (like taxicab).

gr.group theory - Does every retraction of free groups arise from projection to a subset of a freely generating set?

Suppose $F_1$ and $F_2$ are free groups, and suppose $alpha:F_1 to F_2$ is a surjective homomorphism. Then, because $F_2$ is free, the homomorphism splits, and we get a subgroup $H$ of $F_1$ isomorphic to $F_2$ and a retraction of $F_1$ onto $H$, i.e., a surjective map to $H$ that restricts to the identity on $H$ (with kernel a normal complement to $H$).

Question: Can we find a freely generating set $A$ for $F_1$ and a freely generating set $B$ for $H$ such that $B$ is a subset of $A$ and the retraction sends all elements of $B$ to themselves and sends all elements of $A setminus B$ to the identity element?

The corresponding statement for free abelian groups is true: simply pick a (free abelian) generating set for the retraction image and the kernel and take their union to get a freely generating set for the whole group. [Note: Any subgroup of a free abelian group is free abelian.] But this technique of taking a freely generating set for the kernel fails in the non-abelian case, because the kernel is too big.

Why are people interested in defining GW invariant in algebraic geometry category

Part of it is that, for the special case of homogeneous spaces and genus 0, it can be shown that GW invariants count the solutions to certain enumerative problems (how many rational curves of degree $d$ are there that intersect general translates of given cohomology classes) and some rather old problems in algebraic geometry were solved this way, for instance, Kontsevich's formula for (stable) rational plane curves of degree $d$ passing through $3d-1$ points in general position.

More generally, they are invariants that let us distinguish different varieties of the same dimension, by generalizing the cohomology ring.

homological algebra - colimits of spectral sequences

I'm looking for some references about colimits of spectral sequences.

More precisely: let $X : I longrightarrow cal{C}$ be a functor from a filtered category $I$ to the category of double cochain complexes of an abelian category $cal{C}$, in which filtered colimits exist and commute with cohomology.

Let $E_2(X_i)$ be the second page of the first filtration ss associated to $X_i$. Assuming that the $X_i$ are right-half plane double complexes, it weakly converges to $H^*(mbox{Tot}^prod X_i)$ for all $i$ (Weibel, "An introduction to homological algebra", page 142):

$$
E_2(X_i) Longrightarrow H^*(mbox{Tot}^prod X_i) ,
$$

where $mbox{Tot}^prod$ is the total product complex,

$$
(mbox{Tot}^prod X)^n = prod_{p+q=n} X^{pq} .
$$

For the same reason:

$$
E_2(underset{i}{lim_longrightarrow} X_i) Longrightarrow H^*(mbox{Tot}^prod underset{i}{lim_longrightarrow} X_i ) .
$$

Then, because of the exactness of $displaystyle lim_longrightarrow$, we have

$$
underset{i}{lim_longrightarrow} E_2 (X_i) = E_2(underset{i}{lim_longrightarrow} X_i) .
$$

Then my question is: under which conditions can I assure that I have a comparison theorem like

$$
underset{i}{lim_longrightarrow} H^* (mbox{Tot}^prod X_i) = H^*(mbox{Tot}^prod underset{i}{lim_longrightarrow} X_i) quad mbox{?}
$$

Any hints or references will be appreciated.

Category Theory / Topology Question

Let me begin by noting that I know quite little about category theory. So forgive me if the title is too vague, if the question is trivial, and if the question is written poorly.

Let $mathcal{C}$ and $mathcal{D}$ be categories. Say that a functor $T: mathcal{C} to mathcal{D}$ has property X (maybe there is a real name for this property?) if a morphism $f: A to B$ between objects of $mathcal{C}$ is an isomorphism whenever $T(f): T(A) to T(B)$ is an isomorphism. For example, the obvious forgetful functor $CH to Set$ where $CH$ is the category of compact Hausdorff spaces has property X because a continuous bijection from a compact space to a Hausdorff space is automatically a homeomorphism.

Here is my question. Is there a (nontrivial) functor $T: LCH to mathcal{D}$ from the category of locally compact Hausdorff spaces to some category $mathcal{D}$ with property X? Even better, can we assume that $LCH$ is a subcategory of $mathcal{D}$ and that $T$ is a forgetful functor?

I don't care to specify what I mean by "nontrivial", except that the "identity" functor from $LCH$ to itself doesn't count. I want it to be genuinely easier to decide whether or not a morphism is an isomorphism in $mathcal{D}$. If there happen to be lots of ways to do this, perhaps it will help to know that my interest comes from some problems in analysis.

Thanks in advance!

ca.analysis and odes - Are there Generalisations of a Limit (for Just-divergent Sequences)?

There are certain sequences such as

0, 1, 0, 1, 0, 1, 0, 1, ...

that do not converge, but that may be assigned a generalised limit. Such a sequence is said to diverge, although in this case a phrase such as has an orbit might be preferable.

One way to generalise a limit is by considering the sequence of accumulated means: given a sequence

a₁, a₂, a₃, a₄, ...

the accumulated mean sequence would be

a₁, (a₁+a₂)/2, (a₁+a₂+a₃)/3, (a₁+a₂+a₃+a₄)/4, ...

If this sequence has a limit, then the original sequence may be said to have that value as its generalised limit. In this way, the example sequence above has the generalised limit of 1/2; this seems natural as the sequence oscillates around this 'mean' value.

Is there a name for this kind of generalised limit? Are there other ways to define such a thing. Do you know of any good on-line references for this?

Thanks.

nt.number theory - Sum of digits iterated

Original version.
I believe that it is an elementary question, already discussed somewhere. But I just have no idea of how to start it properly. Take a positive integer $n=n_1$ and compute its sum of digits $n_2=S(n)=S_{10}(n)$ in the decimal system. If the newer number $n_2$ is greater than $10$, then compute the sum $n_3=S(n_2)$ of its digits, and continue this iteration $n_k=S(n_{k-1})$ unless you get a number $n^* =n_infty$ in the range $1le n^* le 9$. Is $n^*$ uniformly distributed in the set $lbrace 1,2,dots,9rbrace$? If this is not true in the decimal systems, what can be said in the other systems?

I just learned yesterday about the Feng shui system of determining what kind of problems/advantages one can get according to the house number, say $n$, of his/her home. This depends on the above $n^* $. I do not seriously count on the conclusions but I am curious whether $n^* $ is sufficiently democratic.

Edit. The question was immediately realized as obvious, because $n^*$ is the residue modulo $9$ (with 0 replaced by 9), and this works in any base as well. So the Feng shui function is really trivial, but one can deal with less trivial ones.

Let me fix $m$ and define $Q_m(n)$ as the sum of $m$th powers of decimal digits of a positive integer $n$. What can be said about the sequence of iterations $n_k=Q_m(n_{k-1})$ for a given integer $n_0$? How long can the (minimal) period be for a fixed $m$? And what can be said about the distribution of the purely periodic tails?

I hope that the question is still elementary.

soft question - Grothendieck's mathematical diagram.

First of all, I believe that according to Grothendieck's definition of dessins d’enfants the picture (if I am looking at the right one) indeed seems to show one. At the same time you have a point that this is not one of the more interesting ones.

On the other hand it might be the very first one Grothendieck ever drew and then one could make a wild guess as to what it shows.
I would venture to say that the diagram in question shows the complex conjugation of the Riemann sphere.

If I understand correctly, Grothendieck's inventing and studying dessins d’enfants was motivated by his goal of finding non-trivial elements of the absolute Galois group $mathrm{Gal}(overline{mathbb{Q}}/mathbb Q)$. An obvious (and the only obvious) non-trivial element is complex conjugation of $mathbb C$, which actually extends to $mathbb P^1_{mathbb C}$, a.k.a. the Riemann sphere.

My guess is that this picture shows that and was perhaps the visual clue that led Grothendieck to make the definition of dessins d’enfants.

Addendum: To answer the question raised in the comments: The picture clearly shows a reflection. Complex conjugation is a reflection. I did not claim I have a proof for this, indeed, notice the words wild guess above. The only argument I can offer is that

i) it is reasonable to assume that this picture is or at least has something to do with dessins d’enfants.

ii) it is a very simple drawing for that

iii) there should still be some significance for someone to have put it in the article

iv) it is reasonable to assume that it is an early drawing of dessins d’enfants

v) it is clearly a reflection

vi) complex conjugation is a reflection and has a lot to do with the birth of dessins d’enfants.

As I said, this is a guess, but I wonder if anyone can offer anything other than a guess.

quantum groups - Basis for Universal Calculus

You can describe $Omega_A=ker(m:Aotimes Ato A)$ as the quotient of the free $A$-bimodule generated by symbols $d(a)$, one for each element $ain A$, by the sub-bimodule generated by the elements of the form $$d(ab)-d(a)\,b-a\,d(b), qquad a,bin A,$$ together with the elements of the form $$d(lambda 1), qquad lambdain k$$ with $k$ being the base field.
The elements ${a d(b):a,bin A}$, when seen in $Omega_A$, span $Omega_A$ over $K$ but are not linearly independent over $k$.

To extract from this a $k$-basis of $Omega_A$ you need to know more than a basis of $A$. For example, if you know a presentation of $A$ given by generators and relations, you can obtain a basis using essentially Groebner bases.

ra.rings and algebras - Why is there no Cayley's Theorem for rings?

Cayley's theorem makes groups nice: a closed set of bijections is a group and a group is a closed set of bijections- beautiful, natural and understandable canonically as symmetry. It is not so much a technical theorem as a glorious wellspring of intuition- something, at least from my perspective, that rings are missing; and I want to know why.

Certainly the axiom system is more complicated- so there is no way you're going to get as simple a characterisation as you do with groups- but surely there must be some sort of universal object for rings of a given cardinality, analogous to the symmetric group in group theory. I would be surprised if it was a ring- the multiplicative and additive properties of a ring could be changed (somewhat) independently of one another- but perhaps a fibration of automorphisms over a group? If so is there a natural(ish) way of interpreting it?

Perhaps it's possible for a certain subclass of rings, perhaps it's possible but useless, perhaps it's impossible for specific reasons, in which case: the more specific the better.

Edit: So Jack's answer seems to have covered it (and quickly!): endomorphisms of abelian groups is nice! But can we do better? Is there a chance that 'abelian' can be unwound to the extent we can make this about sets again- or is that too much to hope for?

ra.rings and algebras - Intuitive Example of a Jacobson Radical

Lucky timing, I just worked out a couple of examples for the class I'm teaching this semester. Let A be a commutative local ring, m the maximal ideal, and k=A/m the residue field. Let's consider two rings: M = M₂(A) (2-by-2 matrices with entries in A), and I = the Iwahori order consisting of 2-by-2 matrices with entries in A whose lower-left entry is in m, i.e. matrices of the form

[ A A ]

[ m A ]

We'll compute rad(M) and rad(I) using the fact that rad = intersection of annihilators of simple left modules = { x : 1 - xy is a unit for all y }.

First let's compute rad(M). M acts naturally on k^2 by left multiplication (via M₂(A) ->> M₂(k)), and this is a simple M-module. The annihilator of k^2 is M₂(m) = 2-by-2 matrices with entries in m, so rad(M) is contained in M₂(m). On the other hand every element x in M₂(m) has the property that 1-xy is a unit in M₂(A) for all y in M₂(A) (since xy is in M₂(m), the determinant of 1-xy is a unit); therefore rad(M) contains M₂(m), and we've shown rad(M) = M₂(m).

Next let's compute rad(I). Now k is a simple left I-module in two ways: first by multiplication by the upper-left entry (mod m), and second by multiplication by the lower-right entry (mod m). (Check that if x,y are in I then the upper-left entry of xy is congruent mod m to the product of the upper-left entries of x and y, and similar for the lower right.) The annihilator of the first I-module is therefore matrices of the form

[ m A ]

[ m A ]

and the second is matrices of the form

[ A A ]

[ m m ]

and the intersection of these annihilators is the ring of matrices of the form

[ m A ]

[ m m ]

which therefore contains the Jacobson radical. On the other hand every matrix x of that form has the property that det(1-xy) is a unit in A for y in I, and therefore the above collection of matrices is equal to the Jacobson radical.

ct.category theory - What's a groupoid? What's a good example of a groupoid?

Let me expand a bit on what Dave said.

The Yoneda lemma tells us that given an object X of a category C, the (covariant, contravariant, whatever) functor h_X : C -> Set, which sends an object Y to the set Hom(Y,X), can be thought of as the "same" as the object X. There are many situations in which we are interested in a functor F : C -> Set, and we might like to know whether F is isomorphic to h_M for some object M, because that reduces the study of F to the study of a single object M. In such a case we say that F is represented by M. The letter M here, suggestively, stands for "moduli".

Example: Given a group G, the functor BG' : Top -> Set is the functor which sends a topological space X to the set of isomorphism classes of principal G-bundles over X. (You can also do the analogous thing for schemes.)

Example: The functor M_g' : Sch -> Set is the functor which sends a scheme X to the set of isomorphism classes of flat families of genus g curves over X.

In both of the above examples, there is no object M for which h_M is isomorphic to the functor. So this is perhaps not so nice. But, without getting into too many details, there is a natural "fix", namely we can instead consider the functor BG : Top -> Groupoid (resp. M_g : Sch -> Groupoid) which sends a topological space (resp. a scheme) to the groupoid of G-bundles (resp. flat families of genus g curves). This groupoid has objects G-bundles and morphisms isomorphisms of G-bundles (resp. the obvious analogous thing). The original set-valued functor is just the composition of this functor with the functor Groupoid to Set which takes a groupoid and returns the set of isomorphism classes of objects in the groupoid.

Anyway, despite the fact that the set-valued functors are not so "geometric", since they are not represented by a "geometric" object (topological space and scheme, respectively), the groupoid-valued functors are more "geometric". In the case of M_g, the "geometric" structure we get is that of a "Deligne-Mumford stack", which essentially means that we can for practical purposes pretend that it is represented by a scheme with only some slightly "weird" properties. In the case of BG (the topological one) you can take a "geometric realization" and recover the classifying space BG that we know and love.

Another very important reason for studying groupoids and another very important class of groupoids comes from, as others have already mentioned, group actions. When a group acts on a manifold or a variety, the naive quotient may be badly behaved, for example it may no longer be a manifold (e.g. it might not be smooth, or it might not be Hausdorff) or respectively a variety (or it may not even be clear how to take the quotient at all!), which makes it harder to study geometric properties of the alleged "quotient". However, the groupoid viewpoint allows us to get a better handle on the quotient and its geometry. More precisely, if G is a group acting on a space (manifold, scheme, variety, whatever) X, then the "correct" quotient is actually the functor X/G : C -> Groupoid (where C is the category of manifolds, schemes, whatever) which sends an object Y to the groupoid of pairs (G-bundles E over Y, G-equivariant morphism from the total space of E to X). The functor BG is a special case of this; it's pt/G.

There's some further discussion on this sort of stuff at the nLab:

http://ncatlab.org/nlab/show/moduli+space

http://ncatlab.org/nlab/show/classifying+space

big list - Fields of mathematics that were dormant for a long time until someone revitalized them

The lambda calculus was first published in 1933 by Alonzo Church, intended to be an alternative to first-order logic. Two of his students, Kleene and Rosser, proved it inconsistent in 1935. In 1936, another student, Alan Turing, proved that a stripped-down version was equivalent in computational power to the Turing machine. It was pretty much "just another example of a Turing-equivalent language" for about 30 years.

In the late 1960s and 1970s, John McCarthy, Dana Scott, and Peter Landin (among others) revived the lambda calculus: John McCarthy by loosely basing LISP on it, Dana Scott by giving it a set-theoretic interpretation, and Peter Landin by developing a theoretical machine that - unlike Turing's - was similar to actual computers and a transformation into its machine instructions. These things together showed that the lambda calculus was not only good at encoding mathematical procedures as programs, but could be compiled into reasonable programs that run on actual machines. Guy Steele showed shortly after in his series of "Lambda the Ultimate" papers that the programs could be run efficiently, and that the lambda calculus easily models many familiar programming language constructs.

Today, the lambda calculus is THE theory of programming languages. Among the ways to describe algorithms, its mathematical purity is unrivaled.

Compared to other mathematical areas, 30 years isn't a long time for something to lay dormant. But consider that Computer Science has only been around for about 70!

Relative K-theory and split exact sequences of C* algebras

Although this question was posted and answered a very long time ago, I just stumbled upon it and I thought it might be worthwhile if an answer is provided near the post (it actually seems like a full answer is not yet available).

First I will assume $A$ is untital. Second I will use the fact that given $[(p',q',x')]in K_0(A,A/J)$ I can write it as $[(ell_k,q,ell_k)]$ where
$pi(q)=pi(ell_k)=ell_k$ where $ell_k$ is the standard (bigger than $ktimes k$) matrix over the complex numbers with ones on the first $k$ entries of the diagonal and zeros elsewhere. A sketch of the proof is:

-note that
$$[(p',q',x')]=[(p'oplus 1-p',q'oplus 1-p', x'oplus 1-p')]$$
-note that
$$[(p'oplus 1-p',q'oplus 1-p', x'oplus 1-p')]=[(ell_k,q'',x'')]$$
- Use the fact that given a partial isometry $y$ we can find a path of unitaries in matrices of quadruple the size from the identity to $V$ such that
$V^*yy^*V=y^*y$ and $yy^*Vy^*y=y$ (where we include partial isometries and projections in the upper left hand corner in bigger matrices).

-So let $u_t$ this path of unitaries for the partial isometry $pi(x)$ and let $v_t$ a lift starting at the identity.

-Note that
$$[(ell_k,q'',x'')]=[(ell_k, q, x)],$$
where $ell_k=pi(ell_k)=pi(q)=pi(x)$ (use $(ell_k,v_t^*q''v_t,v_t^*x'')$).

-Note that
$$[(ell_k, q, x)]=[(ell_k,q,ell_k)]$$ by a linear path $tell_k+(1-t)x$ since
$pi(x)=pi(ell_k)$.

Denote by $sigma:A/Jrightarrow A$ the section which exists by assumption. Now suppose $r=[(ell_k, q, ell_k)]$ is a general element in $K_0(A,A/J)$ such that $[ell_k]-[q]=0$ in $K_0(A)$. Then there must exist a path of unitaries $u_t$ starting at the identity such that $u_1^*qu_1=ell_k$. So we have
$r=[(ell_k,ell_k, u_1^*ell_k)]$. Now denote $U:=sigma(pi(u_1))$ then
$pi(U)=pi(u_1)$ and thus by a linear path $r=[(ell_k,ell_k, U^*ell_k)]$. Now note that $U^*ell_k U=sigmapi(u_1^*ell_ku_1)=ell_k$ which shows that $(ell_k,ell_k,U^*ell_k)$ is degenerate thus $r=0$. So we find that the kernel of $K_0(A,A/J)$ is trivial. Which was to be shown.

gt.geometric topology - Legendrian homotopy of curves in a contact structure?

In general, the (parametric) h-principle for Legendrian immersions implies that Legendrian immersions f:L->(M,xi) are classified up to homotopy (through Legendrian immersions) by the following bundle-theoretic invariant: Choosing a compatible almost complex structure on xi allows one to complexify the differential of f to an isomorphism
d_C f: TLotimes C -> f*xi, and the relevant invariant is the homotopy class of this isomorphism of complex vector bundles (of course this is independent of the almost complex structure since the space of compatible almost complex structures is contractible).

The above holds in any contact manifold (M,xi) of arbitrary dimension. Of course when M is 3-dimensional and L is S^1, f^*xi is the unique complex line bundle over S^1, automorphisms of which are parametrized up to homotopy by pi_1(U(1))=Z. So (given that the h-principle also implies that any loop in a 3-manifold is homotopic to a Legendrian loop) it appears to always be the case that the "Legendrian fundamental group" surjects onto the standard fundamental group, with kernel Z.

When M=R^3 this invariant is equivalent to the rotation number that Steven mentioned. There's a proof of the relevant h-principle in the book by Eliashberg and Mishachev. The above discussion is partly based on Section 3.3 of arXiv:0210124 by Ekholm-Etnyre-Sullivan.

co.combinatorics - Variations on a theme of O'Bryant, Cooper and Eichhorn concerning power series over $mathbb Z/2mathbb Z$

(Part 1)--My argument uses the following curious fact about ideals in $Z[i]$ and $Z[sqrt{-2}].$
Suppose $n=8m+1$. Let $I=I(n)$ and $J=J(n)$ be the number of ideals of norm $n$ in $Z[i]$ and $Z[sqrt{-2}]$. Then $Iequiv J$ (4) except when $m$ is odd triangular, in which case $Iequiv J+2$ (4).

As a corollary we find that in $Z/2[[x]]$, $fg^2-fg$ is $x+x^3+x^{15}+x^{21}+cdots$, the exponents being the odd triangular numbers. (I wonder if this is previously observed, and if it's
related to congruence relations for modular forms). To prove the corollary it suffices to
show: Let $I_1=I_1(m)$ be the number of solutions of $m=t+2s$ and $J_1=J_1(m)$ be the number of solutions of $m=t+s$ with $t$ triangular, $s$ a square. Then when $m$ is odd triangular, $I_1-J_1$ is
odd; otherwise it is even.

We compare $I_1(m)$ with $I(n)$. Suppose $m=t+2s$. Then $n=(8t+1)+16s$ and $8t+1=x^2$, $16s=y^2$ with
$x$ odd and $x$, $y$ in $N$. $x+iy$ and $x-iy$ generate ideals of norm $n$ in $Z[i]$. These 2 ideals are
distinct except when $m$ is triangular and $s=y=0$. Using the fact that $Z[i]$ is a PID we find
that every ideal of norm $n$ comes from a decomposition $m=t+2s$, and that $I=2I_1$, except when
$m$ is triangular in which case $I=2I_1-1$.

Suppose $m=t+s$. Then $n=(8t+1)+8s$, and $8t+1=x^2$, $4s=y^2$ with $x$ odd and $x$, $y$ in $N$. $x+ysqrt{-2}$ and $x-ysqrt{-2}$ generate ideals of norm $n$ in $Z[sqrt{-2}]$. As above, we find
that $J=2J_1$, except when $m$ is triangular in which case $J$ is $2J_1-1$. Combining the
result of this paragraph and the last with the curious fact we get the corollary.

One now derives the answer to my question. Let $R=Z/2[[x^2]]$. As R-module, $A$ is the direct sum of $R$ and $xR.$ Let $pr$ be the $R$-linear map $Ato R$ which is id on $R$ and 0 on $xR$.
Since $fg^2-fg=x+x^3+x^{15}+cdots$, $pr(fg^2)=pr(fg)$. Since $pr$ is R linear and $1/g^2$ is in $R$.
$pr(f)=pr(f/g)$. So for even $m$, the coefficient of $x^m$ in $f/g$ is the coefficient of $x^m$ in $f$,
answering my question. (In his answer Wadim saw the projection argument but missed the
implications)---To be continued

dg.differential geometry - Oriention-Reversing Diffeomorphisms of a Manifold

The same technique Allen mentioned also shows that $mathbb{H}P^{2n}$ doesn't admit any orientation reversing diffeomorphisms.

However, it's also true that $mathbb{H}P^{2n+1}$ doesn't admit any orientation reversing diffeomorphisms unless n = 0. This is because the first Pontryagin class $p_1 = 2(n-1)x$ for $xin H^4(mathbb{H}P^n)$ a generator. Any diffeomorphism must take $p_1$ to itself, so it must take $x$ to itself (unless $n=1$). The ring structure of $mathbb{H}P^n$ then implies that the diffeomorphism preserves orientation.

(By contrast, the map $[z_0:...:z_n]rightarrow [overline{z_0}:...:overline{z_{n+1}}]$ is an orientation reversing map for $mathbb{C}P^{2n+1}$).

Another class of (perhaps surprising) examples is exotic spheres: many of them don't admit orientation reversing diffeomorphisms, though, or course, they admit orientation reversing homeomorphisms.

This is because the collection of oriented diffeomorphism classes of an $n$-sphere ($nneq 4$) form an abelian group under connect sum. The inverse of an oriented diffeomorphism class of sphere is the same diffeomorphism class equipped with the opposite orientation. Thus, exotic spheres with orientation reversing diffeomorphisms correspond to elements of order 1 or 2 in this group.

Then, for example, in dimension 7, the group is isomorphic to $mathbb{Z}/28mathbb{Z}$, so there are precisely two spheres which admit orientation reversing diffeomorphisms.

graph theory - Reconstruction conjecture: Can other decks do the job?

The standard reconstruction conjecture states that a graph is determined by its deck of vertex-deleted subgraphs.

Question: Have other decks been investigated, finding out
that only vertex-deleted subgraphs can do the job? If so: Which property of vertex-deleted subgraphs makes them exceptional?

I have three candidates in mind, others are conceivable. (For the sake of simplicity I consider only simple connected graphs $G$.)

1. the deck of sub-maximal neighbourhoods: Let the sub-maximal neighbourhood of $v$ be the $v$-rooted graph constructed from $G$ by deleting all vertices with maximal distance from $v$.




2. the deck of distinguishing neighbourhoods: Let the distinguishing neighbourhood of $v$ be the smallest $n$-neighbourhood of $v$ which distinguishes it from all vertices not conjugate to it ($n$-neighbourhood = the $v$-rooted induced subgraph containing all vertices $w$ with distance $d(v,w) leq n$).




3. the deck of crossref-deleted subgraphs: Let the crossref-deleted subgraph with respect to $v$ be the $v$-rooted graph constructed from $G$ by deleting all edges between vertices that have the same distance from $v$.

Note that the vertex-deleted subgraph with respect to $v$ is nothing but the $v$-rooted graph constructed from $G$ by deleting all edges between $v$ and its neighbours.

I am not good in systematically constructing counterexamples, and I do not have very much intuition about general graphs. So, any counterexample to one of the candidates above would be very welcome.

What I do know is that a) trees are trivially reconstructible from their deck of crossref-deleted subgraphs, that b) graphs with one node of which the distinguishing neighbourhood is the whole graph are trivially reconstructible from their deck of distinguishing neighbourhoods, and that c) reconstructing (very) small graphs from one of the decks above is fun.

ct.category theory - Proof that objects are colimits of generators

I think there are actually three possible things that you might be asking, but the answer to all of them is no. Suppose that G is a strong generator in a cocomplete category C. Then you can ask:

1. Is every object X of C the colimit of G over the canonical diagram of shape $(Gdownarrow X)$? (If so, then G is called dense in C.)




2. Is every object some colimit of a diagram all of whose vertices are G? (If so, then G is called colimit-dense in C.)




3. Is C the smallest subcategory of itself containing G and closed under colimits? (If so, then G is a colimit-generator of C.)

The category of compact Hausdorff spaces is a counterexample to the first two. It is monadic over Set (the monad is the ultrafilter monad, aka Stone-Cech compactification of the discrete topology), and hence cocomplete, and the one-point space is a strong generator. But any colimit of a diagram consisting entirely of 1-point spaces must be in the image of the free functor from Set (the one-point space being its own Stone-Cech compactification), and hence (since that functor is a left adjoint and preserves colimits) must be the free object on some set. However, not every compact Hausdorff space is the Stone-Cech compactification of a discrete set.

As Todd pointed out in the comments, though, CptHaus is the colimit-closure of the one-point space, since every object is a coequalizer of maps between free ones (because the category is monadic over Set); thus it isn't a counterexample to the third question. Counterexamples to the third question are actually much harder to come by, and in fact if you assume additionally that C has finite limits and is "extremally well-copowered", then it is true that any strong generator is a colimit-generator. I think there's a proof of this somewhere in Kelly's book "Basic concepts of enriched category theory," and a brief version can be found here. However, without these assumptions, one can cook up ugly and contrived counterexamples, such as example 4.3 in the paper "Total categories and solid functors" by Borger and Tholen.

ac.commutative algebra - Why are finitely generated modules over principal artin local rings direct sums of cyclic modules?

I am looking for a proof of the following fact:

If $R$ is a principal artin local ring and $M$ a finitely generated $R$-module, then $R$ is a direct sum of cyclic $R$-modules.

(Apparently such rings $R$ are called, e.g. in Zariski-Samuel, special principal ideal rings.)

I almost didn't ask this question for fear that I might just be missing something obvious, but I've been unable to come up with a proof myself and I can't find one anywhere (if I am just being stupid I certainly don't mind being told). Zariski-Samuel proves a structure theorem for principal ideal rings (they are products of PID's and special PIR's), as well as the fact that a submodule of a principal ideal ring generated by n elements is generated by $leq n$ elements. I thought perhaps the statement above could be deduced from this last fact, in a similar manner to the way one proves the corresponding result for finite modules over PID's, but the obstruction to this (as I see it) is that submodules of free $R$-modules will not in general be free (for instance, the maximal ideal of $R$ is not free, assuming $R$ is not a field, i.e., has length $geq 2$). Essentially the naive induction on the number of generators doesn't seem to work because I can't be sure that the relevant exact sequence splits...again, maybe I'm just being foolish. I think a proof might be found in chapter VIII of Bourbaki's Algebra text, but this chapter isn't in my copy (I think maybe it's only available in French).

Incidentally, it's straightforward to show that, if such a decomposition exists, the number of times a factor of the form $R/(pi^i)$, where $(pi)$ is the maximal ideal of $R$ and $1leq ileq k$ ($k$ being the length of $R$, i.e., the index of nilpotency of $(pi)$) is uniquely determined as the length of a quotient of $M$, for instance.

The reason I'm interested in this is because I want to know that the isomorphism type of $M$ is completely determined by the function sending $i$, $1leq ileq k$, to the length of $M[pi^i]$ (the kernel of multiplication by $pi^i$), which, assuming such a decomposition exists, is definitely the case.

Edit: I realized that my module M can (being artinian) be written as a finite direct sum of indecomposable submodules, so I guess this reduces my question to: must an indecomposable submodule of $M$ be a cyclic?

pr.probability - Dynamic programming principle (DPP)

In stochastic control problem, one shall use the measurable selection theorem to prove DPP. It was discussed in discrete time case in [Bertsekas and Shreve 1978]. Is there unified framework in continuous time problem, to derive sufficient condition under which DPP is valid? Is there an easy way to explain why measurable selection theorem is important in DPP?

For ex., here is one control problem:
Let $(Omega, mathcal{F}, mathbb{P}, mathbb{F})$ be a filtered probability space. Let $mathcal{A}$ be admissible control space, and $X^{t,x,alpha}(s)$ be a controlled Markov process with initial $(t,x)$ and control $alpha in mathcal{A}$. The value function is
$V(t,x) = inf mathbb{E}[ g(X^{t,x, alpha}(tau)) ]$, where $inf$ is over $alpha in mathcal{A}$, and $tau$ is a given stopping time. The question is, what is the sufficient condition for $V(cdot)$ to have $V(t,x) = inf mathbb{E}[V(theta, X^{t,x,alpha}(theta))]$ for all stopping time $theta in [t,tau]$?

co.combinatorics - Is every matching of the hypercube graph extensible to a Hamiltonian cycle

Given that $Q_d$ is the hypercube graph of dimension $d$ then it is a known fact (not so trivial to prove though) that given a perfect matching $M$ of $Q_d$ ($dgeq 2$) it is possible to find another perfect matching $N$ of $Q_d$ such that $M cup N$ is a Hamiltonian cycle in $Q_d$.

The question now is - given a (non necessarily perfect) matching $M$ of $Q_d$ ($dgeq 2$) is it possible to find a set of edges $N$ such that $M cup N$ is a Hamiltonian cycle in $Q_d$.

The statement is proven to be true for $d in{2,3,4}$.

analytic number theory - Uniform variant of Stirling's approximation

Stirling's formula is usually stated in the form $log Gamma(s) = (s-frac12) log{s} - s + logsqrt{2pi} + E(s)$, where
$E(s) = c_1/s + c_2/s^2 + dots + O(s^{-K})$ for certain absolute constants $c_i$. I am interested in having a uniform approximation for $E(s)$ that is valid for all $s = sigma + it$ with $sigma>0$ fixed and $|t| leq X$ for $X geq 1$. Does there exist a known "nice" approximation for $E(s)$ of the form $E(s) = F(s) + O(X^{-K})$, where
$F(s)$, which depends on $K$ and $X$ of course, has an explicit shape? Bonus points for explicit bounds
on $F(s)$ and its derivatives uniformly valid in $|t| leq X$.

EDIT ADDED July 28 2010: I am doubtful if there is a positive answer to my question. As a simple example, consider the rate of convergence of the Taylor series of the cosine function. Of course, $cos(x) = 1- frac{x^2}{2!} + frac{x^4}{4!} - dots pm frac{x^{2k}}{(2k)!} + R_{2k}(x)$ where $R_{2k}(x) = cos^{(2k+1)}(xi) frac{x^{2k+1}}{(2k+1)!}$ for some $|xi| leq |x|$. In order to get an error term that is $O(X^{-K})$ uniformly for $|x| leq X$ we need to take $k$ roughly on the order of $X$ (since that is when the factorial in the denominator wins over the size of $X^{2k+1}$); at this point the error term gets very small very fast . This is a lot of terms!

ac.commutative algebra - Jordan Form Over a Polynomial Ring

Let $X$ be the set of $ktimes k$ matrix with entries in $mathbb{C}$, and let $Min X$. The group $GL(k,mathbb{C})$ acts on $X$ by conjugation, and according to the Jordan decomposition theorem (see e.g wikipedia) somewhere in the orbit containing $M$ is a block diagonal matrix with non-zero entries only on the diagonal and superdiagonal.

Suppose now we consider $ktimes k$ matrices whose entries lie in the polynomial ring $mathbb{C}[z_{1},z_{2}, ldots ,z_{n}]$ and we study the action by conjugation of $GL(k,mathbb{C}[z_{1},z_{2}, ldots ,z_{n}])$. Then the Jordan decomposition theorem, as formulated above, clearly no longer holds. For example consider the matrix:

$ M=left(
{begin{array}{cc}
0 & 1 \
z^{p}_{1} & 0
end{array}}
right)$,

where in the above $p$ denotes a positive integer. If $p $ is odd, then $M$ cannot be diagonalized since the ring $mathbb{C}[z_{1},z_{2}, ldots ,z_{n}]$ does not contain the eigenvalues of $M$. On the other hand, if $p$ is even we still cannot diagonalize $M$ since when $z_{1}=0 $, $M$ is not diagonalizable.

My question is then what, if anything, remains of the Jordan decomposition in this case? Or equivalently given a $ktimes k$ matrix $M$ with entries in $mathbb{C}[z_{1},z_{2}, ldots ,z_{n}]$ are there any particularly simple matrices related to $M$ via conjugation by an element of $GL(k,mathbb{C}[z_{1},z_{2}, ldots ,z_{n}])$?

Compact simple simply connected algebraic groups over $Q_p$ or other local non-archimedean fields

Here are some remarks on the answers of Charles Matthews, Kevin Buzzard, and Victor Protsak. For justification of Kevin Buzzard's claim, see G. Prasad, "An elementary proof of a theorem of Bruhat-Tits-Rousseau and of a theorem of Tits" from Bull. Soc. Math. France 110 (1982), pp. 197--202, for an incredibly elegant and short proof that over any henselian valued field $F$, a connected reductive $F$-group $G$ is $F$-anisotropic if and only if $G(F)$ is "bounded" (a property defined in terms of a choice of closed immersion of $G$ into an affine space over $F$, the choice of which doesn't matter; this is meaningful for any affine $F$-scheme of finite type and equivalent to compactness when $F$ is locally compact). Platanov-Rapinchuk has a universal assumption that all fields of characteristic 0 (except when they're finite), so unfortunately that reference is insufficient for uniform arguments over all non-archimedean local fields. I suppose (near?-)circularity (suggested by Victor Protsak) is a more serious issue. :)

There remains the matter of determining, for locally compact non-archimedean $F$ and connected reductive $F$-groups, precisely when the $F$-anisotropic case can actually occur. As Victor Protsak mentioned, via Bruhat-Tits theory one sees that for connected semisimple $F$-groups which are absolutely simple and simply connected over a non-archimedean local field $F$ (i.e., $G$ a simply connected $F$-form of a Chevalley group), such forms never exist away from type A, and in type A the $F$-anisotropic examples are precisely the $F$-groups of norm-1 units of central simple algebras over $F$. (Note the contrast with the case $F = mathbb{R}$, for which there's always a "compact form" of any Chevalley type.)

Let me now briefly explain why this handles the general connected reductive case, by a standard kind of argument with central isogenies and separable Weil restriction. (This is explained also in the article [2] of Tits referenced in Charles Matthews' answer.) If $f:G' rightarrow G$ is a (possibly inseparable) central $F$-isogeny between connected reductive $F$-groups then the preimage of an $F$-torus of $G$ is an $F$-torus of $G'$ (since maximal tori in $G'$ are their own functorial centralizers, so $ker f$ is of multiplicative type, nothing funny happens when $f$ is not separable). Since $F$-anisotropcity of an $F$-torus is invariant under $F$-isogenies (as we see using the $F$-rational character group, or more direct arguments), it follows that $G$ is $F$-anisotropic if and only if $G'$ is. (This argument has the advantage of working over any field $F$, in contrast with a direct attack on the topology of rational points by using finiteness theorems for Galois cohomology of connected reductive groups.) Thus, by considering an arbitrary connected reductive $F$-group $G$ and letting $G'$ denote the product of its maximal central $F$-torus and the simply connected central cover of the derived group $D(G)$, we see that the problem comes down to the simply connected case.

But in the simply connected semisimple case, the general structure of connected semisimple groups over fields (in terms of central isogenous quotient of direct product of commuting simple "factors") implies that $G$ is uniquely a direct product of commuting $F$-simple connected semisimple $F$-groups, each of which is simply connected, so we may assume $G$ is $F$-simple. Then by an elementary result of Borel and Tits (6.21 in "Groupes reductif", IHES), $G = {rm{Res}}_ {F'/F}(G')$ for a finite separable extension $F'/F$ and a connected semisimple $F'$-group $G'$ that is absolutely simple and simply connected. By the good behavior of Weil restriction with respect to the formation of the topological group of rational points, it follows that the equality ${rm{Res}}_ {F'/F}(G')(F) = G'(F')$ of abstract groups is a homeomorphism, so we can replace $(G,F)$ with $(G',F')$ to reduce to the case when $G$ is also absolutely simple, the case addressed by Victor Protsak above.
(A more algebraic argument with Galois descent relating maximal $F'$-tori in $G'$ and maximal $F$-tori in its Weil restriction to $F$ shows the equivalence of anisotropicity for $G'$ and its Weil restriction through the finite separable $F'/F$, where $F$ can be taken to be any field at all.)

Conclusion: for non-archimedean local $F$, the $F$-anisotropic connected reductive $F$-groups are precisely the central quotients of products of an $F$-anisotropic torus and groups of norm-1 units of central division algebras over finite separable extensions of $F$.

dg.differential geometry - De Rham decomposition theorem, generalisations and good references

I suppose we have to ask the Riemannian manifold to be complete. Otherwise $mathbb R^3 - lbrace 0 rbrace$ would be a counterexample.

I do not have an answer to question 2, but you might be interested in variations of De Rham decomposition Theorem to the realm of compact complex manifolds. There, it is natural to ask, as Beauville did, if a holomorphic decomposition of the holomorphic tangent bundle implies that the universal covering is isomorphic to a product(no metric assumption).

Without further assumptions there is no hope since Hopf surfaces provide examples with decomposable tangent bundle but with universal covering isomorphic to $mathbb C^2 - lbrace 0 rbrace$.

If one assume that the manifold is projective or Kahler then there are some positive results, the first of which can be found in Beaviulle's paper linked to above. In the projective case you can also look at this, this, and this paper. In the Kahler case you can look at here.

The general problem seems to be wide open, in the above results either one
assumes that one of the factors is one-dimensional or imposes strong conditions on the ambient variety itself (dimension $le 3$ or uniruledness).

at.algebraic topology - Tor over graded rings

Let $R$ be a graded ring (concentrated in nonnegative dimensions and maybe bounded from above). For every positive natural number $n$, denote by $Rtotau_{leq n}R$ the $n$-truncation and by $tau_{geq n}R to R$ the analogous procedure killing all dimensions below n. These two rings may both be viewed as $R$-modules.

My question is the following: Is there a simple procedure computing $Tor_*^R(tau_{leq n}R, tau_{geq n+1}R)$ (in the category of graded modules)?

reference request - Cohomology of sheaves for sites and Galois cohomology

Hello,

I am looking for a reference (if it exists) that makes the link between cohomology of sheaves for sites and Galois cohomology :

quickly said, I would like to see Galois cohomology (at least in the commutative case) as the cohomology of a sheaf over the étale site of extensions of k.

By the way, what is a reference for cohomology of sites ?

Thanks

rt.representation theory - Classification of finite complex reflection groups

Background:

Let $K$ be a field and let $V$ be a finite-dimensional $K$-vector space. A pseudoreflection (or usually imprecisely just reflection) in $V$ is an element $1 neq s in mathrm{GL}(V)$ fixing a hyperplane. A reflection representation of a group $W$ over $K$ is a $K$-linear representation $rho:W rightarrow mathrm{GL}(V)$, such that $rho(W)$ is generated by reflections. A group $W$ is called a reflection group over $K$ if it admits a reflection representation over $K$.

Shephard-Todd classified (see below) the finite irreducible reflection groups over $mathbb{C}$ (i.e. those finite groups admitting an irreducible reflection representation over $mathbb{C}$).

Question:

Is there also a classification of the finite irreducible reflection representations over $mathbb{C}$?

Edit: This question is very imprecise as indicated in the comments below. I should say what "classification of representations" means, and I have to admit: I don't know. A few ideas in this direction are:

• determine the isomorphism classes of finite irreducible reflection representations over $mathbb{C}$, where an isomorphism between two reflection representations $rho:W rightarrow mathrm{GL}(V)$, $rho':W' rightarrow mathrm{GL}(V')$ is a vector space isomorphism $f:V rightarrow V'$ such that $f rho(G) f^{-1} = rho'(G)$. (I think the Shephard-Todd classification is a classification relative to this notion!?)




• the same as above but an isomorphism is a vector space isomorphism $f:V rightarrow V'$ and a group isomorphism $varphi:W rightarrow W'$ such that $f rho(g) f^{-1} = rho'( varphi(g) )$ for all $g in W$.




• consider pairs $(W,T)$ consisting of a finite irreducible reflection group over $mathbb{C}$ and a subset $T$ which are generating reflections of some irreducible reflection representation of $W$ and then determine isomorphism classes of such pairs.




• [Insert your idea here].

My motivation for this question is something like this: A Cherednik-Algebra is defined for any finite irreducible reflection representation over $mathbb{C}$. In what sense does the algebra depend on the group alone and not on the choice of a particular reflection representation?

homological algebra - Spectra of rings that are projective module over a subring

This question is motivated from my last question here. I wonder if one has a ring A and an over-ring of this ring say B, and if we know that B is a projective A-module can we have a particular idea of how Spec B would look like if we know how Spec A would look like?

This question does make sense to me. Because for instance given a local ring A, then B's are some form of copies of A. If A were zero dimensional reduced and commutative then Spec B would look like copies of clopen subsets of Spec A (because projective modules over von Neumann regular rings are isomorphic to direct sum of principal ideals). So what else do we know?

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.

ct.category theory - Does the Tannaka-Krein theorem come from an equivalence of 2-categories?

Possibly the correct answer to this question is simply a pointer towards some recent literature on Tannaka-Krein-type theorems. The best article I know on the subject is the excellent

• André Joyal and Ross Street, An introduction to Tannaka duality and quantum groups, Category Theory, Lecture Notes in Math, 1991 vol. 1488 pp. 412–492

from which I'm getting most of my facts.

Let me fix, once and for all, a field $mathbb K$. I will denote by $text{Vect}$ the usual category of all $mathbb K$-vector spaces, and by $text{FinVect}$ its full subcategory of dualizable objects. The notions of (coassociative, counital) coalgebra and (right, say, and coassociative and counital) comodule are standard; briefly, if $(mathcal V,otimes)$ is a monoidal category, a coalgebra in $mathcal V$ is an object $A$ along with a map $A to A otimes A$ satisfying some axioms, and an $A$-comodule is an object $X$ and a map $X to Xotimes A$ satisfying some axioms. Here's the fast way to say the axioms. Without telling you anything, it's clear what should be a homomorphism of comodules, namely a map $f: Xto Y$ so that the maps $X overset f to Y to Yotimes A$ and $X to Xotimes A overset{fotimes {rm id}}to Yotimes A$ agree. Then a coalgebra $A$ is coassociative iff the comultiplication $Ato Aotimes A$ is a homomorphism of $A$-comodules, and a comodule $X$ is coassociative iff $Xto Xotimes A$ is a homomorphism of comodules. (In both cases, the comodule structure on the right is just the comultiplication in the second factor.) I will abuse language so that all coalgebras and comodules are coassociative. Oh, and I haven't said anything about counits, but I want them as well. Given a coalgebra $A$, I will denote its category of right comodules by $text{Comod}_A$, and of finite-dimensional right comodules by $text{FinComod}_A$.

Let's say that a Tannakian category is a $mathbb K$-linear (i.e. $text{Vect}$-enriched) abelian category $mathcal C$ along with a faithful exact $mathbb K$-linear functor $F: mathcal C to text{FinVect}$. (If this is not the most standard definition, let me know.) The fundamental theorem is the following:

Theorem (c.f. Op. cit.): Let $F: mathcal C to text{FinVect}$ be any functor from any category. Then there is a coalgebra $operatorname{End}^vee(F) in text{Vect}$ given by a certain natural colimit (take the definition of the vector space of natural transformations and turn all arrows around; use the fact that the endomorphism of a finite-dimensional vector space is naturally a coalgebra). The functor $F$ factors through $text{FinComod}_{operatorname{End}^vee(F)}$ (and its forgetful functor to $text{FinVect}$), and $operatorname{End}^vee(F)$ is universal with respect to this property (if $F$ factors through $text{forget}: text{FinComod}_A to text{FinVect}$, then there is a map $operatorname{End}^vee(F) to A$ inducing this). If $(mathcal C,F)$ is Tannakian, then the map $mathcal C to text{FinComod}_{operatorname{End}^vee(F)}$ is an equivalence of categories.

It follows from the above theorem that there is an equivalence of categories between:
$$ {text{Tannakian categories}, text{strictly commuting triangles}} leftrightarrow {text{coalgebras}, text{homomorphisms}}$$
By a "strictly-commuting triangle" of Tannakian categories $(mathcal C,F) overset{f}to (mathcal D,G)$, I mean a functor $f: mathcal C to D$ so that we have strict equality $F = Gcirc f$ as functors $mathcal C to text{Vect}$.

But when talking about functors, etc., it's evil to think about strict equality. Rather, there should be some two-categories floating around. There is a natural two-category whose objects are coalgebras: the one-morphisms are bicomodules, the two-morphisms are homomorphisms of bicomodules, and the one-composition is cotensor product of bicomodules. There are, to my mind, a few different two-categories whose objects are Tannakian categories: perhaps the one-morphisms should be triangles that commute up to specified natural isomorphism ("strong"?), or up to specified natural transformation in one way or in the other ("lax" and "oplax"?).

All together, my question is as follows:

Question: What is the correct, non-evil two-category of Tannakian categories so that the last two sentences of the "Tannaka theorem" above expresses an equivalence of two-categories

${text{Tannakian categories}} leftrightarrow {text{coalgebras}, text{bicomodules}, text{homomorphisms}}$?

Is this two-category a full sub-two-category of some larger two-category whose objects are pairs
$(mathcal C, F:mathcal C to text{Vect})$ with no further conditions? If so, does the full theorem represent some sort of "Tannakaization" of such pairs?

If modifications need to be made (not quite the right two-category of coalgebras, not quite the right definition of Tannakian category for the question to have an answer, etc.) feel free to answer the corresponding question.

spherical geometry - Plotting path between sphere or ellipsoid points?

I guess you are in the GPS business, aren't you ?
I think that Vincenty 1975 paper is what you are looking for. At least it should be a starting point for a bibliographic search.

Let me add a few remarks. Fortunately, free motion on the ellipsoid is an integrable system. Which means (loosely) that you can explicitely solve the equations of the trajectory using just a few integrals. This was done by Jacobi (1838).

So if you are not happy with Vincenty approach, there are two paths you can follow. Either look in a book (or click here) for the differential equations satisfied by the geodesics, and do a numerical integration. Or you can start from the solutions of these equations, which are given by elliptic functions. There are standard libraries in C for computing numerical values for these functions.

As a reference, I recommend the book "Elliptic functions and applications" by Derek F. Lawden. As far as I recall, the problem is solved in the book (I hope my memory is not betraying me). And I should add, this is a great book for everybody interested in making the connection between elliptic functions and classical mechanics.

By the way, if you are interested in the following question: on which manifold is the geodesic flow is integrable ? then
you can have a look at a short survey by Andre Miller.
And if you are interested in a clever proof of the integrability of the geodesic flow that works in any dimension, there is an online paper by S. Tabachnikov.