Splittability of p -ary functions
Mikhail Igorevich Anokhin · Sbornik Mathematics · 2007
A function ϕ from an n-dimensional vector space V over a field F of p elements (where p is a prime) into F is called splittable if ϕ(u + w) = ψ(u) + χ(w), u ∈ U , w ∈ W , for some non-trivial subspaces U and W such that U ⊕ W = V and for some functions ψ : U → F and χ : W → F. It is explained how one can verify in time polynomial in log p p n whether a function is splittable and, if it is, find a representation of it in the above-described form. Other questions relating to the splittability of functions are considered. Bibliography: 3 titles.