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 $\displaystyle \sum_{k = 0}^\infty \frac1{\binom{n+k}{k}}$ for $n > 1$.

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”:

1. Every finite Boolean algebra $B$ is obtained from a finite set $X$ by taking its power set (or set of functions $\hom(X, \mathbf{2})$ from $X$ to $\mathbf{2}$, with the Boolean algebra structure it inherits “pointwise” from $\mathbf{2} = \{0, 1\}$). The set $X$ may be defined to be $\mbox{Bool}(B, \mathbf{2})$, the set of Boolean algebra homomorphisms from $B$ to $\mathbf{2}$.
2. Conversely, every finite set $X$ is obtained from the Boolean algebra $B = \hom(X, \mathbf{2})$ by taking its “hom-set” $\mbox{Bool}(B, \mathbf{2})$.

More precisely, there are natural isomorphisms

$i_B: B \stackrel{\sim}{\to} \hom(\mbox{Bool}(B, \mathbf{2}), \mathbf{2}),$

$j_X: X \stackrel{\sim}{\to} \mbox{Bool}(\hom(X, \mathbf{2}), \mathbf{2})$

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 $S$ of letters $x, y, z, \ldots$, consider the Boolean algebra $\mathbf{B}(S)$ whose elements are logical equivalence classes of formulas you can build up from the letters using the Boolean connectives $\wedge, \vee, \neg$ (and the Boolean constants $0, 1$), where two formulas $\phi, \phi'$ are defined to be logically equivalent if $\phi \leq \phi'$ and $\phi' \leq \phi$ 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 $A$ 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 $f: S \to A$ from the set of letters to $A$ as modeling or interpreting the atomic formulas $x, y, z, \ldots$ as elements $f(x), f(y), f(z), \ldots$ of $A$. The essential property of the free Boolean algebra is that we can extend this interpretation $f$ in a unique way to a Boolean algebra map $\mathbf{B}(S) \to A$. The way this works is that we map a formula like $(x \wedge \neg y) \vee z$ to the obvious formula $(f(x) \wedge \neg f(y)) \vee f(z)$. This is well-defined on logical equivalence classes of formulas because if $p = q$ in $\mathbf{B}(S)$, i.e., if the equality is derivable just from the Boolean algebra axioms, then of course $f(p) = f(q)$ holds in $A$ as the Boolean algebra axioms hold in $A$. Thus, there is a natural bijective correspondence between functions $S \to A$ and Boolean algebra maps $\mathbf{B}(S) \to A$; to get back from a Boolean algebra map $\mathbf{B}(S) \to A$ to the function $S \to A$, simply compose the Boolean algebra map with the function $S \to \mathbf{B}(S)$ which interprets elements of $S$ as equivalence classes of atomic formulas in $\mathbf{B}(S)$.

To get a better grip on $\mathbf{B}(S)$, 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., $(x + y) \cdot z$ and the like). In other words, the elements of $\mathbf{B}(S)$ can be considered as “polynomials” in the variables $x, y, z, \ldots$. Actually, there are some simplifying features of this polynomial algebra; for one thing, in Boolean rings we have idempotence. This means that $p^n = p$ for $n \geq 1$, and so a monomial term like $x^3 y^2$ reduces to its support $x y$. Since each letter appears in a support with exponent 0 or 1, it follows that there are $2^{|S|}$ possible supports or Boolean monomials, where $|S|$ denotes the cardinality of $S$.

Idempotence also implies, as we saw last time, that $b + b = 0$ for all elements $b \in \mathbf{B}(S)$, so that our polynomials = $\mathbb{Z}$-linear combinations of monomials are really $\mathbb{Z}_2$-linear combinations of Boolean monomials or supports. In other words, each element of $\mathbf{B}(S)$ is uniquely a linear combination

$\sum_{\sigma \in \mbox{supp}(S)} a_\sigma \sigma$ where $a_\sigma \in \{0, 1\},$

i.e., the set of supports $\mbox{supp}(S)$ forms a basis of $\mathbf{B}(S)$ as a $\mathbb{Z}_2$-vector space. Hence the cardinality of the free Boolean ring is $2^{|\mbox{supp}(S)|} = 2^{2^{|S|}}$.

• 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 = $\mathbb{Z}_2$-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

$i: \mathbf{B}(S) \stackrel{\sim}{\to} \hom(\mbox{Bool}(\mathbf{B}(S), \mathbf{2}), \mathbf{2})$

where $\mbox{Bool}(\mathbf{B}(S), \mathbf{2})$ is the set of Boolean algebra maps $\mathbf{B}(S) \to \mathbf{2}$. However, the freeness property says that these maps are in bijection with functions $S \to \mathbf{2}$. What are these functions? They are just truth-value assignments for the elements (atomic formulas, or variables) $x, y, z, \ldots \in S$; there are again $2^{|S|}$ many of these. This leads to the method of truth tables: each formula $b \in \mathbf{B}(S)$ induces (in one-one fashion) a function

$i(b): \mbox{Bool}(\mathbf{B}(S), \mathbf{2}) \to \mathbf{2}$

which takes a Boolean algebra map $\phi: \mathbf{B}(S) \to \mathbf{2}$, aka a truth-value assignment for the variables $x, y, z, \ldots$, to the element of $\{0, 1\}$ obtained by instantiating the assigned truth values $0, 1$ for the variables and evaluating the resulting Boolean expression for $b$ in $\mathbf{2}$. (In terms of power sets,

$\mathbf{B}(S) \cong P(\mbox{Bool}(\mathbf{B}(S), \mathbf{2}))$

identifies each equivalence class of formulas $b \in \mathbf{B}(S)$ with the set of truth-value assignments of variables which render the formula $b$ “true” in $\{0, 1\}$.) The fact that the representation $b \mapsto i(b)$ is injective means precisely that if formulas $b, c$ 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 $b$ is logically equivalent to $\top$, or $b = \top$ in $\mathbf{B}(S)$ if this is derivable from the Boolean algebra axioms). On the semantic side, each Boolean algebra homomorphism $\phi: \mathbf{B}(S) \to \mathbf{2}$ can be regarded as a model of $\mathbf{B}(S)$ in which each formula becomes true or false under $\phi$. The method of truth tables then says that there are enough models or truth-value assignments to detect provability of formulas, i.e., $b$ is provable if it is true when interpreted in any model $\phi$. This is precisely what is meant by a completeness theorem.

There are still other ways of thinking about this. Let $\phi: B \to \mathbf{2}$ be a Boolean algebra map, aka a model of $B$. This model is completely determined by

• The maximal ideal $\phi^{-1}(0)$ in the Boolean ring $B$, or
• The maximal filter or ultrafilter $\phi^{-1}(1)$ in $B$.

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

• A model of a finite Boolean algebra $B$ is specified by a unique atom of $B$.

Thus, baby Stone duality asserts a Boolean algebra isomorphism

$i: B \to P(\mbox{Atoms}(B)).$

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

$x \wedge y \wedge z, x \wedge y \wedge \neg z, x \wedge \neg y \wedge z, x \wedge \neg y \wedge \neg z,$

$\neg x \wedge y \wedge z, \neg x \wedge y \wedge \neg z, \neg x \wedge \neg y \wedge z, \neg x \wedge \neg y \wedge \neg z.$

According to baby Stone duality, any element in the free Boolean algebra (with $2^8 = 256$ 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 $\mathbb{Z}_2$-vector space. For example, as an exercise one may calculate

$(x \Rightarrow y) \wedge z = x \wedge y \wedge z + \neg x \wedge y \wedge z + \neg x \wedge \neg y \wedge z.$

The unique expression of an element $b \in \mathbf{B}(S)$ (where $b$ is given by a Boolean formula) as a $\mathbb{Z}_2$-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 $B$ which is generated by finitely many elements $x_1, x_2, \ldots, x_n \in B$. Generated means that every element in $B$ can be expressed as a Boolean combination of the generating elements. In other words, “generated” means that if we consider the inclusion function $S = \{x_1, \ldots, x_n\} \hookrightarrow B$, then the unique Boolean algebra map $\phi: \mathbf{B}(S) \to B$ which extends the inclusion is a surjection. Thinking of $\phi$ as a Boolean ring map, we have an ideal $I = \phi^{-1}(0)$, and because $\phi$ is a surjection, it induces a ring isomorphism

$B \cong \mathbf{B}(S)/I.$

The elements of $I$ can be thought of as equivalence classes of formulas which become false in $B$ under the interpretation $\phi$. Or, we could just as well (and it may be more natural to) consider instead the filter $F = \phi^{-1}(1)$ of formulas in $\mathbf{B}(S)$ which become true under the interpretation $\phi$. In any event, what we have is a propositional language $\mathbf{B}(S)$ consisting of classes of formulas, and a filter $F \subseteq \mathbf{B}(S)$ consisting of formulas, which can be thought of as theorems of $B$. Often one may find a filter $F$ described as the smallest filter which contains certain chosen elements, which one could then call axioms of $B$.

In summary, any propositional theory (which by definition consists of a set $S$ of propositional variables together with a filter $F \subseteq \mathbf{B}(S)$ of the free Boolean algebra, whose elements are called theorems of the theory) yields a Boolean algebra $B = \mathbf{B}(S)/F$, where dividing out by $F$ means we take equivalence classes of elements of $\mathbf{B}(S)$ under the equivalence relation $b \sim c$ defined by the condition “$b \Leftrightarrow c$ belongs to $F$“. The partial order on equivalence classes [$b$] is defined by [$b$] $\leq$ [$c$] iff $b \Rightarrow c$ belongs to $F$. The Boolean algebra $B$ defined in this way is called the Lindenbaum algebra of the propositional theory.

Conversely, any Boolean algebra $B$ with a specified set of generators $x_1, \ldots x_n$ can be thought of as the Lindenbaum algebra of the propositional theory obtained by taking the $x_i$ as propositional variables, together with the filter $\phi^{-1}(1)$ obtained from the induced Boolean algebra map $\phi: \mathbf{B}(S) \to B$. A model of the theory should be a Boolean algebra map $\mathbf{B}(S) \to \mathbf{2}$ which interprets the formulas of $\mathbf{B}(S)$ 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

$B \cong \mathbf{B}(S)/F \to \mathbf{2}.$

i.e., we may identify a model of a propositional theory with a Boolean algebra map $f: B \to \mathbf{2}$ out of its Lindenbaum algebra.

So the set of models is the set $\mbox{Bool}(B, \mathbf{2})$, and now baby Stone duality, which gives a canonical isomorphism

$i: B \cong \hom(\mbox{Bool}(B, \mathbf{2}), \mathbf{2}),$

implies the following

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

Proof: Let $B$ be the Lindenbaum algebra of the theory, and let $b = [p] \in B$ be the class of formulas provably equivalent to a given formula $p$ under the theory. The Boolean algebra isomorphism $i$ takes an element $b \in B$ to the map $\phi \mapsto \phi(b)$. If $\phi(b) = 1$ for all models $\phi$, i.e., if $i(b) = 1$, then $b = 1$. But then [$p$] $= 1$, i.e., $p \in F$, the filter of provable formulas. $\Box$

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 $\mbox{Bool}(B, \mathbf{2})$ 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:

1. Consider a rectangle with sides of integer lengths $a$ and $b$, subdivided into $ab$ unit squares, and a diagonal line from corner to corner. Show that the number of unit squares that the line crosses is $a+b-\gcd(a,b)$. (Count only those cases where the line crosses the interior of a square.)
2. What would be the $n$-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 $a = (a_1, ... , a_n)$ be the vector of box sidelengths, and $n(a)$ the number of boxes crossed by the diagonal going from 0 to a. Then we claim

$n(a) = \sum_{S \subseteq [n], S \neq \emptyset } (-1)^{|S| - 1} \gcd(\{a_i\}_{i \in S})$

where $|S|$ denotes the cardinality of a set $S$. [Note that for $n=2$, this simplifies to $n(a) = a_1 + a_2 - \gcd(a_1,a_2)$, the result of part 1.]

Proof: Parametrize the diagonal by the function $f(t) = ta$ for $t \in [0,1]$, and let $f_i(t)$ denote the $i^{th}$ coordinate of $f(t)$. Defining [$n$] $= \{1,2, \ldots, n\}$, we have

$n(a) = | \{t \in [0,1) : f_i(t) \in \mathbb{Z} \mbox{ for some } i \in [n]\} |.$

[Proof: let $T = \{t_0 = 0$ < $t_1$ < …$t_n$ < $1\}$ be the set on the right-hand side. Each $t_i$ corresponds to an interval $(t_i, t_{i+1})$ 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 $t_i$‘s and boxes crossed.]

For $i = 1, \ldots, n$, let $A_i = \{t \in [0,1) : f_i(t) \in \mathbb{Z}\}$. Then

$n(a) = | T | = | \bigcup_{i \in [n]} A_i | = \sum_{S \subseteq [n]} (-1)^{|S| - 1} | \bigcap_{i \in S} A_i |$

by the inclusion-exclusion principle, so we need only verify that $| \bigcap_{i \in S} A_i | = \gcd(\{a_i\}_{i \in S})$. Indeed, given $t$, $ta_i$ will be an integer for all $i \in S$ if and only if $t = k/gcd(\{a_i\}_{i \in S})$ for $k = 0, 1..., \gcd(\{a_i\}_{i \in S})-1$, i.e. for $\gcd(\{a_i\}_{i \in S})$ different values of $k$. $\Box$

Remarks: Philipp Lampe notes that the case $n = 3$ 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 $n$, 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 $a$ and $b$, subdivided into $ab$ unit squares, and a diagonal line from corner to corner. Show that the number of unit squares that the line crosses is $a+b-\gcd(a,b)$. (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 $n$-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 $x$ and $y$ are two positive natural numbers such that $x^2 + xy + 1$ is divisible by $y^2 + xy + 1$. Prove that $x = y$.

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 $(a_n)_{n \ge 1}$ and $(b_n)_{n \ge 1}$ be two sequences of real numbers, such that $(b_n)$ is positive, strictly increasing and unbounded. Then,

$\displaystyle \lim_{n \to \infty} \frac{a_n}{b_n} = \lim_{n \to \infty} \frac{a_{n+1} - a_n}{b_{n+1} - b_n}$,

if the limit on the right hand side exists.

The proof involves the usual $\epsilon - \delta$ 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 $\displaystyle \lim_{n \to \infty} \frac{1^k + 2^k + \ldots + n^k}{n^{k+1}}$, where $k \in \mathbb{N}$.

Solution: One may certainly consider the above limit as a Riemann-sum which may then be transformed into the integral $\displaystyle \int_0^1 x^k \, dx$, which then obviously evaluates to $1/(k+1)$. But, we will take a different route here.

First, let $a_n = 1^k + 2^k + \ldots + n^k$ and $b_n = n^{k+1}$. Then, we note that the sequence $(b_n)$ is positive, strictly increasing and unbounded. Now,

$\displaystyle \lim_{n \to \infty} \frac{a_{n+1} - a_n}{b_{n+1} - b_n} = \lim_{n \to \infty} \frac{(n+1)^k}{(n+1)^{k+1} - n^{k+1}}$

$\displaystyle = \lim_{n \to \infty} \frac{(n+1)^k}{\left(1 + \binom{k+1}{1}n + \binom{k+1}{2}n^2 + \ldots + \binom{k+1}{k}n^k + n^{k+1}\right) - n^{k+1}}$

(using the binomial theorem)

$\displaystyle = \lim_{n \to \infty} \frac{(n+1)^k / n^k}{\left(1 + \binom{k+1}{1}n + \binom{k+1}{2}n^2 + \ldots + \binom{k+1}{k}n^k \right) / n^k}$

$\displaystyle = \lim_{n \to \infty} \frac{(1 + 1/n)^k}{\binom{k+1}{k}} = \frac1{k+1}$.

Therefore, using the Stolz-Cesàro theorem, we conclude that the required limit is also $1/(k+1)$.

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 $k\geq 2$ be integers and suppose $C: y = \sqrt {2x + 1}\ (x > 0)$. Given the tangent line at the point $(a_{k},\, \sqrt {2a_{k} + 1})$ from the point $(0, k)$ to $C$, evaluate

$\displaystyle \lim_{n\to\infty}\frac {1}{n^{3}}\sum_{k = 2}^{n}a_{k}$.

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

$\displaystyle y = \sqrt {2x + 1}\Rightarrow \frac {dy}{dx} = \frac {1}{\sqrt {2x + 1}}$.

So, the equation of the tangent line at the point $(a_{k}, \sqrt {2a_{k} + 1})$ is given by

$\displaystyle y - \sqrt {2a_{k} + 1} = \frac {1}{\sqrt {2a_{k} + 1}}(x - a_{k}).$

Since the point $(0,k)$ lies on this line, we must have

$\displaystyle k - \sqrt {2a_{k} + 1} = \frac {1}{\sqrt {2a_{k} + 1}}( - a_{k})$

The above, after squaring and some algebraic manipulation yields
$a_{k}^{2} + 2(1 - k^{2})a_{k} + 1 - k^{2} = 0$, which implies $a_{k} = (k^{2} - 1) + k(\sqrt {k^{2} - 1})$. We drop the negative root because $a_{k} > 0$ for all $k\ge 2$.

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

Now, let $(b_{n})$ and $(c_{n})$ be two sequences such that $\displaystyle b_{n} = \sum_{k = 2}^{n}a_{k}$ and $c_{n} = n^{3}.$
Note that $(c_{n})$ is a positive, increasing and unbounded sequence.

Therefore, $\displaystyle \lim_{n\to \infty}\frac {b_{n + 1} - b_{n}}{c_{n + 1} - c_{n}} = \lim_{n\rightarrow \infty}\frac {\sum_{k = 2}^{n + 1}a_{k} - \sum_{k = 2}^{n}a_{k}}{(n + 1)^{3} - n^{3}} = \lim_{n\rightarrow \infty}\frac {a_{n + 1}}{3n^{2} + 3n + 1}$

$\displaystyle = \lim_{n\to \infty}\frac {(n + 1)^{2} - 1 + (n + 1)\sqrt {(n + 1)^{2} - 1}}{3n^{2} + 3n + 1}$

$\displaystyle = \lim_{n \to \infty} \frac{(1 + 1/n)^2 - 1/n^2 + (1 + 1/n)\sqrt{1 + 2/n}}{3 + 3/n + 1/n^2}$

$= 2/3$.

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

$\displaystyle \lim_{n\to \infty}\frac {b_{n}}{c_{n}} = 2/3 \,$, and so

$\displaystyle \lim_{n\to \infty}\frac {1}{n^{3}}\sum_{k = 2}^{n}a_{k} = 2/3$.

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 $1 \pmod 4$ 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

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 $f: S \to S$ on a finite set $S$ (i.e., a function $f$ equal to its own inverse) has the same parity as $S$ itself; it follows that if $S$ has odd parity, then any involution on $S$ has at least one fixed point; such a fixed point of the involution $(x, y, z) \leftrightarrow (x, z, y)$ on Zagier’s set $S$ yields a solution $(x, y)$ to $x^2 + 4y^2 = p$, whence the theorem. So the bulk of the proof is in showing that $S$ 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 $(x, y, z) = (1, 1, n)$ where $p = 4n+1$. It then remains to check that this really is a well-defined function from $S$ to $S$, 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! 🙂 ]

• 357,711 hits