HMMT 二月 2019 · 团队赛 · 第 9 题
HMMT February 2019 — Team Round — Problem 9
题目详情
- [ 55 ] Let p > 2 be a prime number. F [ x ] is defined as the set of all polynomials in x with coefficients p in F (the integers modulo p with usual addition and subtraction), so that two polynomials are equal p k if and only if the coefficients of x are equal in F for each nonnegative integer k . For example, p 2 ( x + 2)(2 x + 3) = 2 x + 2 x + 1 in F [ x ] because the corresponding coefficients are equal modulo 5. 5 Let f, g ∈ F [ x ]. The pair ( f, g ) is called compositional if p 2 p f ( g ( x )) ≡ x − x in F [ x ]. Find, with proof, the number of compositional pairs (in terms of p ). p
解析
- [ 55 ] Let p > 2 be a prime number. F [ x ] is defined as the set of all polynomials in x with coefficients p in F (the integers modulo p with usual addition and subtraction), so that two polynomials are equal p k if and only if the coefficients of x are equal in F for each nonnegative integer k . For example, p 2 ( x + 2)(2 x + 3) = 2 x + 2 x + 1 in F [ x ] because the corresponding coefficients are equal modulo 5. 5 Let f, g ∈ F [ x ]. The pair ( f, g ) is called compositional if p 2 p f ( g ( x )) ≡ x − x in F [ x ]. Find, with proof, the number of compositional pairs (in terms of p ). p Proposed by: Ashwin Sah Answer: 4 p ( p − 1) 2 Solution 1. First, notice that (deg f )(deg g ) = p and both polynomials are clearly nonconstant. 2 2 Therefore there are three possibilities for the ordered pair (deg f, deg g ), which are (1 , p ) , ( p , 1), and ( p, p ). In the subsequent parts of the solution, equalities are modulo p . If f ( x ) = ax + b, a 6 = 0 is linear, 2 p x − x − b − 1 then it is invertible so then g is uniquely determined as g ( x ) = f ( f ( g ( x ))) = . Similarly, a − 1 if g ( x ) = cx + d, c 6 = 0 (mod p ) is linear then f is uniquely determined as f ( x ) = f ( g ( g ( x ))) = 2 ( ) ( ) p x − d x − d − . In each case there are p ( p − 1) compositional pairs. c c The last case is deg f = deg g = p . We take the derivative of both sides (we use the formal derivative ∑ n − 1 D f ( x ) = nf x , which satisfies the usual chain and product rules but can be used on x n n ≥ 1 arbitrary polynomials, including those in F [ x ]). p Thus 2 ′ ′ 2 p − 1 f ( g ( x )) g ( x ) = p x − 1 = − 1 , ′ ′ using that p = 0 in F . Now g ( x ) and f ( g ( x )) must both be constant polynomials. Since g is p ′ nonconstant, this means that f ( x ) is also a constant polynomial. We must be careful here, as unlike in R , nonlinear polynomials can have constant derivatives. From the formula of derivative, we see that ′ p 2 p h ( x ) = 0 as a polynomial exactly when h ( x ) is a linear combination of 1 , x , x , . . . (remember that ′ ′ p = 0). Thus f , g both being constant and f, g being of degree p tells us p p f ( x ) = ax + bx + c, g ( x ) = dx + ex + f where a, b, c, d, e, f are some elements of F . Now we must have p 2 p p p p a ( dx + ex + f ) + b ( dx + ex + f ) + c = x − x p p p over F [ x ]. We use the fact that ( x + y ) = x + y as polynomials in F , since the binomial coefficients p p ( ) p p p p p ≡ 0 (mod p ) for 1 ≤ j ≤ p − 1. This implies ( x + y + z ) = x + y + z . Therefore we can expand j the previous equation as 2 2 p p p p p p p a ( d x + e x + f ) + b ( dx + ex + f ) + c = x − x. Equating coefficients, we see that p ad = 1 , p ae + bd = 0 , be = − 1 , p af + bf + c = 0 . − p − 1 The first and third equations imply that a, d, b, e are nonzero (mod p ) and a = d , b = − e . Then p ae + bd = 0 gives − p p − 1 d e − e d = 0 p +1 p +1 p − 1 p − 1 2 2 or e = d . Recalling that e = d = 1 in (mod p ), this tells us d = e so d = ± e . Furthermore, any choice of such ( d, e ) give unique ( a, b ) which satisfy the first three equations. Finally, once we have determined a, b, d, e , any choice of f gives a unique valid choice of c . Thus we have p − 1 choices for d , two choices for e after choosing d (n.b. for p = 2 there is only one choice for e , so the assumption p > 2 is used here), and then p choices for f , for a total of 2 p ( p − 1) compositional pairs in this case. Finally, adding the number of compositional pairs from all three cases, we obtain 4 p ( p − 1) compositional pairs in total. Solution 2. The key step is obtaining p p f ( x ) = ax + bx + c, g ( x ) = dx + ex + f in the case where deg f = deg g = p . We present an alternative method of obtaining this, with the rest of the solution being the same as the first solution. Let p p − 1 f ( x ) = f x + f x + · · · + f p p − 1 0 p p − 1 g ( x ) = g x + g x + · · · + g p p − 1 0 p p where f , g are nonzero. Like before, we have g ( x ) = g ( x ) in F [ x ], so p p p 2 p p p − 1 x − x = f g ( x ) + f g ( x ) + · · · + f . p p − 1 0 p Consider the maximal k < p for which f 6 = 0. (It is not hard to see that in fact k ≥ 1, as f g ( x ) + f k p 0 2 p kp − 1 cannot be x − x .) First assume that k > 1. We look at the x coefficient, which is affected only k k − 1 by the f g ( x ) term. By expanding, the coefficient is kf g g . Therefore g = 0. Then we look k k p − 1 p − 1 p kp − 2 kp − 3 kp − p +1 at the x coefficient, then the x coefficient, etc. down to the x coefficient to conclude that g = g = · · · = g = 0. However, then the x coefficient of f ( g ( x )) is zero, contradiction. p − 1 p − 2 1 p Therefore we must have k = 1, so f is of the form ax + bx + c . Using the same method as we used kp − p +1 when k > 1, we get g = g = · · · g = 0, though the x coefficient is now the x coefficient p − 1 p − 2 2 which we want to be nonzero. Hence we do not obtain g = 0 anymore and we find that g is of the 1 p form dx + ex + f .