Given positive integers a, b, c which are pairwise coprime. Let f(n) represent the number of nonnegative integer solutions (x,y,z) of the equation ax+by+cz=n. Prove: there exist real constants α, β, γ, such that for every nonnegative real number n, ∣f(n)−(αn2+βn+γ)∣<12a+b+c.
Solution
Consider the generating function of {f(n)}: G(t)=n=0∑∞f(n)tn=(1+ta+t2a+…)(1+tb+t2b+…)(1+tc+t2c+…)=(1−ta)(1−tb)(1−tc)1. Since a, b, c are pairwise coprime, the denominator (1−ta)(1−tb)(1−tc) contains no repeated factors other than (1−t)3. Let ω=e2πi/a, τ=e2πi/b, ρ=e2πi/c be the primitive a, b, cth roots of unity, respectively. Consider the partial fraction decomposition (1−ta)(1−tb)(1−tc)1=(1−t)h0+(1−t)2h1+(1−t)3h2+k=1∑a−11−ωktdk+k=1∑b−11−τktek+k=1∑c−11−ρktfk, in which the numerators h0, h1, h2, d1,…,da−1, e1,…,eb−1, f1,…,fc−1 are all complex numbers. To find dk in 1−ωktdk, multiply (1−ωkt) on both sides and let t→ω−k (or just let 1−ωkt=0). As all the other terms vanish, we arrive at dk=t→ω−klim(1−(ωkt)a)(1−tb)(1−tc)1−ωkt=a1×(1−ω−kb)(1−ω−kc)1. In the expansion of G(t), the coefficient of tn is f(n)=h0+h1×(n+1)+h2×2(n+1)(n+2)+k=1∑a−1dkωkn+k=1∑b−1ekτkn+k=1∑c−1fkρkn.
Observe that k=1∑a−1dkωkn≤k=1∑a−1∣dk∣=a1×k=1∑a−1∣1−ω−kb∣∣1−ω−kc∣1≤a1×k=1∑a−1∣1−ωk∣21=12aa2−1<12a. Here, the equality in the last row requires a lemma which will be proved. Likewise, we have in the following ∑k=1b−1ekτkn<12b and ∑k=1c−1fkρkn<12c. Taking β2=2h2, β1=h1+23h2, β0=h0+h1+h2, it follows that ∣β2n2+β1n+β0−f(n)∣≤k=1∑a−1dkωkn+k=1∑b−1ekτkn+k=1∑c−1fkρkn<12a+b+c.
Lemma (for the equality in the last row) For any positive integer m, k=1∑m−1sin2mkπ1=3m2−1 holds; equivalently, k=1∑m−1cot2mkπ=3m2−3m+2. Proof of lemma For ϑ∈A={mπ,m2π,…,m(m−1)π}, (cosϑ+isinϑ)m=cos(mϑ)+isin(mϑ)=±1, where the imaginary part Cm1sinϑcosm−1ϑ−Cm3sin3ϑcosm−3ϑ+Cm5sin5ϑcosm−5ϑ+⋯=0, or Cm1(cotϑ)m−1−Cm3(cotϑ)m−3+Cm5(cotϑ)m−5+⋯=0. This implies that {cotmkπ:k=1,2,…,m−1} satisfy the (m−1)th degree polynomial in cot ϑ. According to Viète's formulas, the sum of the m−1 roots is σ1=0 while the sum of their products multiplied in pairs is σ2=−Cm1Cm3=−6(m−1)(m−2). Consequently, the sum of the squares of the m−1 roots is k=1∑m−1cot2mkπ=σ12−2σ2=3m2−3m+2.□
Solution:
By symmetry, assume a≤b≤c. If a=b=c=1, f(n) is the number of ways of writing n as three nonnegative integers, which is Cn+22, and by taking α=21, β=23, γ=1, the error is constantly 0. In the following, assume c>1. For nonnegative integer m, let g(m) represent the number of nonnegative integer solutions (x,y) of ax+by=m. First, we try to find g(m). Let x≡ka(modb), m≡ℓb(moda), where k∈{0,1,…,b−1},ℓ∈{0,1,…,a−1}. Evidently, x≡k(modb), y≡ℓ(moda). Suppose x=k+ub, y=ℓ+va. Then m=ka+ℓb+(u+v)ab, giving u+v=abm−(ka+ℓb), and the number of pairs (u,v) is abm−(ka+ℓb)+1 (note that abm−(ka+ℓb) is an integer greater than −2; when abm−(ka+ℓb)=−1 the conclusion is still valid). Therefore, g(m)=abm−(ka+ℓb)+1. Next, consider f(n). In the Diophantine equation ax+by+cz=n, if z is given (cz≤n), then the number of nonnegative solutions of ax+by=n−cz is g(n−cz). Hence, f(n)=i=0∑⌊n/c⌋g(n−ic). For each integer i, define ki∈{0,1,…,b−1} and ℓi∈{0,1,…,a−1} such that n−ic=kia(modb),n−ic=ℓib(moda). We have f(n)=i=0∑⌊cn⌋g(n−ic)=i=0∑⌊cn⌋(ab(n−ic)−kia+ℓib+1)=⌊cn⌋⋅(abn+1)−2abc⌊cn⌋(⌊cn⌋+1)−b1i=0∑⌊cn⌋ki+a1i=0∑⌊cn⌋ℓi. Note that a, b, c are pairwise coprime. Hence, for i=0,1,…,b−1, the integers n−ic cover a complete system of residues modulo b; so do the integers kia and the integers ki. In addition, when i shifts by a multiple of b, ki does not change. Now we turn to ∑i=0⌊n/c⌋(ki−2b−1): notice that the summands add up to 0 as i goes over a complete system of residues modulo b. Therefore, ∑i=0⌊n/c⌋(ki−2b−1)=∑i=0s(ki−2b−1), where s is the least nonnegative residue of ⌊cn⌋ modulo b. In ∑i=0s(ki−2b−1), the summands are distinct and are all from {21−b,23−b,…,2b−3,2b−1} (the positive and negative elements are symmetric). This indicates that ∑i=0s(ki−2b−1) cannot exceed the sum of the positive elements 22+24+⋯+2b−3+2b−1=8b2−1 when b is odd, or 21+23+⋯+2b−3+2b−1=8b2 when b is even. Hence, i=0∑⌊n/c⌋(ki−2b−1)≤8b2.1◯ Likewise, i=0∑⌊n/c⌋(ℓi−2a−1)≤8a2.2◯ From ① and ②, it follows that b1i=0∑⌊cn⌋ki+b1i=0∑⌊cn⌋li−(⌊cn⌋+1)(2bb−1+2aa−1)≤b1i=0∑⌊cn⌋(ki−2b−1)+a1i=0∑⌊cn⌋(ℓi−2a−1)≤8b+8a.3◯ Let r be the least nonnegative residue of n modulo c. Then ⌊cn⌋⋅(abn+1)−2abc⌊cn⌋⋅(⌊cn⌋+1)−(⌊cn⌋+1)(2bb−1+2aa−1)=abc(n−r)(n+ab)−2abc(n−r)(n−r+c)−2abc(2ab−a−b)(n−r+c)=2abcn2−(a+b+c)n−(2abc+ac+bc)−r(r+a+b−c).4◯ As r takes values 0,1,…,c−1, denote the maximum and the minimum of r(r+a+b−c) as A+B and A−B, respectively. By ③ and ④, f(n)−2abcn2−(a+b+c)n−(2abc+ac+bc)−A≤8a+b+2abcB. Let α=2abc1, β=−2abca+b+c, γ=−2abc2abc+ac+bc+A. We will justify the problem statement ∣f(n)−(αn2+βn+γ)∣<12a+b+c5◯ for different a, b, c values. □
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: MathNet,
licensed CC-BY-4.0.
Statement reproduced verbatim; metadata (topic, difficulty) added by this project.