MK/CS Funny Function Identities

Motivation

• Kauers can only prove certain identities with arbitrary many variables, e.g.,

∑_{k=1}^{n}(x_{k} + (x_{k+1} − 1) ∑_{i=1}^{k} x_{i}) ∏_{i=1}^{k} x_{i} = x_{n+1}(∑_{k=1}^{n} x_{k}) ∏_{k=1}^{n} x_{k}

• Schneider can find certain identities with sums and products, e.g.,

∑_{k=1}^{n}(\frac{1}{k} + (\frac{1}{k + 1} − 1) ∑_{i=1}^{k} \frac{1}{i}) ∏_{i=1}^{k} \frac{1}{i} ⟶ \frac{1}{n + 1}(∑_{k=1}^{n} \frac{1}{k}) ∏_{k=1}^{n} \frac{1}{k}

• Both together can find certain identities with arbitrary many variables, e.g.,

∑_{k=1}^{n}(x_{k} + (x_{k+1} − 1) ∑_{i=1}^{k} x_{i}) ∏_{i=1}^{k} x_{i} ⟶ x_{n+1}(∑_{k=1}^{n} x_{k}) ∏_{k=1}^{n} x_{k}

How?

MK/CS Funny Function Identities

Basic Notions

• Difference ring: R, σ

• Difference field: F, σ

• Constant ring/field: ℚ (for convenience)

• Polynomial difference ring: R = F {x} = F [x_{0}, x_{1}, x_{2}, …], σ(x_{i}) := x_{i+1}.

• Free difference field: 𝔽⟨x⟩ = quot(𝔽{x})

• Ideals ⟨S⟩ ⊴ R, difference ideal: ⟨⟨S⟩⟩ ⊴ R

• Difference field extension: quot(F {t}/⟨⟨S⟩⟩) where ⟨⟨S⟩⟩ is “perfect.”

• ΠΣ-Extension: F {t}/⟨⟨t_{1} − at_{0} − b⟩⟩ with a = 1 or b = 0.

• ΠΣ-Field: Tower of ΠΣ-extensions

The Schneider-Equation

• Goal: Given an expression of nested indefinte sum and prodcuts, find a “simpler” representation • Karr’s algorithm (basic idea)

1. Represent the expression by an appropriate tower of ΠΣ-extensions.

2. Solve the Schneider-Equation in this field

3. translate the solution back into ΠΣ-expressions

• Schneider-Equation (most general form)

– Given: a_{0}, …, a_{m} ∈ F, f_{1}, …, f_{n} ∈ F, (F a difference field)

– Find: g ∈ F and c_{1}, …, c_{n} ∈ F such that

a_{m}σ^{m}(g) + a_{m−1}σ^{m−1}(g) + ⋯ + a_{1}σ(g) + a_{0}g = c_{1}f_{1} + ⋯ + c_{n}f_{n}  (S)

Indeed: Find a basis for the vector space of all solutions.

• Sigma can solve the Schneider equation when F is a ΠΣ-field.

Key observation

• The algorithms in Sigma can applied to any difference field F (t) where – F is a difference field where we know how to solve (S) and

– F (t) is a ΠΣ-extension of F.

• Consequence: If we can solve (S) in the free difference field ℚ⟨x⟩, then can build up a ΠΣ tower on this field and do summation with arbitrary many variables.

• Todo: Solve (S) in ℚ⟨x⟩.

MK/CS Funny Function Identities

Global strategy

• Similar to the classical algorithms: ℚ⟨x⟩ ↓ ↑ ℚ{x} ↓ ↑

ℚ[x_{0}, …, x_{r}]

↓ ↑ ℚ[x_{0}, …, x_{r}]_{≤d}

↓ ↑ ℚ^{n}

MK/CS Funny Function Identities

Crash-Course in Denominator Bounding: ℚ⟨x⟩ → ℚ{x}

• Goal: Given the a_{i}, f_{j} from the Schneider-Equation, find a polynomial d such that g is a rational solution of (S) iff

g′ = dg is a polynomial solution of the modified Schneider-Equation

\frac{a_{0}}{d}g′ + \frac{a_{1}}{σ(d)}σ(g′) + ⋯ + \frac{a_{m}}{σ^{m}(d)}σ^{m}(g′) = c_{1}f_{1} + ⋯ + c_{n}f_{n}  (S′)

• Def.: Given a difference field F (t) and f, g ∈ F [t], define spread(f, g) := { m ∈ ℕ_{0} : gcd(f, σ^{m}(g)) ∉ F }

• Observe: spread(f, g) is finite for f, g ∈ ℚ{x} and can be easily computed.

• Define: spread(σ^{m}(a_{m}), a_{0}) = {m_{1} > m_{2} > ⋯ > m_{s}} and

p_{1} = σ^{m}(a_{m}),  p_{i+1} = p_{i}/d_{i},
q_{1} = a_{0},  q_{i+1} = q_{i}/σ^{−m_{i}}(d_{i}),
u_{1} = 1,  u_{i+1} = u_{i} ∏_{j=0}^{m_{i}} σ^{−j}(d_{i}),

where d_{i} = gcd(p_{i}, σ_{m_{i}}(q_{i})).

• Theorem: u_{s} is a denominator bound.

RISC 2004 Combinatorics Seminar MK/CS Funny Function Identities

Order bounding: ℚ{x} → ℚ[x_{0}, …, x_{r}]

• Theorem: If ρ is the maximum order appearing in one of the a_{i} or f_{j}, then any polynomial solution g of (S) must be free of x_{k} for all k > ρ − m + 1.

• Hence it is fine to chose r = ρ − m + 1.

MK/CS Funny Function Identities

Conclusion and Open Problems

• There are several kinds of problems in Symbolic Summation: – ∑_{k=1}^{n} f(k) (indefinite; classic)

– ∑_{k=1}^{n} f(n, k) (definite; also classic)

– ∑_{k=1}^{n} f(k, x_{k}) (presented today)

– ∑_{k=1}^{n} f(n, k, x_{k}) (“semidefinite,” but probably also possible)

– ∑_{k=1}^{n} f(n, k, x_{k}, x_{n}) (“full definite,” probably significantly more complicated)