[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Weak and strong orders of linear recurring sequences

  • Published:
Computational and Applied Mathematics Aims and scope Submit manuscript

Abstract

The concept of the strong order of linear recurring sequence (LRS) is introduced in this paper. Necessary and sufficient conditions for the existence of the strong LRS order are derived. The strong LRS order is exploited for the formalization of the problem of the extension of a sequence from the available fragment (fragments) of that sequence. The definition of the strong LRS order opens new possibilities for formal sequence analysis whenever the weak LRS order of that sequence exists. Computational experiments with discrete iterative maps are used to illustrate the applicability of the strong LRS order in nonlinear system analysis.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

We’re sorry, something doesn't seem to be working properly.

Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

References

  • Bernstein DS (2009) Matrix mathematics: theory, facts, and formulas. Princeton University Press, Princeton

    Book  MATH  Google Scholar 

  • Brison OJ, Nogueira JE (2003) Linear recurring sequence subgroups in finite fields. Finite Fields Appl 9(4):413–422

    Article  MathSciNet  MATH  Google Scholar 

  • Bronstein M, Solé P (2004) Linear recurrences with polynomial coefficients. J Complex 20(2):171–181

    Article  MathSciNet  MATH  Google Scholar 

  • Everest G, Van Der Poorten A, Shparlinski IE, Ward T et al (2003) Recurrence sequences, vol 104. American Mathematical Society Providence, RI

    MATH  Google Scholar 

  • Fillmore JP, Marx ML (1968) Linear recursive sequences. SIAM Rev 10(3):342–353

    Article  MathSciNet  MATH  Google Scholar 

  • Gao Z, Fu F (2013) Linear recurring sequences and subfield subcodes of cyclic codes. Sci Chin Math 56(7):1413–1420

    Article  MathSciNet  MATH  Google Scholar 

  • Han KF, Baker D (1995) Recurring local sequence motifs in proteins. J Mol Biol 251(1):176–187

    Article  Google Scholar 

  • Kurakin V, Kuzmin A, Mikhalev A, Nechaev A (1995) Linear recurring sequences over rings and modules. J Math Sci 76(6):2793–2915

    Article  MathSciNet  MATH  Google Scholar 

  • Landauskas M, Navickas Z, Vainoras A, Ragulskis M (2016) Weighted moving averaging revisited—an algebraic approach. Comput Appl Math. https://doi.org/10.1007/s40314-016-0309-9

  • Lu P, Liu M, Oberst U (2004) Linear recurring arrays, linear systems and multidimensional cyclic codes over quasi-frobenius rings. Acta Appl Math 80(2):175–198

    Article  MathSciNet  MATH  Google Scholar 

  • Mikhalev A, Nechaev A (1996) Linear recurring sequences over modules. Acta Appl Math 42(2):161–202

    Article  MathSciNet  MATH  Google Scholar 

  • Navickas Z, Bikulčiene L (2006) Expressions of solutions of ordinary differential equations by standard functions. Math Modell Anal 11(4):399–412

    MathSciNet  MATH  Google Scholar 

  • Navickas Z, Bikulciene L, Ragulskis M (2010) Generalization of exp-function and other standard function methods. Appl Math Comput 216(8):2380–2393

    MathSciNet  MATH  Google Scholar 

  • Niederreiter H, Winterhof A (2008) Exponential sums for nonlinear recurring sequences. Finite Fields Appl 14(1):59–64

    Article  MathSciNet  MATH  Google Scholar 

  • Ott E (2002) Chaos in dynamical systems. Cambridge University Press, Cambridge

    Book  MATH  Google Scholar 

  • Panario D, Sahin M, Wang Q, Webb W (2014) General conditional recurrences. Appl Math Comput 243:220–231

    MathSciNet  MATH  Google Scholar 

  • Ragulskis M, Navickas Z (2011) The rank of a sequence as an indicator of chaos in discrete nonlinear dynamical systems. Commun Nonlinear Sci Numer Simul 16(7):2894–2906

    Article  MathSciNet  MATH  Google Scholar 

  • Ribenboim P, Walsh G (1999) The abc conjecture and the powerful part of terms in binary recurring sequences. J Number Theory 74(1):134–147

    Article  MathSciNet  MATH  Google Scholar 

  • Riordan J (1968) Combinatorial identities. Wiley, Amsterdam

    MATH  Google Scholar 

  • Singh S, Al-Zaid H (1991) On a canonical form for recurring sequences. Linear Algebra Appl 157:185–194

    Article  MathSciNet  MATH  Google Scholar 

  • Tam TY (1997) On the behavior of a sequence defined by a periodic recursive relation. SIAM J Matrix Anal Appl 18(4):842–860

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

This research was funded by a Grant (No. MIP078/15) from the Research Council of Lithuania.

Author information

Authors and Affiliations

  1. Department of Mathematical Modeling, Kaunas University of Technology, Studentu 50-325, Kaunas, Lithuania

    Zenonas Navickas

  2. Research Group for Mathematical and Numerical Analysis of Dynamical Systems, Kaunas University of Technology, Studentu 50-147, Kaunas, Lithuania

    Minvydas Ragulskis & Tadas Telksnys

  3. Department of Applied Mathematics, Kaunas University of Technology, Studentu 50-325, Kaunas, Lithuania

    Dovile Karaliene

Authors
  1. Zenonas Navickas
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Minvydas Ragulskis
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Dovile Karaliene
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Tadas Telksnys
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tadas Telksnys.

Additional information

Communicated by Jose Alberto Cuminato.

Appendices

Appendix A: Proof of Theorem 1

The definition of the determinant using combinatorial transposition reads [Bernstein (2009), p. 103]

$$\begin{aligned} \det A := \sum _{\left( k_1,\dots ,k_m\right) } (-1)^{\gamma \left( k_1,\dots ,k_m\right) } \prod _{r = 1}^{m} A_{r, k_r}, \end{aligned}$$
(99)

where \(\left( k_{1},\dots ,k_{m}\right) \) is a permutation of the set \(\left\{ 1,\dots ,m\right\} \); \(\gamma \left( k_{1},\dots ,k_{m}\right) \) is the number of transpositions in the permutation \(\left( k_{1},\dots ,k_{m}\right) \) and \(A_{r, k_r}\) is the \((r, k_r)\)-th entry of the \(m\)-th order matrix \(A\).

The determinant property [Bernstein (2009), p. 104] \(\det \left( A + v e_k^T\right) = \det A + \det A^{(k)}\), where \(v \in {\mathbb {C}}^{m}\); \(e_k \in {\mathbb {C}}^m\) is a unit vector with all elements except the \(k\)-th equal to zero; \(A^{(k)}\) is the matrix \(A\) with the \(k\)-th column replaced by \(v\) and (51) yield

$$\begin{aligned} \begin{aligned} d_{m}^{(j)}&= \sum _{\left( k_{1},\dots ,k_{m}\right) } \left( \prod _{l = 1}^{m} \mu _l \lambda _l^j\right) \left| \begin{array}{ccccc} {1} &{}\quad {\lambda _{k_{1} }^{} } &{}\quad {\lambda _{k_{1} }^{2} } &{}\quad {\dots } &{}\quad {\lambda _{k_{1} }^{m-1} }\\ {\lambda _{k_{2} }^{} } &{}\quad {\lambda _{k_{2} }^{2} } &{}\quad {\lambda _{k_{2} }^{3} } &{}\quad {\dots } &{}\quad {\lambda _{k_{2} }^{m}} \\ {\vdots } &{}\quad {\vdots } &{}\quad {\vdots } &{}\quad {\ddots } &{}\quad {\vdots } \\ {\lambda _{k_{m} }^{m-1} } &{}\quad {\lambda _{k_{m} }^{m} } &{}\quad {\lambda _{k_{m} }^{m+1} } &{}\quad {\dots } &{}\quad {\lambda _{k_{m} }^{2m-2} } \end{array}\right| \\&= \left( \prod _{l = 1}^{m} \mu _l \lambda _l^j\right) \sum _{\left( k_{1} ,k_{2} ,\ldots ,k_{m}\right) } \left( -1\right) ^{\gamma \left( k_1,\dots ,k_m\right) } V_m\left( \lambda _1,\dots ,\lambda _m\right) \prod _{r = 1}^{m} \lambda _{k_r}^{r-1} \\&= \left( V_m\left( \lambda _1,\dots ,\lambda _m\right) \right) ^2 \prod _{l = 1}^{m} \mu _l \lambda _l^j, \end{aligned} \end{aligned}$$
(100)

because (99) yields

$$\begin{aligned} V_m\left( \lambda _1,\dots ,\lambda _m\right) = \sum _{\left( k_{1} ,k_{2} ,\ldots ,k_{m}\right) } \left( -1\right) ^{\gamma \left( k_1,\dots ,k_m\right) } \prod _{r = 1}^{m} \lambda _{k_r}^{r-1}. \end{aligned}$$
(101)

Analogous rearrangements let us prove that

$$\begin{aligned} d_{j}^{(m+1)} = 0, \quad j\in {\mathbb {Z}}. \end{aligned}$$
(102)

Therefore, (50) holds true. On the other hand, it is clear that \(a_{j}^{(m)} \left( \rho \right) =0,\) when \(\rho \) is replaced by \(\lambda _{k} \): \(a_{j}^{(m)} \left( \lambda _{k} \right) =0,\) \(k=1,\dots ,m.\) Thus, (52) holds true.

Appendix B: Computation of the limits of Vandermonde determinants

Suppose a matrix \(A(x) = \left[ a_{kl}(x)\right] _{k,l = 1}^{m}\) is given. The first derivative of the determinant of \(A(x)\) is given by

$$\begin{aligned} \left( \det A(x)\right) '_x = {\varvec{}}{\mathrm {D}}_x \left| a_{kl}(x) \right| _{k,l = 1}^{m} = \sum _{j = 0}^{m} \left| {\varvec{}}{\mathrm {D}}_x^{\delta _{jk}} a_{kl}(x)\right| _{k,l = 1}^{m} = \sum _{j = 0}^{m} \left| {\varvec{}}{\mathrm {D}}_x^{\delta _{jl}} a_{kl}(x)\right| _{k,l = 1}^{m}, \end{aligned}$$
(103)

where \((D_x)\) is the differentiation operator with respect to \(x\), \((D_x^0 = 1)\) is the identity operator and

$$\begin{aligned} \delta _{jk} = {\left\{ \begin{array}{ll} 1, &{} j = k\\ 0, &{} j \ne k \end{array}\right. }, \quad j,k \in {\mathbb {N}}. \end{aligned}$$
(104)

Suppose the determinant defined by (58) is given

$$\begin{aligned} \overline{V}_{m}^{(j)} \left( \lambda _{1},\dots ,\lambda _{m} \right) = \left| v_{r+1,l}\left( \lambda _{1},\dots ,\lambda _{m} \right) \right| _{r,l = 0}^{m-1}, \end{aligned}$$
(105)

where

$$\begin{aligned} v_{r+1,l} = \lambda _{r+1}^{l}, \quad l = 0,\dots ,m-2; \, r = 0,\dots ,m-1; \quad v_{r+1,m-1} = \lambda _{r+1}^{j},\quad j \in {\mathbb {Z}}; \end{aligned}$$
(106)

and \(\lambda _k \in {\mathbb {C}}/\{0\} \, k = 1,\dots ,m\); \(\lambda _k \ne \lambda _l, \, k \ne l\).

Given \(\lambda _0 \ne 0\), the L’Hopital rule and (103) yield

$$\begin{aligned}&\lim _{\lambda _1,\dots ,\lambda _m \rightarrow \lambda _0} \frac{\overline{V}_{m}^{(j)} \left( \lambda _{1},\dots ,\lambda _{m} \right) }{V_m\left( \lambda _1,\dots ,\lambda _m\right) } = \lim _{\lambda _1,\dots ,\lambda _m \rightarrow \lambda _0} \frac{ {\begin{vmatrix} 1&\lambda _1&\dots&\lambda _1^{m-2}&\lambda _1^j\\ 1&\lambda _2&\dots&\lambda _2^{m-2}&\lambda _2^j\\ \vdots&\vdots&\ddots&\vdots&\vdots \\ 1&\lambda _m&\dots&\lambda _m^{m-2}&\lambda _m^j\\ \end{vmatrix}} }{ {\begin{vmatrix} 1&\lambda _1&\dots&\lambda _1^{m-1}\\ 1&\lambda _2&\dots&\lambda _2^{m-1}\\ \vdots&\vdots&\ddots&\vdots \\ 1&\lambda _m&\dots&\lambda _m^{m-1}\\ \end{vmatrix}} } \nonumber \\&\quad = \lim _{\lambda _1,\dots ,\lambda _m \rightarrow \lambda _0} \frac{ {\begin{vmatrix} 1&\lambda _1&\dots&\lambda _1^{m-2}&\lambda _1^j\\ {\varvec{}}{\mathrm {D}}_{\lambda _2}1&{\varvec{}}{\mathrm {D}}_{\lambda _2}\lambda _2&\dots&{\varvec{}}{\mathrm {D}}_{\lambda _2}\lambda _2^{m-2}&{\varvec{}}{\mathrm {D}}_{\lambda _2}\lambda _2^j\\ \vdots&\vdots&\ddots&\vdots&\vdots \\ {\varvec{}}{\mathrm {D}}^{m+1}_{\lambda _m}1&{\varvec{}}{\mathrm {D}}^{m+1}_{\lambda _m}\lambda _m&\dots&{\varvec{}}{\mathrm {D}}^{m+1}_{\lambda _m}\lambda _m^{m-2}&{\varvec{}}{\mathrm {D}}^{m+1}_{\lambda _m}\lambda _m^j\\ \end{vmatrix}} }{ {\begin{vmatrix} 1&\lambda _1&\dots&\lambda _1^{m-1}\\ {\varvec{}}{\mathrm {D}}_{\lambda _2}1&{\varvec{}}{\mathrm {D}}_{\lambda _2}\lambda _2&\dots&{\varvec{}}{\mathrm {D}}_{\lambda _2}\lambda _2^{m-1}\\ \vdots&\vdots&\ddots&\vdots \\ {\varvec{}}{\mathrm {D}}^{m+1}_{\lambda _m}1&{\varvec{}}{\mathrm {D}}^{m+1}_{\lambda _m}\lambda _m&\dots&{\varvec{}}{\mathrm {D}}^{m+1}_{\lambda _m}\lambda _m^{m-1}\\ \end{vmatrix}} } \nonumber \\&\quad =\frac{ {\begin{vmatrix} 1&\lambda _1&\dots&\lambda _0^{m-2}&\lambda _0^j\\ 0&1&\dots&(m-2) \lambda _0^{m-3}&j \lambda _0^{j-1}\\ \vdots&\vdots&\ddots&\vdots&\vdots \\ 0&0&\dots&0&j(j-1)(j-2)\dots (j-m+2) \lambda _0^{j-m+1}\\ \end{vmatrix}} }{(m-1)!} = \left( {\begin{array}{c}j\\ m-1\end{array}}\right) \lambda _0^{j-m+1}.\qquad \end{aligned}$$
(107)

Appendix C: Proof of Theorem 3

Let us construct an algebraic progression with coefficients

$$\begin{aligned} \overline{p}_{j} \left( \lambda _{1} ,\dots ,\lambda _{m} \right) =\sum _{k=1}^{m}\nu _{k} \frac{\overline{V}_{k}^{(j)} \left( \lambda _{1} ,\dots ,\lambda _{k} \right) }{V_{k} \left( \lambda _{1} ,\dots ,\lambda _{k} \right) }, \end{aligned}$$
(108)

where \(m=2,3,\dots \) is fixed and \(\overline{V}_{1}^{(j)} \left( \lambda _{1}\right) :=\lambda _{1}\). Then (49) and (61) yield

$$\begin{aligned} \begin{aligned} \overline{p}_{j} \left( \lambda _{1} ,\dots ,\lambda _{m} \right)&= \sum _{k=1}^{m}\nu _{k} \sum _{l=1}^{k}\frac{1}{\displaystyle \prod _{\begin{array}{l} {r=1,\dots ,k} \\ {\mathrm{\; \; \; \; \; }r\ne l} \end{array}}\left( \lambda _{l} -\lambda _{r} \right) } \lambda _{l}^{j} \\&=\sum _{l=1}^{m}\left( \sum _{k=l}^{m}\frac{\nu _{k} }{\displaystyle \prod _{\begin{array}{l} {r=1,\dots ,k} \\ {\mathrm{\; \; \; \; \; }r\ne l}\end{array}}\left( \lambda _{l} -\lambda _{r} \right) } \right) \lambda _{l}^{j}. \end{aligned} \end{aligned}$$

The highest order nonzero Hankel determinant of this sequence reads

$$\begin{aligned} \overline{d}_{m}^{(j)} \left( \lambda _{1} ,\dots ,\lambda _{m} \right)= & {} \prod _{l=1}^{m}\left( \sum _{k=l}^{m}\frac{\mu _{k} }{\displaystyle \prod _{\begin{array}{l} {r=1,\dots ,k} \\ {\mathrm{\; \; \; \; \; \; }r\ne l} \end{array}}\left( \lambda _{l} -\lambda _{r} \right) } \right) V_{m}^{2}\left( \lambda _{1} ,\dots ,\lambda _{m}\right) \prod _{k = 1}^{m}\lambda _k^j \nonumber \\= & {} \frac{\displaystyle \prod _{l=1}^{m}\left( Q_{l} \left( \lambda _{1} ,\dots ,\lambda _{m} \right) +(-1)^{m-l}\mu _{m}\right) }{V_{m}^{2} \left( \lambda _{1} ,\dots ,\lambda _{m}\right) } V_{m}^{2}\left( \lambda _{1} ,\dots ,\lambda _{m}\right) \prod _{k = 1}^{m}\lambda _k^j \nonumber \\= & {} \prod _{l=1}^{m}\left( Q_{l} \left( \lambda _{1} ,\dots ,\lambda _{m} \right) +(-1)^{m-l} \mu _{m} \right) \prod _{k = 1}^{m}\lambda _k^j \ne 0, \end{aligned}$$
(109)

where \(Q_{l} \left( \lambda _{1} ,\dots ,\lambda _{m} \right) \) are polynomials of \(\lambda _{1} ,\dots ,\lambda _{m} \) satisfying equalities

$$\begin{aligned} \mathop {\lim }\limits _{\lambda _{1} ,\dots ,\lambda _{m} \rightarrow \rho _{0} } Q_{l} \left( \lambda _{1} ,\dots ,\lambda _{m} \right) =0, \quad l=1,\dots ,m-1; \end{aligned}$$
(110)

and

$$\begin{aligned} Q_{m} \left( \lambda _{1} ,\dots ,\lambda _{m}\right) =0. \end{aligned}$$
(111)

Also, determinants \(d_{m+n}^{(j)} \left( \lambda _{1} ,\dots ,\lambda _{m} \right) =0\) for \(n=1,2,\dots \) Therefore,

$$\begin{aligned} {\mathrm {Order}} \left( p_{j} \left( \lambda _{1} ,\dots ,\lambda _{m} \right) ; j\in {\mathbb {Z}}\right) =m. \end{aligned}$$
(112)

Let \(\rho _{0} \ne 0\). Then the following limit transitions hold true

$$\begin{aligned} \mathop {\lim }\limits _{\lambda _{1} ,\dots ,\lambda _{m} \rightarrow \rho _{0} } \overline{d}_{m}^{(j)} \left( \lambda _{1} ,\dots ,\lambda _{m} \right) =(-1)^{\left( {\begin{array}{c}m\\ 2\end{array}}\right) } \mu _{m}^{m} \rho _{0}^{mj} := d_{m}^{(j)} \left( \rho _0 \right) \ne 0; \end{aligned}$$
(113)
$$\begin{aligned} \mathop {\lim }\limits _{\lambda _{1} ,\dots ,\lambda _{m} \rightarrow \rho _{0} } \overline{d}_{m+n}^{(j)} \left( \lambda _{1} ,\dots ,\lambda _{m} \right) :=d_{m+n}^{(j)} \left( \rho _0 \right) =0, \quad n=1,2,\dots ; \end{aligned}$$
(114)
$$\begin{aligned} \mathop {\lim }\limits _{\lambda _{1} ,\dots ,\lambda _{m} \rightarrow \rho _{0} } \overline{p}_{j} \left( \lambda _{1} ,\dots ,\lambda _{m} \right) =\sum _{k=1}^{m}\mu _{k} \left( {\begin{array}{c}j\\ k-1\end{array}}\right) \rho _{0}^{j-k+1} :=p_{j} \left( \rho _0\right) . \end{aligned}$$
(115)

Thus,

$$\begin{aligned} {\mathrm {Order}} \left( p_{j} \left( \rho _{0}\right) ; \, j\in {\mathbb {Z}}\right) =m. \end{aligned}$$
(116)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Navickas, Z., Ragulskis, M., Karaliene, D. et al. Weak and strong orders of linear recurring sequences. Comp. Appl. Math. 37, 3539–3561 (2018). https://doi.org/10.1007/s40314-017-0532-z

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s40314-017-0532-z

Keywords

Mathematics Subject Classification

Search

Navigation