text:
\begin{document}

\title{Toward a language theoretic proof \\ of the four color theorem}

\author{Bobbe Cooper}
\address{
	School of Mathematics \\
	206 Church St.\ S.E. \\
	Minneapolis, MN 55455, USA
}
\author{Eric Rowland}
\address{
	School of Computer Science \\
	University of Waterloo \\
	Waterloo, ON N2L 3G1, Canada
}
\author{Doron Zeilberger}
\address{
	Department of Mathematics \\
	Rutgers University \\
	Piscataway, NJ 08854, USA
}

\date{November 22, 2011}

\thanks{The second author was supported in part by NSF grant DMS-0239996; the third author was supported in part by NSF grant DMS-0901226.}

\begin{abstract}
This paper considers the problem of showing that every pair of binary trees with the same number of leaves parses a common word under a certain simple grammar.  We enumerate the common parse words for several infinite families of tree pairs and discuss several ways to reduce the problem of finding a parse word for a pair of trees to that for a smaller pair.  The statement that every pair of trees has a common parse word is equivalent to the statement that every planar graph is four-colorable, so the results are a step toward a language theoretic proof of the four color theorem.
\end{abstract}

\maketitle
\markboth{Cooper, Rowland, and Zeilberger}{Toward a language theoretic proof of the four color theorem}

\section{Introduction}\label{introduction}

Let $G$ be the context-free grammar with start symbols $0, 1, 2$ and formation rules $0 \to 12$, $0 \to 21$, $1 \to 02$, $1 \to 20$, $2 \to 01$, $2 \to 10$.  An $n$-leaf tree $T$ \emph{parses} a length-$n$ word $w$ on $\{0, 1, 2\}$ if $T$ is a valid derivation tree for $w$ under the grammar $G$; that is, there is a labeling of the vertices of $T$ compatible with the formation rules such that the leaves of $T$, from left to right, are labeled with the letters of $w$.  For example, the tree
\[
	\vcentergraphics{binarytree7-7}
\]
parses the word $0110212$, as can be seen by this labeling:
\[
	\vcentergraphics{binarytree7-7labeled}
\]
Note that labeling the leaves of a tree uniquely determines a labeling of the internal vertices under $G$ if a valid labeling exists.

Certainly $G$ is \emph{ambiguous} --- there exist distinct trees that parse the same word; for example, the trees
\[
	\vcentergraphics{binarytree3-2} \qquad \vcentergraphics{binarytree3-1}
\]
both parse $010$.  To take a somewhat larger example, the trees
\[
	\vcentergraphics{binarytree7-7} \qquad \vcentergraphics{binarytree7-64}
\]
both parse the word $0110212$:
\[
	\vcentergraphics{binarytree7-7labeled} \qquad \vcentergraphics{binarytree7-64labeled}
\]

However, something much stronger can be said about this grammar.

\begin{theorem}\label{main}
The grammar $G$ is totally ambiguous.
\end{theorem}

That is, every pair of derivation trees with the same number of leaves has at least one word that they both parse.  Kauffman~\cite{Kauffman} proved this theorem (in a slightly different form, as we describe below) by showing that it is equivalent to the four color theorem --- the statement that every planar graph is four-colorable.  The four color theorem was proved by Appel, Haken, and Koch~\cite{Appel--Haken, Appel--Haken--Koch} using substantial computing resources.  The hope of the present authors is that a direct proof of Theorem~\ref{main} will be shorter than the known proofs of the four color theorem, thereby providing a shorter proof of the four color theorem.

In this paper we describe first results in this direction.
First we show that Theorem~\ref{main} is equivalent to Kauffman's formulation.
Section~\ref{parameterized families} determines explicit common parse words for several simple parameterized families of tree pairs.
In Section~\ref{general families} we establish existence of parse words for more general families.
In Section~\ref{turn trees} we enumerate the common parse words of a $3$-parameter family of tree pairs.
We conclude in Section~\ref{reducing} by discussing in more generality methods of reducing the problem of finding a common parse word for a pair of trees.

A \emph{Mathematica} package~\cite{ParseWords} and a Maple package~\cite{LOU} that accompany this paper and facilitate the discovery of the results we present can be downloaded from the respective web sites of the second and third authors.

\section{Relationship to the cross product}\label{equivalence}

The set of possible derivation trees under $G$ is the set of \emph{binary trees} --- trees in which each vertex has either $0$ or $2$ children.  (All trees in the paper are rooted and ordered.)

Let $|w|$ be the length of the word $w$, and let $|w|_i$ be the number of occurrences of the letter $i$ in $w$.

\begin{proposition}\label{root label}
Let $w$ be a word of length $n$ on $\{0, 1, 2\}$ and $T$ an $n$-leaf binary tree that parses $w$.  Then for some permutation $(r,s,t)$ of $(0,1,2)$,
\[
	|w|_s \equiv |w|_t \nequiv |w|_r \equiv |w| \mod 2.
\]
Moreover, the root of $T$ receives the label $r$ when parsing $w$.
\end{proposition}

\begin{proof}
The congruence holds for the three words of length $1$, and the derivation rules of $G$ preserve it because all four terms change parity with each rule application.
\end{proof}

It follows that if the parities of $|w|_0$, $|w|_1$, and $|w|_2$ are equal then no tree parses $w$ under $G$.  If on the other hand the parity of $|w|_r$ differs from the other two, then $r$ is an invariant of $w$ in the sense that any tree parsing $w$ has its root labeled $r$.

Kauffman~\cite{Kauffman} formulated Theorem~\ref{main} not in terms of a grammar but in terms of the cross product on the standard unit vectors $\ihat, \jhat, \khat$ in $\R^3$.
The cross product satisfies
\begin{align*}
	\ihat \times \jhat &= (-\ihat) \times (-\jhat) = (-\jhat) \times \ihat = \jhat \times (-\ihat) = \khat, \\
	\jhat \times \khat &= (-\jhat) \times (-\khat) = (-\khat) \times \jhat = \khat \times (-\jhat) = \ihat, \\
	\khat \times \ihat &= (-\khat) \times (-\ihat) = (-\ihat) \times \khat = \ihat \times (-\khat) = \jhat.
\end{align*}
Further, for every vector $v \in \R^3$ we have
\begin{align*}
	v \times v &= v \times (-v) = 0, \\
	v \times 0 &= 0 \times v = 0.
\end{align*}
The cross product on $\R^3$ is not associative, so in general the expression $v_1 \times v_2 \times \cdots \times v_n$ is ambiguous; to evaluate it for a given tuple $(v_1, v_2, \dots, v_n)$ we must choose an order in which to compute the $n-1$ cross products.
Let us call such an order an \emph{$n$-bracketing}.
Kauffman showed that the four color theorem is equivalent to the statement that for every pair of $n$-bracketings there exists an $n$-tuple $(v_1, v_2, \dots, v_n) \in \{\ihat, \jhat, \khat\}^n$ such that the two bracketings of $v_1 \times v_2 \times \cdots \times v_n$ evaluate to the same nonzero vector.

We now develop tools to show that Theorem~\ref{main} is equivalent to Kauffman's statement.
Roughly speaking, we show that we can replace $\pm \ihat \to 0$, $\pm \jhat \to 1$, and $\pm \khat \to 2$.
It is easy to see that $n$-bracketings are in bijection with $n$-leaf binary trees.
Therefore, given an $n$-bracketing of $v_1 \times v_2 \times \cdots \times v_n$, one may label each internal vertex of the corresponding binary tree with the cross product of the labels of its children (in order).
The condition that the bracketing does not evaluate to $0$ is equivalent to the condition that the evaluation does not encounter the product $v \times v$ or $v \times (-v)$, hence our formation rules for the grammar $G$.

Each $(v_1, v_2, \dots, v_n) \in \{\ihat, \jhat, \khat\}^n$ possesses an invariant analogous to that of Proposition~\ref{root label}.
To see what this invariant is, consider the quaternion group, whose elements are $Q = \{1, i, j, k, -1, -i, -j, -k\}$ and whose binary operation $\cdot$ satisfies
\begin{align*}
	i \cdot j &= (-i) \cdot (-j) = (-j) \cdot i = j \cdot (-i) = k, \\
	j \cdot k &= (-j) \cdot (-k) = (-k) \cdot j = k \cdot (-j) = i, \\
	k \cdot i &= (-k) \cdot (-i) = (-i) \cdot k = i \cdot (-k) = j,
\end{align*}
as well as identities such as $(-1) \cdot (-1) = 1$ and $(-1) \cdot i = -i$ suggested by the notation.
Further, for $q \in \{i, j, k, -i, -j, -k\}$ we have $q \cdot q = -1$ and $q \cdot (-q) = 1$.
Consider $\phi : \{\ihat, \jhat, \khat, -\ihat, -\jhat, -\khat\} \to \{i, j, k, -i, -j, -k\}$ mapping
\begin{align*}
	\phi(\ihat) &= i, \qquad \phi(-\ihat) = -i, \\
	\phi(\jhat) &= j, \qquad \phi(-\jhat) = -j, \\
	\phi(\khat) &= k, \qquad \phi(-\khat) = -k.
\end{align*}
The map $\phi$ is a ``partial homomorphism'' in the sense that $\phi(v_1 \times v_2) = \phi(v_1) \cdot \phi(v_2)$ if $v_1 \neq v_2$ and $v_1 \neq -v_2$.
This property allows us to establish the following invariant.

\begin{proposition}\label{root vector}
Let $(v_1, v_2, \dots, v_n) \in \{\ihat, \jhat, \khat\}^n$, and choose a bracketing of $v_1 \times v_2 \times \cdots \times v_n$ that does not evaluate to the zero vector.
Then this bracketing evaluates to $\phi^{-1}(\phi(v_1) \cdot \phi(v_2) \cdots \phi(v_n))$.
\end{proposition}

\begin{proof}
Since the bracketing of $v_1 \times v_2 \times \cdots \times v_n$ does not evaluate to $0$, each of the $n-1$ cross products is an operation on two linearly independent vectors.
Therefore we may emulate the evaluation of the bracketing in $Q$ rather than in $\R^3$, because replacing $\times$ with $\cdot$ is consistent with $\phi$.
Since $\cdot$ is associative, the bracketing evaluates to $\phi(v_1) \cdot \phi(v_2) \cdots \phi(v_n)$ in $Q$.
Moreover, since we do not encounter $0$ in $\R^3$, we do not encounter $-1$ or $1$ in $Q$; in particular, $\phi(v_1) \cdot \phi(v_2) \cdots \phi(v_n) \in \{i, j, k, -i, -j, -k\}$, and therefore $\phi^{-1}(\phi(v_1) \cdot \phi(v_2) \cdots \phi(v_n))$ exists.
\end{proof}

A result of Proposition~\ref{root vector} is that we can drop the condition in Kauffman's statement that the two bracketings evaluate to the same vector.
Therefore the four color theorem is equivalent to the statement that for every pair of $n$-bracketings there exists an $n$-tuple $(v_1, v_2, \dots, v_n) \in \{\ihat, \jhat, \khat\}^n$ such that the two bracketings of $v_1 \times v_2 \times \cdots \times v_n$ evaluate to nonzero vectors.

Consider the homomorphism $\sigma : Q \to Q/\{1, -1\} \cong V$, where $V = \{e, 0, 1, 2\}$ is the Klein four-group, $e = \{1, -1\}$ is the identity element, $0 = \{i, -i\}$, $1 = \{j, -j\}$, and $2 = \{k, -k\}$.
Let $\tau : \{\ihat, \jhat, \khat\} \to \{0, 1, 2\}$ be defined by $\tau(v) = \sigma(\phi(v))$.
In other words, $\tau$ removes the hat and forgets the sign.
Since $\sigma$ is a homomorphism, evaluating $T_1$ and $T_2$ at $(v_1, v_2, \dots, v_n) \in \{\ihat, \jhat, \khat\}^n$ results in nonzero vectors if and only if $\tau(v_1) \tau(v_2) \cdots \tau(v_n)$ is a parse word for $T_1$ and $T_2$.
Therefore, for $n$-leaf binary trees $T_1$ and $T_2$, the $n$-tuples $(v_1, v_2, \dots, v_n) \in \{\ihat, \jhat, \khat\}^n$ that evaluate to nonzero vectors when bracketed by $T_1$ and $T_2$ are in bijection with words $w \in \{0, 1, 2\}^n$ that are parsed by both $T_1$ and $T_2$.
It follows that Theorem~\ref{main} is equivalent to the four color theorem.

\section{Parameterized families}\label{parameterized families}

In this section we introduce several families of binary trees and enumerate the parse words of several pairs of these trees.
First we establish some additional terminology.

If $T$ parses a word $w$ on $\{0, 1, 2\}$, then $T$ also parses all words obtained from $w$ by permuting the letters in the alphabet.  Let $\ParseWords(T_1, T_2)$ be the set of equivalence classes (under permutations) of words parsed by both trees $T_1$ and $T_2$.  We abuse notation slightly by writing a representative of each equivalence class.  For example, it turns out that for the pair of $7$-leaf trees mentioned in Section~\ref{introduction} there is only one equivalence class of parse words, so for those trees we write
\[
	\ParseWords(T_1, T_2) = \{0110212\}.
\]
Often we will take this representative to be the word in the equivalence class which is lexicographically first --- words of the form $0$ or $0^k 1 v$.
However, we will depart from this convention when convenient.
The four color theorem is equivalent to the statement that for every pair of $n$-leaf binary trees $T_1$ and $T_2$ we have $\ParseWords(T_1,T_2) \neq \{\}$.

The \emph{level} of a vertex is its distance from the root.  That is, the root lies on level $0$, the root's children lie on level $1$, and so on.

A \emph{path tree} is a binary tree with at most two vertices in each level.  The $5$-leaf path trees are as follows.
\[
	\includegraphics{pathtrees5}
\]
The two leaves on level $n-1$ in an $n$-leaf path tree are called the \emph{bottom leaves}.

The set of $n$-leaf path trees is in trivial bijection to the set $\{l, r\}^{n-2}$ of $(n-2)$-length words on $\{l, r\}$:  Since each level has at most two vertices, at most one vertex in each level has children, so we may form a word that records which child --- left or right --- has children at each level.  We shall use this bijection to define several families of trees.

Because of their linear structure, path trees are simpler to work with than binary trees in general, so the emphasis of this paper is on path trees.  Indeed, several infinite families of pairs of path trees can be shown to satisfy Theorem~\ref{main} directly and have only a few parse words.  We take up this task now.  Some of the proofs work by finding out where the local conditions imposed by the two trees force a unique labeling and then just working out the consequences, so in some cases it may be quicker to prove the theorem for yourself than to read the proof provided.

Let $\LeftCombTree(n)$ be the $n$-leaf path tree corresponding to the word $l^{n-2}$.  The left comb trees for $n \geq 2$ are pictured below.
\[
	\includegraphics{leftcombtrees}
\]
Let $\RightCombTree(n)$ be the $n$-leaf path tree corresponding to $r^{n-2}$; $\RightCombTree(n)$ is the left--right reflection of $\LeftCombTree(n)$.  We warm up with some \emph{comb}i\-na\-tor\-ics.

\begin{theorem}\label{comb-comb}
$\ParseWords(\LeftCombTree(n), \RightCombTree(n)) =$
\[
	\begin{cases}
		\left\{01^{n-2}2\right\}	& \text{if $n \geq 2$ is even} \\
		\left\{01^{n-2}0\right\}	& \text{if $n \geq 3$ is odd.}
	\end{cases}
\]
\end{theorem}

\begin{proof}
We build a common parse word from left to right --- up $\LeftCombTree(n)$ and down $\RightCombTree(n)$.  At every leaf, each tree will eliminate one possible label, so the parse word will turn out to exist and be unique.

The case $n=2$ can be established by testing all words of length $2$, so let $n \geq 3$.  Without loss of generality we may label the first two leaves $0$ and $1$.  It follows from this that the root of $\RightCombTree(n)$ receives the label $1$, the non-leaf (internal) vertex on the second level of $\RightCombTree(n)$ receives $2$, and therefore the internal vertex on the third level of $\RightCombTree(n)$ receives $0$.  This implies (from the right comb) that the third leaf cannot receive $0$.  However, from the left comb we find that the third leaf cannot receive $2$.  Therefore the third leaf receives $1$.  For the fourth leaf, the right comb precludes $2$ and the left comb precludes $0$, so the fourth leaf receives $1$.  Likewise all the way down the word through leaf $n-1$.  The internal vertex labels in each tree alternate between $0$ and $2$, except for the root which receives 1.  If $n$ is odd then the lowest internal vertex in the right comb receives $2$, so that the last leaf receives $0$; if $n$ is even then this internal vertex receives $0$, and the last leaf receives $2$.
\end{proof}

Note from the proof of this theorem that the internal labels corresponding to a common parse word of $\LeftCombTree(n)$ and $\RightCombTree(n)$ will match (top to bottom) if $n$ is odd, and will differ by the permutation which swaps $0$ and $2$ if $n$ is even.

Let $\LeftTurnTree(m,n)$ be the $(m+n)$-leaf path tree corresponding to $l^m r^{n-2}$, and let $\RightTurnTree(m,n)$ be the tree corresponding to $r^m l^{n-2}$.  Each of these trees is formed by ``gluing'' together two comb trees.  For example,
\[
	\LeftTurnTree(2,3) = \vcentergraphics{binarytree5-13}.
\]
The following theorem is a special case of the general treatment of two turn trees given in Section~\ref{turn trees}.

\begin{theorem}\label{turn-turn}
For $m \geq 1$,
\begin{multline*}
	\ParseWords(\LeftTurnTree(m, n), \RightTurnTree(1, m + n - 1)) = \\
	\begin{cases}
		\left\{0 0 1^{n-3} 2 0^m, 0 2 1^{n-3} 0 0^m\right\}	& \text{if $n \geq 3$ is odd} \\
		\left\{0 2 1^{n-3} 2 0^m, 0 0 1^{n-3} 0 0^m\right\}	& \text{if $n \geq 4$ is even.}
	\end{cases}
\end{multline*}
\end{theorem}

\begin{proof}
Without loss of generality, label the last leaf of each tree $0$.  The roots of the trees receive the same label, and thus the respective parents of the last leaf of each tree must receive $1$ and $2$ in some order, and the first leaf must be labeled $0$.  This implies that the last $m$ leaves are labeled $0$.  There are (up to permutation of $1$ and $2$) three possible options for the labels of leaves $n-1$ and $n$ (the bottom leaves of $\LeftTurnTree(m, n)$), namely $12$, $10$, and $01$.  Each of the first two options can be seen to yield a unique common parse word as given in the statement of the theorem.  The third option, in which leaves $n-1$ and $n$ are labeled $01$, is not valid, since then the sibling of leaf $n+1$ in $\RightTurnTree(1, m + n - 1)$ is labeled $0$, which contradicts leaf $n+1$ receiving $0$.
\end{proof}

If $w = w_1 w_2 \cdots w_m$ is a word of length $m$ and $x$ is a rational number whose denominator (in lowest terms) divides $m$, let
\[
	w^x = w^{\lfloor x \rfloor} w_1 w_2 \cdots w_{m \cdot (x - \lfloor x \rfloor)}
\]
be the word consisting of repeated copies of $w$ truncated at $m x$ letters.  For example, $(lr)^{7/2} = lrlrlrl$.

Let $\LeftCrookedTree(n)$ be the path tree corresponding to $(lr)^{(n-2)/2}$.  The left crooked trees for $n \geq 2$ are as follows.
\[
	\includegraphics{leftcrookedtrees}
\]
Let $\RightCrookedTree(n)$ be the path tree corresponding to $(rl)^{(n-2)/2}$ --- the left--right reflection of $\LeftCrookedTree(n)$.

The next two results determine the common parse words of a comb tree and the completely crooked trees of the same size.  Let $w^R$ be the left--right reversal of the word $w$.  Let $\Mod(n,3)$ be the smallest nonnegative integer congruent to $n$ modulo $3$.

\begin{theorem}\label{comb-crooked}
$\ParseWords(\LeftCombTree(n), \RightCrookedTree(n)) =$
\[
	\begin{cases}
		\left\{ \Mod(1-n,3) \left((012)^{n/6}\right)^R (012)^{(n-2)/6} \right\}		& \text{if $n \geq 2$ is even} \\
		\left\{ \Mod(1-n,3) \left((012)^{(n-3)/6}\right)^R (012)^{(n+1)/6} \right\}	& \text{if $n \geq 3$ is odd.}
	\end{cases}
\]
\end{theorem}

\begin{proof}
One checks that for $n=2$ the set of equivalence classes of parse words is $\{20\}$.

Inductively, assume that $\LeftCombTree(n-1)$ and $\RightCrookedTree(n-1)$ parse the word claimed and that this is the only word they both parse (up to permutations of the alphabet).  For even $n-1$, the two bottom leaves of $\RightCrookedTree(n-1)$ are leaves $\frac{n-1}{2}$ and $\frac{n+1}{2}$.  For odd $n-1$, they are leaves $\frac{n}{2}$ and $\frac{n+2}{2}$.  Observe that for even $n-1$ the right bottom leaf of $\RightCrookedTree(n-1)$ receives $0$, and for odd $n-1$ the left bottom leaf of $\RightCrookedTree(n-1)$ receives $0$.  For $n-1 \geq 4$ these are respectively the first and second of the two consecutive $0$s in the parse word.

We attach $\smalltree{2}{1}$ at the bottom of $\RightCrookedTree(n-1)$ to form $\RightCrookedTree(n)$ and insert $\smalltree{2}{1}$ at the corresponding place in $\LeftCombTree(n-1)$ to form $\LeftCombTree(n)$.  Label the new bottom leaves of $\RightCrookedTree(n)$ $12$ if $n-1$ is even and $21$ if $n-1$ is odd; we can label the corresponding leaves of $\LeftCombTree(n)$ the same by labeling their respective neighboring internal vertices $0$ and $1$ if $n-1$ is even and $0$ and $2$ if $n-1$ is odd.  The permutation $0 \to 2, 1 \to 0, 2 \to 1$ puts the new word in the form given in the theorem.

This process is reversible, so every parse word for $n$ comes from a parse word for $n-1$.
\end{proof}

The next theorem follows immediately from the previous theorem by labeling $\LeftCombTree(n)$ and $\RightCrookedTree(n)$ with a common parse word and then attaching the root of each tree as the left leaf of $\smalltree{2}{1}$.

\begin{theorem}\label{comb-crooked2}
$\ParseWords(\LeftCombTree(n), \LeftCrookedTree(n)) =$
\[
	\begin{cases}
		\begin{array}{l}
			\Big\{ \Mod(2-n,3) \left((012)^{(n-1)/6}\right)^R (012)^{(n-3)/6} \Mod(2-n,3), \\
			\phantom{\Big\{} \Mod(2-n,3) \left((012)^{(n-1)/6}\right)^R (012)^{(n-3)/6} \Mod(-n,3) \Big\}
		\end{array}	& \text{if $n \geq 3$ is odd} \\
		\begin{array}{l}
			\Big\{ \Mod(2-n,3) \left((012)^{(n-4)/6}\right)^R (012)^{n/6} \Mod(2-n,3), \\
			\phantom{\Big\{} \Mod(2-n,3) \left((012)^{(n-4)/6}\right)^R (012)^{n/6} \Mod(-n,3) \Big\}
		\end{array}	& \text{if $n \geq 4$ is even.}
	\end{cases}
\]
\end{theorem}

\begin{theorem}\label{crooked-crooked count}
For $n \geq 2$,
\[
	|\ParseWords(\LeftCrookedTree(n), \RightCrookedTree(n))| = 2^{\lfloor n/2 \rfloor - 1}.
\]
\end{theorem}

\begin{proof}
The cases $n = 2$ and $n = 3$ are easily verified.  In particular, every parse word of the $3$-leaf pair consisting of
\[
	\vcentergraphics{binarytree3-2} \qquad \vcentergraphics{binarytree3-1}
\]
is of the form $aba$ for $a \neq b$, where the two roots also get labeled $b$.

Let $n$ be odd.  Consider inductively extending $\LeftCrookedTree(n - 2)$ and $\RightCrookedTree(n - 2)$ by
\[
	\vcentergraphics{binarytree3-2} \qquad \vcentergraphics{binarytree3-1}
\]
respectively to obtain $\LeftCrookedTree(n)$ and $\RightCrookedTree(n)$.  Because the three new leaves are leaves $(n-1)/2$, $(n+1)/2$, and $(n+3)/2$ in both $\LeftCrookedTree(n)$ and $\RightCrookedTree(n)$, every parse word
\[
	w_1 w_2 \cdots w_{(n-3)/2} b w_{(n+1)/2} \cdots w_{n-3} w_{n-2}
\]
for the two $(n-2)$-leaf crooked trees can be extended to a parse word
\[
	w_1 w_2 \cdots w_{(n-3)/2} a b a w_{(n+1)/2} \cdots w_{n-3} w_{n-2}
\]
for the two $n$-leaf crooked trees.  Moreover, every parse word for the two $n$-leaf crooked trees can be obtained in this way.  Since there are two choices for $a$, there are twice as many parse words for the $n$-leaf crooked trees as for the $(n-2)$-leaf crooked trees, which establishes the statement for odd $n$; we see that $w = w_1 w_2 \cdots w_{n-1} w_n$ is a parse word for $\LeftCrookedTree(n)$ and $\RightCrookedTree(n)$ if and only if $w_i = w_{n+1-i} \neq w_{(n+1)/2}$ for $1 \leq i \leq \frac{n-1}{2}$.

Let $n$ be even.  Then every parse word of the $n$-leaf crooked trees can be obtained by extending a parse word $w_1 w_2 \cdots w_{n/2 - 1} b w_{n/2 + 1} \cdots w_{n-2} w_{n-1}$ of the $(n-1)$-leaf crooked trees.  Every parse word of $\smalltree{2}{1}$ in which the root receives label $b$ is of the form $ac$, where $a \neq b$ and $c \neq b$, so there are twice as many parse words for the $n$-leaf crooked trees as for the $(n-1)$-leaf crooked trees, which establishes the statement for even $n$.  Specifically, $w = w_1 w_2 \cdots w_{n-1} w_n$ is a parse word for $\LeftCrookedTree(n)$ and $\RightCrookedTree(n)$ if and only if $w_{n/2} \neq w_{n/2 + 1}$ and for some $b \in \{0, 1, 2\}$ we have $w_i = w_{n+1-i} \neq b$ for $1 \leq i \leq \frac{n}{2} - 1$.
\end{proof}

\section{General families}\label{general families}

Presumably explicit parse words can be found for various other parameterized families of tree pairs, but we now take a more general approach and establish results for tree pairs in which at least one of the trees does not come from a simple parameterized family.  Some of these results will be used in Section~\ref{turn trees}.  Note that, where stated, these results apply to not just path trees but binary trees in general.

\begin{proposition}\label{shared bottom leaf}
Let $n \geq 3$.  If the $i$th leaf is a bottom leaf in two $n$-leaf path trees, then the trees both parse the word $0^{k-1} 1 0^{n-k}$ for some $2 \leq k \leq n - 1$.
\end{proposition}

For example, this proposition applies to the pair in Theorem~\ref{crooked-crooked count} consisting of $\LeftCrookedTree(n)$ and $\RightCrookedTree(n)$.

\begin{proof}
If $i = 1$ then the second leaf is also a bottom leaf in both trees, so let $k = 2$; similarly, if $i = n$, let $k = n-1$.  If $2 \leq i \leq n-1$, let $k = i$.  Labeling the $k$th leaf $1$ and all other leaves $0$ produces a valid labeling of both trees because the internal vertices of the two trees on each level receive the same label, namely alternating between $2$ and $1$.
\end{proof}

We now give two propositions regarding extending a pair of binary trees by $\smalltree{2}{1}$.

\begin{proposition}\label{bottom-bottom}
Suppose $T_1'$ and $T_2'$ are $n$-leaf binary trees with a common parse word.  Extend each tree by attaching $\smalltree{2}{1}$ to leaf $i$, obtaining $T_1$ and $T_2$ respectively.  Then
\[
	|\ParseWords(T_1, T_2)| = 2 |\ParseWords(T_1', T_2')|.
\]
In particular, $T_1$ and $T_2$ have a common parse word.
\end{proposition}

\begin{proof}
Let $w$ be a parse word of $T_1'$ and $T_2'$.  Without loss of generality we may assume that $w_i = 0$.  Replacing $w_i$ by $12$ or $21$ produces a word that both $T_1$ and $T_2$ parse, and every parse word for the pair arises uniquely in this way.
\end{proof}

In the next proposition we consider extending a tree $T$ by inserting $\smalltree{2}{1}$ into the tree at an internal vertex to ``duplicate'' a leaf.  Fix $i$, and let $S$ be the tree hanging from the sibling vertex of leaf $i$.  Remove $S$ from its position, attach $\smalltree{2}{1}$ to the sibling of leaf $i$, and then reattach $S$ to a leaf of the new $\smalltree{2}{1}$ as follows.  If leaf $i$ is a left leaf, attach $S$ to the right leaf of the new $\smalltree{2}{1}$; if leaf $i$ is a right leaf, attach $S$ to the left leaf.  Therefore if leaf $i$ in $T$ is a left leaf, then leaves $i$ and $i+1$ in the extended tree are both left leaves, and if leaf $i$ in $T$ is a right leaf, then leaves $i$ and $i+1$ in the extended tree are right leaves.  We refer to this operation as \emph{duplicating} leaf $i$.

\begin{proposition}\label{bottom-comb}
Suppose $T_1'$ and $T_2'$ are $n$-leaf binary trees with a common parse word.  Extend $T_1'$ by attaching $\smalltree{2}{1}$ to leaf $i$, obtaining $T_1$.  Extend $T_2'$ to obtain $T_2$ by duplicating leaf $i$.  Then
\[
	|\ParseWords(T_1, T_2)| = |\ParseWords(T_1', T_2')|.
\]
In particular, $T_1$ and $T_2$ have a common parse word.
\end{proposition}

\begin{proof}
Let $w$ be a parse word of $T_1'$ and $T_2'$.  Without loss of generality we may assume that $w_i = 0$ and that the parent of leaf $i$ in $T_2'$ receives the label $1$.

If leaf $i$ is a left leaf in $T_2'$, then $T_2$ parses the word obtained by replacing $w_i$ by $21$ since duplicating leaf $i$ in $T_2'$ has the effect of the replacement
\[
	\vcentergraphics{binarytree2-1labeled0S} \quad \to \quad \vcentergraphics{binarytree3-1labeled21S}
\]
at the parent of leaf $i$, which preserves the labels of all other vertices.  If leaf $i$ is a right leaf in $T_2'$, then $T_2$ parses the word obtained by replacing $w_i$ by $12$ since now the replacement is
\[
	\vcentergraphics{binarytree2-1labeledS0} \quad \to \quad \vcentergraphics{binarytree3-2labeledS12}.
\]

Clearly $T_1$ parses both of these words, so we have found a parse word for the pair.  Moreover, every parse word of $T_1$ and $T_2$ arises uniquely in this way.
\end{proof}

In Section~\ref{parameterized families} we referred to the two leaves of maximal depth in a path tree as \emph{bottom leaves}.  In a general binary tree, a \emph{bottom leaf} is a leaf whose sibling is also a leaf.  It is clear that for $n \geq 2$ every $n$-leaf binary tree has at least one pair of bottom leaves, and every binary tree that is not a path tree has at least two pairs of bottom leaves.  We use these facts in the next two theorems.

\begin{theorem}\label{comb-general}
Let $n \geq 2$, and let $T$ be an $n$-leaf binary tree.  Let $l$ be the level of leaf $1$ in $T$.  Then $|\ParseWords(T, \LeftCombTree(n))| = 2^{l-1}$.
\end{theorem}

By symmetry, the analogous result holds for the right comb.

\begin{proof}
We work by induction on $n$.  The only $2$-leaf binary tree is $\LeftCombTree(2) = \smalltree{2}{1}$, which has only one parse word up to permutation of the alphabet.

Let $T$ be an $n$-leaf binary tree.  Then $T$ has a pair of bottom leaves; suppose these are leaves $i$ and $i+1$.  Remove these two leaves to obtain $T'$, which has $n-1$ leaves.  If $i = 1$, then Proposition~\ref{bottom-bottom} gives twice as many parse words for $T$ and $\LeftCombTree(n)$ as parse words for $T'$ and $\LeftCombTree(n-1)$.  If $i > 1$, then leaf $i$ is a right leaf in $\LeftCombTree(n-1)$, so Proposition~\ref{bottom-comb} gives the same number of parse words as for $T'$ and $\LeftCombTree(n-1)$.
\end{proof}

Csar, Sengupta, and Suksompong~\cite{Csar--Sengupta--Suksompong} have recently provided a generalization of Theorem~\ref{comb-general}.
They consider a partial ordering on the set of $n$-leaf binary trees arising from the rotation operation.
They show that if $T_1$ and $T_2$ are $n$-leaf binary trees whose join exists under this partial ordering, then $|\ParseWords(T_1, T_2)|$ is a certain power of $2$.

The following theorem is an extension of Theorem~\ref{comb-general} to turn trees, although we lose the enumeration.

\begin{theorem}\label{turn-general}
Let $n \geq 4$.  Let $T_1$ be an $n$-leaf binary tree and $T_2$ an $n$-leaf left turn tree.  Then $T_1$ and $T_2$ have a common parse word.
\end{theorem}

\begin{proof}
We work by induction on $n$.  For $n=4$ the result can be verified explicitly.

Now suppose that every $(n-1)$-leaf binary tree has a common parse word with every $(n-1)$-leaf left turn tree.  Let $T_1$ be an $n$-leaf binary tree, and let $T_2$ be an $n$-leaf left turn tree.  Then $T_1$ has a pair of bottom leaves; suppose these are leaves $i$ and $i+1$.

First we consider the case where the $i$th leaf of $T_2$ is the right bottom leaf.  If $T_1$ is a path tree, then $T_1$ and $T_2$ have a common parse word by Proposition~\ref{shared bottom leaf}.  If $T_1$ is not a path tree, then there is another pair of bottom leaves in $T_1$, so we may re-choose $i$ if necessary so that the $i$th leaf of $T_2$ is not the right bottom leaf.

Therefore we may assume that the $i$th leaf of $T_2$ is not the right bottom leaf.  Remove leaves $i$ and $i+1$ from $T_1$ to obtain $T_1'$, which has $n-1$ leaves and so has a common parse word with every $(n-1)$-leaf left turn tree.

If the $i$th leaf of $T_2$ is the left bottom leaf, then we can apply Proposition~\ref{bottom-bottom} to obtain a common parse word for $T_1$ and $T_2$.  Otherwise, leaves $i$ and $i+1$ occur on consecutive levels in $T_2$, so Proposition~\ref{bottom-comb} applies.
\end{proof}

\section{A pair of turn trees}\label{turn trees}

In this section we give three theorems that collectively determine the number of parse words of $\LeftTurnTree(m, n)$ and $\RightTurnTree(k, m + n - k)$.  Note that by Theorem~\ref{turn-general} the number of parse words is nonzero.

\begin{theorem}\label{unique turn-turn count}
For $m \geq 1$, $k \geq 1$, and $\max(2, k - m + 2) \leq n \leq k$,
\[
	|\ParseWords(\LeftTurnTree(m, n), \RightTurnTree(k, m + n - k))| = 1.
\]
\end{theorem}

\begin{proof}
The bottom leaves of $\LeftTurnTree(m,n)$ (which are leaves $n-1$ and $n$) correspond to leaves which are on consecutive levels in $\RightTurnTree(k, m + n - k)$, so we can apply Proposition~\ref{bottom-comb} to see that
\begin{multline*}
	|\ParseWords(\LeftTurnTree(m, n), \RightTurnTree(k, m + n - k))| \\
	= |\ParseWords(\LeftTurnTree(m, n-1), \RightTurnTree(k-1, m + n - k))|.
\end{multline*}
Now, our hypothesis applies to this new, smaller tree pair, so we may continue reducing in the same way until we have reduced the right comb in the left turn tree entirely away.  At this point, we are considering the trees $\LeftTurnTree(m, 2) = \LeftCombTree(m + 2)$ and $\RightTurnTree(k - (n-2), m + n - k)$, which have a unique parse word class by Theorem~\ref{comb-general}.
\end{proof}

Let
\[
	a(m, k) = |\ParseWords(\LeftTurnTree(m, k+1), \RightTurnTree(k, m+1))|.
\]
By considering the left--right reflections of these two trees, we see that $a(m, k) = a(k, m)$.  Theorem~\ref{turn-turn count} determines the number of parse words of $\LeftTurnTree(m, n)$ and $\RightTurnTree(k, m + n - k)$ for $n \geq k + 2$ in terms of $a(m, k)$, and Theorem~\ref{2-parameter turn-turn count} evaluates $a(m, k)$.

\begin{theorem}\label{turn-turn count}
For $m \geq 1$, $k \geq 1$, and $n \geq k + 2$,
\[
	|\ParseWords(\LeftTurnTree(m, n), \RightTurnTree(k, m + n - k))| = 2 a(m, k).
\]
\end{theorem}

\begin{proof}
If $n > k+2$, then the bottom leaves of $\LeftTurnTree(m,n)$ correspond to leaves which are on consecutive levels in $\RightTurnTree(k, m + n - k)$, so we can apply Proposition~\ref{bottom-comb} to see that
\begin{multline*}
	|\ParseWords(\LeftTurnTree(m, n), \RightTurnTree(k, m + n - k))| \\
	= |\ParseWords(\LeftTurnTree(m, n-1), \RightTurnTree(k, m + n - k-1))|.
\end{multline*}
If our hypothesis applies to this new, smaller tree pair, we may continue reducing in exactly the same way until we reach $\LeftTurnTree(m, k + 2)$ and $\RightTurnTree(k, m + 2)$.  Leaves $k$ and $k+1$ are bottom leaves in both these trees, so by Proposition~\ref{bottom-bottom} we have
\begin{multline*}
	|\ParseWords(\LeftTurnTree(m, n), \RightTurnTree(k, m + n - k))| \\
	= 2 |\ParseWords(\LeftTurnTree(m, k + 1), \RightTurnTree(k, m + 1))|. \qedhere
\end{multline*}
\end{proof}

For the final result concerning the number of parse words of two turn trees, it turns out to be convenient to focus on the labels of the internal vertices rather than of the leaves.  We form a word consisting of the internal vertex labels of a labeled path tree by reading these labels from top to bottom.

A word on $\{0,1,2\}$ is \emph{alternating} if no two consecutive letters are equal.  If the internal vertices of a path tree are labeled with $w$, then the labeling can be extended to a parse word for the tree precisely when $w$ is alternating.  Therefore it will be important to know the sizes of certain sets of alternating words.  Let $A_m$ be the set of length-$m$ alternating words of the form $0 v_2 \cdots v_m$, where $v_2, v_m \in \{1,2\}$.  Let $B_m$ be the set of length-$m$ alternating words of the form $0 v_2 \cdots v_m$, where $v_2 \in \{1,2\}$ and $v_m \in \{0,2\}$.

\begin{proposition}\label{alternating counts}
For $m \geq 2$, $|A_m| = (2^m + 2 (-1)^m)/3$ and $|B_m| = (2^m - (-1)^m)/3$.
\end{proposition}

\begin{proof}
Let $a_i(m)$ be the number of length-$m$ alternating words on $\{0,1,2\}$ beginning with $01$ and ending with $\Mod(i,3)$.  Then
\begin{align*}
	a_i(m)
	&= a_{i+1}(m-1) + a_{i+2}(m-1) \\
	&= a_{i+2}(m-2) + 2 a_{i+3}(m-2) + a_{i+4}(m-2) \\
	&= a_{i+3}(m-3) + 3 a_{i+4}(m-3) + 3 a_{i+5}(m-3) + a_{i+6}(m-3) \\
	&\;\:\vdots \\
	&= \sum_{j=0}^n \binom{n}{j} a_{i+n+j}(m-n) \\
	&\;\:\vdots \\
	&= \sum_{j=0}^{m-2} \binom{m-2}{j} a_{i+m-2+j}(2) \\
	&= \sum_{j \equiv -(i+m) \bmod 3} \binom{m-2}{j}
\end{align*}
since $a_0(2) = a_2(2) = 0$ and $a_1(2) = 1$.  Therefore
\[
	a_0(m) = \sum_{j \equiv -m \bmod 3} \binom{m-2}{j} = \frac{1}{3} \left(2^{m-2} + (-1)^{m-1}\right).
\]

Since $a_1(m)$ and $a_2(m)$ also count alternating words of the forms $02 \cdots 2$ and $02 \cdots 1$ respectively, we have
\[
	|A_m| = 2 a_1(m) + 2 a_2(m) = 2 \left(2^{m-2} - a_0(m)\right) = \frac{1}{3} \left(2^m + 2 (-1)^m\right).
\]
Similarly,
\[
	|B_m| = 2 a_0(m) + a_1(m) + a_2(m) = a_0(m) + 2^{m-2} = \frac{1}{3} \left(2^m - (-1)^m\right). \qedhere
\]
\end{proof}

Next we provide a simple recurrence satisfied by $a(m, k)$.  Unfortunately, we do not know a correspondingly simple proof.

\begin{theorem}\label{2-parameter turn-turn count}
For $m \geq 1$ and $k \geq 1$,
\[
	a(m+3, k) - 2 a(m+2, k) - a(m+1, k) + 2 a(m, k) = 0.
\]
\end{theorem}

Initial conditions that suffice to completely determine $a(m, k)$ from this recurrence are $a(1, 1) = 1$, $a(1, 2) = 1$, $a(1, 3) = 1$, $a(2, 2) = 4$, $a(2, 3) = 5$, and $a(3, 3) = 3$.  The particular solution can be written as the matrix product
\[
	a(m, k)
	= \frac{1}{4}
	\begin{pmatrix}
		2/3 \cdot 2^m \\
		1 \\
		5/3 \cdot (-1)^m
	\end{pmatrix}^\top
	\begin{pmatrix}
		1/2 & 1 & 1 \\
		1 & 1 & -1 \\
		1 & -1 & 1/5
	\end{pmatrix}
	\begin{pmatrix}
		2/3 \cdot 2^k \\
		1 \\
		5/3 \cdot (-1)^k
	\end{pmatrix}.
\]

\begin{proof}
Let $m \geq 2$ and $k \geq 2$, and let $A_m$ and $B_m$ be as above.  Let
\begin{align*}
	1_m(w) &= \left\{((01)^{m/2} w, w (10)^{m/2})\right\}, \\
	2_m(w) &= \left\{((02)^{m/2} w, w (20)^{m/2})\right\}, \\
	A_m(w) &= \left\{(v w, w v) : v \in A_m\right\}, \\
	B_m((01)^{k/2}) &= \left\{(v (10)^{k/2}, (01)^{k/2} v) : v \in B_m\right\}.
\end{align*}

We consider the set of pairs $(L, R)$ of length-$(m+k)$ (alternating) words such that $R = 01\cdots$ and such that respectively labeling the internal vertices of $\LeftTurnTree(m, k+1)$ and $\RightTurnTree(k, m+1)$ with $L$ and $R$ produces a parse word for the pair.  Such pairs $(L, R)$ are in bijection with equivalence classes of parse words for this tree pair as follows.  The internal vertex labels of a path tree determine the labels of all leaves except the bottom leaves.  Since $\LeftTurnTree(m, k+1)$ and $\RightTurnTree(k, m+1)$ do not share both bottom leaves, labeling the internal vertices with the pair $(L, R)$ determines a unique parse word.  We may choose representative parse words so that the internal vertex labels of $\RightTurnTree(k, m+1)$ begin with $01$ (since the first two labels cannot be the same).

Let $w = 01\cdots$ be the length-$k$ prefix of $R$.  Thus the internal vertices of the right comb of $\RightTurnTree(k, m+1)$ are labeled with letters from $w$, and the first letter of the parse word is $2$.  We show that if $w$ contains all three letters then the set of pairs $(L, R)$ is
\[
\begin{cases}
	\{\}
		& \text{if $w$ ends in $0$ and $m$ is odd} \\
	1_m(w) \cup 2_m(w)
		& \text{if $w$ ends in $0$ and $m$ is even} \\
	A_m(w)
		& \text{if $w$ ends in $1$ or $2$ and $m$ is odd} \\
	A_m(w) \cup 2_m(w)
		& \text{if $w$ ends in $1$ and $m$ is even} \\
	A_m(w) \cup 1_m(w)
		& \text{if $w$ ends in $2$ and $m$ is even,}
\end{cases}
\]
and if $w = (01)^{k/2} = 0101\cdots$ contains only two letters then this set is
\[
\begin{cases}
	\left\{((01)^{(m+k)/2}, (01)^{(m+k)/2})\right\}
		& \text{if $w$ ends in $0$ and $m$ is odd} \\
	1_m(w) \cup 2_m(w)
		& \text{if $w$ ends in $0$ and $m$ is even} \\
	A_m(w) \cup B_m(w)
		& \text{if $w$ ends in $1$ and $m$ is odd} \\
	A_m(w) \cup B_m(w) \cup 2_m(w)
		& \text{if $w$ ends in $1$ and $m$ is even.}
\end{cases}
\]

To see this, first suppose that $L = v w$ and $R = w v$ for some $v$.  Then $v$ begins with $0$, so $w$ does not end in $0$, and every $v \in A_m$ produces a parse word.

Next suppose that $L = v' w$ and $R = w v$ for some $v' \neq v$.  Then in fact $v$ and $v'$ differ in every position; in particular, $v$ begins with some letter $j \neq 0$.  Let $i \in \{1, 2\}$ such that $i \neq j$.  Then the final leaf receives the label $i$ since it is a child of a $0$ leaf in $\LeftTurnTree(m, k+1)$ and a child of a $j$ leaf in $\RightTurnTree(k, m+1)$.  It follows that $v = (j0)^{m/2}$ and $v' = (0j)^{m/2}$; therefore $m$ is even, and choosing $j$ to be either $1$ or $2$ produces a parse word as long as it differs from the last letter of $w$.

Finally, suppose that $L = v w'$ for some length-$k$ word $w' \neq w$.  Then $w$ and $w'$ differ in every position; in particular, $w'$ begins with $1$, and it follows that $w = (01)^{k/2}$ and $w' = (10)^{k/2}$.  If $w$ ends in $0$, then $L = R = (01)^{(m+k)/2}$, yielding the parse word $2^k 0 2^m$.  If $w$ ends in $1$, then every $v \in B_m$ produces a parse word, and $R = w v$.

Since we know the sizes of all these sets by Proposition~\ref{alternating counts}, we can enumerate the set of internal word pairs $(L, R)$ and obtain an expression for $a(m, k)$, which as expected is symmetric in $m$ and $k$.  For fixed $k$ the expression is a linear combination of $2^m$, $1$, and $(-1)^m$, so it satisfies the recurrence stated in the theorem, which can be written
\[
	(M - 2) (M - 1) (M + 1) \, a(m, k) = 0,
\]
where $M$ is the forward shift operator in the variable $m$.

When $m = 1$ or $k = 1$ one of the two trees is a comb tree, and by Theorem~\ref{comb-general} we have $a(m, k) = 1$, which one checks is also what the general expression for $a(m, k)$ gives upon setting $m = 1$ or $k = 1$.
\end{proof}

\section{Reducing a pair of trees}\label{reducing}

How might one proceed from the theorems of the previous sections to a proof that every two $n$-leaf path trees parse a common word?  Here we introduce two notions of reducibility --- ways to reduce the problem of finding a parse word for a pair of trees to finding parse words for smaller pairs --- and give some related conjectures.

\subsection{Decomposable pairs}

Recall that if $T_1$ and $T_2$ are $n$-leaf trees such that leaves $i$ and $i+1$ are siblings in both trees, then Proposition~\ref{bottom-bottom} reduces the problem of finding a parse word for $T_1$ and $T_2$ to the problem of finding a parse word for the pair of $(n-1)$-leaf trees in which the common $\smalltree{2}{1}$ has been removed.  Our first observation is that there is nothing special about $\smalltree{2}{1}$; if the two trees have any common branch system in the same position, then we can decompose the trees.  For example, the $8$-leaf trees
\[
	T_1 = \vcentergraphics{binarytree8-69} \qquad T_2 = \vcentergraphics{binarytree8-231}
\]
share the branch system
\[
	S = \vcentergraphics{binarytree4-2}
\]
in the second through fifth leaves, which we may remove to obtain the $5$-leaf trees
\[
	\vcentergraphics{binarytree5-1} \qquad \vcentergraphics{binarytree5-7}.
\]
Given a common parse word $w_1 w_2 w_3 w_4 w_5$ of this pair of $5$-leaf trees, we can find a common parse word of the original pair of $8$-leaf trees by taking any valid labeling of $S$ and permuting the alphabet so that the root receives the label $w_2$.

In fact to decompose a pair of trees we only require a vertex in $T_1$ with dangling subtree $S_1$ and a vertex in $T_2$ with dangling subtree $S_2$ such that the leaves in $S_1$ and $S_2$ are the same.  For example, there are two such vertex pairs in the tree pair
\[
	\vcentergraphics{binarytree12-16486labeled} \qquad \vcentergraphics{binarytree12-43123labeled}
\]
(where corresponding leaves have been given the same label).  Breaking the trees at levels $2$ and $8$ as
\[
	\vcentergraphics{binarytree12-16486brokenlabeled} \qquad \vcentergraphics{binarytree12-43123brokenlabeled}
\]
produces the same partition $\{\{a, l\}, \{b, c, h, i, j, k\}, \{d, e, f, g\}\}$ of the leaves in both trees.  Thus, to find a parse word for the original pair it suffices to find parse words for the subtree pairs.  Proposition~\ref{root label} guarantees that we can reattach the subtrees consistently, since every binary tree that parses $w$ receives the same label for its root when the leaves are labeled with the letters of $w$.  Let us call a pair of path trees \emph{indecomposable} if there is no such (nontrivial) decomposition.

The tree pair in Theorem~\ref{comb-comb} consisting of $\LeftCombTree(n)$ and $\RightCombTree(n)$ is indecomposable, as is the pair in Theorem~\ref{comb-crooked} consisting of $\LeftCombTree(n)$ and $\RightCrookedTree(n)$.  On the other hand, breaking the trees $\LeftCombTree(n)$ and $\LeftCrookedTree(n)$ at level $1$ shows that this pair is decomposable, and in this case the decomposition accounts for the non-uniqueness of the equivalence classes of words in Theorem~\ref{comb-crooked2}.

The technique of decomposing trees is not limited to path trees.  For example, the pair
\[
	T_1 = \vcentergraphics{binarytree8-69} \qquad T_2 = \vcentergraphics{binarytree8-231}
\]
can also be decomposed into the two pairs
\[
	T_1' = \vcentergraphics{binarytree6-11} \qquad T_2' = \vcentergraphics{binarytree6-30}, \qquad S_1 = \vcentergraphics{binarytree3-1} \qquad S_2 = \vcentergraphics{binarytree3-2}.
\]

\subsection{Pairs that are not mutually crooked}

We showed in Proposition~\ref{bottom-comb} that if leaves $i$ and $i+1$ are siblings in $T_1$ and are on consecutive levels in $T_2$ then this pair of trees is reducible.  It is natural then to ask whether a tree pair in which leaves $i$ and $i+1$ are on consecutive levels in both trees is reducible.

First let us consider the pair
\[
	\vcentergraphics{binarytree7-1} \qquad \vcentergraphics{binarytree7-92}
\]
which has the common parse word $0001220$.  The three consecutive $0$s label leaves in both trees that are arranged in a right comb structure, and shortening each comb by two leaves produces the pair
\[
	\vcentergraphics{binarytree5-1} \qquad \vcentergraphics{binarytree5-11}
\]
which parses $01220$.  In other words, we obtain a parse word for the larger pair by simply inserting two $0$s corresponding to the two added leaves.  Let us see why this works.  In the first tree, the $4$-leaf right comb subtree whose first three leaves are labeled $0$ has internal vertex labels $1$, $2$, and $1$; in the second tree, the corresponding $4$-leaf right comb subtree has internal vertex labels $2$, $1$, and $2$.  In both cases, the internal vertex labels alternate between $1$ and $2$, so shortening the comb by two leaves preserves the label of the root and the labels of the bottom leaves.  Hence we still have a valid labeling.

The situation will be the same even if the two combs have different orientations, and even if the trees are not path trees but binary trees in general.  We formalize this as follows.  The relevant extending operation is \emph{triplicating} leaf $i$ --- inserting two $\smalltree{2}{1}$ structures in $T'$ so as to obtain three left leaves in $T$ if leaf $i$ is a left leaf in $T'$ and three right leaves in $T$ if leaf $i$ is a right leaf in $T'$, analogous to duplicating a leaf as discussed in Section~\ref{general families}.

\begin{theorem}
Let $T_1'$ and $T_2'$ be $(n-2)$-leaf binary trees.  Let $1 \leq i \leq n-2$, and let $T_1$ and $T_2$ be the $n$-leaf trees obtained from $T_1'$ and $T_2'$ by triplicating leaf $i$.  If $w = w_1 \cdots w_{n-2}$ is a parse word for $T_1'$ and $T_2'$, then $w_1 \cdots w_{i-1} w_i w_i w_i w_{i+1} \cdots w_{n-2}$ is a parse word for $T_1$ and $T_2$.
\end{theorem}

A pair of $n$-leaf trees $T_1$ and $T_2$ is \emph{weakly mutually crooked} if it cannot be obtained by triplicating some leaf $i$ in a pair of $(n-2)$-leaf trees.  To prove that every pair of binary trees has a parse word, by the previous theorem it suffices to consider pairs of weakly mutually crooked trees.

However, it appears that something stronger is true.
A pair of $n$-leaf trees $T_1$ and $T_2$ is \emph{mutually crooked} if it cannot be obtained by duplicating some leaf $i$ in a pair of $(n-1)$-leaf trees.
That is, no pair of consecutive leaves has an uncle--nephew relationship in both trees.
For example, the pair parsing $0110212$ in Section~\ref{introduction} is mutually crooked.
Experimental evidence suggests that in fact it suffices to consider pairs of mutually crooked trees.

\begin{conjecture}
Let $T_1'$ and $T_2'$ be $(n-1)$-leaf binary trees.  Let $1 \leq i \leq n-1$, and let $T_1$ and $T_2$ be the $n$-leaf trees obtained from $T_1'$ and $T_2'$ by duplicating leaf $i$.  There exists a parse word $w = w_1 \cdots w_n$ of $T_1$ and $T_2$ such that $w_i = w_{i+1}$.
\end{conjecture}

For example, in the pair discussed at the beginning of this subsection, leaves $5$ and $6$ are on consecutive levels in both trees, and these leaves receive the label $2$.  Note however that the parse word of $T_1$ and $T_2$ is not necessarily a simple extension of a parse word of $T_1'$ and $T_2'$.

The trees $\LeftCrookedTree(n)$ and $\RightCrookedTree(n)$ (which we addressed in Theorem~\ref{crooked-crooked count}) are mutually crooked, but for $n \geq 5$ no path tree is mutually crooked to $\LeftCombTree(n)$, since even a completely crooked tree has a pair of consecutive leaves that lie in consecutive levels.  Theorems~\ref{comb-comb} and \ref{turn-turn} provide additional examples of pairs that fail to be mutually crooked.

\subsection{Other conjectures}

To prove that every pair of $n$-leaf binary trees $T_1$ and $T_2$ has a parse word, it therefore suffices to consider indecomposable, weakly mutually crooked pairs of trees.  In particular, we may assume that the leaves on level $1$ in $T_1$ and $T_2$ are different, since if they are the same then the pair is decomposable at level $1$ into smaller pairs.

\begin{theorem}
Let $n \geq 3$, and let $T_1$ and $T_2$ be $n$-leaf path trees such that leaf $1$ is on level $1$ in $T_1$ and leaf $n$ is on level $1$ in $T_2$.
Then $T_1$ and $T_2$ have no parse word of the form $01v1$.
\end{theorem}

\begin{proof}
For $n = 3$ one checks that $011$ is not a parse word for one of the two $3$-leaf binary trees.
Assume $n \geq 4$.
Toward a contradiction, suppose that $01v1$ is a common parse word for some $v$.
Then the root of each tree receives the label $2$, and the internal vertex on level $1$ of $T_1$ receives $1$.
Consider the children of this internal vertex.
If the right child is a leaf, then it is leaf $n$ and so receives $1$, which is not a valid label because its parent is already labeled $1$.
If the left child is a leaf, then it is leaf $2$ and so receives $1$, which is also not a valid label.
\end{proof}

A similar argument shows that if there is a parse word of the form $01v2$, then leaf $2$ of $T_1$ is on level $2$, and leaf $n-1$ of $T_2$ is on level $2$.

The following conjecture gives several statements that seem to be true and may be helpful in proving Theorem~\ref{main} for path trees directly.

\begin{conjecture}
Let $n \geq 4$, and let $T_1$ and $T_2$ be $n$-leaf path trees such that leaf $1$ is on level $1$ in $T_1$ and leaf $n$ is on level $1$ in $T_2$.  Then we have the following.
\begin{itemize}
\item If $T_1$ and $T_2$ have no parse word of the form $00v$ or $v00$, then they have a unique parse word (up to permutation of alphabet).
\item If $T_1$ and $T_2$ have no parse word of the form $00v$ and are mutually crooked, then they have a parse word of the form $01v00$.
\item If $T_1$ and $T_2$ have no parse word of the form $00v$, then the only possibilities for the $2$-tuple
\[
	(\text{level of leaf $2$ in $T_1$}, \text{level of leaf $n-1$ in $T_2$})
\]
are $(2,3)$ and $(k,2)$ for some $k \geq 2$. \\
Moreover, if $T_1$ and $T_2$ are weakly mutually crooked, the only possibilities are $(2,3)$ and $(k,2)$ for some $2 \leq k \leq 4$. \\
Moreover, if $T_1$ and $T_2$ are mutually crooked, the only possibilities are $(2,3)$ and $(k,2)$ for some $2 \leq k \leq 3$.
\end{itemize}
\end{conjecture}

Finally, we give an interesting conjecture that has been explicitly verified for $n \leq 12$.  (The statement does not hold for general binary trees.)

\begin{conjecture}
Let $n \geq 4$.  Every pair of $n$-leaf path trees parses a word of the form $u00v$ for some (possibly empty) $u, v$.
\end{conjecture}

config: arxiv


TITLE: Word problem that I need help explaining! Can someone break this down for me?
QUESTION [0 upvotes]: There are $32$ students in Mrs. Vicky’s class. Some of the students took one pencil each from the box with pencils on the teachers desk. Then a third of the remaining students took $3$ pencils each, and there were no more pencils left in the box. How many pencils were there in the box at first?
I’m sure there is a super simple answer for this and I’m embarrassed that I can’t explain it myself! Please help!

REPLY [0 votes]: I’ll give you a road map for a straightforward algebraic solution, though the problem can be solved without algebra using the hint given by Andreas Blass in the comments. Let $s$ be the number of students who took one pencil each, and let $p$ be the total number of pencils.

In terms of $s$, how many students took $3$ pencils each?
Again in terms of $s$, how many pencils did those students take altogether?

Now write down an expression in terms of $s$ for the total number of pencils taken by all of the students who took pencils. Simplify that expression. How is it related to $p$?


text:
\begin{document}

\vspace{5mm}

\date{\today}

\title[On additive functions]{On additive functions with additional derivation properties}

\author[R.\ Gr\"unwald]{Rich\'ard Gr\"unwald}
\author[Zs. P\'ales]{Zsolt P\'ales}
\address{Institute of Mathematics, University of Debrecen,
H-4002 Debrecen, Pf. 400, Hungary}
\email{richard.grunwald96@gmail.com, pales@science.unideb.hu}

\thanks{The research of the first author was supported by the \'UNKP-19-2 New National Excellence Program of the Ministry of Human Capacities. The research of the second author was supported by the 2019-2.1.11-T\'ET-2019-00049, the EFOP-3.6.1-16-2016-00022 and the EFOP-3.6.2-16-2017-00015 projects. The last two projects are co-financed by the European Union and the European Social Fund.}
\subjclass[2010]{Primary 39B22, 39B40, 39B50}
\keywords{algebraic derivation; derivation for trigonometric functions; derivation for hyperbolic functions}

\begin{abstract}
The purpose of this paper is to introduce the notion of a generalized derivation which derivates a prescribed family of smooth vector-valued functions of several variables. The basic calculus rules are established and then a result derived which shows that if a function $f$ satisfies an addition theorem whose determining operation is derivable with respect to an additive function $d$, then the function $f$ is itself derivable with respect to $d$. As an application of this approach, new proof of a generalization of a recent result of Maksa is obtained. We also extend the result of Nishiyama and Horinouchi and formulate two open problems.
\end{abstract}

\maketitle

\section{Introduction}

Derivations are additive and Leibniz-type mappings of a ring into itself. More
precisely, if $(R,+,\cdot)$ is a ring, then a function $d:R\to R$ is called a \emph{derivation} if,
for all $x,y\in R$,
\begin{eqnarray}
d(x+y)&=&d(x)+d(y), \label{ES} \\
d(x\cdot y)&=&d(x)\cdot y+x\cdot d(y). \label{EP}
\end{eqnarray}

Derivations are used in many branches of analysis and algebra. For instance, nonnegative information functions are constructed via real derivations (see
Dar\'oczy--Maksa \cite{DarMak79}, Maksa \cite{Mak76}). Nonconstant functions that are convex with respect to families of power means are also obtained in terms of real derivations (see Maksa--P\'ales \cite{MakPal15}). Derivations are used to express the general solutions of certain functional equations (see Fechner--Gselmann \cite{FecGse12}, Gselmann \cite{Gse12}, \cite{Gse13a}, Halter-Koch \cite{Hal00}, \cite{Hal00b}, Jurkat \cite{Jur65}). Generalizations, such as higher-order derivations, bi-derivations and approximate or near-derivations were studied by Badora \cite{Bad06c}, Gselmann \cite{Gse14b}, Gselmann--P\'ales \cite{GsePal16}, and Maksa \cite{Mak81b}, \cite{Mak87c}.

We say that a function $d:\R\to\R$ derivates a differentiable function $f:I\to\R$ if the functional equation
\Eq{*}{
  d(f(x))=f'(x)d(x) \qquad(x\in I)
}
holds. In the pioneering papers \cite{Kur64,Kur65} Kurepa proved that if $d$ is an additive functions which derivates one of the maps $x\mapsto x^2$ or $x\mapsto x^{-1}$, then it satisfies the Leibniz Rule, i.e., it is a standard derivation.
This result was then extended by Nishiyama and Horinouchi in \cite{NisHor68},
who proved an analogous statement about the derivability of the power function $x\mapsto x^r$ with rational exponent different from $0$ and $1$. Boros and Erdei in \cite{BorErd05} proved that those additive functions that derivate the map $x\mapsto\sqrt{1-x^2}$, that is, satisfy the identity
\Eq{bor}{
		d(\sqrt{1-x^2})=-\frac{x}{\sqrt{1-x^2}}d(x) \qquad(x\in]-1,1[\,),
}
are also standard derivations. Maksa in \cite{Mak13a} showed that if an additive function derivates any of the exponential, hyperbolic or trigonometric functions, then is has to be a standard derivation again. A counterpart of this result was obtained by Grünwald and Páles in \cite{GruPal18}, where an analogous statement
was established assuming Leibniz property instead of additivity.

The purpose of this paper is to introduce the notion of generalized derivation which derivates a prescribed family of smooth vector-valued functions of several variables. After establishing the basic calculus rules in \thm{inv}, we derive in \cor{add} a result which shows that if a function $f$ satisfies an addition theorem whose determining operation is derivable with respect to an additive function $d$, then the function $f$ is itself derivable with respect to $d$.
Using this result, we will be able to give a completely new proof for the aforementioned result of Maksa \cite{Mak13a}. In addition, we also generalize this result, because we require the derivability of the exponential, hyperbolic or trigonometric functions only on small intervals. In the last section of our paper, we also offer a generalization of Nishiyama and Horinouchi by replacing power functions of the form $P\circ Q^{-1}$, where $P$ and $Q$ are polynomials with rational coefficients. Finally, we formulate some open problems.

\section{Generalized derivations and their properties}

For fixed $n,m\in\N$, the class of $n$-variable $\R^m$-valued \emph{admissible functions} is defined as follows:
	\Eq{*}{
		\A_n^m:=\{f:\Omega\to\R^m \mid \emptyset\neq\Omega\subset\R^n \mbox{ is open and }
		f\mbox{ is Fréchet differentiable on }\Omega\}
	}
	and we set
	\Eq{*}{
		\A  := \bigcup_{n,m=1}^\infty \A_n^m.
	}
The set $\Omega$ related to $f$ will be called the \emph{domain of $f$} and denoted by $\dom_f$. In general, for a vector $x\in\R^n$, we will denote the $i$th coordinate of $x$ by $x_i$, and for a function $f\in\A_n^m$, $f_j$ will stand for the $j$th coordinate function of $f$.

We say that a function $d:\R\to\R$ is a \emph{derivation with
respect to an admissible function $f\in\A_n^m$} if, for all $x\in\dom_f$ and $j\in\{1,\dots,m\}$,
	\Eq{df+}{
		d\big(f_j(x)\big)=\partial_1 f_j(x)d(x_1)+\dots+\partial_n f_j(x)d(x_n)
	}
	holds. Furthermore we say that \emph{$d$ is a derivation with respect to $A\subseteq\A$}, if $d$ is a derivation with respect to each member of $A$. For any $n\in\N$ and $x\in\R^n$, define $d(x)$ by
	\Eq{*}{
	d(x):=(d(x_1),\dots,d(x_n)).
	}
	Then \eq{df+} can simply be rewritten as
	\Eq{*}{
	  d(f(x))=f'(x)d(x),
	}
	where $f\in\A_n^m$ and $f'(x)$ denotes the Fréchet derivative of $f$ at $x$, which is an $n\times m$ matrix whose entries are the partial derivatives $\partial_i f_j$ at $x$.

One can immediately see that a function $d:\R\to\R$ is a standard derivation if and only if it is a derivation with respect to $S_2$ and $P_2$, where
	\Eq{*}{
		S_2(x_1,x_2):=x_1+x_2 \qquad\mbox{and}\qquad P_2(x_1,x_2):=x_1x_2 \qquad((x_1,x_2)\in\R^2).
	}
In what follows, we will prefer the terminology $d$ is additive (resp.\ of Leibniz-type) whenever $d$ is a derivation with respect to $S_2$ (resp.\ $P_2$).

The following result, which is a significant extension of \cite[Lemma A]{GruPal18} collects the basic rules for functions that are derivable with respect to a fixed real function. In particular, its second assertion will be very useful for our purposes.

\Thm{inv}{
For any function $d:\R\to\R$, we have the following three assertions.
\begin{enumerate}[(i)]
	\item Let $n,m,k\in\N$ and $f\in\A_n^m$, $g\in\R_m^k$. If $d$ is a derivation with respect to $f$ and $g$, then $d$ is also a derivation with respect to $g\circ f$.
	\item Let $n,m,k\in\N$ and $f\in\A_n^m$, $g\in\R_m^k$ such that $f(\dom_f)$ is open. If $d$ is a derivation with respect to $f$ and $g\circ f$, then $d$ is also a derivation with respect to $g$ on $f(\dom_f)\cap\dom_g$.
	\item Let $n\in\N$ and $f\in\A_n^n$ with a continuous nowhere singular derivative. If $d$ is a derivation with respect to $f$, then $d$ is also a derivation with respect to its inverse $f^{-1}$.
\end{enumerate}
}

\begin{proof}
By the assumptions of (i), for all $x\in\dom_f$ and $y\in\dom_g$, we have
\Eq{xy}{
	d(f(x))=f'(x)d(x)\qquad\mbox{and}\qquad d(g(y))=g'(y)d(y).
}
Let $x\in\dom_f$ with $y:=f(x)\in\dom_g$. Using that $d$ is a derivation with respect to $f$ and $g$, by the standard Chain Rule, we get
\Eq{*}{
	d((g\circ f)(x))&=d(g(f(x)))=d(g(y))=g'(y)d(y)\\
	&=g'(f(x))d(f(x))=g'(f(x))f'(x)d(x)=(g\circ f)'(x)d(x),
}
which yields that $d$ is a derivation with respect to the function $g\circ f$.

Let $y\in f(\dom_f)\cap\dom_g$. Then there exists $x\in\dom_f$ such that $y=f(x)$. Thus, applying the standard Chain Rule, we get
\Eq{*}{
  d(g(y))&=d(g(f(x))=d(g\circ f(x))=(g\circ f)'(x)d(x)\\
  &=g'(f(x))f'(x)d(x)=g'(f(x))d(f(x))=g'(y)d(y),
}
which proves that $d$ is also a derivation with respect to $g$ on $f(\dom_f)\cap\dom_g$.

By the assumption of (iii), for all $x\in\dom_f$, we have the first equality in \eq{xy}. Let $y\in\dom_{f^{-1}}$.
Using the substitution $x=f^{-1}(y)$, this implies
\Eq{*}{
  d(y)=f'(f^{-1}(y))d(f^{-1}(y)).
}
Thus, by the inverse function theorem, it follows that
\Eq{*}{
	d(f^{-1}(y))=\big(f'(f^{-1}(y))\big)^{-1}d(y)=\big(f^{-1}\big)'(y)d(y).
}
Thus, $d$ is a derivation with respect to the inverse function $f^{-1}$.
\end{proof}

The following consequence of the above theorem will be useful in several proofs.

\Cor{add}{Let $\Omega_1,\Omega_2\subseteq\R^n$ be nonempty open sets, let $f:\Omega_1\cup\Omega_2\cup(\Omega_1+\Omega_2)\to\R^m$ be a Fréchet differentiable function such that $f(\Omega_1)$ and $f(\Omega_2)$ are open. Assume that there exists a Fréchet differentiable function $g:f(\Omega_1)\times f(\Omega_2)\to\R^m$ such that $f$ satisfies the functional equation
	\Eq{addition}{
		f(x+y)=g(f(x),f(y)) \qquad ((x,y)\in\Omega_1\times\Omega_2).
	}
	Let $d:\R\to\R$ be an additive function which is a derivation with respect to $f$. Then $d$ is also a derivation with respect to $g$ on $f(\Omega_1)\times f(\Omega_2)$.}

\begin{proof} Assume that $d$ is an additive derivation with respect to $f$. By the additivity of $d$, we have that $d$ is a derivation with respect to the mapping
\Eq{*}{
  \Omega_1\times\Omega_2\ni(x,y)\mapsto f(x+y).
}
Thus, the equality \eq{addition} implies that $d$ is a derivation with respect to the composition
\Eq{*}{
  \Omega_1\times\Omega_2\ni(x,y)\mapsto g(f(x),f(y)).
}
On the other hand, $d$ is trivially a derivation
with respect to the mapping
\Eq{*}{
  \Omega_1\times\Omega_2\ni(x,y)\mapsto(f(x),f(y)).
}
Applying the second assertion of the previous theorem, now it follows that $d$ is also a derivation with respect to $g$ on $f(\Omega_1)\times f(\Omega_2)$.
\end{proof}

\section{Localization theorems}

In the sequel, for a number $r\in\Q$, let $D_r$ denote the domain of the power function $x\mapsto x^r$, which is defined in the following way: If $r=m/n$, where
$n\in\N$, $m\in\Z$ and $n,m$ are coprime, then let
\Eq{*}{
  D_r:=\begin{cases}
       \R \qquad&\mbox{if $n$ is odd and $m\geq0$},\\
       \R\setminus\{0\} \qquad&\mbox{if $n$ is odd and $m<0$},\\
       [0,\infty[ \qquad&\mbox{if $n$ is even and $m\geq0$},\\
       ]0,\infty[ \qquad&\mbox{if $n$ is even and $m<0$}.\\
       \end{cases}
}
A function $d:\R\to\R$ is said to be \emph{$\Q$-homogeneous} if, for all $x\in\R$ and $r\in\Q$, the equality $d(rx)=rd(x)$ holds. It is well-known that every additive function is automatically $\Q$-homogeneous.

\Lem{Nisalt}{
	Let $r\in\Q$, let $I\subseteq D_{r-1}$ be a nonempty open subset and $d:\R\to\R$ be a $\Q$-homogeneous function. Suppose that the equality
	\Eq{xr}{
		d(x^r)=rx^{r-1}d(x)
	}
	holds for all $x\in I$. Then it is also valid for all $x\in D_{r-1}$.
}

\begin{proof}
	Assume that \eq{xr} holds for all $x\in I$.
	Let $x\in D_{r-1}$ be arbitrary. If $x=0$, then $r\geq1$ and hence $x^r=0^r=0$. Thus, by $d(0)=0$, \eq{xr} is trivially valid. If $r=1$ So may assume that $x$ is an arbitrarily fixed element from $D_r\setminus\{0\}$.
	Suppose that $r$ is of the form $r=m/n$ for some $n\in\N$ and $m\in\Z$. By the density of $\Q$ in $\R$, it is clear that the set
	\Eq{*}{
		\{q\in\Q\mid q\neq0,\, q^nx\in I\}
	}
	is nonempty. Let $q$ be a fixed element from it. Thus, using the validity of equation \eq{xr} on the interval $I$ and the $\Q$-homogeneity of $d$, we obtain
	\Eq{*}{
		q^md(x^r)=d(q^mx^r)=d((q^nx)^r)=r(q^nx)^{r-1}d(q^nx)=q^mrx^{r-1}d(x),
	}
	which simplifies to $d(x^r)=rx^{r-1}d(x)$. This is exactly the desired equality since $x$ was an arbitrary element from $D_r\setminus\{0\}$.
\end{proof}

The following result essentially was proved by Nishiyama and Horinouchi \cite{NisHor68}. The result concerning the particular cases $r=-1$ and $r=2$ were discovered by Kurepa in \cite{Kur64} and \cite{Kur65}.

\Lem{Nis}{
	Let $d:\R\to\R$ be an additive function, let $r\in\Q\setminus\{0,1\}$ and let $I\subseteq D_r$ be a nonempty open subinterval. Then $d$ is a standard derivation if and only if \eq{xr} is valid for all $x\in I$.
}

\begin{proof} Assume first that $d$ is a standard derivation. Then by an easy argument, it follows that \eq{xr} is valid for all $x\in D_r$.

Conversely, if \eq{xr} is valid for all $x\in I$, then, by \lem{Nisalt}, we get that \eq{xr} is valid for all $x\in D_r$. Now, the result of Nishiyama and Horinouchi \cite{NisHor68} implies that $d$ must be a standard derivation.
\end{proof}

\Lem{LRext}{
	Let $U\subseteq\R^2$ be a nonempty open subset and let $d:\R\to\R$ be a $\Q$-homogeneous function which satisfies the functional equation \eqref{EP}
	for all $(x,y)\in U$. Then \eqref{EP} also holds for all $x,y\in\R$.
}

\begin{proof}
	Let $x,y\in\R$. Using the density of $\Q$ in $\R$, it is clear that there exist $p,q\in\Q\setminus\{0\}$ such that $(px,qy)\in U$. Applying equation \eq{P} for $px$ and $qy$, taking into consideration the $\Q$-homogeneity of $d$, we obtain that
	\Eq{*}{
		pqd(xy)=d((px)(qy))=d(px)qy+pxd(qy)=pd(x)qy+pxqd(y).
	}
	Dividing by $pq$ the above equality, we get the statement.
\end{proof}

To prove our main result, which will extend the theorem of Maksa \cite{Mak13a}, the following lemma will also be needed.

\Lem{Ratio}{
	The sets
	\Eq{*}{
		U&:=\{x\in\R: x,\sqrt{1+x^2}\in\Q\},\\
		V&:=\{x\in\,]-\infty,-1[\,\cup\,]1,\infty[\,: x,\sqrt{x^2-1}\in\Q\},\\
		W&:=\{x\in\,]-1,1[\,: x,\sqrt{1-x^2}\in\Q\}
	}
	are dense in $\R$, in $\,]-\infty,-1[\,\cup\,]1,\infty[\,$, and in $\,]-1,1[\,$, respectively.
}

\begin{proof}
	To prove the density of $U$, let $x\in \,]-1,1[\,$, let $0<\varepsilon<\min(1+x,1-x)$ be arbitrary and denote
	\Eq{*}{
		I:=\left]\sqrt{\frac{1-x-\varepsilon}{1+x+\varepsilon}},\sqrt{\frac{1-x+\varepsilon}{1+x-\varepsilon}}\right[.
	}
	We are going to show that
	\Eq{rr}{
		\frac{1-r^2}{1+r^2}\in \,]x-\varepsilon,x+\varepsilon[\,\cap\, U
		\qquad \mbox{for all}\qquad r\in \Q\cap I.
	}
	Indeed, let $r\in\Q\cap I$ be arbitrary. Then there exists $(m,n)\in\Z\times\N$ such that $r=\frac{m}{n}$. Using that $r$ is bounded by the endpoints of $I$, we easily get that
	\Eq{*}{
		s:=\frac{1-r^2}{1+r^2}\in\,]x-\varepsilon,x+\varepsilon[\,.
	}
	On the other hand, $s\in\Q$ and
	\Eq{*}{
		\sqrt{1-s^2}
		=\sqrt{1-\bigg(\frac{1-r^2}{1+r^2}\bigg)^2}
		=\sqrt{1-\bigg(\frac{n^2-m^2}{n^2+m^2}\bigg)^2}
		=\frac{2nm}{n^2+m^2}\in\Q,
	}
	which completes the proof of \eq{rr}.

	To prove the density of $V$, let $x\in \,]-\infty,-1[\,\cup\,]1,\infty[\,$, that is, let $|x|>1$, let $0<\varepsilon<|x|-1$ be arbitrary and denote
	\Eq{*}{
		J:=
		\begin{cases}
			\left]\sqrt{\dfrac{x+\varepsilon-1}{x+\varepsilon+1}},\sqrt{\dfrac{x-\varepsilon-1}{x-\varepsilon+1}}\right[
			&\mbox{if } x<-1,\\[4mm]
			\left]\sqrt{\dfrac{x-\varepsilon-1}{x-\varepsilon+1}},\sqrt{\dfrac{x+\varepsilon-1}{x+\varepsilon+1}}\right[
			&\mbox{if } 1<x.\\
		\end{cases}
	}
	Then, one can easily check that $J$ is nonempty and $J\subseteq\,]1,\infty[\,$ if $x<-1$ and $J\subseteq\,]0,1[\,$ if $1<x$. Thus $1\not\in J$ holds in both cases.
	We are going to show that
	\Eq{rr2}{
		\frac{1+r^2}{1-r^2}\in \,]x-\varepsilon,x+\varepsilon[\,\cap\, V
		\qquad \mbox{for all}\qquad r\in \Q\cap J.
	}
	Indeed, let $r\in\Q\,\cap J$ be arbitrary. Then there exists $(m,n)\in\N\times\N$ such that $r=\frac{m}{n}$. Since $r$ cannot be equal to $1$, therefore $n\neq m$ holds. Using that $r$ is bounded by the endpoints of $J$, in each cases we easily get that
	\Eq{*}{
		s:=\frac{1+r^2}{1-r^2}\in\,]x-\varepsilon,x+\varepsilon[\,.
	}
	On the other hand, $s\in\Q$ and
	\Eq{*}{
		\sqrt{s^2-1}
		=\sqrt{\bigg(\frac{1+r^2}{1-r^2}\bigg)^2-1}
		=\sqrt{\bigg(\frac{n^2+m^2}{n^2-m^2}\bigg)^2-1}
		=\frac{2nm}{|n^2-m^2|}\in\Q,
	}
	which completes the proof of \eq{rr2}.

	To prove the density of $W$, let $x\in\R\setminus\{0\}$ and $0<\varepsilon<|x|$ be arbitrary and denote
	\Eq{*}{
		K:=
		\begin{cases}
			\left]\dfrac{-1}{x+\varepsilon}-\sqrt{\dfrac{1}{(x+\varepsilon)^2}+1},1\right[
			&\mbox{if } x<0,\\[4mm]
			\left]-1,\dfrac{-1}{x+\varepsilon}+\sqrt{\dfrac{1}{(x+\varepsilon)^2}+1}\right[
			&\mbox{if } 0<x.\\
		\end{cases}
	}
	Then, one can easily check that $K$ is nonempty and $K\subseteq\,]-1,1[\,$. Thus $1\not\in K$ holds in both cases.
	We are going to show that
	\Eq{rr3}{
		\frac{2r}{1-r^2}\in \,]x-\varepsilon,x+\varepsilon[\,\cap\, W
		\qquad \mbox{for all}\qquad r\in \Q\cap K.
	}
	Indeed, let $r\in\Q\cap K$ be arbitrary. Then there exists $(m,n)\in\Z\times\N$ such that $r=\frac{m}{n}$. Since $r$ cannot be equal to $1$, therefore $n\neq m$ holds. Using that $r$ is bounded by the endpoints of $K$, in each cases we easily get that
	\Eq{*}{
		s:=\frac{2r}{1-r^2}\in\,]x-\varepsilon,x+\varepsilon[\,.
	}
	On the other hand, $s\in\Q$ and
	\Eq{*}{
		\sqrt{1+s^2}
		=\sqrt{1+\bigg(\frac{2r}{1-r^2}\bigg)^2}
		=\sqrt{1+\bigg(\frac{2nm}{n^2-m^2}\bigg)^2}
		=\frac{n^2+m^2}{|n^2-m^2|}\in\Q,
	}
	which completes the proof of \eq{rr3}.
\end{proof}

\section{Extension of the result of Maksa}

In what follows we extend the result of Maksa \cite{Mak13a} by assuming the derivability of any of the exponential, hyperbolic or trigonometric functions on a small interval. Our approach is based on the use of the addition theorems for each of these functions and the application \cor{add}. In each particular case, we obtain that $d$ is a derivation with respect to a two-variable algebraic function.

\Thm{Mak}{
	Let $d:\R\to\R$ be an additive function and let $\alpha,\beta\in\R$ with $\alpha<\beta$. Suppose that $d$ is a derivation with respect to the restriction to $\,]\alpha,\beta[\,$ of any of the following functions with further assumptions on $\alpha$ and $\beta$, respectively:
	\Eq{Mak}{
	(i)\qquad\qquad\qquad&\exp \qquad&&(2\alpha<\beta\mbox{ and }\alpha<2\beta),\\
	(ii)\qquad\qquad\qquad	&\sinh \qquad&&(\alpha<0<\beta),\\
	(iii)\qquad\qquad\qquad	&\cosh \qquad&&(0<2\alpha<\beta\mbox{ or }\alpha<2\beta<0),\\
	(iv)\qquad\qquad\qquad	&\tanh \qquad&&(\alpha<0<\beta),\\
	(v)\qquad\qquad\qquad	&\coth \qquad&&(0<2\alpha<\beta\mbox{ or }\alpha<2\beta<0),\\
	(vi)\qquad\qquad\qquad	&\sin \qquad&&(\alpha<0<\beta),\\
	(vii)\qquad\qquad\qquad	&\cos \qquad&&(0<2\alpha<\pi<\beta\mbox{ or } \alpha<-\pi<2\beta<0),\\
	(viii)\qquad\qquad\qquad	&\tan \qquad&&(-\pi<2\alpha<\beta\mbox{ and }\alpha<2\beta<\pi),\\
	(ix)\qquad\qquad\qquad	&\cot \qquad&&(0<2\alpha<\beta<\pi\mbox{ or }-\pi<\alpha<2\beta<0).
	}
	Then $d$ is a standard derivation.
}

\begin{proof} Observe that in each of the above cases the inequalities $2\alpha<\beta$ and $\alpha<2\beta$ hold. Adding up these inequalities side by side, it follows that $\alpha<\beta$ and hence
	\Eq{*}{
		\gamma:=\tfrac12\max(\alpha,2\alpha)
		<\tfrac12\min(\beta,2\beta)=:\delta.
	}
	Then $\,]\gamma,\delta[\,\subseteq \,]\alpha,\beta[\,\cap \,]\tfrac\alpha2,\tfrac\beta2[\,$, which implies that
	\Eq{*}{
		\,]\gamma,\delta[\,+\,]\gamma,\delta[\,
		=\,]2\gamma,2\delta[\,\subseteq\,]\alpha,\beta[\,.
	}
	In the rest of proof, we shall utilize that each of the functions listed in \eq{Mak} possesses an addition formula, i.e., it satisfies  functional equation of type \eq{addition} with $\Omega_1:=\Omega_2:=\,]\gamma,\delta[\,$.

	$(i)$ Assume first that $2\alpha<\beta$ and $\alpha<2\beta$ and $d$ is a derivation with respect to the restriction to $]\alpha,\beta[\,$ of the exponential function. It means that the equation $d(\exp(x))=\exp(x)d(x)$ holds for all $x\in \,]\alpha,\beta[\,$. Using that this restriction satisfies the functional equation
	\Eq{*}{
		\exp(x+y)=\exp(x)\exp(y) \qquad(x,y\in\,]\gamma,\delta[\,),
	}
	\cor{add} implies that $d$ is a derivation with respect to the mapping
	\Eq{*}{
		(u,v)\mapsto u\cdot v\qquad(u,v\in\,]\exp(\gamma),\exp(\delta)[\,),
	}
	i.e., $d$ is of Leibniz-type on the interval $]\exp(\gamma),\exp(\delta)[\,$. In view of \lem{LRext}, it follows that $d$ is of  Leibniz-type on $\R$ and hence it is a standard derivation.

	$(ii)$ In the second case assume that $\alpha<0<\beta$ and $d(\sinh(x))=\cosh(x)d(x)$ holds for all $x\in\,]\alpha,\beta[\,$. Then $\gamma=\frac\alpha2$ and $\delta=\frac\beta2$. First we can choose $\lambda>0$ such that $\,]-\lambda,\lambda[\,\subseteq \,]\gamma,\delta[\,$. Using the identity $\cosh(x)=\sqrt{1+\sinh^2(x)}$ ($x\in\,]-\lambda,\lambda[\,$), we obtain that the restriction of the sine hyperbolic function to the interval $\,]\alpha,\beta[\,$ satisfies the functional equation
	\Eq{*}{
		\sinh(x+y)=\sinh(x)\sqrt{1+\sinh^2(y)}+\sqrt{1+\sinh^2(x)}\sinh(y)
	}
	for all $x,y\in\,]-\lambda,\lambda[\,$. By \cor{add}, it follows that $d$ is also a derivation with respect to the function
	\Eq{*}{
		(u,v)\mapsto u\sqrt{1+v^2}+v\sqrt{1+u^2}\qquad (u,v\in\,]-\sinh(\lambda),\sinh(\lambda)[\,).
	}
	It means that the functional equation
	\Eq{Phisinh}{
		d(u&\sqrt{1+v^2}+v\sqrt{1+u^2}) \\&
		=\Big(\sqrt{1+v^2}+v\frac{u}{\sqrt{1+u^2}}\Big)d(u)+\Big(\sqrt{1+u^2}+u\frac{v}{\sqrt{1+v^2}}\Big)d(v)
	}
	holds for all $u,v\in\,]-\sinh(\lambda),\sinh(\lambda)[\,$. Replacing $v$ by $-v$ and adding the equality so obtained to \eq{Phisinh} side by side, we get that
	\Eq{Phisinh+}{
		d(u\sqrt{1+v^2})
		=\sqrt{1+v^2}d(u)+u\frac{v}{\sqrt{1+v^2}}d(v)
	}
	holds for all $u,v\in\,]-\sinh(\lambda),\sinh(\lambda)[\,$. Let $U$ be the set defined in \lem{Ratio}. Then, by this lemma, the intersection $U\cap \,]-\sinh(\lambda),\sinh(\lambda)[\,$ is nonempty, moreover it is dense in $]-\sinh(\lambda),\sinh(\lambda)[\,$. Then, for $u,v\in U\cap \,]-\sinh(\lambda),\sinh(\lambda)[\,$, we have that $u,v,$ and $\sqrt{1+v^2}\in\Q$. For such values of $u$ and $v$, the equality \eq{Phisinh+} and the $\Q$-homogeneity of $d$ implies that
	\Eq{*}{
		u\sqrt{1+v^2}d(1)
		=\sqrt{1+v^2}ud(1)+u\frac{v}{\sqrt{1+v^2}}vd(1),
	}
	which is possible only if $d(1)=0$. Let $0\neq u\in\,]-\sinh(\lambda),\sinh(\lambda)[\,\cap\,\Q$,
	and $v\in\,]-\sinh(\lambda),\sinh(\lambda)[\,$. By the $\Q$-homogeneity and additivity of $d$, it follows that $d(u)=ud(1)=0$ and hence \eq{Phisinh+} simplifies to \eq{bor} on the interval $]-\sinh(\lambda),\sinh(\lambda)[\,$. Using this, \eq{Phisinh+} can be rewritten as
	\Eq{*}{
		d(u\sqrt{1+v^2})
		=\sqrt{1+v^2}d(u)+ud(\sqrt{1+v^2})
	}
	for all $u,v\in \,]-\sinh(\lambda),\sinh(\lambda)[\,$. With the substitution $w:=\sqrt{1+v^2}$, this equality yields that
	\Eq{*}{
		d(uw)=ud(w)+wd(u)
	}
	for all $u\in \,]-\sinh(\lambda),\sinh(\lambda)[\,$ and $w\in\,[1,\cosh(\lambda)[$. Then, in view of \lem{LRext}, $d$ is of Leibniz-type and hence is a standard derivation on $\R$.

	$(iii)$ In the third case suppose that $0<2\alpha<\beta$ (the other case can be treated similarly) and $d(\cosh(x))=\sinh(x)d(x)$ holds for all $x\in\,]\alpha,\beta[\,$. Then $\gamma=\alpha$ and $\delta=\frac\beta2$. The restriction of the cosine hyperbolic function to the interval $\,]\alpha,\beta[\,$ satisfies the functional equation
	\Eq{*}{
		\cosh(x+y)=\cosh(x)\cosh(y)+\sqrt{\cosh^2(x)-1}\sqrt{\cosh^2(y)-1}
	}
	for all $x,y\in\,]\gamma,\delta[\,$. By \cor{add}, it follows that $d$ is also a derivation with respect to the function
	\Eq{*}{
		(u,v)\mapsto uv+\sqrt{u^2-1}\sqrt{v^2-1}\qquad (u,v\in\,]\cosh(\gamma),\cosh(\delta)[\,),
	}
	i.e., the functional equation
	\Eq{Phicosh}{
		d(uv+\sqrt{u^2-1}\sqrt{v^2-1})=\Big(v+u\frac{\sqrt{v^2-1}}{\sqrt{u^2-1}}\Big)d(u)+\Big(u+v\frac{\sqrt{u^2-1}}{\sqrt{v^2-1}}\Big)d(v)
	}
	holds for all $u,v\in\,]\cosh(\gamma),\cosh(\delta)[\,$. Let $V$ be the set defined in \lem{Ratio}. Then, by this lemma, the intersection $V\cap \,]\cosh(\gamma),\cosh(\delta)[\,$ is nonempty, moreover it is dense in $]\cosh(\gamma),\cosh(\delta)[\,$. Then, for $u,v\in V\cap \,]\cosh(\gamma),\cosh(\delta)[\,$, we have that $u,v,$ and $\sqrt{v^2-1}\in\Q$. For such values of $u$ and $v$, the equality \eq{Phicosh} and the $\Q$-homogeneity of $d$ implies that
	\Eq{*}{
		(uv+\sqrt{u^2-1}&\sqrt{v^2-1})d(1)\\&
		=\Big(v+u\frac{\sqrt{v^2-1}}{\sqrt{u^2-1}}\Big)ud(1)+\Big(u+v\frac{\sqrt{u^2-1}}{\sqrt{v^2-1}}\Big)vd(1),
	}
	which is possible only if $d(1)=0$. Substituting $v:=u$ in \eq{Phicosh}, using the additivity and $\Q$-homogeneity of $d$ and that $d(1)=0$ we get that \eq{xr} with $r=2$ holds for all $u\in\,]\cosh(\gamma),\cosh(\delta)[\,$, which, using \lem{Nis}, implies that $d$ is a standard derivation.

	$(iv)$ In the fourth case assume that $\alpha<0<\beta$ and $d(\tanh(x))=\frac{1}{\cosh^2(x)}d(x)$ is valid for all $x\in\,]\alpha,\beta[\,$. Then $\gamma=\frac\alpha2$ and $\delta=\frac\beta2$. The restriction of the tangent hyperbolic function to the interval $\,]\alpha,\beta[\,$ satisfies the functional equation
	\Eq{*}{
		\tanh(x+y)=\frac{\tanh(x)+\tanh(y)}{1+\tanh(x)\tanh(y)} \qquad(x,y\in\,]\gamma,\delta[\,).
	}
	By \cor{add}, it follows that $d$ is also a derivation with respect to the function
	\Eq{*}{
		(u,v)\mapsto\frac{u+v}{1+uv}\qquad(u,v\in\,]\tanh(\gamma),\tanh(\delta)[\,),
	}
	i.e., the functional equation
	\Eq{Phitanh}{
		d\Big(\frac{u+v}{1+uv}\Big)=\frac{1-v^2}{(1+uv)^2}d(u)+\frac{1-u^2}{(1+uv)^2}d(v)
	}
	holds for all $u,v\in\,]\tanh(\gamma),\tanh(\delta)[\,$. Now choose a subinterval $\,]\lambda,\mu[\,$ of $\,]\tanh(\gamma),\tanh(\delta)[\,$ such that $\lambda,\mu\in\Q$ and $0<\lambda\mu=:r$. It is easy to see that if $u\in \,]\lambda,\mu[\,$, then $\frac{r}{u}\in \,]\lambda,\mu[\,$ also holds. Substituting $u\in \,]\lambda,\mu[\,$ and $v:=\frac{r}{u}$, \eq{Phitanh} implies
	\Eq{*}{
		\frac1{1+r}d\Big(u+\frac{r}{u}\Big)=\frac{1-(\frac{r}{u})^2}{(1+r)^2}d(u)+\frac{1-u^2}{(1+r)^2}d\Big(\frac{r}{u}\Big).
	}
	A direct and simple computation yields that
	\Eq{*}{
		-\frac{1}{u^2}d(u)=d\Big(\frac{1}{u}\Big)
	}
	for $u\in \,]\lambda,\mu[\,$, which, using \lem{Nis}, implies that $d$ is a standard derivation.

	$(v)$ In the fifth case assume that $0<2\alpha<\beta$ (the other case can be handled similarly) and $d(\coth(x))=-\frac{1}{\sinh^2(x)}d(x)$ holds for all $x\in\,]\alpha,\beta[\,$. Then $\gamma=\frac\alpha2$ and $\delta=\frac\beta2$. The restriction of the cotangent hyperbolic function to the interval $\,]\alpha,\beta[\,$ satisfies the functional equation
	\Eq{*}{
		\coth(x+y)=\frac{\coth(x)\coth(y)+1}{\coth(x)+\coth(y)} \qquad(x,y\in\,]\gamma,\delta[\,).
	}
	By \cor{add}, it follows that $d$ is also a derivation with respect to the function
	\Eq{*}{
		(u,v)\mapsto\frac{uv+1}{u+v}\qquad(u,v\in\,]\coth(\delta),\coth(\gamma)[\,),
	}
	i.e., the functional equation
	\Eq{Phicoth}{
		d\Big(\frac{uv+1}{u+v}\Big)=\frac{v^2-1}{(u+v)^2}d(u)+\frac{u^2-1}{(u+v)^2}d(v)
	}
	holds for all $u,v\in\,]\coth(\delta),\coth(\gamma)[\,$. Now choose a subinterval $\,]\lambda,\mu[\,$ of $\,]\coth(\delta),\coth(\gamma)[\,$ such that  $\lambda,\mu\in\Q$ and $\lambda+\mu=:r\neq0$. It is easy to see that if $u\in \,]\lambda,\mu[\,$, then $r-u\in \,]\lambda,\mu[\,$ also holds. Substituting $u\in \,]\lambda,\mu[\,$ and $v:=r-u$, \eq{Phicoth} implies
	\Eq{*}{
		\frac1r d(u(r-u)+1)=\frac{(r-u)^2-1}{r^2}d(u)+\frac{u^2-1}{r^2}d(r-u).
	}
	This equality, using the additivity and $\Q$-homogeneity, after some simplification, reduces to
	\Eq{*}{
		d(u^2)=2ud(u)+2d(1)-u^2d(1)\qquad(u\in\,]\lambda,\mu[\,).
	}
	If $u$ is rational, then this equality gives that $d(1)=0$. Hence the above equality shows that \eq{xr} is valid on $]\lambda,\mu[\,$ with $r=2$. In view of \lem{Nis}, we obtain that $d$ is a standard derivation.

	$(vi)$ In the sixth case assume that $\alpha<0<\beta$ and $d(\sin(x))=\cos(x)d(x)$ holds for all $x\in\,]\alpha,\beta[\,$. Then $\gamma=\frac\alpha2$ and $\delta=\frac\beta2$. First we can choose $\lambda>0$ such that $\,]-\lambda,\lambda[\,\subseteq \,]\gamma,\delta[\,\cap\,]-\frac\pi2,\frac\pi2[\,$. Thus the cosine function is everywhere positive over $\,]-\lambda,\lambda[\,$. Then the sine function is strictly increasing on $\,]-\lambda,\lambda[\,$ and $\cos(x)=\sqrt{1-\sin^2(x)}$ holds for all $x\in\,]-\lambda,\lambda[\,$. Therefore the restriction of the sine function to the interval $\,]\alpha,\beta[\,$ satisfies the functional equation
	\Eq{*}{
		\sin(x+y)=\sin(x)\sqrt{1-\sin^2(y)}+\sqrt{1-\sin^2(x)}\sin(y)
		\qquad (x,y\in\,]-\lambda,\lambda[\,).
	}
	By \cor{add}, it follows that $d$ is also a derivation with respect to the function
	\Eq{*}{
		(u,v)\mapsto u\sqrt{1-v^2}+v\sqrt{1-u^2}\qquad (u,v\in\,]-\sin(\lambda),\sin(\lambda)[\,).
	}
	It means that the functional equation
	\Eq{Phisin}{
		d(u&\sqrt{1-v^2}+v\sqrt{1-u^2}) \\&
		=\Big(\sqrt{1-v^2}-v\frac{u}{\sqrt{1-u^2}}\Big)d(u)+\Big(\sqrt{1-u^2}-u\frac{v}{\sqrt{1-v^2}}\Big)d(v)
	}
	holds for all $u,v\in\,]-\sin(\lambda),\sin(\lambda)[\,$. Replacing $v$ by $-v$ and adding the equality so obtained to \eq{Phisin} side by side, we get that
	\Eq{Phisin+}{
		d(u\sqrt{1-v^2})
		=\sqrt{1-v^2}d(u)-u\frac{v}{\sqrt{1-v^2}}d(v)
	}
	holds for all $u,v\in\,]-\sin(\lambda),\sin(\lambda)[\,$. Let $W$ be the set defined in \lem{Ratio}. Then, by this lemma, the intersection $W\cap \,]-\sin(\lambda),\sin(\lambda)[\,$ is nonempty, moreover it is dense in $]-\sin(\lambda),\sin(\lambda)[\,$. Then, for $u,v\in W\cap \,]-\sin(\lambda),\sin(\lambda)[\,$, we have that $u,v,$ and $\sqrt{1-v^2}\in\Q$. For such values of $u$ and $v$, the equality \eq{Phisin+} and the $\Q$-homogeneity of $d$ implies that
	\Eq{*}{
		u\sqrt{1-v^2}d(1)
		=\sqrt{1-v^2}ud(1)-u\frac{v}{\sqrt{1-v^2}}vd(1),
	}
	which is possible only if $d(1)=0$. Let $0\neq u\in\,]-\sin(\lambda),\sin(\lambda)[\,\cap\,\Q$,
	and $v\in\,]-\sin(\lambda),\sin(\lambda)[\,$. By the $\Q$-homogeneity and additivity of $d$, it follows that $d(u)=ud(1)=0$ and hence \eq{Phisin+} simplifies to \eq{bor} on the interval $]-\sin(\lambda),\sin(\lambda)[\,$. Using this, \eq{Phisin+} can be rewritten as
	\Eq{*}{
		d(u\sqrt{1-v^2})
		=\sqrt{1-v^2}d(u)+ud(\sqrt{1-v^2})
	}
	for all $u,v\in \,]-\sin(\lambda),\sin(\lambda)[\,$.
	With the substitution $w:=\sqrt{1-v^2}$, this equality yields that
	\Eq{*}{
		d(uw)=ud(w)+wd(u)
	}
	for all $u\in \,]-\sin(\lambda),\sin(\lambda)[\,$ and $w\in\,]\cos(\lambda),1]$. Then, in view of \lem{LRext}, $d$ is of Leibniz-type and hence is a standard derivation on $\R$.

	$(vii)$ In the seventh case suppose that $0<2\alpha<\pi<\beta$ (the other case can be treated similarly) and $d(\cos(x))=-\sin(x)d(x)$ holds for all $x\in\,]\alpha,\beta[\,$. Then $\gamma=\alpha$ and $\delta=\frac\beta2$ and we can choose $\lambda\in\,]0,\frac{\pi}{2}[\,$ such that $\,]\frac{\pi}{2}-\lambda,\frac{\pi}{2}+\lambda[\,\subseteq \,]\gamma,\delta[\,$. Thus the sine function is positive over $\,]\frac{\pi}{2}-\lambda,\frac{\pi}{2}+\lambda[\,$ and hence $\sin(x)=\sqrt{1-\cos^2(x)}$ holds for all $x\in\,]\frac{\pi}{2}-\lambda,\frac{\pi}{2}+\lambda[\,$. The restriction of the cosine function to the interval $\,]\alpha,\beta[\,$ satisfies the functional equation
	\Eq{*}{
		\cos(x+y)=\cos(x)\cos(y)-\sqrt{1-\cos^2(x)}\sqrt{1-\cos^2(y)}
	}
	for all $x,y\in\,]\tfrac{\pi}{2}-\lambda,\tfrac{\pi}{2}+\lambda[\,$.
	By \cor{add}, it follows that $d$ is also a derivation with respect to the function
	\Eq{*}{
		(u,v)\mapsto uv-\sqrt{1-u^2}\sqrt{1-v^2}\qquad (u,v\in\,]\cos(\tfrac{\pi}{2}+\lambda),\cos(\tfrac{\pi}{2}-\lambda)[\,),
	}
	i.e., the functional equation
	\Eq{Phicos}{
		d(uv-\sqrt{1-u^2}\sqrt{1-v^2})=\Big(v+u\frac{\sqrt{1-v^2}}{\sqrt{1-u^2}}\Big)d(u)+\Big(u+v\frac{\sqrt{1-u^2}}{\sqrt{1-v^2}}\Big)d(v)
	}
	holds for all $u,v\in\,]\cos(\tfrac{\pi}{2}+\lambda),\cos(\tfrac{\pi}{2}-\lambda)[\,$. Replacing $v$ by $-v$ and subtracting the equality so obtained from \eq{Phicos}, we get that
	\Eq{Phicos+}{
		d(uv)=vd(u)+ud(v)
	}
	holds for all $u,v\in\,]\cos(\tfrac{\pi}{2}+\lambda),\cos(\tfrac{\pi}{2}-\lambda)[\,$.
	Hence, in view of \lem{LRext}, we get that $d$ is a standard derivation on $\R$.

	$(viii)$ In the eighth case suppose that $-\pi<2\alpha<\beta$ and $\alpha<2\beta<\pi$ and $d(\tan(x))=\frac{1}{\cos^2(x)}d(x)$ is valid for all $x\in\,]\alpha,\beta[\,$. The restriction of the tangent function to the interval $\,]\alpha,\beta[\,$ satisfies the functional equation
	\Eq{*}{
		\tan(x+y)=\frac{\tan(x)+\tan(y)}{1-\tan(x)\tan(y)}
		\qquad(x,y\in\,]\gamma,\delta[\,).
	}
	By \cor{add}, it follows that $d$ is also a derivation with respect to the function
	\Eq{*}{
		(u,v)\mapsto\frac{u+v}{1-uv}\qquad(u,v\in\,]\tan(\gamma),\tan(\delta)[\,),
	}
	i.e., the functional equation
	\Eq{Phitan}{
		d\Big(\frac{u+v}{1-uv}\Big)=\frac{1+v^2}{(1-uv)^2}d(u)+\frac{1+u^2}{(1-uv)^2}d(v)
	}
	holds for all $u,v\in\,]\tan(\gamma),\tan(\delta)[\,$. Now choose a subinterval $\,]\lambda,\mu[\,$ of $\,]\tan(\gamma),\tan(\delta)[\,$ such that $\lambda,\mu\in\Q$ and $0<\lambda\mu=:r\neq1$. It is easy to see that if $u\in \,]\lambda,\mu[\,$, then $\frac{r}{u}\in \,]\lambda,\mu[\,$ also holds. Substituting $u\in \,]\lambda,\mu[\,$ and $v:=\frac{r}{u}$, \eq{Phitan} implies
	\Eq{*}{
		\frac1{1-r}d\Big(u+\frac{r}{u}\Big)=\frac{1+(\frac{r}{u})^2}{(1-r)^2}d(u)+\frac{1+u^2}{(1-r)^2}d\Big(\frac{r}{u}\Big).
	}
	A direct and simple computation yields that
	\Eq{*}{
		-\frac{1}{u^2}d(u)=d\Big(\frac{1}{u}\Big)
	}
	for $u\in \,]\lambda,\mu[\,$, which, using \lem{Nis}, yields that $d$ is a standard derivation.

	$(ix)$ In the last case suppose that $0<2\alpha<\beta<\pi$ (the case $-\pi<\alpha<2\beta<0$ can be treated similarly) and $d(\cot(x))=-\frac{1}{\sin^2(x)}d(x)$ is valid for all $x\in\,]\alpha,\beta[\,$. The restriction of the cotangent function to the interval $\,]\alpha,\beta[\,$ satisfies the functional equation
	\Eq{*}{
		\cot(x+y)=\frac{\cot(x)\cot(y)-1}{\cot(x)+\cot(y)} \qquad(x,y\in\,]\gamma,\delta[\,).
	}
	By \cor{add}, it follows that $d$ is also a derivation with respect to the function
	\Eq{*}{
		(u,v)\mapsto\frac{uv-1}{u+v}\qquad(u,v\in\,]\cot(\delta),\cot(\gamma)[\,),
	}
	i.e., the functional equation
	\Eq{Phicot}{
		d\Big(\frac{uv-1}{u+v}\Big)=\frac{1+v^2}{(u+v)^2}d(u)+\frac{1+u^2}{(u+v)^2}d(v)
	}
	holds for all $u,v\in\,]\cot(\delta),\cot(\gamma)[\,$. Now choose a subinterval $\,]\lambda,\mu[\,$ of $\,]\cot(\delta),\cot(\gamma)[\,$ such that  $\lambda,\mu\in\Q$ and $\lambda+\mu=:r\neq0$. It is easy to see that if $u\in \,]\lambda,\mu[\,$, then $r-u\in \,]\lambda,\mu[\,$ also holds. Substituting $u\in \,]\lambda,\mu[\,$ and $v:=r-u$, \eq{Phicot} implies
	\Eq{*}{
		\frac1r d(u(r-u)-1)=\frac{1+(r-u)^2}{r^2}d(u)+\frac{1+u^2}{r^2}d(r-u).
	}
	This equality, using the additivity and $\Q$-homogeneity, after some simplification, reduces to
	\Eq{*}{
		d(u^2)=2ud(u)-2d(1)-u^2d(1)\qquad(u\in\,]\lambda,\mu[\,).
	}
	If $u$ is rational, then this equality gives that $d(1)=0$. Hence the above equality shows that \eq{xr} is valid on $]\lambda,\mu[\,$ with $r=2$. In view of \lem{Nis} we get that $d$ is a standard derivation.
\end{proof}

When considering the interval $\,]\alpha,\beta[\,$, one should observe that depending on additional assumptions described in the nine cases of the theorem, this interval can be arbitrary small in all the cases except the case $(vii)$, then it contains either $[\pi/2,\pi]$ or $[-\pi,-\pi/2]$.

\section{Extension of the result of Nishiyama and Horinouchi}

\Thm{PQ}{Let $d:\R\to\R$ be an additive function, $I$ be a nonempty open interval not containing zero and assume that $P,Q:I\to\R$ are of the form
\Eq{PQ0}{
  P(u)=\sum_{k\in\Z} p_ku^k,\qquad Q(u)=\sum_{k\in\Z} q_ku^k,
}
where $p_k,q_k\in\Q$ for all $k\in\Z$ and the set $\{k\in\Z\mid (p_k,q_k)\neq(0,0)\}$ is finite. Then
\Eq{PQ}{
   Q'(u)d(P(u))=P'(u)d(Q(u))\qquad (u\in I)
}
holds if and only if
\begin{enumerate}[(i)]                                                                                \item either $P$ and $Q$ are linearly dependent,
\item or $P$ and $Q$ are linearly independent, $P-p_0$ and $Q-q_0$ are linearly dependent and $d(1)=0$,
\item or $P-p_0$ and $Q-q_0$ are linearly independent and $d$ is a standard derivation.
\end{enumerate}}

\begin{proof} First we prove the necessity of (i)--(iii).
Assume that \eq{PQ} holds and $P$, $Q$ are linearly independent. Then the Wronskian $P$ and $Q$ is not identically zero on $I$, i.e., there exists $u_0\in I$ such that $P'(u_0)Q(u_0)\neq P(u_0)Q'(u_0)$.

Substituting $u\in I\cap\Q$ we have that $P(u)$ and $Q(u)$ are rational numbers. Therefore, using the $\Q$-homogeneity of $d$, \eq{PQ} implies that
\Eq{PQu}{
  Q'(u)P(u)d(1)=P'(u)Q(u)ud(1)
}
for all $u\in I\cap\Q$. By the continuity of $P$ and $Q$ and the density of $I\cap\Q$ in $I$, it follows that \eq{PQu} holds for all $u\in I$, in particular, for $u=u_0$, which implies that $d(1)=0$.

From now on, we assume that $P-p_0$ and $Q-q_0$ are linearly independent.
Let $k_0$ denote the smallest element of the finite set $\{k\in\Z\setminus\{0\}\mid (p_k,q_k)\neq(0,0)\}$. Then $u^{-k_0}(P(u)-p_0)$ and $u^{-k_0}(Q(u)-q_0)$ are linearly independent polynomials of the variable $u$. This is equivalent to the linear independence of the coefficients of $P-p_0$ and $Q-q_0$, that is, of $(p_k)_{k\in\Z\setminus\{0\}}$ and $(q_k)_{k\in\Z\setminus\{0\}}$. Therefore, the system of vectors $(p_k,q_k)_{k\in\Z\setminus\{0\}}$ spans $\R^2$. Thus there exists $\ell\in\Z\setminus\{0\}$ such that, for $0\neq k<\ell$, the vector $(p_k,q_k)$ is parallel to $(p_{k_0},q_{k_0})$ and $(p_\ell,q_\ell)$ is not  parallel to $(p_{k_0},q_{k_0})$. Then,
\Eq{kl}{
  p_iq_j=p_jq_i \qquad (0\neq i<\ell,\,0\neq j<\ell)
  \qquad\mbox{and}\qquad
  p_{k_0}q_\ell\neq p_\ell q_{k_0}.
}

Now let $v\in I$ be fixed and $r\in (I/v)\cap\Q)$. Then $u=rv\in I$, therefore, the equality \eq{PQ}, the additivity and $\Q$-homogeneity of $d$ imply
\Eq{*}{
  \bigg(\sum_{j\in\Z}q_jjr^{j-1}v^{j-1}\bigg)
  \bigg(\sum_{i\in\Z} p_ir^{i}d(v^i)\bigg)
  =\bigg(\sum_{i\in\Z}p_iir^{i-1}v^{i-1}\bigg)
  \bigg(\sum_{j\in\Z} q_jr^{j}d(v^j)\bigg).
}
Using that $d(1)=0$, this equality is equivalent to
\Eq{ij}{
  \sum_{i\in\Z\setminus\{0\}}\sum_{j\in\Z\setminus\{0\}}
  p_iq_jr^{i+j-1}(jv^{j-1}d(v^i)-iv^{i-1}d(v^j))=0.
}
This implies
\Eq{*}{
  \sum_{i<j,\,ij\neq0}
  (p_iq_j-p_jq_i)r^{i+j-1}(jv^{j-1}d(v^i)-iv^{i-1}d(v^j))=0.
}
According to the choice of $k_0$ and $\ell$, we have \eq{kl}, therefore,
\Eq{*}{
  \sum_{k_0\leq i,\,\max(i+1,\ell)\leq j,\,ij\neq0}
  (p_iq_j-p_jq_i)r^{i-k_0+j-\ell}(jv^{j-1}d(v^i)-iv^{i-1}d(v^j))=0.
}
The left hand side of this equality is a polynomial of $r$, hence its value at $r=0$ is equal to zero, which gives
\Eq{*}{
  (p_{k_0}q_\ell-p_\ell q_{k_0})(\ell v^{\ell-1}d(v^{k_0})-k_0v^{k_0-1}d(v^\ell))=0.
}
By the last relation in \eq{kl}, this yields
\Eq{*}{
  \ell d(v^{k_0})=k_0v^{k_0-\ell}d(v^\ell) \qquad(v\in I).
}
With the substitution $u:=v^\ell$, and with the notation $r:=\frac{k_0}{\ell}$, we get
\Eq{*}{
  d(u^r)=ru^{r-1}d(u) \qquad(u\in J:=\{x^\ell\mid x\in I\}).
}
Observe that $r\in\Q\setminus\{0,1\}$, therefore, by \lem{Nis}, it follows that $d$ is a standard derivation.

If condition (i) holds and $P$ is not identically zero, then $Q$ is a rational multiple of $P$, hence \eq{PQ} is trivially valid by the $\Q$-homogeneity of $d$.

If condition (ii) holds, then, denoting $P_0:=P-p_0$ and $Q_0:=Q-q_0$ and using (i) for $P_0$ and $Q_0$, we have
\Eq{*}{
  Q'(u)&d(P(u))=Q_0'(u)d(P_0(u)+p_0)
  =Q_0'(u)(d(P_0(u))+p_0d(1))=Q_0'(u)d(P_0(u))\\
  &=P_0'(u)d(Q_0(u))=P_0'(u)(d(Q_0(u))+q_0d(1))
  =P_0'(u)d(Q_0(u)+q_0)=P'(u)d(Q(u)).
}
Finally, if condition (iii) is valid, i.e., $d$ is a standard derivation, then, for all $u\in I$ and $i,j\in\Z$,
\Eq{*}{
   ju^{j-1}d(u^i)=ju^{j-1}iu^{i-1}d(u)=iu^{i-1}d(u^j).
}
Multiplying this equality by $p_iq_j$, then summing up the equalities so obtained side by side for $(i,j)\in\Z^2$, we obtain that
\Eq{*}{
  \bigg(\sum_{j\in\Z}q_jju^{j-1}\bigg)
  \bigg(\sum_{i\in\Z} p_id(u^i)\bigg)
  =\bigg(\sum_{i\in\Z}p_iiu^{i-1}\bigg)
  \bigg(\sum_{j\in\Z} q_jd(u^j)\bigg).
}
This equality, by the additivity and $\Q$-homogeneity of $d$ is equivalent to \eq{PQ}.
\end{proof}

\Cor{PQ}{Let $d:\R\to\R$ be an additive function, $I$ be a nonempty open interval not containing zero and assume that $P,Q:I\to\R$ are of the form \eq{PQ0}, where $p_k,q_k\in\Q$ for all $k\in\Z$ and the set $\{k\in\Z\mid (p_k,q_k)\neq(0,0)\}$ is finite. Assume that $Q'$ is non-vanishing on $I$, furthermore $P-p_0$ and $Q-q_0$ are linearly independent and $d$ derivates $P\circ Q^{-1}$ on $J:=Q(I)$. Then $d$ is a standard derivation.}

\begin{proof}
Using that $d$ derivates $P\circ Q^{-1}$, we have
\Eq{*}{
	d(P(Q^{-1}(v)))=P'(Q^{-1}(v))\frac{1}{Q'(Q^{-1}(v))}d(v)\qquad(v\in J).
}
Substituting $u:=Q^{-1}(v)\in I$ into the above equation, we can see that \eq{PQ} holds. Taking into consideration that $P-p_0$ and $Q-q_0$ are linearly independent by assumption, \thm{PQ} implies that $d$ is a standard derivation.
\end{proof}

\Cor{pol}{Let $d:\R\to\R$ be an additive function, let $P$ be a nonzero real polynomial with rational coefficients and $I$ be a nonempty open subinterval of $\R$. Then $d$ derivates $P$ over $I$ if and only if
\begin{enumerate}[(i)]                                                                                \item either $\deg(P)=0$ and $d(1)=0$,
\item or $\deg(P)=1$ and $P(0)d(1)=0$,
\item or $\deg(P)\geq2$ and $d$ is a standard derivation.
\end{enumerate}
}

\begin{proof}
 This statement is an immediate consequence of \thm{PQ} by choosing $Q(u)=u$.
\end{proof}

\section{Open Questions}

Motivated by the results of the previous section, we can formulate two open problems. Let $P,Q:I\to\R$ by of the form \eq{PQ0}, where $p_k,q_k\in\Q$ for all $k\in\Z$ and the set $\{k\in\Z\mid (p_k,q_k)\neq(0,0)\}$ is finite and let $d:\R\to\R$ be an additive function.

\textbf{Problem 1.} Assume that $Q$ is non-vanishing on $I$ and $d$ derivates $P/Q$ on $I$, that is,
\Eq{*}{
  d\bigg(\frac{P(u)}{Q(u)}\bigg)
  =\frac{P'(u)Q(u)-Q'(u)P(u)}{Q^2(u)}d(u) \qquad(u\in I).
}
Under what conditions on $P$ and $Q$ does this equality imply that $d$ is a standard derivation?

\textbf{Problem 2.} Assume that $P'$ is non-vanishing on $I$ and $Q(I)\subseteq P(I)$ and $d$ derivates $P^{-1}\circ Q$ on $I$, that is,
\Eq{*}{
  d\big(P^{-1}(Q(u)\big)=\frac{Q'(u)}{P'(P^{-1}(Q(u)))} d(u) \qquad(u\in I).
}
This, provided that $Q$ is strictly monotone on $I$, is equivalent to the
condition
\Eq{*}{
  P'(P^{-1}(v))d\big(P^{-1}(v)\big)=Q'(Q^{-1}(v)) d(Q^{-1}(v)) \qquad(v\in Q(I)).
}
Under what conditions on $P$ and $Q$ does this equality imply that $d$ is a standard derivation?

The result of Boros and Erdei \cite{BorErd05} would be a particular case of such a generalization.


TITLE: Resolve $A=\cos{(\pi/7)}+\cos{(3\pi/7)}+\cos{(5\pi/7)}$ using $u=A+iB$
QUESTION [0 upvotes]: With these two sums:
$$A=\cos(\pi/7)+\cos(3\pi/7)+\cos(5\pi/7)$$
$$B=\sin(\pi/7)+\sin(3\pi/7)+\sin(5\pi/7)$$
How to find the explicit value of $A$ using:

$u=A+iB$
the sum of $n$ terms in a geometric sequence: $u_0*\frac{1-q^{n+1}}{1-q}$

I know the answer is $\frac 12$ from this post, but there is no mention of this method.

REPLY [0 votes]: Using Euler formula,
setting $2y=i\frac{\pi}7\implies e^{14y}=-1$
$$A+iB=\sum_{r=0}^2e^{(2r+1)2y}=e^{2y}\cdot\dfrac{1-(e^{4y})^3}{1-e^{4y}}=\dfrac{e^{2y}+1}{1-e^{4y}}=\dfrac1{1-e^{2y}}$$
Now, $\displaystyle\dfrac1{1-e^{i2u}}=\dfrac{-e^{-iu}}{e^{iu}-e^{-iu}}=-\dfrac{\cos u-i\sin u}{2i\sin u}=\dfrac12+i\cdot\dfrac{\cot u}2$
Now equate the real parts.


TITLE: Min Max Principle and Rayleigh-Ritz-Method for eigenvalues of unbounded operators?
QUESTION [9 upvotes]: Finding eigenvalues of matrices using the Rayleigh-Ritz quotient is well-known, c.f. http://en.wikipedia.org/wiki/Min-max_theorem
Does the following generalization of that fact also hold?
Theorem: Let $H$ be a complex Hilbert space, $T:D \to H$ be an unbounded operator defined on a dense domain $D \subset H$. Assume that $T$ is self-adjoint and has discrete spectrum contained in some interval $[c,\infty[$, $c > 0$. Enumerate the eigenvalues by $\lambda_1 \leq \lambda_2 \leq \ldots$ counting with multiplicities. Then for each $k \in \mathbb{N}$
$$ \lambda_k = \min_{\substack{U \subset D, \\ \dim U=k }}{\max_{\substack{x \in U, \\\|x\|=1}}{\langle Tx, x  \rangle}} $$
If this is true, can you give a good reference for this?

REPLY [6 votes]: I know this post is maybe two years too late, but I have a reference for you to check.  There is in fact a corresponding theorem for self-adjoint operators on Hilbert spaces, but the conditions are altered slightly since operators have more than one kind of spectrum.  An operator's spectrum can be divided into its discrete spectrum (eigenvalues) and its essential spectrum, which is defined in terms of projection-valued measures of an operator (using the functional calculus for self-adjoint operators you can define $\chi_B(A)$ where $A$ is self-adjoint, $\chi_B$ is the characteristic function on $B$, and $B$ is any Borel measurable set.  The essential spectrum $\sigma_{ess}(H)$ are those $\lambda \in \mathbb{C}$ such that $\chi_{(\lambda - \epsilon, \lambda+\epsilon)}(A)$ has infinite-dimensional range for all $\epsilon>0$).  Anyway the following statement of the theorem is taken out of Reed and Simon's Book on Operators.

Let $H$ be a self-adjoint operator bounded below (meaning $H \geq cI$ for some $c$).  Define $$U_H(\varphi_1, \ldots, \varphi_m) \;\; =\;\; \inf_{\begin{subarray}{c} \psi\in D(H), \; ||\psi||=1 \\ \psi \in [ \varphi_1, \ldots, \varphi_m]^\perp \end{subarray} } \langle \psi, H\psi \rangle $$ and $$\mu_n(H) \;\; =\;\; \sup_{\varphi_1, \ldots, \varphi_{n-1}} U_H(\varphi_1, \ldots, \varphi_{n-1}) $$ where $[\varphi_1, \ldots, \varphi_{m-1}]^\perp = \{\psi \; : \; \langle \psi, \varphi_i\rangle =0, \; i= 1\ldots, m-1\}$ where the $\varphi_i$ are not necessarily independent.  Then for each fixed $n$ one of the following occurs:

There are $n$ eigenvalues (counting degenerate eigenvalues a number of times equal to their multiplicity) below the bottom of the essential spectrum, and $\mu_n(H)$ is the $n$th eigenvalue counting multiplicity.

$\mu_n = \inf \sigma_{ess}(H)$ and in that case $\mu_n = \mu_{n+1} = \mu_{n+2} = \ldots$ and there are at most $n-1$ eigenvalues (counting multiplicities) below $\mu_n$.