7
$\begingroup$

It seems to me that the undergraduates I teach have particular difficulty with proofs that involve reasoning about algebraic calculations that arise only theoretically. Since I have in mind doing some pedagogical/expository writing around this issue, I want to assemble for myself as many characteristic examples as I can.

I'll give two examples now, and more on demand if it turns out I haven't made myself clear.

1) The proof of the transcendentality of $\pi$ such as one finds in Baker's Transcendental Number Theory, involves a product of many factors, each corresponding to hypothetical conjugate of $\pi$, and leading to a sum having size exponential in the hypothetical degree of $\pi$, all this to set up an application of the fundamental theorem on symmetric polynomials.

2) The proof of the Bruck-Ryser theorem on finite projective planes involves using geometry to create a hypothetical identity and then doing repeated substitutions to reduce the number of variables.

Challenges to clearly illustrating the mechanism within these two proofs include counterfactual hypotheses (for contradiction) and exponential complexity. Many of my students simply have very little feeling for what the distributive law says beyond the multiplication of two binomials, so I have a particular interest on proofs that hinge on analyzing the result of products with many factors each of which has many summands.

Thanks in advance for all contributions. Please give citations for paradigmatic proofs rather then mentioning theorems only, by name or statement. Please, if in doubt, post, but I'm particular interested in important results within the reach of advanced undergraduates and/or beginning graduate students.

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ I would like to see more examples, just so I can be on the same page. Otherwise I might suggest something like constructing the free term algebra for a (universal algebraic) variety as an example, and I do not yet know that that is what you want. If it is, that and similar examples might be found in George Bergman's Math 245 text he uses at UC Berkeley. Gerhard "Ask Me About System Design" Paseman, 2011.10.14 $\endgroup$
    – Gerhard Paseman
    Commented Oct 15, 2011 at 4:55
  • 2
    $\begingroup$ Hi Gerhard, So here's another example: the Greene-Nijenhuis-Wilf probabilistic proof of the hook formula. The proof gives a uniform generation algorithm for standard tableaux and succeeds by showing that each one occurs with probability equal to the reciprocal of the desired count. The probability gets factored as a product of conditional probabilities, which, working backwards from the expected answer, get expanded as products with many factors (the big distributive law - this gets my students lost). Finally each of the exponentially many summands gets an interpretation. $\endgroup$
    – David Feldman
    Commented Oct 15, 2011 at 6:26
  • 3
    $\begingroup$ A different sort of example: classification of modules over a PID by means of describing the contingencies in a theoretical sequence of matrix manipulations. What interests me: if our curricula don't emphasize pencil-and-paper computations on examples on substantial size, have we prepared students to understand theoretical narratives that reference such computations? $\endgroup$
    – David Feldman
    Commented Oct 15, 2011 at 6:29
  • 1
    $\begingroup$ I think many mathematicians aren't very good with these either. For the most part, only combinatorialists and certain kinds of analysts really need this skill on a regular basis. Some mathematicians might even argue that part of the progress of mathematics is abstracting away calculations. $\endgroup$
    – Alexander Woo
    Commented Oct 15, 2011 at 6:58
  • 1
    $\begingroup$ David: Can you specify what the problem is exactly: (a) They don't understand arguments about calculations when you show them such arguments, or (b) They can't come up with such arguments on their own? And (1) is the problem specific to proofs by contradiction or (2) is it only exacerbated by the fact that they can't get an example to work with? In case (1), I suggest dividing the proofs up in modular pieces in such a way that the reasoning-about-calculations part is contained inside those pieces which are not proofs-by-contradictions but, instead, honest-to-god and constructive ... $\endgroup$
    – darij grinberg
    Commented Oct 15, 2011 at 16:45

2 Answers 2

Reset to default
5
$\begingroup$

A very elementary example (simpler than the ones you've given) is the generating function for the number of partitions of $n$, denoted $p_n$: $$\sum_{n\geq 0} p_n q^n = \prod_{i\geq 0} \frac{1}{1-q^i}.$$

Improve this answer
$\endgroup$
1
  • $\begingroup$ Actually I'd thought over including this and even combinatorial identities that follow from manipulating such expressions. $\endgroup$
    – David Feldman
    Commented Oct 15, 2011 at 23:03
5
$\begingroup$

I'm going to define the characteristic polynomial to my students next monday, and I'm going to tell them about its degree and three special coefficients. The constant coefficient is trivial by evaluation at zero. For both others and the degree, the reasoning is an example of what you ask, if I got your question right.

I will write the determinant on the board (written with parenthesis because I don't remember how to make the straight lines...): $$\begin{pmatrix}a_{1,1}-X & a_{1,2} & \dots \\\ a_{2,1} & a_{2,2}-X & \dots \\\ \dots & \dots & \dots \end{pmatrix}$$ and consider the development along the first column : the first term is $a_{1,1}-X$ times a cofactor which looks the same as the original determinant, and all others will have lost two terms of the form $\text{something}-X$ so will at least two lower in degree. That means if I were to really develop the determinant, it would end up looking like $(a_{1,1}-X)\dots(a_{n,n}-X)+\text{at most degree}(n-2)$, so the characteristic polynomial is degree $n$, its dominant coefficient is $(-1)^n$, and the coefficient just behind will be $(-1)^{n-1}\rm{Tr}(A)$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ If I recall, commutative algebra abounds with arguments where one needs to see that a quantity defined, perhaps, by a determinant, or by something even more complicated, sits in a certain ideal, perhaps up to some dominant term. The subject isn't fresh enough in my mind for me to narrow down to the killer examples. $\endgroup$
    – David Feldman
    Commented Oct 15, 2011 at 23:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .