Talk:Skolem–Mahler–Lech theorem

Clarification of theorem statement needed

I'm being pedantic (see my comments at Talk:Constant-recursive sequence and Talk:Linear difference equation also), but the statement that the union of arithmetic progressions is full is not true for eventually-periodic sequences: for example $1,0,0,0,\ldots$, which satisfies $u_{0}=1,u_{1}=0,$ and $u_{n+2}=u_{n+1}+0u_{n}$. I've been trying to figure out if most of the literature is allowing such sequences. I think we really don't want to allow them, but some authors seem to have forgotten to exclude them:

• Terry Tao's blog post technically allows such cases (see definition: it does not specify that $a_{d}\neq 0$ and the recurrence only has to hold for $n\geq d$).

• The paper Decision Problems for Linear Recurrence Sequences, Oaknine and Worrell 2012 makes the same omission (mistake?) in the definition of LRS in the first paragraph.

• Further confusing matters is that the wiki page Constant-recursive sequence explicitly states that all eventually-periodic sequences are constant-recursive.

Any objections to update all these pages to be consistent and disallow sequences like $1,0,0,0,\ldots$, and briefly comment on this where appropriate? Caleb Stanford (talk) 19:18, 7 November 2021 (UTC)

I would rather replace "union of a finite set and finitely many full arithmetic progressions" with "symmetric difference of a finite set and finitely many full arithmetic progressions" than weaken the definition of eventually-periodic. —David Eppstein (talk) 19:50, 7 November 2021 (UTC)

I would be happy with that change as well. Though I note, the LRS literature appears to be implicitly disallowing eventually-periodic sequences like $1,0,0,0,\ldots$. Note that the explicit formula (sum of powers of the characteristic polynomial roots) doesn't apply for such sequences. Caleb Stanford (talk) 22:25, 7 November 2021 (UTC)

@Caleb Stanford and David Eppstein: The new statement is rather ambiguous: as said, it seems that the symmetric difference applies to the full arithmetic progressions as well. I don't think it should, i.e. I think that it should say "symmetric difference of a finite set and the union of finitely many full arithmetic progressions". But isn't it equivalent to the simpler "union of a finite set and finitely many arithmetic progressions" (i.e. removing the "full" from the initial statement)? And with this statement, if additionally $c_{d}\neq 0$, then the arithmetic progressions would be full. — Vincent Lefèvre (talk) 09:35, 22 September 2022 (UTC)

Or perhaps focus on the case $c_{d}\neq 0$. If $c_{d}=0$, one can apply the theorem to the largest $d'$ such that $c_{d'}\neq 0$ and eliminate the first $d-d'$ terms of the sequence to be in the conditions of the general case. This allows a stronger result (i.e., the only possible exceptions are among the first $d-d'$ terms). BTW, what does the theorem say exactly? — Vincent Lefèvre (talk) 10:28, 22 September 2022 (UTC)

Thanks! I edited the statement based on your suggestion. Caleb Stanford (talk) 17:50, 22 September 2022 (UTC)

@Caleb Stanford: In "then we may additionally require that the arithmetic progressions [...]", wouldn't "assert", "state" or "claim" be better than "require"? This is not a requirement, but an additional property that can be deduced. — Vincent Lefèvre (talk) 21:29, 22 September 2022 (UTC)

it's an additional requirement on the arithmetic progressions that can be added to the theorem statement. "Assert," "state" or "claim" makes it sound like the arithmetic progressions referenced earlier must necessarily be full (which is not true). "assume" would be better imo but I'll just reword it entirely. Caleb Stanford (talk) 00:14, 23 September 2022 (UTC)

A requirement is something that is in the hypotheses of the theorem. Here, this is not an hypothesis, but a consequence, i.e. with the additional condition $c_{d'}\neq 0$, the arithmetic progressions are necessarily full; so "assert", "state" or "claim" should be OK. "Assume" is something one says for the hypotheses; I would not use it for a consequence. — Vincent Lefèvre (talk) 00:48, 24 September 2022 (UTC)

It's not a consequence, but a requirement on the consequent inside an existential. $h\to \exists x.(c\land {\text{added condition}})$ rather than just $h\to c\land {\text{added condition}}$. It is not valid to add this condition as a consequence. It's only valid as an additional requirement inside the existential. Caleb Stanford (talk) 04:00, 24 September 2022 (UTC)

This statement you made is false: "with the additional condition $c_{d'}\neq 0$, the arithmetic progressions are necessarily full."

They are not necessarily full; but they may additionally be assumed to be full without invalidating the theorem. Caleb Stanford (talk) 04:03, 24 September 2022 (UTC)

OK, I see. So it would be interesting to give an example with $c_{d'}\neq 0$ where there is an arithmetic progression that isn't full. This is not obvious. — Vincent Lefèvre (talk) 17:03, 24 September 2022 (UTC)

Actually, I think that "with the additional condition $c_{d'}\neq 0$, the arithmetic progressions are necessarily full." was correct. — Vincent Lefèvre (talk) 18:15, 24 September 2022 (UTC)

I don't think we're getting anywhere in this disagreement. What I'm saying is, e.g.: in the Fibonacci section example, the set of zeros can be written as the union of the finite set $\{0,1\}$ and the (non-full) arithmetic progression $\{3,5,7,\ldots \}$. Stating that the arithmetic progression is necessarily full is therefore wrong. That's how I parse when you say "are necessarily full". Caleb Stanford (talk) 06:25, 25 September 2022 (UTC)