ARC 121
Last Update: May 10, 2025
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.
Maple packages produced in this class
Added April 6, 2025: Pick at project
For more details, see this 2002 masterpiece.
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
#Please do not post homework
or
#OK to post homework
Followed by
#Your Name, Date, Assignment X
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.
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]] .
Image(pi,G)
that inputs a permutation pi of {1,...,n} and a graph G=[n,E] and outputs the image under pi.
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
RG(n,p)
Cliques(G,k): inputs a graph G and a pos. integer k outputs the set of k-cliques
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.
[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.
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);
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)?
[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
C3.txt , Contains procedures (in addition to those of C1.txt and C2.txt listed in Help1(); and Help2(); respectively)
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)
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.
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.
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)
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
C4.txt , Contains procedures (in addition to those of C1.txt and C2.txt and C3.txt listed in Help1(); and Help2(); Help3(); respectively)
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.
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
Added Feb. 9, 2025: Students' homework (that they kindly agreed to be posted) are in this directory
C5.txt , Contains procedures
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.
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.
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
C6.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
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.
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 K4 of them
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 K2 of them
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
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)
and fill the form
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.
C7.txt ,
AntiPC(P): inputs a list of length n-2 with entries from {1, ...,n} outputs the tree T such that PC(T)=P
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.
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
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)]
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?
limit(an/n, n goes to infinity)
exists, and find its value.
Added Feb. 16, 2025: Students' homework (that they kindly agreed to be posted) are in this directory
C8.txt ,
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.
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.
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.
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.
RandomProductState4(K)
that outputs a random product state vector of length 4 obtained by taking the tensor product of two RSV(2,K)
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)
Added Feb. 23, 2025: Students' homework (that they kindly agreed to be posted) are in this directory
C9.txt , contains the following procedures:
[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)]
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.
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) ]
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
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
C10.txt , contains the following procedures:
NAND(x,y): not (x and y)
NOT(x): NAND(x,x)
Read Don Knuth's half-a-page version of Hao Huang's Proof of the sensitivity conjecture
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.
SimulateNAND(n,k, K)
that for K times does the following
SimulateNAND(10,5, 1000), SimulateNAND(10,10, 1000), SimulateNAND(10,20, 1000), SimulateNAND(10,50, 1000)?
(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
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):
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.
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?
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
C12.txt ,
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.
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
C13.txt ,
Contains the following procedures:
[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.
[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)
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.
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
Mul(Mul(C1QG()[i],C1QG()[j]),C1QG()[k])=c*C1QG()[r]
Output the set of all such [i,j,k,r,c].
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]]); ?
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
C14.txt contains:
Bell(C1QG()[4],C1QG()[2], -(C1QG()[2]+C1QG()[4])/sqrt(2),(C1QG()[2]-C1QG()[4])/sqrt(2),ES()[1]);
C14pi.txt contains:
LeibnitzN(N): using N terms in the Lebnitz formula to appx. Pi
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.
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/π2.
How close is JesusG(10) to 128/π2?, How close is JesusG(100) to 128/π2?,
[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 combined in one file
Students' Pi homework (that they kindly agreed to be posted) are in this directory
Please email ShaloshBEkhad at gmail dot com an email with
Subject: HomeWork#14
and an attachment
hw14FirstNameLastName.txt
[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)
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)?
Added March 23, 2025: Students' homework (that they kindly agreed to be posted) are in this directory
Today we celebrated (one day early) Pi day.
Please email ShaloshBEkhad at gmail dot com an email with
Subject: HomeWork#15
and an attachment
hw15FirstNameLastName.txt
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).
What is
evalf([seq(2*n*a(n-1)/a(n),n=1000..1010)]) ?
Does it seem to converge to any famous constant?
Added March 23, 2025: Students' homework (that they kindly agreed to be posted) are in this directory
Contains procedures:
Please email ShaloshBEkhad at gmail dot com an email with
Subject: HomeWork#16
and an attachment
hw16FirstNameLastName.txt
and indicate whether it is OK to post.
ToffoliMatrix(): and FredkinMatrix()
that returns the appropriate 8 by 8 matrices
Sjk(j,k)
that expresses the matrix Sj,k (Eq. (4.3), p. 14) in our notation of lists-of-lists
QFTC(l)
that inputs a pos. integer n and outputs the quantum circuit of Eq. (4.4) (but replace l by n) in the same format at the output of RQC. i,e.
[n,[H,[n-1]], ....
where H is the Hadamard matrix C1QG()[7]=[[1/2*2^(1/2), 1/2*2^(1/2)], [1/2*2^(1/2), -1/2*2^(1/2)]]
Added March 30, 2025: Students' homework (that they kindly agreed to be posted) are in this directory
Contains procedures:
FindFact(n,K): tries to find a factor of n using FindFact1(n) K times or returns FAIL (very unlikely if K is big)
ModExp(x,r,n): x^r mod n the fast way where r is given in reverse binary [2^0,2^1,2^2,...]
Please email ShaloshBEkhad at gmail dot com an email with
Subject: HomeWork#17
and an attachment
hw17FirstNameLastName.txt
and indicate whether it is OK to post.
xphi(n) mod n =1 .
Hence the order must be a divisor of phi(n). The Maple package numtheory has both phi and divisors. Write a procedure
MyOrd(x,n)
that (i) computes phi(n) (ii) finds its set of divisors, (iii) sorts them (iv) keeps trying xr mod n until it gets 1.
Take random large x and n and compare the time it takes.
Why is even this more (possibly more) clever way of computing the order of x mod n not break (in realistic time) the RSA with a classical computer?
A weighted directed graph with n vertices can be described a pair [n,E] (like the one generated by procedure RG(n,p) of C2.txt , together with a table T defined on E where for any member e of E T[e] is the distance. Write a procedure, RWG(n,p,K) whose output is a triple [n,E,op(T)] where T is the table of distances. where the distances are random integers from 1 to K.
For example the graph with vertices {1,2,3} and set of edges {{1,2},{1,3}} and the distance between 1 and 2 is 5 and between 1 and 3 is 2 is expressed as:
[3, {{1, 2}, {1, 3}}, table([{1, 3} = 2, {1, 2} = 5])]
Also write a procedure where L[i] is not the shortest distance but the actual path from a to i.
Added March 30, 2025: Students' homework (that they kindly agreed to be posted) are in this directory
Contains procedures:
Please email ShaloshBEkhad at gmail dot com an email with
Subject: HomeWork#18
and an attachment
hw18FirstNameLastName.txt
and indicate whether it is OK to post.
AveLengthSP(G,a)
That inputs a weighted graph and a starting vertex a and uses GijP(G,a)[2] to compute the average length of a shortest path from a.
AveLengthStat(n,p,K,M)
that picks a random weigted graph according to RWG(n,p,K) M times, finds for each AveLengthSP(G,a) and finds the average and variance for each run.
Run
AveLengthStat(100,1/4,2,10000)
five times. What did you get? Are they similar?
Added April 6, 2025: Students' homework (that they kindly agreed to be posted) are in this directory
Pablo Blanco's explanation why you need op(T) rather than T for a table in Maple
Contains procedures:
MST(G): the minimal spanning tree of the weighted graph G=[n,E,DT] followed by its cost (the sum of the costs of the edges of the cheapest tree)
Please email ShaloshBEkhad at gmail dot com an email with
Subject: HomeWork#19
and an attachment
hw19FirstNameLastName.txt
and indicate whether it is OK to post.
EstimateAverageMinCost(n,p,K,N)
that runs MST(RWG(n,p,K)) N times (where N is a large pos. integer) and outputs the fraction of those that are connected, and among them the average cost of a minimal spanning trees (both in decimals)
Using the above, write a procedure
EstimateTable(n,N,a,b)
that inputs a pos. integer n (not too large), a large (at least 1000) pos. integer N, pos. integer a and pos. integer b and outputs the list
L[i][K] (i beteen 1 and a) (K between 1 and b)
such that L[i][K] is the estimated average of a minimal spanning tree of a random weighted spanning tree with prob. of picking an edge with prob. i/a and picking a weight of an edge from 1 to K.
What did you get for
EstimateTable(10,3000,5,10)?
Run it a few times and see whether the results are close (of course they shouldn't be the same, this is simulation)
[Big challenge, I have no clue, 50 dollars if you do it yourself, 20 dollars if you can find a reference]. Find a closed-form expression, in terms of n, p, and K to the expected cost of a minimal spanning tree if you pick a weighted random graph according to RWG(n,p,K) (i.e. you pick each edge (independently) with prob. p and for each edge you pick an integer weight, uniformly from 1 to K.
Added April 6, 2025: Lucy Martinez found the following references: On the value of a random minimum spanning tree problem by Alan Frieze and Minimal Spanning Trees for Graphs with Random Edge Lengths by J. Michael Steele.
Write a procedure
EulerianPath(G)
that inputs a Eulerian graph G=[n,E] (see section 6 of Robin Wilson's graph theory book), that (i) checks that it is indeed Eulerian (ii) outputs a Eulerian trail using either Fleuri's algorithm (see there) or any other correct method.
Added April 6, 2025: Students' homework (that they kindly agreed to be posted) are in this directory
Contains procedures:
Eq57(q,k,n,c,x): the value of Eq. (5.7) in Shor's paper
Eq58(q,k,n,c,x): the value of Eq. (5.8) in Shor's paper (w/o the error term)
Eq59(q,k,n,c,x): the value of Eq. (5.8) in Shor's paper (w/o the error term)
Histogram56(128,86,4,3);
Please email ShaloshBEkhad at gmail dot com an email with
Subject: HomeWork#20
and an attachment
hw20FirstNameLastName.txt
and indicate whether it is OK to post.
Hint: first use Maple's int command. Then do evalc then take the absolute value-squared (the sum of the square of the real part and the square of the imaginary part)
Histogram56(128,86,4,3);
Histogram56(256,86,4,3);
and come up with five more examples like this.
Added April 13, 2025: Students' homework (that they kindly agreed to be posted) are in this directory
Contains procedures:
Please email ShaloshBEkhad at gmail dot com an email with
Subject: HomeWork#21
and an attachment
hw21FirstNameLastName.txt
and indicate whether it is OK to post.
CFx(x,k)
that inputs any positive number (given in decimals) and outputs the first k terms of its infinite continued fraction
Write a procedure
GuessPCF(x)
that inputs a quadratic irrationality x (e.g. sqrt(n) where n is not a square-free) and outputs two lists [L1,L2]
such that the continued fraction of x is [L1,op(L2)infinity].
Find GuessPCF(n) for all non-square integers beween 2 and 100
Added April 13, 2025: Students' homework (that they kindly agreed to be posted) are in this directory
Please email ShaloshBEkhad at gmail dot com an email with
Subject: HomeWork#22
and an attachment
hw22FirstNameLastName.txt
and indicate whether it is OK to post.
Added April 20, 2025: Students' homework (that they kindly agreed to be posted) are in this directory
Images(T): all the images of the full binary tree T under reflection at ALL levels.
Please email ShaloshBEkhad at gmail dot com an email with
Subject: HomeWork#23
and an attachment
hw23FirstNameLastName.txt
and indicate whether it is OK to post.
[Hint, the functional equation, according to Polya is
r(x)=x+1/6*(r(x)^3+ 3*r(x)*r(x^2)+ 2*r(x^3))
Note that the number of leaves is always odd so only extract the odd coefficients]
ALnmG(X,3,4,10,{[1,3],[2,1],[2,3],[3,1],[3,2]});
In the Maple package AL.txt you would get six identities that any four 3x3 matrices A1,A2,A3,A4 where the only the diagonal entries as well as the [1,2] entry are non-zero, i.e. matrices of the form
[[a11,a12,0],[0,a22,0],[0,0,a33]]
One of them is:
X[[1, 2, 3, 4]]-X[[1, 2, 4, 3]]-X[[2, 1, 3, 4]]+X[[2, 1, 4, 3]]
Convince yourself that this is stating that for any four such matrices
(A1A2-A2A1)(A3A4-A4A3)= 0 matrix
Or in our language
Mul(Mul(A1,A2)-Mul(A2,A1), Mul(A3,A4)-Mul(A4,A3))=[[0,0,0],[0,0,0],[0,0,0]] .
Prove it rigorously.
A full k-ary tree is either a single vertex, called a root, or an ordered tree where every vertex is either a leaf or else has exactly k children.
Let f(x) be the generating function
Convince yourself that
f(x)=x+f(x)^k
Note that such a tree must have 1+(k-1)m leaves for some m. Can you conjecture, and if possible, prove, an explicit expression for
A_k(m):=Number of full k-ary trees with 1+(k-1)m leaves?
UTk(k,N)
that inputs a positive integer k ≥ 2, and a positive integer N and outputs the first N terms of the sequence
Number of UNLABELED full k-ary trees with 1+(k-1)m leaves for m=1..N
[Hint: You need to find a general expression (or look it up) for the "cycle index polynomial" of the symmetric group on {1,...,k}, and then generlize UT(N) and your UT3(N) with the appropriate functional equation for r(x)=r_k(x)]
Added April 20, 2025: Students' homework (that they kindly agreed to be posted) are in this directory
GFperiodPer(n,x):the polynomial whose coeff. of x^j is the prob. that if you take a random permutation from [1,n] to [1,n] and a random starting point the length of the ultimate cycle is j, followed by the average and standard-deviation
Please email ShaloshBEkhad at gmail dot com an email with
Subject: HomeWork#24
and an attachment
hw24FirstNameLastName.txt
and indicate whether it is OK to post.
CompareFibMod(INI,M)
that for m from 2 to M compares FibMod(INI,m) to EstimateGFperiod(m^2,x,10000)[2][1]. Is the former ever larger than the latter? when INI=[0,1] and M=300?
GFperiodPer(n,x)[1] is (x+x^2+...+x^n)/n .
seq(GFperiod(n,x)[2][1]*n^(n+1),n=1..5);
coincides with the first five terms of OEIS sequence A262970, and according to the OEIS equals it for all n.
It is stated there that the E.G.F.of this sequene is T/(1-T)^4, where
T:=Sum(n^(n-1)/n!*x^n,n=1..infinity)
Prove it!
Added April 27, 2025: Students' homework (that they kindly agreed to be posted) are in this directory
Contains procedures:
Please email ShaloshBEkhad at gmail dot com an email with
Subject: HomeWork#25
and an attachment
hw25FirstNameLastName.txt
and indicate whether it is OK to post.
Please email ShaloshBEkhad at gmail dot com an email with
Subject: HomeWork#25
and an attachment
hw25FirstNameLastName.txt
and indicate whether it is OK to post.
NuEqC(n,c)
that uses CIPsn(n,x) to find that number.
What is
[seq(NuEqC(i,2),i=1..12)]
[seq(NuEqC(i,3),i=1..12)]
[seq(NuEqC(i,4),i=1..12)]
Can you conjecture a closed-form expression? Can you prove it WITHOUT Polya theory (at least the first one with c=2)
Added April 27, 2025: Students' homework (that they kindly agreed to be posted) are in this directory
Contains procedures (Note, you need to have AGT.txt in the same directory)
Please email ShaloshBEkhad at gmail dot com an email with
Subject: HomeWork#26
and an attachment
hw26FirstNameLastName.txt
and indicate whether it is OK to post.
Added May 4, 2025: Students' homework (that they kindly agreed to be posted) are in this directory
Contains procedures
LkUT(k,N): the first N terms of the number of UNORDERED full k-ary trees with (k-1)*n+1 leaves
Please email ShaloshBEkhad at gmail dot com an email with
Subject: HomeWork#27
and an attachment
hw27FirstNameLastName.txt
and indicate whether it is OK to post.
Added May 4, 2025: Joseph Koutsoutis' homework (that he kindly agreed to be posted) is in this directory
Today we had a "hackaton", there are several versions of the procedurs below with the coder's names.
Please email DoronZeil at gmail dot com an email with
Subject: HomeWork#28
and an attachment
hw28FirstNameLastName.txt
and indicate whether it is OK to post.
1- (1/(k+1)+ 1/(k+2)+ ...+1/n)
In particular for 2n prisoners and n locker-openings it is 1-(1/(n+1)+...+1/(2n)) that converges to 1-log(2)
[Hint: prove that if k is larger than n/2, the probability of a random permutation having a cycle of length k is 1/k]
Here is Group picture at the Mint restaurant after the field trip to two Princeton cemeteries.