1
$\begingroup$

For $i=1,2,\ldots,n$, let $d_i$ be a sequence of positive integers and $r_i$ a sequence of positive real numbers with $2\leq d_i\leq n-1$ that satisfy the following system of equations:

$d_i=\sum_{j=1}^n \frac{r_ir_j}{1+r_ir_j}$

for each $i=1,2\ldots,n$.

Question: Can we find a qualitative bound on $r_i$ in terms of $n$? I don't care if it's is a terrible bound, I just want any bound in terms of $n$.

Everything I've tried thus far seems to give me lower bounds on $r_i$. I've considered fudged cases (i.e. not requiring $d_i$ to be integers) of taking part of the $r_i$ to be some number $L$ and the other part to be $1/L$ in hopes of breaking any bound, but one can show that $L$ will be of order $\sqrt{n}$ thereby being bounded for a fixed $n$.

If we suppose wlog that

(*) $r_1\leq r_2\leq\cdots\leq r_n$,

then a primitive bound on $r_i$ would be:

$\left(\frac{r_1}{1+r_n^2}\right)r_i\leq d_i\leq \left(\frac{r_n}{1+r_1^2}\right)r_i$

but again this is not useful as this doesn't give any information on $r_n$.

Any help with this would be greatly appreciated!

2 Answers 2

1

This is actually a cutie. I'll denote $x_j=r_j^{-1}$, so the sums in question are $S_i=\sum_j\frac{1}{1+x_ix_j}$. Since you do not care what the bound is, I'll make it as simple as I can rather than making it as sharp as I can.

Lemma: Let $A\ge 1$. Suppose that the set $X=\{x_i\}_{i=1}^n$ contains an element outside the interval $[(An^2)^{-1},An^2]$. Then it contains an element in the union of intervals $[An^2)^{-1},A^{-1})\cup(A,An^2]$

Proof:. Suppose not. Let $I=\{i:x_i<(An^2)^{-1}\}$, $J=\{j:x_j>An^2\}$. Note that $I\cup J\ne\varnothing$. For all other $k$, we have $x_k\in[A^{-1},A]$. Write $ \sum_{i\in I}S_i-\sum_{j\in J}S_j=\sum_{i\in i,k\notin J}\frac{1}{1+x_ix_k}-\sum_{j\in j,k\notin I}\frac{1}{1+x_jx_k} $ and note that the left hand side is an integer. However, for $i\in I,k\notin J$, we have $1-\frac 1{n^2}<\frac{1}{1+x_ix_j}<1$ and for $j\in J,k\notin I$, we have $-\frac 1{n^2}<-\frac{1}{1+x_ix_j}<0$. Thus, the right hand side is strictly between $|I|(n-|J|)-1$ and $|I|(n-|J|)$, so we get a contradiction.

If now $X$ contains an element outside $[n^{-2n},n^{2n}]$, this argument can be applied with $A=1,n^2,n^4,n^{2(n-1)}$, giving us $n$ disjoint pairs of intervals each of which should have a point in $X$. Together with the point outside $[n^{-2n},n^{2n}]$, we would have $n+1$ or more points in $X$, which is a clear overcount. Thus, our assumption is false and we must have $n^{-2n}\le r_j\le n^{2n}$ for all $j$.

  • 0
    Wow, that is a beautiful argument! Thank you!2012-09-11
0

With $0 < r_1 \leq r_2 \leq \cdots \leq r_n$, you can obtain an upper bound on $r_1$ as $r_1 \leq \sqrt{n-1} \leq \sqrt{n}$. However, it doesn't give an upper bound on $r_n$.

Here is how it goes. First you can simplify the sum to get

$2 \leq n-\sum_{j=1}^n \frac{1}{1+r_ir_j} \leq n-1$

Simplifying, you'll obtain

$1 \leq \sum_{j=1}^n \frac{1}{1+r_ir_j} \leq n-2$

Now,

$1+r_1^2 \leq 1+r_ir_j \leq 1+r_n^2$

so, using on the the left inequality here

$1 \leq \sum_{j=1}^n \frac{1}{1+r_ir_j} \leq \frac{n}{1+r_1^2}$

and the bound follows.

  • 0
    Thanks for the response. I derived something similar for $r_1$ and it's totally bizarre why this doesn't shed much light on $r_n$. In fact I was able to show that if $r_n$ is larger than $n$, then $r_1$ must be less than 1.2012-09-08