On Addition of Sets in Boolean Space

Vladimir Leontiev¹, Garib Movsisyan², Zhirayr Margaryan³

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

DOI: 10.4236/jis.2016.74019                

Abstract

In many problems of combinatory analysis, operations of addition of sets are used (sum, direct sum, direct product etc.). In the present paper, as well as in the preceding one [1], some properties of addition operation of sets (namely, Minkowski addition) in Boolean space Bⁿ are presented. Also, sums and multisums of various “classical figures” as: sphere, layer, interval etc. are considered. The obtained results make possible to describe multisums by such characteristics of summands as: the sphere radius, weight of layer, dimension of interval etc. using the methods presented in [2], as well as possible solutions of the equation X+Y=A, where  , are considered. In spite of simplicity of the statement of the problem, complexity of its solutions is obvious at once, when the connection of solutions with constructions of equidistant codes or existence the Hadamard matrices is apparent. The present paper submits certain results (statements) which are to be the ground for next investigations dealing with Minkowski summation operations of sets in Boolean space.

Keywords

Hadamard Matrices, Minkowski Addition, Multiset, Cardinality, Multisum, Interval, Quadrate, Boolean Space, Stabilizer, Additive Channel

Received 11 May 2016; accepted 16 July 2016; published 19 July 2016

1. Sum of Sets According to Minkowski

If, are points in, where, is a Boolean space, then:

where is the mod 2 addition operation.

This addition operation for members of can be extended in subsets of.

In other words, if, then:

(1)

Thus, the sum of subsets is consisted of sums of points belonging to X and Y, respectively.

Examples.

1. if, then is the “shift” of the set X to the point y, and.

2. if X is a subset in, then.

3. for any.

Also, can be interprated as union of “shifts” of the sets X onto points of the sets Y.

The family, with an introduced Minkowski addition operation “+” forms a monoid with the neutral element, which is one member set having the zero element of.

The following inequality is valid:

Both limits are achievable here. The following statements describe the sets in which these limits are achieved.

Definition [2] . The pair is called additive if for any and the following is valid:

Statement 1. The upper limit is achieved if is an additive pair.

Corollary. If then for all

We consider an arbitrary subgroup and the action of this subgroup on the family:

,

where. Thus, G acts on with shifts transferring the subset into its “shift”.

Definition [3] . A stabilizer of the set X with respect to the group G is the union of “shifts” from G, conserving X, i.e. for all.

Statement 2. The lower limit is achieved if there exists, for which or.

Corollary. If, then for all.

Now let and.

Example.

1. If is a group of shifts, then for the following is valid:

In this case X has a non-obvious stabilizer if all constituents of X can be partitioned into the pairs, , i.e. with respect to. For we get. It is clear that in this case and. Thus, all subsets of X, having a non-obvious stabilizers, are described above.

In the general form the stabilizer for an arbitrary group G and an arbitrary set can be described in the following terms [3] .

Statement 3. The constituent if the set X can be partitioned into the pairs in such a way that for all pairs which are included in the partition.

This statement can be obtained by analogical consideration for as in [4] .

From the above statement one can construct the following algorithm for building the stabilizer of an arbitrary set X for the subgroup, acting on. And at same time.

1. First we build the multiset.

2. Then we choose all the pairs in C having the multiplicity m.

3. Then we build all partitions in A out of these pairs.

4. If is the set of all partitions of X having the same weights in pairs, then

.

Example.

1. Let.

Then:

This means that all pairs have the multiplicity 2 in the sum. Then we have:

.

The sum of the pairs in each of the solutions is the same. Hence, the following set:

is a stabilizer for X.

Below we present the simple properties of the operation “+”―it is addition in the sense of Minkowski, as was mentioned above―which can be taken as properties of an algebraic system with basic set and those for operations of addition, union of sets, set intersection etc.

1. Assosiativity:

2. Commutativity:

3. Distributivity with respect to union:

4.

There are finitely many other relations connecting constituents of the algebraic system described above.

1.1. Sum of Spheres in Bⁿ

Let be the Hamming distance between the points and be the set of the points of the sphere of the radius t with the centre at the point. In other words, is the sphere of the radius t having the point v as its centre. And at that, for all.

Statement 4 [1] .

(2)

Statement 5.

Here is the set complement of the sphere in and is the logic “negation” of the binary set v. We assume that, for

Proof. Let us note that if, then. As:

,

then for we have:

or:

and if, then.

Example.

1. We consider the sphere. Then.

Formula (2) in the preceding statement allows the following generalization connected with addition.

Let and be the set of points belonging to the union of spheres of the radii p with the centres at the points M, that is:

is the “generalized” sphere of the radius p having its centre at the point M.

Statement 6 [1] . The following presentation is valid:

.

Corollary. For the following take place:

1.

2.

Statement7 [1] . The following relation is valid:

for

and the next one is valid:

for.

Corollary. For the following is valid:

1.2. The Sum of Facets in Bⁿ

A facet, or sub-cube, or interval in is the set of points satisfying the following condition [5] [6] :

,

where (≤) is a coordinate-wise partial order relation in:

, , where,.

In other words, an interval can be given by a word of the length n in the alphabet, the letters of which are ordered linearly:.

Indeed, if:

then the code of the interval J is built in the following way.

Let. Then:

Examples.

1. If, then

2. If, then.

If is the code of the interval J, then all points of the interval J are obtained from the code by replacing the letters in an arbitrary way by zeros or units.

Let and be the numbers of letters 1 and c, respectively included in which is the code of the interval J. it is clear that is the dimension of J, i.e. and.

If the operation “⋆” is introduced in the alphabet A by the following Caley table [7] :

then the sum of the intervals J of the system defined above as a sum of subsets is the interval the code of which is calculated by the codes of items (addends) using the above Caley table.

Statement 7 [1] . The sum is an interval with the code and dimension

Examples.

1. If, then.

On the other hand, we get by definition:

,

i.e..

2. If, then for any interval.

Statement 8 [1] . where is the Hausdorff distance between the sets [8] .

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

1.3. Sum of Layers in Bⁿ

Let be the p-th layer of an -dimensional cube or sphere of the radius p and the centre at zero [9] [10] .

By definition is the sum of layers in, consisting of the union of sums of the points one of which has the weight and the second has the weight q. It is clear that the symmetrical group operates on each layer in the following manner:

if, then.

Hence, g permutes the coordinates of the point , leaving its Hamming weight unchanged.

At the same time the relation is valid for.

Thus, each layer is a transitive set or an orbit of operation of the group on the cube.

Let,.

Statement 9 [1] . The following formula is valid:

(3)

For not large values of the layer the following table of addition is valid:

Note that Formula (3) can be rewritten for any number of terms, using the above-mentioned property of distributivity.

Indeed, using (3), we get:

which makes possible to use (3) again.

Example.

1. Let us find the sum. We have:

NB. As each layer is a sphere of the radius p and the centre at zero point, then all the preceding formulae are rules of ‘sphere’ addition.

1.4. Sum of Subsets in Bⁿ

If we take subspaces in as terms of the sum, we will get a well-known object. Indeed, if is a subspace in, then is a subspace, too, and we have:

,

in terms of cardinality:

Thus, “theory of addition of subspaces” being a well-developed part of linear algebra, makes possible to answer many questions concerning the subject problem.

1.5. Sum of Spheres in Bⁿ

The k-dimensional interval we denote by.

According to statement 6, we have:

i.e. is the union of all spheres of the radii t with centres at the points in the interval, or:

Let

Statement 10..

For the cardinality of the set the following is true:

Corollary., where is the cardinality of the sphere of the radius in.

Proof. If, for any point the following is valid:

if Indeed, in this case belongs to the sphere of the radius t with the centre at. Inversely, if and then for any point y in the interval, that is:

Therefore,

1.6. Sum of a Layer and an Interval in Bⁿ

Analogous to the preceding statement and corollary we get the sum of the sets.

Statement 11. The following relation is valid:

Corollary. The cardinality of the set is calculated as follows:

1.7. Sum of a Sphere and a Layer in Bⁿ

Statement 12. The following is valid:

where

Proof. We have from statements 9 and 6:

Q.E.D.

2. Equation in Sets

Let be the monoid of all subsets with operation of addition (1) in as was defined above. This monoid is of certain interest both in classical discrete analysis [8] and for a number of problems connected with theory of information [4] .

The ‘simplest’ equation in sets is as follows:

(4)

where

It is clear that Equation (4) always has the trivial solution

Examples.

1. If, then one can choose for X, and any subset of for Y.

2. If A is a subspace of, then and, therefore, Equation (4) has the solution

3..

Now, let:

.

Then; consequently, the Hausdorff distance between the sets X and Y:

is expressed by the norm of the sum of these solutions.

On the other hand, if:

then is the reciprocal spectrum of the distance between the points of the sets X and Y and:

that is, is the spectrum of the distance between the points of the set X, or rather, the spectrum of X.

Thus, the set describes, to a considerable extent, the set of distances between the points of X or the spectrum of X.

In an additive channel of communication [4] the class of equivalence has one to one presentation by transitive sets of certain ‘generating’ channels. The problem is to order these transitive sets through cardinalities of ‘generating’ channels. We need the following numerical parameters, which depend on solutions of Equation (4) and on the right hand side of A.

Let

We introduce the following parameters:

,

,

Introduction of such definitions as and is explained by the fact that the equation can sometimes have no solution (for instance, for or for), though the equation always has a solution.

Then, for the minimal and maximal cardinality set, where we get respective boundary values, which make possible to narrow the region, i.e. the region of the set of solutions of Equation (4) (we shall see this below).

It is not hard to prove that:

(5)

As every solution of the equation is a solution for (4), then we present the following useful statement which makes possible to obtain solutions of the equation from solutions of the Equation (4), under certain limitations.

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

Statement 14. For the subspace the following is valid:

(a)

(b).

Proof. It follows from (5) that it is sufficient to prove for (a) that:

Let is a solution of the equation, for which:

(6)

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

The proof for the case (b) is analogical.

Statement 15. The following estimations are valid:

1. for the subspaces for

2. for

3. If is a subspace, then equality in takes place if dim A = 1, 2 or 4.

Proof. Items 1 and 2 of this statement were proved in [1] , and we prove only item 3.

Necessity. We assume that:

(7)

and that the pair is a solution for the equation

It follows from (7) that:

(8)

According to the statement, we have that the set is a solution for the equation as well. We consider a Boolean matrix having points from in its rows. We denote by the number of units in the i-thcolumn of this matrix. As A is a subspace, then the following equality is true: i.e. and Consequently, This and (8) give:

(9)

For and this equation has no solution for every k. Consequently, or Now it is easy to find the solution of Equation (9): or 4.

Sufficiency. Let be the basis for the space. We consider the following sets:

As then for we have:

.

The statement is proved.

Examples.

1. The pair where is a solution of the equation: for

2. The pair where is a solution of the equation: for

If we keep to these examples, then we can assume that there exists some monotonous dependence of the function on the cardinality A. But one can manage to find the possible connection between the right hand side of Equation (4) and the function for the case if A is the halfspace.

Corollary. For the halfspace the inequality is valid if.

The “seemingly obvious” hypothesis that the upper limit of is reached for all is refuted by the following examples.

Examples.

1. Let. In this case there is no solution of Equation (4), satisfying the condition: Consequently, since for the following is valid:

and the upper limit is reached in this example.

2. Let = {(0 0 0 0 0 0 0), (0 0 0 0 1 0 0), (0 0 0 0 1 1 0), (0 0 0 1 1 0 1), (0 0 1 0 0 0 1), (0 0 1 0 1 1 1), (0 1 0 0 0 0 0), (0 1 0 0 1 0 0), (0 1 1 0 1 0 0), (0 1 1 0 1 0 1), (0 1 1 1 0 1 1), (0 1 1 1 1 0 0), (0 1 1 1 1 1 0), (1 0 0 0 0 1 0), (1 0 0 1 1 0 1), (1 0 0 1 1 1 0), (1 0 1 0 0 0 0), (1 0 1 1 0 1 1), (1 1 0 0 1 0 1),(1 1 0 1 1 0 0)}.

We have: Consequently, the upper limit is not reached in this example.

Statement 16 [11] . If, then the solution of the equation is an equidistant code with a distance between any two points equal k, and At the same time if there exists a Hadamard matrix of the order [12] .

Consequently, the problem of constructing of an equidistant code with the distance k having the minimal cardinality can be formulated in terms of solvability of the equation.

Definition. The set is called a quadrate if the following equation:

(10)

is solvable.

It is clear that a quadrate always contains the zero point.

Example.

1. If A is a halfspace in, then, as it was mentioned above, and, therefore, A is a quadrate. If, , then A is a quadrate if i.e.

The notion of ‘quadrate’ is connected with problems of equivalence of additive channels [4] where description of the class of equivalence is connected with finding of all solutions of the following equation:

.

Let:

We denote by the cardinality of the maximal code with the minimal distance d [6] .

Statement 17..

From this and taking into account the known estimations (the upper limit; see [6] ) we get:

Statement18.The following inequality is valid:

At the same time equality takes place if there exists a perfect code in with the minimal distance d.

Consequently, the problem of constructing the code of maximal cardinality ? in particular, a perfect code ? is reduced to finding the solution of maximal cardinality for Equation (10) among all quadrates of the union of layers.

Statement 19 [1] . If is a quadrate, then is a quadrate too.

Corollary. The preceding statement is valid for any number of summands.

Now let be a group of invertible matrices having components in the field.

Definition. The set of matrices is called stabilizer of the set if all matrices in conserve A, i.e., where.

At the same time, if, then.

Statement 20. Let be a stabilizer of the set and. Then the pair is the solution of the equation, as well.

3. Multisets

The second definition of addition of sets from is connected with multiplicity of containing each member into the sum [4] .

Definition. A multisum of two sets is called multiset:

(11)

in which each member is counted as many times as it comes in sum (11), and is the multiplicity of the member.

Examples.

1. If, then.

2. If, , then.

It is clear that by definition, in which the cardinality of the multiset is the sum of the multiplicities of its members.

In particular, the following expression is valid:

where C is an arbitrary subset in and is the multiplicity of the constituent.

It follows from this that:

Let

Statement 21. For the multiset the following formula is valid:

(12)

where is the multiplicity of the member of the multiset with the weight.

Proof. Let z be any member of the multiset Since:

and is an even number, then always is presentable in the form:

We assume (without violating generality) that:

where and,

Hence, we have:

,

that is:

From this, taking into account Statement 9, we get Formula (12).

Corollary. For we have:

а)

b)

if and:

c)

if

Statement 22. For the multiset the following is valid:

where; and at the same time:

is the multiplicity of the members of.

Corollary. For the following is valid:

a)

b)

Statement 23. For the multiset the following equality is valid:

where and at the same time:

is the multiplicity of the members

Corollary. For the following equality is valid:

Statement 24. For the multiset the following formula is valid:

where is the multiplicity of x.

Corollary. For the following is valid:

Statement 25. For the multiset the following formula is valid:

where and at the same time:

is the multiplicity of.

Corollary. For the following is valid:

Statement 26. For the multiset the following is valid:

,

where, is the interval with the code:, and is the multiplicity of the members of.

Finally, we define the operation “/”, that is, subtraction for multisets.

Let.

Definition.

Example. We consider the multisets:

From Statements 22 and 12 we get:

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Leontiev, V.K., Movsisyan, G.L. and Margaryan, Zh.G. (2016) Algebra and Geometry of Sets in Boolean Space. Open Journal of Discrete Mathematics (OJDM), 6, 25-40.
[2]	Movsisyan, G.L. (2013) Dirichlet Regions and Perfect Codes in Additive Channel. Open Journal of Discrete Mathematics (OJDM), 3, 137-142.
[3]	Sachkow, W.N. (1977) Combinatory Methods of Discrete Mathematics. Nauka, Moscow. (In Russian)
[4]	Leontiev, V.K., Movsisyan, G.L. and Osipyan, A. (2014) Classification of the Subsets and the Additive Channels. Open Journal of Discrete Mathematics (OJDM), 4, 67-76.
[5]	Leontiev, V.K. (2001) Selected Problems of Combinatorial Analysis. Bauman Moscow State Technical University, Moscow. (In Russian)
[6]	Leontiev, V.K. (2015) Combinatorics and Information. Moscow Institute of Physics and Technology (MIPT), Moscow. (In Russian)
[7]	Lang, S. (1968) Algebra. Moscow, Mir. (In Russian)
[8]	Nigmatulin, R.G. (1991) Complexity of Boolean Functions. Nauka, Moscow, p. 240. (In Russian)
[9]	Movsisyan, G.L. (1982) Perfect Codes in the Schemes Johnson. Bulletin of MSY, Computing Mathematics and Cybernetics, 1, 64-69. (In Russian)
[10]	Leontiev, V.K., Movsisyan, G.L. and Margaryan, Zh.G. (2012) Constant Weight of Perfect and D-Representable Codes. Proceedings of the Yerevan State University, Physical and Mathematical Sciences, 16-19.
[11]	McWilliams, F.J. and Sloane, N.J.A. (1977) The Theory of Error-Correcting Codes. Parts I and II, North-Holland Publishing Company.
[12]	Delsarte, P. (1973) Four Fundamental Parameters of a Code and Their Combinatorial Significance. Information and Control, 23, 407-438.