Submodules AbstractAlgebra

Hi everybody !
I’m now busy with the submodule concept as described in AbstractAlgebra package documentation.
I noticed that, on my point of view, a lot of things are missing in the interface.
For example as a minimum it would be good to decide if some vector of a module M belongs to some submodule S of M.
Such test function apparently doesn’t exist but AA proposes the computation of the intersection of two submodules of the same module, and it seems to be working very well.
So to know if y belongs to S it’s enough to see the generators of the intersection of S with the submodule of dimension 1 generated by y (straight line) if one generator y in S if 0 generators y not in S.
Here’s a test program :

using AbstractAlgebra

F = FreeModule(ZZ, 3)
@show F
v=F([1,2,3])
w=F([1,1,0])
@show v,w
S,f=sub(F,[v,w])
@show S
@show f
@show(gens(S))
@show f(gen(S,1)) #-v+2w
@show f(gen(S,2)) #v-w
S1,f1=sub(F,[v+w])
@show intersect(S,S1) #donc v+w appartient à S
y=F([0,0,1])
S2,f2 =sub(F,[y])
@show intersect(S,S2) #donc y n'appartient pas à S


result (output)

F = Free module of rank 3 over Integers
(v, w) = ((1, 2, 3), (1, 1, 0))
S = Submodule over Integers with 2 generators and no relations

f = Module homomorphism with
Domain: Submodule over Integers with 2 generators and no relations

Codomain: F
gens(S) = AbstractAlgebra.Generic.SubmoduleElem{BigInt}[(1, 0), (0, 1)]
f(gen(S, 1)) = (1, 0, -3)
f(gen(S, 2)) = (0, 1, 3)
intersect(S, S1) = (Submodule over Integers with 1 generator and no relations
, Module homomorphism with
Domain: Submodule over Integers with 1 generator and no relations

Codomain: Submodule over Integers with 2 generators and no relations
)
intersect(S, S2) = (Submodule over Integers with 0 generators and no relations
, Module homomorphism with
Domain: Submodule over Integers with 0 generators and no relations

Codomain: Submodule over Integers with 2 generators and no relations
)



Going a little farther considering two submodules generated by two distinct sets, it is possible to decide if the two modules are equal by testing that every member of the first set belongs to the second submodule and conversely. So a test S==S1 could be provided.

I would like to know if users of AA agree with me or if I miss something and I am too naive. Of course I understand that all these questions sum up to solving linear systems, which is easy for vector spaces over the rationals but more delicate for module over the ring of integers.
Thank you for any reaction.

Gilles

I begin to understand my mistake …
Everything works with vector spaces
for example :

using AbstractAlgebra

F = FreeModule(QQ, 3)
@show F
u=F([1,2,3])
v=F([1,1,0])
@show u,v
S,f=sub(F,[u,v])
@show S
@show f
U=u+v
V=u-v
S1,f1=sub(F,[U,V])
println(S==S1)


behaves as expected, the two subspaces are equal and AA knows about it
Of course if you want to change QQ for ZZ it won’t work any more. Because from U=u+v and V=u-v
you can draw 2u=U+V which doesn’t mean that u itself is a linear combination of U and V because division by 2 is needed, not possible in ZZ.
By the way it should be the same with subspaces of vector spaces over any ield with characteristic 2.
I will make a test.

If f \colon S \to F is a submodule, then checking whether v \in F is an element of S is the same as asking whether v is in the image of f (or equivalently, whether v has a preimage under f). Unfortunately, there is no haspreimage function (yet), but the preimage function will throw an error if there is no preimage.

julia> F = FreeModule(ZZ, 3);

julia> v = F([1, 2, 3]);

julia> w = F([1, 1, 0]);

julia> S, f = sub(F, [v, w]);

julia> preimage(f, v)
(1, 2)

julia> preimage(f, w)
(1, 1)

julia> preimage(f, v + w)
(2, 3)

julia> preimage(f, basis(F)[1])
ERROR: Unable to solve linear system
Stacktrace:
[1] error(s::String)
@ Base ./error.jl:33
[2] solve_left
@ ~/.julia/packages/AbstractAlgebra/yXuIT/src/Matrix.jl:2768 [inlined]
[3] preimage(f::AbstractAlgebra.Generic.ModuleHomomorphism{BigInt}, v::AbstractAlgebra.Generic.FreeModuleElem{BigInt})
@ AbstractAlgebra ~/.julia/packages/AbstractAlgebra/yXuIT/src/ModuleHomomorphism.jl:157
[4] top-level scope
@ REPL[30]:1


Regarding your example, (u, v) and (u + v, u - v) do not generate the same \mathbf{Z}-submodule. The easiest way to see this is to note that the transformation matrix is

\begin{pmatrix} 1 & 1 \\ 1 & - 1 \end{pmatrix},

which has determinant -2 \not\in \mathbf{Z}^\times. The submodules will be the same over any ring, where 2 is invertible (including your fields of chracteristic \neq 2 that you mention).

As usual I will need some time to read it attentively before reacting.
So, see you soon on this thread.
Have a nice day.
Gilles

Ok ! understood !
I checked just to make sure but no (bad) surprise

using AbstractAlgebra

F = FreeModule(ZZ, 3)
@show F
v=F([1,2,3])
w=F([1,1,0])
S,f=sub(F,[v,w])
t=2v+5w
y=v+3w
S1,f1=sub(F,[t,y])
println(S==S1)


AA recognizes immediately that both submodules are the same, just because I took a transformation with determinant +1 (1 and -1 are the only iunits of ℤ )

My main mistake was to think that it was possible to invoke dimensional arguments with ℤ-modules. It’s due to inherited automatisms acquired with years of practise of vector spaces. Actually a sub ℤ-module can contain a sub-module of the same dimension different from itself. The straight line with vector director 2v is included in the straight line of v.d. v and is different.
Ignoring the warning of the documentation I tried to play with ℤ/pℤ residue fields just as íntegers;2 since we mention it.
AA agrees to build a module on such ring, but when it comes to build a submodule of it an error occur (something like gcdx no defined) which proves that the warning R euclidian ring should be taken into consideration (punishment happens very soon).
Finite additive groups can be considered as ℤ-modules of course finitely generated but never free…
So in practice, given that representations of fields such as ℝ and ℂ are not suited for abstract algebra where exact calculation is needed. the only valid representation proposed by AA consist in QQ-modules (vector spaces) and ZZ-modules (real modules).
So I will use this material for educational purpose and maybe illustrate the differences between vector spaces and more general modules with regards to submodules.
Thank you again for your help.
Gilles

Hm, you should try F = GF(p) if you want finite residue fields. If you do ResidueRing(ZZ, p), AA will not try to prove that it is a field, so will treat as a general commutative ring, which could even contain zero divisors (like ResidueRing(ZZ, 4)).