Superimposed Codes and Query Algorithms

Abstract

New superimposed codes based on finite projective planes are proposed. These codes allow to construct efficient randomized query algorithms for some functions. Linear codes is the simplest class of codes. The alphabet used is a fixed choice of a finite field GF (q) = Fq with q elements. In most of applications a special case of GF (2) = F2 is considered. These codes are binary codes. A generating matrix G for a linear [n; k] code over Fq is a k by n matrix with entries in the finite field Fq, whose rows are linearly independent. The linear code corresponding to the matrix G consists of all the qk possible linear combinations of rows of G. The requirement of linear independence is equivalent to saying that all the qk linear combinations are distinct. The superimposed codes also can be considered as linear codes, only the linear operation "multiplication modulo 2" is substituted by the operation "disjunction". Let X be an n-element set . For an integer k, 0 k n we denote by ( Xk ) the collection of all the k-subsets of X, while 2X denotes the power set of X. A family of subsets of X is a subset of 2X . It is called k-uniform if it is a subset of ( Xk ). We call the family of sets F r-cover-free if F0 * F1 [ [ Fr holds for all pairwise distinct F0; F1; F2; ; Fr in F . Let us denote by f (n; k) the maximum cardinality of an r-cover-free family F in ( Xk ), j X j= n. Definition 1. An r-cover-free family F in ( Xk ), j X j= n is called a [r; k; n]superimposed code.

Introduction

and Z. Füredi [ 8 ] proved upper and lower bounds for f (n; k) and noted relation of existence of superimposed codes with existence of Steiner systems with certain parameters (projective planes also are Steiner systems). The bounds were later improved by several authors and the notion of superimposed codes was generalized in [ 5–7, 12, 15, 17, 20 ] but very many important problems are still widely open. 2

Projective Planes

A projective plane consists of a set of lines, a set of points, and a relation between points and lines called incidence, having the following properties: 1) Given any two distinct points, there is exactly one line incident with both of them. 2) Given any two distinct lines, there is exactly one point incident with both of them. 3) There are four points such that no line is incident with more than two of them.

The second condition means that there are no parallel lines. The term "incidence" is used to emphasize the symmetric nature of the relationship between points and lines. Thus the expression "point p is incident with line l " is used instead of either "p is on l " or "l passes through p ".

A finite projective plane of order n is formally defined as a set of n2 + n + 1 points with the properties that:

1) Any two points determine a line,

2) Any two lines determine a point, 3) Every point has n + 1 lines on it, and 4) Every line contains n + 1 points.

The number n here is called the order of the projective plane. It is proved that a finite projective plane can exist only when the order n is a power of a prime. Existence of projective planes with certain parameters in many cases is an open problem. (Properties of projective planes are described in [ 4 ].)

The projective plane of order 2, also known as the Fano plane, has 7 points, 7 lines and it is defined by the incidence matrix

Definition 2. For arbitrary prime number q we define a collection Proj(q) of points (p1;p2; ;pq2+q+1) and lines (l1;l2; ;lq2+q+1) where a relation point pi is incident to line lj is defined by the following rule: 1) If i 2 f1;2; ;q + 1g then the point pi is incident to the lines l(i 1)q+2; l(i 1)q+3; ;liq+1 and the line li is incident to the points p(i 1)q+2;p(i 1)q+3; ;piq+1. i (q+1) j (q+1) 2) If i 2 fq+2;q+3; ;q2 +q+1g and b q c = a and b q c = b then the point pi is incident to the line lj iff

i (q +2) i (q +2) ( b c) =

q q j (q +2) j (q +2) j (q +2) j (q +2) i (q +2) = ( b c)+( b c) (b c): q q q q q (see an example for q = 5 in Table 1). describing incidence of points pi1;pi1+1; ;pi2 to lines lj1;lj1+1; ;lj2. tu

We will consider only elementary areas where (i1; 12) is taken from the set f(1; q + 1); (q + 2; 2q + 1); (2q + 2; 3q + 1); ; (q2 + 2; q2 + q + 1)g and (j1; j2) is taken from the set f(1; q+1); (q+2; 2q+1); (2q+2; 3q+1); ; (q2 +2; q2 +q+1)g.

The following 4 lemmas are immediately implied by Definition 2.

Lemma 2. The elementary area (1; q + 1) (1; q + 1) is such that pa is incident to lb iff either a = 1 or b = 1.

Lemma 3. The elementary area (i1; i2)

(1; q + 1) where (i1; i2) 2 f(q + 2; 2q + 1); (2q + 2; 3q + 1); ; (q2 + 2; q2 + q + 1)g is such that pa is incident to lb iff b 2 f(b + 1)q + 2; ; (b + 2)q + 1g.

Lemma 4. The elementary area (1; q + 1)

(j1; j2) where (j1; j2) 2 f(q + 2; 2q + 1); (2q + 2; 3q + 1); ; (q2 + 2; q2 + q + 1)g is such that pa is incident to lb iff a 2 f(a + 1)q + 2; ; (a + 2)q + 1g.

Lemma 5. The elementary area (i1; i2) (j1; j2) where (i1; i2) 2 f(q + 2; 2q + 1); (2q + 2; 3q + 1); ; (q2 + 2; q2 + q + 1)g and (j1; j2) 2 f(q + 2; 2q + 1); (2q + 2; 3q + 1); ; (q2 + 2; q2 + q + 1)g is such that pa is incident to lb iff b

a + d( mod q) where d = i1q 2 j1q 2 .

We demanded that the parameter q is a prime number. Hence the property formulated in Lemma 5 shows that in this elementary area each value of a corresponds to exactly one value of b. Moreover, Lemma 5 shows that the characteristics d of an elementary area describes this elementary area in much detail.

Lemma 6. For arbitrary (i1; i2) from the set f(q + 2; 2q + 1); (2q + 2; 3q + 1); ; (q2 + 2; q2 + q + 1)g all the elementary areas (i1; i2) (q + 2; 2q + 1) have characteristics d = 0 and the q 1 elementary areas (i1; i2) (j1; j2) where (j1; j2) 2 f(q + 2; 2q + 1); (2q + 2; 3q + 1); ; (q2 + 2; q2 + q + 1)g have q 1 distinct values of the characteristics d 2 f1; 2; ; qg.

Proof. By definition 2, the elementary areas (i1; i2) (2q + 2; 3q + 1) where (i1; i2) 2 f(2q + 2; 3q + 1); (3q + 2; 4q + 1); ; (q2 + 2; q2 + q + 1)g have characteristics d being 1; 2; ; q, respectively. It follows from Lemma 5 that the set of all characteristics for (i1; i2) (kq + 2; (k + 1)q + 1) can be obtained by multiplying all elements of 1; 2; ; q to k 1. Since q is a prime number, the set f1; 2; ; qg does not change by such a multiplication. tu

We need a much more strong property of P roj(q).

Definition 4. By Sj we define the set of all points incident to the line lj .

To simplify our notation we sometimes will not distinguish between a line lj and the set Sj containing all the points incident to lj .

Definition 5. By S we denote the collection of all the sets S1; S2; Sq2+q+1.

Definition 6. By Q we denote the set f1; 2; ; q2 + q + 1g.

Definition 7. By Rr we denote the set

f(u1; u2;

; ur) j (8i)(i 2 Q) and (8i; j)(i; j 2 Q and ui 6= uj )g Definition 8. By Su1 ; Su2 ; ; Sur .

Definition 9. By Uq;r we denote the collection

S(u1;u2; ;ur) we denote the union of the sets fS(u1;u2; ;ur) j (u1; u2;

; ur) 2 Rr and (8i)(Sui 2 S)g Below we will consider only collections Uq;r where r = q 1.

Lemma 7. Given r q 1, let fu1; u2; ; urg and fv1; v2; distinct subsets of the set Q. Then S(v1;v2; ;vr) 6= S(v1;v2; ;vr). ; vrg be two Proof. Assume from the contrary that there exist two distinct r-tuples (u1; u2; ; ur) and (v1; v2; ; vr) such that S(u1;u2; ;ur) = S(v1;v2; ;vr).

Remember that every set Sj is a line, every S(u1;u2; ;ur) is a union of lines and the two sets fu1; u2; ; urg and fv1; v2; ; vrg have the same cardinality. Since the sets fu1; u2; ; urg and fv1; v2; ; vrg are distinct, there exists a number j 2 Q such that j 2 (u1; u2; ; ur) (v1; v2; ; vr). Then S(u1;u2; ;ur) contains all the points from fp(j i)q+2; p(j i)q+2; ; pjq+1g. The line lj is the only line which contains at least two of these points. If j 2= fv1; v2; ; vrg then each of these q points enters S(v1;v2; ;vr) via a different line. Contradiction with the cardinality of the set fv1; v2; ; vrg. tu Lemma 8. There are 2q log q distinct sets S(u1;u2; ;uq 1) in Uq;q 1. Proof. By Lemma 7, the number of distinct sets S(u1;u2; ;uq 1) is equal to the cardinality of Rq 1. i.e. to (q2+q+1)((qq2+1q))((qq2 +2)q 11) (q2 1) . By Stirling formula, this is at least equal q2qqqeq = 2q log q. tu Comment. There are q2 + q + 1 sets in the collection S. The number of distinct sets S(u1;u2; ;uq 1) is quite impressive 2q log q: However, Lemma becomes invalid if we substitute r q 1 by r = q + 1.

Theorem 1. For arbitrary prime q, the family S = fS1; S2; : : : ; Sq2+q+1g is a [q 1; q; q2 + q + 1]-superimposed code.

Proof. By Lemmas 6 and 7.

tu

Decision Trees

We wish to use superimposed codes to prove advantages of probabilistic decision trees over deterministic decision trees.

A deterministic decision tree is a rooted ordered binary tree T . Each internal node of T is labeled with a variable xi and each leaf is labeled with a value 0 or 1. Given an input x 2 f0; 1gn, the tree is evaluated as follows. Start at the root. If this is a leaf then stop. Otherwise, query the variable xi that labels the root. If xi = 0 then recursively evaluate the left subtree, if xi = 1, then recursively evaluate the right subtree. The output of the tree is the value (0 or 1) of the leaf that is reached eventually. Note that an input x deterministically determines the leaf, and thus the output, that the procedure ends up in.

We say that a decision tree computes f if its output equals f (x), for all x 2 f0; 1gn. Clearly there are many different decision trees that compute the same f . The complexity of such a tree is its depth, i.e., the number of queries made on the worst-case input. We define D(f ), the decision tree complexity of f as the depth of an optimal (= minimal-depth) decision tree that computes f .

As in many other models of computation, we can add the power of randomization to decision trees. We add coin flips as internal nodes to the tree. That is, the tree may contain internal nodes labeled by a bias p 2 f0; 1g, and when the evaluation procedure reaches such a node, it will flip a coin with bias p and will go to the left child on outcome “heads" and to the right child on “tails". Now an input x no longer determines with certainty which leaf of the tree will be reached, but instead induces a probability distribution over the set of all leaves. Thus, the tree outputs 0 or 1 with a certain probability. The complexity of the tree is the number of queries on the worst-case input and worst-case outcome of the coin flips.

Definition 10. We say that a randomized decision tree computes f with bounded

error if its output equals f (x) with probability exceeding 12 , for all x 2 f0; 1gn.

R(f ) denotes the complexity of the optimal randomized decision tree that computes f with bounded error.

We introduce 2 functions for which we consider deterministic and randomized decision trees. Let q 2 be a prime number. We denote q2 + q + 1 by Q. As in Definition 2, the projective plane P roj(q) consists of points (p1; p2; ; pQ) and lines (l1; l2; ; lQ).

The Boolean function F1Q(x1; x2; : : : ; xQ) equals 1 if and only if there exists a line li 2 P roj(q) such that for every point pj 2 li the value xj = 1.

The function F2Q(x1; x2; : : : ; xQ) equals i if and only if there exists a line li 2 P roj(q) such that for all xj = 1 if and only if j 2 li. Otherwise F2Q(x1; x2; : : : ; xQ) = Q + 1.

Theorem 2. (trivial) D(F1Q) = Q and D(F2Q) = Q.

Theorem 3. R(F17)

Theorem 4. R(F1Q) Theorem 5. R(F2Q)

R. Freivalds [ 11 ] introduced a new type of automata and algorithms, called ultrametric automata and ultrametric algorithms where p-adic numbers are used to replace real numbers, called probabilities, as measures of indeterminism. More detailed description of this notion can be found in [ 1 ]. The properties of ultrametric algorithms corresponding to distinct primes p may be surprisingly different.

Definition 11. We say that an p–ultrametric decision tree computes f with

bounded-error if for all x 2 f0; 1gn its output equals f (x) with probability exceeding 21 .

Up(f ) denotes the complexity of the optimal p–ultrametric decision tree that com

putes f with bounded error.

Theorem 6. For arbitrary odd prime number p the complexity Up(F1Q) Theorem 7. For arbitrary odd prime number p the complexity Up(F2Q) q + 1. q 1.

References

1. A¯damsons, V., J ¯erin¸š, K. , Krišlauks , R. , Lapin¸a, M. , Pakulis , A. , Freivalds , R.: Advantages of ultrametric counter automata . In Proceedings of SOFSEM 2015 , vol. 2 ( 2015 )

2. Bach , E. and Shallit , J.: Algorithmic Number Theory . MIT Press ( 1996 )

3. Buhrman , H., de Wolf, R.: Complexity measures and decision tree complexity: a survey . In Theoretical Computer Science , vol. 288 , No. 1 , pp. 21 - 43 ( 2002 )

4. Dembowski , P. : Finite geometries. Springer ( 1968 )

5. D 'yachkov , A.G. , Rykov , V.V.: Bounds on the length of disjunct codes . In Problemy Peredachi Informatsii (in Russian) , vol. 17 , pp. 7 - 13 ( 1982 )

6. D 'yachkov , A.G. , Macula , A.J. , Rykov , V.V. : New constructions of superimposed codes . In IEEE Transactions on Information Theory , vol. 46 , pp. 284 - 290 ( 2000 )

7. D 'yachkov , A.G. , Macula , A.J. , Rykov , V.V. : New applications and results of superimposed code theory arising from the potentialities of molecular biology . In Numbers, Information and Complexity , Kluwer Academic Publishers, Dordrecht, pp. 265 - 282 ( 2000 )

8. Erdös , P. , Frankl , P. , Füredi , Z. : Families of finite sets in which no set is covered by the union of r others . Israel Journal of Mathematics , vol. 51 , No. 1 - 2 , pp. 79 - 89 ( 1985 )

9. Freivalds , R.: Probabilistic Two-Way Machines . In Lecture Notes in Computer Science , vol. 118 , pp. 33 - 45 ( 1981 )

10. Freivalds , R.: On the growth of the number of states in result of the determinization of probabilistic finite automata. Avtomatika i Vichislitel'naya Tekhnika (Russian) , No. 3 , pp. 39 - 42 ( 1982 )

11. Freivalds , R.: Ultrametric finite automata and Turing machines . In Lecture Notes in Computer Science , vol. 7907 , 1 - 11 ( 2013 )

12. Füredi , Z. : A note of r-cover-free families . Journal of Combinatorial Theory, Ser. A 73 , 172 - 73 ( 1996 )

13. Kautz , W.H. , Singleton , R.C. : Nonrandom binary superimposed codes . In IEEE Transactions on Information Theory , vol. 10 , pp. 363 - 377 ( 1964 )

14. Kunc , M. , Okhotin , A. : State complexity of union and intersection for two-way nondeterministic finite automata . In Fundamenta Informaticae , vol. 110 , No. 1 - 4 , pp. 231 - 239 ( 2011 )

15. Quang , A.N. , Zeisel , T. : Bounds on constant weight binary superimposed codes . In Problems of Control and Information Theory , vol. 17 , pp. 223 - 230 ( 1988 )

16. Nisan , N.: CREW PRAMs and decision trees . SIAM Journal of Computing , vol. 20 , No. 6 , pp. 999 - 1007 ( 1991 )

17. Ruszinko , M. : On the upper bound of the size of r-cover-free families . Journal of Combinatorial Theory, Ser. A 66 , pp. 302 - 310 ( 1994 )

18. Saks , M.E. , Wigderson , A. : Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees . In Proceedings of the 27th Annual Symposium on Foundations of Computer Science , pp. 29 - 38 ( 1986 )

19. Santha , M. : On the Monte Carlo Boolean decision tree complexity of read-once formulae . In Random Structures and Algorithms , vol. 6 , No. 1 , pp. 75 - 87 ( 1995 )

20. Stinson , D.R. , Wei , R. , Zhu , L.: Some new bounds for cover-free families . Journal of Combinatorial Theory, Ser. A 90 , pp. 224 - 234 ( 2000 )