Timeline for The p-adic valuation of a linear recurrence
Current License: CC BY-SA 3.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 7, 2016 at 15:27 | vote | accept | CommunityBot | ||
| Sep 26, 2016 at 9:09 | |||||
| Jun 4, 2016 at 13:40 | answer | added | user40023 | timeline score: 3 | |
| Nov 1, 2015 at 20:15 | answer | added | Joe Silverman | timeline score: 6 | |
| Aug 19, 2015 at 10:34 | comment | added | user40023 | @VesselinDimitrov ...I would interested even in a more explicit description of $\phi(\log(\alpha^r / \beta^r - 1) - n/r)$, which corresponds to the case of Lucas sequences $W_0 = 0$ and $W_1 = 1$. | |
| Aug 19, 2015 at 10:27 | comment | added | user40023 | @VesselinDimitrov Thank you again for your explanation. Regarding the p-adic logarithms in Ward's Theorem 10.1 : Do you think that $\log(\alpha^r / \beta^r - 1)$ could be written in a more explicit form in terms of r, P, and Q ? I don't think so, but I am not so practical with logarithm of p-adic numbers. | |
| Aug 17, 2015 at 13:29 | comment | added | Vesselin Dimitrov | @Fry: Yes, I mean the $p$-adic Gelfond-Baker theorem, but it only applies to the $k = 2$ case. Actually you can see in Ward's Thm. 10.1 how, in that case, the question of $v_p(u_n)$ amounts to how close $p$-adically is $n$ to the $p$-adic logarithm of a certain algebraic integer (independent of $n$). This is a situation where Gelfond-Baker applies immediately. For higher order recurrences, Schmidt's Subspace theorem can be applied, but ineffectively. | |
| Aug 17, 2015 at 7:36 | comment | added | Vesselin Dimitrov | @JoeSilverman: I don't think so. I had only the 2-term recurrences in mind, in my comment relating to Ward's paper. Schmidt's Subspace theorem gives the ineffective estimate of course, but the effective one for higher order recurrences is a major open problem as far as I am aware (similarly to the problem about small sums of roots of unity). | |
| Aug 16, 2015 at 23:48 | comment | added | Joe Silverman | @VesselinDimitrov Linear forms in logs ($p$-adic version) should handle $c_1A^n+c_2B^n$, as you indicate. But will linear forms in logs really handle three terms? (They may, I don't know. But for archimedean estimates, I believe that there are effective results for 3 terms, but not for 4 terms.) | |
| Aug 16, 2015 at 16:24 | history | edited | user40023 | CC BY-SA 3.0 |
deleted 1 character in body
|
| Aug 16, 2015 at 14:39 | history | edited | user40023 | CC BY-SA 3.0 |
added 435 characters in body; edited tags
|
| Aug 16, 2015 at 14:27 | comment | added | user40023 | @VesselinDimitrov Thank you. I'm going to edit my post to include the observation that Ward's result is just a reformulation of the problem. I'll be grateful to you if you can tell me more about how Gelfond-Baker results get involved in $\upsilon_p(u_n)$ (maybe, do you mean p-adic version of Gelfond-Baker?) | |
| Aug 16, 2015 at 9:48 | comment | added | Vesselin Dimitrov | This is correct. With the normalization $5 \cdot 5^n - 2 \cdot 1^n$, the example I gave falls into Theorem 10.1 in Ward. But this is just a reformulation of the essential problem, in terms of how well can the $3$-adic integer $\nu$ in that theorem be $3$-adically approximated by a rational integer $n$. This is a quintessential problem in diophantine approximations, solved by the Gelfond-Baker results of logarithmic linear forms. | |
| Aug 16, 2015 at 8:44 | comment | added | user40023 | @VesselinDimitrov I didn't read all Ward's paper, and IMHO his exposition is not so clear, however he stated: "We solve completely here the problem of determining the value function [p-adic valuation] of any such recurrence (W); indeed we shall give specific formulas". Perharps, the problem is that his "formulas" depends on a p-adic number whose computation could be more difficult than the computation of $\upsilon_p(u_n)$ directly (??). See Theorem 10.1. | |
| Aug 16, 2015 at 7:15 | comment | added | Vesselin Dimitrov | In general, diophantine approximations (Schmidt's theorem) yield a good, but ineffective upper bound on the $p$-adic valuation of $u_n$. | |
| Aug 16, 2015 at 7:14 | comment | added | Vesselin Dimitrov | I do not think that Ward's paper treats a general two-term recurrence. For example, there is no formula for the $3$-adic valuation of $5^n-2$. Proving that $3^n \nmid 5^n-2$ for all $n > 1$ was once a well known problem whose solution required the $3$-adic variant of Gelfond's estimates on linear forms in two logarithms. | |
| Aug 15, 2015 at 22:53 | comment | added | Max Alekseyev | "Lifting the exponent" is also a result of this flavor (for $k=2$): s3.amazonaws.com/aops-cdn.artofproblemsolving.com/resources/… | |
| Aug 15, 2015 at 22:35 | comment | added | David Handelman | Surely this is susceptible to rewriting as $M^n u$ where $M$ is the companion matrix for $\lambda^k - \sum a_i \lambda^{k-i}$, and $u$ is any old start-up vector. The characteristic polynomial determines (modulo the start-up) the valuations (this takes some care), but can be done. | |
| Aug 15, 2015 at 17:37 | history | asked | user40023 | CC BY-SA 3.0 |