$J$-ideals of matrices

Let $B$ be an $n\times n$-matrix over a principal ideal domain $D$.

For an ideal $J$, the $J$-ideal of $B$ is defined to be $N_J(B)=\{f\in D[X]\mid f(B)\in M_n(J)\}$.

For a prime element $p$ of $D$ and $t\ge 0$, a $(p^t)$-minimal polynomial of $B$ is a monic polynomial $f\in N_{(p^t)}(B)$ of minimal degree.

This module computes these minimal polynomials.

Let $p$ be a prime element of $D$. Then there is a finite set ${\mathcal{S}}_p$ of positive integers and monic polynomials ${\nu }_{ps}$ for $s\in {\mathcal{S}}_p$ such that for $t\ge 1$,

$$\begin{array}{r}{N}_{(p^t)}(B)={\mu }_{B}D[X]+p^{t}D[X]+\sum _{\begin{array}{c}s\in {\mathcal{S}}_p\\ s\le b(t)\end{array}}{p}^{max\{0,t-s\}}{\nu }_{ps}D[X]\end{array}$$

holds where $b(t)=min\{r\in {\mathcal{S}}_p\mid r\ge s\}$. The degree of ${\nu }_{ps}$ is strictly increasing in $s\in {\mathcal{S}}_p$ and ${\nu }_{ps}$ is a $(p^s)$-minimal polynomial. If $t\le max{\mathcal{S}}_p$, then the summand ${\mu }_{B}D[X]$ can be omitted.

All computations are done by the class ComputeMinimalPolynomials where various intermediate results are cached. It provides the following methods:

• p_minimal_polynomials() computes ${\mathcal{S}}_p$ and the monic polynomials ${\nu }_{ps}$.

• null_ideal() determines $N_{(p^t)}(B)$.

• prime_candidates() determines all primes $p$ where ${\mathcal{S}}_p$ might be non-empty.

• integer_valued_polynomials_generators() determines the generators of the ring $\{f\in K[X]\mid f(B)\in M_n(D)\}$ of integer valued polynomials on $B$.

EXAMPLES:

Sage

sage: from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
sage: B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
sage: C = ComputeMinimalPolynomials(B)
sage: C.prime_candidates()
[2, 3, 5]
sage: for t in range(4):
....:     print(C.null_ideal(2^t))
Principal ideal (1) of
    Univariate Polynomial Ring in x over Integer Ring
Ideal (2, x^2 + x) of
    Univariate Polynomial Ring in x over Integer Ring
Ideal (4, x^2 + 3*x + 2) of
    Univariate Polynomial Ring in x over Integer Ring
Ideal (8, x^3 + x^2 - 12*x - 20, 2*x^2 + 6*x + 4) of
    Univariate Polynomial Ring in x over Integer Ring
sage: C.p_minimal_polynomials(2)
{2: x^2 + 3*x + 2}
sage: C.integer_valued_polynomials_generators()
(x^3 + x^2 - 12*x - 20, [1, 1/4*x^2 + 3/4*x + 1/2])

Python

>>> from sage.all import *
>>> from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
>>> B = matrix(ZZ, [[Integer(1), Integer(0), Integer(1)], [Integer(1), -Integer(2), -Integer(1)], [Integer(10), Integer(0), Integer(0)]])
>>> C = ComputeMinimalPolynomials(B)
>>> C.prime_candidates()
[2, 3, 5]
>>> for t in range(Integer(4)):
...     print(C.null_ideal(Integer(2)**t))
Principal ideal (1) of
    Univariate Polynomial Ring in x over Integer Ring
Ideal (2, x^2 + x) of
    Univariate Polynomial Ring in x over Integer Ring
Ideal (4, x^2 + 3*x + 2) of
    Univariate Polynomial Ring in x over Integer Ring
Ideal (8, x^3 + x^2 - 12*x - 20, 2*x^2 + 6*x + 4) of
    Univariate Polynomial Ring in x over Integer Ring
>>> C.p_minimal_polynomials(Integer(2))
{2: x^2 + 3*x + 2}
>>> C.integer_valued_polynomials_generators()
(x^3 + x^2 - 12*x - 20, [1, 1/4*x^2 + 3/4*x + 1/2])

Sage Live

from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
C = ComputeMinimalPolynomials(B)
C.prime_candidates()
for t in range(4):
    print(C.null_ideal(2^t))
C.p_minimal_polynomials(2)
C.integer_valued_polynomials_generators()

The last output means that

$$\{f\in \mathbf{Q}[X]\mid f(B)\in M_3(\mathbf{Z})\}=(x^3+x^2-12x-20)\mathbf{Q}[X]+\mathbf{Z}[X]+\frac{1}{4}(x^2+3x+2)\mathbf{Z}[X].$$

Todo

Test code over PIDs other than ZZ.

This requires implementation of frobenius() over more general domains than ZZ.

Additionally, lifting() requires modification or a bug needs fixing, see AskSage Question 35555.

REFERENCES:

[Ris2016], [HR2016]

AUTHORS:

• Clemens Heuberger (2016)

• Roswitha Rissner (2016)

ACKNOWLEDGEMENT:

• Clemens Heuberger is supported by the Austrian Science Fund (FWF): P 24644-N26.

• Roswitha Rissner is supported by the Austrian Science Fund (FWF): P 27816-N26.

Classes and Methods

class sage.matrix.compute_J_ideal.ComputeMinimalPolynomials(B)

Bases: SageObject

Create an object for computing $(p^t)$-minimal polynomials and $J$-ideals.

For an ideal $J$ and a square matrix $B$ over a principal ideal domain $D$, the $J$-ideal of $B$ is defined to be $N_J(B)=\{f\in D[X]\mid f(B)\in M_n(J)\}$.

For a prime element $p$ of $D$ and $t\ge 0$, a $(p^t)$-minimal polynomial of $B$ is a monic polynomial $f\in N_{(p^t)}(B)$ of minimal degree.

The characteristic polynomial of $B$ is denoted by ${\chi }_B$; $n$ is the size of $B$.

INPUT:

• B – a square matrix over a principal ideal domain $D$

OUTPUT:

An object which allows to call p_minimal_polynomials(), null_ideal() and integer_valued_polynomials_generators().

EXAMPLES:

Sage

sage: from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
sage: B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
sage: C = ComputeMinimalPolynomials(B)
sage: C.prime_candidates()
[2, 3, 5]
sage: for t in range(4):
....:     print(C.null_ideal(2^t))
Principal ideal (1) of
    Univariate Polynomial Ring in x over Integer Ring
Ideal (2, x^2 + x) of
    Univariate Polynomial Ring in x over Integer Ring
Ideal (4, x^2 + 3*x + 2) of
    Univariate Polynomial Ring in x over Integer Ring
Ideal (8, x^3 + x^2 - 12*x - 20, 2*x^2 + 6*x + 4) of
    Univariate Polynomial Ring in x over Integer Ring
sage: C.p_minimal_polynomials(2)
{2: x^2 + 3*x + 2}
sage: C.integer_valued_polynomials_generators()
(x^3 + x^2 - 12*x - 20, [1, 1/4*x^2 + 3/4*x + 1/2])

Python

>>> from sage.all import *
>>> from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
>>> B = matrix(ZZ, [[Integer(1), Integer(0), Integer(1)], [Integer(1), -Integer(2), -Integer(1)], [Integer(10), Integer(0), Integer(0)]])
>>> C = ComputeMinimalPolynomials(B)
>>> C.prime_candidates()
[2, 3, 5]
>>> for t in range(Integer(4)):
...     print(C.null_ideal(Integer(2)**t))
Principal ideal (1) of
    Univariate Polynomial Ring in x over Integer Ring
Ideal (2, x^2 + x) of
    Univariate Polynomial Ring in x over Integer Ring
Ideal (4, x^2 + 3*x + 2) of
    Univariate Polynomial Ring in x over Integer Ring
Ideal (8, x^3 + x^2 - 12*x - 20, 2*x^2 + 6*x + 4) of
    Univariate Polynomial Ring in x over Integer Ring
>>> C.p_minimal_polynomials(Integer(2))
{2: x^2 + 3*x + 2}
>>> C.integer_valued_polynomials_generators()
(x^3 + x^2 - 12*x - 20, [1, 1/4*x^2 + 3/4*x + 1/2])

Sage Live

from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
C = ComputeMinimalPolynomials(B)
C.prime_candidates()
for t in range(4):
    print(C.null_ideal(2^t))
C.p_minimal_polynomials(2)
C.integer_valued_polynomials_generators()

current_nu(p, t, pt_generators, prev_nu)

Compute $(p^t)$-minimal polynomial of $B$.

INPUT:

• p – a prime element of $D$

• t – positive integer

• pt_generators – list $(g_1,\dots ,g_s)$ of polynomials in $D[X]$ such that $N_{(p^t)}(B)=(g_1,\dots ,g_s)+p{N}_{(p^{t-1})}(B)$

• prev_nu – a $(p^{t-1})$-minimal polynomial of $B$

OUTPUT:

A $(p^t)$-minimal polynomial of $B$.

EXAMPLES:

Sage

sage: from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
sage: B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
sage: C = ComputeMinimalPolynomials(B)
sage: x = polygen(ZZ, 'x')
sage: nu_1 = x^2 + x
sage: generators_4 = [2*x^2 + 2*x, x^2 + 3*x + 2]
sage: C.current_nu(2, 2, generators_4, nu_1)
x^2 + 3*x + 2

Python

>>> from sage.all import *
>>> from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
>>> B = matrix(ZZ, [[Integer(1), Integer(0), Integer(1)], [Integer(1), -Integer(2), -Integer(1)], [Integer(10), Integer(0), Integer(0)]])
>>> C = ComputeMinimalPolynomials(B)
>>> x = polygen(ZZ, 'x')
>>> nu_1 = x**Integer(2) + x
>>> generators_4 = [Integer(2)*x**Integer(2) + Integer(2)*x, x**Integer(2) + Integer(3)*x + Integer(2)]
>>> C.current_nu(Integer(2), Integer(2), generators_4, nu_1)
x^2 + 3*x + 2

Sage Live

from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
C = ComputeMinimalPolynomials(B)
x = polygen(ZZ, 'x')
nu_1 = x^2 + x
generators_4 = [2*x^2 + 2*x, x^2 + 3*x + 2]
C.current_nu(2, 2, generators_4, nu_1)

ALGORITHM:

[HR2016], Algorithm 4.

find_monic_replacements(p, t, pt_generators, prev_nu)

Replace possibly non-monic generators of $N_{(p^t)}(B)$ by monic generators.

INPUT:

• p – a prime element of $D$

• t – nonnegative integer

• pt_generators – list $(g_1,\dots ,g_s)$ of polynomials in $D[X]$ such that $N_{(p^t)}(B)=(g_1,\dots ,g_s)+p{N}_{(p^{t-1})}(B)$

• prev_nu – a $(p^{t-1})$-minimal polynomial of $B$

OUTPUT:

A list $(h_1,\dots ,h_r)$ of monic polynomials such that $N_{(p^t)}(B)=(h_1,\dots ,h_r)+p{N}_{(p^{t-1})}(B)$.

EXAMPLES:

Sage

sage: from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
sage: B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
sage: C = ComputeMinimalPolynomials(B)
sage: x = polygen(ZZ, 'x')
sage: nu_1 = x^2 + x
sage: generators_4 = [2*x^2 + 2*x, x^2 + 3*x + 2]
sage: C.find_monic_replacements(2, 2, generators_4, nu_1)
[x^2 + 3*x + 2]

Python

>>> from sage.all import *
>>> from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
>>> B = matrix(ZZ, [[Integer(1), Integer(0), Integer(1)], [Integer(1), -Integer(2), -Integer(1)], [Integer(10), Integer(0), Integer(0)]])
>>> C = ComputeMinimalPolynomials(B)
>>> x = polygen(ZZ, 'x')
>>> nu_1 = x**Integer(2) + x
>>> generators_4 = [Integer(2)*x**Integer(2) + Integer(2)*x, x**Integer(2) + Integer(3)*x + Integer(2)]
>>> C.find_monic_replacements(Integer(2), Integer(2), generators_4, nu_1)
[x^2 + 3*x + 2]

Sage Live

from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
C = ComputeMinimalPolynomials(B)
x = polygen(ZZ, 'x')
nu_1 = x^2 + x
generators_4 = [2*x^2 + 2*x, x^2 + 3*x + 2]
C.find_monic_replacements(2, 2, generators_4, nu_1)

ALGORITHM:

[HR2016], Algorithms 2 and 3.

integer_valued_polynomials_generators()

Determine the generators of the ring of integer valued polynomials on $B$.

OUTPUT:

A pair (mu_B, P) where P is a list of polynomials in $K[X]$ such that

$$\{f\in K[X]\mid f(B)\in M_n(D)\}={\mu }_{B}K[X]+\sum _{g\in P}gD[X]$$

where $K$ denotes the fraction field of $D$.

EXAMPLES:

Sage

sage: from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
sage: B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
sage: C = ComputeMinimalPolynomials(B)
sage: C.integer_valued_polynomials_generators()
(x^3 + x^2 - 12*x - 20, [1, 1/4*x^2 + 3/4*x + 1/2])

Python

>>> from sage.all import *
>>> from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
>>> B = matrix(ZZ, [[Integer(1), Integer(0), Integer(1)], [Integer(1), -Integer(2), -Integer(1)], [Integer(10), Integer(0), Integer(0)]])
>>> C = ComputeMinimalPolynomials(B)
>>> C.integer_valued_polynomials_generators()
(x^3 + x^2 - 12*x - 20, [1, 1/4*x^2 + 3/4*x + 1/2])

Sage Live

from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
C = ComputeMinimalPolynomials(B)
C.integer_valued_polynomials_generators()

mccoy_column(p, t, nu)

Compute matrix for McCoy’s criterion.

INPUT:

• p – a prime element in $D$

• t – positive integer

• nu – a $(p^t)$-minimal polynomial of $B$

OUTPUT:

An $(n^2+1)\times 1$ matrix $g$ with first entry nu such that $\left(\begin{array}{cc}b& -{\chi }_{B}I\end{array}\right)g\equiv 0(\mathrm{mod}{p}^t)$ where $b$ consists of the entries of $\mathrm{adj}(X-B)$.

EXAMPLES:

Sage

sage: from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
sage: B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
sage: C = ComputeMinimalPolynomials(B)
sage: x = polygen(ZZ, 'x')
sage: nu_4 = x^2 + 3*x + 2
sage: g = C.mccoy_column(2, 2, nu_4)
sage: b = matrix(9, 1, (x - B).adjugate().list())
sage: M = matrix.block([[b, -B.charpoly(x)*matrix.identity(9)]])
sage: (M*g % 4).is_zero()
True

Python

>>> from sage.all import *
>>> from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
>>> B = matrix(ZZ, [[Integer(1), Integer(0), Integer(1)], [Integer(1), -Integer(2), -Integer(1)], [Integer(10), Integer(0), Integer(0)]])
>>> C = ComputeMinimalPolynomials(B)
>>> x = polygen(ZZ, 'x')
>>> nu_4 = x**Integer(2) + Integer(3)*x + Integer(2)
>>> g = C.mccoy_column(Integer(2), Integer(2), nu_4)
>>> b = matrix(Integer(9), Integer(1), (x - B).adjugate().list())
>>> M = matrix.block([[b, -B.charpoly(x)*matrix.identity(Integer(9))]])
>>> (M*g % Integer(4)).is_zero()
True

Sage Live

from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
C = ComputeMinimalPolynomials(B)
x = polygen(ZZ, 'x')
nu_4 = x^2 + 3*x + 2
g = C.mccoy_column(2, 2, nu_4)
b = matrix(9, 1, (x - B).adjugate().list())
M = matrix.block([[b, -B.charpoly(x)*matrix.identity(9)]])
(M*g % 4).is_zero()

ALGORITHM:

[HR2016], Algorithm 5.

null_ideal(b=0)

Return the $(b)$-ideal $N_{(b)}(B)=\{f\in D[X]\mid f(B)\in M_n(bD)\}$.

INPUT:

• b – an element of $D$ (default: 0)

OUTPUT: an ideal in $D[X]$

EXAMPLES:

Sage

sage: from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
sage: B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
sage: C = ComputeMinimalPolynomials(B)
sage: C.null_ideal()
Principal ideal (x^3 + x^2 - 12*x - 20) of
    Univariate Polynomial Ring in x over Integer Ring
sage: C.null_ideal(2)
Ideal (2, x^2 + x) of
    Univariate Polynomial Ring in x over Integer Ring
sage: C.null_ideal(4)
Ideal (4, x^2 + 3*x + 2) of
    Univariate Polynomial Ring in x over Integer Ring
sage: C.null_ideal(8)
Ideal (8, x^3 + x^2 - 12*x - 20, 2*x^2 + 6*x + 4) of
    Univariate Polynomial Ring in x over Integer Ring
sage: C.null_ideal(3)
Ideal (3, x^3 + x^2 - 12*x - 20) of
    Univariate Polynomial Ring in x over Integer Ring
sage: C.null_ideal(6)
Ideal (6, 2*x^3 + 2*x^2 - 24*x - 40, 3*x^2 + 3*x) of
    Univariate Polynomial Ring in x over Integer Ring

Python

>>> from sage.all import *
>>> from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
>>> B = matrix(ZZ, [[Integer(1), Integer(0), Integer(1)], [Integer(1), -Integer(2), -Integer(1)], [Integer(10), Integer(0), Integer(0)]])
>>> C = ComputeMinimalPolynomials(B)
>>> C.null_ideal()
Principal ideal (x^3 + x^2 - 12*x - 20) of
    Univariate Polynomial Ring in x over Integer Ring
>>> C.null_ideal(Integer(2))
Ideal (2, x^2 + x) of
    Univariate Polynomial Ring in x over Integer Ring
>>> C.null_ideal(Integer(4))
Ideal (4, x^2 + 3*x + 2) of
    Univariate Polynomial Ring in x over Integer Ring
>>> C.null_ideal(Integer(8))
Ideal (8, x^3 + x^2 - 12*x - 20, 2*x^2 + 6*x + 4) of
    Univariate Polynomial Ring in x over Integer Ring
>>> C.null_ideal(Integer(3))
Ideal (3, x^3 + x^2 - 12*x - 20) of
    Univariate Polynomial Ring in x over Integer Ring
>>> C.null_ideal(Integer(6))
Ideal (6, 2*x^3 + 2*x^2 - 24*x - 40, 3*x^2 + 3*x) of
    Univariate Polynomial Ring in x over Integer Ring

Sage Live

from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
C = ComputeMinimalPolynomials(B)
C.null_ideal()
C.null_ideal(2)
C.null_ideal(4)
C.null_ideal(8)
C.null_ideal(3)
C.null_ideal(6)

p_minimal_polynomials(p, s_max=None)

Compute $(p^s)$-minimal polynomials ${\nu }_s$ of $B$.

Compute a finite subset $\mathcal{S}$ of the positive integers and $(p^s)$-minimal polynomials ${\nu }_s$ for $s\in \mathcal{S}$.

For $0<t\le max\mathcal{S}$, a $(p^t)$-minimal polynomial is given by ${\nu }_s$ where $s=min\{r\in \mathcal{S}\mid r\ge t\}$. For $t>max\mathcal{S}$, the minimal polynomial of $B$ is also a $(p^t)$-minimal polynomial.

INPUT:

• p – a prime in $D$

• s_max – positive integer (default: None); if set, only $(p^s)$-minimal polynomials for s <= s_max are computed (see below for details)

OUTPUT:

A dictionary. Keys are the finite set $\mathcal{S}$, the values are the associated $(p^s)$-minimal polynomials ${\nu }_s$, $s\in \mathcal{S}$.

Setting s_max only affects the output if s_max is at most $max\mathcal{S}$ where $\mathcal{S}$ denotes the full set. In that case, only those ${\nu }_s$ with s <= s_max are returned where s_max is always included even if it is not included in the full set $\mathcal{S}$.

EXAMPLES:

Sage

sage: from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
sage: B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
sage: C = ComputeMinimalPolynomials(B)
sage: C.p_minimal_polynomials(2)
{2: x^2 + 3*x + 2}
sage: set_verbose(1)
sage: C = ComputeMinimalPolynomials(B)
sage: C.p_minimal_polynomials(2)
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
------------------------------------------
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
p = 2, t = 1:
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
Result of lifting:
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
F =
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
[x^2 + x]
[      x]
[      0]
[      1]
[      1]
[  x + 1]
[      1]
[      0]
[      0]
[  x + 1]
verbose 1 (...: compute_J_ideal.py, current_nu)
------------------------------------------
verbose 1 (...: compute_J_ideal.py, current_nu)
(x^2 + x)
verbose 1 (...: compute_J_ideal.py, current_nu)
Generators with (p^t)-generating property:
verbose 1 (...: compute_J_ideal.py, current_nu)
[x^2 + x]
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
nu = x^2 + x
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
corresponding columns for G
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
[x^2 + x]
[  x + 2]
[      0]
[      1]
[      1]
[  x - 1]
[     -1]
[     10]
[      0]
[  x + 1]
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
------------------------------------------
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
p = 2, t = 2:
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
Result of lifting:
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
F =
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
[  2*x^2 + 2*x x^2 + 3*x + 2]
[          2*x         x + 4]
[            0             0]
[            2             1]
[            2             1]
[      2*x + 2         x + 1]
[            2            -1]
[            0            10]
[            0             0]
[      2*x + 2         x + 3]
verbose 1 (...: compute_J_ideal.py, current_nu)
------------------------------------------
verbose 1 (...: compute_J_ideal.py, current_nu)
(2*x^2 + 2*x, x^2 + 3*x + 2)
verbose 1 (...: compute_J_ideal.py, current_nu)
Generators with (p^t)-generating property:
verbose 1 (...: compute_J_ideal.py, current_nu)
[x^2 + 3*x + 2]
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
nu = x^2 + 3*x + 2
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
corresponding columns for G
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
[x^2 + 3*x + 2]
[        x + 4]
[            0]
[            1]
[            1]
[        x + 1]
[           -1]
[           10]
[            0]
[        x + 3]
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
------------------------------------------
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
p = 2, t = 3:
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
Result of lifting:
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
F =
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
[x^3 + 7*x^2 + 6*x x^3 + 3*x^2 + 2*x]
[        x^2 + 8*x         x^2 + 4*x]
[                0                 0]
[                x             x + 4]
[            x + 4                 x]
[    x^2 + 5*x + 4           x^2 + x]
[           -x + 4                -x]
[             10*x              10*x]
[                0                 0]
[        x^2 + 7*x     x^2 + 3*x + 4]
verbose 1 (...: compute_J_ideal.py, current_nu)
------------------------------------------
verbose 1 (...: compute_J_ideal.py, current_nu)
(x^3 + 7*x^2 + 6*x, x^3 + 3*x^2 + 2*x)
verbose 1 (...: compute_J_ideal.py, current_nu)
Generators with (p^t)-generating property:
verbose 1 (...: compute_J_ideal.py, current_nu)
...
verbose 1 (...: compute_J_ideal.py, current_nu)
[x^3 + 3*x^2 + 2*x]
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
nu = x^3 + 3*x^2 + 2*x
{2: x^2 + 3*x + 2}
sage: set_verbose(0)
sage: C.p_minimal_polynomials(2, s_max=1)
{1: x^2 + x}
sage: C.p_minimal_polynomials(2, s_max=2)
{2: x^2 + 3*x + 2}
sage: C.p_minimal_polynomials(2, s_max=3)
{2: x^2 + 3*x + 2}

Python

>>> from sage.all import *
>>> from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
>>> B = matrix(ZZ, [[Integer(1), Integer(0), Integer(1)], [Integer(1), -Integer(2), -Integer(1)], [Integer(10), Integer(0), Integer(0)]])
>>> C = ComputeMinimalPolynomials(B)
>>> C.p_minimal_polynomials(Integer(2))
{2: x^2 + 3*x + 2}
>>> set_verbose(Integer(1))
>>> C = ComputeMinimalPolynomials(B)
>>> C.p_minimal_polynomials(Integer(2))
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
------------------------------------------
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
p = 2, t = 1:
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
Result of lifting:
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
F =
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
[x^2 + x]
[      x]
[      0]
[      1]
[      1]
[  x + 1]
[      1]
[      0]
[      0]
[  x + 1]
verbose 1 (...: compute_J_ideal.py, current_nu)
------------------------------------------
verbose 1 (...: compute_J_ideal.py, current_nu)
(x^2 + x)
verbose 1 (...: compute_J_ideal.py, current_nu)
Generators with (p^t)-generating property:
verbose 1 (...: compute_J_ideal.py, current_nu)
[x^2 + x]
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
nu = x^2 + x
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
corresponding columns for G
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
[x^2 + x]
[  x + 2]
[      0]
[      1]
[      1]
[  x - 1]
[     -1]
[     10]
[      0]
[  x + 1]
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
------------------------------------------
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
p = 2, t = 2:
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
Result of lifting:
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
F =
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
[  2*x^2 + 2*x x^2 + 3*x + 2]
[          2*x         x + 4]
[            0             0]
[            2             1]
[            2             1]
[      2*x + 2         x + 1]
[            2            -1]
[            0            10]
[            0             0]
[      2*x + 2         x + 3]
verbose 1 (...: compute_J_ideal.py, current_nu)
------------------------------------------
verbose 1 (...: compute_J_ideal.py, current_nu)
(2*x^2 + 2*x, x^2 + 3*x + 2)
verbose 1 (...: compute_J_ideal.py, current_nu)
Generators with (p^t)-generating property:
verbose 1 (...: compute_J_ideal.py, current_nu)
[x^2 + 3*x + 2]
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
nu = x^2 + 3*x + 2
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
corresponding columns for G
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
[x^2 + 3*x + 2]
[        x + 4]
[            0]
[            1]
[            1]
[        x + 1]
[           -1]
[           10]
[            0]
[        x + 3]
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
------------------------------------------
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
p = 2, t = 3:
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
Result of lifting:
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
F =
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
[x^3 + 7*x^2 + 6*x x^3 + 3*x^2 + 2*x]
[        x^2 + 8*x         x^2 + 4*x]
[                0                 0]
[                x             x + 4]
[            x + 4                 x]
[    x^2 + 5*x + 4           x^2 + x]
[           -x + 4                -x]
[             10*x              10*x]
[                0                 0]
[        x^2 + 7*x     x^2 + 3*x + 4]
verbose 1 (...: compute_J_ideal.py, current_nu)
------------------------------------------
verbose 1 (...: compute_J_ideal.py, current_nu)
(x^3 + 7*x^2 + 6*x, x^3 + 3*x^2 + 2*x)
verbose 1 (...: compute_J_ideal.py, current_nu)
Generators with (p^t)-generating property:
verbose 1 (...: compute_J_ideal.py, current_nu)
...
verbose 1 (...: compute_J_ideal.py, current_nu)
[x^3 + 3*x^2 + 2*x]
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
nu = x^3 + 3*x^2 + 2*x
{2: x^2 + 3*x + 2}
>>> set_verbose(Integer(0))
>>> C.p_minimal_polynomials(Integer(2), s_max=Integer(1))
{1: x^2 + x}
>>> C.p_minimal_polynomials(Integer(2), s_max=Integer(2))
{2: x^2 + 3*x + 2}
>>> C.p_minimal_polynomials(Integer(2), s_max=Integer(3))
{2: x^2 + 3*x + 2}

Sage Live

from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
C = ComputeMinimalPolynomials(B)
C.p_minimal_polynomials(2)
set_verbose(1)
C = ComputeMinimalPolynomials(B)
C.p_minimal_polynomials(2)
set_verbose(0)
C.p_minimal_polynomials(2, s_max=1)
C.p_minimal_polynomials(2, s_max=2)
C.p_minimal_polynomials(2, s_max=3)

ALGORITHM:

[HR2016], Algorithm 5.

prime_candidates()

Determine those primes $p$ where ${\mu }_B$ might not be a $(p)$-minimal polynomial.

OUTPUT: list of primes

EXAMPLES:

Sage

sage: from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
sage: B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
sage: C = ComputeMinimalPolynomials(B)
sage: C.prime_candidates()
[2, 3, 5]
sage: C.p_minimal_polynomials(2)
{2: x^2 + 3*x + 2}
sage: C.p_minimal_polynomials(3)
{}
sage: C.p_minimal_polynomials(5)
{}

Python

>>> from sage.all import *
>>> from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
>>> B = matrix(ZZ, [[Integer(1), Integer(0), Integer(1)], [Integer(1), -Integer(2), -Integer(1)], [Integer(10), Integer(0), Integer(0)]])
>>> C = ComputeMinimalPolynomials(B)
>>> C.prime_candidates()
[2, 3, 5]
>>> C.p_minimal_polynomials(Integer(2))
{2: x^2 + 3*x + 2}
>>> C.p_minimal_polynomials(Integer(3))
{}
>>> C.p_minimal_polynomials(Integer(5))
{}

Sage Live

from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
C = ComputeMinimalPolynomials(B)
C.prime_candidates()
C.p_minimal_polynomials(2)
C.p_minimal_polynomials(3)
C.p_minimal_polynomials(5)

This means that $3$ and $5$ were candidates, but actually, ${\mu }_B$ turns out to be a $(3)$-minimal polynomial and a $(5)$-minimal polynomial.

sage.matrix.compute_J_ideal.lifting(p, t, A, G)

Compute generators of $\{f\in D[X{]}^d\mid Af\equiv 0(\mathrm{mod}{p}^t)\}$ given generators of $\{f\in D[X{]}^d\mid Af\equiv 0(\mathrm{mod}{p}^{t-1})\}$.

INPUT:

• p – a prime element of some principal ideal domain $D$

• t – nonnegative integer

• A – a $c\times d$ matrix over $D[X]$

• G – a matrix over $D[X]$. The columns of $\left(\begin{array}{cc}{p}^{t-1}I& G\end{array}\right)$ are generators of $\{f\in D[X{]}^d\mid Af\equiv 0(\mathrm{mod}{p}^{t-1})\}$; can be set to None if t is zero

OUTPUT:

A matrix $F$ over $D[X]$ such that the columns of $\left(\begin{array}{ccc}{p}^{t}I& F& pG\end{array}\right)$ are generators of $\{f\in D[X{]}^d\mid Af\equiv 0(\mathrm{mod}{p}^t)\}$.

EXAMPLES:

Sage

sage: from sage.matrix.compute_J_ideal import lifting
sage: X = polygen(ZZ, 'X')
sage: A = matrix([[1, X], [2*X, X^2]])
sage: G0 = lifting(5, 0, A, None)
sage: G1 = lifting(5, 1, A, G0); G1
[]
sage: (A*G1 % 5).is_zero()
True
sage: A = matrix([[1, X, X^2], [2*X, X^2, 3*X^3]])
sage: G0 = lifting(5, 0, A, None)
sage: G1 = lifting(5, 1, A, G0); G1
[3*X^2]
[    X]
[    1]
sage: (A*G1 % 5).is_zero()
True
sage: G2 = lifting(5, 2, A, G1); G2
[15*X^2 23*X^2]
[   5*X      X]
[     5      1]
sage: (A*G2 % 25).is_zero()
True
sage: lifting(5, 10, A, G1)
Traceback (most recent call last):
...
ValueError: A*G not zero mod 5^9

Python

>>> from sage.all import *
>>> from sage.matrix.compute_J_ideal import lifting
>>> X = polygen(ZZ, 'X')
>>> A = matrix([[Integer(1), X], [Integer(2)*X, X**Integer(2)]])
>>> G0 = lifting(Integer(5), Integer(0), A, None)
>>> G1 = lifting(Integer(5), Integer(1), A, G0); G1
[]
>>> (A*G1 % Integer(5)).is_zero()
True
>>> A = matrix([[Integer(1), X, X**Integer(2)], [Integer(2)*X, X**Integer(2), Integer(3)*X**Integer(3)]])
>>> G0 = lifting(Integer(5), Integer(0), A, None)
>>> G1 = lifting(Integer(5), Integer(1), A, G0); G1
[3*X^2]
[    X]
[    1]
>>> (A*G1 % Integer(5)).is_zero()
True
>>> G2 = lifting(Integer(5), Integer(2), A, G1); G2
[15*X^2 23*X^2]
[   5*X      X]
[     5      1]
>>> (A*G2 % Integer(25)).is_zero()
True
>>> lifting(Integer(5), Integer(10), A, G1)
Traceback (most recent call last):
...
ValueError: A*G not zero mod 5^9

Sage Live

from sage.matrix.compute_J_ideal import lifting
X = polygen(ZZ, 'X')
A = matrix([[1, X], [2*X, X^2]])
G0 = lifting(5, 0, A, None)
G1 = lifting(5, 1, A, G0); G1
(A*G1 % 5).is_zero()
A = matrix([[1, X, X^2], [2*X, X^2, 3*X^3]])
G0 = lifting(5, 0, A, None)
G1 = lifting(5, 1, A, G0); G1
(A*G1 % 5).is_zero()
G2 = lifting(5, 2, A, G1); G2
(A*G2 % 25).is_zero()
lifting(5, 10, A, G1)

ALGORITHM:

[HR2016], Algorithm 1.

sage.matrix.compute_J_ideal.p_part(f, p)

Compute the $p$-part of a polynomial.

INPUT:

• f – a polynomial over $D$

• p – a prime in $D$

OUTPUT:

A polynomial $g$ such that $\mathrm{deg}g\le \mathrm{deg}f$ and all nonzero coefficients of $f-pg$ are not divisible by $p$.

EXAMPLES:

Sage

sage: from sage.matrix.compute_J_ideal import p_part
sage: X = polygen(ZZ, 'X')
sage: f = X^3 + 5*X + 25
sage: g = p_part(f, 5); g
X + 5
sage: f - 5*g
X^3

Python

>>> from sage.all import *
>>> from sage.matrix.compute_J_ideal import p_part
>>> X = polygen(ZZ, 'X')
>>> f = X**Integer(3) + Integer(5)*X + Integer(25)
>>> g = p_part(f, Integer(5)); g
X + 5
>>> f - Integer(5)*g
X^3

Sage Live

from sage.matrix.compute_J_ideal import p_part
X = polygen(ZZ, 'X')
f = X^3 + 5*X + 25
g = p_part(f, 5); g
f - 5*g

Make live