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


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|cite|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
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|cite|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|cite|improve this answer

Your Answer


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

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