Number theoryDifficulty 7.9National olympiad, round 2Prove it
Let A be an infinite subset of the set of natural numbers, and denote by τA(n) the number of divisors of n in A. Construct a set A for which n≤x∑τA(n)=x+O(loglogx) and show that there is no set for which the error term is o(loglogx) in the above formula.
(translated by Miklós Maróti)
Solution
1. Assume the contrary: Suppose there exists a set A such that the error term in the formula is o(loglogx). Specifically, assume: n≤x∑τA(n)=x+ε(x)loglogx where limx→∞ε(x)=0.
2. **Express τA(n)**: Recall that τA(n) is the number of divisors of n in A. Therefore, we can write: n≤x∑τA(n)=n≤x∑a∈A,a∣n∑1=a∈A∑n≤x,a∣n∑1=a∈A∑⌊ax⌋
3. **Sum over A**: Let A={a1,a2,…} be arranged in increasing order. Since ∑iai1=1, we can denote ∑i=1nai1=1−εn, where εn>0 is a decreasing sequence converging to 0. Hence, an≈εn−1−εn1.
4. Rewrite the sum: We have: n≤x∑τA(n)=xai≤x∑ai1−ai≤x∑{aix} where {⋅} denotes the fractional part.
5. Approximate the sum: Using the approximation ∑ai≤xai1≈1−εn for an≤x<an+1, we get: n≤x∑τA(n)=x(1−εn)−ai≤x∑{aix} Thus: x(1−εn)−ai≤x∑{aix}=x+ε(x)loglogx
6. Simplify the equation: Rearrange the terms to get: −εnx−ai≤x∑{aix}=ε(x)loglogx
7. Analyze the second term: The second term on the left-hand side, ∑ai≤x{aix}, can be significant. For some choices of large x, this term can be approximated by ∼n.
8. **Rate of an**: This implies that the rate of an is een/ε, where ε>0 can be made as small as we want. However, such fast convergence would make the first term on the left-hand side of the equation too large, making it impossible to satisfy the equation.
9. Claim: There exists as large x as we want for which: F(x):=ai≤x∑{aix}>c⋅nforan≤x<an+1 where c is an absolute constant.
10. Proof of the claim: (Sketch) We prove there exists x∈[an,2an] for which ∑i=1n{aix}>c⋅n (with c=2−7). This is enough to prove the claim since there are infinitely many n's with a2n>2an (otherwise ∑ai1 would diverge).
11. **Divide ai's into groups**: Let Ak:={ai∈[2k−1,2k):1≤i≤n},k=1,2,…,m. Let I0 be the interval [an,an+2m−1]. It's easy to show we can find an interval I1 inside I0 with length ∣I0∣/4 such that {aix}≥1/8 for at least ∣Am∣/8 terms ai in Am and every x∈I1. Hence: a∈Am∑{ax}≥64∣Am∣ Then we repeat the same argument with Am−2 and I1 and so on, getting there exists x: a∈A′∑{ax}≥64∣A′∣;A′=Am∪Am−2∪Am−4∪… The same can be made for A′′:=Am−1∪Am−3∪… and finally the result follows with c=2−7.
12. Conclusion from the claim: Using the above claim, from the equation we get that for any ε>0 there exist infinitely many n's such that: an>een/ε
13. Implication: From this, it easily follows there are infinitely many n's satisfying: an>(a1⋅a2⋯an−1)2
14. Estimate the first term: For x∈[an−1,an), the first term in the left-hand side of the equation is estimated as: εnx=(1−i=1∑n−1ai1)x≥a1⋅a2⋯an−1x
15. **For x=an−1**: We obtain: εnx≥x
16. Final contradiction: Putting it back in the equation yields: ∣ε(x)∣loglogx≥x This contradicts with limx→∞∣ε(x)∣=0, since we can find as large x as we want for which the above inequality holds.
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: NuminaMath-1.5,
licensed Apache-2.0.
Statement and solution reproduced as published; topic and difficulty added by this site.