$H_{c,n}(y)=\sum_{c\mid d\mid p_n\#}(-1)^{\omega(d)}[\dfrac{y-z_{c,d}}{d}]$ is asymptotic to $\sum_{c\mid d\mid p_n\#}(-1)^{\omega(d)}[\dfrac{y}{d}]$?

39 Views Asked by At

For $c, n \in \Bbb{N}$, define the function $H_{c,n}(y) = \sum_{c \mid d \mid p_n\# \\ d\leq y} (-1)^{\omega(d)} \lfloor \dfrac{y - z_{c,d}}{d}\rfloor$.

Where $z_{c,d}$ is a random variable in the range $\{0, \dots, d-1\}$ for each $c \mid d$.

Now, how can we prove rigorously that $H_{c,n}(y) \sim \sum_{c \mid d \mid p_n\#} (-1)^{\omega(d)}\lfloor\dfrac{y}{d} \rfloor$ as $y \to \infty$ i.e. that $H_{c,n}(y)$ is actually asymptotic to the same thing with $d \leq y$ removed and each $z_{c,d}$ deleted?

Well, we know since $z_{c,d}$ is bounded as $z_{c,d} \lt d \leq p_n\#$ that when $n$ is fixed w.r.t. $y$, the contribution of subtracting each $z_{c,d}$ becomes insanely small.

Of course we can remove $d \leq y$ beacuse as $y \to \infty$ that aready happens automatically as $y$ surpasses $p_n\#$.

I need help formalizing the italicized part above.


Attempt. Suppose each $z_{c,d} = d-1$ when $\omega(d) = $ and odd number, and $z_{c,d} = d-1$ when $\omega(d) = 0$ an even number.

Define $\sum_*(\cdot) = \sum_{c \mid d \mid p_n\# \\ d \leq y} (\cdot)$ to be our summation operator for convenience of notation. Let $\sum^e_*$ mean the same sum except $\omega(d) = \text{even}$ and similarly for $\sum^o_*$.

Then we can surmise that the maximum attained by $H_{c,n}(y)$ is:

$$ \sum_*^e \lfloor\dfrac{y}{d}\rfloor - \sum_*^o\lfloor \dfrac{y - (d-1)}{d} \rfloor = \\ \sum_*^e \dfrac{y - y_{(d)}}{d} - \sum_*^o (\dfrac{y + 1 - (y+1)_{(d)}}{d} - 1) = \\ \sum_*(-1)^{\omega(d)} \dfrac{y}{d} -\sum_*^e\dfrac{y_{(d)}}{d} +\sum_*^o\dfrac{(y + 1)_{(d)}}{d} -\sum_*^o \dfrac{1}{d} -\sum_*^o 1 $$

where $z_{(d)} = $ the least non-negative residue modulo $d$ of $z$, in $\Bbb{Z}$.

The last long line is bounded above by:

$$ \sum_*(-1)^{\omega(d)} \dfrac{y}{d} -\sum_*^e\dfrac{0_{(d)}}{d} +\sum_*^o\dfrac{(d-1)_{(d)}}{d} -\sum_*^o \dfrac{1}{d} -\sum_*^o 1 = \\ \sum_*(-1)^{\omega(d)} \dfrac{y}{d} +\sum_*^o\dfrac{(d-1)_{(d)}}{d} -\sum_*^o \dfrac{1}{d} -\sum_*^o 1 = \\ $$

Since the three terms on the write sum to to a constant $C$ when $n$ is fixed, we have that $H_{c,n}(y) = O(\sum_*(-1)^{\omega(d)} \dfrac{y}{d})$.

But I need more than that I think. I would like a lower bound for one, and it should be in terms of $y$ so I'm thinking asymptotic something or other...


If instead you perform the same procedure above but with the purpose of finding a minimum, we also obtain:

$$ H_{c,n}(y) = \Omega(\sum_* (-1)^{\omega(d)} \dfrac{y}{d}) $$ as well.

Thus $H_{c,n}(y) = O(\cdot)$ and $\Omega(\cdot)$ of $\sum_* (-1)^{\omega(d)} \dfrac{y}{d}$.