Talk:Constant-recursive sequence: Difference between revisions

Content deleted Content added
 
(36 intermediate revisions by 9 users not shown)
Line 1:
{{FailedGA|16:34, 18 April 2024 (UTC)|topic=Mathematics and mathematicians|page=1|oldid=1219582549}}
{{Peer review|archive=1|topic=natsci}}
{{WikiProject banner shell|class=C|
{{maths rating| class=C| priority = mid| field= Discrete}}
{{WikiProject Computer scienceMathematics|class priority =C|importance=low mid}}
{{WikiProject Computer science|importance=low}}
}}
{{Old peer review|ID=1070410909|reviewedname=Constant-recursive sequence|date=1 March 2022|archive=2}}
{{Old peer review|ID=1059493640|reviewedname=Constant-recursive sequence|date=19 December 2021|archive=1}}
 
== Be more explicit about eventually-periodic case ==
Line 58 ⟶ 62:
I agree that 3 articles is a lot, but these objects are so common that they occur in lots of different areas, so different people have quite different ways of thinking about them and different aspects they are interested in. A similar situation exists with [[P-recursive equation]], [[Polynomial solutions of P-recursive equations]], [[Holonomic function]], and [[Linear differential equation]] (though in this case hopefully we can reduce the number of articles). [[Linear difference equation]] seems to be focused on models and stability, which is different than what combinatorists and computer scientists might be interested in. I propose leaving it as its own article and trying to avoid too much duplication where it makes sense. Most of the material under [[Recurrence relation#Solving homogeneous linear recurrence relations with constant coefficients]] could be merged into one of the other two articles since [[Recurrence relation]] is quite long.
 
As for terminology, the reasoning "'''linear-recursive''' is used extensively throughout the article" applies equally well to '''constant-recursive''' because all instances of "constant-recursive" were replaced with "linear-recursive" when the title was changed. So I still don't see good motivation for the recent renaming. The unfortunate fact is that there is no one established name for these sequences. "linear-recursive" is not great because it doesn't distinguish between recurrences with constant coefficients and recurrences with polynomialspolynomial coefficients where <math>s(n + i)</math> also appear linearly. "constant-recursive"/"C-recursive"/"C-finite" are used less widely but have the advantages that they make this distinction and they parallel "polynomial-recursive"/"P-recursive". [[User:Eric Rowland|Eric Rowland]] ([[User talk:Eric Rowland|talk]]) 16:37, 22 November 2021 (UTC)
 
: I am fine with reverting back to the terminology '''constant-recursive''' based on your argument, and merging [[Recurrence relation#Solving homogeneous linear recurrence relations with constant coefficients]] into [[Linear difference equation]]. I still favor renaming [[Linear difference equation]] to [[Linear recurrence with constant coefficients]]. Waiting for further discussion in case D.Lazard wants to chime in, otherwise I will go ahead and take this direction in a couple of days. [[User:Caleb Stanford|Caleb Stanford]] ([[User talk:Caleb Stanford|talk]]) 17:34, 22 November 2021 (UTC)
 
::{{done}} [[User:Caleb Stanford|Caleb Stanford]] ([[User talk:Caleb Stanford|talk]]) 16:54, 25 November 2021 (UTC)
 
== Missing from current article: discussion of integer/rational/algebraic/real/complex ==
 
If D is a subset of complex numbers, there are two possible definitions for a constant-recursive sequence over D:
 
- (Stronger def) A sequence satisfying a linear recurrence with coefficients in D
- (Weaker def) A sequence satisfying a linear recurrence with complex coefficients, such that all numbers in the sequence happen to lie in D
 
So we should probably clarify this, and state if/under what conditions the two definitions are equivalent. [[User:Caleb Stanford|Caleb Stanford]] ([[User talk:Caleb Stanford|talk]]) 21:02, 25 November 2021 (UTC)
 
: This would be good, although I'm not sure much is known. Do you know a reference? [[User:Eric Rowland|Eric Rowland]] ([[User talk:Eric Rowland|talk]]) 17:42, 26 November 2021 (UTC)
 
:: I think it is well-known at least for integers, rational, algebraic, and real numbers. I will do some digging for a reference sometime. (A few other additions to the articles need good references too, mainly the closure properties.) [[User:Caleb Stanford|Caleb Stanford]] ([[User talk:Caleb Stanford|talk]]) 19:11, 26 November 2021 (UTC)
 
== To-do list from [[Wikipedia:Peer review/Constant-recursive sequence/archive2|peer review]] (Jan 2022) ==
 
=== To do for [[Wikipedia:Content assessment/B-Class criteria|B-class]] ===
 
=== Skipped ===
:{{Yellow tick}} "The article reasonably covers the topic, and does not contain obvious omissions or inaccuracies." This one needs review from a subject-matter expert.
:{{Yellow tick}} "The article contains supporting materials where appropriate." I think a video illustrating the concept would be helpful, but the article ought to pass this criterion even without one.
 
=== Done ===
 
:{{tick}} Pass to improve inline citations
:: "The article is suitably referenced, with inline citations." I think this is the weak point of the article, and indeed of many Wikipedia articles about mathematical concepts. Not only are there important uncited statements in the article (although many of them can be verified by readers with sufficient mathematical background), as far as I can tell, all sources cited in the article are [[wp:primary|primary]]. The one thing that would improve the article most, in my opinion, is more [[wp:secondary source|secondary source]]s.
::* Every citation should have an exact page if possible, a page range should only be used if the claim(s) cited cannot be verified by reading any single page (and even then it should be as short as possible). I haven't checked whether the article complies with this, I just wanted to mention that. I see that the ''Reachability Problems'' source is used several times, you can provide a separate page number for each of them by using {{tl|sfn}} or {{tl|r}} but given that the page range isn't long it may be more trouble that it's worth.
::* It would be ideal if there were a source for every definition and every example, to verify that they are notable and therefore relevant to the article. Of particular interest would be a source for the fact that every eventually periodic sequence is constant-recursive, given that it causes a minor headache in [[Constant-recursive sequence#Definition|Definition]]. That said, I don't think it's necessary.
:{{tick}} Pass to improve the writing and make more accessible.
:* The prose is generally good, but it feels too textbook-like to me. Aside from the lead, the article uses a distinctive writing style that is more characteristic of a math textbook than of an encyclopedia.
:* "The article presents its content in an appropriately understandable way." I think the [[wp:write one level down|write one level down]] rule is the best way to assess this, but I don't know at which level this subject is typically studied. If [[graduate school]], I'd say it passes. If [[undergraduate education#United States system|undergraduate]], it fails.
:{{tick}} The use of the notation <math>s(n)</math> for an element of a sequence rather than the more common <math>s_n</math> can confuse readers, especially given that most (all?) articles linked from this one use the common notation. I propose changing <math>s(n)</math> to <math>s_n</math> and <math>F(n)</math> to <math>F_n</math>.
:{{tick}} The article has a defined structure.
:{{tick}} The term "closed under" is used in the article without being wikilinked. Consider linking it in every section where it appears (the lead, [[Constant-recursive sequence#In terms of vector spaces|In terms of vector spaces]] and [[Constant-recursive sequence#Closure properties|Closure properties]]).
:{{tick}} The phrase "note that" is used in the article twice. Per [[MOS:NOTE]], it should be removed.
:{{tick}} In [[Constant-recursive sequence#Definition|Definition]], the phrase "eventually-periodic sequences... which are disallowed by some authors" makes it sound like said authors explicitly disallow them, which is not the case (rather, they require that <math>c_d \ne 0</math>, which incidentally disallows such sequences). I think this sentence and the next one could use a rewrite.
:{{tick}} Speaking of which, the citations in [[Constant-recursive sequence#Definition|Definition]] don't have a page number. I believe it should be page 66 in ''The Concrete Tetrahedron'' and page 1 in ''Skolem's Problem''.
:{{tick}} I've never seen the notation <math>s(n)_{n \geq 0}</math> before, it should be replaced by a more common notation such as <math>(s(n))_{n=0}^\infty</math>, or better yet, <math>(s_n)_{n=0}^\infty</math> (which mirrors the one used in the [[Sequence]] article). <math>(s_n)_{n\in\mathbb N}</math> is alright as long as you explain that <math>\mathbb N</math> includes zero.
:{{tick}} In the table in [[Constant-recursive sequence#Closure properties|Closure properties]], why is "Generating Function Equivalent" in title case?
:{{tick}} In [[Constant-recursive sequence#Decision problems|Decision problems]], "see closure properties" should be linked.
 
=== Discussion ===
Post any comments below. [[User:Caleb Stanford|Caleb Stanford]] ([[User talk:Caleb Stanford|talk]]) 18:03, 18 January 2022 (UTC)
 
I disagree that <math>s_n</math> is preferable to <math>s(n)</math>. The OEIS — the definitive site for sequences on the internet — consistently uses <math>s(n)</math>, not subscripts (see https://oeis.org/A000045 for example). Also, sequences are functions, so <math>s(n)</math> is more appropriate and doesn't introduce extra notation. I don't see any possible cause of confusion. I think we should revert the recent change. [[User:Eric Rowland|Eric Rowland]] ([[User talk:Eric Rowland|talk]]) 00:21, 27 January 2022 (UTC)
 
:Hmm, we may need another opinion on this. I don't have a strong preference either way, but in my experience subscript notation <math>s_n</math> is more common. The page [[Sequence]] uses subscript notation. As for "sequences are functions", subscripts are functions too, set-theoretically. You could replace all subscript notation with functions but that wouldn't always be clarifying. For example, you could represent a quadratic polynomial <math>a_0 + a_1 x + a_2 x^2</math> as <math>a(0) + a(1) x + a(2) x^2</math>, but I don't think that would be helpful. [[User:Caleb Stanford|Caleb Stanford]] ([[User talk:Caleb Stanford|talk]]) 03:45, 27 January 2022 (UTC)
 
: This was my suggestion, so I should weigh in on this. I have suggested this change for the following reasons:
:* Like [[User:Caleb Stanford|Caleb Stanford]], the subscript notation is more common in my experience.
:* People who don't have much mathematical background (and even some people who do) typically think of sequences as a separate type of entity, not as functions whose ___domain is the natural numbers.
:* The sources of this article use the subscript notation.
:* As [[User:Caleb Stanford|Caleb Stanford]] noted, other Wikipedia articles use the subscript notation.
: As for your comments:
:* The OEIS displays mathematical content, including sequenes, in ASCII, while Wikipedia uses [[WP:LaTeX|uses LaTeX]]. I don't think we can regard it as a definitive guide for notation.
:* From my personal experience, people without [[wikt:postsecondary|postsecondary]] mathematical background don't know that sequences are functions or that they can be written using function notation. Per [[WP:MTAU]], such readers are part of our target audience to the greatest possible extent.
: [[User:Eric Rowland|Eric Rowland]], does this address your objections? [[User:Streded|Streded]] ([[User talk:Streded|talk]]) 04:10, 27 January 2022 (UTC)
 
== To-do list for [[Wikipedia:Good article criteria]] (June 2022) ==
 
Trying to bring this to GA status eventually. [[User:Caleb Stanford|Caleb Stanford]] ([[User talk:Caleb Stanford|talk]]) 22:32, 22 June 2022 (UTC)
 
=== Primary to-dos ===
 
*Improve inline citations further
:*We need a few more good textbook references to draw from.
::*Concrete Tetrahedron is a solid reference, but covers only about half of the material in the article (mostly the more elementary stuff). Also, because it doesn't allow eventually-periodic we should avoid relying on it too heavily for citing results.
::*I took a look at Concrete Mathematics but it doesn't cover most of the material in the article (in fact we could probably remove it from Further Reading).
::{{done}}
:*Probably some combinatorics and generating functions textbooks will cover the relevant material, that's where I will look first.
::{{done}} (added ref to Stanley)
:*We need references for every line in the Closure Properties table.
::{{done}} (added refs to Stanley)
:*Finally, a few statements in the lead still need references.
::{{not done}} per [[MOS:LEADCITE]]
 
=== GA criteria list ===
 
{| class="wikitable"
|0||{{Wikipedia:Good article criteria/GAC|0}}
|-
|0a||{{Wikipedia:Good article criteria/GAC|0a}}
|-
|0b||{{Wikipedia:Good article criteria/GAC|0b}}
|-
|0c||{{Wikipedia:Good article criteria/GAC|0c}}
|-
|0d||{{Wikipedia:Good article criteria/GAC|0d}}
|-
|0e||{{Wikipedia:Good article criteria/GAC|0e}}
|}
{| class="wikitable"
|1||{{Wikipedia:Good article criteria/GAC|1}}
|-
|1a||{{Wikipedia:Good article criteria/GAC|1a}}
|-
|1b||{{Wikipedia:Good article criteria/GAC|1b}}
|-
|2||{{Wikipedia:Good article criteria/GAC|2}}
|-
|2a||{{Wikipedia:Good article criteria/GAC|2a}}
|-
|2b||{{Wikipedia:Good article criteria/GAC|2b}}
|-
|2c||{{Wikipedia:Good article criteria/GAC|2c}}
|-
|2d||{{Wikipedia:Good article criteria/GAC|2d}}
|-
|3||{{Wikipedia:Good article criteria/GAC|3}}
|-
|3a||{{Wikipedia:Good article criteria/GAC|3a}}
|-
|3b||{{Wikipedia:Good article criteria/GAC|3b}}
|-
|4||{{Wikipedia:Good article criteria/GAC|4}}
|-
|5||{{Wikipedia:Good article criteria/GAC|5}}
|-
|6||{{Wikipedia:Good article criteria/GAC|6}}
|-
|6a||{{Wikipedia:Good article criteria/GAC|6a}}
|-
|6b||{{Wikipedia:Good article criteria/GAC|6b}}
|}
{{Talk:Constant-recursive sequence/GA1}}
 
== Degeneracy ==
 
{{ping|GaseousButter}} I corrected your edit as I think you meant "if k = 1" not "if n = 1", but let me know if I got the result wrong! [[User:Caleb Stanford|Caleb Stanford]] ([[User talk:Caleb Stanford|talk]]) 23:41, 1 July 2024 (UTC)
 
:Thank you - I was transcribing directly from the book but then changed the letters to match with the article - that n slipped through the cracks it seems! [[User:GaseousButter|GaseousButter]] ([[User talk:GaseousButter|talk]]) 13:37, 4 July 2024 (UTC)
 
== Skolem problem ==
 
"For example, the Skolem problem is decidable for sequences of order up to 4"
 
It would do to be more precise here - what is currently published in the literature is that the Skolem problem is decidable for algebraic sequences of order up to 3, and '''real''' algebraic sequences up to order 4. In fact, it is true that it is decidable for all algebraic sequences up to order 4 - I have a paper in the works about that so watch this space ;). But as of now what is written is a little ambiguous and potentially misleading. [[User:GaseousButter|GaseousButter]] ([[User talk:GaseousButter|talk]]) 13:48, 4 July 2024 (UTC)
 
:Thanks, I can fix this! From the source (Ouaknine and Worrell) I have: "Partial progress towards decidability of the Skolem Problem has been achieved by restricting the order of linear recurrence sequences. For sequences of order 1 and 2, decidability is relatively straightforward and considered to be folklore. Decidability for orders 3 and 4, however, had to wait until the 1980s before being independently settled positively by Mignotte, Shorey, and Tijdeman [13], as well as Vereshchagin"
:so I guess they are referring to real algebraic sequences? I can also check the original sources and add these. Or feel free to propose an edit. Thanks! [[User:Caleb Stanford|Caleb Stanford]] ([[User talk:Caleb Stanford|talk]]) 19:05, 6 July 2024 (UTC)
::Yes, in that source you cited the way they define a linear recurrence sequence is to be over the reals. I think the best thing to do is to cite the original sources (they're not the nicest things to read through being from the 80s). I might edit it myself in a bit but I was originally being lazy because I didn't want to figure out what the cleanest wording would be haha [[User:GaseousButter|GaseousButter]] ([[User talk:GaseousButter|talk]]) 19:02, 16 July 2024 (UTC)