On $n$-Dimensional Sequences. I
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914787035709440 |
|---|---|
| author | Norton, Graham H. |
| author_facet | Norton, Graham H. |
| contents | Let $R$ be a commutative ring and let $n \geq 1.$ We study $Γ(s)$, the generating function and Ann$(s)$, the ideal of characteristic polynomials of $s$, an $n$--dimensional sequence over $R$.
We express $f(X_1,\ldots,X_n) \cdot Γ(s)(X_1^{-1},\ldots ,X_n^{-1})$ as a partitioned sum. That is, we give (i) a $2^n$--fold ``border'' partition (ii) an explicit expression for the product as a $2^n$--fold sum; the support of each summand is contained in precisely one member of the partition. A key summand is $β_0(f,s)$, the ``border polynomial'' of $f$ and $s$, which is divisible by $X_1\cdots X_n$.
We say that $s$ is {\em eventually rectilinear} if the elimination ideals Ann$(s)\cap R[X_i]$ contain an $f_i(X_i)$ for $1 \leq i \leq n$. In this case, we show that $\mbox{Ann}(s)$ is the ideal quotient $(\sum_{i=1}^n(f_i)\ :\ β_0(f,s)/(X_1\cdots X_n)).$
When $R$ and $R[[X_1,X_2, \ldots ,X_n]]$ are factorial domains (e.g. $R$ a principal ideal domain or ${\Bbb F}[X_1,\ldots,X_n]$), we compute {\em the monic generator} $γ_i$ of $\mbox{Ann}(s) \cap R[X_i]$ from known $f_i \in \mbox{Ann}(s) \cap R[X_i]$ or from a finite number of $1$--dimensional linear recurring sequences over $R$. Over a field ${\Bbb F}$ this gives an $O(\prod_{i=1}^n δγ_i^3)$ algorithm to compute an ${\Bbb F}$--basis for $\mbox{Ann}(s)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_04022 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On $n$-Dimensional Sequences. I Norton, Graham H. Commutative Algebra Symbolic Computation Let $R$ be a commutative ring and let $n \geq 1.$ We study $Γ(s)$, the generating function and Ann$(s)$, the ideal of characteristic polynomials of $s$, an $n$--dimensional sequence over $R$. We express $f(X_1,\ldots,X_n) \cdot Γ(s)(X_1^{-1},\ldots ,X_n^{-1})$ as a partitioned sum. That is, we give (i) a $2^n$--fold ``border'' partition (ii) an explicit expression for the product as a $2^n$--fold sum; the support of each summand is contained in precisely one member of the partition. A key summand is $β_0(f,s)$, the ``border polynomial'' of $f$ and $s$, which is divisible by $X_1\cdots X_n$. We say that $s$ is {\em eventually rectilinear} if the elimination ideals Ann$(s)\cap R[X_i]$ contain an $f_i(X_i)$ for $1 \leq i \leq n$. In this case, we show that $\mbox{Ann}(s)$ is the ideal quotient $(\sum_{i=1}^n(f_i)\ :\ β_0(f,s)/(X_1\cdots X_n)).$ When $R$ and $R[[X_1,X_2, \ldots ,X_n]]$ are factorial domains (e.g. $R$ a principal ideal domain or ${\Bbb F}[X_1,\ldots,X_n]$), we compute {\em the monic generator} $γ_i$ of $\mbox{Ann}(s) \cap R[X_i]$ from known $f_i \in \mbox{Ann}(s) \cap R[X_i]$ or from a finite number of $1$--dimensional linear recurring sequences over $R$. Over a field ${\Bbb F}$ this gives an $O(\prod_{i=1}^n δγ_i^3)$ algorithm to compute an ${\Bbb F}$--basis for $\mbox{Ann}(s)$. |
| title | On $n$-Dimensional Sequences. I |
| topic | Commutative Algebra Symbolic Computation |
| url | https://arxiv.org/abs/2405.04022 |