Computerized mathematics and the mathematics of computation

Plan Author

  • Ambrose Sterr, 2007

Fields of Concentration

Sample Courses

  • Course: Writing Math
  • Course: Programming Workshop
  • Course: Formal Languages and the Theory of Computation

Project Description

The design and implementation of efficient computer algorithms to look for combinatorial designs.

Faculty Sponsors

Outside Evaluator

  • Jeff Dinitz, University of Vermont

Overview

Roman-k and Tuscan-k squares are families of combinatorial objects that have applications in experimental design, psychology, graph theory, tournaments, and many other areas. The purpose of this project is to discuss some of the properties of Roman-k and Tuscan-k squares, as well as to describe directed Tk-terraces and generating arrays, two objects that can be used to construct Roman-k and Tuscan-k squares. I will also discuss some of the well-known results on the existence of Roman-k and Tuscan-k squares, particularly the existence of Tuscan squares of every order except 3 and 5.

There are a number of unanswered questions involving the existence of Roman-k and Tuscan-k squares, including the existence of any Roman squares of odd prime order, of which 11 is the smallest odd prime case not known to have no Roman squares, the existence of a Tuscan-2 square of odd order, of a Tuscan generating array that is not Roman, and a Roman-3 square that is not Vatican. In a paper titled “Searching for Roman-k and Tuscan-k Squares”, I detail my methods and results in attempting to answer some of those questions using computational algorithms.

Excerpts

“Of all the languages I regularly use, C is probably the most frustrating, and perhaps the most useful. C has been described as the lowest of the high-level languages, and it seems to me to straddle the line between high and low level, giving the programmer great deal more direct control over the exact behavior of the program, and lacking the automation over things like memory usage that most high-level languages seem to have. C is a compiled language, and indeed forms the basis for many other languages, whose compilers (or interpreters) are written in C.”

“Roman-k squares have some innate symmetries that can be useful in describing them. They do not depend on the order of the rows in their definition, as permuting the rows does not affect which ordered pairs are present, or that each row or column contains every symbol once. Tuscan-k squares are also independent of the ordering of the rows, since row order does not affect the pairs or that each row contains each symbol once. As a result permuting the rows of a Roman-k or Tuscan-k square yields another square of the same type.”

Reflections

“I remember taking over the downtime of all the iMacs in the computer lab to build a compute-cluster, which turned out to be essential for the extremely intensive calculations that went into my Plan. One of the solutions required a full week to compute, even with all of the computers churning away at it.”