Add `is_permutation` in the `FiniteDynamicalSystem`

[junwenwaynepeng]

Problem Description

Add a function is_permutation in the FiniteDynamicalSystem to determine if a given function is a permutation on its domain. Specifically, I propose to create is_permutation to help us determine if a given polynomial or rational function induces a permutation over a finite field.

Proposed Solution

The following code is implemented by Will-Chen2025

def is_permutation(self, method='brute force', prob=0.95):
        r""""
        Test if the given map is a permutation of the ground set.

        ALGORITHM:

        In 'brute force' method, compute the sum of the length of 
        each cycle and check if it is equal to the size of the 
        given ground set. In 'Hermite' method, make a polynomial
        ring of the given finite field, and make a quotient ring
        for moding x^q-x. Change the given map into a polynomial
        on quotient ring, raise the polynomial to the power of 
        i in [1...q-2] and i is not divided by p, if the degree 
        is equal to q-1 then returns false. Raise the polynomial to
        the power of q-1 if the degree is not equal to q-1 then 
        returns false, otherwise returns True. In 'birthday attack'
        method, compute the number of needed random samples n with
        given prob, and make a choose random n elemets from given
        ground set, then compute the number of image and check if 
        it is equal to n.

        INPUT:

        - ``method`` -- string (default: ``brute force``). Can set 
          to ``'brute force'`` or ``'Hermite'`` for different method.
        - ``prob`` -- float (default: ``0.95``); parameter for
          Birthday Attack Method.

        OUTPUT: boolean
        - True: if the given evolution is a permutation of the
          given ground set
        - False: otherwise

        EXAMPLES::

            sage: from sage.dynamics.finite_dynamical_system import FiniteDynamicalSystem
            sage: D = FiniteDynamicalSystem(GF(9), lambda x : x + 1)
            sage: D.is_permutation()
            True
            sage: D = FiniteDynamicalSystem(Integers(3), lambda x : x ^ 2)
            sage: D.is_permutation()
            False
            sage: D = FiniteDynamicalSystem(Integers(5), lambda x : x ^ 2 + x + 1)
            sage: D.is_permutation(method='Hermite')
            False
            sage: D = FiniteDynamicalSystem(GF(23), lambda x : x + 1)
            sage: D.is_permutation(method='birthday attack')
            True
            sage: D = FiniteDynamicalSystem(GF(23), lambda x : x ^ 2 + 1)
            sage: D.is_permutation(method='birthday attack', prob=0.5)
            True

        """
        # check if the method is ...

        # use brute force to check
        if method == 'brute force':
            C = self.cycles()
            if sum(len(c) for c in C) == len(self.ground_set()):
                return True
            return False

        # use Hermite method to check
        elif method == 'Hermite':
            from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
            X = self._X
            q = len(X)
            p = X.characteristic()
            R1 = PolynomialRing(X, 'x1')
            x1 = R1.gen()
            h = x1 ** q - x1
            R2 = R1.quotient(h, 'x2')
            x2 =R2.gen()
            ev1 = self._phi(x2) + 0 * x2 # 0 * x2 for constant function 
            ev2 = ev1
            for i in range(1,q-1):
                if i % p != 0:
                    if ev1.lift().degree() == q - 1: # .lift() to compute degree in quotient ring
                        return False
                ev1 = ev1 * ev2
            if ev1.lift().degree() != q - 1: # .lift() to compute degree in quotient ring
                return False
            return True

        # use birthday attack method to check
        elif method == 'birthday attack':
            if 0 <= prob <= 1:
                import random
                X = self._X
                ev = self._phi
                q = len(X)
                if prob == 1:
                    n = q
                else:
                    from sage.functions.log import log
                    from sage.functions.other import ceil, sqrt
                    n = min(q, ceil(sqrt(2 * q * log(1 / (1 - prob)))))
                S = random.sample(sorted(set(X)), n)
                M = [ev(i) for i in S]
                if len(set(M)) == n:
                    return True
                return False
            raise ValueError("prob needs to be a value between 0 and 1")
        raise ValueError("method needs to be 'brute force', 'Hermite', or 'birthday attack'")

Alternatives Considered

Our experiment and concerns:

1. Using list comprehension in a brute force method is faster than calling .cycle(). However, we choose to use .cycle() for better styling.
2. The Hermite method only works over a finite field, not just any finite set. However, the brute force method can be applied to more general cases. We are concerned that this might be inconsistent.

Additional Information

No response

Is there an existing issue for this?

• [X] I have searched the existing issues for a bug report that matches the one I want to file, without success.

[Will-Chen2025]

For an alternative way of writing 'brute force' method, we may also consider listing the image of evolution and then check if the length of the set of the list is equal to the size of the given ground set, as the following code.

        if method == 'brute force':
            X = self._X
            ev = self._phi
            if len(set([ev(i) for i in X])) == len(X):
                return True
            return False

In my experiments, as the ground set is big enough, this method is faster than the one impremented above. It's because we use [ev(i) for i in X] instead of python for loop.