On the mortality problem: From multiplicative matrix equations to linear recurrence sequences and beyond
On the mortality problem: From multiplicative matrix equations to linear recurrence sequences and beyond
复制标题
关于死亡率问题：从乘法矩阵方程到线性递推序列及其他
DOI：
10.1016/j.ic.2021.104736
复制
发表时间：
2021
影响因子：
1
通讯作者：
Bell P
中科院分区：
文献类型：
--
作者：
Bell P
我们考虑死亡率问题的一个变形：给定k× k矩阵A1，.，At，是否存在非负整数m1，.，mt使得A1 m1 <$Atmt等于零矩阵？已知这个问题在t≤ 2时是可判定的，但对于具有足够大的t和k的整数矩阵是不可判定的。我们证明了当t= 3时，这个问题与Skolem问题是Turing等价的，因此当k≤ 3时是可判定的（分别为k= 4）在（分别真实的）代数数。因此，方程A1 m1 A2 m2 A3 m3等于零矩阵的三元组（m1，m2，m3）的集合是半线性集的直积的有限并。对于t= 4，我们表明，解决方案集可以是非半线性的，因此不太可能有一个连接到Skolem的问题。利用超越理论中的Baker定理和S-单位方程等有力工具，证明了上三角2× 2有理矩阵的可判定性.
We consider a variant of the mortality problem: given k× k matrices A 1,…, A t, do there exist nonnegative integers m 1,…, m t such that A 1 m 1⋯ A t m t equals the zero matrix? This problem is known to be decidable when t≤ 2 but undecidable for integer matrices with sufficiently large t and k. We prove that for t= 3 this problem is Turing-equivalent to Skolem's problem and thus decidable for k≤ 3 (resp. k= 4) over (resp. real) algebraic numbers. Consequently, the set of triples (m 1, m 2, m 3) for which the equation A 1 m 1 A 2 m 2 A 3 m 3 equals the zero matrix is a finite union of direct products of semilinear sets. For t= 4 we show that the solution set can be non-semilinear, and thus there is unlikely to be a connection to Skolem's problem. We prove decidability for upper-triangular 2× 2 rational matrices by employing powerful tools from transcendence theory such as Baker's theorem and S-unit equations.