## On Single Cycle Functions

^{Oct 23, 2007 by Ilya Levin}

During the last year, I have seen few submitted papers based on my note about single cycle functions published on May 19, 2006.

You can read the note here: "On Single Cycle Functions" (pdf, 95Kb)

I was puzzled by the latest of such papers that I have to review. The authors have reconstructed the missing theory quite well but at some point have surprisingly jumped to a premature and a wrong conclusion.

To make things simpler, I have sketched a small interactive online tool to test any given function for being a single cycle and invertible.

If you as much fascinated by this subject as I am, then go ahead and try the T-functions testbed.

Write a function as a JavaScript subroutine, click on *Evaluate* button and
if all the mapping values set to '1' then the function is a single cycle and invertible. It is this simple.

Since I am already on the subject here, I would like to explain a bit more about
the function `x → (a(¬x)) <<< b`

Perhaps I was too harsh in dissemblance *:)*

Multiplication overflow bits do matter. This is easier to see when rotation replaced with
`((x << b) | (x >> (2n-b)))`

If `x = ((a(¬x)) % 2n)`

then the period is 2n-1 and the function is not invertible indeed. However, it is invertible without the mod.

**upd:** here are couple more single cycle functions as a bonus *:)*

- x → ax + (¬x), where a is a term of {a
_{0}= 2, a_{i}= a_{i-1}+ 4} - x → (¬x) + ax + bx, where |a - b| ≡ 4t, t = 0, 1, 2, 3…