Talk:Constant-recursive sequence

Be more explicit about eventually-periodic case

Two possible improvements to this article:

• First, I think we should update the article to be clearer about the case of sequences like $1,0,0,0,\ldots$. This is allowed as a constant-recursive sequence according to the current text (see Eventually periodic sequences) but sections like Characterization in terms of exponential polynomials do not apply for such sequences.

• Second, the article should clearly place itself relative to linear difference equation. These are basically the same concept. I think the latter article is excluding the eventually-periodic case, though. And maybe we should here too... best idea would be to dig up a reference textbook and see how they define it.

Thoughts? Happy to make some of these changes when I get the chance. Caleb Stanford (talk) 19:00, 7 November 2021 (UTC)

Eventually periodic sequences can only be excluded artificially, since "$s(n+\ell )=s(n)$ for all $n\geq N$" is equivalent to "$s(n+N+\ell )=s(n+N)$ for all $n\geq 0$", which satisfies the definition of being constant-recursive. I agree it's worth discussing this in the article, as well as the fact that an "eventually constant-recursive" sequence is constant-recursive, for the same reason. The sequence $1,0,0,0,\dots$ is described by an exponential polynomial, namely $0^{n}$ since zero to the power of zero is $1$ when the exponent only takes on integer values. Eric Rowland (talk) 23:31, 7 November 2021 (UTC)

Thanks User:Eric Rowland, but how would you plan to represent $0,1,0,0,\ldots$ as an exponential polynomial -- since $0^{n-1}$ doesn't work? To exclude eventually-periodic sequences non-artificially, we just have to require that in the satisfied linear recurrence $s(n)=c_{1}s(n-1)+c_{2}s(n-2)+\dots +c_{d}s(n-d),$ $c_{d}\neq 0$. Caleb Stanford (talk) 23:41, 7 November 2021 (UTC)

Good point. I checked The Concrete Tetrahedron (by Kauers and Paule), and they do require $c_{d}\neq 0$. This is artificial from the perspective of generating series because then the characterization as rational series needs an extra requirement on the degree of the numerator. But on the other hand it does fix the characterization as exponential polynomials. Eric Rowland (talk) 00:47, 8 November 2021 (UTC)

Thanks for looking into another reference! My preference would then be to have $c_{d}\neq 0$. Three Two One other justifications for that criterion: (i) it allows the sequence to be uniquely extended in the negative direction as well, (ii) it's implied by the "alternate definition" under "Definition" in the article, namely "the set of sequences $\{s(n+r)_{n\geq 0}:r\geq 0\}$ is contained in a vector space whose dimension is finite." For $1,0,0,0,...$ we get the set of all finite-support sequences, which is infinite-dimensional. Caleb Stanford (talk) 01:06, 8 November 2021 (UTC)

I'm fine with requiring $c_{d}\neq 0$, if you want to make the change. I agree with your point (i). For your point (ii), if $s(n)_{n\geq 0}$ is the sequence $1,0,0,0,...$, then $s(n+1)_{n\geq 0}$ and all higher shifts are the zero sequence, right? In that case $\{s(n+r)_{n\geq 0}:r\geq 0\}$ is contained in the $1$-dimensional space of sequences of the form $a,0,0,0,...$. Eric Rowland (talk) 01:17, 8 November 2021 (UTC)

Oh you are right about (ii), my mistake. OK, thanks for the discussion. Caleb Stanford (talk) 01:33, 8 November 2021 (UTC)

Given that some definitions (see (ii) and the generating series definition) point to eventually-periodic sequences naturally being considered constant-recursive, I think I'm now somewhat inclined to allow $c_{d}=0$. Also, it leads to a more general definition, in terms of many of the results (e.g. closure properties). For now, I edited the article with some clarifications to the definition. Caleb Stanford (talk) 01:57, 8 November 2021 (UTC)

Hasse diagram

As currently defined, the set of order-$2$ sequences doesn't include the set of order-$1$ sequences, but the Hasse diagram implies that it does. The diagram can be fixed by writing "order $\leq 2$" and so on. Also, a vertical ellipsis might look nicer than a horizontal ellipsis for the omitted orders. Eric Rowland (talk) 17:33, 13 November 2021 (UTC)

Good points. Fixed now! Caleb Stanford (talk) 19:56, 13 November 2021 (UTC)

Rename and merges (November 2021)

Per consensus at WT:WPM#Linear recurrence relations and discussion here, I've renamed the article from constant-recursive sequence to the clearer linear recurrence with constant coefficients, and am adding merge suggestions from:

1. Recurrence relation#Solving homogeneous linear recurrence relations with constant coefficients

2. Linear difference equation

Next TODO in editing the page is to complete the merge from the above two articles. Feel free to discuss here. Caleb Stanford (talk) 03:24, 21 November 2021 (UTC)

I don't see good motivation for renaming the article. The entire article is about sequences, not recurrences. Eric Rowland (talk) 16:46, 21 November 2021 (UTC)

I agree and this was a problem when I was trying to update the article. But I didn't want to go against what people were telling me was the WP:Consensus. What do you suggest here? Maybe having two articles, this one for sequences, and one for methods of solving linear recurrences that this one can point to? Or merging the content in here and changing the name? At any rate, having 3 articles on the topic does seem wrong to me. Caleb Stanford (talk) 17:15, 21 November 2021 (UTC)

A possible proposal:

1. Name this article linear-recursive sequence (gives us the adjective form linear-recursive which the other names do not offer and is used extensively throughout the article)

2. Merge the other two articles into a separate linear recurrence with constant coefficients

@D.Lazard: --- Your input would also be valuable here. As Eric points out, the whole article is about sequences, not solving recurrences, so the new name does not fit. I am thinking that having 2 articles would therefore be best as above. Caleb Stanford (talk) 13:03, 22 November 2021 (UTC)

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 polynomial coefficients where $s(n+i)$ 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". 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. Caleb Stanford (talk) 17:34, 22 November 2021 (UTC)

 Done 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. 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? 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.) Caleb Stanford (talk) 19:11, 26 November 2021 (UTC)

To-do list from peer review (Jan 2022)

To do for B-class

1. 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 primary. The one thing that would improve the article most, in my opinion, is more secondary sources.

   • 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 {{sfn}} or {{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 Definition. That said, I don't think it's necessary.

2. The article is reasonably well-written.

   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.

3. The article reasonably covers the topic, and does not contain obvious omissions or inaccuracies.

   This one needs review from a subject-matter expert.

4. 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.

5. The article presents its content in an appropriately understandable way.

   I think the 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, it fails.

Done

Y The use of the notation $s(n)$ for an element of a sequence rather than the more common $s_{n}$ can confuse readers, especially given that most (all?) articles linked from this one use the common notation. I propose changing $s(n)$ to $s_{n}$ and $F(n)$ to $F_{n}$.

Y The article has a defined structure.

Y The term "closed under" is used in the article without being wikilinked. Consider linking it in every section where it appears (the lead, In terms of vector spaces and Closure properties).

Y The phrase "note that" is used in the article twice. Per MOS:NOTE, it should be removed.

Y In 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 $c_{d}\neq 0$, which incidentally disallows such sequences). I think this sentence and the next one could use a rewrite.

Y Speaking of which, the citations in 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.

Y I've never seen the notation $s(n)_{n\geq 0}$ before, it should be replaced by a more common notation such as $(s(n))_{n=0}^{\infty }$, or better yet, $(s_{n})_{n=0}^{\infty }$ (which mirrors the one used in the Sequence article). $(s_{n})_{n\in \mathbb {N} }$ is alright as long as you explain that $\mathbb {N}$ includes zero.

Y In the table in Closure properties, why is "Generating Function Equivalent" in title case?

Y In Decision problems, "see closure properties" should be linked.

Discussion

Post any comments below. Caleb Stanford (talk) 18:03, 18 January 2022 (UTC)

I disagree that $s_{n}$ is preferable to $s(n)$. The OEIS — the definitive site for sequences on the internet — consistently uses $s(n)$, not subscripts (see https://oeis.org/A000045 for example). Also, sequences are functions, so $s(n)$ 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. 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 $s_{n}$ 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 $a_{0}+a_{1}x+a_{2}x^{2}$ as $a(0)+a(1)x+a(2)x^{2}$, but I don't think that would be helpful. 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 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 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 uses LaTeX. I don't think we can regard it as a definitive guide for notation.
• From my personal experience, people without 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.

Eric Rowland, does this address your objections? Streded (talk) 04:10, 27 January 2022 (UTC)