Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I had this question bothering me for a while, but I can't come up with a meaningful answer. The problem is the following:

Let integers $a_i,b_j\in${$1,\ldots,n$} and $K_1,K_2\in$ {$1,\ldots,K$}, then how small (as a function of $K$ and $n$), but strictly positive, can the following absolute difference be.

$\biggl|(\sum_{i=1}^{K_1} \frac{1}{a_i})-(\sum_{j=1}^{K_2} \frac{1}{b_j})\biggr|$

As an example for $K_1=1,$$K_2=1$ choosing $a_1=n,$$b_1=n-1$gives the smallest positive absolute difference, that is $\frac{1}{n(n-1)}$. What could the general case be?

share|improve this question
add comment

4 Answers

up vote 5 down vote accepted

A sum of $K$ unit fractions, each of denominator $n_i \leq n$, can be rewritten as a fraction with a denominator bounded by the product of the $n_i$, i.e. by $n^K$. (A small improvement is possible, with product of distinct integers $\leq n$)

A difference of two such fractions
(which are themselves sums of $K_1$ and $K_2$ fractions, respectively), is a fraction with a demominator bounded by $n^{K_1+K_2}$. (If $K_1\neq K_2$ the order of magnitude of the difference is actually $\frac{1}{n^{\min(K_1,K_2)}}$.)

Let us assume that $K_1=K_2$. So, the smallest nonzero difference $d(K,n)$ of sums of $K$ unit fractions, with $n_i \leq n$ is $d(K, n)\leq \frac{1}{n^{2K}}$.

I believe that this order of magnitude, with slightly weaker constants, can be achieved with a constructive parametrization.

Example: If $K_1=K_2=2$, then choose $\frac{1}{x^2 + 4 x + 1} + \frac{1}{x^2 + 4 x + 3} - \frac{1}{x^2 + 3 x + 1} - \frac{1}{x^2 + 5 x + 5}= \frac{2}{(1 + 3 x + x^2) (1 + 4 x + x^2) (3 + 4 x + x^2) (5 + 5 x + x^2)}$. Now, taking $n=x^2+5x+5$, one has a set of 4 unit fractions, for which the difference of the sums above is asymptotically $ \frac{2}{n^4}$. This example is (for $K_1=K_2=2$) possibly the best one can find, (but I did not prove this).

I conjecture that for larger values of $K$ one can construct similar polynomial examples.

Quite possibly this has applications in questions in diophantine approximation, exponential sums, large sieve etc.

share|improve this answer
1  
"if $K_1\ne K_2$ the order of magnitude of the difference is actually $\frac1{n^{\min(K_1,K_2)}}$" Why? –  Fedor Petrov Oct 2 '10 at 14:59
1  
Indeed, that was not quite correct. (Thanks for spotting this!) If $K_1>K_2$ the smallest possible order of magnitude is $\frac{1}{n^{\max(K_1,2 K_2)}}$. –  Christian Elsholtz Oct 2 '10 at 16:13
1  
My argument above shows that the smallest nonzero difference $d(K,n)\geq \frac{1}{n^{2K}}$ (there was a typos, I mixed up with $\leq$. Maybe this is the lower bound you need. If $K_1 >K_2$, the smallest the (nonzero) difference can be is, if both rationals (as sums of $K_1$ or $K_2$ unit fractions) have denominators of order of magnitude $n^{K_2}$ so that the nonzero difference is at least $d(K_1,K_2,n)\geq \frac{1}{n^{2K_2}}$. –  Christian Elsholtz Oct 2 '10 at 17:05
3  
$|\frac{a}{b}-\frac{c}{d}| = \frac{|ad-bc|}{bd}\geq \frac{1}{bd}$. For the last step observe that $ad-bc$ is an integer. If it's not zero, then it is at least one. So, of $b$ and $d$ are bounded above by $n^K$, you get the requested lower bound of $\frac{1}{n^{2K}}$. –  Christian Elsholtz Oct 2 '10 at 17:31
2  
I think I disagree with the claim for the case $K_1\gt K_2$. Say $K_1=2$, $K_2=1$. Then the identity $${1\over2x+1}+{1\over2x-1}-{1\over x}={1\over4x^3-x}$$ gives you $2n^{-3}$, whereas it looks like you are claiming only $cn^{-2}$ is possible. –  Gerry Myerson Oct 3 '10 at 4:05
show 4 more comments

We can prove Christian Elsholtz's conjecture using only linear functions.

Let $m_1, ..., m_{2K}$ and $\alpha_1, ..., \alpha_{2K}$ be integers satisfying $\sum_i \frac{\alpha_i^j}{m_i} = 0$ for $j = 0, ..., 2K-2$. Then for large $x$ we have

$\sum_i \frac{1}{m_ix - m_i\alpha_i} = \frac{1}{x}\sum_i\frac{1}{m_i}\sum_j\frac{\alpha_i^j}{x^j} = \sum_j \frac{1}{x^{j+1}} \sum_i \frac{\alpha_i^j}{m_i} \approx \frac{C}{x^{2K}}$,

where $C = \sum_i \frac{a_i^{2K-1}}{m_i}$.

For instance, we can pick $\alpha_i = i-1, m_i = \frac{(-1)^iD}{\binom{2K-1}{i}}$, where $D$ is a multiple of $\binom{2K-1}{i}$ for each $i$. Then we will have the same number of positive and negative $m_i$s, so for large $x$ half of the fractions will be positive and half will be negative.

Examples:

$\frac{1}{3x} + \frac{1}{x-2} - \frac{1}{x-1} - \frac{1}{3x-9} = \frac{-2}{x(x-1)(x-2)(x-3)}$, and

$\frac{1}{10x} + \frac{1}{x-2} + \frac{1}{2x-8} - \frac{1}{2x-2} - \frac{1}{x-3} - \frac{1}{10x-50} = \frac{-12}{x(x-1)(x-2)(x-3)(x-4)(x-5)}$.

share|improve this answer
    
Very nice. The constants are not so good; for $K=2$, you're getting $162n^{-4}$, where CE gets $2n^{-4}$. Do you get anything for the "unbalanced" case, $K_1\ne K_2$? –  Gerry Myerson Oct 3 '10 at 22:10
    
I don't know if this method can give us anything useful for the general unbalanced case - no matter which $\alpha_i$s we choose, the corresponding $m_i$s still should alternate in sign. We can use it to handle the case $K_1 = K_2 + 1$, though. –  zeb Oct 3 '10 at 23:21
add comment

if $k_1=k_2$

$A=\biggl|(\sum_{i=1}^{K_1} \frac{1}{a_i})-(\sum_{j=1}^{K_1} \frac{1}{b_j})\biggr|\le\sum_{i=1,j=1}^{K_1}\biggl|\frac{1}{a_i}-\frac{1}{b_j}\biggr|$

we assume that $a_i=n$ and $b_j=n-1$,so $A\le \frac{k_1}{n(n-1)}$

if $k_1\le k_2$,and assume that$a_i=n$ and $b_j=n-1$,so $A\le \frac{k_2}{n(n-1)}$

Added:let $a_i=b_i+b_i^{mk-2}$,$mk\ge 2$,$m$ is positive integer ,$1\le b_i\le n$, and $k_1\ge k_2$,so

$\biggl|(\sum_{i=1}^{K_1} \frac{1}{b_i})-(\sum_{i=1}^{K_2} \frac{1}{a_i})\biggr|$,this is

larger or equal to ,$\sum_{i=1}^{K_1}\frac{b_i^{mk-2}}{b_i(b_i+b_i^{mk-2})}\ge\sum_{i=1}^{K_1}

\frac{1}{b_i(b_i+b_i^{mk-2})}\ge\frac{k_1}{n^{mk}}$

share|improve this answer
    
Thank you for answering. I was more interested in lower bounds of the difference. –  Anadim Oct 2 '10 at 17:24
add comment

See http://en.wikipedia.org/wiki/Egyptian_fraction for some background. You are asking about the difference of rational numbers which can be any positive rationals. So the lower bound is in terms of what? It is natural to ask in terms of the maximum size of required denominator. I think the bound in that article in "Modern number theory" probably answers that question. It should come down to how far apart you can be sure the Farey sequence fractions are (which is known and elementary): http://en.wikipedia.org/wiki/Farey_sequence .

share|improve this answer
2  
Well, actually he gave the bound - denominators should be no larger than $n$. –  Nurdin Takenov Oct 2 '10 at 9:51
    
Thank you for your answer. I checked the wiki entry, but for my case the unit fractions need not be distinct, that is, not all $a_i$s (or all $b_j$s) are distinct. I wanted to find an asymptotic lower bound with respect to $n$. So basically I tried to find whether the difference can be lower bounded by some 1/poly(n), or not. –  Anadim Oct 2 '10 at 16:40
add comment

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.