Assignment #8

Assignment due in lecture on Friday, March 7.

Thanks to everyone for properly crediting ideas from other sources. Even so there have been many original solutions.

For this assignment and the next I'd appreciate it if you could solve the problems independently. There will not be too many problems. Questions in office hours are still welcome.

To hand in:

AA-2¹, AA-5, AA-6;

BB-1 (below);

CC-3.

Problem BB-1. Choose four finite algebras ${\cal A}$, as described below. For each, make free algebras $F _ {{\cal A}}(n)$ for $n=1,2,..$. Stop when they get too large to be calculated within a couple of minutes. Report your findings about size, in comparison with the theoretical bound of $\vert A\vert ^ {\vert A\vert ^ n}$. You should see some examples of ``combinatorial explosion''--the tendency of combinatorial problems to get too large fast.

For the program: While logged into a MathNet UNIX host such as oak, do

cd ~baker/free/examples

Listing using ls, you should see a number of files representing algebras.

The elements of an algebra are named $0,1,2,\dots$. Each file has an indication of the size of the algebra and one or more operations. An operation is indicated by an arity and then a list of values, however many are needed, arranged into one or more tables for clarity. To view a file, use an editor or the more program.

To find $F _ {{\cal A}}(2)$, where ${\cal A}$ is Murskii's algebra, for example, just use the command

free -g2 murskii

Rows of the resulting output are numbered $0,1,2\dots$. Each row has a notation as to how it was calculated from previous rows, where the operations are named A, B, C, etc. By tracing back, you could represent each row by an appropriate expression in the generators $x,y,\dots$, but you are not asked to do so. The last line summarizes the number of rows.