NPTEL Computational Number Theory and Algebra Assignment 8 Answer

Let f be any degree d, n-variate polynomial over an infinite field FF. What is the maximum number of roots of f in FnFn and what is the maximum number of irreducible factors of f in F[x1,x2,…,xn]F[x1,x2,…,xn], respectively?

Let the density of roots of a polynomial over a set T of tuples be defined as the number of roots in the set T divided by the size of set T. Let a be the density of roots of f=x2−y2f=x2−y2 over the set T={0,1,2}×{0,1,2}T={0,1,2}×{0,1,2}. Let b be the upper bound on density of roots obtained from Polynomial Identity Lemma covered in class (the probability). What are the values of a,b respectively?

Which of the following is true for f(x,y):=x2+xy+1f(x,y):=x2+xy+1 with coefficients in the finite field FpFp?

1. ff is almost-monic in xx.

2. ff is almost-monic in yy.

Let f(x):=x2+6f(x):=x2+6 be a univariate polynomial in Z[x]Z[x]. For what value of prime pp, Hensel’s lifting is applicable to fmodpfmodp?

1. Hilbert’s irreducibility theorem relates factoring a general multivariate polynomial to factoring a low-variate polynomial.

2. Kaltofen’s blackbox multivariate factoring algorithm runs in deterministic polynomial time.