Experimental Mathematics Projects

Combinatorics at the Interface of probability theory, analysis, and experimental mathematics
Algorithmic and Enumerative Combinatorics Summer School, August 2016
Hagenberg, Austria
Dan Romik

This Mathematica notebook contains suggestions for experimental mathematics projects you can work on (with Mathematica or with any other mathematical software, or even with straightforward programming in C, Python etc.). Enjoy!

Notebook version: August 1, 2016.

Experimental Mathematics Project 1: investigating the Robbins numbers mod 2

Define the Robbins numbers.

A[n_,k_]:=(((n+k-2)!(2n-k-1)!)/((n-1)!(k-1)!(n-k)!))Product[(((3j+1)!)/((n+j)!)),{j,0,n-2}];

Have a look at the first few rows of the Robbins triangle.

Table[A[n,k],{n,1,8},{k,1,n}]//Grid

When you run across an interesting sequence of numbers, the first thing you should always do is to look it up in the amazing Online Encyclopedia of Integer Sequences (OEIS). We can do this from Mathematica by defining a convenience function OEISLookup[ ] and then looking up the Robbins numbers to see what OEIS has to say about them.

OEISLookup[sequence_]:=Module[{url},
  url = "http://oeis.org/search?q=";
  Do[url = url<>ToString[sequence[[i]]]<>If[i<Length[sequence],"%2C","&languge=english&go=Search"] ,{i,1,Length[sequence]}];
  SystemOpen[url]
];

Try evaluating the next command.

OEISLookup[Flatten[Table[A[n,k],{n,1,4},{k,1,n}]]]

Now look at the Robbins numbers mod 2. Try evaluating this command and then changing the upper range of the index n to get a larger data set

Table[Mod[A[n,k],2],{n,1,7},{k,1,n}]//Grid

Since this is a rather sparse array, it helps to show only the nonzero values, which can be done by forming generating polynomials of each row.

Do[poly=Sum[Mod[A[n,k],2](x^k),{k,1,n}];If[CoefficientList[poly,x]≠{},Print[n,"    ",poly]],{n,1,200,1}]

The project: you’re now on your own. Your goal is to investigate the interesting patterns that emerge from this question and try to 

	1) formulate conjectures;
	2) prove theorems;
	3) generalize the question to find other interesting patterns;
	4) importantly, don’t forget to use the internet to do a literature search to see if anything is known about this question.

Experimental Mathematics Project 2: the number of steps in the hook walk

Let (Subscript[W, n,m]) denote the average number of steps that the hook walk (discussed in the lecture) takes until terminating when it is performed on an n×m rectangular Young diagram. By the definition of the hook walk, (Subscript[W, n,m]) can be expressed as

(Subscript[W, n,m])=(1/(n m))(Underscript[Σ, 1≤i≤n, 1≤j≤m]) S(i,j),

where we denote by S(i,j) the average number of steps of the hook walk on the same Young diagram started from the box with coordinates (n+1-i,m+1-j) (this labeling of the indices is selected so that S(i,j) is independent of m and n -- think of the hook walk as happening in reverse, moving to the left and down towards the bottom-left corner of the diagram). Moreover, again by the definition, it is easy to see that S(i,j) satisfies the recurrence relation

S(i,j)=1+(1/(i+j-2))(Subscript[Σ, k=1]^(i-1))S(k,j)+(Subscript[Σ, k=1]^(j-1))S(i,k),       (i,j)((ϵℕ)^2)\(1,1),

together with the initial condition S(1,1)=1. Let’s program this function in Mathematica. Calling the function SijArray[n] defined below returns a two-dimensional array with the values S(i,j) for 1≤i,j≤n.

SijArray[n_]:=Module[{myarray},
myarray=Table[0,{i,1,n},{j,n}];
Do[myarray[[i,j]]=If[{i,j}=={1,1},0,1+(1/(i+j-2))(Sum[myarray[[k,j]],{k,1,i-1}]+Sum[myarray[[i,k]],{k,1,j-1}])],
{i,1,n},{j,1,n}];
myarray
];

SijArray[6]//MatrixForm

The project: investigate these numbers and find interesting things to say about them. Some possible questions to think about are:

	1. Can you find a closed-form formula for S(i,j) and/or for the average values (Subscript[W, n,m])? (A suggestion: try small examples first, such as setting i=1, i=2,..., etc.) 
	2. Can you determine the asymptotics of (Subscript[W, n,n])? My guess is it should behave asymptotically like a constant times log(n). 
	3. Can you prove upper and lower bounds that are logarithmic in n? 
	4. Can you find the precise constant in the asymptotics? 
	5. Can you understand the distribution (rather than just the average value) of the number of steps?
	6. What can you say about the number of steps in the hook walk for non-rectangular Young diagrams?

Experimental Mathematics Project 3: improved upper bounds in the moving sofa problem

The moving sofa problem is an open problem in geometry. It asks for the two-dimensional shape of maximal area that can be move around a right-angled corner in a corridor of unit width. The problem was first asked 1966 and has been open since.

The best bounds for the maximal area of a moving sofa are 2.21953... (lower bound) and 2(Sqrt[2])≈2.82 (upper bound). The lower bound is the area of a specific shape proposed by Joseph Gerver in a 1992 paper.

The project. I have an idea for an experimental math project whose goal is to prove improved upper bounds. The upper bound of 2(Sqrt[2]) is pretty trivial and should not be too hard to improve using a computational/experimental math approach that involves some programming to do a computer search of a certain configuration space. Getting any improvement of the upper bound (which will already be a publishable result in my opinion) is essentially a purely computational problem, whereas getting a significant improvement that pushes the upper bound much closer to the lower bound would require some additional (possibly rather nontrivial) mathematical reasoning.

I will not include the details of the idea here since this problem is not related to combinatorics, the topic of the summer school, but I’ll be happy to explain them to anyone who’s interested, so feel free to ask me about it. The explanation should not take more than 5 minutes.

Here is a link to a short HTML article I wrote about the moving sofa problem, with a summary of what’s known about the problem (including some new results I proved, making heavy use of experimental math and Mathematica) and some fun animations of moving sofas: https://www.math.ucdavis.edu/~romik/movingsofa/

Experimental Mathematics Project 4: the Witten zeta function

For a problem I was working on in 2015 related to the asymptotic enumeration of representations of the group SU(3), I was led to study the function of a complex variable

f(s)=Γ(s)(Underoverscript[Σ, (j,k=1), ∞])(1/(((j k (j+k)))^s))

Specifically, I needed to understand where f(s) has poles and what their residues are. Actually the series only converges for s>2/3, but it turns out the function can be analytically continued using the following approximate formula

g(s)=Γ(2s-1)Γ(1-s)ζ(3s-1)+(Underoverscript[Σ, (k=0), N])((((-1))^k)/(k!))Γ(s+k)ζ(2s+k)ζ(s-k)

where N is a large integer. It can be shown that f(s)-g(s) is an analytic function in the half-plane Re(s)> -N/2, so g(s) encodes the necessary information about the singularities of f(s).

We can now study the singularitiies of g(s) both experimentally (and then theoretically). It is not hard to see they are located at s=2/3; s=1/2,-1/2,-3/2,-5,2,...; and s=0,-1,-2,-3,....

g[s_]:=Gamma[2s-1]Gamma[1-s]Zeta[3s-1]+Sum[((((-1))^k)/(k!))Gamma[s+k]Zeta[2s+k]Zeta[s-k],
{k,0,20}]; (* We choose 20 as the upper range of the summation *)

Try evaluating the following commands.

Residue[g[s],{s,2/3}]

Table[Residue[g[s],{s,x}],{x,1/2,-7/2,-1}]

Table[Residue[g[s],{s,x}],{x,0,-7,-1}]

Hmm. This last result is surprising, isn’t it? Thinking about why this should happen led me to discover (and eventually prove -- using software developed here at RISC!) a very interesting theorem. 

The project: try to analyze the problem theoretically, using standard facts (that can be easily found on Wikipedia, etc.) about the Euler gamma function and Riemann zeta function, and rediscover the theorem I found, then see if you can prove it. Is this just an isolated fact or one of a larger family of similar results? I don’t know.

Experimental Mathematics Project 5: unleash your creativity

This is an open-ended assignment. Try to think of your own math research problems and write some code to explore them experimentally, or even just write code to visualize and explore a known concept or theorem you are interested in.