Last Update: March 13, 2025

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

  ---

  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
    [solutions]

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

  • Peter Shor's seminal paper

  • Robin Wilson's wonderful graph theory book

  • Don Knuth's half-a-page version of Hao Huang's Proof of the sensitivity conjecture

  • the Einstein-Podolsky-Rosen classic

  • John Bell's seminal paper

  Optional (but Highly recommended) Getting Started Homework

  Teach yourself the basics of Maple by reading Frank Garvan's golden-oldie part 1, part 2
  Note: a few commands are no longer valid in today's Maple. The most important one is that " has been replaced by %.

  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

  C1.txt , Contains procedures
  • 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)

  Please email ShaloshBEkhad at gmail dot com an email with

  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

  C2.txt , Contains procedures (in addition to those of C1.txt listed by Help1();)
  • 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)

  Please email ShaloshBEkhad at gmail dot com an email with

  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)

  Please email ShaloshBEkhad at gmail dot com an email with

  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

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

  ---

  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)

  Please email ShaloshBEkhad at gmail dot com an email with

  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

  Today, due to the inclement weather we had a remote class where we did the following Maple code:

  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)

  Please email ShaloshBEkhad at gmail dot com an email with

  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)

  Please email ShaloshBEkhad at gmail dot com an email with

  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 say "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

        EntanglementAlice(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 EntanglementAlice(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 EntanglementAlice(V)) and the least (closest to 1)

     6. Do the same with EntanglementBob

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

  ---

  Programs done on Thurs., Feb. 20, 2025

  C9.txt , contains the following procedures:

  • Gnd(n,d): the graph whose vertices are {0,...,n-1} and edges {i, i+j mod n} j=1..d (and at the end of the days the vertices are labeled {1, ....n}.

  • AM(G): the adjacency matrix of the graph G=[n,E] (the stupid way, but it works for large graphs)

  • lam2(G): inputs a graph and returns FAIL if it is not regular, otherwise it returns [degree, Lambda_2] (Lambda_2 is the second largestg eigenvalue of the adjacency matrix) (the spectral gap is d-Lambda2)

  • Vk(k): The list of all 0-1 vectors of length k in lex order

  • HD1(v): inputs a 0-1 vector and outputs all the vectors where exactly one bit is changed

    [The original name in class was Nei(v) but Pablo suggested changing the name since in C3.txt there was a procedure called Neis(v)]

  • Ck(k): the k-dim unit cube as a graph in our format

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

  Please email ShaloshBEkhad at gmail dot com an email with

  Subject: HomeWork#9

  and an attachment

  hw9FirstNameLastName.txt

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

  1. [A little bit challenging for novices]

     Using the definition of the Cheeger constant in this wikipedia article, write a procdeure

     CheegerC(G)

     that inputs a graph in our format [n,E] and outpits the Cheeger constant.

     [Hints: 1.with the combinat package loaded, choose(S,i) gives you the set of subsets of S of size i 2. To get the number of edges between S and its complement form the set of potential edges {s1,s2} where s1 is in S and s2 is in its complement and then intersect it with E and then take its nops) ]

  2. Write a procedure

     CheckBounds(G)

     that outputs the Cheeger constant and the interval [(d-Lambda_2)/2,sqrt(2*d*(d-Lambda_2))] and checks that the former is inside the latter.

     What did you get for CheckBounds(G) for

     G=Gnd(n,2), 5 ≤ n ≤ 10

     G=Gnd(n,3), 5 ≤ n ≤ 10

  3. [Optional challenge]

     1. (3 dollars) Conjecture an explicit expression for

     charpoly(AM(Ck(k)),x)

     2. (5 dollars, I don't know the answer): by searching the intenet find out whether it is well-known, and if possible find a reference for a proof

     Added Feb. 24, 2025: Joseph Koutsoutis won the prize and also Lucy Martinez who found this this interesting thesis by Captain Stanley F. Florkowski III.

     3. (20 dollars, I don't know the answer), Without "peeking" prove this conjecture.

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

     ---

     Programs done on Monday, Feb. 24, 2025

     C10.txt , contains the following procedures:

     • NAND(x,y): not (x and y)

     • NOT(x): NAND(x,x)

     • AND(x,y): NAND(NAND(x,y),NAND(x,y))

     • OR(x,y): NAND(NAND(x,x) , NAND(y,y)):

     • RSLP(n,k): a random straight-line progran with NAND only

     • TF(n): the set of all true-false vectors of length n

     • EvalSP1(P,IN): inputs a straight-line NAND program and an input true-false vector outputs the value of the last gate

     • EvalSP(P,n): inputs a NAND SLP and outouts the set of vectors of length n that yields true

     Reading Homework for Monday Feb. 24, 2025, class (due Thurs., Feb. 27, 2025)

     Read Don Knuth's half-a-page version of Hao Huang's Proof of the sensitivity conjecture

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

     Please email ShaloshBEkhad at gmail dot com an email with

     Subject: HomeWork#10

     and an attachment

     hw10FirstNameLastName.txt

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

     1. [clarified Feb. 25, 2025]
        Write a progmram

        SimulateNAND(n,k, K)

        that for K times does the following

        • picks a random P=RSLP(n,k)
        • computes nops(EvalSP(P,n)) ( a nunmber from 0 to 2ⁿ)
        • adds all of these numbers up
        • divides by K
        Whad did you get for:

        SimulateNAND(10,5, 1000), SimulateNAND(10,10, 1000), SimulateNAND(10,20, 1000), SimulateNAND(10,50, 1000)?

     2. (Modified Feb. 26, 2025)
        Adapt RSLP(n,k) to write a procedure

        Monotone(n,k,p) where n and k are positive integers and p is a rational number between 0 and 1), that has no NOT, i.e. only using AND and OR, and a typical member is [i,j,AND] or [i,j,OR] (now i ≤ j, i=j is not allowed) and for each non-input gate, the probability of AND is p and the probability of OR is 1-p)

        then write

        SimulateMonotone(n,k, p, K)

        What did you get for

        SimulateMonotone(10,5, 1/2,1000), SimulateMonotone(10,10, 1/2, 1000), SimulateMonotone(10,20, 1/2, 1000), SimulateMonotone(10,50, 1/2, 1000),

        SimulateMonotone(10,5, 3/4,1000), SimulateMonotone(10,10, 3/4, 1000), SimulateMonotone(10,20, 3/4, 1000), SimulateMonotone(10,50, 3/4, 1000),

        SimulateMonotone(10,5, 1,1000), SimulateMonotone(10,10, 1, 1000), SimulateMonotone(10,20, 1, 1000), SimulateMonotone(10,50,1, 1000),

        Hint: In order to simulate a "loaded die" that returns true with probabality p (where p is a rational number between 0 and 1) you can use

        LD:=proc(p):evalb(rand(1..denom(p))()<=numer(p)):end:

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

     ---

     Programs done on Thursday, Feb. 27, 2025

     C11.txt ,

     Contains (in addition to old procedures from C1.txt, C2.txt and C9.txt that can be viewed via Help1(), Help2(), Help9(), respectively):

     • Mul(A,B): the product of matrix A and B (assuming that it exists), in our favorite format of lists-of-lists

     • NeiList(G): inputs a graph G=[n,E] and outputs a list of length n whose i-th entry is the set of neighbors of vertex i

     • MaxNN(G,H): inputs a graph G=[n,E] and a subset H of {1, ..., n} outputs the maximum number of members that belong to H over all members of H

     • MinMaxNN(G,r): minimum of MaxNN(G,H) over all subsets H of {1, ..., n} with cardinality r
       (Note: the Hao Huang famous sensitivity conjecture (now a theorem) says that MinMaxNN(Ck(n),2^(n-1)+1)>=sqrt(n)

     • MinMaxNNpablo(G,r): A (much more) memory-efficient of MinMaxMN(G,r), suggested by Pablo Blacno (after discussions with Auora Hiveley)

     • An(n): the 2^n by 2^n matrix (given as a list of lists) in Don Knuth's half-a-page version of Hao Huang's Proof of the sensitivity conjecture

     • Bn(n): the 2^(n-1) by 2^n matrix in the above paper

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

     Please email ShaloshBEkhad at gmail dot com an email with

     Subject: HomeWork#11

     and an attachment

     hw11FirstNameLastName.txt

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

     1. Using the corrected Mul(A,B), verify that indeed A_n B_n=sqrt(n)B_n for small n. How far were you able to go with in a reasonable amount of time?

     2. As Pablo noticed the largest r such that MaxNN(G,r) is 0 is the independence number of G (the largest subset of vertices that have no edges between them). Use

        MaxNNpablo(G,r)

        to write a procedure

        IndNu(G)

        that finds the independence number of a graph G=[n,E]

        What are the independence numbers of Gnd(n,2) for n from 3 to 15? Can you make a conjecture? [5 dollars to be divided] Can you prove it?

        What are the independence numbers of Gnd(n,3) for n from 3 to 15? Can you make a conjecture? [5 dollars to be divided] Can you prove it?

     3. Write a procedure

        UpperBoundMinMaxNN(G,r,K)

        that uses combinat[randcomb]({seq(i,i=1..n)},r) K times and finds the minimum of MaxNN(G,H) for K random r-element subsets of the set of vertices {1,..,n}.

        What did you get for

        UpperBoundMinMaxNN(Ck(8),129,5000)?

        How far is it from the actual minimum of 3 (according to the sensitivity theorem)?

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

     ---

     Programs done on Monday, March 3, 2025

     C12.txt ,

     • Verify1(n): checks that An(n) times Bn(n)=sqrt(Bn(n))

     • Findy(n,H): inputs a pos. integer n and a subset H with exacty 2^(n-1)+1 elements and outputs the vector y such that

     • LuckyVertex(n,H): inputs pos. integer n and a subset H of size 2^(n-1)+1 outputs a member that is guaranteed to have at least sqrt(n) neighbors in H

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

     Please email ShaloshBEkhad at gmail dot com an email with

     Subject: HomeWork#12

     and an attachment

     hw12FirstNameLastName.txt

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

     1. Write a procedure

        AveLuckyVertexFriends(n,K)

        that inputs a positive integer n, and for K random subsets of {1, ..., 2^n} with 2^(n-1)+1 elements gotten with

        combinat[randcomb](2^n,2^(n-1)+1)

        does the following

        1. Finds the lucky vertex (in terms of the row number)

        2. Finds the number of members of H that are joined by an edge to it
        [Hint: The absolute value of An(n) is the adjacency matrix of the n-dim unit cube so you have to sum the absolute value of the entry in the row that correpond to the lucky vertex that belong to columns of H]
        Call that number FriendsOfLucky(n,H)
        3. Make sure that it is always ≥ sqrt(n), according to the sensitivity lemma If you can find an H that violates it, return FAIL.
        4. Average it over all K random chices and output the average.

        What did you get for

        AveLuckyVertexFriends(9,100)?

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

     ---

     Programs done on Thurs., March 6, 2025

     C13.txt ,

     Contains the following procedures:

     • C1QGnames(): The names of the seven most common quantum 1-gates , namely: [` Identity `, ` PauliX `, `PauliY `, `PauliZ `, ` PhaseS `, `TPi/8` , ` Hadamard `]

     • C1QG(): The list of length 7 containing the above 2 by 2 unitary matrices in our list-of-lists format for matrices

     • BV(n): inputs a non-neg. integer n and outputs the list of length 2^n of all 0-1 vectors in lex. order

     • nBasis(n,X): the basis of n-quantum gates circuits X[e1,e2,.., en] corresponds to |e1>|e2>...|en>

     • UMtoT(M,n,X): inputs a unitary matrix M of size 2^n by 2^n (correpsonding to a quantum circuit with n qbits, outputs the corresponding LINEAR TRANSFORMATION as it acts on the canonical basis

       [The output is a pair T=[Table,Base]. To see how T[1] acts on a a member of the base do T[1][T[2][i]] where i is between 1 and 2^n.

     • TtoUM(T,n): inputs a table T=[T1,Base] of n-gate quantum network and outputs the corresponding 2^n by 2^n unitary matrix (the reverse of UTtoT(M,n,X))

     • [From previous claases: Mul(A,B) (matrix multiplcation AB in list-of-lists format. TP(A,B): Tensor product of A and B, ES(), the four famous Bell states (maximally entangled)

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

     Please email ShaloshBEkhad at gmail dot com an email with

     Subject: HomeWork#13

     and an attachment

     hw13FirstNameLastName.txt

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

     1. On p. 130 of Thomas G. Wong's wonderful book Introduction to Classical and Quantum Computing it is proved that

        HXH=Z

        This can be rephrased, in our program as

        Mul(Mul(C1QG()[7],C1QG()[2]),C1QG()[7])=C1QG()[4]

        Find all triples 2 ≤ i,j,k ≤ 7 (there are 6^3=216 such triples) such that

        Mul(Mul(C1QG()[i],C1QG()[j]),C1QG()[k])

        is equal to a member of C1QG(), say C1QG()[r]. Output the set of all such quadruples [i,j,k,r] (in particular [7,2,7,4] should be a member of that set).

        In other words find all such identities where a product of three (not necessarily distinct) mmembers of C1QG() equals to one of them.

        How big is that set? for some 1 ≤ r ≤ 7

     2. [Added March 8, 2025] Adapt the above problem to find, more generally all quadruples 2 ≤ i,j,k ≤ 7 and c constant (obviously of absolute value 1) such that

        Mul(Mul(C1QG()[i],C1QG()[j]),C1QG()[k])=c*C1QG()[r]

        Output the set of all such [i,j,k,r,c].

     3. Write a procedure

        ApplyT(T,X,n,u)

        where T=[T1,V], T1 is a table and V is nBasis(n,X), and u is an arbitrary linear combination of of members of nBasis(n,X), that uses the linearity of the table , and outputs the result of applying the linear transformation T (given as a table defined on the canonical basis), as a linear combination of the basis elements.

        If T=UMtoT(TP(H,Z)), what is

        ApplyT(T,X,2,X[[0,0]]+I*X[[0,1]]+2*I*X[[1,0]]+5*X[[1,1]]); ?

     4. Read and understand the "no-cloning theorem", p. 166, of Wong's book.

     5. [Added March 7, 2025, 10:00 am] Optional challenge (ten dollars). The fact that two complex numbers a[1] and a[2] commute, i.e.

        a[1]*a[2]=a[2]*a[1]

        can be rewriiten as

        add(c[pi]*a[pi[1]]*a[pi[2]], pi in permute(2))=0

        where c[12]=1 and c[21]=-1,

        As you know, for 2 by 2 matrices A[1] and A[2] it is usually not true that A[1]A[2]=A[2]A[1] .

        But perhaps something analogous is true for them if you allow something more complicated. Can you find six numbers c[123], ..., c[321] such that

        add(c[pi]*Mul(Mul(A[pi[1]],A[pi[2]]),A[pi[3]]), pi in permute(3))= [[0,0],[0,0]]

        for every three 2 by matrices A[1],A[2],A[3]?

        If not, can you find 24 numbers c[1234], ..., c[4321] such that

        add(c[pi]*Mul(Mul(A[pi[1]],A[pi[2]]),Mul(A[pi[3]],A[pi[4]])), pi in permute(4))=[[0,0],[0,0]]

        for every four 2 by matrices A[1],A[2],A[3], A[4]?

        [Hint (modified March 7, 2025, 2:10pm): You have to look for 24 numbers such that the above relation holds for EVERY choice of four 2 by 2 matrices A[1],A[2],A[3],A[4]. To find 24 unknown numbers you need 24 independent homogeneous equations. By making 6 random choices (using rand(1..10)(), for example, and then writing a little procedure RM() that outputs a random 2 by 2 matrix), pick 6 random choices of quadruple of numerical 2 by 2 matrices. For each random choice you get a 2 by 2 matrix featuring the unknowns c[pi]. Then set them all equal to zero. Then use Maple's solve. If you get a not-all-zero solution it is good news, and you have a conjecture. Finally to prove it rigorously, plug in four SYMBOLIC matrices A[1],A[2],A[3],A[4].]

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

     Programs done on Monday, March 10, 2025

     • C14.txt ,

     • C14pi.txt ,
     C14.txt contains:

     UL>

  4. Bell(A0,A1,B0,B1,V): The expression due to Bell that is the quantum analog of a0*b0+a0*b1+a1*b0-a1*b1 ( the expectation of its abslute value is <=2) The choice of A0,A1,B0,B1 in the wikipedia article is

     Bell(C1QG()[4],C1QG()[2], -(C1QG()[2]+C1QG()[4])/sqrt(2),(C1QG()[2]-C1QG()[4])/sqrt(2),ES()[1]);

C14pi.txt contains:

• Leibnitz(D1): Uses Leibnitz' formula to compute Pi with an error less than1/10^D1

• LeibnitzN(N): using N terms in the Lebnitz formula to appx. Pi

Special Pi Day Homework due Wed., March 12, 2025, 8:00pm

Please email ShaloshBEkhad at gmail dot com an email with

Subject: HomeWork#14pi

and an attachment

hw14piFirstNameLastName.txt

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

1. Write a procedure

   JesusG(N)

   that uses N terms of Jesus Guillera's amazing formula in his homepage (given in "Ramanujan notation") that computes an approximation to 128/&pi².

   How close is JesusG(10) to 128/&pi²?, How close is JesusG(100) to 128/&pi²?,

2. [Pi Hacktaton]: Use any algorithm you can find (except "cheating ones" like copying the digits of Pi) to compute Pi. The fasted and/or most elegant entry will win a Pi T-shirt.

   [Hint: Many series for Pi are of hypergeometric type: Sum(p(n)*f(n),n=0..infinity) where p(n) is a polynoial and f(n)/f(n-1) is a rational function. It is most efficient to just have the current value of f(n) and keep adding p(n)*f(n)]

Added March 13, 2025: See all Students' Pi codes

Regular Homework due Sunday, March 16, 2025, 8:00pm

Please email ShaloshBEkhad at gmail dot com an email with

Subject: HomeWork#14

and an attachment

hw14FirstNameLastName.txt

1. [Modified and simplified, March 11]

   Write a process

   RandomBell1(K)

   (1) After defining ra:=proc(K): rand(-K..K)():end: Keeping the same A0,A1,B0,B1, as in the wikipedia article

   A0:=C1QG()[4],A1:=C1QG()[2],B0:= -(C1QG()[2]+C1QG()[4])/sqrt(2),B1:=(C1QG()[2]-C1QG()[4])/sqrt(2)

   (2) Picks a random state (in the 2-qubit space generated by 00,01,10,11, sets V=[ra(K)+I*ra(K),ra(K)+ra(K)*I,ra(K)+I*ra(K),ra(K)+I*ra(K)]:

   (3) NORMALIZE it! , i.e. divide V by its NORM. rename the new state V.

   Computes Bell(A0,A1,B0,B1,V)

2. Write a procedure

   RandomBell(K,N)

   that runs RandomBell1(K) N times and returns

   (1) The average value over all N trials.

   (2) The fraction of times it exceeds 2, thereby refuting Albert (and Boris and Nathan)

   What did you get for

   RandomBell(10,1000)?

Programs done on Thurs., March 13, 2025

• C15.txt ,

  Today we celebrated (one day early) Pi day.

  • A(n): A sequence of bad approximations to Pi using the prob. that if you toss a coin 2n times the prob. of getting exactly n Heads is asymototic to sqrt(n)/Pi

  • IsUD(pi): Is the permutation pi an up-down i.e. pi[1]pi[3]
  • UD(n): the number of up-down permutations of length n the stupid way (pure brute force)

  • [added after class]
    UDset(n): the SET of up-down permutations of length n the stupid way

  Homework due Sunday, March 16, 2025, 8:00pm

  Please email ShaloshBEkhad at gmail dot com an email with

  Subject: HomeWork#15

  and an attachment

  hw15FirstNameLastName.txt

  1. By looking at UDset(7) and Udset(8), observer that the location of "n" the largest entry (7 and 8 respectively) are always at EVEN locations. Why?

  2. Using this fact, explain why the number of up-down permutations of length n (that is computed by brute force using UD(n)), let's call it a(n), satisfies the non-linear recurrence

     a(n)=Sum(binomial(n-1,2*k-1)*a(2*k-1)*a(n-2*k),k=1..trunc(n/2)):

     (subject to the initial condition a(1)=1).

  3. Using this recurrence, with `option remember`, write a procedure UDc(n) (clever version of UD(n)). Make sure that UDc(n) and UD(n) coincide for 1<=n<=8.

     What is

     evalf([seq(2*n*a(n-1)/a(n),n=1000..1010)]) ?

     Does it seem to converge to any famous constant?

  4. [Optional challenge, 5 dollars] Prove the above conjecture rigorously. Hint: You can "cheat" and look at the exponential generating function stated at the OEIS, but you have to prove that it is indeed the exponential generating function.

  ---

  Dr. Z.'s home page