big list - Undergraduate Level Math Books

What are some good undergraduate level books, particularly good introductions to (Real and Complex) Analysis, Linear Algebra, Algebra or Differential/Integral Equations (but books in any undergraduate level topic would also be much appreciated)?

EDIT: More topics (Affine, Euclidian, Hyperbolic, Descriptive & Diferential Geometry, Probability and Statistics, Numerical Mathematics, Distributions and Partial Equations, Topology, Algebraic Topology, Mathematical Logic etc)

Please post only one book per answer so that people can easily vote the books up/down and we get a nice sorted list. If possible post a link to the book itself (if it is freely available online) or to its amazon or google books page.

ag.algebraic geometry - Quasi-separatedness for Algebraic Spaces

One can certainly make the basic definitions, and the real issue is to show that the definition "works" using any etale map from a scheme. More precisely, the real work is to show that a weaker definition actually gives a good notion: rather than assume representability of the diagonal, it suffices that $R := U times_X U$ is a scheme for some scheme $U$ equipped with an etale representable map $U rightarrow X$. Or put in other terms, we have to show that if $U$ is any scheme and $R subset U times U$ is an 'etale subsheaf which is an etale equivalence relation then the quotient sheaf $U/R$ for the big etale site actually has diagonal representable in schemes. Indeed, sometimes we want to construct an algebraic space as simply a $U/R$, so we don't want to have to check "by hand" the representability of the diagonal each time.

That being done, then the question is: which objects give rise to a theory with nice theorems? For example, can we always define an associated topological space whose generic points and so forth give good notions of connectedness, open behavior with respect to fppf maps, etc.? (The definition of "point" needs to be modified from what Knutson does, though equivalent to his definition in the q-s case.) The truth is that once the theory is shown to "make sense" without q-s, it turns out that to prove interesting results one has to assume something extra, the simplest version being the following weaker version of q-s: $X$ is "Zariski-locally q-s" in the sense that $X$ is covered by "open subspaces" which are themselves q-s. This is satisfied for all schemes, which is nice. (There are other variants as well.)

In the stacks project of deJong, as well as the appendix to my paper with Lieblich and Olsson on Nagata compactification for algebraic spaces, some of the weird surprises coming out of the general case (allowing objects not Zariski-locally q-s) are presented. (In that appendix we also explain why the weaker definition given above actually implies the stronger definition as in Chris' answer. This was surely known to certain experts for a long time.)

riemannian geometry - Determinant of a metric?

This is too long for a comment but still too short for an introductory course that you are asking for.

A Riemannian metric in the plane is (represented by) a matrix-valued function such that the value at every point $p$ is a symmetric matrix $g=g(p)$ of the form $g=begin{pmatrix} E & F \ F & Gend{pmatrix}$ which is positive definite as a quadratic form, that is, $E,G>0$ and $det g >0$. Any matrix-valued function satisfying these properties is (represents) a Riemannian metric, by definition.

There are many examples. Usually introductions begin with metrics defined by parametric surfaces (that $r_u$ and $r_v$ stuff). This is only an example, one of the many, and it is irrelevant in the context of the paper. The paper considers Riemannian metrics not associated to any surface.

Let me try to explain what it is about. The above matrix $g$ defines a norm on $mathbb R^2$ as follows: $|(u,v)|=sqrt{Eu^2+2Fuv+Gv^2}$. This norm defines a metric $d$ by $d(x,y)=|x-y|$. This is a Riemannian metric associated with a constant metric tensor $g$. One can prove that this metric space is isometric to the standard Euclidean plane, and an isometry is given by a linear map (which can be written explicitly in terms of $E$, $F$ and $G$). So a constant metric tensor essentially produces a Euclidean metric written in some non-orthogonal coordinates.

What I said above is a reformulation of some bits from linear algebra. Riemannian geometry begins when $g$ is not constant. Then there is not a norm but a family of norms $|cdot|_p$, $pin U$, where $Usubsetmathbb R^2$ is the domain where $g$ is defined. Every norm $|cdot|_p$ yields a metric $d_p$ on its own private copy of $mathbb R^2$ (this private copy is called the tangent space at $p$ and is usually denoted by $T_pU$).

This family of metrics is "glued together" into one metric $d$ on $U$. It can be defined as the maximal metric satisfying the following condition: for every $pin U$, one has
$$
frac{d(x,y)}{d_p(x,y)} to 1 text{as} x,yto p .
$$
So, locally near a point $p$ the metric is approximately the same as the (essentially Euclidean) metric $d_p$ defined by the matrix at $p$. This is sufficient for any first-order analysis.

The standard definition involves defining a length of a curve with respect to $g$ (integrate the length of the velocity vector, computed in that variable norm), and then defining the distance between points as the infimum of length of connecting curves. It is equivalent to the one I gave above.

Integer matrices with no integer eigenvalues

I just found this problem. If you try the matrix $A^nB^m$, then your question for such matrices is equivalent to this number theory question: Can
$9^n+2cdot 9^ncdot 2^m-12cdot 3^ncdot 2^m+2cdot 3^n+4^{m}cdot 9^n+4^{m}+2cdot 2^m+9$
be a square provided $m,nne 0$. Note that if we denote $3^n$ by $x$, $2^m$ by $y$, we get a quartic polynomial in $x,y$. I hope number theorists here can say something about this exponential Diophantine equation.

The answer to problem with question mark is "obviously NO". To be undecidable, you should have a mass problem. For given $A,B$, you have the following problem:
given a product $W(A,B)$ is it true that the matrix has an integer eigenvalue. That problem is obviously decidable. The question of whether this is true for every word $W$ requires answer "yes" or "no" and is not a mass problem. You can still ask whether it is independent from ZF or even ZFC (or unprovable in the Peano arithmetic). What Bjorn had in mind is a completely different and much harder problem when you include $A, B$ in the input and ask if for this $A$, $B$ some product $W(A,B)$ not of the form $A^n, B^m$ has an integer eigenvalue. This is a mass problem which could be undecidable (although he, of course, did not prove it). But this has nothing to do with the original question.

nt.number theory - Chebyshev's approach to the distribution of primes

This is motivated by a recent question by Wadim.

The negative answer should be known, since t is very natural, in this case I would be happy to see any reference.

May Pafnuty Lvovich Chebyshev's approach to distribution of primes lead to PNT itself, if we replace $frac{(30 n)! n!}{(15 n)! (10 n)! (6 n)!}$ to other integer ratios of factorials? If not, what are the best constants in asymptotic relation
$$
c_1 frac{n}{log n}< pi(n)< c_2 frac{n}{log n}
$$
which may be obtained on this way?

derived functors - Is there a good computer package for working with complexes over non-commutative rings?

I don't know whether Magma can handle all you ask for, but if I remember my coding for Magma correctly, at least the projective resolutions of modules over a non-commutative ring should be covered by that - for nice enough non-commutative rings. It's all been developed there as part of Jon F. Carlson's work on computing group cohomology rings.

If there is a system that does all you ask for, and does it efficiently, it is probably been written in connection to a group cohomology computation effort - which narrows the candidates down significantly: Magma and GAP do group cohomology rings, and SAGE now with the work of Simon King and David Green.

In contrast, I'm reasonably certain that Macaulay only does commutative things, and Singular doesn't have resolutions as a naturally occuring object at all.

Bergman might be able to deal with what you ask for, though.

To conclude: I'd recommend you to take a look at the homological algebra modules in Magma, GAP, SAGE and Bergman - I'd be highly surprised to see any other packages deal with the case you describe, and I'm not entirely convinced either of these do it well either.

qa.quantum algebra - Does some version of U_q(gl(1|1)) have a basis like Lusztig's basis for dot{U(sl_2)}?

There's a non-unital algebra $dot{U}$ formed from $U_q (sl_2)$ by including a system of mutually orthogonal idempotents $1_n$, indexed by the weight lattice. You can think of this as a category with objects $mathbb{Z}$ if you prefer.

Lusztig's basis $mathbb{dot{B}}$ for $dot{U}$ has nice positivity properties: structure coefficients are in $mathbb{Z}[q,q^{-1}]$.

Has anyone tried to write down a similar type of basis for the algebra associated to $U_q (gl_{1|1})$?

ct.category theory - Is there a free digraph associated to a graph?

A little bit of background: A graph G is, of course, a set of vertices V(G) and a multiset of edges, which are unordered pairs of (not necessarily distinct) vertices. We say that two vertices v_1, v_2 are adjacent if {v_1, v_2} is an edge. A directed graph, or digraph is essentially the same thing, except that the edges are now ordered pairs. Digraphs have a rather nice categorical interpretation.

A graph homomorphism is exactly what it should be, categorically, if you think of graphs as "sets with an adjacency structure." It's a map f: V(G) rightarrow V(H) is a homomorphism if v_1, v_2 in V(G) adjacent implies f(v_1), f(v_2) adjacent. The notion of homomorphism for directed graphs is essentially the same; if there's an edge from v_1 to v_2, then there's an edge from f(v_1) to f(v_2). Taking these definitions as morphisms, we can define categories of graphs and of digraphs.

Oftentimes in graph theory (particularly when linear algebra methods come into play), it's easier to work with a digraph than a graph, and so we usually orient the edges arbitrarily. But this isn't really natural...

There's a forgetful functor from the category of digraphs to the category of graphs. Does this functor have an adjoint? (I forget which is left and which is right.) Now that I think about it, is the obvious thing (replace each edge by a pair of directed edges, one in each direction) an adjoint, and if so is there a way to fudge the categories so that simple graphs are taken to simple digraphs?

at.algebraic topology - Representations of pi_1, G-bundles, Classifying Spaces

This question is inspired by a statement of Atiyah's in "Geometry and Physics of Knots" on page 24 (chapter 3 - Non-abelian moduli spaces).

Here he says that for a Riemann surface $Sigma$ the first cohomology $H^1(Sigma,U(1))$, where $U(1)$ is just complex numbers of norm 1, parametrizes homomorphisms $$pi_{1}(Sigma)to U(1).$$

This is fine by me, after all by Brown Representability we know $$H^1(Sigma,G)cong [Sigma,BG]=[Bpi_{1}Sigma,BG]$$ since we know that Riemann surfaces are $K(pi_{1},1)$s. We then use the handy fact from Hatcher Prop. 1B.9 (pg 90) that shows that...

For $X$ a connected CW complex and $Y$ a $K(G,1)$ every homomorphism $pi_1(X,x_0)topi_1(Y,y_0)$ is induced by a map $(X,x_0)to(Y,y_0)$ that is unique up to homotopy fixing $x_0$.

So group homomorphisms $pi_{1}(Sigma)to U(1)$ correspond on the nose with first cohomology of the $Sigma$ with coefficients in $U(1)$.

EDIT: To be accurate the Hatcher result shows we have an injection of group homomorphisms into homotopy classes of maps. Does anyone know if every homotopy class of maps is realized by a group homomorphism?

What bothers me is what comes next. Now replace $U(1)$ with $G$ - any compact simply connected Lie group, take $G=SU(n)$ for example. Now Atiyah claims that $H^1(Sigma,G)$ parametrizes conjugacy classes of homomorphisms $pi_{1}(Sigma)to G$.

Now if the fundamental group or the Lie group were abelian this would be the same statement, but higher genus Riemann surfaces (genus greater than 1) have non-abelian fundamental groups and Atiyah is looking specifically at non-abelian $G$. Also, it seems that the statement of Brown Representability requires abelian coefficient groups, so I am stuck.

Does anyone know a clean way of proving Atiyah's claim?

EDIT2: I renamed the question to draw in the "right" people. I think the answer has to do with the fact that principal G-bundles over a Riemann surface are determined by maps of $pi_1(Sigma)to G$ (can someone explain why?). This is related to local systems and/or flat connections, which I don't understand well. Thanks!

nt.number theory - Weil group, Weil-Deligne group scheme and conjectural Langlands group

Regarding (1), from the point of view of Galois representations, the point is that continuous Weil group representations on a complex vector space, by their nature,
have finite image on inertia.

On the other hand, while a continuous $ell$-adic Galois representation of $G_{mathbb Q_p}$ (with $ell neq p$ of course) must have finite image on wild inertia, it can have infinite image on tame inertia. The formalism
of Weil--Deligne representations extracts out this possibly infinite image, and encodes it as a nilpotent operator (something that is algebraic, and doesn't refer to the $ell$-adic topology,
and hence has a chance to be independent of $ell$).

As for (2): Representations of the Weil group are essentially the same thing as representations
of $G_{mathbb Q}$ which, when restricted to some open subgroup, become abelian. Thus
(as one example) if $E$ is an elliptic curve over $mathbb Q$ that is not CM, its $ell$-adic Tate module cannot be explained by a representation of the Weil group (or any simple modification thereof). Thus neither can the weight 2 modular form to which it corresponds.

In summary: the difference between the global and local situations is that an $ell$-adic representation of $G_{mathbb Q_p}$ (or of $G_E$ for any $p$-adic local field) becomes, after
a finite base-change to kill off the action of wild inertia, a tamely ramified representation,
which can then be described by two matrices, the image of a lift of Frobenius and the image of a generator of tame inertia, satisfying a simple commutation relation.

On the other hand, global Galois representations arising from $ell$-adic cohomology of varieties over number fields are much more profoundly non-abelian.

Added: Let me also address the question about a product of $W_{F_v}'$. Again, it is simplest to think in terms of Galois representations (which roughly correspond to motives,
which, one hopes, roughly correspond to automorphic forms).

So one can reinterpret the question as asking: is giving a representation of $G_F$ (for a number field $F$) the same as giving representations of each $G_{F_v}$ (as $v$ ranges over the places of $F$). Certainly, by Cebotarev, the restriction of the global representation
to the local Galois groups will determine it; but it will overdetermine it; so giving a collection of local representations, it is unlikely that they will combine into a global one. ($G_F$ is very far from being the free product of the $G_{F_v}$, as Cebotarev shows.)

To say something on the automorphic side, imagine writing down a random degree 2 Euler product. You can match this with a formal $q$-expansion, which will be a Hecke eigenform, by taking Mellin transforms,
and with a representation of $GL_2(mathbb A_F)$, by writing down a corresponding tensor product of unramified representations of the various $G_{F_v}$. But what chance is there
that this object is an automorphic representation? What chance is there that your random formal Hecke eigenform is actually a modular form? What chance is there that your random Euler product is actually an automorphic $L$-function? Basically none.

You have left out some vital global glue, the same glue which describes the interrelations of all the $G_{F_v}$ inside $G_F$. Teasing out the nature of this glue is at the heart of proving the conjectured relationship between automorphic forms and motives; its mysterious nature is what makes the theories of automorphic forms, and of Galois representations, so challenging.

dg.differential geometry - Why is cotangent more canonical than tangent?

Neither is more canonical than the other. The tangent bundle of $M$ represents the set of all possible derivatives of maps $R rightarrow M$, and the cotangent bundle of $M$ represents the set of all possible derivatives of maps $M rightarrow R$. They are dual to each other.

I hate to ruin such a nice terse answer, but I might as well describe how I think of the tangent and cotangent bundles. I have a personal prejudice for using only freshman calculus and basic linear algebra as much as possible and avoiding multivariable calculus. So here's the way I see things:

The idea is to build everything using only linear algebra and the definition of the derivative of a real-valued function of one real variable.

So for me you have to first define the tangent bundle as the set of all possible velocity vectors of parameterized curves in the given manifold. The first observation is that if you fix a point in the manifold, the set of all possible velocity vectors based at that point has a natural vector space structure.

Next, given a real-valued function on a manifold, you want to define its derivative. Well, if all you have is the 1-variable derivative, then the only thing you can do is to compose the function with a parameterized curve. Then you observe the following: The value of the derivative at a point actually depends only on the velocity vector of the curve at that point and is a linear function of the velocity vector. Therefore, the set of all possible derivatives of a real-valued function is naturally dual to the tangent bundle (viewed as the set of all possible velocity vectors). That's the cotangent bundle (the set of all possible derivatives of real-valued functions on the manifold).

This for me is a nice coherent story that I can tell (and remember) without using any mathematical symbols at all but also one whose details can be fleshed out in a straightforward manner.

linear algebra - explicit big linearly independent sets

Here is a linearly independent subset of $mathbb{R}$ with size $2^{aleph_0}$.

Let $q_0, q_1, ldots$ be an enumeration of $mathbb{Q}$. For every real number $r$, let
$$T_r = sum_{q_n < r} frac{1}{n!}$$
The proof that these numbers are linearly independent is similar to the usual proof that $e$ is irrational. (It's a cute problem; there's spoiler below.)

I think a similar trick might work for algebraic independence, but I don't recall having seen such a construction. Actually, John von Neumann showed that the numbers
$$A_r = sum_{n=0}^infty frac{2^{2^{[nr]}}}{2^{2^{n^2}}}$$
are algebraically independent for $r > 0$. [Ein System algebraisch unabhängiger zahlen, Math. Ann. 99 (1928), no. 1, 134–141.] A more general result due to Jan Mycielski seems to go through in ZF + DC perhaps just ZF in some cases. [Independent sets in topological algebras, Fund. Math. 55 (1964), 139–147.]

As for subspaces and subfields isomorphic to $mathbb{R}$, the answer is no. (Since I'm not allowed to post any logic here, I'll refer you to this answer and let you figure it out.)

Well, I'll bend the rules a little... Consider a $mathbb{Q}$-linear isomorphism $h:mathbb{R}to H$, where $H$ is a $mathbb{Q}$-linear subspace of $mathbb{R}$ (i.e. $h$ is an additive group isomorphism onto the divisible subgroup $H$ of $mathbb{R}$). If $h$ Baire measurable then it must be continuous by an ancient theorem of Banach and Pettis. It follows that $h(x) = xh(1)$ for all $x in mathbb{R}$ and therefore $H = mathbb{R}$. Shelah has produced a model of ZF + DC where all sets of reals have the Baire property, so any such $h$ in this model must be Baire measurable. A similar argument works if Baire measurable is replaced by Lebesgue measurable, but Solovay's model of ZF + DC where all sets of reals are Lebesgue measurable uses the existence of an inaccessible cardinal, and this hypothesis was shown necessary by Shelah.

---

Spoiler

Suppose for the sake of contradiction that $r_1 > r_2 > cdots > r_k$ and $a_1,a_2,ldots,a_k in mathbb{Z}$ are such that $a_1T_{r_1} + a_2T_{r_2} + cdots + a_kT_{r_k} = 0$. Choose a very large $n$ such that $r_1 > q_n > r_2$. If $n$ is large enough that
$$(|a_1| + |a_2| + cdots + |a_k|) sum_{m=n+1}^infty frac{n!}{m!} < 1$$
then the tail terms of $n!(a_1T_{r_1}+cdots+a_kT_{r_k}) = 0$ must cancel out, and we're left with
$$a_1 = -sum_{m=0}^{n-1} sum_{q_m < r_i} a_i frac{n!}{m!} equiv 0 pmod{n}$$
If moreover $n > |a_1|$, this means that $a_1 = 0$. Repeat to conclude that $a_1 = a_2 = cdots a_k = 0$.

nt.number theory - what is an Euler system and the motivation for it?

My understanding is that they're named "Euler systems" because that "Frobenius acting on T" in the definition (line 4, p. 22 of Rubin's book) is an "Euler factor" as in Euler's product decomposition of the Riemann zeta function.

The two easiest examples of Euler systems are the so-called cyclotomic units (not the roots of unity, but slightly more complicated, but still classical, beasts built out of them) and the elliptic units (built out of torsion points on CM elliptic curves). Not coincidentally, these are related to the only two types of global fields that we know how to explicitly construct abelian extensions of. Then there is Kato's more complicated Euler system of Heegner points [EDIT - This phrase was wrong- please see post below!], and Kolyvagin's Euler system of Stickelberger elements. All these are described in Rubin's book, but if you haven't seen them before, it might help to have more references.

If group cohomology is still new to you, the cyclotomic units are the best Euler systems to start with, since you don't need Galois cohomology to define them. (Norm-coherent units map to corestriction-coherent cohomology classes under the Kummer map, which is why these global units form an Euler system in the sense of Rubin's book). Rubin's appendix in Lang's republished books Cyclotomic Fields I and II is easier reading for this. Rubin's Inventiones paper on the main conjecture for CM elliptic curves also contains a nice introduction to the technique.

The application of Euler systems to number theory is the following: Euler systems allow us to bound Selmer groups of p-adic Galois representations. These generalize the Selmer group attached to an abelian variety, the ideal class group, and other objects of arithmetic interest. Bounding them is good because it allows us to prove Iwasawa Main Conjectures, which link the behavior of Selmer groups to p-adic L-functions and encompass basically every classical arithmetic tool for computing p-parts of special values of L-functions.

Washington's book on cyclotomic fields explains this in the cyclotomic example, and the spirit and flavor of the general theory is the same. Coates and Sujatha's book Cyclotomic Fields and Zeta Values is also an excellent introduction to the Euler system technique in the cyclotomic setting.

noncommutative algebra - Semiprime (but not prime) ring whose center is a domain

A whole class of examples of this kind can be obtained from prime ideals in enveloping algebras with the same central character. I will sketch the construction in the case of primitive ideals in simple Lie algebras, but these conditions can be considerably relaxed.

Let $mathfrak{g}$ be a complex simple Lie algebra of rank at least $2$ (i.e. not $mathfrak{sl}_2$), $U(mathfrak{g})$ its universal enveloping algebra, $I_1, I_2$ two incomparable primitive ideals with the same infinitesimal character, and $I=I_1cap I_2$ their intersection. Then $A=U(mathfrak{g})/I$ is semiprimitive, and hence semiprime. By the assumption, $I_1$ and $I_2$ intersect $Z(mathfrak{g})$ at the same maximial ideal, so $Z(A)=mathbb{C},$ which is a domain. To get a larger center, you can repeat this construction with incomparable prime ideals whose intersection with $Z(mathfrak{g})$ is the same non-maximal prime ideal of the latter ring.

---

If you know representation theory of simple Lie algebras, here is an explicit construction of a pair of ideals with these properties: let $lambda$ be an integral dominant weight, choose two different simple reflections $s_i, i=1, 2$ in the Weyl group, and let $I_i=text{Ann} L(s_i*lambda)$ be the annihilator of the simple highest weight module with highest weight $s_i(lambda+rho)-rho.$ The ideals $I_1$ and $I_2$ have the same infinitesimal character by the Harish-Chandra isomorphism and they are incomparable by the theory of $tau$-invariant: $tau(I_i)={s_i}$, but $tau$-invariant is compatible with the containment of primitive ideals.

Everything except for the $tau$-invariant is explained in Dixmier's "Enveloping algebras", and you can find the rest in Borho–Jantzen's or Vogan's old papers (you need the main property of the $tau$-invariant stated above) or read Jantzen's book about the enveloping algebras (in German) for the whole story.

rt.representation theory - Symmetric tensor products of irreducible representations

Here's a very special case for $mathfrak{gl}_n$ in characteristic 0 (which I have found useful in my work). Let $V$ be the vector representation, and for a partition $lambda$ with at most $n$ parts, let ${bf S}_{lambda}(V)$ denote the corresponding highest weight representation. Then $Sym^n(Sym^2 V) = bigoplus_{lambda} {bf S}_{lambda}(V)$ where the direct sum is over all partitions $lambda$ of size $2n$ with at most $n$ parts such that each part of $lambda$ is even. Similarly, $Sym^n(bigwedge^2 V) = bigoplus_{mu} {bf S}_{mu}(V)$ where the direct sum is over all partitions $mu$ of $2n$ with at most $n$ parts such that each part of the conjugate partition $mu'$ is even. If you want the corresponding result for $mathfrak{sl}_n$ we just introduce the equivalence relation $(lambda_1, dots, lambda_n) equiv (lambda_1 + r, dots, lambda_n + r)$ where $r$ is an arbitrary integer.

One reference for this is Proposition 2.3.8 of Weyman's book Cohomology of Vector Bundles and Syzygies (note that $L_lambda E$ in that book means a highest weight representation with highest weight $lambda'$ and not $lambda$).

Another reference is Example I.8.6 of Macdonald's Symmetric Functions and Hall Polynomials, second edition, which proves the corresponding character formulas.

gr.group theory - Nilpotent group with ascending and descending central series different?

Nobody seems to have answered the second query so far; one important class of groups in which the two series coincide is the class of $p$-groups of maximal class. A $p$-group $G$ of order $p^n$ is of maximal class if the nilpotency class of $G$ is $n-1$. The nonabelian groups of order $p^3$ are an example.

If $G$ is a $p$-group of maximal class, then the lower and upper central series coincide; this is essentially for the same reason as they do in the case of groups of order $p^3$, as Noah Snyder comments: there just isn't enough room for the series to differ.

If $G$ is of order $p^n$ and class $n-1$, then letting $G_2=[G,G]$ and $G_{i+1}=[G_i,G]$ (this is different from the way it is defined in the question as I write this; here, the group has class exactly $c$ if and only if $G_cneq 1$ and $G_{c+1}=1$), we have $|G_i:G_{i+1}|=p$ for $i=2,3,ldots,n-1$; similarly, $|Z_{j+1}(G):Z_j(G)| = p$ for $j=0,1,ldots,n-2$. Since $G_{n-1}subseteq Z_{1}(G)$ and both are of order $p$, they are equal; taking the quotient gives a group of maximal class and order $p^{n-1}$, and an inductive argument gives the equality among the rest of the terms.

Approximate unit for the algebra C*(h) consisting of projectors

No. In fact, K(E) need not even contain any nonzero projections. Take a (nontrivial) C*-algebra B with no nonzero projections¹ and take E=B as a right module over B with inner product 〈a,b〉=a*b. Then K(E)≅B, as mentioned in Example 13.2.4 (a) in Blackadar, and proved for instance as Proposition 2.2.2 (i) in Manuilov and Troitsky. (Note that in this case K(E) also has no nonzero idempotents.)

Edit: I removed an overly complicated comment on the Hilbert space case, forgetting to take into account that h is strictly positive, and in particular positive. I added a comment on trouble that may arise even in this case.

In the case when E is a Hilbert space over B=ℂ, taking into account the fact that h is self-adjoint, C*(h) is the C*-algebra generated by a self-adjoint compact operator, and therefore the spectral projections of h provide an approximate identity {u_n} consisting of increasing projections. Because h is strictly positive, its range is dense, so this will be a sequence of projections converging weakly to the identity operator. However, this approximate identity need not be quasicentral for A⊆B(E). E.g., suppose you have u_n equal to the projection onto the span of the first n elements of an orthonormal basis. If S is the unilateral shift with respect to that basis, then ||u_nS−Su_n|| = 1 for all n, so {u_n} is not quasicentral for C*(S). Pedersen uses the Hahn-Banach theorem and the axiom of choice to show the existence of a quasi-central approximate identity in the closed convex hull of {u_n}, but you typically will not be able to find one consisting of projections, even in the Hilbert space case.

¹ E.g., take B to be C₀(X) for some noncompact, locally compact, connected space X, or if you prefer simple algebras see Blackadar's 1980 paper.

pr.probability - Estimating the mean of a truncated gaussian curve

OK, let me fully address the question since there is no easy way out. The
normal approach is to maximize the "likelihood" of the data under the
parameter. The key question here is how to define likelihood for a
mixed distribution. Let's use the standard approach as our guide.

Parameter estimation is usually based on the idea that we want to
choose parameters that make our data "the most likely." For a discrete
probability distribution, we interpret this to mean that our data is
the most probable. But this breaks down in the case of continuous
probability distributions, where, no matter our choice of parameters,
our data has probability zero.

Statisticians thus replace the probability with the probability
density for continuous distributions. Here is the justification for
this. Instead of actually having a set of numbers drawn from the
probability distribution, you have a highly accurate
measurement---say, your sequence ${x_i}$ for $i = 1,dots,n$ tells
you that the true value of the (still unknown) sequence ${g_i}$ satisfies $|x_i -
g_i| < varepsilon$ for all $i$. When $varepsilon$ is sufficiently
small, the replacement
$$
mathbb{P}(|x_i - g_i|) < varepsilon )approx varepsilon p_{g}(x_i)
$$
is very accurate, where $p_g$ is the pdf of $g_i$. Assuming that
your sequence is iid, we are led to the approximation
$$
mathbb{P}(|x_i - g_i| < varepsilon text{ for all } i)
approx varepsilon^n prod_{i=1}^n p_g(x_i).
$$
We thus choose the pdf from our family which maximizes the right
hand side of the above equation, reproducing the standard maximum
likelihood method.

Now the question is, what do we do with mixed distributions? When
there is a mass at a point $x_i$, that is $mathbb{P}(x_i=g_i) > 0$,
our first approximation is incorrect; for very small $varepsilon$, we
have the approximation
$$ mathbb{P}(|x_i - g_i| < varepsilon) approx mathbb{P}(x_i = g_i)
$$
If we let $mathcal{N}$ be the index set of the "massless" samples, we can approximate
the probability of our data as
$$ mathbb{P}(|x_i - g_i| < varepsilon) approx varepsilon^n
prod_{i in mathcal{N}} p_g(x_i) prod_{i notin mathcal{N}} mathbb{P}(x_i = g_i).
$$
where $n$ is the number of elements in $mathcal{N}$. That is, we can reasonably define our maximum likelihood estimate
for a parameter $m$ as the value of the parameter that maximizes
$$
prod_{i in mathcal{N}} p_g(x_i) prod_{i notin mathcal{N}} mathbb{P}(x_i = g_i).
$$

In your case, it is fairly simple to write down the value of the likelihood function above. First, note that
$$mathbb{P}(x=0) = frac{1}{sqrt{2pi}} int_{-infty}^{-m}
e^{-x^2/2}dx.$$
For $x>0$, you have the standard Gaussian pdf
$p_g(x) = tfrac{1}{sqrt{2pi}} e^{-(x-m)^2/2}$.

I won't do any more here; suffice it to say that the standard approach
to maximizing the likelihood involves taking the logarithm of the likelihood function
and setting its derivative to zero. You will probably get a
transcendental equation that you will need to solve numerically.

examples - Combinatorial results without known combinatorial proofs

This is a very common theme in enumerative combinatorics. You can find a lot of examples with the Google search "no bijective proof" (with quotes).

First, I can say something about why you might care about bijective proofs. Combinatorial species are certainly a nice theory, but they are a fairly specific and elaborate answer related to generating functions. A more general reason is that a bijective proof categorifies an equality in combinatorics to the category of sets. In other words, it promotes an equality $|A| = |B|$ to an isomorphism $A cong B$. In my opinion, it is just as important to find any other categorification, for instance to the category of vector spaces. Instead of showing that two sets are the same size with a bijection, you would show that they are the same size using an invertible matrix.

Second, of the many examples, I can name one that I encountered. This example is interesting because the objects in question seem very similar. Recall that an alternating sign matrix is a matrix whose non-zero entries in each row and column alternate between $1$ and $-1$, and such that the first and last non-zero entry in each row and column is $1$. One interesting subclass is the ASMs of order $2n+1$ which are symmetric about a vertical line. Another interesting subclass is the ASMs of order $2n$ which are diagonally symmetric and have 0s on the diagonal. (ASMs of either type of the opposite parity do not exist.) The first class was discovered by David Robbins and I found the second class. I proved David's product formula for the first class and I established the same product formula for the second class. So these two classes of ASMs are equinumerous, but no bijective proof is known.

---

Here is another interesting example in the same vein. A cyclically symmetric, self-complementary plane partition (CSSCPP) is equivalent to a tiling of a regular hexagon of order $2n$ by unit lozenges, which is invariant under 60 degree rotation. Here a unit lozenge is two unit equilateral triangles stuck together. A totally symmetric, self-complementary plane partition (TSSCPP) is the same thing except with full dihedral symmetry. (I make the size even because otherwise there aren't any plane partitions with the imposed symmetry.) The formulas for both classes were also conjectured by David Robbins; George Andrews proved his conjecture for TSSCPPs and I proved the conjecture for CSSCPPs. In particular, the number CSSCPPs of a fixed size is the square of the number of TSSCPPs, but no one knows a good bijection.

The single most striking thing that David Robbins found was that the number of TSSCPPs, which are plane partitions with full symmetry, equals the number of ASMs with no imposed symmetry. No bijective proof of that is known either. On the positive side, Doron Zeilberger's proof of the ASM conjecture, and his later paper on refined ASMs, could be steps towards one because they equate certain generalizations and refined enumerations. However, alternating-sign matrices look totally different from plane partitions. In my opinion, the most frustrating case is when we can't even match like to like.

pr.probability - Distribution of 1-norm for Gaussian Unitary Ensemble

I'm not at all expert on random matrix stuff, but until someone more qualified pops up, would you be interested in some crude estimates on Z in the $n to infty$ asymptotic? Or do you really want something sharper in each dimension?

EDIT/UPDATE: OK, here's my hand-wavy argument,
it's been a while since I did any probability theory, so caveat lector and all that.

I'm going to use the GOE just because that's the one I know better and to save me worrying about stray scaling factors.

The idea is that for any $n times n$ matrices $S$ and $T$ we always have

$Vert SVert_1 Vert T Vert_{rm op} geq |{rm tr}(ST)|$

where the subscript 1 denotes Ky-Fan/Schatten 1-norm and the subscript "op" denotes usual operator norm. In particular, if $S=T$ is self-adjoint then

$Vert SVert_1 geq || S ||_2^2\, /\, || S ||_{rm op}$

Now when S is GOE(n,$sigma^2$) then $n^{-2} Vert SVert_2^2$ is strongly concentrated round its mean (which is $sigma^2$) -- it's the average of a bunch of independent random variables so we could use variance estimates and Chebyshev, or probably some stronger exponential tail estimates.

Also, when S is GOE(n,$sigma^2$) then $n^{-1/2} Vert SVert_{rm op}$ is strongly concentrated round $2sigma$ - one can get exponential tail estimates, at least for an upper bound of $(2+epsilon)sigma$ for any positive $epsilon$. I think this is folklore or a special case of Big Machinery, but as I said I have a more elementary proof, albeit one which is probably not original.

So, there is going to be a high probability (for $n$ large) that || S ||₂² is bigger than $(1-epsilon)sigma^2n^2$, and there is going to be a high probability (for $n$ large) that $Vert SVert_{rm op}$ is less than $(2+epsilon)sigma n^{1/2}$. On the intersection of these two events you're going to find that

$Vert SVert_1 geq (1-epsilon)n^2sigma^2 / (2+epsilon)sigma n^{1/2}$

which gives the lower bound I was claiming.

pr.probability - 'Focusing' the mass of the Probability Density Function for a Random Walk

Consider a random walk on a two-dimensional surface with circular reflecting boundary conditions (say, of radius 'R'). Here, for a fixed-size area, one finds a larger fraction of the probability density (for the position of the walker) near the midpoint of the circle than near its contour.

Given this example, my question is - for a discrete/continuous random walk in a two-dimensional (or higher dimensional) space, now with arbitrary reflecting boundary conditions, how 'well' can one restrict/focus the mass of the probability density function to the smallest possible area relative to the total surface area available to the walker?

In other words, how effectively can one construct a 'trap' (I'm using this term very loosely) for such a walker, given random initial conditions?

(I obviously welcome any help to ask this question in a more appropriate manner.)

linear algebra - How do you construct a symplectic basis on a lattice?

Here is an algorithm, it may not be a good one. I will only explain how to find a basis $e_i$, $f_i$ such that $langle e_i, e_j rangle = langle f_i, f_j rangle =0$ and $langle e_i, f_j rangle = c_i delta_{ij}$ for some constants $c_i$. I will punt on explaining how to make sure that $c_1$ divides $c_2$ which divides $c_3$ and so forth. This presentation is closely based on the algorithm in Wikipedia for computing Smith normal form.

Find $e$ and $f$ so that $langle e,f rangle neq 0$ (EDIT) and such that the lattice spanned by $e$ and $f$ is the intersection of the whole lattice with the vector space spanned by $e$ and $f$.

Set $d := langle e,f rangle$. Complete $(e,f)$ to a basis $(e,f,g_1, g_2, ldots, g_{2n})$ of our lattice.

Case 1: We have $langle e,g_i rangle = langle f, g_i rangle =0$ for all $i$. Take $e_1=e$, $f_1=f$ and apply our algorithm recursively to the sublattice spanned by the $g_i$.

Case 2: For all $i$, the integer $d$ divides $langle e,g_i rangle$ and $langle f, g_i rangle =0$. Replace $g_i$ by
$$g_i - frac{1}{d}langle g_i, f rangle e- frac{1}{d}langle e, g_i rangle f.$$
We have now reduced to Case 1.

Case 3: There is some $g_i$ so that $k:=langle e, g_i rangle$ is not divisible by $d$. Then, for some $q$, we have $0 < k-qd < d$. Set $f'=g_i-kf$ and $g'_i=f$. Then $(e,f',g_1,g_2,ldots, g'_i, ldots, g_n)$ is a basis, and $langle e, f' rangle$ is less than $d$. Return to the beginning with this new basis.

Case 4: There is some $g_i$ so that $k:=langle f, g_i rangle$ is not divisible by $d$. Just like Case 3, with the roles of $e$ and $f$ switched.

Since $d$ decreases at every step, eventually we will hit Case 1 and be able to reduce the dimension.

algebraic number theory - The field generated by radii of an ellipse

This is a follow up to a question that I posed a few days ago here:
The product of n radii in an ellipse

Suppose we have an ellipse $x^2/a^2 + y^2/b^2 = 1$ (centered at the
origin). Let $n>4$. There are $n$ rays going out of the origin, at angles
$0, 2pi/n, 4pi/n, 6pi/n,...,2pi(n-1)/n$. Let $(x_0,y_0),...,(x_{n-1},y_{n-1})$ be
the points of intersection of the rays and the ellipse. The product
from $k=0$ to $n-1$ of ${x_k}^2 + {y_k}^2$ is equal to one. Can $a$ and $b$ be
rational if $a neq b$?

It was discovered here that the answer is no, because Fermat's Last Theorem is true. Notice that the points of intersection of the rays and the ellipse, $(x_k,y_k)=x_k+{y_k}i$, generate a subfield of the complex numbers, since the ellipse is symmetric about the real line and the product of the points is one and the sum of the points is zero. (If one takes the set of all elements that can be expressed as a combination of additions and multiplications of the points of intersection of the rays and the ellipse, this set will be a subfield of the complex numbers, since zero and one are in this set.)

Conjecture: If $a,b$ are rational and $a neq b$, the set of all complex numbers that can be expressed as a combination of additions and multiplications of the points of intersection of the rays and the ellipse, $(x_k,y_k)=x_k+{y_k}i$, cannot be a subfield of the complex numbers.

Prove this conjecture.

Craig

ag.algebraic geometry - Examples for Decomposition Theorem

I can think of several additions to your list which don't seem to be represented yet.

1. Semismall resolutions

This first example is rather general, but afterward I will discuss how it is used in Springer theory.

First, suppose that $f:X to Y$ is a proper map of stratified irreducible complex algebraic varieties with $X$ rationally smooth such that, if $Y = cup Y_n$ is the stratification of $Y,$ the restriction of $f$ to $f^{-1}(Y_n) to Y_n$ is topologically locally trivial (there's a theorem (not sure who it's by) that says we can always find a stratification such that this condition holds). Furthermore, we say that $f$ is semi-small if for each stratum $Y_n,$the dimension of the fiber of $f^{-1}(Y_n) to Y_n$ is less than or equal to the half of codimension of $Y_n$ inside $Y.$ This condition is important largely because of the following theorem:

Fact. The pushforward of the constant perverse sheaf under a semismall map is still perverse.

Furthermore, we say that a stratum $Y_n$ is relevant whenever equality holds above, i.e., twice the fiber dimension is equal to the codimension. These will be important soon, as they will be the subvarieties appearing in the decomposition theorem.

By the assumptions we made on $f:X to Y,$ we have a monodromy action of $pi_1(Y_n)$ on the top dimensional cohomology group of the fiber of $f^{-1}(Y_n) to Y_n.$ This corresponds to a local system $L_{Y_n},$ which we can decompose into irreducible components: $L_{Y_n} = oplus L_{rho}^{d_{rho}}$ where $rho$ runs over the set of irreducible representations of $pi_1(Y_n)$ and $d_{rho}$ are non-negative integers. We then say that a pair $(Y_n, rho)$ is relevant iff $Y_n$ is a relevant stratum and $d_{rho} neq 0$ (i.e., $rho$ appears in the decomposition of the representation of $pi_1(Y_n)$).

Now we can finally state a theorem, which I believe is due to Borho and Macpherson, but perhaps others deserve credit as well. Keep the initial assumptions on $f:X to Y,$ but now assume in addition that $X$ is smooth. Then a little work plus the decomposition theorem establish the following.

Theorem. $f_{ast}IC_X = oplus IC_{Z_n}(L_{rho})^{d_{rho}}$ where $Z_n$ is the closure of $Y_n$ and the sum ranges over all relevant pairs $(Y_n, rho).$

This theorem is used in Springer theory (and perhaps other places as well). In this case, we want $f:X to Y$ to be the Springer resolution. That is, $Y = mathcal{N},$ the nilpotent cone of a Lie algebra $g$ associated to a reductive group $G$, and $Y = widetilde{mathcal{N}},$ the variety of pairs $(x,b)$ where $x in mathcal{N},$ $b$ is a Borel subalgebra, and $x in b.$ If we stratify $mathcal{N}$ using the $Ad(G)$-orbits (of which there are finitely many), then it turns out that the Springer resolution is semismall and every stratum is relevant.

It can furthermore be shown that the $L_{rho}$ appearing in the theorem above correspond to the irreducible components of the regular representation of the Weyl group of $G.$ This can be seen as follows. There's an analog of the Springer resolution $pi:widetilde{g} to g$ defined as above but with g in place of $mathcal{N}.$ By proper base change, the pushforward of the constant sheaf on $widetilde{mathcal{N}}$ coincides with the pull-back (under the inclusion $mathcal{N} to g$) of the pushforward of the constant sheaf on $widetilde{g}.$ Finally, since $pi$ is what's known as a small map, the pushforward of the constant sheaf on $widetilde{g}$ is equal to $IC_g(L)$ where $L$ is the local system on the dense open subset $g^{rs}$ of regular semisimple elements obtained from the $W$-torsor $widetilde{g^{rs}} to g^{rs}.$ From all this we obtain that the top-dimensional cohomology groups of Springer fibers produce all irreducible representations of $W.$

2. Geometric Satake

In a different direction, let me mention how the decomposition theorem is used in the geometric Satake correspondence (see the Mirkovic-Vilonen paper or the Ginzburg paper on this topic).

Geometric Satake is concerned with proving a tensor equivalence between the category of spherical perverse sheaves on the affine Grassmannian (i.e., perverse sheaves which are direct sums of IC sheaves) associated to a reductive group $G$ and the category of representations of the Langlands dual of $G.$ This is done through the Tannakian formalism, which in particular requires a tensor structure on spherical perverse sheaves. This tensor structure comes from a convolution product on perverse sheaves, meaning that it comes from a pull-back followed by a tensor product followed by a pushforward. In order to ensure that this operation takes spherical perverse sheaves to spherical perverse sheaves, we need the decomposition theorem.

Edit: According to the comments below, the decomposition theorem isn't actually needed to define the convolution product.

Comment on Kazhdan-Lusztig

I'm going to assume that Gil Kalai is referring to the work of Lusztig on Kazhdan-Lusztig polynomials and the Kazhdan-Lusztig conjecture (mentioned in his answer). In particular, they have a paper,

• [KL] Schubert varieties and Poincaré duality, D. Kazhdan, G. Lusztig, Proc. Symp. Pure Math, 1980

in which the coefficients of the Kazhdan-Lusztig polynomials are related to the dimensions of the intersection cohomology of Schubert varieties (which are not generally smooth, hence the appearance of intersection cohomology). At this point, the Decomposition Theorem had not been proved and was not used in [KL]. However, the proof of the Decomposition Theorem heavily uses Deligne's Purity Theorem, which also had not been proved at the time of [KL]. Kazhdan and Lusztig ended up giving a proof of the Purity Theorem in the special case they were considering (i.e., a proof for Schubert varieties). Given this, it's not too surprising that a few years later Macpherson and Gelfand gave a proof of the aforementioned result of [KL] using the decomposition theorem and the result explained at the beginning of this answer.

It's my understanding that Lusztig has another paper from the mid-eighties on finite Chevalley groups which uses the Kazhdan-Lusztig conjecture (proved in 1981) and the full machinery of perverse sheaves and the Decomposition Theorem (I've never looked at it though). Additionally, Lusztig's work in the late seventies and early eighties on Springer theory certainly hints at the Decomposition Theory methods eventually used by Borho and Macpherson (some of his conjectures are proved by Borho and Macpherson, for example).

A wonderful history and reference guide to much of this can be found in this article by Steve Kleiman.

nt.number theory - Is there a high-concept explanation for why characteristic 2 is special?

I think 2 is not special, we just see the weirdness at 2 earlier than the weirdness at odd primes.

For example, consider Ext_E(x)(F_p , F_p) where E(x) denotes an exterior algebra over F_p. If p=2 this is a polynomial algebra on a class x₁ in degree 1 and if p is odd this is an exterior algebra on a class x₁ tensor a polynomial algebra on x₂. I say these are the same, generated by x₁ and x₂ in both cases and with a p-fold Massey product < x₁,...,x₁>=x₂. The only difference is that a 2-fold Massey product is simply a product.

In what sense are the p-adic integers Z_p the same? One way to say it is that if you study the algebraic K-theory of Z_p you find that the first torsion is in degree 2p-3. If p=2 this is degree 1, and K₁(A) measures the units of A (for a reasonable ring A). If p is odd it measures something something more complicated. Another way to say it is that Z_p is the first Morava stabilizer algebra and there is something special about the n'th Morava stabilizer algebra at p if p-1 divides n. If you study something like topological modular forms, this means the primes 2 and 3 are special.

The dual Steenrod algebra is generated by xi_i at p=2 and by xi_i and tau_i at odd primes. But really it is generated by tau_i with a p-fold Massey product < tau_i,...,tau_i>=xi_i+1 at all primes, after renaming the generators at p=2. (Again a 2-fold Massey product is just a product.)

I could go on, but maybe this is enough for now.

coalgebras - Algebraic geometry for cocommutative corings with counit.

I like to think of algebraic geometry as being born out of the fact that Ring behaves a lot like Set^op. For instance, in Ring, A ∐ (B × C) = (A ∐ B) × (A ∐ C), where ∐ is the coproduct in Ring, which is just the tensor product. This formula is also true in Set after we swap ∐ and ×. This suggests that we can use our intuition about Set to think about Ring if we replace Ring by its opposite, the category of affine schemes.

Cocommutative corings with counit are monoid objects in the opposite category of (Ab, ⊗). However, to get the morphisms to point in the right direction, we need to take the opposite category again: so Coring is (CAlg((Ab, ⊗)^op))^op. It follows that products in Coring are computed by tensor products in Ab, and colimits are formed by taking colimits of underlying abelian groups; and in fact Coring is a closed cartesian category, even more like Set than Ring^op is. In particular, we don't want to take the opposite category of Coring. Maybe this isn't surprising, since every set is already a cocommutative comonoid (w.r.t. ×) in a unique way, and we have a functor Set → Coring taking a set to the free abelian group on it.

These are purely formal observations, and I don't know whether anyone has built a more concrete geometric theory, with say a functor from Coring to some kind of topological spaces with extra structure.

at.algebraic topology - Action of the mapping class group on middle-dimensional cohomology

Without other assumptions, the answer is an easy no. For instance, if $N^3$ is a homology 3-sphere with infinite fundamental group, then $M^6 = N^3 times S^3$ does not have very many lifts of automorphisms of its middle homology, because there exists a degree one map $S^3 to S^3$ but no map $S^3 to N^3$ with non-zero degree. There are also obstructions from other cup products besides the middle one, and from algebraic operations on cohomology other than cup products.

So the question is much more reasonable if $M$ is simply connected (unless it is 2-dimensional) and has no homology other than the middle homology and at the ends. In this case, Tom Boardman says in the comment that Wall and Freedman showed that the answer is yes for homeomorphisms, although they surely assume that $M$ is simply connected. In higher dimensions, I don't know the answer to this restricted question, but I imagine that it could be yes using surgery theory.

co.combinatorics - Optimal Monotone Families for the Discrete Isoperimetric Inequality

Background: the Discrete Isoperimetric Inequality

Start with a set X={1,2,...,n} of n elements and the family $2^X$ of all subsets of X.

For a real number p between zero and one, we consider a probability distribution $mu_p$ on $2^X$ where the probability that $i in S$ is p, independently for different i's. Thus for p=1/2 we get the uniform probability distribution.

Given a family F, for a subset S of X, we write h(X) as the number of subsets T in X such that

(1) T differs from S in exactly one element

(2) Exactly one set among S and T belongs to F.

The edge-boundary of F is the expectation of h(S) (according to $mu_p$) over all subsets S of X. It is denoted by $I^p(F)$.

Now a famous isoperimetric relation asserts that

(IR) $I^p(F) ge (1/p) mu_(p)(F) cdot log mu_p(F))$

This relation is true for every family F and every p. It is especially famous and simple when $p=1/2$ and $mu_p(F)=1/2$. In this case, it says that given a set of half the vertices of the discrete cube $2^X$, the number of edges between F and its complement is at least $2^{n-1}$.

The Problem

A family F of subsets of $2^X$ is monotone increasing if when S belongs to F and T contains S then T also belongs to F. (Monotone increasing families also also called "filtes" and "up-families".) From now on we will restrict our attention to the case of monotone increasing families.

We say that a family is optimal for $mu_p$ if the isoperimetric inequality (IR) is sharp up to a multiplicative constant $1000 log (1/p)$.

Problem: For every monotone increasing family F, given an interval [s.t] of real numbers so that $t/s > 1000 log n$ we have some p in the interval [s,t] so that F is optimal with respect to $mu_p$.

Motivation 1

There are two items on the motivation list. The first is why is the problem interesting.

Isoperimetric inequalities are quite central in combinatorics and in applications to probability. This specific problem is a sort of "missing lemma" in a work by Jeff Kahn and me about threshold behavior of monotone properties. The problem is related to an appealing conjecture about random graphs.

This missing lemma is needed for the following conjecture:

Conjecture: Consider a random graph G in G(n,p) and the graph property: G contains a copy of a specific graph H. (Note: H depends on n; a motivating example: H is a Hamiltonian cycle.) Let q be the minimal value for which the expected number of copies of H' in G is at least 1/2 for every subgraph H' of H. Let p be the value for which the probability that G contains a copy of H is 1/2. Conjecture: p/q = O(log n).

(Unfortunately it is not the only missing lemma needed to prove this conjecture.) The paper by Kahn and myself contains an easy proof of a much wealer version of the lemma, where $1000 log n$ is replaced by $C_epsilon n^epsilon$ for every fixed $epsilon$, where $C_epsilon$ is a constant depending on $epsilon$.

Motivation 2

The second item on the motivation list is is why the problem might be doable or even easy.

For a monotone increasing family F of subsets let $a_k(F)$ be the subsets of F of cardinality k. There is a theorem of Kruskal and Katona that gives a complete characterization of sequances that can appear as $(a_0(F),a_1(F),dots,a_n(F))$. The Kruskal Katona theorem gives a numerical characterization.

It also asserts that every such sequence can be realized by very special families: the k-sets in the family are initial with respect to the reverse lexicographic ordering.

It is easy to see that the answer of our problem for a family F depends only on $(a_0(F), a_1(F), dots, a_N(F))$. So, in principle, a positive or a negative answer to the problem should follow from the Kruskal-Katona theorem.

A related paper with several open problems by Michel Talagrand.

M. Talagrand, Are many sets explicitely small?

ho.history overview - Notable mathematics during World War II

Operations research was developed under WWII! This is mentioned in other answers, but only as "mathematical programming", while OR is much wider than that. One paper says

" Operations Research is a ‘war baby’. It is because, the first problem attempted to solve in a
systematic way was concerned with how to set the time fuse bomb to be dropped from an aircraft on
to a submarine. In fact the main origin of Operations Research was during the Second World War. "

googling for "operations research second world war" (or throw into that "submarine") gives a lot of information, one example which looks interesting is

http://www.ibiblio.org/hyperwar/USN/rep/ASW-51/index.html

which is an statistical analysis of anti-submarine warfare.

automata theory - Dumb question about Minimization in IATLC

I have probably a pretty dumb question about the classical Minimization algorithm for a DFA, as described in the Hopcroft book "Introduction to Automata Theory, Languages and Computation", pg. 155-164.

I have no problem with the algorithm itself, or with the examples or even the problems in the book, but the algorithm as described does not seem to work for certain DFAs which are composed entirely of final states.

For example, I tried running this algorithm manually on the automaton from pg.8, fig. 5(a), "Speech Recognition with Weighted-Finite State Transducers" (Mohri) after making all the states final and removing the weights for the sake of simplicity. The resulting automaton is then,

http://i.imgur.com/BDDuT.png (rendered with OpenFST)

however, no matter how I read the description in the book, I cannot find a way to get the table-filling algorithm to do anything with this. It's a non-starter as all the states are already final. But clearly states (1) and (2) should be merged.

My best guess at the moment is that I am interpreting the delta function either incorrectly or too strictly given the wording. That is, for example, in the case of delta(2,e) and delta(3,e), delta(2,e) is accepting and delta(3,e) does not exist. Is that non-existence then also equivalent to 'non-accepting'? From the wording of the book I'm strongly inclined to say that this is not true - that this should be ignored and only existing transitions should be considered, but in that case this pathological example does not end up minimized; the algorithm is just dead in the water before it starts.

I've looked through many other papers and resources online but they all seem to gloss over this which makes me think I'm just a total moron. Any advice for this wayward traveler would be greatly appreciated.

at.algebraic topology - Can two Riemannian manifolds (dim≠4) be homeomorphic without being bi-Lipschitz homeomorphic?

If you don't assume compactness, then no. Silly example: $mathbb R^1$ and $(0,1)$. Example with complete metrics: $mathbb R^2$ and $mathbb H^2$ (they have essentially different volume growths and hence are not bi-Lipschitz equivalent).

If $M$ and $N$ are closed, then yes, by Sullivan's uniqueness result pointed out to by Leonid Kovalev in comments (provided that the MR review is correct - I'm not an expert in any way and don't have access to the paper). The uniqueness means that for every two Lipschitz structures there is an isomorphism between them. And for Lipschitz structures defined by Riemannian metrics, isomorphisms are a locally bi-Lipschitz homeomorphisms of the metrics. By compactness, locally bi-Lipschitz implies bi-Lipschitz.

remark in milne's class field theory notes

1. Here is what Tate says in his account of the General Reciprocity Law in the AMS volume on Hilbert's problems :

With this work of Takagi the theory of
abelian extensions --- "class field
theory" --- seemed in some sense
complete, yet there was still no
general reciprocity law. It remained
for Artin to crown the edifice with
such a theorem. He conjectured in
1923 and proved in 1927 that there is
a natural isomorphism $$
> C_K/N_{L|K}C_Lbuildrelsimovertooperatorname{Gal}(L|K)
> $$ which is characterised by the fact
that...

And a little later :

How did Artin guess his reciprocity
law ? He was not looking for it, not
trying to solve a Hilbert problem.
Neither was he, as would seem so
natural to us today, seeking a
canonical isomorphism, to make
Takagi's theory more functorial. He was led to the law by trying to show...

Read him.

2. Here is a toy example --- not unrelated to class field theory --- of how a bijection can be more natural than others. Let $p$ be a prime number and let $K$ be finite extension of $mathbb{Q}_p$ containing a primitive $p$-th root of $1$. There are only finitely many degree-$p$ cyclic extensions $L|K$, and there are only finitely many vectorial lines in the $mathbb{F}_p$-space $K^times/K^{times p}$. In fact the two sets have the same number of elements, but the only natural bijection is
$$
Lmapstooperatorname{Ker}(K^times/K^{times p}to L^times/L^{times p}),
$$
of which the reciprocal bijections can be written $Dmapsto K(root pof D)$.

It follows that the number of degree-$p$ cyclic extensions $L|K$ is the same as the number of hyperplanes in $K^times/K^{times p}$. But is there a natural bijection between these two sets ? You will agree that $Lmapsto N_{L|K}(L^times)/K^{times p}$ is as natural a bijection as there can be.

One last point : Given a hyperplane $Hsubset K^times/K^{times p}$, how do you recover the degree-$p$ cyclic extension $L|K$ such that $H=N_{L|K}(L^times)/K^{times p}$ ? Answer : use the natural reciprocity isomorphism $K^times/K^{times p}tooperatorname{Gal}(M|K)$, where $M|K$ is the maximal elementary abelian $p$-extension, to identify $H$ with a subgroup of $operatorname{Gal}(M|K)$, and take $L=M^H$.

Addendum (2011/11/21) In Recountings (edited by Joel Segel, A K Peters Ltd, Natick, Mass.), Arthur Mattuck recounts a conversation with Emil Artin about his reciprocity law:

I will tell you a story about the
Reciprocity Law. After my thesis, I
had the idea to define $L$-series for
non-abelian extensions. But for them
to agree with the $L$-series for
abelian extensions, a certain
isomorphism had to be true. I could
show it implied all the standard
reciprocity laws. So I called it the
General Reciprocity Law and tried to
prove it but couldn't, even after many
tries. Then I showed it to the other
number theorists, but they all laughed
at it, and I remember Hasse in
particular telling me it couldn't
possibly be true.

Still, I kept at it, but nothing I
tried worked. Not a week went by ---
for three years ! --- that I did not try to prove the Reciprocity Law. It
was discouraging, and meanwhile I
turned to other things. Then one
afternoon I had nothing special to do, so
I said, `Well, I try to prove the
Reciprocity Law again.' So I went out
and sat down in the garden. You see,
from the very beginning I had the idea
to use the cyclotomic fields, but they
never worked, and now I suddenly saw
that all this time I had been using
them in the wrong way --- and in half
an hour I had it.

nt.number theory - Reference request: given a divisor d of N, how quickly can I obtain the largest factor of N coprime to d?

This is quite likely to be a solved problem, perhaps even a standard exercise. However, being a non-[number theorist], I don't know where to look. A quick perusal of the basic starting references of Google, CLRS, and Bach+Shallit does not seem to help.

Problem. I have an integer N, and a divisor d. What is a good upper bound on the time required to compute coprime integers n₁ and n₂ , such that N = n₁n₂ , and such that d divides n₁?

Actual Question. What is a good reference for the solution / time requirements for this problem?

Solution to problem. As I'm aware that this may also be an exercise in some number-theory class, I'll outline a very reasonable iterative approach as a good-faith gesture.

Define sequences x_j , y_j , and g_j by the recurrences

$begin{align}
quad x_1 =& d & quad && x_{j+1} =& x_j g_j \\
y_1 =& N/d &&& y_{j+1} =& y_j / g_j \\
g_1 =& gcd(x_1, y_1) &&& g_{j+1} =& gcd(x_j, y_j)
end{align}$

which eventually converge. When this occurs (i.e. for j sufficiently large that g_j = 1), we may let n₁ = x_j and n₂ = y_j .

Note that for any j such that x_j ≥ y_j , we may show without too much difficulty that g_j+1 = 1; so the last few iterations take time O( log(N)² ), and the time required for the preceding iterations increases monotonically with x_j . Considering the prime-power decompositions of x_j and of N, we may note that the exponent of the maximal power of each prime p dividing x_j doubles with each succesive iteration, until it saturates the exponent of the maximal power of p which divides N. Thus, the number of iterations required will be bounded above by something like log log(N). The cumulative run-time of all but the last few iterations depends exponentially on the number of iterations; one can then bound the time required for all but the last few iterations by something like O( log(N)² ) again.
This is then an upper bound for the whole procedure.

Remark. I doubt that one can do better than the upper bound of O( log(N)² ) above. I also doubt that I'm the first person to solve this problem, and I'd rather not clutter up a paper describing this solution if I can cite another paper instead.

at.algebraic topology - Homotopy pullbacks of simplicial spaces, and Bousfield-Friedlander

The following represents what I know about this; I don't know of a published reference.

Given a map $f:Z_bulletto Y_bullet$ of simplicial "spaces" (to make things easy, assume spaces are simplicial sets), let's call it a realization quasi-fibration (RQF) if for every $U_bulletto Y_bullet$, the homotopy pullback of the geometric realizations is weakly equivalent to the realizations of the levelwise homotopy pullbacks. The Bousfield-Friendlander theorem gives a sufficient condition for $f$ to be a RQF, in terms of the dreaded $pi_*$-Kan condition.

Some facts:

• The pullback of an RQF $f$ along any $U_bulletto Y_bullet$ is itself an RQF.




• Let $F[n]_{bullet}$ be the simplicial space which is free on a point in degree $n$. Then $f$ is an RQF if and only if its pullback along all $g: F[n]_bullet to Y_bullet$, for all $n$, is an RQF.

These two facts are consequences of something that is sometimes called "descent"; basically, the facts that homotopy colimits distribute over homotopy pullbacks, and compatible homotopy pullbacks assembled by a homotopy colimit result in a homotopy pullback.

So the above gives exact criteria for $f$ to be an RQF. Whether the pullback of an RQF $f$ along a map $g$ is again an RQF only depends on the homotopy class of $g$. So if $f:Z_bulletto Y_bullet$ is any map, let
$pi_0Y$ be the simplicial set whose $k$-simplices are $pi_0(Y_k)$, which is to say all homotopy classes of maps $F[k]_bulletto Y_bullet$. Let $RQF(f)subseteq pi_0Y$ be the sub-simplicial set whose $k$-simplices correspond to $g:F[k]_bulletto Y_bullet$ such that the pullback of $f$ along $g$ is an RQF.

So the criterion is: $f$ is an RQF iff $RQF(f)=pi_0Y$.

It turns out that since geometric realization always preserves products, any map $Z_bullet to point_bullet$ is an RQF. Thus $RQF(f)$ contains all $0$-simplices of $pi_0Y$. Thus, if all $Y_k$ are connected, $f$ is an RQF, which implies the result you describe.

big picture - Is it necessary that model of theory is a set?

You seem to believe that it is somehow contradictory to have a set model of ZFC inside another model of ZFC. But this belief is mistaken.

As Gerald Edgar correctly points out, the Completeness Theorem of first order logic asserts that if a theory is consistent (i.e. proves no contradiction), then it has a countable model. To be sure, the proof of the Completeness Theorem is fairly constructive, for the model is built directly out of the syntactic objects (Henkin constants) in an expanded language. To re-iterate, since you have mentioned several times that you find something problematic with it:

• Completeness Theorem. (Goedel 1929) If a theory is consistent, then it has a model that is a set.

The converse is much easier, so in fact we know that a theory is consistent if and only if it has a set model. This is the answer to your question.

More generally, if a theory is consistent, then the upward Lowenheim-Skolem theorem shows that it has models of every larger cardinality, all of which are sets. In particular, since the language of set theory is countable, it follows that if ZFC is consistent, then it has models of any given (set) cardinality.

The heart of your confusion appears to be the mistaken belief that somehow there cannot be a model M of ZFC inside another structure V satisfying ZFC. Perhaps you believe that if M is a model of ZFC, then it must be closed under all the set-building operations that exist in V. For example, consider a set X inside M. For M to satisfy the Power Set axiom, perhaps you might think that M must have the full power set P(X). But this is not so. All that is required is that M have a set P, which contains as members all the subsets of X that exist in M. Thus, M's version of the power set of X may be much smaller than the power set of X as computed in V. In other words, the concept of being the power set of X is not absolute between M and V.

Different models of set theory can disagree about the power set of a set they have in common, and about many other things, such as whether a given set is countable, whether the Continuum Hypothesis holds, and so on. Some of the most interesting arguments in set theory work by analyzing and taking advantage of such absoluteness and non-absoluteness phenomenon.

Perhaps your confusion about models-in-models arises from the belief that if there is a model of ZFC inside another model of ZFC, then this would somehow mean that we've proved that ZFC is consistent. But this also is not right. Perhaps some models of ZFC have models of ZFC inside them, and others think that there is no model of ZFC. If ZFC is consistent, then these latter type of models definitely exist.

• Incompleteness Theorem. (Goedel 1931) If a (representable) theory T is consistent (and sufficiently strong to interpret basic arithmetic), then T does not prove the assertion "T is consistent". Thus, there is a model of T which believes T is inconsistent.

In particular, if ZFC is consistent, then there will be models M of ZFC that believe that there is no model of ZFC. In the case that ZFC+Con(ZFC) is consistent, then some models of ZFC will have models of ZFC inside them, and some will believe that there are no such models.

A final subtle point, which I hesitate to mention because it can be confusing even to experts, is that it is a theorem that every model M of ZFC has an object m inside it which M believes to be a first order structure in the language of set theory, and if we look at m from outside M, and view it as a structure of its own, then m is a model of full ZFC. This was recently observed by Brice Halmi, but related observations are quite classical. The proof is that if M is an ω-model, then it will have the same ZFC as we do in the meta-theory and the same proofs, and so it will think ZFC is consistent (since we do), and so it will have a model. If M is not an ω-model, then we may look at the fragments of the (nonstandard) ZFC inside M that are true in some V_α of M. Every standard fragment is true in some such set in M by the Reflection Theorem. Thus, by overspill (since M cannot see the standard cut of its ω) there must be some V_α in M that satisfies a nonstandard fragment of its ZFC. Such a model m = V_α^M will therefore satisfy all of the standard ZFC. But M may not look upon it as a model of ZFC, since M has nonstandard axioms which it thinks may fail in m.

cv.complex variables - Converse of Picard's Big Theorem?

If the boundary point is not an isolated singularity, then you can't say it is an essential singularity, so the answer to your final question is no. It is quite possible that $f$ cannot be extended to a larger domain that contains a punctured neighborhood of $x$. To be quasi-explicit, take a holomorphic function whose domain of holomorphy is $Omega$ and multiply by a holomorphic function defined everywhere in the plane except with an essential singularity at $x$.

If $f$ has an isolated singularity at $x$, then yes, this characterizes essential singularities. $f$ goes to $infty$ at a pole, so in particular is nonzero in a neighborhood of the pole. If the singularity at $x$ is removable, then either $f$ goes to a nonzero value, in which case it is nonzero in a neighborhood of $x$, or $f$ goes to 0. In the latter case, $f$ could be extended to a holomorphic function on a domain containing $x$, so if $x$ were a limit point of the zero set of $f$, then $f$ would be identically zero. And you could easily adjust this to nonzero cases.

You don't need anything near the strength of Picard's theorem. In fact, that is what is so amazing about Picard's theorem: Either $f$ has really nice behavior near an isolated singularity, or it maps everywhere except possibly one point in each neighborhood of the singularity.

ct.category theory - Category = Groupoid x Poset?

Given any locally small category, $C$, the collection of all isomorphisms forms a subgroupoid, $G subseteq C$, where $Ob(G) = Ob(C)$ and $Hom_G(A,B) = left ( f in Hom_C(A,B) : exists g, h in Hom_C(B,A) g circ f = id_A, f circ h = id_B right ) $.

Because $G$ is a groupoid, it determines an equivalence relation, $R$ on the objects and morphisms of $C$ such for $A, B in Ob(C)$:

$A equiv_R B Longleftrightarrow Hom_G(A,B) neq emptyset$

And for $f, g in Hom_C(A,B)$:

$f equiv_{R_{A,B}} g Longleftrightarrow exists h_B in Hom_G(B,B), h_A in Hom_G(A,A) : h_B circ f = g circ h_A$

If I understand what you are asking, then the quotient $C/R$ should be the 'poset' you want.

ag.algebraic geometry - What is DAG and what has it to do with the ideas of Voevodsky?

I can't tell you much about the relation to Voevodsky's work, but I can give you a quick summary of Derived Algebraic Geometry.

In DAG you enlarge the category of geometric objects that you can study. It is easiest done by using the functorial approach. So a scheme is just a functor from commutative rings to sets.

Now we'll first enlarge this category in the stacky direction. This means that we change the target of our functor. Instead of studying only set-valued functors we'll allow groupoid-valued functors. This leads to the stacks you are used to. But for some complicated moduli problems groupoids can't encode enough information. So we'll make the target category even bigger and allow for simplicial set valued functors. So now you have to study the category of functors from commutative rings to simplicial sets, also called the category of simplicial presheaves. In this category you have to impose the right descent and atlas conditions to find the objects that have the right to be called geometric. These guys will be called higher stacks.

I think that what we have done so far is very similar to Voevodsky's construction. But I am absolutely not an expert on this. Probably one of the experts will show up here soon and explain that.

So far we haven't derived anything. That starts when you also enlarge the domain category. The natural "derived category" for commutative rings is simplicial commuative rings. That's because the category of commutative rings is not abelian, and then simplicial objects are a good replacement for chain complexes. Derived algebraic geometry then is the study of functors from simplicial commutative rings to simplicial sets, or simplicial presheaves on simplicial commutative rings. Again you have to find the functors inside this category with the right descent and atlas conditions, and that's a lot of work. These guys are then called derived schemes, derived stacks and derived higher stacks.

The geometric intuition for these derived schemes and stacks are that they are ordinary schemes plus a fuzzy cloud of nilpotents on steroids around them. They can encode much more information in their structure sheaf than ordinary schemes. A good example is the intersection of two subschemes in an ambient scheme. You can then construct a "derived intersection". This derived intersection intrinsically in its structure sheaf has encoded that it is an intersection, something you could never accomplish with normal nilpotents.

The difference between the Toen-Vezzosi approach and the approach of Lurie is that TV use model categories where Lurie uses infinity-1 categories. Which approach you actually use is a matter of taste. I think the analogy is to either work coordinate free or with coordinates.

A final comment: If you look into the papers on Luries website or into Toen-Vezzosis Homotopical Algebraic Geomtery II book, you'll find that they work in much greater generality. They do the whole program not on the category of simplicial commutative ring, but for quite general model categories. If you really are only interested in DAG, there are Toen's course notes on his homepage or Luries original thesis.

gr.group theory - Highly transitive groups (without assuming the classification of finite simple groups)

Well, the theorem that $M_{11}$ and $M_{12}$ are the only sharply $k$-transitive groups for $k> 3$ is about 100 years older than the classification theorem...

Also, if $k>3$ (without the sharply hypothesis), $G$ must be simple, unless it is in $S_4$. Of course, that's why the classification is useful.

sg.symplectic geometry - The higher structure of the Floer cochains of the diagonal in CP^ x CP^n

Here's an argument that the diagonal Lagrangian correspondence $Delta$ in $mathbb{C}P^n times mathbb{C}P^n$ is formal. That is, its Floer cochains $CF^ast(Delta,Delta)$, as an $A_infty$-algebra over the rational Novikov field $Lambda=Lambda_mathbb{Q}$ (say), are quasi-isomorphic to the underlying cohomology algebra $HF^ast(Delta, Delta)cong QH^ast(mathbb{C}P^n; Lambda)$ with trivial $A_infty$ operations $mu^d$ except for the product $mu^2$.

Be critical; I might have slipped up!

Write $A$ for $QH^ast(mathbb{C}P^n; Lambda)=Lambda[t]/(t^{n+1}=q)$. Here $q$ is the Novikov parameter. I claim that $A$ is intrinsically formal, meaning that every $A_infty$-structure on $A$, with $mu^1=0$ and $mu^2$ the product on $A$, can be modified by a change of variable so that $mu^d=0$ for $dneq 2$.

Suppose inductively that we can kill the $d$-fold products $mu^d$ for $3leq dleq m$. Then $mu^{m+1}$ is a cycle for the Hochschild (cyclic bar) complex $C^{m+1}(A,A)$. The obstruction to killing it by a change of variable (leaving the lower order terms untouched) is its class in $HH^{m+1}(A,A)$. But $A$ is a finite extension field of $Lambda$ (and, to be safe, we're in char zero). So, as proved in Weibel's homological algebra book, $HH^ast(A,A)=0$ in positive degrees, and therefore the induction works. Taking a little care over what "change of variable" actually means in terms of powers of $q$, one concludes intrinsic formality.

---

You made a much more geometric suggestion - to invoke GW invariants. If you want to handle $Delta_Msubset Mtimes M$ more generally, I think this is a good idea, though I can't immediately think of a suitable reference. One can show using open-closed TQFT arguments that $HF(Delta_M,Delta_M)$ is isomorphic to Hamiltonian Floer cohomology $HF(M)$. One could do this at cochain level and thereby show that the $A_infty$ product $mu^d$ of $HF(Delta_M,Delta_M)$ corresponds to the operation in the closed-string TCFT of Hamiltonian Floer cochains arising from a genus zero surface with $d$ incoming punctures and one outgoing puncture (and varying conformal structure). Via a "PSS" isomorphism with $QH(M)$, these operations should then be computable as genus-zero GW invariants (or at any rate, the cohomology-level Massey products derived from the $A_infty$-structure should be GW invariants).

pr.probability - very simple conditional probability question

We will assume all the obvious implicit assumptions (eg. random child being boy of girl is 50/50, boys and girls open the door uniformly, etc.).

If you had a slightly different question, i.e. if you asked the couple if they have at least one boy, and the answer is yes, then the chance of the other one being a girl is 2/3. Intuitively, the probability is not 1/2 because in this case the answer depends on both the children, i.e. it is a function of both of them considered together.

However, if you asked the couple to pick a child at random, then she/he bears no information about the other child, and consequently his/her gender does not give you any information about the sibling.

Your case is the second case, where the child opening the door is selected at random, and she happens to be female. This does not bear any information regarding the other child.

So answer is 1/2 and your friend is correct.

Mathematically,

$P(Other is B|G opens door) = P(BG|G opens door) =$
$frac{P(BG and G opens)}{P(GG and G opens door) + P(BG and G opens door)} = frac{1/2*1/2}{1/4+1/2*1/2} = 1/2$

(Note here, that $P(BG and G opens)=P(G opens|BG)*P(BG)=1/2*1/2$.)

However as a digression, a twist in the question can be brought about - if you take probabilities for a boy and girl to be different for opening the door.

Eg. suppose boy opens with probability $p$, girl with $q=1-p$, in a family with BG.

Then $P(Other is B|G opened door) = P(BG)/P(G opened door) = $

$frac{P(BG and G opens)}{P(GG and G opens door) + P(BG and G opens door)} = frac{1/2*q
}{1/4+1/2*q} = frac{2q}{2q+1}$.

This means $q = 0 implies P(BG|G opens)=0$. That makes sense, since girls don't open the door if there is a boy, so definitely the other one is girl too.

ag.algebraic geometry - When is a morphism proper?

Assume $V$ and $W$ are quasiprojective. Let $i:Vto X$ be a locally closed embedding with $X$ projective (for instance $X$ could be $P^n$). Consider the induced map $g:Vto Xtimes W$; this is also a locally closed embedding. Then $f$ is proper iff $g$ is a closed embedding, or equivalently if $g(V)$ is closed.

As for the topological approach, use the definition of properness given by Charles Staats. Let $f:Xto Y$ be a continuous map of Hausdorff second countable topological spaces. The base change $f':X'to Y'$ of $f$ by a continuous map $g:Y'to Y$ is defined by letting $X'$ be the set of pairs
$(x,y')$ in $Xtimes Y'$ such that $f(x)=g(y')$ (with the induced topology from $Xtimes Y'$), and $f':X'to Y'$ the obvious projection. Then $f$ is proper if and only if all its base changes are closed. This may not be logically relevant, but I find it very comforting.
To connect the two cases note that, given a locally closed embedding of complex algebraic varieties, it is closed in the Zariski topology iff it is closed in the Euclidean topology.

oc.optimization control - dynamic programming and combinatorics

I tried to work out the problem in a faster way. Here goes my answer.

Let the set $ {chi_p}={t_i, 1 leq i leq l_p } $ collects indices of the buckets for optimally filling $ p $ balls. $bar{chi_p}={1,dots,K}/ chi_p$ is the set of buckets not participating in the $ p $ allocations. The DP we propose derives from the fact that while going inductively from $p$ to $p+1$ allocations, we do not add more than one element (bucket) from the set $bar{chi_p}$. Hence, at every stage of the DP, the goal is to identify bucket that needs to be added and the number of balls to be put in the selected bucket in order to maximize the resulting overall gain. We prove this property.
subsubsection{Proof} Let us assume that while going from the stage $ p $ to $ p+1$, we add $ r $ new buckets from the set $ bar{chi_p} $ into $ chi_{p+1} $ with indices $ x_1,dots,x_r $ containing $ b_1,dots,b_r $ balls. The corresponding gain accrued from the added buckets are $ g_i, , i in {1,dots,r} $. We also alter the allocation in $ n $ buckets from $ chi_p $ with indices $ y_1,dots,y_n $ removing $ d_1,dots,d_n $ balls respectively. Similarly, let the total loss due to this alteration be $q$. Since we add one ball while going from $p$ to $p+1^{th}$ stage, following is true:

$(b_1+b_2dots +b_{r-1}+b_r)- (d_1+d_2 +dots d_n)=1$

Let $ alpha = b_1+b_2dots +b_{r-1} $, be the total number balls placed in all the added buckets except the $ r^{th} $ bucket of index $ x_r $. Similarly, let $ beta= (d_1+d_2 dots +d_n)$ total number of balls removed from the set $ chi_p $ while transitioning from $ p^{th} $ to $ p+1^{th} $ allocation. By

$alpha+b_r=beta+1$

Since $ b_r geq 1 $, $ alpha leq beta $.

Now, consider the partition of the total removed balls $beta$ such that $ beta=alpha + epsilon, , epsilon geq 0 $. The loss $ q $ can also be partitioned as $q = q_{alpha}+ q_{epsilon}$, such that $ q_{alpha} $ is maximum. The gain due to the allocation of $alpha$ balls in $ p+1^{th} $ step in new buckets is $ sum_{i=1}^{r-1} g_i $. It cannot be less then $ q_{alpha} $ else, it is not optimal, as there exists an allocation with higher gain. This implies $ sum_{i=1}^{r-1} g_i geq q_{alpha}$. Moreover, $ q_{alpha} $ was a part of optimal solution of $ p $ allocations. Hence, using same argument, $ q_{alpha} geq sum_{i=1}^{r-1} g_i $. This means $ sum_{i=1}^{r-1} g_i = q_{alpha} $. This is only possible when $ x_1,x_2dots, x_{r-1} in chi_p$. This implies that no more than one bucket is derived from $ bar{chi_p} $ in the $ p+1^{th}$ step. Note that it is also possible that the $ p+1^{th} $ ball is allocated to $ chi_p $.

The DP approach is based on the above property. Given that we know the optimal allocation for $ p $ balls, and optimal gains for $ 1,2dots,p $ allocations, we can approach the $ p+1^{th} $ by exploiting these optimal substructures. Let us call the $ K times N-1 $ matrix $ Delta {bf L} $ whose elements are $ Delta l_{k,i} $ as gain matrix. Let the optimal gain and corresponding updated gain matrix after $ p $ allocations be $Delta R(p)$ and $Delta {bf L}(p)$ respectively. Since, at most one bucket is picked at every step, and this bucket has the capacity of $ N-1 $, hence every successive allocation is dependent only on previous $N-1$ decisions. It can be written as follows:

$Delta R(p+1)= displaystyle max_{i} { Delta R(p-i)+ displaystyle max_{k in [1,K]} Delta l_{k,i}(p)}$

At every step, the recursion involves choosing the optimal bucket and number of balls to be put in it such that new total gain is maximized.

ac.commutative algebra - Formally étale at all primes does not imply formally étale.

Using the module of Kähler differentials, it is easy to show that $Rto S$ is formally unramified if and only if the induced maps $Rto S_{mathfrak{p}}$ are formally unramified for all primes $mathfrak{p}subset S$.

Consider a presentation of $S$ over $R$ as $R[X]/I$ in generators and relations, where $R[X]:=R[X_m]_{min M}$ is a polynomial ring in a possibly infinite family of indeterminates indexed by $M$, and $Isubset R[X]$ is an ideal. Fix a family of generators of $I=(F_j)_{jin J}$ indexed by $J$, again not necessarily finite.

It is enough to show that $Rto S$ is formally smooth. This is equivalent to showing that there exists a morphism of $R$-algebras that is a splitting for the canonical projection $pi:R[X]/I^2 to R[X]/I=S$, which will necessarily be unique because $Rto S$ is formally unramified.

Let $overline{X}_m$ denote the image of $X_m$ in $R[X]/I^2$. We must find elements $delta_min I/I^2$ such that $(forall jin J)F_j(X_m + delta_m)=0$. We rewrite this using Taylor's formula as $$bar{F}_j+ sum_{min M}overline{frac{partial F_j}{partial X_m}}delta_m=0.$$

Rearranging, we get a system of equations indexed by $J$
$$(*)_{jin J} qquad sum_{min M}overline{frac{partial F_j}{partial X_m}}delta_m=-overline{F}_j.$$

We wish to find a unique solution for this system in the $delta_m$. Since $Omega_{S/R}=0$, each $dX_min Omega_{R[X]/R}$ is an $S$-linear combination $dX_m=s_{m,1}dF_{j_{m,1}}+cdots + s_{m,h_m}dF_{j_{m,h_m}}$. If we use the $s_{m,k}$ as coefficients to form $S$-linear combinations of the equations $(*)_{j_k}$, for each $m$, we get an equation of the form $$(**)_m qquad delta_m=-(s_{m,1}overline{F}_{j_{m,1}}+cdots + s_{m,h_m}overline{F}_{j_{m,h_m}}).$$

Showing that these define solutions for all of the equations $(*)_j$ is not immediate, but it is a local question on $S$. However, our local rings $S_{mathfrak{p}}$ are all formally étale, so the local conditions are satisfied. Then this proves the global claim.

(Note: This is not my proof. I've paraphrased the proof communicated to me by Mel Hochster.)

Edit: Fixed LaTeX using Scott's suggestion.

ag.algebraic geometry - What finite group schemes can act freely on a rational function field in one variable?

Suppose that $G$ is a finite group scheme over a field $k$ (we may want to assume that $k$ is perfect). How does one tell whether there exists a free action of $G$ on the function field $k(t)$ in one variable? By this I mean that there exists an action $G times_{mathop{rm Spec}k}mathop{rm Spec}k(t) to mathop{rm Spec}k(t)$, making $mathop{rm Spec}k(t)$ into a $G$-torsor over a scheme (necessarily of the form $mathop{rm Spec} k(s)$, where $s in k(t)$, by Lüroth's theorem).

The question is a very natural one when one studies essential dimension of group schemes: see http://www.math.ubc.ca/~reichst/lens-notes6-27-8.pdf for a nice survey of the topic of essential dimension, and http://front.math.ucdavis.edu/1001.3988 for the essential dimension of group schemes. When $G$ is smooth over $k$, then it is easy to see that the action extends to an action on $mathbb{P}^1$, so $G$ must be a subgroup of ${rm PGL}_{2,k}$; but when $G$ is not smooth it is not all clear to us that this must happen. The sheaf of automorphisms of $k(t)$ over $k$ is enormous in positive characteristic, and we find it very hard to see what group schemes it contains.

For example, how about twisted forms of the group scheme $mu_p$, where $p$ is the characteristic of the field? I would conjecture that most of them can't act freely on $k(t)$, but we can't prove it.

co.combinatorics - Which graphs have incidence matrices of full rank?

The first answer identifies "incidence matrix" with "adjacency matrix". The latter is the
vertices-by-vertices matrix that Sciriha writes about. But the original question
appears to concern the incidence matrix, which is vertices-by-edges. The precise
answer is as follows.

Theorem: The rows of the incidence matrix of a graph are linearly independent over the reals if and only if no connected component is bipartite.

Proof. Some steps are left for the reader :-)

Note first that the sum of rows indexed by the vertices
in one color class of a bipartite component is equal to the sum of the rows indexed by
the other color class. Hence if some component is bipartite, the rows of the incidence matrix are linearly dependent.

For the converse, we have to show that the incidence matrix of a connected non-bipartite
graph has full rank. Select a spanning tree $T$ of our graph $G$. Since $G$ is not bipartite, there is an edge $e$ of $G$ such that the subgraph $H$ formed by $T$ and $e$ is not bipartite.

The trick is to show that the columns of the incidence matrix indexed by the edges of H
form an invertible matrix. We see that $H$ is built by "planting trees on an odd cycle".
We complete the proof by induction on the number of edges not in the cycle.

The base case is when $H$ is an odd cycle. It is easy to show that its incidence matrix is invertible. Otherwise there is a vertex of valency one, $x$ say, such that $H setminus x$ is connected and not bipartite. Then the incidence matrix of $H setminus x$ is invertible and again it is easy to see this implies that the incidence matrix of $H$ is invertible.

Remark: I do not know who first wrote this result down. It is old, and is rediscovered
at regular intervals.

nt.number theory - Is the Green-Tao theorem true for primes within a given arithmetic progression?

Ben Green and Terrence Tao proved that there are arbitrary length arithmetic progressions among the primes.

Now, consider an arithmetic progression with starting term $a$ and common difference $d$. According to Dirichlet's theorem(suitably strengthened), the primes are "equally distributed" in each residue class modulo $d$. Therefore we imagine that the Green-Tao theorem should still be true if instead of primes we consider only those positive primes that are congruent to $a$ modulo $d$. That is, Green-Tao theorem is true for primes within a given arithmetic progression.

Question: Is something known about this stronger statement?

gr.group theory - Why do Groups and Abelian Groups feel so different?

Here's sort of an "opposite" question: Is it possible to naturally and intuitively go from the idea of "groups as group presentations/quotients of the free group" to the idea of groups as symmetry groups? Certainly the reason for why abelian groups are counting things arises immediately in the first context... but of course this isn't a particularly nice place to work, since all sorts of things are undecidable.

Oh, right, it's totally possible to go from group presentations to symmetry groups, although not particularly nicely. There is, of course, a standard construction given a group presentation of a guy on which the group acts... the problem is, we either have to work with a silly definition of automorphism which nobody really uses in real life, or introduce some rather gross and unintuitive combinatorial gadgets that complicate things, or accept that there are a bunch of extra automorphisms that the presentation doesn't account for, and which in particular will generally (always?) make the automorphism group non-abelian... Is there a good way to get around this problem?

ETA: Now that I think about it, though, this isn't even necessarily the core issue with the "co-question." It's pretty easy to think about the free abelian group: It's just how we count apples and oranges if we don't want 3 apples and 3 oranges to make 6 fruits. (If you don't want to deal with negative oranges, fine; it's how you, a stock speculator, keep track of your investments [counting short sells] if you -- for good reason -- don't want to mix up your shares of Reynolds Firearms and Roslin Pharmaceuticals.) From there, it's an easy abstraction to think, well, if I lay out my apples and oranges on the table, then the order they're in doesn't matter. And then you (now you're a mathematician and not a grocer) might think, oh, but what if order does matter, which gets you to the free group. But the conceptual leap from there to general finitely presented groups is non-obvious to me. Maybe I should go back to stacking these cantaloupes...