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 !

  • 1
    $\begingroup$ 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$? $\endgroup$ – David Feldman Oct 4 '12 at 15:57
  • $\begingroup$ 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? $\endgroup$ – David Feldman Oct 4 '12 at 18:43
  • $\begingroup$ For prime $N$, we also lose nothing by taking $x_2=y_2=1$. $\endgroup$ – David Feldman Oct 4 '12 at 21:12

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$).

  • 1
    $\begingroup$ 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)$. $\endgroup$ – Rodolphe Oct 4 '12 at 21:47
  • $\begingroup$ 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. $\endgroup$ – 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}$$


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.