HMMT 二月 2014 · 代数 · 第 10 题

英文解析

10. For an integer n , let f ( n ) denote the number of positive integers d ≤ 9 dividing n . Suppose that m is
    ∑9
    a positive integer and b , b , . . . , b are real numbers such that f ( n ) = b f ( n − j ) for all n > m .m
    1 2 m 9 j 9
    j =1
    Find the smallest possible value of m .
    Answer: 28 Let M = 9. Consider the generating function
    M Md
    ∑ ∑ ∑ ∑
    n dkx
    F ( x ) = f ( n ) x = x = .
    1 − xd mn ≥ 1
    d =1 k ≥ 1 d =1
    Observe that f ( n ) = f ( n + M !) for all n ≥ 1 (in fact, all n ≤ 0 as well). Thus f ( n ) satisfies a
    M M Mdegree m linear recurrence if and only if it eventually satisfies a degree m linear recurrence. But thelatter occurs if and only if P ( x ) F ( x ) is a polynomial for some degree m polynomial P ( x ). (Why?)
    Suppose P ( x ) F ( x ) = Q ( x ) is a polynomial for some polynomial P of degree m . We show that x − 1 |s
    P ( x ) for s = 1 , 2 , . . . , M , or equivalently that P ( ω ) = 0 for all primitive s th roots of unity 1 ≤ s ≤ M ).
    Fix a primitive s th root of unity ω , and define a functiond d
    ∑ ∑
    z z − 1
    F ( z ) = (1 − ω z ) +
    d − 1 − 1 d − 1ω
    1 − z 1 + ( ω z ) + · · · + ( ω z )
    s | d ≤ Ms ∤ d ≤ Mfor all z where all denominators are nonzero (in particular, this includes z = ω ).
    − 1 1 2 M
    Yet F ( z ) − F ( z )(1 − ω z ) = 0 for all complex z such that z , z , . . . , z 6 = 1, so P ( z ) F ( z ) − Q ( z )(1 −
    ω ω − 1 − 1
    ω z ) = 0 holds for all such z as well. In particular, the rational function P ( x ) F ( x ) − Q ( x )(1 − ω x )
    has infinitely many roots, so must be identically zero once we clear denominators . But no denominatorωvanishes at x = ω , so we may plug in x = ω to the polynomial identity and then divide out by the − 1
    original (nonzero) denominators to get 0 = P ( ω ) F ( ω ) − Q ( ω )(1 − ω ω ) = P ( ω ) F ( ω ). However,
    ω ωd
    ∑ ∑
    ω 1
    F ( ω ) = =
    − 1 − 1 d − 1ω
    1 + ( ω ω ) + · · · + ( ω ω ) ds | d ≤ M s | d ≤ Mis a positive integer multiple of 1 /d , and therefore nonzero. Thus P ( ω ) = 0, as desired.
    Conversely, if x − 1 | P ( x ) for s = 1 , 2 , . . . , M , then P ( x ) will clearly suffice. So we just want thessdegree of the least common multiple of the x − 1 for s = 1 , 2 , . . . , M , or just the number of roots of
    ∑
    unity of order at most M , which is φ ( s ) = 1 + 1 + 2 + 2 + 4 + 2 + 6 + 4 + 6 = 28.Ms =1
    Comment: Only at the beginning do we treat F ( x ) strictly as a formal power series; later once we get
    ∑
    6 dxthe rational function representation , we can work with polynomial identities in general anddd =1
    1 − xdon’t have to worry about convergence issues for | x | ≥ 1.