mathematical writing - What is the best graph editor to use in your articles?

I already had about 30 pages of graphs typeset with xymatrix for my thesis before discovering tikz; but was so impressed by it that I was happy to rewrite them all. As well as (imho) looking better, it gave me cross-platform compatibility - xypic seems to need pstricks, so on the mac with TeXshop (which uses pdflatex, I assume) the old graphs couldn't even be rendered.

Its ability to construct graphs iteratively can also be a massive timesaver- for instance, I wanted a bunch of otherwise identical rectangles at various positions, so with tikz could just loop over a list of their first coordinate rather than having to tediously cut,paste and modify an appropriate number of copies of the command for a rectangle. Particularly handy when I then decided they all needed to be slightly wider!

There's a gallery of tikz examples here, to give you some idea of what it's capable of (and with the relevant source code- I did find the manual a bit hard to understand and learnt mostly by examples or trial and error).

The vector graphics package inkscape (which I used to use for drawing more complicated graphs for inclusion as eps images) also apparently has a plugin to export as tikz, although I haven't tried that out.

tag removed - What is the status of the Gauss Circle Problem?

For $r > 0$, let $L(r) = # { (x,y) in mathbb{Z}^2 | x^2 + y^2 leq r^2}$ be the number of lattice points lying on or inside the standard circle of radius $r$. It is easy to see that $L(r) sim pi r^2$ as $r rightarrow infty$. The Gauss circle problem is to give the best possible error bounds: put

$E(r) = |L(r) - pi r^2|$.

Gauss himself gave the elementary bound $E(r) = O(r)$. In 1916 Hardy and Landau showed that it is not the case that $E(r) = O(r^{frac{1}{2}})$. It is now believed that this is "almost" true: i.e.:

Gauss Circle Conjecture: For every $epsilon > 0$, $E(r) = O_{epsilon}(r^{frac{1}{2}+epsilon})$.

So far as I know the best published result is a 1993 theorem of Huxley, who shows one may take $epsilon > frac{19}{146}$.

(For a little more information, see http://math.uga.edu/~pete/NT2009gausscircle.pdf)

In early 2007 I was teaching an elementary number theory class when I noticed that Cappell and Shaneson had uploaded a preprint to the arxiv claiming to prove the Gauss Circle Conjecture:

http://arxiv.org/abs/math/0702613

Two more versions were uploaded, the last in July of 2007.

It is now a little more than three years later, and so far as I know the paper has neither been published nor retracted. This seems like a strange state of affairs for an important classical problem. Can someone say what the status of the Gauss Circle Problem is today? Is the argument of Cappell and Shaneson correct? Or is there a known flaw?

abstract algebra - Canonical examples of algebraic structures

I often think of "universal examples". This is useful because then you can actually prove something in the general case - at least theoretically - just by looking at these examples.

Semigroup: $mathbb{N}$ with $+$ or $*$

Group: Automorphism groups of sets ($Sym(n)$) or of polyhedra (e.g. $D(n)$).

Virtual cyclic group: Semidirect products $mathbb{Z} rtimes mathbb{Z}/n$.

Abelian group: $mathbb{Z}^n$

Non-finitely generated group: $mathbb{Q}$

Divisible group: $mathbb{Q}/mathbb{Z}$

Ring: $mathbb{Z}[x_1,...,x_n]$

Graded ring: Singular cohomology of a space.

Ring without unit: $2mathbb{Z}$, $C_0(mathbb{N})$

Non-commutative ring: Endomorphisms of abelian groups, such as $M_n(mathbb{Z})$.

Non-noetherian ring: $mathbb{Z}[x_1,x_2,...]$.

Ring with zero divisors: $mathbb{Z}[x]/x^2$

Principal ideal domain which is not euclidean: $mathbb{Z}[(1+sqrt{-19})/2]$

Finite ring: $mathbb{F}_2^n$.

Local ring: Fields, and the $p$-adics $mathbb{Z}_p$

Non-smooth $k$-algebra: $k[x,y]/(x^2-y^3)$

Field: $mathbb{Q}, mathbb{F}_p$

Field extension: $mathbb{Q}(i) / mathbb{Q}, k(t)/k$

Module: sections of a vector bundle. Free <=> trivial. Point <=> vector space.

Flat / non-flat module: $mathbb{Q}$ and $mathbb{Z}/2$ over $mathbb{Z}$

Locally free, but not free module: $(2,1+sqrt{-5})$ over $mathbb{Z}[sqrt{-5}]$

... perhaps I should stop here, this is an infinite list.

dg.differential geometry - Singular, holonomy-free connections on Riemannian surfaces?

Consider principal connections on the frame bundle of a compact, connected, smooth, orientable Riemannian surface embedded in $mathbb{R}^3$. On a disk $D$, it is apparent that you can construct a connection $omega$ with zero holonomy everywhere: for instance, map $D$ to the plane and use Euclidean translation to induce parallel transport. Further, suppose that $D$ is actually an embedding of $S^2$ with a single point $p$ removed. If we now compactify $D$ to get $S^2$ again, then we have a connection $tilde{omega}$ on the sphere which is well-defined for any loop that does not contain $p$, and exhibits zero holonomy around any such loop. In a similar way, we can construct a connection with a single "singular" point on a surface of any genus by removing a set of loops that generate the fundamental group rather than just a single point (though we can no longer rely on Euclidean translation to provide the connection). And more generally, we can imagine connections with zero holonomy except at a number of singularities (map a punctured disk to the plane, say).

Is there a more formal description of this type of construction, and does it have a name? Any pointers to literature?

ag.algebraic geometry - Is the Grothendieck ring of varieties reduced?

Qing Liu's example probably works, only we don't know if an abelian variety in
positive characteric is determined by its class in
$K_0(mathrm{Var}_k)$. However, we do know that in characteristic zero (this is
what Bjorn Poonen uses in his examples) and the non-cancellation is a purely
arithmetic phenomenon and hence can be realised in characteristic zero.

Hence, we let $mathcal A$ be a maximal order in a definite (i.e., $mathcal
Aotimesmathbb R$ is non-split) quaternion algebra over $mathbb Q$. There is
an abelian variety $A$ over some field $k$ of characteristic zero with $mathcal
A=mathrm{End}(A)$ (Bjorn works hard to get his example defined over $mathbb
Q$, here I make no such claim). For any (right) f.g. projective (i.e., torsion
free) $mathcal A$-module $M$ we may define an abelian variety
$Mbigotimes_{mathcal A}A$ characterised by $mathrm{Hom}(Mbigotimes_{mathcal
A}A,B)=mathrm{Hom}_{mathcal A}(M,mathrm{Hom}(A,B))$ for all abelian
varieties (concretely it is constructed by realising $M$ is the kernel of an
idempotent of some $mathcal A^n$ and then taking the kernel of the same
idempotent acting on $A^n$). In any case we see that $M$ and $N$ are isomorphic
precisely when $Mbigotimes_{mathcal A}A$ is isomorphic to
$Nbigotimes_{mathcal A}A$.

Now (all the arithmetic results used below can be found in for instance Irving
Reiner: Maximal orders, Academic Press, London-New York), the class group of
$mathcal A$ is equal to the ray class group of $mathbb Q$ with respect to the
infinite prime, i.e., the group of fractional ideals of $mathbb Q$ modulo
ideals with a strictly positive generators. As that is all ideals we find that
the class group is trivial. Furthermore, we have the Eichler stability theorem
which says that projective modules of rank $geq2$ are determined by their rank and
image in the class group and hence are determined by their rank (the rank
condition comes in in that $mathrm{M}_k(mathcal A)$ is a central simple
algebra which is indefinite at the infinite prime). In particular if $M_1$ and
$M_2$ are two rank $1$ modules over $mathcal A$ and $A_1$ and $A_2$ are the
corresponding abelian varieties we get that $A_1bigoplus A_2cong Abigoplus A$
as the left (resp. right) hand side is associated to $M_1bigoplus M_2$ (resp.
$mathcal A^2$). Therefore, to get an example it is enough to give an example of
an $mathcal A$ for which there exist $M_1notcong M_2$. The number (or more
easily the mass) of isomorphism classes of ideals can be computed using mass
formulas and tends to infinity with the discriminant of $mathcal A$. It is
interesting to note that when the discriminant is a prime $p$ we can go
backwards using supersingular elliptic curves: The mass is equal to the mass of
supersingular elliptic curves in characteristic $p$ and the latter mass can be
computed geometrically to be equal to $(p-1)/24$.

ag.algebraic geometry - How to compute the ring of invariants of SO_3(k) acting on a polynomial ring

This is addressed by the classical invariant theory, but the answer is more complicated than for general linear or orthogonal groups (in particular, not all minimal generators are quadratic). Let $k$ be a field of characteristic 0. The group $G=SO_m$ acts on $mtimes n$ matrices by the left multiplication and this induces a $G$-action on $A=k[X_{ij}].$ Let us view the variables as the entries of the $mtimes n$ generic matrix over $k.$ Then the algebra of invariants $A^G$ is generated by:

1 Scalar products of the columns of the matrix $X.$

2 Order $m$ minors of the matrix $X.$

This is the First Fundamental Theorem (FFT) of classical invariant theory for $SO_m.$ In fact, the elements of the first type generate $O_m$-invariants and the elements of the second type generate $SL_m$-invariants ($SO_m=O_mcap SL_m$).

Moreover, all relations between these generators are also known (the Second Fundamental Theorem, SFT) and there is a good description of a standard monomial basis of $A^G.$ If I am not mistaken, the last part is due to Laskshmibai and coauthors. A comprehensive modern reference is

Laskshmibai and Raghavan, Standard monomial theory. Invariant theoretic approach. Encyclopaedia of Mathematical Sciences, vol 137 (Invariant Theory and Algebraic Transformation Groups VIII), Springer.

Category theory and model theory as "natural" counterparts

I'm not an expert in model theory anyway I'll try to answer your questions.

From what I get your problem come from the fact that both model theory and category theory are related with the study of stuctured objects and morphisms between them.
There are categories which aren't at all build up from structured objects and morphisms stucture-preserving, for instance monoids, groups and posets are categories too, and seeing this objects as categories is useful for some applications.
Model theory instead deal exactly with models of a theory which are exactly stuctured objects and the stucture preserving morphisms, so it deals with categories of models of given theories (to be exact if I'm not mistaking, model theory also deal with theories' morphisms and derived morphisms between theories' models, but also this can be seen in terms objects and morphism).

After this not too short introduction let's try to answer your questions:

Answer #1: I suppose that the textbook you are referring to were written in time when the deep connection between model theory and category theory weren't well known. Try to take a look to book about categorical logic.

Answer #2: As I said above categories can be viewed as models of a particular (first order) theory, by the way this is not really useful because of the size issues I mentioned above. By the way category theory via notions of categories (with enough structure), functors (preserving the said structure) and natural transformations offer a new way to define the notion of theory, model and model transformation. In this way it become possible to study the notion of model of a theory in any category, where classical model theory become simply the study the theory of models in $mathbf{Set}$, the category of sets and functions.

Answer #3:I don't know if there's any satisfactory answer to this question, mostly because as I said category theory and model theory are really different theories which aims to study different objects (the first one deal with theories and models, the second with categories, functors and natural transformations, but also other objects if we consider higher category theory as category theory).
Maybe it could be more interesting studying the relation between classical (i.e. set theoretic) model theory and categorical model theory, but I don't know enough to talk about this.

Answer #4:If by level of abstraction you mean if one can be consider as a special case of the other I guess the answer is yes and no: you can build a first order theory of categories, functors natural transformation but from another point of view model theory can be completely rephrased in categorical term. Seeing from this point of view the question seems to me very similar to the chicken or the egg causality dilemma, and I don't think it's really useful this point of view, I would never consider group theory just as the study of the models of the theory of groups. :)

I hope this helps.

at.algebraic topology - Small simplicial complexes with torsion in their homology?

UPDATE This version is substantially improved from the one posted at 8 AM.

I now think I can achieve $mathbb{Z}/p$ using $O( log p)$ vertices. I'm not trying to optimize constants at this time.

Let $B$ be a simplicial complex on the vertices $a$, $b$, $c$, $a'$, $b'$, $c'$ and $z_1$, $z_2$, ..., $z_{k-3}$, containing the edges $(a,b)$, $(b,c)$, $(c,a)$, $(a',b')$, $(b',c')$ and $(c',a')$ and such that $H^1(B) cong mathbb{Z}$ with generator $(a,b)+(b,c)+(c,a)$ and relation

$$2 {large (} (a,b)+(b,c)+(c,a) {large )} equiv (a',b') + (b',c') + (c',a').$$

I think I can do this with $k=6$ by taking damiano's construction with $p=2$ and adding three simplices to make the hexagon $(h_1, h_2, ldots, h_6)$ homologous to the triangle $(h_1, h_3, h_5)$.

Let $B^n$ be a simplicial complex with $3+nk$ vertices $a^i$, $b^i$, $c^i$, with $0 leq i leq n$, and $z^i_j$ with $0 leq i leq n-1$ and $1 leq j leq k-3$. Namely, we build $n$ copies of $B$, the $r$-th copy on the vertices $a^r$, $b^r$, $c^r$, $a^{r+1}$, $b^{r+1}$, $c^{r+1}$ and $z^r_1$, $z^r_2$, ..., $z^r_{k-3}$. Let $gamma_i$ be the cycle $(a^i,b^i) + (b^i, c^i) + (c^i, a^i)$.

Then $H^1(B^n) = mathbb{Z}$ with generator $gamma_0$ and relations
$$gamma_n equiv 2 gamma_{n-1} equiv cdots equiv 2^n gamma_0$$

Let $p = 2^{n_1} + 2^{n_2} + cdots + 2^{n_s}$.

Glue in an oriented surface $Sigma$ with boundary $gamma_{n_1} sqcup gamma_{n_2} sqcup cdots sqcup gamma_{n_s}$, genus $0$, and no internal vertices.

In the resulting space, $sum gamma_{n_i} equiv 0$ so $p gamma_0 equiv 0$, and no smaller multiple of $gamma_0$ is zero. We have use $3 + k log_2 p$ vertices. This is the same order of magnitude as Gabber's bound.

gr.group theory - Cayley graphs of finitely generated groups

The answer is no, as expected. The following proof is "joint work" with L. Scheele.
Consider $G=mathbb{Z}$, $K=D_infty$ and $H:=mathbb{Z}times mathbb{Z}/2mathbb{Z}$. Then $G approx K$ and $Kapprox H$, but $G notapprox H.$

Indeed, the Cayley graph associated to ${-1,1}$ for G and the Cayley graph associated to ${s,t}$ where $D_infty=langle s,t: s^2=t^2=1 rangle$ are clearly isometric.

Similarly, the Cayley graph associated to ${s,st,ts}$ for $K$ and the graph associated to ${(0,1),(-1,0),(1,0)}$ for $H$ are isometric.

However, let $S$ be some symmetric generating set for $G$. Then $S_k$, the set of vertices which have distance precisely $kgeq 1$ from the identity, has even cardinality because $S_k$ is invariant under the mapping $x mapsto -x$ and doesn't contain 0.

Now let $T$ be some symmetric generating set for $H$. Let $k_0$ be the distance of $(0,1)$ from the identity in the associated graph. Then $T_{k_0}$, the set of vertices which have distance precisely $k_0$ from the identity, has odd cardinality. Indeed, it is invariant under the mapping $(x,y) mapsto (-x,-y)$ since $T$ is assumed to be symmetric. But $(0,1)$ is a fixed point.

ag.algebraic geometry - Smooth dg algebras (and perfect dg modules and compact dg modules)

The condition of Hom(M,-) being a continuous functor, i.e. preserving (small homotopy) colimits is equivalent (in the present stable setting) to the maybe more concrete condition of preserving arbitrary direct sums. The issue is not finite direct sums, that's automatic (since the derived Hom is an exact functor, it automatically commutes with FINITE colimits).
This is better known as a compact object of the dg category (see n-lab for lots of discussion).
This is a strong finiteness condition on a module. Its importance in algebraic geometry was realized by Thomason (in a dream form of his friend Trobaugh), who proved some amazing fundamental results about the behavior (and abundance) of compact/perfect objects on schemes.

One can think of Hom(M,-) as the functional on the category defined by M (Hom being a kind of inner product), and this is saying the functional is "continuous"..
There's a discussion of the different common notions of finiteness for modules and their properties (including the foundational results of Thomason and Neeman) in Section 3.1 of this paper (sorry for the self-referencing -- none of this is in the least original, but it's a convenient discussion with plentiful references). This includes an explanation of why compactness is the same as being in the thick subcategory category generated by the free module, which is your definition of perfect from K-S (ie built out of the free module by taking sums, cones, summands), and also the same as being a dualizable object with respect to tensor product in case your category is the derived category of quasicoherent sheaves (ie this is a "commutative" notion not applicable in the NC setting you're discussing).

By the way the definition from K-S is the standard definition of perfection, that from K-K-P is the standard definition of compactness.. there are settings where the two notions don't agree (for example for sheaves on the classifying space of a finite group in a modular characteristic, or on BS^1) [hence our terminology of "perfect stack" in the paper with Francis and Nadler, which is a stack where these notions for sheaves agree and these nice finite objects generate].

The fact that perfection of the diagonal (ie A as an A-bimodule) is equivalent to smoothness in the case of a scheme is a reformulation of the homological criterion of Serre for smoothness of a point in terms of finite Tor amplitude of the skyscraper at the point - ie we're saying all points are smooth all at once.

quantum groups - The Killing Form for Co-Quasi-Triangular Hopf Algebras

I doubt this can be true. I claim that:

Lemma. Let $k$ be a commutative ring, $A$ be a $k$-algebra, and $Q:Ato k$ be a $k$-linear map such that $Qleft(1right)=1$. Then, the following four assertions (1), (2), (3), (4) are pairwise equivalent:

(1) The kernel $mathrm{Ker} Q$ is a two-sided ideal of $A$.

(2) The kernel $mathrm{Ker} Q$ is a right ideal of $A$.

(3) The kernel $mathrm{Ker} Q$ is a left ideal of $A$.

(4) The map $Q$ is a $k$-algebra homomorphism.

Proof of Lemma. Clearly, (4) $Longrightarrow$ (1) $Longrightarrow$ (2). Now let us prove that (2) $Longrightarrow$ (4): Assume that (2) holds. That is, we assume that $mathrm{Ker} Q$ is a right ideal of $A$. Clearly, every $ain A$ satisfies $Qleft(aright)cdot 1-ainmathrm{Ker} Q$ (since the $k$-linearity of $Q$ yields $Qleft(Qleft(aright)cdot 1-aright)=Qleft(aright)cdot underbrace{Qleft(1right)}_{=1}-Qleft(aright)=0$). Thus, every $ain A$ and $bin A$ satisfy $underbrace{left(Qleft(aright)cdot 1-aright)} _ {inmathrm{Ker} Q} b inmathrm{Ker} Q$ (since $mathrm{Ker} Q$ is a right ideal), so that

$0=Qleft(left(Qleft(aright)cdot 1-aright)bright)=Qleft(Qleft(aright)b-abright)=Qleft(aright)Qleft(bright)-Qleft(abright)$

(by the $k$-linearity of $Q$), so that $Qleft(aright)Qleft(bright)=Qleft(abright)$. Together with the $k$-linearity of $Q$ and $Qleft(1right)=1$, this yields that $Q$ is a $k$-algebra homomorphism, so that assertion (4) holds. Thus we have shown that (2) $Longrightarrow$ (4), which completes the (4) $Longrightarrow$ (1) $Longrightarrow$ (2) $Longrightarrow$ (4) circle. Thus, (4) $Longleftrightarrow$ (1) $Longleftrightarrow$ (2). Similarly (4) $Longleftrightarrow$ (1) $Longleftrightarrow$ (3). This proves that all four assertions (1), (2), (3), (4) are pairwise equivalent, and the lemma is proven.

---

The Lemma shows that as long as you want the kernel of $r$ to be an ideal (one- or two-sided), $r$ will be forced to be a $k$-algebra homomorphism. Considering the main example of co-quasi-triangular Hopf algebras, namely the group algebra with a bicharacter, the counterexample we gave in the comments above will hold.

Maybe the "right ideal" that your references claimed refered to a different algebra structure? One of my main sources of confusion in the advanced Hopf algebra theory has always been the presence of many conflicting multiplications, comultiplications, actions etc. on one and the same set.

at.algebraic topology - Group Structure on CP^infinty

Here is a partial answer to question 1: the necessary and sufficient condition for a (sufficiently reasonable, say a CW-complex) space to be homotopy equivalent to a topological group is that it should have the homotopy type of a loop space, or, in other words, that it should admit a structure of an $A_infty$-space. The necessity is clear. On the other hand, if $X=Omega Y$, then Milnor constructs in "The construction of the universal bundles I", section 3, a group $G(Y)$ with the same homotopy type as $X$. The construction is as follows (we assume $Y$ to be a polyhedron): take the subset of the disjoint union of $Y^n,ngeq 1$ formed by all sequences such that any two consecutive elements are in the same simplex and the first and the last elements are the base point, and take the quotient of this subset with respect to the equivalence relation generated by $(x_1,ldots,x,x,ldots x_n)sim (x_1,ldots,x,ldots,x_n)$ and $(x_1,ldots,x,y,x,ldots x_n)sim (x_1,ldots,xldots,x_n)$; the product is the concatenation product.

Here are some remarks:

1. The above is somewhat (but not completely) similar to what happens when one "strictifies" an $A_infty$ algebra by taking the cobar construction of the bar construction.




2. An H-space $X$ can have several non-homotopic products. These are one-to-one with $[Xwedge X,X]$, see e.g. Stasheff, H-spaces from a homotopy point of view, p.11, LNM 161 (which also has useful references to earlier work).

mathematics education - Why linear algebra is fun!(or ?)

An example that my last class loved was lossy image compression using the singular value decomposition.

The SVD says that the transformation corresponding to any real matrix (not necessarily square) can be decomposed into three steps: a rotation that forgets some dimensions, a stretch along the coordinate axes, and finally a rotation. In other words, every matrix can be written the form HDA, with the rows of A being orthonormal, the columns of H being orthonormal, and D being a square diagonal matrix with nonnegative nonincreasing entries on the diagonal.

Consider a photograph that is an $768times 1024$ array of $(red,green,blue)$ triples, which we can just as well store as 3 matrices $R$, $G$, and $B$ of real numbers. Now even though the matrix $R$ has nothing to do with transforming space, we can consider it as such, and using SVD write $R=HDA$. Call the numbers on the diagonal of $D$ by $lambda_1geq lambda_2 geq cdots geq lambda_sgeq 0$, and let $D_k'$ be $diag(lambda_1,dots,lambda_k,0,0,dots)$, an $stimes s$ diagonal matrix, and let $D_k$ be $diag(lambda_1,dots,lambda_k)$. Let $H_k$ be the $768times k$ matrix formed from the first $k$ columns of $H$, and similarly let $A_k$ be the $ktimes 1024$ matrix formed from the first $k$ rows of $A$. Then
$$R = HDA approx HD_k' A = H_k D_k A_k,$$
where $approx$ is because of continuity, which is appropriate if the $lambda$'s that were replaced with zeros were small.

Now for the punch-line. We need $3cdot 768 cdot 1024$ (about 2 megabytes) real numbers initially to store the photograph. But to store $H_k$, $D_k$, and $A_k$ for each of the three colors, we need only $3(768cdot k+k+kcdot 1024)=5379 k$ real numbers. With $k=25$, that gives a compression ratio of about 18. That is, file size goes from around 2 mb to around 130 kb. That is, it is faster by a factor of 20 to transmit the three matrices $H_{25}, D_{25}, A_{25}$ than it is to transmit their product.

SVD is fast enough to compute that you can do this instantly (using Mathematica, say) with a picture of the audience, and they can marvel at their own blurry (but quite recognizable) faces. Also, showing the actual file sizes on disk of the original bitmap and the compressed image is quite impressive. At least, it is if your calculations come out extremely close.

What's really impressive about this example (to me, at least) is that the matrix that we start with is just a table of data and not a transformation. But by considering it as if it were a transform, we gain power over it anyway. This is great motivation for linear algebra; students find it much easier to imagine encountering a table of data than a linear transformation.

ag.algebraic geometry - How do you define the Euler Characteristic of a scheme?

Here are some comments on the questions of the posting.

Every complex algebraic variety has the homotopy type of a finite CW-complex, so the Betti numbers are finite and the Euler characteristic is well defined. To simplify consider the quasi-projective case. Let $Xsubset mathbf{P}^n(mathbf{C})$ be a projective variety and let $Y$ be a closed subvariety, then we can consider both $X$ and $Y$ as real algebraic varieties in $mathbf{P}^{2n}(mathbf{R})$. Now real projective spaces can be embedded in affine spaces, as opposed to the complex case: we can associate to a line $l$ in $mathbf{R}^{k+1}$ the unique orthogonal projection with image $l$. A similar trick exists over an arbitrary field (the Jouanolou trick), but it is the uniqueness of the projection that gives us an embedding in the real case. In coordinates we take a point $(x_0:cdots: x_k)$ to the $k+1$ by $k+1$ matrix $(frac{x_i x_j}{sum x_i^2})$.

This implies that real projective varieties are affine. Then one can use the triangulation theorem for real affine varieties, as presented e.g. in Hironaka's Arcata 1974 lectures to triangulate $X$ so that $Y$ is a subcomplex; this gives a triangulation of $Xsetminus Y$ (infinite if $Y$ is nonempty) and a finite CW complex homotopy equivalent to $Xsetminus Y$.

I'm pretty sure a similar result should hold for arbitrary (not necessarily projective) complex algebraic varieties and also for algebraic spaces, but I've never seen the details worked out in the literature.

The other question (whether or not the algebraic structure determines the cohomology) is not completely trivial either (and the answer depends on what exactly one means by cohomology). If $X$ is defined over a finite extension $F$ of $mathbf{Q}$ and $X'=Xtimes_Fmathbf{C}$ for some embedding $Fsubsetmathbf{C}$, then the cohomology ring of $X'(mathbf{C})$ with finite coefficients does not depend on the embedding (and hence neither does the complex cohomology ring), see Freitag-Kiehl, 'Etale cohomology, theprem 11.6. It was an old question of Grothendieck whether the rational cohomology ring can depend on the embedding. It turned out even the real cohomology ring can, as recently shown by F. Charles. See www.math.ens.fr/~charles/crll5855.pdf

upd: here is an explicit procedure to obtain the Euler characteristic from the algebraic data: as mentioned in the comments, if $X$ is smooth and complete, we can take the alternating sum of the Euler characteristics of $underline{Omega^i}_X$'s. If $X$ the complement of a simple normal crossing divisor $D_1cupcdots cup D_k$ in a smooth complete $D_{varnothing}$, then $$chi(X)=sum_{Isubset{1,ldots,k}}(-1)^{|I|}chi(cap_{iin I} D_i).$$ Here we use the fact that the differentials in a spectral sequence do not change the Euler characteristic. In general one stratifies $X$ so that the difference of any two consecutive strata is smooth and takes the sum of the Euler characteristics of the strata. Using a similar procedure one can compute the Serre characteristic, which is a 2 variable analog; it can be seen as the image of the compactly supported cohomology in the Grothendieck group not of $mathbf{Q}$-vector spaces, but of the mixed Hodge structures.

pr.probability - Random geometric graphs and spanners

I assume you meant $p=(1+varepsilon)p_1$ in the first question, in which case the answer seems to be "no".

To see this, we note that, with high probability:

(i) The size of $C$ is $Theta(n)$ (this is the classical result);

(ii) The average graph-theoretic distance $d_G(x,y)$ between two randomly chosen vertices $x,yin C$ is concentrated around $cln n$ for some $c>0$ (this is proven in eg. Durrett's Random Graph Dynamics);

(iii) All points $p$ in the square are such that the ball of radius $r$ around $p$ contains $Theta(r^2 n)$ points of $C$, simultaneously for all $rgg ln^2n/n$. (To see this, notice that the positions of points in the square are independent from their being or not in the giant component, then apply a VC dimension argument + part (i)).

Now let $varepsilon>0$ be small (and fixed) and let $n$ grow. By item (ii), there is a high probability that one can find a point $pin C$ such that the set
$$P(p)equiv {mbox{all points $q$ in $C$ with }frac{d_G(p,q)}{cln n}in [1/2,1]}$$
has size $geq (1-varepsilon^2)|C|$. By part (iii), there is a high probability that at least one point $q_0in P(p)$ with $|p-q_0|leq varepsilon$ and at least one point $q_1in P(p)$ with $q_1geq 1/3$. Since $d_G(p,q_0),d_G(p,q_1)=O(ln n)$, this shows that:
$$frac{d_G(p,q_0)}{|p-q_0|}geq Omegaleft(frac{1}{varepsilon}right)frac{d_G(p,q_1)}{|p-q_1|}.$$

ag.algebraic geometry - Minimal number of generators of a homogeneous ideal (exercise in Harsthorne)

Dear Andrea: Hartshorne was right, but we need to do some work. Let $mu(I)$ be the minimal number of generators of $I$, and $mu_h(I)$ be the minimal number of a homogenous system of generators of $I$. Let $R=k[x_1,cdots,x_n]$ and $m=(x_1,cdots,x_n)$. Suppose $mu_h(I)=n$ and $(f_1,cdots, f_n)$ is a minimal homogenous set of generators. At this point we switch to the local ring $A=R_m$ (the reason: it is easier to do linear algebra over local rings, as anything not in $m$ is now invertible). It will not affect anything since $Isubset m$.

Construct a surjective map $F_0 = oplus_1^n A(-deg f_i) to I to 0$ and let $K$ be the kernel. We claim that $K subset mF_0$. If not, then one can find an element $(a_1,...,a_n) in K$ such that $sum a_if_i=0$ and $a_1$, say, has a degree $0$ term $u_1neq 0$. By considering terms of same degree in the sum one sees that there are $b_i$s such that:$$u_1f_1 = sum_{2}^n b_if_i$$
so the system is not minimal, as $u_1 in k$, contradiction.

Now tensoring the sequence $$ 0 to K to F_0 to I to 0$$ with $k=A/m$. By the claim $Ksubset mF_0$, so $Fotimes k cong Iotimes k$. It follows that $n= rank F_0 = dim_k(Iotimes k)$. But over a local ring, the last term is exactly $mu(I)$, and we are done.

convexity - Radstrom cancellation only for two convex sets?

Alex, your idea of using a separation theorem can be turned into a full proof as follows:

As you said, $A notsubset B$ iff there is a $a in A$ and vector $x$ such that $sup_{b in B} langle b,x rangle < langle a,x rangle$. But then,

begin{align}
sup_{z in B + C} langle z, x rangle &= sup_{b in B, c in C} (langle b, x rangle + langle c, x rangle ) \\
&= sup_{b in B} langle b, x rangle + sup_{c in C} langle c, x rangle \\
&< langle a, x rangle + sup_{c in C} langle c, x rangle \\
&= sup_{z in a + C} langle z, x rangle \\
&leq sup_{z in B + C} langle z, x rangle,
end{align}

a contradiction.

set theory - Denumerable sets

Here is a summary of standard parlance in set theory.

• A set is finite if it is equinumerous with a natural number. Otherwise, the set is infinite.




• A set is countable if it is equinumerous with a subset of the natural numbers. (This includes the finite sets.)




• A set is countably infinite if it is countable and infinite. This is also called countably enumerable.




• A set is Dedekind finite if it is not bijective with any proper subset of itself. This is equivalent to the set not containing any countably infinite subset. If the Axiom of Choice holds, it is equivalent to being finite.




• The word enumerable is often used with countable sets, but does not by itself imply countability. For example, set theorists often enumerate uncountable sets in a well-ordered sequence. The word enumeration carries a connotation of being well-ordered, but this is not strict, since one might enumerate a set by reals, meaning simply to have a surjection from the reals onto the set.




• Some set theorists use denumerable synonymously with countable (e.g. Moschovakis, Notes on Set Theory, undergraduate textbook). Many or most set theorists seldom use the word denumerable. In a quick perusal, I couldn't find use of it in Jech's book Set Theory or Kanamori's book on large cardinals.

Of course, all these concepts originate with Cantor, and I looked up his Contributions to the founding of the theory of Transfinite Numbers (Dover, in translation by Jourdain). I couldn't find the word denumerable at all, but Cantor does use enumerable at first just to mean countable, but then later extended to include uncountable well-ordered enumerations, as I mentioned above.

soft question - Theorems for nothing (and the proofs for free)

I'd say the Tutte-Berge formula, which is a wonderful result that tells you (almost) everything you want to know about matchings in graphs. Although there are many proofs of this theorem, there is a beautiful proof for free using matroids. Strictly speaking, there is a proof for free of Gallai's Lemma (from which Tutte-Berge follows easily).

Gallai's Lemma.

Let $G$ be a connected graph such that $nu(G-x)=nu(G)$, for all $x in V(G)$. Then $|V(G)|$ is odd and def$(G)=1.$

Remark: $nu(G)$ is the size of a maximum matching of $G$, and def$(G)$ denotes the number of vertices of $G$ not covered by a maximum matching.

Proof for free.
In any matroid $M$ define the relation $x sim y$ to mean $r(x)=r(y)=1$ and $r({x,y})=1$ or if $x=y$. (Here, $r$ is the rank function of $M$). We say that $x sim^* y$ if and only if $x sim y$ in the dual of $M$. It is trivial to check that $sim$ (and hence also $sim^*$) defines an equivalence relation on the ground set of $M$.

Now let $G$ satisfy the hypothesis of Gallai's Lemma and let $M(G)$ be the matching matroid of $G$. By hypothesis, $M(G)$ does not contain any co-loops. Therefore, if $x$ and $y$ are adjacent vertices we clearly have $x sim^* y$. But since $G$ is connected, this implies that $V(G)$ consists of a single $sim^*$ equivalence class. In particular, $V(G)$ has co-rank 1, and so def$(G)$=1, as required.

Edit. For completeness, I decided to include the derivation of Tutte-Berge from Gallai's lemma. Choose $X subset V(G)$ maximal such that def$(G-X) -|X|=$ def$(G)$. By maximality, every component of $G-X$ satisfies the hypothesis in Gallai's lemma. Applying Gallai's lemma to each component, we see that $X$ gives us equality in the Tutte-Berge formula.

at.algebraic topology - Fiber bundle = principal bundle + fiber?

This question is heavily related to this question.

Fix a sufficiently nice and connected topological space $B$ and let $FB$ be the category of fiber bundles over $B$. A morphism $f: (Eto B)to (E'to B)$ in this category is a map $Eto E'$ over $B$ and hence it maps fibers to fibers.

Edit: A fiber bundle $p:Eto B$ is a continuous map such that there exists a local trivialization. Since $B$ is nice and connected, all the fibers $p^{-1}(x)$ are isomorphic.

According to the very helpful answers here,

• a fiber bundle over $B$ with fiber $F$ determines a $G=Aut(F)$-principal bundle together with (trivially) a left $G$-action on $F$ and


• a $G$-principal bundle over $B$, where $G$ is an arbitrary topological group, together with a topological space $F$ and a left $G$-action on $F$ determines a fiber bundle over $B$ with fiber $F$.

Can one formulate this correspondence "categorically", i.e. is there an equivalence of the category $FB$ to a product (?) of two categories, one encoding the "glueing structure" (the principal bundle) and one encoding the "fiber information" (the space $F$ with the action)? (In particular, what should be the analogue to a morphism of fiber bundles?)

(Certainly is not possible to get such a description precisely like above because one have to fix the topological group $G$ to say what a space $F$ with a $G$-action is and conversely one have to fix a space $F$ to say what a $G=Aut(F)$-principal bundle is, but maybe there is a way to formulate this in general.)

lo.logic - Most 'unintuitive' application of the Axiom of Choice?

The most destructive aspect of uncountable choice is that it conflicts with random choice. With uncountable choice, any object which is constructed using randomness, like a random walk, a random field, or even a randomly picked real number, cannot exist, because there are sets which it cannot consistently be assigned membership to.

In order to define what it means to have a random walk, or a random graph, or a random infinite Ising model configuration, or whatever, you need to define what it means to have an infinite sequence of random coin flips. The result can be encoded as a real number, the binary digits of which are the results of the coin flip, and if this real number really exists, as an actual mathematical object, then this object either belongs to any given set S, or it doesn't.

It is so intuitive to think of random objects this way, that they are often illustrated with pictures, showing us what they look like (see http://en.wikipedia.org/wiki/Wiener_process for a picture of a "realization" of a random walk). These pictures do not signify anything when the axiom of choice is present.

The reason is that once you have actual random objects, for which you can assign membership to any set S, then you can define the probability of landing in S by choosing random objects again and again, and asking what fraction of the time you land in S. This always converges, because given any long finite sequence of 1's and 0's which represent independent random events, any permutation of the 1's and 0's has the same likelihood. This means that it is probability 0 that the seqeunce will oscillate in any way, and with certainty it will converge to a unique answer.

This answer is the measure of the set S, and every set is measurable in this universe. This makes analysis much easier, because everything is integrable, measurable, etc. This is so intuitive, that if you look at any probability paper, they will illustrate with random objects without hesistation, implicitly denying choice.

(I realize that this answer overlaps with a previous one, but it corrects a serious central mistake in the former.)

ct.category theory - Understanding the etale space construction from a formal viewpoint

Here is a sketch of why I think the condition that $Y$ is a local homeomorphism over $X$ should be sufficient for the counit to be a homeomorphism. I haven't worked out the converse yet.

For a presheaf $F in Set^{mathcal{O}(X)^{op}}$, the formula for the left Kan extension should be $$L(F) = mathrm{colim}_{y(U) rightarrow F} U$$ where $y : mathcal{O}(X) rightarrow Set^{mathcal{O}(X)^{op}}$ is the Yoneda embedding. By Yoneda's lemma, the indexing category for the colimit is exactly the category of elements of $F$ which I will write as $int F$.

Now, consider the case where $F = Gamma_Y$ for some space $p: Y rightarrow X$ and assume that $p$ is a local homeomorphism. We have $Gamma_Y(U) = {sigma : U rightarrow Y | p circ sigma = mathrm{id}_U }$. So the objects in the category $int Gamma_Y$ are exactly the sections over the various open sets of $X$, and the morphisms are given by restriction of sections. I'll write $d(sigma)$ for the domain of a given section.

Our Kan extension formula becomes $$L(Gamma_Y) = mathrm{colim}_{sigma in int Gamma_Y} d(sigma)$$ From here it's easy to see what the counit is: since our object is given by a colimit, it suffices to construct a map $d(sigma) rightarrow Y$ for each $sigma in int Gamma_Y$. But clearly $sigma$ itself qualifies.

Now choose an open covering ${V_alpha}$ of $Y$ such that $p$ restricts to a homeomorphism on each $V_alpha$. We then have a collection ${sigma_alpha : p(V_alpha) rightarrow V_alpha}$ of sections by choosing the inverse to each restriction. My claim would be that this collection is cofinal (or final? I can never remember which) in the category $int Gamma_Y$ so that we can restrict our colimit to just this subcategory. Notice that in this case, the components of the counit map above are homeomorphisms.

Moreover, this subcategory should also be cofinal in $mathcal{O}(Y)$ by associating $sigma_alpha$ with the open set $V_alpha$. Then the fact that the counit is a homeomorphism should be the statement that a topological space is the colimit of any of its open coverings.

Is this along the lines of what you were thinking?

mg.metric geometry - In a locally CAT(k) space, does uniqueness of geodesics imply the lack of conjugate points?

A complete, simply connected Riemannian manifold has no conjugate points if and only if every geodesic is length-minimizing. I just realized that I don't know whether the same is true for a locally CAT(k) space (i.e. a geodesic space with curvature bounded above in the Alexandrov sense).

Thanks to Alexander and Bishop, there is a developed "geodesic analysis" in these spaces, including Jacobi fields and conjugate points. And there is a Cartan-Hadamard theorem for spaces without conjugate points: if it is simply connected, then every pair of points is connected by a unique geodesic.

In the Riemannian case, the converse statement follows from the basic fact that a geodesic beyond a conjugate point is no longer minimizing. This is proved by constructing a length-decreasing variation, or something similar, from a vanishing Jacobi field. Unfortunately, this argument uses a lower curvature bound. Well, not quite that, because it also works in Finsler geometry, but anyway it fails for CAT(k): on a bouquet of two spheres there are geodesics that remain minimizing beyond a conjugate point.

However this does not disprove the converse Cartan-Hadamard theorem. Hence the question:

Let $X$ be a space with curvature locally bounded above. Let's not talk about monsters: the space is complete, locally compact, all geodesics are extensible (otherwise one can play dirty tricks with a boundary). Suppose that every geodesic in $X$ is minimizing. Or even better: every pair of points is connected by a unique geodesic. Does this imply that the geodesics have no conjugate points?

UPDATE. Thanks to Henry Wilton, I've found that there is no standard definition of a conjugate point. In fact, some definitions are designed so as to imply the affirmative answer to my question immediately. When I asked the question, I meant the following (maybe not the best possible) definition.

Fix a point $pin X$ and consider the space $X_p$ of geodesic segments emanating from $p$. The segments are parametrized by $[0,1]$ proportionally to arc length. The space $X_p$ is regarded with the $C^0$ metric. The exponential map $exp_p:X_pto X$ is defined by $exp_p(gamma)=gamma(1)$. A point $q=gamma(1)$ is conjugate to $p$ along $gamma$ iff $exp_p$ is not bi-Lipschitz near $gamma$.

ac.commutative algebra - How to prove that the subrings of the rational numbers are noetherian?

I will break this up into two steps, each of which is a standard exercise:

1) Let $R$ be a principal ideal domain with fraction field $K$. Every overring of $R$ -- i.e., every ring $S$ with $R subset S subset K$ -- is the localization of $R$ at a multiplicative subset.

2) If $R$ is a Noetherian ring and $S$ is a multiplicative subset, then the localization $S^{-1} R$ is a Noetherian ring.

mp.mathematical physics - What is an integrable system

This is, of course, a very good question. I should preface with the disclaimer that despite having worked on some aspects of integrability, I do not consider myself an expert. However I have thought about this question on and (mostly) off.

I will restrict myself to integrability in classical (i.e., hamiltonian) mechanics, since quantum integrability has to my mind a very different flavour.

The standard definition, which you can find in the wikipedia article you linked to, is that of Liouville. Given a Poisson manifold $P$ parametrising the states of a mechanical system, a hamiltonian function $H in C^infty(P)$ defines a vector field $lbrace H,-rbrace$, whose flows are the classical trajectories of the system. A function $f in C^infty(P)$ which Poisson-commutes with $H$ is constant along the classical trajectories and hence is called a conserved quantity. The Jacobi identity for the Poisson bracket says that if $f,g in C^infty(P)$ are conserved quantities so is their Poisson bracket $lbrace f,grbrace$. Two conserved quantities are said to be in involution if they Poisson-commute. The system is said to be classically integrable if it admits "as many as possible" independent conserved quantities $f_1,f_2,dots$ in involution. Independence means that the set of points of $P$ where their derivatives $df_1,df_2,dots$ are linearly independent is dense.

I'm being purposefully vague above. If $P$ is a finite-dimensional and symplectic, hence of even dimension $2n$, then "as many as possible" means $n$. (One can include $H$ among the conserved quantities.) However there are interesting infinite-dimensional examples (e.g., KdV hierarchy and its cousins) where $P$ is only Poisson and "as many as possible" means in practice an infinite number of conserved quantities. Also it is not strictly necessary for the conserved quantities to be in involution, but one can allow the Lie subalgebra of $C^infty(P)$ they span to be solvable but nonabelian.

Now the reason that integrability seems to be such a slippery notion is that one can argue that "locally" any reasonable hamiltonian system is integrable in this sense. The hallmark of integrability, according to the practitioners anyway, seems to be coordinate-dependent. I mean this in the sense that $P$ is not usually given abstractly as a manifold, but comes with a given coordinate chart. Integrability then requires the conserved quantities to be written as local expressions (e.g., differential polynomials,...) of the given coordinates.

gt.geometric topology - When does a CW-complex of dimension 2 embedd in $R^4$ ?

I think there is an obstruction called Van Kampen's obstruction to embedding an $n$-complex into $mathbb{R}^{2n}$. If you could embed the $n$-complex into $mathbb{R}^{2n}$ then it has a thickening
to a manifold, and that manifold has an intersection pairing in dimension $n$. The obstruction is derived from this pairing. If the complex embeds the obstruction vanishes. For complexes of dimension greater than 2 this suffices, it is not a complete invariant for two complexes. This is worked out in a paper of Krushkal, Freedman, and Teichner and then an example of imcompleteness of the invariant is in a paper of Krushkal. The example given by FKT is of the two skeleton of the six simplex.

Of course that example has more than one vertex. If you could embed one vertex $2$-complexes in $mathbb{R}^4$ then some weird stuff would be happening in that example as you collapse a maximal tree in the one skeleton.

The weird thing is that the one skeleton becomes planar. There is a folk theorem that the
classification of four manifolds is undecidable because any finitely presented group is the fundamental group of a four manifold. The proof is to embed a two complex with one vertex,
whose fundamental group is the chosen finitely presented group into $mathbb{R}^4$ and take a regular neighborhood. Its gotta be Stallings. :)

I would guess that the two questions, one vertex, or planar $1$-skeleton are equivalent.

nt.number theory - Two questions about discriminants of polynomials in Q[x]

Suppose $f in mathbb{Q}[x]$ is monic, with roots $alpha_{1},dots,alpha_{n}$. Define the discriminant of $f$ to be the number $ Delta = Pi_{i<j} (alpha_{i} - alpha_{j})^2$. Let $D(f) = sqrt{Delta} = Pi_{i<j} (alpha_{i} - alpha_{j})$ be the square root of the discriminant. Here are the questions:

1) Let $p/q in mathbb{Q}$ be fixed. What can be said about the set ${ f in mathbb{Q}[x] : D(f) = p/q }$? For example, if we fix $p$ to be some prime, then the family of quadratics having this prime as the discriminant are just translates of the polynomial $x(x-p)$ by any rational number. Of course, the whole family has the same (trivial) Galois group. What can be said about the Galois group of families of polynomials of greater degree with fixed discriminant? The Galois groups will be subgroups of $A_{n}$, but is there any reason to expect any 'stability'?

and less interestingly,

2) What rational numbers $p/q in mathbb{Q}$ have the property that $p/q = D(f)$ for some $f$ as above, with the degree of $f$ fixed to be some natural number $n$? For example, every rational number is the discriminant of some quadratic. But it seems clear that there is no cubic $f$ with $D(f) = 2 times 2 times 3$. What can be said in general?

The context of this is I'm trying to generate some families of polynomials that don't have Galois group $S_{n}$ and my simple-minded idea is to use the discriminant to 'pick them out' (it won't do to just generate polynomials randomly, as the set of polynomials with Galois group $S_{n}$ is thick in the set of all polynomials).

Thank you!

rt.representation theory - Steinberg Representations of Finite Groups of Lie Type

I think that for finite groups of Lie type, the analogue of "having a Whittaker model" is that the representation occurs in a Gelfand-Graev representation: these are the representations obtained by inducing a "regular" character from the unipotent subgroup of a rational Borel. Such representations are multiplicity free and so constitute a "model" (in the sense I think people say "Whittaker model"). Now when the center of $G$ is connected, all regular characters are conjugate under the action of the maximal torus of the Borel, so the Gelfand-Graev representation is unique (otherwise there is a family of such representations). In their famous paper, Deligne and Lusztig decompose the Gelfand-Graev representation in this case and show that there is exactly one constituent in each "geometric conjugacy class" of irreducible representations (which can be thought of as a semisimple conjugacy class in the dual group). The Steinberg representation is then the representative in the conjugacy class of the identity element -- that is the representative among the "unipotent representations".

To focus more on the actual question (!) the character of the Steinberg representation is explicitly known, and it is easy to check from this that its restriction to $U$ is the regular representation, so it certainly occurs in the Gelfand-Graev representation.

algorithms - Heaviest Convex Polygon

It should be polynomial (probably O(N^3)) in the number of input points using the dynamic programming technique in my paper with Overmars et al, "Finding minimum area k-gons", Disc. Comput. Geom. 7:45-58, 1992, doi:10.1007/BF02187823.

The idea is: for each three points p,q,r, let W[p,q,r] be the optimal convex polygon that has p as its bottommost point (smallest y-coordinate) and qr and rp as edges. We can calculate W[p,q,r] by looking at all choices of s for which psqr is convex and combining the (previously computed) value W[p,s,q] with the weight of triangle pqr.

As described above this takes time O(N^4) but I think that, for each pair of p and q one can examine the points s and r in the order of the slopes of the lines sq and sr, keeping track of the best s seen so far and using that choice of s for each r in this slope ordering, to reduce the time to O(N^3)

computability theory - What are the most attractive Turing undecidable problems in mathematics?

Not mentioned yet, that any computer language extended with non-deterministic features is also Turing computable.

This is interesting, because it allows the language to be simplified. If the programs operate on objects that are nil or a pair. Then you only need five instructions:

• The constant nil


• A pair operator


• A sequence operator, that executes one code fragment after another


• An inverse operator


• A closure operator, which repeats a code fragment zero or multiple times

If you want to construct a piece code of that adds the two values of a pair, then first make something that construct (a - 1, b + 1) from (a, b). Then take the closure. This will generate (a - n, b + n). Finally, pick the value (0, c) and output c. This can be done by using the inverse operator on the pair and nil.

So, programming is a little bit odd, because you select the right value outside the loop (closure), rather than inside the loop, as in deterministic languages. The advantages is the much more simpler structure. No variables, no recursion, no matching operators (just use the inverse) and no control-structures, except closure.

This makes it a little bit between programming and mathematics. The simpler structure, allows easier mathematical reasoning. So, it might be an idea to convert a program in a deterministic language, to a program of a simplified non-deterministic language, before doing any mathematics on the program.

Lucas

big picture - Examples of eventual counterexamples

In answering another MathOverflow question on Graham's number, I quoted from Harvey Friedman's Enormous Numbers in Real Life. Perhaps eventual counterexamples bear some relation to proof strength in certain systems of logic? Anyway, that example there could be rephrased to fit the current question.

Suppose I look at strings on three symbols, and given a word w of length n I look
at subwords of the form (forgive the AWK notation) spc[i] = substr(w,i,i+1), i.e.
those substrings starting at the ith character going for length i+1 characters.
So spc[1] gets the first two characters of w, spc[2] == w[2]w[3]w[4], and so on.

I manage to find, for every n that I can compute, a string w_n that I use for w
above such that for 0 < i < j < = n/2, spc[i] is not a subsequence of spc[j]. Others find such examples for even larger values of n. It would be reasonable for me to believe I could find arbitrarily long strings with this property.

Enter Harvey Friedman:

"THEOREM 8.1. Let k >= 1. There is a longest finite sequence
x1,...,xn from {1,...,k} such that for no i < j <= n/2 is
xi,...,x2i a subsequence of xj,...,x2j.

For k >= 1, let n(k) be the length of this longest finite
sequence.

Paul Sally runs a program for gifted high school students at
the University of Chicago.

He asked them to find n(1), n(2), n(3). They all got n(1) =
3. One got n(2) = 11. Nobody reported much on n(3).
I then started to ask several mathematicians to give an
estimate on n(3), some of them very famous. I got guesses
like this:
60, 100, 150, 200, 300.
They were not in combinatorics. Recently I asked Lovasz,
telling him about these five guesses. He guessed 20,000.

THEOREM 8.2. n(3) > A(7,184).
Lovasz wins, as his guess is closer to A(7,184) than the
other guesses.

Recall the discussion about A(5,5) being incomprehensibly
large. With the help of computer investigations (with R.
Dougherty), I got:

THEOREM 8.3. n(3) > A(7198, 158386).

A good upper bound for n(3) is work in progress. Crude result:
A(n,n) where n = A(5,5). "

Here A(n,n) is defined earlier in Friedman's paper as an Ackermann-like sequence.
I suspect n(3) squishes Graham's number quite unlike a galactic black hole absorbing a prion or even a quark.

EDIT: I have been corrected; in the squishing hierarchy, n(4) squishes Graham's number, which squishes n(3). Again, unlike any physical realization I can imagine. END EDIT

The moral here is: "Don't jump to conclusions without a sufficiently strong proof system as back up".

Gerhard "Ask Me About System Design" Paseman, 2010.02.17

rt.representation theory - Is there a good reference for the relationship between the Yangian and formal based loop group?

For every finite dimensional semi-simple Lie group $mathfrak{g}$, we have a loop algebra $mathfrak{g}[t,t^{-1}]$. This loop algebra has a natural invariant inner product by taking the residue at zero of the Killing form applied to two elements (i.e. $t^kmathfrak{g}$ and $t^{-k-1}mathfrak{g}$ are paired by the Killing form.)

This Lie algebra actually has a Manin triple structure with respect to this inner product: the subalgebras $mathfrak{g}[t]$ and $t^{-1}mathfrak{g}[t^{-1}]$ are both isotropic, and non-degenerately paired by this form. This makes $mathfrak{g}[t]$ into a Lie bialgebra, by getting the cobracket from the bracket on $t^{-1}mathfrak{g}[t^{-1}]$.

Now, as we all know, Lie bialgebras can be quantized: in this case, the result is a quite popular Hopf algebra called the Yangian. By the usual yoga of quantization of Lie bialgebras, the dual Hopf algebra to the Yangian quantizes the universal enveloping $t^{-1}mathfrak{g}[t^{-1}]$, so if you take a different associated graded of the Yangian, you must get the Hopf algebra of functions on the group with Lie algebra $t^{-1}mathfrak{g}[t^{-1}]$, which is $L_<G$, the based formal loop group.

Now, all of these things also have explicit descriptions in terms of equations, and it seems as though this story must be worked out explicitly somewhere, but I've had little luck locating it. Does anyone know where? Or is this story just wrong, and that's why I can't find it?

EDIT: The comment below mostly answers this question. I would be interested if anyone out there has written something more explicit than the Etingof and Kazhdan paper, but it's the sort of thing I was looking for. If it were to be left in the form of an answer, I would probably accept it (hint, hint).

pr.probability - Characterizing polyhedron from Brownian particle collisions with a boundary

Please imagine that we have an ordinary 2-sphere, of radius $r_{sphere}$, and some three-dimensional polygon that has all of its points fixed at positions strictly internal to the sphere's surface. Also confined in the sphere is point-like particle (with diffusion constant, $D_{particle}$) undergoing Brownian motion. The surface of the 2-sphere, as well as the surface of the polygon internal to the 2-sphere, are perfect reflecting boundaries for the particle.

Working in discrete time, we track the point-like particle for $N$ finite time units (we'll call them seconds), $(t_1, t_2, ..., t_k, ..., t_N) in T$. However, during this time the only information we are allowed to record is:

1. If a collision between the probe and the surface of the 2-sphere occurs at a given time point, $t_k$.

And if there is at least one such collision during $t_k$...

1. The coordinates of a collision event on the surface of sphere, randomly selected from all collisions that occur during $t_k$.

---

Beyond, perhaps, the volume of the polygon in the sphere (and I'm not entirely sure this is learnable), how (if at all possible) can we use the information specified above to characterize the polygon in some additional manner?

Update - If we apply a further restriction that the polyhedron is convex, at the limit of large $N$ will there be enough information from the collisions to reconstruct the convex polyhedra?

terminology - Standard name for basis-independent submatrices?

The standard name in operator theory is "compression", and its partner in crime is "dilation". I.e., A is a compression of B if and only if B is a dilation of A (although sometimes "dilation" is reserved for cases where the compression respects powers). The Wikipedia entry is not proof, but here it is anyway. As for searches, you'll get some relevant hits from "compression of an operator" with quotes.

Here are some examples.

---

Some further remarks:

Sz.-Nagy and Foiaș in Harmonic analysis of operators on Hilbert space (1970) use the notation $text{pr }T$ for the compression of $T$ onto $K$ (see page 10), but apparently without ever giving it a name. The notation is suggestive of "projection", and that is the terminology used by Sarason in "Generalized interpolation in $H^infty$" (1967).

Lebow goes into more detail on terminology in "A note on normal dilations" (1965), saying in particular that Sz.-Nagy used "projection". In fact, this is the terminology used by Sz.-Nagy in the celebrated appendix to Riesz and Sz.-Nagy's Functional analysis (1955), which in turn refers to Halmos's paper "Normal dilations and extensions of operators" (1950) as the first place where "compression" and "dilation" were used. The terminology "strong compression" may be used when the compression respects powers, and this is the same as saying that $K$ is semi-invariant for $T$ (see Sarason's "On spectral sets having connected complement" (1965)). If $K$ is reducing for $T$, i.e., if both $K$ and $K^perp$ are invariant subspaces for $T$, then Lebow calls the compression a "reduction".

Dixmier gives some terminology in von Neumann algebras (translated 1981 printing) for the case when the compression is applied to an entire von Neumann algebra of operators, which clashes somewhat with the terminology of Lebow. A von Neumann algebra compressed to the space of a projection in the algebra is called a "reduced" von Neumann algebra (page 19), even though the space is reducing only if the projection is in the center. The compression of a von Neumann algebra onto the space of a projection in the commutant (in which case the compression is a normal $*$-homomorphism) is called an "induction". If $P$ denotes the orthogonal projection you called $pi_K$, then Dixmier uses the notation $T_K$ or $T_P$ for the compression, but without ever giving a name to the construction for single operators. On the other hand, Jones and Sunder use "reduction" for what Dixmier calls "induction", more in tune with Lebow, on page 21 of Introduction to subfactors (1997).

I stand by my answer that by now "compression" is most standard for single operators, and it is satisfying to find out that we have Halmos to thank for this.

mg.metric geometry - Algebraicity of the completion of a field? Finiteness?

I had to think for a while to understand Scott's answer (or at least, what I suspect he meant by his answer), and in the end there were enough details to sort out that I thought they were worth posting. It ended up being too long to post as a comment, so here it is as a separate answer. Unless it's all nonsense, of course....

Let {$x_{alpha}$} be a transcendence basis of $mathbb{R}$ over $mathbb{Q}$, and let $L$ be the intermediate field that they generate, so that $mathbb{C}$ is the algebraic closure of $L$ in $mathbb{C}$. Take also a collection of open disks $D_{alpha}$ in $mathbb{C}$ such that any collection of points $y_{alpha} in D_{alpha}$ is dense in $mathbb{C}$ in the usual topology. Now for each $alpha$, take $x_alpha$ and multiply it by an appropriate root of unity and a rational number so that the result $y_alpha$ lies in $D_alpha$. The collection {$y_{alpha}$} is still algebraically independent over $mathbb{Q}$, because a dependence gives an algebraic dependence of {$x_alpha$} over some finite extension of $mathbb{Q}$, which implies the existence of an algebraic dependence over $mathbb{Q}$ as well.

So there exists $sigma : L to mathbb{C}$ sending $x_{alpha} mapsto y_{alpha}$. Now by the usual fact that field embeddings into algebraically closed fields can be extended across algebraic extensions, $sigma$ extends to a map $mathbb{C} to mathbb{C}$. But note that by construction $sigma$ is surjective! The image contains each $y_alpha$, and it contains all the roots of unity, so it contains all the $x_alpha$'s; thus the image is an algebraic closure of $L$ in $mathbb{C}$, hence all of $mathbb{C}$.

In particular $mathbb{C}$ is a quadratic extension of $sigma(mathbb{R})$, obtained by adjoining $sigma(i)$. But finally $sigma(mathbb{R})$ is dense in $mathbb{C}$ since its image contains all the $y_alpha$'s, and so giving $sigma(mathbb{R})$ the norm induced from the usual norm on $mathbb{C}$, we get a normed field $sigma(mathbb{R})$ whose completion is exactly $mathbb{C}$, i.e., a quadratic extension of it. Thus the answer to your second question actually yes.

cv.complex variables - the Cech-cohomology of the sheaf of germs of plurisubharmonic functions defined on a domain in C^n

we all know that if we consider the sheaf of germs of a holomorphic functions defined on a domain in C^n,we have too many beautiful theorems characterizing the geometry of the domain by consider the Cech-cohomology of the sheaf.Then i think that plurisubharmonic functions is in some sense a weaker function than holomorphic functions.So we may get some beautiful theorems as the case of holomorphic case, for example if we can proof that for a domain in C^n,the first Cech-cohomology of the sheaf of germs of plurisubharmonic functions vanishes ,we then can choose any good plurisubharmonic functions as we want. What i want to ask is that have you ever considered such a question ,and i don't know whether this is a good question ? I want to hear some suggestions.

gr.group theory - How can we formalize the naturality of certain characteristic subgroups?

I have plenty to say, so to simplify matters, I'll use the term "subgroup-defining function" for an isomorphism-invariant mapping that associates a unique subgroup to each group. [NOTE: It is not really a "function" because the "domain" and "range" are not sets.]

Any subgroup-defining function yields a characteristic subgroup, because the isomorphism-invariance implies invariance under automorphisms. However, it is not usually the case that a subgroup-defining function gives an endofunctor (in the sense that Scott describes), i.e., it is not necessary that it obey covariance with arbitrary group homomorphisms.

There are a few special examples of endofunctors, notably the commutator subgroup, members of the derived series, members of the lower central series, and other verbal definitions (that give verbal subgroups). In particular, if a subgroup-defining function is an endofunctor, it should, as Scott mentions, output a fully invariant subgroup, which is a weaker condition than being verbal but still stronger than being characteristic.

In fact, most subgroup-defining functions of interest are not endofunctors, and this might be related to the fact that category-theoretic, or functorial, thinking, does not come up much in the study of groups. Subgroup-defining functions such as the center, member of the upper central series, Frattini subgroup, Fitting subgroup, socle, are not endofunctors. Moreover, the subgroup they yield are not necessarily fully invariant. Interestingly, many of these subgroups are still strictly characteristic subgroups (also called distinguished subgroups) -- they are sent to within themselves by surjective endomorphisms of the group. However, this is not true for all of them.

The next question might be: is there some sense in which the subgroups obtained through easy-to-write subgroup-defining functions are more special than arbitrary characteristic subgroups? There are two related ideas that we can borrow from logic to define notions of "uniqueness" stronger than characteristicity:

1. There should be no other subgroup of the group such that the theories of the two group-subgroup pairs are "equivalent" in whatever logic we are working with. In first-order logic, there should be no other subgroup whose embedding in the whole group is elementarily equivalent to that of the given subgroup.




2. The subgroup can be defined (as a subset of the group) in the pure theory of the group, using whatever logic we are working with. In first-order logic, this is what we'd call a "purely definable subgroup" (or "definable subgroup" -- the purely is to emphasize that no additional structure has been tacked on to the group). As mentioned in Henry's reply, the center is purely definable (more generally, all members of the finite part of the upper central series are) but the commutator subgroup is not purely definable for free groups.




3. Even more generally, we may want that there is a pure definition that works for the subgroup-defining function, as opposed to just requiring that the output of the subgroup-defining function for each input group is definable in that group.

For each logic, (2) is stronger than (1). For instance, a purely definable subgroup cannot be elementarily equivalent to any other subgroup. Moreover, the more powerful the logic, the weaker the notions (1) and (2) in that logic.

[NOTE: That (2) in general is stronger than (1) can be seen from the analogous situation for real numbers: any two real numbers can be distinguished by a first-order predicate in the theory of real numbers, so every real number is "unique" in the sense of (1). However, there are only countably many definable real numbers, so almost all real numbers are not uniquely definable in the sense of (2).]

Is there a ground between Set Theory and Group Theory/Algebra?

You may want to determine which discipline of set theory to link to another discipline. Descriptive Set Theory came (roughly) as a result of foundational issues arising from looking at certain arguments in Topology and Real Analysis, and at some point later ties to Model Theory, Proof Theory, and Recursion Theory were also investigated.

If you look at results in Universal Algebra, you will find many links to various foundational disciplines. This is probably the easiest source to find the kinds of links you mention. For example, as a weak parallel to Shelah's Classification Theory, one finds looking at varieties of algebras and considering their spectra, and classifying those which have many models in algebraic terms to those which have few models. People such as Baldwin, Jeong, Jezek, Kearnes, McKenzie, Valeriote, and Wood do work on decidability, the lattice of interpretability types, spectra, and other questions in the context of varieties.

There is also algebraic logic, cylindric algebras, and algebras being used to study certain aspects of set theory and logic. You may want to peruse some of that material and then revisit the question of what links you would still like to see.

Gerhard "Ask Me About System Design" Paseman, 2010.04.06

kt.k theory homology - Regarding the Gerstenhaber bracket on Hochschild cohomology and Morita equivalence

Associated to any $A_infty$ $k$-algebra $A$ the Hochschild cochain complex $CH^*(A)$ has the structure of a dg-Lie algebra and a dg-algebra which are compatible enough that the cohomology is a Gerstenhaber algebra.

If two $A_infty$ algebras are Morita equivalent, are their Hochschild cochain complexes isomorphic in (i) the category of $k$-dg-algebras and (ii) the category of $k$-dg-Lie algebras, both up to quasi-isomorphism? Are they isomorphic in some category that feels both structures together?

Now suppose that $mathcal{C}$ is a dg-category over a field $k$. We say that the $k$-dg-algebra $CH^*(mathcal{C}) = End(id_mathcal{C})$ is the Hochschild cochain complex. Does $CH^*(mathcal{C})$ have a bracket that generalizes the known one in the case that $mathcal{C}$ is a (derived) category of modules? If two dg-categories are quasi-equivalent are their Hochschild cochain complexes quasi-isomorphic?

Is there a point of view that clarifies these issues?

oc.optimization control - modification of singlestart in global optimization

When minimizing a nonconvex function $f : Omega rightarrow mathbb{R}$ that may have multiple minima, there are some very simple strategies to improve the odds of finding the global minimum point. Singlestart scatters points $x_1,ldots,x_n$ in $Omega$ (deterministically or randomly, using rejection sampling if necessary), and starts some local minimization algorithm from a single point $x_k$ where $f(x_k) leq f(x_j)$ for $1 leq j leq n$. Multistart starts the local minimization algorithm from all the points $x_1,ldots,x_n$, and is obviously much more computationally intensive. One of the ways to reduce the computational load in multistart is to do just one iteration of the local minimization algorithm from each of the points $x_1,ldots,x_n$ and run a geometric clustering algorithm on the new collection of points, trying to identify clusters of points that belong to the same basin of attraction of a local minimum point, and saving computational effort by starting a local minimization from the center of mass of each cluster.

I now have a very specific question: Can anyone provide me with a reference for the variant (of singlestart or multistart, as one sees it) where one runs a single iteration of the local minimization algorithm from each of the points $x_1,ldots,x_n$, and then lets it run further on from that particular one of the $n$ new points where the function value is smallest? (If it helps, think of the local minimization algorithm as BFGS, with the first iteration a gradient search).

Note: I am not asking for advice on global optimization, either stochastic or deterministic. I don't need that, only an answer to a very specific query.

ag.algebraic geometry - extending local modules to global modules

Let $X$ be a scheme and $x in X$. Consider the functor

$text{Qcoh}(X) to mathcal{O}_{X,x} text{-Mod} , M mapsto M_x.$

Does it have a right-inverse? I.e. is there, for every $mathcal{O}_{X,x}$-module $N$ a (functorial) quasi-coherent $mathcal{O}_X$-module $M$ such that there is a natural isomorphism $M_x cong N$?

If $X$ is quasi-separated, the answer is yes. First observe that, if $X$ is affine, the direct image with respect to $text{Spec}(mathcal{O}_{X,x}) to X$ works. Now if $X$ is quasi-separated, use the affine case to extend $N$ to a quasi-coherent module on an open affine neighborhood $U$ of $x$, and then take the direct image with respect to $U to X$. This works since $U to X$ is a quasi-compact, quasi-separated morphism.

In the general case, note that direct images don't work, but this does not disprove the existence of the functor I'm looking for. The question is motivated by this one, which is still unsolved.

If $mathfrak{m}_x subseteq text{rad}(text{Ann}(N))$, then the direct image with respect to $text{Spec}(mathcal{O}_{X,x}/text{Ann}(N)) to X$ (this is then an affine morphism!) works.

EDIT: A stronger, but more natural question is the following: Let $U subseteq X$ an open subset. Does then $res : text{Qcoh}(X) to text{Qcoh}(U)$ have a right inverse? As I said, this is clear if $U to X$ is a quasi-compact morphism. In general, a transfinite recursion on the length of an affine cover shows that it is enough to consider the case that $X$ is affine, but $U subseteq X$ arbitrary. Then everything is ok when $U$ is quasi-compact. In general, you can write $U$ as a directed union of quasi-compact subsets of $X$. Does this help somehow?

EDIT 2: There is a right adjoint $text{Qcoh}(U) to text{Qcoh}(X)$ to the restriction functor due to abstract reasons. If $X$ is affine, it maps $N$ to the module associated to $Gamma(U,N)$, where the latter is considered as a $Gamma(X,mathcal{O}_X)$-module. However, this fails to be an extension of $N$, i.e. the counit $widetilde{Gamma(U,N)}|_U to N$ is no isomorphism in general (I have an explicit counterexample). Thus, the desired right-inverse (if it exists) won't be a right adjoint.

EDIT 3: Here is a class of examples where extension works. Assume $X$ is affine and $U subseteq X$ open can be written as $coprod_{i in I} U_i$ with $U_i$ affine. If $M in text{Qcoh}(U)$ and $M_i := Gamma(U_i,M)$, then $widetilde{Gamma(U,M)} = widetilde{prod_{i in I} M_i} in text{Qcoh}(X)$ is not an extension of $M$, but $widetilde{bigoplus_{i in I} M_i}$ works.

EDIT 4: Let $U,X,M$ as in edit 3. Then an application of Zorn's lemma shows that $M$ can be extended to a maximal open subset $U subseteq V subseteq X$. Then for every open affine $W subseteq X$, either $V cap W = W$ or $V cap W$ is not quasi-compact. In particular, $V$ is ("very") dense. For example, $mathbb{A}^{infty} - {0} subseteq mathbb{A}^{infty}$ is such a dense subset. But I don't know if here extension works. I've already looked at several examples, but have not found out anything ..

EDIT 5: If $dim(X)=0$, then extension works.

Please let me know if you have any ideas!

lo.logic - Models for the given FOL statement

Consider the following FOL sentence:

$phi = exists x forall y exists z ((x=y) lor (P(x,y,z) land lnot P(y,x,z) ) $

It can be proven that for any natural number n > 0 there exits a model of size n for the above sentence. (Please correct me here if I am wrong. This should be provable using induction.).

Now imagine a FOL sentence that does not use = (and similar) predicate. And if such a sentence has a model of size n can I claim that the sentence will essentially have a model of size n+1 ?

ct.category theory - A rigid type of structure that can be put on every set?

This doesn't completely answer the question, but I think it's relevant.

Theorem: Let T and W be theories in higher-order logic (by which I mean the internal type theory associated to elementary topoi), where W has a specified underlying object X (i.e. we regard a model of W as an object X equipped with some additional stuff). Then it is not the case that both (1) T proves that W is rigid (as structure on X) and (2) in any topos satisfying T, every object can be equipped with W-structure.

Proof: Suppose that both the given conditions hold. Let C[T,X] be the free topos on the theory T and an additional object X, and let C[T,W] be the free topos on T and W. (Recall that for any theory S and any topos E, the category Log(C[S],E) of logical functors and natural isomorphisms from C[S] to E is equivalent to the category of models of S and their isomorphisms in E.) Now the generic model of W in C[T,W] has an underlying object, giving a logical functor C[T,X]→C[T,W]. And C[T,X] satisfies T, so by assumption, its generic object X can be equipped with W-structure; thus we also have a logical functor C[T,W]→C[T,X], and the composite C[T,X]→C[T,W]→C[T,X] is isomorphic to the identity. In other words, C[T,X] is a pseudo-retract of C[T,W]. Now let E be any other topos satisfying T and Y any object of E admitting a nonidentity automorphism (such as Y=1+1); then we have a logical functor C[T,X]→E sending X to Y, which in turn has a nonidentity automorphism. But because C[T,X]→C[T,W]→C[T,X] is the identity, this functor C[T,X]→E must factor through C[T,W], and since T proves that W is rigid, any automorphism of this functor must be the identity, a contradiction. ∎

This means that if you want a rigid type of structure that can be put on every set, you need to use more about sets than the fact that they form an elementary topos, or even a Boolean topos with a NNO, or any additional property of Set that can be expressed as a theory T in HOL. Note that AC, although it can be phrased as a "categorical" property not referring directly to ∈ (every surjection splits), cannot be expressed as a theory in HOL since it involves a quantification over all sets. Likewise for the "topos-theoretic axiom of foundation" that every set injects into some well-founded extensional relation. So the question is, what can we do with the remaining non-HOL axioms of ZF, i.e. basically replacement and (its consequence) unbounded separation.

algebraic groups - Iwasawa and Cartan Decompositions.

I think the key point is the proposition 4.4.2, where "good" subgroups are caracterised geometrically as stabilisers of special subgroups (ie, stabilisers of a point o such that the Weyl group W is the semidirect product of its translations and of the stabiliser of o in W).

Then the group G is the product of B (the stabiliser of a class of sector, a minimal parabolic group for an algebraic group) and the group K. Moreover, the group B itself is the product of B^0 (which is the union of pointwise fixators of sectors) and the group of translations (acting on some apartment containing o and a sector in this class).

The Cartan decomposition is, as usual, the decomposition of an element g in kvk', where k and k' are element of K and v is an element which sends o to a vertice of the sector starting at o in the class defined by B.

The proposition 4.4.4 is meant to explain the relation between the two decompositions (ie, when you know the translation part in the Iwasawa decomposition, can you deduce it in the Cartan decomposition ?)

If you know how to attach a building to a reductive group, then the book "Buildings" by Abramenko and Brown is a good reference (see chap. 11), much easier to read. They treat every building, but construct only the affine building associated to SL(n). Another reference is the small book of Macdonald, "Spherical functions on a group of p-adic type" (chapter II, Theorem 2.6.11)