You are currently browsing the monthly archive for May 2008.

Okay, time for another Problem of the Week! This little cutie is something I discovered by accident, while doodling around with iterated antiderivatives (but never mind which ones for now!):

Compute for .

Please send your solutions to **topological[dot]musings[At]gmail[dot]com** by **Tuesday, June 3** (11:59pm UTC); do **not** submit solutions in Comments. Everyone who submits a correct solution gets mentioned in our Hall of Fame! Have fun…

Last time in this series on Stone duality, we observed a perfect duality between finite Boolean algebras and finite sets, which we called “baby Stone duality”:

- Every finite Boolean algebra is obtained from a finite set by taking its power set (or set of functions from to , with the Boolean algebra structure it inherits “pointwise” from ). The set may be defined to be , the set of Boolean algebra homomorphisms from to .
- Conversely, every finite set is obtained from the Boolean algebra by taking its “hom-set” .

More precisely, there are natural isomorphisms

in the categories of finite Boolean algebras and of finite sets, respectively. In the language of category theory, this says that these categories are (equivalent to) one another’s opposite — something I’ve been meaning to explain in more detail, and I promise to get to that, soon! In any case, this duality says (among other things) that finite Boolean algebras, no matter how abstractly presented, can be represented concretely as power sets.

Today I’d like to apply this representation to *free* Boolean algebras (on finitely many generators). What is a free Boolean algebra? Again, the proper context for discussing this is category theory, but we can at least convey the idea: given a finite set of letters , consider the Boolean algebra whose elements are logical equivalence classes of formulas you can build up from the letters using the Boolean connectives (and the Boolean constants ), where two formulas are defined to be *logically equivalent* if and can be inferred purely on the basis of the Boolean algebra axioms. This is an excellent example of a very abstract description of a Boolean algebra: syntactically, there are infinitely many formulas you can build up, and the logical equivalence classes are also infinite and somewhat hard to visualize, but the mess can be brought under control using Stone duality, as we now show.

First let me cut to the chase, and describe the key property of free Boolean algebras. Let be any Boolean algebra; it could be a power set, the lattice of regular open sets in a topology, or whatever, and think of a function from the set of letters to as *modeling* or interpreting the atomic formulas as elements of . The **essential property** of the free Boolean algebra is that we can extend this interpretation in a unique way to a Boolean algebra map . The way this works is that we map a formula like to the obvious formula . This is well-defined on logical equivalence classes of formulas because if in , i.e., if the equality is derivable just from the Boolean algebra axioms, then of course holds in as the Boolean algebra axioms hold in . Thus, there is a natural bijective correspondence between functions and Boolean algebra maps ; to get back from a Boolean algebra map to the function , simply compose the Boolean algebra map with the function which interprets elements of as equivalence classes of atomic formulas in .

To get a better grip on , let me pass to the Boolean ring picture (which, as we saw last time, is equivalent to the Boolean algebra picture). Here the primitive operations are addition and multiplication, so in this picture we build up “formulas” from letters using these operations (e.g., and the like). In other words, the elements of can be considered as “polynomials” in the variables . Actually, there are some simplifying features of this polynomial algebra; for one thing, in Boolean rings we have idempotence. This means that for , and so a monomial term like reduces to its *support* . Since each letter appears in a support with exponent 0 or 1, it follows that there are possible supports or Boolean monomials, where denotes the cardinality of .

Idempotence also implies, as we saw last time, that for all elements , so that our polynomials = -linear combinations of monomials are really -linear combinations of Boolean monomials or supports. In other words, each element of is uniquely a linear combination

where

i.e., the set of supports forms a basis of as a -vector space. Hence the cardinality of the free Boolean ring is .

**Remark**: This gives an algorithm for checking logical equivalence of two Boolean algebra formulas: convert the formulas into Boolean ring expressions, and using distributivity, idempotence, etc., write out these expressions as Boolean polynomials = -linear combinations of supports. The Boolean algebra formulas are equivalent if and only if the corresponding Boolean polynomials are equal.

But there is another way of understanding free Boolean algebras, via baby Stone duality. Namely, we have the power set representation

where is the set of Boolean algebra maps . However, the freeness property says that these maps are in bijection with functions . What are these functions? They are just truth-value assignments for the elements (atomic formulas, or variables) ; there are again many of these. This leads to the method of **truth tables**: each formula induces (in one-one fashion) a function

which takes a Boolean algebra map , aka a truth-value assignment for the variables , to the element of obtained by instantiating the assigned truth values for the variables and evaluating the resulting Boolean expression for in . (In terms of power sets,

identifies each equivalence class of formulas with the set of truth-value assignments of variables which render the formula “true” in .) The fact that the representation is injective means precisely that if formulas are inequivalent, then there is a truth-value assignment which renders one of them “true” and the other “false”, hence that they are distinguishable by truth tables.

- Remark: This is an instance of what is known as a
*completeness theorem*in logic. On the syntactic side, we have a notion of provability of formulas (that is logically equivalent to , or in if this is derivable from the Boolean algebra axioms). On the semantic side, each Boolean algebra homomorphism can be regarded as a*model*of in which each formula becomes true or false under . The method of truth tables then says that there are enough models or truth-value assignments to detect provability of formulas, i.e., is provable if it is true when interpreted in any model . This is precisely what is meant by a completeness theorem.

There are still other ways of thinking about this. Let be a Boolean algebra map, aka a model of . This model is completely determined by

- The maximal ideal in the Boolean ring , or
- The maximal filter or ultrafilter in .

Now, as we saw last time, in the case of finite Boolean algebras, each (maximal) ideal is principal: is of the form for some . Dually, each (ultra)filter is principal: is of the form for some . The maximality of the ultrafilter means that there is no nonzero element in smaller than ; we say that is an *atom* in (NB: not to be confused with atomic formula!). So, we can also say

- A model of a finite Boolean algebra is specified by a unique atom of .

Thus, baby Stone duality asserts a Boolean algebra isomorphism

Let’s give an example: consider the free Boolean algebra on three elements . If you like, draw a Venn diagram generated by three planar regions labeled by . The atoms or smallest nonzero elements of the free Boolean algebra are then represented by the regions demarcated by the Venn diagram. That is, the disjoint regions are labeled by the eight atoms

According to baby Stone duality, any element in the free Boolean algebra (with elements) is uniquely expressible as a disjoint union of these atoms. Another way of saying this is that the atoms form a basis (alternative to Boolean monomials) of the free Boolean algebra as -vector space. For example, as an exercise one may calculate

The unique expression of an element (where is given by a Boolean formula) as a -linear combination of atoms is called the **disjunctive normal form** of the formula. So yet another way of deciding when two Boolean formulas are logically equivalent is to put them both in disjunctive normal form and check whether the resulting expressions are the same. (It’s basically the same idea as checking equality of Boolean polynomials, except we are using a different vector space basis.)

All of the above applies not just to free (finite) Boolean algebras, but to general finite Boolean algebras. So, suppose you have a Boolean algebra which is generated by finitely many elements . *Generated* means that every element in can be expressed as a Boolean combination of the generating elements. In other words, “generated” means that if we consider the inclusion function , then the unique Boolean algebra map which extends the inclusion is a *surjection*. Thinking of as a Boolean ring map, we have an ideal , and because is a surjection, it induces a ring isomorphism

The elements of can be thought of as equivalence classes of formulas which become *false* in under the interpretation . Or, we could just as well (and it may be more natural to) consider instead the *filter* of formulas in which become *true* under the interpretation . In any event, what we have is a propositional language consisting of classes of formulas, and a filter consisting of formulas, which can be thought of as theorems of . Often one may find a filter described as the smallest filter which contains certain chosen elements, which one could then call *axioms* of .

In summary, any *propositional theory* (which by definition consists of a set of propositional variables together with a filter of the free Boolean algebra, whose elements are called *theorems* of the theory) yields a Boolean algebra , where dividing out by means we take equivalence classes of elements of under the equivalence relation defined by the condition “ belongs to “. The partial order on equivalence classes [] is defined by [] [] iff belongs to . The Boolean algebra defined in this way is called the *Lindenbaum algebra* of the propositional theory.

Conversely, any Boolean algebra with a specified set of generators can be thought of as the Lindenbaum algebra of the propositional theory obtained by taking the as propositional variables, together with the filter obtained from the induced Boolean algebra map . A *model* of the theory should be a Boolean algebra map which interprets the formulas of as true or false, but in such a way that the theorems of the theory (the elements of the filter) are all interpreted as “true”. In other words, a model is the same thing as a Boolean algebra map

i.e., we may identify a model of a propositional theory with a Boolean algebra map out of its Lindenbaum algebra.

So the set of models is the set , and now baby Stone duality, which gives a canonical isomorphism

implies the following

**Completeness theorem**: If a formula of a finite propositional theory is “true” when interpreted under any model of the theory, then the formula is provable (is a theorem of the theory).

**Proof**: Let be the Lindenbaum algebra of the theory, and let be the class of formulas provably equivalent to a given formula under the theory. The Boolean algebra isomorphism takes an element to the map . If for all models , i.e., if , then . But then [] , i.e., , the filter of provable formulas.

In summary, we have developed a rich vocabulary in which Boolean algebras are essentially the same things as propositional theories, and where models are in natural bijection with maximal ideals in the Boolean ring, or ultrafilters in the Boolean algebra, or [in the finite case] atoms in the Boolean algebra. But as we will soon see, ultrafilters have a significance far beyond their application in the realm of Boolean algebras; in particular, they crop up in general studies of topology and convergence. This is in fact a vital clue; the key point is that the set of models or ultrafilters carries a canonical topology, and the interaction between Boolean algebras and topological spaces is what Stone duality is all about.

The solutions are in! We had a good response to last week’s problem:

- Consider a rectangle with sides of integer lengths and , subdivided into unit squares, and a diagonal line from corner to corner. Show that the number of unit squares that the line crosses is . (Count only those cases where the line crosses the interior of a square.)
- What would be the -dimensional analogue of the previous problem? How would you prove it?

The solution below is due to Paul Shearer (University of Michigan):

**Solution to POW-2**: We’ll solve part 2, which subsumes part 1.

Let be the vector of box sidelengths, and the number of boxes crossed by the diagonal going from 0 to a. Then we claim

where denotes the cardinality of a set . [Note that for , this simplifies to , the result of part 1.]

**Proof**: Parametrize the diagonal by the function for , and let denote the coordinate of . Defining [] , we have

[Proof: let < < … < be the set on the right-hand side. Each corresponds to an interval where the line is in the interior of exactly one box, since a point in a box is interior if none of its coordinates is an integer. Hence there is a bijection between ‘s and boxes crossed.]

For , let . Then

by the inclusion-exclusion principle, so we need only verify that . Indeed, given , will be an integer for all if and only if for , i.e. for different values of .

**Remarks**: Philipp Lampe notes that the case is given by Andreescu and Feng, A Path to Combinatorics for Undergraduates: Counting Strategies (Birkhäuser, 2004). He also gave a solution from which a proof of the inclusion-exclusion principle (which involves binomial coefficients) can be extracted. A number of people gave the correct formula for general , but full credit was given only for complete proofs.

Also solved by Sune Jakobsen, Philipp Lampe. Solutions to part 1. were given by Jimbo Doe, Jason Dyer, and Marni Sheppeard.

Since the cat’s out of the bag and we’ve had some public discussion of our first Problem of the Week, I thought I’d officially kick things off with a new problem, *this time* under the ground rules discussed in our last post. This one comes from our regular reader John Smith, who wrote me this problem in email. It comes in two parts; here’s the first:

Consider a rectangle with sides of integer lengths and , subdivided into unit squares, and a diagonal line from corner to corner. Show that the number of unit squares that the line crosses is . (Count only those cases where the line crosses the interior of a square.)

A little while later, John wrote me a follow-up question, which will be our part two:

What would be the -dimensional analogue of the previous problem? How would you prove it?

Please submit your solutions **through email** to topological[dot]musings[At]gmail[dot]com, rendering the stuff in brackets in the obvious way; please **do not** reply in comments! Solutions should arrive by May 20 (11:59pm UTC time if you want to be exact). We will post one of the correct solutions (or otherwise our own), but all correct solutions will be acknowledged, and successful solvers will have their names entered into our Problem-Solving Hall of Fame. So get your answers in, and happy solving!

[Added May 15: if you just want to solve part one, that’s fine — credit will be awarded for correct solutions. In general for multi-part problems, we ask that you submit all parts you intend to solve in one mailing — thanks.]

Todd and I, after some discussion, have decided to start a new series of posts called “**Problem of the Week**“. Since the title is self-explanatory, there is nothing much to write about, except that this series will be a permanent fixture on our blog. Each week we will post a problem (unless both of us are too busy), and we invite solutions from all our readers, regular or not; in most cases solutions should be submitted through email within a week after the post. To keep things fair, we ask readers **not** to submit solutions in the comment section of a post. At the end of the allotted time, we will then select the most elegant solution (or anyway, one that we like) to a given problem, and post it together with the name of the proposer. (Note: solutions may be edited, or composed from solutions of more than one proposer.) Other people who submit correct solutions will also be acknowledged. In addition, credit will be given to all such people by having their names enshrined in the *Problem-Solving Hall of Fame* page, forever! Who could ask for anything more?!

Most of our problems will be “elementary”, meaning they won’t require knowledge of advanced areas of mathematics; generally they will require some knowledge of subjects such as elementary number theory, college-level calculus, basic algebra, trigonometry, inequalities, etc., and some “mathematical maturity”.

Please submit solutions to **topological[dot]musings[At]gmail.com** (remove the characters within the square brackets and replace them with the appropriate ones). You may send in your solutions in pdf, LaTeX or text format. (Though we prefer LaTeX and/or pdf submissions, we ask you not to worry too much about the format.) [Added May 15: in case of multi-part problems, please submit all the parts you intend to solve in one mailing. Credit will be awarded for each part correctly solved.]

I guess that’s it! Keep checking the blog for the next POW problem!

[**Update**: I have decided to pose at least one problem (or perhaps, two problems) a week from now and invite solutions to those problems from the readers. This should be exciting. I am sure all of you would want your names to be listed in the Problem-Solving Hall of Fame page! 8) ]

This post is about getting the readers of this blog to participate! And so, let me pose an elementary divisibility problem and invite solutions from the readers. “Elementary” doesn’t necessarily mean “easy”, by the way. It just means elementary methods can be used to solve the problem. I am particularly looking for elegant solutions, though all kinds of solutions are welcome. Readers with correct solutions will be given credit and their names will be included in the *Problem-Solving Hall of Fame* page on this blog! So, go ahead, write down your solutions.

**Problem**: Suppose and are two positive natural numbers such that is divisible by . Prove that .

The following theorem, I feel, is not very well-known, though it is a particularly useful one for solving certain types of “limit” problems. Let me pose a couple of elementary problems and offer their solutions. First, the theorem.

**Stolz-Cesàro**: Let and be two sequences of real numbers, such that is positive, strictly increasing and unbounded. Then,

,

if the limit on the right hand side exists.

The proof involves the usual method, and I will avoid presenting it here since it isn’t particularly interesting. Just as *Abel’s lemma* is the discrete analogue of *integration by parts*, the *Stolz-Cesàro theorem* may be considered the discrete analogue of *L’Hospital’s rule* in calculus.

**Problem 1**: Evaluate the limit , where .

**Solution**: One may certainly consider the above limit as a Riemann-sum which may then be transformed into the integral , which then obviously evaluates to . But, we will take a different route here.

First, let and . Then, we note that the sequence is positive, strictly increasing and unbounded. Now,

(using the binomial theorem)

.

Therefore, using the Stolz-Cesàro theorem, we conclude that the required limit is also .

Let us now look at another problem where applying the aforesaid theorem makes our job a lot easier. This problem is an example of one that is not amenable to the other usual methods of evaluating limits.

**Problem 2**: Let be integers and suppose . Given the tangent line at the point from the point to , evaluate

.

**Solution**:(This is basically the solution I had offered elsewhere a while ago; so, it’s pretty much copy/paste!)

.

So, the equation of the tangent line at the point is given by

Since the point lies on this line, we must have

The above, after squaring and some algebraic manipulation yields

, which implies . We drop the negative root because for all .

(This is where the Stolz-Cesàro theorem actually comes into play!)

Now, let and be two sequences such that and

Note that is a positive, increasing and unbounded sequence.

Therefore,

.

Therefore, by the Stolz- Cesàro theorem, we have

, and so

.

The late great Paul Erdös was not a religious man (his take on religion seems to have been fairly ironic, referring for example to God as “The Supreme Fascist”), except of course when it came to mathematics. Ever the Platonist, he considered that when he died, he might finally get a chance to gaze upon “The Book” which, as if written by God, contains the most beautiful and enlightening proofs of all theorems. The highest form of praise from Erdös for a proof was, “It’s straight from The Book!” He also said, “You don’t have to believe in God, but you should believe in The Book!”

Do you believe in The Book? I’m not sure I do!

In fact, there is this book by Aigner and Ziegler, “Proofs from The Book”. In it they include the following one-sentence proof by Don Zagier on Fermat’s two square theorem (that a prime congruent to is a sum of two squares):

A One-Sentence Proof That Every Prime p congruent to 1 modulo 4 Is a Sum of Two Squares D. Zagier Department of Mathematics, University of Maryland, College Park, MD 20742 The involution on a finite set S = {(x,y,z) \in N^3 : x^2 +4yz = p } defined by ( x+2z, z, y-x-z ) if x < y-z (x,y,z) ---> { ( 2y-x, y, x-y+z ) if y-z < x < 2y ( x-2y, x-y+z, y ) if x > 2y has exactly one fixed point, so |S| is odd and the involution defined by (x,y,z) ---> (x,z,y) also has a fixed point.

I plucked this off the Web from here; the author of the page prefaces it with a comment:

The following constitutes the essential text of a complete research article; I have omitted only some comments at the end concerning the history of this type of argument. The author reproves a famous result. He builds his proof into a single sentence as simply a tour-de-force. In fact, he has left many straightforward steps for the reader to verify. 1. As an exercise in critical reading, list all the implicit claims that the reader must verify in order to accept this argument as a proof. 2. As an exercise in logic and algebra, supply all the details necessary to support these claims. Package all this as a long-winded rewrite of Zagier's article written so that any high school algebra student could easily read it with comprehension. You should expect to expand Zagier's single sentence to a full page or more.

Um, yeah.

My own reaction to this proof: it is surely dazzling in its compression, although one’s first reaction is likely to be “WTF?!?” — what just happened here? The underlying idea is that the number of fixed points of an involution on a finite set (i.e., a function equal to its own inverse) has the same parity as itself; it follows that if has odd parity, then any involution on has at least one fixed point; such a fixed point of the involution on Zagier’s set yields a solution to , whence the theorem. So the bulk of the proof is in showing that has odd parity, by showing that his nontrivial involution has exactly one fixed point.

And I guess you can see, by staring at his casewise-defined involution for a while, that its only fixed point is where . It then remains to check that this really is a well-defined function from to , and it really is an involution. The full verification probably does take up at least a page.

It truly is a jaw-dropping proof. My problem though is that it looks like black magic. I mean, I can construct a line-by-line verification that the proof does what it purports to do, but in a deeper sense I *still don’t get it*. How Zagier cooked up this involution is a mystery to me, and unless I made a concerted effort to memorize it, it would remain unmemorable to me (that is, unless someone were to reveal the underlying mystery to me — I suspect that *that* would take a few sentences or more! Can anyone help me?).

What do you think — does it qualify as a Book proof? Me personally, I prefer proofs which are *enlightening* — arguments that I can really understand, proofs that stick, proofs I can take with me to the grave. Put it this way: if God were to write a proof which consumed an absolute minimum number of bytes in some optimal language, it still wouldn’t be much of a Book proof to me unless I (a limited human) could *really* understand it, and if it were really better in that sense than its closest competitors.

I don’t think I believe too strongly in the reality of “Book proofs”, or at least I’m skeptical that every theorem can be said to have a Book proof. Every mathematical statement and proof is embodied in some larger context or matrix of ideas, many requiring patient assimilation before a light suddenly flashes on. I tend to believe that’s the rule rather than the exception, and the idea that we should believe in a Book proof for every theorem, possessing a snappy immediacy which cries “Behold!”, is based on a dangerous and even crazy fallacy concerning the nature of mathematics.

[At the same time: we can all agree that Erdös was an absolute genius at finding Book proofs! 🙂 ]

## Recent Comments