SKOLEM Tool: Solver for the Skolem Problem on Integer LRS

System Explanation

The LRS must be non-degenerate, and not the zero LRS. Leapfrogging only supports simple LRS.
Choose the algorithm(s) and option(s) you wish to run on the given LRS.

Input area

LRS input:

Recurrence relation Exponential polynomial

Line 1: recurrence coefficients a₁ a₂ ... a_k. Line 2: initial values u₀ u₁ ... u_k-1, where u_n+k = a₁u_n+k-1 + ... + a_ku_n.

One line: a sum of c*n^d*(a+bi)^n terms with integer a,b,c,d (Gaussian-integer roots), non-real roots paired with their conjugate. ^ for powers, i for the imaginary unit.

Always render full LRS (otherwise restricted to 400 characters)

I solemnly swear the LRS is non-degenerate (skips degeneracy check, it will timeout or break if the LRS is degenerate!)

I solemnly swear the LRS is minimal (skips minimality check)

Use GCD reduction (reduces initial values by GCD)

Debug:print

Choose Algorithm

Use leapfrogging algorithm of [2]

Factor subcases (merges subcases into single linear set, sometimes requires higher modulo classes)

Find the smallest modulo (often slower)

Use the fast jump algorithm

Use Baker-Davenport algorithm

Bound only (will not search for zeros up to the bound, if timeout try this to see if bound is very big)

List LRS up to bound (up to 400 unless render full LRS also chosen)

Search in both directions

Search for negative indices (note: positive will not be searched)

Use p-adic algorithm of [5]

Assume all zeros have multiplicity 1 (Hensel-only algorithm)

Lower bound on prime used =

Number of p-adic digits to output =

Use BOUNDED-SKOLEM (checks the range [0,b] using the p-adic algorithm of [5])

Either exhibits a zero of u_n in [0,b], or proves none exists in that range, or - if precision alone cannot settle a particular candidate - reports that candidate rather than guessing. Precision is chosen automatically from b, so b can be given in scientific notation for very large ranges.

Assume all zeros have multiplicity 1 (Hensel-only algorithm, much faster; uncheck for a more thorough but often much slower search)

SKOLEM Tool

System Explanation

Input area

Choose Algorithm

Output area

Baker-Davenport result

p-adic result

BOUNDED-SKOLEM result

Leapfrogging result