Closed sets of finitary functions between finite fields of coprime order
- PDF / 402,144 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 8 Downloads / 213 Views
Algebra Universalis
Closed sets of finitary functions between finite fields of coprime order Stefano Fioravanti Abstract. We investigate the finitary functions from a finite field Fq to the finite field Fp , where p and q are powers of different primes. An (Fp , Fq )linearly closed clonoid is a subset of these functions which is closed under composition from the right and from the left with linear mappings. We give a characterization of these subsets of functions through the invariant F \{0} with respect to a certain linear subspaces of the vector space Fpq transformation with minimal polynomial xq−1 − 1. Furthermore we prove that each of these subsets of functions is generated by one unary function. Mathematics Subject Classification. 08A40. Keywords. Clonoids, Clones.
1. Introduction The problem of characterizing sets of functions that satisfy some closure properties plays an increasingly important role in General Algebra. E. Post’s characterization of all clones on a two-element set [13] is a foundational result in this field, which was developed further, e.g., in [14,12,15,10]. Starting from [9], clones are used to study the complexity of certain constraint satisfaction problems (CSPs). The aim of this paper is to describe sets of functions from Fq to Fp that are closed under all linear mappings from the left and from the right, in the case p and q are powers of distinct primes. We are dealing with sets of functions with different domains and codomains; such sets are investigated, e.g., in [1] and are called clonoids. Let B be an algebra, and let A be a non-empty set. n k For a subset C of n∈N B A and k ∈ N, we let C [k] := C ∩ B A . According to Presented by R. P¨ oschel. The research was supported by the Austrian Science Fund (FWF):P29931. 0123456789().: V,-vol
52
Page 2 of 14
S. Fioravanti
Algebra Univers.
Definition 4.1 of [1] we call C a clonoid with source set A and target algebra B if k (1) for all k ∈ N: C [k] is a subuniverse of BA , and (2) for all k, n ∈ N, for all (i1 , . . . , ik ) ∈ {1, . . . , n}k , and for all c ∈ C [k] , the function c : An → B with c (a1 , . . . , an ) := c(ai1 , . . . , aik ) lies in C [n] . By (1) every clonoid is closed under composition with operations of B on the left. In particular we are interested in those clonoids whose target algebra is the vector space Fp which are closed under composition with linear mappings also from the right side. Definition 1.1. Let p and q be powers of different primes, and let Fp and Fq be two fields of orders p and q. An (Fp , Fq )-linearly closed clonoid is a non-empty Fn subset C of n∈N Fpq with the following properties: (1) for all n ∈ N, f, g ∈ C [n] and a, b ∈ Fp : af + bg ∈ C [n] ; : (2) for all m, n ∈ N, f ∈ C [m] and A ∈ Fm×n q g : (x1 , . . . , xn ) → f (A · (x1 , . . . , xn )t ) is in C [n] . Clonoids are of interest since they naturally arise in the study of promise constraint satisfaction problems (PCSPs). These problems are investigated, e.g., in [4], and recently in [5] clonoid theory has been used to give an algebraic app
Data Loading...
