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.

$\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$ 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
    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$ 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
    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
    May 22, 2019 at 18:41

2 Answers 2

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) )
$\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
    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$ 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
    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
    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$ 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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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