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 $N\in\mathbb{N}$ and $G$ the group $\mathbb{Z}/n\mathbb{Z}$.

Let $q< N$ and:

  • $a_1, ..., a_q$ pairwise distinct elements of $G$
  • $b_1, ..., b_q$ pairwise distinct elements of $G$
  • $x_1, ..., x_q$ pairwise distinct elements of $G$
  • $y_1, ..., y_q$ pairwise distinct elements of $G$.

Let $P$ be a random permutation of $G$ verifying $P(a_i)=b_i, \forall i\leq q$.

Let $Q$ be a random permutation of $G$.

Let $k_0, k_1$ be random elements of $G$.

Let $E$ denote the function $E(x)=P(x + k_0)+k_1$

I want to prove that $$\Pr[E(x_q)=y_q|E(x_\ell )=y_\ell, \forall \ell < q]$$ is greater than $$\left(1-\frac{2q}{N}\right)\Pr[Q(x_q)=y_q|Q(x_\ell)=y_\ell, \forall \ell < q]$$

The first probability is over the randomness of $k_0, k_1$ and $P$. The second probability is over the randomness of $Q$.

If we hadn't equations $P(a_i)=b_i$ on $P$, then the two probabilites would be equal. So this result would show that, adding conditions to $P$ doesn't change too much the distribution of $(E(x_1), ..., E(x_q))$, it should still be close of the uniform distribution.

Thank you

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.