**An Algebraic Approach to Reducing the Number of Variables of Incompletely Defined Discrete Functions**

Jaakko Astola, Pekka Astola, Radomir Stanković and Ioan Tabus

In this paper, we consider incompletely defined discrete functions,* i.e.*, Boolean and multiple-valued functions, ƒ : *S* → {0, 1, . . . , *q* − 1} where *S* ⊆ {0, 1, . . . , *q* − 1}^{n}*i.e.*, the function value is specified only on a certain subset *S* of the domain of the corresponding completely defined function. We assume the function to be sparse i.e. |*S*| is ’small’ relative to the cardinality of the domain. We show that by embedding the domain {0, 1, . . . , *q* − 1}* ^{n}*, where

*n*is the number of variables and

*q*is a prime power, in a suitable ring structure, the multiplicative structure of the ring can be used to construct a linear function {0, 1, . . . ,

*q*− 1}

*→ {0, 1, . . . ,*

^{n}*q*− 1}

*that is injective on*

^{m}*S*provided that

*m*> 2 log

*|*

_{q}*S*| + log

*(*

_{q}*n*− 1). In this way we find a linear transform that reduces the number of variables from

*n*to

*m*, and can be used

*e.g.*in implementation of an incompletely defined discrete function by using linear decomposition.