Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given four polynomials in $x$, called $p(x), q(x), r(x), s(x)$, such that $$ \text{poly}(x) = \sum_{k=0}^N {c_k x^k},\qquad (c_k \in \mathbb{N}) \land (|c_k| \le N^2)$$

Is it possible to get an easy (which will be defined later) solution to $$\int {\frac {p(x) (q(x)^{1/2})} {r(x) (s(x)^{1/2})} dx}$$

We define an easy solution as a solution done in polynomial time with respect to $N$ (in other words, the time it takes to get a solution is a polynomial function of $N$) and either:

(1) We get a solution of the definite integral that has arbitrary limits of integration and is accurate to $N$ decimal places. The limits may be reals with an absolute value that doesn't exceed $N^2$.

(2) We get an exact solution to the indefinite integral.

My question is, can we find some way to get an easy solution, or prove that an easy solution is impossible/possible?

MOTIVATION

This question arises from this answer to this question.

I'm attempting to determine if this integral is a potential candidate for a one-way function. It could possibly be used as a new security measure, but that may be years and years away from actual use, if it ever happens.

share|improve this question

1 Answer 1

Suppose the integrand has a pole of order $k > 1$. Then the antiderivative has a pole there of order $k-1$. If the pole is in the interval of integration, presumably your algorithm should return "undefined" or "infinity". But you could run into difficulties if the pole is close to the interval. You'll need to be able to find the poles accurately, and also you'll need the endpoints accurately. If you are only given decimal approximations of an endpoint, there's no guarantee that any particular approximation will be accurate enough to decide which side of a pole it's on. Even if you have the endpoint with arbitrary accuracy (in the sense that you can ask for, and be given, the first $M$ decimal digits for any desired $M$), if that endpoint happens to be equal to the pole there's no way to detect that fact.

EDIT: On the other hand, suppose the integrand $f(x)$ and interval $[a,b]$ are fixed, and the integrand is analytic in a neighbourhood of $[a,b]$. By finding the roots of $r(z)$ and $s(z)$ you can find $\epsilon > 0$ so that $f(z)$ is analytic in $\{z\in {\mathbb C}: \text{dist}(z,[a,b]) < \epsilon\}$. Take integer $n > (b-a)/\epsilon$, and $x_j = a + j(b-a)/n$ for $j = 0,1,\ldots n$. You can calculate the Taylor series of $f(z)$ about each $x_j$ and use it for the integral from $x_j$ to $x_{j+1}$. If $k$ terms are used, you will get an error bounded by $C r^k$ for some computable $C$ and $r$ with $0 <r<1$. Note that to calculate $k$ coefficients will take time polynomial in $k$, using the binomial series: if $g(x) = g(x_0) + h(x-x_0)$, $g(x)^\alpha = \sum_{j=0}^\infty {\alpha \choose j} g(x_0)^{\alpha - j} h(x-x_0)^j$. So you can get $N$-digit accuracy in time polynomial in $N$.

share|improve this answer
    
Thanks for this. I just wanted to be fairly certain that this isn't a good candidate for a one-way function. I guess that it may be impossible to find a good one-way integral... –  Matt Groff Jul 28 '12 at 1:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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