Let $p$ be a prime number, and consider the set $V \subset Z_p$ of $x$ modulo $p$ for which there exist an $m$ where $m^2 \equiv x \pmod p$. Specifically, consider a count version of that, where each integer $x$ is mapped to the total number of $m$ for which $m^2 \equiv x \pmod p$. Notate that counting function by $$f:Z_p\to Z_p$$
My question is the behavior of this function $f$. For example, I computed it specifically for $p=1163$ and computed a 60-wide fourier window across the $f$. That is $\hat f_t$ restricted to $[60t,60(t+1)] \cap Z_p$ is the $t$th transform of $f$. Here were the most frequent largest magnitude indices computed by $\arg \max_\theta |\hat f_t(\theta)|^2$:
- $28$, 10.8% of the time.
- $3, 5, 30$, 8.1% of the time each. (16.2% total)
- $6, 9, 15, 17, 18, 21, 25, (29=31)$, 5.4% of the time each. (43.2% total)
That accounts for $>70\%$ of the weight. I've found nice repeating patterns for this whenever $p$ is composite, but that is why I'm interested in the prime case. Where exactly does this function $f$ come from when $p$ is prime? The fourier transforms are nonsensical and I'm unable to figure out a pattern generalizing from one prime $p$ to the next $p' > p$. Would like to know if these objects have been studied before.
EDIT: For the composite case, consider $1163 + 1 = 1164$. Doing the same process with the windowing fourier with gap 60, we find
- $15$, 89.2% of the time
- $20$, 10.8% of the time
And this is far more typical for the composite numbers, for the fourier to properly break them down due to their symmetries. But with the primes, I am just getting complete junk out of this thing, what is the deal with the distribution of counts of square roots modulo a prime?
EDIT 2: To be extremely concrete, the first 60 images of $f$ when $p=1163$ should be
[1, 2, 0, 2, 2, 0, 0, 0, 0, 2, 2, 2, 2, 0, 2, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 0, 0, 2, 0, 0, 2, 2, 2, 2, 2, 2, 0, 2, 0, 2, 2, 2, 0, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 2, 0, 2, 2]```