Student faces expulsion for Facebook study group

Student faces expulsion for Facebook study group, from Slashdot. (The original article is from the Toronto Star.)

Basically, it's what it sounds like from the headline -- a student, Chris Avenir, started a group for discussing one of his classes on Facebook, and is now being charged with 147 counts of academic misconduct for doing so. The Slashdot comments are surprisingly insightful; basically we hear people point out that in the end you learn a lot more from talking to other people than from working in isolation anyway.

I'm not sure how I feel about the actual case in question. The "147 counts" sounds like trumped-up charges (and besides, how can they punish him 147 times?), but as some people have pointed out, certainly meaningful collaboration wasn't taking part in that large of a group. This is something I've felt when I've worked with groups on assignments, although in the end I rarely work with groups because either I feel that the other people in the group are bringing less to the table than me (and then I feel bitter that I'm doing their work for them) or are bringing more to the table than me (and then I feel guilty for sponging off of them). But I certainly am okay with the idea of people working in groups, both in classes that I'm taking and in classes that I'm teaching. Note that this is just my attitude towards collaboration in classes. My attitude towards collaboration in actual research is not well-formed yet.

A factoring trick

I came across the polynomial f(x) = 2x² + 3x - 5 during a calculation I was doing a few days ago. I wanted to factor it. Sure, I could have done it the usual way. But I have a better intuition for factoring numbers than I do for factoring polynomials. So I plug in x = 10; then f(10) = 225.225 factors into 9 times 25. Perhaps this reflects a factorization f(x) = g(x) h(x), where g(10) = 9, h(10) = 25.

Indeed, it does: 2x² + 3x - 5 = (x-1)(2x+5). Of course, this gives a whole family of integer factorizations, plugging in different integers for x.

Of course, this doesn't work in general; consider for example 2x² + 2x + 5, which doesn't factor at all. And when the trick is spelled out explicitly it seems to be irredeemably flawed -- how did I know to take (x-1)(2x+5), say, and not (x-1)(3x-5)? (More importantly, can this be explained without reference to the original polynomial?) One could perhaps point out that, say, 184 = (8)(23), which is just f(9) = g(9) h(9), and so on; from a family of such facts it might be possible to deduce the polynomial factorization, but at that point it's just not worth the trouble. These sorts of tricks, like jokes, rarely stand up to explanation.

Bollobas and Riordan's "Percolation" -- cheap at Amazon

Amazon.com is selling Bollobás and Riordan's Percolation for $40.28 (marked down from $79).

Percolation isn't a subject that I'm interested enough in to buy the book (especially since our library has it), but I have talked about percolation here before and gotten some interesting responses, so I thought there might be someone out there who'd appreciate knowing.

Breadth-first versus depth-first browsing

Firefox's tabbed browsing feature encourages breadth-first search. If I click on a link the tab containing the page linked to appears as the rightmost tab, and I generally work through tabs from left to right. Breadth-first search can be implemented in this way -- we maintain a list of pages to be looked at, and the first page to enter the queue is also the first page to leave it.

Depth-first browsing wouldn't be too much different on a cosmetic level -- it could be set up by having the new tab appear immediately after the current tab, giving a stack of pages to view instead of a queue. I suspect the subjective experience of Internet browsing would feel much different from such a point of view -- browsing often seems to lead to shallow knowledge. (If one had time to search the entire Internet breadth-first search and depth-first search would eventually visit the same set of pages -- but who has that kind of time?) The "optimal" algorithm for finding particular information isn't strictly breadth-first or depth-first, though; if you think about how you search when you look for a specific piece of information, you don't routinely follow the leftmost tab or the rightmost tab, but instead click on whatever tab subjectively seems like it would give the best information.

The Harvard College Mathematics Review

There exists something called the Harvard College Mathematics Review, which "is a semiannual journal of expository mathematical articles written and edited by undergraduates." I learned about this from Vishal Lama's blog. (Conveniently, the how to link to a blog question is almost irrelevant here.)

The faculty feature article by Noam Elkies which was in their first issue, about the abc conjecture, is quite interesting. (I especially like the heuristics given therein for the number of rational points lying on certain curves and other solutions to diophantine equations -- concerning such questions as Mordell's conjecture and Fermat's last theorem -- which shouldn't surprise longtime readers.)

There have been two issues so far: the first issue and the second issue.

You know it's got to be good -- or at least it looks good from the table of contents and the few links I clicked on -- because I went to MIT for undergrad and I'm now a grad student at Penn and I'm still telling you about it. And you've got to love any publication which includes an article entitled Dunking Donuts: Culinary Calculations of the Euler Characteristic. I mean, who hasn't gotten hungry while doing topology? All those tori look like donuts.

And the editor-in-chief of the HCMR is Scott Kominers, who I've previously mentioned as one of the authors of a paper about whether or not you should wait for the bus.

A leap year scheme based on binary expansions

Yesterday I wrote about leap day, and how a different scheme of determining which years are leap years could make calendrical calculation easier. In particular, the number of days in a year is very nearly 365+31/128; how can we pick 31 years out of every 128 to be leap years? (As was pointed out in the comments, 128 is a power of two, which is what makes this whole post work.)

The answer is obvious -- take every fourth year, except don't take years divisible by 128.

But then I asked -- what if we needed to take 33 years out of every 128? We clearly should take every fourth year... and then one more out of every 128. But which one?

I'm implicitly using the fact 31/128 = 1/4 - 1/128 and 33/128 = 1/4 + 1/128. But we can also write:

33/128 = 1/2 - 1/4 + 1/128.

Why would I do this? Because it gives a very good scheme for assigning 33 leap years out of every 128. Include in the set of leap years all years which are even, but not those that are divisble by 4, but do include those which are divisible by 128. So in every 128-year period we include the year 0, and the years 2, 6, 10, ..., 126.

But there's a nicer way to express that. Look at the binary expansion of such a year. Either it ends in exactly one 0 (it's 2 more than a multiple of 4) or it ends in at least seven 0s (it's a multiple of 128). It turns out that for any fraction of the form m/2ⁿ, where 0 ≤ m < 2ⁿ, we can write m/2ⁿ as an alternating sum of powers of 1/2. For example, consider

59/128 = 1/4 + 1/8 + 1/16 + 1/64 + 1/128.

where that's just the ordinary binary expansion. We can group the consecutive powers of 2 in the binary expansion together to get

59/128 = (1/4 + 1/8 + 1/16) + (1/64 + 1/128)

and then each sum of consecutive powers can be written as a difference, giving

59/128 = 1/2 - 1/16 + 1/32 - 1/128.

So let's say we want 59 leap years out of every 128. We include all the even years, but we don't include those that are divisible by 16, but we do include those that are divisible by 32, but then we don't include those that are divisible by 128.

It sounds complicated -- but there's a better way to say it. If you think about it, the rule I just gave says that the binary expansion of a leap year must end in 1, 2, 3, 5, or 6 zeroes. Write 59/128 = .0111011₂. Now, there are 1s in exactly the 2nd, 3rd, 4th, 6th, and 7th places after the decimal point. That's not a coincidence. The proportion 1/2ⁿ⁺¹ of integers will have binary expansions ending in exactly n zeroes. In general, if we want m/2ⁿ of our years to be leap years, then we can determine if any given year k is a leap year via a scheme like this, as follows:
- let p be the number of zeroes terminating the binary expansion of k.
- if the (p+1)st bit of m/2ⁿ after the decimal point is 1, then k is a leap year, otherwise it's a common year.

The years for which we examine the jth bit are exactly 1/2^j of all years, so this works.

For 31/128 = .0011111, this says that a year should be a leap year if its binary expansion ends in exactly 2, 3, 4, 5, or 6 zeroes -- exactly the rule I suggested in the first place. For 33/128 = .0100001, a year is a leap year if its binary expansion ends in exactly 1 or 6 zeroes. That's one flaw with this scheme -- the set of leap years changes radically as m/2ⁿ passes through some small power of (1/2). But that wasn't my aim here; my aim was to be able to read off if a year is a leap year directly from the binary expansion, just as one can almost do with the decimal expansion in the current scheme. The 8/33 scheme I talked about yesterday doesn't have this property in any small base, although I made the argument that since 33 = (100-1)/3 there are worse situations to be in.

(Exercise for the reader: can you come up with a scheme like this in decimal? Calling this an "exercise" isn't quite fair, because I don't know if it's possible.)

Zeros of some polynomials arising from sums

Here's a little thing I thought of a few days ago. Consider the following identities for the sums of powers:

(okay, that's kind of stupid, but you have to start somewhere...),

;

(the right-hand side might be more familiar as n(n+1)(2n+1)/6), and

(the right-hand side here is,coincidentally the square of (1+2+...+k). For each choice of exponent we get a different polynomial in the numerator. They all factor into linear terms... that doesn't keep up, though. For example,

Still, one wonders -- what are the roots of these polynomials? (The first thought is that they're always in the interval [-1, 0], but that's pretty quickly disproven by considering the sum of 5th powers.)

Some computation shows that the patterns of zeroes in the complex plane are both symmetric around the real axis (no surprise there; zeroes come in complex conjugate pairs!) and around the line y = -1/2 (a bit more surprising). So you think to plot them, and you get something that looks like this plot for the polynomial you obtain when you sum 300th powers. (I didn't make that plot; it's from Richard Stanley's web page on interesting zeros of polynomials.)

It turns out that they're the Bernoulli polynomials; for very large n Veselov and Ward showed that the real zeroes are very near 0, ± 1/2, ± 1, ... if n is odd, and ± 1/4, ± 3/4, ± 5/4, ... if n is even; furthermore, in the limit, the nth Bernoulli polynomial has 2/(πe)n real zeros. (2/πe is about .235; thus in the 300th Bernoulli polynomial we expect about 70 real zeros, taking up an interval of length 35 or so centered at -1/2 on the real line; that's what you see in that plot.)

Goh and Boyer (who I've mentioned before for similar work on partition polynomials) have found the "zero attractor" of the Euler polynomials, and state in their paper that the methods there also give a similar result for the Bernoulli polynomials -- basically, what this means is that if we shrink down the plot of the zeros of the nth Bernoulli polynomial by a factor of n, then the zeroes fall very close to some limiting curves and are arranged with a certain density along those curves. (Along the portion of the real axis in question, the density is constant; along the other branches it doesn't seem to be.)

References:
William M. Y. Goh, Robert Boyer. On the Zero Attractor of the Euler Polynomials. arXiv: math.CO/0409062. (2004)
Alexander Veselov and Joseph Ward, On the real zeroes of the Hurwitz zeta-function and Bernoulli polynomials, arXiv: math.GM/0205183. (2002)