3
$\begingroup$

Let $\pi:\mathbb{N}\to\mathbb{N}$ be a bijection. Then does there exist another bijection $\nu:\mathbb{N}\to\mathbb{N}$ and a constant $C$ such that $$ \frac{1}{n} + \frac{1}{\pi(n)} \leq \frac{C}{\nu(n)} $$ for all $n$? If so, can the constant be chosen independent of $\pi$?

While the harmonic sequence $(\frac{1}{n})_{n\in\mathbb{N}}$ is what comes up in my application, I imagine that a good answer will be able to make a much more general statement about a suitable class of sequences. But I'd be perfectly happy with an answer to the question above.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Unless I am confused, an easy calculation shows that (a) $\nu(1)=1$ and (b) $\nu(\pi^{-1}(1))=1$. So it seems that a necessary condition is $\pi(1)=1$. $\endgroup$
    – Gregory Arone
    Commented Mar 9, 2017 at 13:37
  • $\begingroup$ @GregoryArone: of course, thanks! This shows that I cannot expect the constant to be 2. I'll edit my question accordingly. $\endgroup$
    – Tobias Fritz
    Commented Mar 9, 2017 at 13:41

1 Answer 1

Reset to default
4
$\begingroup$

Yes, we may achieve even $\nu(n)\leqslant 2\min(n,\pi(n))$. Indeed, define $\rho(n)=\min(n,\pi(n))$ and let $t_1,t_2,\dots$ be an enumeration of the positive integers such that $\rho(t_1)\leqslant \rho (t_2)\leqslant \rho(t_3)\leqslant \dots$. Then $\rho(t_k)\geqslant k/2$, otherwise we may find three different numbers with the same values of $\rho$. Therefore defining $\nu(t_k)=k$ we get $\nu(t_k)=k\leqslant 2\rho(t_k)$ as desired.

This results in $$ \frac{1}{n} + \frac{1}{\pi(n)} \leq \frac{2}{\rho(n)} \leq \frac{4}{\nu(n)}, $$ as was to be shown.

Improve this answer
$\endgroup$
1
  • $\begingroup$ So this results in $C=4$. Thank you! $\endgroup$
    – Tobias Fritz
    Commented Mar 9, 2017 at 14:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .