MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $p$ be a large prime and $n \geq 3$ be an integer. Let $f$ and $g$ be two arbitrary bijections from $\mathbb{F}_p^n$ to $\mathbb{F}_p^n$. I want to find a condition on $f$ and $g$ such that the inner product $\langle f(x), g(y) \rangle$ is almost independent of $\langle x, y \rangle$ for $x,y$ chosen uniformly at random from $\mathbb{F}_p^n$. In other words we want to characterize $f$ and $g$ such that for any $i, j \in \mathbb{F}_p$, $$P(\langle f(x), g(y) \rangle = i \; | \; \langle x, y \rangle = j) \approx \frac{1}{p}\;.$$

This does not hold if, for example, $f(x) = x$ and $g(y) = cy$ for some $c \in \mathbb{F}_p$ and for all $x, y$. More generally, this does not hold if $f(x) = Ax$ and $g(y) = c(A^T)^{-1}y$ for some invertible matrix $A$ in $\mathbb{F}_p^{n \times n}$. The question that I want to find an answer for is whether these are the only cases where the statement is not true. More formally stated:


Let $n \geq 3$, and let $f, g$ be bijections from $\mathbb{F}_p^n$ to $\mathbb{F}_p^n$. If for any invertible matrix $A\in \mathbb{F}_p^{n \times n}$,

$$P_{x \leftarrow \mathbb{F}_p^n} (f(x) = Ax) = o(\frac{1}{p^2})\;,$$

then for any $i, j \in \mathbb{F}_p$, and $x \leftarrow \mathbb{F}_p^n, y \leftarrow \mathbb{F}_p^n$,

$$P(\langle f(x), g(y)\rangle = i \;|\; \langle L, R \rangle = j) = \frac{1}{p} + o(\frac{1}{p}) \;.$$

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.