nt.number theory - Inequality with Euler's totient

Using the first 100,000 values of $varphi(n)$ it seems that the following is true.

Let $mathcal A$ be a finite subset of $mathbb{N}$, $forall nin mathbb{N} setminus mathcal{A}$, $displaystyle frac{1}{varphi(2n)} - frac{1}{varphi(2n+1)} geqslant frac{1}{2nln (2n)}$.

Is this true? Is there a stronger lower bound?

P.S.: I looked at Handbook of Number Theory I by Mitrinović and Sándor which has a lot of info about $varphi (n)$ but it doesn't appear there.

dna - How can you identify if a person is homozygous for a certain allele?

You could use a 3-primers strategy, where you have a common primer, one that only amplifies the mutant allele and one that only amplifies the wt. This may or may not be feasable depending on the type of mutation.
DNA from het people will amplify both product, while homozygous will only amplify one (wt or mutant).

Of course then, linking the mutation of a gene to the lack of a chemokine is not necessarily straightforward.

To be honest, however, I would use a different approach: take people who don't produce the chemokine, and people who do (simply by dosing the chemokine in the blood). Now sequence the gene in the two groups and look for mutations.

ag.algebraic geometry - Computing 3 points Gromov-Witten invariants of the Grassmannian

This is from an exercise in Koch, Vainsencher - An invitation to quamtum cohomology.

Background

The exercise asks to compute the 3-points Gromov-Witten invariants of the Grassmannian $G = mathop{Gr}(1, mathbb{P}^3) = mathop{Gr}(2, 4)$ via the enumerative interepretation. In particular my problem is with computing the invariant $I_2(p cdot p cdot p)$, where $p$ is the class of a point on $G$. This is the number of rational curves of degree $2$ through $3$ generic points on $G$. Here we see $G$ as embedded by the Plucker map, and the degree is defined accordingly.

A rational curve $C subset G$ of degree $d$ will sweep out a rational ruled surface $S$ of degree $d$ in $mathbb{P}^3$; up to here I agree with the hints of the book. The problem is the following hint:

Show that the condition on $C$ of passing through a point $q in G$ corresponds to the condition on $S$ of containing the line in $mathbb{P}^3$ corresponding to $q$.

This seems to me plain false. Of course one implication is true, but is absolutely possible that $S$ contains a line without $C$ passing through the corresponding point.

For instance, when $d = 1$, $C$ is a line on the Grassmannian, and it is well-known that these have the form ${ ell mid a in ell subset A }$, where $a$ is a point and $A$ a plane of $mathbb{P}^3$. In this case $S$ is the plane $A$, so it contains many lines which do not pass through $a$, hence these lines are not parametrized by $C$.

Similarly, when $d = 2$, the surface $S$ can be a smooth quadric, which has two distinct rulings of lines; one will correspond to lines parametrized by $C$, but the other one will not. To see that a smooth quadric can actually arise, just invert the construction. Starting from a smooth quadric $S$ take any line $ell subset S$. There is a natural map $ell to G$ given by sending a point $q in ell$ to the unique line in the other ruling passing through $q$. The image of this map is a curve $C subset G$, such that the associated surface is $S$ itself.

Given the hint, the book goes on to say

Show that $I_2(p cdot p cdot p) = 1$, by interpreting this number as a count of quadrics containing three lines.

Now I certainly agree that given three generic lines in $mathbb{P}^3$ there is a unique quadric containing them. To see this, just choose $3$ points on each line: a quadric will contain the lines iff it contains the $9$ points, and it can be shown that these $9$ points give $9$ independent conditions.

Still I do no see how this implies the count $I_2(p cdot p cdot p) = 1$. What I guess happens is that generically we will have two lines in one ruling and one line in the other, so that the curve $C subset G$ which sweeps $S$ will only pass through one or two of the assigned points.

Question

What is the right count? Is there something wrong in what I said above? Is it even true that $I_2(p cdot p cdot p) = 1$?

molecular biology - How do I clean phenol contaminated RNA without losing any of the sample?

I recently extracted RNA from developing plant leaves for the first time, as part of a very long and intensive experiment. The samples were extremely precious because of the amount of effort that went into obtaining them (harvesting thousands of miniscule leaves, one from each plant, to get the required mass).

I extracted the RNA with TRIzol and chloroform. Nanodrop showed excellent yield as you would expect for actively growing young tissue, but some of the samples had really low 260/230 ratios. I know this suggests phenol or salt contamination, but what can I do to clean the samples without losing any of the precious RNA? And how can I avoid the contamination in the future?

nt.number theory - An elementary number theoretic infinite series

For a positive integer k, let d(k) be the number of divisors of k. So d(1)=1, d(p) =2 if p is a prime, d(6)=4, and d(12)=6.

What is the precise asymptotics of SUM_{k=1}^n 1/(kd(k))

Background:

1) This came up on the side in the polymath5 project.

2) There, Tim Gowers wrote: If nobody knows the answer, maybe that’s one for Mathoverflow, where I imagine a few minutes would be enough.

3) Asked: 14:17 Jerusalem time. (The first accurate answer: 17:44 Jerusalem time.)

4) Looking only at primes or only at integers with a typical number of divisors suggested a loglogn behavior, but looking at semiprimes indicates the sum is larger. I dont know how much larger.

5) I couldn't find an asnwer on the web. If there is an easy way searching for an answer that I missed this will be interesting too.

Great answers!! thanks. What about the sum

$sum_{k=1}^n 1/(kd^2(k))$ ?

arithmetic geometry - The monodromy-weight-, Ramanujan-, Langlands-landscape

Dear Thomas,

This "landscape" is, I think, a sketch of the proof of the following theorem of Taylor and Yoshida: if $Pi$ is a self-dual cuspdidal automorphic form on $GL_n$ over $E$ (a CM field)
(satisfying some further technical conditions) and $rho$ is the associated $n$-dimensional
Galois representation (constructed by Harris and Taylor in their book "The geometry and cohomology of some simple Shimura varieties"), then the local factors of $Pi$ at any prime
$p$ of $E$ matches, via local Langlands, with the restriction of $rho$ to a decomposition group at $p$.

What was proved in Harris--Taylor was that this matching is correct, up to the question
of matching the $N$ on each side. What Taylor and Yoshida verified is that the $N$ on each side
also matches.

The top part of the landscape represents the reduction to the unipotent situation (i.e. the context in which $Pi$, locally at $p$, has an Iwahori fixed vector --- the analogue
of classical level $Gamma_0(p)$), by
base-changing to an extension of $E$. On the automorphic side, this is the process
labelled by the names Arthur--Clozel--Selberg; on the Galois side, this is just restricting
from $Gal(overline{E}/E)$ to $Gal(overline{E}/E')$ for some appropriately chosen
extension $E'$ of $E$. If one thinks of $rho$ as appearing in the cohomology of a Shimura
variety (which is, after all, how it is constructed), then this just corresponds to
base-changing the variety from $E$ to $E'$, which is why this process is labelled as
geometric base change in the "landscape".

On the lower right of the diagram, one has the generalized Ramanujan conjecture, stating that the local factor of $Pi$ at $p$ should be tempered,
which in turn implies that the local (at $p$) Galois representation (more precisely,
Weil--Deligne representation) attached to this local factor satisfies the monodromy
weight conjecture. This temperedness was proved by Harris--Taylor.

Now we already know that $rho$ locally at $p$ matches with the local factor of $Pi$ at
$p$ up to $N$, and it is not hard to show that there is a unique way to add $N$ so as
to obtain a local Weil--Deligne representation satisfying the monodromy weight conjecture.
So to prove their theorem, Taylor and Yoshida are reduced to proving that $rho$, locally
at $p$, satisfies the monodromy weight conjecture.
They do this via an application of the Rapoport--Zink spectral sequence and a careful analysis of the bad reduction of the Shimura variety in whose cohomology $rho$ lives. This is represented in the lower left part of the diagram.

The very bottom part of the diagram on the left represents the fact that a priori one knows
that $rho$ is mixed, i.e. its semi-simplification has Frobenius eigenvalues that are
Weil numbers of various weights. But the main part of the landscape here is the monodromy weight conjecture, which describes the precise relationship between the Frobenius eigenvalues and the $N$ operator.

To prove the MWC in their context, Taylor and Yoshida
use the interplay between the geometry of the
special fibre of the Shimura variety and the representation theory of $Pi$ that is the main subject of Harris and Taylor's book, as well as Section 2 of Taylor and Yoshida's article. In particular, the fact that $Pi$, locally at $p$, is tempered unitary, and is assumed to have an Iwahori fixed vector, puts strong restrictions on its structure (using the known classification of unitary reps. of $GL_n$ over local fields; this is why Tadic's name appears on the right hand side of the landscape), which when fed over to
the geometric side implies that the RZ spectral sequence degenerates at $E_1$, giving the desired monodromy weight conjecture.

My suggestion is that if you want to understand this in more detail, you should read Taylor and Yoshida's article. Start at the very end of the paper, where the main theorem is proved (i.e. the paragraph beginning "We can now conclude ... "). The lemmas referred to in section 1 are more or less elementary. Theorem 3.2 is the heart of the argument; it is where degeneration of the RZ spectral sequence is proved. One can try to read it more or less formally, taking various assertions as a black box,
at least to see what role the temperedness of $Pi$ locally at $p$ plays. The earlier parts of Section 3 are just establishing notation, and making contact with the book of Harris--Taylor. Section 2 is devoted to establishing the basic properties of the semi-stable models of the Shimura varieties in whose cohomology $rho$ lives; I recommend treating it as a black box on first reading.

Added: First, I should note that the references I make are to the version of Taylor--Yoshida that is currently posted on Taylor's web-page, which I am told may differ quite substantially in its organization from the published version of the paper.

Also, let me add something about the role of the classification of unitary representations
of $GL_n$, which will help illuminate the structure of the lower part of the landscape:
First, one uses the general result that geometrically obtained Galois representations are mixed (i.e. have Frobenius eigenvalues that are Weil numbers), coupled with the local-global compatibility without the $N$, to deduce that the Frobenius eigenvalues
of the Weil--Deligne representation attached to the local factor of $Pi$ at $p$ are Weil numbers. Second, results of Tadic on the classification of unitary representations of $GL_n$ of $p$-adic fields greatly restrict the structure of this
local factor (since it is both unitary and generic, being the local factor of a cuspidal
automorphic representation for $GL_n$). Finally, when this is combined with the fact that
the Weil--Deligne rep'n associated to it via local Langlands is mixed, ones sees that this
local factor is forced to be tempered. This is how Harris--Taylor deduce temperedness;
it is an analogue at $p$ of an argument at the archimedean prime made by Clozel in his Ann Arbor paper. (See Lemma 4.9 on p.144 of volume I of the Ann Arbor conference. A scan
is available on Jim Milne's web-page here,
but note that it is quite a big file.)

Finally, let me now explain how to correctly read the landscape: one starts in the lower left, following the arrow. When you come to a bridge, you cross the river from the motivic/Galois side to the automorphic side, or back again, continuing to follow the arrows. The areas marked with
x's are impenetrable (or, at least, you don't try to cross them directly --- e.g. you don't prove GRC directly, you don't prove WMC directly, you don't study the general semi-stable reduction problem directly); the only way to proceed is by crossing the river. This then gives
the structure of the Taylor--Yoshida argument.

Are supervector spaces the representations of a Hopf algebra?

As a monoidal category, supervector spaces are the same as $mathbb{Z}/2mathbb{Z}$ representations, so you can think of them as representations of the Hopf algebra $mathbb{C}[mathbb{Z}/2mathbb{Z}]$.

However, the symmetric structure is different, so the thing you need to do is make $mathbb{C}[mathbb{Z}/2mathbb{Z}]$ into a quasi-triangular Hopf algebra in an interesting way, that is, change things so that the map from $Votimes Wto Wotimes V$ isn't just flipping, it's flipping followed by an element of $mathbb{C}[mathbb{Z}/2mathbb{Z}]otimes mathbb{C}[mathbb{Z}/2mathbb{Z}]$ which is called the R-matrix. I'll leave actually writing this element as an exercise to the reader, but it's uniquely determined by acting by -1 on sign tensor sign and by 1 on everything else.

You may want to have a look at the relevant Wikipedia article.

pr.probability - Google question: In a country in which people only want boys

I think this is already implicit in the heavily up-voted answer, but it may be worth clarifying: there are two kinds of expectations that we can talk about.

The first is the distribution of G/B, G/(G + B), B/G, B/(B + G), values for the entire population (along with its expected value, standard deviation, etc.). Here, the distribution is over all possible "runs of history", so to speak, in the sense that we average over all possible ways history could turn out. If the population is large enough (thousands? millions?), then the expected values of all these quantities are what you would expect from a 50:50 split, and the standard deviations are near zero. Thus, as far as demographic estimations of the overall population are concerned, 50:50 is the way to go. In fact, at the population level, the ratio of girls to boys cannot be influenced by stopping strategies; any influence must either (i) affect the relative probability of conception of male versus female fetus (ii) adopt a post-conception filtering mechanism, such as induced abortion or infanticide).

The second is the expected G/B, G/(G + B), B/G, B/(B + G), etc., values over families. More generally, we may be interested in the distribution of different (G,B) values for different families. If we are interested in understanding family dynamics more thoroughly, we may also be interested in the birth orders, i.e., in what order girls and boys arise. Here, family stopping strategies could affect the distribution of (G,B) values and also of the birth orders. In particular, the strategy here ("stop as soon as you have a boy") gives 50% of the families with a single boy, 25% with one (older) girl and one (younger) boy, 12.5% with two older girls and one younger boy, and so on (assuming the complication of twins and triplets does not arise). This could have important demographic implications in the long term, when mating is done for the next generation (since birth order and the age gaps between children and their parents all play a role in mating and the creation of chlidren). However, that is getting beyond the current question.

For this second sense, it is not just the expected value per family that matters, but rather, the specific distribution of families. As already pointed out, since the variables are not independent, E[G/B] is not the same thing as E[G]/E[B], so what variable we choose to average over affects what answer we get. Looking at the whole distribution conveys more information.

When demographers are making short-term population estimates, it is the first sense (expected values for the population over runs of history) that is relevant, so stopping strategies can be discounted unless they are accompanied by post-conception selective strategies or strategies that affect conception probabilities. A deeper understanding of society would require knowing things in both the first and the second sense.

nt.number theory - Subfields joining an algebraic element to another

EDIT: Okay, wrong. Sorry for spamming.

This looks just too easy, so I guess I'm doing something stupid.

I'll prove that

(a) whenever a subfield $K$ of $mathbb{C}$ satisfies $betain Kleft[alpharight]$, then $betainleft(Kcapmathbb{Q}left(alpha,betaright)right)left[alpharight]$.

Adding to this the trivial observation that

(b) whenever a subfield $K$ of $mathbb{C}$ satisfies $betanotin K$, then $betanotin Kcapmathbb{Q}left(alpha,betaright)$,

we see that whenever a subfield $K$ of $mathbb{C}$ joins $alpha$ to $beta$, its subfield $Kcapmathbb{Q}left(alpha,betaright)$ does the same. This obviously settles 1) (even without the normal closure) and therefore 2).

So let's prove (a) now: Since $betain Kleft[alpharight]$, there exists a polynomial $Pin Kleft[Xright]$ such that $beta=Pleft(alpharight)$. Since $Kcapmathbb{Q}left(alpha,betaright)$ is a vector subspace of $K$ (where "vector space" means $mathbb{Q}$-vector space), there exists a linear map $phi:Kto Kcapmathbb{Q}left(alpha,betaright)$ such that $phileft(vright)=v$ for every $vin Kcapmathbb{Q}left(alpha,betaright)$ (this may require the axiom of choice for infinite $K$, but if you want to consider infinite field extensions of $mathbb{Q}$ I think you can't help but use the axiom of choice). Applying the linear map $phi$ to every coefficient of the polynomial $Pin Kleft[Xright]$, we get another polynomial $Qin left(Kcapmathbb{Q}left(alpha,betaright)right)left[Xright]$ which also satisfies $beta=Qleft(alpharight)$ (since all powers of $alpha$ and $beta$ lie in $Kcapmathbb{Q}left(alpha,betaright)$ and thus are invariant under $phi$). Thus, $betainleft(Kcapmathbb{Q}left(alpha,betaright)right)left[alpharight]$, qed.

Can anyone check this for nonsense?

computational complexity - A polynomial-time algorithm for deciding whether a language has a polynomial time algorithm

For any NP-complete problem, search and decision are polynomially related to each other.

If we can find solutions in polynomial time then surely we can decide if a solution exists in polynomial time.

On the other hand, using self reducibility of SAT, we can show that the search problem can be solved in polynomial time using an oracle to the decision version of SAT. Here's the technique:

Suppose I am given formula F, a SAT instance on n variables, and an oracle to decide satisfiability. To solve the search problem, we show how to extend any particular partial solution by fixing a value for one more variable. Then we just start with the empty assignment and repeat this process n times.

Given F, first use Oracle to decide if F has a solution, and if it doesn't, then report Fail. Assuming that it does, we will now find a solution.
Take the first variable of F, call it X_1 (any arbitrary variable will do), and plug in True for it, simplifying F accordingly. Then take this resulting formula and give it to the SAT oracle. If by hypothesizing that X_1 = True, we have now made it so that there is no solution to F, then we know that any solution will have X_1 = False. If the oracle said that there are still solutions when X_1 = True, then we retain this partial assignment and proceed. Whatever value we decided on for X_1, we plug that into F and simplify, then repeat for X_2 ... X_n. At the end we must have found a full solution.

This property is called self-reducibility of SAT -- the point is that SAT on instances of length n can be solved in polynomial time with oracle access to SAT on instances of length n-1. Clearly any other NP-complete problem has a similar self-reduction - for instance with HAM CYCLE, I could take a vertex with more than 2 edges, and then make smaller graphs by deleting one of its edges. Polynomially many graphs result this way, and each is smaller then the initial graph. If one of them has a HAM CYCLE, I can just focus on that smaller graph and start deleting edges from it... eventually, I will be left with one massive Hamiltonian cycle. If none of them has a HAM CYCLE, then I know the original graph didn't have one either.

Additionally, many NP problems that are not NP-complete will have search to decision reductions. For instance, Graph Isomorphism. Along slightly different lines, problems like Discrete Logarithm have what is called Ransom Self Reducibility -- if you have an oracle that solves a large fraction of smaller instances of a problem successfully, then you can solve the problem on a larger input size. This kind of property allows you to reduce worst case to average case, and so a way to try to establish Average Case hardness of a problem, which is important for Cryptography.

Not all NP problems are known to be self-reducible though. Although many common ones are, the result in this paper rules out any simple proof for every single problem in NP.

http://www.google.com/url?sa=t&source=web&cd=5&ved=0CDEQFjAE&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.157.3658%26rep%3Drep1%26type%3Dpdf&ei=02VmTMjIC4K8sQPW0OSXDQ&usg=AFQjCNEvu2rttkpbEQ7X0C9MIlrU-FIgJA&sig2=k7eTQI6BgHMTaIMv312UXA

Your question is also tangentially related to the Dichotomy Conjecture for CSPs. The problem can be posed as follows. Given any particular CSP language, determining if a particular CSP in that language is satisfiable is an NP problem. For some CSP languages, the corresponding problem is NP-complete, for instance 3SAT, while for others such as XORSAT, the problem is known to be in P. Is it true that, for every CSP language, the corresponding problem will be solvable in polynomial time OR NP-complete? Given a description of a particular CSP language, can we determine in polynomial time whether the corresponding problem is solvable in Polynomial Time or NP-complete? There has been much work and a resurgence of interest in this problem in recent years, and it seems that top researchers are getting close to resolving it in the affirmative.

Is there a relationship between model theory and category theory?

Between model theory and category theory broadly conceived: not anything really compelling, because a category, on its own, does not stand as an interpretation for anything.

Between model theory and categorical logic, however: yes, I think the overlap is large.

A spot of history: the man most deserving, in my opinion, of being called the father of model theory is Alfred Tarski, who came from a Polish school of logic that, I understand, was very much within the algebraic school. His model theory was more in the vein of a reworking of the Polish-style algebraic logic (this is not, in anway, to talk down his achievement).

Blackburn &al (2001, pp40-41) talk of a might-have-been for the Jónsson-Tarski representation theorem:

...while modal algebras were useful tools, they seemed of little help in guiding logical intuitions. The [theorem] should have swept this apparent shortcoming away for good, for in essence they showed how to represent modal algebras as the structures we now call models! In fact, they did a lot more that this. Their representation technique is essentially a model building technique, hence their work gave the technical tools needed to prove the completeness result that dominated [work on modal logic before Kripke].

They go on to present a nice anecdote showing how Tarski did not seem to think this algebraic approach provided a semantics for modal logic, even after Kripke stressed how important it was to Kripke semantics. It seems that sometimes algebraic logic and model theory are more similar than they appear.

Like model theory, categorical logic can seem to be a special way of doing algebraic logic. And with some theories, model theory and algebraic logic sometimes seem to differ only in trivialities; with categorical logic I am more hesitant in making sweeping judgements, but it sometimes feels that way to me too.

Ref: Blackburn, de Rijke, & Venema (2001) Modal Logic, CUP.

at.algebraic topology - singular homology of a differential manifold

Let M is differential manifold, $Delta$ is the closed simplex $[p_0, p_1,...,p_k]$. A differential singular k-simplex $sigma$ of M is a smooth mapping $sigma:Delta -> M$.

And we construct a chain complex in the same way we construct the chain complex of singular homology, we gain its homology group.

My question is why this homology group equals the singular homology group? I have tried finding in many books but there is no answer of this question.

ag.algebraic geometry - Normal bundle to a double line in quartic threefold

Let $X$ be your threefold (I assume it is smooth) and $ell subset X$ a line. We have the Gauss map $ell rightarrow mathbb{P}^2$ which associates ot a point x the tangent $T_x X$. Here the target $mathbb{P}^2$ is the space of hyperplanes containing $ell$.

Since the map is given by derivatives of an equation of $X$, it has degree $3$, so it is either 1:1 on a cubic or 3:1 on a line. In the first case the cubic spans the whole $mathbb{P}^2$, so the intersection of all tangent hyperplanes along $ell$ is $ell$ itself. In the second case there is a plane $P supset ell$ which is everywhere tangent along $ell$.

I believe if the double line is contained in $X$ we are in the second case. Now these two cases can be used to distinguish the normal of $ell$ in $X$ as follows. First we can compute by adjunction $c_1(N_{ell, X}) = -1$. Since a vector bundle on a line splits, we must have $N_{ell, X} = mathcal{O}(e_1) oplus mathcal{O}(e_2)$, with $e_1 + e_2 = -1$. Since this is a subbundle of $N_{ell, mathbb{P}^4} = bigoplus mathcal{O}(1)$, each $e_i leq 1$, leaving the two cases you mentioned, namely $(e_1, e_2) = (0, -1)$ or $(1, -2)$.

Now it comes the part where I actually did not do the computations, but it should be the same as the case of a cubic fourfold, where I have worked everything out. Namely you can distinguish the two cases according to the number of sections of $N_{ell, X}$. You have to write explicitly a generic section of $N_{ell, mathbb{P}^4}$; these form a space of dimension $6$.

Then you impose that such a section is actually tangent to $X$; this lowers the dimension by something which depends on the derivatives of $X$. If you do the computation, you will find that this dimension is different according to the two cases I have described above. I believe it turns out that $h^0(ell, N_{ell, X} = 1$ in the first case and $2$ in the second (which should be the one where the line is double).

A final remark: to perform the above computation it may be easier to observe that the normal exact sequence for the inclusion of the line into $X$ splits and work with sections of $T_X |_ell$.

gr.group theory - Fox Calculus and Cohomology.

A 2-group? You are tough cookie. For a knot group, Crowell-Fox's book on knot theory does a nice job. In general its just an observation about the module structure of the CW groups of a normal covering space of your CW complex, where you are working over the group ring of the deck transformations. It only works for computing the 0th and 1st homology groups. Maybe you meant two complex. :) In which point it works for every homology group.

ag.algebraic geometry - Euler-Maclaurin formula and Riemann-Roch

Let $Df$ denote the derivative of a function $f(x)$ and $bigtriangledown f=f(x)-f(x-1)$ be the discrete derivative. Using the Taylor series expansion for $f(x-1)$, we easily get $bigtriangledown = 1- e^{-D}$ or, by taking the inverses,
$$frac{1}{bigtriangledown} = frac{1}{1-e^{-D}} = frac{1}{D}cdot frac{D}{1-e^{-D}}= frac{1}{D} + frac12+ sum_{k=1}^{infty} B_{2k}frac{D^{2k-1}}{(2k)!} ,$$
where $B_{2k}$ are Bernoulli numbers.

(Edit: I corrected the signs to adhere to the most common conventions.)

Here, $(1/D)g$ is the opposite to the derivative, i.e. the integral; adding the limits this becomes a definite integral $int_0^n g(x)dx$. And $(1/bigtriangledown)g$ is the opposite to the discrete derivative, i.e. the sum $sum_{x=1}^n g(x)$. So the above formula, known as Euler-Maclaurin formula, allows one, sometimes, to compute the discrete sum by using the definite integral and some error terms.

Usually, there is a nontrivial remainder in this formula. For example, for $g(x)=1/x$, the remainder is Euler's constant $gammasimeq 0.57$. Estimating the remainder and analyzing the convergence of the power series is a long story, which is explained for example in the nice book "Concrete Mathematics" by Graham-Knuth-Patashnik. But the power series becomes finite with zero remainder if $g(x)$ is a polynomial. OK, so far I am just reminding elementary combinatorics.

Now, for my question. In the (Hirzebruch/Grothendieck)-Riemann-Roch formula one of the main ingredients is the Todd class which is defined as the product, going over Chern roots $alpha$, of the expression $frac{alpha}{1-e^{-alpha}}$. This looks so similar to the above, and so suggestive (especially because in the Hirzebruch's version
$$chi(X,F) = h^0(F)-h^1(F)+dots = int_X ch(F) Td(T_X)$$
there is also an "integral", at least in the notation) that it makes me wonder: is there a connection?

The obvious case to try (which I did) is the case when $X=mathbb P^n$ and $F=mathcal O(d)$. But the usual proof in that case is a residue computation which, to my eye, does not look anything like Euler-Maclaurin formula.

But is there really a connection?

---

An edit after many answers: Although the connection with Khovanskii-Pukhlikov's paper and the consequent work, pointed out by Dmitri and others, is undeniable, it is still not obvious to me how the usual Riemann-Roch for $X=mathbb P^n$ and $F=mathcal O(d)$ follows from them. It appears that one has to prove the following nontrivial

Identity: The coefficient of $x^n$ in $Td(x)^{n+1}e^{dx}$ equals
$$frac{1}{n!} Td(partial /partial h_0) dots Td(partial /partial h_n) (d+h_0+dots + h_n)^n |_{h_0=dots h_n=0}$$

A complete answer to my question would include a proof of this identity or a reference to where this is shown. (I did not find it in the cited papers.) I removed the acceptance to encourage a more complete explanation.

noncommutative topology - Sources for exact triangles in triangulated categories.

This question has kind of been bothering me since I started thinking about it - I am far from an expert on KK-theory but I thought I'd throw something out there and maybe someone else will see it and come along and agree with me or correct me.

I think this statement is a way of thinking rather than something precise. Indeed by definition every distinguished triangle in KK is an isomorph of an extension triangle (although in the equivariant case I believe life is not so simple). Alternatively one can define the triangulation by taking distinguished triangles to be those candidates triangle (i.e. $Xto Yto Z to Sigma X$ where each pair of composites vanishes) which are isomorphic to mapping cone triangles. So this is really all one has. The same story is true in the derived category of an abelian category for instance.

But (here is the punchline) one does not generally build the triangles one needs to prove things by considering short exact sequences of chain complexes! Indeed, one of the virtues of triangulated categories is that one has the ability to produce lots of new objects and triangles starting with very little. Often it is hard/impossible to do this in any explicit way - in fact one generally just knows that some collection of triangles doing the job exists and has no idea what they look like. So even though every triangle one might construct is (up to KK equivalence) an extension there is a very good chance that one didn't obtain it by writing down an explicit extension.

I guess there is also the fact that a triangle which is just isomorphic in KK to an extension triangle is not itself literally an extension of $C^*$-algebras. I don't know the stuff well enough to know whether or not one can produce interesting triangles via other constructions where there is a guarantee that some extension exists to make it distinguished. This is entirely possible (and in my opinion viewing such a construction as a different source of triangles is a worthwhile psychological distinction).

sleep - Is it possible to live without health problems sleeping one day and not the other?

(too long to be a comment)

You may be interested in http://en.wikipedia.org/wiki/Phase_response_curve.

This graph shows how the body's circadian rhythm normally works: http://en.wikipedia.org/wiki/File:Body_Temp_Variation.png. Body temperature decreases during the night (apparently due to more melatonin production.

I conjecture that the proposed schedule would interfere with the Circadian rhythm. Melatonin is the hormone that regulates sleep--it causes drowsiness. It is suppressed by blue light (because we get exposed to blue light in the daytime).

Aside from this, I am also very interested in the effects because I have personally wondered about the same question. The thing I am worried about is significant immunosuppression.

A larger question might be--"Why is sleep necessary?" Does it serve only to conserve food (which is very useful if you are living on subsistence) or does it serve a greater purpose? (whenever I have asked anyone about it, they always cite "regeneration" and some have cited the recycling of neurotransmitters. Personally, I'm a little skeptical.)

One final study: there was a study by Dement on the effect of dream deprivation: he took several people and woke them up whenever they went into REM sleep. Then, there was a period when the patients were not woken up. He found that there was a "REM rebound"--that they would go into more REM sleep after they had been deprived of it. This seems to indicate that dreaming, specifically, may serve a significant purpose.

lo.logic - Graph properties and infinite FOL sentences

Let me suppose for simplicity at first that we are speaking here just of countable graphs. There are continuum many isomorphism types of countable graphs, and any collection of such isomorphism types would seem to constitute a property of countable graphs. Thus, there are $2^{2^omega}$ many properties of countable graphs.

If your infinitary logic does not have this many sentences, therefore, then clearly not every property can be described by an infinitary sentence. For example, if as you seem to, you only allow countable conjunctions, disjunctions and quantifications, so that every sentence is countable, then there are only continuum many sentences, but more than continuum many properties.

If you are more generous with the infinitary sentences, by allowing larger iterated disjunctions (but still just countable quantifications in any one block of quantifiers), then the answer is yes. The reason is that every countable graph $G$ is uniquely specified up to isomorphism by a sentence $sigma_G$ in infinitary logic saying: there are such-and-such vertices connected in exactly such-and-such way and no other vertices (according to what is true in the particular graph $G$). This assertion, which is expressible provided that we have countable conjunctions and quantifications, is true in a graph exactly when it is isomorphic to $G$. Now for any property $P$, let $Gamma_P$ be the disjunction over all $sigma_G$ among the $G$ with property $P$, which will be a size at most continuum disjunction, if we use at most one $G$ of each isomorphism type. The sentence $Gamma_P$ is true of a countable graph exactly when that graph has property $P$. (The same idea works for uncountable $G$ by allowing larger quantifier blocks and disjunctions.)

I take this answer to show that one needs to be more specific about which infinitary logic is to be used. If the logic is too generous, then the infinitary language doesn't seem really to give any insight to the nature of the graphs, since it amounts to describing the property just by listing the graphs that have that property, and we can already do this in our ordinary mathematical treatment of graphs, without any formal language. But when the logic is restricted, for example, if you consider a specific infinitary logic $L_{kappa,lambda}$ and focus in detail on what is describable in that logic, then interesting answers may emerge. The answer above shows that larger logics will be more expressive.

Finding all paths on undirected graph

There is an easy way to partition the set of $s$-$t$ paths in a graph $G$. Fix an edge $tt'$ in $G$. Let $P_1$ be the set of paths from $s$ to $t$ which use the edge $tt'$, and let $P_2$ be the set of paths from $s$ to $t$ in $G-tt'$. Then $P_1 cap P_2 = emptyset$ and the set of $s$-$t$ paths $P = P_1 cup P_2$. Moreover, there is a one to one correspondence between the set of paths $P_1$ and the set of $s$-$t'$ paths in the graph $G-t$.

Thus, we get an easy recursive algorithm to find the set of paths $s$-$t$ paths in a graph $G$. Pick an edge $tt'$ incident the vertex $t$ and recursively calculate the sets $P_1$ and $P_2$. With a small amount of pre-processing, we can ensure that the runtime is $O(m(p+1))$ where $m$ is the number of edges and $p$ is the number of $s$-$t$ paths.

To make the recurrence relation on the runtime work, consider the following. We can test in time $O(m)$ if a given graph $G$ and pair of vertices $s$ and $t$ if $G$ has 0, exactly one, or at least two distinct $s$-$t$ paths. To see this, simply find the block decomposition of the graph and, and check if there is any non-trivial block between $s$ and $t$ in the tree.

We can push this slightly farther. Given an instance of the problem $G$ and vertices $s$ and $t$, we can reduce the problem in time $O(m)$ to a graph $bar{G}$ and vertices $x$ and $y$ such that for all edges $xx'$ incident to $x$, we have that

1. $xx'$ is in some $y$-$x$ path,


2. there exists a $y$-$x'$ path in $bar{G}-x$.

To see this, again using the block decomposition, we contract any bridge in the graph and delete edges not contained in any $s$-$t$ path. As above, this can be done in $O(m)$ time.

We give an $O(m(p-1))$ time algorithm to find the set of $s$-$t$ paths in a given graph $G$ with at least two $s$-$t$ paths.

1. We may assume, as above, that every edge $tt'$ incident to $t$ is contained in some $s$-$t$ path and that there exists at least one $s$-$t'$ path in $G-t$.


2. Check if the number of $s$-$t$ paths in $G-tt'$ is at least two, and if not, let $P_1$ be the set of the unique $s$-$t$ path in $G-tt'$. If there are at least two such paths, we recursively find the set of all such paths. Let $p_1 = |P_1|$. By choice of $tt'$, $p_1 ge 1$.


3. Check if the number of $s$-$t'$ paths in $G-t$ is at least two, and if not let $P_2$ be the set of the unique $s$-$t'$ path in $G-t$. Otherwise, we recursively find the set $P_2$ of $s$-$t'$ path in $G-t$. Let $p_2 = |P_2|$, and as above, we again have $p_2 ge 1$.

Step 1 can be performed in $c'm$ operations for some constant $c'$. The initial check in steps $2$ and $3$ can be performed in $c'(m-1)$ steps. If we must recursively run the algorithm, this will require another $c(m-1)(p_i - 1)$ operations for $i = 1, 2$ in Steps 2 and 3, respectively. As $p_i ge 1$, we can bound the work in each of Steps 2 and 3 by $c'm + cm(p_i - 1)$. Thus, the total number of operations is at most $3c'm + c(m)(p_1 +p_2 - 2) le cm(p-1)$ if we choose $c ge 3c'$.

nt.number theory - How natural is the reciprocity map?

The reciprocity map in the local case can be motivated by considering the unramified case. Let me try to explain this. For simplicity, let us consider the case of a finite abelian unramified extension $K_n/bf Q_p$ of degree $n$. Denote by $k_n$ the residue field of $K_n$. The unramified condition gives rise to the isomorphism
$$Gal(K_n/ {bf Q_p}) simeq Gal(k_n / {bf F_p}) simeq {bf Z}/n.$$

Now we like to parametrize these abelian unramified extensions {$K_n$} of $bf Q_p$ using information from $bf Q_p$. However, $bf Q_p$ is not finitely generated as a module over $bf Z_p$, let along over $bf Z$. $bf Q_p^times$, on the other hand, decomposes as
$$bf Q_p^times simeq p^{bf Z} times {bf Z}_p^times simeq bf Z times mu_{p-1} times Z_p,$$
which, if anything, at least contains a copy of $bf Z$ (depending on the choice of a uniformizer, say $p$).

It then seems somewhat natural to consider the map $${bf Q_p^times} xrightarrow{Art} Gal({bf Q^{ab, un}_p}/{bf Q_p}) qquad p mapsto Frob$$

where $Frob$ is a choice of a topological generator for $Gal({bf Q_p^{ab, un}}/{bf Q_p})$, the Galois group of the maximal abelian unramified extension ${bf Q_p^{ab, un}}$ of $bf Q_p$, which is naturally isomorphic to $Gal(bar{bf F_p} / bf F_p)$ (which is itself non-canonically isomorphic to $hat {bf Z}$).

Now compose the Artin map $Art$ with the restriction map $Gal({bf Q_p^{ab, un}}/{bf Q_p}) to Gal(K_n/ {bf Q_p})$, we obtain a map
$${bf Q_p}^times xrightarrow{Art_n} Gal(K_n/ {bf Q_p})$$ whose kernel is $$p^{n {bf Z}} times bf Z_p^times,$$ which coincidentally is also the image of the norm of $K_n^times$ in $bf Q_p^times$.

This also sheds some light on the global situation, where you have Frobenius at all but finitely many primes. Don't quote me on this, but I recall the Artin reciprocity map is uniquely determined by its action on the Frobenii (I assume a Chebatorev density argument will show this, and you can prove Chebatorev Density Theorem independent of class field theory if I remember correctly.)

Lastly, we saw that the (local) reciprocity map depends on the choice of a Frobenius as well as that of a uniformizer.

Outer automorphisms of simple Lie Algebras

I don't have a good reference, but I can work out the beginning of the answer for you. I will work just over $mathbb C$, and I will call my simple Lie algebra $mathfrak g$.

First, you must decide what you mean by "outer automorphism". We know what an automorphism is, and an "inner automorphism" should be conjugation by something. Of course, for $xin mathfrak g$, the bracket $text{ad}_x = [x,-] in mathfrak{gl}(mathfrak g)$ is a derivation of $mathfrak g$, not an automorphism. So I assume you mean the automorphism $exp(text{ad}_x) in {rm GL}(mathfrak g)$ as the inner automorphism. Now, the set of matrices of the form $exp(text{ad}_x)$ is not a group, but generates a connected group, which I will call $text{Inn}(mathfrak g)$. (Remark: any automorphism of $mathfrak g$ preserves the Killing form, so we really have $text{Inn}(mathfrak g) subseteq text{Aut}(mathfrak g) subseteq {rm SO}(mathfrak g)$.) Of course, $mathfrak g$ acts on itself faithfully since it is simple, so $text{Lie}bigl(text{Inn}(mathfrak g)bigr) = mathfrak g$, but $text{Inn}(mathfrak g)$ may not be simply-connected. Regardless, it is a quotient of the connected simply-connected simple group $G$ with Lie algebra $mathfrak g$, and so you could if you prefer consider inner automorphisms to be given by the adjoint action of $G$.

Now, over $mathbb C$ (and this requires facts about the topology of $mathbb C$), any two choices of Cartan subalgebra are conjugate by an element of $text{Inn}(mathfrak g)$. See, for example, Proposition 5.32 of my notes on the class by M. Haiman. So, to understand $text{Out}(mathfrak g) = text{Aut}(mathfrak g) / text{Inn}(mathfrak g)$, it suffices to understand how it acts any chosen Cartan subalgebra $mathfrak h$.

Any automorphism of $mathfrak g$ that fixes $mathfrak h$ must act on the root lattice, and must take some system of positive roots to some system of positive roots. Now, any two systems of positive roots are related by the Weyl group $W subseteq {rm GL}(mathfrak h^*)$. (Proposition 5.60 from my notes.) On the other hand, we have $W = mathcal N_G(H)/H$, the normalizer of the maximal torus $H = exp mathfrak h$ in $G$ modulo $H$, which acts trivially on $mathfrak h$. So $W$ acts on $mathfrak h$ by inner automorphisms, indeed by $mathcal N_G(H) subseteq G$.

A system of positive roots picks out a Cartan matrix and corresponding Dynkin diagram, and conversely from this matrix you can reconstruct the group. Thus, the only possible source of outer automorphisms of come from automorphisms of the Dynkin diagram.

So your question follows simply from looking at the Dynkin diagrams. In particular, $A_1$, the $B$ and $C$ series, and the exceptional groups $G_2,F_4,E_7,E_8$ have no outer automorphisms. For the others, you have to do a calculation. Maybe it's obvious, but it's late; I'll think about it. As others pointed out in the time I took to write this answer, the theorem is that automorphisms of the Dynkin diagram are all outer. Actually, perhaps this is obvious. If an automorphism of the Dynkin diagram were inner, then it would induce among other things an automorphism of $H$, and so be in the Weyl group, and you must convince yourself that non-trivial elements of the Weyl group do not preserve the system of positive roots. But this is essentially the statements that $W$ acts faithfully on $H$ and that each $W$-orbit intersects the positive Weyl chamber only once. So I am using the fact that $W = mathcal N_G(H)/H$, which off the top of my head right now I don't know how to prove.

Notice that for semisimples, the Dynkin might be disconnected, and clearly any inner automorphism preserves the connected components. So there are certainly outer automorphism for $mathfrak g^{times n}$ given by the $S_n$ that permutes the pieces.

universal algebra - Essential arities in quasi-varieties.

For my question, let us consider the following scenario.

We have a quasi-variety $mathcal{A}$ generated by a finite algebra $mathbf{M}$ (i.e. $mathcal{A} = mathbb{ISP}(mathbf{M})$). Now, let $mathbf{A}$ be another finite algebra in $mathcal{A}$. Assume that there exists an integer $k$ such that, for each $n in mathbb{N}$, every homomorphism $f colon mathbf{A}^n rightarrow mathbf{M}$ is essentially at most $k$-ary.

My question is: Is it guaranteed that there exists a finite algebra $mathbf{M'} in mathcal{A}$ with $mathbf{A} in mathbb{ISP}(textbf{M'})$ such that, for each $n in mathbb{N}$, every homomorphism $f colon mathbf{A}^n rightarrow mathbf{M'}$ is essentially at most unary?

To illustrate this question, I will now give an example in which this is true. Let $textbf{M}$ and $textbf{A}$ be two finite distributive lattices. Now, there exists an integer $k$ such that the essential artiy of every $f colon mathbf{A}^n rightarrow mathbf{M}$ is at most $k$-ary. We can define $mathbf{M'}$ to be the (up to isomorphism unique) two-element distributive lattice.

Note that $mathbb{ISP}(mathbf{M'}) = mathbb{ISP}(mathbf{M})$ is not required (although it is true in the example). It is only required to have $mathbf{A} in mathbb{ISP}(mathbf{M'})$.

Is this always possible? I believe it is not, but I do not know any counterexample up to this point in time. Does anybody know a counterexample, a proof or has a feeling of whether this statement is true or false?

Note: If the answer to my question would be positive, this would have some very nice consequences for centralizer clones (which is my main research interest at the time). In fact, this would mean (and I can explain later, why that is) that every centralizer clones that has bounded essential arity cannot contain many types of functions. Among them: Near-unanimity operations, minority operations, semiprojections etc.. Furthermore, it would lead to a full characterization of all minimal clones in centralizer clones with bounded essential arity.

pr.probability - Brownian Bridge under observational error

if you consider a Gaussian vector $V=(X,Y) in mathbb{R}^{d=m+n}$, you know how to find the conditional distribution of $X$ knowing the value of $Y=y$, right ? This is exactly the same thing here.

For example, let us suppose that $a=0, b=N+1$:

• you have a noisy observation $Y=(y_1, y_2)=(O_a, O_b)$ with know covariance matrix $Sigma_Y$


• the data you are looking for, $X=(z_1, ldots, z_N) in mathbb{R}^N$, have a known covariance matrix $Sigma_X$


• the covariance matrix $E[X Y^t] = Sigma_{X,Y}$ is also known.

A quick way to find the conditional distribution of $X$ knowing $Y$ is to write
$$X = AU + BV$$
$$Y=CU$$
where $U,V$ are independent standard Gaussian random variable of size $2$ and $N$ respectively, while $A in M_{N,2}(mathbb{R})$ and $B in M_{N,N}(mathbb{R})$ and $C in M_{2,2}(mathbb{R})$. Because

• $CC^t = Sigma_Y$ gives you $C=Sigma_y^{frac{1}{2}}$,


• $AC^t = Sigma_{X,Y}$ then gives you $A=Sigma_{X,Y}Sigma_y^{-frac{1}{2}}$,


• $AA^t + BB^t = Sigma_{X}$ then gives you $B=(Sigma_{X}-Sigma_{X,Y}Sigma_y^{-1}Sigma_{X,Y})^{frac{1}{2}}$,

the $3$ matrices are easily computable, and $C$ is invertible in the case you are considering. This shows that if you know that $Y=y$, the conditional law of $X | Y=y$ is given by
$$X = AC^{-1}y + BV,$$
which is a Gaussian vector with mean $AC^{-1}y = Sigma_{X,Y}Sigma_y^{-1}y$ and covariance $BB^t = Sigma_{X}-Sigma_{X,Y}Sigma_y^{-1}Sigma_{X,Y}$

co.combinatorics - Nimber multiplication

In part 2 of Game Theory by Thomas Ferguson, example 2 'Turning Corners' on page 33, Thomas Ferguson mentions a so-called 'flipping-coin' game, where the Sprague-Grundy functions g(x, y) equals nim multiplication of x and y.

A move consists of turning over four distinct coins at the corners of a rectangle, i.e.
(a, b), (a, y), (x, b) and (x, y), where 0 ≤ a < x and 0 ≤ b < y, the coin at (x, y) going from
heads to tails.

This is under the (in part 2 of this book) usual assumptions that the game is for 2 players, and the last player that makes a move wins (i.e., you lose when you can't make a valid move according to the rules of the game). This might be the game that Alex Fink referred to, but I didn't find it to be such a contrived example, so it might be worth looking at (to be honest, at this point I don't understand the game completely and I don't have time for it now: this might be the same game that Lenstra mentions in the article linked to by Kevin O'Bryant: both are 'coin-turning' games).

Edit: In fact, the Sprague-Grundy value of a move in any 'product' of two coin-turning games G1 and G2 is given by the nimber product of the SG-value of the corresponding move in G1 and the corresponding move in G2. What this means exactly is explained more clearly in the document I linked to.

ca.analysis and odes - A two-variable Fourier series and a strange integral

I know how I want to answer this question. I'll write up the easy parts here, and leave the hard part for you :).

---

First some minor changes. It will be convenient to clear out denominators and work with $log left( 4 + e^{2 pi i x} + e^{- 2 pi i x} + e^{2 pi i y} + e^{- 2 pi i y} right)$. That just changes the constant term of your Fourier series by $log 2$. Next, it is convenient to focus on
$$int_0^1 int_0^1 log left( 4 + e^{2 pi i x} + e^{- 2 pi i x} + e^{2 pi i y} + e^{- 2 pi i y} right) e^{2 pi i m x} e^{2 pi i n y} dx dy.$$
A simple linear transformation goes between this and the cosine formulation. Let $S = { (z,w) : |z|=|w|=1 }$. So we are dealing with
$$frac{1}{(2 pi i )^2} int_S log left( 4+z+z^{-1} + w +w^{-1} right) z^{m-1} w^{n-1} dz dw.$$
Dropping out the $4 pi ^2$, we want to show the integrand is of the form $a pi + b$.

UPDATE: Thanks to fedja for pointing out that I had oversimplified the next paragraph.

Assuming that $(m,n) neq (0,0)$, we can integrate by parts with respect to one of the two variables, let's say $z$. Once we do that, we will have a quantity of the form
$$(mbox{rational number}) cdot int_S frac{(z-z^{-1}) w^k z^{ell} dw dz} {4+w+w^{-1}+z+z^{-1}}$$

So we'd like to show this quantity is of the form $a+b pi$.

As fedja points out, we need to be careful here. Without the $z-z^{-1}$ term, the integral diverges like $int int ds dt/(s^2 + t^2)$ near $(-1,-1)$.

---

Whew! Now comes the actual hard part. Let
$$E:={ (z,w) in (mathbb{C}^*)^2 : 4+z+z^{-1}+w+w^{-1} =0 }.$$
This is an elliptic curve with four punctures. As Bjorn points out, this is a nodal cubic and can be parameterized as
$$(z,w) = left( frac{1-u}{u(1+u)}, frac{u(u-1)}{1+u} right).$$
We'll come back to this point later.

The $2$-form $dw dz/(4+z+z^{-1}+w+w^{-1})$ has a simple pole on $E$. Let $omega$ be the $1$-form on $E$ which is the residue of that $2$-form.

I think there should be a curve $gamma$ in $E$ such that $S$ is homotopic, in $(mathbb{C}^*)^2 setminus E$, to a tubular neighborhood of $gamma$. So
$$int_S frac{w^k z^{ell} (z-z^{-1}) dw dz} {4+w+w^{-1}+z+z^{-1}} = int_{gamma} omega w^k z^{ell} (z - z^{-1}) .$$

If we substitute in the above parameterization, this will be the integral around a closed loop of some rational function in $mathbb{Q}(u)$. In particular, we can compute this integral by residues and we will get something of the form $a+b pi$, as desired.

Actually, it looks to me like we should just get $b pi$. Maybe the integration by parts doesn't go as well as I hoped?

---

Obviously, someone should actually work this out explicitly, but I don't think it will be me.

gr.group theory - Uses of the holomorph, Hol($G$) = $G rtimes$ Aut($G$)

If G is abelian, then the holomorph of G is a reasonably nice group. If G is a finite elementary abelian p-group of order pⁿ, then you can consider it to be a vector space over Z/pZ. The automorphism group is the group GL(n,p) of invertible n×n matrices over Z/pZ. The holomorph is called the affine general linear group, AGL(n,p), which can be thought of as (n+1)×(n+1) matrices [ A, v ; 0, 1 ] where A in Aut(G) ≅ GL(n,p) and v in G ≅ (Z/pZ)^n. If you restrict the automorphism group to only include GF(p^k) automorphisms, where k divides n, then you get a subgroup AGL(n/k,p^k) that is also important.

These sorts of groups are (one of) the standard examples of primitive permutation groups. Every soluble primitive permutation group has some minimal normal subgroup G that is elementary abelian, and a maximal subgroup M contained in Aut(G) = GL(n,p) that acts irreducibly on G, and the group itself is then the obvious subgroup { [ A, v ; 0, 1 ] : A in M } of AGL(n,p). Insoluble primitive groups can replace G with a non-abelian simple group or two, but a fair amount of the theory still applies.

These are all examples of the original motivation of the holomorph as the normalizer in the symmetric group of the regular representation of the group. For instance, a Sylow p-subgroup of the symmetric group on p points is regular of order p, and the Sylow normalizer is the holomorph, AGL(1,p).

Regular normal subgroups occur frequently in permutation groups and computational group theory (usually as something to be avoided due to behaving so differently), and their normalizers (aka, the whole group, since the subgroup is normal), are contained in the holomorph.

Primitive soluble groups, and in general, "irreducible" subgroups of AGL(n,p), tend to be important "boundary" examples (as in the boundary of a Schunck class) which do not have a property, but such that every quotient does. "M" is chosen to have the property, and then "G" is taken to be an irreducible M-module such that M⋉G does not have the property. It bugs me to call M the group and G the module, so in the next part M will be the module, and R the ring:

Something similar to a holomorph can be constructed from any module over a ring. You take the matrices [ r, m ; 0, 1 ] where r in R, m in M, and you get another ring where M the module becomes M the ideal; a so-called trivial extension. If instead of all of R, you just take the units of R, GL(1,R), then you get a nice group. For instance, taking R to be the p-adic integers extended by a p'th root of unity z (not already in there), and M to be R, then you get a very important pro-p-group of coclass 1, G = { [ z^i, r ; 0, 1 ] : 0 ≤ i < p, r in R }. For p=2, this is a pro-2 version of the dihedral group, and for all p its finite quotients are "mainline" p-groups of maximal class.

When G is not abelian, many of these comments still apply, but the matrix formulations are usually less enlightening. In general, the holomorph is a very nice setting in which to work with a group G and its automorphisms, with a regular normal subgroup G, with a primitive soluble group, or with various other nice examples.

linear algebra - Geometric Interpretation of Trace

What seems really odd to me is this limitation set by the original question.

The divergence application of trace is somewhat interesting, but again, not really what we are looking for.

Maybe that is rejected because it involves a metric tensor in most textbooks about differential geometry, but the divergence requires only an affine connection, even in differential geometry. In flat Cartesian space (without a norm or inner product), it's even simpler.

First consider that matrices have two main applications, as the components of linear maps and as the components of bilinear forms. Let's ignore the bilinear forms. Linear maps are really where matrices come from because matrix multiplication corresponds to composition of linear maps.

We know that the determinant is the coefficient of the characteristic polynomial at one end of the polynomial, and the trace is at the other end, as the coefficient of the linear term. So we should think in terms of linearization and volume, or some combination of these two concepts. We know that the determinant can be interpreted as the relative volume expansion of the map $xmapsto Ax$. So we should think in terms of maybe linearizing this in some way.

Define a velocity vector field $V(x)=Ax$ on $mathbb{R}^n$ and integrate the flow for a short time. What happens to the volume of any region? The rate of increase of volume equals $mathrm{Tr}(A)$. This is because the integral curves have the form $x(t)=exp(At)x(0)$. (See Jacobi's formula.)

Thus the determinant tells you the volume multiplier for a map with coefficient matrix $A$, whereas the trace tells you the multiplier for a map whose rate of expansion has component matrix $A$.

That sounds very neat and simple to me, but only if you avoid the formulas in the DG literature which try to interpret divergence in terms of absolute volume by referring to a metric tensor or inner product.

PS. To avoid analysis, to keep it completely algebraic apart from the geometric meaning of the determinant, consider the family of transformations $x(t)=x(0)+tAx(0)$ for $tinmathbb{R}$ for all $x(0)inmathbb{R}^n$. Then the volume of a figure (such as a cube) is a polynomial function of $t$. The linear coefficient of this polynomial with respect to $t$ is $mathrm{Tr}(A)$. There are no derivatives, integrals or exponentials here. The trace also happens to be the linear component of the characteristic polynomial. I think this is a pretty close tie-up.

PS 2. I forgot to mention that the divergence of the field $V(x)=Ax$ is $textrm{div} V=mathrm{Tr}(A)$. Therefore trace equals divergence. That's the geometrical significance of the trace. The function $V$ is the linear map with coefficient matrix $A$. And the trace equals its divergence if it is thought of as a vector field rather than just a linear map. You could even write $mathrm{Tr}(A)=mathrm{div}(A)$ if you identify the matrix with the corresponding linear map.

ag.algebraic geometry - Does a locally free sheaf over a product pushforward to a locally free sheaf?

One can prove this also without Bass's theorem.
Let $X= Spec A$ and $Y=Spec B$.
The sheaf $cal F$ comes from a finitely generated module $M$ over $C=Aotimes B$.
Our first goal is to show that $M$, as an $A$-module, is a direct sum of finitely generated, locally free modules.
Since $A$ is noetherian, this is equivalent to $M$ being a direct sum of finitely generated projective $A$-modules.

The fact that $M$ is locally-free implies that $M$ is projective over $C$, further it is finitely generated, so there is a finitely generated $C$-module $N$ such that $Moplus N=bigoplus_{i=1}^kC e_i$.
Now each $e_i$ of this free basis can bewritten uniquely as $e_i=m_i+n_i$.
Let $M_0$ be the $A$-module generated by $m_1,dots,m_k$.
Let $(b_j)_{jin J}$ be a basis of $B$ over the ground field, then
$$M=bigoplus_{jin J}b_j M_0.$$
Let $N_0$ be the $A$-module generated by $n_1,dots,n_k$. Then $M_0oplus N_0= bigoplus_i Ae_i$ is a free $A$-module and so is
Also $b_j(M_0oplus N_0)=bigoplus_iAb_je_i$.
This means that we have written $M$ as a direct sum of finitely generated projective $A$-modules as claimed.

Now to conclude remember that $A$ is noetherian, therefore for each point in $X$ there exists an open neighborhood, where all summands of $cal G$ are free.

hyperbolic geometry - Coordinates on Teichmuller space

We know that every surface of genus ($ggeq 2$) admits a pair of pants decomposition. And there is the Fenchel Nielsen Coordinates on the Teichmuller space associated to such a decomposition where we have the length functions of the geodesics boundaries and the twisting parameters for gluing these boundaries.

My question is the following:

We choose again a pair of pants decomposition. Then there arises the trivalent graph representing this decomposition.

We could associate a fixed a pair of pants to each of vertices, say of boundary geodesic length (1,1,1). And then glue flat cylinders of both boundary length 1 and height $h$ to form a Riemann surface(of course we will also need the twisting parameter for the sewing, but it seems that we should only need the relative twisting parameter as cylinder itself has a rotation symmetry.).

The height of these cylinders and the relative twisting parameter together form 6g-6 parameters. Will they also be a parametrization of Teichmuller space?

at.algebraic topology - Ring of closed manifolds modulo fiber bundles

Consider the variation where we ask for smooth manifolds and smooth fiber bundles. Then I claim that $R$ is not finitely generated.

The starting observation is that if $F to E xrightarrow{p} B$ is a smooth fiber bundle then

$$0 to text{ker}(p) to T(E) to p^{ast}(T(B)) to 0$$

gives a splitting of the tangent bundle of $E$. There are cohomological obstructions to such splittings existing in general, which we can compute. The upshot is that if $E$ is a simply connected (so it has no nontrivial covers) closed smooth manifold whose tangent bundle has no nontrivial subbundles, then $[E]$ does not participate in any of the interesting relations defining $R$, and in particular cannot lie in the subring of $R$ generated by manifolds of dimension smaller than $dim E$. Hence to show that $R$ is not finitely generated it suffices to write down a sequence of such $E$ of arbitrarily large dimension.

But this is standard: we can take the even-dimensional spheres $S^{2n}$. First, observe that because $S^{2n}$ is simply connected, it has no nontrivial covering spaces, and in addition every real vector bundle over $S^{2n}$ is orientable, hence has well-defined Euler classes (after picking an orientation). Second, the Euler class $e(T)$ of the tangent bundle is $2$ times a generator of $H^{2n}(S^{2n})$, and in particular does not vanish. Since the Euler class is multiplicative with respect to direct sum, if $T = T_1 oplus T_2$ is a nontrivial splitting of the tangent bundle then $e(T) = e(T_1) e(T_2)$. But the cohomology groups that $e(T_1)$ and $e(T_2)$ live in both vanish for $S^{2n}$; contradiction. Hence the tangent bundle of $S^{2n}$ admits no nontrivial splittings, and so $S^{2n}$ is not the total space of any nontrivial smooth fiber bundle of closed smooth manifolds.

(Maybe this argument can be rescued in the topological setting using tangent microbundles?)

(Strictly speaking this argument's not quite complete: we also need to show that there aren't any interesting bundles with total space the disjoint union of $S^{2n}$ with something else. But fiber bundle maps $p : E to B$ are open, so the image of $S^{2n}$ under such a map is a connected component of the base, and we can restrict our attention to this connected component without loss of generality. Then $E$ breaks up, as a fiber bundle, as a disjoint union of $S^{2n}$ and whatever else, and we can restrict our attention to $S^{2n}$ again without loss of generality. In other words, in the defining relations we can assume that $E$ and $B$ are both connected without loss of generality.)

measure theory - Dimension of the measurable space $mathbb{R}^n$

Consider $mathbb{R}^n$ as measurable space with the Borel algebra. If $mathbb{R}^n$ and $mathbb{R}^m$ are isomorphic (in the category of measurable spaces, i.e. there are measurable maps in both directions, which are inverse to each other), can we conclude $n=m$? Note that this statement is stronger than the invariance of dimension in topology and I doubt that it is true. Can you give a counterexample?

dg.differential geometry - Cobordisms of bundles?

Is there a notion of a cobordism which is compatible with bundle structure?

That is, if I have bundles $E$ and $F$, is it the case that the manifold $W$ with $E$ and $F$ as boundary components, can be made into a bundle whose bundle structure, when restricted to $E$ or $F$, is the bundle structure of $E$ or $F$.

And, particularly, when can I connect $E$ and $F$ this way (not just when they're cobordant, but when this cobordism is compatable with this structure)? And what can I say about the bundle structure of $W$, knowing what $E$ and $F$ look like? (e.g., if $E$ and $F$ are G-bundles what can I say about the group action on $W$?)

Also, can anyone point me to any particular references which discuss this? I spent a few hours in our (fairly small) math library looking for something like this, but haven't been able to find anything that seems to discuss this. But I may just not know the right catch phrases to search for!

ct.category theory - is localization of category of categories equivalent to |Cat|

There are set theoretic issues that will hinder any proof of this statement. In particular I don't believe you can construct the adjunction in part (2) without applying the axiom of choice to CAT, and it's not clear the localization S^(-1)CAT makes sense either.

That said, let's ignore these issues and pretend that CAT is a small category of (small) categories.

I was originally confused by this. I believe that there are some problems in the formulation of this question. In particular if S consists of those functors which are equivalences of categories, then it does not form a multiplicative system. Specifically, the right Ore condition fails. I'll give an example later. What this means though, is that the property your are trying to check in part (1) actually fails. To see this pick a group G and view it as a category with one object. Then the functors from H to H are the homomorphisms, and the equivalence classes of this functors are the orbits of Hom(H,H) under the conjugation action. Choose H such that there are distinct automorphisms of H which are equivalent under conjugation.

Claim: If F,G: H --> H are two such automorphisms, then there is no equivalence s:H --> C such that sF = sG. I think this is easy to check, so I'll leave it at that.

So the second part of (1) is impossible to prove.

I first thought that we can answer this question be going to skeletal categories. This is not correct, but let's look at why it is not correct. Let SKEL be the full subcategory of CAT consisting of the Skeletal categories, i.e. those categories in which $a cong b$ implies $a = b$, i.e. those categories which have a single object in each isomorphism class.

Every object in CAT is equivalent to one in SKEL. This is an easy exercise you should work out for yourself. By applying the axiom of choice to all of CAT we can construct an equivalence between CAT and SKEL, and in particular we have L: CAT ---> SKEL with an equivalence $C cong L(C)$ for every category C.

Notice that a functor between skeletal categories is an equivalence if and only if it is an isomorphism on the nose. So we are part way there. This made me think that SKEL was the localizing subcategory we were after.

However two functors into a skeletal category can be naturally isomorphic without being equal. The group example above is actually an example of this. The functors F and G are naturally isomorphic, but not equal.

Let J denote the "Joyal interval", the category with two objects and an isomorphism between them. J can be used to say when two functors are naturally isomorphic. F,G: C --> D are nat. isomorphic if they extend to a functor $C times J to D$. There is a quotient of J where we identify the two objects. This is in fact the category Z (the group of integers viewed as a category). Let W be the set of morphisms consisting of the single morphism J --> Z. Notice that SKEL consists of exactly the "W-local" objects. But this is not quite what we want.

---

Okay, now for the rest. First, I promised an example where the right Ore condition fails. This is given by considering the two inclusions of pt into J. Both of these are equivalences, but this cannot be completed to an appropriate square. So the class of equivalences in not a multiplicative system.

Next, Toen doesn't assume that S is a multiplicative system. He (correctly) defines the localization in terms of a (weak) universal property. Namely, there exists a locization functor:

$L: CAT to S^{-1}CAT$

such that fro any other category D, $L^* : Fun( S^{-1}CAT, D) to Fun(CAT, D)$ is fully-faithfull and the essential image consists of those functors which send elements of S to isomorphisms in D. In particular the quotient functor from CAT to |CAT| does this, so this gives us functor from S^(-1)CAT to |CAT| defined up to unique natural isomorphism.

On the other hand, |CAT| is also defined by a universal property. This gives us maps between |CAT| and S^(-1)CAT and by the usual sort of general nonsense this is an equivalence. The details aren't too hard, so I'll leave them to you.

Now the second part of your question asks about whether we can realize |CAT| as a full subcategory of CAT such that the quotient $q:CAT to |CAT|$ is left adjoint to the inclusion. The answer is no. Let's first look at whether q can have a right adjoint at all and what this would mean.

Suppose that R: |CAT| --> CAT is right adjoint to the quotient q. Be abuse, we will identify the objects of CAT and |CAT|. This means that for all categories X and Y we have:

$CAT(X, R(Y)) = |CAT|(X, Y) = |CAT|(X times J, Y) = CAT( X times J, R(Y))$

So $R(Y)$ must be cartesian local with respect to the map J --> pt. In particular we see, taking X=pt, that R(Y) has no non=identity automorphisms, i.e. R(Y) is rigid.

Now let's look at an example. Consider the group Z viewed as a category with one object. Then the endomorphisms of Z in |CAT| is the monoid Z (under multiplication). Now if R is fully-faithful then we need:

$mathbb{Z} = |CAT| (mathbb{Z}, mathbb{Z}) = CAT (R(mathbb{Z}), R(mathbb{Z}))$

but this last is equal to the automorphism of some set R(Z), hence we have a contradiction. So there is no such fully-faithful right adjoint.

mg.metric geometry - find the collision of a particle with a swept triangle.

Consider the (mostly nontrivial) tetrahedron formed by the three moving points and P. There is a determinantal formula for the volume of the tetrahedron, as well as one for the area of the triangle formed by the three moving points. Now you have two formulas depending on t, one measuring signed tetrahedral volume, the other the signed area of the moving triangle. If the area is nonzero at time t while the volume is 0 at time t, then you have a time when point P is in the plane of the triangle. Then you can do some calculations to see if P is inside the triangle or not. Otherwise, either the volume is nonzero (and thus no intersection between P and the triangle), or the triangle has zero area, and you have to check to see if P is collinear at that time with the other points, and also lies within the segment determined by the three points.

If you have more information about the trajectories, I may have more suggestions on how to find time t, if it exists.

Gerhard "Ask Me About System Design" Paseman, 2010.01.23

na.numerical analysis - Is there any numerical technique to sum x^(n^alpha), n=0,1,...?

The $k$th power is the generating function for the ways of expressing $n$ as a sum of $k$ $alpha$th powers of positive integers. However, I don't think this helps much even for most integer values of $alpha$.

When $alpha = 1$, this is a geometric series.

When $alpha = 2$, this is a theta function related to the Jacobi triple product formula

$$prod_{m=1}^infty (1-x^{2m})(1+x^{2m-1}y^2)(1+x^{2m-1}y^{-2}) = sum_{n=-infty}^infty x^{n^2}y^{2n}$$
since
$$(frac 12 text{RHS}+frac12) bigg|_{y=1} = sum_{n=0}^infty x^{n^2} .$$

You may be able to compute the sum when $alpha=2$ more efficiently using one of the integral formulas or other properties for elliptic theta functions. Other than that, I don't know of special cases.

This doesn't say anything about whether some rapid series acceleration technique exists.

physiology - How does the microbial environment in your gut initiate?

Clearly, a zygote does not harbor any microbes. As it develops, and the alimentary canal tissue is differentiated, I logically assume that there is still no microbial activity in the fetus's gut. I'm thus also assuming that the commencement of microbial activity in the intestines occurs after birth, but when, and how?

Do newborn babies just happen to ingest only certain e.g., E.coli strains? Is the gut a selective environment in which only certain E.coli strains develop?

Are there any mechanisms to ensure that harmful bacteria do not initially reside in the gut? Is a newborn's digestive tract particularly unstable and ineffective until the proper microbes are established?

nt.number theory - Transformation formulae for classical theta functions

I am looking for a reference for the transformation formulae
for the classical theta-functions
$$theta_4(tau)=sum_{n=-infty}^infty (-1)^n q^{n^2}$$
and
$$theta_2(tau)=sum_{n=-infty}^infty q^{(2n+1)^2/4}$$
under the congruence group $Gamma_0(4)$.
Here $tau$ lies in the upper-half plane and $q^x$ denotes
$exp(2pi i xtau)$. More precisely I want the exact automorphy
factors for each $AinGamma_0(4)$ (some eighth root of
unity times $sqrt{ctau+d}$). I know these can easily
be deduced from those for the basic theta-function
$$theta_3(tau)=sum_{n=-infty}^infty q^{n^2}$$
for which a nice reference for the automorphy factors is Koblitz's Introduction
to Elliptic Curves and Modular Forms. However

1. a citation would be useful to me,




2. I want to check my calculation and




3. a reference may give the formulae in a more convenient form than I have.

Thanks in advance.

EDIT I have now found a convenient reference: Rademacher's
Topics in Analytic Number Theory.

FURTHER EDIT Rademacher atcually gives full transformation formula
for the two-variable classical Jacobi theta functions under arbitrary
matrices in $mathrm{SL}_2(mathbb{Z})$. From these we can deduce
for $AinGamma_1(4)$ that
$$frac{theta_2(Atau)}{theta_3(Atau)} =i^bfrac{theta_2(tau)}{theta_3(tau)}$$
and
$$frac{theta_4(Atau)}{theta_3(Atau)} =i^{-c/4}frac{theta_4(tau)}{theta_3(tau)}$$
in the usual notation. Once noticed, these relations are easy to prove
from scratch.

Thanks to all who replied to this question.

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.)

ct.category theory - Candidate definitions for "1-braided 2-category"?

Recall that a braided monoidal category is a category $mathcal C$, a functor $otimes: mathcal C times mathcal C to mathcal C$ satisfying some properties, and a natural isomorphism $b_{V,W}: Votimes W to Wotimes V$ satisfying some properties. Recall also that a monoidal category (just $mathcal C,otimes$ and their properties) is the same as a one-element 2-category: the objects of $mathcal C$ become the morphisms, and the monoidal structure becomes composition.

Thus, is there a natural definition of "1-braided 2-category"? I'm calling it "1-braided" because the braiding acts on 1-morphisms (as opposed to "braided monoidal 2-category", where the braiding acts on the 0-morphisms).

I realize, of course, that if $V,W$ are morphisms of a 2-category so that $Vcirc W$ is defined, then generally $Wcirc V$ is not defined, so a priori asking for any relationship $Vcirc W cong Wcirc V$ doesn't make sense. On the other hand, consider Aaron Lauda's categorification of $U_q(mathfrak{sl}_2)$. It is a 2-category, but different hom-sets can be more-or-less identified.

Space Bounded Communication Complexity of Identity

Here's an argument that I believe shows that $log n - omega(1)$ is impossible. (This argument came out of a discussion I had with Steve Fenner.)

Let Alice's input be $xin{0,1}^n$ and let Bob's input be $yin{0,1}^n$. Assume the shared memory stores states in ${0,1}^m$, and its initial state is $0^m$. We are interested in lower-bounding $m$ for any protocol that computes EQ$(x,y)$.

A given protocol is defined by two collections of functions ${f_x}$ and ${g_y}$, representing the functions applied to the shared memory by Alice on each input $x$ and Bob on each input $y$, respectively, along with some answering criterion. To be more specific, let us assume that if the shared memory ever contains the string $1^{m-1}b$ then the output of the protocol is $b$ (for each $bin{0,1}$). For convenience, let us also assume that $f_x(1^{m-1}b) = 1^{m-1}b:$ and $g_y(1^{m-1}b) = 1^{m-1}b:$ for every $x,yin{0,1}^n$ and $bin{0,1}$. In other words, Alice and Bob don't change the shared memory once they know the answer.

Now, for each $x,yin{0,1}^n$, consider what happens when Alice and Bob run the protocol on the input $(x,y)$. Define $A_{x,y}subseteq{0,1}^m$ to be the set of all states of the shared memory that Alice receives at any point in the protocol, and likewise define $B_{x,y}subseteq{0,1}^m$ to be the states of the shared memory that Bob receives. Also define
[
S_{x,y} = {0w,:,win A_{x,y}} cup {1w,:,win B_{x,y}}.
]
We will assume Alice goes first, so $0^m in A_{x,y}$ for all $x,y$. Let us also make the following observations:

1. By the definition of $A_{x,y}$ and $B_{x,y}$, it holds that $f_x(A_{x,y}) subseteq B_{x,y}$ and $g_y(B_{x,y}) subseteq A_{x,y}$ for all $x,y$.




2. For every $x,y$ with $xnot=y$ it holds that $1^{m-1}0in A_{x,y} cup B_{x,y}$, because Alice and Bob output 0 when their strings disagree.




3. For every $x$ it holds that $1^{m-1}0notin A_{x,x} cup B_{x,x}$, because Alice and Bob do not output 0 when their strings agree.

Now let us prove that $S_{x,x}not=S_{y,y}$ whenever $xnot=y$. To do this, let us assume toward contradiction that $xnot=y$ but $S_{x,x} = S_{y,y}$ (i.e., $A_{x,x} = A_{y,y}$ and $B_{x,x} = B_{y,y}$), and consider the behavior of the protocol on the input $(x,y)$.

Let $w_t$ be the contents of the shared memory after $t$ turns have passed in the protocol, so we have $w_0 = 0^m$, $w_1 = f_x(w_0)$, $w_2 = g_y(w_1)$, and so on. It holds that
[
begin{array}{c}
w_0 = 0^m in A_{x,x}\
w_1 = f_x(w_0) in f_x(A_{x,x}) subseteq B_{x,x} = B_{y,y},\
w_2 = g_y(w_1) in g_y(B_{y,y}) subseteq A_{y,y} = A_{x,x},
end{array}
]
and in general
[
begin{array}{c}
w_{2t + 1} = f_x(w_{2t}) in f_x(A_{x,x}) subseteq B_{x,x} = B_{y,y}\
w_{2t+2} = g_y(w_{2t+1}) in g_y(B_{y,y}) subseteq A_{y,y} = A_{x,x}
end{array}
]
for each $tinmathbb{N}$. It follows that $A_{x,y} subseteq A_{x,x}$ and $B_{x,y} subseteq B_{y,y}$.

But now we have our contradiction, assuming the protocol is correct: given that $A_{x,y}subseteq A_{x,x}$ and $B_{x,y} subseteq B_{y,y}$, it follows that $1^{m-1}0 in A_{x,x}cup B_{y,y}$, so Alice and Bob output the incorrect answer 0 on either $(x,x)$ or $(y,y)$.

Each $S_{x,x}$ is a subset of ${0,1}^{m+1}$, so there are at most $2^{2^{m+1}}$ choices for $S_{x,x}$. Given that the sets $S_{x,x}$ must be distinct for distinct choices of $x$, it follows that $2^{2^{m+1}} geq 2^n$, so $m geq log n - 1$.

How to estimate the fraction of graphs with small clique among the graphs with certain edges

A little further elaboration on what you're looking for would be appreciated; as you've asked it, this could be anything from an elementary probability exercise to what I think might be an open problem!

So if we fix k and take n large, then the answer depends entirely on the size of M compared with n. The term of art is "threshold function"; see here for more details. Specifically, for fixed k, if $M >> n^{2-2/(k-1)}$ then almost every graph with n vertices and M edges has a clique of size k; if $M << n^{2-2/(k-1)}$ then almost no graph with those parameters has a clique of size k. This can be proved by a straightforward application of linearity of expectation and bounding the variance (Chebyshev's inequality), using the fact that every subgraph of $K_k$ has a smaller ratio of edges to vertices than does $K_k$ itself. (See Ch. 4 of Alon and Spencer for more details.) When $M$ has the same growth rate as $n^{2-2/(k-1)}$ the analysis is considerably subtler.

If we fix $M/n^2$ to be some constant (say around 1/4), then the size of the largest clique grows like log n, and in fact as n goes to infinity (and taking $M/binom{n}{2} = 1/2$) the clique number becomes concentrated at two points! This should also not be too difficult, but it's in a chapter of Alon-Spencer (Ch. 10) I haven't actually read yet, so I'm just glancing at the proof -- it doesn't look too bad. If you want more details I can try to read it more closely.

In general, the first approach I'd look at would be to estimate the expected number of k-cliques in a random graph and then bound the variance, but this might work less well depending on what exactly you're trying to do.