ProbXiv
Explorersign in
Problem archiveProblem record

Statement

For an integer k≥1k \ge 1, integer coefficients a1,…,aka_1,\dots,a_k, and integer initial values u0,…,uk−1u_0,\dots,u_{k-1}, let (un)n≥0(u_n)_{n \ge 0} be the sequence determined by

un+k=a1un+k−1+a2un+k−2+⋯+akun(n≥0),u_{n+k} = a_1 u_{n+k-1} + a_2 u_{n+k-2} + \cdots + a_k u_n \qquad (n \ge 0),

and let

Z((ai)i=1k,(uj)j=0k−1)={ n≥0:un=0 }Z\big((a_i)_{i=1}^{k},(u_j)_{j=0}^{k-1}\big) = \{\, n \ge 0 : u_n = 0 \,\}

be its set of zero positions.

There exists an algorithm which, given as input the order kk, the coefficients a1,…,aka_1,\dots,a_k and the initial values u0,…,uk−1u_0,\dots,u_{k-1} (each written in binary), terminates and outputs whether

∃ n≥0:un=0,\exists\, n \ge 0 : u_n = 0,

i.e. whether Z((ai)i=1k,(uj)j=0k−1)≠∅Z\big((a_i)_{i=1}^{k},(u_j)_{j=0}^{k-1}\big) \neq \emptyset.

The same assertion is made for recurrences whose coefficients and initial values are rational numbers given as ratios of binary integers, and for recurrences whose coefficients and initial values are algebraic numbers, each specified by its minimal polynomial over Q\mathbb{Q} together with an isolating rational approximation.

Record

Added
Links

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.