# Classification of poset-block spaces admitting MacWilliams-type identity

Jerry Anderson Pinheiro and Marcelo Firer J. A. Pinheiro is with
IMECC–UNICAMP, State University of Campinas, CEP 13083-859, Campinas, SP,
Brazil (e-mail: jerryapinheiro@gmail.com).M. Firer is with IMECC–UNICAMP,
State University of Campinas, CEP 13083-859, Campinas, SP, Brazil (e-mail:
mfirer@ime.unicamp.br).

###### Abstract

In this work we prove that a poset-block space admits a MacWilliams-type
identity if and only if the poset is hierarchical and at any level of the
poset, all the blocks have the same dimension. When the poset-block admits the
MacWilliams-type identity we explicit the relation between the weight
enumerators of a code and its dual.

###### Index Terms:

Poset-block codes, MacWilliams identity, weight distribution, MacWilliams-type
identity.

##  I Introduction

Due to both the interest in generalizing classic problems in coding theory and
to applications in cryptography, experimental designs and high-dimensional
numerical integration (see for example [1] and [2]), by the mid 1990s
researches began to study codes considering metrics others than the usual
Hamming metric over $\mathbb{F}_{q}^{n}$. Among those families of metrics are
the poset metrics [3] and the block metrics [2]. Much of the classical theory
has been generalized to codes in spaces endowed with a poset metric, as can be
seen, for example, in [4], [5], [6] and [7].

In 2008 Firer et al [8] presented the family of metrics called poset-block
that generalizes all the previous ones. In this work we generalize to poset-
block spaces the characterization given in [5] for poset-metric spaces of
poset-block metrics admitting MacWilliams-type identity.

Let $[m]:=\\{1,2,\cdots,m\\}$ be a finite set. If $\preccurlyeq$ is a partial
order relation in $[m]$, we say $P:=([m],\preccurlyeq)$ is a poset and denote
by $\preccurlyeq_{P}$ the order in $P$. An ideal in a poset is a nonempty
subset $I\subset[m]$ such that, for $i\in I$ and $j\in[m]$, if
$j\preccurlyeq_{P}i$ then $j\in I$. Given $A\subset[m]$, we denote by $\langle
A\rangle_{P}$ the smaller ideal of $P$ containing $A$. If $A=\\{i\\}$, we will
denote by $\langle i\rangle_{P}$ the ideal $\langle\\{i\\}\rangle_{P}$. A
chain in a poset $P$ is a subset of $[m]$ such that every two elements are
comparable.

Let $\mathbb{F}_{q}$ be a finite field and $\mathbb{F}_{q}^{n}$ the vector
space of $n$-tuples over $\mathbb{F}_{q}$. Given $m\in[n]$, $P$ a poset over
$[m]$ and $\pi:[m]\rightarrow\mathbb{N}$ a map such that
$n=\sum_{i=1}^{m}\pi(i)$, we say that $\pi$ is a labeling of the poset $P$ and
that the pair $(P,\pi)$ is a poset-block structure over $[m]$.

We denote $k_{i}=\pi(i)$, and consider the vector space over $\mathbb{F}_{q}$

$V:=\mathbb{F}_{q}^{k_{1}}\times\mathbb{F}_{q}^{k_{2}}\times\cdots\times\mathbb{F}_{q}^{k_{m}},$

isomorphic to $\mathbb{F}_{q}^{n}$. Given $u\in\mathbb{F}_{q}^{n}$, there is a
unique decomposition $u=(u_{1},\cdots,u_{m})$ with
$u_{i}\in\mathbb{F}_{q}^{k_{i}}$, $i\in[m]$. The $\pi$-support and the
$(P,\pi)$-weight of $u$ are defined respectively as

$supp_{\pi}(u):=\\{i\in[m]:u_{i}\neq 0\in\mathbb{F}_{q}^{k_{i}}\\}$

and

$w_{(P,\pi)}(u):=|\langle supp_{\pi}(u)\rangle_{P}|,$

where $|.|$ denotes the cardinality of the given set. For
$u,v\in\mathbb{F}_{q}^{n}$,

$d_{(P,\pi)}(u,v):=w_{(P,\pi)}(u-v)$

defines a metric over $\mathbb{F}_{q}^{n}$ called poset-block metric, or just
$(P,\pi)$-distance between $u$ and $v$.

We note that when $\pi(i)=1$ for every $i\in[m]$ the $(P,\pi)$-distance is
usual poset distance introduced in [3], while imposing $P$ to be a trivial
poset ($i\preccurlyeq j\iff i=j$) turns the $(P,\pi)$-distance into the block
distance defined in [2]. Interweaving the poset and the block structures opens
a wide range of possibilities for searching for codes with interesting metric
characteristics, such as perfect codes, since poset and block metrics have
opposite effects on distances: while enlarging the relations on a poset
enlarges the distances (hence “shrinks” metric balls), enlarging the blocks
diminishes distances (hence “blows” metric balls).

Concerned with MacWilliams-type identities, dual posets play a crucial role:

###### Definition 1

Given a poset $P$ over $[m]$, the dual poset is the poset $\overline{P}$
defined by the relations

$i\preccurlyeq_{P}j\iff j\preccurlyeq_{\overline{P}}i$

for every $i,j\in[m]$. The pair $(\overline{P},\pi)$ is called the dual poset-
block.

Given $j\in[m]$, the rank of $j$, denoted by $h_{P}(j)$, is

$h_{P}(j):=max\\{|C|:C\subset\langle j\rangle_{P}\ \mbox{and}\ C\ \mbox{is a
chain}\\}.$

The height $h(P)$ of $P$ is the maximal rank of the elements of $[m]$. The
$i$-level of $P$ is $\Gamma_{P}^{i}:=\\{j\in[m]:h_{P}(j)=i\\}$. We define
$b_{i}=\sum_{j\in\Gamma_{P}^{i}}k_{j}$ as the sum of the dimensions of the
blocks associated by $\pi$ to the $i$-level of $P$, and we call it the
dimension of $\Gamma_{P}^{i}$.

A poset-block $(P,\pi)$ is said to be hierarchical if given
$j_{1}\in\Gamma_{P}^{i}$ we have that $j_{1}\preccurlyeq_{P}j$ for all
$j\in\Gamma_{P}^{i+1}$. Defining a hierarchical poset on $[m]$ is equivalent
to choosing an ordered partition of $[m]$ (the partition defined by the
different levels), thus it is a quite large set of posets (or poset metrics)
including, as a particular case, the block structures presented in [2] when
the poset structure is trivial ($h(P)=1$), the Niederreiter-Rosenbloom-
Tsfasman metric (see [9]) with a unique chain when $h(P)=m$ and the block
structure is trivial ($k_{i}=1$ for every $i\in[m]$) and the usual Hamming
structure when both the poset and the block structures are trivial.

Given a poset-block $(P,\pi)$ over $[m]$ such that $|\Gamma_{P}^{i}|=m_{i}$,
let $\sigma$ be a permutation of $[m]$ such that
$\\{\sigma^{-1}(r_{i}+1),\cdots,\sigma^{-1}(r_{i}+m_{i})\\}=\Gamma_{P}^{i}$
where $r_{i}=m_{1}+\cdots+m_{i-1}$ and $m_{0}=0$. We let $P_{1}$ be the poset
induced by $\sigma$, ie, the poset in which
$\sigma(j_{1})\preccurlyeq_{P_{1}}\sigma(j_{2})$ if
$j_{1}\preccurlyeq_{P}j_{2}$. Obviously, $P_{1}$ and $P$ are isomorphic
posets. If we put $\pi_{1}(i)=\pi(\sigma^{-1}(i))=k_{i}^{\prime}$, then the
map

$g:(\mathbb{F}_{q}^{k_{1}}\times\cdots\times\mathbb{F}_{q}^{k_{m}},d_{(P,\pi)})\rightarrow(\mathbb{F}_{q}^{k_{1}^{\prime}}\times\cdots\times\mathbb{F}_{q}^{k_{m}^{\prime}},d_{(P_{1},\pi_{1})})$
$\ \ \ \ \ \ \ \
(v_{1},\cdots,v_{m})\mapsto(v_{\sigma(1)},\cdots,v_{\sigma(m)})$

is, by construction, a linear isometry. Hence, up to a linear isometry, we can
and will assume that $\Gamma_{P}^{i}=\\{r_{i}+1,\cdots,r_{i}+m_{i}\\}$, and in
this case we say $(P,\pi)$ has a natural labeling. Hence, given
$u\in\mathbb{F}_{q}^{n}$ we may decompose it as

$u=\sum_{i=1}^{h(P)}\sum_{j=1}^{m_{i}}\sum_{l=1}^{k_{(r_{i}+j)}}u_{r_{i}+j}^{l}e_{s(i,j,l)}$

where $u_{r_{i}+j}^{l}\in\mathbb{F}_{q}$ are scalars and

$\left\\{e_{s(i,j,l)}:1\leqslant l\leqslant k_{(r_{i}+j)},1\leqslant
j\leqslant m_{i},1\leqslant i\leqslant h(P)\right\\}$

is the usual basis of $\mathbb{F}_{q}^{n}$, with
$s(i,j,l)=l+\sum_{t=0}^{r_{i}+j-1}k_{t}$ and $k_{0}=0$.

A $[n,k,\delta]_{q}$ linear $(P,\pi)$-code is a $k$-dimensional subspace
$\mathcal{C}\subset\mathbb{F}_{q}^{n}$ where $\mathbb{F}_{q}^{n}$ is equipped
with the poset-block metric $d_{(P,\pi)}$ and

$\delta=min\\{w_{(P,\pi)}(v):0\neq v\in\mathcal{C}\\}$

is the $(P,\pi)$-minimum distance of $\mathcal{C}$.

###### Definition 2

Let $\mathcal{C}$ be a linear $(P,\pi)$-code. Its dual code is defined as

$\mathcal{C}^{\perp}=\\{x\in\mathbb{F}_{q}^{n}:x\cdot u=0\ \forall\
u\in\mathcal{C}\\}$

where $x\cdot u$ is the usual formal inner product. We remark that
$\mathcal{C}^{\perp}$ is an $(n-k)$-dimensional linear code. Along this work,
$\mathcal{C}^{\perp}$ is considered to be a linear $(\overline{P},\pi)$-code
with parameters $[n,n-k]_{q}$ and we denote by $\delta^{\perp}$ its minimal
distance (according to the $(\overline{P},\pi)$-metric).

Given a linear $(P,\pi)$-code $\mathcal{C}$, the $(P,\pi)$-weight enumerator
of $\mathcal{C}$ is the polynomial

$W_{\mathcal{C},(P,\pi)}(x)=\sum_{u\in\mathcal{C}}x^{w_{(P,\pi)}(u)}=\sum_{i=0}^{m}A_{i,(P,\pi)}(\mathcal{C})x^{i},$

where $A_{i,(P,\pi)}(\mathcal{C})=|\\{u\in\mathcal{C}:w_{(P,\pi)}(u)=i\\}|$.
When no confusion may arise, we will use a simplified notation for those
coefficients: $A_{i}=A_{i,(P,\pi)}(\mathcal{C})$ and
$\overline{A}_{i}=A_{i,(\overline{P},\pi)}(\mathcal{C}^{\perp})$.

Note that

$V:=\mathbb{F}_{q}^{b_{1}}\times\cdots\times\mathbb{F}_{q}^{b_{t}}$

is a vector space over $\mathbb{F}_{q}$ isomorphic to $\mathbb{F}_{q}^{n}$, so
that given $u\in\mathbb{F}_{q}^{n}$ we can write $u=(u^{1},\cdots,u^{t})$
where $u^{i}\in\mathbb{F}_{q}^{b_{i}}$ and
$u^{i}=(u_{r_{i}+1},\cdots,u_{r_{i}+m_{i}})$ is such that
$u_{r_{i}+j}\in\mathbb{F}_{q}^{k_{(r_{i}+j)}}$.

If $P$ is a poset with $t$ levels, the leveled $(P,\pi)$-weight enumerator of
$\mathcal{C}$ is the formal expression

$W_{\mathcal{C},(P,\pi)}(x;y_{0},\cdots,y_{t}):=\sum_{u\in\mathcal{C}}x^{w_{(P,\pi)}(u)}y_{s_{P}(u)},$

where $s_{P}(u)=max\\{i:u^{i}\in\mathbb{F}_{q}^{b_{i}}\backslash\\{0\\}\\}$
and $s_{P}(0)=0$. This definition is similar to the one used in [5] in the
classification of poset metrics that admits MacWilliams-type identity, ie, the
case where the block structure is trivial. It is clear that
$W_{\mathcal{C},(P,\pi)}(x)=W_{\mathcal{C},(P,\pi)}(x;1,\cdots,1)$.

###### Definition 3

We say that a poset-block $(P,\pi)$ admits a MacWilliams-type identity (MW-I)
if the $(\overline{P},\pi)$-weight enumerator of $\mathcal{C}^{\perp}$ is
uniquely determined by the $(P,\pi)$-weight enumerator of $\mathcal{C}$ for
every linear $(P,\pi)$-code $\mathcal{C}$.

MacWilliams-type identities in the context of poset codes have interested
researchers (see [4], [10] and [11]) since they establish a relation between
important invariants of a high information rate code with those of a low
dimension code, that are much easier to compute. In 2005, Kim and Oh [5]
proved that a poset space admits a MW-I if and only if the poset is
hierarchical. In this work we extend this result to the instances that
remained open: the instance of poset-block (and block metrics as a particular
case).

##  II MacWilliams-type identity in $(P,\pi)$ spaces

The example below shows that the condition established in [5] is not
sufficient to ensure MacWilliams-type identity in $(P,\pi)$ spaces.

###### Example 1

Let $P=\\{1,2,3\\}$ be the hierarchical poset with partial order defined by
the relations $1\preccurlyeq_{P}2$ and $1\preccurlyeq_{P}3$ so that the dual
poset $\overline{P}$ is defined by the relations
$2\preccurlyeq_{\overline{P}}1$ and $3\preccurlyeq_{\overline{P}}1$. Define
$\pi:[3]\rightarrow\mathbb{N}$ by $\pi(1)=1$, $\pi(2)=1$ and $\pi(3)=2$. Then,
direct computations shows that the linear codes

$\mathcal{C}_{1}=\\{(0,0,0,0),(0,0,1,0)\\}$

and

$\mathcal{C}_{2}=\\{(0,0,0,0),(0,1,0,0)\\}$

over $\mathbb{F}_{2}^{4}$ has the same $(P,\pi)$-weight enumerator:

$W_{\mathcal{C}_{1},(P,\pi)}(x)=1+x^{2}=W_{\mathcal{C}_{2},(P,\pi)}(x).$

However,

$W_{\mathcal{C}_{1}^{\perp},(\overline{P},\pi)}(x)=1+2x+x^{2}+4x^{3}$

and

$W_{\mathcal{C}_{2}^{\perp},(\overline{P},\pi)}(x)=1+3x+4x^{3},$

so that MW-I does not hold.

###  II-A Necessary condition for MacWilliams-type identity

Let $(P,\pi)$ be a poset-block in $[m]$ with $t$ levels such that
$|\Gamma_{P}^{i}|=m_{i}$ for $i\in[t]$. The three lemmas below are the
equivalent, for the poset-block case, of Lemmas (2.1)–(2.4) in [5]. Despite
the fact their proofs for poset-block being more delicate than in the case of
posets (where the blocks are trivial), they are quite similar.

###### Lemma 1

Given $u\in\mathbb{F}_{q}^{n}$ then
$w_{(\overline{P},\pi)}(u)=m\Leftrightarrow
supp_{\pi}(u)\supset\Gamma_{P}^{1}$. Furthermore, if $u$ satisfies
$supp_{\pi}(u)\subset\Gamma_{P}^{1}$, we have that

$q^{n-b_{1}}\ \mbox{\large\textbar}\ |\\{v\in\mathbb{F}_{q}^{n}:u\cdot
v=0\mbox{ and }w_{(\overline{P},\pi)}(v)=m\\}|.$

where $a\mbox{\large\textbar}b$ means $a$ divides $b$ and $b_{1}$ is the
dimension of $\Gamma_{P}^{1}$.

###### Proof:

The first affirmation is evident. Let $u\in\mathbb{F}_{q}^{n}$ such that
$supp_{\pi}(u)\subset\Gamma_{P}^{1}$. Without loss of generality we can assume
that $\Gamma_{P}^{1}=[m_{1}]$ and $u=(u_{1},\cdots,u_{i},0,\cdots,0)$ where
$i\leqslant m_{1}$ and $u_{j}\in\mathbb{F}_{q}^{k_{j}}\backslash\\{0\\}$ for
all $j\in[i]$. Set

$\displaystyle
A:=\\{(v_{1},\cdots,v_{i}):v_{j}\in\mathbb{F}_{q}^{k_{j}}\backslash\\{0$
$\displaystyle\\}\ \forall\ j\in[i]\mbox{ and }$ $\displaystyle u_{1}\cdot
v_{1}+\cdots+u_{i}\cdot v_{i}=0\\}.$

In each $\mathbb{F}_{q}^{k_{j}}$ space we have $q^{k_{j}}-1$ non null vectors,
then we have $\prod_{j=i+1}^{m_{1}}(q^{k_{j}}-1)$ possibilities of vectors in
the blocks associated to elements of the subset $\\{i+1,\cdots,m_{1}\\}$ of
$[m]$, since we do not impose restrictions in the $m-m_{1}$ remaining blocks,
by first claim it follows that

$\displaystyle|\\{v\in\mathbb{F}_{q}^{n}:u\cdot v=0\mbox{ and
}w_{(\overline{P},\pi)}(v)$ $\displaystyle=m\\}|=$ $\displaystyle
q^{n-b_{1}}|A|\prod_{j=i+1}^{m_{1}}(q^{k_{j}}-1).$

∎

###### Lemma 2

If a poset-block $(P,\pi)$ admits a MW-I, then $j\preceq_{P}i$ for every
$i\in\Gamma_{P}^{2}$ and $j\in\Gamma_{P}^{1}$.

###### Proof:

Assuming $\Gamma_{P}^{2}\neq\emptyset$, it follows that $m>m_{1}$. Suppose
there is $i\in\Gamma_{P}^{2}$ that is not comparable to some
$j\in\Gamma_{P}^{1}$, that is, such that $|\langle
i\rangle_{P}|<1+|\Gamma_{P}^{1}|$. In this instance there are
$u,v\in\mathbb{F}_{q}^{n}$ such that $supp_{\pi}(u)=\\{i\\}$,
$supp_{\pi}(v)\subset\Gamma_{P}^{1}$ and $|\langle
supp_{\pi}(u)\rangle_{P}|=|\langle supp_{\pi}(v)\rangle_{P}|$. Without loss of
generality we can admit that $u=e_{s(2,1,1)}$. If $\mathcal{C}_{u}$ and
$\mathcal{C}_{v}$ are two one-dimensional linear $(P,\pi)$-codes generated by
$u$ and $v$ respectively, then $\mathcal{C}_{u}$ and $\mathcal{C}_{v}$ have
same $(P,\pi)$-weight enumerator. Assuming the MW-I in $(P,\pi)$,
$\mathcal{C}_{u}^{\perp}$ and $\mathcal{C}_{v}^{\perp}$ must have the same
$(\overline{P},\pi)$-weight enumerator. If $x\in\mathcal{C}_{u}^{\perp}$ then
$x_{r_{2}+1}^{1}=0$. Furthermore, by Lemma 1 $w_{(\overline{P},\pi)}(x)=m$ if
and only if $\Gamma_{P}^{1}\subset supp_{\pi}(x)$, so that

$\displaystyle|\\{x\in\mathcal{C}_{u}^{\perp}:$ $\displaystyle
w_{(\overline{P},\pi)}(x)=m\\}|=$ $\displaystyle\ \ \ \
|\\{x\in\mathbb{F}_{q}^{n}:x_{r_{2}+1}^{1}=0\mbox{ and }\Gamma_{P}^{1}\subset
supp_{\pi}(x)\\}|.$

Set

$A:=\\{x_{i}\in\mathbb{F}_{q}^{k_{i}}:x_{r_{2}+1}^{1}=0\\}$

and

$B:=\\{(x_{1},\cdots,x_{m}):x_{j}\neq 0\ \forall\ j\in[m_{1}]\mbox{ and
}x_{i}=0\\}.$

Since $i\notin\Gamma_{P}^{1}$, $|A|=q^{k_{i}-1}$ and
$|B|=q^{n-k_{i}-b_{1}}\prod_{j=1}^{m_{1}}(q^{k_{j}}-1)$, it follows that

$\displaystyle|\\{x\in\mathcal{C}_{u}^{\perp}:w_{(\overline{P},\pi)}(x)=m\\}|=$
$\displaystyle|B||A|=$ $\displaystyle
q^{n-b_{1}-1}\prod_{j=1}^{m_{1}}(q^{k_{j}}-1).$ (1)

On the other hand

$\displaystyle\\{x\in\mathcal{C}_{v}^{\perp}:$ $\displaystyle
w_{(\overline{P},\pi)}(x)=m\\}=$ $\displaystyle\ \
\\{x\in\mathbb{F}_{q}^{n}:x\cdot v=0\mbox{ and
}w_{(\overline{P},\pi)}(x)=m\\},$ (2)

hence, by Lemma 1 and by Equations (1) and (2) it follows that

$q\ \mbox{\large\textbar}\prod_{j=1}^{m_{1}}(q^{k_{j}}-1),$

a contradiction because $q$ is power of a prime. Therefore $|\langle
i\rangle_{P}|=1+|\Gamma_{P}^{1}|$, ie, $j\preceq_{P}i$ for all
$j\in\Gamma_{P}^{1}$. ∎

Let $P^{j}=P\backslash\cup_{i=1}^{j}\Gamma_{P}^{i}$. Consider on $P^{j}$ the
order induced by $P$ and let
$\pi^{j}=\pi|_{[m]\backslash\cup_{i=1}^{j}\Gamma_{P}^{i}}$ be the restriction
of $\pi$ to $[m]\backslash\cup_{i=1}^{j}\Gamma_{P}^{i}$.

###### Lemma 3

If a poset-block $(P,\pi)$ admits the MW-I, then the poset-block
$(P^{1},\pi^{1})$ also admits.

###### Proof:

If $m=m_{1}$ we have that $[m]\backslash\Gamma_{P}^{1}=\emptyset$ and there is
nothing to be proved. Let us assume that $m>m_{1}$ and let
$\mathcal{C}_{1}^{\prime}$ and $\mathcal{C}_{2}^{\prime}$ be linear
$(P^{1},\pi^{1})$-codes with length $n-b_{1}$ and same
$(P^{1},\pi^{1})$-weight enumerator. For $i=1,2$, let

$\mathcal{C}_{i}:=\mathbb{F}_{q}^{b_{1}}\oplus\mathcal{C}_{i}^{\prime}=\\{(u,v):u\in\mathbb{F}_{q}^{b_{1}}\mbox{
and }v\in\mathcal{C}_{i}^{\prime}\\}$

be linear $(P,\pi)$-codes with length $n$ and same $(P,\pi)$-weight
enumerator. Since $(P,\pi)$ admits MW-I, $\mathcal{C}_{1}^{\perp}$ and
$\mathcal{C}_{2}^{\perp}$ have the same $(\overline{P},\pi)$-weight
enumerator. Furthermore, the dual codes $\mathcal{C}_{1}^{\perp}$ and
$\mathcal{C}_{2}^{\perp}$ can be described as

$\displaystyle\mathcal{C}_{i}^{\perp}=\\{(u,v)\in\mathbb{F}_{q}^{b_{1}}\times\mathbb{F}_{q}^{n-b_{1}}:(u,v)$
$\displaystyle\cdot(a,b)=0$ $\displaystyle\forall\
a\in\mathbb{F}_{q}^{b_{1}}\mbox{ and }b\in\mathcal{C}_{i}^{\prime}\\}.$

Being $b\in\mathcal{C}_{i}^{\prime}$ the null code-word of
$\mathcal{C}_{i}^{\prime}$, by definition of $\mathcal{C}_{i}^{\perp}$ it
follows that $u$ is the null element of $\mathbb{F}_{q}^{b_{1}}$, hence

$\mathcal{C}_{i}^{\perp}=\\{(u,v):u=0\in\mathbb{F}_{q}^{b_{1}}\mbox{ and
}v\in\mathcal{C}_{i}^{\prime\perp}\\}.$

Therefore, by puncturing the codes $\mathcal{C}_{1}^{\perp}$ and
$\mathcal{C}_{2}^{\perp}$ in the first $b_{1}$ coordinates, it follows that
$\mathcal{C}_{1}^{\prime\perp}$ and $\mathcal{C}_{2}^{\prime\perp}$ have the
same $(P^{1},\pi^{1})$-weight enumerator. ∎

By induction, using Lemmas 2 and 3 we have the following necessary condition
for a poset-block $(P,\pi)$ to admit a MW-I.

###### Proposition 1

If $(P,\pi)$ admits the MW-I, then $P$ is a hierarchical poset.

By Example 1 we can conclude that the previous condition is not sufficient to
assure an MW-I and the following is also necessary:

###### Proposition 2

Suppose that $(P,\pi)$ admits a MW-I. Then, $\pi(j_{1})=\pi(j_{2})$ for all
$j_{1},j_{2}\in\Gamma_{P}^{i}$ and every $1\leqslant i\leqslant h(P)$, ie,
blocks at the same level have the same dimension.

###### Proof:

Given $i\in[h(P)]$ consider $j_{1},j_{2}\in\Gamma_{P}^{i}$ and assume
$\pi(j_{1})\leqslant\pi(j_{2})$. Let $\mathcal{C}_{u}$ and $\mathcal{C}_{v}$
be the one-dimensional linear $(P,\pi)$-codes with length $n$ generated by
$u=e_{s(i,j_{1}-r_{i},1)}$ and $v=e_{s(i,j_{2}-r_{i},1)}$ respectively, where
$r_{i}=m_{1}+\cdots+m_{i-1}$. By Proposition 1 the poset $P$ is hierarchical,
and since there are

$(q^{k_{j_{1}}-1}-1)+\displaystyle\sum_{\genfrac{}{}{0.0pt}{}{j\in\Gamma_{P}^{i}}{j\neq
j_{1}}}(q^{k_{j}}-1)$

elements in $\mathcal{C}_{u}^{\perp}$ with support contained in a unique block
at the $i$-level of $P$, then

$\displaystyle
A_{m_{i+1}+\cdots+m_{t}+1,(\overline{P},\pi)}(\mathcal{C}_{u}^{\perp})=$
$\displaystyle(q^{k_{j_{1}}-1}-1)\prod_{\genfrac{}{}{0.0pt}{}{j\in\Gamma_{P}^{l}}{i<l\leqslant
t}}q^{k_{j}}$
$\displaystyle+\displaystyle\sum_{\genfrac{}{}{0.0pt}{}{j\in\Gamma_{P}^{i}}{j\neq
j_{1}}}(q^{k_{j}}-1)\prod_{\genfrac{}{}{0.0pt}{}{j\in\Gamma_{P}^{l}}{i<l\leqslant
t}}q^{k_{j}}$

since, when considering the dual poset $\overline{P}$, there are no
restrictions on the coordinates in the blocks belonging to levels higher (in
$P$) than $i$. In a similar way we find that

$\displaystyle
A_{m_{i+1}+\cdots+m_{t}+1,(\overline{P},\pi)}(\mathcal{C}_{v}^{\perp})=$
$\displaystyle(q^{k_{j_{2}}-1}-1)\prod_{\genfrac{}{}{0.0pt}{}{j\in\Gamma_{P}^{l}}{i<l\leqslant
t}}q^{k_{j}}$
$\displaystyle+\displaystyle\sum_{\genfrac{}{}{0.0pt}{}{j\in\Gamma_{P}^{i}}{j\neq
j_{2}}}(q^{k_{j}}-1)\prod_{\genfrac{}{}{0.0pt}{}{j\in\Gamma_{P}^{l}}{i<l\leqslant
t}}q^{k_{j}}.$

Assuming that $(P,\pi)$ admits a MW-I it follows that

$A_{m_{i+1}+\cdots+m_{t}+1,(\overline{P},\pi)}(\mathcal{C}_{u}^{\perp})=A_{m_{i+1}+\cdots+m_{t}+1,(\overline{P},\pi)}(\mathcal{C}_{v}^{\perp}),$

ie, $\pi(j_{1})=\pi(j_{2})$. ∎

From the two previous propositions it follows that:

###### Theorem 1

If $(P,\pi)$ admits a MacWilliams-type identity then $P$ is a hierarchical
poset and blocks at the same level have the same dimension.

Figure 1: Diagram of a typical hierarchical poset-block with blocks of equal
dimension at each level.

###  II-B Sufficient condition for MacWilliams-type identity

In this section we will prove that the conditions found to be necessary will
also be sufficient. Let $(P,\pi)$ be a hierarchical poset-block over $[m]$
with $t$ levels such that $|\Gamma_{P}^{i}|=m_{i}$, with $i\in[t]$. As before,
we let $m_{0}=0$ and $r_{i}=m_{1}+\cdots+m_{i-1}$. We can assume without loss
of generality that $\Gamma_{P}^{i}=\\{r_{i}+1,\cdots,r_{i}+m_{i}\\}$. Let
$d_{i}=\pi(r_{i}+j)$ for every $j\in[m_{i}]$, ie, blocks at the same level
have the same dimension. Under this condition the dimension of the $i$-level
is given by

$b_{i}=\sum_{j=1}^{m_{i}}\pi(r_{i}+j)=m_{i}d_{i}.$

We note that $n=b_{1}+\cdots+b_{t}$ and $m=m_{1}+\cdots+m_{t}$. Given
$i\in\\{0,1,\cdots,t\\}$, set

  * •

$\widehat{b_{i}}=n-(b_{1}+\cdots+b_{i})$;

  * •

$\widehat{m_{i}}=m-(m_{1}+\cdots+m_{i})$ and

  * •

$\widetilde{u^{i+1}}=(u^{i+1},\cdots,u^{t})\in\mathbb{F}_{q}^{\widehat{b_{i}}}$.

With this definitions we have that
$w_{(\overline{P},\pi)}(u)=\widehat{m_{i}}+w_{\pi_{i}}(u^{i})$ where
$w_{\pi_{i}}(u^{i})$ is the $(\Gamma_{P}^{i},\pi|_{\Gamma_{P}^{i}})$-weight of
$u^{i}$, the block weight as introduced in [2]. Given a linear $(P,\pi)$-code
$\mathcal{C}$, the set

$\mathcal{C}_{i}=\\{u\in\mathcal{C}:\widetilde{u^{i+1}}=0\\}$

is a subcode of $\mathcal{C}$ that can be decomposed as
$\mathcal{C}_{i}=\mathcal{C}_{i}^{0}\sqcup\mathcal{C}_{i}^{1}$ where

$\mathcal{C}_{i}^{0}=\\{u\in\mathcal{C}_{i}:u^{i}=0\\}\ \mbox{ and }\
\mathcal{C}_{i}^{1}=\\{u\in\mathcal{C}_{i}:u^{i}\neq 0\\}.$

Given $i\in[t]$, the weight enumerator of the $i$-level of $P$ is defined as

$LW_{\mathcal{C},(P,\pi)}^{(i)}(x):=\sum_{j=1}^{m_{i}}A_{r_{i}+j}x^{r_{i}+j}.$
(3)

The coefficients of this polynomial represent the weight distribution of code-
words such that its support contains elements in the $i$-level and do not
contain elements that are above the $i$-level. If we define
$LW_{\mathcal{C},(P,\pi)}^{(0)}(x)=A_{0}$, it is clear that

$W_{\mathcal{C},(P,\pi)}(x;y_{0},y_{1},\cdots,y_{t})=\sum_{i=0}^{t}LW_{\mathcal{C},(P,\pi)}^{(i)}(x)y_{i}.$
(4)

If for each $i\in[t]$ we have that $y_{j}=1$ for $j\leqslant i$ and $y_{j}=0$
for all $j>i$, then the leveled $(P,\pi)$-weight enumerator of $\mathcal{C}$
coincides with the $(P,\pi)$-weight enumerator of $\mathcal{C}_{i}$, hence,

$\displaystyle
W_{\mathcal{C}_{i},(P,\pi)}(x)-W_{\mathcal{C}_{i-1},(P,\pi)}(x)$
$\displaystyle=LW_{\mathcal{C},(P,\pi)}^{(i)}(x)$
$\displaystyle=\sum_{u\in\mathcal{C}_{i}^{1}}x^{w_{(P,\pi)}(u)}.$ (5)

We introduce now some concepts related to additive characters, that will be
used in the proof in a way similar to what was done first by MacWilliams [12]
in the classical case and later in the poset case (see [4], [5] and [11]).

###### Definition 4

An additive character $\chi$ in $\mathbb{F}_{q}$ is an homomorphism of the
additive group $\mathbb{F}_{q}$ into the multiplicative group of complex
numbers with norm $1$. If $\chi\equiv 1$, we say that $\chi$ is the trivial
additive character.

###### Lemma 4

Let $\chi$ be a non trivial additive character of $\mathbb{F}_{q}$ and
$\alpha$ a fix element of $\mathbb{F}_{q}^{j}$. Then

$\sum_{\beta\in\mathbb{F}_{q}^{j}}\chi(\alpha\cdot\beta)=\left\\{\begin{array}[]{lc}q^{j},&\mbox{if
}\alpha\mbox{ is null}\\\ 0,&\mbox{otherwise}\\\ \end{array}\right.$

###### Lemma 5

Let $\chi$ be a non trivial additive character of $\mathbb{F}_{q}$. For any
linear code $\mathcal{C}\subset\mathbb{F}_{q}^{n}$

$\sum_{v\in\mathcal{C}}\chi(u\cdot
v)=\left\\{\begin{array}[]{lcl}0,&\mbox{if}&u\in\mathbb{F}_{q}^{n}\backslash\mathcal{C}^{\perp}\\\
|\mathcal{C}|,&\mbox{if}&u\in\mathcal{C}^{\perp}\\\ \end{array}\right.$

###### Definition 5

(Hadamard Transform) Let $f$ be a complex function defined in
$\mathbb{F}_{q}^{n}$. The Hadamard transform of $f$ is

$\widehat{f}(u)=\sum_{v\in\mathbb{F}_{q}^{n}}\chi(u\cdot v)f(v).$

The proof of the following lemma may be found in [13].

###### Lemma 6

(Discrete Poisson Summation Formula) Let
$\mathcal{C}\subset\mathbb{F}_{q}^{n}$ be a linear code and $f$ a complex
function defined on $\mathbb{F}_{q}^{n}$. Then

$\sum_{v\in\mathcal{C}^{\perp}}f(v)=\frac{1}{|\mathcal{C}|}\sum_{u\in\mathcal{C}}\widehat{f}(u).$
(6)

In case both the block and the poset structures are trivial (the Hamming
case), the use of the discrete Poisson summation formula to establish the
MacWilliams identity is simple: just consider $f(u)=x^{w_{H}(u)}$ and apply
the discrete Poisson summation formula to the Hadamard transform
$\widehat{f}(u)=(1+(q-1)x)^{n-w_{H}(u)}(1-x)^{w_{H}(u)}$ (as in [12]). If
$f(u)=x^{w_{(\overline{P},\pi)}(u)}z_{s_{\overline{P}}(u)}$, where
$s_{\overline{P}}(u)=min\\{i:u^{i}\in\mathbb{F}_{q}^{b_{i}}\backslash\\{0\\}\\}$
and $s_{\overline{P}}(0)=t+1$, then

$\sum_{u\in\mathcal{C}^{\perp}}f(u)=W_{\mathcal{C}^{\perp},(\overline{P},\pi)}(x;z_{t+1},\cdots,z_{1}).$
(7)

Therefore we will extend this result determining the Hadamard transform of the
function $f(u)=x^{w_{(\overline{P},\pi)}(u)}z_{s_{\overline{P}}(u)}$.

Given $i\in\\{0,\cdots,t\\}$, we set

$B_{i}=\\{u\in\mathbb{F}_{q}^{n}:u^{j}=0\ \forall\ 1\leqslant j\leqslant
i\text{ and }u^{i+1}\neq 0\\}$

and then

$\displaystyle\widehat{f}(u)$
$\displaystyle=\sum_{v\in\mathbb{F}_{q}^{n}}\chi(u\cdot v)f(v)$
$\displaystyle=\sum_{i=0}^{t}\sum_{v\in B_{i}}\chi(u\cdot v)f(v)$
$\displaystyle=\sum_{i=0}^{t}\sum_{v\in B_{i}}\chi(u\cdot
v)x^{w_{(\overline{P},\pi)}(v)}z_{s_{\overline{P}}(v)}.$

Defining $S_{i}(u)=\sum_{v\in B_{i}}\chi(u\cdot
v)x^{w_{(\overline{P},\pi)}(v)}z_{s_{\overline{P}}(v)}$, since $B_{t}=\\{0\\}$
it follows that

$\widehat{f}(u)=z_{t+1}+\sum_{i=1}^{t}S_{i-1}(u).$ (8)

The proof of the sufficiency condition will be done with the aid of four
lemmas that allow us to determine $\sum_{u\in\mathcal{C}}\widehat{f}(u)$ as a
function of the leveled weight enumerator of $\mathcal{C}$. From Equation (8)
and assuming that the poset is hierarchical and that blocks at the same level
has the same dimension, we get the following four lemmas.

###### Lemma 7

To $i\in[t]$, denote $\gamma_{i}=(q^{d_{i}}-1)$, then for all
$u\in\mathbb{F}_{q}^{n}$ we have that

$S_{i-1}(u)=z_{i}x^{\widehat{m_{i}}}q^{\widehat{b_{i}}}[(1-x)^{w_{\pi_{i}}(u^{i})}(1+\gamma_{i}x)^{m_{i}-w_{\pi_{i}}(u^{i})}-1]$

if $\widetilde{u^{i+1}}$ is a null vector and $S_{i-1}(u)=0$ if
$\widetilde{u^{i+1}}$ is not a null vector.

###### Proof:

Since $P$ is a hierarchical poset, if $v\in B_{i-1}$, then
$w_{(\overline{P},\pi)}(v)=\widehat{m_{i}}+w_{\pi_{i}}(v^{i})$, and we denote
$v=(v^{1},\cdots,v^{i},\widetilde{v^{i+1}})$. By definition of $S_{i-1}(u)$
and since a character is an additive homomorphism, we have that

$\displaystyle
S_{i-1}(u)=z_{i}x^{\widehat{m_{i}}}\sum_{\widetilde{v^{i+1}}\in\mathbb{F}_{q}^{\widehat{b_{i}}}}$
$\displaystyle\chi(\widetilde{u^{i+1}}\cdot\widetilde{v^{i+1}})\times$
$\displaystyle\sum_{v^{i}\in\mathbb{F}_{q}^{b_{i}}\backslash\\{0\\}}\chi(u^{i}\cdot
v^{i})x^{w_{\pi_{i}}(v^{i})}.$ (9)

By Lemma 4

$\sum_{\widetilde{v^{i+1}}\in\mathbb{F}_{q}^{\widehat{b_{i}}}}\chi(\widetilde{u^{i+1}}\cdot\widetilde{v^{i+1}})=\left\\{\begin{array}[]{lc}q^{\widehat{b_{i}}},&\mbox{if
}\widetilde{u^{i+1}}\mbox{ is null}\\\ 0,&\mbox{otherwise}\\\
\end{array}\right.$ (10)

Being $r_{i}=m_{1}+\cdots+m_{i-1}$ and $\chi$ a non trivial additive
character, since $v_{r_{i}+j}\in\mathbb{F}_{q}^{d_{i}}$ for every
$j\in\\{1,\cdots,m_{i}\\}$ and
$w_{\pi_{i}}(v^{i})=\sum_{j=1}^{m_{i}}\delta(v_{r_{i}+j})$ where $\delta(u)$
is the Kronecker function (it returns $1$ if $u$ is not null and $0$
otherwise), it follows that

$\displaystyle\sum_{v^{i}\in\mathbb{F}_{q}^{b_{i}}}\chi(u^{i}\cdot v^{i})$
$\displaystyle x^{w_{\pi_{i}}(v^{i})}=$ $\displaystyle\ \ \ \ \
\prod_{j=1}^{m_{i}}\sum_{v_{r_{i}+j}\in\mathbb{F}_{q}^{d_{i}}}\chi(u_{r_{i}+j}\cdot
v_{r_{i}+j})x^{\delta(v_{r_{i}+j})}.$

Therefore, if $u_{r_{i}+j}$ is a null vector, then

$\sum_{v_{r_{i}+j}\in\mathbb{F}_{q}^{d_{i}}}\chi(u_{r_{i}+j}\cdot
v_{r_{i}+j})x^{\delta(v_{r_{i}+j})}=1+\gamma_{i}x.$

If $u_{r_{i}+j}$ is not a null vector, since
$u_{r_{i}+j}\notin(\mathbb{F}_{q}^{d_{i}})^{\perp}$, then by Lemma 5

$\displaystyle\sum_{v_{r_{i}+j}\in\mathbb{F}_{q}^{d_{i}}}\chi($ $\displaystyle
u_{r_{i}+j}\cdot v_{r_{i}+j})x^{\delta(v_{r_{i}+j})}=$ $\displaystyle
1+x\sum_{v_{r_{i}+j}\in\mathbb{F}_{q}^{d_{i}}\backslash\\{0\\}}\chi(u_{r_{i}+j}\cdot
v_{r_{i}+j})=1-x,$

hence

$\displaystyle\sum_{v^{i}\in\mathbb{F}_{q}^{b_{i}}\backslash\\{0\\}}\chi(u^{i}$
$\displaystyle\cdot v^{i})x^{w_{\pi_{i}}(v^{i})}=$
$\displaystyle(1-x)^{w_{\pi_{i}}(u^{i})}(1+\gamma_{i}x)^{m_{i}-w_{\pi_{i}}(u^{i})}-1.$
(11)

The result follows from Equations (II-B), (10) and (11). ∎

###### Lemma 8

Given $i\in[t]$, define

$Q_{i}(x):=\frac{1-x}{1+\gamma_{i}x},$
$a_{i}(x):=q^{\widehat{b_{i}}}\left(\frac{1+\gamma_{i}x}{x}\right)^{m-\widehat{m_{i}}}(1-x)^{\widehat{m_{i-1}}}$

and

$c_{i}(x):=x^{\widehat{m_{i}}}q^{\widehat{b_{i}}}\left(\frac{1-x}{Q_{i}(x)}\right)^{m_{i}},$

where $\gamma_{i}=q^{d_{i}}-1$. Then,

$\displaystyle\sum_{u\in\mathcal{C}}\widehat{f}(u)=$
$\displaystyle|\mathcal{C}|z_{t+1}$
$\displaystyle+\left(\frac{x}{1-x}\right)^{m}\sum_{i=1}^{t}a_{i}(x)z_{i}LW_{\mathcal{C},(P,\pi)}^{(i)}(Q_{i}(x))$
$\displaystyle+\sum_{i=1}^{t}z_{i}c_{i}(x)|\mathcal{C}_{i-1}|-\sum_{i=1}^{t}z_{i}x^{\widehat{m_{i}}}q^{\widehat{b_{i}}}|\mathcal{C}_{i}|.$
(12)

###### Proof:

If $u\notin\mathcal{C}_{i}$ then $\widetilde{u^{i+1}}$ is not a null vector
and by Lemma 7 we find that

$\displaystyle\sum_{u\in\mathcal{C}}$ $\displaystyle S_{i-1}(u)=$
$\displaystyle\sum_{u\in\mathcal{C}_{i}}S_{i-1}(u)+\sum_{u\in\mathcal{C}\backslash\mathcal{C}_{i}}S_{i-1}(u)=$
$\displaystyle
z_{i}x^{\widehat{m_{i}}}q^{\widehat{b_{i}}}\left[\left(\frac{1-x}{Q_{i}(x)}\right)^{m_{i}}\sum_{u\in\mathcal{C}_{i}}Q_{i}(x)^{w_{\pi_{i}}(u^{i})}-|\mathcal{C}_{i}|\right].$
(13)

If $u\in\mathcal{C}_{i}^{1}$, then
$w_{(P,\pi)}(u)=w_{\pi_{i}}(u^{i})+(m-\widehat{m_{i-1}})$, and if
$u\in\mathcal{C}_{i}^{0}$ we have $w_{\pi_{i}}(u^{i})=0$. Since
$\mathcal{C}_{i-1}=\mathcal{C}_{i}^{0}$, then
$|\mathcal{C}_{i-1}|=|\mathcal{C}_{i}^{0}|$ and hence

$\displaystyle\sum_{u\in\mathcal{C}_{i}}Q_{i}(x$
$\displaystyle)^{w_{\pi_{i}}(u^{i})}=$
$\displaystyle\sum_{u\in\mathcal{C}_{i}^{1}}Q_{i}(x)^{w_{\pi_{i}}(u^{i})}+\sum_{u\in\mathcal{C}_{i}^{0}}Q_{i}(x)^{w_{\pi_{i}}(u^{i})}=$
$\displaystyle\frac{1}{Q_{i}(x)^{m-\widehat{m_{i-1}}}}\sum_{u\in\mathcal{C}_{i}^{1}}Q_{i}(x)^{w_{(P,\pi)}(u)}+|\mathcal{C}_{i-1}|.$
(14)

Since $m-\widehat{m_{i+1}}+m_{i}=m-\widehat{m_{i}}$ and by Equation (3) we
have that
$\sum_{u\in\mathcal{C}_{i}^{1}}Q_{i}(x)^{w_{(P,\pi)}(u)}=LW_{\mathcal{C},(P,\pi)}^{(i)}(Q_{i}(x))$,
by replacing Equation (14) into (13) it follows that

$\displaystyle\sum_{u\in\mathcal{C}}S_{i-1}(u)$
$\displaystyle=\left(\frac{x}{1-x}\right)^{m}q^{\widehat{b_{i}}}\left(\frac{1+\gamma_{i}x}{x}\right)^{m-\widehat{m_{i}}}\times$
$\displaystyle(1-x)^{\widehat{m_{i-1}}}z_{i}LW_{\mathcal{C},(P,\pi)}^{(i)}(Q_{i}(x))+$
$\displaystyle+z_{i}x^{\widehat{m_{i}}}q^{\widehat{b_{i}}}\left[\left(\frac{1-x}{Q_{i}(x)}\right)^{m_{i}}|\mathcal{C}_{i-1}|-|\mathcal{C}_{i}|\right].$
(15)

By Identity (8), $\widehat{f}(u)=z_{t+1}+\sum_{i=1}^{t}S_{i-1}(u)$, then by
Equation (15)

$\displaystyle\sum_{u\in\mathcal{C}}$
$\displaystyle\widehat{f}(u)=|\mathcal{C}|z_{t+1}+\sum_{i=1}^{t}\sum_{u\in\mathcal{C}}S_{i-1}(u)$
$\displaystyle=|\mathcal{C}|z_{t+1}+\left(\frac{x}{1-x}\right)^{m}\sum_{i=1}^{t}a_{i}(x)z_{i}LW_{\mathcal{C},(P,\pi)}^{(i)}(Q_{i}(x))$
$\displaystyle\ \ \
+\sum_{i=1}^{t}z_{i}c_{i}(x)|\mathcal{C}_{i-1}|-\sum_{i=1}^{t}z_{i}x^{\widehat{m_{i}}}q^{\widehat{b_{i}}}|\mathcal{C}_{i}|.$

∎

In the definition of $W_{\mathcal{C},(P,\pi)}(x;y_{0},\cdots,y_{t})$, the
$y_{i}^{\prime}s$ were considered as formal symbols. In two next lemmas we
consider specific situations that will determine the weight enumerator in the
stated conditions.

###### Lemma 9

Let

$g_{j}=\left\\{\begin{array}[]{ll}\sum_{i=j+1}^{t}c_{i}(x)z_{i},&\mbox{if
}0\leqslant j\leqslant t-1\\\ 0,&\mbox{if }j=t\end{array}.\right.$

Then

$\sum_{i=1}^{t}z_{i}c_{i}(x)|\mathcal{C}_{i-1}|=W_{\mathcal{C},(P,\pi)}(1;g_{0},\cdots,g_{t}).$

###### Proof:

Since $r_{i}=m_{1}+\cdots+m_{i-1}$ and

$|\mathcal{C}_{i}|=A_{0}+A_{1}+\cdots+A_{r_{i}+m_{i}}=\sum_{j=0}^{i}LW_{\mathcal{C},(P,\pi)}^{(j)}(1),$
(16)

then

$\displaystyle\sum_{i=1}^{t}z_{i}c_{i}($ $\displaystyle
x)|\mathcal{C}_{i-1}|=$ $\displaystyle
A_{0}(c_{1}(x)z_{1}+c_{1}(x)z_{2}+\cdots+c_{t}(x)z_{t})$
$\displaystyle+(A_{1}+\cdots+A_{m_{1}})(c_{2}(x)z_{2}+\cdots+c_{t}(x)z_{t})$
$\displaystyle+\cdots+$
$\displaystyle+(A_{m_{1}+\cdots+m_{t-2}+1}+\cdots+A_{m_{1}+\cdots+m_{t-1}})c_{t}(x)z_{t}$
$\displaystyle=$
$\displaystyle\sum_{i=0}^{t}LW_{\mathcal{C},(P,\pi)}^{(i)}(1)g_{i}$

hence the result follows from Identity (4). ∎

The proof of the next lemma is omitted since it follows the same steps as in
the proof of Lemma 9.

###### Lemma 10

Let

$h_{j}=\left\\{\begin{array}[]{ll}\sum_{i=j}^{t}z_{i}x^{\widehat{m_{i}}}q^{\widehat{b_{i}}},&\mbox{if
}1\leqslant j\leqslant t\\\
\sum_{i=1}^{t}z_{i}x^{\widehat{m_{i}}}q^{\widehat{b_{i}}},&\mbox{if
}j=0\end{array}.\right.$

Then

$\sum_{i=1}^{t}z_{i}x^{\widehat{m_{i}}}q^{\widehat{b_{i}}}|\mathcal{C}_{i}|=W_{\mathcal{C},(P,\pi)}(1;h_{0},\cdots,h_{t}).$

Before we proceed to prove the next theorem we recall we are assuming the
following collection of conditions and notations:

  * •

$(P,\pi)$ a poset-block over $[m]$ with $t$ levels;

  * •

$P$ is hierarchical;

  * •

$r_{i}=m_{1}+\cdots+m_{i-1}$;

  * •

$\Gamma_{P}^{i}=\\{r_{i}+1,\cdots,r_{i}+m_{i}\\}$;

  * •

$d_{i}=\pi(r_{i}+j)$ for every $j\in\\{1,\cdots,m_{i}\\}$;

  * •

$b_{i}=m_{i}d_{i}$ is such that $\sum_{i=1}^{t}b_{i}=n$.

Now we can prove that necessary conditions stated in Theorem 1 are also
sufficient to have a MW-I.

###### Theorem 2

Under the conditions above stated, the poset-block $(P,\pi)$ admits a
MacWilliams-type identity.

###### Proof:

By (6) and (7) we have that

$W_{\mathcal{C}^{\perp},(\overline{P},\pi)}(x;z_{t+1},\cdots,z_{1})=\frac{1}{|\mathcal{C}|}\sum_{u\in\mathcal{C}}\widehat{f}(u).$
(17)

Considering Equation (4) we have that

$a_{i}(x)z_{i}LW_{\mathcal{C},(P,\pi)}^{(i)}(Q_{i}(x))=W_{\mathcal{C},(P,\pi)}(Q_{i}(x);y_{0},\cdots,y_{t}),$

for every $i\in\\{1,\cdots,t\\}$, where $a_{i}(x)z_{i}=y_{i}$ and $y_{j}=0$
for every $j\neq i$. Substituting the identities obtained in Lemma 9 and Lemma
10 into Equation (8) it follows that

$\displaystyle|\mathcal{C}|$ $\displaystyle
W_{\mathcal{C}^{\perp},(\overline{P},\pi)}(x;z_{t+1},\cdots,z_{1})=|\mathcal{C}|z_{t+1}$
$\displaystyle\ \ \
+\left(\frac{x}{1-x}\right)^{m}W_{\mathcal{C},(P,\pi)}(Q_{1}(x);0,a_{1}(x)z_{1},0,\cdots,0)$
$\displaystyle\ \ \
+\left(\frac{x}{1-x}\right)^{m}W_{\mathcal{C},(P,\pi)}(Q_{2}(x);0,0,a_{2}(x)z_{2},0,\cdots,0)$
$\displaystyle\ \ \
+\cdots+\left(\frac{x}{1-x}\right)^{m}W_{\mathcal{C},(P,\pi)}(Q_{t}(x);0,\cdots,0,a_{t}(x)z_{t})$
$\displaystyle\ \ \
+W_{\mathcal{C},(P,\pi)}(1;g_{0},\cdots,g_{t})-W_{\mathcal{C},(P,\pi)}(1;h_{0},\cdots,h_{t}).$

On the left side of the above equality we have the leveled weight enumerator
of $\mathcal{C}^{\perp}$ (the dual code of $\mathcal{C}$). On the right side
we have an expression that depends not on the code itself but only on the
leveled weight enumerator of $\mathcal{C}$. Hence, if $\mathcal{C}_{1}$ is a
linear $(P,\pi)$-code that has the same $(P,\pi)$-polynomial as $\mathcal{C}$,
since $W_{\mathcal{C}_{1}^{\perp},(\overline{P},\pi)}(x;1,\cdots,1)$ is the
$(\overline{P},\pi)$-polynomial of $\mathcal{C}_{1}^{\perp}$, it follows that

$W_{\mathcal{C}_{1}^{\perp},(\overline{P},\pi)}(x;1,\cdots,1)=W_{\mathcal{C}^{\perp},(\overline{P},\pi)}(x;1,\cdots,1),$

ie, the $(\overline{P},\pi)$-polynomial of $\mathcal{C}^{\perp}$ is uniquely
determined by $(P,\pi)$-polynomial of $\mathcal{C}$ for every code
$\mathcal{C}$, hence the poset-block structure admits a MW-I. ∎

###  II-C Relationship between Weight Distributions

In this section, we will use the same conditions and notations stated before
Theorem 2 in the previous section. For every $k\in\\{0,\cdots,n\\}$, let

$P_{k}^{\gamma_{i}}(x:n)=\sum_{l=0}^{k}(-1)^{l}\gamma_{i}^{k-l}\genfrac{(}{)}{0.0pt}{}{x}{l}\genfrac{(}{)}{0.0pt}{}{n-x}{k-l}$

be the Krawtchouk polynomial whose generator function is given by

$(1+\gamma_{i}z)^{n-x}(1-z)^{x}=\sum_{k=0}^{\infty}P_{k}^{\gamma_{i}}(x:n)z^{k}.$
(18)

If $x\in\\{0,\cdots,n\\}$, we can switch the upper limit of summation by $n$.
This generator functions arise naturally when we are setting a relationship
between the $(P,\pi)$-polynomial coefficients of $\mathcal{C}$ and the
$(\overline{P},\pi)$-polynomial coefficients of $\mathcal{C}^{\perp}$ (for
details about the Krawtchouk polynomials in coding theory, see [12]).

###### Lemma 11

Let $(P,\pi)$ be a poset-block over $[m]$ that admits MW-I and $\mathcal{C}$ a
linear $(P,\pi)$-code with length $n$. Then

$\displaystyle|$
$\displaystyle\mathcal{C}|W_{\mathcal{C}^{\perp},(\overline{P},\pi)}(x)=|\mathcal{C}|+$
$\displaystyle\sum_{i=1}^{t}q^{\widehat{b_{i}}}x^{\widehat{m_{i}}}\left[\sum_{k=1}^{m_{i}}\left(a_{k}(j:m_{i})+\binom{m_{i}}{k}\gamma_{i}^{k}|\mathcal{C}_{i-1}|\right)x^{k}\right]$
(19)

where
$a_{k}(j:m_{i})=\sum_{j=1}^{m_{i}}A_{r_{i}+j}P_{k}^{\gamma_{i}}(j:m_{i})$.

###### Proof:

Set

$\displaystyle E_{1}$ $\displaystyle(x)=$
$\displaystyle\sum_{i=1}^{t}q^{\widehat{b_{i}}}\left(\frac{1+\gamma_{i}x}{x}\right)^{m-\widehat{m_{i}}}(1-x)^{\widehat{m_{i-1}}}LW_{\mathcal{C},(P,\pi)}^{(i)}(Q_{i}(x))$

and

$E_{2}(x)=\sum_{i=1}^{t}x^{\widehat{m_{i}}}q^{\widehat{b_{i}}}\left(\left(\frac{1-x}{Q_{i}(x)}\right)^{m_{i}}|\mathcal{C}_{i-1}|-|\mathcal{C}_{i}|\right).$

Putting $z_{1}=\cdots=z_{t+1}=1$ and replacing (8) in (17), it follows that

$W_{\mathcal{C}^{\perp},(\overline{P},\pi)}(x)=\
1+F_{1}(x)+\frac{1}{|\mathcal{C}|}E_{2}(x)$ (20)

where $F_{1}(x)=\frac{1}{|\mathcal{C}|}\frac{x^{m}}{(1-x)^{m}}E_{1}(x)$. Using
the Identity (3) in $E_{1}(x)$ and recalling that $r_{i}=m-\widehat{m_{i-1}}$
and $\widehat{m_{i}}-\widehat{m_{i-1}}=m_{i}$, it follows that

$\displaystyle E_{1}(x)$
$\displaystyle=\sum_{i=1}^{t}q^{\widehat{b_{i}}}\left(\frac{1+\gamma_{i}x}{x}\right)^{m-\widehat{m_{i}}}(1-x)^{\widehat{m_{i-1}}}\times$
$\displaystyle\ \ \ \ \ \ \ \
\sum_{j=1}^{m_{i}}A_{r_{i}+j}\left(\frac{1-x}{1+\gamma_{i}x}\right)^{r_{i}+j}$
$\displaystyle=\sum_{i=1}^{t}\frac{q^{\widehat{b_{i}}}}{x^{m-\widehat{m_{i}}}}\sum_{j=1}^{m_{i}}A_{r_{i}+j}(1+\gamma_{i}x)^{m_{i}-j}(1-x)^{m+j},$

and therefore

$\displaystyle F_{1}(x)$
$\displaystyle=\frac{1}{|\mathcal{C}|}\sum_{i=1}^{t}q^{\widehat{b_{i}}}x^{\widehat{m_{i}}}\sum_{j=1}^{m_{i}}A_{r_{i}+j}(1+\gamma_{i}x)^{m_{i}-j}(1-x)^{j}$
$\displaystyle=\frac{1}{|\mathcal{C}|}\sum_{i=1}^{t}q^{\widehat{b_{i}}}x^{\widehat{m_{i}}}\sum_{j=1}^{m_{i}}A_{r_{i}+j}\sum_{k=0}^{m_{i}}P_{k}^{\gamma_{i}}(j:m_{i})x^{k}$
(21)

where the second equality follows from (18). Hence if

$a_{k}(j:m_{i})=\sum_{j=1}^{m_{i}}A_{r_{i}+j}P_{k}^{\gamma_{i}}(j:m_{i}),$

since $P_{0}^{\gamma_{i}}=1$, and then
$a_{0}(j:m_{i})=|\mathcal{C}_{i}|-|\mathcal{C}_{i-1}|$ by (16). Therefore

$\displaystyle|\mathcal{C}|$ $\displaystyle F_{1}(x)=$
$\displaystyle\sum_{i=1}^{t}q^{\widehat{b_{i}}}x^{\widehat{m_{i}}}\sum_{k=0}^{m_{i}}\left(\sum_{j=1}^{m_{i}}A_{r_{i}+j}P_{k}^{\gamma_{i}}(j:m_{i})\right)x^{k}$
$\displaystyle=\sum_{i=1}^{t}q^{\widehat{b_{i}}}x^{\widehat{m_{i}}}\left(|\mathcal{C}_{i}|-|\mathcal{C}_{i-1}|+\sum_{k=1}^{m_{i}}a_{k}(j:m_{i})x^{k}\right).$
(22)

From Newton’s binomial theorem we have that

$\displaystyle E_{2}(x)=$
$\displaystyle\sum_{i=1}^{t}x^{\widehat{m_{i}}}q^{\widehat{b_{i}}}\left[\left(1+\sum_{k=1}^{m_{i}}\binom{m_{i}}{k}\gamma_{i}^{k}x^{k}\right)|\mathcal{C}_{i-1}|-|\mathcal{C}_{i}|\right]$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{t}x^{\widehat{m_{i}}}q^{\widehat{b_{i}}}\left(|\mathcal{C}_{i-1}|-|\mathcal{C}_{i}|+\sum_{k=1}^{m_{i}}\binom{m_{i}}{k}\gamma_{i}^{k}|\mathcal{C}_{i-1}|x^{k}\right)$
(23)

and the result follows from (20), (22) and (23). ∎

In the conditions stated in Lemma (11) we have that

$\displaystyle W$ ${}_{\mathcal{C}^{\perp},(\overline{P},\pi)}(x)=$
$\displaystyle\overline{A}_{0}+(\overline{A}_{1}x+\cdots+\overline{A}_{m_{t}}x^{m_{t}})$
$\displaystyle+(\overline{A}_{m_{t}+1}x+\cdots+\overline{A}_{m_{t}+m_{t-1}}x^{m_{t-1}})x^{m_{t}}$
$\displaystyle+\cdots+$
$\displaystyle+(\overline{A}_{m_{t}+\cdots+m_{2}+1}x+\cdots+\overline{A}_{m_{t}+\cdots+m_{1}}x^{m_{1}})x^{m_{t}+\cdots+m_{2}}$
$\displaystyle=1+\sum_{i=1}^{t}x^{\widehat{m_{i}}}\sum_{k=1}^{m_{i}}\overline{A}_{\widehat{m_{i}}+k}x^{k}$
(24)

therefore from (19) and (24) follows the next theorem, that characterizes the
weight distribution of $\mathcal{C}^{\perp}$ in terms of the distribution of
$\mathcal{C}$.

###### Theorem 3

Let $(P,\pi)$ be a hierarchical poset-block over $[m]$ with $t$ levels
satisfying MW-I and $\mathcal{C}$ a linear $(P,\pi)$-code with length $n$ over
$\mathbb{F}_{q}$. Being $\gamma_{i}=(q^{d_{i}}-1)$ and $b_{j}$ the dimension
of $\Gamma_{P}^{j}$, for any given $i\in[t]$ and $k\in[m_{i}]$ we have that

$\displaystyle\overline{A}_{\widehat{m_{i}}+k}=$
$\displaystyle\frac{q^{\widehat{b_{i}}}}{|\mathcal{C}|}\sum_{j=1}^{m_{i}}\left(A_{r_{i}+j}P_{k}^{\gamma_{i}}(j:m_{i})\right)$
$\displaystyle+\frac{q^{\widehat{b_{i}}}}{|\mathcal{C}|}\binom{m_{i}}{k}\gamma_{i}^{k}\sum_{j=0}^{r_{i}}A_{j}.$

We remark that when we consider a trivial structure of blocks, $b_{j}=m_{j}$
and $d_{j}=1$ for all $j\in[t]$, then we have the result obtained in Theorem
4.4 from [5]. On the other hand, when considering a trivial poset structure
(an antichain poset where none of elements are comparable), then $t=1$ and
$m=m_{1}$, hence given $k\in[m_{1}]$ we have that

$\overline{A}_{k}=\frac{1}{|\mathcal{C}|}\sum_{j=0}^{m}A_{j}P_{k}^{\gamma_{1}}(j:m).$

## Acknowledgment

The first author is currently pursuing the M.Sc. degree in the Institute of
Mathematics, Statistics and Scientific Computing–UNICAMP. He was supported by
CAPES. The second author was partially supported by FAPESP, grant
$2007$/$56052$–$8$. A partial and initial version of this work was will appear
in the Proceedings of ITW 2011.

## References

  * [1] H. Niederreiter, “A combinatorial problem for vector spaces over finite fields,” _Discrete Mathematics_ , vol. 96, pp. 221–228, 1991.
  * [2] K. Feng, L. Xu, and F. J. Hickernell, “Linear error-block codes,” _Finite Fields and Their Applications_ , vol. 12, pp. 638–652, 2006.
  * [3] R. A. Brualdi, J. Graves, and K. Lawrence, “Codes with a poset metric,” _Discrete Mathematics_ , vol. 147, pp. 57–72, 1995.
  * [4] D. S. Kim and D. C. Kim, “Character sums and MacWilliams identities,” _Discrete Mathematics_ , vol. 287, pp. 155–160, 2004.
  * [5] H. K. Kim and D. Y. Oh, “A classification of posets admitting the MacWilliams identity,” _IEEE Transactions on Information Theory_ , vol. 51, no. 4, pp. 1424–1431, Apr. 2005.
  * [6] S. Ling and F. Özbudak, “Constructions and bounds on linear error-block codes,” _Des. Codes Cryptogr._ , vol. 45, pp. 297–316, 2007.
  * [7] L. Panek, M. Firer, H. K. Kim, and J. Y. Hyun, “Groups of linear isometries on poset structures,” _Discrete Mathematics_ , vol. 308, pp. 4116–4123, 2008\.
  * [8] M. M. S. Alves, L. Paneck, and M. Firer, “Error-block codes and poset metrics,” _Advances in Mathematics of Communications_ , vol. 2, no. 1, pp. 95–111, 2008.
  * [9] M. Y. Rosembloom and M. A. Tsfasman, “Codes for m-metric,” _Problems of Information Transmission_ , vol. 33, no. 1, pp. 45–52, 1997.
  * [10] J. N. Gutiérrez and H. Tapia-Recillas, “A MacWilliams identity for poset-codes,” _Congr. Numer_ , vol. 133, pp. 63–73, 1998.
  * [11] D. S. Kim and J. G. Lee, “A MacWilliams-type identity for linear codes on weak order,” _Discrete Mathematics_ , vol. 262, pp. 181–194, 2003.
  * [12] F. J. MacWilliams and N. J. Sloane, _The Theory of Error-Correcting Codes_. Amsterdam, The Netherlands: North-Holland, 1977.
  * [13] R. Lidl and H. Niederreiter, _Finite Fields_ , 2nd ed., ser. Encyclopedia of Mathematics and its Applications. Cambridge, U.K.: Cambridge University Press, 1997, no. 20.

Marcelo Firer received the B.Sc. and M.Sc. degrees in 1989 and 1991
respectively, from State University of Campinas, Brazil, and the Ph.D. degree
from the Hebrew University of Jerusalem, in 1997, all in Mathematics. He is
currently an Associate Professor of the State University of Campinas. His
research interest includes coding theory, action of groups, semigroups and
Tits buildings.
---
Jerry A. Pinheiro receives the B.Sc. in 2006 in Computer Science and in 2008
in Mathematics, from Higher Education Center of Foz do Iguaçu and Western
Parana State University respectively. He is currently pursuing the M.Sc.
degree in the Institute of Mathematics, Statistics and Scientific Computing of
the State University of Campinas. His current research interest includes
poset-block codes and error-correcting codes.
---