7
$\begingroup$

As part of a problem on algebraic number theory, I am faced with the following analysis/calculus exercise:

Show that the volume of the set $$E_n:=\Big\{ (x_1,\ldots,x_n)\in \mathbf{R}^n_{>0} :\prod_{i=1}^n\max(1,x_i)\leqslant d \Big\}$$ is equal to $$d\sum_{i=0}^{n-1} \binom{n-1}{i} \frac{(\log d)^i}{i!}.$$

My attempt at solving this problem was as follows. Clearly, $E_n\subset [0,d]^n$. The volume of $E_n$ equals the following integral (abbreviating $m$ for $\max$):

$$\int_0^d \int_0^{\frac{d}{m(1,x_1)}}\cdots \int_0^{\frac{d}{m(1,x_1)\cdots m(1,x_{n-2})}} \int_0^{\frac{d}{m(1,x_1)\cdots m(1,x_{n-1})}} 1\, dx_n\,dx_{n-1}\cdots dx_2\,dx_1,$$ which can be simplified into $$d\int_0^d \frac{1}{m(1,x_{1})} \int_0^{\frac{d}{m(1,x_1)}}\frac{1}{m(1,x_{2})}\cdots \int_0^{\frac{d}{m(1,x_1)\cdots m(1,x_{n-2})}} \frac{1}{m(1,x_{n-1})}\,dx_{n-1}\cdots dx_2\,dx_1.$$

I tried to prove the formula by induction. By splitting the middle integral, it evaluates to $1+\log d-\sum_{i=1}^{n-2}\log m(1,x_i)$. By linearity of the integral, we get $(1+\log d)E_{n-1}$ plus some other integral. However, this gets incredibly messy.

Is my approach correct? Is there any more clever way to attack this integral or an other method to prove this formula ? Is there maybe a probabilistic way of calculating its value ?

EDIT. In Theorem 6.5 of this article the integral is written as $\int_{y\in \mathbf{R}^n,\sum_i \max(0,y_i)\leq \delta} \exp \sum y_i\,dy$. Are my integral and this one equal ?

Any help is much appreciated.

(For the bounty: I would like to have a comprehensive, detailed answer.)

$\endgroup$
3
+50
$\begingroup$

Indeed the two representations are equivalent. Substituting $x_i = e^{y_i}$, we note that

$$ \prod_{i=1}^{n} \max\{1,x_i\} < d \quad\Leftrightarrow\quad \prod_{i=1}^{n} \max\{1,e^{y_i}\} < d \quad\Leftrightarrow\quad \sum_{i=1}^{n} \max\{0,y_i\} < \log d. $$

Also, since $\mathrm{d}x_i = e^{y_i} \, \mathrm{d} y_i$, we get

\begin{align*} \operatorname{Vol}(E_n) &= \int_{\mathbb{R}_{>0}^n} \mathbf{1}_{E_n} \, \mathrm{d}x_1\cdots\mathrm{d}x_n \\ &= \int_{\mathbb{R}^n} \mathbf{1}_{\{ \sum_{i=1}^{n} \max\{0,y_i\} < \log d\}} e^{y_1+\dots+y_n} \, \mathrm{d}y_1\cdots\mathrm{d}y_n \end{align*}

From now on, we will assume $d > 1$ for an obvious reason. Write $[n] = \{1,\dots,n\}$ and set

$$ F(I) = \int_{A_I} \mathbf{1}_{\{ \sum_{i=1}^{n} \max\{0,y_i\} < \log d\}} e^{y_1+\dots+y_n} \, \mathrm{d}y_1\cdots\mathrm{d}y_n, $$

where $A_I = \bigcap_{i \in I} \{y_i \geq 0\} \cap \bigcap_{i \notin I} \{y_i < 0\} $ is the set of points $(y_1, \dots, y_n)$ such that $y_i \geq 0$ if and only if $i \in I$. Writing $k = \left| I \right|$ for the size of the set $I$, it is easy to find that the value of $F(I)$ depends only on $k$. In particular, if $k \geq 1$, then

\begin{align*} F(I) = F([k]) &= \left( \int_{-\infty}^{0} e^{y} \, \mathrm{d}y \right)^{n-k} \left( \int_{[0,\infty)^k} \mathbf{1}_{\{ \sum_{i=1}^{k} y_i \leq \log d \}} e^{y_1 + \dots + y_k} \, \mathrm{d}y_1 \dots \mathrm{d}y_k. \right) \\ &= \int_{[0,\infty)^k} \mathbf{1}_{\{ \sum_{i=1}^{k} y_i \leq \log d \}} e^{y_1 + \dots + y_k} \, \mathrm{d}y_1 \dots \mathrm{d}y_k. \end{align*}

Substituting $(z_1, \dots, z_k) = (y_1, y_1+y_2, \dots, y_1+\dots+y_k)$, the region $[0, \infty)^k$ in $y$-domain transforms to $\{(z_1, \dots, z_k) : 0 < z_1 < z_2 < \dots < z_k \}$, and so,

\begin{align*} F([k]) &= \int_{0}^{\log d}\int_{0}^{z_{k}} \dots \int_{0}^{z_2} e^{z_k} \, \mathrm{d}z_1 \dots \mathrm{d}z_k \\ &= \int_{0}^{\log d} \frac{z_k^{k-1}}{(k-1)!} e^{z_k} \, \mathrm{d}z_k. \end{align*}

If in addition $k \geq 2$, then integration by parts shows that

\begin{align*} F([k]) &= \frac{d (\log d)^{k-1}}{(k-1)!} - F([k-1]). \end{align*}

Writing $[0] = \varnothing$ for convenience and noting that $F(\varnothing) = 1$, we find that this formula also extends to $ k = 1$. Therefore

\begin{align*} \operatorname{Vol}(E_n) &= \sum_{I \subseteq [n]} F(I) \\ &= \sum_{k=0}^{n} \binom{n}{k} F([k]) \\ &= \sum_{k=0}^{n} \left[ \binom{n-1}{k} + \binom{n-1}{k-1} \right] F([k]) \\ &= \sum_{k=0}^{n-1} \binom{n-1}{k} F([k]) + \sum_{k=0}^{n-1} \binom{n-1}{k} F([k+1]) \\ &= \sum_{k=0}^{n-1} \binom{n-1}{k} \frac{d (\log d)^{k}}{k!}. \end{align*}

$\endgroup$
2
  • $\begingroup$ Thank you for your wonderful answer! The idea of the substitution is very clever. :) There are some typos: (1) in your expression of $F([k])$, the upper bound should be $z_k$, (2) in the last equality of $\operatorname{Vol}(E_n)$, something goes wrong. $\endgroup$ – rae306 Dec 15 '20 at 12:55
  • 1
    $\begingroup$ @rae306, Glad that it was helpful, and thank you for pointing out the typos! $\endgroup$ – Sangchul Lee Dec 15 '20 at 12:57
1
$\begingroup$

Assume $d>1$ (otherwise the volume is $0$). Call the volume $V_n(d)$ so$$V_n(d)=\int_0^1V_{n-1}(d)\mathrm{d}x+\int_1^dV_{n-1}(d/x)\mathrm{d}x=V_{n-1}(d)+\int_1^dV_{n-1}(x)\frac{d}{y^2}\mathrm{d}y,$$using $y=\frac{d}{x}$. Since $V_1(d)=d=d\sum_{i=0}^0\binom{0}{i}\frac{\ln^id}{i!}$, $n=1$ works. Now we use induction: if $V_k(d)=d\sum_{i=0}^{k-1}\binom{k-1}{i}\frac{\ln^id}{i!}$ then$$V_{k+1}(d)=d\sum_{i=0}^{k-1}\binom{k-1}{i}\frac{\ln^id}{i!}+d\int_1^d\frac1y\sum_{i=0}^{k-1}\binom{k-1}{i}\frac{\ln^iy}{i!}\mathrm{d}y.$$With $u=\ln y$, the integral is easy:$$\begin{align}V_{k+1}(d)&=d\sum_{i=0}^{k-1}\binom{k-1}{i}\frac{\ln^id}{i!}+d\sum_{i=0}^{k-1}\binom{k-1}{i}\frac{\ln^{i+1}d}{(i+1)!}\\&=d\sum_{i=0}^{k-1}\binom{k-1}{i}\frac{\ln^id}{i!}+d\sum_{i=1}^k\binom{k-1}{i-1}\frac{\ln^id}{i!}\\&=d\sum_{i=0}^k\binom{k-1}{i}\frac{\ln^id}{i!}+d\sum_{i=0}^k\binom{k-1}{i-1}\frac{\ln^id}{i!},\end{align}$$where binomial coefficients are defined combinatorially, so $\binom{r}{-1}=\binom{r}{r+1}=0$. Hence$$V_{k+1}(d)=d\sum_{i=0}^k\left(\binom{k-1}{i}+\binom{k-1}{i-1}\right)\frac{\ln^id}{i!}=d\sum_{i=0}^k\binom{k}{i}\frac{\ln^id}{i!}.$$

$\endgroup$

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.