
Re: 136 theorems on 29 pages
Posted:
Oct 1, 2012 4:31 PM


Waldek Hebisch schrieb: > > The existence of formulas is not in doubt  it is part of proof > of correctness of Hermite reduction. > > FYI, Hermite reduction starts with an ansatz: > > A*P_1^a_1*...*P_m^a_m = (B*P_1^(a_1+1)*...*P_m^(a_m+1))' + > C*P_1^(a_1+1)*...*P_k^(a_k+1)P_{k+1}^a_{k+1}*...*P_m^a_m > > where P_i are relatively prime polynomials and A, B and C > are polynomials. Denoting by n_1 sum of degrees of P_i for i in 1..k > and by n sum of degrees of P_i for i in 1..m we require > A be polynomial of degree at most n1, C be at most of degree n  2, > while B at most of degree n_1  1. > > This leads to equation: > > A = B*S + B'*U + C*V > > where U=P_1*...*P_m, S = ((a_1+1)P_1'/P_1 + ... + (a_m + 1)P_m'/P_m)*U, > V = P_1*...*P_k. Writing W = P_{k+1}*...*P_m, D = B'*W + C > we get > > A = B*S + D*V > > It is easy to see that as long as all (a_i + 1) for i=1,...,k are nonzero > S and V are relatively prime, so (by the extended euclidean algorithm) > there exist polynomials u and w such that > > A = u*S + w*V > > Moreover, when we requre u to be at most of degree n_1  1 = deg(V)  1 > the solution is unique, so B = u and D = w. Now C = w  B'*W and > it is easy to see that C satisfies requested degree bound. > > This covers increasing a_i. For decreasing them argument is a bit > longer but not much.
Thanks for writing this out. For one, it confirms the wisdom of the author not to bother about proofs. I haven't gone through every detail, but you seem to cover the case of rising exponents in the nondegenerate integrands of the paper fully (I expect the P_i must somewhere be required to be squarefree also). Your (and Hermite's) reference to the extended Euclidean algorithm replaces my reference to solving a system of linear equations. And via decomposition into linear factors and chaining of recurrence relations, the degenerate cases are covered as well.
Unless this must count as your own work, the author will need suitable, maybe original, references that cover the raising and lowering of exponents in this way. While a limitation to rational integrands would presumably be no problem, Hermite(*) has considered (for him without loss of generality) isolated powers only, as also seen in Hardy's account of 1916. The modern presentation in Bronstein's "Symbolic Integration Tutorial", on the other hand, is too specialized: Bronstein restricts the factor acted on to be that with the highest exponent, he somehow omits the other factors from the integrated term, and he doesn't analyze or discuss the numerator degrees. This is downright unsuitable.
(*) <http://www.numdam.org/item?id=NAM_1872_2_11__145_0>
> > My points are: > > 1) While argument is simple the solvability of resulting system > needs a proof.
Mathematicians would be and should be interested in a proof for general order. I am not so sure about applied mathematicians or theoretical physicists ... And engineers probably wouldn't and shouldn't.
> 2) The process is wellknown as Hermite redution. > 3) Since withing degree bounds solution is unique you must get > exactly the same formulas
At least for raising exponents, the nondegenerate formulae in the paper are just special cases of (a rather general formulation of the more or less wellknown process of) Hermite reduction for a generic given numerator that matches the transformed numerator in degree.
> 4) At conceptual level it does not matter if you present this as > rules or an algorithm: you perform exactly the same sequence > of tranformations, using the same formulas. On practical level > procedures are likely to solve systems of equations on the fly, > while the paper presents precomputed formulas (and I agree that > precomputed formulas are better if you insist on encoding > Hermite reduction using rules).
I would say, mathematically the recurrence formulae in the paper and Hermite reduction may be equivalent, or identical, or one a case of the other. Conceptually, I perceive a vast difference between the selfterminating reduction scheme as which the first is presented normally, and relations cast as rules  be they precomputed or produced on demand  which can be applied repeatedly to drive arbitrary exponents in an integrand up or down as desired (as long as no zero determinant is hit). It should be no accident that nobody refers to the integral equation set up for Hermite reduction as a recurrence relation.
> 5) Clearly Hermite reduction counts as prior art for the article.
I don't think the author will have a problem with this insight.
> > > > Agreed. But cases where this is absolutely crucial appear to be rare > > when problems relating to the physical world are addressed by > > integration. > > Avoiding unneeded algebraics is crucial if you want to do some > symbolic computations with the result  extra algebraics > can cause huge slowdown.
I consider factorizations leading to at most square roots within square roots acceptable; more complicated stuff should be handled as RootOf objects anyway (along with the rules for their algebra). But meaningful symbolic (nonnumerical, parametrized) roots where this is needed tend to be rare in science. Mathematical research differs perhaps.
Martin.

