Take the 2-minute tour ×


This problem looks very simple and I conjecture it's true but I have a hard time proving it. It'd be very useful for my work (I'm doing a PhD) and I'll be glad to cite you in a future article if you help me.

Let $P$ be a random permutation of $\mathbb{Z}/N\mathbb{Z}$ with the condition that $P$ verifies $q$ equations : $P(a_i)=b_i, i\leq q$. Let $k_0, k_1$ be random and $x_1, x_2, y_1, y_2$ fixed numbers with $x_1\neq x_2, y_1\neq y_2$

Prove that : $$Pr[P(x_2+k_0)=y_2+k_1 | P(x_1+k_0)=y_1+k_1] \geq (1-\frac{q}{N}) \frac{1}{N-1}$$

Thank you !

share|improve this question
Since $k_0$ and $k_1$ are random, wouldn't it simply the statement (without loss of generality) to take $x_1=y_1=0$? –  David Feldman Oct 4 '12 at 15:57
What if $N=3$, and we have two equations $P(1)=1$, $P(2)=2$, $(x_1,y_1)=(0,0)$ and $(x_2,y_2)=(1,2)$. Don't you get probability 0? –  David Feldman Oct 4 '12 at 18:43
For prime $N$, we also lose nothing by taking $x_2=y_2=1$. –  David Feldman Oct 4 '12 at 21:12

2 Answers 2

up vote 2 down vote accepted

My second comment indicates that I think you need to amend your conjecture, or else I don't understand.

Allow me to sketch some relevant ideas for getting non-trivial lower bounds. If my sketch does not suffice, I'll try to flesh it out when I have more time.

One should think of permutations here in terms of their cycle structures.

Your $q$ equations join some of the elements of ${\Bbb Z}/N{\Bbb Z}$ into cycles and others into finite order segments, each with, let's say, a head and a tail. Write $H$ for the set of heads, $T$ for the set of tails. Write $G$ for the graph of the partial function the equations determine.

Specifying a permutation satisfying the equations amounts to giving a bijection from $T$ to $H$. Since $|T|=|H|=N-q$, $(N-q)!$ permutations satisfy the equations and crucially, any given tail will have probability $1/(N-q)$ of joining any particular head.

The particular equations don't matter to your conjecture, only the resulting $T$ and $H$.

As per my comment, take $x_1=y_1=0$.

Now your probability conditions on either $(k_0,k_1)\in T\times H$ or $(k_0,k_1)\in G$.

Your probability calculation reduces to estimating the probabilities that either $(x_2+k_0,y_2+k_1)\in T\times H$ or $(x_2+k_0,y_2+k_1)\in G$.

That makes four cases to consider and I confess I have not yet worked out the details.

This helps with one case: given $T$, $H$ both of cardinality $N-q$, how small can we have the intersection $T\times H \cap ((T+x_2)\times (H+y_2))$. If $q$ is not too small, the pigeon-hole principle gives a lower bound (but this does not exploit the product structure of $T\times H$).

share|improve this answer
Thank you for your answer. Indeed, I forgot to say that $q$ should be less or equal to $N/2$ (I think, but I'm not sure). I have some ideas that could help : If you want to study $$Pr[P(x_1+k_0)=y_1+k_1]$$ you see that there is $N-q$ values of $k_0$ and $N-q$ values of $k_1$ such that both $x_1+k_0$ and $y_1+k_1$ are new input (and output) to $P$ (ie we don't have $x_1+k_0=a_i$ and $y_1+k_1=b_j$ for some $i$ or $j$). Now, if you choose one of those values of $k_0, k_1$, you connect $x_1+k_0$ to $y_1+k_1$ with probability $1/(N-q)$. –  Rodolphe Oct 4 '12 at 21:47
So we know that $$Pr[P(x_1+k_0)=y_1+k_1]\geq (N-q)/N * (N-q)/N * 1/(N-q = (N-q)/N² = (1-q/N) * 1/N$$ With the same reasoning, you can show that : $$Pr[P(x_1+k_0)=y_1+k_1\textnormal{ and }P(x_2+k_0)=y_2+k_1]\geq (1-2q/N) * 1/(N(N-1))$$ That's why, it seems intuitive (and I'm pretty sure it's true) to conjecture what I said in the first post. –  Rodolphe Oct 4 '12 at 21:51

Thank you for your answer. I think I solved the problem but it's just the beginning. I had something wrong in the conjecture.

First, let's note $C_i$ the event $P(x_i+k_0)=y_i+k_1$.

We have to slightly change the conjecture (I forgot a factor 2) : $$Pr[C_2|C_1]\geq (1-\frac{2q}{N})\times\frac{1}{N-1}.$$

We have $$Pr[C_2|C_1]=Pr[C_2\cap C_1]/Pr[C_1]$$ and I know that $Pr[C_1]=1/N$ (easy computation) and for $C_2\cap C_1$, if $x_1+k_0$ and $x_2+k_0$ are not one of the $a_i$ and $y_1+k_1, y_2+k_1$ are not one of the $b_i$ then the two equations occur with probability $\frac{1}{(N-q)(N-1-q)}$ so we have : $$Pr[C_2|C_1]\geq (N-2q)/N\times (N-2q)/N \times \frac{1}{(N-q)(N-1-q)} \times N$$ which almost solve the conjecture (I don't mind the term in $q²/N²$).

Now I have to prove something like $$Pr[C_3|C_2,C_1]\geq (1-\frac{2q}{N})\times\frac{1}{N-2}$$

share|improve this answer

Your Answer


