Timeline for Strange (or stupid) arithmetic derivation
Current License: CC BY-SA 3.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 19, 2013 at 19:00 | vote | accept | Daniel Soltész | ||
| Sep 23, 2013 at 1:50 | history | edited | user6976 | CC BY-SA 3.0 |
edited body
|
| Sep 22, 2013 at 13:56 | history | edited | user6976 | CC BY-SA 3.0 |
added 402 characters in body
|
| Sep 22, 2013 at 13:48 | comment | added | user6976 | @DanielSoltész: In fact you are right: if you want to bound the number of different elements in a chain, then $p>n^{2^n-1}$ is enough. I accidentally answered a harder question about bounding a precycle. A reasonable (still open) question would be whether the lengths of all cycles are bounded. | |
| Sep 22, 2013 at 13:34 | comment | added | Daniel Soltész | Allright i get it, you actualy make $p$ very large, to ensure that the pre-cycle is at least $n$ long, but since we don't know how long the iteration for $n$ goes, we can not use any bounds. My comment then applies only when you want to bound the length of the pre-cycle plus the cycle. | |
| Sep 22, 2013 at 13:13 | comment | added | user6976 | The difference is that you want to bound the number of different elements in a chain, that is the sum of the length of the pre-cycle and the length of the cycle. My answer shows that already the length of the pre-cycle is unbounded. As far as finding a concrete bound for $p$, I do not see how your definition helps. | |
| Sep 22, 2013 at 13:09 | comment | added | Daniel Soltész | @Mark Sapir But they are not equivalent when i'm trying to get a bound for $p$. | |
| Sep 22, 2013 at 12:42 | comment | added | user6976 | @DanielSoltész: These are equivalent definitions as far as your question is concerned. | |
| Sep 22, 2013 at 12:39 | comment | added | Daniel Soltész | @Mark Sapir Ah i get it now! You mean by {fall into a cycle in $k$ steps} that after $k$ steps you get to an integer $m$ which is part of some cycle. I mean by {fall into a cycle in $k$ steps} that the first $k-1$ elements are all different, but the $k$-th one is equal to some previous one. You think i shall clarify that in the original post? | |
| Sep 22, 2013 at 12:23 | comment | added | user6976 | @DanielSoltész: If I take that bound, it is not clear that in the chain for $A$, no numbers will be divisible by $p$. The exponents of primes may get very large, and you do not control their divisors. Since the exponents turn into factors after application of $f$, we have no control over the prime divisors in the chain for even a small $n$. So I do not think $n^{2^n-1}$ (or any concrete bound) is enough. | |
| Sep 22, 2013 at 12:17 | comment | added | Daniel Soltész | Note that you do not need $p$ to be bigger than the elements of the sequence, just relatively prime to all of them. Also by using $f(n)<n^2$ we can conclude that $a_{i+1}<a^2_in$ which leads to a linear recursion (in the exponents) yielding the bound: $a_n<n^{2^n−1}$ so $p>n^{2^n−1}$ will be enough. | |
| Sep 22, 2013 at 12:11 | comment | added | BS. | @MarkSapir : nice trick! | |
| Sep 22, 2013 at 11:50 | comment | added | user6976 | @BS: I changed the answer again. $n^n$ may not be enough but there is a bound anyway (although we may never know what it is). | |
| Sep 22, 2013 at 11:49 | history | edited | user6976 | CC BY-SA 3.0 |
added 66 characters in body
|
| Sep 22, 2013 at 11:36 | history | edited | user6976 | CC BY-SA 3.0 |
added 66 characters in body
|
| Sep 22, 2013 at 11:31 | comment | added | user6976 | I replaced $n^n$ by $n^{2^n}$. Hope it is enough. I first wanted to write simply $p\gg n$ (which is clearly enough for what I wrote). But @BS's comment is in fact relevant. One needs to prove also that the chain does never produces an extra power of $p$. I have to think about it. | |
| Sep 22, 2013 at 11:26 | history | edited | user6976 | CC BY-SA 3.0 |
added 4 characters in body
|
| Sep 22, 2013 at 8:58 | comment | added | Daniel Soltész | I don't see either how $p>n^n$ ensures that, but it can be done. You just consider the sequence without powers of $p$: $$1→n→f(n)(n−1)→f(f(n)(n−1))(n−2)→...$$ and you choose a prime greater than every element in it. Thank you Mark Sapir, for the elegant solution. (Also by observing $f(n)<n^2$ one could obtain a bound on $p$, but this isn't enough to prove that $n^n$ is enough.) | |
| Sep 22, 2013 at 7:14 | comment | added | BS. | How do you ensure that after the first $n$ steps the chain doesn't go back to some $f^k(p^n)$, $k<n$ ? | |
| Sep 22, 2013 at 5:29 | history | answered | user6976 | CC BY-SA 3.0 |