MACM 401/MATH 701/MATH 801 Assignment 4, Spring 2023.
Michael Monagan
Due Monday March 13th at 11pm. You may use Maple for all calculations unless asked to do the question by hand. For problems involving Maple calculations and Maple programming, please upload a printout of a Maple worksheet.
Late Penalty: −20% for up to 24 hours late. Zero after that.
Question 1: P-adic Lifting (20 marks) Reference: Section 6.2 and 6.3.
(a) By hand, determine the p-adic representation of the integer u = 116 for p = 5, first using the positive representation, then using the symmetric representation for Z5.
(b) Theorem 2: Let u, p ∈ Z with p > 2. For simplicity assume p is odd.
If −pn < u < pn there exist unique integers u0,u1,...,un−1 such that u = u0 + u1p + ··· +
Prove uniqueness.
(c) Determine the cube-root, if it exists, of the following polynomials
a(x) = x6 − 531x5 + 94137x4 − 5598333x3 + 4706850x2 − 1327500x + 125000, b(x) = x6 −406x5 +94262x4 −5598208x3 +4706975x2 −1327375x+125125
using reduction mod 5 and linear p-adic lifting. You will need to derivive the update formula by modifying the update formula for computing the a(x).
Factor the polynomials so you know what the answers are. Express your the answer in the p-adic representation. To calculate the initial solution u0 = √3 a mod 5 use any method. Use Maple to do all the calculations.
Question 2: Hensel lifting (15 marks)
Reference: Section 6.4 and 6.5. (a) Given
a(x) = x4 −2x3 −233x2 −214x+85 u0(x)=x2 −3x−2 and w0(x)=x2 +x+3,
satisfying a ≡ u0 w0 (mod 7), lift the image polynomials using Hensel lifting to find (if there exist) u and w in Z[x] such that a = uw.
2n−1 2p p un−1p and −2 < ui < 2.
and image polynomials
浙大学霸代写 加微信 cstutorcs
and an image polynomials
satisfying b ≡ 6 u0 w0 (mod 7), lift the image polynomials using Hensel lifting to find (if there exist) u and w in Z[x] such that b = uw.
Question 3: Determinants (25 marks)
Consider the following 3 by 3 matrix A of polynomials in Z[x] and its determinant d. > P := () -> randpoly(x,degree=2,dense):
> A := Matrix(3,3,P);
−55−7×2 +22x −56−94×2 +87x 97−62x A:= −83−73×2 −4x −82−10×2 +62x 71+80×2 −44x
−10−17×2 −75x 42−7×2 −40x 75−50×2 +23x > d := LinearAlgebra[Determinant](A);
d:=−224262−455486×2 +55203x−539985×4 +937816×3 +463520×6 −75964×5
(a) (15 marks) Let A by an n by n matrix of polynomials in Z[x] and let d = det(A). Develop a modular algorithm for computing d = det(A) ∈ Z[x]. Your algorithm will compute determi- nants of A modulo a sequence of primes and apply the CRT. For each prime p it will compute the determinant in Zp[x] by evaluation and interpolation. In this way we reduce computation of a determinant of a matrix over Z[x] to many computations of determinants of matrices over Zp, a field, for which ordinary Gaussian elimination, which does O(n3) arithmetic operations in Zp, may be used.
You will need bounds for deg d and ||d||∞. Use primes p = [101, 103, 107, …] and use Maple to do Chinese remaindering. Use x = 1, 2, 3, … for the evaluation points and use Maple for the interpolations.
Present your algorithm as a homomorphism diagram.
Implement your algorithm in Maple and test it on the above example.
To reduce the coefficients of the polynomials in A modulo p in Maple use > B := A mod p;
To evaluate the polynomials in B at x = α modulo p in Maple use
> C := Eval(B,x=alpha) mod p;
To compute the determinant of a matrix C over Zp in Maple use > Det(C) mod p;
b(x) = 48×4 −22×3 +47×2 +144 u0(x)=x2 +4x+2 and w0 =x2 +4x+5
Programming Help
(b) (10 marks) Suppose A is an n by n matrix over Z[x] and Ai,j = dk=0 ai,j,kxk and |ai,j,k| < Bm. That is A is an n by n matrix of polynomials of degree at most d with coefficients at most m base B digits long. Assume the primes satisfy B < p < 2B and that arithmetic in Zp costs O(1). Estimate the time complexity of your algorithm in big O notation as a function of n, m and d. Make reasonable simplifying assumptions such as n < B and d < B as necessary. State your assumptions. Also helpful is
lnn!
Question 4: Lagrange Interpolation (20 marks)
In class we stated the following theorem for polynomial interpolation.
Theorem: Let F be a field. Let (x1,y1),(x2,y2),…,(xn,yn) be n points in F2. If the xi are distinct there exists a unique polynomial f(z) in F[z] satisfying deg(f) ≤ n−1 and f(xi) = yi for 1 ≤ i ≤ n.
Lagrange interpolation is an O(n2) algorithm for computing f(z). It does 1. Expand the product M(z) = ni=1(z − xi).
2. SetLi(z)=M(z)/(z−xi)for1≤i≤n.
3. Setαi =Li(xi)for1≤i≤n.
4. Setβi =yi·α−1 for1≤i≤n. i
5. Set f = ni=1 βiLi(z).
(a) For F = Z7, x = [1, 2, 3, 4] and y = [0, 5, 5, 0], use Maple’s Interp(x,y,z) mod p; command to find f(z). Now, using Maple as a calculator, execute Steps 1 to 5 to find the interpolating polynomial f(z). I suggest you use Arrays for L, α and β.
(b) Write a Maple procedure INTERP(x,y,z,p) that uses Lagrange interpolation to interpolate f(z) for the field F = Zp, that is, for the integers modulo p. Please print out the Li polyno- mials. Test your Maple procedure on the example in part (a).
(c) Show that Steps 1,2,3, and 5 do O(n2) multiplications in F. Since Step 4 does n multiplica- tions and n inverses in F, conclude that Lagrange interpolation does O(n2) multiplications in F . Please note the following. An obvious way to code Step 1 in Maple for F = Z7
> M := z-x[1] mod p;
> for i from 2 to n do M := Expand((z-x[i])*M) mod p; od;
In the loop, at step i, this multiplies (z−xi) by M where M = i−1 (z−xk) = zi−1+i−2 bkzk
for some coefficients bk ∈ F. This multiplication is special because the factors (z − xk) and M are both monic. To minimize the number of multiplications in F we can use
i−2 i−2 i−2 (z−xk)(zi−1 +bkzk)=zi +bkzk+1 −xkzi−1 −(xk ·bk)zk
k=0 k=0 k=0 which needs only i − 1 multiplications xk · bk in F .
Github