Posted by Jason Polak on 21. July 2018 · Write a comment · Categories: number-theory · Tags: ,

If $m$ and $n$ are relatively prime integers, the Jacobi symbol $(m/n)$ is defined as the sign of the permutation $x\mapsto mx$ on the set $\Z/n$. Let's give a simple example: $(7/5)$. The permutation on $\{1,2,3,4\}$ is given by $(1 2 4 3) = (1 2)(2 4)(4 3)$ which has an odd number of transpositions. Therefore, $(7/5) = -1$.

Note that as in this example, it is sufficient to compute the sign of the permutation on $\Z/n – \{0\}$, since multiplication always leaves zero fixed.

But what if we wanted to compute something like $(3/412871)$? These numbers aren't so big, so a computer could do it directly. However, there is a better way to do the computation of the Jacobi symbol $(m/n)$ if one of $m$ or $n$ is much larger than the other one. This method is good for computers too when one of the numbers is so large, that a direct computation even by a fast computer would be hopeless.
More »

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 »

Posted by Jason Polak on 16. January 2018 · Write a comment · Categories: commutative-algebra, ring-theory · Tags:

Let $\Z[\Z/n]$ denote the integral group ring of the cyclic group $\Z/n$. How would you create $\Z[\Z/n]$ in Sage so that you could easily multiply elements?

First, if you've already assigned a group to the variable 'A', then

will give you the corresponding group ring and store it in the variable 'R'. The first argument of 'GroupAlgebra(-,-)' is the group and the second is the coefficient ring. Sage uses 'ZZ' to denote the integers, 'QQ' to denote the rationals, etc.

So how do you specify the cyclic group $A$? The first posibility is to use the construction:

where you'd replace 'n' by the actual number that you want there. This is useful if you want to work with other permutation groups, because the elements of 'A' are stored as permutations:

The output to this snippet is:

More »

Posted by Jason Polak on 11. October 2014 · Write a comment · Categories: math, opensource · Tags: ,

Sage is a neat bundle of mathematical software that can be used to do anything from finding class numbers of number fields (like I did to make this graph) to testing whether a finitely presented group is trivial (sometimes…). Typically one works with Sage in a "worksheet" in a web browser, so that it's easy to organise large numbers of calculations for later reference. Navigating large worksheets, however, might be cumbersome without a table of contents, just like long math papers without a table of contents are hard to read.

In this post, we'll go over how to (manually) make a table of contents in your Sage worksheet with HTML, with the following example: More »