MA522, Fall 2018, Homework 2:
(Problems 1 and 2 due Mon, Nov 19, 4:59pm,
Problem 3 due Mon Dec 3, 4:59pm,
by email or in my mailbox in SAS 3151).

Problem 1 (the discriminant of a polynomial):
Consider a polynomial f(x) = (x - y_1) ... (x - y_n) =
x^n + a_{n-1}x^{n-1} + ... + a_0, where a_i \in K[y_1,...,y_n]
with K a field.  Note that the a_i are plus/minus the symmetric
functions in y_i.

The discriminant of f is defined as

   disc_x(f) = \prod_{1 <= i < j <= n} ( (y_i - y_j) (y_j - y_i) )

i) Show that disc_x(f) is a symmetric polynomial in the y_i, that is,
there is a polynomial \delta(z_{n-1},...,z_0) in K[z_{n-1},...,z_0]
such that \delta(a_{n-1},...,a_0) = disc_x(f).

ii) Show that \delta is irreducible in K[z_{n-1},...,z_0] for
fields of characteristic not equal 2, and a square of an irreducible
polynomial for fields of characteristic equal 2.

iii) Consider the (2n-1) by (2n-1) Sylvester-like matrix M formed with
the coefficient vector of f and f', the derivative of f w.r.t. x:

  f'(x) = n x^{n-1} + (n-1) a_{n-1}x^{n-2} + ... + a_1

Note that if the characteristic of the field K divides n, the first
coefficient, n, is equal 0, hence the matrix is not a true Sylvester
matrix.  Prove that det(M) = disc_x(f).  Note that the identity
is one in K[y_1,...,y_n].

Hint: prove that f'(x) = sum_i (x-y_1)...(x-y_{i-1})(x-y_{i+1})...(x-y_n).


Problem 1 (Bonus extension:
the third discriminant [https://arxiv.org/abs/1609.00840]):

The third discriminant of f is defined as

   disc3_x(f) = \prod_{1 <= i < j <= n,
                       i < k < \ell <= n,
                       j != k, j != \ell}
                ( y_i+y_j - (y_k+y_\ell) )

("!=" is "not equal";
 there are (n choose 4) [choose 4 roots]
          * 6           [choose negative signs for 2 roots]
          / 2           [i > k is - ( y_k + y_\ell - (y_i+y_j) )
                         matching     y_k + y_\ell - (y_i+y_j) ]
linear factors).

Note: the disc3(f) is zero if the average of two roots is equal
the average of another two distinct roots.

i) Show that disc3_x(f) is a symmetric polynomial in the y_i, that is, 
there is a polynomial \delta3(z_{n-1},...,z_0) in K[z_{n-1},...,z_0] 
such that \delta3(a_{n-1},...,a_0) = disc3_x(f).

ii) Show that \delta3 is irreducible in K[z_{n-1},...,z_0] for fields
of characteristic not equal 2.

iii) (Bonus to bonus) Give a formula using resultants/discriminants
for disc3(f)^2 with the a_i as inputs.


Problem 2 is Problem 6.33 [of the Exercises for Section 6]: intersection
of 2 planar curves. It may help to use Maple to compute the resultants.


Problem 3 [Zassenhaus, J. Number Theory, vol. 1, 1969]:
Let b \equiv a^2 (mod p) for a not equal 0,
p a prime >= 3.  We wish to factor x^2 - b in \ZZ_p[x].

(i) prove that for at least (p-1)/2 residues r in \ZZ_p, the residues
r+a mod p  and  r-a mod p  have opposite quadratic residuosity. [hint:
consider the range of the affine function z -> (z+a)/(z-a) [[Rabin]].]

(ii) prove that for at least (p-1)/2 residues r in \ZZ_p the GCD

     GCD( (x+r)^2 - b, (x^{(p-1)/2} - 1) mod ((x+r)^2 - b) )

in \ZZ_p[x] is nontrivial, hence x+r+a or x+r-a.

Can the GCD be computed as GCD(y^2-b, ((y-r)^{(p-1)/2}-1) mod (y^2-b))?
==================================================================================