# Literatecode

## 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 {a0 = 2, ai = ai-1 + 4}
• x → (¬x) + ax + bx, where |a - b| ≡ 4t, t = 0, 1, 2, 3…