## Typeset trees using TikZ/PGF

Some combinatorial trees typeset using TikZ/PGF. The Linux filesystem hierarchy:

\begin{tikzpicture} [-,thick] \footnotesize \node {\texttt{/}} [edge from parent fork down] child {node {\texttt{bin}}} child {node {\texttt{etc}}} child {node {\texttt{home}} child {node {\texttt{anne}}} child {node {\texttt{sam}}} child {node {$\dots$}} } child {node {\texttt{lib}}} child {node {\texttt{opt}}} child {node {\texttt{proc}}} child {node {\texttt{tmp}}} child {node {\texttt{usr}} child {node {\texttt{bin}} child {node {\texttt{acyclic}}} child {node {\texttt{diff}}} child {node {\texttt{dot}}} child {node {\texttt{gc}}} child {node {\texttt{neato}}} child {node {$\dots$}} } child {node {\texttt{include}}} child {node {\texttt{local}}} child {node {\texttt{share}}} child {node {\texttt{src}}} child {node {$\dots$}} } child {node {$\dots$}}; \end{tikzpicture}

Classification tree of organisms:

\begin{tikzpicture} [sibling distance=6cm,-,thick] \footnotesize \node {organism} child {node {plant} [sibling distance=2cm] child {node {tree} child {node {deciduous}} child {node {evergreen}} } child {node {flower}} } child {node {animal} [sibling distance=2.5cm] child {node {invertebrate}} child {node {vetebrate} [sibling distance=4.7cm] child {node {bird} [sibling distance=1.5cm] child {node {finch}} child {node {rosella}} child {node {sparrow}} } child {node {mammal} [sibling distance=1.5cm] child {node {dolphin}} child {node {human}} child {node {whale}} } } }; \end{tikzpicture}

The Bernoulli family tree of mathematicians:

\begin{tikzpicture} [-,thick,% every node/.style={shape=rectangle,inner sep=3pt,draw,thick}] \footnotesize \node {Nikolaus senior} [edge from parent fork down] [sibling distance=4cm] child {node {Jacob}} child {node {Nicolaus} child {node {Nicolaus I}} } child {node {Johann} [sibling distance=2cm] child {node {Nicolaus II}} child {node {Daniel}} child {node {Johann II} child {node {Johann III}} child {node {Daniel II}} child {node {Jakob II}} } }; \end{tikzpicture}

An expression tree:

\begin{tikzpicture} [-,thick] \node {$+$} [sibling distance=2.5cm] child {node {$\times$} [sibling distance=1cm] child {node {$a$}} child {node {$a$}} } child {node {$\times$} [sibling distance=1cm] child {node {$2$}} child {node {$a$}} child {node {$b$}} } child {node {$\times$} [sibling distance=1cm] child {node {$b$}} child {node {$b$}} }; \end{tikzpicture}

## Simple graphs, bridges of Konigsberg and directed graphs

Some combinatorial graphs drawn using TikZ/PGF. The seven bridges of Konigsberg:

\begin{tikzpicture} [lineDecorate/.style={-,thick},% nodeDecorate/.style={shape=circle,inner sep=2pt,draw,thick}] %% nodes or vertices \foreach \nodename/\x/\y/\direction/\navigate in { a/0/0/left/west, b/0/2/left/west, c/0/4/left/west, d/4/2/right/east} { \node (\nodename) at (\x,\y) [nodeDecorate] {}; \node [\direction] at (\nodename.\navigate) {\footnotesize$\nodename$}; } %% edges or lines \path \foreach \startnode/\endnode in {a/d, b/d, c/d} { (\startnode) edge[lineDecorate] node {} (\endnode) } \foreach \startnode/\endnode in {a/b, b/c, c/b, b/a} { (\startnode) edge[lineDecorate,bend left] node {} (\endnode) }; \end{tikzpicture}

A house graph:

\begin{tikzpicture} [lineDecorate/.style={-,thick},% nodeDecorate/.style={shape=circle,inner sep=2pt,draw,thick}] %% nodes or vertices \foreach \nodename/\x/\y/\direction/\navigate in { a/0/5/above/north, b/2/3/right/east, e/-2/3/left/west, c/2/0/right/east, d/-2/0/left/west} { \node (\nodename) at (\x,\y) [nodeDecorate] {}; \node [\direction] at (\nodename.\navigate) {\footnotesize$\nodename$}; } %% edges or lines \path \foreach \startnode/\endnode in {a/b, b/c, b/e, c/d, d/e, e/a} { (\startnode) edge[lineDecorate] node {} (\endnode) }; \end{tikzpicture}

\begin{tikzpicture} [nodeDecorate/.style={shape=circle,inner sep=1pt,draw,thick}] %% nodes or vertices \foreach \nodename/\x/\y in {v_1/4/0, v_2/0/0, v_3/0/3, v_4/4/3, v_5/7/1.5} { \node (\nodename) at (\x,\y) [nodeDecorate] {\scriptsize$\nodename$}; } %% edges or lines \tikzstyle{EdgeStyle}=[->,>=stealth,thick] \tikzstyle{LabelStyle}=[fill=white] \foreach \startnode/\endnode/\bend/\weight in { v_1/v_2/bend left/1, v_1/v_3/bend left/3, v_2/v_3/bend left/1, v_2/v_4/bend left/3, v_3/v_1/bend left/1, v_3/v_2/bend left=0/2, v_3/v_4/bend left/1, v_4/v_1/bend left=0/3, v_4/v_5/bend left/2, v_5/v_1/bend left=0/3, v_5/v_1/bend left/6, v_5/v_4/bend left/1} { \scriptsize \Edge[label=$\weight$,style=\bend](\startnode)(\endnode) } \end{tikzpicture}

## QED symbol for end of proof

The amssymb package defines a default Halmos symbol that automatically appears when you use the proof environment. That default Halmos symbol is . But if you want that to be filled with black, you could redefine the Halmos symbol. Put the following in your preamble:

\renewcommand{\qed}{\hfill \mbox{\raggedright \rule{0.1in}{0.1in}}}

Better still, you could customize what symbol you want to use as your QED symbol. Just replace the macro \rule{0.1in}{0.1in} with the the symbol of your choice.

## Compiling Sage on Linux and Mac OS X

Compiling Sage can be a difficult process. The difficulty is compounded by the many versions of the GNU/Linux and Mac OS X operating systems. In this post, I don’t want to cover every possible ways of compiling Sage on each operating system. My goal here is to provide a general overview of how to compile Sage on Ubuntu 10.10 and Mac OS X 10.6.x.

**Ubuntu 10.10**

For Linux, it should be sufficient to explain how to compile Sage under Ubuntu. The following commands were tested under Ubuntu 10.10. First, make sure you have the necessary tools for compiling Sage. To install these tools, execute the following command from a terminal window:

$ sudo apt-get install build-essential gfortran m4 readline-common libreadline-dev

Suppose you have downloaded the Sage source distribution and it is saved as the file named sage-x.y.z.tar. The file extension “.tar” signifies that sage-x.y.z.tar is a tar archive, also called a tar file or a tarball. To compile Sage, you need to launch a terminal window, extract the Sage source files from the tarball, and use development tools that come with Ubuntu to compile Sage. Suppose the Sage source tarball is located at

/home/username/sage-x.y.z.tar

where “username” is your username, the one you use to login to your Ubuntu system; you should replace “username” your actual username. Say you want to compile Sage under the directory /home/username/. From your terminal window, navigate to your home directory and extract the source tarball:

$ cd $ tar -xf sage-x.y.z.tar

which will produce a directory called

/home/username/sage-x.y.z/

that contains all the packages that are distributed with the Sage source distribution. You are now ready to compile Sage as contained under the latter directory. Note that you can rename the latter directory to, say, /home/username/mysage/ as follows:

$ mv sage-x.y.z mysage

If you have a directory, say, /home/username/bin/ and you want to extract the Sage source tarball to that directory, you can do so as follows:

$ tar -xf sage-x.y.z.tar -C /home/username/bin

Here, it is assumed that you want to compile the Sage source as contained under

/home/username/sage-x.y.z/

This top-level directory is usually referred to as SAGE_ROOT and is where the compiled version of Sage resides. The next step is to navigate to the latter directory and start the automated compilation process:

$ cd /home/username/sage-x.y.z/ $ make

Usually, that is all you need to do. The rest of the compilation process is non-interactive and takes at most a few hours, depending on your system.

Note that compiling Sage is very taxing on your system’s resources, i.e. CPU, RAM, disk space, and so on. Make sure you have sufficient system resources; for example, you could close all running applications and ensure you have at least 2 GB of free disk space for Sage. Furthermore, the compilation process can take from a dozen or so minutes to a few hours, depending on your system’s hardware and how you customized the compilation process. By default, the compilation process uses one thread to compile Sage, which means that every component is compiled one after the other, i.e. serial compilation. Serial compilation of Sage is known to take up to an hour or more to complete.

On a multi-core or multi-CPU system, the compilation process can be parallelized. This means that many components of Sage can be compiled in parallel, hence reducing the time it takes for the compilation process to complete. The general steps to compile Sage in parallel are as follows. Determine the number of cores on your system and decide on how many threads you want to devote to a parallel compilation of Sage. On Ubuntu, detailed information about your system’s CPU is contained in the file

/proc/cpuinfo

Read through that file to determine the number of cores on your system. Say your system has two cores and you want to use two threads for compiling Sage in parallel. Then the necessary setup to compile Sage with two threads is:

$ SAGE_PARALLEL_SPKG_BUILD="yes"; export SAGE_PARALLEL_SPKG_BUILD $ MAKE="make -j2"; export MAKE $ make

This should initiate the process of compiling Sage in parallel. If your system allows for compiling Sage with more threads, e.g. 4 or 8 threads, then change “-j2” to “-j4” or “-j8” accordingly.

Once all components of Sage are successfully compiled, the compilation process will automatically build the HTML version of the Sage standard documentation. This documentation includes a tutorial, an FAQ, a collection of thematic tutorials, a reference manual, an installation guide, among other documents. Building the HTML version of the Sage standard documentation does not require . However, for best results, it is recommended that you have installed on your system. Furthermore, is a prerequisite for building the PDF version of the Sage standard documentation. The following command installs the full distribution that comes with Ubuntu:

$ sudo apt-get install texlive-full

This will also install necessary tools for building both the HTML and PDF versions of the Sage documentation. To manually build the HTML version of the documentation, do the following from within the SAGE_ROOT directory:

$ ./sage -docbuild all html # or $ ./sage -docbuild --no-pdf-links all html

To build the PDF version of the documentation, do

$ ./sage -docbuild all pdf

For further options to customize your build of the Sage standard documentation, see the output of the following command:

$ ./sage -docbuild

You can also download the documentation from

http://www.sagemath.org/help.html

or view it online at

To customize the compilation process to your particular needs, refer to the file

SAGE_ROOT/Makefile

Once the compilation process completes, there is no separate installation process for your newly compiled Sage. You can think of Sage as being compiled and installed under SAGE_ROOT. To begin using your freshly compiled version of Sage, navigate to SAGE_ROOT and launch Sage as follows:

$ cd /home/username/sage-x.y.z/ $ ./sage

**Mac OS X 10.6.x**

For Mac OS X, most of the prerequisites for compiling Sage are bundled with XCode, which is freely available from Apple’s website. Install XCode as directed by Apple’s installation instructions and download the latest Sage stable source distribution from the Sage website. If you have XCode installed on your system, then the following commands should not result in any errors:

$ which gcc /usr/bin/gcc $ which g++ /usr/bin/g++ $ which make /usr/bin/make $ which m4 /usr/bin/m4 $ which perl /usr/bin/perl $ which tar /usr/bin/tar $ which ranlib /usr/bin/ranlib

Suppose you have downloaded the Sage source distribution and it is saved as the file named sage-x.y.z.tar. The file extension “.tar” signifies that sage-x.y.z.tar is a tar archive, also called a tar file or a tarball. To compile Sage, you need to launch a terminal window, extract the Sage source files from the tarball, and use tools that come with XCode to compile Sage. A terminal window or a console is usually launched when you run the program Terminal, which is found at

/Applications/Utilities/Terminal.app

under Mac OS X 10.4.x. For Mac OS X 10.5.x and 10.6.x, use the application finder to locate Terminal and then launch Terminal. Suppose the Sage source tarball is located at

/Users/username/sage-x.y.z.tar

where “username” is your username, the one you use to login to your Mac OS X system; replace “username” with your actual username. Say you want to compile Sage under the directory /Users/username/. From your terminal window, navigate to your home directory and extract the source tarball:

$ cd $ tar -xf sage-x.y.z.tar

which will produce a directory called

/Users/username/sage-x.y.z/

that contains all the packages that are distributed with the Sage source distribution. You are now ready to compile Sage as contained under the latter directory. Note that you can rename the latter directory to, say, /Users/username/mysage/ as follows:

$ mv sage-x.y.z mysage

If you have a directory, say, /Users/username/bin/ and you want to extract the Sage source tarball to that directory, you can do so as follows:

$ tar -xf sage-x.y.z.tar -C /Users/username/bin

Here, it is assumed that you want to compile the Sage source as contained under

/Users/username/sage-x.y.z/

This top-level directory is usually referred to as SAGE_ROOT and is where the compiled version of Sage resides. The next step is to navigate to the latter directory and start the automated compilation process:

$ cd /Users/username/sage-x.y.z/ $ make

Usually, that is all you need to do. The rest of the compilation process is non-interactive and takes at most a few hours, depending on your system.

Note that compiling Sage is very taxing on your system’s resources, i.e. CPU, RAM, disk space, and so on. Make sure you have sufficient system resources; for example, you could close all running applications and ensure you have at least 2 GB of free disk space for Sage. Furthermore, the compilation process can take from a dozen or so minutes to a few hours, depending on your system’s hardware and how you customized the compilation process. By default, the compilation process uses one thread to compile Sage, which means that every component is compiled one after the other, i.e. serial compilation. Serial compilation of Sage is known to take up to an hour or more to complete.

On a multi-core or multi-CPU system, the compilation process can be parallelized. This means that many components of Sage can be compiled in parallel, hence reducing the time it takes for the compilation process to complete. The general steps to compile Sage in parallel are as follows. Determine the number of cores on your system and decide on how many threads you want to devote to a parallel compilation of Sage. On Mac OS X, detailed information about your system’s hardware is obtained via the command

$ system_profiler

Say your system has two cores and you want to use two threads for compiling Sage in parallel. Then the necessary setup to compile Sage with two threads is:

$ SAGE_PARALLEL_SPKG_BUILD="yes"; export SAGE_PARALLEL_SPKG_BUILD $ MAKE="make -j2"; export MAKE $ make

This should initiate the process of compiling Sage in parallel. If your system allows for compiling Sage with more threads, e.g. 4 or 8 threads, then change “-j2” to “-j4” or “-j8” accordingly.

Once all components of Sage are successfully compiled, the compilation process will automatically build the HTML version of the Sage standard documentation. This documentation includes a tutorial, an FAQ, a collection of thematic tutorials, a reference manual, an installation guide, among other documents. Building the HTML version of the Sage standard documentation does not require . However, for best results, it is recommended that you have installed on your system. Furthermore, is a prerequisite for building the PDF version of the Sage standard documentation. To manually build the HTML version of the documentation, do the following from within the SAGE_ROOT directory:

$ ./sage -docbuild all html # or $ ./sage -docbuild --no-pdf-links all html

To build the PDF version of the documentation, do

$ ./sage -docbuild all pdf

For further options to customize your build of the Sage standard documentation, see the output of the following command:

$ ./sage -docbuild

You can also download the documentation from

http://www.sagemath.org/help.html

or view it online at

To customize the compilation process to your particular needs, refer to the file

SAGE_ROOT/Makefile

Once the compilation process completes, there is no separate installation process for your newly compiled Sage. You can think of Sage as being compiled and installed under SAGE_ROOT. To begin using your freshly compiled version of Sage, navigate to SAGE_ROOT and launch Sage as follows:

$ cd /Users/username/sage-x.y.z/ $ ./sage

## Number theory & RSA public key cryptography

I have released version 1.1 of the Sage tutorial “Number theory and the RSA public key cryptosystem”. There is little change in terms of content. However, note that I now use the GNU Free Documentation License v1.3+ for the tutorial. Here are the relevant files you can download for your reading pleasure.

All versions of the tutorial are available from the download page on its website. For the adventurous of heart, I have also made the full source of the document available.

The tutorial is meant to be educational. I don’t pretend that it is complete in any way. Any suggestions and/or criticisms for improving the tutorial are more than welcome. Enjoy and happy Sage’ing.

## Numbering exercises/problems using chapter numbers

To typeset a list of exercises or problems in , you could use the enumerate environment. By default, this would only produce numbers of the form n. where n is a positive integer. You could number an exercise using the chapter number to produce numbering of the form c.n. where c is the chapter number. Put the following macro definition in your preamble to get the chapter number to appear.

%% For listing problem sets. Each problem is numbered according to the %% format %% %% chapterNumber.problemNumber. \newcounter{problemcounter} \newenvironment{problem}{% \setcounter{problemcounter}{1} \begin{list} {\thechapter.\arabic{problemcounter}.} {\usecounter{problemcounter}} \let\olditem\item}{% \end{list} }

This could easily be customized to insert the section number instead of the chapter number.