Let p > 3 be a prime. Let h be the number of sequences a1, a2, ... , ap-1 such that a1 + 2a2 + 3a3 + ... + (p-1)ap-1 is divisible by p and each ai is 0, 1 or 2. Let k be defined similarly except that each ai is 0, 1 or 3. Show that h <= k with equality iff p = 5.
Solution
Let f(x) = (1 + x + x2)(1 + x2 + x4)(1 + x3 + x6) ... (1 + xp-1 + x2(p-1)). Let cn be the coefficient of xn when f(x) is expanded. Then cn is the number of solutions to a1 + 2a2 + 3a3 + ... + (p-1)ap-1 = n, where ai = 0, 1 or 2. So h = cp + c2p + c3p + ... .
Take z to be a complex pth root of 1. Then 1 + z + z2 + ... + zp-1 = 0 and hence 1 + zn + z2n + ... + zn(p-1) = p if p divides n and 0 otherwise. So f(1) + f(z) + f(z2) + ... + f(zp-1) = ph. But f(1) = 3p-1.
f(z) = ( (z3-1)/(z-1) ) ( (z6-1)/(z 2-1) ) ... (z3(p-1)-1)/(zp-1-1). But the numerators are just a permutation of the denominators, so f(z) = 1. Similarly for f(zn) for n < p. Hence ph = 3p-1 + (p-1), or h = (3p-1 + p - 1)/p.
Similarly, we may define g(x) = (1 + x + x3)(1 + x2 + x6)(1 + x3 + x9) ... (1 + xp-1 + x3(p-1)). Then if dn is the coefficient of xn we have that dn is the number of solutions to a1 + 2a2 + 3a3 + ... + (p-1)ap-1 = n, where ai = 0, 1 or 3. So k = dp + d2p + d3p + ... . Taking z as before we find that pk = 3p-1 + (p-1) g(z) (*).
However, in this case, we do not in general have g(z) = 1. We gave to show that g(z) ≥ 1, with equality iff p = 5. The definition of g(z) shows that it is an integral sum a + bz + cz2 + dz3 + e z4. But (*) shows that g(z) is real, so we must have a' + bz + cz2 + dz3 + ez4 = 0. But z cannot satisfy an equation of degree lower than 4, because it could be any of the 4 complex roots of 1. Hence b = c = d = e. So g(z) = a - b, which is integral. Obviously p does not divide 3p-1 so g(z) cannot be zero. So if we can show that g(z) is non-negative, then it will follow that g(z) ≥ 1. But that is easy because the factors (1 + zm + z3m) and (1 + zp-m + z3(p-m)) = (1 + z-m + z-3m) are complex conjugates and hence their product is non-negative (for any complex number v, the product of v and its complex conjugate is |v|2).
So we have established that h ≤ k.
It is easy to verify directly that g(z) = 1 for p = 5: (1 + z + z3)(1 + z2 + z6) = - z4 (using z5 = 1 and 1 + z + z2 + z3 + z4 = 0), and (1 + z3 + z9)(1 + z4 + z12) = - z, and hence g(z) = 1. Proving that g(z) > 1 for p > 5 is significantly harder.
Let t, u, v be the roots of 1 + x + x3 = 0, where t is real, and u, v are complex conjugates. We show by induction on n that for any non-negative integer n, tn + un + vn is an integer. It is obvious for n = 0 and true for n = 1, because t + u + v = 0. Also tu + uv + vt = 1, so t2 + u2+ v2 = (t + u + v)2 - 2(tu + uv + vt) = -2, so it is true for n = 2. But now we have t3 + t + 1 = u3 + u + 1 = v3 + v + 1 = 0. Hence (tn+3 + un+3 + vn+3) = - (tn+1 + un+1 + vn+1) - (tn + un + vn), so if it is true for n and n+1, then it is true for n+3. Hence it is true for all n.
We have g(z) = ∏ (1 + zm + z3m) = ∏ (zm - t)(zm - u)(zm - v). But P (zm - t) = (tp - 1)/(t - 1). Similarly for u and v. Also (t - 1)(u - 1)(v - 1) = - (1 - t)(1 - u)(1 - v) = 1 + 1 + 13 = 3. Hence if g(z) = 1, then (tp - 1)(up - 1)(vp - 1) = -3 (*). We will use this to obtain a contradiction.
We have that tp + up + vp = N for some integer N. We also have that tpupvp = (tuv)p = -1. Hence exanding (*) gives that tpup + upvp + vptp = N+1. So tp, up, vp are the roots of the cubic x3 - Nx2 + (N+1)x + 1 = 0. The real root t must lie between -½ and -1, since -½3 + (-½) + 1 = 3/8 and -13 + (-1) + 1 = -1. If N < 0, then we have (N+1) ≤ 0 and hence for x = tp we have (N+1)x ≥ 0 and x3 - Nx2 > 0, so x3 - Nx2 + (N+1)x + 1 > 1. Contradiction. If N = 0, then, tp, up, vp are roots of x3 + x + 1 = 0, so they must be a permutation of t, u, v. But since |t| < 1 and |u| = |v|, we have |u|, |v| > 1 and hence |t|p < |t| < 1 < |u| < |u|p (and similarly for v), so tp = t. Hence p = 1. Contradiction. So N > 0 and hence N ≥ 1.
For x between -1 and 0, x3 + x + 1 is strictly increasing and N(x2 - x) is strictly decreasing and they intersect at x = tp. As p increases this point gets closer to 0, so N must strictly increase with p. We have (t3 + t + 1) = 0 and hence t2(t3 + t + 1) = 0, so t5 = -t3 - t2 = -t2 + t + 1 and similarly for u, v. So for p = 5, we have N = t5 + u5 + v5 = -(t2 + u2 + v2) + (t + u + v) + 3 = -(t2 + u2 + v2) + 3 = -(t + u + v)2 + 2(tu + uv + vt) + 3 = 5. So if p > 5, then N > 5. But it is easy to check that if N ≥ 6, then the polynomial x3 - Nx2 + (N+1)x + 1 has three distinct real roots. (Its value is negative at x = -1 and 2, and positive at x = 0 or sufficiently large). But two of its roots are up and vp, which are complex conjugates, so if they are real, then they must be equal. Contradiction. Thus we cannot have p > 5 and g(z) = 1.
Comment. This may seem unreasonably hard. That is true for anyone who is not familiar with (1) generating functions, and (2) complex nth roots z of 1 and the fact that 1 + z + z2 + ... + zn-1 = 0. Obviously (2) is a fairly elementary idea, which is easy to prove, but you need to be familiar with the fact that it is a standard trick for summing series. Given those prerequisites, the question is hard, but not unreasonably so.
© John Scholes
jscholes@kalva.demon.co.uk
23 Dec 2002
Last corrected/updated 23 Dec 02