Skip to main content
added 382 characters in body
Source Link
Lucia
  • 43.7k
  • 6
  • 193
  • 218

Let $n_0$ be the smallest number such that the sum of the reciprocals of the integers from $n_0+1$ to $n$ is $<2$. It is easy to see that $n_0 \approx n/e^2$, since $\sum_{j>n/e^2}^{n} 1/j \approx \log n - \log (n/e^2) =2$. Now for any subset $A$ of $\{n_0 +1, \ldots, n\}$ either the sum of the reciprocals of elements in $A$ or the sum of the reciprocals of its complement must be $<1$. Therefore there are at least $$ \frac 12 2^{n-n_0} \asymp 2^{n(1-1/e^2)} $$ possible sets. My guess is that this exponent $1-1/e^2$ is correct -- note that $1-1/e^2 = 0.86466\ldots$.

Maybe my first guess is not right! Here's an upper bound, which gives an exponent around $0.91\ldots$ (my numerical calculations are pretty rough). For any positive $x$, an upper bound on the quantity we want is $$ e^x \prod_{j=1}^n (1+e^{-x/j}). $$ To see this, just expand out the product and terms with sum of reciprocals less than $1$ will contribute at least $1$, and the rest are positive. Now choose $x$ so as to minimize the above (a standard idea, known in analytic number theory as Rankin's trick).

Calculus shows that one must choose $x$ so that $$ 1= \sum_{j=1}^{n} \frac 1j \frac{1}{1+e^{x/j}}. $$ It is natural to guess that $x$ is of the shape $\alpha n$ for a constant $\alpha$, and then for large $n$ the condition on $\alpha$ becomes $$ 1= \int_0^1 \frac{1}{1+e^{\alpha/y}} \frac{dy}{y} = \int_1^\infty \frac{1}{1+e^{\alpha y}} \frac{dy}{y}. $$ If I calculated right, this gives $\alpha \approx 0.1273$. For this choice of $\alpha$ (and so $x$), one obtains the bound (approximately) $$ \exp\Big(n\Big( \alpha + \int_0^1 \log (1+e^{-\alpha/y}) dy\Big)\Big), $$ which seems to be about $$ \exp(-.631n) \approx 2^{0.911n}. $$ (I won't swear to the numerics -- someone should check.) Maybe one can get a better lower

My second guess is that the upper bound by a probabilistic construction based onis tight (and I think this could be proved with some effort). The idea is to choose $j$ to be in your set with probability $1/(1+\exp(x/j))$ with the same $x$ as in the upper bound. The expected value of $1/j$ with this distribution is $1$, by the choice of $x$. An entropy calculation for this distribution then gives the exponent. (More generally, in all the situations I know, the Rankin upper bound is pretty close to optimal.)

Let $n_0$ be the smallest number such that the sum of the reciprocals of the integers from $n_0+1$ to $n$ is $<2$. It is easy to see that $n_0 \approx n/e^2$, since $\sum_{j>n/e^2}^{n} 1/j \approx \log n - \log (n/e^2) =2$. Now for any subset $A$ of $\{n_0 +1, \ldots, n\}$ either the sum of the reciprocals of elements in $A$ or the sum of the reciprocals of its complement must be $<1$. Therefore there are at least $$ \frac 12 2^{n-n_0} \asymp 2^{n(1-1/e^2)} $$ possible sets. My guess is that this exponent $1-1/e^2$ is correct -- note that $1-1/e^2 = 0.86466\ldots$.

Maybe my first guess is not right! Here's an upper bound, which gives an exponent around $0.91\ldots$ (my numerical calculations are pretty rough). For any positive $x$, an upper bound on the quantity we want is $$ e^x \prod_{j=1}^n (1+e^{-x/j}). $$ To see this, just expand out the product and terms with sum of reciprocals less than $1$ will contribute at least $1$, and the rest are positive. Now choose $x$ so as to minimize the above (a standard idea, known in analytic number theory as Rankin's trick).

Calculus shows that one must choose $x$ so that $$ 1= \sum_{j=1}^{n} \frac 1j \frac{1}{1+e^{x/j}}. $$ It is natural to guess that $x$ is of the shape $\alpha n$ for a constant $\alpha$, and then for large $n$ the condition on $\alpha$ becomes $$ 1= \int_0^1 \frac{1}{1+e^{\alpha/y}} \frac{dy}{y} = \int_1^\infty \frac{1}{1+e^{\alpha y}} \frac{dy}{y}. $$ If I calculated right, this gives $\alpha \approx 0.1273$. For this choice of $\alpha$ (and so $x$), one obtains the bound (approximately) $$ \exp\Big(n\Big( \alpha + \int_0^1 \log (1+e^{-\alpha/y}) dy\Big)\Big), $$ which seems to be about $$ \exp(-.631n) \approx 2^{0.911n}. $$ (I won't swear to the numerics -- someone should check.) Maybe one can get a better lower bound by a probabilistic construction based on this idea ...

Let $n_0$ be the smallest number such that the sum of the reciprocals of the integers from $n_0+1$ to $n$ is $<2$. It is easy to see that $n_0 \approx n/e^2$, since $\sum_{j>n/e^2}^{n} 1/j \approx \log n - \log (n/e^2) =2$. Now for any subset $A$ of $\{n_0 +1, \ldots, n\}$ either the sum of the reciprocals of elements in $A$ or the sum of the reciprocals of its complement must be $<1$. Therefore there are at least $$ \frac 12 2^{n-n_0} \asymp 2^{n(1-1/e^2)} $$ possible sets. My guess is that this exponent $1-1/e^2$ is correct -- note that $1-1/e^2 = 0.86466\ldots$.

Maybe my first guess is not right! Here's an upper bound, which gives an exponent around $0.91\ldots$ (my numerical calculations are pretty rough). For any positive $x$, an upper bound on the quantity we want is $$ e^x \prod_{j=1}^n (1+e^{-x/j}). $$ To see this, just expand out the product and terms with sum of reciprocals less than $1$ will contribute at least $1$, and the rest are positive. Now choose $x$ so as to minimize the above (a standard idea, known in analytic number theory as Rankin's trick).

Calculus shows that one must choose $x$ so that $$ 1= \sum_{j=1}^{n} \frac 1j \frac{1}{1+e^{x/j}}. $$ It is natural to guess that $x$ is of the shape $\alpha n$ for a constant $\alpha$, and then for large $n$ the condition on $\alpha$ becomes $$ 1= \int_0^1 \frac{1}{1+e^{\alpha/y}} \frac{dy}{y} = \int_1^\infty \frac{1}{1+e^{\alpha y}} \frac{dy}{y}. $$ If I calculated right, this gives $\alpha \approx 0.1273$. For this choice of $\alpha$ (and so $x$), one obtains the bound (approximately) $$ \exp\Big(n\Big( \alpha + \int_0^1 \log (1+e^{-\alpha/y}) dy\Big)\Big), $$ which seems to be about $$ \exp(-.631n) \approx 2^{0.911n}. $$ (I won't swear to the numerics -- someone should check.)

My second guess is that the upper bound is tight (and I think this could be proved with some effort). The idea is to choose $j$ to be in your set with probability $1/(1+\exp(x/j))$ with the same $x$ as in the upper bound. The expected value of $1/j$ with this distribution is $1$, by the choice of $x$. An entropy calculation for this distribution then gives the exponent. (More generally, in all the situations I know, the Rankin upper bound is pretty close to optimal.)

added 1346 characters in body
Source Link
Lucia
  • 43.7k
  • 6
  • 193
  • 218

Let $n_0$ be the smallest number such that the sum of the reciprocals of the integers from $n_0+1$ to $n$ is $<2$. It is easy to see that $n_0 \approx n/e^2$, since $\sum_{j>n/e^2}^{n} 1/j \approx \log n - \log (n/e^2) =2$. Now for any subset $A$ of $\{n_0 +1, \ldots, n\}$ either the sum of the reciprocals of elements in $A$ or the sum of the reciprocals of its complement must be $<1$. Therefore there are at least $$ \frac 12 2^{n-n_0} \asymp 2^{n(1-1/e^2)} $$ possible sets. My guess is that this exponent $1-1/e^2$ is correct -- note that $1-1/e^2 = 0.86466\ldots$.

Maybe my first guess is not right! Here's an upper bound, which gives an exponent around $0.91\ldots$ (my numerical calculations are pretty rough). For any positive $x$, an upper bound on the quantity we want is $$ e^x \prod_{j=1}^n (1+e^{-x/j}). $$ To see this, just expand out the product and terms with sum of reciprocals less than $1$ will contribute at least $1$, and the rest are positive. Now choose $x$ so as to minimize the above (a standard idea, known in analytic number theory as Rankin's trick).

Calculus shows that one must choose $x$ so that $$ 1= \sum_{j=1}^{n} \frac 1j \frac{1}{1+e^{x/j}}. $$ It is natural to guess that $x$ is of the shape $\alpha n$ for a constant $\alpha$, and then for large $n$ the condition on $\alpha$ becomes $$ 1= \int_0^1 \frac{1}{1+e^{\alpha/y}} \frac{dy}{y} = \int_1^\infty \frac{1}{1+e^{\alpha y}} \frac{dy}{y}. $$ If I calculated right, this gives $\alpha \approx 0.1273$. For this choice of $\alpha$ (and so $x$), one obtains the bound (approximately) $$ \exp\Big(n\Big( \alpha + \int_0^1 \log (1+e^{-\alpha/y}) dy\Big)\Big), $$ which seems to be about $$ \exp(-.631n) \approx 2^{0.911n}. $$ (I won't swear to the numerics -- someone should check.) Maybe one can get a better lower bound by a probabilistic construction based on this idea ...

Let $n_0$ be the smallest number such that the sum of the reciprocals of the integers from $n_0+1$ to $n$ is $<2$. It is easy to see that $n_0 \approx n/e^2$, since $\sum_{j>n/e^2}^{n} 1/j \approx \log n - \log (n/e^2) =2$. Now for any subset $A$ of $\{n_0 +1, \ldots, n\}$ either the sum of the reciprocals of elements in $A$ or the sum of the reciprocals of its complement must be $<1$. Therefore there are at least $$ \frac 12 2^{n-n_0} \asymp 2^{n(1-1/e^2)} $$ possible sets. My guess is that this exponent $1-1/e^2$ is correct -- note that $1-1/e^2 = 0.86466\ldots$.

Let $n_0$ be the smallest number such that the sum of the reciprocals of the integers from $n_0+1$ to $n$ is $<2$. It is easy to see that $n_0 \approx n/e^2$, since $\sum_{j>n/e^2}^{n} 1/j \approx \log n - \log (n/e^2) =2$. Now for any subset $A$ of $\{n_0 +1, \ldots, n\}$ either the sum of the reciprocals of elements in $A$ or the sum of the reciprocals of its complement must be $<1$. Therefore there are at least $$ \frac 12 2^{n-n_0} \asymp 2^{n(1-1/e^2)} $$ possible sets. My guess is that this exponent $1-1/e^2$ is correct -- note that $1-1/e^2 = 0.86466\ldots$.

Maybe my first guess is not right! Here's an upper bound, which gives an exponent around $0.91\ldots$ (my numerical calculations are pretty rough). For any positive $x$, an upper bound on the quantity we want is $$ e^x \prod_{j=1}^n (1+e^{-x/j}). $$ To see this, just expand out the product and terms with sum of reciprocals less than $1$ will contribute at least $1$, and the rest are positive. Now choose $x$ so as to minimize the above (a standard idea, known in analytic number theory as Rankin's trick).

Calculus shows that one must choose $x$ so that $$ 1= \sum_{j=1}^{n} \frac 1j \frac{1}{1+e^{x/j}}. $$ It is natural to guess that $x$ is of the shape $\alpha n$ for a constant $\alpha$, and then for large $n$ the condition on $\alpha$ becomes $$ 1= \int_0^1 \frac{1}{1+e^{\alpha/y}} \frac{dy}{y} = \int_1^\infty \frac{1}{1+e^{\alpha y}} \frac{dy}{y}. $$ If I calculated right, this gives $\alpha \approx 0.1273$. For this choice of $\alpha$ (and so $x$), one obtains the bound (approximately) $$ \exp\Big(n\Big( \alpha + \int_0^1 \log (1+e^{-\alpha/y}) dy\Big)\Big), $$ which seems to be about $$ \exp(-.631n) \approx 2^{0.911n}. $$ (I won't swear to the numerics -- someone should check.) Maybe one can get a better lower bound by a probabilistic construction based on this idea ...

Source Link
Lucia
  • 43.7k
  • 6
  • 193
  • 218

Let $n_0$ be the smallest number such that the sum of the reciprocals of the integers from $n_0+1$ to $n$ is $<2$. It is easy to see that $n_0 \approx n/e^2$, since $\sum_{j>n/e^2}^{n} 1/j \approx \log n - \log (n/e^2) =2$. Now for any subset $A$ of $\{n_0 +1, \ldots, n\}$ either the sum of the reciprocals of elements in $A$ or the sum of the reciprocals of its complement must be $<1$. Therefore there are at least $$ \frac 12 2^{n-n_0} \asymp 2^{n(1-1/e^2)} $$ possible sets. My guess is that this exponent $1-1/e^2$ is correct -- note that $1-1/e^2 = 0.86466\ldots$.