bio | website | maths.bris.ac.uk/~mahah |
---|---|---|
location | ||
age | ||
visits | member for | 4 years, 11 months |
seen | 2 days ago | |
stats | profile views | 3,866 |
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$ |