Applied Math 106: Applied Algebra

Prof. Salil P. Vadhan

SAGE Instructions:

For some of your homework problems, we will be using an online platform for SAGE (see SageMath.org for full details on SAGE). The platform we will be using is hosted by CoCalc, which recommends using the latest version of Google Chrome to access the platform.

1. You should have recevied an email from CoCalc inviting to join AM106 Fall 2018 and create an account if you don't already have one. If you haven't received one please let us know ASAP.
   
   
2. Once you've created your new account, or logged in for the first time, you should arrive at a page titled "Projects."
• a) You shoud see a project titled "[your email address] - AM106 Fall 2018". This is where you will be working, so click on this project.
• b) You'll notice that there are 5 tabs at the top left corner of the page: Files, New, Log, Find, and Settings. The "Files" tab is where you can manage (create, download, upload) the various codes you'll write.
  
  
3. Directly under the "Files" tab, you'll find a place where you can input a "Filename," to the right of which you’ll find a "+Create" button.
• a) Type a file name (say, PS1).
• b) From the dropdown menu adjacent to the "+Create" button, choose the SAGE workstation option "Sagews." You'll be taken to the file you just created in a new tab.
  
  
4. Familiarize yourself with the interface. E.g., try the following computations:
• a) Calculate 1037 mod 7 by writing Mod(1037,7) then hitting "shift+enter." (hitting "enter" would create a new line; to change the settings of these shortcuts, along with other settings, click on "Account" at the top right corner of the page).
• b) Check that Mod(2^10+9,7) gives the same answer.
• c) SAGE's syntax is similar to python’s. Try the following example of a loop in SAGE, with shift+enter after the third line: a=1
  for i in range(10): a=Mod(2*a,7)
  Mod(a+Mod(9,7),7)
  
  
5. Please annotate your notebook wth comments indicating which problem you are solving and the purpose of each step using "#" as follows: a=1 #Initialize at 2^0
   for i in range(10): a=Mod(2*a,7) #Find 2^10 mod 7 by successively multiplying by 2
   Mod(a+Mod(9,7),7) #Find (2^10+9) mod 7 as ((2^10 mod 7) + (9 mod 7)) mod 7
   
   
6. You can save the notebook you're working on, convert it to a pdf, and download it, all within the window you're working in. To download, click on the button directly under the tab "Files," and choose the last option in the dropdown menue. You should always submit your annotated notebook as a pdf file on Canvas. To upload a file, go to the "Files" tab, and look for the "Upload" button at the top right part of the page.

PS2 Tips

When you enter a series of commands in SAGE, you do not need to hit shift+enter after each one. You can just hit shift+enter after the final one, after which all of the commands will execute in sequence. This can help make your notebook more readable.

You may find it useful to use the ``list'' data type in SAGE to keep track of sequences of numbers. The following sequence of commands will create and print a list consisting of the first 10 Fibonacci numbers.
fib=[0 for i in range(10)] # create an list of length 10 filled with 0's.
fib[0]=1 # set the 0th item in the list to 1. note that lists are indexed starting at 0
fib[1]=1 # set the 1st item in the list to 1.
for i in range(2,10): fib[i]=fib[i-2]+fib[i-1] #set the remaining 8 items in the list using the recurrence for Fibonacci numbers
fib # print the list

If you prefer not to use lists and loops, you can also achieve the same thing with a sequence of commands:
fib0=1 #initializing the first two elements of the sequence
fib1=1
fib2=fib0+fib1 #calculate the remaining 8 using the recurrence
fib3=fib1+fib2
fib4=fib2+fib3
fib5=fib3+fib4
fib6=fib4+fib5
fib7=fib5+fib6
fib8=fib6+fib7
fib9=fib7+fib8
fib10=fib8+fib9
fib0,fib1,fib2,fib3,fib4,fib5,fib6,fib7,fib8,fib9 #print all 10 numbers

PS3 Tips

To get the problem data g, q, a, b, and c, follow these instructions:

1) Download the files ps3data.csv (and optionally ps3read.sagews) from Canvas under Files.

2) Upload ps3data.csv  to your Cocalc workspace.

3) Run the following commands to get the data g, q, a, b, and c (also found in ps3read.sagews):

import sympy as sp

import pandas as pd

ABC = pd.read_csv("ps3data.csv",delimiter="\n",header=None).as_matrix()

data = sp.sympify(ABC[0][0])

g = Integer(int(data[0]));

p = Integer(int(data[1]));

a = Integer(int(data[2]));

b = [Integer(int(data[3][i])) for i in range(30)];

c = [Integer(int(data[4][i])) for i in range(30)];

4) You can access elements of the lists b and c as b[0],b[1],...,b[29],c[0],c[1],...,c[29].

5) In addition to the SAGE commands you have used on previous problem sets, you may now use power_mod(x,y,z) which calculates x^y mod z efficiently (using the same repeated squaring algorithm that was covered on problem set 1).   Note that the power_mod function expects all of its inputs to be integers.  If you take an even integer n and set m=n/2, SAGE will cast m as a rational number rather than as an integer and you won't be able to use it in power_mod. This can be avoided by using integer division instead: m=n//2.

PS4 Tips

Important: SAGE composes permutations from left to right, which is opposite from the convention in lecture and Gallian. That is, in SAGE, sigma*tau means performing permutation sigma then tau. For example, in SAGE, (1 2)*(2 3) = (1 3 2).

Here we will illustrate how you can use SAGE to answer questions about permutation groups. Specifically, suppose we want to study a subgroup of Sym({a,b,c,d,e,f}).

• While SAGE does allow one to define a permutation group on an arbitrary finite set X, some of the commands you'll want to use (namely word_problem) require us to restrict to subgroups of S_n. So we use elements of X as names of variables that we assign to numbers as follows:
  
  a,b,c,d,e,f = range(1,7)
  
  which sets a=1, ... , f=6.
  
  
• Now we create the "parent group" S₆ in which all of our permutations will live.
  
  S6 = SymmetricGroup(6)
  
  
• We can now create the permutations sigma = (a b c d)(e f) and tau = (a b) as follows:
  
  sigma = S6([(a,b,c,d),(e,f)])
  tau = S6([(a,b)])
  
  Take note of the syntax here. We put the permutation inside S6() in order to tell SAGE to interpret it as an element of the group S6. The permutation is then specified as a SAGE "list" of items (i.e. inside square brackets), where each item of the list is one of the cycles in the permutation (in disjoint cycle notation) and these are separated by commas. The cycles themselves are specified by SAGE tuples (i.e. in parentheses), with commas separating the items in each cycle.
  
  Since the variables a,b,c,d,e,f are assigned to numbers from 1-6, the above commands are equivalent to:
  
  sigma = S6([(1,2,3,4),(5,6)])
  tau = S6([(1,2)])

• We can calculate the orders of these permutations using the following commands:
  
  sigma.order()
  tau.order()
  
  
• Now we can construct the subgroup H generated by these two permutations as follows.
  
  H = S6.subgroup([sigma,tau])
  H
  
  Note that SAGE reorders the generators. This will be relevant later.
  
  
• We can calculate the order of H as follows:
  
  H.order()
  
  
• We can calculate the orbit and stabilizer of an element of our set X, say "a", as follows:
  
  H.orbit(a)
  I = H.stabilizer(a)
  I
  

• I is a subgroup of H, and hence also a permutation group. So we can use commands like the above to calculate the order of I and the orbit of "b" under I:
  
  I.order()
  I.orbit(b)
  
  
• Once we have constructed a permutation group in SAGE, we can test whether permutations are in that group by asking SAGE to intepret the permutations as elements of the group. For example, to test whether permutations phi=(b c d) and psi=(a e)(b f) are in H:
  
  phi=S6([(b,c,d)])
  H.has_element(phi)
  
  psi=S6([(a,e),(b,f)])
  H.has_element(psi)
  
  
• When a permutation (like phi above) is in fact an element of a permutation group (like H), SAGE can also show to how to write the permutation in terms of the generators of the group (namely sigma and tau).
  
  H(phi).word_problem(H.gens(),False)
  
  The first component of the output will be an expression like:
  
  x2^-1*(x1^-1*x2)^2*x1^-1*x2^-1*x1^-1
  
  Here x1 and x2 refer to the first and second generators of the subgroup H, respectively. Since SAGE may have reordered the generators, we can confirm the order by:
  H.gens()[0]==tau
  H.gens()[1]==sigma
  
  Since both of these commands return True, it means that the order of the generators is [tau,sigma]. Thus x1corresponds to tau and x2 to sigma. (Annoyingly, the x variables are indexed starting at 1 while the H.gens() list of generators is indexed starting at 0.) We can check the output of the word_problem command as follows:
  
  phi==sigma^(-1)*(tau^(-1)*sigma)^2*tau^(-1)*sigma^(-1)*tau^(-1)
  
  (A convenient way to generate the expression on the right-hand side here is to cut & paste the formula with the x variables into a word processor and do a search & replace to change x1 to tau and x2 to sigma. It is also important to manually add parentheses around the negative exponents.)
  
  Note that word_problem does not in general produce the shortest or simplest expression in terms of the generators. In particular, the following is a simpler expression for phi:
  
  phi==sigma^(-2)*(tau*sigma)^2
  
  It is unlikely that there is a polynomial-time algorithm for finding the shortest expression of a permutation in terms of a set of generators. (This problem is known to be "NP-hard").
  
  
• Feel free to use other SAGE functions from the following pages, if you find them useful. (But the above ones should suffice for the homework problem.)
  http://doc.sagemath.org/html/en/thematic_tutorials/group_theory.html
  http://doc.sagemath.org/html/en/reference/groups/sage/groups/perm_gps/permgroup.html
  

PS5 Tips

• To get the problem data p, q, and c, follow these instructions:
  
  1) Download the files ps5data.csv  from Canvas under Files.
  2) Upload ps5data.csv  to your Cocalc workspace.
  3) Run the following commands to get the data  p, q, and c:
  
  import sympy as sp
  import pandas as pd
  
  ABC = pd.read_csv("ps5data.csv",delimiter="\n",header=None).as_matrix()
  data = sp.sympify(ABC[0][0])
  
  p = Integer(int(data[0]));
  q = Integer(int(data[1]));
  c = [Integer(int(data[2][i])) for i in range(8)];
  
  
• On this problem set, you may use the xgcd function in addition to commands you have used on previous problem sets. The command
  
  d,s,t = xgcd(x,y)
  
  will set d to be the gcd of the integers x and y, and s and t to be integers such that d=sx+ty.

PS8 Tips

On this problem, you will see how to use SAGE to solve problems in polynomial rings. 

• Download the file ps8data.csv from Canvas, and add it to the same path in Cocalc as your sagews file. Run the following commands to read the file and also define a function that will be useful in solving the problem.
  import sympy as sp 
• import pandas as pd 
• coeffs_q = pd.read_csv("ps8data.csv",delimiter="\n",header=None).as_matrix() 
• coeffs_q = sp.sympify(coeffs_q[0][0]) 
• coeffs = coeffs_q[:-1] 
• coeffs = [int(c) for c in coeffs] 
• q = int(coeffs_q[-1]) 
• F = GF(q) 
• R.<x> = F[] 
• f = sum([coeffs[k]*x^k for k in range(9)])
•        
• def Fpow(f,h,m):
•     b = bin(m)[2:]
•     n = len(b)
•     poly = h.quo_rem(f)[1]
•     remainder = 1
•     for i in range(1,n):
•         if int(b[-i]) == 1:
•             remainder = (remainder*poly).quo_rem(f)[1]
•         poly = (poly^2).quo_rem(f)[1]
•     return (remainder*poly).quo_rem(f)[1]
  
• After running the above code, q will hold the value of a large prime, F will be the finite field Z_q, R will be the polynomial ring F[x], and f will be a polynomial in F[x]. Your task is to find all the roots of f using the algorithm described in Problem 4.
  
  
• When working within R, arithmetic is done on the coefficients modulo q. For example, typing f+q you'd get f again.
  
  
• Functions that you may use for computing on polynomials g,h in R (in addition to functions you've used on previous problem sets):
• g.degree(): returns the degree of g. SAGE defines the degree of the zero polynomial to be -1. 
• g(a) returns the evaluation of g at a for any value a in the field F. 
• g.quo_rem(h) returns a list [quotient,remainder] containing the polynomials in R that are the quotient and remainder when g is divided by h.
• gcd(g,h) returns the polynomial that is the greatest common divisor of g and h. 
• Fpow(g,h,m) returns g^m mod h, for a nonnegative integer m and a nonzero polynomial h. It is calculated using an efficient algorithm that can handle very large exponents m (running in time polynomial in the bitlength of m). [This is the function defined in the code we provide above.]
• F.random_element() returns a uniformly random element of the field F.
  
  

PS9 Tips

Download the files  ps9data.csv  and ps9.sagews  from Canvas and upload them to CoCalc.  Open ps9.sagews, click 'Run,' and then you can continue your work at the bottom of the worksheet.  After doing that, several useful variables and functions that you will need will have been defined:

• n=128 and k=32 
• F=a field of size n
• r=a received word as a 128-character ASCII string
  
• Index2Field(i)=a function that takes an integer i  from 0 to 127 and returns the i'th element of the field (according to a fixed ordering).
• Field2Index(field_element)=the inverse of the function Index2Field
• ASCII2Field(S)  takes an ASCII string S and returns a list L  of corresponding field elements. That is, L[i] equals Index2Field(j) where the j is such that j'th ASCII character is S[j].
• Field2ASCII  is the inverse of the function ASCII2Field.
• solve(M) takes a matrix M of elements of F and outputs a nonzero vector v such that Mv=0 if one exists.
  

To make use of solve(M), the following functions for constructing matrices will be helpful.

• M = Matrix(F,[row_1,row_2,…,row_k]) generates a matrix of k rows of elements in F where row_i, for k=1,…,k, is a list of elements of F (all rows must be lists of the same size). Below are some examples:
• M1 = Matrix(F,[[Index2Field(0), Index2Field(5)],[Index2Field(1),Index2Field(0)]])  generates a 2x2 matrix of elements in F where the first row contains the 0'th and 5'th elements of the field and the second row contains the 1st and 0'th elements of the field.   
• M2 = Matrix(F,[[Index2Field(i)/Index2Field(j) for j in range(10)] for i in range(n)]) generates nx10 matrix whose (i,j)'th entry is the ratio of the i'th and j'th elements of the field.
• M3 = Matrix(F,[[Index2Field(i)/Index2Field(j) for j in range(10)]+[Index2Field(i)+Index2Field(j) for j in range(10)] for i in range(n)]) generates nx20 matrix where the first 20 columns are as in M2 and the next 10 columns form a matrix whose (i,j)'th entry is the sum of the i'th and j'th elements of the field.
• Some useful operations on polynomials:
• sum([coeff[i]*x^i for i in range(k)]) converts a list coeff of elements from F into a polynomial of degree at most k-1 where coeff[i] is the coefficient of x^i.
• g.quo_rem(h) returns a list [quotient,remainder] containing the polynomials in F[x] that are the quotient and remainder when g is divided by h.
• g.coefficients() returns a list of all the coefficients of the polynomial g.
  

Finally, if you want to play around with encoding messages on your own, corrupting them, and trying to decode them, you can use the following functions we have defined:

• RS_encoding(message)=a function that takes a 32-character string message and outputs its Reed-Solomon encoding as a string of length 128.
• corrupt_string(codeword,t) takes a string codeword and outputs a string obtained by replacing t of the characters with randomly chosen characters. 
• corrupt_string2(codeword,i,c) takes a codeword and outputs a string where the i’th character is replaced with the character c.