pr.probability - Likelihood function for sequential random variables

Context

Consider the following sequential data generating process for $Y_1$, $Y_2$, $Y_3$. (By sequential I mean that we generate $Y_1$, $Y_2$, $Y_3$ in sequence.):

$Y_1 = X_1^' beta + epsilon_1$

$Y_2 = X_2^' beta + epsilon_2$

$Y_3 = X_3^' beta + epsilon_3$

where,

$X_3 = x_{3,1}$ if $y_1$ $y_2$ > 0,

OR

$X_3 = x_{3,2}$ if $y_1$ $y_2$ < 0,

$epsilon_i$, ($i$ = 1, 2, 3) are i.i.d $N(0,sigma^2)$,

$beta$ is a $p x 1$ vector and

$X_1$, $X_2$, and $X_3$ are vectors of appropriate dimensions.

Question

Suppose we observe the following sequence: {$Y_1$ = $y_1$,$Y_2$ = $y_2$, $X_3$ = $x_{31}$, $Y_3$ = $y_3$} and wish to estimate the parameters $beta$ and $sigma$. Is the likelihood function given below the correct function?

L( $beta$, $sigma$ | $y_1$, $y_2$, $y_3$, $x_1$, $x_2$, $x_{31}$ ) = ( $f(y_1|x_1,beta, sigma)$ $f(y_2|x_2,beta, sigma)$ $f(y_3|x_{31},beta, sigma)$ ) / Prob( $Y_1 Y_2 >0$ )

Thanks

EDIT: Fixed some typos and notation in light of comments by Bjørn.

ag.algebraic geometry - Reps of $U(n)$ for the bundles of holomorphic and antiholomorphic forms of projective space

In the comments above, I've been trying to figure out what the vector bundle of antiholomorphic forms is. José Figueroa-O'Farrill writes

I think that holomorphic and antiholomorphic refer, respectively, to (1,0) and (0,1) forms.

I write

It ... seems that "antiholomorphic forms" is the dual vector bundle to "holomorphic forms", that is to say, it is the holomorphic tangent bundle.

The point of this answer is to explain that we are both right.

First of all, I am used to distinguishing between two notions. For me, a "$(1,0)$-form" is a $mathbb{C}$-valued $1$-form which locally looks like $sum f_i(z) d z_i$, for some $C^{infty}$ functions $f_i$. In a "holomorphic $1$-form" we also require the $f_i$ to be holomorphic functions. Apparently, not everyone makes this distinction. That's fine, but in this post I am going to use my language because it appears to be more precise.

Let $X$ be a complex manifold. The sheaf of $(1,0)$-forms on $X$ is a sheaf of modules for the sheaf of $C^{infty}$ functions. Similarly, the sheaf of holomorphic $1$-forms is a sheaf of modules for the sheaf of holmorphic functions. Using the appropriate version of the Serre-Swan theorem in each case; we get a complex vector bundle over $X$, in the $C^{infty}$ and holomorphic categories respectively. Taking the forgetful functor from holomorphic vector bundles to smooth vector bundles, we get naturally isomorphic vector bundles in either case, and this bundle is the cotangent bundle $T^*(X)$. So, no matter how you think about it, the "bundle of holomorphic $1$-forms" is the cotangent bundle.

That's what happens with $(1,0)$-forms. What happens with $(0,1)$-forms? In this case, I think it is best to generalize the $C^{infty}$ approach above. That is to say, we consider the sheaf of all $1$-forms that locally look like $sum f_i(z) d overline{z}_i$, for some $C^{infty}$ functions $f_i$. Again, Serre-Swan gives us a $C^{infty}$ complex vector bundle which I'll call $A$. From this perspective, $A$ does not have an obvious holomorphic structure.

However, I claim that $A$ is noncanonically isomorphic to the tangent bundle to $X$. Here is the isomorphism. Choose a positive definite Hermitian structure on tangent bundle of $X$. This is always possible by a partition of unity argument. (My convention is that Hermitian forms are linear in the second argument and conjugate linear in the first.) For any $(1,0)$-vector field $v$, the $1$-form $langle , v rangle$ is a $(0,1)$-form.

The tangent bundle to $X$, of course, does have a natural holomorphic structure; the holomorphic sections are of the form $sum f_i(z) partial/partial z_i$ where the $f_i$ are holomorphic. But this structure is very hidden in the presentation of $A$ as the bundle of $(0,1)$-forms, and that was the point that was confusing me.

st.statistics - Joint Law with 2 marginals and marginal of the spread

Let us think about the discrete case; that is let us suppose we are interested in determining a probability distribution $P$ on the discrete set
$Omega ={mathbb Z}_n^2$.

Such a probability distribution assigns a nonnegative weight to each $(i,j) in Omega$. $|Omega| = n^2$, thus $P$ is determined by $n^2-1$ nonzero variables $p_{i,j}$ whose sum is less than $1$. To fix the marginals of $P$ means to put $2(n-1)$ constraints on ${p_{i,j}}$. In addition to these constraints, the present question also imposes a distribution on $X-Y$. These translate into $n-1$ further constraints on $p_{i,j}$. Thus, in general, $P$ will be a function of $n^2-1-3(n-1)$ free variables.

The special cases you mention (i.e, the clayton and gumbel copulas as well as the normal distribution), however, are determined by the marginal distributions and an additional real parameter. In general, if the given data makes sense, $theta$ can be recovered by first writing an equation that it satisfies and then solving it.

Under any of the above mentioned copulas
the joint distribution equals $Phi(F(x),G(y),theta)$ where $F$ is the $X$ marginal, $G$ is the $Y$ marginal and $theta$ is a real number. The only unknown here is $theta$. Knowing the distribution of $X-Y$, means in particular we know the probability that $X-Y=n-1$[again assuming that we are operating in the discrete setup]. There is only one way this can happen, i.e, if $Y=0$ and $X=n-1$. Thus, we know the weight $p_{(n-1,0)}$ of the point
$(n-1,0)$. Then, $theta$ is the solution of
$$Phi(F(n-1),G(0),theta) -Phi(F(n-2),G(0),theta) = p_{(n-1,0)}.$$

In the case of ${mathbb R}^2$, one can for example, write the following equation for $theta$:
$$int_{mathbb R}^2 (x-y) dPhi(F(x),G(y),theta) = int z dS(z)$$
where $S$ is the distribution of $X-Y$ given in the problem.

Edit: more importantly, it seems, one has to check if the given distribution of $X-Y$ is compatible with the copula in question. Because, there are many equations that one can write for $theta$ and all must give the same answer for the solution to be meaningful.

rt.representation theory - The Category of Representations of a Group

The category Rep(G) is a symmetric tensor category, and it is a theorem that this structure determines G (Tannaka-Krein duality, but I'm not familiar with it). Each object is dualizable because there is a dual representation, from which appropriate evaluation and coevaluation maps can be constructed. The unital object is the trivial representation.

(Incidentally, a symmetric tensor category is a kind of categorification of a commutative ring.)

In the finite case, It is a fusion category because there are finitely many simple objects, there is rigidity as stated above, and because $mathbb{C}[G]$ (or more generally $k[G]$ for $k$ a field of characteristic prime to the order of $G$) is a semisimple algebra (Maschke's theorem). Semisimplicity is also true for continuous finite-dimensional representations of compact groups by the same "averaging" argument used in Maschke's theorem, though the group algebra is not necessarily semisimple. In the finite group case, the number of simple objects is equal to the number of conjugacy classes in G. In the infinite group case, for instance, the rotation group $SO(n)$ has infinitely many irreducible finite-dimensional representations obtained by the action on the spherical harmonics of various degrees (i.e. harmonic polynomials restricted to the sphere).

In the case of S_n, generators of this ring can be indexed by the Young diagrams of size n. The relations are given by the tensor product rules, and while the Pieri rule gives a special case of this, as far as I know, there is no a simple general way to express the tensor product of two representations associated to Young diagrams as a sum of Young diagrams.
However, there are apparently algorithms to do this.

gr.group theory - Can the symmetric groups on sets of different cardinalities be isomorphic?

For any set X, let S_X be the symmetric group on
X, the group of permutations of X.

My question is: Can there be two nonempty sets X and Y with
different cardinalities, but for which S_X is
isomorphic to S_Y?

Certainly there are no finite examples, since the symmetric
group on n elements has n! many elements, so the finite
symmetric groups are distinguished by their size.

But one cannot make such an easy argument in the infinite
case, since the size of S_X is 2^|X|,
and the exponential function in cardinal arithmetic is not
necessarily one-to-one.

Nevertheless, in some set-theoretic contexts, we can still
make the easy argument. For example, if the Generalized
Continuum Hypothesis holds, then the answer to the question
is No, for the same reason as in the finite case, since the
infinite symmetric groups will be characterized by their
size. More generally, if κ < λ implies
2^κ < 2^λ for all
cardinals, (in another words, if the exponential function
is one-to-one, a weakening of the GCH), then again
S_κ is not isomorphic to
S_λ since they have different
cardinalities. Thus, a negative answer to the question is
consistent with ZFC.

But it is known to be consistent with ZFC that
2^κ = 2^λ for some
cardinals κ < λ. In this case, we will
have two different cardinals κ < λ, whose
corresponding symmetric groups S_κ and
S_λ nevertheless have the same cardinality. But can we still
distinguish these groups as groups in some other (presumably more group-theoretic) manner?

The smallest instance of this phenomenon occurs under Martin's Axiom plus ¬CH, which implies 2^ω =
2^ω₁. But also, if one just forces ¬CH by adding Cohen reals over a model of GCH, then again 2^ω =
2^ω₁.

(I am primarily interested in what happens with AC. But if
there is a curious or weird counterexample involving
¬AC, that could also be interesting.)

A graph on irrationals where p is adjacent to q if p^q or q^p is rational.

The answers are that $|E(G)|=2^{aleph_0}$ and that every vertex of $G$ has degree $aleph_0$.

Proof:
The positive real solutions to $x^y=2$ form a curve of cardinality $2^{aleph_0}$, and at most $aleph_0$ of these have $x$ or $y$ rational, so $|E(G)|=2^{aleph_0}$. (It cannot be larger, because this is also the number of pairs of vertices.)

For $g in G$ with $g>1$, the set of positive real numbers $x$ such that $g^x$ is a prime number contains at most one rational number since if there were two, then we would obtain an equation $p^q=p'$ with $p,p'$ distinct primes and $q$ rational, which is impossible by unique factorization. Thus $g$ has infinite degree. On the other hand, the degree of $g$ is at most countable since $g^x = q$ and $x^g=q$ have at most one solution $x$ each for each $q in mathbf{Q}$. Finally, the same arguments apply when $g<1$, with reciprocals of primes in place of primes.

Remark: The same statements hold for $G^*$ except that one should exclude the vertex $1$.

reference request - Tensor product of abelian categories

A generalization of Deligne's construction may be found here: http://arxiv.org/abs/0911.4979. To recoved Deligne's construction one simply takes the perspective that any abelian category is a module category over $Vec$. Here we define $Votimes N$, for any finite dimensional vector space $V$ and object $N$ to be the unique object representing the functor $Nmapsto Hom(V, Hom(N, N))$ (really internal hom).

In general let $mathcal{M}, mathcal{N}$ be right, left $mathcal{C}$-module categories for $mathcal{C}$ any tensor category. Then the $relative$ $tensor$ $product$ $mathcal{M}boxtimes_{mathcal{C}}mathcal{N}$ is defined as the unique (up to a unique equivalence) universal object for right exact in each variable $mathcal{C}$-balanced bifunctors from the cartesian product $mathcal{M}timesmathcal{N}$. As such it follows that $mathcal{M}boxtimes_{Vec}mathcal{N}=mathcal{M}boxtimesmathcal{N}$ where $mathcal{M}boxtimesmathcal{N}$ denotes the product of abelian categories defined in ``Categories Tannakiennes".

mg.metric geometry - Can the algebraic closure of a complete field be complete and of infinite degree?

Yes, this is yet another "foundational" question in valuation theory.

Here's the background: it is a well known classical fact that the dimension (in the purely algebraic sense) of a real Banach space cannot be countably infinite. The proof is a simple application of the Baire Category Theorem: see e.g.

http://planetmath.org/encyclopedia/ABanachSpaceOfInfiniteDimensionDoesntHaveACountableAlgebraicBasis.html

Suppose now that $(K,| |)$ is a complete non-Archimedean (edit: nontrivial) normed field. One has the notion of a $K$-Banach space, and the Baire Category Theorem argument works verbatim to show that such a thing cannot have countably infinite $K$-dimension.

Now let $overline{K}$ be an algebraic closure of $K$. Then $overline{K}$, by virtue of being a direct limit of finite-dimensional normed spaces over the complete field $K$, has a canonical topology, and indeed a unique multiplicative norm which extends $| |$ on $K$.

My question is: does there exist a complete normed field $(K, | |)$ such that:
(i) $[overline{K}:K] = infty$ and
(ii) $overline{K}$ is complete with respect to its norm?

As with a previous question, it is not too hard to see that this does not happen in the most familiar cases. Indeed, by the above considerations this can only happen if $[overline{K}:K]$ is uncountable. But $[overline{K}:K]$ will be countable if $K$ has a countable dense subfield $F$ [to be absolutely safe, let me also require that $F$ is perfect]. Indeed, the algebraic closure of any infinite field has the same cardinality of the field, so $overline{F}$ can be obtained by adjoining roots of a countable collection of separable polynomials $P_i(t) in F[t]$. It follows from Krasner's Lemma that by adjoining to $K$ the roots of these polynomials one gets $overline{K}$.

What about the general case?

dna sequencing - How to clone and sequence a gene transcript of unknown sequence?

Perhaps you can draw inspiration from classic paper on lambda cloning: Maniatis T, Hardison RC, Lacy E, Lauer J, O’Connell C, Quon D, Sim GK, Efstratiadis A. 1978. The isolation of structural genes from libraries of eucaryotic DNA. Cell 15: 687–701.

Try selecting tissues from the animal which you think is "enriched" (i.e. highly expressed) for the specific gene you're looking for. This might take a little bit of guessing. For example, if gene A is very highly expressed in tissue B, then you can "assume" most of the mRNA transcripts will be for that of gene A. Do a RNA purification, RT-PCR, and clone the cDNA into lambda vectors and pick plaques. With a little bit of luck, you'll be able to identify the gene by cloning, hybridisation, and subsequent chromosome "walking" to determine it's structural origin.

This was done back in the day to identify novel genes way before genomics, sequencing, or even PCR!

at.algebraic topology - The Symmetry of a Soccer Ball

From a combinatorial point of view one can define a fullerene to be a 3-valent 3-connected graph with exactly 12 faces which are 5-gons (pentagons) and h 6-gons (hexagons). By Steinitz's Theorem fullerenes which exist as graphs can be realized by convex polyhedra. Branko Grunbaum and Theodore Motzkin showed, The number of hexagons and the simplicity of geodesics on certain polyhedra, Canadian J. Math., 15 (1963) 744-751, that the admissible values of h for such graphs are all non-negative integers h except h = 1. Other proofs of this, given by construction, show other features than what Grunbaum and Motzkin did. (For references see article listed below.)

What are the symmetry groups which can arise as the automorphism groups of fullerene graphs? There are only 28 such groups and they are listed on page 36 of the book: Geometry of Chemical Graphs: Polycylces and Two-Faced Maps, by Michel Deza, and Mathieu Dutour Sikiric, Cambridge U. Press, 2008. By a theorem of Peter Mani, these fullerene graphs can be realized by 3-dimensional polyhedra with the full automorphisms group of the graph as the group of isometries of the realizing polyhedron.

For further discussion of fullerenes and some open problems about fullerene graphs see:

Malkevitch, J., Geometrical and Combinatorial Questions about Fullerenes, in Discrete Mathematical Chemistry, (P. Hansen, P. Fowler, M. Zheng, eds.), Volume 51, DIMACS Series in Discrete Mathematics and Computer Science, AMS, Providence, 2000, pp. 261-266.

computer science - Satisfiability of general Boolean formulas with at most two occurrences per variable

(If you know basics in theoretical computer science, you may skip immediately to the dark box below. I thought I would try to explain my question very carefully, to maximize the number of people that understand it.)

We say that a Boolean formula is a propositional formula over some 0-1 variables $x_1,ldots,x_n$ involving AND and OR connectives, where the atoms are literals which are instances of either $x_i$ or $neg x_i$ for some $i$. That is, a Boolean formula is a "monotone" formula over the $2n$ atoms $x_1,ldots, x_n, neg x_1,ldots, neg x_n$. For example, $$((neg x_1 ~OR~ x_2) ~AND~ (neg x_2 ~OR~ x_1)) ~OR~ x_3$$ is a Boolean formula expressing that either $x_1$ and $x_2$ take on the same value, or $x_3$ must be $1$. We say that a 0-1 assignment to the variables of a formula is satisfying if the formula evaluates to $1$ on the assignment.

The Cook-Levin theorem says that the general satisfiability of Boolean formulas problem is $NP$-complete: given an arbitrary formula, it is $NP$-hard to find a satisfying assignment for it. In fact, even satisfying Boolean formulas where each variable $x_i$ appears at most three times in the formula is $NP$-complete. (Here is a reduction from the general case to this case: Suppose a variable $x$ appears $k > 3$ times. Replace each of its occurrences with fresh new variables $x^1, x^2, ldots, x^k$, and constrain these $k$ variables to all take on the same value, by ANDing the formula with $$(neg x^1 ~OR~ x^2) ~AND~ (neg x^2 ~OR~ x^3) ~AND~ cdots ~AND~ (neg x^{k-1} ~OR~ x^k) ~AND~ (neg x^k ~OR~ x^1).$$ The total number of occurrences of each variable $x^j$ is now three.) On the other hand, if each variable appears only once in the formula, then the satisfiability algorithm is very easy: since we have a monotone formula in $x_1,ldots, x_n, neg x_1,ldots, neg x_n$, we set $x_i$ to $0$ if $neg x_i$ appears, otherwise we set $x_i$ to $1$. If this assignment does not get the formula to output $1$, then no assignment will.

My question is, suppose every variable appears at most twice in a general Boolean formula. Is the satisfiability problem for this class of formulas $NP$-complete, or solvable in polynomial time?

EDIT: To clarify further, here is an example instance of the problem:
$$((x_1 ~AND~ x_3) ~OR~ (x_2 ~AND~ x_4 ~AND~ x_5)) ~AND~ (neg x_1 ~OR~ neg x_4) ~AND~ (neg x_2 ~OR~ (neg x_3 ~AND~ neg x_5))$$

Note that when we restrict the class of formulas further to conjunctive normal form (i.e. a depth-2 circuit, an AND of ORs of literals) then this "at most twice" problem is known to be solvable in polynomial time. In fact, applying the "resolution rule" repeatedly will work. But it is not clear (at least, not to me) how to extend resolution for the class of general formulas to get a polytime algorithm. Note when we reduce a formula to conjunctive normal form in the usual way, this reduction introduces variables with three occurrences. So it seems plausible that perhaps one might be able to encode an $NP$-complete problem in the additional structure provided by a formula, even one with only two occurrences per variable.

My guess is that the problem is polynomial time solvable. I'm very surprised that I could not find a reference to this problem in the literature. Perhaps I'm just not looking in the right places.

UPDATE: Please think about the problem before looking below. The answer is surprisingly simple.

at.algebraic topology - N_3 and N_4 periodic and pseudo Anosov auto-homeomorphisms

Just to lend some context to the above question: the mapping class group of the two-torus is naturally isomorphic to GL(2, Z). If we restrict to orientation preserving homeomorphism the mapping class group is SL(2, Z). The periodic mapping classes (isotopy classes of homeomorphisms) are exactly those with trace less than two in absolute value. (Hmm, and +/- Id, I guess!) Now we need to count the number of conjugacy classes of periodic elements. There should be a cool algebraic way to do this. (Perhaps it would help to give a purely algebraic proof that the order of torsion is at most 6?)

I think that there is a geometric way to do this: every periodic element occurs as the symmetry of some flat torus (= parallelogram with opposite sides identified). All tori have have the hyperelliptic symmetry, corresponding to rotation by 180 degrees about any point. (These maps lie in the mapping class of the negative identity.) Other symmetries:

Rombic tori have a reflection symmetry as do rectangular tori.

The square torus has a rotation by 90 degrees.

The hexagonal torus has a rotation by 60 degrees.

So I count:

1. the identity, Id

2. the hyperelliptic = -Id = rotation by 180

3. rotation by 90

4. rotation by 60

5. rotation by 120

6. the reflection [[-1,0],[0,1]] (reflection in an axis) and

7. the reflection [[0,1],[1,0]] (exchange axes).

You can prove that the last two are distinct algebraically. Perhaps the lack of 45 degree rotation is a geometric proof.

Now, we could perform similar geometric tricks to obtain symmetries of $N_4$ and get at least all of the rotations... [Edit: For example, it is possible to build a copy of $rm{Sym}_4$ by placing the cross-caps at the vertices of a tetrahedron.]

tag removed - Systematization of deterministic and stochastic integrals

With this question I try to build up a systematization of different kinds of integrals. The following table differentiates between deterministic and stochastic integrals, the summation processes ("from left" or "average between left and right") and different kinds of variations (bounded and quadratic).

The following integrals are already present:

(A) Riemann integral
(F) Ito integral
(G) Stratonovich integral

Unfortunately I didn't find references for the remaining fields. Is this because it doesn't make any sense to define these? And then, why not?

In any case: I would very much appreciate your help here. Could you please reference the field (X) and give some further information regarding

• type of integral


• examples


• refences


• links


• if it doesn't make any sense: why not

Every little bit of information helps - thank you very much and I promise to consolidate the information given here into a proper form.

Addendum: For the cases (D) and (E) [perhaps even (H) and (I)?] there seem to be some possible connections to deterministic fractal functions (like e.g. Weierstrass function) but I can't find any further references on definitions for integrals/integration here.

differential topology - Two kinds of orientability/orientation for a differentiable manifold

If $X$ is a differentiable manifold, so that both notions are defined, then they coincide.

The ``patching'' of local orientations that you describe can be expressed more formally as follows: there is a locally constant sheaf $omega_R$ of $R$-modules on $X$ whose stalk at a point is $H^n(X,Xsetminus{x}; R).$ Of course, $omega_R = Rotimes_{mathbb Z} omega_{mathbb Z}$.

This sheaf is called the orientation sheaf, and appears in the formulation of Poincare duality for not-necessarily orientable manifolds. It is not the case that any section of this sheaf gives an orientation. (For example, we always have the zero section.)
I think the usual definition would be something like a section which generates each stalk.

I will now work just with $mathbb Z$ coefficients, and write $omega = omega_{mathbb Z}$.

Since the stalks of $omega$ are free of rank one over $mathbb Z$, to patch them together you
end up giving a 1-cocyle with values in $GL_1({mathbb Z}) = {pm 1}.$ Thus underlying
$omega$ there is a more elemental sheaf, a locally constant sheaf that is a principal bundle for ${pm 1}$. Equivalently, such a thing is just a degree two (not necessarily connected) covering space
of $X$, and it is precisely the orientation double cover of $X$.

Now giving a section of $omega$ that generates each stalk, i.e. giving an orientation of $X$, is precisely the same as giving a section of the orientation double cover (and so $X$ is orientable, i.e. admits an orientation, precisely when the orientation double cover is disconnected).

Instead of cutting down from a locally constant rank 1 sheaf over $mathbb Z$ to just a double cover, we could also build up to get some bigger sheaves.

For example, there is the sheaf $mathcal{C}_X^{infty}$ of smooth functions on $X$.
We can form the tensor product $mathcal{C}_X^{infty} otimes_{mathbb Z} omega,$
to get a locally free sheaf of rank one over ${mathcal C}^{infty}$, or equivalently, the sheaf of sections of a line bundle on $X$. This is precisely the line bundle of top-dimensional forms on $X$.

If we give a section of $omega$ giving rise to an orientation of $X$, call it $sigma$, then we certainly get a nowhere-zero section
of $mathcal{C}_X^{infty} otimes_{mathbb Z} omega$, namely $1otimessigma$.

On the other hand, if we have a nowhere zero section of $mathcal{C}_X^{infty} otimes_{mathbb Z} omega$, then locally (say on the the members of some cover ${U_i}$ of $X$ by open balls) it has the form $f_iotimessigma_i,$ where $f_i$ is a nowhere zero real-valued function on $U_i$ and $sigma_i$ is a generator of $omega_{| U_i}.$

Since $f_i$ is nowhere zero, it is either always positive or always negative; write
$epsilon_i$ to denote its sign. It is then easy to see that sections $epsilon_isigma_i$
of $omega$ glue together to give a section $sigma$ of $X$ that provides an orientation.

One also sees that two different nowhere-zero volume forms will give rise to the same orientation if and only if their ratio is an everywhere positive function.

This reconciles the two notions.

qa.quantum algebra - Classical limit of quantum systems

This may not answer the question in the way you envisage it, but it is certainly possible for two different classical systems to give rise to equivalent quantum theories. One particularly well-understood example is the boson-fermion correspondence in two-dimensional conformal field theory as explained in Chapter 5 of Bombay lectures on highest weight representations of infinite dimensional Lie algebras by Kac and Raina.

There are also non-conformal examples, also in two-dimensional physics. One of the earliest known examples is the duality between the Sine Gordon and Thirring models, which are quantum mechanically equivalent yet very different classically.

In general, this is what S duality is about. This idea pervades much of modern theoretical physics, but its origins are in the Kramers Wannier duality in statistical mechanics. The Onsager solution of the Ising model is another example.

---

Added

In response to Anirbit's comments above. Here's perhaps another answer which is more in the spirit of the original question.

Any filtered associative unital algebra $A$ whose associated graded algebra $mathrm{Gr}A$ is commutative may be thought of as a quantisation of $mathrm{Gr}A$ with the Poisson structure induced by the commutator in $A$. So an example of the situation you are after could be an associative unital algebra admitting two different filtrations with commutative associated graded algebras. I'd be surprised if one could not cook up something like this. It's another question altogether whether there are any "natural" examples.

Given a number field $K$, when is its Hilbert class field an abelian extension of $mathbb{Q}$?

I happened to come across this question again today. In some cases at least, the Hilbert class field $H$ of an abelian extension $K$ of $mathbf{Q}$ will have to be abelian over $mathbf{Q}$ for purely algebraic reasons.

Let $F$ be any field, $K|F$ an abelian extension of group $G=mathrm{Gal}(K|F)$ and containing a primitive $n$-th root of unity for some $n>1$, $omega:Gto(mathbf{Z}/nmathbf{Z})^times$ the cyclotomic character giving the action of $G$ on $mu_n$, and $H|K$ an abelian extension of exponent dividing $n$. Then $H=K(root nof D)$ for some subgroup $Dsubset K^times/K^{times n}$, by Kummer theory. It can be checked that $H|F$ is galoisian if and only if $D$ is $G$-stable. When such is the case, the conjugation action of $G$ on $mathrm{Gal}(H|K)$ coming from the short exact sequence
$$1tomathrm{Gal}(H|K)tomathrm{Gal}(H|F)to Gto1$$
is trivial if and only if $G$ acts on $D$ via $omega$. In this situation ($H=K(root nof D)$ for some subgroup $Dsubset(K^times/K^{times n})(omega)$), a sufficient condition for $H$ to be abelian over $F$, is that the order of $G$ be prime to $n$, because then $mathrm{Gal}(H|F)=mathrm{Gal}(H|K)timesmathrm{Gal}(K|F)$.

I'm sure this situation can be realised when $F=mathbf{Q}$, for example when the finite abelian extension $K$ has odd degree $[K:mathbf{Q}]$, $n=2$, the class group of $K$ has order ($1$ or) $2$, and $H$ is the Hilbert class field of $K$. In this case the extension $H|mathbf{Q}$ will be necessarily abelian.

gene annotation - Overlapping genetic information in eukaryotes

In general, the compactnes of genomes is a characteristic of prokaryotes, but there are several eykaryotes that have overlapping genes: many parasites and endosymbionts. The best studied of these are the fungal parasites of the phylum microsporidia and the nucleomorphs (remnant nuclei of algal endosymbionts in cryptophytes and chlorarachniophytes).

cDNA library was constructed from the microsporidian Antonospora locustae and 1,146 cDNA clones were sequenced. Here is part of the expression profile (1):

Of the 871 clones found to encode recognizable genes, 97 transcripts (11%) from 70 distinct loci encoded sequence from more than one gene (Fig. 1 A ; see also Table 1, which is published as supporting information on the PNAS web site). The polyA sites of these clones do not correspond to polyA tracts in the genome, so they are unlikely to derive from DNA contamination (see also below), but instead come from polyA RNA. In prokaryotes, polycistronic mRNAs commonly code for multiple proteins (11), but with few exceptions (12) eukaryotic mRNAs encode a single gene. A. locustae multigene transcripts encode two or three genes or gene fragments in various orientations (Fig. 1 B–I ), but they cannot all be polycistronic messages because there is no bias for genes being on the same strand.

Here is part of a review paper on the nucleomorphs genome (2):

As in other reduced genomes, the G. theta nucleomorph genome possesses a very high A+T content (75%) and gene density is extremely high: 1 gene per 977 bp and 44 genes overlap by as many as 76 nucleotides. Williams et al. (84) showed that transcription of the G. theta nucleomorph genome is affected by this compaction, with nucleomorph-derived messenger RNAs often possessing coding sequence for more than one gene, albeit with no strand bias. It appears that during the process of genome compaction, transcription regulatory elements (e.g., promoters, terminators) have moved from the intergenic spacers into the coding regions themselves (84).

I also have to point out that there are a few examples of overlapping genes in yeast: CCT6 overlaps with YDR187C and CCT8 overlaps with YJL009W (3).

1. A high frequency of overlapping gene expression in compacted eukaryotic genomes


2. Nucleomorph Genomes, Annual Review of Genetics


3. The Chemical Genomic Portrait of Yeast: Uncovering a Phenotype for All Genes

ds.dynamical systems - Conjectures on iterated polynomial maps on finite fields

Let $p$ be a prime, and consider the sequence $x_0, x_1, dots$ of elements of the finite field $mathbf F_p$ given by $x_0 = 0$ and $x_{i+1} = x_i^2 + 1$ for all $i ge 0$. This sequence must eventually start repeating; let's write $T(p)$ and $U(p)$ for the period and preperiod (resp.) of the sequence.

There's an informal idea, used for example as the basis of Pollard's Rho method for integer factorisation, that for a 'randomly chosen' prime $p$, $T(p)$ and $U(p)$ should behave like the period and preperiod of the sequence of iterates of a randomly chosen function $mathbf F_prightarrow mathbf F_p$. For example, it's expected that the quantity $T(p) + U(p)$ (that is, the index of the first repeated value in the sequence) is comparable in magnitude to $sqrt p$, exceeding $xsqrt p$ with 'probability' $exp(-x^2/2)$.

Question: Does anyone know of formal statements to this effect in the literature? I'm looking for a conjecture that would imply the following (or something similar) as a special case:

Notation. For each positive integer $M ge 2$, let $X_M$ be a discrete random variable that takes values in the set of primes not greater than $M$, with all primes in $[2, M]$ being equally likely to occur. Let $X_infty$ be a continuous random variable on $[0, infty)$ that satisfies $mathbf P(X_infty > x) = e^{-x^2/2}$.

Conjecture. The sequence $$frac{T(X_M) + U(X_M)}{sqrt{X_M}}, quad M ge 2$$
of random variables converges (in distribution, say) to $X_infty$.

Similarly, one might conjecture that $T(X_M) / (T(X_M) + U(X_M))$ is, in the limit, uniformly distributed on $(0, 1]$, and it should be possible to make (not prove!) some sort of statement about the independence of $T(X_M) / (T(X_M) + U(X_M))$ and $(T(X_M) + U(X_M)) / sqrt{X_M}$.

I've so far failed to find any concrete statements of this form in the literature. Any pointers?

[It's difficult to know how to tag this. I guess it's really about discrete dynamical systems; please retag as appropriate!]

Could someone recommend an introductory book on epidemiology?

There are two books I'd highly recommend for someone starting to dabble in Epidemiology. The first is Kenneth Rothman's Epidemiology: An Introduction, which I'm affectionately going to refer to as "Baby Rothman" from hereon out for reasons that will become obvious.

Baby Rothman is an excellent "getting your feet wet" book. It's simplistic, and clearly designed for someone with no background in Epidemiology, so it starts from things that, if you have a statistical background, you might find a bit dull. But it accomplishes two key tasks:

1. A basic treatment of the subject from a pre-eminent methodologist and advocate for the field that doesn't make some of the sloppy slight-of-hand mistakes many introductory books do.


2. An introduction to the "vocabulary" of Epidemiology as a field - what we call things, how we thing about effect estimates, etc.

The second book I would buy would be Modern Epidemiology: 3rd Edition by Rothman, Greenland and Lash. This is the definitive reference book for most epidemiological methods currently used in the field. As I said on a related CrossValidated question, ME3 is the only epidemiology book that has always come with me, regardless of what project I'm doing, and which I have routinely found invaluable.

The other benefit of the book is that it's "platform agnostic". It's not going to try to teach you a statistics package - its going to teach you the science and philosophy of Epidemiology, the actual doing of the science, rather than the toolkit. Without that kind of methodological rigor, you can be a wizard at your language of choice and still do bad science.

If I were only going to buy one book, it would be ME3.

nt.number theory - Chebyshev-like polynomials with integral roots

I can satisfy conditions 1, 3 and almost satisfy condition 2. Letting $f_n(t) = {t+n-1 choose n}$ we have the well-known generating function

$displaystyle sum_{n ge 0} f_n(t) x^n = frac{1}{(1 - x)^{-t}}$

which is rational in $x$ for any fixed integer value of $t$. I think condition 2 will end up being the hardest to satisfy because rational functions are quite rigid.

---

Edit 1: My current opinion is that the conditions are not satisfiable. Based on the analogous situation with linear homogeneous recurrences on the integers I am going to conjecture that any polynomial sequence which obeys a polynomial linear recurrence and is not essentially a geometric series has terms divisible by irreducible polynomials of arbitrarily high order.

Edit 2: A very strong result available in the integer case is Zsigmondy's theorem, but we don't need a result this strong. Here's a nice result in the integer case. Suppose an integer sequence $a_n$ satisfies a linear homogeneous recurrence with integer coefficients, and let $p$ be a prime not dividing those coefficients. Then the sequence $a_n bmod p$ is periodic (not just eventually periodic) $bmod p$ by Pigeonhole. If in addition there exists $n$ such that $a_n = 0$ and $a_n$ is unbounded, then it follows that there is a nonzero term of the sequence divisible by $p$. For example, this is true of the Fibonacci sequence; in fact we have the much stronger result that for $p > 5$, either $p | F_{p+1}$ or $p | F_{p-1}$.

My guess is that a result like this holds in the polynomial case with $p$ replaced by a monic irreducible polynomial (say, of degree $2$), although the argument above breaks down as written.

pr.probability - When does the ratio X/Y of two random variables have a finite moment-generating function?

Let $X$ and $Y$ be two positive random variables with $Y < X$; these may be highly correlated. I would like a reasonable condition on $X$ and $Y$ so that the ratio $X/Y$ has a finite moment-generating function. By this I mean that $mathbb E e^{r X/Y} < infty$ for all $r in mathbb R$.

Here's one answer. Suppose that X and 1/Y both have super-Gaussian tail decay, that is,

$P(X > u) le C e^{-cu^{2+delta}},$

for positive constants $c$, $C$ and $delta$, and similarly for $1/Y$. Then $X/Y$ has super-exponential tail decay:

$P(X/Y > u) = P(X > Yu$ and $Y le 1/sqrt{u}) + P(X > Yu$ and $Y > 1/sqrt{u})$

$le P(1/Y > sqrt{u}) + P(X > sqrt{u})$

$le 2Ce^{-cu^{(2+delta)/2}} = 2Ce^{-cu^{1+delta/2}}.$

This gives a finite moment-generating function by the following simple argument, which uses the fundamental theorem of calculus and Tonelli's theorem. Let $Z = X/Y$.

$mathbb Ee^{rZ} = mathbb E left[ 1 + int_0^Z re^{ru} ~du right] = 1 + int_0^infty re^{ru} mathbb P(Z > u) ~du le 1 + 2Cr int_0^infty e^{ru} e^{-cu^{1+delta/2}} ~du$,

which is finite for all $r in mathbb R$. Thus, super-Gaussian tail decay suffices, but this is a very strong condition which I'd like to weaken.

(In fact, I only need that $mathbb Ee^{rX/Y} < infty$ for any one positive value of $r = r_0$. In that case, we may choose $r_0 = c/2$, and take $delta = 0$ in all the above arguments. Then the integral $int_0^infty e^{r_0 u} e^{-cu} ~du$ still converges.)

st.statistics - What is the probabilistic counterpart of weighted K-Means

pKNN+AL (Jain and Kapoor, 2009) is a probabilistic modification of the KNN classifier. Given a set of points ${x_1, ldots, x_n}$ from $mathbb{R}^d$, labels ${y_1, ldots, y_n}$ from $[1,C]$, and a Mercer kernel $K$, the probability of $x$ belonging to class $c$ is

$$frac{frac{1}{n_c} sum_{{i : y_i = c}} K(x, x_i)}{sum_{t=1}^C frac{1}{n_t} sum_{{i : y_i = c}} K(x, x_i)}$$

where $n_c$ is the number of $x_i$ that belong to class $c$. It is also an active learning algorithm and comes with a MATLAB implementation.

lo.logic - What assumptions and methodology do metaproofs of logic theorems use and employ?

Here is some more information for the first question. I think that to prove the meta theorems in mathematics, in particular, soundness, completeness, incompleteness, heuristic logic does not exhaust the meta principles being used. Some meta principles relating to heuristic set theory or heuristic category theory must to be used as well. That is because when we talk about a model and a statements true in a model we need to have some notion of set or something equivalent.

It is difficult to understand these meta principles, so we need to cast them into the language of formal logic, formal set theory. I choose Zermelo Fraenkel set theory here. The formal counter part of your question can be considered the question which axioms of set theory necessary for the proof of the formalized version of the theorems. The choice of Zermerlo Fraenkel set theory is in a sense general enough. You might decide that category theory is the genuine language of mathematics but to phrase and prove soundness, completeness, you need to use something of equal strength. The expression may change with different choices of mathematical language, but the mathematical phenomenon remains invariant.

The following is not a very precise answer ( I did not checked the material carefully). I think this might be an approximation to the answer that you want:

Soundness for First Order Logic: We need classical logic, ZF {Powerset,Replacement, Infinity}. The checking of Soundness is basically mechanical so we don't need much.

Completeness for First Order Logic: Need all these thing and some weak version of choice, may be Konig lemma. The proof of completness is basically cook up a model of the theory base on the language. We need to add in many constant to make the theory have Henkin property, and this is an iterated process, so we need choice somewhere. I don't think we need power set.

First incompleteness: We need axiom of foundation and axiom of power set in the universe of set and the identification of theory of natural number with theory of $omega$ with the respectively defined +, x, <. I don't think we need choice here.

Second incompleteness: We still need axiom of founation (PA still must be enumerated by $omega$ in this situation). I don't think we need power set anymore.

To have the precise answer, we can always look closely at the steps of the proof or search the existing material.

nt.number theory - Bounding archimedean lengths of fundamental units

Suppose $K$ is a number field, $r=r_1+r_2-1$ (the rank of the unit group) and $u_1,dots, u_r$ are a basis of fundamental units. Suppose this basis minimizes the max over $i=1,dots, r$ of the largest archimedean absolute value of $u_i$, and this value is $M>0$. What is a good upper bound on $M$ in terms of standard invariants of the field $K$? (In fact, I know one exists which for fixed degree is exponential in the regulator.)

More precisely, I'd like a bound on this minimax (min over choices of basis of max over basis elements) of the product of all archimedean absolute values which are greater than $1$ (a.k.a. the "entropy") of the $u_i$. (This can of course be bounded by an $r-1$st power of the previous bound.)

Is there a better bound/standard reference for bounding these quantities?

rt.representation theory - Global dimenson of quivers with relations

Let Q be a finite quiver without loops. Then its global dimension is 1 if it contains at least one arrow.

I'm trying to get some intuition about how much the global dimension can grow when we quotient by some homogeneous ideal of relations I. In general, if Q is acyclic (is this necessary?), then the global dimension is bounded by the number of vertices, but I want something that uses information from I. For simplicity, let's assume that there is at most 1 edge between any two vertices. If I add the relation that a single path of length 2 is 0, then the global dimension goes up to 2, and the same is true if 2 is replaced by any r>2 (right?). I can get higher global dimensions by the following: take some consecutive arrows $a_1, a_2, dots, a_n$, and require that each path of length 2 $a_{i+1} a_i$ is 0, then the global dimension goes up to n-1.

The way I am trying to picture this is by thinking of projective modules as flowing water which gets stopped by some rock placed where the relations are, and seeing how many times the flow needs to restart before it can reach the end (I don't know if this is a useful comment.)

Anyway, here is my question: is there some simple way to bound the global dimension of Q/I assuming that Q is acyclic and no multiple edges between any two vertices? In this case, we're only allowed to say that certain paths are 0, so I am suspecting this has something to do with "number of overlaps." My guess would be something like, define an overlap to be when an initial segment of one path coincides with an ending segment of another path, and then the global dimension should be less than or equal to number of overlaps + 2.

rt.representation theory - Analogy between canonical basis of U(n_-) and Schur functors, each under restriction

.1. For any category $mathcal C$, possibly enriched over schemes, define $Rep({mathcal C})$ to be the functor category ${mathcal C} to {bf Vec}$ with direct sum inherited from $bf Vec$. (If $mathcal C$ is enriched over schemes, like $bf Vec$ is since it's enriched over itself and vector spaces are schemes, then I probably only want functors that preserve this.) So it's easy to define irrep, etc. of $mathcal C$.

Fun fact: consider the irreps of $bf Vec$, called the Schur functors. If we restrict them to reps of the single-object category (i.e. monoid) $End({mathbb C}^n)$, some irreps restrict to $0$, and the ones that don't go to $0$ stay irreducible and give all the irreps of $End({mathbb C}^n)$ exactly once! In standard indexing, the Schur functors correspond to partitions, the partitions with more than $n$ rows restrict to $0$, and the partitions with $leq n$ rows give the irreps of $End({mathbb C}^n)$.

.2. I am told that one of the nice properties of Lusztig's canonical basis $B =$ { $b$ } of $U({mathfrak n}_-)$ is that on any irrep $V$ of $G$ with high weight vector $vec v$, the nonzero $bcdot vec v$ give a basis of $V$.

Is there a common framework for these two facts, perhaps involving categorifying the second one?

(I don't have anything riding on the answer... it's just a question I'd thought of a number of years ago and was reminded of by another mO question.)

rt.representation theory - Embedding into Permutation Representation

There is the following adjointness (a form of Frobenius reciprocity):

$Hom_G(rho,F^X) = Hom_H(rho,trivial).$

Thus $rho$ embeds in $F^X$ if and only if $rho$ admits a non-trivial $H$-fixed quotient.

(If $H$ is finite and $F$ has characteristic zero, or at least prime to the order
of $H$, so that $rho$ is semi-simple
as an $H$-representation, then this is equivalent to requiring that $rho$ have a
non-trivial $H$-fixed subrepresentation.)

(Note also that a non-zero $G$-equivariant map out of $rho$ is automatically injective,
because $rho$ is irreducible.)

genetics - Linkage and LD: quantitative or qualitative?

Linkage disequilibrium (LD) occurs when there is a non-random association or correlation between genotypes. Note I used the word correlation; this is a quantitative trait.

Some genotypes may well correlate perfectly (R=1), i.e. they are always inherited together. Others may not be in 'perfect' linkage (e.g. R=0.9), but are still considered to be in LD because there is a strong correlation between the genotypes (I think 0.8 is generally seen in published papers as the 'cut-off').

The correlation coefficient is derived from the D' value - this (simply) denotes the observed vs. expected frequencies of the genotypes (whether they are in linkage or not). Therefore either value can be used, but I think it is more common (and more interpretable) to express the correlation coefficient (or to be more precise, the coefficient of determination, R^2).

If you'd like an example: I might be interested to know if any SNPs are in LD with rs10757278 (located on 9p21, associated with heart disease). Using SNAP (by the BROAD) I can input my search, choose my options (e.g. use 1000 genomes data, and an R^2 cut-off of 0.8) and search. ~5 SNPs are found to be in 'perfect' LD (R^2=1), but a further ~40 are still considered to be in linkage with the input-SNP because their R^2 values are above 0.8.

So in summary, both statements can be used correctly, but it is always more informative to state the degree of linkage (otherwise it might be assumed they are in perfect correlation).

mathematical software - Create djvu from jpeg - best practices and tutorial?

This is definitely not a mathematical question, but a relevant one I believe. There are incomplete versions of some books floating around the web and I want to put in the missing pages. There is a good book scanner at our university, albeit I have not really understood most of its functions yet. At the moment I am able to scan color JPGs. So I've got a batch of color JPGs, what next should I do? I want a djvu file.

I have tried cpaldjvu from djvulibre, but it seems to hang up on one single jpg. (Size 2MB.) Some people recommend passing through PDF, but this looks like a lot of overhead work to me. Is there a good tutorial for non-experts? (For Windows or Ubuntu - but bear with an Ubuntu noob who barely knows how to install packages. I am able, however, to script a few lines in bash.)

Besides, is pre-processing of the JPGs in a graphics editor helpful? Is it of use to cut out the margins, or are they useful for the DJVU encoder to approximate the background color?

PS. I think I know how to split DJVU files into pieces and reassemble them. I am only interested in JPG->DJVU here.

order theory - Weak partitioning vs. strong partitioning

If the lattice $U$ satisfies the meet distributive law
$$x wedge bigvee_{i in I} y_i = bigvee_{i in I} x wedge y_i$$
where $(y_i)_{i in I}$ is an arbitrary collection of elements of $U$, then "weak partitioning" implies "strong partitioning." More precisely, you only need the above to hold when the right hand side is $0$.

An example of a complete lattice where weak and strong partitioning are inequivalent is the lattice $U$ consisting of all closed subsets of ${1,frac12,frac13,ldots,0}$ (as a subspace of $mathbb{R}$) and the collection $S = {{frac1n}: n geq 1}$. The weak-partitioning property is easily verified since the points $frac1n$ are isolated. The strong partitioning property fails for the two sets $A = {{frac1{2n}}: n geq 1}$ and $B = {{frac1{2n+1}} : n geq 0}$, for example, since $bigvee A = overline{bigcup A}$ and $bigvee B = overline{bigcup B}$ both contain the point $0$.

PS: In your formulation of weak and strong partitioning, I interpret $S$ as a collection of nonzero elements of $U$, since "nonempty subsets" doesn't make much sense in context.

fractals - Hausdorff dimension of higher powers of the Mandebrot set ?

Yes, it does. See the full statement of Theorem 2 on page 6. The assumptions of the theorem are:

Suppose that a rational map $f_0$ of degree $d (> 1)$ has a parabolic fixed
point ζ with multiplier exp(2πip/q) ($p, q inmathbb{Z}, mathit{gcd}(p, q) = 1$) and that the immediate parabolic basin of ζ contains only one critical point of $f_0$.

This is the case for $z^d+c$.

nt.number theory - Finding zeroes of classical modular forms

I don't have an answer, but I can give some context for the positions of zeros (which you may already know). The dimension formula for the space of modular forms of weight k is essentially (# of zeros) + 1 - restrictions. Here is the formula for even k, taken from Shimura (Introduction to the Arithmetic Theory of Automorphic Functions); I believe he has formulas for odd weight as well.

The space of modular forms of even weight k on a subgroup G of SL₂(ℤ) with $I=[SL_2(mathbb{Z}): pm G]$, r₂ order-2 elliptic points, and r₃ order-3 elliptic points has dimension
$d = Ik/12 + 1 -(k/4 -lfloor k/4 rfloor )r_2 - (k/3 - lfloor k/3 rfloor)r_3 - g$.

The r₂ and r₃ terms come from the zeros required by the valence formula. The -g can be seen as coming from conditions imposed by Abel's Theorem. What's left gives us the degrees of freedom in placing zeros and getting a unique modular form, up to a constant multiple.

In your example, specifying a cusp form of a certain weight leaves a 1-dimensional space, and we know where all the zeros are. For weight 12 forms on SL₂(ℤ), we have genus 0 and don't need zeros at the elliptic points, so we have a 2-dimensional space. Specifying a zero at any point gives us a unique form: a zero at the cusp gives $Delta$, a zero (of degree 3) at the order-3 point gives $E_4^3$, a zero (of degree 2) at the order-2 point gives $E_g^2$. A zero anywhere else comes from some linear combination, but I don't know how to relate the linear combination to the position of the zero.

It's more complicated in the higher genus case, because in a space with dimension d=n+1-g, you can place n zeros anywhere you want, but there are g additional zeros in the fundamental domain, somehow determined by the locations of the first n.

linear algebra - problems concerning subspace of M_n(C)

1. "Non-invertible" means rank $leq n-1$, and thus the upper bound $nleft(n-1right)$ follows from the Theorem in paragraph 8.3 in Victor Prasolov's "Problems and theorems in linear algebra" (see here for a DVI file and here for a PDF version). (Scroll to page 58.) The reference given there is
Flanders H., On spaces of linear transformations with bound rank, J. London Math. Soc. 37 (1962), pp. 10-16.

2. We can WLOG assume that our subspace $N$ is actually a subalgebra of $mathrm{M}_nleft(mathbb Cright)$ (because otherwise, we can replace it by the subalgebra it generates, and it will still have the property that any two of its elements commute), so the question is how large a commutative subalgebra of $mathrm{M}_nleft(mathbb Cright)$ can get. This has been solved by I. Schur (see the 2 links in that topic).

4. Here the maximal dimension is $1$, and Petya has told why.

As for 3., I can prove the upper bound $frac{n^2}{2}$ (strangely enough, for $mathbb C$ only), but unfortunately there is room between it and the lower bound $frac{nleft(n-1right)}{2}$.

fractals - Determining a lower bound on the Hausdorff dimension of a set

Upper bound for the Hausdorff dimension is often easy, from the definition.

Lower bound can be harder. One method can be used if you have a measure on your set. Even better, a measure that naturally fits with the structure of the set. Then lower bounds for the Hausdorff dimension come from density computations for that measure.

(Would citing my own book here be considered crass?)

Packing dimension may be opposite. The lower bound is easy from the definition, but the upper bound harder. Again a density with respeact to a measure can help with this upper bound.

added March 4

This density theorem is found in: G. Edgar, Integral, Probability, and Fractal Measures (Springer 1998) Theorem 1.5.14, p. 52.

Definitions ... Let $E subseteq mathbb{R}^n$ be a Borel set, let $mu$ be a nonzero measure
on $E$, let $s>0$ be a real number. Write
$$B_r(x) = {y in E colon |y-x|le r}$$
for a closed ball. The upper $s$-density of $mu$ at a point
$x in mathbb{R}^n$ is
$$overline{D}^s_mu(x) = limsup_{r to 0} frac{mu(B_r(x))}{(2r)^s} .$$

A consequence of Theorem 1.5.14 is then: If
$sup_{x in E} overline{D}^s_mu(x) < infty$, then the Hausdorff dimension
of $E$ is at least $s$.

Dimension of subalgebras of a matrix algebra

Rough answer : almost all small dims can appear, there are some restrictions to
large dims.

For example, considering 1 matrix all dims between 1 and n appear.
Taking centralizers of these all numbers of the form sum a_i^2 where a is a partition
of n appear.

In general, consider k-tuples of positive integers a and b such that their scalar product
a.b=n (a should be thought of as the Morita setting, b as the matrix-sizes of the semi-simple part
of the subalgebra), then any number of the form

sum b_i^2 + subsum b_ib_j

is possible (here 'subsum' means that one takes all terms b_xb_y for all x,y in a
substring

1 <= i_1 < i_2 < ... < i_l <=k for any 0<=l<=k)

Edit : the subsum gives the dimension of the Jacobson radical. This answer cannot be the final one, as it only detects the subalgebras of global dimension 1. For example any n-diml algebra can be embedded in nxn matrices.

There are some obvious restriction wrt large dimensions. For example, there cannot be an 8-dml
subalgebra of 3x3 matrices as its semi-simple part can be at most C x M_2(C) and so its dimension must be
smaller or equal to 7.

For general n there cannot be subalgebras with dimensions between the dim of the largest parabolic
subgroup of GL(n) and n^2.

Edit : a closely related question can be found here : problems concerning subspaces of mxm matrices.

taxonomy - Is it correct to regard archeaic humans (i.e.n Neanderthals and Denisovans) as distinct species to Homo sapiens?

This question highlights the different species concepts.

If you go by the reproductive species concept (a population of actually or potentially interbreeding organisms), then yes. Apparently, the populations were interbreeding.

If you go by the typological species concept (morphologically distinct), then no. Homo neandertalensis and the "Denosovian" are morphologically distinct enough to be recognized as such.

ac.commutative algebra - Is completeness of a field an algebraic property?

I claim that, for a field $K$, the following are equivalent:
(i) $K$ can be given a nontrivial norm -- i.e., there exists $x in K$ with $|x| neq 0,1$.
(ii) $K$ admits a nontrivial rank one valuation $v$.
(iii) $K$ admits infinitely many inequivalent rank one valuations $v$ such that $(K,v)$ is not complete.
(iv) $K$ is not an algebraic extension of a finite field.

Some of these facts are proved in

http://math.uga.edu/~pete/8410Chapter2v2.pdf

(see e.g. Theorem 1).

Let me prove here that (iv) $implies$ (iii), which answers the OP's question in a rather definitive way.

1) Suppose first that $K$ has characteristic $0$. Then $K$ contains $mathbb{Q}$, which admits the $p$-adic valuations $v_p$. By Theorem 1 of loc. cit., each $v_p$ extends to a valuation on $K$.

Now suppose that $K$ has characteristic $p$ and contains an element $t$ which is not algebraic over $mathbb{F}_p$. Thus $K$ contains the rational function field $mathbb{F}_p(t)$, which carries infinitely many inequivalent nontrivial valuations $v_P$ corresponding to the irreducible polynomials $P in mathbb{F}_p[t]$ (and one more corresponding to the point at infinity on the projective line).

2) (F.K. Schmidt) If a field $K$ is complete with respect to two inequivalent rank one valuations, it is algebraically closed and uncountable. See e.g. Theorem 24 of

http://math.uga.edu/~pete/8410Chapter3.pdf

3) So we are reduced to the case in which $K$ is algebraically closed and uncountable. Then $K$ is isomorphic to the algebraic closure of $K(t)$. If we give $K$ the trivial valuation and $K(t)$ the Gauss norm $v$, then the algebraic closure of $K(t)$ has infinite degree over $K(t)$ so any extension of $v$ to the algebraic closure is not complete. The image of the Gauss norm $v$ under the group $PGL_2(K)$ of linear fractional transformations gives us infinitely more pairwise inequivalent valuations.

ds.dynamical systems - Local linearization of ODE at singular point

I would like the simplest example of the failure of an ODE to be locally diffeomorphic to its linearization, despite being locally homeomorphic to it. More precisely, consider x' = f(x) with f(0) = 0 in R^n. Let A = f'(0) so that the local linearization is x' = Ax. Suppose the eigenvalues of A all have nonzero real part (i.e., 0 is a hyperbolic critical point).

The Hartman-Grobman theorem tells us that there is a homeomorphism of a neighborhood of 0 which conjugates the system x'=f(x) to its linearization x'=Ax. If one reads the elementary `differential equations from the dynamical systems point of view' literature, however, you will gain the false impression that there is a diffeomorphism h : U --> U of a nhood of 0 which does this, and that further, one can even do this with h'(0) = I, the identity matrix. The point of this is to ensure that the trajectories of the nonlinear system are tangent to the trajectories of the linearization: if $h'(0)neq I$ then this may be false.

Smale's stable manifold theorem gives partial information in this direction, saying that the stable manifolds of the system and its linearization are tangent, and similarly for the unstable manifolds. In 2D, at a saddle, this is sufficient to imply that the separatrices of the original system are tangent to those of the linearization. For a node in 2D, or in higher dimensions, I am under the impression this need not hold. I even think I had worked out an example many years ago, which I no longer recall.

Any enlightenment on this issue would be much appreciated. I am not at all expert in these matters, so welcome any corrections, if I have distorted the facts. I am hoping for a 2 dimensional example.

Added later:
Yuri: resonances and normal forms are definitely relevant. When I get time I will look into the references you suggest.

Here's an example of what I am trying to avoid. Consider a flow on the unit disk with trajectories the radial lines y = mx. Conjugate by $(r,theta) mapsto (r,f(r,theta))$ where $f(0,theta)$ is constant on, say, $[-pi/2,pi/2]$, e.g. $f(r,theta) = rtheta$ on $[-pi/2,pi/2]$ and $(2theta-pi) + r(pi-theta)$ in the left half plane. Now all the trajectories leaving the unit circle in the right half plane approach 0 along the positive x-axis. So, conjugating with such a homeomorphism has replaced a single trajectory with horizontal tangent by an entire interval of such.

I strongly suspect that this sort of pathology doesn't happen with polynomial flows. Perhaps the normal forms will show this. What I would hope is that for each slope, there is a 1-1 correspondence between the trajectories in the original flow and its linearization approaching or leaving the singular point at that slope. In particular, that you can't have a single trajectory in the linearization but a whole interval of them in the nonlinear flow. A counterexample to this hope would be disappointing, but would settle the matter.

linear algebra - subspace separation and M-matrices

The separation between two square matrices $A$ and $B$, often used as a measure of the sensitivity of invariant subspace problems, is defined as
$$operatorname{sep}(A,B)=min_{Xneq 0}frac{leftVert AX-XBrightVert_F}{leftVert XrightVert_F}$$
(see e.g. Golub and Van Loan, Section 7.2.4).

I would like to express the separation between two M-matrices in terms of their Perron vector and values $Au=lambda u$, $Bv=mu v$. All I can do is estimating $operatorname{sep}(A,B)geq lambda+mu$. Is there any better bound, maybe from above? The question looks like an "eigenvalues vs. singular values" bound, so I am not sure that the answer is positive.

Alternatively, do you know any "handier" way to deal with $operatorname{sep}(A,B)$, other than using its definition and its alternative formulation as the smallest singular value of a Kronecker sum $sigma_{min}(B otimes I + I otimes A^T)$? I always find it unwieldy to use this definition, it is not easy to squeeze something simple to compute/estimate out of it. For instance, if $A$, $A'$, $B$ are M-matrices and $A'geq A$, does $operatorname{sep}(A',B)geq operatorname{sep}(A,B)$ hold?

ag.algebraic geometry - Is there a general projection formula for morphisms of ringed topoi?

In the context of sheaves of $mathcal O_X$-modules,
there is the following reference: Prop. 3.9.4 in Lipman's
Notes on derived functors and Grothendieck duality.
A closely related result is in Neeman's paper The Grothendieck duality theorem ...; see Prop. 5.3.

I'm not sure that analogous results should be expected to hold in arbitrary generality;
for example, both references place a restriction on the base scheme, and require quasi-coherence assumptions. (In some sense, one has to reduce to the locally free case,
where the statement is obvious. Quasi-coherent sheaves then admit locally free resolutions.
The proofs of the cited results apply some form of this argument in rather subtle and sophisticated ways.)

random matrices - A formula for moments of the limit distribution of singular values in the proof of the circular law

One of the steps in the proof of the circular law in random matrix theory is obtaining the limiting spectral distribution for the matrix

$(frac{1}{sqrt{n}} X_n - zI)(frac{1}{sqrt{n}} X_n - zI)^ast$,

where $X_n$ is an $n times n$ matrix with i.i.d. square integrable coefficients.

This is done with the Stieltjes transform, however Bai and Silverstein remark in their book that (under some assumptions on the random variables), one can also prove that moments of the empirical distribution converge almost surely to $mu_k(|z|^2)$ (they leave the details as an exercise).

It is indeed not difficult to show that the moments converge to a number which depends only on $|z|^2$. My question is whether there is a nice formula for $mu_k(|z|^2)$. For z = 0, we have just the Marchenko-Pastur distribution and there is a relatively good-looking formula involving binomial coefficients. For other values of $z$ we have some additional terms corresponding to some graphs (depending on $k$). This is enough to provide a moment proof of the convergence of the empirical spectral distribution, but I wonder if there is a nicer formula for the moments, e.g. involving only binomial coefficients and algebraic operations (no summation over combinatorial objects).

Why do Humans not produce Vitamin C like other mammals?

Humans do not produce Vitamin C due to a mutation in the GULO (gulonolactone oxidase) gene, which results in the inability to synthesize the protein. Normal GULO is an enzyme that catalyses the reaction of D-glucuronolactone with oxygen to L-xylo-hex-3-gulonolactone. This then spontaneously forms Ascorbic Acid (Vitamin C). However without the GULO enzyme, no vitamin C is produced.

This has not been selected against in natural selection as we are able to consume more than enough vitamin C from our diet. It is also suggested that organisms without a functional GULO gene have a method of "recycling" the vitamin C that they obtain from their diets using red blood cells (see Montel-Hagen et al. 2008).

A 2008 published study (Li et al. 2008) claimed to have successfully re-instated the ability to produce vitamin C in mice.

Simply as trivia: other than humans; guinea pigs, bats and dry-nosed primates have lost their ability to produce vitamin C in the same way.

---

References

• Li, Y., Shi, C.-X., Mossman, K.L., Rosenfeld, J., Boo, Y.C. &
  Schellhorn, H.E. (2008) Restoration of vitamin C synthesis in
  transgenic Gulo-/- mice by helper-dependent adenovirus-based
  expression of gulonolactone oxidase. Human gene therapy. [Online] 19
  (12), 1349–1358. Available from: doi:10.1089/hgt.2008.106 [Accessed:
  31 December 2011].




• Montel-Hagen, A., Kinet, S., Manel, N., Mongellaz, C., Prohaska, R.,
  Battini, J.-L., Delaunay, J., Sitbon, M. & Taylor, N. (2008)
  Erythrocyte Glut1 Triggers Dehydroascorbic Acid Uptake in Mammals
  Unable to Synthesize Vitamin C. Cell. [Online] 132 (6), 1039–1048.
  Available from: doi:10.1016/j.cell.2008.01.042 [Accessed: 31 December
  2011].

oc.optimization control - Optimization over permutation?

It may be the case that simulated annealing and genetic algorithms are relatively complicated to understand, bound and implement in this instance.

Instead, a very easy starting point would be a simple hill-climbing algorithm.

Start with an arbitrary (or better, random) initial permutation $pi$.

The set of moves is the set $M$ of permutations that you can reach by transposing two elements of the permutation.

While there is a move that decreases $f$,

• Make the move to reach a new current permutation.




• Compute the new set of moves (or rather, their profits $f(pi) - f(pi')$ for a move reaching $pi'$).

This will get you to a local minimum at a cost of $O(n^2)cdot C(n)$, per move, where $C(n)$ is the cost of calculating $f(pi)$ for a permutation of $[n]$.

Extremely simple and probably not too costly as a first step. You may be able to prove some sort of worst case bound between a local optimum and a global optimum.

fa.functional analysis - Subspaces of $L^{2}$

[In what follows $0^{0}$= 1 by convention.]

Is there some closed infinite dimensional linear subspace $F$ of $L^{2}(0,1)$
such that $left|fright|^{left|fright|}$ belongs to $L^{2}(0,1)$
for all $f$ in $F$ ?

This problem is related to the Erdos - Shapiro - Shields paper [ESS].
From this paper it follows that the answer is negative if $left|fright|^{left|fright|}$ is replaced by $left|fright|^{left|fright|^{2}}$.

Some thoughts. Suppose that such an $F$ exists, and take some $p > 2$.
Let $f$ be in $F$.

Then clearly $g:=(p/2)cdot f$ is in $F$, too, hence $h :=left|gright|^{left|gright|}$
belongs to $L^{2}(0,1)$.

Next, it is easy to see that $leftVert frightVert _{p}^{p}leq1+leftVert hrightVert _{2}^{2}<+infty$.

Therefore, $F$ is contained in $L^{p}(0,1)$ as a linear subspace
(i.e., algebraically).

Now, applying the Closed Graph Theorem to the natural linear embedding
$j:(F, ||.||_{2})rightarrow L^{p}(0,1)$, it follows that $j$ is
continuous. Consequently, the Hilbertian 2-norm and the $p$-norm
are equivalent on $F$. Moreover, it follows that $F$ is complete
w.r.t. the $p$-norm, and, in turn, it is a closed subspace of $L^{p}(0,1)$.

And this is true for all $p > 2$.

[ESS] http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.mmj/1028999306