Abstract Nonsense

Neat Number Theory/Discrete Math Problem (Pt. II)

Point of post: This is a continuation of this post.

Generalization

We now prove a much more generalized theorem. Namely:

Theorem: Let $n_0\in\mathbb{N}$ with prime factorization $p_1^{\alpha_1}\cdots p_{k}^{\alpha_k}$ be fixed and define

$E_n=\left\{m\leqslant n:(m,n_0)=1\right\}$

From this define

$a_n=\left|E_n\right|$

then

$\displaystyle a_n=n-\sum_{j=1}^{k}(-1)^{j+1}\sum_{S\in S_j}\left\lfloor n\left(\prod_{s\in S}p_s\right)^{-1}\right\rfloor$

and thus

$\displaystyle \lim_{n\to\infty}\frac{a_n}{n}=1-\sum_{j=1}^{k}(-1)^{j+1}\sum_{S\in S_j}\left(\prod_{s\in S}p_s\right)^{-1}$

Proof: We first note thta

$(m,n_0)=1\Leftrightarrow p_1\nmid m\text{ and }\cdots\text{ and }p_k\nmid m$

so that if

$A_{j,n}=\left\{m\leqslant: p_j\mid m\right\},\quad j=1,\cdots,k$

we see that

$[n]=E_n\sqcup\left(A_{1,n}\cup\cdots\cup A_{k,n}\right)$

(where the $\sqcup$ notation was discussed in the last post). Thus,

\begin{aligned}n=\left|[n]\right|& =\left|E_n\sqcup\left(A_{1,n}\cup\cdots\cup A_{k,n}\right)\right|\\ &=\left|E_n\right|+\left|A_{1,n}\cup\cdots\cup A_{k,n}\right|\\ &=a_n+\left|A_{1,n}\cup\cdots\cup A_{k,n}\right|\end{aligned}

so that

$a_n=n-\left|A_{1,n}\cup\cdots\cup A_{k,n}\right|$

Thus, to find $a_n$ it suffices to find

$\left|A_{1,n}\cup\cdots\cup A_{k,n}\right|$

To do this we recall that the Generalized Inclusion-Exclusion Principle states that if $S_j\overset{\text{def.}}{=}\left\{S\subseteq\{:|S|=j\right\}$ then

$\displaystyle \left|A_{1,k}\cup\cdots\cup A_{k,n}\right|=\sum_{j=1}^{k}(-1)^{j+1}\sum_{S\in S_j}\left|\bigcap_{s\in S}A_{s,n}\right|$

So, note that  since each $p_\ell,\quad \ell=1,\cdots,k$ is relatively prime that

$\displaystyle \bigcap_{s\in S}A_{s,n}=\left\{m\leqslant n:p_s\mid m\text{ for all }s\in S\right\}=\left\{m\leqslant n:\prod_{s\in S}p_s\mid m\right\}$

thus

$\displaystyle \left|\bigcap_{s\in S}A_{s,n}\right|=\left\lfloor n\left(\prod_{s\in S}p_s\right)^{-1}\right\rfloor$

Thus,

$\displaystyle \left|A_{1,n}\cup\cdots\cup A_{k,n}\right|=\sum_{j=1}^{k}(-1)^{j+1}\sum_{S\in S_j}\left|\bigcap_{s\in S}A_{s,k}\right|=\sum_{j=1}^{k}(-1)^{j+1}\sum_{S\in S_j}\left\lfloor n\left(\prod_{s\in S}p_s\right)^{-1}\right\rfloor$

from where our first claim follows. The second claim follows immediately since in general

$\displaystyle \lfloor x\rfloor\sim x$

where $\sim$ denotes asymptotic equivalence. Thus,

$\displaystyle \lim_{n\to\infty}\frac{a_n}{n}=\lim_{n\to\infty}\left(1-\sum_{j=1}^{k}(-1)^{j+1}\sum_{S\in S_j}\frac{1}{n}\left\lfloor n\left(\prod_{s\in S}p_s\right)^{-1}\right\rfloor\right)=1-\sum_{j=1}^{k}(-1)^{j+1}\sum_{S\in S_j}\left(\prod_{s\in S}p_s\right)^{-1}$

$\blacksquare$

1. Rosen, Kenneth H. Discrete Mathematics and Its Applications. Boston: McGraw-Hill Higher Education, 2007. Print.

November 4, 2010 -

1 Comment »

1. […] of post: Since I found this problem enjoyable, for some odd reason, I thought I’d also generalize the methodology in the first […]

Pingback by Neat Number Theory/Discrete Math Problem (Pt. III) « Abstract Nonsense | November 6, 2010 | Reply