Tuesday, 31 July 2007

matrices - What is the constant of the Coppersmith-Winograd matrix multiplication algorithm

In your second question, I think you mean "naive matrix multiplication", not "Gaussian elimination".



Henry Cohn et al had a cute paper that relates fast matrix multiply algorithms to certain groups. It doesn't do much for answering your question (unless you want to go and prove the conjectured results =), but it's a fun read.



Also, to back up harrison, I don't think that anyone really believes that there's an $O(n^2)$ algorithm. A fair number of people believe that there is likely to be an algorithm which is $O(n^{2+epsilon})$ for any $epsilon > 0$. An $O(n^2 log n)$ algorithm would fit the bill.



edit: You can get a back-of-the-envelope feeling for a lower bound on the exponent of Coppersmith-Winograd based on the fact that people don't use it, even for n on the order of 10,000; naive matrix multiplication requires $2n^3 + O(n^2)$ flops, and Coppersmith-Winograd requires $Cn^{2.376} + O(n^2)$. Setting the expressions equal and solving for $C$ gives that the two algorithms would have equal performance for n = 10,000 (ignoring memory access patterns, implementation efficiency, and all sorts of other things) if the constant were about 627. In reality, it's likely much larger.

dg.differential geometry - Smooth Dependence of ODEs on Initial Conditions

Dear all,
The following is a theorem known to many, and is essential in elementary differential geometry. However, I have never seen its proof in Spivak or various other differential geometry books.



Let $t_0$ be real, and $x_0 in mathbb{R}^n$ and $a,b>0$. Let $f:[t_0-a,t_0 + a] times overline{B(x_0,b)}rightarrow mathbb{R}^n$ be $C^k$ for $kge 1$.



Then $f$ is Lipschitz continuous, with which it is easy, using the contraction mapping theorem of complete metric spaces, to prove that the ODE:
$dfrac{d}{dt}alpha(t,x)=f(t,alpha(t,x)),quad alpha(t_0,x)=x$



has a continuous solution in an open neighbourhood of $(t_0,x_0)$. In other words, the ODE
$x'(t)=f(t,x(t));x(t_0)=x_0$ has a family of solutions which depends continuously on the initial condition $x_0$.



The theorem that I'd like to prove is that, in fact, if $f$ is $C^k$, then $alpha$ is $C^k$, for any $kge 1$.



I'd like an "elementary" proof that needs no calculus on Banach spaces or any terribly hard theory such as that, but hopefully something elementary, such as the contraction mapping theorem. I currently have an attempt of a proof that looks at perturbations of linear ODEs, but it is incorrect (I think). The proof can be found on page 6 of http://people.maths.ox.ac.uk/hitchin/hitchinnotes/Differentiable_manifolds/Appendix.pdf. I believe that there is a typo in the claim:



"Apply the previous lemma and we get



$mathrm{sup}_{left| tright|leq epsilon}left|lambda(t,x)y-{alpha(t,x+y)+alpha(x)}right|=o(left|yright|).$"



but more importantly, what it should be replaced by is incorrect. What is needed is that $||A-B_y||=o(||y||)$ but I do not see why this is.



Thank you for your time and effort.

gr.group theory - Fibered nots (non-geometric HNN extensions of free groups normally generated by the monodromy)

A fibered knot is a knot $K$ in the $3$-sphere whose complement is a surface bundle over a circle. If $S$ is the fiber, the fundamental group of $S$ is free (of even rank), and the fundamental group of the complement is an HNN extension
$$pi_1(S) to pi_1(S^3-K) to Z$$
where the $Z$ is generated by the meridian of the knot.



Since surgery on $K$ recovers the $3$-sphere, the group $pi_1(S^3-K)$ has the interesting property that it is normally generated by (the conjugacy class of) the meridian.



What I didn't realize until recently is that there are many examples of "non-geometric" automorphisms $phi$ of free groups $F$ for which the associated HNN extension $F to G to Z$ is normally generated by the conjugacy class of the monodromy. One simple example is the case $F = langle a,b,c rangle$ and $phi$ is the automorphism $a to c^{-1}abac, b to bac, cto bc$.



Is there any systematic way of generating such examples? Is there a classification? One reason to be interested is that such examples can be used to construct smooth $4$-manifolds which are topologically $S^4$ but not obviously diffeomorphically $S^4$.



Edit: a link to the construction is http://lamington.wordpress.com/2009/11/09/4-spheres-from-fibered-knots/ (this explains the construction in the case of a fibered knot, but the group-theoretic condition is the only important ingredient).

Sunday, 29 July 2007

fa.functional analysis - rules for operator commutativity?

One obvious but important observation is that, for operators on a $n$-dimensional vector space over a field, if $1 < n < infty$, we have $AB neq BA$ generically. In other words, consider the commutativity locus $mathcal{C}_n$ of all pairs of $n times n$ matrices $A,B$ such that $AB = BA$ as a subset of $mathbb{A}^{n^2}$. This is clearly a Zariski closed set -- i.e., defined by the vanshing of polynomial equations. It is also proper: take e.g.
$A = left[ begin{array}{cc} 1 & 1 \ 0 & 1 end{array} right] oplus 0_{n-2}$ and $B =
left[ begin{array}{cc} 0 & 1 \ 0 & 1 end{array} right] oplus 0_{n-2}$. Since $mathbb{A}^{n^2}$ is an irreducible variety, $mathcal{C}_N$ therefore has dimension less than $N^2$. This implies that over a field like $mathbb{R}$ or $mathbb{C}$ where such things make sense, $mathcal{C}_N$ has measure zero, thus giving a precise meaning to the idea that two matrices, taken at random, will not commute.



One could ask for more information about the subvariety $mathcal{C}_N$: what is its dimension? is it irreducible? and so forth. (Surely someone here knows the answers.)



I would guess it is also true that for a Banach space $E$ (over any locally compact, nondiscrete field $k$, say) of dimension $> 1$, the locus $mathcal{C}_E$ of all commuting pairs of bounded linear operators is meager (in the sense of Baire category) in the space $B(E,E) times B(E,E)$ of all pairs of bounded linear operators on $E$.



Kevin Buzzard has enunciated a principle that without further constraints, the optimal answer to a question "What is a necessary and sufficient condition for $X$ to hold?" is simply "X". This seems quite applicable here: I don't think you'll find a necessary and sufficient condition for two linear operators to commute which is nearly as simple and transparent as the beautiful identity $AB = BA$.



Still, you could ask for useful sufficient conditions. Diagonalizable operators with the same eigenspaces, as mentioned by Jonas Meyer above, is one. Another is that if $A$ and $B$ are both polynomials in the same operator $C$: this shows up for instance in the Jordan decomposition.

Saturday, 28 July 2007

ag.algebraic geometry - Is there a stable algorithm for polynomial division (in several variables)?

Suppose you have a homogeneous ideal $I$ inside the algebra $mathbb{C}[x_1,...,x_d]$ of complex polynomials in $d$-variables. Can one find a basis for $I$, say ${f_1,...,f_k}$, such that every $h in I$ can be written as



$$h = a_1 f_1 + ... + a_k f_k $$



where the coefficients appearing in each summand $a_i f_i$ are not much bigger then the coefficients appearing in $h$?
More specifically, given that ${f_1,...,f_k}$ is a Groebner basis for $I$, can one modify the standard division algorithm so that one gets
$h = a_1 f_1 + ... + a_k f_k$
with controlled terms?



Added 13.11.09 - By controlled I mean that the coefficients of the terms $a_i f_i$ are bounded in a non-exponential manner by the coefficients of $h$. There is no problem with degree of the $a_i$'s.



I will share that I found this possible in some special cases, for example when $d=2$ or when $I$ is generated by monomials, and I am now interested in the general question.



Note: My question begins after a basis has been found, I am not concerned here with the terrible complexity of actually computing a Groebner basis.



Another note (added 12.11.09): The answers and links that I am getting suggest that this problem has not been considered before. So I re-eamphasize my note from above: assume that a Groebner basis, even a universal Groebner basis, has already been found for the ideal. What can be said about the stability of certain variants of the division algorithm now?

Friday, 27 July 2007

at.algebraic topology - Group action, Fixed point set and Orbit Space

First, you might want to identify actions that are not conjugated in $mathrm{Homeo}(M)$. For example, let $mathbb{Z}timesmathbb{Z}$ act on $M$ in the following two ways: the first factor acts by a map $f:Mto M$ and the second acts trivially, or the converse. Then the actions are the same only up to an automorphism of the group.



Second, it is not clear to me what you mean by "the same orbit space". Rational rotations of the circle all have homeomorphic orbit spaces, but of course they are not conjugate in any way.



I guess that even in favorable cases, you need the (conjugacy class of the) stabilizer of each orbit to identify the action.



Last, a remark that is not directly linked to your question, but that I like to advertise: there exist (infinite families) of analytic group actions on analytic manifolds that are topologically but not $C^1$ conjugate.

Thursday, 26 July 2007

computer science - How can one characterize NP^SAT?

Yes, NP^SAT = NP^NP, because SAT is complete for NP. I don't know what else can be said about this class (it's not in the complexity zoo). See the wikipedia oracle page for more details.



By the way, the above "computer" tag is not very relevant, it should rather be "complexity", or "complexity-theory".

Tuesday, 24 July 2007

banach algebras - Is this a correct interpretation of support in coarse geometry?

Edit I have amended the proof to cover the general case following a suggestion of Matthew Daws.



By the definition of $supp(v)$, for any $x$ in $supp(v)^c$ there exists an open set $U(x)subset supp(v)^c$ containing $x$ such that $rho(f)v=0$ for all $fin C_0(U(x)).$ If $g$ has compact support $Ksubset supp(v)^c,$ there is a finite subset $U_1,ldots,U_m$ of ${U(x)}$ covering $K.$ Using a partition of unity, $g=g_1+ldots+g_M$ where $g_iin C_0(U_{k(i)})$. Therefore, $rho(g)v=sum_i rho(g_i)v=0.$ In general, by the lemma below, we can approximate $g$ by a sequence ${g_n}$ of continuous functions with compact support disjoint from $supp(v),$ so $rho(g)v=rho(lim g_n)v=lim rho(g_n)v=0.square$



Lemma Suppose that $Lsubset X$ is compact and $gin C_0(X)$ restricts to zero function on $L.$ Then $g=lim g_n,$ where $g_nin C_0(X)$ has compact support disjoint from $L.$



Proof The function $g_n$ is obtained from $g$ by a smooth cutoff at distance $1/n$ from $L.$ The approximation property follows from the fact that $g$ vanishes on $L$.



More formally, let $h:mathbb{R}to [0,1]$ be a continuous function such that $h(y)=0$ for $yleq 1$, $h(y)=1$ for $ygeq 2.$




___
/
/
/ h(x)
____/
1 2


Since $L$ is compact, the distance function $d_X(cdot,L)$ is well-defined and continuous. Let $L_n$ be the open $1/n$-neighborhood of $L$ in $X$. Set



$$g_n(x)=h(nd_X(x,L))g(x).$$



By construction, $g_n$ vanishes on $L_n$ and coincides with $g$ on $L_{2n}^c$. Its support is compact and is contained in $L_n^c.$ Moreover,



$$ |g-g_n|leq sup_{xin {L}_{2n}} |g(x)|.$$



The right hand side is a non-negative monotone decreasing sequence. Suppose that there exists a sequence of points $x_nin L_{2n}$ such that $g(x_n)$ is bounded away from $0.$ Since $g$ is compactly supported, this sequence has an accumulation point $x.$ Then $xin L$ and so $g(x)=0,$ which is a contradiction. $square$

at.algebraic topology - Vanishing of Euler class

One important case when vanishing of the Euler class does imply triviality of the bundle (and hence existence of nowhere zero section) is for oriented rank 2 bundles over paracompact bases. In fact, Euler class gives one-to-one correspondence between the set of isomorphism classes of such bundles and the second cohomology group [Husemoller's "Fiber bundles" book, 20.2.6].



If rank is $>2$, then a vector bundle is determined by Euler and Pontryagin classes up to finite ambiguity (provided the base is a finite cell complex). In rare cases Euler and Pontryagin determine the bundle completely.



For example, rank 4 bundles over $S^4$ are in one-to-one correspondence with $pi_3(SO(4))congmathbb Z+mathbb Z$ where the latter isomorphism can be chosen so that the bundle $(n,m)$ has Euler class $n$ and first Pontryagin class $2m$. If memory serves me, this can be found in Milnor's original paper on exotic 7-sphere, but there are more recent detailed sources, e.g. see here.

Monday, 23 July 2007

ra.rings and algebras - What does the semiring of ideals of a ring R tell us about R?

This is pretty simple too, but here it goes. I take R to be commutative and have 1.



If S is generated by just one ideal P, then all the ideals of R are of the form P^k. Thus R is local. If P^2 is not all of P then any p in PP^2 generates P, and each P^k is generated by p^k. Hence the only prime ideal is P, and it is exactly the ideal of nilpotents (since these are the intersection of all prime ideals). It follows that some P^k = 0.



If P^2 is all of P then again there is just the one prime ideal P, but now P = P^k = 0, so R is a field.



So either R is a field or there is a nilpotent p in R s.t. all x in R are of the form u*p^k for some unit u and non-negative integer k. (Just consider the biggest k for which x is a multiple of p^k.) Sometimes, but not always (see below), we can identify R with a quotient of the polynomial algebra (R/P)[X] (note that R/P is a field), namely (R/P)[X]/(X^k) where k is the smallest s.t. P^k = 0.



Conversely, any quotient F[X]/(X^k), F a field, has its semiring of ideals generated by (X).

Friday, 20 July 2007

computational complexity - Existence of a pseudo-polynomial time algorithm for a counting problem.

Let T={1,...,n} be a set of tasks. Each task i has associated a non negative processing time p_i and a deadline d_i. A feasible schedule of the tasks consists of a permutation of n elements pi, such that sum_i=1^k p_(pi(i)) <= d_(pi(i)) for all k=1,...n.



Does there exists a pseudo-polynomial time algorithm for computing the total number of feasible schedules?



A pseudo-polynomial time algorithm is an algorithm whose running time is bounded by a polynomial on the size of the input, given that the input is written in unary notation (2=II, 3 =III). (e.g., the size of a number n in unary notation is O(n), and not O(log(n)).



This is an open question from an article published in 2009 at Operations Research Letters.

at.algebraic topology - Obstruction theory for non-simple spaces

@Evans Jenkins: A comparison of the work of Whitehead and Olum is given in



Ellis, G.J. "Homotopy classification the J.H.C. Whitehead way". Exposition. Math. 6 (1988) 97--110.



He writes (and I leave the reader to find the citations):



``In view of the ease with which
Whitehead's methods handle the classifications of Olum and Jajodia,
it is surprising that the papers cite{Olum53} and cite{Jaj80}
(both of which were written after the publication of
cite{W49:CHII}) make respectively no use, and so little use, of
cite{W49:CHII}.



``We note here that B. Schellenberg, who was a student of Olum, has
rediscovered in cite{Sch73} the main classification theorems of
cite{W49:CHII}. The paper cite{Sch73} relies heavily on earlier
work of Olum.''



Whitehead used what he calls "homotopy systems", which we now call "free crossed complexes"; the notion of crossed complex goes back to Blakers in 1948 (Annals of Math), and a full account is in the 2011 EMS Tract Vol 15 Nonabelian algebraic topology: filtered spaces, crossed complexes, cubical homotopy grouopids. The relation between crossed complexes and chain complexes with operators is quite subtle; it was first developed by Whitehead, and in CHII he explains, in our terms, that crossed complexes have better realisation properties that chain complexes with operators. For example, the latter do not model homotopy 2-types.



Section 12.3 of the above Tract is on the homotopy classification of maps, including the non simply connected case, but it may be that your example is out of reach of the "linear" theory of crossed complexes. The homotopy classification of $3$-types requires quadratic information, see books by Baues and also



Ellis, G.J. "Crossed squares and combinatorial homotopy". Math. Z. (214} (1993) 93--110.



So there is sill a lot of work to be done!

mp.mathematical physics - When can we factor out the time dimension?

First of all, my knowledge of both GR and differential geometry is quite weak, so forgive me if the physics here doesn't make much sense.



Let $(M, g)$ be a smooth, connected Lorentzian manifold of dimension $n$. Let $f: mathbb{R}to M$ be a smooth curve such that the pullback of $g$ through $f$ is everywhere negative (where we've chosen an orientation on $mathbb{R}$); we say that $f$ is time-like. Say that we can "factor" $f$ out of $M$ if there exists a manifold $S$ of dimension $n-1$ and an isomorphism $Msimeq Stimes mathbb{R}$ so that the map $mathbb{R}to Msimeq Stimes mathbb{R}to S$ is constant and the map $mathbb{R}to Msimeq Stimes mathbb{R}to mathbb{R}$ is the identity. Intuitively, this factorization exhibits $f$ as "time" in some reference frame, and $S$ as space. My question is:




For which $(M, g)$ can every time-like path be factored out?




Minkowski space seems like an obvious example unless I'm missing something; it seems one can take a tangent vector to $f$ at any point and consider a perpendicular subspace to that vector as $S$. I'd accept as an answer a characterization of all such $(M, g)$ in dimension $4$, or some nice sufficient condition on $M$ for factorization to always work.



If the motivation isn't obvious already, this is supposed to codify the intuition that in my reference frame, I seem to be standing still -- and that the same is true for everyone else, even if they seem to me to be moving. My apologies if I've overloaded terms, or used them incorrectly.




Added: Note that this condition is much stronger than stable causality; indeed, it certainly implies stable causality, as choosing any timelike path $f$ and then considering the given projection to $mathbb{R}$ gives a global time function. However, I am asking for (1) a product structure on $M$ for each path $f$ and (2) in order to formalize the notion that I seem to be standing still (to myself), the projection of $f$ to $S$ must be constant.




Added: I don't think global hyperbolicity suffices either. The theorem of Geroch (it and other splitting theorems are discussed here, for example) does indeed give a decomposition of $M$ as $mathbb{R}times S$. But I don't think this is enough. In particular, I am asking for the following---for every timelike path $f: mathbb{R}to M$, there is a product structure $Msimeq mathbb{R}times S$ such that the projection to $mathbb{R}$ is a section of $f$, and that $f$ is constant upon projection to $S$. This is much stronger than Geroch's splitting theorem, as far as I can tell.




Added: As the accepted answerer rightly points out in the comments to his question, I was wrong to claim that my condition is stronger than global hyperbolicity. They are in fact equivalent.

Thursday, 19 July 2007

nt.number theory - Effective proofs of Siegel's theorem using arithmetic geometry

This is a speculation and perhaps naive. The theorem of Siegel that




There exist only finitely many integral points on a curve of genus $geq 1$ over a number ring $mathcal O_{K, S}$ where $S$ is a finite set of places in a number field $K$




has proofs from arithmetic geometry, for instance by Parshin and Faltings, or by Kim. These proofs are interesting in that they use the modern developments in algebraic geometry and arithmetic to prove a theorem in number theory. But it is dissatisfying that as far as I am aware these proofs do not give an effective bound as opposed to the proofs using Baker's theorem. For instance, Silverman's book feels that the Parshin-Faltings proof is indirect.



But I do not know about the more recent developments and philosophy. I am wondering whether there is any hope that the more sophisticated proofs can be made effective, as it would give the best of both worlds. I hope the experts here can answer this.

ag.algebraic geometry - E_infty spectrum corresponding to Z_p

I would argue that looking for a ring spectrum is not the right thing to do. What you should be looking for is the category of modules over that possibly non-existent ring spectrum, as an infinity-category or just as a triangulated category. If you think about it this way, an obvious answer presents itself.



Begin with the category of HZ-modules, or the derived category of Z, or its infinity-category version. Now take the Bousfield localization with respect to the object Fp (thought of as a complex in degree 0). This is not a smashing localization, so this category is not equivalent to modules over HZp . As a triangulated category, it is compactly generated, but by Fp itself. The sphere is not small. So this category is equivalent to modules over a DGA, the endomorphism DGA of Fp, but it is not commutative. It is more like a DG Hopf algebra, I suspect, so that its homotopy category has a tensor product even though it is not commutative. I have always thought this example needs more investigation, though it might be in Dwyer-Greenlees-Iyengar somewhere. It is a toy version of the K(n)-local stable homotopy category.



Mark

Tuesday, 17 July 2007

lo.logic - What is the history of the Y-combinator?

Turing's 1937 paper (of just one page!) which defines $Theta$, his own fixed point combinator, refers to a 1936 paper by Kleene in which a "function L with a property similar to the essential property of $Theta$" is defined.



References:
A M Turing, The P function in $lambda$-K conversion, Journal of Symbolic Logic Vol 4 No 2 December 1937 p. 164



S C Kleene, $lambda$ definability and recursiveness, Duke Mathematical Journal, Vol 2 1936 p. 346

Monday, 16 July 2007

ag.algebraic geometry - Fourier-Mukai transform - a first example

Indeed, as follows from the comments below, maps between schemes provide examples of Fourier-Mukai transform, most famous example being a similar map with additional twisting by a bundle in $Atimes hat A$ for an Abelian variety $A$.



Anyway, since the restriction $p'_X:Gamma_fto X$ is actually an isomorphism (the inverse is $xmapsto (x, f(x))$) and the composition $p_Ycirc {p'_X}^{-1}: X to Gamma_f to Y$ is exactly $f$, the statement you have written is actually equivalent to $f_* () = f_*()$. Thus there is no hard commutative algebra stuff.

Saturday, 14 July 2007

differential equations - What braking strategy is most fuel-efficient?

You notice a stop-light ahead of you and it is currently red. You can't run the red light, so you will have to brake, but braking wastes energy and you want to be as fuel efficient as possible. What braking strategy maximizes efficiency?



Let's set down some notation and move slowly toward a well-defined question. Suppose you are currently a distance $d$ from the stop-light, and suppose that the stop-light is on a timer whereby it switches from red to green after $T$ seconds. You know the value of $T$, but you don't know how far in the cycle the stop-light is right now -- perhaps it will turn green in 1 second or perhaps in $T$ seconds. So if $t$ is the amount of time until it actually turns green, then $t$ is a random variable uniformly distributed on $[0,T]$.



Your initial speed is $v$, so that if you don't slow down you'll be at the light in $frac{d}{v}$ seconds. If $t<frac{d}{v}$ then ``you win" by not slowing down, because the light will turn green before you get to it and you will have lost no energy to heat. So if $Tleqfrac{d}{v}$ then clearly the best strategy is not to slow down. Thus we may suppose $T>frac{d}{v}$. We assume no friction.



I'm looking for a strategy for applying the brake minimally, not knowing the status of the stop-light's cycle. Perhaps we apply the brakes uniformly to end up stopped at the light, or perhaps we do not apply the brakes at all until we are almost to the stop-light, or perhaps we apply the brakes at the very beginning and coast at that reduced speed until we get very close to the light. What strategy minimizes the expected brake usage?



More precisely, I'm looking for a non-increasing differentiable function (for the car's velocity in terms of its distance to the stop-light) $$fcolon[0,d]to{mathbb R}_{geq 0}$$ such that $f(d)=v$, $f(0)=0$, and such that if you solve the differential equation to find velocity in terms of time, then the expected value of that velocity at time $t$ is maximized.

gr.group theory - References on functorially-defined subgroups

I'm interested in results about functorially-defined subgroups (in a loose sense), especially in the non-abelian case, and would like to know about references I may have missed.



The question, it seems, comes up in its simplest form when noticing a number of common subgroups (the center, commutator subgroup, Frattini subgroup, etc) are characteristic. The characteristicity can be justified by the fact that the object mappings that define of those subgroups give rise to subfunctors of the identity functor, on the core category of Grp.



Hence I'm interested in functors F in Grp (or a carefully chosen sub-category) such that



∀ A F(A) ⊆ A and ∀ A,B ∀ f ∈ hom(A, B), f(F(A)) ⊆ F(B)



Does that ring a bell ?



The topic was mentioned a couple of months ago on Mathoverflow, and can be traced back to (at least) 1945, where Saunders MacLane explains it in some detail in the third chapter of A General Theory of Natural Equivalences.



In between, it seems that those functors have been baptised radicals, pre-radicals or subgroup functorials, and studied mostly in the framework of ring theory, notably by A. Kurosh. Among a number of not-so-recent (and therefore quite-hard-to-find) papers mostly dealing with rings, semigroups, or abelian groups, I came across a single reference mentioning the non-abelian case, by B.I. Plotkin : Radicals in groups, operations on classes of groups, and radical classes. Connections seem have been made with closure operators¹, but do not focus much on Grp.



  • Do you have ideas of connections from those functors to other parts of algebra or category theory, other than (pre-)radicals ?

  • Do you have some pointers to material I may have missed, specially if they mention non-abelian groups ?

¹: Categorical structure of closure operators with applications to topology
By N. Dikranjan, Walter Tholen, p.51

ct.category theory - `Topos' with alternate subobject lattice?

Different types of categories lead to different types of internal logics. Here is a very short list:



 Regular Logic            Regular Category
Coherent Logic Coherent Category
Geometric Logic Infinitary Coherent Category/Geometric Category
First-Order Logic Heyting Category
Dependent Type Theory Locally Cartesian Closed Category
Higher-Order Logic Elementary Topos


Some of the names are somewhat standard by now, but be warned that Johnsone (Sketches of an Elephant), Freyd & Scedrov (Categories, Allegories), the nLab, and many others all use slightly different terminology. I think Johnstone's presentation in the Elephant is very nice, though you can certainly find friendlier and more localized accounts elsewhere.

Thursday, 12 July 2007

big list - Undergraduate Level Math Books

I would also recommend the book entitled Analysis on Manifolds by James Munkres. I think that this is a good undergraduate textbook in mathematics for any student wishing to pursue multivariable calculus in greater depth. My only complaint is that Munkres often chooses to include details which can be seen easily after a little bit of thought. Perhaps this can be viewed as an effort to show the student how to "properly do analysis": doing analysis, just like doing any other branch of mathematics, requires you to carefully apply definitions and theorems, and it is important for the student to appreciate this early in his/her mathematical learning.



That said, the book is an excellent text overall for "advanced calculus". The student will need to be familiar with single variable analysis and perhaps some linear algebra. (Even a rudimentary knowledge of linear algebra will do since Munkres develops most of the necessary theory from scratch.)



Roughly speaking, the book splits into two parts. The first part covers most of the results students see when doing multivariable calculus that are stated "without proof" in their texts. For example, "the equality of the mixed partials", "double integrals can be done in any order", "a bounded function is Riemann integral if and only if it is continuous almost everywhere", "the change of variables theorem" etc., are (very) imprecise forms of some of the results Munkres establishes.



In the second part of the book, manifolds and their theory are introduced. Thus, for example, a rudimentary introduction to tensors is given, and this is supplemented by the basic theory of differential forms, the De Rham groups (of the punctured plane), Stokes' theorem etc.



I think that the exposition could be tightened: if you actually pick up the book and really make an effort to read it, it is quite possible to finish the first half of the book in the space of a week (that is, approximately 200 pages in a week) simply because certain topics are explained in more detail (at least in my opinion) than necessary. (One example is Munkres' proof of the linearity, monotonicity, additivity etc. of the Riemann integral. This is proved in three contexts separately: the case of the integral over a rectangle, that over a bounded set, and that of improper integrals, when essentially the proofs can be left as relatively easy exercises in some cases.)



As the above comments suggest, I think that this is an excellent book for undergraduate students, but perhaps less so for graduate students. (Spivak's Calculus on Manifolds is good for both undergraduate and graduate students, in my opinion, but some people may suggest that it is too hard for undergraduates.) And after reading this book, you should have more than enough preparation to read more advanced texts such as William Boothby's An Introduction to Differentiable Manifolds and Riemannian Geometry.

Wednesday, 11 July 2007

ca.analysis and odes - L^p Idempotent multipliers in 2 dimensions

This question is suggested by that about L^p multipliers (and the answer by Michael Lacey in particular).
Let E be a measurable set in the plane and XiE its characteristic function. We say E is an Lp multiplier set iff the translation invariant operator F(Tf) = XiE F(f) (F = Fourier Transform), extends to a bounded operator on L^p (it is a-priori defined on the Schwartz Class or L^2cap L^p).
For example in dimension 1 every interval is an L^p multiplier for every p except 1 and infty.
The situation strongly differs in the 2-dimensional case, as highlighted by the solution of the ball multiplier conjecture by C. Fefferman: the ball B is a strict L^2 multiplier (not L^p for pneq 2) and the same is true for every set with an appropriate curvature.
I was wondering whether more generally something can be said about the interval of p for which E is an L^p multiplier, in terms of the "geometry" of E, in dimension 2 or higher.

fa.functional analysis - Group homomorphisms and maps between function spaces

Inspired by Victor's idea:



Setup: Let $theta:Grightarrow H$ be a continuous dense range map between locally compact (Hausdorff) spaces. Let $G'=theta(G)$ with the subspace topology from H. Let $pi:C^b(H) rightarrow C^b(G)$ be the pull-back of $theta$.



Lemma: The collection of sets of the form $f^{-1}((1/2,infty))$, where $f$ is a continuous map $Grightarrow [0,1]$ vanishing at infinity, is a base for the topology on $G$.



Proof: Let $G_infty$ be the one-point compactification, let $sin G$, and let $Usubseteq G$ be open with compact closure (which is okay, as $G$ is locally compact) with $sin U$. By Urysohn, there exists a continuous $f:G_inftyrightarrow [0,1]$ with $f(s)=1$ and $f|_{G_inftysetminus U} equiv 0$. Then $f|_G$ vanishes at infinity, and $sin f^{-1}((1/2,infty)) subseteq U$. Clearly every open set can now be written as a union of these special open sets. QED.



Claim: Suppose that $pi$ is surjective (so $pi$ is infact a bijection). Let $phi:Grightarrow G'$ be $theta$, considered as having codomain $G'$. Then $phi$ is a homeomorphism, and so $theta(G)$ is open in $H$.



Proof: We show that $phi$ is open. Let $fin C^b_{mathbb R}(G)$, and let $g=pi^{-1}(f)in C^b(H)$, so that $g(theta(s)) = f(s)$ for $sin G$. Let $U=f^{-1}((1/2,infty))$ so $theta(U) = { tin H : exists s, phi(s)=t, f(s)>1/2 }$ $= { tin G' : f(phi^{-1}(s))>1/2}$ $= { tin G' : g(t)>1/2 } $ $= G' cap g^{-1}((1/2,infty))$. Thus $phi(U)$ is open, as $G'$ has the subspace topology. By the lemma, this does show that $phi$ is open. Then $G'$ is itself locally compact, and so as $G'$ is dense, it must be open in $H$. QED.



Claim: If additionally $G$ and $H$ are groups and $theta$ a homomorphism, then $theta$ is a surjection.



Proof: An open subgroup is closed. QED.



If this is all correct, then I'd be a little surprised if this wasn't known (say, the stuff not about groups). Any ideas???

Tuesday, 10 July 2007

teaching - Category theory sans (much) motivation?

Maybe you could construct an explicit exact sequence which describes something irl about which your friend has already an intuition?



Start with a tiny category (1,2,3 elements) tiny cat



which is theoretically simple, and by a sequence of algebra-respecting surjections how a complex model of the real-world thing can be broken down (at different levels) into smaller bits with an easier logic to them. (Alternatively you could branch out in different directions and show how chain 1 captures this aspect of the model, whilst chain 2 captures that aspect of the model.) I don't have a ready example for that right now but I'll edit this answer if I think of one.



You could also spend time talking about "congruence"—just like it would be idiotic—pedantic beyond the worst human pedant—to treat two different hand-writings of the letter a as having different meanings, we want to be able to use the word "the same" in mathematics as we use it in normal language—like, "OK, not the same same, but, you know, basically the same". (And this needs some precise definition in order to give us, in mathematics, the freedom-of-movement we get gratis in eg English.) I like the familiar toddlers' play blocks as a metaphor for "The same like how?".



blocks



I'm not sure if this applies to your friend, but the simplest functor I can think of is between $(o,e,mathbb{Z}_+) longleftrightarrow (pos,neg,mathbb{R}_{times})$. Anyone who remembers grade-school arithmetic can follow the technical aspects of that relationship. (And you cover "the arrows changing along with the objects"—the relationship wouldn't stay the same if I substituted positives for evens without changing + to ×—and I think this is intuitively clear to anyone whose brain has been sufficiently jogged.)




I'm not sure if that captures what took you out of algebraic doldrums, but that's how I would explain category without busting out a Rube Goldberg of definitions first.

Monday, 9 July 2007

nt.number theory - Global fields: What exactly is the analogy between number fields and function fields?

Sure, here's a overview.



Suppose you have a ring R over a field k, then, by the magic of algebraic geometry, you can think about it in a geometric way. You do this by defining points as epimorphisms R to k and finding out that a lot of geometric intuition plays out nicely.



Now if you start with a field, the above procedure gives you just a single point, so it's more interesting to find ring inside it — people usually take the ring of integers inside the field, which is uniquely defined.



Now the amazing thing is that you can perform this exact procedure either on number fields like Q or on function fields like F_p(t) and it gives you a very similar geometric structure.



For example, you can talk about completion of your ring by some maximal ideal and this corresponds to considering infinitesimal geometry around a single point. For number fields that would be something like Q_p while for function fields that would be F_p[[t]]. Not if you think how Q_p is basically F_p formally extended by p you notice the techniques wors the same in both cases.



E.g. the theory of ramification is basically the theory of extending either F_p[[t]] or Q_p. (There are important differences though — F_p[[t]] can be extended with F_{p^2}[[t]])

ag.algebraic geometry - Line bundles: from transition functions to divisors

Recently I was thinking about how local systems are the same thing as vector bundles with flat connection, and how representations of the fundamental group gave rise to vector bundles. This got me thinking about how we get a handle on line bundles in general, and made me suspect that I don't understand them as well as I should, so I thought I'd ask a novice question about them. In brief: one has two different ways of regarding line bundles on a smooth complex algebraic variety, as a set of transition functions and as an equivalence class of Weil divisors, and I want to see how the two relate.



Let's break it down and be very explicit: $E$ is an elliptic curve over $mathbb{C}$ with (topological) fundamental group generated by $a, b$. I've chosen $E$ because I know all about its Picard group. A one-dimensional local system on $E$ corresponds to an assignation of nonzero complex numbers $lambda, mu$ to $a, b$, and by tensoring this setup with $mathcal{O}$ I get the sheaf of sections of a certain line bundle, whose transition functions in an appropriate set of trivialisations should be $lambda$ and $mu$. I've convinced myself that different choices of $lambda$ and $mu$ give me non-isomorphic bundles. Now, if I fix a distinguished point $P_0$ of $E$, choosing $d in mathbb{Z}$ and $P in E$ is the same thing as choosing an isomorphism class of line bundles on $E$, whose associated divisor will be $P + (d-1)P_0$.



So how are $lambda$, $mu$ and $P, d$ related? Is there a nice formula? What about for higher genus curves? Am I just confused?

ds.dynamical systems - What is the definition of ideal boundary?

There are infinitely (uncountably:-) many definitions of the ideal boundary.
So you have to specify which paper you are reading:-)



See, for example M. Brelot, On topologies and boundaries in potential theory
and Constantinescu, Cornea, Ideale Ränder Riemannscher Flächen.



The simplest example of an ideal boundary is one point compification.
But depending on context, one usually has a space of functions, and one wants
to add ideal bundary points so that the functions of your space have limits.
(Examples: Prime ends, Martin boundary, etc.)

Sunday, 8 July 2007

st.statistics - When do binomial distributions occur?

You are asking, I think, when a Central Limit Theorem holds. The simplest form of the CLT is that the binomial distributions Binomial(n,p), suitably rescaled, converge to a normal distribution as n goes to infinity. (This binomial case is usually not called the CLT, but goes under the name of the de Moivre-Laplace theorem.)



Now, a Binomial(n,p) random variable is the sum of n Bernoulli(p) random variables. The usual form of the CLT states that if $S_n = X_1 + ... + X_n$, where the $X_i$ are independent and identically distributed with mean μ and standard deviation σ, then $(S_n - mu n)/(sigma sqrt{n})$ converges in distribution to the standard normal as n → ∞.



If the $X_i$ are in fact dependent, see the link provided by Ori Gurel-Gurevich above.



If the $X_i$ are independent but not identically distributed, then there are two standard conditions for proving that the rescaled distribution of $S_n = X_1 + ... + X_n$ converges to the standard normal: Lindeberg's condition and Lyapunov's condition. Both are a bit difficult to understand when you first look at them. But the basic idea behind both of them is that if no one of the summands $X_i$ is too large (in variance) compared to the others, then the normal distribution still appears.

computational complexity - Largest subspace that doesn't intersect a given set

The problem is NP hard. Here's a reduction to it from 4-colorability. Given a graph with vertex set $G$ [not $V$ because that's supposed to be a vector space] and edge set $E$, form a vector space $V$ over $mathbb{Z}/2$ having $G$ as a basis. Identify each edge $e$ with the vector that is the difference of the two endpoints of $e$, and let $S$ be the set of these edges-qua-vectors. [I know that "difference" is the same as "sum" here, but it helps to think of the edges as differences.] Then each of the following statements is easily equivalent to the next, for any fixed natural number $t$. [In the end, I'll only need the case $t=2$.]



(1) $V$ has a subspace of codimension at most $t$ that misses $S$.



(2) There are $t$ linear functionals $f:Vtomathbb{Z}/2$ such that each edge $e$ is sent to 1 by at least one of these functionals.



(3) There are $t$ linear functionals $f:Vtomathbb{Z}/2$ such that, for each edge $e$, at least one of these functionals takes different values at the two endpoints of $e$.



(4) There are $t$ functions $g:Gtomathbb{Z}/2$ such that, for each edge $e$, at least one of these functions takes different values at the two endpoints of $e$.



(5) There is a function $h$ from $G$ to $(mathbb{Z}/2)^t$ taking different values at the two ends of each edge.



(6) The graph $(G,E)$ is $2^t$-colorable.



In particular, $V$ has a codimension-2 subspace missing $S$ if and only if $G$ is 4-colorable. Since 4-colorability is known to be an NP-complete problem, the vector subspace problem is also NP-hard.



I believe the "correct" generality for this idea is what's called the critical problem for matroids. What I've presented is the special case of graphic matroids.

formal groups - Extending methods from Lubin-Tate theory

The first lemma in Lubin-Tate theory says the following:




Let $K$ be a local field, $A$ its ring
of integers, and $fin A[[T]]$ be such
that $f(0) = 0$, $f'(0)$ is a
uniformizer, and $f$ induces Frobenius
over the residue field. Then there
exists a unique formal group law
$F_f(X,Y)in A[[X,Y]]$ that makes $f$
into a formal $A$-endomorphism.




If you go over the details of the lemma, you can (I think) generalize it as follows:




If $R$ is any ring, $fin R[[T]]$ such
that $f(0) = 0$ and $f'(0)in R^times$
(Edit: $u=f'(0)$ then $u^n - uin R^times$ for all $n$), then there exists a unique
formal group law $F_f(X,Y)in R[[X,Y]]$ that makes $f$ into a formal
$R$-endomorphism.




The business about uniformizers and Frobenius in the Lubin-Tate lemma is just to ensure that everything converges on the maximal ideal of the ring of integers in the separable closure of $K$, so that you get an actual group.



So this is pretty cool---it says that you can take something purely analytic, $f$, and magically give it an algebraic structure. Specifically, the roots of the iterates $f^{(n)} = fcirccdotscirc f$ become a torsion $A$-module.



If the existence of $F_f$ generalizes like I think it does, a natural question is where does $F_f$ converge? I want to be able to answer the question for specific $f$, a simple example would be the following: if $R=mathbb{C}$ and $f(z) = uz + z^2$, then what can you say about the convergence of $F_f$?



Edit: Okay, $mathbb{C}$ was a bad choice, but suppose $R$ is a ring complete with respect to some $mathfrak{a}$-adic topology. Would there be a reason not to study this case? Maybe the question I should be asking is, for what other $R$ and $f$ do people study these formal groups $F_f$?

ag.algebraic geometry - Reference for explicit calculation of blowups (of ideals) and strict transforms

I think, you'd like to see explicit equations and if possible, a singularity completely solved by blowups. One can take a look at such thinks in Lectures on resolution of singularities by Janos Kollar (http://press.princeton.edu/titles/8449.html). The book starts with more than ten different methods of how to solve singularities on curves and then continues on resolution of singularities on surfaces. There you will see specific examples and explicit equations.

soft question - Why is it so difficult to write complete (computer verifiable) proofs?

The problem of putting an existing mathematical proof through a theorem prover ("formalising a proof") breaks down into 3 inter-dependent stages (with an element of recursion between the stages). With the current state of the art, all three of these stages are agonising. This gets more difficult the larger the proof is.



The first stage is to re-express the proof in a sufficiently detailed, rigorous and coherent symbolic form (or "formalisable" form). Traditional mathematical proofs often switch between different underlying formalisms, and often without any mention that this is happening. Also, sometimes pictorial arguments may be used without any explicit symbolic justification. And there will typically be fairly big, unjustified steps (e.g. "it obviously follows that ...") that may be obvious to the expert in the field, but not immediately obvious to someone fairly new to the subject. All of this needs to be re-expressed. This stage is fundamentally difficult and software cannot really help much. I expect that over time this will become a little easier as people become more experienced. At the moment there are very few people in the world capable of doing this stage effectively for large proofs (perhaps just John Harrison, Tom Hales and Georges Gonthier).



The second stage is to fill in the gaps in the theorem prover's library for theory referenced in the formalisable proof. This involves giving definitions and proving properties in the theorem prover. Ideally the theory referenced will all fit together in a way that helps formalise the proof, and sometimes it will be necessary to come up with alternative formalisms of existing parts of the theorem prover's library. This is a very skilled job, but this stage will eventually become easier as bigger and better library support is built up for the theorem prover being used.



The third stage is to actually translate the formalisable proof into a script accepted by the theorem prover. Currently, this is also a very difficult stage. It will typically take several months to become adept at controlling a theorem prover, and even then some of the steps in the formalisable proof may be agonisingly difficult to achieve. A page of formalisable proof may take weeks to actually formalise. This stage, in my opinion, should be quick and easy for mathematicians, but it will take a small revolution in theorem prover usability to bring this about. I am currently working on this.

order theory - Is there a "universal LYM inequality?"

This question is based on a blog post of Qiaochu Yuan.



Let P be a locally finite* graded poset with a minimal element, and w be a weight function on the elements of P. Suppose that the total weight of the elements of rank k is bounded by 1. Then is the total weight of any antichain bounded by 1, or some constant c (independent of P or w?) The answer, of course, is no, and it's not hard to construct a counterexample. So what are the minimal conditions on P and/or w needed for such a result?



Note that this should specialize to several well-known theorems. Taking the poset to be a Boolean lattice and w to be 1/(n choose k), we obtain the LYM inequality, hence the question title. Taking the poset to be the set of finite-length binary words with X leq Y if X is a prefix of Y, and w to be 1/2^k, we get back Kraft's inequality. And finally, for arbitrary P and setting w to be the constant function 1, we get back (half of a special case of) Dilworth's theorem.



A secondary question: assuming such a result exists, is there a probabilistic proof of it, similar to the probabilistic proofs of Kraft and LYM?



Edit 4: Most of the counterexamples I've constructed thus far have had trees as the underlying poset (i.e., if X leq Z and Y leq Z, then either X leq Y or Y leq X). This subcase seems to simplify the analysis somewhat, so it might be worth considering only trees.



In fact, here's a toy problem which itself seems rather difficult: Can we characterize the weight functions on the infinite rooted binary tree, with the weight of each graded part equal to 1, that satisfy the strong property that the weight of any antichain is at most 1?



*Edit: Actually we want something somewhat stronger than local finiteness, namely that every element is covered by finitely many elements, so that there are are only finitely many elements of any given rank.



Edit^2: Of course we also want the weight function to be nonnegative, or else scary bad things can start happening.



The obvious restriction on the weight function requires it to be dependent only on the rank; interestingly, this is neither necessary nor sufficient for the strong form of the conjecture (i.e. the maximal weight of any antichain leq the maximal weight of all the elements of rank k) to hold. (Counterexamples available upon request.) I'm still searching for a counterexample in this situation to the weak form of the conjecture (Edit^3: Counterexample found.), where every rank has bounded total weight but there are arbitrarily heavy antichains.

Saturday, 7 July 2007

fa.functional analysis - Are proper linear subspaces of Banach spaces always meager?

I am afraid that Konstantin's accepted answer is seriously flawed.



In fact, what seems to be proved in his answer is that $ker f$ is of second category, whenever $f$ is a discontinuous linear functional on a Banach space $X$. This assertion has been known as Wilansky-Klee conjecture
and has been disproved by Arias de Reyna under Martin's axiom (MA).
He has proved that, under (MA), in any separable Banach space there exists a discontinuous linear functional $f$ such that $ker f$ is of first category.
There have been some subsequent generalizations, see Kakol et al.



So, where is the gap in the above proof?



It is implicitly assumed that $ker f = bigcup A_i$. Then $f$ is bounded on $B_i=A_i+[-i,i]z$. But in reality, we have only $ker f subset bigcup A_i$ and we cannot conclude that $f$ is bounded on $B_i$.



And finally, what is the answer to the OP's question?



It should not be surprising (remember the conjecture of Klee and Wilansky) that the answer is:
in every infinite dimensional Banach space $X$ there exists a discontinuous linear form $f$ such that $ker f$ is of second category.



Indeed, let $(e_gamma)_{gamma in Gamma}$ be a normalized Hamel basis
of $X$.
Let us split $Gamma$ into countably many pairwise disjoint sets $Gamma =bigcup_{n=1}^infty Gamma_n$, each of them infinite. We put $X_n=span{e_gamma: gamma in bigcup_{i=1}^n Gamma_i}$. It is clear (from the definition of Hamel basis) that $X=bigcup X_n$. Therefore there exists $n$ such that $X_n$ is of second category. Finally, we define $f(e_gamma)=0$ for every $gamma in bigcup_{i=1}^nGamma_i$ and $f(e_{gamma_k})=k$ for some sequence $(gamma_k) subset Gamma_{n+1}$. We extend $f$ to be a linear functional on $X$. It is clearly unbounded, $fneq 0$, and $X_n subset ker f$. Hence $ker fneq X$ is dense in $X$ and of second category in $X$.

Thursday, 5 July 2007

ca.analysis and odes - How did Gauss discover the invariant density for the Gauss map?

Here is a heuristic.



Observe that $f$ is decreasing on any interval of the form $I_n:=(1/(n+1),1/n)$. If $xin I_n$ and $f(x)=a$, then $x=frac{1}{a+n}$, and so $f^{-1}(a,1)$ is the union of the intervals $(1/(n+1),1/(n+a))$. Supposing there were an $f$-invariant measure $mu=gdx$, you can see that



$displaystyle{sum_{n=1}^infty int_{1/n+1}^{1/n+a}g(x)dx=int_a^1g(x)dx}$.



Supposing that $g$ is continuous, take the derivative of both sides:



(**) $displaystyle{sum_{n=1}^infty gleft(1/(n+a)right)/(n+a)^2=g(a)}$.



Approximating the sum by an integral, we get



$displaystyle{g(a)approxint_1^infty gleft(frac{1}{x+a}right)frac{1}{(x+a)^2}dx}$.



Supposing that $g$ is never too big or too small, this gives



$g(a)approx frac{C}{1+a}$.



One can then plug this kind of function into (**) to see that such a function works for any C. Then just pick C to normalize.



Probably someone from the era of Gauss (especially with his acuity at mathematics) did not need to do anything past (**) since people back then seem like magicians when it comes to expressions with infinite sums.

Wednesday, 4 July 2007

co.combinatorics - Help with a double sum, please

Let's define
$$
beta_n doteq sum_{ile (n-1)/2 } binom{n-(i+1)}{i} (-1)^i frac{1}{ (2i+1) 2^{2i+1} }.
$$
The following problem is equivalent to proving that $S=0$:
prove that the sequence $beta_n$ satisfies the recursion
$$
beta_{n+1} = frac{2n+1}{2n+2} beta_n +frac{1}{(n+1) 2^{n+1}}.
$$
Similar with $S=0$, numerical computations suggest that this statement is true. Unfortunately, I didn't see a straightforward way to prove it.



Below is one way to think about the problem, which led to the above reformulation.



The connection between the above problem and $S=0$.



Using the notation developed in the previous answer, let's define
$$
F(m,n) = sum_{k=0}^m (-1)^k binom{m}{k} binom{2(n+k)}{n+k} frac{1}{2^{2(n+k)}} sum_{l=1}^{k+n}
frac{2^l}{l binom{2l}{l} },
$$
and
$$
f(n)= F(0,n)= binom{2n}{n} frac{1}{2^{2n}}
sum_{l=1}^n frac{2^l}{l binom{2l}{l} }.
$$
The statement $S=0$ is the same as $F(m,m)= 0$. Note that $F$ satisfies
$$
F(m,n) = frac{1}{2} F(m-1,n) - frac{1}{2}F(m-1,n+1) ~~~~~~text{(r1)}
$$
Define the difference operator $D(x_1,x_2) = (x_1 - x_2)/2.$ (r1) in terms of $D$
is
$$
F(m,n) = D( F(m-1,n), F(m-1,n+1) ).
$$
Define $D^k$ by iterating $D$:
$$
D^n(x_1,x_2,x_3,ldots,x_{n+1}) = D( D^{n-1}(x_1,x_2,x_3,ldots,x_{n}), D^{n-1}(x_2,x_3,ldots,x_{n+1} ))
$$
Iterating (r1) gives



$$
F(m,n) = D^m( f(n),f(n+1),f(n+2), f(n+3),cdots,f(n+m)).
$$



In particular:
$$
F(m,m) = D^m( f(m),f(m+1),f(m+2), f(m+3),cdots,f(m+m)).
$$



Define
${mathcal D}:{mathbb R}^inftyrightarrow {mathbb R}^infty$ as follows:
the $i^{th}$ component of ${mathcal D}(x_{1}^infty)$ is
$$D^n(x_n,x_{n+1},x_{n+2},ldots,x_{2n}).$$



We can restate our original problem as follows:
show that $(f(1),f(2),f(3),...,f(n),...)$ is in the kernel
of ${mathcal D}$.



Because we are looking for a zero of this operator,
the $1/2$ in the definition of $D$ is not important; thus let us assume that $D(x_1,x_2)$ is simply
$x_1 -x_2$.



Note that
$D^{n}(f(n),f(n+1),...,f(2n)) =0$
is the same as
$$
D^{n-1}(f(n),f(n+1),f(n+2),...,f(2n-1)) = D^{n-1}(f(n+1),f(n+2),f(n+3),...,f(2n)).
$$
A numerical computation reveals that these discrete derivatives equal $frac{1}{(2n-1)2^{2n-1}}$.
One can go back from these values
to an element
of the kernel of
${mathcal D}$
by inverting each $D$ in the above display.
A bit of computation in this direction yields
the vector $beta$ in the first display.
By its construction $beta$ is in the kernel of ${mathcal D}$.
Thus if one can prove that $f$ equals $beta$ then we are done.



Finally, using its definition, we see that $f$ satisfies:
$$
f(n+1) = frac{2n+1}{2n+2} f(n) + frac{1}{(n+1)2^{n+1}}, ~~~ f(1) = 1/2.
$$
These relations determine $f$ and thus we can take them as $f$'s definition.
Thus to verify $f=beta$ it is enough to show that $beta$ satisfies this recursion.

Tuesday, 3 July 2007

dg.differential geometry - Where does the generic triangle live?

The generic triangle lives in a subset of this function space $Axioms^{Languages}$.



What do I mean? First, let's us what is generic addition? Immediately, you would ask me, addition on which number system? The natural numbers, integers or what? Properly then, one can only say that for each (semi)ring $R$, addition is specified as some subset of $R^{Rtimes R}$.



Now I invoke this duality principle: Operations in number theory are analogous to objects in geometry. Objects in number theory are analogous to operations in geometry.



One of the reasons why this question by Six Winged Seraph is so difficult (and so interesting) is that we should think of the object "triangle" in geometry as analogous to the operation "addition" in number theory. We should not think of the "triangle" as analogous to the number "$n$". It is easy to say where the generic number "$n$" lives in: namely the set of natural numbers ${mathbb{N}}$! (or whatever number system you might be considering) This is an easy question just as where does the generic rotations, dilations and reflections live in: namely the Lie group $Isom({mathbb{R}}^2)$? (or ${mathbb{H}}^2$ or ${mathbb{S}}^2$ depending on which constant curvature space you are considering.)



The "triangle" question is hard because what you can pin down about a generic triangle is not what it is, but what you can do with it. That is, axioms. Using the duality principle again, we pin down what addition is by the axioms, not just axioms for addition, but also how multiplication interacts with it. Are you interested in statements like $23+34=57$, $n+n=2n$ etc? Only to the extent that these statements form part of the completed infinity of theorems from which can be generated by the axioms.



In a similar way, for each constant curvature plane, axioms that govern reflection, axioms that provide congruence criteria, Pappus' proof is generated from these axioms.



As a final refinement, one might also consider triangles in other non-constant curvature spaces. Just as addition can be considered for vector spaces or groups, not just rings. In this case, the full answer is that for any language in which triangles can be talked about, there is a corresponding axiomatization of what can be done with triangles.



Eg, the Pappus proof is for the first-order axiomatization of (non)-Euclidean geometry. There are different proofs for the plane as a Riemannian manifold (via integration) etc. For each of these axiomatizations, we have a different notion of triangle.

Monday, 2 July 2007

ct.category theory - Does this concept have a name, and what are some of its applications?

One reasonable notion of “smallest” here could be “initial”?



So for an object $W$ of $mathbf{D}$, we would look at the iso-comma category $(F downarrow_{cong} W)$, where an object is an object $X in mathbf{C}$ together with an isomorphism $i_X colon F(X) cong W$, and a map $f: (X,i_X) to (Y,i_Y)$ is a map $f : X to Y$ with $i_Y cdot F(f) = i_X$. Then we could define a “minimal $mathbf{C}$-object generating $W$” as an initial object of $(F downarrow_{cong} W)$. (Or possibly weakly initial?)



Idempotent functors of the kind you're describing often fall into one of two classes: reflections or co-reflections. Reflections are more usual: they're functors that come from an adjuntion $mathbf{C} leftrightarrow mathbf{D}$ where the left adjoint goes from $mathbf{C}$ to $mathbf{D}$, the free way to $mathbf{D}$-ify a $mathbf{C}$-object. The abelianisation of a group, the field of fractions of a ring, the Stone-Cech compactification of a space, sheafification of a presheaf, are all examples of this. The unit of the adjunction gives a natural map $X rightarrow F(X)$.



I can't think of many examples of reflections where $(F downarrow_{cong} W)$ will have an initial object for all (or even most) $W in mathbf{D}$. In the “field of fractions” case, for instance, $mathbb{Z}$ is an initial object in $(mathit{Frac} downarrow_cong mathbb{Q})$, but fields of fractions $k(x)$ will have no minimal generating ring. (High-falutin' explanation: $(F downarrow_{cong} W)$ has all connected colimits that $mathbf{C}$ does, but not other limits/colimits in general.)



What about when $F$ (let's call it $G$ now) is a co-reflection, i.e. comes from a right adjoint to the inclusion of $mathbf{D}$? This situation typically looks a little different: the “group core” of invertible elements in a monoid, for instance; in this case the natural map goes the other way, $G(X) to X$.



In this case, there'll always be an initial element of $(G downarrow_{cong} W)$: just $W$ itself! (This is dual to how in the reflection case, W is always a “maximal generating object” for itself, i.e. a terminal object of $(F downarrow_{cong} W)$.) On the other hand, here perhaps a terminal object is a better sense of “minimal” (“maximally quotiented”, or something): taking the sheaf of germs of a bundle is a co-reflection where this might be an interestingly non-trivial question?



Some examples, of course, aren't quite either reflections or co-reflection, like “algebraic closure”, which is nearly a reflection but not quite, because of the automorphisms. This case will look, I suspect, similar to the reflection case…

terminology - The word "torsion" and its connection to geometry and homology

In an $R$-module $M$, an element $m in M$ is said to be torsion if $am = 0$ for some $a in R$ with $a neq 0$.



Also, for a non-orientable (closed) surface such as the projective plane or the Klein bottle, there is a $mathbb Z/2$ term in the first homology. This part is said to detect the "twisting" in the surface.



So this leads to the plausible notion that the origin of the word "torsion" in algebra is related to this "torsion" or "twisting" from topology.



Unfortunately the difficulty is that this is not exactly true. For example, the Möbius band is surely a twisted object. But it deformation retracts to the circle, and therefore its homology is very normal.



I hope somebody can shed more light on this terminology.

ac.commutative algebra - are deformations of torsion modules always torsion?

[I'm going to work over k[h] as the base instead; I don't think anything changes, but if I'm wrong you should let me know.]



Consider the case M = k[s,t,h]/(st-h^2). Setting h=0 yields M_0 = k[s,t]/(st), which is certainly torsion over k[t]. But inverting h yields M' = k[s,t,h,h^{-1}]/(st-h^2). This is a (Z-)graded k[t]-module, so to show it is torsion-free it suffices to show that there are no homogeneous torsion elements.



Let p be any element of k[t] and suppose that pg = f*(st-h^2) for some f in k[s,t,h,h^{-1}] and some homogeneous element g in k[s,t,h,h^{-1}]. Again by homogeneity, we can assume that both f and p are homogeneous, so in particular p = t^k for some k.



But now, we have g * t^k = f * (st-h^2). The ring k[s,t,h,h^{-1}] is a UFD, so either t|f or t|(st-h^2). The latter is false; every degree-1 element of this ring looks like (as + bt + ch)(p(s/h, t/h)), and clearing denominators, to have a solution to pt = st-h^2 would be to have p(s,t)(as + bt + ch)t = h^j(st-h^2), which can't happen since the left-hand-side doesn't have any terms of degree > 1 in h. Hence t|f, so repeating this argument, t^k | f. Dividing both sides by t^k shows that g is divisible by (st-h^2), so g=0 as an element of M'.



I haven't checked that M is flat over k[h], but the definition of M certainly suggests that this should be the case.

Sunday, 1 July 2007

ca.analysis and odes - The characteristic (indicator) function of a set is not in the Sobolev space H1

The answer posted by Tom, as written is actually not true. A function in $H^1$ will not in general be differential almost everywhere; it depends on the dimension. In one dimension however it is indeed true that $H^1$ functions are differentiable almost everywhere (they are in fact absolutely continuous). There are two ways of seeing it is not in $H^1$. The simple answer is that if you differentiate the characteristic function of say $[0,infty)$ then you will get the dirac measure. However let me just answer your question first:



Answer 1:
Take any smooth compactly supported $phi:mathbb{R} to mathbb{R}$. By definition of weak derivative we have
$int phi g^{prime} dx = - int phi^{prime} g dx$ where I've set $g=1_{[0,infty)}$. This would have to be true for all such $phi$ if the weak derivative existed. Now take $phi^{epsilon}$ to be supported in a neighborhood $(-epsilon,epsilon)$ of $0$. We are making the crucial assumption that $g^{prime}$ is an integrable and hence it follows that $int phi^{epsilon} g^{prime} to 0$ as $epsilon to 0$. However, $phi^{epsilon}$ is smooth and so
$int partial_xphi^{epsilon}(x)g(x)dx = phi^{epsilon}(0)$ since $phi$ was assumed to have compact support in $(-epsilon,epsilon)$. Now just fix $phi^{epsilon}(0)=1$ and we have that $phi^{epsilon}(0) to 0$ by the first integral equality. This is a clear contradiction.



Notice that in fact that this really shows that $g' dx = delta(x)$.



Answer 2:
Take $1_{[0,1]}$ instead so that it is an $L^2([0,1])$ function. This is in fact the fourier transform of a "sinc" function, $sin(k)/k$ up to some normalization constants. If we consider the $H^1$ norm in frequency space we would need $int_0^{infty} |k|^2frac{sin(k)^2}{|k|^2} < infty$ which is clearly false. This requires being at ease with the fourier transform so if you're not, answer 1 is probably best.



It is true in $mathbb{R}^n$ that if $u in W^{1,p}$ for $p > n$ then $u$ is a.e differentiable and equals a.e its weak gradient (see Evans chapter 5). This is to correct what Tom had said although perhaps we was thinking about the $n=1$ case in which case $2 > 1$.



Hope this helps!
Dorian

set theory - Shoenfield's Absoluteness Theorem

Wikipedia is correct in that the Shoenfield Absoluteness Theorem holds for plain ZF.



Since the proof of the theorem relies heavily on the absoluteness of well-foundedness, it is tempting to assume DC. However, since the trees that occur in the usual proof of the theorem are canonically well-ordered, DC is not necessary to prove that the well-foundedness of these trees is absolute. For a different approach, see the proof given by Barwise and Fisher in The Shoenfield Absoluteness Lemma. [Israel J. Math. 8 1970, 329-339, MR278934]