ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.560410 J. Algebra Comb. Discrete Appl. 6(2) ● 105–122 Received: 9 March 2019 Accepted: 16 April 2019 Journal of Algebra Combinatorics Discrete Structures and Applications Complexity of neural networks on Fibonacci-Cayley tree∗ Research Article Jung-Chao Ban, Chih-Hung Chang Abstract: This paper investigates the coloring problem on Fibonacci-Cayley tree, which is a Cayley graph whose vertex set is the Fibonacci sequence. More precisely, we elucidate the complexity of shifts of finite type defined on Fibonacci-Cayley tree via an invariant called entropy. We demonstrate that computing the entropy of a Fibonacci tree-shift of finite type is equivalent to studying a nonlinear recursive system and reveal an algorithm for the computation. What is more, the entropy of a Fibonacci tree-shift of finite type is the logarithm of the spectral radius of its corresponding matrix. We apply the result to neural networks defined on Fibonacci-Cayley tree, which reflect those neural systems with neuronal dysfunction. Aside from demonstrating a surprising phenomenon that there are only two possibilities of entropy for neural networks on Fibonacci-Cayley tree, we address the formula of the boundary in the parameter space. 2010 MSC: 37A35, 37B10, 92B20 Keywords: Neural networks, Learning problem, Cayley tree, Separation property, Entropy 1. Introduction For the past few decades, neural networks have been developed to mimic brain behavior so that they are capable of exhibiting complex and various phenomena; they are widely applied in many disciplines ∗ This work is partially supported by the Ministry of Science and Technology, ROC (Contract No MOST 107- 2115-M-259-004-MY2 and 107-2115-M-390-002-MY2). Jung-Chao Ban; Department of Mathematical Sciences, National Chengchi University, Taipei 11605, Taiwan, ROC and Math. Division, National Center for Theoretical Science, National Taiwan University, Taipei 10617, Taiwan, ROC (email: jcban@nccu.edu.tw). Chih-Hung Chang (Corresponding Author); Department of Applied Mathematics, National University of Kaoh- siung, Kaohsiung 81148, Taiwan, ROC (email:chchang@nuk.edu.tw). 105 https://orcid.org/0000-0002-4920-6945 https://orcid.org/0000-0001-7352-5148 J.-C. Ban, C.-H. Chang / J. Algebra Comb. Discrete Appl. 6(2) (2019) 105–122 such as signal propagation between neurons, deep learning, image processing, pattern recognition, and information technology [1]. While the overwhelming majority of neural network models adopt n-dimensional lattice as network topology, Gollo et al. [15–17] propose a neural network with tree structure and show that the dynamic range attains large values. (See [2, 18, 19] for more references.) Recent literature also provides shreds of evidence that excitable media with a tree structure performed better than other network topologies [15, 16]. Mathematically speaking, a tree is a group/semigroup with finitely free generators, and group is one of the most ubiquitous structures found both in mathematics and in nature. A Cayley graph is a graph which represents the structure of a group via the notions of generators of the group. Remarkably, Pomi proposes a neural representation of mathematical group structures which store finite group through their Cayley graphs [20]. Since neural networks with tree structure come to researcher’s attention, it is natural to ask how the complexity of a tree structure neural network can be measured. Alternatively, it is of interest to know how much information a neural network can store. This motivates the investigation of the notion of tree-shifts introduced by Aubrun and Béal [3, 4]. A tree-shift is a shift space defined on a Cayley tree, and a shift space is a dynamical system which consists of patterns avoiding a set of local patterns (such a set is called a forbidden set). Roughly speaking, a tree-shift consists of colored Cayley trees. In [3], Aubrun and Béal indicate that tree-shifts constitute an intermediate class in between one-sided and multidimensional shifts. Ban and Chang propose an algorithm for the computation of the entropy of a class of tree-shifts called tree-shifts of finite type [8]. They also demonstrate that the entropy of a tree-shift of finite type is the logarithm of a Perron number and vice versa [6]. In other words, tree-shifts of finite type achieves rich phenomena. Nowadays, we have known that the entropy of a tree structure neural network reflects its complexity. It is natural to consider the complex nature of a neural network representing disordered brain such as Alzheimer’s disease, which is one of the most prevalent neurodegenerative disorders causing dementia and related severe public health concerns. It is well-known that Alzheimer’s disease is an irreversible, progressive brain disorder that slowly destroys the patient’s memory and thinking skills; although the greatest known risk factor is aging, Alzheimer’s disease is not just a disease for elders. Recent experimental investigations support the hypothesis that the concept of illness progression via neuron-to-neuron transmission and transsynaptic transport of pathogens from affected neurons to anatomically interconnected nerve cells is compatible with the inordinately drawn out prodromal phase and the uniform progression of the pathological process in Alzheimer’s disease. Also, a neuron-to-neuron transfer and propagation via seeding offer the most straightforward explanation for both the predictable distribution pattern of the intraneuronal tau lesions in the brain as well as the prolonged rate of disease progression that characterize Alzheimer’s disease neuropathologically. Readers who are interested in recent development about Alzheimer’s disease are referred to [10, 11, 14] and the references therein for more details. To investigate the complexity of a system with neuronal dysfunction, we propose neural networks whose topologies are Cayley graphs. The basic idea is that an infected neuron cannot transfer signal correctly. Hence we treat those inherit neurons as dead ones. In other words, if x is a node representing some infected neuron, then no node with prefix x is a node in the graph. To clarify the investigation, we study neural networks whose topology is Fibonacci-Cayley tree, which is a semigroup with generators {1,2} and a relation 2∗2 = 2. Namely, the nodes of a Fibonacci-Cayley tree come from the Fibonacci sequence. In Section 2, we recall some definitions and notions about tree-shifts and extend the concept to define a Fibonacci tree-shift, which is a shift space whose topology is Fibonacci-Cayley tree. It follows from the definition that a tree-shift is a dynamical viewpoint of coloring problem on a Cayley tree under a given rule. Section 3 provides the idea of the entropy of a Fibonacci tree-shift. We demonstrate therein that the computation of the entropy of a Fibonacci tree-shift of finite type is equivalent to studying a nonlinear recursive system and propose an algorithm for computing entropy. It is remarkable that, except for 106 J.-C. Ban, C.-H. Chang / J. Algebra Comb. Discrete Appl. 6(2) (2019) 105–122 extending the methodology developed in [6] to Fibonacci tree-shifts of finite type, we can generalize such an algorithm to tree-shifts of finite type with more complex topology. Our result might help in the investigation of the multidimensional coloring problem. Section 4 applies the results to elucidate the complexity of neural networks on Fibonacci-Cayley tree. The Fibonacci tree-shifts came from neural networks are constrained by the so-called separation property; after demonstrating there are only two possibilities of entropy for neural networks on Fibonacci-Cayley tree, we reveal the formula of the boundary in the parameter space. 2. Fibonacci-Cayley tree We introduce below some basic notions of symbolic dynamics on Fibonacci-Cayley tree. The main difference between Fibonacci-Cayley tree and infinite Cayley trees is their topologies. We refer to [3, 7] for an introduction to symbolic dynamics on infinite Cayley trees. 2.1. Cayley tree Let Σ ={1,2, . . . ,d}, d ∈ N, and let Σ∗ =⋃n≥0 Σn be the set of words over Σ, where Σ0 ={ϵ} consists of the empty word ϵ. An infinite (Cayley) tree t over a finite alphabet A is a function from Σ∗ to A; a node of an infinite tree is a word of Σ∗, and the empty word relates to the root of the tree. Suppose x is a node of a tree. Each node xi, i ∈ Σ, is known as a child of x while x is the parent of xi. A sequence of words (wk)1≤k≤n is called a path if, for all k ≤ n−1, wk+1 = wkik for some ik ∈ Σ and w1 ∈ Σ∗. Let t be a tree and let x be a node, we refer tx to t(x) for simplicity. A subtree of a tree t rooted at a node x is the tree t′ satisfying t′y = txy for all y ∈ Σ ∗, where xy = x1⋯xmy1⋯yn means the concatenation of x = x1⋯xm and y1⋯yn. Given two words x = x1x2 . . .xi and y = y1y2 . . .yj, we say that x is a prefix of y if and only if i ≤ j and xk = yk for 1 ≤ k ≤ i. A subset of words L ⊂ Σ∗ is called prefix-closed if each prefix of L belongs to L. A function u defined on a finite prefix-closed subset L with codomain A is called a pattern, and L is called the support of the pattern; a pattern is called an n-block if its support L = x∆n−1 for some x ∈ Σ∗, where ∆n = ⋃ 0≤i≤n Σi. Let AΣ ∗ be the set of all infinite trees over A. For i ∈ Σ, the shift transformations σi ∶AΣ ∗ →AΣ ∗ is defined as (σit)x = tix for all x ∈ Σ∗. The set AΣ ∗ equipped with the shift transformations σi is called the full tree-shift over A. Suppose w = w1⋯wn ∈ Σ∗. Define σw = σwn ○σwn−1 ○⋯○σw1 ; it follows immediately that (σwt)x = twx for all x ∈ Σ∗. Suppose that u is a pattern and t is a tree. Let supp(u) denote the support of u. We say that u is accepted by t if there exists x ∈ Σ∗ such that uy = txy for every node y ∈ supp(u). In this case, we say that u is a pattern of t rooted at the node x. A tree t is said to avoid u if u is not accepted by t; otherwise, u is called an allowed pattern of t. Given a collection of finite patterns F, let XF denote the set of trees avoiding any element of F. A subset X ⊆AΣ ∗ is called a tree-shift if X = XF for some F, and F is a forbidden set of X. A tree-shift XF is called a tree-shift of finite type (TSFT) if the forbidden set F is finite; we say that XF is a Markov tree-shift if F consists of two-blocks. Suppose A1,A2, . . . ,Ad are binary matrices indexed by A, the vertex tree-shift XA1,A2,...,Ad is defined as XA1,A2,...,Ad ={t ∈A Σ ∗ ∶ Ai(tx,txi)= 1 for all x ∈ Σ∗,1 ≤ i ≤ d}. (1) It follows immediately that each vertex tree-shift is a Markov tree-shift and each Markov tree-shift is a TSFT. In [7], the authors indicate that every TSFT is conjugated to a vertex tree-shift. 107 J.-C. Ban, C.-H. Chang / J. Algebra Comb. Discrete Appl. 6(2) (2019) 105–122 1 2 Figure 1. Each node of the Fibonacci-Cayley tree is a finite walk in the Fibonacci graph. 2.2. Fibonacci-Cayley tree Let Σ ={1,2} and let A =(1 1 1 0 ). Denote by ΣA the collection of finite walks of graph representation G (cf. Figure 1) of A together with the empty word ϵ. A Fibonacci-Cayley tree (Fibonacci tree) t over a finite alphabet A is a function from ΣA to A; in other words, a Fibonacci tree is a pattern whose support is the Fibonacci lattice ΣA. A pattern u is called an n-block if supp(u) = x∆n−1⋂ΣA for some x ∈ ΣA. Notably, there are two different supports for n-blocks, say L1 = ∆n−1⋂ΣA and L2 = 1∆n−1⋂ΣA, up to a shift of node. It is seen that the shift transformation σ2 is not well-defined in this case. We consider the shift transformation σ ∶ AΣA × ΣA → AΣA given by σ(t,x)y = txy if and only if xy ∈ ΣA. The set AΣA equipped with the new defined shift transformation σ is called the full Fibonacci tree-shift over A. A subset X ⊆AΣA is called a Fibonacci tree-shift if X = XF for some forbidden set F. Similar to the definitions above, a Fibonacci tree-shift XF is called a Fibonacci tree-shift of finite type (FTSFT) if F is a finite set. If F consists of two-blocks, then XF is a Markov-Fibonacci tree-shift. Suppose A1 and A2 are binary matrices indexed by A, the vertex-Fibonacci tree-shift XA1,A2 is defined as XA1,A2 ={t ∈A ΣA ∶ Ai(tx,txi)= 1 for all x,xi ∈ ΣA}. (2) See Figure 2 for the support of a Fibonacci tree. Example 2.1. Suppose that the alphabet A = {R,G} consists of red and green two colors. Let A1 and A2, the coloring rules on the left and right directions, respectively, be given as A1 = A2 =( 1 1 1 0 ) . That is, we can not color green on any two consecutive nodes. 3. Complexity of colored Fibonacci-Cayley tree This section investigates the complexity of Fibonacci tree-shifts of finite type. We use an invariant known as entropy introduced in [6, 8]. 3.1. Entropy of Fibonacci tree-shifts Let X be a Fibonacci tree-shift. For n ∈ N and w ∈ ΣA, let Γ [w] n (X) denote the set of n-blocks of X rooted at w. More explicitly, Γ[w]n (X)={u ∶ u is allowed and supp(u)= w∆n−1⋂ΣA}. Fix c ∈A, set Γ[w]c;n(X)={u ∈ Γ [w] n (X) ∶ uw = c} and γ [w] c;n = ∣Γ [w] c;n(X)∣, where ∣ ⋅ ∣ means the cardinality. For simplicity, we refer to Γ[ϵ]c;n(X) and γ [ϵ] c;n as Γc;n(X) and γc;n, respectively. The entropy of X is defined 108 J.-C. Ban, C.-H. Chang / J. Algebra Comb. Discrete Appl. 6(2) (2019) 105–122 ϵ 1 2 11 12 21 111 112 121 211 212 Figure 2. The support of Fibonacci-Cayley tree. It is seen that nodes 22, 122, 221, 222,⋯ are absent in this case. as follows. Definition 3.1. Suppose X is a Fibonacci tree-shift. The entropy of X, denoted by h(X), is defined as h(X)= limsup n→∞ ln 2 γn n , (3) where ln2 = ln○ ln. Notably, the growth rate of the number of nodes of ∆n⋂ΣA is exponential; this makes the speed of increase of γn doubly exponential. Hence, the entropy h(X) measures the growth rate of feasible patterns concerning their height. Let A = {c1,c2, . . . ,ck} for some k ≥ 2 ∈ N. Given two binary matrices A1 = (ai,j)ki,j=1 and A2 = (bi,j)ki,j=1, it comes immediately that γn = k ∑ ℓ=1 γℓ;n and γi;n = k ∑ j1,j2=1 ai,j1bi,j2γ [1] j1;n−1γ [2] j2;n−1 (4) for 1 ≤ i ≤ k and n ≥ 3 ∈ N, herein X = XA1,A2 is a vertex-Fibonacci tree-shift, γ [w] ℓ;n refers to γ[w]cℓ;n, and γi;2 = ( k ∑ j=1 ai,j) ⋅( k ∑ j=1 bi,j) for 1 ≤ i ≤ k. For w ∈ ΣA, the follower set of w is defined as Fw ={w′ ∈ ΣA ∶ ww′ ∈ ΣA}. Since each element w = w1w2⋯wn ∈ ΣA is a finite walk in the Fibonacci graph G (cf. Figure 1), it is easily seen that Fw ={ ΣA, wn = 1; F2, otherwise. 109 J.-C. Ban, C.-H. Chang / J. Algebra Comb. Discrete Appl. 6(2) (2019) 105–122 This makes γ [1] i;n = γi;n and γ [2] i;n = k ∑ j=1 ai,jγ [21] j;n−1 = k ∑ j=1 ai,jγj;n−1 (5) for 1 ≤ i ≤ k and n ≥ 3 ∈ N. Substituting (4) with (5) derives γi;n = k ∑ j1,j2,j3=1 ai,j1bi,j2aj2,j3γj1;n−1γj3;n−2 for 1 ≤ i ≤ k and n ≥ 4 ∈ N. Alternatively, computing the entropy of X is equivalent to the investigation of the following nonlinear recursive system. ⎧⎪⎪⎪⎪⎪⎪⎪⎪ ⎨ ⎪⎪⎪⎪⎪⎪⎪⎪⎩ γi;n = k ∑ j1,j2,j3=1 ai,j1bi,j2aj2,j3γj1;n−1γj3;n−2, γi;2 = ( k ∑ j=1 ai,j) ⋅( k ∑ j=1 bi,j), (6) for 1 ≤ i ≤ k and n ≥ 4 ∈ N. We call (6) the recurrence representation of XA1,A2 . Example 3.2. Suppose that A={c1,c2} and A1 = A2 =( 1 1 1 0 ) . Observe that ⎧⎪⎪⎪⎪⎪ ⎨ ⎪⎪⎪⎪⎪⎩ γ1;n = (γ [1] 1;n−1 +γ [1] 2;n−1) ⋅(γ [2] 1;n−1 +γ [2] 2;n−1), γ2;n = γ [1] 1;n−1 ⋅γ [2] 1;n−1, γ1;2 = 4,γ2;2 = 1. Since γ[1]i;n = γi;n, γ [2] 1;n = γ [21] 1;n−1 +γ [21] 2;n−1 = γ1;n−1 +γ2;n−1, and γ [2] 2;n = γ [21] 1;n−1 = γ1;n−1, examining the entropy of XA1,A2 is equivalent to studying ⎧⎪⎪⎪⎪ ⎨ ⎪⎪⎪⎪⎩ γ1;n = (γ1;n−1 +γ2;n−1) ⋅(2γ1;n−2 +γ2;n−2), γ2;n = γ1;n−1 ⋅(γ1;n−2 +γ2;n−2), γ1;2 = 4,γ2;2 = 1. In the next subsection, we introduce an algorithm for solving the growth rate of the nonlinear recursive system (6). 3.2. Computation of entropy The previous subsection reveals that computing the entropy of a Fibonacci tree-shift of finite type is equivalent to studying a corresponding nonlinear recursive system. To address an algorithm for the computation of the entropy, we start with the following proposition. 110 J.-C. Ban, C.-H. Chang / J. Algebra Comb. Discrete Appl. 6(2) (2019) 105–122 Proposition 3.3. Suppose that X = XA1,A2 is a vertex-Fibonacci tree-shift over A with respect to A1,A2. Then the limit (3) exists and h(X)= limsup n→∞ ln∑ki=1 lnγi;n n . (7) Proof. From the Cauchy inequality γ1;n ⋅γ2;n⋯γk;n ≤( ∑ki=1 γi;n k ) k we derive that k ∑ i=1 lnγi;n ≤ k(ln k ∑ i=1 γi;n − lnk). It can be verified without difficulty that limsup n→∞ ln∑ki=1 lnγi;n n ≤ limsup n→∞ ln 2∑ki=1 γi;n n = h(X). It is noteworthy that if there exist 1 ≤ i ≤ k and m ≥ 2 such that γi;m ≥ γj;m for all j ≠ i, then γi;n ≥ γj;n for all j ≠ i and n ≥ m ∈ N. Without loss of generality, we may assume that γ1;n ≥ γi;n for all n ≥ 2 ∈ N and 1 ≤ i ≤ k. The inequality γ1;n ≤ k ∑ i=1 γi;n ≤ kγ1;n reveals that limsup n→∞ ln 2∑ki=1 γi;n n = limsup n→∞ ln 2 γ1;n n . Meanwhile, k ∑ i=1 lnγi;n = ln k ∏ i=1 γi;n ≥ lnγ1;n. Therefore, we conclude that limsup n→∞ ln∑ki=1 lnγi;n n ≥ limsup n→∞ ln 2 γ1;n n = limsup n→∞ ln 2∑ki=1 γi;n n = h(X). This completes the proof. A symbol c ∈A is called essential (resp. inessential) if γc;n ≥ 2 for some n ∈ N (resp. γc;n = 1 for all n ∈ N). Proposition 3.3 infers the alphabet A can be expressed as the disjoint union of two subsets AE and AI consisting of essential and inessential symbols, respectively. In addition, it is easily seen from (7) that h(X)= limsup n→∞ ln 2∑c∈A γc;n n = limsup n→∞ ln 2∑c∈AE γc;n n . For the simplicity, we assume that A=AE; that is, each symbol is essential. 111 J.-C. Ban, C.-H. Chang / J. Algebra Comb. Discrete Appl. 6(2) (2019) 105–122 Now we turn back to the elaboration of the nonlinear recursive system (6). First, we consider a subsystem γi;n = γij1 ;n−1γij2 ;n−1, 1 ≤ i ≤ k, (8) arose from (6). Notably, for each i, the above subsystem contains only one term in the original system and the coefficient is 1. We call such a system simple. Generally speaking, a Fibonacci tree-shift has many simple recurrence representations. The following theorem reveals the entropy of a vertex-Fibonacci tree-shift with simple recurrence representation relates to the spectral radius of some integral matrix. Theorem 3.4. Suppose that X = XA1,A2 is a Fibonacci tree-shift over A such that each symbol is essential. If the recurrence representation of X is simple, then there exists an integral matrix M such that h(X)= log ρM, where ρM is the spectral radius of M. Proof. Since ci is essential for 1 ≤ i ≤ k, we may assume that γi;2 ≥ 2 for simplicity. Proposition 3.3 demonstrates that h(X)= limsup n→∞ ln∑ki=1 lnγi;n n . Let θn = (lnγ1;n, lnγ1;n−1, lnγ2;n, lnγ2;n−1, . . . , lnγk;n, lnγk;n−1)T (9) be a 2k × 1 vector. The recursive system (5) suggests that there exists a 2k × 2k nonnegative integral matrix M such that θn = Mθn−1 for n ≥ 3. (10) Note that γi;2 = ( k ∑ j=1 ai,j) ⋅( k ∑ j=1 bi,j)≤ k2 for 1 ≤ i ≤ k. Therefore, h(X)= limsup n→∞ ln∑ki=1 lnγi;n n ≤ lim n→∞ ln∑2ki,j=1 M n(i,j) n ≤ lnρM. On the other hand, h(X)= limsup n→∞ ln∑ki=1 lnγi;n n = limsup n→∞ ln∑ki=1 2lnγi;n n ≥ limsup n→∞ ln∑ki=1(lnγi;n + lnγi;n−1) n = lim n→∞ ln∑2ki,j=1 M n(i,j) n = lnρM. This completes the proof. We call the matrix M sketched in Theorem 3.4 the adjacency matrix of the simple recursive system (5). This makes Theorem 3.4 an extension of a classical result in symbolic dynamical systems. 112 J.-C. Ban, C.-H. Chang / J. Algebra Comb. Discrete Appl. 6(2) (2019) 105–122 Example 3.5. Suppose that the alphabet A and A1,A2 are given, and the recurrence representation of XA1,A2 is { γ1;n = γ1;n−1 ⋅γ1;n−2, γ2;n = γ1;n−1 ⋅γ2;n−2. (11) Furthermore, each symbol in A is essential. Let θn = ⎛ ⎜⎜⎜ ⎝ lnγ1;n lnγ1;n−1 lnγ2;n lnγ2;n−1 ⎞ ⎟⎟⎟ ⎠ . It comes immediately that M = ⎛ ⎜⎜⎜ ⎝ 1 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 ⎞ ⎟⎟⎟ ⎠ since θn = Mθn−1. In addition, the characteristic polynomial of M is f(λ) = (λ − 1)(λ + 1)(λ2 − λ − 1) and the spectral radius of M is ρM = g, where g = 1+ √ 5 2 is the golden mean. Theorem 3.4 asserts that the entropy of XA1,A2 is h(XA1,A2)= lng. Theorem 3.6. Suppose that X = XA1,A2 is a Fibonacci tree-shift over A such that each symbol is essential. Then h(X)= max{lnρM ∶ M is the adjacency matrix of a simple subsystem of X}. (12) The main idea of the proof of Theorem 3.6 can be examined via the following example. Example 3.7. Suppose that A={c1,c2} and A1 = A2 =( 1 1 1 0 ) are the same as considered in Example 3.2. Recall that the recurrence representation of XA1,A2 is ⎧⎪⎪⎪⎪ ⎨ ⎪⎪⎪⎪⎩ γ1;n = (γ1;n−1 +γ2;n−1) ⋅(2γ1;n−2 +γ2;n−2), γ2;n = γ1;n−1 ⋅(γ1;n−2 +γ2;n−2), γ1;3 = 15,γ2;3 = 8,γ1;2 = 4,γ2;2 = 1. It can be verified without difficulty that γ1;n ≥ γ2;n ≥ γ1;n−1 ≥ γ2;n−1 for n ≥ 3. Therefore, we have two inequalities γ1;n = (γ1;n−1 +γ2;n−1) ⋅(2γ1;n−2 +γ2;n−2) = 2γ1;n−1γ1;n−2 +γ1;n−1γ2;n−2 +2γ2;n−1γ1;n−2 +γ2;n−1γ2;n−2 = γ1;n−1γ1;n−2(2+ γ2;n−2 γ1;n−2 +2 γ2;n−1 γ1;n−1 + γ2;n−1γ2;n−2 γ1;n−1γ1;n−2 )≤ 6γ1;n−1γ1;n−2, and γ2;n = γ1;n−1 ⋅(γ1;n−2 +γ2;n−2) = γ1;n−1γ1;n−2 +γ1;n−1γ2;n−2 = γ1;n−1γ1;n−2(1+ γ2;n−2 γ1;n−2 )≤ 2γ1;n−1γ1;n−2 < 6γ1;n−1γ1;n−2. 113 J.-C. Ban, C.-H. Chang / J. Algebra Comb. Discrete Appl. 6(2) (2019) 105–122 Consider the nonlinear recursive system αi;n = 6α1;n−1α1;n−2, i = 1,2,n ≥ 3, let θn = (lnα1;n, lnα1;n−1, lnα2;n, lnα2;n−1)T and M = ⎛ ⎜⎜⎜ ⎝ 1 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 ⎞ ⎟⎟⎟ ⎠ . It is noteworthy that M is also the adjacency matrix of the simple recurrence representation γi;n = γ1;n−1γ1;n−2, i = 1,2,n ≥ 3, of X. Meanwhile, θn = Mθn−1 +(ln6)14 = Mn−2θ2 +(ln6)(Mn−3 +⋯+M +I4)14, where 14 = (1,1,1,1)T . Therefore, we derive from Proposition 3.3 that h(XA1,A2)= limsup n→∞ ln∑2i=1 lnγi;n n ≤ limsup n→∞ ln∑2i=1 lnαi;n n ≤ lim n→∞ ln∑n−2i=1 ∥M i∥ n = lng, where g = 1+ √ 5 2 is the golden mean. Obviously, h(XA1,A2)≥ lng. This concludes that h(XA1,A2)= lng. Proof of Theorem 3.6. Since every symbol is essential, we may assume that, for 1 ≤ i ≤ k, γi;2 ≥ 2 for simplicity. Set h̵ = max{lnρM ∶ M is the adjacency matrix of a simple subsystem of X}. It suffices to show that h(X)≤ h̵. We may assume without losing the generality that γ1;n ≥ γ2;n ≥⋯≥ γk;n ≥ γ1;n−1 ≥ γ2;n−1 ≥⋯≥ γk;n−1 (13) for n ≥ 3. Recall that, for 1 ≤ i ≤ k and n ≥ 4, γi;n = k ∑ j1,j2,j3=1 ai,j1bi,j2aj2,j3γj1;n−1γj3;n−2, where A1 = (ai,j)1≤i,j≤k,A2 = (bi,j)1≤i,j≤k. Let γī1;n−1γī2;n−2 be the maximum in the above equation. Then γi;n = k ∑ j1,j2,j3=1 ai,j1bi,j2aj2,j3γj1;n−1γj3;n−2 = γī1;n−1γī2;n−2 k ∑ j1,j2,j3=1 ai,j1bi,j2aj2,j3 γj1;n−1γj3;n−2 γī1;n−1γī2;n−2 ≤ κγī1;n−1γī2;n−2 114 J.-C. Ban, C.-H. Chang / J. Algebra Comb. Discrete Appl. 6(2) (2019) 105–122 for some constant κ ∈ N. Notably, κ is independent of i and n. Consider the nonlinear recursive system αi;n = καī1;n−1αī2;n−2 for 1 ≤ i ≤ k. (14) Let θn = (lnα1;n, lnα1;n−1, lnα2;n, lnα2;n−1, . . . , lnαk;n, lnαk;n−1)T . Similar to the discussion in the proof of Theorem 3.4, there exists a 2k×2k integral matrix M such that θn = Mθn−1 +(lnκ)12k = Mn−2θ2 +(lnκ)(Mn−3 +⋯+M +I2k)12k, where 12k = (1, . . . ,1)T is a 2k × 1 vector. Combining the computation above with the fact γi;n ≥ 2 indicates that h(X)= limsup n→∞ ln 2∑ki=1 γi;n n = limsup n→∞ ln∑ki=1 lnγi;n n ≤ limsup n→∞ ln∑ki=1 lnαi;n n ≤ lim n→∞ ln∑n−2i=1 ∥M i∥ n = lnρM. Observe that (14) is a simple recurrence representation of X if we replace κ in (14) by 1, and M is the adjacency matrix of such a new system. Therefore, we conclude that h(X)≤ h̵. The proof is thus complete. Remark 3.8. A key presumption in Theorem 3.6 is that every symbol is essential. If there are inessential symbols, the proof of Theorem 3.6 infers that we only need to replace M by M′, where M′ is obtained by deleting all the rows and columns indexed by those inessential symbols. 4. Neural networks on Fibonacci-Cayley tree In this section, we apply the algorithm developed in the previous section to neural networks with the Fibonacci-Cayley tree as their underlying space. For some reasoning, the overwhelming majority of considered underlying spaces of neural networks are Zn lattice for some n ∈ N; nevertheless, it is known that the characteristic shape of neurons is tree. Some medical experiments suggest that the signal transmission might be blocked by those diseased neurons, which motivate the investigation of neural networks on “incomplete" trees such as Fibonacci-Cayley tree. 4.1. Neural networks on Cayley tree To clarify the discussion, we focus on the neural networks proposed by Chua and Yang [13], which is known as cellular neural network and is widely applied to many disciplines such as signal propagation between neurons, pattern recognition, and self-organization; the elaboration of other models such as Hopfield neural networks can be carried out analogously. Let Σ∗ be the set of nodes of Cayleys as described in the previous section. A cellular neural network on Cayley tree (CTCNN) is represented as d dt xw(t)=−xw(t)+z + ∑ v∈N avf(xwv(t)), (15) for some finite set N ⊂ Σ∗ known as the neighborhood, v ∈N , and t ≥ 0. The transformation f(s)= 1 2 (∣s+1∣− ∣s−1∣) (16) 115 J.-C. Ban, C.-H. Chang / J. Algebra Comb. Discrete Appl. 6(2) (2019) 105–122 xw xw1 xw2 a1 a2 a Figure 3. A cellular neural network with the nearest neighborhood defined on binary trees. In this case, the neighborhood N ={ϵ, 0, 1} and a = aϵ. is called the output function or activation function, and z is called the threshold. The weighted parameters A = (av)v∈N is called the feedback template, and Figure 3 shows the connection of a binary CTCNN with the nearest neighborhood. A mosaic solution x = (xw)w∈Σ∗ of (15) is an equilibrium solution which satisfies ∣xw∣ > 1 for all w ∈ Σ∗; its corresponding pattern y = (yw)w∈Σ∗ = (f(xw))w∈Σ∗ is called a mosaic output pattern. Since the output function (16) is piecewise linear with f(s)= 1 (resp. −1) if s ≥ 1 (resp. s ≤−1), the output of a mosaic solution x = (xw)w∈Σ∗ must be an element in {−1,+1} Σ ∗ , which is why we call it a pattern. Given a CTCNN, we refer to Y as the output solution space; namely, Y ={(yw)w∈Σ∗ ∶ yw = f(xw) and (xw)w∈Σ∗ is a mosaic solution of (15)} . 4.2. Learning problem Learning problem (also called the inverse problem) is one of the most investigated topics in a variety of disciplines. From the mathematical point of view, determining whether a given collection of output patterns can be exhibited by a CTCNN is essential for the study of learning problem. This subsection reveals the necessary and sufficient condition for the capability of exhibiting the output patterns of CTCNNs. For the compactness and consistency of this paper, we focus on cellular neural networks on the binary tree with the nearest neighborhood. The discussion of general cases is similar to the investigation in [5, 9, 12], thus it is omitted. A CTCNN with the nearest neighborhood is realized as d dt xw(t)=−xw(t)+z +af(xw(t))+a1f(xw1(t))+a2f(xw2(t)), (17) where a,a1,a2 ∈ R and w ∈ Σ∗. Considering the mosaic solution x = (xw)w∈Σ∗, the necessary and sufficient condition for yw = f(xw)= 1 is a−1+z >−(a1yw1 +a2yw2). (18) 116 J.-C. Ban, C.-H. Chang / J. Algebra Comb. Discrete Appl. 6(2) (2019) 105–122 Similarly, the necessary and sufficient condition for yw = f(xw)=−1 is a−1−z > a1yw1 +a2yw2. (19) Let V 2 ={v ∈ R2 ∶ v = (v1,v2), and ∣vi∣= 1,1 ≤ i ≤ 2}, and let α = (a1,a2) represent the feedback template without the self-feedback parameter a. The admissible local patterns with the +1 state in the parent neuron is denoted by B̃+(A,z)={v ∈ V 2 ∶ a−1+z >−α ⋅v}, (20) where “⋅" is the inner product in Euclidean space. Similarly, the admissible local patterns with the −1 state in the parent neuron is denoted by B̃−(A,z)={v ∈ V 2 ∶ a−1−z > α ⋅v}. (21) Furthermore, the admissible local patterns induced by (A,z) can be denoted by B(A,z)=B+(A,z)⋃B−(A,z), (22) where B+(A,z)={v ∶ vϵ = 1 and (v1,v2) ∈ B̃+(A,z)}, B−(A,z)={v ∶ vϵ =−1 and (v1,v2) ∈ B̃−(A,z)}. Namely, B(A,z) consists of two-blocks over A = {1,−1}. For simplicity, we omit the parameters (A,z) and refer to B(A,z) as B. Meanwhile, we denote the output space Y by XB to specify the set of local patterns B. Suppose U is a subset of V n, where n ≥ 2 ∈ N. Let Uc = V n ∖U. We say that U satisfies the linear separation property if there exists a hyperplane H which separates U and Uc. More precisely, U satisfies the separation property if and only if there exists a linear functional g(z1,z2, . . . ,zn)= c1z1+c2z2+⋯+cnzn such that g(v)> 0 for v ∈ U and g(v)< 0 for v ∈ Uc. Figure 4 interprets those U ⊂ V 2 satisfying the linear separation property. Proposition 4.1 elucidates the necessary and sufficient condition for the learning problem of CTCNNs, which follows from straightforward examination. Thus the proof is omitted. Such a property holds for arbitrary N provided N is prefix-closed. Readers are referred to [5] for more details. Proposition 4.1. A collection of patterns B =B+⋃B− can be realized in (17) if and only if either of the following conditions is satisfied: (Inv1) −B̃+ ⊆ B̃− and B̃− satisfies linear separation property; (Inv2) −B̃− ⊆ B̃+ and B̃+ satisfies linear separation property. Herein, B̃+ and B̃− are defined in (20) and (21), respectively. We emphasize that Proposition 4.1 demonstrate the parameter space can be partitioned into finitely many equivalent regions. Indeed, whenever the parameters a1 and a2 are determined, (18) and (19) partition the a-z plane into 25 regions; the “order" (i.e., the relative position) of lines a − 1 + (−1)ℓz = (−1)ℓ(a1yw1 +a2yw2), ℓ = 1,2, can be uniquely determined by the following procedures: 1) The signs of a1,a2 (i.e., the parameters are positive or negative). 117 J.-C. Ban, C.-H. Chang / J. Algebra Comb. Discrete Appl. 6(2) (2019) 105–122 (-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) (1,-1) (-1,1) (1,1) (-1,-1) (1,-1) (-1,1) (1,1) (-1,-1) (1,-1) (-1,1) (1,1) b b bb b b bb b b bb b b bb b b b b b b b b b b bb bb b b bb b b Figure 4. Suppose U is a proper subset of V 2 = {−1, 1}2. There are only 12 choices of U that satisfies the linear separation property 2) The magnitude of a1,a2 (i.e., ∣a1∣> ∣a2∣ or ∣a1∣< ∣a2∣). This partitions a-z plane into 8×25 = 200 regions. As a brief conclusion, the parameter space is partitioned into at most 200 equivalent regions. Example 4.2. Suppose that 0 < −a1 < a2. It follows from a1 − a2 < −a1 − a2 < a1 + a2 < −a1 + a2 that, whenever a and z are fixed, the “ordered” basic set of admissible local patterns B =B+⋃B− must obey B+ ⊆{(+;−,+),(+;+,+),(+;−,−),(+;+,−)} and B− ⊆{(−;+,−),(−;−,−),(−;+,+),(−;−,+)}, herein, we denote a two-block u by (uϵ;u1,u2) and use symbols “+" and “−" to represent +1 and −1, respectively, for clarity. If the parameters a and z locate in the region [3,2](cf. Figure 5), then the set of feasible local patterns is B[3,2] ={(+;−,+),(+;+,+),(+;−,−),(−;+,−),(−;−,−)}. A careful but straightforward examination indicates that two symbols are both inessential if and only if the pair of parameters (a,z) is in the plane below the red W -shape line. 4.3. Neural networks on Fibonacci-Cayley tree The definition of cellular neural networks on Fibonacci-Cayley tree is similar to the definition of Fibonacci-Cayley tree-shifts. Let A and ΣA be the same as defined in the previous section. A cellular neural network on Fibonacci-Cayley tree (FTCNN) with the nearest neighborhood is realized as d dt xw(t)={ −xw(t)+z +af(xw(t))+a1f(xw1(t))+a2f(xw2(t)), wn = 1; −xw(t)+z +af(xw(t))+a1f(xw1(t)), wn = 2; (23) 118 J.-C. Ban, C.-H. Chang / J. Algebra Comb. Discrete Appl. 6(2) (2019) 105–122 a−1 z [0, 0] [1, 0] [2, 0] [3, 0] [4, 0] [0, 1] [0, 2] [0, 3] [0, 4] [1, 1] [2, 1] [3, 1] [4, 1] [1, 2] [1, 3] [1, 4] [2, 4] [3, 4] [4, 4] [4, 3] [4, 2] [3, 2] [3, 3] [2, 3] [2, 2] Figure 5. For each chosen pair of parameters (a1, a2), the a-z plane is partitioned into 25 equivalent regions. where a,a1,a2 ∈ R and w = w1⋯wn ∈ ΣA. Suppose the parameters A = (a,a1,a2) and z are given. Let B be the set of feasible local patterns corresponding to (A,z) which is studied in the previous subsection. It can be verified without difficulty that the output space of (23) is YF ={t ∈AΣA ∶ t = t′∣ΣA for some t ′ ∈ Y = XB}. In other words, the output space YF of (23) is a Markov-Fibonacci tree-shift. 4.4. Entropy of neural networks on Fibonacci tree It is of interest that how much information a diseased neural network can store. Based on the algo- rithm developed in the previous section, we study the entropy of FTCNNs with the nearest neighborhood. 119 J.-C. Ban, C.-H. Chang / J. Algebra Comb. Discrete Appl. 6(2) (2019) 105–122 Suppose that the parameters a1,a2 are given. A pair of parameters (a,z) is called critical if, for each r > 0, there exists (a′,z′),(a′′,z′′) such that h(XB′) ≠ h(XB′′) = 0, where B′ =B(a′,a1,a2,z′),B′′ = B(a′′,a1,a2,z′′). Notably, the a-z plane is partitioned into 25 equivalent regions whenever a1 and a2 are given and is indexed as [p,q] for 0 ≤ p,q ≤ 4; we use Y[p,q] instead of XB for simplicity. Theorem 4.3. Suppose that the parameters a1,a2 are given. Let m = min{∣a1∣, ∣a2∣},M = max{∣a1∣, ∣a2∣}. Then h(Y[p,q])={ 0, if min{p,q}= 0 or max{p,q}= 1; lng, otherwise. Furthermore, (a,z) is critical if and only if a−1 = ∣∣z∣−m∣−M. (24) Proof. Obviously, h(Y[p,q])= 0 if min{p,q}= 0 or max{p,q}= 1. We only need to show that h(Y[p,q])= lng provided p,q > 0 and max{p,q}≥ 2. Actually, it suffices to consider the cases where [p,q]= [1,2] or [p,q] = [2,1] since the entropy function is increasing. We demonstrate that h(Y[1,2]) = lng; the other case can be derived analogously, thus it is omitted. Suppose that both symbols in A are essential. Let θn = (lnγ1;n, lnγ2;n, lnγ1;n−1, lnγ2;n−1)T , where γ1;n (resp. γ2;n) denotes the number of n-blocks whose rooted symbol is + (resp. −). Notably, for each simple recurrence representation of Y[1,2], there exist 2 × 2 binary matrices B1 and B2 satisfying 2 ∑ k=1 Bi(j,k) = 1 for 1 ≤ i,j ≤ 2 and M = ( B1 B2 I2 02 ) such that θn = Mθn−1 for n ≥ 2. Set v = (g,g,1,1)T . Then Mv = (g +1,g +1,g,g)T = (g2,g2,g,g)T = gv. Perron-Frobenius Theorem and Theorem 3.6 imply that h(Y[1,2])≥ lng. It is easily seen that h(Y[1,2])≤ lng, thus we can conclude that h(Y[1,2])= lng. Suppose that there is exactly one essential symbol. (In this case, the essential symbol is −.) It can be verified from (18), (19), and Proposition 4.1 that B[1,2] ={(+;+,+),(−;−,−),(−;−,+)} or B[1,2] ={(+;+,+),(−;−,−),(−;+,−)}. For either case, γi;n = γi;n−1γi;n−2 for i = 1,2, is a simple recurrence representation of Y[1,2], and its corresponding adjacency matrix is M = ⎛ ⎜⎜⎜ ⎝ 1 0 1 0 0 1 0 1 1 0 0 0 0 1 0 0 ⎞ ⎟⎟⎟ ⎠ . Deleting the first and third rows and columns of M delivers M′ =(1 1 1 0 ). This shows that h(Y[1,2])≥ lnρM′ = lng, 120 J.-C. Ban, C.-H. Chang / J. Algebra Comb. Discrete Appl. 6(2) (2019) 105–122 which is followed by h(Y[1,2])= lng. Next, we show that (a,z) is critical if and only if (a,z) satisfies (24). Let C = {ℓ1a1 +ℓ2a2 ∶ ℓ1,ℓ2 ∈ {−1,1}}, and let K1 = maxC and K2 = maxC ∖{K1}. be the largest and the second largest elements in C, respectively. A careful but straightforward verification asserts that (a,z) is critical if and only if a−1 = ∣∣z∣− K1 −K2 2 ∣− K1 +K2 2 . (See Figure 5 for more information.) The desired result follows from the fact that K1 = ∣a1∣+ ∣a2∣ and K2 = ∣a1∣+ ∣a2∣−2m. This completes the proof. 5. Conclusion This paper studies the entropy of Fibonacci-Cayley tree-shifts, which are shift spaces defined on Fibonacci-Cayley trees. Entropy is one of the most frequently used invariant that reveals the growth rate of patterns stored in a system. Followed by demonstrating that the computation of the entropy of a Fibonacci tree-shift of finite type is equivalent to studying a nonlinear recursive system, we propose an algorithm for computing entropy. It is seen that the so-called simple recursive system plays an important role. As an application, we elucidate the complexity of neural networks whose topology is Fibonacci- Cayley tree. Such a model reflects a brain going with neuronal dysfunction such as Alzheimer’s disease. A Fibonacci tree-shift came from a neural network is constrained by the so-called separation property. Aside from demonstrating a surprising phenomenon that there are only two possibilities of entropy for neural networks on Fibonacci-Cayley tree, we reveal the formula of the boundary in the parameter space. A related interesting problem is “does the black-or-white entropy spectrum of neural networks still hold for other network topologies?” Further discussion is in preparation. References [1] M. Anthony, P. L. Bartlett, Neural Network Learning: Theoretical Foundations, Cambridge Univer- sity Press, Cambridge, 1999. [2] V. R. V. Assis, M. Copelli, Dynamic range of hypercubic stochastic excitable media, Phys. Rev. E 77(1) (2008) 011923. [3] N. Aubrun, M.-P. Béal, Tree–shifts of finite type, Theoret. Comput. Sci. 459(9) (2012) 16–25. [4] N. Aubrun, M.-P. Béal, Sofic tree–shifts, Theory Comput. Syst. 53(4) (2013) 621–644. [5] J.-C. Ban, C.-H. Chang, Realization problem of multi–layer cellular neural networks, Neural Networks 70 (2015) 9–17. [6] J.-C. Ban, C.-H. Chang, Characterization for entropy of shifts of finite type on Cayley trees, 2017, arXiv:1705.03138. [7] J.-C. Ban, C.-H. Chang, Tree-shifts: Irreducibility, mixing, and chaos of tree–shifts, Trans. Amer. Math. Soc. 369 (2017) 8389–8407. 121 https://doi.org/10.1017/CBO9780511624216 https://doi.org/10.1017/CBO9780511624216 https://doi.org/10.1103/PhysRevE.77.011923 https://doi.org/10.1103/PhysRevE.77.011923 https://doi.org/10.1016/j.tcs.2012.07.020 https://doi.org/10.1007/s00224-013-9456-1 https://doi.org/10.1016/j.neunet.2015.06.003 https://doi.org/10.1016/j.neunet.2015.06.003 https://doi.org/10.1090/tran/6906 https://doi.org/10.1090/tran/6906 J.-C. Ban, C.-H. Chang / J. Algebra Comb. Discrete Appl. 6(2) (2019) 105–122 [8] J.-C. Ban, C.-H. Chang, Tree-shifts: The entropy of tree–shifts of finite type, Nonlinearity 30(7) (2017) 2785–2804. [9] J.-C. Ban, C.-H. Chang, S.-S. Lin, Y.-H Lin, Spatial complexity in multi-layer cellular neural net- works, J. Differ. Equ. 246(2) (2009) 552–580. [10] H. Braak, K. D. Tredici, Alzheimer’s pathogenesis: Is there neuron-to-neuron propagation?, Acta Neuropathol. 121(5) (2011) 589–595. [11] P. Brundin, R. Melki, R. Kopito, Prion–like transmission of protein aggregates in neurodegenerative diseases, Nat. Rev. Mol. Cell Biol. 11(4) (2010) 301–307. [12] C.-H. Chang, Deep and shallow architecture of multilayer neural networks, IEEE Trans. Neural Netw. Learn. Syst. 26(10) (2015) 2477–2486. [13] L. O. Chua, L. Yang, Cellular neural networks: Theory, IEEE Trans. Circuits Syst. 35(10) (1988) 1257–1272. [14] M. Goedert, F. Clavaguera, M. Tolnay, The propagation of prion–like protein inclusions in neurode- generative diseases, Trends Neurosci. 33(7) (2010) 317–325. [15] L. L. Gollo, O. Kinouchi, M. Copelli, Active dendrites enhance neuronal dynamic range, PLoS Comput. Biol. 5(6) (2009) e1000402. [16] L. L. Gollo, O. Kinouchi, M. Copelli, Statistical physics approach to dendritic computation: The excitable–wave mean–field approximation, Phys. Rev. E 85 (2012) 011911. [17] L. L. Gollo, O. Kinouchi, M. Copelli, Single–neuron criticality optimizes analog dendritic computa- tion, Sci. Rep. 3 (2013) 3222. [18] O. Kinouchi, M. Copelli, Optimal dynamical range of excitable networks at criticality, Nat. Phys. 2 (2006) 348–351. [19] D. B. Larremore, W. L. Shew, J. G. Restrepo, Predicting criticality and dynamic range in complex networks: Effects of topology, Phys. Rev. Lett. 106 (2011) 058101. [20] A. Pomi, A possible neural representation of mathematical group structures, Bull. Math. Biol. 78(9) (2016) 1847–1865. 122 https://doi.org/10.1088/1361-6544/aa72c0 https://doi.org/10.1088/1361-6544/aa72c0 https://doi.org/10.1016/j.jde.2008.05.004 https://doi.org/10.1016/j.jde.2008.05.004 https://doi.org/10.1007/s00401-011-0825-z https://doi.org/10.1007/s00401-011-0825-z https://dx.doi.org/10.1038/nrm2873 https://dx.doi.org/10.1038/nrm2873 https://doi.org/10.1109/TNNLS.2014.2387439 https://doi.org/10.1109/TNNLS.2014.2387439 https://doi.org/10.1109/31.7600 https://doi.org/10.1109/31.7600 https://doi.org/10.1016/j.tins.2010.04.003 https://doi.org/10.1016/j.tins.2010.04.003 https://dx.doi.org/10.1371/journal.pcbi.1000402 https://dx.doi.org/10.1371/journal.pcbi.1000402 https://doi.org/10.1103/PhysRevE.85.011911 https://doi.org/10.1103/PhysRevE.85.011911 https://doi.org/10.1038/srep03222 https://doi.org/10.1038/srep03222 https://doi.org/10.1038/nphys289 https://doi.org/10.1038/nphys289 https://doi.org/10.1103/PhysRevLett.106.058101 https://doi.org/10.1103/PhysRevLett.106.058101 https://doi.org/10.1007/s11538-016-0202-0 https://doi.org/10.1007/s11538-016-0202-0 Introduction Fibonacci-Cayley tree Complexity of colored Fibonacci-Cayley tree Neural networks on Fibonacci-Cayley tree Conclusion References