Methods for estimating of continuants, corrected version.

I. D. Kan

Abstract. The purpose of was as follows. “We consider special sets of
continuants which occur in applications. For these sets we solve the problem
of finding maximal and minimal continuants. There are several methods for
finding extremum such as thee: mathod of basic substitutions (section 4.1),
method of quadratic irrationalities (section 4.2), majorizing inequalities
(section 4.3) and unit variation (section 4.4).” Unfortunately, the text of
was littered with numerous typos, making it difficult to read. This defect is
corrected in the present work. In addition, some of the statements are now
provided with more detailed evidence.

##  1  Introduction.

######  ?contentsname?

  1. 1  Introduction.
  2. 2  Notation and parameters.
  3. 3  Main results.
  4. 4  Auxilary statements.
    1. 4.1  Basic substitution method.
    2. 4.2 Quadratic irrationalities’ method.
    3. 4.3  Majorizing inequalities’ method.
    4. 4.4  Unit variation method.
    5. 4.5  Lemmas concerning systems of (in)equalities.
  5. 5  Proof of main theorems.
    1. 5.1 Proof of Theorem 1.
    2. 5.2 Other proof of Theorem 3.1.
    3. 5.3 Proof of Theorem 3.2.
    4. 5.4 Other proof of Theorem 3.2.
    5. 5.5 Proof of Theorem 3.3.
    6. 5.6 Other proof of Theorem 3.3.
    7. 5.7 Proof of Theorem 3.4.
    8. 5.8 Proof of Theorem 3.5.
    9. 5.9 Proof of Theorem 3.6.
    10. 5.10 Proof of Theorem 3.7.

For integer $t\geq 0$ and positive integers $a_{1},a_{2},\ldots,a_{t}$ the
continuant $\langle a_{1},a_{2},\ldots,a_{t}\rangle$ is defined inductively by
equalities $\langle\varnothing\rangle=1$, $\langle a_{1}\rangle=a_{1}$,

$\langle a_{1},a_{2},\ldots,a_{j+1}\rangle=a_{j+1}\langle
a_{1},a_{2},\ldots,a_{j}\rangle+\langle a_{1},a_{2},\ldots,a_{j-1}\rangle,$
(1.1)

$j=1,2,\ldots,t-1$. For a continued fraction

$[a_{0};a_{1},a_{2},\ldots,a_{t}]=a_{0}+\cfrac{1}{a_{1}+\cfrac{1}{a_{2}+{\atop\ddots\,\displaystyle{+\cfrac{1}{a_{t}}}}}},$
(1.2)

we know (see, [2]) that

$[a_{0};a_{1},a_{2},\ldots,a_{t}]=\frac{\langle
a_{0},a_{1},\ldots,a_{t}\rangle}{\langle a_{1},a_{2},\ldots,a_{t}\rangle}.$
(1.3)

We suppose the continued fraction of the empty set to be equal to zero.

Usually it is necessary to consider kontinualts with elements boulded from
above by $n$ (see [3]-[6]). In certain problems in number theory (see [5]) the
following condition occurs:

$a_{1}+a_{2}+\ldots+a_{t}=S,\,\,\,\,S/t\ll{const}.$

Such restrictions define certain sets of continuants. The problem arises is to
find the maximal and the minimal value of continuant over these sets. Some
results related to this problem were obtained in [7, 8, 9]. In the present
paper we obtain further reuslts.

The author is grateful to Prof. N. Moshchevitin for setting the problem and
for idea of method of section 4.4.

##  2  Notation and parameters.

For $a,b\in\mathbb{N}\cup\\{0\\}$ put

$a^{\\{b\\}}=\begin{cases}\underbrace{\\{a,a,\ldots,a\\}}\limits_{\mbox{$b$
\text{elements}}},&\mbox{if $b\geq 1$},\cr\varnothing,&\mbox{ if
$b=0$}\end{cases}.$

For a collection of finite sequences $A_{1},A_{2},\ldots,A_{k}$ by
$\\{A_{1},A_{2},\ldots A_{k}\\}$ we define the sequence of all consecutive
elements of $A_{1},A_{2},\ldots A_{k}$

Consider $f$ natual numbers $h_{1}<h_{2}<\ldots<h_{f}$ with multiplicities
$p_{1},p_{2},\ldots,p_{f}\geq 1$. Let’s put it

$W_{f}=W_{f}(\bar{h},\bar{p})=\left\\{(a_{1},a_{2},\ldots,a_{t}):a_{i}\in\\{h_{1},h_{2},\ldots,h_{f}\\},\,\,|\\{i:a_{i}=h_{j}\\}|=p_{j}\right\\},$

where $t=p_{1}+\ldots+p_{f}$. Consider a partition of each
$p_{1},\ldots,p_{f}$ into a sum

$p_{j}=l_{j}+r_{j}$ (2.1)

of two nonnegative $l_{j}$, $r_{j}$ and put

$D_{f}=D_{f}(\bar{l},\bar{r})=\left\\{h_{f}^{\\{l_{f}\\}},h_{f-1}^{\\{l_{f-1}\\}},\ldots,h_{2}^{\\{l_{2}\\}},h_{1}^{\\{l_{1}\\}},h_{1}^{\\{r_{1}\\}},h_{2}^{\\{r_{2}\\}},\ldots,h_{f}^{\\{r_{f}\\}}\right\\}.$

Define

$V_{f}=V_{f}(\bar{h},\bar{p})=\left\\{(a_{1},a_{2},\ldots,a_{t})\in
W_{f}(\bar{h},\bar{p}):a_{1}=h_{1}\right\\}.$

Moreover for $S,t,n\in\mathbb{N}$ put

$U(S,t,n)=\left\\{(a_{1},a_{2},\ldots,a_{t}):a_{i}\in\\{1,2,\ldots,n\\},a_{1}+a_{2}+\ldots+a_{t}=S\right\\},$
$U_{n}(S)=\bigcup\limits_{t}U(S,t,n),\,\,\,U(S,t)=\bigcup\limits_{n}U(S,t,n).$

Here by $[\xi],\\{\xi\\}$ we denote integer part and fractional part for
$\xi\in\mathbb{R}$, correspondingly.

From the set $W_{f}(\bar{h},\bar{p})$ we extract two monotone sequences

$b_{0}\leq{b_{1}}\leq\ldots\leq{b_{t-1}}$ (2.2)

and

$c_{1}\geq{c_{2}}\geq\ldots\geq{c_{t}}.$ (2.3)

For $j=0,1,\ldots,t$ and $\nu=1,2,\ldots,2[t/2]$ put

$n_{j}=\left\\{\begin{array}[]{cl}b_{j},\,\,\mbox{if}\,\,j\equiv 0\pmod{2},\\\
c_{j},\,\,\mbox{if}\,\,j\equiv
1\pmod{2},\end{array}\right.m_{\nu}=\left\\{\begin{array}[]{cl}c_{\nu},\,\,\mbox{if}\,\,\nu\equiv
0\pmod{2},\\\ b_{\nu},\,\,\mbox{if}\,\,\nu\equiv 1\pmod{2}.\end{array}\right.$

For $m\in\mathbb{N}\cup\\{0\\}$ put $m_{-}=[m/2]$, $m_{+}=m-m_{-}$. For
$x\in\mathbb{Z}$,$n,z\in\mathbb{N}$ define

$N_{z}(x)=\left\\{\begin{array}[]{lc}\left\\{n^{\\{x\\}},z\right\\},&\mbox{ if
x}\geq 0,\\\ \left\\{1^{\\{-1-x\\}},z,1\right\\},&\mbox{ if
x}<0,\end{array}\right.$ (2.4)
$T_{z}(m,x)=\langle\underbrace{1,n,1,n,\ldots,1,n}_{2m_{+}\mbox{elements}},N_{z}(x),\underbrace{n,1,n,1\ldots,n,1}_{2m_{-}\mbox{elements}}\rangle.$
(2.5)

For $S,n\in\mathbb{N}$ define

$S_{0}^{(n)}=(n+1)\left\\{\frac{S-1}{n+1}\right\\}+1,\,\,\,\,\,\,S_{1}^{(n)}=n\left\\{\frac{S}{n}\right\\}.$
(2.6)

We define a subset $P(S)$ of the set $\\{1,2,\ldots,n-1\\}$ by the condition

$P(S)=\left\\{\begin{array}[]{ll}\\{1,2,\ldots,n-1\\},&\mbox{if
}S\geq{n^{2}-1},\\\ \\{S_{0}^{(n)},S_{0}^{(n)},\ldots,S_{1}^{(n)}\\},&\mbox{if
}S<n^{2}-1\,\mbox{and }S_{0}^{(n)}\leq S_{1}^{(n)},\\\
\\{1,2,\ldots,S_{1}^{(n)}\\}\bigcup\,\\{S_{0}^{(n)},S_{0}^{(n)}+1,\ldots,n-1\\}&\mbox{in
the opposite case.}\end{array}\right.$ (2.7)

##  3  Main results.

######  Theorem 3.1.

[7] The maximal continuant over the set $V_{f}(\bar{h},\bar{p})$ satisfies

$\max\limits_{V_{f}}\langle a_{1},a_{2},\ldots,a_{t}\rangle=\langle
b_{0},b_{1},\ldots,b_{t-1}\rangle,$ (3.1)

where the maximum is taken over all permutations of the sequence
$\\{a_{1},a_{2},\ldots,a_{t}\\}$.

######  Theorem 3.2.

The maximal continuant over the set $W_{f}(\bar{h},\bar{p})$ satisfies

$\max_{W_{f}}\langle a_{1},a_{2},\ldots,a_{t}\rangle=\langle
D_{f}(\bar{l},\bar{r})\rangle,$ (3.2)

here integers $l_{j}$ and $r_{j}$ $(j=1,2,...,f)$ from (2.1) are such that

$1=\left\\{\begin{array}[]{cll}l_{j},&\mbox{if}\,\,j\equiv f&\pmod{2},\\\
r_{j},&\mbox{if}\,\,j\equiv f-1&\pmod{2}.\end{array}\right.$ (3.3)

######  Theorem 3.3.

The minimal continuant over the set $W_{f}(\bar{h},\bar{p})$ satisfies

$\min_{W_{f}}\langle a_{1},a_{2},\ldots,a_{t}\rangle=\langle
n_{0},n_{1},\ldots,n_{\nu},m_{\mu},m_{\mu-1},\ldots,m_{2},m_{1}\rangle,$ (3.4)

where $\,\,\,\,\nu=t_{+}-1$, $\mu=t_{-}$.

######  Theorem 3.4.

The maximal continuant over the set $U_{n}(S)$ satisfies

$\max_{U_{n}(S)}\langle
a_{1},a_{2},\ldots,a_{t}\rangle=\langle\underbrace{1,1,\ldots,1}_{S\text{
elements}}\rangle.$ (3.5)

######  Theorem 3.5.

For $2\leq t\leq S$ the maximal continuant over the set $U(S,t)$ satisfies

$\max_{U(S,t)}\langle
a_{1},a_{2},\ldots,a_{t}\rangle=\left\\{\begin{array}[]{lc}\langle
h_{1}^{\\{t\\}}\rangle,&\mbox{if}\,\,S\equiv 0\pmod{t},\\\ \langle
h_{2},h_{1}^{\\{c\\}},h_{2}^{\\{d-1\\}}\rangle,&\mbox{ --- in the opposite
case,}\end{array}\right.$ (3.6)

where

$h_{1}=[S/t],\,\,\,h_{2}=h_{1}+1,\,c=t\\{-S/t\\},\,d=t\\{S/t\\}.$ (3.7)

######  Theorem 3.6.

For $2\leq t\leq S\leq nt$ the minimal continuant over the set $U(S,n,t)$
satisfiies

$\min_{U(S,n,t)}\langle a_{1},a_{2},\ldots,a_{t}\rangle=T_{z}(m,x),$ (3.8)

where

$z\in\\{1,2,\ldots,n-1\\},\,\,\,\,z\equiv S-t+1\pmod{(n-1)},$ (3.9)
$x=\frac{2(S-t+1-z)}{n-1}+1-t,\,\,\,\,\,m=(t-|x|-1)/2.$ (3.10)

######  Theorem 3.7.

For $n\geq 2$, $S\geq 2n+2$ the minimal continuant over the set $U_{n}(S)$
satisfies

$\min_{U_{n}(S)}\langle a_{1},a_{2},\ldots,a_{t}\rangle=\min_{z\in
P^{*}(S)}T_{z}(m,x),$ (3.11)

where

$0\leq x\leq n,\,x\equiv z-S\pmod{(n+1)},\,\,\,\,m=m(z)=\frac{S-z-nx}{n+1},$
(3.12) $P^{*}(S)=\\{z\in P(S):\,m(z)\geq 1\\}.$

Corolary 1. For $2\leq n\leq S-2$ one has

$\min_{U_{n}(S)}\langle
a_{1},a_{2},\ldots,a_{t}\rangle\geq\frac{\left(\sqrt[n+1]{\mu_{n}}\right)^{S-n+1}}{e^{2}},$
(3.13)

where

$\mu_{n}=\frac{n+2+\sqrt{n^{2}+4n}}{2}.$ (3.14)

######  Remark 3.1.

In [3] for the minimum form Corollary 1 for $n=4$ the authors use the lower
bound of the form $\left(\sqrt{2+10^{-6}}\right)^{S}$. The inequality (3.13)
gives a lower bound of the form $\left(\sqrt[5]{3+\sqrt{8}}\right)^{S}$. For
large values of $S$ (for $S\geq 350$) this bound is more precise as

$\sqrt[5]{3+\sqrt{8}}=1,424\ldots>1,414\ldots=\sqrt{2+10^{-6}}.$

######  Remark 3.2.

The 3.4 theorem, given here for ”completeness”, should be considered part of
mathematical folklore: it is quite obvious and is used in many works. For
example, N. M. Korobov in 1997 in the work [10] formulated some algorithm
related to continued fractions. The proof of this result (which he left to his
readers) seems to rely in part on the 3.4 theorem.

######  Remark 3.3.

Statements of problems on calculating the maximum and minimum from the 3.2 and
3.3 theorems are available in the book by D. E. Knuth [11]. The solution of
the second one coincides with the formulation of the 3.3 theorem.

##  4  Auxilary statements.

###  4.1  Basic substitution method.

Let us consider the inequality

$\langle
u_{1},u_{2},\ldots,u_{\alpha},v_{1},v_{2},\ldots,v_{\beta},w_{1},w_{2},\ldots,w_{\gamma}\rangle\leq\langle
u_{1},u_{2},\ldots,u_{\alpha},v_{\beta},v_{\beta-1},\ldots,v_{2},v_{1},w_{1},w_{2},\ldots,w_{\gamma}\rangle.$
(4.1)

######  Lemma 4.1.

[8]. For $v_{1}\neq v_{\beta}$, $u_{\alpha}\neq w_{1}$ the inequality (4.1) is
valid if and only if

$(v_{1}-v_{2})(u_{\alpha}-w_{1})<0.$ (4.2)

Put

$[\stackrel{{\scriptstyle\leftarrow}}{{U}}]=[0;u_{\alpha},u_{\alpha-1},\ldots,u_{2},u_{1}],$
(4.3) $[\overline{W}]=[0;w_{1},w_{2},\ldots,w_{\gamma}],$ (4.4)
$[\overline{V}]=[0;v_{1},v_{2},\ldots,v_{\beta}],$
$[\stackrel{{\scriptstyle\leftarrow}}{{V}}]=[0;v_{\beta},u_{\beta-1},\ldots,u_{2},u_{1}],$
${\bf
a^{\prime}}(U,V,W)=([\stackrel{{\scriptstyle\leftarrow}}{{U}}]-[\overline{W}])(v_{1}-v_{\beta}),$
(4.5) ${\bf
a}(U,V,W)=([\stackrel{{\scriptstyle\leftarrow}}{{U}}]-[\overline{W}])([\stackrel{{\scriptstyle\leftarrow}}{{V}}]-[\overline{V}]).$
(4.6)

In order to use Lemma 4.1 with $[\stackrel{{\scriptstyle\leftarrow}}{{U}}]=0$
or $[\overline{W}]=0$ it is convenient to put $u_{\alpha}=+\infty$ or
$w_{1}=+\infty$. We suppose that adding the sigh “infinity” does not change
the value of the continuant or continued fraction’s value, by the definition.
The sign “infinity” may appear in the inequality (4.2).

######  Lemma 4.2.

[7] For $v_{1}\neq v_{\beta}$ the inequality (4.1) is valid if and only if one
of two foollowing groups of conditions are valid:

the first group

$v_{1}>v_{\beta},\,\,[\stackrel{{\scriptstyle\leftarrow}}{{U}}]\geq[\overline{W}],$

or the second group

$v_{1}<v_{\beta},$ (4.7)
$[\stackrel{{\scriptstyle\leftarrow}}{{U}}]\leq[\overline{W}].$ (4.8)

In other words, the inequality (4.1) holds if and only if

${\bf a}(U,V,W)\geq 0;$

or, if and only if

${\bf a^{\prime}}(U,V,W)\geq 0.$

Moreover the inequality (4.1) turns into an equality if and only if
$[\stackrel{{\scriptstyle\leftarrow}}{{U}}]=[\overline{W}]$, where
$[\stackrel{{\scriptstyle\leftarrow}}{{U}}],[\overline{W}],$ ${\bf a}(U,V,W)$,
${\bf a^{\prime}}(U,V,W)$ are defined in (4.3) — (4.6).

######  Definition 4.1.

Suppose $\alpha+\beta+\gamma=t$,

$\\{a_{1},a_{2},\ldots,a_{t}\\}=\\{u_{1},u_{2},\ldots,u_{\alpha},v_{1},v_{2},\ldots,v_{\beta},w_{1},w_{2},\ldots,w_{\gamma}\\}.$
(4.9)

Suppose $\Pi$ to be a substitution of indices $\\{1,2,\ldots,t\\}$, which
changes the sequence (4.9) into the sequence

$\left\\{a_{\Pi(1)},a_{\Pi(2)},\ldots,a_{\Pi(t)}\right\\}=\\{u_{1},u_{2},\ldots,u_{\alpha},v_{\beta},v_{\beta-1},\ldots,v_{2},v_{1},w_{1},w_{2},\ldots,w_{\gamma}\\}.$
(4.10)

The we define $\Pi$ to be a basic substitution with the middle part
$(v_{1},\ldots,v_{\beta})$ or briefly $(\alpha+1,\alpha+\beta)$-substitution.

The simplest property is the symmetry of continuants (see [8]):

$\langle a_{1},a_{2},\ldots,a_{t}\rangle=\langle
a_{t},a_{t-1},\ldots,a_{2},a_{1}\rangle.$ (4.11)

Another simple property is the property of “unit extraction”:

$\langle a_{1}+1,a_{2},\ldots,a_{t}\rangle=\langle
1,a_{1},a_{2},\ldots,a_{t}\rangle.$ (4.12)

######  Definition 4.2.

A basic substitution $\Pi$ we define to be trivial with respect to the
sequence (4.9), if the continuant (4.9) is equal to the continuant (4.10), and
this equality may be proved by means (4.11) and (4.12) only.

Example 1. The substitution $\Pi:(2,4,5,1,1)\mapsto(2,5,4,1,1)$ is trivial as
from (4.11) and (4.12) it follows that

$\langle 2,4,5,1,1\rangle=\langle 1,1,4,5,1,1\rangle=\langle
1,1,5,4,1,1\rangle=\langle 2,5,4,1,1\rangle.$

######  Remark 4.1.

If a basic substitution does not change the value of a continuant then this
substitution is trivial.

######  Definition 4.3.

Consider a basic substitution $\Pi$ with the middle
$(v_{1},v_{2},\ldots,v_{\beta})$. Supposse the inequality (4.1) to be strict
one (not necessary strict one). Then we define the basic substitution to be
increasing (non-decreasing) with respect to the sequence (4.9). Analogously in
the case of strict (not necessary strict) inequality opposite to (4.1) we
define $\Pi$ to be decreasing (non-increasing) with respect to the sequence
(4.9).

Suppose that $1\leq k<l\leq t$. Then the sequence
$\\{a_{k},a_{k+1},\ldots,a_{l}\\}$ we define to be a $(k,l)$-fragment of the
sequence $\\{a_{1},a_{2},\ldots,a_{t}\\}$ with boundaries $a_{k}$ and $a_{l}$.
For $k\neq 1$ or $l\neq t$ the boundaries $a_{k}$ and $a_{l}$
(correspondingly) we define as the proper boundaries.

######  Remark 4.2.

If a basic substitution is increasing (decreasing) for a fragment of a
sequence with a middle which does not contain proper boundaries of the
fragment the this substitution is increasing (decreasing) for the whole
sequence itself.

(In general, this property is no longer valid for trivial substitutions.)

######  Lemma 4.3.

For integers $r,h,g$ under the conditions $r\geq 0,\,0<h<g\leq+\infty$ one has

$[0;h^{\\{r\\}},g]\leq 1/h.$ (4.13)

Moreover (4.13) turns into an equality only in the case $r=1$, $g=+\infty$.

######  Lemma 4.4.

The maximal continuant over the set $W_{f}(\bar{h},\bar{p})$ is attained on a
sequence $D_{f}(\bar{l},\bar{r})$ with elements satisfying (2.1).

Proof.

Suppose that the maximal continuant over the set $W_{f}(\bar{h},\bar{p})$ is
attained on the sequence $D=\\{a_{1},\ldots,a_{t}\\}$. Suppose that for a
certain value of $\nu\in\\{1,2,\ldots,t\\}$ one has $a_{\nu}=h_{1}$. Consider
two basic substitutions $\Pi$ and $\Phi$ acting on $(1,\nu)$\- and
$(\nu,t)$-fragments of $D$, correspondingly. Suppose that these substitutions
satisfy $a_{\Pi(\nu)}=a_{\Phi(\nu)}=h_{1}$. Then $\Pi$ and $\Phi$ are non-
increasing for the corresponding fragments. Then from Theorem (3.1 (Theorem
(3.1 is proved without application of Lemma (5.2) we know the srtucture of the
fragments under consideration. We take into account Remark (4.2). Lemma
follows.

######  Lemma 4.5.

Suppose that elements of the sequence $D_{f}(\bar{l},\bar{r})$ satisfy

$l_{f}=1,\,r_{f}=0,\,r_{f-1}>0$ (4.14)

Suppose that for this sequence the exist no increasing basic substitutions.
Then elements of the sequence $D_{f}$ satisfy (3.3).

Proof.

Suppose that $f\geq 3$ (otherwise there is nothing to prove). Now we process
induction in $f$. By the assumption, the equality (3.3) is true for $j=f$. We
will show that $r_{f-1}=1$ and $l_{f-2}>0$. Assume that it is not so. Supoose
that $r_{f-1}>1$ or $(r_{f-1}=1)\;\&(l_{f-2}=0)$. For both of these cases we
can consider an $(l_{f-1}+2,t-1)$-basic substitution. Now we allpy Lemma 4.2.
inequality (4.7) is valid, by the construction. We have also a strict
inequality in (4.8), by Lemma 4.3. Hence the substitution $\Pi$ is an
increasing substitution. So for $(l_{f-1}+2,t)$-fragment of the sequence
$D_{f}$ we prove that

$r_{f-1}=1,\,l_{f-1}=0,\,l_{f-2}>0.$ (4.15)

Equality (4.15) with respect to the symmetry coinside with condition (4.14),
for a smalller value of $f$. By remark 3 we can apply the inductive
assumption. Lemma is proved.

Suppose that for a certain $i\geq 0$ and for sequences $\\{b_{j}\\}$ and
$\\{c_{j}\\}$ defined in (4) one has

$b_{i+1}=h_{u}\leq h_{v}=c_{i+1},$ (4.16)

where $\\{h_{i}\\}$ is the sequence from the definition of values $W_{f}$. Put

$H(i)=\\{h_{u},h_{u+1},\ldots,h_{v}\\}.$

Then $H(i)\neq\varnothing$.

######  Lemma 4.6.

Under the condition (4.16) for the numbers $s_{1},s_{2},\ldots,s_{k}\in H(i)$,
$k\geqslant 0$, one has

$[0;n_{i},n_{i-1},\ldots,n_{0}]-[0;s_{1},s_{2},\ldots,s_{k},m_{i},m_{i_{1}},\ldots,m_{1}]\left\\{\begin{array}[]{ll}\geq
0,\text{if }i\equiv 0\pmod{2},\\\ \leq 0,\text{if }i\equiv
1\pmod{2},\end{array}\right.$ (4.17)

Proof.

By the definition for every $j=1,2,\ldots,k$ one has

$c_{1}\geq c_{2}\geq\ldots\geq c_{i+1}\geq s_{j}\geq b_{i+1}\geq
b_{i}\geq\ldots\geq b_{1}>b_{0}.$

That is why inequalities (4.17) follows from the usisl rule of comparing
continued fractions’ values step by step, with respect to the parity of the
step (of course here we should consider separate case of odd $k$ and even
$k$). Lemma is proved.

###  4.2 Quadratic irrationalities’ method.

By induction define $K_{l,n}$. Put

$K_{0,n}=1,\,K_{1,n}=n+2,\,K_{j+1,n}=(n+2)K_{j,n}-K_{j-1,n},\,\,j=1,2,\ldots,n-1.$

######  Lemma 4.7.

For $l\geq 1$ one has

$\underbrace{\langle{1,n,1,n,\ldots,1}\rangle}\limits_{\mbox{$2l-1$
\text{elements}}}=K_{l-1,n},$ (4.18)
$\underbrace{\langle{n,1,n,1,\ldots,n}\rangle}\limits_{\mbox{$2l-1$
\text{elements}}}=nK_{l-1,n},$ (4.19) $\underbrace{\langle
1,n,1,n,\ldots,1,n\rangle}\limits_{\mbox{$2l$
\text{elements}}}=K_{l,n}-K_{l-1,n}.$ (4.20)

This lemma obviosly follows by induction in $l$.

Put

$k_{l,n}=\langle
n^{\\{l\\}}\rangle,\,\,\,\,\,\,\lambda_{n}=\frac{n+\sqrt{n^{2}+4}}{2}.$

######  Lemma 4.8.

The following equalities are valid:

$k_{l,n}=\left|\left|\frac{\lambda_{n}^{l+2}}{\lambda_{n}^{2}+1}\right|\right|,\,\,\,\,\,\,\,K_{l,n}=\left[\frac{\mu_{n}^{l+2}}{\mu_{n}^{2}-1}\right].$
(4.21)

Here $\mu_{n}$ is defined in (3.14).

For $K_{l,n}$ an equatity which was proved in [3] is very close to (4.21). We
should note that our equality (4.21) for $k_{l,n}$ may be proved apsolutely
analogouslely to those from [3].

######  Lemma 4.9.

For $n>8$ one has

$\frac{1+(1/\lambda_{n}^{2})}{1-(1/\mu_{n}^{2})}\left(\frac{\mu_{n}}{\lambda_{n}}\right)^{n}<\frac{41}{40}e^{2}.$
(4.22)

To prove this lemma one should apply inequalities

$n\leq\lambda_{n}\leq{n+1}\leq\mu_{n}\leq{n+2}$

as well as the inequality $(1+1/n)^{n}<e$.

######  Lemma 4.10.

The following inequalities are valid:

$K_{n,n}-K_{n-1,n}<k_{n+1,n},\,\,K_{n-1,n}<k_{n,n},$ (4.23)
$n>\frac{nK_{n-1,n}-k_{n,n}}{k_{n+1,n}-K_{n,n}}.$ (4.24)

Proof. For $n\leq 8$ one can easily chech (4.23) and (4.24). For $n>8$ one
should replace the values in the inequalities by the corresponding values from
Lemma 4.8 and divide by $\lambda_{n}^{n}$. Then one should apply (4.22). Lemma
is proved.

###  4.3  Majorizing inequalities’ method.

For $i,k\in\mathbb{N}$, $j\in\mathbb{N}\cup\\{0\\}$ we consider

$L=\langle x_{1},\ldots,x_{i},z_{1},\ldots,z_{j}\rangle,$

and

$M=\langle y_{1},y_{2},\ldots,y_{k},z_{1},z_{2},\ldots,z_{j}\rangle,$

with the common tale $(z_{1},z_{2},\ldots,z_{j})$.

######  Definition 4.4.

We say that a continuant $M$ is majorized by a continuant $L$ (the notation
$M\preceq L$) if

$\langle y_{1},y_{2},\ldots,y_{k}\rangle\leq\langle
x_{1},x_{2},\ldots,x_{i}\rangle,$ (4.25) $\langle
y_{1},y_{2},\ldots,y_{k-1}\rangle\leq\langle
x_{1},x_{2},\ldots,x_{i-1}\rangle.$ (4.26)

In the case when we have strict inequalities in (4.25), (4.26) or the
inequality in (4.25) is a strict one and $j\geq 1$ we say that $M$ is strictly
majorized by $L$ (notation $M\prec L$).

######  Lemma 4.11.

For $i\geq 2$ one has

$\langle
x_{1},x_{2},\ldots,x_{i-1},1,z_{1},z_{2},\ldots,z_{j}\rangle\succ\langle
x_{1},x_{2},\ldots,x_{i-1}+1,z_{1},z_{2},\ldots,z_{j}\rangle.$

A proof of lemma 4.11 easily follows from

$\langle x_{1},x_{2},\ldots,x_{i-1},1\rangle=\langle
x_{1},x_{2},\ldots,x_{i-1}+1\rangle,$ $\langle
x_{1},x_{2},\ldots,x_{i-1}\rangle>\langle x_{1},x_{2},\ldots,x_{i-2}\rangle.$

######  Lemma 4.12.

If $M\preceq L$ then $M\leq L$. Moreover if $M\prec L$ then $M<L$.

A proof of lemma 4.12 easily follows from the well-known formula

$\langle x_{1},\ldots,x_{i},z_{1},\ldots,z_{j}\rangle=\langle
x_{1},\ldots,x_{i}\rangle\langle z_{1},\ldots,z_{j}\rangle+\langle
x_{1},\ldots,x_{i-1}\rangle\langle z_{1},\ldots,z_{j-1}\rangle$ (4.27)

(see [8]) and from (4.25), (4.26).

######  Lemma 4.13.

Suppose that $jz_{1}>1$ and the inequality in (4.25) is a strict one. In
addition suppose that

$\langle y_{1},y_{2},\ldots,y_{k-1},y_{k}+1\rangle\leq\langle
x_{1},x_{2},\ldots,x_{i-1},x_{i}+1\rangle.$ (4.28)

Then $M\prec L$.

Proof. It is enough to show that

$\langle y_{1},y_{2},\ldots,y_{k},z_{1}\rangle\leq\langle
x_{1},x_{2},\ldots,x_{i},z_{1}\rangle$ (4.29)

holds and that this inequality is srtict for $z_{1}>1$.

By (1.1) we have

$\langle y_{1},y_{2},\ldots,y_{k},z_{1}\rangle=\langle
y_{1},y_{2},\ldots,y_{k},1\rangle+(z_{1}-1)\langle
y_{1},y_{2},\ldots,y_{k}\rangle,$ $\langle
x_{1},x_{2},\ldots,x_{i},z_{1}\rangle=\langle
x_{1},x_{2},\ldots,x_{i},1\rangle+(z_{1}-1)\langle
x_{1},x_{2},\ldots,x_{i}\rangle.$

By (4.12) and (4.28) we compare the corresponding therm in the two last
inequalities and obtain (4.29). Lemma is proved.

######  Lemma 4.14.

Suppose that we have a strict inequality in (4.25). Moreover supppose that

$[z_{j};z_{j-1},z_{j-2},\ldots,z_{2},z_{1}]>\frac{\langle
y_{2},\ldots,y_{k}\rangle-\langle x_{2},\ldots,x_{i}\rangle}{\langle
x_{1},\ldots,x_{i}\rangle-\langle y_{1},\ldots,y_{k}\rangle}.$

Then

$\langle z_{1},z_{2},\ldots,z_{j},x_{1},x_{2},\ldots x_{i}\rangle>\langle
z_{1},z_{2},\ldots,z_{j},y_{1},y_{2},\ldots,y_{k}\rangle.$ (4.30)

The proof easily follows by applying equalities (4.27) to continuants from
(4.30) and by taking into account (1.3).

Put

$J(l)=\\{\underbrace{1,n,1,n,\dots,1}_{(2l-1)\,elements}\\},\,\,\,G=\left\\{z,n,J(m_{-})\right\\}.$

######  Lemma 4.15.

For every $n,m\in\mathbb{N}$ one has

$[n;J(m_{+})]>\frac{\langle n,J(n-1),n\rangle-\langle
n^{\\{n\\}}\rangle}{\langle n^{\\{n+1\\}}\rangle-\langle J(n),n\rangle},$
(4.31) $\langle n^{\\{n\\}}\rangle>\langle J(n)\rangle,$ (4.32) $\langle
n^{\\{n+1\\}}\rangle>\langle J(n),n\rangle$ (4.33) $\langle
J(m_{+}),n^{\\{n+1\\}}\rangle>\langle J(m_{+}),n,J(n)\rangle$ (4.34) $\langle
J(m_{+}),n^{\\{n+2\\}}\rangle>\langle J(m_{+}),n,J(n),n\rangle.$ (4.35)

Moreover for $x\geq n+1$ one has

$\langle J(m_{+}),n^{\\{x+1\\}},G\rangle>\langle
J(m_{+}),n,J(n),n^{\\{x-n\\}},G\rangle.$ (4.36)

Proof.

Inequality (4.31) follows immediately from (4.24) and Lemma 4.7. Inequalities
(4.32) and (4.33) are easy corollaries of (4.18), (4.20) and (4.23). This
proves the majorizind inequality

$\langle n^{\\{n+1\\}},J(m_{+})\rangle\succ\langle J(n),n,J(m_{+})\rangle.$
(4.37)

By the symmetry and Lemma 4.12 we see that (4.37) leads to (4.34). To prove
(4.35) one should apply Lemma 4.14. Conditions od Lemma 4.14 are satisfied as
we have (4.31) and (4.33). Then inequalities (4.34) and (4.35) lead to strict
majorizing property in the inequality (4.36) which now follows from Lemma
4.12. Lemma is proved.

###  4.4  Unit variation method.

The idea of this method is taken from [3].

######  Lemma 4.16.

Consider the sequence $Q$ which gives the minimal value of the continuant on a
set of the form $U(S,n,t)$ or $U_{n}(S)$. Then in this sequence there exist
not more than one element different from $1$ and $n$.

Proof. Assume that it is not so. Then we can take two elements $a$, $b$ from
$Q$ which are not equal to $1$ or $n$. Now we suppose all other elements to be
fixed. We suppose the sum $a+b=\tau$ to be fixed also. Consider the continuant

$F_{\tau}(a)=\underbrace{\langle\ldots,a,\ldots,\tau-a,\ldots\rangle}_{t\,\,elements}.$

Then from (4.27) we see that the function $F_{\tau}(a)$ is a quadratic
polynomial in $a$ with a negative leading coefficient. Hence by convexity
argument

$F_{\tau}(a)>min\left\\{F_{\tau}(a-1),\,\,\,F_{\tau}(a+1)\right\\}$

(here one can see an explanation for the notion “unit variation“). This
inequality contradicts the minimality of $Q$. Lemma is proved.

######  Lemma 4.17.

Suppose that $a,b,c\in\mathbb{N}$, $p\in\mathbb{N}\cup\\{0\\}$. If $a\geq c+1$
then

$\langle a,b^{\\{p\\}},c\rangle\leq\langle a-1,b^{\\{p\\}},c+1\rangle.$ (4.38)

If in addition $a>c+1$ then there is a strrict inequality in (4.38).

Proof.

When $a=c+1$ the equality (4.38) is obvious as we have symmetry property
(4.11). In the case $a>c+1$ by (4.12) and Lemma 4.1 we have

$\langle a,b^{\\{p\\}},c\rangle=\langle 1,a-1,b^{\\{p\\}},c\rangle<\langle
1,c,b^{\\{p\\}},a-1\rangle=\langle a-1,b^{\\{p\\}},c+1\rangle.$

######  Lemma 4.18.

If $a\geq c+2$ and $p\geq 0$, $jz_{1}>1$ then

$\langle a,b^{\\{p\\}},c,z_{1},z_{2},\ldots,z_{j}\rangle\prec\langle
a-1,b^{\\{p\\}},c+1,z_{1},z_{2},\ldots,z_{j}\rangle.$

To proof this lemma one should apply Lemma 4.13. To do this we must verify the
assumotion hypothesis of this lemma. This cam be done by Lemma 4.17.

###  4.5  Lemmas concerning systems of (in)equalities.

######  Lemma 4.19.

Consider $S,t\in\mathbb{N}$. The system

$\left\\{\begin{array}[]{ll}ch_{1}+dh_{2}=S,\\\ c+d=t,\\\ h_{2}=h_{1}+1,\\\
d<t\end{array}\right.$ (4.39)

has the unique solution in integers $c,d,h_{1},h_{2}$. If in addition
$S\not\equiv 0\pmod{t}$ then this solution is defined by equalities (3.7); in
the opposite case

$h_{1}=\frac{S}{t},\,\,\,h_{2}=h_{1}+1,\,c=t,\,d=0.$ (4.40)

Proof. According to the equations of the system (4.39),

$S=ch_{1}+dh_{2}=ch_{1}+d(h_{1}+1)=(c+d)h_{1}+d=th_{1}+d.$

Therefore, $d$ is the remainder of dividing $S$ by $t$, while $h_{1}$ is the
quotient of this division. Hence the formulas (3.7) and (4.40). The lemma is
proved.

######  Lemma 4.20.

Suppose that $2\leq t\leq S<nt$. Then the only one from the following two
systems

$\begin{array}[]{lr}\left\\{\begin{array}[]{l}m(n+1)+nx+z=S,\\\ 2m+x+1=t,\\\
m\geq 0,\\\ x\geq 0,\\\ 1\leq z\leq
n-1,\end{array}\right.&\left\\{\begin{array}[]{l}m(n+1)-x+z=S,\\\ 2m-x+1=t,\\\
m\geq 0,\\\ x<0,\\\ 1\leq z\leq n-1.\end{array}\right.\end{array}$ (4.41)

has a solution in integers $m,x,z$. This solution is unique. It is determined
be formulas (3.9), (3.10).

Proof. The second equality in (3.10) is obtained from the second equalities of
each of the two systems in (4.41). It also shows that the parity of the
numbers $t$ and $x$ are opposite. When substituting the second equality in
(3.10), taking into account the sign of the variable $x$, in the first
equations of each of the two systems in (4.41). Then the equality is obtained

$z=S-t+1-\frac{t-1+x}{2}(n-1).$ (4.42)

According to the above, the numerator of the fraction in (4.42) is even, so
that the coefficient at $(n-1)$ is whole. From here we get a comparison in
(3.9).

We show that the number $m$ satisfying the equalities in any of the systems in
(4.41) is non-negative. To beging with, let us consider the first of these two
systems. Expressing $x$ from the second equality and substituting it into the
first one, we get

$m(n+1)+n(t-1-2m)+z=S<nt.$

Simplifying the resulting inequality, we derive:

$m>\frac{z-n}{n-1}\geq-1.$

Similarly, expressing $x$ from the second equality of the second system in
(4.41) and substituting it into the first of them, we get

$m(n+1)+(t-1-2m)+z=S\geq t.$

Simplifying the resulting inequality, we derive:

$m\geq\frac{1-z}{n-1}>-1.$

Hence, since $m$ is an integer, we get the inequality $m\geq 0$.

Finally, expressing $x$ of (4.42) obtained first equality in (3.10). Depending
on the sign of $x$ triple $(m,x,z)$, found by far, be solution of the first or
the second systems in (4.41). The lemma is proved.

For a natural $T$, we put

$T_{0}^{(n)}=(n+1)\left\\{\frac{T-1}{n+1}\right\\},$ (4.43)
$T_{1}^{(n)}=n\left\\{\frac{T}{n}\right\\}.$ (4.44)

######  Lemma 4.21.

For $T<n^{2}-n-1$, the inequality $T_{1}^{(n)}\leq T_{0}^{(n)}$ is satisfied
if and only if the relation holds

$\left[\frac{T}{n}\right]-\left[\frac{T-1}{n+1}\right]=1$ (4.45)

(otherwise the left side of the equation (4.45) is zero).

Proof. Let $T_{1}^{(n)}\leqslant T_{0}^{(n)}$. We prove the equality (4.45).
On the one hand,

$\begin{split}n\left[\frac{T}{n}\right]=T-n\left\\{\frac{T}{n}\right\\}=T-T_{1}^{(n)}\geq
T-T_{0}^{(n)}=T-(n+1)\left\\{\frac{T-1}{n+1}\right\\}=\\\
=(n+1)\left[\frac{T-1}{n+1}\right]+1,\end{split}$ (4.46)

from where, dividing the beginning and end of the chain of inequalities (4.46)
by $n$, we get

$\left[\frac{T}{n}\right]\geq\frac{n+1}{n}\left[\frac{T-1}{n+1}\right]+\frac{1}{n}>\left[\frac{T-1}{n+1}\right].$
(4.47)

On the other hand,

$\left[\frac{T}{n}\right]-\left[\frac{T-1}{n+1}\right]=\frac{T}{n}-\frac{T-1}{n+1}-\left\\{\frac{T}{n}\right\\}+\left\\{\frac{T-1}{n+1}\right\\}=\frac{T+n}{n(n+1)}-\left\\{\frac{T}{n}\right\\}+\left\\{\frac{T-1}{n+1}\right\\}.$
(4.48)

And since $T<n^{2}$, then (4.48) leads to the inequality

$\left[\frac{T}{n}\right]-\left[\frac{T-1}{n+1}\right]\leq\frac{T+n}{n(n+1)}+1<2.$

From here and from (4.47) it follows (4.45).

Now let the inequality $T_{1}^{(n)}>T_{0}^{(n)}$ be satisfied, or

$n\left\\{\frac{T}{n}\right\\}>(n+1)\left\\{\frac{T-1}{n+1}\right\\}.$

Dividing both parts of the last inequality by $n$, we get:

$\left\\{\frac{T}{n}\right\\}>\frac{n+1}{n}\left\\{\frac{T-1}{n+1}\right\\}\geq\left\\{\frac{T-1}{n+1}\right\\}.$

From here and from (4.48) for $0<T<n^{2}$ we get

$-1<\left[\frac{T}{n}\right]-\left[\frac{T-1}{n+1}\right]<1,$

from where it follows

$\left[\frac{T}{n}\right]-\left[\frac{T-1}{n+1}\right]=0.$

The lemma is proved.

######  Lemma 4.22.

First, every integer $T$ greater than $n^{2}-n-1$ is represented as the sum of
a certain number of terms that can take the values $n$ or $n+1$; the number
$T=n^{2}-n-1$ does not have this property.

Second, the solution of the equation $T=m(n+1)+nx$ in the non-negative integer
variables $m$ and $x$ exists if and only if its solution exists with an
additional constraint $x\leq n$.

Third, for $T<n^{2}-n-1$, the number $T$ is represented as the sum of a
certain number of terms of the form $n$ or $n+1$ if and only if

$T=(n-T_{0}^{(n)})n+T_{1}^{(n)}(n+1).$ (4.49)

Fourth, the equality (4.49) holds if and only if $\,\,\,T_{1}^{(n)}\leq
T_{0}^{(n)}$.

Proof. The first part of the Lemma is a particular case of approval of
Sylvester [14]: every integer greater than $ab-a-b$, can be represented as the
sum of a certain number of terms, which can take the values $a$ or $b$ (it is
sufficient to substitute $a=n$, $b=n+1$), while the number of $ab-a-b$ is not
representable in this form.

We prove the second part of the lemma. To do this, divide $x$ with the
remainder by $n+1$: let

$x=q(n+1)+r,\,\,\,\,r\leq n.$

When substituting the last equality in the Diophantine equation, we get:

$T=m(n+1)+nx=m(n+1)+n(q(n+1)+r)=(m+nq)(n+1)+nr,$

and we got a solution with the desired property.

We prove the third part of the lemma. We show that if the number $T<n^{2}$ is
represented by the sum of terms of the form $n$ or $n+1$, then the equality
(4.49) is satisfied. Indeed: let

$T=m(n+1)+nx$ (4.50)

and $m\geq 0$, $x\geq 0$. Then, taking the remainder of the division of the
left and right parts of the equality (4.50) by $n$, we get: $m\equiv
T\pmod{n}$, which implies that $m=T_{1}^{(n)}$. Similarly, taking the
remainder of the division of the left and right parts of the equality (4.50)
by $n+1$, we get: $x\equiv-T\pmod{n+1}$, which implies that $x=n-T_{0}^{(n)}$.
Substituting the found values of $m$ and $x$ in (4.50) results in equality
(4.49).

We prove the fourth part of the lemma. We now show that for $T<n^{2}-n-1$ ,
the number $T$ is represented by the sum of terms of the form $n$ or $n+1$ if
and only if $T_{1}^{(n)}\leq T_{0}^{(n)}$. To do this, transform the right
side of the equality (4.49):

$(n-T^{(n)}_{0})n+T^{(n)}_{1}(n+1)=\left(n-(n+1)\left\\{\frac{T-1}{n+1}\right\\}\right)n+n\left\\{\frac{T}{n}\right\\}(n+1)=$
$=n^{2}-(n^{2}+n)\left(\left\\{\frac{T-1}{n+1}\right\\}-\left\\{\frac{T}{n}\right\\}\right)=$
$=n^{2}-(n^{2}+n)\left(\frac{T-1}{n+1}-\left[\frac{T-1}{n+1}\right]-\frac{T}{n}+\left[\frac{T}{n}\right]\right)=$
$=n^{2}-n(T-1)+(n+1)T-(n^{2}+n)\left(\left[\frac{T}{n}\right]-\left[\frac{T-1}{n+1}\right]\right)=$
$=T+(n^{2}+n)\left(\left[\frac{T}{n}\right]-\left[\frac{T-1}{n+1}\right]-1\right).$

Thus, the right side of an equality (4.49) is equal to the left one if and
only if the equality (4.45) is satisfied, which, according to the previous
lemma, is satisfied if and only if $T_{1}^{(n)}\leq T_{0}^{(n)}$. The lemma is
proved.

######  Lemma 4.23.

Suppose that $2\leq t\leq S<nt$. Then for any $z\in P(S)$ there exists only
one solution of the system

$\left\\{\begin{array}[]{l}m(n+1)+nx+z=S,\\\ m\geq 0\\\ 0\leq x\leq
n\end{array}\right.$ (4.51)

in integers $m,x$. This solution is defined by formulas (3.12).

Moreove an opposite statement is true: if $S\leq n^{2}-1$,
$z\in\\{1,2,\ldots,n-1\\}$ and the system (4.51) has a unique solution then
$z\in P(S)$.

Proof. The number $T=S-z$, according to the first equation of the system
(4.51), is represented as the sum of a certain number of terms of the form $n$
or $n+1$. Therefore, according to the preceding lemma, the inequalities
$S-z>n^{2}-n-1$ or

$n\left\\{\frac{S-z}{n}\right\\}\leq(n+1)\left\\{\frac{S-z-1}{n+1}\right\\}$

are satisfied. The first of these corresponds to the case when $z\in P(S)$ as
first line in (2.7); the second and third lines in (2.7) correspond to the
situations when $S<n^{2}-1$, the number $S$ is not representable or
representable as the sum of several terms, equal to $n$ or $n+1$. The
uniqueness of the solution is provided by the last inequality in (4.51).

The expressions for $x$ and $m$ in (3.12) follow from the first line of the
system (4.51).

The lemma is proved.

##  5  Proof of main theorems.

###  5.1 Proof of Theorem 1.

Induction in $t$. Suppose $A=\\{a_{1},a_{2},\ldots,t\\}$ to be a sequence from
$V_{f}$. Suppoce than any basic substitution for it is a non-increasing
substitution. Then $a_{1}=b_{0}$ by the assumption. If $a_{2}=b_{1}$ then
$(2,t)$-fragment of the sequence $A$ sshould belong to a certain set $V_{g}$
for a certain value of $g\leq f$. Moreover it containes of $t-1$ elements. We
apply the inductive assumotion to this fragment. We should take into account
remark 3 also. We see that the equality (3.1) is proved, in this case. If
$a_{2}\neq b_{1}$ (and hence $a_{2}>b_{1}$) we consider the basic
$(2,\gamma)$-substitution $\Pi$, $\gamma=\max\\{j:a_{j}=b_{1}\\}$. Then $\Pi$
is an increasing substitution by Lemma 4.1. This contradicts to the assumption
behind. So $a_{2}=b_{1}$. Theorem is proved.

###  5.2 Other proof of Theorem 3.1.

Consider three finite sequences consisting of natural numbers: $U,V$, and $W$,
the middle of which (i.e., $V$) is — nonempty, as is at least one of the two
extremes, — $U$ or $W$. Let us give the following definition.

######  Definition 5.1.

Let’s call the procedure for replacing continuants

$\langle{U,V,W}\rangle\,\,\,\,\mapsto\,\,\,\langle{U},\overleftarrow{V},{W}\rangle$

by reflection [13] of the sequence $(U,V,W)$, where $\overleftarrow{V}$ — the
sequence $V$ written in the opposite order.

Consider any finite sequence $(a_{1},a_{2}\dots,a_{t})$ of natural numbers,
such that $a_{1}=\min(a_{1},a_{2},$ $\dots,a_{t})$ and $a_{i}>a_{j}$ for some
$i<j$ (any such pair $(a_{i},a_{j})$ let’s call correct). Let
$a_{i^{*}},a_{j^{*}}$ — two elements of this sequence, such that
$a_{i^{*}}>a_{j^{*}}$, ${i^{*}}<{j^{*}}$, with the maximum difference value
$j^{*}-i^{*}$ (and such a correct pair $(a_{i^{*}},a_{j^{*}})$ let’s call the
most remote). Then $i^{*}>1$ (since $a_{1}$ is minimal) and

$a_{i^{*}-1}\leqslant a_{j^{*}}<a_{i^{*}}\leqslant a_{j^{*}+1}$ (5.1)

(of course, it may happen that $j^{*}=t$; then the sequence $W$ defined below
is empty).

Let

$\langle a_{1},a_{2},\dots,a_{t}\rangle=\langle U,V,W\rangle,$ (5.2)

where

$U=a_{1},a_{2},\dots,a_{i^{*}-1};\,\,\,V=a_{i^{*}},\dots,a_{j^{*}};\,\,\,\,W=a_{j^{*}+1},\dots,a_{t}.$
(5.3)

It follows from (5.1) that the inequality

${\bf a}(U,V,W)\geqslant 0$ (5.4)

is satisfied. Therefore, it follows from the Lemma 4.2 that

$\langle{U},\overleftarrow{V},{W}\rangle\geq\langle U,V,W\rangle.$ (5.5)

However, the sequence $({U},\overleftarrow{V},{W})$ can be obtained from the
sequence $(a_{1},a_{2}\dots,a_{t})$ by some permutation (reflection). Thus,
for each sequence $(a_{1},a_{2}\dots,a_{t})$ with inversion $a_{i}>a_{j},i<j$
there is a permutation $\pi$ that reduces the number of inversions, but does
not reduce the continuant $\langle a_{1},a_{2},\dots,a_{t}\rangle$. The
theorem 3.1 is proved.

In general terms, this proof consisted in the fact that from an arbitrary
continuant, using an algorithm consisting of non-decreasing reflections, a
continuant equal to the maximum over all permutations of its elements was
obtained. For the rest, let’s imagine the following situation: let the
continuant (5.2), which we will call the internal continuant, be part of
another, — external, — continuant (say, $\langle
F,a_{1},a_{2},\dots,a_{t},G\rangle$), where $F$ and $G$ are finite sequences.
Suppose that for some purposes it is required to obtain a similar algorithm,
which from an arbitrary continuant leads to a maximum, but consists only of
such reflections that do not decrease for both the internal continuant and the
external one. This algorithm is called transitive (step-up). Similarly, a
transitive step-down algorithm is defined: it consists of reflections that are
not external continuant, as for the internal one.

######  Lemma 5.1.

For any continuant that is internal with respect to some external one, a
transitive algorithm exists (both increasing and decreasing).

Proof. We prove, for example, the existence of a transitive step-up algorithm.
Namely, if for the next step of the proof the constructed reflection (5.5)
strictly increases the internal continuant, then it also strictly increases
the external one. Indeed: from the rule of comparing continued fractions and
from the positivity of a number ${\bf a}(U,V,W)$ from (4.6) follows also the
positivity of the number ${\bf a}((F,U),V,(W,G))$. Therefore, it is sufficient
to deal only with those reflections that do not change the value of the
internal continuant: in this case, the inequalities in (5.4) and (5.5) are
performed as equalities. Thus, ${\bf a}(U,V,W)$ from (5.4) is zero. But ${\bf
a}(U,V,W)$ is equal to the product of two multipliers. Hence, the general
situation falls into two cases: $[\overleftarrow{V}]=[{V}]$ or
$[\overleftarrow{U}]=[{W}]$. However, according to (5.1), the first of these
cases is not possible.

Let it be now $[\overleftarrow{V}]\not=[{V}]$, but the equality is met
$[\overleftarrow{U}]=[{{W}}]$. According to (5.1), the final sequences
$\overleftarrow{U}$ and $W$ differ already by their first elements, so that
“unit extraction” (4.12) is involved here. More precisely,
$\overleftarrow{U}=\\{n,1\\}$, $W=\\{n+1\\}$ (a singleton sequence) for some
natural $n$. We show that in this case, the following is true:

$a_{i^{*}-1}=a_{j^{*}}<a_{i^{*}}=a_{j^{*}+1}.$ (5.6)

Indeed: if $a_{i^{*}}>a_{j^{*}+1}$, then the correct maximally distant pair —
is $(a_{i^{*}},a_{j^{*}+1})$ , not $(a_{i^{*}},a_{j^{*}})$. If
$a_{i^{*}}<a_{j^{*}+1}$, then the correct maximally distant pair is
$(a_{i^{*}-1},a_{j^{*}})$ , not $(a_{i^{*}},a_{j^{*}})$. So
$a_{i^{*}}=a_{j^{*}+1}=n+1$, while $a_{i^{*}-1}=n$. So $a_{j^{*}}<n+1$. But,
if $a_{j^{*}}<n=a_{i^{*}-1}$, then, again, the correct maximally distant pair
— is $(a_{i^{*}-1},a_{j^{*}})$ , not $(a_{i^{*}},a_{j^{*}})$. This
contradiction finally proves the equalities in (5.6).

Now $[V]<[\overleftarrow{V}]$ (due to the inequality between the first and
last elements of the final sequence $V$), and if at least one of the two
sequences $F$ or $G$ is non-empty, then
$[\overleftarrow{U},\overleftarrow{F}]>[W,G]$. Therefore, for the outer
continuant, the reflection corresponding to the reflection of the inner one
(5.5) is strictly magnifying. Thus, the existence of a transitive step-up
algorithm is proved.

The existence of a transitive step-down algorithm is proved in a completely
analogous way.

The lemma is proved.

###  5.3 Proof of Theorem 3.2.

By Lemma 5.2 the maximum under consideration attains on a certain sequence
$D_{f}$. By means of the symetry one may assume that at least one of two
numbers $l_{f}$, $r_{f}$, (say, the second one) is greater than zero. In order
to obtain a proof of Theorem 3.2 from Lemma 4.5 we add the continuant by a
virtual element $h_{f+1}=+\infty$, formally:

$\langle+\infty,D_{f}\rangle=\langle D_{f}\rangle.$

Then we have

$l_{f+1}=1,\,\,\,r_{f+1}=0,\,\,\,r_{f}>0.$

This is just (4.14) for large $f$. Now Theorem 3.2 folows from Lemma 4.5.
Theorem is proved.

###  5.4 Other proof of Theorem 3.2.

######  Lemma 5.2.

Maximal continuant on the set $W_{f}(\bar{h},\bar{p})$ is reached on some
finite sequence $D_{f}(\bar{l},\bar{r})$, whose elements are subject to the
condition (2.1).

Proof. Let be the maximal continuant on the set $W_{f}(\bar{h},\bar{p})$ is
reached on a finite sequence $D=(a_{1},a_{2},\ldots,a_{t})$ and let the
equality $a_{\nu}=h_{1}$ be satisfied for some $\nu\in\\{1,2,\ldots,t\\}$.
Let’s imagine the sequence $D$ as a union of finite subsequences
$(a_{1},a_{2},$ $\ldots,a_{\nu})$ and $(a_{\nu},a_{\nu+1},\ldots,a_{\nu})$, in
the first of which the minimum element is in the last place, and in the second
— in the first place. We fix the location of the minimum element in each of
these sequences and apply to them separately the transitive algorithm for
proving the 3.1 theorem (in the first of them, changing the order of the
elements to the exact opposite, and at the end of the algorithm — reversing it
again). Then the first sequence turns into a non-increasing one, the second —
into a non-decreasing one, and together they form a finite sequence
$D_{f}(\bar{l},\bar{r})$. The lemma is proved.

Consider an arbitrary continuant of the form

$\langle D_{f}\rangle=\langle
h_{f}^{\\{l_{f}\\}},h_{f-1}^{\\{l_{f-1}\\}},\ldots,h_{2}^{\\{l_{2}\\}},h_{1}^{\\{l_{1}\\}},h_{1}^{\\{r_{1}\\}},h_{2}^{\\{r_{2}\\}},\ldots,h_{f}^{\\{r_{f}\\}}\rangle$
(5.7)

together with a symmetric one to it, which is obtained by writing all its
elements in exactly the opposite order. From these two continuants, we choose
the one for which $l_{f-1}\geq r_{f-1}$. In the continuant (5.7), we select
the inner part:

$\langle D_{f-1}\rangle=\langle
h_{f-1}^{\\{l_{f-1}\\}},h_{f-2}^{\\{l_{f-2}\\}},\ldots,h_{2}^{\\{l_{2}\\}},h_{1}^{\\{l_{1}\\}},h_{1}^{\\{r_{1}\\}},h_{2}^{\\{r_{2}\\}},\ldots,h_{f-1}^{\\{r_{f-1}\\}}\rangle$
(5.8)

and apply a transitive step-up algorithm to it, using the lemma 5.1. This
means that by applying a certain number of reflections , the continuant (5.8)
will be brought to the maximum over all permutations of its elements, while
the continuant (5.7) will not decrease. Without limiting generality, we can
assume that the inequality $l_{f-1}\geq r_{f-1}$ still holds.

Using the inductive (on the parameter $f$) assumption, we obtain that for the
continuant (5.8) at least one of the sets of equalities is satisfied, (3.3) or
the opposite to it — the one for which the inequality $l_{f-1}\geq r_{f-1}$is
satisfied.

If now $l_{f}=1$, then the inductive transition is complete. It remains to
consider the cases when $l_{f}=0$ or $l_{f}>1$ Consider the case where
$l_{f}=0$. Let’s put it: $U$ — empty,

$V=\left\\{h_{f-1}^{\\{l_{f-1}\\}},h_{f-2}^{\\{l_{f-2}\\}},\ldots,h_{2}^{\\{l_{2}\\}},h_{1}^{\\{l_{1}\\}},h_{1}^{\\{r_{1}\\}},h_{2}^{\\{r_{2}\\}},\ldots,h_{f-1}^{\\{r_{f-1}\\}},h_{f}^{\\{r_{f}-1\\}}\right\\},\,\,\,W=\left\\{h_{f}\right\\}.$

Applying a single reflection with such a partitioning of the sequence into
$U,V,W$ increases the continuant, so that now $l_{f}>0$.

Now let $l_{f}>1$. Let’s put it:

$U=\left\\{h_{f}^{\\{l_{f}-1\\}}\right\\},$
$V=\left\\{h_{f},h_{f-1}^{\\{l_{f-1}\\}},h_{f-2}^{\\{l_{f-2}\\}},\ldots,h_{2}^{\\{l_{2}\\}},h_{1}^{\\{l_{1}\\}},h_{1}^{\\{r_{1}\\}},h_{2}^{\\{r_{2}\\}},\ldots,h_{f-1}^{\\{r_{f-1}\\}}\right\\},\,\,\,$
$W=\left\\{h_{f}^{\\{r_{f}\\}}\right\\}.$

Applying a single reflection with such a partition of the sequence into
$U,V,W$ increases the continuant, so that now $l_{f}=1$. The inductive step is
complete. The 3.2 theorem is proved.

###  5.5 Proof of Theorem 3.3.

Assume that theorem 3.3 is not true. So the minimal value of the continuant on
the set $W_{f}$ is attained on a sequence $B=\\{a_{1},a_{2},\ldots,a_{t}\\}$,
and no one of the trivial substitutions od this sequence does not give (3.4).
Then there exists

$j=j(B)=\min\\{k\geq 0:(a_{k_{-}+1}\neq
n_{k_{-}},k_{-}\leq\nu)\bigvee(a_{k_{-}+1}=n_{k_{-}},a_{t+1-k_{t}}\neq
m_{k_{+}},1\leq k_{+}\leq\mu)\\}.$

Here as usually $k_{-}=\left[k/2\right]$, $k_{+}=k-k_{-}$. We consider all the
sequences trivially obtained from $B$. We may choose $B$ to be the sequence
with the maximal value of $j(B)$. Two cases are possible: $a_{j_{-}+1}\neq
n_{j_{-}}$ or $(a_{j_{-}+1}=n_{j_{-}},a_{t+1-j_{+}}\neq m_{j_{+}})$. In the
first case by $\nu$ we denote the index for which $a_{\nu}=n_{j_{-}}$. Then we
consider the basic $(j_{-}+1,\nu)$-substitution $\Pi$. In the second case we
put $a_{\nu}=m_{j_{+}}$. In this case we take $\Pi$ to be the
$(\nu,t+1-j_{+})$-basic substitution. By Lemmas 4.2, 4.6 we see that the
substitution $\Pi$ is a non-increasing substitution. From the minimality
property we see that it is a non-decreasing substitution also. Hence by Remark
4.1 $\Pi$ is a trivial substitution. But by the construction we have

$j(\\{a_{\Pi(1)},a_{\Pi(2)},\ldots,a_{\Pi(t)}\\})>j(B).$

This contradicts to the choise of $j$. Theorem is proved.

###  5.6 Other proof of Theorem 3.3.

We will conduct induction along the length of the continuant. To do this,
first consider the element $a_{1}$, selecting the desired numbering of the
elements — from the first to the last or from the last to the first, so that
the inequality is satisfied $a_{1}\leq a_{t}$. If $a_{1}$ — is not the minimum
element of the continuant, then we apply a downward reflection that moves this
minimum element to the first place. Let this reflection result in the
continuant $\langle
a^{\prime}_{1},a^{\prime}_{2},\ldots,a^{\prime}_{t}\rangle$, where
$a^{\prime}_{1}=h_{1}$. If now $a^{\prime}_{2}\not=h_{f}$, that is, to the
maximum element of the continuant, then we apply a lowering reflection that
moves this maximum element to the second place. Let this action result in the
continuant $\langle
a^{\prime\prime}_{1},a^{\prime\prime}_{2},\ldots,a^{\prime\prime}_{t}\rangle$.
Note that the elements $a^{\prime\prime}_{1}$ and $a^{\prime\prime}_{2}$
coincide, respectively, with $n_{0}$ and $n_{1}$ — the first two elements of
the continuant from the right side in (3.4).

Consider a finite sequence
$a^{\prime\prime}_{1},a^{\prime\prime}_{2},\ldots,a^{\prime\prime}_{t}$ and
change it numeration reverse (from end to beginning), applying the inductive
hypothesis in the form of a transitive reduction algorithm, then you come to
formula (3.4). Theorem 3.3 is proved.

###  5.7 Proof of Theorem 3.4.

By Lemmas 4.11 and 4.12 applied to continuants corresponding to sequences
containing different from $1$ elements we see that the equality (3.1) should
be valid. Theorem is proved.

###  5.8 Proof of Theorem 3.5.

Let the finite sequence $C$ for which the maximum of continuants is reached on
the set $U(S,t)$ belong to the set $W_{f}$ with $f\geq 3$. Then the structure
of this sequence is given by the formulas (3.2) — (3.3). But, according to the
Lemma 4.18,

$\langle h_{f},h_{f-1}^{\\{l_{f-1}\\}},h_{f-2},\ldots\rangle\prec\langle
h_{f}-1,h_{f-1}^{\\{l_{f-1}\\}},h_{f-2}+1,\ldots\rangle.$

The last inequality, according to the Lemma 4.12, comes into conflict with the
maximality of the continuant on the sequence $C=D_{f}$. This contradiction
shows that the inequality must hold $f\leq 2$.

We show that in the case of $f=2$, the equality $h_{2}=h_{1}+1$ must hold.
Indeed, if $h_{2}>h_{1}+1$, then

$\langle h_{2},h_{1}^{\\{l_{1}\\}},h_{2},\ldots\rangle\prec\langle
h_{2},h_{1}^{\\{l_{1}-1\\}},h_{1}+1,h_{2}-1,\ldots\rangle,$ (5.9)

since

$\langle h_{2},h_{1}^{\\{l_{1}\\}}\rangle<\langle
h_{2},h_{1}^{\\{l_{1}-1\\}},h_{1}+1\rangle$

and (from (4.27))

$\langle h_{2},h_{1}^{\\{l_{1}\\}},h_{2}\rangle=\langle
h_{2},h_{1}^{\\{l_{1}-1\\}}\rangle\langle h_{1},h_{2}\rangle+\langle
h_{2},h_{1}^{\\{l_{1}-2\\}}\rangle h_{2}<$ $<\langle
h_{2},h_{1}^{\\{l_{1}-1\\}}\rangle\langle h_{1}+1,h_{2}-1\rangle+\langle
h_{2},h_{1}^{\\{l_{1}-2\\}}\rangle(h_{2}-1)=\langle
h_{2},h_{1}^{\\{l_{1}-1\\}},h_{1}+1,h_{2}-1\rangle.$

However, according to the 4.12 Lemma, the inequality (5.9) contradicts the
maximality of the continuant on the sequence $C=D_{f}$; therefore,
$h_{2}=h_{1}+1$.

The rest of the proof follows from Lemma 4.19 and from Theorem 3.2. Theorem is
proved.

###  5.9 Proof of Theorem 3.6.

Let $E$ — be the finite sequence that gives the minimum value of the
continuant on the set $U(S,n,t)$, and let $E\in W_{f}$. Then by the Lemma 4.16
we get that $f\leq 3$. The minimal continuant of a finite sequence with at
most three distinct elements ($1$, $n$, and $z$) can be found by the 3.3
theorem. To apply the latter, imagine a sequence of$t$ empty cells, which we
will begin to fill with the numbers $1$ and $n$ (alternating them), starting
with the extreme empty cells, gradually moving to the central ones. This is
the reason for the formation of the central section $N_{z}(x)$ from (2.4): if
the elements “$1$” end first, then $N_{z}(x)$ will be as in the upper line
from (2.4), otherwise — as in the lower one. In this case, it is convenient to
denote by $x$ or $-x$, respectively, the quantities “$n$ ” or ”$1$” in
$N_{z}(x)$ (except ”$z$”), depending on which of the elements in $N_{z}(x)$
are present. The rest of the proof follows from the Lemma 4.20. The theorem is
proved.

###  5.10 Proof of Theorem 3.7.

This minimum is also reduced to minimizing the continuants of three-element
permutations by the 3.3 theorem, which results in a minimum in the form (3.4).
But now the $t$ parameter is not fixed. As in the proof of the previous
theorem, by $x$ we denote the number of “$n$” in the final sequence, which
will be as in the bottom line of (2.4).

Due to the inequality (3.1), the condition $x\leq n$ must be satisfied for the
minimal continuant in the form (3.4). But since $x\geq 0$ and the continuant
is taken from the sequence of the set $U_{n}(S)$, the number $S-z$ must be
represented as the sum of several terms equal to $n$ or $n+1$. This is
provided by selecting the set $P(S)$ in (2.6), (2.7). Remaining relationship
details (2.4)-(2.7) and (3.11), (3.12) follow from the Lemma 4.23. The theorem
is proved.

######  Remark 5.1.

The extremuma from Theorems 3.1-3.6 are attained on the sequences which are
unique up to symmetry (4.11) and extracting a unit (4.12) procedures. It can
be easily seen from the proofs.

##  ?refname?

  * [1] Kan I. D. Methods for estimating of continuants. // J. Math. Sci. (N.-Y.), 182(4), pp. 508-517, 2012
  * [2] R. Graham, D. Knuth, O. Patashnik. Concrete Mathematics, 1994.
  * [3] Dushistova A. A., Moshchevitin N. G. On the derivative of the Minkowski question mark function $?(x)$. // J. Math. Sci. (N.-Y.), vol. 182, iss. 4, 2012, pp. 463-471.
  * [4] Cusick T. W. Continuants with bounded digits, 1-3. // Matematika: 24(1977), 166-172; 25(1978), 107-109; Monatsh Math. 99(1985), 105-109.
  * [5] Good I. J.  The fractional dimension theory of continued fractions. // Proc. Cambridge Philos. Soc. 37(1941), 199-228.
  * [6] Hensley D.  The distridution - of badly approximable numbers, and continuants with bounded digits, 1-2. – // Proc. Int. number Theory. Univ. Laval, 371-385, de Cruiter, New York, 1989; J. Number Theory, 34, 293-334(1990).
  * [7] Kan I. D. A refinement of the rule of comparing continuants. // Discrete Mathematics and Applications, 2000. 10:5, 477-480.
  * [8] Motzkin T. S., Straus E. G.  Some combinatorial extremum problems. // Proc. Amer. Math. Soc. (1956), 7, 1014-1031.
  * [9] D. Knuth.  The art of Computer Programming, 2005.
  * [10] . . . . // , 1997, 52, 6 (318). . 167168. (On finite continued fractions. Korobov, N. M. Russian Mathematical Surveys (1997), 52(6): 1302-1304.
  * [11] Knuth D. E.  Art of Computer Programming V. 2., Third edition. Addison-Wesley, 1997.
  * [12] . . . . .: , 1961. (Continued Fractions. A. Ya. Khinchin, Translated from the third Russian edition (Moscow, 1961) by Scripta Technica. University of Chicago Press, Chicago, 1964.)
  * [13] D. R. Gayfulin. On the derivative of two functions from DenjoyTichyUitz family. // St. Petersburg Math. J., 27:1 (2016), 51 85.
  * [14] Sylvester J. J. Mathematical questions with their solutions // Educational times. 1884\. 41. P. 21.


11institutetext: Federal University of Piauí, Brazil
11email<EMAIL_ADDRESS>
22institutetext: Federal Institute of Piauí, Brazil
22email<EMAIL_ADDRESS>
# Essay-BR: a Brazilian Corpus of Essays

Jeziel C. Marinho 11 Rafael T. Anchiêta 22 Raimundo S. Moura 11

###### Abstract

Automatic Essay Scoring (AES) is defined as the computer technology that
evaluates and scores the written essays, aiming to provide computational
models to grade essays either automatically or with minimal human involvement.
While there are several AES studies in a variety of languages, few of them are
focused on the Portuguese language. The main reason is the lack of a corpus
with manually graded essays. In order to bridge this gap, we create a large
corpus with several essays written by Brazilian high school students at an
online platform. All of the essays are argumentative and were scored across
five competencies by experts. Moreover, we conducted an experiment on the
created corpus and showed challenges posed by the Portuguese language. Our
corpus is publicly available at https://github.com/rafaelanchieta/essay

###### Keywords:

Corpus analysis Automatic Essay Scoring NLP Education.

##  1 Introduction

The Automated Essay Scoring (AES) area began with Page [15] with the Project
Essay Grader. Shermis and Barrera [17] define AES as the computer technology
that evaluates and scores written essays, i.e., it aims to provide
computational models to grade essays either automatically or with minimal
involvement of humans [15].

AES is one of the most important educational applications of Natural Language
Processing (NLP) [12, 4]. It encompasses other fields, such as Cognitive
Psychology, Education Measurement, Linguistics, and Written Research [18],
which aim to study methods to assist teachers in automatic assessments,
providing a cheaper, faster, and deterministic approach than humans to grade
an essay.

Due to all the benefits, AES has been widely studied in various languages, for
example, English, Chinese, Danish, Japanese, Norwegian, and Swedish, among
others [4]. To grade an essay, these studies supported the development of
regression-based methods, such as [3, 22], classification-based methods, as
[10, 14], and neural networks-based methods as [21]. Moreover, AES systems
have also been successfully used in schools and large scale exams [23].
According to Dikli [8], examples of such systems are: Intelligent EssayTM,
CriterionSM, IntelliMetricTM, E-rater®, and MY Access!®.

Despite the importance of AES area, most of the resources and methods are only
available for the English language [12]. There are very few AES-based studies
for the Brazilian Portuguese language. The main reason for that is the lack of
a public corpus with manually graded essays. Hence, it is important to put
some effort into creating resources that will be useful for the development of
alternative methods for this field.

In this paper, aiming to fulfill this gap, we create a large corpus, namely
Essay-BR, with essays written by Brazilian high school students through an
online platform. These essays are of the argumentative type and were graded by
experts across five different competencies to achieve the total score of an
essay. The competencies follow the evaluation criteria of the ENEM - Exame
Nacional do Ensino Médio \- (National High School Exam), which is the main
Brazilian high school exam that serves as an admission test for most
universities in Brazil.

In addition to the corpus, we carry out an experiment, implementing two
approaches to automatically score essays, demonstrating the challenges posed
by the corpus, and providing baseline results. As this is the first publicly
available corpus of essays for the Portuguese language, we believe that it
will foster AES studies for that language, resulting in developing alternative
methods to grade an essay.

The remaining of this paper is organized as follows. Sect. 2 describes the
main related work for the Portuguese language. In Sect. 3, we present the ENEM
exam. Sect. 4 details our corpus, its construction, and an analysis of the
training, development, and testing datasets. In Sect. 5, we describe our
conducted experiments. Finally, Sect. 6 concludes the paper, indicating future
work.

##  2 Related Work

As before mentioned, there is no publicly available corpus of essays for the
Brazilian Portuguese. However, three efforts investigated AES for that
language. Here, we briefly present them.

Bazelato and Amorim [2] crawled $429$ graded essays from the Educação UOL
Website to create the first corpus of essays for the Portuguese Language.
However, the crawled essays are very old, they do not meet the criteria of the
ENEM exam. Moreover, the collected essays are not available.

Amorim and Veloso [1] developed an automatic essay scoring method for the
Brazilian Portuguese language. For that, they collected $1,840$ graded essays
from the Educação UOL Website. Next, they developed 19 features to feed a
linear regression to grade the essays. Then, to evaluate the approach, the
authors compared the automatic scores with the scores of the essays, using the
Quadratic Weighted Kappa (QWK) metric [6], achieving 42.45%.

Fonseca et al. [11] addressed the task of automatic essay scoring in two ways.
In the first one, they adopted a deep neural network architecture similar to
the Dong et al. [9] with two Bidirectional Long Short-Term Memory (BiLSTM)
layers. The first layer reads word vectors and generates sentence vectors,
which are read by the second layer to produce a single essay vector. This
essay vector goes through an output layer with five units and a sigmoid
activation function to get an essay score. In the second approach, the authors
hand-crafted 681 features to feed a regressor to grade an essay. The authors
evaluated the approaches using a corpus with 56,644 graded essays and reached
the best result with the second method, achieving 75.20% in the QWK metric.

Although these works have used essays written in Brazilian Portuguese to
evaluate their methods, the authors did not make corpora publicly available,
making the development of alternative methods difficult. Moreover, each work
utilized a different corpus, also making it difficult to provide a fair
comparison between them.

In English, according to [12], there are five popular available corpora: ICLE
[20], CLC-FCE [24], Automated Student Assessment
Prize111https://www.kaggle.com/c/asap-aes (ASAP), TOEFL 11 [5], and AAE [19].
The ASAP corpus, one of the most famous and established corpus, was released
as part of a Kaggle competition in 2012, becoming widely used for holistic
scoring.Furthermore, the corpus is composed by 17,450 argumentative essays and
8 prompts written by United States students from grades 7 to 10.

In what follows, we present the ENEM exam.

##  3 ENEM exam

The ENEM - Exame Nacional do Ensino Médio \- (National High School Exam) is
the main Brazilian high school exam that serves as an admission test for most
universities in Brazil. More than that, it is the second-largest admission
test in the world after the National Higher Education Entrance Examination,
the entrance examination of higher education in China. In the ENEM exam, the
reviewers take into account five competencies to evaluate an essay, which are:

  1. 1.

Adherence to the formal written norm of Portuguese.

  2. 2.

Conform to the argumentative text genre and the proposed topic (prompt), to
develop a text, using knowledge from different areas.

  3. 3.

Select, relate, organize, and interpret data and arguments in defense of a
point of view.

  4. 4.

Usage of argumentative linguistic structures.

  5. 5.

Elaborate a proposal to solve the problem in question.

where each competence is graded with scores ranging from 0 to 200 in intervals
of 40. These scores are organized by proficiency levels, as shown in Table 1.
In this table, the value 200 indicates an excellent proficiency in the field
of competence, whereas the value 0 shows ignorance in the field of competence.

In this way, the total score of an essay is the sum of the competence scores
and may range from 0 to 1,000. At least two reviewers grade an essay in the
ENEM exam, and the final score for each competence is the arithmetic mean
between the two reviewers. If the disagreement between the reviewers’ score is
greater than 80, a new reviewer is invited to grade the essay. Thus, the final
score for each competence will be the arithmetic mean between the three
reviewers.

Table 1: Proficiency levels of the ENEM exam Score |  Description
---|---
200 |  excellent proficiency
160 |  good mastery
120 |  medium dominance
80 |  insufficient mastery
40 |  precarious dominance
0 |  ignorance

##  4 Essay-BR Corpus

The Essay-BR corpus contains $4,570$ argumentative documents and $319$ topics
(prompts). They were collected from December 2015 to April 2020. The topics
include: human rights, political issues, healthcare, cultural activities, fake
news, popular movements, covid-19, and others. Also, they are annotated with
scores in the five competencies of the ENEM exam. Table 2 summarizes the
Essay-BR corpus.

Table 2: Summary of the Essay-BR Corpus Details | Essay-BR
---|---
Text type | Argumentative
Writer’s language level | BR students (high school)
Scoring | Holistic
Number of essays | $4,570$
Number of prompts | $319$
Number of competencies | $5$
proficiency range | $[0-200]$
proficiency scores | $0,40,80,120,160,200$
Score range | $[0-1,000]$

###  4.1 Construction of the Essay-BR corpus

To create the Essay-BR corpus, we developed a Web Scraper to extract essays
from two public Websites: Vestibular
UOL222https://vestibular.brasilescola.uol.com.br/banco-de-redacoes and
Educação UOL333https://educacao.uol.com.br/bancoderedacoes. The essays from
these Websites are public, may be used for research purposes, were written by
high school students, and are graded by experts following the ENEM exam
criteria. We collected $798$ essays and $43$ prompts from Educação UOL, and
$3,772$ essays and $276$ prompts from Vestibular UOL. The difference in the
number of essays is because of the latter Website receives up to forty essays
per month, while the former receive up to twenty essays per month.

After collecting the essays, we applied some preprocessing to remove HTML tags
and comments from the reviews. So, the essays contain only the content written
by the students. Then, we normalized the scores of the essays. Although these
Websites adopted the same ENEM exam competencies to evaluate the essays, they
have a slightly different scoring strategy. Thus, we mapped the scores from
Websites to ENEM scores, as shown in Figure 1.

Figure 1: Mapping function from Website scores to ENEM scores

Although the corpus has a holistic scoring, it also has proficiency scores.
Holistic scoring technologies are commercially valuable, since they allow
automatically scoring million of essays deterministically, summarizing the
quality of an essay with a single score. However, it is not adequate in
classroom settings, where providing students with feedback on how to improve
their essays is of utmost importance [12]. To mitigate this weakness, the
Essay-BR corpus contains five competencies. Thus, the score of competence
shows how a student should improve its essay. For example, a student who got a
score equals 40 in the first competence, i.e., adherence to the formal written
norm, got as feedback that it is necessary to improve its grammar.

We also present an example of the structure of our corpus, as shown in Table
3. From this table, the score is the sum of the competencies (C1 to C5), and
the essay content is composed as a list of paragraphs. It is important to say
that some essays have no title, since, in the ENEM exam, the title is not
mandatory.

Table 3: Example of the Essay-BR corpus Attribute | Value
---|---
Prompt | covid-19
Score | 720
Title | Fighting coronavirus through science
Essay content | list of paragraphs
C1 | 160
C2 | 160
C3 | 120
C4 | 160
C5 | 120

Besides the structure, we computed some statistics and linguistics features
about the essays of the corpus, as depicted in Tables 5 and 5, respectively.
In Table 5, we can see that, on average, an essay has 4 paragraphs, and each
paragraph has 2 sentences. Furthermore, the sentences are somewhat long, with
an average of 30 tokens. In Table 5, most of the essays are passive voice,
since in the Portuguese Language the essays should be impersonal. Also, we
calculated the Flesch score that measures the readability of an essay. From
the score value, the essays are compatible with the college school level.
Finally, we computed some richness vocabulary metrics, such as: hapax
legomenon, which is a word that occurs only once, lexical diversity, also
known as the type-token ratio, and lexical density, which is the number of
lexical tokens divided by the number of all tokens.

Table 4: Statistics of the essays Statistic | Mean | Std
---|---|---
Paragraph per essay | 4.08 | 1.15
Sentence per essay | 10.57 | 4.42
Sentence per paragraph | 2.58 | 1.44
Token per essay | 324.40 | 94.19
Token per paragraph | 79.33 | 35.22
Token per sentence | 30.66 | 17.68

Table 5: Linguistics features Feature | Mean
---|---
Passive voice | 75%
Active voice | 25%
lexical diversity | 26%
lexical density | 22%
Flesch score | 45.98
Hapax legomenon | 36.46

In order to create sets of training, development, and testing, we divided the
corpus in proportions of $70\%$, $15\%$, and $15\%$, which corresponds to
$3,198$, $686$, and $686$ essays for training, development, and testing,
respectively. Aiming to choose essays with a fair distribution of scores for
each split, we computed the distribution of the total score of the essays, as
depicted in Figure 2.

Figure 2: Distribution of the total score

The top $3$ scores are $600$, $680$, and $720$ corresponding to $13.00\%$,
$10.68\%$, and $8.67\%$ of the corpus, respectively, indicating that essays
with these scores should appear more times in the training, development, and
testing sets. Moreover, the scores in the corpus have a slightly rightward
skewed normal distribution.

We also computed the distribution score for each competence and presented it
in Table 6. From this table, all of the essays received $120$ as the higher
score, showing that, in general, the students have medium dominance in the
field of competence.

Table 6: Distribution score for each competence Competence | Scores
---|---
0 | 40 | 80 | 120 | 160 | 200
C1 | 97 | 24 | 359 | 2,630 | 1,338 | 122
C2 | 109 | 79 | 689 | 1,711 | 1,705 | 277
C3 | 122 | 146 | 1,206 | 2,130 | 827 | 139
C4 | 134 | 61 | 590 | 2,000 | 1,241 | 544
C5 | 302 | 276 | 1,023 | 1,732 | 815 | 422

In the following subsection, we analyzed the training, development, and
testing sets of the Essay-BR corpus.

###  4.2 Analysis of the Essay-BR corpus

To create the three splits with score distributions similar to that of the
complete corpus, we first shuffled all the data; then, we filled each split
with essays based on the score distribution. Figure 3 presents the score
distribution for the training, development, and testing sets, respectively.

Figure 3: Training, development, and testing sets of the Essay-BR corpus

From this figure, one can see that the score distributions are similar to the
score distribution of the complete corpus. Likewise, in the score distribution
of Figure 2, the top $3$ scores of the training set are $600$, $680$, and
$720$. Moreover, the development and testing sets have a similar distribution.
This means that if a machine-learning algorithm performs well in the
development set, it probably will also perform well in the testing set.

More than the scores, we also calculated some statistics on the splits,
intending to verify whether the proportion of paragraphs, sentences, and
tokens for each division remained related to the complete corpus proportion.

Comparing the obtained results in Table 6 with the got results of each split
in Table 7, we can see that the results maintained similar proportions. For
example, the average of paragraphs per essay, sentences per essay, and
sentences per paragraph had related results: $4$, $10$, and $2$, respectively.

Table 7: Statistics for each split of the corpus Split | Statistic | Mean | Standard deviation
---|---|---|---
Train | Paragraph per essay | 4.08 | 1.08
Sentence per essay | 10.60 | 4.45
Sentence per paragraph | 2.59 | 1.44
Token per essay | 325.01 | 94.38
Token per paragraph | 79.52 | 35.00
Token per sentence | 30.64 | 17.70
Dev | Paragraph per essay | 4.15 | 1.60
Sentence per essay | 10.57 | 4.63
Sentence per paragraph | 2.54 | 1.43
Token per essay | 323.52 | 95.69
Token per paragraph | 77.84 | 35.65
Token per sentence | 30.60 | 17.75
Test | Paragraph per essay | 4.03 | 0.93
Sentence per essay | 10.45 | 4.10
Sentence per paragraph | 2.59 | 1.43
Token per essay | 322.48 | 91.75
Token per paragraph | 79.95 | 35.78
Token per sentence | 30.83 | 17.53

In what follows, we present the experiment and obtained results.

##  5 Experiments and Results

We carried out an experiment on the Essay-BR corpus to understand the
challenges introduced by the corpus. For that, we implemented the feature-
based methods of Amorim and Veloso [1] and Fonseca et al. [11]. We are aware
that, in recent years, the NLP area has been dominated by the transformer
architectures, as BERT [7]. However, for the AES field the obtained results by
these architectures are similar to traditional models, such as N-grams at high
computation cost [13]. Thus, as a baseline, we preferred to implement feature-
based methods since they require less computational resources and effort.

Amorim and Veloso [1] developed 19 features: number of grammatical errors,
number of verbs, number of pronouns, and others. These features fed a linear
regression to score an essay. Fonseca et al. [11] created a pool of 681
features, as the number of discursive markers, number of oralities, number of
correct words, among others, and these features fed the gradient boosting
regressor to score an essay. To extract the Essay-BR corpus features, we used
the same tools reported by the authors, and to implement the regressors, we
used the scikit-learn library [16].

We evaluated those methods using the Quadratic Weighted Kappa (QWK), which is
a metric commonly used to assess AES models [25], and the Root Mean Squared
Error (RMSE), which is a metric employed to regression problems. Table 8 shows
the QWK metric results, while Table 9 presents the results for the RMSE
metric. In the QWK metric, the greater the value, the better the result,
whereas in the RMSE metric, the smaller the value, the better the result.

Although the approach of Fonseca et al. [11] achieved better results in both
metrics for each competence (C1 to C5), these results are not fit for
summative student assessment, as normally for the AES field, threshold values
between $0.6$ and $0.8$ QWK are used as a floor for testing purposes [13].
Furthermore, the method of Fonseca et al. [11], which achieved $75.20\%$ in
the QWK metric in their corpus, reached only $51\%$ in the Essay-BR. This
difference may be due to two factors. The first is the size of the corpus.
Fonseca et al. [11] used a corpus with more than $50,000$ essays, whereas our
corpus has $4.570$ essays. The second is implementation details. Fonseca et
al. [11] used several lexical resources, but they did not make them available.
Thus, we do not know if the lexical resources we used are the same as Fonseca
et al. [11].

As we can see, it is necessary to develop more robust methods to grade essays
for the Portuguese language in order to improve the results.

Table 8: Quadratic Weighted Kappa on the test set Model | C1 | C2 | C3 | C4 | C5 | Total
---|---|---|---|---|---|---
Amorim and Veloso [1] | 0.35 | 0.44 | 0.39 | 0.37 | 0.34 | 0.47
Fonseca et al. [11] | 0.42 | 0.46 | 0.40 | 0.45 | 0.36 | 0.51
Table 9: Rooted Mean Squared Error on the test set Model | C1 | C2 | C3 | C4 | C5 | Total
---|---|---|---|---|---|---
Amorim and Veloso [1] | 34.82 | 36.14 | 40.27 | 42.23 | 49.02 | 163.92
Fonseca et al. [11] | 34.16 | 35.76 | 40.02 | 40.48 | 48.28 | 159.44

##  6 Final remarks

In this paper, we presented a large corpus of essays written by Brazilian high
school students that were graded by experts following the evaluation criteria
of the ENEM exam. This is the first publicly available corpus for that
language. At this time, it has $4,570$ essays and $319$ prompts, but we
already scraped 13,306 essays from the Vestibular UOL Website. These essays
are being pre-processed and will be available as soon as possible. We hope
that this resource will foster the research area for Portuguese by developing
of alternative methods to grade essays. More than that, according to Ke and Ng
[12], the quality of an essay may be graded adopting different dimensions, as
presented in Table 10.

Table 10: Dimensions to grade the quality of an essay Dimension | Description
---|---
Grammaticality | Grammar analysis
Usage | Use of prepositions, word usage
Mechanics | Spelling, punctuation, capitalization
Style | Word choice, sentence structure variety
Relevance | Relevance of the content to the prompt
Organization | How well the essay is structured
Development | Development of ideas with examples
Cohesion | Appropriate use of transition phrases
Coherence | Appropriate transitions between ideas
Thesis clarity | Clarity of the thesis
Persuasiveness | Convincingness of the major argument

From this table, one can see that a corpus of essays may be graded regarding
several dimensions. Assessing and scoring these dimensions helps the students
get better feedback on their essays, supporting them to identify which aspects
of the essay need improvements.

Some of these dimensions do not seem challenging, such as the grammaticality,
usage and mechanism dimensions, since they already have been extensively
explored. Several other dimensions, such as cohesion, coherence, thesis
clarity, and persuasiveness, bring problems that involve computational
modeling in different levels of the text. Modeling these challenging
dimensions may require understanding the essay content and exploring the
semantic and discourse levels of knowledge. Thus, there exist several possible
applications that the Essay-BR may be useful.

As future work, besides increasing the corpus, which is already in process, we
intend to provide the essay corrections, aiming to develop machine learning
models to learn from the corrections.

## References

  * [1] Amorim, E., Veloso, A.: A multi-aspect analysis of automatic essay scoring for Brazilian Portuguese. In: Proceedings of the Student Research Workshop at the 15th Conference of the European Chapter of the Association for Computational Linguistics. pp. 94–102. Association for Computational Linguistics, Valencia, Spain (Apr 2017)
  * [2] Bazelato, B., Amorim, E.: A bayesian classifier to automatic correction of portuguese essays. In: XVIII Conferência Internacional sobre Informática na Educação. pp. 779–782. Nuevas Ideas en Informática Educativa, Porto Alegre, Brazil (2013)
  * [3] Beigman Klebanov, B., Flor, M., Gyawali, B.: Topicality-based indices for essay scoring. In: Proceedings of the 11th Workshop on Innovative Use of NLP for Building Educational Applications. pp. 63–72. Association for Computational Linguistics, San Diego, CA (Jun 2016)
  * [4] Beigman Klebanov, B., Madnani, N.: Automated evaluation of writing – 50 years and counting. In: Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics. pp. 7796–7810. Association for Computational Linguistics, Online (Jul 2020)
  * [5] Blanchard, D., Tetreault, J., Higgins, D., Cahill, A., Chodorow, M.: Toefl11: A corpus of non-native english. ETS Research Report Series 2013(2), i–15 (2013)
  * [6] Cohen, J.: Weighted kappa: nominal scale agreement provision for scaled disagreement or partial credit. Psychological bulletin 70(4), 213–220 (1968)
  * [7] Devlin, J., Chang, M.W., Lee, K., Toutanova, K.: BERT: Pre-training of deep bidirectional transformers for language understanding. In: Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers). pp. 4171–4186. Association for Computational Linguistics, Minneapolis, Minnesota (Jun 2019)
  * [8] Dikli, S.: An overview of automated scoring of essays. The Journal of Technology, Learning and Assessment 5(1) (2006)
  * [9] Dong, F., Zhang, Y., Yang, J.: Attention-based recurrent convolutional neural network for automatic essay scoring. In: Proceedings of the 21st Conference on Computational Natural Language Learning (CoNLL 2017). pp. 153–162. Association for Computational Linguistics, Vancouver, Canada (Aug 2017)
  * [10] Farra, N., Somasundaran, S., Burstein, J.: Scoring persuasive essays using opinions and their targets. In: Proceedings of the Tenth Workshop on Innovative Use of NLP for Building Educational Applications. pp. 64–74. Association for Computational Linguistics, Denver, Colorado (Jun 2015)
  * [11] Fonseca, E., Medeiros, I., Kamikawachi, D., Bokan, A.: Automatically grading brazilian student essays. In: Proceedings of the 13th International Conference on Computational Processing of the Portuguese Language. pp. 170–179. Springer International Publishing, Canela, Brazil (2018)
  * [12] Ke, Z., Ng, V.: Automated essay scoring: a survey of the state of the art. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence. pp. 6300–6308. AAAI Press, Macao, China (2019)
  * [13] Mayfield, E., Black, A.W.: Should you fine-tune BERT for automated essay scoring? In: Proceedings of the Fifteenth Workshop on Innovative Use of NLP for Building Educational Applications. pp. 151–162. Association for Computational Linguistics, Online (Jul 2020)
  * [14] Nguyen, H.V., Litman, D.J.: Argument mining for improving the automated scoring of persuasive essays. In: Thirty-Second AAAI Conference on Artificial Intelligence. pp. 5892–5899. AAAI Press, Louisiana, USA (2018)
  * [15] Page, E.B.: The imminence of… grading essays by computer. The Phi Delta Kappan 47(5), 238–243 (1966)
  * [16] Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., Duchesnay, E.: Scikit-learn: Machine learning in Python. Journal of Machine Learning Research 12, 2825–2830 (2011)
  * [17] Shermis, M.D., Barrera, F.D.: Exit assessments: Evaluating writing ability through automated essay scoring (2002)
  * [18] Shermis, M.D., Burstein, J.: Handbook of automated essay evaluation: Current applications and new directions. Routledge (2013)
  * [19] Stab, C., Gurevych, I.: Annotating argument components and relations in persuasive essays. In: Proceedings of COLING 2014, the 25th International Conference on Computational Linguistics: Technical Papers. pp. 1501–1510. Dublin City University and Association for Computational Linguistics, Dublin, Ireland (Aug 2014)
  * [20] Sylviane Granger, Estelle Dagneaux, F.M., Paquot, M.: International Corpus of Learner English (Version 2). UCL Presses de Louvain (2009)
  * [21] Taghipour, K., Ng, H.T.: A neural approach to automated essay scoring. In: Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing. pp. 1882–1891. Association for Computational Linguistics, Austin, Texas (Nov 2016)
  * [22] Vajjala, S.: Automated assessment of non-native learner essays: Investigating the role of linguistic features. International Journal of Artificial Intelligence in Education 28(1), 79–105 (2018)
  * [23] Williamson, D.M.: A framework for implementing automated scoring. In: Annual Meeting of the American Educational Research Association and the National Council on Measurement in Education, San Diego, CA (2009)
  * [24] Yannakoudakis, H., Briscoe, T., Medlock, B.: A new dataset and method for automatically grading ESOL texts. In: Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies. pp. 180–189. Association for Computational Linguistics, Portland, Oregon, USA (Jun 2011)
  * [25] Yannakoudakis, H., Cummins, R.: Evaluating the performance of automated text scoring systems. In: Proceedings of the Tenth Workshop on Innovative Use of NLP for Building Educational Applications. pp. 213–223. Association for Computational Linguistics, Denver, Colorado (Jun 2015)