4
$\begingroup$

Let $f:Z_2^n \to Z_p$ be a one-to-one map, where say $2^n<p<2^{n+1}$. What is the maximal probability that $\Pr[f(x+y)=f(x)+f(y)]$ where $x,y \in Z_2^n$ are uniform and independent? The identity map (treating bits as base-two representation) gives probability of $(3/4)^n$. Is it true that this probability for any $f$ is always $\le 2^{-cn}$ for some absolute $c>0$?

Also, the same question, but in the other direction: $f:Z_p \to Z_2^n$, where here $2^{n-1}<p<2^n$. Is the probability always $\le p^{-c}$ for some $c>0$?

All the references I found show that these probabilities are somewhat smaller than 1, but I suspect that they should be polynomially small in the group size. This might be well known - I appreciate any reference.

$\endgroup$
3
  • $\begingroup$ The techniques in this paper arxiv.org/pdf/1308.2247v1.pdf might be useful. $\endgroup$
    – Lucia
    Jun 4, 2015 at 0:50
  • $\begingroup$ What exactly? the paper seems to study problems in characteristics zero $\endgroup$
    – Shachar
    Jun 4, 2015 at 4:06
  • $\begingroup$ I was thinking of the ideas around Corollary 2.4 in that paper. (And also that ${\Bbb Z}/p$ for large enough $p$ might behave not too differently from ${\Bbb Z}$.) Anyway, just a quick thought. $\endgroup$
    – Lucia
    Jun 4, 2015 at 4:21

1 Answer 1

3
$\begingroup$

I do not know of specific references, but perhaps you could proceed as follows.

Lemma: Suppose that $p$ is an odd prime and $f: \mathbb{Z}/p\mathbb{Z}\rightarrow \mathbb{F}_2^n$ is injective. Then \begin{equation*} \mathbb{P}(f(x+y)=f(x)+f(y))=p^{-\Omega(1)}. \end{equation*}

Proof: Write $\Gamma:=\{(x,f(x)):x \in \mathbb{Z}/p\mathbb{Z}\} \subset \mathbb{Z}/p\mathbb{Z} \times \mathbb{F}_2^n$ and $\varepsilon$ for the probability we are interested in. Using the language of summation instead of expectation the says \begin{equation*} \langle 1_\Gamma\ast 1_\Gamma,1_\Gamma\rangle_{\ell_2} = \varepsilon p^2, \end{equation*} where \begin{equation*} g\ast h(x):=\sum_{y+z=x}{g(y)h(z)} \text{ and }\langle g,h\rangle_{\ell_2}:=\sum_x{g(x)\overline{h(x)}}, \end{equation*} for functions $g$ and $h$.

Since $f$ is a function, $|\Gamma|=p$, and so by Cauchy-Schwarz in the usual way we get \begin{equation*} \|1_\Gamma\ast 1_\Gamma\|_{\ell_2}^2 \geq \frac{1}{|\Gamma|}\langle 1_\Gamma\ast 1_\Gamma,1_\Gamma\rangle_{\ell_2}^2 \geq \varepsilon^2 \frac{p^4}{|\Gamma|} = \varepsilon^2 |\Gamma|^3. \end{equation*} The Balog-Szemerédi-Gowers lemma then tells us that there is a set $\Gamma' \subset \Gamma$ with $|\Gamma'| \geq \varepsilon^{O(1)}|\Gamma|$ and \begin{equation*} |\Gamma'+\Gamma'| \leq \varepsilon^{-O(1)}|\Gamma'|. \end{equation*} For a set $\Lambda \subset \mathbb{Z}/p\mathbb{Z} \times \mathbb{F}_2^n$ write $2\cdot \Lambda:=\{(2x,2y): (x,y) \in \Lambda\}$. Since $p \neq 2$ the map \begin{equation*} \Gamma' \rightarrow 2\cdot \Gamma'; (x,f(x)) \mapsto (2x,2f(x)) \end{equation*} is a bijection and hence $|2\cdot \Gamma'| = |\Gamma'|=\varepsilon^{O(1)}p$. Now, by Cauchy-Schwarz again we have \begin{equation} \tag{1}\label{eq:1} \|1_{\Gamma'} \ast 1_{2\cdot \Gamma'}\|_{\ell_2}^2 \geq \frac{(|\Gamma'||2\cdot \Gamma'|)^2}{|\Gamma'+2\cdot\Gamma'|} = \varepsilon^{O(1)}p^3, \end{equation} where the last inequality follows from the fact that \begin{equation*} |\Gamma'+2\cdot \Gamma'| \leq |\Gamma' + \Gamma' + \Gamma'| \leq \varepsilon^{-O(1)}|\Gamma'| = \varepsilon^{-O(1)}p \end{equation*} by Plünnecke's inequality.

On the other hand, if $(a,f(a)),(b,f(b)) \in \Gamma'$ and $(2c,2f(c)),(2d,2f(d)) \in 2\cdot\Gamma'$ have \begin{equation} \tag{2}\label{eq:2} (a,f(a))+(2c,2f(c))=(b,f(b)) +(2d,2f(d)), \end{equation} then $a+2c=b+2d$ and $f(a)+2f(c)=f(b)+2f(d)$. But the image of $f$ is in $\mathbb{F}_2^n$ and so $2f(c)=0=2f(d)$ whence $f(a)=f(b)$. On the other hand $f$ is injective so $a=b$. It follows from this (and the equation $a+2c=b+2d$) that $2c=2d$, but $p$ is odd and so $c=d$. Thus there are at most $p^2$ quadruples such that \eqref{eq:2} holds. These quadruples are precisely what is counted by the left hand side of \eqref{eq:1} and so \begin{equation*} \varepsilon^{O(1)}p^3 \leq p^2, \end{equation*} from which we get $\varepsilon = p^{-\Omega(1)}$ as claimed.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.