Solution: Day 3, problem 3


Let h(x) = [ 1 + xm + (1 - x)m]/2 be a polynomial in Fp[x]. Each number a in Fp such that both a and 1 - a are quadratic non - residues modulo p is a root of both hp(x) and hp'(x), and there are exactly N = [ m/2] such numbers. (Counting them is easily seen to be equivalent tocounting elements a in Fp - {0, 1} for which both a and a - 1 are quadratic residues, and such a are parametrized by a = (t + t-1)2/4 for t in Fp with t2 ≠ -1 mod p.) But hp has degree 2N and constant term 1, so we must have that hp(x) is the product over a of (1 - x/a)2.

Another proof is to note that h(x) = F(x)2 + O(xm) in Fp[[x]], where F(x) = √(1/2 + √(1 - x)/2) = 1 - 1/8x - 5/128x2 - ... in Z[1/2][[x]].
From the differential equation x(1 - x)F'' + (1/2 - x)F' + 1/16 F = 0 we find that the coefficient of xn in F equals -21-4n binom(4n - 3, 2n - 1)/n, which is 0 modulo p for N < n < m. Hence F(x) = f(x) + O(xm) for some polynomial f(x) in Fp[x] of degree ≤ N. From h(x) = f(x)2 mod xm and deg(h) = 2Nm it immediately follows that h = f2 if m is odd, while for m even we must use the above formula for the coefficients of f(x) to verify that the leading coefficients of h(x) and f(x)2 are both 1.

A third proof, provided during the Colloquium, is even simpler: the product of h(x) and g(x) = [ 1 + xm - (1 - x)m]/2 in Fp[x] is x(1 - xm)2/4, which is x times a square. Since the polynomials f(x) and g(x)/x are coprime, they must both be squares (up to a common scalar multiple, but in fact without it since f(0) = 1).