Algebra and Geometry of Sets in Boolean Space

Vladimir Leontiev¹, Garib Movsisyan^2*, Zhirayr Margaryan³

¹Moscow State University, Moscow, Russia.
²BIT Group, Moscow, Russia.
³Yerevan State University, Yerevan, Armenia.

DOI: 10.4236/ojdm.2016.62004                

Abstract

In the present paper, geometry of the Boolean space Bⁿ in terms of Hausdorff distances between subsets and subset sums is investigated. The main results are the algebraic and analytical expressions for representing of classical figures in Bⁿ and the functions of distances between them. In particular, equations in sets are considered and their interpretations in combinatory terms are given.

Keywords

Equations on Sets, Hausdorff Distance, Hamming Distance, Generating Function, Minkowski Sum, Sum of Sets

Received 16 October 2015; accepted 28 March 2016; published 31 March 2016

1. Distance between Subsets Bⁿ

Let, and be the set of all words of finite length in the alphabet B. For we take:

It is clear that is the Hausdorff distance between the subsets and, and is the Hamming distance between the points:, where and is the addition operation with respect to mod 2.

The Hausdorff distance has essential role in many problems of discrete analysis [1] and thus has certain interest. On the other hand, there only are a few essential results concerning distances between the subsets, and their investigation offers significant difficulties.

First, we present the following simple properties of the Hausdorff distance:

1);

2);

3) Если, то;

4), for.

Let us note that, generally speaking, the Hausdorff distance does not satisfy the triangle inequality:

(1)

which is demonstrated in the following picture:

But inequality (1) holds true if.

Distance between Spheres in Bⁿ

Let be a sphere of radius p with the center at. We take, for an arbitrary subset,:

Thus, we have the following two equvalent interpretations for:

1) is the set of all points in which are at the distance from the set М;

2) is the set of all points in, covered by the spheres of the radius p with the centers at points of the set M.

Examples.

1), for an arbitrary point:;

2), for an arbitrary;

3) If and then p is the radius of the covering of the set [2] .

Theorem 1..

Proof. We consider two cases.

a) Then,

and, consequently,

b) Let We present them in the form:

where

where

From here we have:

As consequently we have:

Then, taking into account that:

,

we have:

The theorem is proved.

Let:

Taking into account that the sphere of the radius p with the center at and the sphere of the radius q with the center at contain, respectively, as many points as:

,

we get the following corollary.

Corrollary. If, then:

The value of the function for definite values of was calculated in [1] .

Theorem 2. If, then:

The general form of the standard generating function for the distance between the subsets has the following form:

(2)

The summation in (2) is over all pairs of the subsets with

Let us consider a few examples.

1).

In this case, we have:

Thus, , which is the well-known function of distribution of distances between the points in the space with the metrics of Hamming.

2), and q is an arbitrary positive integer which does not exeed.

In this case:

(3)

As:

for arbitrary points and any subset, then we get from (3):

Then:

(4)

Consequently, the distance between the zero point and an arbitrary subset Y equals the minimal weight of the points which are in Y.

Hence, , if there are not points with in Y. The numbers of subsets Y with and the condition are found by the following formula:

, (5)

where

where is the cardinality of the sphere with the radius r in

From (5), we get the following statement:

Lemma1. If is the number of the subsets of cardinality q (in) having the distance to the zero point, then:

For

Theorem 3. The following formula holds true:

(6)

Proof. By definition:

From this and Lemma 1, taking into account (3) and (4), we get:

The theorem is proved.

If is the generating function of the random value uniformly distributed on the pairs, where, then the following holds true.

Corollary 1. The following formula holds true:

Corollary 2. The following holds true:

Corollary 3. The formula for follows from (6).

Proof. From (6) we get for p = 1:

Corollary 4. For q = 2, the following formula holds true:

Proof. By definition and from Corollary 2, we derive:

(7)

Transforming the terms in (7), we get:

(8)

Then, using the following formulas:

Let us “compress” the sum:

By definition, we have:

Furthermore, if:

then:

Further:

And:

From here it follows that

Then:

Taking this and (8) into account, we get:

And the generating function:

can be expressed by the following parameters:

2) if then the family of all subsets of cardinality p, having distances from M is expressed as

. Indeed, contains all the points of, having distances from the set M.

Hence, the set does not contain such points; consequently, for an arbitrary subset

, the expression holds true.

The cardinality of this family is:

.

2) The number of all m-element subsets having the distance r from M is:

Summarizing all the previous, we get the following statement.

Theorem 4. The following expression is true:

2. Sum of Sets in

Let; we take:

The operation “+” is defined in the family of all subsets of and (, “+”) is a monoid with the neutral element [3] [4] .

Besides, the following inequality holds true:

Here both limits are reachable.

The properties of “+” are as follows:

1)

2) for all;

3) -associativity;

4) -communacativity;

5) -distributivity;

6);

7).

Examples.

If X is a subspace in, then:

1);

2) if

Let the following holds true:

.

Then

Thus, there is certain analogy between the norm of the sum of points and the distance between those points, as well as between the norm of the sum of the sets and the distance between those sets.

In the general form, the following statement connecting the operations “∪” и+, is true:

2.1. Sum of Facets in Bⁿ and the Distance between Them

A facet or interval in is the set of points where the partial order is defined in the classic way [5] [6] :

for

Every interval J can be written in the form of a word of the length n, in the alphabet the letters of which are ordered linearly:

Examples.

If and then every point of J can be presented by the word, which means the following: all the points which are obtained from the word by the substitution either 0 or 1 for a letter of the given word, are contained in the interval J. Consequently, the cardinality of the interval J is for the given case, i.e. Hence, each interval J has its corresponding code word in the alphabet A. The number of letters c in the code is the dimension of the interval J, i.e. is And the following formula is obvious:

If the operation “*” is introduced on the alphabet A:

then the sum of the intervals and is the Minkowski sum:

.

Examples.

1) If then i.e. which corresponds to the definition of the sum

2) If, then for every interval

The distance between the intervals and, having the codes and -taking into account the introduced definitions-are calculated in the following way.

Let be the number of occurrences of letter 1 in the code of the interval J.

Statement 1.

Thus, the distance between the intervals and is the number of occurrences of letter 1 in the code of their sum.

Examples.

1) Let.

Then and

Let be the family of all p-dimensional intervals of Then

Let us consider the direct product and introduce uniform distribution on it with the generating function:

Theorem 5. The following formula is true:

where

Let us consider the matrix the rows of which are the codes of the intervals from the family

Lemma 2. The following expression is true:

where is the number of zeros and, respectively, units in the i-th column of the matrix

Proof. According to the definition:

(9)

where

and is the code of the interval.

It follows from (9):

(10)

The internal sum in (10) equals the number of such pairs in which one of is unit and the other is zero, i.e. is The Lemma is proved.

Example.

1) Let be the family of all edges in. We consider the matrix of their codes:

The total number of the edges in is. Each column of the matrix has the length 12, and

all letters of the alphabet occur in equal number, 4 times. Therefore, ,

From here, we get:

2) In the general form, if is the family of all edges in, each column contains letters c and

From here, we get:

(11)

Thus, the sum of the pairwise distances between the intervals in is calculated by formula (11).

2.2. The Sum of Spheres in Bⁿ

In the general form, the following statement holds true.

Lemma 3. The following formula is true:

Proof. By definition:

Thus, the above introduced parameter of the setМis rather easily expressed in the terms of the operation “+”.

Lemma4. if.

Proof. If, then either v is at the distance from or there is a point such that.

Then, from it follows that, for all.

From here we get:

or:

.

Hence,

And if, then there is a point such that.

Hence, and, consequently, , that is, , and the proof is completed.

Theorem 6. The following expression is true:

(12)

Proof. We have from Lemma 4:

.

Then, we have from Lemma 3:

And the proof is over.

Formula (12) defines the rule of “addition” for arbitrary spheres in the space.

2.3. Sum of Layers in Bⁿ

Let be the p-th layer of the n-dimensional cube, or be the sphere of the radius p with the center at zero [7] [8] .

According to definition, is the sum of the layers in or it is the sum of the points with the weights p and q. As, then all points from have weights from the interval.

Then, the following statement is true.

Lemma 5. The following expression holds true:

Proof. First, let us note the following.

If, and, then. Consequently, every layer is invariant with respect to the operation of the symmetric group and, for, we have:

, where.

In standard terms, the symmetric group operates on and every layer is a transitive set or an orbit of action of the group.

If, then, where. Therefore, for each permutation we have: and we get:

и.

Taking this into account, to describe the set it is sufficient to describe only the weights of the points which are included into this sum. The minimal weight of these is.

We discuss the following outline:

Here and the “block” of the first 2 units is shifted by a unit in each consecutive word. Thus, we get all weights:

In the general case, the situation is absolutely analogous, and the weights are arranged as follows:

for

Here the condition for z holds true:

.

Examples.

1);

2);

3).

Theorem 7. The following expression is true:

where

Proof. From Lemmas 3 and 5, we have:

The proof is over.

2.4. Sum of Subspaces in Bⁿ

As usual, let be the subspace generated by the vectors from the set X, or be the space “worn” on X.

Statement 2.,

and:

Statement 3. Let

And if:

(13)

then the following equality is true:

Proof. We assume the contrary, that is,

Then, we have:

and.

Hence, Consequently, That is,

This contradicts the initial condition and the proof is over.

The following example shows that condition (12) is not necessary.

Example.

Let Then although

3. Equations in Sets

The “simplest” equation by sets is the following:

(14)

where.

Equation (14) always has the trivial solution: where

The significance of Equation (14) is explained by the following circumstances.

1) The standard problems of covering and partitioning in the Boolean space Bⁿ [6] can be formulated as problems of describing the set of solutions of Equation (14).

2) For certain additional conditions, the solution of Equation (14) forms a perfect pair (perfect code) in the additive channel of communication [9] .

3) The set of all solutions of Equation (14) coincides with the class of equivalence of the additive channel of communication [3] .

Examples.

1) If, we can take as the solution for Equation (14).

2) If A is a subspace of, then Equation (14) has the following solution:.

The following statements are true:

Statement 4. If the equations are solvable, then the equation also is solvable.

Proof. Let the pairs be the solutions of the equations and, respectively. Then for the pairs we have

as was required to be proved.

Statement 5. For the equation:

has the solution

Statement 6. For and the equation has the following solution:

,

where

Statement 7. For, the equation has the following solution:

where

Statement 8. The sets of solutions of the equations and coincide for all

Below, when discussing Equation (14), without violating generality, we may assume if necessary.

Statement 9. The equation has no solution for

Proof. If and, for we have and or. Thus, X is an equidistant code [2] , therefore,. Consequently:

From here it follows that the equation has no solution for, if.

Statement 10. The equation (in “facets”, i.e. X, A are facets in) is solvable iff the code of the interval A does not contain the letter 1.

Let be a solution of the equation As the following equality:

holds iff:

и,

then the following statement is true.

Statement 11. If is a solution of the equation, then is a solution of the equation iff and.

Statement 12. If A is a subspace from then every subset is a solution of the equa-

tion

In an additive channel of communication [3] an equivalence class has a unique representation by transitive sets of certain “generating” channels. The problem is to order these transitive sets by cardinalities of “generating” channels.

Let

We introduce the following parameters:

,

Such definition of is justified, because it is not always that the equation has solutions for instance, if or for), though the equation always has a solution.

One can easily prove that:

(15)

Statement 13. For the subspace the following is true:

.

Proof. It follows from (15) that it is sufficient to prove that the following equality is true:

Let be a solution of the equation for which:

(16)

On the other hand, it follows from Statement 11 that is a solution of the equation and, consequently, Taking this and (16) into account, we get:

Theorem 8. The following estimations are true:

1) for

2) for the subspace for

Proof. We have:

From this and definition of addition of sets we get:

Consequently:

To prove the 2nd estimation, we consider such subspaces for which the following is true:

.

Let:

where,

Let us prove that.

We have:

As (Statement 12) we get:

Then, using:

we get:

Hence, taking this and Statement 13 into account we get:

The statement is proved.

Examples.

1) We have:

2). We have:

but actually:

3) We have:

We consider the set:

We have: Hence,

4)

We have:

and.

But actually

Suggestion. For each the following is true:

where

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Nigmatulin, R.G. (1991) Complexity of Boolean Functions. Moscow, Nauka, 240 (in Russian).
[2]	McWilliams, F.J. and Sloane, N.J.A. (1977) The Theory of Error-Correcting Codes, Parts I and II. North-Holland Publishing Company, Amsterdam.
[3]	Leontiev, V.K. (2001) Selected Problems of Combinatorial Analysis. Bauman Moscow State Technical University, Moscow, 2001 (in Russian).
[4]	Leontiev, V.K. (2015) Combinatorics and Information. Moscow Institute of Physics and Technology (MIPT), Moscow, 2015 (in Russian).
[5]	Leontiev, V.K., Movsisyan, G.L. and Osipyan, A.A. (2014) Classification of the Subsets Bn, and the Additive Channels. Open Journal of Discrete Mathematics (OJDM), 4, 67-76.
[6]	Leontiev, V.K., Movsisyan, G.L., Osipyan, A.A. and Margaryan, Zh.G. (2014) On the Matrix and Additive Communication Channels. Journal of Information Security (JIS), 5, 178-191.
[7]	Leontiev, V.K., Movsisyan, G.L. and Margaryan, Zh.G. (2012) Constant Weight Perfect and D-Representable Codes. Proceedings of the Yerevan State University, Physical and Mathematical Sciences, 16-19.
[8]	Movsisyan, G.L. (1982) Perfect Codes in the Schemes Johnson. Bulletin of MSY, Computing Mathematics and Cybernetics, 1, 64-69 (in Russian).
[9]	Movsisyan, G.L. (2013) Dirichlet Regions and Perfect Codes in Additive Channel. Open Journal of Discrete Mathematics (OJDM), 3, 137-142.