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$
1
  • 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$ Nov 1, 2018 at 9:08

2 Answers 2

9
$\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$
2
  • $\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$ Nov 2, 2018 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$ Nov 2, 2018 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$
6
  • $\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$ Nov 2, 2018 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, 2018 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$ Nov 3, 2018 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$ Nov 3, 2018 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, 2018 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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