In particular, I'm considering the set
$S(n, k, z) = \{(x, y) \in (\mathbb{Z}_n^k)^2 \mid \langle x, y \rangle = z\}$
which contains, for any $n, k, z$ each pair of vectors $(x, y) \in (\mathbb{Z}_n^k)^2$ which has the property that $\sum_{i \in [n]} x_i y_i = z$. I want to know how much smaller this set is than $(\mathbb{Z}_n^k)^2$ itself, which I state mathematically using the following two functions:
$f(n, k, z) = |S(n, k, z)|$
$\rho(n, k, z) = \frac{f(n, k, z)}{n^{2k}}$
It's not a priori clear how to compute these functions, but I've done a little prepping of $f$ with a question on mathoverflow as well as some simply recurrence expansion which I did myself.
I believe its clear that we can partition each $S(n, k, z)$ into sets which each have unique first components $x_1, y_1$:
$S(n, k, z) = \oplus_{(x_1^*, y_1^*) \in \mathbb{Z}^2}\{ (x, y) \in (\mathbb{Z}^k)^2 \mid x_1 = x_1^*, y_1 = y_1^*, \langle x, y\rangle = z \}$
Writing the concatenation of $a, b$ as $a.b$, it is clear that we can also write:
$S(n, k, z) = \oplus_{(x_1^*, y_1^*) \in \mathbb{Z}^2} \{ (x_1^*.x, y_1^*.y) \mid x, y \in \mathbb{Z}^k, \langle x_1^*.x, y_1^*.y \rangle = \langle x, y \rangle = z - x_1^*y_1^* \}$
and then I think its clear that:
$f(n, k, z) = \sum_{(x_1, y_1) \in \mathbb{Z}_n^2} f(n, k - 1, z - x_1y_1)$
Using the fact that $ax\equiv b (\text{mod }n)$ has $(a, n)$ solutions if $(a, n) \mid (b, n)$ and none otherwise, we can see easily that:
$f(n, 1, z) = \sum_{y \in \mathbb{Z} :(y, n) \mid (z, n)} (y, n)$
Using the fact that $|\{ y \in \mathbb{Z}_n \mid (y, n) = d \}| = \varphi(\frac{n}{d})$, we can further see that:
$f(n, 1, z) = \sum_{d \in \mathbb{Z_m}:d|(z, m)} d \varphi(\frac{n}{d})$
We can further simplify this for primes:
$f(p, 1, z) = \sum_{d \in \mathbb{Z}_p:d|(z, p)} d \varphi(\frac{p}{d})$
clearly $(z, p) = 1$ or $p$, the latter case being if $z = 0$. Let's deal with that case:
$f(p, 1, 0) = \varphi(p) + p \varphi(\frac{p}{p}) = p + p(1 - \frac{1}{p}) = 2p - 1$
and in the other case we only have the term $\varphi(p)$, as the $p$ divisor is gone because $0 < z < p, z \neq p \Rightarrow (z, p) = 1$, so we can write
$f(p, 1, z \neq 0) = \varphi(p) = p(1 - \frac{1}{p}) = p - 1$
This is great but I still can't really do much to simplify the initial recurrence and I feel like this function $f$ is going to be quite difficult to compute for most $n$. I'm looking for help simplifying $f$ for higher $k$ and for special cases of $n, z$, particularly $z = 0$, as that's an interesting case for algorithm design.