%% This document created by Scientific Word (R) Version 3.0 \documentclass[12pt,letterpaper]{article} \newtheorem{theorem}{Theorem} \newtheorem{corollary}{Corollary} \newtheorem{conjecture}{Conjecture} \newtheorem{lemma}{Lemma} \newtheorem{proposition}{Proposition} \newtheorem{axiom}{Axiom} \newtheorem{remark}{Remark} \newtheorem{example}{Example} \newtheorem{exercise}{Exercise} \newtheorem{definition}{Definition} \usepackage{amsmath} \usepackage{graphicx} \usepackage{amsfonts} \usepackage{amssymb} %TCIDATA{OutputFilter=latex2.dll} %TCIDATA{TCIstyle=article/art4.lat,lart,article} %TCIDATA{CSTFile=article.cst} %TCIDATA{Created=Wed Jul 03 10:41:26 1996} %TCIDATA{LastRevised=Wed Jul 29 12:33:30 1998} %TCIDATA{} %TCIDATA{Language=American English} \pagestyle{myheadings} \markright{\sc the electronic journal of combinatorics 5 (1998), R37\hfill} \thispagestyle{empty} \setlength{\textwidth}{6in} \setlength{\textheight}{9in} \setlength{\oddsidemargin}{0.2in} \setlength{\evensidemargin}{\oddsidemargin} \setlength{\topmargin}{0in} \setlength{\headsep}{7mm} \newcommand\qed{\hfill\rule{3mm}{2.8mm}} \newcommand\proof{\medskip\noindent{\bf Proof. }} \begin{document} \author{Stefan Dodunekov\\Institute of Mathematics and Informatics\\Bulgarian Academy of Sciences\\8 G. Bontchev Str.\\1113 Sofia, Bulgaria\\e-mail: stedo@moi2.math.acad.bg \and Juriaan Simonis\\Delft University of Technology\\Faculty of Information Technology and Systems\\Department of Technical Mathematics and Informatics\\P.O. Box 5031\\2600 GA Delft, the Netherlands\\e-mail: J.Simonis@twi.tudelft.nl} \title{Codes and Projective Multisets} \date{Submitted: December 25, 1997; Accepted: July 27, 1998.} \maketitle \begin{abstract} The paper gives a matrix-free presentation of the correspondence between full-length linear codes and projective multisets. It generalizes the Brouwer-Van Eupen construction that transforms projective codes into two-weight codes. Short proofs of known theorems are obtained. A new notion of self-duality in coding theory is explored. 94B05, 94B27, 51E22. \end{abstract} \section{Introduction} We start by describing the main idea in an informal way. Let $G$ be a generator matrix of a $q$-ary linear $[n,k,d]$-code $\mathcal{C},$ and let $\mathbf{g}_{1},\mathbf{g}_{2},\ldots,\mathbf{g}_{n}\in\mathbb{F}_{q}^{k}$ be the columns of $G$. Suppose that none of the $\mathbf{g}_{i}$'s is the zero vector. (We say that the code $\mathcal{C}$ is of \emph{full length}.) Then each $\mathbf{g}_{i}$ determines a point $[\mathbf{g}_{i}]$ in the projective space $\Pi:=\mathbb{P}(\mathbb{F}_{q}^{k}).$ If the $\mathbf{g}_{i}$ happen to be pair-wise independent, then $X:=\{[\mathbf{g}_{1}],[\mathbf{g}_{2}% ],\ldots,[\mathbf{g}_{n}]\}$ is a set of $n$ points in $\Pi.$ When dependence occurs, we interpret $X$ as a \emph{multiset} and count each point with the appropriate multiplicity. Different generator matrices yield projectively equivalent codes. In fact, we have a bijective correspondence between the equivalence classes of full-length $q$-ary linear codes and the projective equivalence classes of multisets in finite Desarguesian projective spaces. It is easy to recover minimum distance $d$ of $\mathcal{C}$ from $X$. A nonzero codeword $\mathbf{c}:=(c_{1},c_{2},\ldots,c_{n})\in\mathcal{C}$ corresponds to the hyperplane $H_{c}$ in $\Pi$ with equation $c_{1}\xi_{1}+c_{2}\xi _{2}+\cdots+c_{n}\xi_{n}=0$ and the weight of $\mathbf{c}$ equals the size of $X\cap(\Pi\setminus H_{\mathbf{c}}).$ So $d=n-\min|X\cap H|$, where $H$ runs through the hyperplanes of $\Pi$. The first one to use this relationship between linear codes and projective multisets was Slepian \cite{Slep56}, who used the term \emph{modular representation.} See also \cite{Pete72}. Delsarte, Hill and others studied the relation between projective two-weight codes and projective $(n,k,h_{1}% ,h_{2})$ sets. These are subsets of size $n$ of $\mathbb{P}(\mathbb{F}_{q}% ^{k})$ with the property that every hyperplane is met in $h_{1}$ points or $h_{2}$ points. Two-weight codes are surveyed in Calderbank and Cantor's paper \cite{Cald86}. Subsets of a finite projective space that have a small intersection with all subspaces of a given dimension have been extensively studied by finite geometers. In \cite{Hirs97}, Hirschfeld and Storme survey the known results with respect to so-called $(n;r,s;N,q)$\emph{-sets}. These are spanning subsets $K\subset\mathbb{P}(\mathbb{F}_{q}^{N+1})$ of size $n$ and such that all $s$-dimensional projective subspaces of $\mathbb{P}(\mathbb{F}_{q}^{N+1})$ intersect $K$ in at most $s$ points. So $(n;k-2,n-d;k-1,q)$-sets correspond to $q$-ary linear $[n,k,d]$-codes for which the columns of any generator matrix are pair-wise independent. Other good references are the survey papers by Hill \cite{Hill92a} and Landgev \cite{Land97b}. Yet another terminology has been introduced by Hamada and Tamari in \cite{Hama78}. They defined a \emph{minihyper} (\emph{maxhyper}) $\{f,m;t,q\}$ to be a multiset $w$ in $\mathbb{P}(\mathbb{F}_{q}^{t+1})$ of size $f$ and such that all hyperplanes intersect $w$ in at most (at least) $m$ points. Hence there is a bijective correspondence between the $\{n,n-d;k-1,q\}$ maxhypers that span $\mathbb{P}(\mathbb{F}_{q}^{k})$ and the (equivalence classes) of $q$-ary linear $[n,k,d]$-codes. A recent survey of results on minihypers and their relation to codes meeting the Griesmer bound can be found in \cite{Hama93i}. Goppa's work \cite{Gopp81} initiated a constant flow of contributions to coding theory by algebraic geometers. Of course, the natural setting here is the correspondence between linear codes and projective multisets. A good example is the book \cite{Tsfa91}. where the term ''projective system'' is used. As a matter of fact, in Problem 1.1.9 of \cite{Tsfa91} the reader is invited to ''Rewrite existing books on coding theory in terms of projective systems''. The present paper can be regarded as a first step towards this goal. Quite recently, Brouwer and Van Eupen published a gem of a paper, \cite{Brou97}, in which they used a correspondence between projective codes and two-weight codes to construct optimal codes and to prove the uniqueness of certain codes. Their construction, a generalization of an old result on projective two-weight codes (cf. \cite{Hill78a}, Th. 8.7, or \cite{Cald86}, Th. 5.2), transforms subsets of a finite projective space $\Pi$ into multisets of the dual space $\Pi^{\ast}$. Although mainly dual transforms of ''degree'' one are considered, the final section of their paper gives a more general construction in which the degree of the dual transform is arbitrary. Our paper describes the dual transform in its full generality. \textbf{Outline of the paper} Section 2 contains a concise introduction to algebraic coding theory and fixes notation. In particular, we introduce the \emph{reduced distribution matrix} of a code, a convenient notion in our treatment of the dual transform. In Section 3, we list some basic properties of projective multisets. The notion of \emph{lifting} is introduced. We need this notion in Proposition 2 to repair a minor flaw in \cite{Brou97}. The section also contains a matrix-free presentation of the correspondence between full-length linear codes and projective multisets. Section 4 is devoted to the dual transform of multisets. We give simple expresssions of the basic parameters of the dual transform in terms of the reduced distribution matrix of the dual of the original code. Section 5 treats dual transforms of degree one. To demonstrate the effectiveness of this concept, we give short proofs of a theorem of Ward, a theorem of Bonisoli and the uniqueness of the generalized MacDonald codes. Finally, Section 6 explores a new kind of duality in coding theory. A code $\mathcal{C}$ is said to be $\sigma$-self-dual if its dual transform $\mathcal{C}^{\sigma}$ is equivalent to $\mathcal{C}$. We give a list of examples and derive strong conditions in the case of transforms of degree one. \section{Codes} \subsection{Basic definitions} Let $\mathbb{F}_{q}$ be the finite field of $q$ elements and let $S$ be a finite set of size $n.$ \begin{definition} The \emph{standard vector space} $\mathbb{F}_{q}^{S}$ over $\mathbb{F}_{q}$ is the $\mathbb{F}_{q}$-vector space of the mappings $\mathbf{x}:S\rightarrow\mathbb{F}_{q}.$ (If $S:=\{1,2,\ldots,n\},$ we usually write $\mathbb{F}_{q}^{n}$ for $\mathbb{F}_{q}^{S}.$)\newline The value of $\mathbf{x}\in\mathbb{F}_{q}^{S}$ in $s\in S$ is denoted by $x_{s}.$ \end{definition} The \emph{natural basis} $\{\mathbf{e}_{s}\mid s\in S\}$ of $\mathbb{F}% _{q}^{S}$ is defined by $(\mathbf{e}_{s})_{t}:=\left\{ \begin{array} [c]{lll}% 1 & \text{if} & s=t,\\ 0 & \text{if} & s\neq t. \end{array} \right.$ So the dimension of $\mathbb{F}_{q}^{S}$ is equal to $n.$ \begin{definition} Let $S,$ $S^{\prime}$ be two sets of size $n,$ and let $\{\mathbf{e}_{s}\mid s\in S\},$ $\{\mathbf{e}_{s^{\prime}}^{\prime}\mid s^{\prime}\in S^{\prime}\}$ be the natural bases of $\mathbb{F}_{q}^{S}$, $\mathbb{F}_{q}^{S^{\prime}}$ respectively. A linear isomorphism $\mu:\mathbb{F}_{q}^{S}\rightarrow \mathbb{F}_{q}^{S^{\prime}}$ is said to be \emph{monoidal} if nonzero elements $a_{s}\in\mathbb{F}_{q}$ and a bijection $\sigma:S\rightarrow S^{\prime}$ exist such that $\mu(\mathbf{e}_{s})=a_{s}\mathbf{e}_{\sigma(s)}^{\prime}$ for all $s\in S.$ \end{definition} \begin{definition} A $q$-ary \emph{(linear) code }$\mathcal{C}$ of \emph{length} $n$ and \emph{dimension} $k$ is a $k$-dimensional linear subspace of the $n$-dimensional standard vector space $\mathbb{F}_{q}^{S}$. Two codes $\mathcal{C}\subseteq\mathbb{F}_{q}^{S},$ $\mathcal{C}^{\prime}\subseteq \mathbb{F}_{q}^{S^{\prime}}$ are said to be \emph{equivalent} if a monoidal isomorphism $\mu:\mathbb{F}_{q}^{S}$ $\rightarrow\mathbb{F}_{q}^{S^{\prime}}%$exists such that $\mu(\mathcal{C})=\mathcal{C}^{\prime}.$ \end{definition} \subsection{Weight and distance} The \emph{Hamming weight} $|\mathbf{x}|$ of a vector $\mathbf{x}\in \mathbb{F}_{q}^{S}$ is the size of its support: $|\mathbf{x}|:=|\{s\mid s\in S\land x_{s}\neq0\}|.$ The Hamming weight is a norm on the vector space $\mathbb{F}_{q}^{S}.$ The induced metric, with distance function $d(\mathbf{x},\mathbf{y}):=|\mathbf{x}-\mathbf{y}|,\ \mathbf{x},\mathbf{y}% \in\mathbb{F}_{q}^{S},$ is called the \emph{Hamming metric}. Note that the monoidal isomorphisms are precisely the linear isomorphisms that leave the Hamming weight invariant. Hence equivalent codes are isometric. \begin{definition} The \emph{weight distribution} of a code $\mathcal{C}\subseteq\mathbb{F}% _{q}^{S}$ is the sequence $A_{0}(\mathcal{C}),A_{1}(\mathcal{C}),\ldots,A_{n}(\mathcal{C})$ defined by $A_{i}(\mathcal{C}):=|\{\mathbf{c}\mid\mathbf{c}\in\mathcal{C}\land |\mathbf{c}|=i\}|,\ i=0,1,\ldots,n.$ The \emph{weight set} of $\mathcal{C}$ is the set $W_{\mathcal{C}}:=\{i\mid i\in\{1,2,\ldots,n\}\land A_{i}(\mathcal{C})\neq0\}$ and the \emph{minimum weight} of $\mathcal{C}$ is the integer $d_{\mathcal{C}}:=\min W_{\mathcal{C}}.$ \end{definition} Let $D_{i}(\mathcal{C},\mathbf{x}):=|\{\mathbf{c}\mid\mathbf{c}\in\mathcal{C}\land d(\mathbf{x},\mathbf{c})=i\}|$ be the number of codewords at distance $i$ from $\mathbf{x}\in\mathbb{F}% _{q}^{S}.$ \begin{definition} \emph{(Cf. \cite{Dels73})} The\emph{\ distribution matrix} of $\mathcal{C}$ is the $q^{n}\times(n+1)$ matrix $\mathbf{D}$ parametrized by $\mathbb{F}_{q}% ^{S}\times\{0,1,\ldots,n\}$ having $D_{i}(\mathcal{C},\mathbf{x})$ as its $(\mathbf{x},i)$ entry. \end{definition} The linearity of $\mathcal{C}$ immediately implies that $D_{i}(\mathcal{C}% ,\mathbf{x})=D_{i}(\mathcal{C},\mathbf{x+c})$ for all $c\in\mathbb{\mathcal{C}% }$. In other words, the rows of $\mathbf{D}$ are constant on the cosets of $\mathcal{C}$. Moreover, $D_{i}(\mathcal{C},a\mathbf{x})=D_{i}(\mathcal{C}% ,\mathbf{x})$ for all $a\in\mathbb{F}_{q}\setminus\{0\}.$ Hence the following definition makes sense. \begin{definition} The \emph{reduced distribution matrix} of $\mathcal{C}$ is the $\frac {q^{n-k}-1}{q-1}\times(n+1)$ matrix $\mathbf{\bar{D}}$ parametrized by $\mathbb{P}(\mathbb{F}_{q}^{S}/\mathcal{C})\times\{0,1,\ldots,n\}$ and having\textbf{\ }$D_{i}(\mathcal{C},\mathbf{x})-D_{i}(\mathcal{C},\mathbf{o})$ as its $([\mathbf{\bar{x}]},i)$ entry. (Here $\mathbf{\bar{x}}$ denotes the vector in $\mathbb{F}_{q}^{S}/\mathcal{C}$ corresponding to the coset $\mathbf{x}+\mathcal{C}$ and $[\mathbf{\bar{x}]}$ denotes the projective point determined by $\mathbf{\bar{x}}$ in the projective space $\mathbb{P}% (\mathbb{F}_{q}^{S}/\mathcal{C})$ over $\mathbb{F}_{q}^{S}/\mathcal{C}$.) The $(i+1)$-st column of $\mathbf{\bar{D}}$ will be denoted by $\mathbf{\bar{D}% }_{i}.$ \end{definition} \subsection{Dual codes} The standard inner product on $\mathbb{F}_{q}^{S}$ is defined by $\left\langle \mathbf{x},\mathbf{y}\right\rangle :=\sum_{s\in S}x_{s}% y_{s},\ \mathbf{x},\mathbf{y}\in\mathbb{F}_{q}^{S}.$ \begin{definition} \label{dual}The \emph{dual} of a code $\mathcal{C}\subseteq\mathbb{F}_{q}^{S}$ is the code $\mathcal{C}^{\perp}:=\{\mathbf{x}\mid\mathbf{x}\in\mathbb{F}_{q}^{S}% \land\left\langle \mathbf{x},\mathbf{c}\right\rangle =0\text{ for all }\mathbf{c}\in\mathcal{C}\}.$ The \emph{external distance} $t_{\mathcal{C}}$ of $\mathcal{C}$ is the size of the weight set of $\mathcal{C}^{\perp}$ and the \emph{dual distance} of $\mathcal{C}$ is the minimum distance of $\mathcal{C}^{\perp}$. A code $\mathcal{C}$ is said to be \emph{of full length} if $d_{\mathcal{C}^{\perp}% }\geq2$ and \emph{projective} if $d_{\mathcal{C}^{\perp}}\geq3$. \end{definition} The external distance of a code $\mathcal{C}$ gives information about its distribution matrix. In fact, Delsarte proved the \begin{theorem} \label{rank}\emph{(\cite{Dels73})} The rank of the distribution matrix $\mathbf{D}$ of$\mathcal{\ C}$ is equal to $t_{\mathcal{C}}+1.$ In fact, the first $t_{\mathcal{C}}+1$ columns of $\mathbf{D}$ are independent and the $i$-th column of $\mathbf{D}$ can be expressed in these columns by a linear relation that only depends on $k,$ $n,$ $q,$ $i$ and the weight set $W_{\mathcal{C}^{\perp}}$ of $\mathcal{C}^{\perp}.$ \end{theorem} In 1963, MacWilliams found a remarkable relation between the weight spectra of $\mathcal{C}$ and $\mathcal{C}^{\perp}.$ \begin{theorem} \emph{(\cite{Macw63})} For $i=0,1,\ldots,n,$ we have the identities $\sum_{j=0}^{n}\binom{n-j}iA_{j}(\mathcal{\mathcal{C}})=q^{k-i}\sum_{j=0}% ^{n}\binom{n-j}{n-i}A_{j}(\mathcal{C}^{\perp}).$ \end{theorem} If we solve this system of equations for the $A_{j}(\mathcal{C}),$ we find \begin{equation} A_{i}(\mathcal{C})=q^{k-n}\sum_{j=0}^{n}K_{i}(j)A_{j}(\mathcal{\mathcal{C}% }^{\perp}), \label{MacWilliams}% \end{equation} with $K_{i}(j):=\sum_{m=0}^{i}(-1)^{m}(q-1)^{i-m}\binom jm\binom{n-j}{i-m}.$ The $K_{i}(j)$ are polynomials of degree $i$ in $j,$ the so-called \emph{Krawtchouk polynomials}, cf. \cite{Kraw29}. A comprehensive description can be found in \cite{Macw83}, pp. 129 ff., 150 ff.. We shall need the fact that the $K_{i}(j)$ satisfy the \emph{orthogonality relations} \begin{equation} \sum_{j=0}^{n}K_{l}(j)K_{j}(i)=q^{n}\delta_{l,i},\ l,i=0,1,\ldots,n. \label{orthogonality}% \end{equation} \section{Projective multisets} \subsection{Basic definitions} Let $\Pi:=\mathbb{P}(\mathcal{V})$ be the projective space over a finite-dimensional $\mathbb{F}_{q}$-vector space $\mathcal{V}$, and let $\mathbb{N}$ denote the set of the nonnegative integers. \begin{definition} A \emph{projective multiset} in $\Pi$ is a mapping $\gamma:\Pi\rightarrow \mathbb{N}$ of $\Pi$ into $\mathbb{N}.$ The \emph{multiplicity} of a point $p\in\Pi$ in $\gamma$ is the integer $\gamma(p).$ The \emph{multiplicity set} of $\gamma$ is the set $M_{\gamma}:=\operatorname{Im}\gamma.$ \end{definition} If $M_{\gamma}\subseteq\{0,1\}$, we identify $\gamma$ with its support and call it a \emph{set.} \begin{definition} The \emph{spanning space} of $\gamma$ is the projective span $\Sigma_{\gamma}:=\left\langle \operatorname*{supp}(\gamma)\right\rangle$ of the support $\operatorname*{supp}(\gamma):=\{p\mid p\in\Pi\land\gamma(p)\neq0\}.$ of $\gamma$ in $\Pi.$ The \emph{dimension} of $\gamma$ is the integer $k_{\gamma}:=\dim\Sigma_{\gamma}+1.$ \end{definition} \begin{definition} Two projective multisets $\gamma,$ $\gamma^{\prime}$ are said to be \emph{equivalent} if a projective isomorphism $\varphi:\Sigma_{\gamma }\rightarrow\Sigma_{\gamma^{\prime}}$ exists such that $\gamma=\gamma^{\prime }\circ\varphi.$ \end{definition} For example, any projective multiset $\gamma:\Pi\rightarrow\mathbb{N}$ is equivalent to the restriction $\left. \gamma\right| _{\Sigma_{\gamma}}$ of $\gamma$ to its spanning space. We can extend the mapping $\gamma$ to the \emph{power set} of $\Pi$ as follows. \begin{definition} If $W\subseteq\Pi$ is any subset, then $\gamma(W):=\sum_{p\in W}\gamma(p).$ In particular, the integer $n_{\gamma}:=\gamma(\Pi)$ is called the\emph{\ length} of the multiset $\gamma$. \end{definition} \subsection{Projective multisets and full-length codes} In Definition \ref{dual}, we defined a full-length code to be a code with dual distance $\geq2$. This can be rephrased as follows: a code $\mathcal{C}% \subseteq\mathbb{F}_{q}^{S}$ is of full length if and only if the natural basis $\{\mathbf{e}_{s}\mid s\in S\}$ does not intersect the dual code $\mathcal{C}^{\perp}.$ \begin{definition} Let $\mathcal{C}\subseteq\mathbb{F}_{q}^{S}$ be a full-length code, and let $\overline{\mathbf{e}_{s}}$ denote the image of the standard basis vector $\mathbf{e}_{s}$ under the quotient mapping $\mathbb{F}_{q}^{S}\rightarrow \mathbb{F}_{q}^{S}/\mathcal{C}^{\perp}.$ Then the multiset $\gamma_{\mathcal{C}}:\mathbb{P}(\mathbb{F}_{q}^{S}/\mathcal{C}^{\perp })\rightarrow\mathbb{N},\ p\mapsto|\{s\mid p=[\overline{\mathbf{e}_{s}}]\}|$ is called the \emph{projective multiset induced by} $\mathcal{C}.$ \end{definition} \begin{remark} The multiset induced by $\mathcal{C}$ can be identified with the (second) column $\mathbf{\bar{D}}_{1}$ of the reduced distribution matrix $\mathbf{\bar{D}}$ of $\mathcal{\mathcal{C}^{\perp}}.$ \end{remark} The length and dimension of a full-length code $\mathcal{C}$ are equal to the length and dimension of the induced multiset $\gamma_{\mathcal{C}}.$ A full-length code $\mathcal{C}$ is \emph{projective} if and only if the induced multiset $\gamma_{\mathcal{C}}$ is a \emph{set}. \begin{proposition} Any projective multiset is equivalent to a projective multiset induced by a code. Two induced multisets $\gamma_{\mathcal{C}},$ $\gamma_{\mathcal{C}% ^{\prime}}$ are equivalent if and only if the codes $\mathcal{C},$ $\mathcal{C}^{\prime}$ are equivalent. \end{proposition}% %TCIMACRO{\TeXButton{Proof}{\proof}}% %BeginExpansion \proof %EndExpansion Let $\gamma:\Pi:=\mathbb{P}(\mathcal{V})\rightarrow\mathbb{N}$ be a projective multiset of dimension $k$ and length $n.$ Choose a list $(\mathbf{v}% _{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{n})$ of vectors $\mathbf{v}_{i}% \in\mathcal{V}$ such that $\{[\mathbf{v}_{1}],[\mathbf{v}_{2}],\ldots,[\mathbf{v}_{n}% ]\}=\operatorname*{supp}(\gamma)$ and such that each point $p\in\Pi$ occurs in the list $([\mathbf{v}% _{1}],[\mathbf{v}_{2}],\ldots,[\mathbf{v}_{n}])$ with multiplicity $\gamma(p).$ Consider the linear mapping $\varphi:\mathbb{F}_{q}% ^{n}\rightarrow\mathcal{V}$ fixed by $\varphi(\mathbf{e}_{i})=\mathbf{v}_{i},$ $i=1,2,\ldots,n.$ If we put $\mathcal{C}:=\ker(\varphi)^{\perp},$ then $\gamma=\gamma_{\mathcal{C}}.$ Secondly, if two full-length codes $\mathcal{C},$ $\mathcal{C}^{\prime}$ are equivalent under a monoidal isomorphism $\mu:\mathbb{F}_{q}^{S}\rightarrow\mathbb{F}_{q}^{S^{\prime}},$ then $\mu(\mathcal{C}^{\perp})=\mathcal{\mathcal{C}}^{\prime}\mathcal{^{\perp }}.$ So the induced projective isomorphism $\tilde{\mu}:\mathbb{P}% (\mathbb{F}_{q}^{S}/\mathcal{C}^{\perp})\rightarrow\mathbb{P}(\mathbb{F}% _{q}^{S^{\prime}}/\mathcal{C}^{\prime\perp})$ is well-defined. It obviously defines an equivalence between the projective multisets $\gamma_{\mathcal{C}}$ and $\gamma_{\mathcal{C}^{\prime}}.$ Conversely, let $\mathcal{C}\subseteq\mathbb{F}_{q}^{S},$ $\mathcal{C}% ^{\prime}\subseteq\mathbb{F}_{q}^{S^{\prime}}$ be two full-length codes such that $\gamma_{\mathcal{C}}$ and $\gamma_{\mathcal{C}^{\prime}}$ are equivalent. Let $\varphi:\mathbb{F}_{q}^{S}/\mathcal{C}^{\perp}\rightarrow \mathbb{F}_{q}^{S^{\prime}}/\mathcal{C}^{\prime\perp}$ be a linear isomorphism such that the induced projective isomorphism $\tilde{\varphi}:\mathbb{P}% (\mathbb{F}_{q}^{S}/\mathcal{C}^{\perp})\rightarrow\mathbb{P}(\mathbb{F}% _{q}^{S^{\prime}}/\mathcal{C}^{\prime\perp})$ is an equivalence between $\gamma_{\mathcal{C}}$ and $\gamma_{\mathcal{C}^{\prime}}.$ Then a bijection $\sigma:S\rightarrow S^{\prime}$ exists such that $\tilde{\varphi}% ([\overline{\mathbf{e}_{s}}])=[\overline{\mathbf{e}_{\sigma(s)}^{\prime}}],$ $s\in S.$ So nonzero elements $a_{s}\in\mathbb{F}_{q}$ exist such that $\varphi(\overline{\mathbf{e}_{s}})=a_{s}\overline{\mathbf{e}_{\sigma (s)}^{\prime}},$ $s\in S.$ Now the monoidal isomorphism $\mu:\mathbb{F}% _{q}^{S}\rightarrow\mathbb{F}_{q}^{S^{\prime}}$ fixed by $\mu(\mathbf{e}% _{s}):=a_{s}\mathbf{e}_{\sigma(s)}^{\prime}$, $s\in S,$ determines an equivalence between $\mathcal{C}$ and $\mathcal{C}^{\prime}.\hfill$% %TCIMACRO{\TeXButton{End Proof}{\qed}}% %BeginExpansion \qed %EndExpansion \begin{description} \item [\textbf{Notation}]If $\gamma$ is a projective multiset, then $\mathcal{C}_{\gamma}$ denotes any code such that the multiset induced by $\mathcal{C}_{\gamma}$ is equivalent to $\gamma.$ The preceding proposition shows that the code $\mathcal{C}_{\gamma}$ exists and that it is determined by $\gamma$ up to equivalence. \end{description} \subsection{Quotient multisets} An interesting way to obtain new projective multisets from old ones is by considering \emph{quotient spaces}. Let $\mathcal{U}$ be an $(m+1)$% -dimensional linear subspace of the vector space $\mathcal{V},$and let $L:=\mathbb{P}(\mathcal{U})$ be the corresponding $m$-dimensional projective subspace of the projective space $\Pi:=\mathbb{P}(\mathcal{V}).$ Then the points of the projective space $\Pi/L:=\mathbb{P}(\mathcal{V}/\mathcal{U})$ can be identified with the $(m+1)$-dimensional projective subspaces $M$ of $\Pi$ such that $M\supset L.$ More generally, the $i$-dimensional subspaces of $\Pi/L$ correspond to the $(i+m+1)$-dimensional subspaces of $\Pi$ that contain $L$. In particular, the dual space $(\Pi/L)^{*}$ will be identified with the subspace of $\Pi^{*}$ consisting of all hyperplanes in $\Pi$ that contain $L.$ \begin{definition} The \emph{quotient multiset} of $\gamma$ by $L$ is the mapping $\gamma^{L}% :\Pi/L\rightarrow\mathbb{N}$ defined by $(\gamma^{L})(M):=\gamma(M\setminus L),\ M\in\Pi/L.$ \end{definition} Note that the dimension of $\gamma^{L}$ is equal to $k_{\gamma}-\dim (L\cap\Sigma_{\gamma})-1.$ \begin{remark} Let $\gamma:=\gamma_{\mathcal{C}}$ be the projective multiset induced by the code $\mathcal{C}\subseteq\mathbb{F}_{q}^{S}.$ An $m$-dimensional subspace $L\subseteq\mathbb{P}(\mathbb{F}_{q}^{S}/\mathcal{\mathcal{C}^{\perp}})$ is of the form $\mathbb{P}(\mathcal{U}),$ where $\mathcal{U}$ is a subspace of the vector space $\mathbb{F}_{q}^{S}/\mathcal{\mathcal{C}^{\perp}}.$ If $\mathcal{W}$ is the inverse image of $\mathcal{U}$ under the quotient mapping $\mathbb{F}_{q}^{S}\rightarrow\mathbb{F}_{q}^{S}/\mathcal{\mathcal{C}^{\perp}% }$, then $\mathcal{D}:=\mathcal{W}^{\perp}$ is a subcode of codimension $m+1$ in $\mathcal{C}$ and $\gamma^{L}=\gamma_{\mathcal{D}}.$ So the quotient multisets of $\gamma$ correspond to the subcodes of $\mathcal{C}$ of the same codimension. \end{remark} \subsection{Weights\label{weights}} Now we turn to the dual space $\Pi^{*}$ of the projective space $\Pi.$ (The points of $\Pi^{*}$ are the hyperplanes $H\subset\Pi$.) \begin{definition} The \emph{weight function} of $\gamma$ is the mapping $\mu:\Pi^{*}\rightarrow\mathbb{N},\ H\longmapsto\gamma(\Pi\setminus H).$ The \emph{weight set} of $\gamma$ is the set $W_{\gamma}:=\operatorname{Im}\mu\setminus\{0\}.$ The \emph{minimum weight} of $\gamma$ is the integer $d_{\gamma}:=\min W_{\gamma}.$ The \emph{frequency} of a weight $w\in W_{\gamma}$ is the integer $f_{w}(\gamma):=q^{\dim\Sigma_{\gamma}-\dim\Pi}|\mu^{-1}(w)|.$ \end{definition} Note that $\mu^{-1}(0)=(\Pi/\Sigma_{\gamma})^{*}.$ Hence $\mu$ takes the value $0$ if and only if $\dim\gamma<\dim\Pi+1.$ \begin{remark} The weight distribution of $\mathcal{C}_{\gamma}$ and the frequencies $f_{w}(\gamma)$ of $\gamma$ are related as follows: $A_{i}(\mathcal{C}_{\gamma})=\left\{ \begin{array} [c]{lll}% 1 & \text{for} & i=0,\\ 0 & \text{for} & i\notin W_{\gamma}\cup\{0\},\\ (q-1)f_{w}(\gamma) & \text{for} & i\in W_{\gamma}. \end{array} \right.$ Hence the weight set of $\mathcal{C}_{\gamma}$ is equal to $W_{\gamma}$. In particular, the minimum weight of $\mathcal{C}_{\gamma}$ is the minimum weight of $\gamma.$ \end{remark} \begin{example} \label{MacD}Let the projective multiset $\gamma$ be (the characteristic function of) the complement of a $(u-1)$-dimensional subspace $L$ of a $(k-1)$-dimensional projective space $\Pi$. Denote by $% %TCIMACRO{\QATOPD{[}{]}{k}{j}}% %BeginExpansion \genfrac{[}{]}{0pt}{}{k}{j}% %EndExpansion$ the $q$-ary \emph{Gaussian binomial coefficient}. If $u=0,$ then $\mathcal{C}_{\gamma}$ is called a \emph{simplex code}, with parameters $\lbrack% %TCIMACRO{\QATOPD{[}{]}{k}{1}}% %BeginExpansion \genfrac{[}{]}{0pt}{}{k}{1}% %EndExpansion ,\ k,\ q^{k-1}].$ It has only one weight: $q^{k-1}$. If $k>u>0,$then $\mathcal{C}_{\gamma}$ is called a \emph{Macdonald code}, with parameters $\lbrack% %TCIMACRO{\QATOPD{[}{]}{k}{1}}% %BeginExpansion \genfrac{[}{]}{0pt}{}{k}{1}% %EndExpansion -% %TCIMACRO{\QATOPD{[}{]}{u}{1}}% %BeginExpansion \genfrac{[}{]}{0pt}{}{u}{1}% %EndExpansion ,\ k,\ q^{k-1}-q^{u-1}].$ This code is a two-weight code, with weights $q^{k-1}-q^{u-1}$ and $q^{k-1}.$ Both the simplex codes and the MacDonald codes attain the Griesmer bound. Hence they are length-optimal. \end{example} \subsection{Simple constructions} In this section, we describe two methods of constructing a new projective multiset $\gamma^{\prime}$ from a projective multiset $\gamma.$ In both cases the parameters of $\gamma^{\prime}$ only depend on those of $\gamma$ and on the construction parameters. \subsubsection{Linear transforms} Let $\gamma$ be a projective multiset on the projective space $\Pi$, and let $a\in\mathbb{Q}^{*},b\in\mathbb{Q}$ be such that $\gamma^{\prime}:\Pi\rightarrow\mathbb{Q},\ \gamma^{\prime}(p):=a\gamma(p)+b,$ is a projective multiset, i.e. such that $\operatorname{Im}\gamma^{\prime }\subset\mathbb{N}$ . Putting $l:=\dim\Pi+1,$ we find that $n_{\gamma^{\prime}}=an+b% %TCIMACRO{\QATOPD{[}{]}{l}{1}}% %BeginExpansion \genfrac{[}{]}{0pt}{}{l}{1}% %EndExpansion$ and $\mu_{\gamma^{\prime}}(H)=a\mu_{\gamma}(H)+bq^{l-1}.$ If $b\neq0,$ the dimensions $k,$ $k^{\prime}$ of $\gamma$ and $\gamma^{\prime }$ may differ. In fact, if $k^{\prime}\neq k$ then either $k=l$ or $k^{\prime}=l.$ If $k^{\prime}\leq k,$ then $W_{\gamma^{\prime}}=\{aw+bq^{l-1}\mid w\in W_{\gamma}\}\setminus\{0\}$ and $f_{w^{\prime}}(\gamma^{\prime})=q^{k^{\prime}-k}f_{w}(\gamma),\ w^{\prime }=aw+bq^{l-1}.$ Three special cases are particularly important: \begin{itemize} \item $\gamma^{\prime}(p):=a\gamma(p),$ with $a\in\mathbb{N}.$ Then the code $\mathcal{C}_{\gamma^{\prime}}$ is said to be the $a$-fold \emph{replication} of $\mathcal{C}_{\gamma}.$ \item $\gamma^{\prime}(p):=m-\gamma(p),$ with $m:=\max M_{\gamma}.$ In this case $\mathcal{C}_{\gamma^{\prime}}$ is called an \emph{anticode} of $\mathcal{C}_{\gamma}.$ The Macdonald codes, for instance, are the anticodes of the simplex codes. \item $\gamma^{\prime}(p):=\gamma(p)+b,$ $b\in\mathbb{N}.$ Then $\mathcal{C}% _{\gamma^{\prime}}$ is said to be obtained from $\mathcal{C}_{\gamma}$ by \emph{adding} $b$ \emph{simplex codes} of dimension $l.$ \end{itemize} \begin{example} If we add $t-1$ simplex codes of dimension $k$ to the $[% %TCIMACRO{\QATOPD{[}{]}{k}{1}}% %BeginExpansion \genfrac{[}{]}{0pt}{}{k}{1}% %EndExpansion -% %TCIMACRO{\QATOPD{[}{]}{u}{1}}% %BeginExpansion \genfrac{[}{]}{0pt}{}{u}{1}% %EndExpansion ,k,q^{k-1}-q^{u-1}]$ MacDonald code, we obtain a \emph{generalized MacDonald code}, with parameters $\lbrack t% %TCIMACRO{\QATOPD{[}{]}{k}{1}}% %BeginExpansion \genfrac{[}{]}{0pt}{}{k}{1}% %EndExpansion -% %TCIMACRO{\QATOPD{[}{]}{u}{1}}% %BeginExpansion \genfrac{[}{]}{0pt}{}{u}{1}% %EndExpansion ,\ k,\ tq^{k-1}-q^{u-1}].$ \end{example} \subsubsection{Lifting\label{lifted}} Let $N$ be an $(s-1)$-dimensional subspace of $\Pi$ and let $\gamma :\Pi/N\rightarrow\mathbb{N}$ be a\\ $k$-dimensional projective multiset of length $n.$ Choose a nonnegative integer $c$ and define a projective multiset $\gamma^{\prime}$ on $\Pi$ as follows: $\gamma^{\prime}(p):=\left\{ \begin{array} [c]{lll}% c & \text{if} & p\in N,\\ \gamma(Np) & \text{if} & p\notin N. \end{array} \right.$ We say that $\gamma^{\prime}$ is obtained from $\gamma$ by an $(s,c)$% -\emph{lifting }of $\gamma$ to $\Pi.$ If $s>0,$ the lifting is said to be \emph{proper}. So a properly lifted projective multiset $\gamma^{\prime}% :\Pi\rightarrow\mathbb{N}$ is characterized by the property that a nonempty projective subspace $N\subset\Pi$ exists such that $\gamma^{\prime}$ is constant on $N$ and on all sets $M\setminus N$, $M\in\Pi/N.$ The dimension of $\gamma^{\prime}$ is $k+s$ and its length is $q^{s}n+c% %TCIMACRO{\QATOPD{[}{]}{s}{1}}% %BeginExpansion \genfrac{[}{]}{0pt}{}{s}{1}% %EndExpansion .$ The weight function of $\gamma^{\prime}$ is given by $\mu_{\gamma^{\prime}}(H)=\left\{ \begin{array} [c]{lll}% (q-1)q^{s-1}n+q^{s-1}c & \text{if} & H\nsupseteq N,\\ q^{s}\mu_{\gamma}(H) & \text{if} & H\supseteq N. \end{array} \right.$ Hence the minimum weight of $\gamma^{\prime}$ is equal to $d_{\gamma^{\prime}}=\min\{q^{s}d_{\gamma},(q-1)q^{s-1}n+q^{s-1}c\}.$ Note that the quotient multiset $(\gamma^{\prime})^{N}$ is equivalent to $q^{s}\gamma.$ \begin{remark} \label{equivalent}If $\gamma,\delta:\Pi/N\rightarrow\mathbb{N}$ are equivalent, the $(s,c)$-lifted multisets $\gamma^{\prime},\delta^{\prime}% :\Pi\rightarrow\mathbb{N}$ are equivalent. \end{remark} \section{Dual transforms of multisets} \subsection{Definition and basis properties} Now consider any function $\sigma:W\rightarrow\mathbb{N}$ on the weight set $W:=W_{\gamma}$ of a projective multiset $\gamma :\Pi\rightarrow\mathbb{N}.$ Let us extend this function to a polynomial function $\sigma(i):=\sum_{y\in W}\sigma(y)\frac{\prod\limits_{w\in W\setminus y}% (i-w)}{\prod\limits_{w\in W\setminus y}(y-w)}$ on $\mathbb{Q}$ by Lagrange interpolation. Note that the degree $g:=g_{\sigma }$ of the polynomial $\sigma$ does not exceed $|W|-1=t-1$, where $t$ is the external distance of the dual of $\mathcal{C}_{\gamma}$. For each $\sigma,$ we shall construct from $\gamma$ a new multiset on the dual of the spanning space $\Sigma:=\Sigma_{\gamma}$. \begin{definition} The \emph{dual transform} of the projective multiset $\gamma$ with respect to $\sigma$ is the multiset $\gamma^{\sigma}:\Sigma^{*}\rightarrow\mathbb{N},\ H\longmapsto\sigma(\mu(H)).$ \end{definition} Obviously, the multiplicity set of $\Gamma:=\gamma^{\sigma}$ is the $\sigma$-image of the weight set of $\gamma:$% \begin{equation} M_{\Gamma}=\{\sigma(w)\mid w\in W_{\gamma}\}. \label{M_Gamma}% \end{equation} The length of $\Gamma$ is equal to $n_{\Gamma}=\sum_{w\in W}\sigma(w)f_{w}(\gamma)$ and its weight function is given by \begin{equation} \mu_{\Gamma}(p)=n_{\Gamma}-\sum_{H\ni p}\Gamma(H)=\sum_{w\in W}\sigma (w)\{f_{w}(\gamma)-f_{w}(\gamma^{p})\},\quad p\in\Sigma. \label{dualweight}% \end{equation} From (\ref{dualweight}), we see that the weight function $\mu_{\Gamma}$ is known if we can calculate the frequencies of all $1$-codimensional quotient multisets $\gamma^{p}$ of $\gamma.$ Now we turn to the dimension of $\Gamma.$ The dual of the spanning space $\Sigma_{\Gamma}$ of $\Gamma$ is equal to $N:=\mu_{\Gamma}^{-1}(0)\subseteq \Sigma_{\gamma}.$ Hence $N$ is a projective subspace of $\Sigma_{\gamma}$ and $\Sigma_{\Gamma}=(\Sigma/N)^{*}.$ This implies that the dimension $k_{\Gamma}$ of $\Gamma$ is equal to $k_{\gamma}-\dim N-1.$ In particular, \begin{equation} k_{\Gamma}0,a_{j}\neq0\}}}% %BeginExpansion {\displaystyle\sum\limits_{\{j\mid j>0,a_{j}\neq0\}}} %EndExpansion (q-1)^{j-1}\binom nj & \text{if} & w=q^{k-1}a_{0,}\\ & & \\% %TCIMACRO{\dsum \limits_{\{j\mid j>0,a_{j}=a_{i}\}}}% %BeginExpansion {\displaystyle\sum\limits_{\{j\mid j>0,a_{j}=a_{i}\}}} %EndExpansion (q-1)^{j-1}\binom nj & \text{if} & w=q^{k-1}(a_{0}-a_{i})\neq q^{k-1}a_{0}. \end{array} \right. \] \section{Dual transforms of degree one} Let $\mathcal{C}\subseteq\mathbb{F}_{q}^{S}$ be a $k$-dimensional full-length code of length $n,$ and let $\gamma:=\gamma_{\mathcal{C}}$ be the corresponding projective multiset on $\Pi:=\mathbb{P}(\mathbb{F}_{q}% ^{S}/\mathcal{C}^{\perp}).$ In this section, we study dual transforms $\mathcal{C}^{\sigma}$ under the assumption that the transform function $\sigma$ is \emph{has degree one:} $\sigma(j):=aj+b.$ Two choices for $\sigma$ are particularly useful: If $\Delta:=\gcd W,$ $d:=\min W$ and $D:=\max W,$ then the functions $\sigma_{+}$ and $\sigma_{-}$ defined by \begin{equation} \sigma_{+}(j):=\frac{j-d}{\Delta},\ \sigma_{-}(i):=\frac{-j+D}{\Delta} \label{sigma+}% \end{equation} indeed take nonnegative integer values on $W_{\mathcal{C}}$. \subsection{Length, weights, dimension, frequencies\label{Length}} Expressing the polynomial $\sigma$ in the Krawtchouk polynomials $K_{0}(j):=1$ and $K_{1}(j):=(q-1)n-qj,$ we get \begin{align*} \sigma(j) & =a_{0}K_{0}(j)+a_{1}K_{1}(j)=\\ & =(b+\frac{(q-1)an}q)K_{0}(j)+(-\frac aq)K_{1}(j). \end{align*} Let $\mathcal{D}:=\mathcal{C}^{\sigma}$ be the dual transform of $\mathcal{C}$ with respect to $\sigma.$ Since the code $\mathcal{C}$ is of full length, i.e. $A_{1}(\mathcal{C}^{\perp})=0,$ Formula (\ref{length}) for the length of $\mathcal{D}$ reduces to \begin{align} n_{\mathcal{D}} & =a_{0}(\frac{q^{k}}{q-1}-\frac1{q-1})+a_{1}n=\label{n_D}\\ & =nq^{k-1}a+% %TCIMACRO{\QATOPD{[}{]}{k}{1}}% %BeginExpansion \genfrac{[}{]}{0pt}{}{k}{1}% %EndExpansion b.\nonumber \end{align} Now we consider the weight function of $\Gamma:=\gamma^{\sigma}$. Formula (\ref{mu}) gives us \begin{align} \mu_{\Gamma}(p) & =-q^{k-1}\{(b+\frac{(q-1)an}q)\mathbf{\bar{D}}% _{p,0}+(-\frac aq)\mathbf{\bar{D}}_{p,1}\}=\nonumber\\ & =q^{k-2}\{qb+(q-1)an+a\gamma(p)\}=\label{muGamma}\\ & =\alpha\gamma(p)+\beta,\nonumber \end{align} with $\alpha:=q^{k-2}a$ and $\beta:=q^{k-1}b+q^{k-2}(q-1)an=\frac{(q-1)n_{\mathcal{D}}+b}q.$ \begin{remark} Note that the weight set $W_{\mathcal{D}}$ of $\mathcal{D}$ is equal to $\{\alpha m+\beta\mid m\in M_{\gamma}\}\setminus\{0\}.$ If, in particular, $\mathcal{C}$ is \emph{projective}, then $\mathcal{D}$ is a $(\leq2)$-weight code. This case is the main subject matter of Brouwer and Van Eupen's paper \cite{Brou97}. \end{remark} Next we discuss the possibility of a dimension drop. Put $N:=\{p\in\Pi\mid\alpha\gamma(p)+\beta=0\}.$ This is a projective subspace of $\Pi$ on which $\gamma$ has the constant value $-\frac\beta\alpha=-q\frac ba-(q-1)n.$ From (\ref{dimension}) we see that the dimension $k_{\mathcal{D}}$ of $\mathcal{D}$ is equal to $k$ unless $-q\frac ba-(q-1)n\in M_{\gamma}.$ If $p\in\Pi\setminus N,$ then $w:=\mu_{\Gamma}(p)\in W_{\mathcal{D}}.$ Moreover $\gamma$ takes the constant value $\frac{w-\beta}\alpha$ on $Np\setminus N.$ Hence if $k_{\mathcal{D}}0,\\ (an+b)q^{k-1}+a(\max M_{\gamma}-n)q^{k-2} & \text{if} & a<0. \end{array} \right. \] If$k_{\mathcal{D}}1$,$r\mid q.$Since all weights$w_{\rho},\rho=1,...,n$are divisible by$q+1,$the code$\mathbf{\Gamma}_{0}$is a$(q+1)$-fold replicated code extended by an appropriate number of zero columns. \end{example} \begin{proposition} (\cite{Boni84}) Let$\mathcal{C}$be a$q$-ary$k$-dimensional full-length code with exactly one non-zero weight$d.$Then$\mathcal{C}$is a$\frac d{q^{k-1}}$times replicated simplex code. \end{proposition}% %TCIMACRO{\TeXButton{Proof}{\proof}}% %BeginExpansion \proof %EndExpansion By counting the non-zero entries in the list of all codewords, we see that $n=\frac{(q^{k}-1)d}{q^{k-1}(q-1)}.$ Consider the$\sigma_{+}$-dual transform$\Gamma$of$\gamma_{\mathcal{C}}.$Note that$\Delta=d.Hence $n_{\Gamma}=\frac{nq^{k-1}}d-\frac{q^{k}-1}{q-1}\frac dd=0,$ which implies that \begin{align*} \mu_{\Gamma}(p) & =-\frac{q^{k-1}d}d+\frac{q^{k-2}(q-1)n}d+\frac {q^{k-2}\gamma(p)}d=\\ & =-\frac1q+\frac{q^{k-2}\gamma(p)}d=0\text{ for all }p\in\Pi. \end{align*} So\gamma$is the constant function$\frac d{q^{k-1}}.\hfill$% %TCIMACRO{\TeXButton{End Proof}{\qed}}% %BeginExpansion \qed %EndExpansion \begin{proposition} \emph{(Tamari \cite{Tama84})} The generalized MacDonald codes are unique. \end{proposition}% %TCIMACRO{\TeXButton{Proof}{\proof}}% %BeginExpansion \proof %EndExpansion Let$\mathcal{C}$be a$q$-ary code with parameters $\lbrack t% %TCIMACRO{\QATOPD{[}{]}{k}{1}}% %BeginExpansion \genfrac{[}{]}{0pt}{}{k}{1}% %EndExpansion -% %TCIMACRO{\QATOPD{[}{]}{u}{1}}% %BeginExpansion \genfrac{[}{]}{0pt}{}{u}{1}% %EndExpansion ,\ k,\ tq^{k-1}-q^{u-1}],$ and let$\gamma:=\gamma_{\mathcal{C}}$be the corresponding multiset in$\Pi:=\mathbb{P}(\mathbb{F}_{q}^{n}/\mathcal{C}^{\perp}).$Consider the dual transform$\Gamma$of$\gamma$with respect to$\sigma:j\mapsto j-tq^{k-1}% +q^{u-1}.$Substitution of the parameters in (\ref{muGamma}) yields $\mu_{\Gamma}(p)=q^{k-2}(-t+1+\gamma(p)).$ Since$\mu_{\Gamma}$is nonnegative, the minimum multiplicity of$\gamma$must be at least$t-1.$In fact this minimum is equal to$t-1,$and$|\gamma ^{-1}(t-1)|\geq% %TCIMACRO{\QATOPD{[}{]}{u}{1}}% %BeginExpansion \genfrac{[}{]}{0pt}{}{u}{1}% %EndExpansion ,$because$t|\Pi|-n_{\gamma}=% %TCIMACRO{\QATOPD{[}{]}{u}{1}}% %BeginExpansion \genfrac{[}{]}{0pt}{}{u}{1}% %EndExpansion .$Consequently, the dimension$v-1$of the projective subspace$\mu_{\Gamma }^{-1}(0)=\gamma^{-1}(t-1)$of$\Pi$is not smaller than$u-1.$From Proposition \ref{Inverse}, we see that$\gamma$is a$(v,t-1)$-lifting of a multiset$\gamma^{\prime}.$By Subsection \ref{lifted}, the length of$\gamma^{\prime}$is equal to $q^{-v}(n_{\gamma}-(t-1)% %TCIMACRO{\QATOPD{[}{]}{v}{1}}% %BeginExpansion \genfrac{[}{]}{0pt}{}{v}{1}% %EndExpansion )=t% %TCIMACRO{\QATOPD{[}{]}{k-v}{1}}% %BeginExpansion \genfrac{[}{]}{0pt}{}{k-v}{1}% %EndExpansion +\frac{q^{u-v}-1}{q-1}.$ This is an integer if and only if$v\leq u$. Hence$u=v$. So$\gamma(p)\geq t$outside a$(u-1)$-dimensional subspace$L:=\gamma^{-1}(t-1)\subset\Pi.$But the existence of any point$p$with$\gamma(p)>t$would imply that $n_{\gamma}>t% %TCIMACRO{\QATOPD{[}{]}{k}{1}}% %BeginExpansion \genfrac{[}{]}{0pt}{}{k}{1}% %EndExpansion -% %TCIMACRO{\QATOPD{[}{]}{u}{1}}% %BeginExpansion \genfrac{[}{]}{0pt}{}{u}{1}% %EndExpansion .$ Hence $\gamma(p)=\left\{ \begin{array} [c]{lll}% t-1 & \text{if} & p\in L,\\ t & \text{if} & p\in\Pi\setminus L. \end{array} \right.$ \hfill\hfill% %TCIMACRO{\TeXButton{End Proof}{\qed}}% %BeginExpansion \qed %EndExpansion \section{$\sigma$--self-dual codes} Let$\mathcal{C}\subseteq\mathbb{F}_{q}^{S}$be a$k$-dimensional full-length code, and let$\sigma$be a function that takes integer values on the weight set of$\mathcal{C}.$\begin{definition} The code$\mathcal{C}$is said to be \emph{self-dual} with respect to$\sigma$if it is equivalent to its dual transform$\mathcal{C}^{\sigma}$. \end{definition} \begin{example} Let$\mathcal{C}$be the$[48,8,22]$-code$\mathcal{C}$discussed in Example \ref{48_8_22}. If we take$\sigma$to be the function with$\sigma(30):=1$and$\sigma(w):=0$for$w\in W_{\mathcal{C}}\setminus\{30\},$then$\mathcal{C}% ^{\sigma}$turns out to have the same parameters as$\mathcal{C}.$Hence the uniqueness of$\mathcal{C}$implies that it is self-dual with respect to$\sigma.$\end{example} \begin{example} It is known \cite{Dodu93a} that there are exactly two nonequivalent binary$[18,6,8]$-codes$\mathcal{C}_{1},\mathcal{C}_{2}$. Their weight distributions are $% \begin{tabular} [c]{ccccc}% & A_{8} & A_{12} & A_{16} & A_{2}(\mathcal{C}_{i}^{\perp}% )\\\cline{2-5}% \mathcal{C}_{1} & \multicolumn{1}{|c}{46} & \multicolumn{1}{|c}{16} & \multicolumn{1}{|c}{1} & \multicolumn{1}{|c|}{1}\\\cline{2-5}% \mathcal{C}_{2} & \multicolumn{1}{|c}{45} & \multicolumn{1}{|c}{18} & \multicolumn{1}{|c}{0} & \multicolumn{1}{|c|}{0}\\\cline{2-5}% \end{tabular}$ Both codes are easily seen to be self-dual with respect to$\sigma_{+}.$\end{example} \begin{example} The unique binary$[51,8,24]$-code has weight distribution$A_{24}=204$and$A_{32}=51$(cf. \cite{Jaff97}). This code is self-dual with respect to$\sigma_{+}.$\end{example} \begin{example} Let$G$be an incidence matrix of the finite projective plane$\mathfrak{P}% :=\mathbb{P}(\mathbb{F}_{p}^{3}),p$prime, and let$\mathcal{C}$be the$q$-ary code with generator matrix$G.$It is well known \cite{Sach79} that$\mathcal{C}$is a$[p^{2}+p+1,\frac12(p^{2}+p+2),p+1]$-code for which the words of minimum weight are the nonzero multiples of the rows of$G$. Let$\sigma$be the function with$\sigma(p+1):=1$and$\sigma(w):=0$for$w\in W_{\mathcal{C}}\setminus\{p+1\}$. The existence of correlations in$\mathfrak{P}$implies that the transpose$G^{t}$is a permutation of$G$. Hence$\mathcal{C}$is self-dual with respect to$\sigma$. \end{example} If the transform function$\sigma$has degree \emph{one}, it is easy to derive strong conditions on the parameters of self-dual codes with respect to$\sigma:$\begin{proposition} Let$\mathcal{C}$be$q$-ary$[n,k,d]$-code which is self-dual with respect to the function$\sigma:j\mapsto aj+b$. If$\mathcal{C}$is not a replicated simplex code, then \begin{equation} a=\pm q^{1-\frac k2},\ b=-\frac{q-1}{1+q^{k-1}a}n\text{.} \label{linselfdual}% \end{equation} \end{proposition}% %TCIMACRO{\TeXButton{Proof}{\proof}}% %BeginExpansion \proof %EndExpansion Let$(w_{1},w_{2},\ldots,w_{r})$be the ordered weight set of$\mathcal{C}$(and$\mathcal{C}^{\sigma}$), and let$(m_{1},m_{2},\ldots,m_{r})$be the ordered multiplicity set of$\gamma_{\mathcal{C}}$(and$\gamma_{\mathcal{C}% ^{\sigma}}$). Since$\mathcal{C}$is self-dual with respect to$\sigma,$the sizes of these sets are equal:$r=s.Moreover (\ref{M_Gamma}) and (\ref{muGamma}) imply that either \begin{align*} w_{i} & =q^{k-2}am_{i}+q^{-1}((q-1)n+b),\\ m_{i} & =aw_{i}+b \end{align*} or \begin{align*} w_{i} & =q^{k-2}am_{r-i}+q^{-1}((q-1)n+b),\\ m_{i} & =aw_{r-i}+b, \end{align*} fori=1,2,\ldots,r$. Eliminating$m_{i}$, we find that $w_{i}=q^{k-2}a^{2}w_{i}+q^{k-2}ab+q^{-1}((q-1)n+b).$ If$r>1,$then $q^{k-2}a^{2}=1\text{ and }q^{k-2}ab+q^{-1}((q-1)n+b)=0,$ which immediately gives (\ref{linselfdual}). If$r=1,$then$\mathcal{C}$is an$m_{1}$-fold replicated simplex code. This code is self-dual with respect to the constant function$\sigma=m_{1}$.\hfill% %TCIMACRO{\TeXButton{End Proof}{\qed}}% %BeginExpansion \qed %EndExpansion \begin{example} A. Brouwer \cite{Brou85} constructed a family of$q$-ary two-weight projective codes with parameters $n=(q^{e-1}-1)(q^{de-e}+q^{\frac{de}2-e})/(q-1),k=de,$ where$d$and$e$are arbitrary integers,$d$even and$e>1.$The weights are $w_{1}=(q^{e-1}-1)q^{de-e-1},w_{2}=w_{1}+q^{\frac{de}2-1}.$ These codes satisfy the conditions (\ref{linselfdual}) with respect to$\sigma_{-}.$It is not known if they are self-dual with respect to$\sigma_{-}.$\end{example} \begin{remark} Choose$q=2$,$d=2$in the above construction. Then the resulting code$\mathcal{C}_{1}(e)$has parameters $n=2^{2e-1}-2^{e-1},k=2e$ and $w_{1}=2^{2e-2}-2^{e-1},w_{2}=2^{2e-2}.$ The code$\mathcal{C}(e):=\left\langle \mathcal{C}_{1}(e),\mathbf{1}% \right\rangle ,$spanned by$\mathcal{C}_{1}(e)$and the all-one vector$\mathbf{1,}$is a projective self-complementary$[n,k+1,w_{1}]$-code with weight set$\{w_{1},w_{2},n\}.$It meets the Grey-Rankin bound. Since it is projective, the code $\mathcal{D}(e):=RM(1,2e)\backslash\mathcal{C}(e)$ (the column set of the first order Reed-Muller code with the columns of$\mathcal{C}(e)$deleted) has parameters $\lbrack2^{2e-1}+2^{e-1},2e+1],$ and the weight set $\{2^{2e-2},2^{2e-2}+2^{e-1},2^{2e-1}+2^{e-1}\}.$ It also meets the Grey-Rankin bound. For an alternative construction of codes with the above parameters see \cite{Jung91}. The partition $RM(1,2e)=(\mathcal{C}(e)\mid\mathcal{D}(e))$ shows that the number of nonequivalent projective self-complementary codes with parameters $\lbrack2^{2e-1}-2^{e-1},2e+1,2^{2e-2}-2^{e-1}]$ coincides with the number of nonequivalent projective self-complementary codes with parameters $\lbrack2^{2e-1}+2^{e-1},2e+1,2^{2e-2}].$ In particular, since there are exactly$4$non-equivalent projective self-comple-mentary$[28,7,12]$-codes (cf.\cite{Dodu94}, \cite{Tonc93}), it follows that there are exactly$4$nonequivalent projective self-complementary$[36,6,16]$-codes (cf.\cite{Tonc93}). \end{remark} \begin{remark} Tonchev showed in \cite{Tonc95} and \cite{Tonc96} that there are exactly$5$nonequivalent$[27,6,12]$two-weight codes, with weight$A_{12}=36$and$A_{16}=27$. All these codes satisfy the conditions (\ref{linselfdual}) with respect to$\sigma_{+}.$As a matter of fact, Boukliev and Kapralov managed to show that they are self-dual with respect to$\sigma_{+}.$In general, however, it is not clear whether the conditions (\ref{linselfdual}) imply self-duality in the case of transforms$\sigma$of degree 1. \end{remark} {\LARGE Acknowledgments} This work was completed during the visit of S. Dodunekov to the Faculty of Technical Mathematics and Informatics, Delft University of Technology. He would like to thank Dr. Juriaan Simonis and Dr. Jan van Zanten for their support and hospitality and Mrs. C.A. van Baar for her assistance. The paper was partially supported by the Bulgarian NSF grant MM502/95. \begin{thebibliography}{99} \bibitem{Boni84}Bonisoli, A. Every equidistant linear code is a sequence of dual Hamming codes. \emph{Ars Combin.} \textbf{18} (1984), 181--186. \bibitem{Bouk97c}Boukliev, I.; Dodunekov, S. M.; Helleseth, T.; Ytrehus, \O. On the$[162,8,80;2]$codes. \emph{IEEE Trans. Inform. Theory }\textbf{43} (1997), no. 6, 2055--2057. \bibitem{Brou85}Brouwer, A. E. Some new two-weight codes and strongly regular graphs. \emph{Discrete Appl. Math.} \textbf{10} (1985), no. 4, 455--461. \bibitem{Brou93a}Brouwer, A. E.; Verhoeff, T. An updated table of minimum-distance bounds for binary linear codes. \emph{IEEE Trans. Inform. Theory} \textbf{39} (1993), no. 2, 662--676. Online version: http://www.win.tue.nl/math/dw/voorlincod.html. \bibitem{Brou97}Brouwer, A. E.; van Eupen, M. The correspondence between projective codes and$2$-weight codes. \emph{Des. Codes Cryptogr.} \textbf{11} (1997), no. 3, 262--266. \bibitem{Cald86}Calderbank, A. R.; Kantor, W. M. The geometry of two-weight codes. \emph{Bull. London Math. Soc.} \textbf{18} (1986), 97--122. \bibitem{Cher97}Cherdieu, J. P.; Delcroix, A.; Mado, J. C.; Mercier, D. J. Weight distribution of the Hermition forms codes. \emph{Appl. Alg. Engrg. Comm. Comput.} \textbf{8} (1997), no. 4, 307--314. \bibitem{Dels73}Delsarte, P. An algebraic approach to the association schemes of coding theory. \emph{Philips Res. Rep. Suppl.} No. 10 (1973), vi+97 pp. \bibitem{Dodu85a}Dodunekov, S. M.; Manev, N. L. An improvement of the Griesmer bound for some small minimum distances. \emph{Discrete Appl. Math.} \textbf{12} (1985), no. 2, 103--114. \bibitem{Dodu93a}Dodunekov, S. M.; Encheva, S. B. Uniqueness of some linear subcodes of the binary extended Golay code. \emph{Problems Inform. Transmission} \textbf{29} (1993), no. 1, 38--43; \emph{translated from Problemy Peredachi Informatsii} \textbf{29} (1993), no. 1, 45--51 (Russian). \bibitem{Dodu94}Dodunekov, S. M.; Encheva, S. B.; Kapralov, S. N. On the$[28,7,12]$binary self-complementary codes and their residuals. \emph{Des. Codes Cryptogr.} \textbf{4} (1994), no. 1, 57--67. \bibitem{Gopp81}Goppa, V. D. Codes on algebraic curves. \emph{Soviet Math. Doklady} \textbf{24}, 170--172; \emph{translated from Dokl. Akad. Nauk SSSR} \textbf{259} (1981), no. 6, 1289--1290 (Russian). \bibitem{Hama78}Hamada, N.; Tamari, F. On a geometrical method of construction of maximal$t$-linearly independent sets. \emph{J. Combin. Theory Ser. A} \textbf{25} (1978), no. 1, 14--28. \bibitem{Hama93i}Hamada, N. A characterization of some$[n,k,d;q]$-codes meeting the Griesmer bound using a minihyper in a finite projective geometry. \emph{Discrete Math.} \textbf{116} (1993), no. 1-3, 229--268. \bibitem{Hill78a}Hill, R. Caps and codes. \emph{Discrete Math.} \textbf{22} (1978), no. 2, 111--137. \bibitem{Hill92a}Hill, R. Optimal linear codes. \emph{Cryptography and coding, II (Cirencester, 1989),} 75-104, Inst. Math. Appl. Conf. Ser. New Ser., 33, \emph{Oxford Univ. Press, New York,} 1992. \bibitem{Hirs97}Hirschfeld, J. W. P.; Storme, L. The packing problem in statistics, coding theory and finite projective spaces. To appear in \emph{J. Statist. Plann. Inference} .(\emph{Proceedings of the Bose Memorial conference, Colorado,} June 1995). \bibitem{Jaff97}Jaffe, D. B. Binary linear codes: new results on nonexistence. \emph{Draft version accessible through the author's web page: http://www.math.unl.edu/}$^{\thicksim}$\emph{djaffe/}, November 10,1997 (Version 0.5). Dept. of Math. and Statistics, University of Nebraska, Lincoln. \bibitem{Jaff98a}Jaffe, D. B.; Simonis, J. New binary linear codes which are dual transforms of good codes. submitted to \emph{IEEE Trans. Inform. Theory.} Online preprint available at http://www.math.unl.edu/$^{\thicksim}$djaffe/. \bibitem{Jung91}Jungnickel, D.; Tonchev, V. D. Exponential number of quasi-symmetric SDP designs and codes meeting the Grey-Rankin bound. \emph{Des. Codes Cryptogr.} \textbf{1} (1991), no. 3, 247--253. \bibitem{Kraw29}Krawtchouk, M. Sur une g\'{e}n\'{e}ralisation des polynomes d'Hermite. \emph{Comptes Rendus} \textbf{189} (1929), 620-622. \bibitem{Land97b}Landgev, I. N. Linear codes over finite fields and finite projective geometries. To appear in \emph{Discrete Math.}. \bibitem{Macw63}MacWilliams, F. J. A theorem on the distribution of weights in a systematic code. \emph{Bell System Tech. J.} \textbf{42} (1963), 79-94. \bibitem{Macw83}MacWilliams, F. J.; Sloane, N. J. A. The theory of error-correcting codes. 2nd reprint. North-Holland Mathematical Library, Vol. 16. \emph{North-Holland Publishing Co., Amsterdam - New York - Oxford,} 1983, xx+762 pp. ISBN: 0-444-85009-0 and 0-444-85010-4. \bibitem{Pete72}Peterson, W. W.; Weldon, E. J., Jr. Error-correcting codes. Second edition. \emph{The M.I.T. Press, Cambridge, Mass. - London,} 1972. xi+560 pp. \bibitem{Sach79}Sachar, H. The$\mathbb{F}_{p}$span of the incidence matrix of a finite projective plane. \emph{Geom. Dedicata} \textbf{8} (1979), 407--415. \bibitem{Slep56}Slepian, D. A class of binary signaling alphabets. \emph{Bell System Tech. J.} \textbf{35} (1956), 203--234. \bibitem{Tama84}Tamari, F. On linear codes which attain the Solomon-Stiffler bound. \emph{Discrete Math.} \textbf{49} (1984), no. 2, 179--191. \bibitem{Tonc93}Tonchev, V. D. Quasi-symmetric designs, codes, quadrics, and hyperplane sections. \emph{Geom. Dedicata} \textbf{48} (1993), no. 3, 295--308. \bibitem{Tonc95}Tonchev, V. D. The uniformly packed binary$[27,21,3]$and$[35,29,3]$codes. \emph{Proc. Int. Workshop on Optimal Codes and Related Topics, Sozopol, Bulgaria, May 26 - June 1,} 1995, 130-136. \bibitem{Tonc96}Tonchev, V. D. The uniformly packed binary$[27,21,3]$and$[35,29,3]\$ codes. \emph{Discrete Math.} \textbf{149} (1996), 283-288. \bibitem{Tsfa91}Tsfasman, M. A.; Vladut, S. G. Algebraic-geometric codes. Translated from the Russian by the authors. Mathematics and its Applications (Soviet Series), 58. \emph{Kluwer Academic Publishers Group, Dordrecht, }1991 xxiv+667 pp. ISBN: 0-7923-0727-5. \bibitem{Ward81}Ward, H. N. Divisible codes. \emph{Arch. Math.} (Basel) 36 (1981), no. 6, 485--494. \end{thebibliography} \end{document}