2
$\begingroup$

This question is a sentence in a quantum information paper, I was assuming the proof is easy...but I had a hard time on proving one of the directions. Maybe I am overlooking some very basic fact...Here is the question:

Let $h_1,\ldots,h_r,g$ be commuting elements of an arbitrary group $G$, with order $s_1,\ldots,s_r,s$ respectively. Define $\phi:\mathbb{Z}_{s_1}\times \cdots\times \mathbb{Z}_{s_r}\times \mathbb{Z}_s\to G$ such that $$\phi(\alpha_1,\ldots,\alpha_r,\alpha)=h_1^{\alpha_1}\ldots h_r^{\alpha_r}g^{-\alpha}.$$ Let $(\alpha_1,\ldots,\alpha_r,\alpha)$ be in the kernel of $\phi$. Then $\alpha$ and $s$ are co-primes if and only if $g$ is representable as a product of power of $h_i$'s. I am ok with .. if co-prime, then.. part, but not quite sure how to proceed the converse direction part.

EDITED: Just to make sure I didn't misunderstand anything, I also attached a screenshot of the paper.

Could someone help me, thanks!

enter image description here

and the task (b) is so called constructive membership test, which is the following:

enter image description here

$\endgroup$
8
  • 1
    $\begingroup$ The statement is false. You always have $(0,0,\ldots,0,s)$ in the kernel, regardless of whether $g$ can be written as a product of the $h_i$ or not; here, $\alpha=s$, which is not relatively prime to $s$. $\endgroup$ Commented Oct 19, 2019 at 21:12
  • 1
    $\begingroup$ On the other hand, if we assume the $\alpha$ is the smallest positive integer such that there exist $\alpha_1,\ldots,\alpha_r$ with $(\alpha_1,\ldots,\alpha_r,\alpha)$ in the kernel, then the assertion does hold. $\endgroup$ Commented Oct 19, 2019 at 21:13
  • $\begingroup$ Hi @ArturoMagidin, thanks for the comment, and sorry for the late reply. Yes, I agree with you with your first comment. Could you help me to elaborate your second comment? Thanks $\endgroup$ Commented Oct 20, 2019 at 16:34
  • $\begingroup$ @ArturoMagidin Also...I guess as $\alpha\in\mathbb{Z}_s$, we don't "really" have $\alpha=s$... $\endgroup$ Commented Oct 20, 2019 at 18:01
  • $\begingroup$ Doesn’t matter: you still have $(0,0,\ldots,0)$ in the kernel, where $\alpha=0$, and that happens no matter whether $g$ is equal to a power of the $h$s or not (and $\gcd(0,s)=s\neq 1$ if $s\neq 1$). There are extra assumptions in there that are not being stated. $\endgroup$ Commented Oct 20, 2019 at 18:35

1 Answer 1

Reset to default
1
$\begingroup$

With the screenshots it is clear where the error lies: you have misinterpreted/misrepresented the claim in the paper, and are thus trying to prove a false statement.

Namely, what the paper asserts is:

There exists an element of the kernel with last coordinate relatively prime to $s$ if and only if $g$ can be expressed as a product of the $h$s.

What you are trying to prove (which is false) is:

If $\mathbf{x}$ is in the kernel, then the last coordinate of $\mathbf{x}$ is relatively prime to $s$ if and only if $g$ can be expressed as a product of the $h$s.

They are different statements; in one direction, the former statement is an existential statement about elements in the kernel with desired properties, whereas what you have attempted to prove is a universal statement about such elements. The paper asserts that when $g$ can be expressed as a product of the $h$s, then there exist elements in the kernel with last coordinate relatively prime to $s$. What you have are trying to prove is that if $g$ can be expressed as a product of the $h$s, then an arbitrary element of the kernel (and hence, that every element of the kernel) will necessarily have last coordinate relatively prime to $s$. And that statement is false.

Simply: if $g$ can be expressed as a product of the $h_i$, $g=h_1^{a_1}\cdots h_r^{a_r}$, then $(a_1,\ldots,a_r,1)$ lies in the kernel, and the last coordinate, $1$, is relatively prime to $s$. Conversely, if you can find an element in the kernel with last coordinate relatively prime to $s$, say $(b_1,\ldots,b_r,\alpha)$, then find $x,y\in\mathbb{Z}$ such that $x\alpha + ys = 1$. Then $(xb_1,\ldots,xb_r,x\alpha)$ lies in the kernel, which yields $$\begin{align*} h_1^{xb_1}\cdots h_r^{xb_r}g^{-x\alpha} &= 1\\ h_1^{xb_1}\cdots h_r^{xb_r}&= g^{x\alpha}\\ h_1^{xb_1}\cdots h_r^{xb_r}&= g^{x\alpha}(g^s)^y\\ h_1^{xb_1}\cdots h_r^{xb_r}&= g^{x\alpha+sy}\\ h_1^{xb_1}\cdots h_r^{xb_r}&= g, \end{align*}$$ so $g$ can be expressed as a product of the $h$s.

A counterexample to the claim you stated is given with $r=1$, $s=s_1=4$, and $g=h_1$. Then $g$ can be expressed as a product of the $h$s, but the kernel is equal to $(0,0)$, $(1,1)$, $(2,2)$, and $(3,3)$; and while there are elements in the kernel with last coordinate relatively prime to $4$, not every element of the kernel has last coordinate relatively prime to $4$, even if we restrict to non-trivial elements.

$\endgroup$
1
  • $\begingroup$ Ah! How stupid I am! Thanks! $\endgroup$ Commented Oct 21, 2019 at 1:40

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.