2,208 reputation
1449
bio website maths.bris.ac.uk/~mahah
location
age
visits member for 4 years, 11 months
seen 2 days ago

Sep
15
awarded  Popular Question
Jul
23
awarded  Popular Question
Jul
11
comment Fixed points of $x\mapsto 2^{2^{2^{2^x}}} \mod p$
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
8
comment Fixed points of $x\mapsto 2^{2^{2^{2^x}}} \mod p$
... but if anybody can get $< (1-\epsilon) p$ for quadruple exponentiation, Kate and I will be very happy.
Jul
8
comment Fixed points of $x\mapsto 2^{2^{2^{2^x}}} \mod p$
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
comment Fixed points of $x\mapsto 2^{2^{2^{2^x}}} \mod p$
...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
comment Fixed points of $x\mapsto 2^{2^{2^{2^x}}} \mod p$
Kate, do you have to give everything away? :)
Jul
8
comment Fixed points of $x\mapsto 2^{2^{2^{2^x}}} \mod p$
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
comment Fixed points of $x\mapsto 2^{2^{2^{2^x}}} \mod p$
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
comment Fixed points of $x\mapsto 2^{2^{2^{2^x}}} \mod p$
That's nice - yes, the question we are discussing is really about the cycles of $f_g(u)$, in the paper's notation. It looks like my (self-)answer improves on Theorem 6. Unfortunately, the paper contains no bounds on what it calls $N_g(4)$ (which is what we are trying to bound non-trivially here).
Jul
6
awarded  Good Question
Jul
6
comment Fixed points of $x\mapsto 2^{2^{2^{2^x}}} \mod p$
Well, let us stay away from $p$ that give such an easy negative answer. The interpretation some have given above (making $f$ into a bijection) is closer to what I had in mind.
Jul
4
comment Fixed points of $x\mapsto 2^{2^{2^{2^x}}} \mod p$
Note that the argument above is in some sense "local", in that relies entirely on comparisons between the values of functions at $x$ and at $x+k$, where $k$ is bounded by a constant. Something tells me that this will not be so straightforward for the quadruple power.
Jul
4
comment Fixed points of $x\mapsto 2^{2^{2^{2^x}}} \mod p$
Interpret the question as loosely or as strictly as you wish, as long as it helps to make it possible to say something meaningful. Want to define $f(x)=2^x$ for $x\in {0,1,\dotsc,p-2}$, $f(x) = 0$ for $x=p-1$, and $f(x) = f(\overline{x})$ elsewhere, where $\overline{x}$ is the element of $\{0,1,\dotsc,p-1\}$ congruent to $x$ modulo $p$? Be my guest.
Jul
3
awarded  Popular Question
Jul
2
awarded  Inquisitive
Jul
2
awarded  Curious
Jun
29
awarded  Nice Answer
Jun
29
awarded  Nice Question
Jun
28
answered Fixed points of $x\mapsto 2^{2^{2^{2^x}}} \mod p$