This course is intended to familiarize the students with the types of mathematical reasoning found in theoretical research on computing and communications. The course contains a broad set of intermediate and advanced level topics in Algebra, Combinatorics, Probability and Graph Theory.
Goal: By the end of the course, students should be able to read and understand research papers with algebraic/combinatorial reasoning. They should should be able to write concise and clear proofs.
Prerequisites: Students are expected to have already attended Discrete Maths, Linear Algebra and Probability courses some time in their career. Though we will be revising these in a few lectures, the course will quickly move on to advanced topics.
Acknowledgements: This course is loosely based on a similar course offered by Jaikumar Radhakrishnan (http://www.tcs.tifr.res.in/~jaikumar/Courses/MathStructures/Autumn06/) at TIFR, Mumbai.
Assignment Tests: 20%
Quiz 1, Quiz 2: 10% each
MidSem: 25%
EndSem: 35%
Bonus Marks: 5% (for 90% attendance or solve some hard problem that will be given).
If $G$ has no proper subgroups then show that $G$ is cyclic of order $p$, where $p$ is a prime number.
If $G$ is not a cyclic group then show that $G$ has a proper subgroup (ie not ${0}$ or $G$ itself).
A group is called Abelian if the operation is also commutative. Prove that
$\mathbb{Z}_p\times \mathbb{Z}_q$ is the product of the two sets with $pq$ elements. Addition is defined coordinate wise. Prove that:
Let $p$ be a prime and $n, k$ positive integers, $F = \left\{ f:\mathbb{Z}_p^k \rightarrow [n] \right\}$ (the set of all functions from $\mathbb{Z}_p^k$ to $[n]$.). For a function $f \in F$, and $a \in \mathbb{Z}_p^k$, the translation of $f$ by $a$ is the function $g(x) = f(x + a)$ (addition is defined coordinate-wise modulo $p$).
[Hint] This is the strict generalization of the example we did in class: the proof of FLT theorem. For getting that result, substitute $k=1$ and $n = a$.
A function $f:[m]^k \rightarrow [n]$ is symmetric if for all $x, y \in [m]^k$ such that $y$ can be obtained by permuting $x$ (using a permutation in $S_k$), $f(x) = f(y)$. For example the sum and product functions ($f(x) = \sum_{i\in [k]} x_i \mod n$ and $g(x) = \prod_{i\in [k]} x_i \mod n$ correspondingly) are symmetric. The Max, Min functions are also symmetric. Find the number of symmetric functions in terms of $m, n, k$. [Hint] Requires some ball and bins counting.
Let $k$ be prime and $\mathcal F = \left\{ f:[m]^k\rightarrow [n] \right\}$ (set of all functions from $[m]^k$ to $[n]$). $g$ is a cyclic reordering of $f$, if $\exists i \in [k]$ such that $g(x) = f(\sigma^i(x))$ where $\sigma^i(x) = x_i \cdots x_n x_1 \cdots x_{i-1}$. Find the number of distinct functions in $\mathcal F$ if cyclic reorderings are considered the same. Use this to show that $k$ divides $n^{m^k} - n^t$ where $t = \frac{m^k - m}{k} + m $.
Read: [CoCo] Sections 1.7.1, 1.7.2, 1.7.3, Section 2 - 2.1.1.
Solve:
Tutorial 1
Test 1 | Lec 7: Inclusion Exclusion Examples
Read:
Solve:
Let $n \geq 2$ be a positive integer. The Euler totient function is defined by $\phi(n) = \left| \{ m: m < n \text{ and } \text{gcd}(m,n) = 1 \} \right|$. If the prime factorization of $n$ is $n = p_1^{e_1}\cdot p_2^{e_2} \cdots p_k^{e_k}$. Show using inclusion exclusion that: $$\phi(n) = n \prod_{i=1}^k \left(\frac{p_i - 1}{p_i}\right).$$
[Hint] Choose sets $A_1, \cdots, A_k$ that can easily be counted such that $\phi(n) = \left| \overline{A_1 \cup \cdots \cup A_k} \right|$.
Office Hrs 1
Read
Solve
Suppose $A$ is a randomized algorithm for a decision problem ($0,1$ output) which takes $x \in \{0,1\}^n$ (where $n$ is a fixed number say $100$; we are not interested in all inputs which are infinite in number but only the $2^n$ inputs of length $n$) as input. Also suppose we provide all the randomness that the algorithm requires by giving it a string $r \in \{0,1\}^m$ which is chosen uniformly at random. You are told that for all inputs $x \in \{0,1\}^n$, the algorithm is correct with probability $1-\frac{1}{2^{n+1}}$. That is $$ \forall x \in \{0, 1\}^n, \Pr_{r \in \{0, 1\}^m}\left[A(x,r) \text{ is correct}\right] \geq 1 - \frac{1}{2^{n+1}}.$$ Then show that there is a fixed string $r \in \{0,1\}^m$ such that for every input $x\in \{0,1\}^n$, $A(x,r)$ is correct. That is $$ \exists r \in \{0,1\}^m, \forall x \in \{0,1\}^n, A(x,r) \text{ is correct}.$$
Let $p(x_1,x_2,\cdots,x_n)$ be a nonzero polynomial of total degree $d$ (maximum value among all monomials of the sum of degrees of each variable) on $n$ variables with coefficients from a finite field $\mathbb F$. Let $\alpha_1,\cdots, \alpha_n$ be chosen uniformly and independently from $\mathbb F$. Show that: $$ \Pr\left[p(\alpha_1,\cdots, \alpha_n) = 0 \right] \leq \frac{d}{|\mathbb F|}.$$ Hint: Use induction on number of variables $n$. Decompose the polynomial according to powers of $x_1$. Condition on appropriate event and upperbound the probability.
Suppose you have a fair coin (equal probability of heads and tails). You can use the coin to choose one among four options uniformly at random by tossing it twice and assigning the four outcomes to the four options.
Read:
Error Correcting Codes | Reed Solomon Codes: 3 lecs (by Prof. Prasad)
Pair/$k$-wise independent hash functions, Application to Set Membership, Construction using Reed Solomon Codes.
Read:
There is no single book covering all the topics. For different lectures, we will be following material from different sources, which will be posted at the course page. Some of the sources that will be used often are:
[AZ] Proofs from the Book. Aigner and Ziegler
[AS] The Probabilistic Method. Alon and Sipser
[MA] Algebra by M Artin, Prentice-Hall India.
[TJ] Abstract Algebra: Theory and Applications Thomas W. Judson pdf
[ADS] Applied Discrete Structures, Al Doerr, Ken Levasseur pdf
[CoCo] Lecture Notes, Combinatorics Lecture by Torsten Ueckerdt (KIT) pdf
[JM] Permutation Puzzles: A Mathematical Perspective. Jamie Mulholland pdf
[PJC] Notes on Combinatorics Peter J. Cameron pdf
[DG] An Introduction to Combinatorics and Graph Theory David Guichard. pdf