WebPage for Dr.Z''s Math683 class

Last Update: Dec. 15, 1998.

MATH 683(Fall 1998): Integer Sequences and Famous Mathematical Constants


Steve Finch's Favorite Constants Site. and The Sloane-Plouffe Amazing Collection of Integer Sequences .


Class Room: Wachman Hall 527

Time: MW 11:40 AM-1:00 PM

Dr. Z''s Office: Computer Bldg. 530 ( Phone:204-7287)

Dr. Z''s Office Hours: MW 10:40-11:30 and by appointment


Ibrahim Al-Rashidi, Olga Alexandrov, Jennifer Helmuth, Kurt Ludwick, Jay Pathak, Marc Renault, Aaron Robertson, Akalu Tefera, and Myra Wise Bologona.


8/31/98: What are integer sequences, and what makes a mathematical constant interesting? Easy vs. Hard sequences. Example of an easy sequence: 1,1,1,1,1,1,1,... Example of a hard sequence: 1,2,6,18,?,... (Ramsey numbers R(n,n)) almost as hard, but not quite so hard: 1,4,12,36,100, ... (Self avoiding walks on the square-lattice).

9/2/98: Aaron Robtertson gave a fascinating lecture on Ramsey numbers.

9/9: How to tell whether a sequence is polynomial? (keep taking differences, and see if you make it to 0); The notion of generating function and exponential generationg function. The algebra of formal power series. Catalan numbers.

9/14: Catalan numbers continued. Proof via WZ theory. The number of labelled trees. Two proofs: Using Bosses and Employees , and another using John Majewicz's Abel-extension of WZ theory .

9/16: Starting Pattern-Avoiding words, using Steve Finch's Essay on this topic . The Thue-Morse word (0->01, 1->10) and how applying this to 0 (0,01,0110,...) yields an infinite binary cube-free word (assigned as homework). Squre-Free words. Fekete's Lemma. More homework: read and understand Ekhad and Dr. Z''s Construction , that yields the best-to-date lower bound for mu: mu>=2^(1/17).

9/21: Ibrahim Al-Rashidi talked about divisibility properties of Fibonacci numbers

9/23 and 9/28: Finshed Pattern-Avioding sequences. Proved that there exists an infinite word avoiding P iff there are such words for every length (following the excellent Ch.2 of Combinatorics on Words by Lothaire). Pop quiz about the U2-band Flashlight Microsoft puzzle. Chaitin's constant, Omega defined. Its amazing properties (complete randomness in the sense of Chaitin-Kolmogorv, and normality IN ALL BASES), pointed out. Turing's theorem about the non-existence of an algoritm for the halting problem is proved in detail. Finally we discussed whether Omega is Kosher or not. According to constructivists (which Dr. Z' is 96.598 percents of the time), it is intersting but does not exit. This inspired Dr. Z' to present a snappy and infinity-free rendition (in Maple) of Turing's Theorem.

9/30: Marc Reanault continuted Ibrahim Al-Rashidi's interesting account of the Fibonnacci numbers. See his fascinating essay on Fibonnaci numbers.

10/5: Dr. Z's briefly described his, and Shalosh's General solution of the U2-puzzle. Then he started talking about Feigenbaum's constants alpha and delta, following first Steve Finch's superb essay on this topic . We then discussed the derivation of Feigenbaum's renormalization equation g(x)=-alpha*g(g(-x/alpha)), from which alpha can be derived numerically. We followed closely the excellent exposition in Hao Bai Lin's fascinating and gripping text, `Elementary Symbolic Dynamics'.

10/7: Discussed how to find the most famous of the Feigenbaum constants, the celebrated delta. Once you know g(x) and alpha (appx. of course), you look for another function h(x), and a constant delta, solving the Linear Eigenvalue Problem:
-alpha[h(g(x/alpha))]+g'(g(x/alpha))h(x/alpha)=delta h(x)
(see HaoBai-Lin's book, p. 86).
The next topic was Pi, following Steve Finch's essay on Pi. We discussed Machin-type formulas and AGM-type formulas, and finally mentioned the Borwein-Borwein-Plouffe amazing formula for Pi.

10/12 and 10/14: Akalu Tefera and Aaron Robertson conduct A Maple tuturial for the other students.

10/19: All about Conway's constant using Steve Finch's essay on Conway's constant.

10/21: We watched the videtape of Dr. Z''s brilliant lecture at the MSRI conference that took place the previous week.

10/26: More on Pi. How to compute Pi as slowly as possible. Declarating formulas suggested by Kurt Ludwick. Then we Dr. Z' tried, without preparation to talk about counting up-down permutations, and how they can be used to computer Pi. But he got stuck. Homework: Help him out.

10/28: This time Dr. Z' got it right, and proved Andre's exponential generating function for the number of up-down permutations: sec x + tan x . From here you can compute Pi, by using either formula for the radius of convergence.

11/2: Talked about Zeta(2), ln 2, and Zeta(3). started Apery's proof of their irrationality.

11/4: Finshed Apery's proof, as conceptualized and WZ-ized by Dr. Z' in his paper: ``Closed Form (pun intended!)'' ( appeared in: Contemporaty Math. v. 143).

11/9,11/16,11/18: We talked about the Kolakoski sequence 2,2,1,1,2,1,2,2,1,2,2,1,1,... , and C-infinity words. We covered, in great detail, Arturo Capri brilliant proof that there are only finitely many C-infinity words that are squares, and more generally, for any k, there are only finitely many C-infinity words of the form uvu with length(v) less than or equal to k. We followed Capri's paper: `Om repeated factors in C-infinity words', Information Processing Letters 52(1994), 289-294.

11/23: We talked about the constant 4, namely we discussed Ken Appel and Wolfgang Haken's proof of the Four Color Theorem. We first proved the Five Color Theorem. Then we proved (half of) Lou Kauffman's theorem that 4CT is equivalent to a very reasonable statement about pairs of binary trees. We followed Robin Thomas's excellent, lively, and lucid treatment in is article in the Notices of the Amer. Math. Soc., Aug. 1998, 848-859.

11/25: We finished talking about 4CT. Then we started talking again about the extremely hard to compute sequence of Ramsey numbers R(k). Recall that in the class of 9/2/98, Aaron Rotertson proved the upper bound R(k) less than binomial(2k-2,k-1) which is roughly 4^k. We will soon prove lower bounds due to Erdos, and a `slight' improvement due to Joel Spencer.

11/30,12/2,12/7: Using Joel Spencer's charming little book: Ten Lectures on the Probablistic Method, we derived the promised lower bounds for R(k,k), as well as for the van der Waerden numbers.

Happy Holidays! See you next semester.

Student's Essays:

  1. Ibrahim Al-Rashidi's Essay on Irrationality.
  2. Mrc Renault's essay on Fibonnaci numbers.
  3. Akalu Tefera's Essay on the Catalan numbers.
  4. Myra Wise Bologona's essay on the Bell Numbers