10
$\begingroup$

What is the tight upper bound of $\sum_{i=1}^n \frac{i}{i+x_i}$, where the $x_i$'s are distinct integers in $\{1,2,...,n\}$?

$\endgroup$
  • 4
    $\begingroup$ Are you asking for the maximum of $f:S_{n}\rightarrow\mathbb{R}:\sigma\mapsto\sum_{i=1}^{n}\frac{i}{i+\sigma(i)}$? $\endgroup$ – Nicéphore Bayekula Nov 1 '18 at 9:08
10
$\begingroup$

I doubt that there is an exact formula for this maximum, and unfortunately Wolfgang's guess is incorrect. Indeed, let $$ a_n = \mathrm{max}_{\sigma \in \mathfrak{S}_n} \sum_{i=1}^n \frac{i}{i + \sigma(i)}. $$ Then by considering the standard embedding $\mathfrak{S}_n \times \mathfrak{S}_m \hookrightarrow \mathfrak{S}_{n+m}$, one checks that $$ a_{n+m} \geq a_n + a_m, $$ so that the sequence $\frac{a_n}{n}$ converges to the number $c = \mathrm{sup}_n \frac{a_n}{n} \in [\frac{1}{2},1]$. Now, I claim that $c > \frac{1}{2}$, so that neither $\mathrm{id}$ nor $(n, 1, 2,...,n-1)$ grant the maximum when $n$ is large.

For $r = r_n = \lfloor \alpha n \rfloor$ with $\alpha \in ]0,1[$, let us consider the cycle $(n-r+1,n-r+2,...,n-1,n,1,2,...,n-r)$. Then we get \begin{align*} c &\geq \lim_n \frac{1}{n} \left( \sum_{j=1}^r \frac{j}{n-r+2j} + \sum_{j=r+1}^n \frac{j}{2j-r} \right) \\ &= \frac{1}{2} + \frac{\alpha}{4} \log \left( \frac{2-\alpha}{\alpha} \right) - \frac{1-\alpha}{4} \log \left( \frac{1+\alpha}{1-\alpha} \right) . \end{align*} This is $> \frac{1}{2}$ for $\alpha \in ]0, \frac{1}{2}[$. The maximum is around $\alpha = 0.14868$, where the bound is $c >0.529$.

$\endgroup$
  • $\begingroup$ Here are the first few maxima: $([1], 1/2)$, $([1, 2], 1), ([2, 1], 1)$, $([3, 1, 2], 91/60)$, $([4, 1, 2, 3], 214/105)$, $([5, 1, 2, 3, 4], 1613/630)$, $([6, 1, 2, 3, 4, 5], 10679/3465)$, $([7, 1, 2, 3, 4, 5, 6], 1298221/360360)$, $([8, 7, 1, 2, 3, 4, 5, 6], 3469/840)$, $([9, 8, 1, 2, 3, 4, 5, 6, 7], 2609/560)$, $([10, 9, 1, 2, 3, 4, 5, 6, 7, 8], 287579/55440)$ $\endgroup$ – Martin Rubey Nov 2 '18 at 16:17
  • $\begingroup$ In fact, if this pattern persists, then the maximum would be $\frac{1}{4} \, r {\left(H_{n - r/2} - H_{r/2} - 2\right)} + \frac{1}{2} \, n + \frac{r(r+1)}{2 \, {\left(n + 1\right)}}$ for some $r$, where $H_k$ is the harmonic number. $\endgroup$ – Martin Rubey Nov 2 '18 at 16:39
4
$\begingroup$

Most surely, (see bottom) Initially I had thought $$max=\frac1{1+n}+\sum_{i=2}^n \frac i{i+(i-1)},$$ but my proof below is still somewhat incomplete...

If the $x_i$ are a permutation $\pi$ of $\{1,2,...,n\}$, let $y_i:=\pi^{-1}(i)$ Then we have $$\sum_{i=1}^n \frac{i}{i+x_i}=n-\sum_{i=1}^n \frac{x_i}{i+x_i}=n-\sum_{j=1}^n \frac{j}{y_j+j},$$ so the sums come in pairs, and if $\pi$ yields a maximum, then $\pi^{-1}$ will yield a minimum.

I'd like to show that the maximum is attained for the permutation ${\pi:=(n,1,2,...,n-1)}$.

Now, for $i>1$ and $k<n$, $$\frac1{1+n}+\frac i{i+k}>\frac 1{1+k}+\frac i{i+n}$$because $$LHS-RHS=\frac{(i - 1) (n-k) (k n - i)}{(1+n) (i + k)(1+k) (i + n)}>0.$$ So we must have $x_1=n$ for a maximal permutation.

Generally, $$\frac j{j+a}+\frac k{k+b}-\left(\frac j{j+b}+\frac k{k+a}\right) =\frac{(b-a)(k-j)(jk-ab)}{(j+a) (k+b) (j+b)(k+a)}.$$ Thus if for $j\ge2$ we put $x_j=j-1$, the above difference (with putting $a=x_j, b=x_k$) is always positive. This proves that $\pi$ does strictly better than with any involution applied to it, which gives a strong evidence in favor of $\pi$.
But the problem remains that we cannot conclude from there for any combination of involutions because of the factor $(jk-ab)$ which might become negative at some point.

EDIT after js21's answer: That shot was too quick. It looks in fact like the maximum is attained for the permutation $$\color{red}{\pi_k=[n,n-1,...,n-k+1,1,2,...,n-k]}$$ with $k\approx \dfrac n{6.3032}$, thus linear in $n$. This is very precise: for $n<1,000,000$, the optimal $k$ always seems to be within a range $\pm1$ of this fraction, even for small $n$.

$\endgroup$
  • $\begingroup$ How can you check that the maximum for such a large $n$ is of the given form? Besides, I think that @js21 considered a different permutation (which yields a large value, but not the maximum)... $\endgroup$ – Martin Rubey Nov 2 '18 at 22:08
  • $\begingroup$ @MartinRubey Of course, like for most conjectures, there is a certain amount of educated guess involved. I have not checked millions of sums, I just say "it looks like", but I don't claim... One of my assumptions is a kind of monotonicity, which seems highly plausible: if for a fixed $n$, we take $\pi_k:=[n,n-1,...,n-k+1,1,2,...,n-k]$, then there is a $k$ such that $f(\pi_1)<\cdots<f(\pi_k)>f(\pi_{k+1}>\cdots$. And the first $\pi_k$ seem to be the best candidates, so... My "indeed" referred rather to your first comment there than to js21's permutations. :) In any case, we must have $x_1=n$. $\endgroup$ – Wolfgang Nov 3 '18 at 13:10
  • $\begingroup$ OK, I just thought you had some way to check that the general form I mentioned in the comment was correct. By the way, the poset of permutations ordered by $f$ is quite interesting! $\endgroup$ – Martin Rubey Nov 3 '18 at 13:25
  • $\begingroup$ Another comment: if I made no mistake, given the conjectural form, I think that $k\simeq c\cdot n$ should be such that $c$ is the zero of $(c-2)\ln(\frac{c}{2}-1) + 2(2c-3)(c-1)$. So, $1/c=6.303250770424045$ as you write. $\endgroup$ – Martin Rubey Nov 3 '18 at 13:31
  • $\begingroup$ @MartinRubey That sounds good. How did you come up with that? I suppose by solving $f(\pi_k)=f(\pi_{k+1})$ for big n, using asymptotics of the harmonic series? $\endgroup$ – Wolfgang Nov 3 '18 at 16:46

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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