39
$\begingroup$

Consider a set of fractions $\left\{1, \frac{1}{2}, \frac{1}{3}, \ldots, \frac{1}{n}\right\}$. How many subsets of this set have sum at most 1? I'm interested in the asymptotics of this number.

Clearly, any subset of $\left\{\frac{1}{\lceil n/2 \rceil}, \ldots, \frac{1}{n}\right\}$ works, hence the answer is $\Omega(2^{n / 2})$. Can we show $\Omega(2^{\beta n})$ for $\beta > \frac{1}{2}$? Can we determine $\beta$ exactly? From numeric estimates of OEIS sequence $\beta$ seems to at least $0.88$ (link to the sequence and correction of the estimate due to Max Alekseyev).

The question arose while I was thinking about upper bounds for this question. Clearly, every divisibility antichain $I$ of $[n]$ must satisfy $\sum_{x \in I} \lfloor\frac{n}{x}\rfloor \leq n$, which is a very similar condition.

Post-mortem: while I accepted Lucia's answer (simply because it was the first to contain the correct answer and some reasoning to why it is correct), the whole discussion here is very valuable. Be sure to also check out js21's answer with an approach based on large deviations method, and RaphaelB4's answer for a more off-the-ground explanation of the method. In a comment Jay Pantone shared a link to a paper on series analysis, in particular, the differential approximation method allows to obtain the same answer with high precision and is, without doubt, a great practical tool. Kudos to all of you guys! What a great day to learn.

$\endgroup$
  • 3
    $\begingroup$ oeis.org/A212657 $\endgroup$ – Max Alekseyev Sep 14 '17 at 11:51
  • 1
    $\begingroup$ The data in the OEIS suggest that $\beta$ may be larger than 0.88 $\endgroup$ – Max Alekseyev Sep 14 '17 at 12:06
  • $\begingroup$ Somehow it seems that a similar question was asked on MO many years ago, unfortunately I cannot find it right now. Perhaps someone else can! $\endgroup$ – Suvrit Sep 14 '17 at 12:32
  • 1
    $\begingroup$ Differential approximation suggests that the sequence grows like $C\alpha^nn^{\gamma}$ where $\alpha \in [1.8805,1.8807]$ and $\gamma \in [-0.498, -0.494]$. This would imply $\beta \in [0.9111, 0.9113]$. $\endgroup$ – Jay Pantone Sep 14 '17 at 13:25
  • 3
    $\begingroup$ Differential approximation is a numerical estimation technique that uses known terms of a series to construct many linear differential equations with series expansions that match the known terms (and likely don't match later, unknown, terms). Then, the asymptotic behavior of the linear ODEs is read off and coalesced in a particular way, leading to an non-rigorous estimate of the asymptotic behavior of the sequence. It tends to be very accurate in practice. You can find more info (and more references) in the first 4 sections here: arXiv $\endgroup$ – Jay Pantone Sep 14 '17 at 13:41
35
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The numerical data in oeis.org/A212657 suggest that the exponent may be larger - at least 0.88 $\endgroup$ – Max Alekseyev Sep 14 '17 at 12:03
  • $\begingroup$ Cool! Is this a standard argument? Also, Max Alekseyev seems to be right, I used too small values for my estimates. I will update the answer with more precise value. $\endgroup$ – Mikhail Tikhomirov Sep 14 '17 at 12:12
  • 2
    $\begingroup$ Yes, expected value of $\sum 1/j$. Also, the argument could be made better, to give an asymptotic. The idea is to use the method of stationary phase (or saddle point method) -- one would integrate $e^s \prod_{j=1}^{n} (1+e^{-s/j}) /s$ over a vertical line $s=x+it$ with $t \in {\Bbb R}$ and $x$ chosen as in the upper bound. With some effort (a standard type of calculation), one should get an asymptotic of the form $C 2^{\beta n}/\sqrt{n}$, where $\beta \approx 0.911$ is the constant described above, and some constant $C$ that can be explicitly given. $\endgroup$ – Lucia Sep 14 '17 at 14:13
  • 4
    $\begingroup$ 0.911167... it is, indeed, though I used much rougher techniques (just partition $[\frac 1n,\frac Cn]$ into finitely many short intervals and look at how many numbers you can take in each interval). That will give you $\beta$ in no time but, certainly, not the fine asymptotics Lucia claimed :-) $\endgroup$ – fedja Sep 14 '17 at 15:51
  • 1
    $\begingroup$ @Andy -- In number theory, a couple of applications are (i) to getting a uniform bound on the number of integers up to $x$ composed only of prime factors below $y$; (ii) getting essentially the right order of magnitude for the partition function $p(n)$. It also arises very often as an intermediate step -- some quantity you must bound, but don't want to be too careful. This gives a quick and accurate estimate. $\endgroup$ – Lucia Sep 27 '17 at 14:13
16
$\begingroup$

The bound proposed by Lucia is correct. I add some detail and I stress that It is an application of "large deviation" theorem which is very very standard.

Set the following independent Bernoulli random variable defined as $$X_i=\begin{cases} 0 \text{ with } p=1/2\\ \frac{1}{i} \text{ with } p=1/2\end{cases}$$ Then we have the number of subset is given by $$ 2^n \mathbb{P}(\sum_{i=1}^n X_i \leq 1)$$

And we can then adapte the proof of the well known Cramer theorem. For a lower bound $$\mathbb{P}(\sum_{i=1}^n X_i\leq 1)=\mathbb{P}(e^{-x\sum_{i=1}^n X_i}\geq e^{-x})\leq \frac{\mathbb{E}(e^{-x\sum_{i=1}^n X_i})}{e^{-x}}$$ which give because of the independence of $X_i$ the formula that Lucia have already stated (I didn't know it is called Rankin bound) $$\mathbb{P}(\sum_{i=1}^n {X}_i \leq 1)\leq e^{x} \prod_i^n (e^{-\frac{x}{i}}+1)/2^n$$

There exists $x_0$ which minimise the right part.

Then introduce $$\tilde{X}_i=\begin{cases} 0 \text{ with } p=\frac{1}{1+e^\frac{-x_0}{i}}\\ \frac{1}{i} \text{ with } p=\frac{e^\frac{-x_0}{i}}{1+e^\frac{-x_0}{i}} \end{cases}$$

Remark that $$ \mathbb{E}(\sum_i \tilde{X}_i)=\frac{\mathbb{E}(\sum_i X_i e^{-x_0\sum_{i=1}^n X_i})}{\mathbb{E}(e^{-x_0\sum_{i=1}^n X_i})}=\partial_x [ln(\mathbb{E}(e^{-x_0\sum_{i=1}^n X_i}))]_{x=x_0}$$ But because $x_0$ is a minimum, $\partial_x [ln(\mathbb{E}(e^{-x_0\sum_{i=1}^n X_i}))-ln(e^{-x})]_{x=x_0}=0$ and therefore $\mathbb{E}(\sum_i \tilde{X}_i)=1$. But because of convexity for any $\epsilon>0$ changing $\tilde{X}$ by $\tilde{X}^\epsilon$ by replacing $x_0$ by $x=x_0+\epsilon n$ in the definition give $\mathbb{E}(\sum_i \tilde{X}_i)\leq 1-\delta(\epsilon)$ with $\delta(\epsilon)>0$. We have then that $\mathbb{P}(\sum\tilde{X}^\epsilon_i\leq 1)\geq \delta(\epsilon)$ We can then state the lower bound $$ \delta(\epsilon)\leq \mathbb{E}(1_{\sum(\tilde{X}_i^\epsilon)\leq 1})\leq \frac{\mathbb{E}(1_{\sum X_i \leq 1} e^{-x \sum_i X_i})}{\mathbb{E}(e^{-x \sum_i X_i})} \leq \frac{\mathbb{E}(1_{\sum X_i \leq 1} )e^{-x}}{\mathbb{E}(e^{-x \sum_i X_i})}$$ And to conclude $$ \delta(\epsilon)\frac{\mathbb{E}(e^{-x \sum_i X_i})}{e^{-x}}\leq \mathbb{P}(\sum X_i \leq 1)$$ and therefore $$\lim \frac{1}{n}\log(\frac{\mathbb{E}(e^{-x \sum_i X_i})}{e^{-x}})\leq \lim \frac{1}{n}\log(\mathbb{P}(\sum X_i \leq 1))$$

which is true for any $\epsilon>0$. This is the end of the proof that the bound is tight

$\endgroup$
  • $\begingroup$ Thanks, this is a very clear explanation of the method and how to apply it. $\endgroup$ – Mikhail Tikhomirov Sep 14 '17 at 17:59
  • $\begingroup$ Nice explanation indeed (I fixed some typos). Rankin bound occurs in the context of analytic number theory. It is a technique to bound arithmetic sums via similar looking Dirichlet series. $\endgroup$ – GH from MO Sep 14 '17 at 21:26
  • $\begingroup$ The last inequality in the equation right above the words "And to conclude" $\endgroup$ – karpasi Sep 15 '17 at 21:11
  • $\begingroup$ Sorry, comment cut off. The right most inequality in the equation right above the words "And to conclude" seems wrong. after cancelling out some termsseems like the L.H.S. Gives you $\mathbb{E}(e^{-x\sum X_i}|\sum X_i \leq 1)$, while the right hand is just $e^{-x}$. $\endgroup$ – karpasi Sep 15 '17 at 21:19
12
$\begingroup$

Let $R > 1$ and $\lambda \in \mathbb{R}$ be such that $$ \int_{1}^R \mathrm{tanh}(\frac{\lambda x}{2}) \frac{d x}{x} = \log R -2. $$ Then standard techniques in large deviation theory yield $$ \frac{1}{n} \log | \{ I \subseteq [n R^{-1},n] | \sum_{i \in I} \frac{1}{i} \leq 1 \} | \longrightarrow \int_{1}^R \phi(\lambda x)\frac{d x}{x^2} $$ where $\phi(u) = \log2 +\log \cosh (\frac{u}{2}) - \frac{u}{2} = \log(1 + e^{-u})$. For $R = e^2$ one has $\lambda =0$ and the limit is $(1 - e^{-2})\log 2$ : this recovers Lucia's first result.

Moreover, letting $R$ tend to infinity, then $\lambda$ tends to Lucia's constant $\alpha$, and the limit integral matches Lucia's upper bound. In particular Lucia's "second guess" was correct.

EDIT: Some details about the said "standard techniques". Let $(X_i)_i$ be independent Bernoulli random variable ($= \pm 1$ with probability $1/2$), and let $(t_i)_{i=1}^n$ be positive real numbers lying in a fixed interval $(-R,R)$. We are going to study the probability that $S = \sum_{i=1}^n t_i X_i$ is $\geq c$, for some $c \in \mathbb{R}$. Let $\lambda \in \mathbb{R}$ be such that $$ \frac{1}{n} \sum_{i=1}^n t_i \tanh(\lambda t_i) = c. $$ This amounts to say that $E[\frac{1}{n} S e^{\lambda S}] = c E[e^{\lambda S}]$. Such a $\lambda$ exists as soon as $|c| < \frac{1}{n} \sum_{i=1}^n t_i$. One checks that $$ E[(\frac{1}{n} S)^2 e^{\lambda S}]E[e^{\lambda S}]^{-1} = c^2 + \frac{1}{n^2} \sum_{i=1}^n t_i^2(1- \tanh(\lambda t_i)^2) $$ so that the variance of $\frac{1}{n} S$ w.r.t. the measure weighted by $e^{\lambda S} E[e^{\lambda S}]^{-1}$, is at most $R^2 n^{-1}$. In particular $$ E[ \mathbb{1}_{\frac{1}{n} S \in [c,c+\epsilon]} e^{\lambda S}] E[e^{\lambda S}]^{-1} = \frac{1}{2} + O(R^2 \epsilon^{-2} n^{-1}). $$ Thus $$ P( S \geq nc) \geq e^{-n \lambda (c+\epsilon)}E[ \mathbb{1}_{\frac{1}{n} S \in [c,c+\epsilon]} e^{\lambda S}] = e^{-n \lambda (c+\epsilon)} E[e^{\lambda S}] \left( \frac{1}{2} + O(R^2 \epsilon^{-2} n^{-1}) \right) $$ On the other hand $$ P( S \geq nc) \leq e^{-n \lambda c} E[e^{\lambda S}] $$ so that $$ \frac{1}{n} \log P( S \geq nc) = - \lambda c + \frac{1}{n} \log E[e^{\lambda S}] + o_{R}(1) $$ For the application above, just use $t_i = \frac{n}{2i}$ (indexed by $i$ between $n R^{-1}$ and $n$) and $c = \frac{1}{2} \sum_{n R^{-1} < j \leq n} \frac{1}{j} - 1$.

$\endgroup$
  • $\begingroup$ Impressive! Am I correct in understanding that this method can only provide lower bounds? $\endgroup$ – Mikhail Tikhomirov Sep 14 '17 at 16:07
  • 2
    $\begingroup$ The upper bound for fixed $R$ and for $R = + \infty$ are obtained by the same method (Chernoff bound). $\endgroup$ – js21 Sep 14 '17 at 16:24
6
$\begingroup$

I think I can do slightly better. Let's look at the following sets:

$S_1=\{A\subseteq \{\frac{e^2}{n},\dots,\frac{1}{n}\}|\sum_{x\in A}x\leq 0.9\}$.

$S_2=\{B\subseteq \{\frac{2e^2}{n},\dots,\frac{e^2}{n}\}|\sum_{x\in B}x \leq 0.1\}$.

Then obviously for any $A \in S_1, B \in S_2$, $A\cup B$ has a sum of less than one, so we have at least $|S_1|\cdot|S_2|$ sets with the desired property.

Let's try to lower bound $|S_1|$ and $|S_2|$. as for $|S_2|$, any subset of $\{\frac{2e^2}{n},\dots,\frac{e^2}{n}\}$ of size at most $\frac{0.1n}{2e^2}$ must be in $S_2$. the number of such sets is roughly $2^{H(0.1)/2e^2}=2^{0.03...}$.

Let's try to lower bound $|S_1|$. The number of subsets of $\{\frac{e^2}{n},\dots,\frac{1}{n}\}$ of size at most $0.45n(1-\frac{1}{e^2})$ is about $2^{H(0.45)(1-\frac{1}{e^2})}=2^{0.857...}$. For a set of such size the sum of its elements typically would be around $2\cdot0.45=0.9$. So the size of $|S_1|$ would also be $2^{0.8577}$. Multiplying $|S_1|\cdot|S_2|\geq 2^{0.887}$.

$\endgroup$
  • $\begingroup$ I don't exactly see how $S_1$ and $S_2$ are subsets of the original set. Could you please clarifiy your answer by adding rounding when (and if) intended, or providing additional explanations? $\endgroup$ – Mikhail Tikhomirov Sep 14 '17 at 13:15
  • $\begingroup$ You're right, I take $\frac{1}{\lceil n/e^2 \rceil}$, $\frac{1}{\lceil n/2e^2 \rceil} $ etc. I assume that $n$ is large here. $\endgroup$ – karpasi Sep 14 '17 at 13:22
  • 2
    $\begingroup$ Thank you, that's what I thought. I would still suggest adding this clarification to the answer. $\endgroup$ – Mikhail Tikhomirov Sep 14 '17 at 13:24

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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