gn.general topology - Galois Groups vs. Fundamental Groups

I saw this question a while ago and felt something in the way of a (probably misguided) missionary zeal to make at least a few elementary remarks. But upon reflection,
it became clear that even that would end up rather long, so it was difficult to find the time until now.

The point to be made is a correction: fundamental groups in arithmetic geometry are not the same as Galois groups, per se. Of course there is a long tradition of
parallels between Galois theory and the theory of covering spaces, as when Takagi writes of being misled by
Hilbert in the formulation of class field theory essentially on account of
the inspiration from Riemann surface theory. And then, Weil was fully aware that
homology and class groups are somehow the same, while speculating that a sort of
non-abelian number theory informed by the full theory of the 'Poincare
group' would become an ingredient of many serious arithmetic investigations.

A key innovation of Grothendieck, however, was the formalism for refocusing attention on the
base-point. In this framework, which I will review briefly below, when one says
$$pi_1(Spec(F), b)simeq Gal(bar{F}/F),$$
the base-point in the notation is the choice of separable closure
$$b:Spec(bar{F})rightarrow Spec(F).$$
That is,

Galois groups are fundamental groups with generic base-points.

The meaning of this is clearer in the Galois-theoretic interpretation of the fundamental group of
a smooth variety $X$. There as well, the choice of a separable closure
$k(X)hookrightarrow K$ of the function field $k(X)$ of $X$ can be viewed as a base-point
$$b:Spec(K)rightarrow X$$
of
$X$, and then
$$pi_1(X,b)simeq Gal(k(X)^{ur}/k(X)),$$
the Galois group of the maximal sub-extension $k(X)^{ur}$ of $K$ unramified over $X$.
However, it would be quite limiting to take this last object as the definition of the fundamental group.

We might recall that even in the case of a path-connected pointed topological space $(M,b)$ with universal covering space $$M'rightarrow M,$$
the isomorphism $$Aut(M'/M)simeq pi_1(M,b)$$ is not canonical. It comes rather
from the choice of a base-point lift $b'in M'_b$. Both $pi_1(M,b)$ and $Aut(M'/M)$
act on the fiber $M'_b$, determining bijections
$$pi_1(M,b)simeq M'_bsimeq Aut(M'/M)$$
via evaluation at $b'$. It is amusing to check that the isomorphism of groups obtained thereby is independent of
$b'$ if and only if the fundamental group is abelian. The situation here is an instance of the choice involved in the isomorphism
$$pi_1(M,b_1)simeq pi_1(M,b_2)$$
for different base-points $b_1 $ and $b_2$.
The practical consequence is that when fundamental groups are equipped with natural
extra structures coming from geometry, say Hodge structures or Galois actions, different base-points give rise to enriched groups that are
are often genuinely non-isomorphic.

A more abstract third group is rather important in the general discussion of base-points. This is
$$Aut(F_b),$$
the automorphism group of the functor
$$F_b:Cov(M)rightarrow Sets$$
that takes a covering $$Nrightarrow M$$ to its fiber $N_b$. So elements of $Aut(F_b)$ are
compatible collections $$(f_N)_N$$ indexed by coverings $N$ with each $f_N$ an automorphism of the set $N_b$.
Obviously, newcomers might wonder where to get such compatible collections, but
lifting loops to paths defines a natural map
$$pi_1(M,b)rightarrow Aut(F_b)$$
that turns out to be an isomorphism. To see this, one uses again the fiber
$M'_b$ of the universal covering space, on which both groups act compatibly.
The key point is that while $M'$ is not
actually universal in the category-theoretical sense, $(M',b')$ is universal
among pointed covers. This is enough to show that an element of $Aut(F_b)$ is completely determined by its action
on $b'in M'_b$, leading to another bijection $$Aut(F_b)simeq M'_b.$$
Note that the map $pi_1(M,b)rightarrow Aut(F_b)$ is entirely canonical,
even though we have used the fiber $M'_b$ again to prove bijectivity, whereas the identification with $Aut(M'/M)$
requires the use of $(M'_b,b')$ just for the definition.

Among these several isomorphic groups, it is $Aut(F_b)$ that ends up most relevant for the
definition of the etale fundamental group.

So for any base-point $b:Spec(K)rightarrow X$ of a connected scheme
$X$ (where $K$ is a separably closed field, a 'point' in the etale theory), Grothendieck defines
the 'homotopy classes of etale loops' as
$$pi^{et}_1(X,b):=Aut(F_b),$$
where $$F_b:Cov(X) rightarrow mbox{Finite Sets}$$ is the functor that sends a finite etale covering
$$Yrightarrow X$$ to the fiber $Y_b$. Compared to a construction like
$Gal(k(X)^{ur}/k(X))$, there are three significant advantages to this definition.

(1) One can easily consider small base-points, such as might come from
a rational point on a variety over $mathbb{Q}$.

(2) It becomes natural to study the variation of $pi^{et}_1(X,b)$ with $b$.

(3) There is an obvious extension to path spaces $$pi^{et}_1(X;b,c):=Isom(F_b,F_c),$$ making up a two-variable
variation.

This last, in particular, has no analogue at all in the Galois group approach to
fundamental groups. When $X$ is a variety over $mathbb{Q}$, it becomes possible, for example, to study $pi^{et}_1(X,b)$ and
$pi^{et}_1(X;b,c)$ as sheaves on $Spec(mathbb{Q})$, which encode rich information about
rational points. This is a long story, which would be rather tiresome to expound upon here
(cf. lecture at the INI ).
However, even a brief contemplation of it might help you to appreciate the arithmetic perspective that general $pi^{et}_1$'s
are substantially more powerful than Galois groups. Having read thus far, it shouldn't surprise you that
I don't quite agree with
the idea explained, for example, in this post
that a Galois group is only
a 'group up to conjugacy'. To repeat yet again, the usual Galois groups are just fundamental groups with specific large base-points.
The dependence on these base-points as well as a generalization to small base-points
is of critical interest.

Even though the base-point is very prominent in Grothendieck's definition, a curious fact is that it took quite a long time for even the experts to fully metabolize its significance.
One saw people focusing mostly on base-point independent constructions
such as traces or characteristic polynomials associated to representations. My impression is that the initiative for allowing the base-points a truly active role
came from Hodge-theorists like Hain, which then was taken up by arithmeticians like Ihara and Deligne.
Nowadays, it's possible to give entire lectures just about base-points, as Deligne has actually done on several occasions.

Here is a puzzle that I gave to my students a while ago: It has been pointed out that
$Gal(bar{F}/F)$ already refers to a base-point in the Grothendieck definition. That is,
the choice of $Fhookrightarrow bar{F}$ gives at once a universal covering space and a base-point.
Now, when we turn to the manifold situation $M'rightarrow M$, a careful reader may have noticed a hint above that there is
a base-point implicit in $Aut(M'/M)$ as well.
That is, we would like to write $$Aut(M'/M)simeq pi_1(M,B)$$ canonically for some base-point $B$. What is $B$?

Added:

-In addition to the contribution of Hodge-theorists, I should say that Grothendieck himself urges attention to many base-points in his writings from the 80's, like 'Esquisse d'un programme.'

-I also wanted to remark that I don't really disagree with the point of view in JSE's answer either.

Added again:

This question reminds me to add another very basic reason to avoid the Galois group as a definition of $pi_1$. It's rather tricky to work out the functoriality that way, again because the base-point is de-emphasized. In the $Aut(F_b)$ approach, functoriality is essentially trivial.

Added, 27 May:

I realized I should fix one possible source of confusion. If you work it out, you find that the bijection $$pi_1(M,b)simeq M'_bsimeq Aut(M'/M)$$ described above is actually an anti-isomorphism. That is, the order of composition is reversed. Consequently, in the puzzle at the end, the canonical bijection $$Aut(M'/M)simeq pi_1(M,B)$$ is an anti-isomorphism as well. However, another simple but amusing exercise is to note that the various bijections with Galois groups, like $$pi_1(Spec(F), b)simeq Gal(bar{F}/F),$$ are actually isomorphisms.

Added, 5 October:

I was asked by a student to give away the answer to the puzzle. The crux of the matter is that
any continuous map $$B:Srightarrow M$$ from a simply connected set $S$ can be used as a base-point for the
fundamental group. One way to do this to use $B$ to get a fiber functor
$F_B$ that associates to a covering $$Nrightarrow M$$the set of splittings of the covering $$N_B:=Stimes_M Nrightarrow S$$ of $S$.
If we choose
a point $b'in S$, any splitting is determined by its value at $b'$, giving
a bijection of functors
$F_B=F_{b'}=F_b$ where $b=B(b')in M$. Now, when $$B:M'rightarrow M$$ is the universal
covering space, I will really leave it as a (tautological) exercise
to exhibit a canonical anti-isomorphism
$$Aut(F_B)simeq Aut(M'/M).$$ The 'point' is that $$F_B(M')$$ has a canonical
base-point that can be used for this bijection.

How do researchers carry out computational experiments in Graph Theory?

There are packages like, Combinatorica in Mathematica, GA, SA, PSO can be comparatively easily done in MATLAB, C++ has boost, Java has JGraphT and so on and on. My question is,

1. How do Graph Theorists carry out large computational experiments?


2. What languages or packages or libraries do they usually use? Is their any general preferences?


3. Do they use a combination of many sporadic resources? Like use something that is good at plotting, then use some other thing that is good for numerical solutions etc?


4. Where from you get Hard-Instances ?

Background:
I'm assigned to work on a GT problem named 'Degree Constrained Minimum Spanning Tree'. I want to study, implement and compare current algorithms. As I've been studying, I come to observe most of the algorithms are : Heuristics, Distributed Algorithms, Genetic Algorithms, Linear Programming (Narula-Ho) etc. Some uses methods called 'Particle Swarm Optimization', 'Simulated Annealing' and 'Ant Colony Optimization'. As far as I know MATLAB has built in routines for GA, SA, PSO, ACO etc but don't have any graph theory package. Combinatorica seems very good package but I don't have any access to it's accompanying book 'Computational Discrete Mathematics'. I don't know MATLAB or Mathematica.

Update:
A comprehensive list on GT packages/systems can be found here: http://wiki.sagemath.org/graph_survey

Update
It seems Mathematica 7 has all the above, mostly as built in functions/Commands.

soft question - the delta system lemma outside set theory

There's a nice application of the lemma to point-set topology (whether or not you consider this to be set theoretic is up to you :-) )

Define the following generalisation of separability:

A topological space X is ccc if every pairwise disjoint collection of non-empty open sets is countable.

It's clear that every separable space is ccc (because you can pick an element of the dense set in each open set), but ccc has the following theorem which makes it better behaved on products (a product of $> 2^{aleph_0}$ spaces with more than one point is not separable):

Theorem: Let ${ F_a : a in A }$ be a family of topological spaces such that every finite product is ccc. Then $prod F_a$ is ccc.

Proof:

Let T be an uncountable family of pairwise disjoint non-empty open sets. We can without loss of generality assume T consists of basis elements. Each of these basis elements is a product of sets of the form $U_a subseteq F_a$ with at most finitely many not equal to $F_a$.

Let $G = { { a : U_a neq F_a } : prod U_a in T }$. This is an uncountable collection of finite sets, so contains a delta system, say with root R.

But we must have the projection of $T$ to $prod_{a in R} F_a$ still be disjoint: For any $a notin R$ we have $U_a neq F_a$ for at most one element of T. But products of finitely many $T_a$ are ccc, thus we must have the projection of T (and thus T itself) being countable, contradicting the hypothesis.

QED

This in particular gives us the following corollary:

Theorem: An arbitrary product of separables spaces is ccc.

Proof: A finite product of spearable spaces is separable and thus ccc.

which is interesting because e.g. it tells us that there are compact hausdorff spaces which are not the continuous image of ${0, 1}^kappa$ for any $kappa$.

pr.probability - A geometric interpretation of independence?

If you leave the realm of abstract probability spaces and focus on probability in Banach spaces, there's a lot of geometry to take advantage of. Here's an example.

Let $X$ be a Banach space, and let $mathbb P$ be a Radon probability measure on $X$ such that continuous linear functionals are square-integrable (i.e. $int_X |f(x)|^2 ~dmathbb P(x) < infty$ for all $f in X^*$). For example, $X = C([0,1])$ with Wiener measure $mathbb P$.

These are sufficient conditions for there to exist a mean $m in X$ and covariance operator $K : X^* to X$ such that $$mathbb Ef = f(m) qquad mathrm{and} qquad mathbb E (fg) - f(m)g(m) = f(Kg)$$
for all $f, g in X^*$. One can show that

$$mathbb P left( m + overline{KX^*} right) = 1.$$

Under these very general assumptions, the probability concentrates on the affine subspace generated by the mean and covariance.

_{Reference: Vakhania, Tarieladze and Chobanyan, Probability Distributions in Banach Spaces}

big list - Applications of compactness

Any continuous function on a compact space is bounded and admits a maximum. This is perhaps the most important application to compactness.

Also pretty important in my opinion is the fact that a bijective continuous map $f:Xrightarrow Y$, X,Y Hausdorff topological spaces, is automatically an homeomorphism if X is compact.

Another important application of compactness is the Stone-Weierstrass theorem : assuming X compact, a subalgebra of $C^0(X,R)$ is dense iff it separates points.

Now something a bit more fancy :

Let G be a compact group. Then the semi-group generated by an element is dense in the groupe generated by that element.

All maximal connected compact subgroups of Lie groups are conjuguated to each other.

Let $f_n$ a sequence of continuous functions on a compact space that converges uniformly to $f$. Then for all neighborhood $V$ of $f^{-1}(0)$, and any sufficiently big n, $f_n^{-1}(0)$ is contained in $V$.

Compact manifolds (more generally ANR) have finitely generated homology groups.

On a compact smooth riemannian manifold, there is always infinitely many geodesics connecting two points.

The list goes on forever. Let me end with some famous conjecture on compact spaces (Kaplansky). Let X be a Hausdorff compact space. Are all algebra homomorphisms from $C^0(X)$ to a Banach algebra A , continuous ?

Why not use usual topology in ordered spaces ?

Pretopological spaces generalize both the topological notion of convergence and most kinds of order convergence. In a toplogical space X, one can define a satisfactory notion of convergence by filters. A filter in X is a nonempty family of subsets of X that is closed under finite intersections, supersets and that does not contain the empty set. The systems of neighborhoods (not just open neighborhoods) of a point forms a filter. A filter is said to converge to a point if it contains all neighborhoods.

One can abstract from this concept and define a pretopological space by a set X of points and for every point x in X a Filter representing abstract Neighborhoods such that x is an element of every neighborhood. A filter now converges again to a point if it includes every neighborhood.

There are various criteria by which one can identify pretopological spaces that are actually topological spaces. The Handbook of Analysis and its Foundations by Eric Schechter contains a lot of material on various forms of convergences and is a good reference for such questions. But there is no reason that the various noions of order convergence are topological. Actually, using the Bourbaki classifcation topological structures and order structures are separate types of structures. They only coincide if one wants by, say, using the order topology on a completely preordered set, in which case topological convergence also leads to a nice type of order convergence.

at.algebraic topology - Fundamental group of the line with the double origin.

In the simplest cases, the fundamental group serves as a measure of the number of 2-dimensional "holes" in a space. It is interesting to know whether they capture the following type of "hole".

This example may look pathological, but one must understand where one gets stuck, when one tries to study pathological spaces. It helps one in understanding where exactly all the extra nice conditions are used, and hopefully this type of approach will help in minimizing the number of false beliefs we unconsciously have.

The line with the double origin is the following space. In the union ${0} times mathbb R cup { 1 } times mathbb R$, impose the equivalence relation $(0, x) sim (1, x) $ iff $x neq 0$.

This space is locally like the real line, ie a $1$-manifold in everything except the Hausdorff condition. It is connected, path-connected and semilocally simply connected. Just the sort of nice space you study in the theory of fundamental group and covering spaces, except for the (significant) pathology that it has one inconvenient extra point violating the Hausdorff-ness.

It seems that the usual methods of computing the fundamental group are not working for this space. Van Kampen's theorem in particular does not apply. Also the covering spaces are weird, just like this space. In fact this space would have been a covering of $mathbb R$, were it not for the condition that the preimage of every point is a disjoint union of open sets.

So, what if we try to compute the fundamental group of this space? I would be satisfied to know whether it trivial or not. Say, is the collection of homotopy classes of loops based at $1$ nontrivial? It is possible to speculate that a certain loop based at $1$ which passes through both the origins on this special line, in such a way that it passes through the "upper" origin, ie $(1,0)$ on the way left, and it passes through the lower origin, ie $(0,0)$, ought not to be homotopic to the constant loop based at $1$. But how to go about proving/disproving this statement?

statistical physics - Mathematica/Matlab/other for calculating Onsager's exact solution to the 2d Ising model

Not that it's directly relevant, but I have code for the generator matrix of a 1D Glauber-Ising model that could probably be reworked into 2D...

---

function y = glauber1d(symb,n,varargin);

% produces the generator matrix etc for a 1D Glauber-Ising model of n spins
% call as either glauber1d(1,n) for a less complete symbolic result, or 
% glauber1d(0,5,[a,mu,H,kT,J]) for a more complete numerical result--i.e.,
% symb is a flag indicating whether or not to use symbolic calculations
% (this requires the symbolic toolbox in order to work)

% a (Glauber's alpha) is the spin flip rate, depends on the coupling 
%   between the GI system and the bath; 
% mu is the magnetic moment associated with the spins; 
% H is the magnetic field strength;
% kT is (well, you know);
% J is the exchange energy

if symb     % SYMBOLICS
    syms a b g real;
else        % NUMERICS
    args = varargin{1};
    a   = args(1);
    mu  = args(2);
    H   = args(3);
    kT  = args(4);
    J   = args(5);
    b = tanh(mu*H/kT);   % Glauber's beta (NOT 1/kT)
    g = tanh(2*J/kT);   % Glauber's gamma
end

% produce an array with rows equal to spin configurations
temp = dec2bin(0:((2^n)-1),n);
for j = 1:2^n
    for k = 1:n
        s(j,k) = 2*str2num(temp(j,k))-1;
    end
end

% obtain spin flip rates
for j = 1:2^n
    for k = 1:n
        km = mod(k-2,n)+1;
        kp = mod(k,n)+1;
        temp = (g/2) * (b - s(j,k)) * (s(j,km) + s(j,kp));
        w(j,k) = (a/2) * (1 - b*s(j,k) + temp);
    end
end

% generator matrix
if symb
    Q = sym(zeros(2^n));
else
    Q = zeros(2^n);
end

for j1 = 1:2^n
    for j2 = 1:2^n
        if sum(abs( s(j1,:) - s(j2,:) )) == 2   % single spin flip
            % now find out which spin gets flipped
            k0 = find( s(j1,:) - s(j2,:) );
            Q(j1,j2) = w(j1,k0);
        end
    end
end

if symb
    Q = simplify( Q - diag(sum(Q,2)) );
else
    Q = Q - diag(sum(Q,2));
end

% invariant distribution p (if you want it)
if 2^n - 1 - rank(Q)
    'error'
    y = 0;
    return;
else
    p0 = null(Q')';
end
if symb, simplify(p0); end
sp0 = sum(p0);
if symb, simplify(sp0); end
p = p0 / sp0;   % invariant distribution

y = Q;

geometry - How can I efficiently determine which side of a line segment is internal to the polygon?

As part of a larger analysis I have a need to break a polygon into it's individual line segments and mark which side is "inside" of the polygon. If your curious this is going to be fed into a big parallel map reduce algorithm to translate the representation of the polygon into a more efficient data structure for fast recall.

The naive solution I've come up with is to first cast a ray towards the calculated centroid of the polygon from each vertex of every line segment and count the number of line intersections between the vertex and the centroid. That way I can determine if the side of each line that is facing the centroid is "internal" or not. Based upon whether or not each ray has an odd or even number of intersections.

The best way to think about this is that I will be creating a triangle at a single line segment with the two rays that are cast towards the centroid. I can determine based upon the internal angles which side of the line segment is "facing" the centroid. There is a distinct difference between facing the centroid, and actually being on the internal side of the polygon.

Unfortunately, this is quite inefficient to calculate. Assume I have a very detailed polygon with tens of millions of vertexes. It would be very slow if for each vertex I created a vector between the centroid and the vertex, then ran a line intersection algorithm against every other line segment in the polygon. It's just not going to finish in a timely manner.

I think I can walk the line segments one by one and determine based upon the internal angles at each vertex which side of each line segment is "internal" to the polygon. Are there any known theorems out there that I am unaware of that will help me answer this problem?

lie algebras - reductive Lie subalgebra

Sorry, this started as a comment, but got too long.

If $G$ is semisimple, then every derivation of $G$ is inner, so
that the normalizer $N_L(G)=C_L(G)+G$ where $C_L(G)$
is the centralizer. In this situtaion Michele's condition holds
if and only if the centralizer is trivial.

However the case where $G$ is reductive isn't so easy.
A reductive $G$ is the direct sum of an Abelian and a semisimple
Lie algebra. The Abelian part can have (if at least two-dimensional)
non-trivial derivations. These will lift to non-inner derivations
of $G$. If we let $L$ be the semidirect product of $G$ with
a one-dimensional Lie algebra using this derivation, then
$L$ normalizes $G$, $Lne G$ but $C_L(G)$ is trivial.

co.combinatorics - Examples of Super-polynomial time algorithmic/induction proofs?

In combinatorics, one can sometimes get an algorithmic proof, which loosely has the following form:

-The proof moves through stages

-An invariant is shown to hold by induction from previous stages

-The algorithm is shown to terminate

-The invariant holding at termination implies the desired claim.

Perhaps the best example I know of is an algorithmic proof of Konig's theorem, which in a sense is just a max-flow/min-cut algorithm. In some sense, most induction proofs fit this mold.

The above example runs in polynomial time. Are there good examples of algorithmic/induction proofs that take super-polynomial time to prove things that don't obviously need such induction?

That is, I don't want Ackermann-like recurrences, or anything that is "brute-force". Further, I'm not looking for super-polynomial time algorithms that solve instances of problems, but rather am looking for super-polynomial time algorithms that prove a theorem of some sort (eg. like a combinatorial max-min theorem in the above example).

soft question - Which magazines should I read?

I collected Kim Greene's answers into one, which unfortunately makes it look like the answer came from me. (They are fine answers, just not mine.) My own answer is that in Kim's list, only the Notices and the Intelligencer provide a good graduate/professional perspective on mathematics. However, those two aside, the "magazines" that you read should also include the four best Internet resources for serious mathematics: The arXiv, MathSciNet, Wikipedia, and now this site. There are other fine math web sites out there, but as far as I know, nothing else is as important as these four.

linear algebra - Is there a version of inclusion/exclusion for vector spaces?

One way to look at this question is via quiver representations. Two subspaces of a vector space form a representation of the quiver $A_3$ with orientations $bullet rightarrow bullet leftarrow bullet$ with the additional condition that both maps are injective (that's tautology). Now, every representation of $A_3$ is a sum of indecomposables, whose dimension vectors are (1,0,0), (0,1,0), (0,0,1), (1,1,0), (0,1,1), (1,1,1), where for the first and the third one the maps are not injective, and for the remaining four the maps are injective. Thus, the dimension vector for a generic representation with injective maps is a(0,1,0)+b(1,1,0)+c(0,1,1)+d(1,1,1)=(b+d,a+b+c+d,c+d). Clearly, the dimension of the sum of the two subspaces is b+c+d (the complement is represented by the first summand a(0,1,0)), which is (b+d)+(c+d)-d, and d is the dimension of the intersection.

Now, for the three subspaces we deal with representations of the quiver $D_4$ with injective maps. (I am too lazy to draw $D_4$ on MO, sorry!). Indecomposable representations have dimension vectors $(d_1,d_2,d_3,d)$ (note different ordering of dimensions - the largest one is the last one) being (1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1), (1,0,0,1), (0,1,0,1), (0,0,1,1), (1,1,0,1), (1,0,1,1), (0,1,1,1), (1,1,1,1), (1,1,1,2) - altogether 12 vectors. Among them, the first three have non-injective maps, and the fourth one captures the complement of the sum of our three subspaces. Thus, there are 8 numbers through which the dimension can be expressed (not 7, as in the inclusion-exclusion formula), and what remains is to choose the 8th number, in addition to the dimensions of all possible intersections, reasonably for your needs.

For $k>3$ subspaces the classification problem stops being of finite type so it becomes a bit more nasty...

ag.algebraic geometry - Functorial point of view for formal schemes

There are many nonequivalent generalities in which one can define a formal scheme, for example the definitions in Hartshorne and in EGA are not quite the same. (I use in this answer some parts of my own editing in nlab's entry where more references can be found). In my understanding, whatever the definition is, the category of formal schemes is a realization of certain subcategory of Ind-schemes. Typically one requires at least that the [[ind-object]] in the subcategory may be represented by a diagram whose connecting morphisms are closed immersions of schemes. A pretty modern treatment is in

• A. Beilinson, V. Drinfel'd, Quantization of Hitchin's integrable system and Hecke eigensheaves on Hitchin system, preliminary version (pdf)

Some subcategories of Ind-objects in many algebraic categories can be described by putting the topology on algebraic objects. Thus the complete local rings, or more general the pseudocompact case, in the Grothendieck's approach to local schemes. One can use a topological version of Yoneda on rings to get a nice theory of formal schemes, over an arbitrary ring:

• B. Pareigis, R. A. Morris, Formal groups and Hopf algebras over discrete rings, Trans. Amer. Math. Soc. 197 (1974), 113--129 (doi).

Nikolai Durov suggests to use directly the Gabriel-Demazure approach but not over Aff but over the opposite to the category of pairs (commutative ring, nilpotent ideal). Formal schemes should be an appropriate subcategory of that category of presheaves. That larger category (but without singling out there the smaller subcategory which would correspond more precisely to Grothendieck's formal schemes) is sketched in ch. 7-9 of

• N. Durov, S. Meljanac, A. Samsarov, Z. Škoda, A universal formula for representing Lie algebra generators as formal power series with coefficients in the Weyl algebra, Journal of Algebra 309, n. 1, 318--359 (2007)
  (doi:jalgebra)
  (math.RT/0604096).

nt.number theory - Why no abelian varieties over Z?

Comments by Anweshi

The essential point is what Emerton mentioned, ie the analogy with Minkowski's theorem on number fields with ramification. The basic principle is that "arithmetic is geometry". Number rings are in a sense zero dimensional objects, elliptic curves one dimensional objects and abelian varieties correspond to higher dimensions. So we have Minkowski's theorem. And we ask, can we extend it to higher dimensions? Tate, after setting up the theory correctly as in his famous survey article on the arithmetic of elliptic curves, proved it rather trivially for elliptic curves(as Emerton mentions). Now the task is for abelian varieties.

Fontaine comes along, and proves that it is indeed the case. But the proof turns out to be much more complicated than expected. He built a whole lot of "Fontaine theory" around this. It goes into $p$-adic Hodge theory, $p$-adic Galois representations etc. He worked on it for some 15 years in isolation, it is said. The first major success of his theory was this theorem, and later it gained popularity. Now it is a major stream of research in arithmetic geometry.

References:

• Neukirch, Algebraic number theory, for the general philosophy that "arithmetic is geometry".


• Notes of Robert Coleman's course on Fontaine's theory of the mysterious functor


• The Bourbaki expose of Bearnadette Perrin-Riou. Fonctions L p-adiques des représentations p-adiques, Astérisque 229, (1995).


• Tate, The Arithmetic of Elliptic Curves, Survey Article, Inventiones.

It could be also worthwhile to have a look at the articles on finite flat group schemes in the volume Arithmetic Geometry of Cornell and Silverman, and in the volume Modular forms and Fermat's Last Theorem by Cornell, Silverman and Stevens. This is all intimately connected with them, as Emerton mentions. In fact, you can find a particular viewpoint by Fontaine on Finite Flat group Schemes.

There could be also be a simpler motivic explanation of this, without getting into the intricacies of Fontaine theory. The reason I think so is the following. I have heard the answer that there is no elliptic curve over $F_1$ because from the zeta functions the motives turn out to be mixed Tate. But, on the other hand, my own "proof" of this fact was that if there were an elliptic curve or abelian variety over $F_1$, it would be extensible to $Spec Z$ and there by Fontaine's theorem the only abelian scheme is the trivial one. Ever since I have wondered, whether it is possible to substitute Fontaine's theory arguments with motivic ones.

Emerton clarified to me in this connection: From a number theorist's point of view, p-adic Hodge theory is one of the key ingredients in the theory of motives, so these arguments are motivic, in a certain sense. (Perhaps one can say that p-adic Hodge theory encodes arithmetic properties of motives in a way analogously to the way that Hodge theory encodes geometric and analytic properties.)

Thus, by Emerton's answer, Fontaine theory seems to be thus a deeper part of motives. However, this "no abelian variety over Z" theorem of Fontaine was the first major application of Fontaine's theory. I imagined, if any results of Fontaine's theory were to be replaced by usual motivic arguments, then this ought to be the first candidate.

Before stopping, I must mention the intimate connection all this has with Iwasawa theory. Fontaine's theory is very much tangled with it, as could be seen in the expose of Perrin-Riou. However the more knowledgeable people should clarify on this.

This might be an apt place to mention the conference in honor of Fontaine. He is about to retire, after his great achievements.

Comment by Ilya

I think this should be indeed related to motives. (update: I think others provided some good references.)

Comments by Emerton

(1) There were earlier applications of Fontaine's results on finite flat group schemes; e.g. they played a role in Mazur's proof of boundedness of torsion of elliptic curves over $mathbb Q$. I say this just to emphasize that Fontaine's theory didn't really develop in isolation.
His theory is deep and technical, and it took people time to absorb it. But the theory of finite flat group schemes and $p$-divisible groups has a long history intertwined with arithmetic: there are results going back to Oda, Raynaud, and Tate; Fontaine generalized these; they were used by Mazur in his work, and by Faltings; Fontaine generalized further to $p$-adic Hodge theory (a theory whose existence was in part conjectured earlier by Grothendieck, motivated by, among other things, the work of Tate); ... . One shouldn't think of these ideas as being esoteric (despite the ``black magic'' label); they are and always have been at the forefront of the interaction between geometry and arithmetic, in one guise or another. (As another illustration, Fontaine's theory also closely ties in with earlier themes in the work of Dwork.)

(2) I'm not sure that there is any particular kind of usual motivic argument. The phrase motive conjures up a lot of different images in different peoples minds, but one way to think of what motivic means is that it is the study of geometry via structures on cohomology. From this point of view, $p$-adic Hodge theory is certainly a natural and important tool.

Here are some papers that give illustrations of $p$-adic Hodge theoretic reasonsing in what might be regarded as a motivic context:

Grothendieck, Un theoreme sur les homomorphismes de schemas abeliens, a wonderful paper.
Although the results are essentially recovered and generalized by Delignes work in his Hodge II paper, it gives a fantastic illustration of how $p$-adic Hodge theoretic methods can be used to deduce geometric theorems.

Kisin and Wortmann, A note on Artin motives

Kisin and Lehrer, Eigenvalues of Frobenius and Hodge numbers

James Borger, Lambda-rings and the field with one element

These three are chosen to illustrate how $p$-adic Hodge theory arguments can be used to make geometric/motivic deductions. The paper of Borger is also an attempt in part to provide foundations for the theory of schemes over the field of one element, and illustrates how $p$-adic Hodge theory plays a serious role in their study.

Maulik, Poonen, Voisin, Neron-Severi groups under specialization, a terrific paper, which
illustrates the possibility of using either $p$-adic Hodge-theoretic arguments or classical Hodge-theoretic arguments to make geometric deductions. (This is the same kind of complementarity as in Grothendieck's paper above compared to Deligne's Hodge II.)

Comments by Anweshi.

@Emerton, or anybody else: If there is something which does not make sense in my foray into "motivic" pictures, or something else which does not make sense, please feel free to erase and edit in whatever way you wish.

a further question by Thomas:

The great references given above let me ask about the current status of the many conjectures and open questions in Illusie's survey, e.g. finiteness theorems, crystalline coefficients, geometric semistability,... ?

• ilya's comment: I think it would be very useful if somebody posted a question along the lines of what Thomas suggests, especially filling in some background from Illusie's paper (I would do it, but I don't have the paper itself).

** Anweshi's comment:** Fontaine's theory uses a great deal of crystalline cohomology. For instance please see Robert Coleman's notes referred above.

singularity theory - Poll about your proof of resolution of singularities and a request for advice

The questions first: What is the proof of resolution of singularities that you know?

Why am I asking?: There are a number of proofs of resolution of singularities of varieties over a field of characteristic zero, all with more or less similar flavor but different in technical details and in choices that the resolution algorithm allows us to make. When writing a proof that uses specific features of some of those details I can't stop being uneasy about assuming the reader read about the specific constructions elsewhere.
I would like to know from MOers what proof you have seen and if you have a reason for the choice, if it was a choice, I would like to hear it too.

Maybe asking about what you know is too invasive. I am just asking for the proof that you happened to find in your way, even you have only read a few lines of it.

The purpose of the question: The conspicuous one. To get a sense, by a rough approximation and a small sample, of what proofs are more culturally known. Have a concrete feeling when sending a reader to find the details in other paper, either of feeling OK with it or of guilt.

It is a question about fashion, which also has its role in mathematics... and knowing what the fashion is is useful.

What details?: Although I had in mind a specific detail of the proofs I didn't mention it because it is not the only one that changes from proof to proof and because the result of the poll gives information about all of them. Examples are: the resolution invariant, the ways of making the local descriptions of the centers of blowings-up match to form a globally defined smooth subvariety, the ways of getting functoriality and the different meanings that functoriality can have...

(edit) Forgot the "request for advise": If you have would like to give advise about how you have dealt with similar situations and describe your example that is welcomed.

It is a community wiki question, so feel free to change what is said here if needed or if you want the poll to also give information about other questions that you would like to be answered. (or for correcting the English!)

soft question - MathSciNet vs Google Scholar

Not having subscription access to Zentralblatt, I won't try to comment on its merits. Leaving that aside,
MathSciNet is certainly the most comprehensive database of published work in mathematics (and to some extent the closely related areas of mathematical physics, etc.). It's constructed and maintained by a substantial paid staff of professional mathematicians and technicians, with no advertising revenue. Though AMS is a nonprofit organization and MathSciNet is partly subsidized from voluntary membership dues, there is no free lunch. For some time now they've compensated reviewers, who used to work for free, with 8 dollars worth of AMS credits for each review written; it's a token payment but eats into AMS book revenues.

Availability to people outside the North American system of colleges and universities which pay for the service is always problematic; there are frequent arguments in the AMS Council about how to subsidize MathSciNet as well as journals and books for developing countries. Anyone in doubt about the complexity of AMS finances should try to chat with the incoming AMS president Eric Friedlander, who has long experience as a trustee.
Having said that, I'm one of the lucky people who (so far) have MathSciNet access
and can use my university system password even at home. Whether our financially stressed library continues the arrangement is an open question, since they have to cancel hundreds of journal subscriptions every year even in stable economic times.

On the plus side, MathSciNet has developed its search capabilities even though there is usually too little access to the text of articles or books to search that far. And for a couple of decades the ability to list references in a given paper and citations to the paper in reviews or other papers has grown rapidly. Another very useful feature is the author profile (even for the elusive et al.), with lists of all published work and links when possible to co-authors, math genealogy.

Also on the plus side is the professionalism of the staff and the attempt to keep all data precise, even the troublesome identification of authors by sometimes variable or duplicated names (notable for Chinese authors).

For me Google Scholar is a back-up source of limited use (and limited trustworthiness), which often has the defect of giving too much information in a time-wasting format. But it's definitely free of charge and will contain even more information if publishers can be persuaded to hand over all content to them
(presumably in exchange for advertising space or priority listing or even old-fashioned cash).

soft question - why haven't certain well-researched classes of mathematical object been framed by category theory?

To turn a class into a category, you need a notion of morphisms between objects in the class. That's the long and short of it.

Consider for instance the class of infinite real series, say viewed as the set $S = mathbb{R}^{aleph_0}$ of sequences of real numbers. (There is often some notational and "ontological" confusion between the terms of an infinite series, its associated sequence of partial sums, and its sum, if it has one. Which one of these "is" the series? But such considerations are not relevant here and indeed are usually viewed as antithetical to the categorical point of view.) To get a category, you need to identify a set of morphisms between any two elements of this set. This can certainly be done in any number of ways -- for instance one could use the ordering induced from the standard ordering on $mathbb{R}$ and the lexicographic ordering of the sequence, and then $S$ is a totally ordered set. We could then define a category by having $operatorname{Hom}(s,t)$ to be a one point set if $s leq t$ and the empty set otherwise (and then take the unique composition law of morphisms, defined when $s leq t leq u$).

But the question is: what does this category have to do with any aspect of the theory of
infinite series? Apparently nothing. You could create any number of other categories with underlying set $S$ but you run into the same problem: the very old and extremely well-developed area of mathematics which studies the convergence and divergence of real infinite series simply does not have anything evident to do with any notion of "morphisms" between infinite series.

Similarly for the other examples you mention. Categorical structure is a very fundamental kind of mathematical structure; it's a great way of thinking and unifies and conceptualizes the study of many kinds of mathematical objects in highly disparate fields. But it doesn't explain everything, and it is frankly a bit weird to think it should.

inequalities - Is there a good reason why a^{2b} + b^{2a}

Fixed now. I spent some time looking for some clever trick but the most unimaginative way turned out to be the best. So, as I said before, the straightforward Taylor series expansion does it in no time.

Assume that $a>b$. Put $t=a-b=1-2b$.

Step 1:
$$
begin{aligned}
a^{2b}&=(1-b)^{1-t}=1-b(1-t)-t(1-t)left[frac{1}2b^2+frac{1+t}{3!}b^3+frac{(1+t)(2+t)}{4!}b^4+dotsright]
\
&le 1-b(1-t)-t(1-t)left[frac{b^2}{1cdot 2}+frac{b^3}{2cdot 3}+frac{b^4}{3cdot 4}+dotsright]
\&
=1-b(1-t)-t(1-t)left[blogfrac 1{a}+b-logfrac {1}aright]
\
&=1-b(1-t^2)+(1-b)t(1-t)logfrac{1}a=1-bleft(1-t^2-t(1+t)logfrac 1aright)
end{aligned}
$$
(in the last line we rewrote $(1-b)(1-t)=(1-b)2b=b(2-2b)=b(1+t)$)

Step 2.
We need the inequality $e^{ku}ge (1+u)(1+u+dots+u^{k-1})+frac k{k+1}u^{k+1}$ for $uge 0$.
For $k=1$ it is just $e^uge 1+u+frac{u^2}{2}$. For $kge 2$, the Taylor coefficients on the left are $frac{k^j}{j!}$ and on the right $1,2,2,dots,2,1$ (up to the order $k$) and then $frac{k}{k+1}$. Now it remains to note that $frac{k^0}{0!}=1$, $frac{k^j}{j!}ge frac {k^j}{j^{j-1}}ge kge 2$ for $1le jle k$, and $frac{k^{k+1}}{(k+1)!}ge frac{k}{k+1}$.

Step 3:
Let $u=logfrac 1a$. We've seen in Step 1 that $a^{2b}le 1-b(1-tmu)$ where $mu=u+(1+u)t$. In what follows, it'll be important that $mulefrac 1a-1+frac 1a t=1$ (we just used $logfrac 1ale frac 1a-1$ here.

We have $b^{2a}=b(a-t)^t$. Thus, to finish, it'll suffice to show that $(a-t)^tle 1-tmu$. Taking negative logarithm of both sides and recalling that $frac 1a=e^u$, we get the inequality
$$
tu+tlog(1-te^u)^{-1}ge log(1-tmu)^{-1}
$$
to prove.
Now, note that, according to Step 2,
$$
begin{aligned}
&frac{e^{uk}}kge frac{(1+u)(1+u+dots+u^{k-1})}k+frac{u^{k+1}}{k+1}
gefrac{(1+u)(mu^{k-1}+mu^{k-2}u+dots+u^{k-1})}k+frac{u^{k+1}}{k+1}
\
&=frac{mu^k-u^k}{kt}+frac{u^{k+1}}{k+1}
end{aligned}
$$
Multiplying by $t^{k+1}$ and adding up, we get
$$
tlog(1-te^u)^{-1}ge -ut+log(1-tmu)^{-1}
$$
which is exactly what we need.

The end.

P.S. If somebody is still interested, the bottom line is almost trivial once the top line is known. Assume again that $a>b$, $a+b=1$. Put $t=a-b$.

$$
begin{aligned}
&left(frac{a^b}{2^b}+frac{b^a}{2^a}right)^2=(a^{2b}+b^{2a})(2^{-2b}+2^{-2a})-left(frac{a^b}{2^a}-frac{b^a}{2^b}right)^2
\
&le 1+frac 14{ [sqrt 2(2^{t/2}-2^{-t/2})]^2-[(1+t)^b-(1-t)^a]^2}
end{aligned}
$$
Now it remains to note that $2^{t/2}-2^{-t/2}$ is convex on $[0,1]$, so, interpolating between the endpoints, we get $sqrt 2(2^{t/2}-2^{-t/2})le t$. Also, the function $xmapsto (1+x)^b-(1-x)^a$ is convex on $[0,1]$ (the second derivative is $ab[(1-x)^{b-2}-(1+x)^{a-2}]$, which is clearly non-negative). But the derivative at $0$ is $a+b=1$, so $(1+x)^b-(1-x)^age x$ on $[0,1]$. Plugging in $x=t$ finishes the story.

oc.optimization control - Is there an intuitive explanation for an extremal property of Chebyshev polynomials?

Let's denote $Pi_n$ the vector space of polynomial functions on I:=[-1,1] of degree less than or equal to n. The optimization problem you quoted is equivalent to:

Problem(2): Find $qinPi_{n-1}$ that minimizes the uniform distance on I from the function $f(x)=x^n.$

While it is clear by compactness that Problem(2) has a solution, it's not obvious that the solution is unique, because the uniform norm is not uniformly convex (lack of unicity already appears in the analogous problem of point-line distance in $mathbb{R}^2$ with the max norm). The magic of polynomials is that the solution is always unique, for any continuous function $f$. Not only, but Chebyshev also gave a characterization of the minimizer: it is the unique polynomial $q$ such that $f(x)-q(x)$ attains the maximum absolute value in at least n points, with alternate sign.
(Polynomials are not the unique functions with this property; more generally one defines "Haar families", that span finite dimensional spaces analogous to the $Pi_n$, and for them the argument works as well). Going back to your optimization problem, you have that $p(x)$ is the unique monic polynomial with all real simple zeros and that reaches the maximum absolute value with alternate sign between consecutive zeros. With a bit more work one arrives to $T_n/2^{n-1}$ (or, at this time, one pulls it out of the hat, but at this point I'd consider that quite more fair, and would have no objections, especially if the hat is the most noble one of Pafnuty Lvovich).

PS: Trying to answer the "psychology of mathematics" part of your question (how one arrives to the $T_n$ from the optimization problem). Once the problem is reduced to that of determining the n-th degree polynomial $T$ (say with positive leading coefficient) that oscillates n+1 times between it maximum value 1 and its minimum value -1 on the interval [-1,1], I guess that very soon one suspects that circles and trigonometric functions are around (I can't say it certainly, because I already know the answer!). But if one computes the first few such polynomials, and look at their graphs, they clearly look like sinusoidal curves drawn on a cylinder, and at that point one could recall from high school memories that cos(nx) is a trigonometric polynomial of cos(x), and observe it has clearly the wanted property.

soft question - Describe a topic in one sentence.

Representation theory of Lie groups: there is a whole world between $mathrm{Sym}^n V$ and $wedge^n V$. (Okay, this is an oversimplication - I am talking about the representations of $mathrm{GL}left(Vright)$ here, but this is the fundament of all other classical groups.)

Constructive logic: if you can't compute it, shut up about it. (At least some forms of constructive logic. Brouwer seemed to have a different opinion iirc.)

Homological algebra: How badly do modules fail to behave like vector spaces?

Gröbner basis theory: polynomials in $n$ variables can be divided with rest (at least if you have some $Oleft(N^{N^{N^{N}}}right)$ of time)

Finite group classification: what works for Lie groups will surely be even simpler for finite groups, right? ;)

Algebraic group theory: In order to differentiate a function on a Lie group, we just have to consider the group over $mathbb Rleft[varepsilonright]$ for an infinitesimal $varepsilon$ ($varepsilon^2=0$).

Semisimple algebras: The representations of a sufficiently nice algebra mirror a structure of the algebra itself, namely how it breaks into smaller algebras.

$n$-category theory: all the obvious isomorphisms, homotopies, congruences you have always been silently sweeping under the rug are coming back to have their revenge.

Modern algebraic geometry (schemes instead of varieties): let's have the beauty of geometry without its perversions.

How many of these did I get totally wrong?

Is every finite-dimensional Lie algebra the Lie algebra of an algebraic group?

Sorry to tune in so late to this conversation, but I think it's worth pointing out some of the paper trail on the question (supplementing BCnrd's comment). This goes back to Chevalley's initial work in the 1950s, especially in volume II (in French) of his projected
six volume work Theorie des groupes de Lie. The first volume (in English) was published by Princeton Press, then II and III followed but no more; his 1956-58 Paris seminar changed the whole approach to linear algebraic groups and largely ignored the Lie algebras. In Section 14 of II, working over an arbitrary field of characteristic 0, Chevalley asks which Lie subalgebras $mathfrak{g} subset mathfrak{gl}(V)$ (with $dim V < infty$) can be Lie algebras of closed subgroups of the general linear group. He worked out a number of nice features of the unique smallest algebraic subalgebra containing $mathfrak{g}$: it has the same derived algebra as $mathfrak{g}$, for instance. In fact, the derived algebra of any $mathfrak{g}$ is algebraic.

Some of these ideas were written down by Borel (Section 7) and by me (Chap. V)
in our Springer graduate texts, working over an algebraically closed field of characteristic 0 (my treatment came from the earlier Bass/Borel notes). These sources include further references to papers by Hochschild and others along with the more scheme-theoretic treatment in the 1970 book by Demazure and Gabriel: II, Section 6, no. 2. They assume $k$ is a field and $mathfrak{G}$ is a " $k$-groupe localement algebrique" with an appropriate Lie algebra attached, then study possible algebraic subalgebras.

In prime characteristic the notion of algebraic Lie algebra becomes much more problematic. See Seligman's 1965 book Modular Lie Algebras, VI.2, for some
discussion. For example, the Lie algebra
$mathfrak{sl}(p,k)$
is usually simple modulo its one-dimensional center, but the quotient algebra can't be algebraic since then it would be the Lie algebra of a known simple algebraic group. Even more extreme are the extra simple Lie algebras of "Cartan type"
(and others for small primes), for which there are no corresponding groups. `

pr.probability - Stationary Solutions of stochastic differential equations

It is hard to be brief here, but I will try.

One answer is: when the corresponding stationary Fokker-Planck equation (aka forward Kolmogorov equation) has a nonnegative integrable solution. The density is then obtained by normalization of that solution. This is not a very good answer because FP equations are often not so easy to analyze.

In fact, it is hard to guess what is the question you really wanted to ask. For example, one may say that your question is twofold:
1) when is there an invariant probability distribution?
2) If it exists, is it absolutely continuous w.r.t. Lebesgue?

Existence is guaranteed if the drift prevents the trajectories from going to infinity so that they spend a lot of time in a compact set. Some of the relevant keywords are: Lyapunov-Foster functions, Harris recurrence. Among weakest known conditions guaranteeing existence of invariant distributions are those due to Veretennikov.

Given part 1), absolute continuity of the stationary distributions can essentially be deduced from absolute continuity of transition probabilities. This part is easy if your equations are elliptic and not so easy if the noise excites only some directions.

The analysis can be quite nontrivial depending on how bad your equation is, as a look at a recent paper http://arxiv.org/abs/0712.3884 might convince you.

graph theory - Degree sequences of multigraphs with bounded multiplicity

I got to thinking about this problem while sifting through the math puzzles for dinner thread. There's a fun puzzle by rgrig which asks the guests to prove that when they came to dinner two of them shook hands the same amount of times. The solution is to make the handshake graph, and apply the pigeonhole principle on the vertex degrees. The key observation is that if there are $n$ guests, then the degrees 0 and $n-1$ cannot both occur.

Yaakov Baruch made the astute comment that the result is false if the forgetful mathematicians shake hands twice with each other. However, note that mathematicians are probably not so forgetful to shake hands three times with someone. This leads us to the following questions:

Question 1. Is it true that for large $n$, every loopless multigraph on $n$ vertices with at most two parallel edges between any two vertices has two vertices of the same degree? This is false for $n=3,4,5,6,7$.

Question 2. Is there a nice characterization of such degree sequences?

I'll finish with what is known. If we allow loops, then the problem is trivial, because all sequences whose sum is even are degree sequences. To see this, put a matching on the odd degree vertices, and then add loops. For simple graphs, there are many nice characterizations. For example, the Erdos-Gallai theorem says that a decreasing sequence $(d_1, dots, d_n)$ is a degree sequence of a simple graph if and only if $sum_i d_i$ is even and for all $k in [n]$

[
sum_{i=1}^k d_i leq k(k-1)+ sum_{i=k+1}^n min (k, d_i).
]

This sort of answers Question 2, since a degree sequence of a multigraph with multiplicity at most 2 is the sum of two degree sequences of simple graphs. However, this is a rather convoluted characterization, and it is unclear how to answer Question 1 from it.

I'll end by mentioning that if we do not bound the multiplicity of edges, then there is a nice characterization of degree sequences of multigraphs by Hakimi (1962).

ho.history overview - Does there exist a comprehensive compilation of Erdos's open problems?

Fan Chung and Ron Graham's book Erdos on Graphs: His Legacy of Unsolved Problems (A. K. Peters, 1998) collects together all of Erdos's open problems in graph theory that they could find into a single volume, complete with bounties where applicable. Of course Erdos posed many other open problems in combinatorics and number theory that do not appear in this book. I once heard a rumor that some people were working on a project to publish a similar but more comprehensive book or series of books, covering all of Erdos's open problems, but I don't know if the rumor is true. Does such a compilation exist? If not, is there anything else like this besides Chung and Graham's book?

co.combinatorics - Looking for cubic, bipartite graphs with girth at least six and no cycles of length 8.

Desargues graph, also known as the generalized Petersen graph $G(10,3)$ has girth 6 and also contains cycles of length 8. There exist three 10-cages, smallest cubic graphs of girth 10. They have 70 vertices and none of them is vertex-transitive. For more information about the motivation
see here.

Therefore it is quite surprising that Gordon's example is so small. By the way, it is also arc-transitive. One may consider it as a Levi graph of a self-dual, flag-transitive 3-configuration of 19 points and 19 lines. Configuration contains triangles but has no quadrangles.

Here is a geometric realization of this graph.

Configuration with triangles but no quadrangles

1. A natural question is, whether this is the smallest graph with required properties.




2. Another related question is, whether there exist smaller bipartite graphs if the vertex-transitivity condition is dropped.

dg.differential geometry - Diffeomorphism groups of orbifolds

The result you want can be found in the following paper:

MR0955816 (89h:30028)
Earle, Clifford J.(1-CRNL); McMullen, Curt(1-MSRI)
Quasiconformal isotopies. Holomorphic functions and moduli, Vol. I (Berkeley, CA, 1986), 143--154,
Math. Sci. Res. Inst. Publ., 10, Springer, New York, 1988.

What they prove is actually pretty remarkable. Namely, let $S$ be a hyperbolic surface. Then there is a family $phi_t$ of self-maps of $text{Diff}^{0}(S)$ such that $phi_0$ is the identity, such that $phi_1$ is the constant map taking each diffeomorphism to the identity diffeomorphism, and such if $f in text{Diff}^0(S)$ commutes with a finite order diffeomorphism $g$ of $S$, then $phi_t(f)$ also commutes with $g$ for all $t$. In other words, you can contract $text{Diff}^0(S)$ in way that doesn't break any symmetries.

Now assume that $Sigma = S / Gamma$ is a good hyperbolic orbifold, where $Gamma$ is a finite group of diffeomorphisms of $S$. The identity component of the orbifold diffeomorphism group of $Sigma$ is then homeomorphic to
$$text{Diff}^{0}(S,Gamma) := langle f in text{Diff}^{0}(S) | gfg^{-1}=f text{for all} g in Gamma rangle subset text{Diff}^{0}(S)$$
The null-homotopy $phi_t$ preserves $text{Diff}^{0}(S,Gamma)$, so it is contractible.

(EDIT : I made a slight fix to the definition of the orbifold diffeomorphism above. It doesn't change the argument. Thanks to Tom Church for pointing it out to me!).

analytic number theory - Most squares in the first half-interval

There is a method of explaining this without using analytic methods. I will get to that at the end of this answer.

First, if $p equiv 1 bmod 4$ then this result is clear since -1 is a square mod $p$. So here exactly half the squares mod $p$ lie in the first half of $[1,p-1]$. The real problem is for $p equiv 3 bmod 4$, where analytic methods show there are more squares mod $p$ lying in the first half of that interval than in the second half because there is a formula for the class number of ${mathbf Q}(sqrt{-p})$ that is 1 or 1/3 times $S - N$, where $S$ is the number of squares mod $p$ in $[1,(p-1)/2]$ and $N$ is the number of nonsquares mod $p$ in $[1,(p-1)/2]$. Class numbers are positive integers, so $S > N$, which means in $[1,(p-1)/2]$ the squares mod $p$ outnumber nonsquares mod $p$. Since there are as many squares as nonsquares mod $p$ on $[1,p-1]$, the square vs. nonsquare bias on the first half of this interval forces there to be more squares mod $p$ on the first half than squares mod $p$ on the second half.

For a proof by analytic methods, see Borevich-Shafarevich's "Number Theory", Theorem 4 on p. 346. It is not true that no non-analytic derivations of this bias are known. For instance, Borevich and Shafarevich say on p. 347 that Venkov gave a non-analytic proof for some cases in 1928 (which came out in German in 1931: see Math Z. Vol. 33, 350--374). I should clarify this point since there is a bad typo in Borevich and Shafarevich here. What Venkov did was give a non-analytic proof of Dirichlet's class number formula for imaginary quadratic fields having discriminant $D notequiv 1 bmod 8$. Here the book unfortunately has $D equiv 1 bmod 8$. (It's clear from the book that something is wrong because shortly after saying Venkov treated $D equiv 1 bmod 8$ by non-analytic methods they say the case $D equiv 1 bmod 8$ still awaits a non-analytic proof.) The class number formula only gets an interpretation about squares or nonsquares for the fields ${mathbf Q}(sqrt{-p})$, but Venkov was working on non-analytic proofs of the class number formula for imaginary quadratic fields without having this restrictive case as the only one in mind. R. W. Davis (Crelle 286/287 (1976), 369--379) made simplifications to Venkov's argument.

What cases for ${mathbf Q}(sqrt{-p})$ are covered by Venkov? When $p equiv 3 bmod 4$, the discriminant of ${mathbf Q}(sqrt{-p})$ is $-p$. If $p equiv 3 bmod 8$ then $-p equiv 5 bmod 8$, while if $p equiv 7 bmod 8$ then $-p equiv 1 bmod 8$, so Venkov had non-analytically proved the formula when $p equiv 3 bmod 8$. The case $p equiv 7 bmod 8$ remained open.

In 1978 the whole problem was solved. Davis, in a second paper (Crelle 299/300 (1978), 247--255), handled some but not all cases of imaginary quadratic fields with discriminant $1 bmod 8$ (corresponding to $p equiv 7 bmod 8$ for the fields ${mathbf Q}(sqrt{-p})$) by non-analytic methods and in the same year H. L. S. Orde settled everything by non-analytic methods. See his paper "On Dirichlet's class number formula", J. London Math. Soc. 18 (1978), 409--420.

lo.logic - Weakest subsystems of second order arithmetic for mathematical logic

In fact, the incompleteness and completeness theorems can be proven in subsystems of second-order arithmetic weaker than RCA-0: incompleteness can be proven in EFA (first-order elementary arithmetic), which proves exponentiation total, but cannot prove iterated exponentiation to be total. In fact, systems much weaker than EFA can prove incompleteness: Solovay has shown that any sane system of arithmetic (more or less, any first-order equational logic where there are reasonable definitions of zero and successor) strong enough to prove that multiplication is total can prove incompleteness. But EFA is interesting because "Exponential Function Arithmetic is the weakest system in use for which the coding of finite objects by nonnegative integers is worry free" (Friedman 2010): EFA is a reasonable first-order base upon which to build reverse mathematics.

EFA can be usefully extended to the language of second-order arithmetic using the comprehension scheme ∀x (φ(x) ↔ ψ(x)) → ∃Y ∀x (x ∈ Y ↔ φ(x)), where where φ and ψ are Σ-0-1 and Π-0-1 predicates which may have free second-order variables (this definition is from Avigad 2003). This language, call it ERCA-0, is then an analog of RCA-0-like that is a conservative extension of EFA. Avigad shows how this base system can be considered as a weaker base theory for reverse mathematics, with a series of weaker analogs to other fixtures of the reverse mathematics landscape: in particular, EWKL-0, that analog of WKL-0, can prove the completeness theorem.

To summarise: ERCA-0 is weaker than RCA-0 and can prove the incompleteness theorems; EWKL-0 is weaker than WKL-0 and can prove the completeness theorem. We can hope for weaker systems still, but Friedman's remark suggests that such systems will be more complex, and less suitable for reverse mathematics: there's a sense in which we might expect this to be around the best "weak" base system.

References

1. Avigad, 2003, Number theory and elementary arithmetic. NB. Avigad calls elementary arithmetic, EA.


2. Friedman, 2010, Concrete Incompleteness from EFA through Large Cardinals.

at.algebraic topology - Exotic spheres and stable homotopy in all large dimensions?

As Ryan Budney indicated, Mark Behrens gave a talk about joint work with Mike Hill, Mike Hopkins, and Mark Mahowald at the Milnor conference a few days ago. Here's a link to the video.

The "reader's digest" version of this is that, by using periodic families of elements in the stable homotopy groups of spheres, they've established a large number of congruences where exotic spheres are always forced to exist, but it's not yet exhaustive. In addition, they've done enough low-dimensional computations to know that in dimensions less than or equal to (at least) 63, there are exotic spheres in all dimensions except 1, 2, 3, 4, 5, 6, 12, and 61. The first of these were known from work of Kervaire-Milnor in 1963 (as part of their enumeration of the number of exotic spheres that's indicated by the Wikipedia entry), but the nonexistence of exotic spheres in dimension 61 is a new result.

soft question - What should be offered in undergraduate mathematics that's currently not (or isn't usually)?

Computer Science. I know programming has been said already, but computer science isn't programming. (There's the famous Dijkstra quote: “Computer science is no more about computers than astronomy is about telescopes.”)

There is a vast and beautiful field of computer science out there that draws on algebra, category theory, topology, order theory, logic and other areas and that doesn't get much of a mention in mathematics courses (AFAIK). Example subjects are areas like F-(co)algebras for (co)recursive data structures, the Curry-Howard isomorphism and intuitionistic logic and computable analysis.

When I did programming as part of my mathematics course I gave it up. It was merely error analysis for a bunch of numerical methods. I had no idea that concepts I learnt in algebraic topology could help me reason about lists and trees (eg. functors), or that transfinite ordinals aren't just playthings for set theorists and can be immediately applied to termination proofs for programs, or that if my proof didn't use the law of the excluded middle then maybe I could automatically extract a program from it, or that there's a deep connection between computability and continuity, and so on.

ag.algebraic geometry - A necessary and sufficient condition for a curve to have an $A_k$ singularity.

Although the above answer involving the local algebra and the Milnor number is correct, it is often very hard to apply in real situations. Especially if you have a general function with arbitrary coefficients. You can perform a rather messy iterative process to check for an $A_k.$ In general the condition is far too ugly to want to, or be able to, write down.

You have a curve in the plane given by $f(x,y) = 0.$ The Taylor series, with respect to $x$ and $y$ is what you're really interested in. Let's assume we are only interested in the origin. If the linear terms vanish then you know that you have a singular point (a critical point of $f$). In that case you consider the quadratic part. If the quadratic part is non-degenerate, i.e. not a perfect square, then you have Morse singularity. These are $mathscr{A}$-equivalent to $x^2 pm y^2,$ and give the so-called $A_1^{pm}$-singularity types.

(Notice that $mathscr{A}$-equivalence has no relevance to the $A$ in $A_k.$ $mathscr{A}$-equivalence is also called $mathscr{RL}$-equivalence. You allow diffeomorphic changes of coordinate in the source and target (right and left sides of the commutativity diagram.)

If $f$ has a zero linear part and a degenerate quadratic part, we complete the square on the quadratic part. Then take a change of coordinates that turns the quadratic part into $tilde{x}^2$. The condition for exactly an $A_2$ is that $tilde{x}$ does not divide the new, post-coordinate change, cubic term. If not then $f$ is $mathscr{A}$-equivalent to $tilde{x}^2 + tilde{y}^3.$ (There is no $pm$ because $(x,y) mapsto (x,-y)$ changes the sign of the cubic term.

If $tilde{x}$ does divide the new cubic term, then you can complete the square on the three jet, i.e. on the quadratic and cubic terms as a whole. You take a change of coordinates so that this completed square become, say $X^2$. The condition for an $A_3^{pm}$ is that $X$ does not divide the new, post-coordinate change, quadric terms. If not then $f$ is $mathscr{A}$-equivalent to $X^2 pm Y^4.$

In general you follow the same pattern. Complete the square, take a formal power series change of coordinates so that the perfect square becomes $x_{new}^2.$ Check if $x_{new}$ divides the next set of fixed order terms. If not then stop. If $x_{new}$ didn't divide the order $n$-terms then $f$ is $mathscr{A}$-equivalent to $x_{new}^2 pm y_{new}^n.$

You just repeat the pattern: Is the quadratic part degenerate? If so then change coordinates (by a formal power series of low, but sufficient order) so that the degenerate part becomes $x_{new}^2 + O(3).$ Check if $x_{new}$ divides the cubic terms. If not then you have $x^2 + y^3.$ If so then complete the square on the new 3-jet and change coordinates so that you have $x_{new}^2 + O(4)$. Does $x_{new}^2$ divide the quartic terms? If not then you have $x^2 pm y^4.$ If so then complete the square on the new 4-jet and change coordinates. Just keep completing the square, checking divisibility, changing coordinates.

The conditions on the coefficients soon spiral out of control. To check an $A_6$ you'll need a computer program. For a general polynomial it's impossible without a computer. (Except for very special cases!) I wrote a program in Maple to calculate the conditions up to $A_k$ once, but the output was so messy then I gave up. Having said that, for an explicit polynomial it's child's play.

soft question - What should be offered in undergraduate mathematics that's currently not (or isn't usually)?

Personally, I think the answer to this question is largely going to depend on one's particularly interests (whether they lie in algebra, analysis, topology, or whatever). This can be seen from many of the previous posts.

That being said, I do think that more number theory would be a great addition to the undergraduate curriculum. Many students take an introductory number theory course (or skip it because they learned it all in high school) and then don't do any more. There are lots of great areas of number theory which don't require too much background. P-adics would be great (Gouvea even laments in his book that p-adics aren't taught earlier - so maybe such a course should use his book). One could teach a basic semester of algebraic number theory, or a course in elliptic curves (following Silverman and Tate, for example). Both of these require no more than a basic course in undergraduate algebra. You can probably find these courses at many top universities, but they usually aren't emphasized as much to undergraduates. The reason why I think that these would be good is because number theory is a particularly beautiful area of math, and by getting glimpses of modern number theory early on, students get to see how beautiful is the math that's ahead of them.
(Another possibility is to have a course on Ireland and Rosen's book A Classical Introduction to Modern Number Theory. Princeton had a junior seminar on this book, for example.)

I also think Riemann surfaces are a very beautiful topic which should be taught early on and aren't too complicated in their most basic form. For, you get to see the deep geometrical theory lying behind the $e^{2 i pi}=1$ and the ambiguity of complex square roots which you learned about when you were younger. It shows the student that there can be very deep ideas lying behind a simple observation, and it shows the beauty and deep understanding that modern mathematics can lead you to.

soft question - Reading materials for mathematical logic

Joe Mileti wrote a really nice set of course notes on mathematical logic (approx 20 weeks of lectures). It's a draft for a book titled, I think, "Mathematical Logic for Mathematicians." The course notes are beautifully written (and beautifully delivered, if you've had the chance to see him lecture). He's a very nice guy, and I would suggest contacting him about it.

My memory is a bit hazy about the topics he covered, but we discussed propositional and first order logic, nonstandard analysis, and axiomatic set theory. I also remember that some highlights included connections to graph theory and algebra (I guess this sort of touches upon his research themes).

st.statistics - How to present overlap of related sets

One approach is to represent your data as a graph, and use a network diagram tool to draw it. Variant 1: nodes are websites, weighted edges represent number of common links. Variant 2: a bipartite graph with nodes being either web sites or links, and unweighted edges indicating "web site A contains link B." The magic google phrase to find examples related to your example is "citation visualization".

The problem with this technique is that big graphs sometimes turn into hairballs in a graph layout tool, so you may need to prune or filter your data set for it to be intelligible.

There are other techniques: you could draw a grid where rows correspond to web pages, and columns to links they contain, and fill in cells (X,Y) where link X appears in web site Y. If you reorder the rows and columns to put related pages near each other and related links near each other this can be an effective analytic tool, but it might not be right for non-technical readers.

A lot of this depends on the details of your data. If you have any kind of metadata (a categorization of web pages or links) that could suggest other approaches--feel free to add details in your question. About the only thing you can say for sure is a big Venn diagram is going to be a mess!

sp.spectral theory - An experiment on random matrices

A bit unsure if my use/mention of proprietary software might be inappropriate or even frowned upon here. If this is the case, or if this kind of experimental question is not welcome, please let me know and I'll remove it quickly.

I was experimenting on the distribution of eigenvalues of random matrices via the following Mathematica code

dim = 301;
decomplex = {z_Complex -> {Re[z], Im[z]}, A_Real -> {A, 0}}; b =
Eigenvalues[
SparseArray[{i_, i_} -> 1, {dim, dim}] +
Table[RandomReal[{-.9, 1.}], {i, 1, dim}, {j, 1, dim}]] /. decomplex;
ListPlot[b, PlotStyle -> PointSize[0.015], AspectRatio -> Automatic]

This simply draws (or should draw) a picture of the complex eigenvalues of a 301 x 301 matrix, with entries uniformly distributed in the real interval [-0.9, 1]. If you try the code you will notice a disk of random eigenvalues, which is expected, plus a single positive eigenvalue at some distance of the disk. Decreasing the lower bound on the entries to -1 makes this phenomenon disappear, while increasing the lower bound makes it more evident.

Question: is this an artifact, a real phenomenon, or maybe even a well known and simple to explain phenomenon?

set theory - "Internal" versus "external" definitions of functions: equivalent foundations for mathematics?

This is a generalization of the question given at Definition of Function.

I think it fairly clear that the Bourbaki and the ordered pair definition of functions are equivalent. A deeper question is whether or not the conception of functions as arrows-as in category theory without specification-is equivalent.

Let me be a little more specific what I mean. Currently,there are roughly 2 kinds of foundations proposed for mathematics: "internal" and "external".

An internal foundation for mathematics is one based on a primitive building block from which the functions are ultimately constructed explicitly from the building blocks. Examples are,of course,set theories-particularly Zermelo-Frankel set theory-where sets are defined as abstract collections that satisfy a finite number of axioms (union,extensionality,etc).

We then define ordered pairs explicitly from sets (to be precise,the set of ordered pairs ={{x},{x,y}} of elements is a subset of the power set of the power set of the union of sets where the elements {x} and {x,y} are taken). A function is then defined as a subset of this set where no 2 different ordered pairs have the same first member.

An extensionalist foundation-such as Paul Taylor and to a lesser extent, William Lawvere,have proposed-takes the FUNCTIONS to be the primitive elements as arrows that are specified in some manner. There are then 2 ways sets can be obtained from functions:
1) the sets can simply be defined as the domain and ranges of maps without specifying thier composition explicitly. I think this is what Taylor does,more or less-but I had a lot of difficulty understanding exactly what he's proposing since most of it is couched in heavy logical language.
2) A primitive function-called the membership function-is proposed which assigns single elements to collections and they are built up as the ranges of collections of membership maps. The rest of set-theoretic constructions are built up in a similar manner using specialized functions. This is what William Lawvere and Robert Rosebraugh do in thier fascinating book,Sets For Mathematics.

The extensionalist approach,of course,is favored by those who want to replace set theoretic models with categorical ones for mathematics. In some respects,it is simpler-arrows are easier to deal with then axiomatic sets. It also allows us to sidestep the sticky cardinality issues that come up in category theory,when dealing with collections that are too large to be sets,that started all this debating in the first place. Unfortunately,what makes set theory difficult is also what gives it it's tremendous power as a foundation for mathematics: It allows us to develop all objects in mathematics explicitly and unambiguously.There's absolutely no doubt 2 sets are equal in axiomatic set theory since in principle,you can see that they indeed have the same elements.

Personally,I favor a foundation that allows us to do both.Thinking we need to jettison one for the other is tantamount to saying we can't accept quantum theory without rejecting general relativity.

My question: Can these 2 conceptions of function-internal and external-be shown to be logically equivalent?Of course,the question's probably not that simple-you'd probably need to specify which "theory" you're talking about-for example,Taylor or Lawvere/Rosebaugh's.

So would they be equivelent in:

a) Paul Taylor's vrs. classical ZFC models?
b) Lawvere/Rosebaugh's vrs. classical ZFC models?

It seems to me the model proposed in Lawvere/Rosebaugh should be equivalent since the membership function more or less is the same as the membership relation in axiomatic set theory. In Taylor's though-it's not so clear.

rt.representation theory - Are complex semisimple Lie groups matrix groups?

Actually, my question is a bit more specific: Does every complex semisimple Lie group $G$ admit a faithful finite-dimensional holomorphic representation? [As remarked by Brian Conrad, this is enough to prove that $G$ is a matrix group (at least when it's connected) because $G$ can be made into an (affine) algebraic group over $mathbb{C}$ in unique way which is compatible with its complex Lie group structure, and under which every finite-dimensional holomorphic representation is algebraic. Furthermore, one can show that the image of a faithful representation would then be closed.]

Of course the analogous question for real semisimple Lie groups has a negative answer -- "holomorphic" having been replaced by "continuous", "smooth" or "real analytic" -- with the canonical counterexample being a nontrivial cover of $mathrm{SL}(2,mathbb{R})$.

For a connected complex semisimple Lie group $G$ I believe the answer is "YES." The idea is to piggy back off a 'sufficiently large' representation of a compact real form $G_mathbb{R}$; here by "compact real form" I'm referring specifically to the definition which allows us to uniquely extend continuous finite-dimensional representations of $G_mathbb{R}$ to holomorphic representations of $G$. I know (e.g. from the proof of Theorem 27.1 in D. Bump's Lie Groups) that such a definition is possible if we require $G$ to be connected (and I'd like to know if it's possible in general).

The details of the argument for connected $G$ are as follows. Consider the adjoint representation $mathrm{Ad} colon G to mathrm{GL}(mathfrak{g})$. Since $G$ is semisimple, $mathrm{Ad}$ has discrete kernel $K$. Consider next the restriction of $mathrm{Ad}$ to $G_mathbb{R}$. Observe that the kernel of this map is also $K$, for otherwise its holomorphic extension is different from the adjoint representation of $G$. Thus $K$ is finite, being a discrete, closed subset of a compact space. So by the Peter-Weyl theorem, we can find a representation $pi_0$ of $G_mathbb{R}$ that is nonzero on $K$. Extend $pi_0$ to a holomorphic representation $pi$ of $G$ and put $rho = pi oplus mathrm{Ad}$. Notice that $rho$ is a holomorphic representation of $G$ with kernel $kerpi cap K = 0$, which is what we were after.

What can we say if $G$ is disconnected?

conformal geometry - Intuition behind moduli space of curves

(EDIT 1: Replaced hand-waving argument in third paragraph with a hopefully less incorrect version)

(EDIT 2: Added final paragraph about obtaining all conformal deformations for surfaces other than sphere.)

I think it is possible to see the infinitesimal rigidity of the sphere, even if it does involve a PDE as Dmitri says. I think you can also try and see if for other embedded surfaces, all infinitesimal deformations of conformal structure are accounted for by deformations of the embedding in a similar way.

For the case of S², what you want is to do is take a normal vector field V (i.e. infinitesimal change of embedding) and produce a tangent vector field X such that flowing along X gives the same infinitesimal change in conformal structure as flowing along V. This should amount to solving a linear PDE, so as Dmitri says a PDE is definitely involved, but probably not as hard as proving the existence of isothermal coordinates (which from memory is non-linear). For the standard embedding of S² there can't be too many choices for this linear differential operator given that it has to respect the SO(3)-symmetry.

I guess we're looking for a first-order equivariant linear operator from normal vector fields to tangent vector fields. If we identify normal fields with functions then two possible candidates are to take X=grad V or X to be the Hamiltonian flow generated by V. I can't think of any others and probably it's possible to prove these are the only such ones. (Assuming it's elliptic, the symbol of the operator must be an SO(3)-equivariant isomorphism from T^*S² to TS² and there can't be too many choices! Using the metric leads to grad and using the area form leads to the Hamiltonian flow.) Then you just have to decide which one to use.

For the case of a general embedded surface $M$, you can ask "is it possible to obtain all deformations of conformal structure by deforming the embedding into R³?" To answer this we can again think of a normal vector field as a function V on the surface. There is a second-order linear differential operator
$$
Dcolon C^infty(M) to Omega^{0,1}(T)
$$
which sends a normal vector field to the corresponding infinitesimal change of conformal structure. This operator will factor through the hessian with a homomorphism from $T^* otimes T^*$ to $T^{*0,1}otimes T^{1,0}$. The operator $D$ will not be onto, but what we want to know is whether every cohomology class in $H^{0,1}(T)$ has a representative in the image of $D$. At least, this is how I would try and approach the question; I'm sure there are other methods.

ac.commutative algebra - Does the free resolution of the cokernel of a generic matrix remain exact on a Zariski open set?

"Random" modules of the same size over a polynomial ring seem to always have the same Betti table. By a "random" module I mean the cokernel of a matrix whose entries are random forms of a fixed degree.

For example if we take the quotient of the polynomial ring in three variables by five random cubics:
$S = mathbb{Q}[x1,x2,x3]$
$M$ = coker random( S^1, S^{5:-3} )
then Macaulay2 "always" (e.g. 1000 out of 1000 times) gives the following Betti table

total: 1 5 9 5
0: 1 . . .
1: . . . .
2: . 5 . .
3: . . 9 5

It seems that the behavior can be explained by the fact that we can resolve the cokernel of a generic matrix of the given form and this resolution remains exact when specializing to any point in a Zariski open subset of some affine space. My question is whether anyone knows a slick proof of this fact.

To elaborate: we can adjoin a new variable to our original ring for each coefficient appearing in each entry of the matrix. So in the above example we would adjoin 10*5 = 50 new variables to $S$, say $y1..y50$. Call the new ring $T$. Consider the $1x3$ matrix $N$ over $T$ whose entries are cubic in the $x_i$ and linear in the $y_i$. Resolve the cokernel of $N$ over $T$ to get a complex $F$. We can then substitute any point in $mathbb{Q}^{50}$ into the maps of $F$ to get a complex over the original ring $S$. The claim is that this complex is exact on a Zariski open set of the affine space $mathbb{Q}^{50}$.

It seems like this must be well known but I'm having trouble finding references.

Positive vector bundles

In the case of a line bundle over M, positivity of such a bundle (one whose curvature form which is Kahler) gives rise to an embeddings of M into the projective space.

Now I have in mind (more or less) the following definition. Let E be a holomorphic vector bundle over M with a hermitian metric. Moreover let D be a connection on E. Then we can define D^2 so that the curvature matrix of 2-forms. Such a curvature matrix (tensor) gives rise to a Hermitian form O_E on the bundle TMotimes E. We can say that E is positive if such a hermitian form O_E is positive on all the tensors in TMotimes E.

Then, What is the geometric meaning (if any) of the positivity in a vector bundle? rank>1.

I think, there are several definitions that generalize the concept of positive line bundle. Can you say which is the more standard one and why?

I edited the previous question since it was ambiguous.

transcendence - Showing e is transcendental using its continued fraction expansion

In his article Transcendental continued fractions, Journal of Number Theory 13, November 1981, 456-462, Gideon Nettler shows that two numbers given by continued fractions
$A = [a_0,a_1,a_2,...]$ and $B = [b_0, b_1, b_2, ...]$ have the property that $A$, $B$,
$A pm B$, $A/B$ and $AB$ are irrational if $frac12 a_n > b_n > a_{n-1}^{5n}$ for sufficiently large $n$, and transcendental if $a_n > b_n > a_{n−1}^{(n−1)^2}$ for sufficiently large $n$. The growth of the $a_i$ in the continued fraction expansion of $e$ is so small that present methods seem useless for proving the transcendence of $e$ in this way.

Edit. Similarly, Alan Baker proved in Continued fractions of transcendental numbers (Mathematika 9 (1962), 1-8) that if $q_n$ denotes the denominator of the $n$-th convergent of a continued fraction $A$, and if
$$ lim sup frac{(log log q_n)(log n)^{1/2}}{n} = infty, $$
then $A$ is transcendental.

Edit 2 I guess that the answer to your question should be a firm "yes" after all.
In

• Über einige Anwendungen diophantischer Approximationen,
  Abh. Preuss. Akad. Wiss. 1929; Gesammelte Abhandlungen, vol I, p. 209-241

Siegel proved that all continued fractions
$$ frac{1}{a_1 + cfrac{1}{a_2 + cfrac{1}{a_3 + ldots}}} $$
in which the $a_i$ form a nonconstant arithmetic sequence are transcendental.
Applying this to the continued fraction expansion of $frac{e-1}{e+1}$ gives
the transcendence of $e$.

Siegel's proof uses, predictably, analytic machinery (solutions of Bessel and
Riccati differential equations) going far beyond Liouville's theorem.

st.statistics - Estimating the number of clusters

This is an age-old question, which actually does not have (I think even cannot have) a definite answer, because first you need to define what you mean by a cluster and so on. A famous saying in this regard is that "cluster is in the eye of a beholder". It is easy to construct examples where somebody could see one cluster, but somebody else more than one.

This being said, the MDL (minimum description length) principle would lead you
to devise (IMHO) a clustering cost function in a most principled way, which by
optimizing you could the find the cluster assignments and number of clusters
simultaneously. For multinomial data you can see following:
P.Kontkanen, P.Myllymäki, W.Buntine, J.Rissanen, H.Tirri, An MDL Framework
for Data Clustering. In Advances in Minimum Description Length: Theory and
Applications, edited by P. Grünwald, I.J. Myung and M. Pitt. The MIT Press,
2005.

The intuitively-appealing idea behind MDL clustering is that by clustering you
create a model of the data. So the assumption is that a very good model is one
that lets you compress the data well.

Anyway MDL might not be easy to apply, if you are looking for a practical way to detect the number of clusters. BIC (Bayesian information criteria) and the F-ratio have
proven to work OK in practice.

co.combinatorics - Tiling A Rectangle With A Hint of Magic

Here's a a famous problem:

If a rectangle $R$ is tiled by rectangles $T_i$ each of which has at least one integer sidelength, then the tiled rectangle $R$ has at least one integer side length.

$mbox{}$

There are a number of proofs of this result (14 proofs in this particular paper). One would think this problem is a tedious exercise in combinatorics, but the broad range of solutions which do not rely on combinatorial methods makes me wonder what deeper principles are at work here. In particular, my question is about the proof using double integrals which I sketch out below:

Suppose the given rectangle $R$ has dimensions $atimes b$ and without loss of generality suppose $R$ has a corner at coordinate $(0,0)$. Notice that $int_m^nsin(2pi x)dx=0$ iff $mpm n$ is an integer. Thus, for any tile rectangle $T_i$, we have that:

$intint_{T_i}sin(2pi x)sin(2pi y)dA=0$

If we sum over all tile rectangles $T_i$, we get that the area integral over $R$ is also zero:

$intint_{R}sin(2pi x)sin(2pi y)dA=sum_iintint_{T_i}sin(2pi x)sin(2pi y)dA=0$

Since the cornor of the rectangle is at $(0,0)$, it follows that either $a$ or $b$ must be an integer.

My question is as follows: where exactly does such a proof come from and how does it generalize to other questions concerning tiling? There is obviously a deeper principle at work here. What exactly is that principle?

One can pick other functions to integrate over such as $x-[x]-1/2$ and the result will follow. It just seems like black magic that this works. It's as if the functions you are integrating over tease out the geometric properties of your shape in an effortless way.

EDIT: It's likely that one doesn't necessary need integrals to think in the same flavor as this solution. You're essentially looking at both side lengths in parallel with linear test functions on individual tiles. However, this doesn't really explain the deeper principles here, in particular how one could generalize this method to more difficult questions by choosing appropriate "test functions."

gn.general topology - Is there good evidence that topological spaces are the correct way to study the general theory of continuity?

Geometry and "theory of distance" are not the only motivation for general topology. Another motivation comes from information processing and computation.

Briefly, let us consider the notion of "observable subset" where by "observable" we mean "can be confirmed by a (finite-time) computation". More precisely, a subset $S subseteq X$ of a datatype $X$ is computationally observable if there exists a program $p$ such that

for all $x in X$, $p(x)$ terminates if, and only if $x in S$.

Note the assymetry between an observable subset and its complement. You can think of the fact that $p(x)$ terminates as giving you half a bit of information.

We make the following basic observations:

1. The empty subset is observable by a program which never terminates.


2. The whole set is observable by a program which always terminates.


3. If $S$ and $T$ are observable by $p$ and $q$, respectively, then $S cap T$ is observable by the program $p; q$ (execute $p$, wait for it to finish then execute $q$).


4. If $(S_n)$ is a sequence of subsets observable by a (computable) sequence $p_n$ of programs, then $bigcup_n S_n$ is observable by the program which runs $p_0, p_1, p_2, ldots$ in parallel by dovetailing and finishes as soon as one of them does.

If we replace "observable" by "open" and generalize to arbitrary unions instead of just countable computable ones, we get the usual definition of topology.

You should convince yourself that it is unreasonable to expect that a countable intersection of observable subsets is observable: if it were, we could solve the Halting problem.

The topological spaces which arise in theoretical computer science from the point of view that "open = computationally observable" are typically not Hausdorff, let alone metrizable. They are however very nice spaces with lots of good properties.

You asked about continuity. Under the view I described we can show that computable maps are continuous in a very natural way: if $f : X to Y$ is computable and $S subseteq Y$ is observable by $p$ then $f^{-1}(S)$ is observable by $q(x) = p(f(x))$.

To summarize

"Observable sets are open, computable maps are continuous."

So yes, the usual definition of continuous maps as one whose inverse image preserves open sets is right. The definition of topology, however, could be discussed a bit further. There is something fishy about going from computable countable unions to general ones just like that.