MK Deciding zero equivalence of certain special sequences

Some Sample Sequences in C

• rational functions in n

• n ↦ α^{n} (α ∈ ℚ)

• n ↦ α^{β^{n}} (α ∈ ℚ, β ∈ ℕ)

• n ↦ F(n)

• n ↦ Γ(αn + β) (α ∈ ℚ)

• n ↦ ∑_{k=1}^{n} H(n)\binom{n}{k}

• next week: Extend C to C^{∗} including n ↦ \sqrt[5]{H(n)^{2} + 7\sqrt{n}}, n ↦ \sqrt{n + \sqrt{(n − 1) + \sqrt{(n − 2) + ⋯ + \sqrt{2 + \sqrt{1}}}}}

RISC 2003 Combinatorics Seminar

Some Closure Properties

• Let f(n), g(n), h(n) ∈ C, h(n) ≠ 0 for all n.

• f + g, f · g, f − g, αf, f/h ∈ C

• n ↦ ∑_{k=1}^{n} f(n) ∈ C

• n ↦ ∏_{k=1}^{n} f(n) ∈ C

• n ↦ K_{k=1}^{n} h(n) = h(1) + \frac{1}{h(2) + \frac{1}{⋯ + \frac{1}{h(n)}}} ∈ C

• next week: C ⊆ C^{∗}, f ∈ C^{∗} ⇒ \sqrt[r]{f} ∈ C^{∗}, etc.

RISC 2003 Combinatorics Seminar

Formal definition of C

• Every constant sequence {α}_{n} is in C.

• If {f(n)}_{n} satisfies

f(n + r) = p(f(n), f(n + 1), …, f(n + r − 1)) (n ∈ ℕ)

where p is a multivariate polynomial whose coefficients are rational functions of elements in C, then {f(n)}_{n} ∈ C • It is assumed that no denominator ever vanishes on the natural numbers.

• Example:

f(n + 3) = f(n + 2)^{5} + \frac{n + H(n)}{F(n) + 1} f(n)f(n + 1) + ( ∏_{k=1}^{n}(−1)^{k}) (f(n) + f(n + 1) + f(n + 2)) + 1

f(1) = 2, f(2) = 0, f(3) = −\frac{2345071}{394757}.

• next week: formal definition of C^{∗}.

Algebraic Representation of Elements of C

• Like Karr(sten): formal variables t_{i} represent (sub)expressions

• Like Burki: additional formal variables st_{i}, sst_{i}, … encode the behaviour of shift.

• Additional variables are also introduced for every denominator.

• Example: f(n) := ∑_{k=1}^{n} \frac{k! H(k)}{F(k)}

R_{0} := {st_{1} − t_{1} − 1,  ∼ k  R := {st_{1} − t_{1} − 1, sst_{1} − st_{1} − 1,
sst_{2} − st_{2} − t_{2},  ∼ F(k)  sst_{2} − st_{2} − t_{2},
st_{3} − t_{3}st_{1},  ∼ k! = Πk  st_{3} − t_{3}st_{1}, sst_{3} − st_{3}sst_{1},
t_{4}t_{1} − 1,  ∼ 1/k  t_{4}t_{1} − 1, st_{4}st_{1} − 1, sst_{4}sst_{1} − 1
t_{5}t_{2} − 1,  ∼ 1/ F(k)  t_{5}t_{2} − 1, st_{5}st_{2} − 1, sst_{5}sst_{2} − 1,
st_{6} − t_{6} − st_{4},  ∼ H(k)  st_{6} − t_{6} − st_{4}, sst_{6} − st_{6} − sst_{4},
st_{7} − t_{7} − st_{3}st_{5}st_{6} }  ∼ f(n)  st_{7} − t_{7} − st_{3}st_{5}st_{6}, sst_{7} − st_{7} − sst_{3}sst_{5}sst_{6} }

• For technical convenience, assume R to be filled up till the highest order.

The Proving Algorithm

• Input: f ∈ C a polynomially recursive function

R defining relations of f and its subexpressions

Assumption: t_{m} corresponds to {f(n)}_{n};

The highest order recurrence in R is of order r.

Output:  “correct” or “incorrect” depending on whether f ≡ 0 or not

1 \underline{function} prove(f, R) 2 k := 0 3 I_{0} := ⟨R⟩ + ⟨t_{m}, st_{m}, …, s^{r−1}t_{m}⟩ ⊴ K[t_{∗}, …, s^{r}t_{∗}] 4 \underline{while} s^{r+k}t_{m} ∉ Rad I_{k} 5 k := k + 1 6 I_{k} := I_{k−1} + ⟨s^{r+k−1}t_{m}⟩ + ⟨s^{k}R⟩ ⊴ K[t_{∗}, …, s^{k+r}t_{∗}]

7  \underline{repeat}

8 // check initial conditions 9 \underline{for} n \underline{from} 0 \underline{to} k + r − 1 \underline{do} 10 \underline{if} f(n) ≠ 0 \underline{then} 11 \underline{return} “incorrect”, counterexample = n

12  \underline{return} “correct”

Termination

• Theorem The algorithm is correct. (obvious)

• Theorem The algorithm and terminates.

• Lemma 1 For every variable s^{r}t_{i}, there exists exactly one polynomial p ∈ R with p = s^{r}t_{i} + q or p = qs^{r}t_{i} − 1 for some polynomial q which depends only on variables s^{r′}t_{i′} with i′ ≤ i and r′ ≤ r, but not on s^{r}t_{i}.

• Lemma 2 If X, Y are algebraic sets, Y is irreducible and X ⊊ Y, then dim X < dim Y.

Proof Literature, e.g., Theorem I.§6.1.1 in Schafarewitsch 1972

• Lemma 3 Let I_{k} = ⟨R ∪ sR ∪ ⋯ ∪ s^{k}R⟩ ⊴ K[t_{∗}, st_{∗}, …, s^{k+r}t_{∗}] (k ∈ ℕ).

Let I_{n} ⊆ 𝔞 ⊴ K[t_{∗}, st_{∗}, …, s^{n+r}t_{∗}] for some n be fixed.

1. dim 𝔞 ≥ dim(𝔞 + I_{n+1}) where the first dim is wrt. K[t_{∗}, st_{∗}, …, s^{n+r}t_{∗}] and the second dim is wrt. K[t_{∗}, st_{∗}, …, s^{n+r+1}t_{∗}].

2. 𝔞 has the same number of components as 𝔞 + I_{n+1}, or 𝔞 + I_{n+1} = ⟨1⟩.

MK Deciding zero equivalence of certain special sequences

Example I

• Consider \frac{F(n)}{F(n + 1)} + ∑_{k=1}^{n} \frac{(−1)^{k}}{F(k) F(k + 1)} = 0.

• Put

R := {st_{1} + t_{1}, sst_{1} + st_{1}  ∼ (−1)^{n}
− sst_{2} + st_{2} + t_{2},  ∼ F(n)
t_{3}t_{2} − 1, st_{3}st_{2} − 1, sst_{3}sst_{2} − 1,  ∼ 1/ F(n)
− st_{5} + t_{5} + t_{2}st_{4}t_{4}, −sst_{5} + st_{5} + st_{2}sst_{4}st_{4},  ∼ Σ
− st_{6} + t_{3}st_{4} + st_{5}, −sst_{6} + st_{3}sst_{4} + sst_{5} }  ∼ f(n)

• Write I_{k} := ⟨R ∪ sR ∪ ⋯ ∪ s^{k}R⟩. Loop

I_{0} + ⟨t_{m}, st_{m}, Xsst_{m} − 1⟩ ≠ ⟨1⟩
I_{1} + ⟨t_{m}, st_{m}, sst_{m}, Xssst_{m} − 1⟩ ≠ ⟨1⟩
I_{2} + ⟨t_{m}, …, s^{3}t_{m}, Xs^{4}t_{m} − 1⟩ = ⟨1⟩

• Check n = 1, 2, 3, 4.

RISC 2003 Combinatorics Seminar

Example II

• Consider f(n) = (n − 7)(n − 3) ∑_{k=1}^{n}(−1)^{k}(1 + ∏_{k=1}^{n}(−1)^{k}).

• We have f(n) = 0, 0, 0, 0, 0, 0, 0, 0, 0, …

• Conjecture: f ≡ 0

• Put

R := {−st_{1} + t_{1} + 1, st_{2} + t_{2}, −st_{3} + t_{3} + st_{2}, −st_{4} + t_{4} + st_{2},
− t_{5} + (t_{1} − 3)(t_{1} − 7)t_{3}t_{4}, −st_{5} + (st_{1} − 3)(st_{1} − 7)st_{3}st_{4}}

• Loop:

I_{0} + ⟨t_{5}, Xst_{5} − 1⟩ ≠ ⟨1⟩
I_{1} + ⟨t_{5}, st_{5}, Xsst_{5} − 1⟩ ≠ ⟨1⟩
⋮
I_{10} + ⟨t_{5}, …, s^{10}t_{5}, Xs^{11}t_{5} − 1⟩ ≠ ⟨1⟩
I_{11} + ⟨t_{5}, …, s^{11}t_{5}, Xs^{12}t_{5} − 1⟩ = ⟨1⟩

• Check 11 initial conditions, find f(1) = ⋯ = f(10) = 0 ≠ f(11) = −64.

MK Deciding zero equivalence of certain special sequences

Example III

• An identity family with an arbitary function.

• Consider ∑_{k=1}^{n} ( H(k) ∑_{i=1}^{k} f(i)) = (−n + (1 + n) H(n)) ∑_{k=1}^{n} f(k) − ∑_{k=1}^{n} ( H(k) − 1)kf(k).

• Let t_{4} correspond to f(n). Put

R = {−st_{1} + t_{1} + 1,  ∼ n
t_{2}t_{1} − 1, st_{2}st_{1} − 1,  ∼ 1/n
−st_{3} + t_{3} + st_{2},  ∼ H(n)
−st_{5} + t_{5} + st_{4},  ∼ Σf(n)
−st_{6} + t_{6} + st_{1}(st_{3} − 1)st_{4}, ∼ Σ(H(n) − 1)nf(n)
−st_{7} + t_{7} + st_{3}st_{5},  ∼ Σ(H(n)Σf(n))

−t_{8} − t_{7} + (−t_{1} + (1 + t_{1})t_{3})t_{5} − t_{6}, −st_{8} − st_{7} + (−st_{1} + (1 + st_{1})st_{3})st_{5} − st_{6}}

• I_{0} + ⟨t_{8}, Xst_{8} − 1⟩ = ⟨1⟩

• Need to check one initial value. f(1) = f(1). QED.

RISC 2003 Combinatorics Seminar MK Deciding zero equivalence of certain special sequences

Example IV

• Consider K_{k=1}^{n} (\frac{1}{4} \frac{(k + 1) ((−1)^{k}(π + 2) + (π − 2)) Γ(k/2)}{\sqrt{π} Γ(k/2 + 1/2)} − ∏_{i=1}^{k} ( − \frac{7}{4}i^{2} + 9i − \frac{45}{4})) = ∑_{k=0}^{n} \frac{1}{k!}

• Despite some support by the user, Singular, Magma, Asir, and Cocoa run out of memory or compute for a week without any result.

• However, Faugere’s Gb system does the job in 8 seconds!

• Corollary e ∉ ℚ ( K_{k=1}^{∞} a_{k} ∈ ℚ ⟺^{?} a_{n} is periodic )

Correctness and Termination

• Theorem 1 The algorithm is correct. (obvious)

• Theorem 2 The algorithm and terminates.

• Lemma 1 For every variable s^{r}t_{i}, there exists exactly one polynomial p ∈ R with p = s^{r}t_{i} + q or p = qs^{r}t_{i} − 1 for some polynomial q which depends only on variables s^{r′}t_{i′} with i′ ≤ i and r′ ≤ r, but not on s^{r}t_{i}.

• Lemma 2 If X, Y are algebraic sets, Y is irreducible and X ⊊ Y, then dim X < dim Y.

Proof Literature, e.g., Theorem I.§6.1.1 in Shafarewich 1972

• Lemma 3 Let I_{k} = ⟨R ∪ sR ∪ ⋯ ∪ s^{k}R⟩ ⊴ K[t_{∗}, st_{∗}, …, s^{k+r}t_{∗}] (k ∈ ℕ). Let I_{n} ⊆ 𝔞 ⊴ K[t_{∗}, st_{∗}, …, s^{n+r}t_{∗}] for some n be fixed.

1. dim 𝔞 ≥ dim(𝔞 + I_{n+1}) where the first dim is wrt. K[t_{∗}, st_{∗}, …, s^{n+r}t_{∗}] and the second dim is wrt. K[t_{∗}, st_{∗}, …, s^{n+r+1}t_{∗}].

2. 𝔞 has the same number of components as 𝔞 + I_{n+1}, or 𝔞 + I_{n+1} = ⟨1⟩.

Summary: Proofs of last week

• Theorem 2 The algorithm terminates.

• Consider primary decomposition of I_{k}.

• If s^{k+r}t_{m} ∈ Rad I_{k}, then done.

• Otherwise, s^{k+r}t_{m} ∉ Rad p for at least one primary component.

• dim (V (s^{k+r}t_{m}) ∩ V (p)) < dim V (p).

• Shift does not harm components and their dimension (Lemma 3)

• Dixon’s lemma: Replacement of components by others of strictly lower dimension cannot happen infinitely often.

• Hence: At some point, V (I_{k}) =, i.e. I_{k} = ⟨1⟩, i.e. s^{k+r} ∈ Rad I_{k}.

• Lemma 3.1 I_{k} = ⟨R ∪ ⋯ ∪ s^{k}R⟩, I_{k−1} ⊆ 𝔞 ⊴ K[…, s^{k−1+r}t_{m}]. Then dim 𝔞 ≤ dim(𝔞 + I_{k}).

• wlog. 𝔞 primary.

• Extension by one variable increases the dimension by 1

• Show: the relation of the new variable drops the dimension by 1

• Put X = V (𝔞 + ⟨p⟩), Y = V (𝔞).

• X = Y ∩ V (p).

• Clear: X ⊆ Y. Show: X ⊊ Y.

• Let x = (x_{1}, …, x_{n}) ∈ X. Then x′ = (x_{1}, …, x_{n−1}, x_{n} + 1) ∈ Y \ X because p is linear in x_{n} and cannot have more than one solution.

Work in Progress

• Find interesting examples → Complete the proof of e ∉ ℚ

• Find a priori bounds for k.

→ Complexity bounds.

→ Variants of the algorithm.

• Extension to algebraic functions

• Multivariate sequences → Closure under definite summation?