Python's "map" method and permutations of lists

Posted by Jason Polak on 18. February 2018 · Write a comment · Categories: computer-science · Tags: , ,

Let's look at Python's map function. What does this function do? Here is the syntax:

It takes a function called function and applies it to each element of iterable, returning the result as an iterable. For example:

The output of this program is:

More »

Polynomial over finite field: permutation polynomial?

Posted by Jason Polak on 18. February 2018 · 2 comments · Categories: computer-science · Tags: , ,

Let's assume you have a polynomial over a finite field $\F_q$, defined in Sage. How can you tell whether it's a permutation polynomial? That is, when is the corresponding function $\F_q\to\F_q$ bijective?

This is how you might have a polynomial over $\F_q$ defined in Sage:

Here, the variable $x$ refers the element $x$ in the isomorphism $\F_q \cong \F_p[x]/\alpha(x)$ and $t$ is the variable in the polynomial ring $\F_q[t]$. Is $f$ a permutation polynomial? That of course depends on what $q$ is.
More »

Degrees of some permutation polynomials

Let $\F_q$ be a finite field. For any function $f:\F_q\to \F_q$, there exists a polynomial $p\in \F_q[x]$ such that $f(a) = p(a)$ for all $a\in \F_q$. In other words, every function from a finite field to itself can be represented by a polynomial.

In particular, every permutation of $\F_q$ can be represented by a polynomial. This isn't true for other finite rings, a fact which is the topic of one of my papers. At any rate, polynomials that represent permutations are called permutation polynomials.

It's not easy to determine which polynomials are permutation polynomials. The exception is for the finite field $\F_2$, and more generally $\Z/2^w$. Then this case Ronald Rivest gave a straightforward criterion for whether a polynomial is a permutation polynomial.

However, there is a classical result that says any permutation may be represented uniquely by a polynomial whose degree is at most $q-2$. Here is an example noted by Charles Wells. Let $a,b\in\F_q$ be two distinct elements. The polynomial
$$f(x) = x + (a-b)(x-a)^{q-1} + (b-a)(x-b)^{q-1}$$
represents the transposition of $a$ and $b$. I suggest that you verify this by direct substitution, using the identity $c^{q-1} =1$ whenever $c\not=0$, which in turn follows from Fermat's little theorem.
More »

Determinants, Permutations and the Lie Algebra of SL(n)

Here is an old classic from linear algebra: given an $n\times n$ matrix $A = (a_{ij})$, the determinant of $A$ can be calculated using the permuation formula for the determinant:

$\det(A) = \sum_{\sigma\in S_n} (-1)^\sigma a_{1\sigma(1)}\cdots a_{n\sigma(n)}$.

Here $S_n$ denotes the permutation group on $n$ symbols and $(-1)^\sigma$ denotes the sign of the permutation $\sigma$. The computation of the determinant is much more easily done via the 'minor expansion method', but this just reduces to the above formula. Now, typically we would never use the above formula to calculate the determinant, but that doesn't mean it isn't useful!

The Lie Algebra of an Algebraic Group

In fact, computating the Lie algebra of $\mathrm{SL}_n$ over a fixed commutative ring $k$ happens to be a quick and interesting application of the above determinant formula. First, let us recall the definition of the Lie algebra, or at least one of the many equivalent definitions. Consider the algebra of dual numbers, $k[\tau]/(\tau^2)$. Each element in this algebra can be written uniquely as $a + b\tau$: this gives a $k$-algebra map $C: k[\tau]/(\tau^2)\to k$ by sending $a + b\tau$ to $a$.
More »