高级算法 (Fall 2021)/Finite Field Basics and 高级算法 (Fall 2021)/Problem Set 4: Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
imported>Etone
(Created page with "=Field= Let <math>S</math> be a set, '''closed''' under binary operations <math>+</math> (addition) and <math>\cdot</math> (multiplication). It gives us the following algebrai...")
 
imported>TCSseminar
 
Line 1: Line 1:
=Field=
*每道题目的解答都要有<font color="red" size=5>完整的解题过程</font>。中英文不限。
Let <math>S</math> be a set, '''closed''' under binary operations <math>+</math> (addition) and <math>\cdot</math> (multiplication). It gives us the following algebraic structures if the corresponding set of axioms are satisfied.
{|class="wikitable"
!colspan="7"|Structures
!Axioms
!Operations
|-
|rowspan="9" style="background-color:#ffffcc;text-align:center;"|'''''field'''''
|rowspan="8" style="background-color:#ffffcc;text-align:center;"|'''''commutative<br>ring'''''
|rowspan="7" style="background-color:#ffffcc;text-align:center;"|'''''ring'''''
|rowspan="4" style="background-color:#ffffcc;text-align:center;"|'''''abelian<br>group'''''
|rowspan="3" style="background-color:#ffffcc;text-align:center;"|'''''group'''''
| rowspan="2" style="background-color:#ffffcc;text-align:center;"|'''''monoid'''''
|style="background-color:#ffffcc;text-align:center;"|'''''semigroup'''''
|1. '''Addition''' is '''associative''': <math>\forall x,y,z\in S, (x+y)+z= x+(y+z).</math>
|rowspan="4" style="text-align:center;"|<math>+</math>
|-
|
|2. Existence of '''additive identity 0''': <math>\forall x\in S, x+0= 0+x=x.</math>
|-
|colspan="2"|
|3. Everyone has an '''additive inverse''': <math>\forall x\in S, \exists -x\in S, \text{ s.t. } x+(-x)= (-x)+x=0.</math>
|-
|colspan="3"|
|4. '''Addition''' is '''commutative''': <math>\forall x,y\in S, x+y= y+x.</math>
|-
|colspan="4" rowspan="3"|
|5. Multiplication '''distributes''' over addition: <math>\forall x,y,z\in S, x\cdot(y+z)= x\cdot y+x\cdot z</math> and <math>(y+z)\cdot x= y\cdot x+z\cdot x.</math>
|style="text-align:center;"|<math>+,\cdot</math>
|-
|6. '''Multiplication''' is '''associative''': <math>\forall x,y,z\in S, (x\cdot y)\cdot z= x\cdot (y\cdot z).</math>
|rowspan="4" style="text-align:center;"|<math>\cdot</math>
|-
|7. Existence of '''multiplicative identity 1''':  <math>\forall x\in S, x\cdot 1= 1\cdot x=x.</math>
|-
|colspan="5"|
|8. '''Multiplication''' is '''commutative''': <math>\forall x,y\in S, x\cdot y= y\cdot x.</math>
|-
|colspan="6"|
|9. Every non-zero element has a '''multiplicative inverse''': <math>\forall x\in S\setminus\{0\}, \exists x^{-1}\in S, \text{ s.t. } x\cdot x^{-1}= x^{-1}\cdot x=1.</math>
|}
The semigroup, monoid, group and abelian group are given by <math>(S,+)</math>, and the ring, commutative ring, and field are given by <math>(S,+,\cdot)</math>.


Examples:
== Problem 1 ==
* '''Infinite fields''': <math>\mathbb{Q}</math>, <math>\mathbb{R}</math>, <math>\mathbb{C}</math> are fields. The integer set <math>\mathbb{Z}</math> is a commutative ring but is not a field.
* '''Finite fields''': Finite fields are called '''Galois fields'''. The number of elements of a finite field is called its '''order'''. A finite field of order <math>q</math>, is usually denoted as <math>\mathsf{GF}(q)</math> or <math>\mathbb{F}_q</math>.
** '''Prime field''' <math>{\mathbb{Z}_p}</math>: For any integer <math>n>1</math>,  <math>\mathbb{Z}_n=\{0,1,\ldots,n-1\}</math> under modulo-<math>p</math> addition <math>+</math> and multiplication <math>\cdot</math> forms a commutative ring. It is called '''quotient ring''', and is sometimes denoted as <math>\mathbb{Z}/n\mathbb{Z}</math>.  In particular, for '''prime''' <math>p</math>, <math>\mathbb{Z}_p</math> is a field. This can be verified by [http://en.wikipedia.org/wiki/Fermat%27s_little_theorem Fermat's little theorem].
** '''Boolean arithmetics''' <math>\mathsf{GF}(2)</math>: The finite field of order 2 <math>\mathsf{GF}(2)</math> contains only two elements 0 and 1, with bit-wise XOR as addition and bit-wise AND as multiplication. <math>\mathsf{GF}(2^n)</math>
** Other examples: There are other examples of finite fields, for instance <math>\{a+bi\mid a,b\in \mathbb{Z}_3\}</math> where <math>i=\sqrt{-1}</math>. This field is isomorphic to <math>\mathsf{GF}(9)</math>. In fact, the following theorem holds for finite fields of given order.


{{Theorem|Theorem|
== Problem 2 ==
:A finite field of order <math>q</math> exists if and only if <math>q=p^k</math> for some prime number <math>p</math> and positive integer <math>k</math>. Moreover, all fields of a given order are isomorphic.
A ''<math>k</math>-uniform hypergraph'' is an ordered pair <math>G=(V,E)</math>, where <math>V</math> denotes the set of vertices and <math>E</math> denotes the set of edges. Moreover, each edge in <math>E</math> now contains <math>k</math> distinct vertices, instead of <math>2</math> (so a <math>2</math>-uniform hypergraph is just what we normally call a graph).
}}
A hypergraph is <math>k</math>-regular if all vertices have degree <math>k</math>; that is, each vertex is exactly contained within <math>k</math> hypergraph edges.


=Polynomial over a field=
Show that for sufficiently large <math>k</math>, the vertices of a <math>k</math>-uniform, <math>k</math>-regular hypergraph can be <math>2</math>-colored so that no edge is monochromatic.
Given a field <math>\mathbb{F}</math>, the '''polynomial ring''' <math>\mathbb{F}[x]</math> consists of all polynomials in the variable <math>x</math> with coefficients in <math>\mathbb{F}</math>. Addition and multiplication of polynomials are naturally defined by applying the distributive law and combining like terms.
What's the smallest value of <math>k</math> you can achieve?


{{Theorem|Proposition (polynomial ring)|
== Problem 3 ==
:<math>\mathbb{F}[x]</math> is a ring.
Suppose we have graphs <math>G=(V,E)</math> and <math>H=(V,F)</math> on the same vertex set.
}}
We wish to partition <math>V</math> into clusters <math>V_1,V_2,\cdots</math> so as to maximise:
The '''degree''' <math>\mathrm{deg}(f)</math> of a polynomial <math>f\in \mathbb{F}[x]</math> is the exponent on the '''leading term''', the term with a nonzero coefficient that has the largest exponent.
:<math>(\#\text{ of edges in }E\text{ that lie within clusters})+(\#\text{ of edges in }F\text{ that lie between clusters}).</math>


Because <math>\mathbb{F}[x]</math> is a ring, we cannot do division the way we do it in a field like <math>\mathbb{R}</math>, but we can do division the way we do it in a ring like <math>\mathbb{Z}</math>, leaving a '''remainder'''. The equivalent of the '''integer division''' for <math>\mathbb{Z}</math> is as follows.
* Show that the following SDP is an upperbound on this.
{{Theorem|Proposition (division for polynomials)|
:::<math>
:Given a polynomial <math>f</math> and a nonzero polynomial <math>g</math> in <math>\mathbb{F}[x]</math>, there are unique polynomials <math>q</math> and <math>r</math> such that <math>f =q\cdot g+r</math> and <math>\mathrm{deg}(r)<\mathrm{deg}(g)</math>.
\text{maximize} &&& \sum_{(u,v)\in E}\langle x_u,x_v\rangle+\sum_{(u,v)\in F}(1-\langle x_u,x_v\rangle) \\
}}
\begin{align}
The proof of this is by induction on <math>\mathrm{deg}(f)</math>, with the basis <math>\mathrm{deg}(f)<\mathrm{deg}(g)</math>, in which case the theorem holds trivially by letting <math>q=0</math> and <math>r=f</math>.
\text{subject to} && \langle x_u,x_u\rangle & =1, & \forall u & \in V, \\
 
&& \langle x_u,x_v\rangle & \ge0, & \forall u,v & \in V, \\
As we turn <math>\mathbb{Z}</math> (a ring) into a finite field <math>\mathbb{Z}_p</math> by taking quotients <math>\bmod p</math>, we can turn a polynomial ring <math>\mathbb{F}[x]</math> into a finite field by taking <math>\mathbb{F}[x]</math> modulo a "prime-like" polynomial, using the division of polynomials above.
&& x_u & \in R^n, & \forall u & \in V.
 
\end{align}
{{Theorem|Definition (irreducible polynomial)|
</math>
:An '''irreducible polynomial''', or a '''prime polynomial''', is a non-constant polynomial <math>f</math> that ''cannot'' be factored as <math>f=g\cdot h</math> for any non-constant polynomials <math>g</math> and <math>h</math>.
}}

Revision as of 08:10, 20 December 2021

  • 每道题目的解答都要有完整的解题过程。中英文不限。

Problem 1

Problem 2

A [math]\displaystyle{ k }[/math]-uniform hypergraph is an ordered pair [math]\displaystyle{ G=(V,E) }[/math], where [math]\displaystyle{ V }[/math] denotes the set of vertices and [math]\displaystyle{ E }[/math] denotes the set of edges. Moreover, each edge in [math]\displaystyle{ E }[/math] now contains [math]\displaystyle{ k }[/math] distinct vertices, instead of [math]\displaystyle{ 2 }[/math] (so a [math]\displaystyle{ 2 }[/math]-uniform hypergraph is just what we normally call a graph). A hypergraph is [math]\displaystyle{ k }[/math]-regular if all vertices have degree [math]\displaystyle{ k }[/math]; that is, each vertex is exactly contained within [math]\displaystyle{ k }[/math] hypergraph edges.

Show that for sufficiently large [math]\displaystyle{ k }[/math], the vertices of a [math]\displaystyle{ k }[/math]-uniform, [math]\displaystyle{ k }[/math]-regular hypergraph can be [math]\displaystyle{ 2 }[/math]-colored so that no edge is monochromatic. What's the smallest value of [math]\displaystyle{ k }[/math] you can achieve?

Problem 3

Suppose we have graphs [math]\displaystyle{ G=(V,E) }[/math] and [math]\displaystyle{ H=(V,F) }[/math] on the same vertex set. We wish to partition [math]\displaystyle{ V }[/math] into clusters [math]\displaystyle{ V_1,V_2,\cdots }[/math] so as to maximise:

[math]\displaystyle{ (\#\text{ of edges in }E\text{ that lie within clusters})+(\#\text{ of edges in }F\text{ that lie between clusters}). }[/math]
  • Show that the following SDP is an upperbound on this.
[math]\displaystyle{ \text{maximize} &&& \sum_{(u,v)\in E}\langle x_u,x_v\rangle+\sum_{(u,v)\in F}(1-\langle x_u,x_v\rangle) \\ \begin{align} \text{subject to} && \langle x_u,x_u\rangle & =1, & \forall u & \in V, \\ && \langle x_u,x_v\rangle & \ge0, & \forall u,v & \in V, \\ && x_u & \in R^n, & \forall u & \in V. \end{align} }[/math]
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=高级算法_(Fall_2021)/Finite_Field_Basics&oldid=9698"