Timeline for How long iterations of $x \to (p \!\!\! \mod \!\! x)$ can be?
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 20, 2018 at 19:28 | comment | added | Kaban-5 | Let us continue this discussion in chat. | |
| Jul 20, 2018 at 19:16 | comment | added | Gerhard Paseman | OK. How about this: suppose for small r and c that p= rx + x-c, so d(x) is x-c, so p= r(x-c) + (x-c) + rc, so d(d(x)) = rc when rc is small enough that x is larger than (r+1)c . (Otherwise d(d(x)) is less than rc.) So " r shifts" after less than two iterations to a larger value of r for small r. For large r, it is not as clear. Further, it may be possible to show that r shifts by 1 or by small values only for log(p) many values of small r. Of course, something different is needed for large r. Gerhard "Time To Write Some More" Paseman, 2018.07.20. | |
| Jul 20, 2018 at 19:11 | comment | added | Kaban-5 | Answer to the last comment by you: I don't argue about "about half" statement, I agree. The problem is in the "about" part: as $H_k$ grow smaller, it becomes more difficult to ignore: even arbitrarily small segments in $[0, 1]$ notation may contain integers in $[1, p]$ notation. It is more or less the same problem as with $x \ll \sqrt{p}$: when $[\frac{p}{x}] = k \gg \sqrt{p}$, then corresponding segment, where $x$ lies in $(0, 1)$ notation is $(\frac{1}{k + 1}, \frac{1}{k})$ and has length $\approx pk^{-2} \ll 1$ in $[1, p]$ notation, but it does indeed contain an integer. | |
| Jul 20, 2018 at 19:02 | comment | added | Kaban-5 | Moreover, it should be noted that continuous version of the problem ($x_1 \in [0, 1], x_{k + 1} = 1 \!\!\! \mod \!\! x_k$ in a sense that $1 = qx_k + x_{k + 1}$ for some integer $q$ and $x_{k + 1} \in [0, x_k)$) can have $x_k$ decrease really slowly: $d ((\frac{1}{k + 1}, \frac{2}{2k + 1})) = (\frac{1}{2k + 1}, \frac{1}{k + 1}) \supset (\frac{1}{k + 2}, \frac{2}{2k + 3})$. Therefore it is possible that $x_k \in (\frac{1}{k + 1}, \frac{2}{2k + 1})$ for every $k$. So, figuring out why it is impossible in discrete version of the problem requires looking not only on high-level picture. | |
| Jul 20, 2018 at 18:49 | comment | added | Kaban-5 | Therefore it is hard to deal with possible case, when $H_{k - 1}$ has only one element in each $S_m$: we can't use any arguments like "elements from $H_{k - 1} \cap S_m$ run far from each other after applying $d$, so some of them miss $H$" or "$H_k \cap S_m$ can't have too many elements coming from $H_{k - 1} \cap S_r$ for every $r < m$ after applying $d$". Therefore such counting methods would have problems with disproving statements like "there are such $\alpha > 0, p, x_1$ that $[\frac{p}{x_k}] = k$ for each $k < p^{\alpha}$" . | |
| Jul 20, 2018 at 18:47 | comment | added | Gerhard Paseman | When x and y are small, it is indeed hard to understand relations between d(x) and d(y). When x and y are significantly larger than 2sqrt(p), that part of H is like a collection of intervals (1/k, 2/(2k-1)), and for H_2 (with x and d(x) both in H and both greater than say 2sqrt(p)) is a larger collection of smaller intervals which has about half the numbers above 2sqrt(p) that H has above 2sqrt(p). Below 2sqrt(p), I also don't understand H, but I suspect similar relations hold between H, H_2, and iterates of H. Gerhard "The Way Is Not Clear" Paseman, 2018.07.20. | |
| Jul 20, 2018 at 18:38 | comment | added | Kaban-5 | I thought about your suggestions quite a lot, but there seems to be a serious conceptual problem: proving that $H_k := \bigcap_{j = 0}^k d^j (H)$ is significantly smaller than $H_{k - 1}$ requires $H_{k - 1}$ being quite big by itself: for example, $H_{k - 1} \cap S_m$ being big enough at least for one $m$, where $S_m = (\frac{p}{m + 1}, \frac{2p}{2m + 1}) \cap \mathbb{N}$ (alternatively, $S_m = \{ x \in H : [\frac{p}{x}] = m \}$). Because it is hard to understand relations between $d(x)$ and $d(y)$, where $x \in S_a, y \in S_b$ and $a \not = b$. | |
| Jul 20, 2018 at 1:40 | comment | added | Gerhard Paseman | There are effects but it looks asymptotically like the size of H is more than twice the size of H_2 which eventually is more than twice the size of H_3 (as p grows, there are exceptions for small p), so the idea may be good after all if not as convenient. If I get a proof I will post it here. Gerhard "An Asymptotic Approach To Proof?" Paseman, 2018.07.19. | |
| Jul 19, 2018 at 14:56 | comment | added | Gerhard Paseman | Yes, the effects when x goes below sqrt(p) are considerable. I think it can be rescued to show that about log p steps above sqrt p suffice. (If not, then H_k is nonempty for k bigger than log p, which is at odds with H_k having half again as many members as k increases, but I don't have this rigorously.) Either that, or I am complicating your simple sqrt bound argument above. Gerhard "Thanks For Considering This Idea" Paseman, 2018.07.19. | |
| Jul 19, 2018 at 10:48 | comment | added | Kaban-5 | And I don't see how to get any bound significantly better than $2^{-k} p + k \log_2 p$ even if $|\bigcap_{i = 0}^k d^i (H)| \leqslant 2^{-k} |H|$ would hold, and minimum of this expression is of order $\log^2 p$. | |
| Jul 19, 2018 at 10:47 | comment | added | Kaban-5 | Hello. I tried to understand your answer and it seems that you more or less claim two things (let $d(1) := 1$ so $d$ is everywhere defined): $|\bigcap_{i = 0}^k d^i (H)| \leqslant 2^{-k} |H|$ and it implies that $n = O(\log p)$. First statement is almost true (up to factors that are negligible compared to $|H|$ for $k = 1$, I will call this "edge effects"), but I failed to see how it generalizes to bigger $k$. Computer says that "edge effects" grow stronger as $k$ grows: even $|\bigcap_{i = 0}^k d^i (H)| - 50$ is not less than $\leqslant 2^{-k} |H|$. | |
| Jul 19, 2018 at 6:41 | comment | added | Gerhard Paseman | It seems that H is not as nice as I hoped. It behaves as expected for x bigger than (some small multiple of) sqrt(p), but is less predictable for smaller x. The argument can be used to show that a number not far from sqrt(p) can be reached in O((log p)^2) steps, but more is needed to get to one. Gerhard "Square Root Seems Bigger Now" Paseman, 2018.07.18. | |
| Jul 18, 2018 at 20:39 | comment | added | Gerhard Paseman | Other than that d(x) is nonzero, I did not use profanity (primality, spellcheck!) anywhere. If you don't mind stopping at 0, you can use this argument for p not prime. If you do a literature search, you might consider the more general version. Gerhard "Maybe Easier Looking For Bigger" Paseman, 2018.07.18. | |
| Jul 18, 2018 at 20:15 | history | edited | Gerhard Paseman | CC BY-SA 4.0 |
added 5 characters in body
|
| Jul 18, 2018 at 19:59 | history | answered | Gerhard Paseman | CC BY-SA 4.0 |