Anki Deck Changes

Note 1: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: C}sy0oyJ5m

modified

Before

Front

Lemma about uniqueness of the inverse:

Back

Lemma about uniqueness of the inverse:

Lemma 5.2: In a monoid $\langle M; *, e \rangle$, if $a \in M$ has a left inverse and a right inverse, then they are equal. In particular, $a$ has at most one inverse.

After

Front

Lemma about uniqueness of the inverse:

Back

Lemma about uniqueness of the inverse:

Lemma 5.2: In a monoid $\langle M; *, e \rangle$, if $a \in M$ has a left inverse and a right inverse, then they are equal. In particular, $a$ has at most one inverse.

Proof: $L$ left inverse, $R$ right inverse.

$L = L * e = L * (a * R) $ $= (L * a) * R = e * R = R$

Field-by-field Comparison

Field	Before	After
Back	<p><strong>Lemma 5.2</strong>: In a monoid $\langle M; *, e \rangle$, if $a \in M$ has a left inverse and a right inverse, then they are <strong>equal</strong>. In particular, $a$ has <strong>at most one inverse</strong>.</p>	<p><strong>Lemma 5.2</strong>: In a monoid $\langle M; , e \rangle$, if $a \in M$ has a left inverse and a right inverse, then they are <strong>equal</strong>. In particular, $a$ has <strong>at most one inverse</strong>.</p><p><b>Proof: </b>$L$ left inverse, $R$ right inverse.</p><p>$L = L e = L * (a * R) $ $= (L * a) * R = e * R = R$</p>

Tags: ETH::1._Semester::DiskMat::5._Algebra::2._Monoids_and_Groups::3._Inverses_and_Groups

Note 2: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: M035/^ZEJ$

modified

Before

Front

What is the number of subgroups of $\mathbb{Z}_n$?

Back

What is the number of subgroups of $\mathbb{Z}_n$?

The number of divisors of $n$ (as the order of each subgroup divides the group order (which is n here) by Lagrange).

If $n$ is written $n = p_1^{e_1} \times p_2^{e_2} \times ... \times p_k^{e_k}$ then it is $\prod_{i=1}^k (e_i+1)$

After

Front

What is the number of subgroups of $\mathbb{Z}_n$?

Back

What is the number of subgroups of $\mathbb{Z}_n$?

it is the number of divisors of $n$ (as the order of each subgroup divides the group order (which is n here) by Lagrange).
if $n$ is written $n = p_1^{e_1} \times p_2^{e_2} \times ... \times p_k^{e_k}$ then it is $\prod_{i=1}^k (e_i+1)$

Note: This only holds because $\mathbb{Z}_n$ is cyclic and therefore the subgroups are unique.

Field-by-field Comparison

Field	Before	After
Back	The number of divisors of $n$ (as the order of each subgroup divides the group order (which is n here) by Lagrange). <br>~~<br>I~~f $n$ is written $n = p_1^{e_1} \times p_2^{e_2} \times ... \times p_k^{e_k}$ then it is $\prod_{i=1}^k (e_i+1)$	it is the number of divisors of $n$ (as the order of each subgroup divides the group order (which is n here) by Lagrange). <br>if $n$ is written $n = p_1^{e_1} \times p_2^{e_2} \times ... \times p_k^{e_k}$ then it is $\prod_{i=1}^k (e_i+1)$<br><br><i>Note:</i> This only holds because $\mathbb{Z}_n$ is cyclic and therefore the subgroups are unique.

Tags: ETH::1._Semester::DiskMat::5._Algebra::3._The_Structure_of_Groups::5._Cyclic_Groups

Note 3: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: eApiqwS~J~

modified

Before

Front

State the Chinese Remainder Theorem (Theorem 4.19).

Back

State the Chinese Remainder Theorem (Theorem 4.19).

Let $m_1, m_2, \dots, m_r$ be pairwise relatively prime integers and let $M = \prod_{i=1}^{r} m_i$. For every list $a_1, \dots, a_r$ with $0 \leq a_i < m_i$, the system \[\begin{align} x &\equiv_{m_1} a_1 \\ x &\equiv_{m_2} a_2 \\ &\vdots \\ x &\equiv_{m_r} a_r \end{align}\] has a unique solution $x$ satisfying $0 \leq x < M$.

After

Front

State the Chinese Remainder Theorem (Theorem 4.19).

Back

State the Chinese Remainder Theorem (Theorem 4.19).

Let $m_1, m_2, \dots, m_r$ be pairwise relatively prime integers and let $M = \prod_{i=1}^{r} m_i$. For every list $a_1, \dots, a_r$ with $0 \leq a_i < m_i$, the system \[\begin{align} x &\equiv_{m_1} a_1 \\ x &\equiv_{m_2} a_2 \\ &\vdots \\ x &\equiv_{m_r} a_r \end{align}\] has a unique solution $x$ satisfying $0 \leq x < M$.

Why unique:
If there are two solutions, then, for all $i$:
$x \equiv_{m_i} a_i$ and $x' \equiv_{m_i} a_i$
$\implies m_i \mid( x - x_i)$
$\implies$$\sum_i m_i \mid (x-x_i)$ b/c $m_i$ are coprime
$\implies$any two solutions differ by a multiple of $M$

Field-by-field Comparison

Field	Before	After
Back	Let $m_1, m_2, \dots, m_r$ be <~~strong~~>pairwise relatively prime</~~strong~~> integers and let $M = \prod_{i=1}^{r} m_i$. For every list $a_1, \dots, a_r$ with $0 \leq a_i < m_i$, the system \[\begin{align} x &\equiv_{m_1} a_1 \\ x &\equiv_{m_2} a_2 \\ &\vdots \\ x &\equiv_{m_r} a_r \end{align}\] has a <~~strong~~>unique solution</~~strong~~> $x$ satisfying $0 \leq x < M$.	Let $m_1, m_2, \dots, m_r$ be <b>pairwise relatively prime</b> integers and let $M = \prod_{i=1}^{r} m_i$. For every list $a_1, \dots, a_r$ with $0 \leq a_i < m_i$, the system \[\begin{align} x &\equiv_{m_1} a_1 \\ x &\equiv_{m_2} a_2 \\ &\vdots \\ x &\equiv_{m_r} a_r \end{align}\] has a <b>unique solution</b> $x$ satisfying $0 \leq x < M$.<br><br><b>Why unique:</b> <br>If there are two solutions, then, for all $i$:<br>$x \equiv_{m_i} a_i$ and $x' \equiv_{m_i} a_i$ <br>$\implies m_i \mid( x - x_i)$<br>$\implies$$\sum_i m_i \mid (x-x_i)$ b/c $m_i$ are coprime<br>$\implies$any two solutions differ by a multiple of $M$ <br>

Tags: ETH::1._Semester::DiskMat::4._Number_Theory::5._Congruences_and_Modular_Arithmetic::4._The_Chinese_Remainder_Theorem

Note 4: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: gg+,r$i,o

modified

Before

Front

For what $m$ is $\mathbb{Z}^*_m$ cyclic? (Theorem 5.15)

Back

For what $m$ is $\mathbb{Z}^*_m$ cyclic? (Theorem 5.15)

The group ℤ*_m is cyclic if and only if:
• $m = 2$
• $m = 4$
• $m = p^e$ (where p is an odd prime and $e ≥ 1$)
• $m = 2p^e$ (where p is an odd prime and $e ≥ 1$) Example: Is $\mathbb{Z}^*_{19}$ cyclic? What is a generator? Yes, $\mathbb{Z}^*_{19}$ is cyclic (since $19$ is an odd prime).

2 is a generator.

Powers of 2: 2, 4, 8, 16, 13, 7, 14, 9, 18, 17, 15, 11, 3, 6, 12, 5, 10, 1

Other generators: 3, 10, 13, 14, 15

After

Front

For what $m$ is $\mathbb{Z}^*_m$ cyclic? (Theorem 5.15)

Back

For what $m$ is $\mathbb{Z}^*_m$ cyclic? (Theorem 5.15)

The group $\mathbb{Z}^*_m$ is cyclic if and only if:
• $m = 2$
• $m = 4$
• $m = p^e$ (where p is an odd prime and $e ≥ 1$)
• $m = 2p^e$ (where p is an odd prime and $e ≥ 1$)

Example: Is $\mathbb{Z}^*_{19}$ cyclic? What is a generator? Yes, $\mathbb{Z}^*_{19}$ is cyclic (since $19$ is an odd prime).

2 is a generator.
Powers of 2: 2, 4, 8, 16, 13, 7, 14, 9, 18, 17, 15, 11, 3, 6, 12, 5, 10, 1
Other generators: 3, 10, 13, 14, 15

Why it doesn't contradict that very group of prime order is cyclic, with every element except the neutral element being a generator: $\{2\} \cup [\text{all odd primes}]$

$= [\text{all primes}]$

Field-by-field Comparison

Field	Before	After
Back	The group ~~ℤ_m~~ is cyclic if and only if:<br>• $m = 2$<br>• $m = 4$<br>• $m = p^e$ (where p is an odd prime and $e ≥ 1$)<br>• $m = 2p^e$ (where p is an odd prime and $e ≥ 1$) Example: Is $\mathbb{Z}^_{19}$ cyclic? What is a generator? Yes, $\mathbb{Z}^*_{19}$ is cyclic (since $19$ is an odd prime).<br><br>2 is a generator.<~~br><br~~>Powers of 2: 2, 4, 8, 16, 13, 7, 14, 9, 18, 17, 15, 11, 3, 6, 12, 5, 10, 1<~~br><br~~>Other generators: 3, 10, 13, 14, 15	The group $\mathbb{Z}^_m$ is cyclic if and only if:<br>• $m = 2$<br>• $m = 4$<br>• $m = p^e$ (where p is an odd prime and $e ≥ 1$)<br>• $m = 2p^e$ (where p is an odd prime and $e ≥ 1$) <br><br><b>Example:</b> Is $\mathbb{Z}^_{19}$ cyclic? What is a generator? Yes, $\mathbb{Z}^*_{19}$ is cyclic (since $19$ is an odd prime). <br><ul><li>2 is a generator.</li><li>Powers of 2: 2, 4, 8, 16, 13, 7, 14, 9, 18, 17, 15, 11, 3, 6, 12, 5, 10, 1</li><li>Other generators: 3, 10, 13, 14, 15</li></ul><div><b>Why it doesn't contradict </b>that <span style="color: rgb(51, 51, 51);">very group of </span>prime order<span style="color: rgb(51, 51, 51);"> is cyclic, with </span>every element except the neutral element being a generator<font color="#333333">: </font>$\{2\} \cup [\text{all odd primes}]$</div>$= [\text{all primes}]$<div><br></div>

Tags: ETH::1._Semester::DiskMat::5._Algebra::3._The_Structure_of_Groups::8._The_Group_Zₘ*_and_Euler's_Function

Note 5: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID: h:Z}faoBcQ

modified

Before

Front

We can reduce the exponent $a^m$ modulo $n$ by {{c1::the $\text{ord}(a)$}} iff. $\gcd(a, n) = 1$, i.e. $a$ and $n$ are coprime.

Back

We can reduce the exponent $a^m$ modulo $n$ by {{c1::the $\text{ord}(a)$}} iff. $\gcd(a, n) = 1$, i.e. $a$ and $n$ are coprime.

$(a^{\operatorname{ord}(a)})^q \cdot a^r \equiv_n a^r$

This is because if $\gcd(a, n) = 1$ then there exists an $m$ for which $a^m = e$ (same as mult. inverse since $a^{m-1}$ is the inverse. Every $a$ w/ $\gcd(a, n) = 1$ has a real order b/c it generates the entire group and therefore also the mult. inverse).

After

Front

We can reduce the exponent $a^m$ modulo $n$ by {{c1::the $\text{ord}(a)$}} iff. $\gcd(a, n) = 1$, i.e. $a$ and $n$ are coprime.

Back

We can reduce the exponent $a^m$ modulo $n$ by {{c1::the $\text{ord}(a)$}} iff. $\gcd(a, n) = 1$, i.e. $a$ and $n$ are coprime.

$(a^{\operatorname{ord}(a)})^q \cdot a^r \equiv_n a^r$

This is because if $\gcd(a, n) = 1$ then there exists an $m$ for which $a^m = e$ (same as for the mult. inverse since $a^{m-1}$ is the inverse).

Field-by-field Comparison

Field	Before	After
Extra	$(a^{\operatorname{ord}(a)})^q \cdot a^r \equiv_n a^r$<br><br>This is because if $\gcd(a, n) = 1$ then there exists an $m$ for which $a^m = e$ (same as mult. inverse since $a^{m-1}$ <i>is</i> the ~~inverse. Every $a$ w/ $\gcd(a, n) = 1$ has a real order b/c it generates the entire group and therefore also the mult.~~ inverse).	$(a^{\operatorname{ord}(a)})^q \cdot a^r \equiv_n a^r$<br><br>This is because if $\gcd(a, n) = 1$ then there exists an $m$ for which $a^m = e$ (same as for the mult. inverse since $a^{m-1}$ <i>is</i> the inverse).

Tags: ETH::1._Semester::DiskMat::5._Algebra::3._The_Structure_of_Groups::5._Cyclic_Groups

Note 6: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID: np*2077JVj

modified

Before

Front

The minimum distance of an error-correcting code $\mathcal{C}$, denoted $d_{\min}(\mathcal{C})$, is the minimum of the Hamming distance between any two codewords.

Back

The minimum distance of an error-correcting code $\mathcal{C}$, denoted $d_{\min}(\mathcal{C})$, is the minimum of the Hamming distance between any two codewords.

After

Front

The minimum distance of an error-correcting code $\mathcal{C}$, denoted $d_{\min}(\mathcal{C})$, is the minimum Hamming distance between any two codewords.

Back

The minimum distance of an error-correcting code $\mathcal{C}$, denoted $d_{\min}(\mathcal{C})$, is the minimum Hamming distance between any two codewords.

Field-by-field Comparison

Field	Before	After
Text	<p>The minimum distance of an error-correcting code $\mathcal{C}$, denoted $d_{\min}(\mathcal{C})$, is the {{c3::minimum ~~of the~~ Hamming distance}} between any two codewords.</p>	<p>The minimum distance of an error-correcting code $\mathcal{C}$, denoted $d_{\min}(\mathcal{C})$, is the {{c3::minimum Hamming distance}} between any two codewords.</p>

Tags: ETH::1._Semester::DiskMat::5._Algebra::9._Application:_Error-Correcting_Codes::1._Definition_of_Error-Correcting_Codes

Note 7: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: o)+^3Q.5-H

modified

Before

Front

When does an irreducible polynomial exist in $\text{GF}(p)[x]$?

Back

When does an irreducible polynomial exist in $\text{GF}(p)[x]$?

For every prime $p$ and every $d > 1$, there exists an irreducible polynomial of degree $d$ in $\text{GF}(p)[x]$.

In particular, there exists a finite field with $p^d$ elements.

After

Front

When does an irreducible polynomial exist in $\text{GF}(p)[x]$?

Back

When does an irreducible polynomial exist in $\text{GF}(p)[x]$?

For every prime $p$ and every $d > 1$, there exists an irreducible polynomial of degree $d$ in $\text{GF}(p)[x]$.

Result: we can construct a finite field with $p^d$ elements by using an irreducible polynomial of degree $d$ to cap the number of coefficients at $d$

Field-by-field Comparison

Field	Before	After
Back	<p>For every prime $p$ and every $d > 1$, there exists an <strong>irreducible polynomial</strong> of degree $d$ in $\text{GF}(p)[x]$.</p> <p>~~In particular, there exists~~ a <strong>finite field</strong> with $p^d$ elements.</p>	<p>For every prime $p$ and every $d > 1$, there exists an <strong>irreducible polynomial</strong> of degree $d$ in $\text{GF}(p)[x]$.</p> <p><b>Result:</b> we can construct a <strong>finite field</strong> with $p^d$ elements by using an irreducible polynomial of degree $d$ to cap the number of coefficients at $d$</p>

Tags: ETH::1._Semester::DiskMat::5._Algebra::8._Finite_Fields::3._Some_Facts_About_Finite_Fields_*

Note 8: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: u%LA!tL]Sb

modified

Before

Front

What is a polynomial based encoding function?

Back

What is a polynomial based encoding function?

Theorem 5.42: Let $\mathcal{A} = \text{GF}(q)$ and let $\alpha_0, \dots, \alpha_{n-1}$ be arbitrary distinct elements of $\text{GF}(q)$. Encode by polynomial evaluation: \[E((a_0, \dots, a_{k-1})) = (a(\alpha_0), \dots, a(\alpha_{n-1}))\] where $a(x)$ is the polynomial with coefficients $(a_0, \dots, a_{k-1})$.

The code has minimum distance $d_{\min} = n - k + 1$.

Key property: The polynomial can be interpolated from any $k$ values by Lagrangian interpolation. Two codewords cannot agree at $k$ positions (else they'd be equal), so they disagree in at least $n - k + 1$ positions.

After

Front

What is a polynomial based encoding function?

Back

What is a polynomial based encoding function?

Theorem 5.42: Let $\mathcal{A} = \text{GF}(q)$ and let $\alpha_0, \dots, \alpha_{n-1}$ be arbitrary distinct elements of $\text{GF}(q)$. Encode by polynomial evaluation: \[E((a_0, \dots, a_{k-1})) = (a(\alpha_0), \dots, a(\alpha_{n-1}))\] where $a(x)$ is the polynomial with coefficients $(a_0, \dots, a_{k-1})$.

The code has minimum distance $d_{\min} = n - k + 1$.

Key property: The polynomial can be interpolated from any $k$ values by Lagrangian interpolation (b/c $k$ coefficients = degree $k-1$ due to the constant part of the polynomial). Two codewords cannot agree at $k$ positions (else they'd be equal), i.e. they agree at most at $k-1$ positions, so they disagree in at least $n - k + 1$ positions.

Field-by-field Comparison

Field	Before	After
Back	<p><strong>Theorem 5.42</strong>: Let $\mathcal{A} = \text{GF}(q)$ and let $\alpha_0, \dots, \alpha_{n-1}$ be arbitrary distinct elements of $\text{GF}(q)$. Encode by polynomial evaluation: \[E((a_0, \dots, a_{k-1})) = (a(\alpha_0), \dots, a(\alpha_{n-1}))\] where $a(x)$ is the polynomial with coefficients $(a_0, \dots, a_{k-1})$.</p> <p>The code has minimum distance $d_{\min} = n - k + 1$.</p> <p><strong>Key property</strong>: The polynomial can be interpolated from any $k$ values by Lagrangian interpolation. Two codewords cannot agree at $k$ positions (else they'd be equal), so they disagree in at least $n - k + 1$ positions.</p>	<p><strong>Theorem 5.42</strong>: Let $\mathcal{A} = \text{GF}(q)$ and let $\alpha_0, \dots, \alpha_{n-1}$ be arbitrary distinct elements of $\text{GF}(q)$. Encode by polynomial evaluation: \[E((a_0, \dots, a_{k-1})) = (a(\alpha_0), \dots, a(\alpha_{n-1}))\] where $a(x)$ is the polynomial with coefficients $(a_0, \dots, a_{k-1})$.</p> <p>The code has minimum distance $d_{\min} = n - k + 1$.</p> <p><strong>Key property</strong>: The polynomial can be interpolated from any $k$ values by Lagrangian interpolation (b/c $k$ coefficients = degree $k-1$ due to the constant part of the polynomial). Two codewords cannot agree at $k$ positions (else they'd be equal), i.e. they agree at most at $k-1$ positions, so they disagree in at least $n - k + 1$ positions.</p>

Tags: ETH::1._Semester::DiskMat::5._Algebra::9._Application:_Error-Correcting_Codes::3._Codes_based_on_Polynomial_Evaluation

Note 9: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: u7I279IY#p

modified

Before

Front

When is there a finite field with $q$ elements?

Back

When is there a finite field with $q$ elements?

$\text{GF}(q)$ is only finite if and only if $q$ is a power of a prime, i.e. $q = p^k$ for $p$ prime.

Any two fields of the same size $q$ are isomorphic.

After

Front

When is there a finite field with $q$ elements?

Back

When is there a finite field with $q$ elements?

$\text{GF}(q)$ is only finite if and only if $q$ is a power of a prime, i.e. $q = p^k$ for $p$ prime.

Any two fields of the same size $q$ are isomorphic.

Why: to construct an extension field, use $\mathbb{Z}_p$ for coefficients. To be a field, $p$ must be prime. In a polynomial with degree $k-1$, each coefficient can take any of the $p$ values from the coefficient field.

Field-by-field Comparison

Field	Before	After
Back	<p>$\text{GF}(q)$ is only finite <em>if and only if</em> $q$ is a <em>power</em> of a prime, i.e. $q = p^k$ for $p$ prime.</p> <p>Any two fields of the same size $q$ are isomorphic.</p>	<p>$\text{GF}(q)$ is only finite <em>if and only if</em> $q$ is a <em>power</em> of a prime, i.e. $q = p^k$ for $p$ prime.</p> <p>Any two fields of the same size $q$ are isomorphic.</p><p><br></p><p><b>Why:</b> to construct an extension field, use $\mathbb{Z}_p$ for coefficients. To be a field, $p$ must be prime. In a polynomial with degree $k-1$, each coefficient can take any of the $p$ values from the coefficient field.</p>

Tags: ETH::1._Semester::DiskMat::5._Algebra::8._Finite_Fields::3._Some_Facts_About_Finite_Fields_*