Non-Projective Two-Weight Codes

Abstract

It has been known since the 1970’s that the difference of the non-zero weights of a projective ${\mathbb{F}}_q$-linear two-weight code has to be a power of the characteristic of the underlying field. Here, we study non-projective two-weight codes and, e.g., show the same result under mild extra conditions. For small dimensions we give exhaustive enumerations of the feasible parameters in the binary case.

1. Introduction

It has been known since the 1970s that the two non-zero weights of a projective ${\mathbb{F}}_q$-linear two-weight code C can be written as $w_1=u{p}^t$ and $w_2=(u+1)p^t$, where $u\in {\mathbb{N}}_{\ge 1}$ and p is the characteristic of the underlying finite field ${\mathbb{F}}_q$; see Corollary 2 [1]. So, especially the weight difference $w_2-w_1$ is a power of the characteristic p. Here, we want to consider ${\mathbb{F}}_q$-linear two-weight codes C with non-zero weights $w_1<w_2$ which are not necessarily projective. In [2], it was observed that if $w_2-w_1$ is not a power of the characteristic p, then the code C has to be non-projective, which settles a question in [3]. Here, we prove the stronger statement that C is repetitive, i.e., C is the l-fold repetition of a smaller two-weight code $C^{\prime }$, where l is the largest factor of $w_2-w_1$ that is coprime to the field size q, if C does not have full support, cf. [4]. Moreover, if a two-weight code C is non-repetitive and does not have full support, then its two non-zero weights can be written as $w_1=u{p}^t$ and $w_2=(u+1)p^t$, where again p is the characteristic of the underlying finite field ${\mathbb{F}}_q$; see Theorem 3.

Constructions for projective two-weight codes can be found in the classical survey paper [5]. Many research papers considered these objects since they, e.g., yield strongly regular graphs (srgs), and we refer the reader to [6] for a corresponding monograph on srgs. For a few more recent papers on constructions for projective two-weight codes, we refer, e.g., to [7,8,9,10]. In, e.g., [9], the author uses geometric language and speaks of constructions for two-character sets, i.e., sets of points in a projective space $PG(k-1,q)$ with just two different hyperplane multiplicities; call them s and t. In general, each (full-length) linear code is in one-to-one correspondence to a (spanning) multiset of points in some projective space $PG(k-1,q)$. Here, we will also mainly use the geometric language and consider a few general constructions for two-character multisets of points corresponding to two-weight codes (possibly non-projective). For each subset $\overline{\mathcal{H}}$ of hyperplanes in $PG(k-1,q)$ we construct a multiset of points $\mathcal{M}\left(\overline{\mathcal{H}}\right)$ such that all hyperplanes $H\in \overline{\mathcal{H}}$ have the same multiplicity, say s, and also all other hyperplanes $H\notin \overline{\mathcal{H}}$ have the same multiplicity, say t. Actually, we characterize the full set of such multisets with at most two different hyperplane multiplicities given $\overline{\mathcal{H}}$; see Theorems 1 and 2. Using this correspondence we have classified all two-weight codes up to symmetry for small parameters. For projective two-weight codes such enumerations can be found in [11].

Brouwer and van Eupen give a correspondence between arbitrary projective codes and arbitrary two-weight codes via the so-called BvE dual transform. The correspondence can be said to be 1–1, even though there are choices for the involved parameters to be made in both directions. In [12], the dual transform was, e.g., applied to the unique projective ${[16,5,9]}_3$-code. For parameters $\alpha =\frac{1}{3}$ and $\beta =-3$ the result is a ${[69,5,45]}_3$ two-weight code, and for $\alpha =-\frac{1}{3}$ and $\beta =5$ the result is a ${[173,5,108]}_3$ two-weight code. This resembles the fact that we have some freedom when constructing a two-weight code from a given projective code, e.g., we can take complements or add simplex codes of the same dimension. Our obtained results may be rephrased in the language of the BvE dual transform by restricting to a canonical choice of the involved parameters. For further literature on the dual transform, see, e.g., [12,13,14,15]. For a variant that is rather close to our presentation we refer the reader to [16].

With respect to further related studies in the literature we remark that a special subclass of (non-projective) two-weight codes was completely characterized in [17]. A conjecture by Vega [18] states that all two-weight cyclic codes are the “known” ones, cf. [19]. Another stream of the literature considers the problem of whether all projective two-weight codes that have the parameters of partial k-spreads indeed have to be partial k-spreads. Those results can be found in papers considering extendability results for partial k-spreads or classifying minihypers; see, e.g., [20]. Two-weight codes have also been considered over rings instead of finite fields; see, e.g., [21].

The remaining part of this paper is structured as follows. In Section 2, we introduce the necessary preliminaries for linear two-weight codes and their geometric counterpart called two-character multisets in projective spaces. In general, multisets of points, corresponding to general linear codes, can be described via so-called characteristic functions and we collect some of their properties in Section 3. Examples and constructions for two-character multisets are given in Section 4. In Section 5, we present our main results. We close with enumeration of the results for two-character multisets in $PG(k-1,q)$ for small parameters in Section 6. We will mainly use geometric language and arguments. For the ease of the reader we only use elementary arguments and give (almost) all details.

2. Preliminaries

An ${[n,k]}_q$-code C is a k-dimensional subspace of ${\mathbb{F}}_q^n$, i.e., C is assumed to be ${\mathbb{F}}_q$-linear. Here, n is called the length and k is called the dimension of C. Elements $c\in C$ are called codewords and the weight $wt\left(c\right)$ of a codeword is given by the number of non-zero coordinates. Clearly, the all-zero vector $\mathbf{0}$ has weight zero and all other codewords have a positive integer weight. A two-weight code is a linear code with exactly two non-zero weights. A generator matrix for C is a $k\times n$ matrix G such that its rows span C. We say that C is of full length if for each index $1\le i\le n$ there exists a codeword $c\in C$ whose ith coordinate $c_i$ is non-zero, i.e., all columns of a generator matrix of C are non-zero. The dual code $C^{\perp }$ of C is the $(n-k$)-dimensional code consisting of the vectors orthogonal to all codewords of C with respect to the inner product $\langle u,v\rangle ={\sum }_{i=1}^n{u}_i{v}_i$.

Now, let C be a full-length ${[n,k]}_q$-code with generator matrix G. Each column g of G is an element of ${\mathbb{F}}_q^k$ and since $g\ne \mathbf{0}$ we can consider $\langle g\rangle$ as a point in the projective space $PG(k-1,q)$. Using the geometric language we call 1-, 2-, 3-, and $(k-1)$-dimensional subspaces of ${\mathbb{F}}_q^k$ points, lines, planes, and hyperplanes in $PG(k-1,q)$. Instead of an l-dimensional space we also speak of an l-space. By $\mathcal{P}$ we denote the set of points and by $\mathcal{H}$ we denote the set of hyperplanes of $PG(k-1,q)$ whenever k and q are clear from the context. A multiset of points in $PG(k-1,q)$ is a mapping $\mathcal{M}:\mathcal{P}\to \mathbb{N}$, i.e., to each point $P\in \mathcal{P}$ we assign its multiplicity $\mathcal{M}\left(P\right)\in \mathbb{N}$. By $\#\mathcal{M}={\sum }_{P\in \mathcal{P}}\mathcal{M}\left(P\right)$ we denote the cardinality of $\mathcal{M}$. The support $supp\left(\mathcal{M}\right)$ is the set of all points with non-zero multiplicity. We say that $\mathcal{M}$ is spanning if the set of points in the support of $\mathcal{M}$ span $PG(k-1,q)$. Clearly permuting columns of a generator matrix G or multiplying some columns with non-zero elements in ${\mathbb{F}}_q^{★}:={\mathbb{F}}_q\backslash \left\{0\right\}$ yields an equivalent code. In addition to that we obtain a one-to-one correspondence between full-length ${[n,k]}_q$-codes and spanning multisets of points $\mathcal{M}$ in $PG(k-1,q)$ with cardinality $\#\mathcal{M}=n$. Moreover, two linear ${[n,k]}_q$-codes C and $C^{\prime }$ are equivalent if their corresponding multisets of points $\mathcal{M}$ and ${\mathcal{M}}^{\prime }$ are. For details we refer, e.g., to [22]. A linear code C is projective if its corresponding multiset of points satisfies $\mathcal{M}\left(P\right)\in \{0,1\}$ for all $P\in \mathcal{P}$. We also speak of a set of points in this case. The multisets of points with $\mathcal{M}\left(P\right)=0$ for all $P\in \mathcal{P}$ are called trivial.

Geometrically, for a non-zero codeword $c\in C$ the set $c·{\mathbb{F}}_q^{★}$ corresponds to a hyperplane $H\in \mathcal{H}$ and $wt\left(c\right)=\#\mathcal{M}-\mathcal{M}\left(H\right)$, where we extend the function $\mathcal{M}$ additively, i.e., $\mathcal{M}\left(S\right):={\sum }_{P\in S}\mathcal{M}\left(P\right)$ for every subset $S\subseteq \mathcal{P}$ of points. We call $\mathcal{M}\left(H\right)$ the multiplicity of hyperplane $H\in \mathcal{H}$ and have $\mathcal{M}\left(V\right)=\#\mathcal{M}$ for the entire ambient space $V:=\mathcal{P}$. The number of hyperplanes $\#\mathcal{H}$, as well as the number of points $\#\mathcal{P}$, in $PG(k-1,q)$ is given by ${\left[k\right]}_q:=\frac{q^k-1}{q-1}$. A two-character multiset is a multiset of points $\mathcal{M}$ such that exactly two different hyperplane multiplicities $\mathcal{M}\left(H\right)$ occur. i.e., a multiset of points $\mathcal{M}$ is a two-character multiset if its corresponding code C is a two-weight code. If $\mathcal{M}$ actually is a set of points, i.e., if we have $\mathcal{M}\left(P\right)\in \{0,1\}$ for all points $P\in \mathcal{P}$, then we speak of a two-character set. We say that an ${[n,k]}_q$-code C is $\Delta$-divisible if the weights of all codewords are divisible by $\Delta$. A multiset of points $\mathcal{M}$ is called $\Delta$-divisible if the corresponding linear code is. More directly, a multiset of points $\mathcal{M}$ is $\Delta$-divisible if we have $\mathcal{M}\left(H\right)\equiv \#\mathcal{M}(mod\Delta )$ for all $H\in \mathcal{H}$.

A one-weight code is an ${[n,k]}_q$-code C such that all non-zero codewords have the same weight w. One-weight codes have been completely classified in [23] and are given by repetitions of so-called simplex codes. Geometrically, the multiset of points $\mathcal{M}$ in $PG(k-1,q)$ corresponding to a one-weight code C satisfies $\mathcal{M}\left(P\right)=l$ for all $P\in \mathcal{P}$, i.e., we have $\#\mathcal{M}=n={\left[k\right]}_q·l$, $\mathcal{M}\left(H\right)={[k-1]}_q·l$ for all $H\in \mathcal{H}$, and $w=\#\mathcal{M}-\mathcal{M}\left(H\right)=q^{k-1}·l$. We say that a linear ${[n,k]}_q$-code C is repetitive if it is the l-fold repetition of an ${[n/l,k]}_q$-code $C^{\prime }$, where $l>1$, and non-repetitive otherwise. A given multiset of points $\mathcal{M}$ is called repeated if its corresponding code is. More directly, a non-trivial multiset of points $\mathcal{M}$ is repeated if the greatest common divisor of all point multiplicities is larger than one. We say that a multiset of points $\mathcal{M}$ or its corresponding linear code C has full support if $supp\left(\mathcal{M}\right)=\mathcal{P}$, i.e., if $\mathcal{M}\left(P\right)>0$ for all $P\in \mathcal{P}$. So, for each non-repetitive one-weight code C with length n, dimension k, and non-zero weight w we have $n={\left[k\right]}_q$ and $w=q^{k-1}$. Each non-trivial one-weight code, i.e., one with dimension at least 1, has full support. The aim of this paper is to characterize the possible parameters of non-repetitive two-weight codes (with or without full support). For the correspondence between ${[n,k]}_q$-codes and multisets of points $\mathcal{M}$ in $PG(k-1,q)$ we have assumed that $\mathcal{M}$ is spanning. If $\mathcal{M}$ is not spanning, then there exists a hyperplane containing the entire support, so that $\mathcal{M}$ is two-character multiset if $\mathcal{M}$ induces a one-character multiset in the span of $supp\left(\mathcal{M}\right)$, cf. Proposition 1. The structure of the set of all two-character multisets where the larger hyperplane multiplicity is attained for a prescribed subset of the hyperplanes is considered in Section 5.

3. Characteristic Functions

Fixing the field size q and the dimension k of the ambient space, a multiset of points in $PG(k-1,q)$ is a mapping $\mathcal{M}:\mathcal{P}\to \mathbb{N}$. By $\mathcal{F}$ we denote the $\mathbb{Q}$-vector space consisting of all functions $F:\mathcal{P}\to \mathbb{Q}$, where addition and scalar multiplication is defined pointwise. i.e., $(F_1+F_2)\left(P\right):=F_1\left(P\right)+F_2\left(P\right)$ and $(x·F_1)\left(P\right):=x·F_1\left(P\right)$ for all $P\in \mathcal{P}$, where $F_1,F_2\in \mathcal{F}$, and $x\in \mathbb{Q}$ are arbitrary. For each non-empty subset $S\subseteq \mathcal{P}$ the characteristic function ${\chi }_S$ is defined by ${\chi }_S\left(P\right)=1$ if $P\in S$ and ${\chi }_S\left(P\right)$ otherwise. Clearly the set of functions ${\chi }_P$ for all $P\in \mathcal{P}$ forms a basis of $\mathcal{F}$ for ambient space $PG(k-1,q)$ for all $k\ge 1$. Note that there are no hyperplanes if $k=1$ and hyperplanes coincide with points for $k=2$. We also extend the functions $F\in \mathcal{F}$ additively, i.e., we set $F\left(S\right)={\sum }_{P\in S}F\left(P\right)$ for all $S\subseteq \mathcal{P}$. Our next aim is to show the well-known fact that also the set of functions ${\chi }_H$ for all hyperplanes $H\in \mathcal{H}$ forms a basis of $\mathcal{F}$ for ambient space $PG(k-1,q)$ for all $k\ge 2$. In other words, also $\mathcal{M}\left(P\right)$ can be reconstructed from the $\mathcal{M}\left(H\right)$:

Lemma 1. 

Let $\mathcal{M}\in \mathcal{F}$ for ambient space $PG(k-1,q)$, where $k\ge 2$. Then, we have

$$\mathcal{M}\left(P\right)=\sum _{H\in \mathcal{H}:P\in H}\frac{1}{{[k-1]}_q}·\mathcal{M}\left(H\right)+\sum _{H\in \mathcal{H}:P\notin H}\frac{1}{q^{k-1}}·\left(\frac{1}{{[k-1]}_q}-1\right)·\mathcal{M}\left(H\right)$$

(1)

for all points $P\in \mathcal{P}$.

Proof. 

Without loss of generality we assume $k\ge 3$. Since each point $P^{\prime }\in \mathcal{P}$ is contained in ${[k-1]}_q$ of the $\#\mathcal{H}={\left[k\right]}_q$ hyperplanes and each point $P^{\prime }\ne P$ is contained in ${[k-2]}_q$ of the ${[k-1]}_q$ hyperplanes that contain P, we have

$$\sum _{H\in \mathcal{H}:P\in H}\mathcal{M}\left(H\right)={[k-2]}_q·\left|\mathcal{M}\right|+\left({[k-1]}_q-{[k-2]}_q\right)\mathcal{M}\left(P\right)={[k-2]}_q·\left|\mathcal{M}\right|+q^{k-2}\mathcal{M}\left(P\right)$$

so that

$$\sum _{H\in \mathcal{H}:P\in H}\mathcal{M}\left(H\right)-\frac{{[k-2]}_q}{{[k-1]}_q}·\sum _{H\in \mathcal{H}}\mathcal{M}\left(H\right)=q^{k-2}\mathcal{M}\left(P\right)$$

using ${[k-1]}_q·\#\mathcal{M}={\sum }_{H\in \mathcal{H}}\mathcal{M}\left(H\right)$. Thus, we can conclude the stated formula using

$$\frac{1}{q^{k-2}}·\left(1-\frac{{[k-2]}_q}{{[k-1]}_q}\right)=\frac{1}{q^{k-2}}·\frac{{[k-1]}_q-{[k-2]}_q}{{[k-1]}_q}=\frac{1}{{[k-1]}_q}$$

and

$$-\frac{{[k-2]}_q}{{[k-1]}_q·q^{k-2}}=\frac{1-{[k-1]}_q}{{[k-1]}_q·q^{k-1}}=\frac{1}{q^{k-1}}·\left(\frac{1}{{[k-1]}_q}-1\right).$$

□

As an example we state that in $PG(3-1,2)$ we have

$$\mathcal{M}\left(P\right)=\frac{1}{3}·\sum _{H\in \mathcal{H}:P\in H}\mathcal{M}\left(H\right)-\frac{1}{6}·\sum _{H\in \mathcal{H}:P\notin H}\mathcal{M}\left(H\right).$$

Lemma 2. 

Let $\mathcal{M}\in \mathcal{F}$ for ambient space $PG(k-1,q)$, where $k\ge 2$. Then, there exist ${\alpha }_H\in \mathbb{Q}$ for all hyperplanes $H\in \mathcal{H}$ such that

$$\mathcal{M}=\sum _{H\in \mathcal{H}}{\alpha }_H·{\chi }_H.$$

(2)

Moreover, the coefficients ${\alpha }_H$ are uniquely determined by $\mathcal{M}$.

Proof. 

Each point $P\in \mathcal{P}$ is contained in ${[k-1]}_q$ hyperplanes and for each point $Q\ne P$ there are exactly ${[k-2]}_q$ hyperplanes that contain both P and Q, so that

$$\sum _{H\in \mathcal{H}:P\in H}{\chi }_H-\frac{{[k-2]}_q}{{[k-1]}_q}·\sum _{H\in \mathcal{H}}{\chi }_H=q^{k-2}·{\chi }_P.$$

Using

$$\mathcal{M}=\sum _{P\in \mathcal{P}}\mathcal{M}\left(P\right)·{\chi }_P$$

we conclude the existence of the ${\alpha }_H\in \mathbb{Q}$. Since the functions ${\left({\chi }_P\right)}_{P\in \mathcal{P}}$ form a basis of the $\mathbb{Q}$-vector space $\mathcal{F}$, which is also generated by the functions ${\left({\chi }_H\right)}_{H\in \mathcal{H}}$, counting $\#\mathcal{P}={\left[k\right]}_q=\#\mathcal{H}$ yields that also ${\left({\chi }_H\right)}_{H\in \mathcal{H}}$ forms a basis and the coefficients ${\alpha }_H$ are uniquely determined by $\mathcal{M}$. □

If $\mathcal{M}\in \mathcal{F}$ is given by the representation

$$\mathcal{M}=\sum _{P\in \mathcal{P}}{\alpha }_P·{\chi }_P$$

with ${\alpha }_P\in \mathbb{Q}$ we can easily decide whether $\mathcal{M}$ is a multiset of points. The necessary and sufficient conditions are given by ${\alpha }_P\in \mathbb{N}$ for all $P\in \mathcal{P}$ (including the case of a trivial multiset of points). If a multiset of points is characterized by coefficients ${\alpha }_H$ for all hyperplanes $H\in \mathcal{H}$, as in Lemma 2, then some ${\alpha }_H$ may be fractional or negative. For two-character multisets we will construct a different unique representation, involving the characteristic functions ${\chi }_H$ of hyperplanes; see Theorem 1.

Let us state a few observations about operations for multisets of points that yield multisets of points again.

Lemma 3. 

For two multisets of points ${\mathcal{M}}_1$ and ${\mathcal{M}}_2$ of $PG(k-1,q)$ and each non-negative integer $n\in \mathbb{N}$ the functions ${\mathcal{M}}_1+{\mathcal{M}}_2$ and $n·{\mathcal{M}}_1$ are multisets of points of $PG(k-1,q)$.

In order to say something about the subtraction of multisets of points we denote the minimum point multiplicity of a multiset of points $\mathcal{M}$ by $\mu \left(\mathcal{M}\right)$ and the maximum point multiplicity by $\gamma \left(\mathcal{M}\right)$. Whenever $\mathcal{M}$ is clear from the context we also just write $\mu$ and $\gamma$ instead of $\mu \left(\mathcal{M}\right)$ and $\mu \left(\gamma \right)$.

Lemma 4. 

Let ${\mathcal{M}}_1$ and ${\mathcal{M}}_2$ be two multisets of points of $PG(k-1,q)$. If $\mu \left({\mathcal{M}}_1\right)\ge \gamma \left({\mathcal{M}}_2\right)$, then ${\mathcal{M}}_1-{\mathcal{M}}_2$ is a multiset of points of $PG(k-1,q)$.

Definition 1. 

Let $\mathcal{M}$ be a multiset of points in $PG(k-1,q)$. If l is an integer with $l\ge \gamma \left(\mathcal{M}\right)$, then the l-complement ${\mathcal{M}}^{l-C}$ of $\mathcal{M}$ is defined by ${\mathcal{M}}^{l-C}\left(P\right):=l-\mathcal{M}\left(P\right)$ for all points $P\in \mathcal{P}$.

One can easily check that ${\mathcal{M}}^{l-C}$ is a multiset of points with cardinality $l·{\left[k\right]}_q-\#\mathcal{M}$, maximum point multiplicity $\gamma \left({\mathcal{M}}^{l-C}\right)=l-\mu \left(\mathcal{M}\right)$, and minimum point multiplicity $\mu \left({\mathcal{M}}^{l-C}\right)=l-\gamma \left(\mathcal{M}\right)$. Using characteristic functions we can write ${\mathcal{M}}^{l-C}=l·{\chi }_V-\mathcal{M}$, where $V=\mathcal{P}$ denotes the set of all points of the ambient space.

Given an arbitrary function $\mathcal{M}\in \mathcal{F}$ there always exist $\alpha \in \mathbb{Q}\backslash \left\{0\right\}$ and $\beta \in \mathbb{Z}$ such that $\alpha ·\mathcal{M}+\beta ·{\chi }_V$ is a multiset of points.

4. Examples and Constructions for Two-Character Multisets

The aim of this section is to list a few easy constructions for two-character multisets of points $\mathcal{M}$ in $PG(k-1,q)$. We will always abbreviate $n=\#\mathcal{M}$ and denote the two occurring hyperplane multiplicities by s and t, where we assume $s>t$ by convention.

Proposition 1. 

For integers $1\le l<k$, let L be an arbitrary l-space in $PG(k-1,q)$. Then, ${\chi }_L$ is a two-character set with $n={\left[l\right]}_q$, $\gamma =1$, $\mu =0$, $s={\left[l\right]}_q$, and $t={[l-1]}_q$.

Note that for the case $l=k$ we have the one-character set ${\chi }_V$, which can be combined with any two-character multiset.

Lemma 5. 

Let $\mathcal{M}$ be a two-character multiset of points in $PG(k-1,q)$. Then, for each integer $0\le a\le \mu \left(\mathcal{M}\right)$, each $b\in N$, and each integer $c\ge \gamma \left(\mathcal{M}\right)$ the functions $\mathcal{M}-a·{\chi }_V$, $\mathcal{M}+b·{\chi }_V$, $b·\mathcal{M}$, and $c·{\chi }_V-\mathcal{M}$ are two-character multisets of points.

For the first and the fourth construction we also spell out the implications for the parameters of a given two-character multiset:

Lemma 6. 

Let $\mathcal{M}$ be a multiset of points in $PG(k-1,q)$ such that $\mathcal{M}\left(H\right)\in \{s,t\}$ for every hyperplane $H\in \mathcal{H}$. If $\mathcal{M}\left(P\right)\ge l$ for every point $P\in \mathcal{P}$, i.e., $l\le \mu \left(\mathcal{M}\right)$, then ${\mathcal{M}}^{\prime }:=\mathcal{M}-l·{\chi }_V$ is a multiset of points in $PG(k-1,q)$ such that ${\mathcal{M}}^{\prime }\left(H\right)\in \{s-{[k-1]}_q·l,t-{[k-1]}_q·l\}$ for every hyperplane $H\in \mathcal{H}$.

Lemma 7. 

Let $\mathcal{M}$ be a multiset of points in $PG(k-1,q)$ such that $\mathcal{M}\left(H\right)\in \{s,t\}$ for every hyperplane $H\in \mathcal{H}$. If $\mathcal{M}\left(P\right)\le u$, i.e., $\le \gamma \left(\mathcal{M}\right)$ for every point $P\in \mathcal{P}$, then the u-complement ${\mathcal{M}}^{\prime }:=u·{\chi }_V-\mathcal{M}$ of $\mathcal{M}$ is a multiset of points in $PG(k-1,q)$ such that ${\mathcal{M}}^{\prime }\left(H\right)\in \left\{u[k-1]-s,u[k-1]-t\right\}$ for every hyperplane $H\in \mathcal{H}$.

We can also use two (almost) arbitrary subspaces to construct two-character multisets:

Proposition 2. 

Let $a\ge b\ge 1$ and $0\le i\le b-1$ be arbitrary integers, A be an a-space, and B be a b-space with $dim(A\cap B)=i$ in $PG(k-1,q)$, where $k=a+b-i$. Then, $\mathcal{M}={\chi }_A+q^{a-b}·{\chi }_B$ satisfies $\mathcal{M}\left(H\right)\in \{s,t\}$ for all $H\in \mathcal{H}$, where $s={[a-1]}_q+q^{a-b}·{[b-1]}_q$ and $t=s+q^{a-1}$. If $i=0$, then $\gamma =q^{a-b}$, and $\gamma =q^{a-b}+1$ otherwise. In general, we have $n={\left[a\right]}_q+q^{a-b}·{\left[b\right]}_q$ and $\mu =0$.

Proof. 

For each $H\in \mathcal{H}$ we have $\mathcal{M}(H\cap A)\in \left\{{[a-1]}_q,{\left[a\right]}_q\right\}$ and $\mathcal{M}(H\cap B)\in \left\{{[b-1]}_q,{\left[b\right]}_q\right\}$. Noting that we cannot have both $\mathcal{M}(H\cap A)={\left[a\right]}_q$ and $\mathcal{M}(H\cap B)={\left[b\right]}_q$, we conclude $\mathcal{M}\left(H\right)\in \left\{{[a-1]}_q+q^{a-b}·{[b-1]}_q,{\left[a\right]}_q+q^{a-b}·{[b-1]}_q,{[a-1]}_q+q^{a-b}·{\left[b\right]}_q\right\}=\{s,t\}$. □

A partial k-spread is a set of k-spaces in $PG(v-1,q)$ with pairwise trivial intersection.

Proposition 3. 

Let ${\mathcal{S}}_1,...,{\mathcal{S}}_r$ be a partial parallelism of $PG(2k-1,q)$, i.e., the ${\mathcal{S}}_i$ are partial k-spreads that are pairwise disjoint. Then,

$$\mathcal{M}=\sum _{i=1}^r\sum _{S\in {\mathcal{S}}_i}{\chi }_S$$

is a two-character multiset of $PG(2k-1,q)$ with $n=r·{\left[k\right]}_q$ and hyperplane multiplicities $s=r·{[k-1]}_q$, $t=r·{[k-1]}_q+q^{k-1}$, where $r={\sum }_{i=1}^r\left|{\mathcal{S}}_i\right|$.

Cf. example SU2 in [5]. Field changes work similarly to those explained in Section 6 [5] for two-character sets.

Based on hyperplanes we can construct large families of two-character multisets:

Lemma 8. 

Let $\varnothing \ne {\mathcal{H}}^{\prime }⊊\mathcal{H}$ be a subset of the hyperplanes of $PG(k-1,q)$, where $k\ge 3$, then

$$\mathcal{M}=\sum _{H\in {\mathcal{H}}^{\prime }}{\chi }_H$$

(3)

is a two-character multiset with $n=r{[k-1]}_q$, $s=r{[k-2]}_q+q^{k-2}$, and $t=r{[k-2]}_q$, where $r=\#{\mathcal{H}}^{\prime }$.

By allowing ${\mathcal{H}}^{\prime }$ to be a multiset of hyperplanes we end up with $(\tau +1)$-character sets, where $\tau$ is the maximum number of occurrences of a hyperplane in ${\mathcal{H}}^{\prime }$.

Applying Lemma 6 yields:

Lemma 9. 

Let $\varnothing \ne {\mathcal{H}}^{\prime }⊊\mathcal{H}$ be a subset of the hyperplanes of $PG(k-1,q)$, where $k\ge 3$. If each point $P\in \mathcal{P}$ is contained in at least $\mu \in N$ elements of ${\mathcal{H}}^{\prime }$, then

$$\mathcal{M}=\sum _{H\in {\mathcal{H}}^{\prime }}{\chi }_H-\mu ·{\chi }_V$$

(4)

is a two-character multiset with $n=r{[k-1]}_q-\mu {\left[k\right]}_q$, $s=r{[k-2]}_q+q^{k-2}-\mu {[k-1]}_q$ and $t=r{[k-2]}_q-\mu {[k-1]}_q$, where $r=|{\mathcal{H}}^{\prime }|$.

In some cases we obtain two-character multisets where all point multiplicities have a common factor $g>1$. Here, we can apply the following general construction:

Lemma 10. 

Let $\mathcal{M}$ be a multiset of points in $PG(k-1,q)$ such that $\mathcal{M}\left(H\right)\in \{s,t\}$ for every hyperplane $H\in \mathcal{H}$. If $\mathcal{M}\left(P\right)\equiv 0(modg)$ for every point $P\in \mathcal{P}$, then ${\mathcal{M}}^{\prime }:=\frac{1}{g}·\mathcal{M}$ is a multiset of points in $PG(k-1,q)$ such that ${\mathcal{M}}^{\prime }\left(H\right)\in \left\{\frac{1}{g}·s,\frac{1}{g}·t\right\}$ for every hyperplane $H\in \mathcal{H}$. Moreover, we have $\#{\mathcal{M}}^{\prime }=\frac{1}{g}·\#\mathcal{M}$, $\mu \left({\mathcal{M}}^{\prime }\right)=\frac{1}{g}·\mu \left(\mathcal{M}\right)$, and $\gamma \left({\mathcal{M}}^{\prime }\right)=\frac{1}{g}·\gamma \left(\mathcal{M}\right)$.

Interestingly enough, it will turn out that we can construct all two-character multisets by combining Lemma 8 with Lemmas 5 and 10; see Theorems 1 and 2.

5. Geometric Duals and Sets of Feasible Parameters for Two-Character Multisets

To each two-character multiset $\mathcal{M}$ in $PG(k-1,q)$, i.e., $\left\{\mathcal{M}\left(H\right):H\in \mathcal{H}\right\}=\{s,t\}$ for some $s,t\in \mathbb{N}$, we can assign a set of points $\overline{\mathcal{M}}$ by using the geometric dual, i.e., interchanging hyperplanes and points. More precisely, fix a non-degenerated billinear form ⊥ and consider pairs of points and hyperplanes $(P,H)$ that are perpendicular with respect to ⊥ (different choices of ⊥ lead to isomorphic configurations). We write $H=P^{\perp }$ for the geometric dual of a point. We define $\overline{\mathcal{M}}$ via $\overline{\mathcal{M}}\left(P\right)=1$ if $\mathcal{M}\left(H\right)=s$, where $H=P^{\perp }$, and $\overline{\mathcal{M}}\left(P\right)=0$ otherwise, i.e., if $\mathcal{M}\left(H\right)=t$ (a generalization of the notion of the geometric dual has been introduced by Brouwer and van Eupen [12] for linear codes and formulated for multisets of points by Dodunekov and Simonis [22]). Of course we have some freedom in how we order s and t. So, we may also write $\overline{\mathcal{M}}\left(P\right)=\left(\mathcal{M}\left(H\right)-t\right)/(s-t)\in \{0,1\}$ for all $P\in \mathcal{P}$, where $H=P^{\perp }$. Noting the asymmetry in s and t we may also interchange the role of s and t or replace $\overline{\mathcal{M}}$ by its complement. Note that in principle several multisets of points with two hyperplane multiplicities can have the same corresponding point set $\overline{\mathcal{M}}$.

For the other direction we can start with an arbitrary set of points $\overline{\mathcal{M}}$, i.e., $\overline{\mathcal{M}}\left(P\right)\in \{0,1\}$ for all $P\in \mathcal{P}$. The multiset of points with two hyperplane multiplicities $\mathcal{M}$ is then defined via $\mathcal{M}\left(H\right)=s$ if $\overline{\mathcal{M}}\left(P\right)=1$, where $H=P^{\perp }$, and $\mathcal{M}\left(H\right)=t$ if $\overline{\mathcal{M}}\left(P\right)=0$. i.e., we may set

$$\mathcal{M}\left(H\right)=t+(s-t)·\overline{\mathcal{M}}\left(H^{\perp }\right).$$

(5)

While we have $\mathcal{M}\left(H\right)\in \mathbb{N}$ for all $s,t\in \mathbb{N}$, the point multiplicities $\mathcal{M}\left(P\right)$ induced by the hyperplane multiplicities $\mathcal{M}\left(H\right)$ (see Lemma 1) are not integral or non-negative in general. For suitable choices of s and t they are, while for others they are not.

Definition 2. 

Let $\overline{\mathcal{M}}$ be a set of points in $PG(k-1,q)$. By $\mathbb{L}\left(\overline{\mathcal{M}}\right)\subseteq {\mathbb{N}}^2$ we denote the set of all pairs $(s,t)\in {\mathbb{N}}^2$ with $s\ge t$ such that a multiset of points $\mathcal{M}$ in $PG(k-1,q)$ exists with $\mathcal{M}\left(H\right)=s$ if $\overline{\mathcal{M}}\left(H^{\perp }\right)=1$ and $\mathcal{M}\left(H\right)=t$ if $\overline{\mathcal{M}}\left(H^{\perp }\right)=0$ for all hyperplanes $H\in \mathcal{H}$.

Directly from Lemma 5 we can conclude:

Lemma 11. 

Let $\overline{\mathcal{M}}$ be a set of points in $PG(k-1,q)$. If $(s,t)\in \mathbb{L}\left(\overline{\mathcal{M}}\right)$, then we have

$${\langle (s,t)\rangle }_{\mathbb{N}}+{〈\left({[k-1]}_q,{[k-1]}_q\right)〉}_{\mathbb{N}}=\left\{\left(us+v{[k-1]}_q,ut+v{[k-1]}_q\right):u,v\in \mathbb{N}\right\}\subseteq \mathbb{L}\left(\overline{\mathcal{M}}\right).$$

(6)

Before we study the general structure of $\mathbb{L}\left(\overline{\mathcal{M}}\right)$ and show that it can be generated by a single element $\left(s_0,t_0\right)$ in the above sense, we consider all non-isomorphic examples in $PG(3-1,2)$ (ignoring the constraint $s\ge t$).

Example 1. 

Let $\mathcal{M}$ be a multiset of points in $PG(2,2)$ uniquely characterized by $\mathcal{M}\left(L\right)=s\in \mathbb{N}$ for some line L and $\mathcal{M}\left(L^{\prime }\right)=t\in \mathbb{N}$ for all other lines $L^{\prime }\ne L$. For each point $P\in L$, we have

$$\mathcal{M}\left(P\right)=\frac{s+2t}{3}-\frac{4t}{6}=\frac{s}{3}$$

(7)

and for each point $Q\notin L$, we have

$$\mathcal{M}\left(Q\right)=\frac{3t}{3}-\frac{s+3t}{6}=\frac{3t-s}{6}.$$

(8)

Since $\mathcal{M}\left(P\right),\mathcal{M}\left(Q\right)\in \mathbb{N}$ we set $x:=\mathcal{M}\left(P\right)=\frac{s}{3}$ and $y:=\mathcal{M}\left(Q\right)=\frac{3t-s}{6}$, so that $s=3x$ and $t=2y+x$. With this we have $n=3x+4y$, $\gamma =max\{x,y\}$, and $s-t=2(x-y)$. If $x\ge y$, then we can write $\mathcal{M}=y·{\chi }_E+(x-y)·{\chi }_L$. If $x\le y$, then we can write $\mathcal{M}=y·{\chi }_E-(y-x)·{\chi }_L$.

For Example 1 the set of all feasible $(s,t)$-pairs, assuming $s\ge t$, is given by ${〈(3,1)〉}_{\mathbb{N}}+{〈(3,3)〉}_{\mathbb{N}}$. If we assume $t\ge s$, then the set of feasible $(s,t)$-pairs is given by ${〈(0,2)〉}_{\mathbb{N}}+{〈(3,3)〉}_{\mathbb{N}}$. The vector $(0,2)$ can be computed from $(3,1)$ by computing a suitable complement.

Due to Lemma 6 we can always assume the existence of a point of multiplicity 0 as a normalization. So, in Example 1 we may assume $x=0$ or $y=0$, so that $\mathcal{M}=y·{\chi }_E-y·{\chi }_L$ or $\mathcal{M}=x·{\chi }_L$.

Due to Lemma 10 we can always assume that the greatest common divisor of all point multiplicities is 1 as a normalization (excluding the degenerated case of an empty multiset of points). Applying both normalizations to the multisets of points in Example 1 leaves the two possibilities ${\chi }_L$ and ${\chi }_E-{\chi }_L$, i.e., point sets.

Due to Lemma 7 we always can assume $\#\mathcal{M}\le \gamma \left(\mathcal{M}\right)·{\left[k\right]}_q/2$. Applying also the third normalization to the multisets of points in Example 1 leaves only the possibility ${\chi }_L$, i.e., a subspace construction; see Proposition 1, where $s=3$, $t=1$, $n=3$, and $s-t=2$.

Example 2. 

Let $\mathcal{M}$ be a multiset of points in $PG(2,2)$ uniquely characterized by $\mathcal{M}\left(L_1\right)=\mathcal{M}\left(L_2\right)=s\in \mathbb{N}$ for two different lines $L_1,L_2$ and $\mathcal{M}\left(L^{\prime }\right)=t\in \mathbb{N}$ for all other lines $L^{\prime }\notin \left\{L_1,L_2\right\}$. For $P:=L_1\cap L_2$, we have

$$\mathcal{M}\left(P\right)=\frac{2s+t}{3}-\frac{4t}{6}=\frac{2s-t}{3},$$

(9)

for each point $Q\in \left(L_1\cup L_2\right)\backslash \left\{P\right\}$, we have

$$\mathcal{M}\left(Q\right)=\frac{s+2t}{3}-\frac{s+3t}{6}=\frac{s+t}{6},$$

(10)

and for each point $R\notin L_1\cup L_2$, we have

$$\mathcal{M}\left(R\right)=\frac{3t}{3}-\frac{2s+2t}{6}=\frac{2t-s}{3}.$$

(11)

Since $\mathcal{M}\left(Q\right),\mathcal{M}\left(R\right)\in \mathbb{N}$ we set $x:=\mathcal{M}\left(Q\right)=\frac{s+t}{6}$ and $y:=\mathcal{M}\left(R\right)=\frac{2t-s}{3}$, so that $s=4x-y$ and $t=2x+y$. With this we have $n=6x+7y$ and $s-t=2(x-y)$. Of course we need to have $y\le 2x$ so that $\mathcal{M}\left(P\right)\ge 0$, which implies $s\ge 0$.

• $\mathcal{M}\left(P\right)=0$: $y=2x$, so that $\mathcal{M}\left(P\right)=0$, $\mathcal{M}\left(Q\right)=x$, $\mathcal{M}\left(R\right)=2x$, and the greatest common divisor of $\mathcal{M}\left(P\right)$, $\mathcal{M}\left(Q\right)$, and $\mathcal{M}\left(R\right)$ is equal to x. Thus, we can assume $x=1$, $y=2$, so that $s=2$, $t=4$, $n=8$, $\gamma =2$, $t-s=2$, and $\mathcal{M}=2{\chi }_E-{\chi }_{L_1}-{\chi }_{L_2}$ for two different lines $L_1,L_2$.
• $\mathcal{M}\left(Q\right)=0$: $x=0$, so that also $y=0$ and $\mathcal{M}$ is the empty multiset of points.
• $\mathcal{M}\left(R\right)=0$: $y=0$, $\mathcal{M}\left(P\right)=2x$, $\mathcal{M}\left(Q\right)=x$, so that $gcd\left(\mathcal{M}\right(P),\mathcal{M}(Q),\mathcal{M}(R\left)\right)=x$ and we can assume $x=1$. With this we have $s=4$, $t=2$, $n=6$, $\gamma =2$, $s-t=2$, and $\mathcal{M}={\chi }_{L_1}+{\chi }_{L_2}$ for two different lines $L_1,L_2$.

So, Example 2 can be explained by the construction in Proposition 2.

Example 3. 

Let $\mathcal{M}$ be a multiset of points in $PG(2,2)$ uniquely characterized by $\mathcal{M}\left(L_1\right)=\mathcal{M}\left(L_2\right)=\mathcal{M}\left(L_3\right)=s\in \mathbb{N}$ for three different lines $L_1,L_2,L_3$ with a common intersection point $P=L_1\cap L_2\cap L_3$ and $\mathcal{M}\left(L^{\prime }\right)=t\in \mathbb{N}$ for all other lines. We have

$$\mathcal{M}\left(P\right)=\frac{3s}{3}-\frac{4t}{6}=s-\frac{2t}{3}$$

(12)

and

$$\mathcal{M}\left(Q\right)=\frac{s+2t}{3}-\frac{2s+2t}{6}=\frac{t}{3}$$

(13)

for all points $Q\ne P$. Since $\mathcal{M}\left(P\right),\mathcal{M}\left(Q\right)\in \mathbb{N}$ we set $x:=\mathcal{M}\left(P\right)=s-\frac{2t}{3}$ and $y:=\mathcal{M}\left(Q\right)=\frac{t}{3}$, so that $s=x+2y$ and $t=3y$. With this we have $n=x+6y$ and $s-t=x-y$.

• $\mathcal{M}\left(P\right)=0$: $x=0$, so that we can assume $y=1$, which implies $s=2$, $t=3$, $\gamma =1$, $n=6$, $t-s=1$, and $\mathcal{M}={\chi }_E-{\chi }_P$ for some point P.
• $\mathcal{M}\left(Q\right)=0$: $y=0$, so that we can assume $x=1$, which implies $s=1$, $t=0$, $\gamma =1$, $n=1$, $s-t=1$, and $\mathcal{M}={\chi }_P$ for some point P.

So, also Example 3 can be explained by the subspace construction in Proposition 1.

Example 4. 

Let $\mathcal{M}$ be a multiset of points in $PG(2,2)$ uniquely characterized by $\mathcal{M}\left(L_1\right)=\mathcal{M}\left(L_2\right)=\mathcal{M}\left(L_3\right)=s\in \mathbb{N}$ for three different lines $L_1,L_2,L_3$ without a common intersection point, i.e., $L_1\cap L_2\cap L_3=\varnothing$, and $\mathcal{M}\left(L^{\prime }\right)=t\in \mathbb{N}$ for all other lines. For each point P that is contained on exactly two lines $L_i$, we have

$$\mathcal{M}\left(P\right)=\frac{2s+t}{3}-\frac{s+3t}{6}=\frac{3s-t}{6},$$

(14)

for each point Q that is contained on exactly one line $L_i$, we have

$$\mathcal{M}\left(Q\right)=\frac{s+2t}{3}-\frac{2s+2t}{6}=\frac{t}{3},$$

(15)

and for the unique point R that is contained on none of the lines $L_i$, we have

$$\mathcal{M}\left(R\right)=\frac{3t}{3}-\frac{3s+t}{6}=\frac{5t-3s}{6}.$$

(16)

Since $\mathcal{M}\left(P\right),\mathcal{M}\left(Q\right)\in \mathbb{N}$, we set $x:=\mathcal{M}\left(P\right)=\frac{3s-t}{6}$ and $y:=\mathcal{M}\left(Q\right)=\frac{t}{3}$, so that $s=2x+y$ and $t=3y$. With this we have $n=2x+5y$ and $s-t=2(x-y)$.

• $\mathcal{M}\left(P\right)=0$: $x=0$, so that we can assume $y=1$, which implies $s=1$, $t=3$, $t-s=2$, $\gamma =2$, $n=5$, and $\mathcal{M}={\chi }_L+2{\chi }_P$ for some line L and some point $P\notin L$.
• $\mathcal{M}\left(Q\right)=0$: $y=0$, so that $x=0$ and $\mathcal{M}$ is the empty multiset of points.
• $\mathcal{M}\left(R\right)=0$: $x=2y$, so that we can assume $y=1$, which implies $x=2$, $s=4$, $t=6$, $t-s=2$, $\gamma =2$, $n=9$, and the 2-complement of $\mathcal{M}$ equals $\mathcal{M}={\chi }_L+2{\chi }_P$ for some line L and some point $P\notin L$; see the case $\mathcal{M}\left(P\right)=0$.

So, also Example 4 can be explained by the construction in Proposition 2.

In Examples 1–4 we have considered all cases of $1\le \#\overline{\mathcal{M}}\le 3$ up to symmetry. The cases $\#\overline{\mathcal{M}}\in \{0,7\}$ give one-character multisets. By considering the complement ${\mathcal{M}}^{\prime }={\chi }_V-\overline{\mathcal{M}}$ we see that examples for $4\le \#\overline{\mathcal{M}}\le 6$ do not give anything new. Since the dimension of the ambient space is odd, we cannot apply the construction in Proposition 3.

Now, let us consider the general case. Given the set $\overline{\mathcal{M}}$ of hyperplanes with multiplicity s we obtain an explicit expression for the multiplicity $\mathcal{M}\left(P\right)$ of every point $P\in \mathcal{P}$ depending on the two unknown hyperplane multiplicities s and t.

Lemma 12. 

Let $\overline{\mathcal{M}}$ be a set of points in $PG(k-1,q)$, where $k\ge 3$, and $\mathcal{M}$ be a multiset of points in $PG(k-1,q)$ such that $\mathcal{M}\left(H\right)=s$ if $\overline{\mathcal{M}}\left(H^{\perp }\right)=1$ and $\mathcal{M}\left(H\right)=t$ if $\overline{\mathcal{M}}\left(H^{\perp }\right)=0$ for all hyperplanes $H\in \mathcal{H}$. Denoting the number of hyperplanes $H\ni P$ with $\mathcal{M}\left(H\right)=s$ by $\phi \left(P\right)$ and setting $r:=\#\overline{\mathcal{M}}$, $\Delta :=s-t\in \mathbb{Z}$, we have

$$\mathcal{M}\left(P\right)=\frac{t+\Delta ·\phi \left(P\right)}{{[k-1]}_q}-\frac{\Delta }{q^{k-2}}·\frac{{[k-2]}_q}{{[k-1]}_q}·\left(r-\phi \left(P\right)\right).$$

(17)

Proof. 

Counting gives that ${[k-1]}_q-\phi \left(P\right)$ hyperplanes through P have multiplicity t, from the $q^{k-1}$ hyperplanes not containing P exactly $r-\phi \left(P\right)$ have multiplicity $\mathcal{M}\left(H\right)=s$ and $q^{k-1}-r+\phi \left(P\right)$ have multiplicity $\mathcal{M}\left(H\right)=t$. With this we can use Lemma 1 to compute

$$\begin{array}{ccc}\hfill \mathcal{M}\left(P\right)& =& \sum _{H\in \mathcal{H}:P\in H}\frac{1}{{[k-1]}_q}·\mathcal{M}\left(H\right)+\sum _{H\in \mathcal{H}:P\notin H}\frac{1}{q^{k-1}}·\left(\frac{1}{{[k-1]}_q}-1\right)·\mathcal{M}\left(H\right)\hfill \\ & =& \sum _{H\in \mathcal{H}:P\in H}\frac{1}{{[k-1]}_q}·\mathcal{M}\left(H\right)-\sum _{H\in \mathcal{H}:P\notin H}\frac{1}{q^{k-1}}·\frac{q{[k-2]}_q}{{[k-1]}_q}·\mathcal{M}\left(H\right)\hfill \\ & =& t+\frac{\Delta }{{[k-1]}_q}·\phi \left(P\right)-\frac{q{[k-2]}_q}{{[k-1]}_q}·t-\frac{\Delta }{q^{k-1}}·\frac{q{[k-2]}_q}{{[k-1]}_q}·\left(r-\phi \left(P\right)\right)\hfill \\ & =& \frac{t+\Delta ·\phi \left(P\right)}{{[k-1]}_q}-\frac{\Delta }{q^{k-2}}·\frac{{[k-2]}_q}{{[k-1]}_q}·\left(r-\phi \left(P\right)\right).\hfill \end{array}$$

□

Note that $\phi \left(P\right)=\overline{\mathcal{M}}\left(P^{\perp }\right)$ for all $P\in \mathcal{P}$.

Lemma 13. 

Let $\overline{\mathcal{M}}$ be a set of points in $PG(k-1,q)$, where $k\ge 3$, and $\mathcal{M}$ be a multiset of points in $PG(k-1,q)$ such that $\mathcal{M}\left(H\right)=s$ if $\overline{\mathcal{M}}\left(H^{\perp }\right)=1$ and $\mathcal{M}\left(H\right)=t$ if $\overline{\mathcal{M}}\left(H^{\perp }\right)=0$ for all hyperplanes $H\in \mathcal{H}$. Denote the number of hyperplanes $H\ni P$ with $\mathcal{M}\left(H\right)=s$ by $\phi \left(P\right)$ and uniquely choose $m\in \mathbb{N}$, $\mathcal{I}\subseteq \mathbb{N}$ with $0\in \mathcal{I}$ such that $\left\{\phi \left(P\right):P\in \mathcal{P}\right\}=\left\{m+i:i\in \mathcal{I}\right\}$. If $s>t$ and there exists a point $Q\in \mathcal{P}$ with $\mathcal{M}\left(Q\right)=0$, then we have

$$t=\frac{\Delta }{q^{k-2}}·{[k-2]}_q·\left(r-m\right)-\Delta ·m$$

(18)

and

$$\mathcal{M}\left(P\right)=\frac{\Delta ·i}{q^{k-2}}$$

(19)

for all points $P\in \mathcal{P}$ where $i:=\phi \left(P\right)-m$, $r:=\#\overline{\mathcal{M}}$, and $\Delta :=s-t\in {\mathbb{N}}_{\ge 1}$. If $\mathcal{M}$ is non-repetitive, then Δ divides $q^{k-2}$.

Proof. 

Using $\Delta >0$ we observe that the expression for $\mathcal{M}\left(P\right)$ in Equation (17) is increasing in $\phi \left(P\right)$. So, we need to choose a point $Q\in \mathcal{P}$ which minimizes $\phi \left(Q\right)$ to normalize using $\mathcal{M}\left(Q\right)=0$, since otherwise we will obtain points with negative multiplicity. So, choosing a point $Q\in \mathcal{P}$ with $\phi \left(Q\right)=m$ we require

$$0=\mathcal{M}\left(Q\right)=\frac{t+\Delta ·m}{{[k-1]}_q}-\frac{\Delta }{q^{k-1}}·\frac{q{[k-2]}_q}{{[k-1]}_q}·\left(r-m\right),$$

which yields Equation (18). Using $i:=\phi \left(P\right)-m$ and the expression for t we compute

$$\begin{array}{ccc}\hfill \mathcal{M}\left(P\right)& =& \frac{t+\Delta ·(m+i)}{{[k-1]}_q}-\frac{\Delta }{q^{k-2}}·\frac{{[k-2]}_q}{{[k-1]}_q}·\left(r-m-i\right)\hfill \\ & =& \frac{\Delta }{q^{k-2}}·\frac{{[k-2]}_q}{{[k-1]}_q}·\left(r-m\right)-\frac{\Delta ·m}{{[k-1]}_q}+\frac{\Delta ·(m+i)}{{[k-1]}_q}-\frac{\Delta }{q^{k-2}}·\frac{{[k-2]}_q}{{[k-1]}_q}·\left(r-m-i\right)\hfill \\ & =& \frac{\Delta ·i}{{[k-1]}_q}+\frac{\Delta ·i}{q^{k-2}}·\frac{{[k-2]}_q}{{[k-1]}_q}=\frac{\Delta ·i}{q^{k-2}}\hfill \end{array}$$

for all $P\in \mathcal{P}$. Note that if $f>1$ is a divisor of $\Delta$ that is coprime to q, then all point multiplicities of $\mathcal{M}$ are divisible by f. If $\Delta =q^{k-2}·f$ for an integer $f>1$, then all point multiplicities of $\mathcal{M}$ are divisible by f. Thus, we have that $\Delta$ divides $q^{k-2}$. □

Note that $\mathcal{I}=\left\{\overline{\mathcal{M}}\left(H\right)-\overline{\mathcal{M}}\left(H^{\prime }\right):H\in \mathcal{H}\right\}$, where $H^{\prime }\in \mathcal{H}$ is a minimizer of $\overline{\mathcal{M}}\left(H\right)$.

Lemma 14. 

Let $\overline{\mathcal{M}}$ be a set of points in $PG(k-1,q)$, where $k\ge 3$ and $\mathcal{M}$ be a multiset of points in $PG(k-1,q)$ such that $\mathcal{M}\left(H\right)=s$ if $\overline{\mathcal{M}}\left(H^{\perp }\right)=1$ and $\mathcal{M}\left(H\right)=t$ if $\overline{\mathcal{M}}\left(H^{\perp }\right)=0$ for all hyperplanes $H\in \mathcal{H}$. Using the notation from Lemma 13 we set

$$\begin{array}{ccc}\hfill g& =& gcd\left(\{i\in \mathcal{I}\}\cup \left\{q^{k-2}\right\}\right),\hfill \end{array}$$

(20)

$$\begin{array}{ccc}\hfill {\Delta }_0& =& q^{k-2}/g,\hfill \end{array}$$

(21)

$$\begin{array}{ccc}\hfill t_0& =& \frac{1}{g}·{[k-2]}_q·\left(r-m\right)-{\Delta }_0·m,\mathit{and}\hfill \end{array}$$

(22)

$$\begin{array}{ccc}\hfill s_0& =& t+{\Delta }_0.\hfill \end{array}$$

(23)

If $s>t$, then we have

$$\mathbb{L}\left(\overline{\mathcal{M}}\right)={〈(s_0,t_0)〉}_{\mathbb{N}}+{〈({[k-1]}_q,{[k-1]}_q)〉}_{\mathbb{N}}.$$

Proof. 

Setting $\mu =\mu \left(\mathcal{M}\right)\in \mathbb{N}$ we have that ${\mathcal{M}}^{\prime }:=\mathcal{M}-\mu ·{\chi }_V$ is a two-character multiset corresponding to $(s^{\prime },t^{\prime }):=(s-\mu {[k-1]}_q,t-\mu {[k-1]}_q)\in \mathbb{L}\left(\overline{\mathcal{M}}\right)$ and there exists a point $Q\in \mathcal{P}$ with ${\mathcal{M}}^{\prime }\left(Q\right)=0$. Clearly, we have $(s^{\prime },t^{\prime })\in {\mathbb{N}}^2$ and $s^{\prime }>t^{\prime }$. From Lemma 13 we conclude the existence of an integer ${\Delta }^{\prime }\in {\mathbb{N}}_{\ge 1}$ such that $t^{\prime }=\frac{{\Delta }^{\prime }}{q^{k-2}}·{[k-2]}_q·\left(r-m\right)-{\Delta }^{\prime }·m$, $s^{\prime }=t^{\prime }+{\Delta }^{\prime }$, and ${\mathcal{M}}^{\prime }\left(P\right)=\frac{{\Delta }^{\prime }·i}{q^{k-2}}$ for all $P\in \mathcal{P}$. Since ${\mathcal{M}}^{\prime }\left(P\right)\in \mathbb{N}$ for all $P\in \mathcal{P}$ we have that $q^{k-2}$ divides ${\Delta }^{\prime }·g$, so that ${\Delta }_0\in \mathbb{N}$ divides ${\Delta }^{\prime }$. For $f:={\Delta }^{\prime }/{\Delta }_0\in {\mathbb{N}}_{\ge 1}$ we observe that ${\mathcal{M}}^{\prime }\left(P\right)$ is divisible by f and we set ${\mathcal{M}}^{″}:=\frac{1}{f}·{\mathcal{M}}^{\prime }$. With this, we can check that ${\mathcal{M}}^{″}$ is a two-character multiset corresponding to $(s_0,t_0)\in \mathbb{L}\left(\overline{\mathcal{M}}\right)$. □

Note that it is not necessary to explicitly check $t_0\in \mathbb{N}$ since ${\mathcal{M}}^{″}\left(P\right)\in \mathbb{N}$ is sufficient to this end.

Before we consider the problem whether $\mathbb{L}\left(\overline{\mathcal{M}}\right)\subseteq {\mathbb{N}}^2$ contains an element $(s,t)$ with $s>t$, we treat the so-far-excluded case $k=2$ separately.

Lemma 15. 

Let $\overline{\mathcal{M}}$ be a set of points in $PG(1,q)$. Then, we have

$$\mathbb{L}\left(\overline{\mathcal{M}}\right)={〈(s_0,0)〉}_{\mathbb{N}}+{〈(q+1,q+1)〉}_{\mathbb{N}},$$

where $s_0=0$ if $\#\overline{\mathcal{M}}\in \{0,q+1\}$ and $s_0=1$ otherwise.

Proof. 

If $\#\overline{\mathcal{M}}\in \{0,q+1\}$, then a two-character multiset $\mathcal{M}$ corresponding to $(s,t)\in \overline{\mathcal{M}}$ actually is a one-character multiset and there exists some integer $x\in \mathbb{N}$ such that $\mathcal{M}=x·{\chi }_v$.

Otherwise, we observe that in $PG(1,q)$ points and hyperplanes coincide and the image of $\overline{\mathcal{M}}$ is $\{0,1\}$. Note that we have $\mathcal{M}=t·{\chi }_V+{\sum }_{P\in \mathcal{P}}(s-t)·\overline{\mathcal{M}}\left(P\right)·{\chi }_P$ for each two-character multiset $\mathcal{M}$ corresponding to $(s,t)\in \mathbb{L}\left(\overline{\mathcal{M}}\right)$ by definition. We can easily check $(s,t)\in {〈(1,0)〉}_{\mathbb{N}}+{〈(q+1,q+1)〉}_{\mathbb{N}}$. The proof is completed by choosing $s=1$ and $t=0$ in our representation of $\mathcal{M}$. □

Theorem 1. 

Let $\overline{\mathcal{M}}$ be a set of points in $PG(k-1,q)$ with $\#\overline{\mathcal{M}}\notin \left\{0,{\left[k\right]}_q\right\}$, where $k\ge 2$. Then,

$$\mathcal{M}:=\sum _{H\in \mathcal{H}}\overline{\mathcal{M}}\left(H^{\perp }\right)·{\chi }_H$$

(24)

is a two-character multiset corresponding to $(s,t)\in \mathbb{L}\left(\overline{\mathcal{M}}\right)$ with $n=\#\mathcal{M}=r{[k-1]}_q$, where $r:=\#\overline{\mathcal{M}}$, $t=r{[k-2]}_q$, and $s=r{[k-2]}_q+q^{k-2}$. Setting $\mu :=\mu \left(\mathcal{M}\right)$ and $g:=gcd\left(\left\{\mathcal{M}\left(P\right)-\mu :P\in \mathcal{P}\right\}\right)$ the function

$${\mathcal{M}}^{\prime }:=\frac{1}{g}·\left(-\mu ·{\chi }_V+\sum _{H\in \mathcal{H}}\overline{\mathcal{M}}\left(H^{\perp }\right)·{\chi }_H\right)=\frac{1}{g}·\left(\mathcal{M}-\mu ·{\chi }_V\right)$$

(25)

is a two-character multiset corresponding to $(s_0,t_0)\in \mathbb{L}\left(\overline{\mathcal{M}}\right)$ with $n^{\prime }=\#{\mathcal{M}}^{\prime }=\frac{1}{q}·\left(r{[k-1]}_q-\mu {\left[k\right]}_q\right)$, where $r:=\#\overline{\mathcal{M}}$, $t_0=\frac{1}{g}·\left(r{[k-2]}_q-\mu {[k-1]}_q\right)$, and $s_0=\frac{1}{g}·\left(r{[k-2]}_q-\mu {[k-1]}_q+q^{k-2}\right)$, and g divides $q^{k-2}$. Moreover, we have

$$\mathbb{L}\left(\overline{\mathcal{M}}\right)={〈(s_0,t_0)〉}_{\mathbb{N}}+{〈({[k-1]}_q,{[k-1]}_q)〉}_{\mathbb{N}}.$$

(26)

Proof. 

We can easily check $\mathcal{M}\left(H\right)=r{[k-2]}_q=t$ if $\mathcal{M}\left(H^{\perp }\right)=0$ and $\mathcal{M}\left(H\right)=r{[k-2]}_q+q^{k-2}=s$ if $\mathcal{M}\left(H^{\perp }\right)=1$ for all $H\in \mathcal{H}$ as well as $\#\mathcal{M}=r{[k-1]}_q$ directly from the definition of $\mathcal{M}$. Using Lemmas 6 and 10 we conclude that ${\mathcal{M}}^{\prime }$ is a two-character multiset with the stated parameters.

For $k=2$, Lemma 15 is our last statement. For $k\ge 3$ we can apply Lemma 13 to conclude $g=gcd\left(\right\{i\in \mathcal{I}\left\}\right)$ and use the proof of Lemma 14 to conclude our last statement. Since $s,t\in \mathbb{N}$ and $s>t$ we have that g divides $g(s-t)=q^{k-2}$. □

Using the notation from Lemma 13 applied to the multiset of points $\mathcal{M}-\mu ·{\chi }_V$ from Theorem 1 we observe $\#\mathcal{I}\ge 2$ for $\#\overline{\mathcal{M}}\notin \left\{0,{\left[k\right]}_q\right\}$. Using the facts that $g:=gcd\left(\left\{\mathcal{M}\left(P\right)-\mu :P\in \mathcal{P}\right\}\right)$, that g divides $q^{k-2}$, and Equation (19) we conclude

$$g=gcd\left(\{i\in \mathcal{I}\}\right)=gcd\left(\left\{\overline{\mathcal{M}}\left(H\right)-\overline{\mathcal{M}}\left(H^{\prime }\right):H\in \mathcal{H}\right\}\right),$$

(27)

where $H^{\prime }\in \mathcal{H}$ is a minimizer of $\overline{\mathcal{M}}\left(H\right)$.

Using the classification of one-character multisets we conclude from Theorem 1:

Corollary 1. 

Let $\overline{\mathcal{M}}$ be a set of points in $PG(k-1,q)$, where $k\ge 2$. Then, there exist $\left(s_0,t_0\right)\in {\mathbb{N}}^2$ such that $\mathbb{L}\left(\overline{\mathcal{M}}\right)={〈(s_0,t_0)〉}_{\mathbb{N}}+{〈({[k-1]}_q,{[k-1]}_q)〉}_{\mathbb{N}}$.

Theorem 2. 

Let $\tilde{\mathcal{M}}$ be a two-character multiset in $PG(k-1,q)$, where $k\ge 2$. Then, there exist unique $u,v\in \mathbb{N}$ such that $\tilde{\mathcal{M}}=u·{\mathcal{M}}^{\prime }+v·{\chi }_V$, where ${\mathcal{M}}^{\prime }$ is given by Equation (25).

Proof. 

Let $s>t$ be the two hyperplane multiplicities of $\tilde{\mathcal{M}}$. With this, define $\overline{\mathcal{M}}$ such that $\overline{\mathcal{M}}\left(H^{\perp }\right)=1$ if $\tilde{\mathcal{M}}\left(H\right)=s$ and $\overline{\mathcal{M}}\left(H^{\perp }\right)=0$ if $\tilde{\mathcal{M}}\left(H\right)=t$ for all $H\in \mathcal{H}$. So, $(s,t)\in \mathbb{L}\left(\overline{\mathcal{M}}\right)$ and Theorem 1 yields the existence of $u,v\in \mathbb{N}$ with $(s,t)=u·(s_0,t_0)+v·({[k-1]}_q,{[k-1]}_q)$, where $s_0$, $t_0$ are as in Theorem 1. From Lemma 1 we then conclude $\tilde{\mathcal{M}}=u·{\mathcal{M}}^{\prime }+v·{\chi }_V$. Note that $\mu \left({\mathcal{M}}^{\prime }\right)$ and $\mu \left({\chi }_V\right)=1$ imply $\mu \left(\tilde{M}\right)=v$, so that u can be computed from $\gamma \left(\tilde{\mathcal{M}}\right)=u·\gamma \left({\mathcal{M}}^{\prime }\right)+v$, i.e., u and v are uniquely determined. □

Note that for a one-character multiset $\tilde{\mathcal{M}}$ there exists a unique $v\in \mathbb{N}$ such that $\tilde{\mathcal{M}}=v·{\chi }_V$. Given a set of points $\overline{\mathcal{M}}$ we call ${\mathcal{M}}^{\prime }$ the canonical representant of the set of two-character multisets $\mathcal{M}$ corresponding to $(s,t)\in \mathbb{L}\left(\overline{\mathcal{M}}\right)$. If $\mathcal{M}={\mathcal{M}}^{\prime }$ we just say that $\mathcal{M}$ is the canonical two-character multiset.

Theorem 3. 

Let $w_1<w_2$ be the non-zero weights of a non-repetitive ${[n,k]}_q$ two-weight code C without full support. Then, there exist integers f and u such that $w_1=u{p}^f$ and $w_2=(u+1)p^f$, where p is the characteristic of the underlying field ${\mathbb{F}}_q$.

Proof. 

Let $\mathcal{M}$ be the two-character multiset in $PG(k-1,q)$ corresponding to C. Choose unique $u,v\in \mathbb{N}$ such that $\mathcal{M}=u·{\mathcal{M}}^{\prime }+v·{\chi }_V$, as in Theorem 2. Since C does not have full support, we have $v=0$ and since C is non-repetitive we have $u=1$. With this we can use Theorem 1 to compute

$$w_1=n-s=\frac{1}{g}·\left(r·q^{k-2}-\mu ·q^{k-1}-q^{k-2}\right)=(r-q\mu -1)·p^f$$

(28)

and

$$w_2=n-t=\frac{1}{g}·\left(r·q^{k-2}-\mu ·q^{k-1}\right)=(r-q\mu )·p^f,$$

(29)

where f is chosen such that $\frac{q^{k-2}}{g}=p^f$, i.e., we can choose $u=r-q\mu -1$. □

We have seen in Equation (27) that we can compute the parameter g directly from the set of points $\overline{\mathcal{M}}$. If we additionally assume that $\overline{\mathcal{M}}$ is spanning, then we can consider the corresponding projective ${[n,k]}_q$-code $\overline{C}$, where $n=\#\overline{\mathcal{M}}$ (if $\overline{\mathcal{M}}$ is not spanning, then we can consider the lower-dimensional subspace spanned by $supp\left(\overline{\mathcal{M}}\right)$). Note that we have $\overline{\mathcal{M}}\left(H\right)\equiv m(modg)$ for all $H\in \mathcal{H}$ and that g is maximal with this property. If $m\equiv n(modg)$, then g would simply be the maximal divisibility constant of the weights of $\overline{C}$. From theorem 7 in [24] or theorem 3 in [25] we can conclude $m\equiv n(modg)$. Thus, we have

$$g=gcd\left(\left\{wt\left(c\right):c\in \overline{C}\right\}\right).$$

(30)

The argument may also be based on the following lemma (using the fact that $\overline{C}$ is projective):

Lemma 16. 

Let C be an ${[n,k]}_q$-code of full length such that we have $wt\left(c\right)\equiv m(mod\Delta )$ for all non-zero codewords $c\in C$. If Δ is a power of the characteristic of the underlying field ${\mathbb{F}}_q$, then we have $m\equiv 0(modmin\{\Delta ,q\left\}\right)$. Moreover, if additionally q divides Δ and $k\ge 2$, then the non-zero weights in each residual code are congruent to $m/q$ modulo $\Delta /q$.

Proof. 

Let $\mathcal{M}$ be the multiset of points in $PG(k-1,q)$ corresponding to C. For each hyperplane H we have $n-\mathcal{M}\left(H\right)\equiv m(mod\Delta )$, which is equivalent to $\mathcal{M}\left(H\right)\equiv n-m(mod\Delta )$. The weight of a non-zero codeword in a residual code is given by a subspace K of codimension 2 and a hyperplane H with $K\le H$. With this, the weight is given by $\mathcal{M}\left(H\right)-\mathcal{M}\left(K\right)\equiv n-m-\mathcal{M}\left(K\right)(mod\Delta )$. Counting the hyperplane multiplicities of the $q+1$ hyperplanes that contain K yields

$$\sum _{H\in \mathcal{H}:K\le H}\mathcal{M}\left(H\right)=\#\mathcal{M}+q·\mathcal{M}\left(K\right)=\#\mathcal{M}+q·\mathcal{M}\left(K\right)$$

(31)

and

$$\sum _{H\in \mathcal{H}:K\le H}\mathcal{M}\left(H\right)\equiv (q+1)(n-m)(mod\Delta ),$$

(32)

so that

$$m\equiv q·\left(n-m-\mathcal{M}\left(K\right)\right)(mod\Delta ).$$

(33)

□

Given Equation (30) we might be interested in projective divisible codes (with a large divisibility constant). For enumerations for the binary case we refer the reader to [26] and for a more general survey we refer the reader to, e.g., [27]. Note that the only point sets $\mathcal{M}$ in $PG(k-1,q)$ that are $q^{k-1}$-divisible are given by $\#\mathcal{M}\in \left\{0,{\left[k\right]}_q\right\}$, i.e., the empty and the full set. All other point sets are at most $q^{k-2}$-divisible, as implied by Theorem 1.

6. Enumeration of Two-Character Multisets in $\mathbf{PG}\mathbf{(}\mathit{k}\mathbf{-}\mathbf{1}\mathbf{,}\mathit{q}\mathbf{)}$ for Small Parameters

Since all two-character multisets in $PG(1,q)$ can be parameterized as $\mathcal{M}=b·{\chi }_V+{\sum }_{P\in \mathcal{P}}(a-b)·\overline{\mathcal{M}}\left(P\right)·{\chi }_P$ for integers $a>b\ge 0$ and a set of points $\overline{\mathcal{M}}$ in $PG(k-1,q)$ (see Lemma 15 and its proof), we assume $k\ge 3$ in the following. Due to Theorem 2, every two-character multiset in $PG(k-1,q)$ can be written as $u·{\mathcal{M}}^{\prime }+v·{\chi }_V$, where $u,v\in \mathbb{N}$ and ${\mathcal{M}}^{\prime }$ is characterized in Theorem 1. So, we further restrict out considerations on canonical two-character multisets where we have $u=1$ and $v=0$. For $k=2$, all canonical two-character multisets in $PG(k-1,q)$ are indeed sets of points and given by the construction in Proposition 3 (with $r=1$).

It can be easily checked that two isomorphic sets of points in $PG(k-1,q)$ yield isomorphic canonical two-character multisets ${\mathcal{M}}^{\prime }$. So, for the full enumeration of canonical two-character multisets in $PG(k-1,q)$ we just need to loop over all non-isomorphic sets of points $\overline{\mathcal{M}}$ in $PG(k-1,q)$ and use Theorem 1 to determine $\mathcal{M}$, ${\mathcal{M}}^{\prime }$, and their parameters. We remark that the numbers of non-isomorphic projective codes per length, dimension, and field size are, e.g., listed in tables 6.10–6.12 in [28] (for small parameters). For the binary case and at most six dimensions some additional data can be found in [29]. Here, we utilize the software package LinCode [30] to enumerate these codes.

In

Table 1. Feasible parameters for canonical two-character multisets in $PG(2,2)$.

g	$\mathit{\mu }$	r	n	$\mathit{\gamma }$	s	t	${\mathit{s}}_0$	${\mathit{t}}_0$	${\mathit{n}}^{\prime }$	${\mathit{\gamma }}^{\prime }$
2	1	3	9	3	5	3	1	0	1	1
1	0	1	3	1	3	1	3	1	3	1
1	2	6	18	3	8	6	2	0	4	1
2	0	4	12	2	6	4	3	2	6	1
1	1	4	12	3	6	4	3	1	5	2
1	0	2	6	2	4	2	4	2	6	2
1	1	5	15	3	7	5	4	2	8	2
1	0	3	9	2	5	3	5	3	9	2

and

Table 2. Feasible parameters for canonical two-character multisets in $PG(3,2)$.

g	$\mathit{\mu }$	r	n	$\mathit{\gamma }$	s	t	${\mathit{s}}_0$	${\mathit{t}}_0$	${\mathit{n}}^{\prime }$	${\mathit{\gamma }}^{\prime }$
4	3	7	49	7	25	21	1	0	1	1
2	1	3	21	3	13	9	3	1	3	1
2	4	10	70	6	34	30	3	1	5	1
2	2	6	42	4	22	18	4	2	6	1
1	0	1	7	1	7	3	7	3	7	1
1	6	14	98	7	46	42	4	0	8	1
2	3	9	63	5	31	27	5	3	9	1
2	1	5	35	3	19	15	6	4	10	1
2	4	12	84	6	40	36	6	4	12	1
4	0	8	56	4	28	24	7	6	14	1
2	2	8	56	6	28	24	7	5	13	2
1	0	2	14	2	10	6	10	6	14	2
2	0	4	28	4	16	12	8	6	14	2
1	5	13	91	7	43	39	8	4	16	2
2	3	11	77	7	37	33	8	6	16	2
2	1	7	49	5	25	21	9	7	17	2
1	1	4	28	4	16	12	9	5	13	3
1	4	11	77	7	37	33	9	5	17	3
1	3	9	63	6	31	27	10	6	18	3
1	2	7	49	5	25	21	11	7	19	3
1	1	5	35	4	19	15	12	8	20	3
1	0	3	21	3	13	9	13	9	21	3
1	4	12	84	7	40	36	12	8	24	3
1	3	10	70	6	34	30	13	9	25	3
1	2	8	56	5	28	24	14	10	26	3
1	1	6	42	4	22	18	15	11	27	3
1	0	4	28	3	16	12	16	12	28	3
1	3	11	77	6	37	33	16	12	32	3
1	3	8	56	7	28	24	7	3	11	4
1	2	6	42	6	22	18	8	4	12	4
1	3	9	63	7	31	27	10	6	18	4
1	2	7	49	6	25	21	11	7	19	4
1	1	5	35	5	19	15	12	8	20	4
1	3	10	70	7	34	30	13	9	25	4
1	2	8	56	6	28	24	14	10	26	4
1	1	6	42	5	22	18	15	11	27	4
1	2	9	63	6	31	27	17	13	33	4
1	1	7	49	5	25	21	18	14	34	4
1	0	5	35	4	19	15	19	15	35	4
1	2	10	70	6	34	30	20	16	40	4
1	1	8	56	5	28	24	21	17	41	4
1	0	6	42	4	22	18	22	18	42	4
1	1	9	63	5	31	27	24	20	48	4
1	0	7	49	4	25	21	25	21	49	4

we list the feasible parameters for canonical two-character multisets in $PG(2,2)$ and in $PG(3,2)$, respectively, where $n^{\prime }:=\#{\mathcal{M}}^{\prime }$ and ${\gamma }^{\prime }:=\gamma \left({\mathcal{M}}^{\prime }\right)$. The two hyperplane multiplicities for ${\mathcal{M}}^{\prime }$ are denoted by $s_0$, $t_0$ and those of $\mathcal{M}$ by $s,t$. The parameters g, $\mu$, r are as in (25) and $n=\#\mathcal{M}$. For $PG(2,2)$ we can also state more direct constructions:

• $(n^{\prime },s_0,t_0,{\gamma }^{\prime })=(1,1,0,1)$: characteristic function of a point (not spanning);
• $(n^{\prime },s_0,t_0,{\gamma }^{\prime })=(3,3,1,1)$: characteristic function of a line (not spanning);
• $(n^{\prime },s_0,t_0,{\gamma }^{\prime })=(4,2,0,1)$: complement of the characteristic function of a line;
• $(n^{\prime },s_0,t_0,{\gamma }^{\prime })=(6,3,2,1)$: complement of the characteristic function of a point;
• $(n^{\prime },s_0,t_0,{\gamma }^{\prime })=(5,3,1,2)$: ${\chi }_L+2{\chi }_P$ for a line L and a point P with $P\notin L$;
• $(n^{\prime },s_0,t_0,{\gamma }^{\prime })=(6,4,2,2)$: ${\chi }_L+{\chi }_L^{\prime }$ for two different lines L and $L^{\prime }$;
• $(n^{\prime },s_0,t_0,{\gamma }^{\prime })=(8,4,2,2)$: ${\chi }_V-{\chi }_L-{\chi }_L^{\prime }$ for two different lines L and $L^{\prime }$;
• $(n^{\prime },s_0,t_0,{\gamma }^{\prime })=(9,5,3,2)$: $2{\chi }_V-{\chi }_L+-{\chi }_P$ for a line L and a point P with $P\notin L$.

Of course, also for $PG(3,2)$ some of the examples have nicer descriptions:

• $(n^{\prime },s_0,t_0,{\gamma }^{\prime })=(1,1,0,1)$: characteristic function of a point (not spanning);
• $(n^{\prime },s_0,t_0,{\gamma }^{\prime })=(3,3,1,1)$: characteristic function of a line (not spanning);
• $(n^{\prime },s_0,t_0,{\gamma }^{\prime })=(7,7,3,1)$: characteristic function of a plane (not spanning);
• $(n^{\prime },s_0,t_0,{\gamma }^{\prime })=(5,3,1,1)$: projective base; spanning projective 2-weight code;
• $(n^{\prime },s_0,t_0,{\gamma }^{\prime })=(6,4,2,1)$: characteristic function of two disjoint lines; spanning projective 2-weight code;
• $(n^{\prime },s_0,t_0,{\gamma }^{\prime })=(14,10,6,2)$: characteristic function of two different planes;
• $(n^{\prime },s_0,t_0,{\gamma }^{\prime })=(21,13,9,3)$: characteristic function of three planes intersecting in a common point but not a common line.

Note that we may restrict our considerations to $r<{\left[k\right]}_q/2$, since if ${\mathcal{M}}^{\prime }$ is the a canonical two-character multiset for a set of points $\overline{\mathcal{M}}$ with $\#\overline{\mathcal{M}}=r$, then the complement of ${\mathcal{M}}^{\prime }$ is the a canonical two-character multiset for a set of points which is the complement of $\overline{\mathcal{M}}$ and has cardinality ${\left[k\right]}_q-r$.

From the data in Table 1 and Table 2 we can guess the maximum possible point multiplicity $\gamma \left({\mathcal{M}}^{\prime }\right)$ of ${\mathcal{M}}^{\prime }$:

Proposition 4. 

Let $\mathcal{M}$ be a canonical two-character multiset in $PG(k-1,q)$, where $k\ge 2$. Then, we have $\gamma \left(\mathcal{M}\right)\le q^{k-2}$.

Proof. 

Choose a suitable set ${\mathcal{H}}^{\prime }\subseteq \mathcal{H}$ and $g,\nu \in \mathbb{N}$ such that

$$\mathcal{M}=\frac{1}{g}·\left(\sum _{H\in {\mathcal{H}}^{\prime }}{\chi }_H-\mu ·{\chi }_V\right).$$

Let $P\in \mathcal{P}$ be a point with $\mathcal{M}\left(P\right)=\gamma$ and $Q\in \mathcal{P}$ be a point with $\mathcal{M}\left(Q\right)=0$. With this we have $\lambda \ge \left|\left\{H\in {\mathcal{H}}^{\prime }:Q\le H\right\}\right|$. Since P is contained in ${[k-1]}_q$ hyperplanes in $\mathcal{H}$ and $\langle P,Q\rangle$ is contained in ${[k-2]}_q$ hyperplanes in $\mathcal{H}$, we have $\mathcal{M}\left(P\right)\le q^{k-2}$. □

We can easily construct an example showing that the stated upper bound is tight. To this end, let P, Q be two different points in $PG(k-1,q)$, where $k\ge 3$, and $H^{\prime }$ be an arbitrary hyperplane neither containing P nor Q. With this, we choose ${\mathcal{H}}^{\prime }$ as the set of all $q^{k-2}$ hyperplanes that contain P but do not contain Q and additionally the hyperplane $H^{\prime }$. For the corresponding multiset of points $\mathcal{M}$ we then have $\mathcal{M}\left(P\right)=q^{k-2}$ and $\mathcal{M}\left(Q\right)=0$, so that $\mu \left(\mathcal{M}\right)=0$. For an arbitrary point $R\in H^{\prime }$ we have $\mathcal{M}\left(R\right)=q^{k-2}-q^{k-3}+1=(q-1)q^{k-3}+1$, so that $gcd\left(\mathcal{M}\right(R),\mathcal{M}(P\left)\right)=1$ if $k\ge 4$ or $k=3$ and $q\ne 2$. For $(k,q)=(3,2)$ we have already seen examples of canonical two-character multisets with maximum point multiplicity 2.

In

Table 3. Feasible parameters for canonical two-character multisets in $PG(4,2)$ with ${\gamma }^{\prime }\le 4$—part 1.

g	$\mathit{\mu }$	r	n	$\mathit{\gamma }$	s	t	${\mathit{s}}_0$	${\mathit{t}}_0$	${\mathit{n}}^{\prime }$	${\mathit{\gamma }}^{\prime }$
8	7	15	225	15	113	105	1	0	1	1
4	3	7	105	7	57	49	3	1	3	1
2	1	3	45	3	29	21	7	3	7	1
1	0	1	15	1	15	7	15	7	15	1
1	14	30	450	15	218	210	8	0	16	1
2	12	28	420	14	204	196	12	8	24	1
4	8	24	360	12	176	168	14	12	28	1
8	0	16	240	8	120	112	15	14	30	1
2	2	6	90	6	50	42	10	6	14	2
2	5	13	195	9	99	91	12	8	20	2
2	3	9	135	7	71	63	13	9	21	2
2	1	5	75	5	43	35	14	10	22	2
2	8	20	300	12	148	140	14	10	26	2
2	6	16	240	10	120	112	15	11	27	2
2	4	12	180	8	92	84	16	12	28	2
2	2	8	120	6	64	56	17	13	29	2
4	0	8	120	8	64	56	16	14	30	2
2	0	4	60	4	36	28	18	14	30	2
1	0	2	30	2	22	14	22	14	30	2
4	7	23	345	15	169	161	16	14	32	2
2	11	27	405	15	197	189	16	12	32	2
1	13	29	435	15	211	203	16	8	32	2
2	9	23	345	13	169	161	17	13	33	2
2	7	19	285	11	141	133	18	14	34	2
2	5	15	225	9	113	105	19	15	35	2
2	3	11	165	7	85	77	20	16	36	2
2	10	26	390	14	190	182	20	16	40	2
2	8	22	330	12	162	154	21	17	41	2
2	6	18	270	10	134	126	22	18	42	2
2	9	25	375	13	183	175	24	20	48	2
2	4	10	150	10	78	70	9	5	13	3
2	9	21	315	15	155	147	10	6	18	3
2	3	9	135	9	71	63	13	9	21	3
2	6	16	240	12	120	112	15	11	27	3
2	4	12	180	10	92	84	16	12	28	3
2	2	8	120	8	64	56	17	13	29	3
1	1	4	60	4	36	28	21	13	29	3
2	7	19	285	13	141	133	18	14	34	3
2	5	15	225	11	113	105	19	15	35	3
2	3	11	165	9	85	77	20	16	36	3
2	1	7	105	7	57	49	21	17	37	3
2	6	18	270	12	134	126	22	18	42	3
2	4	14	210	10	106	98	23	19	43	3
2	2	10	150	8	78	70	24	20	44	3
1	0	3	45	3	29	21	29	21	45	3
1	12	28	420	15	204	196	24	16	48	3
2	7	21	315	13	155	147	25	21	49	3

and

Table 4. Feasible parameters for canonical two-character multisets in $PG(4,2)$ with ${\gamma }^{\prime }\le 4$—part 2.

g	$\mathit{\mu }$	r	n	$\mathit{\gamma }$	s	t	${\mathit{s}}_0$	${\mathit{t}}_0$	${\mathit{n}}^{\prime }$	${\mathit{\gamma }}^{\prime }$
2	5	17	255	11	127	119	26	22	50	3
2	3	13	195	9	99	91	27	23	51	3
2	8	24	360	14	176	168	28	24	56	3
2	6	20	300	12	148	140	29	25	57	3
2	4	16	240	10	120	112	30	26	58	3
2	2	12	180	8	92	84	31	27	59	3
1	11	27	405	14	197	189	32	24	64	3
2	7	23	345	13	169	161	32	28	64	3
2	5	19	285	11	141	133	33	29	65	3
2	3	15	225	9	113	105	34	30	66	3
2	6	22	330	12	162	154	36	32	72	3
2	0	10	150	6	78	70	39	35	75	3
2	5	21	315	11	155	147	40	36	80	3
2	4	12	180	12	92	84	16	12	28	4
1	2	6	90	6	50	42	20	12	28	4
2	3	11	165	11	85	77	20	16	36	4
2	4	14	210	12	106	98	23	19	43	4
1	2	7	105	6	57	49	27	19	43	4
1	1	5	75	5	43	35	28	20	44	4
1	11	26	390	15	190	182	25	17	49	4
1	10	24	360	14	176	168	26	18	50	4
1	9	22	330	13	162	154	27	19	51	4
1	8	20	300	12	148	140	28	20	52	4
1	7	18	270	11	134	126	29	21	53	4
1	5	14	210	9	106	98	31	23	55	4
2	6	20	300	14	148	140	29	25	57	4
1	3	10	150	7	78	70	33	25	57	4
2	4	16	240	12	120	112	30	26	58	4
1	2	8	120	6	64	56	34	26	58	4
1	1	6	90	5	50	42	35	27	59	4
1	0	4	60	4	36	28	36	28	60	4
1	11	27	405	15	197	189	32	24	64	4
1	10	25	375	14	183	175	33	25	65	4
2	3	15	225	11	113	105	34	30	66	4
1	9	23	345	13	169	161	34	26	66	4
2	1	11	165	9	85	77	35	31	67	4
1	8	21	315	12	155	147	35	27	67	4
1	6	17	255	10	127	119	37	29	69	4
1	4	13	195	8	99	91	39	31	71	4
1	3	11	165	7	85	77	40	32	72	4
1	2	9	135	6	71	63	41	33	73	4
1	1	7	105	5	57	49	42	34	74	4
1	0	5	75	4	43	35	43	35	75	4
1	10	26	390	14	190	182	40	32	80	4
2	3	17	255	11	127	119	41	37	81	4
1	9	24	360	13	176	168	41	33	81	4
2	4	20	300	12	148	140	44	40	88	4
2	3	19	285	11	141	133	48	44	96	4
1	9	25	375	13	183	175	48	40	96	4

, we list the feasible parameters for canonical two-character multisets in $PG(4,2)$ with point multiplicity at most 4.