Indecomposability

Indecomposability

In order to minimize the number of orbits that must be enumerated or represented, and following Slepian again, we can restrict attention to indecomposable linear (n,k)-codes. Let C₁ be a linear (n₁,k₁)-code over GF(q) with generator matrix Γ₁ and let C₂ be a linear (n₂,k₂)-code over GF(q) with generator matrix Γ₂, then the code C with generator matrix

Γ: =

⎛
⎜
⎜
⎝

Γ₁

Γ₂

⎞
⎟
⎟
⎠

is called the direct sum of the codes C₁ and C₂, and it will be denoted by C=C₁ ⊕ C₂. A code C is called decomposable, if and only if it is equivalent to a code which is the direct sum of two or more linear codes. Otherwise it is called indecomposable.

In [13] Slepian proves that every decomposable linear (n,k)-code is equivalent to a direct sum of indecomposable codes, and that this decomposition is unique up to equivalence and order of the summands. Slepian used a generating function scheme for computing the numbers R_nk2 and R_nk2. However after constructing these codes the authors realized that in some situations this formula doesn't work correctly. For that reason we are giving another formula to determine the numbers R_nkq and R_nkq. For the rest of this section let n≥ 2.

Theorem The number R_nkq is equal to

S_nkq- ^._.
∑
a ^._.
∑
b ^._. n-1
∏
j=1 a_j ≠ 0 ( ^._.
∑
c=(c₁,...,c_{a_j})∈ ℕ^a_j j≥ c₁≥ ...≥ c_{a_j}≥ 1, ∑c_i=b_j U(j,a,c)),^._.

where

U(j,a,c)=^._. j
∏
i=1 Z( S_{ν(i,a_j,c)}) | _{x_ℓ=R_jiq}, ν(i,a_j,c)=|{1≤ l≤ a_j | c_l=i}|,^._.

and where the first sum is taken over the cycle types a=(a₁,...,a_n-1) of n, (which means that a_i∈ ℕ₀ and ∑ia_i=n) such that ∑a_i≤ k, while the second sum is over the (n-1)-tuples b =(b₁,...,b_n-1)∈ ℕ^n-1₀, for which a_i≤ b_i≤ i a_i, and ∑b_i=k. In the same way the R_nkq can be computed from the S_nkq. The numerical results show that for fixed q and n the sequence of R_nkq is unimodal and symmetric. (It is easy to prove that this sequence must be symmetric, but the proof of the unimodality is still open.)

Proof: In order to evaluate the values R_nkq the number of all classes of decomposable linear (n,k)-codes must be subtracted from S_nkq. In other words one has to find all possibilities of decomposing a linear (n,k)-code into a direct sum of indecomposable linear (n_i,k_i)-codes such that

^._. l
∑
i=1 n_i=n, ^._. l
∑
i=1 k_i=k, 1≤ k_i≤ n_i, 2≤ l≤ k. ^._.

According to Slepians theorem the (n_i,k_i)-codes can be arranged such that n₁≥ n₂≥ ...≥ n_l and in the case that n_i=n_i+1 the inequality k_i≥ k_i+1 holds. At first all partitions of n into at least two parts and into at most k parts must be found. Let n=n₁+n₂+...+n_l be such a partition with n_i≥ 1 and 2≤ l≤ k. Then the cycle type of λ is (a₁,a₂,...,a_n-1), where a_i=|{1≤ j≤ l | n_j=i}|. Two decomposable codes which determine two different partitions of n are not equivalent. In the second step to each partition of n one has to find all sequences (k₁,...,k_l) such that (*) is fulfilled, and such that codes belonging to different sequences are not equivalent. In order to do this we start with such a sequence (k₁,...,k_l) and define

b_i := ^._.
∑
j: n_j=i k_j,^._.

then

^._. n-1
∑
i=1 b_i=^._. l
∑
i=1 k_i=k and a_i≤ b_i≤ ia_i.^._.

Two decomposable codes which on the one hand belong to one partition of n but on the other hand define two different vectors b and b' are not in the same equivalence class. Now the other way round we start with a sequence (b₁,...,b_n-1) and try to determine all sequences (k₁,...,k_l) which define non equivalent codes such that b_i=∑_{j:
n_j=i}k_j. Again by Slepian's theorem we must find all partitions of b_j ≠ 0 (this implies a_j ≠ 0) into exacyly a_j parts of the form

b_j=^._. a_j
∑
i=1 c_i, j≥ c₁≥ ...≥ c_{a_j}≥ 1.^._.

In the last step U(j,a,c) must be evaluated. This is the the number of classes of linear (j⋅ a_j,b_j)-codes, which have a decomposition into a direct sum of indecomposable (j,c_i)-codes for 1≤ i≤ a_j to a given partition c of b_j into exactly a_j parts. We already know that there are R_{j,c_i,q} classes of indecomposable linear (j,c_i)-codes. In the case that all the c_i are distinct, this number is given by

^._. a_j
∏
i=1 R_{j,c_i,q}.^._.

Otherwise there exist i,l such that i<l and c_i=c_l. Then c_i=c_i+1=...=c_l and permuting the corresponding summands in the direct sum may lead to equivalent codes. For 1≤ i≤ j let ν(i)=ν(i,a_j,c) be the cardinality of {t | c_t=i}. Now there is a bijection between the classes of codes, which are a direct sum of ν(i) (j,i)-codes and the orbits of the symmetric group S_ν(i) on the set of all mappings from ν(i) into a set of R_jiq elements, where the action of S_ν(i) is given by:

S_ν(i) × R_jiq^ν(i)→R_jiq^ν(i), (π,f) ↦ f o π^-1.^._.

By Pólyas theorem [12] one has to compute the cycle index S_ν(i) and each variable must be substituted by R_jiq. Doing this for all possible values of i we get

U(j,a,c)=^._. j
∏
i=1 Z(S_ν(i))|_{x_ℓ=R_jiq}.^._.

Using the computer algebra system SYMMETRICA, among many other ones the tables of numbers of indecomposable codes which are shown below were computed.

harald.fripertinger "at" uni-graz.at, May 10, 2016

Indecomposability