Clonoids over vector spaces

Technical Summary: Clonoids Over Vector Spaces

Problem Statement
The paper investigates the structural properties of clonoids, defined as sets of finitary operations between two algebraic structures $A$ and $B$ that are closed under composition with the term operations of $A$ (on the right) and $B$ (on the left). The central problem addressed is the classification of clonoids between finite modules, specifically focusing on the finiteness of the set of such clonoids.

The authors address Conjecture 1, which posits that for finite modules $A$ and $B$, there are only finitely many clonoids from $A$ to $B$ if and only if $A$ and $B$ are of coprime order. While the "only if" direction was previously established by Mayr and Wynne [MW24] (showing that a common divisor allows for an infinite ascending chain of clonoids), the "if" direction remained open for general modules. Previous results had confirmed finiteness for specific cases, such as when $A$ is a group of prime order or when $A$ has a distributive lattice of submodules.

Methodology
The paper's primary methodological contribution is the development and application of a theory of "uniform generation by minors." This concept, introduced in [MW24], is refined and generalized here to provide a combinatorial criterion for when all clonoids between two algebras are generated by their $n$-ary functions.

1. Uniform Generation and Representation: The authors define a set of operations $U \subseteq B^{A^k}$ as uniformly generated by $n$-ary $(A, B)$-minors if there exist fixed operations $s \in B^{(m)}$ and $r_1, \dots, r_m \in R^k_{k,n}(A)$ (operations factoring through $n$-ary terms) such that every $f \in U$ can be expressed as $f = s \circ (f \circ r_1, \dots, f \circ r_m)$.
2. Reduction to Minors: A key theoretical result (Theorem 18) establishes that if the $(n+1)$-ary part of a clonoid is uniformly generated by $n$-ary minors, then the entire clonoid is generated by its $n$-ary part. This reduces the problem of classifying infinite sets of operations to a finite combinatorial problem involving subsets of $n$-ary operations.
3. Linear Algebraic Construction: For the case where $A$ is a finite vector space $F^k$ and $B$ is a module of coprime order, the authors construct explicit representations for characteristic functions of matrices. They introduce $\theta$-spaces (affine subspaces of matrices) and use inclusion-exclusion principles over these spaces to show that characteristic functions of full-rank matrices can be generated by $k$-ary minors.
4. Lattice Isomorphism: The paper constructs an explicit isomorphism between the lattice of clonoids from $F^k$ to $B$ and a product of submodules of specific function spaces $M_{i,k}(F, B)$, which are modules over the group ring $R[GL_i(F)]$.

Key Contributions and Results

• Confirmation of Conjecture 1 for Vector Spaces: The main result (Theorem 49 and Corollary 50) confirms that if $A = F^k$ is a finite vector space and $B$ is a module of coprime order (i.e., $|F|$ is invertible in the ring acting on $B$), then every clonoid from $A$ to $B$ is generated by its $k$-ary functions. Consequently, there are only finitely many such clonoids.
• Optimality of Arity: The authors prove that the arity $k$ is optimal; there exist clonoids from $F^k$ to $B$ that are not generated by their $(k-1)$-ary functions. This establishes a sharp lower bound on the arity of generators.
• Generalization to Product Modules: By combining their results with Proposition 21 (regarding direct products) and existing results on distributive modules [MW24], the authors confirm Conjecture 1 for a broad class of modules $A = F_1^{k_1} \times \dots \times F_n^{k_n} \times D$, where $F_i$ are finite fields and $D$ is a distributive module.
• Explicit Lattice Description: Theorem 55 provides a complete structural description of the lattice of clonoids from $F^k$ to $B$. It shows this lattice is isomorphic to the product of the lattices of submodules of $M_{i,k}(F, B)$ for $0 \le i \le k$.
• Subpower Membership Problem (SMP): The authors apply their classification results to computational complexity. They prove that the Subpower Membership Problem (SMP) for a large class of 2-nilpotent Mal'cev algebras is solvable in polynomial time. Specifically, if the quotient algebra $A/\mu$ (where $\mu$ is a central congruence) is polynomially equivalent to a vector space, the problem reduces to computing representations in a clonoid generated by $k$-ary functions, which can be done efficiently.

Significance
The paper claims significance in several areas:

1. Advancing the Classification of Clonoids: It resolves a major open case of Conjecture 1, moving from specific prime-order groups to general finite vector spaces and their products.
2. Unifying Framework: The paper argues that many existing classification results in the literature (e.g., for discriminator algebras or near-unanimity targets) implicitly rely on the principle of uniform generation by minors. By formalizing this, the authors provide a unified lens through which to view finiteness results.
3. Computational Implications: The results provide a concrete algorithmic pathway for solving the SMP for 2-nilpotent algebras, a problem that remains open for the general Mal'cev case. The paper demonstrates that for algebras with a vector space quotient, the problem is in P.
4. Foundational Bounds: The derivation of a sharp lower bound on the arity of generators (Theorem 58) clarifies the structural complexity required to generate full clonoids between modules.

The authors conclude by noting that while their method works for vector spaces and distributive modules, the general case of Conjecture 1 (e.g., for $A = \mathbb{Z}_{p^2} \times \mathbb{Z}_p$) remains open, suggesting that future progress will likely depend on extending the theory of uniformly representable operations to non-distributive abelian $p$-groups.