Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

2 Answers 2

up vote 1 down vote accepted
+50

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$.

share|improve this answer
    
Wow, that is a beautiful argument! Thank you! –  Alex R. Sep 11 '12 at 0:12

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.

share|improve this answer
    
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. –  Alex R. Sep 8 '12 at 17:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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