Notes on Fibonacci Partitions
F.~V.~Weinstein
Let $f_1=1,f_2=2,f_3=3,f_4=5,\dots$ be the sequence of Fibonacci numbers. It is well known that for any natural $n$ there is a unique expression $n=f_{i_1}+f_{i_2}+\cdots+f_{i_q}$ such that $i_{a+1}-i_a\>2$ for $a=1,2,\dots,q-1$ (Zeckendorf Theorem). By means of it we find an explicit formula for the quantity $F_h(n)$ of partitions of $n$ with $h$ summands, all parts of them are the distinct Fibonacci numbers. This formula is used for an investigation of the functions $F(n)=\sum_{h=1}^\infty F_h(n)$ and $\chi(n)=\sum_{h=1}^\infty (-1)^hF_h(n)$. They are interpreted by means of the representations of rational numbers as some continues fractions. Using this approach we define a canonical action of monoid $\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{N}$ (see the text for the notations) on the set of natural numbers, the set orbits of that is also a monoid, freely generated by the set $\qz$, and such that $F(n)$ is invariant under this action. A fundamental domain of the action is found and the following results are established: the formula $\chi(n)=0,\pm 1$, a theorem on "Fibonacci random distribution" of $n$ with $F(n)=k$, the estimation $F(n)\<\sqrt{n+1}$, and it is shown that $\lim_{N\to\infty}(\chi^2(1)+\dots+\chi^2(N))/N=0$. In addition, an algorithm to find a minimal $n$ with $F(n)=k$ is provided.
FibSubmit.tex
%=============================================================
%%  c:\articles\Fibonacci\FibSubmit.tex
%=============================================================

\documentclass[a4paper,notitlepage,reqno,twoside]{amsart}
\usepackage{amsmath,amsfonts,amscd,verbatim,amssymb,amsthm,graphics}
\usepackage{enumerate,textcomp,mathcomp,stmaryrd,hhline,mathrsfs}
\usepackage[all]{xy}

%%% math.NT/0307150

\pagestyle{myheadings}
\textwidth 158mm
\oddsidemargin 1mm\evensidemargin 1mm

\newcounter{mycounter}

\newenvironment{enumeratei}{\begin{enumerate}[\upshape (a)]}%
                            {\end{enumerate}}

\newtheorem{tth}{Theorem}[section]
\newtheorem{ttth}{Theorem}
\newtheorem{pr}{Proposition}[section]
\newtheorem{cor}{Corollary}[section]
\newtheorem{lm}{Lemma}[section]
\newtheorem{st}{}[section]
\newtheorem{conj}{Conjecture}[section]

%%\newtheorem*{ack}{Acknowledgments} 

\theoremstyle{definition}{\newtheorem{df}{Definition}[section]}
\theoremstyle{definition}{\newtheorem{rem}{Remark}[section]}

\newcommand{\bl}[1]{\framebox[15cm]{\begin{minipage}[t]{14cm}\bigskip
\setlength{\textwidth}{10cm}
#1\bigskip\end{minipage}}\bigskip}

\renewcommand{\theequation}{\arabic{equation}}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\renewcommand{\thetth}{\thesection.\arabic{mycounter}}
\renewcommand{\thettth}{\Alph{Acounter}\arabic{mycounter}}
\renewcommand{\thepr}{\thesection.\arabic{mycounter}}
\renewcommand{\thecor}{\thesection.\arabic{mycounter}}
\renewcommand{\thelm}{\thesection.\arabic{mycounter}}
\renewcommand{\thedf}{\thesection.\arabic{mycounter}}
\renewcommand{\therem}{\thesection.\arabic{mycounter}}
\renewcommand{\thest}{\thesection.\arabic{mycounter}}
\renewcommand{\theconj}{\thesection.\arabic{mycounter}}

\def \tl{\lhd}
\def \tr{\rhd}
\def \tlq{\trianglelefteqslant}
\def \trq{\trianglerighteqslant}
\def \wg{\wedge}
\def \wP{\mathbf P}
\def \dk{\delta_k}
\def \wdw{\wedge\dots\wedge}
\def \e{\varepsilon}
\def \ml{\mathcal}
\def \>{\geqslant}
\def \<{\leqslant}
\def \gg{\succcurlyeq}
\def \ll{\preccurlyeq}
\def \l{\langle}
\def \r{\rangle}
\def \lb{\lfloor}
\def \rb{\rfloor}
\def \qz{\mathbb{Q}/\mathbb{Z}}
\def \G{\Gamma(\qz)}
\def \GG{\Gamma_G(\mathbb{Q}/\mathbb{Z})}
\def \d{\delta}
\def \D{\Delta}
\def \*{\bullet}
\def\B#1{\mathbf{#1}}
\def \en{\begin{enumerate}}
\def \ene{\end{enumerate}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{Notes on Fibonacci Partitions}

\author{F.~V.~Weinstein}

\address
{Universit\"at Bern, Anatomisches Institut,
CH-3012 Bern, B\"uhlstrasse 26, Switzerland.}

\email{Weinstein@ana.unibe.ch}
\dedicatory{To my children, Sergej and Jelena with love}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\begin{abstract}
Let $f_1=1,f_2=2,f_3=3,f_4=5,\dots$ be the sequence of
Fibonacci numbers. It is well known that for any natural $n$ there
is a unique expression $n=f_{i_1}+f_{i_2}+\cdots+f_{i_q}$ such that
$i_{a+1}-i_a\>2$ for $a=1,2,\dots,q-1$ (Zeckendorf Theorem). By means of it
we find an explicit formula for the
quantity $F_h(n)$ of partitions of $n$ with $h$ summands,
all parts of them are the distinct Fibonacci numbers.
This formula is used for an investigation of the functions $F(n)=\sum_{h=1}^\infty F_h(n)$
and $\chi(n)=\sum_{h=1}^\infty (-1)^hF_h(n)$. They are interpreted
by means of the representations of rational numbers as some continues fractions.
Using this approach we define a canonical action of monoid
$\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{N}$ (see the text for the notations) on the set of
natural numbers, the set orbits of that is also a monoid,
freely generated by the set $\qz$,
and such that $F(n)$ is invariant under this action.
A fundamental domain of the action is found and
the following results are established: the formula $\chi(n)=0,\pm 1$,
a theorem on "Fibonacci random distribution" of $n$ with $F(n)=k$, the estimation
$F(n)\<\sqrt{n+1}$, and it is shown that $\lim_{N\to\infty}(\chi^2(1)+\dots+\chi^2(N))/N=0$.
In addition, an algorithm to find a minimal $n$ with $F(n)=k$ is provided.
\end{abstract}

\maketitle
\markboth{F.V.WEINSTEIN}{NOTES ON FIBONACCI PARTITIONS}

Let $\mathbb{N}$ be the set of non negative integers and let
$f_0=f_1=1,f_i=f_{i-1}+f_{i-2},(i\>2)$ be the Fibonacci sequence.
The article concerns the representations of $n\in\mathbb{N}$ as
$n=f_{i_1}+\dots+f_{i_q}$, where $1\<i_1<\dots<i_q$.
Such representations we call the
\emph{Fibonacci partitions of $n$}.
Let $F_h(n)$ be the quantity of all such partitions of $n$ with $h$ summands.
It is obvious that
\[
\prod_{i=1}^\infty(1+tx^{f_i})=1+\sum^\infty_{n=1}\sum^\infty_{h=1}F_h(n)t^h x^n
\]
In Section \ref{secF} we establish an explicit formula for the polynomial
$F(n;t)=1+\sum_{h=1}^\infty F_h(n)t^h$.
One corollary of this result is that in the expansion
\begin{equation*}\label{0}
\prod_{i=1}^\infty (1-x^{f_i})=1+\sum^\infty_{n=1}\chi(n)x^n
\end{equation*}
all coefficients $\chi(n)$ are equal to $0,\pm 1$,
that resembles Euler's Pentagonal Theorem.

In the subsequent sections we study the functions $F(n)=F(n;1)$ and $\chi(n)=F(n;-1)$.
The contents of Section \ref{secC} points to a close relation
between them and
the representations of rational numbers as especial continued fractions.
This observation implies the following factorization of $F$.

Let $\G$ be a monoid
(i.e. a semigroup with a two-sided unit), freely generated
by the set of non-zero elements of the group $\qz$,
where $\mathbb{Q}$ and $\mathbb{Z}$ be the additive groups
of rational and integer numbers respectively.
Any non unit element of $\G$ may uniquely be represented as a word $g_1*\dots*g_s$,
where $g_1,\dots,g_s$ are the non reducible rational fractions $a/b\in(0,1)$.
Let $\mathbb{N}_*$ be a multiplicative monoid of natural numbers.
Define a homomorphism of monoids $\delta:\G\to\mathbb{N}_*$ by
$\delta(a_1/b_1*\dots*a_s/b_s)=b_1\cdots b_s$.
In Section \ref{secC} we define a surjective map of the sets
$\pi:\mathbb{N}\to\G$, that makes the diagram
\[
\xy
\xymatrix{
\mathbb{N}\ar[dr]_F\ar[r]^(.4){\pi} &\G\ar[d]^\delta\\
&\mathbb{N}_*
}
\endxy
\]
commutative. It turns to be that on $\mathbb{N}$
may canonically be defined a free action of direct product of monoids
$\mathbb{T}=\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{N}$
such that $\G$ is naturally identified with the set of
$\mathbb{T}$-orbits
(here $\mathbb{N}$ is treated as an additive monoid,
and $\mathbb{Z}_2$ is a group with two elements),
and $\pi$ is the corresponding projection. Thus
$F(n)$ is invariant under the $\mathbb{T}$-action.

For each $\gamma\in\G$
define $\theta(\gamma)\in\mathbb{N}$ to be the minimal number
in $\pi^{-1}(\gamma)$. Let $\mathcal{E}$ be the set of all such numbers.
Then $\mathcal{E}$ is a fundamental domain for $\mathbb{T}$.
The elements of $\mathcal{E}$ we call the
\emph{essential numbers}. We will be convinced that $\mathcal{E}$
is exhausted by the set of integers $\lb m\tau\rb +\lb m\tau^2\rb$,
where $\tau=(1+\sqrt{5})/2$ is the Golden Ratio, $m\in\mathbb{N}$,
and $\lb\rho\rb $ denotes the integer part (floor) of real number $\rho$.
(In this form the sequence $\mathcal{E}$ is included in \cite{SP}.)
The set of essential numbers inherits the multiplicative structure
of monoid $\G$. In Section \ref{secCEss} we give a formula
for the corresponding multiplication.

In view of the $\mathbb{T}$-action on $\mathbb{N}$, to find all $n\in\mathbb{N}$
with $F(n)=k$ it is sufficient
to find all essential $k$-numbers, i.e. those $n\in\mathcal{E}$,
for which $F(n)=k$. The quantity of essential
$k$-numbers is obviously finite. Using this, in
Section \ref{secEst} we obtain an additional information on $F(n)$.

Namely, let $\Psi(k)$ be the cardinality of the set $\delta^{-1}(k)$.
It is easy to verify (Lemma \ref{lmPsi}) that
\begin{equation}\label{400}
\Psi(k)=\sum_{1<r\<k,r|k}\Psi(k/r)\varphi(r)
\end{equation}
where $\varphi$ is the Euler's totient function and $\Psi(1)=1$.
Function $\Psi$ naturally appears in
Section \ref{secEst} as a quantitative expression
for an interesting property of ``stability'' of $F(n)$:
we prove that for $r\>2k$ the quantity of naturals
$n$ such that $f_r\<n<f_{r+1}$ and $F(n)=k$, equals to 1 for $k=1$, and to $2\Psi(k)$
for $k>1$. In particular, for $r\>2k$ this quantity
is independent from $r$.
The sequence of numbers
\[
\Psi(k)=\{1,1,2,3,4,6,6,9,10,12,10,22,12,18,24,27,16,38,18,44,\dots\}
\]
was also observed by R.~Munafo (see\cite{SP}) as the quantities
of $k$-periodic hyperbolic components on the continent of Mandelbrot set (\cite{M}).
Another result of Section \ref{secEst} is the estimation $F(n)\<\sqrt{n+1}$.

In Section \ref{secSym} we study the function $\chi(n)$.
Since $|\chi(n)|\<1$, the quantity of naturals $n\<N$ with $\chi(n)=\pm 1$
equals to $X(N)=\chi^2(1)+\chi^2(2)+\dots+\chi^2(N)$.
The main result of Section \ref{secSym} implies that
$\lim_{N\to\infty}X(N)/N=0$ although $n\in\mathbb{N}$
with $\chi(n)\neq 0$ appear often enough.
For instance, $X(f_{26})=X(196418)=46299$.

A minimal essential $k$-number is a minimal $n\in\mathbb{N}$ with $F(n)=k$.
Finding such $n$ poses an interesting question,
but seems to be difficult. In sections \ref{secCEss} and \ref{secG} we
outline an algorithm to find the minimal essential $k$-number for any $k$.

The included figure is a graphical presentation of $F(n)$,
where $n$ belongs to the interval $[0,f_{26}-1]$.
This plot hopefully helps to clarify the situation.
Few comments on it are included in Section \ref{secGraph}.
The graphic of $F(n)$ reminds some "fractal" pictures.
Probably a "fractal" behavior of the quantity of partitions
with the distinct parts, taken from the linear recurrent sequences,
is typical. In Section \ref{secGraph} we propose a related conjecture.

Two of our results were independently obtained by other people.
Namely, the inequality $|\chi(n)|\<1$ was established by G.~Payne (unpublished) and
by N.~Robbins (cf.\cite{RN}). Theorem \ref{th41} in a slightly different form
was proved by F.~Ardila (cf.\cite{AR}).

%%We are using the following notations:
We use the following notations:
$\mathbb{Z}$ and $\mathbb{Q}$ mean the additive groups
of the integer and rational numbers respectively;
$\mathbb{N}$ and $\mathbb{N}_*$ are the additive
and multiplicative monoids of non negative and positive integers respectively;
$\mathbb{Z}_2$ is a group with two elements.
The word "iff" is a synonym for "if and only if";
the abbreviation "F.p." is a synonym for "Fibonacci partition".
The notation $\#\mathcal{S}$ is used for the cardinality of the set $\mathcal{S}$.
For integer $m$ we define $\lambda(m)=0,1$ according to $m\equiv 0,1\mod2$;
$\varphi$ is the Euler totient function.
All claims on Fibonacci numbers and on the Golden Ratio $\tau=(1+\sqrt{5})/2$ we mention as
"well known" one may find in book \cite{GKP}.

%\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The quantity of Fibonacci partitions}\label{secF}
\setcounter{mycounter}{0}
In this section we introduce the main definitions and notations we use
during the article,
and establish an explicit formula for
the quantity $F_h(n)$ of Fibonacci partitions of $n$ with $h$ summands.
\stepcounter{mycounter}
\begin{df}
\noindent
\en
\item A \emph{partition} is a set of integers
$I=\{i_1,\dots,i_q\}$ such that $0<i_1\<\dots\<i_q$.
The numbers $i_1,\dots,i_q$ are called the \emph{parts} of $I$.
The partition $I$ is \emph{strict} if $i_1<\dots<i_q$.
\item The number $n=i_1+\dots+i_q$ is a \emph{content of $I=\{i_1,\dots,i_q\}$,
and $q$ is a dimension of $I$}.
\item A {\sl Fibonacci partition} is a strict partition, all parts of it are Fibonacci numbers.
\item A partition $I=\{i_1,\dots,i_q\}$ is a {\sl 2-partition} if $i_{a+1}-i_a\>2$
for $a=1,\dots,q-1$.
\item A Fibonacci partition $\{f_{i_1},\dots,f_{i_q}\}$ is
{\sl minimal} if $\{i_1,\dots,i_q\}$ is a 2-partition.
\ene
\end{df}
The following notations and conventions will be used:
\vspace{2mm}

$\mathcal{F}(n)$ is the set of Fibonacci partitions of content $n$ and $F(n)=\#\mathcal{F}(n)$.
 
$\mathcal{F}_h(n)=\{\{f_{i_1},\dots,f_{i_h}\}\in\mathcal{F}(n)\}$ for $h>0$ and $F_h(n)=\#\mathcal{F}_h(n)$.

By definition $F(0)=F_0(0)=1$ and $F_h(0)=0$ for $h>0$.

For $I=\{i_1,\dots,i_q\}$ we set $f_I=f_{i_1}+\dots+f_{i_q}$.

Often we shall write a F.p. $\{f_{i_1},\dots,f_{i_q}\}$ of content $n$
as $n=f_{i_1}+\dots+f_{i_q}$.
\vspace{2mm}

\emph{For any $n\in\mathbb{N}$ there exists a unique minimal F.p.}
$n=f_{\mu_1(n)}+\dots+f_{\mu_q(n)}$.
This simple observation is a content of \emph{Zeckendorf's Theorem}.
It implies that the correspondence
\[
n\to Z(n)=\{\mu_1(n),\dots,\mu_q(n)\}
\]
defines a canonical bijection $Z:\mathbb{N}\to\mathcal{P}_2$.
Sometimes we use the notations $\mu_\infty(n)=\mu_q(n)$ and
$\mu_{\infty-a}(n)=\mu_{q-a}(n)$. By definition $\mu_\infty(0)=0$.

The main aim of this section is an explicit expression for
$F(n;t)=1+\sum_{h=1}^\infty F_h(n)t^h$
by means of the 2-partition $Z(n)$ (Theorem \ref{th1}).
To formulate the result we need few more definitions.
\stepcounter{mycounter}
\begin{df}
Let $I=\{i_1,\dots,i_q\}$ be a 2-partition.
\noindent
\en
\item $I$ is {\sl simple} if $\lambda(i_1)=\dots=\lambda(i_q)$.
\item A {\sl canonical form of $I$} is a (unique) representation $I=(I_1;\dots;I_s)$, where
$I_1,\dots,I_s$ are the simple 2-partitions such that $I=I_1\bigcup\cdots\bigcup I_s$ and
$\min(I_{a+1})-\max(I_a)$ is an odd positive number for each $a=1,\dots,s-1$.
\item 2-partitions $I_1,\dots,I_s$ are the {\sl simple components of} $I$.
\ene
\end{df}
\stepcounter{mycounter}
\begin{df}
Let $I=\{i_1,\dots,i_q\}$ be a 2-partition.
\noindent
\en
\item Define $\alpha(I)=(\alpha_1,\dots,\alpha_q)\in\mathbb{N}^q$ by
\begin{equation*}
\alpha_r=
\begin{cases}
\lb \frac{i_1-1}{2}\rb +1        & \text{if $\;r=1$}\\
\lb  \frac{i_r-i_{r-1}}{2}\rb +1 & \text{if $\;r>1$}
\end{cases}
\end{equation*}
Vector $\alpha(I)$ is the {\sl associated vector of} $I$.
\item Let $I=(I_1;\dots;I_s)$ be a canonical form of $I$,
and $\alpha(I)=(\alpha_1,\dots,\alpha_q)$.
Set $d_0=0,d_m=\dim(I_1)+\dots+\dim(I_m)$ and
$A_m(I)=(\alpha_{d_{m-1}+1},\alpha_{d_{m-1}+2},\dots,\alpha_{d_m})$.
Define
\[
\mathcal{A}_m=\bigcup_{q=1}^\infty\{(\alpha_1,\alpha_2,\dots,\alpha_q)\in\mathbb{N}^q\;:\;
\alpha_1\>m,\alpha_2\>2,\dots,\alpha_q\>2\}
\]
An \emph{associated multivector} of $I$ is
$\mathcal{V}(I)=A_1(I)\times A_2(I)\times\dots\times A_s(I)\in
\mathcal{A}_1\times\mathcal{A}_2^{\times(s-1)}$.
We set $\mathcal{A}=\bigcup_{s=1}^\infty\mathcal{A}_1\times\mathcal{A}_2^{\times(s-1)}$.
Thus $\mathcal{V}:\mathcal{P}_2\to\mathcal{A}$ is a surjective map.
\ene
\end{df}

Define $\D_0(\emptyset;\emptyset)=1, \D_1(x_1;\emptyset)=x_1$ and
\[
\D_q(x_1,x_2,\dots,x_q;y_1,y_2,\dots,y_{q-1})=
\begin{vmatrix}
\;x_1 & y_1 & 0 & 0 & \hdots & 0 \\
\;1 & x_2 & y_2 & 0 & \hdots & 0 \\
\;\vdots & \vdots & & \ddots & &\vdots \\
\;0 & 0 & \hdots & 1 &x_{q-1} & y_{q-1} \\
\;0 & 0 & \hdots & 0 & 1 &x_q
\end{vmatrix}
\]
for $q\>2$. Now
for $A=(\alpha_1,\alpha_2,\dots,\alpha_q)\in\mathbb{N}^q$ let
\begin{equation*}
D(A;t)=\D_q(\phi_{\alpha_1}(t),\phi_{\alpha_2}(t),\dots,\phi_{\alpha_q}(t);
\ t^{\alpha_2+1},\dots,t^{\alpha_q+1})
\end{equation*}
where $\phi_\alpha(t)=t+t^2+\dots+t^\alpha$ for $\alpha\in\mathbb{N}$.
Thus polynomial $D(A;t)$ may be defined by the recurrence
\begin{equation}\label{eqRec}
D(\alpha_1,\dots,\alpha_r;t)=\phi_{\alpha_r}(t)
D(\alpha_1,\dots,\alpha_{r-1};t)-
t^{\alpha_r+1}D(\alpha_1,\dots,\alpha_{r-2};t)
\end{equation}
starting with $D(\emptyset;t)=1, D(\alpha_1;t)=\phi_{\alpha_1}(t)$.
\stepcounter{mycounter}
\begin{tth}\label{th1}
Let $n\in\mathbb{N}$ and let $\mathcal{V}(Z(n))=A_1\times\cdots\times A_s$. Then
$F(n;t)=D(A_1;t)\cdots D(A_s;t)$.
\end{tth}
Our proof is divided into several lemmas.
\stepcounter{mycounter}
\begin{lm}\label{pr1}
Let $n=f_{\mu_1(n)}+\dots+f_{\mu_q(n)}$. Then
\begin{enumerate}[\rm(a)]
\item The greatest part of each F.p. of content $n$
equals to either $f_{\mu_q(n)}$ or to $f_{\mu_q(n)-1}$. \label{La}
\item Each F.p. of content $f_r$ is of a form
$f_{r-2k}+f_{r-(2k-1)}+f_{r-(2k-3)}+\dots+f_{r-3}+f_{r-1}$,
where $k=0,1,\dots,\lb \frac{r-1}{2}\rb $.
In particular $F(f_r,t)=\phi_{\lb \frac{r-1}{2}\rb +1}(t)$.
\item $\mathrm{(Rigidity\ of\ F.p's.)\;}$
Let $n=f_{a_1}+\dots+f_{a_h}$ be a F.p. Then for each $m,1\<m\<q$ there exists $s,1\<s\<h$
such that $f_{a_1}+\dots+f_{a_s}=f_{\mu_1(n)}+\dots+f_{\mu_m(n)}$. If $m<q$, then $f_{a_{s+1}}\>f_{\mu_m(n)}$.
\end{enumerate}
\end{lm}
\begin{proof}
To prove (a) let us assume that $n=f_{a_1}+\dots+f_{a_s}$ and $f_{a_s}<f_{\mu_q(n)-1}$.
Then $n=f_{a_1}+\dots+f_{a_s}\<f_1+f_2+\dots+f_{\mu_q(n)-2}=f_{\mu_q(n)}-2<n$ what is not possible.
Heading (b) follows from (a) by induction on $r$.

The proof of (c) is by induction on $n$.
It is sufficient to find $s$ such that $f_{a_{s+1}}+\dots+f_{a_h}=f_{\mu_q(n)}$.
Indeed, then the first claim of (c) is implied by the same one
for the F.p. $n_1=f_{a_1}+\dots+f_{a_s}<n$ and with minimal F.p. $n_1=f_{\mu_1(n)}+\dots+f_{\mu_{q-1}(n)}$.
Since either $a_s=\mu_{q-1}(n)$ or $a_s=\mu_{q-1}(n)-1$,
we obtain that $f_{a_{s+1}}\>f_{\mu_{q-1}(n)}$. That proves the second claim of (c).

Again, by (a) either $a_h=\mu_q(n)$ or $a_h=\mu_q(n)-1$. For $a_h=\mu_q(n)$k, there is nothing to prove.
Let $a_h=\mu_q(n)-1$ and $n_1=n-f_{a_h}=f_{\mu_1(n)}+\dots+f_{\mu_{q-1}(n)}+f_{\mu_q(n)-2}$.
If $(\mu_q(n)-2)-\mu_{q-1}(n)\>2$, then the last expression is a minimal F.p. for $n_1$.
Since $n_1<n$, by the inductive assumption there is $s$ such that
$f_{a_{s+1}}+f_{a_{s+2}}+\dots+f_{a_{h-1}}=f_{\mu_q(n)-2}$.
But then $f_{a_{s+1}}+f_{a_{s+2}}+\dots+f_{a_{h-1}}+f_{a_h}=f_{\mu_q(n)}$, and (c) follows.

For $(\mu_q(n)-2)-\mu_{q-1}(n)<2$ it is sufficient to verify that $f_{a_{h-1}}=f_{\mu_q(n)-2}$, since
then $f_{a_{h-1}}+f_{a_h}=f_{\mu_q(n)-2}+f_{\mu_q(n)-1}=f_{\mu_q(n)}$.
Contrary, assume that $f_{a_{h-1}}\<f_{\mu_q(n)-3}$. Then
$n=f_{a_1}+f_{a_2}+\dots+f_{a_{h-1}}+f_{\mu_q(n)-1}\<f_1+f_2+\dots+f_{\mu_q(n)-3}+f_{\mu_q(n)-1}=2f_{\mu_q(n)-1}-2$.
Since in the considered case $\mu_{q-1}(n)\>\mu_q(n)-3$, from the minimal F.p. for $n$ we obtain
$n\>f_{\mu_q(n)-3}+f_{\mu_q(n)}=2f_{\mu_q(n)-1}$, that is a contradiction.
\end{proof}
Let $\mathcal{F}_{k,h}(n)=\{\{f_{a_1},\dots,f_{a_h}\}\in\mathcal{F}_h(n):a_1>k\}$,
and let $F_{k,h}(n)=\#\mathcal{F}_{k,h}(n)$.
\stepcounter{mycounter}
\begin{lm}\label{pr0}
Assume that $\mu_1(n)>k$. Then
$F_{k,h}(n)=F_h(f_{\mu_1(n)-k}+\dots+f_{\mu_q(n)-k})$.
\end{lm}
\begin{proof}
For $\{f_{a_1},\dots,f_{a_h}\}\in\mathcal{F}_{k,h}(n)$ define
$\lambda_k(\{f_{a_1},\dots,f_{a_h}\})=\{f_{a_1-k},\dots,f_{a_h-k}\,\}$.
We claim that
$\lambda_k(\{f_{a_1},\dots,f_{a_h}\})\in\mathcal{F}_h(f_{\mu_1(n)-k}+\dots+f_{\mu_q(n)-k})$.
The proof is by induction on $q$.
For $q=1$ it follows from Lemma \ref{pr1}(b). Let $q>1$.
We can find $s>1$
such that $f_{a_1}+\dots+f_{a_s}=f_{\mu_1(n)}+\dots+f_{\mu_{q-1}(n)}$ (Lemma \ref{pr1}(c)).
By the inductive assumption
$f_{a_1-k}+\dots+f_{a_s-k}=f_{\mu_1(n)-k}+\dots+f_{\mu_{q-1}(n)-k}$,
$f_{a_{s+1}-k}+\dots+f_{a_h-k}=f_{\mu_q(n)-k}$, and our claim follows.
Thus the map $\lambda_k:\mathcal{F}_{k,h}(n)\to
\mathcal{F}_h(f_{\mu_1(n)-k}+\dots+f_{\mu_q(n)-k})$ is well defined. Then it is obviously bijective.
\end{proof}
\stepcounter{mycounter}
\begin{lm}\label{pr2}
Let $\{i_1,\dots,i_x,j_1,\dots,j_y\}\in\mathcal{P}_2,(x,y>0)$ and $\alpha=\lb \frac{j_1-i_x}{2}\rb +1$. Then
\begin{multline*}
F(f_{i_1}+\dots+f_{i_x}+f_{j_1}+\dots+f_{j_y},t)=\\
\begin{cases}
F(f_{i_1}+\dots+f_{i_x},t)F(f_{j_1-i_x}+\dots+f_{j_y-i_x},t)
&\text{\rm if $\lambda(j_1)\neq\lambda(i_x)$}\\
F(f_{i_1}+\dots+f_{i_x},t)F(f_{j_1-i_x+1}+\dots+f_{j_y-i_x+1},t)-
&\text{ }\\
\qquad t^{\alpha+1} F(f_{i_1}+\dots+f_{i_{x-1}},t)
F(f_{j_2-j_1+1}+\dots+f_{j_y-j_1+1},t)
&\text{\rm if $\lambda(j_1)=\lambda(i_x)$}
\end{cases}
\end{multline*}
\end{lm}
\begin{proof}
Let $f_{i_1}+\dots+f_{i_x}=n_1,f_{j_1}+\dots+f_{j_y}=n_2$ and
$F_h^{(m)}(n)=\#\{\{f_{a_1},\dots,f_{a_h}\}\in\mathcal{F}_h(n):a_h=m\}$.
Thanks to Lemma \ref{pr1}(c,a) each F.p. from $\mathcal{F}_h(n_1+n_2)$ is of a form
$\{f_{a_1},\dots,f_{a_s},f_{a_{s+1}},\dots,f_{a_h}\}$,
where $f_{a_1}+\dots+f_{a_s}=n_1$ and either $a_s=i_x-1$ or $a_s=i_x$.
Therefore
\begin{equation}
\label{4}
F_h(n_1+n_2)=\sum_{s=1}^h \big(F_s^{(i_x-1)}(n_1) F_{i_x-1,h-s}(n_2)+
F_s^{(i_x)}(n_1) F_{i_x,h-s}(n_2)\big)
\end{equation}
Again by Lemma \ref{pr1}(c) there is $s_1\>s+1$ such that
$f_{a_{s+1}}+\dots+f_{a_{s_1}}=f_{j_1}$.
Then Lemma \ref{pr1}(b) implies that $\lambda(a_{s+1})=\lambda(j_1)$.
In addition we know that $a_{s+1}\>i_x$ (Lemma \ref{pr1}(c)).
If $\lambda(j_1)\neq\lambda(i_x)$
then $a_{s+1}>i_x$. Thus $F_{i_x-1,h-s}(n_2)=F_{i_x,h-s}(n_2)$.
Since $F_s(n_1)=F_s^{(i_x-1)}(n_1)+F_s^{(i_x)}(n_1)$,
we may rewrite formula \eqref{4} as
\[
F_h(n_1+n_2)=\sum_{s=1}^h F_s(n_1) F_{i_x,h-s}(n_2)
\]
Applying Lemma \ref{pr0} to $F_{i_x,h-s}(n_2)$ completes
the proof in case $\lambda(j_1)\neq\lambda(i_x)$.

Now let $\lambda(j_1)=\lambda(i_x)$. From Lemma \ref{pr1}(b,c) it follows that
each F.p. from $\mathcal{F}_{i_x-1,h-s}(n_2)$ with the minimal part $f_{i_x}$
is of a form $\{f_{i_x},f_{i_x+1},f_{i_x+3},\dots,f_{j_1-1},f_{l_1},\dots,f_{h-s-\alpha}\}$,
where $\alpha=\lb \frac{j_1-i_x}{2}\rb +1$.
Therefore
$F_{i_x,h-s}(n_2)=F_{i_x-1,h-s}(n_2)-F_{j_1-1,h-s-\alpha}(n_2-f_{j_1})$.
After substitution this expression in formula \eqref{4} and recall that
$F_s(n_1)=F_s^{(i_x-1)}(n_1)+F_s^{(i_x)}(n_1)$ and
$F_s^{(i_x)}(n_1)=F_{s-1}(n_1-f_{i_x})$, we obtain
\[
F_h(n_1+n_2)=\sum_{s=1}^h F_s(n_1) F_{i_x-1,h-s}(n_2)-
\sum_{s=1}^h F_{s-1}(n_1-f_{i_x}) F_{j_1-1,h-s-\alpha}(n_2-f_{j_1})
\]
Applying Lemma \ref{pr0} to $F_{i_x-1,h-s}(n_2)$ and
to $F_{j_1-1,h-s-\alpha}(n_2-f_{j_1})$ completes the proof.
\end{proof}
\begin{proof}[Proof of Theorem \ref{th1}]
Let $Z(n)=\{i_1,\dots,i_q\}$ be a simple 2-partition and
$\mathcal{V}(Z(n))=(\alpha_1,\dots,\alpha_q)$.
From the second case of Lemma \ref{pr2} formula, we obtain a recurrence
\[
F(n;t)=F(n-f_{i_q},t) F(f_{i_q-i_{q-1}},t)-
t^{\alpha_q+1} F(n-f_{i_{q-2}}-f_{i_{q-1}},t)
\]
where $F(f_{i_q-i_{q-1}})=\phi_{\alpha_q}(t)$ by Lemma \ref{pr1}(b).
The induction on $q$ shows that $F(n;t)$ depends only on vector
$\mathcal{V}(Z(n))$. Therefore, there exists a function
$D^\prime(\alpha_1,\alpha_2,\dots,\alpha_q;t)=F(n;t)$ and for $r\>2$
\begin{equation*}
D^\prime(\alpha_1,\dots,\alpha_r;t)=\phi_{\alpha_r}(t)
D^\prime(\alpha_1,\dots,\alpha_{r-1};t)-
t^{\alpha_r+1}D^\prime(\alpha_1,\dots,\alpha_{r-2};t)
\end{equation*}
In addition $D^\prime(\emptyset;t)=1, D^\prime(\alpha_1;t)=\phi_{\alpha_1}(t)$.
Therefore recurrence \eqref{eqRec} implies that $D^\prime(A;t)=D(A;t)$.
Now Theorem \ref{th1} follows from the first case of Lemma \ref{pr2} formula.
\end{proof}
\stepcounter{mycounter}
\begin{cor}\label{cor1}
\begin{enumerate}[\rm(a)]
\item For $n\in\mathbb{N}$ let $\chi(n)=F(n;-1)$. Then $\chi(n)=0,\pm 1$.
\item Let $(\alpha_1,\dots,\alpha_r)\in\mathcal{A}_1$.
Then $D(\alpha_1,\dots,\alpha_r;-1)=0$ iff $\lambda(D(\alpha_1,\dots,\alpha_r;1))=0$.
\end{enumerate}
\end{cor}
\begin{proof}
Thanks to Theorem \ref{th1} it is sufficient to verify that $D(A;-1)=0,\pm 1$
for arbitrary integer vector $A=(\alpha_1,\dots,\alpha_q)$.
This is obvious for $q=0,1$ and for $q=2,3$ can easily be verified.
The recurrence \eqref{eqRec} implies that
\begin{equation}\label{11}
D(\alpha_1,\dots,\alpha_q;-1)=
\begin{cases}
D(\alpha_1,\dots,\alpha_{q-3},\alpha_{q-2};-1) & \text{if $\lambda(\alpha_q)=0$}\\
D(\alpha_1,\dots,\alpha_{q-4},\alpha_{q-3};-1) & \text{if $\lambda(\alpha_q)=1$
\;and\; $\lambda(\alpha_{q-1})=1$}\\
D(\alpha_1,\dots,\alpha_{q-2},\alpha_{q-1}+1;-1) & \text{if $\lambda(\alpha_q)=1$
\;and\; $\lambda(\alpha_{q-1})=0$}
\end{cases}
\end{equation}
The induction on $q$ completes the proof of (a).

Obviously $\lambda(F(n))=\lambda(\chi(n))$.
Since $\mathcal{V}:\mathcal{P}_2\to\mathcal{A}$ is a surjective map,
there exists $n\in\mathbb{N}$ such that $D(\alpha_1,\dots,\alpha_r;1)=F(n)$
and $D(\alpha_1,\dots,\alpha_r;-1)=\chi(n)$. Therefore (b) follows from (a).

\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Continued fraction interpretation of $\chi(n)$ and $F(n)$}\label{secC}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setcounter{mycounter}{0}
Theorem \ref{th1}, in particular, gives the explicit expressions for the
functions $F(n)=F(n;1)$ and $\chi(n)=F(n;-1)$. These expressions
might quite naturally be interpreted
by means of the presentations of rational numbers as some continued fractions.

Namely, for $A=(\alpha_1,\dots,\alpha_q)\in \mathcal{A}_1$
define a rational function $\l A;t\r$ on $t$ by
\[
\l A;t\r=\l\alpha_1,\dots,\alpha_q;t\r=
\frac{1}{\phi_{\alpha_1}(t)-}\;\frac{t^{\alpha_2+1}}{\phi_{\alpha_2}(t)-}\;
\dots\;\frac{t^{\alpha_q+1}}{\phi_{\alpha_q}(t)}=
\frac{D(\alpha_2,\dots,\alpha_q;t)}{D(\alpha_1,\dots,\alpha_q;t)}
\]
\stepcounter{mycounter}
\begin{lm}\label{lmGCD}
For $A=(\alpha_1,\dots,\alpha_q)\in\mathcal{A}_1$ there exists
a polynomial $d(A;t)$ such that
$D(A;t)=t^qd(A;t)$ and $d(A;0)\neq 0$.
A greatest common divisor of the polynomials
$D(\alpha_1,\dots,\alpha_q;t)$ and
$D(\alpha_2,\dots,\alpha_q;t)$ in $\mathbb{Z}[t]$
equals to $t^{q-1}$.
\end{lm}
\begin{proof}
For $q=1$ lemma is obvious.
For $q>1$ it follows by induction on $q$. Really, using the
inductive assumption we obtain a recurrence
\[
D(\alpha_1,\dots,\alpha_q;t)=
t^q\big((1+t+\dots+t^{\alpha_1-1})d(\alpha_2,\dots,\alpha_q;t)-
t^{\alpha_2-1}d(\alpha_3,\dots,\alpha_q;t)\big)=
t^qd(\alpha_1,\dots,\alpha_q;t)
\]
where the polynomials $d(\alpha_2,\dots,\alpha_q;t)$
and $d(\alpha_3,\dots,\alpha_q;t)$ are relatively prime.
Now the first claim follows because the inequality $\alpha_2-1\>1$
implies that $d(\alpha_1,\dots,\alpha_q;0)=d(\alpha_2,\dots,\alpha_q;0)\neq 0$.
The second claim follows as well, since if we assume that there exists
a common root for $d(\alpha_1,\dots,\alpha_q;t)$
and $d(\alpha_2,\dots,\alpha_q;t)$, then it is also a root
for $d(\alpha_3,\dots,\alpha_q;t)$ as
the above recurrence shows.
But relatively prime polynomials $d(\alpha_2,\dots,\alpha_q;t)$
and $d(\alpha_3,\dots,\alpha_q;t)$ can not have common roots.
\end{proof}
For $A\in \mathcal{A}_1$ set for brevity $D(A)=D(A;1)$
and $\l A\r=\l A;1\r$.
\stepcounter{mycounter}
\begin{lm}\label{lm30}
\begin{enumerate}[\rm(a)]
\item Let $(\alpha_1,\dots,\alpha_q)\in \mathcal{A}_1$. Then
the rightmost side of expression
\begin{equation}\label{eqFr}
\l\alpha_1,\dots,\alpha_q\r=
\frac{1}{\alpha_1-}\;\frac{1}{\alpha_2-}\;\dots\;\frac{1}{\alpha_q}=
\frac{D(\alpha_2,\dots,\alpha_q)}{D(\alpha_1,\alpha_2,\dots,\alpha_q)}
\end{equation}
is a non reducible positive rational fraction.
\item For any rational $g>0$ there exists a unique $c(g)\in\mathcal{A}_1$
such that $g=\l c(g)\r$. In other words if $\l A\r=g, (A\in\mathcal{A}_1)$, then $A=c(g)$.
\item In this correspondence $c(g)\in\mathcal{A}_2$ iff $g<1$.
\end{enumerate}
\end{lm}
\begin{proof}
For $A\in \mathcal{A}_1$ there exists $n\in\mathbb{N}$
such that $\mathcal{V}(Z(n))=A$.
Theorem \ref{th1} implies that $D(A)=F(n)>0$. Therefore
$\l\alpha_1,\dots,\alpha_q\r>0$.
The non reducibility follows from Lemma \ref{lmGCD} when $t=1$.

For a rational fraction $g=a/b>0$ the coordinates
of vector $c(g)$ may be found by the recurrence
\begin{equation*}
\alpha_i =\lceil b_i/a_i\rceil\;\;\;\;\text{if\; $a_i\neq 0$},\qquad
a_{i+1}=a_i\alpha_i-b_i,\qquad
b_{i+1}\;=a_i
\end{equation*}
starting with $a_1=a,b_1=b$, where $\lceil\rho\rceil$
denotes the ceiling of real number $\rho$.
The recursion terminates when $a_{i+1}=0$.
The proof of uniqueness is omitted, because
it repeats the standard arguments from \cite{HW} (Ch.X)
in a similar situation.
\end{proof}
For instance, for integer $k>0$ we have $c(k)=\l 1,2,\dots,2\r$ and
$c((k-1)/k)=\l 2,2,\dots,2\r$, where $2$ repeats $k-1$ times in each case.
\stepcounter{mycounter}
\begin{tth}
For relatively prime non zero integers $a,b$ define
$\widetilde{\chi}(a/b)=\lambda(b)(1-2\lambda(a))$. Let
$\mathcal{V}(Z(n))=A_1\times\cdots\times A_s$. Then
$\chi(n)=\widetilde{\chi}(\l A_1\r)\dots\widetilde{\chi}(\l A_s\r)$.
\end{tth}
\begin{proof}
In view of Theorem \ref{th1} it is sufficient to
establish the claim only for $s=1$. Let
$\mathcal{V}(Z(n))=A=(\alpha_1,\alpha_2,\dots,\alpha_q)$.
Then $\l A\r=D(\alpha_2,\dots,\alpha_q)/D(\alpha_1,\alpha_2,\dots,\alpha_q)$.
The proof is by induction on $q$.

From Corollary \ref{cor1}(b), we know that if
$\lambda(F(n))=\lambda(D(\alpha_1,\alpha_2,\dots,\alpha_q))=0$, then
$\chi(n)=0=\widetilde{\chi}(\l A\r)$.
Thus we may assume that $\lambda(D(\alpha_1,\alpha_2,\dots,\alpha_q))=1$.
It remains to show that then
\[
D(\alpha_1,\alpha_2,\dots,\alpha_q;-1)=
\begin{cases}
1 &\text{if}\quad \lambda(D(\alpha_2,\dots,\alpha_q))=0\\
-1 &\text{if}\quad \lambda(D(\alpha_2,\dots,\alpha_q))=1
\end{cases}
\]
For $q=1,2$ this is clear. Let $q>2$. The following recurrences
follow from the definition of $D$:
\begin{gather}
D(\alpha_1,\dots,\alpha_q)=
\alpha_1D(\alpha_2,\dots,\alpha_q)-
D(\alpha_3,\dots,\alpha_q)\label{r1}\\
D(\alpha_2,\dots,\alpha_q)=
\alpha_2D(\alpha_3,\dots,\alpha_q)-
D(\alpha_4,\dots,\alpha_q)\label{r2}\\
D(\alpha_1,\dots,\alpha_q;-1)=
-\lambda(\alpha_1)D(\alpha_2,\dots,\alpha_q;-1)+
(1-2\lambda(\alpha_2))D(\alpha_3,\dots,\alpha_q;-1)\label{r3}
\end{gather}
In \eqref{r3} we used that $\phi_\alpha(-1)=-\lambda(\alpha)$ and
$(-1)^{\alpha+1}=2\lambda(\alpha)-1$.

If $\lambda(D(\alpha_2,\dots,\alpha_q))=0$
then $D(\alpha_2,\dots,\alpha_q;-1)=0$ by Corollary \ref{cor1}(b).
Then \eqref{r1} implies that $\lambda(D(\alpha_3,\dots,\alpha_q))=1$.
But then from \eqref{r2} it follows that
$\lambda(D(\alpha_4,\dots,\alpha_q))=\lambda(\alpha_2)$.
Therefore the inductive assumption shows that
$D(\alpha_3,\dots,\alpha_q;-1)=1-2\lambda(\alpha_2)$.
Now from \eqref{r2} we obtain
$D(\alpha_1,\dots,\alpha_q;-1)=(1-2\lambda(\alpha_2))^2=1$
as claimed.

Let now $\lambda(D(\alpha_2,\dots,\alpha_q))=1$. By induction
$D(\alpha_2,\dots,\alpha_q;-1)=\pm 1$,
depending on $\lambda(D(\alpha_3,\dots,\alpha_q))=0,1$.
If $\lambda(D(\alpha_3,\dots,\alpha_q))=0$, then
$D(\alpha_3,\dots,\alpha_q;-1)=0$ by Corollary \ref{cor1}(b).
In addition \eqref{r1} shows that $\lambda(\alpha_1)=1$.
Now from \eqref{r3} it follows that $D(\alpha_1,\dots,\alpha_q;-1)=-1$ as claimed.

Finally, let $\lambda(D(\alpha_3,\dots,\alpha_q))=1$.
Then \eqref{r1} shows that $\lambda(\alpha_1)=0$.
From \eqref{r2} it follows that $\lambda(\alpha_2)+\lambda(D(\alpha_4,\dots,\alpha_q))=1$.
If $\lambda(\alpha_2)=0$, then $\lambda(D(\alpha_4,\dots,\alpha_q))=1$,
and by the inductive assumption $D(\alpha_3,\dots,\alpha_q;-1)=-1$.
Similarly for $\lambda(\alpha_2)=1$ we obtain $D(\alpha_3,\dots,\alpha_q;-1)=1$.
In both cases from \eqref{r3} it follows that $D(\alpha_1,\dots,\alpha_q;-1)=-1$.
The proof is completed. 
\end{proof}
Function $F(n)$ may also be interpreted by means of continued fractions.
Namely, consider a monoid $\G$, freely generated
by the set $\qz$.
By definition $1$ is a two sided unit of $\G$.
The non unit elements of $\G$ we identify
with the words $\gamma=g_1*\dots*g_s,(s>0)$,
where each $g_i$ is a non reducible fraction $a/b\in(0,1)$
of positive integers. For $s=0$ by definition $\gamma=1$.

Let $\mathcal{A}^{(s)}=\mathcal{A}_1\times \mathcal{A}_2^{\times(s-1)}$,
$\mathcal{A}=\bigcup_{s=1}^\infty \mathcal{A}^{(s)}$, and
let $p:\mathcal{A}\to\G$ be a map, defined on
$A=A_1\times A_2\times\dots\times A_s\in \mathcal{A}^{(s)}$ by
\[
p(A)=\big(\l A_1\r-\lb \l A_1\r\rb \big)*\l A_2\r*\dots*\l A_s\r
\]
Lemma \ref{lm30} implies that $p$ is surjective.

%%Let $\mathbb{N}_*$ be a multiplicative monoid of natural numbers.
Define a homomorphism of monoids $\delta:\G\to\mathbb{N}_*$ by the formulas
$\delta(1)=1,\delta(a_1/b_1*\dots*a_s/b_s)=b_1\cdots b_s$.
Theorem \ref{th1} says that $F(n)=D(A_1)\dots D(A_s)$,
where $A_1\times\dots\times A_s=\mathcal{V}(Z(n))$.
Therefore \eqref{eqFr} shows that the diagram
\begin{equation*}\label{Diag}
\xy
\xymatrix{
\mathbb{N}\ar[drrr]_F\ar[r]^-{Z} &\mathcal{P}_2 \ar[r]^-{\mathcal{V}}
&\mathcal{A}\ar[dr]^D\ar[r]^-{p} &\G \ar[d]^\delta\\
&&&\mathbb{N}_*
}
\endxy
\end{equation*}
is  commutative.
Our next aim is to show that on the fibers of map $p\cdot\mathcal{V}$
there exists a canonically defined algebraic structure.

Consider the maps $\mathbb{N}^q\to\mathbb{N}^{q+1},(q\>0)$, defined by
$\emptyset\to(1)$ for $q=0$ and by
$(\alpha_1,\alpha_2,\dots,\alpha_q)\to(1,\alpha_1+1,\alpha_2,\dots,\alpha_q)$
for $q>0$.
These maps induce a map $S_\mathcal{A}:\mathcal{A}\to\mathcal{A}$.
Let $S_\mathcal{A}^0=\mathrm{id}_\mathcal{A}$,
and let $S_\mathcal{A}^r$ be the $r$-th iteration of $S_\mathcal{A}$.
It is easy to check that
for $(\alpha_1,\dots,\alpha_q)\in\mathcal{A}_1$ and $r>0$
\begin{equation*}\label{eqD}
\l S_\mathcal{A}^r(\alpha_1,\dots,\alpha_q);t\r=\frac{t^r-1}{t(t-1)}+
t^{\alpha_1+r-1}\l\alpha_1,\dots,\alpha_q;t\r
\end{equation*}
For $t=1$ and $g\in\qz$ this formula implies that
$\l S_\mathcal{A}^r(c(g))\r=r+\l c(g)\r=r+g$.

Let $A\in\mathcal{A}$ and let $p(A)=g$.
Then either $A=A_1$ or $A=A_1\times A_2$.
If $A=A_1$, then $\l A_1\r=\lb\l A_1\r\rb+g$.
Lemma \ref{lm30}(b) implies that then
$A=S_\mathcal{A}^r(c(g))$, where $r=\lb\l A_1\r\rb$.
If $A=A_1\times A_2$, then $\l A_1\r=\lb\l A_1\r\rb=r$
and $A_2=c(g)$. Again, Lemma \ref{lm30}(b) shows that $A_1=S_\mathcal{A}^r((1))$.

These arguments imply that for $\gamma=g_1*\dots*g_s\in\G$
the set $p^{-1}(\gamma)$ is exhausted by the multivectors
$S_\mathcal{A}^r\big(c(\gamma)\big)$ and
$S_\mathcal{A}^r\big((1)\times c(\gamma)\big)$, where
$c(\gamma)=c(g_1)\times\cdots\times c(g_s)$,
and $r$ runs over $\mathbb{N}$.
Moreover, for each $A\in\mathcal{A}$ there exist
a uniquely defined $\gamma\in\G$ and $r\in\mathbb{N}$
such that either $A=S_\mathcal{A}^r\big(c(\gamma)\big)$, or
$A=S_\mathcal{A}^r\big((1)\times c(\gamma)\big)$.

Therefore the formulas
$\tau_\mathcal{A}(S_\mathcal{A}^r\big(c(\gamma)\big))=
S_\mathcal{A}^r\big((1)\times c(\gamma)\big)$
and $\tau_\mathcal{A}\big(S_\mathcal{A}^r((1)\times c(\gamma))\big)=
S_\mathcal{A}^r\big(c(\gamma)\big)$ define an involution
$\tau_\mathcal{A}:\mathcal{A}\to\mathcal{A}$.
Since $\tau_\mathcal{A}$ commutes with $S_\mathcal{A}$,
monoid $\mathbb{T}_\mathcal{A}$, generated by the set of maps
$\{\tau_\mathcal{A},S_\mathcal{A}^0,S_\mathcal{A}^1,S_\mathcal{A}^2,\dots\}
:\mathcal{A}\to\mathcal{A}$,
is isomorphic to a direct product of monoids
$\mathbb{Z}_2\times\mathbb{N}$.

Each orbit of the action of $\mathbb{T}_\mathcal{A}$ on $\mathcal{A}$
coincides with $p^{-1}(\gamma)$ for a uniquely defined $\gamma\in\G$.
Therefore the set of orbits may canonically be identified with $\G$.
In addition it follows that the action of $\mathbb{T}_\mathcal{A}$
on $\mathcal{A}$ is free (i.e. without fixed points).

The fibers of $\mathcal{V}$ obviously coincide with the orbits of involution
$\omega:\mathcal{P}_2\to\mathcal{P}_2$, defined by
\begin{equation}\label{defW}
\omega\{i_1,\dots,i_q\}=
\begin{cases}
\{i_1+1,\dots,i_q+1\}&\text{if\quad $\lambda(i_1)=1$}\\
\{i_1-1,\dots,i_q-1\}&\text{if\quad $\lambda(i_1)=0$}
\end{cases}
\end{equation}
It is possible to raise up the maps
$S_\mathcal{A},\tau_\mathcal{A}:\mathcal{A}\to\mathcal{A}$
to the maps $S,\tau:\mathcal{P}_2\to\mathcal{P}_2$ such that
\begin{equation}\label{eqcond}
\mathcal{V}\cdot S=S_\mathcal{A}\cdot\mathcal{V},\quad
\mathcal{V}\cdot\tau=\tau_\mathcal{A}\cdot\mathcal{V},\quad
\tau^2=\mathrm{id}_{\mathcal{P}_2},\quad
\omega\cdot S=S\cdot\omega,\quad
\omega\cdot\tau=\tau\cdot\omega,\quad
\tau\cdot S=S\cdot\tau
\end{equation}
First define $S$ by
\begin{equation}\label{defS}
S\{i_1,\dots,i_q\}=\{2-\lambda(i_1),i_1+2,\dots,i_q+2\}
\end{equation}
To define $\tau$, notice that the above description of $p^{-1}(\gamma)$
implies that for any $I\in\mathcal{P}_2$ there exist a uniquely defined
$I^\prime\in\mathcal{P}_2$ and $r\in\mathbb{N}$ such that
$I=S^r(I^\prime)$ and $I^\prime$ is one of the following $2$-partitions:
either $\{i_1,\dots,i_q\}$ or $\{1,i_1,\dots,i_q\}$ and $\lambda(i_1)=0$,
or $\{2,i_1,\dots,i_q\}$ and $\lambda(i_1)=1$,
where in all cases $i_1\>3$.
For such $2$-partitions $I^\prime$ we set
\[
\tau(I^\prime)=
\begin{cases}
\{2-\lambda(i_1),i_1+1,\dots,i_q+1\}&\text{if} \quad I^\prime=\{i_1,\dots,i_q\}\\
\{i_1-1,\dots,i_q-1\}&\text{if} \quad I^\prime=\{1,i_1,\dots,i_q\}\;\; \text{or}\;\; I^\prime=\{2,i_1,\dots,i_q\}
\end{cases}
\]
Now for $I=S^r(I^\prime)$ set $\tau(I)=S^r(\tau(I^\prime))$.
This formula extends the action of $\tau$ to the whole set $\mathcal{P}_2$.
A test shows that all formulas \eqref{eqcond} are satisfied.

Thus on $\mathcal{P}_2$ is defined an action of monoid
$\mathbb{T}\simeq\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{N}$,
generated by the set $\{\omega,\tau,S\}$ of maps
$\mathcal{P}_2\to\mathcal{P}_2$.
It is easy to check that this action is free.

For $\alpha\in\mathcal{A}$ the set $\mathcal{V}^{-1}(\alpha)$
consists from two $2$-partitions.
Denote by $\theta(\alpha)\in\mathcal{P}_2$ those of them,
the lowest coordinate of that is odd.
\stepcounter{mycounter}
\begin{lm}\label{lmTet}
\begin{enumerate}[\rm(a)]
\item Let $I=(i_1,\dots,i_q)\in\mathcal{P}_2$ and $\lambda(i_1)=1$.
Then $I=\theta(c(\gamma))$ for $\gamma\in\G$ iff $i_1\>3$.
\item For $\gamma\in\G$ let $\theta(c(\gamma))=t(I)$,
where $t\in\mathbb{T},I\in\mathcal{P}_2$.
Assume that $f_I\<f_{\theta(c(\gamma))}$.
Then $I=c(\gamma)$ and $t=\rm{id}_{\mathcal{P}_2}$.
\end{enumerate}
\end{lm}
\begin{proof}
Claim (a) directly follows from Lemma \ref{lm30}.
Let us prove (b). Since $i_1\>3$, formula \eqref{defS} shows that if 
$\theta(c(\gamma))=S^r(I)$, then $r=0$.
Therefore if $\theta(c(\gamma))=(i_1,\dots,i_q)=\tau(I)$
then either $I=(1,i_1+1,\dots,i_q+1)$ or $I=(2,i_1+1,\dots,i_q+1)$,
according to $\lambda(i_1)=1,0$.
If, finally, $\theta(c(\gamma))=\omega(i_1^\prime,\dots,i_q^\prime)$,
then $i_1^\prime=i_1+1,\dots,i_q^\prime=i_q+1$ as it follows from \eqref{defW}.
Thus if $t\neq\rm{id}_{\mathcal{P}_2}$, then $f_{\theta(c(\gamma))}<f_I$
that completes the proof.
\end{proof}
For $\gamma\in\G$ define $\theta(\gamma)=f_{\theta(c(\gamma))}\in\mathbb{N}$.
From Lemma \ref{lmTet} it follows that $\theta(\gamma)$ is the lowest number
in $(p\cdot\mathcal{V}\cdot Z)^{-1}(\gamma)\subset\mathbb{N}$.
Since $Z:\mathbb{N}\to\mathcal{P}_2$ is a canonical bijection, the maps
$\omega,\tau$ and $S$ are uniquely defined on $\mathbb{N}$.
Collecting the whole above information, we conclude:
\stepcounter{mycounter}
\begin{tth}\label{th10}
On the set of natural numbers $\mathbb{N}$ is
defined a free action of monoid $\mathbb{T}\simeq\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{N}$,
generated by the above defined set $\{\omega,\tau,S\}$ of maps $\mathbb{N}\to\mathbb{N}$.
For each orbit $x\subset\mathbb{N}$ of $\mathbb{T}$ there exists a unique $\gamma(x)\in\G$
such that $x=\mathbb{T}(\theta(\gamma(x)))$.
This correspondence is a bijection between the set of orbits of $\mathbb{T}$
and the set $\G$. Let $\pi:\mathbb{N}\to\G$ be the natural projection.
Then $\pi=p\cdot\mathcal{V}\cdot Z$. In particular, $F(\mathbb{T}(n))=F(n)$.
\end{tth}
\stepcounter{mycounter}
\begin{rem}
It is obvious that $\chi(\omega(n))=\chi(n)$.
Directly verifiable formula $D(S_\mathcal{A}^r(A);t)=t^rD(A;t)$
implies that $\chi(S^r(n))=(-1)^r\chi(n)$.
Now from the definition of $\tau$ we obtain $\chi(\tau(n))=-\chi(n)$.
\end{rem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Essential Numbers}\label{secCEss}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setcounter{mycounter}{0}

In the previous section we have introduced an injective map $\theta:\G\to\mathbb{N}$,
the image of that is a fundamental domain for the action of
monoid $\mathbb{T}$ on $\mathbb{N}$ (Theorem \ref{th10}).
Here we give a simple description of this set of integers.
The next definition agrees (as Lemma \ref{lmTet}(b) shows)
with the notation we have used in Theorem \ref{th10}.
\stepcounter{mycounter}
\begin{df}
For $\gamma\in\G$ let $\theta(\gamma)$ be the lowest number in $\pi^{-1}(\gamma)$.
A number of the form $\theta(\gamma)$ is called an \emph{essential number}.
If $F(\theta(\gamma))=k$, then $\theta(\gamma)$ is called an \emph{essential $k$-number}.
If $\gamma\in\qz$, then $\theta(\gamma)$ is called a $F$(ibonacci)-\emph{prime} number.
\end{df}
The set of essential $k$-numbers is denoted by $\mathcal{E}(k)$,
and by $\mathcal{E}=\bigcup_{k\>0}\mathcal{E}(k)$ is denoted the set of all essential numbers.
Theorem \ref{th10} implies that any $n\in\mathcal{E}$ may
uniquely be represented as a $*$-product of the $F$-primes.
\stepcounter{mycounter}
\begin{lm}\label{lmPsi}
Let $\Psi(k)=\#\mathcal{E}(k)$.
Then $\Psi(1)=1$ and $\Psi(k)$ satisfies recurrence \eqref{400}.
\end{lm}
\begin{proof}
The set $\mathcal{E}(k)$ is finite, since it is in a bijective correspondence
with $\delta^{-1}(k)$.
Let $r>1$ be an integer and let
\[
\Gamma(k,r)=\{a_1/b_1*\dots*a_s/b_s\in\delta^{-1}(k),s\in\mathbb{N}:b_s=r\}
\]
Then $\Gamma(k,r)\neq\emptyset$ iff $r|k$. In this case obviously
$\#\Gamma(k,r)=\Psi(k/r)\varphi(r)$. Since $\G$ is a free monoid,
we have $\Gamma(k,r_1)\cap\Gamma(k,r_2)=\emptyset$ for $r_1\neq r_2$.
Therefore
\[
\Psi(k)=\sum_{1<r\<k,r|k}\#\Gamma(k,r)=\sum_{1<r\<k,r|k}\Psi(k/r)\varphi(r)
\]
The proof is completed.
\end{proof}
\stepcounter{mycounter}
\begin{rem}\label{remE}
To get an idea on the behavior of $\Psi(k)$, let us notice that
for a prime $p$ and for the distinct primes $p_1,\dots,p_m$ we have
\[
\Psi(p^n)=(p-1)(2p-1)^{n-1},\qquad
\Psi(p_1\dots p_m)=B(m)\;(p_1-1)\dots(p_m-1)
\]
where $B(0)=1$ and
\[
B(m)=\sum_{r=0}^{m-1}\binom{m}{r}B(r)
\]
These formulas may easily be established by induction.

The elements of sequence $B(m)=\{1,1,3,13,75,541,4683,47293,545835,\cdots\}$
are known as the \emph{ordered Bell numbers} (see \cite{Wilf}).
The generating function for $B(m)$ is $1/(2-\exp(x))$.
In general,
\[
\Psi(p_1^{a_1}\dots p_m^{a_m})=B_{a_1,\dots,a_m}\big(p_1,\dots,p_m\big)\;
(p_1-1)\dots(p_m-1)
\]
where $B_{a_1,\dots,a_m}(t_1,\dots,t_m)$ is a polynomial.
\end{rem}

To explicitly describe the set of essential numbers,
define a map $\varepsilon:\mathcal{A}\to\mathcal{P}_2$ by
\begin{equation*}\label{eqeps}
\varepsilon(A_1\times A_2\times\cdots\times A_s)=\big\{\varepsilon(A_1),\sigma^{2d(A_1)+1}\big(\varepsilon(A_2)\big),
\dots,\sigma^{2d(A_1)+2d(A_2)+\dots+2d(A_{s-1})+s-1}\big(\varepsilon(A_s)\big)\big\}
\end{equation*}
where
\begin{gather*}
d(\alpha_1,\dots,\alpha_q)=\alpha_1+\dots+\alpha_q-q,\qquad
\sigma\{i_1,\dots,i_q\}=\{i_1+1,\dots,i_q+1\}\\
\varepsilon(\alpha_1,\alpha_2,\dots,\alpha_q)=
\{2d(\alpha_1)+1,2d(\alpha_1,\alpha_2)+1,\dots,2d(\alpha_1,\alpha_2,\dots,\alpha_q)+1\}
\end{gather*}
\stepcounter{mycounter}
\begin{tth}\label{esspr}
\begin{enumerate}[\rm(a)]
\item Let $\gamma=g_1*\dots*g_s\in\G$ and $s\neq 0$.
Then $\theta(\gamma)=f_{\varepsilon(c(\gamma))}$.
\item  A number $n\in\mathbb{N}$ is essential iff either $n=0$, or
$\lambda(\mu_1(n))=1$ and $\mu_1(n)\>3$.
\item A number $n\in\mathbb{N}$ is essential iff $n=\lb m\tau\rb+\lb m\tau^2\rb,(m\in\mathbb{N})$.
\end{enumerate}
\end{tth}
\begin{proof}
Claim (a) follows from the definitions of maps $Z,\mathcal{V}$ and $p$
and Lemma \ref{lmTet}(b).
Claim (b) is a direct corollary of Lemma \ref{lmTet}(a).

Let us prove (c). Formula $\tau^2=\tau+1$ implies that
$\lb m\tau\rb+\lb m\tau^2\rb=2\lb m\tau\rb+m$.
Let $m>0$. It is well known (see \cite{GKP}) that
$\lb m\tau\rb =f_{\mu_1(m)+1}+\dots+f_{\mu_\infty(m)+1}-\lambda(\mu_1(m))$.
Therefore $2\lb m\tau\rb +m=f_{\mu_1(m)+3}+\dots+f_{\mu_\infty(m)+3}-2\lambda(\mu_1(m))$.
Since $f_{\mu_1(m)+3}-2=f_3+f_5+\dots+f_{\mu_1(m)+2}$, we obtain
\begin{equation}\label{eqess}
2\lb m\tau\rb+m=
\begin{cases}
f_{\mu_1(m)+3}+\dots+f_{\mu_\infty(m)+3} &\text{if}\quad \lambda(\mu_1(m))=0\\
f_3+f_5+\dots+f_{\mu_1(m)+2}+
f_{\mu_2(m)+3}+\dots+f_{\mu_\infty(m)+3} &\text{if}\quad \lambda(\mu_1(m))=1
\end{cases}
\end{equation}
Thus $\lambda(\mu_1(2\lb m\tau\rb+m))=1$
and $\mu_1(2\lb m\tau\rb+m)\>3$. Then $2\lb m\tau\rb+m\in\mathcal{E}$
by heading (b).

Contrary, let $n\in\mathcal{E}$.
Then $\mu_1(n)\>3$ and $\lambda(\mu_1(n))=1$ by heading (b).
Let $m=f_{l_1}+\dots+f_{l_{\mu_\infty(n)-a}}$,
where $a$ and $l_r$ are defined as follows.

If $\mu_1(n)=3$
then $a$ be a maximal $r\in[1,\mu_\infty(n)]$ such that $\mu_r(n)-\mu_{r-1}(n)=2$
for all $r\<a$ and $l_1=\mu_a(n)-2, l_r=\mu_{a+r-1}(n)-3,\;(r=2,3,\dots,\mu_\infty(n)-a+1)$.

If $\mu_1(n)>3$, then $a=0$ and $l_r=\mu_r(n)-3,\;(r=1,2,\dots,\mu_\infty(n))$.

Then formula \eqref{eqess} shows that $2\lb m\tau\rb +m=n$.
\end{proof}
\stepcounter{mycounter}
\begin{rem}
Formula \eqref{eqess} shows that $\lb m\tau\rb+\lb m\tau^2\rb$
is $F$-prime iff
$\lambda(\mu_2(m))=\dots=\lambda(\mu_\infty(m))=0$.
In particular, $\lb m\tau\rb+\lb m\tau^2\rb$ is not $F$-prime
if $f_{2r-1}<m<f_{2r}$ and it is $F$-prime if $m$ is a Fibonacci number.
\end{rem}
Since $\theta:\G\to\mathcal{E}$ is a bijective map,
the set of essential numbers $\mathcal{E}$
inherits the monoid structure of $\G$.
Theorem \ref{esspr}(a) implies that for $n_1,n_2\in \mathcal{E}$
the monoid multiplication on $\mathcal{E}$ has a form
\[
n_1*n_2=n_1+\sigma^{\mu_\infty(n_1)}(n_2)
\]
where $\sigma(0)=0$ and $\sigma(n)=f_{\sigma(Z(n))}$.
For example, $11\in\mathcal{E}(3)$ and $29\in\mathcal{E}(5)$.
Then $11*29=333$ and $29*11=351$.
From our results it follows that $F(n_1*n_2)=F(n_1)F(n_2)$.

On the other hand, map $\theta$ equips $\G$ with
a structure of totally ordered set as follows:
\stepcounter{mycounter}
\begin{df}
Let $\gamma_1,\gamma_2\in\G$. We say that
$\gamma_1\ll\gamma_2$ if $\theta(\gamma_1)\<\theta(\gamma_2)$.
\end{df}
For instance,
$3/5\prec 2/5\prec 1/5\prec 4/5$ according to
the sequence of essential $5$-numbers $24<29<55<87$. Another example is
$1/2*1/3\prec 1/3*1/2\prec 2/3*1/2\prec 1/2*2/3\prec 1/6\prec 5/6$ according to
the sequence of essential $6$-numbers $37<42<45<50<144<231$.

Theorem \ref{esspr}(a), in particular, provides
an algorithm to find the minimal essential $k$-number. Namely, it is sufficient to
find the minimal word $\gamma$ of finite set $p^{-1}(k)\in\G$
with respect to the order $\ll$. Then $f_{\varepsilon(c(\gamma))}$
is the minimal essential $k$-number.
The number of necessary calculation steps is proportional to $\Psi(k)$.
As Remark \ref{remE} shows, it grows very rapidly
with the number of prime factors of $k$.
In Section \ref{secG} we shall see, how this algorithm may be enhanced.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Stability and upper estimation for $F(n)$}\label{secEst}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setcounter{mycounter}{0}

In this section first we show that the maximal essential $k$-number equals to $f_{2k}-2$.
Together with Theorem \ref{th10} this leads to a "Fibonacci stable random distribution"
of $n\in\mathbb{N}$ with $F(n)=k$ (Theorem \ref{th2}). The second result of the section
is the estimation $F(n)\<\sqrt{n+1}$ (Theorem \ref{pr3}).
It shows, in particular, that the minimal essential $k$-number $\>k^2-1$.
In what follows a key role plays
\stepcounter{mycounter}
\begin{lm}\label{lm10}
Let $A=(\alpha_1,\dots,\alpha_q)\in \mathcal{A}_2$ and let $d(A)=\alpha_1+\dots+\alpha_q-q$. Then
\begin{equation}\label{403}
d(A)+1\<D(A)\<f_{d(A)+1}
\end{equation}
In these inequalities the identities hold iff either $q=1$ or $A=(2,2,\dots,2)$
for the lefthanded inequality, and iff
$\alpha_1,\alpha_q\<3$ and $\alpha_2=\dots=\alpha_{q-1}=3$
for the righthanded one.
\end{lm}
\begin{proof}
Our proofs of the left- and righthanded inequalities \eqref{403} are separated although
the arguments in both cases are similar. We establish Lemma \ref{lm10} by induction on $q$.
For $q=1$ all the claims are obvious. Let $q>1$.
In the proof will be used two easily verifiable identities
\begin{gather}\label{402}
D(\alpha_1,\dots,\alpha_m,\underbrace{2,\dots,2}_{r\;\mathrm{times}})=
D(\alpha_1,\dots,\alpha_m)+rD(\alpha_1,\dots,\alpha_{m-1},\alpha_m-1)\\
\label{405}
D(\alpha_1,\dots,\alpha_q)=D(\alpha_1,\dots,\alpha_{q-1},2)+
(\alpha_q-2)D(\alpha_1,\dots,\alpha_{q-1})
\end{gather}

We first prove the lefthanded inequality \eqref{403}
for $A=(\alpha_1,\dots,\alpha_m,2,\dots,2)$,
where $2$ is repeated $r>0$ times and $\alpha_m>2$ if $m\neq 0$, ($m+r=q$).
For $m=0$ formula \eqref{402} implies that $D(A)=d(A)+1$. Let $m>0$.
Since $m<q$ and $\alpha_m-1\>2$, we can apply the inductive assumption.
Then the righthanded side of \eqref{402} is greater than
$(r+1)(\alpha_1+\dots+\alpha_m-m)+1>\alpha_1+\dots+\alpha_m+r-m+1=d(A)+1$.

Assume now that $\alpha_q>2$. Then formula \eqref{405},
inductive assumption and already established case $\alpha_q=2$ imply
that the righthanded side of \eqref{405} is greater than
$(\alpha_q-1)(\alpha_1+\dots+\alpha_{q-1}-q+1)+\alpha_q>\alpha_1+\dots+\alpha_q-q+1=d(A)+1$.
The proof of the lefthanded inequality \eqref{403} is completed.

To prove the righthanded one,
first notice that for integers $a,r>0$ we have
\begin{equation}\label{f}
f_{a+r+1}\>f_{a+1}+rf_a
\end{equation}
where the identity holds iff $r=1$. Really,
$f_{a+r+1}=f_{a+1}+(f_a+f_{a+1}+\dots+f_{a+r-1})\>f_{a+1}+rf_a$.

Let now $A=(\alpha_1,\dots,\alpha_m,2,\dots,2)$,
where $2$ is repeated $r>0$ times and $\alpha_m>2$ if $m\neq 0$, ($m+r=q$).
If $m=0$, then $D(A)=d(A)+1\<f_{d(A)+1}$ and the identity holds iff $d(A)=2$.
In this case $A=(2,2)$. Let $m>0$. Then formula \eqref{402} and inductive assumption
imply that the righthanded inequality \eqref{403} is a corollary of \eqref{f} when
$a=\alpha_1+\alpha_2+\dots+\alpha_m-m$. The identity on it holds iff $r=1$.
In this case $\alpha_1\<3,\alpha_2=\dots=\alpha_{q-1}=3,\alpha_q=2$.

Finally, let $\alpha_q>2$. Then formula \eqref{405},
inductive assumption and already established case
$\alpha_q=2$ imply that the righthanded inequality \eqref{403} is a corollary of \eqref{f}
when $a=\alpha_1+\dots+\alpha_{q-1}-q+2$ and $r=\alpha_q-2$. The identity on it holds iff
$\alpha_1\<3,\alpha_2=\dots=\alpha_q=3$.
\end{proof}
\stepcounter{mycounter}
\begin{lm}\label{lmness}
Let $n$ be an essential number and let
$\mathcal{V}(Z(n))=A_1\times\dots\times A_s$. Then
\[
n\<f_{2d(A_1)+\dots+2d(A_s)+s+1}-2
\]
where the identity holds iff $s=1$ and $A_1=(2,\dots,2)$.
In this case $n=f_{2\dim(A_1)+2}-2$.
\end{lm}
\begin{proof}
Since $n$ is an essential number, we have
$n=f_{\varepsilon(A_1\times\dots\times A_s)}$ by Theorem \ref{esspr}.
If $\varepsilon(A_1\times\dots\times A_s)=\{i_1,\dots,i_q\}$, then $i_1$ is an odd number and
$i_q=2d(A_1)+\dots+2d(A_s)+s$.
But $i_1\>3$ because $A_1\in \mathcal{A}_2$ by Theorem \ref{esspr}. Therefore
\[
n\<\sum_{i=0}^{2\big\lb \frac{i_q-3}{2}\big\rb }f_{i_q-2i}=f_{i_q+1}-3+\lambda(i_q)
\]
In this inequality the identity holds iff $i_1=3,4$ and $i_a=i_1+2a,(a=0,1,\dots,q-1)$.
Since $a_1$ is an odd number, we have $a_1=3$. In this case
$\{i_1,i_2,\dots,i_q\}=\{3,5,\dots,2q+1\}$ is a simple 2-partition.
Thus $s=1$ and $A_1=(2,\dots,2)$.
\end{proof}
\stepcounter{mycounter}
\begin{cor}\label{press}
The maximal essential $k$-number equals to $f_{2k}-2=\theta((k-1)/k)$.
\end{cor}
\begin{proof}
Let $n$ be the maximal essential $k$-number and let $\mathcal{V}(Z(n))=A_1\times\dots\times A_s$.
Since $A_1\in \mathcal{A}_2$ (Theorem \ref{esspr}), we have $d(A_i)>0$.
Therefore Lemma \ref{lm10} shows that
\[
k=D(A_1)\cdots D(A_s)\>(d(A_1)+1)\cdots(d(A_s)+1)\>d(A_1)+\dots+d(A_s)+s
\]
Now from Lemma \ref{lmness} we obtain that
$n\<f_{2d(A_1)+\dots+2d(A_s)+s+1}-2\<f_{2k-s+1}-2\<f_{2k}-2$.
Since $n$ is a maximal essential $k$-number
and $f_{2k}-2\in \mathcal{E}(k)$, we conclude that $n=f_{2k}-2$.
\end{proof}

\stepcounter{mycounter}
\begin{tth}\label{th2}
Let $L_r(k)=\#\{n:f_r\<n<f_{r+1},F(n)=k\}$.
Then for $r\>2k$ the number $L_r(k)$
does not depends on $r$. Let $L(k)=\lim_{r\to\infty}L_r(k)$. Then
$L(1)=1$ and $L(k)=2\Psi(k)$ for $k>1$.
\end{tth}
\begin{proof}
Let $n\in\mathcal{E}(k)$. Since $\lambda(\mu_1(n))=1$
by Theorem \ref{esspr}(b), formulas \eqref{defW} and \eqref{defS}
show that for $m\>0$
\[
\mu_\infty(S^m(n))=\mu_\infty(n)+2m,\qquad
\mu_\infty(\omega(S^m(n)))=\mu_\infty(n)+2m+1
\]
Thus for any $r\>\mu_\infty(n)$ the interval
$[f_r,f_{r+1})$ contains one and only one number from the set
$N(n)=\{n,\omega(n),S(n),\omega(S(n)),\dots,S^m(n),\omega(S^m(n)),\dots\}$,
since $x\in[f_r,f_{r+1})\bigcap\mathbb{N}$ iff $\mu_\infty(x)=r$.

Therefore, thanks to Lemma \ref{lmPsi} and Corollary \ref{press}, we see
that for $r\>2k-1$ interval $[f_r,f_{r+1})$ contains exactly
$\Psi(k)$ numbers from the set $N_k=\bigcup_{n\in\mathcal{E}(k)}N(n)$.

Let $N(k,r)=N_k\bigcap[f_r,f_{r+1})$. Since $n\in\mathcal{E}$,
we obtain $\tau(N(k,r))\subset N(k,r+1)$.
Thus for $r\>2k$ interval $[f_r,f_{r+1})$ contains exactly $2\Psi(k)$
numbers with $F(n)=k$: $N(k,r)\bigcup\tau(N(k,r-1))$.
\end{proof}
\stepcounter{mycounter}
\begin{tth}\label{pr3}
$F(n)\<\sqrt{n+1}$. In this inequality the identity holds
iff $n=f^2_r-1,(r\in\mathbb{N})$.
\end{tth}
\begin{proof}
It is sufficient to establish the
inequality only for the essential numbers.
Let $\mathcal{V}(Z(n))=A_1\times\dots\times A_s$. We claim that
$F^2(n)\<n+1$, where the identity holds iff $s=1$
and either $A_1=(2,3,\dots,3)$ or $A_1=(3,3,\dots,3)$.
In the last case we have respectively
$n=f_3+f_7+\dots+f_{4q-1}=f^2_{2q}-1$, or
$n=f_5+f_9+\dots+f_{4q+1}=f^2_{2q+1}-1$.
Thus Theorem \ref{pr3} follows from this claim.

Since $n$ is essential, we have
$A_1=A=(\alpha_1,\dots,\alpha_q)\in\mathcal{A}_2$ (Theorem \ref{esspr}(a)).
For $s=1$ we shall prove the claim by induction on $q$.
For $q=1$ it is equivalent to inequality $\alpha^2\<f_{2\alpha-1}+1$,
where the identity holds iff $\alpha=2$ or $3$.
This is easily verified by induction on $\alpha$.

Let $q>1$. Since $n=f_{2d_1(A)+1}+\dots+f_{2d_q(A)+1}$ (Theorem \ref{esspr}(a)),
the inductive assumption implies that it is sufficient to establish the inequality
\begin{equation}
\label{23}
D^2(\alpha_1,\dots,\alpha_q)-
D^2(\alpha_1,\dots,\alpha_{q-1})\<f_{2d(A)+1}
\end{equation}
where $d(A)=d_q(A)$. In the proof we shall use two identities
\begin{equation}\label{21}
f_{a+b}=f_a f_b+f_{a-1} f_{b-1}
\end{equation}
\begin{equation}\label{18}
D(\alpha_1,\alpha_2,\dots,\alpha_q)=
\begin{cases}
D(\alpha_1,\dots,\alpha_{q-1},\alpha_q-1)+
D(\alpha_1,\dots,\alpha_{q-1}) & \text{if $\alpha_q\>3$}\\
D(\alpha_1,\dots,\alpha_{q-1})+D(\alpha_1,\dots,\alpha_{q-1}-1) &
\text{if $\alpha_q=2$}
\end{cases}
\end{equation}
the first of which is well known and the second one is directly verified.

Let $\alpha_q\>3$. Then
\begin{multline*}
D^2(\alpha_1,\dots,\alpha_q)-D^2(\alpha_1,\dots,\alpha_{q-1})
\overset{\mathrm{by\;(\ref{18})}}=\\
D(\alpha_1,\dots,\alpha_{q-1},\alpha_q-1)
\big(D(\alpha_1,\dots,\alpha_{q-1},\alpha_q-1)+2\,D(\alpha_1,\dots,\alpha_{q-1})\big)
\overset{\mathrm{by\;Lemma\, \ref{lm10}}}\<\\
f_{d(A)} (f_{d(A)}+2\,f_{d(A)-\alpha_q+2})
\overset{\mathrm{since}\;\alpha_q\>3}
\<f_{d(A)} (f_{d(A)}+2\,f_{d(A)-1})=
f_{d(A)} (f_{d(A)+1}+f_{d(A)-1})\overset{\mathrm{by\;(\ref{21})}}=f_{2\,d(A)+1}
\end{multline*}
The identities here hold iff
$\alpha_q=3$ and $D(\alpha_1,\dots,\alpha_{q-1},\alpha_q-1)=f_{d(A)}$.
Then Lemma \ref{lm10} shows that $\alpha_1=2$ or $\alpha_1=3$
and $\alpha_2=\alpha_3=\dots=\alpha_{q-1}=3$.

For $\alpha_q=2$ we have
\begin{multline*}
D^2(\alpha_1,\dots,\alpha_q)-D^2(\alpha_1,\dots,\alpha_{q-1})
\overset{\mathrm{by\;(\ref{18})}}=\\
D(\alpha_1,\dots,\alpha_{q-1}-1)
\big(D(\alpha_1,\dots,\alpha_{q-1}-1)+2\,D(\alpha_1,\dots,\alpha_{q-1})\big)
\overset{\mathrm{by\;Lemma\, \ref{lm10}}}\<\\
f_{d(A)-1}(f_{d(A)-1}+2\,f_{d(A)})=f_{d(A)-1}(f_{d(A)}+f_{d(A)+1})<
f_{d(A)-1}f_{d(A)}+f_{d(A)}f_{d(A)+1}
\overset{\mathrm{by\;(\ref{21})}}=f_{2\,d(A)+1}
\end{multline*}
This completes the proof for $s=1$.

Let $s>1$. Using the inductive assumption, we obtain
\[
D^2(A_1)\dots D^2(A_s)\<D^2(A_1)(N(\varepsilon(A_2\times\dots\times A_s))+1)\<\\
D^2(A_1)N(\varepsilon(A_2\times\dots\times A_s))+N(\varepsilon(A_1))+1
\]
To complete the proof it is sufficient to show that the
righthanded side of this expression is less than
\[
N(\varepsilon(A_1,A_2\times\dots\times A_s))+1=
N(\varepsilon(A_1))+\sigma^{2d(A_1)+1}(N(\varepsilon(A_2\times\dots\times A_s)))+1
\]
Let $N(\varepsilon(A_1))=f_{i_1}+\dots+f_{i_a}$ and
$N(\varepsilon(A_2\times\dots\times A_s))=f_{j_1}+\dots+f_{j_b}$.
Then $i_1\>3,d(A_1)+1=(i_a+1)/2$ and $2d(A_1)+1=i_a$. From Lemma \ref{lm10}, we know that
$D^2(A_1)\<f^2_{(i_a+1)/2}$. Therefore the needed claim follows from the inequality
$f^2_{(i_a+1)/2}(f_{j_1}+\dots+f_{j_b})<f_{j_1+i_a}+\dots+f_{j_b+i_a}$.
But $f^2_{(i+1)/2}f_j<f_{i+j}$
for odd $i\>3$ and any $j$, since
$f_{i+j}=f_if_j+f_{i-1}f_{j-1}=(f^2_{(i+1)/2}+f^2_{(i-1)/2})f_j+f_{i-1}f_{j-1}$
by formula \eqref{21}.
\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{How often $\chi(n)=0$}\label{secSym}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setcounter{mycounter}{0}
This section concerns an investigation of function $\chi(n)$.
The main result here is that the natural density of
whose $n\in\mathbb{N}$, for which $\chi(n)=0$, equals to 1.
\stepcounter{mycounter}
\begin{lm}
\label{cor3}
Let $n,r,a\in\mathbb{N}$ and $r>1$. Then
\begin{alignat}{2}
\chi(n) &=(-1)^r\chi(f_{r+2}-2-n)\quad
&\text{\rm if}& \quad n\in[f_r-1,f_{r+1}-1]\label{12}\\
\chi(n) &=0\quad &\text{\rm if}&\quad n\in[2f_r-1,f_{r-1}+f_{r+1}-1]\label{14}\\
\chi(n) &=\chi(n+f_a+f_{a+2})\quad
&\text{\rm if}&\quad\text{\rm $n\in[0,f_r-1]$\quad and\quad $a\>r$}\label{15}
\end{alignat}
\end{lm}
\begin{proof}
Proof of formula \eqref{12}: Clear is that $n\in[f_r-1,f_{r+1}-1]$
iff $f_{r+2}-2-n\in[f_r-1,f_{r+1}-1]$.
Since $f_1+f_2+\dots+f_r=f_{r+2}-2$, to each F.p. with $q$ parts
$n=f_{i_1}+\dots+f_{i_q}=f_I$ corresponds the F.p. of
$f_{r+2}-2-n=f_{\{1,2,\dots,r\}\setminus I}$ with $(r-q)$ parts
and vice versa. That, obviously, implies \eqref{12}.

Proof of formula \eqref{14}:
Let $Z(n)=\{i_1,i_2\dots,i_q\}$. Then $i_q=r+1$ by Lemma \ref{pr1}(a)
since $f_{r+1}-1<n<f_{r+2}-1$. If $i_{q-1}\<r-4$, then
$n=f_{i_1}+\dots+f_{i_{q-1}}+f_{i_q}\<f_{r-3}-1+f_{r+1}<2f_r-2$
in contradiction with our assumption $n>2f_r-2$. Thus either
$i_{q-1}=r-3$ or $i_{q-1}=r-2$.
If $i_{q-1}=r-3$, then $n\<f_{r-2}+f_{r+1}-1=2f_r-1$.
Hence $n=2f_r-1$. Applying Theorem \ref{th1}, we conclude that
\[
\chi(n)=D\big(\mathcal{V}(Z(2f_r-1));-1\big)=D(1,2,\dots,2,3;-1)=0
\]
If $i_{q-1}=r-2$, then $i_q$ is a simple component of $Z(n)$,
and $\alpha_q=2$. Therefore $\chi(n)=0$ by Theorem \ref{th1}.

Proof of formula \eqref{15}:
$\mu_\infty(n)\<r-1$ by Lemma \ref{pr1}(a).
Let $\mathcal{V}(Z(n))=(\alpha_1,\alpha_2,\dots,\alpha_q)$.
Obviously
\[
\mathcal{V}\big(Z(n+f_a+f_{a+2})\big)=
\begin{cases}
(\alpha_1,\dots,\alpha_{q-1},\alpha_q+2) & \text{if $\mu_\infty(n)=r-1$ and $a=r$}\\
(\alpha_1,\dots,\alpha_q,\alpha_{q+1},2) & \text{otherwise}.
\end{cases}
\]
Since in the first case the coordinates of associated vectors of $n$ and
$n+f_a+f_{a+2}$ have the same parity, formula \eqref{15} follows
from Theorem \ref{th1}.
In the second case \eqref{15} follows from the recursions \eqref{11}.
\end{proof}
\stepcounter{mycounter}
\begin{cor}\label{cor40}
\begin{enumerate}[\rm(a)]
\item Let $h(r)=\#\{n\in\mathbb{Z}:0\<n\<f_r-1\;\;\text{and}\;\;\chi(n)=0\}$.
Then $h(0)=h(1)=h(2)=h(3)=0,h(4)=1$ and for $r\>5$ we have
\begin{equation}\label{eqH}
h(r)=f_{r-5}+1+h(r-1)+2h(r-4)
\end{equation}
\item Let $n$ and $k$ be the naturals such that $\chi(n+1)=\chi(n+2)=\dots=\chi(n+k)=0$,
and $\chi(n)\neq 0,\chi(n+k+1)\neq 0$. Then $k=f_{r(n)}+1$ for some $r(n)\>0$.
Moreover, for any $k=f_r+1$ such $n$ is exists.
\end{enumerate}
\end{cor}
\begin{proof}
Proof of (a): For $r<5$ the claim is obvious. Let $r\>5$.
The number $h(r)-h(r-1)$ is a quantity of
$n\in[f_{r-1}-1,f_r-1]$ with $\chi(n)=0$. Identity \eqref{14} says that
$\chi(n)=0$ for all
$n\in[2f_{r-2}-1,f_{r-3}+f_{r-1}-1]\subset[f_{r-1}-1,f_r-1]$.
The quantity of these numbers equals to $f_{r-5}+1$.
Formula \eqref{12} implies that the quantities of $n$ with $\chi(n)=0$
in intervals $[f_{r-1}-1,2f_{r-2}-2]$ and $[f_{r-3}+f_{r-1},f_r-2]$
are equal. Let $n\in[f_{r-3}+f_{r-1},f_r-2]$. Then
$n=n_1+f_{r-3}+f_{r-1}$, where $n_1\in[0,f_{r-4}-2]$.
Formula \eqref{15} shows that $\chi(n)=\chi(n_1)$.
Since $\chi(f_{r-4}-1)\neq 0$, we obtain
\[
\#\{n\in[f_{r-1}-1,2f_{r-2}-2]\cup[f_{r-3}+f_{r-1},f_r-2]:\chi(n)=0\}=2h(r-4)
\]

Proof of (b):
The claim holds for $n<f_5-1$.
Assume that it holds for $n\in[0,f_r-1),(r\>5)$.
Let $n\in[f_r-1,f_{r+1}-1)$. If $n=2f_{r-1}-2$
then $\chi(n)=1,\chi(n+1)=0$. In this case we take
$r(n)=r-4$ as it follows from \eqref{14}.
Otherwise either $n\in[f_r-1,2f_{r-1}-2)$ or $n\in[f_{r-2}+f_r,f_{r+1}-1)$. In view of \eqref{12}
it is enough to consider only the second case.
Then $n=n_1+f_{r-2}+f_r$, where $n_1\in[0,f_{r-3}-1)$.
Formula \eqref{15} shows that $\chi(n)=\chi(n_1)$.
Since $\chi(f_{r-3}-1)\neq 0$,
the claim follows from the inductive assumption.
The existence follows from formula \eqref{14}
\end{proof}
\stepcounter{mycounter}
\begin{tth}\label{th41}
Let $E(k)=\#\{n\in\mathbb{Z}:0\<n\<k\;\;\text{and}\;\;\chi(n)=0\}$. Then
$\lim_{k\to\infty}E(k)/k=1$.
\end{tth}
\begin{proof}
The sequence $\{E(k)\}$ is a non decreasing one and
$\{E(f_r-1)\}=\{h(r)\}$ its increasing subsequence.
To prove the theorem it is sufficient
to establish that $\lim_{r\to\infty}h(r)/(f_r-1)=1$.

Let $H(t)=\sum_{r=0}^\infty h(r)t^r$.
A routine calculation, based on recurrence \eqref{eqH},
leads to expression
\begin{multline*}
H(t)=\frac{t^4(2t^2-1)}{(t^2-1)(t^2+t-1)(2t^3-2t^2+2t-1)}=\\
\frac{1}{1-t-t^2}+\frac{1}{2(t-1)}-\frac{1}{14(t+1)}+
\frac{8t^2-2t+3}{7(2t^3-2t^2+2t-1)}
\end{multline*}
It implies that
\[
h(r)=f_r-1+\frac{1}{7}\Big(3+\lambda(r)+a_1t^r_1+a_2t^r_2+a_3t^r_3\Big)
\]
where $t_1,t_2,t_3$ are the roots of equation $t^3-2t^2+2t-2=0$,
and $a_1,a_2,a_3$ are some constants (see \cite{GKP}, Sec.7.3).
From Cardan's formula, we obtain
\[
t_1=\frac{\beta^2+2\beta-2}{3\beta},\qquad
t_{2,3}=\frac{2+4\beta-\beta^2}{6\beta}\pm\frac{2+\beta^2}{6\beta}\sqrt{-3},
\qquad\mbox{where}\quad\beta=\sqrt[3]{17+3\sqrt{33}}
\]
It is easy to verify that $|t_{1,2,3}|<\tau\approx 1.61$,
($t_1\approx 1.54,|t_{2,3}|\approx 1.13$).
Now Binet's formula implies that $\lim_{r\to\infty}h(r)/(f_r-1)=1$.
\end{proof}
\stepcounter{mycounter}
\begin{rem}
One can show that the quantity of sequential $n$
with $\chi(n)\neq 0$ does not exceed $4$.
Moreover, for such sequences of $n$ only the following
sequences of $\chi(n)$ of maximal length appear:
\[
\{1\},\{-1\},\{1,-1\},\{-1,1\},\{1,1,-1\},\{-1,-1,1\},
\{1,-1,-1\},\{-1,1,1\},\{1,-1,-1,1\},\{-1,1,1,-1\}
\]
\end{rem}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{On the minimal essential $k$-numbers}\label{secG}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setcounter{mycounter}{0}

Let $M(k)$ be the minimal essential $k$-number.
At the end of Section \ref{secCEss}
we have described an algorithm to find $M(k)$.
In the present section we discuss how one can enhance this algorithm by
increasing the monoid $\mathbb{T}$ to some bigger monoids, which are also act on $\mathbb{N}$,
continuing the action of $\mathbb{T}$ and such that function $F$
still be invariant with respect to the action of them.

Let $\Sigma_s$ be the symmetric group of all permutations
of $\{1,2,\dots,s\}$. (By definition, $\Sigma_0=\{1\}$).
Let $\Gamma_s\subset\G$ be the set of all
elements $g_1*\dots*g_s\in\G,(g_i\in\qz,g_i\neq 1)$.
Group $\Sigma_s$ acts on $\Gamma_s$ by
$\varpi(g_1*\dots*g_s)=g_{\varpi(1)}*\dots*g_{\varpi(s)}$,
($\varpi\in\Sigma_s$). This action induces
an action of the group $\Sigma=\prod_{s=0}^\infty\Sigma_s$ on
$\G=\coprod_{s=0}^\infty\Gamma_s$: for
$\varpi=\prod_{m=1}^\infty\varpi_m\in\Sigma$ and $\gamma\in\Gamma_s$,
$\varpi(\gamma)=\varpi_s(\gamma)$.

On the other hand, let $U(\mathbb{Z}/b\mathbb{Z})$ be the group of units
of the ring $\mathbb{Z}/b\mathbb{Z}$ and let
$i:\qz\to\coprod_{b=1}^\infty U(\mathbb{Z}/b\mathbb{Z})$
be a bijective map, defined by $i(a/b)=a\mod b\in U(\mathbb{Z}/b\mathbb{Z})$.
(Keeping in mind this identification, instead of $i(a/b)$
we may write $a/b\in U(\mathbb{Z}/b\mathbb{Z})$.)
The group of automorphisms of the set $U(\mathbb{Z}/b\mathbb{Z})$
is $\Sigma_{\varphi(b)}$.
Thus the group of all automorphisms of the set $\qz\subset\G$,
commuting with $\delta$, is
$\Sigma_*=\prod_{b=1}^\infty\Sigma_{\varphi(b)}$.

Let $G=\Sigma\times H$, where $H\subset\Sigma_*$ is a subgroup.
The formula $(\varpi\times h)(g_1*\dots*g_s)=h(g_{\varpi(1)})*\dots*h(g_{\varpi(s)})$
defines an action of $G$ on $\G$.
Let $\GG$ be the corresponding set of orbits of $G$,
and let $p_G:\G\to\GG$ be a natural projection.
Then there is a unique map $\delta_G:\GG\to\mathbb{N}_*$ such that the diagram
\[
\xy
\xymatrix{
\mathbb{N}\ar[dr]_F\ar[r]^(.4){\pi} &\G\ar[d]^{\delta}\ar[r]^{p_G} &\GG\ar[dl]^{\delta_G}\\
&\mathbb{N}_*
}
\endxy
\]
is commutative.

For $\gamma\in\G$ let $G(\gamma)\subset\G$ be the $G$-orbit of $\gamma$.
Obviously, the operation $G(\gamma_1)*G(\gamma_2)=G(\gamma_1*\gamma_2)$
is well defined on $\Gamma_G(\qz)$.
It supplies $\Gamma_G(\qz)$ with structure of a \emph{commutative monoid,
freely generated by the set of orbits of $H$ on $\qz$}.
Then the map $p_G:\G\to\Gamma_G(\qz)$ is a homomorphism of monoids.
Let $\pi_G=p_G\cdot\pi:\mathbb{N}\to\GG$.
\stepcounter{mycounter}
\begin{df}
For $\gamma\in\GG$ let $\theta_G(\gamma)$ be the lowest number in $\pi_G^{-1}(\gamma)$.
A number of the form $\theta_G(\gamma)$ is called a \emph{$G$-essential number}.
If $F(\theta_G(\gamma))=k$, then $\theta_G(\gamma)$
is called a \emph{$G$-essential $k$-number}.
If $\gamma\in\qz$, then $\theta(\gamma)$ is called \emph{$F_G$-prime number}.
\end{df}
The set of $G$-essential $k$-numbers is denoted by $\mathcal{E}_G(k)$,
and by $\mathcal{E}_G=\bigcup_{k\>0}\mathcal{E}(k)$
it is denoted the set of all $G$-essential numbers.
It inherits the multiplicative structure of $\Gamma_G(\qz)$.

Let $w(\gamma)$ be a minimal element of $p_G^{-1}(\gamma)$
with respect to the order $\ll$.
Then $\theta_G(\gamma)=\theta(w(\gamma))$,
and thus the multiplication in $\mathcal{E}_G$ has a form
\begin{equation}\label{eqMult}
\theta_G(\gamma_1)\underset{G}{*}\theta_G(\gamma_2)=\theta(w(p_G(w(\gamma_1)*w(\gamma_1))))
\end{equation}
Each natural $b\>2$ defines $\varphi_H(b)$
$F_{\Sigma\times H}$-primes, where
$\varphi_H(b)$ be the number of orbits of restriction
$H$ to $U(\mathbb{Z}/b\mathbb{Z})$.

The next statement, that is directly follows from Theorem \ref{th10},
shows, how to raise up the action of
$G$ on $\G$ to an action on $\mathbb{N}$.
\stepcounter{mycounter}
\begin{pr}\label{cor10}
Let $G$ be a group of automorphisms of the set $\G$
such that $\delta G(\gamma)=\delta(\gamma)$ for all $\gamma\in\G$.
Then the formula
$\xi(\mathbb{T}(\theta(\gamma)))=\mathbb{T}(\theta(\xi(\gamma)))$,
($\xi\in G$) defines an action of group $G$ on $\mathbb{N}$,
that commutes with the action of $\mathbb{T}$.
Thus, in our assumptions, on $\mathbb{N}$ is uniquely defined an action
of monoid $\mathbb{T}_G=\mathbb{T}\times G$.
For each orbit $x\subset\mathbb{N}$ of this action
there exists a unique $\gamma(x)\in\GG$ such that
$x=\mathbb{T}_G(\theta_G(\gamma(x)))$.
This correspondence is a
bijection between the set of orbits of $\mathbb{T}_G$
and the set $\GG$. The natural projection $\mathbb{N}\to\GG$ coincides
with map $\pi_G=p_G\cdot\pi$. In particular, $F(\mathbb{T}_G(n))=F(n)$.
\end{pr}
Let, for instance, $H=\{1\}$. It is natural
to call the elements of $\mathcal{E}_{\Sigma}$ the \emph{commutative essential numbers}.
The sets of $F_\Sigma$-primes and $F$-primes are obviously the same.
One can write the multiplication of $\mathcal{E}_{\Sigma}$
in a more visible form than in general case.
To describe it, let us introduce some linear order in $\qz$.
\stepcounter{mycounter}
\begin{df}
Let $x=(x_1,\dots,x_{q_1}),y=(y_1,\dots,y_{q_2}),x\neq y$
be the vectors with natural coordinates.
If $q_1\neq q_2$, let us add to the left side of the shorter vector
$\max(q_1,q_2)-\min(q_1,q_2)$ coordinates, each of them equals to
the infinite big integer $\infty$. Then we may suppose that both
vectors $x,y$ have the same dimension $q=\max\{q_1,q_2\}$. Let
$r=\min\{m\;|\;x_{q-m}\neq y_{q-m}\}$.
We say that $x\lhd y$ if $x_{q-r}<y_{q-r}$,
and $x\rhd y$ otherwise.
Let $g_1,g_2\in\qz$. We say that $g_1\lhd g_2$ if $c(g_1)\lhd c(g_2)$,
and for the $F$-prime essential numbers $n_1=\theta(g_1),n_2=\theta(g_2)$,
$n_1\lhd n_2$ if $g_1\lhd g_2$.
\end{df}
For instance, $c(3/8)=(3,3)\lhd c(1/3)=(3)$.
Since $\theta(3/8)=63$ and $\theta(1/3)=8$, we obtain $63\lhd 8$.

It is not difficult to prove the following claim.
\stepcounter{mycounter}
\begin{tth}["Main theorem of arithmetic" for $\mathcal{E}_\Sigma$]\label{Comm}
A number $n$ is a commutative essential number
iff it has a form $n=n_1^{*r_1}*\dots*n_m^{*r_m}$,
where $n_1\lhd\dots\lhd n_m$ are $F$-primes. 
\end{tth}
Denote the product of numbers $n_1,n_2$ in monoid
$\mathcal{E}_\Sigma$ by $n_1\circ n_2$.
Theorem \ref{Comm} together with formula \eqref{eqMult}
shows how to find this product.
For example, for $37\in\mathcal{E}_\Sigma(6)$ and $92\in\mathcal{E}_\Sigma(8)$,
$37\circ 92=4341$, whereas $37*92=4362$ and $92*37=4650$.
Another example is $8\in\mathcal{E}_\Sigma(3),63\in\mathcal{E}_\Sigma(8)$.
Then $8\circ 63=63*8=673$, whereas $8*63=707$.

Theorem \ref{Comm} implies that in algorithm for finding  $M(k)$
from Section \ref{secCEss} it is sufficient
to test only the commutative essential $k$-numbers.
Then the number of calculation steps is proportional to $\Psi_\Sigma(k)=\#\mathcal{E}_\Sigma(k)$.
It is not difficult to show that for a prime $p$,
\[
\Psi_\Sigma(p^r)=\sum_{k_1+2k_2+\dots+rk_r=r}\;
\prod_{i=1}^r\binom{\varphi(p^i)+k_i-1}{k_i}
\]
($k_i\>0$ are integers). For example,
\[
\Psi_\Sigma(p^2)=\frac{3}{2}p(p-1),\quad
\Psi_\Sigma(p^3)=\frac{1}{6}p(p-1)(13p-5),\quad
\Psi_\Sigma(p^4)=\frac{1}{24}p(p-1)(73p^2-45p+14)
\]
By induction on $m$ it is easy to show that for the
distinct primes $p_1,\dots,p_m$ we have
\[
\Psi_\Sigma(p_1\dots p_m)=b(m)\;(p_1-1)\dots(p_m-1),\quad
\text{where}\quad b(m)=\sum_{r=0}^{m-1}\binom{m-1}{r}b(r),\quad\big(b(0)=1\big)
\]
The elements of sequence $b(m)=\{1,1,2,5,15,52,203,877,4140,\cdots\}$
are known as the \emph{Bell numbers} (see \cite{Wilf}).
The generating function for $b(m)$ is $\exp(\exp(x)-1) $.
In general,
\[
\Psi_\Sigma(p_1^{a_1}\dots p_m^{a_m})=b_{a_1,\dots,a_m}\big(p_1,\dots,p_m\big)\;
(p_1-1)\dots(p_m-1)
\]
where $b_{a_1,\dots,a_m}(t_1,\dots,t_m)$ is a polynomial on $t_i$'s.
From these formulas one can see that the possibility to use in our algorithm
only the commutative essential numbers is considerably decreasing the number of calculation steps.

The first twenty terms of $\Psi_\Sigma(k)$ are
$1,1,2,3,4,4,6,7,$ $10,8,10,10,12,12,16,18,16,19,18,24$.

\stepcounter{mycounter}
\begin{df}
We say that $k$ is a \emph{primitive number} if $M(k)$ is $F$-prime.
In this case we say that $M(k)$ is an \emph{$F$-primitive number}. 
\end{df}
Any prime number is obviously primitive.
But there are many non prime primitive numbers.
For instance, Theorem \ref{pr3} implies that
all Fibonacci numbers are primitive.
One can show that the numbers
\[
f_{2q-1}+f_{2q+1},\quad f_{2q}+f_{2q+2},\quad 
f_{2q-1}+f_{2q+3}+f_{2q+5},\quad f_{2q}+f_{2q+4}+f_{2q+6},
\qquad (q\>1)
\]
are also primitive (as well as many others).

The first twenty  primitive numbers $k$,
ordered by the values of $M(k)$, are
$1,2,3,5,7,8,11,13,18,$ $17,19,21,23,29,27,34,31,37,41,47$.
The corresponding sequence $M(k)$ of $F$-primitive numbers
is $0,3,8,$ $24,58,63,152,168,401,406,$ $435,440,1011,1050,1066,1155,1160,
2647,2736,2752$.

If it is already known that $k$ is primitive, then we can
find $M(k)$ in less than $\varphi(k)$ steps,
that is much faster for the non primes $k$
than by using the above algorithm.

One can show that for any $k$ there is a unique representation
\begin{equation}\label{eqPrim}
M(k)=M(\pi_1)\circ\dots\circ M(\pi_m)
\end{equation}
where $\pi_1,\dots,\pi_m$ are the primitive numbers.
That reduces the calculation of $M(k)$ to the following questions.
What is the set of primitive numbers?
How to decompose an arbitrary minimal essential number in $\circ$-product
of $F$-primitives?
Unfortunately, I have no conjectures concerning the possible answers.

Let $n>0$ be an $F$-primitive number. Then $\pi(n)\in\mathbb{Q}/\mathbb{Z}\setminus\{0\}\subset(0,1)$.
Since the Fibonacci numbers are primitive and
\[
\pi(f^2_{2q}-1)=\l 2,\overbrace{3,\dots,3}^{q-1}\r=\frac{f_{2q-1}}{f_{2q}},\qquad
\pi(f^2_{2q+1}-1)=\l \overbrace{3,3,\dots,3}^q\r=\frac{f_{2q-1}}{f_{2q+1}}
\]
the numbers $\tau^{-1}$ and $\tau^{-2}$ are the accumulation points
for the set of fractions $\pi(n)\subset(0,1)$.
It would be interesting to know if there exist other accumulation points for
the set $\pi(F-\mathrm{primitives})$?
An answer to this question may clarify the nature of primitive numbers.

A computer experiment shows that for the $F$-primitive $n$,
$\pi(n)$ often (but not always) is the best rational
approximation either to $\tau^{-1}$ or to $\tau^{-2}$
with denominator $F(n)$. The calculations also show that
$0.2<\pi(n)<0.8$ for any $F$-primitive number $n<10^6$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{On the graphic of $F(n)$}\label{secGraph}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setcounter{mycounter}{0}

The included plot is a graphical presentation of $F(n)$ in interval $[1,f_{26}-1]$.
From Theorem \ref{th1} it follows that
\[
F(n)=
\begin{cases}
1& \text{iff\; $n=f_r-1$\; and\; $r\>0$}\\
2& \text{iff\; $n=2f_r-1$\; or\; $n=f_{r-1}+f_{r+1}-1$\; and\; $r>1$}
\end{cases}
\]
The numbers $f_r-1,2f_r-1,f_{r-1}+f_{r+1}-1$ are the
bearing points for numerous symmetries of the functions $F$ and $\chi$.
For instance, if $f_r-1\<n\<f_{r+1}-1$, then $F(n)=F(f_{r+2}-2-n)$.

On the plot the thick points on the dashed vertical lines have coordinates
$(f_r-1,1)$; on the continuous vertical lines they have coordinates
$(2f_r-1,2)$ and $(f_{r-1}+f_{r+1}-1,2)$. The upper curve is defined by
the equation $F(n)=\sqrt{n+1}$. The thick points on it have coordinates $(f^2_r-1,f_r)$.

Let $C_r$ be the set of vertices of the convex hull of points
${(n,F(n))}$, where $n\in[f_r-1,f_{r+1}-1]$.
One can show, that $C_r$ includes the points $(c,F(c))$, where $c$ is one of the numbers
\[
f_r-1+f_q^2,\quad\text{or}\quad f_{r+1}-1-f_q^2
\qquad \Big(1\<q\<\Big\lb \frac{r-3}{2}\Big\rb \Big)
\]
The set $C_r$ coincides with this set of points if $\lambda(r)=1$.
For $\lambda(r)=0$ the set $C_r$
in addition includes the points $(c,F(c))$, where $c$ is one of the numbers
\[
f_r-1-2\cdot(-1)^q+f_q f_{q+1},
\quad\mbox{or}\quad f_{r+1}-1+2\cdot(-1)^q-f_q f_{q+1}
\qquad\Big(3\<q\<\frac{r}{2}-2\Big)
\]

The graphic of $F(n)$ reminds some "fractal" pictures.
I would like to propose a conjecture,
concerning a "fractal" behavior of the quantity of partitions,
all parts of which belong to a linear recurrent sequence. 
\stepcounter{mycounter}
\begin{df}
Let $\Phi:\mathbb{N}\to\mathbb{N}$ be a function.
For $v\in\Phi(\mathbb{N})$ let $N_\Phi(v)=\#\{n\in\mathbb{N}:\Phi(n)=v\}$.
Assume that $\Phi(\mathbb{N})=\{v_1,v_2,\dots\}$ is an infinite set
of the distinct numbers.
We say that \emph{$\Phi$ is a fractal function},
if $\overline{\lim}_{r\to\infty}|N_\Phi(v_r)|=\infty$.
If in addition $N_\Phi(v)<\infty$ for all $v\in\Phi(\mathbb{N})$, then we say
that $\Phi$ is a \emph{finite fractal function}.
Otherwise it is an \emph{infinite fractal function}.
\end{df}
For instance, our results imply that $F(n)$ is an infinite fractal function.
\stepcounter{mycounter}
\begin{conj}
Assume that the linear recurrence
\[
n_{i+r+1}=\lambda_rn_{i+r}+\lambda_{r-1}n_{i+r-1}+\dots+\lambda_0n_i,\quad (i\>0,\lambda_0,\dots,\lambda_r\in\mathbb{Z})
\]
for some initial values $n_1,n_2,\dots,n_r$
defines an infinite increasing sequence of the natural numbers $S=\{n_1,n_2,\dots\}$.
Let $\Phi_S(n)$ be a quantity of all partitions of $n$,
the parts of which belong to $S$.
Assume that the polynomial
$f_S(t)=t^{r+1}-\lambda_rt^r-\lambda_{r-1}t^{r-1}-\dots-\lambda_0$
is irreducible over $\mathbb{Q}$,
and that $r>1$. Then $\Phi_S(n)$ is a finite fractal function.
\end{conj}

\noindent{\bf Acknowledgments:}
I am grateful to R.~Munafo for a kind letter, where he explains his result,
to N.~Robbins, who sent me a draft of his article \cite{RN},
and to R.~Stanley pointed me out to the paper \cite{AR}. 
I also would like to thank A.~M.~Vershik for a useful discussion and a letter, where he has informed me
that the inequality $|\chi(n)|\<1$ was independently established by G.~Payne.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibliographystyle{plain}
\bibliography{fib}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}

FibSubmit.bbl
\begin{thebibliography}{1}

\bibitem{AR}
F.~Ardila.
\newblock {\sl {O}n the {C}oefficients of a {F}ibonacci {P}ower {S}eries}.
\newblock arXiv Mathematics Preprint Server, Preprint math.CO/0110160, 2001.

\bibitem{GKP}
R.~L. Graham, D.~E. Knuth, and O.~Patashnik.
\newblock {\em Concrete mathematics}.
\newblock Addison-Wesley, second edition, 1994.

\bibitem{HW}
G.~H. Hardy and E.~M. Wright.
\newblock {\em An introduction to the theory of numbers}.
\newblock The Clarendon Press Oxford University Press, New York, fifth edition,
  1979.

\bibitem{M}
J.~Milnor.
\newblock Periodic orbits, externals rays and the {M}andelbrot set: an
  expository account.
\newblock {\em Ast\'erisque}, (261):xiii, 277--333, 2000.
\newblock G\'eom\'etrie complexe et syst\`emes dynamiques (Orsay, 1995).

\bibitem{RN}
N.~Robbins.
\newblock Fibonacci partitions.
\newblock {\em Fibonacci Quart.}, 34(4):306--313, 1996.

\bibitem{SP}
N.~J.~A. Sloane and S.~Plouffe.
\newblock {\em The encyclopedia of integer sequences}.
\newblock Academic Press Inc., 1995.

\bibitem{Wilf}
H.~S. Wilf.
\newblock {\em Generatingfunctionology}.
\newblock Academic Press Inc., Boston, MA, second edition, 1994.

\end{thebibliography}
