Question

Hello,

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 !

Answer 1

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

Answer 2

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}$$