0
$\begingroup$

It is known that linear recurrences with constant coefficients can be computed via powers in $\mathbb{Z}[x]/f(x)$.

We believe that this generalizes to quotients of multivariate polynomial rings.

Let $f_1(x_1,..,x_m),f_2(x_1,..,x_m)...f_k(x_1,...,x_m)$. be polynomials with integer coefficients.

Define the quotient $K=\mathbb{Q}[x_1,...,x_m]/(f_1,...f_k)$.

Let the term order be lexicographic (for an answer your can chose another order).

Working over $K$, let $t(n)=(\sum_{i=1}^m x_i)^n$.

$t(n)$ is group satisfying $t(n+m)=t(n) t(m)$.

In general, if $k=m$ then $t(n)$ is of bounded degree and it is efficiently computable.

Define $a(n)$ to be the coefficient of $x_1$ in $t(n)$.

Q1 When $a(n)$ satisfy linear recurrence with constant rational coefficients?

Very limited experimental data suggests that the probability is about 1/2.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Don't you need to specify a term ordering for Gröbner base calculations in order to define $a(n)$? Otherwise if e.g. $f_1 = x_1 - x_2 - 3$ it's arbitrary whether $t(1) = x_1 + x_2 = 2x_1 - 3 = 2x_2 + 3$ yields $a(1) = 0$ or $a(1) = 2$. $\endgroup$
    – Peter Taylor
    Commented Jan 23 at 12:29
  • $\begingroup$ @PeterTaylor Thanks, very good point. Edited with lexicographic term order, allowing as an option another order. $\endgroup$
    – joro
    Commented Jan 23 at 12:57
  • $\begingroup$ I'm curious about your experimental data. I'm experimenting with $k=m=2$, $f_i$ up to cubic terms, coefficients from $\{-1,0,1\}$ except fixed constant coefficients $-5$ and $-13$ (as a compromise because working over $\mathbb{Q}[a,b]$ and using constant coefficients $-a$ and $-b$ ran into memory trouble), and in hundreds of thousands of tests I haven't yet found a case which doesn't appear to have a linear recurrence of order at most $9$. $\endgroup$
    – Peter Taylor
    Commented Jan 24 at 12:02
  • $\begingroup$ @PeterTaylor I noticed problems with my experimental data, but I still get experimental support. For k=m=2 and degree f_i=2 I got these recurrences, starting from x ZERO and recurrence order up to 10: f_i: [x0^2 - x1^2 - 4*x1 - 1, -x0^2 + 2*x1^2], [x0^2 - 2*x0 + x1^2 - x1 + 5, -x0*x1 + x1^2 + 9*x1], [x0^2 - 3*x0 + x1^2 - x1 - 3, -x0^2 + x0*x1 + 2*x0 + x1^2 + 2*x1], [-x1^2 + x1, -x0^2 - 4*x0*x1 + 5*x0 - x1^2 - x1], [x0^2 + x0 + 4*x1^2 + 5, -2*x0*x1 + x1^2 + 6*x1] $\endgroup$
    – joro
    Commented Jan 24 at 14:43

0

Reset to default

You must log in to answer this question.