PaperlayerView exact revision on arXiv

Source-linked AI summary

Parameterized Telescoping Proves Algebraic Independence of Sums

Carsten Schneider

arXiv:0808.2596v1cs.SCmath.COmath.NT

TL;DR

The paper addresses how the absence of creative or parameterized telescoping solutions can establish algebraic independence of sums. It develops ΠΣ∗-field and sequence-embedding machinery to make this criterion effective, showing transcendence for whole classes of sequences and clarifying recurrence minimality. The approach remains bounded by unresolved general embedding questions and technical pole-related conditions.

  • Problem

    Creative telescoping is commonly used to derive recurrences, but its failure and recurrence-order behavior require a theoretical explanation connected to algebraic independence of sums.

  • Method

    The paper combines parameterized telescoping with ΠΣ∗-field theory and difference-ring monomorphisms into sequence rings.

  • Results

    The criterion proves algebraic independence over the relevant base fields for sequences arising from sums, including the rational-sum setting.

  • Takeaways & Limitations

    For hypergeometric terms, Zeilberger’s algorithm can check transcendence; Sigma can check algebraic independence for indefinite nested sums and products.

  • Takeaways & Limitations

    It remains open whether every ΠΣ∗-field over K can be embedded in the ring of K-sequences, and some sum expressions may be undefined because of poles or an insufficient starting index.

Abstract

from arXiv · show

Usually creative telescoping is used to derive recurrences for sums. In this article we show that the non-existence of a creative telescoping solution, and more generally, of a parameterized telescoping solution, proves algebraic independence of certain types of sums. Combining this fact with summation-theory shows transcendence of whole classes of sums. Moreover, this result throws new light on the question why, e.g., Zeilberger's algorithm fails to find a recurrence with minimal order.

1. Introduction

The paper reframes parameterized telescoping as a route to algebraic independence: failure to find a telescoping relation yields transcendental extensions for the associated sums. Combined with summation theory, this provides criteria for transcendence and clarifies when creative telescoping may miss minimal-order recurrences.

  • Parameterized telescoping: Parameterized telescoping seeks constants c1, …, cd and g(k) satisfying g(k + 1) − g(k) = c1f1(k) + ··· + c_d f_d(k).Telescoping is the d = 1 case, while creative telescoping arises from shifts of a bivariate summand.
  • Parameterized telescoping: The framework applies Karr’s summation algorithms to nested sums and products, with implementations available in Sigma.The input terms f_i(k) may be arbitrarily nested sums and products.
  • Algebraic independence: If parameterized telescoping has no solution in a given ΠΣ∗-field, the corresponding sums can be represented in a larger field by transcendental extensions.A difference-ring monomorphism then transfers these transcendence properties to sequences.
  • Algebraic independence: Combining the criterion with summation-theory results shows that whole classes of sequences, including harmonic-number sequences, are transcendental.The introduction presents this as a consequence of the parameterized-telescoping criterion together with established summation methods.
  • Recurrence minimality: The results provide new insight into when Zeilberger’s algorithm finds an optimal recurrence and when it may fail to compute a minimal-order recurrence.This connects nonexistence of telescoping solutions with recurrence-order behavior.

2. Basic notions: ΠΣ∗-extensions and generalized d’Alembertian extension

This section develops difference-field foundations for representing nested sums and products through ΠΣ∗-extensions, then establishes structural criteria for telescoping solutions in generalized d’Alembertian extensions.

  • Difference fields: A difference ring or field consists of a ring or field equipped with an automorphism σ, whose fixed elements form the constant field K.The paper assumes the constant set is itself a field.
  • ΠΣ∗-extensions: A ΠΣ∗-extension preserves the constant field, adjoins a transcendental t, and updates it multiplicatively as σ(t) = at or additively as σ(t) = t + a.Π-extensions use σ(t)/t ∈ F, while Σ∗-extensions use σ(t) − t ∈ F.
  • Generalized d’Alembertian extensions: Generalized d’Alembertian extensions require σ(t_i) = α_i t_i + β_i, with α_i in the base field and β_i polynomial in earlier generators.This ordering supports the nested sum-product representations used later.
  • Structural criteria: In a generalized d’Alembertian extension, σ(g) − g is polynomial in the generators exactly when g itself is polynomial in those generators.Theorem 2.7 rules out rational-function solutions outside the polynomial ring.

3. Parameterized telescoping, ΠΣ∗-extensions and the ring of sequences

The section establishes an equivalence between unsolvable parameterized telescoping and adjoining independent indefinite sums, then embeds the resulting difference structures into the ring of sequences.

  • Parameterized telescoping: The paper obtains a criterion for checking transcendence in a difference field from the absence of suitable telescoping solutions.This criterion is the basis for the later algebraic-independence results.
  • Parameterized telescoping: Theorem 3.1 equates the absence of a nonzero constant combination telescoping to the existence of a Σ∗-extension with σ(t_i) = t_i + f_i.The equivalence connects telescoping obstructions with adjoining sum generators.
  • The ring of sequences: The ring of K-sequences is formed from sequences modulo eventual equality, making the shift S an automorphism.The construction identifies field elements with constant sequences.
  • The ring of sequences: A difference-ring monomorphism embeds the polynomial ring of a generalized d’Alembertian extension into the sequence ring while preserving constants and the shift operation.This transfers transcendence properties from the extension to sequences.

4. The monomorphism construction

The monomorphism construction extends sequence embeddings through generalized d’Alembertian towers, preserving injectivity and computable control functions under stated hypotheses.

  • Evaluation control: The evaluation map defines sequence images that eventually respect addition, multiplication, and shifts of elements in the difference ring.The associated o-function bounds when these identities become valid.
  • Iterative extension: The construction proceeds iteratively by extending a K-homomorphism when a new generator satisfies σ(t) = αt + β.The extension is uniquely determined up to an additive or nonzero multiplicative constant, depending on the generator type.
  • Iterative extension: If the initial map is injective, the extended map remains injective, and an o-function continues to exist after adjoining the generator.The proof handles additive and multiplicative extensions separately.
  • Iterative extension: Repeated application yields a K-homomorphism or K-monomorphism from the polynomial ring of any generalized d’Alembertian extension into S(K).Computability of the resulting o-function follows from computable initial control functions and a computable z-function.
  • Ground-field extensions: The rational-function extension theorem preserves computable z- and o-functions, while corresponding embeddings are established for rational, q-rational, and mixed cases.A related corollary supplies computable embeddings for rational-function fields with shifted n and q-multiplicative generators.
  • Scope: The authors leave open whether every ΠΣ∗-field over K can be embedded in S(K).Asymptotic arguments may produce embeddings for more general ΠΣ∗-fields, but universality remains unresolved.

5. A criterion to check algebraic independence

The paper gives an equivalence between the non-existence of parameterized telescoping solutions and algebraic independence of the associated sum sequences. This criterion is algorithmically checkable and supports classification of sum families.

  • 5. A criterion to check algebraic independence: Theorem 5.1 makes the absence of a nontrivial parameterized telescoping solution equivalent to algebraic independence of the corresponding sum sequences.The sequences are algebraically independent over τ(F[t1, . . . , te]) for sufficiently large starting index r.
  • 5. A criterion to check algebraic independence: The sums are represented by adjoining generators s1, . . . , sd satisfying σ(si) = si + fi.Under the no-solution condition, this produces a Σ∗-extension over the generalized d’Alembertian extension.
  • 5. A criterion to check algebraic independence: A K-monomorphism maps the constructed generators si to the corresponding sequences of partial sums.The mapping extends τ and sends si to (Si(n))n≥0, enabling transfer of transcendence properties to the sequence ring.
  • 5. A criterion to check algebraic independence: Sigma can test non-existence of a solution to the parameterized telescoping equation, thereby deciding transcendence for the associated sums.A suitable starting index r is computable when τ has computable o- and z-functions.
  • 5. A criterion to check algebraic independence: Restricting the summands to structured classes allows the authors to predict when parameterized telescoping solutions cannot exist.This yields classifications of multiple families of algebraically independent sums.

6. Rational sums

For rational summands, the criterion yields algebraic independence results over K(n) under the absence of rational parameterized telescoping solutions and suitable denominator conditions. It produces harmonic, q-, and mixed analogues through related constructions.

  • 6. Rational sums: Theorem 6.1 states that rational sums are algebraically independent over K(n) when no rational g(k) and constants ci satisfy the telescoping relation.The result applies to sequences formed from rational functions f1(k), . . . , fd(k), for sufficiently large r.
  • 6. Rational sums: Corollary 6.2 gives algebraic independence for sums with polynomial numerators and a common denominator q satisfying nonvanishing and shifted-coprimality conditions.The denominator must satisfy q(r) ≠ 0 on positive integers and gcd(q(k), q(k + r)) = 1 for positive shifts.
  • 6. Rational sums: Choosing pi = ui = 1 and q = k in Corollary 6.2 yields algebraic independence results for generalized harmonic numbers.The paper presents these numbers as an example of the rational-sum framework.
  • 6. Rational sums: Theorem 5.1 combined with Corollary 4.10 produces q-versions and mixed versions of the rational-sum results.Example 6.4 gives a typical application involving q-harmonic numbers.
  • 6. Rational sums: Corollary 6.5 extends the denominator conditions to multiple rational sums with pairwise shifted-coprime denominators.It concludes algebraic independence over K(n).

7. Hypergeometric sums and the minimality of recurrences

For nondegenerate hypergeometric inputs, failure of telescoping characterizes algebraic independence of sums and clarifies when Zeilberger’s algorithm achieves minimal recurrence order. Specialization can introduce lower-order relations, changing both recurrence minimality and independence.

  • Hypergeometric framework: A hypergeometric term is represented in a ΠΣ∗-field, where Gosper’s and Zeilberger’s algorithms test for telescoping solutions.The representation excludes terms of the form γ^k r(k), with γ a root of unity and r(k) rational.
  • Algebraic independence: If no parameterized telescoping solution exists, the associated sums are algebraically independent over the relevant rational-function field.The result applies when no constants c_i and rational certificate g satisfy the telescoping relation.
  • Minimal recurrence order: Zeilberger’s algorithm finds a recurrence with minimal order for sums of the form (7.3) when a recurrence exists.The paper connects minimality to the absence of additional lower-order linear recurrence relations.
  • Specialization effects: If specialization introduces additional lower-order relations, Zeilberger’s algorithm does not succeed in finding the minimal-order recurrence.Setting n = m is given as a case where the algebraic-independence situation changes drastically.
  • Criteria and examples: Abramov’s criterion yields algebraic independence of f(m,n) together with all shifted sums S(m+i,n) when its criterion is satisfied.The conclusion is stated over Q(m)(n) for the sequence f(m,n) and the family of sums beginning at k = 0.
  • Criteria and examples: For individually nonsummable hypergeometric terms, the terms f_i(n) and their sums S_i(n) are jointly algebraically independent.The theorem assumes a ΠΣ∗-field representation and excludes Gosper-summable terms.

8. Nested sums

The framework extends to generalized d’Alembertian extensions and can certify algebraic independence for nested sums when creative telescoping fails to reduce recurrence order. A specialized sum may nonetheless satisfy a substantially lower-order recurrence.

  • Nested sums: The paper extends most ideas from the hypergeometric setting to sequences represented in generalized d’Alembertian extensions.This extension is illustrated through a nested-sum example treated with creative telescoping.
  • Nested sums: Sigma constructs a ΠΣ∗-field, designs a Q(m)-monomorphism, and proves algorithmically that the relevant telescoping equation has no solution.The resulting transcendence conclusion follows from Theorem 5.1.
  • Nested sums: The specialized sum S(n) = S(n,n) has different behavior and satisfies a recurrence of order two.This contrasts with the unspecialized nested-sum family discussed immediately beforehand.

9. A transcendence criterion for products

The section characterizes algebraic independence of products through equivalent conditions involving the absence of multiplicative telescoping relations and the existence of Π-extensions. It also gives rational-function criteria and examples supporting algorithmic checks.

  • Theorem 9.1: Theorem 9.1 equates the absence of a nonzero integer telescoping relation with the existence of a Π-extension adjoining generators whose shifts multiply them by f_i.The relation is expressed using g and integer exponents c_i; the Π-extension satisfies σ(t_i)=f_i t_i.
  • Algorithmic criterion: Karr’s algorithm can check the existence of the product telescoping relation when the base difference field is a ΠΣ∗-field over K.This makes the criterion algorithmically applicable in the stated difference-field setting.
  • Theorem 9.2: Theorem 9.2 provides an analogous equivalence over a difference field with constant field K, with algebraic independence over τ(F).The result applies when no g and nonzero integer vector satisfy the product relation (9.1).
  • Example: The sequences 2^n, 3^n, 5^n, 7^n, … over the prime numbers are presented as algebraically independent over K(n).This is given as Example 9.3.
  • Rational-function criteria: Coprimality conditions on rational functions rule out the telescoping relation and yield algebraic independence results for their associated products.The section first states a ΠΣ∗-extension criterion and then gives a polynomial-shift version over K[k].
  • Theorem 9.1: These equivalent conditions imply that the corresponding products are algebraically independent over K(n).The theorem states that, for sufficiently large r, the associated sequences admit no nonzero polynomial relation over K(n).

10. Conclusion

The conclusion states that telescoping methods provide criteria for algebraic independence of nested sums and products, while summation theory establishes transcendence for whole classes of sums. It also points to refinements that may strengthen these tools.

  • 10. Conclusion: Telescoping, creative telescoping, and parameterized telescoping yield criteria for checking algebraic independence of nested sum expressions.For hypergeometric sums, Zeilberger’s algorithm can be used; Sigma applies to indefinite nested sums and products.
  • 10. Conclusion: For hypergeometric terms, implementations of Zeilberger’s algorithm can check transcendence, while Sigma can check algebraic independence of indefinite nested sums and products.The conclusion distinguishes the hypergeometric-term setting from the more general indefinite nested sum-product setting.
  • 10. Conclusion: Summation-theory results show that whole classes of sums are transcendental.The authors note that refinements of summation theory could provide stronger tools for proving or disproving transcendence.
  • 10. Conclusion: Results predicting contiguous relations may help refine the paper’s transcendence criteria, including Corollary 7.3.The conclusion specifically cites Peter Paule’s results as a possible refinement.
Loading 0808.2596v1…