text:
\section{Proof of Theorem \ref{path}}
\label{sec:vertex}

In this section, our goal is to prove Theorem \ref{path}. The strategy is to first assume that $G$ is a minimum counter-example. In particular, we assume that there exist a minimum $t\ge 3$ and a $P_k$-free graph $G$ with minimum order $n=q(k-1)+r$  such that $k_t(G) \ge k_t(qK_{k-1}\cup K_r)$ and $G$ is not one of the extremal graphs described in Theorem \ref{path}. We further assume that the number of copies of $K_t$ in any other graph with the same number of vertices is at most $k_t(G)$. We start by proving some structural results about this minimum counter-example $G$ and lastly show that such examples cannot exist.

Note that if $n \le k-1$, it is easy to check that $G = K_n$ maximizes $k_t(G)$. Moreover, if $n \ge t$, then $K_n$ is the unique extremal graph. Also, if $n < t$, then any graph on $n$ vertices serve as an extremal graph, because no graph on $n$ vertices contain a copy of $K_t$. Thus, for the rest of this section, we may assume that $n \ge k$. We use the following simple fact proved in \cite{CC}.

\begin{lemma} [Lemma 2.3 in \cite{CC}] \label{easy:convex}
	Let $t$, $w$, $x$, $y$, and $z$ be non-negative integers such that $t \ge 2$, $x+w=y+z$, $x\ge y$, $x\ge z$, and $x\ge t$. Then, $\binom{x}{t}+\binom{w}{t} \ge \binom{y}{t}+\binom{z}{t}$. Moreover, the inequality is strict if $x> y$ and $x>z$.
\end{lemma}

\begin{lemma} \label{con}
If $G$ is a minimum counter-example, then $G$ is connected.
\end{lemma}

\begin{proof}
Suppose for the sake of contradiction that $G$ is not connected. First we show that $G$ does not contain a clique of order $k-1$. Suppose $G$ does contain one such clique, note that due to the $P_k$-free condition, the clique is disjoint from the rest of the graph. Then, by removing this clique, we obtain a graph $G'$ with $(q-1)(k-1)+r$ vertices with at least $(q-1)\binom{k-1}{t}+\binom{r}{t}$ number of $K_t$'s. Since $G'$ is not a counter-example, $G'$ has exactly the optimal number of $K_t$'s and thus is one of the extremal graphs. However, adding the clique back implies that $G$ is also one of the extremal graphs, a contradiction.

	Now, suppose that $G$ contains a proper subgraph $H$ that is a union of connected components of $G$ where $|V(H)| \ge k-1$. Since $H$ is not a counter-example to Theorem \ref{path}, either $H$ contains strictly less $K_t$'s than an extremal graph with the same number of vertices, or $H$ is an extremal graph. In the first case, replacing $H$ with one of the extremal graphs results in a graph that strictly increases the number of $K_t$'s in $G$ while maintaining the same number of vertices, creating a worse minimum counter-example, a contradiction. In the latter case, $H$ contains at least one copy of $K_{k-1}$, contradicting our previous claim. Thus, we may assume that all proper subgraphs that is a union of connected components of $G$ has strictly less than $k-1$ vertices.

	Let $G_1$ be a connected component of $G$ and $G_2=G\backslash G_1$. For $i =1,2$, let $r_i$ denote the number of vertices in $G_i$. By the previous claim, we know that both $r_1$ and $r_2$ are strictly less than $k-1$. Furthermore, as we have discussed in the beginning of this section, we can assume that the number of vertices in $G$ is at least $k$, i.e., $r_1 + r_2 \ge k$. Thus, from Lemma \ref{easy:convex}, by setting $x = k-1$, $y = r_1$, $z = r_2$ and $w = r_1 + r_2 - (k-1)$, we obtain the following: $$\binom{k-1}{t} + \binom{r_1+r_2-(k-1)}{t} > \binom{r_1}{t} + \binom{r_2}{t} \ge k_t(G).$$ Thus, $K_{k-1} \cup K_{r_1+r_2-(k-1)}$ is a $P_k$-free graph with the same number of vertices as $G$, but with strictly more copies of $K_t$, a contradiction.
\end{proof}

\begin{lemma} \label{mindeg}
	If $G$ is a minimum counter-example, then $G$ has minimum degree at least $\max(r, t-1)$.
\end{lemma}

\begin{proof}
	If $G$ is a counter-example containing a vertex $v$ with degree less than $t-1$, then, one can remove $v$ from $G$ to obtain a smaller counter-example $G \backslash v$, which contradicts our choice of $G$. Thus, the minimum degree of $G$ is at least $t-1$.

	To show that the minimum degree of $G$ is at least $r$, for the sake of contradiction, we assume that there exists a vertex $v$ with degree $\b < r$. We may trivially assume that $r>0$. Note that there are at most $\binom{\b}{t-1}$ copies of $K_t$ containing $v$. Consider $G\backslash v$, which is not a counter-example to Theorem \ref{path}. Since $\b < r$,
	\begin{align*}
		k_t(G\backslash v) &\le q\binom{k-1}{t}+\binom{r-1}{t}\\
		&= q\binom{k-1}{t}+\binom{r}{t}-\binom{r-1}{t-1}\\
		&\le k_t(G)-\binom{\b}{t-1} \le k_t(G\backslash v)
	\end{align*}

	Thus, the inequalities above are tight and $G\backslash v$ is one of the extremal graphs. In particular, $G\backslash v$ and $G$ contain $q$ copies of $K_{k-1}$. Note that all these cliques are disjoint and disconnected; otherwise $G$ contains a copy of $P_k$. Since $n\ge k, q\ge 1$ and thus $G$ is not connected, contradicting Lemma \ref{con}.

\end{proof}

Unlike the minimum degree, we are unable to bound the maximum degree of $G$ in such a way. However, we can obtain an upper-bound for the number of $K_t$'s containing any vertex $v$ based on its degree and $k$. Slightly abusing the notation, let $k_t(v)$ denote the number of $K_t$'s containing $v$.

\begin{lemma} \label{smallcase}
Let $G$ be a minimum-counter example and $v$ be a vertex in $G$. Let $a$ and $b < k-2$ be non-negative integers such that $d(v) = a (k-2) + b$. Then, $k_t(v) \le a \binom{k-2}{t-1} + \binom{b}{t-1}$. Moreover, if $d(v) \ge k-1$, then the inequality is strict, i.e., equality cannot be achieved.
\end{lemma}

\begin{proof}
Let $N(v)$ denote the set of all neighbors of $v$. Note that the number of copies of $K_t$ containing $v$ is the same as the number of copies of $K_{t-1}$ in $N(v)$. Since $G$ is $P_k$-free, it follows that the graph induced by $N(v)$ is $P_{k-1}$-free. Hence, by the minimality of $t$, we may apply Theorem \ref{path} on $N(v)$ for $t \ge 4$ or apply Theorem \ref{erdos} on $N(v)$ for $t=3$, and obtain $k_t(v) \le a \binom{k-2}{t-1} + \binom{b}{t-1}$. Thus, it remains to show that this bound is never achieved when $d(v) \ge k-1$. Suppose for the sake of contradiction that this bound is achieved, then the graph induced by $N(v)$ is one of the extremal graphs. Since $d(v)\ge k-1$, $a\ge 1$ and the graph induced by $N(v)$ contains a copy of $P_{k-2}$. Since $d(v)\ge k-1$, there exists a vertex $u \in N(v)$ outside of this path. Then, one can extend the path to $u$ via $v$, obtaining a path on $k$ vertices, a contradiction.
\end{proof}

In the extremal graphs of Theorem \ref{path}, the number of copies of $K_t$ is the same as $\frac{1}{t}\sum_{v}\binom{d(v)}{t-1}$. Then in order to compare $k_t(G)$ to the optimal number, it is useful to similarly construct a sequence $\{y_1, \ldots, y_N\}$ such that $k_t(G)\le \frac{1}{t}\sum_{i=1}^N \binom{y_i}{t-1}$. Motivated by this fact and the result of Lemma \ref{smallcase}, we consider the following function:

\begin{definition} \label{split}
	Given non-negative integers $\Delta$ and $d$, let $\spl_\D(d)$ output a sequence of $a_d$ integers of value $\D$ and one integer of value $b_d$ where $a_d\D+b_d=d$ and $b_d<\D$. Given a sequence of non-negative integers $\bar{d}=\{d_1, \ldots, d_n\}$, let $\spl_\D{\bar{d}}$ be the concatenation of the $\spl_\D(d_i)$'s, arranged in descending order.
\end{definition}

Then, we obtain the following corollary from Lemma \ref{smallcase}:

\begin{corollary} \label{countkt}
	Let $G$ be a minimum counter-example. Let $\{y_i\}_{i=1}^{N}=\spl_{k-2}(\bar{d})$ where $\bar{d}$ is the degree sequence of $G$. Then $k_t(G)\le \frac{1}{t}\sum_{i=1}^N\binom{y_i}{t-1}$.
\end{corollary}

Now, we can compare $\sum_{i=1}^N \binom{y_i}{t-1}$ with $q(k-1) \binom{k-2}{t-1} + r \binom{r-1}{t-1} = t \cdot k_t\left(qK_{k-1}\cup K_r\right)$ using the well-known Karamata's inequality:

\begin{lemma}[Karamata's inequality \cite{K}] \label{karma}
Let $f$ be a real valued convex function defined on $\N$. If $x_1, x_2, \ldots, x_N \in \N$ and $y_1, y_2, \ldots, y_N \in \N$ are such that
\begin{align}
&\bullet \;\; x_1 \ge\cdots \ge x_N \text{	and	} y_1 \ge y_2 \ge \cdots \ge y_N, \label{K1}
\\ &\bullet \;\; x_1 + x_2 + \cdots x_i \ge y_1 + y_2 + \cdots + y_i \text{	for all	} i \in \{1, 2, \ldots, N-1\}, \text{	and	} \label{K2}
\\ &\bullet \;\; x_1 + x_2 + \cdots x_N = y_1 + y_2 + \cdots + y_N, \label{K3}
\end{align}
then
\begin{equation} \label{karamata}
f(x_1) + f(x_2) + \cdots + f(x_N) \ge f(y_1) + f(y_2) + \cdots + f(y_N).
\end{equation}
\end{lemma}

\begin{definition}
For $x_1, x_2, \ldots, x_N \in \N$ and $y_1, y_2, \ldots, y_N \in \N$, we say that $(x_1, x_2, \ldots, x_N)$ majorizes $(y_1, y_2, \ldots, y_N)$ if the conditions in \eqref{K1}, \eqref{K2}, and \eqref{K3} are satisfied.
\end{definition}

\begin{proof} [Proof of Theorem \ref{path}]

Let $\{y_i\}_{i=1}^N=\spl_{k-2}(\bar{d})$, where $\bar{d}$ is the degree sequence of $G$. Then, construct the following sequence, $\{x_i\}_{i=1}^N$, of the same length $N$:

\begin{itemize}
\item $x_i = k-2$ for all $1 \le i \le q(k-1)$,
\item $x_i = r-1$ for all $q(k-1) < i \le q(k-1) + r$, and
\item $x_i = 0$ for all $i > q(k-1) + r$.
\end{itemize}

Next we show that $(x_1, x_2, \ldots, x_N)$ majorizes $(y_1, y_2, \ldots, y_N)$. Condition \eqref{K1} is trivially true. By applying Theorem \ref{erdos}, the number of edges in $G$ is at most $q\binom{k-1}{2} + \binom{r}{2}$. This implies $\sum_{i=1}^N y_i\le \sum_{i=1}^N x_i$. We modify the sequences slightly to satisfy Condition \eqref{K3}. We consider the sequence $\{y'_i\}_{i=1}^{N'}$ by adding as many $1$'s as needed at the end of $\{y_i\}_{i=1}^N$, until the condition is satisfied. We similarly create $\{x'\}_{i=1}^{N'}$ by padding the $x$ sequence with $0$'s until the two sequences have the same length. Note that Condition \eqref{K1} remains satisfied. In order to show that Condition \eqref{K2}, is satisfied, we consider the following three ranges separately.
\smallskip

Case 1: If $1 \le i \le q(k-1)$, then $$x'_1 + x'_2 + \cdots + x'_i = i (k-2) \ge y'_1 + y'_2 + \cdots + y'_i.$$
\smallskip

Case 2: $q(k-1) + r < i < N'$, then $$x'_1 + x'_2 + \cdots + x'_i = x'_1 + x'_2 + \cdots + x'_{N'} = y'_1 + y'_2 + \cdots + y'_{N'} \ge y'_1 + y'_2 + \cdots + y'_i.$$
\smallskip

Case 3: If $q(k-1) < i \le q(k-1) + r$, then since every vertex in $G$ has degree at least $r$, $\spl_{k-2}(d(v))$ outputs an integer at least $r$ for all $v \in V(G)$. Then, it follows that the first $n=q(k-1) + r$ elements in the sequence $y'$ are all at least $r$. Hence, $\sum_{j=i+1}^{q(k-1)+r} x'_j \le \sum_{j=i+1}^{q(k-1)+r} y'_j$. Thus,
\begin{align*}
&\sum_{j=1}^{N'} x'_i - \sum_{j=i+1}^{q(k-1)+r} x'_j \ge \sum_{j=1}^{N'} y'_i - \sum_{j=i+1}^{q(k-1)+r} y'_j \\
\Longrightarrow \;\; &\sum_{j=1}^{q(k-1)+r} x'_i - \sum_{j=i+1}^{q(k-1)+r} x'_j \ge \sum_{j=1}^{q(k-1)+r} y'_i - \sum_{j=i+1}^{q(k-1)+r} y'_j \\
\Longrightarrow \;\; &x'_1 + x'_2 + \cdots + x'_i \ge y'_1 + y'_2 + \cdots + y'_i.
\end{align*}

This proves $(x'_1, \ldots, x'_{N'})$ majorizes $(y'_1, \ldots, y'_{N'})$. Then , apply Karamata's inequality \eqref{karamata} for the convex function $f : \N \rightarrow \N$ defined by $f(x) = \binom{x}{t-1}$ to obtain
\begin{equation} \label{contradictionkt}
\sum_{i=1}^N \binom{y_i}{t-1} = \sum_{i=1}^{N'} \binom{y_i'}{t-1} \le \sum_{i =1}^{N'}\binom{x_i'}{t-1} = \sum_{i=1}^N\binom{x_i}{t-1}=t \cdot k_t(qK_{k-1}\cup K_r).
\end{equation}

If $G$ has a vertex of degree greater than $k-2$, then it follows from the second part of Lemma \ref{smallcase} and Corollary \ref{countkt} that $\frac{1}{t}\sum_{i=1}^N \binom{y_i}{t-1}> k_t(G)\ge k_t(qK_{k-1}\cup K_r)$, a contradiction to \eqref{contradictionkt}. Similarly, when the maximum degree of $G$ is at most $k-2$, the inequalities in \eqref{contradictionkt} and Corollary \ref{countkt} should be equalities. Consequently, for every vertex $v$, we have that $k_t(v) = \binom{d(v)}{t-1}$. Using Lemma \ref{mindeg}, we know that every vertex $v$ satisfies that $d(v) \ge t-1$. Hence, it follows that for every vertex $v$, the neighborhood $N(v)$ induces a clique. This fact together with Lemma \ref{con} implies that $G$ must be a complete graph. Since $n\ge k$, $G$ contains a copy of $P_k$, a contradiction.

\end{proof}


text:
\begin{document}
\title{On existence of PI-exponents of unital algebras}
\author[D.D. Repov\v s and M.V. Zaicev]
{Du\v san D. Repov\v s and Mikhail V. Zaicev}
\address{Du\v san D. Repov\v s \\Faculty of Education, and
Faculty of  Mathematics and Physics, University of Ljubljana \&
Institute of mathematics, Physics  and Mechanics, Ljubljana, 1000, Slovenia}
\email{dusan.repovs@guest.arnes.si}
\address{Mikhail V. Zaicev \\Department of Algebra\\ Faculty of Mathematics and
Mechanics\\  Moscow State University \\ Moscow,119992, Russia}
\email{zaicevmv@mail.ru}
\thanks{The first author was supported by the Slovenian Research Agency
grants P1-0292, J1-8131, N1-0114, N1-0083, and N1-0064.
The second author was supported by the Russian Science Foundation,
grant 16-11-10013$\Pi$}
\subjclass[2010]{Primary 16R10; Secondary 16P90}
\keywords{Polynomial identities, exponential codimension growth}

\begin{abstract} We construct a family of unital  non-associative algebras
$\{T_\alpha\vert~ 2<\alpha\in\mathbb R\}$ such that $\underline{exp}(T_\alpha)=2$,
whereas $\alpha\le\overline{exp}(T_\alpha)\le\alpha+1$. In particular, it follows
that ordinary PI-exponent of codimension growth of algebra $T_\alpha$  does not exist
for any $\alpha> 2$. This is the first example of a unital
algebra whose PI-exponent does not exist.
\end{abstract}

\maketitle

\section{Introduction}
We consider numerical invariants associated with polynomial identities
of algebras over a field of characteristic zero. Given an algebra $A$,
one can construct a sequence of non-negative integers $\{c_n(A)\},
n=1,2,\ldots$, called the {\it codimensions} of $A$, which is an important
numerical characteristic of identical relations of $A$. In general, the
sequence $\{c_n(A)\}$ grows faster than $n!$. However, there is a wide class of
algebras with exponentially bounded codimension growth. This class includes
all associative PI-algebras \cite{r2}, all finite-dimensional algebras
\cite{r2}, Kac-Moody algebras \cite{r3}, infinite-dimensional simple Lie
algebras of Cartan type \cite{r4}, and many others. If the sequence
$\{c_n(A)\}$ is exponentially bounded then the following natural question arises:
does the limit
\begin{equation}\label{eqi1}
\lim_{n\rightarrow\infty}\root n \of{c_n(A)}
\end{equation}
exist and what are its possible values? In case of existence, the limit
(\ref{eqi1}) is called the PI-{\it exponent} {\it of} $A$, denoted as $exp(A)$. At the end of 1980's, Amitsur
conjectured that for any associative PI-algebra, the limit (\ref{eqi1})
exists and is a non-negative integer. Amitsur's conjecture was confirmed
in \cite{r5,r6}. Later, Amitsur's conjecture was also confirmed for
finite-dimensional Lie and Jordan algebras \cite{r8,r7}. Existence
of $exp(A)$ was also proved for all finite-dimensional simple algebras \cite{r9}
and many others.

Nevertheless, the answer to Amitsur's question in the general case  is negative:
 a counterexample was presented in \cite{r18}. Namely, for any real
$\alpha>1$, an algebra $R_\alpha$ was constructed such that the lower
limit of $\root n \of{c_n(A)}$ is equal to $1$,  whereas the upper limit is equal
to $\alpha$. It now looks natural to describe classes of algebras in which
for any algebra $A$, its PI-exponent $exp(A)$ exists. One of the candidates
is the class of all finite-dimensional algebras. Another one is the class of
so-called special Lie algebras. The next interesting class consists of unital
algebras, it contains in particular, all algebras with an external unit. Given
an algebra $A$, we denote by $A^\sharp$ the algebra obtained from $A$ by
adjoining the external unit. There is a number of papers where the existence
of $exp(A^\sharp)$ has been proved, provided that $exp(A)$ exists \cite{r12,r13,
r11}. Moreover, in all these cases, $exp(A^\sharp)=exp(A)+1$.

The main goal of the present paper is to construct a series of unital algebras
such that $exp(A)$ does not exist, although the sequence $\{c_n(A)$ is exponentially
bounded (see Theorem \ref{t1} and Corollary \ref{c1} below). All details about polynomial
identities and their numerical characteristics can be found in \cite{r14,r15,r16}.

\section{Definitions and preliminary structures}

Let $A$ be an algebra over a field $F$ and let $F\{X\}$ be a free $F$-algebra with
an infinite set $X$ of free generators. The set $Id(A)\subset F\{X\}$ of all
identities of $A$ forms an ideal of $F\{X\}$. Denote by $P_n=P_n(x_1,\ldots,x_n)$ the
subspace of $F\{X\}$ of all multilinear polynomials on $x_1,\ldots,x_n\in X$. Then
$P_n\cap Id(A)$ is actually the set of all multilinear identities of $A$ of degree $n$.
An important numerical characteristic of $Id(A)$ is the sequence of non-negative integers
$\{c_n(A)\},n=1,2,\ldots~,$ where
$$
c_n(A)=\dim\frac{P_n}{P_n\cap Id(A)}.
$$
If the sequence $\{c_n(A)\}$ is exponentially bounded, then the lower and the upper
PI-exponents of $A$, defined as follows
$$
\underline{exp}(A)=\liminf_{n\rightarrow\infty} \root n \of{c_n(A)}, \quad
\overline{exp}(A)=\limsup_{n\rightarrow\infty} \root n \of{c_n(A)},
$$
are well-defined. An existence of ordinary PI-exponent (\ref{eqi1}) is equivalent to the
equality $\underline{exp}(A)=\overline{exp}(A)$.

In  \cite{r18}, an algebra $R=R(\alpha)$ such that
$\underline{exp}(R)=1,\overline{exp}(R)=\alpha$, was constructed for any real $\alpha>0$. Slightly modifying the
construction from \cite{r18}, we want to get for any real $\alpha>2$, an algebra $R_\alpha$
with $\underline{exp}(R_\alpha)^\sharp=2$ and $\alpha\le \overline{exp}(R^\sharp)\le\alpha+1$.

Clearly, polynomial identities of $A^\sharp$ strongly depend on the identities of $A$.
In particular, we make the following observation. Note that if $f=f(x_1,\ldots, x_n)$ is
a multilinear polynomial from $F\{X\}$ then $f(1+x_1,\ldots,1+x_n)\in F\{X\}^\sharp$ is
the sum
\begin{equation}\label{eq1}
f=\sum f_{i_1,\ldots,i_k},\quad \{i_1,\ldots,i_k\}\subseteq\{1,\ldots,n\},~
0\le k\le n,
\end{equation}
where $f_{i_1,\ldots,i_k}$ is a multilinear polynomial on
$x_{i_1},\ldots,x_{i_k}$ obtained from $f$ by replacing all $x_j,j\ne i_1,\ldots,i_k$
with $1$.

\begin{remark}\label{rm1}
A multilinear polynomial $f=f(x_1,\ldots,x_n)$ is an identity of $A^\sharp$ if and only
if all of its components $f_{i_1,\ldots,i_k}$ on the left hand side of (\ref{eq1}) are
identities of $A$.
\end{remark}

 The next statement
  easily follows
  from Remark \ref{rm1}.

\begin{remark}\label{rm2}
Suppose that an algebra $A$ satisfies all multilinear identities of an algebra $B$ of
degree $\deg f=k\le n$ for some fixed $n$. Then $A^\sharp$ satisfies all identities
of $B^\sharp$ of degree $k\le n$.
\end{remark}

Using results of \cite{r17}, we obtain the following inequalities.

\begin{lemma}\label{l1} (\cite[Theorem 2]{r17})
Let $A$ be an algebra with an exponentally bounded codimension growth. Then
$\overline{exp}(A^\sharp)\le \overline{exp}(A)+1$.\hfill $\Box$
\end{lemma}

\begin{lemma}\label{l2} (\cite[Theorem 3]{r17})
Let $A$ be an algebra with an exponentally bounded codimension growth satisfying the
identity (\ref{eq2}). Then $\underline{exp}(A^\sharp)\ge \underline{exp}(A)+1$.\hfill $\Box$
\end{lemma}

Given an integer $T\ge 2$, we define an infinite-dimensional algebra $B_T$ by its basis
$$
\{a,b,z_1^i,\ldots,z_T^i\vert~i=1,2,\ldots\}
$$
and by the multiplication table

$$
z^i_j a =\left\{
               \begin{array}{l}
         z^i_{j+1} \quad \rm{if} \quad j\le T-1,    \\
          0 \qquad \rm{if} \quad j=T
               \end{array}
             \right.
$$
for all $i\ge 1$ and
$$
z^i_Tb=z_1^{i+1},\quad i\ge 1.
$$
All other products of basis elements are equal to zero. Clearly, algebra $B_T$ is right
nilpotent of class 3, that is
\begin{equation}\label{eq2}
x_1(x_2x_3)\equiv 0
\end{equation}
is an identity of $B_T$. Due to (\ref{eq2}), any nonzero product of elements of $B_T$
must be left-normed. Therefore we omit brackets in the left-normed products and write
$(y_1y_2)y_3=y_1y_2y_3$ and $(y_1\cdots y_k)y_{k+1}=y_1\cdots y_{k+1}$ if $k\ge 3$.

We will use the following properties of algebra $B_T$.

\begin{lemma}\label{l3} (\cite[Lema 2.1]{r18})
Let $n\le T$. Then $c_n(B_T)\le 2n^3$.\hfill $\Box$
\end{lemma}

\begin{lemma}\label{l4} (\cite[Lema 2.2]{r18})
Let $n= kT+1$. Then
$$
c_n(B_T)\ge k!=\left(\frac{N-1}{T}\right)!.
$$\hfill $\Box$
\end{lemma}

\begin{lemma}\label{l5} (\cite[Lema 2.3]{r18})
Any multilinear identity $f=f(x_1,\ldots,x_n)$ of degree $n\le T$ of
algebra $B_T$ is an identity of $B_{T+1}$.\hfill $\Box$
\end{lemma}

Let $F[\theta]$ be a polynomial ring over $F$ on one indeterminate $\theta$
and let $F[\theta]_0$ be its subring of all polynomials without free term. Denote
by $Q_N$ the quotient algebra
$$
Q_N=\frac{F[\theta]_0}{(Q^{N+1})},
$$
where $(Q^{N+1})$ is an ideal of $F[\theta]$ generated by $Q^{N+1}$. Fix an
infinite sequence of integers $T_1<N_1<T_2<N_2\ldots$ and consider the algebra
\begin{equation}\label {eq3}
R=B(T_1,N_1)\oplus B(T_2,N_2)\oplus\cdots\, ,
\end{equation}
where $B(T,N)=B_T\otimes Q_N$.

Let $R$ be an algebra of the type (\ref{eq3}). Then the following lemma holds.

\begin{lemma}\label{l6}
For any $i\ge 1$, the following equalities hold:
\begin{itemize}
\item[(a)]
if $T_i\le n\le N_i$ then
$$
P_n\cap Id(R)=P_n\cap Id(B(T_i,N_i)\oplus B(T_{i+1},N_{i+1}))=
P_n\cap Id(B_{T_i}\oplus B_{T_{i+1}});
$$
\item[(b)]
if $N_i <n\le T_{i+1}$ then
$$
P_n\cap Id(R)=P_n\cap Id(B(T_{i+1},N_{i+1}))=
P_n\cap( Id(B_{T_{i+1}})).
$$
\end{itemize}
\end{lemma}

\begin{proof}
This follows immediately from the equality $B(T_i,N_i)^{N_i+1}=0$ and from Lemma \ref{l5}.
\end{proof}

The folowing remark is obvious.

\begin{remark}\label{rm3}
Ler $R$ be an algebra  of type (\ref{eq3}). Then
$$
Id(R^\sharp)=Id(B(T_1,N_1)^\sharp\oplus B(T_2,N_2)^\sharp\oplus\cdots ).
$$\hfill $\Box$
\end{remark}

\section{The main result}

\begin{theorem}\label{t1}
For any real $\alpha>1$, there exists an algebra $R_\alpha$ with  $\underline{exp}(R_\alpha)=1,
\overline{exp}(R_\alpha)=\alpha$ such that $\underline{exp}(R_\alpha^\sharp)=2$ and
$\alpha\le\overline{exp}(R_\alpha^\sharp)\le\alpha+1$.
\end{theorem}
\begin{proof}
Note that
\begin{equation}\label{eq4}
c_n(A)\le nc_{n-1}(A)
\end{equation}
for any algebra $A$ satisfying (\ref{eq2}). We will construct $R_\alpha$ of type (\ref{eq3})
by a special choice of the sequence $T_1,N_1,T_2,N_2,\ldots$ depending on $\alpha$. First,
choose $T_1$ such that
\begin{equation}\label{eq5}
2m^3<\alpha^m
\end{equation}
for all $m\ge T_1$. By Lemma \ref{l4}, algebra $B_{T_1}$ has an overexponential codimenson
growth. Hence there exists $N_1> T_1$ such that
$$
c_n(B_{T_1})<\alpha^n \quad \hbox{for~all} \quad n\le N_1-1
\quad \hbox{and} \quad c_{N_1}(B_{T_1}) \ge \alpha^{N_1}.
$$

Consider an arbitrary $n>N_1$. By Remark \ref{rm1}, we have
$$
c_n(R^\sharp)\le \sum_{k=0}^n {n\choose k}c_k(R)=\Sigma_1'+\Sigma_2',
$$
where
$$
\Sigma_1'=\sum_{k=0}^{N_1} {n\choose k}c_k(R),\quad
\Sigma_2'=\sum_{k=N_1+1}^{n} {n\choose k}c_k(R).
$$
By Lemma \ref{l6}, we have $\Sigma_1'+\Sigma_2'\le \Sigma_1+\Sigma_2$, where
$$
\Sigma_1=\sum_{k=0}^{N_1} {n\choose k}c_k(B_{T_1}),\quad
\Sigma_2=\sum_{k=0}^{n} {n\choose k}c_k(B_{T_2}).
$$
Then for any $T_2>N_1$, an upper bound for $\Sigma_2$ is
\begin{equation}\label{eq6}
\Sigma_2\le\sum_{k=0}^n {n\choose k} 2k^3\le 2n^3 \sum_{k=0}^n {n\choose k}=2n^3 2^n,
\end{equation}
which follows from (\ref{eq5}), provided that $n\le T_2$.

Let us find an upper bound for $\Sigma_1$ assuming that $n$ is sufficiently large.
Clearly,
\begin{equation}\label{eq6a}
\Sigma_1\le N_1\alpha^{N_1}\sum_{k=0}^{N_1} {n\choose k}
\end{equation}
which follows from the choice of $N_1$, relation (\ref{eq4}), and the equality
$B(T_1,N_1)^n=0$ for all $n\ge N_1+1$. Since $N_1\alpha^{N_1}$ is a constant for fixed
$N_1$, we only need to estimate the sum of binomial coefficients.

From the Stirling formula
$$
m! =\sqrt{2\pi m} (\frac{m}{e})^m e^{\frac{1}{12m+\theta_m}},\quad 0<\theta_m<1,
$$
it follows that
\begin{equation}\label{eq7}
{n\choose k}\le \sqrt{\frac{n}{k(n-k)}}\cdot\frac{n^n}{k^k(n-k)^{n-k}}.
\end{equation}

Now we define the function $\Phi:[0;1]\to\mathbb R$ by setting
$$
\Phi(x)=\frac{1}{x^x(1-x)^{1-x}}.
$$
It is not difficult to show that $\Phi$ increases on $[0;1/2]$, $\Phi(0)=1$,
and $\Phi(x)\le 2$ on $[0;1]$. In terms of the function $\Phi$ we rewrite (\ref{eq7}) as
\begin{equation}\label{eq8}
{n\choose k}\le \sqrt{\Phi\left(\frac{k}{n}\right)}\cdot\Phi\left(\frac{k}{n}\right)^n <
2\Phi\left(\frac{k}{n}\right)^n\le 2\Phi\left(\frac{N_1}{n}\right)^n
\end{equation}
provided that $n> 2N_1$. Now (\ref{eq6a}) and (\ref{eq8}) together with (\ref{eq6})
imply
$$
\Sigma_1\le 2N_1\alpha^{N_1}(N_1+1)\Phi\left(\frac{N_1}{n}\right)^n,
\quad \Sigma_2\le 2n^3 2^n.
$$

Since
$$
\lim_{n\to\infty}\Phi\left(\frac{N_1}{n} \right)^n=1
$$
and $\Phi(x)$ increases on $(0;1/2]$, there exists $n>2N_1$ such that
\begin{equation}\label{eq9}
2N_1(N_1+1)\alpha^{N_1}\Phi\left(\frac{N_1}{n} \right)^n+2n^3 2^n < (2+\frac{1}{2})^n.
\end{equation}

Now we take $T_2$ to be equal to the minimal $n>2N_1$ satisfying (\ref{eq9}). Note that for
such $T_2$ we have
$$
c_n(R^\sharp)<(2+\frac{1}{2})^n
$$
for $n=T_2$.

As soon as $T_2$ is choosen, we can take $N_2$ as the minimal $n$ such that $c_n(B_{T_2})
\ge \alpha^n$. Then again, $c_m(R)<m
\alpha^m$ if $m<N_2$. Repeating this procedure, we can
construct an infinite chain $T_1<N_1<T_2<N_2\cdots~$ such that
\begin{equation}\label{eq9o}
c_n(R)<\alpha^n+2n^3
\end{equation}
for all $n\ne N_1,N_2,\ldots$,
\begin{equation}\label{eq9a}
\alpha^n\le c_n(R)<\alpha^n+n(\alpha^{n-1}+2n^3)
\end{equation}
for all $n= N_1,N_2,\ldots$
and
\begin{equation}\label{eq10}
2N_j(N_j+1)\alpha^{N_j}\Phi\left(\frac{N_j}{T_{j+1}} \right)^{T_{j+1}}+
2T_{j+1}^3\cdot 2^{T_{j+1}} < (2+\frac{1}{2^j})^{T_{j+1}}
\end{equation}
for all $j=1,2,\ldots~$.

Let us denote by $R_\alpha$ the  just constructed algebra $R$ of type (\ref{eq3}).
Then (\ref{eq10}) means that
\begin{equation}\label{eq11}
c_n(R_\alpha^\sharp)<(2+\frac{1}{2^j})^n
\end{equation}
if $n=T_{j+1}, j=1,2,\ldots~$. It follows from inequality (\ref{eq11}) that
\begin{equation}\label{eq12}
\underline{exp}(R_\alpha^\sharp)\le 2.
\end{equation}
On the other hand, since $R_\alpha$ is not nilpotent, it follows that
\begin{equation}\label{eq13}
\underline{exp}(R_\alpha^\sharp)\ge 1.
\end{equation}
Since the PI-exponent of non-nilpotent algebra cannot be strictly less than $1$,
relations (\ref{eq12}), (\ref{eq13}) and Lemma \ref{l2} imply
$$
\underline{exp}(R_\alpha)=1,~\underline{exp}(R_\alpha^\sharp)=2.
$$
Finally, relations (\ref{eq9o}), (\ref{eq9a}) imply the equality $\overline{exp}(R_\alpha)=\alpha$.
Applying Lemma \ref{l1}, we see that $\overline{exp}(R_\alpha^\sharp)\le\alpha+1$.
The inequality $\alpha=\overline{exp}(R_\alpha)\le \overline{exp}(R_\alpha^\sharp)$ is obvious,
since $R_\alpha$ is a subalgebra of $R_\alpha^\sharp$, Thus we have  completed the proof
of Theorem \ref{t1}.
\end{proof}

As a consequence of Theorem \ref{t1} we get an infinite family of unital algebras of
exponential codimension growth without ordinary PI-exponent.

\begin{corollary}\label{c1}
Let $\beta>2$ be an arbitrary real number. Then the ordinary PI-exponent of unital algebra
$R_\beta^\sharp$ from Theorem \ref{t1} does not exist. Moreover,
$\underline{exp}(R_\beta^\sharp)=2$, whereas $\beta\le\overline{exp}(R_\beta^\sharp)\le\beta+1$.\hfill $\Box$
\end{corollary}

\section*{Acknowledgments} We would like to thank the referee for comments and suggestions.

config: arxiv


text:
/-
Copyright (c) 2021 Anne Baanen. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Anne Baanen
-/
import data.int.absolute_value
import linear_algebra.matrix.determinant

/-!
# Absolute values and matrices

This file proves some bounds on matrices involving absolute values.

## Main results

 * `matrix.det_le`: if the entries of an `n × n` matrix are bounded by `x`,
   then the determinant is bounded by `n! x^n`
 * `matrix.det_sum_le`: if we have `s` `n × n` matrices and the entries of each
   matrix are bounded by `x`, then the determinant of their sum is bounded by `n! (s * x)^n`
 * `matrix.det_sum_smul_le`: if we have `s` `n × n` matrices each multiplied by
   a constant bounded by `y`, and the entries of each matrix are bounded by `x`,
   then the determinant of the linear combination is bounded by `n! (s * y * x)^n`
-/

open_locale big_operators
open_locale matrix

namespace matrix

open equiv finset

variables {R S : Type*} [comm_ring R] [nontrivial R] [linear_ordered_comm_ring S]
variables {n : Type*} [fintype n] [decidable_eq n]

lemma det_le {A : matrix n n R} {abv : absolute_value R S}
  {x : S} (hx : ∀ i j, abv (A i j) ≤ x) :
  abv A.det ≤ nat.factorial (fintype.card n) • x ^ (fintype.card n) :=
calc  abv A.det
    = abv (∑ σ : perm n, _) : congr_arg abv (det_apply _)
... ≤ ∑ σ : perm n, abv _ : abv.sum_le _ _
... = ∑ σ : perm n, (∏ i, abv (A (σ i) i)) : sum_congr rfl (λ σ hσ,
  by rw [abv.map_units_int_smul, abv.map_prod])
... ≤ ∑ σ : perm n, (∏ (i : n), x) :
  sum_le_sum (λ _ _, prod_le_prod (λ _ _, abv.nonneg _) (λ _ _, hx _ _))
... = ∑ σ : perm n, x ^ (fintype.card n) : sum_congr rfl (λ _ _,
  by rw [prod_const, finset.card_univ])
... = nat.factorial (fintype.card n) • x ^ (fintype.card n) :
  by rw [sum_const, finset.card_univ, fintype.card_perm]

lemma det_sum_le {ι : Type*} (s : finset ι) {A : ι → matrix n n R}
  {abv : absolute_value R S} {x : S} (hx : ∀ k i j, abv (A k i j) ≤ x) :
  abv (det (∑ k in s, A k)) ≤
    nat.factorial (fintype.card n) • (finset.card s • x) ^ (fintype.card n) :=
det_le $ λ i j,
calc  abv ((∑ k in s, A k) i j)
    = abv (∑ k in s, A k i j) : by simp only [sum_apply]
... ≤ ∑ k in s, abv (A k i j) : abv.sum_le _ _
... ≤ ∑ k in s, x : sum_le_sum (λ k _, hx k i j)
... = s.card • x : sum_const _

lemma det_sum_smul_le {ι : Type*} (s : finset ι) {c : ι → R} {A : ι → matrix n n R}
  {abv : absolute_value R S}
  {x : S} (hx : ∀ k i j, abv (A k i j) ≤ x) {y : S} (hy : ∀ k, abv (c k) ≤ y) :
  abv (det (∑ k in s, c k • A k)) ≤
    nat.factorial (fintype.card n) • (finset.card s • y * x) ^ (fintype.card n) :=
by simpa only [smul_mul_assoc] using
det_sum_le s (λ k i j,
calc  abv (c k * A k i j)
    = abv (c k) * abv (A k i j) : abv.map_mul _ _
... ≤ y * x : mul_le_mul (hy k) (hx k i j) (abv.nonneg _) ((abv.nonneg _).trans (hy k)))

end matrix

subset_name: curated


TITLE: Roots of a quadratic polynomial over a finite field
QUESTION [3 upvotes]: I am having a hard time figuring this problem out. I have not come up with anything substantial in terms of solving it. Any help would be great.
Show that if $z \in F_{p^2}$ is a root of the polynomial $g = X^2 +aX + b$ where $a, b \in F_p$, then $z^p$ is also a root of $g$.
Also, verify that $a = - z - z^p$ and that $b = z^{p+1}$ provided that $z \notin F_p$. Is this true if $z \in F_p$? Explain your answer.

REPLY [5 votes]: Consider the Frobenius morphism $\;\begin{aligned}[t]\mathbf F_{p^2}&\longrightarrow \mathbf F_{p^2}\\x&\longmapsto x^p\end{aligned}$.  Its fixed points are the prime field $\;\mathbf F_p$. Hence, if $z^2+az+b=0$, then
$$(z^2+az+b)^p=(z^p)^2+az^p+b=0, $$
which proves $z^p$ is a root of $X^2+aX+b$.
On the other hand, the sum of the roots of this polynomial, in any splitting field, is equal to $-a$ and their product is equal to $c$ (Vieta's relations). Thus, if $z^p\neq z$, we have two roots of the equation, and
$$z+z^p=-a, \quad z z^p=z^{p+1}=c.$$
If $z\in \mathbf F_p$, this is no more true since $z$ and $z^p$ are  the same root.