1
$\begingroup$

In the context of a paper I study, I want to prove an inequality. Consider $K,N$ positive integers and $a,b$ positive real numbers basically with $a=0.275$ and $b=1.1$. I try to prove the following

\begin{equation} -\frac{(\lfloor a\cdot\mathrm{min}\{N,K\}\rfloor)^2}{1-\lfloor a\cdot\mathrm{min}\{N,K\}\rfloor/N}\frac{b\cdot\mathrm{max}\{1,N/K\}}{N}\geq-\mathrm{min}\{N,K\}\frac{ba^2}{1-a\cdot\mathrm{min}\{1,K/N\}} \end{equation}

Equivalently we have that \begin{eqnarray} -\frac{(\lfloor a\cdot\mathrm{min}\{N,K\}\rfloor)^2}{1-\lfloor a\cdot\mathrm{min}\{N,K\}\rfloor/N}b\cdot\mathrm{max}\{1/N,1/K\}&\geq&-\mathrm{min}\{N,K\}\frac{ba^2}{1-a\cdot\mathrm{min}\{1,K/N\}}\\ -\frac{(\lfloor a\cdot\mathrm{min}\{N,K\}\rfloor)^2}{1-\lfloor a\cdot\mathrm{min}\{N,K\}\rfloor/N}b\cdot\mathrm{min}\{N,K\}&\geq&-\mathrm{min}\{N,K\}\frac{ba^2}{1-a\cdot\mathrm{min}\{1,K/N\}}\\ \Leftrightarrow\frac{(\lfloor a\cdot\mathrm{min}\{N,K\}\rfloor)^2}{1-\lfloor a\cdot\mathrm{min}\{N,K\}}/N&\leq&\frac{a^2}{1-a\cdot\mathrm{min}\{1,K/N\}} \end{eqnarray}

by exploiting \begin{equation} \lfloor x\rfloor\geq x-1 \end{equation}

I am trying to compare the denominators so by the above identity \begin{eqnarray} \lfloor a\cdot\mathrm{min}\{N,K\}\rfloor/N&\geq&a\cdot\mathrm{min}\{N,K\}/N-1/N\\ \Leftrightarrow-\lfloor a\cdot\mathrm{min}\{N,K\}\rfloor/N&\leq&-a\cdot\mathrm{min}\{N,K\}/N+1/N\\ \Leftrightarrow1-\lfloor a\cdot\mathrm{min}\{N,K\}\rfloor/N&\leq&1-a\cdot\mathrm{min}\{N,K\}/N+1/N\\ \Leftrightarrow1-\lfloor a\cdot\mathrm{min}\{N,K\}\rfloor/N&\leq&1-a\cdot\mathrm{min}\{1,K/N\}+1/N \end{eqnarray} but I cannot reach a conclusive result here. Also I am not sure about the second step of the previous series of inequalities.

$\endgroup$
  • $\begingroup$ It seems that the inequality does not hold when $N=1,K=2,a=10.1, b=11$. $\endgroup$ – mathlove Jan 15 '17 at 4:01
  • $\begingroup$ @mathlove basically in my case $a=0.275$ and $b=1.1$ are fixed but I did not state that in order to simplify the expression. I thought it woulnd't matter. $N,K$ are still arbitrary positive integers, though. $\endgroup$ – mgus Jan 15 '17 at 4:06
1
$\begingroup$

For $0\lt a\lt 1$ and $b\gt 0$ such that $$1-\frac{\lfloor a\cdot\min\{N,K\}\rfloor}{N}\not=0\quad\text{and}\quad 1-a\cdot\min\left\{1,\frac KN\right\}\not=0$$ the inequality holds.

$$-\frac{(\lfloor a\cdot\mathrm{min}\{N,K\}\rfloor)^2}{1-\lfloor a\cdot\mathrm{min}\{N,K\}\rfloor/N}\frac{b\cdot\mathrm{max}\{1,N/K\}}{N}\geq-\mathrm{min}\{N,K\}\frac{ba^2}{1-a\cdot\mathrm{min}\{1,K/N\}}\tag1$$

Let us separate it into two cases :

Case 1 : $K\ge N$ $$\begin{align}(1)&\iff -\frac{(\lfloor a\cdot N\rfloor)^2}{1-\frac{\lfloor a\cdot N\rfloor}{N}}\cdot\frac{b\cdot 1}{N}\geq-N\cdot\frac{ba^2}{1-a\cdot 1}\\\\&\iff \frac{\lfloor aN\rfloor^2}{N-\lfloor aN\rfloor}\le \frac{(aN)^2}{N-aN}\tag2\end{align}$$

Multiplying the both sides of $(2)$ by $(N-\lfloor aN\rfloor)(N-aN)\gt 0$ gives $$\begin{align}(2)&\iff (N-aN)\lfloor aN\rfloor^2\le (aN)^2(N-\lfloor aN\rfloor)\\\\&\iff a^2N^3-a^2N^2\lfloor aN\rfloor-N\lfloor aN\rfloor^2+aN\lfloor aN\rfloor^2\ge 0\\\\&\iff (aN+\lfloor aN\rfloor)(aN-\lfloor aN\rfloor)-a\lfloor aN\rfloor(aN-\lfloor aN\rfloor)\ge 0\\\\&\iff (aN-\lfloor aN\rfloor)(aN+(1-a)\lfloor aN\rfloor)\ge 0\end{align}$$ which holds for $0\lt a\lt 1$.

Case 2 : $K\lt N$

$$\begin{align}(1)&\iff -\frac{(\lfloor aK\rfloor)^2}{1-\frac{\lfloor aK\rfloor}{N}}\cdot\frac{b\cdot\frac NK}{N}\geq -K\cdot\frac{ba^2}{1-a\cdot\frac KN}\\\\&\iff \frac{\lfloor aK\rfloor^2}{N-\lfloor aK\rfloor}\le \frac{(aK)^2}{N-aK}\tag3\end{align}$$

Multiplying the both sides of $(3)$ by $(N-\lfloor aK\rfloor)(N-aK)\gt 0$ gives $$(3)\iff (aK-\lfloor aK\rfloor)(NaK+(N-aK)\lfloor aK\rfloor)\ge 0$$ which holds for $0\lt a\lt 1$.

$\endgroup$
  • $\begingroup$ Thanks, it seems that you have a lot of imagination. How did you approach this problem? Those are the kinds of things I usually encounter when I study papers. $\endgroup$ – mgus Jan 15 '17 at 6:11
  • $\begingroup$ @mgus: You are welcome. Well, first, I found that separating the inequality into two cases should make it easy to deal with since the only thing that matters is the relation between $K$ and $N$. After this, I tried to simplify the inequality (hoping to factorize it) and luckily managed to factorize it. I hope this helps. $\endgroup$ – mathlove Jan 15 '17 at 6:24
  • $\begingroup$ @mgus: In general, it is not very easy to deal with min, max. So, separating an (in)equality into some cases in order to eliminate min, max is a good start especially when many cases are not needed like our inequality. $\endgroup$ – mathlove Jan 15 '17 at 6:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.