6
$\begingroup$

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?

$\endgroup$

4 Answers 4

5
$\begingroup$

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.

$\endgroup$
9
  • 1
    $\begingroup$ "if $K_1\ne K_2$ the order of magnitude of the difference is actually $\frac1{n^{\min(K_1,K_2)}}$" Why? $\endgroup$ Oct 2, 2010 at 14:59
  • 1
    $\begingroup$ 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)}}$. $\endgroup$ Oct 2, 2010 at 16:13
  • 1
    $\begingroup$ 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}}$. $\endgroup$ Oct 2, 2010 at 17:05
  • 3
    $\begingroup$ $|\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}}$. $\endgroup$ Oct 2, 2010 at 17:31
  • 2
    $\begingroup$ 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. $\endgroup$ Oct 3, 2010 at 4:05
3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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$? $\endgroup$ Oct 3, 2010 at 22:10
  • $\begingroup$ 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. $\endgroup$
    – zeb
    Oct 3, 2010 at 23:21
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thank you for answering. I was more interested in lower bounds of the difference. $\endgroup$
    – Anadim
    Oct 2, 2010 at 17:24
1
$\begingroup$

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 .

$\endgroup$
2
  • 2
    $\begingroup$ Well, actually he gave the bound - denominators should be no larger than $n$. $\endgroup$ Oct 2, 2010 at 9:51
  • $\begingroup$ 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. $\endgroup$
    – Anadim
    Oct 2, 2010 at 16:40

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.