Rotten Cotton

It seems like you can’t swing a stick on the Web without hitting an article about absurd banking fees: outrageous bank fees and when banks turn evil (MSN Money), five sneaky bank fees (SmartMoney) or rising bank fees hit consumers (USA Today). Some Canadian lawmakers were taking about regulating bank fees earlier this year. I don’t know if anything came of it. You can find similar conversations online from various US cities and states from around 2000. With banks raking in hundreds of millions in ATM fees and billions in general banking fees, I doubt the subject of regulation will come up again.

What’s a hapless consumer to do? Until recently, I was a Bank of America customer (after they bought Fleet who bought Bank Boston who bought my original bank. Or something.) After a few egregious incidents (I won’t go into details. It would only make me angry again.) I got fed up and went out in search of a bank that wasn’t evil, guided by Cotton’s 10th law of personal finance:

Cotton’s 10th law of personal finance: If someone is charging you for the privilege of borrowing your money, you’re getting screwed.

I wasn’t optimistic. What I eventually settled on — Charles Schwab Investor Checking — continues to pleasantly surprise me. I turned a few other people onto it, and they’ve been equally happy. What’s the deal? Well:

• Schwab charges no ATM fees and rebates, at the of each month, ATM fees charged by other institutions when you use their ATMs, anywhere in the world. I’ve been using it for several months, and it is true. Amazing.
• They pay 4.25% APY. This crushes Bank of America’s savings accounts, and even beats out ING Direct’s Electric Orange which yields 4.0% for <$50,000. True, you can do better with various money markets (Vanguard Prime Money Market Fund is yielding 5.13%, for example), but this is a checking account.
• $0 to open with no minimum balance.
• They send you free checks, deposit slips and a stack of postage-paid envelopes for sending in deposits.
• You can configure overdrafts to come out of the linked brokerage account or a Schwab line of credit. You can control this one the web site and they explicitly point it out as something to think about. At Bank of America, I had to call up irate after a $100 overdraft charge on some small purchase to find out I needed to explicitly link overdrafts to my credit card. They waived one of the $33 charges. Gee, thanks.

When I was looking into the account I had a few questions, so I called them up. After a few rings, an actual person answered the phone, “Hi, welcome to Charles Schwab. This is Tom. How can I help you?” No automated menus? No having to enter my account number (three tries) only to be asked for it again when I finally talk to a human being? Tom answered my questions quickly and accurately. These days, this is a revelation. And the best part? It is free.

Go to schwab.com and check it out. To open an investor checking account, you first need to open a SchwabOne brokerage account and then open the (linked) invest checking. All told it took me a few weeks to get it set up and to move everything over from Bank of America.

I have no other interest in Schwab apart from being (so far) a satisfied customer. I know a lot of people are unsatisfied with their banking situation, as I was, and I hope this information might be useful in finding better financial services. If you’ve got something even better, I’d love to hear it.

Update: It is $0 to open with no minimum balance, see here. I had thought it was $2,500 to open and, after that, no minimum balance, but either my recollection was incorrect, or it has changed since I opened my account. Either way…

Working through my ever-growing backlog of unread books, I recently finished John Holt’s How Children Learn and I’m almost done with How Children Fail. These books use a collection of anecdotes drawn from his experience teaching 5th grade, his collaboration with Bill Hull teaching and observing an elementary school class and simply spending time with children as a springboard for his theories about how children learn, why they fail, and how we might go about helping them learn. I found both books engrossing, filled with inspiring and disheartening stories of children’s attempts to understand the world and engage in intellectual work. Perhaps the most inspiring part of the book is John Holt’s mostly-unspoken attitude towards children. He likes children and has a great empathy for them. He enjoys their company, genuinely wants them to succeed, believes them to be fundamentally curious and intelligent and as their teacher holds himself responsible when they fail to learn. He believes them capable and responsible people and treats them as such. I can’t do it justice, if you’re interested in children or education (of children or yourself) I recommend both books. I saw much of myself, successes and failures, in what he described.

John Holt ultimately became disillusioned with schooling and advocated a form of homeschooling called unschooling, following the idea that given ample resources and the freedom to follow their interests, children, naturally curious, could and will learn on their own.

As I read these books, I couldn’t help but think back to my own schooling. Almost every vivid memory that came to mind of schooling was overwhelmingly negative, almost every instance of learning that came to mind, those “aha!” moments of genuine learning (what Holt’s kids called “getting the trick”), happened while exploring my own interests.

When I was eight, my family moved from California to Montana. We moved during the school year and the next fall I was placed in third grade. I remember one day taking turns reading from a science textbook. If you made a mistake while reading, the teacher would flick you in the head with a fingernail. It hurt, yes, but it was nothing compared to the humiliation. My mother eventually became friends with this woman, but to this day I can’t think of her as anything but a bully of eight year olds.

After three weeks it was decided I couldn’t read at a 3rd grade level and I was moved back to a 2nd grade class. I was absolutely devastated. The class was in a different school, I had to take a different (not short!) school bus. I remember two events in particular. Once, during recess, I found a flower going to seed exactly like a picture in our science textbook. I was excited. I picked it and tried to bring it to my teacher. God, I was naive, but hey, I was eight. The teachers were probably chain smoking in the teacher’s lounge. The guard posted at the entrance of the school told me to go play and stop bothering them.

My siblings and I were all successful academically (CalTech, Harvard, MIT, MIT). I often wonder what it was about our childhood that allowed us to succeed. Part of it is what I learned interacting with my siblings, esp. my older brother Huck. One morning, he taught me to do multi-digit addition and subtraction (carry, borrow, etc.) He gave me a problem I worked out on the bus to school, adding two five-digit numbers. When I got to school, I showed my teacher. She took a short look, said, “That’s wrong.” and turned away. I can’t imagine treating a kid like this. It turns out she was alcoholic and died some years later in an alcohol-related car accident. (Back during the summer after his first year at CalTech, Huck showed me some basic calculus, tangents, area under a curve, etc. It blew my mind. I also worked through his textbook on digital design, the one by Mano.)

After that, at least until Jr. high school, my mom got us placed with the better teachers when she could. Most of them weren’t overtly hurtful, but I don’t think I learned much, either.

I took an “AP” (god, I can’t help but laugh) programming class in high school. The class was taught by the wife of the PE teacher/basketball coach. In our little town, the community centered around high school athletics. By then I’d already taught myself more about programming than the teacher knew. She was smart enough to let me do my own thing, which mostly involved writing games for the other kids to play and a basketball stats program for her husband. For the final she asked the other students to write program in BASIC to generate the Fibonacci numbers. Nobody could do it! Amazing. In one year, absolutely no learning had occurred. How was this possible?

Plenty of other episodes come to mind, but let me relate one last one from high school. A physics test had the question: “You throw a ball up in the air. At the apex of the ball’s trajectory, what is the acceleration of the ball? (a) stupid answer (b) 0 (c) another stupid answer, and (d) g.” I answered (d), of course, but it was graded as wrong. The teacher thought the answer was (b). We had a little talk about it. “If there is no acceleration, why does the ball ever come down?” “Well, it is just for an instant.” “Gravity turns off for an instant?” Eventually I suggest we show it more formally: figure out the trajectory for the ball and solve the derivative when the ball as at the apex. I saw in his eyes he realized I was right, but continued to argue against me out of pride. He attacked my use of mathematical formalism to solve the problem! Something about math only approximating physics, and not to confuse the intuitions that come from math with reality. Or something, I’d stopped listening by then. My thinking was developed enough by then to defend myself from his attempts to drive me into confusion, but I fear other students were not so lucky. I lost a lot of respect for schooling in that moment. How did this man become entrusted with the minds of children? A few years later his tenure at my high school (and that of his wife) ended when the police found some hundreds of marijuana plants in his greenhouse.

There was an interesting article in the latest New Yorker, by Atul Gawande, author of the recently published Better, about the shortage of doctors going into geriatrics, and more interesting I thought, the nature of geriatric care.

Yesterday, I went to a talk at Harvard by Walter Willett, professor of Epidemiology and Nutrition at Harvard School of Public Health and author of (among others) Eat, Drink, and Be Healthy. It is on my list of things to read, all the more so after attending his talk.

I took some rough notes. I’m sure everything he said is spelled out more accurately in his book. It seems many of his conclusions were derived from the Nurses’ Health Study, which has been following 122,000 registered nurses since 1976, and Nurses’ Health Study II, started in 1989 to study diet and lifestyle risk in a cohort younger than the original Nurses’ Health Study.

He started out describing the USDA food pyramid, which puts refined carbohydrates at the base of the pyramid and vilifies fats at the top of the pyramid. Much of the remainder of the talk was spent explaining why those two decisions, in particular, were misguided, and motivating a modern take on the food pyramid and optimal diets.

First, fats. The problem with the USDA food pyramid is that it recommends using all fats and oils sparingly, while research shows it is not the amount of fats but rather the type of fats that is important. In particular, trans fats (strongly) and saturated fats (moderately) correlate with increased coronary heart disease (CHD) risk, while mono- and (more strongly) poly-unsaturated fats actually decrease CHD risk. They found no correlation between reduced fat intake and breast cancer risk in the Nurses’ Health Study. Someone during the Q and A period asked a good question about ratios of omega-3 and omega-6. Willett didn’t think this was important and was afraid decreasing omega-6 intake would erode some benefits people are getting by eating good fatty acids.

He did mention the Nurses’ Health Study II showed a correlation between animal fat intake and breast cancer, but only for estrogen positive tumors which have a hormonal link. He called the USDA to get data about hormone levels in meat, but nobody has any data. Scary.

Now, on to fruits and vegetables. They didn’t see a decrease in cancer risk for eating fruits and veggies, but they did see decreased risk for CHD both from fruits and veggies and whole cereals. He had more to say on low glycemic index carbohydrates (good), diary consumption (not bad), vitamin D (get a multivitamin with 1,000 IUs), alcohol (modern intake is OK with if taken with folate), but he went through many dense slides quickly and my notes are vague. You’re probably better off doing your own research if you’re interested in the details. This interview with Willett reproduces the USDA food pyramid and his healthy eating pyramid.

He presented some data on the preventative power of diet on disease. For each disease, they identified an optimal diet to minimize risk. I think he presented data for colon cancer, type 2 diabetes and CHD. In each case, in the Nurses’ Health Study, about 4% were eating the optimal diet, and about 70+% (in some cases more) of the observed incidence of the disease would have been preventable through diet alone.

He didn’t have much to say about protein, so I asked what he thought about the The China Study which I’ve been reading lately. The China Study argues for a whole foods, plant based diet and tries to link most diseases of affluence to animal protein intake. Willett said, paraphrasing from memory: I’ve been friends with Campbell for a long time. He is fanatical on this point, and his own research doesn’t support it.

I’m not trying to take any position, just trying to relate what I learned and heard. Talking with a friend later, she asked me, “So are you still going to be a crazy vegetarian?” Aside from lapses (I had a burger and some prosciutto last weekend) I was already eating fish and eggs, so the real difference between the diet he recommends and what I am shooting for is chicken. Chicken. I’m much rather have a good steak.

I upgraded my blog to Wordpress 2.1.3 and installed the LatexRender plugin. Now I can use pretty symbols for math posts. All the cool math bloggers are doing it. Like and:

and even xy-pic:

Oh my god, how cool is that?

A while back my friend John was writing up a paper (which I think was “The spin bordism of BSpin and K(Z, 4): Dirac operators and integrality”, which his website lists as “in preparation”.)

One result he needed in the paper was a correspondence between the cohomology of K(Z, 4) and some other objects I know nothing about. (I’m obviously going to butcher this. I hope John will chime in and clarify things for interested mathematicians who stumble over this post.) He was able to prove it for the case needed by his paper, but it turns out the conjecture didn’t hold for all of K(Z, 4): the first object of the cohomology that was unaccounted for appeared at degree 49. He didn’t know what the offending object was. It is infeasible to compute it by hand. I had just started studying some computational algebra so I nonchalantly suggested I could write a program to compute the cohomology out to degree 49. Thus a little collaboration was born. John taught me the necessary math and I got a concrete problem in computational algebra to play with. It turned out to be harder than I expected, but I learned a lot.

The basic idea is this. Let H be the mod 2 Steenrod algebra as a A(1)-module, where A(1) is the Steenrod subalgebra generated by sq¹ and sq². We want to decompose H into a direct product of submodules. To do that, we want to find a basis of H (starting from the random basis that follows directly from the definition of H) such that, for each basis element a at degree i, sq¹(a) is a basis element of degree i+1 and sq²(a) is a basis element of degree i+2. Then the submodules of H are just the connected components of the basis elements viewed as a graph.

It took a few iterations with John just to get the Steenrod algebra definitions right. My first cut at an algorithm was completely intractable. In fact, I wasn’t able to improve on the algorithm which searched all possible bases (exponential), but by mod’ing out by the free modules and some intelligent pruning I did get it to run fast enough to compute the decomposition of H through degree 49.

The program spits out a xy-pic .tex file of the desired basis of H. It was exciting when I got everything working. John was on hand, and as we paged through the output of the program (H mod free modules through degree 49 is over a hundred pages.) we found the offending submodule at degree 49: a Moore space (a submodule consisting of a
single sq¹.)

I extended the code to support arbitrary K(Z, n) and BSpin. BSpin won’t work until I find a clever way to compute the decomposition. While working on BSpin, I broke the code and set it aside to move on to other things. This was about a year ago. I picked it up recently and got it working again. I surprised myself with how much math I’ve learned since then. Things I struggled with before (split exact sequences, for example) were now, well, obvious. Now if I just felt that way about sheaves…

I uploaded the output, through degree 33 (pdf, 21pg, 216KB) and degree 55 (pdf, 164pg, 17MB, the Moore space in degree 49 is on page 142) and the source code written in Caml. On a related note, Andre has made an amazing picture of the subalgebra A(2) of the Steenrod algebra (ps, local pdf).

They’re making a movie about Huck, or at least inspired by Huck. Lucky You stars Eric Bana as Huck Cheever, a “hot shot poker player” who tries to win a tournament in Vegas while “fighting a losing battle with his personal problems.” Drew Barrymore plays the love interest.

That’s so unrealistic. Huck would never go for Drew Barrymore.

According to this, Huck, along with a spate of other professional poker players, are to appear in the movie. I haven’t talked to him about it yet.

For those of you who don’t know me, or haven’t been subjected to endless Vegas stories, my older brother Huckleberry (aka Huck, get it right, Wikipedia) is a professional poker player and 1996 World Series of Poker Champion.

Yes, it is that time again, to give some attention to my neglected blog. The masses are getting restless, people have been asking if and when I’m going to update The Bad Seed again. I also promise something non-techincal for those of you who aren’t armchair mathematicians, otherwise my mom is going to stop reading. For now, on to the goods…

This is forth in a series of posts on Grobner bases. If you haven’t, go read part I, II and III.

We’ve laid the necessary groundwork, now we’re ready to define a Grobner basis and figure out how to find one. Let’s go!

We defined the leading term of a polynomial f, LT(f), to be the greatest (according to the lexical ordering) term of the polynomial. We extend this to ideals, and say the leading terms of an ideal I, LT(I), is the leading terms of its members, that is LT(I) = { LT(f) | f in I }. A set G = { g₁, g₂, …, g_n } with g_i in G is a Grobner basis if <LT(g₁), LT(g₂), …, LT(g_n)> = <LT(I)>.

So a Grobner basis is a set whose leading terms generate the same ideal as the leading terms of the ideal it represents as a Grobner basis.

What a disappointment. What good is this?

Let’s look a more closely at our construction, and we’ll find it has all the properties we’ve been looking for.

First, we want to argue G is a basis of I, that is, <G> = I. We note that <G> is a subset of I as each g_i is in I. Let f be a polynomial in I. It remains to show that f is in <G>. Divide f by g_is in any order, which gives us f = sum(q_ig_i) + r. r must be zero. If not, no term of r divisible by any LT(g_i), but r is in I, so LT(r) is in <LT(I)> = <G>, which implies that LT(r) is divisible by some LT(g_i). Since r = 0, f is in <G> and <G> = I.

G generates I, great, but what about our goal to solve the ideal membership problem? How about this theorem? Let G = { g₁, …, g_n } be a Grobner basis for an ideal I, and f a polynomial in F[xⁿ]. Then there is a unique r in F[xⁿ] such that no term of r is divisible by any LT(g_i) and there are q_is such that f = sum(q_ig_i) + r. r is unique! In particular, it is independent of the order of the g_is. This solves perfectly the problem we encountered before in our naive attempt to generalize division to solve the multivariate ideal membership problem.

Proof. Our old division algorithm gives us an r, but it might not be unique, that is, there might be r, r’ such that f = sum(q_ig_i) + r = sum(q_i‘g_i) + r’. We want to show r = r’. If r is not equal to r’, we have r - r’ is in I, so LT(r - r’) is in <LT(I)> = <G>, which implies LT(r - r’) is divisible by some LT(g_i). But this is impossible since neither r nor r’ are divisible by any LT(g_i) so r - r’ = 0 and r = r’.

Woot! If we have a Grobner basis for an ideal, we can use it to solve the ideal membership problem. Just use our generalized division algorithm to divide by the g_is in any order. So how do we find a Grobner basis? We need an algorithm.

On our way to an algorithm, we first need define something called the S-polynomial. Let LM(f), the leading monomial of f, be the greatest (according to the lexical order) monomial (the variable and exponent part, excluding the coefficient) of f. Let the least common multiple of two monomials, x^a and x^b, be a monomial whose exponent is the maximum of a and b at each point, that is, x^c where c = (max(a₁, b₁), …, max(a_n, b_n)). Then we define the S-polynomial of two polynomials f and g to be S(f, g) = x^af/LT(f) - x^ag/LT(g) where x^a is the LCM(LM(f), LM(g)).

What does the S polynomial do? Basically, it has the effect of cancelling leading terms. If you look at just the leading terms of f and g, you can see they cancel: x^aLT(f)/LT(f) - x^aLT(g)/LT(g) = 0.

Now we can give a new condition for Grobner bases based on the S-polynomial that will clearly lead us to an algorithm. G is a Grobner basis iff S(g_i, g_j), i unequal to j, has remainder zero when divided by g_is (in any order.) I’m going to skip the proof.

So what’s the algorithm? Basically, given a basis which is not a Grobner basis, we’ll compute the S-polynomial remainder for each pair g_i, g_j. If the remainder is non-zero, we just add that to the basis G until the remainder is zero for all such pairs. This is known as Buchberger’s algorithm. In pseudocode:

do
  oldG = G
  changed = false
  for each pair f, g in oldG, f != g
    r = S(f, g) mod oldG
    if r != 0
      changed = true
      add r to G
while changed

When the iteration terminates, G is clearly a Grobner basis since the S-polynomial for each pair is zero modulo G. It only remains to be shown that the iteration terminates. This follows from the ascending chain condition on ideals. The ascending chain condition says that for an ascending chain of ideals in F[xⁿ], I₁ subset I₂ subset I₃ …, etc. there exists some N such that I_N = I_N+1 …, etc. (Proof omitted.) In each iteration of the outer do-while loop, <LT(G)> is strictly increasing: <LT(G₁)> subset <LT(G₂)> subset <LT(G₃)> …, etc. So by the ascending chain condition <LT(G)> eventually stabilizes and the algorithm terminates.

I realize this was a bit abstract, but we’re over the hump now: we now what Grobner bases are and how to compute them. In the next installment we’ll cook up some (real) code for manipulating polynomials and look at some more concrete examples and applications.

A post of fluffy ruminations.

In the comments on my post bootstrapping the lambda calculus, there was a short discussion about the inability to implement the Y combinator in the polymorphic lambda calculus. This is true of all the lambda calculi in Barendregt’s lambda cube. Those calculi admit decidable procedures for term equivalence and as logics they are consistent.

Most programming languages based on these calculi add some kind of support for recursion. Plotkin’s PCF adds the Y combinator, ML has letrec and Haskell supports named recursion.

Adding Y (or recursion) makes these languages universal, true. Is that power really necessary? Without Y, you can still write the usual, silly examples (in Haskell, using recursion only to convert between Integer and church numerals):

 -- play fast-and-loose with Haskell Integers and church numerals (cn)
int_to_cn 0 f = id
int_to_cn n f = f . (int_to_cn (n - 1) f)

cn_to_int n = n (+1) 0

 -- fib and fact
fib n = fst ((int_to_cn n) fib1 (1, 1))
    where fib1 (a, b) = (b, a + b)

fib 7
 => 21

fact n = snd ((int_to_cn n) fact1 (n, 1))
    where fact1 (a, b) = (a - 1, a * b)
fact 5
 => 120

The question becomes, what programs can you write in the polymorphic lambda calculus? What programs require the unbridled power of universality? Interesting questions. I don’t have any answers.

This is the approach taken by systems that blur the distinction (via the Curry-Howard isomorphism) between programming and theorem proving, like Coq and, I assume, Epigram. Programs in these systems provably terminate, and in some sense are “verified” by their types. These systems support non-trivial programs, for example, Xavier Leroy implemented a compiler in Coq, proven correct, for much of C to PowerPC assembly.

If the answer is the programs you can write are simply those that you can prove correct (whatever that means. I’m still trying to understand how types, esp. dependent types, correspond to theorems about programs. fact and fib both have type Integer -> Integer, which asserts that, given an integer, they return an integer, but this type doesn’t make an assertions about the values returned by these functions. This is a rather trivial assertion of the “correctness” of fact or fib.) then giving up recursion for bounded induction doesn’t lose you anything. I mean, you’re proving all your programs correct already, right?

I went for a walk and it instantly became obvious how to directly prove F[x] is a PID. Consider an ideal I of F[x]. If I is the zero ideal, we can write I = <0>. If not, I has some non-zero element f with least degree deg(f). Now consider some element of I, g. Divide g by f getting g = qf + r. By definition of division, we know deg(r) < deg(f). But, by definition of an ideal, g - qf = r is in I. This contradicts our assumption that f has least degree, so r must be zero. Thus f divides each element of I, and we can write I = <f>, thus F[x] is a PID.

The same method is used to prove Eclidean domains are PIDs, except instead of degree you use the Euclidean valuation.

In my last post on Grobner bases, I made a claim that was flat out wrong. I said that multivariate polynomial rings are neither principle ideal domains (PIDs) or unique factorization domains (UFDs). They are not PIDs — I gave a counterexample — but they are unique factorization domains. It is just that we can’t use GCDs to solve the membership problem like we did with univariate polynomials. I = <x, y> and gcd(x, y) = 1 but I != <1> (which is the entire ring.) So we generalized division instead.

To clear up my own confusion, I want to develop some of the theory around UFDs. First, some definitions:

Let R be a unital ring, not necessarily commutative. An element x of R is an unit if there exists an element b such that ab = 1. That is, units are the invertible elements of the ring. Don’t confuse a unit element, the multiplicative identity, with a unit. In Z, the units are 1 and -1. For a field, all elements (except 0) are units.

A non-unit element x of R is irreducible if, whenever x = ab, one of a or b is a unit. That is, a irreducible element cannot be written as a product of non-units.

A zero divisor is an element x of R, non-zero, such that there exists b non-zero, xb = 0.

An integral domain is a commutative ring R such that, for a, b in R, ab = 0 implies one of a or b equals zero. Alternatively, a integral domain is a commuative ring with no zero divisors.

An principle ideal domain is an integral domain R where every ideal can be generated by single element. That is, for every ideal I, there exists some r in R such that I = <r>.

Now we can define a unique factorization domain: a UFD is an integral domain such that non-zero elements can be written as a finite product of irreducible elements unique up to order and units. That is, if x = a₁a₂ … a_m and x = b₁b₂ … b_n a_is and b_js irreducible, then n = m and there exists a bijective map phi over {1..n} such that a_i = ub_phi(i) for some unit u (that is, a_i and b_phi(i) are associated.) All fields are trivially unique factorization domain.

Now that we have the necessary definitions down, we want to show if R is a unique factorization domain, so is R[xⁿ]. This is not exactly trivial and my lunch is overdue, so I’m going to write the proof up in another post.

We also want to show F[x] is a principle ideal domain. I’m not sure how to do that directly without talking about Euclidean domains, so I’m going to queue up another post for that, too.