School of Technology and Computer Science Seminars

Constructing Faithful Maps

by Prerona Chatterjee (School of Technology and Computer Science, TIFR)

Friday, September 14, 2018 from to (Asia/Kolkata)
at A-201 (STCS Seminar Room)
Description
Abstract: Suppose we are given a set of $k$ polynomials, $f_1, \ldots, f_k \in \mathbb{F}[x_1, \ldots, x_n]$. They are said to be algebraically dependent if there is a non-zero polynomial $A$ over $\mathbb{F}$ in $k$ variables such that $A(f_1, \ldots, f_k) = 0$. Otherwise, they are said to be algebraically independent.

Just like a set of $k$ linearly independent vectors in $\mathbb{R}^n$ actually resides in a $k$-dimensional subspace, a set of $k$ algebraically independent polynomials intuitively has the same "freedom" as only $k$ independent variables. A faithful map formalises this.

Suppose $\{f_1, \ldots, f_k\} \subseteq \mathbb{F}[x_1, \ldots, x_n]$ is a set of algebraically independent polynomials. A map $\phi : \{x_i\} \mapsto \mathbb{F}[y_1, \ldots, y_k]$ is said to be faithful if the set of polynomials $\{f_i(\phi(x_1), \ldots, \phi(x_n))\}_{i \in [k]} \subseteq \mathbb{F}[y_1, \ldots, y_k]$ is algebraically independent.

In this talk, we will construct faithful maps when the underlying field is $\mathbb{Q}$, $\mathbb{R}$ or $\mathbb{C}$ for example. Apart from being an interesting question in its own right, construction of faithful maps also has applications in algebraic circuit complexity.