# On Nearly Linear Recurrence Sequences

Ontology type: schema:Chapter      Open Access: True

### Chapter Info

DATE

2017-05-30

AUTHORS ABSTRACT

A nearly linear recurrence sequence (nlrs) is a complex sequence (an) with the property that there exist complex numbers A0,…, Ad−1 such that the sequence an+d+Ad−1an+d−1+⋯+A0ann=0∞\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\big(a_{n+d} + A_{d-1}a_{n+d-1} + \cdots + A_{0}a_{n}\big)_{n=0}^{\infty }$$ \end{document} is bounded. We give an asymptotic Binet-type formula for such sequences. We compare (an) with a natural linear recurrence sequence (lrs) (ãn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$(\tilde{a}_{n})$$ \end{document} associated with it and prove under certain assumptions that the difference sequence (an−ãn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$(a_{n} -\tilde{ a}_{n})$$ \end{document} tends to infinity. We show that several finiteness results for lrs, in particular the Skolem-Mahler-Lech theorem and results on common terms of two lrs, are not valid anymore for nlrs with integer terms. Our main tool in these investigations is an observation that lrs with transcendental terms may have large fluctuations, quite different from lrs with algebraic terms. On the other hand, we show under certain hypotheses that though there may be infinitely many of them, the common terms of two nlrs are very sparse. The proof of this result combines our Binet-type formula with a Baker type estimate for logarithmic forms. More... »

PAGES

1-24

### Book

TITLE

Number Theory – Diophantine Problems, Uniform Distribution and Applications

ISBN

978-3-319-55356-6
978-3-319-55357-3

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-55357-3_1

DOI

http://dx.doi.org/10.1007/978-3-319-55357-3_1

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1085706155

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Computation Theory and Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Institute of Mathematics, University of Tsukuba, 1-1-1 Tennodai, 350-0006, Tsukuba, Ibaraki, Japan",
"id": "http://www.grid.ac/institutes/grid.20515.33",
"name": [
"Institute of Mathematics, University of Tsukuba, 1-1-1 Tennodai, 350-0006, Tsukuba, Ibaraki, Japan"
],
"type": "Organization"
},
"familyName": "Akiyama",
"givenName": "Shigeki",
"id": "sg:person.011153327405.03",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011153327405.03"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Mathematical Institute, Leiden University, P.O. Box 9512, 2300, RA Leiden, The Netherlands",
"id": "http://www.grid.ac/institutes/grid.5132.5",
"name": [
"Mathematical Institute, Leiden University, P.O. Box 9512, 2300, RA Leiden, The Netherlands"
],
"type": "Organization"
},
"familyName": "Evertse",
"givenName": "Jan-Hendrik",
"id": "sg:person.015165732215.42",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015165732215.42"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science, University of Debrecen, P.O. Box 12, H-4010, Debrecen, Hungary",
"id": "http://www.grid.ac/institutes/grid.7122.6",
"name": [
"Department of Computer Science, University of Debrecen, P.O. Box 12, H-4010, Debrecen, Hungary"
],
"type": "Organization"
},
"familyName": "Peth\u0151",
"givenName": "Attila",
"id": "sg:person.013334020373.46",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013334020373.46"
],
"type": "Person"
}
],
"datePublished": "2017-05-30",
"datePublishedReg": "2017-05-30",
"description": "A nearly linear recurrence sequence (nlrs) is a complex sequence (an) with the property that there exist complex numbers A0,\u2026, Ad\u22121 such that the sequence an+d+Ad\u22121an+d\u22121+\u22ef+A0ann=0\u221e\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$$\\big(a_{n+d} + A_{d-1}a_{n+d-1} + \\cdots + A_{0}a_{n}\\big)_{n=0}^{\\infty }$$\n\\end{document} is bounded. We give an asymptotic Binet-type formula for such sequences. We compare (an) with a natural linear recurrence sequence (lrs) (\u00e3n)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$$(\\tilde{a}_{n})$$\n\\end{document} associated with it and prove under certain assumptions that the difference sequence (an\u2212\u00e3n)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$$(a_{n} -\\tilde{ a}_{n})$$\n\\end{document} tends to infinity. We show that several finiteness results for lrs, in particular the Skolem-Mahler-Lech theorem and results on common terms of two lrs, are not valid anymore for nlrs with integer terms. Our main tool in these investigations is an observation that lrs with transcendental terms may have large fluctuations, quite different from lrs with algebraic terms. On the other hand, we show under certain hypotheses that though there may be infinitely many of them, the common terms of two nlrs are very sparse. The proof of this result combines our Binet-type formula with a Baker type estimate for logarithmic forms.",
"editor": [
{
"familyName": "Elsholtz",
"givenName": "Christian",
"type": "Person"
},
{
"familyName": "Grabner",
"givenName": "Peter",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-319-55357-3_1",
"inLanguage": "en",
"isAccessibleForFree": true,
"isPartOf": {
"isbn": [
"978-3-319-55356-6",
"978-3-319-55357-3"
],
"name": "Number Theory \u2013 Diophantine Problems, Uniform Distribution and Applications",
"type": "Book"
},
"keywords": [
"linear recurrence sequences",
"recurrence sequences",
"Skolem\u2013Mahler",
"Lech theorem",
"algebraic terms",
"finiteness results",
"transcendental terms",
"integer terms",
"type estimates",
"difference sequence",
"main tool",
"certain assumptions",
"certain hypotheses",
"logarithmic form",
"large fluctuations",
"formula",
"such sequences",
"theorem",
"infinity",
"terms",
"fluctuations",
"proof",
"assumption",
"complex sequence",
"A0",
"estimates",
"results",
"common terms",
"properties",
"sequence",
"LR",
"tool",
"form",
"observations",
"investigation",
"hand",
"hypothesis",
"NLR"
],
"name": "On Nearly Linear Recurrence Sequences",
"pagination": "1-24",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1085706155"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-319-55357-3_1"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-319-55357-3_1",
"https://app.dimensions.ai/details/publication/pub.1085706155"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-05-10T10:55",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_68.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-319-55357-3_1"
}
]

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-55357-3_1'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-55357-3_1'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-55357-3_1'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-55357-3_1'

This table displays all metadata directly associated to this object as RDF triples.

123 TRIPLES      23 PREDICATES      63 URIs      56 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-55357-3_1 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N004cae4016904b5db28ee7416f5f9363
4 schema:datePublished 2017-05-30
5 schema:datePublishedReg 2017-05-30
6 schema:description A nearly linear recurrence sequence (nlrs) is a complex sequence (an) with the property that there exist complex numbers A0,…, Ad−1 such that the sequence an+d+Ad−1an+d−1+⋯+A0ann=0∞\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\big(a_{n+d} + A_{d-1}a_{n+d-1} + \cdots + A_{0}a_{n}\big)_{n=0}^{\infty }$$ \end{document} is bounded. We give an asymptotic Binet-type formula for such sequences. We compare (an) with a natural linear recurrence sequence (lrs) (ãn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$(\tilde{a}_{n})$$ \end{document} associated with it and prove under certain assumptions that the difference sequence (an−ãn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$(a_{n} -\tilde{ a}_{n})$$ \end{document} tends to infinity. We show that several finiteness results for lrs, in particular the Skolem-Mahler-Lech theorem and results on common terms of two lrs, are not valid anymore for nlrs with integer terms. Our main tool in these investigations is an observation that lrs with transcendental terms may have large fluctuations, quite different from lrs with algebraic terms. On the other hand, we show under certain hypotheses that though there may be infinitely many of them, the common terms of two nlrs are very sparse. The proof of this result combines our Binet-type formula with a Baker type estimate for logarithmic forms.
7 schema:editor N9c4e089e15504736a8ae4c63645009c9
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N82e1e7ca58304dc5aaeabe0ac62f6c6b
12 schema:keywords A0
13 LR
14 Lech theorem
15 NLR
16 Skolem–Mahler
17 algebraic terms
18 assumption
19 certain assumptions
20 certain hypotheses
21 common terms
22 complex sequence
23 difference sequence
24 estimates
25 finiteness results
26 fluctuations
27 form
28 formula
29 hand
30 hypothesis
31 infinity
32 integer terms
33 investigation
34 large fluctuations
35 linear recurrence sequences
36 logarithmic form
37 main tool
38 observations
39 proof
40 properties
41 recurrence sequences
42 results
43 sequence
44 such sequences
45 terms
46 theorem
47 tool
48 transcendental terms
49 type estimates
50 schema:name On Nearly Linear Recurrence Sequences
51 schema:pagination 1-24
52 schema:productId N5e7c184dc40541b998f8f4cd4996e6bc
53 Nef271f005af842888e851355dff09a70
54 schema:publisher N1d01a9feefa64fb7816b1bb5188ff029
55 schema:sameAs https://app.dimensions.ai/details/publication/pub.1085706155
56 https://doi.org/10.1007/978-3-319-55357-3_1
57 schema:sdDatePublished 2022-05-10T10:55
59 schema:sdPublisher N27e998dd6a044fc7b58599bbe4cce5a0
60 schema:url https://doi.org/10.1007/978-3-319-55357-3_1
62 sgo:sdDataset chapters
63 rdf:type schema:Chapter
64 N004cae4016904b5db28ee7416f5f9363 rdf:first sg:person.011153327405.03
65 rdf:rest N5fd8447bff0f45cfb906725818c2ca57
66 N1d01a9feefa64fb7816b1bb5188ff029 schema:name Springer Nature
67 rdf:type schema:Organisation
68 N2096c17894fc49e798a54644628bfc16 rdf:first sg:person.013334020373.46
69 rdf:rest rdf:nil
70 N27e998dd6a044fc7b58599bbe4cce5a0 schema:name Springer Nature - SN SciGraph project
71 rdf:type schema:Organization
72 N4d2710da487d404ba53290f24ecd3803 schema:familyName Elsholtz
73 schema:givenName Christian
74 rdf:type schema:Person
75 N5e7c184dc40541b998f8f4cd4996e6bc schema:name doi
76 schema:value 10.1007/978-3-319-55357-3_1
77 rdf:type schema:PropertyValue
78 N5fd8447bff0f45cfb906725818c2ca57 rdf:first sg:person.015165732215.42
79 rdf:rest N2096c17894fc49e798a54644628bfc16
80 N82e1e7ca58304dc5aaeabe0ac62f6c6b schema:isbn 978-3-319-55356-6
81 978-3-319-55357-3
82 schema:name Number Theory – Diophantine Problems, Uniform Distribution and Applications
83 rdf:type schema:Book
84 N85d60728a9f044638e32593f4d6c5c7f schema:familyName Grabner
85 schema:givenName Peter
86 rdf:type schema:Person
87 N8c470964cfd44cfdba1f91428e4ea0b7 rdf:first N85d60728a9f044638e32593f4d6c5c7f
88 rdf:rest rdf:nil
89 N9c4e089e15504736a8ae4c63645009c9 rdf:first N4d2710da487d404ba53290f24ecd3803
90 rdf:rest N8c470964cfd44cfdba1f91428e4ea0b7
91 Nef271f005af842888e851355dff09a70 schema:name dimensions_id
92 schema:value pub.1085706155
93 rdf:type schema:PropertyValue
94 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
95 schema:name Information and Computing Sciences
96 rdf:type schema:DefinedTerm
97 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
98 schema:name Computation Theory and Mathematics
99 rdf:type schema:DefinedTerm
100 sg:person.011153327405.03 schema:affiliation grid-institutes:grid.20515.33
101 schema:familyName Akiyama
102 schema:givenName Shigeki
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011153327405.03
104 rdf:type schema:Person
105 sg:person.013334020373.46 schema:affiliation grid-institutes:grid.7122.6
106 schema:familyName Pethő
107 schema:givenName Attila
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013334020373.46
109 rdf:type schema:Person
110 sg:person.015165732215.42 schema:affiliation grid-institutes:grid.5132.5
111 schema:familyName Evertse
112 schema:givenName Jan-Hendrik
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015165732215.42
114 rdf:type schema:Person
115 grid-institutes:grid.20515.33 schema:alternateName Institute of Mathematics, University of Tsukuba, 1-1-1 Tennodai, 350-0006, Tsukuba, Ibaraki, Japan
116 schema:name Institute of Mathematics, University of Tsukuba, 1-1-1 Tennodai, 350-0006, Tsukuba, Ibaraki, Japan
117 rdf:type schema:Organization
118 grid-institutes:grid.5132.5 schema:alternateName Mathematical Institute, Leiden University, P.O. Box 9512, 2300, RA Leiden, The Netherlands
119 schema:name Mathematical Institute, Leiden University, P.O. Box 9512, 2300, RA Leiden, The Netherlands
120 rdf:type schema:Organization
121 grid-institutes:grid.7122.6 schema:alternateName Department of Computer Science, University of Debrecen, P.O. Box 12, H-4010, Debrecen, Hungary
122 schema:name Department of Computer Science, University of Debrecen, P.O. Box 12, H-4010, Debrecen, Hungary
123 rdf:type schema:Organization

Preview window. Press ESC to close (or click here)

...