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
.