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

[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!

 

[fresh_42]

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*}

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]

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}$.

 

[fresh_42]

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.

 

[Peter_Newman]

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

 

[fresh_42]

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.

 

[MidgetDwarf]

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.

 

[MidgetDwarf]

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.

 

[Peter_Newman]

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$?

 

[fresh_42]

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.$

 

[Peter_Newman]

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

 

[fresh_42]

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.