Universal Functions for Classes of Linear Functions of Three Variables
- PDF / 397,677 Bytes
- 8 Pages / 594 x 792 pts Page_size
- 83 Downloads / 194 Views
III. INFORMATICS UNIVERSAL FUNCTIONS FOR CLASSES OF LINEAR FUNCTIONS OF THREE VARIABLES A. A. Voronenko1 and A. S. Okuneva2
UDC 517.718.7
We consider the construction of a universal function for classes of modulo 2 sums of three arguments. The definition domain of the universal functions is of cardinality Θ(log n). Keywords: linear function, universal function, upper bound.
Introduction We have previously introduced the notion of universal function and considered its existence and the cardinality of its definition domain [1]. The formulation of the problem of construction of universal function as proposed in [1] is original and substantially differs from similar formulations in the literature. From the outset, it contains a “big lie” and then proceeds to construct the target so that partially true information can be used to specify every possible solution in a unique manner. A review of results on universal functions can be found in [6]. Consider some class of functions K. We say that a function f dependent on the same set of variables as the functions from K generates the function g (given that g ∈K ) if we can present a set of points X such that for every x from X we have f (x) = g(x) . The function f is called universal for the class K if it generates
every function from this class. The case of a sum of two variables is considered in [2]. The construct closest to universal functions for the class of linear functions are the bent-functions (see, e.g., [4]). A bent function is maximally distant from all linear functions, while a universal function differs from each linear function at n + 1 points from among a smallest possible number. The addition of possibly false answers is a classical stratagem that permits to continue investigating related problems for a long time. Thus, although the decoding problem for a monotone function has been fully solved by Hansel [8] in 1966, one of the formulations with false answers was considered in [5] quite recently. The most popular close formulations are presented in [7]. Main Results Denote the set of sums of triples of various variables by D = {xi ⊕ x j ⊕ xk } . The following theorem holds. Theorem 1. For the set D of functions of n variables there exists a universal function defined on 6 ] log 2 n [
tuples. 1
Faculty of Computational Mathematics and Cybernetics, Lomonosov Moscow State University, Moscow, Russia, and Moscow Institute of Physics and Technology (National Research University), Moscow, Russia; e-mail: [email protected]. 2 Faculty of Computational Mathematics and Cybernetics, Lomonosov Moscow State University, Moscow, Russia; e-mail: okuneva-anna@ mail.ru. Translated from Prikladnaya Matematika i Informatika, No. 63, 2020, pp. 115–121. 410
1046–283X/20/3103–0410
© 2020
Springer Science+Business Media NewYork
UNIVERSAL FUNCTIONS FOR CLASSES OF LINEAR FUNCTIONS OF THREE VARIABLES
411
Proofs Auxiliary Problem. Three different unknown elements are guessed from a set of cardinality n. We can take any subset of the original set and ask about the parity of the n
Data Loading...
