4
$\begingroup$

I need to integrate $$ \int\limits_{[1,a]^n} \frac {\chi(\{ b \le x_1 \cdots x_n \le c \})} {( x_1 x_2 \cdots x_n)^k} \,dx_1 \cdots dx_n, $$ where $\chi(E)$ is the characteristic function of a set $E$. We have $a>1$ and $c>b>1$; furthermore $k\in\mathbb R$, but feel free to restrict it to either larger than $0$ or smaller than $0$ if that's easier; the case $k=0$ would also be of independent interest.

While this might look like homework, it's come up in a research context; I sincerely hope it is as easy as homework for someone, I've dug through various papers, but it seems tough. So I'm happy for any pointers!!

Thanks!

PS: I'm happy to give more context, but I'm not sure it'll add much.

Improve this question
$\endgroup$
11
  • 2
    $\begingroup$ How about changing variables to $z_{i}:=\ln x_{i}$ ? The restriction then converts to an integration over a simplex area ($\ln b \le \sum z_{i} \le \ln c$), which might be easier to handle. $\endgroup$
    – Johannes Trost
    Commented May 22, 2019 at 11:39
  • 1
    $\begingroup$ Good suggestion! That leads to a simpler expression $$ \iiint_0^{a'} \exp(k'(z_1+\ldots+z_n))*\begin{cases} 1 & b' \le z_1+\ldots+z_n \le c' \\ 0 & \text{otherwise,} \end{cases} $$ where $a'=\ln a$, $b'=\ln b$, $c'=\ln c$, and $k'=k+1$. It should suffice to solve this for $b'=0$, of course, as then we can just subtract two integrals off each other, and we can rescale to set $a'=1$. For $k'=0$, we appear to get a list of polynomials for various ranges of $c'$, with coefficients from [oeis.org/A188668]. Not a proof, just an observation. Thanks, that was already helpful! $\endgroup$
    – J Bausch
    Commented May 22, 2019 at 12:19
  • 1
    $\begingroup$ The problem statement now is missing the $dx_1 dx_2 \cdots dx_n$. And note, when you change variables, you need to switch to $dz_1 dz_2\cdots dz_n$. $\endgroup$
    – Gerald Edgar
    Commented May 22, 2019 at 12:51
  • 3
    $\begingroup$ I don't see much hope for a clean answer. Consider the simplest case, $k=0, n=2$. Then the integral we want is $f(c)-f(b)$ where $$f(c)=\int_1^a \max(1,\min(a,\frac cx))dx = \begin{cases} -c + c \log c + a \ \ \ \ \ \text{ if } 1 \le c \le a \\ c + c \log(a^2/c) - a \text{ if } a \le c \le a^2 \\ a^2 - a \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{ if } c \ge a^2\end{cases}$$ $\endgroup$
    – user44143
    Commented May 22, 2019 at 15:41
  • 3
    $\begingroup$ If you perform a Fourier expansion of the indicator function $1_{[b',c']}$ and use Fubini's theorem (which requires some preliminary smoothing of the indicator function to justify properly, but never mind that) you can convert the $n$-dimensional $z$-integral in the previous comment to a one-dimensional integral over the Fourier variable, which should be a suitable form for instance for working out asymptotics in various limiting regimes such as $n \to \infty$, if that is your application of interest. $\endgroup$
    – Terry Tao
    Commented May 22, 2019 at 18:41

2 Answers 2

Reset to default
6
$\begingroup$

UPDATE 2019-05-31. Formulae are corrected and SageMath code added.

Let us assume that $a$ is fixed, and define: $$ I_n^{k,l}(b,c) := \iiiint_{[1,a]^n} \frac {\chi(\{ b \le x_1 \cdots x_n \le c \})\log(x_1 x_2 \cdots x_n)^l} {( x_1 x_2 \cdots x_n)^k} \,dx_1 \cdots dx_n. $$ Hence, the integral in question equals $I_n^{k,0}(b,c)$.

We first consider the case $b\leq\frac{c}a$, while the other case is considered similarly.

We will need the following formula, which holds for all integer $l\geq 0$: $$\int \frac{\log(y)^l}{y^k}dy = \begin{cases} \frac{\log(y)^{l+1}}{l+1}, & \text{if }k=1;\\ -\sum_{i=0}^l \frac{l!}{i!(k-1)^{l+1-i}} \frac{\log(y)^i}{y^{k-1}} & \text{if }k\ne 1. \end{cases}$$

Making a substitution $x_n := \frac{t}{x_1\cdots x_{n-1}}$, we get $$I_n^{k,l}(b,c) = \int_1^a dx_1 \cdots \int_1^a dx_{n-1} \int_{x_1\cdots x_{n-1}}^{ax_1\cdots x_{n-1}} dt\frac{\log(t)^l\chi(b\leq t\leq c)}{t^k x_1\cdots x_{n-1}}.$$

If $k\ne 1$, depending on the value of $x_1\cdots x_{n-1}$ the last integral breaks into 4 cases:

  • If $x_1\cdots x_{n-1}\leq \frac{b}{a}$ or $x_1\cdots x_{n-1}\geq c$, then the integral over $t$ is zero.
  • If $\frac{b}{a} \leq x_1\cdots x_{n-1}\leq b$, then the integral over $t$ equals $$-\sum_{i=0}^l \frac{l!}{i!(k-1)^{l+1-i}} \frac{\log(ax_1\cdots x_{n-1})^i}{a^{k-1}(x_1\cdots x_{n-1})^k} + \sum_{i=0}^l \frac{l!}{i!(k-1)^{l+1-i}} \frac{\log(b)^i}{b^{k-1}x_1\cdots x_{n-1}}$$
  • If $b\leq x_1\cdots x_{n-1}\leq \frac{c}{a}$, then the integral over $t$ equals $$-\sum_{i=0}^l \frac{l!}{i!(k-1)^{l+1-i}} \frac{\log(ax_1\cdots x_{n-1})^i}{a^{k-1}(x_1\cdots x_{n-1})^k} + \sum_{i=0}^l \frac{l!}{i!(k-1)^{l+1-i}} \frac{\log(x_1\cdots x_{n-1})^i}{(x_1\cdots x_{n-1})^k}.$$
  • If $\frac{c}{a}\leq x_1\cdots x_{n-1}\leq c$, then the integral over $t$ equals $$-\sum_{i=0}^l \frac{l!}{i!(k-1)^{l+1-i}} \frac{\log(c)^i}{c^{k-1}x_1\cdots x_{n-1}} + \sum_{i=0}^l \frac{l!}{i!(k-1)^{l+1-i}} \frac{\log(x_1\cdots x_{n-1})^i}{(x_1\cdots x_{n-1})^k}$$

Hence, if $b\leq\frac{c}{a}$ and $k\neq 1$, we get a recurrence formula: $$I_n^{k,l}(b,c) = -\sum_{i=0}^l \frac{l!}{i!(k-1)^{l+1-i}} \left( \sum_{j=0}^i \binom{i}{j} \frac{\log(a)^{i-j}}{a^{k-1}} I_{n-1}^{k,j}(\frac{b}{a},\frac{c}{a}) - \frac{\log(b)^i}{b^{k-1}} I_{n-1}^{1,0}(\frac{b}{a},b) - I_{n-1}^{k,i}(b,c) + \frac{\log(c)^i}{c^{k-1}}I_{n-1}^{1,0}(\frac{c}{a},c) \right).$$ It can be easily verified that the same formula holds in the case $b\geq\frac{c}{a}$ as well. In fact, for the original problem, we don't need this formula in full generality, but rather its special case with $l=0$: $$I_n^{k,0}(b,c) = \frac{1}{1-k} \left( \frac{1}{a^{k-1}} I_{n-1}^{k,0}(\frac{b}{a},\frac{c}{a}) - \frac{1}{b^{k-1}} I_{n-1}^{1,0}(\frac{b}{a},b) - I_{n-1}^{k,0}(b,c) + \frac{1}{c^{k-1}}I_{n-1}^{1,0}(\frac{c}{a},c) \right).$$

Similarly, when $k=1$, we get the formula: $$I_n^{1,l}(b,c) = \frac{1}{l+1}\left(\sum_{j=0}^{l+1} \binom{l+1}{j} \log(a)^{l+1-j} I_{n-1}^{1,j}(\frac{b}{a},\frac{c}{a}) - \log(b)^{l+1} I_{n-1}^{1,0}(\frac{b}{a},b) - I_{n-1}^{1,l+1}(b,c) + \log(c)^{l+1} I_{n-1}^{1,0}(\frac{c}{a},c) \right).$$

These formulae allow to compute the integral $I_n^{k,l}(b,c)$ recursively. The recursion stops as soon as $n=1$, $c\leq 1$, or $b\leq 1$ and $c\geq a^n$ -- in all these cases the corresponding integral can be computed explicitly.

SageMath code implementing these formulae:

def II(n,k,l,a,b,c):
  if (c<=1) or (c<=b) or (b>=a^n):
    return 0

  if n==1:
    if k==1:
      return ( log(min(a,c))^(l+1) - log(max(1,b))^(l+1) ) / (l+1)
    return - sum( factorial(l)/factorial(i)/(k-1)^(l+1-i) * ( log(min(a,c))^i/min(a,c)^(k-1) - log(max(1,b))^i/max(1,b)^(k-1) ) for i in range(l+1) )

  if k==1:
    return ( sum( binomial(l+1,j)*log(a)^(l+1-j)*II(n-1,1,j,a,b/a,c/a) for j in range(l+2) ) - log(b)^(l+1)*II(n-1,1,0,a,b/a,b) - II(n-1,1,l+1,a,b,c) + log(c)^(l+1)*II(n-1,1,0,a,c/a,c) ) / (l+1)
  return - sum( factorial(l)/factorial(i)/(k-1)^(l+1-i) * ( sum( binomial(i,j)*log(a)^(i-j)/a^(k-1)*II(n-1,k,j,a,b/a,c/a) for j in range(i+1) ) - log(b)^i/b^(k-1)*II(n-1,1,0,a,b/a,b) - II(n-1,k,i,a,b,c) + log(c)^i/c^(k-1)*II(n-1,1,0,a,c/a,c) ) for i in range(l+1) )
Improve this answer
$\endgroup$
9
  • $\begingroup$ Do you have an estimate for the number of terms in this calculation? If the calculation of $I_n$ uses at least $4$ terms of $I_{n-1}$, and so it uses at least $4^n$ basic terms, then it'd be nicer to get something with polynomial growth. $\endgroup$
    – user44143
    Commented May 22, 2019 at 20:24
  • $\begingroup$ @MattF.: My estimate is that $I^{1,l}_n(b,c)$ has $O(n)$ terms and $I^{k,0}_n(b,c)$ has $O(n^2)$ terms. $\endgroup$
    – Max Alekseyev
    Commented May 23, 2019 at 15:36
  • $\begingroup$ Very useful answer, much appreciated. I'll try to implement this in MM and cross-check with the original expression. $\endgroup$
    – J Bausch
    Commented May 24, 2019 at 16:01
  • $\begingroup$ @MaxAlekseyev: I've just tried implementing it in MM, but there seems to be something amiss: for e.g. $a=20, b=1, c=40, n=3, l=0$ we have: $I_3^{k,0}(1,40)$ expands the rightmost term $I_{2}^{1,0}(2,\infty)$; the latter then includes a term that has $\log(\infty)I^{1,0}_1(\infty,\infty)$ in it. Am I missing a break condition? $\endgroup$
    – J Bausch
    Commented May 27, 2019 at 19:51
  • 1
    $\begingroup$ @JBausch: Good catch! There was an error in my formulae, now corrected. Essentially, we should use $\frac{b}{a}$ instead of $1$ in $I(1,\cdot)$ and $c$ instead of $\infty$ in $I(\cdot,\infty)$. This also addresses the issue with $\infty$ you pointed out earlier. $\endgroup$
    – Max Alekseyev
    Commented May 31, 2019 at 18:12
1
$\begingroup$

To expand on the excellent comments and answers provided here and following up on Terry Tao's proposition to take the Fourier expansion of the indicator function in the integral, I derived an alternative closed expression for the special case where $b=1$ and $k\neq 1$: using the notation for the integral as Max Alekseyev, we have $$ I_n^{k,0}(1,c) = \frac{(-1)^n}{k'^n} \sum_{j=0}^{\min\{n,\lfloor c'/a'\rfloor\}} \binom{n}{j} \left( \mathrm{e}^{a'k'j} - \mathrm{e}^{-c'k'}\sum_{l=0}^{n-1}\frac{(a'k'j-c'k')^l}{l!} \right), $$ where $k'=1-k$, $c'=\log c$, $a'=\log a$.

This is proven in lemma 10 of arxiv:1909.05023.

Thanks all!

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .