lo.logic - Is there a computable model of ZFC?

The Tennenbaum phenomenon is amazing, and that is totally correct, but let me give a direct proof using the idea of computable inseparability.

Theorem. There is no computable model of ZFC.

Proof: Suppose to the contrary that M is a computable model of ZFC. That is, we assume that the underlying set of M is ω and the membership relation E of M is computable.

First, we may overcome the issue you mention at the end of your question, and we can computably get access to what M thinks of as the
n^th natural number, for any natural number n. To see this, observe first that there is a particular natural number z, which M believes
is the natural number 0, another natural number N, which M believes to the set of all natural numbers, and another natural number s, which M
believes is the successor function on the natural numbers. By decoding what it means to evaluate a function in set theory using ordered pairs, We
may now successively compute the function i(0)=z and i(n+1) = the unique number that M believes is the successor function s of i(n). Thus,
externally, we now have computable access to what M believes is the n^th natural number. Let me denote i(n) simply by n. (We
could computably rearrange things, if desired, so that these were, say, the odd numbers).

Let A, B be any computably inseparable sets. That is, A and B are disjoint computably
enumerable sets having no computable separation. (For example, A is the set of TM programs halting with output 0 on input 0, and B is the set of
programs halting with output 1 on input 0.) Since A and B are each computably enumerable, there are programs p₀ and p₁ that
enumerate them (in our universe). These programs are finite, and M agrees that p₀ and p₁ are TM programs that
enumerate a set of what it thinks are natural numbers. There is some particular natural number c that M thinks is the set of natural numbers
enumerated by p₀ before they are enumerated by p₁. Let A⁺ = { n | n E c }, which is the set
of natural numbers n that M thinks are enumerated into M's version of A before they are enumerated into M's version of B. This is a computable
set, since E is computable. Also, every member of A is in A⁺, since any number actually enumerated into A will be seen by M to have
been so. Finally, for the same reason, no member of B is in A⁺, because M can see that they are enumerated into B by a (standard)
stage, when they have not been enumerated into A. Thus, A⁺ is a computable separation of A and B, a contradiction. QED

Essentially this argument also establishes the version of Tennenbaum's theorem mentioned by Anonymous, that there is no computable nonstandard
model of PA. But actually, Tennenbaum proved a stronger result, showing that neither plus nor times individually is computable in a nonstandard model of PA. And this takes a somewhat more subtle argument.

genetics - Is the function of adjacent genes correlated?

In bacteria, this is often true. This is because more than one gene is often transcribed onto a single RNA. This grouping of genes is called an operon. It is usually true that these have a related function because they are being translated to protein in very much the same proportion - a convenient way to regulate the function as a whole.

Once you get into eukaryotes this is no longer true (except for v. rare cases most of which are viral genes), one mRNA transcript contains just one translation region. This is true even for yeast and other single celled organisms. Gene regulation can be correlated, but the relationship on the genome has little to do with it.

There is some importance to the genomic relationship of two genes because of the crossing over that occurs in meiosis, but this is more of a relationship that is important in speciation and evolution, it doesn't have any recognized importance to how the genes act within the eukaryotic cell.

ag.algebraic geometry - Evidences on Hartshorne's conjecture? References?

A remark similar to Hailong Dao's comment under his answer:

Let $E$ be a vector bundle on $mathbb{P}^n$. A cohomological criterion (Horrocks' criterion) states that $E$ splits if and only if $H^i(mathbb{P}^n, E(t))=0$ for $0 < i < n$ and all $t$.

There is a little less well known criterion, due to Evans and Griffiths, which says that we only need to check the vanishing of $H^i(mathbb{P}^n, E(t))$ for $0 < i < min(n, rank(E))$ and all $t$.

In particular, in the rank two case, the whole conjecture boils down to the simple claim that $H^1(mathbb{P}^n, E) = 0$. Since $E$ is trivial on each "standard open" $U_i$, we can describe cohomology classes in this $H^1$ group using explicit Cech cocycles in this covering.

In summary, it is surprising how little we know about such a simple situation!

soft question - Colloquial catchy statements encoding serious mathematics

The consequences of this little harmless looking statement are deep enough that I worry that the majority will think that it is provably wrong.

Simple statement:

• "You can pick a real number at random between 0 and 1, so that any number is as likely as any other."

more colloquially, (Freiling):

• "You can throw a dart at the unit square."

more computer-scienc-y:

• "The process of coin flipping to determine the binary digits of a real number converges to a unique well defined real number answer in the limit of infinitely many throws".

The interpretation of this statement is not that the probability distribution of the result is a well defined function, nor that statements about whether this number is in this or that Borel set can be assigned a probability--- both these assertions are true and boring. The assertion above is that a real number "x" produced in this way actually exists as an element of the mathematical universe, and every question you can ask of it, including "does x belong to this arbitrary subset S of [0,1]" gets a well defined yes or no answer in the limit. If you believe this assertion is self-evidently true, as I do, beware the implications!

• The continuum hypothesis is false. (Sierpinsky,Freiling)

For contradiction, well order [0,1] with order type aleph-1, then choose two numbers x,y at random in [0,1]. What is the probability that $yle x$ in the well-ordering? Since the set ${ z|zle y} $ is countable for any y, the answer is 0. The same thing works whenever sets of cardinality less than the continuum always have zero Lebesgue measure.

• Every subset of [0,1] has well-defined Lebesgue measure. (Solovay, more or less)

Make a countable list of independent numbers $x_i$, and ask for each one whether the number is in the set S or not. The fraction of random picks which land in S will define the Lebesgue measure of S. In more detail, if you write down a "1" every time $x_i$ is in S, and write down a zero when $x_i$ is not in S, then the number of ones divided by the number of throws converges to a unique real number, which defines the Lebesgue measure of S.

In this forum, somewhere or other, someone had the idea that this process will not converge for sets S which are not measurable, alternating between long strings of "0"s and long strings of "1"s in such a way that it will not have an average frequency of 1's. This is impossible, because the picks are independent. That means that any permutation of the 0's and 1's is as likely as any other. If you have a long string of N zeros and ones, the only permutation invariant of these bits is the number of ones. Any segregation of zeros or ones that has oscillating mean has less than epsilon probability whenever the mean number of ones after M throws, deviates by more than a few times $sqrt{ln epsilon}/sqrt{N}$ from the mean established by the first N throws.

It is astonishing to me that someone here simultaneously holds in their head the two ideas: "there exists a non measurable subset of [0,1]" and "you can choose a real number at random between [0,1]". The negation of the first statement is the precise statement of the second.

(Solovay defined this stuff precisely, but did not accept the resulting model as true. Others take the axiom of determinacy, thereby establishing that all subsets of R are measurable and that choice fails for the continuum, but determinacy is a stronger statement than "you can pick in [0,1]".)

• The axiom of choice fails, already for sets of size the continuum.

Since the axiom of choice easily gives a non-measurable set.

• The continuum has no well order.

This is because you could then do choice on the reals. So the first bullet on this list should really be rephrased as "the continuum hypothesis is just a stupid question".

• Sorry, you can NOT cut up a grape and rearrange the pieces so that it is bigger than the sun.

Simply because if you put a grape next to the sun, and pick a random point in a big box that surrounds both, the probability that the random point lands in the grape is less than the probability that it lands in the sun. The Lebesgue measure of the pieces is well defined, and invariant under translations and rotations, so it never amounts to more than the measure of the grape.

• The reals which are in "L", the Godel constructable universe, have measure zero.

When the axiom of Choice holds for all elements of the powerset of Z (i.e. R), then the pea can be split up and rearranged to make the sun. The axiom of choice holds in L, so that the Godel constructible L-points in the pea can be cut up and rotated and translated to fit over the L-points of the sun. This means that these points make a measure zero set, both in the pea and in the sun, when considered as a sub-collection of the real numbers which admit random picks.

To understand the Godel constructible universe, and choice, I will pretend that the phrase "Godel constructible" simply means "computable." This is a bald-faced lie. the Godel constructible universe contains many non-computable numbers, but they all resemble computable numbers, in that they are defined by a process which takes an ordinal number of steps and at each step uses only text sentences of ZF acting on previously defined objects. If you replace ordinal by "omega" and "text sentences acting on previously defined elements" by "arithmetical operations defined on previously defined memory", you get computable as opposed to Godel-constructible. To well order the Godel universe, you just order the objects constructed at each ordinal step by alphabetical order and ordinal birthday. To well order the computable reals, you just order their shortest program alphabetically (like the well-ordering of the Godel-universe, this ordering is explicitly definable, but not computable).

• That stupid hat trick doesn't work in the random-pick real numbers

There is a recently popularized puzzle: A demon puts a hat, either red or green, on the head of a countably infinite number of people. Each person sees everyone else's hat, and is told to simultaneously guess the color on their heads. If infinitely many get this wrong, everybody loses. If only finitely many people get the answer wrong, everybody wins.

When the demon picks the hat color randomly on each person's head, they lose. Each person has 50% chance of getting their hat right. End of story. Nothing more to say. Really. This is why set theory has nothing to do with weather prediction.

• The stupid hat trick does work over the computable reals, but is intuitive.

If the demon is forced to place hats according to a fixed definite computer program, there are only countably many different programs, the demon must pick a program, and stick with it. Then it is reasonable that each person can figure out the program used from the infinite answers at their disposal, up to a finite number of errors.

Supposing the people are provided just with some halting oracles and a prearranged agreement regarding computer programs. They do not need a choice function on the continuum. The people see the other hats, and they test the computer programs one by one, in lexicographic order, until they find the shortest program consistent with what they see. They then go through all the programs again, until they find the shortest program on integers which will give be only different from what they see in finitely many places (this requires a stronger oracle, but it still doesn't require a choice function). Then they answer with the value of this program at their own position.

(more precisely, to see everyone else's hat means that the demon provides a program which will give the value of everyone elses hat. You use the halting oracle to test whether each program successively will answer correctly on everyone else's hat, until you find the shortest program that does so.)

This version also has application to weather prediction: by studying the weather long enough, you can guess that it is obeying the Navier Stokes equations. Then you can simulate these equations to predict the weather. Come to think of it, this is exactly what we humans did.

• The stupid hat trick is also intuitive in L, so long as you always think inside a countable model of ZF(C).

The demon again is constrained to definable reals below omega one, which is now secretly a countable ordinal (but ZF doesn't know it). So there is very little difference between the conceptual method to guess the definable real, except that now it isn't so easy to interpret things in terms of oracles.

• There is no problem with "$R_L$, the L version of R, coexisting inside $R_R$, the actual version of R, in your mental model of the universe.

The axiom of choice is true in L, which includes a particular model for the real numbers (and all powersets). This model is fine for interpreting all the counterintuitive statements of ZFC, since they are just plain true in L. When you read a choicy theorem, you just imagine little "L" subscripts on the theorem, and then it is true (this is called relativizing to L in logic). But you always keep in mind that L is measure zero. Then that's it. There are no more intuitive paradoxes.

Your mental axiom system for no-intuitive-paradox mathematics than can be this

ZF (but you interpret powerset as "L-powerset")

V=L (and therefore Choice for all sets in your universe, and the continuum hypothesis for the constructible reals, and for the constructible powersets)

For each set S in the universe L, (which is well-ordered by V=L), there is a non-well-orderable proper class of subsets of S, the true power-class. Every subclass of a powerclass has a real valued Lebesgue measure, and every subset (meaning well-orderable sub-SET, not a non-well-orderable subCLASS) of a powerclass has measure zero. All powerclasses are the same size, since they are not powerclasses of previous powerclasses, just powerclasses of dinky little sets. The measure of the proper-class completion of the dinky little measure-zero L-Borel sets is the same as the measure assigned to these Borel sets in L.

This system does nothing but shuffle the intuition around. There is no new real mathematics here (no new arithmetic theorems). But with this in your head, you banish all the choice paradoxes to the dustbin of history. No more puzzles, no more paradoxes, no more nothing. This has been a public service announcement.

nt.number theory - Diagonalizing matrices over cyclotomic fields with unitaries

Let $F$ be a number field with a fixed embedding $F hookrightarrow mathbb{C}$ such that the restriction of complex conjugation from $mathbb{C}$ to $F$ is in Gal$(F/mathbb{Q})$ and fix a Hermitian inner product $langle v,w rangle = overline{v_1}w_1 + cdots + overline{v_n}w_n$ on $mathbb{C}^n$ (with respect to the standard basis of $mathbb{C}^n$. In particular, this restricts to a Hermitian inner product on $F^n$.

Now suppose we are given a unitary matrix $U$ on $F^n$ with respect to that inner product. It is well known (independent of unitarity) that $U$ is diagonalizable over some extension $E/F$ - for instance, take $E$ to be a splitting field of the minimal polynomial of $U$. This means there is a matrix $M$ over $E$ such that $M U M^{-1}$ is diagonal in the standard basis.

What if we instead want a unitary $W$ such that $W U W^dagger$ is diagonal? This can be accomplished by working over a bigger extension $E'/E$ that includes some extra square roots of elements of E. Namely, given any $M$ that diagonalizes $U$ over $E$, just add in the square roots of the eigenvalues of $M^dagger M$.

Now for my question:

Is there any sort of intrisic (i.e. independent of a choice of $M$) understanding of the extension $E'$? By understanding, I mean things like: is there a nice way of describing its generators over E? Can anything be said about its Galois group in general? When is it a semidirect product?

My actual interest is in the case where $F$ is cyclotomic and $U$ has finite order (and thus has roots of unity as eigenvalues, so $E$ is another cyclotomic field). Any advice on what is known in this specific, or otherwise the general case, would be be much appreciated.

marine biology - Modern Whales with Vestigial legs Myth?

Yes there are several published sources (with photos) of whales born with protruding vestigial legs.

http://digitallibrary.amnh.org/dspace/bitstream/handle/2246/4849/N0009.pdf;jsessionid=55D6453968F5461B1B6BFF8D53C81F16?sequence=1

Modern Right Whales have rudimentary legs--completely inside their bodies.

"approaching the inquiry with the most skeptical determination, one cannot help being convinced, as the dissection goes on, that these rudiments [in the Right Whale] really are femur and tibia. The synovial capsule representing the knee-joint was too evident to be overlooked. An acetabular cartilage, synovial cavity, and head of femur, together represent the hip-joint. Attached to this femur is an apparatus of constant and strong ligaments, permitting and restraining movements in certain directions; and muscles are present, some passing to the femur from distant parts, some proceeding immediately from the pelvic bone to the femur, by which movements of the thigh-bone are performed; and these ligaments and muscles present abundant instances of exact and interesting adaptation. "

http://etb-whales.blogspot.com/2012/03/hind-limb-rudiments-on-modern-whales_1221.html

What metabolically happens when an egg fuses with the nucleus of a somatic cell

In stem cell biology, it is recognized that embryonic stem cells are transcriptionally inactive for the first 3 days of development. However, during somatic cell nuclear transfer, the nucleus is likely to include various polymerases and RNA both coding and non-coding. Does this affect the success rates of cloning?

posets - Is every lattice the fixed-point set of an order endomorphism of ⋄^n?

For all finite lattices, the answer is Yes.

More generally, for all complete lattices, the answer is Yes, and for all incompleteness lattices, the answer is No.

(Complete = every set has a LUB and GLB.)

Let me first give the positive result. Suppose that L is a complete lattice. Every lattice is naturally a sub-order of the power-set lattice P(L), by associating each point b with it's lower cone b* = { a in L | a <= b }. This map is clearly order-preserving. (Note: it is not a lattice embedding, however, since (b* v c*) is the union of two cones, rather than the cone of (b v c). ) Thus, L is order-isomorphic to the set of lower cones. Define f:P(L) to P(L) by

• f(A) = (sup A)*.

That is, f(A) is the lower cone of (sup A). This is the smallest lower cone containing A. Note that (sup A) is an element of L, since L is complete. The map f is order preserving, since if A is a subset of B, then sup A <= sup B.

Clearly, f(b*) = b* for any b in L, since b is the sup of b*. Conversely, if F(A) = A, then A = b* for b = sup A. That is, A is a lower cone. Thus, the fixed points of f are exactly the lower cones of L, which are order-isomorphic to L, as desired.

Finally, to make the connection with your Diamond lattice, note that P(L) is simply 2^L, a power of the 2 element Boolean algebra. Since Diamond is 2², we can view P(L) as a power of Diamond. (Add a dummy coordinate if L is odd finite size.)

Now, let's consider the negative result. Every power of Diamond is isomorphic as I mentioned earlier to a power set P(J) for some set J. Suppose that f:P(J) to P(J) is an order-preserving map from P(J) to P(J). I claim that the set of fixed points of f must have a smallest element. To see this, let B be the intersection of all A such that f(A) subset A. For any such A it follows that B subset A, so f(B) subset f(A), and so f(B) subset B. So B is the smallest with f(B) subset B. But since applying f gives f(f(B)) subset f(B), it follows that f(B)=B, as desired. By working above any given collection of fixed points, the same argument shows that the collection of fixed points is complete. This establishes:

Theorem. A lattice is complete if and only if it is isomorphic to the set of fixed points of an order-preserving endomorphism of a power set lattice P(J).

Note that many lattices are not complete. For example, the positive integers, as Neel mentioned in his answer. So these lattices are never the set of fixed points of an order-preserving map on a power set lattice, and consequently the same for the powers of Diamond.

Hypercube decomposition of perverse sheaves

In some sense there is no canonical way to extract these vector spaces. Algebraically this is because projective objects usually have automorphisms. Geometrically because these vector spaces are the stalks of local systems on a manifold with no natural base point. But the manifold and the local system are canonical.

Each of the 2^n coordinate subspaces of C^n has a conormal bundle in C^{2n}. This gives an arrangement of 2^n Lagrangian subspaces of the symplectic vector space C^2n, which are in general position (as general as possible for Lagrangian subspaces). The smooth part of this arrangement, the points that lie on exactly one of these Lagrangians, is a disjoint union of 2^n copies of (C-0)^n. The 2^n vector spaces in your hypercube are the stalks of local systems on these.

I am not sure what Verdier specialization is, but I bet it's exactly the construction of these local systems. In general, if Y is a smooth subvariety of X, then it is possible to extract from a perverse sheaf a local system on an open subset of the conormal variety to Y in X, by the following recipe:

1. Take nearby cycles for the deformation-to-the-normal-bundle family. This family has a C^*-action so taking nearby cycles is more canonical than usual--the monodromy action (var compose can) is trivial.




2. Take the Fourier transform. (As you know, I'm still pretty confused about this, but I think this has to be the topological version, or Fourier-Sato transform. In particular even with the C^*-action on the family, I don't think the sheaf you get at the end of 1. is C^*-equivariant.)




3. The result is a perverse sheaf on the conormal bundle to Y. This sheaf is locally constant on an open subset.

At one time S. Gelfand, MacPherson, and Vilonen had a project to understand the natural maps between the fibers of these local systems on different strata, i.e. the analogs of can and var. From a certain perspective the work of Nadler and Zaslow is a (not very concrete) solution to this problem.

In general, whether psi_f psi_g F = psi_g psi_f F depends on the blowup behavior of F with respect to the map (f,g) to C^2. For a counterexample, consider F = constant sheaf on C^2, f = x, g = xy. But if F is constructible with respect to a stratification that satisfies Thom's condition a_{f,g}--that is, the stratification is without blowups/sans eclatement with respect to (f,g)--then you are in good shape. (Although even here there is no canonical isomorphism between the two. They behave like stalks of a local system on an open subset of the base C^2.)

For sheaves without blowups I am not sure about references, but try Sabbah's "Morphismes analytiques stratifies sans eclatement et cycles evanescents," or from the etale point of view Illusie's recent note: http://www.math.u-psud.fr/~illusie/vanishing1b.pdf

bioinformatics - Downloadable worldwide database of disease statistics?

I took a quick peek and HealthMap and their JavaScripts are publicly viewable. As such, I believe cross site scripting would be quite feasible. In other words, call their JavaScripts from a page you develop on your server to create a feed of the data you want.

In this way, minimal effort on your part could leverage their data scraping efforts. If you're adding your own data then you're basically doing a Mashup.

That said, my concern with doing this is potentially violating their copyright. I would email them saying if their database is not available then you wish to use cross site scripting to access this data for your project, and unless they let you know otherwise by (specific date) you will assume this is acceptable.

I'm not a lawyer, so use this advice at your own risk. =)

How do you find the potential function V of the gradient system?

I'm going to assume everything is happening in $mathbb{R}^n$, which I think is what you intended.

Start by defining V(0) = 0.

Now, for each $xin mathbb{R}^n$, let $gamma_x:[0,b]rightarrow mathbb{R}^n$ be a (piecewise) smooth curve with $gamma_x(0) = 0$ and $gamma_x(b) = x$, i.e., $gamma_x$ is any continuous curve joining $0$ to $x$. Define $V(x) = int_0^b W cdot dgamma_x(t) = int_0^b W(gamma_x(t))cdot gamma_x'dt$, that is, $V(x)$ is the result obtained by integrating $W$ along $gamma_x$.

First note that by the fundamental theorem for line integrals, $V(x)$ is independent of the choice of curve. Thus, to actually compute $V(x)$, one may as well take $gamma_x$ to be a straight line joining $0$ and $x$ (or, if some other path gives a nicer integral, use that).

However, to actually prove that this $V(x)$ satisfies $nabla V = W$, it'll help to be able to pick the curves however we want.

So, why does this $V(x)$ work? Well, suppose one wants to compute $frac{d}{dx_1} V(x)$. Formally, this is lim$_{hrightarrow 0} frac{V(x+he_1) - V(x)}{h}$, where $e_1$ is a unit vector in the direction of $x_1$.

To actually evaluate this, make life as easy as possible by picking $gamma_{x+he_1}$ and $gamma_x$ nicely. So, pick $gamma(t)$ to be a smooth curve which starts at 0, and when , near $x$, looks like a straight line pointing in the direction of $e_1$, with $gamma(1) = x$. Thus, $gamma(t)$ is both $gamma_x$ and $gamma_{x+he_1}$, if you travel along it long enough.

Then $V(x+he_1) - V(x) = int_1^{1+h} Wcdot e_1 dt$.

But then $frac{d}{dx_1} V(x) = $lim$_{hrightarrow 0}frac{1}{h} int_1^{1+h} Wcdot e_1 dt$. But then, by the fundamental theorem of calculus (the usual one variable version), this is exactly $Wcdot e_1$, i.e., it's the first component of $W$. Of course, the other components work analogously.

(Incidentally, using Petya's isomorphism between vector fields and one forms, and using Stokes' theorem in place of the fundamental theorem of line integrals, this proves that $H^1_{text{de Rham}}(mathbb{R}^n) = 0$)

co.combinatorics - Why are multinomial coefficients with same entropy equal? (usually)

Suppose $p_1,ldots,p_d$ and $q_1,ldots,q_d$ are positive real numbers such that

$$p_1+cdots+p_d=q_1+cdots+q_d=n$$

and

$$p_1 log p_1+cdots+p_dlog p_d=q_1 log q_1+cdots+q_d log q_d $$

Then the following seems to hold

$$frac{n!}{p_1!cdots p_d!}=frac{n!}{q_1!cdots q_d!}$$

why?

Edit: JBL correctly notices that it doesn't always hold. I just didn't go far enough.
Still, it's surprising to me that it holds so frequently.

If we put a black disk at x,y if equality seems to hold (in machine precision) for x=n,y=d, and positive integer coefficients, it'll look like this

Red circle is JBL's example. Blue circle is n=18,d=3 which fails for (12,3,3) and (9,8,1).

docheck[n_, d_] := (
   coefs = IntegerPartitions[n, {d}, Range[1, n]];
   entropy[x_] := N[Total[# Log[#] & /@ x]];
   groupedCoefs = GatherBy[coefs, entropy];
   allEqual[list_] := And @@ (First[list] == # & /@ list);
   multinomials = Apply[Multinomial, groupedCoefs, {2}];
   And @@ (allEqual /@ multinomials)
   );
vals = Table[docheck[#, d] & /@ Range[1, 30], {d, 1, 20}];
Graphics[Table[Disk[{n, d}, If[vals[[d, n]], .45, .1]], {d, 1, Length[vals]}, {n, 1, 30}]]

Edit:
Updated version that does exact checking and allows coefficients with 0 components. Still only one example of failure for d=3.

docheck[n_, d_] := (coefs = IntegerPartitions[n, {d}, Range[0, n]];
   entropy[x_] := Exp[Total[If[# == 0, 0, # Log[#]] & /@ x]];
   groupedCoefs = GatherBy[coefs, entropy];
   allEqual[list_] := And @@ (First[list] == # & /@ list);
   multinomials = Apply[Multinomial, groupedCoefs, {2}];
   And @@ (allEqual /@ multinomials));
maxn = 30; maxd = 20;
vals = Table[docheck[#, d] & /@ Range[1, maxn], {d, 1, maxd}];
Graphics[Table[Disk[{n, d}, If[vals[[d, n]], .45, .1]], {d, 1, Length[vals]}, {n, 1, maxn}]]

linear algebra - problems of subspace of M_n(C)

let $M_n(c)$ denote the n times n matrices over the complex number field. $N$ be a subspace of

$M_n(C)$.

1 If there is no unitary lies in $N$, what is the maximum of the dimension of $N$ can be?

It's easy to see that it is not less than n(n-1), I guess it's also tight, but I don't know if I am correct.

2 If all the rank of $M$ lies in $N$ are greater than a fixed integer $k$, what is the maximum of the dimension of $N$ can be?

abstract algebra - On order of subgroups in abelian groups

I wonder whether any of you guys has already read the homonymous note by R. Beals in the December 2009 issue of the Monthly.

If so, would you be so kind as to let me know about the main ideas in Beal's approach? As you know, the whole point of his note is to present a solution to the following exercise in Herstein's Topics in Algebra:

Let G be an abelian group having subgroups of order m and n. Prove that G also possesses a subgroup of order lcm(m, n).

The funny thing about this proposal is that in subsequent editions of his book, Prof. Yitz would proclaim that he himself didn't have a solution using the authorized tools. Besides, he even went on to saying: "I've had more correspondence about this problem than about any other point in the whole book.".

Being aware of some of the history behind this little pearl, I'd really like to know what it is that Beals came up with. Is his approach crystal-clear? Is it somehow related to the standard attack of proving it first for the case gcd(m, n)=1?

Thanks in advance for you insightful replies.

P.S. The local library is the only access that I have to the literature. Unfortunately, they don't subscribe to any of the MAA periodicals.

co.combinatorics - What are the Applications of Hypergraphs

I've done some work which made me appreciate the view that labelled hypergraphs are one of the most widely appropriate, general ways to represent data on stateful machines. In computer science, we commonly want to divide up state into a number of possibly overlapping data structures, which will contain and be referenced by pointers.

This lends itself to the following representation: data structures are hyperedges. Non-pointer data within data structures are labels of the associated hyperedge. And pointers are represented by vertices, possibly (not always!) needing an attribute to indicate which hyperedge is the source and which is the target of the pointer. Computation, then, is graph rewriting.

As Qiaochu says, hyperedges are absurdly general. Likewise, the notion of data. To make this useful, one needs to constrain the form the hyperedges take. What is nice is that the need to constrain the way that state is represented is perfectly matched with the need in useful programming langauges to contrain the representation of data, and furthermore, one can often cleanly map the programming-driven constraints into reasonable constraints on the hypergraphs.

The idea crops up again and again the literature on graph transformations. A good stepping off point is Drewes, Habel, & Kreowski, 1997, Hyperedge Replacement Graph Grammars, In Rozenberg, Handbook of Graph Grammars and Computing by Graph Transformations.

Reference for model structure on CosimplicialAbelianGroups

There is a standard (simplicial) model category structure on the category $Ab^Delta simeq Ch^bullet_+(Ab)$ of co-simplicial abelian groups, whose fibrations are the degreewise surjections (and weak equivalences are the usual quasi-isos).

My question is about proper attribution: where does this first appear in citable form?. What is the canonical reference you would cite?

nt.number theory - Conditions that allow unique solutions for Linear Diophantine equations

(This posting became very long, so I should note that there are two alternative but nearly equivalent formulations of the same question being given. The first one asks for the optimal strategy for playing a game, the second is a more formally stated optimization problem. There is also a proposed solution for the n = 2 case, and an answer by Boris Bukh (below) for the unbounded case of [$a_1$, ..., $a_n$].)

You and I play a game:

I hand you an empty box and 'n' > 1 canisters of balls, where 'n' is agreed upon beforehand. The balls in each canister have a unique integer mass to my specification, 'L' < [$a_1$, ..., $a_n$] < 'M' (where 'L' and 'M' are some fixed, lowest and largest possible integer masses, respectively), and no two canisters will have balls with the same mass.

Now, after blindfolding myself, I ask you to fill the empty box with somewhere between zero or a finite integer number of copies, 'T', of each type of ball: [$x_1$, ..., $x_n$]. Here, 'T' is the same for all ball types.

When finished, you fully seal the box, hand it back to me, and ask for the copy numbers of each ball type. To accomplish this, all I am allowed to do is place the box on a scale to 'weigh' its total mass.

The reward system works as follows - the higher I can set the copy number threshold, 'T', the more money I win. However, if I set 'T' too high to properly guess the exact copy numbers, I lose an infinite amount of money and the game is over. Assuming I love money and hate risk, how do I choose the masses of the balls, [$a_1$, ..., $a_n$], such that I make the most money at no risk of financial ruin?

---

Interestingly, for the n = 2 case (though not for n > 2), the answer seems to be: Pick 'L' < [$a_1$, $a_2$] < 'M' such that the Lowest Common Multiple, LCM[$a_1$, $a_2$], is maximized over the allowed interval. Depending on 'L' and 'M', [$a_1$, $a_2$] are not necessarily prime.

LCM[$a_1$, $a_2$] also seems to always equal the maximum measured mass of the box for which unique copy numbers can be determined ($S_{max}$ from the below optimization formulation where 'T' can be different for the different masses/balls).

Intuitively this seems right, but is it true for all values of 'L' and 'M'?

---

(For finding 'T' in polynomial-time given masses [$a_1$, ..., $a_n$], please see note at bottom of page. Is there a better solution?)

---

We can also state this question as the following optimization problem -

I provide you with the number of terms, 'n', for a monomial sum (or linear Diophantine equation) of the form: $a_1$*$x_1$ + ... + $a_n$*$x_n$ = S, where 'L' < [$a_1$, ..., $a_n$] < 'M', and 'S' belong to the set of positive real integers while [$x_1$, ..., $x_n$] belongs to the set of integers $ge$ 0.

We now define a function #NonDegenerate([$a_1$, ..., $a_n$]) that outputs [k, $S_{max}$] where 'k' is the cardinality (i.e. number of elements) in the set [$S_1$, ..., $S_{max}$] which:

1. For the provided set [$a_1$, ..., $a_n$], must contain all possible sums, $a_1$*$x_1$ + ... + $a_n$*$x_n$ = $S_k$, for all sets of integers [$x_1$, ..., $x_n$] s.t. 0 < $S_k$ $le$ $S_{max}$.




2. Where all elements of the set [$S_1$, ..., $S_{max}$], i.e. all $S_k$, must have a single or unique solution [$x_1$, ..., $x_n$] for the given set of [$a_1$, ..., $a_n$].




3. Where $S_{max}$ is the largest possible sum satisfying conditions (1) & (2).

Now, for a given number of monomial terms 'n' (or if you are allowed to select 'n'), what is the most efficient strategy for selecting [$a_1$, ..., $a_n$] to maximize the output 'k' of the '#NonDegenerate' function?

Note on relationship to game that was described earlier - Here we're talking about maximizing the number of sums, $S_k$ < $S_{max}$, that have unique solutions. This should be equivalent to maximizing the threshold 'T' for the maximum possible copy numbers of balls in the first formulation of the problem under the condition that you won't allow yourself to lose the game.

(For finding $S_{max}$ in polynomial-time given [$a_1$, ..., $a_n$], please see note at bottom of page. Is there a better solution?)

---

Some computational results:

For expression $a_1$*$x_1$ + $a_2$*$x_2$ = S, over the range $x_1$, $x_2$ = (1, 100) and $a_1$, $a_2$ = (1, 100), max(#NonDegenerate) = 5049 for [$a_1$, $a_2$] = [99, 100] and $S_{max}$ = 9899.

(Mistake before where I used a result that set a minimum copy number min($a_k$) = '1' rather than the correct min($a_k$) = '0')

---

Note on counting solutions for the expression - $a_1$*$x_1$ + ... + $a_n$*$x_n$ = $S_k$, and a possible polynomial time algorithm to find $S_{max}$ or 'T' given the set [$a_1$, ..., $a_n$]:

As fleshed out in a previous post of mine (with help from Sam Nead) - "Counting Lattice Points on an N-simplex" (Counting lattice points on an n-simplex) - the problem of finding solutions to expressions of the form:

$a_1$*$x_1$ + ... + $a_n$*$x_n$ = S

Is equivalent to counting the number of integer lattice-points on (but NOT in the bounded area) the N-simplex being defined (i.e the real-number solution set to the expression). Since polynomial time algorithms exist for exactly enumerating integer points for rational polyhedron of fixed-dimension (due to Barvinok et al), there should also exist a straightforward polynomial-time algorithm for this optimization problem (via testing and incrementing $S_{max}$ or the corresponding value 'T' in the game description). But does a nicer strategy or solution exist?

at.algebraic topology - Do chains and cochains know the same thing about the manifold?

This question was inspired by Poincaré quasi-isomorphism

Let $M$ be a closed oriented $n$-manifold. The cap product with the fundamental class of $M$ induces an isomorphism $H^i(M,mathbf{Z})to H_{n-i}(M,mathbf{Z})$. Both the source and the target of this are rings. (For the definition of the homology intersection product see e.g. McClure http://arxiv.org/abs/math/0410450 or M. Goresky and R. MacPherson's first paper on the intersection homology.) It is not too difficult to show that the Poincar'e isomorphism respects the ring structure.

The question is: to which extent is this true on the chain level?

More precisely, Goresky and MacPherson's PL chains of a manifold form a partial commutative dga (see McClure's paper mentioned above). Singular cochains form a non-commmutative dga that can be completed to an $E_{infty}$-algebra, which is a different kind of structure. So one way to make the above question precise would be as follows:

1. Is there a natural way to turn the PL-chains on a PL-manifold into an $E_infty$ algebra? (In the above-mentioned paper McClure promises to do this in another paper, but I don't know if the details are available.)




2. If the answer to 1. is positive, then can one complete the chain level cap product with the fundamental cycle into an $E_{infty}$ morphism?

fourier analysis - Hypoellipticity of square root of laplacian

It is a well known result (sometimes called the Weyl lemma) that the laplacian in $mathbb{R}^n$ is hypoelliptic, i.e. if $f$ is a distribution s.t. $triangle(f)$ is smooth in an open set, than $f$ itself is smooth in the same open set. To establish the result one observes that:

1) $f in H^s(mathbb{R}^n)$ and $triangle{f} in H^s(mathbb{R}^n)$ than $f in H^{s+2}( mathbb{R}^n)$ ($H$ are ordinary $L^2$ Sobolev spaces)

2) the same results holds if $mathbb{R}^n$ is replaced by an arbitrary bounded open set $U$. Here one can define $H^s(U):=${$f:rho f in H^s(mathbb{R}^n) forall rho in C^{infty}_c(U)$}

3) every distribution $f$ lies in some $H^s(U)$, for some $s>-infty$
Then a kind of bootstraping argument and Sobolev embedding gives the result.

1) is very easy to establish (just look at the Fourier transform side), while the local version 2) is harder and requires the "local nature" of the laplacian (in fact of partial differentiation operators), as is encoded for example by the Leibniz rule (Reed and Simon has a complete proof).

Since on the Fourier trasform side $hat triangle(f)(xi) = -|xi|^2 hat{f}(xi)$ one can naturally define a square root of $-triangle$ as $hat{Lambda(f)}(xi) :=|xi|hat{f}(xi)$.

Here comes my question: Is $Lambda$ hypoelliptic?

The equivalent of 1) for $Lambda$ is trivially true, but 2) seems much harder because $Lambda$ appears to be "non local" (the values of $Lambda(f)$ on an open set seem to depend on the values of $f$ everywhere).

at.algebraic topology - Simplicial homotopy book suggestion for HTT computations

Echoing what Urs said, "But you should all be using the nLab more: if you want literature on quasi-categories, look up the references section on quasi-categories! :-) " and in regard to your question in particular, "See the nLab page on simplicial sets for links."

By looking at this nLab page on simplicial sets, in the references section you'll have found (as of this date, July 21, 2011 10:19 pm, EST):

Greg Friedman: An elementary illustrated introduction to simplicial sets

which is chock full of pictures illustrating the geometric ideas underlying the combinatorics of simplicial sets. As Friedman discusses in the introduction on the second and third pages of this paper,

"Here, for the most part, you won't
find many complete proofs of theorems,
and so these notes will not be
completely self-contained. Rather, I
try primarily to show by example how
the very basic combinatorics,
including the definitions, arise out
of geometric ideas and to show the
geometric ideas underlying the most
elementary proofs and properties."

Suffice it to say, those notes may be the end of your search in finding a concise introduction to simplicial sets that also helps develop your geometric intuition and the computation of products. You also might find the references I gave in answer to the question here helpful.

open problem - Topological version of Bogomolov’s question

I'm quoting a question from p. 753 of Gromov's recent paper Singularities, Expanders and Topology of Maps:

"Does there exist, for every closed oriented $n$-manifold $X_0$, a closed oriented $n$-manifold $X$ that admits a map
$X to X_0$ of positive degree and, at the same time, can be smoothly fibered over some
$Y$ with $dim(Y) = n − 2$ ? (Bogomolov’s original question concerns parametrization
of complex algebraic manifolds $X_0$ by algebraic manifolds fibred by surfaces.)"

I'm wondering where Bogomolov's question came from, and for what cases it is known and why it may be of interest?
Gromov doesn't give a reference, and searching for "Bogomolov conjecture" seems to bring up a different conjecture. Maybe an expert can point me quickly to a reference.

Also, if anyone has partial answers to Gromov's question, I would be interested. I think I can prove it for 3-manifolds, and there may be a 4-manifold topologist who might know something about the 4-dimensional case.

Addendum: I'll add my argument in the 3-dimensional case, then ask a question which would answer Gromov's question in dimension 4.

Any orientable 3-manifold is a cover of $S^3$ branched over the figure 8 knot $K$. The 3-fold cyclic cover branched over $K$ is a Euclidean manifold, which has a finite-sheeted cover which is a 3-torus. The preimage of the branched locus is geodesic, so we may find a product fibering of the 3-torus by tori transverse to the preimage of the branched locus. Thus, any covering of this cover will also fiber (by taking the preimage of the fibering). For a 3-manifold, we may take the common branched cover over $K$ with the 3-torus branched cover. This fibers since it covers the 3-torus, and has a non-zero degree (in fact bounded degree) map to the 3-manifold.

As mentioned in an answer to this question, any closed orientable PL 4-manifold is a branched cover over $S^4$ with branched locus a surface. One could try to generalize my 3-dimensional argument to this context. The key fact is that there is a cover of $S^3$
branched over the figure 8 knot which has a fibration transverse to the branched locus. So I ask the question: for any surface in $S^4$, is there a cover of $S^4$ branched over the surface which has a fibration by surfaces which are transverse to the preimage of the branched locus? I have no evidence for or against this question, it just seems like a natural generalization of the 3-D case.

One could also ask the analogous question in higher dimensions and in the algebraic category. But one would need to know the corresponding branched covering result first. For projective algebraic varieties, maybe it would be natural to consider branched covers over projective space, analogous to Belyi's theorem.

dg.differential geometry - Equivalent singular chains and differential forms, as functionals on forms, on compact Riemannian manifolds

On a compact Riemannian oriented manifold $M$,for each singular $k$-chain $sigma$ (with real coefficients), $sigma$ induces a linear functional on the $mathbb{R}$-vector space of differential k-forms, by integration of the form over $sigma$. At the same time the metric induces an inner product on that space, by $<alpha,beta>=displaystyleint_{M}{alphawedge *beta}$. This product also gives, for each given form, a functional on the space of forms.

I'm just playing around here with possible relationships between basic stuff I was learning about, but it seemed to me like an obvious way to compare singular chains and forms is to compare the induced functionals (kind of in the spirit of Poincare duality and Stokes' theorem, which pair classes of closed forms with classes of cycles. However, the restriction to only considering singular chains may not make sense in this context...since you just need to integrate k-forms on them, not take boundaries or anything...). For example, when can a chain $sigma$ and a form $omega$ have the same functional?

I believe one can show that for any $sigma$ there is a unique corresponding "dual" form so to speak, say $D(sigma)$, with the same functional. Since $M$ is compact, there exists a countable orthonormal basis $e_j$ for the space of k-forms, and every element is determined by its inner product with the basis elements (its coordinates). So if we have some chain $sigma$, we take $< D(sigma),e_j>$ to be $displaystyleint_{sigma}{e_j}$, and then $displaystyle D(sigma)= sum_{j}{left(int_{sigma}{e_j}right)e_j}$, and one checks using the basis again that by construction this form has the same functional as $sigma$. Furthermore, the functional of a form completely determines it, so a priori the dual form must be unique (and it doesn't matter that we chose a basis).

So my question is obviously first of all, does the above make sense? I don't recall seeing it yet. Another obvious question is the other direction - given a form, does it have a dual singular chain? (Or if one broadens from considering just singular chains?) If not, what can one say about the set of forms that do have duals, relative to the whole space of forms? (e.g. it might be dense.)

EDIT: Thanks, Petya, I guess I need to restrict to smooth singular chains. Also thanks Gonçalo for pointing out that I appear to really be talking about currents - I will take a look at the book! My remaining question: first of all, it seems to me like in the context of a compact Riemannian manifold, the space of k-currents is naturally identified with the space of k-forms via the inner product. So in this space, is the set of currents given by integration over a smooth k-submanifold a proper subspace? I understand that the point of currents is that in the general case they are broader, but in the compact case it seems like maybe that doesn't happen, and I'm having difficulty understanding the statements about the mass norm that seem to concern this question.

lo.logic - Higher-order axiomatisations of Euclidean Geometry?

I am currently thinking about the possibility to axiomatise Euclidean Geometry using higher-order axioms. The idea is that all objects are points, and that we only have two primitive notions: A three place predicate for betweenness, and a one-place third-order predicate indicating whether a function from a set of points to another set of points is a congruence mapping (so the existence of such a function between two given sets means that the sets are congruent in the intuitive way; the function maps points from the first set to corresponding points of the set congruent to it).

$ab equiv cd$ can then be defined to mean that there is a congruence mapping from {a,b} to {c,d}. The line through a and b can be defined to be {p|p is between a and b or a is between p and b or b is between p and a} $cup$ {a,b}.

Using these two primitive notions of betwenness and congruence mappings, it seems to me that quite a short and simple list of axioms can specify Euclidean Geometry: Three simple betweenness properties, one completeness axiom (similar to that for $mathbb{R}$, but using the betweenness relation rather than the less-than relation), one axiom ensuring the existence of enough congurence mappings, one axiom ensuring that relations between points are preserved by congurence mappings, and two axioms specifying the dimension of the space (one for the lower bound on the dimension, another for the upper bound).

My interest in such an axiomatisation is mainly philosophical: The two primitive notions correspond to concepts from our natural intuition and expirience of space (congruence mappings correspond to moves of an object in space without the shape of the object changing). The axiomatisation seems simpler than first-order axiomatisations like those of Hilbert and Tarski. And the higher-order nature of the system makes it possible to define lines, circles, triangle, quadrilaterals and any other shapes, which is not possible in first-order systems.

I have an idea for a proof that my axiomatisation specifies a space isomorphic to $mathbb{R}^n$ (for the $n$ used in the dimension axioms); but before I actually work out the proof, I want to know whether a comparable higher-order axiomatisation of Euclidean Geometry already exists. Unfortunately, I couldn't find any higher-order axiomatisations of Euclidean Geometry. Does anyone know about such axiomatisations or attempts at them?

mrna - Is exon order always preserved in splicing?

After performing a quick literature search, I am, as with GWW, unable to provide any literature against this occurring, although this paper by Black (2005) states that exons in multi-exon pre-mRNAs are always maintained in order.

Black DL. 2005. A simple answer for a splicing conundrum. Proceedings of the National Academy of Sciences of the United States of America 102: 4927–8..

Separate components of the spliceosome recognise sequences at the the start and end of each intron, along with a branch point adenine and some other conserved (highly in the case of yeast) regions upstream of the 3' end. The components seem to assemble in a particular order, which is 5' to 3' directional.

The general consensus seems to be that the spliceosome moves along the pre-mRNA from 5' to 3' removing the introns and splicing the exons together to form the mature transcript, ready for translation. The introns are subsequently degraded. In the case of eukaryotes some processing is required to transport the mRNA out of the nucleus to the ribosomes in the cytoplasm.

The mRNA would have a start codon near the 5' terminus and stop codon near the 3' end, at the boundaries of the CDS, and it isn't clear to me how this structure could be maintained if exon order didn't follow the 5' to 3' assemblage. I should imagine that the protein could be affected in much a similar way to exon skipping, possibly resulting in a truncated, inactive or ineffective protein. As protein folding is determined by the interactions between the amino acids, any change in exon order (secondary structure) is likely to result in a different tertiary structure.

morse theory - Do higher dimensional maxima of a real valued multivariable function form a cell complex?

Suppose $f: R^n rightarrow R$ is a positive real valued function. Let $lambda_1, ldots , lambda_i$ be the first $i$ ordered eigenvalues of the Hessian $Hess(f)$. Let $v_1, ldots, v_i$ be the corresponding unit eigenvectors. Suppose $V = [v_1, ldots, v_{n-d}] $. Define a $d-$dimensional ridge point as a point where $V^T nabla f = 0$ and where $lambda_1, ldots, lambda_{n-d} < 0$. Each point in the support of $f$ can then be classified as a ridge point. My question is, does this classification yield a cell complex? Or at least, are the $k$ dimensional ridge points always bounded by $k-1$ dimensional ridge points? This construction seems close enough to a Morse complex but it's different in that I'm only interested in the local maxima, and that two maxima need not be joined by an integral curve. Any help would be appreciated, thanks!

ca.analysis and odes - l^p space inequality related to compressed sensing

I'm trying to read Donoho's 2004 paper Compressed Sensing and am having trouble with a supposedly trivial statement (equation 1.2 on page 3).

He makes the sparsity assumption on $theta in mathbb{R}^m$ that for some $0<p<2$ and $R>0$ we have $|theta|_pleq R$. Then if $theta_N$ denotes $theta$ with everything except the $N$ largest coefficients set to $0$ he claims that $| theta-theta_N |_2 leq zeta_{2,p} cdot | theta |_p cdot (N+1)^{1/2-1/p}$ for $N=0,1,2,ldots$ where $zeta_{2,p}$ depends only on $p$.

I've tried writing out the definitions of various things. I've noticed that the $N$th largest coefficient must satisfy $midtheta_imid leq RN^{-1/p}$ but I can't figure out how the result above follows.

I'm also having some difficulty thinking about $ell^p$ spaces with $0<p<1$, in particular knowing what results from the $p>1$ theory apply. Does anyone know some good notes or a book that covers this?

ct.category theory - Primacy of arcs/arrows over vertices/objects

Qu 1: At about the time of Freyd's book there were two approaches to defining categories. One came from algebraic topology and homological algebra, thus from Eilenberg and MacLane and used the objects and arrows definition, the other was motivated by differential geometry and used the arrows only formalism. This second one is perhaps better suited to those areas where the arrows are what is seen first. For instance, when introducing the concept of the fundamental groupoid of a space then you can think of the idea as a set with a partially defined composition satisfying certain rules and that has distinct advantages for that setting. Ehresmann wrote his book on categories from this viewpoint, but some of the basic ideas do end up being less clear from that viewpoint, others are perhaps clearer. That approach is also linked to more algebraic ideas such as inverse semigroups.

The first 'objects plus arrows' approach is thought to be more accessible to researchers with a `standard' mathematical background e.g. from algebra or algebraic topology. There the objects are usually thought of as being what is being studied and the morphisms are a tool for that study.

The recent use of categorification, quasicategories, internal categories, enriched categories and other similar ideas, tends to show that both viewpoints are best kept in balance, meeting in that higher categorical area.

Put simply I thing the answer to your question is: historically the comparison of objects using arrows was the more pressing application to start with. It came to dominate. More researchers came to use it.

Now the question arises `which to use with a given audience? and that is a hard one to answer.

lo.logic - In what sense Fraissean view point shows Model Theory can be done without any formal syntax and deduction rule?

This is a partial answer to the above question. It is too long for a comment. I write it hear hoping to hear idea from those senior than me, and in case it is useful.

Here is some back ground, you might skip it if you are familiar with Poizat's definition:

There are two definitions of p- equivalent given in Poizat's A course in Model Theory, one via local isomorphism and the other via formal language. I think to compare the two view, it is crucial to compare this twos definitions.

Let ${bf M}=(M, R)$, ${bf N}=(N, S)$ structures with $ R, S$ $m$-ary relations.

Formal language definition:

Two $n$-tupe $vec{a},vec{b}$ are $p$-equivalent if and only if they satisfy the same formula in the language with quantifier rank at most $p$.

Local isomorphism definition: (Fraissean point of view)

A local isomorphism $s$ from $bf M$ to $bf N$ is defined to be an isomorphism between the a restriction of $bf M$ to a finite set $vec{a}$ to the restriction of $bf N$ to a finite set $vec{b}$.
0-isomorphism are local isomorphisms. A local isomorphism $s$ is a $p+1$-isomorphism iff

1) Forth condition: for any element $c$ in $M$ there is $d$ in $N$, and $t$ a $p$-isomorphism which map $c$ to$d$ and extends $s$.

2) Back condition: for any element $d$ in $N$ there is $c$ in $M$, and $t$ a $p$-isomorphism which map $c$ to $d$ and extends $s$.

Two $n$-tupe $vec{a},vec{b}$ are $p$-equivalent if there is a $p$ automorphism that maps one into another

First, we try to answer the question about syntax. We can unravel the local isomorphism definition to make it more like the language one, we get the following:

Two $n$-tupe $vec{a},vec{b}$ are $p$-equivalent iff all the following are satisfied

$ forall c_p in M, exists d_p in N,$ $ forall c_{p-1} in M, exists d_{p-1} in N,$...( all statements about $vec{a}, c_p, c_{p-1}, c_{p-2}, ...c_1 ) leftrightarrow$ ( all statements about $vec{b}, d_p, d_{p-1}, d_{p-2}, ...d_1 $ )

$ forall d_p in N, exists c_p in M,$ $ forall c_{p-1} in M, exists d_{p-1} in N,$...( all statements about $vec{a}, c_p, c_{p-1}, c_{p-2}, ...c_1 ) leftrightarrow$ ( all statements about $vec{b}, d_p, d_{p-1}, d_{p-2}, ...d_1 $ )

... ( all alternation between $c_i in M$ and $d_i in N$).

I think was wrong in the question. There was some genuine difference between the Fraissean view and the traditional view. In both cases we do use (formal or informal) quantifiers. But in traditional view the quantifier was on each domain and in the Fraissean view the quantifier is running back and forth between two domains. However, this difference does NOT shows Fraissean view point is anymore free from language than the traditional view. (The quantifier is even more complicated, in fact. But it is not the point).

I think the difference is like this: The traditional view point characterize local morphism in term of invariance. (In this case, it preserve the statements with at most p quantifier). The Fraissean view point describe the morphisms directly through induction.
Both are useful. The traditional view point is used in the proof of compactness (I don't know if this can be done in an easy way using the Fraissean view). The Fraissean view is important in many applications: To show that many theories are complete.

How about deduction rules?

I think we can define the deduction rule on the model side in an adhoc way (or may be not so adhoc) but it seems rather irrelevant here. So my previous concern is not correct.

I think that it is right that model theory can be developed independent of deduction rules. Perhaps that is because two equivalent statement are exactly the same to all model. I still don't understand exactly the relationship between Fraissean approach and this.

foliations - Integrability of distributions close to a given one.

No smooth non-integrable distribution can be $C^0$ approximated by integrable ones.

For example, consider the following 2-dimensional distribution in $mathbb R^3$: the plane at $(x,y,z)inmathbb R^3$ is spanned by vectors $(1,0,0)$ and $(0,1,x)$. Perturb this distribution within a small $C^0$ distance $varepsilonll 1$. Consider the square in $mathbb R^2$ with vertices $(0,0)$, $(1,0)$, $(1,1)$, $(0,1)$ and let $gamma$ be its boundary (counter-clockwise). This $gamma$ has a "lift", that is a curve $tildegamma$ in $mathbb R^3$ which is tangent to the distribution and whose projection to the horizontal plane is $gamma$. The lift is found by solving an o.d.e., so it is unique if the distribution is smooth but may be non-unique if it is only $C^0$. In the non-perturbed case, the unique lift ends at $(0,0,1)$, hence in the perturbed case all lifts end near $(0,0,1)$. This implies that the distribution is not integrable - if it was integrable, there would be at least one lift (the one contained in a leaf of a foliation) that ends near the origin.

The proof in the general case is similar.

ac.commutative algebra - Alternative proof of unique factorization for ideals in a Dedekind ring

I'm writing some commutative algebra notes, but I'm facing a difficulty in organizing the order of the topics. I'd like to have the topics about factorization before speaking of integral closure. This is fine, as long as I talk of UFD and primary decomposition.

The problem is that a topic worth mentioning is the factorization theory for ideals in a Dedekind ring. Now, there are a few ways to define a Dedekind ring, but I guess one of the most natural is a Noetherian domain, integrally closed, of dimension 1.

At this point I haven't yet introduced the concept of dimension, nor integral closure. It is easy not to speak of dimension, and just say that every prime ideal is maximal. I'm also fine in writing out explicitly what integrally closed means.

The real problem is to get a proof of unique factorization for ideals without using anything about integral closure, apart from direct arguments. For instance, I'd be fine in saying: "...so this element satisfies this monic equation, hence it is in A." Less so in saying "...so this element lies in a ring which is finitely generated as an A-module, hence it is integral. Since it is in the field of fractions of A, is must belong to A."

The only missing step in proving that ideals in a Dedekind ring satisfy unique factorization is the fact that primary ideals are prime powers.

Is there a direct proof of this fact which does not rely on anything about integrally closed domains, apart from the definition?

I should make clear that other standard techniques are available at this point: localization, Noetherian and Artinian stuff, primary decomposition, symbolic powers and so on.

I should also say that changing the order of the topics woule a major headache. I have thought out for long the order, and this is the only point where I get things in the wrong order. If possible, I would like to leave it as it is.

Edit (added in response to KConrad comment).

The steps which are easy are the following. Since $A$ is Noetherian, a primary decomposition exists. Since every prime is maximal, there are no embedded primes, so all primary components are unique. Finally, using again that every prime is maximal, all primary components are coprime, so intersections become products. So the only step where one uses integrality is the proof that the primary ideals are actually prime powers.

For the definition, there is no need to speak about integral closure, let alone proving that the integral closure is a ring. The integral domain $A$ is said to be integrally closed if every element $x$ of the quotient field of $A$, which satisfies a monic equation $x^n + a_{n-1} x^{n-1} + cdots + a_0$ with coefficients in $A$, is itself in $A$.

As for the examples, the compromise for now is to list some number rings, with the promise that it will be shown in a later section that these are actually Dedekind rings. Of course I'm not happy with this solution. But I'm also not happy with putting an aside on integral closure in the middle of a section about factorization and primary decomposition; even less so because there IS a later section on integral closure.

I cannot even reverse the two, because in the section of integral closure I want to be able to speak about the integral closures of $mathbb{Z}$, so I need the factorization theory for Dedekind rings.

dg.differential geometry - Frobenius Theorem for subbundle of low regularity?

Let me conisder the case when the distribution of planes is of codimension 1 and explain why in this case it is enough to have $C^1$ smoothness in order to ensure the existence of the folitation.

In the case when the distribution is of codimension 1, you can formulate Frobenius Theorem in terms of 1-forms. Namely you can define a non-zero 1-form $A$, whose kernel is the distribution. The smoothness of this 1-form will be the same as the smoothness of the distribution. Now, you can say that the distribution is integrable if $Awedge dA=0$. This quantity is well defined is A is $C^1$. Let me give a sketch of the proof that $Awedge dA=0$ garanties existence of the foliation is A is $C^1$.

The proof is by induction

1) Consider the case $n=2$. In this case it is a standard fact of ODE, that for a $C^1$ smooth distribution of directions on the plane the integral lines are uniquelly defined.

2) Conisder the case $n=3$. We will show that the foliation exists locally near any point, say the origin $O$ of $R^3$. The 1-form A, that defines the distribution is non vanishing on one of the coordinate planes, say $(x,y)$ plane in the neighborhood of $O$. Take a $C^1$
smooth vector field in the neigborhood of $O$ that is transversal to planes $z=const$
and satisfies $A(v)=0$. Take the flow correponding to this vector field. The flow is $C^1$ smooth and moreover it preserves the distribution of planes $A=0$. Indeed, dA vanishes on the planes A=0 (by the condition of integrability), and we can apply the formula for Lie derivative $L_v(A)=d(i_v(A))+i_v(dA)=i_v(dA)$. Finally, we take the integral curve of the restriction of $A=0$ to the plane $(x,y)$ and for evey curve conisder the surface it covers unders the flow of $v$. This gives the foliation.

This reasoning can be repeated by induction.

A good refference is Arnold, Geometric methods of ordinary differential equations. I don't know if this book was transalted to English

finite groups - Applications of fusion systems

Lots of results in group cohomology only have topological proofs using the techniques of Bob Oliver and his (generalized) collaborators. For instance, many results along the lines of "controls fusion iff controls cohomology" only have topological proofs using the same techniques that Bob Oliver called fusion systems (though I think some of the papers stick to the topological language). "Controls fusion" is a very old term predating fusion systems by 50 years, so I think of this as a pretty pure finite group cohomology result.

I think it is common to call these topological results by the name "fusion" results, even if fusion systems are not used directly, but rather p-completed classifying spaces are used (also known as p-local groups and such), even if the fusion system used to define the topological space is not prominent. Allowing such abuse of language, one of my favorite examples is the topological proof that the famous Z*-theorem holds for odd primes too: MR1125010. It was proven later using more pure finite group theory, but I suspect lots of people prefer the topological proof.

In modular representation theory, the work of Puig on nilpotent blocks is (as far as I know) literally defined in terms of fusion systems and gets results on the representation theory using only conditions on the fusion systems. One also has some nice descriptions of the representation type of blocks of dihedral defect in terms of the fusion system induced on the block (I believe Linckelmann's introduction gives this as an example).

More historically, the classification of finite groups with dihedral (and then for semi-dihedral/wreathed) begins by dividing clearly into cases based on which fusion system occurs. This just organizes the (couple hundred page) papers, so I guess whether it is essential depends on how practical you are.

Perhaps the most "exciting" answer is not quite ready yet, but Michael Aschbacher and collaborators have begun to recast the classification of finite simple groups in terms of fusion systems. It is quite surprising and comforting that several very important steps in the classification are radically easier in the fusion system case. The fusion system theorems would also have as side-effects corresponding theorems in modular representation theory and the theory of p-local groups.

Let me know if you want references for any of the wishy washy terms, but basically read Linckelmann's introduction, read a few papers of BLO (Broto–Levi–Oliver), and check out the slides from any recent finite group theory conference, and you should have some pretty convincing evidence that fusion systems are opening up a very bright future for finite group theory.

nt.number theory - Bound on the number of solutions of a specific Diophantine equation

Falco had asked a question regarding sum equals to product ( Sum Equals Product)

I have a question in the orthogonal direction. Suppose $X_1,X_2,...,X_n$ are variables and we allow $X_i$'s to take only natural numbers. Look at the following Diophantine equation
$X_1+X_2+ dots + X_n = X_1 X_2 ldots X_n$. Any solution of this equation satiesfies the property that the sum of the entries is equal to their product.

It is easy to see that for every $n$, there are only finitely many solutions of the above equation, denote that number by $f(n)$. It is easy to see that there is no absolute constant $k in mathbb{N}$ such that $f(n) < k$ for every $n$. (look at the sequence $x_n= n!+1$, then $f(x_n) > n$, for $n geq 5$)

If $(x_1,..., x_n)$ is a solution of the above equation then we have $prod_{i=1}^{n-1} x_i < n$. From here one can have a very crude bound for $f(n)$.

Question: 1) What is the best upper bound for $f(n)$?
2) Is there an asymptotic behaviour of $f(n)$ as $n$ tends to infinity.

gt.geometric topology - Collapsing the medial axis of a polytope

Let X be a convex polyhedron in hyperbolic 3-space.

Let M be the medial axis of X.

Question: Is M collapsible?

It is easy to see that M is contractable.
In the case of Euclidian 3-space, instead of hyperbolic 3-space, I think I have an elementary proof for the analogues statement.
In hyperbolic space, I guess that the statement still holds, but I do not have a proof.

I would appreciate comments and references for the above question.

Definitions for the above question

The MEDIAL AIXS of X : consider a maximal round ball inscribed in X (maximal with respect to set inclusion), which at least has two points of tangency (on $partial X$). Take the union of the centers of all such maximal balls inscribed in X. Then, this union is called the medial axis of X, and it is a polygonal complex, to be precise, after adding the 1-skeleton of the boundary of X.

M is COLLAPSIBLE: There is a strong deformation retract of M to a point that is a composition of certain simplicial homotopies, each of which reduces a single cell.

What is known about the $k^{mathrm{th}}$ powers of graphs of diameter $k+1$?

Let $G$ be a simple unweighted graph. The distance between two vertices $u,v$ in $G$ is the length of a shortest path in $G$ between $u$ and $v$. The diameter of $G$, denoted $diam(G)$, is the largest distance between two vertices in $G$. For a natural number $k$, The $k^{mathrm{th}}$ power of $G$, denoted $G^{k}$, is the graph obtained from $G$ by adding edges between every two vertices $u,v$ where the distance between $u,v$ in $G$ is at most $k$.

Let $mathcal{F}_{k}$ be the family of all graphs that are the $k^{mathrm{th}}$ powers of graphs of diameter $k+1$. That is,

$mathcal{F}_{k} = {G^{k}mid diam(G)=k+1}$

$mathcal{F}_{1}$ is the set of all graphs of diameter $2$, and for all $kge2$, $mathcal{F}_{k}subseteqmathcal{F}_{2}$.

Is something more known about the structure of the graphs in $mathcal{F}_{k}$ for $kge2$? In particular, are these containments strict? Do we get more structure the higher the value of $k$?

Thanks for any ideas, pointers, and/or references on this.

neuroscience - How does an inhibitory synapse communicate to the cell body of a neuron?

An inhibitory synapse works just like a stimulatory one!

When a presynaptic neuron fires it will release a neurotransmitter at its terminal(s). This neurotransmitter can be excitatory or inhibitory, the main excitatory one being glutamate and the main inhibitory one GABA.^*

GABA and Glu are far from being the only neurotransmitters in the brain, they're just a classic example, so we'll stick with them. When the neurotransmitter is released it binds to receptors on the postsynaptic neuron (provided, of course, that the postsynaptic neuron expresses these receptors).

Various GABA and Glu receptors exist, both ionotropic (i.e. channel-receptors that let ions flow through the membrane upon binding of the ligand) and metabotropic (i.e. receptors which activate an intracellular pathway that does not per se start the flow of ions, but that can induce it or prevent it indirectly).
For simplicity we'll stick to ionotropic receptors.

Glu binds to three types of ionotropic receptors: AMPA, NMDA and kainate receptors. These have different kinetics/properties, but the bottom line is that they let cations (positively charged ions, such as Na+ and Ca++) into the cell. When this happens a postsynaptic depolarization happens, which is named EPSP (excitatory post-synaptic potential).
So, if the resting membrane potential was, say, -57mV, it will become, for instance -52mV.
This means that, if the threshold potential for firing an action potential were -43mV the cell, which first needed a 14mV depolarization to fire now will need a 9mV depolarization.
If subsequent EPSP sum they can depolarize the cell sufficiently to reach threshold and let the cell fire.

This image from Wikipedia is quite self-explicatory: in this case 3 synaptic events generated 3 EPSPs that summed, making the cell depolarize enough to reach threshold potential, and generate an action potential, that will then propagate to the cell body.

GABA, on the other hand, binds to the GABA-A receptor, which is a chloride channel. In most cases, upon binding of GABA, GABA-A lets Cl- in the cell, effectively hypopolarizing it and generating an IPSP (inhibitory post-synaptic potential). The situation is the same (but opposite) to Glu, this time, though, the potential becomes more negative.

EPSP and IPSP can and do happen at the same time: as they can vary in frequency and intensity depending on the firing frequency and firing pattern of the presynaptic neuron, a pretty much continuous range of voltages can be achieved in the postsynaptic neuron.

Other controls over this process come from metabotropic receptors that can, for instance [de]phosphorylate (add or remove a phosphate group) ion channels modulating their permeability to ions or from the different kinetics of the different channels (for instance certain channels stay open for longer or open in a delayed manner etc), allowing for fine-tuning of the system.

---

^*I am making a gross generalization here. A neurotransmitter is not excitatory or inhibitory per se, it depends on the context. For instance stimulatory GABA synapses do exist.

ag.algebraic geometry - Why does the group law commute with morphisms of elliptic curves?

This answer is an elaboration on some of the earlier ones. Throughout we suppose
that $phi:E_1 rightarrow E_2$ is a morphism of elliptic curves (so in particular
it preserves the origins, i.e. $phi(O) = O$).

---

Here is a concrete form of the rigidy argument:

If $P$ is in $E_1$, then we define a map $phi_P:E_1 rightarrow E_2$ via
$phi_P(X) = phi(X + P) - phi(P)$. Note that $phi_O = phi.$
(Here we use the fact that $phi(O) = O$.)
Thus $phi_P$ is a family of map $E_1 rightarrow E_2$, parameterized by $E_1$,
passing through $phi$, with the property that $phi_P(O) = O.$

Now $phi_P$ induces a corresponding local map on local rings
$phi_P^*: mathcal O_{E_2,O} rightarrow mathcal O_{E_1,O},$
and hence also on the finite length quotients
$(phi_P^*)_n: mathcal O_{E_2,O}/mathfrak m^n rightarrow mathcal O_{E_1,O}/
mathfrak m^n$. (Here we use $mathfrak m$ to denote the maximal ideal
in each of the local rings.)

If $k$ is our ground field, then the source and target of $(phi_P^*)_n$ are
just finite-dimensional vector spaces, and so
$P mapsto (phi_P^*)_n$ is a morphism (of varieties) from $E$ to a finite dimensional
(and in particular, affine!) space of matrices. Since $E$ is projective and connected,
it must be constant.

Thus $(phi_P^*)_n = (phi_O^*)_n$ for all $n$, and so passing to the limit we find
that $phi_P^* = phi_O^*$. Thus $phi_P$ and $phi_O$ induce the same map on
local rings at $O$, and since $E$ is irreducible, they therefore coincide.
(If you like, passing to fraction fields, we see that they induce the same maps
$K(E_2)rightarrow K(E_1)$, and hence coincide as morphisms of curves.)

Thus $phi_P = phi_O = phi.$ Unwinding the definition of $phi_P$,
we find that $phi(P + X) = phi(P) + phi(X)$ for all $X$, and thus that
$phi$ is a group homomorphism.

---

Here is a concrete version of the argument with Picard and divisors:

To show that $phi$ is a homomorphism, it
is easy to see that it suffices to show that $P + Q + R = O$ implies that
$phi(P) + phi(Q) + phi(R) = O.$ (This uses the fact that $phi(O) = O$; hopefully no confusion
is caused by using $O$ to denote the origin on both $E$ and $F$.)

Now $P + Q + R = O$ (in the group law of $E$) if and only if there is a rational function $f$ such that
div $f$ = P + Q + R - 3 O (where now the right hand side is a divisor on $E$); i.e. if
and only if $P + Q + R - 3 O$ is a principal divisor. (Concretely, if $E$ is given
by a cubic Weierstrass equation in ${mathbb P}^2$ with homogeneous coordinates
$X$, $Y$, and $Z$, then $P + Q + R = O$ when $P$, $Q$, and $R$ are collinear, and then
if $ell(X,Y,Z)$ is the equation of the line passing through them, the function $f$ can be taken to be $ell(X,Y,Z)/Z^3$.)

Similarly $phi(P) + phi(Q) + phi(R) = O$ in the group law on $F$ if and only
if the divisor $phi(P) + phi(Q) + phi(R) - 3 O$ is principal.

So we are reduced to showing that $phi$ takes principal divisors to principal divisors.

This is a general property of maps of smooth projective curves: if $phi$ is constant,
there is nothing to show. Otherwise, if $phi:C rightarrow D$ is non-constant,
then it induces a finite extension of function fields $K(D) hookrightarrow K(C)$,
and we have the corresponding norm map (in the usual sense of field theory)
$K(C) rightarrow K(D)$. It turns out that for any function $f in K(C)$,
we have div$(text{norm of }f) = phi(text{div }f)$. (This is an exercise
whose difficulty will vary with your comfort level with the material; if you understand
the basics of rational functions and divisors on curves well, then it is not too
hard.)

co.combinatorics - Diagonally-cyclic Steiner Latin squares

A Steiner triple system is a decomposition of $K_n$ into $K_3$, such as $S={013,026,045,124,156,235,346}$. Steiner triple systems give rise to a Steiner Latin squares, such as $L$ below.

[L=left(begin{matrix}
0 & 3 & 6 & 1 & bf{5} & 4 & 2 \\
3 & 1 & 4 & 0 & 2 & bf{6} & 5 \\
6 & 4 & 2 & 5 & 1 & 3 & bf{0} \\
bf{1} & 0 & 5 & 3 & 6 & 2 & 4 \\
5 & bf{2} & 1 & 6 & 4 & 0 & 3 \\
4 & 6 & bf{3} & 2 & 0 & 5 & 1 \\
2 & 5 & 0 & bf{4} & 3 & 1 & 6
end{matrix}right)]

We define $L=(l_{ij})$ by $l_{ii}=i$ for all $i$ and $l_{ij}=k$ whenever $ijk$ is a triangle in $S$.

Note: Typically, Steiner Latin squares are viewed in an algebraic context and referred to as "Steiner quasigroups" -- Steiner quasigroups correspond to isomorphism classes of Steiner Latin squares, whereas for this question, I'm interested in the "labelled" case.

In some instances, such as $L$ above, the Latin square obtained is a diagonally-cyclic Latin square. That is, $L$ satisfies the identity $l_{(i+1)(j+1)}=l_{ij}+1 pmod n$, for all $i,j in mathbb{Z}_n$, where the indices are taken modulo $n$ also. I've highlighted (in bold) an orbit of an entry of $L$ under this symmetry.

Which Steiner triple systems give rise to diagonally-cyclic Steiner Latin squares?

The above question was my original question, however, as Douglas Zare points out, these are precisely the Steiner triple systems that admit the automorphism $(0,1,ldots,n-1)$.

Proof: If $L$ is a Steiner Latin square derived from $S$ then $(i,j,k)$ is an entry in $L$ if and only if it $ijk$ is an element of $S$. For $L$ to be diagonally-cyclic, if $(i,j,k)$ is an entry of $L$ then so is $(i+1,j+1,k+1) pmod n$. Therefore $(i+1)(j+1)(k+1)$ is also an element of $S$. The converse is true by definition.

Since that was such an easy task, lets look at a (hopefully) more interesting question.

Let $L=(l_{ij})$ be a diagonally-cyclic Steiner Latin square. Let $sigma$ be the permutation defined by $sigma(j)=l_{0j}$ (that is, the first row of $L$). Then $sigma$ is an orthomorphism of $mathbb{Z}_n$. That is, $sigma$ is a permutation of $mathbb{Z}_n$ and the map defined by $i mapsto sigma(i)-i pmod n$ is also a permutation of $mathbb{Z}_n$.

In the above example $sigma=(0)(13)(26)(45)$.

Which orthomorphisms of $mathbb{Z}_n$ arise from diagonally-cyclic Steiner Latin squares?

pr.probability - Conditional probabilities are measurable functions - when are they continuous?

Even if your probability measure is absolutely continuous with respect to Lebesgue measure on $Omega={mathbb R}^2$, I don't think this suffices for the function $f$ you have defined to be continuous (just take $X$ to be independent from $Y$, i.e. your probability measure is just the product of two probability measures, "one on each axis", and choose the one for $X$ to be something in $L^1({mathbb R}, {mathcal B}, dx)$ which is discontinuous.

On the other hand, if ${mathbb P}$ is not just absolutely continuous with respect to Lebesgue measure on $Omega$, but has a continuous density function wrt said measure, then your function $f$ will be continuous -- just because integrating over a ball of radius $eta$ with centre $eta$ can only smooth things out, so that continuity of the original density function goes over to continuity of your conditional probability. [This is a fairly straightforward observation using basic properties of usual integration in the plane.]

So in your example, the Gaussian structure isn't really relevant as far as I can see. Also, if the original density function is strictly positive on the cylinder ${(x,y) : |y-y_0|<eta }$, then the conditional probability you've defined will also be strictly positive; this condition is evidently not necessary, but I suspect in the examples you're interested in something like it should hold.

In between these two extremes, I'm not sure what else one can say. Perhaps, from your point of view, it's more important to go up to infinite-dimensional $Omega$ but place restrictions on the kind of probability measure which you wish to consider.

reference request - Infinite electrical networks and possible connections with LERW

I've been exposed to various problems involving infinite circuits but never seen an extensive treatment on the subject. The main problem I am referring to is

Given a lattice L, we turn it into a circuit by placing a unit resistance in each edge. We would like to calculate the effective resistance between two points in the lattice (Or an asymptotic value for when the distance between the points gets large).

I know of an approach to solve the above introduced by Venezian, it involves superposition of potentials. An other approach I've heard of, involves lattice Green functions (I would like to read more about this). My first request is for a survey/article that treats these kind of problems (for the lattices $mathbb{Z}^n$, Honeycomb, triangular etc.) and lists the main approaches/results in the field.

My second question (that is hopefully answered by the request above) is the following:

I noticed similarities in the transition probabilities of a Loop-erased random walk and the above mentioned effective resistances in $mathbb{Z}^2$. Is there an actual relation between the two? (I apologize if this is obvious.)

tag removed - Where can I buy Napier's Bones/Rods?

Avoid the website mentioned in answer number 2 above. I make presentations at rendezvous all over the Midwest and at my seminar I demonstrates Napier's Bones. I, unfortunately, bought a set from an eBay dealer who sells the very same set,
http://www.uniquecanes.com. The construction was terrible. The rods were not even square. The tabulat's index rod was not square to the tabulat, and the silk-screen printing did not align correctly, especially for the square root and cube root rods. The box the set came in, however, was well constructed. I had a great deal of difficulty trying to convince "ajsfixit" to make amends. He never did. the price of the set was approx $80,but I think it is now available for around $45. Finally, the set is not a replication of Napier's Rods, if you're interested in historical accuracy. My recommendation: depending on how authentic you desire, study up on the rods via Google and then have a local craftsman make a set for you.

The state space of the stabilization of a C*-algebra

From the general point of view of $C^*$-algebra theory, Bill Paschke mentioned to me today an interesting classification of states (or even, positive functionals) on the stabilization of $A$ as follows:

Proposition. Let $A$ be unital $C^{ast}$-algebra, $H$ be a Hilbert space and $varphi$ be a positive linear functional on $Aotimesmathcal{K}(H)$. Let ${cal L}^1(H)$ denote the ideal of trace-class operators on $H$. Then there exist a Hilbert space $H_{varphi}$, a representation $pi:Arightarrow B(H_varphi)$ and an operator $S:Hrightarrow H_{varphi}$ such that $S^*Sin{cal L}^1(H)$ (so $S^{ast}pi(a),Sinmathcal{L}^1(H)$ for $ain A$), and $varphi(aotimes K)={rm tr}(S^{ast}pi(a),S,K)$ for all $ain A$ and $Kinmathcal{K}(H)$.
Moreover, $varphi$ is a state iff ${rm tr}(S^{ast}S)=1$.

Proof. Since ${cal K}(H)^{ast}cong{cal L}^1(H)$, any positive linear functional $varphi$ can be regarded as a completely positive map $T:Arightarrow{cal L}^1(H)$ with $varphi(aotimes K)={rm tr}(T(a)K)$. Define a sesquilinear form on the algebraic tensor
product $Aodot H$ by $$langle aotimesxi,botimesetarangle_{varphi}:=langle T(b^{ast}a)xi,etarangle_{H},$$ set $N_{varphi}={rm span}{aotimesxiin Aodot Hmidlangle T(a^{ast}a)xi,xirangle_{H}=0}$ and $H_{varphi}:=overline{Aodot H/N_{varphi}}$. Then we can define a representation $pi:Arightarrow B(H_varphi)$ by
$$pi(a)(botimeseta+N_{varphi}):=abotimeseta+N_{varphi}.$$ Now, let $S:Hrightarrow H_{varphi}$ be the operator defined by $$Sxi:=1otimesxi+N_{varphi}.$$ Then $S^{ast}:H_{varphi}rightarrow H$ is given by $$S^{ast}(botimeseta+N_{varphi})=T(b)eta,$$ and we have $S^{ast}S=T(1)in{cal L}^1(H)$. Moreover, $S^{ast}pi(a),S=T(a)$,
which is what we need. It is easy to see that $||varphi||={rm tr}(S^{ast}S)$. Q.E.D

graph theory - How to estimate the growth of the probability that $G(n, M)$ contains a $k$-clique

You might take a look at Chapter VII of Bollobas. In particular,
Theorem VII.1.7 -- which is simple enough that he doesn't bother providing a proof -- states that the expected number of $k$-cliques in $G(n,M)$ is, setting $N={n choose 2}$ and $K={k choose 2}$,
$$
{n choose k} {n-K choose M- K} {N choose M}^{-1}.
$$
Also, Theorem VII.3.7 states that if $M=o(n^{-2/(k-1)})$ then with probability tending to one, $G_{n,M}$ contains no $k$-clique, whereas if $M/n^{-2/(k-1)} to infty$ then with probability tending to one $G_{n,M}$ does contain a $k$-clique. I know this doesn't fully answer your question but it may help.

Incidentally, (you probably already realize that) it is a priori possible (though I don't think it is the case) that, for example, $t_k(M+1)-t_k(M) geq frac{1}{mathrm{poly}(n)}$ for all ${k choose 2}leq M leq lceil frac{(k-1)N}{k}rceil$, since all we really know by Turán is that
$$
sum_{M=K}^{lceil(k-1)N/krceil} (t_k(M+1)-t_k(M)) = 1.
$$

Suggestions for a good Measure Theory book

Well, I personally HATE Halmos' Measure Theory, even though an entire generation grew up on it. My favorite book on measure and integration is available in Dover paperback and is one of my all time favorite analysis texts: Angus Taylor's General Theory Of Functions And Integration. Lots of wonderful examples and GREAT exercises along with discussions of point set topology, measure theory both on $mathbb{R}$ and in abstract spaces and the Daneill approach. And all written by a master analyst with lots of references for further reading. It's one of my all time favorites and I heartily recommend it.
Folland's Real Analysis is a fine book, but it's much harder and it's really more of a general first year graduate analysis course. On the plus side, it does have many applications, including probability and harmonic analysis. It's definitely worth having, but it's going to take a lot more effort then Taylor. The IDEAL thing to do would be to work through both books simultaneously for a fantastic course in first year graduate analysis.
And please don't torture yourself with Rudin's Real And Complex Analysis. It's
sole purpose seems to be to see how much analysis can be crammed incomprehensibly into a single text. Folland is the same level and is much more accessible.
That should get you started. Good luck!

Reference for von Neumann algebras coming from a group algebra twisted by a 2-cocycle?

You can consult the article

Bédos, Erik
On Følner nets, Szegő's theorem and other eigenvalue distribution theorems.
Exposition. Math. 15 (1997), no. 3, 193--228.

and this recent article:

http://arxiv.org/PS_cache/math/pdf/0605/0605145v2.pdf

Finally, I believe that the construction is first appeared in

Zeller-Meier, G.
Produits croisés d’une C*-algèbre par un groupe d’automorphismes. (French)
J. Math. Pures Appl. (9) 47 1968 101–239

knot theory - What would the slice-ribbon conjecture imply?

I don't know a genuine link to the smooth Poincare conjecture but the link to cobordism for homology spheres is simple. Given a slice disc, construct a branched cover of $D^4$, branched over the slice disc. That gives you a 4-manifold bounding the associated branched cover of the knot in $S^3$. I wouldn't describe it as an approach to determining which homology 3-spheres bound homology 4-balls but it's a natural source of examples, and a linkage. If anything the information seems to flow mostly the other direction. For example, Paolo Lisca's recent paper where he determines precisely which connect-sums of lens spaces bound rational homology balls. As a corollary he deduces the order of 2-bridge knots in the concordance group of knots in $S^3$.

EDIT: Not exactly addressing your question, I think of the slice-ribbon conjecture as a primitive 4-dimensional knotting problem. Given a slice disc you could ask if it's isotopic to a ribbon disc (if the height function on $D^4$ when restricted to the slice disc has only 1-handle and 2-handle attachments, in that order). You can mess up a ribbon disc by taking connect-sums with 2-knots. So modulo connect sums with 2-knots is every slice disc isotopic to a ribbon disc? Perhaps that's too much to ask too, so you can ask the slice-ribbon problem.

2nd edit: As far as I know, the slice-ribbon conjecture has no major consequences. As I describe above, it's more of an ''outer-marker'' type of conjecture. It's a measure of how well we understand knotting of 2-dimensional things in 4-dimensional things.

3rd edit: Here is a type of mild consequence that was pointed out to me recently. In my arXiv preprint on embeddings of 3-manifolds in $S^4$ there's Construction 2.9 which creates embeddings of certain 3-manifolds $M$ in homotopy 4-spheres. The first step is to find a contractible $4$-manifold $W$ that bounds the 3-manifold $M$, then you double $W$ to get a homotopy $S^4$. If the link used in the construction is a ribbon link, the contractible manifold $W$ admits a handle decomposition with one 0-handle, $n$ 1-handles and $n$ 2-handles (for some $n$) and no higher dimensional handles. So the homotopy $S^4$ constructed that contains $M$ is diffeomorphic to $S^4$ provided the corresponding presentation of $pi_1 W$ is trivializable by Andrews-Curtis moves (handle slides for the handle presentation). This argument will appear in the next draft of the paper, which should appear before January.