Atoms in the Semigroup of Non-Negative Integer Matrices

技術要約：非負整数行列の半群における原子（Atoms）

問題提起
本論文は、非零の行列式を持つ非負整数成分の $2 \times 2$ 行列からなる半群 $M_2(\mathbb{N}_0)^\bullet$ の分解特性を調査するものである。非可換な設定において一意の分解が一般には成立しないものの、主な焦点は、この半群における「原子（atom）」（既約元）の特定にある。ある要素が、2つの非単元要素の積として表せないとき、その要素は原子である。Baethら（2022年）によっていくつかの基本的な原子のクラスが確立されているが、完全な分類は依然として未知であり、この半群における大多数の行列の分解可能性は未決定である。

手法
著者らは、新たな原子のクラスを特定するために、理論的分析と計算による検証を組み合わせた手法を用いている。その手法は、以下の構造的性質および技術に基づいている。

1. 構造的制約： 本研究は、「二重に均衡した（doubly-balanced）」行列（どの行も列も支配的でないもの）かつ隣接する成分が互いに素である行列に焦点を当てている。既知のクラスに含まれない原子は、これらの条件を満たさなければならないことが先行研究から示されている。
2. 行列式分析： 著者らは、最小成分に基づく分解可能な行列の行列式の下限を導出している。行列式の乗法的性質を分析することにより、特定の行列式の値（例：素数 $p$ に対して $p, 2p, 4p$、および $16, 32$）が、二重に均衡した行列の分解を不可能にすることを特定している。
3. 除数閉じた部分集合： 重要な手法上のステップとして、互いに素な成分を持つ両対称行列（bisymmetric matrices） $X = \begin{pmatrix} x & y \\ y & x \end{pmatrix}$ の集合 $B^*$ への探索範囲の限定が含まれる。著者らは、$B^*$ が $M_2(\mathbb{N}_0)^\bullet$ の除数閉じた（divisor-closed）部分集合であることを証明している。これは、もし $B^*$ 内の行列が分解されるならば、その因子もまた $B^*$ 内に存在しなければならないことを意味する。この簡約化により、分解の探索空間が大幅に縮小される。
4. 境界不等式： 著者らは、分解可能な行列の成分に関する上限を導出している。具体的には、分解可能な行列 $X = \begin{pmatrix} w & x \\ y & z \end{pmatrix}$ について、非対角成分は対角成分の関数によって制限される。これらの境界の違反は、行列が原子であるための十分条件となる。
5. アルゴリズム探索： $B^*$ の除数閉じた性質を利用して、著者らは因子探索アルゴリズムを開発した。すべての $2 \times 2$ 因子行列を探索する代わりに、最小成分を固定し、対角要素を分割することで探索を最適化し、計算量を3つの変数へと削減している。

主要な貢献と結果

• 行列式による新たな原子のクラス： 著者らは、行列式の値に基づく2つの新しい原子のクラスを特定した。

  • 定理 4.3： 隣接する成分が互いに素である二重に均衡した行列は、その行列式が $p, 2p,$ または $4p$ （$p$ は素数）であるとき、原子である。
  • 定理 4.4： このような行列は、行列式が $16$または$32$ であるときも原子である。
  • これらの結果は、これらのタイプの行列が分解可能である場合、その因子の行列式が確立された下限（具体的には、因子の行列式が $1, 2,$または$4$ になり得ないこと）に抵触することを示すことで導出されている。

• 成分境界による新たな原子のクラス：

  • 定理 6.2： $w \le z < x, y$ を満たす二重に均衡した行列 $X = \begin{pmatrix} w & x \\ y & z \end{pmatrix}$ について、$x > 2(z-1)(w-1)$ または $y > 2(z-1)(w-1)$ ならば、$X$ は原子である。
  • 定理 6.4： $B^*$ に属する両対称行列 $X = \begin{pmatrix} x & y \\ y & x \end{pmatrix}$ について、$\max\{x, y\} > 1 + \frac{(\min\{x, y\})^2}{4}$ ならば、$X$ は原子である。

• 両対称行列の除数閉じた性質：

  • 定理 5.1： $B^*$ （互いに素な成分を持つ両対称行列）は $M_2(\mathbb{N}_0)^\bullet$ において除数閉じている。これは、$B^*$ 内の行列のいかなる分解も、すべて $B^*$ 内の行列で構成されなければならないことを意味する。この結果により、探索範囲を両対称の形式に限定することが可能となり、分類問題の複雑さが大幅に軽減される。

• 計算による分類：

  • 除数閉じた性質と導出された境界を用いて、著者らは最小成分が $4000$までの$M_2(\mathbb{N}_0)^\bullet$ におけるすべての両対称原子を分類するアルゴリズムを実装した。
  • 定理 7.1： $\min\{x, y\} \le 4000$ である $B^*$ 内の行列は、それら（およびその随伴元）が著者らの生成した分解可能行列のリストに現れない場合に限り、原子である。論文では、最小成分が $42$までの行列のリストを提供しており、範囲$4000$ までの全データセットについては参照を示している。

意義
本論文は、$M_2(\mathbb{N}_0)^\bullet$ における既知の原子のカタログを拡張することにより、行列の半群における非一意分解の理解を進展させると主張している。特定の行列式の値や成分の大きさの比率が既約性を保証することを確立することで、著者らは、網羅的な分解を行うことなく原子を特定するための具体的な基準を提供している。さらに、互いに素な成分を持つ両対称行列が除数閉じた部分集合を形成するという証明は、この特定のクラスに対する分解問題の複雑さを軽減する構造的な結果である。計算結果は、最小成分 $4000$ までの両対称行列に関する完全な分類を提供しており、ほとんどの分解可能性の問題が未解決のまま残されている文献の空白を埋めるものである。本研究は、行列の分解を「パープレックス整数（perplex integers）」（分裂複素数）の理論に結びつけ、特定の既約パープレックス整数のクラスが、この半群における原子的な行列に対応することを確認している。