# Proof for subgroup -- How prove it is a subgroup of Z^m?

• I
• Peter_Newman
In summary: This implies the choice ##\mathbf{u}:=\mathbf{v}## which leads to ##\mathbf{0}=\mathbf{u-u}\in \Lambda_q(A).##Thanks for the fantastic answer!
Peter_Newman
Hi together!

Say we have ## \Lambda_q{(A)} = \{\mathbf{x} \in \mathbb{Z}^m: \mathbf{x} = A^T\mathbf{s} \text{ mod }q \text{ for some } \mathbf{s} \in \mathbb{Z}^n_q\} ##.

How can we proof that this is a subgroup of ##\mathbb{Z}^m## ?

For a sufficient proof we need to check, closure, identity, inverse.
1.) (closure): Say ##x,y \in \Lambda_q{(A)}## by definition both are elements of ##\mathbb{Z}^m##, we need to show ##x+y \in \mathbb{Z}^m##, but does this follow directly from the definition, or is there more to be shown here?
2.) (identity): The identity is given with the zero element 0, we need to show ##x + 0 = x##, let ##x,0 \in \Lambda_q{(A)}## then for ##x+ 0## we have ##x + 0 = A^T\mathbf{s} \text{ mod }q## rewriting ##(x \text{ mod }q + 0 \text{ mod }q ) \text{ mod }q = A^T\mathbf{s} \text{ mod }q ##, i used linearity to rewrite the expression, by assumption, there must be an ##s## for each case. And moreover ##0 \text{ mod }q = 0##, so that ##x = A^T\mathbf{s} \text{ mod }q## follows and ##x + 0 = x## is shown.
3.) For the inverse I have no idea yet how to show this, but it should be ##-x##.

Thanks for any help!

Last edited:
Peter_Newman said:
Say we have ## \Lambda_q{(A)} = \{\mathbf{x} \in \mathbb{Z}^m: \mathbf{x} = A^T\mathbf{s} \text{ mod }q \text{ for some } \mathbf{s} \in \mathbb{Z}^n_q\} ##.
How can we proof that this is a subgroup of ##\mathbb{Z}^m## ?
For a sufficient proof we need to check, closure, identity, inverse.
1.) (closure): Say ##x,y \in \Lambda_q{(A)}## by definition both are elements of ##\mathbb{Z}^m##, we need to show ##x+y \in \mathbb{Z}^m##, but does this follow directly from the definition, or is there more to be shown here?
More or less. Formally you have to show that with ##\mathbf{x}\, , \,\mathbf{y} \in \Lambda_q(A)## we have ##\mathbf{x+y} \in \Lambda_q(A)## which needs some explanation rather than "by definition"
\begin{align*}
\mathbf{x}\, , \,\mathbf{y} \in \Lambda_q(A) &\Longrightarrow \mathbf{x}\equiv A^T\mathbf{s}\pmod{q}\, , \,\mathbf{y}\equiv A^T\mathbf{t}\pmod{q}\\
&\Longrightarrow \mathbf{x+y}\equiv A^T\mathbf{s}+A^T\mathbf{t}\equiv A^T(\mathbf{s+t})\pmod{q}\\
&\Longrightarrow \mathbf{x+y}\in \Lambda_q(A)
\end{align*}
Peter_Newman said:
2.) (identity): The identity is given with the zero element 0, we need to show ##x + 0 = x##, let ##x,0 \in \Lambda_q{(A)}## then for ##x+ 0## we have ##x + 0 = A^T\mathbf{s} \text{ mod }q## rewriting ##(x \text{ mod }q + 0 \text{ mod }q ) \text{ mod }q = A^T\mathbf{s} \text{ mod }q ##, i used linearity to rewrite the expression, by assumption, there must be an ##s## for each case. And moreover ##0 \text{ mod }q = 0##, so that ##x = A^T\mathbf{s} \text{ mod }q## follows and ##x + 0 = x## is shown.
3.) For the inverse I have no idea yet how to show this, but it should be ##-x##.

Thanks for any help!
There is a common trick to do all at once in group theory. To show that ##U\leq G## is a subgroup, we only show that ##uv^{-1}\in U## for any ##u,v\in U.## This covers the identity with ##u=v##, then the inverse with ##u=e## and even closure with ##v^{-1}\rightarrow v.##

This means for additive groups ##u-v\in U## and in our case ##\mathbf{u-v} \in \Lambda_q(A)## which is done as above, only with a minus.

Peter_Newman

I think that's a helpful trick. If I wanted to show the identity, it would be ##\mathbf{u-u} \in \Lambda_q(A)##, right?

That might be a better approach than showing it with ##\mathbf{u} + \mathbf{0} = \mathbf{u}##.

Peter_Newman said:

I think that's a helpful trick. If I wanted to show the identity, it would be ##\mathbf{u-u} \in \Lambda_q(A)##, right?

That might be a better approach than showing it with ##\mathbf{u} + \mathbf{0} = \mathbf{u}##.
I'm not quite sure what you mean with ##\mathbf{u}-\mathbf{u}.##

We only show ##\mathbf{u-v}\in \Lambda_q(A).##

The point is:
As long as we do not impose any restrictions on ##\mathbf{u}## or ##\mathbf{v}## besides being in ##\Lambda_q(A)## we show ##\mathbf{u-v}\in \Lambda_q(A)## for all choices of these elements. If we have done this, we do not need to show ...

a) This implies the choice ##\mathbf{u}:=\mathbf{v}## which leads to ##\mathbf{0}=\mathbf{u-u}\in \Lambda_q(A).##
b) This implies the choice ##\mathbf{u}:=\mathbf{0}## which leads to ##\mathbf{-v}=\mathbf{0-v}\in \Lambda_q(A).##
c) This implies the choice ##\mathbf{v}:=(-\mathbf{v})## which leads to ##\mathbf{u+v}=\mathbf{u+(-(-v))}\in \Lambda_q(A).##

... because we have already done all at once.

Last edited:
Peter_Newman
This trick you mentioned, can you read about it somewhere. Do you perhaps have a reference? Just asked out of interest

Peter_Newman said:
This trick you mentioned, can you read about it somewhere. Do you perhaps have a reference? Just asked out of interest
https://en.wikipedia.org/wiki/Subgroup

But it should occur in any lecture notes about group theory. It is as the Wikipedia entry says ...
These two conditions can be combined into one, that for every ##a## and ##b## in ##H##, the element ##ab^{-1}## is in ##H##, but it is more natural and usually just as easy to test the two closure conditions separately.
... it is primarily a matter of convenience. It is a common deduction: prove the general result and apply it to specific examples.

Peter_Newman and malawi_glenn
fresh_42 said:
More or less. Formally you have to show that with ##\mathbf{x}\, , \,\mathbf{y} \in \Lambda_q(A)## we have ##\mathbf{x+y} \in \Lambda_q(A)## which needs some explanation rather than "by definition"
\begin{align*}
\mathbf{x}\, , \,\mathbf{y} \in \Lambda_q(A) &\Longrightarrow \mathbf{x}\equiv A^T\mathbf{s}\pmod{q}\, , \,\mathbf{y}\equiv A^T\mathbf{t}\pmod{q}\\
&\Longrightarrow \mathbf{x+y}\equiv A^T\mathbf{s}+A^T\mathbf{t}\equiv A^T(\mathbf{s+t})\pmod{q}\\
&\Longrightarrow \mathbf{x+y}\in \Lambda_q(A)
\end{align*}

There is a common trick to do all at once in group theory. To show that ##U\leq G## is a subgroup, we only show that ##uv^{-1}\in U## for any ##u,v\in U.## This covers the identity with ##u=v##, then the inverse with ##u=e## and even closure with ##v^{-1}\rightarrow v.##

This means for additive groups ##u-v\in U## and in our case ##\mathbf{u-v} \in \Lambda_q(A)## which is done as above, only with a minus.
There is a very important point missing, from the common trick. That the subset of the group we want to show is a subgroup, needs to also be nonempty.

fresh_42
Peter_Newman said:
This trick you mentioned, can you read about it somewhere. Do you perhaps have a reference? Just asked out of interest
I would google one-step and two-step subgroup test. Two different shortcuts.

The most common one, is what some authors call the Subgroup Criterion.

One further question:

When we have ##\Lambda_q{(A)} = \{\mathbf{x} \in \mathbb{Z}^m: \mathbf{x} = A^T\mathbf{s} \text{ mod }q \text{ for some } \mathbf{s} \in \mathbb{Z}^n_q\}## and ##A## is now the ##2 \times 2## identity matrix and ##q=5##. Then, what is ##\Lambda_q{(A)}##? Is this the full space ##\mathbf{Z}^2##?

Peter_Newman said:
One further question:

When we have ##\Lambda_q{(A)} = \{\mathbf{x} \in \mathbb{Z}^m: \mathbf{x} = A^T\mathbf{s} \text{ mod }q \text{ for some } \mathbf{s} \in \mathbb{Z}^n_q\}## and ##A## is now the ##2 \times 2## identity matrix and ##q=5##. Then, what is ##\Lambda_q{(A)}##? Is this the full space ##\mathbf{Z}^2##?
Let's see. You have defined
$$\Lambda_q{(A)} = \{\underbrace{\mathbf{x} \in \mathbb{Z}^m}_{=: \,S}: \underbrace{\mathbf{x} = A^T\mathbf{s} \text{ mod }q \text{ for some } \mathbf{s} \in \mathbb{Z}^n_q}_{=:\,C}\}$$
- lattice or not - by a set ##S## which we take the elements from (and note that ##\mathbb{Z}_q^m \not\subseteq \mathbb{Z}^m##), and a condition ##C## which restricts (or not) which elements are allowed. If ##A \pmod{q}\in \mathbb{M}(m,\mathbb{Z}_q)## is regular, then
$$\left\{A^T\boldsymbol s \pmod{q}\,|\,\boldsymbol s\in \mathbb{Z}_q^m\right\}=\left\{ s\pmod{q}\,|\,\boldsymbol s\in \mathbb{Z}_q^m\right\}=\left\{\boldsymbol s\in \mathbb{Z}_q^m\right\}=\mathbb{Z}_q^m$$
So ##\boldsymbol x## fulfills condition ##C## if and only if it is in ##\mathbb{Z}_q^m## and now we have
$$\Lambda_q{(A)}=\left\{\boldsymbol x \in \mathbb{Z}^m\,|\,\boldsymbol x \pmod{q} \in \mathbb{Z}_q^m\right\}=\mathbb{Z}^m$$
since every vector reduced to modulo ##q## transforms its coordinates from ##\mathbb{Z}## to ##\mathbb{Z}_q.##

Last edited:
Peter_Newman
Thank you @fresh_42 , the answer is really very instructive! Nice how you broke down the expression

Peter_Newman said:
Thank you @fresh_42 , the answer is really very instructive! Nice how you broke down the expression
To proceed step by step, notation by notation, definition by definition, and condition by condition won't let you prove Fermat's last theorem but will show you how to tackle a problem in many other cases.

Last edited:
Peter_Newman

• Linear and Abstract Algebra
Replies
4
Views
1K
• Linear and Abstract Algebra
Replies
52
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
1
Views
175
• Linear and Abstract Algebra
Replies
16
Views
1K
• Linear and Abstract Algebra
Replies
1
Views
1K
• Linear and Abstract Algebra
Replies
1
Views
1K
• Linear and Abstract Algebra
Replies
3
Views
2K
• Linear and Abstract Algebra
Replies
1
Views
957
• Linear and Abstract Algebra
Replies
4
Views
2K
• Linear and Abstract Algebra
Replies
1
Views
1K