MACM 401/MATH 801/CMPT 891 Assignment 4, Spring 2021.
Michael Monagan
Due Monday March 15th 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, you should submit a printout of a Maple worksheet of your Maple session.
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
1
(b) Given
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 interpolation. Implement your algorithm in Maple and test it on the above example.
To reduce the coefficients of the polynomials in A modulo p = 7 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
2
(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!
Let p be an odd prime and let a(x) = a0 +a1x+…+anxn ∈ Zp[x] with a0 ̸= 0 and an ̸= 0. Suppose √a0 = ±u0 mod p. The goal of this question is to design an x-adic Newton iteration algorithm that given u0, determines if u = a(x) ∈ Zp[x] and if so computes u.
(a) Let
Derive the Newton update formula for uk. Show your working.
(b) Now test your update formula on the two polynomials a1(x) and a2(x) below using p = 101 and u0 = +5. Please print out the sequence of values of u0, u1, u2, … as you compute them. Note, one of the polynomials has a √ in Zp[x], the other does not. So you will need to work out when the algorithm should stop lifting.
Do all calculations in Maple.
a1 =81×6 +16×5 +24×4 +89×3 +72×2 +41x+25
a2 =81×6 +46×5 +34×4 +19×3 +72×2 +41x+25
u=u0 +u1x+…+uk−1xk−1 +ukxk +…
3