Rate of growth of an explicit integral

Question

Let $$J_1=\int_0^1\frac{1}{\sqrt{1-t_2}}dt_2,$$ $$J_2=\int_0^1 \int_0^{t_2}\frac{1}{\sqrt{1-t_2}}(\frac{1}{\sqrt{1-t_3}}+\frac{1}{\sqrt{t_2-t_3}})dt_3dt_2,$$ $J_3=\int_0^1 \int_0^{t_2}\int_0^{t_3}\frac{1}{\sqrt{1-t_2}}(\frac{1}{\sqrt{1-t_3}}+\frac{1}{\sqrt{t_2-t_3}})(\frac{1}{\sqrt{1-t_4}}+\frac{1}{\sqrt{t_2-t_4}}+\frac{1}{\sqrt{t_3-t_4}})dt_4t_3t_2,$ and so on.

Is it true that $$J_N\leq C^N\quad \text{for some }C\;?$$

Mathematica and Maple both tells me that $J_1=2$, $J_2=2+\pi$ and $J_3=4+\frac{10\pi}{3}$, but they fail to compute $J_4$. Any help will be appreciated.

---

ps: The largest of the $N!$ terms in $J_N$ is exactly $$\int_0^1 \int_0^{t_2}\cdots\int_0^{t_N}\prod_{i=1}^N\frac{1}{\sqrt{t_i-t_{i+1}}}dt_{N+1}\cdots dt_3dt_2=\frac{\pi^{N/2}}{\Gamma(\frac{N+2}{2})}$$ which is too large, while the smallest term is $$\int_0^1 \int_0^{t_2}\cdots\int_0^{t_N}\prod_{i=1}^N\frac{1}{\sqrt{1-t_{i+1}}}dt_{N+1}\cdots dt_3dt_2=\frac{2^N}{N!}$$

Answer 1

The growth rate is exponential. Specifically, I will prove the bound $J_n \leq \frac{(n+1)^{n} 2^n}{(n+1)!}$, which grows like $(2e)^n$. I can also show that $J_n \geq 2^n$. I would guess that neither of these are the true rate of growth.

I'll also give an explicit recursion for the $J_n$, which makes it clear that they are all in $\mathbb{Q}[\pi]$ and should make it easy to compute them recursively.

It is convenient to define $J_n(b)$ to be $J_n$ with every upper bound $1$ replaced by $b$. For example, $$J_2(b) = \int_{t_2=0}^b d t_2 \int_{t_3=0}^{t_2} d t_3 \frac{1}{\sqrt{b-t_2}} \left( \frac{1}{\sqrt{b-t_3}} + \frac{1}{\sqrt{t_2-t_3}} \right)$$ By homogeneity, $J_n(b) = J_n \cdot b^{n/2}$. We set $J_0(b)=1$.

Here is the recursion in the form which is easiest to prove: $$J_n(b) = \sum_{k\geq 1} \frac{1}{k!} \sum_{\begin{matrix} n_1+n_2 + \cdots + n_k = n \\ n_1, n_2, \ldots, n_k >0 \end{matrix}} \prod_{i=1}^k \int_{c_i=0}^b \frac{J_{n_1-1}(c_i) d c_i}{\sqrt{b-c_i}}$$

Sketch of proof of recursion: The left hand side is a sum of $n!$ terms which are naturally indexed by functions $f: \{ 2,3,\ldots, n+1 \} \to \{1,2,\ldots, n \}$ obeying $f(i) \lt i$. The term corresponding to $f$ has integrand $1/\prod \sqrt{t_{f(i)} - t_i}$, where $t_1=b$.

Group together those summands for which $f^{-1}(1)$ has size $k$; let $(u_1, u_2, \ldots, u_k) = f^{-1}(1)$. For any $x \in \{2,3, \ldots, n \}$, there is precisely one $u_i$ such that $u_i \in \{ x, f(x), f(f(x)), f^3(x), \ldots \}$ Say that "$x$ passes through $u_i$". Let $n_i$ be the number of $x$ which pass through $u_i$. We group together all terms on the left with the same unordered list of multiplicities $(n_1, n_2, \ldots, n_k)$. On the right, group together all terms which differ only by permuting $(n_1, n_2, \ldots, n_k)$. I claim that the corresponding sums on the two sides match up.

An example is probably clearer than a proof here. Take $n=3$ and look at the partition $3=2+1$. On the left hand side, we have terms accounting for $(f(2), f(3), f(4))$ equal to: $(1, 1, 3)$, $(1,1,2)$ and $(1,2,1)$. On the right hand side, we have $2$ copies of $$\frac{1}{2!} \int_{c_1=0}^b \int_{c_2=0}^b \int_{t=0}^{c_1} \frac{d c_1 dc_2 dt}{\sqrt{b-c_1} \sqrt{b-c_2} \sqrt{c_1-t}}$$ The two copies cancel the $1/2!$. We are integrating over the region $0 \leq t \leq c_1$, $0 \leq c_2$. There are three possible orderings for the integrands: $0 \leq c_2 \leq t \leq c_1$, $0 \leq t \leq c_2 \leq c_1$ and $0 \leq t \leq c_1 \leq c_2$, and these correspond to the three functions $f$ above.

The confusing thing in writing out a general proof is noticing that the $1/k!$ and the number of orderings of the partition $n_1+n_2+ \cdots + n_k$ exactly cancel to eliminate any double counting. Since you tagged this with "feynmann-integrals", I assume you are used to the way these sort of symmetry factors work. $\square$

Simplifying the recursion We first plug in $J_m(b) = J_m \cdot b^{m/2}$ to obtain $$J_n = \sum_{k\geq 1} \frac{1}{k!} \sum_{\begin{matrix} n_1+n_2 + \cdots + n_k = n \\ n_1, n_2, \ldots, n_k >0 \end{matrix}} \prod_{i=1}^k J_{n_1-1} \int_{c_i=0}^1 \frac{ d c_i \ c_i^{(n_i-1)/2}}{\sqrt{b-c_i}}$$

The integrals are now simple one dimensional integrals and can be evaluated: $$J_n = \sum_{k\geq 1} \frac{1}{k!} \sum_{\begin{matrix} n_1+n_2 + \cdots + n_k = n \\ n_1, n_2, \ldots, n_k >0 \end{matrix}} \prod_{i=1}^k \left( J_{n_1-1} \cdot \frac{\sqrt{\pi}\ \Gamma((n_i+1)/2)}{\Gamma((n_i+2)/2)} \right)$$ Note that $\left( \frac{\sqrt{\pi}\ \Gamma((n_i+1)/2)}{\Gamma((n_i+2)/2)} \right)$ is rational if $n_i$ is odd and is a rational multiple of $\pi$ if $n_i$ is even, so this shows that all your polynomials are polynomials in $\pi$. (I am feeling nicely superior to Mathematica now. )

Upper bounds We have $ \frac{\sqrt{\pi}\ \Gamma((n_i+1)/2)}{\Gamma((n_i+2)/2)} \leq 2$. So $J_n$ is bounded by $K_n$, where $K_n$ is defined by the recursion $$K_n = \sum_{k\geq 1} \frac{1}{k!} \sum_{\begin{matrix} n_1+n_2 + \cdots + n_k = n \\ n_1, n_2, \ldots, n_k >0 \end{matrix}} \prod_{i=1}^k \left( 2 \cdot K_{n_1-1} \right)$$ Define the generating function $g(x) = \sum_{n=0}^{\infty} K_n x^n$. Then this shows $$g(x) = \exp(2 x g(x))$$

We thus see that $g(x) = -W(-2x)/(2x)$ where $W$ is the Lambert $W$ function and so $$K_n = \frac{(n+1)^{n} 2^n}{(n+1)!}$$ as promised.

Lower bound We can use a similar trick to get a lower bound. Note that $\frac{\sqrt{\pi} \Gamma((n+1)/2)}{\Gamma((n+2)/2)} \geq \frac{2}{n}$. So $J_n \geq L_n$ where $L$ is defined recursively by $L_0=1$ and $$L_n = \sum_{k\geq 1} \frac{1}{k!} \sum_{\begin{matrix} n_1+n_2 + \cdots + n_k = n \\ n_1, n_2, \ldots, n_k >0 \end{matrix}} \prod_{i=1}^k \left( \frac{2}{n} L_{n_1-1} \right)$$

Putting $L(x) = \sum_{n \geq 0} L_n x^n$, we see that $$L(x) = \exp\left( 2 \int_{t=0}^x L(t) dt \right).$$ This integral equation has the unique solution $L(x) = 1/(1-2x)$, so $L_n = 2^n$, as promised.

Answer 2

David's approach is, indeed, superb. Here is an alternative proof with more analytic flavor. It gives a worse constant as presented here (I made next to no attempt to optimize it), but it shows a bit more and can also teach you a couple of useful techniques.

First, let's clear the ground a bit. The problem is equivalent to estimating the integral $$ \idotsint\limits_S \prod_{n=1}^N\left(\sum_{k=1}^n\frac{1}{\sqrt{x_{n-k+1}+\dots+x_n}}\right)dx_1\dots dx_N $$ where $S$ is the standard simplex $x_j\ge 0,\sum_j x_j\le 1$. I suspect that this is what you started with because your notation strongly suggests that your $1$ was actually $t_1$ initially, so I'll not dwell on this reformulation now and will go straight to the point.

The simplex is not a very nice body for integration, but, if we do not mind losing a factor of $4^N$, we can replace it by the cube $Q_N=[0,1/N]^N$ ($S$ can be covered by about $4^N$ cubes $\frac 1N(k_1,\dots k_N)+Q_N$ with $k_j\in\mathbb Z_+$, $\sum_j k_j\le N$. Clearly, the cube with $k_1=\dots=k_N=0$ gives the largest contribution. It is then natural to make the change of variable $x_j=y_j/N$ that makes the domain of integration the standard unit cube. The problem becomes to show that
$$ \idotsint\limits_Q \prod_{n=1}^N\left(\sum_{k=1}^n\frac{1}{\sqrt{y_{n-k+1}+\dots+y_n}}\right)dy_1\dots dy_N\le C^N N^{N/2} $$

Next, all those long sums under the square root are, probably, behaving essentially like $\sqrt k$ due to the law of large numbers, with only severe deviations possible for small $k$. Thus, it looks like we should be able to replace the sum $$ \sum_{k=1}^n\frac{1}{\sqrt{y_{n-k+1}+\dots+y_n}} $$ by $$ \left(\sum_{k=1}^n\frac 1{\sqrt k}\right)\max_{1\le k\le n} \sqrt{\frac k{ y_{n-k+1}+\dots+y_n }}\approx 2\sqrt k \max_{1\le k\le n}\sqrt{\frac k{ y_{n-k+1}+\dots+y_n }}. $$ The factors $2\sqrt k$ multiply to just what we need. Thus, all that remains is to show that $$ \idotsint\limits_Q \prod_{n=1}^N\max_{1\le k\le n}\sqrt{\frac k{ y_{n-k+1}+\dots+y_n }} dy_1\dots dy_N\le C^N $$ If there were no maximum in $k$, just the product $\prod_{n=1}^N\sqrt{1/y_n}$, that would be a triviality. Moreover, we would have a lot of leeway in the possibility to replace the power $1/2$ by any other power less than $1$. We are going to use this leeway now and show that for every $p>1$, we have a pointwise estimate $$ \prod_{n=1}^N\max_{1\le k\le n}{\frac k{ y_{n-k+1}+\dots+y_n }}\le C(p)^N \left[\prod_{n=1}^N\frac{1}{y_n}\right]^p $$ This looks like the classical Hardy-Littlewood maximal function inequality in disguise, and, indeed, it is, though the maximal function one has to use here is the $\delta$-percentile one, which is rarely mentioned in the textbooks until you start dealing with the BMO spaces, so I'll remind the corresponding routines here.

Denote $z_n=\log(1/y_n)\ge 0$. Fix a small $\delta>0$. For each $n$, consider all intervals $I\subset[1,N]$ of integers containing $n$. Let $Z(I)$ be the least number such that at least $\delta|I|$ integers $m\in I$ satisfy $z_m\le Z(I)$ (we are really looking just for the "$\delta$-percentile" in the distribution of values on $I$, but due to the discrete setting instead of the continuous one, we have to handle things in a somewhat clumsy way). Put $Z_n=\max_{I:n\in I}Z(I)$.

Note now that $\frac k{ y_{n-k+1}+\dots+y_n }\le \delta^{-1}e^{Z_n}$ for every $k$, so the story will end if we demonstrate that our maximal operator $z\mapsto Z$ acts in $\ell^1$ with the norm at most $p$.

As usual, we play with the covering lemmas. Alas, Vitali, which is taught in every measure theory course, is not good enough for us because of the length tripling, so we'll use Besicovitch instead. Fortunately, in dimension 1, it is a piece of cake and reduces to the observation that is three intervals on the line contain a common point, then one of them is contained in the union of two others. Thus, we get the following

Lemma: From any finite collection of intervals on the line, one can choose a subcollection with the same union so that it covers no point more than twice.

(just remove the redundant intervals one by one using the observation above)

Now take any $t>0$ and consider the set $E=\{n:Z_n>t\}$. It is covered by intervals $I$ with $Z(I)>t$. Choosing a Besicovitch subcollection, we can assume that no point is covered more than twice. Let $F=\cup I$. Clearly, $|E|\le |F|$. On the other hand, the number of all indices $n\in F$ with $z_n\le t$ is at most $\delta\sum_I |I|\le 2\delta|F|$. Thus, the cardinality of the set $e=\{n:z_n>t\}$ is at least $(1-2\delta)|F|$. If $1-2\delta>p^{-1}$, we get $|E|\le p|e|$ for all $t$. Integrating this distributional inequality, we conclude that $$ \Vert Z\Vert_{\ell^1}\le p\Vert z\Vert_{\ell^1} $$ finishing the story.

As I said, this approach gives you a cruder bound, but it can often be used even when no nice algebraic identities are anywhere in sight.

I also could not help commenting on David's remark

so this shows that all your polynomials are polynomials in $\pi$. (I am feeling nicely superior to Mathematica now. )

IMHO, Mathematica never works when you really need it and has a strong tendency to irreversibly replace the gray cells in your brain when you don't really need it. I usually lament a lot about its complete impotence when one needs to determine whether some oscillatory integral is positive or negative, but its defendants always respond that numeric integration is not a purely algebraic problem. To see a human (albeit one with math. abilities well above average) beating it in its own field (exact symbolic computation of definite integrals involving simple radicals) gives me enormous satisfaction and some hope that not all is lost yet. :)

Answer 3

I got an alternative approach to prove the upper bound $J_n \leq C^n$, based on Fedja's idea of covering simplexes by cubes, and on David's description of $J_n$ using the functions $f$.

Using a change of variable, we convert all the $n!$ integrands in $J_n$ to be the same, namely $1/\sqrt{x_1x_2\cdots x_n}$. Now the integrands are $n!$ polytopes {$P_i:\;i=1,\cdots,n!$} which has a one to one correspondence to the collection of matrices {$M_f: f$} where $f:\{ 2,3,\ldots, n+1 \} \to \{1,2,\ldots, n \}$ obeys $f(i) < i$.

We now describe the correspondence. Given such a function $f$, we create an upper triangular $n\times n$ matrices matrix $M_f$ as follows: All entries of $M_f$ is either 0 or 1, and on the $j-$th column, an entry $M(i,j)$ is 1 if and only if $f(j-1) \leq i\leq j$.

For example, when $n=3$ and $(f(2),f(3),f(4))=(1,2,1)$, then the $M_f=$ $\begin{matrix} 1 0 1, \\ 0 1 1,\\ 0 0 1 \end{matrix}$

(These are the 3 rows of $M$ in the correct order, the output does not show the matrix in this environment and I don't know why)

These row vectors of $M_f$, together with the origin, gives rise to the polytope in $\{P_i:\;i=1,\cdots,6\}$.

The job now is to show that these polytopes patch up around the origin at most $C^n$ times. An idea is to project the vertices (except the origin) of each polytope onto a sphere to form a spherical polygon, then check how may times these polygons patch up on the sphere. This maybe as hard as the original problem (high dimensional polytopes are hard to deal with) but the symmetry of the integrand .may simply the counting job. It'd be interesting to know if such an approach works.