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

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!
  • #1
Peter_Newman
155
11
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:
Physics news on Phys.org
  • #2
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.
 
  • Like
Likes Peter_Newman
  • #3
Thanks for the fantastic answer!

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}##.
 
  • #4
Peter_Newman said:
Thanks for the fantastic answer!

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:
  • Like
Likes Peter_Newman
  • #5
This trick you mentioned, can you read about it somewhere. Do you perhaps have a reference? Just asked out of interest :smile:
 
  • #6
Peter_Newman said:
This trick you mentioned, can you read about it somewhere. Do you perhaps have a reference? Just asked out of interest :smile:
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.
 
  • Like
Likes Peter_Newman and malawi_glenn
  • #7
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.
 
  • Like
Likes fresh_42
  • #8
Peter_Newman said:
This trick you mentioned, can you read about it somewhere. Do you perhaps have a reference? Just asked out of interest :smile:
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.
 
  • #9
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##?
 
  • #10
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:
  • Like
Likes Peter_Newman
  • #11
Thank you @fresh_42 , the answer is really very instructive! Nice how you broke down the expression :smile:
 
  • #12
Peter_Newman said:
Thank you @fresh_42 , the answer is really very instructive! Nice how you broke down the expression :smile:
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:
  • Like
Likes Peter_Newman

Similar threads

Replies
1
Views
2K
Replies
13
Views
2K
Replies
52
Views
3K
Replies
1
Views
1K
Replies
16
Views
2K
Replies
7
Views
2K
Back
Top