Fix an integer $0<a<p-1$, and an odd prime $p$.
Define $$S(a,p)=\sqrt{a+\sqrt{a+\sqrt{a+\cdots}}}\;\;(\text{mod}\;p)$$ to be the set of all integers $x\in\{0,...,p-1\}$ such that, for some positive integer $n$, $$x\equiv \sqrt{a+\sqrt{a+\sqrt{a+\cdots + \sqrt{a+x}}}}\;\;(\text{mod}\;p)$$ with exactly $n$ radicals, and where each square root evaluates to a valid modular square root such that the square root branch is closest to $0$ and positive.
For instance the square root of $4 \mod 17$ is $2$ and not $-2 = 15 \mod 17$
Now this seems to suggest that
$$x^2 = a + x \mod p$$
But I am unsure and confused.
For starters what if one of the square roots does not exist but the equation
$$x^2 = a + x \mod p$$
does have a solution ?
We need square root extensions then ?
How many cycles exist and what the minimum value for $n$ ?
$$x^2 = a + x \mod p$$
has half of the residues as solution because of the quadratic residue theorems and abc formula.
But what if
$$x^2 = a + \sqrt{a+x} \mod p$$
$$(x^2 - a)^2 = a + x \mod p$$
is the correct equation ?
Now we get a degree 4 equation from 2 iterations.
In general it seems the number of iterations for the polynomial equation for $x \mod p$ must be a divisor of $n$. That makes sense.
But I took a specific branch for the square roots.
So instead of the degree of the defining polynomial for $x$ growing like $2^n$ , it seems rather to grow slower.
$n$ seems to be the only parameter to decide what $x$ we get since the branches are predetermined.
But not every element is a quadratic residue.
So for a given $p$ , $a$ and $n$ how many solutions $x$ do we get ?
What if we take the union of solution for a fixed $p,a$ and with $n$ going from $1$ to ...
I wanted to say from $1$ to $p-1$ but maybe $p-1$ is unneccessarily large.
What if we take the union of solution $x$ for a fixed $p,a$ and with $n$ going from $1$ to $c$ ? How many solutions do we get then ?
Number of solutions
$$sol(a,p,c) = ?? $$
$$S(a,p)=\sqrt{a+\sqrt{a+\sqrt{a+\cdots}}}\;\;(\text{mod}\;p)$$ where the dots seem to indicate ' infinity '. What does infinity mean here ? all solutions $x$ for any $n$ ? All cycles are given when every number divides $n$ hence
the max number of solutions to
$$S(a,p)=\sqrt{a+\sqrt{a+\sqrt{a+\cdots}}}\;\;(\text{mod}\;p)$$
is
$$sol(a,p,(p-1)!) $$
But I still lack insight.
Lets think backwards and use heuristics :
$$y^2 - a = x \mod p$$
has a probability $1/(2(p-1))$ to hold for a random $y$ and fixed$a$. $1/2$ because $y^2 = x - a$ must be solvable and $1/(p-1)$ to get the right residue.
So doing this step
$$y_{i-1}^2 - a = y_i$$
$n$ times gives a probability to give $x = y_0$ of $1 - (1 - 1/(2(p-1)))^n$.
This suggests the approximation
$$sol(a,p,(p-1)!) = \sum_{k= 1}^{(p-1)!} 1 - (1 - 1/(2(p-1)))^k$$
LET $L(p) = scm(1,2,3,...,p-1)$ ( smallest common multiple )
then a better one is
$$sol(a,p,L(p)) = \sum_{k= 1}^{(L(p)} 1 - (1 - 1/(2(p-1)))^k$$
But that is a very naive estimate. And it does not even depend on $a$ !? Also it does not seem to much focused on cycles or multiplicity of solutions.
How good is this asymptotic ? Can we improve it ?
Another idea that occured is this :
The first square root gave about (p-1)/2 solutions ( quadradic residue theorem ) The second square root gave (p-1)/4 solutions ( quartic residue theorem ) etc
So all cycles of roots gives about
$$(p-1)(1/2 + 1/4 + 1/8 + 1/16 + ...)$$
what suggests the total number of solutions is
$$2^{q(p)}$$
where $q(p)$ is the log base 2 of $p-1$.
so for instance
$p = 71$ gives about $64$ solutions. and $c = 6$ is enough ( $2^6 = 64 $ )
Still no dependance on $a$ in sight !?
Any ideas how to improve these estimates ?
edit
Edit : I reconsidered and maybe the following (related) estimate makes more sense :
The first square root gave about $(p-1)/2$ solutions ( quadradic residue theorem ) BUT I only allow the one closest to $0$. Therefore the probability goes to $1/4$ or about $(p-1)/4$ solutions. The second square root gave $(p-1)/4$ solutions ( quartic residue theorem ) normally BUT again I only allow one square root, the one closest to $0$. So the probability goes to $\frac{(1/4)}{4} = 1/16$ or about $(p-1)/16$ solutions.
etc
So all cycles of roots gives about
$$(p-1)(1/4 + 1/16 + 1/64 + 1/256 + ...)$$
what suggests the total number of solutions is
$$3^{q(p)}$$
where $q(p)$ is the log base 3 of $p-1$.
so for instance
$p = 71$ gives about $27$ solutions. and $c = 3$ is enough ( $3^3 = 27 $ )
Still no dependance on $a$ in sight !?
Any ideas how to improve these estimates ?
MAIN QUESTION :
What are the asymptotics or average asymptotics for
The Number of solutions of $x's$ : to the set of all integers $x\in\{0,...,p-1\}$ such that, for some positive integer $n$, $$x\equiv \sqrt{a+\sqrt{a+\sqrt{a+\cdots + \sqrt{a+x}}}}\;\;(\text{mod}\;p)$$ with exactly $n$ radicals, and where each square root evaluates to a valid modular square root such that the square root branch is closest to $0$ and positive.
For instance the square root of $4 \mod 17$ is $2$ and not $-2 = 15 \mod 17$
$$sol(a,p,c) = ?? $$
As function of $p$ ?
And how good are my estimates ?
SECONDARY QUESTION :
Same question , but how about dependance on $a$, is that really so irrelevant for the average asymptotic ?
How about asymptotics mainly focused on $a$ ?
TERNARY QUESTION :
Similarly ,dependancy on $n$ ?
( 4 th question : any patterns or number theory results ? Conjectures and plots are welcome too )
Ofcourse I am not demanding answers to all of these. The main question will get an accepted answer if solved.
But I wanted to make my priorities clear by listing the other non main questions.
Any other question will get an upvote when answered.