Maths Olympiad Prep

Library / /503 of 520

Number theory Difficulty 7.9 National olympiad, round 2 Prove it

Let AA be an infinite subset of the set of natural numbers, and denote by τA(n)\tau_A(n) the number of divisors of nn in AA. Construct a set AA for which
nxτA(n)=x+O(loglogx)\sum_{n\le x}\tau_A(n)=x+O(\log\log x)
and show that there is no set for which the error term is o(loglogx)o(\log\log x) in the above formula.

(translated by Miklós Maróti)

Solution

1. Assume the contrary: Suppose there exists a set A A such that the error term in the formula is o(loglogx) o(\log\log x) . Specifically, assume:
nxτA(n)=x+ε(x)loglogx \sum_{n \le x} \tau_A(n) = x + \varepsilon(x) \log\log x
where limxε(x)=0 \lim_{x \to \infty} \varepsilon(x) = 0 .

2. **Express τA(n)\tau_A(n)**: Recall that τA(n)\tau_A(n) is the number of divisors of n n in A A . Therefore, we can write:
nxτA(n)=nxaA,an1=aAnx,an1=aAxa \sum_{n \le x} \tau_A(n) = \sum_{n \le x} \sum_{a \in A, a|n} 1 = \sum_{a \in A} \sum_{n \le x, a|n} 1 = \sum_{a \in A} \left\lfloor \frac{x}{a} \right\rfloor

3. **Sum over A A **: Let A={a1,a2,} A = \{a_1, a_2, \ldots\} be arranged in increasing order. Since i1ai=1 \sum_{i} \frac{1}{a_i} = 1 , we can denote i=1n1ai=1εn \sum_{i=1}^n \frac{1}{a_i} = 1 - \varepsilon_n , where εn>0 \varepsilon_n > 0 is a decreasing sequence converging to 0. Hence, an1εn1εn a_n \approx \frac{1}{\varepsilon_{n-1} - \varepsilon_n} .

4. Rewrite the sum: We have:
nxτA(n)=xaix1aiaix{xai} \sum_{n \le x} \tau_A(n) = x \sum_{a_i \le x} \frac{1}{a_i} - \sum_{a_i \le x} \left\{ \frac{x}{a_i} \right\}
where {} \{ \cdot \} denotes the fractional part.

5. Approximate the sum: Using the approximation aix1ai1εn \sum_{a_i \le x} \frac{1}{a_i} \approx 1 - \varepsilon_n for anx<an+1 a_n \le x < a_{n+1} , we get:
nxτA(n)=x(1εn)aix{xai} \sum_{n \le x} \tau_A(n) = x (1 - \varepsilon_n) - \sum_{a_i \le x} \left\{ \frac{x}{a_i} \right\}
Thus:
x(1εn)aix{xai}=x+ε(x)loglogx x (1 - \varepsilon_n) - \sum_{a_i \le x} \left\{ \frac{x}{a_i} \right\} = x + \varepsilon(x) \log\log x

6. Simplify the equation: Rearrange the terms to get:
εnxaix{xai}=ε(x)loglogx -\varepsilon_n x - \sum_{a_i \le x} \left\{ \frac{x}{a_i} \right\} = \varepsilon(x) \log\log x

7. Analyze the second term: The second term on the left-hand side, aix{xai} \sum_{a_i \le x} \left\{ \frac{x}{a_i} \right\} , can be significant. For some choices of large x x , this term can be approximated by n \sim n .

8. **Rate of an a_n **: This implies that the rate of an a_n is een/ε e^{e^{n/\varepsilon}} , where ε>0 \varepsilon > 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 x as we want for which:
F(x):=aix{xai}>cnforanx<an+1 F(x) := \sum_{a_i \le x} \left\{ \frac{x}{a_i} \right\} > c \cdot n \quad \text{for} \quad a_n \le x < a_{n+1}
where c c is an absolute constant.

10. Proof of the claim: (Sketch) We prove there exists x[an,2an] x \in [a_n, 2a_n] for which i=1n{xai}>cn \sum_{i=1}^n \left\{ \frac{x}{a_i} \right\} > c \cdot n (with c=27 c = 2^{-7} ). This is enough to prove the claim since there are infinitely many n n 's with a2n>2an a_{2n} > 2a_n (otherwise 1ai \sum \frac{1}{a_i} would diverge).

11. **Divide ai a_i 's into groups**: Let Ak:={ai[2k1,2k):1in},k=1,2,,m A_k := \{a_i \in [2^{k-1}, 2^k) : 1 \le i \le n \}, k = 1, 2, \ldots, m . Let I0 I_0 be the interval [an,an+2m1] [a_n, a_n + 2^{m-1}] . It's easy to show we can find an interval I1 I_1 inside I0 I_0 with length I0/4 |I_0|/4 such that {xai}1/8 \left\{ \frac{x}{a_i} \right\} \geq 1/8 for at least Am/8 |A_m|/8 terms ai a_i in Am A_m and every xI1 x \in I_1 . Hence:
aAm{xa}Am64 \sum_{a \in A_m} \left\{ \frac{x}{a} \right\} \geq \frac{|A_m|}{64}
Then we repeat the same argument with Am2 A_{m-2} and I1 I_1 and so on, getting there exists x x :
aA{xa}A64;A=AmAm2Am4 \sum_{a \in A'} \left\{ \frac{x}{a} \right\} \geq \frac{|A'|}{64}; \quad A' = A_m \cup A_{m-2} \cup A_{m-4} \cup \ldots
The same can be made for A:=Am1Am3 A'' := A_{m-1} \cup A_{m-3} \cup \ldots and finally the result follows with c=27 c = 2^{-7} .

12. Conclusion from the claim: Using the above claim, from the equation we get that for any ε>0 \varepsilon > 0 there exist infinitely many n n 's such that:
an>een/ε a_n > e^{e^{n/\varepsilon}}

13. Implication: From this, it easily follows there are infinitely many n n 's satisfying:
an>(a1a2an1)2 a_n > (a_1 \cdot a_2 \cdots a_{n-1})^2

14. Estimate the first term: For x[an1,an) x \in [a_{n-1}, a_n) , the first term in the left-hand side of the equation is estimated as:
εnx=(1i=1n11ai)xxa1a2an1 \varepsilon_n x = \left( 1 - \sum_{i=1}^{n-1} \frac{1}{a_i} \right) x \geq \frac{x}{a_1 \cdot a_2 \cdots a_{n-1}}

15. **For x=an1 x = a_n - 1 **: We obtain:
εnxx \varepsilon_n x \geq \sqrt{x}

16. Final contradiction: Putting it back in the equation yields:
ε(x)loglogxx |\varepsilon(x)| \log\log x \geq \sqrt{x}
This contradicts with limxε(x)=0 \lim_{x \to \infty} |\varepsilon(x)| = 0 , since we can find as large x 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.