Derivatives via Trees

For some reason I've started thinking that teaching first semester calculus classes about syntax trees would be beneficial. Mostly I end up thinking about this applied to the process of taking derivatives (using the rules, not the definition), but I feel like its utility should extend beyond that (eg. graph transformations, and general parsing of mathematics).

I'm thinking start the semester teaching students how to take an expression and make its syntax tree (or at least, 'a' syntax tree representing it). So x+sin(3x) would have root '+' with left child 'x', and right child 'apply' with children 'sin' and '*' (with children '3' and 'x'). Then when you get to derivative rules, you can have the derivative rules work on the level of trees. So you re-phrase the derivative rules by saying you work your way down the tree, and if the node is '+' then you leave the node alone and just do the derivatives of the children individually, and if the node is '*' you replace the node with '+' and make the appropriate children... It seems to me that students might like this approach, as it is fairly graphical in nature. Perhaps visual learners will have an easier time remembering the rules if they are presented this way.

Currently I am thinking about difficulties arising in expressions with exponentials. The expressions x^2 and 2^x have fairly different differentiation rules, which should be reflected in their syntax trees. For example, having a node 'pow' with children 'x' and '2', versus having a node 'pow' with children '2' and 'x'... it'd be easy to mess up the rule. I'm thinking the root nodes should have different names, 'pow' and 'exp', for example. So 'pow' -> ('x', '2') would be x^2, and 'exp' -> ('2', 'x') would be 2^x. This convention fits reasonably with the occasional use of exp(x) for e^x. So what about f(x)^g(x)? Avoid the issue by having students rewrite it as e^(g(x)*ln(f(x))) and using a big tree?

What do you think? Any of this seem worth the trouble? I don't remember ever thinking drawing a syntax tree was difficult, so I would hope that teaching it would be relatively quick - maybe just a day in class, with them doing lots of examples. Then they can use this new understanding throughout the semester (and, hopefully, since it is easy, well past that (unlike lots of the other things that get taught...)). Would it help? The tree for the quotient rule will never match a good 'lo d(high) minus high d(lo) then square below' chant.

One question I have is if students need this. Perhaps my perception is wrong, and they already think in these terms. Or they don't think this way, but parsing the function to be differentiated is not where difficulties lie. Presumably in some sort of grade school they made similar diagrams for sentences. I know my memory isn't great, but I don't remember seeing math syntax trees in classes through high school (or even, potentially, in any math classes, just computer science). Anybody know, or have a better impression? Has anybody tried using syntax trees in calc class (or algebra or something), and found that it was something the students already knew, or that the students found useful?

Wiki Watch

So... its only been fairly recently that I've gotten into rss feeds and things. But I've been really enjoying them. And just the other day I realized an application of them that I would like. I knew that in wikipedia you can tag a page to 'watch', if you are logged in. Then you can view a page of your watchlist, and it will show what pages were recently updated. I've always felt a little bad about not being an active member of the wikipedia editing community, so I thought this would be a great step in the right direction. I could make a watch list of math pages I feel comfortable about, and then watch out for vandalism (which I don't honestly expect happens much with math pages) and just updated articles. And I figured since the page was updated regularly by wikipedia, it'd have an rss feed I could use. That's where it fell apart. I was pretty suprised to find that your personal watchlist doesn't have an rss feed (the rss feed firefox picks up on the page is just the global recently updated pages feed). I looked online, and there seem to be a few people that have written php scripts to create an rss feed... but come on wikipedia.

Join Me

For spaces $X$ and $Y$, recall that the join $X*Y$ is obtained by "drawing all the lines from points in $X$ to points in $Y$". Ok, that's fairly informal. You can define the join as a quotient of the product of $X$ and $Y$ and the unit interval, $I$: $X*Y = (X\times Y\times I)/\sim$ where $(x,y,0)\sim(x,y',0)$ and $(x,y,1)\sim (x',y,1)$ for all $x\in X, y\in Y$. You might visualize this as taking the cylinder on $X\times Y$ (that is, the product with $I$), and collapsing one end to $X$, and the other end to $Y$. For example, the join of $X$ with a single point is the cone on $X$, while the join of $X$ with two points ($S^0$) is the suspension of $X$.

There's another, fancier looking, way to say this: $X*Y$ is the homotopy pushout of the diagram $X\leftarrow X\times Y\rightarrow Y$. If you haven't looked at homotopy pushouts recently... you take the mapping cylinder of $X\times Y \rightarrow Y$, and the mapping cylinder of $X\times Y\rightarrow X$, and you bring together the two 'end' copies of $X\times Y$.

Ok, so, that's all well and good. Now suppose that $X$ and $Y$ are contractible CW complexes with boundaries $\partial X$ and $\partial Y$, respectively (I don't want to define the boundary here... draw a CW complex, and you can tell it's boundary :)). Then the boundary of $X\times Y$ can be realized as the strict pushout (colim) of the diagram $\partial X\times Y\leftarrow \partial X\times \partial Y\rightarrow X\times \partial Y$. The inclusion of the boundary into it's complex is a cofibration, so this strict pushout is homotopy equivalent to the homotopy pushout. Furthermore, since we assumed $X$ and $Y$ were contractible, this diagram is object-wise homotopy equivalent to the diagram $\partial X\leftarrow \partial X\times \partial Y\rightarrow \partial Y$ (and there is an obvious map of diagrams). Taking homotopy pushouts is nice with respect to (object-wise) homotopy equivalent diagrams (with maps between them making everything commute), so putting everything together, we've got

$\partial(X\times Y)\simeq \mathrm{colim}(\partial X\times Y\leftarrow \partial X\times \partial Y\rightarrow X\times \partial Y)$
$\simeq \mathrm{hocolim}(\partial X\times Y\leftarrow \partial X\times \partial Y\rightarrow X\times \partial Y)$
$\simeq \mathrm{hocolim}(\partial X\leftarrow \partial X\times \partial Y\rightarrow \partial Y)$
which we recall is just the join, $\partial X * \partial Y$.

So, that's something. Why do I care? Well, I've been looking at posets recently, and their realizations in order to get some idea about homotopy types of some particular homotopy limits. My posets tend to have initial and final objects, so their realizations are contractible. If I remove the initial and final objects, then the suspension of the resulting realization is the same as the boundary of the realization of the whole poset. Furthermore, the posets turn out to be products of other posets.

Staples Commercial

There's a commercial I've heard a few times recently on the radio that upsets me a little. Its a commercial for Staples. They are playing the famous audio clip from the moon landing, and interrupt the middle of it, saying something like 'Lets cut to something interesting', and go on to mention whatever sale. Except I've not heard the rest of the commercial, because I get distracted, being mildly aggravated.

Unless I'm missing something, landing on the moon was rather a big deal. I'm all for space exploration, and the space program. And so it saddens me to read little articles about how fewer and fewer people care about such things. Or think the space program is a waste of time or resources. I was born well after 'we' landed on the moon, but apparently before people starting losing interest, or something.

For anybody who wasn't sure, there was a post not too long ago about justifying the space program, from a financial standpoint. If you don't think we should be spending our money on such things, do have a look at the article. I seem to recall seeing other articles about how kids are growing up with less interest in space programs, and that one of the potential reasons was the lack of a huge exciting project like landing on the moon. With any luck, new ventures like SpaceShipOne and Virgin's space tourist programs will renew interest (and come down in price, so I can go someday). Or perhaps I'm mistaken about the lack of interest to begin with?

(And I have a hard time being upset with Staples for long. When you walk in, and realize all the vast potential of all that paper, and all those pencils... all neatly lined up... it gets me every time)

In other, not too unrelated, news, there's apparently supposed to be a pretty sweet lunar eclipse Wednesday. At least, it'll be sweet here on the east coast. I hope our weather holds.

OAuth

While writing my recent bit on OpenID, I had in the back of my mind that I also wanted to look up OAuth. I don't remember where I heard about it, or why, but that's beside the point. So I decided today was the day to learn about OAuth, at least a little. I can't say what it is, or how it works, any better than is done here, so you might as well just check that out.

I don't see myself implementing any pages in the near future that use OAuth (besides the point that I don't seem to be doing any implementing...). This is essentially because I lack ideas for pages that require interaction with other services. Even more noteworthy, perhaps, is that most (if not all) of the things I do online don't seem like they would benefit from OAuth. I guess I don't use that many services to begin with, and I don't really see the need for them to interact (besides my google services). Perhaps I'm just behind some curve. After all, facebook doesn't particularly excite me, and certainly hasn't replaced any of my usual forms of interaction.

Anyway, I don't want to sound negative about OAuth. I do think it is a good thing, I can see that it fills a job and can make the web a better place. The trend toward providing your authentication details to fewer sites is a good thing. I look forward to the day when I have a use for OAuth.

p-adics

Yesterday I said I'd post something about p-adics this weekend. I had originally planned on typing up the notes I used for my talk, but may have decided not to do that, saving my time for other things. But I still wanted to post some highlights.

Fix a prime p. For integers x, let v_p(x) denote the largest power of p dividing x (to save some time typing this, I'll drop the p from the notation, and just write v(x)). Note that v(xy)=v(x)+v(y), which looks logarithmic (as well it should, we're talking about powers...). So lets extend the definition to include rationals, via v(a/b)=v(a)-v(b) (and check that this is well defined). I should comment that we set v(0)=∞, with usual conventions for working with ∞. Anyway, our v has another interesting property: v(x+y)≥min(v(x),v(y)), with equality if v(x)≠v(y). To see this, let a=v(x) and b=v(y) and we can then write x=p^am, y=p^bn where p doesn't divide m or n (since p is prime, we could say this as "p doesn't divide mn"). Now v(x+y)=v(p^am+p^bn), so we factor our the least power of p, and we see that v(x+y) is at least that power. Furthermore, suppose a<b. Then x+y=p^a(m+p^b-an), and since p doesn't divide m, p also doesn't divide m+p^b-an (here we use b-a≠0), so v(x+y) is exactly the min of v(x) and v(y), as claimed.

We now create a new absolute value on the rationals, via |x|_p=p^-v(x) (I will, again, drop the p from the notation and just write |x|). Translating the two properties we now know about v(x), we see that |xy|=|x|*|y| and |x+y|≤max(|x|,|y|) (which is, in turn, no larger than |x|+|y|). This new absolute value is stronger than the normal absolute value, in the sense that it satisfies the strong triangle inequality (the second property above). This new absolute value is an example of a "non-Archimedean" norm. A norm is Archimedean if it satisfies the following property: if x is smaller than y, there is a positive integer n such that nx is bigger than y (stick enough small line segments together to make as large a number as you want). Notice that our new absolute value cannot possibly have this property, because for integers n, v(n)≥1, so |n|≤1, and then the multiplicative property tells us |nx|≤|x|, so we've actually made (potentially) our length smaller by taking more copies of it.

Given an absolute value, the thing to do is define a new metric. So let d(x,y)=|x-y|. Keep in mind this is our new absolute value, so I should write d_p(x,y)=|x-y|_p (but it takes longer). Anyway, this metric satisfies the "ultrametric" property: For any z, d(x,y)≤max(d(x,z),d(z,y)) (this is stronger than the normal triangle inequality). What's more: if d(x,z) is different from d(z,y), then d(x,y)=max(d(x,z),d(z,y)). This can be interpreted as saying that "all triangles are isosceles".

With a metric you get the associated topology. Let b(a,r) denote the set of all points whose distance from a is less than r, and B(a,r) be those points whose distance is less than or equal to r. These balls (as they are called) have some interesting properties, different from balls in the normal topology on the reals. I think I'll leave it for you to prove that if x is in b(a,r), then b(a,r)=b(x,r) (I think about this as saying that every point is the center). Using this, we can see that if b(a,r) intersects b(s,t), then one is contained in the other: if x is in the intersection, then b(a,r)=b(x,r), and b(s,t)=b(x,t) and the ball with larger radius contains (possibly with equality) the ball of smaller radius. Now every ball is open in the topology (that's how the topology is defined), but what is new with this topology is that all the balls b(a,r) are also closed.

I'd like to leave you with one last fact about these balls: B(0,1) is the disjoint union of b(0,1), b(1,1),... b(p-1,1). The proof I'll summarize here is from Gouvea's book: Suppose a/b is in B(0,1). Taking a/b to be in lowest terms, we may assume p doesn't divide b (since its distance from 0 is no more than 1...). Consider the p integers a, a-b, a-2b,... a-(p-1)b. It is not too hard to see that these are all distinct mod p, and since there are p of them, exactly 1 of them, say a-ib, is equivalent to 0 mod p. Now check that a/b is in b(i,1). Anyway, that's a start. Perhaps you'd rather thing about it algebraically. If I tell you B(0,1) is a subring of the rationals with maximal ideal b(0,1), can you guess what the b(i,1) are?

So anyway, those are the low hanging fruits of the new metric. Fun things to see, I hope. If you want to learn more, the books by Gouvea and Koblitz were the main ones I looked at when preparing my talk.

OpenID

Last weekend (during the superbowl, actually), I sat down and read a bit about OpenID. There's still plenty I want to read about it, and experimenting to do with it. But as several other pages have pointed out, OpenID got a big boost today, and I felt like talking about it. OpenID is a good thing. Not just in general, but for you, personally.

What openid (I'm too lazy for all those caps) does for you, at the most basic level, is ease password management. Most popular webpages have some sort of login requirement. Which means that every time you want to use a new webpage, you have to sign up again, pick a username and password (making a new one you'll forget, or using the same one everywhere - so that if somebody knows your password in one place, they can pretend to be you anywhere online), enter whatever personal information... etc. And it's a pain. With openid, you pick one place (there are lots of options, and you can even run your own; there's no reason you only need one, of course) that you will use as your personal login hub. Then, for sites that support openid, logging in becomes much easier. Instead of remembering your username and password for that particular site, you tell the site where you have your openid (you specify a url). The site then redirects you there, and you log in at this one central (for you) location. After logging in, you approve the request to use your openid at the site you want, and you get redirected back to the site you wanted in the first place. Your openid provider then acknowledges, to the webpage that you wanted, that you logged in. So, yes, it does seem like an extra step. But it really isn't much, especially when you consider the convenience of one central place to log in.

For example, I registered for an openid at myopenid.com as 'imanidiot'. So if a webpage 'A' requests my openid so I can log in, I tell them 'imanidiot.myopenid.com' (not telling 'A' any password). I get re-directed to imanidiot.myopenid.com, log in (actually, myopenid lets you use digital certificates, so you can easily stay logged in, or log in just by pressing a button (instead of remembering a password)), tell myopenid.com that, yes, I would like to let 'A' know that I have logged in successfully. Then myopenid says ok, and I am back to 'A's page. In the background, 'A' asks myopenid if I really logged in, and myopenid tells them I did (because I told it to).

Depending on your openid provider, you might get additional functionality. For example, at myopenid I can create profiles (you can to, if you register). Then when I want to log in at 'A', I pick a profile to send them (with, say, a nickname, email, picture...) and 'A' can use this information for my profile at 'A'. Handy. I honestly don't know the advantages of differing providers. I didn't want to have to create accounts at them all to find out...

So, you want to try it out, huh? Luckily, you might already have an openid provider. If you have an aol (or aim) account, say 'myaimname', then check out 'openid.aol.com/myaimname'. Yahoo users also have openids through yahoo. If you have an account on blogger, you can use it as your openid provider (you just have to click the check-box in the appropriate privacy page, it's experimental). Otherwise, you'll have to sign up somewhere (the last sign up you'll ever need?). For options (and more sites that might already be giving you an openid), see this list. If you want to try logging in at some site that uses openid, the one I've been pretending to use is plaxo.com (for no particularly good reason, except they've been in the news recently). They also let you log in without openid, but what fun is that?

Anyway, that's a brief intro. I suggest reading more (I know I want to), and if you haven't read any, openid.net is the place to start. If you already know about it, and I used the wrong terminology above in any place, please forgive me.

Guess that's about it for today. I gave a talk today on p-adics, and am planning on typing something up this weekend. There's something for you to look forward to.

Found It

I have asked previously if anybody knew a reference describing the homotopy type of the poset of linear subspaces of Rⁿ (with intial and final object removed). I guess you were all ignoring me. Anyway, last night I finally found it in 'Combinatorics of Topological Posets: Homotopy Complementation Formulas' by Zivaljevic (on the arxiv). There, he provides a proof along the lines of the one I described recently, as well as a proof using the methods the paper is describing. So anyway, if you were curious, check it out.

Poset Realization

Let $Sub(n)$ be the poset of proper nontrivial linear subspaces of $\mathbb{R}^n$. I've asked before if anybody knew the realization of this poset (topological category), and haven't heard anything. Listening to my advisor, it looks like the realization should be homeomorphic to the unit sphere in the following vector space $V$: Let $Sym(n)$ be the symmetric $n$ by $n$ matrices, and include $\mathbb{R}$ via constant diagonal matrices. The quotient $Sym(n)/\mathbb{R}$ is what I will call $V$. To get the unit sphere, we take $(V-0)/\mathbb{R}^+$, where the positive reals act by scalar multiplication (perhaps this could be said better).

Anyway, the correspondence goes something like this. Recall that symmetric matrices have all real eigenvalues, and that the eigenspaces form a direct sum decomposition of $\mathbb{R}^n$. Modding out by $\mathbb{R}$ in $Sym(n)$ shifts eigenvalues (if $e_1,\ldots,e_n$ are the eigenvalues for $M$, then the $e_i+r$ are the eigenvalues for $M+rI$), so we might as well say V is the those symmetric matrices that have 0 as their least eigenvalue. Next, modding by $\mathbb{R}^+$ scales the eigenvalues, so we think of points in the unit sphere of $V$ as symmetric matrices with eigenvalues $0<\lambda_1<\cdots<\lambda_l<1$. The associated eigenspaces $E_1,\ldots,E_l$ let us define a flag $E_1 < E_1+E_2 < \cdots < \sum E_i$, and the eigenvalues themselves pick out a unique point in the simplex corresponding to this flag, in the geometric realization of the poset.

This was pretty brief, and in fact, when I've been messing with it, I generally write the homeomorphism going from the poset to the sphere, but whatever. Apparently its a homeomorphism, so it doesn't matter which way we go :).

Anyway, the main reason I'm posting this is fishing for people who already knew this result (or can see an error - I'm happy to provide a more rigorously written account, on request). My advisor expects the result is 'known to the experts', which clearly doesn't include me. And I can't find a paper with it online. Somebody should really make a theorems database... [Update: Found it]