Proof about two disjoint non-empty sets ## S ## and ## T ##

[Math100]

Homework Statement

The set $\left \{ 1, 2, ..., 22 \right \}$ is to be split into two disjoint non-empty sets $S$ and $T$ in such a way that:
(i) the product (mod $23$) of any two elements of $S$ lies in $S$;
(ii) the product (mod $23$) of any two elements of $T$ lies in $S$;
(iii) the product (mod $23$) of any element of $S$ and any element of $T$ lies in $T$.
Prove that the only solution is
$S=\left \{ 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18 \right \}$,
$T=\left \{ 5, 7, 10, 11, 14, 15, 17, 19, 20, 21, 22 \right \}$.

Relevant Equations

If $A$ and $B$ are disjoint, then their union $A\cup B$ contains $m+k=(p-1)/2$ integers in the interval $[1, (p-1)/2]$.

Proof:

Let $p$ be an odd prime and $G=\left \{ 1, 2, ..., p-1 \right \}$ be the set which can be expressed as the
union of two nonempty subsets $S$ and $T$ such that $S\neq T$.
Observe that $p-1=22\implies p=23$.
Let $g\in G$.
Since $g$ is either an element of $S$ or $T$, it follows that $g^{2}\in S$.
This implies that $S$ contains all quadratic residues modulo $23$.
Suppose for the sake of contradiction that there exists $x\in S$ for $(x|p)=-1$.
Note that there exists $y\in T$, so we have $(y|p)=-1$.
Thus $xy\in T$, but $(xy|p)=1$, which is a contradiction, so $S$ cannot contain any quadratic non-residues modulo $23$.
Therefore, the only solution is $S=\left \{ 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18 \right \}, T=\left \{ 5, 7, 10, 11, 14, 15, 17, 19, 20, 21, 22 \right \}$.

 

[fresh_42]

Homework Statement:: The set $\left \{ 1, 2, ..., 22 \right \}$ is to be split into two disjoint non-empty sets $S$ and $T$ in such a way that:
(i) the product (mod $23$) of any two elements of $S$ lies in $S$;
(ii) the product (mod $23$) of any two elements of $T$ lies in $S$;
(iii) the product (mod $23$) of any element of $S$ and any element of $T$ lies in $T$.
Prove that the only solution is
$S=\left \{ 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18 \right \}$,
$T=\left \{ 5, 7, 10, 11, 14, 15, 17, 19, 20, 21, 22 \right \}$.
Relevant Equations:: If $A$ and $B$ are disjoint, then their union $A\cup B$ contains ...

... $m+k=22$ numbers with $k\in [1,11]$ and $m\in [11,21].$

$m+k=(p-1)/2$ integers in the interval $[1, (p-1)/2]$.

Proof:

Let $p$ be an odd prime and $G=\left \{ 1, 2, ..., p-1 \right \}$ be the set which can be expressed as the
union of two nonempty subsets $S$ and $T$ such that $S\neq T$.
Observe that $p-1=22\implies p=23$.
Let $g\in G$.
Since $g$ is either an element of $S$ or $T$, it follows that $g^{2}\in S$.

No. This is the wrong way of conclusion. You have to show this after you have defined $S$.

The idea is as before:

We have a field $\mathbb{Z}_{23}$ with a multiplicative group $\mathbb{Z}_{23}^*=\{1,2,\ldots,22\}.$
We are looking for a split $\mathbb{Z}_{23}^*=S \cup T$ with $S,T\neq \emptyset$ and $S\cap T=\emptyset.$
Furthermore, $S$ has to be a multiplicative group: $S\cdot S\subseteq S\, , \,T\cdot T \subseteq S\, , \,T\cdot S\subseteq T.$

An assumption would be that $k=|S|=|T|=m=11$ and that $S$ contains all quadratic residues modulo $23$ and $T$ all quadratic non-residues. We already saw in a previous thread that there are equally many quadratic residues as there are quadratic non-residues in $\mathbb{Z}_{23}^*.$

\begin{align*}
S&:=\{a\in \mathbb{Z}_{23}^*\,|\,a\text{ is a quadratic residue modulo }23\}\\
T&:=\{a\in \mathbb{Z}_{23}^*\,|\,a\text{ is a quadratic non-residue modulo }23\}
\end{align*}
We now have two candidates. Given these two definitions, we must next prove that all properties of $S$ and $T$ are fulfilled.

This implies that $S$ contains all quadratic residues modulo $23$.

See above. The other way around. We set $S$ as this set and have to prove the properties.

$\left(\dfrac{a}{23}\right)=a^{11}\pmod{23}=1$ for quadratic residues:
\begin{matrix}
1^{11}\equiv 1\pmod{23}\, & \,2^{11}\equiv 1 \equiv \pmod{23}\, & \,3^{11}\equiv 1\pmod{23}\, & \,4^{11}\equiv 1\pmod{23}\\
6^{11}\equiv 1\pmod{23}\, & \,8^{11}\equiv 1 \equiv \pmod{23}\, & \,9^{11}\equiv 1\pmod{23}\, & \,12^{11}\equiv 1\pmod{23}\\
13^{11}\equiv 1\pmod{23}\, & \,16^{11}\equiv 1 \equiv \pmod{23}\, & \,18^{11}\equiv 1\pmod{23}\, &
\end{matrix}
Thus
\begin{align*}
S&=\left \{ 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18 \right \}\\
T&=\mathbb{Z}_{23}^*-S.
\end{align*}
We also have $S,T\neq \emptyset\, , \, S\cap T =\emptyset\, , \,S\cup T =\mathbb{Z}_{23}^*.$ From
$$
\left(\dfrac{a}{23}\right)\cdot \left(\dfrac{b}{23}\right)=\left(\dfrac{ab}{23}\right)\, , \,\left(\dfrac{a}{23}\right)=1\,(a\in S)\, , \,\left(\dfrac{a}{23}\right)=-1\,(a\in T)
$$
we get $S\cdot S\subseteq S\, , \,T\cdot T \subseteq S\, , \,T\cdot S\subseteq T.$

We finally need to show that this is the only possible decomposition of $\mathbb{Z}_{23}^*$ with the given properties. For that matter, we assume a second decomposition
$$
\mathbb{Z}_{23}^*=A\cup B\, , \,A \cap B=\emptyset\neq A,B\, , \,A\cdot A,B\cdot B\subseteq A,A\cdot B\subseteq B
$$
and show that $A=S.$ ($B=T$ follows automatically.)

Can you prove these two statements: $A=S$ and "automatically"?

 

[Math100]

... $m+k=22$ numbers with $k\in [1,11]$ and $m\in [11,21].$

No. This is the wrong way of conclusion. You have to show this after you have defined $S$.

The idea is as before:

We have a field $\mathbb{Z}_{23}$ with a multiplicative group $\mathbb{Z}_{23}^*=\{1,2,\ldots,22\}.$
We are looking for a split $\mathbb{Z}_{23}^*=S \cup T$ with $S,T\neq \emptyset$ and $S\cap T=\emptyset.$
Furthermore, $S$ has to be a multiplicative group: $S\cdot S\subseteq S\, , \,T\cdot T \subseteq S\, , \,T\cdot S\subseteq T.$

An assumption would be that $k=|S|=|T|=m=11$ and that $S$ contains all quadratic residues modulo $23$ and $T$ all quadratic non-residues. We already saw in a previous thread that there are equally many quadratic residues as there are quadratic non-residues in $\mathbb{Z}_{23}^*.$

\begin{align*}
S&:=\{a\in \mathbb{Z}_{23}^*\,|\,a\text{ is a quadratic residue modulo }23\}\\
T&:=\{a\in \mathbb{Z}_{23}^*\,|\,a\text{ is a quadratic non-residue modulo }23\}
\end{align*}
We now have two candidates. Given these two definitions, we must next prove that all properties of $S$ and $T$ are fulfilled.See above. The other way around. We set $S$ as this set and have to prove the properties.

$\left(\dfrac{a}{23}\right)=a^{11}\pmod{23}=1$ for quadratic residues:
\begin{matrix}
1^{11}\equiv 1\pmod{23}\, & \,2^{11}\equiv 1 \equiv \pmod{23}\, & \,3^{11}\equiv 1\pmod{23}\, & \,4^{11}\equiv 1\pmod{23}\\
6^{11}\equiv 1\pmod{23}\, & \,8^{11}\equiv 1 \equiv \pmod{23}\, & \,9^{11}\equiv 1\pmod{23}\, & \,12^{11}\equiv 1\pmod{23}\\
13^{11}\equiv 1\pmod{23}\, & \,16^{11}\equiv 1 \equiv \pmod{23}\, & \,18^{11}\equiv 1\pmod{23}\, &
\end{matrix}
Thus
\begin{align*}
S&=\left \{ 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18 \right \}\\
T&=\mathbb{Z}_{23}^*-S.
\end{align*}
We also have $S,T\neq \emptyset\, , \, S\cap T =\emptyset\, , \,S\cup T =\mathbb{Z}_{23}^*.$ From
$$
\left(\dfrac{a}{23}\right)\cdot \left(\dfrac{b}{23}\right)=\left(\dfrac{ab}{23}\right)\, , \,\left(\dfrac{a}{23}\right)=1\,(a\in S)\, , \,\left(\dfrac{a}{23}\right)=-1\,(a\in T)
$$
we get $S\cdot S\subseteq S\, , \,T\cdot T \subseteq S\, , \,T\cdot S\subseteq T.$

We finally need to show that this is the only possible decomposition of $\mathbb{Z}_{23}^*$ with the given properties. For that matter, we assume a second decomposition
$$
\mathbb{Z}_{23}^*=A\cup B\, , \,A \cap B=\emptyset\neq A,B\, , \,A\cdot A,B\cdot B\subseteq A,A\cdot B\subseteq B
$$
and show that $A=S.$ ($B=T$ follows automatically.)

Can you prove these two statements: $A=S$ and "automatically"?

Aren't the two statements of $A=S$ and $B=T$ ("automatically") the same as proving what's already proven from the first decomposition: $S\cdot S\subseteq S\, , \,T\cdot T \subseteq S\, , \,T\cdot S\subseteq T.$? What's different in the second decomposition from the first decomposition? Instead of $S$ and $T$, we have $A$ and $B$ now. Or is there another way to prove this?

 

[fresh_42]

Aren't the two statements of $A=S$ and $B=T$ ("automatically") the same as proving what's already proven from the first decomposition: $S\cdot S\subseteq S\, , \,T\cdot T \subseteq S\, , \,T\cdot S\subseteq T.$? What's different in the second decomposition from the first decomposition? Instead of $S$ and $T$, we have $A$ and $B$ now. Or is there another way to prove this?

If $A=S$ then $B=\mathbb{Z}_{23}^*-A=\mathbb{Z}_{23}^*-S=T.$

But $A=S$ is not automatically the case. E.g. $A$ could be all even numbers, and $B$ all odd numbers. We have to rule out that such a decomposition fulfills the properties. And we have to rule it out for any decomposition with the given properties.

The proof begins with:

Assume $G:=\mathbb{Z}_{23}^* =A\cup B$ with $A\cap B =\emptyset$ and $A,B\neq \emptyset$ and $A\cdot A \subseteq A\, , \,A\cdot B \subseteq B\, , \,B\cdot B\subseteq A.$

Since $A\subseteq G=S\cup T$ we have $A=S$ in which case we are done, $A\subset S$ or $A\not\subset S.$

Note that all elements of $G$ are invertible modulo $23.$ This means that for every $g\in G$ and every non-empty, proper subset $M\subset G$ holds $g\cdot M \subset G,$ i.e. $g\cdot M$ is also a non-empty proper subset of $G.$ In other words: left-multiplication in a (multiplicative) group is a bijection.

If $A\subset S$ then $B\not\subset T.$ There is thus a $b\in B$ that is not in $T,$ i.e. it is contained in $S.$ Thus $b\cdot B \subseteq A \subseteq S$ and $b\cdot A\subset S\cdot S\subseteq S.$ So $b\cdot G\subseteq S$ and $G\subseteq b^{-1}\cdot S \subset G$ which is a contradiction. This disproves $A\subseteq S.$

Assume $A\not\subset S.$ Then there is a $a\in A\cap T.$ If $A\subset T$ then $A\cdot A\subseteq A\subset T$ and $A\cdot A\subseteq T\cdot T\subseteq S$ which is not possible. Hence $A\cap T\neq \emptyset \neq A\cap S.$ But if $A$ intersects both, $S$ and $T$ non-trivially, so does $B.$

Hence we must rule out the following situation:

Can you do this?

 

[Math100]

If $A=S$ then $B=\mathbb{Z}_{23}^*-A=\mathbb{Z}_{23}^*-S=T.$

But $A=S$ is not automatically the case. E.g. $A$ could be all even numbers, and $B$ all odd numbers. We have to rule out that such a decomposition fulfills the properties. And we have to rule it out for any decomposition with the given properties.

The proof begins with:

Assume $G:=\mathbb{Z}_{23}^* =A\cup B$ with $A\cap B =\emptyset$ and $A,B\neq \emptyset$ and $A\cdot A \subseteq A\, , \,A\cdot B \subseteq B\, , \,B\cdot B\subseteq A.$

Since $A\subseteq G=S\cup T$ we have $A=S$ in which case we are done, $A\subset S$ or $A\not\subset S.$

Note that all elements of $G$ are invertible modulo $23.$ This means that for every $g\in G$ and every non-empty, proper subset $M\subset G$ holds $g\cdot M \subset G,$ i.e. $g\cdot M$ is also a non-empty proper subset of $G.$ In other words: left-multiplication in a (multiplicative) group is a bijection.

If $A\subset S$ then $B\not\subset T.$ There is thus a $b\in B$ that is not in $T,$ i.e. it is contained in $S.$ Thus $b\cdot B \subseteq A \subseteq S$ and $b\cdot A\subset S\cdot S\subseteq S.$ So $b\cdot G\subseteq S$ and $G\subseteq b^{-1}\cdot S \subset G$ which is a contradiction. This disproves $A\subseteq S.$

Assume $A\not\subset S.$ Then there is a $a\in A\cap T.$ If $A\subset T$ then $A\cdot A\subseteq A\subset T$ and $A\cdot A\subseteq T\cdot T\subseteq S$ which is not possible. Hence $A\cap T\neq \emptyset \neq A\cap S.$ But if $A$ intersects both, $S$ and $T$ non-trivially, so does $B.$

Hence we must rule out the following situation:
View attachment 317547

Can you do this?

So to rule out the following situation in which you listed above, one example would be $S\cap B=S$ if $B=S$?

 

[fresh_42]

$S=A\, , \,S=B\, , \,T=A\, , \,T=B$ are already ruled out. We must basically show that the principal character and the Legendre-symbol are the only two characters (multiplicative functions) with $\chi^2=1.$

The reason is that $\mathbb{Z}_{23}^*$ has $22=2 \cdot 11$ elements and there is only one normal subgroup of order two. That means such a case as in the picture cannot occur. But why exactly?

 

[Math100]

$S=A\, , \,S=B\, , \,T=A\, , \,T=B$ are already ruled out. We must basically show that the principal character and the Legendre-symbol are the only two characters (multiplicative functions) with $\chi^2=1.$

The reason is that $\mathbb{Z}_{23}^*$ has $22=2 \cdot 11$ elements and there is only one normal subgroup of order two. That means such a case as in the picture cannot occur. But why exactly?

I still don't really understand. Can you please tell me why?

 

[fresh_42]

I'm not sure whether the tools I would use are the tools you are expected to use. My plan would be to define
$$
\chi\, : \,\mathbb{Z}_{23}^*=:G \longrightarrow \mathbb{C}^*=\mathbb{C}-\{0\}\; , \;\chi(g)=\begin{cases}1&\text{ if }g\in A\\-1&\text{ if }g\in B\end{cases}
$$
Then
\begin{align*}
\chi(1)&=\chi(1\cdot 1)=\chi(1)\cdot \chi(1)\Longrightarrow \chi(1)=1\Longrightarrow 1\in A\\
\chi(gAg^{-1})&=\chi(g)\chi(A)\chi(g^{-1})=\chi(g)\cdot 1\cdot\chi(g^{-1})=\chi(g\cdot g^{-1})=\chi(1)=1
\end{align*}
This shows that $A=\operatorname{ker}\chi \trianglelefteq G$ is a normal subgroup. The order of any subgroup divides the order of the group. We have only two such prime divisors: $|G|=22=2\cdot 11.$ Hence $A$ has either $2$ or $11$ elements. Now $B\neq \emptyset$ so there is a $b\in B-\{1\}$ such that $b\cdot A \cup A=G.$ The mapping $a\longmapsto b\cdot a$ is a bijection since $b$ is invertible. So $bA$ and $A$ must have equally many elements. Thus, $|A|=11.$

The exact same considerations can be made for the Legendre symbol. So $1\in S.$ Thus we have an element $1\in S\,\cap \,A.$ So we have two normal subgroups $A\trianglelefteq G$ and $S\trianglelefteq G$ with equally many elements, namely $11$, that also share one element, namely $1\in G.$ But there is only one cyclic subgroup of $G$ with $11$ elements, $S=\mathbb{Z}_{11}.$ So $S=A$ and $T=B.$

If you aren't familiar with this basic group theory, then you have to find another way to make sure that there can't be two different partitions of $G=S\,\cup\,T=A\,\cup \,B.$

My idea: Look at $3$. Then either $3\in A$ or $3\in B.$ Rule out the latter and show that all powers of $3$ already generate $S.$

 

[fresh_42]

Forget that complicated stuff above; though it brought me the easier solution.

We have shown everything but uniqueness. We have $\mathbb{Z}_{23}^*=S\,\cup\,T$ partitioned in quadratic residues $S$ and quadratic non-residues $T$. Now, let us assume that there is another partition $\mathbb{Z}_{23}^*=A\,\cup\,B$ such that $A\cdot A ,B\cdot B \subseteq A, A\cdot B\subseteq B.$ Then $1=1\cdot 1\in A$ and $A\cdot A\subseteq A.$ Moreover, if $b\in B$ then $b\cdot A\subseteq B$ and $A\,\cup\,B= \mathbb{Z}_{23}^*$ because $A$ and $b\cdot A$ have equally many elements, i.e. $B=b\cdot A.$ To show that $A \trianglelefteq \mathbb{Z}_{23}^*$ is a subgroup, it remains to show that inverses of elements of $A$ are in $A$ again. Suppose $a^{-1}\in b\cdot A,$ i.e. $A\ni 1=a^{-1}\cdot a=b\cdot a'\cdot a \in B$ which is impossible since $A$ and $B$ are disjoint.
\begin{matrix}
3\cdot 3\equiv 9\pmod{23}&3\cdot 9\equiv 4\pmod{23}&3\cdot 4\equiv 12\pmod{23}&3\cdot 12\equiv 13\pmod{23}\\
3\cdot 13\equiv 16\pmod{23}&3\cdot 16\equiv 2\pmod{23}&3\cdot 2\equiv 6\pmod{23}&3\cdot 6\equiv 18\pmod{23}\\
3\cdot 18\equiv 8\pmod{23}&3\cdot 8\equiv 1\pmod{23}
\end{matrix}
If $3\in B$ then $3^{11}=1\in A\,\cup\,B$ which is impossible. So $\langle 3 \rangle \cong \mathbb{Z}_{11}\subseteq A\trianglelefteq \mathbb{Z}_{23}^*$ creates a cyclic subgroup with eleven elements: $\langle 3 \rangle=A=\{1,2,3,4,6,8,9,12,13,16,18\}=S.$

Sorry, the idea was finally shorter than the solution with all the technical details:

• $1\in A$
• $B=b\cdot A$
• $A^{-1}\subseteq A$
• $A\trianglelefteq \mathbb{Z}_{23}^*$ is a subgroup.
• $\mathbb{Z}_{23}^*=A \,\cup\,B$
• $3\in A$
• $\langle 3 \rangle = A = S$

 

[Math100]

Forget that complicated stuff above; though it brought me the easier solution.

We have shown everything but uniqueness. We have $\mathbb{Z}_{23}^*=S\,\cup\,T$ partitioned in quadratic residues $S$ and quadratic non-residues $T$. Now, let us assume that there is another partition $\mathbb{Z}_{23}^*=A\,\cup\,B$ such that $A\cdot A ,B\cdot B \subseteq A, A\cdot B\subseteq B.$ Then $1=1\cdot 1\in A$ and $A\cdot A\subseteq A.$ Moreover, if $b\in B$ then $b\cdot A\subseteq B$ and $A\,\cup\,B= \mathbb{Z}_{23}^*$ because $A$ and $b\cdot A$ have equally many elements, i.e. $B=b\cdot A.$ To show that $A \trianglelefteq \mathbb{Z}_{23}^*$ is a subgroup, it remains to show that inverses of elements of $A$ are in $A$ again. Suppose $a^{-1}\in b\cdot A,$ i.e. $A\ni 1=a^{-1}\cdot a=b\cdot a'\cdot a \in B$ which is impossible since $A$ and $B$ are disjoint.
\begin{matrix}
3\cdot 3\equiv 9\pmod{23}&3\cdot 9\equiv 4\pmod{23}&3\cdot 4\equiv 12\pmod{23}&3\cdot 12\equiv 13\pmod{23}\\
3\cdot 13\equiv 16\pmod{23}&3\cdot 16\equiv 2\pmod{23}&3\cdot 2\equiv 6\pmod{23}&3\cdot 6\equiv 18\pmod{23}\\
3\cdot 18\equiv 8\pmod{23}&3\cdot 8\equiv 1\pmod{23}
\end{matrix}
If $3\in B$ then $3^{11}=1\in A\,\cup\,B$ which is impossible. So $\langle 3 \rangle \cong \mathbb{Z}_{11}\subseteq A\trianglelefteq \mathbb{Z}_{23}^*$ creates a cyclic subgroup with eleven elements: $\langle 3 \rangle=A=\{1,2,3,4,6,8,9,12,13,16,18\}=S.$

Sorry, the idea was finally shorter than the solution with all the technical details:

• $1\in A$
• $B=b\cdot A$
• $A^{-1}\subseteq A$
• $A\trianglelefteq \mathbb{Z}_{23}^*$ is a subgroup.
• $\mathbb{Z}_{23}^*=A \,\cup\,B$
• $3\in A$
• $\langle 3 \rangle = A = S$

Don't say sorry, it's okay. I am the one who should apologize, because many stuffs above are things I never learned, I have no knowledge in group theory. So these are all new to me. For example, $A\trianglelefteq \mathbb{Z}_{23}^*$ is a subgroup, I've never seen $\trianglelefteq$ before. But it's always beneficial to know and learn the new stuffs.

 

[WWGD]

There seems to be too, a Combinatorial side to this. This may be call a matching or an SDR ( System of Distinct Representatives) .

 

[fresh_42]

Don't say sorry, it's okay. I am the one who should apologize, because many stuffs above are things I never learned, I have no knowledge in group theory. So these are all new to me. For example, $A\trianglelefteq \mathbb{Z}_{23}^*$ is a subgroup, I've never seen $\trianglelefteq$ before. But it's always beneficial to know and learn the new stuffs.

The point with the group is the following. I have observed that $S$ is equal to the set of all powers of, say $3$ modulo $23.$ If we have a second partition $G=A\,\cup\,B$ then $3$ is either an element of $A$ or an element of $B$. The powers of $3$ could hop between $A$ and $B$ all the time.

We show, that $A$ is a group, i.e. it contains the neutral element $1$, is closed under multiplication, i.e. $A\cdot A \subseteq A,$ a fact that is given by the properties of the partition and is closed under inversion $A^{-1}\subseteq A$ which has to be shown.

Then we show that $3\in A$. But now we know that $A$ is a group, so all powers of its elements are also within $A,$ no hopping between $A$ and $B$ allowed for powers of elements of $A$. Hence $\{3^n\pmod{23}\,|\,n\in \mathbb{N}\} = S \subseteq A.$

I think I have forgotten the final part. We know that $S\subseteq A$ but we need to show $A\subseteq S$ also. Assume that there is an element $a\in A$ which is not in $S.$ Then $a\in A\,\cup\,T$ and $a\cdot S\subseteq T.$ But $a\cdot S$ and $T$ have both $11$ elements, so $a\cdot S=T.$ Thus
$$
G=S\,\cup\,T=S\,\cup\,a\cdot S\subseteq A\,\cup\,a\cdot A\subseteq A
$$
which contradicts $B\neq \emptyset.$ There is therefore no element $a\in A-S,$ i.e. $A=S.$