MacTutor logo MacTutor

Solution: Day 3, problem 3

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

Another proof is to note that h(x)=F(x)2+O(xm)h(x) = F(x)^{2} + O(x^{m}) in Fp[[x]]\mathbb{F}_{p}[[x]], where F(x)=√(1/2+√(1−x)/2)=1−1/8x−5/128x2−...F(x) = √(1/2 + √(1 - x)/2) = 1 - 1/8x - 5/128x^{2} - ... in Z[12][[x]]\mathbb{Z}[{{1}\over{2}}][[x]].
From the differential equation x(1−x)F′′+(1/2−x)F′+116F=0x(1 - x)F'' + (1/2 - x)F' + {{1}\over{16}} F = 0 we find that the coefficient of xnx^{n} in FF equals −21−4nbinom(4n−3,2n−1)/n-2^{1-4n} binom(4n - 3, 2n - 1)/n, which is 0 modulo pp for N < n < m. Hence F(x)=f(x)+O(xm)F(x) = f(x) + O(x^{m}) for some polynomial f(x)f(x) in Fp[x]\mathbb{F}_{p}[x] of degree ≤ NN. From h(x)=f(x)2modxmh(x) = f(x)^{2} mod x^{m} and deg⁡(h)=2N≤m\deg(h) = 2N ≤ m it immediately follows that h=f2h = f^{2} if mm is odd, while for mm even we must use the above formula for the coefficients of f(x)f(x) to verify that the leading coefficients of h(x)h(x) and f(x)2f(x)^{2} are both 1.

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