Deprecated: $wgMWOAuthSharedUserIDs=false is deprecated, set $wgMWOAuthSharedUserIDs=true, $wgMWOAuthSharedUserSource='local' instead [Called from MediaWiki\HookContainer\HookContainer::run in /var/www/html/w/includes/HookContainer/HookContainer.php at line 135] in /var/www/html/w/includes/Debug/MWDebug.php on line 372
A remark about the positivity problem problem of fourth order linear recurrence sequences - MaRDI portal

A remark about the positivity problem problem of fourth order linear recurrence sequences (Q2875913)

From MaRDI portal





scientific article; zbMATH DE number 6329414
Language Label Description Also known as
English
A remark about the positivity problem problem of fourth order linear recurrence sequences
scientific article; zbMATH DE number 6329414

    Statements

    12 August 2014
    0 references
    positivity problem
    0 references
    recurrence sequences
    0 references
    decidability
    0 references
    A remark about the positivity problem problem of fourth order linear recurrence sequences (English)
    0 references
    From the text: Consider a fourth order linear recurrence with integer coefficients whose characteristic polynomial has two distinct real and a complex conjugate pair of roots. A new proof showing that its Positivity Problem is decidable is given for the case where there is exactly one real root having the same absolute value as the two complex conjugate roots.NEWLINENEWLINEThe Positivity Problem for sequences satisfying a second order linear recurrence relation was shown to be decidable by \textit{V. Halava, T. Harju} and \textit{M. Hirvensalo} [Discrete Appl. Math. 154, No. 3, 447--451 (2006; Zbl 1158.11305)]. The Positivity Problem for sequences satisfying third and fourth order linear recurrences was shown to be decidable in [the authors, Discrete Appl. Math. 157, No. 15, 3239--3248 (2009; Zbl 1209.11020)], [the authors and N. Punnim, Colloq. Math. 128, No. 1, 133--142 (2012; Zbl 1284.11023), East-West J. Math. 14, No. 2, 185--200 (2012; Zbl 1307.11021)], respectively, see also [\textit{J. Ouaknine} and \textit{J. Worrell}, (*) Reachability problems -- RP 2012, Lect. Notes Comput. Sci. 7550, 21--28 (2012; Zbl 1298.11015), (**) Positivity Problem for low-order linear recurrence sequences. In: Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Philadelphia, PA: SIAM); New York, NY: ACM, 366--379 (2014), see Zbl 1287.68005]. As pointed out by Professor J. Ouaknine in a private communication, there is a gap in the proof of Claim 2 on page 141 of [(*)]. Our objective here is to repair this gap and a few loose arguments by giving a new proof, supplementing the works in [(*), (**)],
    0 references

    Identifiers