Given positive integer $M.$ For any $n\in\mathbb N_+,$ let $h(n)$ be the number of elements in $[n]$ that are coprime to $M.$ Define $\beta :=\frac {h(M)}M.$ Proof: there are at least $\frac M3$ elements $n$ in $[M],$ satisfy $$\left| h(n)-\beta n\right|\le\sqrt{\beta\cdot 2^{\omega(M)-3}}+1.$$Here $[n]:=\{1,2,\ldots ,n\}$ for all positive integer $n.$ Proposed by Bin Wang
Problem
Source: 2024 Chinese TST P3
Tags: number theory, 2024 CTST
DottedCaculator
06.03.2024 05:43
I think I might be having extreme reading comprehension issues. If $M=2^{10}$, then $h(n)=\frac n2$ so the right hand side is less than $2$, which means only $n=1,2,3$ works?
TheHazard
06.03.2024 05:48
EDIT: This probably depends on the definition of $\omega(n)$, and Dotted's complaint is valid if $\omega(n)$ is assumed as the prime divisor counting function.
DottedCaculator
06.03.2024 05:50
TheHazard wrote: $h(n)$ depends on the value of $n$, which isn't always $M = 2^{10}$. Isn't $h(n)=\frac n2$ for $M=1024$?
LLL2019
06.03.2024 09:33
redacted
CANBANKAN
06.03.2024 16:11
L should be number of distinct prime divisors…. Not the number of divisors
CANBANKAN
06.03.2024 16:13
DottedCaculator wrote: TheHazard wrote: $h(n)$ depends on the value of $n$, which isn't always $M = 2^{10}$. Isn't $h(n)=\frac n2$ for $M=1024$? So in this case $L=1$ and $\beta =\frac 12$. The statement is true since $h(n)=\lceil \frac n2\rceil$
Rushery_10
06.03.2024 19:54
Use Mobius inversion/PIE to calculate the expression for $h\left(n\right)-\beta n$, the key is to use the second moment method(in other words, compute$\sum\limits_{n=1}^{M}\left(h\left(n\right)-\beta n\right)^2$), and the variance can be explicitly calculated.
Rushery_10
06.03.2024 20:26
It can be easily seen (via Mobius inversion or PIE) that $h\left(n\right)-\beta n=\sum\limits_{d\mid M}\mu\left(d\right)\left\{\frac{n}{d}\right\}$. As usual, $\left\{\right\}$ denotes the fraction part. We have:
$\sum\limits_{n=1}^{M}\left(h\left(n\right)-\beta n\right)^2
=\sum\limits_{n=1}^{N}\sum\limits_{a,b\mid M}\mu\left(a\right)\mu\left(b\right)\left\{\frac{n}{a}\right\}\left\{\frac{n}{b}\right\}
=\sum\limits_{a,b\mid M}\mu\left(a\right)\mu\left(b\right)\sum\limits_{n=1}^{N}\left\{\frac{n}{a}\right\}\left\{\frac{n}{b}\right\}
$
Note that $\sum\limits_{n=1}^{N}\left\{\frac{n}{a}\right\}\left\{\frac{n}{b}\right\}
$ can be computed: the number of $n$ for which $n\equiv i\left(\mathrm{mod}a\right)$ and $n\equiv j\left(\mathrm{mod}b\right)$ equals $0$ if $\left(a,b\right)$ does not divide $i-j$ , and $\frac{\left(a,b\right)}{ab}M$ otherwise. Rearrange the summation as $\sum\limits_{k=0}^{\left(a,b\right)-1}\sum\limits_{i\equiv j\equiv k\left(\mathrm{mod}\left(a,b\right)\right)}$, after some tedious calculation on arithmetic progressions, the above sum turns out to be $M\sum\limits_{a,b\mid M}\mu\left(a\right)\mu\left(b\right)\frac{3ab+\left(a,b\right)^2-3a-3b+2}{12ab}$
We compute the coefficient term by term:
$\sum\limits_{a,b\mid M}\mu\left(a\right)\mu\left(b\right)=\left(\sum\limits_{d\mid M}\mu\left(d\right)\right)^2=0$
$\sum\limits_{a,b\mid M}\mu\left(a\right)\mu\left(b\right)\frac{a+b}{ab}=2\sum\limits_{a\mid M}\frac{\mu\left(a\right)}{a}\left(\sum\limits_{b\mid M}\mu\left(b\right)\right)=0$
$\sum\limits_{a,b\mid M}\mu\left(a\right)\mu\left(b\right)\frac{1}{ab}=\beta^2$
One can show (by induction on $\omega\left(M\right)$) that $\sum\limits_{a,b\mid M}\mu\left(a\right)\mu\left(b\right)\frac{\left(a,b\right)^2}{ab}=2^{\omega\left(M\right)}\beta$. Direct computation also works, by interpreting $\frac{\left(a,b\right)^2}{ab}$ as symmetric difference of prime sets.
We arrive at the conclusion that $\sum\limits_{n=1}^{M}\left(h\left(n\right)-\beta n\right)^2=\left(\frac{2}{3}2^{\omega\left(M\right)-3}\beta+\frac{\beta^2}{6}\right)M$. Suppose, for the sake of contradiction, that the result doesn't hold, then $\sum\limits_{n=1}^{M}\left(h\left(n\right)-\beta n\right)^2\geq \frac{2}{3}M\left(\sqrt{2^{\omega\left(M\right)-3}\beta}+1\right)^2$, which is absurd since $\beta<1$.
ZussimanSupremacy
08.03.2024 13:14
Actually it is not abstruse by using Markov ine
EthanWYX2009
01.10.2024 11:22
Actually the original problem created by proposer is way more difficult, but since he thought that no one is abled to solve it, at last this problem turns out. Original Problem: Given positive integer $M.$ For any $n\in\mathbb N_+,$ let $h(n)$ be the number of elements in $[n]$ that are coprime to $M.$ Define $\beta :=\frac {h(M)}M.$ Proof: there are at least $\frac {M-h(M)}3$ elements $n$ in $[M]$ that are not coprime to $M,$ satisfy $$\left| h(n)-\beta n\right|\le\sqrt{\beta\cdot 2^{\omega(M)-3}}.$$
Limitedcurry
11.01.2025 19:40
Rushery_10 wrote:
It can be easily seen (via Mobius inversion or PIE) that $h\left(n\right)-\beta n=\sum\limits_{d\mid M}\mu\left(d\right)\left\{\frac{n}{d}\right\}$. As usual, $\left\{\right\}$ denotes the fraction part. We have:
$\sum\limits_{n=1}^{M}\left(h\left(n\right)-\beta n\right)^2
=\sum\limits_{n=1}^{N}\sum\limits_{a,b\mid M}\mu\left(a\right)\mu\left(b\right)\left\{\frac{n}{a}\right\}\left\{\frac{n}{b}\right\}
=\sum\limits_{a,b\mid M}\mu\left(a\right)\mu\left(b\right)\sum\limits_{n=1}^{N}\left\{\frac{n}{a}\right\}\left\{\frac{n}{b}\right\}
$
Note that $\sum\limits_{n=1}^{N}\left\{\frac{n}{a}\right\}\left\{\frac{n}{b}\right\}
$ can be computed: the number of $n$ for which $n\equiv i\left(\mathrm{mod}a\right)$ and $n\equiv j\left(\mathrm{mod}b\right)$ equals $0$ if $\left(a,b\right)$ does not divide $i-j$ , and $\frac{\left(a,b\right)}{ab}M$ otherwise. Rearrange the summation as $\sum\limits_{k=0}^{\left(a,b\right)-1}\sum\limits_{i\equiv j\equiv k\left(\mathrm{mod}\left(a,b\right)\right)}$, after some tedious calculation on arithmetic progressions, the above sum turns out to be $M\sum\limits_{a,b\mid M}\mu\left(a\right)\mu\left(b\right)\frac{3ab+\left(a,b\right)^2-3a-3b+2}{12ab}$
We compute the coefficient term by term:
$\sum\limits_{a,b\mid M}\mu\left(a\right)\mu\left(b\right)=\left(\sum\limits_{d\mid M}\mu\left(d\right)\right)^2=0$
$\sum\limits_{a,b\mid M}\mu\left(a\right)\mu\left(b\right)\frac{a+b}{ab}=2\sum\limits_{a\mid M}\frac{\mu\left(a\right)}{a}\left(\sum\limits_{b\mid M}\mu\left(b\right)\right)=0$
$\sum\limits_{a,b\mid M}\mu\left(a\right)\mu\left(b\right)\frac{1}{ab}=\beta^2$
One can show (by induction on $\omega\left(M\right)$) that $\sum\limits_{a,b\mid M}\mu\left(a\right)\mu\left(b\right)\frac{\left(a,b\right)^2}{ab}=2^{\omega\left(M\right)}\beta$. Direct computation also works, by interpreting $\frac{\left(a,b\right)^2}{ab}$ as symmetric difference of prime sets.
We arrive at the conclusion that $\sum\limits_{n=1}^{M}\left(h\left(n\right)-\beta n\right)^2=\left(\frac{2}{3}2^{\omega\left(M\right)-3}\beta+\frac{\beta^2}{6}\right)M$. Suppose, for the sake of contradiction, that the result doesn't hold, then $\sum\limits_{n=1}^{M}\left(h\left(n\right)-\beta n\right)^2\geq \frac{2}{3}M\left(\sqrt{2^{\omega\left(M\right)-3}\beta}+1\right)^2$, which is absurd since $\beta<1$.
Is summation of h(n) - Bㆍn = fraction part of n/d ?