Representing a number close to 1 with a sum of reciprocals of natural numbers

Question

For positive integers $n_1, \ldots, n_k$, let $H(n_1, \ldots, n_k)$ denote $1/n_1 + \ldots + 1/n_k$. Let $V(N)$ be the largest possible value of $H(n_1, \ldots, n_k)$ that is less than 1, subject to the condition that $n_1 + \ldots +n_k \le N$. So $V(5) = 5/6$, realized as $1/2 + 1/3$. My question is, how does $1/(1-V(N))$ grow as a function of $N$? In particular, is there a $C$ and a $k$ such that $$ \frac 1{1-V(N)} \le C N^k\ $$ for all $N$?

Answer 1

$K(N) := 1 / (1 - V(N))$ grows faster than any power of $N$.

This can be seen by finding for each $k$ an identity $$ \sum_{i=1}^m \frac{A_i x + B_i}{C_i x + D_i} = 1 - c x^{-(2k+1)} + O(x^{-(2k+2)}) $$ where the coefficients $A_i,B_i,C_i,D_i$ are integers with $A_i, C_i > 0$ and $c$ is a positive rational number (and the right-hand side is a Taylor expansion about $x=\infty$). Once we have such an identity, we can take for $x$ a large integer (in particular large enough that the denominators $C_i x + D_i$ and numerators $A_i x + B_i$ are all positive), and write each term $(A_i x + B_i) \, / \, (C_i x + D_i)$ as a sum of $A_i x + B_i$ copies of the reciprocal of $C_i x + D_i$. Then as $x\rightarrow\infty$ the sum $N$ of the denominators grows as a multiple of $x^2$, while $1/(1-H)$ grows as $x^{2k+1}$ which is faster than $N^k$.

The identity we need is easy to construct because the conditions on the coefficients are linear in the $B_i$ (and also in the $A_i$, but we do not use this). For example, fix distinct rationals $\delta_i$ and positive rationals $\alpha_i$ with $\sum_{i=1}^m \alpha_i = 1$, and then find rational $\beta_i$ such that $$ \sum_{i=1}^m \frac{\alpha_i x + \beta_i}{x + \delta_i} = 1 + O(x^{-(2k+1)}); $$ that's $2k$ independent linear equations in $m$ unknowns, so there exists a solution once $m \geq 2k$. Then write each term $(\alpha_i x + \beta_i) / (x + \delta_i)$ as $(A_i x + B_i) \, / \, (C_i x + D_i)$ with integer coefficients. We must show that there is a choice of $\alpha_i$ and $\delta_i$ that makes the $x^{-(2k+1)}$ coefficient nonzero; but this is easy, for example because otherwise that coefficient would vanish identically, even if we allowed complex $\alpha_i$ and $\delta_i$, and that's contradicted (for $m=2k+1$) by the partial-fraction decomposition of the rational function $X^{2k+1} / (X^{2k+1} - 1)$. Jeremy Kahn insists that the $x^{-(2k+1)}$ coefficient be negative, but if our recipe happens to yield a positive coefficient then we can get a negative one by changing each $B_i$ and $D_i$ to $-B_i$ and $-D_i$ respectively (that's why we used an odd exponent $2k+1$).

It may be reasonable to expect that $K(N)$ grows almost as fast as the number of partitions $(n_1,\ldots,n_k)$ of $N$, i.e. $\log K(N)$ should be asymptotic to some multiple of $\sqrt{N}$ (or at any rate it should grow not much slower than $\sqrt{N})$, because there are plenty of partitions for which $\sum_{i=1}^k 1/n_i < 1$. Numerical computation seems to corroborate this guess; here are the record values of $K(N)$ for $2 \leq N \leq 72$, followed by the total number of partitions and the count of partitions with $\sum_{i=1}^k 1/n_i < 1$:

 N     K(N)        #      #1
 2      2          2       2
 5      6          7       3
10     12         42       7
11     20         56       9
12     42         77      13
17     60        297      26
19    120        490      39
23    156       1255      79
29    168       4565     194
30    231       5604     230
31   1320       6842     265
44   3740      75175    1519
49   5040     173525    2754
57  23100     614154    6832
67  34807.5  2679689   20372
70  47058    4087968   27744

Curiously $K(N)$ is always an integer in this range, except for $K(N) = 34807\!\frac12 = 2^{-1} \, 3^2 \, 5 \; 7 \; 13 \; 17$ for $67 \leq N \leq 69$. Here's the gp code that generated this data (in about 10 minutes):

S(v) = sum(i=1,#v,1/v[i])

{
K(n, v,p,c) =
  v = partitions(n);
  p = #v;
  v = vecsort(vector(p,i,S(v[i])));
  c = 1;
  while(v[c]<1,c++);
  [n, 1. / (1-v[c-1]), p, c]
}

\p 9
allocatemem(2^31)
#
for(n=2,72,print(K(n)))

ADDED LATER: Here's some further computational data. Using gp-2.6's new function forpart in place of partitions, and removing the unnecessary sort, avoids using $p(n)$ space; we also save time by not trying any partition with $n_1=1$. This lets us extend the calculation to $N=100$ in about half an hour. Here are the records (now including two more non-integral values for $74 \leq N \leq 79$), together with all partitions that attain them:

 N        K     n_i
 2        2     2
 5        6     2, 3
10       12     3, 3, 4
11       20     2, 4, 5
12       42     2, 3, 7
17       60     3, 4, 5, 5
19      120     3, 3, 5, 8
21      """     2, 5, 6, 8
23      156     3, 3, 4, 13
25      """     2, 4, 6, 13
29      168     3, 4, 7, 7, 8
30      231     2, 3, 11, 14
32      420     2, 4, 5, 21
33      """     3, 4, 5, 7, 14
38     1320     2, 5, 8, 11, 12
40     """"     4, 5, 6, 6, 8, 11
44     3740     2, 4, 10, 11, 17
47     """"     4, 5, 5, 5, 11, 17
49     5040     3, 4, 7, 9, 10, 16
56     """"     2, 7, 9, 10, 12, 16
57    23100     3, 4, 7, 7, 11, 25
64    """""     2, 7, 7, 11, 12, 25
66    """""     4, 6, 6, 7, 7, 11, 25
67    34807.5   3, 5, 7, 9, 13, 13, 17
70    47058     2, 3, 11, 23, 31
74    59690.4   2, 4, 11, 17, 19, 21
75    """""""   3, 4, 7, 11, 14, 17, 19
79    91162.5   3, 5, 5, 11, 13, 17, 25
80   200970     3, 5, 7, 7, 11, 18, 29
83   """"""     5, 6, 7, 7, 9, 9, 11, 29
89   """"""     5, 6, 6, 7, 7, 11, 18, 29
92   239085     5, 5, 7, 7, 7, 11, 23, 27
96   405720     2, 5, 8, 9, 23, 49

and here's the gp-2.6 code:

\\ gp-2.6
S(v) = sum(i=1,#v,1/v[i])

{
K(n, p,p1,c,c1) =
  c = 0;
  p = [];
  forpart(p1=n, c1=S(p1); if((c1<1) && (c1>=c),
    if(c==c1, p=concat(p,[Vec(p1)]), c=c1; p=[Vec(p1)])
  ), [2,n]);
[n, 1./(1-c), p]
}

\p 10
#
for(n=2,100,print(K(n)))

Answer 2

Some greater detail about the context for the question. Thurston (see Doaudy and Hubbard) considers a branched cover $f\colon S^2 \to S^2$ such that $P_f \equiv \{ f^n(c) \mid c \in C_f$ is finite (where $C_f$ is the set of critical points of $f$). He defines a map $\sigma_f$ from $\operatorname{Teich}(S^2, P_f)$ to itself by pulling back complex structures (up to maps isotopic to the identify rel $P_f$) by $f$. The fixed points for $\sigma_f$ are exactly the rational maps that are "combinatorially equivalent" to $f$. Moreover, he proves that in the generic case for $f$, the map $\sigma_f$ is uniformly contracting on compact subsets of $M(S^2, P_f)$, which is just the space of maps of $P_f$ into the Riemann sphere, up to Moebius transformation.

Moreover we understand the map $\sigma_f$ up to a bounded error as follows. Let $WA(S^2, P_f)$ be the space of real-weighted sums of disjoint curves (nontrivial and nonperipheral, and up to homotopy) on $S^2 \setminus P_f$. We can define a map $W \colon \operatorname{Teich}(S^2, P_f) \rightarrow WA(S^2, P_f)$ by weighting each curve by the modulus of the associated covering annulus, and then discarding the curves of weight less that 1. Moreover we can prove the fundamental estimate that $$ W(\sigma_f(X)) = f^*W(X) + O(1) $$ for all $X \in \operatorname{Teich}(S^2, P_f)$, where $f^*\colon WA(S^2, P_f) \to WA(S^2, P_f)$ is defined by $$ f^*\gamma = \sum_{f(\eta) = \gamma} \frac1{\operatorname{deg} f|_\eta} \eta. $$ Here the constant for the O(1) depends only on $\operatorname{deg} f$ and $|P_f|$.

Now suppose that $\alpha$ is an "invariant multicurve", which means that $f^{-1}(\alpha) \subset \alpha$. Then $f^*\colon \mathbb R^\alpha \to \mathbb R^\alpha$ is a positive linear transformation (or at least nonnegative) and so has a positive leading eigenvalue $\lambda_\alpha$. If $\lambda_\alpha > 1$ it is easy to prove that $\sigma_f^nX \to \infty$ as $n \to \infty$, for any starting point $X$. It turns out that same also holds if $\lambda_\alpha = 1$.

If $\lambda_\alpha = 1 - 1/K$ then we expect to take about $K$ iterations of $\sigma_f$ to get to a place where the covering annuli have modulus about $K$. In particular if $\alpha$ is just a single curve then we will have $$ W_\alpha(\sigma_f X) = (1-1/K) W_\alpha(X) + O(1) $$ where the $O(1)$ term is positive and converges in the course of the iteration.

Now we should be able to construct a branched cover $f$ of degree about $N$ (say with $|P_f| = 4$) and a single curve $\alpha$ on $S^2 \setminus P_f$ such that $f^*\colon \mathbb R^\alpha \to \mathbb R^\alpha$ is multiplication by $1 - 1/K(N)$, and then by Noam Elkies' estimate we find that the number of iterations of $\sigma_f$ to get near the fixed point (from a reasonable starting point) can grow superpolynomially in $\operatorname{deg} f$ and $|P_f|$. So the iteration of $\sigma_f$ is not a polynomial-time algorithm to find the fixed point of $\sigma_f$ (which is the unique rational map representing $f$).

Answer 3

You might want to check out the references in the Wikipedia article on Egyptian Fractions.

Answer 4

A specific paper that comes to mind is "On Engel's and Sylvester's series" by Erdos, Renyi, and Szusz. It is available here. The Sylvester series is the so called "Greedy Egyptian fraction". We let $x=\frac {1} {Q_1(x)}+\frac {1}{Q_2(x)}+\cdots$ be the Sylvester series for $x \in (1,\infty)$. They prove (Theorem 6) that for almost every $x$

$$ \lim_{n \to \infty} \frac {\log Q_n(x)} {2^n} $$

exists and is finite. They use probabilistic methods to arrive at this result. They also arrive at a similar result for Engel series. This is definitely different from what you're looking for, but to me it seems to be somewhat similar in that you're still trying to arrive at asymptotics that come from these sorts of expansions. So maybe there are some relevant techniques that they use?