Testing equivalence of parameters algorithmically

In Uncategorized on May 9, 2011 by nessgrh

In the previous post we reduced the problem of finding an expression of a Hypergeometric function to creating a suitably large “knowledge base” of suitable origins, and to find, given a suitable set of parameters $a_p, b_q$ an origin $a_p^0, b_q^0$. This post is concerned with the latter problem.

Let us re-state the definitions. We are given two vectors of complex numbers $a_p, b_q$. These parameters are called suitable if $a_i - b_j \in \mathbb{Z}$ implies that $a_i < b_j$. We assume $a_p, b_q$ are suitable, and also that $a_i \ne 0$, $b_j > 0$ for all $i, j$. All our origins also satisfy the same conditions. To every such set of parameters $a_p, b_q$ we associate three invariants:

• For $r \in [0, 1)$, the number $\alpha_r$ of $a_i \equiv r \pmod{1}$, and similarly the number $\beta_r$ of $b_j \equiv r \pmod{1}$.
• The number $\gamma$ of $a_i < 0$.

We then know that $a_p, b_q$ are equivalent to (reachable from) $a_p^0, b_q^0$ if and only if these invariants all agree.

Strictly Numerical Parameters

If all of the $a_i, b_j, a_i^0, b_j^0$ are concretely given, then this leads to an easy efficient algorithm. To every $r \in [0, 1)$ we can associate a tuple $A_r = (r, \alpha_r)$ and similarly a tuple $B_r = (r, \beta_r)$. Given parameters $a_p, b_q$ there exist finitely many $r_1 < r_2 < \dots$ and $s_1 < s_2 < \dots$ such that $\alpha_r > 0$ if and only if $r = r_k$ for some $k$, and similarly $\beta_r > 0$ if and only if $r = s_k$ for some $k$. We can thus pack all invariants of $a_p, b_q$ into a single tuple: $C(a_p, b_q) = (\gamma, A_{r_1}, A_{r_2}, \dots, B_{s_1}, B_{s_2}, \dots)$

Thus from our knowledge base we simply assemble a python dictionary that is indexed by the invariant $C$. In this way strictly numerical parameters can be settled very quickly and easily.

Parametric Hypergeometric Formulae

In particular for low orders, there are often parametric formulae for Hypergeometric functions, like this:

• $2{}_2F_1\left({-a, \frac{1}{2}-a} \atop \frac{1}{2} \middle| z\right) = (1 + \sqrt{z})^{2a} + (1-\sqrt{z})^{2a}$
• ${}_2F_3 \left({(\mu + \nu + 1)/2, (\mu + \nu + 2)/2} \atop {\mu + 1, \nu + 1, \mu + \nu + 1} \middle| -z^2 \right) = (2/z)^{\mu + \nu} \Gamma(\mu + 1) \Gamma(\nu + 1) J_\mu(z) J_\nu(z)$

Clearly we want to support these kinds of formulae. This seems much harder, though. Part of the difficulty stems from the fact that $\mathbb{Q}/\mathbb{Z}$ is not even a ring, and part of the difficulty stems from the fact that the Hypergeometric function is symmetric in the numerator parameters and in the denominator parameters. The following strategy is the best I could come up with: Given $a_p^0, b_q^0$ (where the $a_p^0, b_q^0$ are parametric formulae) we call a choice of numbers for the free variables an instantiation of the parametric formula. So for example $(1, \frac{3}{2})$ would be an instantiation of $(-a, \frac{1}{2}-a)$ (here $a = -1$). Now given $a_p, b_q$ , for every $(\sigma, \tau) \in S_{p} \times S_{q}$ (where $S_{p}$ denotes the symmetric group acting on  $p$ elements), we will try to find all inequivalent instantiations of $a_p^0, b_q^0$ that satisfy

• $a_{\pi i} \equiv a_i^0 \pmod{1}$ for all $i$,
• $b_{\tau j} \equiv b_j^0 \pmod{1}$ for all $j$.

We then instantiate all of these formulae, and run the algorithm for numerical parameters on the instantiations.

It remains to find a way to solve the above system of equations. Here we make additional assumptions. First of all we will assume all formulae are linear in the free parameters. The formulae found in tables are all of this form. Moreover, they have the property that for every free parameter $\mu$ there exists at least one entry in the vector $a_p$ (or $b_q$) containing $\mu$ as the only free symbol. We will use this entry to make an initial guess of the value of $\mu$, and then see what other values we should try. Thus to find the values of $\mu$ to try, do the following:

• Find the least common multiple $l$ of all denominators of coefficients of $\mu$ appearing in the equations.
• Of all entries that isolate $\mu$, find the one in which $\mu$ appears with largest denominator, say $m$.
• The right-hand side of the equation corresponding to that entry determines $\mu$ up to multiples of $m$. Pick an initial choice $\mu_0$.
• Let $r = \frac{l}{m}$. Try also $\mu_0 + m$, $\mu_0 + 2m$, and so on, up to $\mu_0 + (r-1)m$.

I think this should yield all possible solutions (and a lot of spurious ones). We then run these steps for all free parameters, and try all combinations of all possible solutions, and all permutations. Evidently this leads to combinatorial explosion, but it is important to keep in mind that the formulae we will be working with have $\le 3$ free parameters and very small denominators. Efficient code will still be important.

Finding Expressions for Hypergeometric Functions with Parameters

This is a different notion from the above: what if we want to find a formula for a Hypergeometric function where the $a_p, b_q$ themselves contain free symbols? This can happen when trying to evaluate general integrals (involving say the general order $\nu$ Bessel function), or when computing transforms (e.g. the Laplace transform). Clearly none of the “concrete” formulae are of help here. So we can only try to find an instantiation of some parametric Hypergeometric formula from which we can reach the function we are interested in in a finite number of steps independent of the free symbols. Clearly there are no huge tricks we can play here. We will just assume that everything that is not obviously congruent mod 1 is “generically incongruent” and return formulae that are valid for almost all values of the free parameters. With this in mind, running the above algorithm should also work in the case of free symbols.

5 Responses to “Testing equivalence of parameters algorithmically”

1. In the first part, I only count two invariants.

2. It seems like you could do it even if each index has more than one free variable just by using some linear algebra.

3. I counted alpha_r, beta_r and gamma as three invariants.

As for doing linear algebra, I feel slightly shaky doing this (since Q/Z is not a ring, so we have to keep track of moduli etc), but yes it could be done. The point is that I don’t think we need it, and I don’t want to do more complicated than necessary (initially).

Of course if you can show me a clean linear algebra way to solve the entire problem then I would like that much more than my algorithm. I just couldn’t come up with one (again I’m blaming this in Q/Z not being a ring, but maybe I just don’t see it).

4. The last part sounds like a difficult problem in general. It’s like the difference between integrating $x^ne^x$ when $n$ is given (like say it’s 3), and integrating $x^ne^x$ when $n$ is symbolic and only given to be a positive integer. The Risch Algorithm can handle the first case pretty easily. But to do the second case would require being able to manipulate polynomials with symbolic exponents. However, if you run through the algorithm by hand, you will be able to derive a general expression for $\int{x^ne^x\,dx}$. But the answer will contain things like factorials and summations, and it isn’t something that you can produce just by running it through the program.

And for assuming that things are “generically incongruent,” we do similar things in CAS all the time. It’s like assuming that $a \neq 0$ when solving $ax=1$. A more advanced example is in the Risch Algorithm, where we have to assume that symbolic constants are not rational multiples of each other. For example, when it says that $\int{e^{ax^2}e^{bx^2}\,dx}$ is nonelementary, it is actually correct for all $a$ and $b$ except for $a = -b$. So my point is that I think that that’s a perfectly valid assumption to make.

• It looks like I screwed up the LaTeX, which isn’t surprising due to WordPress’s lack of a preview function. Could you fix it for me?