# On linear diameter perfect Lee codes with diameter 6

Tao Zhang${}^{\text{a,}}$ and Gennian Ge${}^{\text{b,}}$
${}^{\text{a}}$ Zhejiang Lab, Hangzhou 311100, China.
${}^{\text{b}}$ School of Mathematics Sciences, Capital Normal University,
Beijing 100048, China.
Email address<EMAIL_ADDRESS>address<EMAIL_ADDRESS>
###### Abstract

In 1968, Golomb and Welch conjectured that there is no perfect Lee codes with
radius $r\geq 2$ and dimension $n\geq 3$. A diameter perfect code is a natural
generalization of the perfect code. In 2011, Etzion (IEEE Trans. Inform.
Theory, 57(11): 7473–7481, 2011) proposed the following problem: Are there
diameter perfect Lee (DPL, for short) codes with diameter greater than four
besides the $DPL(3,6)$ code? Later, Horak and AlBdaiwi (IEEE Trans. Inform.
Theory, 58(8): 5490–5499, 2012) conjectured that there are no $DPL(n,d)$ codes
for dimension $n\geq 3$ and diameter $d>4$ except for $(n,d)=(3,6)$. In this
paper, we give a counterexample to this conjecture. Moreover, we prove that
for $n\geq 3$, there is a linear $DPL(n,6)$ code if and only if $n=3,11$.

Keywords: Diameter perfect code, Lee metric, group ring, lattice tiling.

AMS subject classifications: 52C22, 11H31, 11H71.

##  1 Introduction

The Lee metric was first introduced in [16, 29] for transmission of signals.
For two vectors
$u=(u_{1},\dots,u_{n}),v=(v_{1},\dots,v_{n})\in\mathbb{Z}^{n}$, their _Lee
distance_ is defined by

$d_{L}(u,v)=\sum_{i=1}^{n}|u_{i}-v_{i}|.$

A _Lee code_ $C$ in $\mathbb{Z}^{n}$ is a subset of $\mathbb{Z}^{n}$ endowed
with Lee distance. If $C$ is also a subgroup of $\mathbb{Z}^{n}$, then $C$ is
called a _linear Lee code_. Lee codes have been well studied due to many
practical applications, for example, constrained and partial-response channel
[24], flash memory [14, 26], interleaving schemes [3] and multidimensional
burst error correction [7].

Let $S_{n,r}(u)$ denote the _Lee sphere_ of radius $r$ centered at $u$, that
is,

$S_{n,r}(u)=\\{v\in\mathbb{Z}^{n}:\ d_{L}(u,v)\leq r\\}.$

The _packing radius_ $r(C)$ of a Lee code $C$ is the greatest integer $r$ such
that $S_{n,r}(u)\cap S_{n,r}(v)=\emptyset$ holds for all $u,v\in C$. The
_covering radius_ $R(C)$ of a Lee code $C$ is the smallest integer $r$ such
that $\cup_{u\in C}S_{n,r}(u)=\mathbb{Z}^{n}$. A Lee code
$C\subseteq\mathbb{Z}^{n}$ is called _perfect_ if $r(C)=R(C)=r$, and then $C$
is called a $PL(n,r)$ code.

Another way to define perfect codes is by tiling. For a subset
$V\subset\mathbb{Z}^{n}$, if there exists $W\subset\mathbb{Z}^{n}$ such that
$\mathbb{Z}^{n}=V\bigoplus W$, then we say that $\mathbb{Z}^{n}$ can be
_tiled_ by $V$. It is easy to see that there is a $PL(n,r)$ code if and only
if $\mathbb{Z}^{n}$ can be tiled by $S_{n,r}(0)$. The well-known _Golomb-Welch
conjecture_ states that

######  Conjecture 1.1.

[8] For $n\geq 3$ and $r\geq 2$, there is no $PL(n,r)$ code.

In [8], Golomb and Welch showed that there is no $PL(n,r)$ code for $n\geq 3$
and $e\geq e_{n}$, where $e_{n}$ is not specified. Post [21] proved the
nonexistence of $PL(n,r)$ codes for $n\geq 6$ and
$r\geq\frac{\sqrt{2}}{2}n-\frac{1}{4}(3\sqrt{2}-2)$. Later, Lepistö [17]
showed that $PL(n,r)$ codes must satisfy $n\geq\frac{(r+2)^{2}}{2.1}$, where
$r\geq 285$.

For some small dimensions, Golomb-Welch conjecture has been solved. Gravier et
al. [9] settled the dimension 3 case. Dimension 4 was resolved in [27], and
dimension 5 was proved in [11]. Horak [10] showed the nonexistence of perfect
Lee codes for $n=6$ and $r=2$.

Researchers also considered the conjecture with small radius. Under certain
conditions, the nonexistence of $PL(n,r)$ (or linear $PL(n,r)$) codes has been
proved in [15, 23, 31, 32] for $r=2,3,4$. In [18], Leung and Zhou completely
solved the existence of linear $PL(n,2)$ codes. In [30, 33], the authors
showed that almost perfect linear Lee codes of radius 2 only exist for small
dimensions. For more information about Golomb-Welch conjecture, we refer the
readers to a recent survey [13].

A natural generalization of perfect code includes the diameter perfect code.
Let $(V,d)$ be a metric space. Then a set $C\subseteq V$ is a _diameter $d$
code_ if $d(u,v)\geq d$ for any $u,v\in C$, and a set $A\subseteq V$ is a
_diameter $d$ anticode_ if $d(u,v)\leq d$ for all $u,v\in A$. In [1], the
authors proved that if $V$ is a distance regular graph, $C$ is a diameter $d$
code and $A$ is a diameter $d-1$ anticode, then $|C||A|\leq|V|$. A diameter
$d$ code that attains above bound with equality is called a diameter $d$
perfect code. For more about perfect codes (and diameter perfect codes), we
refer the readers to [6].

However, the above definition cannot be extended to infinite space. In order
to define diameter perfect Lee codes, we need the following notations. Let
$\mathcal{S}=\\{S_{i}:i\in I\\}$ be a family of subsets of $\mathbb{Z}^{n}$.
Then a set $T\subset\mathbb{Z}^{n}$ is called a transversal of $\mathcal{S}$
if $|T\cap S_{i}|=1$ for each $i\in I$, and $T\cap S_{i}\neq T\cap S_{j}$ for
all $i\neq j$.

######  Definition 1.2.

Let $C\subseteq\mathbb{Z}^{n}$. Then $C$ is a diameter $d$ perfect Lee code if
$C$ is a diameter $d$ code, and there is a tiling $\mathcal{T}=\\{W_{i}:i\in
I\\}$ of $\mathbb{Z}^{n}$ by the anticode of diameter $d-1$ of maximum size
such that $C$ is a transversal of $\mathcal{T}$. The diameter $d$ perfect Lee
code in $\mathbb{Z}^{n}$ will be denoted by $DPL(n,d)$.

For $d$ odd, the anticode of diameter $d-1$ of the maximum size is the Lee
sphere $S_{n,\frac{d-1}{2}}$. Hence $DPL(n,d)$ is the same as
$PL(n,\frac{d-1}{2})$ for $d$ odd.

For $u,v\in\mathbb{Z}^{n}$ with $d_{L}(u,v)=1$, the double Lee sphere is
defined by

$DS_{n,r}(u,v)=S_{n,r}(u)\cup S_{n,r}(v).$

The size of double Lee sphere is [4]

$|DS_{n,r}|=\sum_{i=0}^{\min\\{n-1,r\\}}2^{i+1}\binom{n-1}{i}\binom{r+1}{i+1}.$

It was pointed out in [2] that, for $d$ even, the anticode of diameter $d-1$
of maximum size is the double Lee sphere $DS_{n,r}$ with $r=\frac{d-2}{2}$.

The following conjecture is an extension of Golomb-Welch conjecture, which was
first proposed by Etzion [5] and formally presented in [12].

######  Conjecture 1.3.

There is no $DPL(n,d)$ code for $n\geq 3$ and $d>4$ with the exception of the
pair $(n,d)=(3,6)$.

In this paper, we give a counterexample to this conjecture. Moreover, we prove
the following result.

######  Theorem 1.4.

For $n\geq 3$, there is a linear $DPL(n,6)$ code if and only if $n=3,11$.

This paper is organized as follows. In Section 2, we first give some basics
about group rings and partial difference sets, then we provide a group ring
representation of linear $DPL(n,6)$ codes. In Section 3, we prove our main
result.

##  2 Preliminaries

###  2.1 Group ring and partial difference set

Let $G$ be a finite abelian group (written multiplicatively). The group ring
$\mathbb{Z}[G]$ is a free abelian group with a basis $\\{g:\ g\in G\\}$. For
any $A\in\mathbb{Z}[G]$, $A$ can be written as formal sum $A=\sum_{g\in
G}a_{g}g$, where $a_{g}\in\mathbb{Z}$. For any $A=\sum_{g\in
G}a_{g}g\in\mathbb{Z}[G]$ and $t\in\mathbb{Z}$, we define

$A^{(t)}=\sum_{g\in G}a_{g}g^{t}.$

Addition, subtraction and multiplication in group rings are defined as:

$\sum_{g\in G}a_{g}g\pm\sum_{g\in G}b_{g}g=\sum_{g\in G}(a_{g}\pm b_{g})g,$

and

$\sum_{g\in G}a_{g}g\sum_{g\in G}b_{g}g=\sum_{g\in G}(\sum_{h\in
G}a_{h}b_{h^{-1}g})g.$

For any set $A$ whose elements belong to $G$ ($A$ may be a multiset), we can
identify $A$ with the group ring element $\sum_{g\in G}a_{g}g$, where $a_{g}$
is the multiplicity of $g$ appearing in $A$. For a finite abelian group $G$,
its character group is denoted by $\widehat{G}$. For any $A=\sum_{g\in
G}a_{g}g\in\mathbb{Z}[G]$ and $\chi\in\widehat{G}$, define

$\chi(A)=\sum_{g\in G}a_{g}\chi(g).$

Group rings are widely used in the study of difference sets and related
topics, see [22, 25] and the references therein.

We also need some results about partial difference sets. We first give its
definition.

######  Definition 2.1.

A $k$-element subset $D$ of a finite group $G$ (written multiplicatively) of
order $v$ is called a $(v,k,\lambda,\mu)$-partial difference set in $G$ if the
multiset $\\{d_{1}d_{2}^{-1}:\ d_{1},d_{2}\in D,d_{1}\neq d_{2}\\}$ contains
each nonidentity element of $D$ exactly $\lambda$ times and each nonidentity
element of $G\backslash D$ exactly $\mu$ times. When $e\not\in D$ and
$D^{(-1)}=D$, then $D$ is called a regular partial difference set.

In the language of group ring, $D$ is a $(v,k,\lambda,\mu)$ partial difference
set in $G$ if and only if

$DD^{(-1)}=\mu G+(\lambda-\mu)D+\gamma e,$

where $\gamma=k-\mu$ if $e\notin D$ and $\gamma=k-\lambda$ if $e\in D$. See
[20] for the background on partial difference sets. The following result can
be found in [19].

######  Lemma 2.2.

[19] If there exists a nontrivial regular $(v,k,\lambda,\mu)$ partial
difference set in an abelian group, then $v,\Delta$ and $v^{2}/\Delta$ must
have the same prime divisors, where $\Delta=(\lambda-\mu)^{2}+4(k-\mu)$.

###  2.2 Group ring representation of linear $DPL(n,6)$ codes

In this paper, we focus on the existence of linear $DPL(n,d)$ codes. The
following theorem says that there is a linear $DPL(n,d)$ code if and only if
there is a lattice tiling of $\mathbb{Z}^{n}$ by a fixed double Lee sphere
$DS_{n,\frac{d-2}{2}}$.

######  Theorem 2.3.

[12] Let $d$ be an even integer and $C$ be a linear $DPL(n,d)$ in
$\mathbb{Z}^{n}$. Let $W$ be a double Lee sphere $DS_{n,r}$ with
$r=\frac{d-2}{2}$. Then $\mathcal{T}=\\{W+c:c\in C\\}$ is a lattice tiling of
$\mathbb{Z}^{n}$ by double Lee sphere $W$.

The following theorem can be found in [12], which establishes the connection
between lattice tilings of $\mathbb{Z}^{n}$ and finite abelian groups.

######  Theorem 2.4.

[12] Let $V$ be a subset of $\mathbb{Z}^{n}$. Then there is a lattice tiling
$\mathcal{T}$ of $\mathbb{Z}^{n}$ by $V$ if and only if there are both an
abelian group $G$ of order $|V|$ and a homomorphism
$\phi:\mathbb{Z}^{n}\rightarrow G$ so that the restriction of $\phi$ to $V$ is
a bijection.

The following lemma can be found in [28].

######  Lemma 2.5.

[28, Theorem 3.19] If a finite abelian group $G$ is a direct sum of subgroups
$H,K$ of relatively prime orders and $G=A+B$ is a factorization, where
$|A|=|H|$, $|B|=|K|$, then $G=H+B=A+K$.

Now we translate the existence of linear $DPL(n,6)$ codes into group ring
equations.

######  Theorem 2.6.

Let $n\geq 3$, then there exists a linear $DPL(n,6)$ code if and only if there
exists a finite abelian group $H$ of order $2n^{2}+1$ and $T\subseteq H$
satisfying

  1. (1)

$|T|=2n$,

  2. (2)

$T=T^{(-1)}$,

  3. (3)

$T^{2}=2H-T^{(2)}+(2n-2)e$.

###### Proof.

Let $e_{i}$, $i=1,2,\dots,n$, be a fixed orthonormal basis of
$\mathbb{Z}^{n}$. By Theorem 2.4, there exists a linear $DPL(n,6)$ code if and
only if there are both an abelian group $G$ (written multiplicatively) of
order $4n^{2}+2$ and a homomorphism $\phi:\mathbb{Z}^{n}\rightarrow G$ such
that the restriction of $\phi$ to $DS_{n,2}(0,e_{1})$ is a bijection. Since
the homomorphism $\phi$ is determined by the values $\phi(e_{i})$,
$i=1,\dots,n$, then there exists a linear $DPL(n,6)$ code if and only if there
exists an $n$-subset $\\{a_{1},a_{2},\dots,a_{n}\\}\subset G$ (let
$\phi(e_{i})=a_{i}$) such that

$\displaystyle G=$ $\displaystyle\\{e,a_{1}^{\pm 1},a_{1}^{\pm
2},a_{1}^{3}\\}\cup\\{a_{i}^{\pm 1},a_{1}^{\pm 1}a_{i}^{\pm
1},a_{1}^{2}a_{i}^{\pm 1},a_{i}^{\pm 2},a_{1}a_{i}^{\pm 2}:\ 2\leq i\leq n\\}$
$\displaystyle\cup\\{a_{i}^{\pm 1}a_{j}^{\pm 1},a_{1}a_{i}^{\pm 1}a_{j}^{\pm
1}:\ 2\leq i<j\leq n\\}.$

In the language of group ring, the above equation can be written as

$\displaystyle G=$ $\displaystyle
e+a_{1}+a_{1}^{2}+a_{1}^{-1}+a_{1}^{-2}+a_{1}^{3}+(e+a_{1}+a_{1}^{-1}+a_{1}^{2})\sum_{i=2}^{n}(a_{i}+a_{i}^{-1})+(e+a_{1})\sum_{i=2}^{n}(a_{i}^{2}+a_{i}^{-2})$
$\displaystyle+(e+a_{1})\sum_{2\leq i<j\leq
n}(a_{i}+a_{i}^{-1})(a_{j}+a_{j}^{-1})$ $\displaystyle=$
$\displaystyle(e+a_{1})(e+a_{1}^{2}+a_{1}^{-2}+(a_{1}+a_{1}^{-1})\sum_{i=2}^{n}(a_{i}+a_{i}^{-1})+\sum_{i=2}^{n}(a_{i}^{2}+a_{i}^{-2})+\sum_{2\leq
i<j\leq n}(a_{i}+a_{i}^{-1})(a_{j}+a_{j}^{-1}))$ $\displaystyle=$
$\displaystyle(e+a_{1})(e+\sum_{i=1}^{n}(a_{i}^{2}+a_{i}^{-2})+\sum_{1\leq
i<j\leq n}(a_{i}+a_{i}^{-1})(a_{j}+a_{j}^{-1})).$

Since $|G|=4n^{2}+2$ and $\gcd(2,2n^{2}+1)=1$, then $\mathbb{Z}_{2}$ is a
subgroup of $G$. Let $H=G/\mathbb{Z}_{2}$ and $\varphi:G\rightarrow
G/\mathbb{Z}_{2}$ be the natural homomorphism, then $|H|=2n^{2}+1$. By Lemma
2.5, we have

$\varphi(e)+\sum_{i=1}^{n}(\varphi(a_{i})^{2}+\varphi(a_{i})^{-2})+\sum_{1\leq
i<j\leq
n}(\varphi(a_{i})+\varphi(a_{i})^{-1})(\varphi(a_{j})+\varphi(a_{j})^{-1})=H.$

Let $T=\sum_{i=1}^{n}(\varphi(a_{i})+\varphi(a_{i})^{-1})$, then we can
compute to get that

$\displaystyle T^{2}=$
$\displaystyle(\sum_{i=1}^{n}(\varphi(a_{i})+\varphi(a_{i})^{-1}))^{2}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{n}(\varphi(a_{i})^{2}+\varphi(a_{i})^{-2})+2\sum_{1\leq
i<j\leq
n}(\varphi(a_{i})+\varphi(a_{i})^{-1})(\varphi(a_{j})+\varphi(a_{j})^{-1})+2n\varphi(e)$
$\displaystyle=$ $\displaystyle 2H-T^{(2)}+(2n-2)\varphi(e).\qed$

######  Lemma 2.7.

Let $H$ be a finite abelian group of order $2n^{2}+1$ and $T\subset H$
satisfying conditions in Theorem 2.6, then for any nontrivial character
$\chi\in\widehat{H}$, $\chi(T)\neq 0$.

###### Proof.

If $\chi(T)=0$, by Theorem 2.6, we have $\chi(T^{(2)})=2n-2$. This is
impossible since $|T^{(2)}|=2n$ and $\gcd(2,|H|)=1$. ∎

##  3 Proof of Theorem 1.4

In this section, we will give an explicit construction of linear $DPL(11,6)$
code and prove that for any $n\geq 4$, $n\neq 11$, there does not exist any
subset $T$ in a finite abelian group $H$ satisfying conditions in Theorem 2.6.

We will first study $T^{(2)}T$, by modulo 3, we can get some restrictions on
the coefficients of elements of $T^{(2)}T$. This can solve the cases $n\equiv
1\pmod{3}$ and $n\equiv 2\pmod{3}$ except for $n=5,8,11$. However, we cannot
get a contradiction when $n\equiv 0\pmod{3}$. Hence we consider
$TT^{(4)}\pmod{5}$ and $TT^{(5)}\pmod{5}$. Small dimensions will be solved in
the last subsection.

Let $n\geq 3$ be an integer. Suppose that $H$ is a finite abelian group with
order $2n^{2}+1$, and $T\subset H$ satisfying conditions in Theorem 2.6. We
write $T$ as $T=\sum_{i=1}^{n}(a_{i}+a_{i}^{-1})$, then

$\displaystyle H=e+\sum_{i=1}^{n}(a_{i}^{2}+a_{i}^{-2})+\sum_{1\leq i<j\leq
n}(a_{i}+a_{i}^{-1})(a_{j}+a_{j}^{-1}).$ (1)

We first prove some lemmas.

######  Lemma 3.1.

$T\cap T^{(3)}=\emptyset$.

###### Proof.

If there exist $a_{i},a_{j}\in T$ with $j\neq i$ such that $a_{i}=a_{j}^{3}\in
T\cap T^{(3)}$, then $a_{j}^{2}=a_{i}a_{j}^{-1}$. By Equation (1), it can be
seen that $a_{j}^{2}$ appears twice in $H$, which is a contradiction.

If there exists $a_{i}\in T$ such that $a_{i}=a_{i}^{3}\in T\cap T^{(3)}$,
then $a_{i}^{2}=e$. Since $\gcd(2,|H|)=1$, then $a_{i}=e$, which contradicts
to $e\notin T$.

If there exists $a_{i}\in T$ such that $a_{i}=a_{i}^{-3}\in T\cap T^{(3)}$,
then $a_{i}^{4}=e$. Similarly as above, we have $a_{i}=e$, which is also a
contradiction. ∎

######  Lemma 3.2.

For any $t\neq e$, we have

$|\\{(t_{1},t_{2})\in T\times T:t_{1}t_{2}=t\\}|=\begin{cases}1,&\mbox{if
}t\in T^{(2)};\\\ 2,&\mbox{if }t\notin T^{(2)}.\end{cases}$

###### Proof.

The proof is directly from Condition (3) of Theorem 2.6. ∎

Since $T^{2}=2H-T^{(2)}+(2n-2)e$, then

$\displaystyle TT^{(2)}=4nH+(2n-2)T-T^{3}.$ (2)

Writing $TT^{(2)}$ as

$\displaystyle TT^{(2)}=\sum_{i=0}^{M}iX_{i},$ (3)

where $X_{i}$ $(i=0,1,\dots,M)$ form a partition of group $H$, i.e.,

$\displaystyle H=\sum_{i=0}^{M}X_{i}.$ (4)

Then we have the following lemma.

######  Lemma 3.3.

  1. (1)

$\sum_{i=1}^{M}i|X_{i}|=4n^{2}$,

  2. (2)

$\sum_{i=0}^{M}|X_{i}|=2n^{2}+1$,

  3. (3)

$\sum_{i=1}^{M}|X_{i}|=4n-\beta+\sum_{i\geq 3}\frac{(i-1)(i-2)}{2}|X_{i}|$,
where $2\beta=|T\cap T^{(2)}|$.

###### Proof.

The first two equations are directly from Equations (3) and (4). Now we count
the size of distinct elements in $T^{(2)}T$. Let
$T^{(2)}=\sum_{i=1}^{2n}b_{i}$ with $b_{i}^{-1}=b_{n+i}$ for $i=1,2,\dots,n$.
By Lemma 3.2, we have

$|b_{i}T\cap b_{j}T|=\begin{cases}1,&\mbox{if }b_{i}b_{j}^{-1}\in T^{(2)};\\\
2,&\mbox{if }b_{i}b_{j}^{-1}\notin T^{(2)}.\end{cases}$

Let $|T\cap T^{(2)}|=2\beta$ and $\alpha=|\\{(i,j):1\leq i<j\leq
2n,b_{i}b_{j}^{-1}\in T^{(2)}\\}|$. Let $N(t)=|\\{(i,j):1\leq i<j\leq
2n,b_{i}b_{j}^{-1}=t\\}|$, then $\alpha=\sum_{t\in T^{(2)}}N(t)$. Since
$\gcd(2n^{2}+1,2)=1$, then $T^{(2)}$ also satisfies conditions in Theorem 2.6.
By the definition of $b_{i}$ and Lemma 3.2, we have

$N(t)+N(t^{-1})=\begin{cases}1,&\mbox{if }t\in T^{(2)}\cap T^{(4)};\\\
2,&\mbox{if }t\in T^{(2)}\backslash T^{(4)}.\end{cases}$

Hence, $\alpha=|T^{(2)}\backslash T^{(4)}|+\frac{|T^{(2)}\cap
T^{(4)}|}{2}=|T\backslash T^{(2)}|+\frac{|T\cap T^{(2)}|}{2}=2n-\beta$.

By the inclusion-exclusion principle, we have

$\displaystyle\sum_{i=1}^{M}|X_{i}|=$ $\displaystyle|T^{(2)}T|$
$\displaystyle=$ $\displaystyle\sum_{i=1}^{2n}|b_{i}T|-\sum_{1\leq i<j\leq
2n}|b_{i}T\cap b_{j}T|+\sum_{r\geq 3}\sum_{1\leq i_{1}<\dots<i_{r}\leq
2n}(-1)^{r-1}|b_{i_{1}}T\cap\dots\cap b_{i_{r}}T|$ $\displaystyle=$
$\displaystyle 4n^{2}-\alpha-2(\binom{2n}{2}-\alpha)+\sum_{r\geq 3}\sum_{1\leq
i_{1}<\dots<i_{r}\leq 2n}(-1)^{r-1}|b_{i_{1}}T\cap\dots\cap b_{i_{r}}T|.$

Suppose that $g\in b_{i_{1}}T\cap\dots\cap b_{i_{r}}T$ for some $r\geq 3$,
then $g\in X_{i}$ for some $i\geq 3$. The contribution for $g$ in the sum
$\sum_{r\geq 3}\sum_{1\leq i_{1}<\dots<i_{r}\leq
2n}(-1)^{r-1}|b_{i_{1}}T\cap\dots\cap b_{i_{r}}T|$ is

$(-1)^{3-1}\binom{i}{3}+(-1)^{4-1}\binom{i}{4}+\cdots=\binom{i}{2}-\binom{i}{1}+\binom{i}{0}=\frac{(i-1)(i-2)}{2}.$

Hence, we have

$\displaystyle\sum_{i=1}^{M}|X_{i}|=$ $\displaystyle
4n^{2}-\alpha-2(\binom{2n}{2}-\alpha)+\sum_{r\geq 3}\sum_{1\leq
i_{1}<\dots<i_{r}\leq 2n}(-1)^{r-1}|b_{i_{1}}T\cap\dots\cap b_{i_{r}}T|$
$\displaystyle=$ $\displaystyle
4n^{2}-\alpha-2(\binom{2n}{2}-\alpha)+\sum_{i\geq
3}|X_{i}|\frac{(i-1)(i-2)}{2}$ $\displaystyle=$ $\displaystyle
4n-\beta+\sum_{i\geq 3}\frac{(i-1)(i-2)}{2}|X_{i}|.\qed$

Now we divide our discussion into three cases.

###  3.1 $n\equiv 1\pmod{3}$

######  Proposition 3.4.

Theorem 1.4 holds for $n\equiv 1\pmod{3}$.

###### Proof.

By Equation (2), we have

$TT^{(2)}\equiv H+2T^{(3)}\pmod{3}.$

Then we get

$\displaystyle\sum_{i\geq 0}|X_{3i}|=a_{1},$ $\displaystyle\sum_{i\geq
0}|X_{3i+2}|=a_{2},$ $\displaystyle\sum_{i\geq
0}|X_{3i+1}|=2n^{2}+1-a_{1}-a_{2},$

where

$\displaystyle a_{1}=|\\{h\in T^{(3)}:\ h\text{ appears }3i+1\text{ times in
}T^{(3)}\text{ for some }i\\}|,$ $\displaystyle a_{2}=|\\{h\in T^{(3)}:\
h\text{ appears }3i+2\text{ times in }T^{(3)}\text{ for some }i\\}|.$

Hence $a_{1}+a_{2}\leq 2n$. Since for any $t\in T$, $t^{3}=t\cdot t^{2}$, then
any element in $T^{(3)}$ appears at least once in $TT^{(2)}$. Note that
$\cup_{i\geq 0}X_{3i}\subseteq T^{(3)}$, then $|X_{0}|=0$. By Lemma 3.3, we
obtain

$\displaystyle 4n^{2}+4n-\beta=$
$\displaystyle\sum_{i=1}^{M}i|X_{i}|+\sum_{i=1}^{M}|X_{i}|-\sum_{i=3}^{M}\frac{(i-1)(i-2)}{2}|X_{i}|$
$\displaystyle=$ $\displaystyle
2|X_{1}|+3|X_{2}|+\sum_{i=3}^{M}\frac{5i-i^{2}}{2}|X_{i}|$ $\displaystyle\leq$
$\displaystyle 2|X_{1}|+3|X_{2}|+3|X_{3}|+2|X_{4}|$ $\displaystyle\leq$
$\displaystyle 2(2n^{2}+1-a_{1}-a_{2})+3(a_{1}+a_{2})$ $\displaystyle=$
$\displaystyle 4n^{2}+2+a_{1}+a_{2}.$

This leads to $a_{1}+a_{2}\geq 4n-\beta-2\geq 3n-2$, which is a contradiction.
∎

###  3.2 $n\equiv 2\pmod{3}$

######  Proposition 3.5.

Theorem 1.4 holds for $n\equiv 2\pmod{3}$ except for $n=5,8,11$.

###### Proof.

By Equation (2), we have

$\displaystyle TT^{(2)}\equiv 2H+2T+2T^{(3)}\pmod{3}.$ (5)

From above equation, for any $h\in H\backslash(T\cup T^{(3)})$, $h$ appears at
least twice in $TT^{(2)}$. Note that for any $t\in T$, $t=t^{-1}t^{2}$ and
$t^{3}=tt^{2}$. Hence, $|X_{0}|=0$. By Lemma 3.1 and Equation (5), we get

$\displaystyle\sum_{i\geq 1}|X_{3i}|=a_{1},$ $\displaystyle\sum_{i\geq
0}|X_{3i+1}|=2n+a_{2},$ $\displaystyle\sum_{i\geq
0}|X_{3i+2}|=2n^{2}-2n+1-a_{1}-a_{2},$

where

$\displaystyle a_{1}=|\\{h\in T^{(3)}:\ h\text{ appears }3i+2\text{ times in
}T^{(3)}\text{ for some }i\\}|,$ $\displaystyle a_{2}=|\\{h\in T^{(3)}:\
h\text{ appears }3i+1\text{ times in }T^{(3)}\text{ for some }i\\}|.$

Then $a_{1}+a_{2}\leq 2n$. By Lemma 3.3, we obtain

$\begin{split}\sum_{i=3}^{M}(i-2)|X_{i}|=&\sum_{i=1}^{M}i|X_{i}|-2\sum_{i=1}^{M}|X_{i}|+|X_{1}|\\\
=&4n^{2}-2(2n^{2}+1)+|X_{1}|\\\ =&|X_{1}|-2,\end{split}$ (6)

and

$\begin{split}2n^{2}+1-4n+\beta=&\sum_{i=3}^{M}\frac{(i-1)(i-2)}{2}|X_{i}|\\\
\leq&\frac{M-1}{2}\sum_{i=3}^{M}(i-2)|X_{i}|\\\
=&\frac{M-1}{2}(|X_{1}|-2).\end{split}$ (7)

If $s,t\in T$ such that $s=t^{2}\in T\cap T^{(2)}$, then $s^{2}=t^{4}\in
T^{(2)}$. Hence $t^{3}=t\cdot t^{2}=t^{-1}\cdot s^{2}\in TT^{(2)}$, and so
$t^{3}\notin X_{1}$. Thus $|X_{1}|\leq 4n-2\beta$. Hence,

$\displaystyle
M\geq\frac{4n^{2}-8n+2\beta+2}{|X_{1}|-2}+1\geq\frac{4n^{2}-8n+2\beta+2}{4n-2\beta-2}+1=\frac{4n^{2}-4n}{4n-2\beta-2}.$
(8)

Since $M\in\mathbb{Z}$, then $M\geq n$.

Case 1: $|X_{M}|\geq 5$.

From Equation (6), we derive that $5n-10\leq 5(M-2)\leq|X_{1}|-2\leq 4n-2$.
This is possible only for $n=5,8$.

Case 2: $|X_{M}|=4.$

From Equation (6), we derive that $4(M-2)\leq|X_{1}|-2\leq 4n-2$. Then $M\leq
n+1$. So $n\leq M\leq n+1$.

If $M=n+1$, then

$\displaystyle 2n^{2}-4n+\beta+1=$
$\displaystyle\sum_{i=3}^{n}\frac{(i-1)(i-2)}{2}|X_{i}|+4\frac{n(n-1)}{2}$
$\displaystyle=$
$\displaystyle\sum_{i=3}^{n}\frac{(i-1)(i-2)}{2}|X_{i}|+2n^{2}-2n.$

This leads to $\beta\geq 2n-1$, which is a contradiction.

If $M=n$, then we have

$\sum_{i=3}^{n-1}\frac{(i-1)(i-2)}{2}|X_{i}|=(2n^{2}-4n+\beta+1)-4\frac{(n-1)(n-2)}{2}=2n+\beta-3,$

and

$\sum_{i=3}^{n-1}(i-2)|X_{i}|=(|X_{1}|-2)-4(n-2)=|X_{1}|-4n+6\leq 6.$

Let $L$ be the maximum of $3\leq i\leq n-1$ such that $|X_{i}|\neq 0$, then
$L\leq 8$. This implies that

$2n+\beta-3=\sum_{i=3}^{n-1}\frac{(i-1)(i-2)}{2}|X_{i}|\leq\frac{L-1}{2}\sum_{i=3}^{n-1}(i-2)|X_{i}|\leq\frac{8-1}{2}6=21.$

Thus $21\geq 2n+\beta-3\geq 3n-3$. This is possible only for $n=5,8$.

Case 3: $|X_{M}|=3.$

Since $X_{M}=X_{M}^{(-1)}$, then $e\in X_{M}$. Note that $e$ appears $|T\cap
T^{(2)}|=2\beta$ times, then $M=2\beta$, and $|X_{1}|\leq 4n-M$. By Equation
(8), we have

$\displaystyle
M\geq\frac{4n^{2}-8n+2\beta+2}{|X_{1}|-2}+1\geq\frac{4n^{2}-4n}{4n-M-2}.$

This leads to $M^{2}-(4n-2)M+4n^{2}-4n\leq 0$, so $2n-2\leq M\leq 2n$, which
contradicts to $3(M-2)\leq|X_{1}|-2$.

Case 4: $|X_{M}|=2.$

If $X_{M}\cap T^{(3)}=\emptyset$, suppose that
$t=u_{1}v_{1}^{2}=\cdots=u_{M}v_{M}^{2}\in X_{M}$, where $u_{j},v_{j}\in T$.
By Lemma 3.2, $u_{j},v_{j}$ ($j\in[1,M]$) are pairwise distinct. Then $M\leq
n$. Combining with Equation (8), we have $M=n$ and $\beta=1$, $|X_{1}|=4n-2$.
We obtain

$\displaystyle\sum_{i=3}^{n-1}|X_{i}|(i-2)=2n,$
$\displaystyle\sum_{i=3}^{n-1}|X_{i}|\frac{(i-1)(i-2)}{2}=n^{2}-n.$

This implies that

$\displaystyle
n^{2}-n\leq\frac{n-2}{2}\sum_{i=3}^{n-1}|X_{i}|(i-2)\leq(n-2)n,$

which is a contradiction. Therefore $X_{M}\subset T^{(3)}$.

Suppose that
$t_{1}^{3}=\cdots=t_{s}^{3}=u_{1}v_{1}^{2}=\cdots=u_{r}v_{r}^{2}\in X_{M}$,
where $t_{i},u_{j},v_{j}\in T$, $s\geq 1$ and $s+r=M$. By Lemma 3.2,
$t_{i},u_{j},v_{j}$ ($i\in[1,s],j\in[1,r]$) are pairwise distinct. Then we
have $s+2r\leq 2n$. Since $t_{i}^{3},t_{i}^{-3}\notin X_{1}$ for $i\in[1,s]$,
then $|X_{1}|\leq 4n-2s$. By Equation (8), we have

$\displaystyle
M\geq\frac{4n^{2}-8n+2\beta+2}{|X_{1}|-2}+1\geq\frac{4n^{2}-8n+4}{|X_{1}|-2}+1.$

If $|X_{1}|\leq 4n-2s-2$, then we can get $M\geq n+\frac{s+1}{2}$. This leads
to $s+2r\geq 2n+1$, which is a contradiction. Note that $e\notin X_{1}$ and
$X_{1}^{(-1)}=X_{1}$, then $|X_{1}|$ is even. So $|X_{1}|=4n-2s$ and
$T^{(3)}\subset(X_{1}\cup X_{M})$. By Equation (8) again, we obtain

$\displaystyle
M\geq\frac{4n^{2}-8n+4}{4n-2s-2}+1=n+\frac{s-1}{2}+\frac{s^{2}-2s+1}{4n-2s-2}.$

This leads to $M\geq n+\frac{s}{2}.$ Recall that $M=r+s$, $s+2r\leq 2n$, we
obtain $s$ is even and $M=n+\frac{s}{2}$. By Equation (6), we can get that

$2(M-2)\leq|X_{1}|-2,$

which leads to $s\leq\frac{2n+2}{3}$. If $s=\frac{2n+2}{3}$, by Equation (6),
we have $|X_{i}|=0$ for all $3\leq i\leq M$. By Lemma 3.3, we get

$2n^{2}+1-4n+\beta=(M-1)(M-2)=(n+\frac{n+1}{3}-1)(n+\frac{n+1}{3}-2),$

which is impossible. Hence $s<\frac{2n+2}{3}$, and there exists $i\in[3,M-1]$
such that $|X_{i}|\neq 0$. Let $L$ be the maximum of $i\in[3,M-1]$ with
$|X_{i}|\neq 0$, then $X_{L}\cap T^{(3)}=\emptyset$ and $L\leq n$. By
Equations (6) and (7), we have

$\displaystyle\sum_{i=3}^{L}(i-2)|X_{i}|=(|X_{1}|-2)-2(M-2)=4n-2s-2-2n-s+4=2n-3s+2,$
(9)

and

$\begin{split}\sum_{i=3}^{L}\frac{(i-1)(i-2)}{2}|X_{i}|=&(2n^{2}+1-4n+\beta)-2\frac{(M-1)(M-2)}{2}\\\
=&n^{2}-(1+s)n-\frac{s^{2}}{4}+\frac{3s}{2}+\beta-1\\\
\geq&n^{2}-(1+s)n-\frac{s^{2}}{4}+\frac{3s}{2}.\end{split}$ (10)

This implies that

$\displaystyle n^{2}-(1+s)n-\frac{s^{2}}{4}+\frac{3s}{2}\leq$
$\displaystyle\sum_{i=3}^{L}\frac{(i-1)(i-2)}{2}|X_{i}|$ $\displaystyle\leq$
$\displaystyle\frac{L-1}{2}\sum_{i=3}^{L}(i-2)|X_{i}|$ $\displaystyle\leq$
$\displaystyle\frac{n-1}{2}(2n-3s+2),$

which leads to $s^{2}-2ns+4n-4\geq 0$. Thus $s\leq 2$, and so $s=2$ and $L=n$.
Note that $|X_{1}|=4n-4\leq 4n-2\beta$, then $\beta\leq 2$. Hence $e\notin
X_{L}$. Since $X_{L}^{(-1)}=X_{L}$, then $|X_{L}|\geq 2$. By Equation (9), we
have $|X_{L}|=2$.

Now we consider the elements in $X_{L}=X_{n}$ and $X_{M}=X_{n+1}$. Suppose
that $t_{1}^{3}=t_{2}^{3}=u_{1}v_{1}^{2}=\cdots=u_{n-1}v_{n-1}^{2}\in X_{n+1}$
and $a_{1}b_{1}^{2}=\cdots=a_{n}b_{n}^{2}\in X_{n}$, where
$t_{i},u_{j},v_{j}\in T$ ($i\in[1,2],j\in[1,n-1]$) are pairwise distinct and
$a_{i},b_{i}\in T$ ($i\in[1,n]$) are pairwise distinct.

If $\\{b_{i}:i\in[1,n]\\}\cap\\{b_{i}^{-1}:i\in[1,n]\\}\geq 2$, without loss
of generality, we may assume $b_{i}=b_{i+2}^{-1}$ for $i=1,2$. From
$a_{1}b_{1}^{2}=a_{2}b_{2}^{2}$ and
$a_{3}^{-1}b_{3}^{-2}=a_{4}^{-1}b_{4}^{-2}$, we have

$\displaystyle
b_{1}^{2}b_{2}^{-2}=b_{3}^{-2}b_{4}^{2}=a_{1}^{-1}a_{2}=a_{3}a_{4}^{-1}.$

By Lemma 3.2, we get $a_{1}^{-1}=a_{3}$, then
$a_{1}b_{1}^{2}=a_{3}^{-1}b_{3}^{-2}$, which contradicts to $|X_{L}|=2$. Then
we may assume that
$\\{t_{1},t_{2},v_{i}:i\in[1,n-1]\\}\cap\\{b_{i}:i\in[1,n]\\}\geq 3$
(otherwise, we replace $\\{b_{i}:i\in[1,n]\\}$ by
$\\{b_{i}^{-1}:i\in[1,n]\\}$). Without loss of generality, we may assume
$v_{i}=b_{i}$ for $i\in[1,3]$. By
$u_{1}v_{1}^{2}=u_{2}v_{2}^{2}=u_{3}v_{3}^{2}$ and
$a_{1}b_{1}^{2}=a_{2}b_{2}^{2}=a_{3}b_{3}^{2}$, we obtain

$\displaystyle
v_{1}^{2}v_{2}^{-2}=b_{1}^{2}b_{2}^{-2}=u_{1}^{-1}u_{2}=a_{1}^{-1}a_{2},$
$\displaystyle
v_{1}^{2}v_{3}^{-2}=b_{1}^{2}b_{3}^{-2}=u_{1}^{-1}u_{3}=a_{1}^{-1}a_{3}.$

By Lemma 3.2, we get $a_{1}^{-1}=u_{2}=u_{3}$, which is a contradiction.

Case 5: $|X_{M}|=1.$

For this case, we have $X_{M}=\\{e\\}$, $M$ is even and $M=2\beta$. With a
similar discussion as Case 3, we can get $2n-2\leq M\leq 2n$.

If $M=2n-2$, then $|X_{1}|\leq 4n-2\beta=2n+2$. By Equations (6) and (7), we
have

$\displaystyle\sum_{i=3}^{M-1}|X_{i}|(i-2)\leq 4,$ (11)
$\displaystyle\sum_{i=3}^{M-1}|X_{i}|\frac{(i-1)(i-2)}{2}=2n-6.$ (12)

Let $L$ be the maximum $i\in[3,M-1]$ such that $|X_{i}|\neq 0$, then
$|X_{L}|\geq 2$. By Equation (11), we have $L\leq 4$. From Equation (12), we
can get $2n-6\leq\frac{L-1}{2}4\leq 6$. This is possible only for $n=5$.

If $M=2n$, then $T=T^{(2)}$. We obtain $T^{2}=2H-T+(2n-2)e$. This means that
$T$ is a partial difference set with $v=2n^{2}+1$, $k=2n$, $\lambda=1$,
$\mu=2$ and $\Delta=8n-7$. Note that $\gcd(2n^{2}+1,8n-7)=\gcd(81,8n-7)$, by
Lemma 2.2, we have $2n^{2}+1=3^{a}$ and $8n-7=3^{b}$ for some integers $a,b$.
This is possible only for $n=11$. ∎

###  3.3 $n\equiv 0\pmod{3}$

By Equation (2), we have

$TT^{(2)}\equiv T+2T^{(3)}\pmod{3}.$

Since $\gcd(3,2n^{2}+1)=1$, then all coefficients of elements in $T^{(3)}$ is
1. By Lemma 3.1, we have

$\displaystyle\sum_{i\geq 0}|X_{3i+1}|=2n,$ $\displaystyle\sum_{i\geq
0}|X_{3i+2}|=2n,$ $\displaystyle\sum_{i\geq 0}|X_{3i}|=2n^{2}-4n+1.$

By Lemma 3.2, we obtain that $|X_{1}|=2n$, $X_{1}=T$ and $|X_{3i+1}|=0$ for
all $i\geq 1$.

######  Lemma 3.6.

$\beta=0$, i.e., $T\cap T^{(2)}=\emptyset$, and $|X_{i}|=0$ for $i\geq 5$.

###### Proof.

Note that $e\in\cup_{i\geq 0}X_{3i}$, if $\beta>0$, then $\beta\geq 3$ and
$e\in X_{2\beta}$. By Lemma 3.3, we have

$\displaystyle\beta=$ $\displaystyle(2n^{2}+1-4n+\beta)-(2n^{2}-4n+1)$
$\displaystyle=$ $\displaystyle(|X_{0}|+\sum_{i\geq
3}|X_{i}|\frac{(i-1)(i-2)}{2})-(\sum_{i\geq 0}|X_{3i}|)$ $\displaystyle=$
$\displaystyle\sum_{i\geq 1}|X_{3i+2}|\binom{3i+1}{2}+\sum_{i\geq
2}|X_{3i}|\frac{3i(3i-3)}{2}$ $\displaystyle\geq$
$\displaystyle\frac{2\beta(2\beta-3)}{2}.$

This leads to $\beta^{2}-2\beta\leq 0$, which is a contradiction. Hence
$\beta=0$. Substituting $\beta=0$ into above equation, we get $|X_{i}|=0$ for
$i\geq 5$. ∎

From above lemma, we obtain

$\displaystyle|X_{0}|+|X_{3}|=2n^{2}-4n+1,$ $\displaystyle|X_{1}|=|X_{2}|=2n,$
$\displaystyle|X_{i}|=0\text{ for all }i\geq 4.$

By Lemma 3.3, we get $|X_{0}|=\frac{2}{3}n^{2}-2n+1$,
$|X_{3}|=\frac{4}{3}n^{2}-2n$, and

$\displaystyle TT^{(2)}=T+2T^{(3)}+3X_{3}.$ (13)

In order to get a contradiction, we need to investigate $TT^{(4)}$. By Theorem
2.6, we have

$\displaystyle(T^{(2)})^{2}=$ $\displaystyle(2H+(2n-2)e-T^{2})^{2}$
$\displaystyle=$
$\displaystyle(8n^{2}+8n-4)H+(4n^{2}-8n+4)e-(4H+(4n-4)e)T^{2}+T^{4}$
$\displaystyle=$
$\displaystyle(8n^{2}+8n-4)H+(4n^{2}-8n+4)e-(4H+(4n-4)e)(2H-T^{(2)}+(2n-2)e)+T^{4}$
$\displaystyle=$
$\displaystyle(-8n^{2}+4)H+(-4n^{2}+8n-4)e+(4n-4)T^{(2)}+T^{4}.$

On the other hand, $T^{(2)}$ also satisfies conditions in Theorem 2.6, then

$(T^{(2)})^{2}=2H-T^{(4)}+(2n-2)e.$

Combining above two equations, we obtain

$T^{4}=(8n^{2}-2)H+(4n^{2}-6n+2)e-T^{(4)}-(4n-4)T^{(2)}.$

Multiplying $T$ to both sides, we can get

$\displaystyle TT^{(4)}=(16n^{3}-4n)H+(4n^{2}-6n+2)T-(4n-4)TT^{(2)}-T^{5}.$
(14)

Writing $TT^{(4)}$ as

$\displaystyle TT^{(4)}=\sum_{i=0}^{N}iY_{i},$

where $N\leq 2n$, and $Y_{i}$, $i=0,1,\dots,N$ form a partition of group $H$,
i.e.,

$\displaystyle H=\sum_{i=0}^{N}Y_{i}.$

Then we have the following lemma.

######  Lemma 3.7.

  1. (1)

$\sum_{i=0}^{N}|Y_{i}|=2n^{2}+1$,

  2. (2)

$\sum_{i=1}^{N}i|Y_{i}|=4n^{2},$

  3. (3)

$\sum_{i=1}^{N}|Y_{i}|=4n-\gamma+\sum_{i\geq 3}|Y_{i}|\frac{(i-1)(i-2)}{2}$,
where $|T\cap T^{(4)}|=2\gamma$.

###### Proof.

The proof is similar to that for Lemma 3.3. ∎

######  Corollary 3.8.

$2|Y_{1}|+3|Y_{2}|+3|Y_{3}|+2|Y_{4}|\geq 4n^{2}+3n.$

###### Proof.

By Lemma 3.7, we have

$\displaystyle 4n^{2}+4n-\gamma=$
$\displaystyle\sum_{i=1}^{N}i|Y_{i}|+\sum_{i=1}^{N}|Y_{i}|-\sum_{i\geq
3}|Y_{i}|\frac{(i-1)(i-2)}{2}$ $\displaystyle=$ $\displaystyle
2|Y_{1}|+3|Y_{2}|+3|Y_{3}|+2|Y_{4}|-\sum_{i\geq 5}|Y_{i}|\frac{i(i-5)}{2}$
$\displaystyle\leq$ $\displaystyle 2|Y_{1}|+3|Y_{2}|+3|Y_{3}|+2|Y_{4}|.$

Then the statement follows from $\gamma\leq n$. ∎

Now we divide our discussion into five cases according to the residues modulo
5.

######  Proposition 3.9.

Theorem 1.4 holds for $n\equiv 6\pmod{15}$.

###### Proof.

By Equation (14), we have

$\displaystyle TT^{(4)}\equiv 2H+4T^{(5)}\pmod{5}.$ (15)

Since $\gcd(5,2n^{2}+1)=1$, then all coefficients of $T^{(5)}$ is 1. By
Equation (15), we obtain

$\displaystyle\sum_{i\geq 0}|Y_{5i+1}|=2n,$ $\displaystyle\sum_{i\geq
0}|Y_{5i+2}|=2n^{2}-2n+1,$ $\displaystyle|Y_{i}|=0\text{ for all }i\equiv
0,3,4\pmod{5}.$

By Lemma 3.7, we can get

$\begin{split}2n-2=&\sum_{i=1}^{N}i|Y_{i}|-\sum_{i\geq
0}|Y_{5i+1}|-2\sum_{i\geq 0}|Y_{5i+2}|\\\ =&\sum_{i\geq
1}5i(|Y_{5i+1}|+|Y_{5i+2}|).\end{split}$ (16)

Consequently,

$\displaystyle 2n^{2}+1-4n+\gamma=$
$\displaystyle\sum_{i=6}^{N}|Y_{i}|\frac{(i-1)(i-2)}{2}$ $\displaystyle\leq$
$\displaystyle\frac{N-1}{2}\sum_{i=6}^{N}|Y_{i}|(i-2)$ $\displaystyle\leq$
$\displaystyle\frac{N-1}{2}(2n-2).$

This implies that $N\geq 2n-1$. From Equation (16), we have $|Y_{N}|=1$, and
so $Y_{N}=\\{e\\}$ and $N=|T\cap T^{(4)}|$ is even. Thus $N=2n$. In this case,
we have $T=T^{(4)}$ and $TT^{(4)}=T^{2}=2H-T^{(2)}+(2n-2)e$. Comparing with
Equation (15), we obtain $T^{(2)}=T^{(5)}$. Then for any $t\in T$, there
exists $s\in T$ such that $s^{2}=t^{5}=t\cdot t^{4}$. Note that $t^{4}\in T$,
by Lemma 3.2, we have $t=t^{4}=s$. Then $t^{3}=e$, and so $t=e$, which is a
contradiction. ∎

######  Proposition 3.10.

Theorem 1.4 holds for $n\equiv 9\pmod{15}$.

###### Proof.

By Equations (13) and (14), we have

$\displaystyle TT^{(4)}\equiv$ $\displaystyle
3H+2T+3TT^{(2)}+4T^{(5)}\pmod{5}$ $\displaystyle\equiv$ $\displaystyle
3H+2T+3T+T^{(3)}+4X_{3}+4T^{(5)}\pmod{5}$ $\displaystyle\equiv$ $\displaystyle
2T+4T^{(5)}+3X_{0}+T+4T^{(3)}+2X_{3}\pmod{5}$ $\displaystyle\equiv$
$\displaystyle 4T^{(5)}+3X_{0}+3T+4T^{(3)}+2X_{3}\pmod{5}.$

From above equation, we can get

$\displaystyle\sum_{i\geq 0}|Y_{5i+1}|=|T^{(5)}\cap X_{3}|,$
$\displaystyle\sum_{i\geq 0}|Y_{5i+2}|=|X_{3}\backslash T^{(5)}|+|T^{(5)}\cap
X_{0}|+|T^{(5)}\cap T|,$ $\displaystyle\sum_{i\geq
0}|Y_{5i+3}|=|X_{0}\backslash T^{(5)}|+|T\backslash T^{(5)}|+|T^{(3)}\cap
T^{(5)}|,$ $\displaystyle\sum_{i\geq 0}|Y_{5i+4}|=|T^{(3)}\backslash
T^{(5)}|.$

By Lemma 3.7, we obtain

$\displaystyle 4n^{2}=$ $\displaystyle\sum_{i=1}^{N}i|Y_{i}|$
$\displaystyle\geq$ $\displaystyle\sum_{i\geq 0}|Y_{5i+1}|+2\sum_{i\geq
0}|Y_{5i+2}|+3\sum_{i\geq 0}|Y_{5i+3}|+4\sum_{i\geq 0}|Y_{5i+4}|$
$\displaystyle=$ $\displaystyle|T^{(5)}\cap X_{3}|+2(|X_{3}\backslash
T^{(5)}|+|T^{(5)}\cap X_{0}|+|T^{(5)}\cap T|)+3(|X_{0}\backslash
T^{(5)}|+|T\backslash T^{(5)}|+|T^{(3)}\cap T^{(5)}|)$
$\displaystyle+4|T^{(3)}\backslash T^{(5)}|$ $\displaystyle\geq$
$\displaystyle 3(\frac{2}{3}n^{2}-2n+1)+3\times 2n+4\times
2n+2(\frac{4}{3}n^{2}-2n)-2n$ $\displaystyle=$
$\displaystyle\frac{14}{3}n^{2}+2n+3,$

which is impossible. ∎

######  Proposition 3.11.

Theorem 1.4 holds for $n\equiv 3\pmod{15}$ except for $n=3$.

###### Proof.

By Equations (13) and (14), we have

$\displaystyle TT^{(4)}\equiv$ $\displaystyle 2TT^{(2)}+4T^{(5)}\pmod{5}$
$\displaystyle\equiv$ $\displaystyle 2T+4T^{(3)}+X_{3}+4T^{(5)}\pmod{5}.$

From above equation, we can get

$\displaystyle\sum_{i\geq 0}|Y_{5i+1}|=|X_{3}\backslash T^{(5)}|+|T\cap
T^{(5)}|,$ $\displaystyle\sum_{i\geq 0}|Y_{5i+2}|=|T\backslash T^{(5)}|,$
$\displaystyle\sum_{i\geq 0}|Y_{5i+3}|=|T^{(3)}\cap T^{(5)}|,$
$\displaystyle\sum_{i\geq 0}|Y_{5i+4}|=|T^{(3)}\backslash
T^{(5)}|+|T^{(5)}\cap X_{0}|.$

By Corollary 3.8, we obtain

$\displaystyle 4n^{2}+3n\leq$ $\displaystyle
2|Y_{1}|+3|Y_{2}|+3|Y_{3}|+2|Y_{4}|$ $\displaystyle\leq$ $\displaystyle
2(|X_{3}\backslash T^{(5)}|+|T\cap T^{(5)}|+|T^{(3)}\backslash
T^{(5)}|+|T^{(5)}\cap X_{0}|)+3(|T\backslash T^{(5)}|+|T^{(3)}\cap T^{(5)}|)$
$\displaystyle\leq$ $\displaystyle 2(\frac{4}{3}n^{2}-2n+2n+2n)+3\times 2n.$

This leads to $\frac{4}{3}n^{2}-7n\leq 0$ and so $n\leq 5$. Hence $n=3$. ∎

######  Proposition 3.12.

Theorem 1.4 holds for $n\equiv 12\pmod{15}$.

###### Proof.

By Equations (13) and (14), we have

$\begin{split}TT^{(4)}\equiv&T+TT^{(2)}+4T^{(5)}\pmod{5}\\\
\equiv&2T+2T^{(3)}+3X_{3}+4T^{(5)}\pmod{5}.\end{split}$ (17)

From above equation, we can get

$\displaystyle\sum_{i\geq 0}|Y_{5i+1}|=|T\cap T^{(5)}|+|T^{(3)}\cap T^{(5)}|,$
$\displaystyle\sum_{i\geq 0}|Y_{5i+2}|=|T\backslash T^{(5)}|+|T^{3}\backslash
T^{(5)}|+|X_{3}\cap T^{(5)}|,$ $\displaystyle\sum_{i\geq
0}|Y_{5i+3}|=|X_{3}\backslash T^{(5)}|,$ $\displaystyle\sum_{i\geq
0}|Y_{5i+4}|=|X_{0}\cap T^{(5)}|.$

By Lemma 3.7, we obtain

$\displaystyle 4n^{2}=$ $\displaystyle\sum_{i=1}^{N}i|Y_{i}|$
$\displaystyle\geq$ $\displaystyle\sum_{i\geq 0}|Y_{5i+1}|+2\sum_{i\geq
0}|Y_{5i+2}|+3\sum_{i\geq 0}|Y_{5i+3}|+4\sum_{i\geq 0}|Y_{5i+4}|$
$\displaystyle=$ $\displaystyle(|T\cap T^{(5)}|+|T^{(3)}\cap
T^{(5)}|)+2(|T\backslash T^{(5)}|+|T^{3}\backslash T^{(5)}|+|X_{3}\cap
T^{(5)}|)+3|X_{3}\backslash T^{(5)}|+4|X_{0}\cap T^{(5)}|$ $\displaystyle\geq$
$\displaystyle 3(\frac{4}{3}n^{2}-2n)+2\times 2n+2\times 2n-2n$
$\displaystyle=$ $\displaystyle 4n^{2}.$

This means that $T^{(5)}\subset(T\cup T^{(3)}\cup X_{3})$ and

$\displaystyle|Y_{1}|=a_{1},$ $\displaystyle|Y_{2}|=4n-a_{1}+a_{2},$
$\displaystyle|Y_{3}|=\frac{4}{3}n^{2}-2n-a_{2},$
$\displaystyle|Y_{i}|=0\text{ for all }i\geq 4,$

where $a_{1}=|T^{(5)}\cap(T\cup T^{(3)})|$, $a_{2}=|T^{(5)}\cap X_{3}|$ and
$a_{1}+a_{2}=2n$. Since $e\in X_{0}$, then $T\cap T^{(4)}=\emptyset$. By Lemma
3.7, we have $|Y_{1}|+|Y_{2}|=4n$. So $a_{2}=0$ and $a_{1}=2n$. Thus
$T^{(5)}\subset(T\cup T^{(3)})$.

If there exist $s,t\in T$ such that $s^{3}=t^{5}\in(T^{(5)}\cap T^{(3)})$,
then $s^{3}=t^{5}=s^{-1}\cdot s^{4}=t\cdot t^{4}$. So $s^{3}=t^{5}$ appears at
least twice in $TT^{(4)}$, which is a contradiction. Hence $T=T^{(5)}$ and

$TT^{(4)}=T+2T^{(3)}+3X_{3}.$

Comparing with Equation (13), we have $TT^{(2)}=TT^{(4)}$, i.e.,
$T(T^{(2)}-T^{(4)})=0$. Then for any nontrivial character
$\chi\in\widehat{H}$, we have $\chi(T)(\chi(T^{(2)})-\chi(T^{(4)}))=0$. By
Lemma 2.7, $\chi(T)\neq 0$, then $\chi(T^{(2)})-\chi(T^{(4)})=0$ for any
$\chi\in\widehat{H}$. Hence $T^{(2)}=T^{(4)}$, which contradicts to Lemma 3.6.
∎

######  Proposition 3.13.

Theorem 1.4 holds for $n\equiv 0\pmod{15}$.

###### Proof.

By Equations (13) and (14), we have

$\displaystyle T^{6}=$
$\displaystyle(32n^{4}-8n^{2})H+(4n^{2}-6n+2)T^{2}-(4n-4)T^{2}T^{(2)}-T^{2}T^{(4)}$
$\displaystyle=$
$\displaystyle(32n^{4}-8n^{2})H+(4n^{2}-6n+2)(2H-T^{(2)}+(2n-2)e)-(4n-4)(2H-T^{(2)}+(2n-2)e)T^{(2)}$
$\displaystyle-(2H-T^{(2)}+(2n-2)e)T^{(4)}$ $\displaystyle=$
$\displaystyle(32n^{4}-16n^{2}+4)H-(12n^{2}-22n+10)T^{(2)}+(4n-4)(T^{(2)})^{2}+T^{(2)}T^{(4)}-(2n-2)T^{(4)}+$
$\displaystyle(8n^{3}-20n^{2}+16n-4)e$ $\displaystyle=$
$\displaystyle(32n^{4}-16n^{2}+4)H-(12n^{2}-22n+10)T^{(2)}+(4n-4)(2H-T^{(4)}+(2n-2)e)+$
$\displaystyle T^{(2)}T^{(4)}-(2n-2)T^{(4)}+(8n^{3}-20n^{2}+16n-4)e$
$\displaystyle=$
$\displaystyle(32n^{4}-16n^{2}+8n-4)H-(12n^{2}-22n+10)T^{(2)}+T^{(2)}T^{(4)}-(6n-6)T^{(4)}$
$\displaystyle+(8n^{3}-12n^{2}+4)e.$

This implies that

$\begin{split}TT^{(5)}\equiv&H+T^{(2)}T^{(4)}+T^{(4)}+4e\pmod{5}\\\
\equiv&H+T^{(2)}+2T^{(6)}+3X_{3}^{(2)}+T^{(4)}+4e\pmod{5}\\\
\equiv&X_{0}^{(2)}+2T^{(2)}+3T^{(6)}+4X_{3}^{(2)}+T^{(4)}+4e\pmod{5}\\\
\equiv&(X_{0}^{(2)}\backslash\\{e\\})+2T^{(2)}+3T^{(6)}+4X_{3}^{(2)}+T^{(4)}\pmod{5}.\end{split}$
(18)

Writing $TT^{(5)}=\sum_{i=0}^{L}iZ_{i}$, where $Z_{i}$, $i=0,1,\dots,L$ form a
partition of group $H$. Then

$4n^{2}=\sum_{i=1}^{L}i|Z_{i}|.$

From Equation (18), we can get

$\displaystyle\sum_{i\geq 0}|Z_{5i+1}|=|X_{0}^{(2)}\backslash(\\{e\\}\cup
T^{(4)})|,$ $\displaystyle\sum_{i\geq 0}|Z_{5i+2}|=|T^{(2)}|+|X_{0}^{(2)}\cap
T^{(4)}|,$ $\displaystyle\sum_{i\geq 0}|Z_{5i+3}|=|T^{(6)}\backslash
T^{(4)}|,$ $\displaystyle\sum_{i\geq 0}|Z_{5i+4}|=|X_{3}^{(2)}\backslash
T^{(4)}|+|T^{(6)}\cap T^{(4)}|.$

Hence we obtain

$\displaystyle 4n^{2}=$ $\displaystyle\sum_{i=1}^{L}i|Z_{i}|$
$\displaystyle\geq$ $\displaystyle\sum_{i\geq 0}|Z_{5i+1}|+2\sum_{i\geq
0}|Z_{5i+2}|+3\sum_{i\geq 0}|Z_{5i+3}|+4\sum_{i\geq 0}|Z_{5i+4}|$
$\displaystyle=$ $\displaystyle|X_{0}^{(2)}\backslash(\\{e\\}\cup
T^{(4)})|+2(|T^{(2)}|+|X_{0}^{(2)}\cap T^{(4)}|)+3|T^{(6)}\backslash
T^{(4)}|+4(|X_{3}^{(2)}\backslash T^{(4)}|+|T^{(6)}\cap T^{(4)}|)$
$\displaystyle\geq$
$\displaystyle\frac{2}{3}n^{2}-2n+4n+6n+4(\frac{4}{3}n^{2}-2n)-8n$
$\displaystyle=$ $\displaystyle 6n^{2}-8n.$

This leads to $2n^{2}-8n\leq 0$, and so $n\leq 4$, which is impossible. ∎

###  3.4 Some sporadic cases

For $n=3$, it has been pointed out in [5] that, there exists a linear
$DPL(3,6)$ code. For $n=11$, we have the following result.

######  Proposition 3.14.

There exists a linear $DPL(11,6)$ code.

###### Proof.

Let $H=(\mathbb{F}_{3^{5}},+)$, and $g$ be a primitive element of finite field
$\mathbb{F}_{3^{5}}$. Let $T=\\{g^{11i}:i\in[0,21]\\}\subset H$, then
$T=T^{(-1)}$, $T=T^{(2)}$ and $T^{2}=2H-T+(2n-2)e$. By Theorem 2.6, there
exists a linear $DPL(11,6)$ code. ∎

For $n=5$ or 8, the nonexistence of $DPL(n,6)$ code follows from following
proposition.

######  Proposition 3.15.

If $n\equiv 5,8\pmod{9}$ and $4n^{2}+2$ is a squarefree integer, then there
does not exist a linear $DPL(n,6)$ code.

###### Proof.

Let $e_{i}$, $i=1,2,\dots,n$, be fixed orthonormal basis of $\mathbb{Z}^{n}$.
By Theorem 2.4, there exists a linear $DPL(n,6)$ code if and only if there is
a homomorphism $\phi:\mathbb{Z}^{n}\rightarrow\mathbb{Z}_{4n^{2}+2}$ (the
group $\mathbb{Z}_{4n^{2}+2}$ is written additively) such that the restriction
of $\phi$ to $DS_{n,2}(0,e_{1})$ is a bijection. Since the homomorphism $\phi$
is determined by the values $\phi(e_{i})$, $i=1,\dots,n$, then there exists a
linear $DPL(n,6)$ code if and only if there exists an $n$-subset
$\\{a_{1},a_{2},\dots,a_{n}\\}\subset\mathbb{Z}_{4n^{2}+2}$ (let
$\phi(e_{i})=a_{i}$) such that

$\displaystyle\mathbb{Z}_{4n^{2}+2}=$ $\displaystyle\\{0,\pm a_{1},\pm
2a_{1},3a_{1}\\}\cup\\{\pm a_{i},\pm a_{1}\pm a_{i},2a_{1}\pm a_{i},\pm
2a_{i},a_{1}\pm 2a_{i}:\ 2\leq i\leq n\\}$ $\displaystyle\cup\\{\pm a_{i}\pm
a_{j},a_{1}\pm a_{i}\pm a_{j}:\ 2\leq i<j\leq n\\}.$

Then we have

$\begin{split}&(\pm a_{1})^{2}+(\pm
2a_{1})^{2}+(3a_{1})^{2}+\sum_{i=2}^{n}((\pm a_{i})^{2}+(\pm a_{1}\pm
a_{i})^{2}+(2a_{1}\pm a_{i})^{2}+(\pm 2a_{i})^{2}\\\ &+(a_{1}\pm
2a_{i})^{2})+\sum_{2\leq i<j\leq n}((\pm a_{i}\pm a_{j})^{2}+(a_{1}\pm
a_{i}\pm
a_{j})^{2})\equiv\sum_{i=1}^{4n^{2}+1}i^{2}\pmod{4n^{2}+2}.\end{split}$ (19)

The left hand side of Equation (19) can be computed as

$\displaystyle(\pm a_{1})^{2}+(\pm
2a_{1})^{2}+(3a_{1})^{2}+\sum_{i=2}^{n}((\pm a_{i})^{2}+(\pm a_{1}\pm
a_{i})^{2}+(2a_{1}\pm a_{i})^{2}+(\pm 2a_{i})^{2}+(a_{1}\pm 2a_{i})^{2})$
$\displaystyle+\sum_{2\leq i<j\leq n}((\pm a_{i}\pm a_{j})^{2}+(a_{1}\pm
a_{i}\pm a_{j})^{2})$ $\displaystyle=$
$\displaystyle(2n^{2}+8n+9)a_{1}^{2}+(8n+8)\sum_{i=2}^{n}a_{i}^{2}$
$\displaystyle\equiv$ $\displaystyle 0\pmod{3}.$

For the right hand side of Equation (19), we have

$\sum_{i=1}^{4n^{2}+1}i^{2}=\frac{(4n^{2}+1)(4n^{2}+2)(8n^{2}+3)}{6}\not\equiv
0\pmod{3}.$

This contradicts to $4n^{2}+2\equiv 0\pmod{3}$. ∎

Theorem 1.4 is a combination of Propositions 3.4, 3.5, and 3.9—3.15.

## Acknowledgements

Gennian Ge was partially supported by the National Key Research and
Development Program of China under Grant 2020YFA0712100 and Grant
2018YFA0704703, the National Natural Science Foundation of China under Grant
11971325 and Grant 12231014, and Beijing Scholars Program.

## References

  * [1] R. Ahlswede, H. K. Audinian, and L. H. Khachatrian.  On perfect codes and related concepts.  Des. Codes Cryptogr., 22:221–237, 2001.
  * [2] R. Ahlswede and V. Blinovsky.  Lectures on Advances in Combinatorics.  Springer-Verlag, New York, 2008.
  * [3] M. Blaum, J. Bruck, and A. Vardy.  Interleaving schemes for multidimensional cluster errors.  IEEE Trans. Inform. Theory, 44(2):730–743, 1998.
  * [4] T. Etzion.  Tilings with generalized Lee spheres.  In J.-S. No, H.-Y. Song, T. Helleseth, and P. V. Kumar, editors, Mathematical Properties of Sequences and Other Combinatorial Structures, pages 181–198. Springer US, Boston, MA, 2003.
  * [5] T. Etzion.  Product constructions for perfect Lee codes.  IEEE Trans. Inform. Theory, 57(11):7473–7481, 2011.
  * [6] T. Etzion.  Perfect codes and related structure.  World Scientific, 2022.
  * [7] T. Etzion and E. Yaakobi.  Error-correction of multidimensional bursts.  IEEE Trans. Inform. Theory, 55(3):961–976, 2009.
  * [8] S. W. Golomb and L. R. Welch.  Perfect codes in the Lee metric and the packing of polynomials.  SIAM J. Appl. Math., 18(2):302–317, 1970.
  * [9] S. Gravier, M. Mollard, and C. Payan.  On the non-existence of $3$-dimensional tiling in the Lee metric.  European J. Combin., 19(5):567–572, 1998.
  * [10] P. Horak.  On perfect Lee codes.  Discrete Math., 309(18):5551–5561, 2009.
  * [11] P. Horak.  Tilings in Lee metric.  European J. Combin., 30(2):480–489, 2009.
  * [12] P. Horak and B. F. AlBdaiwi.  Diameter perfect Lee codes.  IEEE Trans. Inform. Theory, 58(8):5490–5499, 2012.
  * [13] P. Horak and D. Kim.  50 years of the Golomb-Welch conjecture.  IEEE Trans. Inform. Theory, 64(4):3048–3061, 2018.
  * [14] A. Jiang, M. Schwartz, and J. Bruck.  Correcting charge-constrained errors in the rank-modulation scheme.  IEEE Trans. Inform. Theory, 56(5):2112–2120, 2010.
  * [15] D. Kim.  Nonexistence of perfect $2$-error correcting Lee codes in certain dimensions.  European J. Combin., 63:1–5, 2017.
  * [16] C. Y. Lee.  Some properties of nonbinary error-correcting codes.  IRE Trans. Inform. Theory, IT-4:77–82, 1958.
  * [17] T. Lepistö.  A modification of the Elias-bound and nonexistence theorems for perfect codes in the Lee-metric.  Inf. Control, 49(2):109–124, 1981.
  * [18] K. H. Leung and Y. Zhou.  No lattice tiling of $\mathbb{Z}^{n}$ by Lee sphere of radius 2.  J. Combin. Theory Ser. A, 171:105157, 2020.
  * [19] S. L. Ma.  Partial difference sets.  Discrete Math., 52:75–89, 1984.
  * [20] S. L. Ma.  A survey of partial difference sets.  Des. Codes Cryptogr., 4:221–261, 1994.
  * [21] K. A. Post.  Nonexistence theorems on perfect Lee codes over large alphabets.  Inf. Control, 29(4):369–380, 1975.
  * [22] A. Pott.  Finite geometry and character theory, volume 1601 of Lecture Notes in Mathematics.  Springer-Verlag, Berlin, 1995.
  * [23] C. Qureshi.  On the non-existence of linear perfect Lee codes: The Zhang-Ge condition and a new polynomial criterion.  European J. Combin., 83:103022, 2020.
  * [24] R. M. Roth and P. H. Siegel.  Lee-metric BCH codes and their application to constrained and partial-response channels.  IEEE Trans. Inform. Theory, 40(4):1083–1096, 1994.
  * [25] B. Schmidt.  Characters and cyclotomic fields in finite geometry, volume 1797 of Lecture Notes in Mathematics.  Springer-Verlag, Berlin, 2002.
  * [26] M. Schwartz.  Quasi-cross lattice tilings with applications to flash memory.  IEEE Trans. Inform. Theory, 58(4):2397–2405, 2012.
  * [27] S. Špacapan.  Nonexistence of face-to-face four-dimensional tilings in the Lee metric.  European J. Combin., 28(1):127–133, 2007.
  * [28] S. Szabó and A. D. Sands.  Factoring groups into subsets, volume 257 of Lecture Notes in Pure and Applied Mathematics.  CRC Press, Boca Raton, FL, 2009.
  * [29] W. Ulrich.  Non-binary error correction codes.  Bell Syst. Tech. J., 36:1341–1387, 1957.
  * [30] X. Xu and Y. Zhou.  On almost perfect linear Lee codes of packing radius 2.  arXiv: 2210.03361.
  * [31] T. Zhang and G. Ge.  Perfect and quasi-perfect codes under the $l_{p}$ metric.  IEEE Trans. Inform. Theory, 63(7):4325–4331, 2017.
  * [32] T. Zhang and Y. Zhou.  On the nonexistence of lattice tilings of $\mathbb{Z}^{n}$ by Lee spheres.  J. Combin. Theory Ser. A, 165:225–257, 2019.
  * [33] Z. Zhou and Y. Zhou.  Almost perfect linear Lee codes of packing radius 2 only exist for small dimensions.  arXiv: 2210.04550.