# A polynomial analogue of Berggren’s theorem on Pythagorean triples

Byungchul Cha  Department of Mathematics, 2400 W Chew st., Allentown, PA 18104
<EMAIL_ADDRESS>and  Ricardo Conceição  Department of Mathematics, 300 N
Washington St, Gettysburg, PA 17325<EMAIL_ADDRESS>
###### Abstract.

Say that $(x,y,z)$ is a positive primitive integral Pythagorean triple if
$x,y,z$ are positive integers without common factors satisfying
$x^{2}+y^{2}=z^{2}$. An old theorem of Berggren gives three integral
invertible linear transformations whose semi-group actions on $(3,4,5)$ and
$(4,3,5)$ generate all positive primitive Pythagorean triples in a unique
manner. We establish an analogue of Berggren’s theorem in the context of a
one-variable polynomial ring over a field of characteristic $\neq 2$. As its
corollaries, we obtain some structure theorems regarding the orthogonal group
with respect to the Pythagorean quadratic form over the polynomial ring.

###### 2020 Mathematics Subject Classification:

Primary: 11G35, Secondary: 11T06

##  1\. Introduction

A triple $(x,y,z)\in\mathbb{Z}^{3}$ is an _integral Pythagorean triple_ if it
satisfies

(1.1) $x^{2}+y^{2}=z^{2}.$

It is said to be _primitive_ if $\gcd(x,y,z)=1$ and _positive_ if $x,y,z>0$.

An old theorem of Berggren [Ber34], rediscovered independently first by
[Bar63] and later by several other authors111See the introduction of [Rom08]
for a more comprehensive list., says that every positive primitive integral
Pythagorean triple can be generated from the well-known integral Pythagorean
triple $(3,4,5)$ using four linear transformations, one of which is the
permutation of $x$ and $y$. More precisely, if we define

(1.2) $N_{1}=\begin{pmatrix}1&-2&2\\\ 2&-1&2\\\ 2&-2&3\end{pmatrix},\quad
N_{2}=\begin{pmatrix}1&2&2\\\ 2&1&2\\\ 2&2&3\end{pmatrix},\quad
N_{3}=\begin{pmatrix}-1&2&2\\\ -2&1&2\\\ -2&2&3\end{pmatrix}$

then

######  Theorem 1.1 (Berggren’s theorem).

Let $(x,y,z)$ be a positive primitive integral Pythagorean triple. Then there
exists a unique sequence $\\{d_{1},\dots,d_{k}\\}\in\\{1,2,3\\}^{k}$ such that

$\begin{pmatrix}x\\\ y\\\ z\end{pmatrix}=N_{d_{1}}\cdots
N_{d_{k}}\begin{pmatrix}3\\\ 4\\\ 5\end{pmatrix}\text{ or }\begin{pmatrix}x\\\
y\\\ z\end{pmatrix}=N_{d_{1}}\cdots N_{d_{k}}\begin{pmatrix}4\\\ 3\\\
5\end{pmatrix}.$

(Here, $\\{d_{1},\dots,d_{k}\\}$ is understood to be an empty sequence if
$(x,y,z)=(3,4,5)$ or $(4,3,5)$.)

Berggren’s theorem has been generalized to Pythagorean forms in more than two
variables [CA90] and certain indefinite binary quadratic forms [CNT]. In both
cases, it is shown that all primitive integral tuples are generated from a
finite set of primitive tuples and a finite number of linear transformations.
The main result of this paper, Theorem 1.2 below, is an analogue of Berggren’s
theorem for polynomial rings over a field. Similarly to the results in [CA90]
and [CNT], it describes how all primitive polynomial Pythagorean triples can
be generated from a single polynomial Pythagorean triple using linear
transformations and composition of polynomials. The remaining of this
introduction is used to make this statement more precise by finding analogues
over $K[t]$ of the notions of positive primitive integral Pythagorean triples,
the triple $(3,4,5)$ and the matrices in (1.2). We also present applications
of the polynomial version of Berggren’s Theorem to the group of linear
automorphisms of (1.1) over a polynomial ring.

Let $K$ be a field of characteristic $\neq 2$ and $K[t]$ be the ring of
polynomials over $K$ in the indeterminate $t$. A non-zero triple $(x,y,z)\in
K[t]^{3}$ satisfying (1.1) is called a _(polynomial) Pythagorean triple_. As
before, $(x,y,z)$ is said to be primitive if $\gcd(x,y,z)=1$222Recall that
$\gcd(x,y,z)$ is by definition the unique monic polynomial in $K[t]$ that
generates the smallest ideal of $K[t]$ containing $x,y,z$.. The analogue of a
positive primitive integral Pythagorean triple is a primitive Pythagorean
triple $(x,y,z)\in K[t]^{3}$ such that $\deg x<\deg y=\deg z$ and the leading
coefficients of $y$ and $z$ are the same. We call them _standard Pythagorean
triples_ or SPT in short. As in the classical case, any non-standard primitive
Pythagorean triple can be brought to a standard one by means of a $K$-linear
coordinate change (cf. Lemma 4.2). Moreover, it follows from the primality
condition that all SPT’s $(x,y,z)$ with $x=0$ are of the form $(0,c,c)$, for
some $c\in K^{*}$. Therefore, we restrict ourselves to the study of SPT’s with
$x\neq 0$.

To find an analogue to $(3,4,5)$, we observe that

$S_{t}=(2t,t^{2}-1,t^{2}+1),$

which comes from the classical rational parametrization of the unit circle,
yields an SPT of smallest height (see definition of height in §2). But,
because (1.1) is defined over $K$, new SPT’s can be created from other SPT’s
by replacing $t$ with a polynomial $f\in K[t]\backslash K$. In particular,

(1.3) $S_{f}=(2f,f^{2}-1,f^{2}+1)$

is also an SPT, which we take to be the natural analogue over $K[t]$ of the
triple $(3,4,5)$.

As for the linear transformations (1.2) appearing in Berggren’s theorem, in §2
we explain how they can be constructed from reflections on a quadratic space
defined by the quadratic form $\mathcal{Q}(x,y,z)=x^{2}+y^{2}-z^{2}$
associated to (1.1). When this construction is applied to reflections defined
by a polynomial $f\in K[t]$, we arrive at the matrix

$M_{f}=\left(\begin{array}[]{rrr}-1&2f&2f\\\ -2f&2f^{2}-1&2f^{2}\\\
-2f&2f^{2}&2f^{2}+1\end{array}\right).$

This is the final piece needed to state the following analogue of Berggren’s
theorem, which is proved in §3.

######  Theorem 1.2.

Let $Q=(x,y,z)$ be an SPT with $x\neq 0$. Then there exist $c\in K^{*}$, $f\in
K[t]\backslash K$, and a (possibly empty) sequence $\\{f_{1},\dots f_{k}\\}$
in $K[t]\backslash K$ such that

$Q^{T}=cM_{f_{1}}\cdots M_{f_{k}}S_{f}^{T}.$

Moreover, this representation of $Q$ is unique.

As consequences of this polynomial Berggren’s theorem, we obtain the following
two theorems on the orthogonal group $O_{\mathcal{Q}}(K[t])$ of the quadratic
form $\mathcal{Q}$.

######  Theorem 1.3.

The group $O_{\mathcal{Q}}(K[t])$ acts transitively on the set of all
primitive Pythagorean triples.

For each $c\in K^{*}$ and $f\in K[t]$, define

(1.4) $T_{c}=\begin{pmatrix}1&0&0\\\ 0&(c+c^{-1})/2&(c-c^{-1})/2\\\
0&(c-c^{-1})/2&(c+c^{-1})/2\\\ \end{pmatrix}$

and

$R_{f}=\left(\begin{array}[]{rrr}-1&-2f&2f\\\ -2f&-2f^{2}+1&2f^{2}\\\
-2f&-2f^{2}&2f^{2}+1\end{array}\right).$

It is straightforward to see that $T_{c}$ and $R_{f}$ preserve the form
$\mathcal{Q}(x,y,z)$.

######  Theorem 1.4.

The group $O_{\mathcal{Q}}(K[t])$ is generated by the following set:

$\\{R_{f}\mid f\in K[t]\\}\cup\left\\{P_{xy}\right\\}\cup\left\\{T_{c}\mid
c\in K^{*}\right\\}$

where $P_{xy}$ is the permutation $(x,y,z)\mapsto(y,x,z)$.

The paper is organized as follows. In §2 we present some preliminary
definitions and results that will be used in the proofs of the three theorems
above. The proof of Theorem 1.2 is given in §3, while the proofs of Theorems
1.3 and 1.4 are given in §4.

##  2\. Definitions and preliminary results

Recall that $K$ is a field of characteristic $\neq 2$. Given a non-zero
polynomial $f\in K[t]$, we denote by $\ell(f)$ the (nonzero) leading
coefficient of $f$ and $\deg(f)$ the degree of $f$. We adopt the convention
that $\deg(0)=-\infty$. For a triple $Q=(x,y,z)\in K[t]^{3}$, the _height of
$Q$_ is the integer

$h(Q)=\max\\{\deg(x),\deg(y),\deg(z)\\}.$

When $\gcd(x,y,z)=1$, we say that $Q$ is _primitive_. Given a ring $R$, recall
that $A\in\operatorname{GL}_{3}(R)$ if both $A$ and $A^{-1}$ are defined over
$R$. Below we record two properties of height and primitivity of triples that
will be useful later.

######  Lemma 2.1.

For a triple $Q=(x,y,z)\in K[t]^{3}$ and $A\in\operatorname{GL}_{3}(K[t])$,
write $\tilde{Q}^{T}=(\tilde{x},\tilde{y},\tilde{z})^{T}=AQ^{T}$. Then
$\gcd(x,y,z)=\gcd(\tilde{x},\tilde{y},\tilde{z})$. In particular, $Q$ is
primitive if and only if $\tilde{Q}$ is primitive.

###### Proof.

Write $f=\gcd(x,y,z)$ and $\tilde{f}=\gcd(\tilde{x},\tilde{y},\tilde{z})$.
Then $f$ divides any $K[t]$-linear combination of $x,y,z$. Therefore, $f$
divides each of $\tilde{x}$, $\tilde{y}$, $\tilde{z}$, thus $\tilde{f}$ as
well. Apply the same argument with $A^{-1}$ to show that $\tilde{f}$ divides
$f$. So we conclude that $f=\tilde{f}$, which clearly implies that $A$
preserves primitivity. ∎

######  Lemma 2.2.

For a triple $Q=(x,y,z)\in K[t]^{3}$ and $A\in\operatorname{GL}_{3}(K)$,

$h(Q)=h(AQ^{T}).$

###### Proof.

As before, write $Q=(x,y,z)$ and
$\tilde{Q}^{T}=(\tilde{x},\tilde{y},\tilde{z})^{T}=AQ^{T}$. Then the degree of
any $K$-linear combination of $x,y,z$ cannot exceed $h(Q)$, therefore
$h(\tilde{Q})\leq h(Q)$. Apply the same argument with $A^{-1}$, which would
give $h(Q)\leq h(\tilde{Q})$. This completes the proof. ∎

To find analogues over $K[t]$ of the matrices $N_{1},N_{2},N_{3}$ in (1.2), we
first contextualize their construction using a geometric interpretation that
first appeared in Conrad’s note [Conrad] and that was later generalized by
[CNT]. Since this construction works simultaneously for both $\mathbb{Z}$ and
$K[t]$, we briefly consider the more general framework of an integral domain
$D$ of characteristic $\neq 2$ and its fraction field $F$.

We view the quadratic form

(2.1) $\mathcal{Q}(x,y,z)=x^{2}+y^{2}-z^{2}$

associated to (1.1) as being defined over $D$. The orthogonal group
$O_{\mathcal{Q}}(D)$ of $\mathcal{Q}$ over $D$ is, by definition, the group of
matrices $A\in GL_{3}(D)$ satisfying
$\mathcal{Q}(A\mathbf{x})=\mathcal{Q}(\mathbf{x})$, for all $\mathbf{x}\in
D^{3}$.

Note that $\mathcal{Q}$ defines the bilinear pairing
$\langle,\rangle:F^{3}\times F^{3}\longrightarrow F$

$\langle\mathbf{x},\mathbf{y}\rangle=\frac{1}{2}\left(\mathcal{Q}(\mathbf{x}+\mathbf{y})-\mathcal{Q}(\mathbf{x})-\mathcal{Q}(\mathbf{y})\right),$

for $\mathbf{x},\mathbf{y}\in F^{3}$. For $\mathbf{w}\in F^{3}$ with
$\mathcal{Q}(\mathbf{w})\neq 0$, we define a _reflection_ $R_{\mathbf{w}}$
with respect to $\mathbf{w}$ to be the linear map from $F^{3}$ onto itself
given by

(2.2)
$R_{\mathbf{w}}(\mathbf{x})=\mathbf{x}-2\frac{\langle\mathbf{x},\mathbf{w}\rangle}{\mathcal{Q}(\mathbf{w})}\mathbf{w}.$

The map $R_{\mathbf{w}}$ is easily seen to have order 2 and to be an element
of $O_{\mathcal{Q}}(F)$. If $\mathbf{w}\in F^{3}$ is such that
$\mathcal{Q}(\mathbf{w})=\pm 1,\pm 2$, then $R_{\mathbf{w}}$ is actually an
element of $O_{\mathcal{Q}}(D)$.

When we specialize to the case $D=\mathbb{Z}$, $F=\mathbb{Q}$,
$\mathbf{w}=(1,1,1)$, we may regard $R_{\mathbf{w}}$ as a $3\times 3$ matrix
with respect to the standard basis of $\mathbb{Q}^{3}$. Under this point of
view, for $d=1,2,3$, the matrices $N_{d}$ in (1.2) are given by

$N_{d}=R_{\mathbf{w}}U_{d}$

where $U_{1},U_{2},U_{3}$ are defined by

(2.3) $U_{1}=\begin{pmatrix}1&0&0\\\ 0&-1&0\\\ 0&0&1\end{pmatrix},\quad
U_{2}=\begin{pmatrix}-1&0&0\\\ 0&-1&0\\\ 0&0&1\end{pmatrix},\quad
U_{3}=\begin{pmatrix}-1&0&0\\\ 0&1&0\\\ 0&0&1\end{pmatrix}.$

Considering the case where $D=K[t]$, $F=K(t)$ and $\mathbf{w}=(1,f,f)$, for
some $f\in K[t]$, we denote by $R_{f}$ the reflection with respect to
$\mathbf{w}$ using the formula (2.2). The matrix representation of $R_{f}$
with respect to the standard basis of $K(t)^{3}$ is

(2.4) $R_{f}=\left(\begin{array}[]{rrr}-1&-2f&2f\\\ -2f&-2f^{2}+1&2f^{2}\\\
-2f&-2f^{2}&2f^{2}+1\end{array}\right).$

Observe that $R_{f}$ is the matrix appearing in Theorem 1.4, while the matrix
$M_{f}$ appearing in the statement of Theorem 1.2 is given by the product

(2.5) $R_{f}U_{1}=M_{f}=\left(\begin{array}[]{rrr}-1&2f&2f\\\
-2f&2f^{2}-1&2f^{2}\\\ -2f&2f^{2}&2f^{2}+1\end{array}\right).$

Since $\mathcal{Q}(1,f,f)=1$, we see that both $R_{f}$ and $M_{f}$ are
elements of $O_{\mathcal{Q}}(K[t])$, with $R_{f}$ having order 2. We record
here $M_{f}^{-1}$ for future use:

(2.6) $M_{f}^{-1}=U_{1}R_{f}=\left(\begin{array}[]{rrr}-1&-2f&2f\\\
2f&2f^{2}-1&-2f^{2}\\\ -2f&-2f^{2}&2f^{2}+1\end{array}\right).$

The matrix $R_{f}$ also satisfies the following identities.

######  Lemma 2.3.

For $a,b\in K[t]$, we have

$\begin{cases}R_{a}R_{b}=R_{a-b}R_{0},\\\ R_{a}R_{0}R_{b}=R_{a+b}.\end{cases}$

###### Proof.

Both of these equations are easily verified by direct computation. ∎

As defined in the introduction, a _standard Pythagorean triple (SPT)_ is a
primitive Pythagorean triple $(x,y,z)$ satisfying $\deg x<\deg y=\deg z$ and
$\ell(y)=\ell(z)$. SPT’s play the role over $K[t]$ of a positive primitive
integral Pythagorean triple. In the classical setting, every primitive
integral Pythagorean triple can be obtained from a positive one by an element
of $O_{\mathcal{Q}}(\mathbb{Z})$; namely, a change of sign. The next two
results are used to show that, similar to the integral case, any non-standard
primitive Pythagorean triple can be obtained from SPT’s via multiplication by
an element of $O_{\mathcal{Q}}(K[t])$.

######  Lemma 2.4.

Suppose that $Q=(x,y,z)\in K[t]^{3}$ is a Pythagorean triple but not an SPT.
Then $Q$ is one of the following types:

  * (I)

$\deg x<\deg y=\deg z$ and $\ell(y)=-\ell(z)$.

  * (II)

$\deg y<\deg x=\deg z$.

  * (III)

$\deg x=\deg y=\deg z$.

  * (IV)

$\deg z<\deg x=\deg y$. In this case, $K$ must contain a square root of $-1$,
say, $i=\sqrt{-1}$, and $\ell(x)=\pm i\ell(y)$.

###### Proof.

The proof follows easily by comparing the degrees and leading coefficients of
the polynomials appearing in both sides of the equation (1.1). We leave the
details to the reader. ∎

######  Lemma 2.5.

If $Q$ is a primitive Pythagorean triple that is not an SPT and $f\in
K[t]\backslash K$ then $R_{f}Q$ is an SPT.

###### Proof.

Write $Q=(x,y,z)$. Then $Q$ is one of the type (I)–(IV) in Lemma 2.4. Let
$d=z-y$. We claim that $d$ is a non-zero polynomial with $\deg d=\max\\{\deg
y,\deg z\\}=h(Q)$. This claim is obvious if $\deg z\neq\deg y$ (type (II) or
(IV)). Also, if $Q$ is type (I), then clearly $\deg d=\deg y=\deg z$. In case
(III), we must have $\ell(x)^{2}+\ell(y)^{2}=\ell(z)^{2}$, which implies
$\ell(y)\neq\pm\ell(z)$ (because $\ell(x)$ is nonzero). Therefore, the claim
is proved.

If
$\begin{pmatrix}\tilde{x},\tilde{y},\tilde{z}\end{pmatrix}^{T}=R_{f}\begin{pmatrix}x,y,z\end{pmatrix}^{T}$
then (2.4) gives

(2.7) $\displaystyle\tilde{x}$ $\displaystyle=-x+2fd,$
$\displaystyle\tilde{y}$ $\displaystyle=-2fx+2f^{2}d+y=(\tilde{x}-x)f+y,$
$\displaystyle\tilde{z}$ $\displaystyle=-2fx+2f^{2}d+z=(\tilde{x}-x)f+z.$

As a consequence,

$\deg\tilde{x}=\deg d+\deg f<\deg d+2\deg f=\deg\tilde{y}=\deg\tilde{z}$

and $\ell(\tilde{y})=\ell(\tilde{z})=\ell(2f^{2}d)$. ∎

We end this section of preliminary results with a lemma relating the height of
an SPT $Q$ with that of $M_{f}Q^{T}$, for some $f\in K[t]\backslash K$.

######  Lemma 2.6.

If $Q$ is an SPT then, for all $f\in K[t]\backslash K$,
$M_{f}Q^{T}=(\tilde{x},\tilde{y},\tilde{z})^{T}$ is an SPT with $\tilde{x}\neq
0$. Furthermore,

$h(M_{f}Q^{T})=2\deg f+h(Q).$

###### Proof.

Write $Q=(x,y,z)$ and let
$\begin{pmatrix}\tilde{x},\tilde{y},\tilde{z}\end{pmatrix}^{T}=M_{f}\begin{pmatrix}x,y,z\end{pmatrix}^{T}$.
Then (2.5) implies

(2.8) $\begin{array}[]{ccl}\tilde{x}&=&-x+2f(y+z)\\\
\tilde{y}&=&-2fx+2f^{2}(y+z)-y\\\ \tilde{z}&=&-2fx+2f^{2}(y+z)+z\end{array}$

Because $Q$ is an SPT and $f$ is non-constant, by analyzing degrees we can see
that the leading terms from both $\tilde{y}$ and $\tilde{z}$ come from the
polynomial $2f^{2}(y+z)$, while the leading term from $\tilde{x}$ comes from
$2f(y+z)$. From that, it follows easily that $M_{f}Q^{T}$ is an SPT with
$\tilde{x}\neq 0$ and $h(M_{f}Q^{T})=2\deg f+h(Q)$. ∎

##  3\. Proof of Theorem 1.2

In this section, we use infinite descent to prove the existence of a product
representation of an SPT as given in Theorem 1.2. Its proof in Corollary 3.3
is a consequence of the next two propositions. The proof of the uniqueness of
the representation in Theorem 1.2 is found in Corollary 3.7.

######  Proposition 3.1.

Let $Q=(x,y,z)$ be an SPT with $x\neq 0$ and $\deg z\neq 2\deg x$. Then there
exists $f\in K[t]\backslash K$ such that
$\tilde{Q}^{T}=\begin{pmatrix}\tilde{x},\tilde{y},\tilde{z}\end{pmatrix}^{T}=M_{f}^{-1}Q^{T}$
is an SPT with $\tilde{x}\neq 0$ and $h(\tilde{Q})<h(Q)$.

###### Proof.

Let $f\in K[t]$ satisfy $z=fx+k$ with $\deg k<\deg x$. Notice that $f\not\in
K$ since $\deg z>\deg x$.

From (2.6), it follows that

$\displaystyle\tilde{x}$ $\displaystyle=$ $\displaystyle-x-2fy+2fz$
$\displaystyle\tilde{y}$ $\displaystyle=$ $\displaystyle
2fx+(2f^{2}-1)y-2f^{2}z$ $\displaystyle\tilde{z}$ $\displaystyle=$
$\displaystyle-2fx-2f^{2}y+(2f^{2}+1)z.$

If we let $d=z-y$ then the above expressions can be simplified into

(3.1) $\displaystyle\tilde{x}$ $\displaystyle=$ $\displaystyle-x+2fd$ (3.2)
$\displaystyle\tilde{y}$ $\displaystyle=$ $\displaystyle-\tilde{z}+d$

Moreover, since $(\tilde{x},\tilde{y},\tilde{z})$ is a Pythagorean triple, we
have that

(3.3) $\tilde{x}^{2}+d^{2}=2\tilde{z}d.$

We also observe that (1.1) yields

(3.4) $x^{2}=d(z+y).$

From this last equality, the definition of $f$ and $k$, and (3.1) we obtain

(3.5) $\tilde{x}x=-d(z+y)+2(z-k)d=d(d-2k).$

Because $(x,y,z)$ is an SPT with $x\neq 0$, we conclude that $d\neq 0$ and, by
(3.4),

(3.6) $\deg d=2\deg x-\deg z.$

Since $(x,y,z)$ is an SPT with $\deg z\neq 2\deg x$ then (3.6) and $\deg
x<\deg z$ show that

(3.7) $0<\deg d<\deg x.$

Thus, $\deg(d-2k)<\deg x$ and, by equating degrees in (3.5), we arrive at

$\deg\tilde{x}+\deg x=\deg d+\deg(d-2k)<\deg d+\deg x.$

This shows that $\deg\tilde{x}<\deg d$. Consequently, (3.3) proves that
$\deg\tilde{z}=\deg d$ and $2\ell(\tilde{z})=\ell(d)$. Together with (3.2), we
conclude that $\ell(\tilde{y})=\ell(\tilde{z})$ and that
$\deg\tilde{y}=\deg\tilde{z}=\deg d>\deg\tilde{x}$, proving that
$(\tilde{x},\tilde{y},\tilde{z})$ is an SPT.

If we assume that $\tilde{x}=0$, then $\tilde{z}=\tilde{y}$ and

$\tilde{z}=\gcd(\tilde{x},\tilde{y},\tilde{z})=\gcd(x,y,z)=1.$

Moreover, (3.3) shows that $1=\tilde{z}=d/2$. Since this equality contradicts
(3.7), we conclude that $\tilde{x}\neq 0$. To finish our proof, notice that
$Q^{T}=M_{f}\tilde{Q}^{T}$ and Lemma 2.6 imply that $h(\tilde{Q})<h(Q)$. ∎

######  Proposition 3.2.

Let $Q=(x,y,z)$ be an SPT with $x\neq 0$ and $\deg z=2\deg x$. Then there
exist $c\in K^{*}$ and $f\in K[t]\backslash K$ such that $Q=cS_{f}$, for
$S_{f}$ as in (1.3).

###### Proof.

We let $e=\deg x$ and $2e=\deg y=\deg z$. Using the euclidean algorithm, we
can find $a\in K^{*}$ and $b\in K[t]$ satisfying $y=ax^{2}+b$ and $\deg b<2e$.
And since $y$ and $z$ have the same leading coefficient, we have that
$z=ax^{2}+\beta$, for some $\beta\in K[t]$ with $\deg\beta<2e$. From (1.1), we
arrive at

(3.8) $x^{2}(1+2a(b-\beta))=\beta^{2}-b^{2}.$

If $b=0$ or $\beta=0$ then (3.8) implies that $\gcd(x,y,z)\neq 1$. Therefore,
we assume that $\beta$ and $b$ are non-zero.

We show that $\beta^{2}-b^{2}=0$. If we assume otherwise, then $(\beta-b)\neq
0$, $(\beta+b)\neq 0$ and, by equating degrees in (3.8),

$2e=\deg(\beta+b)\leq\max\\{\deg b,\deg\beta\\}<2e.$

Also from (3.8) we see that $\beta\neq b$, since $x\neq 0$. Therefore
$b=-\beta$ and, consequently, (3.8) implies that

$1+4ab=0.$

This proves that

$Q=\left(x,ax^{2}-\frac{1}{4a},ax^{2}+\frac{1}{4a}\right).$

The result follows by taking $f=2ax$ and $c=1/4a$. ∎

######  Corollary 3.3.

Let $Q=(x,y,z)$ be an SPT with $x\neq 0$. Then there exist a sequence
$\\{f,f_{1},\dots f_{k}\\}$ in $K[t]\backslash K$ and $c\in K^{*}$ such that

$Q^{T}=cM_{f_{1}}\cdots M_{f_{k}}S_{f}^{T}.$

###### Proof.

If $Q=(x,y,z)$ satisfies $\deg z=2\deg x$ then $Q=cS_{f}$, where $c\in K^{*}$
and $f\in K[t]$ are given by Proposition 3.2.

Thus we may assume that $\deg z\neq 2\deg x$. According to Proposition 3.1,
there exists $f_{1}\in K[t]\backslash K$ such that
$Q_{1}^{T}=(x_{1},y_{1},z_{1})^{T}=M_{f_{1}}^{-1}Q^{T}$ is an SPT with
$x_{1}\neq 0$ and $h(Q_{1})<h(Q)$. If $\deg z_{1}=2\deg x_{1}$ then, from
Proposition 3.2 we find $c\in K^{*}$ and $f\in K[t]$ such that

$Q^{T}=cM_{f_{1}}S_{f}^{T},$

and we are done. If $\deg z_{1}\neq 2\deg x_{1}$, then we can use Proposition
3.1 to construct $Q_{2}^{T}=(x_{2},y_{2},z_{2})^{T}=M_{f_{2}}^{-1}Q_{1}^{T}$,
for some $f_{2}\in K[t]\backslash K$, such that $x_{2}\neq 0$ and

$h(Q_{2})<h(Q_{1})<h(Q).$

Again, either $\deg z_{2}=2\deg x_{2}$ or $\deg z_{2}\neq 2\deg x_{2}$. In the
first case, we are finished because Proposition 3.2 implies

$Q^{T}=cM_{f_{2}}M_{f_{1}}S_{f}^{T}.$

Otherwise, we can use Proposition 3.1 to construct an SPT
$Q_{3}^{T}=(x_{3},y_{3},z_{3})^{T}=M_{f_{3}}^{-1}Q_{2}^{T}$ with $x_{3}\neq 0$
and

$h(Q_{3})<h(Q_{2})<h(Q_{1})<h(Q).$

In this fashion, for $Q_{0}=Q$, $i\geq 1$ and some sequence
$\\{f_{1},\dots,f_{i}\\}$ in $K[t]\backslash K$ we can construct a recursive
sequence of SPT’s

$(x_{i},y_{i},z_{i})^{T}=Q_{i}^{T}=M_{f_{i}}^{-1}Q_{i-1}^{T}$

with $x_{i}\neq 0$ and

$h(Q_{i})<\cdots<h(Q_{2})<h(Q_{1})<h(Q)$

Since $h(Q_{i})$ is a positive integer for all $i$, the above inequality shows
that we can not continue this construction indefinitely. Therefore, there
exists an integer $k\geq 1$ such that
$Q_{k}^{T}=(x_{k},y_{k},z_{k})^{T}=M_{f_{k}}^{-1}Q_{k-1}^{T}$ is a SPT with
$x_{k}\neq 0$ and $\deg z_{k}=2\deg x_{k}$. Therefore, Proposition 3.2
guarantees the existence of $c\in K^{*}$ and $f\in K[t]$ such that

$Q_{k}=cS_{f},$

The result follows by noticing that

$cS_{f}^{T}=Q_{k}^{T}=M_{f_{k}}^{-1}Q_{k-1}^{T}=M_{f_{k}}^{-1}M_{f_{k-1}}^{-1}Q_{k-2}^{T}=\cdots=M_{f_{k}}^{-1}M_{f_{k-1}}^{-1}\cdots
M_{f_{1}}^{-1}Q^{T}.$

∎

The next series of results are used to prove the uniqueness of the product
representation

$Q^{T}=cM_{f_{1}}\cdots M_{f_{k}}S_{f}^{T}$

of any SPT $Q$ with $x\neq 0$.

######  Lemma 3.4.

Let $P$ and $Q$ be SPT’s and $g$ and $h$ be polynomials in $K[t]\backslash K$.
If

$M_{g}P^{T}=M_{h}Q^{T}$

then $P=Q$ and $g=h$.

###### Proof.

Write $f=g-h$. Clearly, it is enough to prove that $f=0$.

Use Lemma 2.3, together with the fact that $R_{f}$ is of order 2 to obtain

$U_{1}P^{T}=R_{f}R_{0}U_{1}Q^{T}.$

We rewrite this equation as

(3.9)
$\begin{pmatrix}\tilde{x},\tilde{y},\tilde{z}\end{pmatrix}^{T}=R_{f}\begin{pmatrix}x,y,z\end{pmatrix}^{T}$

where $(\tilde{x},\tilde{y},\tilde{z})^{T}=U_{1}P^{T},$ and
$(x,y,z)^{T}=R_{0}U_{1}Q^{T}.$

In what follows, we use notation from the proof of Lemma 2.5. Since $P$ is an
SPT, $(\tilde{x},\tilde{y},\tilde{z})$ is a Pythagorean triple of type (I). If
we assume that $f\notin K$, Lemma 2.5 would imply that the right-hand side of
(3.9) is an SPT. Therefore, $f\in K$.

Notice that $(x,y,z)$ is also a Pythagorean triple of type (I). Thus, if $f\in
K^{*}$ then (2.7) implies that $\deg x<\deg\tilde{x}=\deg(z-y)=\deg z=\deg y$.
Additionally, (2.7) implies that $\ell(\tilde{y})=\ell(\tilde{x})f-\ell(z)$
and $\ell(\tilde{z})=\ell(\tilde{x})f+\ell(z)$. This shows that
$\ell(\tilde{y})$ and $\ell(\tilde{z})$ cannot be both zero; consequently,
either $\deg\tilde{y}=\deg z$ or $\deg\tilde{z}=\deg z$. Therefore,
$\deg\tilde{x}=\deg\tilde{y}$ or $\deg\tilde{x}=\deg\tilde{z}$. Since this
contradicts the fact that $(\tilde{x},\tilde{y},\tilde{z})$ is a Pythagorean
triple of type (I), we have that $f=g-h=0$, as desired. ∎

######  Proposition 3.5.

Let $P$ and $Q$ be SPT’s and $m\geq n$ be positive integers. Suppose that
there are sequences $\\{g_{0},g_{1},\ldots,g_{m}\\}$ and
$\\{h_{0},h_{1},\ldots,h_{n}\\}$ in $K[t]\backslash K$ such that

$M_{g_{m}}M_{g_{m-1}}\cdots M_{g_{1}}P^{T}=M_{h_{n}}M_{h_{n-1}}\cdots
M_{h_{1}}Q^{T}.$

Then either $P=Q$, $m=n$ and $g_{i}=h_{i}$; or $m>n$, $Q^{T}=M_{g_{m-n}}\cdots
M_{g_{1}}P^{T}$ and $g_{m-n+i}=h_{i}$ for $1\leq i\leq n$.

###### Proof.

Assume first that $m=n$. We prove, by induction on $n$, that

$M_{g_{n}}M_{g_{n-1}}\cdots M_{g_{1}}P^{T}=M_{h_{n}}M_{h_{n-1}}\cdots
M_{h_{1}}Q^{T}$

implies $P=Q$ and $g_{i}=h_{i}$, for all $1\leq i\leq n$. The base case of
induction is Lemma 3.4. By Lemma 2.6, $\bar{P}^{T}=M_{g_{n-1}}\cdots
M_{g_{1}}P^{T}$ and $\bar{Q}^{T}=M_{h_{n-1}}\cdots M_{h_{1}}Q^{T}$ are SPT’s.
By assumption, they satisfy

$M_{g_{n}}\bar{P}^{T}=M_{h_{n}}\bar{Q}^{T}.$

Another application of Lemma 3.4 implies that $g_{n}=h_{n}$ and
$\bar{P}=\bar{Q}$. Therefore, the induction hypothesis implies that $P=Q$ and
$g_{i}=h_{i}$ for all $1\leq i\leq n$.

Suppose $m>n$. If $P^{\prime T}=M_{g_{m-n}}M_{g_{j-1}}\cdots M_{g_{1}}P^{T}$
then, by hypothesis,

$M_{g_{m}}M_{g_{m-1}}\cdots
M_{g_{m-n+1}}{P^{\prime}}^{T}=M_{h_{n}}M_{h_{n-1}}\cdots M_{h_{1}}Q^{T}.$

Notice that there are $n$ matrices in both sides of the previous equation.
Therefore, we can apply the $m=n$ case which had been proved above to arrive
at our desired result. ∎

######  Lemma 3.6.

Let $P$ be an SPT, $c\in K^{*}$ and $f$ and $g$ be polynomials in
$K[t]\backslash K$. Then

$cS_{g}^{T}=M_{f}P^{T}$

if and only if $g=2f$ and $P=(0,c,c)$.

###### Proof.

We write $P=(x,y,z)$. From $cS_{g}^{T}=M_{f}P^{T}$ and (2.8), we get

$\displaystyle 2cg$ $\displaystyle=$ $\displaystyle-x+2f(y+z)$ $\displaystyle
cg^{2}-c$ $\displaystyle=$ $\displaystyle-2fx+2f^{2}(y+z)-y$ $\displaystyle
cg^{2}+c$ $\displaystyle=$ $\displaystyle-2fx+2f^{2}(y+z)+z$

Therefore,

$2c=cg^{2}+c-(cg^{2}-c)=z+y.$

Since $P$ is an SPT, we conclude that $z=y=c$ and $x=0$. Consequently, the
first equality above implies that $g=2f$.

The converse is proved via direct computation using (2.8). ∎

######  Corollary 3.7.

Let $m$ and $n$ be positive integers. Suppose that there are $c,d\in K^{*}$
and sequences $\\{g_{0},g_{1},\ldots,g_{m}\\}$ and
$\\{h_{0},h_{1},\ldots,h_{n}\\}$ in $K[t]\backslash K$ such that

$cM_{g_{m}}M_{g_{m-1}}\cdots
M_{g_{1}}S_{g_{0}}^{T}=dM_{h_{n}}M_{h_{n-1}}\cdots M_{h_{1}}S_{h_{0}}^{T}.$

Then $m=n$, $c=d$ and $g_{i}=h_{i}$, for all $0\leq i\leq n$.

###### Proof.

First, we show that $m\neq n$ is impossible. Otherwise, we may assume without
loss of generality that $m>n$ and conclude from Proposition 3.5 that

(3.10) $cS_{h_{0}}^{T}=M_{h}\bar{P}^{T}$

where $h=g_{m-n}$, and $\bar{P}=dS_{g_{0}}$ or
$\bar{P}^{T}=dM_{g_{m-n-1}}\cdots M_{g_{1}}S_{g_{0}}^{T}$. In any case,
$\bar{P}=(\bar{x},\bar{y},\bar{z})$ is an SPT with $\bar{x}\neq 0$, according
to Lemma 2.6. But, given (3.10), $\bar{x}\neq 0$ contradicts the conclusion of
Lemma 3.6.

Therefore, $m=n$ and Proposition 3.5 implies that $g_{i}=h_{i}$, for all
$1\leq i\leq n$, and $cS_{g_{0}}=dS_{h_{0}}$. From the last equality, it
easily follows that $c=d$ and $g_{0}=h_{0}$, finishing our proof. ∎

##  4\. Generators of $O_{\mathcal{Q}}(K[t])$

When $(\tilde{x},\tilde{y},\tilde{z})^{T}=R_{f}(x,y,z)^{T}$, recall from (2.7)
that

(4.1) $\displaystyle\tilde{x}$ $\displaystyle=-x+2f(z-y),$
$\displaystyle\tilde{y}$ $\displaystyle=(\tilde{x}-x)f+y,$
$\displaystyle\tilde{z}$ $\displaystyle=(\tilde{x}-x)f+z.$

We will use these identities in the following two lemmas.

######  Lemma 4.1.

Suppose that $Q$ is an SPT. Then $R_{f}Q^{T}$ is also an SPT for any $f\in K$.

###### Proof.

Write $Q=(x,y,z)$ and
$\tilde{Q}^{T}=(\tilde{x},\tilde{y},\tilde{z})^{T}=R_{f}Q^{T}$ for $f\in K$.
Note from Lemma 2.2 that $h(Q)=h(\tilde{Q})$. From the first equation in
(4.1), we see that that $\deg\tilde{x}<\deg(y)=h(Q)=h(\tilde{Q})$. This
implies that $\deg\tilde{y}=\deg\tilde{z}$. Also it is obvious from the second
and third equations of (4.1) that $\ell(\tilde{y})=\ell(\tilde{z})$. This
completes the proof that $\tilde{Q}$ is an SPT. ∎

######  Lemma 4.2.

Suppose that $Q$ is a primitive Pythagorean triple, which is not an SPT. Then
there exists $f\in K$ such that $M_{f}^{-1}Q^{T}$ is an SPT.

###### Proof.

Recall from Lemma 2.4 that $Q$ is one of the type (I)–(IV). We claim that
there exists $f\in K$ such that
$\tilde{Q}^{T}=(\tilde{x},\tilde{y},\tilde{z})^{T}:=R_{f}Q^{T}$ is of type
(I). This would imply the conclusion in the lemma because
$U_{1}\tilde{Q}^{T}=M_{f}^{-1}Q^{T}$ would then be an SPT. Choose $f\in K$ so
that

(4.2) $\begin{cases}f=0&\text{ if $Q$ is of type (I)},\\\
-\ell(x)+2f\ell(z)=0&\text{ if $Q$ is of type (II)},\\\
-\ell(x)+2f(\ell(z)-\ell(y))=0&\text{ if $Q$ is of type (III)},\\\
-\ell(x)-2f\ell(y)=0&\text{ if $Q$ is of type (IV)}.\end{cases}$

We see from the first equation of (4.1) that the above equations are solvable
in $f$ in all cases and that $h(Q)=h(\tilde{Q})$ because of Lemma 2.2. Once
$f$ is chosen to satisfy (4.2), we have $\deg\tilde{x}<h(\tilde{Q})$, which
results in $\deg\tilde{y}=\deg\tilde{z}$. This implies that either
$\ell(\tilde{y})=-\ell(\tilde{z})$ (in which case the claim is proven) or
$\ell(\tilde{y})=\ell(\tilde{z})$. However, if
$\ell(\tilde{y})=\ell(\tilde{z})$, this means that $\tilde{Q}$ is an SPT. This
is a contradiction because Lemma 4.1 would then imply that

$R_{f}\tilde{Q}^{T}=R_{f}(R_{f}Q)^{T}=Q^{T}$

is also an SPT, which we had assumed not. ∎

###### Proof of Theorem 1.3.

We will prove that every primitive Pythagorean triple $Q$ is in the
$O_{\mathcal{Q}}(K[t])$-orbit of $(0,1,1)$.

We handle the case $h(Q)=0$. If $Q$ is an SPT, then $Q=(0,c,c)$ for some $c\in
K^{*}$. Recall that $T_{c}$ is a matrix defined by (1.4). It is easily
verified that

(4.3) $T_{c}(0,1,1)^{T}=(0,c,c)^{T},$

so that $Q=(0,c,c)$ is in the $O_{\mathcal{Q}}(K[t])$-orbit of $(0,1,1)$. If
$Q$ is not an SPT, we apply Lemma 4.2 to obtain $f\in K$ such that
$M_{f}^{-1}Q^{T}$ is an SPT. Since $h(M_{f}^{-1}Q^{T})=0$ (cf. Lemma 2.2) we
see from the above argument that $M_{f}^{-1}Q^{T}$ is in the orbit of
$(0,1,1)$, which of course implies that $Q$ is as well. It remains to consider
the case $h(Q)>0$. Then Theorem 1.2 shows that $Q$ is in the orbit of
$cS_{g}$, for some $c\in K^{*}$ and $g\in K[t]\backslash K$. But Lemma 3.6
implies that $cS_{g}$ and, thus, $Q$ are in the orbit of $(0,c,c)$, which has
already been shown to be in the orbit of $(0,1,1)$. ∎

######  Proposition 4.3.

The stabilizer of $(0,1,1)$ in $O_{\mathcal{Q}}(K[t])$ is generated by the set

$\\{R_{f}\mid f\in K[t]\\}.$

###### Proof.

We follow Conrad’s argument given in Appendix of [Conrad]. Let
$\mathcal{S}_{1}$ be the group generated by $\\{R_{f}\mid f\in K[t]\\}$. A
simple calculation shows that $R_{f}$ fixes $(0,1,1)$ for every $f\in K[t]$
therefore $\mathcal{S}_{1}$ is a subgroup of the stabilizer of $(0,1,1)$.
Conversely, let $R$ be in the stabilizer of $(0,1,1)$. Then $R$ is of the form

$R=\begin{pmatrix}a_{1}&a_{2}&-a_{2}\\\ a_{3}&a_{4}&1-a_{4}\\\
a_{5}&a_{6}&1-a_{6}\\\ \end{pmatrix}$

for some $a_{1},\dots,a_{6}\in K[t]$. Also, letting $J$ be the $3\times 3$
diagonal matrix whose diagonal entries are $(1,1,-1)$, the condition that $R$
is orthogonal with respect to the quadratic form $\mathcal{Q}(t)$ is
equivalent to

$R^{T}JR=J,$

which yields

$\begin{cases}a_{1}^{2}+a_{3}^{2}-a_{5}^{2}=1,\\\
a_{2}^{2}+a_{4}^{2}-a_{6}^{2}=1,\\\
a_{2}^{2}+(a_{4}-1)^{2}-(a_{6}-1)^{2}=-1,\end{cases}\begin{cases}a_{1}a_{2}+a_{3}a_{4}-a_{5}a_{6}=0,\\\
-a_{1}a_{2}-a_{3}(a_{4}-1)+a_{5}(a_{6}-1)=0,\\\
-a_{2}^{2}-a_{4}(a_{4}-1)+a_{6}(a_{6}-1)=0.\end{cases}$

Solving them simultaneously, we obtain

$\begin{cases}a_{1}^{2}=1,\\\ a_{3}=a_{5}=-a_{1}a_{2},\\\
a_{4}=1+a_{6}=1-\frac{a_{2}^{2}}{2}.\\\ \end{cases}$

As a result, we have

$R=\begin{pmatrix}a_{1}&a_{2}&-a_{2}\\\
-a_{1}a_{2}&1-\frac{a_{2}^{2}}{2}&\frac{a_{2}^{2}}{2}\\\
-a_{1}a_{2}&-\frac{a_{2}^{2}}{2}&1+\frac{a_{2}^{2}}{2}\end{pmatrix}$

with $a_{1}=1$ or $a_{1}=-1$. Therefore, we have

$R=R_{-a_{2}/2}\text{ or }R_{-a_{2}/2}U_{3}$

depending on $a_{1}=1$ or $a_{1}=-1$, respectively. Since
$U_{3}=R_{0}\in\mathcal{S}_{1}$ this completes the proof. ∎

###### Proof of Theorem 1.4.

Let $\mathcal{S}_{2}$ be the subgroup of $O_{\mathcal{Q}}(K[t])$ generated by
the set given in the statement of the theorem. Since

$U_{1}=\begin{pmatrix}1&0&0\\\ 0&-1&0\\\
0&0&1\end{pmatrix}=P_{xy}\begin{pmatrix}-1&0&0\\\ 0&1&0\\\
0&0&1\end{pmatrix}P_{xy}=P_{xy}R_{0}P_{xy}$

it follows that $M_{h}\in\mathcal{S}_{2}$ for any $h\in K[t]$ (see (2.5)).
Suppose $A\in O_{\mathcal{Q}}(K[t])$. Let $Q^{T}=A(0,1,1)^{T}$, which is
obviously a primitive Pythagorean triple. Next, we find $N\in\mathcal{S}_{2}$
such that $NQ^{T}$ is an SPT; if $Q$ is already an SPT, then $N=I_{3}$ (the
identity matrix), otherwise, we choose $N$ to be $M_{f}^{-1}$ as constructed
in Lemma 4.2. Now, we apply Theorem 1.2 and Lemma 3.6 to obtain

$\begin{pmatrix}0\\\ c\\\ c\end{pmatrix}=M^{-1}_{g/2}M_{f_{1}}\cdots
M_{f_{k}}NQ^{T}=M^{-1}_{g/2}M_{f_{1}}\cdots M_{f_{k}}NA\begin{pmatrix}0\\\
1\\\ 1\end{pmatrix}$

for some $g,f_{1},\cdots,f_{k}\in K[t]$ and $c\in K^{*}$. Therefore we
conclude from (4.3) that

$T_{c}^{-1}M_{f_{1}}\cdots M_{f_{k}}NA$

fixes $(0,1,1)$. From Proposition 4.3, it follows that the above product
belongs to $\mathcal{S}_{1}$ (thus to $\mathcal{S}_{2}$ as well), which then
implies that $A\in\mathcal{S}_{2}$. ∎

## References


# TCAD modeling of radiation-induced defects in 4H-SiC diodes

Philipp Gaggl  Jürgen Burin  Andreas Gsponer  Simon Emanuel Waid  Richard
Thalmeier  Thomas Bergauer<EMAIL_ADDRESS>
###### Abstract

Silicon Carbide (SiC) has several advantageous properties compared to Silicon
(Si) that make it an appealing detector material, such as a larger charge
carrier saturation velocity, bandgap, and thermal conductivity. While the
current understanding of material and model parameters suffices to simulate
unirradiated 4H-SiC devices using technical computer-aided design (TCAD),
configurations to accurately predict performance degradation after high levels
of irradiation due to induced defects acting as traps and recombination
centers do not exist. Despite increasing efforts to characterize the
introduction and nature of such defects in 4H-SiC, published results are often
contradictory. This work presents a bulk radiation damage model for TCAD
simulations based on measurements on $50\;$\mathrm{\SIUnitSymbolMicro m}$$
4H-SiC pad diodes, neutron-irradiated at various fluxes ranging from $5\times
10^{14}\;\text{n}_{\text{eq}}/${\mathrm{cm}}^{2}$$ to $1\times
10^{16}\;\text{n}_{\text{eq}}/${\mathrm{cm}}^{2}$$. The model accurately
predicts internal electric shifts, such as flattening of the detector
capacitance, degradation in charge collection efficiency (CCE), and signal
detection capabilities under forward bias conditions up to high bias. It
further introduces the EH4 defect cluster as major lifetime killer and
reinforces the assumption of the EH${}_{\text{6,7}}$ deep-level defect to be
of donor type.

###### keywords:

Silicon carbide , Radiation damage to detector materials (solid state) , TCAD
, Numerical simulations , Defect states

[1]organization=Institute of High Energy Physics of the Austrian Academy of
Sciences, addressline=Nikolsdorfer Gasse 18, postcode=1050, city=Vienna,
country=Austria [2]organization=TU Wien, addressline=Wiedner Hauptstr. 8–10,
postcode=1040, city=Vienna, country=Austria

##  1 Introduction

With the upcoming high luminosity upgrade for the large hadron collider (HL-
LHC) at the research center CERN and the consequent increase in radiation
damage to operating equipment, current silicon (Si) based detectors are
rendered inoperable [1, 2]. Next to a variety of improvements in the
manufacturing and novel design of Si-detectors [3, 4, 5], research in Silicon
Carbide (SiC), prominently the 4H polytype, as high-energy particle detector
material has been rekindled due to its unique properties [6, 7, 8, 9, 10].
Simulations via technology computer-aided design (TCAD) software are crucial
in investigating 4H-SiC. Despite a multitude of studies on performance
degradation of, and defect formation in 4H-SiC after high levels of
irradiation ($\Phi\geq 1\times
10^{16}\;\text{n}_{\text{eq}}/${\mathrm{cm}}^{2}$$, where
$\text{n}_{\text{eq}}$ describes the $1\;$\mathrm{MeV}$$ neutron equivalent
according to NIEL hypothesis [11]), no TCAD model to reproduce these findings
accurately exists to the best of our knowledge. Utilizing the TCAD simulation
software Sentaurus [12], this work presents our first results towards
developing a comprehensive radiation damage model for 4H-SiC up to high
irradiation fluences. The current model focuses solely on introducing bulk
defects, whose parameters are derived from literature and adapted to reproduce
measurements on neutron-irradiated 4H-SiC samples described in [13].

##  2 Materials and methods

###  2.1 Samples and Irradiation

The devices under test (DUTs) were planar, $3\times 3\;${\mathrm{mm}}^{2}$$
PiN-diodes manufactured and developed at IMB-CNM-CSIC [14]. A
$50\;$\mathrm{\SIUnitSymbolMicro m}$$ epitaxially grown layer of high
resistivity ($20\;$\mathrm{\SIUnitSymbolOhm}\text{\,}\mathrm{cm}$$) serves as
active detecting region. Detailed information about the device production can
be found in [15]. The samples have been neutron-irradiated at the TRIGA Mark
II reactor at the Atominstitut in Vienna [16] at different neutron fluences,
one sample each. The resulting fluences ($5\times
10^{14}\;\text{n}_{\text{eq}}/${\mathrm{cm}}^{2}$$ to $1\times
10^{16}\;\text{n}_{\text{eq}}/${\mathrm{cm}}^{2}$$) resulted by varying
exposition times and are summarized in [17].
The electrical characterization included current (I-V) and capacitance (C-V),
as well as charge collection efficiency (CCE) measurements using different
sources of ionizing radiation at both forward and reverse operating bias [13].

###  2.2 TCAD model

Due to the p++-implant and metalization covering all active diode areas, the
proposed TCAD model only considers bulk defects while neglecting interface
defects and oxide charges. The initial choice of defects and their respective
characteristics have been varied to cover the vast parameter space in the
existing literature. These parameters were then adapted successively to
increase conformity with experimental results. Due to the low dark current
levels of 4H-SiC, reverse I-V measurements are dominated by electric noise and
surface currents, restricting TCAD comparison to forward bias operation.

##  3 Results

Table 1 summarizes the defects considered for the TCAD model and their
respective parameters, as well as parts of the wide field of investigated
literature best fitting the final obtained values. While the Z1,2 and EH6,7
defect are both widely known as major lifetime killers in 4H-SiC, the EH4
center, representing a cluster of defects [18], proved to be crucial as well.
As the discussion about the type of the EH6,7 defect continues, the presented
model strongly suggests it to be of donor-type [19, 20, 21]. The included
Boron-center defects, namely the B and D centers, are considered solely
intrinsic and, therefore, do not feature an introduction rate to increase with
irradiation [22, 23]. However, aside from slight improvements in C-V
conformity, their contribution to the overall model remains insignificant,
while actual concentration strongly depends on the process design.

Table 1: Final defect specifications of the developed TCAD irradiation damage
model and their respective parameters: Defect type, activation energy,
electron and hole capture cross-sections, and their assumed density after
$1\;$\mathrm{MeV}$$ neutron equivalent fluence $\Phi$. $E_{C}$ and $E_{V}$
denote the conduction and valence band energy, and B/D refer to Boron-center
defects. Additionally, the investigated literature that best fits the
respective values is given.

Name | Type | $E\;[$\mathrm{eV}$]$ | $\sigma_{e}\;[${\mathrm{cm}}^{2}$]$ | $\sigma_{h}\;[${\mathrm{cm}}^{2}$]$ | $N\;[${\mathrm{cm}}^{-3}$]$
---|---|---|---|---|---
Z1,2 | Acceptor |  $E_{C}-0.67$ [24] |  $2.0\cdot 10^{-14}$ [24] |  $3.5\cdot 10^{-14}$ [25] |  $5.0\cdot\Phi$ [26]
EH6,7 | Donor |  $E_{C}-1.60$ [27] |  $9.0\cdot 10^{-12}$ [27] |  $3.8\cdot 10^{-14}$ [27] |  $1.6\cdot\Phi$ [26]
EH4 | Acceptor |  $E_{C}-1.03$ [18] |  $5.0\cdot 10^{-13}$ [28] |  $5.0\cdot 10^{-14}$ [26] |  $2.4\cdot\Phi$ [26]
B | Donor |  $E_{V}+0.28$ [22] |  $2.0\cdot 10^{-15}$ [23] |  $2.0\cdot 10^{-14}$ [26] | $1.0\cdot 10^{14}$
D | Donor |  $E_{V}+0.54$ [22] |  $2.0\cdot 10^{-15}$ [23] |  $2.0\cdot 10^{-14}$ [26] | $1.0\cdot 10^{14}$

Figure 1 shows the forward I-V measurement and simulation results. As can be
seen, the TCAD model accurately predicts the 4H-SiC device increasingly losing
its rectifying properties, thus allowing for forward biasing up to high
voltages [13, 29]. Absolute values are in good agreement with the experiments
despite increasingly underestimating current levels with rising fluence. This
may be attributed to surface currents not included in the model. Although the
exact origin of this rectification after irradiation is not yet fully
understood, the model suggests a separation of charges within the device.
Holes and electrons diffusing from the implant and the buffer layer,
respectively, are trapped close to their origin, resulting in a field well
located mid-device. Defects become fully occupied only at sufficient currents,
and carrier lifetimes increase, thus restoring conducting properties.
Accompanying this, the capacitance in both forward and reverse bias flatlines
after irradiation, as displayed in Figure 2. While the model reproduces this
trend, absolute values, though very accurate, are not perfect. This most
likely is a direct result of slight deviations in the simulated doping
profile, as is already indicated for the unirradiated case in Figure 2.

Figure 1: Comparison of forward I-V measurements from [13] with TCAD-model
output. Figure 2: Comparison of C-V measurements from [13] (given as
$1/C^{2}$) with TCAD-model output

##  4 Conclusions and Outlook

A first step towards a comprehensive irradiation damage TCAD model for 4H-SiC
has been developed, focusing solely on bulk defects. Results agree well with
I-V and C-V measurements of neutron-irradiated 4H-SiC diodes. While absolute
values deviate with increasing irradiation fluence, major shifts in the
internal electric structure of 4H-SiC after irradiation can be recreated very
well. Furthermore, the model strongly suggests the EH6,7 center be of donor
type, which is still discussed within the literature, while also introducing
the EH4 defect cluster as a significant lifetime killer.

## Acknowledgements

This project has received funding from the Austrian Research Promotion Agency
FFG, grant number 883652. Production and development of the 4H-SiC samples was
supported by the Spanish State Research Agency (AEI) and the European Regional
Development Fund (ERDF), ref. RTC-2017-6369-3.

## References

  * Bruzzi et al. [2007] M. Bruzzi, et al.,  Comparing radiation tolerant materials and devices for ultra rad-hard tracking detectors,  NIM-A 579 (2007) 754–761.
  * Sellin and Vaitkus [2006] P. Sellin, J. Vaitkus,  New materials for radiation hard semiconductor dectectors,  NIM-A 557 (2006) 479–489.
  * Lozano et al. [2005] M. Lozano, et al.,  Comparison of radiation hardness of P-in-N, N-in-N, and N-in-P silicon pad detectors,  IEEE transactions on nuclear science 52 (2005) 1468–1473.
  * Parker et al. [1997] S. I. Parker, et al.,  3D-A proposed new architecture for solid-state radiation detectors,  NIM-A 395 (1997) 328–343.
  * Macchiolo [2005] A. Macchiolo,  The CERN RD50 Collaboration: Development of Radiation Hard Semiconductor Detectors for Super-LHC,  in: AIP conference proceedings, volume 794, United States, 2005, pp. 302–306.
  * Coutinho et al. [2021] J. Coutinho, et al.,  Silicon carbide diodes for neutron detection,  NIM-A 986 (2021) 164793.
  * Liu et al. [2017] L. Y. Liu, et al.,  A 4H silicon carbide based fast-Neutron detection system with a neutron threshold of 0.4 MeV,  Sensors and actuators. A. Physical. 267 (2017) 547–551.
  * Nava et al. [2004] F. Nava, et al.,  Minimum ionizing and alpha particles detectors based on epitaxial semiconductor silicon carbide,  IEEE transactions on nuclear science 51 (2004) 238–244.
  * Christanell et al. [2022] M. Christanell, et al.,  4H-Silicon Carbide as particle detector for high-intensity ion beams,  JINST 17 (2022). doi:10.1088/1748-0221/17/01/c01060.
  * Nava et al. [2008] F. Nava, et al.,  Silicon carbide and its use as a radiation detector material,  Measurement science & technology 19 (2008) 102001.
  * Moll [1999] M. Moll, Radiation Damage in Silicon Particle Detectors: Microscopic defects and macroscopic properties, Ph.D. thesis, Hamburg U., 1999.
  * Synopsys Sentaurus TCAD Ver. V-2023.09, Synopsys, Inc., Mountain View, CA, USA. [2024] Synopsys Sentaurus TCAD Ver. V-2023.09, Synopsys, Inc., Mountain View, CA, USA., 2024. URL: https://www.synopsys.com/home.aspx.
  * Gsponer et al. [2023] A. Gsponer, et al.,  Neutron radiation induced effects in 4H-SiC PiN diodes,  JINST 18 (2023). doi:10.1088/1748-0221/18/11/C11027.
  * IMB-CNM -CSIC(2024) [Centro Nacional de Micróelectronica] IMB-CNM (Centro Nacional de Micróelectronica)-CSIC, 2024. URL: http://www.cnm.es/.
  * Rafí et al. [2018] J. Rafí, et al.,  Four-quadrant silicon and silicon carbide photodiodes for beam position monitor applications: electrical characterization and electron irradiation effects,  JINST 13 (2018). doi:10.1088/1748-0221/13/01/C01045.
  * Salajka [2021] P. Salajka, Irradiation of Silicon detectors for HEP experiments in the Triga Mark II reactor of ATI, Wien, 2021.
  * Gaggl et al. [2022] P. Gaggl, et al.,  Charge collection efficiency study on neutron-irradiated planar silicon carbide diodes via UV-TCT,  NIM-A 1040 (2022). doi:10.1016/j.nima.2022.167218.
  * Alfieri et al. [2005] G. Alfieri, et al.,  Annealing behavior between room temperature and 2000°C of deep level defects in electron-irradiated n-type 4H silicon carbide,  Journal of Applied Physics 98 (2005) 043518. doi:10.1063/1.2009816.
  * Booker et al. [2016] I. D. Booker, et al.,  Donor and double-donor transitions of the carbon vacancy related EH6,7 deep level in 4H-SiC,  Journal of Applied Physics 119 (2016) 235703. doi:10.1063/1.4954006.
  * Hornos et al. [2011] T. Hornos, et al.,  Large-Scale Electronic Structure Calculations of Vacancies in 4H-SiC Using the Heyd-Scuseria-Ernzerhof Screened Hybrid Density Functional,  in: Silicon Carbide and Related Materials 2010, volume 679 of Materials Science Forum, Trans Tech Publications Ltd, 2011, pp. 261–264. doi:10.4028/www.scientific.net/MSF.679-680.261.
  * Bathen et al. [2024] M. E. Bathen, et al.,  Dual configuration of shallow acceptor levels in 4H-SiC,  Materials Science in Semiconductor Processing 177 (2024) 108360. doi:https://doi.org/10.1016/j.mssp.2024.108360.
  * Capan and Brodar [2022] I. Capan, T. Brodar,  Majority and Minority Charge Carrier Traps in n-Type 4H-SiC Studied by Junction Spectroscopy Techniques,  Electronic Materials 3 (2022) 115–123. URL: https://www.mdpi.com/2673-3978/3/1/11.
  * Klein et al. [2011] P. B. Klein, et al.,  Slow de-trapping of minority holes in n-type 4H-SiC epilayers,  physica status solidi (a) 208 (2011) 2790–2795. doi:https://doi.org/10.1002/pssa.201127260.
  * Klein [2009] P. B. Klein,  Identification and carrier dynamics of the dominant lifetime limiting defect in n– 4H-SiC epitaxial layers,  physica status solidi (a) 206 (2009) 2257–2272. doi:https://doi.org/10.1002/pssa.200925155.
  * Klein et al. [2006] P. B. Klein, et al.,  Lifetime-limiting defects in n- 4H-SiC epilayers,  Applied Physics Letters 88 (2006) 052110. doi:10.1063/1.2170144.
  * Hazdra et al. [2014] P. Hazdra, et al.,  Point Defects in 4H-SiC Epilayers Introduced by 4.5 MeV Electron Irradiation and their Effect on Power JBS SiC Diode Characteristics,  in: Gettering and Defect Engineering in Semiconductor Technology XV, volume 205 of Solid State Phenomena, Trans Tech Publications Ltd, 2014, pp. 451–456. doi:10.4028/www.scientific.net/SSP.205-206.451.
  * Knezevic et al. [2023] T. Knezevic, et al.,  Boron-Related Defects in N-Type 4H-SiC Schottky Barrier Diodes,  Materials 16 (2023). doi:10.3390/ma16093347.
  * Booker et al. [2014] I. D. Booker, et al.,  Carrier Lifetime Controlling Defects Z1/2 and RB1 in Standard and Chlorinated Chemistry Grown 4H-SiC,  Crystal Growth & Design 14 (2014) 4104–4110. doi:10.1021/cg5007154.
  * Rafí [2020] J. M. o. Rafí,  Electron, Neutron, and Proton Irradiation Effects on SiC Radiation Detectors,  IEEE Transactions on Nuclear Science 67 (2020) 2481–2489. doi:10.1109/TNS.2020.3029730.


#  GPTQT: Quantize Large Language Models Twice to Push the Efficiency
††thanks: Accepted by 11th IEEE International Conference on Cybernetics and
Intelligent Systems. This work was supported by the National Natural Science
Foundation.China (No.62173300)

Yipin Guo, Yilin Lang, Qinyuan Ren
College of Control Science and Engineering, Zhejiang University, Hangzhou,
China
{guoyipin, langyilin<EMAIL_ADDRESS>
###### Abstract

Due to their large size, generative Large Language Models (LLMs) require
significant computing and storage resources. This paper introduces a new post-
training quantization method, GPTQT, to reduce memory usage and enhance
processing speed by expressing the weight of LLM in 3bit/2bit. Practice has
shown that minimizing the quantization error of weights is ineffective,
leading to overfitting. Therefore, GPTQT employs a progressive two-step
approach: initially quantizing weights using Linear quantization to a
relatively high bit, followed by converting obtained int weight to lower bit
binary coding. A re-explore strategy is proposed to optimize initial scaling
factor. During inference, these steps are merged into pure binary coding,
enabling efficient computation. Testing across various models and datasets
confirms GPTQT’s effectiveness. Compared to the strong 3-bit quantization
baseline, GPTQT further reduces perplexity by 4.01 on opt-66B and increases
speed by 1.24$\times$ on opt-30b. The results on Llama2 show that GPTQT is
currently the best binary coding quantization method for such kind of LLMs.

###### Index Terms:

Large Language Models, Quantization, Efficient AI

##  I Introduction

Pre-trained large language models (LLMs), especially from the Transformer
family like the Generative Pre-trained Transformer (GPT)[1] and Open Pre-
trained Transformer (OPT)[2], excel in complex language tasks. Their success
has generated considerable academic and practical interest.

However, their high computational and storage demands pose a significant
adoption barrier. For instance, GPT-3 175B’s parameters, even when compressed
to float16, require about 326GB for inference. This exceeds the capacity of
advanced single GPU units, often necessitating expensive multi-GPU
configurations.

Quantization technology reduces model parameter and activation precision,
e.g., substituting float32 with int8 cuts storage needs by 4$\times$ [3, 4].
While applying low-bit weight quantization to LLMs promises memory savings, it
introduces significant challenges. Quantization-aware training (QAT) [5, 6],
though effective, is impractical for LLMs due to high training costs.
Conversely, post-training quantization (PTQ) suffers from substantial accuracy
losses in low-bit configurations, compromising model performance.

Due to communication bandwidth constraints, keeping activations in float16
while quantizing weights to low bits has proven effective in local settings
with low concurrency. AWQ[7] keeps 1% of critical weights in float16,
quantizing the rest in a w4a16 LLM configuration. GPTQ[8] uses second-order
information for error compensation, resulting in acceptable accuracy losses
under w3a16. BiLLM[9] integrates binary weights into LLMs, achieving 1.11bits
with unstructured sparsity. However, GPTQ’s linear quantization and
maintenance of float16 activations lack effectiveness. Furthermore, BiLLM’s
aggressive quantization complicates achieving tangible hardware performance
gains. BCQ[10] first applies binary coding[11] to LLMs but only iteratively
optimizes quantized MSE weight error, leading to significant accuracy losses.

GPTQT aims to improve the accuracy of post-training quantized LLMs and achieve
significant performance enhancements on general-purpose GPUs. It introduces a
new binary-coding method, offering enhanced representational capacity within
the same bit allocation.

Specifically, GPTQT quantizes LLMs in two stages. First, it linearly quantizes
weights to a higher bit resolution, then converts these to lower bit binary-
coded weights. This change in representation range compels GPTQT to reassess
and adjust the scaling factor to maintain and restore accuracy. In inference,
these two steps are merged into pure binary coding, which can use efficient
computing methods. Our contributions are summarized as follows:

  * •

Introduce GPTQT, a novel post-training quantization approach that converts LLM
weights to low-bit binary coding via a heterogeneous, progressive, two-stage
quantization process.

  * •

Propose a new re-exploration scheme for the scaling factor in response to
changes in representation range during progressive quantization, optimizing
accuracy.

  * •

Show that weights processed by GPTQT eliminate intermediate states in
inference, enabling the use of an efficient binary-coding weight calculation
method to significantly boost processing speed.

##  II GPTQT: quantize LLM twice

Figure 1: GPTQT: Quantize Weight Twice. Initially, the fp16 weight model is
quantized to a relatively high bit number (3 bits shown) using linear
quantization. Subsequently, the resulting int-type weight is further reduced
to fewer bits (2 bits depicted) using binary coding.

###  II-A Background

GPTQ. Based on Optimal Brain Quanization[12], GPTQ perform error compensation
with Hessian Matrix $H_{F}=2X_{F}X_{F}^{T}$, where $F$ denotes the set of
remaining full-precision weights. It first confirms the quantization
parameters row-wisely, then quantifies the weights column by column, and
updates the unquantized weights in real time.

$Goal:argmin_{w_{q}}\frac{(quant(w_{q})-w_{q})^{2}}{H_{F}^{-1}},$ (1)
$\delta_{F}=-(w_{q}-quant(w_{q}))([H_{F}^{-1}]_{qq})^{-1}(H_{F}^{-1})_{:,q}.$
(2)

The optimization goal is Equ.1, and the compensation is Equ.2 . The subscript
$q$ represents the weight being quantized.

Binary Coding Weight. Unlike linear quantization, which evenly distributes
several points across the original data range, binary coding weight sets
unequal representation intervals. Specifically, it represents the weight as
several binarized bits $b_{i}(\in\\{-1,+1\\})$, with each bit corresponding to
a floating point number $\alpha_{i}$. Its quantization and dequantization
process is shown as Equ. 3.

$\begin{matrix}quant:b_{i}=sign(r_{i-1}),\alpha_{i}=\frac{r_{i-1}^{T}b_{i}}{n},r_{i}=w-\sum_{j=1}^{i-1}\alpha_{j}b_{j},\\\
dequant:w_{dq}=\sum_{i=1}^{n}\alpha_{i}b_{i}.\end{matrix}$ (3)

Where $n$ is the number of quantization bits, $w_{dq}$ is the inverse
quantization result, and $r$ is the current quantization residual.

According to Equ.4, BCQ[10] uses an iterative method to alternately optimize
$\alpha$ and $b$, which reduces the MSE error, but still causes a non-
negligible loss of accuracy on LLM. It will be compared as a baseline.

$[\alpha_{1},...\alpha_{n}]=((B_{n}^{T}B_{n})^{-1}B_{n}^{T}w)^{T}.$ (4)

###  II-B Quantize Weight Twice

Intuitively, binary coding methods like BCQ, optimized from scratch, should
outperform Linear Quantization. Yet, experiments reveal that integrating BCQ
directly into the GPTQ method fails. GPTQ, which initially uses linear
quantization, sets quantization parameters, then quantizes column by column,
compensating earlier errors in subsequent columns. In this mechanism, weights
considered for quantization parameters differ from those actually quantized.
Therefore, the BCQ method that overfits the original weights loses its
generalization to GPTQ at this situation.

To address this, GPTQT employs a two-step progressive quantization as shown in
Fig. 1. Initially, linear quantization is used to quantize the weights to a
relatively high bits as $W_{int}$. Subsequently, critical points from this
output are selected and re-encoded using low-bit binary coding.

$\begin{matrix}step1:W_{int}=round(\frac{W}{S}-qbias),\\\ \\\
step2:argmin_{W_{q}}(W_{q}X),W_{q}=BinrayCoding(W_{int}).\end{matrix}$ (5)

In this process, $S$ represents the scaling factor for linear quantization,
$qbias$ is the quantization offset, $W_{int}$ denotes the intermediate high-
bit value from the first quantization step, and $Wq$ is the final quantized
weight.

To identify critical segments of $W_{int}$, GPTQT employs a grid search to
minimize output errors, serving as the optimization criterion.

The first step maintains finer representable distances and the
generalizability of linear quantization. It completes quantization with 5
bits. The second step reduces $W_{int}$ to a lower bit, for example, to 3
bits.

During the second step, from all integers representable after the first step,
select a few and convert the remainder to the nearest selected number. For
instance, if the weight is quantized to 3 bits initially, the numbers
${0,1,2,3,4,5,6,7}$ can be represented. For the binary coding step, you might
select numbers representable by 2 bits, such as ${0,1,6,7}$.”

$\begin{matrix}W_{int}=[0,2,3,1,1,6,5]\in\\{0\sim 2^{n-1}\\}\\\
BCchoice=[0,1,6,7]\\\ \\\ W_{q}=BinaryCoding(W_{int},BCchoice)\\\
=[0,1,1,1,1,6,6]\end{matrix}$ (6)

This process involves rounding from one integer to the nearest target integer,
denoted as $BCchoice$, which represents the target expressible in binary
coding. Since the first step initially reduces the number of weight bits, the
feasible $BCchoice$ options are limited, allowing for a sequential trial of
each possibility.

###  II-C Re-explore Scale Factor

Figure 2: Re-exploring scale factor.

In the initial step, floating point weight information is reduced to a
constrained set of integer numbers, making each one critical. Yet, the second
step further simplifies this information, instead of extracting directly from
the original data, leading to additional information loss.

To address the issues of overfitting or significant information loss, GPTQT
re-explore the scaling factor used in the first step.

We contend that the scaling factor $S$, determined in step 1, becomes
inadequate due to the modifications in the second step of quantization. This
second step introduces gaps in the uniformly distributed integer axis. Some
gaps may be too wide, significantly increasing quantization errors.

To mitigate this, we adjust the numerical axis like a spring, allowing it to
stretch and compress to an optimal degree, as shown in Fig.2, to identify the
best scale factor as per Equ.5.

For instance, if the weight is quantized to $n$ bits in step 1, then
$S=(W_{max}-W_{min})/(2^{n}-1)$. The exploration is conducted within the range
corresponding to $n-1$ and $n+1$ bits:

$\hat{S}\in(\frac{W_{max}-W_{min}}{2^{n+1}-1},\frac{W_{max}-W_{min}}{2^{n-1}-1})$
(7)

Where $\hat{S}$ represents the scaling factor determined through re-
exploration, with $W_{max}$ and $W_{min}$ being the maximum and minimum values
of the original weights, respectively.

GPTQT conducts a grid search within the range specified in Equ.7 to identify
the optimal value.

###  II-D Intermediate Steps Can be Fused in Inference

Figure 3: Binary coding is a unique variant of linear quantization, structured
in a tree-like form. GPTQT selects specific nodes and cotyledons from the
linear quantization tree to create a new binary coding tree, thus bypassing
intermediate steps during inference. Dark colors indicate final results while
light colors denote intermediate results.

Binary coding pushes the gaps between the quantized weight value in continuous
space to be different. Therefore, Linear quantization can be regarded as a
special form of binary coding. Specifically, consider wanting to quantize
weights to 2 bits using Linear quantization; the available integer weights
would be $W_{int}\in[-2,-1,0,1]$. To convert these back to floating point
numbers, a scaling factor $S$ and a quantization bias $qbias$ are employed.
The resulting dequantized weight is then expressed as $\hat{W}=S\times
W_{int}+qbias$. If set:

$\alpha_{2}=2^{-1}S,\alpha_{1}=2^{0}S,$ (8)

the points representable by binary coding are equivalent to those by linear
quantization. Given this characteristic, the entire quantization process can
be consolidated into a single binary coding expression during inference.

For instance, in Fig.3 (c), the process initially completes linear
quantization with 3 bits, followed by 2-bit binary coding. During fusion, the
result of linear quantization is first transformed into a binary coding
representation, and subsequently, the scaling factor $S$ and partial bit
$\alpha$ are integrated.

$\begin{matrix}\textbf{step1}:W_{int}\in\\{0,1,2,3,4,5,6,7\\}(3bit),\\\
W_{int}=\sum_{i=1}^{3}\alpha_{i}b_{i}+3.5,\\\
\alpha_{i}=2^{i-2},b_{i}=\\{+1,-1\\},\end{matrix}$ (9)

$\begin{matrix}\textbf{step2}:W_{q}=\sum_{i=1}^{2}\hat{\alpha_{i}}\hat{b_{i}}+3.5,\\\
\hat{\alpha_{1}}=2^{-1},\hat{\alpha_{2}}=2^{-0}+2^{1},\hat{b_{i}}\in\\{+1,-1\\}.\end{matrix}$
(10)

Where $\hat{\alpha_{i}},\hat{b_{i}}$ is the fused width floating point number
and binary value.

Then we also take the dequantization process of linear quantization into
consideration, and the final fused binary coding is expressed as:

$\begin{matrix}\textbf{fused}:W_{q}=\sum_{i=1}^{2}\hat{\alpha_{i}}\hat{b_{i}}+(3.5S+qbias),\\\
\hat{\alpha_{1}}=2^{-1}S,\hat{\alpha_{2}}=(2^{-0}+2^{1})S,\hat{b_{i}}\in\\{+1,-1\\}.\end{matrix}$
(11)

This approach enables the use of efficient binary coding calculation methods
like LUT-GEMM[13] during inference.

Given the limited binary coding options available in step 2, directly
performing a grid search to optimize Equ.5 is feasible when the bit number of
$Wq$ does not exceed 4 bits.

##  III Experiment

TABLE I: OPT perplexity (the lower the better) results on WikiText2.

Method | Bits | 125M | 350M | 1.3B | 2.7B | 6.7B | 13B | 30B | 66B
---|---|---|---|---|---|---|---|---|---
full | 16 | 27.65 | 22.00 | 14.63 | 12.47 | 10.86 | 10.13 | 9.56 | 9.34
RTN | 3 | 1.3e3 | 64.57 | 1.3e4 | 1.6e4 | 5.8e3 | 3.4e3 | 1.6e3 | 6.1e3
BCQ | 60.00 | 42.32 | 49.09 | 17.55 | 20.027 | 12.50 | 139.9 | 100.33
GPTQ | 53.85 | 33.79 | 20.97 | 16.88 | 14.86 | 11.61 | 10.27 | 14.16
GPTQT | 90.31 | 27.41 | 17.23 | 14.88 | 14.23 | 12.98 | 10.10 | 10.15
RTN | 2 | 5.4e3 | 2.8e4 | 1.1e4 | 9.5e3 | 2.8e4 | 1.9e5 | 1.6e5 | 1.7e5
BCQ | 484.32 | 2.0e3 | 3.8e3 | 616.3 | 1.7e4 | 4.9e3 | 7.7e3 | 6.2e3
GPTQ | 2.4e3 | 1.0e4 | 4.7e3 | 6.3e3 | 442.6 | 126.09 | 71.70 | 20.91
GPTQT | 5.6e3 | 706.3 | 248.3 | 56.03 | 91.21 | 27.82 | 13.26 | 12.53

TABLE II: Llama2 and Bloom perplexity results on WikiText2.

Method | Bits | Llama2-7b | Llama2-13b | Bloom-560m | Bloom-1.1b | Bloom-1.7b | Bloom-3b | Bloom-7.1b
---|---|---|---|---|---|---|---|---
full | 16 | 5.47 | 4.88 | 22.42 | 17.69 | 15.39 | 13.48 | 11.37
BCQ | 3 | 117.41 | 6872.46 | 48.87 | 46.37 | 24.723 | 21.02 | 17.29
GPTQ | 32.31 | 25.08 | 32.31 | 25.08 | 21.11 | 17.40 | 13.47
GPTQT | 12.80 | 6.27 | 38.39 | 22.56 | 20.97 | 17.53 | 12.41

The experiment primarily assesses the language generation task using
Perplexity as the performance metric for language models, which are notably
sensitive to model quantization[14]. Perplexity evaluates how effectively a
probability distribution or language model predicts a sample, essentially
measuring the model’s surprise when predicting the next word in a sequence.
Lower perplexity values signify superior performance, indicating greater model
confidence and less surprise with the data encountered. Additionally, GPTQT
not only reduces storage requirements but also enhances processing speed on
general-purpose GPUs. To demonstrate this, the time taken to generate a single
token is recorded.

###  III-A Setup

GPTQT is implemented in Pytorch and integrates with HuggingFace’s OPT,
BLOOM[15], and Llama[16] model families. Models with fewer than 13B parameters
are quantized on an A5000 GPU, while larger models are processed on an NVIDIA
A100 GPU with 80GB due to memory constraints. Calibration employs 128 random
slices of 2048 tokens each from the datasets.

Testing primarily utilized the WikiText2[17] and PTB[18] datasets.

Token generation speed was evaluated on an A5000 GPU. The test method involved
generating a sequence of 128 tokens with a batch size of 1 and timing this to
calculate the average token generation time. Notably, GPTQT also reduces
weight to 3 bits when measuring speed, aligning the communication overhead
with GPTQ. The speed improvement solely results from the adoption of more
efficient binary coding calculation methods. Given that the fp16 model
consumes more storage, model parallel technology was employed with as few GPUs
as possible.

###  III-B Result on OPT

TABLE III: OPT perplexity results on PTB.

Method | Bits | 125M | 350M | 1.3B | 2.7B | 6.7B | 13B | 30B
---|---|---|---|---|---|---|---|---
full | 16 | 32.55 | 26.08 | 16.96 | 15.11 | 13.08 | 12.34 | 11.84
BCQ | 3 | 70.59 | 52.53 | 112.06 | 22.98 | 23.61 | 14.74 | 258.74
GPTQ | 67.28 | 40.10 | 26.69 | 21.57 | 16.62 | 13.91 | 15.36
GPTQT | 110.53 | 36.59 | 22.87 | 19.03 | 16.26 | 12.51 | 12.56

Here, we primarily compare GPTQT with round-to-nearest (RTN) quantization,
GPTQ, and BCQ, all of which are quantization methods for LLMs using similar
technical approaches. Notably, 4-bit quantization for LLMs can be almost
lossless; thus, extensive GPTQT experiments focus on 3-bit and 2-bit outcomes,
as shown in Tab. I.

In 3-bit quantization, GPTQT outperforms most of the OPT model variants from
350M to 66B. Smaller models utilizing GPTQT exhibit lower perplexity. Given
that smaller models contain more compact information, this underscores GPTQT’s
advantages. As model size increases, the redundancy in information also
increases, and the improvements from GPTQT become less pronounced. However, on
opt-66B, where GPTQ shows notably poor results, GPTQT significantly reduces
perplexity by 4.01.

When reducing the quantization bit depth to 2-bit, both RTN and BCQ show a
complete collapse in performance, whereas GPTQT still maintains reasonable
perplexity, particularly in larger models. Under these stringent conditions,
GPTQT substantially outperforms GPTQ, demonstrating its superior capability to
extract important information during quantization. Specifically, GPTQT
achieves normal perplexity with a model size of 13B, whereas GPTQ requires a
model size of 66B to reach acceptable perplexity levels.

###  III-C Result on Llama2 and Bloom

As depicted in Tab. II, GPTQT also surpasses earlier quantization methods
across different types of LLMs.

Notably, for LLMs like Llama2 that utilize GRU instead of FFN, GPTQT
significantly outperforms BCQ and GPTQ. It reduces perplexity by 104.61 and
19.51 on the 7B model, and by 6e3 and 18.8 on the 13B model, respectively.
It’s evident that GPTQ struggles with Llama-like models, leading to severe
performance deterioration at 3-bit quantization, while GPTQT effectively
compensates for this deficiency. Moreover, BCQ completely fails on Llama2,
highlighting GPTQT’s ability to bridge the gap in binary coding methods for
this model type.

For Bloom models, GPTQT generally leads in performance. However, since GPTQ
performs relatively well with this type of LLM, its results are not far behind
those of GPTQT.

###  III-D Result on PTB dataset

OPT perplexity results on the PTB dataset are also provided in Tab.III,
demonstrating that GPTQT’s effectiveness is not limited to specific datasets.
For the OPT model, the perplexity trends on PTB mirror those observed on
WikiText2. It’s important to highlight that in 3-bit quantization, the GPTQ
method still experiences a notable performance decline on PTB. However, GPTQT
maintains performance close to the original fp16 model on opt-30B, with only a
minimal increase in perplexity of 0.72.

###  III-E Speed up of GPTQT

TABLE IV: The speed up of GPTQT (ms).

Method | Bits | 125M | 1.3B | 6.7B | 13B | 30B
---|---|---|---|---|---|---
full | 16 | 0.69 | 1.34 | 3.03 | 5.16 | 11.0
GPTQ | 3 | 1.01 | 2.01 | 2.7 | 3.34 | 4.01
GPTQT | 0.76 | 1.48 | 2.00 | 2.50 | 3.21

In low-throughput scenarios, the performance of generative LLMs is primarily
constrained by bandwidth. Weight quantization can substantially reduce
communication time, which is crucial to the noticeable speed improvement seen
with GPTQ. Notably, GPTQ dequantizes weights to fp16 in real-time during
computations, introducing a minor computational overhead.

For GPTQT, the savings in memory and bandwidth are comparable to those of
GPTQ, providing it with excellent potential for efficient operation. Moreover,
because its two-step quantization process can ultimately be merged into a
separate binary coding, GPTQT can utilize more efficient computation methods
specifically designed for binary coding, such as LUT-GEMM, resulting in more
significant speed improvements as model scale increases.

As detailed in Tab. IV, when the model size is small, bandwidth limitations
are less apparent, and the speed of GPTQ is even considerably slower than that
of fp16 models. However, as the model size increases to 30B, GPTQ enhances
speed by 2.75$\times$ due to bandwidth savings. GPTQT, using the more
efficient LUT-GEMM method, further boosts speed by an additional 1.24$\times$.

##  IV Ablation Study

In this section, we will present specific experiments to demonstrate the
effectiveness of our proposed ideas and methods.

###  IV-A Quantizaion Overfitting

TABLE V: Overfitting on GPTQ.

Method | 125M | 350M | 1.3B | 2.7B | 6.7B | 13B
---|---|---|---|---|---|---
GPTQ(Linear Quant) | 53.85 | 33.79 | 20.97 | 16.88 | 14.86 | 11.61
GPTQ(min MSE) | 59.38 | 35.29 | 93.76 | 73.61 | 71.53 | 15.22
GPTQ+BCQ | 213.22 | 34.59 | 142.68 | 71.31 | 52.66 | 45.09
GPTQT | 90.31 | 27.41 | 17.23 | 14.88 | 14.23 | 12.98

GPTQT employs a two-step quantization approach on LLMs to address the
overfitting issues inherent in the GPTQ method. Specifically, within GPTQ-
based strategies, the weights designated for parameter determination do not
match the final quantized weights. This discrepancy necessitates a
quantization method with adequate generalization capabilities.

To illustrate this point, two specific experimental setups are introduced.
GPTQ (min MSE) utilizes linear quantization and adjusts the clipping range via
grid search to minimize the MSE error between the original and quantized
weights. GPTQ+BCQ incorporates BCQ into the GPTQ framework, leveraging binary
coding to decrease quantization error by creating non-uniform quantization
intervals.

Despite significantly reducing the quantization error of the weights
themselves, as demonstrated in Tab.V, both methods perform substantially worse
than both GPTQT and the original GPTQ.

###  IV-B Intermediate Bit

In the first step, GPTQT quantizes the weight to a relatively high bit level
to assess the impact of this intermediate bit depth on the results. The
experiments explored quantization from 3 to 6 bits, with the second phase
finalizing at 3 bits. These experiments were conducted using opt-125M,
opt-350M, and opt-1.3B models, with perplexity reported on the WikiText2
dataset.

Figure 4: The impact of Intermediate Bit on results.

As indicated in Fig.4, it is necessary to select a relatively high
quantization bit in the first step . To strike a balance between search time
and final outcome, quantizing at 4 bits or 5 bits emerges as the optimal
choice.

###  IV-C Re-exploration

TABLE VI: Result on WikiText2 with different re-exploration range.

Range | opt-125M | opt-350M | opt-1.3B | opt-2.7B
---|---|---|---|---
0 | 399.51 | 27.41 | 17.79 | 15.08
1 | 96.41 | 28.13 | 17.23 | 14.88
2 | 90.31 | 27.51 | 20.06 | 15.91

Tab.VI illustrates the impact of re-exploration on the results, where ”range”
specifies the bit range used for exploring the scaling factor $S$. Results are
reported for a configuration using a 3-bit final quantization with an
intermediate 5-bit setting. Here, ”Range 0” indicates no re-exploration,
”Range 1” represents exploration of $S$ from 4 bits to 6 bits, and ”Range 2”
extends the exploration from 3 bits to 7 bits. This setup demonstrates how
adjusting the range of $S$ exploration can affect the final quantization
effectiveness.

###  IV-D Conclusion

In this paper, we identify overfitting as a significant issue in the
quantization process with GPTQ. To address this problem, we propose a Post
Train Quantization method for LLMs, named GPTQT, which divides the
quantization process into two progressive steps. Initially, weights are
quantized to a relatively higher bit with linear quantization. Subsequently,
they are converted into a lower bit binary coding representation. To manage
the change in representation range introduced by the second step, GPTQT re-
explores the scaling factor to enhance performance. During inference, these
two phases are merged into a pure binary coding representation, allowing the
use of more efficient computational methods to achieve acceleration. However,
we also note significant limitations: the activation values remain at fp16,
rendering GPTQT less suitable for high-throughput applications.

## References

  * [1] G. Yenduri, R. M, C. S. G, S. Y, G. Srivastava, P. K. R. Maddikunta, D. R. G, R. H. Jhaveri, P. B, W. Wang, A. V. Vasilakos, and T. R. Gadekallu, “Generative pre-trained transformer: A comprehensive review on enabling technologies, potential applications, emerging challenges, and future directions,” 2023.
  * [2] S. Zhang, S. Roller, N. Goyal, M. Artetxe, M. Chen, S. Chen, C. Dewan, M. Diab, X. Li, X. V. Lin, T. Mihaylov, M. Ott, S. Shleifer, K. Shuster, D. Simig, P. S. Koura, A. Sridhar, T. Wang, and L. Zettlemoyer, “Opt: Open pre-trained transformer language models,” 2022.
  * [3] G. Xiao, J. Lin, M. Seznec, H. Wu, J. Demouth, and S. Han, “SmoothQuant: Accurate and efficient post-training quantization for large language models,” in Proceedings of the 40th International Conference on Machine Learning (A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, eds.), vol. 202 of Proceedings of Machine Learning Research, pp. 38087–38099, PMLR, 23–29 Jul 2023.
  * [4] T. Dettmers, M. Lewis, Y. Belkada, and L. Zettlemoyer, “Gpt3.int8(): 8-bit matrix multiplication for transformers at scale,” in Advances in Neural Information Processing Systems (S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, eds.), vol. 35, pp. 30318–30332, Curran Associates, Inc., 2022.
  * [5] T. Dettmers, A. Pagnoni, A. Holtzman, and L. Zettlemoyer, “Qlora: Efficient finetuning of quantized llms,” in Advances in Neural Information Processing Systems (A. Oh, T. Neumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, eds.), vol. 36, pp. 10088–10115, Curran Associates, Inc., 2023.
  * [6] Y. Xu, L. Xie, X. Gu, X. Chen, H. Chang, H. Zhang, Z. Chen, X. ZHANG, and Q. Tian, “QA-loRA: Quantization-aware low-rank adaptation of large language models,” in The Twelfth International Conference on Learning Representations, 2024.
  * [7] J. Lin, J. Tang, H. Tang, S. Yang, X. Dang, C. Gan, and S. Han, “Awq: Activation-aware weight quantization for llm compression and acceleration,” 2023.
  * [8] E. Frantar, S. Ashkboos, T. Hoefler, and D. Alistarh, “OPTQ: Accurate quantization for generative pre-trained transformers,” in The Eleventh International Conference on Learning Representations, 2023.
  * [9] W. Huang, Y. Liu, H. Qin, Y. Li, S. Zhang, X. Liu, M. Magno, and X. Qi, “Billm: Pushing the limit of post-training quantization for llms,” 2024.
  * [10] S. J. Kwon, D. Lee, Y. Jeon, B. Kim, B. S. Park, and Y. Ro, “Post-training weighted quantization of neural networks for language models,” 2021.
  * [11] M. Rastegari, V. Ordonez, J. Redmon, and A. Farhadi, “Xnor-net: Imagenet classification using binary convolutional neural networks,” 2016.
  * [12] E. Frantar, S. P. Singh, and D. Alistarh, “Optimal brain compression: A framework for accurate post-training quantization and pruning,” 2023.
  * [13] G. Park, B. park, M. Kim, S. Lee, J. Kim, B. Kwon, S. J. Kwon, B. Kim, Y. Lee, and D. Lee, “LUT-GEMM: Quantized matrix multiplication based on LUTs for efficient inference in large-scale generative language models,” in The Twelfth International Conference on Learning Representations, 2024.
  * [14] Z. Yao, R. Yazdani Aminabadi, M. Zhang, X. Wu, C. Li, and Y. He, “Zeroquant: Efficient and affordable post-training quantization for large-scale transformers,” in Advances in Neural Information Processing Systems (S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, eds.), vol. 35, pp. 27168–27183, Curran Associates, Inc., 2022.
  * [15] B. Workshop, “Bloom: A 176b-parameter open-access multilingual language model,” 2023.
  * [16] H. Touvron, T. Lavril, G. Izacard, X. Martinet, M.-A. Lachaux, T. Lacroix, B. Rozière, N. Goyal, E. Hambro, F. Azhar, A. Rodriguez, A. Joulin, E. Grave, and G. Lample, “Llama: Open and efficient foundation language models,” 2023.
  * [17] S. Merity, C. Xiong, J. Bradbury, and R. Socher, “Pointer sentinel mixture models,” 2016.
  * [18] M. Dinarelli and L. Grobol, “Seq2biseq: Bidirectional output-wise recurrent neural networks for sequence modelling,” 2019.