Timeline for Fixed points of $x\mapsto 2^{2^{2^{2^x}}} \mod p$
Current License: CC BY-SA 3.0
39 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Jul 16, 2014 at 6:58 | history | bounty ended | CommunityBot | ||
| S Jul 16, 2014 at 6:58 | history | notice removed | CommunityBot | ||
| Jul 11, 2014 at 10:46 | comment | added | H A Helfgott | The point is that I should have been a bit more precise about the wording - I think most have understood the "right meaning" by now, but it is worth repeating. Sean Eberhard's reply below contains a clean formulation. | |
| Jul 11, 2014 at 3:47 | comment | added | Gottfried Helms | My first idea was to apply Euler's phi-/totient-function four times iteratively -and of course such an iteration reduces the set of residue-classes much. But the intensity of the discussion around suggests I'm badly missing some other aspect by your question. What is the point that it is not so simple? | |
| Jul 8, 2014 at 18:07 | comment | added | H A Helfgott | ... but if anybody can get $< (1-\epsilon) p$ for quadruple exponentiation, Kate and I will be very happy. | |
| Jul 8, 2014 at 16:02 | comment | added | Andreas Thom | Right, sorry, I confused $\epsilon$ and $1-\epsilon$. | |
| Jul 8, 2014 at 14:35 | comment | added | H A Helfgott | Yes, we know that - that gives that there are at most $(1-\epsilon) p$ solutions. The answer below gives $<\epsilon p$ (without attempting to follow closely the group-theoretical ideas that give $(1-\epsilon) p$). Notice that the supposedly non-group-theoretical proof for two iterations (and possibly that for three iterations) is soft enough that it can be adapted even if there are $o(p)$ breaking points. | |
| Jul 8, 2014 at 14:31 | comment | added | Andreas Thom | Another comment. It is true but not trivial that Higman's group with three instead of four generators is trivial -- as far as I remember. This also implies the claim for three iterations and $p$ large enough. | |
| Jul 8, 2014 at 14:28 | comment | added | Andreas Thom | I also thought about this some time ago, but I found that one had to iterate a function on $\lbrace 0,\dots,p-1\rbrace$ which is kind of piecewise a translate of $x \mapsto 2^x$ -- with the number of breaking points $o(p)$. It seemed to get completely out of hand to interate such a function four times. | |
| Jul 8, 2014 at 14:18 | comment | added | H A Helfgott | ...and actually, you mean either "if one disproves a slightly weaker statement than the above", or, what is the same, "if one proves a slightly stronger statement than the negative of the statement above". I'm trying to keep "positive" and "negative" answers straight... | |
| Jul 8, 2014 at 14:10 | comment | added | H A Helfgott | Kate, do you have to give everything away? :) | |
| Jul 8, 2014 at 11:52 | comment | added | Kate Juschenko | Andreas, you are right, since the group itself has a lot of quotients, what I actually meant is that if one disproves a slightly stronger statemetn then above, then it would imply non-soficity. This motivates the question. | |
| Jul 8, 2014 at 9:29 | comment | added | Andreas Thom | Yes, sorry -- I switched between positive and negative. | |
| Jul 8, 2014 at 9:28 | comment | added | Andreas Thom | You are right, "multiplication by $2$" is almost conjugate to "addition of $1$" as a permutation on $\mathbb Z/p\mathbb Z$ (at least if the multiplicative order of $2$ is large). So indeed, there is some $t$ that almost does the job, that is enough for soficity. Your original question asks for some $t$ like this, that also almost satisfies $t^4={\rm id}$. | |
| Jul 8, 2014 at 8:39 | comment | added | H A Helfgott | On your second comment: which answer is positive and which answer is negative? I take you mean to say that, if $2^{2^{2^{2^x}}} = x \mod p$ had $> (1-\epsilon) p$ fixed points, then the discrete logarithm would be easy to compute? (Agreed.) | |
| Jul 8, 2014 at 8:37 | comment | added | H A Helfgott | Actually, Andreas, your example (the group $H$) strengthens the case for an algebraic approach. Its soficity corresponds to $2 (x+1) = 2x + 2$, which is, um, true. Or do you have a different soficity-algebra dictionary in mind? Please explain. | |
| Jul 8, 2014 at 8:03 | comment | added | Andreas Thom | Another comment, if the answer is positive, then the discrete logarithm is not as uncomputable as we think it is. | |
| Jul 8, 2014 at 6:49 | comment | added | Andreas Thom | Kate, I think it might well be that Harald's question can be answered positively, but Higman's group is still sofic. For example $H= \langle a,t \mid tat^{-1}a=a^2tat^{-1} \rangle$ is somewhat of a similar type, known to be sofic -- but I do not think that an algebraic approach like this can show it. | |
| S Jul 8, 2014 at 5:48 | history | bounty started | Kate Juschenko | ||
| S Jul 8, 2014 at 5:48 | history | notice added | Kate Juschenko | Draw attention | |
| S Jul 7, 2014 at 22:03 | history | bounty ended | CommunityBot | ||
| S Jul 7, 2014 at 22:03 | history | notice removed | CommunityBot | ||
| Jul 6, 2014 at 19:58 | comment | added | Kate Juschenko | Yes, Andreas, this is how we've got into it. In fact, one can make a reformulation of soficity of Higman, which would be very closely related to the question above. | |
| Jul 6, 2014 at 15:08 | comment | added | Andreas Thom | This question is related to the question whether Higman's group $G= \langle a,b,c,d \mid ab^2=ba, bc^2=ca, cd^2=dc, da^2=ad \rangle$ (which is known not to have any finite quotients) is sofic. | |
| Jul 6, 2014 at 9:47 | answer | added | Sean Eberhard | timeline score: 6 | |
| Jul 4, 2014 at 21:13 | comment | added | Rodrigo | Indeed, for one exponent the bound may be improved up to $O(\sqrt{n})$, since we can have no two pairs of fixed points with the same difference. | |
| Jul 3, 2014 at 12:42 | answer | added | Geoff Robinson | timeline score: 5 | |
| Jun 29, 2014 at 20:45 | comment | added | Alvin | In fact, for one exponent, one can use quantitate Roth to improve the bound to p/\log\log p | |
| S Jun 29, 2014 at 20:10 | history | bounty started | H A Helfgott | ||
| S Jun 29, 2014 at 20:10 | history | notice added | H A Helfgott | Draw attention | |
| Jun 28, 2014 at 21:30 | answer | added | H A Helfgott | timeline score: 21 | |
| Jun 28, 2014 at 15:54 | comment | added | H A Helfgott | PS. I think I can do $2^{2^{2^x}} = x \mod p$, at the very least, but I would rather hear your solutions. | |
| Jun 27, 2014 at 18:25 | comment | added | H A Helfgott | To wit: let $f(x)=2^x$. We can have $\gg p$ solutions to $f(x)=x$ if only if there is a constant $k>0$ such that $f(x) = x \mod p$ and $f(x+k) = x+k \mod p$ are both true for $\gg p$ elements $x$ of $\{0,1,\dotsc p-1\}$. This implies, of course, that $f(x+k) = f(x) + k \mod p$, i.e., $2^k f(x) = f(x) + k \mod p$. For any $k\ne 0$, there is clearly at most one solution mod $p$ to this equation. Since $f$ is almost a bijection, we are done. (For $f=2^{2^x}$, the same argument applies; now $y=f(x)$ has to satisfy $y^{2^k} = y + k$, which also has a bounded number of solutions.) | |
| Jun 27, 2014 at 18:19 | comment | added | H A Helfgott | Well, for one or two exponentiations, I think it is fairly easy to show the bound $<\epsilon\cdot p$. | |
| Jun 27, 2014 at 18:16 | comment | added | Felipe Voloch | Is there any rationale for the size of the tower? Do you know the answer with fewer exponentiations? | |
| Jun 27, 2014 at 18:10 | history | edited | H A Helfgott | CC BY-SA 3.0 |
deleted 8 characters in body
|
| Jun 27, 2014 at 18:09 | comment | added | H A Helfgott | Good point. Assume $0\leq x<p$. | |
| Jun 27, 2014 at 18:06 | comment | added | Eric Wofsey | Do you mean to assume that $0\leq x<p$? Taking $x$ to $2^x$ does not give a well-defined function mod $p$. | |
| Jun 27, 2014 at 17:54 | history | asked | H A Helfgott | CC BY-SA 3.0 |