Last Update: Feb. 18, 2025

• Teacher: Dr. Doron ZEILBERGER ("Dr. Z")

• Classroom: Allison Road Classroom Building [Busch Campus], IML Room 121 in ARC

• Time: Mondays and Thursdays, period 3 (12:10-1:30pm)

• Dr. Zeilberger's Email: zeilberg@math.rutgers.edu

• Dr. Zeilberger's Office Hours (Spring 2025): MTh 10:50-11:50am
  

Description

Experimental Mathematics used to be considered an oxymoron, but the future of mathematics is in that direction. In addition to learning the philosophy and methodology of this budding field, students will become computer-algebra wizards, and that should be very helpful in whatever mathematical specialty they are doing (or will do) research in.

We will first learn Maple, and how to program with it. This semester we will learn, from an experimental mathematics point of view, Quantum computing and algorithmic graph theory. People who already took previous editions of this class are welcome to take it again, since except for the basics, there is very little overlap with previous years.

This class is suitable for graduate students in other departments, and the software development skills learned will be useful for doing any quantitative research. Very smart advanced undergraduates are also welcome. In particular, the methods learned should be applicable almost everywhere.

Textbooks

• Quantum Mechanics (The Theoretical Minimum) by Leonard Susskind and Art Friedman.

• The Nielsen-Chuang classic

• Introduction to Classical and Quantum Computing by Thomas G. Wong.

• Peter Shor's seminal paper

• Robin Wilson's wonderful graph theory book

Optional (but Highly recommended) Getting Started Homework

For more details, see this 2002 masterpiece.

How to submit homework

• Every class has a homework assignment. Both Mondays and Thursdays' are due 8:00pm Sunday of the following week.

  It should be sent to the email address

  ShaloshBEkhad at gmail dot com

  Subject: HomeWork#X

  and then attach a .txt file(s) called

  hwXYourFirstNameYourLastName.txt

  where X is the number of the assignment

  Except for the first assignment, you should have two attached .txt files.

  For example, when David Hilbert submits homework assignments 2 and 3, he should email ShaloshBEkhad at gmail dot com, with

  Subject: HomeWork#2#3

  and attach the text files (the source code plus human comments (such lines must start with #)

  hw2DavidHilbert.txt and hw3DavidHilbert.txt

• The very first line of the .txt files should have

  #Please do not post homework
  or
  #OK to post homework

  Followed by
  #Your Name, Date, Assignment X

Programs done on Thurs., Jan. 23, 2025

• Graphs(n): inputs a non-neg. integer and outputs the set of ALL (undirected simple) graphs on {1,...,n} with the data structure [n,E] where it is understood that the set of vertices is {1, ...,n} and E is the set of edges, where an edge joining vertex i and vertex j is denoted by {i,j}

• Tri(G): inputs a graph [n,E] and outputs the set of all triples {i,j,k} such {{i,j},{i,k},{j,k}} is a subset of E

• Comp(G): the complement of G=[n,E] i.e. the graph [n, E1] such E1 is the set of all possible edges minus E. For example Comp([3,{{1,2},{1,3}}]); should give [3,{{2,3}}]

• TotTri(G): the total number of love triangles and hate triangles

Homework for Thurs., Jan. 23, 2025, class (due Sunday Jan. 26, 8:00pm)

Subject: HomeWork#1

and an attachment

hw1FirstNameLastName.txt

and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

1. [People who took this class before, or already know Maple, are excempt from this] Read and do all the examples, plus make up similar ones, in the first 30 pages of Frank Garvan's awesome Maple booklet ( part 1, part 2)
   Only record a small sample in hw1YourName.txt .

2. [For everyone!] Read and (try to understand) Chapter 1 of the Susskind-Frieman Quantum Mechanics book book. Do all the exercises.

3. [Optional (and very challenging) for novices, mandatory for experts]

   Write a procedure AM(G) that inputs a graph [n,E] and outputs the adjacency matrix, represented as a list of lengthn of lists of length n, such that M[i][j]=1 if {i,j} belongs to E and 0 otherwise. For example

   AM([2,{{1,2}});

   should output [[0,1],[1,0]] .

4. [Optional (and very challenging) for novices, mandatory for experts] write a procedue

   Image(pi,G)

   that inputs a permutation pi of {1,...,n} and a graph G=[n,E] and outputs the image under pi.

5. [Optional (and very challenging) for novices, mandatory for experts] By definition an unlabelled graph is an equivalene class of labeled graphs under graph isomorphism (i.e. mapping under the symmetric group). Write a procedure

   ULgraphs(n)

   that outputs a set of graphs with ONE member of each equivalence class.

   What is

   [seq(nops(ULgraphs(i)),i=1..6)]

   Is is in the OEIS? What is its A-number.

Added Jan. 26, 2025: Students' homework (that they kindly agreed to be posted) are in this directory

Programs done on Monday, Jan. 27, 2025

• LC(p): inputs a rational number between 0 and 1 and outputs true with prob. p

• RG(n,p)

• Cliques(G,k): inputs a graph G and a pos. integer k outputs the set of k-cliques

Homework for Monday, Jan. 27, 2025, class (due Sunday Feb. 2, 8:00pm)

Subject: HomeWork#2

and an attachment

hw2FirstNameLastName.txt

and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

1. [People who took this class before, or already know Maple, are excempt from this] Read and do all the examples, plus make up similar ones, pages 30-60 of Frank Garvan's awesome Maple booklet ( part 1, part 2)
   Only record a small sample in hw1YourName.txt .

2. [For everyone!] Read and (try to understand) Chapter 2 of the Susskind-Frieman Quantum Mechanics book book. Do all the exercises (if they exist)

3. [Optional for novices] Write a procedure

   TotClique(G,k)

   that inputs a graph G=[n,E] and a positive integer k, and outputs the total number of k-cliques and k-anti-cliques.

4. [Optional for novices] Writing a procedure

   CheckRamsey(k,K), that inputs a positive intgeger k and a large integer K that picks K random graphs (using RG(18,1/2)) and finds the minimum of ToClique(G,4);

5. [Optional for novices] Write a procedure

   EstimateAverageClique(n,p,k,K)

   that estimates the average number of cliques of size k in a random graph given by RG(n,p) by picking K of them and averaging.

   What did you get for

   EstimateAverageClique(10,1/2,4,10000)?

6. [Optional challenge, 5 dollars] Find a closed-form expression for the average number of k-cliques in a graph with p vertices where the prob. of every edge showing up is p.

Added Feb. 2, 2025: Students' homework (that they kindly agreed to be posted) are in this directory

Programs done on Thurs., Jan. 30, 2025

C3.txt , Contains procedures (in addition to those of C1.txt and C2.txt listed in Help1(); and Help2(); respectively)

• Neis(G): inputs a graph G=[n,E] and outputs a list of length n, N, such that N[i] is the set of neighbors of vertexi

• CC(G,i): The connected component of vertex i in the graph G

• IsCo(G): Is the graph G=[n,E] connected?

• NuCG(n): the first n terms of the sequence enumerating CONNECTED labeled graphs on n vertices, in other words sequence OEIS A001187 , done by brute force

• NuCGc(n): the first n terms of the sequence enumerating CONNECTED labeled graphs on n vertices, in other words sequence OEIS A001187 , done cleverly, using Exponential Generting Function, the fact that

  Sum(CC[i]/i!*z^i,i=0..infinity)= log(Sum(2^binomial(i,2)/i!*z^i,i=0..infinity)

Homework for Thurs. Jan. 30, 2025, class (due Sunday Feb. 2, 8:00pm)

Subject: HomeWork#3

and an attachment

hw3FirstNameLastName.txt

and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

1. [People who took this class before, or already know Maple, are excempt from this] Read and do all the examples, plus make up similar ones, pages 60-90 of Frank Garvan's awesome Maple booklet ( part 1, part 2)
   Only record a small sample in hw1YourName.txt .

2. [For everyone!] Read and (try to understand) Chapter 3 of the Susskind-Frieman Quantum Mechanics book book. Do all the exercises (if they exist)

3. [For everyone!] Read and (try to understand) the section on "Exponential generating functions" (pp. 7-9) of Dr. Z.'s essay

4. [For everyone] Convince yourself that the following one-line procedure, for p rational between 0 and 1 and n positive integer

   PC:=proc(n,p,K) local i:evalf(coeff(add(IsCo(RG(n,p)),i=1..K),true,1)/K):end:

   is an estimate, with large enough K (say at least 200), for the probability of coonectivity of a random graph with n edges where every edge is picked with prob. p (the Edros-Renyi model)

   With n=10,20,30, and p=1/10, 2/10, ... and K=200 experiment and try to estimate the threshhold for connectivity, i.e. when it changes being very unlikely to very likely.

5. [Optional for novices]

   Procedure NuCCc(n) outputs the first n terms (starting at n=1) of OEIS sequence A1187 that counts the sequence let's call it C[n], of the number of connected labeled graphs with n vertices. It is based on the formula

   Sum(C[n]*z^n/n!,n=0..infinity)=log(Sum(2^(n*(n-1)/2)*z^n/n!,n=0..infinity)

   Let P[n](x) be the polynomial in x whose coefficient of x^r is the number of labeled connected graphs on n vertices and EXACTLY r edges. Convince yourself (or believe) that using generating functions one has the formula

   Sum(P[n](x)*z^n/n!,n=0..infinity)=log(Sum((1+x)^(n*(n-1)/2)*z^n/n!,n=0..infinity)

   Write a procedure

   NuCGx(n,x)

   that inputs a pos. integer n and a variable x, and outputs a list of length n whose i-th entry is P[i](x)

6. [Optional for novices]

   Convince yourself that the lowest power (lowdegree in Maple) of P[n](x) is n-1. Using NuCGx(n,x) (make sure to put "option remember" there), Write a procedure

   NuCGk(n,k)

   that inputs a positive integer n and a non-negative integer k and outputs the sequence of cofficients of x^(n-1+k) of P[n](x)

   What OEIS number is NuCGk(n,0)?

   What OEIS number is NuCGk(n,1)? (if it exists)

   Keep upping k and see the largest k for which NuCGk(n,k) is in the OEIS

Programs done on Monday, Feb. 3, 2025

C4.txt , Contains procedures (in addition to those of C1.txt and C2.txt and C3.txt listed in Help1(); and Help2(); Help3(); respectively)

• PM(): the three famous Pauli matrices [sigma_x,sigma_y, sigma_z]

• RM(n,K): a random n by n matrix with complex entries from -K to K

• CT(A): the conjugate transpose of A

• IsUM(A): Is the matrix A unitary

• STbf: Inputs a graph G=[n,E] and outputs the set of all spanning trees by brute force

• NST(G): The number of spanning trees of G=[n,E] (using the Matrix Three Therorem)

Homework for Monday Feb. 3, 2025, class (due Sunday Feb. 9, 8:00pm)

Subject: HomeWork#4

and an attachment

hw4FirstNameLastName.txt

and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

1. [People who took this class before, or already know Maple, are excempt from this] Read and do all the examples, plus make up similar ones, pages 90-end of Frank Garvan's awesome Maple booklet ( part 1, part 2)
   Only record a small sample in hw1YourName.txt .

2. Read section 1.3 of the The Nielsen-Chuang book

3. Write a procedure

   UM(alpha,beta,gamma,delta)

   that implements box 1.1. on p. 20 of the The Nielsen-Chuang book [Note the superflous comma]

   For random alpha, beta, gamma, delta apply it to IsUM(A). Also, a litle bit of challenge, prove it for geneal (symbolic) alpha,beta,gamma, delta

4. [Optional challenge, 5 dollars to be divided among correct answers] Use the matrix tree theorem applied to the complete graph K_n to prove Cayley's formula that there n^n-2 labelled trees

Added Feb. 9, 2025: Students' homework (that they kindly agreed to be posted) are in this directory

Programs done on Thurs., Feb. 7, 2025

C5.txt , Contains procedures

• PM(): the three famous Pauli matrices sigma_x,sigma_y, sigma_z

• RHM(n,K): a random n by n Hermitian matrix with entriries from -K to K

• EV(L): inputs a Hermitian matrix (say n by n) and outputs the LIST of eigenvalues

• EVC1(L,g): inputs a matrix L and an eigenvalue g finds the NORMALIZED eigenvector

• EVC(L): inputs a Hermitian matrix and outputs the pair ListOfEigenvalues, ListOfEigenvectors

• ProbDist(L,A): Given an obervalble represented by the Hermitian matrix L and a state vector A outputs first all the eigenvectors (pure states) and the prob. of winding in the respective pure states followed by the expected value of A (i.e. if you make the observation L and the state is A the average in the long run

Homework for Thurs. Feb. 6, 2025, class (due Sunday Feb. 9, 8:00pm)

Subject: HomeWork#5

and an attachment

hw5FirstNameLastName.txt

and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

1. Write a procedure

   RandomState(n,K)

   that inputs a pos. integer n and a pos. integer K and outputs a random state vector with n complex components whose real and imaginary parts are from -K to K, then normalize it.

2. Experiment with three different random random Hermitian matrices using RHM(n,K) with n=3 and K=10 and check that the eigenvalues are real and that the eigenvectors (pure states) are all orhogonal to each other.

3. Experiment with five different random random Hermitian matrices using RHM(n,K) with n=3 and K=10 and corresponding five random state vector and apply ProbDist(L,A) to them. For each case check that the proba. distribution consists of non-negative numbers that add up to 1.

4. Write a procedure

   GeneralPauli(n)

   that inputs a NORMALIZED vector n=[nx,ny,nz]

   that constructs the 2 by 2 matrix. at the bottm of p. 349 of the Susskind-Frieman Quantum Mechanics book book.

   Find its eigenvalues and eigenvectors.

Added Feb. 9, 2025: Students' homework (that they kindly agreed to be posted) are in this directory

Programs done on Monday., Feb. 10, 2025

C6.txt ,

• Mul(A,B): the product of matrix A and B (assuming that it exists)

• Com(A,B: The commutator of A and B

• RSV(n,K): a random NORMALIAED state vector of length n with complex entries from -K to K

• Del(L,A): the "avergae error", i.e. standard deviation pf the prob. distribution of measuring the observable L when the state is A

• CheckUP(A,B,V): the ratio of Del(A,V)*Del(B,V)/Expectation(Com(A,B),V) (it should be >=1/2, if the (generalized) Heisenberg Uncertainty Principle is True)

• [modified from C5.txt]

  ProbDist(L,A): Given an obervalble represented by the Hermitian matrix L and a state vector A (i) the list if eigenvalues (possible outcomes of observing L regardless of the state A (ii) the respective probabilities of the outcome being that eigenvalue, if the system is at state A (iii) the expected value of the outcome

Homework for Monday Feb. 10, 2025, class (due Sunday Feb. 16, 8:00pm)

Subject: HomeWork#6

and an attachment

hw6FirstNameLastName.txt

and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

1. Write a procedure

   AllHM2(K)

   that inputs a positive integer K and outputs ALL 2 by 2 matrices of the form

   [[a,b+I*c],[b-I*c,d]]

   where a,b,c,d, are integers such that 1 ≤ a,b,c,d ≤ K (there are K⁴ of them

2. [clarified Feb. 13, 2025]

   Write a procedure

   RealSV2(K)

   that inputs a positive integer K and outputs all normalizations of the vectors (i.e. make them unit vectors)

   [a,b]

   with

   where a and b are integers 1 ≤ a,b ≤ K (there are K² of them

3. UncertaintyContest(K)

   that inputs a positive integer K and goes all throgh the pairs A, B of matrices in AllMH2(K), and RealSV2(K) (quite a few of them) and outpts the triplet [A,B,V] that make CheckUP(A,B,V) as small as possible and as big as possible [Make sure that you exclude the case when A and B commute, since then the ratio is infinity]

   What are

   UncertaintyContest(2)?, UncertaintyContest(3)?

   Added Feb. 16, 2025: Students' homework (that they kindly agreed to be posted) are in this directory

4. ---

   SPECIAL VALENTINE HOMEWORK (also due Sunday, 8:00pm but a different attachments)

   Design a Valentine that says

   I love Algorithmic Graph Theory

   OR

   I love Quantum Computing

   email two attachments

   ValentineFirstLast.jpg

   and ValentineFirstLast.txt (with the source code)

5. (due Monday, 10:00am). Look the valentines in the directory

   Valentines,

   and fill the form

   ValentineBallot.txt

   and email ShaloshBEkhad@gmail.com with

   Subject: Valentine Ballot

   and an attachment

   ValentineBallotFirstLast.txt

   with your ratings (from 1 to 10, please reserve 0 for your own valentine and for those that have no submissions)

   [The winner will get a chocolate box.]

   Added Feb. 17: Congratulations to Lucy Martinez for winning first prize.

   ---

   Programs done on Thurs., Feb. 13, 2025

   C7.txt ,

   • PC1(T): one step in the Pruffer code algorithm. Looks for the smallest leaf outputs the pair [a,T1] where a is the LABEL of the (only) neighboor of the smallest leaf and T1 is the smaller tree where the only edge incident that leaf is removed.

   • PC(T): the Pruffer code of the labeled tree T labeled by {1, ...,n} where n=nops(T)+1

   • Added after class (based on Nick Belov's idea and top of p. 49 of Robin Wilson's wonderful graph theory book

     AntiPC(P): inputs a list of length n-2 with entries from {1, ...,n} outputs the tree T such that PC(T)=P

   Homework for Thurs. Feb. 13, 2025, class (due Sunday Feb. 16, 8:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: HomeWork#7

   and an attachment

   hw7FirstNameLastName.txt

   and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

   1. Carefully read the code for AntiPC(P) (based on Nick Belov's idea and Robin Wilson's book) and convince yourself that it does the right thing. By using rand, generate several sequences of length 10 with entries in [1,12] call them P, and find out whether PC(AntiPC(P))=P as it should.

   2. Write a procedure

      NumberOfLeaves(T)

      that inputs a labeled tree, T, and outputs the number of leaves (vertices of degree 1). For example

      NumberOfLeaves({{1,2},{1,3},{1,4}}); should output 3

   3. Write a procedure

      RandomTree(n)

      that inputs a positive integer n, and outputs a random labeled tree on {1, ...,n}

      [Hint: using rand(1..n), generate a random list of length n-2, P, and then let T:=AntiPC(P)]

   4. Write a procedure

      EstimateAverageNumberOfLeavs(n,K)

      that uses simulation to esimates the average number of leaves in a random labeled tree with n vertices

      [Hint: run RandomTree(n) K times, for each time find out the number of leaves, add them all up and divide by K.]

      What did you get for

      EstimateAverageNumberOfLeavs(100,1000)?

      EstimateAverageNumberOfLeavs(100,10000)?

      Are they close?

   5. [Optional theoretical challenge, "open book" and "open internet", 5 dollars]. Find the exact expression for the average number of leaves in a random tree with n vertices. Call it a_n. After you found it, prove that

      limit(a_n/n, n goes to infinity)

      exists, and find its value.

   6. Do a preliminary reading of Chapter 6 of Quantum Mechanics (The Theoretical Minimum) by Leonard Susskind and Art Friedman.

   Added Feb. 16, 2025: Students' homework (that they kindly agreed to be posted) are in this directory

   ---

   Programs done on Monday, Feb. 17, 2025

   C8.txt ,

   • ES(): the four fullly entangled states in the Alice-Bob combined system (based on p. 166 of the Susskind-Friedman's book)

   • TP(A,B):the tensor product of matrix A and matrix B (using our data structure of lists-of-lists)

   • [Added after class]: ExpMV(M,V): inputs a Hermitian matrix M and a state vector V finds the expected value of the observable M in state V using (more efficient than ProbDist(M,V)[3])

   Reading Homework for Monday Feb. 17, 2025, in preparation for the next class (2/20/25)

   Read Turing and Abel prizes winner Avi Wigderson's essay (section III.24, pp. 196-199) in the Princeton Companion of Mathematics edited by Sir W. Timothy Gowers.

   Homework for Monday Feb. 17, 2025, class (due Sunday Feb. 23, 8:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: HomeWork#8

   and an attachment

   hw8FirstNameLastName.txt

   and indicate whether it is OK to post. If you do not "OK to post", it will not be posted.

   1. Read and understand procedure ExpMV(M,V) that is supposed to give you the same ouptut as ProbDist(M,V)[3]. Take three take a random 3 by 3 Hermitian matrices (using RHM(3,10)) and a random 3-state vetor (using RSV(3,10)) and check that if you take evalf(ProbDist(M,V)[3]) you get the same thing as evalf(ExpMV(M,V)). Do it three times.

   2. By taking V:=RSV(2,100); verify that

      add(ExpMV(PM()[i],V)^2,i=1..3)=1

      Do it three times. In other words the sum of the squares of the expectation of the three Pauli matrices adds up to 1 for every state vector.

   3. The Alice-versions of the Pauli matrices are obtained by taking the tensor product with the identity, getting a 4 by 4 Hermitian matrix, in other words

      TP(PM()[i],PM()[4])

      Let's call them Ax,Ay,Az. For a random state vector, obtained by RSV(4,10), say, write a procedure

      EntangelmentAlice(V)

      that outputs the sum of the squares of the expected values of Alice's measurement in that state.

   4. Write a procedure

      RandomProductState4(K)

      that outputs a random product state vector of length 4 obtained by taking the tensor product of two RSV(2,K)

   5. what are EntangelmentAlice(V) for ES()[i], i=1..4?

      What is it for a random product state?

      By using RSV(4,10) twenty times, find the vector with maximal entanglemt (i.e. the smallest value of EntanglemtAlice(V)) and the least (closest to 1)

   6. Do the same with EntangelmentBob

Dr. Z.'s teaching page