3
$\begingroup$

What does it mean to multiply or divide polynomials?

I have used them so many times, in error correcting codes, cryptography, etc. but it was never clear to me what would be a graphical representation/ interpretation.

I have always pondered what did it mean when someone multiplies a line with a curve to get another hyperplane of a bigger dimension.

I know the formulae and properties of polynomial multiplication & division, I am specifically looking for a graphical/algebraic interpretation of it.

$\endgroup$
  • 2
    $\begingroup$ I think this would fit Mathematics even better. $\endgroup$ – Juho Sep 18 '13 at 8:42
  • 1
    $\begingroup$ @Juho Since this asks for CS intuition, maybe not. It might be worthwhile to get both perspectives. $\endgroup$ – Raphael Sep 18 '13 at 9:16
  • 1
    $\begingroup$ The polynomial $PQ$ is the unique polynomial satisfying $(PQ)(x) = P(x) Q(x)$ for all $x$ in the ground field. (This works only over infinite fields.) $\endgroup$ – Yuval Filmus Sep 19 '13 at 17:41
3
$\begingroup$

I am a bit uncertain by what you mean by graphical. One notion is to plot or graph a function, like $y=f(x)$, as you would in a highschool level algebra course. Another notion of "graphical" may include some similar to a Cayley graph. I just want to be upfront that the extent of my knowledge does not extend greatly into topology and some algebraic geometry. I will go off on the assumption that overly abstract "graphical" representations do not count.

Graphical Plots: In abstract algebra, the polynomials that work with the $y$ vs. $x$ type of graphing are in the ring of polynomials over $\mathbb{R}$, otherwise known as $\mathbb{R}[x]$. Evaluating any of these for an $x \in \mathbb{R}$ gives you a continuous function that you can plot. This works for $\mathbb{R}[X]$'s extensions, too ($\mathbb{C}[X]$).

Graphs: Cryptography and coding theory involve a massive number of structures, each of which can be represented as a graph. A notable set of examples are graphs depicting algebras over structures of finite size. Rings of polynomials are not one of them, since they contain, at minimum, a countable number of elements. Some intuition can be gathered from how these graphs change as you vary/limit the degree of your polynomial (more on this later). Though I imagine that this is not the kind of representation that you had hoped.

For other graphical/geometrical/topological aspects of crypto and coding theory, you might want to look into things like vector spaces, sphere packing, and lattices.

Polynomials Over Finite Fields:

Even so, it is important to realize that the inclusion of rings of polynomials in cryptography and coding theory are over finite fields. That is, they usually only consider $\mathbb{F}_q[X]$, which is the finite field with $q$ elements. An easily recognized one would be $\mathbb{F}_2^k = \{0,1\}^k$ (your typical algebra over binary strings).

A slight extension of this idea, rings of multivariate polynomials, are also useful. They are typically represented by $\mathbb{F}[X_1,X_2,...]$ where $\mathbb{F}$ is a field. An algebra of multivariate polynomial over $\mathbb{F}_2$ is equivalent to a boolean algebra. A boolean formula, $\varphi(x_1,x_2,...,x_n)$, would be equivalent to evaluating a degree $n$ multivariate polynomial over $\mathbb{F}_2$. The intuition behind this is to see that $+$ and $\times$ act like XOR and AND logic gates on your binary inputs, $x_1,x_2,...,x_n \in \{0,1\}$.

Beyond drawing something fundamentally equivalent to circuit diagrams, I do not see a fruitful way to represent this graphically. Though, this did not stop these guys from trying (I still think it is the same): http://polybori.sourceforge.net/zdd.html

There are obviously way more concepts from abstract algebra that are involved in these areas (e.g. $\mathbb{Z}_p$, the ring integers mod $p$). Some may even have graphical representations that make the idea more intuitive. Though these fall outside the scope of the question, which is specific to algebras over polynomials.

$\endgroup$
-1
$\begingroup$

You should not try to visualize this. Algebraic properties can span to multi dimensions.. try to ask what would an algebraic interpretation of it? Use linear algebra to reason about it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.