Note that everything is mod x^p-x, which is NOT irreducible; in fact x^p-x = x(x+1)(x+2)...(x+p-1), so lots of zero-divisors. Result is *not* a field, and lots of intuitions are wrong. For example, "x" itself has no inverse. We know for sure that x->x+1 and x->2/x do generate ALL (and just) the perm polys (proved by someone else & verified by my Maxima code), so all I'm doing is examining the consequences of this. At 06:12 PM 4/9/2016, Warren D Smith wrote:

H.Baker: (I may be the last person on Earth to know this, but...) All "even" perm polys over a prime p can be written in the form: ... a+1/(b+1/(c+1/(d+1/(e+1/(f+x)))) ...a *continued fraction* !!

--WDS: Seems like a great observation! And I think this CF rational form is more useful than the polynomial form where x^(p-2) is written instead of 1/x.

By "all even" you meant what? That every even permutation can be written this way??

If so, then every odd perm is representable as a single odd perm, composed with a general even perm. And the most convenient odd perm is: x --> g*x mod p if p is an odd prime and g is a generator modulo that prime.

Which would mean that EVERY perm -- both odd and even -- modulo p=prime, is representable as a continued fraction in this way, it is just that at the end we optionally multiply it by g.

Seems very elegant to me.

===

There's just one problem: you're wrong.

Specifically, a+1/(b+1/(c+1/(d+1/(e+1/(f+x)))), no matter how high you stack it, is just a fractional linear of the form (A+Bx) / (C+Dx).

So this all was rather absurd. Plainly, this is not enough, in general, to generate all perms, or all even perms, or even anyplace close. There are p! perms and p!/2 even perms but fractional linears cannot generate more than p^4 of them, indeed (slightly more carefully counting) at most (p+1)*p*(p-1)/6 are possible.

-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)