Using Symbolic Computation to Explore Generalized Dyck Paths and Their Areas

AJ BU and Doron ZEILBERGER

Dedicated to Symbolic Computation pioneer Bruno Buchberger (b. 22 October,
1942) on his $80^{th}$ birthday

Abstract: We show the power of Bruno Buchberger’s seminal Gröbner Basis
algorithm, interfaced, seamlessly, with what we call symbolic dynamical
programming, to automatically generate algebraic equations satisfied by the
generating functions enumerating so-called Generalized Dyck Walks, i.e. 2D
walks that start and end on the $x$-axis, and never dip below it, for an
arbitrary set of steps. More impressively, we combine it with calculus (that
Maple knows very well!), to automatically compute generating functions for the
sum-of-the-areas of these generalized Dyck paths, and even for the sum of any
given power of the areas, enabling us to get statistical information about the
area under a random generalized Dyck path.

Maple package and Output Files

This article is accompanied by a Maple package, GDW.txt, and numerous output
files, some of which will be referred to later.

They are all obtainable from the front of this article

https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/area.html  .

Bruno Buchberger: the Gauss of Non-Linear Algebra

Using Gaussian elimination, we can solve, efficiently, any system of linear
equations with any (finite) number of unknowns. Using the Buchberger algorithm
[B1] [B2] (see the modern classic [CLO] for a lucid and engaging account) we
can solve any system of non-linear equations with any (finite) number of
unknowns. Alas, due to the non-linearity, we can only go so far, but yet, with
modern computers, and computer algebra systems (our favorite being Maple), one
can do a lot.

In the applications that we need, the scenario is that we have $N$ quantities
$X_{1},\dots,X_{N}$ and they satisfy $N$ polynomial equations

$P_{i}(t;X_{1},\dots,X_{n})=0\quad,\quad 1\leq i\leq N\quad,$

where $t$ is variable (or multi-variable), that may be viewed as a parameter.
We are really only interested in the first quantity, $X_{1}=X_{1}(t)$.

In our application, these equations are derived using combinatorial
considerations, that we can teach to the computer. There is one primary
object, $X_{1}$, that we really care about, but in order to determine it, we
need to introduce secondary objects, $X_{2},\dots,X_{n}$, that we don’t care
about, and whose sole raison d’être is that they enable us to get a grip on
$X_{1}$.

All we want is a succinct algebraic relation of the form $Q(X_{1},t)=0$, where
$Q$ is a bi-variate polynomial of $X_{1}$ and $t$.

In order to eliminate the unwanted quantities $X_{2},\dots,X_{n}$, and get a
pure equation only involving $X_{1}$ (and the auxiliary variable (or
variables), $t$), the command in Maple is:

$Groebner[Basis](\\{P_{1},P_{2},\dots,P_{n}\\},plex(X_{2},X_{3},\dots,X_{n},X_{1}))[1];\,.$

To take a random example (we just made up), suppose that we have the system of
three equations in the three unknowns $X,Y,Z$ that depend on some auxiliary
variable $t$:

$X=Y^{2}+Z^{2}+1\quad,\quad Y=X^{2}+3Z^{2}+t\quad,\quad Z=XYZ+t+1\quad,$

and we want to eliminate $Y$ and $Z$, i.e. get an algebraic equation in
$X=X(t)$ that only involves, in addition to $X$, the variable $t$. Then type
in a Maple session

Groebner[Basis]( $\\{$ X-Y**2-Z**2-1,Y-X**2-3*Z**2-t, Z-X*Y*Z-t-1 $\\}$
,plex(Y,Z,X))[1]=0;

getting that our quantity of interest $X=X(t)$, satisfies the following
degree-$12$ polynomial equation in $X(t)$ (abbreviated $X$), with coefficients
that are polynomials of $t$:

$X^{12}+6X^{11}+\left(4t+3\right)X^{10}+\left(18t-21\right)X^{9}+\left(6t^{2}-8\right)X^{8}+\left(18t^{2}-44t-9\right)X^{7}$
$+\left(4t^{3}+9t^{2}+20t+60\right)X^{6}+\left(6t^{3}+29t^{2}+96t+43\right)X^{5}+\left(t^{4}+30t^{3}+16t^{2}-14t-24\right)X^{4}$
$+\left(52t^{3}+177t^{2}+232t+50\right)X^{3}+\left(18t^{4}-12t^{3}+89t^{2}+242t+149\right)X^{2}$
$+\left(54t^{3}+12t^{2}-150t-105\right)X+81t^{4}+378t^{3}+612t^{2}+396t+99\,=\,0\quad.$

The Art of Counting in General

In enumerative combinatorics, we are interested in counting families of sets
$\\{A(n)\\}$, defined by some combinatorial conditions, indexed by (one or
more) discrete parameter(s) $n$. The best possible scenario is an explicit
(aka closed form) expression for $a(n):=|A(n)|$, where as usual $|S|$ denotes
the number of elements of the finite set $S$.

For example, the number of words in the alphabet $\\{0,1\\}$ of length $n$
(Ans.: $2^{n}$), or the number of permutations of length $n$ (Ans.: $n!$).

Alas, in many cases there is no closed form (unless you consider $\sum_{s\in
A(n)}1$ as one), and one looks for a closed-form, or failing this, an
equation, satisfied by the (ordinary) generating function

$X(t)\,=\,\sum_{n=0}^{\infty}a(n)t^{n}\quad.$

In many applications, including all those in the present paper, it is better
to think of $X(t)$ as a weight enumerator of the (usually) ‘infinite’ set

${\cal A}\,:=\,\bigcup_{n=0}^{\infty}A(n)\quad,$

and define, $Weight(s):=t^{n}$ if $s\in A(n)$. The generating function,
$X(t)$, is the total weight (i.e. sum of all the weights of its members) of
${\cal A}$, denoted by $Weight({\cal A})$.

Reminders about Counting Classical Dyck and Motzkin Walks

In order to illustrate our general approach, already initiated in [AyZ], and
further pursued in [TZ], [EK1], and [EK2], let’s revisit the very classical
problem of counting (ungeneralized) Dyck walks. These are walks that start at
the origin $(0,0)$, end somewhere on the $x$-axis, using the atomic steps
$[1,1],[1,-1]$ (i.e. moving from $(x,y)$ to either $(x+1,y+1)$ or $(x+1,y-1)$,
respectively) and crucially, always stay in the upper-half plane $y\geq 0$.

The weight of a walk $w$ is $t^{NumberOfSteps(w)}$, in other words $t^{n}$, if
the endpoint of our walk is $(n,0)$.

Let $f[0,0](t)$ be our object of desire, the weight-enumerator of all Dyck
walks. There are two possibilities.

$\bullet$ The walk is empty (of length $0$), with weight $t^{0}=1$.

$\bullet$ The walk, let’s call it $w$, sooner of later, again touches the
$x$-axis. Let $w_{1}$ be the prefix of $w$ consisting of this portion and let
$w_{2}$ be the rest, so we can express $w$ as the catenation $w=w_{1}\,w_{2}$,
where $w_{2}$ is a (possibly empty) shorter walk weight-counted by
$f[0,0](t)$, but $w_{1}$ is a strict Dyck path, a walk that starts and ends on
the $x$-axis, and except at the endpoints, is strictly above the $x$-axis.
Let’s call the weight-enumerator of these kind of walks $g[0,0](t)$.

Taking weights, we get a first equation

$f[0,0](t)=1+g[0,0](t)\cdot f[0,0](t)\quad.$

Note that we were forced to introduce the quantity $g[0,0](t)$.

Let’s look at the anatomy of such a walk that is weight-enumerated by
$g[0,0](t)$. Since it is non-empty, and can’t get below the $x$-axis, it must
start with the step $[1,1]$, i.e. the first step is from the origin $(0,0)$ to
$(1,1)$. Since sooner or later it must return to the $x$-axis, its last step
must be a down step $[1,-1]$, from $(n-1,1)$ to $(n,0)$ (say). Removing this
first and last step is a walk that is shorter by two steps that is weakly
above the line $y=1$. But these walks are in obvious bijection with walks
weight-counted by $f[0,0](t)$. Hence we get a second equation

$g[0,0](t)\,=\,t^{2}\cdot f[0,0](t)\ \quad.$

So we get a system of two equations and two unknowns.

In this case, we don’t need a computer, or Bruno Buchberger, to solve this
system, and eliminating $g[0,0](t)$ gives the quadratic equation for
$f[0,0](t)$ (let’s abbreviate it to $f[0,0]$)

$t^{2}\,f[0,0]^{2}-f[0,0]+1\,=\,0\quad,$

that thanks to the Babylonians can be solved in terms of radicals, yielding
the Catalan numbers.

Similarly, for Motzkin walks, where the set of steps is
$\\{[1,1],[1,0],[1,-1]\\}$, we still only have one extra quantity $g[0,0](t)$,
and the two equations are

$\\{f[0,0]=1\,+\,tf[0,0]\,+\,g[0,0]\cdot f[0,0]\quad,\quad
g[0,0]\,=\,t^{2}\cdot f[0,0]\\}\quad,$

that again lead to a simple quadratic equation, whose solution is the
generating function for Motzkin numbers.

The primary novelty of the present article is to keep track of the area
statistics. Let $f[0,0](t,q)$, that we will still call $f[0,0](t)$ for short
(not to be confused with the previous $f[0,0](t)$), but it is implied that
there is also a variable $q$, that may be viewed as a parameter, be the
weight-enumerator of Dyck walks according to the bi-variate weight

$Weight(w):=t^{LengthOf(w)}\,q^{AreaUnder(w)}\quad.$

One way to define the ‘area’ without geometry is as the sum of the
$y$-coordinates of all the intermediate points on the walk.

Going back to the classical Dyck case, instead of a system of algebraic
equations, we get a system of functional equations. It is easy to see that we
have .

$\\{f[0,0](t)\,=\,1+g[0,0](t)\cdot f[0,0](t)\quad,\quad
g[0,0](t)\,=\,qt^{2}\cdot f[0,0](qt)\\}\quad.$

Of course one can eliminate $g[0,0](t)$ and get a pure functional equation for
$f[0,0](t)$ (let’s call it $X(t)$).

$X(t)=1\,+\,qt^{2}\cdot X(t)\cdot X(qt)\quad.$

Alas $f[0,0](t)=X(t)$ is no longer an algebraic formal power series.

The study of the area under Dyck paths was pioneered in [MSV] and further
explored in [Wo],[SRW], and for higher moments by Robin Chapman [C]. We will
soon see how to fully automate this to a much more general setting. In
particular, our Maple package, GDW.txt, can confirm, in a few nano-seconds,
all their beautiful human-generated results.

Similarly, for the Motzkin case, the system of functional equations is:

$\\{f[0,0](t)=1\,+\,t\cdot f[0,0](t)\,+\,g[0,0](t)\cdot f[0,0](t)\quad,\quad
g[0,0](t)\,=\,qt^{2}\cdot f[0,0](qt)\\}\quad,$

and the pure functional equation for $f[0,0](t)$ (again let’s call it $X(t)$)
is:

$X(t)=1\,+\,t\cdot X(t)\,+\,qt^{2}\cdot X(t)\cdot X(qt)\quad.$

The bi-variate generating function contains lots of statistical information.
To get the average area under a random Dyck walk, we must first compute the
generating function for the ‘sum of the areas of all walks’ that is given by

${d\over dq}f[0,0](t){\big{|}}_{q=1}\quad,$

(recall that $f[0,0](t)$ is really a function of both $t$ and $q$.). More
generally, the generating function for the sum of the $r$-th powers of the
areas, is

$\left(q{d\over dq}\right)^{r}f[0,0](t){\big{|}}_{q=1}\quad.$

If you are interested in these quantities up to the $r$-th power of the area,
we can taylor expand $f[0,0](t)$ (and similarly $g[0,0](t)$) as a Taylor
expansion about $q=1$:

$f[0,0](t)=f[0,0,0](t)+f[0,0,1](t)(q-1)+f[0,0,2](t)(q-1)^{2}+\dots+f[0,0,r](t)(q-1)^{r}+\dots$

where $f[0,0,0](t),f[0,0,1](t),\dots$ are formal power series of $t$ alone,
and do not depend on $q$. (Note that what we now call $f[0,0,0](t)$ is
identical to what we called $f[0,0](t)$ in the original, straight-enumeration
case).

It would follow from the algorithm to be described shortly, that these are all
algebraic formal power series, and thanks to the Buchberger Gröbner basis
algorithm, we can actually find the pure equations that they each satisfy.

Plugging this series expansion into the functional equation, would introduce
quantities like $f[0,0,0](qt)$.

For this we need an elementary lemma from Calculus:

Simple Lemma: Let $f(t)$ be a formal power series of a single variable $t$,
and $q$ be another variable, then

$f(qt)\,=\,f(t)+(q-1)tf^{\prime}(t)+{1\over
2}(q-1)^{2}t^{2}f^{\prime\prime}(t)+\dots+{1\over
r!}(q-1)^{r}t^{r}f^{(r)}(t)+\dots\quad.$

So we can Taylor-expand it with respect to $q$ around $q=1$, and thanks to
Calculus, that Maple knows so well, automatically express it in terms of
$f[0,0,0]^{\prime}(t),f[0,0,1]^{\prime}(t)\dots\quad$. It seems that we have
too many quantities, and that we need more equations. But we can also
(automatically!) differentiate with respect to $t$ the algebraic equation
satisfied by $f[0,0,0](t)$, (and if needed, by $f[0,0,1](t)$ etc.) using
implicit differentiation (that Maple also knows!), and collect terms, and at
the end of the day we would have as many algebraic equations as quantities. If
we want to focus, say, on $f[0,0,1](t)$ (alias $({\partial\over\partial
q})f[0,0](t){\big{|}}_{q=1}$, alias the generating function for the ‘sum of
areas’ of the walks), we can use Buchberger’s algorithm as above with plex,
singling out $f[0,0,1](t)$. Ditto for higher (factorial) moments, i.e.
$f[0,0,2](t),f[0,0,3](t),\dots$ except that things do get more and more
complicated, even for computerkind.

Straight Enumeration of Generalized Dyck Paths

Let’s recall the method initiated in [AyZ], extended in [EK1] and [EK2], and
continued in [TZ], but with a new implementation, that makes full use of
Gröbner bases. Alternative approaches to the problem of (straight) enumeration
have been undertaken by Banderier et. al. [BKKKKNW], using the kernel method,
and in [EkhZ], using “Guess and Check”.

The input is an arbitrary set of integers, $S$, and our goal is to find a pure
algebraic equation of the form

$\sum_{i=0}^{d}p_{i}(t)X(t)^{i}\quad=0,$

where $p_{i}(t)$ are polynomials in $t$ for the following formal power series

$X(t)=\sum_{n=0}^{\infty}a_{S}(n)\,t^{n}\quad,$

where $a_{S}(n)$ is the number of walks from $(0,0)$ to $(n,0)$, in the 2D
lattice, with the set of allowable steps

$(x,y)\rightarrow(x+1,y+s)\quad,\quad s\in S\quad,$

and that always stay in the upper half plane $y\geq 0$. Equivalently, and more
useful for us, it is the weight enumerator, according to the weight
$t^{NumberOfSteps}$, of the (infinite) set of all these walks.

Remark: If you don’t insist on always staying above the $x$-axis, then the
number of such $n$-step walks from the origin to the $x$-axis, is the constant
term of

$\left(\sum_{s\in S}t^{s}\right)^{n}\quad\quad,$

and it is possible, very fast, to use the Almkvist-Zeilberger algorithm [AlZ]
(see [D] for a great exposition) to get a linear recurrence equation with
polynomial coefficients.

Note that if $S$ only consists of positive integers, or only consists of
negative integers, then $X(t)$ is trivially $1$. So for things to be non-
trivial, $S$ must have at least one positive member and at least one negative
member.

We will rename $X(t)$, $f[0,0](t)$, since we need to introduce auxiliary
quantities $f[a,b](t)$ and $g[a,b](t)$.

For integer $a\geq 0$ and $b\geq 0$,

$\bullet$ Let $f[a,b](t)$ be the weight-enumerator of walks with a set of
steps given by $S$, that start at the point $(0,a)$ and end on the horizontal
line $y=b$ and stay weakly above the $x$-axis.

$\bullet$ Let $g[a,b](t)$ be the weight-enumerator of non-empty walks with a
set of steps given by $S$, that start at the point $(0,a)$ and end on the
horizontal line $y=b$ and stay strictly above the $x$-axis, except at an
endpoint when $a=0$ or $b=0$. If both $a>0$ and $b>0$ then we have no need for
it, and we declare that it is $0$.

For each $f[a,b](t)$ and $g[a,b](t)$ that will show up we would need to set
its own equation.

How to form the Equations for the $f[a,b]$?

$\bullet$ If $a>0$ and $b>0$ then

$f[a,b]\,=\,g[a,0]\cdot f[0,b]\,+\,f[a-1,b-1]\quad.$

Explanation: if such a walk, that starts at $y=a$ and ends at $y=b$, touches
the $x$-axis, then the first portion until that first encounter is a walk
weight-counted by $g[a,0]$, while the second part is a walk weight-counted by
$f[0,b]$ (it starts at $y=0$, ends at $y=b$ and stays weakly above the
$x$-axis). On the other hand, if it never touches the $x$-axis it must stay in
$y\geq 1$, so lowering it by $1$ unit, yields a walk weight-counted by
$f[a-1,b-1]$.

$\bullet$ If $a>0$ and $b=0$ then

$f[a,0]\,=\,g[a,0]\cdot f[0,0]\quad.$

Explanation: A walk that starts at $(0,a)$ and ends on $y=0$, must meet the
$x$-axis for the first time, this initial portion is weight-counted by
$g[a,0]$, the remaining portion of the walk is weight-counted by $f[0,0]$.

Similarly

$\bullet$ If $a=0$ and $b>0$ then

$f[0,b]\,=\,f[0,0]\cdot g[0,b]\quad.$

$\bullet$ If $a=0$ and $b=0$ and $0\not\in S$

$f[0,0]\,=\,1\,+\,g[0,0]\cdot f[0,0]\quad.$

Explanation: A walk that starts and ends on $y=0$ may be the empty walk
(weight=$1$). If not, it can be broken up into the portion until the first
encounter with the $x$ axis, that is weight-counted by $g[0,0]$, followed by
any-old (shorter) walk weight-counted by $f[0,0]$.

$\bullet$ If $a=0$ and $b=0$ and $0\in S$

$f[0,0]\,=\,1\,+\,t\cdot f[0,0]\,+\,g[0,0]\cdot f[0,0]\quad.$

Explanation: Now the first step could also be $(0,0)\rightarrow(1,0)$, and
after that it is a typical walk weight-counted by $f[0,0]$.

This is implemented in procedure MakeEqF(f,g,x,a,b,S) in our Maple package. In
fact, it is more general, keeping track of the individual steps.

How to form the Equations for the $g[a,b]$?

We also need to set up equations for $g[a,b]$ for those $(a,b)$ that would be
needed.

Let $P$ be the subset of $S$ consisting of the (strictly) positive members of
$S$, and let $N$ be the subset of $S$ consisting of the (strictly) negative
members of $S$, so if $0\in S$ then

$S=P\cup N\cup\\{0\\}\quad,$

while, if $0\not\in S$ then

$S=P\cup N\quad.$

$\bullet$ If $a=0$ and $b>0$ then

$g[0,b]=t\left(\sum_{i\in P}f[a+i-1,b-1]\right)\quad.$

Explanation: Such a walk must start with a step of the form $[1,i]$ where
$i\in P$, and then it is always in $y\geq 1$. Removing that first step (weight
$t$) and ‘lowering’ it by $1$ unit, is in bijection with a walk weight-counted
by $f[a+i-1,b-1]$.

$\bullet$ If $a>0$ and $b=0$ then

$g[a,0]=t\left(\sum_{j\in N}f[a-1,b-j-1]\right)\quad.$

Explanation: Such a walk must end with a step of the form $[1,j]$ where $j\in
N$, and before that it is always in $y\geq 1$. Removing that last step (weight
$t$) and ‘lowering’ it by $1$ unit, is in bijection with a walk weight-counted
by $f[a-1,b-j-1]$.

$\bullet$ If $a=0$ and $b=0$ then

$g[0,0]=t^{2}\left(\sum_{i\in P}\sum_{j\in N}f[a+i-1,b-j-1]\right)\quad.$

Explanation: Every non-empty walk that starts at $y=0$ and ends at $y=0$ and
that never touches the $x$-axis except at the two endpoints, must start with a
positive step $[1,i]$ and end with a negative step $[1,j]$. Deleting the first
and last steps gives you a shorter walk (with two steps shorter) that is
always in the region $y\geq 1$. Lowering the remaining walk by $1$ unit gives
a walk weight-counted by $f[a+i-1,b-j-1]$.

This is implemented in procedure MakeEqG(f,g,x,a,b,S) in our Maple package.
Again, it is more general keeping track of the individual steps.

To get the full system of equations with a set of steps S, type:

MakeSysT(f,g,t,S);

It returns the set of equations, followed by the set of quantities that
participate. For example

MakeSysT(f,g,t, $\\{$ 1,2,-1,-2 $\\}$ )[1]; gives

$\\{f_{00}=f_{00}g_{00}+1\quad,\quad f_{01}=f_{00}g_{01}\quad,\quad
f_{10}=g_{10}f_{00}\quad,\quad f_{11}=f_{01}g_{10}+f_{00},$
$g_{00}=t^{2}f_{00}+t^{2}f_{01}+t^{2}f_{10}+t^{2}f_{11}\quad,\quad
g_{01}=tf_{00}+tf_{10}\quad,\quad g_{10}=tf_{00}+tf_{01}\\}\quad,$

while MakeSysT(f,g,t, $\\{$1,2,-1,-2 $\\}$)[2]; gives the set of quantities

$\\{f_{00}\quad,\quad f_{01}\quad,\quad f_{10}\quad,\quad f_{11}\quad,\quad
g_{00}\quad,\quad g_{01}\quad,\quad g_{10}\\}\quad.$

Weighted Enumeration of Generalized Dyck Paths According to the Area

We can teach Maple how, all by itself, set up a system of functional
equations, for the $q$-analog, where one keeps track of the area. Everything
is analogous.

For integer $a\geq 0$ and $b\geq 0$,

$\bullet$ Let $f[a,b](t)$ be the weight-enumerator of walks with a set of
steps given by $S$, that start at the point $(0,a)$ and end on the horizontal
line $y=b$ and stay weakly above the $x$-axis, but now the weight of a walk is
not just $t^{length}$ but rather $t^{length}\cdot q^{AreaUnder}$. For the sake
of notational convenience, We still write $f[a,b](t)$ rather than
$f[a,b](t,q)$, but one should keep in mind that they all depend on $q$. We can
think of $q$ as a parameter.

Similarly,

$\bullet$ Let $g[a,b](t)$ be the weight-enumerator (in the above sense of
$t^{length}\cdot q^{AreaUnder}$) of non-empty walks with a set of steps given
by $S$, that start at the point $(0,a)$ and end on the horizontal line $y=b$
and stay strictly above the $x$-axis, except at an endpoint when $a=0$ or
$b=0$. If both $a>0$ and $b>0$ then we have no need for it and we declare that
it is $0$.

How to form the Functional Equations for $f[a,b](t)$?

$\bullet$ If $a>0$ and $b>0$ then

$f[a,b](t)=g[a,0](t)\cdot f[0,b](t)\,+\,f[a-1,b-1](q\,t)\quad.$

Explanation: if such a walk that starts at $y=a$ and ends at $y=b$ touches the
$x$-axis, then the first portion until that first encounter is a walk weight-
counted by $g[a,0](t)$, while the second part is a walk weight-counted by
$f[0,b](t)$ (it starts at $y=0$, ends at $y=b$ and stays weakly above the
$x$-axis). On the other hand, if it never touches the $x$-axis, it must stay
in $y\geq 1$, so lowering it by $1$ unit, results in a walk weight-counted by
$f[a-1,b-1](t)$. But, by lowering it, we lost some area!. If the length of the
walk is $n$, then we lost $n$ units of area (the area of an $n\times 1$
rectangle), hence this is bi-weight-enumerated by $f[a-1,b-1](q\,t)$, (rather
than $f[a-1,b-1](t)$.)

$\bullet$ If $a>0$ and $b=0$ then

$f[a,0](t)\,=\,g[a,0](t)\cdot f[0,0](t)\quad.$

Explanation: Each walk that starts at $y=a$ must meet the $x$-axis for the
first time, this portion is weight-counted by $g[a,0](t)$, the remaining
portion of the walk is weight-counted by $f[0,0](t)$.

Similarly:

$\bullet$ If $a=0$ and $b>0$ then

$f[0,b](t)\,=\,f[0,0](t)\cdot g[0,b](t)\quad,$

$\bullet$ If $a=0$ and $b=0$ and $0\not\in S$

$f[0,0](t)\,=\,1\,+\,g[0,0](t)\cdot f[0,0](t)\quad.$

Explanation: Each walk that starts and ends on $y=0$ must either be the empty
walk (of length $0$, area $0$, and hence with weight $t^{0}\cdot q^{0}=1$), or
else meet the $x$-axis for the first time (weight-counted by $g[0,0](t)$),
followed by any-old walk (possibly empty) weight-counted by $f[0,0](t)$.

$\bullet$ If $a=0$ and $b=0$ and $0\in S$

$f[0,0](t)\,=\,1\,+\,t\cdot f[0,0](t)\,+\,g[0,0](t)\cdot f[0,0](t)\quad.$

Explanation: Now the first step could also be $(0,0)\rightarrow(1,0)$, and
after that it is a typical walk weight-counted by $f[0,0](t)$, and there is no
area gain.

This is implemented in procedure qMakeEqF(f,g,t,q,a,b,S) in our Maple package.

How to form the Functional Equations for $g[a,b](t)$?

We also need to set up equations for $g[a,b](t)$ for those $(a,b)$ that would
be required.

As before:

Let $P$ be the subset of $S$ consisting of the (strictly) positive members of
$S$, and let $N$ be the subset of $S$ consisting of the (strictly) negative
members of $S$, so if $0\in S$ then

$S=P\cup N\cup\\{0\\}\quad,$

while, if $0\not\in S$ then

$S=P\cup N\quad.$

$\bullet$ If $a=0$ and $b>0$ then

$g[0,b](t)=t\left(\sum_{i\in P}q^{i/2}\,f[a+i-1,b-1](qt)\right)\quad.$

Explanation: Such a walk must start with a step of the form $[1,i]$ where
$i\in P$, and then it is always in $y\geq 1$. Removing that first step reduces
the area by $1\times i/2=i/2$ and ‘lowering’ by $1$ unit, it looses $n$ units
of area (if the remaining path has length $n$), to account for the lost area
we need $f[a+i-1,b-1](qt)$, (rather than $f[a+i-1,b-1](t)$).

Similarly:

$\bullet$ If $a>0$ and $b=0$ then

$g[a,0](t)=t\left(\sum_{j\in N}q^{-j/2}f[a-1,b-j-1](qt)\right)\quad.$

$\bullet$ If $a=0$ and $b=0$ then

$g[0,0](t)=t^{2}\left(\sum_{i\in P}\sum_{j\in
N}q^{i/2-j/2}\,f[a+i-1,b-j-1](qt)\right)\quad.$

Explanation: Every walk that starts at $y=0$ and ends at $y=0$ and that never
touches the $x$-axis except at the endpoints, must start with a positive step
$[1,i]$ and end with a negative step $[1,j]$. Deleting the first and last
steps gives you a shorter walk (with two steps shorter) that is always in the
region $y\geq 1$. Removing the first step (i.e. $(0,0)\rightarrow(1,i)$)
reduces the area by $i/2$. Removing the last step (i.e.
$(n-1,-j)\rightarrow(n,0)$) reduces the area by $-j/2$.

Lowering it by $1$ unit gives a walk weight-counted by $f[a+i-1,b-j-1](qt)$.

This is implemented in procedure qMakeEqGt(f,g,t,q,a,b,S) in our Maple
package.

To get the full system of functional equations, followed by the quantities
that feature in them, with set of steps S, type:

qMakeSysT(f,g,t,q,S); .

For example, if the set of steps is $S=\\{2,1,0,-1,-2\\}$, typing

qMakeSyst(f,g,t,q, $\\{$ 2,1,0,-1,-2 $\\}$ )[1];

gives

$\\{f_{01}\\!\left(t\right)-f_{00}\\!\left(t\right)g_{01}\\!\left(t\right)\quad,\quad
f_{10}\\!\left(t\right)-g_{10}\\!\left(t\right)f_{00}\\!\left(t\right)\quad,$
$f_{11}\\!\left(t\right)-f_{01}\\!\left(t\right)g_{10}\\!\left(t\right)-f_{00}\\!\left(qt\right)\quad,\quad
g_{01}\\!\left(t\right)-t\sqrt{q}\,f_{00}\\!\left(qt\right)-tqf_{10}\\!\left(qt\right)\quad,$
$g_{10}\\!\left(t\right)-tqf_{01}\\!\left(qt\right)-t\sqrt{q}\,f_{00}\\!\left(qt\right),\quad
f_{00}\\!\left(t\right)-f_{00}\\!\left(t\right)g_{00}\\!\left(t\right)-f_{00}\\!\left(t\right)t-1\quad,$
$g_{00}\\!\left(t\right)-t^{2}q^{{3\over
2}}f_{01}\\!\left(qt\right)-t^{2}qf_{00}\\!\left(qt\right)-t^{2}q^{2}f_{11}\\!\left(qt\right)-t^{2}q^{{3\over
2}}f_{10}\\!\left(qt\right)\\}\quad,$

while to see the set of featured quantities type

qMakeSyst(f,g,t,q, $\\{$ 2,1,0,-1,-2 $\\}$)[2]; , getting

$\\{f_{00}\\!\left(t\right)\quad,\quad f_{00}\\!\left(qt\right)\quad,\quad
f_{01}\\!\left(t\right)\quad,\quad f_{01}\\!\left(qt\right)\quad,\quad
f_{10}\\!\left(t\right)\quad,\quad f_{10}\\!\left(qt\right)\quad,\quad$
$f_{11}\\!\left(t\right)\quad,\quad f_{11}\\!\left(qt\right)\quad,\quad
g_{00}\\!\left(t\right)\quad,\quad g_{01}\\!\left(t\right)\quad,\quad
g_{10}\\!\left(t\right)\\}\quad.$

From Functional Equations to Algebraic Equations

After the computer finds the system of functional equations described above,
we instruct it to find a system algebraic equations for the ‘components’ of
the $f[a,b](t)$ (and we also need $g[a,b](t)$). If we are interested in
finding the pure algebraic equation satisfied by the formal power series
$f[0,0,0](t),f[0,0,1](t),\dots,f[0,0,k](t)$. We write

$f[0,0](t)=\sum_{i=0}^{k}f[0,0,i](t)(q-i)^{i}+O((q-1)^{k+1})\quad,$

and analogously for the other $f[a,b](t)$ and $g[a,b](t)$, then expand in
powers of $(q-1)$, collect terms, use the Lemma, and get more equations by
differentiating with respect to $t$ each of these equations up to the $k$-th
derivative, using implicit differentiation.

Because of the extreme complexity, we decided only to implement this scheme
for $k=1$, i.e. for finding the algebraic equation satisfied by the generating
function for the ‘sum of the areas’.

This is implemented in procedure qEqGFt(S,X,t) . For example, to get the
algebraic equation for the generating function for ‘sum of areas’ of the
classical Dyck paths, type:

qEqGFt($\\{$1,-1$\\}$,X,t);

getting

$t^{2}\,-\,(4t^{2}-1)(2t^{2}-1)X\,+\,t^{2}(4t^{2}-1)^{2}\,X^{2}\,=\,0\quad.$

(This is A8549 of [Sl], https://oeis.org/A008549).

For Motzkin walks, typing

qEqGFt($\\{$1,0,-1$\\}$,X,t);, gives

$t^{2}-\left(3t-1\right)\left(t+1\right)\left(t^{2}+2t-1\right)X+t^{2}\left(3t-1\right)^{2}\left(t+1\right)^{2}X^{2}\,=\,0\quad.$

(This is A57585 of [Sl], https://oeis.org/A057585).

For a more complicated example, to get the pure algebraic equation satisfied
by the generating function for the ‘sum of the areas under generalized Dyck
paths with set of steps $\\{[1,2],[1,1],[1,0],[1,-1],[1,-2]\\}$’, type:

qEqGFt($\\{$ 2,1,0,-1,-2 $\\}$,X,t);, getting, after less than a minute,

$t^{2}\left(775t^{4}-1460t^{3}+1006t^{2}-264t+24\right)$
$+\left(t-1\right)\left(5t-1\right)\left(425t^{6}-1520t^{5}+1527t^{4}-68t^{3}-282t^{2}+88t-8\right)X$
$-t\left(150t^{5}+540t^{4}-889t^{3}-240t^{2}+228t-32\right)\left(t-1\right)^{2}\left(5t-1\right)^{2}X^{2}$
$-2t^{2}\left(5t+4\right)\left(5t^{3}-t^{2}-17t+4\right)\left(t-1\right)^{3}\left(5t-1\right)^{3}X^{3}+t^{4}\left(5t+4\right)^{2}\left(t-1\right)^{4}\left(5t-1\right)^{4}X^{4}\,=\,0\quad.$

(This is not (yet, May 15, 2023) in the OEIS. Note that the straight
enumeration version is A104184 of [Sl], https://oeis.org/A104184). For the
sake of the OEIS, here are the first $30$ terms:

$0,0,3,18,113,636,3487,18656,98429,514012,2664690,13737758,70522801,360806214,1840913908,$
$9371761174,47621259557,241601881822,1224111502194,6195045902854,$
$31321134873744,158217553824544,798622703316154,4028438371631942,$
$20308239308212037,102323623873153810,515313296262175206,2594054240062008690,$
$13053194513626873348,65659889953142043376\quad.$

Strict Generalized Dyck paths

If we want to count strict generalized Dyck paths (respectively, sum of the
areas), i.e. paths that never touch the $x$-axis except at the endpoints, use
procedures EqGFtS(S,X,t) and qEqGFtS(S,X,t) respectively.

For the algebraic equation for the generating function for the sum of the
areas under strict classical Dyck paths, type

qEqGFtS($\\{$1,-1$\\}$,X,t);, getting that the equation is

$\left(4t^{2}-1\right)X+t^{2}\,=\,0\quad,$

that implies

$X(t)={t^{2}\over 1-4t^{2}}\quad,$

confirming, purely automatically, the following elegant proposition first
discovered, and proved, in [SRW] (see also [C]):

Proposition (Shapiro, Rogers, and Woan) The sum of the areas of the strict
Dyck paths of length $2n$ is $4^{n-1}$.

What about sum-of-the-areas of strict Motzkin paths? Typing

qEqGFtS($\\{$ 1 ,0,-1 $\\}$,X,t); gives

$\left(3t^{2}+2t-1\right)X+t^{2}\,=\,0\quad,$

implying that

$X(t)={t^{2}\over 1-2t-3t^{2}}\quad.$

This is A015518[n-1] of [Sl] (see https://oeis.org/A015518). This sequence has
numerous combinatorial interpretations, but so far, the connection to the sum
of the areas under strict Motzkin paths escaped notice.

Efficient Computation of many terms

It is well-known and fairly easy to see (e.g. the modern classic [KP]) that
every algebraic formal power series is $D$-finite, and equivalently, the
sequence itself satisfies some linear recurrence equation with polynomial
coefficients. The Maple package gfun (designed by Bruno Salvy and Paul
Zimmermann) can do it for you, but it is just as easy to use guessing. Using
dynamical programming one can easily crank out many terms, and then use
‘guessing’ (implemented in listtorec in gfun, but we have our own home-made
version). Now we can even talk about sum-of-square-of-areas, and even higher
powers.

Sample Output

Straight Enumeration of Generalized Dyck Paths

$\bullet$ If you want to see $16$ theorems stating algebraic equations
satisfied by generating functions enumerating generalized Dyck paths with set
of steps that are subsets of $\\{-2,-1,0,1,2\\}$ (excluding trivial cases) and
sometimes linear recurrences with polynomial coefficients satisfied by the
sequences themselves, enjoy

https://sites.math.rutgers.edu/~zeilberg/tokhniot/oGDW1.txt  .

$\bullet$ If you want to see $94$ theorems stating algebraic equations
satisfied by generating functions enumerating generalized Dyck paths with set
of steps that are subsets of $\\{-3,-2,-1,0,1,2,3\\}$ (excluding trivial
cases) and sometimes linear recurrences with polynomial coefficients satisfied
by the sequences themselves, enjoy

https://sites.math.rutgers.edu/~zeilberg/tokhniot/oGDW2.txt  .

[Of course this file includes all the theorems in the previous file].

$\bullet$ If you want to see (one) theorem about the algebraic equation
satisfied by the generating function enumerating generalized Dyck paths with
set of steps $\\{-4,-3,-2,-1,0,1,2,3,4\\}$, look at

https://sites.math.rutgers.edu/~zeilberg/tokhniot/oGDW3.txt  .

It has degree $41$ in $X(t)$!

Enumeration According to the Sum of Areas of Generalized Dyck Paths

$\bullet$ If you want to see $16$ theorems stating algebraic equations for the
SUM OF THE AREAS under generalized Dyck paths for all non-trivial subsets of
$\\{-2,-1,0,1,2\\}$, as well, as estimates for the asymptotics of the average
area (divided by $n^{3/2}$ (the ratio always tends to some constant)), see

https://sites.math.rutgers.edu/~zeilberg/tokhniot/oGDW7.txt  .

$\bullet$ If you want to see interesting information about generalized Dyck
paths for all non-trivial subsets of $\\{-2,-1,0,1,2\\}$, that consist of
linear recurrences (obtained by guessing, but definitely correct, since we
know they exist from theoretical reasons), for the straight enumeration,
enumeration by ‘sum of areas’, and sometimes, enumeration by ‘sum of area-
squared’, enabling estimates not only of the asymptotic average area, but also
of the asymptotic variance, look here:

https://sites.math.rutgers.edu/~zeilberg/tokhniot/oGDW8.txt  .

Conclusion

We described an interesting application of Bruno Buchberger’s seminal Gröbner
Basis algorithm, and at the same time demonstrated how an important class of
enumerative combinatorics problems can be fully automated, using the great
power of modern Computer Algebra Systems (in our case Maple), also using
calculus (that Maple knows very well), as well as good-old numerical (and
symbolic) dynamical programming. We also demonstrated how to teach the
computer to build, ab initio, the system of equations (sometimes quite large)
before asking it to kindly solve it.

References

[AlZ] Gert Almkvist and Doron Zeilberger, The method of differentiating under
the integral sign, J. Symbolic Computation 10 (1990), 571-591.
https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/duis.pdf . [It is
implemented in procedure AZd in the Maple package
https://sites.math.rutgers.edu/~zeilberg/tokhniot/EKHAD.txt ]

[AyZ] Arvind Ayyer and Doron Zeilberger, The Number of [Old-Time] Basketball
games with Final Score n:n where the Home Team was never losing but also never
ahead by more than w Points, Electronic J. of Combinatorics 14(1) (2007), R19
[8 pp].
https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/basketball.html .

[BKKKKNW] C. Banderier, C. Krattenthaler, A. Krinik, D. Kruchinin, V.
Kruchinin, D. Nguyen, and M. Wallner, Explicit formulas for enumeration of
lattice paths: basketball and the kernel method, arXiv preprint
arXiv:1609.06473 [math.CO], 2016. https://arxiv.org/abs/1609.06473

[B1] Bruno Buchberger, “Ein Algorithmus zum Auffinden der Basiselemente des
Restklassenringes nach einem nulldimensionalen Polynom ideal”, PhD thesis,
University of Innsbruck, 1965.

[B2] Bruno Buchberger, Gröbner Bases: an algorithmic method in polynomial idea
theory. In: “Multidimensional Systems Theory”, ed. N.K. Bose, “Mathematics and
Its Applications”, chapter 6, 184-232. D. Reidel Publishing company,
Dordrecht, 1985.

[Ch] Robin Chapman, Moments of Dyck paths, Discrete Mathematics 204 (1999),
113-117.

[CLO] David Cox, John Little, and Donald O’Shea, “Ideals, Varieties, and
Algorithms”, Springer, 1991.

[D] Robert Dougherty-Bliss, Integral Recurrences from A to Z, American
Mathematical Monthly 129 (2022), 805-815. https://arxiv.org/abs/2102.10170

[Ek1] Bryan Ek, “Unimodal Polynomials and Lattice Walk Enumeration with
Experimental Mathematics”, PhD thesis, Rutgers University, May 2018. Available
from http://sites.math.rutgers.edu/~zeilberg/Theses/BryanEkThesis.pdf .

[Ek2] Bryan Ek, Lattice Walk Enumeration, 29 March, 2018,
https://arxiv.org/abs/1803.10920.

[EkhZ] Shalosh B. Ekhad and Doron Zeilberger, The Method(!) of “Guess and
Check”, The Personal journal of Shalosh B. Ekhad and Doron Zeilberger, Feb.
15, 2015.
https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/gac.html .

[KP] Manuel Kauers and Peter Paule, “The Concrete Tetrahedron, Springer, 2011.

[MSV] R. Merlini, R. Sprugnoli, and M.C. Verri, The area determined by under-
diagonal paths, Proc. CAAP, vol. 1059, Lecture Notes in Computer Science,
1996, 59-71.

[Sl] Neil A. J. Sloane, The On-Line Encyclopedia of Integer Sequences® (OEIS),
https://oeis.org/.

[SRW] L.W. Shapiro, D. Rogers, and W. -J. Woan, The Catalan numbers, the
Lebesgue integral, and $4^{n-2}$, Amer. Math. Monthly 104 (1997). 926-931.

[TZ] Thotsaporn Aek Thanatipanonda and Doron Zeilberger, A Multi-Computational
Exploration of Some Games of Pure Chance, J. of Symbolic Computation
104(2021), 38-68.
https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/chance.html

[Wo] W.-J. Woan, Area of Catalan Paths, Discrete Math. 226 (2001), 439-444.

AJ Bu and Doron Zeilberger, Department of Mathematics, Rutgers University (New
Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ
08854-8019, USA. Email: ab1854 at math dot rutgers dot edu , DoronZeil at
gmail dot com .

Written: May 15, 2023.


# Computer Aided Diagnosis and Out-of-Distribution Detection in Glaucoma
Screening Using Color Fundus Photography

Satoshi Kondo  Muroran Institute of Technology
Hokkaido, Japan
<EMAIL_ADDRESS>Satoshi Kasai  Niigata University of Healthcare
and Welfare
Niigata, Japan
<EMAIL_ADDRESS>Kosuke Hirasawa  Konica Minolta, Inc.
Osaka, Japan
<EMAIL_ADDRESS>
###### Abstract

Artificial Intelligence for RObust Glaucoma Screening (AIROGS) Challenge is
held for developing solutions for glaucoma screening from color fundus
photography that are robust to real-world scenarios. This report describes our
method submitted to the AIROGS challenge. Our method employs convolutional
neural networks to classify input images to ”referable glaucoma” or ”no
referable glaucoma”. In addition, we introduce an inference-time out-of-
distribution (OOD) detection method to identify ungradable images. Our OOD
detection is based on an energy-based method combined with activation
rectification.

###### Index Terms:

Color fundus photography, Glaucoma screening, Computer aided diagnosis, Out-
of-distribution detection, Deep neural networks

##  I Introduction

Early detection of glaucoma can avoid visual impairment, which could be
facilitated through screening. Artificial intelligence (AI) could increase the
cost-effectiveness of glaucoma screening, by reducing the need for manual
labor. AI approaches for glaucoma detection from color fundus photography
(CFP) have been proposed and promising at-the-lab performances have been
reported. However, large performance drops often occur when AI solutions are
applied in real-world settings. Unexpected out-of-distribution data and bad
quality images are major causes for this performance drop.

Artificial Intelligence for RObust Glaucoma Screening (AIROGS) Challenge [1]
is held to develop solutions for glaucoma screening from CFP that are robust
to real-world scenarios.

This report describes our method submitted to the AIROGS challenge. Our method
employs convolutional neural networks to classify input images to ”referable
glaucoma” or ”no referable glaucoma”. In addition, we introduce an inference-
time out-of-distribution (OOD) detection method to identify ungradable images.
Our OOD detection is based on an energy-based method combined with activation
rectification.

##  II Overview of AIROGS Challenge

In this challenge, the Rotterdam EyePACS AIROGS dataset is used [2]. This
dataset contains 113,893 color fundus images from 60,357 subjects and
approximately 500 different sites with a heterogeneous ethnicity. All images
is assigned by human experts with the labels of referable glaucoma, no
referable glaucoma, or ungradable.

The training set provided by the organizers only consists of gradable images
and ungradable images are excluded. In the test set, however, both gradable
and ungradable images are included. Hence, the ungradable images cannot be
used in the training phase.

For each input image, the following four outputs are expected; a likelihood
score for referable glaucoma, a binary decision on referable glaucoma
presence, a binary decision on whether an image is ungradable, and a scalar
value that is positively correlated with the likelihood for ungradability.

##  III Proposed Method

###  III-A Overview

Our method employs convolutional neural networks to classify input images to
”referable glaucoma” or ”no referable glaucoma”. In addition, we introduce an
inference-time OOD detection method to identify ungradable images. Our OOD
detection is based on an energy-based method combined with activation
rectification. We will explain the details of the proposed method in the
following sections.

###  III-B Classification

We employ ResNet-RS [3] for the classifying color fundus images to ”referable
glaucoma” or ”no referable glaucoma”. Since it is two class classification, a
single linear layer with two channel output is attached at the end of the
network instead of the final linear layer of ResNet-RS.

###  III-C Out-of-distribution Detection

Our inference-time OOD detection is based on an energy-based method [4]
combined with activation rectification [5]. The energy-based method uses a
scoring function based on energy, instead of softmax, to discriminate in-
distribution (ID) and OOD data. In the activation rectification, the outsized
activation of a few layers can be attenuated by rectifying the activations at
an upper limit. After rectification, the output distributions for ID and OOD
data become much more well-separated. It is based on the observation that the
mean activation for ID data is well-behaved with a near-constant mean and
standard deviation, and the mean activation for OOD data has significantly
larger variations across units and is biased towards having sharp positive
values.

We consider a pre-trained neural network parameterized by $\theta$, which
encodes an input $\mathrm{x}$ to a feature vector. We denote the feature
vector from the penultimate layer of the network by
$h(\mathrm{x})\in\mathbb{R}^{m}$. The activation rectification operation is
applied to the feature vector as:

$\bar{h}(\mathrm{x})=\min(h(\mathrm{x}),c),$

where the operation $\min$ is applied element-wise and $c$ is the activation
threshold. The model output after the activation rectification is given by:

$\bar{f}(\mathrm{x};\theta)=\mathbf{W}^{T}\bar{h}(\mathrm{x})+\mathbf{b},$

where $\mathbf{W}$ and $\mathbf{b}$ are the weight matrix and the bias vector
of the last layer of the network. The energy of the model output is given by:

$E(\mathrm{x};\bar{f})=-T\cdot\log\sum_{i}^{K}e^{\bar{f}_{i}(\mathrm{x};\theta)/T},$

where $T$ is a temperature parameter and $\bar{f}_{i}(\mathrm{x};\theta)$
indicates the logit corresponding to the $i$-th class label.

The OOD scoring function is given by:

$g(\mathrm{x};\tau,\bar{f})=\begin{cases}\text{ID}&\text{if
$-E(x;\bar{f})\geq\tau$,}\\\ \text{OOD}&\text{if
$-E(x;\bar{f})<\tau$,}\end{cases}$

where $\tau$ is the energy threshold. And we define the scalar value that is
positively correlated with the likelihood for ungradability as
$\tau+E(x;\bar{f})$.

###  III-D Model Ensemble

We use multiple models as described in the next section. Each model is trained
independently and the inference results are obtained by ensemble of the
outputs from the models. The final likelihood score for referable glaucoma is
obtained by averaging the likelihood scores (softmax) from the models. The
binary decision on referable glaucoma presence is obtained by thresholding the
final likelihood score. The final binary decision on whether the image is
ungradable is obtained by majority voting of the models. And the final scalar
value that is positively correlated with the likelihood for ungradability is
obtained by averaging the scalar values from the models.

###  III-E Training Procedure

We use 200-layer ResNet-RS pretrained with the ImageNet dataset [6] for our
base network.

As for the preprocessing, the images are cropped and resized to 256 $\times$
256 pixels and then augmented. We use shift (maximum shift size is 10 % of the
image size), scaling (0.9 – 1.1 times), rotation (-5 – +5 degrees), color
jitter (0.8 – 1.2 times for brightness, contrast, saturation and hue) and
Gaussian blur (the max value of the sigma is 1.0) for the augmentation. The
images are then normalized.

We use the cross entropy loss as the loss function. Since the dataset is
imbalanced (there are much more ”no referable glaucoma” samples than
”referable glaucoma” samples), the weights are given depending on the inverse
of the frequencies in the training dataset.

The whole dataset includes 101,442 images. We divide the dataset into five
folds. Five models are trained by using different combinations of the folds.
Four folds are used for training and the remaining one fold is used for
validation. About 80,000 and 20,000 images are used in training and validation
for each model, respectively.

The optimizer is Adam [7] and the learning rate changes with cosine annealing.
The initial learning rate is 1e-3. The number of epoch is 90. The model with
the highest value in F1 score for the validation dataset is selected as the
final model.

The thresholds $c$ and $\tau$ are decided by using the validation dataset for
each model. For the activation threshold $c$, 90-th percentile of activations
estimated on the validation dataset is used. For the energy threshold $\tau$,
95-th percentile of energies estimated on the validation dataset is used. We
use the temperature parameter $T=1$ .

##  IV Experimental Results

The organizers of the AIROGS challenge prepare the preliminary test site to
evaluate the performance. The screening performance is evaluated using the
partial area under the receiver operator characteristic curve (90 – 100 %
specificity) for referable glaucoma and sensitivity at 95 % specificity. The
agreement between the reference and the prediction on image gradability is
calculated by using Cohen’s kappa score. Furthermore, the area under the
receiver operator characteristic curve is determined using the human reference
for ungradability as the true labels and the ungradability scalar values
provided by the predictions as the target scores.

The results of the preliminary test of our proposed method were that the
screening sensitivity was 0.787, the screening partial AUC was 0.857, the
ungradability kappa was 0.359, and the ungradability AUC was 0.863,

## References

  * [1] [Online]. Available: https://airogs.grand-challenge.org/
  * [2] “Rotterdam eyepacs airogs train set.” [Online]. Available: https://doi.org/10.5281/zenodo.5745363
  * [3] I. Bello, W. Fedus, X. Du, E. D. Cubuk, A. Srinivas, T.-Y. Lin, J. Shlens, and B. Zoph, “Revisiting resnets: Improved training and scaling strategies,” _Advances in Neural Information Processing Systems_ , vol. 34, 2021.
  * [4] W. Liu, X. Wang, J. Owens, and Y. Li, “Energy-based out-of-distribution detection,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 21 464–21 475, 2020.
  * [5] Y. Sun, C. Guo, and Y. Li, “React: Out-of-distribution detection with rectified activations,” _Advances in Neural Information Processing Systems_ , vol. 34, 2021.
  * [6] O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein _et al._ , “Imagenet large scale visual recognition challenge,” _International journal of computer vision_ , vol. 115, no. 3, pp. 211–252, 2015.
  * [7] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” in _Proc. of the 3rd International Conference for Learning Representations (ICLR)_ , 2015.


# Local automorphisms of $p$-filiform Leibniz algebras

Bakhtiyor Yusupov1,2 1 V.I.Romanovskiy Institute of Mathematics
Uzbekistan Academy of Sciences, 9
Univesity street, 100174
Tashkent, Uzbekistan  2 Department of Physics and Mathematics, Urgench State
University, H. Alimdjan street, 14, Urgench 220100, Uzbekistan
<EMAIL_ADDRESS>
###### Abstract.

This paper is devoted to study local automorphisms of $p$-filiform Leibniz
algebras. We prove that $p$-filiform Leibniz algebras as a rule admit local
automorphisms which are not automorphisms.

Keywords: Leibniz algebra, $p$-filiform Leibniz algebras, automorphism, local
automorphism.

AMS Subject Classification: 17A36, 17B20, 17B40.

##  1\. Introduction

In recent years non-associative analogues of classical constructions become of
interest in connection with their applications in many branches of mathematics
and physics. The notions of local and $2$-local derivations (automorphisms)
are also popular for some non-associative algebras such as the Lie and Leibniz
algebras.

R.Kadison [18] introduced the concept of a local derivation and proved that
each continuous local derivation from a von Neumann algebra into its dual
Banach bemodule is a derivation. B. Jonson [17] extended the above result by
proving that every local derivation from a C*-algebra into its Banach bimodule
is a derivation. In particular, Johnson gave an automatic continuity result by
proving that local derivations of a C*-algebra $A$ into a Banach $A$-bimodule
$X$ are continuous even if not assumed a priori to be so (cf. [17, Theorem
7.5]). Based on these results, many authors have studied local derivations on
operator algebras.

A similar notion, which characterizes non-linear generalizations of
automorphisms, was introduced by P.Šemrl in [22] as $2$-local automorphisms.
He described such maps on the algebra $B(H)$ of all bounded linear operators
on an infinite dimensional separable Hilbert space $H$. After P.Šemrl’s work,
numerous new results related to the description of local and $2$-local
derivation of some varieties have been appeared (see, for example, [9, 23,
14]).

The first results concerning to local and 2-local derivations and
automorphisms on finite-dimensional Lie algebras over algebraically closed
field of zero characteristic were obtained in [7, 10]. Namely, in [10] it is
proved that every 2-local derivation on a semi-simple Lie algebra
$\mathcal{L}$ is a derivation and that each finite-dimensional nilpotent Lie
algebra with dimension larger than two admits 2-local derivation which is not
a derivation. In [7] the authors have proved that every local derivation on
semi-simple Lie algebras is a derivation and gave examples of nilpotent
finite-dimensional Lie algebras with local derivations which are not
derivations. Sh.Ayupov, K.Kudaybergenov, B.Omirov proved similar results
concerning local and 2-local derivations and automorphisms on simple Leibniz
algebras in their recent paper [9]. Local automorphisms of certain finite-
dimensional simple Lie and Leibniz algebras are investigated in [8].
Concerning local automorphism, T.Becker, J.Escobar, C.Salas and R.Turdibaev in
[13] established that the set of local automorphisms $LAut(sl_{2})$ coincides
with the group $Aut^{\pm}(sl_{2})$ of all automorphisms and anti-
automorphisms. Later in [15] M.Costantini proved that a linear map on a simple
Lie algebra is a local automorphism if and only if it is either an
automorphism or an anti-automorphism. Similar results concerning local and
2-local derivations and automorphisms on Lie superalgebras were obtained in
[14, 23] and [24]. In [12] local derivations of solvable Leibniz algebras are
investigated and it is shown that in the class of solvable Leibniz algebras
there exist algebras which admit local derivations which are not derivation
and also algebras for which every local derivation is a derivation. Moreover,
it is proved that every local derivation on a finite-dimensional solvable
Leibniz algebras with model nilradical and maximal dimension of complementary
space is a derivation. The results of the paper [11] show that p-filiform
Leibniz algebras as a rule admit local derivations which are not derivations.
The authors proved similar results concerning local automorphism on the
solvable Leibniz algebras with null-filiform and naturally graded non-Lie
filiform nilradicals, whose dimension of complementary space is maximal is an
automorphism[5]. J.Adashev and B.Yusupov proved similar results concerning
local derivations of naturally graded quasi-filiform Leibniz algebras in their
recent paper [2]. J.Adashev and B.Yusupov proved proved that direct sum null-
filiform nilpotent Leibniz algebras as a rule admit local derivations which
are not derivations [3]. J.Adashev and B.Yusupov proved that quasi-filiform
Leibniz algebras of type I, as a rule, admit local automorphisms which are not
automorphisms [4]. The first example of a simple (ternary) algebra with
nontrivial local derivations is constructed by B.Ferreira, I.Kaygorodov and
K.Kudaybergenov in [16]. After that, in [6] Sh.Ayupov, A.Elduque and
K.Kudaybergenov constructed an example for a simple (binary) algebra with non-
trivial local derivations.

In the paper [20], I.A.Karimjanov, S.M.Umrzaqov, and B.B.Yusupov describe
automorphisms, local and 2-local automorphisms of solvable Leibniz algebras
with a model or abelian null-radicals. They show that any local automorphisms
on solvable Leibniz algebras with a model nilradical, the dimension of the
complementary space of which is maximal, is an automorphism. But solvable
Leibniz algebras with an abelian nilradical with a $1$-dimensional
complementary space admit local automorphisms which are not automorphisms.

In the present paper we study automorphisms and local automorphisms
$p$-filiform Leibniz algebras. In Section 3 we describe the automorphisms
$p$-filiform Leibniz algebras. In Section 4 we describe the local
automorphisms $p$-filiform Leibniz algebras. We show that in section 4 we
describe $p$-filiform Leibniz algebras as a rule admit local automorphisms
which are not automorphisms.

##  2\. Preliminaries

In this section we give some necessary definitions and preliminary results.

######  Definition 2.1.

A vector space with bilinear bracket $(\mathcal{L},[\cdot,\cdot])$ is called a
Leibniz algebra if for any $x,y,z\in\mathcal{L}$ the so-called Leibniz
identity

$\big{[}x,[y,z]\big{]}=\big{[}[x,y],z\big{]}-\big{[}[x,z],y\big{]},$

holds.

Let $\mathcal{L}$ be a Leibniz algebra. For a Leibniz algebra $\mathcal{L}$
consider the following central lower and derived sequences:

$\mathcal{L}^{1}=\mathcal{L},\quad\mathcal{L}^{k+1}=[\mathcal{L}^{k},\mathcal{L}^{1}],\quad
k\geq 1,$
$\mathcal{L}^{[1]}=\mathcal{L},\quad\mathcal{L}^{[s+1]}=[\mathcal{L}^{[s]},\mathcal{L}^{[s]}],\quad
s\geq 1.$

######  Definition 2.2.

A Leibniz algebra $\mathcal{L}$ is called nilpotent (respectively, solvable),
if there exists $p\in\mathbb{N}$ $(q\in\mathbb{N})$ such that
$\mathcal{L}^{p}=0$ (respectively, $\mathcal{L}^{[q]}=0$).The minimal number
$p$ (respectively, $q$) with such property is said to be the index of
nilpotency (respectively, of solvability) of the algebra $\mathcal{L}$.

Now let us define a naturally graduation for a nilpotent Leibniz algebra.

######  Definition 2.3.

Given a nilpotent Leibniz algebra $\mathcal{L}$, put
$\mathcal{L}_{i}=\mathcal{L}^{i}/\mathcal{L}^{i+1},\ 1\leq i\leq n-1$, and
$gr(\mathcal{L})=\mathcal{L}_{1}\oplus\mathcal{L}_{2}\oplus\dots\oplus\mathcal{L}_{n-1}$.
Then $[\mathcal{L}_{i},\mathcal{L}_{j}]\subseteq\mathcal{L}_{i+j}$ and we
obtain the graded algebra $gr(\mathcal{L})$. If $gr(\mathcal{L})$ and $L$ are
isomorphic, then we say that an algebra $\mathcal{L}$ is naturally graded.

Now we define the notion of characteristic sequence, which is one of the
important invariants. For a finite-dimensional nilpotent Leibniz algebra $N$
and for the matrix of the linear operator $R_{x}$ denote by $C(x)$ the
descending sequence of its Jordan blocks’ dimensions. Consider the
lexicographical order on the set $C(N)=\\{C(x)\ |\ x\in N\\}$.

######  Definition 2.4.

The sequence

$\left(\max\limits_{x\in N\setminus N^{2}}C(x)\right)$

is said to be the characteristic sequence of the nilpotent Leibniz algebra
$N.$

######  Definition 2.5.

A Leibniz algebra $\mathcal{L}$ is called $p$-filiform, if the characteristic
sequence is $C(\mathcal{L})=(n-p,\underbrace{1,\dots,1}_{p}).$

Now we give the definitions of automorphisms and local automorphisms.

######  Definition 2.6.

A linear bijective map $\varphi:\mathcal{L}\rightarrow\mathcal{L}$ is called
an automorphism, if it satisfies $\varphi([x,y])=[\varphi(x),\varphi(y)]$ for
all $x,y\in\mathcal{L}.$

######  Definition 2.7.

Let $\mathcal{L}$ be an algebra. A linear map
$\Delta:\mathcal{L}\to\mathcal{L}$ is called a local automorphism, if for any
element $x\in\mathcal{L}$ there exists an automorphism
$\varphi_{x}:\mathcal{L}\to\mathcal{L}$ such that $\Delta(x)=\varphi_{x}(x)$.

It was proved in [1, Theorem 2.9] that any naturally graded indecomposable
non-Lie $p$-filiform Leibniz algebra, is isomorphic to one of the following
pairwise non-isomorphic algebras $(n-p\geq 4)$:

if $p=2k$, then

$\displaystyle\mu_{1}:$
$\displaystyle\left\\{\begin{array}[]{ll}[e_{i},e_{1}]=e_{i+1},&1\leq i\leq
n-2k-1,\\\\[2.84526pt] [e_{1},f_{j}]=f_{k+j},&1\leq j\leq k,\\\\[2.84526pt]
\end{array}\right.$ $\displaystyle\mu_{2}:$
$\displaystyle\left\\{\begin{array}[]{ll}[e_{i},e_{1}]=e_{i+1},&1\leq i\leq
n-2k-1,\\\\[2.84526pt] [e_{1},f_{1}]=e_{2}+f_{k+1},&\\\\[2.84526pt]
[e_{i},f_{1}]=e_{i+1},&2\leq i\leq n-2k-1,\\\\[2.84526pt]
[e_{1},f_{j}]=f_{k+j},&2\leq j\leq k,\\\\[2.84526pt] \end{array}\right.$

if $p=2k+1$, then

$\displaystyle\mu_{3}:$
$\displaystyle\left\\{\begin{array}[]{ll}[e_{1},e_{1}]=e_{3},&\\\\[2.84526pt]
[e_{i},e_{1}]=e_{i+1},&2\leq i\leq n-2k-1,\\\\[2.84526pt]
[e_{1},f_{j}]=f_{k+j},&1\leq j\leq k,\\\\[2.84526pt]
[e_{2},f_{j}]=f_{k+j},&1\leq j\leq k,\\\\[2.84526pt] \end{array}\right.$

where $\\{e_{1},e_{2},\dots,e_{n-p},f_{1},f_{2},\dots,f_{p}\\}$ is the basis
of the algebra and the omitted products are equal to zero.

##  3\. Automorphisms of naturally graded non-Lie $p$-filiform Leibniz
algebras

In order to start the description we need to know the automorphisms of
naturally graded non-Lie $p$-filiform Leibniz algebras.

######  Proposition 3.1.

Any automorphisms of the algebra $\mu_{1}$ has the following matrix form:

$\displaystyle\Phi$
$\displaystyle=\begin{pmatrix}\varphi_{1,1}&\varphi_{1,2}\\\
\varphi_{2,1}&\varphi_{2,2}\end{pmatrix},$

where

$\varphi_{1,1}=\sum_{i=1}^{n-2k}a_{1}^{i}e_{i,i}+\sum_{i=1}^{n-2k-1}a_{1}^{i-1}\sum_{j=i+1}^{n-2k}a_{j-i+1}e_{j,i},$
$\varphi_{2,1}=\sum_{i=1}^{2k}b_{i}e_{i,1}+a_{1}\sum_{i=1}^{k}b_{i}e_{k+i,2},\quad\varphi_{1,2}=\sum_{i=1}^{k}c_{i}e_{n-2k,i},$

$\varphi_{2,2}=\begin{pmatrix}\varphi_{2,2}^{(1)}&0\\\
\varphi_{2,2}^{(2)}&a_{1}\varphi_{2,2}^{(1)}\end{pmatrix},$

$\varphi_{1,1}\in M_{n-2k,n-2k},\ \varphi_{2,1}\in M_{2k,n-2k},\
\varphi_{1,2}\in M_{n-2k,2k},\ \varphi_{2,2}^{(1)},\varphi_{2,2}^{(2)}.$

Let $\\{e_{i,j}:1\leq i,j\leq n\\}$ – be the system of matrix units, i.e., the
$(n\times n)$-matrix $e_{i,j}$ is such that the $(i,j)$th component is equal
to 1 and all other components are zeros.

###### Proof.

Let $\\{e_{1},f_{1},f_{2},\dots,f_{k}\\}$ be a generator basis elements of the
algebra $\mu_{1}$.

We put

$\varphi(e_{1})=\sum\limits_{i=1}^{n-2k}a_{i}e_{i}+\sum\limits_{i=1}^{2k}b_{i}f_{i},\qquad\varphi(f_{i})=\sum\limits_{j=1}^{n-2k}c_{j,i}e_{j}+\sum\limits_{j=1}^{2k}d_{j,i}f_{j},\quad
1\leq i\leq k.$

From the automorphisms property (2.6) we have

$\begin{split}\varphi(e_{2})&=\varphi([e_{1},e_{1}])=[\varphi(e_{1}),\varphi(e_{1})]=\left[\sum\limits_{i=1}^{n-2k}a_{i}e_{i}+\sum\limits_{i=1}^{2k}b_{i}f_{i},\sum\limits_{i=1}^{n-2k}a_{i}e_{i}+\sum\limits_{i=1}^{2k}b_{i}f_{i}\right]=\\\
&=a_{1}\sum\limits_{i=2}^{n-2k}a_{i-1}e_{i}+a_{1}\sum\limits_{i=1}^{k}b_{i}f_{k+i}.\end{split}$

Buy applying the induction and the automorphisms property (2.6) we derive

$\varphi(e_{i})=a_{1}^{i-1}\sum\limits_{t=i}^{n-2k}a_{t-i+1}e_{t},\quad 3\leq
i\leq n-2k.$

Consider

$\begin{split}0&=\varphi([f_{i},e_{1}])=[\varphi(f_{i}),\varphi(e_{1})]=\left[\sum\limits_{j=1}^{n-2k}c_{j,i}e_{j}+\sum\limits_{j=1}^{2k}d_{j,i}f_{j},\sum\limits_{j=1}^{n-2k}a_{j}e_{j}+\sum\limits_{j=1}^{2k}b_{j}f_{j}\right]=\\\
&=a_{1}\sum\limits_{j=1}^{n-2k-1}c_{j,i}e_{j+1}+c_{1,i}\sum\limits_{j=1}^{k}b_{j}f_{j},\quad
1\leq i\leq k.\end{split}$

Consequently,

$a_{1}\neq 0,\ c_{j,i}=0,\quad 1\leq i\leq k,\quad 1\leq j\leq n-2k-1.$

Similarly, from $\varphi(f_{k+i})=\varphi([e_{1},f_{i}]),\ 1\leq i\leq k$, we
deduce

$\varphi(f_{k+i})=a_{1}\sum\limits_{j=1}^{k}d_{j,i}f_{k+j},\qquad 1\leq i\leq
k.$

∎

######  Proposition 3.2.

Any automorphisms of the algebra $\mu_{2}$ has the following matrix form:

$\displaystyle\Phi$
$\displaystyle=\begin{pmatrix}\varphi_{1,1}&\varphi_{1,2}\\\
\varphi_{2,1}&\varphi_{2,2}\end{pmatrix},$

where

$\varphi_{1,1}=\sum_{i=1}^{n-2k}(a_{1}+b_{1})^{i-1}a_{1}e_{i,i}+\sum_{i=1}^{n-2k-1}\sum_{j=i+1}^{n-2k}(a_{1}+b_{1})^{i-1}a_{j-i+1}e_{j,i},$
$\varphi_{2,1}=\sum_{i=1}^{2k}b_{i}e_{i,1}+a_{1}\sum_{i=1}^{k}b_{i}e_{k+i,2},\quad
D_{1,2}=\sum_{i=1}^{k}c_{i}e_{n-2k,i},$
$\varphi_{2,2}=\begin{pmatrix}\varphi_{2,2}^{(1)}&0\\\
\varphi_{2,2}^{(2)}&\varphi_{2,2}^{(3)}\end{pmatrix},$
$\varphi_{2,2}^{(1)}=\sum_{i=1}^{k}\sum_{j=2}^{k}d_{j,i}e_{j,i}+(a_{1}+b_{1})e_{1,1},\quad\varphi_{2,2}^{(3)}=a_{1}\varphi_{2,2}^{(1)}-a_{1}\sum_{j=1}^{k}b_{j}e_{j,1},$
$\varphi_{1,1}\in M_{n-2k,n-2k},\ \varphi_{2,1}\in M_{2k,n-2k},\
\varphi_{1,2}\in M_{n-2k,2k},\
\varphi_{2,2}^{(1)},\varphi_{2,2}^{(2)},\varphi_{2,2}^{(3)},\mathbb{E}\in
M_{k,k}.$

Let $\\{e_{i,j}:1\leq i,j\leq n\\}$ – be the system of matrix units, i.e., the
$(n\times n)$-matrix $e_{i,j}$ is such that the $(i,j)$th component is equal
to 1 and all other components are zeros.

###### Proof.

The proof follows by straightforward calculations similarly to the proof of
Proposition 3.1.

∎

######  Proposition 3.3.

Any automorphisms of the algebra $\mu_{3}$ has the following matrix form:

$\displaystyle\Phi$
$\displaystyle=\begin{pmatrix}\varphi_{1,1}&\varphi_{1,2}\\\
\varphi_{2,1}&\varphi_{2,2}\end{pmatrix},$

where

$\displaystyle\varphi_{1,1}=$ $\displaystyle
a_{1}e_{1,1}+\sum_{i=2}^{n-2k}a_{1}^{i-2}(a_{1}+a_{2})e_{i,i}+\sum_{i=2}^{n-2k}a_{i}e_{i,1}+\sum_{i=3}^{n-2k-1}a_{i}e_{i,2}+$
$\displaystyle+\beta
e_{n-2k,2}+\sum_{i=3}^{n-2k-1}\sum_{j=i+1}^{n-2k}a_{1}^{j-3}a_{j-i+2}e_{j,i},$
$\displaystyle\varphi_{2,1}=$
$\displaystyle\sum_{i=1}^{2k}b_{i,1}e_{i,1}+\sum_{i=1}^{k}b_{i,2}e_{k+i,2}+(a_{1}+a_{2})\sum_{i=1}^{k}b_{i,1}e_{k+i,3},\quad\varphi_{1,2}=\sum_{i=1}^{k}c_{i}e_{n-2k,i},$
$\displaystyle\varphi_{2,2}=$
$\displaystyle\begin{pmatrix}\varphi_{2,2}^{(1)}&0\\\
\varphi_{2,2}^{(2)}&(a_{1}+a_{2})\varphi_{2,2}^{(1)}\end{pmatrix}$
$\varphi_{1,1}\in M_{n-2k,n-2k},\ \varphi_{2,1}\in M_{2k,n-2k},\
\varphi_{1,2}\in M_{n-2k,2k},\ \varphi_{2,2}^{(1)},\varphi_{2,2}^{(2)}\in
M_{k,k}.$

Let $\\{e_{i,j}:1\leq i,j\leq n\\}$ – be the system of matrix units, i.e., the
$(n\times n)$-matrix $e_{i,j}$ is such that the $(i,j)$th component is equal
to 1 and all other components are zeros.

###### Proof.

The proof follows by straightforward calculations similarly to the proof of
Proposition 3.1.

∎

######  Remark 3.4.

The dimensions of the space of automorphisms of the algebras $\mu_{1},\mu_{2}$
and $\mu_{3}$ are

$\displaystyle\dim Aut(\mu_{1})=$ $\displaystyle n+2k^{2}+k,$
$\displaystyle\dim Aut(\mu_{2})=$ $\displaystyle n+2k^{2}+1,$
$\displaystyle\dim Aut(\mu_{3})=$ $\displaystyle n+2k^{2}+2k+1,$

where $k\in\mathbb{N}$ and $n\geq 2k+4.$

##  4\. Local automorphisms of naturally graded non-Lie $p$-filiform Leibniz
algebras

In the following theorem we give the description of local automorphisms of the
algebra $\mu_{1}$.

######  Theorem 4.1.

Let $\Delta$ be a linear operator on $\mu_{1}$. Then $\Delta$ is a local
automorphisms, if and only if its matrix has the form:

$\Delta=\left(\begin{array}[]{cc}\Delta_{1,1}&\Delta_{1,2}\\\
\Delta_{2,1}&\Delta_{2,2}\end{array}\right),$ (4)

where

$\Delta_{1,1}=\sum\limits_{j=1}^{n-2k}\sum\limits_{i=j}^{n-2k}\gamma_{i,j}e_{i,j},\quad\Delta_{2,1}=\sum\limits_{i=n-2k+1}^{n}\gamma_{i,1}e_{i,1}+\sum\limits_{i=n-k+1}^{n}\gamma_{i+1,2}e_{i+1,2},$
$\Delta_{1,2}=\sum\limits_{i=n-2k+1}^{n-k}\gamma_{n-2k,i}e_{n-2k,i},$
$\Delta_{2,2}=\begin{pmatrix}\Delta_{2,2}^{(1)}&0\\\
\Delta_{2,2}^{(2)}&\Delta_{2,2}^{(3)}\end{pmatrix},$
$\Delta_{2,2}^{(1)}=\sum\limits_{j=n-2k+1}^{n-k}\sum\limits_{j=n-2k+1}^{n-k}\gamma_{i,j}e_{i,j},\quad\Delta_{2,2}^{(2)}=\sum\limits_{j=n-2k+1}^{n-k}\sum\limits_{j=n-k+1}^{n}\gamma_{i,j}e_{i,j},$
$\Delta_{2,2}^{(3)}=\sum\limits_{j=n-k+1}^{n}\sum\limits_{j=n-k+1}^{n}\gamma_{i,j}e_{i,j}.$

###### Proof.

$(\Rightarrow)$ Assume that $\Delta$ is a local automorphisms of $\mu_{1}:$

$\displaystyle\Delta=\left(\begin{array}[]{cc}\Delta_{1,1}&\Delta_{1,2}\\\
\Delta_{2,1}&\Delta_{2,2}\end{array}\right),$

where

$\displaystyle\Delta_{1,1}=$
$\displaystyle\sum\limits_{j=1}^{n-2k}\sum\limits_{i=1}^{n-2k}\gamma_{i,j}e_{i,j},\quad\Delta_{2,1}=\sum\limits_{i=n-2k+1}^{n}\sum\limits_{j=1}^{n-2k}\gamma_{i,j}e_{i,j},$
$\displaystyle\Delta_{1,2}=$
$\displaystyle\sum\limits_{j=n-2k+1}^{n}\sum\limits_{i=1}^{n-2k}\gamma_{i,j}e_{i,j},\quad\Delta_{2,2}=\sum\limits_{j=n-2k+1}^{n}\sum\limits_{j=n-2k+1}^{n}\gamma_{i,j}e_{i,j}.$

Take a automorphism $\varphi_{e_{2}}$ such that
$\Delta(e_{2})=\varphi_{e_{2}}(e_{2})$. Then

$\displaystyle\Delta(e_{2})=$
$\displaystyle\sum_{j=1}^{n-2k}\gamma_{j,2}e_{2}+\sum_{j=n-2k+1}^{n}\gamma_{j,2}f_{j-n+2k},$
$\displaystyle\varphi_{e_{2}}(e_{2})=$ $\displaystyle
a_{1}\sum_{i=2}^{n-2k}a_{i-1}e_{i}+a_{1}\sum_{i=1}^{k}b_{i}f_{k+i}.$

Comparing the coefficients, we conclude that
$\gamma_{1,2}=\gamma_{n-2k+i,2}=0$ for $1\leq i\leq k$.

We take a automorphism $\varphi_{e_{i}}$ such that
$\Delta(e_{i})=\varphi_{e_{i}}(e_{i}),$ where $3\leq i\leq n-2k.$ Then

$\displaystyle\Delta(e_{i})=$
$\displaystyle\sum_{j=1}^{n-2k}\gamma_{j,i}e_{j}+\sum_{j=n-2k+1}^{n}\gamma_{j,i}f_{j-n+2k},$
$\displaystyle\varphi_{e_{i}}(e_{i})=$ $\displaystyle
a_{1}^{i-1}\sum_{j=i}^{n-2k}a_{j-i+1}e_{j}.$

Comparing the coefficients at the basis elements for $\Delta(e_{i})$ and
$\varphi_{e_{i}}(e_{i})$, we obtain the identities

$\gamma_{t,j}=\gamma_{n-2k+i,j}=0,\quad 3\leq j\leq n-2k,\ 1\leq i\leq 2k,\
1\leq t\leq n-2k-1.$

We take a automorphism $\varphi_{f_{i}}$ such that
$\Delta(f_{i})=\varphi_{f_{i}}(f_{i}),$ where $1\leq i\leq k$. Then

$\displaystyle\Delta(f_{i})=$
$\displaystyle\sum_{j=1}^{n-2k}\gamma_{j,n-2k+i}e_{j}+\sum_{j=n-2k+1}^{n}\gamma_{j,n-2k+i}f_{j-n+2k},$
$\displaystyle\varphi_{f_{i}}(f_{i})=$ $\displaystyle
c_{n-2k,i}e_{n-2k}+\sum_{j=1}^{2k}d_{j,i}f_{j}.$

Comparing the coefficients at the basis elements for $\Delta(f_{i})$ and
$\varphi_{f_{i}}(f_{i})$, we obtain

$\gamma_{j,i}=\gamma_{j,n-2k+i}=0,\quad 1\leq j\leq n-2k-1,\ 1\leq i\leq k-1.$

Now, take a automorphism $\varphi_{f_{i}}$ such that
$\Delta(f_{i})=\varphi_{f_{i}}(f_{i}),$ where $k+1\leq i\leq 2k$. Then

$\displaystyle\Delta(f_{i})=$
$\displaystyle\sum_{j=1}^{n-2k}\gamma_{j,n-2k+i}e_{j}+\sum_{j=n-2k+1}^{n}\gamma_{j,n-2k+i}f_{j-n+2k},$
$\displaystyle\varphi_{f_{i}}(f_{i})=$ $\displaystyle
a_{1}\sum_{j=1}^{k}d_{j,i-k}f_{k+j},$

which implies

$\gamma_{j,i}=0,\quad 1\leq j\leq n-k,\ n-k+1\leq i\leq n.$

$(\Leftarrow)$ Assume that the operator $\Delta$ has the form (4). For an
arbitrary element

$x=\sum\limits_{i=1}^{n-2k}\xi_{i}e_{i}+\sum\limits_{i=1}^{2k}\zeta_{i}f_{i},$

we have

$\displaystyle\varphi(x)_{e_{1}}=$ $\displaystyle a_{1}\xi_{1},$
$\displaystyle\varphi(x)_{e_{i}}=$ $\displaystyle
a_{i}\xi_{1}+\sum_{j=1}^{i-2}a^{j}_{1}a_{i-j}\xi_{j+1}+a_{1}^{i}\xi_{i},\ \ \
\ 2\leq i\leq n-2k-1,$ $\displaystyle\varphi(x)_{e_{n-2k}}=$ $\displaystyle
a_{n-2k}\xi_{1}+\sum_{j=1}^{n-2k-2}a_{n-2k-j}\xi_{j+1}+(n-2k)a_{1}\xi_{n-2k}+\sum_{j=1}^{k}c_{j,n-2k}\zeta_{j},$
$\displaystyle\varphi(x)_{f_{i}}=$ $\displaystyle
b_{i}\xi_{1}+\sum_{j=1}^{k}d_{j,i}\zeta_{j},\ \ \ \ \ \ 1\leq i\leq k,$
$\displaystyle\varphi(x)_{f_{i}}=$ $\displaystyle
b_{i}\xi_{1}+b_{i-k}\xi_{2}+\sum_{j=1}^{k}d_{j,i}\zeta_{j}+$
$\displaystyle+a_{1}\sum_{j=1}^{k}d_{j,i-k}\zeta_{k+j},\ \ k+1\leq i\leq 2k.$

The coordinates of $\Delta(x)$ are

$\displaystyle\Delta(x)_{e_{1}}=$ $\displaystyle\gamma_{11}\xi_{1},$
$\displaystyle\Delta(x)_{e_{i}}=$
$\displaystyle\sum_{j=1}^{i}\gamma_{i,j}\xi_{j},\ \ \ \ 2\leq i\leq{n-2k-1},$
$\displaystyle\Delta(x)_{e_{n-2k}}=$
$\displaystyle\sum_{j=1}^{n-2k}\gamma_{n-2k,j}\xi_{j}+\sum_{j=1}^{k}\gamma_{n-2k,n-2k+j}\zeta_{j},$
$\displaystyle\Delta(x)_{f_{i}}=$
$\displaystyle\gamma_{n-2k+i,1}\xi_{1}+\sum_{j=1}^{k}\gamma_{n-2k+i,n-2k+j}\zeta_{j},\
\ \ \ \ \ 1\leq i\leq k,$ $\displaystyle\Delta(x)_{f_{i}}=$
$\displaystyle\gamma_{n-2k+i,1}\xi_{1}+\gamma_{n-2k+i,2}\xi_{2}+\sum_{j=1}^{2k}\gamma_{n-2k+i,n-2k+j}\zeta_{j},\,\,k+1\leq
i\leq 2k.$

Comparing the coordinates of $\Delta(x)$ and $D(x),$ we obtain

${\small\left\\{\begin{array}[]{llllllllllll}a_{1}\xi_{1}&=\gamma_{11}\xi_{1}\\\
a_{i}\xi_{1}+\sum\limits_{j=1}^{i-2}a^{j}_{1}a_{i-j}\xi_{j+1}+a_{1}^{i}\xi_{i}&=\sum\limits_{j=1}^{i}\gamma_{i,j}\xi_{j},\,\,\,\,2\leq
i\leq{n-2k-1},\\\
a_{n-2k}\xi_{1}+\sum\limits_{j=1}^{n-2k-2}a_{n-2k-j}\xi_{j+1}+(n-2k)a_{1}\xi_{n-2k}+&\\\
+\sum\limits_{j=1}^{k}c_{j,n-2k}\zeta_{j}&=\sum\limits_{j=1}^{n-2k}\gamma_{n-2k,j}\xi_{j}+\sum\limits_{j=1}^{k}\gamma_{n-2k,n-2k+j}\zeta_{j},\\\
b_{i}\xi_{1}+\sum\limits_{j=1}^{k}d_{j,i}\zeta_{j}&=\gamma_{n-2k+i,1}\xi_{1}+\\\
&+\sum\limits_{j=1}^{k}\gamma_{n-2k+i,n-2k+j}\zeta_{j},\,\,\,1\leq i\leq k,\\\
b_{i}\xi_{1}+b_{i-k}\xi_{2}+\sum\limits_{j=1}^{k}d_{j,i}\zeta_{j}+&\\\
+a_{1}\sum\limits_{j=1}^{k}d_{j,i-k}\zeta_{k+j}&=\gamma_{n-2k+i,1}\xi_{1}+\gamma_{n-2k+i,2}\xi_{2}+\\\
&+\sum\limits_{j=1}^{2k}\gamma_{n-2k+i,n-2k+j}\zeta_{j},\,\,\,k+1\leq i\leq
2k.\end{array}\right.}$ (6)

We show the solvability of this system of equations with respect to
$a_{i},b_{i},c_{i}$ and $d_{i,j}.$ For this purpose we consider the following
possible cases.

Case 1. Let $\xi_{1}\neq 0$, then putting $c_{i}=d_{i,j}=0,\ 1\leq i\leq k,\
1\leq j\leq k$ from (6) we uniquely determine
$a_{1},a_{2},\ldots,a_{n-2k},b_{1},b_{2},\ldots,b_{2k}.$

Case 2. Let $\xi_{1}=0$ and $\xi_{2}\neq 0$, then putting $c_{i}=d_{i,j}=0,\
1\leq i\leq k,\ 1\leq j\leq k$ we uniquely determine remaining unknowns
$a_{1},a_{2},\ldots,a_{n-2k},b_{1},b_{2},\ldots,b_{k}$.

Case 3. Let $\xi_{1}=\xi_{2}=\dots=\xi_{r-1}=0$ and $\xi_{r}\neq 0,\ 3\leq
r\leq n-2k$. Then putting

$a_{2}=\ldots=a_{n-2k-m}=b_{1}=\ldots=c_{1}=\ldots=d_{t,j}=0,\ 1\leq t\leq k,\
1\leq j\leq k.$

we determine unknowns $a_{1},\ a_{n-2k-m+1},\ i\leq m\leq n-2k$.

Case 4. Let $\xi_{1}=\ldots=\xi_{n-2k}=\zeta_{1}=\ldots=\zeta_{r-1}=0$ and
$\zeta_{r}\neq 0,\ 1\leq r\leq k$. Then setting

$a_{2}=\ldots=b_{1}=\ldots=0,\ c_{i}=0,\,i\neq r,\ d_{j,i}=0,\ j\neq r,$

we determine $a_{1},\ c_{r},d_{r,i},\ 1\leq i\leq k$.

Case 5. Let $\xi_{1}=\ldots=\xi_{n-2k}=\zeta_{1}=\ldots=\zeta_{k+r-1}=0$ and
$\zeta_{k+r}\neq 0,\ 1\leq r\leq k$. Then setting

$a_{2}=\ldots=b_{1}=\ldots=c_{1}=\ldots=0,\ d_{j,i}=0,\ r\neq k+r,$

we obtain that the unknowns $a_{1},\ d_{k+r,i},k+1\leq i\leq 2k,$ are uniquely
determined from (6). ∎

In the following theorems we obtain the descriptions of local automorphism of
the algebras $\mu_{2}$ and $\mu_{3}$.

######  Theorem 4.2.

Let $\Delta$ be a linear operator on $\mu_{2}$. Then $\Delta$ is a local
automorphism if and only if its matrix has the form:

$\displaystyle\Delta=\left(\begin{array}[]{cc}\Delta_{1,1}&\Delta_{1,2}\\\
\Delta_{2,1}&\Delta_{2,2}\end{array}\right),$

where

$\Delta_{1,1}=\sum\limits_{j=1}^{n-2k}\sum\limits_{i=j}^{n-2k}\alpha_{j,i}e_{j,i},\quad\Delta_{2,1}=\sum\limits_{i=1}^{2k}\beta_{n-2k+i,1}e_{n-2k+i,1}+\sum\limits_{i=1}^{k}b_{n-2k+i,2}e_{n-2k+i,2},$
$\Delta_{1,2}=\sum_{i=1}^{k}\gamma_{n-2k,n-2k+i}e_{n-2k,n-2k+i},$
$\Delta_{2,2}=\begin{pmatrix}\Delta_{2,2}^{(1)}&0\\\
\Delta_{2,2}^{(2)}&\Delta_{2,2}^{(3)}\end{pmatrix},$
$\Delta_{2,2}^{(1)}=\delta_{n-2k+1,n-2k+1}e_{n-2k+1,n-2k+1}+\sum\limits_{i=n-2k+1}^{n-k}\sum\limits_{j=n-2k+2}^{n-k}\delta_{j,i}e_{j,i},$
$\Delta_{2,2}^{(2)}=\sum\limits_{i=n-k+1}^{n-k}\sum\limits_{j=n-k+1}^{n}\delta_{j,i}e_{j,i},$
$\Delta_{2,2}^{(3)}=\delta_{n-k+1,n-k+1}e_{n-k+1,n-k+1}+\sum\limits_{i=n-k+1}^{n}\sum\limits_{j=n-k+2}^{n}\delta_{j,i}e_{j,i}.$

###### Proof.

The proof is similar to the proof of Theorem 4.1 ∎

######  Theorem 4.3.

Let $\Delta$ be a linear operator on $\mu_{3}$. Then $\Delta$ is a local
automorphism if and only if its matrix has the form:

$\displaystyle\Delta=\left(\begin{array}[]{cc}\Delta_{1,1}&\Delta_{1,2}\\\
\Delta_{2,1}&\Delta_{2,2}\end{array}\right),$

where

$\Delta_{1,1}=\sum\limits_{j=1}^{n-2k}\sum\limits_{i=j}^{n-2k}\alpha_{j,i}e_{j,i},\quad\alpha_{i,1}=\alpha_{i,2},\
\alpha_{2,2}=\alpha_{1,1}+\alpha_{2,1},\ 3\leq i\leq n-2k-1$
$\Delta_{2,1}=\sum\limits_{i=1}^{2k}\beta_{n-2k+i,1}e_{n-2k+i,1}+\sum\limits_{i=1}^{k}b_{n-2k+i,2}e_{n-2k+i,2}+\sum\limits_{i=1}^{k}b_{n-2k+i,3}e_{n-2k+i,3},$
$\Delta_{1,2}=\sum_{i=1}^{k}\gamma_{n-2k,n-2k+i}e_{n-2k,n-2k+i},$
$\Delta_{2,2}=\begin{pmatrix}\Delta_{2,2}^{(1)}&0\\\
\Delta_{2,2}^{(2)}&\Delta_{2,2}^{(3)}\end{pmatrix},$
$\Delta_{2,2}^{(1)}=\sum\limits_{i=n-2k+1}^{n-k}\sum\limits_{j=n-2k+1}^{n-k}\delta_{j,i}e_{j,i},\quad\Delta_{2,2}^{(2)}=\sum\limits_{i=n-k+1}^{n-k}\sum\limits_{j=n-k+1}^{n}\delta_{j,i}e_{j,i},$
$\Delta_{2,2}^{(3)}=\sum\limits_{i=n-k+1}^{n}\sum\limits_{j=n-k+1}^{n}\delta_{j,i}e_{j,i}$

###### Proof.

The proof is similar to the proof of Theorem 4.1 ∎

######  Example 4.4.

Leibniz algebras $\mu_{1}$ (see Proposition 3.1), admit a local automorphisms
which is not a automorphisms.

###### Proof.

Let us consider the linear operator $\Phi$ on $\mathfrak{L}$, such that

$\Phi\left(x\right)=x+x_{2}e_{n-2k},\ \
x=\sum\limits_{i=1}^{n-2k}x_{i}e_{i}+\sum\limits_{i=1}^{2k}x_{i}f_{i}$

By Lemma 3.1, it is not difficult to see that $\Phi$ is not a automorphism. We
show that, $\Phi$ is a local automorphism on $\mu_{1}.$

Consider the automorphism $\varphi_{1}$ and $\varphi_{2}$ on the algebras
$\mu_{1},$ defined as:

$\begin{split}\varphi_{1}\left(x\right)&=x+x_{1}e_{n-2k-1}+x_{2}e_{n-2k},\\\
\varphi_{2}\left(x\right)&=x+\beta x_{1}e_{n-2k},\ \ \
x=\sum\limits_{i=1}^{n-2k}x_{i}e_{i}+\sum\limits_{i=1}^{2k}x_{i}f_{i}.\end{split}$

Now, for any
$x=\sum\limits_{i=1}^{n-2k}x_{i}e_{i}+\sum\limits_{i=1}^{2k}x_{i}f_{i},$ we
shall find a automorphism $\varphi,$ such that $\Phi(x)=\varphi(x).$

If $x_{1}=0,$ then

$\varphi_{1}(x)=x+x_{2}e_{n-2k}=\Phi(x).$

If $x_{1}\neq 0,$ then set $\beta=\frac{x_{2}}{x_{1}},$ we obtain that

$\begin{split}\varphi_{2}(x)=x+\beta
x_{1}e_{n}=x+\frac{x_{2}}{x_{1}}x_{1}e_{n-2k}=x+x_{2}e_{n-2k}=\Phi(x)\end{split}$

Hence, $\Phi$ is a local automorphism. ∎

######  Remark 4.5.

The dimensions of the space of local automorphism of algebras
$\mu_{1},\mu_{2}$ and $\mu_{3}$ are

$\displaystyle\dim LocDer(\mu_{1})=$
$\displaystyle\frac{n^{2}+10k^{2}-4kn+n+6k}{2},$ $\displaystyle\dim
LocDer(\mu_{2})=$ $\displaystyle\frac{n^{2}+10k^{2}-4kn+n+2k+4}{2},$
$\displaystyle\dim LocDer(\mu_{3})=$
$\displaystyle\frac{n^{2}+10k^{2}-4kn-n+12k+4}{2},$

where $k\in\mathbb{N}$ and $n\geq 2k+4.$

Remarks 3.4 and 4.5 show that the dimensions of the spaces of all local
automorphism of the algebras $\mu_{i},$ $i=1,2,3,$ are strictly greater than
the dimensions of the space of all automorphism of $\mu_{i}.$ Therefore, we
have the following result.

######  Corollary 4.6.

The algebras $\mu_{1},\mu_{2}$ and $\mu_{3}$ admit local automorphism which
are not automorphism.

## References

  * [1] Adashev J. Q., Ladra M., Omirov B. A. Solvable Leibniz Algebras with Naturally Graded Non-Lie $p$-Filiform Nilradicals // Communications in Algebra. 45(10)(2017), p.4329–4347.
  * [2] Adashev J. Q., Yusupov B. B. Local derivation of naturally graded quasi-filiform Leibniz algebras. Uzbek Mathematical Journal. 65:1 ( 2021), p. 28–41.
  * [3] Adashev J. Q., Yusupov B. B. Local derivations and automorphisms of direct sum null-filiform Leibniz algebras. Lobachevskii Journal of Mathematics. 43(12) (2022), p. 1–7.
  * [4] Adashev J. Q., Yusupov B. B. Local automorphisms of $n$-dimensional naturally graded quasi-filiform Leibniz algebra of type I. Algebraic structures and their applications. (2023), doi:10.22034/AS.2023.3040.
  * [5] Arzikulov F.N., Karimjanov I.A., Umrzaqov S.M., Local and 2-local automorphisms of some solvable Leibniz algebras. Journal of Geometry and Physics. Vol. 178, (2022). .
  * [6] Ayupov Sh. A., Elduque A., Kudaybergenov K. K. Local derivations and automorphisms of Cayley algebras. Journal of Pure and Applied Algebra. 227(5) (2022), p. 107277.
  * [7] Ayupov Sh. A., Kudaybergenov K. K. Local derivations on finite-dimensional Lie algebras. Linear Algebra and its Applications. 493 (2016), p. 381–398.
  * [8] Ayupov Sh. A., Kudaybergenov K. K. Local Automorphisms on Finite-Dimensional Lie and Leibniz Algebras, // Algebra, Complex Analysis and Pluripotential Theory, USUZCAMP 2017. Springer Proceedings in Mathematics and Statistics. 264 (2017), p. 31–44.
  * [9] Ayupov Sh.A., Kudaybergenov K.K., Omirov B.A. Local and $2$-local derivations and automorphisms on simple Leibniz algebras. Bulletin of the Malaysian Mathematical Sciences Society. 43(3), (2020), p. 2199–2234.
  * [10] Ayupov Sh. A., Kudaybergenov K. K., Rakhimov I. S. 2-Local derivations on finite-dimensional Lie algebras. Linear Algebra and its Applications. 474 (2015), p. 1–11.
  * [11] Ayupov Sh. A., Kudaybergenov K. K., Yusupov B. B. Local and 2-local derivations of p-filiform Leibniz algebras. Journal of Mathematical Sciences, 245(3), 2020, p. 359-367.
  * [12] Ayupov Sh. A., Khudoyberdiyev A. Kh., Yusupov B. B. Local and 2-local derivations of Solvable Leibniz algebras. International Journal of Algebra and Computation, 30 (6), (2020), p. 1185–1197.
  * [13] Becker T., Escobar J., Salas C., Turdibaev R. On Local Automorphisms of $sl_{2}$, // Uzbek Mathematical Journal. (2) (2019), p. 27–34.
  * [14] Chen H., Wang Y., Dalian. Local superderivation on Lie superalgebra $q(n)$ . Czechoslovak Mathematical Journal. 68 (143) (2018), p. 661–675.
  * [15] Costantini M., Local automorphisms of finite dimensional simple Lie algebras, // Linear Algebra and its Applications. 562 (2019), p. 123–134.
  * [16] Ferreira B., Kaygorodov I., Kudaybergenov K. Local and 2-local derivations of simple n-ary algebras. Ricerche di Matematica. (2021), DOI: 10.1007/s11587-021-00602-3.
  * [17] Johnson B. Local derivations on C*-algebras are derivations. Transactions of the American Mathematical Society. 353 (2001), p. 313–325.
  * [18] Kadison R. Local derivations. Journal of Algebra. 130 (1990), p. 494–509.
  * [19] Karimjanov I.A., Ladra M. Some classes of nilpotent associative algebras. Mediterr. J. Math. 17:70 (2020), p.1-21.
  * [20] Karimjanov I.A., Umrzaqov S.M., Yusupov B.B. Local and 2-local automorphisms of solvable Leibniz algebras with abelian and model nilradicals. Preprint, (2022).
  * [21] Masutova, K.K., Omirov, B.A. On some zero-filiform algebras. Ukrainian Math. J. 66 (2014), no. 4, p. 541–552.
  * [22] Šemrl P., Local automorphisms and derivations on $B(H)$. Proceedings of the American Mathematical Society. 125 (1997), p. 2677–2680.
  * [23] Wang Y., Chen H., Nan J. 2-Local superderivations on basic classical Lie superalgebras. Journal of Mathematical Research with Applications. 37 (2017), p. 527–534.
  * [24] Wang Y., Chen H., Nan J. 2-Local automorphisms on basic classical Lie superalgebras, // Acta Mathematica Sinica, English Series. 35(3) (2019), p. 427–437.