Degrees of Second and Higher-Order Polynomials

Lim, Donghyun; Ziegler, Martin

doi:10.4230/LIPIcs.FSTTCS.2025.42

Degrees of Second and Higher-Order Polynomials

Donghyun Lim

KAIST, Daejeon, Republic of Korea Martin Ziegler

KAIST, Daejeon, Republic of Korea

Abstract

Second-order polynomials generalize classical (=first-order) ones in allowing for additional variables that range over functions rather than values. We are motivated by their applications in higher-order computational complexity theory, extending for instance discrete classes (like $\text{\sf P}/\text{\sf FP}$ or $\text{\sf PSPACE}/\text{\sf FPSPACE}$ ) to operators in Analysis [Kapron&Cook’96], [Kawamura&Cook’12]. The degree subclassifies ordinary polynomial growth into linear, quadratic, cubic, etc. To similarly classify second-order polynomials, we (well-)define their degree by structural induction as an “arctic” first-order polynomial: a term/expression over integer variable $\operatorname{\textbf{D}}$ and operations $+$ and $\cdot$ and binary $\max()$ . This generalized degree turns out to transform nicely under (now two kinds of) polynomial composition. As examples, we collect and determine the degrees of previous and new asymptotic analyses of algorithms and operators receiving function/oracle arguments. Then we motivate and introduce third-order polynomials and their degrees as arctic second-order polynomials, along with their transformations under three kinds of composition. Proceeding to fourth order and beyond yields a hierarchy, with characterization in Simply Typed Lambda Calculus.

Keywords and phrases:

Logic in Computer Science, Higher Order Program Analysis, Asymptotic Type Theory

Copyright and License:

2012 ACM Subject Classification:

Mathematics of computing ; Theory of computation

\rightarrow

Higher order logic ; Theory of computation

\rightarrow

Type theory

Related Version:

arXiv Version: http://arXiv.org/abs/2305.03439 [21]

Acknowledgements:

We thank anonymous reviewers for feedback and guidance.

Funding:

This work was supported by the National Research Foundation of Korea and by the Korean Ministry of Science and ICT with grants NRF-2017R1E1A1A03071032 and NRF-2016K1A3A7A03950702 and by KAIST in-house grant.

DOI:

10.4230/LIPIcs.FSTTCS.2025.42

Event:

45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Editors:

C. Aiswarya, Ruta Mehta, and Subhajit Roy

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Motivating Examples and Overview

Polynomial – as opposed to, say, exponential – growth is investigated in areas such as Chemistry (reaction kinetics) and Mathematics (Gromov’s theorem) and of course Computer Science (Cobham–Edmonds Thesis). The degree of polynomial growth provides a refined classification into linear, quadratic, cubic, quartic, quintic, etc. We focus on univariate polynomials over $\mathbb{N}$ . For example $15\operatorname{\textbf{D}}^{3}+2\operatorname{\textbf{D}}+4$ is of degree 3 in variable $\operatorname{\textbf{D}}$ .

So-called second-order polynomials, involving an additional variable ranging over functions on natural numbers (instead of values, i.e., one step up the type hierarchy), arise naturally in many areas: including but not limited to characterizations of computational complexity classes and reductions on higher types [30, 13, 15, 7, 25, 2].

Example 1.

$\displaystyle\boldsymbol{\Phi}\Big(\boldsymbol{\Phi}^{3}\big(\boldsymbol{\Phi}% ^{5}(\operatorname{\textbf{N}})\big)\Big)\cdot\big(\boldsymbol{\Phi}(% \operatorname{\textbf{N}}^{2})+\operatorname{\textbf{N}}^{9}\big)\cdot% \operatorname{\textbf{N}}^{4}\;+\;\\ \hskip 52.00005pt+\;\operatorname{\textbf{N}}^{999}\cdot\boldsymbol{\Phi}\big(% 3\operatorname{\textbf{N}}^{5}+4\boldsymbol{\Phi}^{8}(\operatorname{\textbf{N}% }+2)\cdot\boldsymbol{\Phi}(7\operatorname{\textbf{N}})+\boldsymbol{\Phi}^{6}(1% )\big)\;+\;\boldsymbol{\Phi}^{50}(\operatorname{\textbf{N}}^{9})$
is a second-order polynomial $\boldsymbol{\Pi}$ in first-order variable $\operatorname{\textbf{N}}$ and second-order variable $\boldsymbol{\Phi}$ .
The degree of this second-order polynomial turns out to be the following expression $\widetilde{\operatorname{\textbf{P}}}(\operatorname{\textbf{D}})=$

\max\big\{\;\operatorname{\textbf{D}}\cdot(3\operatorname{\textbf{D}})\cdot(5% \operatorname{\textbf{D}})+\max\{2\operatorname{\textbf{D}},9\}+4\;,\;999+% \operatorname{\textbf{D}}\cdot\max\{5,8\operatorname{\textbf{D}}+\operatorname% {\textbf{D}}\}\;,\;450\cdot\operatorname{\textbf{D}}\;\big\}

(1)

Other than classical polynomials, it involves the (binary) $\max$ operation and is thus called “arctic”: see Remark 2a) below. However, whenever $\operatorname{\textbf{D}}$ has value $d\geq 6$ , Expression (1) semantically coincides with the above simple cubic polynomial $15\operatorname{\textbf{D}}^{3}+2\operatorname{\textbf{D}}+4$ . $\lrcorner$

In Section 2 below, Definition 5 formally recalls second-order polynomials; and Subsection 2.3 collects both previous and new examples and applications from Complexity Theory and Analysis. In Subsection 2.1, Definition 9 introduces the notion of second-order polynomial degree; and Proposition 12 records some of its properties as well as connections to ordinary (=first-order) polynomial degrees. Theorem 7 asserts semantic completeness.

Section 3 climbs further up the type hierarchy: first to third-order polynomials, whose degrees are arctic second-order polynomials (Subsection 3.2); and then (Subsection 3.3) to the higher-order cases, including a characterization in terms of a certain fragment of Simply Typed Lambda Calculus in Subsection 3.4. Proofs are deferred to Appendices A and B; those omitted due to page constraints can be found in [21].

Our notions of higher-order degrees offer sub-classifications of higher-degree polynomial growth to various levels of detail; cf. Table 2 in Subsection 2.1. Such a sub-classification had been envisioned/requested by Akitoshi Kawamura (personal conversation, ca. 2015).

$\blacktriangleright$ Remark 2.

a)

“Tropical” historically refers to expressions over $(\min,+,\infty,0)$ instead of classical $(+,\cdot,0,1)$ [26], “arctic” dually to $(\max,+,-\infty,0)$ : used in Definition 3 below. Both are instances of so-called “exotic” semi-rings [5, §2].
b)

First-order polynomials are commonly defined syntactically as a family of well-formed expressions over $+$ and $\cdot$ and $1$ : over one or several ( $M\in\mathbb{N}$ ) variables $\vec{\operatorname{\textbf{X}}}=(X_{1},\ldots,X_{M})$ , with or without (=“pure”) additional constants from some semi/ring $\mathcal{R}$ , with or without (=“positive”) subtraction. Logically speaking, they are precisely the elements of a suitable term language. Each syntactic polynomial $\operatorname{\textbf{P}}\in\mathcal{R}[\vec{\operatorname{\textbf{X}}}]$ gives rise semantically to a unique total function $\overline{\operatorname{\textbf{P}}}=p:\mathcal{R}^{M}\to\mathcal{R}$ .
c)

Regarding the converse direction – namely translating certain functions (semantics) to syntactic polynomials – existence and uniqueness questions can be challenging depending on the particular setting. [28] for example investigates which multivariate functions over a ring $\mathcal{R}$ with zero-divisors can be represented as polynomials at all. And Hilbert’s famous Nullstellensatz characterizes the non-uniqueness of polynomial representations of a multivariate partial function, defined on some algebraic variety over $\mathcal{R}=\mathbb{C}$ .
d)

By virtue of Commutative and Associative and Distributive Laws, any classical multivariate polynomial can be rewritten – see Equation (3) – as a linear combination of monomials $\operatorname{\textbf{X}}_{1}^{d_{1}}\cdots\operatorname{\textbf{X}}_{M}^{d_{M}}$ of lexicographically strictly increasing multidegrees $(d_{1},\ldots,d_{M})$ . And for $\mathcal{R}=\mathbb{N}$ , this syntactic normal form is also semantically unique:
e)

Let $\operatorname{\textbf{P}}(\vec{\operatorname{\textbf{X}}}),\operatorname{% \textbf{Q}}(\vec{\operatorname{\textbf{X}}})$ denote two ordinary syntactically non-equivalent (Equation 3) positive pure polynomials in variables $\vec{\operatorname{\textbf{X}}}=(\operatorname{\textbf{X}}_{1},\ldots,% \operatorname{\textbf{X}}_{M})$ over $\mathbb{N}$ . Then there exists an assignment $\vec{x}=(x_{m})_{{}_{m}}\in\mathbb{N}^{M}$ that makes them evaluate differently: $\overline{\operatorname{\textbf{P}}}(\vec{x})\neq\overline{\operatorname{% \textbf{Q}}}(\vec{x})$ .

Item e) follows for instance from the (DeMillo-Lipton-) Schwartz-Zippel Lemma, based on monomial normal form. Theorem 7 generalizes Item e) to the second-order case.

Introducing second-order polynomial degrees had been attempted in [31]: a brief note summarizing a spontaneous short Dagstuhl idea without (explicit) definitions nor proofs, which furthermore wrongly claims that the second-order degree is a (non-arctic) polynomial – rendering the remaining claims moot. Section 2 puts said ideas from [31] on a sound foundation with definitions and proofs and elaborate examples; and Section 3 takes a new perspective on the first and second-order case, in order to then generalize to third and higher-order polynomials and degrees.

Table 1: List of symbols and notational conventions.

$\operatorname{\textbf{N}},\operatorname{\textbf{M}},\operatorname{\textbf{D}}$	first-order variables
$\overline{\operatorname{\textbf{N}}}=n,\overline{\operatorname{\textbf{M}}}=m,% \overline{\operatorname{\textbf{D}}}=d\in\mathbb{N}$	values of said variables
$\operatorname{\textbf{P}}=\operatorname{\textbf{P}}(\vec{\operatorname{\textbf% {N}}}),\operatorname{\textbf{Q}}=\operatorname{\textbf{Q}}(\operatorname{% \textbf{M}})$	pure positive multi/uni-variate 1st-order polynomials
$\overline{\operatorname{\textbf{P}}}=p,\overline{\operatorname{\textbf{Q}}}=q:% \mathbb{N}{\scriptstyle\nearrow}\mathbb{N}$	induced monotonic functions
$d=\deg(\operatorname{\textbf{P}})\in\mathbb{N}$	(total) degree of non-zero first-order polynomial
$\widetilde{\operatorname{\textbf{P}}},\widetilde{\operatorname{\textbf{Q}}}$	arctic first-order polynomials
$\operatorname{\textbf{Q}}=\lim\widetilde{\operatorname{\textbf{Q}}}$	induced asymptotic first-order polynomial
$\boldsymbol{\Phi},\boldsymbol{\Psi}$	second-order variables
$\overline{\boldsymbol{\Phi}}=\phi,\overline{\boldsymbol{\Psi}}=\psi:\mathbb{N}% {\scriptstyle\nearrow}\mathbb{N}$	values of said variables
$\boldsymbol{\Pi}=\boldsymbol{\Pi}(\boldsymbol{\Phi},\vec{\operatorname{\textbf% {N}}}),\boldsymbol{\Xi}(\boldsymbol{\Psi},\operatorname{\textbf{N}})$	(multi/uni-variate) second-order polynomials
$\overline{\boldsymbol{\Pi}}:(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\times% \mathbb{N}^{m}\nearrow\mathbb{N}$	induced monotonic mixed functionals
$\overline{\boldsymbol{\Xi}}=\mathcal{Q}:(\mathbb{N}{\scriptstyle\nearrow}% \mathbb{N})\nearrow(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})$	Curry-ed monotonic operator
$\widetilde{\operatorname{\textbf{P}}}=\operatorname{Deg}(\boldsymbol{\Pi})$	arctic first-order polynomial as second-order degree
$\operatorname{\textbf{P}}=\lim\operatorname{Deg}(\boldsymbol{\Pi})$	1st-order polynomial as asymptotic 2nd-order degree
$d=\deg\big(\lim\operatorname{Deg}(\boldsymbol{\Pi}))\in\mathbb{N}$	nesting depth of second-order polynomial $\boldsymbol{\Pi}$
$\widetilde{\boldsymbol{\Pi}},\widetilde{\boldsymbol{\Xi}}$	arctic second-order polynomials
$\boldsymbol{\mathfrak{F}},\boldsymbol{\mathfrak{G}}$	third-order variables
$\overline{\boldsymbol{\mathfrak{F}}}=\mathcal{F},\overline{\boldsymbol{% \mathfrak{G}}}=\mathcal{G}:(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})% \nearrow(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})$	values of said variables
$\boldsymbol{\mathfrak{P}}=\boldsymbol{\mathfrak{P}}(\boldsymbol{\mathfrak{F}},% \boldsymbol{\Phi},\operatorname{\textbf{N}}),\boldsymbol{\mathfrak{Q}}(% \boldsymbol{\mathfrak{G}},\boldsymbol{\Psi},\operatorname{\textbf{M}})$	third-order polynomials
$\overline{\boldsymbol{\mathfrak{P}}}:\big((\mathbb{N}{\scriptstyle\nearrow}% \mathbb{N})\nearrow(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\big)\times(% \mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\times\mathbb{N}\nearrow\mathbb{N}$	induced monotonic mixed hyper-functional
$\overline{\boldsymbol{\mathfrak{P}}}:\big((\mathbb{N}{\scriptstyle\nearrow}% \mathbb{N})\nearrow(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\big)\times(% \mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\nearrow(\mathbb{N}{\scriptstyle% \nearrow}\mathbb{N})$	Curry-ed monotonic mixed operator
$\overline{\boldsymbol{\mathfrak{P}}}:\big((\mathbb{N}{\scriptstyle\nearrow}% \mathbb{N})\nearrow(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\big)\nearrow% \big((\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\nearrow(\mathbb{N}{% \scriptstyle\nearrow}\mathbb{N})\big)$	Curry-ed monotonic hyper-operator
$\widetilde{\boldsymbol{\Pi}}=\operatorname{DEG}(\boldsymbol{\mathfrak{P}})$	arctic second-order polynomial as third-order degree

1.1 Arctic First-Order Polynomials

Definition 9 below defines the degree $\operatorname{Deg}(\boldsymbol{\Pi})$ of a second-order polynomial to be an ordinary polynomial, but one involving $\max()$ .

Definition 3.

An arctic (first-order) polynomial $\widetilde{\operatorname{\textbf{P}}}(\vec{\operatorname{\textbf{X}}})$ in variables $\vec{\operatorname{\textbf{X}}}$ is a well-formed expression over $\operatorname{\textbf{X}}$ and constant symbols $0,1$ (unary) and binary $+,\cdot,\max()$ .

Recall Example 1 and Remark 2a). As opposed to Definition 5, the constant 0 is permitted here. We refrain from spelling out the obvious semantics $\overline{\operatorname{\textbf{P}}}$ of an arctic polynomial $\widetilde{\operatorname{\textbf{P}}}$ . Note that, when evaluating $\widetilde{\operatorname{\textbf{P}}}(\vec{x})$ on an arbitrary fixed integer vector $\vec{x}$ , any occurrence of $\max()$ evaluates to at least one of its two arguments. Moreover, in the univariate case $\vec{X}=X$ and as $\overline{X}\to\infty$ , the role of the dominant argument in $\max()$ may switch only finitely often, as one can see by structural induction:

Lemma 4.

a)

For any two distinct univariate positive ordinary polynomials $\operatorname{\textbf{P}}=\operatorname{\textbf{P}}(\operatorname{\textbf{N}})$ and $\operatorname{\textbf{Q}}=\operatorname{\textbf{Q}}(\operatorname{\textbf{N}})$ , their associated polynomial functions $p=\overline{\operatorname{\textbf{P}}}$ and $q=\overline{\operatorname{\textbf{Q}}}$ satisfy

$\exists N\in\mathbb{N}:\quad\big(\forall n\geq N:\;p(n)>q(n)\big)\quad\vee% \quad\big(\forall n\geq N:\;p(n)<q(n)\big)\enspace.$ (2)
b)

Fix univariate arctic polynomial $\widetilde{\operatorname{\textbf{P}}}=\widetilde{\operatorname{\textbf{P}}}(% \operatorname{\textbf{D}})$ . Its value coincides, for all sufficiently large arguments $d\in\mathbb{N}$ , with $\overline{\operatorname{\textbf{P}}}(d)$ for a unique ordinary (positive pure) polynomial $\operatorname{\textbf{P}}=\operatorname{\textbf{P}}(\operatorname{\textbf{D}})$ .

Call $\operatorname{\textbf{P}}\in\mathbb{N}[\operatorname{\textbf{D}}]$ from Lemma 4b) the asymptotic polynomial induced by univariate arctic $\widetilde{\operatorname{\textbf{P}}}$ , written $\operatorname{\textbf{P}}=\lim\widetilde{\operatorname{\textbf{P}}}$ . There is no risk of confusing the polynomial $\lim\widetilde{\operatorname{\textbf{P}}}$ with the “value” $\infty=\lim_{d\to\infty}\widetilde{\operatorname{\textbf{P}}}(d)$ . We record that $\lim(\widetilde{\operatorname{\textbf{P}}}+\widetilde{\operatorname{\textbf{Q}% }})=(\lim\widetilde{\operatorname{\textbf{P}}})+(\lim\widetilde{\operatorname{% \textbf{Q}}})$ and $\lim(\widetilde{\operatorname{\textbf{P}}}\cdot\widetilde{\operatorname{% \textbf{Q}}})=(\lim\widetilde{\operatorname{\textbf{P}}})\cdot(\lim\widetilde{% \operatorname{\textbf{Q}}})$ . Lemma 4 is limited to the univariate case: multivariate arctic terms like $\max(\operatorname{\textbf{X}}\operatorname{\textbf{Y}}^{2},\operatorname{% \textbf{X}}^{2}\operatorname{\textbf{Y}})$ may not asymptotically coincide with an ordinary one; see also Example 19.

2 Second-Order Polynomials

We consider “positive pure” (univariate) second-order polynomials, that is, with syntactically well-formed expressions involving – in addition to operations $+,\cdot$ and $1$ as only constant and classical variables $\vec{\operatorname{\textbf{N}}}=(\operatorname{\textbf{N}}_{1},\ldots,% \operatorname{\textbf{N}}_{M})$ – some unary function-type variable $\boldsymbol{\Phi}$ [13]:

Definition 5.

Second-order polynomials, like $\boldsymbol{\Pi}=\boldsymbol{\Pi}(\boldsymbol{\Phi},\vec{\operatorname{\textbf% {N}}})$ and $\boldsymbol{\Xi}=\boldsymbol{\Xi}(\boldsymbol{\Phi},\vec{\operatorname{\textbf% {N}}})$ , are syntactically generated by the Backus-Naur rules

\boldsymbol{\Pi},\boldsymbol{\Xi}\quad::=\quad 1\mid\operatorname{\textbf{N}}_% {1}\mid\ldots\mid\operatorname{\textbf{N}}_{M}\mid\boldsymbol{\Pi}+\boldsymbol% {\Xi}\mid\boldsymbol{\Pi}\cdot\boldsymbol{\Xi}\mid\boldsymbol{\Phi}(% \boldsymbol{\Pi})\enspace.

In other words, second-order polynomials are the least class of formal expressions (=terms)

$\blacksquare$

that include constant $1$ and variables $(\operatorname{\textbf{N}}_{1},\ldots,\operatorname{\textbf{N}}_{M})=\vec{% \operatorname{\textbf{N}}}$
$\blacksquare$

and are closed under binary addition $+$ and product $\cdot$
$\blacksquare$

Moreover, when $\boldsymbol{\Pi}$ is a second-order polynomial, then so is $\boldsymbol{\Phi}(\boldsymbol{\Pi})$ :

Regarding semantics, we continue using overline to denote the interpretation of an expression as a mapping: Each variable $\operatorname{\textbf{N}}$ may take values $\overline{\operatorname{\textbf{N}}}=n$ ranging over $\mathbb{N}$ ; and $\overline{\boldsymbol{\Phi}}$ ranges over $(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})$ , the set of nondecreasing total unary functions $\phi:\mathbb{N}\nearrow\mathbb{N}$ . Extended by structural induction to compound expressions, let $\overline{\boldsymbol{\Phi}(\boldsymbol{\Pi})}$ evaluate to $\phi\big(\overline{\boldsymbol{\Pi}}(\phi,n)\big)$ and $\overline{1}=1$ .

Recall Example 1, note that we prohibit the constant 0. Exponentiation (only to a natural number power) abbreviates repeated multiplication: $\operatorname{\textbf{N}}^{3}=\operatorname{\textbf{N}}\cdot\operatorname{% \textbf{N}}\cdot\operatorname{\textbf{N}}$ and $\boldsymbol{\Phi}^{2}(\boldsymbol{\Xi})=\boldsymbol{\Phi}(\boldsymbol{\Xi})% \cdot\boldsymbol{\Phi}(\boldsymbol{\Xi})$ , as opposed to repeated composition $\boldsymbol{\Phi}\circ\boldsymbol{\Phi}=\boldsymbol{\Phi}^{(2)}$ . Commutative, associative, distributive laws extend from numbers to (both first and) second-order polynomials pointwise:

Definition 6.

Let “ $\mathrel{\begin{matrix}\includegraphics{dagpub-standalone-dagpub-svg-2026-02-0% 3-16-22-40.pdf2svg.svg}\end{matrix}}$ ” denote syntactic equivalence of terms up to Associative, Commutative, and Distributive Laws; formally the equivalence relation generated by the following rules:

	$\displaystyle\boldsymbol{\Pi}+\boldsymbol{\Xi}\mathrel{\begin{matrix}% \includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}% \end{matrix}}\boldsymbol{\Xi}+\boldsymbol{\Pi},\qquad(\boldsymbol{\Pi}+% \boldsymbol{\Xi})+\boldsymbol{\Lambda}\mathrel{\begin{matrix}\includegraphics{% dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}% \boldsymbol{\Pi}+(\boldsymbol{\Xi}+\boldsymbol{\Lambda}),\hskip 100.00015pt$		(3)
	$\displaystyle\boldsymbol{\Pi}\cdot\boldsymbol{\Xi}\mathrel{\begin{matrix}% \includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}% \end{matrix}}\boldsymbol{\Xi}\cdot\boldsymbol{\Pi},\quad(\boldsymbol{\Pi}\cdot% \boldsymbol{\Xi})\cdot\boldsymbol{\Lambda}\mathrel{\begin{matrix}% \includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}% \end{matrix}}\boldsymbol{\Pi}\cdot(\boldsymbol{\Xi}\cdot\boldsymbol{\Lambda}),% \quad\boldsymbol{\Pi}\cdot 1\mathrel{\begin{matrix}\includegraphics{dagpub-% standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\boldsymbol% {\Pi},\quad\boldsymbol{\Pi}\cdot(\boldsymbol{\Xi}+\boldsymbol{\Lambda})% \mathrel{\begin{matrix}\includegraphics{dagpub-standalone-dagpub-svg-2026-02-0% 3-16-22-40.pdf2svg.svg}\end{matrix}}\boldsymbol{\Pi}\cdot\boldsymbol{\Xi}+% \boldsymbol{\Pi}\cdot\boldsymbol{\Lambda}$
	$\displaystyle\big(\boldsymbol{\Pi}\mathrel{\begin{matrix}\includegraphics{% dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}% \boldsymbol{\Pi}^{\prime}\;\wedge\;\boldsymbol{\Xi}\mathrel{\begin{matrix}% \includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}% \end{matrix}}\boldsymbol{\Xi}^{\prime}\big)\quad\Rightarrow\quad\boldsymbol{% \Pi}+\boldsymbol{\Xi}\mathrel{\begin{matrix}\includegraphics{dagpub-standalone% -dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\boldsymbol{\Pi}^{% \prime}+\boldsymbol{\Xi}^{\prime}\;\;\wedge\;\;\boldsymbol{\Pi}\cdot% \boldsymbol{\Xi}\mathrel{\begin{matrix}\includegraphics{dagpub-standalone-% dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\boldsymbol{\Pi}^{% \prime}\cdot\boldsymbol{\Xi}^{\prime}\;\;\wedge\;\;\boldsymbol{\Phi}(% \boldsymbol{\Pi})\mathrel{\begin{matrix}\includegraphics{dagpub-standalone-% dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\boldsymbol{\Phi}(% \boldsymbol{\Pi}^{\prime})$

Syntactic equivalence is semantically sound for 2nd-order polynomials: $\boldsymbol{\Pi}\mathrel{\begin{matrix}\includegraphics{dagpub-standalone-% dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\boldsymbol{\Xi}% \Rightarrow\overline{\boldsymbol{\Pi}}\equiv\overline{\boldsymbol{\Xi}}$ . Generalizing Remark 2e), the converse – semantic completeness – is also true, but less obvious:

Theorem 7.

Let $\boldsymbol{\Pi}(\boldsymbol{\Phi},\operatorname{\textbf{N}}),\boldsymbol{\Xi}% (\boldsymbol{\Phi},\operatorname{\textbf{N}})$ be syntactically non-equivalent second-order polynomials. There exists an assignment $n\in\mathbb{N}$ and $\phi\in\!(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})$ such that $\overline{\boldsymbol{\Pi}}(\phi,n)\neq\overline{\boldsymbol{\Xi}}(\phi,n)$ .

See [20, 21] for a proof, omitted here due to space limitations. A similar result has been shown for Simply Typed Lambda Calculus (see also Subsection 3.4 below) modulo integer arithmetic [27, Theorems 5.2+5.6], with two caveats: function variable $\boldsymbol{\Phi}$ is supposed bi-variate [27, p.684] and runs over all (not just monotonic) total integer mappings [27, Definition 4.11].

2.1 Second-Order Polynomial Degree

The total degree $\deg(\operatorname{\textbf{P}})\in\mathbb{N}$ of a classical multivariate polynomial $\operatorname{\textbf{P}}=\operatorname{\textbf{P}}(\vec{\operatorname{\textbf% {X}}})\neq 0$ is commonly defined first for monomials, and then for linear combinations of the latter: relying on the monomial normal form, recall Remark 2d+e). An alternative equivalent definition proceeds by structural induction, for instance for positive pure polynomials as follows:

	$\displaystyle\deg(1)=0,\qquad\deg(\operatorname{\textbf{P}}+\operatorname{% \textbf{Q}})=\max\{\deg(\operatorname{\textbf{P}}),\deg(\operatorname{\textbf{% Q}})\},$		(4)
	$\displaystyle\deg(\operatorname{\textbf{X}}_{m})=1,\qquad\deg(\operatorname{% \textbf{P}}\cdot\operatorname{\textbf{Q}})=\deg(\operatorname{\textbf{P}})+% \deg(\operatorname{\textbf{Q}})\enspace.$

The former approach builds on monomial normal form (Remark 2d) while the latter needs to separately establish well-definition, namely invariance under syntactic equivalence (3):

\operatorname{\textbf{P}}\mathrel{\begin{matrix}\includegraphics{dagpub-% standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}% \operatorname{\textbf{Q}}\quad\Rightarrow\quad\deg(\operatorname{\textbf{P}})% \;=\;\deg(\operatorname{\textbf{Q}})\enspace,

(5)

which we generalize in Remark 10 below. Either way, the Rule of Composition then follows, in the univariate case expressed concisely as: $\deg(\operatorname{\textbf{P}}\circ\operatorname{\textbf{Q}})=\deg(% \operatorname{\textbf{P}})\cdot\deg(\operatorname{\textbf{Q}})$ .

$\blacktriangleright$ Remark 8.

Strictly speaking, $\operatorname{\textbf{P}}\circ\operatorname{\textbf{Q}}$ needs to be defined syntactically: for instance by structural induction on $\operatorname{\textbf{P}}$ , essentially replacing each occurrence of variable $\operatorname{\textbf{X}}$ in $\operatorname{\textbf{P}}$ with $\operatorname{\textbf{Q}}$ . And said inductive definition then gets justified semantically by concluding $\overline{\operatorname{\textbf{P}}\circ\operatorname{\textbf{Q}}}=\overline{% \operatorname{\textbf{P}}}\circ\overline{\operatorname{\textbf{Q}}}$ , where (only) the right-hand side means composition of functions. Definition 11 and Proposition 12 below proceed in this very way, for second-order polynomials.

For univariate polynomials, the integer total order on degrees “ $\deg(\operatorname{\textbf{P}})\leq\deg(\operatorname{\textbf{Q}})$ ” captures Landau’s pre-order of asymptotic growth “ $\operatorname{\textbf{P}}(\operatorname{\textbf{N}})=\mathcal{O}\big(% \operatorname{\textbf{Q}}(\operatorname{\textbf{N}})\big)$ ”; recall Lemma 4a). This suggests extending Equation (4) from ordinary to second-order polynomials:

Definition 9.

The (second-order) degree of a second-order polynomial $\boldsymbol{\Pi}$ in $\boldsymbol{\Phi}$ and $\vec{\operatorname{\textbf{N}}}=(\operatorname{\textbf{N}}_{1},\ldots,% \operatorname{\textbf{N}}_{m})$ is an arctic polynomial $\operatorname{Deg}\big(\boldsymbol{\Pi}\big)$ in $\operatorname{\textbf{D}}$ , given inductively by

	$\displaystyle\operatorname{Deg}(1)\;:=\;0,\quad\operatorname{Deg}(% \operatorname{\textbf{N}}_{m})\;:=\;1,\qquad\operatorname{Deg}(\boldsymbol{\Pi% }+\boldsymbol{\Xi})\;:=\;\max\{\operatorname{Deg}(\boldsymbol{\Pi}),% \operatorname{Deg}(\boldsymbol{\Xi})\},$
	$\displaystyle\operatorname{Deg}(P\cdot Q)\;:=\;\operatorname{Deg}(P)+% \operatorname{Deg}(Q),\quad\text{and}\quad\operatorname{Deg}\big(\boldsymbol{% \Phi}(\boldsymbol{\Pi})\big)\;:=\;\operatorname{\textbf{D}}\cdot\operatorname{% Deg}(\boldsymbol{\Pi})\enspace.$		(6)

We write “ $\operatorname{\textbf{D}}=\operatorname{Deg}(\boldsymbol{\Phi})$ ” to emphasize that first-order variable $\operatorname{\textbf{D}}$ in $\operatorname{Deg}(\boldsymbol{\Pi})$ corresponds to second-order argument $\boldsymbol{\Phi}$ in $\boldsymbol{\Pi}$ , particularly when later generalizing to several second-order variables; see Remark 13b+e).

Related work [16] had investigated linear second-order polynomials: defined by omitting/prohibiting multiplication from Definition 5 (but still allowing for addition $+$ and nesting $\boldsymbol{\Phi}$ ). These are precisely those having as degree an arctic polynomial without addition $+$ (but still with multiplication $\cdot$ and $\max$ ); recall that Definition 5 allows only the constant $1$ .

$\blacktriangleright$ Remark 10.

Definition 9 is well-defined, namely it respects syntactic equivalence (3): Arithmetical commutativity and associativity of $+$ and $\cdot$ translate to “arctic” commutativity and associativity of $\max()$ and $+$ , respectively; multiplication by $1$ translates to addition of $0$ ; and distributivity $\boldsymbol{\Pi}\cdot(\boldsymbol{\Xi}+\boldsymbol{\Lambda})\mathrel{\begin{% matrix}\includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2% svg.svg}\end{matrix}}\boldsymbol{\Pi}\cdot\boldsymbol{\Xi}+\boldsymbol{\Pi}% \cdot\boldsymbol{\Lambda}$ translates to

\operatorname{Deg}(\boldsymbol{\Pi})+\max\big\{\operatorname{Deg}(\boldsymbol{% \Xi}),\operatorname{Deg}(\boldsymbol{\Lambda})\big\}\;=\;\max\big\{% \operatorname{Deg}(\boldsymbol{\Pi})+\operatorname{Deg}(\boldsymbol{\Xi})\>,\>% \operatorname{Deg}(\boldsymbol{\Pi})+\operatorname{Deg}(\boldsymbol{\Lambda})% \big\}\enspace.

(7)

Reflecting that every ordinary polynomial is a fortiori also a second-order polynomial, Definition 9 extends the classical degree: $\operatorname{Deg}(\operatorname{\textbf{P}})=\deg(\operatorname{\textbf{P}})% \in\mathbb{N}$ for any (positive pure) multivariate first-order polynomial $\operatorname{\textbf{P}}\neq 0$ .

According to Lemma 4b), the degree $\operatorname{Deg}(\boldsymbol{\Pi})$ of a second-order polynomial induces an ordinary univariate polynomial $\lim\operatorname{Deg}(\boldsymbol{\Pi})$ – which we call $\boldsymbol{\Pi}$ ’s asymptotic degree.

Table 2: Stating “second-order polynomial growth” in various levels of detail.

Growing as …	Example
a given second-order polynomial $\boldsymbol{\Pi}=\boldsymbol{\Pi}(\boldsymbol{\Phi},\operatorname{\textbf{N}})$	(complicated) $\boldsymbol{\Pi}$ from Example 1
(some unspecified second-order polynomial) having a given arctic first-order polynomial as degree	(simpler) $\widetilde{\operatorname{\textbf{P}}}(\operatorname{\textbf{D}})$ from Example 1
(some unspecified second-order polynomial) having a given first-order polynomial as asymptotic degree	“ $15\operatorname{\textbf{D}}^{3}+2\operatorname{\textbf{D}}+4$ ” (Example 1)
(some unspecified second-order polynomial) having a given nesting depth according to Proposition 12d)	“ $3\!\in\!\mathbb{N}$ ” in Example 1
some unspecified second order polynomial	[15, Definition 3.2]

2.2 Second-Order Polynomial Compositions

Second-order polynomials naturally compose in two different ways, here denoted $\circ$ and $\star$ :

Definition 11.

Let $\boldsymbol{\Pi}=\boldsymbol{\Pi}(\boldsymbol{\Phi},\operatorname{\textbf{N}})$ and $\boldsymbol{\Xi}=\boldsymbol{\Xi}(\boldsymbol{\Phi},\operatorname{\textbf{N}})$ be univariate second-order polynomials. Define their compositions $\boldsymbol{\Pi}\circ\boldsymbol{\Xi}$ and $\boldsymbol{\Pi}\star\boldsymbol{\Xi}$ by structural induction as follows:

$\displaystyle 1\circ\boldsymbol{\Xi}\;:=\;1,\qquad$	$\displaystyle 1\star\boldsymbol{\Xi}\;:=\;1,$	$\displaystyle\qquad\operatorname{\textbf{N}}\circ\boldsymbol{\Xi}\;:=\;% \boldsymbol{\Xi},$	$\displaystyle\qquad\operatorname{\textbf{N}}\star\boldsymbol{\Xi}\;:=\;% \operatorname{\textbf{N}},$
$\displaystyle(\boldsymbol{\Pi}_{1}+\boldsymbol{\Pi}_{2})\circ\boldsymbol{\Xi}% \;:=$	$\displaystyle\;(\boldsymbol{\Pi}_{1}\circ\boldsymbol{\Xi})+(\boldsymbol{\Pi}_{% 2}\circ\boldsymbol{\Xi}),\qquad$	$\displaystyle(\boldsymbol{\Pi}_{1}+\boldsymbol{\Pi}_{2})\star\boldsymbol{\Xi}% \;:=$	$\displaystyle\;(\boldsymbol{\Pi}_{1}\star\boldsymbol{\Xi})+(\boldsymbol{\Pi}_{% 2}\star\boldsymbol{\Xi})$
$\displaystyle(\boldsymbol{\Pi}_{1}\cdot\boldsymbol{\Pi}_{2})\circ\boldsymbol{% \Xi}\;:=$	$\displaystyle\;(\boldsymbol{\Pi}_{1}\circ\boldsymbol{\Xi})\cdot(\boldsymbol{% \Pi}_{2}\circ\boldsymbol{\Xi}),\qquad$	$\displaystyle(\boldsymbol{\Pi}_{1}\cdot\boldsymbol{\Pi}_{2})\star\boldsymbol{% \Xi}\;:=$	$\displaystyle\;(\boldsymbol{\Pi}_{1}\star\boldsymbol{\Xi})\cdot(\boldsymbol{% \Pi}_{2}\star\boldsymbol{\Xi})$
$\displaystyle\boldsymbol{\Phi}(\boldsymbol{\Pi})\circ\boldsymbol{\Xi}\;:=$	$\displaystyle\;\boldsymbol{\Phi}(\boldsymbol{\Pi}\circ\boldsymbol{\Xi}),\qquad$	$\displaystyle\boldsymbol{\Phi}(\boldsymbol{\Pi})\star\boldsymbol{\Xi}\;:=$	$\displaystyle\;\boldsymbol{\Xi}\circ(\boldsymbol{\Pi}\star\boldsymbol{\Xi})$

$\boldsymbol{\Pi}\big(\boldsymbol{\Phi},\boldsymbol{\Xi}(\boldsymbol{\Phi},% \operatorname{\textbf{N}})\big):=\big(\boldsymbol{\Pi}\circ\boldsymbol{\Xi}% \big)(\boldsymbol{\Phi},\operatorname{\textbf{N}})$ essentially replaces in $\boldsymbol{\Pi}$ every occurrence of first-order variable $\operatorname{\textbf{N}}$ with $\boldsymbol{\Xi}(\boldsymbol{\Phi},\operatorname{\textbf{N}})$ ; and $\boldsymbol{\Pi}\big(\boldsymbol{\Xi}(\boldsymbol{\Phi},\cdot),\operatorname{% \textbf{N}}\big):=\big(\boldsymbol{\Pi}\star\boldsymbol{\Xi}\big)(\boldsymbol{% \Phi},\operatorname{\textbf{N}})$ replaces in $\boldsymbol{\Pi}$ every occurrence of second-order variable $\boldsymbol{\Phi}$ with $\boldsymbol{\Xi}(\boldsymbol{\Phi},\cdot)$ .
Note that $\boldsymbol{\Phi}(\operatorname{\textbf{N}})=\boldsymbol{\Phi}$ ; and $\operatorname{\textbf{P}}=\operatorname{\textbf{P}}\circ\operatorname{\textbf{% N}}$ for first-order polynomials $\operatorname{\textbf{P}}$ : justifying the common notation $\operatorname{\textbf{P}}=\operatorname{\textbf{P}}(\operatorname{\textbf{N}})$ . In the second-order case, there is no danger of confusing the notation $\boldsymbol{\Pi}=\boldsymbol{\Pi}(\boldsymbol{\Phi},\operatorname{\textbf{N}})$ with a composition, since the pair $(\boldsymbol{\Phi},\operatorname{\textbf{N}})$ is not a single second-order polynomial.

Like in the classical case, the notion of degree translates composition “ $\circ$ ” to multiplication “ $\cdot$ ”. The other kind “ $\star$ ” of composition, new to the second-order case, translates as ordinary composition “ $\circ$ ” of first-order (arctic) polynomials:

Proposition 12.

Fix univariate second-order polynomials $\boldsymbol{\Pi}=\boldsymbol{\Pi}(\boldsymbol{\Phi},\operatorname{\textbf{N}})$ and $\boldsymbol{\Xi}=\boldsymbol{\Xi}(\boldsymbol{\Phi},\operatorname{\textbf{N}})$ .

a)

$(\boldsymbol{\Pi}\circ\boldsymbol{\Xi})$ is again a second-order polynomial in $(\boldsymbol{\Phi},\operatorname{\textbf{N}})$ , with semantics $\overline{\big(\boldsymbol{\Pi}\circ\boldsymbol{\Xi}\big)}(\phi,n)=\overline{% \boldsymbol{\Pi}}\big(\phi,\overline{\boldsymbol{\Xi}}(\phi,n)\big)$ for all $n\in\mathbb{N}$ and all $\phi\in(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})$ . Furthermore

$\operatorname{Deg}\big(\boldsymbol{\Pi}\circ\boldsymbol{\Xi}\big)(% \operatorname{\textbf{D}})\;=\;\operatorname{Deg}\big(\boldsymbol{\Pi}\big)(% \operatorname{\textbf{D}})\;\cdot\;\operatorname{Deg}\big(\boldsymbol{\Xi}\big% )(\operatorname{\textbf{D}})\enspace.$
b)

$\big(\boldsymbol{\Pi}\star\boldsymbol{\Xi}\big)(\boldsymbol{\Phi},% \operatorname{\textbf{N}})$ is again a second-order polynomial in $(\boldsymbol{\Phi},\operatorname{\textbf{N}})$ , with semantics $\overline{\boldsymbol{\Pi}\big(\boldsymbol{\Xi}(\boldsymbol{\Phi},\cdot),% \operatorname{\textbf{N}}\big)}(\phi,n)=\overline{\boldsymbol{\Pi}}\big(% \overline{\boldsymbol{\Xi}}(\phi,\cdot),n\big)$ for $n\in\mathbb{N}$ and $\phi\in(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})$ . Here $\overline{\boldsymbol{\Xi}}(\phi,\cdot)\in(\mathbb{N}{\scriptstyle\nearrow}% \mathbb{N})$ denotes the monotonic mapping $\lambda n^{\prime}:\mathbb{N}.\overline{\boldsymbol{\Xi}}(\phi,n^{\prime})\in% \mathbb{N}$ . Furthermore

$\operatorname{Deg}\big(\boldsymbol{\Pi}\star\boldsymbol{\Xi}\big)(% \operatorname{\textbf{D}})\;=\;\big(\operatorname{Deg}(\boldsymbol{\Pi})\circ% \operatorname{Deg}(\boldsymbol{\Xi})\big)(\operatorname{\textbf{D}})\;=\;% \operatorname{Deg}\big(\boldsymbol{\Pi}\big)\big(\operatorname{Deg}(% \boldsymbol{\Xi})(\operatorname{\textbf{D}})\big)\enspace.$
c)

Moreover, if $\boldsymbol{\Xi}$ is an ordinary polynomial, then so is $\boldsymbol{\Pi}\star\boldsymbol{\Xi}$ . For $\boldsymbol{\Xi}_{m}\equiv m\in\mathbb{N}$ the family of constant ordinary polynomials, $\boldsymbol{\Pi}\star\boldsymbol{\Xi}_{M}$ is a bivariate polynomial in $(M,N)$ .
d)

$\deg\big(\lim\operatorname{Deg}(\boldsymbol{\Pi})\big)\in\mathbb{N}$ is well-defined, and coincides with the (nesting) depth of $\boldsymbol{\Phi}$ in $\boldsymbol{\Pi}$ according to [13, Definition 5.9].

The proofs proceed by straight-forward structural induction and are omitted.

$\blacktriangleright$ Remark 13.

a)

Proposition 12a) extends and recovers the first-order case, when $\boldsymbol{\Pi}$ and $\boldsymbol{\Xi}$ are ordinary polynomials. When $\boldsymbol{\Xi}=\operatorname{\textbf{Q}}$ is first-order, then $\operatorname{Deg}(\boldsymbol{\Pi}\circ\boldsymbol{\Xi})=\operatorname{Deg}(% \boldsymbol{\Pi})\cdot\deg(\operatorname{\textbf{Q}})$ : an integer multiple of $\operatorname{Deg}(\boldsymbol{\Pi})$ ; analogously when $\boldsymbol{\Pi}$ is first-order.
b)

In Proposition 12c), when $\boldsymbol{\Xi}=\operatorname{\textbf{Q}}$ is first-order, then $\operatorname{Deg}(\boldsymbol{\Pi}\star\boldsymbol{\Xi})=\operatorname{Deg}% \big(\boldsymbol{\Pi}\big)(\deg\operatorname{\textbf{Q}})$ : evaluating the arctic first-order polynomial $\operatorname{Deg}\big(\boldsymbol{\Pi}\big)(\operatorname{\textbf{D}})$ at the argument $\overline{\operatorname{\textbf{D}}}:=\deg(\operatorname{\textbf{Q}})\in% \mathbb{N}$ . This semantic coincidence justifies our syntactic convention “ $\operatorname{\textbf{D}}=\operatorname{Deg}(\boldsymbol{\Phi})$ ” at the end of Definition 9.
c)

Regarding Proposition 12d), recall Lemma 4b) that $\lim\operatorname{Deg}(\boldsymbol{\Pi})$ denotes the unique ordinary polynomial coinciding with arctic $\operatorname{Deg}(\boldsymbol{\Pi})$ on all sufficiently large arguments. In view of Proposition 12d), second-order polynomial asymptotic growth can be stated with various decreasing degrees of detail and increasing conciseness, as illustrated in Table 2.
d)

Regarding the multivariate case, Definition 9 already covers second-order polynomials involving several first-order variables $\vec{\operatorname{\textbf{N}}}=(\operatorname{\textbf{N}}_{1},\ldots,% \operatorname{\textbf{N}}_{M})$ . Composition “ $\boldsymbol{\Pi}\circ\boldsymbol{\Xi}$ ” then becomes “ $\boldsymbol{\Pi}\circ_{m}\boldsymbol{\Xi}$ ”: We refrain from spelling out the inductive replacement of $\operatorname{\textbf{N}}_{m}$ in $\boldsymbol{\Pi}$ with $\boldsymbol{\Xi}$ . Proposition 12a) adapts immediately – but of course not Lemma 4.
e)

Definition 5 naturally generalizes to several unary second-order variables $\boldsymbol{\Phi}_{m}$ . The degree (Definition 9) then becomes a multivariate arctic first-order polynomial: Replace Equation (6) with $\operatorname{Deg}\big(\boldsymbol{\Phi}_{m}(\boldsymbol{\Pi})\big):=% \operatorname{\textbf{D}}_{m}\cdot\operatorname{Deg}(\boldsymbol{\Pi})$ , where $\operatorname{\textbf{D}}_{m}=\operatorname{Deg}(\boldsymbol{\Phi}_{m})$ ; recall Item b). Composition “ $\boldsymbol{\Pi}\star\boldsymbol{\Xi}$ ” becomes “ $\boldsymbol{\Pi}\star_{m}\boldsymbol{\Xi}$ ”, and Proposition 12b) adapts accordingly.
f)

$\boldsymbol{\Pi}:=\boldsymbol{\Phi}^{2}(\operatorname{\textbf{N}}^{3})$ and $\boldsymbol{\Xi}:=\boldsymbol{\Phi}(\operatorname{\textbf{N}}^{6})$ both have same degree $6\operatorname{\textbf{D}}$ , but neither $\overline{\boldsymbol{\Pi}}\leq\mathcal{O}\big(\overline{\boldsymbol{\Xi}}\big)$ nor $\overline{\boldsymbol{\Xi}}\leq\mathcal{O}\big(\overline{\boldsymbol{\Pi}}\big)$ ; see also Example 19.

2.3 Examples and Applications

Polynomial bounds capture “tame” (as opposed to, say, exponential) growth in many areas:

$\blacksquare$

In classical Complexity Theory, $\operatorname{\textbf{P}}(\operatorname{\textbf{N}})$ denotes the amount of resources used to process inputs of length $\overline{\operatorname{\textbf{N}}}=n$ .
$\blacksquare$

In Geometric Group Theory, $\operatorname{\textbf{P}}(\operatorname{\textbf{N}})$ denotes the number of distinct group elements expressible by words of length $\overline{\operatorname{\textbf{N}}}=n$ over a fixed symmetric set of generators [9].
$\blacksquare$

In statistical physics / probability theory, $\operatorname{\textbf{P}}(\operatorname{\textbf{N}})$ denotes the mixing time of a dynamical system or stochastic process over a $2^{\operatorname{\textbf{N}}}$ element universe [19].

Generally, establishing polynomially bounded growth is followed by further investigating the (least) degree of said polynomial [29, 8, 6]. Recall (before Definition 9) that the integer total order on degrees captures Landau’s preorder of asymptotic growth.

The present work enables similarly refined analyses of higher-type problems: Extending the Cobham-Edmonds Thesis, asymptotic growth of a functional depending on (first-order $\overline{\operatorname{\textbf{N}}}$ and on) a second-order parameter $\overline{\boldsymbol{\Phi}}$ is commonly considered “tame” iff it is bounded by (the values of) some second-order polynomial $\boldsymbol{\Pi}=\boldsymbol{\Pi}(\boldsymbol{\Phi},\operatorname{\textbf{N}})$ . And its degree $\operatorname{Deg}(\boldsymbol{\Pi})$ captures, and allows to concisely compare, second-order asymptotic growth; recall Remark 13c) and see Table 2. When its argument $\overline{\boldsymbol{\Phi}}$ itself grows exponentially, then $\boldsymbol{\Pi}(\boldsymbol{\Phi},\operatorname{\textbf{N}})$ as a relative polynomial bound [24, §4] may grow like an exponential tower of height $\deg\big(\lim\operatorname{Deg}(\boldsymbol{\Pi})\big)$ , recall Proposition 12d). We collect here some old and new examples, proofs in Appendix B.

Example 14 (String Functionals).

i)

Suppose traditional Turing machine $\mathcal{M}$ computes function $f:\{\textup{{0}},\textup{{1}}\}^{*}\to\{\textup{{0}},\textup{{1}}\}^{*}$ in polynomial time $\operatorname{\textbf{P}}=\operatorname{\textbf{P}}(\operatorname{\textbf{M}})$ and machine $\mathcal{N}$ computes $g:\{\textup{{0}},\textup{{1}}\}^{*}\to\{\textup{{0}},\textup{{1}}\}^{*}$ in polynomial time $\operatorname{\textbf{Q}}=\operatorname{\textbf{Q}}(\operatorname{\textbf{N}})$ . Then executing $\mathcal{M}$ on input $\vec{y}=g(\vec{x})$ of length $m\leq\operatorname{\textbf{Q}}(n)$ , obtained by executing $\mathcal{N}$ on input $\vec{x}$ , results in a Turing machine computing $f\circ g$ in total running time $\mathcal{O}\Big(\operatorname{\textbf{Q}}(\operatorname{\textbf{N}})+% \operatorname{\textbf{P}}\big(\operatorname{\textbf{Q}}(\operatorname{\textbf{% N}})\big)\Big)$ : a polynomial of degree $\max\{\deg(\operatorname{\textbf{Q}}),\deg(\operatorname{\textbf{P}})\cdot\deg% (\operatorname{\textbf{Q}})\}=\deg(\operatorname{\textbf{P}})\cdot\deg(% \operatorname{\textbf{Q}})$ for non-constant $\operatorname{\textbf{P}}$ . This simple observation appears ubiquitously, often implicitly.
ii)

An oracle Turing machine $\mathcal{M}^{?}$ computing $F=F(\varphi,\vec{x})$ is said [13] to run in second-order polynomial time $\boldsymbol{\Pi}(\boldsymbol{\Phi},\operatorname{\textbf{N}})$ if the following holds: On input of any string $\vec{x}\in\{\textup{{0}},\textup{{1}}\}^{*}$ and for any string function oracle $\varphi:\{\textup{{0}},\textup{{1}}\}^{*}\to\{\textup{{0}},\textup{{1}}\}^{*}$ , $\mathcal{M}^{\varphi}(\vec{x})$ outputs $F(\varphi,\vec{x})$ and makes at most $\boldsymbol{\Pi}(|\varphi|,|\vec{x}|)$ steps, where $|\varphi|(m)\;:=\;\max\big\{|\varphi(\vec{b})|:|\vec{b}|\leq m\big\}$ .
iii)

Similarly to (i), let us analyze the running time of oracle Turing machine composition in (iv)+(v). Indeed, second-order string functionals naturally compose in two distinct ways, similarly to second-order polynomials in Subsection 2.2: For $F,G:(\{\textup{{0}},\textup{{1}}\}^{*})^{\{\textup{{0}},\textup{{1}}\}^{*}}% \times\{\textup{{0}},\textup{{1}}\}^{*}\to\{\textup{{0}},\textup{{1}}\}^{*}$ , let $F\circ G\;\equiv\;\lambda\varphi.\lambda\vec{x}.\;F\big(\varphi,G(\varphi,\vec% {x})\big)$ and $F\star G\;\equiv\;\lambda\varphi.\lambda\vec{x}.\;F\big(G(\varphi,\cdot),\vec{% x}\big)$ , where $G(\varphi,\cdot)\;\equiv\;\lambda\vec{y}.G(\varphi,\vec{y})$ .
iv)

Let $\mathcal{M}^{?}$ and $\mathcal{N}^{?}$ denote oracle Turing machines computing $F$ and $G$ , respectively, in second-order running time bounds $\boldsymbol{\Pi}=\boldsymbol{\Pi}(\boldsymbol{\Psi},\operatorname{\textbf{M}})$ and $\boldsymbol{\Xi}=\boldsymbol{\Xi}(\boldsymbol{\Phi},\operatorname{\textbf{N}})$ . Then $F\circ G$ can be computed by an oracle Turing machine in second-order polynomial time $\mathcal{O}\big(\boldsymbol{\Xi}+\boldsymbol{\Pi}\circ\boldsymbol{\Xi}\big)$ of degree $\max\big\{\operatorname{Deg}(\boldsymbol{\Xi}),\operatorname{Deg}(\boldsymbol{% \Pi})\cdot\operatorname{Deg}(\boldsymbol{\Xi})\big\}=\operatorname{Deg}(% \boldsymbol{\Pi})\cdot\operatorname{Deg}(\boldsymbol{\Xi})$ for non-constant $\boldsymbol{\Xi}$ .
v)

Let $\mathcal{M}^{?},\mathcal{N}^{?}$ and $F, G$ and $\boldsymbol{\Pi},\boldsymbol{\Xi}$ be as in (iv). Then $F\star G$ can be computed by an oracle Turing machine in second-order polynomial time $\mathcal{O}\Big(\big(\boldsymbol{\Pi}\star\boldsymbol{\Xi}\big)\>\cdot\>\big(% \boldsymbol{\Xi}\circ(\boldsymbol{\Pi}\star\boldsymbol{\Xi})\big)\Big)$ of degree $\operatorname{Deg}(\boldsymbol{\Pi})\circ\operatorname{Deg}(\boldsymbol{\Xi})% \>+\>\operatorname{Deg}(\boldsymbol{\Xi})\cdot\big(\operatorname{Deg}(% \boldsymbol{\Pi})\circ\operatorname{Deg}(\boldsymbol{\Xi})\big)$ .
vi)

[14] designs and analyzes running times of oracle Turing machines computing certain other mixed functionals $H:(\{\textup{{0}},\textup{{1}}\}^{*})^{\{\textup{{0}},\textup{{1}}\}^{*}}% \times\{\textup{{0}},\textup{{1}}\}^{*}\to\{\textup{{0}},\textup{{1}}\}^{*}$ . Specifically, [14, Proposition 2.8] establishes a time bound $\big(\operatorname{\textbf{P}}\circ\boldsymbol{\Phi}\big)^{[r]}(\operatorname{% \textbf{P}}(\operatorname{\textbf{N}}))\;+\operatorname{\textbf{P}}(% \operatorname{\textbf{N}})$ , where $\operatorname{\textbf{P}}\in\mathbb{N}[N]$ denotes some (unspecified, cf.Table 2) ordinary polynomial and $r\in\mathbb{N}$ indicates how often to iterate $\operatorname{\textbf{P}}\circ\boldsymbol{\Phi}$ . The degree of the this second-order polynomial is $\operatorname{\textbf{D}}^{r}\cdot\big(\deg(\operatorname{\textbf{P}})\big)^{r% +1}=\mathcal{O}(\operatorname{\textbf{D}})^{r}$ . $\lrcorner$

The second-order running time bound in Example 14vi) is already rather concise to begin with, hence here considering its second-order degree does not yield as much further simplification as in, say, Example 1. Asymptotic growth w.r.t. $\operatorname{\textbf{N}}\to\infty$ of a second-order polynomial depends additionally on that of its second-order argument $\overline{\boldsymbol{\Phi}}$ , and the second-order degree captures both: cf. Remark 13. In Example 14, the second-order parameter $\overline{\boldsymbol{\Phi}}=|\varphi|:\mathbb{N}{\scriptstyle\nearrow}\mathbb% {N}$ measures the “size” of function-type argument $\varphi:\{\textup{{0}},\textup{{1}}\}^{*}\to\{\textup{{0}},\textup{{1}}\}^{*}$ . Other applications, like in Examples 14 above and 17 below, assign other meanings to the second-order parameter:

Example 15.

a)

To any continuous real function $f:[0;1]\to\mathbb{R}$ (as argument to an operator in Analysis, say) assign as size its modulus of uniform continuity [17, Definition 2.12]: $\mu:\mathbb{N}{\scriptstyle\nearrow}\mathbb{N}$ pointwise minimal such that $|x-x^{\prime}|\leq 2^{-\mu(n)}\;\Rightarrow\;|f(x)-f(x^{\prime})|\leq 2^{-n}$ .
b)

To any pre-compact metric space $(X,d)$ assign as size its Kolmogorov entropy [23]: $\eta:\mathbb{N}{\scriptstyle\nearrow}\mathbb{N}$ pointwise minimal such that there exist $2^{\eta(n)}$ balls of radius $2^{-n}$ covering $X$ .
c)

For $p\geq 1$ , to any $p$ -summable sequence $\bar{z}$ assign as size its modulus of convergence: $\sigma:\mathbb{N}{\scriptstyle\nearrow}\mathbb{N}$ pointwise minimal such that $2^{-np}\geq\sum\nolimits_{K\geq 2^{\sigma(n)}}|z_{K}|^{p}$ .
d)

These and more second-order “size” parameters $\overline{\boldsymbol{\Phi}}$ arise generically from Skolemizing classical $\forall\exists$ statements [4]. We consider moduli as mappings from/to integer exponents w.r.t. base two, see [22, §2.4] and cf. [3, p.186]. $\lrcorner$

Example 16 (1D Real Function Inversion).

Recall Example 15a) and record [17, Theorem 2.19] that any polynomial-time computable bijection $f:[0;1]\to[0;1]$ has a polynomial modulus of uniform continuity; and its inverse $f^{-1}$ is again polynomial-time computable – provided that it, too, admits a polynomial modulus of continuity [17, Corollary 4.7].

More generally and more precisely, let $\mathcal{C}_{{\mu},{\nu}}[0;1]$ denote the set of bijections $f:[0;1]\to[0;1]$ having modulus $\leq\mu$ and whose inverse $f^{-1}$ has modulus $\leq\nu$ . Note that $f^{-1}\circ f=\operatorname{id}$ : the identity on $\mathbb{N}$ , with modulus $\operatorname{id}\leq\mu\circ\nu$ and similarly $\nu\circ\mu(n)\geq n$ .

i)

By the proof of [17, Theorem 4.6], there exists an oracle Turing machine computing the family of inversion operators $\lambda f:\mathcal{C}_{{\mu},{\nu}}[0;1].\;f^{-1}:\mathcal{C}_{{\mu},{\nu}}[0;1]$ in time $\mathcal{O}\Big({\mu}\big({\nu}(n)\big)+3\Big)^{2}$ : a second-order polynomial in first-order variable¹¹1The kind reader may generously forgive us for relaxing the distinction between syntax and semantics. $n$ and in two independent second-order variables $\mu$ and $\nu$ . This polynomial has degree $2\operatorname{\textbf{E}}\operatorname{\textbf{F}}$ : a bivariate first-order polynomial in $\operatorname{\textbf{E}}=\operatorname{Deg}(\mu)$ and $\operatorname{\textbf{F}}=\operatorname{Deg}(\nu)$ according to Remark 13e).
ii)

Trisection (Appendix A) yields another oracle Turing machine computing the same family of inversion operators in time $\mathcal{O}\Big(n\cdot{\nu}(n+3)\>+\>n\cdot{\mu}\big(3+{\nu}(n+3)\big)\Big)$ : a second-order polynomial of degree $\max\{1+\operatorname{\textbf{F}},1+\operatorname{\textbf{E}}\operatorname{% \textbf{F}}\}\leq\max\{\operatorname{\textbf{E}}\operatorname{\textbf{F}}+% \operatorname{\textbf{F}},2\operatorname{\textbf{E}}\operatorname{\textbf{F}}\}$ since $\operatorname{\textbf{E}}\operatorname{\textbf{F}}=\operatorname{Deg}(\mu\star% \nu)\geq 1$ by the above considerations.
iii)

Combining $\mu$ and $\nu$ in the single second-order parameter $\phi:=\max\{{\mu},{\nu}\}$ , the runtime bound from (i) becomes $\mathcal{O}\Big(\phi\big(\phi(n)\big)+3\Big)^{2}$ of univariate degree $2\operatorname{\textbf{D}}^{2}$ in $\operatorname{\textbf{D}}=\operatorname{Deg}(\phi)$ ; the bound from (ii) becomes $\mathcal{O}\Big(n\cdot\phi\big(3+\phi(n+3)\big)\Big)$ of univariate degree $1+\operatorname{\textbf{D}}^{2}$ . $\lrcorner$

In Example 16, the degree captures concisely that Trisection (ii) is asymptotically more efficient – and thus preferable over – the algorithm from (i) whenever $\operatorname{\textbf{E}}\operatorname{\textbf{F}}>\operatorname{\textbf{F}}$ , i.e., when $\mu\circ\nu$ grows faster than $\nu$ .

Example 17 (Continuous Operator in Functional Analysis).

Fix $p,q\geq 1$ and recall that $\ell^{p}=\{\bar{z}:\sum_{k}|z_{k}|^{p}<\infty\}$ denotes the space of $p$ -summable complex sequences $\bar{z}=(z_{k})$ . Write $\ell_{R}^{p}\subseteq\ell^{p}$ for the sphere with radius $R>0$ , that is, the subset of those sequences having $p$ -norm $\|\bar{z}\|_{p}\leq R$ . For $\sigma:\mathbb{N}{\scriptstyle\nearrow}\mathbb{N}$ let furthermore $\ell_{R,\sigma}^{p}\subseteq\ell_{R}^{p}$ denote the subset of all sequences having modulus of convergence $\leq\sigma$ .

We record that $\ell_{R,\sigma}^{p}$ is compact and, conversely, any compact subset of $\ell^{p}$ is contained in $\ell_{R,\sigma}^{p}$ for some $R\in\mathbb{N}$ and some $\sigma:\mathbb{N}{\scriptstyle\nearrow}\mathbb{N}$ .

i)

Consider some continuous (but not necessarily linear) $\mathbb{O}:\ell_{1}^{p}\to\ell^{q}$ . By continuity, $\mathbb{O}$ maps compact subsets of $\ell^{p}$ to compact subsets of $\ell^{q}$ . In particular it maps every $\ell_{1,\sigma}^{p}$ to $\ell_{R,\tau}$ for some minimal $R=R(\sigma)\in\mathbb{N}$ and some minimal $\tau:\mathbb{N}{\scriptstyle\nearrow}\mathbb{N}$ which also depends on $\sigma$ . Let $\mathcal{F}=\mathcal{F}_{\mathbb{O}}:(\mathbb{N}{\scriptstyle\nearrow}\mathbb{% N})\to(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})$ denote the thus well-defined mapping $\lambda\sigma.\tau$ associated with $\mathbb{O}$ . Note that $\mathcal{F}$ is non-decreasing: $\sigma^{\prime}\leq\sigma$ implies $\tau^{\prime}\leq\tau$ . The case $p=2=q$ of continuous (linear) operators on Fourier series is particularly relevant [18, Remark 26].
ii)

The identity operator $\ell^{p}\to\ell^{p}$ has $\mathcal{F}\;\equiv\;\lambda\sigma.\sigma$ the identity. The “repetition” operator $\lambda\bar{z}=(z_{K})_{{}_{K}}:\ell^{1}.\;(z_{\lfloor K/2\rfloor})_{{}_{K}}:% \ell^{1}$ is linear and 2-Lipschitz and has $\mathcal{F}\;\equiv\;\lambda\sigma:(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N}% ).\;\big(\lambda n:\mathbb{N}.\sigma(n+1)+1\big):\mathbb{N}$ .
iii)

For any bijection (aka infinite permutation) $\pi:\mathbb{N}\to\mathbb{N}$ , the linear operator $\lambda\bar{z}=(z_{K})_{{}_{K}}:\ell^{p}.\;(z_{\pi^{-1}(K)})_{{}_{K}}:\ell^{p}$ is isometric. Its associated $\mathcal{F}=\mathcal{F}_{\pi}$ is bounded by a second-order polynomial iff $\displaystyle\forall m\>\forall M\!<\!2^{m}:\pi(M)\!<\!2^{q(m)}$ for some ordinary polynomial $q$ . $\lrcorner$

We close this subsection with some further, sporadic examples:

i)

[22, Example 2.23i] involves an expression $\sum_{m=0}^{n+1}\eta(m+1)$ , where $\eta$ denotes the Kolmogorov entropy from Example 15b). This expression in $(\eta,n)$ itself is not a second-order polynomial, but it is bounded by the second-order polynomial $(n+1+1)\cdot\eta(n+1+1)$ of degree $1+\operatorname{\textbf{D}}$ with convention $\operatorname{\textbf{D}}=\deg(\eta)$ .
ii)

[22, Corollary 3.6a] uses the expression $\mathcal{P}\circ\phi\circ\mathcal{P}$ , where $\mathcal{P}$ denotes the class of univariate ordinary polynomials. Its degree is $\mathcal{O}(\operatorname{\textbf{D}})$ ; here the constant hidden in $\mathcal{O}$ captures (the degrees of) the particular ordinary polynomials.
iii)

[3, §3] establishes rates of convergence, which turn out to be (bounded by) multivariate second-order polynomials $\boldsymbol{\Pi}$ in (certain first-order parameters and in) two second-order parameters $\eta$ and $\omega$ ; see [3, p.186 ll.8ff]. See also [1]…

2.4 Arctic Second-Order Polynomials

Definition 23d) below considers the degree of a third-order polynomial to be an arctic second-order polynomial.

Definition 18.

a)

Arctic second-order polynomials in first-order variables $\vec{\operatorname{\textbf{N}}}=(\operatorname{\textbf{N}}_{1},..\operatorname% {\textbf{N}}_{M})$ and one second-order variable $\boldsymbol{\Phi}$ are generated by

$\widetilde{\boldsymbol{\Pi}},\widetilde{\boldsymbol{\Xi}}\quad::=\quad 0\mid 1% \mid\operatorname{\textbf{N}}_{1}\mid\ldots\mid\operatorname{\textbf{N}}_{M}% \mid\widetilde{\boldsymbol{\Pi}}+\widetilde{\boldsymbol{\Xi}}\mid\widetilde{% \boldsymbol{\Pi}}\cdot\widetilde{\boldsymbol{\Xi}}\mid\boldsymbol{\Phi}(% \widetilde{\boldsymbol{\Pi}})\mid\max\big(\widetilde{\boldsymbol{\Pi}},% \widetilde{\boldsymbol{\Xi}}\big)\enspace.$

with obvious semantics similar to (non-arctic) second-order polynomials.

b)

Regarding syntactic equivalence, extend Rules (3) to $\max()$ capturing monotonicity:

	$\displaystyle\max\{\widetilde{\boldsymbol{\Pi}},\widetilde{\boldsymbol{\Xi}}\}% \mathrel{\begin{matrix}\includegraphics{dagpub-standalone-dagpub-svg-2026-02-0% 3-16-22-40.pdf2svg.svg}\end{matrix}}\max\{\widetilde{\boldsymbol{\Xi}},% \widetilde{\boldsymbol{\Pi}}\},\qquad\max\big\{\max\{\widetilde{\boldsymbol{% \Pi}},\widetilde{\boldsymbol{\Xi}}\},\widetilde{\boldsymbol{\Lambda}}\big\}% \mathrel{\begin{matrix}\includegraphics{dagpub-standalone-dagpub-svg-2026-02-0% 3-16-22-40.pdf2svg.svg}\end{matrix}}\max\big\{\widetilde{\boldsymbol{\Pi}},% \max\{\widetilde{\boldsymbol{\Xi}},\widetilde{\boldsymbol{\Lambda}}\}\big\},$		(8)
	$\displaystyle\widetilde{\boldsymbol{\Pi}}+\max\{\widetilde{\boldsymbol{\Xi}},% \widetilde{\boldsymbol{\Lambda}}\}\mathrel{\begin{matrix}\includegraphics{% dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\max% \{\widetilde{\boldsymbol{\Pi}}+\widetilde{\boldsymbol{\Xi}},\widetilde{% \boldsymbol{\Pi}}+\widetilde{\boldsymbol{\Lambda}}\},\quad\widetilde{% \boldsymbol{\Pi}}\cdot\max\{\widetilde{\boldsymbol{\Xi}},\widetilde{% \boldsymbol{\Lambda}}\}\mathrel{\begin{matrix}\includegraphics{dagpub-% standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\max\{% \widetilde{\boldsymbol{\Pi}}\cdot\widetilde{\boldsymbol{\Xi}},\widetilde{% \boldsymbol{\Pi}}\cdot\widetilde{\boldsymbol{\Lambda}}\},$
	$\displaystyle\max\{\widetilde{\boldsymbol{\Pi}},0\}\mathrel{\begin{matrix}% \includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}% \end{matrix}}\widetilde{\boldsymbol{\Pi}},\qquad\quad\big(\widetilde{% \boldsymbol{\Pi}}\mathrel{\begin{matrix}\includegraphics{dagpub-standalone-% dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\widetilde{\boldsymbol% {\Pi}}^{\prime}\;\wedge\;\widetilde{\boldsymbol{\Xi}}\mathrel{\begin{matrix}% \includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}% \end{matrix}}\widetilde{\boldsymbol{\Xi}}^{\prime}\big)\quad\Rightarrow\quad% \max\{\widetilde{\boldsymbol{\Pi}},\widetilde{\boldsymbol{\Xi}}\}\mathrel{% \begin{matrix}\includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-4% 0.pdf2svg.svg}\end{matrix}}\max\{\widetilde{\boldsymbol{\Pi}}^{\prime},% \widetilde{\boldsymbol{\Xi}}^{\prime}\}$

Lemma 4 about the asymptotic behaviour of arctic first-order polynomials does not extend to the second-order case:

Example 19.

Consider $\boldsymbol{\Pi}(\boldsymbol{\Phi},\operatorname{\textbf{N}}):=\boldsymbol{% \Phi}^{2}\big(\boldsymbol{\Phi}(\operatorname{\textbf{N}})\big)+\boldsymbol{% \Phi}\big(\boldsymbol{\Phi}(\operatorname{\textbf{N}}^{2})\big)$ and $\boldsymbol{\Xi}(\boldsymbol{\Phi},\operatorname{\textbf{N}}):=2\boldsymbol{% \Phi}\big(\boldsymbol{\Phi}^{2}(\operatorname{\textbf{N}})\big)$ . They both have the same degree $\operatorname{Deg}\big(\boldsymbol{\Pi}\big)(\operatorname{\textbf{D}})=2% \operatorname{\textbf{D}}^{2}=\operatorname{Deg}\big(\boldsymbol{\Xi}\big)(% \operatorname{\textbf{D}})$ . For all integers $a,c,d\geq 2$ and for all sufficiently large $n\in\mathbb{N}$ , they evaluate

\displaystyle\overline{\boldsymbol{\Pi}}\big(\lambda m.a\cdot m^{d}\>,\>n\big)% \;\mathbf{>}\;\overline{\boldsymbol{\Xi}}\big(\lambda m.a\cdot m^{d}\>,\>n\big% )\;\text{\nobreak\ but\nobreak\ }\;\displaystyle\overline{\boldsymbol{\Pi}}% \big(\lambda m.m^{d}+c\>,\>n\big)\;\mathbf{<}\;\overline{\boldsymbol{\Xi}}\big% (\lambda m.m^{d}+c\>,\>n\big).

In particular the arctic univariate second-order polynomial $\max\big\{\boldsymbol{\Pi}(\boldsymbol{\Phi},\operatorname{\textbf{N}}),% \boldsymbol{\Xi}(\boldsymbol{\Phi},\operatorname{\textbf{N}})\big\}$ cannot reasonably be said to “asymptotically” coincide with any ordinary second-order polynomial. $\lrcorner$

See Appendix B. Due to the semantic completeness Theorem 7, $\boldsymbol{\Pi}(\boldsymbol{\Phi},\operatorname{\textbf{N}})$ and $\boldsymbol{\Xi}(\boldsymbol{\Phi},\operatorname{\textbf{N}})$ are the only candidates for $\max\big\{\boldsymbol{\Pi}(\boldsymbol{\Phi},\operatorname{\textbf{N}}),% \boldsymbol{\Xi}(\boldsymbol{\Phi},\operatorname{\textbf{N}})\big\}$ to “asymptotically” coincide with.

3 Higher-Order Polynomials and Degrees

We now climb further up in the type hierarchy: by one step to the third-order case in Subsection 3.2, and then to the general case in Subsection 3.3. But first revisit and take a new perspective on the first and second-order case:

3.1 First and Second-Order Case Revisited

Section 2 had regarded compositions $\circ$ and $\star$ as operators on previously defined second-order polynomials, and the algebraic properties of these operators were consequences. This is the traditional perspective [13, 15]. In order to proceed to third and higher order polynomials, we now take a new but equivalent perspective on the same families of traditional first and second-order polynomials, considering compositions as part of their syntactic definition:

$\blacktriangleright$ Remark 20 (First-Order Polynomials, Revisited).

Note that the semantics of ordinary polynomials is based on “values”, namely starting with $1$ and $\overline{\operatorname{\textbf{N}}}\in\mathbb{N}$ and proceeding inductively via $+$ and $\cdot$ . Alternatively, ordinary polynomials can be considered as certain mappings

\overline{\operatorname{\textbf{P}}}=p\;\equiv\;\lambda\overline{\operatorname% {\textbf{N}}}:\mathbb{N}.\;\overline{\operatorname{\textbf{P}}}(\overline{% \operatorname{\textbf{N}}}):\mathbb{N}\enspace.

Here, $+$ and $\cdot$ are tacitly “overloaded” to denote pointwise addition and multiplication of functions instead of values.

a)

A univariate first-order polynomial in $\operatorname{\textbf{N}}$ is syntactically generated by the rules

$\operatorname{\textbf{P}},\operatorname{\textbf{Q}}\quad::=\quad 1\mid% \operatorname{\textbf{N}}\mid\operatorname{\textbf{P}}+\operatorname{\textbf{Q% }}\mid\operatorname{\textbf{P}}\cdot\operatorname{\textbf{Q}}\mid\operatorname% {\textbf{P}}\circ\operatorname{\textbf{Q}}\enspace.$
b)

The semantics of $\operatorname{\textbf{P}}$ is the canonical interpretation as map $\overline{\operatorname{\textbf{P}}}=p:\mathbb{N}\nearrow\mathbb{N}$ .
c)

Syntactic equivalence is generated by the Rules (3), together with these for $\circ$ :

$\displaystyle 1\circ\operatorname{\textbf{P}}\;\mathrel{\begin{matrix}% \includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}% \end{matrix}}\;1,\qquad\operatorname{\textbf{N}}\circ\operatorname{\textbf{P}}% \;\mathrel{\begin{matrix}\includegraphics{dagpub-standalone-dagpub-svg-2026-02% -03-16-22-40.pdf2svg.svg}\end{matrix}}\;\operatorname{\textbf{P}}\;\mathrel{% \begin{matrix}\includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-4% 0.pdf2svg.svg}\end{matrix}}\;\operatorname{\textbf{P}}\circ\operatorname{% \textbf{N}},\qquad(\operatorname{\textbf{P}}\circ\operatorname{\textbf{Q}})% \circ\operatorname{\textbf{R}}\;\mathrel{\begin{matrix}\includegraphics{dagpub% -standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\;% \operatorname{\textbf{P}}\circ(\operatorname{\textbf{Q}}\circ\operatorname{% \textbf{R}}),$

$\displaystyle(\operatorname{\textbf{P}}+\operatorname{\textbf{Q}})\circ% \operatorname{\textbf{R}}\;\mathrel{\begin{matrix}\includegraphics{dagpub-% standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\;(% \operatorname{\textbf{P}}\circ\operatorname{\textbf{R}})+(\operatorname{% \textbf{Q}}\circ\operatorname{\textbf{R}}),\qquad(\operatorname{\textbf{P}}% \cdot\operatorname{\textbf{Q}})\circ\operatorname{\textbf{R}}\;\mathrel{\begin% {matrix}\includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2% svg.svg}\end{matrix}}\;(\operatorname{\textbf{P}}\circ\operatorname{\textbf{R}% })\cdot(\operatorname{\textbf{R}}\circ\operatorname{\textbf{R}})$
d)

The degree of $\operatorname{\textbf{P}}$ is defined inductively by

$\displaystyle\deg(1)=0,\quad\deg(\operatorname{\textbf{N}})=1,\qquad\deg(% \operatorname{\textbf{P}}+\operatorname{\textbf{Q}})=\max\{\deg(\operatorname{% \textbf{P}}),\deg(\operatorname{\textbf{Q}})\},$

$\displaystyle\deg(\operatorname{\textbf{P}}\cdot\operatorname{\textbf{Q}})=% \deg(\operatorname{\textbf{P}})+\deg(\operatorname{\textbf{Q}}),\qquad\deg(% \operatorname{\textbf{P}}\circ\operatorname{\textbf{Q}})=\deg(\operatorname{% \textbf{P}})\cdot\deg(\operatorname{\textbf{Q}}).$

Well-definition follows from (c), together with Commutative/Associative/ Distributive Laws of $\max()$ captured in (h).
e)

For any first-order polynomial according to (a), there exists a syntactically equivalent first-order polynomial devoid of composition symbol $\circ$ .
f)

Every classical univariate polynomial (function) can be expressed in the form (a) with semantics (b). Conversely every polynomial according to (a) without composition symbol (e) amounts to a classical polynomial with same semantics.
g)

An arctic first-order polynomial in $\operatorname{\textbf{M}}$ is syntactically generated by the rules

$\widetilde{\operatorname{\textbf{P}}},\widetilde{\operatorname{\textbf{Q}}}% \quad::=\quad 0\mid 1\mid\operatorname{\textbf{M}}\mid\widetilde{\operatorname% {\textbf{P}}}+\widetilde{\operatorname{\textbf{Q}}}\mid\widetilde{% \operatorname{\textbf{P}}}\cdot\widetilde{\operatorname{\textbf{Q}}}\mid% \widetilde{\operatorname{\textbf{P}}}\circ\widetilde{\operatorname{\textbf{Q}}% }\mid\max\big(\widetilde{\operatorname{\textbf{P}}},\widetilde{\operatorname{% \textbf{Q}}}\big)\enspace.$
h)

Arctic syntactic rules extend (c) with: $\max\big\{0,\widetilde{\operatorname{\textbf{P}}}\big\}\mathrel{\begin{matrix}% \includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}% \end{matrix}}\widetilde{\operatorname{\textbf{P}}}$ , $0+\widetilde{\operatorname{\textbf{P}}}\mathrel{\begin{matrix}\includegraphics% {dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}% \widetilde{\operatorname{\textbf{P}}}$ , $0\cdot\widetilde{\operatorname{\textbf{P}}}\mathrel{\begin{matrix}% \includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}% \end{matrix}}0$ , $0\circ\widetilde{\operatorname{\textbf{P}}}\mathrel{\begin{matrix}% \includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}% \end{matrix}}0$ ,

	$\displaystyle\max\big\{\widetilde{\operatorname{\textbf{P}}},\widetilde{% \operatorname{\textbf{Q}}}\big\}\;\mathrel{\begin{matrix}\includegraphics{% dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\;% \max\big\{\widetilde{\operatorname{\textbf{Q}}},\widetilde{\operatorname{% \textbf{P}}}\big\},\quad\max\Big\{\widetilde{\operatorname{\textbf{P}}},\max% \big\{\widetilde{\operatorname{\textbf{Q}}},\widetilde{\operatorname{\textbf{R% }}}\big\}\Big\}\;\mathrel{\begin{matrix}\includegraphics{dagpub-standalone-% dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\;\max\Big\{\max\big\{% \widetilde{\operatorname{\textbf{P}}},\widetilde{\operatorname{\textbf{Q}}}% \big\},\widetilde{\operatorname{\textbf{R}}}\big\}\Big\},$
	$\displaystyle\widetilde{\operatorname{\textbf{P}}}+\max\big\{\widetilde{% \operatorname{\textbf{Q}}},\widetilde{\operatorname{\textbf{R}}}\big\}\>% \mathrel{\begin{matrix}\includegraphics{dagpub-standalone-dagpub-svg-2026-02-0% 3-16-22-40.pdf2svg.svg}\end{matrix}}\>\max\big\{\widetilde{\operatorname{% \textbf{P}}}+\widetilde{\operatorname{\textbf{Q}}},\widetilde{\operatorname{% \textbf{P}}}+\widetilde{\operatorname{\textbf{R}}}\big\},\quad\widetilde{% \operatorname{\textbf{P}}}\cdot\max\big\{\widetilde{\operatorname{\textbf{Q}}}% ,\widetilde{\operatorname{\textbf{R}}}\big\}\>\mathrel{\begin{matrix}% \includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}% \end{matrix}}\>\max\big\{\widetilde{\operatorname{\textbf{P}}}\cdot\widetilde{% \operatorname{\textbf{Q}}},\widetilde{\operatorname{\textbf{P}}}\cdot% \widetilde{\operatorname{\textbf{R}}}\big\}$
	$\displaystyle\widetilde{\operatorname{\textbf{P}}}\circ\max\big\{\widetilde{% \operatorname{\textbf{Q}}},\widetilde{\operatorname{\textbf{R}}}\big\}\mathrel% {\begin{matrix}\includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-% 40.pdf2svg.svg}\end{matrix}}\max\big\{\widetilde{\operatorname{\textbf{P}}}% \circ\widetilde{\operatorname{\textbf{Q}}},\widetilde{\operatorname{\textbf{P}% }}\circ\widetilde{\operatorname{\textbf{R}}}\big\},$
	$\displaystyle\big(\widetilde{\operatorname{\textbf{P}}}\mathrel{\begin{matrix}% \includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}% \end{matrix}}\widetilde{\operatorname{\textbf{P}}}^{\prime}\wedge\widetilde{% \operatorname{\textbf{Q}}}\mathrel{\begin{matrix}\includegraphics{dagpub-% standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\widetilde{% \operatorname{\textbf{Q}}}^{\prime}\big)\Rightarrow\max\big\{\widetilde{% \operatorname{\textbf{P}}},\widetilde{\operatorname{\textbf{Q}}}\big\}\mathrel% {\begin{matrix}\includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-% 40.pdf2svg.svg}\end{matrix}}\max\big\{\widetilde{\operatorname{\textbf{P}}}^{% \prime},\widetilde{\operatorname{\textbf{Q}}}^{\prime}\big\}\qquad\qquad\qquad% \qquad\qquad\qquad\qquad\qquad\penalty 9999\hbox{}\nobreak\hfill\quad\hbox{$% \lrcorner$}$

Item e) follows from c) by structural induction, which also implies $\operatorname{\textbf{P}}\circ\operatorname{\textbf{Q}}\mathrel{\begin{matrix}% \includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}% \end{matrix}}\operatorname{\textbf{P}}^{\prime}\circ\operatorname{\textbf{Q}}^% {\prime}$ .

$\blacktriangleright$ Remark 21 (Second-Order Polynomials, Revisited).

Curry-ing (Schönfinkel-ing) suggests considering a second-order polynomial $\boldsymbol{\Pi}$ as family of first-order polynomials, parameterized by an additional variable $\boldsymbol{\Phi}$ ranging over $\phi\in(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})$ : $\displaystyle\overline{\boldsymbol{\Pi}}(\phi,\cdot)\;\equiv\;\;\lambda% \overline{\operatorname{\textbf{N}}}:\mathbb{N}.\;\overline{\boldsymbol{\Pi}}(% \phi,\overline{\operatorname{\textbf{N}}}):\mathbb{N}$ .
Second-order polynomials can alternatively be interpreted as operators $(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\nearrow(\mathbb{N}{\scriptstyle% \nearrow}\mathbb{N})$ :

\overline{\boldsymbol{\Pi}}\;\equiv\;\lambda\phi:(\mathbb{N}{\scriptstyle% \nearrow}\mathbb{N}).\;\big(\lambda n:\mathbb{N}.\overline{\boldsymbol{\Pi}}(% \phi,n)\big):(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\enspace.

Let us re-introduce $\star$ to denote the composition of operators, $\circ$ for composition of functions.

a)

A univariate second-order polynomial in $(\boldsymbol{\Phi},\operatorname{\textbf{N}})$ is syntactically generated by

$\boldsymbol{\Pi},\boldsymbol{\Xi}\quad::=\quad 1\mid\operatorname{\textbf{N}}% \mid\boldsymbol{\Phi}\mid\boldsymbol{\Pi}+\boldsymbol{\Xi}\mid\boldsymbol{\Pi}% \cdot\boldsymbol{\Xi}\mid\boldsymbol{\Pi}\circ\boldsymbol{\Xi}\mid\boldsymbol{% \Pi}\star\boldsymbol{\Xi}\enspace.$

b)

The semantics is given as follows, subject to implicit Curry-ing:

	$\displaystyle\overline{1}\;\;\equiv\;\;\lambda\phi:(\mathbb{N}{\scriptstyle% \nearrow}\mathbb{N}).\;\lambda n:\mathbb{N}.\;\;1:\mathbb{N},\quad\overline{% \operatorname{\textbf{N}}}\;\equiv\;\lambda\phi.\lambda n.\;n:\mathbb{N},$
	$\displaystyle\overline{\boldsymbol{\Phi}}\;\equiv\;\lambda\phi.\;\phi\in(% \mathbb{N}{\scriptstyle\nearrow}\mathbb{N}),\qquad\qquad\overline{\boldsymbol{% \Pi}+\boldsymbol{\Xi}}\quad\text{and}\quad\overline{\boldsymbol{\Pi}\cdot% \boldsymbol{\Xi}}\qquad\text{ pointwise}$
	$\displaystyle\overline{\boldsymbol{\Pi}\circ\boldsymbol{\Xi}}\;\equiv\;\lambda% \phi.\lambda n.\;\overline{\boldsymbol{\Pi}}\big(\phi,\overline{\boldsymbol{% \Xi}}(\phi,n)\big):\mathbb{N},\qquad\overline{\boldsymbol{\Pi}\star\boldsymbol% {\Xi}}\;\equiv\;\lambda\phi:(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N}).\;% \overline{\boldsymbol{\Pi}}\big(\overline{\boldsymbol{\Xi}}(\phi)\big):(% \mathbb{N}{\scriptstyle\nearrow}\mathbb{N})$

c)

Regarding syntactic equivalence we record, in addition to Remark 20c):

	$\displaystyle 1\star\boldsymbol{\Pi}\mathrel{\begin{matrix}\includegraphics{% dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}1,% \quad\operatorname{\textbf{N}}\star\boldsymbol{\Pi}\mathrel{\begin{matrix}% \includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}% \end{matrix}}\operatorname{\textbf{N}},\quad\boldsymbol{\Phi}\star\boldsymbol{% \Pi}\mathrel{\begin{matrix}\includegraphics{dagpub-standalone-dagpub-svg-2026-% 02-03-16-22-40.pdf2svg.svg}\end{matrix}}\boldsymbol{\Pi}\mathrel{\begin{matrix% }\includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg% }\end{matrix}}\boldsymbol{\Pi}\star\boldsymbol{\Phi},\quad(\boldsymbol{\Pi}+% \boldsymbol{\Xi})\star\boldsymbol{\Lambda}\mathrel{\begin{matrix}% \includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}% \end{matrix}}(\boldsymbol{\Pi}\star\boldsymbol{\Lambda})+(\boldsymbol{\Xi}% \star\boldsymbol{\Lambda})$
	$\displaystyle(\boldsymbol{\Pi}\cdot\boldsymbol{\Xi})\star\boldsymbol{\Lambda}% \mathrel{\begin{matrix}\includegraphics{dagpub-standalone-dagpub-svg-2026-02-0% 3-16-22-40.pdf2svg.svg}\end{matrix}}(\boldsymbol{\Pi}\star\boldsymbol{\Lambda}% )\cdot(\boldsymbol{\Xi}\star\boldsymbol{\Lambda}),\qquad(\boldsymbol{\Pi}\circ% \boldsymbol{\Xi})\star\boldsymbol{\Lambda}\mathrel{\begin{matrix}% \includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}% \end{matrix}}(\boldsymbol{\Pi}\star\boldsymbol{\Lambda})\circ(\boldsymbol{\Xi}% \star\boldsymbol{\Lambda})$
	$\displaystyle\big(\boldsymbol{\Pi}\mathrel{\begin{matrix}\includegraphics{% dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}% \boldsymbol{\Pi}^{\prime}\;\wedge\;\boldsymbol{\Xi}\mathrel{\begin{matrix}% \includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}% \end{matrix}}\boldsymbol{\Xi}^{\prime}\big)\quad\Rightarrow\quad\boldsymbol{% \Pi}\circ\boldsymbol{\Xi}\mathrel{\begin{matrix}\includegraphics{dagpub-% standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\boldsymbol% {\Pi}^{\prime}\circ\boldsymbol{\Xi}^{\prime}\enspace.$		(9)

d)

The degree of $\boldsymbol{\Pi}=\boldsymbol{\Pi}(\boldsymbol{\Phi},\operatorname{\textbf{N}})$ is an arctic first-order polynomial in variable $\operatorname{\textbf{D}}=\operatorname{Deg}(\boldsymbol{\Phi})$ , defined inductively as in Remark 20d) and, additionally, $\operatorname{Deg}(\boldsymbol{\Pi}\star\boldsymbol{\Xi})=\operatorname{Deg}(% \boldsymbol{\Pi})\circ\operatorname{Deg}(\boldsymbol{\Xi})$ .
e)

To any 2nd-order polynomial $\boldsymbol{\Pi}$ according to (a) there is a syntactically equivalent one
(i) devoid of composition symbol $\star$ and (ii) whenever $\circ$ occurs, its left argument is $\boldsymbol{\Phi}$ .
f)

Any second-order polynomial according to Definition 5 can be expressed in the form (a) with semantics (b). Conversely any polynomial according to (a) satisfying (i)+(ii) from (e) amounts to a 2nd-order polynomial according to Definition 5 with same semantics.
g)

An arctic univariate second-order polynomial in $(\boldsymbol{\Psi},\operatorname{\textbf{M}})$ is syntactically generated by

$\widetilde{\boldsymbol{\Pi}},\widetilde{\boldsymbol{\Xi}}\quad::=\quad 0\mid 1% \mid\operatorname{\textbf{M}}\mid\boldsymbol{\Psi}\mid\widetilde{\boldsymbol{% \Pi}}+\widetilde{\boldsymbol{\Xi}}\mid\widetilde{\boldsymbol{\Pi}}\cdot% \widetilde{\boldsymbol{\Xi}}\mid\widetilde{\boldsymbol{\Pi}}\circ\widetilde{% \boldsymbol{\Xi}}\mid\widetilde{\boldsymbol{\Pi}}\star\widetilde{\boldsymbol{% \Xi}}\mid\max\big(\widetilde{\boldsymbol{\Pi}},\widetilde{\boldsymbol{\Xi}}% \big)\enspace.$
h)

Arctic syntactic rules extend (c), Remark 20h), and (8) in Definition 18b) with:
$\widetilde{\boldsymbol{\Pi}}\star\max\big\{\widetilde{\boldsymbol{\Xi}},% \widetilde{\boldsymbol{\Lambda}}\big\}\mathrel{\begin{matrix}\includegraphics{% dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\max% \big\{\widetilde{\boldsymbol{\Pi}}\star\widetilde{\boldsymbol{\Xi}},\widetilde% {\boldsymbol{\Pi}}\star\widetilde{\boldsymbol{\Lambda}}\big\}$ . $\lrcorner$

Items e+f) record that this new perspective coincides with Definition 5. Note that now both $\boldsymbol{\Phi}$ and $\operatorname{\textbf{N}}$ are of type $(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})$ but, other than for composition “ $\star$ ”, the type of its two arguments tacitly gets Curry-ed for composition “ $\circ$ ”; and Proposition 12 is now axiomatized in Item d). Again, Item e) follows from structural induction using Item c), and implies congruence w.r.t. $\star$ ; but congruence w.r.t. $\circ$ now needs to be postulated as Rule (9). Regarding the first part of Item f), rewrite $\boldsymbol{\Phi}(\boldsymbol{\Pi})$ as $\boldsymbol{\Phi}\circ\boldsymbol{\Pi}$ . Second-order polynomials according to Remark 21 use brackets only to express priority, not anymore to express “application”.

3.2 Third-Order Polynomials and Degrees

Second-order polynomials describe “tame” dependencies on both integer arguments $n\in\mathbb{N}$ and integer function arguments $\phi:\mathbb{N}\nearrow\mathbb{N}$ . Third-order polynomials should additionally take into account dependency on integer operator arguments $\mathcal{F}:(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\nearrow(\mathbb{N}{% \scriptstyle\nearrow}\mathbb{N})$ . Recall Example 17 where continuous operators between Banach spaces give rise to all possible such $\mathcal{F}$ . In addition to variable $\operatorname{\textbf{N}}$ ranging over $\mathbb{N}$ and $\boldsymbol{\Phi}$ ranging over $(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})$ , now introduce indeterminate $\boldsymbol{\mathfrak{F}}$ to range over the set $\big((\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\nearrow(\mathbb{N}{% \scriptstyle\nearrow}\mathbb{N})\big)$ of total monotonic integer operators.

$\blacktriangleright$ Remark 22.

Curry-ing respects monotonicity: $f:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ is non-decreasing iff $f:\mathbb{N}\to(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})$ is non-decreasing and well-defined regarding its co-domain. Write $f:\mathbb{N}\nearrow\mathbb{N}\nearrow\mathbb{N}$ .

A third-order polynomial can thus be considered as a certain family of monotonic first-order polynomials, parameterized monotonically by two variables $\boldsymbol{\Phi}$ and $\boldsymbol{\mathfrak{F}}$ that range over second-order and third-order arguments $\phi\in(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})$ and $\mathcal{F}\in\big((\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\nearrow(% \mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\big)$ , respectively; or alternatively as a family of monotonic second-order polynomials, parameterized monotonically by $\mathcal{F}$ ; or as monotonic “hyper”-operator of type $\big((\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\nearrow(\mathbb{N}{% \scriptstyle\nearrow}\mathbb{N})\big)\nearrow\big((\mathbb{N}{\scriptstyle% \nearrow}\mathbb{N})\nearrow(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\big)$ . We introduce $\#$ to denote the composition of such hyper-operators.

After first and second-order Remarks 20 and 21, the following Definition 23 and Theorem 25 about third-order polynomials and their degrees follow naturally:

Definition 23.

a)

A third-order polynomial in $(\boldsymbol{\mathfrak{F}},\boldsymbol{\Phi},\operatorname{\textbf{N}})$ is syntactically generated by

$\boldsymbol{\mathfrak{P}},\boldsymbol{\mathfrak{Q}}\quad::=\quad 1\mid% \operatorname{\textbf{N}}\mid\boldsymbol{\Phi}\mid\boldsymbol{\mathfrak{F}}% \mid\boldsymbol{\mathfrak{P}}+\boldsymbol{\mathfrak{Q}}\mid\boldsymbol{% \mathfrak{P}}\cdot\boldsymbol{\mathfrak{Q}}\mid\boldsymbol{\mathfrak{P}}\circ% \boldsymbol{\mathfrak{Q}}\mid\boldsymbol{\mathfrak{P}}\star\boldsymbol{% \mathfrak{Q}}\mid\boldsymbol{\mathfrak{P}}\#\boldsymbol{\mathfrak{Q}}.$

b)

Its semantics is $\overline{\boldsymbol{\mathfrak{P}}\#\boldsymbol{\mathfrak{Q}}}\;\equiv\;% \lambda\mathcal{F}:\big((\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\nearrow(% \mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\big).\;\overline{\boldsymbol{% \mathfrak{P}}}\big(\overline{\boldsymbol{\mathfrak{Q}}}(\mathcal{F})\big):\big% ((\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\nearrow(\mathbb{N}{\scriptstyle% \nearrow}\mathbb{N})\big)$ ,

$\displaystyle\overline{1}$	$\displaystyle\equiv$	$\displaystyle\lambda\mathcal{F}:\big((\mathbb{N}{\scriptstyle\nearrow}\mathbb{% N})\nearrow(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\big).\lambda\phi:(% \mathbb{N}{\scriptstyle\nearrow}\mathbb{N}).\lambda n:\mathbb{N}.\;\;1:\mathbb% {N}$
$\displaystyle\overline{\operatorname{\textbf{N}}}$	$\displaystyle\equiv$	$\displaystyle\lambda\mathcal{F}:\big((\mathbb{N}{\scriptstyle\nearrow}\mathbb{% N})\nearrow(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\big).\lambda\phi:(% \mathbb{N}{\scriptstyle\nearrow}\mathbb{N}).\lambda n.\;\;n:\mathbb{N}$
$\displaystyle\overline{\boldsymbol{\Phi}}$	$\displaystyle\equiv$	$\displaystyle\lambda\mathcal{F}:\big((\mathbb{N}{\scriptstyle\nearrow}\mathbb{% N})\nearrow(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\big).\lambda\phi:(% \mathbb{N}{\scriptstyle\nearrow}\mathbb{N}).\;\;\phi:(\mathbb{N}{\scriptstyle% \nearrow}\mathbb{N})$
$\displaystyle\overline{\boldsymbol{\mathfrak{F}}}$	$\displaystyle\equiv$	$\displaystyle\lambda\mathcal{F}:\big((\mathbb{N}{\scriptstyle\nearrow}\mathbb{% N})\nearrow(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\big).\;\;\mathcal{F}:% \big((\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\nearrow(\mathbb{N}{% \scriptstyle\nearrow}\mathbb{N})\big)$

all of (or Curry-ed to) type $\big((\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\nearrow(\mathbb{N}{% \scriptstyle\nearrow}\mathbb{N})\big)\nearrow\big((\mathbb{N}{\scriptstyle% \nearrow}\mathbb{N})\nearrow(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\big)$ . Moreover

$\displaystyle\overline{\boldsymbol{\mathfrak{P}}+\boldsymbol{\mathfrak{Q}}}(% \mathcal{F},\phi,n)$	$\displaystyle=$	$\displaystyle\overline{\boldsymbol{\mathfrak{P}}}(\mathcal{F},\phi,n)+% \overline{\boldsymbol{\mathfrak{Q}}}(\mathcal{F},\phi,n)$
$\displaystyle\overline{\boldsymbol{\mathfrak{P}}\cdot\boldsymbol{\mathfrak{Q}}% }(\mathcal{F},\phi,n)$	$\displaystyle=$	$\displaystyle\overline{\boldsymbol{\mathfrak{P}}}(\mathcal{F},\phi,n)\cdot% \overline{\boldsymbol{\mathfrak{Q}}}(\mathcal{F},\phi,n)$
$\displaystyle\overline{\boldsymbol{\mathfrak{P}}\circ\boldsymbol{\mathfrak{Q}}% }(\mathcal{F},\phi,n)$	$\displaystyle=$	$\displaystyle\overline{\boldsymbol{\mathfrak{P}}}\big(\mathcal{F},\phi,% \overline{\boldsymbol{\mathfrak{Q}}}(\mathcal{F},\phi,n)\big)\;:\mathbb{N}$
$\displaystyle\overline{\boldsymbol{\mathfrak{P}}\star\boldsymbol{\mathfrak{Q}}% }(\mathcal{F},\phi)$	$\displaystyle=$	$\displaystyle\overline{\boldsymbol{\mathfrak{P}}}(\mathcal{F},\overline{% \boldsymbol{\mathfrak{Q}}}(\mathcal{F},\phi))\;:(\mathbb{N}{\scriptstyle% \nearrow}\mathbb{N})$

c)

In addition to Remark 20c) and Remark 21c), we have syntactic equivalence rules

	$\displaystyle 1\#\boldsymbol{\mathfrak{P}}\;\mathrel{\begin{matrix}% \includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}% \end{matrix}}\;1,\qquad\operatorname{\textbf{N}}\#\boldsymbol{\mathfrak{P}}\;% \mathrel{\begin{matrix}\includegraphics{dagpub-standalone-dagpub-svg-2026-02-0% 3-16-22-40.pdf2svg.svg}\end{matrix}}\;\operatorname{\textbf{N}},\qquad% \boldsymbol{\Phi}\#\boldsymbol{\mathfrak{P}}\;\mathrel{\begin{matrix}% \includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}% \end{matrix}}\;\boldsymbol{\Phi},\qquad\boldsymbol{\mathfrak{F}}\#\boldsymbol{% \mathfrak{P}}\;\mathrel{\begin{matrix}\includegraphics{dagpub-standalone-% dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\;\boldsymbol{% \mathfrak{P}}\;\mathrel{\begin{matrix}\includegraphics{dagpub-standalone-% dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\;\boldsymbol{% \mathfrak{P}}\#\boldsymbol{\mathfrak{F}}$
	$\displaystyle(\boldsymbol{\mathfrak{P}}\star\boldsymbol{\mathfrak{Q}})\#% \boldsymbol{\mathfrak{R}}\;\mathrel{\begin{matrix}\includegraphics{dagpub-% standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\;(% \boldsymbol{\mathfrak{P}}\#\boldsymbol{\mathfrak{R}})\star(\boldsymbol{% \mathfrak{Q}}\#\boldsymbol{\mathfrak{R}}),\qquad(\boldsymbol{\mathfrak{P}}% \circ\boldsymbol{\mathfrak{Q}})\#\boldsymbol{\mathfrak{R}}\;\mathrel{\begin{% matrix}\includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2% svg.svg}\end{matrix}}\;(\boldsymbol{\mathfrak{P}}\#\boldsymbol{\mathfrak{R}})% \circ(\boldsymbol{\mathfrak{Q}}\#\boldsymbol{\mathfrak{R}}),$
	$\displaystyle(\boldsymbol{\mathfrak{P}}+\boldsymbol{\mathfrak{Q}})\#% \boldsymbol{\mathfrak{R}}\;\mathrel{\begin{matrix}\includegraphics{dagpub-% standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\;(% \boldsymbol{\mathfrak{P}}\#\boldsymbol{\mathfrak{R}})+(\boldsymbol{\mathfrak{Q% }}\#\boldsymbol{\mathfrak{R}}),\qquad(\boldsymbol{\mathfrak{P}}\cdot% \boldsymbol{\mathfrak{Q}})\#\boldsymbol{\mathfrak{R}}\;\mathrel{\begin{matrix}% \includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}% \end{matrix}}\;(\boldsymbol{\mathfrak{P}}\#\boldsymbol{\mathfrak{R}})\cdot(% \boldsymbol{\mathfrak{Q}}\#\boldsymbol{\mathfrak{R}})$
	$\displaystyle\big(\boldsymbol{\mathfrak{P}}\;\mathrel{\begin{matrix}% \includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}% \end{matrix}}\;\boldsymbol{\mathfrak{P}}^{\prime}\;\;\wedge\;\;\boldsymbol{% \mathfrak{Q}}\;\mathrel{\begin{matrix}\includegraphics{dagpub-standalone-% dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\;\boldsymbol{% \mathfrak{Q}}^{\prime}\big)\quad\Rightarrow\quad\boldsymbol{\mathfrak{P}}\star% \boldsymbol{\mathfrak{Q}}\;\mathrel{\begin{matrix}\includegraphics{dagpub-% standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\;% \boldsymbol{\mathfrak{P}}^{\prime}\star\boldsymbol{\mathfrak{Q}}^{\prime}\enspace.$

d)

The degree of third-order polynomial $\boldsymbol{\mathfrak{P}}$ is an arctic second-order polynomial in first-order variable $\operatorname{\textbf{D}}=\operatorname{Deg}(\boldsymbol{\Phi})$ and second-order variable $\boldsymbol{\Psi}=\operatorname{DEG}(\mathcal{F})$ . It is defined inductively as in Remark 20d) and Remark 21d) and, additionally, $\operatorname{DEG}(\boldsymbol{\mathfrak{P}}\#\boldsymbol{\mathfrak{Q}}):=% \operatorname{DEG}(\boldsymbol{\mathfrak{P}})\star\operatorname{DEG}(% \boldsymbol{\mathfrak{Q}})$ .
e)

An arctic third-order polynomial in $(\boldsymbol{\mathfrak{G}},\boldsymbol{\Psi},\operatorname{\textbf{M}})$ is syntactically generated by

$\widetilde{\boldsymbol{\mathfrak{P}}},\widetilde{\boldsymbol{\mathfrak{Q}}}% \quad::=\quad 0\mid 1\mid\operatorname{\textbf{M}}\mid\boldsymbol{\Psi}\mid% \boldsymbol{\mathfrak{G}}\mid\widetilde{\boldsymbol{\mathfrak{P}}}+\widetilde{% \boldsymbol{\mathfrak{Q}}}\mid\widetilde{\boldsymbol{\mathfrak{P}}}\cdot% \widetilde{\boldsymbol{\mathfrak{Q}}}\mid\widetilde{\boldsymbol{\mathfrak{P}}}% \circ\widetilde{\boldsymbol{\mathfrak{Q}}}\mid\widetilde{\boldsymbol{\mathfrak% {P}}}\star\widetilde{\boldsymbol{\mathfrak{Q}}}\mid\widetilde{\boldsymbol{% \mathfrak{P}}}\#\widetilde{\boldsymbol{\mathfrak{Q}}}\mid\max\big(\widetilde{% \boldsymbol{\mathfrak{P}}},\widetilde{\boldsymbol{\mathfrak{Q}}}\big).$
f)

Syntactic rules extend (c) and Remark 21h) with $\widetilde{\boldsymbol{\Pi}}\#\max\big\{\widetilde{\boldsymbol{\Xi}},% \widetilde{\boldsymbol{\Lambda}}\big\}\mathrel{\begin{matrix}\includegraphics{% dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\max% \big\{\widetilde{\boldsymbol{\Pi}}\#\widetilde{\boldsymbol{\Xi}},\widetilde{% \boldsymbol{\Pi}}\#\widetilde{\boldsymbol{\Lambda}}\big\}$ .

Example 24.

a)

Consider the following third-order polynomial

$\boldsymbol{\mathfrak{P}}(\boldsymbol{\mathfrak{F}},\boldsymbol{\Phi},% \operatorname{\textbf{N}})\;\;:=\;\;\left(\boldsymbol{\mathfrak{F}}\star% \boldsymbol{\mathfrak{F}}^{4}\star\left(\boldsymbol{\Phi}^{2}\circ\boldsymbol{% \Phi}\circ\left(2\cdot\operatorname{\textbf{N}}^{6}+7\right)\right)\right)\;+% \;\left(\boldsymbol{\mathfrak{F}}^{3}\star\left(\boldsymbol{\Phi}\circ% \boldsymbol{\Phi}^{3}\circ\boldsymbol{\Phi}^{5}\circ\operatorname{\textbf{N}}^% {4}\right)\right)\enspace,$

where “ $\boldsymbol{\mathfrak{Q}}^{3}$ ” abbreviates $(\boldsymbol{\mathfrak{Q}}\cdot\boldsymbol{\mathfrak{Q}}\cdot\boldsymbol{% \mathfrak{Q}})$ . $\boldsymbol{\mathfrak{P}}$ has degree

$\operatorname{DEG}\big(\boldsymbol{\mathfrak{P}}\big)(\boldsymbol{\Psi},% \operatorname{\textbf{D}})\;=\;\max\big\{\boldsymbol{\Psi}\big(4\boldsymbol{% \Psi}(12\operatorname{\textbf{D}}^{2})\big)\>,\>3\boldsymbol{\Psi}(60% \operatorname{\textbf{D}}^{3})\big\}$

and semantics $\displaystyle\overline{\boldsymbol{\mathfrak{P}}}\;\equiv\;\;\lambda\mathcal{F% }.\;\lambda\phi.\;\;\mathcal{F}\big(\phi^{4}\big(\lambda n.\phi^{2}(\phi(2n^{6% }+7))\big)\big)\;+\;\mathcal{F}^{3}\big(\lambda n.\phi\big(\phi^{3}(\phi^{5}(n% ^{4}))\big)\big)$
b)

By Remark 30g) in Subsection 3.4 below, the following mapping of type $\big((\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\nearrow(\mathbb{N}{% \scriptstyle\nearrow}\mathbb{N})\big)\nearrow\big((\mathbb{N}{\scriptstyle% \nearrow}\mathbb{N})\nearrow(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\big)$ is not (the semantics of) a third-order polynomial:

$\lambda\mathcal{F}:\big((\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\nearrow(% \mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\big).\;\lambda\phi:(\mathbb{N}{% \scriptstyle\nearrow}\mathbb{N}).\;\lambda n:\mathbb{N}.\quad\mathcal{F}\big(% \lambda m:\mathbb{N}\;.4m^{3}+5\big)(n^{2}+n+1):\mathbb{N}$
c)

A first-order polynomial is a second-order polynomial $\boldsymbol{\Pi}(\boldsymbol{\Phi},\operatorname{\textbf{N}})$ which does not “depend” on $\boldsymbol{\Phi}$ , i.e., whose semantics of type $(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\nearrow(\mathbb{N}{\scriptstyle% \nearrow}\mathbb{N})$ is a constant of type $(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})$ ; recall Theorem 7. A second-order polynomial is a third-order polynomial whose semantics of type $\big((\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\nearrow(\mathbb{N}{% \scriptstyle\nearrow}\mathbb{N})\big)\nearrow\big((\mathbb{N}{\scriptstyle% \nearrow}\mathbb{N})\nearrow(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\big)$ is a constant of type $\big((\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\nearrow(\mathbb{N}{% \scriptstyle\nearrow}\mathbb{N})\big)$ . $\lrcorner$

Theorem 25.

a)

Every third-order polynomial as in Definition 23a) can be syntactically transformed, using Definition 23c), into an equivalent form in which (i) $\#$ does not occur; (ii) whenever $\star$ occurs, its left argument is $\boldsymbol{\mathfrak{F}}$ ; (iii) whenever $\circ$ occurs, its left argument is either $\boldsymbol{\mathfrak{F}}$ or $\boldsymbol{\Phi}$ or of the form $(\boldsymbol{\mathfrak{P}}\star\boldsymbol{\mathfrak{Q}})$ .
b)

The degree of third-order polynomials is well-defined, namely invariant under the syntactic congruence relations from Definition 23c)+e).

Example 26.

Consider the third-order polynomial $\boldsymbol{\mathfrak{P}}+\boldsymbol{\mathfrak{Q}}$ in $(\boldsymbol{\mathfrak{F}},\boldsymbol{\Psi},\operatorname{\textbf{D}})$

\boldsymbol{\mathfrak{P}}\;+\;\boldsymbol{\mathfrak{Q}}\;\;=\;\;\boldsymbol{% \mathfrak{F}}\star\boldsymbol{\mathfrak{F}}\star(\boldsymbol{\Psi}\circ% \boldsymbol{\Psi})\;+\;\boldsymbol{\mathfrak{F}}\star(\boldsymbol{\mathfrak{F}% }\circ\boldsymbol{\mathfrak{F}})\;\cdot\;(\boldsymbol{\mathfrak{F}}\star% \boldsymbol{\mathfrak{F}})\circ(\boldsymbol{\mathfrak{F}}\star\boldsymbol{% \mathfrak{F}})

with implicit default operator precedence $+$ after $\cdot$ after $\circ$ after $\star$ . Noting that $\boldsymbol{\mathfrak{F}}(\boldsymbol{\Psi})=\boldsymbol{\mathfrak{F}}$ , the semantics $\overline{\boldsymbol{\mathfrak{P}}+\boldsymbol{\mathfrak{Q}}}$ of $\boldsymbol{\mathfrak{P}}+\boldsymbol{\mathfrak{Q}}$ means mapping argument pairs $\psi:(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})$ and $\mathcal{F}:\big((\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\nearrow(\mathbb{% N}{\scriptstyle\nearrow}\mathbb{N})\big)$ to the value $\mathcal{F}\big(\mathcal{F}(\psi\circ\psi)\big)\;+\;\mathcal{F}\big(\mathcal{F% }(\psi)\circ\mathcal{F}(\psi)\big)\;\cdot\;\mathcal{F}\big(\mathcal{F}(\psi)% \big)\circ\mathcal{F}\big(\mathcal{F}(\psi)\big)$ . $\operatorname{DEG}(\boldsymbol{\mathfrak{P}}+\boldsymbol{\mathfrak{Q}})$ here coincides with the arctic second-order polynomial from Example 19.

3.3 Polynomials and Degrees of Arbitrary Order

Motivated by [11] and [10, §3.3.1], we are now ready to treat the general case:

Definition 27.

Let $\delta\in\mathbb{N}$ denote the order of the polynomials under consideration.

a)

With “ $\mathbb{N}\;^{\scriptscriptstyle\delta}\!\!\!\!\nearrow\mathbb{N}$ ” we abbreviate the type $\big(\mathbb{N}\;^{\scriptscriptstyle\delta\!-\!1\!}\!\!\!\!\nearrow\mathbb{N}% \big)\nearrow\big(\mathbb{N}\;^{\scriptscriptstyle\delta\!-\!1\!}\!\!\!\!% \nearrow\mathbb{N}\big)$ in case $\delta\geq 1$ ; “ $\mathbb{N}\;^{\scriptscriptstyle 0}\!\!\!\!\nearrow\mathbb{N}$ ” means $\mathbb{N}$ , and “ $\mathbb{N}\;^{\scriptscriptstyle-1}\!\!\!\!\nearrow\mathbb{N}$ ” is $\{1\}\subset\mathbb{N}$ . Let “ $\,{\overset{\scriptscriptstyle 0}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}$ ” mean multiplication “ $\cdot$ ” and $\,{\overset{\scriptscriptstyle-1}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}=+$ ” addition and, for $\delta\geq 1$ , “ $\,{\overset{\scriptscriptstyle\delta}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}$ ” denotes the typed composition $g\circ f$ of $f,g:\big(\mathbb{N}\;^{\scriptscriptstyle\delta}\!\!\!\!\nearrow\mathbb{N}\big)$ .
In the sequel, variable $\operatorname{\textbf{V}}^{(\delta)}$ ranges over values $\overline{\operatorname{\textbf{V}}}^{(\delta)}=V^{(\delta)}:\mathbb{N}\;^{% \scriptscriptstyle\delta\!-\!1\!}\!\!\!\!\nearrow\mathbb{N}$ ; $\operatorname{\textbf{V}}^{(0)}=1$ .
b)

Univariate order- $\delta$ polynomials in variables $(\!\operatorname{\textbf{V}}^{(\delta)},\ldots,\operatorname{\textbf{V}}^{(1)})$ are syntactically generated by

$\boldsymbol{\Pi},\boldsymbol{\Xi}\quad::=\quad 1\mid\operatorname{\textbf{V}}^% {(1)}\mid\cdots\mid\operatorname{\textbf{V}}^{(\delta)}\mid\boldsymbol{\Pi}+% \boldsymbol{\Xi}\mid\boldsymbol{\Pi}\cdot\boldsymbol{\Xi}\mid\boldsymbol{\Pi}% \,{\overset{\scriptscriptstyle 1}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}\>% \boldsymbol{\Xi}\mid\cdots\mid\boldsymbol{\Pi}\,{\overset{\scriptscriptstyle% \delta}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}\>\boldsymbol{\Xi}\enspace.$

c)

The semantics is $\overline{\boldsymbol{\Pi}}\;\;:\;\;\mathbb{N}\;^{\scriptscriptstyle\delta}\!% \!\!\!\nearrow\mathbb{N}\;\;=\;\;\big(\mathbb{N}\;^{\scriptscriptstyle\delta\!% -\!1}\!\!\!\!\nearrow\mathbb{N}\big)\nearrow\big(\mathbb{N}\;^{% \scriptscriptstyle\delta\!-\!1}\!\!\!\!\nearrow\mathbb{N}\big)$ , where

	$\displaystyle\overline{\operatorname{\textbf{V}}}^{(\delta)}$	$\displaystyle\;\equiv\;\big(\lambda V^{(\delta)}.\;V^{(\delta)}\big)\quad\cdots\quad$	$\displaystyle\overline{\operatorname{\textbf{V}}}^{(2)}$	$\displaystyle\;\equiv\;\big(\lambda V^{(\delta)}\ldots\lambda V^{(2)}.\;V^{(2)% }\big)$
	$\displaystyle\overline{\operatorname{\textbf{V}}}^{(1)}$	$\displaystyle\;\equiv\;\big(\lambda V^{(\delta)}\ldots\lambda V^{(1)}.\;V^{(1)% }\big)\qquad\qquad$	$\displaystyle\overline{1}$	$\displaystyle\;\equiv\;\big(\lambda V^{(\delta)}\ldots\lambda V^{(1)}.\;1\big)$

are all understood via Curry-ing as of type $\big(\mathbb{N}\;^{\scriptscriptstyle\delta}\!\!\!\!\nearrow\mathbb{N}\big)$ . Moreover, as structural induction:

$\displaystyle\overline{\boldsymbol{\Pi}+\boldsymbol{\Xi}}\big(V^{(\delta)},% \ldots,V^{(1)}\big)$	$\displaystyle=$	$\displaystyle\overline{\boldsymbol{\Pi}}\big(V^{(\delta)},\ldots,V^{(1)}\big)+% \overline{\boldsymbol{\Xi}}\big(V^{(\delta)},\ldots,V^{(1)}\big)\;:\mathbb{N}$
$\displaystyle\overline{\boldsymbol{\Pi}\cdot\boldsymbol{\Xi}}\big(V^{(\delta)}% ,\ldots,V^{(1)}\big)$	$\displaystyle=$	$\displaystyle\overline{\boldsymbol{\Pi}}\big(V^{(\delta)},\ldots,V^{(1)}\big)% \cdot\overline{\boldsymbol{\Xi}}\big(V^{(\delta)},\ldots,V^{(1)}\big)\;:% \mathbb{N}$
$\displaystyle\overline{\boldsymbol{\Pi}\,{\overset{\scriptscriptstyle 1}{% \raisebox{-1.0pt}[2.0pt]{$\star$}}}\>\boldsymbol{\Xi}}\big(V^{(\delta)},\ldots% ,V^{(1)}\big)$	$\displaystyle=$	$\displaystyle\overline{\boldsymbol{\Pi}}\Big(V^{(\delta)},\ldots V^{(2)},% \overline{\boldsymbol{\Xi}}\big(V^{(\delta)},\ldots V^{(1)}\big)\Big)\;:\>% \mathbb{N}=\mathbb{N}\;^{\scriptscriptstyle 0}\!\!\!\!\nearrow\mathbb{N}$
$\displaystyle\overline{\boldsymbol{\Pi}\,{\overset{\scriptscriptstyle 2}{% \raisebox{-1.0pt}[2.0pt]{$\star$}}}\>\boldsymbol{\Xi}}\big(V^{(\delta)},\ldots% ,V^{(2)}\big)$	$\displaystyle=$	$\displaystyle\overline{\boldsymbol{\Pi}}\Big(V^{(\delta)},\ldots,V^{(3)},% \overline{\boldsymbol{\Xi}}\big(V^{(\delta)},\ldots,V^{(2)}\big)\Big)\;\;:\;% \big(\mathbb{N}\;^{\scriptscriptstyle 1}\!\!\!\!\nearrow\mathbb{N}\big)$
	$\displaystyle\vdots$
$\displaystyle\overline{\boldsymbol{\Pi}\,{\overset{\scriptscriptstyle\delta\!-% \!1}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}\>\boldsymbol{\Xi}}\big(V^{(\delta)},V% ^{(\delta\!-\!1)}\big)$	$\displaystyle=$	$\displaystyle\overline{\boldsymbol{\Pi}}\Big(V^{(\delta)},\overline{% \boldsymbol{\Xi}}\big(V^{(\delta)},V^{(\delta\!-\!1)}\big)\Big)\;\;:\;\big(% \mathbb{N}\;^{\scriptscriptstyle\delta\!-\!2}\!\!\!\!\nearrow\mathbb{N}\big)$
$\displaystyle\overline{\boldsymbol{\Pi}\,{\overset{\scriptscriptstyle\delta}{% \raisebox{-1.0pt}[2.0pt]{$\star$}}}\>\boldsymbol{\Xi}}\big(V^{(\delta)}\big)$	$\displaystyle=$	$\displaystyle\overline{\boldsymbol{\Pi}}\Big(\overline{\boldsymbol{\Xi}}\big(V% ^{(\delta)}\big)\Big)\quad:\;\big(\mathbb{N}\;^{\scriptscriptstyle\delta\!-\!1% }\!\!\!\!\nearrow\mathbb{N}\big)$

d)

Syntactic rules are: $\boldsymbol{\Pi}+\boldsymbol{\Xi}\;\mathrel{\begin{matrix}\includegraphics{% dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\;% \boldsymbol{\Xi}+\boldsymbol{\Pi}$ , $\boldsymbol{\Pi}\cdot\boldsymbol{\Xi}\;\mathrel{\begin{matrix}\includegraphics% {dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\;% \boldsymbol{\Xi}\cdot\boldsymbol{\Pi}$ ,

	$\displaystyle 1\cdot\boldsymbol{\Pi}\;\mathrel{\begin{matrix}\includegraphics{% dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\;% \boldsymbol{\Pi},\qquad\qquad 1\,{\overset{\scriptscriptstyle 1}{\raisebox{-1.% 0pt}[2.0pt]{$\star$}}}\>\boldsymbol{\Pi}\;\mathrel{\begin{matrix}% \includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}% \end{matrix}}\;1,\qquad\ldots\qquad\quad 1\,{\overset{\scriptscriptstyle\delta% }{\raisebox{-1.0pt}[2.0pt]{$\star$}}}\>\boldsymbol{\Pi}\;\mathrel{\begin{% matrix}\includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2% svg.svg}\end{matrix}}\;1$
	$\displaystyle\operatorname{\textbf{V}}^{(1)}\,{\overset{\scriptscriptstyle 1}{% \raisebox{-1.0pt}[2.0pt]{$\star$}}}\>\boldsymbol{\Pi}\;\mathrel{\begin{matrix}% \includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}% \end{matrix}}\;\boldsymbol{\Pi},\quad\operatorname{\textbf{V}}^{(1)}\,{% \overset{\scriptscriptstyle 2}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}\>% \boldsymbol{\Pi}\;\mathrel{\begin{matrix}\includegraphics{dagpub-standalone-% dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\;\operatorname{% \textbf{V}}^{(1)},\quad\ldots\quad\operatorname{\textbf{V}}^{(1)}\,{\overset{% \scriptscriptstyle\delta}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}\>\boldsymbol{\Pi% }\;\mathrel{\begin{matrix}\includegraphics{dagpub-standalone-dagpub-svg-2026-0% 2-03-16-22-40.pdf2svg.svg}\end{matrix}}\;\operatorname{\textbf{V}}^{(1)}$
	$\displaystyle\qquad\vdots$
	$\displaystyle\operatorname{\textbf{V}}^{(\delta\!-\!1)}\,{\overset{% \scriptscriptstyle\delta\!-\!1}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}\>% \boldsymbol{\Pi}\;\mathrel{\begin{matrix}\includegraphics{dagpub-standalone-% dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\;\boldsymbol{\Pi},% \quad\operatorname{\textbf{V}}^{(\delta\!-\!1)}\,{\overset{\scriptscriptstyle% \delta}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}\>\boldsymbol{\Pi}\;\mathrel{\begin% {matrix}\includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2% svg.svg}\end{matrix}}\;\operatorname{\textbf{V}}^{(\delta\!-\!1)},\qquad% \operatorname{\textbf{V}}^{(\delta)}\,{\overset{\scriptscriptstyle\delta}{% \raisebox{-1.0pt}[2.0pt]{$\star$}}}\>\boldsymbol{\Pi}\;\mathrel{\begin{matrix}% \includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}% \end{matrix}}\;\boldsymbol{\Pi}$

	$\displaystyle(\boldsymbol{\Pi}+\boldsymbol{\Xi})+\boldsymbol{\Lambda}\;% \mathrel{\begin{matrix}\includegraphics{dagpub-standalone-dagpub-svg-2026-02-0% 3-16-22-40.pdf2svg.svg}\end{matrix}}\;\boldsymbol{\Pi}+(\boldsymbol{\Xi}+% \boldsymbol{\Lambda}),\quad(\boldsymbol{\Pi}+\boldsymbol{\Xi})\,{\overset{% \scriptscriptstyle\varepsilon}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}\>% \boldsymbol{\Lambda}\;\mathrel{\begin{matrix}\includegraphics{dagpub-% standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\;\big(% \boldsymbol{\Pi}\,{\overset{\scriptscriptstyle\varepsilon}{\raisebox{-1.0pt}[2% .0pt]{$\star$}}}\>\boldsymbol{\Lambda}\big)+\big(\boldsymbol{\Xi}\,{\overset{% \scriptscriptstyle\varepsilon}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}\>% \boldsymbol{\Lambda}\big)\quad(\varepsilon=0\ldots\delta)$
	$\displaystyle(\boldsymbol{\Pi}\cdot\boldsymbol{\Xi})\cdot\boldsymbol{\Lambda}% \;\mathrel{\begin{matrix}\includegraphics{dagpub-standalone-dagpub-svg-2026-02% -03-16-22-40.pdf2svg.svg}\end{matrix}}\;\boldsymbol{\Pi}\cdot(\boldsymbol{\Xi}% \cdot\boldsymbol{\Lambda}),\qquad\quad\;\;(\boldsymbol{\Pi}\cdot\boldsymbol{% \Xi})\,{\overset{\scriptscriptstyle\varepsilon}{\raisebox{-1.0pt}[2.0pt]{$% \star$}}}\>\boldsymbol{\Lambda}\;\mathrel{\begin{matrix}\includegraphics{% dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\;% \big(\boldsymbol{\Pi}\,{\overset{\scriptscriptstyle\varepsilon}{\raisebox{-1.0% pt}[2.0pt]{$\star$}}}\>\boldsymbol{\Lambda}\big)\cdot\big(\boldsymbol{\Xi}\,{% \overset{\scriptscriptstyle\varepsilon}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}\>% \boldsymbol{\Lambda}\big)\quad(\varepsilon=1\ldots\delta)$
	$\displaystyle\big(\boldsymbol{\Pi}\,{\overset{\scriptscriptstyle 1}{\raisebox{% -1.0pt}[2.0pt]{$\star$}}}\>\boldsymbol{\Xi}\big)\,{\overset{\scriptscriptstyle 1% }{\raisebox{-1.0pt}[2.0pt]{$\star$}}}\>\boldsymbol{\Lambda}\;\mathrel{\begin{% matrix}\includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2% svg.svg}\end{matrix}}\;\boldsymbol{\Pi}\,{\overset{\scriptscriptstyle 1}{% \raisebox{-1.0pt}[2.0pt]{$\star$}}}\>\big(\boldsymbol{\Xi}\,{\overset{% \scriptscriptstyle 1}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}\>\boldsymbol{\Lambda% }\big),\qquad\big(\boldsymbol{\Pi}\,{\overset{\scriptscriptstyle 1}{\raisebox{% -1.0pt}[2.0pt]{$\star$}}}\>\boldsymbol{\Xi}\big)\,{\overset{\scriptscriptstyle% \varepsilon}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}\>\boldsymbol{\Lambda}\;% \mathrel{\begin{matrix}\includegraphics{dagpub-standalone-dagpub-svg-2026-02-0% 3-16-22-40.pdf2svg.svg}\end{matrix}}\;\big(\boldsymbol{\Pi}\,{\overset{% \scriptscriptstyle\varepsilon}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}\>% \boldsymbol{\Lambda}\big)\,{\overset{\scriptscriptstyle 1}{\raisebox{-1.0pt}[2% .0pt]{$\star$}}}\>\big(\boldsymbol{\Xi}\,{\overset{\scriptscriptstyle% \varepsilon}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}\>\boldsymbol{\Lambda}\big)% \quad(\varepsilon=2\ldots\delta)$
	$\displaystyle\qquad\vdots$
	$\displaystyle\big(\boldsymbol{\Pi}\,{\overset{\scriptscriptstyle\delta\!-\!1}{% \raisebox{-1.0pt}[2.0pt]{$\star$}}}\>\boldsymbol{\Xi}\big)\,{\overset{% \scriptscriptstyle\delta\!-\!1}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}\>% \boldsymbol{\Lambda}\;\mathrel{\begin{matrix}\includegraphics{dagpub-% standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\;% \boldsymbol{\Pi}\,{\overset{\scriptscriptstyle\delta\!-\!1}{\raisebox{-1.0pt}[% 2.0pt]{$\star$}}}\>\big(\boldsymbol{\Lambda}\,{\overset{\scriptscriptstyle% \delta\!-\!1}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}\>\boldsymbol{\Xi}\big),% \qquad\big(\boldsymbol{\Pi}\,{\overset{\scriptscriptstyle\delta\!-\!1}{% \raisebox{-1.0pt}[2.0pt]{$\star$}}}\>\boldsymbol{\Xi}\big)\,{\overset{% \scriptscriptstyle\delta}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}\>\boldsymbol{% \Lambda}\;\mathrel{\begin{matrix}\includegraphics{dagpub-standalone-dagpub-svg% -2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\;\big(\boldsymbol{\Pi}\,{% \overset{\scriptscriptstyle\delta}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}\>% \boldsymbol{\Lambda}\big)\,{\overset{\scriptscriptstyle\delta\!-\!1}{\raisebox% {-1.0pt}[2.0pt]{$\star$}}}\>\big(\boldsymbol{\Xi}\,{\overset{% \scriptscriptstyle\delta}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}\>\boldsymbol{% \Lambda}\big)$
	$\displaystyle\big(\boldsymbol{\Pi}\;\mathrel{\begin{matrix}\includegraphics{% dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\;% \boldsymbol{\Pi}^{\prime}\;\;\wedge\;\;\boldsymbol{\Xi}\;\mathrel{\begin{% matrix}\includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2% svg.svg}\end{matrix}}\;\boldsymbol{\Xi}^{\prime}\big)\quad\Rightarrow\quad% \boldsymbol{\Pi}\,{\overset{\scriptscriptstyle\varepsilon}{\raisebox{-1.0pt}[2% .0pt]{$\star$}}}\>\boldsymbol{\Xi}\;\mathrel{\begin{matrix}\includegraphics{% dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\;% \boldsymbol{\Pi}^{\prime}\,{\overset{\scriptscriptstyle\varepsilon}{\raisebox{% -1.0pt}[2.0pt]{$\star$}}}\>\boldsymbol{\Xi}^{\prime}\quad(\varepsilon=-1,0% \ldots\delta-1)\enspace.$

e)

A univariate arctic order- $\delta$ polynomial in $\big(\operatorname{\textbf{W}}^{(\delta)},\ldots,\operatorname{\textbf{W}}^{(1% )}\big)$ is syntactically generated by

$\widetilde{\boldsymbol{\Pi}},\widetilde{\boldsymbol{\Xi}}\quad::=\quad 0\mid 1% \mid\operatorname{\textbf{W}}^{(1)}\mid\cdots\mid\operatorname{\textbf{W}}^{(% \delta)}\mid\widetilde{\boldsymbol{\Pi}}+\widetilde{\boldsymbol{\Xi}}\mid% \widetilde{\boldsymbol{\Pi}}\cdot\widetilde{\boldsymbol{\Xi}}\mid\widetilde{% \boldsymbol{\Pi}}\,{\overset{\scriptscriptstyle 1}{\raisebox{-1.0pt}[2.0pt]{$% \star$}}}\>\widetilde{\boldsymbol{\Xi}}\mid\cdots\mid\widetilde{\boldsymbol{% \Pi}}\,{\overset{\scriptscriptstyle\delta}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}% \>\widetilde{\boldsymbol{\Xi}}\mid\max\big(\widetilde{\boldsymbol{\Pi}},% \widetilde{\boldsymbol{\Xi}}\big)\enspace.$

f)

Syntactic equivalence among arctic order- $\delta$ polynomials extends (d) with these rules:

	$\displaystyle\max\big\{0,\widetilde{\boldsymbol{\Pi}}\big\}\;\mathrel{\begin{% matrix}\includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2% svg.svg}\end{matrix}}\;\widetilde{\boldsymbol{\Pi}},\quad 0+\widetilde{% \boldsymbol{\Pi}}\;\mathrel{\begin{matrix}\includegraphics{dagpub-standalone-% dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\;\widetilde{% \boldsymbol{\Pi}},\qquad 0\,{\overset{\scriptscriptstyle\varepsilon}{\raisebox% {-1.0pt}[2.0pt]{$\star$}}}\>\widetilde{\boldsymbol{\Pi}}\;\mathrel{\begin{% matrix}\includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2% svg.svg}\end{matrix}}\;0\quad(\varepsilon=0\ldots\delta)$
	$\displaystyle\max\big\{\widetilde{\boldsymbol{\Pi}},\widetilde{\boldsymbol{\Xi% }}\big\}\;\mathrel{\begin{matrix}\includegraphics{dagpub-standalone-dagpub-svg% -2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\;\max\big\{\widetilde{% \boldsymbol{\Xi}},\widetilde{\boldsymbol{\Pi}}\big\},\quad\max\Big\{\widetilde% {\boldsymbol{\Pi}},\max\big\{\widetilde{\boldsymbol{\Xi}},\widetilde{% \boldsymbol{\Lambda}}\big\}\Big\}\;\mathrel{\begin{matrix}\includegraphics{% dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\;% \max\Big\{\max\big\{\widetilde{\boldsymbol{\Pi}},\widetilde{\boldsymbol{\Xi}}% \big\},\widetilde{\boldsymbol{\Lambda}}\big\}\Big\},$
	$\displaystyle\widetilde{\boldsymbol{\Pi}}\,\,{\overset{\scriptscriptstyle% \varepsilon}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}\>\max\big\{\widetilde{% \boldsymbol{\Xi}},\widetilde{\boldsymbol{\Lambda}}\big\}\;\mathrel{\begin{% matrix}\includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2% svg.svg}\end{matrix}}\;\max\big\{\widetilde{\boldsymbol{\Pi}}\,{\overset{% \scriptscriptstyle\varepsilon}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}\>\widetilde% {\boldsymbol{\Xi}},\widetilde{\boldsymbol{\Pi}}\,{\overset{\scriptscriptstyle% \varepsilon}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}\>\widetilde{\boldsymbol{% \Lambda}}\big\}\quad(\varepsilon=-1,0\ldots\delta)$
	$\displaystyle\big(\widetilde{\boldsymbol{\Pi}}\;\mathrel{\begin{matrix}% \includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}% \end{matrix}}\;\widetilde{\boldsymbol{\Pi}}^{\prime}\;\;\wedge\;\;\widetilde{% \boldsymbol{\Xi}}\;\mathrel{\begin{matrix}\includegraphics{dagpub-standalone-% dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\;\widetilde{% \boldsymbol{\Xi}}^{\prime}\big)\quad\Rightarrow\quad\max\big\{\widetilde{% \boldsymbol{\Pi}},\widetilde{\boldsymbol{\Xi}}\big\}\;\mathrel{\begin{matrix}% \includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}% \end{matrix}}\;\max\big\{\widetilde{\boldsymbol{\Pi}}^{\prime},\widetilde{% \boldsymbol{\Xi}}^{\prime}\big\}\enspace.$

g)

The degree $\operatorname{Deg}(\boldsymbol{\Pi})$ of (non-arctic) order- $\delta$ polynomial $\boldsymbol{\Pi}=\boldsymbol{\Pi}\big(\operatorname{\textbf{V}}^{(\delta)},% \ldots,\operatorname{\textbf{V}}^{(1)}\big)$ is the arctic order- $(\delta-1)$ polynomial in $\big(\operatorname{\textbf{W}}^{(\delta\!-\!1)},\ldots,\operatorname{\textbf{W% }}^{(1)}\big)$ defined inductively by

	$\displaystyle\operatorname{Deg}(1)\>=\>0,\quad\operatorname{Deg}(\operatorname% {\textbf{V}}^{(1)})\>=\>1,\quad\operatorname{Deg}(\operatorname{\textbf{V}}^{(% 2)})\>=\>\operatorname{\textbf{W}}^{(1)},\;\ldots\;\operatorname{Deg}(% \operatorname{\textbf{V}}^{(\delta)})\>=\>\operatorname{\textbf{W}}^{(\delta-1)}$
	$\displaystyle\operatorname{Deg}(\boldsymbol{\Pi}+\boldsymbol{\Xi})\;=\;\max% \big\{\operatorname{Deg}(\boldsymbol{\Pi}),\operatorname{Deg}(\boldsymbol{\Xi}% )\big\},\qquad\operatorname{Deg}(\boldsymbol{\Pi}\cdot\boldsymbol{\Xi})\;=\;% \operatorname{Deg}(\boldsymbol{\Pi})+\operatorname{Deg}(\boldsymbol{\Xi}),$
	$\displaystyle\operatorname{Deg}(\boldsymbol{\Pi}\,{\overset{\scriptscriptstyle 1% }{\raisebox{-1.0pt}[2.0pt]{$\star$}}}\>\boldsymbol{\Xi})\;=\;\operatorname{Deg% }(\boldsymbol{\Pi})\cdot\operatorname{Deg}(\boldsymbol{\Xi}),\quad\ldots\quad% \operatorname{Deg}(\boldsymbol{\Pi}\,{\overset{\scriptscriptstyle\delta}{% \raisebox{-1.0pt}[2.0pt]{$\star$}}}\>\boldsymbol{\Xi})\;=\;\operatorname{Deg}(% \boldsymbol{\Pi})\,{\overset{\scriptscriptstyle\delta\!-\!1}{\raisebox{-1.0pt}% [2.0pt]{$\star$}}}\>\operatorname{Deg}(\boldsymbol{\Xi})\enspace.$

Theorem 28.

a)

Every $\delta$ -order polynomial as in Definition 27b) can be syntactically transformed, using Definition 27d), into an equivalent form in which (i) $\,{\overset{\scriptscriptstyle\delta}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}$ does not occur; (ii) whenever $\,{\overset{\scriptscriptstyle\delta\!-\!1}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}$ occurs, its left argument is $\operatorname{\textbf{V}}^{(\delta)}$ ; (iii) whenever $\,{\overset{\scriptscriptstyle\delta\!-\!2}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}$ occurs, its left argument is $\operatorname{\textbf{V}}^{(\delta)}$ or $\operatorname{\textbf{V}}^{(\delta\!-\!1)}$ or of the form $(\boldsymbol{\Pi}\,{\overset{\scriptscriptstyle\delta\!-\!1}{\raisebox{-1.0pt}% [2.0pt]{$\star$}}}\>\boldsymbol{\Xi})$ ; (iv) whenever $\,{\overset{\scriptscriptstyle\delta\!-\!3}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}$ occurs, its left argument is $\operatorname{\textbf{V}}^{(\delta)}$ or $\operatorname{\textbf{V}}^{(\delta\!-\!1)}$ or $\operatorname{\textbf{V}}^{(\delta\!-\!2)}$ or of the form $(\boldsymbol{\Pi}\,{\overset{\scriptscriptstyle\delta\!-\!1}{\raisebox{-1.0pt}% [2.0pt]{$\star$}}}\>\boldsymbol{\Xi})$ or of the form $(\boldsymbol{\Pi}\,{\overset{\scriptscriptstyle\delta\!-\!2}{\raisebox{-1.0pt}% [2.0pt]{$\star$}}}\>\boldsymbol{\Xi})$ .
b)

The degree of $\delta$ -order polynomials is well-defined, namely invariant under syntactic equivalences according to Definition 27d+f).

Proofs proceed as in the third-order case. We hope that Remark 2e) and Theorem 7 generalize:

Conjecture 29.

Let $\boldsymbol{\Pi}\not\mathrel{\begin{matrix}\includegraphics{dagpub-standalone-% dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\boldsymbol{\Xi}$ denote two syntactically non-equivalent order- $\delta$ polynomials. Then there exists an assignment $\overline{\operatorname{\textbf{V}}}^{(1)}=V^{(1)}:\mathbb{N}=\big(\mathbb{N}% \;^{\scriptscriptstyle 0}\!\!\!\!\nearrow\mathbb{N}\big)$ , $\overline{\operatorname{\textbf{V}}}^{(2)}=V^{(2)}:\big(\mathbb{N}\;^{% \scriptscriptstyle 1}\!\!\!\!\nearrow\mathbb{N}\big)$ , … $\overline{\operatorname{\textbf{V}}}^{(\delta)}=V^{(\delta)}:\big(\mathbb{N}\;% ^{\scriptscriptstyle\delta\!-\!1}\!\!\!\!\nearrow\mathbb{N}\big)$ such that $\overline{\boldsymbol{\Pi}}\big(V^{(\delta)},\ldots,V^{(1)}\big)\;\neq\;% \overline{\boldsymbol{\Xi}}\big(V^{(\delta)},\ldots,V^{(1)}\big)\;\in\;\mathbb% {N}$ .

3.4 Simply Typed Lambda Calculus Perspective

We have already employed Lambda notation, for instance when expressing the semantics of higher-order polynomials in Remark 21b) and in Definitions 23b) and 27c). A reader familiar with Type Theory might appreciate the following alternative characterization of order- $\delta$ polynomials, here for simplicity only in the non-arctic case.

$\blacktriangleright$ Remark 30.

a)

Let $\operatorname{\textbf{V}}^{(1)},\ldots,\operatorname{\textbf{V}}^{(\delta)}$ denote variables, and $\operatorname{\textbf{V}}^{(0)}$ a constant symbol. For each $\varepsilon=-1,0,1,\ldots,\delta$ let $\,{\overset{\scriptscriptstyle\varepsilon}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}$ denote an associative binary function symbol.
b)

Write $\mathcal{P}^{(\delta)}$ for the set of syntactically valid expressions $\boldsymbol{\Pi}^{(\delta)}$ over said variables and symbols. Order- $\delta$ polynomials are Lambda Terms of the form

$\lambda\operatorname{\textbf{V}}^{(1)}.\;\ldots\;\lambda\operatorname{\textbf{% V}}^{(\delta)}.\;\;\boldsymbol{\Pi}^{(\delta)}\enspace.$ (10)
c)

Towards the semantics of such a Lambda Term, impose initial types as follows:

$\displaystyle\operatorname{\textbf{V}}^{(0)}=1:\{1\}=(\mathbb{N}\;^{% \scriptscriptstyle-1}\!\!\!\!\nearrow\mathbb{N}),\quad\operatorname{\textbf{V}% }^{(1)}:\mathbb{N}=(\mathbb{N}\;^{\scriptscriptstyle 0}\!\!\!\!\nearrow\mathbb% {N}),\quad\operatorname{\textbf{V}}^{(2)}:(\mathbb{N}{\scriptstyle\nearrow}% \mathbb{N}),$

$\displaystyle\operatorname{\textbf{V}}^{(3)}:\big((\mathbb{N}{\scriptstyle% \nearrow}\mathbb{N})\nearrow(\mathbb{N}{\scriptstyle\nearrow}\mathbb{N})\big),% \quad\ldots\quad\operatorname{\textbf{V}}^{(\delta)}:\mathbb{N}\;^{% \scriptscriptstyle\delta\!-\!1\!}\!\!\!\!\nearrow\mathbb{N}\enspace.$
d)

Let $\,{\overset{\scriptscriptstyle-1}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}="+":% \mathbb{N}\nearrow\mathbb{N}\nearrow\mathbb{N}$ and $\,{\overset{\scriptscriptstyle 0}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}="\cdot":% \mathbb{N}\nearrow\mathbb{N}\nearrow\mathbb{N}$ and

$\,{\overset{\scriptscriptstyle\varepsilon}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}% \;=\;"\circ":\;(\mathbb{N}\;^{\scriptscriptstyle\varepsilon}\!\!\!\!\nearrow% \mathbb{N})\nearrow(\mathbb{N}\;^{\scriptscriptstyle\varepsilon}\!\!\!\!% \nearrow\mathbb{N})\nearrow(\mathbb{N}\;^{\scriptscriptstyle\varepsilon}\!\!\!% \!\nearrow\mathbb{N}),\quad\varepsilon=1,\ldots,\delta$

where $g\circ f$ denotes the polymorphic composition of $f,g:(\mathbb{N}\;^{\scriptscriptstyle\varepsilon}\!\!\!\!\nearrow\mathbb{N})% \nearrow(\mathbb{N}\;^{\scriptscriptstyle\varepsilon}\!\!\!\!\nearrow\mathbb{N})$ .
e)

Next consider $\,{\overset{\scriptscriptstyle-1}{\raisebox{-1.0pt}[2.0pt]{$\star$}}},\,{% \overset{\scriptscriptstyle 0}{\raisebox{-1.0pt}[2.0pt]{$\star$}}},\ldots,\,{% \overset{\scriptscriptstyle\delta\!-\!1\!}{\raisebox{-1.0pt}[2.0pt]{$\star$}}}$ extended pointwise to type $(\mathbb{N}\;^{\scriptscriptstyle\delta}\!\!\!\!\nearrow\mathbb{N})\nearrow(% \mathbb{N}\;^{\scriptscriptstyle\delta}\!\!\!\!\nearrow\mathbb{N})\nearrow(% \mathbb{N}\;^{\scriptscriptstyle\delta}\!\!\!\!\nearrow\mathbb{N})$ . And, for $\varepsilon<\delta$ , consider $\boldsymbol{\Pi}^{(\varepsilon)}$ of type $\mathbb{N}\;^{\scriptscriptstyle\varepsilon}\!\!\!\!\nearrow\mathbb{N}$ as constant mapping of type

$\mathbb{N}\;^{\scriptscriptstyle\delta}\!\!\!\!\nearrow\mathbb{N}\;=\;\big(% \mathbb{N}\;^{\scriptscriptstyle\delta\!-\!1\!}\!\!\!\!\nearrow\mathbb{N}\big)% \nearrow\big(\mathbb{N}\;^{\scriptscriptstyle\delta\!-\!2\!}\!\!\!\!\nearrow% \mathbb{N}\big)\nearrow\cdots\nearrow\big(\mathbb{N}\;^{\scriptscriptstyle% \varepsilon}\!\!\!\!\nearrow\mathbb{N}\big)\nearrow\big(\mathbb{N}\;^{% \scriptscriptstyle\varepsilon}\!\!\!\!\nearrow\mathbb{N}\big)\enspace.$
f)

Structural induction on the expression built-up according to (b) thus well-defines the semantics of Equation (10) of type $\mathbb{N}\;^{\scriptscriptstyle\delta}\!\!\!\!\nearrow\mathbb{N}$ . And said family of mappings coincides with the family of order- $\delta$ polynomials according to Definition 27c).
g)

This fragment of Simply Typed Lambda Calculus allows only terms in “head” normal form (10) without inner bound variables, cmp. Example 24b). Item e) employs two kinds of type coercion: i) Extending each binary operation $+,\cdot,\circ,\ldots$ pointwise from its initial $X\to X\to Y$ to a higher type $(Z\to X)\to(Z\to X)\to(Z\to Y)$ . And ii) considering an element $y$ of some type $Y$ as constant function of type $Z\to Y$ . Thus any (sub-)expression $\boldsymbol{\Xi}$ semantically induces an operator of same pure input and output type. $\lrcorner$

References

[1] Aras Bacho and Martin Ziegler. Second-order parameterizations for the complexity theory of integrable functions. arXiv CoRR, 2506.11210, 2025. doi:10.48550/arXiv.2506.11210.
[2] Patrick Baillot, Ugo Dal Lago, Cynthia Kop, and Deivid Vale. On basic feasible functionals and the interpretation method. In Naoki Kobayashi and James Worrell, editors, Proc.II of 27th Int. Conf. Foundations of Software Science and Computation Structures (FoSSaCS2024), held as part of the European Joint Conferences on Theory and Practice of Software (ETAPS2024) in Luxembourg, volume 14575 of Lecture Notes in Computer Science, pages 70–91. Springer, 2024. doi:10.1007/978-3-031-57231-9_4.
[3] Eyvind Martol Briseid. Fixed point of generalized contractive mappings. Journal of Nonlinear and Convex Analysis, 9:2:181–204, 2008.
[4] Eyvind Martol Briseid. Logical aspects of rates of convergence in metric spaces. The Journal of Symbolic Logic, 74(4):1401–1428, 2009. doi:10.2178/jsl/1254748697.
[5] Michael Codish, Yoav Fekete, Carsten Fuhs, Jürgen Giesl, and Johannes Waldmann. Exotic Semiring Constraints. In SMT 2012. 10th International Workshop on Satisfiability Modulo Theories, volume 20 of EasyChair Proceedings in Computing, pages 88–97. EasyChair, 2013. doi:10.29007/QQVT.
[6] Martin Dietzfelbinger. Primality Testing in Polynomial Time, volume 3000 of Lecture Notes in Computer Science. Springer, 2004. doi:10.1007/B12334.
[7] Hugo Férée and Mathieu Hoyrup. Higher-order complexity in analysis. HAL Archive, July 2013. Proc 10th Int.Conf. Computability and Complexity in Analysis (CCA). URL: https://hal.inria.fr/hal-00915973.
[8] Anka Gajentaan and Mark H Overmars. On a class of O( $n^{2}$ ) problems in computational geometry. Computational Geometry, 5(3):165–185, 1995. doi:10.1016/0925-7721(95)00022-2.
[9] Mikhail Gromov. Groups of polynomial growth and expanding maps. Publications Mathématiques de L’Institut des Hautes Scientifiques, 53:53–78, 1981. doi:10.1007/BF02698687.
[10] Emmanuel Hainry, Bruce M. Kapron, Jean-Yves Marion, and Romain Péchoux. Declassification policy for program complexity analysis. In Pawel Sobocinski, Ugo Dal Lago, and Javier Esparza, editors, Proc. 39th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2024, Tallinn, Estonia, pages 41:1–41:14. ACM, 2024. doi:10.1145/3661814.3662100.
[11] Emmanuel Hainry and Romain Péchoux. Higher order interpretation for higher order complexity. In Thomas Eiter and David Sands, editors, LPAR-21, 21st International Conference on Logic for Programming, Artificial Intelligence and Reasoning, Maun, Botswana, May 7-12, 2017, volume 46 of EPiC Series in Computing, pages 269–285. EasyChair, 2017. doi:10.29007/1TKW.
[12] Peter Hertling. Topological complexity with continuous operations. Journal of Complexity, 12(4):315–338, 1996. doi:10.1006/jcom.1996.0021.
[13] Bruce M. Kapron and Stephen A. Cook. A new characterization of type-2 feasibility. SIAM J. Comput., 25(1):117–132, 1996. doi:10.1137/S0097539794263452.
[14] Bruce M. Kapron and Florian Steinberg. Type-two polynomial-time and restricted lookahead. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS ’18, pages 579–588, New York, NY, USA, 2018. Association for Computing Machinery. doi:10.1145/3209108.3209124.
[15] Akitoshi Kawamura and Stephen A. Cook. Complexity theory for operators in analysis. ACM Trans. Comput. Theory, 4(2):5:1–5:24, 2012. doi:10.1145/2189778.2189780.
[16] Akitoshi Kawamura, Florian Steinberg, and Holger Thies. Second-order linear-time computability with applications to computable analysis. In Proc. 15th Conf. on Theory and Applications of Models of Computation (TAMC), pages 337–358, Berlin, Heidelberg, 2019. Springer-Verlag. doi:10.1007/978-3-030-14812-6_21.
[17] Ker-I Ko. Complexity Theory of Real Functions, volume 3 of Progress in theoretical computer science. Birkhäuser / Springer, 1991. doi:10.1007/978-1-4684-6802-1.
[18] Ivan Koswara, Gleb Pogudin, Svetlana Selivanova, and Martin Ziegler. Bit-complexity of classical solutions of linear evolutionary systems of partial differential equations. Journal of Complexity, 76:101727, 2023. doi:10.1016/j.jco.2022.101727.
[19] David A. Levin and Yuval Peres. Markov chains and mixing times. American Mathematical Society, Providence, Rhode Island, 2009.
[20] Donghyun Lim. Degrees of second and higher-order polynomials. 4th Workshop on Mathematical Logic and its Applications, March 2021. URL: http://jaist.ac.jp/event/mla2021.
[21] Donghyun Lim and Martin Ziegler. Degrees of second and higher-order polynomials. arXiv CoRR, 2305.03439, 2023. doi:10.48550/arXiv.2305.03439.
[22] Donghyun Lim and Martin Ziegler. Quantitative coding and complexity theory of Continuous data: Part I. J. ACM, 72(1):4:1–4:39, 2025. doi:10.1145/3705609.
[23] George G. Lorentz. Metric entropy and approximation, volume 72. AMS, 1996.
[24] Kurt Mehlhorn. Polynomial and abstract subrecursive classes. Journal of Computer and System Sciences, 12(2):147–178, 1976. doi:10.1016/S0022-0000(76)80035-9.
[25] Eike Neumann and Florian Steinberg. Parametrised second-order complexity theory with applications to the study of interval computation. Theor. Comput. Sci., 806:281–304, 2020. doi:10.1016/j.tcs.2019.05.009.
[26] Jürgen Richter-Gebert, Bernd Sturmfels, and Thorsten Theobald. First steps in tropical geometry. Idempotent Mathematics and Mathematical Physics, 377:289–317, 2005.
[27] Jon G. Riecke and Ramesh Subrahmanyam. Conditions for the completeness of functional and algebraic equational reasoning. Mathemat.Structures Computer Science, 9(6):651–685, 1999. doi:10.1017/S0960129599002807.
[28] Ernst Specker, Norbert Hungerbühler, and Micha Wasem. Polyfunctions over commutative rings. J. Algebra and Applications, 23(01):2450014, 2024. doi:10.1142/S0219498824500142.
[29] Volker Strassen. Gaussian elimination is not optimal. Numer.Mathematik, 13:354–356, 1969.
[30] Mike Townsend. Complexity for type-2 relations. Notre Dame Formal Logic, 31(2):241–262, 1990. doi:10.1305/NDJFL/1093635419.
[31] Martin Ziegler. Hyper-degrees of 2nd-order polynomial-time reductions. Technical report, Dagstuhl Seminar #15392, 2016. abstract §3.20. doi:10.4230/DagRep.5.9.77.

Appendix A Proof of Example 16b

Recall [12, bottom of p.336] the Trisection Algorithm 1 below, approximating $f^{-1}(y)$ up to error $2^{-n}$ . Traditional bisection in $[a;b]$ for $x$ with $f(x)=y$ fails in case $f(\tfrac{a+b}{2})=y$ , since test for equality is impossible reliably. Inequalities $f(\tfrac{a+b}{2})<y$ and $f(\tfrac{a+b}{2})>y$ on the other hand can be verified reliably, subject to the promise $f(\tfrac{a+b}{2})\neq y$ . Trisection instead performs both tests $f(a^{\prime})<y$ and $f(b^{\prime})>y$ simultaneously, for $a^{\prime}:=\tfrac{2}{3}a+\tfrac{1}{3}b$ and $b^{\prime}:=\tfrac{1}{3}a+\tfrac{2}{3}b$ : Whichever test succeeds reliably, is taken to proceed either to $[a^{\prime};b]$ or to $[a;b^{\prime}]$ , respectively.

Algorithm 1 Trisection.

In Line 6 of the Pseudo-code 1, xorif indicates that both comparisons “ $v>y$ ” and “ $u<y$ ” are conducted in parallel such that, non-deterministically, precisely one of the two assignments gets executed. Since $f$ is guaranteed strictly increasing, at least one of the two conditions holds; possibly both. To find out which one, take approximations $\tilde{u}$ to $u=f(a)$ and $\tilde{v}$ to $v=f(b)$ up to sufficient precision. For that in turn take approximations to $a$ and $b$ up to sufficient precision. This incurs total bit-cost $\mathcal{O}(\nu(m)+\mu(\nu(m)+2))$ , as argued in the sequel:

Indeed, $\nu$ being a modulus of continuity of $f^{-1}$ implies $v-u>2^{-\nu(m)}$ since $f^{-1}(v)-f^{-1}(u)=b^{\prime}-a^{\prime}=(\tfrac{2}{3})^{k+1}>2^{-m}$ for $m:=\lceil(k+1)\cdot\log_{2}(\tfrac{3}{2})\rceil$ . Hence dyadic approximations $\tilde{u}$ to $u=f(a^{\prime})$ and $\tilde{v}$ to $v=f(b^{\prime})$ and $\tilde{y}$ to $y$ , all up to error $2^{-\nu(m)-3}$ , will confirm at least one of the two inequalities

\tilde{v}>\tilde{y}+2^{-\nu(m)-2},\qquad\tilde{u}<\tilde{y}-2^{-\nu(m)-2}

satisfied as witnesses to $v>y$ or $u<y$ , respectively; to which in turn approximations to $a^{\prime},b^{\prime}$ suffice up to error $2^{-\mu(\nu(m)+2)}$ . Hence Lines 6 and 4 and 5 incur bit-cost

\mathcal{O}\Big(\nu(m)\>+\>\mu\big(\nu(m)+2\big)\Big)\;\leq\;\mathcal{O}\Big(% \nu(n+2)\>+\>\mu\big(\nu(n+2)+3\big)\Big)\enspace.

And these lines are repeated $\mathcal{O}(n)$ times according to Line 3. ∎

Appendix B Selected Further Deferred Proofs

Proof of Example 19.

Calculate

$\displaystyle\overline{\boldsymbol{\Pi}}\big(m\mapsto a\cdot m^{d},n\big)$	$\displaystyle=$	$\displaystyle\big(a^{2d+2}+a^{d+1}\big)\cdot n^{2d^{2}}$
$\displaystyle\overline{\boldsymbol{\Xi}}\big(m\mapsto a\cdot m^{d},n\big)$	$\displaystyle=$	$\displaystyle 2a^{2d+1}\cdot n^{2d^{2}}$
$\displaystyle\overline{\boldsymbol{\Pi}}\big(m\mapsto m^{d}+c,n\big)$	$\displaystyle=$	$\displaystyle\big((n^{d}+c)^{d}+c\big)^{2}\;+\;\big(n^{2d}+c\big)^{d}$
	$\displaystyle\approx$	$\displaystyle\big(n^{d^{2}}\>+\>cdn^{d(d-1)}\>+\>\ldots\big)^{2}\;+\;N^{2d^{2}% }\>+\>cdn^{2d\cdot(d-1)}\>+\>\cdots$
	$\displaystyle\approx$	$\displaystyle 2n^{2d^{2}}\;+\;2cdn^{d^{2}+2d\cdot(d-1)}\;+\;\cdots$
$\displaystyle\overline{\boldsymbol{\Xi}}\big(m\mapsto m^{d}+c,n\big)$	$\displaystyle=$	$\displaystyle 2\cdot(n^{d}+c)^{2d}\;+\;2c$
	$\displaystyle\approx$	$\displaystyle 2n^{2d^{2}}\;+\;\boldsymbol{2}(2d)cn^{d(2d-1)}\;+\;\cdots$

where “ $\approx$ ” means first (few) terms in the Taylor expansion w.r.t. $n\to\infty$ . $\hfill\blacktriangleleft$

Proof of Example 14iv+v.

iv)

By definition of $\boldsymbol{\Pi}$ , running $\mathcal{M}^{\varphi}(\vec{x})$ makes at most $\overline{\boldsymbol{\Pi}}(|\varphi|,|\vec{x}|)$ steps. In particular its output $\vec{y}$ has length at most $\overline{\boldsymbol{\Pi}}(|\varphi|,|\vec{x}|)$ . By definition of $\boldsymbol{\Xi}$ , $\mathcal{N}^{\varphi}(\vec{y})$ in turn makes at most $\overline{\boldsymbol{\Xi}}(|\varphi|,|\vec{y}|)$ steps.
v)

$\mathcal{M}^{\psi}(\vec{x})$ makes at most $\boldsymbol{\Pi}(|\psi|,|\vec{x}|)$ steps and in particular makes at most that many queries “ $G(\varphi,\vec{y})=\textbf{?}$ ” to oracle $\psi=\mathcal{N}^{\varphi}$ , each of bounded length $m=|\vec{y}|\leq\boldsymbol{\Pi}(|\psi|,|\vec{x}|)$ . Similarly, $\psi=\mathcal{N}^{\varphi}$ answering any such query $\vec{y}$ takes time at most $\boldsymbol{\Xi}(|\varphi|,m)$ and in particular returns an answer $\vec{z}=\psi(\vec{y})$ of length $|\vec{z}|\leq\boldsymbol{\Xi}(|\varphi|,m)$ : hence $|\psi|(m)\leq\boldsymbol{\Xi}(|\varphi|,m)$ .

$\hfill\blacktriangleleft$

Proof of Example 17iii.

For one direction, suppose that $\pi$ satisfies

\forall m\;\forall M<2^{m}:\quad\pi(M)\;<\;2^{q(m)}\enspace.

(11)

Then $\pi^{-1}\big[2^{q(m)};\infty)\subseteq\big[2^{m};\infty)$ and therefore

\sum\nolimits_{L\geq 2^{q(m)}}|z_{\pi^{-1}(L)}|^{p}\;\;\leq\;\sum\nolimits_{K% \geq 2^{m}}|z_{K}|^{p}\quad\leq\ 2^{-pn}

for $m:=\sigma(n)$ by hypothesis. Hence $\tau:=q\circ\sigma$ is a (not necessarily minimal, i.e. an upper bound on the) modulus of convergence of the image sequence.

Conversely suppose $\tau=\boldsymbol{\Pi}(\sigma,\cdot)$ is some (upper bound on the minimal) modulus of convergence of the image sequence whenever $\sigma$ is for the original sequence: Since $\boldsymbol{\Pi}$ is monotone, also $\sigma$ need not be minimal. Fix $m\geq 3$ and note that $\sigma:\equiv m$ constitutes a joint modulus of convergence to all sequences $\bar{z}^{(M)}=(0,\ldots,0,\boldsymbol{1},0,\ldots)\in\ell^{p}$ with value 1 only at one index $M<2^{m}$ . The image of $\bar{z}^{(M)}$ is the sequence $\bar{z}^{(\pi(M))}$ , which by hypothesis satisfies $\displaystyle\tfrac{1}{2}\;\geq\;\sum\nolimits_{L\geq 2^{\tau(1)}}\big|z^{(M)}% _{\pi^{-1}(L)}\big|^{p}\;\geq 1$ unless $\pi(M)<2^{\tau(1)}=2^{q(m)}$ for all $M<2^{m}$ , with $q(m):=\boldsymbol{\Pi}(\lambda n.m,1)$ a first-order polynomial according to Proposition 12c). $\hfill\blacktriangleleft$

[bib.bib1] [1] Aras Bacho and Martin Ziegler. Second-order parameterizations for the complexity theory of integrable functions. arXiv CoRR, 2506.11210, 2025. doi:10.48550/arXiv.2506.11210.

[bib.bib2] [2] Patrick Baillot, Ugo Dal Lago, Cynthia Kop, and Deivid Vale. On basic feasible functionals and the interpretation method. In Naoki Kobayashi and James Worrell, editors, Proc.II of 27th Int. Conf. Foundations of Software Science and Computation Structures (FoSSaCS2024), held as part of the European Joint Conferences on Theory and Practice of Software (ETAPS2024) in Luxembourg, volume 14575 of Lecture Notes in Computer Science, pages 70–91. Springer, 2024. doi:10.1007/978-3-031-57231-9_4.

[bib.bib3] [3] Eyvind Martol Briseid. Fixed point of generalized contractive mappings. Journal of Nonlinear and Convex Analysis, 9:2:181–204, 2008.

[bib.bib4] [4] Eyvind Martol Briseid. Logical aspects of rates of convergence in metric spaces. The Journal of Symbolic Logic, 74(4):1401–1428, 2009. doi:10.2178/jsl/1254748697.

[bib.bib5] [5] Michael Codish, Yoav Fekete, Carsten Fuhs, Jürgen Giesl, and Johannes Waldmann. Exotic Semiring Constraints. In SMT 2012. 10th International Workshop on Satisfiability Modulo Theories, volume 20 of EasyChair Proceedings in Computing, pages 88–97. EasyChair, 2013. doi:10.29007/QQVT.

[bib.bib6] [6] Martin Dietzfelbinger. Primality Testing in Polynomial Time, volume 3000 of Lecture Notes in Computer Science. Springer, 2004. doi:10.1007/B12334.

[bib.bib7] [7] Hugo Férée and Mathieu Hoyrup. Higher-order complexity in analysis. HAL Archive, July 2013. Proc 10th Int.Conf. Computability and Complexity in Analysis (CCA). URL: https://hal.inria.fr/hal-00915973.

[bib.bib8] [8] Anka Gajentaan and Mark H Overmars. On a class of O( $n^{2}$ ) problems in computational geometry. Computational Geometry, 5(3):165–185, 1995. doi:10.1016/0925-7721(95)00022-2.

[bib.bib9] [9] Mikhail Gromov. Groups of polynomial growth and expanding maps. Publications Mathématiques de L’Institut des Hautes Scientifiques, 53:53–78, 1981. doi:10.1007/BF02698687.

[bib.bib10] [10] Emmanuel Hainry, Bruce M. Kapron, Jean-Yves Marion, and Romain Péchoux. Declassification policy for program complexity analysis. In Pawel Sobocinski, Ugo Dal Lago, and Javier Esparza, editors, Proc. 39th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2024, Tallinn, Estonia, pages 41:1–41:14. ACM, 2024. doi:10.1145/3661814.3662100.

[bib.bib11] [11] Emmanuel Hainry and Romain Péchoux. Higher order interpretation for higher order complexity. In Thomas Eiter and David Sands, editors, LPAR-21, 21st International Conference on Logic for Programming, Artificial Intelligence and Reasoning, Maun, Botswana, May 7-12, 2017, volume 46 of EPiC Series in Computing, pages 269–285. EasyChair, 2017. doi:10.29007/1TKW.

[bib.bib12] [12] Peter Hertling. Topological complexity with continuous operations. Journal of Complexity, 12(4):315–338, 1996. doi:10.1006/jcom.1996.0021.

[bib.bib13] [13] Bruce M. Kapron and Stephen A. Cook. A new characterization of type-2 feasibility. SIAM J. Comput., 25(1):117–132, 1996. doi:10.1137/S0097539794263452.

[bib.bib14] [14] Bruce M. Kapron and Florian Steinberg. Type-two polynomial-time and restricted lookahead. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS ’18, pages 579–588, New York, NY, USA, 2018. Association for Computing Machinery. doi:10.1145/3209108.3209124.

[bib.bib15] [15] Akitoshi Kawamura and Stephen A. Cook. Complexity theory for operators in analysis. ACM Trans. Comput. Theory, 4(2):5:1–5:24, 2012. doi:10.1145/2189778.2189780.

[bib.bib16] [16] Akitoshi Kawamura, Florian Steinberg, and Holger Thies. Second-order linear-time computability with applications to computable analysis. In Proc. 15th Conf. on Theory and Applications of Models of Computation (TAMC), pages 337–358, Berlin, Heidelberg, 2019. Springer-Verlag. doi:10.1007/978-3-030-14812-6_21.

[bib.bib17] [17] Ker-I Ko. Complexity Theory of Real Functions, volume 3 of Progress in theoretical computer science. Birkhäuser / Springer, 1991. doi:10.1007/978-1-4684-6802-1.

[bib.bib18] [18] Ivan Koswara, Gleb Pogudin, Svetlana Selivanova, and Martin Ziegler. Bit-complexity of classical solutions of linear evolutionary systems of partial differential equations. Journal of Complexity, 76:101727, 2023. doi:10.1016/j.jco.2022.101727.

[bib.bib19] [19] David A. Levin and Yuval Peres. Markov chains and mixing times. American Mathematical Society, Providence, Rhode Island, 2009.

[bib.bib20] [20] Donghyun Lim. Degrees of second and higher-order polynomials. 4th Workshop on Mathematical Logic and its Applications, March 2021. URL: http://jaist.ac.jp/event/mla2021.

[bib.bib21] [21] Donghyun Lim and Martin Ziegler. Degrees of second and higher-order polynomials. arXiv CoRR, 2305.03439, 2023. doi:10.48550/arXiv.2305.03439.

[bib.bib22] [22] Donghyun Lim and Martin Ziegler. Quantitative coding and complexity theory of Continuous data: Part I. J. ACM, 72(1):4:1–4:39, 2025. doi:10.1145/3705609.

[bib.bib23] [23] George G. Lorentz. Metric entropy and approximation, volume 72. AMS, 1996.

[bib.bib24] [24] Kurt Mehlhorn. Polynomial and abstract subrecursive classes. Journal of Computer and System Sciences, 12(2):147–178, 1976. doi:10.1016/S0022-0000(76)80035-9.

[bib.bib25] [25] Eike Neumann and Florian Steinberg. Parametrised second-order complexity theory with applications to the study of interval computation. Theor. Comput. Sci., 806:281–304, 2020. doi:10.1016/j.tcs.2019.05.009.

[bib.bib26] [26] Jürgen Richter-Gebert, Bernd Sturmfels, and Thorsten Theobald. First steps in tropical geometry. Idempotent Mathematics and Mathematical Physics, 377:289–317, 2005.

[bib.bib27] [27] Jon G. Riecke and Ramesh Subrahmanyam. Conditions for the completeness of functional and algebraic equational reasoning. Mathemat.Structures Computer Science, 9(6):651–685, 1999. doi:10.1017/S0960129599002807.

[bib.bib28] [28] Ernst Specker, Norbert Hungerbühler, and Micha Wasem. Polyfunctions over commutative rings. J. Algebra and Applications, 23(01):2450014, 2024. doi:10.1142/S0219498824500142.

[bib.bib29] [29] Volker Strassen. Gaussian elimination is not optimal. Numer.Mathematik, 13:354–356, 1969.

[bib.bib30] [30] Mike Townsend. Complexity for type-2 relations. Notre Dame Formal Logic, 31(2):241–262, 1990. doi:10.1305/NDJFL/1093635419.

[bib.bib31] [31] Martin Ziegler. Hyper-degrees of 2nd-order polynomial-time reductions. Technical report, Dagstuhl Seminar #15392, 2016. abstract §3.20. doi:10.4230/DagRep.5.9.77.

	$\displaystyle 1\circ\operatorname{\textbf{P}}\;\mathrel{\begin{matrix}% \includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}% \end{matrix}}\;1,\qquad\operatorname{\textbf{N}}\circ\operatorname{\textbf{P}}% \;\mathrel{\begin{matrix}\includegraphics{dagpub-standalone-dagpub-svg-2026-02% -03-16-22-40.pdf2svg.svg}\end{matrix}}\;\operatorname{\textbf{P}}\;\mathrel{% \begin{matrix}\includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-4% 0.pdf2svg.svg}\end{matrix}}\;\operatorname{\textbf{P}}\circ\operatorname{% \textbf{N}},\qquad(\operatorname{\textbf{P}}\circ\operatorname{\textbf{Q}})% \circ\operatorname{\textbf{R}}\;\mathrel{\begin{matrix}\includegraphics{dagpub% -standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\;% \operatorname{\textbf{P}}\circ(\operatorname{\textbf{Q}}\circ\operatorname{% \textbf{R}}),$
	$\displaystyle(\operatorname{\textbf{P}}+\operatorname{\textbf{Q}})\circ% \operatorname{\textbf{R}}\;\mathrel{\begin{matrix}\includegraphics{dagpub-% standalone-dagpub-svg-2026-02-03-16-22-40.pdf2svg.svg}\end{matrix}}\;(% \operatorname{\textbf{P}}\circ\operatorname{\textbf{R}})+(\operatorname{% \textbf{Q}}\circ\operatorname{\textbf{R}}),\qquad(\operatorname{\textbf{P}}% \cdot\operatorname{\textbf{Q}})\circ\operatorname{\textbf{R}}\;\mathrel{\begin% {matrix}\includegraphics{dagpub-standalone-dagpub-svg-2026-02-03-16-22-40.pdf2% svg.svg}\end{matrix}}\;(\operatorname{\textbf{P}}\circ\operatorname{\textbf{R}% })\cdot(\operatorname{\textbf{R}}\circ\operatorname{\textbf{R}})$

	$\displaystyle\deg(1)=0,\quad\deg(\operatorname{\textbf{N}})=1,\qquad\deg(% \operatorname{\textbf{P}}+\operatorname{\textbf{Q}})=\max\{\deg(\operatorname{% \textbf{P}}),\deg(\operatorname{\textbf{Q}})\},$
	$\displaystyle\deg(\operatorname{\textbf{P}}\cdot\operatorname{\textbf{Q}})=% \deg(\operatorname{\textbf{P}})+\deg(\operatorname{\textbf{Q}}),\qquad\deg(% \operatorname{\textbf{P}}\circ\operatorname{\textbf{Q}})=\deg(\operatorname{% \textbf{P}})\cdot\deg(\operatorname{\textbf{Q}}).$

Degrees of Second and Higher-Order Polynomials

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Motivating Examples and Overview

Example 1.

▶ Remark 2.

1.1 Arctic First-Order Polynomials

Definition 3.

Lemma 4.

2 Second-Order Polynomials

Definition 5.

Definition 6.

Theorem 7.

2.1 Second-Order Polynomial Degree

▶ Remark 8.

Definition 9.

▶ Remark 10.

2.2 Second-Order Polynomial Compositions

Definition 11.

Proposition 12.

▶ Remark 13.

2.3 Examples and Applications

Example 14 (String Functionals).

Example 15.

Example 16 (1D Real Function Inversion).

Example 17 (Continuous Operator in Functional Analysis).

2.4 Arctic Second-Order Polynomials

Definition 18.

Example 19.

3 Higher-Order Polynomials and Degrees

3.1 First and Second-Order Case Revisited

▶ Remark 20 (First-Order Polynomials, Revisited).

▶ Remark 21 (Second-Order Polynomials, Revisited).

3.2 Third-Order Polynomials and Degrees

▶ Remark 22.

Definition 23.

Example 24.

Theorem 25.

Example 26.

3.3 Polynomials and Degrees of Arbitrary Order

Definition 27.

Theorem 28.

Conjecture 29.

3.4 Simply Typed Lambda Calculus Perspective

▶ Remark 30.

References

Appendix A Proof of Example 16b

Appendix B Selected Further Deferred Proofs

Proof of Example 19.

Proof of Example 14iv+v.

Proof of Example 17iii.

$\blacktriangleright$ Remark 2.

$\blacktriangleright$ Remark 8.

$\blacktriangleright$ Remark 10.

$\blacktriangleright$ Remark 13.

$\blacktriangleright$ Remark 20 (First-Order Polynomials, Revisited).

$\blacktriangleright$ Remark 21 (Second-Order Polynomials, Revisited).

$\blacktriangleright$ Remark 22.

$\blacktriangleright$ Remark 30.