# Upper bound of floor function

I'm studying a paper where the authors stated preliminarily:

$$\mid R_{i,T}\mid \leq \frac{C \theta_0}{K(i_\theta,\theta,T)}, \forall i\in\{1,\dotsc,\theta^x\}$$

where $$C$$ is a finite contant; $$\theta_0$$ a positive integer; $$R_{i,T}:=R(i,T)$$; and $$i_\theta=i-\theta\left \lfloor{\frac{i-1}{\theta}}\right \rfloor$$ ; and $$\theta^x$$ is the least common multiple of $$\theta$$ and $$\theta_0$$; and $$\theta \in \{1,\dotsc,\Theta_T\}$$ integer. Note that $$i_\theta \in \{1,\dotsc,\theta\}$$. However, it was given that $$K(i_\theta,\theta,T)=\left \lfloor{\frac{T-i_\theta}{\theta}}\right \rfloor +1$$, which implies that this function can only be either $$\left \lfloor{\frac{T}{\theta}}\right \rfloor$$ or $$\left \lfloor{\frac{T}{\theta}}\right \rfloor +1$$. It also implies that $$K(i_\theta,\theta,T)=O\big(\frac{T}{\theta}\big)$$. Untill here it was everything fine to me. But, from this, they claimed that:

$$\mid R_{i,T}\mid \leq \frac{C\Theta_T}{T}, \forall i\in\{1,\dotsc,\theta^x\}$$

Is it right?

It is true that $$\frac{C \theta_0}{K(i_\theta,\theta,T)}\leq \frac{C}{\left \lfloor{\frac{T}{\theta}}\right \rfloor}$$. On one hand, $$\frac{C}{\left \lfloor{\frac{T}{\theta}}\right \rfloor} \geq \frac{C}{\frac{T}{\theta}}$$ (and then cannot be used), on the other, $$\frac{C}{\frac{T}{\theta}} \leq\frac{C\Theta_T}{T}$$. How they simply dropped the floor function and stablished the that upper bound? Even asymptotically, I don't see that $$\frac{C}{\left \lfloor{\frac{T}{\theta}}\right \rfloor} = \frac{C}{\frac{T}{\theta}}$$ does hold.

The asymptotics here respects $$T \rightarrow \infty$$, $$\Theta_T \rightarrow \infty$$ at a slower rate than $$T$$ (implying $$\mid R_{i,T}\mid \rightarrow 0$$).

Reference: Proof of 'lemma a.4'

• With no restriction on $\theta_0$, you have no bound at all. Did you copy this correctly? – Matt Samuel May 24 at 13:45
• In my view, $\theta_0$ is a parameter (constant). If I put $\theta_0 \in \{1,...,\Theta_T\}$, does it help anything? I will try to link the paper here. – Danmat May 24 at 14:02
• If it's constant and it is absorbed into $C$, then sure it holds. $\left\lfloor \frac T{\theta}\right \rfloor$ differs from $\frac T{\theta}$ by at most $1$, so certainly it is asymptotically equal. – Matt Samuel May 24 at 14:08
• @MattSamuel Yes! I know it, $\frac{T}{ \theta}-1<{\left \lfloor{\frac{T}{\theta}}\right \rfloor} \leq \frac{T}{ \theta}$. But there is no guarantee that $\mid R_{i,T}\mid \leq \frac{C \theta}{T}$ from the first inequality. This is the problem. I can just guarantee that $\mid R_{i,T}\mid \leq \frac{C}{{\left \lfloor{\frac{T}{\theta}}\right \rfloor}}$ – Danmat May 24 at 14:31
• @MattSamuel If $\theta$ happen to be $\Theta_T$, clearly, the first inequality shows that $\mid R_{i,T}\mid$ could be greater than $\frac{C \theta}{T}$. – Danmat May 24 at 14:39