ABSTRACT

The problem of classification of the subset of the vertices of the n-dimensional unit cube in respect to all “shifts” by a vector from is studied. Some applications for the investigation of the additive channels of communication are represented.

Keywords:Additive Channel, Code, Group, Stabilizer, Cardinality, Transitive Set

Let be a two element Galois field and be an n-dimensional space on that field. In other words, is the set of vertices of the n-dimensional unit cube, The subsets have many different interpretations in the terms of Boolean function theory, or of correcting code theory, or of partially ordered set theory, or that of additive channels etc. And each of these theories is connected with a certain class of restrictions imposed on the properties of the subsets, We consider the “shift” of the subsets, and we define equvalence as equality that is accurate within the shift. To define the subsets stabilizers and the transitive subfamilies we use the classic ways connected with Burnside’s Lemma.

Let be the family of all m-element subsets of the cube The transformation group operates on this set as follows. For any  and let the following is valid:

Thus is the shift of the set on the vector. The transitive set generated by has the standard form:

The family of all transitive sets generates the partition:

The cardinality of a transitive set is found in terms of the stabilizer of the set:

It is well known [1] [2] that is a subsets in and the cardinality of the transitive set is equal to the index of the subsets; that is:

(1)

where is the index of the group in regard to the subsets.

Example.

1) Let be a subgroup in, and be the family of cosets of the subgroup, and

If we form the set:

out of an arbitrary collection of the cosets, then

Let and be an arbitrary cosets to the subgroup; then Consequently, any element of the group, , belongs to the stabilizer of  the set, and thus: and

This example will be used in the sequel.

As (1) shows, to define the cardinality of the transitive set it is sufficient to know the cardinality of the stabilizer.

Let us note that the group acts on the given set, that is, is a stabilizer and we can use the same way of argumentation as we did above.

If, then the transitive set is defined in the standard way and:

(2)

where is the stabilizer of the element,. Taking into account that:

we have, for all. Then we have from (2):

that is, is equal to the index of the unit subgroup E, or:

Lemma 1. The following comparison holds:

This immediately follows from the formula of the partition:

If is the power index of the prime number, which is included in the canonic presentation, then the following statements hold true:

Corollary 1. The following inequality holds true:

Corollary 2. The stabilizer for any

Corollary 3. Let and Then either, or.

Lemma 2. The stabilizer for an arbitrary set if.

Proof. We assume, Then the elements of the set satisfy the following system:

Adding up all the equations of the system, we get the following equality: From this it follows that: which is a contradiction and it proves the Lemma.

In the general case, if the element belongs to the stabilizer of the subsets, the following holds true (according to the definition):

(3)

Let be a symmetrical group of the degree. We denote the elements of the group corresponding to transformation (3) by. Consequently, the element should by written as follows:

We consider the expansion into a product of independent cycles:

(4)

Lemma 3. If, then,.

Proof. If, we have from (4):

(5)

It follows from (5) that:

that is, Q. E. D.

To calculate the stabilizer one has to consider the multiset:

which has a key role for the further considerations.

Let, and:

where is the multiplicity of the inclusion of the element, , into.

Lemma 4. The stabilizer, of the set, is the sets of elements, where each occurs m times plus the zero element.

Proof. Let then the following holds true:

Two different pairs: and, have no common elements; otherwise they coinside.

Thus, the set of pairs form the partition, and the point y belongs to, according to Lemma 3.

From Lemma 4 a simple algorithm for building the stabilizer follows and, as a matter of fact, it is reduced to building of the multiset,. Complexity of such an algorithm is, where. The volume of the input information is the length of the recording of the set, that is,.

Lemma 5. If the cardinality of the subsets and that of the stabilizer satisfy the following conditions:

then:

Proof. Let For any we build the set. We choose any element from and define the set. We assume that there exists. Then the vector can be represented in two ways, namely:

and

where. Consequently, we get:, which contradicts the choice of the element. Hence, the following holds true:

(6)

Taking into account that we have:

(7)

We denote. Taking into account that, we have:. It follows from (6) and (7) that is represented either in the form:

, or

where. If, then. It can be proved in the same way that, for the case, , Consequently, We got a contradiction and it concludes the proof of Lemma 5 if we take into account Lemma 1.

Lemma 5 is a useful tool for calculation of the stabilizer for. Its content can be interpreted as follows. If it is possible to define elements belonging to, then, taking into account that the cardinality of a stabilizer is an exponent with the base 2, we directly get:.

Examples.

2) If, then. Consequently,. Taking Lemma 4 into account, we get:

3) If then Consequently:

All the partitions into pairs of the set are generated by one of them, for instance:

It follows from this that if:

then the following equalities hold true:

Consequently, the following statement holds true:

Statement 1. If then, But if then

Examples.

4) Let Then:

and.

5) Let Then:

And as then:

Now let us calculate the number of the sets that are transitive in regard to the group The tool for such calculation is Burnside’s Lemma: [1] [2] .

Lemma (Burnside’s) 6. The number of the equivalence classes or transitive sets is as follows:

where is the set of the (stationary) points of the transformation, that is:

Lemma 7. The number of the solutions of the following equation:

(8)

is, if.

Proof. According to Lemma 3, Equation (8) is equivalent to the system of the following equations:

(9)

where the partition is chosen for the sake of certainty. Let us note that the following equation:

(10)

has exactly solutions for and it does not depend on if. Indeed, choosing an we get:. Further, if and are two solutions of Equation (10), then either these solutions do not overlap, or they coinside. Indeed, we get, from and; consequently, it follows from that In the same way, if, then Thus, all the solutions of system (9) can be obtained by choosing pairs from pairs, which are solutions of (10).

Theorem 1. The following equalities are valid:

(11)

(12)

Proof. We get from Burnside’s Lemma:

Then, for the case, taking into account Lemma 7, we get:

For. This directly proves Formula (11).

For the case, taking into account Corollary 2, we get: for all, which proves formula (12).

Thus, the above statements make, more or less, possible to know the structure of the stabilizer of the set

and to find the number of the transitive sets which are generated by the action of the group on.

Let us also note that, according to Corollary 1, , if, where. On the other hand, as Example 1 shows, for any subgroup and for any collection of contiguous classes of the group in regard to then the set is in the family and

For an odd  the cardinality of the set is equal to, and its stabilizer has elements. This shows that it is possible to draw the above mentioned boundary for the stabilizers of the considered sets. The following example of a contiguous class with the stabilizer illustrates the above mentioned considerations, because. Thus, the estimate for the case is not so bad evaluation for the cardinality of the stabilizer of the set. The “average” value of this boundary in the whole interval of the cardinalities, is and this can serve as a “realistic” boundary for the cardinality of the stabilizer for a uniform distribution on the family of the sets.

The family of all transitive sets, where, generates the partition:

(13)

As, then, according to Theorem 1, we have for the numbers of the transitive sets the following equality:

Corollary 4.

Shifts and Additive Channels. One of the applications of the above considerations are the so called additive channels.

We call any subsets additive channel [3] [4] , if it carries out the following dictionary function:

(14)

Thus, any word, if transmitted through the additive channel, is transformed into one of the words of (14), in the result of the shift by the vector.

Definition 1 [5] . We define the th order neighbourhood of the vector, , in regard to, as follows:

.

Definition 2. The code, , corrects the errors of the additive channel if the following condition holds true:

.

The equivalent definition has the following form: The code corrects the errors of the additive channel if the following condition holds true:

(15)

As the order cardinality does not depend on the vector we denote:

.

Let us note that for the cardinality of the code correcting the errors of the additive channel the following boundaries hold true [3] [4] :

(16)

Actually, condition (15) makes possible to decode the initial message at the channel output through a standard “decoding table” of any word.

If one takes the sphere of radius t with the centre at zero as, then he gets the classic channel through which there take place no more than t distortions of the form:.

The main problem when investigating a given additive channel is the building the code of the maximum cardinality, correcting the errors of the channel. Consequently, each additive channel generates its own coding theory, and the possibilities of examining and sorting out all these communication tools are rather limited. At the same time, some most simple considerations show that many of these additive channels are equivalent (identical) in the sense of their content. Indeed, the channels, and, are equivalent for any, in the sense that any code,correcting the errors of the additive channel corrects the errors of the additive channel as well, and vice versa. The above classification of the additive channels is based on these considerations. In particular, one can always consider that belongs to the channel otherwise one could pass to the equivalent channel including the zero vector, without any loss of generality.

Another definition of equivalence of additive channals is directly connected with the error correcting code.

Let be a predicate given on the Cartesian product or:

Definition 3 [5] . The two additive channels and are equivalent if the following condition holds true  for all:

(17)

Actually, condition (17) means that if the code corrects the errors of the channel, then the code corrects the errors of the channel as well, and vice versa. In particular, if:

(that is, is a shift transformation) then:

for any pair of points,where the tilde sign means the notion of equivalence introduced above.

We denote the equivalence class including the channel by.

Example.

One easily can see that these channels are equivalent though

Actually, in the general case, the channel cardinality is not any obstacle for classification and, in some certain cases, it defines the channel equivalence one to one.

Statement 2. For any channel with the cardinality the followingtakes place:

.

Proof. It follows from (16) that any code for which either, or, is consisted of one vector. On the other hand, for any code consisted of one vectorthe following equality is valid:

that is:

.

Q. E. D.

Note that the following example excludes the possibility of the contrary statement.

Example.

7) Let:. Then:, if.

Now let us go back to Example 6. We have:

It is obvious that this example is not an exception; therefore, we can use the following equality:

where is the transitive set of the channel in regard to the group of transformation. We get:

Taking into account (13), we state the following:

Theorem 2. For any channel there exist the channels from, such that the partition

is unique.

This theorem shows the connection between the classes of equivalence for communication channels and the transitive sets of subsets, which are generated through the the action of the group on them.

Though the expansion of is unique, the transitive sets included in the expansion are generated by different collections of “basic” channels,.

We reduced the investigation of communication channels to the investigation of transitive sets, and thus the investigation of the latter is reduced to that of the classes of equivalence, which can further be described introducing the relations of partial order:

Consequently, we came to the necessity of introducing of an invariant of an equivalence class, characterizing the given order.

An invariant of any is the set, including the zero vector, and this is its difference from the set which was defined above.

Theorem 3. For any channels and the following holds:

Proof. Let:, and the code corrects the errors of the channel. Then, taking into account (15), we have:

Consequently, , which means that the code corrects the errors of the channel.

If, then—without any loss of generality—we can assume that there exist and. We consider the code. Let us show that corrects the errors of the channel, but does not correct the errors of the channel. To prove this it is sufficient to show that both channels and include the zero point, and it can be done applying the shift transformation. Obviously, this transformation does not change the sets and. The code corrects the errors of the channel, because:

But, that is,. Hence:

that is, the code does not correct the errors of A. Q. E. D.

Unfortunately, the answer to the question: “is every set from invariant under action of any equivalence class” is negative. For instance, all sets having cardinality 3 or 5 have no invariants from Bn .

Statement 3. An equivalence class does not include more than one group.

Proof. Let the channels, be groups from. It follows from the following obvious equalities:

that. Q. E. D.

Statement 4. If the group, , is the equivalence class invariant of some channel, then and it has the maximum cardinality in that equivalence class.

In other words, a group channel is a “preferable generator” in its equivalence class.

Concluding, we note that the preceding definitions are symmetrical in regard to the pair and, consequently, both the generation and correction of errors have the same essence. It means that all statements in regard to the communication channels hold true in regard to the codes of the pair.

References